Auctions with Dynamic Populations: Efficiency and Revenue Maximization

Said, Maher (2009): Auctions with Dynamic Populations: Efficiency and Revenue Maximization.

Abstract

We study a setting where objects and privately-informed buyers arrive stochastically to a market. A seller in this setting faces a sequential allocation problem with a dynamic population. We derive both efficient and revenue-maximizing incentive compatible direct mechanisms. Our main result shows that the sequential ascending auction is a simple indirect mechanism that achieves these desirable objectives. We construct equilibria in memoryless strategies where, in every period, bidders reveal all private information. These equilibria are outcome equivalent to the direct mechanisms. In contrast to static settings, sequential second-price auctions cannot yield these outcomes, as they do not reveal sufficient information.

• Item Type: MPRA Paper
• Language: English
• Keywords: Dynamic mechanism design; Sequential allocation; Random arrivals; Revenue equivalence; Indirect mechanisms; Sequential ascending auctions.
• Subjects: D - Microeconomics > D4 - Market Structure, Pricing, and Design > D44 - Auctions; D - Microeconomics > D8 - Information, Knowledge, and Uncertainty > D82 - Asymmetric and Private Information ; Mechanism Design; D - Microeconomics > D8 - Information, Knowledge, and Uncertainty > D83 - Search ; Learning ; Information and Knowledge ; Communication ; Belief ; Unawareness; C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C73 - Stochastic and Dynamic Games ; Evolutionary Games ; Repeated Games

References

Athey, S., and I. Segal (2007): "An Efficient Dynamic Mechanism," Unpublished manuscript, Harvard University.

Ausubel, L.M. (2004): "An Efficient Ascending-Bid Auction for Multiple Objects," American Economic Review, 94(5), 1452-1475.

Banks, J.S., J.O. Ledyard, and D.P. Porter (1989): "Allocating Uncertain and Unresponsive Resources: An Experimental Approach," The RAND Journal of Economics, 20(1), 1-25.

Bergemann, D. and J. Valimaki (2008): "The Dynamic Pivot Mechanism," Cowles Foundation Discussion Paper 1672, Yale University.

Bikhchandani, S., P.A. Haile, and J.G. Riley (2002): "Symmetric Separating Equilibria in English Auctions," Games and Economic Behavior, 38(1), 19-27.

Caillaud, B. and J. Robert (2005): "Implementation of the Revenue-Maximizing Auction by an Ignorant Seller," Review of Economic Design, 9(2), 127-143.

Cavallo, R., D.C. Parkes, and S. Singh (2009): "Efficient Mechanisms with Dynamic Populations and Dynamic Types," Unpublished manuscript, Harvard University.

Dasgupta, P. and E. Maskin (2000): "Efficient Auctions," Quarterly Journal of Economics, 115(2), 341-388.

Demange, G., D. Gale, and M. Sotomayor (1986): "Multi-Item Auctions," Journal of Political Economy, 94(4), 863-872.

Edelman, B. and M. Schwarz (2006): "Optimal Auction Design in a Multi-Unit Environment: The Case of Sponsored Search Auctions," Unpublished manuscript, Harvard Business School.

Fudenberg, D. and J. Tirole (1991): "Perfect Bayesian Equilibrium and Sequential Equilibrium," Journal of Economic Theory, 53(2), 236-260.

Gershkov, A. and B. Moldovanu (2008): "Dynamic Revenue Maximization with Heterogeneous Objects: A Mechanism Design Approach," American Economic Journal: Microeconomics, forthcoming.

Gershkov, A. and B. Moldovanu (2009): "Efficient Sequential Assignment with Incomplete Information," Games and Economic Behavior, forthcoming.

Hendon, E., H.J. Jacobson, and B. Sloth (1996): "The One-Shot-Deviation Principle for Sequential Rationality," Games and Economic Behavior, 12(2), 274-282.

Kagel, J.H., R.M. Harstad, and D. Levin (1987): "Information Impact and Allocation Rules in Auctions with Affiliated Private Values: A Laboratory Study," Econometrica, 55(6), 1275-1304.

Kagel, J.H. and D. Levin (2009): "Implementing Efficient Multi-Object Auction Institutions: An Experimental Study of hte Performance of Boundedly Rational Agents," Games and Economic Behavior, 66(1), 221-237.

Kittsteiner, T., J. Nikutta, and E. Winter (2004): "Declining Valuations in Sequential Auctions," International Journal of Game Theory, 33(1), 89-106.

Krishna, V. (2003): "Asymmetric English Auctions," Journal of Economic Theory, 112(2), 261-288.

Kurino, M. (2009): "House Allocation with Overlapping Agents: A Dynamic Mechanism Design Approach," Unpublished manuscript, University of Pittsburgh.

Lavi, R. and N. Nisan (2005): "Online Ascending Auctions for Gradually Expiring Items," in Proceedings of the 16th Symposium on Discrete Algorithms (SODA 2005), Vancouver.

Lavi, R. and E. Segev (2008): "Efficiency Levels in Sequential Auctions with Dynamic Arrivals," Unpublished manuscript, Technion.

Maskin, E. and J.G. Riley (1989): "Optimal Multi-Unit Auctions," in The Economics of Missing Markets, Information, and Games, ed. by F. Hahn, pp. 312-335. Oxford University Press.

Mierendorff, K. (2008): "An Efficient Intertemporal Auction," Unpublished manuscript, University of Bonn.

Milgrom, P.R. and R.J. Weber (1982): "A Theory of Auctions and Competitive Bidding," Econometrica, 50(5), 1089-1122.

Milgrom, P.R. and R.J. Weber (2000): "A Theory of Auctions and Competitive Bidding, II," in The Economic Theory of Auctions, ed. by P. Klemperer, vol. 2, pp. 179-194. Edward Elgar Publishing, Cheltenham, UK.

Myerson, R.B. (1981): "Optimal Auction Design," Mathematics of Operations Research, 6(1), 58-73.

Pai, M. and R. Vohra (2008): "Optimal Dynamic Auctions," Unpublished manuscript, Northwestern University.

Parkes, D.C. (2007): "Online Mechanisms," in Algorithmic Game Theory, ed. by N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, chap. 16, pp. 411-439. Cambridge University Press, Cambridge, UK.

Parkes, D.C. and S. Singh (2003): "An MDP-Based Approach to Online Mechanism Design," in Proceedings of the 17th Annual Conference on Neural Information Processing Systems (NIPS '03).

Pavan, A., I. Segal, and J. Toikka (2009): "Dynamic Mechanism Design: Revenue Equivalence, Profit Maximization and Information Disclosure," Unpublished manuscript, Northwestern University.

Perea, A. (2002): "A Note on the One-Deviation Property in Extensive Form Games," Games and Economic Behavior, 40(2), 322-338.

Rahman, D. (2009): "Dynamic Implementation," Unpublished manuscript, University of Minnesota.

Rothkopf, M.H., T.J. Teisberg, and E.P. Kahn (1990): "Why Are Vickrey Auctions Rare?," Journal of Political Economy, 98(1), 94-109.

Said, M. (2008): "Information Revelation in Sequential Ascending Auctions," Unpublished manuscript, Yale University.

Said, M. (2009): "Sequential Auctions with Randomly Arriving Buyers," Unpublished manuscript, Yale University.

Skreta, V. (2007): "Optimal Auctions with General Distributions," Unpublished manuscript, New York University.

Unver, U. (2009): "Dynamic Kidney Exchange," Review of Economic Studies, forthcoming.

Vickrey, W. (1961): "Counterspeculation, Auctions, and Competitive Sealed Tenders," Journal of Finance, 16(1), 8-37.

Vulcano, G., G. van Ryzin, and C. Maglaras (2002): "Optimal Dynamic Auctions for Revenue Management," Management Science, 48(11), 1388-1407.