TY - GEN

T1 - When Dividing Mixed Manna Is Easier Than Dividing Goods

T2 - 14th International Symposium on Algorithmic Game Theory, SAGT 2021

AU - Garg, Jugal

AU - Hoefer, Martin

AU - McGlaughlin, Peter

AU - Schmalhofer, Marco

N1 - Funding Information:
J. Garg and P. McGlaughlin—Supported by NSF grant CCF-1942321 (CAREER). M. Hoefer and M. Schmalhofer—Supported by DFG grant Ho 3831/5-1, 6-1 and 7-1.
Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

PY - 2021

Y1 - 2021

N2 - We study markets with mixed manna, where m divisible goods and chores shall be divided among n agents to obtain a competitive equilibrium. Equilibrium allocations are known to satisfy many fairness and efficiency conditions. While a lot of recent work in fair division is restricted to linear utilities, we focus on a substantial generalization to separable piecewise-linear and concave (SPLC) utilities. We first derive polynomial-time algorithms for markets with a constant number of items or a constant number of agents. Our main result is a polynomial-time algorithm for instances with a constant number of chores (as well as any number of goods and agents) under the condition that chores dominate the utility of the agents. Interestingly, this stands in contrast to the case when the goods dominate the agents utility in equilibrium, where the problem is known to be PPAD-hard even without chores.

AB - We study markets with mixed manna, where m divisible goods and chores shall be divided among n agents to obtain a competitive equilibrium. Equilibrium allocations are known to satisfy many fairness and efficiency conditions. While a lot of recent work in fair division is restricted to linear utilities, we focus on a substantial generalization to separable piecewise-linear and concave (SPLC) utilities. We first derive polynomial-time algorithms for markets with a constant number of items or a constant number of agents. Our main result is a polynomial-time algorithm for instances with a constant number of chores (as well as any number of goods and agents) under the condition that chores dominate the utility of the agents. Interestingly, this stands in contrast to the case when the goods dominate the agents utility in equilibrium, where the problem is known to be PPAD-hard even without chores.

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

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

U2 - 10.1007/978-3-030-85947-3_22

DO - 10.1007/978-3-030-85947-3_22

M3 - Conference contribution

AN - SCOPUS:85115875835

SN - 9783030859466

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 329

EP - 344

BT - Algorithmic Game Theory - 14th International Symposium, SAGT 2021, Proceedings

A2 - Caragiannis, Ioannis

A2 - Hansen, Kristoffer Arnsfelt

PB - Springer

Y2 - 21 September 2021 through 24 September 2021

ER -