Computer Science and Mechanism Design: Two Case Studies

Vincent Conitzer, Duke University

In many settings, a decision must be made based on the preferences of multiple parties (agents). A self-interested agent will misreport her preferences if she believes that this will result in an outcome that she prefers. In mechanism design, the goal is to create a mechanism (that is, rules for choosing the outcome) that does not incentivize such misreporting and still results in good outcomes. The 2007 Nobel Prize in Economics was awarded for fundamental work in mechanism design. In recent years, computer scientists have also become interested in mechanism design, both because computational tools can help in designing mechanisms, and because computer scientists face increasingly many settings with multiple self-interested agents. We will see examples of both in this talk.

First, we consider the design of auctions that redistribute their revenue back to the bidders. It is not possible to redistribute all of the revenue without introducing incentives for misreporting, but we will see how almost everything can be redistributed. We derived optimal (in various senses) redistribution mechanisms by solving various linear programming formulations.

Second, I consider mechanism design in highly anonymous environments such as the Internet, where an agent can participate multiple times (sometimes referred to as a "Sybil attack"). I give a characterization of all voting mechanisms that do not incentivize such behavior. This is mostly a negative result, and I consider a number of ways in which it can be circumvented.

The first part of this talk is joint work with Mingyu Guo.

close this window