Revisiting Fair and Efficient Allocations for Bivalued Goods
This work addresses algorithmic fairness in resource allocation for agents with specific valuations, correcting an incremental error in prior research.
The paper tackles the problem of fairly and efficiently allocating indivisible goods with bivalued valuations by identifying a flaw in a prior algorithm that may not terminate, and proposes a new polynomial-time algorithm that computes a WEFX and fPO allocation, with an adaptation for WEQX and fPO allocations.
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.