Handbook of the Shapley Value

This volume belongs to the series in Operations Research, and is devoted to the modern development and applications of the Shapley value—one of the most famous tools of the cooperative (non-antagonistic) game theory. It was introduced by Lloyd Shapley in 1953 (Shapley 1953), who together with his follower Alvin Roth (Roth 1988) won Nobel Prize in economics in 2012. Shapley value (let us denote it SV) uses a finite formula of combinatorial kind to assign a unique distribution among all the players who yield a total surplus in their coalition. In a brief lay explanation, the SV allocates the total value of the game to each player by evaluating over all possible coalitions that a player can join in. The value for an ith player can be defined as$${\phi }_i={\displaystyle \sum _{S-\text{all}\text{subsets}}{\gamma }_{n(s)}}\left[\upsilon (S)-\upsilon (S-\{i\})\right]$$here the summing is taken across all possible subsets of players S. The function v() is called a characteristic function defining a value of a coalition. The value of an ith player is defined via the averaged increments for all subsets of the value v(S) of the game for a subset S containing player i from the value v(S−{i}) of that subset of players without the ith player. In other words, it is the marginal value of adding the player to any possible set of other players. The weights are defined as$${\gamma }_{n(s)}=\frac{(s-1)!(n-s)!}{n!}$$ so the summation is weighted by a factor that reflects the number of subsets of a particular size (s) that are possible given the total number of players (n).

The book opens with the foreword by A. Roth, and presents about 60 authors in 24 chapters of their contributed papers. The most of works describe developments achieved in Spain and several other European countries. In the Preface, the editors describe the book structure in four parts: the first Chapters 1 and 2 give a general introduction to the book framework and to SV; then Chapters 3–10 present theoretical aspects of SV; the next Chapters 11–15 are related to theoretical and applied issues of SV; and the last Chapters 16–24 are devoted to SV applications to different problems in various fields. Let us consider these chapters in more detail.

Chapter 1, “The Shapley Value, a Crown Jewel of Cooperative Game Theory,” by William Thomson, draws general ideas and theory of the coalition games, and describes main directions of the current works, including mathematical and axiomatic foundations, computations and power indices, applications to special and enriched classes of games, to a widening range of concretely specified allocation problems and mapping allocation problems, and implementation of SV. In Chapter 2, “The Shapley Value, a Paradigm of Fairness,” the editors introduce main features of SV, with axiomatics, extensions, and some applications.

Chapter 3, “An Index of Unfairness,” by Aguiar et al., provides an axiomatic characterization of Shapley distance as a measure of unfairness in revenue distribution, which is used to show how favoritism, egalitarianism, and a tax levied over a fair wage can alter the fairness in an economy. Chapter 4, “The Shapley Value and Games With Hierarchies,” by Algaba and van den Brink, studies SV with structures and constraints of hierarchies among the players. Chapter 5, “Values, Nullifiers and Dummifiers,” by Alonso-Meijide et al., considers games with nullifying player who makes coalitions with him to have zero worth, and with dummifying player who makes coalitions with her to have a worth equal to the sum of the individual payoffs of its members. Using those, new axiomatic characterizations of Shapley and three kinds of Banzhaf values are given for transferable utility (TU) games. Chapter 6, “Games With Identical Shapley Values,” by Béal et al., describes axiomatization of SV based on its kernel for studying classes of games with the same SVs and the so-called inverse problem. Chapter 7, “Several Bases of a Game Space and an Application to the Shapley Value,” by Funaki and Yokote, uses properties of the so-called commander game when only one player in a given coalition yields the total payoff. Chapter 8, “Extensions of the Shapley Value for Environments With Externalities,” by Macho-Stadler et al., extends the classical SV, including, for instance, dividends approach by Harsanyi, non-cooperative and bargaining approaches, and partition function form (PPF) games. Chapter 9, “The Shapley Value and Other Values,” by Bernardi and Lucchetti, considers TU games and develops the concept of a probabilistic semi-value which special cases corresponds to the SV and Banzhaf power index, with applications to microarrays in genetics research and in social choice context. Chapter 10, “Power and the Shapley Value,” by Peters, deals with a family of power indices, including Shapley-Shubik, Shapley-Owen, Banzhaf, and Banzhaf-Coleman measures of pivotal players in a political party or parliament, who can turn a coalition from a loser to the winner by joining it. An example on the control and power in the stockholders’ board of Volkswagen and Porsche Automobile Holding is given.

Chapter 11, “Cost Allocation With Variable Production and the Shapley Value,” by Albizuri et al., studies the so-called Aumann-Shapley cost allocation rule (Aumann and Shapley 1974), on the discrete and continuum cases, with illustrations on President Roosevelt’s TVA Act of 1933, internal telephone billing rates, and aircraft landing fees. Chapter 12, “Pure Bargaining Problems and the Shapley Rule: A Survey,” by Carreras and Owen, reviews the relations of Nash equilibrium model and SV solution, and discusses cost allocation and other examples. Chapter 13, “The Shapley Value as a Tool for Evaluating Groups: Axiomatization and Applications,” by Flores et al., in place of each one player in a coalition game considers groups of players, and uses the generalized SV for assessment of groups in political parties, inventory cost games, and social networks. Chapter 14, “A Value for j-Cooperative Games: Some Theoretical Aspects and Applications,” by Freixas, discusses a class of multi-choice games where agents participate at several ordered levels, with examples on United Nations Security Council, and others. Chapter 15, “The Shapley Value of Corporation Tax Games With Dual Benefactors,” by Meca et al., presents a model of tax collection with possible evasion, which has a simple SV solution, with an example of two countries and two firms acting in both countries.

Chapter 16, “The Shapley Value in Telecommunication Problems,” by Sanchez-Soriano, suggests SV applications for various engineering problems, for instance, to wireless networks (in mobile communication and resource management, channel and bandwidth allocation), Internet pricing (keyword auctions in search engines, collaboration among ISP—internet service providers), and in communication routing problems. Chapter 17, “The Shapley Rule for Loss Allocation in Energy Transmission Networks,” by Bergantiños et al., describes distributing among the owners of an energy network, and proposes a coalition game, with estimations for the Spanish gas transmission network. Chapter 18, “On Some Applications of the Shapley–Shubik Index for Finance and Politics,” by Bertini et al., deals with construction of power indices, such as Shapley–Shubik index and its alternatives in evaluation of numerous shareholders. Chapter 19, “The Shapley Value in the Queueing Problem,” by Chun, transforms a mapping allocation problem to a coalition game where each user has her own cost of waiting. Chapter 20, “Sometimes the Computation of the Shapley Value Is Simple,” by Dall’Aglio et al., finds simple closed-form SV expressions for various problems, particularly, for sharing the cost of partially overlapping public goods, or airport games, cleaning pollutants from a river, some auctions and markets, special classes of games with decomposability property, maintenance cost games, microarray games and network centrality in biology, coverage games of the best choice for an ambulance locations, and more. Chapter 21, “Analysing ISIS Zerkani Network Using the Shapley Value,” by Hamers et al., assigned weights to terrorists by the resources they control and by the links between members, and evaluated the ranks of the individuals. The results can help to a better surveillance and targeting of the members of terrorist groups posing the greatest threat. Chapter 22, “A Fuzzy Approach to Some Shapley Value Problems in Group Decision Making,” Gladysz et al., is applied when the parameters of the game are not known precisely, and examples are given on several voting cases, particularly, on Brexit. Chapter 23, “Shapley Values for Two-Sided Assignment Markets,” by Núñez and Rafels, where in the pairing problem a player cares not about whom to pair with, but only about her own share. Chapter 24, “The Shapley Value in Minimum Cost Spanning Tree Problems,” by Trudeau and Vidal-Puga, considers both costs of connection between the players and costs of connection of the group to a source of supply, describing also the so-called Kar solution, Folk solution, the cycle-complete solution, and the weighted SV solution.

Dozens of the most recent references are given in each chapter. The book is innovative even for specialists in game theory and operations research, decision making and applied socio-economics research in various fields. Also, it makes sense to note that in practical implementations SV has been successfully applied in marketing research, for example, in total unduplicated reach and frequency estimation and other problems (Conklin, Powaga, and Lipovetsky 2004; Conklin and Lipovetsky 2005, 2013; Lipovetsky 2007, 2008), and in regression modeling and key driver analysis (Lipovetsky and Conklin 2001, 2010; Lipovetsky 2012).

Stan Lipovetsky
Minneapolis, MN