Social welfare in one-sided matching mechanisms
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 n...
| Main Authors: | , , , , |
|---|---|
| Format: | Conference item |
| Published: |
Association for Computing Machinery
2016
|
| _version_ | 1826266440555036672 |
|---|---|
| author | Christodoulou, G Filos-Ratsikas, A Frederiksen, S Goldberg, P Zhang, J Zhang, J |
| author_facet | Christodoulou, G Filos-Ratsikas, A Frederiksen, S Goldberg, P Zhang, J Zhang, J |
| author_sort | Christodoulou, G |
| collection | OXFORD |
| description | 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 Ω(√ 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. |
| first_indexed | 2024-03-06T20:39:00Z |
| format | Conference item |
| id | oxford-uuid:339ea1a0-dc4f-4a44-9a0f-f95bfc6bdf19 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T20:39:00Z |
| publishDate | 2016 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:339ea1a0-dc4f-4a44-9a0f-f95bfc6bdf192022-03-26T13:21:13ZSocial welfare in one-sided matching mechanismsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:339ea1a0-dc4f-4a44-9a0f-f95bfc6bdf19Symplectic Elements at OxfordAssociation for Computing Machinery2016Christodoulou, GFilos-Ratsikas, AFrederiksen, SGoldberg, PZhang, JZhang, JWe 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 Ω(√ 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. |
| spellingShingle | Christodoulou, G Filos-Ratsikas, A Frederiksen, S Goldberg, P Zhang, J Zhang, J Social welfare in one-sided matching mechanisms |
| title | Social welfare in one-sided matching mechanisms |
| title_full | Social welfare in one-sided matching mechanisms |
| title_fullStr | Social welfare in one-sided matching mechanisms |
| title_full_unstemmed | Social welfare in one-sided matching mechanisms |
| title_short | Social welfare in one-sided matching mechanisms |
| title_sort | social welfare in one sided matching mechanisms |
| work_keys_str_mv | AT christodouloug socialwelfareinonesidedmatchingmechanisms AT filosratsikasa socialwelfareinonesidedmatchingmechanisms AT frederiksens socialwelfareinonesidedmatchingmechanisms AT goldbergp socialwelfareinonesidedmatchingmechanisms AT zhangj socialwelfareinonesidedmatchingmechanisms AT zhangj socialwelfareinonesidedmatchingmechanisms |