Matching with couples revisited
It is well known that a stable matching in a many-to-one matching market with couples need not exist. We introduce a new matching algorithm for such markets and show that for large random markets the algorithm will find a stable matching with high probability. In our model we allow the number of cou...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2014
|
| Online Access: | http://hdl.handle.net/1721.1/87606 https://orcid.org/0000-0003-2124-738X |
| _version_ | 1826200427243241472 |
|---|---|
| author | Ashlagi, Itai Braverman, Mark Hassidim, Avinatan |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Ashlagi, Itai Braverman, Mark Hassidim, Avinatan |
| author_sort | Ashlagi, Itai |
| collection | MIT |
| description | It is well known that a stable matching in a many-to-one matching market with couples need not exist. We introduce a new matching algorithm for such markets and show that for large random markets the algorithm will find a stable matching with high probability. In our model we allow the number of couples to grow at a near-linear rate. Furthermore, truth-telling is an approximated equilibrium in the game induced by the new matching algorithm. Our results are tight: for markets in which the number of couples grows at a linear rate, we show that with constant probability no stable matching exists. |
| first_indexed | 2024-09-23T11:36:18Z |
| format | Article |
| id | mit-1721.1/87606 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:36:18Z |
| publishDate | 2014 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | mit-1721.1/876062022-10-01T04:44:35Z Matching with couples revisited Ashlagi, Itai Braverman, Mark Hassidim, Avinatan Sloan School of Management Ashlagi, Itai It is well known that a stable matching in a many-to-one matching market with couples need not exist. We introduce a new matching algorithm for such markets and show that for large random markets the algorithm will find a stable matching with high probability. In our model we allow the number of couples to grow at a near-linear rate. Furthermore, truth-telling is an approximated equilibrium in the game induced by the new matching algorithm. Our results are tight: for markets in which the number of couples grows at a linear rate, we show that with constant probability no stable matching exists. 2014-06-02T17:22:51Z 2014-06-02T17:22:51Z 2011-06 2010-10 Article http://purl.org/eprint/type/ConferencePaper 9781450302616 1544-5372 1544-5380 http://hdl.handle.net/1721.1/87606 Ashlagi, Itai, Mark Braverman, and Avinatan Hassidim. “Matching with Couples Revisited. [Extended Abstract]” Proceedings of the 12th ACM Conference on Electronic Commerce - EC ’11 (2011), June 5-9, 2011, San Jose, California, USA. https://orcid.org/0000-0003-2124-738X en_US http://dx.doi.org/10.1145/1993574.1993628 Proceedings of the 12th ACM conference on Electronic Commerce - EC '11 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery Other univ. web domain |
| spellingShingle | Ashlagi, Itai Braverman, Mark Hassidim, Avinatan Matching with couples revisited |
| title | Matching with couples revisited |
| title_full | Matching with couples revisited |
| title_fullStr | Matching with couples revisited |
| title_full_unstemmed | Matching with couples revisited |
| title_short | Matching with couples revisited |
| title_sort | matching with couples revisited |
| url | http://hdl.handle.net/1721.1/87606 https://orcid.org/0000-0003-2124-738X |
| work_keys_str_mv | AT ashlagiitai matchingwithcouplesrevisited AT bravermanmark matchingwithcouplesrevisited AT hassidimavinatan matchingwithcouplesrevisited |