Computer Science and Mechanism Design: Two Case Studies

Speaker: Vincent Conitzer
Date: Wednesday, 12 March 2008
Time: 1pm
Place: Ross 201

Abstract:

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.

Bio: Vincent Conitzer is an Assistant Professor of Computer Science
and Economics at Duke University.  He received Ph.D. (2006) and M.S.
(2003) degrees in Computer Science from Carnegie Mellon University,
and an A.B. (2001) degree in Applied Mathematics from Harvard
University.  He also received an Alfred P. Sloan Research Fellowship
(2008), the IFAAMAS Victor Lesser Distinguished Dissertation Award
(2007), the AAMAS Best Program Committee Member Award (2006), and an
IBM Ph.D. Fellowship (2005).  He has co-authored over 50 technical
papers on computational issues in game theory, mechanism design,
auctions, elections, and other negotiation settings.