PaperlayerView exact revision on arXiv

Source-linked AI summary

Simultaneous Envy and Equitability Guarantees

Hadi Hosseini, Shraddha Pathak, Lirong Xia, Chengkai Zhang

arXiv:2608.26410v1cs.GTcs.AIecon.TH

TL;DR

The paper asks whether envy-freeness and equitability can be jointly guaranteed for indivisible goods and chores, including across ex-ante and ex-post settings. It studies relaxed guarantees under additive valuations and finds sharp differences by setting and valuation structure. EF1+EQ1 can fail, while structured binary instances yield strong positive results, especially for chores.

  • Problem

    Existing work often studies fairness notions in isolation, leaving open whether fundamentally different notions such as envy-freeness and equitability can coexist deterministically and across ex-ante and ex-post worlds.

  • Method

    The paper analyzes EF1, EFX, EQ1, and EQX under additive goods-only and chores-only valuations, studying existence, computational complexity, structured binary cases, and randomized cross-notion guarantees.

  • Results

    EF1+EQ1 may fail even for normalized bivalued valuations; normalized binary goods admit EF1+EQ1 for up to seven agents, while binary chores always admit EFX+EQX.

  • Takeaways & Limitations

    Compatibility depends sharply on the goods-versus-chores setting and valuation structure, and the paper initiates cross-notion best-of-both-worlds fairness.

  • Takeaways & Limitations

    For common bivalued domains with q > 0, EF1+EQ1 existence remains open, and a normalized restricted-additive three-agent laminar goods instance has no EF1+EQ1 allocation.

Abstract

from arXiv · show

Recent work in fair division has focused on either simultaneously satisfying closely related fairness notions or achieving a single notion across the ex-ante and ex-post worlds. We study the compatibility of two fundamentally different fairness notions: envy-freeness and equitability. For indivisible goods-only and chores-only settings, we study the existence and complexity of simultaneously satisfying their relaxations, revealing sharp contrasts between the two settings. We show that EF1+EQ1 may fail to exist even for normalized, additive valuations. Our main algorithmic result computes an EF1+EQ1 allocation for normalized binary goods with at most seven agents. In sharp contrast, binary chores admit the stronger EFX+EQX guarantee for any number of agents, even without normalization. We further initiate the study of cross-notion ex-ante--ex-post guarantees, asking whether randomized allocations can provide ex-ante guarantees for one notion while preserving ex-post guarantees for another.

1 Introduction

The paper studies whether envy-freeness and equitability can coexist for indivisible goods and chores, deterministically and across ex-ante and ex-post settings. It establishes sharp contrasts between settings and valuation structures.

  • Motivation: Most prior work studies fairness notions separately, while this paper asks whether fundamentally different notions can be guaranteed simultaneously.The motivation includes both deterministic allocations and cross-notion ex-ante–ex-post guarantees.
  • Fairness notions: Envy-freeness compares each agent’s bundle with others using that agent’s valuation, whereas equitability requires equal subjective values across agents.These notions therefore differ in their invariance properties: envy-freeness is individually scale-invariant, but equitability is not.
  • Deterministic guarantees: EF1+EQ1 may fail to exist for n ≥3 even under normalized bivalued valuations, and deciding existence is NP-HARD for unnormalized two-agent instances.Under normalization, two-agent EF1+EQ1 allocations nevertheless always exist and are computable in polynomial time for goods and chores.
  • Binary valuations: Binary goods admit EF1+EQ1 algorithms for up to seven agents and, more generally, for any number of agents with laminar approval structures.The paper identifies binary structure as a route to compatibility, while a stronger result holds for binary chores.
  • Cross-setting and probabilistic guarantees: Binary chores always admit EFX+EQX, whereas the stronger guarantee may fail for goods; randomized allocations provide ex-ante EF+EQ with differing ex-post guarantees.For normalized binary instances, goods obtain ex-post EQ1, while chores obtain ex-post EF1+EQ1; the latter extends beyond normalization to restricted-additive chores.

2 Preliminaries

The preliminaries formalize additive allocations, goods and chores instances, valuation restrictions, deterministic fairness relaxations, and randomized ex-ante and ex-post guarantees.

  • Instance types: Goods instances have nonnegative item values, whereas chores instances have non-positive item values.For chores, the negative of utility is interpreted as disutility or cost.
  • Valuation classes: Normalized valuations give every agent the same total value for all items, while binary valuations use {0,1} for goods and {0,−1} for chores.Bivalued and restricted-additive valuations generalize binary valuations.
  • Allocations: An allocation partitions the item set among agents, with each agent’s realized utility equal to the additive value of its assigned bundle.A randomized allocation is a probability distribution over deterministic allocations.
  • Equitability: EQ requires all agents to receive equal subjective value, with EQ1 and EQX allowing removal of some or every appropriate item.The goods and chores definitions use the corresponding bundle-side removal conditions.
  • Envy-freeness: EF requires each agent to value its own bundle at least as highly as every other bundle under its own valuation.EF1 and EFX relax this by permitting removal of some or every appropriate item, respectively.
  • Randomized fairness: Ex-ante equitability equalizes expected utilities and ex-ante envy-freeness prevents expected envy across the lottery’s deterministic allocations.An ex-post guarantee holds when every allocation in the lottery’s support satisfies that guarantee.

3 Deterministic Guarantees

The paper identifies sharp barriers and structural opportunities for simultaneously achieving envy and equitability guarantees. EF1+EQ1 may fail for general normalized valuations, while structured binary settings yield polynomial-time guarantees, including EFX+EQX for arbitrary binary chores.

  • Fundamental Barriers: EF1+EQ1 may fail for n ≥3 agents even with normalized bivalued valuations, and deciding existence is NP-HARD for two-agent unnormalized instances.These results establish both an existential barrier and a computational barrier for simultaneous fairness.
  • Fundamental Barriers: A single deviating agent can destroy simultaneous existence even when all other agents have identical valuations.The construction shows that envy-based and equitability-based notions need not remain compatible under near-common valuations.
  • Two-Agent Instances: For normalized two-agent goods, EFX+EQX always exists, whereas normalized two-agent chores may lack EFX+EQX allocations.Thus, even at two agents, the stronger simultaneous guarantee differs between goods and chores.
  • Two-Agent Instances: For normalized two-agent goods and chores, polynomial-time algorithms compute EF1+EQ1 allocations.The goods result is given by Theorem 2, and the chores result by Corollary 1.
  • Binary Goods: For normalized binary goods, a polynomial-time algorithm computes EF1+EQ1 for at most seven agents.The construction relies on exchanges preserving bundle sizes, assigned-good maximality, and the relevant closure property.
  • Binary Goods: With laminar approval sets, normalized binary goods admit EF1+EQ1 allocations for any number of agents, computable in polynomial time.Laminarity also implies that agents’ approval sets are either disjoint or induce identical valuations.
  • Binary Goods: The binary assumption is essential under laminar approval sets: normalized restricted-additive goods may lack EF1+EQ1 allocations for three agents.In the counterexample, one agent’s bundle constraints force another agent to receive at least three approved light goods.
  • Binary Chores: For binary chores, an EFX+EQX allocation always exists and can be computed in polynomial time for any number of agents without normalization.The algorithm partitions universally disliked chores evenly, assigns remaining chores while preserving a value invariant, and ends with equal realized utilities.

4 Ex-ante and Ex-post Guarantees

The paper develops cross-notion ex-ante–ex-post guarantees, finding stronger results for chores than goods and using randomized constructions to combine exact expected fairness with approximate realized fairness.

  • Two-Agent Instances: For two normalized agents, an ex-ante EF+EQ and ex-post EF1 randomized allocation always exists for goods and chores.The construction uses a partition whose two orientations are EF1 and randomizes uniformly between them.
  • Limitations: The realized guarantees are tight in important cases: the goods guarantee cannot generally reach EFX, and chores cannot generally reach EFX or EQX.The stated impossibilities include laminar binary goods and a two-agent binary chores instance.
  • Binary Goods: For normalized binary goods with any number of agents, an ex-ante EF+EQ allocation with ex-post EQ1 always exists.A fractional equal-share allocation is decomposed into integral allocations where each agent receives either the floor or ceiling of her approved utility.
  • Binary Goods: For normalized binary goods with laminar approval sets, the ex-post guarantee strengthens to EF1+EQ1 and remains polynomial-time computable for any number of agents.Laminarity permits balanced blocks within identical or disjoint approval sets.
  • Chores: For restricted-additive chores, an ex-ante EF+EQ and ex-post EF1+EQ1 randomized allocation can be computed in polynomial time without normalization or an agent bound.The guarantee is obtained through RANDCHORE-related constructions and extends beyond binary chores.

5 Concluding Remarks

The paper identifies sharp goods–chores contrasts and opens questions about stronger deterministic guarantees and cross-notion best-of-both-worlds fairness.

  • Concluding Remarks: The work studies simultaneous fairness within deterministic allocations and across ex-ante and ex-post settings, revealing a sharp distinction between goods and chores.Open directions include normalized binary goods with at least eight agents and broader non-personalized bivalued valuations.

AI Usage Disclosure

The authors disclose using AI assistance for one theorem’s extension, editorial suggestions, and drafting, while reporting that they reviewed and verified the mathematical arguments and final text.

  • AI Usage Disclosure: AI assistance extended Theorem 3 from three to seven agents and supported editorial suggestions and drafting.The authors state that all mathematical arguments and the final text were reviewed and verified by them.

A.1 Fundamental Barriers

The section proves that EF1+EQ1 may fail for normalized bivalued valuations with at least three agents in both goods and chores settings.

  • Scope: The barriers persist despite normalization and bivalued valuations, showing that simultaneous existence can fail under highly structured preferences.The constructions normalize every agent’s total value or disutility while using only two valuation levels.
  • Goods: For goods, normalized bivalued instances with n ≥3 can admit no allocation satisfying EF1 and EQ1 simultaneously.The construction uses a distinguished heavy good, many light goods, and a flat agent to force an EF1 contradiction after EQ1 restricts bundle sizes.
  • Goods: In the goods construction, the heavy-good structure forces one agent to receive at most one good, while another receives at least three.Those constraints make the latter agent EF1-envied by the former, contradicting simultaneous fairness.
  • Chores: For chores, normalized bivalued instances with n ≥3 can likewise lack any EF1+EQ1 allocation.The proof treats n ≥4 with flat agents and two agents valuing one chore heavily, then gives a separate three-agent construction.
  • Chores: In the three-agent chores construction, EF1 and EQ1 force agent 1 to receive exactly the heavy chore, after which every feasible split violates EQ1.The argument separately rules out receiving zero, multiple, or a light chore for agent 1.

A.2 Computational Barriers

The paper proves that jointly achieving EF-k and EQ-k can encode PARTITION, yielding NP-hardness even with two agents and fixed k. For k=1, this establishes the computational barrier for EF1+EQ1 in unnormalized instances.

  • Hardness result: For two agents and any fixed k ≥1, deciding whether an allocation satisfying both EF-k and EQ-k exists is NP-HARD.The result applies to additive, possibly unnormalized valuations.
  • Reduction: The reduction creates n ordinary goods and 3k dummy goods, with dummy value D chosen larger than the total ordinary-good value T.The constructed instance is fair exactly when the PARTITION instance has an equal-sum split.
  • Reduction: EF-k and EQ-k force the two agents to receive exactly k and 2k dummies, respectively.Claims 1 and 2 derive these counts from the dummy value D > T and the fairness constraints.
  • Reduction: The same constraints force the ordinary goods to be split into two bundles of equal value T/2, recovering a solution to PARTITION.Claims 3 and 4 establish both inequalities sA ≤ sB and sA ≥ sB.
  • Reduction: Conversely, an equal-sum partition yields an EF-k+EQ-k allocation by assigning k dummies to one agent and 2k to the other.Removing the appropriate k dummies equalizes the relevant comparisons and eliminates envy.

A.3 Limits of Strengthening EF1+EQ1

Even normalized binary goods can lack stronger combinations of envy-freeness and equitability relaxations. A six-agent construction rules out both EF1+EQX and EFX+EQ1, showing that neither guarantee generally strengthens the other.

  • Implication: Thus, under normalization and binary valuations, neither guarantee in EF1+EQ1 can generally be strengthened.The two impossibility results separate the stronger equitability and envy-freeness relaxations.
  • Non-existence: Six agents with normalized binary valuations may admit neither an EF1+EQX allocation nor an EFX+EQ1 allocation.Both non-existence claims use the same instance with nine L-goods and nine R-goods.
  • Construction: The EF1+EQX instance has agent 1 approving exactly L, while agents 2 through 6 approve exactly R.All valuations are binary and normalized, creating disjoint approval patterns.
  • EF1+EQX: Under EQX, integral realized utilities must lie in {µ, µ + 1}, and any agent holding a zero-valued good must have utility exactly µ.These restrictions drive the contradiction for EF1+EQX.
  • EFX+EQ1: The construction admits no EFX+EQ1 allocation.The proof first bounds µ, then derives contradictions in both µ = 0 and µ = 1 cases.

A.4 Two-Agent Instances

For two agents, leximin++ yields EFX+EQX for normalized goods, while normalized chores can lack any EFX+EQX allocation under the paper’s all-item convention. A greedy algorithm also computes EF1+EQ1 for chores.

  • Goods: Every leximin++ allocation of normalized goods for two agents is both EFX and EQX.The proof uses transfer arguments: violating EQX or EFX would improve the leximin++ objective.
  • Goods: Computing leximin++ is generally hard, but it is polynomial-time computable for binary valuations.The existence proof itself applies the leximin++ characterization.
  • Chores: Two normalized agents may have no allocation satisfying EFX and EQX for chores, already with three chores.The counterexample uses chore values 0, −1, and −2 in opposite orders across the agents.
  • Chores: Symmetry reduces the chore counterexample to allocations with |A1| ≤1, and each of the four resulting cases violates EFX or EQX.The cases A1 = ∅, {c1}, {c2}, and {c3} are ruled out explicitly.
  • Chores: Under the weaker convention allowing removal only of negatively valued chores, the three-chore instance does admit an EFX+EQX allocation.The paper identifies A1 = {c1} and A2 = {c2, c3} as an example.
  • Algorithmic guarantee: Algorithm 5 assigns each next chore to the agent with higher current utility and computes a normalized two-agent chores allocation satisfying EF1+EQ1 in polynomial time.Its proof uses a cross-bundle dominance invariant and a final-chore argument.

A.5 Why the Barrier at Seven Agents?

The seven-agent boundary reflects a failure of scattering from some maximum partial allocations, not necessarily a failure of EF1+EQ1 existence. For five agents, a simpler scattering algorithm remains polynomial-time and achieves EF1+EQ1.

  • Eight-agent obstruction: The swap phase rescues the stalled run by moving g1 and g2 into u’s bundle and releasing freely scatterable singleton goods.The residual type is S = {u, v}.
  • Barrier at seven agents: Beyond seven agents, scattering need not succeed from every maximum partial allocation, even when an EF1+EQ1 allocation exists.An eight-agent instance demonstrates this failure.
  • Interpretation: The obstruction stems from the choice of partial allocation rather than from the instance itself.The example therefore does not show that EF1+EQ1 is impossible for eight agents.
  • Eight-agent obstruction: In the eight-agent instance, residual goods g1 and g2 are jointly valued by u and v, while the outside bundles are anti-correlatedly saturated for these agents.Only Pj† has room for both valuers, so placing g1 there blocks g2 despite low individual counts.
  • Open direction: Extending the approach requires stronger transformations before scattering or a more careful choice of the initial maximum partial allocation.The paper leaves a provable rule for making that choice as future work.
  • Five-agent algorithm: For five agents with normalized binary valuations, Algorithm 6 computes an EF1+EQ1 allocation in polynomial time.Its simpler level-and-scatter procedure assigns residual goods outside the reachable agent set.
  • Five-agent algorithm: The five-agent construction preserves utilities in {t, t + 1} and keeps every bundle worth at most t + 1 to every agent.These bounds imply EQ1 and EF1 for binary valuations, while the required computations are polynomial-time.

C An Alternative Argument for Three Agents

For three agents with normalized binary valuations, a complete allocation satisfying EF1 and EQ1 always exists. The proof constructs a maximal balanced partial allocation and completes it by case analysis.

  • A complete EF1+EQ1 allocation always exists for three agents with normalized binary valuations.
  • The proof assumes each agent values exactly t goods at 1 and discards universally valueless goods until the final arbitrary distribution.
  • The construction begins with a maximal balanced partial allocation giving every agent exactly u valued goods, equivalently a maximum balanced b-matching.
  • Hall’s condition guarantees u ≥⌊t/3⌋, providing the capacity needed to complete the allocation.
  • Case analysis distributes remaining goods while keeping every bundle’s value to every agent at most u + 1, yielding utilities in {u, u + 1}.
  • The resulting complete allocation satisfies both EF1 and EQ1 in every case.

D Omitted Material from Section 4

A normalized goods instance with two agents shows that ex-ante EQ and ex-post EFX can be incompatible. In the example, all EFX-supported randomizations leave agent 1’s expected utility below agent 2’s.

  • A normalized goods instance with two agents can lack any randomized allocation that is ex-ante EQ and ex-post EFX.
  • Both agents value the grand bundle at one, so the instance is normalized.
  • EFX forces g1 to agent 2 and g2 to agent 1; otherwise one agent’s envy survives every permitted single-good removal.
  • The only EFX allocations give realized utility pairs (0.5, 1) and (0.9, 1), so every EFX-supported randomization gives agent 1 expected utility at most 0.9.

D.1 Randomized Guarantees for Laminar Binary Goods Instances

For laminar binary goods, a uniform randomization over at most n deterministic allocations achieves ex-ante EF and EQ while every realization satisfies EF1 and EQ1. The construction partitions each approval set into equal numbers of blocks and assigns them across rounds.

  • Setup: The construction groups identical approval sets, which are pairwise disjoint under normalized binary valuations, and separates universally unvalued junk goods.
  • Construction: Each approval set is partitioned into r blocks, with sizes u or u + 1, where every group uses the same number r of blocks.
  • Construction: Injective labels assign group members to blocks, while filler assignments use distinct agents outside the group.
  • Validity: The randomized allocation is uniform over A(0), …, A(r−1), has support size r ≤n, and each round is a valid allocation.
  • Ex-post guarantees: Every deterministic realization is simultaneously EF1 and EQ1, with bundle values capped at u + 1 for every agent.
  • Ex-ante guarantees: Every agent receives expected utility exactly k/r, so the randomization is ex-ante EQ and ex-ante EF.
  • Limits: The construction is polynomial-time, but it need not satisfy ex-post EQX because removing zero-valued junk or another group’s block may not reduce envy or utility.

D.2 Tight Examples for Ex-post Guarantees in Randomized Allocations

Tight examples show that ex-ante guarantees can prevent strengthening ex-post EF1 and EQ1 to EFX and EQX. The obstruction arises from combining randomized ex-ante requirements with ex-post guarantees.

  • The ex-post EF1+EQ1 guarantees cannot generally be strengthened to EFX+EQX when combined with exact ex-ante EF+EQ.
  • Goods: With four agents and five normalized goods having laminar approval sets, no ex-ante EQ randomization is ex-post EFX.
  • Goods: The goods obstruction follows because ex-post EFX allocations force expected utilities satisfying µ1 + µ2 + µ3 = 2 and µ4 ≥1, incompatible with equal expectations.
  • Chores: With two agents and two binary chores, no ex-ante EF+EQ randomization is ex-post EFX or ex-post EQX.
  • Chores: The two singleton allocations are EFX and EQX, but ex-ante EQ forces one deterministic allocation that is not ex-ante EF.
  • Open scope: For laminar binary goods, exhaustive searches found no obstruction to strengthening ex-post EF1+EQX in the tested scope, leaving that question open.
Loading 2608.26410v1…