×

Cooperative games on combinatorial structures. (English) Zbl 0983.91013

Cooperative game theory is a mathematical tool to model and analyze conflict and cooperation in the interaction of multiple decision makers (players). An important premise is the assumption that the players are able to make binding agreements before the actual decisions are made. In fact, it is usually (but unrealistically) assumed that all coalitions of players are possible.
The author indicates that this justifies the goal of this comprehensive book: the development of a theoretical framework of cooperative games where only certain coalitions are able or allowed to form. Thus, the cooperative games studied here are real-valued functions on the collection of possible coalitions of players. One of the main problems then is the search for allocation rules that distribute the utility in one or another “fair” way among the players.
In order to be able to present both his own results and that of others, the author recalls first the definition of a cooperative game and illustrates it by means of various typical examples such as assignment games and linear production games. Next, he recalls the definitions of several combinatorial structures, like convex geometries and matroids, which are used to model the collection of possible coalitions. Besides definitions and some results on these structures, the author provides the necessary theory on linear optimization methods (Chapter 2), discrete convex analysis (Chapter 3), and computational complexity (Chapter 4).
Chapters 5-10 basically form the core of the book. The structure of this part is as follows. In Chapters 5 and 6, the reader is provided with an overview on the results on games restricted by partition systems and union stable systems, respectively. Values, i.e., one-point allocation rules, are discussed in Chapters 7 and 8, which deal with games on convex geometries and matroids, respectively. Chapter 9 mainly describes the relations between three important set solutions, viz., the core, the selectope, and the Weber set.
In Chapter 10, the (widely applied) class of simple games is studied. The simple games of Chapter 10 serve as a bridge to get to computational aspects of values (Chapters 11 and 12): in Chapter 11 voting power (closely related to simple games) is treated. At the end of Chapter 11 it is shown how the package Mathematica can be used to compute power indices. Finally, in Chapter 12, the author presents several notebooks for Mathematica to calculate the Shapley, Banzhaf, and Myerson value of certain restricted games thereby relying on theoretical results provided in previous chapters.
The book is interesting mainly for graduate students and researchers in Game Theory, Operations Research, and the Political Sciences. In spite of its high level of abstraction, the book might be useful in other fields as well.
Reviewer: Flip Klijn (Vigo)

MSC:

91A12 Cooperative games
91-02 Research exposition (monographs, survey articles) pertaining to game theory, economics, and finance
91A44 Games involving topology, set theory, or logic

Software:

Mathematica
PDFBibTeX XMLCite