Resilient and Equilibrium-Less Mechanism Design

COMPUTER SCIENCE/DISCRETE MATH II
Topic:Resilient and Equilibrium-Less Mechanism Design
Speaker:Silvio Micali and Paul Valiant
Affiliation:Massachusetts Institute of Technology
Date:Tuesday, January 20
Time/Room:10:30am - 12:30pm/S-101

Mechanism design is not robust. It traditionally guarantees a desired property "at equilibrium", but an equilibrium is by definition very fragile: it only guarantees that no INDIVIDUAL player can profitably deviate from his envisaged strategy. Two or more players, however, may have a lot to gain by coordinating their deviating strategies. Thus, typical mechanisms (e.g., the VCG) are totally vulnerable to PLAYER COLLUSION. We advocate designing mechanisms in a new and RESILIENT way, yielding games that are invulnerable to, or even take advantage of, player collusion. We exemplify our notions and techniques for guaranteeing revenue in UNRESTRICTED combinatorial auctions, a problem about which very little was previously known, even in a non-collusive setting. (Partly based on work with Jing Chen.)