Polynomial algorithms achieve fair and envy-free item allocations

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

Computer Science and Game Theory

Summary

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.

What this means in practice

  • For resource allocators: Assign indivisible resources fairly in settings where participants value items positively, ensuring envy-free and approximate fair shares efficiently.
  • For scheduling coordinators: Create fair task assignments that balance perceived fairness and envy avoidance among multiple agents in polynomial time.

Authors

Hannaneh Akrami, Arash Ashuri, Kurt Mehlhorn

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.