This site is best viewed using a newer browser that supports style sheets

TAC LOGO WELCOME TO THE TRADING AGENT COMPETITION
Competitive Benchmarking for The Trading Agent Community
 LOGIN | SEARCH | FAQ | LEGAL NOTICES
TAC 2012
Info & Call
Registration
Participants
TADA-12 *
* link to external site
 
   

Game Overview

Before going into details, note that the following changes have been made to TAC Classic before the 2004 competition:
  • Games are now 9 minutes instead of 12 (first hotel auction close after 1 minute)
  • Changed flight price perturbation
Read more about the changes.

In the TAC shopping game, each "agent" (an entrant to the competition) is a travel agent, with the goal of assembling travel packages (from TACtown to Tampa, during a notional 5-day period). Each agent is acting on behalf of eight clients, who express their preferences for various aspects of the trip. The objective of the travel agent is to maximize the total satisfaction of its clients (the sum of the client utilities).

Travel packages consist of the following:

  • A round-trip flight,
  • A hotel reservation, and
  • Tickets to some of the following entertainment events
    • Alligator wrestling
    • Amusement park
    • Museum

    Illustration of the environment a TAC agent operates within. To the left are its eight clients and their preferences, in the middle all its competitors lined up (7 competitors/game), and to its right are all the auctions (28 simultaneous auctions of three different types).

    There are obvious interdependencies, as the traveler needs a hotel for every night between arrival and departure of the flight, and can attend entertainment events only during that interval. In addition, the clients have individual preferences over which days they are in Tampa, the type of hotel, and which entertainment they want. All three types of goods (flights, hotels, entertainment) are traded in separate markets with different rules.

    A run of the game is called an instance. Several instances of the game are played during each round of the competition in order to evaluate each agent's average performance and to smooth the variations in client preferences.

    Detailed Rules Outline


    Goods

    Flights

    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:
    1. An agent submits a bid to the auction.
    2. 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:

    "((q1 p1) (q2 p2) ... (qn pn))"

    where qi is a quantity and pi is a price. If there is a point (qi pi) with qi > 0, then it means that the agent is willing to buy qi units of the good at the auction for no more than pi price units per unit of the good. If there is a pair (qj pj) with qj < 0, then it means that the agent is willing to sell qj units of the good at the auction for no less than pj 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:
    1. b must offer to buy at least one unit at a price of ASK+1 or greater.
    2. 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


    Copyright © 2001-2012 SICS AB. All Rights Reserved.
    For questions about Trading Agent Competition or about this web site, contact tac-dev [at] sics.se