Source-linked AI summary
A Little Charity Guarantees Almost Envy-Freeness
Bhaskar Ray Chaudhury, Tellikepalli Kavitha, Kurt Mehlhorn, Alkmini Sgouritsa
TL;DR
Envy-free allocations need not exist for indivisible goods, motivating the study of fairness relaxations. The update rules use a minimal-envied-subset oracle to support a constructive allocation procedure. The paper guarantees almost-EFX allocations for general valuations by donating a small number of goods that nobody envies to charity, and shows its constructed allocation is 4/7-GMMS.
Problem
Envy-free allocations need not exist for indivisible goods, motivating the study of fairness relaxations.
Source: §1 · p. 2Method
The update rules use a minimal-envied-subset oracle to support a constructive allocation procedure.
Source: §1.1.1 · p. 4Results
The paper guarantees almost-EFX allocations for general valuations by donating a small number of goods that nobody envies to charity, and shows its constructed allocation is 4/7-GMMS.
Source: §3.2 · p. 15, §4 · p. 17Takeaways & Limitations
Whether complete EFX allocations always exist remains an open problem.
Source: §4 · p. 17For exact EFX with general valuations, the stated query guarantee is pseudo-polynomial and applies to two agents.
Source: §2.3 · p. 13
Abstract
from arXiv · showhide
Fair division of indivisible goods is a very well-studied problem. The goal of this problem is to distribute $m$ goods to $n$ agents in a "fair" manner, where every agent has a valuation for each subset of goods. We assume general valuations. Envy-freeness is the most extensively studied notion of fairness. However, envy-free allocations do not always exist when goods are indivisible. The notion of fairness we consider here is "envy-freeness up to any good" (EFX) where no agent envies another agent after the removal of any single good from the other agent's bundle. It is not known if such an allocation always exists even when $n=3$. We show there is always a partition of the set of goods into $n+1$ subsets $(X_1,\ldots,X_n,P)$ where for $i \in [n]$, $X_i$ is the bundle allocated to agent $i$ and the set $P$ is unallocated (or donated to charity) such that we have$\colon$ 1) envy-freeness up to any good, 2) no agent values $P$ higher than her own bundle, and 3) fewer than $n$ goods go to charity, i.e., $|P| < n$ (typically $m \gg n$). Our proof is constructive. When agents have additive valuations and $\lvert P \rvert$ is large (i.e., when $|P|$ is close to $n$), our allocation also has a good maximin share (MMS) guarantee. Moreover, a minor variant of our algorithm also shows the existence of an allocation which is $4/7$ groupwise maximin share (GMMS): this is a notion of fairness stronger than MMS. This improves upon the current best bound of $1/2$ known for an approximate GMMS allocation.
1 Introduction
The introduction motivates EFX with bounded charity and presents existence guarantees for general valuations alongside stronger approximate MMS/GMMS results for additive valuations. It also outlines the algorithmic constructions and situates these results within prior fairness work and open questions.
1 Introduction
- EFX requires that no agent envies another after any one good is removed; the paper seeks such allocations while bounding both the amount and value of charity.Earlier EFX-with-charity work [12] gave no bound on the number of unallocated goods or on how much agents value them.Source: §1 · pp. 2–3
1.1.1 General valuations
- For general valuations, an EFX allocation exists with |P| < n and vi(Xi) ≥ vi(P) for every agent, and it is computable with poly(n, m, V, 1/∆) value queries.The assumptions are that valuations are normalized and monotone.Source: §1.1.1 · pp. 3–4
1.1.2 Identical valuations
- When all agents have identical valuations, the proof yields a complete EFX allocation, providing an alternate proof of the result originally shown in [26].Source: §1.1.2 · p. 4
1.1.3 Additive valuations
- For additive valuations, modifying the algorithm's starting step ensures that its allocation retains the three general guarantees and has high Nash social welfare.The modified step uses the allocation computed in [12] as a black box.Source: §1.1.3 · p. 4
- For additive valuations, the MMS guarantee improves as |P| grows; when |P| = n−1, every agent receives at least (1−1/n)·MMS_i(n, M).When |P| = 0, the allocation is complete and EFX.Source: §1.1.3 · pp. 4–5
- A 4/7-GMMS allocation always exists for additive valuations and can be computed in pseudo-polynomial time.The result is obtained by modifying the last step of the algorithm.Source: §1.1.3 · p. 5
1.2 Our Techniques
- The technique uses cut-and-merge reallocation: it selects a most-envious agent, shifts bundles along an envy-graph path, and returns leftover goods to the unallocated pool.The shift improves every agent on the path without worsening others and restores EFX.Source: §1.2 · pp. 6–7
- When |P| = n − 1, every agent is a source and envies neither another agent’s bundle nor the unallocated set; the paper also establishes approximate-MMS and improved approximate-GMMS results.For additive valuations, the argument uses v_i(M)/n ≥ MMS_i(n, M).Source: §1.2 · p. 7
1.3 Related Work
- EFX is known to exist for three agents with additive valuations [15], but its existence for general valuations or more agents remains open.Caragiannis et al. introduced EFX.Source: §1.3 · p. 7
- Prior work showed that EF1 allocations can be Pareto-optimal and gave a pseudo-polynomial-time algorithm to compute one [8].Source: §1.3 · p. 7
1.4 Improvements with respect to the SODA version
- The revised version gives a pseudo-polynomial-time algorithm for bounded-charity EFX with general valuations, beyond the conference version’s gross-substitute setting.A relaxed definition of the “most envious agent” enables efficient implementation of the minimal-envied-subset oracle.Source: §1.4 · p. 8
2 Existence of an EFX-Allocation with Bounded Charity
This section develops query-efficient constructions for EFX allocations with fewer than n unallocated goods, including ε-relaxed EFX and results for identical valuations and two-agent settings.
2 Existence of an EFX-Allocation with Bounded Charity
- The algorithm returns an EFX allocation X and pool P with |P| < n and vi(P) ≤ vi(Xi) for every agent i, in at most nmV/∆ iterations.Here V is the maximum agent valuation of all goods and ∆ is the minimum difference between distinct valuations; U1 and U2 increase welfare while U0 decreases the pool size.Source: §2 · pp. 8, 11, 12
- U0 allocates a pool good when doing so preserves EFX, without decreasing welfare; if unavailable, every source and pool good pair has a minimal envied subset of size at most the source bundle.Each U0 application reduces the pool size by one.Source: §2 · p. 10
- U1 applies when an agent values the pool more than her bundle, reallocates a minimal envied subset, and increases social welfare while preserving EFX.The subset is chosen from the pool and is envied by the most envious agent.Source: §2 · p. 10
- When U0 is unavailable and |P| ≥ n, a cycle of distinct sources, pool goods, and reachable most-envious agents enables U2, which increases welfare and preserves EFX.The cycle's existence follows from the condition that the pool has at least n goods.Source: §2 · pp. 10–11
2.1 Finding an inclusion-wise minimal envied subset
- The minimal-envied-subset oracle checks removals to find an inclusion-wise minimal envied subset in at most nm value queries, yielding an overall bound of n^2m^2V/∆ value queries.The overall query bound applies to computing an allocation satisfying Theorem 8's three conditions.Source: §2.1 · p. 12
2.2 An FPTAS to Determine an “Almost” Desired Allocation
- The exact Algorithm 1 is pseudo-polynomial; for the relaxed version, each update yields a 1+ε valuation improvement, bounding iterations by poly(n, m, log(1+ε)V).The pseudo-polynomial limitation arises because valuation increases under the update rules can be very small.Source: §2.2 · pp. 12–13
- For normalized, monotone valuations, poly(n, m, 1/ε, log V) value queries find an allocation with (1+ε)-EFX comparisons, (1+ε)·v_i(X_i) ≥ v_i(P), and |P| < n.The relaxed EFX condition requires (1+ε)·v_i(X_i) ≥ v_i(X_j \ g) for every pair i, j and every g in X_j.Source: §2.2 · p. 12
2.3 New Proof of a Result from [26] for Identical Valuations
- For identical general valuations, Algorithm 1 proves that a complete EFX allocation always exists, providing another proof of the result of Plaut and Roughgarden [26].While unallocated goods remain, either U0 or U2 applies; U2 improves a source agent's bundle without making any agent worse off, and termination leaves P empty.Source: §2.3 · p. 13
- An EFX allocation for two agents with distinct valuations follows by first finding an EFX split under agent 1's valuation, then giving agent 2 the bundle she values more.Agent 1 receives the other bundle.Source: §2.3 · p. 13
- For two agents with general valuations, an EFX allocation takes pseudo-polynomially many value queries, while a (1−ε)-EFX allocation with charity takes poly(n, m, 1/ε, log V) queries.Plaut and Roughgarden [26] show that determining EFX may require exponentially many value queries even for two agents with identical submodular valuations.Source: §2.3 · p. 13
3 Guarantees on Other Notions of Fairness
For additive valuations, the paper extends its allocation guarantees to Nash social welfare, MMS, and GMMS. In particular, a complete allocation can be 4/7-GMMS, improving on the stated 1/2 bound.
3 Guarantees on Other Notions of Fairness
- For additive valuations, each agent’s bundle in the final allocation is worth at least half her bundle in an optimal Nash social welfare allocation.The proof initializes bundles using an allocation from [12] and maintains that no agent’s bundle value decreases.Source: §3 · p. 14
3.1 An Approximate MMS Allocation for Large |P|
- When the unallocated pool is sufficiently large, Theorem 14 gives an approximate MMS guarantee alongside the three conditions of Theorem 8.The proof selects agents including envy-graph sources and agents with at least two goods, then uses an MMS comparison after excluding agents with at most one good.Source: §3.1 · pp. 14–15
3.2 An Improved Bound for Approximate-GMMS
- For n agents with additive valuations and m goods, there exists a complete allocation Y that is 4/7-GMMS, compared with the stated existence of 1/2-GMMS allocations [6].Y is not necessarily EFX, but has sufficiently nice properties to establish its 4/7-GMMS guarantee.Source: §3.2 · pp. 15–16
- The GMMS proof reduces instances with more than n′ bad goods by removing pairs while preserving the MMS value, then bounds good- and bad-good values against Yi.Bad goods lie in two-good bundles; the reduction decreases the number of agents by one per pair, and the resulting bounds support the 4/7 guarantee.Source: §3.2 · p. 16
4 Conclusions and Open Problems
The paper leaves complete EFX existence as its major open problem, while reporting almost-EFX allocations for general valuations. It also points to improving or establishing the tightness of its fairness guarantees as future work.
4 Conclusions and Open Problems
- Whether complete EFX allocations always exist remains the major open problem, despite the paper’s almost-EFX result for general valuations.The authors say that result gives reason to hope for complete EFX at least for more structured valuations such as additive ones.Source: §4 · p. 17
- The authors identify improving their constant-factor guarantees or constructing instances showing they are tight as open directions.They frame these results as an early step toward an allocation with good guarantees across several fairness notions.Source: §4 · p. 17
- Amanatidis et al. announced a 4/7-GMMS guarantee matching this paper’s result, alongside a separate (φ−1)-EFX and 2/(φ+2)-GMMS guarantee.Their announcement also states that GMMS and hence EFX allocations always exist for additive valuations when m is at most n + 2.Source: §4 · pp. 17–18