Computer Science/Discrete Mathematics Seminar II

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