PaperlayerView exact revision on arXiv

Source-linked AI summary

Fair Division with Binary Valuations: One Rule to Rule Them All

Daniel Halpern, Ariel D. Procaccia, Alexandros Psomas, Nisarg Shah

arXiv:2007.06073v2cs.GT

TL;DR

With additive valuations, Pareto optimality and strategyproofness leave only unfair serial dictatorship, raising the question of whether binary additive valuations permit all three goals. The paper studies MNW rules in that domain and reports deterministic and randomized guarantees, while leaving ex post group strategyproofness of the randomized rule open.

  • Problem

    With additive valuations, Pareto optimality and strategyproofness leave only unfair serial dictatorship, prompting the question of whether binary additive valuations admit efficient, fair, and truthful rules.

    Source: §1 · pp. 1–2

  • Method

    The paper studies MNWtie under binary additive valuations and implements fractional MNW allocations as distributions over deterministic MNW allocations.

    Source: §2 · p. 3, §4 · p. 14

  • Results

    MNWtie is EF1, Pareto optimal, group strategyproof, and polynomial-time computable; its randomized variant is ex ante EF, PO, and GSP, and ex post EF1.

    Source: §3 · p. 6, §5 · p. 16

  • Takeaways & Limitations

    The authors conclude that, modulo minor caveats, these are the strongest results one could hope for under binary additive valuations.

    Source: §5 · p. 16

    Whether the randomized rule’s ex ante group strategyproofness can be strengthened to ex post group strategyproofness remains open.

    Source: §5 · p. 16

Abstract

from arXiv · show

We study fair allocation of indivisible goods among agents. Prior research focuses on additive agent preferences, which leads to an impossibility when seeking truthfulness, fairness, and efficiency. We show that when agents have binary additive preferences, a compelling rule -- maximum Nash welfare (MNW) -- provides all three guarantees. Specifically, we show that deterministic MNW with lexicographic tie-breaking is group strategyproof in addition to being envy-free up to one good and Pareto optimal. We also prove that fractional MNW -- known to be group strategyproof, envy-free, and Pareto optimal -- can be implemented as a distribution over deterministic MNW allocations, which are envy-free up to one good. Our work establishes maximum Nash welfare as the ultimate allocation rule in the realm of binary additive preferences.

1 Introduction

Additive valuations make reporting simple, but Pareto optimality and strategyproofness conflict; binary additive valuations motivate the question of whether efficiency, fairness, and truthfulness can coexist. The paper answers with deterministic and randomized MNW rules, while situating its results alongside related deterministic and fractional allocation work.

1 Introduction

  • Under additive valuations, Pareto optimality and strategyproofness leave only unfair serial dictatorship, motivating the question of whether binary additive valuations can reconcile efficiency, fairness, and truthfulness.Binary values reduce expressiveness but make elicitation simple; agents report each good’s value separately.Source: §1 · pp. 1–2

1.1 Our Contribution

  • Under binary additive valuations, MNWtie is Pareto optimal, EF1, group strategyproof, and polynomial-time computable.This strengthens MNW’s established EF1 and Pareto-optimal guarantees with group strategyproofness for this valuation domain.Source: §1 · p. 1, §1.1 · p. 2
  • Randomizing over MNW allocations achieves ex ante envy-freeness, Pareto optimality, and group strategyproofness alongside ex post EF1, in polynomial time.The authors frame randomization as avoiding the mild unfairness inherent in deterministic allocations while retaining the other guarantees.Source: §1.1 · p. 2

1.2 Related Work

  • Babaioff et al.’s prioritized egalitarian mechanism is identical to MNWtie; their results complement this work’s group-strategyproofness guarantee with EFX and Lorenz-dominance [5].Together with EFX established by Amanatidis et al. [3], the authors say the results establish MNWtie’s EFX, PO, Lorenz-dominance, group-strategyproofness, and polynomial-time computability.Source: §1.2 · p. 2
  • Ortega’s fractional rule has ex ante envy-freeness, Pareto optimality, and group strategyproofness, but does not provide ex post EF1 for the allocation.The authors focus on implementing fractional allocations as distributions over integral allocations with ex post EF1; Ortega uses a weaker strategyproofness notion in a setting with multiple copies of each good.Source: §1.2 · pp. 2–3
  • Under binary additive valuations, the sets of MNW and leximin allocations are identical; the polynomial-time deterministic MNWtie algorithm starts from an MNW allocation found using either or [6].Benabbou et al. [7] extend the equivalence to a more general valuation class and show an MNW allocation can be computed efficiently there.Source: §1.2 · p. 3

2 Preliminaries

The preliminaries define binary additive valuations and the allocation model, then formalize fairness and efficiency criteria. In this domain, EF1 coincides with EFX, and Pareto optimality has a simple valued-good characterization.

2 Preliminaries

  • Binary additive valuations assign each agent value 0 or 1 per good, so bundle value is the count of liked goods.An agent likes a good when its value is 1; the valuation profile collects all agents’ valuation functions.Source: §2 · p. 3
  • An allocation partitions goods among agents; it is complete if it allocates every valued good and minimally complete if it allocates no non-valued goods.A good is valued when at least one agent likes it; non-valued goods are liked by no agent.Source: §2 · p. 3
  • EF1 permits envy to be removed by deleting at most one good from the envied bundle, and under binary additive valuations it coincides with EFX.Pareto optimality means no feasible allocation can make everyone at least as well off and someone strictly better off; here it is equivalent to allocating each valued good to an agent who likes it.Source: §2 · pp. 3–4

3 Deterministic Setting

This section studies deterministic MNW allocation under binary additive valuations, including its relationship to leximin and the EF1, Pareto-optimality, and group-strategyproofness properties of the MNWtie rule. It also presents a polynomial-time algorithm that uses paths in an allocation graph to find an MNW allocation with the lexicographically greatest utility vector.

MNW and leximin

  • Under binary additive valuations, the sets of MNW and leximin allocations coincide.All leximin allocations share the same utility profile, and any allocation with that profile is leximin; the section establishes the corresponding equivalence with MNW.Source: §3 · p. 5

The deterministic rule

  • MNWtie selects an MNW allocation with the lexicographically greatest utility vector and requires it to be minimally complete.It is well-defined because non-valued goods can be removed without changing the utility vector.Source: §3 · p. 5
  • MNWtie is EF1, Pareto optimal, group strategyproof, and polynomial-time computable under binary additive valuations.The EF1 and Pareto guarantees also hold for MNW allocations under general additive valuations.Source: §3 · p. 6

Characterizing MNW allocations

  • A Pareto optimal allocation is MNW exactly when its allocation graph has no path from an agent to one whose utility exceeds theirs by more than one.The path criterion follows by comparing the Nash welfare change from passing goods back along a path.Source: §3 · p. 6

Group strategyproofness

  • The group-strategyproofness proof uses reachability in the allocation graph and lexicographic tie-breaking to rule out a coalition’s profitable deviation.For the key contradiction, passing goods back along a path yields an MNW allocation with the same utility profile but a lexicographically better utility vector.Source: §3 · pp. 6, 8

3 Deterministic Setting

  • If an MNW allocation’s utility vector differs from the lexicographically greatest one, its first differing agent i has a path to some later agent j with utility one higher.Passing goods back along this path raises i’s utility by one, preserves MNW optimality, and produces a utility vector with a longer matching prefix.Source: §3 · pp. 8–9
  • Starting from any MNW allocation, the algorithm repeatedly passes goods back along a path from the smallest eligible agent i to some j > i, and terminates within n iterations.It returns an MNW allocation with the lexicographically greatest utility vector; constructing the graph, searching for a path, and applying the transfer are all polynomial-time operations.Source: §3 · pp. 9–10
  • The algorithm processes agents in order, preserving the already-matched utility prefix whether it applies a path transfer or leaves the allocation unchanged.The correctness argument uses induction on the agent index; a transfer along the identified path does not change utilities for agents with smaller indices.Source: §3 · p. 10

4 Randomized Setting

This section examines fractional maximum Nash welfare for binary additive valuations, including its equivalence to fractional leximin and its ex ante fairness, Pareto optimality, and group strategyproofness. It also covers polynomial-time implementation as distributions over deterministic MNW allocations with an ex post EF1 guarantee.

4 Randomized Setting

  • The result circumvents the impossibility shown by Freeman et al. [23] for combining ex ante envy-freeness, ex post EF1, and ex ante Pareto optimality under general additive valuations, and adds group strategyproofness.Freeman et al. [23] do not consider group strategyproofness.Source: §4 · p. 10
  • Under binary additive valuations, fractional leximin and fractional MNW allocations coincide and have identical utility vectors.This identical-vector guarantee is stronger than the identical utility-profile guarantee for deterministic allocations.Source: §4 · pp. 11–12
  • Every fractional MNW allocation is ex ante envy-free and Pareto optimal, while the fractional MNW rule is ex ante group strategyproof.The rule returns a minimally complete fractional MNW allocation.Source: §4 · p. 13
  • A polynomial-time bihierarchy implementation expresses any fractional MNW allocation as a distribution over deterministic MNW allocations, which are EF1.The support allocations preserve the goods assigned under the fractional allocation and round each agent’s utility to its floor or ceiling.Source: §4 · pp. 13–14
  • For binary additive valuations, fractional MNW is ex ante envy-free, ex ante Pareto optimal, ex ante group strategyproof, ex post envy-free up to one good, and polynomial-time computable.The rule is amended to implement a minimally complete fractional MNW allocation.Source: §4 · p. 15

5 Discussion

Under binary additive valuations, deterministic and randomized variants of MNW provide combinations of fairness, efficiency, and strategyproofness. The discussion also identifies limits on allocating every good and an open question about ex-post group strategyproofness.

5 Discussion

  • The deterministic MNW variant is EF1, PO, and GSP, while its randomized variant is ex-ante EF, PO, and GSP and ex-post EF1; all rules are polynomial-time computable.The all-goods guarantee is not included in these stated results.Source: §5 · p. 16
  • No variant of MNW can achieve EF1, PO, and GSP while allocating all goods under binary additive valuations.The discussion frames this as a contrast with an impossibility for general additive valuations, which applies only to rules allocating all goods.Source: §5 · p. 16
  • Whether the randomized rule can achieve ex-post GSP by using a distribution over deterministic GSP rules remains open.Source: §5 · p. 16

A Example Illustrating MNWtie

The examples illustrate MNWtie using valuation profiles represented as agent-by-good matrices. One example has a unique returned allocation, while another allows several allocations.

A Example Illustrating MNWtie

B Allocating Non-valued Goods

The appendix shows that MNW cannot always select a strategyproof allocation while also allocating every good, even in a two-agent, six-good setting. A separate computational check finds a full-allocation EF1, PO, and SP rule for that setting, while the corresponding question for seven or more goods remains open.

B Allocating Non-valued Goods

  • No deterministic rule can always select an MNW allocation, allocate all goods, and be SP for two agents and six goods.Source: B Allocating Non-valued Goods · p. 19
  • In the proof, an agent can misreport to raise their utility from 2 to at least 3, contradicting strategyproofness for the proposed rule.The misreport makes the agent value goods g1, g3, and g4, whereas under the truthful profile their utility is exactly 2.Source: B Allocating Non-valued Goods · p. 19
  • An ILP check found a full-allocation rule that is EF1, PO, and SP for every binary valuation profile with two agents and six goods; the corresponding existence question is open for two agents and seven or more goods.The program did not terminate in reasonable time for two agents and seven goods.Source: B Allocating Non-valued Goods · p. 19

Related papers

Loading 2007.06073v2…