Three freelancers, a designer, a programmer, and a salesperson, are thinking of working together. Each of them alone earns nothing worth mentioning from the kind of project in question. The designer and the programmer together could earn \(4\) (in thousands of euros a month); the designer and the salesperson \(3\) ; the programmer and the salesperson \(2\) . All three together could earn \(6\) . They can sign a contract, and a signed contract will be honoured. Should all three team up, and if they do, how should the \(6\) be divided?
This is a different kind of question from any asked so far. In the first nine chapters agreements were worthless unless they were self-enforcing, and the analysis turned on what each player would do alone. Here agreements bind, so the interesting unit is the group: what a set of players can achieve together and can therefore insist on. The description of the situation changes accordingly. There are no strategies and no order of moves; there is only a list of what each possible coalition is worth. Two questions are then natural. Which divisions of the total are stable, in the sense that no group could do better by walking away? And which division is fair, in the sense of rewarding each player for what that player contributes? The two questions have different answers, the core and the Shapley value, and this chapter develops both. It then looks back over the whole book and asks, for a given situation, which of its models to reach for.
10.1 Games in coalitional form
Definition 10.1 (coalitional game). A coalitional game with transferable utility is a pair \((N,v)\) , where \(N=\{1,\dots,n\}\) is the set of players and \(v\) assigns to every subset \(S\subseteq N\) , called a coalition, a real number \(v(S)\) , its worth, with \(v(\emptyset)=0\) . The function \(v\) is the characteristic function. The game is superadditive if \(v(S\cup T)\ge v(S)+v(T)\) whenever \(S\) and \(T\) are disjoint.
The worth \(v(S)\) is the total payoff that the members of \(S\) can secure by cooperating among themselves, whatever the players outside \(S\) do, and “transferable utility” means that this total can be divided among the members in any way, as money can. Superadditivity says that two disjoint groups can do at least as well together as apart, which holds whenever merging leaves them free to go on doing what they did separately. In a superadditive game the full coalition \(N\) , the grand coalition, creates the largest total, and the question is how to divide \(v(N)\) .
Definition 10.2 (allocations). An allocation is a vector \(x=(x_1,\dots,x_n)\) ; for a coalition \(S\) write \(x(S)=\sum_{i\in S}x_i\) . An allocation is efficient if \(x(N)=v(N)\) and individually rational if \(x_i\ge v(\{i\})\) for every \(i\) . An efficient and individually rational allocation is an imputation.
Example 10.1: The freelancers as a coalitional game
Number the designer, programmer, and salesperson \(1\) , \(2\) , \(3\) . Writing \(v(12)\) for \(v(\{1,2\})\) and so on,
The game is superadditive: a pair is worth more than its two members separately, and \(v(123)=6\) exceeds \(v(12)+v(3)=4\) , \(v(13)+v(2)=3\) , and \(v(23)+v(1)=2\) . So all three should work together. The imputations are the vectors with \(x_1+x_2+x_3=6\) and \(x_i\ge 0\) : a triangle with corners \((6,0,0)\) , \((0,6,0)\) , and \((0,0,6)\) . Equal division \((2,2,2)\) is an imputation. Is it one the freelancers would accept? The designer and the programmer receive \(4\) between them under it, exactly what they could earn as a pair, so they have no reason to object. But consider \((1,2,3)\) , which rewards the salesperson most. The designer and the programmer receive \(3\) between them and could earn \(4\) without the salesperson. They would refuse.
10.2 The core
Definition 10.3 (core). A coalition \(S\) blocks an allocation \(x\) if \(v(S)>x(S)\) : its members can obtain more in total by themselves than \(x\) gives them. The core of \((N,v)\) is the set of efficient allocations that no coalition blocks:
If a coalition blocks \(x\) , its members can divide \(v(S)\) so that each of them gets more than under \(x\) ; that is what transferable utility allows. An allocation in the core is immune to every such objection, by individuals, by pairs, and by any larger group. The core plays the role in this theory that Nash equilibrium plays in the noncooperative one, with deviations by coalitions in place of deviations by individuals. Being defined by finitely many linear inequalities and one equation, the core is a convex polytope, possibly empty.
Example 10.2: The core of the freelancers’ game
The conditions are \(x_1+x_2+x_3=6\) , \(x_i\ge 0\) , and
Using the equation, each pair condition becomes an upper limit on the third player: \(x_3\le 2\) , \(x_2\le 3\) , and \(x_1\le 4\) . A player cannot receive more than the amount by which the grand coalition exceeds what the other two could earn without that player. So the core is
It is a quadrilateral inside the triangle of imputations, with corners \((4,2,0)\) , \((4,0,2)\) , \((1,3,2)\) , and \((3,3,0)\) ; each corner is where two of the limits bind. Equal division \((2,2,2)\) satisfies all the conditions and lies in the core. The allocation \((1,2,3)\) violates \(x_3\le 2\) , which is the designer’s and programmer’s objection in another form.
Figure 10.1 shows the triangle of imputations and the three lines that cut the core out of it. The core is large in this game: the stability requirement leaves the division far from determined. In other games it leaves nothing.
Example 10.3: A game with an empty core
Three players divide \(1\) by majority rule: any two of them can take the whole amount. So \(v(S)=1\) if \(S\) has two or three members and \(v(S)=0\) otherwise. A core allocation would need \(x_1+x_2\ge 1\) , \(x_1+x_3\ge 1\) , and \(x_2+x_3\ge 1\) . Adding the three gives \(2(x_1+x_2+x_3)\ge 3\) , while efficiency requires \(x_1+x_2+x_3=1\) . The conditions are incompatible and the core is empty. Whatever division is proposed, some pair gets less than \(1\) between them and can do better by excluding the third: if the division is \((\tfrac13,\tfrac13,\tfrac13)\) , players 1 and 2 can take \(\tfrac12\) each; against that, players 2 and 3 can agree on \((0,\tfrac23,\tfrac13)\) ; and so on without end. Majority rule over a pure division is inherently unstable.
The argument that showed emptiness, adding up the pair constraints with suitable weights, is the general test.
Theorem 10.4 (Bondareva–Shapley). Call a family of weights \(\lambda_S\ge 0\) , one for each nonempty coalition \(S\) , balanced if \(\sum_{S\ni i}\lambda_S=1\) for every player \(i\) . The core of \((N,v)\) is nonempty if and only if
Proof. Consider the linear program: maximize \(\sum_S\lambda_Sv(S)\) subject to \(\sum_{S\ni i}\lambda_S=1\) for each \(i\) and \(\lambda\ge 0\) . Written as a minimization of \(-\sum_S\lambda_Sv(S)\) it is in the standard form used in the proof of Theorem 4.4, with one equation per player. It is feasible, since \(\lambda_N=1\) with all other weights zero is balanced, and its feasible set is closed and bounded, since every weight lies between \(0\) and \(1\) ; so it has an optimal solution. Its dual has one unrestricted variable \(y_i\) per player and one constraint per coalition, \(\sum_{i\in S}y_i\le-v(S)\) ; putting \(x=-y\) , the dual is: minimize \(x(N)\) subject to \(x(S)\ge v(S)\) for every nonempty \(S\) . By strong duality for linear programs, the result imported in Chapter 4, the dual has an optimal solution and
Every \(x\) feasible for the minimization has \(x(N)\ge v(N)\) , because \(S=N\) is one of the constraints. The core is the set of feasible \(x\) with \(x(N)=v(N)\) . So the core is nonempty exactly when the minimum equals \(v(N)\) , that is, when the maximum is at most \(v(N)\) , which is the displayed condition.
A balanced family describes a way for each player to split one unit of time among coalitions, with every coalition \(S\) operating for the fraction \(\lambda_S\) of the time agreed by all its members. The theorem says that the core is nonempty exactly when no such time-sharing scheme produces more than the grand coalition does. In the majority game the family \(\lambda_{12}=\lambda_{13}=\lambda_{23}=\tfrac12\) is balanced and gives \(\tfrac32>1\) . In the freelancers’ game the same family gives \(\tfrac12(4+3+2)=4.5\le 6\) , and one can check that it is the most demanding one.
There is a large class of games in which the core is guaranteed to be nonempty: those in which a player’s contribution grows with the size of the coalition joined.
Definition 10.5 (convex game). A coalitional game is convex if for every player \(i\) and all coalitions \(S\subseteq T\subseteq N\setminus\{i\}\) ,
For an ordering \(\pi\) of the players, the marginal vector \(m^\pi\) pays each player the amount by which that player raises the worth of the coalition of predecessors: \(m^\pi_i=v(P_i^\pi\cup\{i\})-v(P_i^\pi)\) , where \(P_i^\pi\) is the set of players who come before \(i\) in \(\pi\) .
Theorem 10.6 (core of a convex game). In a convex game every marginal vector belongs to the core. In particular the core is nonempty.
Proof. Fix an ordering and write \(m\) for its marginal vector. Summing \(m_i\) over all players in order, the terms telescope to \(v(N)-v(\emptyset)=v(N)\) , so \(m\) is efficient. Let \(S\) be any coalition and list its members in the order in which they appear: \(i_1,i_2,\dots,i_k\) . The set \(\{i_1,\dots,i_{j-1}\}\) of earlier members of \(S\) is contained in the set \(P_{i_j}\) of all predecessors of \(i_j\) , so by convexity
Summing over \(j=1,\dots,k\) , the right-hand sides telescope to \(v(S)\) . Hence \(m(S)\ge v(S)\) .
The freelancers’ game is not convex: the programmer adds \(v(12)-v(1)=4\) when joining the designer alone, but only \(v(123)-v(13)=3\) when joining the designer and the salesperson together. Accordingly not all of its marginal vectors lie in the core: the ordering \(1,2,3\) gives \((0,4,2)\) , which violates \(x_2\le 3\) . Its core is nonempty all the same; convexity is sufficient, not necessary.
10.3 The Shapley value
The core, when it is nonempty, is usually a set, and when it is empty it offers nothing. A different approach asks for a single allocation, defined for every game, that divides \(v(N)\) according to contributions. The difficulty is that a player’s contribution depends on who is already there. Shapley’s answer is to average over all the orders in which the coalition might be assembled.
Definition 10.7 (Shapley value). The Shapley value of the game \((N,v)\) is the allocation \(\varphi(v)\) that gives each player the average of that player’s marginal contribution over all \(n!\) orderings of the players:
The second expression groups the orderings by the set \(S\) of predecessors of \(i\) : there are \(|S|!\) ways to order the predecessors and \((n-|S|-1)!\) ways to order the players who come after \(i\) .
Example 10.4: The freelancers’ Shapley value
There are \(3!=6\) orderings. For each, the three marginal contributions are:
For instance, in the ordering \(2,3,1\) the programmer arrives first and adds \(v(2)=0\) , the salesperson adds \(v(23)-v(2)=2\) , and the designer adds \(v(123)-v(23)=4\) . Each row sums to \(6\) . Dividing the column sums by \(6\) ,
The designer, who is part of the two most valuable pairs, receives the most. The allocation satisfies \(x_1\le 4\) , \(x_2\le 3\) , and \(x_3\le 2\) , so in this game the Shapley value lies in the core. Four of the six rows are core allocations and two are not, and their average is.
What singles out this particular average? Shapley showed that it is the only rule with four properties that are hard to object to.
Theorem 10.8 (Shapley). Fix the player set \(N\) . The Shapley value is the unique function \(\varphi\) from games on \(N\) to allocations that satisfies the following four axioms. Efficiency: \(\sum_i\varphi_i(v)=v(N)\) . Symmetry: if \(v(S\cup\{i\})=v(S\cup\{j\})\) for every \(S\) containing neither \(i\) nor \(j\) , then \(\varphi_i(v)=\varphi_j(v)\) . Null player: if \(v(S\cup\{i\})=v(S)\) for every \(S\) , then \(\varphi_i(v)=0\) . Additivity: \(\varphi(v+w)=\varphi(v)+\varphi(w)\) for any two games \(v,w\) on \(N\) .
Proof. The Shapley value satisfies the axioms. Each marginal vector is efficient, by the telescoping sum in the proof of Theorem 10.6, so their average is. If \(i\) and \(j\) are interchangeable as in the symmetry axiom, exchanging their positions is a one-to-one map on orderings under which the marginal contribution of \(i\) in one ordering equals that of \(j\) in the other; so the averages agree. A null player’s marginal contribution is zero in every ordering. And marginal contributions are linear in \(v\) .
Uniqueness. For a nonempty coalition \(T\) define the unanimity game \(u_T\) by \(u_T(S)=1\) if \(T\subseteq S\) and \(u_T(S)=0\) otherwise. Let \(\varphi\) satisfy the axioms and let \(c\) be a real number. In the game \(c\,u_T\) every player outside \(T\) is a null player and gets \(0\) ; the players in \(T\) are interchangeable and get equal amounts; by efficiency these sum to \(c\) . So \(\varphi_i(c\,u_T)=c/|T|\) for \(i\in T\) and \(0\) otherwise: the axioms determine \(\varphi\) on multiples of unanimity games.
The games on \(N\) form a vector space of dimension \(2^n-1\) , one coordinate for each nonempty coalition, and there are \(2^n-1\) unanimity games. They are linearly independent: if \(\sum_Tc_Tu_T=0\) with some \(c_T\ne 0\) , choose \(T_0\) minimal among the coalitions with \(c_{T_0}\ne 0\) and evaluate at \(S=T_0\) ; only the terms with \(T\subseteq T_0\) contribute, and by minimality that leaves \(c_{T_0}=0\) , a contradiction. So they form a basis, and every game can be written as \(v=\sum_Tc_Tu_T\) . Move the terms with negative coefficients to the other side:
Applying additivity to both sides expresses \(\varphi(v)\) through the values of multiples of unanimity games, which are already determined. So at most one function satisfies the axioms, and the Shapley value is one.
The axioms are about fairness, not stability, and nothing in them refers to blocking. So the Shapley value may or may not be a core allocation.
Example 10.5: A fair division that is not stable
Player 1 owns a left glove; players 2 and 3 each own a right glove. A pair of gloves is worth \(1\) and single gloves are worthless. So \(v(12)=v(13)=v(123)=1\) and every other coalition is worth \(0\) .
The core. Efficiency requires \(x_1+x_2+x_3=1\) , and the pairs require \(x_1+x_2\ge 1\) and \(x_1+x_3\ge 1\) . The first gives \(x_3\le 0\) and the second \(x_2\le 0\) , so with \(x_i\ge 0\) the core is the single point \((1,0,0)\) . The owner of the scarce glove takes everything: each right-glove owner would accept any positive amount sooner than be left out, and the other one would undercut any better deal.
The Shapley value. Player 1 contributes \(1\) unless first in the ordering, and is first in \(2\) of the \(6\) orderings, so \(\varphi_1=\tfrac46=\tfrac23\) . By symmetry and efficiency, \(\varphi_2=\varphi_3=\tfrac16\) . Indeed player 2 contributes \(1\) only in the ordering \(1,2,3\) .
The Shapley value \((\tfrac23,\tfrac16,\tfrac16)\) is not in the core: players 1 and 3 receive \(\tfrac56\) between them and are worth \(1\) . The two solutions answer different questions. The core registers competition, which drives the payoff of the abundant side to zero. The Shapley value registers contribution, and a right glove does contribute in some orderings. By Theorem 10.6, and because the core is convex, the two cannot disagree in a convex game: there the Shapley value is an average of core allocations and so lies in the core.
One of the most used applications of the Shapley value needs no money at all.
Example 10.6: Voting power
Four shareholders own \(40\) , \(30\) , \(20\) , and \(10\) per cent of a company, and a motion passes with more than half of the shares. Define a game by \(v(S)=1\) if the members of \(S\) own at least \(51\) per cent and \(v(S)=0\) otherwise. A player’s marginal contribution in an ordering is \(1\) if that player’s arrival turns a losing coalition into a winning one, that is, if the player is pivotal, and \(0\) otherwise. The Shapley value is therefore the fraction of orderings in which each shareholder is pivotal.
Counting over the \(24\) orderings gives
For example, the smallest shareholder is pivotal only when the shares before him total exactly \(50\) , held by the second and third shareholders in either order with the largest coming last: \(2\) orderings. The shareholders with \(30\) and \(20\) per cent have exactly the same power, although one owns half as much again as the other, because they belong to exactly the same kinds of winning coalitions: each wins with the largest shareholder, and each needs the other two if the largest is against. Power in a voting body is a property of the winning coalitions, not of the weights. In a three-party parliament with \(49\) , \(48\) , and \(3\) seats, any two parties form a majority, and all three have the same power, \(\tfrac13\) .
Common mistake. Treating the Shapley value as a core allocation, or the core as a recipe for fairness. The glove game shows a Shapley value outside the core, and Example 10.3 shows a game with a Shapley value, \((\tfrac13,\tfrac13,\tfrac13)\) , and no core at all. A second mistake is computational: averaging the worths \(v(S)\) of the coalitions a player belongs to, in place of the marginal contributions \(v(S\cup\{i\})-v(S)\) . A quick check catches most errors: the Shapley value must sum to \(v(N)\) , interchangeable players must receive the same amount, and a player who adds nothing to any coalition must receive nothing.
10.4 Choosing the model
The book has presented two families of models. Noncooperative models specify who can do what and when, and predict behaviour by an equilibrium of individually optimal strategies. Cooperative models specify what groups can achieve and say which divisions are stable or fair, leaving the bargaining unmodelled. Neither is the more fundamental. A noncooperative model is the right tool when the procedure is known and commitments are not available; a cooperative one when binding agreements are possible and the procedure is fluid. The link between them is the characteristic function: given a strategic situation, \(v(S)\) can be defined as the largest total payoff that \(S\) can guarantee when its members coordinate and the others do their worst.
Within the noncooperative family the choice of solution concept follows from the features of the situation, and each concept refines the one before it for a reason that was demonstrated by an example.
| Feature of the situation | Model | Solution concept | First thing to check |
|---|---|---|---|
| One simultaneous choice, payoffs known | Strategic form (Chapters 1 to 3) | Dominance, then Nash equilibrium in pure or mixed strategies | Each player’s deviation inequalities; supports and indifference |
| Pure conflict between two players | Matrix game (Chapter 4) | Value and optimal strategies | A certificate: guarantee for one side, ceiling for the other |
| Sequential moves, all observed | Tree with perfect information (Chapter 5) | Backward induction | An action at every node, including unreached ones |
| Sequential moves, some simultaneous or repeated | Subgames, repeated game (Chapter 6) | Subgame-perfect equilibrium | One-shot deviations at every kind of history |
| Private information, one simultaneous move | Bayesian game (Chapter 7) | Bayes–Nash equilibrium | An action for every type; each type’s own beliefs |
| Private information, sequential moves | Signaling game (Chapter 8) | Perfect Bayesian equilibrium | Beliefs after every message, on and off the path |
| The rules themselves are to be chosen | Mechanism (Chapter 9) | Incentive-compatible direct mechanism | Monotone allocation; payments from the envelope formula |
| Binding agreements among groups | Coalitional game (Chapter 10) | Core; Shapley value | Every coalition’s constraint; the four axioms |
Using the table well means being suspicious of a first classification. The same market can call for several rows, depending on what one believes about timing, information, and commitment.
Example 10.7: One market, five analyses
Return for the last time to Arno and Bea, whose cafés earn \((6,6)\) at High prices, \((3,3)\) at Low prices, and \(8\) and \(1\) when one undercuts the other.
Prices set once, simultaneously. Low is strictly dominant (Chapter 1), and (Low, Low) is the unique Nash equilibrium (Chapter 2). Outcome \((3,3)\) .
Arno sets his price first and Bea sees it. By backward induction Bea chooses Low after either price, since Low is dominant for her; so Arno compares \(1\) from High with \(3\) from Low and chooses Low (Chapter 5). Commitment does not help, because Bea’s best reply does not depend on what she sees. Outcome \((3,3)\) .
Prices set every week, with no known end. By Example 6.4 the grim-trigger profile sustains (High, High) as a subgame-perfect equilibrium when \(\delta\ge 2/5\) . So do many other outcomes, and (Low, Low) for ever remains an equilibrium. Outcome \((6,6)\) is possible but not predicted.
Arno is unsure of Bea’s motives. Suppose that with probability \(\mu\) Bea is the friend of Example 1.2, for whom High is dominant. Low is still dominant for Arno, and in the unique Bayes–Nash equilibrium Arno and the ordinary Bea charge Low while the friendly Bea charges High (Chapter 7). Arno’s expected profit is \(8\mu+3(1-\mu)\) .
The owners can sign an enforceable agreement. Then the situation is a two-player coalitional game. Either owner alone can guarantee \(3\) by charging Low, and no more, so \(v(1)=v(2)=3\) ; together they can earn \(v(12)=6+6=12\) , the largest total in the table. The core consists of the divisions with \(x_1+x_2=12\) and \(x_1,x_2\ge 3\) . The Shapley value averages two orderings: \(\varphi_1=\tfrac12\bigl[3+(12-3)\bigr]=6\) , and likewise \(\varphi_2=6\) . Outcome \((6,6)\) , with the division pinned down by symmetry.
Five models of one market give outcomes ranging from \((3,3)\) to \((6,6)\) . None of the five is the correct analysis of “the” café game, because there is no such game until the timing, the information, and the possibilities for commitment have been specified. Each of those specifications is a claim about the world that can be right or wrong. The mathematics of this book begins only after they have been made, and it is exact from that point on; the judgement that precedes it is the part that no theorem supplies.
Exercises
-
Three players have \(v(1)=1\) , \(v(2)=v(3)=0\) , \(v(12)=3\) , \(v(13)=2\) , \(v(23)=2\) , and \(v(123)=5\) . Check whether the game is superadditive, writing out every inequality, and describe the set of imputations by its corner points.
Answer
Pairs against their members: \(v(12)=3\ge 1+0\) , \(v(13)=2\ge 1+0\) , \(v(23)=2\ge 0+0\) . The grand coalition against every partition: \(5\ge v(12)+v(3)=3\) , \(5\ge v(13)+v(2)=2\) , \(5\ge v(23)+v(1)=3\) , and \(5\ge 1+0+0\) . The game is superadditive. The imputations satisfy \(x_1\ge 1\) , \(x_2\ge 0\) , \(x_3\ge 0\) , and \(x_1+x_2+x_3=5\) : a triangle with corners \((5,0,0)\) , \((1,4,0)\) , and \((1,0,4)\) .
-
For the three-player game with \(v(i)=0\) for each player, \(v(12)=5\) , \(v(13)=4\) , \(v(23)=3\) , and \(v(123)=8\) , write the core as a system of upper and lower limits on \(x_1,x_2,x_3\) , find its corner points, and decide whether \((3,3,2)\) is in the core.
Solution
The core conditions are \(x_1+x_2+x_3=8\) , \(x_i\ge 0\) , \(x_1+x_2\ge 5\) , \(x_1+x_3\ge 4\) , and \(x_2+x_3\ge 3\) . Subtracting each pair condition from the equation turns it into an upper limit on the remaining player: \(x_3\le 3\) , \(x_2\le 4\) , and \(x_1\le 5\) . So the core is
\[ \{x:\ x_1+x_2+x_3=8,\ \ 0\le x_1\le 5,\ \ 0\le x_2\le 4,\ \ 0\le x_3\le 3\}. \]A corner is a point of this set at which two of the six limits hold with equality; the equation then gives the third coordinate. Trying the pairs: \(x_1=5\) and \(x_3=0\) give \((5,3,0)\) ; \(x_1=5\) and \(x_2=0\) give \((5,0,3)\) ; \(x_2=4\) and \(x_3=3\) give \((1,4,3)\) ; \(x_2=4\) and \(x_3=0\) give \((4,4,0)\) . The remaining pairs give points that violate some limit: for instance \(x_1=5\) and \(x_2=4\) would need \(x_3=-1\) , and \(x_1=5\) and \(x_3=3\) give \(x_2=0\) , which is the corner \((5,0,3)\) again. The corner points are \((5,3,0)\) , \((5,0,3)\) , \((1,4,3)\) , and \((4,4,0)\) .
The allocation \((3,3,2)\) sums to \(8\) and respects all three upper limits, so it is in the core: the pairs receive \(6\) , \(5\) , and \(5\) against worths of \(5\) , \(4\) , and \(3\) .
-
Three players have \(v(i)=0\) , every pair is worth \(5\) , and \(v(123)=7\) . Use a balanced family of weights to prove that the core is empty, and exhibit a blocking coalition for the allocation \((\tfrac73,\tfrac73,\tfrac73)\) .
Answer
The weights \(\lambda_{12}=\lambda_{13}=\lambda_{23}=\tfrac12\) are balanced, since each player belongs to two pairs, and give \(\tfrac12(5+5+5)=7.5>7=v(123)\) . By Theorem 10.4 the core is empty. Under \((\tfrac73,\tfrac73,\tfrac73)\) any pair receives \(\tfrac{14}{3}<5\) and blocks.
-
In the freelancers’ game replace \(v(123)=6\) by a number \(c\ge 4\) , keeping the pairs at \(4\) , \(3\) , and \(2\) . Find the smallest \(c\) for which the core is nonempty, and the core at that value of \(c\) .
Solution
With \(v(123)=c\) , the pair conditions become upper limits: \(x_3\le c-4\) , \(x_2\le c-3\) , and \(x_1\le c-2\) . For the core to be nonempty these must be compatible with \(x_1+x_2+x_3=c\) . Adding the three limits gives \(c\le 3c-9\) , that is, \(c\ge 4.5\) . Conversely, if \(c\ge 4.5\) and we start from the limits and reduce coordinates until the sum is \(c\) , all coordinates stay nonnegative, since \(c-4\ge 0.5\) . Equivalently, by Theorem 10.4 with the weights \(\tfrac12\) on each pair, a necessary condition is \(\tfrac12(4+3+2)=4.5\le c\) . So the smallest value is \(c=4.5\) .
At \(c=4.5\) the sum of the three upper limits equals \(c\) exactly, so each limit must hold with equality: \(x_1=2.5\) , \(x_2=1.5\) , \(x_3=0.5\) . The core is the single point \((2.5,\ 1.5,\ 0.5)\) . At that point every pair receives exactly its worth; the grand coalition has nothing to spare. For \(c<4.5\) the freelancers would do better to work in rotating pairs than all together, and no division of \(c\) can keep all three pairs content.
-
Compute the Shapley value of the game in Exercise 2 by listing the marginal contributions in all six orderings, confirm that the result is efficient, and decide whether it is in the core.
Solution
The marginal contributions, with \(v(12)=5\) , \(v(13)=4\) , \(v(23)=3\) , \(v(123)=8\) :
\[ \begin{array}{c|ccc} \text{ordering} & \text{player 1} & \text{player 2} & \text{player 3}\\ \hline 1,2,3 & 0 & 5 & 3\\ 1,3,2 & 0 & 4 & 4\\ 2,1,3 & 5 & 0 & 3\\ 2,3,1 & 5 & 0 & 3\\ 3,1,2 & 4 & 4 & 0\\ 3,2,1 & 5 & 3 & 0\\ \hline \text{sum} & 19 & 16 & 13 \end{array} \]Each row sums to \(8\) . Dividing by \(6\) , the Shapley value is \(\bigl(\tfrac{19}{6},\tfrac{16}{6},\tfrac{13}{6}\bigr)\) , about \((3.17,2.67,2.17)\) . It is efficient: \(19+16+13=48=6\cdot 8\) . No two players are interchangeable and none is a null player, so the other two checks impose nothing here.
For the core, use the limits of Exercise 2: \(\tfrac{19}{6}\le 5\) , \(\tfrac{16}{6}\le 4\) , and \(\tfrac{13}{6}\le 3\) , with all coordinates nonnegative. The Shapley value is in the core.
-
Prove that the core of any coalitional game is a convex set: if \(x\) and \(y\) are in the core, so is \(\lambda x+(1-\lambda)y\) for every \(\lambda\in[0,1]\) . Then prove that it is bounded.
Hint
Each core condition is a linear inequality or equation in \(x\) , and a linear inequality satisfied by \(x\) and by \(y\) is satisfied by every weighted average of them. For boundedness combine \(x_i\ge v(\{i\})\) with \(x_i=v(N)-x(N\setminus\{i\})\le v(N)-v(N\setminus\{i\})\) .
-
Let \(i\) be a null player in a game \((N,v)\) , so \(v(S\cup\{i\})=v(S)\) for all \(S\) . Prove that every core allocation gives player \(i\) exactly \(0\) .
Solution
Let \(x\) be a core allocation and let \(i\) be a null player. Taking \(S=\emptyset\) in the definition of a null player gives \(v(\{i\})=v(\emptyset)=0\) , and taking \(S=N\setminus\{i\}\) gives \(v(N)=v(N\setminus\{i\})\) .
The core condition for the coalition \(\{i\}\) says \(x_i\ge v(\{i\})=0\) .
The core condition for the coalition \(N\setminus\{i\}\) says \(x(N\setminus\{i\})\ge v(N\setminus\{i\})=v(N)\) . By efficiency \(x(N\setminus\{i\})=v(N)-x_i\) , so \(v(N)-x_i\ge v(N)\) , that is, \(x_i\le 0\) .
Hence \(x_i=0\) . The others could block any allocation that paid a null player a positive amount, since they lose nothing by leaving that player out. On this point stability and the null-player axiom of the Shapley value agree.
-
For the unanimity game \(u_T\) on \(N=\{1,2,3,4\}\) with \(T=\{1,2\}\) , find the Shapley value and describe the core.
Answer
Players 3 and 4 are null and get \(0\) ; players 1 and 2 are interchangeable and share \(1\) : \(\varphi=(\tfrac12,\tfrac12,0,0)\) . The core is \(\{(t,1-t,0,0):0\le t\le 1\}\) : by Exercise 7 the null players get \(0\) , and every remaining condition reduces to \(x_1,x_2\ge 0\) and \(x_1+x_2=1\) .
-
Players 1 and 2 each own a left glove and players 3, 4, and 5 each own a right glove; \(v(S)\) is the number of pairs that the members of \(S\) can form. Find the core. Then compute the Shapley value of a left-glove owner by counting, for each possible number of predecessors, the orderings in which that player is needed, and deduce the Shapley value of a right-glove owner.
Solution
The core. Here \(v(N)=2\) , since there are two left gloves. Let \(x\) be in the core. For a left owner \(l\) and a right owner \(r\) , \(x_l+x_r\ge 1\) . The coalition of both left owners and two right owners, leaving out the right owner \(r\) , is worth \(2\) , so it must receive at least \(2\) ; by efficiency it receives \(2-x_r\) ; hence \(x_r\le 0\) , and so \(x_r=0\) for every right owner. Then \(x_l\ge 1\) for each left owner, and efficiency forces \(x_1=x_2=1\) . The core is the single point \((1,1,0,0,0)\) : the scarce side takes everything.
The Shapley value of a left owner, say player 1. Player 1’s arrival adds a pair exactly when the predecessors include more right gloves than left gloves. The number \(s\) of predecessors is equally likely to be \(0,1,2,3,4\) , and given \(s\) all sets of that size from the other four players are equally likely.
With \(s=0\) there is no right glove waiting: probability \(0\) . With \(s=1\) , the predecessor is a right owner in \(3\) of \(4\) cases: \(\tfrac34\) . With \(s=2\) , the predecessors are two right owners in \(3\) of the \(6\) pairs; in the other \(3\) they are the other left owner and one right owner, whose gloves are already paired: \(\tfrac12\) . With \(s=3\) the predecessors contain at least two right gloves and at most one left: probability \(1\) . With \(s=4\) likewise: \(1\) .
So \(\varphi_1=\tfrac15\bigl(0+\tfrac34+\tfrac12+1+1\bigr)=\tfrac{13}{20}\) , and by symmetry \(\varphi_2=\tfrac{13}{20}\) . By efficiency the three right owners share \(2-\tfrac{26}{20}=\tfrac{14}{20}\) equally, so each gets \(\tfrac{7}{30}\) .
The Shapley value \((\tfrac{13}{20},\tfrac{13}{20},\tfrac{7}{30},\tfrac{7}{30},\tfrac{7}{30})\) is far from the core point: it gives the abundant side about a third of the total.
-
In a committee of four, the members have \(3\) , \(2\) , \(2\) , and \(1\) votes and a motion needs at least \(5\) votes. List the minimal winning coalitions, compute the Shapley value, and compare each member’s power with that member’s share of the votes.
Solution
The total is \(8\) votes and the quota is \(5\) . A coalition wins if its votes sum to at least \(5\) . The minimal winning coalitions, those with no winning proper subset, are \(\{1,2\}\) , \(\{1,3\}\) , and \(\{2,3,4\}\) ; \(\{2,3\}\) has only \(4\) votes, and \(\{1,4\}\) has \(4\) .
Pivots. Member 4 is pivotal only when the predecessors have exactly \(4\) votes and adding one vote wins: the predecessors must be \(\{2,3\}\) (the set \(\{1\}\) has \(3\) votes, and \(\{1,4\}\) is not available). That is \(2\) orderings of the \(24\) . Members 2 and 3 are interchangeable. Member 1 is pivotal when the predecessors have \(2\) , \(3\) , or \(4\) votes: \(\{2\}\) , \(\{3\}\) , \(\{2,4\}\) , \(\{3,4\}\) , \(\{2,3\}\) . Counting orderings: a single predecessor leaves \(2!\) arrangements of the two members who follow, so \(2+2\) ; a pair of predecessors can be ordered in \(2!\) ways with one member following, so \(2+2+2\) . In all \(10\) . The remaining \(24-10-2=12\) pivots are shared equally by members 2 and 3.
The Shapley value is \(\bigl(\tfrac{5}{12},\tfrac14,\tfrac14,\tfrac{1}{12}\bigr)\) , against vote shares of \(\tfrac38,\tfrac14,\tfrac14,\tfrac18\) . The largest member has more power than votes (\(0.417\) against \(0.375\) ) and the smallest less (\(0.083\) against \(0.125\) ); the member with one vote matters only in the single coalition that opposes the largest member.
-
Three airlines need runways costing \(6\) , \(12\) , and \(24\) to build; a runway that serves one airline serves any airline with a smaller requirement, so a coalition’s cost is the largest requirement among its members. Apply the Shapley formula to this cost function to divide the cost \(24\) of the single long runway, and interpret the result as a rule for sharing each segment of the runway.
Solution
The cost function is \(c(S)=\max\) of the requirements in \(S\) : \(c(1)=6\) , \(c(2)=12\) , \(c(3)=24\) , \(c(12)=12\) , \(c(13)=c(23)=c(123)=24\) . Apply Definition 10.7 to \(c\) . An airline’s marginal cost in an ordering is the amount by which its requirement exceeds the largest requirement among its predecessors, or \(0\) .
Airline 1 adds \(6\) only when it comes first, in \(2\) of the \(6\) orderings: \(\varphi_1=\tfrac{12}{6}=2\) .
Airline 2 adds \(12\) when first (\(2\) orderings), and \(6\) when preceded by airline 1 only (the ordering \(1,2,3\) ); otherwise it follows airline 3 and adds \(0\) : \(\varphi_2=\tfrac{24+6}{6}=5\) .
Airline 3 gets the rest: \(\varphi_3=24-2-5=17\) . Directly: it adds \(24\) when first (\(2\) orderings), \(18\) after airline 1 alone, \(12\) after airline 2 alone or after both (\(1+2\) orderings): \(\tfrac{48+18+36}{6}=17\) .
The cost shares are \((2,5,17)\) . They have a simple reading. Cut the runway into three segments: the first \(6\) , used by all three airlines; the next \(6\) , used by airlines 2 and 3; the last \(12\) , used by airline 3 alone. Share each segment’s cost equally among its users: \(\tfrac63=2\) each for the first, \(\tfrac62=3\) each for the second, \(12\) for the third. That gives \(2\) , \(2+3=5\) , and \(2+3+12=17\) .
-
A student computes a “Shapley value” for the freelancers’ game by giving each player the average worth of the coalitions containing that player: for player 1, the average of \(v(1)\) , \(v(12)\) , \(v(13)\) , \(v(123)\) . Compute the student’s three numbers, show that they violate efficiency, and state what should have been averaged.
Hint
The student’s numbers are \(\tfrac14(0+4+3+6)=\tfrac{13}{4}\) , \(\tfrac14(0+4+2+6)=3\) , and \(\tfrac14(0+3+2+6)=\tfrac{11}{4}\) , which sum to \(9\) , not \(6\) . The worth of a coalition is not the player’s contribution to it. Average the differences \(v(S\cup\{i\})-v(S)\) , with the weights of Definition 10.7.
-
On \(N=\{1,2,3\}\) let \(v(S)=|S|^2\) . Show that the game is convex, list the marginal vectors, verify that each is in the core, and find the Shapley value without further computation.
Answer
A player joining a coalition of size \(s\) adds \((s+1)^2-s^2=2s+1\) , which increases with \(s\) , so the game is convex. The marginal vectors are the six arrangements of \((1,3,5)\) . Each is in the core: singles get at least \(1\) , pairs at least \(1+3=4=v\) of a pair, and the total is \(9\) . The players are interchangeable, so the Shapley value is \((3,3,3)\) .
-
Prove that Definition 10.5 is equivalent to the condition \(v(S\cup T)+v(S\cap T)\ge v(S)+v(T)\) for all coalitions \(S,T\) .
Hint
From the set condition to Definition 10.5: apply it to the coalitions \(S\cup\{i\}\) and \(T\) , with \(S\subseteq T\) and \(i\notin T\) . For the converse, write \(S\setminus T=\{i_1,\dots,i_k\}\) and add the players one at a time, first to \(S\cap T\) and then to \(T\) ; Definition 10.5 compares the two marginal contributions at each step, and the sums telescope.
-
Treat the Cournot duopoly of Example 2.3 as a two-player coalitional game in which profit can be transferred: let \(v(i)\) be the profit firm \(i\) can guarantee whatever the rival produces, and \(v(12)\) the largest joint profit. Find \(v\) , the core, and the Shapley value, and say whether the Cournot equilibrium profits \((16,16)\) form a core allocation.
Solution
Singletons. Whatever firm \(i\) produces, the rival can produce so much that the price falls to the unit cost or below; then firm \(i\) earns at most \(0\) . By producing nothing firm \(i\) gets exactly \(0\) . So the most that firm \(i\) can guarantee is \(v(i)=0\) .
The pair. Together the firms can act as a monopolist: total output \(6\) , price \(8\) , profit \(36\) . So \(v(12)=36\) .
Core and Shapley value. The core is \(\{(x_1,x_2):x_1+x_2=36,\ x_1,x_2\ge 0\}\) . The Shapley value averages the two orderings: \(\varphi_1=\tfrac12\bigl[0+(36-0)\bigr]=18\) , and likewise for firm 2, giving \((18,18)\) .
The Cournot equilibrium. The profits \((16,16)\) sum to \(32<36=v(12)\) , so the pair blocks: the equilibrium is not efficient and not a core allocation. This is the gap between Chapter 2 and binding agreements. Note how pessimistic \(v(i)=0\) is: it assumes the rival would flood the market, which would hurt the rival too. The characteristic function records what a coalition can guarantee, not what it can reasonably expect, and the Cournot profit \(16\) plays no part in it.
-
For each situation name the model and the solution concept you would use and the first thing you would check, without solving: (a) two bidders submit sealed bids for a contract whose cost to each is private; (b) a manufacturer chooses a warranty length before consumers decide whether to buy, and only the manufacturer knows the product’s reliability; (c) four municipalities can build one joint waste plant and must split its cost; (d) two airlines set fares every day on the same route; (e) a goalkeeper and a striker in a penalty shoot-out.
Hint
(a) Private information and one simultaneous move: a Bayesian game, as in the auctions of Chapter 9; check each type’s bid against the rival’s bidding function. (b) An informed party moves first and is observed: a signaling game; check beliefs after every warranty length. (c) Binding cost-sharing: a coalitional cost game; check every coalition’s stand-alone cost. (d) Repeated simultaneous moves: subgame-perfect equilibrium; check one-shot deviations on and off the path. (e) Pure conflict: a matrix game; produce a certificate.
-
Player 1 has a veto: \(v(S)=1\) if \(S\) contains player 1 and at least one other of the three players, and \(v(S)=0\) otherwise. Find the core and the Shapley value, and name the game of this chapter that has the same characteristic function.
Answer
\(v(12)=v(13)=v(123)=1\) and all other coalitions are worth \(0\) . This is exactly the glove game of Example 10.5, so the core is \(\{(1,0,0)\}\) and the Shapley value is \((\tfrac23,\tfrac16,\tfrac16)\) .
-
Two players divide one unit, so \(v(1)=v(2)=0\) and \(v(12)=1\) . Find the core and the Shapley value. Then locate in the core the subgame-perfect outcomes of the two-period and three-period bargaining games of Exercise 14 of Chapter 6Chapter 6, and show that the proposer’s share in the three-period game is at least \(\tfrac34\) for every \(\delta\) .
Answer
The core is every division \((t,1-t)\) with \(0\le t\le 1\) , and the Shapley value is \((\tfrac12,\tfrac12)\) . The two-period outcome \((1-\delta,\delta)\) and the three-period outcome \((1-\delta+\delta^2,\ \delta-\delta^2)\) are both in the core. The function \(1-\delta+\delta^2\) has derivative \(2\delta-1\) and its minimum, at \(\delta=\tfrac12\) , is \(\tfrac34\) . A specific bargaining procedure selects one point of the core, and which point depends on the procedure.