Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 5539–5638 of 6559. Source text is displayed literally.
5539large stock of worked models built with a consistent recipe should read the source; that is what it is for.5540%% ---- end ch/B-concordance.tex ----5541%% ---- begin ch/C-computations.tex ----5542\chapter{Computational Checks}\label{app:computations}5543 5544The script \texttt{verify.py} that accompanies this book recomputes every numerical example in the text5545and tests a number of structural claims on explicit or randomly generated finite instances. It uses only5546the Python standard library, fixes its random seed, and runs in about a second; \texttt{python3 verify.py}5547prints one line per check and exits with status zero if and only if all pass. Version~1.1 performs 1135548checks, all of which pass under Python~3.8 or later; the last 29 recompute the numerical answers of5549\cref{app:solutions}.5550 5551A check of this kind is evidence about the examples and about the absence of slips in the finite5552statements. It is not a proof of any theorem, and the theorems tagged \textsf{classical} or5553\textsf{literature} rest on the references cited for them. What the script does establish is the5554following.5555 5556\begin{center}\small5557\renewcommand{\arraystretch}{1.25}5558\begin{longtable}{@{}p{0.09\textwidth}p{0.83\textwidth}@{}}5559\toprule5560\textbf{Ch.} & \textbf{What is checked}\\\midrule5561\endhead5562\ref{ch:rules} & The transformed Prisoner's Dilemma has the same equilibrium and reversed efficiency5563 (\cref{prop:which-type}). Both elimination orders of \cref{ex:weakdom} and the simultaneous procedure. Order5564 independence of strict dominance on 200 random games. The invariant profile in pure coordination.\\5565\ref{ch:open} & A direct implementation of \cref{def:opengame,def:og-comp}: the closed composite of5566 decisions and a payoff has exactly the pure Nash equilibria (\cref{prop:og-nash}); the sequential composite5567 of \cref{ex:og-seq} admits the non-credible equilibrium. The product of selection functions agrees with5568 brute-force backward induction on 100 random three-stage trees (\cref{thm:EO}).\\5569\ref{ch:extensive} & The equilibria of \cref{ex:outside} in both trees; the imperfect-recall example.\\5570\ref{ch:knowledge} & On 300 random information structures: the S5 laws and the adjunction of5571 \cref{prop:S5}; equality of iterated mutual knowledge with knowledge relative to the pushout5572 (\cref{thm:aumann-ck}); the formula for $b_1(B)$ against a direct computation of the cycle rank5573 (\cref{prop:hocolim}). The graphs of \cref{fig:Bgraph}, the product structure, and the three-agent example.\\5574\ref{ch:belief} & On 400 random structures: when $b_1(B)=0$ a common prior is constructed for random5575 posteriors and its conditionals verified; when $b_1(B)>0$ random posteriors fail to glue, and posteriors5576 derived from a prior always glue (\cref{thm:H1}); the Hellman--Samet count. The cycle equation of5577 \cref{ex:cycle}. The tower property used in \cref{thm:agree}. \Cref{ex:contribution,ex:redundant}.\\5578\ref{ch:mixing} & \Cref{ex:mixed,ex:chicken}; the fixed-point indices $(+1,+1,-1)$ of \cref{ex:index},5579 computed as winding numbers of the displacement field of a Nash map around each equilibrium.\\5580\ref{ch:order}--\ref{ch:perfection} & Cournot, Bertrand, Stackelberg and the convergence of best-response5581 iteration from the top and bottom of the lattice (\cref{ex:cournot,ex:bertrand,ex:stackelberg}).\\5582\ref{ch:repetition} & The grim-trigger threshold; the operator $B$ of \cref{thm:APS} on the sets of5583 \cref{ex:grim}; Hawk--Dove.\\5584\ref{ch:dynamic} & \Cref{ex:seq-entry,ex:reputation}; the count of strata in \cref{prop:cps}; the knowledge5585 graph of \cref{ex:email} is a connected tree.\\5586\ref{ch:moralhazard}--\ref{ch:moralhazard2} & \Cref{ex:pa,ex:LEN}; the multitask formula of5587 \cref{prop:multitask} against numerical maximization; the efficiency-wage condition.\\5588\ref{ch:adverse} & \Cref{ex:lemons,ex:lemons2}; $\alpha^*\approx0.2899$ and $\lambda^*\approx0.2817$ in5589 \cref{ex:RS}; \cref{ex:GM,ex:kyle}.\\5590\ref{ch:mechanism} & The incentive category by an all-pairs shortest-path computation:5591 \cref{ex:twotype-metric}; a three-type example; detection of negative cycles for a non-monotone rule;5592 incentive compatibility of the representable payment rule on 50 random monotone rules; and the failure of5593 revenue equivalence on a grid of $n+1$ types by exactly $d_f(0,1)+d_f(1,0)=1/n$, vanishing in the limit5594 (\cref{thm:rochet,cor:myerson}). \Cref{ex:screening,ex:screening-cont}; the pivot example.\\5595\ref{ch:signalling} & \Cref{ex:spence}; the cutoffs and boundary indifference of the cheap-talk example;5596 \cref{ex:persuasion,ex:career}.\\5597\ref{ch:bargaining} & \Cref{ex:nash-risk}; finite-horizon shares and the Rubinstein fixed point;5598 the gains from trade $\tfrac16$ and $\tfrac9{64}$ and the buyer's best response in \cref{ex:CS}.\\5599\ref{ch:auctions} & The first-price equilibrium as a best response; revenue equivalence for uniform5600 values; the optimal reserve; the all-pay and third-price bids; the wallet game.\\5601\ref{ch:pricing} & The collusion threshold; \cref{ex:hotelling,ex:coase}; the capacity exercise.\\5602\ref{app:solutions} & The numerical answers to Exercises 1.1, 1.3, 1.4, 5.1, 5.5, 6.2, 6.4, 8.3, 9.2,5603 10.1, 10.4, 11.3, 12.2, 12.3, 13.1--13.3, 14.5, 15.1--15.4, 16.1--16.4, 18.1, 18.3, 18.5 and 18.6. Where5604 a solution asserts an optimum (the best correlated equilibrium of 6.4, the contract of 11.3, the bundle5605 of 14.5), the script checks the stated point against a grid or a random search over the feasible set as5606 well as the first-order conditions.\\5607\bottomrule5608\end{longtable}5609\end{center}5610 5611\noindent The implementation of open games in the script is deliberately naive---strategy sets are5612enumerated and equilibrium predicates evaluated by brute force---and is intended as an executable form of5613the definitions rather than as software. For serious use see the engine cited in \cref{ch:open}.5614%% ---- end ch/C-computations.tex ----5615%% ---- begin ch/D-solutions.tex ----5616\chapter{Solutions to the Exercises}\label{app:solutions}5617 5618Solutions are given for every exercise, numbered as in the chapters. Where an exercise asks for a5619computation, the numbers below are recomputed by the script of \cref{app:computations}.5620 5621\section*{Chapter 1}5622 5623\sol{1.1} The obedience constraint for player $i$ involves payoffs only through the differences5624$u_i(a_i,a_{-i})-u_i(a_i',a_{-i})$. Under $u_i\mapsto\alpha_iu_i+\beta_i(a_{-i})$ each difference is multiplied by5625$\alpha_i>0$, so the system of inequalities is unchanged. For efficiency, take the Battle of the Sexes of5626\cref{ex:three} and add $5$ to the row player's payoff whenever the column player chooses $F$. The profile5627$(F,F)$ now pays $(6,2)$ and Pareto-dominates $(O,O)$, which pays $(2,1)$ and was efficient before; both5628remain Nash equilibria.5629 5630\sol{1.2} An automorphism is a permutation of the players together with bijections of action sets5631preserving payoffs. Payoffs depend only on whether the actions agree, so the two bijections must be the5632same permutation $\pi\in S_m$, with or without exchanging the players: $\Aut(G)\iso S_m\times\Z/2$. In the5633framed game $\pi$ must fix action $1$, and the group is $S_{m-1}\times\Z/2$. An invariant profile is5634symmetric, with each player putting weight $x$ on action $1$ and $(1-x)/(m-1)$ on each other action. A5635player's payoff from an action is the probability the other puts on it, so the support must consist of5636actions of maximal probability. This leaves three invariant equilibria: $x=1$ (both play the distinguished5637action, payoff $1$); $x=0$ (uniform on the undistinguished actions, payoff $\frac1{m-1}$); and $x=\frac1m$5638(uniform on all, payoff $\frac1m$). The first is now selectable.