Computationally-Efficient Combinatorial Auctions for Resource Allocation in Weakly-Coupled MDPs

Dmitri A. Dolgov, and Edmund H. Durfee

In Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-05). Pages 657--664. July 2005.

Copyright © 2005 ACM. Publisher's version is available at http://doi.acm.org/10.1145/1082473.1082573.

Abstract
The capabilities of an autonomous agent are often determined by the resources that are available to it. We examine the problem of allocating scarce resources among multiple self-interested agents, operating in complex, stochastic environments (modeled as MDPs), where the value of a particular resource bundle to an agent is the expected payoff of the best control policy the agent can implement using these resources. Combinatorial auctions are popular mechanisms for allocating resource bundles among agents with such complex preferences. In particular, generalized Vickrey auctions (GVAs) yield socially optimal outcomes and have excellent strategic complexity, but suffer from high computational complexity for the agents' preference-valuation and the auctioneer's winner-determination problems. We describe a GVA-based mechanism that exploits knowledge of the agents' MDP-based resource preferences, and we show analytically and demonstrate empirically that this leads to an exponential improvement in computational efficiency over a straightforward GVA implementation with flat preferences. We also present a distributed implementation of the winner-determination problem that leads to further speedup while maintaining strategy-proofness of the mechanism, and without revealing agents' private MDP information.


BibTex
@inproceedings{ dolgov05caMDP,
   paperID   = "AAMAS-05",
   month     = "July",
   author    = "Dmitri A. Dolgov and Edmund H. Durfee",
   booktitle = "Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-05)",
   address   = "Utrecht, The Netherlands",
   title     = "Computationally-Efficient Combinatorial Auctions for Resource Allocation in Weakly-Coupled MDPs",
   pages     = "657--664",
   year      = "2005"
}


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