Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Generalized Knapsack Solvers for Multi-unit Combinatorial Auctions: Analysis and Application to Computational Resource Allocation

  • Conference paper
Agent-Mediated Electronic Commerce VI. Theories for and Engineering of Distributed Mechanisms and Systems (AMEC 2004)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 3435))

Included in the following conference series:

Abstract

The problem of allocating discrete computational resources motivates interest in general multi-unit combinatorial exchanges. This paper considers the problem of computing optimal (surplus-maximizing) allocations, assuming unrestricted quasi-linear preferences. We present a solver whose pseudo-polynomial time and memory requirements are linear in three of four natural measures of problem size: number of agents, length of bids, and units of each resource. In applications where the number of resource types is inherently a small constant, e.g., computational resource allocation, such a solver offers advantages over more elaborate approaches developed for high-dimensional problems.

We also describe the deep connection between auction winner determination problems and generalized knapsack problems, which has received remarkably little attention in the literature. This connection leads directly to pseudo-polynomial solvers, informs solver benchmarking by exploiting extensive research on hard knapsack problems, and allows E-Commerce research to leverage a large and mature body of literature.

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

Access this chapter

Log in via an institution

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. de Vries, S., Vohra, R.V.: Combinatorial auctions: A survey. INFORMS Journal on Computing 15, 284–309 (2003)

    Article  MathSciNet  Google Scholar 

  2. Pekec, A., Rothkopf, M.H.: Combinatorial auction design. Management Science 49, 1485–1503 (2003)

    Article  Google Scholar 

  3. Rothkopf, M.H., Pekec, A., Harstad, R.M.: Computationally manageable combinatorial auctions. Management Science 44, 1131–1147 (1998)

    Article  MATH  Google Scholar 

  4. Leyton-Brown, K., Shoham, Y., Tennenholtz, M.: An algorithm for multi-unit combinatorial auctions. In: Proc. of the 17th National Conference on Artificial Intelligence (2000)

    Google Scholar 

  5. Gonen, R., Lehmann, D.: Optimal solutions for multi-unit combinatorial auctions: Branch and bound heuristics. In: ACM E-Commerce (2000)

    Google Scholar 

  6. Andersson, A., Tenhunen, M., Ygge, F.: Integer programming for combinatorial auction winner determination. In: ICMAS (2000)

    Google Scholar 

  7. Wurman, P.R., Wellman, M.P., Walsh, W.E.: A parametrization of the auction design space. Games and Economic Behavior 35, 304–338 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  8. Varian, H., MacKie-Mason, J.K.: Generalized Vickrey auctions. Technical report, Dept.of Economics, University of Michigan (1994)

    Google Scholar 

  9. Mas-Colell, A., Whinston, M.D., Green, J.R.: Microeconomic Theory. Oxford University Press, Oxford (1995)

    Google Scholar 

  10. Nisan, N., Ronen, A.: Algorithmic mechanism design. Games and Economic Behavior 35, 166–196 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  11. Lehmann, D., O’Callaghan, L., Shoham, Y.: Truth revelation in approximately efficient combinatorial auctions. Journal of the ACM 49, 577–602 (2002)

    Article  MathSciNet  Google Scholar 

  12. Nisan, N., Ronen, A.: Computationally feasible VCG mechanisms. In: Proceedings of the ACM Conference on Electronic Commerce, pp. 242–252 (2000)

    Google Scholar 

  13. Lavi, R., Mu’alem, A., Nisan, N.: Towards a characterization of truthful combinatorial auctions (extended abstract). In: IEEE FOCS (2003)

    Google Scholar 

  14. Kelly, T.: Generalized knapsack solvers for multi-unit combinatorial auctions. Technical Report HPL-2004-21, HP Labs (2004)

    Google Scholar 

  15. Hewlett-Packard Corporation: HP Utility Data Center (UDC) overview (2004), http://h30046.www3.hp.com/solutions/overview.html

  16. Hewlett-Packard Corporation: An economy of IT: Allocating resources in the computing utility (2003), http://www.hpl.hp.com/news/2003/oct_dec/computons.html

  17. Nisan, N.: Bidding and allocation in combinatorial auctions. In: Proceedings of the Second ACM Conference on Electronic Commerce, pp. 1–12 (2000)

    Google Scholar 

  18. Ledyard, J.O.: Incentive compatible space station pricing. American Economic Review 76, 274–279 (1987)

    Google Scholar 

  19. Kelly, T.: Utility-directed allocation. In: First Workshop on Algorithms and Architectures for Self-Managing Systems. Also available as HP Labs tech report HPL-2003-115 (2003), http://tesla.hpl.hp.com/self-manage03/

  20. Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Heidelberg (2004)

    MATH  Google Scholar 

  21. Tennenholtz, M.: Some tractable combinatorial auctions. In: Proc. of the 17th National Conference on Artificial Intelligence (2000); A later and longer version is Ref.[45]

    Google Scholar 

  22. Kothari, A., Parkes, D.C., Suri, S.: Approximately-strategyproof and tractable multi-unit auctions. In: ACM E-Commerce (2003)

    Google Scholar 

  23. Wurman, P.R., Walsh, W.E., Wellman, M.P.: Flexible double auctions for electronic commerce: Theory and implementation. Decision Support Systems 24, 17–27 (1998)

    Article  Google Scholar 

  24. Lehmann, B., Lehmann, D., Nisan, N.: Combinatorial auctions with decreasing marginal utilities. In: ACM E-Commerce (2001)

    Google Scholar 

  25. Walsh, W.: Personal communication (2003)

    Google Scholar 

  26. Sandholm, T., Suri, S., Gilpin, A., Levine, D.: Winner determination in combinatorial auction generalizations. In: AAMAS (2002)

    Google Scholar 

  27. Pisinger, D.: A minimal algorithm for the multiple-choice knapsack problem. European Journal of Operations Research 83, 394–410 (1995)

    Article  MATH  Google Scholar 

  28. Holte, R.C.: Combinatorial Auctions, Knapsack Problems, and Hill-Climbing Search. In: Stroulia, E., Matwin, S. (eds.) Canadian AI 2001. LNCS, vol. 2056, p. 57. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  29. Leyton-Brown, K.: Resource Allocation in Competitive Multiagent Systems. PhD thesis, Stanford University (2003)

    Google Scholar 

  30. Martello, S., Toth, P.: Knapsack Problems: Algorithms and Computer Implementation. John Wiley & Sons Ltd., Chichester (1990)

    Google Scholar 

  31. Sedgewick, R.: Algorithms in C. Addison-Wesley, Reading (1998); See page 215 of the 8th printing (August 2001) for a remarkably clear and compact integer knapsack solver in C

    MATH  Google Scholar 

  32. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)

    MATH  Google Scholar 

  33. Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity, 2nd edn. Dover (1998) ISBN 0-486-40258-4

    Google Scholar 

  34. Leyton-Brown, K., Pearson, M., Shoham, Y.: Towards a universal test suite for combinatorial auction algorithms. In: ACM E-Commerce (2000)

    Google Scholar 

  35. Chvátal, V.: Hard knapsack problems. Operations Research 28, 1402–1411 (1980)

    Article  MATH  MathSciNet  Google Scholar 

  36. Pisinger, D.: Algorithms for Knapsack Problems. PhD thesis, University of Copenhagen (1995), http://www.diku.dk/users/pisinger/95-1.pdf

  37. Martello, S., Pisinger, D., Toth, P.: New trends in exact algorithms for the 0-1 knapsack problem. European Journal of Operational Research 123, 325–332 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  38. Pisinger, D.: A fast algorithm for strongly correlated knapsack problems. Discrete Applied Mathematics 89, 197–212 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  39. Klemperer, P.: Auction theory: A guide to the literature. Journal of Economic Surveys 13, 227–260 (1999)

    Article  Google Scholar 

  40. Krishna, V.: Auction Theory. Academic Press, London (2002)

    Google Scholar 

  41. Sandholm, T., Suri, S.: Market clearability. In: IJCAI (2001)

    Google Scholar 

  42. Sandholm, T.: Algorithm for optimal winner determination in combinatorial auctions. Artificial Intelligence 135, 1–54 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  43. Bassamboo, A., Gupta, M., Juneja, S.: Efficient winner-determination techniques for Internet multi-unit auctions. In: Proceedings of the First IFIP Conference on E-Commerce, E-Business, and E-Government, vol. 202 (2001)

    Google Scholar 

  44. Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows. Prentice-Hall, Englewood Cliffs (1993)

    Google Scholar 

  45. Tennenholtz, M.: Tractable combinatorial auctions and b-matching. Artificial Intelligence 140, 231–243 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  46. Ghebreamiak, K.A., Andersson, A.: Caching in multi-unit combinatorial auctions. In: AAMAS (2002)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Hewlett-Packard Laboratories, Palo Alto, CA, 94304, USA

    Terence Kelly

Authors
  1. Terence Kelly
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Massachusetts Institute of Technology, Computer Science and Artificial Intelligence Laboratory, Massachusetts Avenue, 02139, Cambridge, USA

    Peyman Faratin

  2. IIIA, Artificial Intelligence Research Institute CSIC, Spanish Research Council, Campus, UAB, 08193, Bellaterra, Spain

    Juan A. Rodríguez-Aguilar

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Kelly, T. (2006). Generalized Knapsack Solvers for Multi-unit Combinatorial Auctions: Analysis and Application to Computational Resource Allocation. In: Faratin, P., Rodríguez-Aguilar, J.A. (eds) Agent-Mediated Electronic Commerce VI. Theories for and Engineering of Distributed Mechanisms and Systems. AMEC 2004. Lecture Notes in Computer Science(), vol 3435. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11575726_6

Download citation

  • DOI: https://doi.org/10.1007/11575726_6

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-29737-6

  • Online ISBN: 978-3-540-33166-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation