[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

A Faster Optimal Allocation Algorithm in Combinatorial Auctions

  • Conference paper
MICAI 2004: Advances in Artificial Intelligence (MICAI 2004)

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

Included in the following conference series:

  • 1600 Accesses

Abstract

In combinatorial auctions, a bidder may bid for arbitrary combinations of items, so combinatorial auction can be applied to resource and task allocations in multiagent systems. But determining the winners of combinatorial auctions who maximize the profit of the auctioneer is known to be NP-complete. A branch-and-bound method can be one of efficient methods for the winner determination.

In this paper, we propose a faster winner determination algorithm in combinatorial auctions. The proposed algorithm uses both a branch-and-bound method and Linear Programming. We present a new heuristic bid selection method for the algorithm. In addition, the upper-bounds are reused to reduce the running time of the algorithm in some specific cases.

We evaluate the performance of the proposed algorithm by comparing with those of CPLEX and a known method. The experiments have been conducted with six datasets each of which has a different distribution. The proposed algorithm has shown superior efficiency in three datasets and similar efficiency in the rest of the datasets.

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. Andersson, A., Tenhunen, M., Ygge, F.: Integer Programming for Combinatorial Auction Winner Determination. In: Proceedings of the Fourth International Conference on Multi Agent Systems (ICMAS), pp. 39–46 (2000)

    Google Scholar 

  2. Brewer, P.J., Plott, C.R.: A Binary Conflict Ascending Price (BICAP) Mechanism for the Decentralized Allocation of the Right to Use Railroad Tracks. Int.Journal of Industrial Organization 14, 857–886 (1996)

    Article  Google Scholar 

  3. Clearwater, S.H. (ed.): Market-Based Control: a Paradigm for Distributed Resource Allocation. World Scientific, Singapore (1996)

    Google Scholar 

  4. de Vries, S., Vohra, R.: Combinatorial Auctions: A Survey. Draft (2000)

    Google Scholar 

  5. Fujishima, Y., Leyton-Brown, K., Shoham, Y.: Taming the Computational Complexity of Combinatorial Auctions: Optimal and Approximate Approaches. In: Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence(IJCAI), pp. 548–553 (1999)

    Google Scholar 

  6. Gonen, R., Lehmann, D.: Linear Programming Helps Solving Large Multi-unit Combinatorial Auctions. In: Electronic Market Design Workshop, July 11-13 (2001)

    Google Scholar 

  7. Lazar, A., Semret, N.: The Progressive Second Price Auction Mechanism for Network Resource Sharing. In: 8th International Symposium on Dynamic Games, Maastricht, The Netherlands, July 5-8 (1998)

    Google Scholar 

  8. Milgrom, P.: Putting Auction Theory to Work: The Simultaneous Ascending Auction. Journal of Political Economy 108, 245–272 (2000)

    Article  Google Scholar 

  9. Nisan, N.: Bidding and Allocation in Combinatorial Auctions. In: ACM Conference on Electronic Commerce, pp. 1–12 (2000)

    Google Scholar 

  10. Rassenti, S.J., Smith, V.L., Bulfin, R.L.: A combinatorial Auction Mechanism for Airport Time Slot Allocation. Bell Journal of Economics 13, 402–417 (1982)

    Article  Google Scholar 

  11. Rothkopf, M.H., Pekec, A., Harstad, R.M.: Computationally Manageable Combinatorial Auctions. Management Science 44(8), 1131–1147 (1995)

    Article  Google Scholar 

  12. Sandholm, T., Suri, S., Gilpin, A., Levine, D.: CABOB: A Fast Optimal Algorithm for Combinatorial Auctions. In: Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI), pp. 1102–1108 (2001)

    Google Scholar 

  13. Tennenholtz, M.: Some Tractable Combinatorial Auctions. AAAI, Menlo Park (2000)

    Google Scholar 

  14. Zurel, E., Nisan, N.: An Efficient Approximate Allocation Algorithm for Combinatorial Auctions. In: ACM Conference on Electronic Commerce, pp. 125–136 (2001)

    Google Scholar 

  15. Sandholm, T., Suri, S.: BOB: Improved Winner Determination in Combinatorial Auctions and Generalizations. Artificial Intelligence 145(1-2), 33–58 (2003)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. of Computer Science, Yonsei University, Seoul, 120-749, Korea

    Jin-Woo Song & Sung-Bong Yang

Authors
  1. Jin-Woo Song
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sung-Bong Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Computer Science Department, Tecnológico de Monterrey, Campus Estado de México, Carretera al lago de Guadalupe, Km 3.5, Atizapán, 52926, Mexico

    Raúl Monroy

  2. Instituto de Investigaciones Electricas, Reforma # 113, Col. Palmira, 62490, Morelos, Cuernavaca, Mexico

    Gustavo Arroyo-Figueroa

  3. Instituto Nacional de Astrofísica, Óptica y Electrónica, Luis Enrique Erro No. 1, 72840, Puebla, México

    Luis Enrique Sucar

  4. Centro de Investigación en Computación – IPN, Av. Juan de Dios Batíz, esquina con Miguel Othón de Mendizábal, Ciudad de México, 07738, México

    Humberto Sossa

Rights and permissions

Reprints and permissions

Copyright information

© 2004 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Song, JW., Yang, SB. (2004). A Faster Optimal Allocation Algorithm in Combinatorial Auctions. In: Monroy, R., Arroyo-Figueroa, G., Sucar, L.E., Sossa, H. (eds) MICAI 2004: Advances in Artificial Intelligence. MICAI 2004. Lecture Notes in Computer Science(), vol 2972. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24694-7_37

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-24694-7_37

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-21459-5

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

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation