A Course on Cooperative Game Theory

Introduction

As we have seen in the discussion of the profit-sharing game in Chapter 1, if all the players in a game decide to work together, there arises a natural question concerning the division of profit among themselves. We have also observed that if some of the players in a coalition object to a proposed allocation, they can decide to leave the coalition. In order to understand this formally, a rigorous treatment of the worth of different coalitions of players and the marginal contribution of a player to a coalition is necessary. Often, some structural assumptions about a game, for instance, whether the game is additive, super-additive or sub-additive, make the analysis convenient. Moreover, in some situations, study of issues like equivalence between two games becomes relevant. This chapter makes a formal presentation of such preliminary concepts and analyzes their implications.

Preliminaries

In this section, we present and explain some preliminary concepts and look at their implications. We assume that N = {A1, A2, …, An} is a finite set of players, where n ≥ 2 is a positive integer. The players are decision makers in the game and we will call any subset S of N, a coalition. The entire set of players N is called the grand coalition. The collection of all coalitions of N is denoted by 2N; each coalition has certain strategies which it can employ. Each coalition also knows how best to use these strategies in order to maximize the amount of pay-off received by all its members. For any coalition S, the complement of S in N, which is denoted by N \ S, is the set of all players who are in N but not in S. For any coalition S, |S| stands for the number of players in S.

An n-person cooperative game assigns to each coalition S, the pay-off that it can achieve without the help of other players. It is a convention to define the pay-off of the empty coalition Ø as zero.