Resource Allocation Among Agents with MDP-Induced Preferences

Dmitri A. Dolgov, and Edmund H. Durfee

In Journal of Artificial Intelligence Research (JAIR-06), 27. Pages 505--549. December 2006.

Copyright © 2006 AI Access Foundation. Publisher's version is available at JAIR.

Abstract
Allocating scarce resources among agents to maximize global utility is, in general, computationally challenging. We focus on problems where resources enable agents to execute actions in stochastic environments, modeled as Markov decision processes (MDPs), such that the value of a resource bundle is defined as the expected value of the optimal MDP policy realizable given these resources. We present an algorithm that simultaneously solves the resource-allocation and the policy-optimization problems. This allows us to avoid explicitly representing utilities over exponentially many resource bundles, leading to drastic (often exponential) reductions in computational complexity. We then use this algorithm in the context of self-interested agents to design a combinatorial auction for allocating resources. We empirically demonstrate the effectiveness of our approach by showing that it can, in minutes, optimally solve problems for which a straightforward combinatorial resource-allocation technique would require the agents to enumerate up to $2^{100}$ resource bundles and the auctioneer to solve an NP-complete problem with an input of that size.


BibTex
@article{ dolgov06resourceMDP,
   paperID   = "JAIR-06",
   volume    = "27",
   month     = "December",
   author    = "Dmitri A. Dolgov and Edmund H. Durfee",
   title     = "Resource Allocation Among Agents with MDP-Induced Preferences",
   pages     = "505--549",
   year      = "2006",
   journal   = "Journal of Artificial Intelligence Research (JAIR-06)"
}


Download:
pdf [pdf]        ps [ps.gz]