-
Find all Nash equilibria, pure and mixed, of the game \(\begin{array}{c|cc}& L & R\\\hline T&(3,2)&(0,0)\\ B&(0,0)&(1,4)\end{array}\) , and compute both players’ payoffs in each. Which equilibrium gives both players less than they get in either of the others?
Solution
Pure equilibria. Player 1’s best response to \(L\) is \(T\) (\(3>0\) ) and to \(R\) is \(B\) (\(1>0\) ). Player 2’s best response to \(T\) is \(L\) (\(2>0\) ) and to \(B\) is \(R\) (\(4>0\) ). The mutual best responses are \((T,L)\) , with payoffs \((3,2)\) , and \((B,R)\) , with payoffs \((1,4)\) .
Mixed equilibrium. Let \(p\) be the probability of \(T\) and \(q\) the probability of \(L\) . Player 1 is indifferent when \(3q=1-q\) , so \(q=\tfrac14\) . Player 2 is indifferent when \(2p=4(1-p)\) , so \(p=\tfrac23\) . The payoffs are \(3q=\tfrac34\) for player 1 and \(2p=\tfrac43\) for player 2.
There are no equilibria in which exactly one player mixes, because each player has a strict best response to each pure strategy of the other. So there are three equilibria. The mixed one gives \((\tfrac34,\tfrac43)\) , which is worse for both players than \((3,2)\) and worse for both than \((1,4)\) : the players fail to coordinate with probability \(\tfrac23\cdot\tfrac34+\tfrac13\cdot\tfrac14=\tfrac{7}{12}\) .
-
Solve the matrix game \(\begin{pmatrix}3&-1&2\\-2&4&1\end{pmatrix}\) : find the value and optimal strategies for both players, say which column is not used, and give the certificate.
Solution
Let the maximizer play the first row with probability \(p\) . Against the three columns the payoffs are \(3p-2(1-p)=5p-2\) , \(-p+4(1-p)=4-5p\) , and \(2p+(1-p)=1+p\) . The first two cross at \(p=\tfrac35\) , where both equal \(1\) , and there the third equals \(\tfrac85>1\) . To the left of \(\tfrac35\) the first line is below \(1\) and to the right the second is, so the lower envelope peaks at \(p=\tfrac35\) : the value is \(1\) and \(x^\star=(\tfrac35,\tfrac25)\) .
The third column gives the maximizer more than the value, so the minimizer does not use it. With probability \(y\) on the first column and \(1-y\) on the second, the rows earn \(3y-(1-y)=4y-1\) and \(-2y+4(1-y)=4-6y\) , equal at \(y=\tfrac12\) . So \(y^\star=(\tfrac12,\tfrac12,0)\) .
Certificate: \((x^\star)^{\top}A=(1,\ 1,\ \tfrac85)\) , all at least \(1\) ; \(Ay^\star=(1,\ 1)\) , all at most \(1\) . Hence the value is \(1\) .
-
An investor chooses Keep, ending the game with payoffs \((1,1)\) , or Trust; after Trust a manager chooses Share, with payoffs \((2,2)\) , or Grab, with payoffs \((0,3)\) . Find the subgame-perfect equilibrium. Then suppose the game is played in every period with discount factor \(\delta\) , and find the values of \(\delta\) for which “Trust and Share as long as the manager has never grabbed; otherwise Keep, and Grab if trusted” is a subgame-perfect equilibrium, checking every kind of history.
Solution
One play. After Trust the manager compares \(2\) with \(3\) and grabs. The investor compares \(1\) from Keep with \(0\) from Trust and keeps. The subgame-perfect equilibrium is (Keep; Grab), with payoffs \((1,1)\) , although \((2,2)\) is available.
Repeated play. The stage game here is sequential, so use the one-shot deviation principle in the form noted after Theorem 6.6, with a deviation at a single decision node; the stage payoffs are bounded. Examine each kind of decision node and each player.
No grab so far, manager’s move after Trust: sharing yields \(2\) now and in every later period, \(2/(1-\delta)\) ; grabbing yields \(3\) now and then \(1\) for ever, \(3+\delta/(1-\delta)\) . Sharing is at least as good when \(2\ge 3(1-\delta)+\delta\) , that is, \(\delta\ge\tfrac12\) .
No grab so far, investor’s move: trusting yields \(2\) and keeping yields \(1\) today, with the same future either way, since the strategies react only to grabs. Trust is better.
After a grab, investor’s move: the manager will grab if trusted, so trusting yields \(0\) and keeping \(1\) , with the same future. Keep is better.
After a grab, manager’s move after Trust: grabbing yields \(3\) and sharing \(2\) , and the future is Keep for ever either way. Grab is better.
So the profile is a subgame-perfect equilibrium exactly when \(\delta\ge\tfrac12\) .
-
Two firms with unit cost \(1\) face the price \(10-Q\) . Compute the outputs and profits when quantities are chosen simultaneously; when firm 1 chooses first and firm 2 observes; and when the firms split the monopoly output. Then find the smallest discount factor at which the last outcome is sustained in the infinitely repeated simultaneous game by reversion to the first.
Answer
Simultaneous: \(q_1=q_2=3\) , price \(4\) , profit \(9\) each. Sequential: \(q_1=4.5\) , \(q_2=2.25\) , price \(3.25\) , profits \(10.125\) and \(5.0625\) . Splitting the monopoly output \(4.5\) : each produces \(2.25\) at price \(5.5\) and earns \(10.125\) . The best deviation from \(2.25\) is \(3.375\) , earning \(3.375^2=11.390625\) , so \(\delta_0=(11.390625-10.125)/(11.390625-9)=9/17\) , the same as in Example 6.6 because the threshold does not depend on \(a-c\) . As in that example, quantities are restricted to a bounded interval, here \([0,10]\) , so that Theorem 6.10 applies.
-
Two bidders have independent values uniform on \([0,2]\) . Find the equilibrium bidding function of the first-price auction and the seller’s expected revenue, and compare with the second-price auction. What reserve price maximizes expected revenue?
Answer
\(F(v)=v/2\) , so \(\beta(v)=v-\dfrac{1}{v/2}\displaystyle\int_0^v\tfrac y2\,dy=v-\tfrac v2=\tfrac v2\) . The higher of the two values has mean \(\tfrac43\) , so first-price revenue is \(\tfrac23\) ; the lower has mean \(\tfrac23\) , so second-price revenue is the same. The virtual value is \(2v-2\) and the optimal reserve is \(1\) .
-
A sender is a Friend with probability \(0.4\) and an Enemy otherwise, in the gift game of Exercise 12 of Chapter 8Chapter 8. For each claim say whether it describes a perfect Bayesian equilibrium, and if not, name the condition that fails: (a) the Friend gives, the Enemy does not, and the receiver accepts; (b) both give and the receiver accepts; (c) neither gives, and the receiver would reject, believing an unexpected giver to be an Enemy with probability \(0.9\) .
Answer
(a) Not an equilibrium: sender optimality fails, since the Enemy would gain \(1\) by giving too. (b) Not an equilibrium: receiver optimality fails, since after a gift the belief must be the prior \(0.4<\tfrac12\) and rejecting is better. (c) An equilibrium: the belief after the unsent message is free, \(0.1\le\tfrac12\) makes rejection optimal, and no type wants to give a gift that will be rejected.
-
Three players have \(v(1)=1\) , \(v(2)=v(3)=0\) , \(v(12)=4\) , \(v(13)=3\) , \(v(23)=1\) , and \(v(123)=6\) . Find the corner points of the core and the Shapley value, and decide whether the Shapley value is a core allocation.
Solution
The core conditions are \(x_1+x_2+x_3=6\) , \(x_1\ge 1\) , \(x_2\ge 0\) , \(x_3\ge 0\) , \(x_1+x_2\ge 4\) , \(x_1+x_3\ge 3\) , and \(x_2+x_3\ge 1\) . As upper limits: \(x_3\le 2\) , \(x_2\le 3\) , \(x_1\le 5\) . The corner points, where two limits bind, are \((1,3,2)\) , \((3,3,0)\) , \((4,0,2)\) , \((5,0,1)\) , and \((5,1,0)\) .
For the Shapley value use the second formula of Definition 10.7 with \(n=3\) : a player’s marginal contribution to the empty set and to the pair of the others each have weight \(\tfrac13\) , and to each single other player weight \(\tfrac16\) .
\(\varphi_1=\tfrac13(1)+\tfrac16(4-0)+\tfrac16(3-0)+\tfrac13(6-1)=\tfrac{2+4+3+10}{6}=\tfrac{19}{6}\) .
\(\varphi_2=\tfrac13(0)+\tfrac16(4-1)+\tfrac16(1-0)+\tfrac13(6-3)=\tfrac{3+1+6}{6}=\tfrac{10}{6}\) .
\(\varphi_3=\tfrac13(0)+\tfrac16(3-1)+\tfrac16(1-0)+\tfrac13(6-4)=\tfrac{2+1+4}{6}=\tfrac76\) .
The sum is \(\tfrac{36}{6}=6\) . Since \(1\le\tfrac{19}{6}\le 5\) , \(0\le\tfrac{10}{6}\le 3\) , and \(0\le\tfrac76\le 2\) , the Shapley value \((\tfrac{19}{6},\tfrac53,\tfrac76)\) is in the core.
-
For each claim say whether it is true or false and justify the answer in one or two sentences: (a) every finite game has a Nash equilibrium in pure strategies; (b) every finite game with perfect information has one; (c) in a zero-sum game all equilibria give the same payoffs; (d) in a signaling game Bayes’ rule determines the receiver’s belief after every message; (e) a coalitional game with a nonempty core has its Shapley value in the core.
Answer
(a) False: matching pennies has none; Theorem 4.7 promises a mixed equilibrium. (b) True: backward induction gives one, by Theorem 5.3. (c) True: by Corollary 4.5 every equilibrium gives the maximizer the value. (d) False: after a message no type sends, Bayes’ rule divides by zero and the belief is unrestricted. (e) False: in the glove game the core is \(\{(1,0,0)\}\) and the Shapley value is \((\tfrac23,\tfrac16,\tfrac16)\) .
-
Prove that in a finite two-player zero-sum game the set of Nash equilibria is a product \(X^\star\times Y^\star\) of two convex sets, and show by an example from this book that neither property holds in general for games that are not zero-sum.
Hint
By Corollary 4.5(a) the equilibria are exactly the pairs of a maximin strategy with a minimax strategy, so the set is \(X^\star\times Y^\star\) ; each factor is convex by Exercise 17 of Chapter 4Chapter 4 and its mirror image. In the seminar game (Algebra, Algebra) and (Biology, Biology) are equilibria while (Algebra, Biology) is not, and the midpoint of the two pure equilibria is not an equilibrium either.
-
Two arguments are offered about the repeated café game. First: “Both owners are rational and (High, High) is better for both than (Low, Low), so they will charge High.” Second: “By the folk theorem, patient owners will charge High.” Identify precisely what is wrong with each, and state what the theory does establish.
Hint
The first argument tests a joint move, which Nash equilibrium does not consider; with a known horizon, Proposition 6.7 gives Low throughout. The second confuses “is an equilibrium” with “will be played”: the folk theorem shows that (High, High) can be sustained for \(\delta\ge\tfrac25\) , and equally that (Low, Low) for ever and many other paths can.
-
The game \(\begin{array}{c|ccc}& L & C & R\\\hline T&(4,2)&(0,3)&(1,1)\\ M&(0,3)&(4,1)&(1,1)\\ B&(1,0)&(1,0)&(2,4)\end{array}\) has three Nash equilibria: one pure, one in which each player mixes over two strategies, and one in which each mixes over all three. Find all three, verifying the conditions for unused strategies where there are any.
Solution
Pure. Player 1’s best responses are \(T\) to \(L\) , \(M\) to \(C\) , and \(B\) to \(R\) . Player 2’s best responses are \(C\) to \(T\) , \(L\) to \(M\) , and \(R\) to \(B\) . The only mutual best response is \((B,R)\) , with payoffs \((2,4)\) .
Supports \(\{T,M\}\) and \(\{L,C\}\) . With probability \(y\) on \(L\) , \(T\) earns \(4y\) and \(M\) earns \(4(1-y)\) , so \(y=\tfrac12\) and both earn \(2\) ; \(B\) earns \(1\le 2\) . With probability \(x\) on \(T\) , \(L\) earns \(2x+3(1-x)=3-x\) and \(C\) earns \(3x+(1-x)=1+2x\) , so \(x=\tfrac23\) and both earn \(\tfrac73\) ; \(R\) earns \(1\le\tfrac73\) . This is an equilibrium: \(\sigma_1=(\tfrac23,\tfrac13,0)\) , \(\sigma_2=(\tfrac12,\tfrac12,0)\) , payoffs \((2,\tfrac73)\) .
Full supports. Let player 2 play \((y_L,y_C,y_R)\) . The rows earn \(4y_L+y_R\) , \(4y_C+y_R\) , and \(y_L+y_C+2y_R\) . Equality of the first two gives \(y_L=y_C\) ; equality with the third gives \(4y_L+y_R=2y_L+2y_R\) , so \(y_R=2y_L\) ; hence \((\tfrac14,\tfrac14,\tfrac12)\) and each row earns \(\tfrac32\) . Let player 1 play \((x_T,x_M,x_B)\) . The columns earn \(2x_T+3x_M\) , \(3x_T+x_M\) , and \(x_T+x_M+4x_B\) . Equality of the first two gives \(x_T=2x_M\) ; equality with the third gives \(7x_M=3x_M+4x_B\) , so \(x_B=x_M\) ; hence \((\tfrac12,\tfrac14,\tfrac14)\) and each column earns \(\tfrac74\) . All probabilities are positive, so this is an equilibrium with payoffs \((\tfrac32,\tfrac74)\) .
The three equilibria give player 1 the payoffs \(2\) , \(2\) , and \(\tfrac32\) and player 2 the payoffs \(4\) , \(\tfrac73\) , and \(\tfrac74\) .
-
The stage game of Example 6.3 is played twice, with the second period’s payoffs multiplied by \(\delta\) . Now suppose that the payoff to \((C,C)\) is \((x,x)\) in place of \((4,4)\) , with \(x<5\) . For which pairs \((x,\delta)\) is the profile “play \(C\) ; then \(G\) after \((C,C)\) and \(D\) otherwise” a subgame-perfect equilibrium? Why is there no such equilibrium, for any \(\delta\) , if the stage game has \((D,D)\) as its only equilibrium?
Answer
Second-period play is a stage equilibrium after every history, so only the first period needs checking: \(x+3\delta\ge 5+\delta\) , that is, \(\delta\ge(5-x)/2\) . Since \(\delta\le 1\) this requires \(x\ge 3\) . A deviation to \(G\) in the first period earns \(0+\delta\) and is worse. With a unique stage equilibrium, Proposition 6.7 forces \((D,D)\) in both periods.
-
A seller offers a single buyer, whose value is uniform on \([0,1]\) , the direct mechanism in which a report \(z\) obtains the object with probability \(z\) for a payment of \(z^2/2\) . Verify that it is incentive compatible and individually rational, compute the seller’s expected revenue, and compare it with the revenue from the optimal posted price. Explain the comparison using virtual values.
Solution
A buyer with value \(v\) who reports \(z\) gets \(vz-\tfrac12z^2\) , a concave function of \(z\) with derivative \(v-z\) , maximized at \(z=v\) . So truthful reporting is optimal: the mechanism is incentive compatible. The truthful payoff is \(U(v)=v^2-\tfrac12v^2=\tfrac12v^2\ge 0\) , so it is individually rational. This agrees with Theorem 9.5: \(Q(v)=v\) is nondecreasing and \(U(v)=\int_0^vs\,ds\) .
The seller’s expected revenue is \(\int_0^1\tfrac12v^2\,dv=\tfrac16\) . The optimal posted price is \(\tfrac12\) , which earns \(\tfrac12\cdot\tfrac12=\tfrac14\) .
By Proposition 9.7 revenue equals the expected virtual surplus \(E[(2v-1)Q(v)]\) . The lottery mechanism gives \(\int_0^1(2v-1)v\,dv=\tfrac23-\tfrac12=\tfrac16\) . It hands the object, with positive probability, to buyers with \(v<\tfrac12\) , whose virtual value is negative, and withholds it, with positive probability, from buyers with \(v>\tfrac12\) , whose virtual value is positive. The posted price does neither: \(Q(v)=1\) exactly when \(2v-1\ge 0\) , which gives \(\int_{1/2}^1(2v-1)\,dv=\tfrac14\) .
-
A rival decides whether to enter a market. With probability \(p\) the incumbent is tough and prefers to fight entry; otherwise it is the incumbent of Example 5.1, which prefers to accommodate. Entry followed by a fight gives the rival \(-1\) , entry followed by accommodation gives \(2\) , and staying out gives \(0\) . The incumbent knows its type and the rival does not. Find the rival’s optimal decision as a function of \(p\) , and explain why an ordinary incumbent would like the rival to believe that \(p\) is large.
Answer
Entering yields \(-p+2(1-p)=2-3p\) , so the rival enters when \(p<\tfrac23\) , stays out when \(p>\tfrac23\) , and is indifferent at \(p=\tfrac23\) . An ordinary incumbent earns more when the rival stays out, so it gains if the rival thinks toughness likely; that gives it a reason to act tough in earlier encounters, which is how a reputation can make a threat credible that would not be credible in the game of Example 5.1 alone.