PaperlayerView exact revision on arXiv

Source-linked AI summary

Fair Allocation of Indivisible Goods: Improvement and Generalization

Mohammad Ghodsi, MohammadTaghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, Hadi Yami

arXiv:1704.00222v3cs.GT

TL;DR

The paper studies how to fairly allocate indivisible goods when exact maxmin-share allocations may not exist. It improves additive guarantees to 3/4-MMS, extends guarantees to non-additive valuations, and provides polynomial-time algorithms in several settings.

  • Problem

    Fair allocation asks how to distribute indivisible items so every agent receives at least a specified fraction of their maxmin share.

  • Method

    The paper develops allocation techniques for additive agents and extends the analysis to submodular, XOS, and subadditive valuations using valuation oracles.

  • Results

    A 3/4-MMS allocation always exists for additive agents and can be found in polynomial time; the paper also gives constant guarantees for submodular and XOS agents and a 1/10⌈log m⌉-MMS guarantee for subadditive agents.

  • Takeaways & Limitations

    The results improve the previous 2/3-MMS additive guarantee and provide polynomial-time allocation algorithms for additive, submodular, and XOS settings.

  • Takeaways & Limitations

    For non-additive valuations, eliciting an exact valuation function requires exponentially many oracle queries, although the allocation methods use only polynomially many queries.

Abstract

from arXiv · show

We study the problem of fair allocation for indivisible goods. We use the the maxmin share paradigm introduced by Budish as a measure for fairness. Procaccia and Wang (EC'14) were first to investigate this fundamental problem in the additive setting. In contrast to what real-world experiments suggest, they show that a maxmin guarantee (1-MMS allocation) is not always possible even when the number of agents is limited to 3. While the existence of an approximation solution (e.g. a $1/2$-MMS allocation) is quite straightforward, improving the guarantee becomes subtler for larger constants. Procaccia provide a proof for existence of a $2/3$-MMS allocation and leave the question open for better guarantees. Our main contribution is an answer to the above question. We improve the result of [Procaccia and Wang] to a $3/4$ factor in the additive setting. The main idea for our $3/4$-MMS allocation method is clustering the agents. To this end, we introduce three notions and techniques, namely reducibility, matching allocation, and cycle-envy-freeness, and prove the approximation guarantee of our algorithm via non-trivial applications of these techniques. Our analysis involves coloring and double counting arguments that might be of independent interest. One major shortcoming of the current studies on fair allocation is the additivity assumption on the valuations. We alleviate this by extending our results to the case of submodular, fractionally subadditive, and subadditive settings. More precisely, we give constant approximation guarantees for submodular and XOS agents, and a logarithmic approximation for the case of subadditive agents. Furthermore, we complement our results by providing close upper bounds for each class of valuation functions. Finally, we present algorithms to find such allocations for additive, submodular, and XOS settings in polynomial time.

1 Introduction

The paper advances maxmin-share fairness for indivisible goods, improving additive guarantees and extending approximation results to several non-additive valuation classes. It also develops polynomial-time algorithms and identifies upper bounds that limit achievable guarantees.

  • Additive Setting: The additive result improves the previous 2/3-MMS guarantee and is supported by new maxmin-share properties, generalized reducibility, coloring, and double-counting techniques.
  • Additive Setting: 3/4-MMS allocations always exist for additive agents, and a (3/4 −ϵ)-MMS allocation can be found in time poly(n, m).
  • Additive Setting: 4/5-MMS allocations are achievable algorithmically when there are exactly four additive agents, yielding a polynomial-time (4/5 −ϵ)-MMS algorithm.
  • Non-additive Settings: Submodular agents admit a 1/3-MMS allocation in polynomial time, while no allocation can exceed 3/4-MMS in some submodular instances.
  • Non-additive Settings: XOS agents admit a 1/5-MMS allocation, a polynomial-time 1/8-MMS algorithm with demand and XOS oracles, and instances with no guarantee above 1/2-MMS.
  • Non-additive Settings: Subadditive agents are guaranteed a 1/10⌈log m⌉-MMS allocation, while exact MMS computation is NP-hard and non-additive algorithms use only polynomially many valuation queries.

2 Preliminaries

The paper formalizes fair allocation for indivisible goods across several valuation classes and develops oracle-based methods for representing non-additive valuations. Its preliminaries define MMS allocations and reducibility, showing that guarantees for irreducible instances suffice for all instances.

  • Valuation models: The study restricts attention to additive, submodular, XOS, and subadditive valuation functions because unrestricted valuations admit no approximation guarantee.The unrestricted counterexample uses two agents and four items, where no allocation gives both agents positive value.
  • Oracle access: Additive valuations are represented directly, while submodular, XOS, and subadditive valuations require oracle access.Query oracles evaluate submodular functions; demand oracles provide stronger access for XOS and subadditive functions, and XOS oracles expose additive representations.
  • Maxmin share: An allocation is α-MMS when every agent receives a bundle worth at least α times that agent’s maxmin share.MMS is defined through partitioning the items into n bundles and maximizing the value of the least-valued bundle.
  • Reducibility: An instance is α-reducible when a subset of agents and items can already be allocated to meet their α-MMS requirements.The reducibility framework isolates a smaller residual instance after satisfying selected agents.
  • Reducibility: Proving an α-MMS guarantee for all α-irreducible instances is sufficient to prove it for every instance.The paper uses this reduction argument in both existential proofs and algorithms, while irreducible instances provide useful structural properties.

3 Additive Agents5

The additive-agent section proves that a 3/4-MMS allocation exists and gives a polynomial-time approximation algorithm. Its approach clusters agents, reduces irreducible instances, and completes allocations through prioritized bag filling.

  • 3/4-MMS allocation always exists for additive agents, improving the previously established 2/3-MMS guarantee.
  • A polynomial-time algorithm finds a 3/(4α)-MMS allocation when MMS values are computed within factor α.Combining this with an MMS PTAS yields a 3/(4+ϵ)-MMS allocation in polynomial time.
  • The main method clusters agents into three groups, allocates heavy items during clustering, and uses bag filling for the remaining items.The clusters are refined so remaining items satisfy useful low-value and non-satisfaction invariants.
  • The algorithm has two phases: clustering agents and satisfying them through a priority-aware bag filling procedure.Agent priorities depend on cluster membership and cycle-envy-freeness; each agent receives two sets whose combined value is at least 3/4.
  • Extending the algorithm beyond three clusters remains open because it requires generalized lemmas and hypergraph bounds.The authors identify these techniques as deeper and more complicated than the current graph-based analysis.
  • The proof reduces attention to 3/4-irreducible instances, where no item alone can satisfy an agent and every item has value below 3/4.The item-value bound holds for monotone valuations and therefore extends beyond additive valuations.

3.3 Phase 1: Building the Clusters

Phase 1 clusters agents into three groups, allocates initial items, and uses matching and vertex merging to preserve value and matching properties needed later.

  • Clustering: The algorithm divides agents into clusters C1, C2, and C3, allocating each agent sets fi and gi whose combined value is at least 3/4.Refinement targets remaining items that could satisfy agents, leaving items light enough for the newly formed cluster.
  • Building C1: C1 is constructed from an MCMWM in a 1/2-filtered value graph, with matched items allocated as fi to corresponding agents.Agents outside C1 satisfy the conditions needed for placement in C2 or C3.
  • Value bounds: For agents outside C1, items allocated during refinement have value below 1/2, and Lemmas 3.14 and 3.16 bound cross-agent values of fi and gi.Because these allocated sets are singletons, the bounds support the later value analysis.
  • Refining C1: A matching in the auxiliary graph saturates W1 and assigns second sets gi while preventing specified envy by unsaturated neighboring agents.After refinement, remaining items outside the filtered set cannot satisfy C1 agents.
  • Merged vertices: Merged pairs are worth less than 3/4 to every agent, while pairs are worth less than 2ϵk to agents in C1.The universal bound follows from 3/4-irreducibility; the C1 bound follows from the earlier refinement observation.
  • Building C2: The algorithm merges desirable item pairs into vertices whose weights sum the agents’ values, increasing the filtered graph’s maximum matching before constructing C2.The process stops when no desirable pair remains for the relevant agents.

3.4 Phase 2: Satisfying the Agents

Phase 2 fills feasible bundles from the remaining items using a priority order across clusters, while preserving value bounds and cycle-envy-freeness.

  • State after Phase 1: The remaining free items F satisfy cluster-specific bounds: they are below ϵi for C1 and C2 agents, and at most one can reach 1/4 for each C3 agent.These bounds make the items suitable for a controlled bag-filling process.
  • Priority order: The priority order combines cluster membership with topological ordering within cycle-envy-free agent sets.Agents in different clusters follow the prescribed cross-cluster ordering, while same-cluster ordering reflects the topological order.
  • Bag filling: Each round finds a minimal feasible subset S of F and assigns it to the lowest-priority eligible agent under the order ≺pr.The process repeats until F is no longer feasible for any agent.
  • Progress and value control: During the second phase, each round either satisfies an agent or makes an agent in Cf3 semi-satisfied, while selected bundles have bounded value to other clusters.For a selected Cf3 agent, the assigned fi is bounded by 2ϵj for agents in the relevant clusters.
  • Invariants: The sets C1, C2, and C3 remain cycle-envy-free throughout the second phase.This invariant supports the continued use of cluster-specific ordering and envy arguments.

3.5 The Algorithm Finds a 3/4-MMS Allocation

The final proof shows that the second phase cannot terminate while any agent remains unsatisfied, so every agent receives value at least 3/4.

  • Proof strategy: The proof assumes the second phase terminates with an unsatisfied agent and rules out membership in each cluster separately.The contradiction is that a remaining feasible set would exist for the selected unsatisfied agent.
  • Cluster C3: C3 is empty at termination because any remaining C3 agent would make the free-item set feasible under the case analysis.The argument covers both agents in Cs3 or Cb3 and agents entirely in Cf3.
  • Cluster C1: C1 is empty at termination because a winner’s value for the free items is shown to be at least ϵi using coloring and double counting.This contradicts termination when C1 still contains an unsatisfied agent.
  • Cluster C2: C2 is empty at termination by analogous arguments, using a four-coloring and double counting when ϵi < 1/8.When ϵi ≥ 1/8, feasibility follows through the corresponding direct argument.
  • Guarantee: All agents are satisfied before termination, and each receives a subset worth at least 3/4 to that agent.This establishes the claimed 3/4-MMS allocation guarantee.

3.6 Algorithm

The algorithm finds near-3/4-MMS allocations in polynomial time by combining clustering and bag filling, while handling reducible instances through efficient reductions.

  • Algorithmic structure: The method has two main phases: clustering agents into C1, C2, and C3, followed by bag filling.Clusters C1 and C2 are constructed using matching-based procedures, while remaining agents form C3.
  • Algorithmic guarantee: (3/4 −ϵ)-MMS allocations can be found in polynomial time for every additive instance.The result follows from an existential 3/4-MMS proof together with algorithmic reductions.
  • Clustering phase: Matching-based refinement and network-flow constructions make the clustering procedures polynomial-time computable.Reachability can be found by depth-first search, and minimum-cost maximum flow yields the required matching.
  • Bag filling phase: Reverse bag filling finds a minimally feasible subset by repeatedly removing any item whose removal preserves feasibility.This procedure makes the second phase polynomial time once feasible-set checks are available.
  • Reducibility: Reducible instances are handled by satisfying matched agents and recursively shrinking the instance, with at most n reductions.The relevant irreducibility conditions can be validated in polynomial time, including the final condition through emptiness testing.

4 Submodular Agents

For submodular agents, the paper establishes both an upper bound and a constructive lower bound on MMS fairness. It proves a 1/3-MMS guarantee in polynomial time with valuation query oracles, while showing that guarantees above 3/4 are impossible in general.

  • Computational model: Finding the exact MMS of a submodular function is NP-hard, but the paper’s oracle-based algorithm still computes a 1/3-MMS allocation in polynomial time.The oracle returns Vi(S) in O(1) time for any queried set and agent.
  • Upper bound: 3/4-MMS is an upper bound for submodular agents: some instances admit no allocation better than 3/4-MMS.The counterexample applies for any number of agents.
  • Related upper bounds: For XOS agents, no allocation can guarantee more than 1/2-MMS in some instances.The same construction also yields a 1/2-MMS upper bound for subadditive agents.
  • Valuation transformations: Ceiling functions preserve submodularity, XOS, and subadditivity, enabling capped-value arguments across these valuation classes.The preservation properties are stated separately for each class.
  • Existential guarantee: A 1/3-MMS allocation always exists for submodular agents.The proof reduces to 1/3-irreducible instances and uses an allocation maximizing ex(2/3)(A).
  • Algorithm: A 1/3-MMS allocation can be found in polynomial time given valuation query oracles.The algorithm increases ex2/3(A) by at least 1/3m per iteration and performs at most 2nm iterations.

5 XOS Agents

For XOS valuations, the paper proves a 1/5-MMS allocation always exists and gives a polynomial-time algorithm finding a 1/8-MMS allocation using demand and XOS oracles.

  • 1/5-MMS allocations always exist for fair allocation problems with XOS agents.
  • The existential proof uses reducibility, capped XOS valuations, and an allocation maximizing ex2/5.The proof handles 1/5-irreducible instances and extends the result to all instances.
  • A polynomial-time algorithm finds a 1/8-MMS allocation using only demand and XOS oracles, without knowing the agents’ maxmin values.The algorithm addresses both the difficulty of finding a suitable transfer set and the NP-hardness of exact MMS scaling.
  • Each iteration increases ex1/4(A) by at least 1/12n, so the algorithm terminates after at most 3n^2 steps.The potential is bounded by n/4, yielding polynomial termination.
  • The algorithm remains correct when it replaces unknown MMS values with estimates that stay at least as large as the true values.The resulting allocation is still 1/8-MMS with respect to the true maxmin values.
  • The XOS algorithm also yields an 8-approximation algorithm for determining an XOS function’s maxmin value with r partitions.

6 Subadditive Agents

For subadditive valuations, the paper reduces each function to a dominated XOS function whose maxmin value loses only a logarithmic factor, obtaining a logarithmic MMS guarantee.

  • The reduction constructs an XOS function g dominated by subadditive f while preserving maxmin value within a logarithmic factor.
  • The optimal solution of the additive-function LP is at least f(ground(f))/ log m.The proof uses LP duality and a randomized construction based on subadditivity.
  • The reduction approximates f on each of n disjoint MMS-valued sets with additive functions, then takes their maximum to form g.
  • A subadditive fair allocation always admits a 1/10⌈log m⌉-MMS allocation.

7 Acknoledgment

The authors thank anonymous reviewers for thoughtful comments and direction.

  • The authors thank the anonymous reviewers for their thoughtful comments and direction.

A A 4/5-MMS Allocation for Four Agents

For four agents with additive valuations, the appendix proves that a 4/5-MMS allocation is possible through bundle repartitioning and a reduction to smaller allocation instances.

  • Algorithm outline: The construction begins with an optimal four-partition for one agent, then repartitions three bundles so another agent values each new bundle sufficiently.
  • Definitions and tools: A perfect set of bundles has the same cardinality as its agent set and can allocate one satisfying bundle to every agent.
  • Definitions and tools: The core of a satisfying bundle is its minimum-size subset that still satisfies the agent.Its items are ordered by value, and the core is the smallest high-value suffix.
  • Definitions and tools: If a core is worth 4/5 + β, every item in it is worth more than β to the agent, while every core is worth less than 8/5.
  • Final allocation: After the first two agents are handled, the remaining cases for agents three and four are resolved using perfectness and the three-agent allocation lemma.
  • Repartitioning lemmas: Three bundles can be formed to satisfy an agent from a four-partition by moving items from selected bundles.This repartitioning lemma supports the subsequent allocation of all four agents.
  • 4/5-MMS allocations are possible for four agents in the additive setting.

B Omitted Proofs of Section 3.2

These proofs establish structural consequences of MMS normalization and irreducibility, then use alternating paths and weighted matchings to derive contradiction-based lemmas.

  • MMS and reducibility: Removing one item leaves at least n − 1 MMS partitions with value at least 1 to the agent.The argument is that only one partition in an optimal n-partitioning can lose value.
  • MMS and reducibility: If an item is worth at least α to an agent, allocating it makes the instance α-reducible, contradicting α-irreducibility.The proof applies the definition of α-irreducibility after assigning the item.
  • MMS and reducibility: For two items, assuming every other agent values the pair at most 1 enables an n − 1 partitioning after removing them, yielding 3/4-reducibility.Removing two items affects at most two partitions; merging those partitions preserves value at least 1.
  • Matching structure: An alternating path from ˆY1 to ˆY2 that meets T exposes a neighbor outside M(T), proving |N(T)| > |T|.The first T-vertex on the path has a preceding unmatched edge, while its preceding vertex is not in T.
  • Matching structure: The proofs characterize FH(M, ˆX) as empty exactly when every subset T of ˆX satisfies |N(T)| > |T|.A matching saturating N(T) supplies the converse contradiction when FH(M, ˆX) is nonempty.
  • Weighted matching: Maximum-weight matching optimality rules out directed cycles and locally heavier replacement edges in the auxiliary graph.Cycle exchanges and single-edge replacements would preserve matching feasibility while increasing total weight.

C Omitted Proofs of Section 3.3

These proofs use irreducibility, Hall-type matching arguments, and filtered graphs to construct cluster matchings with controlled agent-item values.

  • Cluster C1: Irreducibility implies Hall’s condition for G1, so a matching exists that saturates every vertex in W1.If the condition failed, the instance would be reducible.
  • Reducibility contradiction: The construction ensures that combining each f_i with its paired item does not give value 1 to agents outside the selected set T.The proof separates agents outside C1 and inside C1, using values below 1/2 or bounds involving ϵ_i.
  • Cluster C1: A maximum matching M1 can be chosen so that each matched agent is a loser relative to any relevant unsaturated neighboring agent.Otherwise, replacing the edge would reduce the topological-order objective, contradicting its minimality.
  • Filtered matching: Algorithm 1 preserves saturation of X′1/2 while enlarging the maximum matching at every step.The reachable filtered vertices remain saturated, yielding both matching-size inequalities.
  • Cluster C3: For agents in C3, every pair of residual items has value below 1/2 when Algorithm 1 terminates.Termination means no desirable pair remains, and the residual vertex set is contained in the filtered region.

D Omitted Proofs of Section 3.4

The proofs preserve cycle-envy-freeness while refining clusters and bound the values of bundles assigned across the resulting subgroups.

  • Bundle bounds: For bundles f_i of size at most 2, every other agent values them below 3/4.Singleton bundles use Lemma 3.1, while merged two-item bundles use Lemmas 3.19 and 3.20.
  • Cycle-envy-freeness: Removing an agent preserves cycle-envy-freeness for C1 and C2, while the proof shows agent additions preserve it for Cs3.A first violating round would contradict the winner-loser property inherited by every proper subset.
  • Bundle bounds: Minimal bundle structure bounds an agent’s value for another agent’s bundle by 2ϵ_j.Removing any item leaves a non-feasible remainder, and individual items are also bounded by ϵ_j.
  • Priority ordering: Priority ordering ensures that an agent preceding another cannot feasibly receive the latter’s bundle, giving value below ϵ_j.When the order is reversed, minimality combines remainder and item bounds to obtain a 2ϵ_j bound.

E Omitted Proofs of Section 3.5

These proofs bound cross-agent values during the second phase and use aggregate white-item estimates to show that residual cluster C3 cannot persist.

  • Second-phase bounds: For any agent in C3 during the second phase, V_i(f_j ∪ g_j) < |S3| + 1/4.All but at most one satisfied agent contribute value below 1, while one exceptional round contributes below 5/4.
  • Second-phase bounds: At most one round can contain the exceptional case V_i(f_j ∪ g_j) < 5/4.This occurs only when the maximum-valued item in g_j is the unique residual item worth at least 1/4.
  • Eliminating C3: If C3 were nonempty, the accumulated bundle bounds would make the remaining free set feasible, contradicting Algorithm 1’s termination.The proof treats nonempty Cs3 and Cf3 separately and derives feasibility in each case.
  • Coloring argument: After C3 is eliminated, items are colored blue or white and MMS partitions are classified as B0, B1, or B2 by their blue-item counts.B0 has no blue items, B1 exactly one, and B2 at least two.
  • Coloring argument: The coloring proof uses the fact that no single item is worth 3/4 to the target agent, so white items in certain B1 partitions are worth at least 1/4.This lower bound is combined with upper bounds on white items assigned during the algorithm.

F Omitted Proofs of Section 4

The omitted proofs establish that truncating a submodular or XOS function at x preserves the relevant valuation class, and that the construction also yields subadditivity. Additional lemmas derive bounds using diminishing returns and summation arguments.

  • Properties of f_x: The truncated function f_x(S) is bounded above by x and by the original function f(S).These properties are recorded as Observations F.1 and F.2 and support the subsequent case analyses.
  • Submodularity: Submodularity of f_x follows by considering whether f(A) and f(B) are each below or above the truncation threshold x.The three cases use the bounds on f_x for large sets and equality f_x(S)=f(S) for sets below x.
  • XOS representation: For an XOS function f, the proof constructs finitely many additive functions whose maximum equals f_x.For each set S, the maximizing additive component of f is modified by zeroing items outside S and scaling values when f(S)>x.
  • Subadditivity: The truncated function f_x is subadditive, proved by separating cases where at least one of f(A), f(B) reaches x from the case where both are below x.When one value reaches x, the sum of truncated values is at least x; otherwise subadditivity of f and f_x(S)≤f(S) complete the argument.
  • Auxiliary lemmas: The proofs of Lemmas 4.5 and 4.6 apply diminishing returns incrementally along ordered item sequences, then sum and normalize the resulting inequalities.The constructions use nested sets T_j and derive aggregate bounds through summation and division by the relevant set-size terms.

G Omitted Proofs of Section 5

The omitted proofs for Section 5 use XOS representations and the maxmin-share partition to establish bounds for selected bundles. They combine maximizing additive components with partition refinement arguments.

  • XOS bounds: An XOS representation selects an additive function maximizing a set and uses its bundle values to derive a lower bound for the complement.If the selected bundles have additive values α_i summing to β, the proof obtains f(S\S_i)≥β−α_i.
  • MMS partition refinement: The MMS proof starts from an n-way partition whose every part has value at least 1, then refines each part into two disjoint subsets valued at least 2/5.For a part T, the proof chooses an additive function maximizing its value and orders prefixes of T for the refinement argument.
Loading 1704.00222v3…