TY - JOUR
T1 - A Complementary Pivot Algorithm for Competitive Allocation of a Mixed Manna
AU - Chaudhury, Bhaskar Ray
AU - Garg, Jugal
AU - McGlaughlin, Peter
AU - Mehta, Ruta
N1 - Funding Information:
Funding: Financial support from the Division of Computing and Communication Foundations, National Science Foundation (NSF) [Grants 1942321, 1750436] is gratefully acknowledged.
Publisher Copyright:
Copyright: © 2022 INFORMS.
PY - 2023/8
Y1 - 2023/8
N2 - We study the fair division problem of allocating a mixed manna under additively separable piecewise linear concave (SPLC) utilities. A mixed manna contains goods that everyone likes and bads (chores) that everyone dislikes as well as items that some like and others dislike. The seminal work of Bogomolnaia et al. argues why allocating a mixed manna is genuinely more complicated than a good or a bad manna and why competitive equilibrium is the best mechanism. It also provides the existence of equilibrium and establishes its distinctive properties (e.g., nonconvex and disconnected set of equilibria even under linear utilities) but leaves the problem of computing an equilibrium open. Our main results are a linear complementarity problem formulation that captures all competitive equilibria of a mixed manna under SPLC utilities (a strict generalization of linear) and a complementary pivot algorithm based on Lemke’s scheme for finding one. Experimental results on randomly generated instances suggest that our algorithm is fast in practice. Given the PPAD-hardness of the problem, designing such an algorithm is the only non–brute force (nonenumerative) option known; for example, the classic Lemke–Howson algorithm for computing a Nash equilibrium in a two-player game is still one of the most widely used algorithms in practice. Our algorithm also yields several new structural properties as simple corollaries. We obtain a (constructive) proof of existence for a far more general setting, membership of the problem in PPAD, a rational-valued solution, and an odd number of solutions property. The last property also settles the conjecture of Bogomolnaia et al. in the affirmative. Furthermore, we show that, if the number of either agents or items is a constant, then the number of pivots in our algorithm is strongly polynomial when the mixed manna contains all bads.
AB - We study the fair division problem of allocating a mixed manna under additively separable piecewise linear concave (SPLC) utilities. A mixed manna contains goods that everyone likes and bads (chores) that everyone dislikes as well as items that some like and others dislike. The seminal work of Bogomolnaia et al. argues why allocating a mixed manna is genuinely more complicated than a good or a bad manna and why competitive equilibrium is the best mechanism. It also provides the existence of equilibrium and establishes its distinctive properties (e.g., nonconvex and disconnected set of equilibria even under linear utilities) but leaves the problem of computing an equilibrium open. Our main results are a linear complementarity problem formulation that captures all competitive equilibria of a mixed manna under SPLC utilities (a strict generalization of linear) and a complementary pivot algorithm based on Lemke’s scheme for finding one. Experimental results on randomly generated instances suggest that our algorithm is fast in practice. Given the PPAD-hardness of the problem, designing such an algorithm is the only non–brute force (nonenumerative) option known; for example, the classic Lemke–Howson algorithm for computing a Nash equilibrium in a two-player game is still one of the most widely used algorithms in practice. Our algorithm also yields several new structural properties as simple corollaries. We obtain a (constructive) proof of existence for a far more general setting, membership of the problem in PPAD, a rational-valued solution, and an odd number of solutions property. The last property also settles the conjecture of Bogomolnaia et al. in the affirmative. Furthermore, we show that, if the number of either agents or items is a constant, then the number of pivots in our algorithm is strongly polynomial when the mixed manna contains all bads.
KW - LCP formulation
KW - competitive equilibrium
KW - complementary pivot algorithm
KW - fair division
KW - mixed manna
UR - http://www.scopus.com/inward/record.url?scp=85169292306&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85169292306&partnerID=8YFLogxK
U2 - 10.1287/moor.2022.1315
DO - 10.1287/moor.2022.1315
M3 - Article
SN - 0364-765X
VL - 48
SP - 1630
EP - 1656
JO - Mathematics of Operations Research
JF - Mathematics of Operations Research
IS - 3
ER -