Resource Allocation with MDP-Induced Preferences

The problem of resource allocation is to effectively distribute a set of scarce resources among multiple agents, where an optimal allocation is commonly defined as one that maximizes the sum of agents' utilities. A number of resource-allocation mechanisms exist that have very attractive analytical properties, but they often suffer from high computational complexity when the agents' preferences for resources are not additive (finding an optimal allocation is NP-complete with input exponential in the number of resources).

In this talk I will discuss the problem of resource allocation where an agent's utility function for a set of resources is induced by a stochastic planning problem, represented as a Markov decision process. Under this model, the value of a resource bundle is the expected value of the best MDP policy realizable given the resources. As I will demonstrate analytically and experimentally, this compact representation of utility functions can be used to develop resource-allocation mechanisms that achieve drastic (often exponential) improvements in computational efficiency.

This is joint work with Ed Durfee.