False-name-proofness in voting, and limited verification of identities
Time:November 26, 2007, 1pm - 2pm
Place:D344, LSRC
Speaker:Vincent Conitzer

In mechanism design, we study how to make a decision based on the preferences of multiple parties (agents), when each agent will report her preferences strategically to maximize her own utility. Traditionally, mechanism design has focused on strategy-proofness, that is, no agent should ever have an incentive to declare preferences other than her true ones. However, in anonymous environments such as the Internet, misreporting one's preferences is not the only possible manipulation: another manipulation is to pretend to be multiple agents and submit multiple preferences. We will illustrate this with some amusing examples. A mechanism is false-name-proof if no agent can benefit from using multiple identifiers (e.g. e-mail addresses). We show that the best false-name-proof voting rule satisfying voluntary participation is to draw two alternatives at random; if all votes prefer the same one, choose that one, otherwise flip a coin. To address this and other impossibility results, we show how to verify the identities of some agents so that the mechanism and the verification protocol together are false-name-proof. We will use combinatorial auctions as an illustrative example for this.