Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 5181–5280 of 6559. Source text is displayed literally.
5181The same must be said of the word ``higher''. The homotopy types that appeared are graphs. The categories5182that appeared are 1-categories, a bicategory and a double category of open games, and categories enriched5183in posets. Where genuinely higher structure is visible---the homotopy types of equilibrium sets, which by5184Datta's theorem are arbitrary; the simplicial models of many-agent knowledge; the $\infty$-toposes in which5185smooth and probabilistic games ought to live---this book has pointed and not built. A reader who came for5186$(\infty,1)$-categories has been given the 1-truncation of a programme.5187 5188\section{What the language does not do}5189 5190\emph{It does not solve games.} Composition of open games composes the equilibrium check, not the search5191(\cref{ch:open}). Computing equilibria is hard for reasons no notation removes (\cref{ch:mixing}).5192 5193\emph{It does not select equilibria.} The invariance principle says what a selection must respect, and5194thereby that many proposed selections are not well defined; it does not supply one. The structure theorem5195says there is no continuous one.5196 5197\emph{It does not adjudicate modelling choices.} Whether the order of moves is part of the game, whether5198histories may serve as frames, whether types are hierarchies or something finer: the type-theoretic5199discipline forces these choices to be declared. It does not make them.5200 5201\emph{It does not replace the examples.} Every structural statement in this book was extracted from models5202that economists built for particular purposes, and the worked examples carry content that the general5203statements do not.5204 5205\section{Problems}5206 5207The following seem to us well posed, open, and of a kind that the language of this book makes natural.5208 5209\begin{problem}[A univalent type of extensive games]\Spg5210\Cref{sec:thompson} defined $\EFG_{\mathrm{T}}$ as a quotient. Find a notion of structure, intrinsic rather5211than presented, whose structure-preserving equivalences are exactly the Thompson equivalences, so that5212invariance holds by the structure identity principle rather than by decree. The set-theoretic5213reformulations of the extensive form in terms of plays and choices \cite{AFR16} are a natural starting5214point; the reduced strategic form is the trivial answer, and the problem is to find one that retains5215enough dynamic structure to state sequential rationality.5216\end{problem}5217 5218\begin{problem}[Perfection as an operation on open games]\Spg5219The modality $\Box$ of \cref{prop:box} was defined for closed extensive games. Define it on the category of5220open games, as an operation on equilibrium predicates, so that $\Box(\mathcal{H}\circ\mathcal{G})$ is5221computed from $\Box\mathcal{H}$ and $\Box\mathcal{G}$, recovering \cite{Hed16,GKLF18} as special cases, and5222extend it to information sets with beliefs so as to obtain a compositional sequential equilibrium for the5223Bayesian open games of \cite{BHZ19}.5224\end{problem}5225 5226\begin{problem}[The exit-path category of the space of games]\Spg5227The equilibrium correspondence is semialgebraic, so the space $\mathcal{U}$ of games with given action sets5228admits a stratification over each stratum of which the projection5229$\mathrm{pr}\colon\mathcal{E}\to\mathcal{U}$ of \cref{sec:KM} is a fibre bundle. The fibres then assemble into a5230functor from the exit-path $\infty$-category of the stratification to spaces. Describe this functor for the5231smallest nontrivial cases. Characterize the essential components and the stable sets of \cite{KM86,GW05} as5232subfunctors with a universal property. \Cref{rem:truncated} suggests that a refinement in the proper sense5233is a homotopy-invariant of this functor; make that a definition and compare it with the axiomatic5234characterizations.5235\end{problem}5236 5237\begin{problem}[Higher cohomology of information]\Spg5238For $n\ge3$ agents the simplicial model $\mathcal{C}$ of \cref{ch:knowledge} has higher homotopy that the5239graph $B$ lacks. In distributed computing its connectivity obstructs the solvability of tasks. Find the5240game-theoretic meaning of $H^k(\mathcal{C})$ for $k\ge2$. A candidate: the marginal problem \cite{Vor62}, of5241which \cref{thm:H1} is the pairwise case, asks when beliefs specified on a family of coalitions are the5242marginals of a single joint belief, and its obstructions are known to be cohomological in the closely5243related setting of contextuality \cite{AB11}. Which mediated correlations among coalitions are implementable5244by local devices is a question of this kind.5245\end{problem}5246 5247\begin{problem}[Graded modalities]\Spg5248Three approximations in this book are indexed by a real parameter: common $p$-belief5249(\cref{ch:dynamic}), $\epsilon$-equilibrium, and discounting by $\delta$. The first is a graded comonad, the5250second has a compositional metric formulation \cite{Gha25}, and the third is a quantitative form of the5251later modality (\cref{thm:guarded}). Give a single quantale-graded modal type theory in which all three are5252instances, and in which the continuity theorem of Monderer and Samet and the limit theorems for5253finite-horizon approximations \cite{FL83} are theorems about grades.5254\end{problem}5255 5256\begin{problem}[Beyond quasi-linearity]\Spg5257\Cref{thm:rochet} and \cref{prop:nucleus} use transferable utility in an essential way: the base of5258enrichment is the additive reals. N\"oldeke and Samuelson \cite{NS18} extend the duality between tariffs5259and utility profiles to preferences that are not quasi-linear, by means of Galois connections. Identify the5260enriching structure for which their duality is the nucleus of a profunctor, and state implementability and5261payoff equivalence as conditions on the resulting enriched category.5262\end{problem}5263 5264\begin{problem}[A synthetic existence theorem]\Spg5265Nash's theorem requires Brouwer's, which holds synthetically in a cohesive type theory \cite{Shu18}, while5266mixed strategies require probability, which is axiomatized by Markov categories \cite{Fri20}. Find a5267setting with both: a category or type theory in which the mixed extension is a free construction, strategy5268spaces carry intrinsic topology, and the truncated existence statement of \cref{rem:truncated} is a5269theorem. Determine which classes of games admit an untruncated one: supermodular games, by5270\cref{thm:supermodular}; two-player zero-sum games, by linear programming; potential games, by5271maximization.5272\end{problem}5273 5274\begin{problem}[Effective game theory]\Spg5275\Cref{thm:NZ} shows that best responses to computable strategies need not be computable. Develop the5276theory of repeated games internally to a realizability topos, where every function is computable by5277construction. Is there a folk theorem there? The internal terminal coalgebra of the strategy functor5278consists of computable strategies, and the internal equilibrium condition quantifies only over those; the5279classical counterexamples suggest that the internal and external equilibrium sets differ, and the5280difference would be a precise measure of what bounded rationality costs.