Continuous Value Function Approximation for Sequential Bidding Policies
This work addresses resource allocation in multiagent systems, offering an incremental improvement in computational efficiency for sequential bidding strategies.
The paper tackles the problem of computing bidding policies for sequences of auctions with complementary and substitutable resources by introducing a continuous approximation of a discrete dynamic programming model, which reduces computational cost with minimal loss in solution quality.
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.