Collusive Dominant-Strategy Truthfulness
Fifty years ago, Vickrey published his famous mechanism for auctioning a single good in limited supply. The main property of Vickrey's mechanism is efficiency in dominant strategies. In absence of collusion, this is a wonderful efficiency guarantee. We note, however, that collusion is far from...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Published: |
2011
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/62301 |
| _version_ | 1826197893110824960 |
|---|---|
| author | Chen, Jinc Micali, Silvio |
| author2 | Silvio Micali |
| author_facet | Silvio Micali Chen, Jinc Micali, Silvio |
| author_sort | Chen, Jinc |
| collection | MIT |
| description | Fifty years ago, Vickrey published his famous mechanism for auctioning a single good in limited supply. The main property of Vickrey's mechanism is efficiency in dominant strategies. In absence of collusion, this is a wonderful efficiency guarantee. We note, however, that collusion is far from rare in auctions, and if some colluders exist and have some wrong beliefs, then the Vickrey mechanism dramatically loses its efficiency. Accordingly, we put forward a new mechanism that, despite unconstrained collusion, guarantees efficiency by providing a richer set of strategies and ensuring that it is dominant for every player to reveal truthfully not only his own valuation, but also with whom he is colluding, if he is indeed colluding with someone else. Our approach meaningfully bypasses prior impossibility proofs. |
| first_indexed | 2024-09-23T10:55:15Z |
| id | mit-1721.1/62301 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T10:55:15Z |
| publishDate | 2011 |
| record_format | dspace |
| spelling | mit-1721.1/623012019-04-10T13:39:59Z Collusive Dominant-Strategy Truthfulness Chen, Jinc Micali, Silvio Silvio Micali Theory of Computation Collusion Auctions Efficiency Fifty years ago, Vickrey published his famous mechanism for auctioning a single good in limited supply. The main property of Vickrey's mechanism is efficiency in dominant strategies. In absence of collusion, this is a wonderful efficiency guarantee. We note, however, that collusion is far from rare in auctions, and if some colluders exist and have some wrong beliefs, then the Vickrey mechanism dramatically loses its efficiency. Accordingly, we put forward a new mechanism that, despite unconstrained collusion, guarantees efficiency by providing a richer set of strategies and ensuring that it is dominant for every player to reveal truthfully not only his own valuation, but also with whom he is colluding, if he is indeed colluding with someone else. Our approach meaningfully bypasses prior impossibility proofs. 2011-04-22T18:45:10Z 2011-04-22T18:45:10Z 2011-04-22 http://hdl.handle.net/1721.1/62301 MIT-CSAIL-TR-2011-025 10 p. application/pdf |
| spellingShingle | Collusion Auctions Efficiency Chen, Jinc Micali, Silvio Collusive Dominant-Strategy Truthfulness |
| title | Collusive Dominant-Strategy Truthfulness |
| title_full | Collusive Dominant-Strategy Truthfulness |
| title_fullStr | Collusive Dominant-Strategy Truthfulness |
| title_full_unstemmed | Collusive Dominant-Strategy Truthfulness |
| title_short | Collusive Dominant-Strategy Truthfulness |
| title_sort | collusive dominant strategy truthfulness |
| topic | Collusion Auctions Efficiency |
| url | http://hdl.handle.net/1721.1/62301 |
| work_keys_str_mv | AT chenjinc collusivedominantstrategytruthfulness AT micalisilvio collusivedominantstrategytruthfulness |