An efficient approximate algorithm for winner determination in combinatorial auctions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An efficient approximate algorithm for winner determination in combinatorial auctions

Full text

Pdf (353 KB)

Source

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

Minneapolis, Minnesota, United States

Pages: 30 - 37

Year of Publication: 2000

ISBN:1-58113-272-7

Authors

Yuko Sakurai	NTT Communication Science Laboratories, 2-4 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-0237 Japan
Makoto Yokoo	NTT Communication Science Laboratories, 2-4 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-0237 Japan
Koji Kamei	NTT Communication Science Laboratories, 2-4 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-0237 Japan

Sponsor

SIGEcom: ACM Special Interest Group on Electronic Commerce

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 34, Citation Count: 6

Additional Information:

references cited by index terms review 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.352875 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	Integer Programming for Combinatorial Auction Winner Determination, Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-2000), p.39, July 10-12, 2000
	2	Yuzo Fujishima , Kevin Leyton-Brown , Yoav Shoham, Taming the Computational Complexity of Combinatorial Auctions: Optimal and Approximate Approaches, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.548-553, July 31-August 06, 1999
	3	W.D.Harvey and M.L.Ginsberg.Limited discrepancy search.In the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-95) pages 607 -613,1995.
	4	Holger H. Hoos , Craig Boutilier, Solving Combinatorial Auctions Using Stochastic Local Search, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.22-29, July 30-August 03, 2000
	5	Richard E. Korf, Depth-first iterative-deepening: an optimal admissible tree search, Artificial Intelligence, v.27 n.1, p.97-109, Sept. 1985 [doi>10.1016/0004-3702(85)90084-0]
	6	Daniel Lehmann , Liaden Ita O'Callaghan , Yoav Shoham, Truth revelation in approximately efficient combinatorial auctions, Proceedings of the 1st ACM conference on Electronic commerce, p.96-102, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337016]
	7	Kevin Leyton-Brown , Yoav Shoham , Moshe Tennenholtz, An Algorithm for Multi-Unit Combinatorial Auctions, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.56-61, July 30-August 03, 2000
	8	P.R.Milgrom.Putting auction theory to work:The simultaneous ascending auction. http://www.cramton.umd.edu/conference/Auction- Conference.html, 1985.
	9	Michael H. Rothkopf , Aleksandar Pekec , Ronald M. Harstad, Computationally Manageable Combinational Auctions, Management Science, v.44 n.8, p.1131-1147, August 1998 [doi>10.1287/mnsc.44.8.1131]
	10	Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
	11	Tuomas Sandholm, An Algorithm for Optimal Winner Determination in Combinatorial Auctions, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.542-547, July 31-August 06, 1999
	12	Tuomas Sandholm , Subhash Suri, Improved Algorithms for Optimal Winner Determination in Combinatorial Auctions and Generalizations, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.90-97, July 30-August 03, 2000
	13	H.R.Varian.Economic mechanism design for computerized agent.In the First Usenix Workshop on Electronic Commerce 1995.
	14	T.Walsh.Depth-bounded discrepancy search.In the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI-97)pages 1388 -1393,1997.
	15	M.P.Wellman.A market-oriented programming environment and its application to distributed ulticommodity ?ow problems.Journal of Artificial Intelligence Research 1:1 -23,1993.

CITED BY 6

	Makoto Yokoo , Koutarou Suzuki, Secure multi-agent dynamic programming based on homomorphic encryption and its application to combinatorial auctions, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, July 15-19, 2002, Bologna, Italy
	Cuihong Li , Katia Sycara, Algorithm for combinatorial coalition formation and payoff division in an electronic marketplace, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, July 15-19, 2002, Bologna, Italy
	Masaya Mito , Satoshi Fujita, On Heuristics for Solving Winner Determination Problem in Combinatorial Auctions, Journal of Heuristics, v.10 n.5, p.507-523, September 2004
	G. Anandalingam , Robert W. Day , S. Raghavan, The Landscape of Electronic Market Design, Management Science, v.51 n.3, p.316-327, March 2005
	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
	Makoto Yokoo , Yuko Sakurai , Shigeo Matsubara, Bundle design in robust combinatorial auction protocol against false-name bids, Proceedings of the 17th international joint conference on Artificial intelligence, p.1095-1101, August 04-10, 2001, Seattle, WA, USA

INDEX TERMS

Primary Classification:
K. Computing Milieux
K.4 COMPUTERS AND SOCIETY
K.4.4 Electronic Commerce

Additional Classification:
G. Mathematics of Computing
G.2 DISCRETE MATHEMATICS
G.2.1 Combinatorics
Subjects: Combinatorial algorithms

General Terms:
Algorithms

REVIEW

"A.K. Krishna Menon : Reviewer"

Combinatorial auctions (CA) allow bidders to express logical constraints, such as: "I want A only if I also get B." CA also lets bidders specify preferences for substitutable items. In short, CA increases the revenue for the seller, as well as enh more...

Collaborative Colleagues:

Yuko Sakurai: colleagues

Makoto Yokoo: colleagues

Koji Kamei: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player