Self-correcting sampling-based dynamic multi-unit auctions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Self-correcting sampling-based dynamic multi-unit auctions

Full text

Pdf (494 KB)

Source

Electronic Commerce archive
Proceedings of the tenth ACM conference on Electronic commerce table of contents

Stanford, California, USA

SESSION: Session 3 table of contents

Pages 89-98

Year of Publication: 2009

ISBN:978-1-60558-458-4

Authors

Florin Constantin	Harvard University, Cambridge, MA, USA
David C. Parkes	Harvard University, Cambridge, MA, USA

Sponsors

ACM: Association for Computing Machinery
SIGEcom: ACM Special Interest Group on Electronic Commerce

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 29, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1566374.1566387 What is a DOI?

ABSTRACT

We exploit methods of sample-based stochastic optimization for the purpose of strategyproof dynamic, multi-unit auctions. There are no analytic characterizations of optimal policies for this domain and thus a heuristic approach, such as that proposed here, seems necessary in practice. Following the suggestion of Parkes and Duong [17], we perform sensitivity analysis on the allocation decisions of an online algorithm for stochastic optimization, and correct the decisions to enable a strategyproof auction. In applying this approach to the allocation of non-expiring goods, the technical problem that we must address is related to achieving strategyproofness for reports of departure. This cannot be achieved through self-correction without canceling many allocation decisions, and must instead be achieved by first modifying the underlying algorithm. We introduce the NowWait method for this purpose, prove its successful interfacing with sensitivity analysis and demonstrate good empirical performance. Our method is quite general, requiring a technical property of uncertainty independence, and that values are not too positively correlated with agent patience. We also show how to incorporate "virtual valuations" in order to increase the seller's revenue.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	C. Boutilier, D.C. Parkes, T. Sandholm, and W.E. Walsh. Expressive banner ad auctions and model-based online optimization for clearing. In Proc. 23rd National Conf. on Artificial Intelligence (AAAI), pages 30--37, 2008.
	2	V. Conitzer and T. Sandholm. Complexity of mechanism design. In Proc. 18th Conference on Uncertainty in Artificial Intelligence, pages 103--110, 2002.
	3	V. Conitzer and T. Sandholm. Incremental mechanism design. In International Joint Conferences on Artificial Intelligence (IJCAI), 2007.
	4	Jrmie Gallien, Dynamic Mechanism Design for Online Commerce, Operations Research, v.54 n.2, p.291-310, March-April 2006 [doi>10.1287/opre.1050.0239]
	5	A. Gershkov and B. Moldovanu. Learning about the future and dynamic efficiency. Forthcoming, Amer. Econ. Review.
	6	A. Gershkov and B. Moldovanu. Dynamic revenue maximization with heterogeneous objects: a mechanism design approach. www.econ2.uni-bonn.de/gershkov/pdf/dynamicrev.pdf, February 2008.
	7	J. Gilbert and F. Mosteller. Recognizing the maximum of a sequence. Journal of the American Statistical Association, 61(313):35--73, March 1966.
	8	Mohammad T. Hajiaghayi, Online auctions with re-usable goods, Proceedings of the 6th ACM conference on Electronic commerce, p.165-174, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064027]
	9	M. Hajiaghayi, R. Kleinberg, and T. Sandholm. Automated online mechanism design and prophet inequalities. In AAAI 2007, pages 58--65, 2007.
	10	Michael J. Kearns , Yishay Mansour , Andrew Y. Ng, A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.1324-1231, July 31-August 06, 1999
	11	Ron Lavi , Noam Nisan, Competitive analysis of incentive compatible on-line auctions, Proceedings of the 2nd ACM conference on Electronic commerce, p.233-241, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352897]
	12	Ron Lavi , Chaitanya Swamy, Truthful and Near-Optimal Mechanism Design via Linear Programming, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.595-604, October 23-25, 2005 [doi>10.1109/SFCS.2005.76]
	13	R.B. Myerson. Optimal auction design. Mathematics of Operations Research, VI:58--73, 1981.
	14	M. Pai and R. Vohra. Optimal dynamic auctions. http://www.kellogg.northwestern.edu/faculty/vohra/ftp/vohra91.pdf, March 2008.
	15	D.C. Parkes. Online mechanisms. In N. Nisan, E. Tardos, T. Roughgarden, and V. Vazirani, editors, Algorithmic Game Theory, chapter 16. Cambridge Univ. Press, 2007.
	16	David C. Parkes, When Analysis Fails: Heuristic Mechanism Design via Self-correcting Procedures, Proceedings of the 35th Conference on Current Trends in Theory and Practice of Computer Science, January 24-30, 2009, `pindlerov Mlýn, Czech Republic [doi>10.1007/978-3-540-95891-8_9]
	17	D.C. Parkes and Q. Duong. An ironing-based approach to adaptive online mechanism design in single-valued domains. In AAAI, 2007.
	18	D.C. Parkes and S. Singh. An MDP-Based approach to Online Mechanism Design. In Proc. NIPS, 2003.
	19	D.C. Parkes, S. Singh, and D. Yanovsky. Approximately efficient online mechanism design. In Proc. 18th Conf. on Neural Information Processing Systems (NIPS), 2004.
	20	A. Pavan, I. Segal, and J. Toikka. Dynamic mechanism design: Revenue equivalence, profit maximization and information disclosure. www.stanford.edu/~isegal/dmd.pdf, June 2008.
	21	Pascal Van Hentenryck , Russell Bent, Online Stochastic Combinatorial Optimization, The MIT Press, 2006