Independent scholarship · Open accessThe monthly digest

Indexed text attachment

games-and-information-in-higher-categories.tex

Source for Games and Information in Higher Categories

View paper · Download original file

Lines 5839–5938 of 6559. Source text is displayed literally.

5839\cref{ex:chicken}, which is interior to an edge of the polytope.5840 5841\sol{6.5} Let a public device name one player uniformly at random, who then acts alone. The named player5842gets $b-c>0$ rather than $0$; the others get $b$ rather than $b-c$. The good is always provided, and each5843player expects $b-c/n$. The distribution over profiles is invariant under all permutations of the players.5844It maximizes total surplus, so it is the best invariant correlated equilibrium. The symmetric mixed5845equilibrium, also invariant, gives each player only $b-c$. Correlation can respect a symmetry \emph{ex ante}5846while breaking it \emph{ex post}, which independent randomization cannot.5847 5848\sol{6.6} The marginals of $\mu\otimes\nu$ are $\mu$ and $\nu$, so $\nabla$ is injective; and5849$\Dist(f\times g)(\mu\otimes\nu)=\Dist f(\mu)\otimes\Dist g(\nu)$. If $x\ne x'$ and $y\ne y'$, the distribution5850$\tfrac12\delta_{(x,y)}+\tfrac12\delta_{(x',y')}$ is not a product, since a product with its marginals gives5851$(x,y')$ probability $\tfrac14$. If $X$ or $Y$ is a point the map is a bijection, and if one is empty both5852sides are empty.5853 5854\section*{Chapter 7}5855 5856\sol{7.1} $\bot\le f(\bot)$, so $f^k(\bot)$ is increasing and stabilizes in a finite lattice at a fixed point,5857which lies below every fixed point $y$ because $f^k(\bot)\le f^k(y)=y$. Dually from $\top$. For fixed points5858$x,y$, $z=x\vee y$ satisfies $z\le f(z)$, and iterating $f$ from $z$ reaches the least fixed point above both;5859dually for meets. So $\Fix(f)$ is a lattice. On $\N$, a lattice with no top, $n\mapsto n+1$ is monotone5860without fixed points.5861 5862\sol{7.2} For $x'\ge x$, $y'\ge y$, supermodularity applied to $(x',y)$ and $(x,y')$ is increasing5863differences. Conversely two incomparable points $(x_1,y_1)$, $(x_2,y_2)$ with $x_1>x_2$, $y_1<y_2$ have join5864$(x_1,y_2)$ and meet $(x_2,y_1)$, and increasing differences between these four points is the supermodular5865inequality. For $f=g(x+y)$ the condition is $g(s+h+k)-g(s+k)\ge g(s+h)-g(s)$ for $h,k\ge0$: increments of $g$5866are nondecreasing, which for continuous $g$ is convexity.5867 5868\sol{7.3} Each firm's first-order condition is $a-c-bQ-bq_i=0$; summing, $Q=\frac{n(a-c)}{(n+1)b}$,5869$q=\frac{a-c}{(n+1)b}$, $P-c=\frac{a-c}{n+1}$, and profit per firm $\frac{(a-c)^2}{(n+1)^2b}$. Industry profit5870is proportional to $\frac{n}{(n+1)^2}$, whose derivative has the sign of $1-n$.5871 5872\sol{7.4} The best-response map $p\mapsto\tfrac12(a+c+sp)$ is increasing with slope $s/2<1$. Iterating from5873$\bar p$ gives a decreasing sequence and from $c$ an increasing one, both converging to5874$p^*=\frac{a+c}{2-s}$. By \cref{thm:supermodular}(ii) these limits bound the rationalizable prices, so only5875$p^*$ is rationalizable.5876 5877\sol{7.5} Let $m_{-i}=\min_{j\ne i}e_j$. For $e_i'\ge e_i$ the difference5878$2[\min(e_i',m_{-i})-\min(e_i,m_{-i})]-(e_i'-e_i)$ is nondecreasing in $m_{-i}$, which is nondecreasing in5879$e_{-i}$; action sets are chains. So the game is supermodular. The best response is $e_i=m_{-i}$: effort up5880to the minimum returns $2$ per unit at cost $1$, and beyond it returns nothing. The pure equilibria are the5881$m+1$ profiles $(k,\dots,k)$, a chain ordered by payoff $k$. The greatest is $(m,\dots,m)$ and the least5882$(0,\dots,0)$, and every action is rationalizable.5883 5884\sol{7.6} On $\{0,1\}\times\{0,1\}$ let $f(0,t)=0$, $f(1,0)=2$, $f(1,1)=1$. The difference $f(1,t)-f(0,t)$ is5885positive for both $t$, so single crossing holds, but it decreases in $t$. The function $x+y$ on $\{0,1\}^2$ is5886supermodular; $\sqrt{x+y}$ is not, since $\sqrt2+0<1+1$.5887 5888\section*{Chapter 8}5889 5890\sol{8.1} $\Gamma=\bigl(1,\{\mathit{Out},\mathit{In}\},\ \mathit{Out}\mapsto(0,4),\ \mathit{In}\mapsto(2,\{A,F\},A\mapsto(1,2),F\mapsto(-1,0))\bigr)$.5891(a) The inner node evaluates to $(1,2)$ and the root to $(1,2)$. (b) There are no ties, so the fold is5892$\{(1,2)\}$. (c) With $\alpha(o)=1$ and $\alpha(i,A,v)=\sum_av(a)$ the fold is $3$.5893 5894\sol{8.2} (i) Take $h'=h$ for $\Box Q\subseteq Q$; transitivity of ``at or after'' gives5895$\Box Q\subseteq\Box\Box Q$; a universal quantifier commutes with intersections. (ii) If $(h,\sigma)\in\Box Q$5896and $h''$ is after $h$, everything after $h''$ is after $h$, so $(h'',\sigma)\in\Box Q$. If $H\subseteq Q$ is5897hereditary and $(h,\sigma)\in H$ then $(h',\sigma)\in H\subseteq Q$ for all later $h'$. (iii) is the5898definition. In the entry game the profile (\emph{Out}, \emph{Fight}) is in $\mathsf{Nash}$ at the root and5899not at the node after \emph{In}.5900 5901\sol{8.3} With $q_1=\frac{a-c}{2b}$ and $q_2=\frac{a-c}{4b}$ the price is $c+\frac{a-c}{4}$, so profits are5902$\frac{(a-c)^2}{8b}$ and $\frac{(a-c)^2}{16b}$, against $\frac{(a-c)^2}{9b}$ each in Cournot. For prices, the5903follower plays $p_2=\tfrac12(a+c+sp_1)$ and the leader maximizes $(p_1-c)(a-p_1+sp_2)$, giving5904\[ p_1=\frac{a(2+s)+c(2+s-s^2)}{2(2-s^2)}. \]5905With $a=10$, $c=1$, $s=\tfrac12$: $p_1\approx7.79$ and $p_2\approx7.45$, both above the simultaneous price5906$7.33$; profits are about $40.29$ for the leader and $41.56$ for the follower, against $40.11$ each. With5907strategic substitutes the leader gains and the follower loses. With complements both gain and the5908follower gains more, so each firm would like the other to lead.5909 5910\sol{8.4} The buyer accepts $p<v$ and rejects $p>v$. If she accepted $p=v$ with probability $\alpha<1$ the5911seller would earn $\alpha v$ at $v$ and $v-\eta$ at $v-\eta$, and would have no best response. So $\alpha=1$5912and $p=v$. On a grid, if $v$ is not a grid point the seller offers the largest grid price below $v$. If it5913is, the buyer may accept $p=v$ with any probability $\alpha$: for $\alpha\ge1-\epsilon/v$ the seller offers5914$v$, and for $\alpha\le1-\epsilon/v$ she offers $v-\epsilon$. All of these are subgame perfect, their5915outcomes lie within $\epsilon$ of $v$, and the limit as $\epsilon\to0$ selects acceptance when indifferent.5916 5917\sol{8.5} Yes. A deviation still gains $1$ and loses $2$. After a defection by player~1 the continuation5918pays $(0,3)$, which is not Pareto-dominated by $(2,2)$: the innocent party is better off under the5919punishment and will not agree to renegotiate. The three second-stage equilibria are mutually undominated,5920and the cooperative path pays $(4,4)$, which no other profile built from them dominates. Punishments that5921move along the Pareto frontier survive renegotiation; punishments that move inside it do not.5922 5923\sol{8.6} Take a decision node all of whose children are terminal. Its owner has a unique best action5924there. Any strategy choosing otherwise is weakly dominated by the strategy that differs only at that5925node: equal if the node is not reached, better if it is. Delete those strategies, replace the node by its5926backward-induction value, and repeat. The surviving strategies agree with backward induction wherever5927their own earlier choices allow the node to be reached, which is one point of the reduced strategic form.5928The order of deletion was chosen, and \cref{ex:weakdom} shows that this matters in general. For these5929games a theorem of Marx and Swinkels \cite{MaSw97} shows that the payoff outcome, though not the set of5930surviving strategies, is the same for every order.5931 5932\section*{Chapter 9}5933 5934\sol{9.1} Tit-for-tat: states $\{\mathsf{c},\mathsf{d}\}$, outputs $C$ and $D$, initial state $\mathsf{c}$,5935and transition to $\mathsf{c}$ or $\mathsf{d}$ according as the opponent's last action was $C$ or $D$.5936Win-stay, lose-shift: the same states and outputs, with transition to $\mathsf{c}$ iff the two last actions5937agreed. The induced strategies send the empty history to $C$; a history of length one or two to the5938opponent's last action (tit-for-tat) or to $C$ iff the last action profile was $(C,C)$ or $(D,D)$