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 -