The Absorbing Sets Solution in Coalition Formation Systems
by
Norma Olaizola
Basque Country University
Coauthors: Elena Inarra (Basque Country University), Jeroen Kuipers (Maastricht University)

Partition function form games are one of the approaches being used to analyze the problem of coalition formation. These games consist of a player set and a function that assigns worths to all coalitions in any possible coalition structure. Hence, the worth of a coalition depends not only on the coalition itself, but also on what players outside the coalition do, which makes models of coalition formation extremely complex. We will make the simplifying assumption that the payoffs to the players are completely determined by the coalition structure that has formed. This motivates the definition of a coalition formation system as a pair (N,f), where N is a finite player set and f, is a function that assigns to each partition of N a (payoff) vector.

Starting from this mathematical model, one can still follow different approaches. We assume that the coalition formation process starts with an arbitrary coalition structure. Some players may be satisfied with this structure, others may want to change it. If the unsatisfied players have the capacity to change the coalition structure into something better for them, we assume that they will do so. We consider no time horizon or stoping criteria to end the process, this means that players can change coalition structures indefinitely unless some natural 'stable'coalition structure is reached.

Note that this process can adequately be described by means of an abstract game: the set of elements representing the set of all the coalition structures, and the binary relation defined on that set representing the plausible transitions between coalition structures. Several concepts have been defined for abstract games. After discussing and comparing some of them we decided to adopt the absorbing sets solution, that is defined as the collection of all the absorbing sets. This solution has a dynamic interpretation in a coalition formation context, it can be understood as a stable collection of coalitions structures whose elements will be created and destroyed endlessly. In other words, once an absorbing set is reached, the negotiation process gets stuck in a cycle. On the other hand, although this solution always exists it may not be uniqhe, in general. Hence, one may not know which of the absorbing sets will be reached. However, since we provide sufficient conditions for the absorbing sets solution to have a unique element, this problem is avoided in our context. We formulate some conditions which give rise to what we call symmetric cooperative systems, a specific class of coalition formation systems. One of the conditions we have considerer is that the sum of the payoffs over all players is maximal for coalition structure {N} and, not surprisingly, this 'efficient' coalition structure belongs to the unique absorbing set. However, we find that either {N} is the only element, or else our set contains at least one coalition structure dominated by {N}, i.e. a coalition structure where all players receive smaller or equal payoffs than the payoffs they would gety in {N}. This last case can be interpreted as analogous to the prisioner dilemma. It exibits an undesiderable consequence of the players myopic behavior, which may lead to Pareto dominated outcomes.

We conclude the paper with an example to clarify our results.

Date received: July 10, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Mathematical Conference Abstracts. Document # cafl-26.