Bidding algorithms for a distributed combinatorial auction

ABSTRACT

Distributed allocation and multiagent coordination problems can be solved through combinatorial auctions. However, most of the existing winner determination algorithms for combinatorial auctions are centralized. The PAUSE auction is one of a few efforts to release the auctioneer from having to do all the work (it might even be possible to get rid of the auctioneer). It is an increasing price combinatorial auction that naturally distributes the problem of winner determination amongst the bidders in such a way that they have an incentive to perform the calculation. It can be used when we wish to distribute the computational load among the bidders or when the bidders do not wish to reveal their true valuations unless necessary. PAUSE establishes the rules the bidders must obey. However, it does not tell us how the bidders should calculate their bids. We have developed a couple of bidding algorithms for the bidders in a PAUSE auction. Our algorithms always return the set of bids that maximizes the bidder's utility. Since the problem is NP-Hard, run time remains exponential on the number of items, but it is remarkably better than an exhaustive search. In this paper we present our bidding algorithms, discuss their virtues and drawbacks, and compare the solutions obtained by them to the revenue-maximizing solution found by a centralized winner determination algorithm.

REFERENCES

• 1: P. J. Brewer. Decentralized computation procurement and computational robustness in a smart market. Economic Theory, 13(1):41--92, January 1999.
• 2: Peter Cramton , Yoav Shoham , Richard Steinberg, Combinatorial Auctions, The MIT Press, 2006
• 3: 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
• 4: Frank Kelly , Richard Steinberg, A Combinatorial Auction with Multiple Winners for Universal Service, Management Science, v.46 n.4, p.586-596, April 2000 [doi>10.1287/mnsc.46.4.586.12054]
• 5: A. Land, S. Powell, and R. Steinberg. PAUSE: A computationally tractable combinatorial auction. In Cramton et al. {2}, chapter 6, pages 139--157.
• 6: Kevin Leyton-Brown , Mark Pearson , Yoav Shoham, Towards a universal test suite for combinatorial auction algorithms, Proceedings of the 2nd ACM conference on Electronic commerce, p.66-76, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352879]
• 7: M. V. Narumanchi and J. M. Vidal. Algorithms for distributed winner determination in combinatorial auctions. In LNAI volume of AMEC/TADA. Springer, 2006.
• 8: S. Park and M. H. Rothkopf. Auctions with endogenously determined allowable combinations. Technical report, Rutgets Center for Operations Research, January 2001. RRR 3-2001.
• 9: David C. Parkes , Jeffrey Shneidman, Distributed Implementations of Vickrey-Clarke-Groves Mechanisms, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.261-268, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.108]
• 10: 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]
• 11: 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]
• 12: T. Sandholm, S. Suri, A. Gilpin, and D. Levine. CABOB: a fast optimal algorithm for winner determination in combinatorial auctions. Management Science, 51(3):374--391, 2005.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

General Terms:
Algorithms, Performance

Keywords:
combinatorial auctions, coordination, task and resource allocation