PaperlayerView exact revision on arXiv

Source-linked AI summary

Finding Fair and Efficient Allocations

Siddharth Barman, Sanath Kumar Krishnamurthy, Rohit Vaish

arXiv:1707.04731v2cs.GT

TL;DR

The paper addresses the challenge of finding allocations of indivisible goods that are both EF1 and efficient despite the NP-hardness of maximizing NSW. It develops a market-based combinatorial algorithm and proves EF1 with PO, EF1 with fPO existence, and a polynomial-time 1.45-approximation for NSW.

  • Problem

    For additive valuations, maximizing NSW yields EF1 and PO, but NSW maximization over integral allocations is NP-hard, leaving efficient computation unresolved.

  • Method

    The algorithm starts from a Pareto efficient allocation, exchanges goods while maintaining an equilibrium market with prices, and stops at price EF1.

  • Results

    The work gives a pseudopolynomial algorithm for EF1 and PO, establishes existence of EF1 and fPO allocations, and provides a polynomial-time 1.45-approximation for NSW.

  • Takeaways & Limitations

    Fair and efficient allocations for additive valuations can be computed in pseudopolynomial time, and bounded valuations yield polynomial-time computation.

  • Takeaways & Limitations

    The algorithm's running-time analysis is intricate and relies on analyzing agents' spending across different phases.

Abstract

from arXiv · show

We study the problem of allocating a set of indivisible goods among a set of agents in a fair and efficient manner. An allocation is said to be fair if it is envy-free up to one good (EF1), which means that each agent prefers its own bundle over the bundle of any other agent up to the removal of one good. In addition, an allocation is deemed efficient if it satisfies Pareto optimality (PO). While each of these well-studied properties is easy to achieve separately, achieving them together is far from obvious. Recently, Caragiannis et al. (2016) established the surprising result that when agents have additive valuations for the goods, there always exists an allocation that simultaneously satisfies these two seemingly incompatible properties. Specifically, they showed that an allocation that maximizes the Nash social welfare (NSW) objective is both EF1 and PO. However, the problem of maximizing NSW is NP-hard. As a result, this approach does not provide an efficient algorithm for finding a fair and efficient allocation. In this paper, we bypass this barrier, and develop a pseudopolynomial time algorithm for finding allocations that are EF1 and PO; in particular, when the valuations are bounded, our algorithm finds such an allocation in polynomial time. Furthermore, we establish a stronger existence result compared to Caragiannis et al. (2016): For additive valuations, there always exists an allocation that is EF1 and fractionally PO. Another contribution of our work is to show that our algorithm provides a polynomial-time 1.45-approximation to the NSW objective. This improves upon the best known approximation ratio for this problem (namely, the 2-approximation algorithm of Cole et al. (2017)). Unlike many of the existing approaches, our algorithm is completely combinatorial.

1 Introduction

For indivisible goods with additive valuations, the paper develops an efficient route to allocations that are both EF1 and Pareto efficient, while also improving Nash social welfare approximation guarantees. It further establishes EF1 together with fractional Pareto efficiency as an existence result.

  • Main contributions: A pseudopolynomial-time algorithm finds an EF1 and Pareto efficient allocation for additive valuations, with polynomial time when valuations are bounded.The algorithm’s general running time is polynomial in the number of goods, agents, and the maximum singleton valuation.
  • Fairness and efficiency: EF1 relaxes envy-freeness by allowing removal of the most valuable good from another agent’s bundle, and an EF1 allocation always exists.EF1 is useful because exact envy-free allocations are not guaranteed for indivisible goods.
  • Fairness and efficiency: Maximizing Nash social welfare yields EF1 and Pareto efficiency for additive valuations, but integral NSW maximization is NP-hard.This leaves open the algorithmic problem of finding a fair and efficient allocation efficiently.
  • Main contributions: 1.45 is the algorithm’s polynomial-time approximation factor for NSW, improving the previous best-known factor of 2 while returning a fair and efficient allocation.Approximating NSW alone does not guarantee EF1 or Pareto efficiency.
  • Main contributions: An EF1 and fractionally Pareto efficient allocation always exists for additive valuations, strengthening the earlier EF1-and-PO existence result.Fractional Pareto efficiency rules out Pareto domination even by fractional allocations.
  • Algorithmic approach: The approach maintains an integral Fisher-market equilibrium while exchanging goods and stops when price envy-freeness up to one good is achieved.Balanced spending under market prices implies EF1 for the corresponding allocation, while equilibrium ensures Pareto efficiency.
  • Algorithmic approach: Unlike relax-and-round methods, the algorithm remains integral throughout and introduces price envy-freeness up to one good as a balanced-spending criterion.The paper identifies this price-based notion as novel and potentially useful in other fair and efficient allocation settings.

2 Preliminaries

The preliminaries formalize additive fair-division instances, integral and fractional allocations, EF1 and approximate EF1, Nash social welfare, and integral, approximate, and fractional Pareto efficiency.

  • Fair division model: A fair-division instance consists of n agents, m goods, and additive nonnegative integral valuation functions over goods.For additive valuations, an agent’s value for a bundle is the sum of its singleton-good values.
  • Allocations: An integral allocation partitions all goods into agent bundles, whereas a fractional allocation may assign portions of goods subject to each good receiving at most one total unit.The paper uses “allocation” for the integral case and explicitly says fractional allocation otherwise.
  • Fairness notions: An allocation is EF1 when, for every ordered pair of agents, removing some good from the other agent’s bundle eliminates the first agent’s envy.The approximate variant permits a factor of 1 + ε on the envious agent’s own value.
  • Fairness notions: Nash social welfare is optimized by selecting an allocation x* from the integral allocations that maximizes NSW(x).The supplied definition passage states the optimizer notation but does not include the objective’s expanded formula.
  • Efficiency notions: Pareto efficiency means that no allocation can weakly improve every agent’s value while strictly improving at least one agent’s value.The paper also defines ε-Pareto efficiency by requiring improvements of at least a factor of 1 + ε.
  • Efficiency notions: Fractional Pareto efficiency rules out Pareto domination by any fractional allocation and therefore implies ordinary Pareto efficiency.The converse need not hold.

3 Main Results

The paper presents three main results: algorithms for EF1 and PO allocations, an existence result for EF1 and fPO allocations, and a 1.45-approximation algorithm for Nash social welfare.

  • Theorem 1: An EF1 and PO allocation can be found in O(poly(m, n, vmax)) time for additive valuations.Here, vmax = max_i,j v_i,j.
  • Theorem 1: Polynomially bounded valuations make EF1 and PO allocation computable in polynomial time.This includes the case where all valuations are bounded by a constant, despite NSW maximization remaining APX-hard for constant valuations.
  • Theorem 1: Relaxing both guarantees to ε-EF1 and ε-PO allows the algorithm to run in polynomial time.The stated runtime depends polynomially on the instance parameters and valuation bound.
  • Theorem 2: For additive valuations, an EF1 and fractionally Pareto efficient allocation always exists.This strengthens the existence guarantee beyond EF1 and PO allocation results by establishing fractional Pareto efficiency.
  • Theorem 3: A polynomial-time 1.45-approximation algorithm exists for Nash social welfare maximization.The proof uses a connection between approximate envy-freeness and Nash social welfare: any ε-EF1 allocation with identical additive valuations gives an e(1+ε)/e-approximation.

4 Our Algorithm

The algorithm uses Fisher-market prices, MBB allocations, and alternating paths to transform an integral allocation into one that is approximately EF1 and fractionally Pareto efficient.

  • Market preliminaries: A Fisher market models buyers with budgets who purchase goods maximizing utility per unit of money.An equilibrium requires market clearing, budget exhaustion, and allocation only among maximum-bang-per-buck goods.
  • Market preliminaries: An equilibrium allocation is fractionally Pareto efficient by the first welfare theorem.
  • Price fairness: Price envy-freeness up to one good requires each buyer’s spending to cover another buyer’s spending after removing one good, up to a factor of 1 + ε.
  • Algorithmic framework: The algorithm’s combinatorial structure uses MBB and allocation edges to form alternating paths and hierarchies.These hierarchies organize agents by alternating-path distance from a source agent.
  • Algorithmic framework: The algorithm maintains an integral allocation whose bundles consist of MBB goods and establishes approximate price-EF1.Lemma 2 converts ε-approximate price-EF1 into ε-approximate EF1 for the associated fair-division instance.
  • Guarantees: The resulting allocation is fractionally Pareto efficient while satisfying the algorithm’s approximate EF1 guarantee.

5 Proof of Theorem 1

The proof rounds valuations to powers of 1 + ε, analyzes a three-phase combinatorial algorithm, and transfers its approximate guarantees back to the original instance.

  • Algorithm: The algorithm initializes a welfare-maximizing allocation, assigns prices from the owning agents’ valuations, and then executes hierarchy-based exchanges and price rises.Its phases initialize the market, remove price-envy within a hierarchy, and raise prices.
  • Power-of-(1 + ε) instances: Power-of-(1 + ε) valuations restrict each nonzero value to an integer power of 1 + ε, enabling the running-time analysis.
  • Running time: The execution consists of swaps, least-spender changes, price rises, and termination steps, each running in polynomial time.
  • Correctness: 3ε-EF1 and fPO are guaranteed for power-of-(1 + ε) instances.The proof derives fPO from maintaining MBB allocations and EF1 from the price-EF1 condition.
  • Theorem 1: An EF1 and PO allocation can be found in O(poly(m, n, vmax)) time for additive valuations.Thus the algorithm is pseudopolynomial generally and polynomial when valuations are bounded.
  • Rounding: An ε-rounded instance is formed by rounding valuations upward to the nearest integer power of 1 + ε.For suitable ε, the resulting allocation’s approximate EF1 and fPO guarantees transfer to EF1 and PO for the original instance.

6 Existence Result: Proof of Theorem 2

The existence proof takes limits of allocations from increasingly fine rounded instances, preserving EF1 while obtaining an allocation that is fractionally Pareto efficient for the original instance.

  • Theorem 2: For additive valuations, an allocation that is both EF1 and fractionally Pareto efficient always exists.
  • Rounded sequence: The proof sets εz = 1/(14zm^3vmax^4) and applies the algorithm to each εz-rounded instance.Each resulting allocation xz is εz-EF1 and fPO for its rounded instance.
  • EF1 preservation: Because εz is sufficiently small, every xz is EF1 for the original instance.
  • Limit argument: A subsequence has a common integral allocation and convergent bounded price vectors, yielding a limit allocation x and price vector p*.Finitely many integral allocations ensure repetition, while bounded prices enable a convergent subsequence.
  • Limit argument: The limiting allocation satisfies the MBB condition for the original valuations and limit prices.The valuation sequence converges to the original valuations through the rounding bounds.
  • Conclusion: The first welfare theorem then establishes that the limiting allocation is fPO for the original instance.

7 Nash Social Welfare Approximation: Proof of Theorem 3

The section proves that the algorithm yields a polynomial-time 1.45-approximation for Nash social welfare by relating EF1 allocations to NSW through partially-fractional allocations. The analysis establishes the guarantee first under identical valuations and then transfers it to the general additive-valuation setting.

  • Approximation guarantee: Under identical additive valuations, any ε-EF1 allocation provides an e(1+ε)/e-approximation to Nash social welfare.This lemma supplies the central connection between fairness and NSW used in the theorem.
  • Proof strategy: The proof optimizes NSW over partially-fractional allocations, where selected goods remain integral and all remaining goods may be fractionally allocated.The partially-fractional optimum upper-bounds the integral optimum, allowing the analysis to compare the EF1 allocation against NSW(x*) through an intermediate allocation ω.
  • Proof strategy: A structural lemma permits an NSW-maximizing partially-fractional allocation in which each agent receives at most one selected integral good.Agents valued above the minimum receive exactly one integral good and no fractional good.
  • Proof strategy: The proof constructs x′ by transferring goods from larger-valued bundles to smaller-valued bundles without increasing NSW, then bounds NSW(x′) and NSW(ω).The construction preserves the required integral assignments for agents in H and organizes the comparison through parameters α, ℓ, n, h, and t.
  • Approximation guarantee: 1.45-approximation for NSW is achieved in polynomial time for additive valuations.The proof establishes the bound under a scaled valuation profile and transfers it to the original instance.

8 Concluding Remarks

The paper presents an integral-Fisher-market framework with approximate price envy-freeness for computing fair and efficient allocations. It also identifies unresolved complexity questions while highlighting the algorithm’s NSW approximation guarantee.

  • Concluding remarks: The framework yields a pseudopolynomial algorithm for an EF1 and PO allocation.It is based on integral Fisher markets and an approximate price envy-freeness condition.
  • Concluding remarks: The algorithm provides a polynomial-time 1.45-approximation for Nash social welfare.This matches the stated approximation theorem and is part of the paper’s main contributions.
  • Concluding remarks: Whether EF1 and PO can be found in strongly polynomial time remains open.The conclusion explicitly leaves this complexity question unresolved.

A.2 Proof of Lemma 4

This section bounds the running time of Alg on power-of-(1 + ε) instances by limiting the number of Phase 2 events and Phase 3 price rises. The argument uses monotonic spending and discrete valuation-price structure.

  • Running-time bound: Alg terminates in time O(...) on power-of-(1 + ε) instances.The supplied lemma states the running-time bound for this restricted valuation class, with the expression truncated in the passage.
  • Progress argument: When an agent again becomes the least spender, either its allocation gains a good or its spending grows by a factor of (1 + ε).This progress argument bounds repeated identity changes before a price-rise.
  • Phase 2: Phase 2 lasts at most poly(n, m, 1/ε) · ln(mvmax) consecutive time steps before a Phase 3 step.This follows from polynomial bounds on consecutive swaps and changes in the least spender’s identity.
  • Phase 3: Alg performs at most n log(1+ε) mvmax Phase 3 steps.Price rises increase spending in discrete powers of (1 + ε), while the least spender’s spending cannot decrease.
  • Phase 3: Each Phase 3 step raises prices for goods owned by agents in the hierarchy by a factor α.The factor is α = min{α1, α2, α3}; termination occurs when α = α2.

A.2.1 Proof of Lemma 12

The proof of Lemma 12 tracks 3ε-violators across price rises and swaps. It shows that violators cannot be newly created by price rises and that their spending is controlled across successive events.

  • Violator dynamics: The set of 3ε-violators cannot increase between price-rise steps.For price-rise times t < t′, the proof establishes Et′ ⊆ Et.
  • Violator dynamics: A price rise cannot turn an agent into a new 3ε-violator.The argument considers whether the agent lies inside or outside the hierarchy and uses uniform price changes outside the hierarchy.
  • Price-rise condition: At the beginning of every price-rise step, no agent in the hierarchy is a 3ε-violator.Such an agent would instead trigger a Phase 2 swap because it would be an ε-path violator.
  • Spending bound: For any violator remaining at a later price-rise, its spending is no greater than at the earlier price-rise.This follows from the shrinking violator set and the fact that relevant goods are not repriced between the two events.
  • Spending bound: The least spender’s spending is bounded by the spending of every 3ε-violator at each price-rise step.The proof combines the violator definition with the preceding monotonicity result to establish Lemma 12.

A.2.2 Proof of Lemma 13

Lemma 13 bounds the number of consecutive swap operations by using a potential function that decreases after every swap. The proof tracks hierarchy levels and critical goods to establish this decrease.

  • Critical goods: Critical goods are defined through alternating paths from the least spender to agents in the hierarchy.The set G_h,t is non-empty exactly for agents in the corresponding hierarchy level.
  • Swap bound: poly(n, m) consecutive swaps are possible before the least spender changes or Phase 3 begins.Lemma 13 derives this bound from a potential-function argument.
  • Potential function: The potential combines hierarchy levels and the number of critical goods as m(n − level(h, t)) + |G_h,t|.The function is non-negative and bounded by poly(n, m).
  • Potential decrease: After a swap, the contribution of every agent does not increase, while the contribution of hℓ strictly decreases.For hℓ, either its level rises or its critical-good set shrinks, forcing a decrease of at least 1.

A.3 Proof of Lemma 5

The proof of Lemma 5 bounds price growth through successive price rises and least-spender spending. With sufficiently small ε, an fPO allocation for the rounded instance is PO for the original instance.

  • Price bounds: The resulting product of price-rise factors bounds final good prices by a polynomial expression in m and v_max.The proof combines bounds on least-spender spending and the final price rise to control p_j.
  • Price-rise analysis: The algorithm’s price-rise analysis relates each successive least-spender level through inequalities of the form s(t₂) ≥ α_t1 s(t₁).The least spender’s spending is non-decreasing, and multiplicative price jumps are tracked across time steps.
  • Time-step structure: The analysis partitions time steps by least spenders experiencing price rises and uses marked-agent updates to prove the required spending relations.Marked agents accumulate across Phase 3 steps and never become unmarked.
  • Rounding transfer: ε ≤ 1/(6m^3v_max^4) ensures that an fPO allocation for the ε-rounded instance is PO for the original instance.This is the stated condition and conclusion of Lemma 5.
  • Corner cases: After O(n^2) steps, every agent has strictly positive spending in instances satisfying power-of-(1 + ε) and Hall’s conditions.This is the stated conclusion of Lemma 21.

B.3 Second Welfare Theorem for Fisher Markets

The paper establishes a second welfare theorem for Fisher markets: every fPO allocation can be supported as a market equilibrium with suitable prices and endowments. The proof uses linear programming duality and complementary slackness.

  • Theorem: Every fPO allocation admits a price vector and endowment vector making it a Fisher market equilibrium.This is the statement of Theorem 4.
  • Primal program: The proof formulates a linear program whose feasible allocations provide each buyer at least the utilities induced by the given fPO allocation.Fractional Pareto efficiency makes the given allocation primal-optimal.
  • Dual interpretation: Dual variables are interpreted as good prices and buyer-specific terms, with constraints linking prices, utilities, and valuations.The dual constraints are p_j − d_i v_i,j ≥ v_i,j, with nonnegative d_i and p_j.
  • Equilibrium conditions: Complementary slackness verifies market clearing, budget exhaustion, and maximum-bang-per-buck allocation conditions.The endowment is chosen from the allocation’s priced bundle values.
  • Example: Utility maximization under budgets does not by itself imply that every allocated good is in the buyer’s MBB set.The example explicitly exhibits utility maximization without the maximum-bang-per-buck condition.

B.5 An Instance where a 1.44-approximate NSW and fPO Allocation Does Not Exist

The section constructs an instance showing that near-optimal NSW and fractional Pareto efficiency cannot always coexist. The obstruction follows from structural restrictions imposed on integral fPO allocations.

  • Construction: The constructed instance has three agents, five goods, two high-valued goods, and three signature goods, with high-good value c.Each signature good is valued at 1 by its corresponding agent and at 1/3 by others.
  • fPO structure: Every integral fPO allocation gives some agent a bundle contained in that agent’s single signature good.This follows from the shortage of high-valued goods and the market-equilibrium characterization of fPO allocations.
  • Nash optimum: The Nash-optimal allocation assigns both high-valued goods to two agents and all signature goods to the third agent.This allocation is identified as Nash optimal in the example.
  • Approximation gap: 1.44 is the asymptotic NSW ratio separating the constructed fPO allocation from the Nash-optimal allocation.The construction yields a ratio at least 1.44 for large c.
  • PO versus fPO: The Nash-optimal allocation is PO but not fPO, because no agent receives only a subset of its signature goods.The section uses this distinction to separate Pareto efficiency from fractional Pareto efficiency.
  • Fairness limitation: EF1 alone can permit extreme inefficiency: an allocation may be EF1 while every agent receives value zero.The cyclic allocation in the binary instance has this property.

B.7 Every Rounding of Spending Restricted Outcome Violates EF1

The section gives a fair-division instance in which every rounding of the spending restricted equilibrium violates EF1, and shows that approximate NSW alone need not ensure fairness or efficiency.

  • Every rounding of the spending restricted equilibrium in the constructed instance violates EF1.The example also serves as a counterexample for rounding CEEI outcomes.
  • The instance uses n = 5 agents and m = 7 goods with specified valuation functions.
  • In any rounding, some agents receive bundles whose valuations make one agent envy another even after removing any single good.
  • A 2-approximation to Nash social welfare can nevertheless fail both EF1 and Pareto optimality.The displayed construction has NSW(y) = 2n−1, while a Nash-optimal allocation x Pareto dominates y.
Loading 1707.04731v2…