Computationally efficient and revenue optimized auctioneer's strategy for expanding auctions

ABSTRACT

An expanding auction---a special type of an ascending-price open-cry auction---allows the auctioneer to dynamically add (identical) items to the single item offered initially. Expanding auctions are becoming an increasingly popular business-to-consumer auction mechanism. The auctioneer's revenue from an expanding auction depends, in large part, on its schedule for increasing the number of units offered. As we show, the naïve strategies commonly used for increasing the number of items offered in contemporary e-commerce implementations of expanding auctions are sub-optimal. In this study we provide a strategy that, given some assumptions about buyers' behaviors, maximizes the expected revenues of the auctioneer in an expanding auction. We model the auction process as a state graph in which nodes are auction states and edges are transitions. With this model, finding the optimal strategy is equivalent to solving a search problem on the state graph. We prove that the search problem to be solved, although seemingly exponentially complex, is actually linearly bounded. Based on this result, we introduce an informed decision strategy that optimizes the auctioneer's revenue.

REFERENCES

• 1: www.olsale.co.il/olsale/rules.aspx?type=1
• 2: L. Ausubel, "An Efficient Ascending-Bid Auction for Multiple Objects", Working Paper 97--06, U. Maryland, 1997.
• 3: L. Ausubel, "A Generalized Vickrey Auction", Working Paper, University of Maryland, 1999.
• 4: P. Cramton. Ascending Auctions, European Economic Review 42:3--5, 745--756, 1998.
• 5: Andrew V. Goldberg , Jason D. Hartline , Andrew Wright, Competitive auctions and digital goods, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.735-744, January 07-09, 2001, Washington, D.C., United States
• 6: P. Klemperer. Auction Theory: A Guide to the Literature. Journal of Economic Surveys, Vol. 13(3) pp. 227--286, 1999.
• 7: E. Maskin, J. Riley, "Open and Sealed-Bid Auctions: Auction Theory with Private Values," American Economic Review, 75, 150--155, 1985.
• 8: P. Milgrom, R. Weber, "A Theory of Auctions and Competitive Bidding", Econometrica, 50, 1089--1122, 1982.
• 9: R. Myerson, "Optimal Auction Design," Mathematics of Operations Research, 6, 58--73, 1981.
• 10: Sunju Park , Edmund H. Durfee , William P. Birmingham, An adaptive agent bidding strategy based on stochastic modeling, Proceedings of the third annual conference on Autonomous Agents, p.147-153, April 1999, Seattle, Washington, United States [doi>10.1145/301136.301181]
• 11: Onn Shehory , Eran Dror, Optimizing auctioneer's revenues in expanding multi-unit auctions, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082694]
• 12: H. Varian, "Economic Mechanism Design for Computerized Agents", Working Paper, U. California, 1995.
• 13: W. Vickrey, Counterspeculation, Auctions and Competitive Sealed Tenders. J. of Finance, 16, 8--37, 1961.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

Keywords:
auctioneer's revenue, expanding auction