High Welfare Matching Markets via Descending Price
We consider design of monetary mechanisms for two-sided matching. Mechanisms in the tradition of the deferred acceptance algorithm, even in variants incorporating money, tend to focus on the criterion of stability. Instead, in this work we seek a simple auction-inspired mechanism with social welfare...
Guardat en:
| Autors principals: | , |
|---|---|
| Format: | Article |
| Publicat: |
2022
|
| Matèries: | |
| Accés en línia: | https://arxiv.org/abs/2203.02023 http://arxiv.org/abs/2203.02023 |
| Etiquetes: |
Sense etiquetes, Sigues el primer a etiquetar aquest registre!
|
| _version_ | 1879177265264197632 |
|---|---|
| author | Bowers, Robin Waggoner, Bo |
| author_browse | Bowers, Robin Waggoner, Bo |
| author_facet | Bowers, Robin Waggoner, Bo |
| author_sort | Bowers, Robin |
| building | arXiv |
| collection | Acceso abierto |
| description | We consider design of monetary mechanisms for two-sided matching. Mechanisms in the tradition of the deferred acceptance algorithm, even in variants incorporating money, tend to focus on the criterion of stability. Instead, in this work we seek a simple auction-inspired mechanism with social welfare guarantees. We consider a descending-price mechanism called the Marshallian Match, proposed (but not analyzed) by Waggoner and Weyl (2019). When all values for potential matches are positive, we show the Marshallian Match with a "rebate" payment rule achieves constant price of anarchy. This result extends to models with costs for acquiring information about one's values, and also to matching on hypergraphs. With possibly-negative valuations, which capture e.g. job markets, the problem becomes harder. We introduce notions of approximate stability and show that they have beneficial welfare implications. However, the main problem of proving constant factor welfare guarantees in "ex ante stable equilibrium" remains open. |
| doi_str_mv | 10.1007/978-3-031-48974-7_4 |
| first_indexed | 2026-10-16T00:58:03Z |
| format | Article |
| fullrecord | <oai_dc:dc xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/ https://www.openarchives.org/OAI/2.0/oai_dc.xsd"><identifier>arxiv-2203.02023</identifier><datestamp>2025-06-30</datestamp>
<dc:title>High Welfare Matching Markets via Descending Price</dc:title>
<dc:creator>Bowers, Robin</dc:creator>
<dc:creator>Waggoner, Bo</dc:creator>
<dc:subject>Computer Science and Game Theory</dc:subject>
<dc:description>We consider design of monetary mechanisms for two-sided matching. Mechanisms in the tradition of the deferred acceptance algorithm, even in variants incorporating money, tend to focus on the criterion of stability. Instead, in this work we seek a simple auction-inspired mechanism with social welfare guarantees. We consider a descending-price mechanism called the Marshallian Match, proposed (but not analyzed) by Waggoner and Weyl (2019). When all values for potential matches are positive, we show the Marshallian Match with a "rebate" payment rule achieves constant price of anarchy. This result extends to models with costs for acquiring information about one's values, and also to matching on hypergraphs. With possibly-negative valuations, which capture e.g. job markets, the problem becomes harder. We introduce notions of approximate stability and show that they have beneficial welfare implications. However, the main problem of proving constant factor welfare guarantees in "ex ante stable equilibrium" remains open. </dc:description>
<dc:date>2022-03-03</dc:date>
<dc:date>2022-04-28</dc:date>
<dc:type>text</dc:type>
<dc:identifier>https://arxiv.org/abs/2203.02023</dc:identifier>
<dc:identifier>http://arxiv.org/abs/2203.02023</dc:identifier>
<dc:identifier>doi:10.1007/978-3-031-48974-7_4</dc:identifier>
</oai_dc:dc> |
| id | arxiv-2203.02023 |
| institution | arXiv |
| last_indexed | 2026-10-16T00:58:03Z |
| publishDate | 2022 |
| publishDateRange | 2022 |
| publishDateSort | 2022 |
| record_format | oai_dc |
| spelling | arxiv-2203.020232025-06-30 High Welfare Matching Markets via Descending Price Bowers, Robin Waggoner, Bo Computer Science and Game Theory We consider design of monetary mechanisms for two-sided matching. Mechanisms in the tradition of the deferred acceptance algorithm, even in variants incorporating money, tend to focus on the criterion of stability. Instead, in this work we seek a simple auction-inspired mechanism with social welfare guarantees. We consider a descending-price mechanism called the Marshallian Match, proposed (but not analyzed) by Waggoner and Weyl (2019). When all values for potential matches are positive, we show the Marshallian Match with a "rebate" payment rule achieves constant price of anarchy. This result extends to models with costs for acquiring information about one's values, and also to matching on hypergraphs. With possibly-negative valuations, which capture e.g. job markets, the problem becomes harder. We introduce notions of approximate stability and show that they have beneficial welfare implications. However, the main problem of proving constant factor welfare guarantees in "ex ante stable equilibrium" remains open. 2022-03-03 2022-04-28 text https://arxiv.org/abs/2203.02023 http://arxiv.org/abs/2203.02023 doi:10.1007/978-3-031-48974-7_4 |
| spellingShingle | Computer Science and Game Theory Bowers, Robin Waggoner, Bo High Welfare Matching Markets via Descending Price |
| title | High Welfare Matching Markets via Descending Price |
| title_full | High Welfare Matching Markets via Descending Price |
| title_fullStr | High Welfare Matching Markets via Descending Price |
| title_full_unstemmed | High Welfare Matching Markets via Descending Price |
| title_short | High Welfare Matching Markets via Descending Price |
| title_sort | high welfare matching markets via descending price |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2203.02023 http://arxiv.org/abs/2203.02023 |
| work_keys_str_mv | AT bowersrobin highwelfarematchingmarketsviadescendingprice AT waggonerbo highwelfarematchingmarketsviadescendingprice |