Competitive analysis of incentive compatible on-line auctions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Competitive analysis of incentive compatible on-line auctions

Full text

Pdf (494 KB)

Source

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

Minneapolis, Minnesota, United States

Pages: 233 - 241

Year of Publication: 2000

ISBN:1-58113-272-7

Authors

Ron Lavi	Institute of Computer Science, The Hebrew University of Jerusalem, Israel
Noam Nisan	Institute of Computer Science, The Hebrew University of Jerusalem, Israel

Sponsor

SIGEcom: ACM Special Interest Group on Electronic Commerce

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 33, Citation Count: 26

Additional Information:

references cited by 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/352871.352897 What is a DOI?

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	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	2	ebay. Web page: http://www.ebay.com.
	3	Ran El-Yaniv, Competitive Solutions for On-line Financial Problems, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.326-372, January 1998
	4	Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
	5	R. El-Yaniv, A. Fiat, R. Karp, and G. Turpin. Competitive analysis of ~nancial games. In Proc. of the 33rd Symposium on Foundations of Computer Science (FOCS'92), pages 327{333, 1992.
	6	E. Ephrati and J. S. Rosenschein. The clarke tax as a consensus mechanism among automated agents. In Proc. of the National Conference onArti~cial Intelligence, 1991.
	7	Donald F. Ferguson , Christos Nikolaou , Jakka Sairamesh , Yechiam Yemini, Economic models for allocating resources in computer systems, Market-based control: a paradigm for distributed resource allocation, World Scientific Publishing Co., Inc., River Edge, NJ, 1996
	8	Developments from a June 1996 seminar on Online algorithms: the state of the art, January 1998
	9	H. Jiang and S. Jordan. Connection establishment in high speed networks. Ieee Journal of Selected Areas in Communications, 13(7), 1995.
	10	P. Klemperer. Auction theory: A guide to the literature. Journal of Economic Surveys, 13(3):227{286, 1999.
	11	Yannis A. Korilis , Aurel A. Lazar, On the existence of equilibria in noncooperative optimal flow control, Journal of the ACM (JACM), v.42 n.3, p.584-613, May 1995 [doi>10.1145/210346.210415]
	12	Sarit Kraus, An overview of incentive contracting, Artificial Intelligence, v.83 n.2, p.297-346, June 1996 [doi>10.1016/0004-3702(95)00059-3]
	13	A. A. Lazar and N. Semret. The progressive second price auction mechanism for network resource sharing. In Proc. of the 8th International Symposium on Dynamic Games, 1998.
	14	Moai. Web page: http://www.moai.com.
	15	Jeffrey K. MacKie-Mason , Hal R. Varian, Pricing the Internet, Public access to the Internet, MIT Press, Cambridge, MA, 1995
	16	A. Mas-Collel, W. Whinston, and J. Green. Microeconomic Theory. Oxford university press, 1995.
	17	E. S. Maskin and J. G. Riley. Optimal multi-unit auctions. In F. Hahn, editor, The Economics of Missing Markets, Information, and Games. Oxford University Press, Clarendon Press, 1989.
	18	M. S. Miller and K. E. Drexler. Markets and computation: Agoric open systems. In B. Huberman, editor, The Ecology of Computation. Elsevier Science Publishers/North-Holland, 1988.
	19	N. Nisan. Algorithms for sel~sh agents. In Proc. of the 16th Symposium on Theoretical Aspects of Computer Science (STACS'99), 1999.
	20	Noam Nisan , Amir Ronen, Algorithmic mechanism design (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.129-140, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301287]
	21	Jeffrey S. Rosenschein , Gilad Zlotkin, Rules of encounter: designing conventions for automated negotiation among computers, MIT Press, Cambridge, MA, 1994
	22	Tuomas W. Sandholm, Distributed rational decision making, Multiagent systems: a modern approach to distributed artificial intelligence, MIT Press, Cambridge, MA, 1999
	23	T. Sandholm and F. Ygge. On the gains and losses of speculation in equilibrium markets. In Proc. of the 15th Int. Joint Conference onArti~cial Intelligence (IJCAI-97), 1999.
	24	Scott Shenker, Making greed work in networks: a game-theoretic analysis of switch service disciplines, Proceedings of the conference on Communications architectures, protocols and applications, p.47-57, August 31-September 02, 1994, London, United Kingdom
	25	W. Vickrey. Counterspeculations, auctions, and competitive sealed tenders. Journal of Finance, 16:8{37, 1961.
	26	Carl A. Waldspurger , Tad Hogg , Bernardo A. Huberman , Jeffrey O. Kephart , W. Scott Stornetta, Spawn: A Distributed Computational Economy, IEEE Transactions on Software Engineering, v.18 n.2, p.103-117, February 1992 [doi>10.1109/32.121753]

CITED BY 26

	Yair Bartal , Rica Gonen , Noam Nisan, Incentive compatible multi unit combinatorial auctions, Proceedings of the 9th conference on Theoretical aspects of rationality and knowledge, June 20-22, 2003, Univerity of Indiana, Indiana
	Eric J. Friedman , David C. Parkes, Pricing WiFi at Starbucks: issues in online mechanism design, Proceedings of the 4th ACM conference on Electronic commerce, June 09-12, 2003, San Diego, CA, USA
	Avrim Blum , Tuomas Sandholm , Martin Zinkevich, Online algorithms for market clearing, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.971-980, January 06-08, 2002, San Francisco, California
	Aaron Archer , Christos Papadimitriou , Kunal Talwar , Éva Tardos, An approximate truthful mechanism for combinatorial auctions with single parameter agents, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Baruch Awerbuch , Yossi Azar , Adam Meyerson, Reducing truth-telling online mechanisms to online optimization, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Mohammad Taghi Hajiaghayi , Robert Kleinberg , David C. Parkes, Adaptive limited-supply online auctions, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA
	Ryan Porter, Mechanism design for online real-time scheduling, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA
	Ziv Bar-Yossef , Kirsten Hildrum , Felix Wu, Incentive-compatible online auctions for digital goods, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.964-970, January 06-08, 2002, San Francisco, California
	Avrim Blum , Vijay Kumar , Atri Rudra , Felix Wu, Online learning in online auctions, Theoretical Computer Science, v.324 n.2-3, p.137-146, 20 September 2004
	Avrim Blum , Vijay Kumar , Atri Rudra , Felix Wu, Online learning in online auctions, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Chaki Ng , Philip Buonadonna , Brent N. Chun , Alex C. Snoeren , Amin Vahdat, Addressing strategic behavior in a deployed microeconomic resource allocator, Proceeding of the 2005 ACM SIGCOMM workshop on Economics of peer-to-peer systems, August 22-22, 2005, Philadelphia, Pennsylvania, USA
	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
	Adam I. Juda , David C. Parkes, The sequential auction problem on eBay: an empirical analysis and a solution, Proceedings of the 7th ACM conference on Electronic commerce, p.180-189, June 11-15, 2006, Ann Arbor, Michigan, USA
	Avrim Blum , Tuomas Sandholm , Martin Zinkevich, Online algorithms for market clearing, Journal of the ACM (JACM), v.53 n.5, p.845-879, September 2006
	Shahram Esmaeilsabzali , Nancy A. Day, Online pricing for web service providers, Proceedings of the 2006 international workshop on Economics driven software engineering research, May 27-27, 2006, Shanghai, China
	Tuomas Sandholm , Andrew Gilpin, Sequences of take-it-or-leave-it offers: near-optimal auctions without full valuation revelation, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan
	Eugene Fink , Josh Johnson , Jenny Hu, Exchange Market for Complex Goods: Theory and Experiments, Netnomics, v.6 n.1, p.21-42, April 2004
	Eugene Fink , Jianli Gong , Josh Johnson, Exchange market for complex commodities: search for optimal matches, Journal of Experimental & Theoretical Artificial Intelligence, v.19 n.2, p.91-117, June 2007
	Florin Constantin , Jon Feldman , S. Muthukrishnan , Martin Pál, An online mechanism for ad slot reservations with cancellations, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1265-1274, January 04-06, 2009, New York, New York
	Moshe Babaioff , Michael Dinitz , Anupam Gupta , Nicole Immorlica , Kunal Talwar, Secretary problems: weights and discounts, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1245-1254, January 04-06, 2009, New York, New York
	Mohammad Taghi Hajiaghayi , Robert Kleinberg , Tuomas Sandholm, Automated online mechanism design and prophet inequalities, Proceedings of the 22nd national conference on Artificial intelligence, p.58-65, July 22-26, 2007, Vancouver, British Columbia, Canada
	David C. Parkes , Quang Duong, An ironing-based approach to adaptive online mechanism design in single-valued domains, Proceedings of the 22nd national conference on Artificial intelligence, p.94-101, July 22-26, 2007, Vancouver, British Columbia, Canada
	Naoki Fukuta , Takayuki Ito, Fine-grained efficient resource allocation using approximated combinatorial auctions: A parallel greedy winner approximation for large-scale problems, Web Intelligence and Agent Systems, v.7 n.1, p.43-63, January 2009
	Adam I. Juda , David C. Parkes, An options-based solution to the sequential auction problem, Artificial Intelligence, v.173 n.7-8, p.876-899, May, 2009
	Florin Constantin , David C. Parkes, Self-correcting sampling-based dynamic multi-unit auctions, Proceedings of the tenth ACM conference on Electronic commerce, July 06-10, 2009, Stanford, California, USA
	Jonathan Bredin , David C. Parkes , Quang Duong, Chain: a dynamic double auction framework for matching patient agents, Journal of Artificial Intelligence Research, v.30 n.1, p.133-179, September 2007