Simon Parsons
Skip Abstract Section
Abstract
There is a veritable menagerie of auctions—single-dimensional, multi-dimensional, single-sided, double-sided, first-price, second-price, English, Dutch, Japanese, sealed-bid—and these have been extensively discussed and analyzed in the economics literature. The main purpose of this article is to survey this literature from a computer science perspective, primarily from the viewpoint of computer scientists who are interested in learning about auction theory, and to provide pointers into the economics literature for those who want a deeper technical understanding. In addition, since auctions are an increasingly important topic in computer science, we also look at work on auctions from the computer science literature. Overall, our aim is to identifying what both these bodies of work these tell us about creating electronic auctions.
- An, N., Elmaghraby, W., and Keskinocak, P. 2005. Bidding strategies and their impact on revenues in combinatorial auctions. J. Rev. Pric. Manage. 3, 4, 337--357.Google Scholar
Cross Ref
- Andersson, A., Tenhunen, M., and Ygge, F. 2000. Integer programming for combinatorial auction winner determination. In Proceedings of the 4th International Conference on Multiagent Systems, E. Durfee, S. Kraus, H. Nakashima, and M. Tambe, Eds. IEEE Computer Society, 39--48. Google ScholarDigital Library
- Archer, A., Papadimitriou, C., Talwar, K., and Tardos, E. 2003. An approximate truthful mechanism for combinatorial auctions with single parameter agent. Internet Math. 1, 2, 129--150.Google ScholarCross Ref
- Ausubel, L. M. 1997. An efficient ascending-bid auction for multiple objects. Working paper 97-06, Department of Economics, University of Maryland.Google Scholar
- Ausubel, L. M. and Cramton, P. 1998. Demand reduction and inefficiency in multi-unit auctions. Working paper 96-07, Department of Economics, University of Maryland.Google Scholar
- Ausubel, L. M. and Milgrom, P. 2001. Ascending auctions with package bidding. Working paper, Department of Economics, University of Maryland.Google Scholar
- Babaioff, M. and Walsh, W. 2005. Incentive-compatible, budget-balanced, yet highly efficient auctions for supply chain formation. Decision Support Syst. 39, 123--149. Google ScholarDigital Library
- Bajari, P. and Ye, L. 2003. Deciding between competition and collusion. Rev. Econ. Stat. 85, 4, 971--989.Google ScholarCross Ref
- BBC News. 2001. Sotheby's and Christie's chiefs charged. BBC News. http://news.bbc.co.uk/onthisday/hi/dates/stories/may/2/newsid_2480000/2480711.stm.Google Scholar
- Bichler, M. 2000. An experimental analysis of multi-attribute auctions. Decision Support Syst. 29, 3, 249--268. Google ScholarDigital Library
- Bichler, M. 2001. The Future of e-Markets: Multi-Dimensional Market Mechanisms. Cambridge University Press, Cambridge, UK. Google ScholarDigital Library
- Bichler, M. and Kalagnanam, J. 2005. Configurable offers and winner determination in multi-attribute auctions. Europ. J. Oper. Res. 160, 380--394.Google ScholarCross Ref
- Bichler, M., Lee, J., Kim, C., and Lee, H. 2001. Design and implementation of an intelligent decision analysis system for e-sourcing. In Proceedings of the International Conference on Artificial Intelligence.Google Scholar
- Bogdanovych, A. 2008. Virtual institutions. Ph.D. dissertation, University of Technology Sydney.Google Scholar
- Boutilier, C. and Hoos, H. H. 2001. Bidding languages for combinatorial auctions. In Proceedings of the 17th International Joint Conference on Artificial Intelligence. Morgan-Kaufmann, San Francisco, CA, 1211--1217. Google ScholarDigital Library
- Branco, F. 1997. The design of multidimensional auctions. RAND J. Econ. 28, 1, 63--81.Google ScholarCross Ref
- Bulow, J. and Klemperer, P. 2002. Prices and the winner's curse. RAND J. Econ. 33, 1, 1--21.Google ScholarCross Ref
- Bussmann, S., Jennings, N., and Wooldridge, M. 2004. Multiagent Systems for Manufacturing Control: A Design Methodology. Series on Agent Technology. Springer-Verlag, Berlin, Germany. Google ScholarDigital Library
- Bussmann, S. and Schild, K. 2000. Self-organizing manufacturing control: An industrial application of agent technology. In Proceedings of the 4th International Conference on Multiagent Systems, E. Durfee, S. Kraus, H. Nakashima, and M. Tambe, Eds. IEEE Computer Society, 87--94. Google ScholarDigital Library
- Carney, T. F. 1971. The Economies of Antiquity. Coronado Press, Lawrence, KS.Google Scholar
- Cassady, Jr., R. 1967. Auctions and Auctioneering. University of California Press, Berkeley, CA.Google Scholar
- Cerquides, J., Endriss, U., Giovannucci, A., and Rodriguez-Aguilar, J. A. 2007a. Bidding languages and winner determination for mixed multi-unit combinatorial auctions. In Proceedings of the 20th International Joint Conference on Artificial Intelligence, M. M. Veloso, Ed. Hyderabad, India, 1221--1227. Google ScholarDigital Library
- Cerquides, J., Reyes-Moro, A., Rodriguez-Aguilar, J. A., and López-Sánchez, M. 2007b. Enabling assisted strategic negotiations in actual-world procurement scenarios. Electron. Comm. Res. 7, 3/4, 189--220. Google ScholarDigital Library
- Che, Y. K. 1993. Design competition through multidimensional auctions. RAND J. Econ. 24, 4, 668--680.Google ScholarCross Ref
- Clarke, E. H. 1971. Multipart pricing of public goods. Public Choice 11, 17--33.Google ScholarCross Ref
- Cliff, D. 1997. Minimal-intelligence agents for bargaining behaviours in market-based environments. Tech. rep. HP-97-91, Hewlett-Packard Research Laboratories, Bristol, England.Google Scholar
- Conitzer, V. 2008. Mechanism design for MAS. Course at the Dubai Agents and Multiagent Systems School.Google Scholar
- Conitzer, V. and Sandholm, T. 2002. Complexity of mechanism design. In Proceedings of the 18th Conference in Uncertainty in Artificial Intelligence, A. Darwiche and N. Friedman, Eds. Morgan, Kaufmann, San Francisco, CA. Google ScholarDigital Library
- Conitzer, V. and Sandholm, T. 2004. Computational criticisms of the revelation principle. In Proceedings of the 5th ACM Conference on Electronic Commerce. ACM, New York. Google ScholarDigital Library
- Conitzer, V. and Sandholm, T. 2006. Failures of the VCG mechanism in combinatorial auctions and exchanges. In Proceedings of the 5th International Conference on Autonomous Agents and Multiagent Systems, H. Nakashima, M. P. Wellman, G. Weiss, and P. Stone, Eds. ACM, New York, 521--528. Google ScholarDigital Library
- Cramton, P. 1997. The FCC spectrum auctions: An early assessment. J. Econ. Manage. Strat. 6, 3, 431--495.Google ScholarCross Ref
- Cramton, P. 2002. Spectrum auctions. In Handbook of Telecommunications Economics, M. Cave, S. Majumdar, and I. Vogelsang, Eds., Elsevier, Amsterdam, Chapter 14, 605--639.Google Scholar
- Cramton, P. and Schwartz, J. 1998. Collusive bidding in the FCC spectrum auctions. Working paper, University of Maryland.Google Scholar
- Cramton, P. and Schwartz, J. 2000. Collusive bidding: Lessons from the FCC spectrum auctions. J. Regulat. Econ. 17, 3, 229--252.Google ScholarCross Ref
- Cramton, P., Shoham, Y., and Steinberg, R., Eds. 2006. Combinatorial Auctions. The MIT Press, Cambridge, MA. Google ScholarDigital Library
- Das, R., Hanson, J. E., Kephart, J. O., and Tesauro, G. 2001. Agent-human interactions in the continuous double auction. In Proceedings of the 17th International Joint Conference on Artificial Intelligence, B. Nebel, Ed. Morgan-Kaufmann, San Francisco, CA, 1169--1187. Google ScholarDigital Library
- Dash, R. K., Parkes, D. C., and Jennings, N. R. 2003. Computational mechanism design: A call to arms. IEEE Intell. Syst. 18, 6, 40--47. Google ScholarDigital Library
- Dash, R. K., Ramchurn, S. D., and Jennings, N. R. 2004. Trust-based mechanism design. In Proceedings of the 3rd International Joint Conference on Autonomous Agents and Multiagent Systems, N. R. Jennings, C. Sierra, L. Sonenberg, and M. Tambe, Eds. ACM, New York, 748--755. Google ScholarDigital Library
- de Vries, S. and Vohra, R. 2003. Combinatorial auctions: A survey. INFORMS J. Comput. 15, 3, 284--309. Google ScholarDigital Library
- Economides, N. and Schwartz, R. A. 1995. Electronic call market trading. J. Portfolio Manage. 21, 3, 10--18.Google ScholarCross Ref
- Engel, Y., Wellman, M. P., and Lochner, K. M. 2006. Bid expressiveness and clearing algorithms in multiattribute double auctions. In Proceedings of the 7th ACM Conference on Electronic Commerce. ACM, New York, 110--119. Google ScholarDigital Library
- Engelbrecht-Wiggans, R. 1980. Auctions and bidding models: A survey. Manage. Sci. 26, 119--142.Google Scholar
- Fink, E., Johnson, J., and Hu, J. 2004. Exchange market for complex goods: Theory and experiments. Netnomics 6, 1, 21--42. Google ScholarDigital Library
- Friedman, D. 1993. The double auction institution: A survey. In The Double Auction Market: Institutions, Theories and Evidence, Perseus Publishing, Cambridge, MA, Chapter 1, 3--25.Google Scholar
- Friedman, D. and Rust, J., Eds. 1993a. The Double Auction Market: Institutions, Theories and Evidence. Santa Fe Institute Studies in the Sciences of Complexity, Perseus Publishing, Cambridge, MA.Google Scholar
- Friedman, D. and Rust, J. 1993b. Preface. In The Double Auction Market: Institutions, Theories and Evidence, Perseus Publishing, Cambridge, MA, 199--219.Google Scholar
- Friedman, E. J. and Parkes, D. C. 2003. Pricing wifi at Starbucks: Issues in online mechanism design. In Proceedings of the 4th ACM Conference on Electronic Commerce. ACM, New York, 240--241. Google ScholarDigital Library
- Fujishima, Y., McAdams, D., and Shoham, Y. 1999. Speeding up ascending bid auctions. In Proceedings of the 16th International Joint Conference on Artificial Intelligence, T. Dean, Ed. 548--553. Google ScholarDigital Library
- García, B. M. and Vidal, J. M. 2007. Bidding algorithms for a distributed combinatorial auction. In Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems, E. H. Durfee, M. Yokoo, M. N. Huhns, and O. Shehory, Eds. IFAAMAS, 694--701. Google ScholarDigital Library
- GE. 2000. Letter to Share owners. Annual report, General Electric Corporation.Google Scholar
- Gerding, E., McBurney, P., Niu, J., Parsons, S., and Phelps, S. 2007a. Overview of CAT: A market design competition. Tech. rep. ULCS-07-006, Department of Computer Science, University of Liverpool.Google Scholar
- Gerding, E. H., Rogers, A., Dash, R. K., and Jennings, N. R. 2007b. Sellers competing for buyers in online markets: Reserve prices, shill bids, and auction fees. In Proceedings of the 20th International Joint Conference on Artificial Intelligence, M. M. Veloso, Ed. Hyderabad, India, 1287--1293. Google ScholarDigital Library
- Gibbard, A. 1973. Manipulation of voting schemes: A general result. Econometrica 41, 587--602.Google ScholarCross Ref
- Giovannucci, A., Rodríguez-Aguilar, J. A., Cerquides, J., and Endriss, U. 2007. On the winner determination problem in mixed multi-unit combinatorial auctions. In Proceedings of the 6th International Joint Conference on Autonomous Agents and Multi-Agent Systems, E. H. Durfee, M. Yokoo, M. N. Huhns, and O. Shehory, Eds. IFAAMAS, 710--717. Google ScholarDigital Library
- Giovannucci, A., Rodríguez-Aguilar, J. A., Reyes, A., Noria, F. X., and Cerquides, J. 2004. Towards automated procurement via agent-aware negotiation support. In Proceedings of the 3rd International Joint Conference on Autonomous Agents and Multiagent Systems, ACM, New York, 244--251. Google ScholarDigital Library
- Giovannucci, A., Vinyals, M., Rodríguez-Aguilar, J. A., and Cerquides, J. 2008. Computationally-efficient winner determination for mixed multi-unit combinatorial auctions. In Proceedings of the 7th International Joint Conference on Autonomous Agents and Multi-agent Systems, L. Padgham, D. Parkes, J. Müller, and S. Parsons, Eds. IFAAMAS, 1071--1078. Google ScholarDigital Library
- Gjerstad, S. and Dickhaut, J. 1998. Price formation in double auctions. Games Econ. Behaviour 22, 1--19.Google ScholarCross Ref
- Goeree, J. K. and Offerman, T. 2004. The Amsterdam auction. Ecomometrica 72, 1, 281--294.Google ScholarCross Ref
- Goiten, S. D. 1967. A Mediterranean Society: The Jewish Communities of the Arab World as Portrayed in the Documents of the Cairo Geniza. Vol. 1, Economic Foundations. University of California Press, Berkeley and Los Angeles.Google Scholar
- Gonen, R. and Lehmann, D. 2000. Optimal solutions for multi-unit combinatorial auctions: Branch and bound heuristics. In Proceedings of the 2nd ACM Conference on Electronic Commerce. ACM, New York, 13--20. Google ScholarDigital Library
- Gong, J. 2002. Exchanges for complex commodities: Search for optimal matches. M.S. dissertation. University of South Florida.Google Scholar
- Graham, D. A. and Marshall, R. C. 1987. Collusive bidder behaviour at single-object second-price and English auctions. J. Polit. Econ. 95, 579--599.Google ScholarCross Ref
- Green, J. R. and Laffont, J.-J. 1979. On coalition incentive compatibility. Rev. Econ. Stud. 46, 243--254.Google ScholarCross Ref
- Greenwald, A. and Stone, P. 2001. Autonomous bidding agents in the Trading Agent Competition. IEEE Internet Comput. 5, 2, 52--60. Google ScholarDigital Library
- Greenwald, A. R. and Kephart, J. O. 1999. Shopbots and pricebots. In Proceedings of the 16th International Joint Conference on Artificial Intelligence, T. Dean, Ed. Stockholm, Sweden, 506--511. Google ScholarDigital Library
- Groves, T. 1973. Incentives in teams. Econometrica 41, 617--631.Google ScholarCross Ref
- Hansell, S. 2004. Google's slow search for a good share price. New York Times: Business Day.Google Scholar
- Hasbrouck, J., Sofianos, G., and Sosebess, D. 1993. New York Stock Exchange systems and trading procedures. Working paper 93-01, New York Stock Exchange.Google Scholar
- Healey, C. G., Amant, R. S., and Chang, J. 2001. Assisted visualization of e-commerce auction agents. In Proceedings of Graphics Interface. 201--208. Google ScholarDigital Library
- Hoos, H. H. and Boutilier, C. 2000. Solving combinatorial auctions using stochastic local search. In Proceedings of the 17th National Conference on Artificial Intelligence. AAAI Press, 22--29. Google ScholarDigital Library
- Huberman, B. A. and Clearwater, S. H. 1995. A multi-agent system for controlling building environments. In Proceedings of the 1st International Conference on Multiagent Systems, V. R. Lesser and L. Gasser, Eds. The MIT Press, Cambridge, MA, 171--176.Google Scholar
- Hunsberger, L. and Grosz, B. 2000. A combinatorial auction for collaborative planning. In Proceedings of the 4th International Conference on Multiagent Systems, E. Durfee, S. Kraus, H. Nakashima, and M. Tambe, Eds. IEEE Computer Society, 151--158. Google ScholarDigital Library
- Hurwicz, L. 1972. On informationally decentralized systems. In Decision and Organisation: A Volume in Honour of Jacob Marchak, C. McGuire and R. Radner, Eds. North-Holland.Google Scholar
- Hurwicz, L. 1975. On the existence of allocation systems whose manipulative Nash equilibria are Pareto optimal. Unpublished manuscript.Google Scholar
- Hurwicz, L. and Walker, M. 1990. On the generic nonoptimality of dominant-strategy allocation mechanisms: A general theorem that includes pure exchange economies. Econometrica 58, 683--704.Google ScholarCross Ref
- Jackson, M. O. 2003. Mechanism theory. In Optimization and Operations Research, U. Devigs, Ed. The Encyclopedia of Life Support Science. EOLSS Publishers, Oxford, UK.Google Scholar
- Jennings, N. and Bussmann, S. 2003. Agent-based control systems. IEEE Control Syst. Mag. 23, 3, 61--74.Google ScholarCross Ref
- Kahn, A. E., Cramton, P. C., Porter, R. H., and Tabors, R. D. 2001. Pricing in the California power exchange electricity market: Should California switch from uniform pricing to pay-as-bid pricing? Blue Ribbon Panel report, commissioned by the California Power Exchange.Google Scholar
- Kalagnanam, J., Davenport, A., and Lee, H. 2000. Computational aspects of clearing continuous call double auctions with assignment constraints and indivisible demand. Tech. rep. RC21660(97613), IBM.Google Scholar
- Kalagnanam, J. and Parkes, D. C. 2004. Auctions, bidding and exchange design. In Handbook of Quantitative Supply Chain Analysis: Modeling in the E-Business Era, D. Simchi-Levi, S. D. Wu, and M. Shen, Eds. International Series in Operations Research and Management Science. Kluwer, Chapter 5.Google Scholar
- Kelly, F. and Stenberg, R. 2000. A combinatorial auction with multiple winners for universal service. Manage. Sci. 46, 4, 586--596. Google ScholarDigital Library
- Klemperer, P. 1998. Auctions with almost common values: The “wallet game” and its applications. Europ. Econ. Rev. 42, 3--5, 757--769.Google ScholarCross Ref
- Klemperer, P. 2002a. Auction theory: A guide to the literature. J. Econ. Surv. 13, 3, 227--286. (Reprinted as Chapter 1 of Klemperer{2004}).Google ScholarCross Ref
- Klemperer, P. 2002b. How (not) to run auctions: The European 3G telecom auctions. European Econ. Rev. 46, 4/5, 829--845.Google ScholarCross Ref
- Klemperer, P. 2002c. What really matters in auction design. J. Econ. Perspec. 16, 169--189.Google ScholarCross Ref
- Klemperer, P. 2004. Auctions: Theory and Practice. Princeton University Press.Google ScholarCross Ref
- Lee, J. 2002. Making losers of auction winners. The New York Times.Google Scholar
- Lee, J., Bichler, M., Verma, S., and Lee, H. 2000. Design and implementation of an interactive visual analysis system for e-sourcing. Tech. rep. RC22045, IBM.Google Scholar
- Lehmann, D., Müller, R., and Sandholm, T. 2006. The winner determination problem. In Combinatorial Auctions, Chapter 12, 297--317.Google Scholar
- Leskelä, R.-L., Teich, J. E., Wallenius, H., and Wallenius, J. 2007. Decision support for multi-unit combinatorial bundle auctions. Decision Support Syst. 43, 2, 420--434. Google ScholarDigital Library
- Lévy, J. 1967. The Economic Life of the Ancient World. University of Chicago Press, Chicago, IL.Google Scholar
- Leyton-Brown, K., Nudelman, E., and Shoham, Y. 2006. Empirical hardness models for combinatorial auctions. In Combinatorial Auctions, Chapter 19, 479--504.Google Scholar
- Leyton-Brown, K. and Shoham, Y. 2006. A test-suite for combinatorial auctions. In Combinatorial Auctions, Chapter 18, 451--478.Google Scholar
- Leyton-Brown, K., Shoham, Y., and Tennenholtz, M. 2002. Bidding clubs in first-price auctions. In Proceedings of the 18th National Conference on Artificial Intelligence. AAAI Press, San Matteo, CA, 373--378. Google ScholarDigital Library
- Lucking-Reiley, D. 2000. Auctions on the internet: What's being auctioned, and how? J. Industr. Econ. 48, 227--252.Google ScholarCross Ref
- Mackie-Mason, J. K. and Varian, H. R. 1994. Generalized Vickrey auctions. Tech. rep., Department of Economics, University of Michigan.Google Scholar
- Maskin, E. S. and Riley, J. G. 1985. Auction theory with private values. Amer. Econ. Rev. 75, 150--155.Google Scholar
- Maskin, E. S. and Sjöström, T. 2002. Implementation theory. In Handbook of Social Choice Theory and Welfare, K. J. Arrow, A. K. Sen, and K. Suzumura, Eds. North-Holland, Amsterdam.Google Scholar
- McAfee, R. P. and McMillan, J. 1987. Auctions and bidding. J. Econ. Lit. 25, 2, 699--738.Google Scholar
- McAfee, R. P. and McMillan, J. 1996. Analyzing the airwaves auction. J. Econ. Perspect. 10, 159--176.Google ScholarCross Ref
- McCabe, K. A., Rassenti, S. J., and Smith, V. L. 1993. Designing a uniform-price double auction: An experimental evaluation. In The Double Auction Market: Institutions, Thories and Evndence, Pervious Publishing, Cambridge, MA, 307--332.Google Scholar
- McMillan, J. 1994. Selling spectrum rights. J. Econ. Perspect. 8, 191--199.Google ScholarCross Ref
- Menezes, F. 1996. Multiple-unit English auctions. Europ. J. Polit. Econ. 12, 4, 671--684.Google ScholarCross Ref
- Milgrom, P. 1989. Auctions and bidding: A primer. J. Econ. Perspect. 3, 3, 3--22.Google ScholarCross Ref
- Milgrom, P. 2000. Putting auction theory to work: The simultaneous ascending auction. J. Polit. Econ. 108, 245--272.Google ScholarCross Ref
- Milgrom, P. and Weber, R. 1982. A theory of auctions and competitive bidding. Econometrica 50, 1089--1122.Google ScholarCross Ref
- Monderer, D. and Tennenholtz, M. 1999. Distributed games. Games Econ. Behav. 28, 1, 55--72.Google ScholarCross Ref
- Monderer, D. and Tennenholtz, M. 2000. k-price auctions. Games Econom. Behav. 31, 1--2, 220--244.Google ScholarCross Ref
- Morita, T., Yuitou, M., Hidaka, T., and Hirakawa, Y. 2005. Visualization methods using three-dimensional space for auctions. In Proceedings of the Symposium on Applications and the Internet Workshops. 396--399. Google ScholarDigital Library
- Mu'alem, A. and Nisan, N. 2002. Truthful approximation mechanisms for restricted combinatorial auctions. In Proceedings of the 18th National Conference on Artificial Intelligence. AAAI Press, San Matteo, CA, 379--384. Google ScholarDigital Library
- Müller, R. 2006. Tractable cases of the winner determination problem. In Combinational Auctions, Chapter 13, 319--336.Google Scholar
- Murnighan, J. K. 1992. Bargaining Games. William Murrow and Company.Google Scholar
- Myerson, R. B. 1981. Optimal auction design. Math. Oper. Res. 6, 1, 58--73.Google ScholarDigital Library
- Narumanchi, M. V. and Vidal, J. M. 2006. Algorithms for distributed winner determination in combinatorial auctions. In Agent-Mediated Electronic Commerce. Designing Trading Agents and Mechanisms. Lecture Notes in Computer Science, vol. 3937. Springer-Verlag, 43--56. Google ScholarDigital Library
- Nisan, N. 2000. Bidding and allocation in combinatorial auctions. In Proceedings of the 2nd ACM Conference on Electronic Commerce. ACM, 1--12. Google ScholarDigital Library
- Nisan, N. 2006. Bidding languages for combinatorial auctions. In Combinatonial Auctions, Chapter 9, 215--232.Google Scholar
- Nisan, N. 2007. Introduction to mechanism design (for computer scientists). In Algorithmic Game Theory, N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani, Eds. Cambridge University Press, Cambridge, UK.Google Scholar
- Nisan, N. and Ronen, A. 2007. Computationally feasible VCG mechanisms. J. Artif. Intell. Res. 29, 19--47. Google ScholarCross Ref
- Niu, J., Cai, K., Gerding, E., McBurney, P., and Parsons, S. 2008. Characterizing effective auction mechanisms: Insights from the 2007 TAC market design competition. In Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems, L. Padgham, D. Parkes, J. Müller, and S. Parsons, Eds. IFAAMAS, 1079--1086. Google ScholarDigital Library
- Object Management Group 2006. BPM 1.0: BPM business process modeling notation specification. Tech. rep., Object Management Group. (Final adopted specification.)Google Scholar
- Osborne, M. J. and Rubinstein, A. 1994. A Course in Game Theory. MIT Press, Cambridge, MA.Google Scholar
- Ostwald, J., Lesser, V., and Abdallah, S. 2005. Combinatorial auction for resource allocation in a distributed sensor network. In Proceedings of the 26th IEEE International Real-Time Systems Symposium (RTSS'05). IEEE Computer Society, 266--274. Google ScholarDigital Library
- Parkes, D. 1999. iBundle: An efficient ascending price bundle auction. In Proceedings of the 1st ACM Conference on Electronic Commerce. ACM, New York, 148--157. Google ScholarDigital Library
- Parkes, D. 2000. Optimal auction design for agents with hard valuation problems. In Agent Mediated Electronic Commerce II: Towards Next-Generation Agent-Based Electronic Commerce Systems, F. Y. A. Moukas, C. Sierra, Ed. Lecture Notes in Artificial Intelligence, vol. 1788. Springer Verlag, Berlin, 206--219.Google Scholar
- Parkes, D. 2001. Iterative combinatorial auctions: Achieving economic and computational efficiency. Ph.D. dissertation, Department of Computer and Information Science, University of Pennsylvania. Google ScholarDigital Library
- Parkes, D., Cavallo, R., Elprin, N., Juda, A., Lahaie, S., Lubin, B., Michael, L., Shneidman, J., and Sultan, H. 2005. ICE: An iterative combinatorial exchange. In Proceedings of the 6th ACM Conference on Electronic Commerce. ACM, New York, 249--258. Google ScholarDigital Library
- Parkes, D. and Kalagnanam, J. 2005. Models for iterative multiattribute procurement auctions. Manage. Sci. 51, 435--451. Google ScholarDigital Library
- Parkes, D., Kalagnanam, J. R., and Eso, M. 2001. Achieving budget-balance with Vickrey-based payment schemes in exchanges. In Proceedings of the 17th International Joint Conference on Artificial Intelligence, B. Nebel, Ed. Seattle, WA, 1161--1168. Google ScholarDigital Library
- Parkes, D. C. and Duong, Q. 2007. An ironing-based approach to adaptive online mechanism design in single-valued domains. In Proceedings of the 22nd AAAI Conference on Artificial Intelligence. AAAI Press, San Matteo, CA, 94--101. Google ScholarDigital Library
- Parsons, S. 2002. Exception analysis for double auctions. Research Note, Center for Coordination Science, Sloan School of Management, Massachusetts Institute of Technology.Google Scholar
- Parsons, S., Marcinkiewicz, M., Niu, J., and Phelps, S. 2008. Everything you wanted to know about double auctions, but were afraid to (bid or) ask. Tech. rep., Department of Computer and Information Science, Brooklyn College.Google Scholar
- Patel, J., Teacy, W. T. L., Jennings, N. R., Luck, M., Chalmers, S., Oren, N., Norman, T. J., Preece, A. D., Gray, P. M. D., Shercliff, G., Stockreisser, P. J., Shao, J., Gray, W. A., Fiddian, N. J., and Thompson, S. G. 2005. Agent-based virtual organisations for the grid. In Proceedings of the 4th International Joint Conference on Autonomous Agents and Multi-agent Systems, F. Dignum, V. Dignum, S. Koenig, S. Kraus, M. P. Singh, and M. Wooldridge, Eds. 1151--1152. Google ScholarDigital Library
- Pesendorfer, M. 2000. A study of collusion in first-price auctions. Rev. Econ. Stud. 67, 381--411.Google ScholarCross Ref
- Petcu, A., Faltings, B., and Parkes, D. C. 2006. MDPOP: faithful distributed implementation of efficient social choice problems. In Proceedings of the 5th International Conference on Autonomous Agents and Multiagent Systems, H. Nakashima, M. P. Wellman, G. Weiss, and P. Stone, Eds. ACM, New York, 1397--1404. Google ScholarDigital Library
- Phelps, S. 2008. Evolutionary mechanism design. Ph.D. thesis, Department of Computer Science, University of Liverpool.Google Scholar
- Phelps, S., Cai, K., McBurney, P., Niu, J., Parsons, S., and Sklar, E. 2008. Auctions, evolution, and multi-agent learning. In Adaptive Agents and Multi-Agent Systems III, K. Tuyls, A. Nowe, Z. Guessoum, and D. Kudenko, Eds. Lecture Notes in Artificial Intelligence, vol. 4865. Springer Verlag, Berlin. Google ScholarDigital Library
- Porter, R., Ronen, A., Shoham, Y., and Tennenholtz, M. 2002. Mechanism design with execution uncertainty. In Proceedings of the 18th Conference in Uncertainty in Artificial Intelligence, A. Darwiche and N. Friedman, Eds. Morgan-Kaufmann, San Francisco, CA. Google ScholarDigital Library
- Porter, R. H. and Zona, J. D. 1993. Detection of bid rigging in procurement auctions. J. Polit. Econ. 101, 3, 518--538.Google ScholarCross Ref
- PricewaterhouseCoopers. 2002. E-markets: Realism, not pessimism. http://pwcglobal.com/ebusinessinsights. (Aceessed 4/02).Google Scholar
- Pringsheim, F. 1949. The Greek sale by auction. In Scritti in Onore di Contardo Ferrini Pubblicati in Occasione della sua Beatificazione. Pubblicazioni dell' Universita Cattolica del Sacro Cuore, Nuova Serie, vol. XXVIII. Societa Editrice “Vita e Pensiero”, Milan, 284--343.Google Scholar
- Ramchurn, S. D., Mezzetti, C., Giovannucci, A., Rodriguez-Aguilar, J. A., Dash, R. K., and Jennings, N. R. 2009. Trust-based mechanisms for robust and efficient task allocation in the presence of execution uncertainty. J. Artif. Intell. Res. 35, 1, 119--159. Google ScholarCross Ref
- Ramchurn, S. D., Rogers, A., MacArthur, K., Farinelli, A., Vytelingum, P., Vetsikas, I., and Jennings, N. R. 2008. Agent-based coordination technologies in disaster management. In Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems, L. Padgham, D. Parkes, J. Müller, and S. Parsons, Eds. IFAAMAS, 1651--1652. Google ScholarDigital Library
- Riley, J. G. and Samuelson, W. F. 1981. Optimal auctions. Amer. Econ. Rev. 71, 381--392.Google Scholar
- Roth, A. E. and Ockenfels, A. 2000. Last minute bidding and the rules for ending second-price auctions: Theory and evidence from a natural experiment on the internet. Working paper, Department of Economics, Harvard University.Google Scholar
- Rust, J., Miller, J. H., and Palmer, R. 1994. Characterizing effective trading strategies. J. Econ. Dynam. Cont. 18, 61--96.Google ScholarCross Ref
- Sandholm, T. 2002. An algorithm for optimal winner determination in combinatorial auctions. Artif. Intell. 135, 1--54. Google ScholarDigital Library
- Sandholm, T. 2003. Automated mechanism design: A new application area for search algorithms. In Principles and Practice of Constraint Programming, F. Rossi, Ed. Lecture Notes in Computer Science, vol. 2833. Springer, Berlin, Germany, 19--36.Google Scholar
- Sandholm, T. 2006. Optimal winner determination algorithms. In Combinatorial Auctions, P. Cramton, Y. Shoham, and Steinberg, Eds. MIT Press, Cambridge, MA.Google Scholar
- Sandholm, T. and Boutilier, C. 2006. Bidding languages for combinatorial auctions. In Combinatonial Auctions, Chapter 10, 233--263.Google Scholar
- Sandholm, T. and Gilpin, A. 2006. Sequences of take-it-or-leave-it offers: near-optimal auctions without full valuation revelation. In Proceedings of the 5th International Conference on Autonomous Agents and Multiagent Systems, H. Nakashima, M. P. Wellman, G. Weiss, and P. Stone, Eds. ACM, New York, 1127--1134. Google ScholarDigital Library
- Sandholm, T. and Suri, S. 2006. Side constraints and non-price attributes in markets. Games Econ. Behav. 55, 321--330.Google ScholarCross Ref
- Sandholm, T., Suri, S., Gilpin, A., and Levine, D. 2002. Winner determination in combinatorial auction generalizations. In Proceedings of the 1st International Joint Conference on Autonomous Agents and Multiagent Systems. ACM, New York, 69--76. Google ScholarDigital Library
- Satterthwaite, M. A. 1975. Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions. J. Econ. Theory 10, 187--217.Google ScholarCross Ref
- Satterthwaite, M. A. and Williams, S. R. 1993. The Bayesian theory of the k-double auction. In The Double Auction Market: Institutions, Theories and Evidence. Perseus Publishing, Cambridge, MA, Chapter 4, 99--123.Google Scholar
- Shoham, Y. 2000. A survey of auction types. Lecture notes: Stanford University CS206—Technical Foundations of Electronic Commerce.Google Scholar
- Shoham, Y. 2001a. Auctions on the internet: what's actually happening. Lecture notes: Stanford University CS206—Technical Foundations of Electronic Commerce.Google Scholar
- Shoham, Y. 2001b. Combinatorial auctions. Lecture notes: Stanford University CS206—Technical Foundations of Electronic Commerce.Google Scholar
- Shoham, Y. 2001c. The zoology of auctions. Lecture notes: Stanford University CS206—Technical Foundations of Electronic Commerce.Google Scholar
- Shoham, Y. 2002. Combinatorial auctions. Lecture notes: Stanford University CS206—Technical Foundations of Electronic Commerce.Google Scholar
- Shoham, Y. and Leyton-Brown, K. 2008. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press, Cambridge, UK. Google ScholarCross Ref
- Sierra, C., de Mantaras, R. L., and Busquets, D. 2000. Multiagent bidding mechanisms for robot qualitative navigation. In Intelligent Agents VII. Lecture Notes in Artificial Intelligence, vol. 1986. 198--212. Google ScholarDigital Library
- Smith, V. L. 1962. An experimental study of competitive market behaviour. J. Polit. Econ. 70, 2, 111--137.Google ScholarCross Ref
- Smith, V. L. 1982. Microeconomic systems as an experimental science. Amer. Econ. Rev. 72, 5, 923--955.Google Scholar
- Song, J. and Regan, A. 2002a. Approximation algorithms for the bid construction problem in combinatorial auctions for the procurement of freight transportation contracts. Tech. rep., ITS-CUI Working paper, University of California, Irvine.Google Scholar
- Song, J. and Regan, A. C. 2002b. Combinatorial auctions for transportation service procurement: the carrier perspective. Transport. Res. Rec. 1833, 40--46.Google ScholarCross Ref
- Stark, R. and Rothkopf, M. H. 1979. Competitive bidding: A comprehensive bibliography. Oper. Res. 27, 364--391.Google ScholarDigital Library
- Strobel, M. and Weinhardt, C. 2003. The Montreal taxonomy of electronic negotiations. Group Dec. Negot. 12, 143--164.Google Scholar
- Suyama, T. and Yokoo, M. 2005. Strategy/false-name proof protocols for combinatorial multi-attribute procurement auction. Auton. Agents Multi-Agent Syst. 11, 1, 7--21. Google ScholarDigital Library
- Tesauro, G. and Das, R. 2001. High-performance bidding agents for the continuous double auction. In Proceedings of the 3rd ACM Conference on Electronic Commerce. ACM, New York, 206--209. Google ScholarDigital Library
- Thomas, J. A. C. 1957. The auction sale in Roman law. Judicial Rev., 42--66.Google Scholar
- Uckelman, J. and Endriss, U. 2008. Winner determination in combinatorial auctions with logic-based bidding languages. In Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems, L. Padgham, D. Parkes, J. Müller, and S. Parsons, Eds. IFAAMAS, 1617--1618. Google ScholarDigital Library
- Ungern-Sternberg, T. V. 1991. Swiss auctions. Econometrica 58, 341--357.Google Scholar
- Varian, H. R. 1995. Economic mechanism design for computerized agents. In Proceedings of the USENIX Workshop on Electronic Commerce. USENIX, New York. Google ScholarDigital Library
- Vickrey, W. 1961. Counterspeculation, auctions, and competitive sealed bids. J. Fin. 16, 1, 8--37.Google ScholarCross Ref
- Vinyals, M., Giovannucci, A., Cerquides, J., Meseguer, P., and Rodriguez-Aguilar, J. A. 2008. A test suite for the evaluation of mixed multi-unit combinatorial auctions. J. Algorithms 63, 1--3, 130--150. Google ScholarDigital Library
- Walton, K. 2006. Fake: Forgery, Lies & eBay. Simon Spotlight Entertainment, New York. Google ScholarDigital Library
- Wang, X. and Xia, M. 2005. Combinatorial bid generation problem for transportation service procurement. Transportation Research Record: J. Trans. Res. Board 1923, 189--198.Google ScholarCross Ref
- Wellman, M. 1993. A market-oriented programming environment and its application to distributed multicommodity flow problems. J. Artif. Intell. Res. 1, 1--23. Google ScholarCross Ref
- Wellman, M. P., Greenwald, A., Stone, P., and Wurman, P. R. 2002. The 2001 trading agent competition. In Proceedings of the 18th National Conference on Artificial Intelligence. AAAI, Edmonton, Alberta, Canada, 935--941. Google ScholarDigital Library
- Wellman, M. P., Wurman, P. R., O'Malley, K., Bangera, R., Lin, S., Reeves, D., and Walsh, W. E. 2001. Designing the market game for a trading agent competition. IEEE Internet Comput. 5, 2, 43--51. Google ScholarDigital Library
- Wolfstetter, E. 1996. Auctions: An introduction. J. Econ. Surv. 10, 4, 367--420.Google ScholarCross Ref
- Wurman, P. and Wellman, M. 2000. AkBA: a progressive, anonymous-price combinatorial auction. In Proceedings of the 2nd ACM Conference on Electronic Commerce. 21--29. Google ScholarDigital Library
- Wurman, P. R., Walsh, W. E., and Wellman, M. P. 1998. Flexible double auctions for electronic commerce: Theory and applications. Decision Supp. Syst. 24, 17--27. Google ScholarDigital Library
- Wurman, P. R., Wellman, M. P., and Walsh, W. E. 2001. A parameterization of the auction design space. Games Econ. Behav. 35, 1/2, 304--338.Google Scholar
- Xia, M., Stallaert, J., and Whinston, A. B. 2004. Solving the combinatorial double auction problem. Europ. J. Oper. Res. 164, 1, 234--251.Google Scholar
- Xu, L., Hutter, F., Hoos, H., and Leyton-Brown, K. 2008. SATzilla: Portfolio-based algorithm selection for SAT. J. Artif. Intell. Res. 32, 565--606. Google ScholarCross Ref
- Yokoo, M., Sakurai, Y., and Matsubara, S. 2001. Robust combinatorial auction protocol against false-name bids. Artif. Intell. 130, 2, 167--181. Google ScholarDigital Library
- Yokoo, M., Sakurai, Y., and Matsubara, S. 2004. The effect of false-name bids in combinatorial auctions: New fraud in internet auctions. Games Econ. Beh. 46, 1, 174--188.Google ScholarCross Ref
- Zurel, E. and Nisan, N. 2001. An efficient approximation algorithm for combinatorial auctions. In Proceedings of the 3rd ACM Conference on Electronic Commerce. ACM, New York, 125--136. Google ScholarDigital Library
Index Terms
- Auctions and bidding: A guide for computer scientists
Recommendations
The Impact of Discrete Bidding and Bidder Aggressiveness on Sellers' Strategies in Open English Auctions: Reserves and Covert Shilling
In practice, the rules in most open English auctions require participants to raise bids by a sizeable, discrete amount. Furthermore, some bidders are typically more aggressive in seeking to become the "current bidder" during competitive bidding. Most ...
Envy-free auctions for digital goods
EC '03: Proceedings of the 4th ACM conference on Electronic commerceWe study auctions for a commodity in unlimited supply, e.g., a digital good. In particular we consider three desirable properties for auctions: item Competitive: the auction achieves a constant fraction of the optimal revenue even on worst case inputs. ...
The Effect of Regret on Optimal Bidding in Auctions
<P>While most models of auctions and competitive bidding assume that each bidder's utility for an outcome depends only on his own profit, we allow the utility to also depend on any regret that a bidder suffers after the fact and characterize when and ...
Comments