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.)