Craig Boutilier
Department of Computer Science
University of British Columbia
Vancouver, BC, CANADA, V6T 1Z4
email: cebly@cs.ubc.ca
Moises Goldszmidt and Bikash Sabata
SRI International
333 Ravenswood Avenue
Menlo Park, CA 94025, USA
email: {moises,sabata}@erg.sri.com
Abstract
Market-based mechanisms such as auctions are being studied as an
appropriate means for resource allocation in distributed and
multiagent decision problems. When agents value resources in
combination rather than in isolation, they must often deliberate about
appropriate bidding strategies for a sequence of auctions offering
resources of interest. We briefly describe a discrete dynamic
programming model for constructing appropriate bidding policies for
resources exhibiting both complementarities and substitutability. We
then introduce a continuous approximation of this model, assuming that
money (or the numeraire good) is infinitely divisible. Though this has
the potential to reduce the computational cost of computing policies,
value functions in the transformed problem do not have a
convenient closed
form representation. We develop grid-based approximations for
such value functions, representing value functions using piecewise
linear approximations. We show that these methods can offer
significant computational savings with relatively small cost in
solution quality.
To appear, UAI-99
Return to List of Papers