Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 4521–4620 of 6559. Source text is displayed literally.
4521pairs and a disagreement point $d\in S$, with some $s\in S$ strictly better than $d$ for both. A4522\term{solution} assigns to each problem a point of $S$.4523\end{definition}4524 4525\begin{theorem}[Nash]\label{thm:nash-bargaining}\Scl[\cite{Nas50b}]4526There is exactly one solution that is (i) Pareto efficient, (ii) symmetric, (iii) invariant under positive4527affine transformations of either player's utility, and (iv) independent of irrelevant alternatives: if4528$S'\subseteq S$ contains the solution of $(S,d)$, then it is the solution of $(S',d)$. It is4529\[ \phi(S,d)=\argmax_{s\in S,\ s\ge d}\ (s_1-d_1)(s_2-d_2). \]4530\end{theorem}4531 4532Read the axioms as statements about a category. Let the objects be bargaining problems. Axioms (ii) and4533(iii) say that the solution is \emph{equivariant} under the group generated by exchanging the players and4534rescaling utilities: it is a function on the type of bargaining problems \emph{up to} the equivalences that4535von Neumann--Morgenstern utility imposes, in the sense of \cref{prin:invariance} and \cref{thm:vnm}. They are4536not substantive assumptions about bargaining; they are the requirement that the question be well posed.4537Axiom (iv) is of a different kind. It says that the solution is \emph{natural} with respect to a class of4538non-invertible morphisms, the inclusions $S'\hookrightarrow S$ that keep the solution feasible. This is the4539substantive axiom, and different choices of morphisms give different theories: requiring instead4540monotonicity with respect to expansions of $S$ that preserve each player's best feasible payoff4541characterizes the solution of Kalai and Smorodinsky \cite{KS75}. The axiomatic method in bargaining is the4542choice of a category on which the solution is to be a natural transformation.4543 4544\begin{example}\label{ex:nash-risk}4545Two players divide one unit. Player~1 has utility $x$ and player~2 has utility $\sqrt{1-x}$; disagreement4546gives both zero. The Nash solution maximizes $x\sqrt{1-x}$, so $x=\tfrac23$. The more risk-averse player4547receives the smaller share: concavity makes her less willing to hold out for more.4548\end{example}4549 4550\section{The strategic solution}4551 4552\begin{definition}4553In the \term{alternating-offers game}, player~1 proposes a division of a unit surplus; player~2 accepts,4554ending the game, or rejects, in which case a period passes and player~2 proposes; and so on. Player $i$4555discounts by $\delta_i\in(0,1)$ per period.4556\end{definition}4557 4558With a finite number $T$ of rounds, after which disagreement gives zero, the game is an element of the4559initial algebra of \cref{ch:perfection} and is solved by a fold. In the last round the proposer takes4560everything. In the round before, the proposer must offer the other her discounted continuation value. With4561a common discount factor the first proposer's share is4562\[ x_T=1-\delta+\delta^2-\cdots\pm\delta^{T-1}=\frac{1-(-\delta)^T}{1+\delta}, \]4563which oscillates and converges to $\frac{1}{1+\delta}$.4564 4565\begin{theorem}[Rubinstein]\label{thm:rubinstein}\Scl[\cite{Rub82,SS84b}]4566The infinite-horizon alternating-offers game has a unique subgame perfect equilibrium. Player~1 proposes4567to keep4568\[ x^*=\frac{1-\delta_2}{1-\delta_1\delta_2}, \]4569player~2 accepts at once, and each player always proposes the same division and accepts exactly the offers4570at least as good as her discounted proposer share.4571\end{theorem}4572 4573\begin{proof}[Proof (Shaked--Sutton)]4574The game is stationary: the subgame beginning at each of player $i$'s proposals is the same game. Let $M_i$4575and $m_i$ be the supremum and infimum of $i$'s subgame-perfect payoffs in a subgame where she proposes. A4576responder gets at most $\delta_jM_j$ by rejecting, so she accepts anything better, and the proposer can4577secure $m_i\ge1-\delta_jM_j$. A responder can secure $\delta_jm_j$ by rejecting, so $M_i\le1-\delta_jm_j$.4578Combining the four inequalities,4579\[ M_1\le\varphi(M_1),\qquad m_1\ge\varphi(m_1),\qquad\text{where }\varphi(x)=1-\delta_2\,(1-\delta_1x). \]4580The affine map $\varphi$ is increasing with slope $\delta_1\delta_2<1$, so $x\le\varphi(x)$ iff $x\le x^*$4581and $x\ge\varphi(x)$ iff $x\ge x^*$, where $x^*$ is its fixed point. Hence $M_1\le x^*\le m_1$.4582\end{proof}4583 4584The proof is worth comparing with the analysis of repeated games in \cref{ch:repetition}. There too one4585considered the set of subgame-perfect payoffs and an operator under which it is a fixed point, and the4586operator $B$ was monotone, with a greatest fixed point much larger than the least. Here the operator4587acts on the interval $[m_1,M_1]$ and is a \emph{contraction}, with modulus $\delta_1\delta_2$; a contraction4588has one fixed point, and the interval collapses. In the terms of \cref{thm:guarded}, bargaining is a4589\emph{guarded} recursion: the continuation value enters each player's decision only as a single number,4590scaled by a discount factor. In a repeated game the continuation enters as a function from histories to4591promised values, whose \emph{spread} supplies incentives, and discounting does not shrink the spread4592relative to what it has to deter. That is the structural reason why one infinite-horizon game has a unique4593equilibrium and the other has a folk theorem.4594 4595A corollary: the infinite-horizon solution is the limit of the finite-horizon ones, $x_T\to\frac{1}{1+\delta}$.4596Under a guard the initial algebra and the terminal coalgebra give the same answer, and the question4597whether there is a last period---so vexed for repeated games---does not matter.4598 4599The solution has the comparative statics one would hope for. The proposer has an advantage, which4600vanishes as offers become frequent. Patience is power: $x^*$ increases in $\delta_1$ and decreases in4601$\delta_2$. If the time between offers is $\Delta$ and $\delta_i=e^{-r_i\Delta}$, then as $\Delta\to0$,4602\[ x^*\longrightarrow\frac{r_2}{r_1+r_2}, \]4603which is the asymmetric Nash bargaining solution with weights inversely proportional to the rates of4604impatience \cite{BRW86}. The strategic theory thus recovers the axiomatic one, and tells us what the4605disagreement point and the bargaining weights are in terms of the primitives of a negotiation: the weights4606are relative patience, and the disagreement point is the payoff \emph{during} disagreement, not the payoff4607from walking away. An outside option that a player could take up instead of continuing affects the4608outcome only if it is worth more to her than her equilibrium share; otherwise the threat to take it is not4609credible, and by the logic of \cref{ch:perfection} it is ignored.4610 4611\section{Private information and delay}4612 4613In the equilibrium of \cref{thm:rubinstein} agreement is immediate, so nothing is wasted. Real4614negotiations take time, and strikes happen. The standard explanation is private information. If the4615seller does not know how much the buyer values agreement, a low offer that would be accepted at once by4616every type leaves money on the table with the high types; a high offer that only high types accept,4617followed by lower offers later, discriminates among them. Delay is a screening device: only a buyer who4618values the good little is willing to wait. The seller is then in the position of the durable-goods4619monopolist of \cref{ch:pricing}, competing with her own future offers, and the analysis is postponed to4620that chapter. With private information on both sides there is a sharper result, which does not depend on