Coalition formation through motivation and trust

ABSTRACT

Cooperation is the fundamental underpinning of multi-agent systems, allowing agents to interact to achieve their goals. Where agents are self-interested, or potentially unreliable, there must be appropriate mechanisms to cope with the uncertainty that arises. In particular, agents must manage the risk associated with interacting with others who have different objectives, or who may fail to fulfil their commitments. Previous work has utilised the notions of motivation and trust in engendering successful cooperation between self-interested agents. Motivations provide a means for representing and reasoning about agents' overall objectives, and trust offers a mechanism for modelling and reasoning about reliability, honesty, veracity and so forth. This paper extends that work to address some of its limitations. In particular, we introduce the concept of a clan: a group of agents who trust each other and have similar objectives. Clan members treat each other favourably when making private decisions about cooperation, in order to gain mutual benefit. We describe mechanisms for agents to form, maintain, and dissolve clans in accordance with their self-interested nature, along with giving details of how clan membership influences individual decision making. Finally, through some simulation experiments we illustrate the effectiveness of clan formation in addressing some of the inherent problems with cooperation among self-interested agents.

References

1. M. E. Bratman. Shared cooperative activity. Philosophical Review, 101(2):327--341, Apr. 1992.]]
2. M. E. Bratman, D. Israel, and M. Pollack. Plans and resource-bounded practical reasoning. Computational Intelligence, 4:349--355, 1988.]]
3. S. Breban and J. Vassileva. Long-term coalitions for the electronic marketplace. In B. Spencer, editor, Proceedings of the E-Commerce Applications Workshop, Canadian AI Conference, 2001.]]
4. C. Brooks and E. Durfee. Congregating and market formation. In Proceedings of the First International Joint Conference on Autonomous Agents in Multi-Agent Systems, pages 96--103, Bologna, Italy, 2002. ACM Press.]]
5. C. Brooks, E. Durfee, and A. Armstrong. An introduction to congregating in multiagent systems. In E. Durfee, editor, Proceedings of the Fourth International Conference on Multi-Agent Systems (ICMAS-2000), pages 79--86, 2000.]]
6. C. Castelfranchi. Guarantees for autonomy in cognitive agent architecture. In M. J. Wooldridge and N. R. Jennings, editors, Intelligent Agents: Proceedings of the First International Workshop on Agent Theories, Architectures and Languages (ATAL-94), pages 56--70. Springer-Verlag, 1995.]]
7. C. Castelfranchi and R. Falcone. Principles of trust for MAS: Cognitive anatomy, social importance, and quantification. In Proceedings of the Third International Conference on Multi-Agent Systems (ICMAS-98), pages 72--79, Paris, France, 1998.]]
8. M. d'Inverno and M. Luck. Understanding Agent Systems. Springer-Verlag, 2001.]]
9. D. Gambetta. Can we trust trust? In D. Gambetta, editor, Trust: Making and Breaking Cooperative Relations, pages 213--237. Basil Blackwell, 1988.]]
10. N. Griffiths. Motivated Cooperation in Autonomous Agents. PhD thesis, University of Warwick, 2000.]]
11. N. Griffiths and M. Luck. Cooperative plan selection through trust. In F. J. Garijo and M. Boman, editors, Multi-Agent System Engineering: Proceedings of the Ninth European Workshop on Modelling Autonomous Agents in a Multi-Agent World (MAAMAW'99). Springer-Verlag, 1999.]]
12. N. Griffiths, M. Luck, and M. d'Inverno. Annotating cooperative plans with trusted agents. In R. Falcone and L. Korba, editors, Proceedings of the Fifth International Workshop on Deception, Fraud and Trust in Agent Societies, 2002.]]
13. M. Klusch and O. Shehory. Coalition formation among rational information agents. In W. Van de Velde and J. W. Perram, editors, Agents Breaking Away: Proceedings of the Seventh European Workshop on Modelling Autonomous Agents in a Multi-Agent World (MAAMAW-96), pages 204--217, 1996.]]
14. H. J. Levesque, P. R. Cohen, and J. H. T. Nunes. On acting together. In Proceedings of the Eighth National Conference on Artificial Intelligence (AAAI-90), pages 94--99, Boston, MA, 1990.]]
15. M. Luck and M. d'Inverno. A formal framework for agency and autonomy. In Proceedings of the First International Conference on Multi-Agent Systems, pages 254--260. AAAI Press/The MIT Press, 1995.]]
16. S. Marsh. Formalising Trust as a Computational Concept. PhD thesis, University of Stirling, 1994.]]
17. S. Marsh. Optimism and pessimism in trust. In Proceedings of the Ibero-American Conference on Artificial Intelligence (IBERAMIA '94), 1994.]]
18. T. J. Norman. Motivation-based direction of planning attention in agents with goal autonomy. PhD thesis, University of London, 1996.]]
19. O. Shehory and S. Kraus. Task allocation via coalition formation among autonomous agents. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-95), pages 655--661, Montréal, Québec, Canada, 1995.]]
20. M. Tambe. Towards flexible teamwork. Journal of Artificial Intelligence Research, 7:83--124, 1997.]]
21. M. Wooldridge and N. R. Jennings. Formalizing the cooperative problem solving process. In Proceedings of the Thirteenth International Workshop on Distributed Artificial Intelligence (IWDAI-94), pages 403--417, Lake Quinhalt, WA, 1994.]]

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Distributed artificial intelligence