we-solve (beta)

Econ-79 · economics · Economics

Pure positional equilibria in multiplayer reachability games

LLM status Open unverified

Statement

GT-031 | Qualitative and graph games

P | Source-reported pure positional existence question

Definitions and mathematical statement

Let $(V,E)$ be a finite directed graph with at least one outgoing edge at every vertex, and let $V=\bigsqcup_{i=1}^{n}V_i$ specify its controlling players. There are no stochastic vertices. Each player has a target $T_i\subseteq V$. A behavioral strategy chooses a distribution over successors at every finite vertex history ending in $V_i$. A pure positional strategy is a function $f_i:V_i\to V$ with $(v,f_i(v))\in E$. For initial vertex $v_0$, the payoff is \[ u_i^{v_0}(\sigma)=\Pr_{v_0,\sigma}(\exists t\geq0:\ v_t\in T_i). \] The question is \[ \forall n\geq2\ \forall(V,E,(V_i),(T_i))\ \forall v_0\in V \quad\exists(f_i)_{i=1}^{n}\quad\forall i\ \forall\tau_i, \qquad u_i^{v_0}(\tau_i,f_{-i})\leq u_i^{v_0}(f), \] where deviations may be arbitrary randomized history-dependent strategies.

Short English statement

Does every finite deterministic turn-based multiplayer reachability game have a Nash equilibrium using only the current vertex and no randomization?

Variants and scope boundaries

An everywhere Nash equilibrium uses one profile satisfying the Nash inequalities from every vertex, with each objective started afresh. A positional SPE must satisfy the continuation inequalities after every feasible history and retain earlier target visits. These are separate stronger targets. Randomized memoryless strategies are not positional in the source's terminology. Absorbing targets form a special positive subcase, not the unrestricted model.

Source relationship and status

[S1], Section 5, expressly leaves reachability-only pure positional NE and stronger refinements open. Its positive results for randomized stationary equilibria do not settle this question. Theorem 10 proves a positional SPE under additional absorption assumptions.

References

[S1] Mona Alluwaym, James C. A. Main and Sven Schewe, Simple Nash Equilibria for Qualitative Multiplayer Games, MFCS 2026, LIPIcs 386, Article 85, pp. 85:1--85:17, doi:10.4230/LIPIcs.MFCS.2026.85. Locators: Section 2, pp. 85:4--85:5 (strategy and refinement definitions); Theorem 10 and Section 5, p. 85:14 (special absorption result and open positional cases). https://drops.dagstuhl.de/storage/00lipics/lipics-vol386-mfcs2026/LIPIcs.MFCS.2026.85/LIPIcs.MFCS.2026.85.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 1

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

GPT 6 Astra Ultra attempt on Econ-79

Pure positional equilibria in multiplayer reachability games: Pure equilibria when every strongly connected component has one owner

In a finite deterministic turn-based arena, player $i$ wants to visit its target $T_i$. A pure positional profile $f$ is required to defeat all unilateral behavioral deviations from a given initial state: \[ \Pr_{v_0,(\tau_i,f_{-i})}(\exists t:v_t\in T_i) \leq\Pr_{v_0,f}(\exists t:v_t\in T_i). \] The result below supplies a structural subclass allowing arbitrary target locations, including nonabsorbing targets. It also gives an exact certificate for testing proposed positional profiles.

Lemma (Testing a proposed profile): For a pure positional profile $f$, form $G_i(f)$ by retaining all outgoing edges at vertices owned by $i$ and only the edge selected by $f$ at every other vertex. Then $f$ is a Nash equilibrium from $v_0$ if and only if, for each player whose $f$-outcome never visits $T_i$, no vertex in $T_i$ is reachable from $v_0$ in $G_i(f)$.
Proof: A player already attaining payoff one cannot improve. If a losing player has a target-reaching path in $G_i(f)$, delete loops to obtain a simple path. Its choices along this path define a deterministic positional deviation reaching the target, and thus a profitable behavioral deviation. Conversely, every possible finite target-reaching prefix under a behavioral deviation uses only edges of $G_i(f)$. If the target is unreachable there, no randomization or history dependence can give positive reaching probability. This proves both directions. ∎
Theorem (One owner per component): Let the arena be finite and nonblocking. Suppose that for every strongly connected component $K$ there is a player $c(K)$ owning every vertex of $K$. Then a pure positional profile exists that is a Nash equilibrium from every fresh initial vertex. It can be constructed by processing the component graph in reverse topological order and solving finite one-player reachability problems.
Proof: The directed graph of strongly connected components is acyclic. Suppose strategies have already been fixed on all components strictly downstream of $K$, and that their combined profile is a Nash equilibrium from every vertex in that downstream subgraph. Let $c=c(K)$.

On $K$, only player $c$ makes choices. Treat an exit to a downstream vertex $w$ as successful for $c$ if the already fixed continuation from $w$ reaches $T_c$. Also treat every vertex of $K\cap T_c$ as successful immediately. Standard finite graph reachability gives a simultaneous optimal positional policy for this one-player problem: for every vertex that can reach one of these successes, select an edge decreasing a shortest-path distance until success is reached. At successful target vertices choose any legal continuation; reaching has already occurred. Vertices unable to reach a success cannot have an edge to a successful-reachable vertex, so arbitrary legal choices there cannot destroy the optimality just described. Combine this policy with the fixed downstream profile.

To check a deviation by $c$, if its original outcome from a vertex of $K$ loses, the one-player construction says it cannot reach a local target or an exit with a winning fixed continuation. At a losing exit $w$, the downstream equilibrium says that $c$ cannot improve by changing its downstream choices either. Thus no deviation, including one changing both local and downstream decisions, wins. This can also be seen from the preceding graph criterion: any deviating target-reaching path would either reach a local target or use a first exit from which a downstream deviation reaches the target, both excluded.

For a player $i\neq c$, a unilateral deviation cannot change the path inside $K$. That path either stays in $K$ forever, in which case the deviation changes nothing, or reaches a fixed first downstream exit $w$. If $T_i$ was visited before the exit, payoff is already one. If not, the downstream Nash property at $w$ rules out an improvement. Randomized deviations add no possibilities by the lemma. This verifies equilibrium at every vertex of $K$ and preserves it downstream. Induction over all components proves the theorem. ∎

Remark (Nonabsorbing targets are allowed): The proof never makes targets absorbing in the actual arena. The temporary success labels are used only while solving the current owner's local reachability problem. A target vertex may lead to another player's component; already reached players are indifferent to that continuation. The theorem guarantees one profile that is Nash from every fresh initial vertex, but makes no separate claim of subgame perfection with arbitrary past target visits.
Source relationship and remaining gap.
Alluwaym, Main, and Schewe [source], Section 5, retain the general pure-positional question; their randomized stationary result and absorption theorem concern different restrictions. The component argument above is a direct restricted derivation. If a component contains vertices of several owners, a deviator can change the exit and revisit earlier decision vertices controlled by other players. The backward induction then ceases to be a one-player optimization, and no general positional existence proof is supplied.

References

Completion Estimate

20%

Go to contribution →