Social welfare in one-sided matching mechanisms

George Christodoulou; Aris Filos-Ratsikas; Søren Kristoffer Stiil; Paul W. Goldberg; Jie Zhang; Jinshan Zhang

Social welfare in one-sided matching mechanisms

George Christodoulou, Aris Filos-Ratsikas, Søren Kristoffer Stiil, Paul W. Goldberg, Jie Zhang, Jinshan Zhang

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

11 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 and we show that a very well-known mechanisms, Probabilistic Serial achieves 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.

Original language	English
Title of host publication	AAMAS 2016 - Proceedings of the 2016 International Conference on Autonomous Agents and Multiagent Systems
Publisher	International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages	1297-1298
Number of pages	2
ISBN (Electronic)	9781450342391
Publication status	Published - 2016
Event	15th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2016 - Singapore, Singapore Duration: 9 May 2016 → 13 May 2016

Publication series

Name	Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
ISSN (Print)	1548-8403
ISSN (Electronic)	1558-2914

Conference

Conference	15th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2016
Country/Territory	Singapore
City	Singapore
Period	9/05/16 → 13/05/16

Funding

G. Christodoulou, P.W. Goldberg and Jinshan Zhang were supported by the EPSRC grant EP/K01000X/1. P.W. Goldberg was supported by COST Action IC1205. A. Filos-Ratsikas and Jie Zhang were supported by the ERC Advanced Grant 321171 (ALGAME). A. Filos-Ratsikas and S.K.S. Frederiksen acknowledge support from the Danish National Research Foundation and The National Science Foundation of China (under the grant 61061130540) for the Sino-Danish Center for the Theory of Interactive Computation, within which part of this work was performed and support from the Center for Research in Foundations of Electronic Markets (CFEM), supported by the Danish Strategic Research Council. The authors would like to thank Piotr Krysta for useful discussion.

Funders	Funder number
Center for Research in Foundations of Electronic Markets
Danish Strategic Research Council
Sino-Danish Center for the Theory of Interactive Computation
Engineering and Physical Sciences Research Council	EP/K01000X/1
European Research Council	321171
COST Association	IC1205
Danmarks Grundforskningsfond
National Natural Science Foundation of China	61061130540

Keywords

Nash equilibrium
One-sided matching
Price of anarchy
Probabilistic serial
Truthfulness

ASJC Scopus subject areas

Artificial Intelligence
Software
Control and Systems Engineering

Cite this

Christodoulou, G., Filos-Ratsikas, A., Stiil, S. K., Goldberg, P. W., Zhang, J., & Zhang, J. (2016). Social welfare in one-sided matching mechanisms. In AAMAS 2016 - Proceedings of the 2016 International Conference on Autonomous Agents and Multiagent Systems (pp. 1297-1298). (Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS). International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).

Social welfare in one-sided matching mechanisms. / Christodoulou, George; Filos-Ratsikas, Aris; Stiil, Søren Kristoffer et al.
AAMAS 2016 - Proceedings of the 2016 International Conference on Autonomous Agents and Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2016. p. 1297-1298 (Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS).

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

Christodoulou, G, Filos-Ratsikas, A, Stiil, SK, Goldberg, PW, Zhang, J & Zhang, J 2016, Social welfare in one-sided matching mechanisms. in AAMAS 2016 - Proceedings of the 2016 International Conference on Autonomous Agents and Multiagent Systems. Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), pp. 1297-1298, 15th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2016, Singapore, Singapore, 9/05/16.

Christodoulou G, Filos-Ratsikas A, Stiil SK, Goldberg PW, Zhang J, Zhang J. Social welfare in one-sided matching mechanisms. In AAMAS 2016 - Proceedings of the 2016 International Conference on Autonomous Agents and Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS). 2016. p. 1297-1298. (Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS).

Christodoulou, George ; Filos-Ratsikas, Aris ; Stiil, Søren Kristoffer et al. / Social welfare in one-sided matching mechanisms. AAMAS 2016 - Proceedings of the 2016 International Conference on Autonomous Agents and Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2016. pp. 1297-1298 (Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS).

@inproceedings{a2233444629e44489845995a38010d7d,

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 and we show that a very well-known mechanisms, Probabilistic Serial achieves 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.",

keywords = "Nash equilibrium, One-sided matching, Price of anarchy, Probabilistic serial, Truthfulness",

author = "George Christodoulou and Aris Filos-Ratsikas and Stiil, {S{\o}ren Kristoffer} and Goldberg, {Paul W.} and Jie Zhang and Jinshan Zhang",

year = "2016",

language = "English",

series = "Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS",

publisher = "International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)",

pages = "1297--1298",

booktitle = "AAMAS 2016 - Proceedings of the 2016 International Conference on Autonomous Agents and Multiagent Systems",

note = "15th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2016 ; Conference date: 09-05-2016 Through 13-05-2016",

}

TY - GEN

T1 - Social welfare in one-sided matching mechanisms

AU - Christodoulou, George

AU - Filos-Ratsikas, Aris

AU - Stiil, Søren Kristoffer

AU - Goldberg, Paul W.

AU - Zhang, Jie

AU - Zhang, Jinshan

PY - 2016

Y1 - 2016

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 and we show that a very well-known mechanisms, Probabilistic Serial achieves 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.

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 and we show that a very well-known mechanisms, Probabilistic Serial achieves 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.

KW - Nash equilibrium

KW - One-sided matching

KW - Price of anarchy

KW - Probabilistic serial

KW - Truthfulness

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

M3 - Chapter in a published conference proceeding

AN - SCOPUS:85014291964

T3 - Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS

SP - 1297

EP - 1298

BT - AAMAS 2016 - Proceedings of the 2016 International Conference on Autonomous Agents and Multiagent Systems

PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)

T2 - 15th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2016

Y2 - 9 May 2016 through 13 May 2016

ER -

Social welfare in one-sided matching mechanisms

Abstract

Publication series

Conference

Funding

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this