Computationally Feasible Approaches to Automated Mechanism Design

dc.contributor.advisor

Conitzer, Vincent

dc.contributor.author

Guo, Mingyu

dc.date.accessioned

2011-01-05T14:40:20Z

dc.date.available

2011-01-05T14:40:20Z

dc.date.issued

2010

dc.department

Computer Science

dc.description.abstract

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.

dc.identifier.uri

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

dc.subject

Computer Science

dc.subject

Economics, Theory

dc.subject

automated mechanism design

dc.subject

false-name-proofness

dc.subject

mechanism design without payments

dc.subject

VCG redistribution mechanism

dc.title

Computationally Feasible Approaches to Automated Mechanism Design

dc.type

Dissertation

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
D_Guo_Mingyu_a_2010.pdf
Size:
1.29 MB
Format:
Adobe Portable Document Format

Collections