Information Technology Reference
In-Depth Information
preferences, find an optimal set of bids (and asks). It is natural to formulate this problem
as a two-stage stochastic program: in the first stage an agent makes its bidding deci-
sions; in the second stage, when the agent is informed of its winnings, it allocates those
winnings to its clients. This second stage problem, TAC Travel allocation—find the
utility-maximizing set of packages that an agent can assemble from its winnings, given
its clients preferences—is equivalent to the (NP-hard) winner determination problem in
combinatorial auctions (see Appendix B.)
A TAC Travel Stochastic Pricing Model.
The bidding problem takes as input a stochas-
tic model of clearing prices. Our stochastic pricing model is inspired by the
expected
competitive equilibrium pricing model developed for Michigan's TAC Travel Agent,
Walverine
[7]. To compute the
expected
competitive equilibrium price of a good,
the tatonnement process is run once making use of the expected market wide demand,
which is calculated based on the expected values of the opposing agents' clients' pref-
erences. In a
stochastic
modeler, rather than run the tatonnement process only once
using expected market wide demand, the process is run multiple times, each time draw-
ing a random selection of the opposing agents' clients' preferences from the probabil-
ity distributions given in the game's specification. We ran this procedure 2000 times
to generate 2000 scenarios, which comprise our model of stochasticity in our experi-
ments.
3.2
Stochastic Scheduling Problem
We solve a stochastic scheduling problem inspired by the Trading Agent Competition
in Supply Chain Management. The problem is to schedule production of computers at a
factory with limited capacity when demand for different types of computers is stochas-
tic. There are 16 computer types that can be produced. The computers are produced to
meet customer demand, which comes in the form of possible orders. A possible order
is specified by a probability, price, computer type, and quantity. The probability indi-
cates how likely it is that a possible order will become a real order. Real orders can be
satisfied by delivering the quantity of the computer type requested. Revenue is earned
by satisfying real orders. The objective is to distribute the available production capacity
among computer types in a way that maximizes expected revenue.
We express the problem as a two-stage stochastic program. In the first stage, the
agent makes its production decisions. In the second stage, the agent is told which
of the possible orders become real orders, and chooses the profit maximizing subset
of real orders to deliver using the computers produced in the first stage. The second
stage problem, which we call delivery scheduling, is a 0-1 knapsack problem (see Ap-
pendix C).
A problem instance is a set of 40 possible orders. The possible orders are generated
based on uniform distributions of probabilities, computer types, and quantities. A pos-
sible order's price is inversely related to the probability of it becoming a real order. To
make the problem interesting, we generate a range of quantities such that the expected
demand is twice the production capacity.
