Trading Agent Competition - TAC Classic

TACAIR is the only airline to fly between TACtown and Tampa. It operates only one flight each way per day. Tickets for these flights are sold in single seller auctions---one auction for each day and direction (in or out). Since all clients must stay at least one night in Tampa, there will be no inflights on the last day, nor outflights on the first day. The auctions will clear continuously. TACAIR is represented in the marketplace by an agent that sets prices according to a stochastic function. The process used to update flight prices is a random walk, starting between $250 and $400 and perturbed every 10 seconds by a value drawn uniformly from

[-10,x(t)] if x(t) > 0
[x(t), 10] if x(t) < 0
[-10, 10] if x(t) = 0

The final upper bound x on perturbations is a random variable (not revealed directly to the agents), chosen for each flight independently from a uniform distribution on [-10,30]. The upper bound on perturbations at time t, x(t), is a linear interpolation between 10 and the final bound x: x(t) = 10 + (t/9:00)*(x-10). Regardless of the perturbations, prices are constrained to remain in the range $150 to $800. The distribution of initial flight prices is also uniform. The supply of available seats on these flights is, as far as TAC agents are concerned, unlimited.

Hotels

There are two hotels in Tampa: the Tampa Towers (TT) and Shoreline Shanties (SS). TT is cleaner, more comfortable, and more convenient---all-around a nicer place to stay. For this reason, we would expect TT to cost more. Note that a client cannot move between hotels during its trip.

Rooms at the hotels are traded in ascending auctions: one auction for each combination of hotel and night, each with 16 rooms being auctioned off. Only the hotels can sell rooms. There is no minimum bid for either type of hotel. The price difference between the hotels is based on preference for Tampa Towers, as defined by the client utility functions (see next section).

Since clients need hotels only from the night of their arrival and through the night before their departure, no hotels will be available (or needed) on the last day.

Entertainment Tickets

At commencement of a game instance, each travel agent receives an allotment of entertainment tickets. There are a total of 8 tickets available for each event type on each day, and each agent receives 12 tickets partitioned as follows:

One bundle of four of a particular type on day 1 or day 4.
One bundle of four of a particular type on day 2 or day 3.
One bundle of two of a particular type (different from above) on day 1 or day 4.
One bundle of two of a particular type (different from above) on day 2 or day 3.

Agents exchange entertainment tickets through a continuous double auction (CDA). The travel agents can act both as buyers and sellers in these markets. There is one auction for each event-night combination.

As with the hotels, a client cannot use an entertainment ticket on the day of departure.

Auctions

All of the auctions run according to the following high-level protocol:

An agent submits a bid to the auction.
The auction updates its price quote, indicating the current going prices.

The rules for a particular auction specify when, or under what conditions the auction will match the bids and record the transactions.

Bid Format

A bid contains a bid string, representing an agent's willingness to buy and sell the good in an auction. A bid string containing a list of bid points in the following form:

"((q₁ p₁) (q₂ p₂) ... (q_n p_n))"

where q_i is a quantity and p_i is a price. If there is a point (q_i p_i) with q_i > 0, then it means that the agent is willing to buy q_i units of the good at the auction for no more than p_i price units per unit of the good. If there is a pair (q_j p_j) with q_j < 0, then it means that the agent is willing to sell qj units of the good at the auction for no less than p_j price units per unit of the good. The prices should always be nonnegative.

Given a list of quantity-point points that comprise the agent's bid string, say, ((-2 $40) (3 $20) (1 $10)), the semantics of the bid are "I am willing to sell 2 units if the price is $40 or more; I am willing to buy 3 if the price is $20 or less; and I am willing to buy 1 (in addition to the 3) if the price is $10 or less."

Note that, it is illegal to place a bid in which the agent would sell a good to itself. For instance if an agent placed the bid "((-1 10) (1 20))" it could potentially sell 1 unit to itself at a price between $10 and $20.

When a bid is matched at the AuctionBot, the bid string changes to reflect the match. For instance, if an agent places the bid "((-1 10) (-1 20))" and sells one unit of the good for $10, then the bid string would become "((-1 20))".

Flight Auctions

Flight auctions are continuous one-sided auctions, and close at the end of the game.

Agents may submit buy bids, but not sell bids. Only the TACAIR seller may submit sell bids, as specified here.

Price quotes are issued immediately in response to new bids. The price quote is specified as the ask price, which is simply the price of the current sell bid.

Flight auctions clear continually. Any buy bid points that are at least as high as the current ask price will match immediately at the ask price. Any buy bids that do not match immediatly remain in the auction as standing bids. A standing buy bid remains in the auction until it is matched by a sell bid with a price at or below the buy bid, or until the bid is withdrawn. A standing buy bid matches at the price of the buy bid. For instance, assume that TACAIR places a sell bid of ((-64 300)), then:

A bid of ((5 370)) would match five units at $300 each.
A bid of ((3 290)) would not match, and would remain standing in the auction. A subsequent sell bid at $290 or lower would match three units at $290 each from the buy bid.
A bid of ((2 370) (3 290)) would match two units at $300 each. Since the entire bid would not match, the remaining portion, ((3 290)), would remain standing in the auction.

Hotel Auctions

Hotel auctions are standard English ascending multi-unit, except that they close at randomly determined times. Specifically, at 01:00 (one minute) into the game, one randomly chosen hotel auction will close. Another hotel auction closes each minute thereafter, on the minute, again chosen randomly, until 8:00 when the last hotel auction is closed. The agents cannot tell in advance which hotel auction will close at which time. A hotel auction clears and matches bids only once, when it closes. Price quotes are only generated once per minute, on the minute.

Agents may submit buy bids, but not sell bids. Only the hotel owners may submit sell bids. The hotel owners submit bids to provide up to 16 rooms of each hotel type on each night, for a minimum price of $0.

Price quotes are issued every minute, on the minute. The price quote is the ask price, calculated as the 16th highest price among all buy and sell bid units. For instance, if the following bids were in a hotel auction, the ask price would be $0:

((-16 0)), ((2 4) (6 6)), ((4 8)).

If however, the following bids were in a hotel auction, the ask price would be $6:

((-16 0)), ((2 4) (6 6)), ((4 8)), ((7 10)).

When agents submit new bids, they must "beat the quote", according to the following rules:

Let ASK be the current ask quote (16th highest price). Any new bid b must satisfy the following conditions to be admitted to the auction:

b must offer to buy at least one unit at a price of ASK+1 or greater.

If the agent's current bid b' would have resulted in a purchase of q units in the current state, then the new bid b must offer to buy at least q units at ASK+1 or greater.

Agents may not withdraw bids from hotel auctions.

When a hotel auction clears, the 16 highest price buy units will be matched and the agents will pay the ask price for the hotel rooms. For instance, assume the following bids were in a hotel auction at the closing time:

Hotel bid: ((-16 0)),
Agent 1: ((8 2))
Agent 2: ((2 4) (6 6)),
Agent 3: ((4 8)),
Agent 4: ((7 10)).

In this example, Agent 4 would win 7 rooms, Agent 3 would win 4 rooms, Agent 2 would win 5 rooms, and Agent 1 would not win any rooms. The price of the rooms would be $6.

Entertainment Ticket Auctions

The entertainment ticket auctions are standard continuous double auctions (much like a stock market) that close when the game ends. Agents may submit bids with buy and/or sell points (so long as a bid does not specify that the agent sell to itself).

Entertainment ticket auctions clear continuously. Bids match immediately, if possible. A bid that does not completely match remains standing in the auction.

Buy bid points will immediately match the lowest price standing sell bid points that have prices at or below the price of the buy bid. Sell bid points will immediately match the highest price standing buy bid points that have prices above the price at or below the sell bid. Bids match at the price of the standing bid in the auction.

Price quotes are issued immediately in response to new bids. The price quote is specified as the bid and ask price. The bid price is the price of the highest standing buy point. The ask price is the price of the lowest standing sell point.

As an example, consider the following standing bids in an entertainment ticket auction:

((-1 100))
((-4 90) (-2 50))
((-6 60))
((1 40) (3 10))
((1 20))

The bid price is $40 and the ask price is $50. The following examples show what would happen if a new bid entered the auction:

A new bid of ((-1 45)) would not match and would become a standing bid. The ask price would become $45.
A new bid of ((3 48)) would not match and would become a standing bid. The bid price would become $48.
A new bid of ((6 70)) would match two units at $50 each and four units at $60 each. The ask price would become $60.
A new bid of ((-3 15)) would match one unit at $40 each and one unit at $20. Since this bid wouldn't match completely, the remaining portion would remain standing in the auction as ((-1 15)). The bid price would become $10 and the ask price would become $15.

Client Utility Functions

Clients specify their preferences by:

A single preferred arrival date (PA).
A single preferred departure date (PD).

The arrival and departure preferences for each client are chosen randomly such that all possible pairs of arrival/departure days are equally likely.

A premium value for upgrading to the better hotel (HP).

Hotel premium values are chosen for each client uniformly in the range $50 to $150.

A premium value for each type of entertainment event (AW, AP, MU).

Entertainment premium values are chosen uniformly in the range $0 to $200 for every entertainment type.

Let a travel package be specified by:

An actual arrival date (AA).
An actual departure date (AD).
Tampa Towers indicator (TT? in {0,1}).

A travel package is feasible if it contains rooms for every night between the arrival and departure dates. The soonest that any client can leave is one day after arrival. Note that it will never make sense to give a client a hotel for the day of departure. Also, the hotel bonus that a client gets for staying in the Tampa Towers is a bonus for the whole trip, not per night.

An entertainment package is a set of event tickets consisting of no more than one ticket of each type. For the purposes of computing the utility of an entertainment package, we use an abstract representation:

A ticket indicator for each event type (AW?, AP?, MU?, each in {0,1}).

An entertainment package is feasible if none of the tickets are for events on the same day, and all of the tickets coincide with nights the client is in town. Also note that the client does not get additional utility for attending the same type of entertainment more than once during their trip.

A client's utility, measured in dollars, from a feasible travel package and a feasible entertainment package is given by the following:

u = 1000 - travel_penalty + hotel_bonus + fun_bonus

where

travel_penalty = 100*(|AA - PA| + |AD - PD|)
hotel_bonus = TT? * HP
fun_bonus = AW? * AW + AP? * AP + MU? * MU

A client receives zero utility for an infeasible package.

The following table shows the range of possible utilities for a feasible package assigned to a particular client.

                  
                  Arr    Dep   Hotel   AW    AP    MU

    Umin = 1000 - 300  - 300  +   0  +  0 +   0 +   0 =  400

    Umax = 1000 -   0  -   0  + 150 + 200 + 200 + 200 = 1750

Final Score

At the end of the game, the travel agent holds several plane tickets, hotel rooms and event tickets. If it ends the game holding negative balances of any entertainment tickets (because it sold tickets it did not have), it is assessed a penalty of 200 for each ticket owed.

The TAC scorer allocates the agent's travel goods to its individual clients in order to construct feasible trips. Value for a particular allocation is the sum of the individual client utilities. The agent's final score is the value of the allocation of the goods to clients, minus the travel agent's expenses, minus a penalty for negative entertainment balances (if applicable). The scorer attempts to construct an optimal allocation, and usually succeeds or comes very close.

Printable page