30 May 2008, Computational Social Choice Seminar, Stéphane Airiau

Coalition formation is a generic means for engendering cooperation: by joining forces, people, robots, web services, resources, and firms can improve their performance. Forming efficient coalitions requires identifying synergies between different entities. In addition, different parties must negotiate and agree on a fair repartitioning of the worth created by the coalition. Most current studies in the multiagent literature assume known valuation functions that estimate or predict the worth of a coalition and which is independent of the other coalitions in the population. This latter assumption does not hold in many real scenarios: decisions about joining forces or splitting a coalition can depend on how the competitors are organized. This scenario has received little attention in the game theory or the multiagent systems community.

In this talk, I will first review the traditional game theoretic stability criteria (Core, Kernel, Shapley Value). Then, I will consider the case where an agent receives an individual payoff when it enters a coalition, and its payoff depends on the coalition structure formed by all the agents. I will describe a fair payoff distribution scheme when the agents are myopically rational. As the search space is exponentially large in the number of agents, our solution can be applied for only a small number of agents. Then, I will come back to valuation functions rewarding an entire coalition, and I will concentrate on Kernel-stable payoff distributions. We propose a modification of the Kernel to design a payoff distribution that depends only on the valuation function, and is independent of the coalition structure actually formed by the agents.

For more information, see http://www.illc.uva.nl/~ulle/seminar/, or contact Ulle Endriss (ulle at illc.uva.nl).