Proceedings

Multi-Dimensional Bid Improvement Algorithm for Simultaneous Auctions

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 1215-1219.

© 2007 International Joint Conferences on Artificial Intelligence

Abstract

Bidding for multi-items in simultaneous auctions raises challenging problems. In multi-auction settings, the determination of optimal bids by potential buyers requires combinatorial calculations. While an optimal bidding strategy is known when bidding in sequential auctions, only suboptimal strategies are available when bidding for items being sold in simultaneous auctions. We investigate a multi-dimensional bid improvement scheme, motivated by optimization techniques, to derive optimal bids for item bundles in simultaneous auctions. Given a vector of initial bids, the proposed scheme systematically improves bids for each item. Such multi-dimensional improvements result in locally optimal bid vectors. Globally optimal bid vectors are guaranteed in the limit for infinite restarts. For ease of presentation we use two-item scenarios to explain the working of the algorithm. Experimental results show polynomial complexity of variants of this algorithm under different types of bidder valuations for item bundles.

  1. [Byde et al., 2002] Andrew Byde, Chris Preist, and Nicholas R. Jennings. Decision procedures for multiple auctions. In Proceedings of the 1st Joint International Conference on Autonomous Agents and Multi-Agent Systems, pages 613-620. ACM, 2002.
  2. [Candale and Sen, 2006] Teddy Candale and Sandip Sen. A comparison of bidding strategies for simultaneous auc- tions. SIGecomm Exchange, 5(5):41-48, January 2006.
  3. [Greenwald and Boyan, 2003] Amy Greenwald and Justin Boyan. Bidding marginal utility in simultaneous auctions. In Proceedings of the 18 th International Joint Conference on Artificial Intelligence, pages 1463-1464, August 2003. IJCAI
  4. [Greenwald and Boyan, 2004] Amy Greenwald and Justin Boyan. Bidding under uncertainty: theory and experi- ments. In AUAI '04: Proceedings of the 20th conference on Uncertainty in artificial intelligence, pages 209-216. AUAI Press, 2004.
  5. [Greenwald and Boyan, 2005] Amy Greenwald and Justin Boyan. Bidding algorithms for simultaneous auctions: A case study. Journal of Autonomous Agents and Multiagent Systems, 10(1):67-89, 2005.
  6. [Greenwald and Stone, 2001] Amy Greenwald and Peter Stone. Autonomous bidding agents in the trading agent competition. IEEE Internet Computing, 5(2):52-60, 2001.
  7. [Parkes, 2001] David C. Parkes. Iterative Combinatorial Auctions: Achieving Economic and Computational Effi- ciency. PhD thesis, University of Pennsylvania, May 2001.
  8. [Sandholm, 2000] Tuomas Sandholm. eMediator: a next generation electronic commerce server. In AGENTS'00: Proceedings of the Fourth International Conference on Autonomous Agents, pages 341-348. ACM Press, 2000.
  9. [Sandholm, 2002] Tuomas Sandholm. Algorithm for opti- mal winner determination in combinatorial auctions. Arti- ficial Intelligence, 135(1):1-54, 2002.
  10. [Sen et al., 2005] Sandip Sen, Teddy Candale, and Susnata Basak. Profit sharing auction. In Proceedings of the Twen- tieth International Conference on Artificial Intelligence, pages 170-175, July 2005.
  11. [Stone and Greenwald, 2005] Peter Stone and Amy Green- wald. The first international trading agent competition: Autonomous bidding agents. Electronic Commerce Re- search, 5(2):229-65, April 2005.
  12. [Stone et al., 2003] P. Stone, R. E. Schapire, M. L. Littman, J. A. Csirik, and D. McAllester. Decision-theoretic bid- ding based on learned density models in simultaneous, in- teracting auctions. Journal of Artificial Intelligence Re- search, 19:209-242, 2003.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards