pith. sign in

arxiv: 1907.05481 · v1 · pith:FVXSBB76new · submitted 2019-07-11 · 💻 cs.GT

On Relevant Equilibria in Reachability Games

Thomas Brihaye , V\'eronique Bruy\`ere , Aline Goeminne , Nathan Thomasset This is my paper

Pith reviewed 2026-05-24 22:36 UTC · model grok-4.3

classification 💻 cs.GT
keywords reachability gamesNash equilibriumsubgame perfect equilibriumPareto optimalitysocial welfarecomplexitymultiplayer games on graphs
0
0 comments X

The pith

Reachability games admit relevant equilibria such as Pareto optimal Nash equilibria whose existence and properties can be decided with specific complexity results.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Multiplayer reachability games on finite directed graphs always possess Nash equilibria and subgame perfect equilibria, yet different equilibria can produce sharply different outcomes: some leave every player short of their target set while others let several players succeed. The paper introduces notions of relevant equilibria that filter these possibilities, including Pareto optimal equilibria and equilibria that maximize social welfare. It then supplies complexity results for the natural decision problems that ask whether such relevant equilibria exist or satisfy further conditions. A sympathetic reader cares because these results turn the mere existence of equilibria into a practical question of selecting the ones that improve collective or individual outcomes.

Core claim

In finite reachability games, relevant equilibria are defined via Pareto optimality or social-welfare maximization applied to Nash and subgame-perfect equilibria; the associated decision problems of existence, verification, and optimization admit precise complexity classifications.

What carries the argument

Relevant equilibria obtained by imposing Pareto optimality or social-welfare maximality on the set of Nash equilibria and subgame-perfect equilibria of a reachability game.

If this is right

  • If a Pareto-optimal equilibrium exists, no player can be made better off without making another player worse off.
  • Equilibria with maximal social welfare guarantee that the largest possible number of players reach their targets simultaneously.
  • Decision procedures for these notions allow algorithmic selection among coexisting equilibria rather than arbitrary choice.
  • The same complexity landscape applies to both Nash equilibria and their subgame-perfect refinements.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The complexity results could be used to compare the computational cost of relevant equilibria across different graph classes or objective types.
  • Implementation of the decision procedures might support automated synthesis of strategies in multi-agent systems where targets represent safety or reachability goals.
  • Extending the same relevance filters to infinite games or to objectives beyond reachability would test whether the complexity pattern persists.

Load-bearing premise

That the known existence of ordinary Nash and subgame-perfect equilibria carries over without change to the restricted classes of relevant equilibria.

What would settle it

A concrete finite graph with target sets for which an algorithm decides the existence of a Pareto-optimal Nash equilibrium in time or space outside the complexity class established by the paper.

Figures

Figures reproduced from arXiv: 1907.05481 by Aline Goeminne, Nathan Thomasset, Thomas Brihaye, V\'eronique Bruy\`ere.

Figure 1
Figure 1. Figure 1: A two-player quantitative reachability game such that F1 = {v3, v4} and F2 = {v1, v4} For this example, we claim that there is no NE (and thus no SPE) such that its cost profile is Pareto optimal (see Problem 3). Assume the contrary and suppose that there exists an NE σ such that its outcome ρ has cost profile (3, 3), meaning that ρ begins with v0v2v4. Then Player 1 has a profitable deviation such that aft… view at source ↗
Figure 1
Figure 1. Figure 1: We explained in Example 1 that there is no NE in this game such t [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A qualitative reachability game with two players such that F1 = {v1} and F2 = {v2}. B Complements to Section 4.2 B.1 Complements about coalitionnal games We provide the formal definitions of (quantitative) coalitional game, value and optimal strategy. Definition 5 ((Quantitative) Coalitional game). Let A = (Π, V, E; (Vi)i∈Π) be an arena and G = (A,(Costi)i∈Π ,(Fi)i∈Π) be a quantitative reachability game wi… view at source ↗
Figure 3
Figure 3. Figure 3: The condition of Definition 10 Proposition 2. Let (G, v0) be a quantitative reachability game and (X,(v0, I0)) be its extended game, let c ∈ (N∪ {+∞}) |Π| and let M = maxi∈Π{ci | ci < +∞} if this max exists, M = 0 otherwise. The following assertions are equivalent: 1. There exists an SPE with cost profile c in (X,(v0, I0)); [PITH_FULL_IMAGE:figures/full_fig_p023_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Reduction from the formula ψ to the quantitative reachability game Gψ We conclude results about the threshold existence problem in quantitative reachability games with some remarks about a variant of this problem in this setting. Remark 3. We may also consider this problem but with an upper and a lower threshold. This problem is also NP-complete but the result about memory is a little bit different. Indeed… view at source ↗
Figure 5
Figure 5. Figure 5: Reduction from the formula ψ to the quantitative reachability game Gψ for Problem 2 with SPEs. ⊓⊔ D.3 Proof of Theorem 5 and Theorem 6 for Problem 3 Lemma 6. Problem 4 belongs to co-NP for quantitative reachability games. Proof. Let us prove it for quantitative reachability games. If ρ is not Pareto optimal, there exists a play ρ ′ such that (Costi(ρ))i∈Π ≥ (Costi(ρ ′ ))i∈Π and (Costi(ρ))i∈Π 6= (Costi(ρ ′ … view at source ↗
Figure 6
Figure 6. Figure 6: A qualitative reachability game that has no NE with a gain profile that is Pareto-optimal For the second item, consider the initialized qualitative reachability game (G, v0) of [PITH_FULL_IMAGE:figures/full_fig_p036_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Reduction from the formula ψ to the quantitative reachability game Gψ Theorem 15. Let (G, v0) be a qualitative reachability game, for SPE: for each decision problem, if the answer is positive, there exists a strategy profile σ with memory in O(|V | 3 · |Π| · 2 3·|Π| ) which satisfies the conditions. These two theorems are due to Propositions 11,12 and 13. Proposition 11 ([4]). Let (G, v0) be a qualitative … view at source ↗
read the original abstract

We study multiplayer reachability games played on a finite directed graph equipped with target sets, one for each player. In those reachability games, it is known that there always exists a Nash equilibrium (NE) and a subgame perfect equilibrium (SPE). But sometimes several equilibria may coexist such that in one equilibrium no player reaches his target set whereas in another one several players reach it. It is thus very natural to identify "relevant" equilibria. In this paper, we consider different notions of relevant equilibria including Pareto optimal equilibria and equilibria with high social welfare. We provide complexity results for various related decision problems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript studies multiplayer reachability games on finite directed graphs with one target set per player. It recalls that Nash equilibria (NE) and subgame-perfect equilibria (SPE) always exist, observes that multiple equilibria may coexist with differing reachability outcomes (some players reach their targets in one equilibrium but not in another), introduces notions of relevant equilibria (including Pareto-optimal equilibria and equilibria maximizing social welfare), and establishes complexity results for associated decision problems.

Significance. If the complexity classifications hold, the results would be a useful contribution to algorithmic game theory on graphs. They extend the known existence of NE and SPE by addressing the computational problem of selecting among equilibria according to relevance criteria, which is relevant for multi-agent verification and synthesis applications.

minor comments (2)
  1. [Abstract] Abstract: the phrase 'various related decision problems' is vague; a brief enumeration of the exact decision problems (e.g., existence of a Pareto-optimal NE in which k players reach their targets) would improve clarity.
  2. The manuscript should explicitly state the input encoding (graph size, target sets) used for the complexity results to make the PSPACE / NP bounds fully precise.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful summary of our work and the recommendation for minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's central results are complexity classifications for decision problems on formally defined notions of relevant equilibria (Pareto-optimal, high social welfare, etc.) in finite reachability games. These decision problems are well-defined directly from the input graph, target sets, and equilibrium concepts without any reduction to fitted parameters, self-referential definitions, or load-bearing self-citations. The background fact that NE and SPE exist is invoked only motivationally and is treated as an external known result; the new work does not derive existence or any quantitative prediction from its own inputs. No step in the derivation chain matches any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard domain assumptions from graph theory and game theory regarding finite directed graphs, target sets, and equilibrium definitions; no free parameters or invented entities are indicated in the abstract.

axioms (1)
  • domain assumption Finite directed graphs with per-player target sets admit Nash and subgame perfect equilibria
    Invoked in the abstract as a known fact on which the relevance notions build.

pith-pipeline@v0.9.0 · 5632 in / 1208 out tokens · 54110 ms · 2026-05-24T22:36:54.300127+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    In: 34th International Conference on Foundat ion of Software Tech- nology and Theoretical Computer Science, FSTTCS 2014, Dece mber 15-17, 2014, New Delhi, India

    Bouyer, P., Markey, N., Stan, D.: Mixed Nash equilibria in concurrent terminal- reward games. In: 34th International Conference on Foundat ion of Software Tech- nology and Theoretical Computer Science, FSTTCS 2014, Dece mber 15-17, 2014, New Delhi, India. pp. 351–363 (2014)

    work page 2014

  2. [2]

    In: CA V (2)

    Brenguier, R., Raskin, J.: Pareto curves of multidimensi onal mean-payoff games. In: CA V (2). Lecture Notes in Computer Science, vol. 9207, pp . 251–267. Springer (2015)

    work page 2015

  3. [3]

    Logical Methods in Computer S cience 9(1) (2012)

    Brihaye, T., Bruy` ere, V., De Pril, J., Gimbert, H.: On sub game perfection in quan- titative reachability games. Logical Methods in Computer S cience 9(1) (2012)

    work page 2012

  4. [4]

    In: Proceedings Ninth International Symposium on Games, Autom ata, Logics, and Formal Verification, GandALF 2018, Saarbr¨ ucken, Germany, 26-28th September

    Brihaye, T., Bruy` ere, V., Goeminne, A., Raskin, J.: Cons trained existence prob- lem for weak subgame perfect equilibria with ω-regular boolean objectives. In: Proceedings Ninth International Symposium on Games, Autom ata, Logics, and Formal Verification, GandALF 2018, Saarbr¨ ucken, Germany, 26-28th September

    work page 2018

  5. [5]

    To appear CONCUR 2019

    Brihaye, T., Bruy` ere, V., Goeminne, A., Raskin, J., van d en Bogaard, M.: The complexity of subgame perfect equilibria in quantitative r eachability games. To appear CONCUR 2019

    work page 2019

  6. [6]

    CoRR abs/1905.00784 (2019), http://arxiv.org/abs/1905.00784

    Brihaye, T., Bruy` ere, V., Goeminne, A., Raskin, J., van d en Bogaard, M.: The complexity of subgame perfect equilibria in quantitative r eachability games. CoRR abs/1905.00784 (2019), http://arxiv.org/abs/1905.00784

    work page arXiv 1905

  7. [7]

    In: Logical Foundations of Computer Science, I nternational Sympo- sium, LFCS 2013, San Diego, CA, USA, January 6-8, 2013

    Brihaye, T., De Pril, J., Schewe, S.: Multiplayer cost gam es with simple Nash equilibria. In: Logical Foundations of Computer Science, I nternational Sympo- sium, LFCS 2013, San Diego, CA, USA, January 6-8, 2013. Proce edings. pp. 59–73 (2013), https://doi.org/10.1007/978-3-642-35722-0_5

    work page doi:10.1007/978-3-642-35722-0_5 2013

  8. [8]

    Acta Inf

    Brihaye, T., Geeraerts, G., Haddad, A., Monmege, B.: Pseu dopolynomial iterative algorithm to solve total-payoff games and min-cost reachabi lity games. Acta Inf. 54(1), 85–125 (2017)

    work page 2017

  9. [9]

    In: Devel- opments in Language Theory - 21st International Conference , DLT 2017, Li` ege, Belgium, August 7-11, 2017, Proceedings

    Bruy` ere, V.: Computer aided synthesis: A game-theoreti c approach. In: Devel- opments in Language Theory - 21st International Conference , DLT 2017, Li` ege, Belgium, August 7-11, 2017, Proceedings. pp. 3–35 (2017)

    work page 2017

  10. [10]

    : The Complexity of Rational Synthesis

    Condurache, R., Filiot, E., Gentilini, R., Raskin, J.F. : The Complexity of Rational Synthesis. In: Chatzigiannakis, I., Mitzenmacher, M., Rab ani, Y., Sangiorgi, D. (eds.) 43rd International Colloquium on Automata, Languag es, and Programming (ICALP 2016). Leibniz International Proceedings in Inform atics (LIPIcs), vol. 55, pp. 121:1–121:15. Schloss Dags...

    work page 2016

  11. [11]

    CoRR cs.GT/0205074 (2002), http://arxiv.org/abs/cs.GT/0205074

    Conitzer, V., Sandholm, T.: Complexity results about Na sh equilibria. CoRR cs.GT/0205074 (2002), http://arxiv.org/abs/cs.GT/0205074

    work page arXiv 2002

  12. [12]

    Haddad, A.: Characterising Nash equilibria outcomes in fully informed concurrent games, available at http://web1.ulb.ac.be/di/verif/had dad/H16.pdf

    work page

  13. [13]

    Theory of Computing Systems 43(2), 204–233 (Aug 2008)

    Khachiyan, L., Boros, E., Borys, K., Elbassioni, K., Gur vich, V., Rudolf, G., Zhao, J.: On short paths interdiction problems: Total and node-wi se limited interdiction. Theory of Computing Systems 43(2), 204–233 (Aug 2008)

    work page 2008

  14. [14]

    In: PNAS

    Nash, J.F.: Equilibrium points in n-person games. In: PNAS. vol. 36, pp. 48–49. National Academy of Sciences (1950)

    work page 1950

  15. [15]

    Oxford Univ

    Osborne, M.: An introduction to game theory. Oxford Univ . Press (2004)

    work page 2004

  16. [16]

    In: POPL

    Pnueli, A., Rosner, R.: On the synthesis of a reactive mod ule. In: POPL. pp. 179–

    work page

  17. [17]

    Brihaye et al

    ACM Press (1989) 14 T. Brihaye et al

    work page 1989

  18. [18]

    In: Mayr, E.W., Puech, C

    Thomas, W.: On the synthesis of strategies in infinite gam es. In: Mayr, E.W., Puech, C. (eds.) STACS 95. pp. 1–13. Springer Berlin Heidelb erg, Berlin, Heidel- berg (1995)

    work page 1995

  19. [19]

    In: FSTTCS

    Ummels, M.: Rational behaviour and strategy constructi on in infinite multiplayer games. In: FSTTCS. Lecture Notes in Computer Science, vol. 4 337, pp. 212–223. Springer (2006)

    work page 2006

  20. [20]

    Ummels, M.: The complexity of Nash equilibria in infinite multiplayer games. In: Foundations of Software Science and Computational Structu res, 11th International Conference, FOSSACS 2008, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2008, Budapest, Hung ary, March 29 - April 6, 2008. Proceedings. pp. 20–34 (2008...

    work page 2008

  21. [21]

    Brihaye et al

    There exists an SPE with cost profile c in (X, (v0,I 0)); 24 T. Brihaye et al

    work page

  22. [22]

    Λ ∗ (v,I ) = {ρ ∈ PlaysX (v,I ) | ρ is λ ∗ -consistent} ̸ = ∅ for all (v,I ) ∈ Succ∗ (v0,I 0) and there exists ρ ∈ Λ ∗(v0,I 0) such that (Costi(ρ))i∈Π =c

    work page

  23. [23]

    Moreover, for each ρi,v,I ∈ P , |ρi,v,I | ≤ O(|V |(|Π |+1)·(|Π |+|V |)) + (|Π |+ 1) · |V |

    There exists a good symbolic witness P that contains a lasso ρ0,v 0,I 0 with cost profile c and |ρ0,v 0,I 0 | ≤ M + |V |. Moreover, for each ρi,v,I ∈ P , |ρi,v,I | ≤ O(|V |(|Π |+1)·(|Π |+|V |)) + (|Π |+ 1) · |V |

    work page

  24. [24]

    ⇐ ” holds, we have to slightly change the arena of the game (see Figure 5): we add a vertex ⊥ that we add in the target set of the “existential player

    There exists a finite-memory SPE σ with cost profile c in (X, (v0,I 0)) such that its memory is in O(M + 2|Π | · |Π | · |V |(|Π |+1)·(|Π |+|V |)+1). To obtain the bound on the length of the lassoes, we use the following lemma. Lemma 4 ([6]). Let v be a vertex in the extended game, let MaxCosti(v) = max{Costi(ρ) |ρ ∈ Plays(v) and ρ is λ ∗ -consistent}. If Ma...

    work page