Theoretical Mathematics Finds Use in Economics--A Tribute to Lloyd Shapley

Economics benefited tremendously, as did mathematics itself, because Lloyd Shapley did the mathematics that he did....

Joseph Malkevitch
York College (CUNY)
Email Joseph Malkevitch

 

Introduction

When Lloyd Shapley was notified that he had won the Nobel Memorial Prize in Economics for 2012 he is quoted as saying

“I’m a mathematician, I’m not an economist.”
 

While some mathematicians talk about the "beauty" of mathematics and disparage applied mathematics, one of the beauties of mathematics for me is how insightful it proves to be in fields outside of mathematics. Within the social and behavioral sciences mathematics has interacted with economics dramatically. In particular, economics benefited tremendously, as did mathematics itself, because Lloyd Shapley did the mathematics that he did. His work was for the most part theoretical rather than applied mathematics and much of it would fall within the domain of mathematics called game theory. There is an impressively long list of mathematical "pioneers" of game theory: The list includes John von Neumann, John Nash, Lloyd Shapley, David Gale, John Harsanyi, Harold Kuhn, Robert Aumann, Kenneth Arrow, Albert Tucker, and William Lucas. However, game theory also owes a lot to economists and other scholars who inspired mathematical work and who collaborated with mathematicians. Examples include Oskar Morgenstern, Martin Shubik, and Steven Brams. Many of these individuals had ties to Princeton University. Among a younger generation of game theorists and contributors to the theory of voting and mechanism design, there are Michel Balinksi, Eric Maskin, Roger Myerson, Alvin Roth, Donald Saari, and H. P. Young.

While not all of the people listed above wrote their doctoral thesis in the area of game theory, they would all have thought of themselves as mathematicians despite making major contributions to subjects outside of mathematics. Strangely, today people who call themselves game theorists are rarely housed in mathematics departments. More often than not they will teach in a department of economics, political science or at a business school. This is sad because the general public, when trying to understand what mathematics is--the nature of the subject and where it finds uses--can learn a lot from looking at the kinds of problems that game theory addresses and the successes that game theory has had in understanding the world. And yet, game theory also contributes to work in theoretical mathematics and theoretical computer science by addressing fundamental questions that in the short run don't find use in the "world."

Two of Lloyd Shapley's most famous collaborations were with people who were part of the Princeton group who worked in game theory. One of these collaborations was with David Gale. The paper "College Admissions and the Stability of Marriage" published in 1962 is highly cited but did not have a totally smooth route to publication. In one formulation the paper shows that if n students and n hospitals rank each other without ties, it is possible for the students and the hospitals to be paired in a "stable" manner--no student or hospital would rather be paired with another partner than with the partner assigned . Gale and Shapley developed an algorithm, often called the deferred acceptance algorithm, which efficiently locates such a stable marriage. In fact, the algorithm can be used to find two "extreme" stable marriages (which sometimes are identical) which are optimal from the student's point of view or from the hospital's point of view. It was partly for this work that Shapley won his Nobel Prize. The prize was shared with Alvin Roth, and perhaps, had not David Gale died by then, the prize might have also been shared with Gale.

The other famous joint work with a Princeton-connected co-author was with Martin Shubik, who worked in the area of economics. Their joint work, which can be viewed as an application of the Shapley value (discussed in more detail below) is a way of measuring the "power" or influence of the players in a voting game. The basic idea is that players interact to form coalitions in a situation where political action can be taken if the coalition forms. The Shapley-Shubik Power Index can be used for voting situations like the Security Council of the United Nations or the Electoral College. The Electoral College is an example of a weighted voting game with 51 players (players are the 50 states and the District of Columbia). The District of Columbia casts 3 votes and for the other states the number of votes cast equals the number of senators for the state (2) and the number of members of the House of Representatives for that state. Thus, 538 votes are case (100 + 435 + 3) and 270 votes are needed for a candidate to achieve a majority. Note that in the Electoral College a split of 269-269 is possible. Games where players cast a block of votes and there is a quota Q, usually set to be the smallest positive integer larger than than half the sum of the weights, is called a weighted voting game. The Shapely-Shubik index can be used to indicate the "power" of the individual players. However, there are many different approaches to assign a power to the players in a weighted voting game or more general "voting" games." It is important to note that in such games a player may cast a positive number of votes but never be a member of a "minimal winning" coalition. Thus, in designing weighted voting games it is not typically useful to assign players weights which, by way of example, are proportional to the populations of the constituencies that they represent.

My goal here is in an informational way to discuss the mathematics that Shapley developed, provide some biographical information about him, and the forces that molded his mathematics, and describe the uses in economics (and elsewhere) that his mathematics was put to.

Comments?

Lloyd Shapley

Lloyd Shapley was the son of Harlow Shapley and Martha Betz.
 

 

His father was a famous astronomer who had a long career first using the Mt. Wilson telescope in Pasadena, California and later as director of the astronomical observatory at Harvard. One of his noted discoveries was that the Sun was not located at the "center" of its galaxy, the Milky Way.

Lloyd Shapley was born on June 2, 1923 in Cambridge, Massachusetts. He had 4 siblings, 3 boys and one girl, and was the fourth child of the family. He attended Philips Exeter Academy and upon graduation from there attended Harvard University. His stay at Harvard was interrupted by World War II and in 1943 he was drafted and sent to China where he served in the Army Air Corps.
 

Part of his work for the Army involved weather prediction in support of bombing missions on Japan. One of Lloyd's accomplishments was to break a Soviet weather code which helped with making more reliable weather predictions. This won him a Bronze Star. Many mathematicians were involved with breaking codes during WW II and beyond. While cryptography is typically a team effort, mathematicians who were involved in such work include Alan Turing, Peter Hilton, William Tutte, and Andrew Gleason.

After the war he returned to Harvard where he physically completed his studies in 1947, having "majored" in mathematics, and serving as a member of Harvard's Putnam Team. The Putnam is a high prestige contest for undergraduate mathematics students, founded in 1927. Many very successful Putnam participants have gone on to have distinguished careers in mathematics or other fields. After finishing at Harvard Shapley sought a job at the RAND Corporation.

RAND, Princeton and UCLA

The RAND Corporation was initially a creature of the Douglas Aircraft Company and the U.S. air forces, formed to serve as a "think tank" for the military and its contractors. RAND's name drew on the letters of "research and development." RAND has gone through various stages since its formal "birth" in 1948, with funding coming in a variety of ways. While wars are fought with soldiers and weapons, the military and the private companies who supported keeping the military "strong" came to realize that there had to be science and mathematics behind military preparedness and research. With regard to mathematics, the emerging area of operations research (OR) had more than proved its value during WW II. In particular, the area of OR of finding a best or optimal solution to a problem defined by a linear equation "objective function," and constraints which were given by linear equations or inequalities, proved very useful during the war. Now known as linear programming this methodology had helped with the war efforts greatly by solving logistical problems with supplies for our troops in America and abroad. Over a period of time this part of OR expanded to what is called mathematical programming which, in addition to linear programming, includes integer programming. Loosely speaking, integer programming involves constructing mathematical models where the linear objective function and the constraints that satisfy them can't be arbitrary numbers but must be non-negative integers. While there are polynomial time algorithms for solving linear programming problems, this is not true of integer programming problems some of which but not all types of which, are computationally much more complicated. In terms of theory, it turns out that there are strong connections between linear programming and game theory as shown by von Neumann and others. Some feel, however, that over emphasis about this connection obscured the importance of the way that game theory situations in political science and economics could show the way for as yet unexplored areas in theoretical mathematics such as some looked at by Shapley. Today mathematical programming finds applications ranging from blending gasoline fuels, to mixing animal feeds, scheduling air planes, operating rooms, and production lines.

While at RAND, Shapley got involved with the newly emerging field of game theory. John von Neumann and Oskar Morgenstern's book, Theory of Games and Economic Behavior (Princeton U,. Press), had appeared in 1944 with roots in earlier work of von Neumann. A group of RAND employees created a discussion group to explore the ideas in the book. This resulted in a collaboration between Shapley and Roger Snow on a paper dealing with games that appeared in the Princeton U. Press compendium of papers dealing with game theory. However, there were also reports that Shapley wrote for RAND, one in 1948, ten in 1949, and one in 1950, and many more in the years that followed. After a few years at RAND, Shapley decided to pursue graduate studies in mathematics at Princeton, though over the summers he was at RAND as a consultant. There was a certain irony that RAND did a lot of classified work which required a security clearance, a process complicated for Lloyd Shapley by the fact that his father had come under scrutiny by Senator Joseph McCarthy.

The atmosphere at Princeton during the period that Shapley was a student there gave a tremendous boost to his career trajectory as well as to the trajectory that game theory was to have not only in America but world wide. In the pioneers list above, many of these individuals had some "Princeton" connection. Furthermore, many of them had ties to Albert Tucker, who in the mathematics community is perhaps more known as the chairperson of the mathematics department at Princeton than for his role in shaping the development of game theory. Tucker was Shapley's doctoral thesis advisor. His thesis was entitled "Additive and Non-Additive Set Functions." Eventually Shapley would come to have 6 doctoral students of his own during the time he was at UCLA.


 

Many mathematicians came to Princeton with backgrounds in areas not specifically related to game theory but took up game theory as a subject to investigate and turned that interest into a lifelong passion. Shapley returned to working for RAND but as time went on many of the people who he collaborated and worked with had left. So Shapley decided to seek and obtain a position in academia, moving to UCLA where his appointment was in both the mathematics and economics departments. In all, he spent 20 years at UCLA before retiring from there in 2001, having supervised his final doctoral student just the year before. During his productive life as a researcher he worked closely with many researchers and actively attended conferences for researchers. MathSciNet, the abstracting service for research publications in the area of mathematics provided through the American Mathematical Society, lists 69 papers written and co-authored by Lloyd Shapley. Shapley and Alvin Roth were honored in getting the Nobel Prize in Economics in 2012. Shapely died at 92 in 2016. His insights into game theory continue to inspire mathematicians, economists, and political scientists as well as other scholars.

 

Comments?

Some background for game theory

One of the approaches to the theory of games is to think of there being a finite collection of players who try to come together and work together in a group, a subset of players called a coalition. Coalitions form for the purpose of getting a reward or payoff. This payoff might be the passing of a piece of legislation in a legislature, a share of a market in an economic situation, or how to divide the costs of a joint project.

As mathematics often does, it turns to abstraction and notation to represent and understand the "rules" of the situation. This modeling helps both capture the ideas intended and serve for extensions of what was done by altering the "rules." So what notions have to be captured in understanding how individuals team together to achieve a goal? Each person has some "payoff" that he/she can accomplish on their own. By joining with others, more payoff can presumably be achieved for the group as a whole but at the "price" of having to divide up the presumably larger payoff for the bigger group among the members of the larger coalition in some reasonable way. Since what individuals can get on their own may vary, how to share a combined payoff is open to various viewpoints. This suggests that one needs to have payoffs where larger groups have a combined payoff of at least what the individuals in the group can get. It also suggests that there are "rationality" issues from the point of view of the individual and the point of view of groups of individuals.

Some games scream out about the conflict involved (non-cooperative games) but some games involve the need to work together (cooperative games) to cut costs or achieve some gain. In cooperative game theory, one idea is that there will be an attempt for all the players to work together so that a "grand coalition" forms. If this indeed happens then what is necessary is to have a way to divide up the proceedings for the grand coalition in a way that encourages all of the players to participate.

Often one's first introduction to game theory is via zero-sum or non-zero-sum "non-cooperative" games, usually described using a matrix or payoff table. Here for simplicity, the assumption is made that there are two players (named Row and Column) and they have two actions each taken independently of each other. The results of these actions give rise to payoffs that the players know in advance (perfect information). Thus if Row takes the Row 1 action and Column takes the Column II action in Figure 1 (a), then Row loses 4 and Column wins 4. Figure 1 (a) is such that the payoffs to the players add to 0, thus, the name zero-sum game. Figure 1 (b) has payoffs that don't add to zero, and illustrates a non-zero-sum game. The two games in Figure 1 are somewhat typical of "perfect information" matrix games for two players.
 

 

Both of the games above are of interest in educational settings. The first may not appear to be a fair game, but in a precise sense it is, while the second is an example of what is sometimes called Prisoner's Dilemma. This game illustrates that seemingly "rational" play may result in an outcome that is unintuitive. Many people see the fact that playing Row 2 by Row and Column II by Column as having a better outcome regardless of what one's opponent does as a reason to play Row 2 and Column 2 in either single or repeated plays of this game, despite both players getting a negative payoff!

However, many of the games that interest people involve players getting together for some common goal. A good example is the parties in the parliament of a democratic country. If no party has a majority of seats in the legislature, to pass a piece of legislation will require that several parties work together to achieve a goal. Sometimes the "spoils" of the collaboration can't be parceled out among the parties; everyone, say, gets credit for a law that changes "health care" benefits.

Some games where players work together have something "tangible" and divisible, say money, that is to be shared. For example, as artificial as it may seem, suppose that three people are offered the opportunity to share $100 provided they can agree about how to divide up the $100 to the group that comes together as a "coalition." To get the $100 some subset of players of size at least two has to work together. If the players are named 1, 2, and 3, for example, and players 2 and 3 enter an agreement to work together, they would receive the $100. Any pair of players in this game can guarantee $100 for themselves. How they might agree to split the $100 is up to them, perhaps $50 for 2 and $50 for 3 but if they want to they could split so that $98 goes to player 2 and $2 to player 3. This does not seem like a "fair division" but player 3 may not get on with player 1 and does not want to "cooperate" with him while player 3 is happy to get even $2 (rather than $0) and maybe "score points" with 2 for some future joint efforts.

Let us use an ordered triple to denote the payoffs that might be considered. Symmetric solutions would be (50, 50, 0) $50 for each of players 1 and 2 and $0 for player 3, and (0, 50, 50) and (50, 0, 50). Another division of the proceeds as noted above might be (0, 98, 2). However, notice that if this game proceeds in time or there is a period of "tentative" coalitions before the time deadline to collect the $100 there is no "stable" coalition that seems natural. For example, suppose some negotiations lead to (50, 50, 0) as a division, perhaps because initially a coin was flipped to decide which of the three symmetrical solutions to use. Player 3 might go to player 2 and say how about you and I forming an alliance and we will divide the $100 with $60 for you and $40 me, the payoffs being (0, 60 40). Two of the three players do better by "moving" to this solution but now player 1 might suggest the division (50, 0, 50). Thus, we see that for this game there seems to be no division of the prize that will stand up to "trading" pieces of the prize. Suppose that we change the game so that the payoffs stay the same for all coalitions other than the grand coalition, and we change the value of the grand coalition to $150 or more. Thus, for exactly $150, if we allocate to each player (50, 50, 50), no player can go to another player and try to make a payoff arrangement that will seem more attractive than was possible when the grand coalition could only collectively garner for itself $100. This particular game (the payoff to the grand coalition is 100) has the property that its "core" is empty, that is, there are no solutions for dividing the spoils that avoids this shifting pattern of temporary agreements. Shapley made significant contributions to our understanding of the core concept (more details below).

The way that games such as this came to be modeled was using the coalitional form of a game rather than using trees or matrices to represent the game. Typically the set of players could be called N and would consist of the players named 1, 2, ..., n. Hence, N = {1,2, ...., n}. Each subset S of N with at least one player can be assigned a "value" V(S) which is the amount of "utility" that S can achieve as a group by working together. Game theorists as a foundation for their analysis of games had to look at the idea of the value of different kinds of things to different people. A cake might be viewed as having different values to different persons, but many things cannot be divided into pieces without losing their value such as a painting or computer. Even money can have different values to different persons depending on their wealth circumstances. I will denote this "payoff" to a coalition by V(S) and for convenience the null or empty set will be assigned the value 0. V(S) will be assumed to be a non-negative real number. To be realistic, it reasonable to assume that if X has more players than Y then V(X) ≧ V(Y) though "for the fun of it" one might look at what might happen for games where this might not be true. One can look at various assumptions about the behavior of the function V that assigns coalitions values. For example one might want to assume, for all coalitions S and T which are non-empty and have no players in common, that
 

Here S T denotes the subset of players that arises by lumping together the players in S and T, which is called taking the "union" of S and T.

A game which obeys this rule would be called "super additive" and assuming this rule might give coalitions incentives to form. Game theorists have studied this condition applied to games while also allowing for equality to hold in (*).

Notice that here we are looking at some approach to "solving" the game which is described using the coalition function defined for different subsets of players. We are getting at that perhaps V({1,2}) = 50 but players 1 and 2 might decide or be "forced" to divide up the 50 units with different schemes. We might have player 1 get 30 and player 2 get 20, player 1 get 10 and player 2 get 40 or player 1 get 10 and player 2 get 10. This last "division" seems peculiar but there might be some reason that the players might be "permitted" to do this.

What are some of the "fairness" rules that might govern what to do when thinking about reasonable ways to divide up the value that the grand coalition, the coalition of all of the players, can earn?

a. Symmetry

If the payoffs as defined via V(S) are symmetric with respect to players i and j, then i and j should receive equal amounts. Players whose role is identical in coalitions except for their names would get treated the same (e.g. get the same allotment).

b. Efficiency

The payoff to the collection of all players is all of what the grand coalition can garner for itself. (Why "waste" some of the possible payoff?)

c. Individual rationality

No player will accept in dividing up the spoils less than that player can get by playing on his/her own. (There is no incentive for an individual to join a coalition unless there is more to "share" in the "larger" coalition that the player joined. Thus one might assume that for each player i and any coalition S that does not contain i, V(S {i}) > V(S ) + V({i}).

d. Group rationality

When we add together what subsets of a coalition get, they should not get less than those subsets get together.

One can look for solutions to games that obey some or all of the "axioms" or "rules" such as these. Lloyd Shapley was a pioneer in looking at what is called the core of a game in characteristic form. The intuitive notion behind the core, though there are now many generalizations and variants of the original idea, is that one is looking for those payoffs where what is called individual rationality and group rationality both hold. Solutions in the core for n-player coalitional games (n at least 3 is where things start to get really interesting) are solutions where players can't try to negotiate "better terms" with other players because subject to the structure of the V(N) values, superior payoffs cannot be achieved. In thinking about the core for games with three players it is helpful to be able to visualize the payoffs for the different players. For those who have had some experience graphing, you can try getting insights into what happens for coalitional games by using diagrams like the ones below (Figure 2 and Figure 3). In Figure 3 there is a representation of points where a single player can get 34 units of payoff, and the points where player 1 gets 4 or 4 gets 10 with the remaining amounts going to players 2 and 3 are shown as the points of segments. One can use diagrams of this kind to show what the core of a 3-person game in characteristic form looks like. Note that Figures 2 and 3 show an equilateral triangle and that when a player gets a constant amount this shows up as a line parallel to one of the sides of the triangle. In Figure 1, lines parallel to BC and close to point A represent a payoff to player 1 which is close in size to M.
 

 

Lloyd Shapley was able to find conditions under which one could show that the core of a game had points in it. Sometimes the core is empty and in other cases there are infinitely many points in the core, so it is not clear which point to "advise" the players to "use." when negotiating for how to share the amount available in the grand coalition. Shapely was also able to obtain theorems about how to pick out a single point (now known as the Shapely value) in the "space" of ways to allocate the amount available to the grand coalition, but sometimes this point is not in the core!

There are many routes to game theory and Lloyd Shapley made contributions to nearly all of the approaches. There are cooperative games and non-cooperative games, there are games with "transferable" utility and those without, there are games where there is perfect information and those where there is partial and/or imperfect information.

To summarize, for the investigations into games that Shapley often worked with, one goes to what is known as the characteristic function form of a game, or its coalitional form. Here the notion is to associate with each subset of players, called a coalition, what amount of money (utility) that set of players can by working together obtain for themselves. One modeling assumption is that since each player brings something to the group, over time the grand coalition will form. Once this happens, the interesting issue is how to disperse the amount that the grand coalition can earn among the players based on the way that the smaller coalitions could get payoffs (or some other point of view).

Comments?

Cost sharing, other applications, and the Shapley value

Three fictional towns, Argon (A), Boron (B), and Carbon (C), are under court orders to clean up their sewage, currently being sent to the ocean but with more bacteria than meets state law. The towns have determined that the costs of meeting the state standards are displayed in the table below. Line 4 means that C to meet the standards by doing the waste treatment alone would incur a cost 8 while line 5 means that if A and B work together their cost will be 15.
 

Note that if A and C work together, then the total cost of the work would amount to 23 because the cost for A and C together is 17, while B would still have to incur a cost of 6, so the total would be 23. If A, B, and C can work together, the total cost can be brought down to 20.

There are a variety of questions one might ask:

a. Would one expect to see all three towns act separately?

b. If two or more towns work together, which of the coalitions might form?

c. How might the coalitions of players that might come about in situations such as this share the costs of "working together" rather than each "player" acting for his/her self?

A well-known approach to problem solving suggests that if one is not sure what to do to solve a problem, one should try a simpler case. So what one might consider is what we would do in terms of cost sharing for two players. Thus, for only A and B above, we might try saying that if A and B work together they should each be charged 7.5 units of the total cost of working together, that is, split the costs equally. However, this seems not to make much sense since B can do things alone for less. If one adds their separate costs to get 18 and reasons that A's stand alone cost is 1/3 of this and B's stand alone cost is 2/3, then assigning A one third of the joint costs and B two thirds of the joint cost might be reasonable, since then A would pay 5 and B would pay 10 and both would be better off working together. However, working together saves (12 + 6) - 15 = 3 units. If this saving is split equally, A would pay 4.5 and B would pay 10.5, which is a different way of splitting the joint cost of 15. Lots of different approaches emerge.

We can use set notation to show the cost to the players of working together in a particular game setting. Thus, we could describe the cost-sharing game we have looked at above in this way:

V {A} = 12; V {B} = 6; V {C} = 8

V {A, B} = 15; V {A, C} = 17; V {B, C} = 11

V {A, B, C} = 20

Above we briefly looked at how one might try to "fairly" share the benefit of two players cooperating. However, deciding what to do might vary with the "context" of the game. In games where the "payoff" to a coalition is having a candidate elected or a bill passed, the "reward" for joint action is the outcome of having the bill passed or the candidate one wanted elected. Without working together, nothing happens. However, in a cost-sharing situation (where some action is being required), the coalition must now decide how to divide the costs involved among the members of the "winning' coalition when working together cuts costs. If it would cost more to participate in a coalition than it would to have acted alone, this does not seem very "rational."

So in discussing a fair or reasonable collection of rules for a way of sharing the "value" for the members of a grand coalition, here are some axioms that a value or division scheme should obey.

Note that there is a difference between making assumptions about the rules that the representation of a game in coalitional form might take, the rules for V(S) in our descriptions above, versus the descriptions of what might be the "solutions" to such a game. Saying that players 1 and 2 can obtain V({1, 2}) = 20 does not say anything about how the players might share the 20 units that they can get working together. Thus, if one might require players named 1 never to get any benefit of working together, one could give 0 to player 1 and player 2 would get 20 and this is consistent with V({1,2}) being 20. However, there are infinitely many other ways of sharing 20 which are also consistent with V({1,2}) being 20. If we let p(A) be the payoff to a collection of players (which might be only one person) in dividing up the value of the "grand coalition" we might consider as an "axiom" that governs a reasonable approach to be that p({i}) ≧ V({i}). In words, the payoff to player i is at least as great as i could get by acting on his/her own.

Here are some examples with different flavors that one might be interested in understanding by using coalitional ways to represent these situations as games in applications settings, somewhat different from the cost sharing example just considered.

1. Bankruptcy problem

Three claimants (A, B, C) have put in for reimbursement due to a fire. The money available to settle the claims is 210 units. The individual claims are:

A = 150; B = 120; C = 90

What might be a reasonable way to settle these claims?

2. Airport utilization costs

What is a reasonable way of sharing costs of maintaining the runways of an airport which are used by 3 airlines of different sizes? Thus, the different airlines operate differing numbers of flights and use planes with varying weights. The wear and tear on a runway is related to the weight of the planes involved. How might 3 airlines share the yearly maintenance costs of the runways? Variants include having only one runway or different runways that are used to different degrees by the different airlines depending on the size of the planes in the respective fleets they use.

3. Accounting practice

Many large companies have separate pieces or divisions. These divisions often share resources such as phone systems, computer services, or advertising. This raises the question of how to fairly "apportion" the costs of these services to the various parts of the large company for purposes of analyzing how the different divisions of the company are doing, or for filing taxes.

4. Government ministries

When a coalition forms of different parties to create a government in a democracy (because no single party got a majority) there are often different "ministries" (labor, immigration finances, etc.) that people must be appointed to. One way to assign these ministries to the parties would depend on the size of the vote that each party got in the general election. What might be a fair way of doing this?

5. Power in a voting game

Suppose there are three legislators, A, B, and C, who cast blocks of votes of size 10, 7, and 5, respectively. If to pass a bill 12 votes (one more than 1/2 the sum of the weights is 12) are required, is there a way of measuring the influence (power) of the players?

Once one has expressed these "situations" in coalition form by using specifying V(S) for various sets of players S, one can address the question of how to "solve" the coalitional game by deciding what to give to each of the players.

There are a variety of approaches to "defining" the value of a game that Lloyd Shapley pioneered. However, one important intuition is that one should give each player i in a coalition credit for what he brings to the coalition that existed "prior" to i's joining the coalition compared to what it was entitled to without player i. Here is one way to conceptualize this. Imagine that someone was dispensing the amount available to the grand coalition but that this amount is given out depending on the order in which the players apply for this amount. This does not seem to be fair because the order in which people apply should not matter. We can "correct" this by seeing what amounts would be given out for all the orders possible and computing the average of the payoffs to the individual players over all of the orderings.

Let me illustrate this for the cost-sharing game spelled out in Table 1.

Since there are three players named A, B, C, how many orders are there to arrange these three players in? The first position (we will read from left to right) can be chosen in 3 ways, the second position in 2 ways, and the last position in 1 way. So there are 6 orders. For 4 players the number of ways would be 24, 4(3)(2)(1) = 2. In general, the number of permutations of n things, where order matters is n! (e.g. (n)(n-1)(n-2)....(3)(2)(1). Note that this is a fast growing number as n grows.

So for three players, here is the list of (ordered) permutations:

ABC
ACB
BAC
BCA
CAB
CBA

Consider giving the money out from left to right in the order of any of these permutations. Let us work out a few samples.

Consider ABC:

A is entitled to 12, which does not exhaust the 20 units of costs to be dispersed, so start by giving A a share of 12. Now when B arrives, A and B together are "entitled" to 15, so B would get 3 units. When C arrives, of the 20 units to disperse 5 are left so C gets 5.

Hence, ABC gives:

A = 12, B = 3, C = 5

For the ordering ACB we would have:

A gets 12, and since the coalition AC can be assigned a cost of 17 of which 12 was assigned to A, we give 5 to C, and so for B, of the 20 available to the grand coalitions, with AC having gotten 17 in costs, we have 3 left for B. Thus:

ACB gives:

A = 12, B = 3, C = 5.

What about CAB?

C is assigned 8 and CA assigned 17, so A gets assigned 9. When B arrives B gets assigned a cost of 3. Note that B will have to pay 3 for this order but that is better than the cost of 6 had B done things alone. So the grand coalition has an incentive to form given the numbers involved.

In the table below are filled in the results of carrying out this process for all six lines. Note that the columns show the amount given a particular player for the order shown in the left hand column:
 

The Shapley values of the players are A = 10, B = 4, and C = 11. Each of these numbers is less than that of the cost alone for a single player, as well as giving less cost than pairs acting together and forcing the third player to go it alone. It is instructive to study what happens to the Shapley value as the value of the costs for the grand coalition go up, to say, 20, 21, 22, 23, or 24. Each of these numbers is smaller than adding the stand alone costs for single players. However, at the cost of 24 for all working together, B and C can work together for a cost of 11 (an improvement on separate costs of adding to 14), but to add A to the group would add 13 to costs when the grand coalition has to pay 24, so costs go up by 13 but A's stand-alone costs are 12. In this "cost-sharing game" players are trying to keep their "payoffs" low but in some games one hopes one's payoffs are high. Associated with the original cost-sharing game here is a "dual" game which involves what different coalitions can "save" by banding together. A player who goes it alone saves nothing, but, for example, by working together B and C save 3, since 11 is three less than 6 + 8, the respective stand alone costs of B and C. So we could look at a different game where V(A) = 0, V(B) = 0 and V(C) = 0, V(AB) = 3, V(AC) = 3, and V(BC) = 3, and V(ABC) = 6. In the cost game one wants the costs one gets assigned as small as possible, in the savings game one wants the savings one makes as large as possible. One can now look at the core and the Shapley values of the original game (grand coalition 20) and the savings game (grand coalition 6). .

Lloyd Shapely and Martin Shubik collaborated on using the idea of the Shapley value in voting games, and in this environment it is called the Shapley-Shubik Power Index.
 

 

Consider the voting game of three players A, B, C, where A, B and C cast 10, 7, and 5 votes respectively, and where the "quota" for a bill to pass is 12, which is half the sum of the weights of the players plus one.

In this environment for each order of the players we give one point to that player who for this ordering puts the sum of the weights read from left to right to be at least equal to the quota. Each row gives rise to one "pivot" point for one of the players.

For example, consider the order ABC. A's 10 points can't pass the bill but B's 7 points added to A's 10 makes 17 which is more than 12 so for this order B gets the pivot point. For these numbers it is easy to verify that the second player in any order gets the pivot point. So each player gets exactly 2 pivot points and, thus, the power of each player is 2/6 or 1/3. A moment's thought should convince one that thinking of the players as having equal power makes a lot of sense, even though the players have different blocks of weight they cast. The "minimal" coalitions that can take action are AB, AC, and BC and this symmetry suggests equal power. If to pass a bill a quota of 13 were required (similar to what happens in many legislatures where for some bills a simple majority is needed but for other bills, a "super majority" is required, as when there is a vote on a proposed amendment to the U.S. Constitution) then one gets different powers for the players. In this case, A, B, and C casting 10, 7, and 5 votes but with a "quota" of 13, A gets 4 pivot points and B and C get one pivot point each. So A has power 2/3 and B and C have power of 1/6.

Another interesting power index was developed by John Banzhaf, which gives different results from the Shapley-Shubik index. The Banzhaf Index was also studied by Shapley (in a paper with P. Dubey), who helped clarify what axioms were needed to "characterize" the Shapley-Shubik Index and what axioms were need to characterize the Banzhaf Index.

Lloyd Shapley, as he himself observed, was a mathematician not an economist. However, Shapley had a truly remarkable career as a mathematician and this did not stop his having had tremendous influence on economics and other fields as well. His deep insights into game theory will never stop inspiring future work in the field he loved so much.

 

 

Comments?

References

Aumann, R. and S. Hart, (eds),, Handbook of Game Theory with Economic Applications, Volumes 1, 2, 3, North Holland, New York. (Note: A 4th volume edited by P. Young and S. Zamir appeared in 2015.)

Bondareva, Olga, Some applications of linear programming methods to the theory of cooperative games (In Russian), Kybernetiki. 10:(1963) 119–139.

Eatwell, J. and M. Milgate, P. Newman, (eds., )Game Theory (The New Palgrave), Norton, NY, 1989.

Dubey, P. and L. Shapley, Mathematical properties of the Banzhaf power index, Mathematics of Operations Research 4 (1979): 99-131.

Friedman, J., Game Theory, Second Edition, Oxford, New York, 1990.

Gale, D., and L. Shapley., College admissions and the stability of marriage, American Mathematical Monthly 69.(1962): 9-15.

Gale, D. and H. Kuhn, A. Tucker, Linear Programming and the Theory of Games, In Activity Analysis of Production and Allocation, T. Koopmans, (ed.), Wiley, NY, 1951.

Gillies, D., Some theorems in n-person games, Doctoral dissertation, Adviser, John von Neumann, Princeton, 1953.

Kuhn, H., (ed.), Classics in Game Theory, Princeton U. Press, Princeton, 1997.

Jones, A., Game Theory Wiley, NY 1980.

Leonard, R., von Neumann, Morgenstern, and the Creation of Game Theory, Cambridge U. Press, New York. 2010.

Lucas, W., A Game with No Solution, Bulletin AMS, 74 (1968) 237-239.

Moriarity, S. (ed.) Joint Cost Allocations, University of Oklahoma, Norman, 1981.

Mosteller, F. and P. Nogee, An experimental measurement of utility, J. of Political Economy, 59 (1951) 371-404.

Nash, J. and L. Shapley, A simple three-person poker game, Annals of Mathematics Study, 24 (1950) 105-116.

Roth, A., (ed.), The Shapley value: essays in honor of Lloyd S. Shapley. Cambridge University Press, 1988.

Shapley, L., A value for n-person games, In Kuhn, H. W.; Tucker, A. W. Contributions to the Theory of Games. Annals of Mathematical Studies. 28, 1953, Princeton University Press, pp. 307–317.

Shapley, L., On balanced sets and cores, Naval Research Logistics Quarterly, 14 (1967) 453-460.

Shubik, M., Game Theory at Princeton, 1949-1955: A Personal Reminiscence, In Towards A History of Game Theory, Weintraub, E. (ed.) Duke U. Press, pp. 151-163.

Straffin, P., Game Theory and Strategy, Mathematical Association of America, Washington, 1993.

Taylor, A. and W. Zwicker, Simple Games, Princeton U. Press, 1999.

Tijs, S. Introduction to Game Theory, Hindustan Book Agency, New Delhi, 2004. (Distributed through the American Mathematical Society.)

Weintraub, E., (ed.), Toward A History of Game Theory, Duke U. Press, Durham, 1992.

Young, H., (ed.), Fair Allocation, American Mathematical Society, Providence, 1985.

Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society's MathSciNet can be used to get additional bibliographic information and reviews of some these materials.

 

Joseph Malkevitch
York College (CUNY)
Email Joseph Malkevitch