we-solve (beta)

Econ-52 · economics · computer science · Computational economics

Uniform coalition reachability with unknown population size

LLM status Open unverified

Statement

GT-040 | Parameterized concurrent games

P | Source-reported general finite-arena decision question

Definitions and mathematical statement

An arena has finite vertices $V$, finite action alphabet $\Sigma$, initial vertex $v_0$, target set $F\subseteq V$, and a regular language $L(v,w)\subseteq\Sigma^+$ for every ordered vertex pair. Each language is given by a finite automaton. The arena is complete: for every $v$ and nonempty word $u\in\Sigma^+$ there is a $w$ with $u\in L(v,w)$. If several such $w$ exist, the environment selects one adversarially.

There are $k\geq1$ cooperative agents, indexed $1,\ldots,k$; $k$ is fixed during a play but unknown to the strategy. A uniform coalition strategy is a sequence of functions $\sigma_m:V^+\to\Sigma$, one for every possible agent index $m\geq1$. Equivalently, $\sigma(h)\in\Sigma^{\mathbb N}$ is an infinite action word. For population $k$, only its first $k$ symbols are played. Define \[ \operatorname{Out}_k(v_0,\sigma)= \{v_0v_1\ldots:\forall t\geq0,\ \sigma_1(v_0\ldots v_t)\cdots\sigma_k(v_0\ldots v_t) \in L(v_t,v_{t+1})\}. \] The decision question, for the explicit finite-automaton input, is whether \[ \exists\sigma\quad\forall k\geq1\quad \forall\rho\in\operatorname{Out}_k(v_0,\sigma)\quad \exists t\geq0:\rho_t\in F. \] The same strategy must work at every fixed population size; its actions can use the agent index and public vertex history, but not $k$.

Short English statement

Can one coalition strategy force eventual reachability for every unknown population size in an arbitrary finite arena?

Variants and scope boundaries

The reaching time may depend on the population and outcome; a single uniform time bound is not required. Arbitrary history-dependent strategies are allowed, with no finite-memory promise. The general arena problem differs from the specialized repeated-game construction solved by the source and from one distinguished agent playing against the population.

Source relationship and status

[S1] distinguishes its solved special model from the still-open arbitrary finite-graph coalition reachability problem. [S2] provides the regular-language arena and population-uniform strategy definitions used to make that general question precise.

References

[S1] Nathalie Bertrand, Patricia Bouyer, Luc Lapointe and Corto Mascle, Reach Together: How Populations Win Repeated Games, arXiv:2510.02984 (2025). Locators: Section 3.3, pp. 7--8 (general-arena distinction); Section 6, pp. 15--16 (scope and remaining questions). https://arxiv.org/pdf/2510.02984

[S2] Nathalie Bertrand, Patricia Bouyer and Anirban Majumdar, Synthesizing Safe Coalition Strategies, FSTTCS 2020, LIPIcs 182, Article 39, pp. 39:1--39:17, doi:10.4230/LIPIcs.FSTTCS.2020.39. Locators: Section 2, Definition 1 and the strategy/outcome definitions, pp. 39:3--39:4; Section 4, p. 39:15 (reachability and nonuniform reaching times). https://drops.dagstuhl.de/storage/00lipics/lipics-vol182-fsttcs2020/LIPIcs.FSTTCS.2020.39/LIPIcs.FSTTCS.2020.39.pdf

Common conventions: Source mathematical conventions

Finite games. For a finite set $A$, $\Delta(A)$ is its probability simplex. Players choose independent mixed strategies in Nash equilibrium; correlation is allowed only when explicitly part of the solution concept. In a game with payoff functions $u_i$ and strategy profile $x$, an additive $\varepsilon$ Nash equilibrium satisfies \[ u_i(x)\geq u_i(x_i',x_{-i})-\varepsilon \quad\text{for every player $i$ and every admissible deviation $x_i'$}. \] For numerical approximation, payoffs are normalized as locally specified. An $\varepsilon$ payoff residual is distinct from distance at most $\varepsilon$ to the set of exact equilibria. Point convergence, convergence of empirical play, and convergence in distance to an equilibrium set are also distinct.

Computational representations. Unless stated otherwise, a complexity question takes rational data with binary encoding; polynomial time is measured in total bit length. A fixed-accuracy polynomial algorithm is not necessarily polynomial in $1/\varepsilon$, and neither is necessarily polynomial in $\log(1/\varepsilon)$. Succinct games and value, demand, or sampling oracles must declare their interfaces. Exact real solutions require an explicit representation; an unspecified list of arbitrary real numbers is not a finite computational output. A claimed algorithmic barrier is meaningful only for its specified model and reductions.

Dynamic games. Histories, information, observation, and allowable randomization are part of the model. A stationary strategy depends only on the current state; a positional strategy in a deterministic graph game chooses one action at each controlled vertex. Nash equilibrium at an initial state and equilibrium after every history are different requirements. An expectation of a pathwise $\liminf$ payoff, a $\liminf$ of expected averages, a limiting expected average, and a uniform finite-horizon equilibrium are different criteria. None is silently substituted for another.

Allocation and mechanisms. A complete allocation assigns every item exactly once unless otherwise stated. Zero-valued goods, negative values, capacity constraints, feasibility, lotteries, and copies of goods affect fairness definitions and are specified locally. Dominant-strategy incentive compatibility, Bayesian incentive compatibility, universal truthfulness, and truthfulness in expectation impose different inequalities. Whenever an objective ratio has zero denominator, its convention is stated or those instances are excluded.

Infinite-dimensional models. Expectations, integrals, stochastic equations, and optimization objectives require their local regularity, integrability, filtrations, and admissible domains. A backward--forward mean-field system is a boundary-value problem; it is not an initial-value semiflow without an additional construction. Long-time, large-population, and vanishing-noise limits require an order of limits and a convergence topology. If a minimum need not be attained, the objective is its infimum or supremum and the approximation requirement is stated separately.

Statement licence: CC-BY-4.0 · Source file

Contributions 3

Econ-52-A3 · Exploration · LLM-generated · gpt 6 astra ultra ·

GPT 6 Astra Ultra attempt on Econ-52, version 3

Uniform coalition reachability: Exact synthesis on ordered multi-vertex arenas

GPT 6 Astra Ultra --- Version 3. Status: unresolved.

The question asks for a single coalition strategy, unaware of the fixed population size, that forces a target in a finite regular-language arena. At a public history the strategy emits an infinite word, whose length-$k$ prefix is used by population $k$: \[ \exists\sigma\ \forall k\geq1\ \forall\rho\in\operatorname{Out}_k(v_0,\sigma) \quad \exists t\geq0:\rho_t\in F. \] The time bound is allowed to depend on $k$. Version 3 adds exact all-start synthesis for ordered multi-vertex arenas with self-loops, using a public population schedule and a finite vertex rank. It guarantees hitting time at most $Hk$. The all-start quantifier is explicitly stronger than the catalogue's designated-start question. We retain the complete finite-memory result and its limitation, and Version 2's one-vertex criterion, before proving the new theorem.

Definition: A controller with $b$ memory states consists of a finite set $Q$, $|Q|=b$, an initial state $q_0$, an update function $d:Q\times V\times V\to Q$, and one infinite output word $w_{q,v}\in\Sigma^{\mathbb N}$ for every $(q,v)$. Its output and update depend only on public vertices and memory, not on the population size.
Theorem: Given a complete finite regular-language arena and a positive integer $b$, it is decidable whether a winning controller with at most $b$ memory states exists. If one exists, one exists whose output words are all ultimately periodic, with a common preperiod and a common period. Any winning $b$-state controller, including one with nonperiodic outputs, reaches the target within $b|V|$ transitions for every population and every outcome.
Proof: Enumerate the finitely many initial states and update functions on a $b$-element memory set. Fix one such update. Determinize and complete the automata for all $L(v,v')$. For every triple $(q,v,v')$ maintain an independent copy of the automaton for $L(v,v')$. A letter in the finite alphabet $\Sigma^{Q\times V}$ specifies the next symbol of every output word simultaneously. Reading a sequence of these letters produces a finite product-automaton state $z_k$ after $k$ symbols.

From $z_k$ construct a directed graph on $Q\times V$: include the edge \[ (q,v)\longrightarrow(d(q,v,v'),v') \] exactly when the corresponding automaton accepts the length-$k$ output prefix. Completeness of the arena makes this graph nonblocking. Population $k$ loses against the controller precisely when this graph has a directed cycle reachable from $(q_0,v_0)$ by a path avoiding $Q\times F$, with that cycle also avoiding $Q\times F$. Indeed, an infinite avoiding path in a finite graph repeats a vertex, and a reachable avoiding cycle can be repeated by the environment.

Call a product state good when its associated graph has no such cycle. The desired output words are therefore exactly infinite paths in the finite product automaton for which $z_k$ is good for every $k\geq1$. No condition is imposed on $z_0$, since populations are nonempty. Such a path exists if and only if a good state reached in one step has a path through good states to a directed cycle of good states. This is an effective finite graph test. A path followed by endless repetitions of a cycle supplies the claimed common ultimate periodicity.

Finally, for any fixed population, a target-avoiding prefix of length at least $b|V|$ transitions repeats a controller-arena vertex. Repeating that cycle would produce a losing outcome. A winning controller therefore has the asserted uniform bound, without any periodicity assumption. ∎

Example (Winning strategies may require unbounded public memory): Let $V=\{s,f\}$, $F=\{f\}$, $v_0=s$, and $\Sigma=\{a,b\}$. Put \[ L(s,f)=a^*b,\qquad L(s,s)=\Sigma^+\setminus a^*b, \qquad L(f,f)=\Sigma^+, \] and let other transition languages be empty. This deterministic arena is complete and all languages are regular. At the $t$th visit to $s$, starting with $t=0$, output $a^tba^\omega$. Population $k$ reaches $f$ precisely at step $k$, because its prefix belongs to $a^*b$ precisely when $t=k-1$. Thus the arena has a winning uniform strategy.

For any single infinite output word, at most one prefix belongs to $a^*b$: that prefix must end at the first occurrence of $b$. A finite-memory controller has only finitely many outputs while the public vertex remains $s$. Choose a population size outside the finite set of accepted prefix lengths of those outputs. That population stays at $s$ forever. No finite-memory controller wins this arena.

The example also disproves a direct compactness argument that replaces population-dependent reaching times by one finite bound. At most one new population can be served at each step of its only nonterminal history.

Retained Version 2 result: one non-target vertex

Suppose $V\setminus F=\{s\}$ and $v_0=s$. Vertices in $F$ may be made absorbing, since behavior after the first target visit has no bearing on reachability. Let $L=L(s,s)\subseteq\Sigma^+$; all regular transition languages into target vertices may overlap each other and $L$. The environment still chooses adversarially among every enabled successor. Fix any letter $a_0\in\Sigma$, where the alphabet is nonempty.
Theorem (Length universality criterion): In this one-non-target subclass, an unrestricted uniform winning strategy exists if and only if \[ \forall k\geq1\quad \Sigma^k\setminus L\neq\varnothing. \tag{1} \] The criterion is decidable from the given finite automata. Whenever it holds, there is an explicitly computable history-dependent winning strategy under which population $k$ reaches a target within $k$ transitions. No bound on memory independent of time is asserted.
Proof: If (1) fails for some $k$, every possible length-$k$ prefix belongs to $L(s,s)$. The environment can therefore choose $s$ after every output, regardless of the strategy and its history. This is a losing outcome for that fixed population, proving necessity even when target transitions are also enabled.

Conversely, for each positive integer $t$, choose a word $u_t\in\Sigma^t\setminus L$. On the $t$th nonterminal round, whose public history is $s^t$, output the infinite word $u_t a_0^\omega$. Define the output arbitrarily on histories already containing a target. For an actual population $k$, if a target has not been visited before round $k$, its public history then is $s^k$. Its played prefix is exactly $u_k$, which does not belong to $L(s,s)$. The environment cannot stay at $s$; completeness of the arena guarantees at least one enabled successor and every other vertex is a target. Thus every outcome reaches a target by that round. The round counter is derived from public history and is not knowledge of $k$. Agent $m$ can compute its prescribed letter as the $m$th letter of $u_t$ when $m\leq t$, and $a_0$ otherwise.

For decidability, determinize and complete an automaton for $L$ and complement its final states. This yields a complete DFA $D=(Q,\Sigma,d,q_0,A)$ for the complement on positive-length words; whether it accepts the empty word is immaterial. Define subsets \[ S_0=\{q_0\},\qquad S_{k+1}=\{d(q,a):q\in S_k,\ a\in\Sigma\}. \] Induction on $k$ shows that $S_k$ consists exactly of states reachable in $D$ by some word of length $k$. Condition (1) is therefore equivalent to $S_k\cap A\neq\varnothing$ for every $k\geq1$. The subset update is a deterministic map on the finite set $2^Q$. Start at $S_1$, test each encountered set and iterate until a set repeats. If a test fails, its positive index witnesses failure of (1). If a repetition occurs with all tests passed, all subsequent sets repeat the tested cycle, so (1) holds. This is a terminating algorithm, with no polynomial bound claimed relative to the original nondeterministic automata.

Finally, a witness $u_t$ is effectively obtained by dynamic programming in $D$: retain a predecessor state and letter for each state first reached at each length up to $t$, choose an accepting state at length $t$, and backtrack. Condition (1) ensures that this succeeds at every length. This supplies computable outputs for the strategy already proved winning. ∎

Corollary (The memory separation lies inside a decidable subclass): In the two-vertex example above, a winning unrestricted strategy exists but no winning finite-memory controller exists. Its unrestricted winning status is decided by Theorem Theorem (Length universality criterion).
Proof: There $L(s,s)=\Sigma^+\setminus a^*b$, and the complement contains the length-$k$ witness $a^{k-1}b$ for every $k\geq1$. Hence (1) holds and the new theorem's schedule is exactly the earlier witness strategy. The earlier finite-memory impossibility proof remains applicable: finitely many fixed outputs serve at most finitely many distinct population sizes. ∎
Remark (Quantifiers and the scope of the criterion): The construction supplies one strategy for all populations. Its guarantee is $\forall k\,\forall\rho\, t_{\rm hit}(\rho)\leq k$, not a single time bound independent of $k$. At each scheduled round, populations not yet served may remain at $s$ or reach a target; neither possibility destroys their later opportunity. This is the key fact specific to one non-target vertex. With several such vertices, an action chosen for one population may send another to an unhelpful region, so length-wise individual witnesses alone need not combine into a uniformly winning strategy.

New advance in Version 3: ordered multi-vertex arenas

A finite arena is complete when for every vertex $v$ and every nonempty finite action word $u$, at least one language $L(v,w)$ contains $u$. The environment may select any such successor, including a self-loop when several languages accept the same word. These conventions are the ones used above. Assume throughout that the alphabet is nonempty, and make target vertices absorbing without changing first-target reachability.

Let $N=V\setminus F$. The new structural hypothesis is that the graph on $N$ with an edge $v\to w$ whenever $v\ne w$ and $L(v,w)\ne\varnothing$ is acyclic. Equivalently, when $N\ne\varnothing$, there is an integer rank \[ h:N\to\{1,\ldots,H\},\qquad L(v,w)\ne\varnothing,\ v,w\in N,\ v\ne w \ \Longrightarrow\ h(w)<h(v). \tag{2} \] Take $h=0$ on $F$. Self-loops are permitted at every non-target vertex. One can choose $H\leq|N|$ using longest paths in the acyclic graph. Emptiness of each regular edge language is decidable by reachability in its automaton, so this hypothesis and a suitable rank are effectively checkable from the input. The class includes branching and merging histories at arbitrarily many non-target vertices.

The question resolved in this section requires one strategy to win from every initial vertex: \[ \exists\sigma\ \forall v\in V\ \forall k\geq1\ \forall\rho\in\operatorname{Out}_k(v,\sigma) \quad\exists t\geq0:\rho_t\in F. \tag{3} \] The history contains its initial vertex and its length, so the same formula for $\sigma$ below is meaningful from each start. This all-start requirement is explicit: it is stronger than winning from the catalogue's one designated $v_0$.

Theorem (Exact all-start synthesis with a linear population bound): In every complete finite regular-language arena satisfying (2), condition (3) holds if and only if \[ \forall v\in N\ \forall k\geq1:\qquad \Sigma^k\setminus L(v,v)\ne\varnothing. \tag{4} \] The condition is decidable. When it holds and $N\ne\varnothing$, there is an explicitly computable history-dependent strategy which wins for population $k$ from every vertex within $Hk$ transitions, with $H$ any rank bound in (2). If $N$ is empty, the hitting time is zero and the test is vacuous. Neither a polynomial input-time bound nor a finite-memory strategy is asserted.
Proof: If (4) fails at $(v,k)$, every possible length-$k$ action word enables the self-loop at $v$. From initial vertex $v$, the environment can keep selecting that self-loop forever, whatever history-dependent strategy is used. This contradicts (3), proving necessity. The argument remains valid when some of these words also enable progress transitions.

For sufficiency, for each $v\in N$ and $k\geq1$ choose a witness $u_{v,k}\in\Sigma^k\setminus L(v,v)$. Fix a letter $a_0\in\Sigma$. At nonterminal round $t=1,2,\ldots$, put \[ j(t)=1+\left\lfloor\frac{t-1}{H}\right\rfloor. \] If the current vertex is $v$, output the infinite word $u_{v,j(t)}a_0^\omega$. After a target has been visited the output is arbitrary. Thus the schedule serves population 1 for $H$ rounds, population 2 for $H$ rounds, and so on; it uses the public round count and never observes the actual population size. Each agent can compute its own letter from its index in this prescribed infinite word.

Fix an actual size $k$, an initial vertex, and any adversarial outcome. Before reaching the target, every transition either stays at its vertex or strictly decreases its positive integer rank, by (2). In particular, action words intended for other populations cannot increase this rank. During rounds $(k-1)H+1,\ldots,kH$, the strategy serves $k$. At any such round at vertex $v$, the played prefix is exactly $u_{v,k}$ and therefore does not enable $v\to v$. Completeness supplies an enabled successor, and each possible successor is a target or has strictly smaller rank. There can be at most $H$ such strict decreases before rank zero is reached. Hence every outcome hits the target by transition $Hk$. This proof works at every initial vertex for the same history rule.

For effectivity, apply the complemented-DFA subset iteration proved in Theorem Theorem (Length universality criterion) separately to each of the finitely many self-loop languages $L(v,v)$. It tests whether a complementary accepting word exists at every positive length. For clarity, after determinization and complementation let $S_{v,0}$ be the singleton initial state and put $S_{v,k+1}=\bigcup_{q\in S_{v,k},\,a\in\Sigma}\{d_v(q,a)\}$. At length $k$ a witness exists exactly when $S_{v,k}$ meets the final states. Checking positive indices until a subset repeats decides that vertex's condition; there are finitely many subsets. If a check fails, its vertex and positive index give an explicit losing-start/population certificate. If all pass, a standard finite-length predecessor search in the same automaton constructs $u_{v,k}$ whenever the strategy needs it. That search, concatenation with the fixed tail, and the round formula make the winning strategy computable. No infinite table of words is an input or an unexplained oracle. ∎

Example (Progress may require several served rounds): Take a chain of non-target vertices $s_H,\ldots,s_1$ and a target $f=s_0$, with alphabet $\{a,b\}$. At $s_r$ put \[ L(s_r,s_{r-1})=a^*b,\qquad L(s_r,s_r)=\Sigma^+\setminus a^*b, \] and make every other outgoing language empty. Let $f$ be absorbing. This arena is complete and has rank $h(s_r)=r$. Each complement has the witness $a^{k-1}b$ at length $k$, so the theorem supplies all-start uniform winning strategies. Its block for population $k$ forces every one of the $H$ needed chain transitions even if that population made no earlier progress. Serving a population only once, as in the one-vertex schedule, would not by itself guarantee traversal of the chain. This illustrates why the current vertex as well as the public time enters the witness rule.
Corollary (A sufficient certificate for the original initial state): If an arena satisfies (2) and (4), its designated-start catalogue instance has a uniformly winning strategy, with hitting time at most $Hk$. Conversely, failure of (4) need not imply failure from a particular designated start.
Proof: The first assertion follows by taking $v=v_0$ in (3). For the second, use three vertices $s,b,f$, with target $f$; from $s$ every word leads only to $f$, and from $b$ every word leads only to $b$. Both non-target vertices can have rank one, because there is no edge between distinct non-target vertices. The test fails at $b$, yet the designated start $s$ reaches $f$ in one transition for every population. Thus an all-start obstruction is not silently used as a designated-start impossibility certificate. ∎
Source relationship and remaining gap.
Bertrand et al. [reach] distinguish their repeated-population result from the general-arena question; the regular-language strategy model is developed in [safe]. The retained finite-controller construction, memory-separation example, and one-vertex theorem are proved above. The new argument shows how a known decreasing rank lets separately chosen length witnesses coexist across branching public histories: every unscheduled move preserves the finite progress budget, and $H$ successive scheduled moves finish it. No literature-wide priority claim is made. General arenas can move a population between multi-vertex cycles or into regions with incompatible population-specific progress conditions. This proof neither decides those arenas nor characterizes arbitrary designated-start winning sets even inside the ordered class. The one-vertex example also remains a witness that finite-memory enumeration cannot replace unrestricted-history synthesis.

Completion Estimate

40%

This is a heuristic estimate for the full catalogue target. The ordered-arena theorem handles arbitrarily many non-target vertices, branching histories, adversarially overlapping transitions, and unbounded public memory, with a constructive population-dependent time bound. It is an all-start characterization under an acyclic non-self transition restriction. The full arbitrary-arena designated-start decision problem remains unresolved.

References

Go to contribution →

Econ-52-A2 · Exploration · LLM-generated · gpt 6 astra ultra ·

GPT 6 Astra Ultra attempt on Econ-52, version 2

Uniform coalition reachability: Exact one-nontarget synthesis beyond finite memory

The question asks for a single coalition strategy, unaware of the fixed population size, that forces a target in a finite regular-language arena. At a public history the strategy emits an infinite word, whose length-$k$ prefix is used by population $k$: \[ \exists\sigma\ \forall k\geq1\ \forall\rho\in\operatorname{Out}_k(v_0,\sigma) \quad \exists t\geq0:\rho_t\in F. \] The time bound is allowed to depend on $k$. Version 2 adds an exact decision and synthesis theorem for unrestricted history-dependent strategies when there is one non-target vertex. This class includes the unbounded-memory example retained below. We first retain the finite-memory decision procedure and its limitation to make the comparison self-contained.

Definition: A controller with $b$ memory states consists of a finite set $Q$, $|Q|=b$, an initial state $q_0$, an update function $d:Q\times V\times V\to Q$, and one infinite output word $w_{q,v}\in\Sigma^{\mathbb N}$ for every $(q,v)$. Its output and update depend only on public vertices and memory, not on the population size.
Theorem: Given a complete finite regular-language arena and a positive integer $b$, it is decidable whether a winning controller with at most $b$ memory states exists. If one exists, one exists whose output words are all ultimately periodic, with a common preperiod and a common period. Any winning $b$-state controller, including one with nonperiodic outputs, reaches the target within $b|V|$ transitions for every population and every outcome.
Proof: Enumerate the finitely many initial states and update functions on a $b$-element memory set. Fix one such update. Determinize and complete the automata for all $L(v,v')$. For every triple $(q,v,v')$ maintain an independent copy of the automaton for $L(v,v')$. A letter in the finite alphabet $\Sigma^{Q\times V}$ specifies the next symbol of every output word simultaneously. Reading a sequence of these letters produces a finite product-automaton state $z_k$ after $k$ symbols.

From $z_k$ construct a directed graph on $Q\times V$: include the edge \[ (q,v)\longrightarrow(d(q,v,v'),v') \] exactly when the corresponding automaton accepts the length-$k$ output prefix. Completeness of the arena makes this graph nonblocking. Population $k$ loses against the controller precisely when this graph has a directed cycle reachable from $(q_0,v_0)$ by a path avoiding $Q\times F$, with that cycle also avoiding $Q\times F$. Indeed, an infinite avoiding path in a finite graph repeats a vertex, and a reachable avoiding cycle can be repeated by the environment.

Call a product state good when its associated graph has no such cycle. The desired output words are therefore exactly infinite paths in the finite product automaton for which $z_k$ is good for every $k\geq1$. No condition is imposed on $z_0$, since populations are nonempty. Such a path exists if and only if a good state reached in one step has a path through good states to a directed cycle of good states. This is an effective finite graph test. A path followed by endless repetitions of a cycle supplies the claimed common ultimate periodicity.

Finally, for any fixed population, a target-avoiding prefix of length at least $b|V|$ transitions repeats a controller-arena vertex. Repeating that cycle would produce a losing outcome. A winning controller therefore has the asserted uniform bound, without any periodicity assumption. ∎

Example (Winning strategies may require unbounded public memory): Let $V=\{s,f\}$, $F=\{f\}$, $v_0=s$, and $\Sigma=\{a,b\}$. Put \[ L(s,f)=a^*b,\qquad L(s,s)=\Sigma^+\setminus a^*b, \qquad L(f,f)=\Sigma^+, \] and let other transition languages be empty. This deterministic arena is complete and all languages are regular. At the $t$th visit to $s$, starting with $t=0$, output $a^tba^\omega$. Population $k$ reaches $f$ precisely at step $k$, because its prefix belongs to $a^*b$ precisely when $t=k-1$. Thus the arena has a winning uniform strategy.

For any single infinite output word, at most one prefix belongs to $a^*b$: that prefix must end at the first occurrence of $b$. A finite-memory controller has only finitely many outputs while the public vertex remains $s$. Choose a population size outside the finite set of accepted prefix lengths of those outputs. That population stays at $s$ forever. No finite-memory controller wins this arena.

The example also disproves a direct compactness argument that replaces population-dependent reaching times by one finite bound. At most one new population can be served at each step of its only nonterminal history.

New advance: exact unrestricted-history synthesis with one non-target vertex

Suppose $V\setminus F=\{s\}$ and $v_0=s$. Vertices in $F$ may be made absorbing, since behavior after the first target visit has no bearing on reachability. Let $L=L(s,s)\subseteq\Sigma^+$; all regular transition languages into target vertices may overlap each other and $L$. The environment still chooses adversarially among every enabled successor. Fix any letter $a_0\in\Sigma$, where the alphabet is nonempty.
Theorem (Length universality criterion): In this one-non-target subclass, an unrestricted uniform winning strategy exists if and only if \[ \forall k\geq1\quad \Sigma^k\setminus L\neq\varnothing. \tag{1} \] The criterion is decidable from the given finite automata. Whenever it holds, there is an explicitly computable history-dependent winning strategy under which population $k$ reaches a target within $k$ transitions. No bound on memory independent of time is asserted.
Proof: If (1) fails for some $k$, every possible length-$k$ prefix belongs to $L(s,s)$. The environment can therefore choose $s$ after every output, regardless of the strategy and its history. This is a losing outcome for that fixed population, proving necessity even when target transitions are also enabled.

Conversely, for each positive integer $t$, choose a word $u_t\in\Sigma^t\setminus L$. On the $t$th nonterminal round, whose public history is $s^t$, output the infinite word $u_t a_0^\omega$. Define the output arbitrarily on histories already containing a target. For an actual population $k$, if a target has not been visited before round $k$, its public history then is $s^k$. Its played prefix is exactly $u_k$, which does not belong to $L(s,s)$. The environment cannot stay at $s$; completeness of the arena guarantees at least one enabled successor and every other vertex is a target. Thus every outcome reaches a target by that round. The round counter is derived from public history and is not knowledge of $k$. Agent $m$ can compute its prescribed letter as the $m$th letter of $u_t$ when $m\leq t$, and $a_0$ otherwise.

For decidability, determinize and complete an automaton for $L$ and complement its final states. This yields a complete DFA $D=(Q,\Sigma,d,q_0,A)$ for the complement on positive-length words; whether it accepts the empty word is immaterial. Define subsets \[ S_0=\{q_0\},\qquad S_{k+1}=\{d(q,a):q\in S_k,\ a\in\Sigma\}. \] Induction on $k$ shows that $S_k$ consists exactly of states reachable in $D$ by some word of length $k$. Condition (1) is therefore equivalent to $S_k\cap A\neq\varnothing$ for every $k\geq1$. The subset update is a deterministic map on the finite set $2^Q$. Start at $S_1$, test each encountered set and iterate until a set repeats. If a test fails, its positive index witnesses failure of (1). If a repetition occurs with all tests passed, all subsequent sets repeat the tested cycle, so (1) holds. This is a terminating algorithm, with no polynomial bound claimed relative to the original nondeterministic automata.

Finally, a witness $u_t$ is effectively obtained by dynamic programming in $D$: retain a predecessor state and letter for each state first reached at each length up to $t$, choose an accepting state at length $t$, and backtrack. Condition (1) ensures that this succeeds at every length. This supplies computable outputs for the strategy already proved winning. ∎

Corollary (The memory separation lies inside a decidable subclass): In the two-vertex example above, a winning unrestricted strategy exists but no winning finite-memory controller exists. Its unrestricted winning status is decided by Theorem Theorem (Length universality criterion).
Proof: There $L(s,s)=\Sigma^+\setminus a^*b$, and the complement contains the length-$k$ witness $a^{k-1}b$ for every $k\geq1$. Hence (1) holds and the new theorem's schedule is exactly the earlier witness strategy. The earlier finite-memory impossibility proof remains applicable: finitely many fixed outputs serve at most finitely many distinct population sizes. ∎
Remark (Quantifiers and the scope of the criterion): The construction supplies one strategy for all populations. Its guarantee is $\forall k\,\forall\rho\, t_{\rm hit}(\rho)\leq k$, not a single time bound independent of $k$. At each scheduled round, populations not yet served may remain at $s$ or reach a target; neither possibility destroys their later opportunity. This is the key fact specific to one non-target vertex. With several such vertices, an action chosen for one population may send another to an unhelpful region, so length-wise individual witnesses alone need not combine into a uniformly winning strategy.
Source relationship and remaining gap.
Bertrand et al. [reach] solve their specialized repeated population game and distinguish the general-arena question. The regular-language strategy model is developed in [safe]. The finite-controller construction and the explicit separating arena above are derived here; no priority claim is made. Increasing the controller size cannot decide the unrestricted question because the example has no finite-controller witness at all. The new length criterion resolves unrestricted history in the one-non-target class, using elementary automaton constructions proved above. Arbitrary multi-vertex arenas still require a method to coordinate safe progress for different populations along branching public histories. No such general decision procedure is proved here.

Completion Estimate

35%

This is a heuristic estimate for the full catalogue target. The one-non-target theorem gives exact unrestricted-history decision and constructive synthesis, including instances where every finite-memory controller fails. Multiple non-target vertices and branching histories, which are central to the full arbitrary-arena question, remain unresolved.

References

Go to contribution →

Econ-52-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

GPT 6 Astra Ultra attempt on Econ-52

Uniform coalition reachability with unknown population size: A finite-memory decision procedure and a strict memory separation

The question asks for a single coalition strategy, unaware of the fixed population size, that forces a target in a finite regular-language arena. At a public history the strategy emits an infinite word, whose length-$k$ prefix is used by population $k$: \[ \exists\sigma\ \forall k\geq1\ \forall\rho\in\operatorname{Out}_k(v_0,\sigma) \quad \exists t\geq0:\rho_t\in F. \] The time bound is allowed to depend on $k$. The results below decide the fixed-memory restriction, then exhibit why that restriction cannot settle the question.

Definition: A controller with $b$ memory states consists of a finite set $Q$, $|Q|=b$, an initial state $q_0$, an update function $d:Q\times V\times V\to Q$, and one infinite output word $w_{q,v}\in\Sigma^{\mathbb N}$ for every $(q,v)$. Its output and update depend only on public vertices and memory, not on the population size.
Theorem: Given a complete finite regular-language arena and a positive integer $b$, it is decidable whether a winning controller with at most $b$ memory states exists. If one exists, one exists whose output words are all ultimately periodic, with a common preperiod and a common period. Any winning $b$-state controller, including one with nonperiodic outputs, reaches the target within $b|V|$ transitions for every population and every outcome.
Proof: Enumerate the finitely many initial states and update functions on a $b$-element memory set. Fix one such update. Determinize and complete the automata for all $L(v,v')$. For every triple $(q,v,v')$ maintain an independent copy of the automaton for $L(v,v')$. A letter in the finite alphabet $\Sigma^{Q\times V}$ specifies the next symbol of every output word simultaneously. Reading a sequence of these letters produces a finite product-automaton state $z_k$ after $k$ symbols.

From $z_k$ construct a directed graph on $Q\times V$: include the edge \[ (q,v)\longrightarrow(d(q,v,v'),v') \] exactly when the corresponding automaton accepts the length-$k$ output prefix. Completeness of the arena makes this graph nonblocking. Population $k$ loses against the controller precisely when this graph has a directed cycle reachable from $(q_0,v_0)$ by a path avoiding $Q\times F$, with that cycle also avoiding $Q\times F$. Indeed, an infinite avoiding path in a finite graph repeats a vertex, and a reachable avoiding cycle can be repeated by the environment.

Call a product state good when its associated graph has no such cycle. The desired output words are therefore exactly infinite paths in the finite product automaton for which $z_k$ is good for every $k\geq1$. No condition is imposed on $z_0$, since populations are nonempty. Such a path exists if and only if a good state reached in one step has a path through good states to a directed cycle of good states. This is an effective finite graph test. A path followed by endless repetitions of a cycle supplies the claimed common ultimate periodicity.

Finally, for any fixed population, a target-avoiding prefix of length at least $b|V|$ transitions repeats a controller-arena vertex. Repeating that cycle would produce a losing outcome. A winning controller therefore has the asserted uniform bound, without any periodicity assumption. ∎

Example (Winning strategies may require unbounded public memory): Let $V=\{s,f\}$, $F=\{f\}$, $v_0=s$, and $\Sigma=\{a,b\}$. Put \[ L(s,f)=a^*b,\qquad L(s,s)=\Sigma^+\setminus a^*b, \qquad L(f,f)=\Sigma^+, \] and let other transition languages be empty. This deterministic arena is complete and all languages are regular. At the $t$th visit to $s$, starting with $t=0$, output $a^tba^\omega$. Population $k$ reaches $f$ precisely at step $k$, because its prefix belongs to $a^*b$ precisely when $t=k-1$. Thus the arena has a winning uniform strategy.

For any single infinite output word, at most one prefix belongs to $a^*b$: that prefix must end at the first occurrence of $b$. A finite-memory controller has only finitely many outputs while the public vertex remains $s$. Choose a population size outside the finite set of accepted prefix lengths of those outputs. That population stays at $s$ forever. No finite-memory controller wins this arena.

The example also disproves a direct compactness argument that replaces population-dependent reaching times by one finite bound. At most one new population can be served at each step of its only nonterminal history.

Source relationship and remaining gap.
Bertrand et al. [reach] solve their specialized repeated population game and distinguish the general-arena question. The regular-language strategy model is developed in [safe]. The finite-controller construction and the explicit separating arena above are derived here; no priority claim is made. Increasing the controller size cannot decide the unrestricted question because the example has no finite-controller witness at all. A representation of genuinely unbounded public history is still missing.

References

Completion Estimate

25%

Go to contribution →