\documentstyle[jair,twoside,11pt,epsfig,url,theapa,macros]{article}

\long\def\comment#1{{\bf**{#1}**}} 

\newcommand{\namecite}[1]{{\citeauthor{#1}~\citeyear{#1}}}
\newcommand{\npcite}[1]{{\citeauthor{#1}~\citeyear{#1}}}

\newcommand{\agentfont}{\sf}

\newcommand{\attac}{{\agentfont ATTac-2001}}
\newcommand{\attacold}{{\agentfont ATTac-2000}}
\newcommand{\attacbig}{ATTac-2001}

\newlength{\hrulegap}
\setlength{\hrulegap}{0.2em}

\newcommand{\IAD}{{\it IAD}}
\newcommand{\IDD}{{\it IDD}}
\def\optalloc{{$G^*$}}
\def\optallocval{{$v(G^*)$}}
\newcommand{\agnt}[1]{{\agentfont{#1}}}

\newcommand{\un}{\perp}
\newcommand{\paren}[1]{\left({#1}\right)}
\newfont{\msym}{msbm10}
\newcommand{\reals}{\mbox{\msym R}}
\newcommand{\fabove}{\overline{f}}
\newcommand{\fbelow}{\underline{f}}
\newcommand{\sampagent}[1]{$\mbox{\agentfont {#1}}_{s}$}
\newcommand{\nosampagent}[1]{$\mbox{\agentfont {#1}}_{ev}$}
\newcommand{\atfulsamp}{\sampagent{\attacbig}}  % ATTac1
\newcommand{\atfulnosamp}{\nosampagent{\attacbig}}  % ATTac2
\newcommand{\atcondsamp}{\sampagent{Cond'lMean}}  % ATTac3
\newcommand{\atcondnosamp}{\nosampagent{Cond'lMean}}  % ATTac4
\newcommand{\atsimpsamp}{\sampagent{SimpleMean}}  % ATTac5
\newcommand{\atsimpnosamp}{\nosampagent{SimpleMean}}  % ATTac6
\newcommand{\atcurbid}{{\agentfont CurrentBid}}  % ATTac7
\newcommand{\livag}{{\agentfont EarlyBidder}}  % ATTac8

\newcommand{\atshcdsamp}{\sampagent{Cond'lMean}}  % ATTac3
\newcommand{\atshcdnosamp}{\nosampagent{Cond'lMean}}  % ATTac4

\jairheading{19}{2003}{209-242}{12/02}{9/03}
\ShortHeadings{Decision-Theoretic Bidding with Learned
  Density Models}
{Stone, Schapire, Littman, Csirik, \& McAllester}

\firstpageno{209}

\begin{document}

\title{Decision-Theoretic Bidding Based on Learned Density Models in
Simultaneous, Interacting Auctions}

\author{\name Peter Stone \email pstone@cs.utexas.edu \\
  \addr Dept. of Computer Sciences, 
  The University of Texas at Austin\\
  1 University Station C0500, 
     Austin, Texas 78712-1188 USA   \\
 \name Robert E.\ Schapire \email schapire@cs.princeton.edu \\
       \addr Department of Computer Science, Princeton University\\ 35
       Olden Street, Princeton, NJ 08544  USA \\
  \name Michael L.\ Littman \email mlittman@cs.rutgers.edu \\
  \addr Dept. of Computer Science, Rutgers University\\ Piscataway, NJ
        08854-8019 USA\\
 \name J\'{a}nos A.\ Csirik \email janos@pobox.com \\    
        \addr D.~E.~Shaw \& Co.\\ 120 W 45th St, New York, NY 10036 USA\\
  \name David McAllester \email mcallester@tti-chicago.edu\\
   \addr Toyota Technological Institute at Chicago\\ 1427 East 60th
   Street, Chicago IL, 60637 USA\\
}

\maketitle

\begin{abstract}
Auctions are becoming an increasingly popular method for transacting
business, especially over the Internet.  This article presents a general
approach to building autonomous bidding agents to bid in multiple
simultaneous auctions for interacting goods.  A core component of our approach
learns a model of the empirical price dynamics based on past data
and uses the model to analytically calculate, to the greatest extent
possible, optimal bids.  We introduce a new and general boosting-based
algorithm for conditional density estimation problems of this kind,
{\it i.e.}, supervised learning problems in which the goal is to estimate
the entire conditional distribution of the real-valued label.  This
approach is fully implemented as \attac, a top-scoring agent in the
second Trading Agent Competition (TAC-01).
We present experiments demonstrating the
effectiveness of our boosting-based price predictor relative to
several reasonable alternatives.
\end{abstract}

\section{Introduction}

Auctions are an increasingly popular method for transacting
business, especially over the Internet.  In an auction for a single
good, it is straightforward to create automated bidding
strategies---an agent could keep bidding until reaching a target
reserve price, or it could monitor the auction and place a winning bid
just before the closing time (known as {\it sniping}).

When bidding for multiple interacting goods in simultaneous auctions,
on the other hand, agents must be able to reason about uncertainty and
make complex value assessments.  For example, an agent bidding on
one's behalf in separate auctions
for a camera and flash may end up buying the flash and
then not being able to find an affordable camera.  Alternatively, if
bidding for the same good in several auctions, it may purchase two
flashes when only one was needed.

This article makes three main contributions.  The first contribution is
a general approach to building autonomous bidding agents to bid in
multiple simultaneous auctions for interacting goods.  We start with
the observation that the key challenge in auctions is the prediction
of eventual prices of goods: with complete knowledge of eventual
prices, there are direct methods for determining the optimal bids to
place.  Our guiding principle is to have the agent model its {\it
uncertainty} in eventual prices and, to the greatest extent possible,
analytically calculate optimal bids.

To attack the price prediction problem, we propose a machine-learning
approach: gather examples of previous auctions and the prices paid in
them, then use machine-learning methods to predict these prices based
on available features in the auction.
Moreover, for our strategy, we needed to be able to model the
uncertainty associated with predicted prices; in other words, we
needed to be able to sample from a predicted distribution of prices
given the current state of the game.  This can be viewed as a {\em
conditional density estimation\/} problem, that is, a supervised
learning problem in which the goal is to estimate the entire
distribution of a real-valued label given a description of current
conditions, typically in the form of a feature vector.  The second main
contribution of this article is a new algorithm for solving such
general problems based on boosting~\cite{FreundSc97,SchapireSi99}.

The third contribution of this article is a complete description of a
prototype implementation of our approach in the form of \attac, a
top-scoring agent\footnote{Top-scoring by one metric, and second place
by another.}  in the second Trading Agent Competition (TAC-01) that
was held in Tampa Bay, FL on October~14, 2001~\cite{EM02}.  The TAC
domain was the main motivation for the innovations reported here.
\attac\ builds on top of \attacold~\cite{JAIR-tac00}, the top-scoring
agent at TAC-00, but introduces a fundamentally new approach to
creating autonomous bidding agents.

We present details of \attac\ as an instantiation of its underlying
principles that we believe have applications in a wide variety of
bidding situations.  \attac\ uses a predictive, data-driven approach
to bidding based on expected marginal values of all available goods.
In this article, we present empirical results demonstrating the
robustness and effectiveness of \attac's adaptive strategy.  We also
report on \attac's performance at TAC-01 and TAC-02 and reflect on
some of the key issues raised during the competitions.

The remainder of the article is organized as follows.  In
Section~\ref{sec:general}, we present our general approach to bidding
for multiple interacting goods in simultaneous auctions.  In
Section~\ref{sec:tac}, we summarize TAC, the substrate domain for our work.
Section~\ref{sec:hotel-prediction} describes our boosting-based 
price predictor.
In Section~\ref{sec:attac}, we give the details of \attac.  In
Section~\ref{sec:results}, we present empirical results including a
summary of \attac's performance in TAC-01, controlled experiments
isolating the successful aspects of \attac, and controlled experiments
illustrating some of the lessons learned during the competition.
A discussion and summary of related work is provided in
Sections~\ref{sec:discussion} and~\ref{sec:conc}.


\section{General Approach}
\label{sec:general}

In a wide variety of decision-theoretic settings, it is useful to be
able to evaluate hypothetical situations.  In computer chess, for
example, a static board evaluator is used to heuristically measure
which player is ahead and by how much in a given board situation.  The
scenario is similar in auction domains, and our bidding agent
\attac\ uses a situation evaluator, analogous to the static board
evaluator, which estimates the agent's expected profit in a
hypothetical future situation.  This ``profit predictor'' has a wide
variety of uses in the agent.  For example, to determine the value of
an item, the agent compares the predicted profit assuming the item is
already owned to the predicted profit assuming that the item is not
available.

Given prices for goods, one can often compute a set of purchases and
an allocation that maximizes profit.\footnote{The problem is
computationally difficult in general, but has been solved effectively
in the non-trivial TAC setting~\cite{boyan01,JAIR-tac00}.}  
Similarly, if closing
prices are known, they can be treated as fixed, 
and optimal bids can be computed (bid high for anything you want to
buy).  So, one natural profit predictor is simply to calculate the
profit of optimal purchases under fixed predicted prices.  (The
predicted prices can, of course, be different in different situations,
e.g., previous closing prices can be relevant to predicting future
closing prices.)

A more sophisticated approach to profit prediction is to construct a
model of the probability distribution over possible future prices and
to place bids that maximize \emph{expected} profit.  An approximate solution
to this difficult optimization problem can be created by
stochastically sampling possible prices and computing a profit
prediction as above for each sampled price.  A sampling-based scheme
for profit prediction is important for modeling uncertainty and
the value of gaining information, {\it i.e.}, reducing the price
uncertainty.  

Section~\ref{sec:abstraction} formalizes this latter approach within a
simplified sequential auction model.  This abstraction illustrates
some of the decision-making issues in our full sampling-based approach
presented in Section~\ref{sec:fullapproach}.  The full setting that
our approach addresses is considerably more complex than the abstract
model, but our simplifying assumptions allow us to focus on a core
challenge of the full scenario.  Our guiding principle is to make
decision-theoretically optimal decisions given profit predictions for
hypothetical future situations.\footnote{An alternative approach would
be to abstractly calculate the Bayes-Nash
equilibrium~\cite{harsanyi68} for the game and play the optimal
strategy.  We dismissed this approach because of its intractability in
realistically complex situations, including TAC.  Furthermore, even if
we were able to approximate the equilibrium strategy, it is reasonable
to assume that our opponents would not play optimal strategies.  Thus,
we could gain additional advantage by tuning our 
approach to our opponents' {\it actual} behavior as observed in the
earlier rounds, which is essentially the strategy we adopted.}

\newcommand{\argmax}{\mathop{\mbox{argmax}}}

\subsection{Simplified Abstraction}
\label{sec:abstraction}

In the simple model, there are $n$ items to be auctioned off in
sequence (first item 0, then item 1, etc.).  The bidder must place a
bid $r_i$ for each item $i$, and after each bid, a closing price $y_i$
is chosen for the corresponding item from a distribution specific to
the item.  If the bid matches or exceeds the closing price, $r_i \ge
y_i$, the bidder holds item $i$, $h_i=1$.  Otherwise, the bidder does
not hold the item, $h_i=0$.  The bidder's utility $v(H)$ is a function of its
final vector of holdings $H=(h_0,\ldots,h_{n-1})$ and its cost is a
function of the 
holdings and the vector of closing prices, $H \cdot Y$.
We will formalize the problem of optimal bid selection and develop a
series of approximations to make the problem solvable.

\subsubsection{Exact Value}

What is the \emph{value} of the auction, that is, the bidder's
expected profit (utility minus cost) for bidding optimally for the
rest of the auction?  If a
bidder knows this value, it can make its next bid to be one that
maximizes its expected profit.
The value is a function of the bidder's current holdings
$H$ and the current item to bid on, $i$.
It can be
expressed as
\begin{equation}
\mbox{value}(i,H) = \max_{r_i} E_{y_i} \max_{r_{i+1}} E_{y_{i+1}} \ldots
                        \max_{r_{n-1}} E_{y_{n-1}} (v(G+H)- G \cdot Y),
\label{e:aucval}
\end{equation}
where the components of $G$ are the new holdings as a result of
additional winnings $g_j \equiv r_j \ge y_j$.  Note that $H$ only has
non-zero entries for items that have already been sold ($\forall j
\geq i, H_j = 0$) and $G$ only has non-zero entries for items that
have yet to be sold ($\forall j < i, G_j = 0$).  Note also that $G$
and $Y$ are fully specified when the $g_j$ and $y_j$ variables (for $j
\geq i$) are bound sequentially by the expectation and maximization
operators.  The idea here is that the bids $r_i$ through $r_{n-1}$ are
chosen to maximize value in the context of the possible closing prices
$y_j$.

Equation~\ref{e:aucval} is closely related to the equations defining
the value of a finite-horizon partially observable Markov decision
process~\cite{papadimitriou87} or a stochastic satisfiability
expression~\cite{littman00}. 
Like these other problems, the sequential auction problem is
computationally intractable for sufficiently general representations
of $v(\cdot)$ (specifically, linear functions of the holdings are not
expressive enough to achieve intractability while arbitrary nonlinear
functions are).

\subsubsection{Approximate Value by Reordering}

There are three major sources of intractability in
Equation~\ref{e:aucval}---the alternation of the maximization and
expectation operators (allowing decisions to be conditioned on an exponential
number of possible sets of holdings), the large number of
maximizations (forcing an exponential number of decisions to be
considered), and the large number of expectations (resulting in sums
over an exponential number of variable settings).

We attack the problem of interleaved operators by moving all but the
first of the maximizations inside the expectations, resulting in an
expression that approximates the value:
\begin{equation}
\mbox{value-est}(i,H) = \max_{r_i} E_{y_i} E_{y_{i+1}} \ldots E_{y_{n-1}}
        \max_{r_{i+1}} \ldots \max_{r_{n-1}} (v(G+H)-G \cdot Y).
\label{e:aucapprox1}
\end{equation}
Because the choices for bids $r_{i+1}$ through $r_{n-1}$ appear more deeply
nested than the bindings for the closing prices $y_i$ through $y_{n-1}$,
they cease to be bids altogether, and instead represent decisions as
to whether to purchase goods at given prices.  
Let $G=\mbox{opt}(H,i,Y)$ be a vector representing the optimal number of
goods to purchase at the prices specified by the vector $Y$ given the
current holdings $H$ starting from auction $i$.  Conceptually, this
can be computed by evaluating 
\begin{equation}
\mbox{opt}(H,i,Y) =\argmax_{g_{i}, \ldots, g_{n-1}} (v(G+H)-H \cdot
Y).
\label{e:aucopt}
\end{equation}
Thus,
Equation~\ref{e:aucapprox1} can be written:
\begin{equation}
\mbox{value-est}(i,H) = \max_{r_i} E_{y_i, \ldots, y_{n-1}} 
        (v(\mbox{opt}(H',i+1,Y)+H')-\mbox{opt}(H',i+1,Y) \cdot Y)
\label{e:aucapprox}
\end{equation}
where
$H'$ is identical to $H$ except the $i$-th component
reflects whether item $i$ is won---$r_i \ge y_i$.

Note that there is a further approximation that can be made by
computing the expected prices (as point values) before solving the
optimization problem.  This approach corresponds to further swapping
the expectations towards the core of the equation:
\begin{equation}
  \mbox{value-est}(i,H)_{ev} = \max_{r_i} 
        (v(\mbox{opt}(H',i+1,E_{Y})+H')-\mbox{opt}(H',i+1,E_{Y}) \cdot E_{Y})
\label{e:aucapprox2}
\end{equation}
where $ E_{Y} = E[y_{i+1},\ldots,y_{n-1}] $, the vector of
expected costs of the goods.  In the remainder of the article, we
refer to methods that use this further approximation from
Equation~\ref{e:aucapprox2} as expected value approaches for reasons
that will be come apparent shortly.

The technique of swapping maximization and expectation operators was
previously used by \namecite{hauskrecht97} to generate a bound for
solving partially observable Markov decision processes.  The decrease
of uncertainty when decisions are made makes this approximation an
upper bound on the true value of the auction: $\mbox{value-est} \ge
\mbox{value}$.  The tightness of the approximations in
Equations~\ref{e:aucapprox1} and~\ref{e:aucapprox2} depends on the
true distributions of the expected prices.  For example, if the prices
were known in advance with certainty, then both approximations are
exact.


\subsubsection{Approximate Bidding}

Given a vector of costs $Y$, the optimization problem
$\mbox{opt}(H,i,Y)$ in Equation~\ref{e:aucapprox} is still NP-hard
(assuming the representation of the utility function $v(\cdot)$ is
sufficiently complex).  For many representations of $v(\cdot)$, the
optimization
problem can be cast as an integer linear program and approximated by
using the fractional relaxation instead of the exact optimization
problem.  This is precisely the approach we have adopted in
ATTac~\cite{JAIR-tac00}.

\subsubsection{Approximation via Sampling}

Even assuming that $\mbox{opt}(H,i,Y)$ can be solved in unit time, a
literal interpretation of Equation~\ref{e:aucapprox} says we'll need to
solve this optimization problem for an exponential number of cost
vectors (or even more if the probability distributions $\Pr(y_j)$ are
continuous).  \namecite{kearns99b} showed that values of partially
observable Markov decision processes could be estimated accurately by
sampling trajectories instead of exactly computing sums.
\namecite{littman00} did the same for stochastic satisfiability
expressions.  Applying this idea to Equation~\ref{e:aucapprox} leads
to the following algorithm.

\begin{enumerate}
\item Generate a set $S$ of vectors of closing costs $Y$
according to the product distribution
$\Pr(y_i)\times\cdots\times\Pr(y_{n-1})$.
\item For each of these samples, calculate $\mbox{opt}(H',i+1,Y)$ as
  defined above and average the results, resulting in the approximation
\begin{equation}
\mbox{value-est}_s(i,H) = \max_{r_i} \sum_{Y\in S} 
         (v(\mbox{opt}(H',i+1,Y)+H')-\mbox{opt}(H',i+1,Y) \cdot Y)/|S|.
\label{e:aucapproxsam}
\end{equation}
\end{enumerate}
This expression converges to value-est with increasing sample size.

A remaining challenge in evaluating Equation~\ref{e:aucapproxsam} is
computing the real-valued bid $r_i$ that maximizes the value.  Note
that we want to buy item $i$ precisely at those closing prices for
which the value of having the item (minus its cost) exceeds the value
of not having the item; this maximizes profit.  Thus, to make a
positive profit, we are willing to pay up to, but not more than, the
difference in value of having the item and not having the item.

Formally,
let $H$ be the vector
of current holdings and $H_w$ be the holdings modified to reflect
winning item $i$.  Let $G_w(Y) = \mbox{opt}(H_w,i+1,Y)$, the optimal
set of purchases assuming item $i$ was won, and $G(Y) =
\mbox{opt}(H,i+1,Y)$ the optimal set of purchases assuming otherwise
(except in cases of ambiguity, we write simply $G_w$ and $G$ for
$G_w(Y)$ and $G(Y)$ respectively).  We want to select $r_i$ to
achieve the equivalence
\begin{equation}
r_i \ge y_i \equiv 
\sum_{Y\in S} (v(G_w+H) - G_w \cdot Y) / |S| - y_i \ge
\sum_{Y\in S} (v(G+H) - G \cdot Y) / |S|.
\label{e:valmax}
\end{equation}
Setting
\begin{equation}
r_i = \sum_{Y\in S} ([v(G_w+H) - G_w \cdot Y] - [v(G+H) - G \cdot Y]) / |S|.
\label{e:bdefn}
\end{equation}
achieves the equivalence desired in Equation~\ref{e:valmax}, as can be
verified by substitution, and
therefore bidding the average difference between holding and not
holding the item maximizes the value.\footnote{Note that the strategy
for choosing $r_i$ in Equation~\ref{e:bdefn} does not exploit the fact
that the sample $S$ contains only a finite set of possibilities for
$y_i$, which might make it more robust to inaccuracies in the
sampling.}


\subsection{The Full Approach}
\label{sec:fullapproach}

Leveraging from the preceding analysis, we define our sampling-based
approach to profit prediction in general simultaneous, multi-unit
auctions for interacting goods. In this scenario, let there be $n$
simultaneous, multi-unit auctions for interacting goods
$a_0,\ldots,a_{n-1}$.  The auctions might close at different times and
these times are not, in general, known in advance to the bidders.
When an auction closes, let us assume that the $m$ units available are
distributed irrevocably to the $m$ highest bidders, who each need to
pay the price bid by the $m$th highest bidder.  This scenario
corresponds to an $m$th price ascending auction.\footnote{For large
enough $m$ it is practically the same as the more efficient $m+1$st
auction.  We use the $m$th price model because that is what is used in
TAC's hotel auctions.}  Note that the same bidder may place multiple
bids in an 
auction, and thereby potentially win multiple units.  We assume that
after the auction closes, the bidders will no longer have any
opportunity to acquire additional copies of the goods sold in that
auction ({\it i.e.}, there is no aftermarket).

Our approach is based upon five assumptions. For $G =
(g_0,\ldots,g_{n-1}) \in \Nats^n$, let $v(G) \in \Reals$ represent the
value derived by the agent if it owns $g_i$ units of the commodity
being sold in auction $a_i$.  Note that $v$ is independent of the
\emph{costs} of the commodities.  Note further that this
representation allows for interacting goods of all kinds, including
complementarity and substitutability.\footnote{Goods are considered
complementary if their value as a package is 
greater than the sum of their individual values; goods are considered
substitutable if their value as a package is less than the sum of
their individual values.}  
The assumptions of our approach are as follows:
\begin{enumerate}
\item \label{predictable} Closing prices are somewhat, but only
somewhat, predictable.  That is, given a set of input features $X$,
for each auction $a_i$, there exists a sampling rule that outputs a
closing price $y_i$ according to a probability distribution of
predicted closing prices for $a_i$.

\item \label{value} Given a vector of holdings $H = (h_0,\ldots,h_{n-1})$
where $h_i \in \Nats$ represents the quantity of the commodity being
sold in auction $a_i$ that are already owned by the agent, and given a
vector of fixed closing prices $Y = (y_0,\ldots,y_{n-1})$, there exists a
tractable procedure $\mbox{opt}(H,Y)$ to determine the optimal set of
purchases $(g_0,\ldots,g_{n-1})$ where $g_i \in \Nats$
represents the number of goods to be purchased in auction $i$ such
that
\[v(\mbox{opt}(H,Y)+H) - \mbox{opt}(H,Y) \cdot Y \geq v(G+H) - G \cdot
Y\] for all $G \in \Nats^n$.  This procedure corresponds to the
optimization problem $\mbox{opt}(H,i,Y)$ in Equation~\ref{e:aucopt}.

\item \label{inf-econ} An individual agent's bids do not have an
appreciable effect on the economy (large population assumption).

\item \label{retractable} The agent is free to change existing bids in
auctions that have not yet closed.

\item \label{future} Future decisions are made in the presence of
complete price information.  This assumption corresponds to the
operator reordering approximation from the previous section.
\end{enumerate}
While these assumptions are not all true in general, they can be
reasonable enough approximations to be the basis for an effective
strategy. 

By Assumption~\ref{inf-econ}, the price predictor can generate
predicted prices prior to considering one's bids.  Thus, we can sample
from these distributions to produce complete sets of closing prices of
all goods.

For each good under consideration, we assume that it is the next one
to close.  If a different auction closes first, we can then revise our
bids later (Assumption~\ref{retractable}).  Thus, we would like to bid
exactly the good's {\em expected marginal utility} to us.  That is, we
bid the difference between the expected utilities attainable with and
without the good.  To compute these expectations, we simply average
the utilities of having and not having the good under different price
samples as in Equation~\ref{e:bdefn}.  This strategy rests on
Assumption~\ref{future} in that we assume that bidding the good's
current expected marginal utility cannot adversely affect our future
actions, for instance by impacting our future space of possible bids.
Note that as time proceeds, the price distributions change in response
to the observed price trajectories, thus causing the agent to
continually revise its bids.


Table~\ref{tab:bid-code} shows pseudo-code for the entire algorithm.
A fully detailed description of an instantiation of this approach is
given in Section~\ref{sec:attac}.

\begin{table}[htb]
{\sloppy\small
\hrule
\vspace{\hrulegap}
\begin{itemize}
\item Let $H = (h_0,\ldots,h_{n-1})$ be the agent's current holdings
  in each of the $n$ auctions.
\item For $i = 0$ to $n-1$ (assume auction $i$ is next to close):
  \begin{itemize}
  \item $\mbox{total-diff} = 0$
  \item $\mbox{counter} = 0$
  \item As time permits:
    \begin{itemize}
    \item For each auction $a_j, j \neq i$, generate a predicted price
      sample $y_j$.  Let $Y = (y_0,\ldots,y_{i-1},\infty,y_{i+1},\ldots,y_{n-1})$.
    \item Let $H_w = (h_0,\ldots,h_{i-1},h_{i}+1,h_{i+1},\ldots,h_{n-1})$, the vector of
    holdings if the agent wins a unit in auction $a_{i}$.
    \item Compute $G_w = \mbox{opt}(H_w,Y)$, the optimal set of
      purchases if the agent wins a unit in auction $a_i$.  Note that no
      additional units of the good will be purchased, since the
      $i$-th component of $Y$ is $\infty$.
    \item Compute $G = \mbox{opt}(H,Y)$, the optimal set of purchases
      if the agent never acquires any additional units in the auction
      $a_i$ and prices are set to $Y$.
    \item $\mbox{diff} =  [v(G_w+H) - G_w \cdot Y] - [v(G+H) - G \cdot Y]$
    \item $\mbox{total-diff} =  \mbox{total-diff} + \mbox{diff}$
    \item $\mbox{counter} = \mbox{counter}+1$
    \end{itemize}
  \item $r = \mbox{total-diff} / \mbox{counter}$
  \item Bid $r$ in auction $a_i$.
  \end{itemize}
\end{itemize}
\vspace{\hrulegap}
\hrule
}
\caption{The decision-theoretic algorithm for bidding in simultaneous,
  multi-unit, interacting auctions.}
\label{tab:bid-code}
\end{table}

\subsection{Example}

Consider a camera and a flash with interacting values to an agent as
shown in Table~\ref{tab:example}.  Further, consider that the agent
estimates that the camera will sell for \$40 with probability 25\%,
\$70 with probability 50\%, and \$95 with probability 25\%.  Consider the
question of what the agent should bid for the flash (in auction
$a_0$).  The decision pertaining to the camera would be made via a
similar analysis.

\begin{table}[htb]
\begin{center}
\begin{tabular}{|l|r|}
\hline
& \emph{utility} \\
\hline
\hline
\emph{camera alone} & {\$50} \\
\hline
\emph{flash alone} & {10} \\
\hline
\emph{both}      & {100}\\
\hline
\emph{neither}  & {0}\\
\hline
\end{tabular}
\end{center}
\caption{The table of values for all combination of camera and flash
  in our example.}
\label{tab:example}
\end{table}

First, the agent samples from the distribution of possible camera
prices.  When the price of the camera (sold in auction $a_1$) is \$70
in the sample:
\begin{itemize}
\item $H=(0,0), H_w=(1,0), Y=(\infty,70)$
\item $G_w = \mbox{opt}(H_w,Y)$ is the best set of purchases the agent
can make with the flash, and assuming the camera costs \$70.  In this
case, the only two options are buying the camera or not.  Buying the
camera yields a profit of $100 - 70 = 30$.  Not buying the
camera yields a profit of $10 - 0 = 10$.  Thus, $G_w = (0,1)$, and 
$[v(G_w+H) - G_w \cdot Y]  = v(1,1) - (0,1) \cdot (\infty,70) = 100 - 70$.
\item Similarly $G = (0,0)$ (since if the flash is not owned, buying
  the camera  yields a profit of $50 - 70 = -20$, and not buying it
  yields a profit of $0 - 0 = 0$) and $[v(G+H) - G \cdot Y] = 0$.
\item $\mbox{val} = 30 - 0 = 30$.
\end{itemize}
Similarly, when the camera is predicted to cost \$40, 
$\mbox{val} = 60 - 10 = 50$; and when the camera is predicted to cost
\$95, $\mbox{val} = 10 - 0 = 10$.  Thus, we expect that 50\% of the
camera price samples will suggest a flash value of \$30, while 25\%
will lead to a value of \$50 and the other 25\% will lead to a value
of \$10.  Thus, the agent will bid $.5\times 30 + .25\times 50 +
.25\times 10 = \$30$
for the flash.

Notice that in this analysis of what to bid for the flash, the actual
closing price of the flash is irrelevant.  The proper bid depends only
on the predicted price of the camera.  To determine the proper bid for
the camera, a similar analysis would be done using the predicted price
distribution of the flash.


\section{TAC}
\label{sec: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~\cite{WellmanTAC00}, TAC-01
included 19 agents from 9 countries~\cite{EM02}.  A key feature of TAC
is that it required {\it autonomous bidding agents} to buy and sell
{\it 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~\cite<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
\url{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.  
\begin{description}

\item[Flights (8 auctions):] There is a separate auction for each type
of airline ticket: to Tampa ({\it inflights}) on days $1$--$4$ and
from Tampa ({\it 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.

\item[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 {\it 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 {\em randomly chosen\/} hotel auction closes at minutes 4--11 of the
12-minute game.  Ask prices are changed only on the minute.

\item[Entertainment Tickets (12):] Alligator wrestling, amusement
park, and museum tickets are each sold for days $1$--$4$ in continuous
double auctions.  Here, agents can {\it 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 {\it bid-ask
spreads}, {\it 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, {\it bid withdrawal} and {\it 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.

\end{description}


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, {\it HP} ($\$50$--$\$150$); and entertainment values,
{\it 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 {\it feasible} travel
package consisting of an inflight on some arrival day {\it AD},
an outflight on a
departure day {\it DD}, and
hotel rooms of the {\it 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
\begin{itemize}
\item {\it travelPenalty} = $100(|AD - \IAD| + |DD - \IDD|)$
\item {\it hotelBonus} = {\it HP} if the client is in the TT,
  0 otherwise.
\item {\it funBonus} = sum of {\it EV}s for assigned entertainment tickets.
\end{itemize}

A TAC agent's {\it 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~\ref{tab:prefs} and~\ref{tab:utils}.

\begin{table}[htb]
\begin{center}
\begin{tabular}{|c|cccccc|} \hline
Client & \IAD & \IDD\ & {\it HP} & {\it AW} &
{\it AP} &  {\it MU} \\ \hline
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 \\ \hline
\end{tabular}
\caption{\attac's client preferences from an actual game.  {\it AW}, {\it
    AP}, and {\it MU} are {\it EV}s for alligator wrestling, amusement park, and
  museum respectively.}
\label{tab:prefs}
\end{center}
\end{table}

\begin{table}[htb]
\begin{center}
\begin{tabular}{|c|cccc|c|} \hline
Client & {\it AD} & {\it DD} & Hotel & Ent'ment & Utility \\ \hline
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 \\ \hline
\end{tabular}
\caption{\attac's client allocations and utilities from the same
  actual game as that in Table~\ref{tab:prefs}.
  Client 1's ``4'' under ``Ent'ment'' indicates  on day 4.}
\label{tab:utils}
\end{center}
\end{table}                                                       

The rules of TAC-01 are largely identical to those of TAC-00, with
three important exceptions:
\begin{enumerate}
\item In TAC-00, flight prices did not tend to increase;
\item In TAC-00, hotel auctions usually all closed at the end of the
game;
\item In TAC-00, entertainment tickets were distributed uniformly to
  all agents
\end{enumerate}
While relatively minor on the surface, these changes significantly
enriched the strategic complexity of the game.  \namecite{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~\ref{sec:results}.

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~\cite<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 \emph{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.

\section{Hotel Price Prediction} 
\label{sec:hotel-prediction}

As discussed earlier, a central part of our strategy depends on the
ability to predict prices, particularly hotel prices,
at various points in the game.
To do this as accurately as possible, we used machine-learning
techniques that would examine the hotel prices actually paid in
previous games to predict prices in future games.
This section discusses this part of our strategy in detail, including
a new boosting-based algorithm for conditional density estimation.

There is bound to be considerable uncertainty regarding hotel prices
since these depend on many unknown factors, such as the time at which
the hotel room will close, who the other agents are, what kind of
clients have been assigned to each agent, etc.  Thus, {\em exactly\/}
predicting the price of a hotel room is hopeless.  Instead, we regard
the closing price as a random variable that we need to estimate,
conditional on our current state of knowledge ({\it i.e.}, number of minutes
remaining in the game, ask price of each hotel, flight prices, etc.).
We might then attempt to predict this variable's conditional expected
value.  However, our strategy requires that we not only predict
expected value, but that we also be able to estimate the {\em
entire\/} conditional distribution so that we can {\em sample\/} hotel
prices.

To set this up as a learning problem, we gathered a set of training
examples from previously played games.
We defined a set of features for describing each
example that 
together are meant to comprise a snap-shot of all the
relevant information available at the time each prediction is
made.
All of the features we used are real valued; a couple of the
features can have a special value $\un$ indicating ``value unknown.''
We used the following basic features:
\begin{itemize}
\item
The number of minutes remaining in the game.
\item
The price of each hotel room, {\it i.e.}, the current ask price for rooms
that have not closed or the actual selling price for rooms that have
closed.
\item
The closing time of each hotel room.
Note that this feature is defined even for rooms that have not yet
closed, as explained below.
\item
The prices of each of the flights.
\end{itemize}
To this basic list, we added a number of redundant variations, which we
thought might help the learning algorithm:
\begin{itemize}
\item
The closing price of hotel rooms that have closed (or
$\un$ if the room has not yet closed).
\item
The current ask price of hotel rooms that have not closed (or
$\un$ if the room has already closed).
\item
The closing time of each hotel room minus the closing time of the room
whose price we are trying to predict.
\item
The number of minutes from the current time until each hotel room
closes.
\end{itemize}

During the seeding rounds, it was impossible to know during play who
our opponents were, although this information was available at the end
of each game, and therefore during training.
During the semifinals and finals, we did know the identities
of all our competitors.
Therefore, in preparation for the semifinals and finals, we added
the
following features:
\begin{itemize}
\item
The number of players playing (ordinarily eight, but sometimes fewer, for
instance if one or more players crashed).
\item
A bit for each player indicating whether or not that player
participated in this game.
\end{itemize}

We trained specialized predictors for predicting the price of each
type of hotel room.
In other words, one predictor was specialized for predicting only the
price of TT on day 1, another for predicting SS on day 2, etc.
This would seem to require eight separate predictors.
However, the tournament game is naturally symmetric about its
middle
in the sense that we can create an equivalent game by
exchanging the hotel rooms on days 1 and 2 with those on days 4 and 3
(respectively),
and by exchanging the inbound flights on days 1, 2, 3 and 4 with the
outbound flights on days 5, 4, 3 and 2 (respectively).
Thus, with appropriate transformations, the outer days (1 and 4) can
be treated equivalently, and likewise for the inner days (2 and 3), 
reducing the number of specialized predictors by half.

We also created specialized predictors for predicting in the first minute
after flight prices had been quoted but prior to receiving any hotel
price information.
Thus, a total of eight specialized predictors were built
(for each combination of TT versus SS, inner versus outer day, and
first minute versus not first minute).

We trained our predictors to predict not the actual closing price of
each room per se, but rather how much the price would increase, {\it i.e.},
the difference between the closing price and the current price.  We
thought that this might be an easier quantity to predict, and, because
our predictor never outputs a negative number when trained on
nonnegative data, this approach also ensures that we never predict a
closing price below the current bid.

{From} each of the previously played games, we were able to extract many
examples.  Specifically, for each minute of the game and for each room
that had not yet closed, we extracted the values of all of the
features described above at that moment in the game, plus the actual
closing price of the room (which we are trying to predict).

Note that during training, there is no problem extracting the closing
times of all of the rooms.  During the actual play of a game, we do
not know the closing times of rooms that have not yet closed.
However, we do know the exact probability distribution for closing
times of all of 
the rooms that have not yet closed.  Therefore, to sample a vector of
hotel prices, we can first sample according to this distribution over
closing times, and then use our predictor to sample hotel prices using
these sampled closing times.


\subsection{The Learning Algorithm}
\label{sec:learn}

Having described how we set up the learning problem, we are now ready
to describe the learning algorithm that we used.  Briefly, we solved
this learning problem by first reducing to a multiclass, multi-label
classification problem (or alternatively a multiple logistic
regression problem), and then applying boosting techniques developed
by Schapire and Singer~\citeyear{SchapireSi99,SchapireSi00} combined
with a modification of boosting algorithms for logistic regression
proposed by Collins, Schapire and Singer~\citeyear{CollinsScSi02}.
The result is a new machine-learning algorithm for solving
conditional density estimation problems, described in detail in the
remainder of this section.  Table~\ref{tab:boost-code} shows
pseudo-code for the entire algorithm.

\begin{table}[t]
{\sloppy\small
\hrule
\vspace{\hrulegap}
\begin{tabbing}
{\bf Input}:~\=$(x_1,y_1),\ldots,(x_m,y_m)$ where $x_i\in X$, $y_i\in\reals$\\
       \>positive integers $k$ and $T$
\end{tabbing}

\medskip

{\bf Compute breakpoints}: $b_0 < b_1 < \cdots < b_{k+1}$ where
\begin{s_itemize}
\item
$  b_0 =  \min_i y_i$
\item
$b_{k+1} =  \max_i y_i$
\item
$b_1, \ldots, b_k$ chosen to minimize $\sum_{j=0}^k q_j \ln q_j$
where $q_0,\ldots,q_k$ are fraction of $y_i$'s in\\
$[b_0,b_1),[b_1,b_2),\ldots,[b_k,b_{k+1}]$ (using dynamic programing)
\end{s_itemize}

\medskip

{\bf Boosting}:
\begin{s_itemize}
\item
for $t=1,\ldots T$:
\begin{s_itemize3}
\item
compute weights
$\displaystyle
 W_t(i,j) = \frac{1}{1+e^{s_j(y_i) f_t(x_i,j)}}
$\\
where $s_j(y)$ is as in Eq.~(\ref{eqn:1})
\item
use $W_t$ to obtain base function $h_t:X\times\{1,\ldots,k\}\rightarrow\reals$
minimizing\\
$\displaystyle
  \sum_{i=1}^m \sum_{j=1}^k W_t(i,j) e^{- s_j(y_i) h_t(x_i, j)}
$
over all decision rules $h_t$ considered.  The decision rules can take any form.  In
our work, we use ``decision stumps,'' or simple thresholds on one of
the features.
\end{s_itemize3}
\end{s_itemize}

\medskip

{\bf Output sampling rule}:
\begin{s_itemize}
\item
let $\displaystyle f = \sum_{t=1}^T h_t$
\item
let $f' = (\fabove + \fbelow) / 2$ where
\begin{eqnarray*}
\fabove(x,j) &=& \max\{f(x, j') : j \leq j' \leq k\} \\
\fbelow(x,j) &=& \min\{f(x, j') : 1 \leq j' \leq j\}
\end{eqnarray*}
\item
to sample, given $x\in X$
\begin{s_itemize3}
\item
let $\displaystyle p_j = \frac{1}{1+e^{-f'(x,j)}}$
\item
let $p_0 = 1, p_{k+1} = 0$
\item
choose $j\in \{0,\ldots,k\}$ randomly with probability $p_j - p_{j+1}$
\item
choose $y$ uniformly at random from $[b_j, b_{j+1}]$
\item
output $y$
\end{s_itemize3}
\end{s_itemize}
\vspace{\hrulegap}
\hrule
}
\caption{The boosting-based algorithm for conditional density estimation.}
\label{tab:boost-code}
\end{table}

Abstractly, we are given pairs $(x_1,y_1),\ldots,(x_m,y_m)$ where each
$x_i$ belongs to a space $X$ and each $y_i$ is in $\reals$.
In our case, the $x_i$'s are the auction-specific feature vectors
described above; for some $n$,
$X\subseteq (\reals \cup \{\un\})^n$.  Each target quantity
$y_i$ is the difference between
closing price and current price.
Given a new $x$, our goal is to estimate the conditional distribution
of $y$ given $x$.

We proceed with the working assumption that all training and test
examples $(x,y)$ are i.i.d.\ (i.e, drawn independently from identical
distributions).
Although this assumption is false in our
case (since the agents, including ours, are changing
over time), it seems like a reasonable approximation that greatly
reduces the difficulty of the learning task.

Our first step is to reduce the estimation problem to a classification
problem by 
breaking the range of the $y_i$'s into bins:
\[
   [b_0,b_1), [b_1,b_2), \ldots, [b_k,b_{k+1}]
\]
for some breakpoints $b_0 < b_1 < \cdots < b_k \leq b_{k+1}$ where for
our problem, we chose $k=50$.\footnote{We did not experiment with
varying $k$, but expect that the algorithm is not sensitive to it for
sufficiently large values of $k$.}  The endpoints $b_0$ and $b_{k+1}$
are chosen to be the smallest and largest $y_i$ values observed during
training.  We choose the remaining breakpoints $b_1,\ldots,b_k$ so
that roughly an equal number of training labels $y_i$ fall into each
bin.  (More technically, breakpoints are chosen so that the entropy of
the distribution of bin frequencies is maximized.)

For each of the breakpoints $b_j$ ($j=1,\ldots,k$),
our learning algorithm attempts to
estimate the probability that a new $y$ (given $x$) will be at least
$b_j$.
Given such estimates $p_j$ for each $b_j$, we can then estimate the
probability that $y$ is in the bin $[b_j,b_{j+1})$ by $p_{j+1}-p_j$
(and we can then use a constant density within each bin).
We thus have reduced the problem to one of estimating multiple
conditional Bernoulli 
variables corresponding to the event $y\geq b_j$, and for this, we use
a logistic regression algorithm based on boosting techniques as
described by \namecite{CollinsScSi02}.

Our learning algorithm constructs a real-valued function
$f:X\times \{1,\ldots,k\} \rightarrow \reals$
with the interpretation that
\begin{equation} \label{eqn:logit}
   \frac{1}{1 + \exp(-f(x,j))}
\end{equation}
is our estimate of the probability that $y\geq b_j$, given $x$.
The negative log likelihood of the conditional Bernoulli variable
corresponding to $y_i$ being above or below $b_j$ is then
\[  \ln\paren{1 + e^{- s_j(y_i) f(x_i, j)}}  \]
where
\begin{equation} \label{eqn:1}
   s_j(y) = \left\{ \begin{array}{ll}
                        +1 & \mbox{if $y \geq b_j$} \\
                        -1 & \mbox{if $y < b_j$.}
                      \end{array}
              \right.
\end{equation}

We attempt to minimize this quantity for all training examples
$(x_i,y_i)$ and all breakpoints $b_j$.
Specifically, we try to find a function $f$ minimizing
\[
\sum_{i=1}^m \sum_{j=1}^k  \ln\paren{1 + e^{- s_j(y_i) f(x_i, j)}}.
\]
We use a boosting-like algorithm described by \namecite{CollinsScSi02}
for minimizing objective functions of 
exactly this form.
Specifically, we build the function $f$ in rounds.
On each round $t$, we add a new base function
$h_t: X \times \{1,\ldots,k\}\rightarrow \reals$.
Let
\[ f_t = \sum_{t' = 1}^{t-1} h_{t'} \]
be the accumulating sum.
Following Collins, Schapire and Singer,
to construct each $h_t$, we first let
\[ W_t(i,j) = \frac{1}{1+e^{s_j(y_i) f_t(x_i,j)}} \]
be a set of weights on example-breakpoint pairs.
We then choose $h_t$ to minimize
\begin{equation}  \label{eqn:obj-fun}
\sum_{i=1}^m \sum_{j=1}^k W_t(i,j) e^{- s_j(y_i) h_t(x_i, j)}
\end{equation}
over some space of ``simple'' base functions $h_t$.
For this work, we considered all ``decision stumps'' $h$ of the form
\[
   h(x,j) = 
         \left\{ \begin{array}{ll}
                        A_j & \mbox{if $\phi(x) \geq \theta$} \\
                        B_j & \mbox{if $\phi(x) < \theta$} \\
                        C_j & \mbox{if $\phi(x) = \un$}
                      \end{array}
              \right.
\]
where $\phi(\cdot)$ is one of the features described above, and
$\theta$, $A_j$, $B_j$ and $C_j$ are all real numbers.
In other words, such an $h$ simply compares one feature $\phi$ to a
threshold $\theta$ and returns a vector of numbers $h(x,\cdot)$ that
depends only on whether $\phi(x)$ is unknown ($\un$), or above or
below $\theta$.
\namecite{SchapireSi00} show how to efficiently
search for the best such $h$ over all possible choices of $\phi$, 
$\theta$, $A_j$, $B_j$ and $C_j$.
(We also employed their technique for
``smoothing'' $A_j$, $B_j$ and $C_j$.)

When computed by this sort of iterative procedure,
\namecite{CollinsScSi02} prove the asymptotic convergence 
of $f_t$ to the minimum of the objective function in
Equation~(\ref{eqn:obj-fun}) over all linear combinations of the base
functions.  For this problem, we fixed the number of rounds to
$T=300$.  Let $f=f_{T+1}$ be the final predictor.

As noted above, given a new feature vector $x$, we compute $p_j$ as in
Equation~(\ref{eqn:logit}) to be our estimate for the probability that
$y\geq b_j$, and we let $p_0 = 1$ and $p_{k+1}=0$.  For this to make
sense, we need $p_1\geq p_2\geq \cdots \geq p_k$, or equivalently,
$f(x,1)\geq f(x,2)\geq \cdots \geq f(x,k)$, a condition that may not
hold for the learned function $f$.  To force this condition, we
replace $f$ by a reasonable (albeit heuristic) approximation $f'$ that
is nonincreasing in $j$, namely, $f' = (\fabove + \fbelow) / 2$ where
$\fabove$ (respectively, $\fbelow$) is the pointwise minimum
(respectively, maximum) of all nonincreasing functions $g$ that
everywhere upper bound $f$ (respectively, lower bound $f$).

With this modified function $f'$, we can compute modified
probabilities $p_j$.  To sample a single point according to the
estimated distribution on $\reals$ associated with $f'$, we choose bin
$[b_j,b_{j+1})$ with probability $p_j - p_{j+1}$, and then select a
point from this bin uniformly at random.  Expected value according to
this distribution is easily computed as
\[ \sum_{j=0}^k  (p_j - p_{j+1}) \paren{\frac{b_{j+1} + b_j}{2}}. \]

Although we present results using this algorithm in the trading agent
context, we did not test its performance on more general learning
problems, nor did we compare to other methods for conditional density
estimation, such as those studied by \namecite{Stone94}.  This
clearly should be an area for future research.

\section{\attacbig}
\label{sec:attac}

Having described hotel price prediction in detail, we now present the
remaining details of \attac's algorithm.  We begin
with a brief description of the goods allocator, which is used as a
subroutine throughout the algorithm.  We then present the algorithm in
a top-down fashion.

\subsection{Starting Point}
\label{sec:alloc}

A core subproblem for TAC agents is the allocation problem: finding
the most profitable allocation of goods to clients, \optalloc, given a
set of owned goods and prices for all other goods.  The allocation
problem corresponds to finding $\mbox{opt}(H,i,Y)$ in
Equation~\ref{e:aucopt}.  We denote the value of \optalloc\ ({\it
i.e.}, the
score one would attain with \optalloc) as \optallocval.  The general
allocation problem is NP-complete, as it is equivalent to the
set-packing problem~\cite{garey79}.  However it can be solved
tractably in TAC via integer linear programming~\cite{JAIR-tac00}.

The solution to the integer linear program is a value-maximizing
allocation of owned resources to clients along with a list of
resources that need to be purchased.  Using the linear programming
package ``LPsolve'', \attac\ is usually able to find the globally
optimal solution in under 0.01 seconds on a 650 MHz Pentium
II.  However, since integer linear programming is an NP-complete
problem, some inputs can lead to a great deal of search over the
integrality constraints, and therefore significantly longer solution
times.  When only \optallocval\ is needed (as opposed to \optalloc\
itself), the upper bound produced by LPsolve prior to the search over
the integrality constraints, known as the LP relaxation, can be used
as an estimate.  The LP relaxation can always be generated very
quickly.

Note that this is not by any means the only possible formulation of
the allocation problem.  \namecite{boyan01} studied a fast, heuristic
search variant 
and found that it performed extremely well on a collection of large,
random allocation problems.  \namecite{JAIR-tac00} used a randomized
greedy strategy as a fallback for the cases in which the linear
program took too long to solve.

\subsection{Overview}

Table~\ref{tab:high-level} shows a high-level overview of \attac.  The
italicized portions are described in the remainder of this section.

\begin{table}[htb]
{\small
\begin{center}
\hrule
\vspace{\hrulegap}
\begin{description}
\item[When the first flight quotes are posted:] \
\begin{noinds_itemize}
\item Compute \optalloc\ with current holdings and 
\emph{expected prices}
\item Buy the flights in \optalloc\ for which \emph{expected cost of
postponing commitment} exceeds the \emph{expected benefit of
postponing commitment}
\end{noinds_itemize}

\item[Starting 1 minute before each hotel close:] \
\begin{noinds_itemize}
\item Compute \optalloc\ with current holdings
and \emph{expected prices}
\item Buy the flights in \optalloc\ for which \emph{expected cost of
postponing commitment} exceeds \emph{expected benefit of postponing
commitment} (30 seconds)
\item Bid \emph{hotel room expected marginal values} given holdings,
  new flights, and \emph{expected hotel purchases} (30 seconds)
\end{noinds_itemize}

\item[Last minute:] Buy remaining flights as needed by \optalloc

\item[In parallel (continuously):] Buy/sell entertainment tickets
based on their \emph{expected values}
\end{description}
\vspace{\hrulegap}
\hrule
\end{center}
}
\caption{\attac's high-level algorithm.  The italicized portions are
  described in the remainder of this section.}
\label{tab:high-level}
\end{table}


\subsection{Cost of Additional Rooms} 

Our hotel price predictor described in
Section~\ref{sec:hotel-prediction} assumes that \attac's bids do not
affect the ultimate closing price (Assumption~\ref{inf-econ} from
Section~\ref{sec:general}).  This assumption holds in a large economy.
However in TAC, each hotel auction involved $8$ agents competing for
$16$ hotel rooms.  Therefore, the actions of each agent had an
appreciable effect on the clearing price: the more hotel rooms an
agent attempted to purchase, the higher the clearing price would be,
all other things being equal.  This effect needed to be taken into
account when solving the basic allocation problem.

The simplified model used by \attac\ assumed that the $n$th highest
bid in a hotel auction was roughly proportional to $c^{-n}$ (over the
appropriate range of $n$) for some $c\geq1$.  Thus, if the predictor
gave a price of $p$, \attac\ only used this for purchasing two hotel
rooms (the ``fair'' share of a single agent of the $16$ rooms), and
adjusted prices for other quantities of rooms by using $c$.  

For example, \attac\ would consider the cost of obtaining $4$ rooms to
be $4pc^2$.  One or two rooms each cost $p$, but $3$ each cost $pc$,
$4$ each cost $pc^2$, 5 each cost $pc^3$, etc.  So in total, $2$ rooms
cost $2p$, while $4$ cost $4pc^2$.  The reasoning behind this procedure
is that if \attac\ buys two rooms --- its fair share given that there
are 16 rooms and 8 agents, then the 16th highest bid (\attac's 2 bids
in addition to 14 others) sets the price.  But if \attac\ bids on an
additional unit, the previous 15th highest bid becomes the
price-setting bid: the price for all rooms sold goes up from $p$ to
$pc$.

The constant $c$ was calculated from the data of several hundred games
during the seeding round.  In each hotel auction, the ratio of the
$14$th and $18$th highest bids (reflecting the most relevant range of
$n$) was taken as an estimate of $c^4$, and the (geometric) mean of
the resulting estimates was taken to obtain $c = 1.35$.

The LP allocator takes these price estimates into account when
computing \optalloc\ by assigning higher costs to larger purchase
volumes, thus tending to spread out \attac's demand over the different
hotel auctions.

In \attac, a few heuristics were applied to the above procedure to
improve stability and to avoid pathological behavior: prices below \$1
were replaced by \$1 in estimating $c$; $c=1$ was used for purchasing
fewer than two hotel rooms; hotel rooms were divided into early
closing and late closing (and cheap and expensive) ones, and the $c$
values from the corresponding subsets of auctions of the seeding
rounds were used in each case.

\subsection{Hotel Expected Marginal Values} 

Using the hotel price prediction module as described in
Section~\ref{sec:hotel-prediction}, coupled with a model of its own
effect on the economy, \attac\ is equipped to determine its bids for
hotel rooms.

Every minute, for each hotel auction that is still open, \attac\
assumes that auction will close next and computes the marginal
value of that hotel room given the predicted closing prices of the
other rooms.  If the auction does not close next, then it assumes that
it will have a chance to revise its bids.  Since these predicted
prices are represented as distributions of possible future prices,
\attac\ samples from these distributions and averages the marginal
values to obtain an expected marginal value.  Using the full minute
between closing times for computation (or 30 seconds if there are
still flights to consider too), \attac\ divides the available time
among the different open hotel auctions and generates as many price
samples as possible for each hotel room.  In the end, \attac\ bids the
expected marginal values for each of the rooms.

The algorithm is described precisely and with explanation in
Table~\ref{tab:hotel-vals}.

\begin{table}[htb]
{\small
\begin{center}
\hrule
\vspace{\hrulegap}
\begin{itemize}
\item For each hotel (in order of increasing expected price):
\item Repeat until time bound
  \begin{s_enumerate}
  \item Generate a random hotel closing order (only over open hotels)
  \item \emph{Sample} closing prices from predicted hotel price distributions 
  \item Given these closing prices, compute $V_0, V_1, \ldots V_n$ 
    \begin{s_itemize3}
    \item $V_i \equiv$ \optallocval\ if owning $i$ of the hotel 
    \item Estimate \optallocval\ with LP relaxation
    \item Assume that no additional hotel rooms of this type can be bought
    \item For other hotels, assume outstanding bids above sampled price
      are already owned ({\it i.e.}, they cannot be withdrawn).
    \item Note that $V_0 \leq V_1 \leq \ldots \leq V_n$:  the values
      are monotonically increasing since having more goods cannot be
      worse in terms of possible allocations.
    \end{s_itemize3}
  \end{s_enumerate}
\item The value of the $i$th copy of the room is the mean of $V_i - V_{i-1}$ over
all the samples.
\item Note further that $V_1 - V_0 \geq V_2 - V_1 \ldots \geq V_n -
  V_{n-1}$:  the value differences are monotonically decreasing since
  each additional room will be assigned to the client who can derive
  the most value from it.
\item Bid for one room at the value of the $i$th copy of the room for
  all $i$ such that the value is at least as much as the current
  price.  Due to the monotonicity noted in the step above,
  no matter what the closing price, the desired number of rooms at
  that price will be purchased.
\end{itemize}
\vspace{\hrulegap}
\hrule
\end{center}
}
\caption{The algorithm for generating bids for hotel rooms.}
\label{tab:hotel-vals}
\end{table}

One additional complication regarding hotel auctions is that, contrary
to one of our assumptions in Section~\ref{sec:fullapproach}
(Assumption~\ref{retractable}), bids are not fully retractable: they
can only be changed to \$1 above the current ask price.  In the case
that there are current active bids for goods that \attac\ no longer
wants that are less than \$1 above the current ask price, it may be
advantageous to refrain from changing the bid in the hopes that the
ask price will surpass them: that is, the current bid may have a
higher expected value than the best possible new bid.  To address this
issue, \attac\ samples from the learned price distribution to find the
average expected values of the current and potential bids, and only
enters a new bid in the case that the potential bid is better.


\subsection{Expected Cost/Benefit of Postponing Commitment} 

\attac\ makes flight bidding decisions based on a cost-benefit
analysis: in particular, \attac\ computes the incremental cost of
postponing bidding for a particular flight versus the value of
delaying commitment.  In this section, we describe the determination of
the cost of postponing the bid.

Due to difficulties that compounded with more sophisticated
approaches, \attac\ used the following very simple model for estimating
the price of a flight ticket at a given future time.  It is evident from
the formulation that---given $y$---the expected 
price increase from time $0$ to time $t$ was very nearly 
of the form $Mt^2$ for some
$M$.  It was also clear that as long as the price did not hit the
artificial boundaries at \$150 and \$800, the constant $M$ must depend
linearly on $y-10$.  This linear dependence coefficient was then
estimated from several hundred flight price evolutions during the
qualifying round.  Thus, for this constant $m$, the expected price
increase from time $t$ to time $T$ was $m(T^2-t^2)(y-10)$.  When a price
prediction was needed, this formula was first used for the first and
most recent actual price observations to obtain a guess for $y$, and
then this $y$ was used in the formula again to estimate the future
price.  No change was predicted if the formula yielded a price decrease.

This approach suffers from systemic biases of various kinds (mainly due
to the fact that the variance of price changes gets relatively smaller
over longer periods of time), but was thought to be accurate enough for
its use, which was to predict whether or not the ticket can be expected
to get significantly more expensive over the next few minutes.

In practice, during TAC-01, \attac\ started with the {\it
flight-lookahead} parameter set to 3 ({\it i.e.}, cost of postponing is the
average of the predicted flight costs 1, 2, and 3 minutes in the
future).  However, this parameter was changed to 2 by the end of the
finals in order to cause \attac\ to delay its flight commitments
further.

\subsubsection{Expected Benefit of Postponing Commitment}

Fundamentally, the benefit of postponing commitments to flights is
that additional information about the eventual hotel prices becomes
known.  Thus, the benefit of postponing commitment is computed by
sampling possible future price vectors and determining, on average,
how much better the agent could do if it bought a different flight
instead of the one in question.  If it is optimal to buy the flight in
all future scenarios, then there is no value in delaying the
commitment and the flight is purchased immediately.  However, if there
are many scenarios in which the flight is not the best one to get, the
purchase is more likely to be delayed.

The algorithm for determining the benefit of postponing commitment is
similar to that for determining the marginal value of hotel rooms. 
It is detailed, with explanation, in Table~\ref{tab:flight-vals}.

\begin{table}[htb]
\begin{center}
\hrule
\vspace{\hrulegap}
\begin{itemize}
\item Assume we're considering buying $n$ flights of a given type
\item Repeat until time bound
  \begin{s_enumerate}
  \item Generate a random hotel closing order (open hotels)
  \item \emph{Sample} closing prices from predicted price distributions (open hotels)
  \item Given these closing prices compute $V_0, V_1, \ldots V_n$ 
    \begin{s_itemize3}
    \item $V_i$ = \optallocval\ if forced to buy $i$ of the
      flight
    \item Estimate \optallocval\ with LP relaxation
    \item Assume more flights can be bought at the \emph{current price}
    \item Note that $V_0 \geq V_1 \geq \ldots \geq V_n$ since it is
      never worse to retain extra flexibility.
    \end{s_itemize3}
  \end{s_enumerate}
\item The value of waiting to buy copy $i$ is the mean of $V_i -
  V_{i-1}$ over all the samples.  If all price samples lead to the
  conclusion that the $i$th flight should be bought, then $V_i =
  V_{i-1}$ and there is no benefit to postponing commitment.
\end{itemize}
\vspace{\hrulegap}
\hrule
\end{center}
\caption{The algorithm for generating value of postponing flight commitments.}
\label{tab:flight-vals}
\end{table}

\subsection{Entertainment Expected Values} 

The core of \attac's entertainment-ticket-bidding strategy is again a
calculation of the expected marginal values of each ticket.  For each
ticket, \attac\ computes the expected value of having one more and one
fewer of the ticket.  These calculations give bounds on the bid and
ask prices it is willing to post.  The actual bid and ask prices are a
linear function of time remaining in the game: \attac\ settles for a
smaller and smaller profit from ticket transactions as the game goes
on.  Details of the functions of bid and ask price as a function of
game time and ticket value remained unchanged from
\attacold~\cite{JAIR-tac00}.

Details of the entertainment-ticket expected marginal utility
calculations are given in Table~\ref{tab:ent-vals}.

\begin{table}[htb]
\begin{center}
\hrule
\vspace{\hrulegap}
\begin{itemize}
\item Assume $n$ of a given ticket type are currently owned
\item Repeat until time bound
  \begin{s_enumerate}
  \item Generate a random hotel closing order (open hotels)
  \item \emph{Sample} closing prices from predicted price distributions (open hotels)
  \item Given these closing prices compute $V_{n-1}, V_n, V_{n+1}$ 
    \begin{s_itemize3}
    \item $V_i$ = \optallocval\ if own $i$ of the ticket
    \item Estimate \optallocval\ with LP relaxation
    \item Assume no other tickets can be bought or sold
    \item Note that $V_{n-1} \leq V_n \leq V_{n+1}$ since it is never
      worse to own extra tickets.
    \end{s_itemize3}
  \end{s_enumerate}

\item The value of buying a ticket is the mean of $V_{n+1} - V_{n}$
  over all the samples;  the value of selling is the mean of $V_{n} -
  V_{n-1}$.

\item Since tickets are considered sequentially, if the determined buy
or sell bid leads to a price that would clear according to the current
quotes, assume the transaction goes through before computing the
values of buying and selling other ticket types.
\end{itemize}
\vspace{\hrulegap}
\hrule
\end{center}
\caption{The algorithm for generating value of entertainment tickets.}
\label{tab:ent-vals}
\end{table}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Results}
\label{sec:results}

This section presents empirical results demonstrating the
effectiveness of the \attac\ strategy.  First, we summarize its
performance in the 2001 and 2002 Trading Agent Competitions (TACs).
These summaries provide evidence of the strategy's overall
effectiveness, but, due to the small number of games in the
competitions, are anecdotal rather than scientifically conclusive.  We
then present controlled experiments that provide more conclusive
evidence of the utility of our decision theoretic and learning
approaches embedded within \attac.

\subsection{TAC-01 Competition}

Of the 19 teams that entered the qualifying round, \attac\ was one of
eight agents to make it to the finals on the afternoon of October
14th, 2001.  The finals consisted of 24 games among the same eight
agents.  Right from the beginning, it became clear that
\agnt{livingagents}~\cite{Fritschi02} was the team to beat in the
finals.  They jumped to an early lead in the first two games, and by
eight games into the round, they were more than 135 points per game
ahead of their closest
competitor~\cite<\agnt{SouthamptonTAC,}>{Jennings02}.  16 games into
the round, they were more than 250 points ahead of their two closest
competitors (\attac\ and \agnt{whitebear}).

{From} that point, \attac, which was continually retraining its
price predictors based on recent games, began making a comeback.  By
the time the last game was to be played, it was only an average of 22
points per game behind \agnt{livingagents}.  It thus needed to beat
\agnt{livingagents} by 514 points in the final game to overtake it,
well within the margins observed in individual game instances.
As the game completed, \attac's score of 3979 was one of the
first scores to be posted by the server.  The other agents' scores
were reported one by one, until only the \agnt{livingagents} score was
left.  After agonizing seconds (at least for us), the TAC server
posted a final game score of 4626, resulting in a win for
\agnt{livingagents}.

After the competition, the TAC team at the University of Michigan
conducted a regression analysis of the effects of the client profiles
on agent scores.  Using data from the seeding rounds, it was
determined that agents did better when their clients had:
\begin{enumerate}
    \item  fewer total preferred travel days;
    \item  higher total entertainment values; and
    \item  a higher ratio of outer days (1 and 4) to inner (2 and 3) in preferred trip intervals.
\end{enumerate}
Based on these significant measures, the games in the finals could be
handicapped based on each agents' aggregate client profiles.  Doing so
indicated that \agnt{livingagents}' clients were much easier to
satisfy than those of 
\attac, giving \attac\ the highest handicapped score.  
The final scores, as well as the handicapped scores, are shown in
Table~\ref{tab:finals-scores}.  Complete results and affiliations are
available from \url{http://tac.eecs.umich.edu}.

\begin{table}[htb]
\begin{center}
\begin{tabular}{||l||c|c||}\hline
Agent & Mean & Handicapped score \\ \hline \hline
\attac  & 3622 & 4154  \\ \hline
\agnt{livingagents}  & 3670 & 4094 \\ \hline
\agnt{whitebear}   & 3513 & 3931  \\ \hline
\agnt{Urlaub01} & 3421 & 3909 \\  \hline
\agnt{Retsina}  & 3352 & 3812  \\ \hline
\agnt{CaiserSose}  & 3074 & 3766 \\ \hline
\agnt{SouthamptonTAC} & 3253 & 3679  \\ \hline
\agnt{TacsMan}  & 2859 & 3338  \\ \hline
\end{tabular}
\caption{Scores during the finals. Each agent played 24
  games.  Southampton's score was adversely affected by a game in
  which their agent crashed after buying many flights but no hotels, leading 
  to a loss of over 3000 points.
  Discarding that game results in an average score of 3531.}
\label{tab:finals-scores}
\end{center}
\end{table}

\subsection{TAC-02 Competition}

A year after the TAC-01 competition, \attac\ was re-entered in the
TAC-02 competition using the models trained at the end of TAC-01.
Specifically, the price predictors were left unchanged throughout (no
learning).  The seeding round included 19 agents, each playing 440
games over the course of about 2 weeks.  \attac\ was the top-scoring
agent in this round, as shown in Table~\ref{tab:seeding-scores}.
Scores in the seeding round were weighted so as to emphasize later
results over earlier results: scores on day $n$ of the seeding round
were given a weight of $n$.  This practice was designed to encourage
experimentation early in the round.  The official ranking in the
competitions was based on the mean score after ignoring each agent's
worst 10 results so as to allow for occasional program crashes and
network problems.


\begin{table}[htb]
\begin{center}
\begin{tabular}{||l||c|c||}\hline
Agent & Mean & Weighted, dropped worst 10 \\ \hline \hline
\attac  & 3050 & 3131  \\ \hline
\agnt{SouthamptonTAC}  & 3100 & 3129 \\ \hline
\agnt{UMBCTAC}   & 2980 & 3118  \\ \hline
\agnt{livingagents} & 3018 & 3091 \\  \hline
\agnt{cuhk}  & 2998 & 3055 \\ \hline
\agnt{Thalis} & 2952 & 3000  \\ \hline
\agnt{whitebear}  & 2945 & 2966  \\ \hline
\agnt{RoxyBot}  & 2738 & 2855  \\ \hline
\end{tabular}
\caption{Top 8 scores during the seeding round of TAC-02.  Each agent
  played 440 games, with its worst 10 games ignored when computing the
  rankings.}
\label{tab:seeding-scores}
\end{center}
\end{table}

On the one hand, it is striking that \attac\ was able to finish so
strongly in a field of agents that had presumably improved over the
course of the year.  On the other hand, most agents were being tuned,
for better and for worse, while \attac\ was consistent throughout.  In
particular, we are told that \agnt{SouthamptonTAC} experimented with
its approach during the later days of the round, perhaps causing it to
fall out of the lead (by weighted score) in the end.  During the
14-game semifinal heat, \attac, which was now restored with its
learning capability and retrained over the data from the 2002 seeding
round, finished 6th out of 8 thereby failing to reach the finals.

There are a number of possible reasons for this sudden failure.  One
relatively mundane explanation is that the agent had to change
computational environments between the seeding rounds and the finals,
and there may have been a bug or computational resource constraint
introduced.  Another possibility is that due to the small number of
games in the semifinals, \attac\ simply got unlucky with respect to
clients and the interaction of opponent strategies.  However, it is
also plausible that the training data from the 2002 qualifying and
seeding round data was less representative of the 2002 finals than the
was the training data from 2001; and/or that the competing agents
improved significantly over the seeding round while \attac\ remained
unchanged.  The TAC team at the University of Michigan has done a
study of the price predictors of several 2002 TAC agents that suggests
that the bug hypothesis is most plausible: the \attac\ predictor from
2001 outperforms all other predictors from 2002 on the data from the
2002 semifinals and finals; and one other agent that uses the 2002
data did produce good predictions based on that
data~\cite{Wellman03rlv}.\footnote{Indeed, in the TAC-03 competition,
ATTac-2001 was entered using the trained models from 2001, and it won
the competition, suggesting further that the failure in 2002 was due
to a problem with the learned models that were used during the finals
in 2002.}

\subsection{Controlled Experiments}
\label{sec:exper}

\attac's success in the TAC-01 competition demonstrates its
effectiveness as a complete system.  However, since the competing
agents differed along 
several dimensions, the competition results cannot isolate the
successful approaches.  In this section, we report controlled
experiments designed to test the efficacy of \attac's machine-learning
approach to price prediction.

\subsubsection{Varying the Predictor}


In the first set of experiments, we attempted to determine how the
quality of \attac's hotel price predictions affects its performance.
To this end, we devised seven price prediction schemes, varying
considerably in sophistication and inspired by approaches taken
by other TAC competitors, and incorporated these schemes into our
agent.  We then played these seven agents against one another
repeatedly, with regular retraining as described below.

Following are the seven hotel prediction schemes that we used, in
decreasing order of sophistication:
\begin{itemize}
\item
\atfulsamp:
This is the ``full-strength'' agent based on boosting that was used
during the tournament.  (The $s$ denotes sampling.)
\item
\atcondsamp:
This agent samples prices from the empirical distribution of prices
from previously played games, conditioned only on the closing time of the
hotel room (a subset of of the features used by \atfulsamp).
In other words, it collects all historical hotel prices and breaks them
down by the time at which the hotel closed (as well as room type, as
usual).
The price predictor then simply samples from the collection of prices
corresponding to the given closing time.
\item
\atsimpsamp:
This agent samples prices from the empirical distribution of prices
from previously played games, without regard to the closing time of the
hotel room (but still broken down by room type).  It uses a subset of
the features used by \atcondsamp.
\item 
\atfulnosamp, \atcondnosamp, \atsimpnosamp: These agents
predict in the same way
as their corresponding predictors above, but instead of returning a
random sample from the estimated distribution of hotel
prices, they deterministically return the expected value of the
distribution.  (The $ev$ denotes expected value, as introduced in
Section~\ref{sec:abstraction}.)
\item
\atcurbid:
This agent uses a very simple predictor that always predicts that the
hotel room will close at its current price.
\end{itemize}
In every case, whenever the price predictor returns a price that is
below the current price, we replace it with the current price (since
prices cannot go down).

In our experiments, we added as an eighth agent \livag, inspired by
the \agnt{livingagents} agent.  \livag\ used \atsimpnosamp\ to predict
closing prices, determined
an optimal set of purchases, and then placed bids for these goods at
sufficiently high prices to ensure that they would be purchased
(\$1001 for all hotel rooms, just as \agnt{livingagents} did in
TAC-01) right after the first flight quotes.  It then never revised
these bids.

Each of these agents require training, {\it i.e.}, data from previously
played games.  However, we are faced with a sort of ``chicken and
egg'' problem: to run the agents, we need to first train the agents
using data from games in which they were involved, but to get this kind of
data, we need to first run the agents.  To get around this problem, we
ran the agents in phases.  In Phase~I, which consisted of 126 games,
we used training data from the seeding, semifinals and finals rounds
of TAC-01.  In Phase~II, lasting 157 games, we retrained the agents
once every six hours using all of the data from the seeding,
semifinals and finals rounds as well as all of the games played in
Phase~II.  Finally, in Phase~III, lasting
622 games, we continued to retrain the agents once every six hours,
but now using only data from games played during Phases~I and~II, and
not including data from the seeding, semifinals and finals rounds.

%%%%%%%%%%%%%%%%%%%%%%%%%%%% table %%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\tabscore}[5]{{#1} & ${#2}\pm {#3}$ \\ \hline}
\newcommand{\shorttabscore}[9]{{#1} & ${#2}\pm {#3}$ & ${#6}\pm {#7}$
  & ${#8}\pm {#9}$ \\ \hline}

\begin{table}
{\small
\begin{center}
\begin{tabular}{|l|r|r|r|}
\hline
\multicolumn{1}{|c}{\em Agent} & \multicolumn{3}{|c|}{\em Relative Score} \\
\hline\hline
& \multicolumn{1}{|c|}{{\em Phase I}} & \multicolumn{1}{|c|}{{\em Phase II}} & \multicolumn{1}{|c|}{{\em Phase III}} \\
\hline
      \shorttabscore{\atfulnosamp }{    105.2}{   49.5\ \ (2)}{  9520.5}{  33.5}{    131.6}{   47.7\ \ (2)}{    166.2}{   20.8\ \ (1)}
      \shorttabscore{\atfulsamp   }{     27.8}{   42.1\ \ (3)}{  9623.8}{  35.9}{     86.1}{   44.7\ \ (3)}{    122.3}{   19.4\ \ (2)}
      \shorttabscore{\livag       }{    140.3}{   38.6\ \ (1)}{ 10039.6}{  84.6}{    152.8}{   43.4\ \ (1)}{    117.0}{   18.0\ \ (3)}
      \shorttabscore{\atsimpnosamp}{    -28.8}{   45.1\ \ (5)}{  9512.2}{  38.4}{    -53.9}{   40.1\ \ (5)}{    -11.5}{   21.7\ \ (4)}
      \shorttabscore{\atsimpsamp  }{    -72.0}{   47.5\ \ (7)}{  9611.9}{  42.1}{    -71.6}{   42.8\ \ (6)}{    -44.1}{   18.2\ \ (5)}
      \shorttabscore{\atshcdnosamp}{      8.6}{   41.2\ \ (4)}{  9526.3}{  33.9}{      3.5}{   37.5\ \ (4)}{    -60.1}{   19.7\ \ (6)}
      \shorttabscore{\atshcdsamp  }{   -147.5}{   35.6\ \ (8)}{  9660.1}{  34.6}{    -91.4}{   41.9\ \ (7)}{    -91.1}{   17.6\ \ (7)}
      \shorttabscore{\atcurbid    }{    -33.7}{   52.4\ \ (6)}{ 10281.0}{  32.2}{   -157.1}{   54.8\ \ (8)}{   -198.8}{   26.0\ \ (8)}
\end{tabular}
\end{center}
}
\caption{The average relative scores ($\pm$ standard deviation) for eight agents in
the three phases of our controlled experiment in which the hotel
prediction algorithm was varied.  The relative score of an agent is
its score minus the average score of all agents in that game.  The
agent's rank within each phase is shown in parentheses.}
\label{tab:exp1}
\end{table}


Table~\ref{tab:exp1} shows how the agents performed in 
{each} of these
phases.
Much of what we observe in this table is consistent with our
expectations.
The more sophisticated boosting-based agents (\atfulsamp\
and \atfulnosamp) clearly dominated the agents based on simpler
prediction schemes.
Moreover, with continued training, these agents improved markedly
relative to \livag.
We also see the performance of the simplest agent, \atcurbid, which
does not employ any kind of training, significantly decline relative
to the other data-driven agents.

On the other hand, there are some phenomena in this table that were
very surprising to us.  Most surprising was the failure of sampling to
help.  Our strategy relies heavily not only on estimating hotel
prices, but also taking samples from the distribution of hotel prices.
Yet these results indicate that using expected hotel price, rather
than price samples, consistently performs better.  We speculate that
this may be because an insufficient number of samples are being used
(due to computational limitations) so that the numbers derived from
these samples have too high a variance.  Another possibility is that
the method of using samples to estimate scores consistently
overestimates the expected score because it assumes the agent can
behave with perfect knowledge for each individual sample---a property
of our approximation scheme.  Finally, as our algorithm uses sampling
at several different points (computing hotel expected values, deciding
when to buy flights, pricing entertainment tickets, etc.), it is
quite possible that sampling is beneficial for some decisions while
detrimental for others.  
For example, when directly comparing versions of the algorithm with
sampling used at only subsets of the decision points, the data
suggests that sampling for the hotel decisions is most beneficial,
while sampling for the flights and entertainment tickets is neutral at
best, and possibly detrimental.  This result is not surprising given
that the sampling approach is motivated primarily by the task of
bidding for hotels.

We were also surprised that \atcondsamp\ and \atcondnosamp\ eventually
performed worse than the less sophisticated \atsimpsamp\ and
\atsimpnosamp.  One possible explanation is that the simpler model
happens to give predictions that are just as good as the more
complicated model, perhaps because closing time is not terribly
informative, or perhaps because the adjustment to price based on
current price is more significant.  Other things being equal, the
simpler model has the advantage that its statistics are based on all
of the price 
data, regardless of closing time, whereas the conditional model makes
each prediction based on only an eighth of the data (since there are
eight possible closing times, each equally likely).

In addition to agent performance, it is possible to measure the
inaccuracy of the eventual predictions, at least for the non-sampling
agents.
For these agents, we measured the root mean squared error of the
predictions made in Phase~III.  These were: 56.0 for \atfulnosamp,
66.6 for \atsimpnosamp, 69.8 for \atcurbid\ and 71.3 for
\atcondnosamp.  Thus, we see that the lower the error of the predictions
(according to this measure), the higher the score (correlation $R=-0.88$).

\subsubsection{\attac\ vs.\ \livag}

In a sense, the two agents that finished
at the top of the standings in TAC-01 represented opposite ends of a
spectrum.  The \agnt{livingagents} agent uses a 
simple open-loop strategy, committing to a set of desired goods right
at the beginning of the game, while \attac\ uses a closed-loop,
adaptive strategy.

The open-loop strategy relies on the other agents to stabilize the
economy and create consistent final prices.  In particular, if all
eight agents are open loop and  place very high bids for the goods
they want, many of the prices will 
skyrocket, evaporating any potential profit.  Thus, a set of open-loop
agents would
tend to get negative scores---the open-loop
strategy is a parasite, in a manner of speaking.
Table~\ref{tab:7livings} shows the
results of running 27 games with 7 copies of the open-loop
\livag\ and one of \attac.  Although motivated by \agnt{livingagents},
in actuality it is 
identical to \attac\ except that it uses \atsimpnosamp\ and it places
all of its flight and hotel bids immediately after the first flight
quotes.  It bids only for the hotels that appear in \optalloc\ at that
time.  All hotel bids are for \$1001.  In the experiments, one copy of
\atfulsamp\ is included for comparison.  The price predictors are all
from Phase~I in the preceding experiments.  \livag's high bidding
strategy backfires and it ends up overpaying significantly for its
goods.  As our experiments above indicate, \attac\ may improve even
further if it is allowed to train on the games of the on-going
experiment as well.


\begin{table}[htb]
{\small
\begin{center}
\begin{tabular}{||l||c|c||}\hline
Agent & Score & Utility \\ \hline
\attac\ & 2431 $\pm$ 464 & 8909 $\pm$ 264 \\
\livag(7) & $-4880$ $\pm$ 337 & 9870 $\pm$ 34 \\ \hline
\end{tabular}
\end{center}
}
\caption{The results of running \attac\ against 7 copies of 
  \livag\ over the course of 27 games.  \livag\ achieves high utility,
but overpays significantly, resulting in low scores.}
\label{tab:7livings}
\end{table}

The open-loop strategy has the advantage of buying a minimal set of
goods.  That is, it never buys more than it can use.  On the other
hand, it is susceptible to unexpected prices in that it can get stuck
paying arbitrarily high prices for the hotel rooms it has decided to
buy.

Notice in Table~\ref{tab:7livings} that the average utility of the
\livag's clients is significantly greater than that of \attac's
clients.  Thus, the difference in score is accounted for entirely by
the cost of the goods.  \livag\ ends up paying exorbitant prices,
while \attac\ generally steers clear of the more expensive hotels.
Its clients' utility suffers, but the cost-savings are well worth it.


Compared to the open-loop strategy, \attac's strategy is relatively
stable against itself.  Its main drawback is that as it changes its
decision about what goods it wants and as it may also buy goods to
hedge against possible price changes, it can end up getting stuck
paying for some goods that are ultimately useless to any of its
clients.

Table~\ref{tab:7attacs} shows the results of 7 copies of \attac\
playing against each other and one copy of the \livag.  Again,
training is from the seeding round and finals of TAC-01: the agents
don't adapt during the experiment.  Included in this experiment are
three variants of \attac, each with a different {\it flight-lookahead}
parameter (from the section on ``cost of postponing flight
commitments'').  There were three copies each of the agents with {\it
flight-lookahead} set to 2 and 3 (\attac(2) and \attac(3),
respectively), and one \attac\ agent with {\it flight-lookahead} set to
4 (\attac(4)).

\begin{table}[htb]
{\small
\begin{center}
\begin{tabular}{||l||c|c||}\hline
Agent & Score & Utility \\ \hline
\livag & 2869 $\pm$ 69 & 10079 $\pm$ 55 \\
\attac(2) & 2614 $\pm$ 38 & 9671 $\pm$ 32 \\
\attac(3) & 2570 $\pm$ 39 & 9641 $\pm$ 32 \\
\attac(4) & 2494 $\pm$ 68 & 9613 $\pm$ 55 \\ \hline
\end{tabular}
\end{center}
}
\caption{The results of running the \livag\ against 7
  copies of \attac\ over the course of 197 games.  The three different
  versions of \attac\ had slightly different {\it flight-lookahead}s.}
\label{tab:7attacs}
\end{table}

{From} the results in Table~\ref{tab:7attacs} it is clear that \attac\
does better when committing to its flight purchases later in the game
(\attac(2) as opposed to \attac(4)).  In comparison with
Table~\ref{tab:7livings}, the economy represented here does
significantly better overall.  That is, having many copies of \attac\
in the economy does not cause them to suffer.  However, in this
economy, \livag\ is able to invade.  It gets a significantly higher
utility for its clients and only pays slightly more than the \attac\
agents (as computed by utility minus score).\footnote{We suspect that
were the agents allowed to retrain over the course of the experiments,
\attac\ would end up improving, as we saw in Phase~III of the
previous set of experiments.  Were this to occur, it is possible that
\livag\ would no longer be able to invade.}

The results in this section suggest that the variance of the closing
prices is the largest determining factor between the effectiveness of
the two strategies (assuming nobody else is using the open-loop
strategy).
We speculate that with large price variances, the closed-loop strategy (\attac)
should do better, but with small price variances, the open-loop
strategy could do better.

\section{Discussion}
\label{sec:discussion}

The open-loop and closed-loop strategies of the previous section
differ in their handling of price fluctuation.  A fundamental way of
taking price fluctuation into account is to place ``safe bids.''  A
very high bid exposes an agent to the danger of buying something at a
ridiculously high price.  If prices are in fact stable then high bids
are safe.  But if prices fluctuate, then high bids, such as the bids
of the stable-price strategy, are risky.  In TAC, hotel rooms are sold
in a Vickrey-style $n$th price action.  There is a separate auction
for each day of each hotel and these auctions are done sequentially.
Although the order of the auctions is randomized, and not known to the
agent, when placing bids in one of these auctions the agent assumes
that auction will close next.  We assumed in the design of our
agent that our bids in one auction do not affect prices in other
auctions.  This assumption is not strictly true, but in a large
economy one expects that the bids of a single individual have a
limited effect on prices.  Furthermore, the price most affected by a
bid is the price of the item being bid on; the effect on other
auctions seems less direct and perhaps more limited.  Assuming bids in
one auction do not affect prices in another, the optimal bidding
strategy is the standard strategy for a Vickrey auction---the bid for
an item should be equal to its utility to the bidder.
So, to place a Vickrey-optimal bid, one must be able to estimate the
utility of an item.  The utility of owning an item is simply the
expected final score assuming one owns the item minus the expected
final score assuming one does not own the item.  So, the problem of
computing a Vickrey-optimal bid can be reduced to the problem of
predicting final scores for two alternative game situations.  We use
two score prediction procedures, which we call the stable-price score
predictor (corresponding to Equation~\ref{e:aucapprox2}) and the
unstable-price score predictor (Equation~\ref{e:aucapprox}).

{\bf The Stable-Price Score Predictor.} The stable-price score
predictor first estimates the expected prices in the rest of the game
using whatever information is available in the given game situation.
It then computes the value achieved by optimal purchases under the
estimated prices.  In an economy with stable prices, this estimate will
be quite accurate---if we make the optimal purchases for the
expected price then, if the prices are near our estimates, our
performance will also be near the estimated value.  

{\bf The Unstable-Price Score Predictor.}  Stable-price score
prediction does not take into account the ability of the agent to
react to changes in price as the game progresses.  Suppose a given
room is often cheap but is sometimes expensive.  If the agent can
first determine the price of the room, and then plan for that price,
the agent will do better than guessing the price ahead of time and
sticking to the purchases dictated by that price.  The unstable price
predictor uses a model of the {\em distribution} of possible prices.
It repeatedly samples prices from this distribution, computes the
stable-price score prediction under the sampled price, and then takes
the average of these stable-price scores over the various price
samples.  This score prediction algorithm is similar to the algorithm
used in Ginsberg's~\citeyear{Ginsberg01} quite successful computer
bridge program where the score is predicted by sampling the possible
hands of the opponent and, for each sample, computing the score of
optimal play in the case where all players have complete information
(double dummy play).  While this approach has a simple intuitive
motivation, it is clearly imperfect.  The unstable-price score
predictor assumes both that future decisions are made in the presence
of complete price information, and that the agent is free to change
existing bids in auctions that have not yet closed.  Both of these
assumptions are only approximately true at best.  Ways of compensating
for the imperfections in score prediction were described in
Section~\ref{sec:attac}.

{\bf Buy Now or Decide Later.}  The trading agent must decide what
airline tickets to buy and when to buy them.  In deciding whether to
buy an airline ticket, the agent can compare the predicted score in
the situation where it owns the airline ticket with the predicted
score in the situation where it does not own the airline ticket but
may buy it later.  Airline tickets tend to increase in price, so if
the agent knows that a certain ticket is needed it should buy it as
soon as possible.  But whether or not a given ticket is desirable may
depend on the price of hotel rooms, which may become clearer as the
game progresses.  If airline tickets did not increase in price, as was
the case in TAC-00, then they should be bought at the last possible
moment~\cite{JAIR-tac00}.  To determine whether an airline ticket
should be bought now or not, one can compare the predicted score in
the situation where one has just bought the ticket at its current
price with the predicted score in the situation where the price of the
ticket is somewhat higher but has not yet been bought.  It is
interesting to note that if one uses the stable-price score predictor
for both of these predictions, and the ticket is purchased in the
optimal allocation under the current price estimate, then the
predicted score for buying the ticket now will always be
higher---increasing the price of the ticket can only reduce the score.
However, the unstable-price score predictor can yield an advantage for
delaying the purchase.  This advantage comes from the fact that buying
the ticket may be optimal under some prices but not optimal under
others.  If the ticket has not yet been bought, then the score will be
higher for those sampled prices where the ticket should not be bought.
This corresponds to the intuition that in certain cases the purchase
should be delayed until more information is available.


Our guiding principle in the design of the agent was,
to the greatest extent possible, to have the agent analytically
calculate optimal actions.  A key component of these calculations is
the score predictor, based either on a single estimated assignment of
prices or on a model of the probability distribution over assignments
of prices.  Both score predictors, though clearly imperfect, seem
useful. Of these two predictors, only the unstable-price predictor can
be used to quantitatively estimate the value of postponing a decision
until more information is available.  The accuracy of price estimation
is clearly of central importance.  Future research will undoubtedly
focus on ways of improving both price modeling and score prediction
based on price modeling.


\section{Related and Future Work}
\label{sec:conc}

Although there has been a good deal of research on auction theory,
especially from the perspective of auction
mechanisms~\cite{Klemperer99}, 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~\cite{fishmarket00}.  Automatic bidding agents
have also been created in this domain~\cite{fishmarket-designing98}.
There have been a number of studies of agents bidding for a single
good in multiple auctions~\cite{ito00,jennings01,preist00}.  

A notable auction-based competition that was held prior to TAC was the
Santa Fe Double Auction Tournament~\cite{Rust92}.  This auction
involved several agents competing in a single continuous double
auction similar to the TAC entertainment ticket auctions.  As analyzed
by \namecite{TesauroDas01}, this tournament was won by a parasite
strategy that, like \agnt{livingagents} as described in
Section~\ref{sec:exper}, 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 \emph{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:
\begin{enumerate}
\item In TAC-00, flight prices did not tend to increase;
\item In TAC-00, hotel auctions usually all closed at the end of the
game;
\item In TAC-00, entertainment tickets were distributed uniformly to
  all agents
\end{enumerate}
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~\cite{TAC00-full}.  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~\ref{sec:alloc}.

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~\ref{sec:exper}, 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~\cite{IAAI02}, associated in some cases
with the price-predictor variant in our experiments that was motivated
by it.
\begin{enumerate}
     \item  Just use the current price quote $p_t$ (\atcurbid).
     \item  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$.
     \item Predict by fitting a curve to the sequence of ask prices
     seen in the current game.
      \item  Predict based on closing price data for that hotel in past
games (\atsimpnosamp, \atsimpsamp).  
      \item  Same as above, but condition on hotel closing time,
      recognizing that the closing sequence will influence the relative
      prices.
      \item Same as above, but condition on full ordering of hotel
      closings, or which hotels are open or closed at a particular
      point (\atcondnosamp, \atcondsamp).
      \item  Learn a mapping from features of the current game
      (including current prices) to closing prices based on historic data 
      (\atfulsamp, \atfulnosamp).
      \item  Hand-construct rules based on observations about
      associations between abstract features.
\end{enumerate}

Having demonstrated \attac'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~\cite{Weber96}.  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 \emph{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~\cite{FCC01}, we discovered a novel,
successful bidding strategy in this domain that allows the bidders to
increase their profits significantly over a reasonable default
strategy~\cite{AMEC02-rsdr}.

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.


\acks{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.}

\bibliographystyle{theapa}
\input{../../bibstring}
\end{document}


\begin{thebibliography}{}

\bibitem[\protect\BCAY{Anthony, Hall, Dang, \BBA\ Jennings}{Anthony
  et~al.}{2001}]{jennings01}
Anthony, P., Hall, W., Dang, V.~D., \BBA\ Jennings, N.~R. \BBOP2001\BBCP.
\newblock \BBOQ Autonomous agents for participating in multiple on-line
  auctions\BBCQ\
\newblock In {\Bem Proceedings of the {IJCAI}-2001 Workshop on E-Business and
  the Intelligent Web}\ Seattle, WA.

\bibitem[\protect\BCAY{Boutilier}{Boutilier}{2002}]{boutilier02}
Boutilier, C. \BBOP2002\BBCP.
\newblock \BBOQ A pomdp formulation of preference elicitation problems\BBCQ\
\newblock In {\Bem Proceedings of the Eighteenth National Conference on
  Artificial Intelligence}, \BPGS\ 239--246.

\bibitem[\protect\BCAY{Collins, Schapire, \BBA\ Singer}{Collins
  et~al.}{2002}]{CollinsScSi02}
Collins, M., Schapire, R.~E., \BBA\ Singer, Y. \BBOP2002\BBCP.
\newblock \BBOQ Logistic regression, {AdaBoost} and {Bregman} distances\BBCQ\
\newblock {\Bem Machine Learning}, {\Bem 48\/}(1/2/3).

\bibitem[\protect\BCAY{Csirik, Littman, Singh, \BBA\ Stone}{Csirik
  et~al.}{2001}]{FCC01}
Csirik, J.~A., Littman, M.~L., Singh, S., \BBA\ Stone, P. \BBOP2001\BBCP.
\newblock \BBOQ {FAucS}: An {FCC} spectrum auction simulator for autonomous
  bidding agents\BBCQ\
\newblock In Fiege, L., M\"{u}hl, G., \BBA\ Wilhelm, U.\BEDS, {\Bem Electronic
  Commerce: Proceedings of the Second International Workshop}, \BPGS\ 139--151\
  Heidelberg, Germany. Springer Verlag.

\bibitem[\protect\BCAY{Freund \BBA\ Schapire}{Freund \BBA\
  Schapire}{1997}]{FreundSc97}
Freund, Y.\BBACOMMA\  \BBA\ Schapire, R.~E. \BBOP1997\BBCP.
\newblock \BBOQ A decision-theoretic generalization of on-line learning and an
  application to boosting\BBCQ\
\newblock {\Bem Journal of Computer and System Sciences}, {\Bem 55\/}(1),
  119--139.

\bibitem[\protect\BCAY{Fritschi \BBA\ Dorer}{Fritschi \BBA\
  Dorer}{2002}]{Fritschi02}
Fritschi, C.\BBACOMMA\  \BBA\ Dorer, K. \BBOP2002\BBCP.
\newblock \BBOQ Agent-oriented software engineering for successful {TAC}
  participation\BBCQ\
\newblock In {\Bem First International Joint Conference on Autonomous Agents
  and Multi-Agent Systems}\ Bologna.

\bibitem[\protect\BCAY{Garey \BBA\ Johnson}{Garey \BBA\
  Johnson}{1979}]{garey79}
Garey, M.~R.\BBACOMMA\  \BBA\ Johnson, D.~S. \BBOP1979\BBCP.
\newblock {\Bem Computers and Intractability: {A} Guide to the Theory of
  {NP}-completeness}.
\newblock Freeman, San Francisco, CA.

\bibitem[\protect\BCAY{Gimenez-Funes, Godo, Rodriguez-Aguiolar, \BBA\
  Garcia-Calves}{Gimenez-Funes et~al.}{1998}]{fishmarket-designing98}
Gimenez-Funes, E., Godo, L., Rodriguez-Aguiolar, J.~A., \BBA\ Garcia-Calves, P.
  \BBOP1998\BBCP.
\newblock \BBOQ Designing bidding strategies for trading agents in electronic
  auctions\BBCQ\
\newblock In {\Bem Proceedings of the Third International Conference on
  Multi-Agent Systems}, \BPGS\ 136--143.

\bibitem[\protect\BCAY{Ginsberg}{Ginsberg}{2001}]{Ginsberg01}
Ginsberg, M.~L. \BBOP2001\BBCP.
\newblock \BBOQ {GIB}: Imperfect information in a computationally challenging
  game\BBCQ\
\newblock {\Bem JAIR}, {\Bem 14}, 303--358.

\bibitem[\protect\BCAY{Greenwald \BBA\ Boyan}{Greenwald \BBA\
  Boyan}{2001}]{boyan01}
Greenwald, A.\BBACOMMA\  \BBA\ Boyan, J. \BBOP2001\BBCP.
\newblock \BBOQ Bidding algorithms for simultaneous auctions\BBCQ\
\newblock In {\Bem Proceedings of Third ACM Conference on E-Commerce}, \BPGS\
  115--124\ Tampa, FL.

\bibitem[\protect\BCAY{Harsanyi}{Harsanyi}{1968}]{harsanyi68}
Harsanyi, J. \BBOP1967--1968\BBCP.
\newblock \BBOQ Games with incomplete information played by bayesian
  players\BBCQ\
\newblock {\Bem Management Science}, {\Bem 14}, 159--182,320--334,486--502.

\bibitem[\protect\BCAY{Hauskrecht}{Hauskrecht}{1997}]{hauskrecht97}
Hauskrecht, M. \BBOP1997\BBCP.
\newblock \BBOQ Incremental methods for computing bounds in partially
  observable {M}arkov decision processes\BBCQ\
\newblock In {\Bem Proceedings of the Fourteenth National Conference on
  Artificial Intelligence}, \BPGS\ 734--739.

\bibitem[\protect\BCAY{He \BBA\ Jennings}{He \BBA\ Jennings}{2002}]{Jennings02}
He, M.\BBACOMMA\  \BBA\ Jennings, N.~R. \BBOP2002\BBCP.
\newblock \BBOQ Southampton{TAC}: Designing a successful trading agent\BBCQ\
\newblock In {\Bem Fifteenth European Conference on Artificial Intelligence}\
  Lyon, France.

\bibitem[\protect\BCAY{Ito, Fukuta, Shintani, \BBA\ Sycara}{Ito
  et~al.}{2000}]{ito00}
Ito, T., Fukuta, N., Shintani, T., \BBA\ Sycara, K. \BBOP2000\BBCP.
\newblock \BBOQ Biddingbot: a multiagent support system for cooperative bidding
  in multiple auctions\BBCQ\
\newblock In {\Bem Proceedings of the Fourth International Conference on
  MultiAgent Systems}, \BPGS\ 399--400.

\bibitem[\protect\BCAY{Kearns, Mansour, \BBA\ Ng}{Kearns
  et~al.}{1999}]{kearns99b}
Kearns, M., Mansour, Y., \BBA\ Ng, A.~Y. \BBOP1999\BBCP.
\newblock \BBOQ A sparse sampling algorithm for near-optimal planning in large
  {M}arkov decision processes\BBCQ\
\newblock In {\Bem Proceedings of the Sixteenth International Joint Conference
  on Artificial Intelligence (IJCAI-99)}, \BPGS\ 1324--1331.

\bibitem[\protect\BCAY{Klemperer}{Klemperer}{1999}]{Klemperer99}
Klemperer, P. \BBOP1999\BBCP.
\newblock \BBOQ Auction theory: A guide to the literature\BBCQ\
\newblock {\Bem Journal of Economic Surveys}, {\Bem 13\/}(3), 227--86.

\bibitem[\protect\BCAY{Littman, Majercik, \BBA\ Pitassi}{Littman
  et~al.}{2001}]{littman00}
Littman, M.~L., Majercik, S.~M., \BBA\ Pitassi, T. \BBOP2001\BBCP.
\newblock \BBOQ Stochastic {B}oolean satisfiability\BBCQ\
\newblock {\Bem Journal of Automated Reasoning}, {\Bem 27\/}(3), 251--296.

\bibitem[\protect\BCAY{Papadimitriou \BBA\ Tsitsiklis}{Papadimitriou \BBA\
  Tsitsiklis}{1987}]{papadimitriou87}
Papadimitriou, C.~H.\BBACOMMA\  \BBA\ Tsitsiklis, J.~N. \BBOP1987\BBCP.
\newblock \BBOQ The complexity of {M}arkov decision processes\BBCQ\
\newblock {\Bem Mathematics of Operations Research}, {\Bem 12\/}(3), 441--450.

\bibitem[\protect\BCAY{Preist, Bartolini, \BBA\ Phillips}{Preist
  et~al.}{2001}]{preist00}
Preist, C., Bartolini, C., \BBA\ Phillips, I. \BBOP2001\BBCP.
\newblock \BBOQ Algorithm design for agents which participate in multiple
  simultaneous auctions\BBCQ\
\newblock In {\Bem Agent Mediated Electronic Commerce {III} (LNAI)}, \BPGS\
  139--154. Springer-Verlag, Berlin.

\bibitem[\protect\BCAY{Reitsma, Stone, Csirik, \BBA\ Littman}{Reitsma
  et~al.}{2002}]{AMEC02-rsdr}
Reitsma, P. S.~A., Stone, P., Csirik, J.~A., \BBA\ Littman, M.~L.
  \BBOP2002\BBCP.
\newblock \BBOQ Self-enforcing strategic demand reduction\BBCQ\
\newblock In {\Bem Agent Mediated Electronic Commerce {IV}: Designing
  Mechanisms and Systems}, \lowercase{\BVOL}\ 2531 of {\Bem Lecture Notes in
  Artificial Intelligence}, \BPGS\ 289--306. Springer Verlag.

\bibitem[\protect\BCAY{Rodriguez-Aguilar, Martin, Noriega, Garcia, \BBA\
  Sierra}{Rodriguez-Aguilar et~al.}{1998}]{fishmarket00}
Rodriguez-Aguilar, J.~A., Martin, F.~J., Noriega, P., Garcia, P., \BBA\ Sierra,
  C. \BBOP1998\BBCP.
\newblock \BBOQ Towards a test-bed for trading agents in electronic auction
  markets\BBCQ\
\newblock {\Bem AI Communications}, {\Bem 11\/}(1), 5--19.

\bibitem[\protect\BCAY{Rothkopf \BBA\ Harstad}{Rothkopf \BBA\
  Harstad}{1994}]{rothkopf94}
Rothkopf, M.~H.\BBACOMMA\  \BBA\ Harstad, R.~M. \BBOP1994\BBCP.
\newblock \BBOQ Modeling competitive bidding: A critical essay\BBCQ\
\newblock {\Bem Management Science}, {\Bem 40\/}(3), 364--384.

\bibitem[\protect\BCAY{Rust, Miller, \BBA\ Palmer}{Rust et~al.}{1992}]{Rust92}
Rust, J., Miller, J., \BBA\ Palmer, R. \BBOP1992\BBCP.
\newblock \BBOQ Behavior of trading automata in a computerized double auction
  market\BBCQ\
\newblock In Friedman, D.\BBACOMMA\  \BBA\ Rust, J.\BEDS, {\Bem The Double
  Auction Market: Institutions, Theories, and Evidence}. Addison-Wesley,
  Redwood City, CA.

\bibitem[\protect\BCAY{Schapire \BBA\ Singer}{Schapire \BBA\
  Singer}{1999}]{SchapireSi99}
Schapire, R.~E.\BBACOMMA\  \BBA\ Singer, Y. \BBOP1999\BBCP.
\newblock \BBOQ Improved boosting algorithms using confidence-rated
  predictions\BBCQ\
\newblock {\Bem Machine Learning}, {\Bem 37\/}(3), 297--336.

\bibitem[\protect\BCAY{Schapire \BBA\ Singer}{Schapire \BBA\
  Singer}{2000}]{SchapireSi00}
Schapire, R.~E.\BBACOMMA\  \BBA\ Singer, Y. \BBOP2000\BBCP.
\newblock \BBOQ {BoosTexter}: A boosting-based system for text
  categorization\BBCQ\
\newblock {\Bem Machine Learning}, {\Bem 39\/}(2/3), 135--168.

\bibitem[\protect\BCAY{Stone}{Stone}{1994}]{Stone94}
Stone, C.~J. \BBOP1994\BBCP.
\newblock \BBOQ The use of polynomial splines and their tensor products in
  multivariate function estimation\BBCQ\
\newblock {\Bem The Annals of Statistics}, {\Bem 22\/}(1), 118--184.

\bibitem[\protect\BCAY{Stone \BBA\ Greenwald}{Stone \BBA\
  Greenwald}{2003}]{TAC00-full}
Stone, P.\BBACOMMA\  \BBA\ Greenwald, A. \BBOP2003\BBCP.
\newblock \BBOQ The first international trading agent competition: Autonomous
  bidding agents\BBCQ\
\newblock {\Bem Electronic Commerce Research}.
\newblock To appear.

\bibitem[\protect\BCAY{Stone, Littman, Singh, \BBA\ Kearns}{Stone
  et~al.}{2001}]{JAIR-tac00}
Stone, P., Littman, M.~L., Singh, S., \BBA\ Kearns, M. \BBOP2001\BBCP.
\newblock \BBOQ {ATT}ac-2000: An adaptive autonomous bidding agent\BBCQ\
\newblock {\Bem Journal of Artificial Intelligence Research}, {\Bem 15},
  189--206.

\bibitem[\protect\BCAY{Tesauro \BBA\ Das}{Tesauro \BBA\
  Das}{2001}]{TesauroDas01}
Tesauro, G.\BBACOMMA\  \BBA\ Das, R. \BBOP2001\BBCP.
\newblock \BBOQ High-performance bidding agents for the continuous double
  auction\BBCQ\
\newblock In {\Bem Third ACM Conference on Electronic Commerce}, \BPGS\
  206--209.

\bibitem[\protect\BCAY{Weber}{Weber}{1997}]{Weber96}
Weber, R.~J. \BBOP1997\BBCP.
\newblock \BBOQ Making more from less: Strategic demand reduction in the {FCC}
  spectrum auctions\BBCQ\
\newblock {\Bem Journal of Economics and Management Strategy}, {\Bem 6\/}(3),
  529--548.

\bibitem[\protect\BCAY{Wellman, Greenwald, Stone, \BBA\ Wurman}{Wellman
  et~al.}{2002}]{IAAI02}
Wellman, M.~P., Greenwald, A., Stone, P., \BBA\ Wurman, P.~R. \BBOP2002\BBCP.
\newblock \BBOQ The 2001 trading agent competition\BBCQ\
\newblock In {\Bem Proceedings of the Fourteenth Innovative Applications of
  Artificial Intelligence Conference}, \BPGS\ 935--941.

\bibitem[\protect\BCAY{Wellman, Greenwald, Stone, \BBA\ Wurman}{Wellman
  et~al.}{2003a}]{EM02}
Wellman, M.~P., Greenwald, A., Stone, P., \BBA\ Wurman, P.~R. \BBOP2003a\BBCP.
\newblock \BBOQ The 2001 trading agent competition\BBCQ\
\newblock {\Bem Electronic Markets}, {\Bem 13\/}(1), 4--12.

\bibitem[\protect\BCAY{Wellman, Reeves, Lochner, \BBA\ Vorobeychik}{Wellman
  et~al.}{2003b}]{Wellman03rlv}
Wellman, M.~P., Reeves, D.~M., Lochner, K.~M., \BBA\ Vorobeychik, Y.
  \BBOP2003b\BBCP.
\newblock \BBOQ Price prediction in a trading agent competition\BBCQ\
\newblock \BTR, University of Michigan.

\bibitem[\protect\BCAY{Wellman, Wurman, O'Malley, Bangera, Lin, Reeves, \BBA\
  Walsh}{Wellman et~al.}{2001}]{WellmanTAC00}
Wellman, M.~P., Wurman, P.~R., O'Malley, K., Bangera, R., Lin, S.-d., Reeves,
  D., \BBA\ Walsh, W.~E. \BBOP2001\BBCP.
\newblock \BBOQ A trading agent competition\BBCQ\
\newblock {\Bem IEEE Internet Computing}, {\Bem 5\/}(2), 43--51.

\end{thebibliography}
