TY - GEN

T1 - Competitive allocation of a mixed manna

AU - Chaudhury, Bhaskar Ray

AU - Garg, Jugal

AU - McGlaughlin, Peter

AU - Mehta, Ruta

N1 - Funding Information:
Supported by NSF Grant CCF-1942321 (CAREER)
Publisher Copyright:
Copyright © 2021 by SIAM

PY - 2021

Y1 - 2021

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 that everyone dislikes, as well as items that some like and others dislike. The seminal work of Bogomolnaia et al. [14] argue why allocating a mixed manna is genuinely more complicated than a good or a bad manna, and why competitive equilibrium is the best mechanism. They also provide the existence of equilibrium and establish its peculiar properties (e.g., non-convex and disconnected set of equilibria even under linear utilities), but leave the problem of computing an equilibrium open. Our main result is a simplex-like algorithm based on Lemke's scheme for computing a competitive allocation of a mixed manna under SPLC utilities, a strict generalization of linear. Experimental results on randomly generated instances suggest that our algorithm will be fast in practice. The problem is known to be PPAD-hard for the case of good manna [24], and we also show a similar result for the case of bad manna. Given these PPAD-hardness results, designing such an algorithm is the only non-enumerative option known. 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, rational-valued solution, and odd number of solutions property. The last property also settles the conjecture of [14] in the affirmative.

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 that everyone dislikes, as well as items that some like and others dislike. The seminal work of Bogomolnaia et al. [14] argue why allocating a mixed manna is genuinely more complicated than a good or a bad manna, and why competitive equilibrium is the best mechanism. They also provide the existence of equilibrium and establish its peculiar properties (e.g., non-convex and disconnected set of equilibria even under linear utilities), but leave the problem of computing an equilibrium open. Our main result is a simplex-like algorithm based on Lemke's scheme for computing a competitive allocation of a mixed manna under SPLC utilities, a strict generalization of linear. Experimental results on randomly generated instances suggest that our algorithm will be fast in practice. The problem is known to be PPAD-hard for the case of good manna [24], and we also show a similar result for the case of bad manna. Given these PPAD-hardness results, designing such an algorithm is the only non-enumerative option known. 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, rational-valued solution, and odd number of solutions property. The last property also settles the conjecture of [14] in the affirmative.

UR - http://www.scopus.com/inward/record.url?scp=85104203927&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85104203927&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85104203927

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1405

EP - 1424

BT - ACM-SIAM Symposium on Discrete Algorithms, SODA 2021

A2 - Marx, Daniel

PB - Association for Computing Machinery

T2 - 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021

Y2 - 10 January 2021 through 13 January 2021

ER -