Comparing winner determination algorithms for mixed multi-unit combinatorial auctions

ABSTRACT

Mixed multi-unit combinatorial auctions are combinatorial auctions in which the auctioneer and the bidders negotiate over transformations rather than over simple goods. By proposing a transformation a bidder is offering to produce a certain set of output goods after having received the specified input goods. Solving such a mixed auction means choosing a sequence of transformations such that the auctioneer ends up with all the goods desired at the lowest possible cost. This is a generalisation of the winner determination problem in combinatorial auctions and cannot be solved using standard winner determination algorithms. In this paper we analyse the computational complexity of the winner determination problem for mixed auctions and compare the performance of two new algorithms and of the original algorithm proposed for the problem. We also discuss suitable ways of generating test sets for this comparison.

REFERENCES

• 1: J. Cerquides, U. Endriss, A. Giovannucci, and J. A. Rodríguez-Aguilar. Bidding languages and winner determination for mixed multi-unit combinatorial auctions. In Proc. 20th International Joint Conference on Artificial Intelligence, 2007.
• 2: Peter Cramton , Yoav Shoham , Richard Steinberg, Combinatorial Auctions, The MIT Press, 2006
• 3: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 4: Andrea Giovannucci , Meritxell Vinyals , J. A. Rodriguez-Aguilar , Jesus Cerquides, Computationally-efficient winner determination for mixed multi-unit combinatorial auctions, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 5: N. Nisan. Bidding languages for combinatorial auctions. In P. Cramton et al., editors, Combinatorial Auctions. MIT Press, 2006.
• 6: B. Ottens. Comparing winner determination algorithms for mixed multi-unit combinatiorial auctions. Master of Logic thesis, University of Amsterdam, 2007.
• 7: 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]
• 8: M. Vinyals, A. Giovannucci, J. Cerquides, P. Meseguer, and J. A. Rodríguez-Aguilar. Towards a realistic bid generator for mixed multi-unit combinatorial auctions. In Proc. 14th Italian RCRA Workshop, 2007.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES

General Terms:
Algorithms, Economics, Experimentation

Keywords:
combinatorial auctions, integer programming