next up previous
Next: Bibliography Up: Decision-Theoretic Bidding Based on Previous: Discussion

Related and Future Work

Although there has been a good deal of research on auction theory, especially from the perspective of auction mechanisms [KlempererKlemperer1999], studies of autonomous bidding agents and their interactions are relatively few and recent. TAC is one example. FM97.6 is another auction test-bed, which is based on fishmarket auctions [Rodriguez-Aguilar, Martin, Noriega, Garcia, SierraRodriguez-Aguilar et al.1998]. Automatic bidding agents have also been created in this domain [Gimenez-Funes, Godo, Rodriguez-Aguiolar, Garcia-CalvesGimenez-Funes et al.1998]. There have been a number of studies of agents bidding for a single good in multiple auctions [Ito, Fukuta, Shintani, SycaraIto et al.2000,Anthony, Hall, Dang, JenningsAnthony et al.2001,Preist, Bartolini, PhillipsPreist et al.2001].

A notable auction-based competition that was held prior to TAC was the Santa Fe Double Auction Tournament [Rust, Miller, PalmerRust et al.1992]. This auction involved several agents competing in a single continuous double auction similar to the TAC entertainment ticket auctions. As analyzed by TesauroDas01 TesauroDas01, this tournament was won by a parasite strategy that, like livingagents as described in Section 6.3, relied on other agents to find a stable price and then took advantage of it to gain an advantage. In that case, the advantage was gained by waiting until the last minute to bid, a strategy commonly known as sniping.

TAC-01 was the second iteration of the Trading Agent Competition. The rules of TAC-01 are largely identical to those of TAC-00, with three important exceptions:

  1. In TAC-00, flight prices did not tend to increase;
  2. In TAC-00, hotel auctions usually all closed at the end of the game;
  3. In TAC-00, entertainment tickets were distributed uniformly to all agents
While minor on the surface, the differences significantly enriched the strategic complexity of the game. In TAC-00, most of the designers discovered that a dominant strategy was to defer all serious bidding to the end of the game. A result, the focus was on solving the allocation problem, with most agents using a greedy, heuristic approach. Since the hotel auctions closed at the end of the game, timing issues were also important, with significant advantages going to agents that were able to bid in response to last-second price quotes [Stone GreenwaldStone Greenwald2003]. Nonetheless, many techniques developed in 2000 were relevant to the 2001 competition: the agent strategies put forth in TAC-00 were important precursors to the second year's field, for instance as pointed out in Section 5.1.

Predicting hotel clearing prices was perhaps the most interesting aspect of TAC agent strategies in TAC-01, especially in relation to TAC-00 where the last-minute bidding created essentially a sealed-bid auction. As indicated by our experiments described in Section 6.3, there are many possible approaches to this hotel price estimation problem, and the approach chosen can have a significant impact on the agent's performance. Among those observed in TAC-01 are the following [Wellman, Greenwald, Stone, WurmanWellman et al.2002], associated in some cases with the price-predictor variant in our experiments that was motivated by it.

  1. Just use the current price quote $p_t$ (CurrentBid).
  2. Adjust based on historic data. For example, if $\Delta_t$ is the average historical difference between clearing price and price at time \( t \), then the predicted clearing price is $p_t + \Delta_t$.
  3. Predict by fitting a curve to the sequence of ask prices seen in the current game.
  4. Predict based on closing price data for that hotel in past games ( $\mbox{\sf {SimpleMean}}_{ev}$, $\mbox{\sf {SimpleMean}}_{s}$).
  5. Same as above, but condition on hotel closing time, recognizing that the closing sequence will influence the relative prices.
  6. Same as above, but condition on full ordering of hotel closings, or which hotels are open or closed at a particular point ( $\mbox{\sf {Cond'lMean}}_{ev}$, $\mbox{\sf {Cond'lMean}}_{s}$).
  7. Learn a mapping from features of the current game (including current prices) to closing prices based on historic data ( $\mbox{\sf {ATTac-2001}}_{s}$, $\mbox{\sf {ATTac-2001}}_{ev}$).
  8. Hand-construct rules based on observations about associations between abstract features.

Having demonstrated ATTac-2001's success at bidding in simultaneous auctions for multiple interacting goods in the TAC domain, we extended our approach to apply it to the U.S. Federal Communications Commission (FCC) spectrum auctions domain [WeberWeber1997]. The FCC holds spectrum auctions to sell radio bandwidth to telecommunications companies. Licenses entitle their owners to use a specified radio spectrum band within a specified geographical area, or market. Typically several licenses are auctioned off simultaneously with bidders placing independent bids for each license. The most recent auction brought in over $16 billion dollars. In a detailed simulation of this domain [Csirik, Littman, Singh, StoneCsirik et al.2001], we discovered a novel, successful bidding strategy in this domain that allows the bidders to increase their profits significantly over a reasonable default strategy [Reitsma, Stone, Csirik, LittmanReitsma et al.2002].

Our ongoing research agenda includes applying our approach to other similar domains. We particularly expect the boosting approach to price prediction and the decision-theoretic reasoning over price distributions to transfer to other domains. Other candidate real-world domains include electricity auctions, supply chains, and perhaps even travel booking on public e-commerce sites.

This work was partially supported by the United States-Israel Binational Science Foundation (BSF), grant number 1999038. Thanks to the TAC team at the University of Michigan for providing the infrastructure and support required to run many of our experiments. Thanks to Ronggang Yu at the University of Texas at Austin for running one of the experiments mentioned in the article. Most of this research was conducted while all of the authors were at AT&T Labs -- Research.

next up previous
Next: Bibliography Up: Decision-Theoretic Bidding Based on Previous: Discussion
Peter Stone 2003-09-24