Auctions with Dynamic Populations: Efficiency and Revenue Maximization

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

Abstract

We examine an environment where objects and privately-informed buyers arrive stochastically to a market. The seller in this setting faces a sequential allocation problem with a changing population. We characterize the set of incentive compatible allocation rules and provide a generalized revenue equivalence result. In contrast to a static setting where incentive compatibility implies that higher-valued buyers have a greater likelihood of receiving an object, in this dynamic setting, incentive compatibility implies that higher-valued buyers have a greater likelihood of receiving an object sooner.

We also characterize the set of efficient allocation rules and show that a dynamic Vickrey-Clarke-Groves mechanism is efficient and periodic ex post incentive compatible. We then derive the revenue-maximizing allocation rule and show that the optimal direct mechanism is a pivot mechanism with a reserve price.

Finally, we consider sequential ascending auctions in this setting, both with and without a reserve price. We construct memoryless equilibrium bidding strategies in this indirect mechanism. Bidders reveal their private information in every period, yielding the same outcomes as the direct mechanisms. Thus, the sequential ascending auction is a natural institution for achieving either efficient or optimal outcomes. Interestingly, this is not the case for sequential second-price auctions, as the bids in a second-price auction do not reveal sufficient information to realize either the efficient or the optimal allocation.

• 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.

Cavallo, R. (2008): "Efficiency and Redistribution in Dynamic Mechanism Design," in Proceedings of the 9th ACM Conference on Electronic Commerce (EC'08), Chicago.

Cavallo, R., D.C. Parkes, and S. Singh (2007): "Efficient Online Mechanisms for Persistent, Periodically Inaccessible Self-Interested Agents," Unpublished manuscript, Harvard University.

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

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

Gershkov, A. and B. Moldovanu (2008b): "Efficient Sequential Assignment with Incomplete Information," Unpublished manuscript, University of Bonn.

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.

Iyengar, G. and A. Kumar (2006): "Characterizing Optimal Keyword Auctions," in Proceedings of the 2nd Workshop on Sponsored Search Auctions, Ann Arbor.

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.

Krishna, V. and M. Perry (2000): "Efficient Mechanism Design," Unpublished manuscript, Pennsylvania State University.

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.

Ok, E.A. (2007): Real Analysis with Economic Applications. Princeton University Press.

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

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.

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. (2009): "Sequential Auctions with Randomly Arriving Buyers," Unpublished manuscript, Yale University.

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

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.