Revisiting Fair and Efficient Allocations for Bivalued Goods

A new computer science paper from researchers Hui Liu and Zhijie Zhang has identified and corrected a critical flaw in a 2021 algorithm designed for a fundamental problem in algorithmic game theory and AI: fairly and efficiently allocating indivisible resources. The original work by Garg and Murhekar proposed a polynomial-time method to find an allocation that is both EFX (Envy-Free up to any good) and fPO (fractional Pareto Optimal) for agents with additive bivalued valuations—a common model where items have only two possible values to each person. However, Liu and Zhang provide a concrete counterexample demonstrating that this algorithm may fail to terminate, leaving the problem unsolved by the prior approach.

To resolve this, the authors introduce a new, verified polynomial-time algorithm. Their solution computes a WEFX (Weighted Envy-Free up to any good) and fPO allocation, which is a more general and robust fairness guarantee than the standard EFX condition originally sought. Furthermore, they show the flexibility of their method by adapting it to also compute a WEQX (Weighted Equitable up to any good) and fPO allocation. This work not only patches a significant hole in the theoretical literature but also advances the toolkit for designing provably fair multi-agent systems, where resources like compute time, data slices, or model access must be divided without envy and without waste.