pith. sign in

arxiv: 2604.08345 · v1 · submitted 2026-04-09 · 💻 cs.GT · cs.DS

Revisiting Fair and Efficient Allocations for Bivalued Goods

Hui Liu , Zhijie Zhang This is my paper

Pith reviewed 2026-05-10 17:03 UTC · model grok-4.3

classification 💻 cs.GT cs.DS
keywords fair allocationindivisible goodsbivalued valuationsWEFXfPOEFXpolynomial-time algorithmweighted envy-freeness
0
0 comments X

The pith

An existing algorithm for EFX and fPO allocations of bivalued goods may fail to terminate, but a new polynomial-time algorithm computes WEFX and fPO allocations instead.

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

This paper examines the allocation of indivisible goods to agents whose additive valuations take only two possible values. It demonstrates that a prior polynomial-time algorithm claimed to produce EFX and fPO allocations can enter an infinite loop on certain inputs. A concrete counterexample shows the non-termination. The authors introduce a replacement algorithm that runs in polynomial time and returns a WEFX and fPO allocation; the same procedure adapts to produce WEQX and fPO allocations. The work therefore supplies a reliable computational method for these combined fairness and efficiency properties under bivalued valuations.

Core claim

The paper establishes that Garg and Murhekar's algorithm does not always terminate, supplies an explicit counterexample, and replaces it with a new polynomial-time procedure guaranteed to return a WEFX and fPO allocation for any instance of additive bivalued valuations; the same procedure can be adapted to return a WEQX and fPO allocation.

What carries the argument

A new iterative polynomial-time allocation procedure that maintains invariants ensuring weighted envy-freeness up to any good together with fractional Pareto optimality while assigning indivisible goods.

If this is right

  • WEFX and fPO allocations for additive bivalued valuations can be computed in polynomial time.
  • The same algorithmic template can be adapted to compute WEQX and fPO allocations.
  • Any claim that the earlier algorithm always terminates with an EFX and fPO allocation is false.
  • Weighted variants of envy-freeness and equitability become computationally tractable for this restricted class of valuations.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Weighted fairness notions may admit efficient algorithms even when their unweighted counterparts do not for the same valuation class.
  • The technique could be tested on other two-value or low-support valuation domains to check whether similar termination guarantees hold.
  • Implementations can now safely use WEFX as a target fairness concept in practical fair-division systems handling binary-like preferences.

Load-bearing premise

The new algorithm is assumed to always terminate in polynomial time and to output a valid WEFX and fPO allocation on every bivalued instance.

What would settle it

Any bivalued valuation profile on which the algorithm either exceeds polynomial running time or produces an allocation that violates WEFX or fPO.

read the original abstract

This paper re-examines the problem of fairly and efficiently allocating indivisible goods among agents with additive bivalued valuations. Garg and Murhekar (2021) proposed a polynomial-time algorithm that purported to find an EFX and fPO allocation. However, we provide a counterexample demonstrating that their algorithm may fail to terminate. To address this issue, we propose a new polynomial-time algorithm that computes a WEFX (Weighted Envy-Free up to any good) and fPO allocation, thereby correcting the prior approach and offering a more general solution. Furthermore, we show that our algorithm can be adapted to compute a WEQX (Weighted Equitable up to any good) and fPO allocation.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper shows that the algorithm of Garg and Murhekar (2021) for computing EFX and fPO allocations under additive bivalued valuations can fail to terminate, by exhibiting a concrete counterexample instance that induces a cycle under the algorithm's selection rule. It then introduces a new algorithm that computes a WEFX and fPO allocation in polynomial time via an explicit lexicographic tie-breaking rule together with a potential function equal to the sum of squared weighted utilities; the potential is shown to decrease by at least 1 in every iteration while remaining bounded by O(nm), and the WEFX and fPO invariants are maintained by construction. The same algorithmic framework is adapted to produce a WEQX and fPO allocation.

Significance. If the claims hold, the work supplies a correct polynomial-time procedure for a weighted fairness notion (WEFX) paired with fractional Pareto optimality in the bivalued domain, thereby correcting an earlier claim in the literature. The potential-function argument is a standard and transparent technique that directly yields the polynomial bound without additional parameters. The extension to WEQX broadens the result's utility for resource-allocation settings that require equitable rather than envy-free guarantees.

minor comments (2)
  1. [Section 4] Section 4 (algorithm description): the pseudocode would benefit from an explicit line stating the lexicographic tie-breaking rule on the weighted utilities, as this rule is load-bearing for the potential decrease.
  2. [Theorem 2] Theorem 2 (potential bound): the O(nm) upper bound on the potential function is stated but the derivation from the maximum possible sum of squared weighted utilities is only sketched; a one-line calculation would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful and positive review. The referee summary accurately captures the paper's contributions, including the counterexample to non-termination of the Garg and Murhekar (2021) algorithm and our new polynomial-time procedure for WEFX+fPO (with the potential-function argument) together with the extension to WEQX+fPO. We have no standing objections and will incorporate any minor polishing requested in the revision.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's core contribution consists of an explicit counterexample instance disproving termination of the Garg-Murhekar algorithm together with a new algorithm whose steps are defined by a concrete lexicographic selection rule and whose termination is shown via a strictly decreasing potential function (sum of squared weighted utilities) bounded by O(n m). Correctness invariants for WEFX and fPO are maintained directly by the update rules without reference to any fitted parameters, self-defined quantities, or load-bearing self-citations. The derivation is therefore self-contained and does not reduce any claimed result to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard definitions of EFX, WEFX, fPO, and polynomial-time computability in fair division; no free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)
  • domain assumption Additive bivalued valuations are given as input and the algorithm must run in time polynomial in the number of agents and goods.
    Invoked throughout the abstract as the setting for both the counterexample and the new algorithm.

pith-pipeline@v0.9.0 · 5408 in / 1277 out tokens · 60306 ms · 2026-05-10T17:03:40.239272+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [1]

    Voudouris

    Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, Alexandros Hollender, and Alexandros A. Voudouris. Maximum nash welfare and other stories about EFX. InProceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pages 24–30. ijcai.org, 2020

    work page 2020

  2. [2]

    Finding fair and efficient alloca- tions

    Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. Finding fair and efficient alloca- tions. InProceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, June 18-22, 2018, pages 557–574. ACM, 2018

    work page 2018

  3. [3]

    Best-of-both-worlds fair allocation of indivisible and mixed goods

    Xiaolin Bu, Zihao Li, Shengxin Liu, Xinhang Lu, and Biaoshuai Tao. Best-of-both-worlds fair allocation of indivisible and mixed goods. In Marios Mavronicolas, Qi Qi, and Grant Schoenebeck, editors,Web and Internet Economics - 20th International Conference, WINE 2024, Edinburgh, UK, December 2-5, 2024, Proceedings, Lecture Notes in Computer Science, pages ...

    work page 2024

  4. [4]

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

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

    work page 2011

  5. [5]

    Strategic behavior in multi-unit assignment problems: Theory and evidence from course allocations

    Eric Budish and Estelle Cantillon. Strategic behavior in multi-unit assignment problems: Theory and evidence from course allocations. InComputational Social Systems and the Internet, 1.7. - 6.7.2007, volume 07271 ofDagstuhl Seminar Proceedings. Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany, 2007

    work page 2007

  6. [6]

    Probing efx via pmms: (non-)existence results in discrete fair division, 2025

    Jaros law Byrka, Franciszek Malinka, and Tomasz Ponitka. Probing efx via pmms: (non-)existence results in discrete fair division, 2025

    work page 2025

  7. [7]

    Procaccia, Nisarg Shah, and Junxing Wang

    Ioannis Caragiannis, David Kurokawa, Herv´ e Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare. InProceedings of the 2016 ACM Conference on Economics and Computation, EC ’16, Maastricht, The Netherlands, July 24-28, 2016, pages 305–

    work page 2016

  8. [8]

    Resource allocation and the public sector.Yale Economic Essays, pages 45–98, 1967

    Duncan Foley. Resource allocation and the public sector.Yale Economic Essays, pages 45–98, 1967

    work page 1967

  9. [9]

    Equitable allocations of indivisible goods

    Rupert Freeman, Sujoy Sikdar, Rohit Vaish, and Lirong Xia. Equitable allocations of indivisible goods. In Sarit Kraus, editor,Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pages 280–286. ijcai.org, 2019

    work page 2019

  10. [10]

    Computing fair and efficient allocations with few utility values

    Jugal Garg and Aniket Murhekar. Computing fair and efficient allocations with few utility values. In Algorithmic Game Theory - 14th International Symposium, SAGT 2021, Aarhus, Denmark, September 21-24, 2021, Proceedings, volume 12885 ofLecture Notes in Computer Science, pages 345–359. Springer, 2021

    work page 2021

  11. [11]

    Near fairness in matroids

    Laurent Gourv` es, J´ erˆ ome Monnot, and Lydia Tlilane. Near fairness in matroids. In Torsten Schaub, Gerhard Friedrich, and Barry O’Sullivan, editors,ECAI 2014 - 21st European Conference on Artificial Intelligence, 18-22 August 2014, Prague, Czech Republic - Including Prestigious Applications of Intel- ligent Systems (PAIS 2014), volume 263 ofFrontiers ...

    work page 2014

  12. [12]

    On pareto-optimal and fair allocations with personalized bi-valued utilities, 2025

    Jiarong Jin and Biaoshuai Tao. On pareto-optimal and fair allocations with personalized bi-valued utilities, 2025

    work page 2025

  13. [13]

    Apx-hardness of maximizing nash social welfare with indivisible items.Inf

    Euiwoong Lee. Apx-hardness of maximizing nash social welfare with indivisible items.Inf. Process. Lett., 122:17–20, 2017

    work page 2017

  14. [14]

    Approximately EFX and fpo allocations for bivalued chores

    Zehan Lin, Xiaowei Wu, and Shengwei Zhou. Approximately EFX and fpo allocations for bivalued chores. InProceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2025, Montreal, Canada, August 16-22, 2025, pages 3952–3960. ijcai.org, 2025. 19

    work page 2025

  15. [15]

    Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi

    Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. InProceedings 5th ACM Conference on Electronic Commerce (EC- 2004), New York, NY, USA, May 17-20, 2004, pages 125–131. ACM, 2004

    work page 2004

  16. [16]

    Whinston, and Jerry R

    Andreu Mas-Colell, Michael D. Whinston, and Jerry R. Green. Microeconomic theory.OUP Catalogue, 1995

    work page 1995

  17. [17]

    MIT Press, 2003

    Herv´ e Moulin.Fair division and collective welfare. MIT Press, 2003

    work page 2003

  18. [18]

    On fair and efficient allocations of indivisible goods

    Aniket Murhekar and Jugal Garg. On fair and efficient allocations of indivisible goods. InThirty- Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, Februar...

    work page 2021

  19. [19]

    Understanding EFX allocations: Counting and variants

    Tzeh Yuan Neoh and Nicholas Teh. Understanding EFX allocations: Counting and variants. InAAAI- 25, Sponsored by the Association for the Advancement of Artificial Intelligence, February 25 - March 4, 2025, Philadelphia, PA, USA, pages 14036–14044. AAAI Press, 2025

    work page 2025

  20. [20]

    Computational complexity and approximability of social welfare optimization in multiagent resource allocation.Auton

    Nhan-Tam Nguyen, Trung Thanh Nguyen, Magnus Roos, and J¨ org Rothe. Computational complexity and approximability of social welfare optimization in multiagent resource allocation.Auton. Agents Multi Agent Syst., 28(2):256–289, 2014

    work page 2014

  21. [21]

    The fair and efficient division of the winsor family silver.Management Science, 36(11):1293–1301, 1990

    John Winsor Pratt and Richard Jay Zeckhauser. The fair and efficient division of the winsor family silver.Management Science, 36(11):1293–1301, 1990

    work page 1990

  22. [22]

    Steinhaus

    H. Steinhaus. The problem of fair division.Econometrica, 16(1), 1948

    work page 1948

  23. [23]

    Fair allocation concepts in air traffic management.Unpublished PhD thesis, University of Maryland, College Park, MD, 2002

    Thomas Vossen. Fair allocation concepts in air traffic management.Unpublished PhD thesis, University of Maryland, College Park, MD, 2002

    work page 2002

  24. [24]

    Weighted EF1 allocations for indivisible chores

    Xiaowei Wu, Cong Zhang, and Shengwei Zhou. Weighted EF1 allocations for indivisible chores. In Kevin Leyton-Brown, Jason D. Hartline, and Larry Samuelson, editors,Proceedings of the 24th ACM Conference on Economics and Computation, EC 2023, London, United Kingdom, July 9-12, 2023, page

    work page 2023

  25. [25]

    A A Counterexample For clarity, we present the algorithm from [10] as Algorithm 5, using the notation consistent with this paper

    ACM, 2023. A A Counterexample For clarity, we present the algorithm from [10] as Algorithm 5, using the notation consistent with this paper. Algorithm 5 seeks an EFX allocation by iteratively adjusting allocations and prices. Its main loop (lines 4-7) transfers goods along MBB paths, serving the same purpose as the loop in our Algorithm 1. Subsequently, t...

    work page 2023

  26. [26]

    The process continues until the least spenderisatisfies the pWEFX condition

    and repeats. The process continues until the least spenderisatisfies the pWEFX condition. It is this overly strong termination condition that causes the algorithm to potentially run forever. Theorem 1.There exists a counterexample on which the algorithm of Garg and Murhekar [10] never halts. Proof.Consider an instance with 2 agents and 5 goods. The agents...

    work page