AAMAS Conference 2010 Conference Paper
On Agent Types in Coalition Formation Problems
- Tammar Shrot
- Yonatan Aumann
- Sarit Kraus
Coalitions and cooperation are key topics in multi–agent systems (MAS). They enable agents to achieve goals that theymay not have been able to achieve independently. A rangeof previous studies have found that many problems in coalitional games tend to be computationally intractable - thatis, the computational complexity grows rapidly as a functionof the number of participating agents. However, these hardness results generally require that each agent is of a differenttype. Here, we observe that in many mas settings, while thenumber of agents may grow, the number of different types ofagents remains small. We formally define the notion of agenttypes in cooperative games. We then re-examine the computational complexity of the different coalition formationproblems when assuming that the number of agent typesis fixed. We show that most of the previously hard problems become polynomial when the number of agent typesis fixed. We consider multiple different game formulationsand representations (characteristic function with subadditive utilities, crg, and graphical representations) and several different computational problems (including stability, core-emptiness, and Shapley value).