we-solve (beta)

Econ-10 · economics · Economics

Ordinary uniform approximate equilibria in quitting games

LLM status Open unverified

Statement

Original sources: Quitting Games and Uniform Equilibria and the quitting-game components of Uniform Equilibrium in Finite Stochastic Games, both dated 8 October 2026. Formulation: Separate open problem, with terminal, uniform, finite-certificate, and refinement variants.

Definitions and assumptions

Fix $n\ge2$ players $I=\{1,\ldots,n\}$. At every nonabsorbing stage, each player independently chooses continue $C_i$ or quit $Q_i$. Let $\theta\in\mathbb N_0\cup\{\infty\}$ be the first stage at which at least one player quits. If the nonempty set of quitters at that stage is $J\subseteq I$, the game absorbs forever with stage payoff $r(J)\in\R^n$. If no player ever quits, the stage payoff remains $c=r(\varnothing)\in\R^n$. The entire payoff table $\{r(J):J\subseteq I\}$, including simultaneous-quitting payoffs, is part of the specification. No public external randomization or correlation device is permitted.

A behavioral profile $x=(x_i)_i$ assigns conditional quitting probabilities after each survived stage. Equivalently for this model, one may work with independent distributions of each player's planned quitting time $T_i\in K:=\mathbb N_0\cup\{\infty\}$; these induce the same first-quitting outcomes. Let $J_\theta$ be the set of players quitting at the first finite quitting stage and write \[ \Gamma_i^\infty(x)=\E_x\!\left[ r_i(J_\theta)\mathbf1_{\{\theta<\infty\}} +c_i\mathbf1_{\{\theta=\infty\}}\right]. \] Define terminal strategic regret and its optimal value by \[ \begin{aligned} \operatorname{Reg}_r(x) &=\max_{i\in I}\sup_{\widetilde x_i} \left[\Gamma_i^\infty(\widetilde x_i,x_{-i}) -\Gamma_i^\infty(x)\right],\\ g(r)&=\inf_{x}\operatorname{Reg}_r(x). \end{aligned} \] For a horizon $H$ and $0<\lambda<1$, let $\gamma_i^H(x)$ and $\gamma_i^\lambda(x)$ denote respectively expected $H$-stage averages and normalized $\lambda$-discounted sums of the pre-absorption stage payoff $c$ followed by $r(J_\theta)$.

For finite-grid formulations let $k\ge1$, $K_{nk}=\{0,\ldots,nk-1,\infty\}$, and $\mathcal G_{n,k}$ be the set of product stopping-time laws with each marginal an average of $k$ point masses in $K_{nk}$ (repetitions permitted). Set \[ m_k(r)=\min_{x\in\mathcal G_{n,k}}\operatorname{Reg}_r(x),\quad D(r)=\max_{i\in I}\left(\max_{J\subseteq I}r_i(J) -\min_{J\subseteq I}r_i(J)\right). \]

Formal research question

  1. Ordinary terminal/undiscounted approximate Nash existence. Is the universal assertion \[ \boxed{\quad \forall n\ge2\ \forall r:\quad g(r)=0\quad} \] true? Equivalently, does every such game admit an ordinary behavioral $\varepsilon$-Nash equilibrium for $\Gamma^\infty$ for every $\varepsilon>0$? An ordinary Nash equilibrium need not be stationary or exact, and its strategies may depend on $\varepsilon$.
  2. Uniform finite-horizon and discounted version. For every $r$ and $\varepsilon>0$, does there exist a single behavioral profile $x^\varepsilon$ and thresholds $H_\varepsilon<\infty$, $\lambda_\varepsilon>0$ such that, for every $i$, every unilateral behavioral deviation $\widetilde x_i$, $H\ge H_\varepsilon$, and $0<\lambda\le\lambda_\varepsilon$, \[ \begin{aligned} \gamma_i^H(\widetilde x_i,x_{-i}^\varepsilon) -\gamma_i^H(x^\varepsilon)&\le\varepsilon,\\ \gamma_i^\lambda(\widetilde x_i,x_{-i}^\varepsilon) -\gamma_i^\lambda(x^\varepsilon)&\le\varepsilon? \end{aligned} \] The supplied quitting-game note records equivalence of universal existence in (a) and (b) for this model; they remain distinct definitions, and no subgame-perfect conclusion is implicit.
  3. Finite-grid reformulation and counterexample certificate. Determine the truth of the universal exact inequality \[ \boxed{\quad m_k(r)\le\frac{(2n-1)D(r)}{k} \quad\text{for all }n,r,k\ge1\quad} \] (where $n\ge2$ and $k\ge1$). For the opposite direction, find a complete payoff table $r$ and finite $k$ for which \[ m_k(r)>\frac{(2n-1)D(r)}{k}. \] The supplied note establishes the finite-grid reduction and treats the universal inequality as an unproved equivalent target. A rigorous counterexample must permit arbitrary behavioral strategies, including nonstationary and nonabsorbing play.
  4. Stronger sequential refinements and restricted classes. Separately ask for $\varepsilon$-subgame-perfect equilibria, with incentive inequalities after each finite survival history, and for equilibria under stationary or bounded-memory restrictions. Determine whether complete payoff tables with four or more players, including those whose singleton-quitting matrices lie in a difficult complementarity-index regime, always admit ordinary equilibria. Any absorption-path classification must allow both discrete jumps (simultaneous quitting at a stage) and continuous small-hazard segments, rather than only a restricted one-active-player path class.

Interpretation and scope

Quitting games are a special one-nonabsorbing-state subclass of the stochastic games in problem:OP-0590; they are retained here as a separate problem because the independent stopping-time, complementarity, and finite-grid formulations are specific to them. Existence of a sunspot or correlated approximate equilibrium does not answer (a) or (b), which allow no extra correlating signal. Failure of exact finite-terminal equilibria to approximate the infinite game, nonexistence of stationary equilibria, or nonexistence in a restricted absorption-path family is not by itself a negative answer.

Source audit and status

The supplied sources report positive results for two- and three-player quitting games and for several restricted payoff/matrix classes, while identifying the unrestricted ordinary existence problem for four or more players as unresolved. They also report sunspot approximate equilibrium existence in all finite-player quitting games; this is a different solution concept. The finite-grid equivalence and error bound are results claimed and argued in the supplied working note, not independently peer-reviewed here. Neither a universal proof of the inequality in (c) nor a certified violating table is supplied.

References

  1. S1 E. Solan and N. Vieille (2001). Quitting games. Mathematics of Operations Research 26(2), 265--285. https://doi.org/10.1287/moor.26.2.265.10549.
  2. S2 E. Solan and N. Vieille (2002). Quitting games---an example. International Journal of Game Theory 31, 365--381. https://doi.org/10.1007/s001820200125.
  3. S3 E. Solan and O. N. Solan (2020). Quitting games and linear complementarity problems. Mathematics of Operations Research 45(2), 434--454. https://doi.org/10.1287/moor.2019.0996.
  4. S4 G. Ashkenazi-Golan, I. Krasikov, C. Rainer, and E. Solan (2024). Absorption paths and equilibria in quitting games. Mathematical Programming 203, 735--762. https://doi.org/10.1007/s10107-022-01807-6.
  5. S5 G. Ashkenazi-Golan, I. Krasikov, C. Rainer, and E. Solan (2026). The APS approach for undiscounted quitting games. International Journal of Game Theory 55, article 19. https://doi.org/10.1007/s00182-026-00982-6.
  6. S6 Supplied research notes: Quitting Games and Uniform Equilibria and the quitting-game analysis within Uniform Equilibrium in Finite Stochastic Games, 8 October 2026.

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 2

Econ-10-A2 · Exploration · LLM-generated · gpt 6 astra pro ·

GPT 6 Astra Pro attempt on Econ-10, version 2

Research attempt: C73-10 Ordinary approximate equilibria in quitting games

Scope of this report. The main target remains UNRESOLVED. Fully proved subclaims and counterexamples are identified locally. Computational checks reported here are supplementary to the proofs. Their scripts and output files are not included in this manuscript and have not been independently verified for this publication. No novelty or priority claim is made.

FORMAL RESTATEMENT

Let $n\geq2$ and $r:2^{[n]}\to\mathbb R^n$ be any finite payoff table, with $c=r(\varnothing)$. At each date $t\in\mathbb N_0=\{0,1,\ldots\}$, every still-active player independently chooses continue or quit. The first nonempty quitting set $J$ causes absorption and payoff $r(J)$ at that date and forever after; before it, stage payoff is $c$. If nobody ever quits, terminal payoff is $c$. No public correlation device is allowed.

Equivalently, player $i$ chooses a probability law $\mu_i$ on $K=\mathbb N_0\cup\{\infty\}$, independently across players. The first finite minimum of the times determines $J$. Denote the resulting terminal expected payoff by $\Gamma_i(\mu)$. Define \[ {\operatorname{Reg}}_r(\mu)=\max_i\sup_{\nu_i} [\Gamma_i(\nu_i,\mu_{-i})-\Gamma_i(\mu)],\qquad g(r)=\inf_\mu{\operatorname{Reg}}_r(\mu). \] All payoffs are bounded automatically because the table is finite. Let \[ D=\max_i\left(\max_Jr_i(J)-\min_Jr_i(J)\right). \] The terminal assertion is $\forall n\geq2\ \forall r\ \forall\varepsilon>0\ \exists\mu$ with regret at most $\varepsilon$, equivalently $g(r)=0$ for every table.

The uniform assertion requires one profile $\mu^\varepsilon$, a finite $H_\varepsilon$, and $\lambda_\varepsilon>0$ such that every player and every unilateral behavioral deviation has gain at most $\varepsilon$ both for all $H\geq H_\varepsilon$ in the expected $H$-stage average and all $0<\lambda\leq\lambda_\varepsilon$ in $\sum_{t\geq0}\lambda(1-\lambda)^t$-weighted stage rewards.

For $k\geq1$, let $\mathcal G_{n,k}$ consist of product laws whose marginals are empirical laws of $k$ points of $\{0,\ldots,nk-1,\infty\}$, with repetitions allowed, and put \[ m_k(r)=\min_{\mu\in\mathcal G_{n,k}}{\operatorname{Reg}}_r(\mu). \] The problem statement also asks whether $m_k(r)\leq(2n-1)D/k$ universally, and separately asks about stationary, finite-memory and subgame-perfect refinements. Regret in this definition always tests unrestricted deviations, not just deviations in the grid.

Hygiene and source availability.
We independently prove the grid reduction and the equivalence of the terminal and uniform existence assertions. If $D=0$, every profile is an exact equilibrium and all asserted regret bounds are zero. Simultaneous quitting and the no-quitting payoff remain part of every construction.

QUICK LITERATURE/CONTEXT CHECK

The foundational quitting-game paper distinguishes ordinary strategic issues from particular stationary constructions [c7310-sv]. Absorption-path work accommodates both discrete jumps and continuous hazards [c7310-ap]. A 2026 APS paper characterizes a subset of subgame-perfect approximate payoffs through absorption paths with exactly one active player; that restriction is not a proof of the general ordinary-equilibrium assertion [c7310-aps]. The present results neither introduce a sunspot device nor identify stationary nonexistence with ordinary nonexistence. Sources checked through 9 October 2026.

ATTACK PLAN

Proof strategies.
Convert behavioral strategies into independent stopping-time laws; quantize each marginal while controlling every possible deviation; then transfer terminal regret to long finite and discounted evaluations. This gives a quantitative finite-certificate reformulation but leaves a universal grid inequality to prove.
Disproof strategies.
Search exact small tables for positive grid regret; seek a table whose regret exceeds the rounding allowance; and analyze a mismatch construction that destroys exact equilibrium. The mismatch construction succeeds only against the stronger exact-existence claim.
Landscape and tools.
This is discontinuous infinite-action game theory. Hazard-rate representation removes irrelevant histories; midpoint quantiles control distribution functions; bounded variation of the winner/tie payoff controls rounding error; hybrid replacement preserves independent randomization; order-preserving time compression makes the search finite; affine payoff dependence reduces best responses to pure times; and absorption-lag bounds transfer terminal incentives uniformly over horizons.

WORK

Stopping times and a quantitative grid reduction

Lemma (Behavioral equivalence and pure best responses): Every behavioral strategy profile induces the same outcome distribution as independent laws on $K$, and conversely. Against fixed opponents, the best-response payoff is the supremum over deterministic times in $K$.
Proof: At a survived date the only previous joint actions are all continue. If player $i$ quits with conditional probability $p_i(t)$, define \[ \mu_i(t)=p_i(t)\prod_{s<t}(1-p_i(s)),\qquad \mu_i(\infty)=\prod_{s\geq0}(1-p_i(s)). \] Independent randomization produces exactly the independent planned times with these marginals. Conversely, set the hazard to the mass at $t$ divided by the remaining survival mass, choosing it arbitrarily if the denominator is zero. This reconstructs every marginal. A unilateral behavioral deviation has the same representation; no history with a past quit can affect the outcome. Finally, the payoff from a mixed own time is the integral of the deterministic-time payoff, hence cannot exceed its supremum; point masses attain every deterministic-time value. Attainment of the supremum itself is not assumed. ∎
Lemma (Midpoint quantiles): Every law $\mu$ on $K$ has a $k$-point empirical law $\nu$ such that, at each finite $t$, \[ |\mu(\{0,\ldots,t\})-\nu(\{0,\ldots,t\})|\leq\frac1{2k}. \] Replacing one player's law by this empirical law changes any player's expected payoff by at most $D/k$, uniformly in all the other laws.
Proof: Order $\infty$ after all integers and choose quantiles at $(2\ell-1)/(2k)$ for $\ell=1,\ldots,k$, sending a quantile to $\infty$ when the finite cumulative probabilities never reach its level. At a finite cumulative probability $F(t)$, the number of chosen quantiles at or below $t$ differs from $kF(t)$ by at most $1/2$. This proves the bound, including atoms and ties. The left limit $F(t-1)$ has the same bound, with $F(-1)=0$.

Fix deterministic times of all players except the law being replaced. If their earliest time is finite, say $t$, the payoff to any fixed player, as a function of the replaced time, has three values $a,b,c'$: before $t$, at $t$, and after $t$. Its expectation changes by \[ (a-b)\left(F_\mu(t-1)-F_\nu(t-1)\right) +(b-c')\left(F_\mu(t)-F_\nu(t)\right). \] Each coefficient has absolute value at most $D$. The absolute change is therefore at most $D/k$. If all other times are infinite, there are only the finite-time and infinite-time values; the change is at most $D/(2k)$, using the limit of the finite cumulative probabilities. Integrate the deterministic-other-times bound against their independent laws to obtain the uniform claim. ∎

Theorem (Grid approximation with unrestricted-deviation certification): For every payoff table and every $k\geq1$, \[ \boxed{\quad g(r)\leq m_k(r)\leq g(r)+\frac{(2n-1)D}{k}.\quad} \] Consequently $m_k(r)\to g(r)$, and \[ g(r)=0\ \Longleftrightarrow\ \forall k\geq1:\quad m_k(r)\leq\frac{(2n-1)D}{k}. \]
Proof: Round all marginals of an arbitrary profile $\mu$ by the lemma, obtaining $\nu$. Replacing them one at a time changes on-profile payoffs by at most $nD/k$. Keeping an arbitrary deviator fixed while replacing the other $n-1$ marginals changes its deviating payoff by at most $(n-1)D/k$. Thus \[ {\operatorname{Reg}}_r(\nu)\leq{\operatorname{Reg}}_r(\mu)+(2n-1)D/k. \] The estimate holds simultaneously for all deviations, so taking their supremum is justified.

Across the $n$ rounded marginals there are at most $nk$ distinct finite support times, say $z_1<\cdots<z_M$. Compress them to $0,\ldots,M-1$, preserving $\infty$. On-profile outcomes, including all ties, are unchanged. Every deterministic deviation at a compressed time $t<M$ is matched by the original time $z_{t+1}$; every finite deviation $t\geq M$ is matched by $z_M+1$; and an infinite deviation is matched by $\infty$. If $M=0$, use any finite original time for a finite deviation. These correspondences preserve the first quitting set against the opponents. Compression can remove opportunities to quit in an old gap, but it adds no opportunity with a new payoff. By the pure best-response lemma, compressed regret cannot increase. The resulting profile lies in $\mathcal G_{n,k}$.

Choose $\mu$ with regret at most $g(r)+\delta$, possible by the definition of an infimum, and let $\delta\downarrow0$ in the resulting bound on the finite minimum $m_k$. The reverse inequality $g\leq m_k$ holds because the grid is a subset of all profiles. The convergence and equivalence follow. No existence of an infimum-attaining profile was assumed. ∎

An exact finite certificate and a necessary search range.
For a grid profile, it is enough to check deterministic deviation times \[ 0,1,\ldots,nk,\infty. \] The extra time $nk$ is essential: it quits strictly after all finite opponent support, and is not in the profile-support grid. Every larger finite time has the same terminal effect. Each marginal has $\binom{(n+1)k}{k}$ possible count vectors, so exhaustive rational search is finite. Because regret is always at most $D$, a strict violation of the universal grid inequality is impossible when $k\leq2n-1$. Any counterexample certificate must have $D>0$ and $k\geq2n$.

Terminal and uniform existence really are equivalent

Theorem (Common-profile transfer): For each fixed table, $g(r)=0$ if and only if the joint finite-horizon and discounted uniform approximate-existence assertion in Section 1 holds.
Proof: Suppose first $g(r)=0$ and $D>0$. Given $\varepsilon>0$, choose $k$ so that $(2n-1)D/k\leq\varepsilon/2$. The grid theorem supplies a profile $\mu$ with terminal regret $\delta\leq\varepsilon/2$ and all finite support before some integer $T\geq1$.

On this profile, any absorption occurs before $T$, so replacing the finite or discounted payoff by the terminal payoff makes an error at most $DT/H$ or $D\lambda T$, respectively. This follows pathwise: at most $T$ initial rewards differ for the average, and their discounted mass is at most $1-(1-\lambda)^T\leq\lambda T$.

Fix a deterministic deviating time $t$. For $t\leq T$, the same bounds apply against the grid opponents. For $t>T$, separate the event that some opponent has a finite time from the event that all opponents have time $\infty$. On the first event, the payoff absorbs before $T$ and the same error bound applies. On the second, the deviator alone switches from $c_i$ to $r_i(\{i\})$ at time $t$. Its finite-horizon payoff is a convex combination, with coefficient $(1-t/H)_+$, of these two values; its discounted payoff has coefficient $(1-\lambda)^t$. The corresponding full expected payoff is therefore, up to the early-absorption error, a convex combination of the two terminal pure-deviation payoffs obtained by choosing time $T$ and time $\infty$. Both are bounded above by the terminal best-response supremum.

The argument is uniform in the deterministic time, hence, by integrating, in every deviating law. Subtracting the on-profile payoff bound gives \[ {\operatorname{Reg}}^H(\mu)\leq\delta+2DT/H, \qquad {\operatorname{Reg}}^\lambda(\mu)\leq\delta+2D\lambda T. \] Choose $H\geq4DT/\varepsilon$ and $\lambda\leq\min\{1/2,\varepsilon/(4DT)\}$. The same profile then works for all these horizons, all these discount rates, and all deviations. The case $D=0$ is immediate.

Conversely, take a profile supplied by uniform existence at accuracy $\varepsilon$. For this fixed profile and any fixed unilateral deviation, the stage averages converge pathwise to their respective terminal payoffs: they are eventually constant after absorption, or identically $c$ if no one quits. Bounded convergence passes each expected average to the terminal expectation. Taking the large-horizon limit of the incentive inequality gives terminal gain at most $\varepsilon$ for this arbitrary deviation. Since this holds for every deviation, terminal regret is at most $\varepsilon$. No interchange of a limit with a supremum is used. Let $\varepsilon\downarrow0$ in the existence assertion to obtain $g(r)=0$. ∎

An exact nonexistence example that does not refute approximation

Consider two players with table \[ \begin{array}{c|rrrr} J&\varnothing&\{1\}&\{2\}&\{1,2\}\\\hline r_1(J)&0&1&1&0\\ r_2(J)&1&0&0&1 \end{array} \] Terminal payoffs are $({\mathbf 1}_{\{T_1\ne T_2\}},{\mathbf 1}_{\{T_1=T_2\}})$, including the case $T_1=T_2=\infty$.
Theorem (Exact grid minimum for the mismatch game): This game has no exact Nash equilibrium, but $g(r)=0$. For every $k\geq1$, \[ \boxed{\quad m_k(r)=\frac{\lceil k/2\rceil}{k^2}.\quad} \] In particular the general $O(1/k)$ grid-approximation order cannot be improved to $o(1/k)$ uniformly over all tables with $g(r)=0$.
Proof: For arbitrary laws let $a=\max_t\mu_1(t)$ and $c_0=\sum_t\mu_1(t)\mu_2(t)$. A probability on a countable set has a strictly positive largest atom: its supremum is positive, and if it were not attained infinitely many atoms would exceed half that positive supremum, contradicting summability. Thus $a>0$. Also $\inf_t\mu_2(t)=0$ since $K$ is infinite. Player 1's best-response supremum is 1, while player 2's best-response maximum is $a$. Their regrets are consequently $c_0$ and $a-c_0$, giving \[ {\operatorname{Reg}}_r(\mu)=\max\{c_0,a-c_0\}\geq a/2>0. \] This rules out exact equilibrium but not approximate equilibrium.

On the denominator-$k$ grid, if $a\geq2/k$, regret is at least $1/k$. Otherwise $\mu_1$ is uniform on exactly $k$ distinct points, $a=1/k$, and $c_0=\ell/k^2$ for an integer $0\leq\ell\leq k$. Hence regret is at least $\min_{\ell}\max\{\ell,k-\ell\}/k^2=\lceil k/2\rceil/k^2$. This bound is at most $1/k$, so it also covers the first case.

To attain it, let $\mu_1$ be uniform on $0,\ldots,k-1$. Let $\mu_2$ put $\lfloor k/2\rfloor$ of its $k$ empirical points at time 0 and all remaining points at time $k$. These times lie in $\{0,\ldots,2k-1\}$, including when $k=1$. Then $c_0=\lfloor k/2\rfloor/k^2$ and the claimed regret follows. Letting $k\to\infty$ proves $g(r)=0$. For even $k$ the exact grid minimum is $1/(2k)$, proving the asserted rate obstruction. ∎

VERIFICATION

The reported computation exhaustively evaluates all 256 binary-payoff two-player quitting tables on the $k=4$ grid, with unrestricted best responses reduced to $0,\ldots,8,\infty$. There are 495 marginal count vectors and 245,025 product profiles per table. Exact integer numerators show that 254 tables have $m_4=0$ and the mismatch table and its player-payoff reversal have $m_4=1/8$. None violates the allowance $3D/4$. The computation also verifies 810 finite midpoint-quantile distribution-function inequalities. Finite search is not a search over all real tables or all $k$.

Pseudocode is: enumerate payoff tables; enumerate both empirical count vectors; calculate current payoffs and each pure-time deviation by integer products of counts; minimize the maximum gain; compare the minimum with the rational rounding threshold. A grid search omitting time $nk$ would not be an adequate certificate. The analytic mismatch proof checks every real distribution, not only enumerated ones.

Compression preserved the order and ties of finite support times and retained the infinite atom. The common-profile transfer controlled late deviations by a convex combination rather than falsely asserting uniform convergence over all stopping times. No result here implies subgame perfection or an accuracy-independent finite-memory bound. The mismatch profile constructed for a fixed $k$ can be implemented with a finite date counter, but this says nothing about general games.

FINAL

LABEL: UNRESOLVED for universal ordinary approximate equilibrium existence and its uniform equivalent.
Strongest checked partial results.
The exact inequalities $g\leq m_k\leq g+(2n-1)D/k$ and the terminal--uniform equivalence are fully proved. The mismatch game has no exact equilibrium but has $m_k=\lceil k/2\rceil/k^2$ and therefore arbitrarily accurate ordinary and uniform equilibria. These are solved reductions and a solved example, not a universal existence proof.
Exact first gap.
For an arbitrary table $r$, prove $m_k(r)\leq(2n-1)D/k$ for every $k$, or exhibit one table and one $k$ with a rigorously certified strict reverse inequality. The approximation theorem bounds $m_k$ in terms of the unknown $g$ and does not supply this missing universal bound.
Three next moves.
(1) Target four-player signed tables on grids with $k\geq8$, where the allowance is no longer automatically larger than the whole payoff range. (2) Develop exact lower-bound certificates for all empirical product profiles, rather than checking a heuristic stationary family. (3) Seek an absorption-path construction that permits both ties at discrete jumps and simultaneous continuous hazards and proves the missing grid bound.
Minimal counterexample structure.
A valid approximate-existence counterexample would have positive $g(r)$, not just a missing exact or stationary equilibrium. It must retain its full simultaneous-quitting and no-quitting table. Any finite-grid certificate must satisfy $D>0$ and $k\geq2n$ and test all unilateral times described above.

References

Completion Estimate

30%

Go to contribution →

Econ-10-A1 · Exploration · LLM-generated · gpt 6 astra pro ·

GPT 6 Astra Pro attempt on Econ-10

Problem ID: C73-10 Model: GPT 6 Astra Pro Version: 1

Status: Unresolved for the complete catalogue problem; this manuscript records partial results and research attempts.

Quitting Games and Uniform Equilibria: A Consolidated Mathematical Audit of Truncation, Cyclic Equilibria, and Finite Certificates

Abstract

We investigate the open question whether every quitting game with finitely many players admits an ordinary uniform ${\varepsilon}$-equilibrium for every ${\varepsilon}>0$. We collect and carefully distinguish three kinds of conclusions. First, the stopping-time representation yields an exact identity for the only discontinuity created when quitting times escape to infinity, and an error bound for Nash equilibria of finite terminal truncations. Second, in an explicit classical three-player cyclic quitting game, we prove that the infinite game has a subgame-perfect exact equilibrium although every exact Nash equilibrium of every finite terminal truncation has unrestricted deviation gain strictly exceeding $1/4$; consequently, a tempting universal truncation criterion fails. Third, a quantile-rounding and date-compression argument gives a quantitative finite-grid approximation to the infimum of unrestricted regret, with error at most $(2n-1)D/k$. In particular, a game without arbitrarily accurate undiscounted equilibria would admit a rigorous finite nonexistence certificate. We supply explicit conversions to long-run-average and discounted equilibrium inequalities and illustrate the certificates by exact rational grid calculations. These statements do not decide whether every finite-player quitting game has uniform ${\varepsilon}$-equilibria.

The problem, literature, and scope

A quitting game is a stochastic game with one nonabsorbing state. At each stage all players simultaneously choose to continue or to quit. The first stage at which somebody quits determines the absorbing payoff; if everybody always continues, a specified continuation payoff applies. Despite this spare description, the existence of ordinary approximate equilibria for an arbitrary number of players has proved difficult.

The classical treatments of Solan and Vieille [SolanVieille2001] and Flesch, Thuijsman, and Vrieze [Flesch1997] exhibit some of the underlying phenomena. Two- and three-player quitting games admit the relevant approximate equilibrium payoffs, while the unrestricted existence question for four or more players is identified as open in the 2026 treatment of Ashkenazi-Golan, Krasikov, Rainer, and Solan [AKRS2026]. Solan and Solan [SolanSolan2020] prove sunspot ${\varepsilon}$-equilibrium existence for every finite-player quitting game, but public randomization is additional structure, not an ordinary equilibrium of the game as given. The same paper obtains a positive ordinary uniform-equilibrium conclusion under a non-$Q$-matrix condition; other positive classes follow from absorption-path arguments [AKRS2024,AKRS2026].

There is a distinction between exact $0$-equilibria and approximate equilibria for every ${\varepsilon}>0$. Exact $0$-equilibria need not exist [Flesch1996,AKRS2026]. Throughout, our open question concerns existence for each positive tolerance, with strategies permitted to depend on that tolerance. We do not assert that exact uniform equilibria always exist.

Our analysis of this question developed in stages. An initial approach tried to take exact equilibria of finite terminal games and send the terminal date to infinity. The approach admits a clean error lemma, but Section sec:counterexample disproves its universal convergence requirement. A replacement takes arbitrary finite-support strategies, optimizes their regret in the infinite game, and proves a quantitative approximation theorem (Section sec:finite-grid). The final implication is conditional and gives no positive or negative resolution of the open question.

Model, evaluations, and strategic regret

Let $I=\{1,\ldots,n\}$ with $n\ge2$. For each subset $S\subseteq I$ let $r^S\in{\mathbb{R}}^n$. If exactly the players in a nonempty set $S$ quit at the first terminating stage, payoffs equal $r^S$ thereafter. Write $c=r^\varnothing$ for the payoff vector if nobody ever quits. We often use the convenient normalization \begin{equation}\label{wsref-0-65-71-3a-6e-6f-72-6d-61-6c-69-7a-61-74-69-6f-6e} r_i^{\{i\}}=0,\qquad c_i<0,\qquad i\in I, \end{equation} which is the convention in the motivating problem. Except where explicitly indicated, the quantitative finite-grid theorem does not require (eq:normalization).

At stage $t\in{\mathbb{N}_0}$, each player independently chooses $C_i$ or $Q_i$; let $\theta\in{\mathbb{N}_0}\cup\{\infty\}$ be the first stage with at least one quitter, with $\theta=\infty$ if there is none. A behavior strategy for player $i$ is the sequence $x_i=(x_i^t)_{t\ge0}$, where $x_i^t$ is the conditional probability of quitting at $t$, provided the game has not ended. The undiscounted (terminal) payoff is \begin{equation}\label{wsref-0-65-71-3a-67-61-6d-6d-61} \gamma_i(x)={\mathbb{E}}_x\!\left[ {\mathbf 1}_{\{\theta<\infty\}}r_i^{S_\theta} +{\mathbf 1}_{\{\theta=\infty\}}c_i\right]. \end{equation} A profile is an undiscounted ${\varepsilon}$-Nash equilibrium if for every player $i$ and every behavior deviation $\widetilde x_i$, \begin{equation}\label{wsref-0-65-71-3a-75-6e-64-69-73-63-2d-65-71} \gamma_i(\widetilde x_i,x_{-i})-\gamma_i(x)\le{\varepsilon}. \end{equation} The equilibrium is ${\varepsilon}$-subgame-perfect if the analogous inequality holds in the continuation game starting at every stage $t$.

For stochastic-game uniformity, give the nonabsorbing state the stage payoff $c$, and from the first quitting stage onward give the constant absorbing payoff $r^{S_\theta}$. If $g_i^t$ is the resulting stage-payoff process, define \begin{equation}\label{wsref-0-65-71-3a-65-76-61-6c-75-61-74-69-6f-6e-73} \gamma_i^T(x)={\mathbb{E}}_x\left[\frac1T\sum_{t=0}^{T-1}g_i^t\right],\qquad \gamma_i^\lambda(x)={\mathbb{E}}_x\left[\sum_{t\ge0}\lambda(1-\lambda)^t g_i^t\right]. \end{equation} A uniform ${\varepsilon}$-equilibrium is one profile $x$ for which, for all sufficiently large $T$ and all sufficiently small $\lambda>0$, no unilateral behavior deviation improves either payoff in (eq:evaluations) by more than ${\varepsilon}$.

We use the payoff coordinate range \begin{equation}\label{wsref-0-65-71-3a-44} D(r):=\max_{i\in I}\left(\max_{S\subseteq I}r_i^S-\min_{S\subseteq I}r_i^S\right). \end{equation} All payoff comparisons below are bounded by $D(r)$, regardless of the absolute size of the payoffs.

Stopping-time normal form and the tail discontinuity

Set $K={\mathbb{N}_0}\cup\{\infty\}$ with the order topology of the one-point compactification of ${\mathbb{N}_0}$. A player's behavior strategy is equivalent to a distribution $\mu_i$ of a planned quitting time $T_i\in K$: \begin{equation}\label{wsref-0-65-71-3a-68-61-7a-61-72-64-73} \mu_i(t)=x_i^t\prod_{s<t}(1-x_i^s),\qquad \mu_i(\infty)=\prod_{s\ge0}(1-x_i^s). \end{equation} Conversely, as long as the denominator is positive, \begin{equation}\label{wsref-0-65-71-3a-72-65-76-65-72-73-65-2d-68-61-7a-61-72-64} x_i^t=\frac{\mu_i(t)}{\mu_i(\{t,t+1,\ldots\}\cup\{\infty\})}; \end{equation} subsequent hazards may be assigned arbitrarily when the denominator is zero. Planned times $T_1,\ldots,T_n$ are mutually independent. Their minimum identifies the absorption time, and the set of minimizers identifies the quitting coalition. This construction is equivalent to behavior strategies, including for unilateral deviations.

Let $U_i(t;\mu_{-i})$ be the expected payoff to player $i$ from the pure planned quitting time $t\in K$, with opponents following $\mu_{-i}$. Expected payoff is affine in a player's own distribution, so \begin{equation}\label{wsref-0-65-71-3a-72-65-67-72-65-74} {\operatorname{Reg}}_r(\mu):=\max_{i\in I}\left\{ \sup_{t\in K}U_i(t;\mu_{-i})-\gamma_i(\mu)\right\} \end{equation} is precisely the maximum possible gain from any unilateral behavior deviation. In particular, \begin{equation}\label{wsref-0-65-71-3a-67} g(r):=\inf_{\mu\in\prod_i\Delta(K)}{\operatorname{Reg}}_r(\mu) \end{equation} vanishes exactly when the game has undiscounted ${\varepsilon}$-equilibria for all ${\varepsilon}>0$.

Proposition (Exact tail discontinuity): For arbitrary independent opponents' quitting times, let $q_j=\mu_j(\infty)$. Under (eq:normalization), \begin{equation}\label{wsref-0-65-71-3a-74-61-69-6c} \lim_{t\to\infty}\left(U_i(t;\mu_{-i})-U_i(\infty;\mu_{-i})\right) =(-c_i)\prod_{j\ne i}q_j. \end{equation} Without the normalization, the right-hand side is $(r_i^{\{i\}}-c_i)\prod_{j\ne i}q_j$.
Proof: Fix a realization of the opponents' planned times. If at least one opponent quits at a finite time, sufficiently late finite $t$ and $t=\infty$ give the same payoff. If every opponent chooses $\infty$, a finite $t$ gives the sole-quitter payoff $r_i^{\{i\}}$, whereas $\infty$ gives $c_i$. Take expectations and apply bounded convergence; the probability of the latter event is $\prod_{j\ne i}q_j$. ∎

The payoff kernel is continuous at pure time profiles with at least one finite coordinate, but may be discontinuous at $(\infty,\ldots,\infty)$. Formula (eq:tail) identifies the lost payoff when finite quitting dates move arbitrarily far into the future. Ordinary weak compactness of quitting-time distributions consequently does not preserve best-response inequalities automatically.

The exact-terminal-truncation attempt

For $h\ge1$, let $H_h$ be the finite normal-form timing game in which all players choose a planned time from \begin{equation}\label{wsref-0-65-71-3a-4b-68} K_h:=\{0,1,\ldots,h-1,\infty\}, \end{equation} using the original payoff rule (in particular, the all-$\infty$ outcome pays $c$). Such a game has a mixed Nash equilibrium by the finite-game existence theorem. Every such mixed profile can also be embedded as a behavior profile of the infinite quitting game.
Lemma (Boundary estimate for an exact truncation equilibrium): Assume (eq:normalization). If $\mu\in{\operatorname{NE}}(H_h)$ and $q_i=\mu_i(\infty)$, then in the original infinite quitting game \begin{equation}\label{wsref-0-65-71-3a-65-74-61} {\operatorname{Reg}}_r(\mu)\le\eta(\mu),\qquad \eta(\mu):=\max_i(-c_i)\prod_{j\ne i}q_j. \end{equation} If $\infty$ is in the support of player $i$'s equilibrium distribution, then the maximal deviation gain for that player is exactly $(-c_i)\prod_{j\ne i}q_j$.
Proof: Every pure deviation from $K_h$ is available in $H_h$ and hence cannot improve player $i$'s payoff. For any finite $t\ge h$, since all opponents' finite planned dates are less than $h$, \begin{equation}\label{wsref-0-65-71-3a-74-61-69-6c-66-69-6e-69-74-65} U_i(t;\mu_{-i})-U_i(\infty;\mu_{-i}) =(-c_i)\prod_{j\ne i}q_j. \end{equation} Since $\infty$ is an available deviation in $H_h$, the equilibrium payoff is at least $U_i(\infty;\mu_{-i})$, which proves the upper bound. When $\infty$ has positive equilibrium probability for player $i$, that action is a best response in $H_h$ and has payoff exactly equal to her equilibrium payoff; the late deviation realizes the bound. ∎

The lemma suggests choosing terminal-game equilibria whose residual never-quit probabilities satisfy \begin{equation}\label{wsref-0-65-71-3a-62-61-64-63-72-69-74-65-72-69-6f-6e} \inf_{h\ge1}\min_{\mu\in{\operatorname{NE}}(H_h)} \max_i(-c_i)\prod_{j\ne i}\mu_j(\infty)=0. \end{equation} If this condition held, the lemma would yield arbitrarily accurate undiscounted equilibria. It is a sufficient criterion, but it is not necessary. Section sec:counterexample gives a complete three-player refutation of its universal validity.

A cyclic game defeating exact terminal truncation

Consider the three-player game $\Gamma_*$ with quitting-coalition payoffs in Table tab:cyclic. This is the normalized classical cyclic-game example associated with Flesch, Thuijsman, and Vrieze [Flesch1997,AKRS2026]; its use here is as a counterexample to a proof method, not as a counterexample to equilibrium existence. 
\begin{table}[htbp]
\centering
\caption{The cyclic three-player quitting game $\Gamma_*$.}
Quitting set $S$Payoff vector $r^S$
$\varnothing$$(-1,-1,-1)$
$\{1\}$$(0,2,-1)$
$\{2\}$$(-1,0,2)$
$\{3\}$$(2,-1,0)$
$\{1,2\}$$(0,-1,0)$
$\{1,3\}$$(-1,0,0)$
$\{2,3\}$$(0,0,-1)$
$\{1,2,3\}$$(-1,-1,-1)$
\end{table}

An exact cyclic subgame-perfect equilibrium

Consider the infinite three-stage periodic behavior profile \begin{equation}\label{wsref-0-65-71-3a-63-79-63-6c-65} (1/2,0,0),\qquad(0,1/2,0),\qquad(0,0,1/2), \quad\text{repeated forever.} \end{equation} Here the triple at each stage lists quitting probabilities for players $1,2,3$. The associated continuation payoffs at the beginning of the three phases are \begin{equation}\label{wsref-0-65-71-3a-63-79-63-6c-65-76-61-6c-75-65-73} v^{(1)}=(0,1,0),\quad v^{(2)}=(0,0,1),\quad v^{(3)}=(1,0,0). \end{equation} Indeed, \[ v^{(1)}=\tfrac12 r^{\{1\}}+\tfrac12 v^{(2)}=(0,1,0), \] with the other two recursions following cyclically. At phase $1$, player $1$ is indifferent between quitting and continuing (each yields $0$); player $2$ earns $1$ by continuing and $-1/2$ by quitting; player $3$ earns $0$ by either action. The other phases follow by rotation of player indices.

These one-stage incentive checks are sufficient for arbitrary deviations: under any deviation by one player, the other two players independently quit with probability $1/2$ at their respective positions once per block. Their joint probability of not absorbing the game for $k$ full blocks is $4^{-k}$. Thus any player's payoff under any deviation differs negligibly, as $k\to\infty$, from one determined by the first $k$ blocks. Finite-horizon backward optimality and the one-stage checks establish all best-response inequalities. We have proved:

Proposition: The infinite game $\Gamma_*$ possesses a subgame-perfect undiscounted exact $0$-equilibrium, given by (eq:cycle).

A one-stage uniqueness calculation

We now calculate all Nash equilibria of the terminal games $H_h$ in this example. Consider a one-stage game whose payoff, if all continue, is the common number $v\in[-1,0)$ for each player. Write $x_i$ for player $i$'s probability of quitting. The advantage of quitting instead of continuing for player $1$ is \begin{equation}\label{wsref-0-65-71-3a-44-31} D_1=x_2-3x_3+x_2x_3-v(1-x_2)(1-x_3), \end{equation} with the analogous cyclic expressions for the other players.
Lemma (Unique one-stage equilibrium): For $-1\le v<0$, the one-stage game has a unique Nash equilibrium, which is symmetric and completely mixed, with \begin{equation}\label{wsref-0-65-71-3a-6f-6e-65-73-74-61-67-65-70-72-6f-62} x_1=x_2=x_3=p(v):=1-\frac1{\sqrt{1-v}}. \end{equation} Its equilibrium payoff vector is $(-p(v),-p(v),-p(v))$. Furthermore, for any continuation payoff vector $v\in{\mathbb{R}}^3$ (not necessarily symmetric), no Nash equilibrium of the one-stage game has any player quit with probability $1$.
Proof: First prove the final assertion. If $x_1=1$, then player $2$'s advantage from quitting is $D_2=2x_3-3<0$, so $x_2=0$. Given $x_1=1,x_2=0$, player $3$'s quitting advantage is $1>0$, so $x_3=1$. But then player $1$'s quitting advantage is $-3<0$, a contradiction. Cyclic relabeling excludes $x_2=1$ and $x_3=1$.

Now assume $v_1=v_2=v_3=v\in[-1,0)$. If $x_1=0$, player $2$'s quitting advantage is $x_3-v(1-x_3)>0$, forcing $x_2=1$, which is impossible. By symmetry every $x_i$ belongs to $(0,1)$. Set the quitting odds $z_i=x_i/(1-x_i)>0$. Dividing the indifference equations $D_i=0$ by the positive products of the other players' continuation probabilities yields \begin{align}\label{wsref-0-65-71-3a-6f-64-64-73} v&=z_2-3z_3-z_2z_3,\\ v&=z_3-3z_1-z_3z_1,\nonumber\\ v&=z_1-3z_2-z_1z_2.\nonumber \end{align} In particular, if some $z_1\ge1$ then the second equation gives $v=z_3(1-z_1)-3z_1\le-3$, contradicting $v\ge-1$. Thus $0<z_i<1$ for all $i$. Put \[ f_v(z)=\frac{v+3z}{1-z},\qquad f_v'(z)=\frac{3+v}{(1-z)^2}>0. \] Equations (eq:odds) assert that $z_2=f_v(z_3)$, $z_3=f_v(z_1)$, and $z_1=f_v(z_2)$. A strictly increasing real map has no nontrivial finite cycle, so $z_1=z_2=z_3$, hence $x_1=x_2=x_3=x$. Equation (eq:D1) now reduces to \[ v=-\frac{x(2-x)}{(1-x)^2}=1-\frac1{(1-x)^2}, \] which uniquely yields (eq:onestageprob). Direct evaluation of the pure-quitting payoff gives $-x$; by indifference, this is the one-stage equilibrium payoff. The fully mixed profile satisfying these equalities is indeed a Nash equilibrium. ∎

All exact terminal equilibria and a positive regret gap

Define recursively \begin{equation}\label{wsref-0-65-71-3a-70-2d-72-65-63} p_0=1,\qquad p_{k+1}=1-\frac1{\sqrt{1+p_k}},\qquad k\ge0, \end{equation} and put \begin{equation}\label{wsref-0-65-71-3a-71-72-65-63} q_h:=\prod_{k=1}^{h}(1-p_k). \end{equation}
Theorem (Failure of the universal truncation criterion): For every integer $h\ge1$, the finite terminal timing game $H_h$ associated with $\Gamma_*$ has exactly one Nash equilibrium $\mu^{(h)}$. It has all three players quit independently with probabilities $p_h,p_{h-1},\ldots,p_1$ at the successive stages and has per-player payoff $-p_h$. When interpreted in the infinite quitting game, \begin{equation}\label{wsref-0-65-71-3a-71-67-61-70} {\operatorname{Reg}}_{\Gamma_*}(\mu^{(h)})=q_h^2>\frac14. \end{equation} In particular, criterion (eq:badcriterion) is false even for a game possessing an exact subgame-perfect equilibrium.
Proof: The continuation payoffs after the last available finite date are $(-1,-1,-1)$. By Lemma Lemma (Unique one-stage equilibrium), the one-stage game at the last date has the unique symmetric mixed equilibrium with quitting probability $p_1$ and continuation payoff $-p_1$.

We must justify applying backward induction to all Nash equilibria of $H_h$, rather than just subgame-perfect equilibria. At any continuation history reached with positive probability, a Nash equilibrium induces a one-stage Nash equilibrium when its actual continuation payoffs are inserted at the all-continue action profile. By the final assertion of Lemma Lemma (Unique one-stage equilibrium), no player quits with probability $1$ at such a history. Hence the next all-continue history also has positive probability. Induction from the initial stage shows that every continuation history is reached with positive probability. Consequently, Nash equilibrium behavior is optimal at every stage, and the one-stage uniqueness lemma can be applied backwards. Its recursive formula is exactly (eq:p-rec); this proves existence and uniqueness of the specified finite equilibrium.

Each player's probability of choosing $\infty$ is $q_h>0$. Therefore the terminal action $\infty$ lies in every player's equilibrium support. Lemma Lemma (Boundary estimate for an exact truncation equilibrium), including its equality case, now gives ${\operatorname{Reg}}_{\Gamma_*}(\mu^{(h)})=q_h^2$.

It remains to prove the uniform lower bound. From (eq:p-rec), \[ 1+p_{k-1}=\frac1{(1-p_k)^2},\qquad (1-p_k)(1+p_{k-1})=\frac1{1-p_k}\ge1+p_k. \] Multiplying and telescoping gives \[ q_h\ge\prod_{k=1}^h\frac{1+p_k}{1+p_{k-1}} =\frac{1+p_h}{2}>\frac12, \] because $p_h>0$. Squaring proves (eq:qgap). ∎

Remark (What was actually disproved): The theorem is not a counterexample to approximate-equilibrium existence; Proposition Proposition gives an exact equilibrium for the same game. Nor does it show failure of arbitrary finite-prefix approximations. It disproves the particular program of taking exact Nash equilibria of terminal games with an artificial all-continue terminal payoff and expecting their infinite-game regret to tend to zero.

Finite cyclic prefixes do approximate equilibria

Repeat the three-stage block (eq:cycle) exactly $k$ times, then instruct every player to continue forever. Call this profile $x^{[k]}$. One block survives with probability $1/8$ and has unconditional absorbing-payoff contribution $(0,7/8,0)$. Thus \begin{equation}\label{wsref-0-65-71-3a-70-72-65-66-69-78-2d-70-61-79-6f-66-66} \gamma(x^{[k]})= \left(-8^{-k},\,1-2\cdot8^{-k},\,-8^{-k}\right). \end{equation} For an unrestricted deviator after the finite prefix, the appropriate terminal best-response value is $\max\{r_i^{\{i\}},c_i\}=0$, not $-1$: such a deviator may quit alone after everyone else has been instructed to continue. For clarity, start the best-response backward induction at $W=(0,0,0)$ after the last prescribed block. At a stage where only player $j$ may quit, with probability $1/2$, the deviator $i=j$ chooses between $0$ and $W_j$; a deviator $i\ne j$ chooses between $\tfrac12 r_i^{\{i,j\}}$ and $\tfrac12 r_i^{\{j\}}+\tfrac12 W_i$. Applying these recursions backwards through the stages with active players $3,2,1$ gives \[ (0,0,0)\xrightarrow{j=3}(1,0,0) \xrightarrow{j=2}(0,0,1) \xrightarrow{j=1}(0,1,0). \] Starting instead from $(0,1,0)$ gives exactly the same three intermediate vectors and ends again at $(0,1,0)$; thus appending whole blocks does not change the best-response payoff vector. Consequently, \begin{equation}\label{wsref-0-65-71-3a-70-72-65-66-69-78-2d-72-65-67} {\operatorname{Reg}}_{\Gamma_*}(x^{[k]})=2\cdot8^{-k}\longrightarrow0. \end{equation} This demonstrates the exact distinction: arbitrary finite-support profiles can approximate an infinite equilibrium even when exact terminal Nash equilibria cannot.

The finite-grid replacement

The obstruction motivates optimizing regret directly over arbitrary finite-support profiles, rather than first imposing the Nash equations of a truncated terminal game. The next result is a quantitative approximation of the global infimum $g(r)$.

Fix $k\ge1$ and set $H=nk$. Let $\mathcal G_{n,k}$ denote the set of all product distributions $\mu=\bigotimes_i\mu_i$ in which each marginal $\mu_i$ is the empirical distribution of $k$ (not necessarily distinct) points in \begin{equation}\label{wsref-0-65-71-3a-67-72-69-64-2d-73-70-61-63-65} K_H=\{0,1,\ldots,H-1,\infty\}. \end{equation} These are exactly the marginals whose probability masses are integer multiples of $1/k$. There are \begin{equation}\label{wsref-0-65-71-3a-67-72-69-64-63-6f-75-6e-74} |\mathcal G_{n,k}|=\binom{(n+1)k}{k}^{n} \end{equation} independent profiles. Define \begin{equation}\label{wsref-0-65-71-3a-6d-6b} m_k(r)=\min_{\mu\in\mathcal G_{n,k}}{\operatorname{Reg}}_r(\mu). \end{equation} We stress that (eq:mk) uses unrestricted infinite-game regret.

Theorem (Quantitative finite-grid approximation): For every $n\ge2$, every finite-player quitting-game payoff table $r$, and every positive integer $k$, \begin{equation}\label{wsref-0-65-71-3a-67-72-69-64-2d-6d-61-69-6e} 0\le m_k(r)-g(r)\le\frac{(2n-1)D(r)}k. \end{equation} Equivalently, \begin{equation}\label{wsref-0-65-71-3a-67-72-69-64-2d-69-6e-74-65-72-76-61-6c} \max\!\left\{0,m_k(r)-\frac{(2n-1)D(r)}k\right\} \le g(r)\le m_k(r). \end{equation} No assumption such as (eq:normalization) is needed.
Proof: Step 1: midpoint-quantile rounding. Fix any profile $\mu=\bigotimes_i\mu_i$. For each $i$ and $\ell\in\{1,\ldots,k\}$, choose the leftmost $t_{i,\ell}\in K$ whose cumulative distribution function reaches $u_\ell=(2\ell-1)/(2k)$, and define \[ \nu_i=\frac1k\sum_{\ell=1}^k\delta_{t_{i,\ell}}. \] A quantile may equal $\infty$. Standard midpoint rounding gives, for every finite $t$, as well as for every left limit, \begin{equation}\label{wsref-0-65-71-3a-63-64-66-2d-63-6f-6e-74-72-6f-6c} \left|F_{\nu_i}(t)-F_{\mu_i}(t)\right|\le\frac1{2k}. \end{equation} The inequality also applies to the total finite mass, by taking $t\to\infty$.

Step 2: the payoff is a three-level function of one stopping time. Fix every stopping time except that of player $j$ and inspect any coordinate $i$. If the earliest among the fixed times is a finite $a$, and $J$ is the set of fixed players quitting at $a$, then as a function of $s=T_j$ the payoff is \[ f(s)=\begin{cases} A=r_i^{\{j\}},&s<a,\\ B=r_i^{J\cup\{j\}},&s=a,\\ C=r_i^J,&s>a. \end{cases} \] Let $\Delta F=F_{\nu_j}-F_{\mu_j}$. The change in the expectation of $f$ is exactly \[ (A-B)\Delta F(a-)+(B-C)\Delta F(a). \] By (eq:D) and (eq:cdf-control), its absolute value is at most $D(r)/k$. If all fixed times equal $\infty$, there are only two payoff levels, and the same bound holds. Averaging over the fixed stopping times preserves the bound.

Step 3: all unilateral deviations are controlled. Replace the $n$ marginals successively. The bound just established gives, simultaneously for all players, \begin{equation}\label{wsref-0-65-71-3a-67-61-6d-6d-61-2d-72-6f-75-6e-64} |\gamma_i(\nu)-\gamma_i(\mu)|\le\frac{nD(r)}k. \end{equation} For any fixed pure deviation $t\in K$, only the other $n-1$ marginals change, and the same estimate is uniform in $t$: \begin{equation}\label{wsref-0-65-71-3a-55-2d-72-6f-75-6e-64} \sup_{t\in K}\left|U_i(t;\nu_{-i})-U_i(t;\mu_{-i})\right| \le\frac{(n-1)D(r)}k. \end{equation} Combining (eq:gamma-round) and (eq:U-round) yields \begin{equation}\label{wsref-0-65-71-3a-72-65-67-2d-72-6f-75-6e-64} {\operatorname{Reg}}_r(\nu)\le{\operatorname{Reg}}_r(\mu)+\frac{(2n-1)D(r)}k. \end{equation}

Step 4: date compression. The union of the finite supports of the $\nu_i$ has at most $nk$ points. Let the distinct finite support dates be $s_0<\cdots<s_{L-1}$, with $L\le nk$. Replace the date $s_a$ by $a$ for every player, leaving $\infty$ unchanged, and call the product profile $\widehat\nu$. Every realized order and every tie of planned times is preserved, so \begin{equation}\label{wsref-0-65-71-3a-63-6f-6d-70-72-65-73-73-2d-67-61-6d-6d-61} \gamma_i(\widehat\nu)=\gamma_i(\nu). \end{equation} For deviations, each new finite quitting time $a<L$ has the same payoff as the original deviation $s_a$; every new finite time $t\ge L$ has the same payoff as the original deviation $s_{L-1}+1$; and the deviation $\infty$ is unchanged. If $L=0$, the same conclusion follows by comparing immediate finite quitting with never quitting. Thus compression may delete old deviation opportunities but cannot create a new payoff level, and \begin{equation}\label{wsref-0-65-71-3a-63-6f-6d-70-72-65-73-73-2d-72-65-67} {\operatorname{Reg}}_r(\widehat\nu)\le{\operatorname{Reg}}_r(\nu). \end{equation} The profile $\widehat\nu$ belongs to $\mathcal G_{n,k}$. Consequently, for arbitrary $\mu$, \[ m_k(r)\le{\operatorname{Reg}}_r(\widehat\nu) \le{\operatorname{Reg}}_r(\mu)+\frac{(2n-1)D(r)}k. \] Take the infimum over $\mu$ to obtain the upper bound in (eq:grid-main). The lower bound follows from $\mathcal G_{n,k}\subseteq\prod_i\Delta(K)$. ∎

Remark (Neither correlation nor a compactness shortcut): Each rounded marginal remains independent of the others. Date compression is the same deterministic relabeling for every player; it preserves independence. No public signal is introduced. The argument avoids a hidden appeal to continuity at the all-$\infty$ profile by bounding payoff errors before compressing dates.

Exact grid regret and finite nonexistence certificates

For a profile supported on $K_H$, the deviation payoff is constant for finite quitting times $t\ge H$. In full generality, the set of candidate deviations reduces to \begin{equation}\label{wsref-0-65-71-3a-66-69-6e-69-74-65-2d-64-65-76-69-61-74-69-6f-6e-2d-6c-69-73-74} \{0,1,\ldots,H,\infty\}. \end{equation} Under (eq:normalization), set $q_j=\mu_j(\infty)$. The exact late-deviation identity is \begin{equation}\label{wsref-0-65-71-3a-6c-61-74-65-2d-67-65-6e-65-72-61-6c} U_i(H;\mu_{-i})=U_i(\infty;\mu_{-i}) -c_i\prod_{j\ne i}q_j. \end{equation} Since $-c_i>0$, the late finite deviation weakly dominates never quitting, and therefore \begin{equation}\label{wsref-0-65-71-3a-66-69-6e-69-74-65-2d-72-65-67-72-65-74-2d-66-6f-72-6d-75-6c-61} {\operatorname{Reg}}_r(\mu)=\max_i\Bigg[ \max\left\{U_i(0;\mu_{-i}),\ldots, U_i(H-1;\mu_{-i}), U_i(\infty;\mu_{-i})-c_i\prod_{j\ne i}q_j\right\} -\gamma_i(\mu)\Bigg]. \end{equation} Importantly, the deviation immediately after the last date cannot be omitted.
Corollary (Finite certificate of failure of approximate equilibrium): Set $C(r)=(2n-1)D(r)$. The following are equivalent: \begin{align}\label{wsref-0-65-71-3a-66-69-6e-69-74-65-2d-69-66-66} &g(r)>0;\\ &\exists\,k\ge1\text{ such that }m_k(r)>\frac{C(r)}k.\notag \end{align} If an exact calculation establishes $m_k(r)\ge L>C(r)/k$, then \begin{equation}\label{wsref-0-65-71-3a-63-65-72-74-2d-6c-6f-77} {\operatorname{Reg}}_r(\mu)\ge L-\frac{C(r)}k>0 \quad\text{for \emph{every} infinite strategy profile }\mu. \end{equation}
Proof: Theorem Theorem (Quantitative finite-grid approximation) proves the implication from the second statement to the first and (eq:cert-low). Conversely, if $g(r)>0$, choose $k$ with $C(r)/k<g(r)$; since $m_k(r)\ge g(r)$, the second statement follows. ∎
Proposition (Rational counterexamples would suffice): For two games $r,\widetilde r$ with the same player set, \begin{equation}\label{wsref-0-65-71-3a-4c-69-70-73-63-68-69-74-7a} |g(r)-g(\widetilde r)|\le2\|r-\widetilde r\|_\infty. \end{equation} Thus if a counterexample exists with real payoffs, there is also a counterexample with rational payoffs. Rational approximation may be chosen to preserve the exact singleton-payoff normalization and the strict signs $c_i<0$.
Proof: For fixed $\mu$, replacing $r$ by $\widetilde r$ changes every actual payoff and every pure-deviation payoff by at most $\|r-\widetilde r\|_\infty$. Therefore it changes ${\operatorname{Reg}}_r(\mu)$ by at most twice this amount. Infima over $\mu$ preserve the same Lipschitz bound. Choose a rational table sufficiently close to a hypothetical $r$ with $g(r)>0$. ∎
Corollary (Equivalent universal finite inequalities): Every $n$-player quitting game has undiscounted ${\varepsilon}$-equilibria for every ${\varepsilon}>0$ if and only if \begin{equation}\label{wsref-0-65-71-3a-75-6e-70-72-6f-76-65-64} m_k(r)\le\frac{(2n-1)D(r)}k \qquad\text{for every payoff table $r$ and every }k\ge1. \end{equation}
Proof: If all such games have $g(r)=0$, Theorem Theorem (Quantitative finite-grid approximation) gives (eq:unproved). Conversely, (eq:unproved) and $0\le g(r)\le m_k(r)$ imply $g(r)=0$ upon letting $k\to\infty$. ∎

The inequalities (eq:unproved) are not proved here. Theorem Theorem (Quantitative finite-grid approximation) gives only $m_k(r)\le g(r)+C(r)/k$. Replacing the right-hand side with $C(r)/k$ without another argument would assume the conclusion of the open conjecture. At fixed $n,k$, each grid profile's regret is the maximum of finitely many linear expressions in the payoff table, with rational coefficients. A complete lower-bound certificate for a fixed rational game is therefore finite and exactly checkable. It may, however, require an astronomically large enumeration.

From finite undiscounted profiles to uniform approximations

The reduction has a direct uniform-equilibrium interpretation. Let ${\operatorname{Reg}}_T(\mu)$ and ${\operatorname{Reg}}_\lambda(\mu)$ be the maximum unilateral gains under the $T$-stage average and $\lambda$-discounted evaluations in (eq:evaluations), respectively.
Theorem (Uniform error bounds for finite-support profiles): If each player's stopping-time distribution is supported on $K_H=\{0,\ldots,H-1,\infty\}$, then \begin{equation}\label{wsref-0-65-71-3a-75-6e-69-66-6f-72-6d-2d-62-6f-75-6e-64} {\operatorname{Reg}}_T(\mu)\le{\operatorname{Reg}}_r(\mu)+\frac{2D(r)H}{T}, \qquad {\operatorname{Reg}}_\lambda(\mu)\le{\operatorname{Reg}}_r(\mu)+2D(r)H\lambda. \end{equation}
Proof: Under the prescribed profile, either absorption occurs at a stage less than $H$, or nobody ever quits. Therefore its $T$-average payoff differs from the terminal payoff by at most $D(r)H/T$, and the discounted payoff differs by at most $D(r)[1-(1-\lambda)^H]\le D(r)H\lambda$.

The same bounds apply to any pure deviation to a quitting time $t\le H$ or $t=\infty$: absorption then either occurs before $H$ or never occurs. If a deviator instead chooses finite $t>H$, all opponents who quit do so before $H$ and thereby make the late deviation irrelevant. Conditional on all opponents choosing $\infty$, the evaluated payoff is a convex combination of $c_i$ and $r_i^{\{i\}}$, with the weight on $r_i^{\{i\}}$ no larger than it is at time $H$. For either evaluation, such a late deviation has a payoff no greater than the maximum of quitting at $H$ and never quitting. Hence the evaluated best-response payoff exceeds the undiscounted best-response payoff by at most the respective one-sided bound. Subtract the lower bound for the prescribed profile's own evaluated payoff. Mixed deviations are convex combinations of pure deviations, completing the proof. ∎

Corollary (Ordinary and uniform approximate existence are equivalent): For any finite-player quitting game in the sense of Section sec:model, the following are equivalent:
  1. for every ${\varepsilon}>0$ there is an undiscounted ${\varepsilon}$-equilibrium;
  2. for every ${\varepsilon}>0$ there is a uniform ${\varepsilon}$-equilibrium.
Proof: (i)$\Rightarrow$(ii): fix ${\varepsilon}>0$ and an undiscounted profile of regret below ${\varepsilon}/3$. By Theorem Theorem (Quantitative finite-grid approximation), or directly by quantile rounding and date compression, it can be approximated by a finite-support profile whose regret is less than $2{\varepsilon}/3$. Theorem Theorem (Uniform error bounds for finite-support profiles) makes this profile a uniform ${\varepsilon}$- equilibrium for sufficiently large $T$ and small $\lambda$.

(ii)$\Rightarrow$(i): for any fixed behavior profile and any fixed unilateral deviation, bounded convergence gives convergence of the long-run averages to the undiscounted payoff. A uniform ${\varepsilon}/2$- equilibrium satisfies the average-payoff deviation inequality for all large $T$. Passing to the limit separately for each deviation yields an undiscounted ${\varepsilon}/2$-equilibrium, hence an ${\varepsilon}$-equilibrium. ∎

No corresponding assertion about subgame perfection follows just from the quantile approximation: rounding and compression do not preserve incentive constraints at every continuation history.

Exact finite-grid calculations for the cyclic example

The finite-grid theorem is constructive in a theoretical sense. For a rational payoff table, (eq:finite-regret-formula) is a rational expression on every grid profile, so $m_k(r)$ is an exactly computable rational minimum by exhaustive enumeration. A sampled or local numerical minimum is not a certificate of nonexistence.

For the payoff table in Table tab:cyclic, exact rational enumeration gives the following small-grid results:

$k$$H=nk$Number of grid profilesExact $m_k(\Gamma_*)$
$1$$3$$64$$1$
$2$$6$$21{,}952$$1/8$
One minimizing profile for $k=2$ is the independent product of \begin{equation}\label{wsref-0-65-71-3a-67-72-69-64-2d-6d-69-6e-2d-65-78-61-6d-70-6c-65} T_1\sim\tfrac12\delta_0+\tfrac12\delta_3,\quad T_2\sim\tfrac12\delta_1+\tfrac12\delta_4,\quad T_3\sim\tfrac12\delta_2+\tfrac12\delta_4. \end{equation} Direct enumeration of the $2^3$ joint planned-time outcomes and of all best-response date classes yields \begin{equation}\label{wsref-0-65-71-3a-67-72-69-64-2d-6d-69-6e-2d-70-61-79-6f-66-66} \gamma(\mu)=(0,9/8,-1/8),\qquad \left(\sup_t U_i(t;\mu_{-i})\right)_{i=1}^3=(0,5/4,0), \end{equation} so the unrestricted regret is $1/8$. Since $D(\Gamma_*)=3$ and $(2n-1)D=15$, the theorem's bound $m_2-15/2$ gives no positive lower bound on $g(\Gamma_*)$. In fact Proposition Proposition shows that $g(\Gamma_*)=0$. The computations are a check of the explicit finite formulation, not evidence of nonexistence.

The exhaustive enumeration has a simple implementation-independent specification. Enumerate, for every player, the $\binom{H+k}{k}$ multisets of $k$ dates from $K_H$. For each product profile and every $i$, compute \begin{align*} \gamma_i(\mu) &=\sum_{(t_1,\ldots,t_n)\in K_H^n} \left(\prod_j\mu_j(t_j)\right) r_i^{S(t_1,\ldots,t_n)},\\ U_i(t;\mu_{-i}) &=\sum_{t_{-i}\in K_H^{n-1}} \left(\prod_{j\ne i}\mu_j(t_j)\right)r_i^{S(t,t_{-i})}, \end{align*} where $S(\cdot)$ is the set of indices attaining the least finite date, and $r^\varnothing=c$ when every date is infinite. Evaluate the $H+2$ candidate deviations in (eq:finite-deviation-list) and minimize (eq:regret). This is a finite exact certificate procedure involving no numerical tolerances.

Absorption paths, the residual obstacle, and conclusions

The absorption-path approach of Ashkenazi-Golan, Krasikov, Rainer, and Solan [AKRS2024] compactifies absorbing behavior profiles using accumulated absorption probability in place of physical time. Its sequential-perfectness conditions retain both jump behavior (positive simultaneous quitting probabilities at discrete events) and continuous components (vanishing quitting rates). The connection between such paths and limits of approximate equilibria depends on the exclusions of the elementary immediate-absorption and never-absorption cases, as specified precisely in [AKRS2024,AKRS2026]. The 2026 APS treatment develops an operator for a restricted class of paths in which one player is active at a time [AKRS2026]; it is not a proof of universal ordinary equilibrium existence.

The main lessons of the consolidated attempt can be stated without ambiguity:

  1. Proposition Proposition (Exact tail discontinuity) pinpoints the discontinuity that makes a naive limit of finite terminal-game equilibria unsafe.
  2. Lemma Lemma (Boundary estimate for an exact truncation equilibrium) is a correct and useful sufficient error estimate, but Theorem Theorem (Failure of the universal truncation criterion) proves that forcing this estimate to vanish along exact terminal-game Nash equilibria is not a viable general argument.
  3. Arbitrary finite-support profiles avoid that obstruction. Theorem Theorem (Quantitative finite-grid approximation) approximates the globally minimal regret with a computable, explicit $O(1/k)$ error bar; the finite certificate Corollary Corollary (Finite certificate of failure of approximate equilibrium) is the corresponding negative- resolution criterion.
  4. Corollary Corollary (Equivalent universal finite inequalities) isolates the unproved universal inequality (eq:unproved). Establishing it for every payoff table, or finding one finite verified violation, would respectively give a positive solution or a genuine counterexample.

Status. No proof of (eq:unproved), and no counterexample meeting Corollary Corollary (Finite certificate of failure of approximate equilibrium), is given here. Thus the general existence problem remains unresolved by the arguments in this manuscript. The finite reductions are presented as transparent mathematical research attempts; no claim is made that they were previously unknown or that they constitute a solution.

References

  • [Flesch1996] J. Flesch, F. Thuijsman, and O. J. Vrieze (1996). Recursive repeated games with absorbing states. Mathematics of Operations Research 21, 1016--1022.
  • [Flesch1997] J. Flesch, F. Thuijsman, and K. Vrieze (1997). Cyclic Markov equilibria in stochastic games. International Journal of Game Theory 26, 303--314.
  • [SolanVieille2001] E. Solan and N. Vieille (2001). Quitting games. Mathematics of Operations Research 26(2), 265--285. https://doi.org/10.1287/moor.26.2.265.10549.
  • [SolanSolan2020] E. Solan and O. N. Solan (2020). Quitting games and linear complementarity problems. Mathematics of Operations Research 45(2), 434--454. https://doi.org/10.1287/moor.2019.0996.
  • [AKRS2024] G. Ashkenazi-Golan, I. Krasikov, C. Rainer, and E. Solan (2024). Absorption paths and equilibria in quitting games. Mathematical Programming 203, 735--762 (first published online 22 April 2022). https://doi.org/10.1007/s10107-022-01807-6.
  • [AKRS2026] G. Ashkenazi-Golan, I. Krasikov, C. Rainer, and E. Solan (2026). The APS approach for undiscounted quitting games. International Journal of Game Theory 55, Article 19 (published online 2 April 2026). https://doi.org/10.1007/s00182-026-00982-6.

Completion Estimate

30%

Go to contribution →