Papers for

resource allocators

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Query complexity limits fairness in dividing good and bad resources

The Query Complexity of Envy-Free Division: Cake, Chores, and Mixed Resources

Abstract: We study the query complexity of envy-free division for cake, chores, and resources with both positive and negative values. For arbitrary nonnegative nonatomic chore costs, we give a deterministic exact protocol using $2^{3n\log_2 n+O(n)}$ queries and cuts. For both cake and chores, a Las Vegas protocol uses $O(n^{21}\log^2(2n))$ expected queries and $O(n^{20}\log^2(2n))$ expected cuts. Conversely, every exact protocol with fixed positive success probability requires $Ω(n^2)$ expected queries in general, even with arbitrarily many output cuts at no query cost. For mixed cake and chores, no uniform finite expected-query bound exists even when every Cut returns the leftmost root or every Cut returns the rightmost root. This holds for any fixed positive multiplicative approximation factor and success probability, already when all net totals are one. An additive impossibility holds on the same normalized domain.

Sun 8 NovComputer Science and Game Theory
The gist
Fairly dividing things that people like (cake) and dislike (chores) is tricky, especially when both are mixed together. The authors studied how many questions you need to ask to guarantee a perfectly fair split without envy. They showed it can be done for just cake or chores with a certain number of steps, but when mixing positive and negative parts, no simple method exists with a predictable number of questions. This means splitting mixed resources fairly requires more complex approaches and possibly infinite effort.
Open → 2611.11424v1

Polynomial algorithms achieve fair and envy-free item allocations

Polynomial Algorithms for Simultaneous Share-Based and Envy-Based Guarantees

Abstract: We study the simultaneous achievement of share-based and envy-based fairness in the allocation of indivisible goods with nonnegative additive valuations. The AnyPrice share (APS) is a strengthening of the maximin share (MMS). A polynomial-time algorithm is known to guarantee a $2n/(3n-1)$ approximation of APS, but without an accompanying envy-based guarantee. Separately, allocations simultaneously satisfying minimum EFX share (MXS) and envy-freeness up to one less-preferred good (EFL), and subsequently the stronger requirement of residual maximin share (RMMS) together with EFL, have been shown to exist. However, the known constructions do not provide pseudopolynomial-time guarantees. We develop algorithms that combine these share-based and envy-based fairness requirements. First, for every $\varepsilon \in (0,1)$, we give an algorithm that computes an allocation satisfying exact EFL, $(1-\varepsilon)$-MXS, and $2n/(3n-1)$-APS. Its running time is polynomial in the binary input length and $1/\varepsilon$. Thus, we match the previously established polynomial-time APS approximation while simultaneously guaranteeing exact EFL and an arbitrarily close approximation to MXS. Second, we provide a pseudopolynomial-time algorithm that simultaneously guarantees exact MXS, exact EFL, and $2n/(3n-1)$-APS. Third, for every fixed number of agents, we obtain a pseudopolynomial-time algorithm that simultaneously achieves exact RMMS and exact EFL. Finally, we establish that computing a numerical threshold between MXS and RMMS is weakly NP-hard, even for additive valuations. This identifies a computational barrier to extending our polynomial-time approach to exact MXS through independently computed residual-valid share thresholds.

Sun 11 OctComputer Science and Game Theory
The gist
Dividing items fairly among people is hard when the items cannot be split. The paper finds ways to assign items so that each person feels they have a fair share and does not envy others, using efficient algorithms. The authors improved previous methods by combining two fairness ideas—sharing fairly and avoiding envy—and ensuring their algorithms run in reasonable time. They also show a complexity limit for some fairness measures, explaining why certain exact solutions are hard to find.
Open → 2610.15437v1

Envy-free sharing of indivisible goods guaranteed with perfect complements

Envy-Free Allocation of Indivisible Goods under Leontief Preferences

Abstract: Envy-freeness is a fundamental notion of fairness in the allocation of indivisible goods. In this paper, we study envy-free allocation under Leontief preferences, which model perfect complements. Although Leontief preferences have been extensively studied in the context of allocating divisible goods and market equilibria, they have received comparatively little attention for the allocation of indivisible goods. We show that, unlike additive valuations in cardinal preferences, an envy-free allocation always exists for Leontief preferences when there are at least two goods. In contrast, envy-free allocations may fail to exist when there is a single good, however it can be decided in polynomial time. We next study the problem of computing a welfare-maximizing envy-free allocation. We prove that this problem is NP-hard in general, whereas it is polynomial-time solvable when there is only a single good or agents have identical demands. Finally, we investigate the parameterized complexity of this problem.

Wed 23 SeptComputer Science and Game TheoryComputational Complexity
The gist
Fair division means giving items to people so no one feels jealous of another’s share. This paper studies a type of preference where goods must be combined in fixed proportions, called Leontief preferences, often seen as perfect complements. The authors show that if there are at least two goods, it is always possible to divide them fairly without envy. They also explore how hard it is to find the fairest such division and identify scenarios where this task is easier or harder. Their work helps understand fairness in situations where items cannot be split and must be combined in specific ways.
Open → 2609.28308v1