The Pareto Frontier of Inefficiency in Mechanism Design

Aris Filos-Ratsikas; Yiannis Giannakopoulos; Philip Lazos

doi:10.1007/978-3-030-35389-6_14

The Pareto Frontier of Inefficiency in Mechanism Design

Aris Filos-Ratsikas, Yiannis Giannakopoulos, Philip Lazos

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

Abstract

We study the trade-off between the Price of Anarchy (PoA) and the Price of Stability (PoS) in mechanism design, in the prototypical problem of unrelated machine scheduling. We give bounds on the space of feasible mechanisms with respect to the above metrics, and observe that two fundamental mechanisms, namely the First-Price (FP) and the Second-Price (SP), lie on the two opposite extrema of this boundary. Furthermore, for the natural class of anonymous task-independent mechanisms, we completely characterize the PoA/PoS Pareto frontier; we design a class of optimal mechanisms backslashmathcal SPbackslashalpha that lie exactly on this frontier. In particular, these mechanisms range smoothly, with respect to parameter backslashalpha backslashge 1 across the frontier, between the First-Price (backslashmathcal SP1) and Second-Price (backslashmathcal SPbackslashinfty ) mechanisms.

Original language	English
Title of host publication	Web and Internet Economics: 15th International Conference, WINE 2019, New York, NY, USA, December 10–12, 2019, Proceedings
Editors	Ioannis Caragiannis, Vahab Mirrokni, Evdokia Nikolova
Place of Publication	Cham
Publisher	Springer
Pages	186-199
Number of pages	14
ISBN (Electronic)	978-3-030-35389-6
ISBN (Print)	978-3-030-35388-9
DOIs	https://doi.org/10.1007/978-3-030-35389-6_14
Publication status	Published - 3 Dec 2019
Event	The 15th Conference on Web and Internet Economics, 2019 - New York, United States Duration: 10 Dec 2019 → 12 Dec 2019 Conference number: 15 https://wine2019.cs.columbia.edu/call-for-papers.html

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Cham
Volume	11920
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	The 15th Conference on Web and Internet Economics, 2019
Abbreviated title	WINE 2019
Country/Territory	United States
City	New York
Period	10/12/19 → 12/12/19
Internet address	https://wine2019.cs.columbia.edu/call-for-papers.html

Keywords / Materials (for Non-textual outputs)

Mechanism design
Price of anarchy
Price of stability
Pareto frontier

Access to Document

10.1007/978-3-030-35389-6_14Licence: All Rights Reserved

https://link.springer.com/chapter/10.1007/978-3-030-35389-6_14Licence: All Rights Reserved

Cite this

Filos-Ratsikas, A., Giannakopoulos, Y., & Lazos, P. (2019). The Pareto Frontier of Inefficiency in Mechanism Design. In I. Caragiannis, V. Mirrokni, & E. Nikolova (Eds.), Web and Internet Economics: 15th International Conference, WINE 2019, New York, NY, USA, December 10–12, 2019, Proceedings (pp. 186-199). (Lecture Notes in Computer Science; Vol. 11920). Springer. https://doi.org/10.1007/978-3-030-35389-6_14

Filos-Ratsikas, Aris ; Giannakopoulos, Yiannis ; Lazos, Philip. / The Pareto Frontier of Inefficiency in Mechanism Design. Web and Internet Economics: 15th International Conference, WINE 2019, New York, NY, USA, December 10–12, 2019, Proceedings. editor / Ioannis Caragiannis ; Vahab Mirrokni ; Evdokia Nikolova. Cham : Springer, 2019. pp. 186-199 (Lecture Notes in Computer Science).

@inproceedings{0a1908ee503f4f009445b913bfaf199e,

title = "The Pareto Frontier of Inefficiency in Mechanism Design",

abstract = "We study the trade-off between the Price of Anarchy (PoA) and the Price of Stability (PoS) in mechanism design, in the prototypical problem of unrelated machine scheduling. We give bounds on the space of feasible mechanisms with respect to the above metrics, and observe that two fundamental mechanisms, namely the First-Price (FP) and the Second-Price (SP), lie on the two opposite extrema of this boundary. Furthermore, for the natural class of anonymous task-independent mechanisms, we completely characterize the PoA/PoS Pareto frontier; we design a class of optimal mechanisms backslashmathcal SPbackslashalpha that lie exactly on this frontier. In particular, these mechanisms range smoothly, with respect to parameter backslashalpha backslashge 1 across the frontier, between the First-Price (backslashmathcal SP1) and Second-Price (backslashmathcal SPbackslashinfty ) mechanisms.",

keywords = "Mechanism design, Price of anarchy, Price of stability, Pareto frontier",

author = "Aris Filos-Ratsikas and Yiannis Giannakopoulos and Philip Lazos",

year = "2019",

month = dec,

day = "3",

doi = "10.1007/978-3-030-35389-6_14",

language = "English",

isbn = "978-3-030-35388-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "186--199",

editor = "Ioannis Caragiannis and Vahab Mirrokni and Evdokia Nikolova",

booktitle = "Web and Internet Economics: 15th International Conference, WINE 2019, New York, NY, USA, December 10–12, 2019, Proceedings",

address = "United Kingdom",

note = "The 15th Conference on Web and Internet Economics, 2019, WINE 2019 ; Conference date: 10-12-2019 Through 12-12-2019",

url = "https://wine2019.cs.columbia.edu/call-for-papers.html",

}

Filos-Ratsikas, A, Giannakopoulos, Y & Lazos, P 2019, The Pareto Frontier of Inefficiency in Mechanism Design. in I Caragiannis, V Mirrokni & E Nikolova (eds), Web and Internet Economics: 15th International Conference, WINE 2019, New York, NY, USA, December 10–12, 2019, Proceedings. Lecture Notes in Computer Science, vol. 11920, Springer, Cham, pp. 186-199, The 15th Conference on Web and Internet Economics, 2019, New York, New York, United States, 10/12/19. https://doi.org/10.1007/978-3-030-35389-6_14

The Pareto Frontier of Inefficiency in Mechanism Design. / Filos-Ratsikas, Aris; Giannakopoulos, Yiannis; Lazos, Philip.
Web and Internet Economics: 15th International Conference, WINE 2019, New York, NY, USA, December 10–12, 2019, Proceedings. ed. / Ioannis Caragiannis; Vahab Mirrokni; Evdokia Nikolova. Cham: Springer, 2019. p. 186-199 (Lecture Notes in Computer Science; Vol. 11920).

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

TY - GEN

T1 - The Pareto Frontier of Inefficiency in Mechanism Design

AU - Filos-Ratsikas, Aris

AU - Giannakopoulos, Yiannis

AU - Lazos, Philip

N1 - Conference code: 15

PY - 2019/12/3

Y1 - 2019/12/3

N2 - We study the trade-off between the Price of Anarchy (PoA) and the Price of Stability (PoS) in mechanism design, in the prototypical problem of unrelated machine scheduling. We give bounds on the space of feasible mechanisms with respect to the above metrics, and observe that two fundamental mechanisms, namely the First-Price (FP) and the Second-Price (SP), lie on the two opposite extrema of this boundary. Furthermore, for the natural class of anonymous task-independent mechanisms, we completely characterize the PoA/PoS Pareto frontier; we design a class of optimal mechanisms backslashmathcal SPbackslashalpha that lie exactly on this frontier. In particular, these mechanisms range smoothly, with respect to parameter backslashalpha backslashge 1 across the frontier, between the First-Price (backslashmathcal SP1) and Second-Price (backslashmathcal SPbackslashinfty ) mechanisms.

AB - We study the trade-off between the Price of Anarchy (PoA) and the Price of Stability (PoS) in mechanism design, in the prototypical problem of unrelated machine scheduling. We give bounds on the space of feasible mechanisms with respect to the above metrics, and observe that two fundamental mechanisms, namely the First-Price (FP) and the Second-Price (SP), lie on the two opposite extrema of this boundary. Furthermore, for the natural class of anonymous task-independent mechanisms, we completely characterize the PoA/PoS Pareto frontier; we design a class of optimal mechanisms backslashmathcal SPbackslashalpha that lie exactly on this frontier. In particular, these mechanisms range smoothly, with respect to parameter backslashalpha backslashge 1 across the frontier, between the First-Price (backslashmathcal SP1) and Second-Price (backslashmathcal SPbackslashinfty ) mechanisms.

KW - Mechanism design

KW - Price of anarchy

KW - Price of stability

KW - Pareto frontier

U2 - 10.1007/978-3-030-35389-6_14

DO - 10.1007/978-3-030-35389-6_14

M3 - Conference contribution

SN - 978-3-030-35388-9

T3 - Lecture Notes in Computer Science

SP - 186

EP - 199

BT - Web and Internet Economics: 15th International Conference, WINE 2019, New York, NY, USA, December 10–12, 2019, Proceedings

A2 - Caragiannis, Ioannis

A2 - Mirrokni, Vahab

A2 - Nikolova, Evdokia

PB - Springer

CY - Cham

T2 - The 15th Conference on Web and Internet Economics, 2019

Y2 - 10 December 2019 through 12 December 2019

ER -

Filos-Ratsikas A, Giannakopoulos Y, Lazos P. The Pareto Frontier of Inefficiency in Mechanism Design. In Caragiannis I, Mirrokni V, Nikolova E, editors, Web and Internet Economics: 15th International Conference, WINE 2019, New York, NY, USA, December 10–12, 2019, Proceedings. Cham: Springer. 2019. p. 186-199. (Lecture Notes in Computer Science). doi: 10.1007/978-3-030-35389-6_14

The Pareto Frontier of Inefficiency in Mechanism Design

Abstract

Publication series

Conference

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Cite this