Skip to main content
SpringerLink
Log in

Auctions, Bidding and Exchange Design

  • Chapter
Handbook of Quantitative Supply Chain Analysis

Part of the book series: International Series in Operations Research & Management Science ((ISOR,volume 74))

Abstract

Auctions have found widespread use in the last few years as a technique for supporting and automating negotiations on the Internet. For example, eBay now serves as a new selling channel for individuals, and small and big enterprises. Another use for auctions is for industrial procurement. In both these settings traditional auction mechanisms such as the English, Dutch, First (or Second) price Sealed-Bid auctions are now commonplace. These auctions types are useful for settings where there is a single unit of an item being bought/sold. However, since procurement problems are business-to-business they tend to be more complex and have led to the development and application of advanced auction types that allow for negotiations over multiple units of multiple items, and the configuration of the attributes of items. At the heart of auctions is the problem of decentralized resource allocation.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 169.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 219.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 219.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. K Ahuja, T L Magnanti, and J B Orlin. Network flows. Prentice-Halls, Englewood Cliffs, 1993.

    Google Scholar 

  2. Arne Andersson, Mattias Tenhunen, and Fredrik Ygge. Integer programming for auctions with bids for combinations. In Proc. 4th International Conference on Multi-Agent Systems (ICMAS-00), 2000.

    Google Scholar 

  3. A Archer and E Tardos. Frugal path mechanisms. In Proc. 13th Symp. on Discrete Algorithms, pages 991–999, 2002.

    Google Scholar 

  4. Aaron Archer, Christos Papadimitriou, Kunal Talwar, and Eva Tardos. An approximate truthful mechanism for combinatorial auctions with single parameter agents. In Proc. 14th ACM Symposium on Discrete Algorithms, 2003.

    Google Scholar 

  5. Lawrence M Ausubel. An efficient ascending-bid auction for multiple objects. American Economic Review,2002. Forthcoming.

    Google Scholar 

  6. Lawrence M Ausubel and Peter Cramton. The optimality of being efficient. Technical report, University of Maryland, 1999.

    Google Scholar 

  7. Lawrence M Ausubel and Paul R Milgrom. Ascending auctions with package bidding. Frontiers of Theoretical Economics, 1: 1–42, 2002.

    Article  Google Scholar 

  8. Moshe Babaioff and Noam Nisan. Concurrent auctions across the supply chain. In Proc. 3rd ACM Conference on Electronic Commerce, pages 1–10. ACM Press, 2001.

    Google Scholar 

  9. J S Banks, J O Ledyard, and D Porter. Allocating uncertain and unresponsive resources: An experimental approach. The Rand Journal of Economics, 20: 1–25, 1989.

    Article  Google Scholar 

  10. Y Bartal, R Gonen, and N Nisan. Incentive compatible multi unit combinatorial auctions. Technical report, The Hebrew University of Jerusalem, 2003.

    Google Scholar 

  11. J J Bartholdi. The computatonal difficulty of manipulating an election. Social Choice and Welfare, 6: 227–241, 1989.

    Article  Google Scholar 

  12. Damian R Beil and Lawrence M Wein. An inverse-optimization-based auction mechanism to support a multi-attribute RFQ process. Technical report, Operations Research Center, MIT, 2001.

    Google Scholar 

  13. Martin Bichler and Jayant Kalagnanam. Winner determination problems in multi-attribute auctions. Technical report, IBM Research report, 2002.

    Google Scholar 

  14. Martin Bichler, Jayant Kalagnanam, and Ho Soo Lee. RECO: Representation and Evaluation of Configurable Offers. Technical Report RC 22288, Jan, IBM Research report, 2002. in Proceedings of ICS 2003.

    Google Scholar 

  15. Sushil Bikhchandani, Sven de Vries, James Schummer, and Rakesh V Vohra. Linear programming and Vickrey auctions. In Brenda Dietrich and Rakesh Vohra, editors, Mathematics of the Internet: E-Auction and Markets, pages 75–116. IMA Volumes in Mathematics and its Applications, Springer-Verlag, 2001.

    Google Scholar 

  16. Sushil Bikhchandani and Joseph M Ostroy. Ascending price Vickrey auctions. Games and Economic Behavior,2002. Forthcoming.

    Google Scholar 

  17. Sushil Bikhchandani and Joseph M Ostroy. The package assignment model. Journal of Economic Theory,2002. Forthcoming.

    Google Scholar 

  18. Liad Blumrosen and Noam Nisan. Auctions with severely bounded communication. In Proc. 43rd Annual Symposium on Foundations of Computer Science, 2002.

    Google Scholar 

  19. Craig Boutilier. Solving concisely expressed combinatorial auction problems. In Proc. 18th National Conference on Artificial Intelligence (AAAI02), July 2002.

    Google Scholar 

  20. Craig Boutilier and Holger Hoos. Bidding languages for combinatorial auctions. In Proc. 17th International Joint Conference on Artificial Intelligence (IJCAI-01), 2001.

    Google Scholar 

  21. F Branco. The design of multidimensional auctions. RAND Journal of Economics, 28: 63–81, 1997.

    Article  Google Scholar 

  22. Paul J Brewer. Decentralized computation procurement and computational robustness in a smart market. Economic Theory, 13: 41–92, 1999.

    Article  Google Scholar 

  23. Estelle Cantillon and Martin Pesendorfer. Combination bidding in multiunit auctions. Technical report, HBS and LSE, 2003.

    Google Scholar 

  24. K Chatterjee and W Samuelson. Bargaining under incomplete information. Operations Research, 31: 835–851, 1983.

    Article  Google Scholar 

  25. Y K Che. Design competition through multidimensional auctions. RAND Journal of Economics, 24: 668–680, 1993.

    Article  Google Scholar 

  26. E H Clarke. Multipart pricing of public goods. Public Choice, 11:17–33, 1971.

    Google Scholar 

  27. D Cliff. Evolution of market mechanism through a continuous space of auction types. Technical Report Technical Report HPL-2001–326, Hewlett Packard Labs, 2001.

    Google Scholar 

  28. Olivier Compte and Philippe Jehiel. On the virtues of the ascending price auction: New insights in the private value setting. Technical report, CERAS and UCL, 2000.

    Google Scholar 

  29. Wolfram Conen and Tuomas Sandholm. Preference elicitation in combinatorial auctions. In Proc. 3rd ACM Conf. on Electronic Commerce (EC-01), pages 256–259. ACM Press, New York, 2001.

    Chapter  Google Scholar 

  30. V Conitzer and T Sandholm. Complexity of manipulating elections with few candidates. In Proc. 18th National Conference on Artificial Intelligence (AAAI-02),July 2002..

    Google Scholar 

  31. V Conitzer and T Sandholm. Complexity of mechanism design. In Proc. 18th Conf. on Uncertainty in Artificial Intelligence (UAI’02), 2002.

    Google Scholar 

  32. Andrew Davenport, Abigail Hohner, and Jayant Kalagnanam. Combinatorial and quantity discount procurement auctions with mutual benefits at Mars, Inc. Interfaces,2002. Forthcoming.

    Google Scholar 

  33. Andrew Davenport and Jayant Kalagnanam. Price negotiations for procurement of direct inputs. In Brenda Dietrich and Rakesh Vohra, editors, Mathematics of the Internet: E-Auction and Markets. IMA Volumes in Mathematics and its Applications, Springer-Verlag, 2001.

    Google Scholar 

  34. Milind Dawande, R. Chandrasekharan, and Jayant Kalagnanam. On a question in linear programming and its application in decentralized allocation. Technical report, IBM research report, Jul 2002.

    Google Scholar 

  35. Sven de Vries and Rakesh V Vohra. Combinatorial auctions: A survey. Informs Journal on Computing,2002. Forthcoming.

    Google Scholar 

  36. Gabrielle Demange, David Gale, and Marilda Sotomayor. Multi-item auctions. Journal of Political Economy, 94 (4): 863–872, 1986.

    Article  Google Scholar 

  37. C DeMartini, A M Kwasnica, J O Ledyard, and D Porter. A new and improved design for multi-object iterative auctions. Technical Report SSWP 1054, California Institute of Technology, 1998. Revised March 1999.

    Google Scholar 

  38. Wedad Elmaghraby and Pinar Keskinocak. Combinatorial auctions in procurement. Technical report, National University of Singapore, 2002.

    Google Scholar 

  39. Marta Eso, Soumyadip Ghosh, Jayant R Kalagnanam, and Laszlo Ladanyi. Bid evaluation in procurement auctions with piece-wise linear supply curves. Technical Report RC 22219, IBM TJ Watson Research Center, 2001.

    Google Scholar 

  40. Joan Feigenbaum, Arvind Krishnamurthy, Rahul Sami, and Scott Shenker. Approximation and collusion in multicast cost sharing. In Proc. of the 3rd Conference on Electronic Commerce, pages 253–255, 2001.

    Google Scholar 

  41. Joan Feigenbaum and Scott Shenker. Distributed Algorithmic Mechanism Design: Recent Results and Future Directions. In Proceedings of the 6th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pages 1–13, 2002.

    Google Scholar 

  42. Yuzo Fujishima, Kevin Leyton-Brown, and Yoav Shoham. Taming the computational complexity of combinatorial auctions: Optimal and approximate approaches. In Proc. 16th International Joint Conference on Artificial Intelligence (IJCAI-99), pages 548–553, 1999.

    Google Scholar 

  43. Jeremie Gallien and Lawrence Wein. Design and analysis of a smart market for industrial procurement. Technical report, Operations Research Center, MIT, 2000.

    Google Scholar 

  44. Alan Gibbard. Manipulation of voting schemes: A general result. Econometrica, 41: 587–602, 1973.

    Article  Google Scholar 

  45. I Gilboa and E Zemel. Nash and correlated equilibria: Some complexity considerations. Games and Economic Behavior, pages 213–221, 1989.

    Google Scholar 

  46. Robert L Graves, Linus Schrage, and Jayaram Sankaran. An auction method for course registration. Interfaces, 23 (5): 81–92, 1993.

    Article  Google Scholar 

  47. Jerry Green and Jean-JacquesLaffont. Characterization of satisfactory mechanisms for the revelation of preferences for public goods. Econometrica, 45: 427–438, 1977.

    Article  Google Scholar 

  48. Theodore Groves. Incentives in teams. Econometrica, 41: 617–631, 1973.

    Article  Google Scholar 

  49. Faruk Gul and Ennio Stacchetti. The English auction with differentiated commodities. Journal of Economic Theory, pages 66–95, 2000.

    Google Scholar 

  50. R Holzman, N Kfir-Dahav, D Monderer, and M Tennenholtz. Bundling equilibrium in combinatorial auctions. Games and Economic Behavior, 2001.

    Google Scholar 

  51. Holger H Hoos and Craig Boutilier. Solving combinatorial auctions with stochastic local search. In Proc. 17th National Conference on Artificial Intelligence (AAAI-00), July 2000.

    Google Scholar 

  52. B Hudson and T Sandholm. Effectiveness of preference elicitation in combinatorial auctions. In Proc. Agent-Mediated Electronic Commerce (AMEC’IV) workshop at AAMAS’02, 2002.

    Google Scholar 

  53. Matthew O. Jackson. Mechanism theory. In The Encyclopedia of Life Support Systems. EOLSS Publishers, 2000.

    Google Scholar 

  54. Jayant R Kalagnanam, Andrew J Davenport, and H S Lee. Computational aspects of clearing continous call double auctions with assignment constraints and indivisible demand. Electronic Commerce Journal,1(3):221238, 2001.

    Google Scholar 

  55. Alexander S Kelso and Vincent P Crawford. Job matching, coalition formation, and gross substitutes. Econometrica, 50: 1483–1504, 1982.

    Article  Google Scholar 

  56. Anshul Kothari, David C. Parkes, and Subhash Suri. Approximatelystrategyproof and tractable multi-unit auctions. In Fourth ACM Conf. on Electronic Commerce (EC’03), pages 166–175, 2003.

    Google Scholar 

  57. Vijay Krishna and Motty Perry. Efficient mechanism design. Technical report, Pennsylvania State University, 1998. Available at: http://econ.la.psu.edurvkrishna/vcg 18.ps.

    Google Scholar 

  58. David Krych. Calculation and analysis of Nash equilibria of Vickreybased payment rules for combinatorial exchanges. Technical re- port, Harvard University, 2003. Undergraduate Thesis. Available from http://www.eecs.harvard.edu/econcs.

    Google Scholar 

  59. John O Ledyard, Mark Olson, David Porter, Joseph A Swanson, and David P Tonna. The first use of a combined value auction for transportation services. Interfaces,2000. Forthcoming.

    Google Scholar 

  60. Daniel Lehmann, Liadan Ita O’Callaghan, and Yoav Shoham. Truth revelation in approximately efficient combinatorial auctions. Journal of the ACM, 49 (5): 577–602, September 2002.

    Article  Google Scholar 

  61. Silvano Martello and Paulo Toth. Knapsack Problems. WileyIntersciences Series in Discrete Mathematics and Optimization, 1980.

    Google Scholar 

  62. R Preston McAfee. A dominant strategy double auction. J. of Economic Theory, 56: 434–450, 1992.

    Article  Google Scholar 

  63. John McMillan. Selling spectrum rights. Journal of Economic Perspectives, 8: 145–62, 1994.

    Article  Google Scholar 

  64. Paul Milgrom. Putting Auction Theory to Work. MIT Press, 2002.

    Google Scholar 

  65. Robert B Myerson. Optimal auction design. Mathematics of Operation Research, 6: 58–73, 1981.

    Article  Google Scholar 

  66. Robert B Myerson and Mark A Satterthwaite. Efficient mechanisms for bilateral trading. Journal of Economic Theory, 28: 265–281, 1983.

    Article  Google Scholar 

  67. Noam Nisan. Bidding and allocation in combinatorial auctions. In Proc. 2nd ACM Conf on Electronic Commerce (EC-00), pages 1–12, 2000.

    Chapter  Google Scholar 

  68. Noam Nisan and Amir Ronen. Computationally feasible VCG mechanisms. In Proc. 2nd ACM Conf on Electronic Commerce (EC-00), pages 242–252, 2000.

    Chapter  Google Scholar 

  69. Noam Nisan and Amir Ronen. Algorithmic mechanism design. Games and Economic Behavior, 35: 166–196, 2001.

    Article  Google Scholar 

  70. Noam Nisan and I Segal. The communication complexity of efficient allocation problems. Technical report, Hebrew University and Stanford University, 2002.

    Google Scholar 

  71. C H Papadimitriou. Algorithms, games and the Internet. In Proc. 33rd Annual ACM Symp. on the Theory of Computing, pages 749–753, 2001.

    Google Scholar 

  72. David C Parkes. iBundle: An efficient ascending price bundle auction. In Proc. 1st ACM Conf. on Electronic Commerce (EC-99), pages 148–157, 1999.

    Google Scholar 

  73. David C Parkes. Optimal auction design for agents with hard valuation problems. In Proc. IJCAI-99 Workshop on Agent Mediated Electronic Commerce,pages 206–219, July 1999. Stockholm.

    Google Scholar 

  74. David C Parkes. Iterative Combinatorial Auctions: Achieving Economic and Computational Efficiency. PhD thesis, Department of Computer and Information Science, University of Pennsylvania, May 2001. http://www.cis.upenn.edurdparkes/diss.html.

    Google Scholar 

  75. David C. Parkes. Price-based information certificates for minimal-revelation combinatorial auctions. In Agent Mediated Electronic Commerce IV: Designing Mechanisms and Systems, volume 2531 of Lecture Notes in Artificial Intelligence, pages 103–122. 2002.

    Google Scholar 

  76. David C Parkes. Auction design with costly preference elicitation. Submitted for publication, 2003.

    Google Scholar 

  77. David C Parkes and Jayant Kalagnanam. Iterative Multiattribute Vickrey Auctions. Submitted for publication, 2003.

    Google Scholar 

  78. David C Parkes, Jayant R Kalagnanam, and Marta Eso. Achieving budget-balance with Vickrey-based payment schemes in exchanges. In Proc. 17th International Joint Conference on Artificial Intelligence (IJCAI-01), 2001.

    Google Scholar 

  79. David C Parkes and Lyle H Ungar. Iterative combinatorial auctions: Theory and practice. In Proc. 17th National Conference on Artificial Intelligence (AAAI-00), pages 74–81, July 2000.

    Google Scholar 

  80. David C Parkes and Lyle H Ungar. Preventing strategic manipulation in iterative auctions: Proxy agents and price-adjustment. In Proc. 17th National Conference on Artificial Intelligence (AAAI-00), pages 82–89, July 2000.

    Google Scholar 

  81. David C Parkes and Lyle H Ungar. An ascending-price generalized Vickrey auction. Technical report, Harvard University, 2002.

    Google Scholar 

  82. S Phelps, P McBurney, S Parsons, and E Sklar. Co-evolutionary auction mechanism design: A preliminary report. In Proc. Agent-Mediated Electronic Commerce (AMEC’IV) workshop at AAMAS’02, 2002.

    Google Scholar 

  83. R Preston McAfee and John McMillan. Auctions and bidding. Journal of Economic Literature, 25: 699–738, June 1987.

    Google Scholar 

  84. S J Rassenti, V L Smith, and R L Bulfin. A combinatorial mechanism for airport time slot allocation. Bell Journal of Economics, 13: 402–417, 1982.

    Article  Google Scholar 

  85. Daniel M. Reeves and Michael P. Wellman. Computing equilibrium strategies in infinite games of incomplete information. In Proc. of Game-theoretic and Decision-theoretic Workshop at AAMAS’03, 2003.

    Google Scholar 

  86. Daniel M Reeves, Michael P Wellman, and Benjamin N Grosof. Automated negotiation from declarative descriptions. In Proc. 5th International Conference on Autonomous Agents (AGENTS-01). 2001.

    Google Scholar 

  87. Amir Ronen. Mechanism design with incomplete languages. In Proc. 3rd ACM Conf on Electronic Commerce (EC’01), 2001.

    Google Scholar 

  88. A E Roth. The economist as engineer. Econometrica, 70: 1341–1378, 2002.

    Article  Google Scholar 

  89. Michael H Rothkopf, Aleksandar Pekec, and Ronald M Harstad. Computationally manageable combinatorial auctions. Management Science, 44 (8): 1131–1147, 1998.

    Article  Google Scholar 

  90. Tuomas W Sandholm. Issues in computational Vickrey auctions. International Journal of Electronic Commerce, 4: 107–129, 2000.

    Google Scholar 

  91. Tuomas W Sandholm. eMediator: A next generation electronic commerce server. Computational Intelligence, 18: 656–676, 2002.

    Article  Google Scholar 

  92. Tuomas W Sandholm and Subhash Suri. Market clearability. In Proc. 17th Int. Joint Conf on Artificial Intelligence, 2001.

    Google Scholar 

  93. Tuomas W Sandholm, Subhash Suri, Andrew Gilpin, and David Levine. CABOB: A fast optimal algorithm for combinatorial auctions. In Proc. 17th Int. Joint Conf. on Artificial Intelligence, 2001.

    Google Scholar 

  94. Tuomas W Sandholm, Subhash Suri, Andrew Gilpin, and David Levine. Winner determination in combinatorial auction generalizations. In Proc. International Conference on Autonomous Agents, Workshop on Agent-based Approaches to B2Bpages 35–41, 2001.

    Google Scholar 

  95. Mark A Satterthwaite and Steven R Williams. Bilateral trade with the sealed bid k-double auction: Existence and efficiency. Journal of Economic Theory, 48: 107–133, 1989.

    Article  Google Scholar 

  96. James Schummer. Almost dominant strategy implementation. Technical report, MEDS Department, Kellogg Graduate School of Management, 2002.

    Google Scholar 

  97. Jeff Shneidman and David C. parkes. Rationality and self-interest in peer to peer networks. In 2nd Int. Workshop on Peer-to-Peer Systems (IPTPS’03), 2003.

    Google Scholar 

  98. Jeffrey Shneidman and David C. Parkes. Using redundancy to improve robustness of distributed mechanism implementations. In Fourth ACM Conf. on Electronic Commerce (EC’03), 2003. (Poster paper). Extended version at http://www.eecs.harvard.edulparkes/pubs/redundancy.pdf.

    Google Scholar 

  99. Valentina Tamma, Michael Wooldridge, and Ian Dickinson. An ontology based approach to automated negotiation. In Proc. Agent-Mediated Electronic Commerce (AMEC’IV) workshop at AAMAS’02, 2002.

    Google Scholar 

  100. William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance, 16: 8–37, 1961.

    Article  Google Scholar 

  101. N Vulkan and N R Jennings. Efficient mechanisms for the supply of services in multi-agent environments. Decision Support Systems, 28: 519, 2000.

    Article  Google Scholar 

  102. Michael P Wellman, Amy Greenwald, Peter Stone, and Peter R Wurman. The 2001 Trading Agent Competition. In Proc. 14th Conf on Innovative Applications of Art. Intell., pages 935–941, 2002.

    Google Scholar 

  103. Steven R Williams. A characterization of efficient, Bayesian incentive-compatible mechanisms. Economic Theory, 14: 155–180, 1999.

    Article  Google Scholar 

  104. R Wilson. Incentive efficiency of double auctions. Econometrica, 53: 1101–1115, 1985.

    Article  Google Scholar 

  105. Peter R Wurman and Michael P Wellman. AkBA: A progressive, anonymous-price combinatorial auction. In Second ACM Conference on Electronic Commerce, pages 21–29, 2000.

    Chapter  Google Scholar 

  106. Peter R. Wurman, Michael P. Wellman, and William E. Walsh. Specifying rules for electronic auctions. AI Magazine, 2002.

    Google Scholar 

  107. Weili Zhu and Peter R. Wurman. Structural leverage and fictitious play in sequential auctions. In Proc. 18th National Conference on Artificial Intelligence (AAAI-02), pages 385–390, July 2002.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. IBM Research Division, T.J. Watson Research Center, P.O.Box 218, Yorktown Heights, NY, 1058, USA

    Jayant Kalagnanam

  2. Division of Engineering and Applied Sciences, Harvard University, Cambridge, MA, 02138, USA

    David C. Parkes

Authors
  1. Jayant Kalagnanam
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. David C. Parkes
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Massachusetts Institute of Technology, USA

    David Simchi-Levi

  2. Lehigh University, USA

    S. David Wu

  3. University of Florida, USA

    Zuo-Jun Shen

Rights and permissions

Reprints and permissions

Copyright information

© 2004 Springer Science+Business Media New York

About this chapter

Cite this chapter

Kalagnanam, J., Parkes, D.C. (2004). Auctions, Bidding and Exchange Design. In: Simchi-Levi, D., Wu, S.D., Shen, ZJ. (eds) Handbook of Quantitative Supply Chain Analysis. International Series in Operations Research & Management Science, vol 74. Springer, Boston, MA. https://doi.org/10.1007/978-1-4020-7953-5_5

Download citation

  • DOI: https://doi.org/10.1007/978-1-4020-7953-5_5

  • Publisher Name: Springer, Boston, MA

  • Print ISBN: 978-1-4757-1074-8

  • Online ISBN: 978-1-4020-7953-5

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation