Mechanism design for stochastic optimization problems

Samuel Ieong, Mukund Sundararajan, Anthony Man-Cho SoSIGecom Exch 2007 · DOI · OpenReview

Abstract

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.
BibTeX
@article{ieong2007mechanism,
  author = {Samuel Ieong and Mukund Sundararajan and Anthony Man-Cho So},
  title = {{Mechanism design for stochastic optimization problems}},
  journal = {SIGecom Exch.},
  year = {2007},
  doi = {10.1145/1345037.1345050},
}

Loading related content...

Figure