22 September 2006, Computational Social Choice Seminar, René van den Brink

Abstract

A situation in which a finite set of players can generate certain payoffs by cooperation can be described by a cooperative game with transferable utility (or simply a TU-game). In a TU-game there are no restrictions on the cooperation possibilities of the players, i.e. every subset of the player set is feasible and can generate a worth.

Recently, TU-games are applied to economic allocation problems where there are restrictions on the possibilities of cooperation. Various models of restricted cooperation in cooperative games have been developed, such as games in coalition structure and games with limited communication structure.

Here we consider games with a permission structure in which the players in a TU-game are part of a hierarchical organization, refered to as a permission structure, such that there are players that need permission from other players (refered to as their predecessors) before they are allowed to cooperate. Thus, the possibilities of coalition formation are determined by the positions of the players in the permission structure.

Various assumptions can be made about how a permission structure affects the cooperation possibilities. In the disjunctive approach it is assumed that every player needs permission from at least one of its predecessors before it is allowed to cooperate with other players. Alternatively, in the conjunctive approach it is assumed that every player needs permission from all its predecessors before it is allowed to cooperate.

A solution for games with a permission structure is a function that assigns to every such a game a payoff distribution over the individual players. Given a game and a permission structure, in the same spirit as Myerson (1977), a modified game is defined which takes account of the limited cooperation possibilities. The conjunctive and disjunctive approach yield different modified games. Applying solutions for TU-games to the modified games yields solutions for games with a permission structure. For example, the Shapley value (Shapley (1953)) yields the disjunctive and conjunctive Shapley permission values. An alternative is to apply the Banzhaf value (which is based on the Banzhaf index for voting games (Banzhaf (1965)) and is generalized to TU-games games by, e.g., Owen (1975) and Dubey and Shapley (1979)). This yields the disjunctive and conjunctive Banzhaf permission values.

We discuss axiomatic characterizations of these permission values. The difference between the disjunctive and conjunctive permission values turns out to be about which fairness axiom to use. Fairness axioms compare the change of payoffs for certain players after deleting an arc. The difference between the Shapley and Banzhaf permission values turns out to be about the neutrality axiom that is used. Neutrality axioms compare the change of payoffs for certain players after splitting certain players into two players.

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