TLDR: A new proposal for a prescriptive theory of multi-agent rationality, based on generalizing superrationality using local symmetries.
Hofstadter's "superrationality" postulates that a rational agent should behave as if other rational agents are similar to itself. In a symmetric game, this implies the selection of a Pareto efficient outcome. However, it's not clear how to apply this principle to asymmetric games. I propose to solve this by suggesting a notion of "local" symmetry that is much more ubiquitous than global (ordinary) symmetry.
We will focus here entirely on finite deterministic (pure strategy) games. Generalizing this to mixed strategies and infinite games more generally is an important question left for the future.
Consider a game Γ with a set P of players, for each player i∈P a non-empty set Si or pure strategies and a utility function ui:S∗→R, where S∗:=∏j∈PSj. What does it mean for the game to be "symmetric"? We propose a "soft" notion of symmetry that is only sensitive to the ordinal ordering between payoffs. While the cardinal value of the payoff will be important in the stochastic context, we plan to treat the latter by explicitly expanding the strategy space.
Given two games Γ(1), Γ(2), a premorphism from Γ(1) to Γ(2) is defined to consist of
Notice that these mappings induce a mapping ^q:S(2)∗→S(1)∗ via
^q(x)i:=¯qi(xq(i))A premorphism is said to be a homomorpism if q and ¯q are s.t. that for any i∈P(1) and x,y∈S(2)∗, if uq(i)(x)≤uq(i)(y) then ui(^q(x))≤ui(^q(y)). Homomorphisms makes games into a category in a natural way.
An automorphism of Γ is a homomorphism from Γ to Γ that has an inverse homomorphism. An automorphism q of Γ is said to be flat when for any i∈P, if q(i)=i then ¯qi is the identity mapping[1]. A flat symmetry of Γ is a group G together with a group homomorphism φ:G→Aut(Γ) s.t. φ(g) is flat for all g∈G.
Given a flat symmetry (G,φ), we can apply the superrationality principle to reduce Γ to the "smaller" quotient game Γ/G. The players are P/G i.e. orbits in the original player set. Given α∈P/G, we define the set of strategies for player α in the game Γ/G to be
(S/G)α:={σ∈∏i∈αSα∣∣ ∣∣∀i∈α,g∈G:σ(i)=¯¯¯¯¯¯¯¯¯¯φ(g)iσ(φ(g)i)}This is non-empty thanks to flatness.
Observe that there is a natural mapping γ:(S/G)∗→S∗ given by
γ(x)i:=xGi(i)Finally, the utility function of α is defined by
uα(x):=1|α|∑i∈αui(γ(x))It is easy to see that the construction of Γ/G is functorial w.r.t. the category structure on games that we defined.
We can generalize this further by replacing game homomorphisms with game quasimorphisms: premorphisms satisfying the following relaxed condition on q and ¯q:
This is no longer closed under composition, so no longer defines a category structure[2]. However, we can still define flat quasisymmetries and the associated quotient games, and this construction is still functorial w.r.t. the original (not "quasi") category structure. Moreover, there is a canonical homomorphism (not just a quasimorphism) from Γ to Γ/G, even when G is a mere quasisymmetry.
The significance of quasisymmetries can be understood as follows.
The set of all games on a fixed set of players P with fixed strategy sets {Si}i∈P naturally forms a topological space[3] X. Given a group G acting on the game via invertible premorphisms, the subset of X where G is a symmetry is not closed, in general. However, the subset of X where G is a quasisymmetry is closed. I believe this will be important when generalizing the formalism to infinite games.
What if a game doesn't have even quasisymmetries? Then, we can look for a coarse graining of the game which does have them.
Consider a game Γ. For each i∈P, let S′i be some set and fi:Si→S′i a surjection. Denote S′∗:=∏i∈PS′i. Given any x∈S′∗, we have the game Γx in which:
If for any x∈S′∗ we choose some αx∈Sx∗ this allows us to define the coarse-grained game Γ(α) in which:
Essentially, we rephrased Γ as an extensive form game in which first the game Γ(α) is played and then, if the outcome was x, the game Γx is played. This, assuming the expected outcome of game Γx is αx.
It is also possible to generalize this construction by allowing multivalued f.
Given a game Γ, a local symmetry presolution (LSP) is recursively defined to be one of the following:
It's easy to see that an LSP always exists, because for any game we can choose a sequence of coarse-grainings whose effect is making the players choose their strategies one by one (with full knowledge of choices by previous players). However, not all LSP are "born equal". It seems appealing to prefer LSP which use "more" symmetry. This can be formalized as follows.
The way an LSP is constructed defines the set of coherent outcomes A⊆S∗, which is the set of outcomes compatible with the local symmetries[4]. We define it recursively as follows:
We define a local symmetry solution (LSS) to be an LSP whose set of coherent outcomes is minimal w.r.t. set inclusion.
Note that flatness is in general not preserved under composition.
I believe this can be interpreted as a category enriched over the category of sets and partial functions, with the monoidal structure given by Cartesian product of sets.
An affine space, even.
Maybe we can interpret the set of coherent outcomes as a sharp infradistirbution corresponding to the players' joint belief about the outcome of the game.