Information Technology Reference
In-Depth Information
for optimal settings of the parameters of the SAA algorithm, given the time and space
constraints of an application. Based on our observations, we formulated a quick test to
determine whether maximizing
S
and then
P
, given the constraints of an application is
sufficient—namely, do time and space usage grow only linearly with
S
?Often,how-
ever, we expect time and space usage to grow exponentially with
S
, in which case it is
necessary to search the space of parameter settings to optimize the tradeoffs between
increasing
S
or
P
. The stochastic bidding and scheduling problems studied in this pa-
per were inspired by the Trading Agent Competition. In both TAC Travel and TAC
SCM, our agent's architecture [3, 8] is comprised of two main modules: a “modeler”
and a “decider.” Our modelers build stochastic models of their environments, which
necessitates that our deciders solve stochastic optimization problems. In other words,
decision-making under uncertainty, particularly the two problems defined and analyzed
in this paper, is fundamental to our agents' designs. Generalizing from our experience
in TAC Travel and TAC SCM, we expect that related stochastic optimization problems
are fundamental to the design of trading agents for domains outside the scope of the
Trading Agent Competition.
A
Stochastic Programming Formulations
A.1
TAC Travel Bidding Problem
Index Sets
a
∈
A
indexes the set of auctions.
c
∈
C
indexes the set of clients.
p
∈
P
indexes the set of bid prices.
q
∈
Q
a
indexes the set of goods in auction
a
.
s
∈
S
indexes the set of scenarios.
t
∈
T
indexes the set of packages.
Constants
G
at
is an integer constant indicating how many goods from auction
a
are
contained in a package
t
.
B
aqs
is an integer constant indicating the closing buy price
of the
q
th good of auction
a
in scenario
s
.
Z
aqs
is an integer constant indicating the
closing sell price of the
q
th good of auction
a
in scenario
s
.
U
ct
is an integer constant
indicating the utility gained for client
c
having package
t
.
Decision Variables
B
=
is a set of boolean variables indicating whether to
bid price
p
for the
q
th good in auction
a
.
Z
=
{
β
apq
}
is a set of boolean variables
indicating whether to ask price
p
for the
q
th good in auction
a
.
Γ
=
{
ζ
apq
}
{
γ
cst
}
is a set of
boolean variables indicating whether client
c
gets package
t
in scenario
s
.
Objective Function
⎛
utility
cost
⎛
⎝
⎞
⎛
⎞
⎝
A,Q
a
,p>B
aqs
B
aqs
β
aqp
⎠
−
⎝
⎠
+
max
B,Z,Γ
Pr(
s
)
C,T
U
ct
γ
cst
S
