Resource allocation among agents with preferences induced by factored MDPs

ABSTRACT

Distributing scarce resources among agents in a way that maximizes the social welfare of the group is a computationally hard problem when the value of a resource bundle is not linearly decomposable. Furthermore, the problem of determining the value of a resource bundle can be a significant computational challenge in itself, such as for an agent operating in a stochastic environment, where the value of a resource bundle is the expected payoff of the optimal policy realizable given these resources. Recent work has shown that the structure in agents' preferences induced by stochastic policy-optimization problems (modeled as MDPs) can be exploited to solve the resource-allocation and the policy-optimization problems simultaneously, leading to drastic (often exponential) improvements in computational efficiency. However, previous work used a flat MDP model that scales very poorly. In this work, we present and empirically evaluate a resource-allocation mechanism that achieves much better scaling by using factored MDP models, thus exploiting both the structure in agents' MDP-induced preferences, as well as the structure within agents' MDPs.

REFERENCES

• 1: Stefan Arnborg , Derek G. Corneil , Andrzej Proskurowski, Complexity of finding embeddings in a k-tree, SIAM Journal on Algebraic and Discrete Methods, v.8 n.2, p.277-284, April 1, 1987 [doi>10.1137/0608024]
• 2: R. Bellman. Adaptive Control Processes: A Guided Tour. Princeton University Press, 1961.
• 3: C. Boutilier, R. Dearden, and M. Goldszmidt. Exploiting structure in policy construction. In Proceedings of the 14th International Joint Conference on AI, pages 1104--1111, 1995.
• 4: Craig Boutilier , Richard Dearden , Moisés Goldszmidt, Stochastic dynamic programming with factored representations, Artificial Intelligence, v.121 n.1-2, p.49-107, Aug. 2000 [doi>10.1016/S0004-3702(00)00033-3]
• 5: Daniela Pucci de Farias , Benjamin Van Roy, On Constraint Sampling in the Linear Programming Approach to Approximate Dynamic Programming, Mathematics of Operations Research, v.29 n.3, p.462-478, August 2004 [doi>10.1287/moor.1040.0094]
• 6: D. P. de Farias , B. Van Roy, The Linear Programming Approach to Approximate Dynamic Programming, Operations Research, v.51 n.6, p.850-865, November 2003 [doi>10.1287/opre.51.6.850.24925]
• 7: Dmitri Dolgov , Edmund Durfee, Graphical Models in Local, Asymmetric Multi-Agent Markov Decision Processes, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.956-963, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.133]
• 8: D. A. Dolgov and E. H. Durfee. Optimal resource allocation and policy formulation in loosely-coupled Markov decision processes. In Proceedings of the 14th International Conference on Automated Planning and Scheduling, pages 315--324, 2004.
• 9: Dmitri Dolgov , Edmund Durfee, Computationally-efficient combinatorial auctions for resource allocation in weakly-coupled MDPs, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082573]
• 10: D. A. Dolgov and E. H. Durfee. Symmetric primal-dual approximate linear programming for factored MDPs. In Proc. of the Ninth Int. Symposium on AI and Math. (AI&M-06), January 2006.
• 11: Carlos Ernesto Guestrin , Daphne Koller, Planning under uncertainty in complex structured environments, 2003
• 12: C. Guestrin, D. Koller, R. Parr, and S. Venkataraman. Efficient solution algorithms for factored MDPs. Journal of AI Research, 19:399--468, 2003.
• 13: M. I. Jordan. Graphical models. Statistical Science (Special Issue on Bayesian Stat), 19:140--155, 2004.
• 14: Daphne Koller , Ronald Parr, Computing Factored Value Functions for Policies in Structured MDPs, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.1332-1339, July 31-August 06, 1999
• 15: Kate Larson , Tuomas Sandholm, Mechanism design and deliberative agents, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082572]
• 16: Nicolas Meuleau , Milos Hauskrecht , Kee-Eung Kim , Leonid Peshkin , Leslie Pack Kaelbling , Thomas Dean , Craig Boutilier, Solving very large weakly coupled Markov decision processes, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.165-172, July 1998, Madison, Wisconsin, United States
• 17: Relu Patrascu , Pascal Poupart , Dale Schuurmans , Craig Boutilier , Carlos Guestrin, Greedy linear value-approximation for factored Markov decision processes, Eighteenth national conference on Artificial intelligence, p.285-291, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 18: M. L. Puterman. Markov Decision Processes. John Wiley & Sons, New York, 1994.
• 19: Michael H. Rothkopf , Aleksandar Pekec , Ronald M. Harstad, Computationally Manageable Combinational Auctions, Management Science, v.44 n.8, p.1131-1147, August 1998 [doi>10.1287/mnsc.44.8.1131]
• 20: P. Schweitzer and A. Seidmann. Generalized polynomial approximations in Markovian decision processes. Journal of Mathematical Analysis and Applications, 110:568--582, 1985.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Algorithms, Design, Performance

Keywords:
(multi-)agent planning, task and resource allocation in agent systems