Conference item
Social Welfare in One-Sided Matching Mechanisms.
- Abstract:
- We study the Price of Anarchy of mechanisms for the wellknown 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 ( p 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.*
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 341.8KB, Terms of use)
-
Authors
- Publisher:
- International Foundation for Autonomous Agents and Multiagent Systems
- Host title:
- Proceedings of the 15th International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, May 9–13, 2016, Singapore
- Journal:
- Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS More from this journal
- Volume:
- abs/1502.03849
- Publication date:
- 2016-05-09
- Acceptance date:
- 2016-05-09
- ISBN:
- 9781450342391
- Keywords:
- Pubs id:
-
pubs:578436
- UUID:
-
uuid:028f3950-c608-437c-a9e0-9fe0f5e925b6
- Local pid:
-
pubs:578436
- Source identifiers:
-
578436
- Deposit date:
-
2016-04-04
- ARK identifier:
Terms of use
- Copyright holder:
- © 2016, International Foundation for Autonomous Agents and Multiagent Systems (wwwifaamasorg) All rights reserved
- Copyright date:
- 2016
- Notes:
- Copyright © 2016 by IFAAMAS. Permission to make digital or hard copies of portions of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyright for components of this work owned by others than IFAAMAS must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
If you are the owner of this record, you can report an update to it here: Report update to this record