Resilient and Equilibrium-less Mechanism Design
Silvio Micali
MIT, Department of Electrical Engineering and Computer Science
Abstract:
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.)