Values for cooperative games with restricted coalition formation

*Xianghui LiĀ is a PhD student in the research group Discrete Mathematics and Mathematical Programming. Her supervisors are prof.dr. M.J. Uetz from the Faculty of Electrical Engineering, Mathematics and Computer Science and prof.dr. H. Sun from the Northwestern Polytechnical University, Xian, China.*

In the standard cooperative games, it is often implicitly assumed that any coalition may form and the worth of the grand coalition will be divided among all players. However, since the coalition formation problems may depend on many factors (for example, the sharing rule used), it is not unlikely that in certain cases the players prefer other options to organize themselves. This thesis focuses on the values for games with restricted coalition formation. In Chapter 1, we briefly present the background and the basic knowledge for cooperative games. Apart from the introductory Chapter 1, our thesis can be divided into two parts according to the factors that influence the coalition formation.

The first part consists of Chapters 2 and 3, where the coalition formation is affected by the characteristic functions or a given solution concept of games. Chapter 2 assumes that any two players are allowed to exchange their positions, and thereby claims that only those ordered coalitions where the addition of every player benefits both the coalition formed by its predecessors and itself, and increases or at least does not reduce the marginal contributions of its predecessors can be formed. In the similar spirit of graph game, we define an order restricted game which transforms a cooperative game to a game in generalized function form. Finally, we define the average of marginal contributions of every player overall feasible different permutations in the order restricted game as the allowable value for games with restricted permutations and provide its characterizations. When the game is convex, the allowable value coincides with the Shapley value. Moreover, we list some extensions of the allowable value.

Chapter 3 studies a combination of coalition formation and stability for cooperative games. We assume that for a given allocation rule, it is possible for a set of players to improve their payoffs if the worth of the coalition they form exceeds the sum of their individual payoffs.

Considering that in most cases, the core might be empty, we define a concept of levels core by the aid of a levels structure, which is a weak version of the core. We show how to construct an element of the levels core by a procedure which is interpreted as the ``stabilization'' of the Shapley value (or, any other value), and which generally works for all superadditive games even if the core is empty. Moreover, we model the procedure by a series of non-cooperative level formation games in strategic forms and show that the strategic choices of players in each level formation game corresponding to this level of the levels structure in the outcome is a strong Nash equilibrium. Finally, the same procedural idea is applied for any situation where the levels structure is given, and a LIS value is proposed and characterized.

The second part consists of Chapters 4-7, which pay attention to the cooperative situations where the coalition formation is restricted by the given social, economic and other structures.

Inspired by the two-step Shapley value cite{kamijo2009two} for games with a coalition structure, Chapter 4 defines a multi-step Shapley value for cooperative games with levels structures. Furthermore, we give a non-cooperative multi-step bidding mechanism to implement it.

In Chapter 5, we allow different weights of players in different conferences and establish a framework of weighted hypergraph communication situations. First, we define a concept of power measure to reflect the bargaining power of players for the surplus of their conferences in the cooperation between conferences by arguing that players who contribute less in the cooperation between conferences should pay part of their cooperative earnings as intermediary fees to players who contribute more. Then, we define a power surplus solution, which can be seen as a generalization of the position value and provide its axiomatizations. Finally, we list two examples to illustrate the applications of the power surplus solution.

Chapters 6 and 7 define and axiomatize the Myerson value and position value for communication situations with fuzzy coalition where players have the Choquet, proportional, or multilinear behavior, respectively.