Truth revelation in approximately efficient combinatorial auctions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Truth revelation in approximately efficient combinatorial auctions

Full text

Pdf (177 KB)

Source

Journal of the ACM (JACM) archive
Volume 49 , Issue 5 (September 2002) table of contents

Pages: 577 - 602

Year of Publication: 2002

ISSN:0004-5411

Authors

Daniel Lehmann	Hebrew University, Jerusalem, Israel
Liadan Ita Oćallaghan	Stanford University, Stanford, California
Yoav Shoham	Stanford University, Stanford, California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 28, Downloads (12 Months): 244, Citation Count: 78

Additional Information:

abstract 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/585265.585266 What is a DOI?

ABSTRACT

Some important classical mechanisms considered in Microeconomics and Game Theory require the solution of a difficult optimization problem. This is true of mechanisms for combinatorial auctions, which have in recent years assumed practical importance, and in particular of the gold standard for combinatorial auctions, the Generalized Vickrey Auction (GVA). Traditional analysis of these mechanisms---in particular, their truth revelation properties---assumes that the optimization problems are solved precisely. In reality, these optimization problems can usually be solved only in an approximate fashion. We investigate the impact on such mechanisms of replacing exact solutions by approximate ones. Specifically, we look at a particular greedy optimization method. We show that the GVA payment scheme does not provide for a truth revealing mechanism. We introduce another scheme that does guarantee truthfulness for a restricted class of players. We demonstrate the latter property by identifying natural properties for combinatorial auctions and showing that, for our restricted class of players, they imply that truthful strategies are dominant. Those properties have applicability beyond the specific auction studied.

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. Archer , É. Tardos, Truthful Mechanisms for One-Parameter Agents, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.482, October 14-17, 2001
	2	Bartal, Y., Gonen, R., and Nisan, N. 2002. Incentive compatible multi unit combinatorial auctions. Tech. Rep. TR-2002-36, Leibniz Center for Research in Computer Science, School of Computer Science and Engineering, Hebrew University, Jerusalem, Israel. June. (Presented at Dagstuhl workshop on Electronic Market Design.)
	3	Boutilier, C., and Hoos, H. H. 2001. Bidding languages for combinatorial auctions. In Proceedings of IJCAI'01 (Seattle, Wash.). Morgan-Kaufmann, San Mateo, Calif.
	4	Clarke, E. H. 1971. Multipart pricing of public goods. Public Choice 11, 17--33.
	5	Cramton, P. C. 1997. The FCC spectrum auction: An early assessment. J. Econ. Manage. Strat. 6, 3, 431--495.
	6	DeMartini, C., Kwasnica, A. M., Ledyard, J. O., and Porter, D. 1999. A new and improved design for multi-object iterative auctions. Social Science Working Paper 1054, California Institute of Technology, Pasadena, Calif.
	7	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
	8	Rica Gonen , Daniel Lehmann, Optimal solutions for multi-unit combinatorial auctions: branch and bound heuristics, Proceedings of the 2nd ACM conference on Electronic commerce, p.13-20, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352873]
	9	Groves, T. 1973. Incentives in teams. Econometrica 41, 617--631.
	10	Halldórsson, M. M. 1999. Approximation of weighted independent set and hereditary subset problems. In Proceedings of COCOON'99. Lecture Notes in Computer Science, vol. 1627. Springer-Verlag, New York.
	11	Halldórsson, M. M. 2000. Approximation of weighted independent set and hereditary subset problems. J. Graph Algori. Appl. 4, 1, 1--16.
	12	Håstad, J. 1999. Clique is hard to approximate within n1−ε. Acta Math. 182, 105--142.
	13	Kamal Jain , Vijay Vazirani, Applications of approximation algorithms to cooperative games, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.364-372, July 2001, Hersonissos, Greece [doi>10.1145/380752.380825]
	14	Karp, R. M. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds. Plenum Press, New York, pp. 85--103.
	15	Krishna, V., and Perry, M. 1998. Efficient mechanism design. Available at http://www.ma.huji.ac. il/∼motty.
	16	Benny Lehmann , Daniel Lehmann , Noam Nisan, Combinatorial auctions with decreasing marginal utilities, Proceedings of the 3rd ACM conference on Electronic Commerce, p.18-28, October 14-17, 2001, Tampa, Florida, USA [doi>10.1145/501158.501161]
	17	Daniel Lehmann , Liadan I O''Callaghan , Yoav Shoham, Truth Revelation in Rapid, Approximately Efficient Combinatorial Auctions, Stanford University, Stanford, CA, 1999
	18	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]
	19	MacKie-Mason, J. K., and Varian, H. R. 1994. Generalized Vickrey auctions. Working paper, Univ. Michigan. July.
	20	Mas-Colell, A., Whinston, M. D., and Green, J. R. 1995. Microeconomic Theory. Oxford University Press, New York, Oxford.
	21	McMillan, J. 1994. Selling spectrum rights. J. Econ. Pers. 68, 145--162.
	22	Milgrom, P. 2000. Putting auction theory to work: The simultaneous ascending auction. Journal of Political Economy 108, 2, 245--272.
	23	Monderer, D., Kfir-Dahav, N. E., and Tennenholtz, M. 2000. Mechanism design for resource bounded agents. In Proceedings of ICMAS-2000.
	24	Monderer, D., and Tennenholtz, M. 2000. Asymptotically optimal multi-object auctions for risk-averse agents. Available at http://ie.technion.ac.il/dov.phtml.
	25	Ahuva Mu'alem , Noam Nisan, Truthful approximation mechanisms for restricted combinatorial auctions: extended abstract, Eighteenth national conference on Artificial intelligence, p.379-384, July 28-August 01, 2002, Edmonton, Alberta, Canada
	26	Myerson, R. B. 1981. Optimal auction design. Math. Oper. Res. 6, 58--73.
	27	Nisan, N. 1999. Algorithms for selfish agents. In Symposium on Theoretical Aspects in Computer Science (Trier, Germany), 1--15.
	28	Noam Nisan, Bidding and allocation in combinatorial auctions, Proceedings of the 2nd ACM conference on Electronic commerce, p.1-12, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352872]
	29	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]
	30	Noam Nisan , Amir Ronen, Computationally feasible VCG mechanisms, Proceedings of the 2nd ACM conference on Electronic commerce, p.242-252, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352898]
	31	Rothkopf, M. H. 1983. Bidding theory: the phenomena to be modeled. In Auctions, Bidding and Contracting: Uses and Theory, R. Engelbrecht-Wiggans, M. Shubik, and R. Stark, Eds. New York University Press, New York, pp. 105--120.
	32	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]
	33	Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]
	34	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
	35	Tuomas Sandholm, eMediator: a next generation electronic commerce server, Proceedings of the fourth international conference on Autonomous agents, p.341-348, June 03-07, 2000, Barcelona, Spain [doi>10.1145/336595.337522]
	36	Tuomas Sandholm, Algorithm for optimal winner determination in combinatorial auctions, Artificial Intelligence, v.135 n.1-2, p.1-54, 02/01/2002 [doi>10.1016/S0004-3702(01)00159-X]
	37	Varian, H. R. 1995. Economic mechanism design for computerized agents. In Proceedings of the 1st Usenix Conference on Electronic Commerce. New York.
	38	Vickrey, W. S. 1961. Counterspeculation, auctions and competitive sealed tenders. J. Finance 16, 8--37.

CITED BY 78

	Vincent Conitzer , Tuomas Sandholm, Self-interested automated mechanism design and implications for optimal combinatorial auctions, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA
	Anshul Kothar , David C. Parke , Subhash Sur, Approximately-strategyproof and tractable multi-unit auctions, Proceedings of the 4th ACM conference on Electronic commerce, p.166-175, June 09-12, 2003, San Diego, CA, USA
	Kenji Terada , Makoto Yokoo, False-name-proof multi-unit auction protocol utilizing greedy allocation based on approximate evaluation values, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia
	Kate Larson , Tuomas Sandholm, Miscomputing ratio: social cost of selfish computing, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia
	Chaki Ng , David C. Parkes , Margo Seltzer, Virtual worlds: fast and strategyproof auctions for dynamic resource allocation, Proceedings of the 4th ACM conference on Electronic commerce, June 09-12, 2003, San Diego, CA, USA
	Moshe Babaioff , Ron Lavi , Elan Pavlov, Single-value combinatorial auctions and implementation in undominated strategies, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1054-1063, January 22-26, 2006, Miami, Florida
	Vincent Conitzer , Tuomas Sandholm, Expressive negotiation over donations to charities, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA
	Aranyak Mehta , Vijay V. Vazirani, Randomized truthful auctions of digital goods are randomizations over truthful auctions, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA
	Moshe Babaioff , William E. Walsh, Incentive-compatible, budget-balanced, yet highly efficient auctions for supply chain formation, Decision Support Systems, v.39 n.1, p.123-149, March 2005
	Shahar Dobzinski , Noam Nisan , Michael Schapira, Approximation algorithms for combinatorial auctions with complement-free bidders, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Anshul Kothari , David C. Parkes , Subhash Suri, Approximately-strategyproof and tractable multiunit auctions, Decision Support Systems, v.39 n.1, p.105-121, March 2005
	Ahuva Mu'alem, On decentralized incentive compatible mechanisms, Proceedings of the 6th ACM conference on Electronic commerce, p.240-248, June 05-08, 2005, Vancouver, BC, Canada
	Nikhil R. Devanur , Milena Mihail , Vijay V. Vazirani, Strategyproof cost-sharing mechanisms for set cover and facility location games, Decision Support Systems, v.39 n.1, p.11-22, March 2005
	Ron Lavi , Noam Nisan, Online ascending auctions for gradually expiring items, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Ming-Yang Kao , Xiang-Yang Li , WeiZhao Wang, Towards truthful mechanisms for binary demand games: a general framework, Proceedings of the 6th ACM conference on Electronic commerce, p.213-222, June 05-08, 2005, Vancouver, BC, Canada
	Amir Ronen , Daniel Lehmann, Nearly optimal multi attribute auctions, Proceedings of the 6th ACM conference on Electronic commerce, p.279-285, June 05-08, 2005, Vancouver, BC, Canada
	Thomas C. O'Connell , Richard E. Stearns, Mechanism design for software agents with complete information, Decision Support Systems, v.39 n.2, p.197-217, April 2005
	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
	Michael Saks , Lan Yu, Weak monotonicity suffices for truthfulness on convex domains, Proceedings of the 6th ACM conference on Electronic commerce, p.286-293, June 05-08, 2005, Vancouver, BC, Canada
	Tuomas Sandholm , Subhash Suri, BOB: improved winner determination in combinatorial auctions and generalizations, Artificial Intelligence, v.145 n.1-2, p.33-58, April 2003
	Kate Larson , Tuomas Sandholm, Mechanism design and deliberative agents, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands
	Moshe Babaioff , William E. Walsh, Incentive-compatible, budget-balanced, yet highly efficient auctions for supply chain formation, Proceedings of the 4th ACM conference on Electronic commerce, p.64-75, June 09-12, 2003, San Diego, CA, USA
	Avrim Blum , Jeffrey Jackson , Tuomas Sandholm , Martin Zinkevich, Preference Elicitation and Query Learning, The Journal of Machine Learning Research, 5, p.649-667, 12/1/2004
	Shahar Dobzinski , Noam Nisan , Michael Schapira, Truthful randomized mechanisms for combinatorial auctions, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Tokuro Matsuo , Takayuki Ito , Robert W. Day , Toramatsu Shintani, A robust combinatorial auction mechanism against shill bidders, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan
	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
	Weizhao Wang , Xiang-Yang Li , Stephan Eidenbenz , Yu Wang, OURS: optimal unicast routing systems in non-cooperative wireless networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA
	Daniel Golovin, Stochastic packing-market planning, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA
	Shahar Dobzinski , Noam Nisan, Limitations of VCG-based mechanisms, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Yu-Kwong Kwok , Kai Hwang , ShanShan Song, Selfish Grids: Game-Theoretic Modeling and NAS/PSA Benchmark Evaluation, IEEE Transactions on Parallel and Distributed Systems, v.18 n.5, p.621-636, May 2007
	Vincent Conitzer , Tuomas Sandholm, Failures of the VCG mechanism in combinatorial auctions and exchanges, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan
	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
	Takayuki Ito , David C. Parkes, Instantiating the contingent bids model of truthful interdependent value auctions, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan
	Kate Larson, Reducing costly information acquisition in auctions, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan
	Ron Lavi , Chaitanya Swamy, Truthful mechanism design for multi-dimensional scheduling via cycle monotonicity, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA
	Maria-Florina Balcan , Avrim Blum , Yishay Mansour, Item pricing for revenue maximization, Proceedings of the 9th ACM conference on Electronic commerce, July 08-12, 2008, Chicago, Il, USA
	Shahar Dobzinski , Noam Nisan, Mechanisms for multi-unit auctions, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA
	Georg Gottlob , Gianluigi Greco, On the complexity of combinatorial auctions: structured item graphs and hypertree decomposition, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA
	Mira Gonen , Rica Gonen , Elan Pavlov, Generalized trade reduction mechanisms, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA
	Yossi Azar , Iftah Gamzu , Shai Gutner, Truthful unsplittable flow for large capacity networks, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	Naoki Fukuta , Takayuki Ito, Towards Better Approximation of Winner Determination for Combinatorial Auctions with Large Number of Bids, Proceedings of the IEEE/WIC/ACM international conference on Intelligent Agent Technology, p.618-621, December 18-22, 2006
	Shantanu Biswas , Y. Narahari, Iterative Dutch combinatorial auctions, Annals of Mathematics and Artificial Intelligence, v.44 n.3, p.185-205, July 2005
	David C. Parkes, Auction design with costly preference elicitation, Annals of Mathematics and Artificial Intelligence, v.44 n.3, p.269-302, July 2005
	Ron Lavi, Searching for the possibility: impossibility border of truthful mechanism design, ACM SIGecom Exchanges, v.7 n.1, p.25-29, December 2007
	Ofer Dekel , Felix Fischer , Ariel D. Procaccia, Incentive compatible regression learning, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.884-893, January 20-22, 2008, San Francisco, California
	Moshe Babaioff , Nicole Immorlica , Robert Kleinberg, Matroids, secretary problems, and online mechanisms, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.434-443, January 07-09, 2007, New Orleans, Louisiana
	Rajdeep K. Dash , Nicholas R. Jennings , David C. Parkes, Computational-Mechanism Design: A Call to Arms, IEEE Intelligent Systems, v.18 n.6, p.40-47, November 2003
	Ahuva Mu'alem , Michael Schapira, Mechanism design over discrete domains, Proceedings of the 9th ACM conference on Electronic commerce, July 08-12, 2008, Chicago, Il, USA
	Jochen Stöβer , Dirk Neumann, GreedEx--a scalable clearing mechanism for utility computing, Electronic Commerce Research, v.8 n.4, p.235-253, December 2008
	Maria-Florina Balcan , Avrim Blum , Yishay Mansour, Item pricing for revenue maximization, ACM SIGecom Exchanges, v.7 n.3, p.1-4, November 2008
	Ureil Feige , Nicole Immorlica , Vahab Mirrokni , Hamid Nazerzadeh, A combinatorial allocation mechanism with penalties for banner advertising, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China
	Shaheen S. Fatima , Michael Wooldridge , Nicholas R. Jennings, Approximate and online multi-issue negotiation, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii
	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
	Benito Mendoza , José M. Vidal, Approximate bidding algorithms for a distributed combinatorial auction, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
	Xia Zhou , Sorabh Gandhi , Subhash Suri , Haitao Zheng, eBay in the Sky: strategy-proof wireless spectrum auctions, Proceedings of the 14th ACM international conference on Mobile computing and networking, September 14-19, 2008, San Francisco, California, USA
	Juncheng Jia , Qian Zhang , Qin Zhang , Mingyan Liu, Revenue generation for truthful spectrum auction in dynamic spectrum access, Proceedings of the tenth ACM international symposium on Mobile ad hoc networking and computing, May 18-21, 2009, New Orleans, LA, USA
	Moshe Babaioff , Ron Lavi , Elan Pavlov, Single-value combinatorial auctions and algorithmic implementation in undominated strategies, Journal of the ACM (JACM), v.56 n.1, p.1-32, January 2009
	Baharak Rastegari , Anne Condon , Kevin Leyton-Brown, Stepwise randomized combinatorial auctions achieve revenue monotonicity, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.738-747, January 04-06, 2009, New York, New York
	Weizhao Wang , Xiang-Yang Li, Towards truthful mechanisms for binary demand games: a general framework, Proceedings of the 20th national conference on Artificial intelligence, p.1632-1633, July 09-13, 2005, Pittsburgh, Pennsylvania
	Liad Blumrosen, Implementing the maximum of monotone algorithms, Proceedings of the 22nd national conference on Artificial intelligence, p.30-35, July 22-26, 2007, Vancouver, British Columbia, Canada
	Baharak Rastegari , Anne Condon , Kevin Leyton-Brown, Revenue monotonicity in combinatorial auctions, Proceedings of the 22nd national conference on Artificial intelligence, p.122-127, July 22-26, 2007, Vancouver, British Columbia, Canada
	Moshe Babaioff , Ron Lavi , Elan Pavlov, Mechanism design for single-value domains, Proceedings of the 20th national conference on Artificial intelligence, p.241-247, July 09-13, 2005, Pittsburgh, Pennsylvania
	Vincent Conitzer , Tuomas Sandholm , Paolo Santi, Combinatorial auctions with k-wise dependent valuations, Proceedings of the 20th national conference on Artificial intelligence, p.248-254, July 09-13, 2005, Pittsburgh, Pennsylvania
	Vincent Conitzer , Thomas Sandholm, Expressive negotiation in settings with externalities, Proceedings of the 20th national conference on Artificial intelligence, p.255-260, 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
	Jing Chen , Silvio Micali, A new approach to auctions and resilient mechanism design, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	David C. Parkes , Grant Schoenebeck, GROWRANGE: anytime VCG-based mechanisms, Proceedings of the 19th national conference on Artifical intelligence, p.34-41, July 25-29, 2004, San Jose, California
	Leon Yang Chu, Truthful Bundle/Multiunit Double Auctions, Management Science, v.55 n.7, p.1184-1198, July 2009
	Moshe Babaioff , Ron Lavi , Elan Pavlov, Impersonation-based mechanisms, Proceedings of the 21st national conference on Artificial intelligence, p.592-597, July 16-20, 2006, Boston, Massachusetts
	Ariel D. Procaccia , Moshe Tennenholtz, Approximate mechanism design without money, Proceedings of the tenth ACM conference on Electronic commerce, July 06-10, 2009, Stanford, California, USA
	Moshe Babaioff , Noam Nisan, Concurrent auctions across the supply chain, Journal of Artificial Intelligence Research, v.21 n.1, p.595-629, January 2004
	Noam Nisan , Amir Ronen, Computationally feasible VCG mechanisms, Journal of Artificial Intelligence Research, v.29 n.1, p.19-47, May 2007
	Alan Holland , Barry O'Sullivan, Truthful risk-managed combinatorial auctions, Proceedings of the 20th international joint conference on Artifical intelligence, p.1315-1320, January 06-12, 2007, Hyderabad, India
	Nathanaël Hyafil , Craig Boutilier, Mechanism design with partial revelation, Proceedings of the 20th international joint conference on Artifical intelligence, p.1333-1340, January 06-12, 2007, Hyderabad, India
	Makoto Yokoo , Atsushi Iwasaki, Making VCG more robust in combinatorial auctions via sub modular approximation, Proceedings of the 22nd national conference on Artificial intelligence, p.1679-1682, 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
	Makoto Yokoo, Characterization of strategy/false-name proof combinatorial auction protocols: price-oriented, rationing-free protocol, Proceedings of the 18th international joint conference on Artificial intelligence, p.733-739, August 09-15, 2003, Acapulco, Mexico