Towards a universal test suite for combinatorial auction algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Towards a universal test suite for combinatorial auction algorithms

Full text

Pdf (495 KB)

Source

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

Minneapolis, Minnesota, United States

Pages: 66 - 76

Year of Publication: 2000

ISBN:1-58113-272-7

Authors

Kevin Leyton-Brown	Dept. of Computer Science, Stanford University, Stanford, CA
Mark Pearson	Dept. of Computer Science, Stanford University, Stanford, CA
Yoav Shoham	Dept. of Computer Science, Stanford University, Stanford, CA

Sponsor

SIGEcom: ACM Special Interest Group on Electronic Commerce

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 54, Citation Count: 51

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.352879 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	A.Andersson,M.Tenhnen,,and F.Ygge.Integer programming for combinatorial a ction winner determination.In ICMAS-00 ,2000.
	2	L.A s bel,P.Cramption,R.McAfee,and J.McMillan.Synergies in wireless telephony: Evidence from the broadband PCS auctions.Journal of Economic and Management Strategy ,6(3):497 -527, Fall 1997.
	3	J.Banks,J.Ledyard,and D.Porter.Allocating uncertain and unresponsive reso rces:An experimental approach.RAND Journal of Economics , 20:1 -23,1989.
	4	Craig Boutilier , Moisés Goldszmidt , Bikash Sabata, Sequential Auctions for the Allocation of Resources with Complementarities, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.527-523, July 31-August 06, 1999
	5	P.Brewer and C.Plott.A binary con ?ict ascending price (BICAP)mechanism for the decentralized allocation of the right to se railroad tracks. International Journal of Industrial Organization , 14:857 -886,1996.
	6	M.Bykowsky,R.Cull,and J.Ledyard.M t ally destructive bidding:The FCC auction design problem. Technical Report Social Science Working Paper 916, California Instit te of Technology,Pasadena,1995.
	7	C.DeMartini,A.Kwasnica,J.Ledyard,and D.Porter.A new and improved design for m lti-object iterative a ctions.Technical Report Social Science Working Paper 1054,California Instit te of Technology,Pasadena,November 1998.
	8	S.DeVries and R.Vohra.Combinatorial auctions:A survey.2000.
	9	W.Elmaghraby and S.Oren.The e ?ciency of m lti-nit electricity auctions.IAEE ,20(4):89 -116, 1999.
	10	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
	11	D.Grether,R.Isaac,and C.Plott.The Allocation of Scarce Resources:Experimental Economic and the Problem of Allocating Airport Slots .Westview Press, Boulder,CO,1989.
	12	J.Ledyard,D.Porter,and A.Rangel.Experiments testing m ltiobject allocation mechanisms.Journal of Economic &Management Strategy ,6(3):639 -675,Fall 1997.
	13	J.Ledyard and K.Szakaly.Designing organizations for trading poll tion rights.Journal of Economic Behavior and Organization ,25:167 -196,1994.
	14	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]
	15	P.Milgrom.Putting auction theory to work:The sim ltaneous ascending a ction.Technical Report 98-0002,Department of Economics,Stanford University,1998.
	16	N.Nisan.Bidding and allocation in combinatorial auctions.Working paper,1999.
	17	David C. Parkes, iBundle: an efficient ascending price bundle auction, Proceedings of the 1st ACM conference on Electronic commerce, p.148-157, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337032]
	18	C.Plott and T.Cason.EPA 's new emissions trading mechanism:A laboratory evaluation.Journal of Environmental Economics and Management , 30:133 -160,1996.
	19	D.Q an.Real estate a ctions:A s rvey of theory and practice.Journal of Real Estate Finance and Economic ,9:23 -49,1994.
	20	S.Rassenti,S.Reynolds,,and V.Smith.Cotenancy and competition in an experimental auction market for nat ral gas pipeline networks.Economic Theory , 4:41 -65,1994.
	21	S.Rassenti,V.Smith,and R.Bul ?n.A combinatorial auction mechanism for airport time slot allocation. Bell Journal of Economic ,13:402 -417,1982.
	22	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]
	23	T.Sandholm.An implementation of the contract net protocol based on marginal cost calculations.pages 256 -262.Proceedings of AAAI-93,1993.
	24	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
	25	Moshe Tennenholtz, Some Tractable Combinatorial Auctions, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.98-103, July 30-August 03, 2000
	26	M.Wellman,W.Walsh,P.W rman,and J.MacKie-Mason.A ction protocols for decentralized sched ling.Proceedings of the 18th International Conference on Distrib ted Comp ting Systems,1998.

CITED BY 51

	Amy Greenwald , Justin Boyan, Bidding algorithms for simultaneous auctions, Proceedings of the 3rd ACM conference on Electronic Commerce, p.115-124, October 14-17, 2001, Tampa, Florida, USA
	Edo Zurel , Noam Nisan, An efficient approximate allocation algorithm for combinatorial auctions, Proceedings of the 3rd ACM conference on Electronic Commerce, p.125-136, October 14-17, 2001, Tampa, Florida, USA
	Tuomas Sandholm , Subhash Suri , Andrew Gilpin , David Levine, Winner determination in combinatorial auction generalizations, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, July 15-19, 2002, Bologna, Italy
	Craig Boutilier, Solving concisely expressed combinatorial auction problems, Eighteenth national conference on Artificial intelligence, p.359-366, July 28-August 01, 2002, Edmonton, Alberta, Canada
	Alan Holland , Barry O'Sullivan, Towards Fast Vickrey Pricing using Constraint Programming, Artificial Intelligence Review, v.21 n.3-4, p.335-352, June 2004
	Justin Boyan , Amy Greenwald, Bid determination in simultaneous actions an agent architecture, Proceedings of the 3rd ACM conference on Electronic Commerce, p.210-212, October 14-17, 2001, Tampa, Florida, USA
	Alan Holland , Barry O'Sullivan, Robust solutions for combinatorial auctions, Proceedings of the 6th ACM conference on Electronic commerce, p.183-192, June 05-08, 2005, Vancouver, BC, Canada
	Y. Guo , A. Lim , B. Rodrigues , Y. Zhu, Heuristics for a bidding problem, Computers and Operations Research, v.33 n.8, p.2179-2188, August 2006
	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
	John Collins , Wolfgang Ketter , Maria Gini, A Multi-Agent Negotiation Testbed for Contracting Tasks with Temporal and Precedence Constraints, International Journal of Electronic Commerce, v.7 n.1, p.35-57, Number 1/Fall 2002
	Michael Brydon, Economic metaphors for solving intrafirm allocation problems: what does a market buy us?, Decision Support Systems, v.42 n.3, p.1657-1672, December 2006
	Alessandro Avenali , Anna Bassanini, Simulating combinatorial auctions with dominance requirement and loll bids through automated agents, Decision Support Systems, v.43 n.1, p.211-228, February, 2007
	Laura Kang , David C. Parkes, Passive verification of the strategyproofness of mechanisms in open environments, Proceedings of the 8th international conference on Electronic commerce: The new e-commerce: innovations for conquering current barriers, obstacles and limitations to conducting successful business on the internet, August 13-16, 2006, Fredericton, New Brunswick, Canada
	Sylvia Estivie , Yann Chevaleyre , Ulle Endriss , Nicolas Maudet, How equitable is rational negotiation?, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan
	Peter Gradwell , Julian Padget, A comparison of distributed and centralised agent based bundling systems, Proceedings of the ninth international conference on Electronic commerce, August 19-22, 2007, Minneapolis, MN, USA
	Oktay Günlük , Lászlo Ladányi , Sven de Vries, A Branch-and-Price Algorithm and New Test Problems for Spectrum Auctions, Management Science, v.51 n.3, p.391-406, March 2005
	Peter Gradwell , Julian Padget, Markets vs auctions: Approaches to distributed combinatorial resource scheduling, Multiagent and Grid Systems, v.1 n.4, p.251-262, December 2005
	Alexander Babanov , John Collins , Maria Gini, Asking the right question: Risk and expectation in multiagent contracting, Artificial Intelligence for Engineering Design, Analysis and Manufacturing, v.17 n.3, p.173-186, June 2003
	Shantanu Biswas , Y. Narahari, Iterative Dutch combinatorial auctions, Annals of Mathematics and Artificial Intelligence, v.44 n.3, p.185-205, July 2005
	Amy Greenwald , Justin Boyan, Bidding Algorithms for Simultaneous Auctions: A Case Study, Autonomous Agents and Multi-Agent Systems, v.10 n.1, p.67-89, January 2005
	Terence Kelly, Combinatorial Auctions and Knapsack Problems, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.1280-1281, July 19-23, 2004, New York, New York
	Benoit Hudson , Tuomas Sandholm, Effectiveness of Query Types and Policies for Preference Elicitation in Combinatorial Auctions, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.386-393, July 19-23, 2004, New York, New York
	Séstien Lahaie , David C. Parkes, A modular framework for iterative combinatorial auctions, ACM SIGecom Exchanges, v.7 n.2, p.1-5, December 2008
	Peter Gradwell , Michel Oey , Reinier Timmer , Frances Brazier , Julian Padget, Engineering large-scale distributed auctions, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
	Shouxi Yang , Alberto Maria Segre , Bruno Codenotti, An optimal multiprocessor combinatorial auction solver, Computers and Operations Research, v.36 n.1, p.149-166, January, 2009
	Naoki Fukuta , Takayuki Ito, Short-time approximation on combinatorial auctions: a comparison on approximated winner determination algorithms, Proceedings of the 3rd international workshop on Data enginering issues in E-commerce and services: In conjunction with ACM Conference on Electronic Commerce (EC '07), p.26-33, June 12-12, 2007, San Diego, California
	Chun Wang , Hamada H. Ghenniwa , Weiming Shen, A winner determination algorithm for auction-based decentralized scheduling, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii
	Benito Mendoza , José M. Vidal, Bidding algorithms for a distributed combinatorial auction, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii
	Javier Larrosa , Federico Heras , Simon de Givry, A logical approach to efficient Max-SAT solving, Artificial Intelligence, v.172 n.2-3, p.204-233, February, 2008
	Güleser K. Demir , Maria Gini, Winner determination for combinatorial auctions for tasks with time and precedence constraints, Journal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology, v.18 n.3, p.267-280, August 2007
	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
	Joel Uckelman , Ulle Endriss, Winner determination in combinatorial auctions with logic-based bidding languages, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
	Sylvain Bouveret , Michel Lemaître, Computing leximin-optimal solutions in constraint networks, Artificial Intelligence, v.173 n.2, p.343-364, February, 2009
	Laureano F. Escudero , Mercedes Landete , Alfredo Marín, A branch-and-cut algorithm for the Winner Determination Problem, Decision Support Systems, v.46 n.3, p.649-659, February, 2009
	Alan Holland , Barry O'Sullivan, Weighted super solutions for constraint programs, Proceedings of the 20th national conference on Artificial intelligence, p.378-383, July 09-13, 2005, Pittsburgh, Pennsylvania
	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
	Martin Bichler , Pasha Shabalin , Alexander Pikovsky, A Computational Analysis of Linear Price Iterative Combinatorial Auction Formats, Information Systems Research, v.20 n.1, p.33-59, March 2009
	Kevin Leyton-Brown , Eugene Nudelman , Yoav Shoham, Empirical hardness models: Methodology and a case study on combinatorial auctions, Journal of the ACM (JACM), v.56 n.4, p.1-52, June 2009
	Emma Rollon , Javier Larrosa, Multi-Objective Propagation in Constraint Programming, Proceeding of the 2006 conference on ECAI 2006: 17th European Conference on Artificial Intelligence August 29 -- September 1, 2006, Riva del Garda, Italy, p.128-132, May 22, 2006
	Víctor Muòoz , Javier Murillo, CABRO: Winner Determination Algorithm for Single-unit Combinatorial Auctions, Proceeding of the 2008 conference on Artificial Intelligence Research and Development: Proceedings of the 11th International Conference of the Catalan Association for Artificial Intelligence, p.303-312, July 03, 2008
	William E. Walsh , Michael P. Wellman, Decentralized supply chain formation: a market protocol and competitive equilibrium analysis, Journal of Artificial Intelligence Research, v.19 n.1, p.513-567, July 2003
	Adrian Petcu , Boi Faltings , David C. Parkes, M-DPOP: faithful distributed implementation of efficient social choice problems, Journal of Artificial Intelligence Research, v.32 n.1, p.705-755, May 2008
	Akshat Kumar , Adrian Petcu , Boi Faltings, H-DPOP: using hard constraints for search space pruning in DCOP, Proceedings of the 23rd national conference on Artificial intelligence, p.325-330, July 13-17, 2008, Chicago, Illinois
	Federico Heras , Javier Larrosa , Albert Oliveras, MINIMAXSAT: an efficient weighted max-SAT solver, Journal of Artificial Intelligence Research, v.31 n.1, p.1-32, January 2008
	Radu Marinescu , Rina Dechter, Best-first AND/OR search for graphical models, Proceedings of the 22nd national conference on Artificial intelligence, p.1171-1176, July 22-26, 2007, Vancouver, British Columbia, Canada
	Thomas Sandholm, Making markets and democracy work: a story of incentives and computing, Proceedings of the 18th international joint conference on Artificial intelligence, p.1649-1671, August 09-15, 2003, Acapulco, Mexico
	Kevin Leyton-Brown , Eugene Nudelman , Galen Andrew , Jim McFadden , Yoav Shoham, A portfolio approach to algorithm select, Proceedings of the 18th international joint conference on Artificial intelligence, p.1542-1543, August 09-15, 2003, Acapulco, Mexico
	Yiming Ye , Yuhai Tu, Dynamics of coalition formation in combinatorial trading, Proceedings of the 18th international joint conference on Artificial intelligence, p.625-630, August 09-15, 2003, Acapulco, Mexico
	Dale Schuurmans , Finnegan Southey , Robert C. Holte, The exponentiated subgradient algorithm for heuristic Boolean programming, Proceedings of the 17th international joint conference on Artificial intelligence, p.334-341, August 04-10, 2001, Seattle, WA, USA
	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
	Tuomas Sandholm , Subhash Suri , Andrew Gilpin , David Levine, CABOB: a fast optimal algorithm for combinatorial auctions, Proceedings of the 17th international joint conference on Artificial intelligence, p.1102-1108, August 04-10, 2001, Seattle, WA, USA