Exercise [exe:fpauniform].

If the rival bids \(v_j/2\), bidding \(b\) wins with probability \(\Prob(v_j/2 < b) = 2b\) (for \(b \le \tfrac12\)); expected profit \((v - b)\,2b\) is maximized at \(b = v/2\). Revenue: \(\E[\max(v_1, v_2)/2] = \tfrac12 \cdot \tfrac23 = \tfrac13 = \E[\min(v_1, v_2)]\), the second-price revenue—revenue equivalence verified.

Exercise [exe:allpay].

Imitating type \(z\) against a rival using \(b(v) = v^2/2\): profit \(= z v - z^2/2\) (win probability \(z\), pay always). FOC: \(v - z = 0\) at \(z = v\): equilibrium confirmed. Revenue \(= \E[b(v_1)] + \E[b(v_2)] = \E[v^2] = \tfrac13\): equivalent again. Real-world all-pay contests: lobbying, patent races, sports training, wars of attrition, crowdfunded prize competitions.

Exercise [exe:pgprivate].

Cutoff \(\theta^*\): contributing yields \(\theta - 1\); abstaining yields \(\theta \cdot \Prob(\text{other contributes}) = \theta \frac{2 - \theta^*}{2}\). Indifference at \(\theta^*\): \(\theta^* - 1 = \theta^* \frac{2-\theta^*}{2} \Rightarrow (\theta^*)^2 = 2 \Rightarrow \theta^* = \sqrt2 \approx 1.41\). First-best: build iff \(\max_i \theta_i \ge 1\) with one contributor (or \(\theta_1 + \theta_2 \geq 1\) with cost sharing)—the equilibrium underprovides: types in \((1, \sqrt2)\) free-ride hoping the other contributes.

Exercise [exe:noswap].

The informed buyer offers \(p\) only when the asset is worth more than \(p\) to her and the offer is profitable: she buys exactly when \(1.5\theta > p\), i.e. your acceptance selects against you. Accepting all \(p \ge 50\): offers arrive (at \(p = 50\)) only when \(\theta > 100/3\); you receive 50 for assets worth on average \(\E[\theta \mid \theta > 33.3] = 66.7\). Expected payoff \(\approx \tfrac13(16.7) + \tfrac23(50) = 38.9 < 50 =\) never trading. Like the lemons market: the willingness of an informed counterparty to trade at \(p\) is itself bad news about \(p\).

Chapter [ch:dynamicincomplete]

Exercise [exe:beerquiche].

Pooling on Beer: on-path belief = prior (0.9 strong) \(\Rightarrow\) no duel; off-path (Quiche) belief “weak” \(\Rightarrow\) duel. Strong: \(3\) vs \(0\); weak: \(2\) vs \(1\): both stay—PBE. Pooling on Quiche: symmetric construction works (\(2\) vs \(1\) for strong, \(3\) vs \(0\) for weak)—also a PBE. Intuitive criterion on the Quiche equilibrium: deviating to Beer is equilibrium-dominated for the weak type (best conceivable payoff \(0 + 2 = 2 < 3\), his equilibrium payoff) but not for the strong type (\(1 + 2 = 3 > 2\)). Beliefs after Beer must then assign probability 1 to strong \(\Rightarrow\) no duel \(\Rightarrow\) the strong type profitably deviates: the all-Quiche equilibrium fails the criterion; all-Beer survives.

Exercise [exe:sepwage].

Pure signaling, cost \(e^2/\theta\): low type: \(e_L = 0\), \(w_L = 1\). Separation requires the low type not to imitate: \(3 - (e^s)^2 \le 1 \Rightarrow e^s \geq \sqrt2\); and the high type to comply: \(3 - (e^s)^2/3 \ge 1 \Rightarrow e^s \le \sqrt6\). Riley outcome: \(e^s = \sqrt2\). Productive education (wage \(\theta + e/2\)): full-information optima \(e_\theta = \theta/4\) (from \(\tfrac12 = 2e/\theta\)). Separation now requires \(3 + e/2 - e^2 \le\) (low type’s honest payoff \(\approx 1.06\)), giving \(e^s \approx 1.66\), far above the high type’s efficient \(0.75\): the high type over-invests to separate. Education is productive but still partly wasteful at the margin—the signaling distortion survives.

Exercise [exe:cheaptalkexercise].

\(b = \tfrac1{10}\): condition \(2K(K-1)b < 1 \iff K(K-1) < 5 \Rightarrow K = 2\). Two intervals \([0, a], [a, 1]\) with actions \(a/2\) and \((1+a)/2\); the boundary type \(a\) must be indifferent between the two actions, which gives \(a/2 + b = (1-a)/2 - b\), hence \(a = \tfrac12 - 2b = 0.3\). Receiver’s expected loss: babbling \(= \mathrm{Var}(U[0,1]) = \tfrac1{12} \approx 0.083\); two-interval \(= \frac{0.3^3 + 0.7^3}{12} \approx 0.031\). Communication is coarse but valuable.

Exercise [exe:insurance].

Pooling fails: a contract slightly better for low-risks only (lower premium, lower coverage) attracts them and leaves the pool high-risk, making the pooling contract unprofitable—cream-skimming. Separating equilibrium: high-risks get full insurance at their fair premium (their IC binds, no distortion for them); low-risks get partial coverage at their own fair rate—coverage limited exactly enough that high-risks prefer their full-coverage contract. If high-risks are too rare, even this fails and no equilibrium exists (Rothschild–Stiglitz)—an early sign that competitive markets with adverse selection are fragile.

Chapter [ch:zerosum]

Exercise [exe:saddle].

Row minima: \(T: 2\), \(C: 0\), \(B: 1 \Rightarrow \underline v = 2\). Column maxima: \(L: 4\), \(M: 2\), \(R: 5 \Rightarrow \overline v = 2\). Saddle point at \((T, M)\), value \(2\) (unique: no other cell is simultaneously a row-max of its column and column-min of its row).

Exercise [exe:guessgame].

Payoff matrix (row’s payoff): \(u(1, \cdot) = (0, 2, -1)\), \(u(2, \cdot) = (-2, 0, 2)\), \(u(3, \cdot) = (1, -2, 0)\). Antisymmetry (\(u(i,j) = -u(j,i)\)) confirms value 0. Equalizing: \(2x_2 - x_3 = 0\), \(-2x_1 + 2x_3 = 0\), \(x_1 - 2x_2 = 0\) give \(x^* = (\tfrac25, \tfrac15, \tfrac25)\). The “middle” action is played least—it never wins big.

Exercise [exe:lpform].

Primal: \(\max v\) s.t. \(x_H - x_T \geq v\) (vs \(H\)), \(-x_H + x_T \ge v\) (vs \(T\)), \(x_H + x_T = 1\), \(x \geq 0\). Adding the constraints: \(0 \ge 2v\), so \(v \le 0\); \(x = (\tfrac12, \tfrac12)\) achieves \(v = 0\). The dual is the column player’s identical program; both optima are 0 with uniform strategies.

Exercise [exe:fpbyhand].

With the stated tie-breaking, one obtains (one legitimate run): \((H,H), (H,T), (H,T), (T,T), (T,T), (T,H), \dots\)—each player chases the other’s empirical frequency, overshoots, and reverses. Frequencies after 6 rounds are already near \((\tfrac12, \tfrac12)\); play cycles forever but the averages converge to optimal play, exactly as Robinson’s theorem promises (and the value estimate converges to 0).

Chapter [ch:existence]

Exercise [exe:kakutaniexercise].

\(\BR_i(x_j) = x_j / 2\) (unique, continuous). \(A_i = [0,1]\) compact convex; \(u_i\) continuous and strictly concave in own action: Theorem [thm:dgf] applies. Fixed point: \(x_1 = x_2/2\), \(x_2 = x_1/2 \Rightarrow (0, 0)\), the unique equilibrium.

Exercise [exe:perfectexercise].

Pure equilibria: \((T, L)\), \((B, R)\), and \((M, C)\). The strict equilibria \((T,L)\) and \((B,R)\) are trivially perfect. \((M, C)\): against the symmetric totally mixed tremble \(\sigma_2 = (\varepsilon, 1 - 2\varepsilon, \varepsilon)\), all three of row’s actions pay exactly 1, so \(M\) is a best response, and likewise for \(C\): \((M, C)\) is also perfect (though not strict). Perfection kills weakly dominated behavior—but \(M\) is not dominated, merely payoff-equivalent to \(\tfrac12 T + \tfrac12 B\). The example shows perfection is weaker than one might hope in non-generic games.

Exercise [exe:seqvspbe].

Standard example structure: players 1 and 2 move in sequence, player 3 moves at an information set reached only if both deviate. PBE permits player 3 to hold any belief there—including beliefs that treat 1’s and 2’s deviations as perfectly correlated in an arbitrary way. Consistency (limits of independent trembles) forces 3’s belief to be the product of the two small deviation probabilities, pinning the conditional to specific ratios. Sequential rationality against those pinned-down beliefs can then eliminate equilibria PBE allows. Moral: consistency disciplines off-path beliefs by requiring a single coherent “theory of mistakes.”

Exercise [exe:notrade].

Suppose a bet occurs with positive probability at some pair of signals. Willingness to bet is common knowledge at that point (betting is voluntary and observed). Player 1 bets only if his conditional expected gain is positive; player 2 likewise—but the bet is zero-sum, so the two conditional expectations, taken with respect to the common prior conditional on the same public event, cannot both be positive (iterated expectations). Aumann’s agreement logic turns “I’m happy to bet” into information that destroys the other’s willingness. Without the common prior, players can knowingly disagree, and betting on differences of opinion (not information) becomes possible.

Chapter [ch:mechanism]

Exercise [exe:vcgcombo].

Efficient allocation: \(A \to 2\), \(B \to 3\) (total 12 \(> 10\)). Payments: without bidder 2, the best the others can do is 10 (bidder 1 takes the pair); others’ value at the actual allocation is 6, so bidder 2 pays 4; symmetrically bidder 3 pays 4. Revenue \(= 8\). VCG revenue can be fragile: raise \(v_2(A) = v_3(B) = 10\) and each pays \(10 - 10 = 0\)—efficient allocation, zero revenue. Adding bidders can reduce VCG revenue; this non-monotonicity is why high-stakes combinatorial auctions modify VCG (core-selecting designs).

Exercise [exe:reservederive].

Exponential: \(\frac{1 - F}{f} = 1\), so \(\psi(v) = v - 1\) (increasing: regular); \(r^* = 1\). Pareto \(F = 1 - v^{-2}\) on \([1, \infty)\): \(\frac{1-F}{f} = \frac{v^{-2}}{2v^{-3}} = \tfrac{v}{2}\), so \(\psi(v) = v/2 > 0\) everywhere: the “reserve” is the support minimum (always sell). Indeed, for one bidder a posted price \(p\) earns \(p\,(1 - F(p)) = p \cdot p^{-2} = p^{-1}\), maximized at the corner \(p = 1\). Heavy tails make revenue maximization degenerate—and for tail index 1, expected values are infinite and every price earns the same revenue. Optimal auction theory quietly assumes tails are thin enough.

Exercise [exe:mshand].

With \(c, v \sim U[0,1]\), efficient trade (iff \(v > c\)) requires expected transfers that violate budget balance under IC and IR; running the Myerson–Satterthwaite calculation, the second-best mechanism trades iff \(v \ge c + \tfrac14\): one maximizes expected gains from trade subject to IC, IR, and budget balance; the binding budget constraint enters as a Lagrange multiplier on the virtual surplus, and solving for the multiplier that exactly balances the budget yields the \(\tfrac14\) wedge (this is also the outcome of the linear equilibrium of the Chatterjee–Samuelson double auction). First-best trade region: the triangle above the diagonal; second-best: the smaller triangle shifted up by \(\tfrac14\)—trades with gains below \(\tfrac14\) are sacrificed to control information rents.

Exercise [exe:singlepeaked].

Median voting: a voter left of the median can change the outcome only by reporting on the other side of the median, moving the chosen point further from her peak; misreporting on her own side changes nothing. Single-peakedness makes “further in the wrong direction” unambiguously worse: strategy-proof. Phantoms preserve the argument verbatim (the median of true peaks plus constants). Gibbard–Satterthwaite does not apply because single-peaked preferences are a restricted domain—the theorem needs all preference profiles to be possible.

Chapter [ch:cooperative]

Exercise [exe:coreexercise].

Core: \(\sum x_i = 135\), \(x_1 + x_2 \ge 90\), \(x_1 + x_3 \ge 80\), \(x_2 + x_3 \geq 70\) (equivalently \(x_3 \le 45\), \(x_2 \le 55\), \(x_1 \le 65\)), \(x_i \geq 0\): a nonempty polytope; e.g. \((65, 45, 25)\). Shapley value: averaging marginal contributions over the 6 orders gives \(\phi = (50, 45, 40)\). Check core membership: pairwise sums \(95, 90, 85\) all clear their thresholds: yes, \(\phi \in C(v)\).

Exercise [exe:production].

Core: if a worker received more than \(g(w) - g(w-1)\), the coalition of L with the other \(w - 1\) workers could object; so worker pay is capped by the marginal product. Shapley with \(g = \sqrt{k}\), \(w = 3\): in a uniformly random order, the number of workers preceding L is uniform on \(\{0,1,2,3\}\), so \(\phi_L = \tfrac14(0 + 1 + \sqrt2 + \sqrt3) \approx 1.04\); each worker gets \((\sqrt3 - \phi_L)/3 \approx 0.23\) (below the marginal product \(\sqrt3 - \sqrt2 \approx 0.32\), consistent with the core cap).

Exercise [exe:ssindex].

Enumerating pivots over the 24 orders of \((A{:}4, B{:}3, C{:}2, D{:}1)\) with quota 6: \(A\) pivots 10 times, \(B\) 6, \(C\) 6, \(D\) 2. Index: \((\tfrac{5}{12}, \tfrac14, \tfrac14, \tfrac1{12})\). Note \(B\) and \(C\) have equal power despite different weights—power is about pivotal position in coalitions, not vote count (the deep lesson of power indices).

Exercise [exe:roommates].

Players \(\{1,2,3,4\}\); preferences: \(1: 2 \succ 3 \succ 4\); \(2: 3 \succ 1 \succ 4\); \(3: 1 \succ 2 \succ 4\); 4: anyone. In any matching, someone among \(\{1,2,3\}\) is paired with 4; that person is the favorite of one of the other two, who is currently matched to their least-preferred partner among \(\{1,2,3\}\)—the two form a blocking pair. All three matchings are blocked: no stable matching exists. Two-sidedness matters because it prevents exactly these odd “cyclic envy” configurations within one side.

Chapter [ch:evolutionary]

Exercise [exe:essverify].

\(u(A, B) = 5 > 3 = u(B, B)\) and \(u(A, A) = 2 > 1 = u(B, A)\): \(A\) strictly dominates \(B\). The only symmetric equilibrium is \((A, A)\), which is strict, hence the unique ESS. (The indifference equation \(5 - 3p = 3 - 2p\) has no solution in \([0,1]\), confirming no mixed equilibrium.)

Exercise [exe:replphase].

Payoffs: \(u_H = -x + 2(1 - x) = 2 - 3x\), \(u_D = 1 - x\). Replicator: \(\dot x = x(1 - x)\,(u_H - u_D) = x(1-x)(1 - 2x)\). Rest points \(0, \tfrac12, 1\). Sign: positive on \((0, \tfrac12)\), negative on \((\tfrac12, 1)\): interior point \(x^* = \tfrac12 = V/C\) is asymptotically stable; both monomorphic states are unstable. The population converges to the ESS mix from any interior start.

Exercise [exe:domdie].

\(\frac{d}{dt} \log \frac{x_a}{x_b} = \frac{\dot x_a}{x_a} - \frac{\dot x_b}{x_b} = u(a, x) - u(b, x) \le -\varepsilon\), where \(\varepsilon = \min_x [u(b,x) - u(a,x)] > 0\) by strict domination and compactness. Hence \(x_a / x_b \le e^{-\varepsilon t} \cdot x_a(0)/x_b(0) \to 0\), and since \(x_b \le 1\), \(x_a \to 0\).

Exercise [exe:invasion].

With mutant share \(\varepsilon\): \(u_{\text{Stag}} = 4\varepsilon + 0(1 -\varepsilon) = 4\varepsilon\); \(u_{\text{Hare}} = 2\). Stag grows iff \(4\varepsilon > 2\), i.e. \(\varepsilon > \tfrac12\): the good convention needs the majority to switch at once—an enormous invasion barrier (the mixed equilibrium share). This is why inferior conventions persist and why coordinated “big push” interventions (assurance contracts, standards bodies announcing a switch date, critical-mass subsidies) are the practical remedy.

Chapter [ch:algorithmic]

Exercise [exe:cournotpotential].

Take \(\Phi(q_1, q_2) = (a - c)(q_1 + q_2) - q_1^2 - q_2^2 - q_1 q_2\). Then \(\partial \Phi / \partial q_i = a - c - 2q_i - q_j = \partial u_i / \partial q_i\): an exact (continuous) potential. Maximizing \(\Phi\): FOCs give \(q_1 = q_2 = \frac{a - c}{3}\), the Cournot equilibrium—and concavity of \(\Phi\) proves uniqueness and gives convergence of continuous best-response dynamics.

Exercise [exe:pigoupoa].

Equilibrium: all traffic on road 2 (cost \(x^d \leq 1\) with equality at \(x = 1\)): social cost 1. Optimum: minimize \(1 - x + x^{d+1}\): \(x^{\mathrm{opt}} = (d+1)^{-1/d}\), cost \(1 - \frac{d}{d+1}(d+1)^{-1/d} \to 0\) like \(\frac{\ln d}{d}\). Hence \(\mathrm{PoA} \sim \frac{d}{\ln d} \to \infty\): with very convex congestion, selfish routing can be arbitrarily bad—and the affine bound \(\tfrac43\) of Theorem [thm:routingpoa] is seen to be a genuinely structural fact about linear congestion.

Exercise [exe:ccenotce].

Rock–Paper–Scissors; let \(\mu\) be uniform on the three diagonal profiles \((R,R), (P,P), (S,S)\), giving each player payoff 0. CCE: any constant deviation faces a uniform opponent marginal, earning 0—no gain. Not CE: conditional on the recommendation “Rock,” the opponent plays Rock for sure, so swapping to Paper earns \(+1 > 0\). The extra power of swap deviations (using the recommendation as information) is exactly what separates the two concepts.

Exercise [exe:loadbalance].

Congestion game with \(c(k) = k\); potential \(\Phi = \sum_{r} \frac{\ell_r(\ell_r + 1)}{2}\). Pure equilibria: profiles where no job can move to a strictly less loaded machine, i.e. \(|\ell_1 - \ell_2| \le 1\): loads are balanced. Every equilibrium makespan is \(\lceil n/2 \rceil\), which is also optimal: \(\mathrm{PoA} = 1\) here. (With \(m\) unrelated machines or weighted jobs, equilibria can be unbalanced and the PoA grows—the classic Koutsoupias–Papadimitriou setting.)