computer-aided mechanism design

Algorithmic mechanism design, as practised today, is a manual process; however, manual design and reasoning do not scale well with the complexity of design tasks. In this thesis, we study computer-aided mechanism design as an alternative to manual construction and analysis of mechanisms. In our approach, a mechanism is a program that receives inputs from agents with private preferences, and produces a public output. Rather than programming such a mechanism manually, the human designer writes a high-level partial specification that includes behavioral models of agents and a set of logical correctness requirements (for example, truth-telling) on the desired mechanism. A program synthesis algorithm is now used to automatically search a large space of candidate mechanisms and find one that satis es the requirements. The algorithm is based on a reduction to automated rst-order logic theorem proving | speci cally, deciding the satis ability of quanti er-free formulas in the rst-order theory of reals. We present an implementation of our synthesis approach on top of a Satis ability Modulo Theories solver. The system is evaluated through several case studies where we automatically synthesize a set of classic mechanisms and their variations, including the Vickrey auction, a multistage auction, a position auction, and a voting mechanism.

Name thesis:degree_name

Master of Science

Level thesis:degree_level

Masters

Discipline thesis:degree_discipline

Engineering

Grantor

Rice University

Year dc:date.issued

2015

Author dc:creator

• Fang, Ye

Advisor dc:contributor.advisor

• Chaudhuri, Swarat

Committee members dc:contributor.committeemember

• Vardi, Moshi
• Nakhleh, Luay K.
• Jermaine, Christopher M.

• program synthesis
• economic mechanism design
• game theory

Statement dc:rights

• Copyright is held by the author, unless otherwise indicated. Permission to reuse, publish, or reproduce the work beyond the bounds of fair use or other exemptions to copyright law must be obtained from the copyright holder.

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1911/87798

OAI identifier oai:identifier

oai:repository.rice.edu:1911/87798