Marriage, Honesty, and Stability
Many centralized two-sided markets form a matching between participantsby running a stable marriage algorithm. It is a well-knownfact that no matching mechanism based on a stable marriage algorithmcan guarantee truthfulness as a dominant strategy for participants.However, as we will show in this pap...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Language: | en_US |
| Published: |
2005
|
| Online Access: | http://hdl.handle.net/1721.1/30405 |
| _version_ | 1811075770215301120 |
|---|---|
| author | Immorlica, Nicole Mahdian, Mohammad |
| author2 | Theory of Computation |
| author_facet | Theory of Computation Immorlica, Nicole Mahdian, Mohammad |
| author_sort | Immorlica, Nicole |
| collection | MIT |
| description | Many centralized two-sided markets form a matching between participantsby running a stable marriage algorithm. It is a well-knownfact that no matching mechanism based on a stable marriage algorithmcan guarantee truthfulness as a dominant strategy for participants.However, as we will show in this paper, in a probabilisticsetting where the preference lists of one side of the market are composedof only a constant (independent of the the size of the market)number of entries, each drawn from an arbitrary distribution, thenumber of participants that have more than one stable partner is vanishinglysmall. This proves (and generalizes) a conjecture of Rothand Peranson [23]. As a corollary of this result, we show that, withhigh probability, the truthful strategy is the best response for a givenplayer when the other players are truthful. We also analyze equilibriaof the deferred acceptance stable marriage game. We show thatthe game with complete information has an equilibrium in which a(1?o(1)) fraction of the strategies are truthful in expectation. In themore realistic setting of a game of incomplete information, we willshow that the set of truthful strategies form a (1+o(1))-approximateBayesian-Nash equilibrium. Our results have implications in manypractical settings and were inspired by the work of Roth and Peranson[23] on the National Residency Matching Program. |
| first_indexed | 2024-09-23T10:11:36Z |
| id | mit-1721.1/30405 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:11:36Z |
| publishDate | 2005 |
| record_format | dspace |
| spelling | mit-1721.1/304052019-04-12T13:39:25Z Marriage, Honesty, and Stability Immorlica, Nicole Mahdian, Mohammad Theory of Computation Many centralized two-sided markets form a matching between participantsby running a stable marriage algorithm. It is a well-knownfact that no matching mechanism based on a stable marriage algorithmcan guarantee truthfulness as a dominant strategy for participants.However, as we will show in this paper, in a probabilisticsetting where the preference lists of one side of the market are composedof only a constant (independent of the the size of the market)number of entries, each drawn from an arbitrary distribution, thenumber of participants that have more than one stable partner is vanishinglysmall. This proves (and generalizes) a conjecture of Rothand Peranson [23]. As a corollary of this result, we show that, withhigh probability, the truthful strategy is the best response for a givenplayer when the other players are truthful. We also analyze equilibriaof the deferred acceptance stable marriage game. We show thatthe game with complete information has an equilibrium in which a(1?o(1)) fraction of the strategies are truthful in expectation. In themore realistic setting of a game of incomplete information, we willshow that the set of truthful strategies form a (1+o(1))-approximateBayesian-Nash equilibrium. Our results have implications in manypractical settings and were inspired by the work of Roth and Peranson[23] on the National Residency Matching Program. 2005-12-19T22:49:33Z 2005-12-19T22:49:33Z 2003-07-28 MIT-CSAIL-TR-2003-007 MIT-LCS-TR-913 http://hdl.handle.net/1721.1/30405 en_US Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory 12 p. 22012898 bytes 874678 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | Immorlica, Nicole Mahdian, Mohammad Marriage, Honesty, and Stability |
| title | Marriage, Honesty, and Stability |
| title_full | Marriage, Honesty, and Stability |
| title_fullStr | Marriage, Honesty, and Stability |
| title_full_unstemmed | Marriage, Honesty, and Stability |
| title_short | Marriage, Honesty, and Stability |
| title_sort | marriage honesty and stability |
| url | http://hdl.handle.net/1721.1/30405 |
| work_keys_str_mv | AT immorlicanicole marriagehonestyandstability AT mahdianmohammad marriagehonestyandstability |