Sequential decision making in repeated coalition formation under uncertainty

ABSTRACT

The problem of coalition formation when agents are uncertain about the types or capabilities of their potential partners is a critical one. In [3] a Bayesian reinforcement learning framework is developed for this problem when coalitions are formed (and tasks undertaken) repeatedly: not only does the model allow agents to refine their beliefs about the types of others, but uses value of information to define optimal exploration policies. However, computational approximations in that work are purely myopic. We present novel, non-myopic learning algorithms to approximate the optimal Bayesian solution, providing tractable means to ensure good sequential performance. We evaluate our algorithms in a variety of settings, and show that one, in particular, exhibits consistently good sequential performance. Further, it enables the Bayesian agents to transfer acquired knowledge among different dynamic tasks.

REFERENCES

• 1: C. Boutilier, T. Dean, and S. Hanks. Decision theoretic planning: Structural assumptions and computational leverage. Journal of Artificial Intelligence Research, 11:1--94, 1999.
• 2: Georgios Chalkiadakis , Craig Boutilier, Coordination in multiagent reinforcement learning: a Bayesian approach, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860689]
• 3: Georgios Chalkiadakis , Craig Boutilier, Bayesian Reinforcement Learning for Coalition Formation under Uncertainty, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.1090-1097, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.74]
• 4: G. Chalkiadakis and C. Boutilier. Coalitional Bargaining with Agent Type Uncertainty. In IJCAI-07, pages 1227--1232, 2007.
• 5: Georgios Chalkiadakis , Evangelos Markakis , Craig Boutilier, Coalition formation under uncertainty: bargaining equilibria and the Bayesian core stability concept, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329203]
• 6: R. Dearden, N. Friedman, and D. Andre. Model based Bayesian Exploration. In UAI'99, pages 150--159, 1999.
• 7: Richard Dearden , Nir Friedman , Stuart Russell, Bayesian Q-learning, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.761-768, July 1998, Madison, Wisconsin, United States
• 8: Sarit Kraus , Onn Shehory , Gilad Taase, Coalition formation with uncertain heterogeneous information, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860577]
• 9: Sarit Kraus , Onn Shehory , Gilad Taase, The Advantages of Compromising in Coalition Formation with Incomplete Information, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.588-595, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.259]
• 10: Carlos Merida-Campos , Steven Willmott, Modelling Coalition Formation over Time for Iterative Coalition Games, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.572-579, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.174]
• 11: R. Myerson. Game Theory: Analysis of Conflict. Harvard University Press, 1991.
• 12: Tuomas W. Sandholm , Victor R. Lesser, Coalitions among computationally bounded agents, Artificial Intelligence, v.94 n.1-2, p.99-137, July 1997 [doi>10.1016/S0004-3702(97)00030-1]
• 13: Onn Shehory , Sarit Kraus, Methods for task allocation via agent coalition formation, Artificial Intelligence, v.101 n.1-2, p.165-200, May 1998 [doi>10.1016/S0004-3702(98)00045-9]
• 14: O. Shehory and S. Kraus. Feasible Formation of Coalitions among Autonomous Agents in Nonsuperadditive Environments. Computational Intelligence, 15:218--251, 1999.
• 15: Onn Shehory , Katia P. Sycara , Somesh Jha, Multi-Agent Coordination through Coalition Formation, Proceedings of the 4th International Workshop on Intelligent Agents IV, Agent Theories, Architectures, and Languages, p.143-154, July 24-26, 1997
• 16: W. T. Luke Teacy , Georgios Chalkiadakis , Alex Rogers , Nicholas R. Jennings, Sequential decision making with untrustworthy service providers, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Economics

Keywords:
coalition formation, reinforcement learning, uncertainty