Understanding Incentives: Mechanism Design Becomes Algorithm Design
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 (...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2015
|
| Online Access: | http://hdl.handle.net/1721.1/99969 https://orcid.org/0000-0002-5451-0490 |
| _version_ | 1811069711947923456 |
|---|---|
| author | Cai, Yang Daskalakis, Konstantinos Weinberg, Seth Matthew |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Cai, Yang Daskalakis, Konstantinos Weinberg, Seth Matthew |
| author_sort | Cai, Yang |
| collection | MIT |
| 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. |
| first_indexed | 2024-09-23T08:14:43Z |
| format | Article |
| id | mit-1721.1/99969 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:14:43Z |
| publishDate | 2015 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/999692022-09-23T11:51:54Z Understanding Incentives: Mechanism Design Becomes Algorithm Design Cai, Yang Daskalakis, Konstantinos Weinberg, Seth Matthew Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Cai, Yang Daskalakis, Konstantinos Weinberg, Seth Matthew 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. National Science Foundation (U.S.) (CAREER Award CCF-0953960) National Science Foundation (U.S.) (Award CCF-1101491) Alfred P. Sloan Foundation (Fellowship) Microsoft Research (Faculty Fellowship) National Science Foundation (U.S.). Graduate Research Fellowship 2015-11-20T18:32:58Z 2015-11-20T18:32:58Z 2013-10 Article http://purl.org/eprint/type/ConferencePaper 978-0-7695-5135-7 0272-5428 http://hdl.handle.net/1721.1/99969 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). https://orcid.org/0000-0002-5451-0490 en_US http://dx.doi.org/10.1109/FOCS.2013.72 Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Cai, Yang Daskalakis, Konstantinos Weinberg, Seth Matthew Understanding Incentives: Mechanism Design Becomes Algorithm Design |
| title | Understanding Incentives: Mechanism Design Becomes Algorithm Design |
| title_full | Understanding Incentives: Mechanism Design Becomes Algorithm Design |
| title_fullStr | Understanding Incentives: Mechanism Design Becomes Algorithm Design |
| title_full_unstemmed | Understanding Incentives: Mechanism Design Becomes Algorithm Design |
| title_short | Understanding Incentives: Mechanism Design Becomes Algorithm Design |
| title_sort | understanding incentives mechanism design becomes algorithm design |
| url | http://hdl.handle.net/1721.1/99969 https://orcid.org/0000-0002-5451-0490 |
| work_keys_str_mv | AT caiyang understandingincentivesmechanismdesignbecomesalgorithmdesign AT daskalakiskonstantinos understandingincentivesmechanismdesignbecomesalgorithmdesign AT weinbergsethmatthew understandingincentivesmechanismdesignbecomesalgorithmdesign |