Indexed text attachment
evolutionary-game-theory-in-machine-learning-and-ai.tex
Source for Evolutionary Game Theory in Machine Learning and AI: Naturality, Regret, and Recurrence
View paper · Download original file
Lines 485–584 of 725. Source text is displayed literally.
485a mutant drawn uniformly from the other \emph{names}, with transition probability given by the fixation486probability, is not natural.487\end{enumerate}488\end{proposition}489\begin{proof}490(a) and (d) by example, below. (b) Payoffs against $f_*x$ at the types are the payoffs against $x$ at the491agents, and a clone map omits no type \cite[Prop.~1.10]{EGHC}. (c) By \Cref{thm:natural}(a), $f_*$ carries492trajectories to trajectories and hence time averages to time averages; the time-average theorem for the493replicator equation \cite{HoSi98} identifies the limit.494\end{proof}495 496\noindent \emph{The example.} Rock, a second copy of Rock, Paper, Scissors. Mean scores are $(0,0,0.25,-0.25)$:497Paper looks best and Scissors worst, although the game is symmetric among the three types. The498time-averaged replicator mass on the types is $(0.3334,0.3333,0.3333)$. \chk{B13} The small-mutation chain,499uniform on plain Rock--Paper--Scissors, gives $(0.2,0.2,0.4,0.2)$ on the four names: Rock's type has mass $0.4$,500Paper $0.4$ and Scissors $0.2$. \chk{B14} The reason is visible in the chain: a population of Scissors is now501invaded twice as often.502 503\begin{remark}[Chain components]\label{rem:mcc}504The chain in (d) is in the manner of $\alpha$-Rank \cite{OPP19}, which ranks agents by the stationary505distribution of a Markov chain on strategy profiles built from fixation probabilities, and which grounds the506construction in Conley's theory: the long-run behaviour of a dynamical system is carried by its chain507recurrent set, and Markov--Conley chains are a finite model of the sink components. This is the right508generalization of equilibrium for games that cycle \cite{PaPi19}, and the dynamical content is natural: chain509components of a natural flow map into chain components. Statement (d) concerns only the mutation kernel of510our small implementation, which counts names; we make no claim about $\alpha$-Rank as published or as used.511A kernel that draws mutants by type would restore invariance, at the price of knowing the types.512\end{remark}513 514\section{Finite populations of learners}\label{sec:pop}515 516Population-based training keeps $N$ agents, lets better ones overwrite worse ones, and perturbs the copies517\cite{Jad17}. With copying in proportion to fitness and one replacement at a time this is the Moran process518of population genetics, and its classical theory applies \cite{Now06,EGHC}.519 520\begin{theorem}[Fixation and the one-third law]\label{thm:third}521\Sli[\cite{NSTF04}] Let two variants play a coordination game: each does best against its own kind, and522the newcomer must exceed a fraction $x^*$ of the population before it is favoured. Under weak selection in a523large population a single newcomer takes over with probability greater than the neutral value $1/N$ if and524only if $x^*<\tfrac13$.525\end{theorem}526 527\noindent With $N=400$ and selection intensity $10^{-3}$, $N\rho$ was $1.021$, $1.009$, $0.991$ and $0.958$ at528$x^*=0.25$, $0.30$, $0.36$ and $0.45$. \chk{B16} The deterministic dynamics says that a new convention, protocol529or shared representation cannot invade from rarity at all when it needs partners; the finite population says530it can, by drift, and when it is more likely than chance to do so.531 532\begin{theorem}[The copying topology matters]\label{thm:graph}533\Sli[\cite{LHN05}] Let offspring of agent $i$ replace agent $j$ with probability $w_{ij}$. The fixation534probability of a variant of relative fitness $r$ equals the well-mixed value $(1-r^{-1})/(1-r^{-N})$ for all $r$535if and only if $W$ is doubly stochastic. A star amplifies selection. On a directed line, in which each536agent copies only its predecessor, fixation has probability $1/N$ whatever the fitness.537\end{theorem}538 539\noindent For $N=6$ and $r=1.2$ the exact values are $0.167$ on the line, $0.251$ well-mixed and $0.287$ on the540star. \chk{B17} The design reading is direct. Symmetric exchange between agents, of any shape, neither helps541nor hurts selection. A hub that many agents copy from and that copies from them sharpens it. A strictly542feed-forward pipeline of copying removes selection altogether: which variant ends up everywhere is decided by543where it started.544 545\begin{remark}[Populations of language-model agents]\label{rem:llm}546Recent work studies populations of agents built on large language models with exactly these tools: replicator547dynamics over agent types in open-source games \cite{OSG25}, evolutionarily stable strategies as a design548target for trust mechanisms \cite{EvT25}, group selection and replicator--mutator models for the evolution of549cooperative prompts \cite{GSP26}, evolutionary game theory as a probe of strategic behaviour \cite{SIL25}, and a550survey of the area \cite{XLLS26}. The titles and identifiers of these five items were checked on 17 November5512026; we have not evaluated their results. Our contribution to that programme is a set of constraints.552Two prompts that induce the same behaviour are clones, so an analysis of a prompt population should be natural553in the sense of \Cref{sec:setting}; stability should be asked of sets of prompts and not of single ones,554because stability of a point is destroyed by cloning and stability of a set is not \cite[Thm.~2.8]{EGHC}; and555conclusions drawn from the replicator equation about invasion by a single new agent are subject to the556correction of \Cref{thm:third}.557\end{remark}558 559\section{Inference}\label{sec:bayes}560 561\begin{proposition}[Bayes is the replicator]\label{prop:bayes}562\Scl[\cite{Sha09,Har09b}] Let $S$ be a set of hypotheses with likelihoods $\ell_h$. Bayesian updating of a prior563$x$ on an observation $o$ is one step of Hedge with $\eta=1$ and payoff $\pi_h=\log\ell_h(o)$. \chk{B18}564\end{proposition}565 566\noindent Bayesian inference is the replicator learner fed log-likelihoods, and the dictionary is exact.567Naturality for clone maps is the statement that splitting a hypothesis into two indistinguishable ones, with the568prior mass divided, changes no posterior probability of any event. The regret identity of \Cref{thm:regc} is569the statement that the log-loss of the Bayesian mixture exceeds that of the best hypothesis by at most570$\log(1/x_h(0))$. And the elimination of dominated strategies with its rate \cite{EGHC} is posterior571concentration: if observations come from $h^*$, the log-odds of any other $h$ against $h^*$ fall at the572expected rate $\KL{\ell_{h^*}}{\ell_h}$ per observation.573 574\section{Summary of results}\label{sec:summary}575 576\begin{table*}[t]577\centering\small578\begin{tabular}{@{}>{\raggedright}p{0.16\textwidth}>{\raggedright}p{0.3\textwidth}>{\raggedright}p{0.34\textwidth}l@{}}579\toprule580Topic & Qualitative statement & Quantitative statement & Checks\\581\midrule582Hedge and replicator & one is the other, sampled & exact at every step size & B1\\583Policy gradient & replicator with an extra factor $x_i$ & escape time $\sim1/(2D\epsilon)$ against $\log(1/\epsilon)/D$; ratios $3.0$, $11.8$, $73.3$ & B2, B3\\584Duplicated actions & (R), (H) natural; (PG), (Q) not & slowdown $2k/(k+1)$; defect $0.028$ & B19--B21\\