22 problems

Let $M_1,\ldots,M_n$ be matroids on the same finite ground set $E$, with $\chi(M_i)\leq n$ for every $i=1,\ldots,n$. Suppose $n$ agents have additive valuations $v_1,\ldots,v_n$ of…

Let $M=(E,\mathcal{I})$ be a matroid on the finite set of goods $E$, and let $\chi(M)$ be the least number of independent sets in a partition of $E$. Suppose $\chi(M)\leq n$ and th…

Let $M=(E,\mathcal{I})$ be an independence structure, where $E$ is a finite set and $\mathcal{I}$ is closed under taking subsets. Let $\chi(M)$ be the least number of independent s…

Equitable distribution conjecture. It should be possible to cut at most $(r-1)m$ cookies and distribute them so that each child has the same amount of each kind of frosting and at…

Let $\mathcal{M}_1$ and $\mathcal{M}_2$ be matroids on the same ground set $E$, and assume that $E$ can be partitioned into $k$ independent sets in each matroid. For a set…

Crew–Narayanan–Spirkl conjecture. There is a partition $[n]=P\cup Q$ into two nonempty sets and a partition $S^1=X\cup X^c$ into two intervals such that

Soberón's polytopal extension conjecture. The sparse-colorful KKM theorem has a polytopal extension.

Let an instance consist of $n$ agents and $m$ items. A symEF$(n-1)$ allocation is an allocation satisfying symmetric envy-freeness up to $n-1$ items. SymEF$(n-1)$ existence conject…

Consider instances with a fixed number $n$ of agents and $m$ items, with probability taken over the paper's instance model. A symEF1 allocation is an allocation satisfying symmetri…

Let an instance consist of $n$ agents and $m$ distinct items, and let a symEF1 allocation mean an allocation satisfying symmetric envy-freeness up to one item. Assume that $m>n$. M…

Let $n,d$ be positive integers, and let $(\mu^1_1,\dots,\mu^1_n),\dots,(\mu^d_1,\dots,\mu^d_n)$ be $d$ tuples of $n$ absolutely continuous probability measures on $\mathbb{R}^d$. A…

Let $M$ be a matroid whose ground set $E$ can be partitioned into $k$ disjoint bases. The matroid is equitable if, for every subset $Z\subseteq E$, there is a partition…

Let $R_i(d)$, $R_p(d)$, and $R_f(d)$ denote the quantities for integer-labeled, permutation-labeled, and function-labeled fixed-point cycles, respectively. The lower-bound construc…

Let $\mathcal{T}$ be a tangle, and let $n$ agents have monotone continuous valuations. The Generalized gap threshold conjecture. A tangle $\mathcal{T}$ guarantees connected envy-fr…

Let $G$ be a biconnected graph. For positive integers $a,b$, say that $G$ is $(a,b)$-linked if, for every pair of disjoint vertex sets $M_1,M_2$ with $|M_1|=a$ and $|M_2|=b$, there…

Three-quarters maximin share conjecture. In the general case of any number of agents, there exist allocations guaranteeing all agents at least $3/4$ of their maximin share.

In a connected cake with $n$ agents, suppose each agent may receive at most $k$ disconnected pieces, and measure the optimal social welfare as the sum of the agents' values or the…

Let $n$ players have preferences over the connected pieces of the cake $[0,1]$. An envy-free division is a division of the cake into $n$ connected pieces assigned to the players so…

Universal upper-bound conjecture. For every $n$, every set of $n$ value measures, and every entitlement vector $t$, there exists a $t$-proportional allocation with at most $2n-2$ c…

Consider an instance of the cake-cutting problem with $k$ players. For integers $1\leq p,q\leq k$, the theorem gives bounds $\left\lceil \frac{k-p}{p}\right\rceil$ and…

Let $n$ be the number of agents and $m$ the number of bads in a mixed manna division problem, and let $CU(\mathcal{P})$ denote the set of competitive utilities for a problem…

Let an open necklace have $q$ types of beads, with the number of beads of each type divisible by $k$, and let a $k$-splitting divide the necklace among $k$ thieves so that every th…