| dc.contributor |
Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
|
| dc.contributor |
Cai, Yang |
|
| dc.contributor |
Daskalakis, Konstantinos |
|
| dc.contributor |
Weinberg, Seth Matthew |
|
| dc.creator |
Cai, Yang |
|
| dc.creator |
Daskalakis, Konstantinos |
|
| dc.creator |
Weinberg, Seth Matthew |
|
| dc.date |
2015-11-20T18:32:58Z |
|
| dc.date |
2015-11-20T18:32:58Z |
|
| dc.date |
2013-10 |
|
| dc.date.accessioned |
2023-03-01T18:06:59Z |
|
| dc.date.available |
2023-03-01T18:06:59Z |
|
| dc.identifier |
978-0-7695-5135-7 |
|
| dc.identifier |
0272-5428 |
|
| dc.identifier |
http://hdl.handle.net/1721.1/99969 |
|
| dc.identifier |
Cai, Yang, Constantinos Daskalakis, and S. Matthew Weinberg. “Understanding Incentives: Mechanism Design Becomes Algorithm Design.” 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (October 2013). |
|
| dc.identifier |
https://orcid.org/0000-0002-5451-0490 |
|
| dc.identifier.uri |
http://localhost:8080/xmlui/handle/CUHPOERS/278806 |
|
| dc.description |
We provide a computationally efficient black-box reduction from mechanism design to algorithm design in very general settings. Specifically, we give an approximation-preserving reduction from truthfully maximizing any objective under arbitrary feasibility constraints with arbitrary bidder types to (not necessarily truthfully) maximizing the same objective plus virtual welfare (under the same feasibility constraints). Our reduction is based on a fundamentally new approach: we describe a mechanism's behavior indirectly only in terms of the expected value it awards bidders for certain behavior, and never directly access the allocation rule at all. Applying our new approach to revenue, we exhibit settings where our reduction holds both ways. That is, we also provide an approximation-sensitive reduction from (non-truthfully) maximizing virtual welfare to (truthfully) maximizing revenue, and therefore the two problems are computationally equivalent. With this equivalence in hand, we show that both problems are NP-hard to approximate within any polynomial factor, even for a single monotone sub modular bidder. We further demonstrate the applicability of our reduction by providing a truthful mechanism maximizing fractional max-min fairness. |
|
| dc.description |
National Science Foundation (U.S.) (CAREER Award CCF-0953960) |
|
| dc.description |
National Science Foundation (U.S.) (Award CCF-1101491) |
|
| dc.description |
Alfred P. Sloan Foundation (Fellowship) |
|
| dc.description |
Microsoft Research (Faculty Fellowship) |
|
| dc.description |
National Science Foundation (U.S.). Graduate Research Fellowship |
|
| dc.format |
application/pdf |
|
| dc.language |
en_US |
|
| dc.publisher |
Institute of Electrical and Electronics Engineers (IEEE) |
|
| dc.relation |
http://dx.doi.org/10.1109/FOCS.2013.72 |
|
| dc.relation |
Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science |
|
| dc.rights |
Creative Commons Attribution-Noncommercial-Share Alike |
|
| dc.rights |
http://creativecommons.org/licenses/by-nc-sa/4.0/ |
|
| dc.source |
arXiv |
|
| dc.title |
Understanding Incentives: Mechanism Design Becomes Algorithm Design |
|
| dc.type |
Article |
|
| dc.type |
http://purl.org/eprint/type/ConferencePaper |
|