IDEAS home Printed from
   My bibliography  Save this paper

Sequential Posted Pricing and Multi-parameter Mechanism Design


  • Shuchi Chawla
  • Jason Hartline
  • David Malec
  • Balasubramanian Sivan


We consider the classical mathematical economics problem of {\em Bayesian optimal mechanism design} where a principal aims to optimize expected revenue when allocating resources to self-interested agents with preferences drawn from a known distribution. In single-parameter settings (i.e., where each agent's preference is given by a single private value for being served and zero for not being served) this problem is solved [Myerson '81]. Unfortunately, these single parameter optimal mechanisms are impractical and rarely employed [Ausubel and Milgrom '06], and furthermore the underlying economic theory fails to generalize to the important, relevant, and unsolved multi-dimensional setting (i.e., where each agent's preference is given by multiple values for each of the multiple services available) [Manelli and Vincent '07]. In contrast to the theory of optimal mechanisms we develop a theory of sequential posted price mechanisms, where agents in sequence are offered take-it-or-leave-it prices. These mechanisms are approximately optimal in single-dimensional settings, and avoid many of the properties that make optimal mechanisms impractical. Furthermore, these mechanisms generalize naturally to give the first known approximations to the elusive optimal multi-dimensional mechanism design problem. In particular, we solve multi-dimensional multi-unit auction problems and generalizations to matroid feasibility constraints. The constant approximations we obtain range from 1.5 to 8. For all but one case, our posted price sequences can be computed in polynomial time.

Suggested Citation

  • Shuchi Chawla & Jason Hartline & David Malec & Balasubramanian Sivan, 2010. "Sequential Posted Pricing and Multi-parameter Mechanism Design," Discussion Papers 1486, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
  • Handle: RePEc:nwu:cmsems:1486

    Download full text from publisher

    File URL:
    File Function: main text
    Download Restriction: no

    References listed on IDEAS

    1. D. Pearce, 2010. "Rationalizable Strategic Behavior and the Problem of Perfection," Levine's Working Paper Archive 523, David K. Levine.
    2. Dutta, Jayasri & Morris, Stephen, 1997. "The Revelation of Information and Self-Fulfilling Beliefs," Journal of Economic Theory, Elsevier, vol. 73(1), pages 231-244, March.
    3. Radner, Roy, 1979. "Rational Expectations Equilibrium: Generic Existence and the Information Revealed by Prices," Econometrica, Econometric Society, vol. 47(3), pages 655-678, May.
    4. Tan, Tommy Chin-Chiu & da Costa Werlang, Sergio Ribeiro, 1988. "The Bayesian foundations of solution concepts of games," Journal of Economic Theory, Elsevier, vol. 45(2), pages 370-391, August.
    5. R. Guesnerie, 2002. "Anchoring Economic Predictions in Common Knowledge," Econometrica, Econometric Society, vol. 70(2), pages 439-480, March.
    6. Roger Guesnerie, 2005. "Assessing Rational Expectations 2: "Eductive" Stability in Economics," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262072580, July.
    7. McAllister, Patrick H., 1990. "Rational behavior and rational expectations," Journal of Economic Theory, Elsevier, vol. 52(2), pages 332-363, December.
    8. Bernheim, B Douglas, 1984. "Rationalizable Strategic Behavior," Econometrica, Econometric Society, vol. 52(4), pages 1007-1028, July.
    9. Roy Radner, 1997. "Rational Expectations Equilibrium: Generic Existence and the Information Revealed by Prices," Levine's Working Paper Archive 1594, David K. Levine.
    10. Battigalli, Pierpaolo & Bonanno, Giacomo, 1999. "Recent results on belief, knowledge and the epistemic foundations of game theory," Research in Economics, Elsevier, vol. 53(2), pages 149-225, June.
    11. Pearce, David G, 1984. "Rationalizable Strategic Behavior and the Problem of Perfection," Econometrica, Econometric Society, vol. 52(4), pages 1029-1050, July.
    12. Kreps, David M., 1977. "A note on "fulfilled expectations" equilibria," Journal of Economic Theory, Elsevier, vol. 14(1), pages 32-43, February.
    13. John C Harsanyi, 1997. "Games with incomplete information played by "bayesian" players," Levine's Working Paper Archive 1175, David K. Levine.
    Full references (including those not matched with items on IDEAS)

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:


    Access and download statistics


    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:nwu:cmsems:1486. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Fran Walker). General contact details of provider: .

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.