Bidding under Uncertainty: Theory and Experiments
Amy Greenwald and Justin Boyan
Abstract
This paper describes a study of agent bidding strategies, assuming
combinatorial valuations for complementary and substitutable goods, in
three auction environments: sequential auctions, simultaneous
auctions, and the Trading Agent Competition (TAC) Classic hotel
auction design, a hybrid of sequential and simultaneous auctions. The
problem of bidding in sequential auctions is formulated as an MDP, and
it is argued that expected marginal utility bidding is the optimal
bidding policy. The problem of bidding in simultaneous auctions is
formulated as a stochastic program, and it is shown by example that
marginal utility bidding is not an optimal bidding policy, even in
deterministic settings. Two alternative methods of approximating a
solution to this stochastic program are presented: the first method,
which relies on expected values, is optimal in deterministic
environments; the second method, which samples the nondeterministic
environment, is asymptotically optimal as the number of samples tends
to infinity. Finally, experiments with these various bidding policies
are described in the TAC Classic setting.