Bidding algorithms for simultaneous auctions

ABSTRACT

This paper introduces RoxyBot, one of the top-scoring agents in the First International Trading Agent Competition. A TAC agent simulates one vision of future travel agents: it represents a set of clients in simultaneous auctions, trading complementary (e.g., airline tickets and hotel reservations) and substitutable (e.g., symphony and theater tickets) goods. RoxyBot faced two key technical challenges in TAC: (i) allocation---assigning purchased goods to clients at the end of a game instance so as to maximize total client utility, and (ii) completion---determining the optimal quantity of each resource to buy and sell given client preferences, current holdings, and market prices. For the dimensions of TAC, an optimal solution to the allocation problem is tractable, and RoxyBot uses a search algorithm based on A* to produce optimal allocations. An optimal solution to the completion problem is also tractable, but in the interest of minimizing bidding cycle time, RoxyBot solves the completion problem using beam search, producing approximately optimal completions. RoxyBot's completer relies on an innovative data structure called a priceline.

REFERENCES

• 1: B. Abramson, Expected-Outcome: A General Model of Static Evaluation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.2, p.182-193, February 1990 [doi>10.1109/34.44404]
• 2: D. Cliff and J. Bruten. Zero is not enough: On the lower limit of agent intelligence for continuous double auction markets. HP Technical Report HPL-97-141, 1997.
• 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: Rica Gonen , Daniel Lehmann, Optimal solutions for multi-unit combinatorial auctions: branch and bound heuristics, Proceedings of the 2nd ACM conference on Electronic commerce, p.13-20, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352873]
• 5: A. Greenwald, J. Boyan, R. M. Kirby, and J. Reiter. Bid determination in simultaneous auctions. Available at http://www.cs.brown.edu/people/amygreen/, 2001.
• 6: Amy Greenwald , Peter Stone, Autonomous Bidding Agents in the Trading Agent Competition, IEEE Internet Computing, v.5 n.2, p.52-60, March 2001 [doi>10.1109/4236.914648]
• 7: 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]
• 8: Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 9: Tuomas Sandholm , Subhash Suri, Improved Algorithms for Optimal Winner Determination in Combinatorial Auctions and Generalizations, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.90-97, July 30-August 03, 2000
• 10: Peter Stone , Michael L. Littman , Satinder Singh , Michael Kearns, ATTac-2000: an adaptive autonomous bidding agent, Proceedings of the fifth international conference on Autonomous agents, p.238-245, May 2001, Montreal, Quebec, Canada [doi>10.1145/375735.376301]
• 11: G. Tesauro and G. R. Galperin. On-line policy improvement using Monte-Carlo search. In M. C. Mozer, M. I. Jordan, and T. Petsche, editors, Advances in NIPS, volume 9. MIT Press, 1997.
• 12: M. P. Wellman, P. R. Wurman, K. O'Malley, R. Bangera, S.-d. Lin, D. Reeves,and W. E.Walsh. A trading agent competition. IEEE Internet Computing, April 2001.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computational logic

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Algorithms, Design, Performance