Indexed text attachment
games-and-information-in-higher-categories.tex
Source for Games and Information in Higher Categories
View paper · Download original file
Lines 5199–5298 of 6559. Source text is displayed literally.
5199discipline 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.5281\end{problem}5282 5283\section{A last remark on method}5284 5285The source of this book's subject matter describes its own method as modelling with the minimum of5286structure: find the simplest set of assumptions that generates the phenomenon, and stop. That is a5287principle of economy about what goes into a model. The discipline followed here adds a second economy,5288about what one may get out: only what is invariant under the equivalences of the model's type. The two5289economies are complementary. The first prevents explanation by excess detail. The second prevents5290explanation by accident of presentation. Game theory has always practised both, the second by the5291judgment of its practitioners. The claim of this book is modest: that the judgment can be written down.5292%% ---- end ch/19-coda.tex ----5293\appendix5294%% ---- begin ch/A-toolkit.tex ----5295\chapter{Categorical Toolkit}\label{app:toolkit}5296 5297This appendix fixes notation and collects, without proofs, the categorical notions used in the text. It is5298a list of what is needed, in the order in which it is needed, and not an introduction to any of the