Characterization and computation of equilibria for indivisible goods

Simina Brânzei; Hadi Hosseini; Peter Bro Miltersen

doi:10.1007/978-3-662-48433-3_19

Characterization and computation of equilibria for indivisible goods

Simina Brânzei, Hadi Hosseini, Peter Bro Miltersen

College of Information Sciences and Technology

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

9 Scopus citations

Abstract

We consider the problem of allocating indivisible goods using the leading notion of fairness in economics: the competitive equilibrium from equal incomes. Focusing on two major classes of valuations, namely perfect substitutes and perfect complements, we establish the computational properties of algorithms operating in this framework. For the class of valuations with perfect complements, our algorithm yields a surprisingly succinct characterization of instances that admit a competitive equilibrium from equal incomes.

Original language	English (US)
Title of host publication	Algorithmic Game Theory - 8th International Symposium, SAGT 2015
Editors	Martin Hoefer, Martin Hoefer
Publisher	Springer Verlag
Pages	244-255
Number of pages	12
ISBN (Print)	9783662484326
DOIs	https://doi.org/10.1007/978-3-662-48433-3_19
State	Published - 2015
Event	8th International Symposium on Algorithmic Game Theory, SAGT 2015 - Saarbrucken, Germany Duration: Sep 28 2015 → Sep 30 2015

Publication series

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

Conference

Conference	8th International Symposium on Algorithmic Game Theory, SAGT 2015
Country/Territory	Germany
City	Saarbrucken
Period	9/28/15 → 9/30/15

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-662-48433-3_19

Cite this

Brânzei, S., Hosseini, H., & Miltersen, P. B. (2015). Characterization and computation of equilibria for indivisible goods. In M. Hoefer, & M. Hoefer (Eds.), Algorithmic Game Theory - 8th International Symposium, SAGT 2015 (pp. 244-255). Article A19 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9347). Springer Verlag. https://doi.org/10.1007/978-3-662-48433-3_19

Brânzei, Simina ; Hosseini, Hadi ; Miltersen, Peter Bro. / Characterization and computation of equilibria for indivisible goods. Algorithmic Game Theory - 8th International Symposium, SAGT 2015. editor / Martin Hoefer ; Martin Hoefer. Springer Verlag, 2015. pp. 244-255 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{792a35dae2d84db59590ca8eaead3c6c,

title = "Characterization and computation of equilibria for indivisible goods",

abstract = "We consider the problem of allocating indivisible goods using the leading notion of fairness in economics: the competitive equilibrium from equal incomes. Focusing on two major classes of valuations, namely perfect substitutes and perfect complements, we establish the computational properties of algorithms operating in this framework. For the class of valuations with perfect complements, our algorithm yields a surprisingly succinct characterization of instances that admit a competitive equilibrium from equal incomes.",

author = "Simina Br{\^a}nzei and Hadi Hosseini and Miltersen, {Peter Bro}",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 8th International Symposium on Algorithmic Game Theory, SAGT 2015 ; Conference date: 28-09-2015 Through 30-09-2015",

year = "2015",

doi = "10.1007/978-3-662-48433-3_19",

language = "English (US)",

isbn = "9783662484326",

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

publisher = "Springer Verlag",

pages = "244--255",

editor = "Martin Hoefer and Martin Hoefer",

booktitle = "Algorithmic Game Theory - 8th International Symposium, SAGT 2015",

address = "Germany",

}

Brânzei, S, Hosseini, H & Miltersen, PB 2015, Characterization and computation of equilibria for indivisible goods. in M Hoefer & M Hoefer (eds), Algorithmic Game Theory - 8th International Symposium, SAGT 2015., A19, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9347, Springer Verlag, pp. 244-255, 8th International Symposium on Algorithmic Game Theory, SAGT 2015, Saarbrucken, Germany, 9/28/15. https://doi.org/10.1007/978-3-662-48433-3_19

Characterization and computation of equilibria for indivisible goods. / Brânzei, Simina; Hosseini, Hadi; Miltersen, Peter Bro.
Algorithmic Game Theory - 8th International Symposium, SAGT 2015. ed. / Martin Hoefer; Martin Hoefer. Springer Verlag, 2015. p. 244-255 A19 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9347).

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

TY - GEN

T1 - Characterization and computation of equilibria for indivisible goods

AU - Brânzei, Simina

AU - Hosseini, Hadi

AU - Miltersen, Peter Bro

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2015.

PY - 2015

Y1 - 2015

N2 - We consider the problem of allocating indivisible goods using the leading notion of fairness in economics: the competitive equilibrium from equal incomes. Focusing on two major classes of valuations, namely perfect substitutes and perfect complements, we establish the computational properties of algorithms operating in this framework. For the class of valuations with perfect complements, our algorithm yields a surprisingly succinct characterization of instances that admit a competitive equilibrium from equal incomes.

AB - We consider the problem of allocating indivisible goods using the leading notion of fairness in economics: the competitive equilibrium from equal incomes. Focusing on two major classes of valuations, namely perfect substitutes and perfect complements, we establish the computational properties of algorithms operating in this framework. For the class of valuations with perfect complements, our algorithm yields a surprisingly succinct characterization of instances that admit a competitive equilibrium from equal incomes.

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

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

U2 - 10.1007/978-3-662-48433-3_19

DO - 10.1007/978-3-662-48433-3_19

M3 - Conference contribution

AN - SCOPUS:84983770922

SN - 9783662484326

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

SP - 244

EP - 255

BT - Algorithmic Game Theory - 8th International Symposium, SAGT 2015

A2 - Hoefer, Martin

PB - Springer Verlag

T2 - 8th International Symposium on Algorithmic Game Theory, SAGT 2015

Y2 - 28 September 2015 through 30 September 2015

ER -

Brânzei S, Hosseini H, Miltersen PB. Characterization and computation of equilibria for indivisible goods. In Hoefer M, Hoefer M, editors, Algorithmic Game Theory - 8th International Symposium, SAGT 2015. Springer Verlag. 2015. p. 244-255. A19. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-48433-3_19

Characterization and computation of equilibria for indivisible goods

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this