Mechanism Design with Approximate Valuations
In mechanism design, we replace the strong assumption that each player knows his own payoff type EXACTLY with the more realistic assumption that he knows it only APPROXIMATELY. Specifically, we study the classical problem of maximizing social welfare in single-good auctions when players know their t...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Published: |
2011
|
| Online Access: | http://hdl.handle.net/1721.1/62296 |
| _version_ | 1826215432560836608 |
|---|---|
| author | Chiesa, Alessandro Micali, Silvio Zhu, Zeyuan Allen |
| author2 | Silvio Micali |
| author_facet | Silvio Micali Chiesa, Alessandro Micali, Silvio Zhu, Zeyuan Allen |
| author_sort | Chiesa, Alessandro |
| collection | MIT |
| description | In mechanism design, we replace the strong assumption that each player knows his own payoff type EXACTLY with the more realistic assumption that he knows it only APPROXIMATELY. Specifically, we study the classical problem of maximizing social welfare in single-good auctions when players know their true valuations only within a constant multiplicative factor d in (0,1). Our approach is deliberately non-Bayesian and very conservative: each player i only knows that his true valuation is one among finitely many values in a d-APPROXIMATE SET, Ki, and his true valuation is ADVERSARIALLY and SECRETLY chosen in Ki at the beginning of the auction. We prove tight upper and lower bounds for the fraction of the maximum social welfare achievable in our model, in either dominant or undominated strategies, both via deterministic and probabilistic mechanisms. The landscape emerging is quite unusual and intriguing. |
| first_indexed | 2024-09-23T16:28:45Z |
| id | mit-1721.1/62296 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T16:28:45Z |
| publishDate | 2011 |
| record_format | dspace |
| spelling | mit-1721.1/622962019-04-11T03:51:41Z Mechanism Design with Approximate Valuations Chiesa, Alessandro Micali, Silvio Zhu, Zeyuan Allen Silvio Micali Theory of Computation In mechanism design, we replace the strong assumption that each player knows his own payoff type EXACTLY with the more realistic assumption that he knows it only APPROXIMATELY. Specifically, we study the classical problem of maximizing social welfare in single-good auctions when players know their true valuations only within a constant multiplicative factor d in (0,1). Our approach is deliberately non-Bayesian and very conservative: each player i only knows that his true valuation is one among finitely many values in a d-APPROXIMATE SET, Ki, and his true valuation is ADVERSARIALLY and SECRETLY chosen in Ki at the beginning of the auction. We prove tight upper and lower bounds for the fraction of the maximum social welfare achievable in our model, in either dominant or undominated strategies, both via deterministic and probabilistic mechanisms. The landscape emerging is quite unusual and intriguing. 2011-04-21T18:15:33Z 2011-04-21T18:15:33Z 2011-02-16 http://hdl.handle.net/1721.1/62296 MIT-CSAIL-TR-2011-024 MIT-CSAIL-TR-2011-009 http://hdl.handle.net/1721.1/61008 30 p. application/pdf |
| spellingShingle | Chiesa, Alessandro Micali, Silvio Zhu, Zeyuan Allen Mechanism Design with Approximate Valuations |
| title | Mechanism Design with Approximate Valuations |
| title_full | Mechanism Design with Approximate Valuations |
| title_fullStr | Mechanism Design with Approximate Valuations |
| title_full_unstemmed | Mechanism Design with Approximate Valuations |
| title_short | Mechanism Design with Approximate Valuations |
| title_sort | mechanism design with approximate valuations |
| url | http://hdl.handle.net/1721.1/62296 |
| work_keys_str_mv | AT chiesaalessandro mechanismdesignwithapproximatevaluations AT micalisilvio mechanismdesignwithapproximatevaluations AT zhuzeyuanallen mechanismdesignwithapproximatevaluations |