Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Continuous Value Function Approximation for Sequential Bidding Policies
Craig Boutilier, Moises Goldszmidt, Bikash Sabata
Abstract:
Market-based mechanisms such as auctions are being studied as an appropriate means for resource allocation in distributed and mulitagent 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 {em grid-based} approximation 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.
Keywords:
Pages: 81-90
PS Link:
PDF Link: /papers/99/p81-boutilier.pdf
BibTex:
@INPROCEEDINGS{Boutilier99,
AUTHOR = "Craig Boutilier and Moises Goldszmidt and Bikash Sabata",
TITLE = "Continuous Value Function Approximation for Sequential Bidding Policies",
BOOKTITLE = "Proceedings of the Fifteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-99)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1999",
PAGES = "81--90"
}


hosted by DSL   •   site info   •   help