Revisiting Fair and Efficient Allocations for Bivalued Goods
2026-04-09 • Computer Science and Game Theory
Computer Science and Game TheoryData Structures and Algorithms
AI summaryⓘ
The authors re-examined a previous method for fairly dividing items that can't be split, where people value items in two possible ways. They found that the earlier algorithm by Garg and Murhekar could get stuck and never finish. To fix this, they created a new algorithm that runs quickly and ensures a fair and efficient division, using a fairness idea called Weighted Envy-Free up to any good (WEFX). They also showed their method can be adjusted to guarantee another fairness concept called Weighted Equitable up to any good (WEQX).
indivisible goodsadditive valuationsbivalued valuationsEFX (Envy-Free up to any good)fPO (fractional Pareto optimality)WEFX (Weighted Envy-Free up to any good)WEQX (Weighted Equitable up to any good)polynomial-time algorithmfair division
Authors
Hui Liu, Zhijie Zhang
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.