Resilient and Equilibrium-less Mechanism Design



Silvio Micali
MIT, Department of Electrical Engineering and Computer Science

Monday  January 26, 2009
4:00 PM, 5130 Upson Hall



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 invulnerable to any reasonable model of 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.

(Based on work with Paul Valiant, and on work with Jing Chen.)