Auctions with Dynamic Populations: Efficiency and Revenue Maximization

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

Abstract

We study indirect mechanisms in a setting where both objects and privately-informed buyers arrive stochastically to a market. The seller in this setting faces a sequential allocation problem, and must elicit the private information of the dynamic population of buyers in order to achieve her desired outcome -- either an efficient or a revenue-maximizing allocation. We propose a simple indirect mechanism, the sequential ascending auction, which yields outcomes identical to those of an efficient dynamic Vickrey-Clarke-Groves mechanism. We construct equilibria in memoryless strategies where strategic bidders are able to reach the efficient outcome by revealing all private information in every period, inducing behavior that is symmetric across both incumbent and newly entered buyers. In contrast to settings with a static population, a sequence of second-price auctions cannot yield this outcome, as these auctions do not reveal sufficient information to symmetrize different cohorts. We also extend our results to revenue-maximization, showing that the sequential ascending auction with a reserve price is optimal.

• Item Type: MPRA Paper
• Language: English
• Keywords: Dynamic mechanism design; Indirect mechanisms; Sequential ascending auctions; Sequential allocation; Random arrivals.
• 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 M. Said (2010): "Dynamic Auctions: A Survey," Cowles Foundation Discussion Paper 1757R, Yale University.

Bergemann, D., and J. Valimaki (2003): "Dynamic Common Agency," Journal of Economic Theory, 111(1), 23-48.

Bergemann, D., and J. Valimaki (2006): "Dynamic Price Competition," Journal of Economic Theory, 127(1), 232-263.

Bergemann, D., and J. Valimaki (2010): "The Dynamic Pivot Mechanism," Econometrica, 78(2), 771-789.

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

Board, S., and A. Skrzypacz (2010): "Optimal Dynamic Auctions for Durable Goods: Posted Prices and Fire-Sales," Unpublished manuscript, University of California, Los Angeles.

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.

Calzolari, G., and A. Pavan (2006): "On the Optimality of Privacy in Sequential Contracting," Journal of Economic Theory, 130(1), 168-204.

Calzolari, G., and A. Pavan (2009): "Sequential Contracting with Multiple Principals," Journal of Economic Theory, 144(2), 503-531.

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.

Dolan, R.J. (1978): "Incentive Mechanisms for Priority Queuing Problems," Bell Journal of Economics, 9(2), 421-436.

Edelman, B., and M. Schwarz (2010): "Optimal Auction Design and Equilibrium Selection in Sponsored Search Auctions," American Economic Review, 100(2), 597-602.

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 (2009): "Dynamic Revenue Maximization with Heterogeneous Objects: A Mechanism Design Approach," American Economic Journal: Microeconomics, 1(2), 168-198.

Gershkov, A., and B. Moldovanu (2010): "Efficient Sequential Assignment with Incomplete Information," Games and Economic Behavior, 68(1), 144-154.

Gershkov, A., and B. Moldovanu (2010): "Incentive Compatible Optimal Stopping," Unpublished manuscript, University of Bonn.

Haile, P.A. (2003): "Auctions with Private Uncertainty and Resale Opportunities," Journal of Economic Theory, 108(1), 72-110.

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.

Jehiel, P., and B. Moldovanu (2000): "Auctions with Downstream Interaction Among Buyers," RAND Journal of Economics, 31(4), 768-791.

Jehiel, P., and B. Moldovanu (2000): "Efficient Design with Interdependent Valuations," Econometrica, 69(5), 1237-1259.

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.

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 (2009): "Efficiency Levels in Sequential Auctions with Dynamic Arrivals," Unpublished manuscript, Technion.

Li, A. (2009): "Selling Storable Goods to a Dynamic Population of Buyers: A Mechanism Design Approach," Unpublished manuscript, Stanford University.

Mas-Colell, A., M.D. Whinston, and J.R. Green (1995): Microeconomic Theory. Oxford University Press, Oxford.

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. (2010): "Optimal Dynamic Mechanism Design with Deadlines," 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.

Monteiro, P.K., and B.F. Svaiter (2010): "Optimal Auction with a General Distribution: Virtual Valuation without Densities," Journal of Mathematical Economics, 46(1), 21-31.

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

Nalebuff, B.J., and J.I. Bulow (1993): "Designing the PCS Auction," Attached to Comments of Bell Atlantic Personal Communications, Inc., PP Docket 93-253.

Pai, M., and R. Vohra (2009): "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.

Pavan, A., I. Segal, and J. Toikka (2010): "Infinite-Horizon Mechanism Design: The Independent-Shock Approach," 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.

Said, M. (2008): "Information Revelation in Sequential Ascending Auctions," in Proceedings of the 9th ACM Conference on Electronic Commerce (EC'08), Chicago.

Said, M. (2010): "Sequential Auctions with Randomly Arriving Buyers," Unpublished manuscript, Microsoft Research New England.

Unver, U. (2010): "Dynamic Kidney Exchange," Review of Economic Studies, 77(1), 372-414.

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.