skip to main content
article

Mechanism design for stochastic optimization problems

Published: 01 December 2007 Publication History

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.

References

[1]
BERGEMANN, D. AND VÄLIMÄKI, J. 2006. Efficient dynamic auctions. Working paper.
[2]
CAVALLO, R., PARKES, D. C., AND SINGH, S. 2006. Optimal coordinated planning amongst self-interested agents with private state. In Proceedings of UAI 2006.
[3]
DANTZIG, G. B. 1955. Linear programming under uncertainty. Mgmt. Sci. 1, 3/4, 197-206.
[4]
FEIGENBAUM, J., PAPADIMITRIOU, C. H., AND SHENKER, S. 2001. Sharing the cost of multicast transmissions. Journal of Computer and System Sciences 63, 1, 21-41.
[5]
IMMORLICA, N., KARGER, D., MINKOFF, M., AND MIRROKNI, V. S. 2004. On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems. In SODA '04. 691-700.
[6]
SHMOYS, D. B. AND SWAMY, C. 2006. An approximation scheme for stochastic linear programming and its application to stochastic integer programs. JACM 53, 6, 978-1012.
[7]
SWAMY, C. AND SHMOYS, D. B. 2006. Approximation algorithms for 2-stage stochastic optimization problems. SIGACT News 37, 1, 33-46.

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM SIGecom Exchanges
ACM SIGecom Exchanges  Volume 7, Issue 1
December 2007
70 pages
EISSN:1551-9031
DOI:10.1145/1345037
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 2007
Published in SIGECOM Volume 7, Issue 1

Check for updates

Author Tag

  1. stochastic programming

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 154
    Total Downloads
  • Downloads (Last 12 months)3
  • Downloads (Last 6 weeks)0
Reflects downloads up to 30 Jan 2025

Other Metrics

Citations

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media