Computationally Feasible Approaches to Automated Mechanism Design

<p>In many multiagent settings, a decision must be made based on the preferences of multiple agents, and agents may lie about their preferences if this is to their benefit. In mechanism design, the goal is to design procedures (mechanisms) for making the decision that work in spite of such strategic behavior, usually by making untruthful behavior suboptimal. In automated mechanism design, the idea is to computationally search through the space of feasible mechanisms, rather than to design them analytically by hand. Unfortunately, the most straightforward approach to automated mechanism design does not scale to large instances, because it requires searching over a very large space of possible functions. In this thesis, we adopt an approach to automated mechanism design that is computationally feasible. Instead of optimizing over all feasible mechanisms, we carefully choose a parameterized subfamily of mechanisms. Then we optimize over mechanisms within this family. Finally, we analyze whether and to what extent the resulting mechanism is suboptimal outside the subfamily. We apply (computationally feasible) automated mechanism design to three resource allocation mechanism design problems: mechanisms that redistribute revenue, mechanisms that involve no payments at all, and mechanisms that guard against false-name manipulation.</p>

Author dc:creator

• Guo, Mingyu

Advisor dc:contributor.advisor

• Conitzer, Vincent

• Computer Science
• Economics, Theory
• automated mechanism design
• false-name-proofness
• mechanism design without payments
• VCG redistribution mechanism

Handle dc:identifier.uri

https://hdl.handle.net/10161/3015

OAI identifier oai:identifier

oai:dukespace.lib.duke.edu:10161/3015