Handbook of the Shapley Value

Encarnación Algaba, Vito Fragnelli, Joaquín Sánchez-Soriano, Encarnación Algaba, Vito Fragnelli, Joaquín Sánchez-Soriano

• Publisher: Chapman and Hall/CRC
• Year: 2019
• ISBN:
  9781351241397
• Edition: 1
• Topic: Negocios y empresa
• Subtopic: Operaciones

Handbook of the Shapley Value contains 24 chapters and a foreword written by Alvin E. Roth, who was awarded the Nobel Memorial Prize in Economic Sciences jointly with Lloyd Shapley in 2012. The purpose of the book is to highlight a range of relevant insights into the Shapley value. Every chapter has been written to honor Lloyd Shapley, who introduced this fascinating value in 1953.

The first chapter, by William Thomson, places the Shapley value in the broader context of the theory of cooperative games, and briefly introduces each of the individual contributions to the volume. This is followed by a further contribution from the editors of the volume, which serves to introduce the more significant features of the Shapley value. The rest of the chapters in the book deal with different theoretical or applied aspects inspired by this interesting value and have been contributed specifically for this volume by leading experts in the area of Game Theory.

Chapters 3 through to 10 are more focused on theoretical aspects of the Shapley value, Chapters 11 to 15 are related to both theoretical and applied areas. Finally, from Chapter 16 to Chapter 24, more attention is paid to applications of the Shapley value to different problems encountered across a diverse range of fields. As expressed by William Thomson in the Introduction to the book, "The chapters contribute to the subject in several dimensions: Mathematical foundations; axiomatic foundations; computations; applications to special classes of games; power indices; applications to enriched classes of games; applications to concretely specified allocation problems: an ever-widening range, mapping allocation problems into games or implementation."

Nowadays, the Shapley value continues to be as appealing as when it was first introduced in 1953, or perhaps even more so now that its potential is supported by the quantity and quality of the available results. This volume collects a large amount of work that definitively demonstrates that the Shapley value provides answers and solutions to a wide variety of problems.

Chapter 1

The Shapley Value, a Crown Jewel of Cooperative Game Theory

William Thomson

University of Rochester, Rochester, New York, United States. E-mail: [email protected]

1.1Introduction

1.2Coalitional Games and their Values

1.3A Short Guide to the Chapters

1.4Acknowledgments

Bibliography

1.1 Introduction

Game theory is a towering intellectual achievement of the post-World-War-II era and the Shapley value (Shapley, 1953b) a centerpiece of the branch of game theory known as “cooperative game theory”. Introduced in the early days of the subject when mathematicians were its main contributors, it was quickly adopted by economists, political scientists, and operations researchers. Its popularity is reflected in the multiple theoretical analyses of which it has been the object over the years and in the ever expanding scope of its applications. Although the fortunes of some other concepts of game theory have waxed and waned, the Shapley value is as fascinating today as it was when first defined.

Shapley’s 1953b paper is his most cited paper. Together with the Nash bargaining solution (Nash, 1950), it is an obligatory reference in general game theory texts and, of course, it is given detailed attention in all comprehensive treatments of cooperative game theory. It even has an important place in the leading graduate microeconomics textbook (Mas-Colell et al., 1995).

The rich palette of essays gathered in this volume testifies to its remarkable resilience and versatility.

This Introduction first describes how the Shapley value fits in the conceptual apparatus of game theory. It reviews basic definitions of the key axioms that have been invoked in its classic characterizations. The second part briefly comments on how each of the chapters contributes to honoring Shapley and his value.

1.2 Coalitional Games and their Values

A painter on his own can secure a certain income and the same is true of a plumber. When a painter and a plumber get together, they can save on advertising, billing and insurance costs; they can recommend each other to their respective customers; as a result, they can get more in total than the sum of what they would get on their own. By joining forces with a carpenter, an electrician and an architect, they can set up a construction company and build houses. The company can achieve more than the sum of what the components of any partition of its employees could attain. The question it faces then is to distribute among them the revenue it generates, taking into account what each group would attain on its own.

More generally, consider a group of people, or “players”, who can get together in “coalitions”. Each coalition can engage in activities that create value. By pooling together the resources its members control, exploiting the technology at their disposal, putting to the best use their skills and their knowledge, it can achieve “something”, called its “worth”. The simplest case is when the “something” is given as a single number, referred to as “utility”. The assumption is made that utility can be transferred at a one-to-one rate among any two players. The vector collecting the worths of all the coalitions is a “transferable utility coalitional game”, for short a “TU game”. Here, the term “game” will simply be used. Utility is an abstract concept, however, and it will be easier to think of what coalitions can achieve and of what is assigned to players as money. This will be the most natural interpretation of the data of a game in almost all of the applications considered in this volume. Sometimes, players get in each other’s way—for instance, if they have to use the same facility to produce worth—and together, they achieve less that the sum of what the subgroups into which they could arrange themselves could achieve. In calculating the worth of a coalition, all of the opportunities and organizational constraints the coalition faces should be identified and properly taken into account. The amount that has to be divided between the players is the worth of the grand coalition.

A “dual” interpretation of the model is possible, in which worths are replaced by costs. To each group is associated the cost that the group would incur in order to satisfy some demand it has for a service for example, or to undertake some project. Most of what follows covers this kind of applications, but we use language that is best suited to situations in which what is to be divided is a desirable entity.

A “solution concept” is a mapping that provides, for each game, a payoff vector, or a set of payoff vectors. When the data of a game are interpreted in monetary terms, a player’s payoff is an amount of money, a salary, or a share of profits. A vector chosen by a solution concept for a game can also be thought of as a recommendation that an impartial arbitrator could make as to what the various players should get, or as a prediction of the compromise that they would agree on through negotiations. The negotiation process is left unspecified but one can imagine a conversation they would have, arguments they would make, in favor of this or that payoff vector, or to support general principles that could be invoked to select a payoff vector, not only for the game they face at this point, but also for each game they could have faced or could face in the future.

Single-valued solution concepts are often called “values” because the payoff specified for a player involved in some game is interpreted as the value to the player of participating in the game; alternatively, when the variables of the model are thought of in monetary terms, it is the amount that she would be willing to pay to get involved in it (or would have to pay if the cost-sharing interpretation of the model is taken).

The goal of the theory of coalitional games is to identify the most desirable solution concepts. Before going into the reasons why the Shapley value is widely regarded as one of them, it will be useful to show where it belongs in an organized inventory of solution concepts.

Two main categories can be distinguished (Hokari and Thomson, 2015). On the one hand, a “coalition-centric” solution concept attempts to satisfy coalitions. Each coalition has a claim on the worth of the grand coalition based on its own worth. Payoffs are not assigned to coalitions, however, but to players, so a coalition has to assess how well it is treated in terms of the sum of the payoffs assigned to its members. If this sum is too small, the coalition will object. To placate a coalition, the only instrument at one’s disposal is the payoffs to its members, a blunt instrument because as a function of the number of players, the number of possible coalitions increases very quickly. Also, raising a player’s payoff in an attempt to satisfy a coalition will imply lowering some other player’s payoff, and this will impact negatively other coalition(s). Hence, the balancing act that one faces in selecting payoff vectors.

On the other hand, a “player-centric” solution concept rewards each player directly based on an assessment of what she can achieve on her own and how valuable she is to others, that is, based on the worths of the various coalitions to which she belongs. The challenge here is the opposite of what it is for coalition-centric solution concepts; it is to aggregate or summarize this rich information in some fashion, to distill it into a payoff for each player.

Examples of coalition-centric solution concepts are the “core” (Shapley, 1953a)¹ and the “nucleolus” (Schmeidler, 1969). For a payoff vector to be in the core of a game, each coalition should get in total at least its worth. Otherwise, the coalition would refuse to participate. Depending upon the context, whether to participate may or may not be an option, but even if not, the scenario according to which a group of players would leave to collect its worth is a meaningful counterfactual on which to anchor the choice of a payoff vector.

For the nucleolus, not only the sign, for each coalition, of the difference between what its members have been assigned in total and its worth, but also the magnitude of this difference, are taken into account. A large difference means that the coalition is “treated well” and a small difference the opposite. Expecting the loudest complaints from coalitions that are treated the worse leads to a lexicographic search for payoff vectors at which, dealing with coalitions in the reverse order of how well they are treated, each is treated as well as possible.

A first example of a player-centric solution concept is the “plain egalitarian value”, which divides the worth of the grand coalition equally among all players. This solution concept has the disadvantage of disregarding the worths of all other coalitions.²

The “equal-division-over-individual-worths value” first assigns to each player its own worth, then splits what remains equally among all players. This value is a little more responsive to the data of the game.

Next, say that a player’s “contribution” to a coalition to which she belongs is the change in the worth of the coalition if she leaves; if she does not belong to a coalition, her “contribution” to it is the change in the worth of the coalition if she joins. (It is with a slight abuse of language that the term is applied to a quantity that may be negative.) Calling a player’s contribution to the grand coalition her “principal contribution”—it is this contribution that is most meaningful to an economist—the “equal-division-over-principal-contributions value” first assigns to each player her principal contribution, and then splits what remains equally among all players. This value too ignores most of the coordinates of a game, but instead of using as reference the worths of individual players, it uses their principal contributions.

The Shapley value is also a player-centric solution concept. However, by contrast to the three solution concepts just defined, it has the merit of taking all coordinates of a game into account: It assigns to each player a weighted average of her contributions to all coalitions, the weights being combinatorial expressions that are most easily derived from the following scenario. Imagine players arriving one at a time in some order and assign to each player what she contributes to the coalition consisting of all the players who were there when she arrived; then take the simple average of her contributions over all orders of arrival.

The Shapley value satisfies a number of appealing properties and various axiomatizations that have been given of it are brought up in several of the chapters of this volume. Shapley’s (1953b) own characterization is based on four axioms: “efficiency” says that the sum of everyone’s payoffs should be equal to the worth of the grand coalition; “the null player axiom” says that if all of a player’s contributions are equal to 0, that is what she should get; “symmetry” says that two players who play symmetric roles in a game should be assigned equal payoffs; “additivity” says that the payoff vector selected for the sum of two games should be the sum of the payoff vectors selected for each of...