When Dividing Mixed Manna Is Easier Than Dividing Goods: Competitive Equilibria with a Constant Number of Chores

Jugal Garg; Martin Hoefer; Peter McGlaughlin; Marco Schmalhofer

doi:10.1007/978-3-030-85947-3_22

When Dividing Mixed Manna Is Easier Than Dividing Goods: Competitive Equilibria with a Constant Number of Chores

Jugal Garg, Martin Hoefer, Peter McGlaughlin, Marco Schmalhofer

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original language	English (US)
Title of host publication	Algorithmic Game Theory - 14th International Symposium, SAGT 2021, Proceedings
Editors	Ioannis Caragiannis, Kristoffer Arnsfelt Hansen
Publisher	Springer
Pages	329-344
Number of pages	16
ISBN (Print)	9783030859466
DOIs	https://doi.org/10.1007/978-3-030-85947-3_22
State	Published - 2021
Event	14th International Symposium on Algorithmic Game Theory, SAGT 2021 - Virtual, Online Duration: Sep 21 2021 → Sep 24 2021

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12885 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th International Symposium on Algorithmic Game Theory, SAGT 2021
City	Virtual, Online
Period	9/21/21 → 9/24/21

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Online availability

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

Library availability

Discover UIUC Full Text

Cite this

Garg, J., Hoefer, M., McGlaughlin, P., & Schmalhofer, M. (2021). When Dividing Mixed Manna Is Easier Than Dividing Goods: Competitive Equilibria with a Constant Number of Chores. In I. Caragiannis, & K. A. Hansen (Eds.), Algorithmic Game Theory - 14th International Symposium, SAGT 2021, Proceedings (pp. 329-344). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12885 LNCS). Springer. https://doi.org/10.1007/978-3-030-85947-3_22

When Dividing Mixed Manna Is Easier Than Dividing Goods: Competitive Equilibria with a Constant Number of Chores. / Garg, Jugal; Hoefer, Martin; McGlaughlin, Peter et al.
Algorithmic Game Theory - 14th International Symposium, SAGT 2021, Proceedings. ed. / Ioannis Caragiannis; Kristoffer Arnsfelt Hansen. Springer, 2021. p. 329-344 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12885 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Garg, J, Hoefer, M, McGlaughlin, P & Schmalhofer, M 2021, When Dividing Mixed Manna Is Easier Than Dividing Goods: Competitive Equilibria with a Constant Number of Chores. in I Caragiannis & KA Hansen (eds), Algorithmic Game Theory - 14th International Symposium, SAGT 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12885 LNCS, Springer, pp. 329-344, 14th International Symposium on Algorithmic Game Theory, SAGT 2021, Virtual, Online, 9/21/21. https://doi.org/10.1007/978-3-030-85947-3_22

Garg J, Hoefer M, McGlaughlin P, Schmalhofer M. When Dividing Mixed Manna Is Easier Than Dividing Goods: Competitive Equilibria with a Constant Number of Chores. In Caragiannis I, Hansen KA, editors, Algorithmic Game Theory - 14th International Symposium, SAGT 2021, Proceedings. Springer. 2021. p. 329-344. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-85947-3_22

Garg, Jugal ; Hoefer, Martin ; McGlaughlin, Peter et al. / When Dividing Mixed Manna Is Easier Than Dividing Goods : Competitive Equilibria with a Constant Number of Chores. Algorithmic Game Theory - 14th International Symposium, SAGT 2021, Proceedings. editor / Ioannis Caragiannis ; Kristoffer Arnsfelt Hansen. Springer, 2021. pp. 329-344 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f30264eaab1c4ff8b329deaac3a33c55,

title = "When Dividing Mixed Manna Is Easier Than Dividing Goods: Competitive Equilibria with a Constant Number of Chores",

abstract = "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.",

author = "Jugal Garg and Martin Hoefer and Peter McGlaughlin and Marco Schmalhofer",

note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 14th International Symposium on Algorithmic Game Theory, SAGT 2021 ; Conference date: 21-09-2021 Through 24-09-2021",

year = "2021",

doi = "10.1007/978-3-030-85947-3_22",

language = "English (US)",

isbn = "9783030859466",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "329--344",

editor = "Ioannis Caragiannis and Hansen, {Kristoffer Arnsfelt}",

booktitle = "Algorithmic Game Theory - 14th International Symposium, SAGT 2021, Proceedings",

address = "Germany",

}

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

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 -

When Dividing Mixed Manna Is Easier Than Dividing Goods: Competitive Equilibria with a Constant Number of Chores

Abstract

Publication series

Conference

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this