When Do LLM Agents Settle? Memory-Mediated Potential Games

Multi-agent systems increasingly revise persistent shared state such as memories, workboards, and partial solutions. Each worker owns the part it may rewrite and writes only what it judges better than the incumbent. Those judgments are imperfect, and the record used to evaluate a candidate may be stale. When must such revision settle? We study this in finite exact-potential games, where a worker's report of a candidate's improvement may differ from the truth by at most $\beta$ and a revision is accepted only when the reported gain exceeds a margin $\delta$. We characterize the settling boundary: universal termination holds if and only if $\delta \ge \beta$. Above the boundary, every accepted revision makes true progress of more than $\delta -\beta$, so there is a finite move bound, and an exhaustive quiet scan gives a $(\delta +\beta )$-approximate Nash guarantee. At equality, termination survives without a spread-based rate; below the boundary, even stationary reports can cycle with one player. Representation matters too, since reports generated by one fixed scalar score terminate for every positive margin in that single-player case. Within the scalar class, let $n\ge 2$ workers update one at a time with pointwise scalar error at most $\eta$. Each reads its own coordinate fresh and others coordinatewise, possibly from different rounds at most $q\in \{1,\dots ,n-1\}$ rounds old. If changing one opponent's action changes a worker's true cost by at most $L>0$ at every fixed own action, universal termination holds exactly when $\delta \ge 2\eta +L\min \{2q,n-1\}$, even with partial scans or unfair schedules. Matching finite games cycle below it. Potential descent handles short delays; long delays need an argument that no worker returns to an action it left. Further results account for simultaneous writes, certify recorded paths and fresh endpoints, and separate a quiet scan from absorption under continued stochastic evaluation, where ties can move infinitely often almost surely. An appendix applies record-level checks to one language model's comparisons at fixed profiles.