Pith. sign in

REVIEW 4 minor 26 references

Best-of-Both-Worlds Fairness and Pareto Optimality

T0 review · 0 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For every two-agent fair-division instance with non-negative additive valuations, there is a lottery over two allocations that is ex-ante envy-free, ex-post EFX, and Pareto optimal.

desk verdict Clean resolution of the two-agent case of a BoBW open problem, with a sharp three-agent impossibility; the proofs hold up and the paper deserves peer review. read the letter →

arxiv 2608.08966 v1 pith:IZKBQ75Q submitted 2026-08-10 cs.GT

Haris Aziz This is my paper · ORCID
classification cs.GT MSC 91B32
keywords fairdivisionindivisiblegoodsbestofbothworldsfairnessex-anteenvy-freenessex-postEFXParetooptimalityadditivevaluationsrandomizedallocation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper targets an open 'best of both worlds' question in fair division: can a random allocation of indivisible items be exactly fair in expectation while every outcome it might produce is both approximately fair and efficient? For two agents with non-negative additive valuations, the answer is yes: there is always a lottery over at most two allocations that is ex-ante envy-free, ex-post envy-free up to any item (EFX), and ex-post Pareto optimal. The paper also gives a softer version with ex-post EF1, proves the lotteries can be computed in pseudo-polynomial time for integral valuations, and shows the two-agent guarantee is sharp by constructing a three-agent, four-good instance where no such lottery exists.

What carries the argument

The central objects are two extremal allocations, one favoring each agent, built by a three-step lexicographic construction: make agent $i$ envy-free, maximize the other agent's utility subject to that, then maximize total utility. The proof that each allocation is EFX—envy-free up to any positively valued item, meaning each agent prefers her own bundle after removing any positively valued item from the other's bundle—and Pareto optimal runs through a swap-and-transfer argument that relies on additivity. The uniform lottery over the two allocations is ex-ante envy-free because, with two agents, ex-ante envy-freeness is equivalent to ex-ante proportionality, and the extremality inequalities guarantee that each agent's expected own-bundle utility is at least half her value for all items. The weaker EF1 route uses a separate structural lemma: any weak Pareto improvement of a two-agent EFX allocation is EF1, so the support of a known ex-ante envy-free EFX lottery can be Pareto-completed without losing ex-ante envy-freeness.

What would settle it

Compute the two lexicographic allocations $A^1$ and $A^2$ from Section 5 for any concrete two-agent instance and check whether each is EFX and Pareto optimal and whether each agent's expected own-bundle utility in the uniform lottery is at least $v_i(M)/2$; the theorem predicts all three checks pass for every non-negative additive instance. For the three-agent claim, enumerate all EFX allocations for the four-good valuations in Theorem 5; if any allocation beyond $X,Y,Z$ is simultaneously EFX and Pareto optimal, or if a lottery over $X,Y,Z$ satisfies the three envy-surplus inequalities, the impossibility would be refuted.

Watch

Extended reading notes

Core claim

The central discovery is that two-agent fair division achieves the strongest natural combination of ex-ante and ex-post requirements. For every instance with two agents and non-negative additive valuations, there exists a probabilistic allocation that is ex-ante envy-free, ex-post EFX, and ex-post Pareto optimal, with support size at most two; when two allocations are required, each receives probability $1/2$. The proof constructs, for each agent, a lexicographically extremal allocation that first makes that agent envy-free, then maximizes the other agent's utility, then maximizes total utility, and shows that each resulting allocation is EFX and Pareto optimal. The paper also proves an impossibility for three agents: with strictly positive additive utilities over four goods, no ex-ante envy-free lottery can be supported on allocations that are simultaneously EFX and Pareto optimal.

Load-bearing premise

The load-bearing premise is that the two agents' valuations are additive and non-negative, because the transfer inequalities, the proportionality equivalence, and the lexicographic EFX/PO arguments all use additivity, and the paper itself notes that without it (e.g., monotone subadditive or submodular valuations) even deterministic EF1 plus Pareto optimality can fail.

Editorial extensions

If this is right

  • Every two-agent instance admits a two-outcome lottery that is simultaneously fair in expectation, envy-free up to any item in every realized allocation, and Pareto optimal; a single coin flip implements it.
  • For integer-valued additive valuations, this lottery is constructible in pseudo-polynomial time, so the guarantee is algorithmic rather than purely existential.
  • The result is tight on the efficiency dimension: the paper notes that ex-post fractional Pareto optimality cannot be added, and that ex-ante Pareto optimality together with ex-post EF1 and ex-ante envy-freeness is likewise impossible even for two agents.
  • For three or more agents, the ex-ante envy-free, ex-post EF1, ex-post Pareto-optimal combination remains open, and the paper's appendix shows that the two-agent Pareto-completion argument cannot be transplanted because a Pareto improvement of a three-agent EFX allocation can fail EF1.
  • Additivity is essential: for monotone subadditive or submodular valuations, even a deterministic allocation that is both EF1 and Pareto optimal may fail to exist.
  • The three-agent impossibility uses strictly positive valuations and only four goods, so the obstruction is not an artifact of zero-valued items.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural next step is to search small three- and four-agent additive instances to locate the exact boundary of the impossibility; the paper's four-good example shows the boundary is low, but the minimal number of goods required for the obstruction is not identified.
  • The lexicographic template could generalize to other two-agent objectives: replacing the 'maximize the other agent's utility' step with, say, maximizing Nash welfare or minimizing envy surplus might yield ex-ante fairness together with different ex-post efficiency or stability benchmarks.
  • If a positive result for three or more agents exists, the paper's appendix suggests it must coordinate fairness and efficiency globally rather than Pareto-improving each support allocation independently, since the two-agent transfer argument provably fails there.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper studies the best-of-both-worlds (BoBW) question in fair division of indivisible goods: existence of a lottery that is envy-free ex ante while every realized allocation is, ex post, approximately envy-free and Pareto optimal. For two agents with non-negative additive valuations, it proves (Theorem 2) existence of an ex-ante envy-free lottery supported on allocations that are EF1 and Pareto optimal, and then a stronger result (Theorem 4) with ex-post EFX instead of EF1, with support size at most two. The strong result is obtained by a lexicographic construction of two extremal allocations, one making agent 1 envy-free then maximizing agent 2's utility and total utility, and the reverse for agent 2. For integral valuations, pseudo-polynomial algorithms are given (Propositions 1 and 2), and it is shown that the exact lexicographic allocation is weakly NP-hard in general. The paper also proves an impossibility (Theorem 5): for three agents with strictly positive additive valuations over four goods, no ex-ante envy-free lottery can be supported on allocations that are simultaneously EFX and Pareto optimal. Appendices provide an example where randomized Adjusted Winner fails and show that Lemma 2 does not extend to three agents.

Significance. The paper resolves the two-agent case of a question posed by Freeman et al. (2020) and strengthens the guarantee from EF1 to EFX, which is the strongest approximate envy-freeness notion currently known to be achievable with Pareto optimality in this setting. The proof of Theorem 4 is self-contained and introduces a clean lexicographic method that is likely to be reusable. The impossibility for three agents with only four goods is a valuable boundary result. The paper also gives pseudo-polynomial algorithms and an NP-hardness caveat, and it is transparent about the additivity assumption. I checked the proofs of Lemma 2, Lemma 3, Theorem 4, and Theorem 5 in detail and found them correct and complete; the computational claims are consistent with the stated DP recurrences. The external theorems (Bu et al., Aziz et al.) are cited appropriately.

minor comments (4)
  1. [Section 1 / Corollary 1] The introduction states 'The proof of Theorem 1 proceeds by a Pareto-completion argument' for Main Result 1, but Theorem 1 is later assigned to the cited Bu et al. result in Section 4; similarly, Corollary 1 says 'the lottery in Theorem 1' when the intended reference is the authors' Theorem 2. Please renumber or refer to 'Main Result 1' and 'Theorem 2' to remove the ambiguity.
  2. [Abstract] In the second sentence, 'envy-free up each one item (EFX)' should read 'envy-free up to any item' (or 'up to each item') to match Definition 4.
  3. [Section 7] The first sentence contains an extra period inside the phrase 'ex-ante EF+ex-post EF1+ex-post PO.'; the period should be placed outside the string so the sentence reads naturally.
  4. [Related Work] The spelling of 'Frosh' in the reference to Babaioff and Frosh [6] should be checked for consistency, and the same for any other author names that appear only once in the text.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the two-agent existence proofs are self-contained; self-citations are ancillary and non-load-bearing.

full rationale

The strongest claim, Main Result 2 (Theorem 4), is derived without any self-citation. The two extremal allocations A1 and A2 are defined by explicit lexicographic constraints (agent i envy-free, then maximize the other agent's utility, then maximize total utility), so the target properties are not embedded in the definition. Lemma 3 proves EFX and Pareto optimality directly from these constraints, and the ex-ante envy-freeness proof is a case analysis using the two-agent identity vi(Ai)+vi(A3-i)=vi(M) and the equivalence between ex-ante proportionality and ex-ante envy-freeness (Eq. (3)). Main Result 1 (Theorem 2) uses Bu et al. as an external starting point only to obtain an ex-ante envy-free, ex-post EFX lottery; Lemma 2 is proved from EFX and weak Pareto dominance, and preservation of ex-ante envy-freeness follows from supportwise dominance together with Eq. (3). The computational claim invokes Aziz et al. [2] as a subroutine, but that is a published pseudo-polynomial reallocation theorem whose assumptions do not include the target best-of-both-worlds conclusion; it is therefore independent support rather than a circular input. The citation of Aziz et al. [5] in the discussion concerns the impossibility of ex-post fPO and does not carry the positive result. No fitted parameter is renamed as a prediction, and no uniqueness or ansatz is imported from the author's own prior work to force the construction. The only reason the score is not zero is the presence of self-citations in the computational and discussion sections, but they are not load-bearing for the central existence theorems.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central existence claims rest on standard finite-combinatorics reasoning and on the stated domain assumptions (additive non-negative complete allocations). The paper uses two external theorems as black boxes: the Bu et al. lottery (for the EF1 route) and the pseudo-polynomial Pareto dominance algorithm of Aziz et al. (for the computational variant). No fitted parameters or new postulated entities appear.

assumptions (5)
  • domain assumption Valuations are additive and non-negative (Section 3, model).
    All definitions of EF, EFX, EF1, proportionality, and the equivalence ex-ante EF iff ex-ante proportionality for two agents rely on additive utilities. The paper's results are scoped to this model; Section 7 notes additivity is essential.
  • domain assumption Allocations are complete (each item assigned to exactly one agent).
    Used in the two-agent identity vi(Aj)=vi(M)-vi(Ai) (Eq. (3)) and throughout the lexicographic construction and Pareto domination.
  • standard math The set of deterministic allocations is finite, so Pareto-maximal elements in the weakly-dominating set exist (proof of Theorem 2, Section 4).
    Finite combinatorial search is used to choose Bt; this is standard finiteness, not an ad hoc assumption.
  • domain assumption Theorem 3.2 of Bu et al. [9]: there exists an ex-ante envy-free lottery supported on EFX allocations for two agents.
    Invoked as a black box in the proof of Main Result 1 (Theorem 2 in Section 4) as the starting lottery; not re-derived in this paper beyond a sketch of the cutter-chooser procedure.
  • domain assumption Theorem 4 of Aziz et al. [2]: a pseudo-polynomial-time algorithm computes a Pareto-optimal allocation weakly dominating a given allocation for constant number of agents.
    Used in Proposition 1 and Corollary 1 for the computational version of Main Result 1; cited from prior work by the same author.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Best-of-Both-Worlds Fairness and Pareto Optimality." pith.science (2026). https://pith.science/paper/IZKBQ75Q

@misc{pith2026260808966,
  author       = {Pith},
  title        = {Pith review of: Best-of-Both-Worlds Fairness and Pareto Optimality},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IZKBQ75Q}},
  note         = {Machine review of arXiv:2608.08966}
}
read the original abstract

We consider fair allocation of indivisible items among agents with non-negative and additive valuations. The goal is to construct a lottery over deterministic allocations whose induced fractional allocation is envy-free, while every realised allocation is envy-free up to one item and Pareto optimal. We show that this is always possible for two agents. We then prove a stronger result that there always exists a lottery over deterministic allocations whose induced fractional allocation is envy-free, while every realised allocation is envy-free up each one item (EFX) and Pareto optimal. For non-negative integral additive valuations, such a lottery can be computed in pseudo-polynomial time. We also prove that for three agents and four items, there may be no ex-ante envy-free lottery that can be supported on allocations that are simultaneously EFX and Pareto optimal.

Figures

Figures reproduced from arXiv: 2608.08966 by the authors.

Figure 1
Figure 1. Set relations used in the proof of Lemma 2. The initial allocation [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 23 canonical work pages

  1. [1]

    H. Aziz. A probabilistic approach to voting, allocation, matching, and coalition formation. In J.-F. Laslier, H. Moulin, R. Sanver, and W. S. Zwicker, editors,The Future of Economic Design. Springer-Verlag, 2019

    work page 2019

  2. [2]

    H. Aziz, P. Biro, J. Lang, J. Lesca, and J. Monnot. Efficient realloca- tion under additive and ordinal preferences.Theoretical Computer Science, 2019

    work page 2019

  3. [3]

    H. Aziz, I. Caragiannis, A. Igarashi, and T. Walsh. Fair allocation of indivisible goods and chores.Journal of Autonomous Agents and Multi- Agent Systems, 36(3), 2022

    work page 2022

  4. [4]

    H. Aziz, A. Ganguly, and E. Micha. Best of both worlds fairness under entitlements. InProceedings of the 22nd International Conference on Au- tonomous Agents and Multiagent Systems (AAMAS),pages941–948.ACM, 2023

    work page 2023

  5. [5]

    H. Aziz, R. Freeman, N. Shah, and R. Vaish. Best of both worlds: Ex ante and ex post fairness in resource allocation.Operations Research, 72 (4):1674—1688, 2024. 23

    work page 2024

  6. [6]

    Near-optimalbest-of-both-worldsfairness for few agents, 2026

    MosheBabaioffandGefenFrosh. Near-optimalbest-of-both-worldsfairness for few agents, 2026

    work page 2026

  7. [7]

    Bouveret, Y

    S. Bouveret, Y. Chevaleyre, and J. Lang. Fair allocation of indivisible goods. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, editors,Handbook of Computational Social Choice, chapter 12, pages 284–

    work page

  8. [8]

    S. J. Brams, D. M. Kilgour, and C. Klamler. Two-person fair division of indivisible items: An efficient, envy-free algorithm.Notices of the AMS, 61 (2):130–141, 2014

    work page 2014

Show all 26 references
  1. [9]

    X. Bu, Z. Li, S. Liu, X. Lu, and B. Tao. Best-of-both-worlds fair allocation of indivisible and mixed goods. InProceedings of the 20th Conference on Web and Internet Economics, 2024

    2024

  2. [10]

    X. Bu, Z. Li, S. Liu, X. Lu, and B. Tao. Best-of-both-worlds fair alloca- tion of indivisible and mixed goods.CoRR, abs/2410.06877, 2024. URL https://doi.org/10.48550/arXiv.2410.06877

    2024 doi arXiv

  3. [11]

    E. Budish. The combinatorial assignment problem: Approximate competi- tive equilibrium from equal incomes.Journal of Political Economy, 119(6): 1061–1103, 2011

    2011

  4. [12]

    Caragiannis, D

    I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang. The Unreasonable Fairness of Maximum Nash Welfare. InPro- ceedings of the 17th ACM Conference on Economics and Computation (ACM-EC), pages 305–322, 2016

    2016

  5. [13]

    Caragiannis, K

    I. Caragiannis, K. A. Hansen, and N. Rathi. On the complexity of pareto- optimal and envy-free lotteries. InProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, pages 244– 252, 2024

    2024

  6. [14]

    Nonexistence of simultaneously EF1 and pareto optimal allocations for submodular valua- tions, 2026

    Harish Chandramouleeswaran and Prajakta Nimbhorkar. Nonexistence of simultaneously EF1 and pareto optimal allocations for submodular valua- tions, 2026

    2026

  7. [15]

    B. R. Chaudhury, J. Garg, and K. Mehlhorn. Efx exists for three agents. Journal of the ACM, 71(1), February 2024. ISSN 0004-5411. URL https://doi.org/10.1145/3616009

    2024 doi

  8. [16]

    Feldman, S

    M. Feldman, S. Mauras, V. V. Narayan, and T. Ponitka. Breaking the envy cycle: Best-of-both-worlds guarantees for subadditive valuations. In Proceedings of the 25th ACM Conference on Economics and Computation, 2024

    2024

  9. [17]

    Bestofbothworlds:ex-anteandex-post fairness in resource allocation

    R.Freeman, N.Shah, andR.Vaish. Bestofbothworlds:ex-anteandex-post fairness in resource allocation. InProceedings of the 21st ACM Conference on Economics and Computation, pages 21–22, 2020. 24

    2020

  10. [18]

    Fairly allocating goods in parallel

    Rohan Garg and Alexandros Psomas. Fairly allocating goods in parallel. InProceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2025, pages 839–847. International Foun- dation for Autonomous Agents and Multiagent Systems, 2025

    2025

  11. [19]

    Goldman and A

    J. Goldman and A. D. Procaccia. Spliddit: Unleashing fair division algo- rithms.ACM SIGecom Exchanges, 13(2):41–46, 2014

    2014

  12. [20]

    Hoefer, M

    M. Hoefer, M. Schmalhofer, and G. Varricchio. Best of both worlds: Agents with entitlements. InProceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 564–572. ACM, 2023

    2023

  13. [21]

    Kavitha, S

    T. Kavitha, S. Panchapakesan, R. Vaish, V. Viswanathan, and J. Yadav. Best-of-both-worlds guarantees with fairer endings, 2025. arXiv preprint arXiv:2507.16209

    2025 arXiv

  14. [22]

    D. M. Kilgour and R. Vetschera. Two-player fair division of indivisible items: Comparison of algorithms.European Journal of Operational Re- search, 271(2):620–631

  15. [23]

    Mackenzie and M

    S. Mackenzie and M. Suzuki. When one good is not enough: Ef1 and pareto optimality are not compatible for submodular valuations, 2026. arXiv preprint arXiv:2607.17811

    2026 arXiv

  16. [24]

    Rothe, editor.Economics and Computation: An Introduction to Algo- rithmic Game Theory, Computational Social Choice, and Fair Division

    J. Rothe, editor.Economics and Computation: An Introduction to Algo- rithmic Game Theory, Computational Social Choice, and Fair Division. Springer, 2015

    2015

  17. [25]

    Vetschera and D

    R. Vetschera and D. M. Kilgour. Fair division of indivisible items between two players: design parameters for contested pile methods.Theory and Decision, 76:547–572, 2013. 25 Appendix A. Failure of Randomized Adjusted Winner to satisfy EF1 Example 4.The two integral allocation...

    2013

  18. [311]

    Cambridge University Press, 2016

    2016

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.