TAC

We instantiated our approach as an entry in the second Trading Agent Competition (TAC), as described in this section. Building on the success of TAC-00 held in July 2000 [Wellman, Wurman, O'Malley, Bangera, Lin, Reeves, WalshWellman et al.2001], TAC-01 included 19 agents from 9 countries [Wellman, Greenwald, Stone, WurmanWellman et al.2003a]. A key feature of TAC is that it required autonomous bidding agents to buy and sell multiple interacting goods in auctions of different types. It is designed as a benchmark problem in the complex and rapidly advancing domain of e-marketplaces, motivating researchers to apply unique approaches to a common task. By providing a clear-cut objective function, TAC also allows the competitors to focus their attention on the computational and game-theoretic aspects of the problem and leave aside the modeling and model validation issues that invariably loom large in real applications of automated agents to auctions []<see>rothkopf94. Another feature of TAC is that it provides an academic forum for open comparison of agent bidding strategies in a complex scenario, as opposed to other complex scenarios, such as trading in real stock markets, in which practitioners are (understandably) reluctant to share their technologies.

A TAC game instance pits eight autonomous bidding agents against one another. Each TAC agent is a simulated travel agent with eight clients, each of whom would like to travel from TACtown to Tampa and back again during a 5-day period. Each client is characterized by a random set of preferences for the possible arrival and departure dates, hotel rooms, and entertainment tickets. To satisfy a client, an agent must construct a travel package for that client by purchasing airline tickets to and from TACtown and securing hotel reservations; it is possible to obtain additional bonuses by providing entertainment tickets as well. A TAC agent's score in a game instance is the difference between the sum of its clients' utilities for the packages they receive and the agent's total expenditure. We provide selected details about the game next; for full details on the design and mechanisms of the TAC server and TAC game, see http://www.sics.se/tac.

TAC agents buy flights, hotel rooms and entertainment tickets through auctions run from the TAC server at the University of Michigan. Each game instance lasts 12 minutes and includes a total of 28 auctions of 3 different types.

Flights (8 auctions):

There is a separate auction for each type of airline ticket: to Tampa (inflights) on days $1$-$4$ and from Tampa (outflights) on days $2$-$5$. There is an unlimited supply of airline tickets, and every 24-32 seconds their ask price changes by from $-\$10$ to $\$x$. $x$ increases linearly over the course of a game from 10 to $y$, where $y \in [10,90]$ is chosen uniformly at random for each auction, and is unknown to the bidders. In all cases, tickets are priced between $\$150$ and $\$800$. When the server receives a bid at or above the ask price, the transaction is cleared immediately at the ask price and no resale is allowed.

Hotel Rooms (8):

There are two different types of hotel rooms--the Tampa Towers (TT) and the Shoreline Shanties (SS)--each of which has 16 rooms available on days $1$-$4$. The rooms are sold in a 16th-price ascending (English) auction, meaning that for each of the 8 types of hotel rooms, the 16 highest bidders get the rooms at the 16th highest price. For example, if there are 15 bids for TT on day 2 at $\$300$, 2 bids at $\$150$, and any number of lower bids, the rooms are sold for $\$150$ to the 15 high bidders plus one of the $\$150$ bidders (earliest received bid). The ask price is the current 16th-highest bid and transactions clear only when the auction closes. Thus, agents have no knowledge of, for example, the current highest bid. New bids must be higher than the current ask price. No bid withdrawal or resale is allowed, though the price of bids may be lowered provided the agent does not reduce the number of rooms it would win were the auction to close. One randomly chosen hotel auction closes at minutes 4-11 of the 12-minute game. Ask prices are changed only on the minute.

Entertainment Tickets (12):

Alligator wrestling, amusement park, and museum tickets are each sold for days $1$-$4$ in continuous double auctions. Here, agents can buy and sell tickets, with transactions clearing immediately when one agent places a buy bid at a price at least as high as another agent's sell price. Unlike the other auction types in which the goods are sold from a centralized stock, each agent starts with a (skewed) random endowment of entertainment tickets. The prices sent to agents are the bid-ask spreads, i.e., the highest current bid price and the lowest current ask price (due to immediate clears, ask price is always greater than bid price). In this case, bid withdrawal and ticket resale are both permitted. Each agent gets blocks of 4 tickets of 2 types, 2 tickets of another 2 types, and no tickets of the other 8 types.

In addition to unpredictable market prices, other sources of variability from game instance to game instance are the client profiles assigned to the agents and the random initial allotment of entertainment tickets. Each TAC agent has eight clients with randomly assigned travel preferences. Clients have parameters for ideal arrival day, IAD ($1$-$4$); ideal departure day, IDD ($2$-$5$); hotel premium, HP ($\$50$-$\$150$); and entertainment values, EV ($\$0$-$\$200$) for each type of entertainment ticket.

The utility obtained by a client is determined by the travel package that it is given in combination with its preferences. To obtain a non-zero utility, the client must be assigned a feasible travel package consisting of an inflight on some arrival day AD, an outflight on a departure day DD, and hotel rooms of the same type (TT or SS) for the days in between (days $d$ such that $AD \leq d < DD$). At most one entertainment ticket of each type can be assigned, and no more than one on each day. Given a feasible package, the client's utility is defined as

$$1000 - \emph{travelPenalty} + \emph{hotelBonus} + \emph{funBonus}$$

where

• travelPenalty = $100(\vert AD - {\it IAD}\vert + \vert DD - {\it IDD}\vert)$
• hotelBonus = HP if the client is in the TT, 0 otherwise.
• funBonus = sum of EVs for assigned entertainment tickets.

A TAC agent's score is the sum of its clients' utilities in the optimal allocation of its goods (computed by the TAC server) minus its expenditures. The client preferences, allocations, and resulting utilities from a sample game are shown in Tables 3 and 4.

Table 3: ATTac-2001's client preferences from an actual game. AW, AP, and MU are EVs for alligator wrestling, amusement park, and museum respectively.

Client	IAD	IDD	HP	AW	AP	MU
1	Day 2	Day 5	73	175	34	24
2	Day 1	Day 3	125	113	124	57
3	Day 4	Day 5	73	157	12	177
4	Day 1	Day 2	102	50	67	49
5	Day 1	Day 3	75	12	135	110
6	Day 2	Day 4	86	197	8	59
7	Day 1	Day 5	90	56	197	162
8	Day 1	Day 3	50	79	92	136

Table 4: ATTac-2001's client allocations and utilities from the same actual game as that in Table 3. Client 1's ``4'' under ``Ent'ment'' indicates on day 4.

Client	AD	DD	Hotel	Ent'ment	Utility
1	Day 2	Day 5	SS	AW4	1175
2	Day 1	Day 2	TT	AW1	1138
3	Day 3	Day 5	SS	MU3, AW4	1234
4	Day 1	Day 2	TT	None	1102
5	Day 1	Day 2	TT	AP1	1110
6	Day 2	Day 3	TT	AW2	1183
7	Day 1	Day 5	SS	AF2, AW3, MU4	1415
8	Day 1	Day 2	TT	MU1	1086

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 relatively minor on the surface, these changes significantly enriched the strategic complexity of the game. TAC00-full TAC00-full detail agent strategies from TAC-00.

TAC-01 was organized as a series of four competition phases, culminating with the semifinals and finals on October 14, 2001 at the EC-01 conference in Tampa, Florida. First, the qualifying round, consisting of about 270 games per agent, served to select the 16 agents that would participate in the semifinals. Second, the seeding round, consisting of about 315 games per agent, was used to divide these agents into two groups of eight. After the semifinals, on the morning of the 14th consisting of 11 games in each group, four teams from each group were selected to compete in the finals during that same afternoon. The finals are summarized in Section 6.

TAC is not designed to be fully realistic in the sense that an agent from TAC is not immediately deployable in the real world. For one thing, it is unrealistic to assume that an agent would have complete, reliable access to all clients' utility functions (or even that the client would!); typically, some sort of preference elicitation procedure would be required []<e.g.>boutilier02. For another, the auction mechanisms are somewhat contrived for the purposes of creating an interesting, yet relatively simple game. However, each mechanism is representative of a class of auctions that is used in the real world. And it is not difficult to imagine a future in which agents do need to bid in decentralized, related, yet varying auctions for similarly complex packages of goods.