Social welfare in one-sided matching mechanisms

George Christodoulou; Aris Filos-Ratsikas; Soren Kristoffer Stiil Frederiksen; Paul W. Goldberg; Jie Zhang; Jinshan Zhang

doi:10.1007/978-3-319-46882-2_3

Social welfare in one-sided matching mechanisms

George Christodoulou, Aris Filos-Ratsikas, Soren Kristoffer Stiil Frederiksen, Paul W. Goldberg, Jie Zhang, Jinshan Zhang

Department of Computer Science

Research output: Chapter or section in a book/report/conference proceeding › Chapter in a published conference proceeding

9 Citations (SciVal)

Abstract

We study the Price of Anarchy of mechanisms for the well-known problem of one-sided matching, or house allocation, with respect to the social welfare objective. We consider both ordinal mechanisms, where agents submit preference lists over the items, and cardinal mechanisms, where agents may submit numerical values for the items being allocated. We present a general lower bound of Ω (√n) on the Price of Anarchy, which applies to all mechanisms. We show that two well-known mechanisms, Probabilistic Serial, and Random Priority, achieve a matching upper bound. We extend our lower bound to the Price of Stability of a large class of mechanisms that satisfy a common proportionality property, and show stronger bounds on the Price of Anarchy of all deterministic mechanisms.

Original language	English
Title of host publication	Autonomous Agents and Multiagent Systems
Editors	N. Osman, C. Sierra
Publisher	Springer, Cham; Fondazione C.I.M.E., Florence
Pages	30-50
Number of pages	21
ISBN (Print)	978-3-319-46881-5
DOIs	https://doi.org/10.1007/978-3-319-46882-2_3
Publication status	Published - 24 Sept 2016

Bibliographical note

Access to Document

10.1007/978-3-319-46882-2_3

Cite this

Social welfare in one-sided matching mechanisms. / Christodoulou, George; Filos-Ratsikas, Aris; Frederiksen, Soren Kristoffer Stiil et al.
Autonomous Agents and Multiagent Systems. ed. / N. Osman; C. Sierra. Springer, Cham; Fondazione C.I.M.E., Florence, 2016. p. 30-50.

Research output: Chapter or section in a book/report/conference proceeding › Chapter in a published conference proceeding

@inproceedings{12d7a30c76db4607bcfacfaabb76f4b7,

title = "Social welfare in one-sided matching mechanisms",

abstract = "We study the Price of Anarchy of mechanisms for the well-known problem of one-sided matching, or house allocation, with respect to the social welfare objective. We consider both ordinal mechanisms, where agents submit preference lists over the items, and cardinal mechanisms, where agents may submit numerical values for the items being allocated. We present a general lower bound of Ω (√n) on the Price of Anarchy, which applies to all mechanisms. We show that two well-known mechanisms, Probabilistic Serial, and Random Priority, achieve a matching upper bound. We extend our lower bound to the Price of Stability of a large class of mechanisms that satisfy a common proportionality property, and show stronger bounds on the Price of Anarchy of all deterministic mechanisms.",

author = "George Christodoulou and Aris Filos-Ratsikas and Frederiksen, {Soren Kristoffer Stiil} and Goldberg, {Paul W.} and Jie Zhang and Jinshan Zhang",

note = "{\textcopyright} 2016 Springer International Publishing AG; AAMAS '16 International Conference on Autonomous Agents and Multiagent Systems, AAMAS '16 ; Conference date: 09-05-2016 Through 13-05-2016",

year = "2016",

month = sep,

day = "24",

doi = "10.1007/978-3-319-46882-2_3",

language = "English",

isbn = "978-3-319-46881-5",

pages = "30--50",

editor = "N. Osman and C. Sierra",

booktitle = "Autonomous Agents and Multiagent Systems",

publisher = "Springer, Cham; Fondazione C.I.M.E., Florence",

}

TY - GEN

T1 - Social welfare in one-sided matching mechanisms

AU - Christodoulou, George

AU - Filos-Ratsikas, Aris

AU - Frederiksen, Soren Kristoffer Stiil

AU - Goldberg, Paul W.

AU - Zhang, Jie

AU - Zhang, Jinshan

PY - 2016/9/24

Y1 - 2016/9/24

N2 - We study the Price of Anarchy of mechanisms for the well-known problem of one-sided matching, or house allocation, with respect to the social welfare objective. We consider both ordinal mechanisms, where agents submit preference lists over the items, and cardinal mechanisms, where agents may submit numerical values for the items being allocated. We present a general lower bound of Ω (√n) on the Price of Anarchy, which applies to all mechanisms. We show that two well-known mechanisms, Probabilistic Serial, and Random Priority, achieve a matching upper bound. We extend our lower bound to the Price of Stability of a large class of mechanisms that satisfy a common proportionality property, and show stronger bounds on the Price of Anarchy of all deterministic mechanisms.

AB - We study the Price of Anarchy of mechanisms for the well-known problem of one-sided matching, or house allocation, with respect to the social welfare objective. We consider both ordinal mechanisms, where agents submit preference lists over the items, and cardinal mechanisms, where agents may submit numerical values for the items being allocated. We present a general lower bound of Ω (√n) on the Price of Anarchy, which applies to all mechanisms. We show that two well-known mechanisms, Probabilistic Serial, and Random Priority, achieve a matching upper bound. We extend our lower bound to the Price of Stability of a large class of mechanisms that satisfy a common proportionality property, and show stronger bounds on the Price of Anarchy of all deterministic mechanisms.

U2 - 10.1007/978-3-319-46882-2_3

DO - 10.1007/978-3-319-46882-2_3

M3 - Chapter in a published conference proceeding

SN - 978-3-319-46881-5

SP - 30

EP - 50

BT - Autonomous Agents and Multiagent Systems

A2 - Osman, N.

A2 - Sierra, C.

PB - Springer, Cham; Fondazione C.I.M.E., Florence

ER -

Social welfare in one-sided matching mechanisms

Abstract

Bibliographical note

Access to Document

Fingerprint

Cite this