Mechanism design for stochastic optimization problems

✍ Scribed by Ieong, Samuel; Sundararajan, Mukund; So, Anthony Man-Cho

• Book ID: 125835461
• Publisher: Association for Computing Machinery
• Year: 2007
• Weight: 125 KB
• Volume: 7
• Category: Article
• ISSN: 1551-9031
• DOI: 10.1145/1345037.1345050

✦ Synopsis

We identify and address algorithmic and game-theoretic issues arising from welfare maximization in the well-studied two-stage stochastic optimization framework. In contrast, prior work in algorithmic mechanism design has focused almost exclusively on optimization problems without uncertainty. We show both positive results, by demonstrating a mechanism that implements the social welfare maximizer in sequential ex post equilibrium, and also negative results, by showing the impossibility of dominant-strategy implementation. In this letter, we describe the relationship between mechanism design and stochastic optimization, and highlight our key technical results. An extended abstract will appear in WINE 2007, and a journal version is under preparation.