A Category Theoretic Approach to Compositional Approximation in Game Theory
Neil Ghani · 2025
Read A Category Theoretic Approach to Compositional Approximation in Game Theory by Neil Ghani (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-20932.txt.
Introduction
Game theory asks what the best move is, but in real life an almost-best move is often all anyone can compute. Neil Ghani rebuilds that idea from category theory in a solo-authored 2025 paper, first presented at the ACT 2024 conference. The paper proposes a wholly fresh approach to approximate game theory.
Ghani starts with selection functions, abstract tools that pick outcomes from sets of possibilities. On that base he builds a simple, robust model of approximate equilibria. He then develops the algebraic rules that approximation obeys in this setting. Category theory supplies a uniform language for agents, decisions, and near-optimality. The aim is practical as much as theoretical: exact answers may be impossible when inputs are uncertain.
Catalog record
| CREATOR | Neil Ghani |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 39 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-20932
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Category Theoretic Approach to Compositional Approximation in Game Theory Neil Ghani Abstract This paper uses category theory to guide the development of an entirely new approach to approximate game theory. Game theory is the study of how different agents within a multi-agent system take decisions. At its core, game theory asks what an optimal decision is in a given scenario. Thus approximate game theory asks what is an approximately optimal decision in a given scenario. This is important in practice as — just like in much of computing — exact answers maybe too difficult (or even impossible) to compute given inherent uncertainty in input. We consider first Selection Functions which are a simple model of compositional game theory. We develop i) a simple yet robust model of approximate equilibria; ii) the algebraic properties of approximation with respect to selection functions; and iii) relate approximation to the compositional structure of selection functions. We then repeat this process for Open Games — a more advanced model of game theory featuring the key operation of sequential composition of games. Finally, we use approximation to develop new metrics on game theory and show these yield core theorems in what one might term ”Metric Game Theory”. 1 Introduction This paper uses category theory to develop an entirely new approach to compositional approximate game theory. Approximation in computation is ubiquitous e.g. it arises in: i) stochastic systems, where one merely has probability distributions over values induced by inherent/simulated randomness; ii) resource limited environments, where exact computation is prohibitively expensive; iii) systems with imperfect/partial recall, where one only has limited information about what has happened or the intentions/trustworthiness of each agent; and iv) non-exact computation where primitive data (e.g. from sensors) is inexact and supplied with error bars. These scenarios arise in e.g. cyber-physical systems, machine learning, robotics, automotive engineering, aerospace, and energy systems. On the other hand, game theory is the study of how different agents within a multi-agent system take decisions. The simplest model of game theory we consider are the multi-valued selection functions [ 6 ] which are functions s:(X\to V)\to PX . Henceforth we merely call them selection functions. Here, i) the set X is thought of as a set of actions (or moves, or choices) the agent can consider; ii) the set V is thought of as a type of utilities; and iii) a function X\to V is called a utility function as it assigns, to each possible action, a utility measuring how good that action is deemed to be. A selection function then maps every utility function to those actions deemed optimal for that utility function as as such is a model of game theory. The canonical selection function is argmax defined by x\in\mbox{{\sf argmax}}\;f\;\;\mbox{ iff }\;\;(\forall x^{\prime}:X)\;fx\geq fx^{\prime} Another selection function is \epsilon\!\!-\!\!\mbox{{\sf argmax}} defined by x\in\epsilon\!\!-\!\!\mbox{{\sf argmax}}\;f\;\;\mbox{ iff }\;\;(\forall x^{\prime}:X)\;fx\geq fx^{\prime}-\epsilon which means for an action x to be \epsilon -optimal it need merely have an associated utility which is within \epsilon of a true optimal action. This approach aligns with the general approach to approximation of uncertainty budgets as we track - and therefore can check - how much utility is lost by moving to an approximately optimal decision. Notice this is NOT saying x is close to an optimal choice of action, rather that the utility of x is close to being the utility of an optimal action. One might study the former and, indeed, this was our first intention. However, the mathematical behaviour of that concept was poorer so we switched to the approach taken in this paper. Nevertheless, this was the first of several moments where key decisions need to be taken to obtain a well behaved mathematical theory showing the combination of approximation and game theory to be a delicate and nuanced endeavour. A second difficulty arises from the desire for compositionality to ensure scalability. Compositional systems are those where larger systems can be defined by assembling smaller subsystems together which means that proving properties of larger systems can be reduced to proving properties of smaller (and hence easier to reason about) subsystems. At its core, compositionality is a story about structure and so the natural mathematical medium in which to develop compositionality is category theory. Recently, Compositional Game Theory [ 10 ] was introduced to bring the advantages of compositionality to game theory. However, within compositional game theory there are a number of different notions of morphisms of open games and, as we shall see, certain notions behave better with regards to approximation than others. Finding the right notion of morphisms of open games to interact well with approximation was another issue we had to solve. Concretely, this paper will • introduce a notion of the \epsilon -approximation of a game by defining for any game G , another game \mbox{{\sf T}}_{\epsilon}G which we think of as containing not just the equilibria of G , but also the \epsilon -equilibria of G — this is an entirely new approach to approximation of equilibria and shows novelty of methodology. • show that \mbox{{\sf T}}_{\epsilon} has good algebraic structure in that it is i) functorial; and ii) possesses graded structure — this shows our methodology is canonical in being aligned with other work on quantitative computation. [ 3 ] • show T_{\epsilon} interacts well with the compositional structure of game theory, in particular with Nash equilibria and sequential composition. There is no particular reason that the approximation of a large game built from game-constructors should retain that structure — we show this holds for the key cases of parallel (or Nash) product and sequential composition. This is crucial evidence for the utility of our approach, namely that preserves the compositional structure of game theory. • use our approximate game theory to create what one might call Metric Game Theory which i) not only builds new games from old; but ii) ensures if one substitutes a subgame with another which has similar behaviour, the overall system remains similar to the original. The crucial construction permitting Metric Game Theory is a metric on games which we build from our approximate game theory. This third item is particularly surprising and thus our strongest contribution — as mentioned there is no inherent reason why, for example, the approximations of a Nash equilibria should form a Nash equilibria. Finally, we argue in the conclusions that our methodology is also general in that it can apply to other forms of game theory, eg Markov Decision Processes, and beyond game theory into the huge area of machine learning. This latter application area is particularly exciting as formally quantifying distance from optimality is a way of expressing how much has been learned and thus contributing to the XAI agenda. This paper is structured as follows. In Section 2, we cover preliminaries pertaining to metric spaces, lenses and selection functions. Section 3 develops approximation for selection functions, discusses the algebraic properties of approximation and shows approximation is compositional. Section 4 extends these results to open games [ 10 ] , while Section 5 uses approximation to develop Metric Game Theory. Section 6 concludes the paper with conclusions and directions for future research. 2 Preliminaries: Metric Spaces and Lenses This paper should be accessible