Simple Nash Equilibria for Qualitative Multiplayer Games

James C. A. Main; Mona Alluwaym; Sven Schewe

REVIEW 3 major objections 7 minor 23 references

Simple Nash Equilibria for Qualitative Multiplayer Games

T0 review · 3 major / 7 minor · reviewed 2026-07-09 · glm-5.2

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Memoryless randomised equilibria always exist for simple multiplayer games

desk verdict Constructive proof that memoryless randomised SPE exist for reachability, safety, and 0-2 Muller objectives on turn-based deterministic arenas, with tightness results showing randomisation is necessary and 1-3 Muller objectives may have no memoryless NE at all. read the letter →

arxiv 2607.07151 v1 pith:5SFCM45P submitted 2026-07-08 cs.GT

Mona Alluwaym , James C. A. Main , Sven Schewe This is my paper

classification cs.GT

keywords Nashequilibriumsubgame-perfectmemorylessstrategiesturn-basedgamesMullerobjectivesreachabilitysafetyMostowskihierarchy

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper settles when multiplayer turn-based games on graphs admit simple equilibria — strategy profiles where no player benefits from unilaterally deviating, and where each player's strategy depends only on the current position, not on history. The authors prove that for any combination of reachability objectives (reach a target), safety objectives (stay in a safe region), and 0-2 Muller objectives (a restricted class where winning sets are upward or downward closed), a memoryless randomised subgame-perfect equilibrium always exists and can be constructed in polynomial time. The key insight is that randomisation replaces memory: in cyclic regions of the game graph where no player can force an exit, having players choose moves uniformly at random ensures all positions are visited infinitely often, which simultaneously satisfies as many reachability players as possible while making deviation pointless. The construction works incrementally — fixing strategies in terminal cycles first, then propagating winning information backward through the graph. The authors complement this with two sharp impossibility results: randomisation is strictly necessary (pure memoryless equilibria can fail to exist even for reachability plus safety games), and stepping outside the 0-2 Muller class to its dual (the 1-3 class) destroys the result entirely — memoryless equilibria may not exist at all, even with randomisation.

What carries the argument

The algorithm (Rules 1-4 in Section 4.4) incrementally constructs a partially-defined memoryless strategy profile. Rule 1 handles leaf SCCs: either fix uniform random play or allow a player to fix a pure winning strategy in a sub-component. Rule 2 fixes a vertex's strategy toward an already-evaluated winning successor. Rule 3 evaluates vertices with a single evaluated successor. Rule 4 removes edges to evaluated vertices that are losing for the controlling player, simplifying the graph so new leaf SCCs emerge. The inductive proof (Lemma 9) shows that at each step, any extension of the partial profile remains a Nash equilibrium from evaluated vertices. The fact that every everywhere-NE is anS

What would settle it

A concrete counterexample would be a turn-based deterministic game with only reachability, safety, and 0-2 Muller objectives where no memoryless randomised strategy profile is a subgame-perfect equilibrium from every vertex. Alternatively, a specific rule-application ordering of the algorithm that produces a profile with a profitable unilateral deviation would expose a gap in the inductive proof.

Watch

Extended reading notes

Core claim

The central mechanism is a constructive algorithm that builds a memoryless randomised strategy profile by processing the game graph bottom-up. In each leaf strongly connected component (a cyclic region with no exits), the algorithm either fixes uniform random play (which visits all vertices infinitely often almost surely, satisfying reachability players whose targets lie inside and safety players whose safe sets contain the component) or, if a player can unilaterally guarantee a better outcome by fixing a pure strategy within a sub-region, allows them to do so. Once a leaf is evaluated, the algorithm propagates: vertices with a winning successor are fixed toward it, edges to losing evaluated

Load-bearing premise

The inductive proof that the constructed strategy profile is an equilibrium relies on the ordering of rule applications being consistent: specifically, that when an edge is removed because it leads to a losing evaluated vertex, that vertex's equilibrium property has already been established. The paper does not explicitly prove that every possible non-deterministic ordering of the rules maintains this consistency, though the natural bottom-up structure of the algorithm makes a

Editorial extensions

If this is right

Controller synthesis for multi-component systems: when system components have reachability or safety specifications, a stationary controller profile satisfying all components can be synthesised in polynomial time without coordination memory.
The boundary between tractable and intractable Muller objectives for equilibrium existence is precisely the 0-2 / 1-3 divide in the Mostowski hierarchy, giving a clean structural criterion for when simple equilibria are guaranteed.
Randomisation serves as a memory substitute: the coin flips that cycle through a leaf SCC encode the same information that a finite-memory strategy would need to track, suggesting a general trade-off between randomness and memory in multi-agent strategy construction.
The polynomial-time algorithm is directly implementable, making equilibrium construction practical for moderate-sized game graphs rather than merely existential.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The 0-2 boundary may extend to richer objective classes: any objective where uniform random play in a leaf SCC is either optimal or worst-case (allowing unilateral improvement to be detected and fixed) could potentially admit the same construction, suggesting a generalisation beyond Muller objectives to other omega-regular winning conditions with similar monotonicity properties.
The trade-off between randomisation and memory observed here for equilibria mirrors known results in zero-sum games, but the multiplayer setting adds a new dimension: randomisation not only replaces memory but also stabilises against deviations, a role absent in the zero-sum case.
If the algorithm's non-deterministic rule ordering could be shown to always produce the same winning sets (even if different strategy profiles), this would yield a unique equilibrium payoff characterisation — a question the paper leaves open.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The main result: for any turn-based deterministic game where each player has a reachability, safety, or 0-2 Muller objective, there exists a memoryless randomised SPE from every vertex, with each objective satisfied with probability 0 or 1. The proof is constructive — a polynomial-time algorithm that incrementally evaluates vertices, fixes strategies in leaf SCCs, and propagates winning sets backward. This is new: prior work gave finite-memory pure SPE for general ω-regular objectives (Ummels) and various negative results for stochastic or concurrent settings, but nobody had pinned down this class on deterministic arenas. The tightness results are clean: a six-player circle example shows randomisation is necessary even for reachability+safety, and a two-player example shows 1-3 Muller objectives may have no memoryless NE at all. The boundary is well-drawn and the examples are small enough to verify by hand. The algorithm is clearly described with good illustrative examples in Sections 4.1–4.3. The ENE-to-SPE reduction is clean and correct for the objective classes considered. Theorem 10 (pure memoryless SPE when all targets and unsafe vertices are absorbing) is a nice bonus that slightly generalises Kehagias [28] and gives a direct construction where the prior proof used Kakutani's fixed point theorem non-constructively. On the soft spots: the reader flagged a concern about well-foundedness of the induction in Lemma 9 under non-deterministic rule ordering. I checked this carefully and the concern does not land. Rule 4's precondition explicitly requires the target vertex v' to be evaluated, so it is in dom(σk) and covered by the induction hypothesis. The Rule 3 case has a minor imprecision in the proof text (claiming all successors satisfy i∉Wv' by Rule 4), but the conclusion holds in all cases regardless of ordering. The induction is well-founded. The impossibility examples (Section 3) are informally presented — they work but could use more rigorous verification. No code is provided, though the algorithm is simple enough that this is not a serious gap. The paper is self-contained with minimal circularity burden. This is for researchers in games on graphs and multi-component controller synthesis. It deserves a serious referee — the main result is correct and the contribution is real.

Referee Report

3 major / 7 minor

Summary. This paper studies memory requirements for Nash equilibria (NE) and subgame-perfect equilibria (SPE) in turn-based deterministic multiplayer games on graphs with omega-regular objectives. The main positive result (Theorem 7) establishes that memoryless randomised SPEs always exist for games where every player's objective is reachability, safety, or a 0-2 Muller objective (i.e., Muller objectives whose accepting sets are all upward- or downward-closed, corresponding to the 0-2 level of the Mostowski hierarchy). The proof is constructive: a polynomial-time algorithm incrementally evaluates vertices by fixing uniform random play in leaf SCCs, propagating winning sets backward, and pruning edges to losing successors. The paper shows that every 'everywhere NE' (ENE) is an SPE in this setting, so the constructed ENE yields an SPE. Complementing this, the paper provides two impossibility results: (1) positional (pure memoryless) ENEs and SPEs may fail to exist when both reachability/Buchi and safety/CoBuchi objectives are present (Example 1, Theorem 2), showing randomisation is sometimes necessary; and (2) memoryless NEs may fail to exist entirely for 1-3 Muller objectives (Example 3, Theorem 4), establishing a boundary in the Mostowski hierarchy. A restricted result (Theorem 10) shows that pure memoryless SPEs exist when all targets and unsafe vertices are absorbing.

Significance. The question of when simple (memoryless) equilibria exist in multiplayer games on graphs is well-motivated by controller synthesis for multi-component systems. Prior negative results for stochastic and concurrent arenas do not settle the deterministic turn-based case for simple objectives, and this paper fills that gap. The constructive, polynomial-time algorithm is a strength: it provides an explicit equilibrium rather than a mere existence proof via fixed-point theorems (contrast the approach in [28]). The boundary results (randomisation necessary for reachability+safety; no memoryless NE for 1-3 Muller) are clean and sharp. The class of 0-2 Muller objectives is natural, encompassing parity objectives with colours {0,1,2}. The paper is essentially self-contained.

major comments (3)

Section 4.4, proof of Lemma 9, Rule 1 case (first paragraph of the case analysis): The argument that a player Pi with P_v^sigma(Omega_i)=0 cannot profitably deviate by exiting the leaf SCC C relies on the claim that any exit edge (v,v') was removed by Rule 4 and that i is not in W_{v'}. However, the logical flow is stated as: the edge 'has been removed by Rule 4, and thus i not in W_{v'}.' This is backwards: Rule 4's precondition is that v' is evaluated and i not in W_{v'}, which is why the edge is removed. The paper should clarify that Rule 4 can only fire when v' is already evaluated (i.e., in dom(sigma_k)), so the induction hypothesis applies to v'. As stated, the text could be read as claiming that removal by Rule 4 implies i not in W_{v'}, rather than the converse. This is a presentation issue in a load-bearing part of the proof, not a logical gap, but it should be corrected for the
Section 4.4, proof of Lemma 9, Rule 3 case: The proof states 'no outgoing edges of v could have been removed by Rule 1(a); otherwise, we would have i in W_v. It follows that all successors v' of v satisfy i not in W_{v'} by Rule 4.' This inference is imprecise under arbitrary rule ordering. If some successor v' satisfies i in W_{v'}, then Rule 2 would apply (fixing v -> v'), and Rule 3 would not fire. The claim 'all successors satisfy i not in W_{v'}' is only valid because Rule 3 fires when v has a unique evaluated successor, implying no evaluated successor satisfies i in W_{v'} (else Rule 2 would have fired first). The proof should make this ordering argument explicit rather than attributing the property solely to Rule 4. The conclusion is correct but the reasoning as written could mislead a careful reader.
Section 4.4, Rule 1(a): The rule identifies a player Pi who 'can win with positive probability from some vertex in C when the other players play uniformly at random' and then fixes a positional winning strategy tau_i over a subset C' of C. The text states this is possible because Pi's objective is a safety objective or a downward-closed Muller objective, reducing to a safety game. However, the claim that 'there exists a subset C' and a positional strategy tau_i such that all plays starting in C' remain in C' and satisfy Omega_i against all opponent strategies that do not exit C' should be justified more carefully. In particular, it should be clarified that the zero-sum game restricted to C (with the opponent allowed any strategy not exiting C) is a safety game for Pi, and that positional determinacy of safety games on finite graphs yields the required tau_i and C'. This is standard but a

minor comments (7)

Section 3.2, Figure 4 caption: The caption refers to 'Figure 3.2' in the text ('see Figure 3.2') but the figure is labelled 'Figure 4'. This cross-reference should be corrected.
Section 3.1, Example 1: The extension to SPEs by adding a seventh vertex is described in a single long sentence. Consider breaking this into two sentences or adding a small figure, as the argument is somewhat dense as written.
Section 4.1, Example 5: The text says 'we can mark t2, v3, and t4 as winning for P2 and P4' but the arena in Figure 6 shows t2 as a target for P2 and t4 as a target for P4. It would help to explicitly state which players' targets are in C to avoid confusion about why P2 and P4 (and not others) are marked winning.
Section 4.4, algorithm description: The algorithm is described as applying rules 'in arbitrary order.' It would help to state explicitly that the algorithm terminates (e.g., 'each rule application either extends dom(sigma_k) or removes an edge; since V and E are finite, the algorithm terminates with dom(sigma) = V'). Termination is implicit but not stated.
Theorem 10: The result slightly generalises [28]. It would be helpful to state precisely what the generalisation is (e.g., from NE to SPE, or from a restricted class of arenas) in the theorem statement or immediately after.
Section 5 (Conclusion): The open question of whether pure memoryless NEs/SPEs exist when all players have only reachability or only safety objectives is mentioned. This is a natural and interesting question; consider briefly discussing why the current technique (uniform random play in leaf SCCs) does not directly resolve it.
Typographical: In the abstract, 'Buchi' and 'CoBuchi' use different accent styles ('Büchi' vs 'Buchi') inconsistently across the paper. Standardise.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity identified

full rationale

The paper's central result (Theorem 7) is proved constructively via an explicit algorithm (Rules 1-4 in Section 4.4) with an inductive correctness argument (Lemma 9). The derivation chain is self-contained: the algorithm defines strategy profiles incrementally, Lemma 8 establishes the 0/1 probability property directly from the algorithm's construction, and Lemma 9 proves the ENE property by induction on the algorithm's steps. The SPE property (Theorem 7's proof) follows from the observation that profitable deviations in subgames would also be profitable deviations in the original game due to the prefix-independence of the objectives considered. No step in this chain reduces to its own inputs by definition. Self-citations ([10, 19, 28, 31, 32]) are to related but distinct results (finite-memory NE existence, memory bounds, randomised strategy expressiveness, discounted games) and are not load-bearing for the central claim. Theorem 10 extends a result of [28] (Kehagias) but via a different, direct algorithmic construction rather than by invoking that result. The impossibility results (Theorems 2, 4) are established via explicit game examples, not by self-citation. The proof is parameter-free, the algorithm is fully specified, and the correctness argument does not depend on any prior result by the same authors.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no new entities, particles, or physical constructs. It is a pure mathematics/theoretical computer science paper. The axioms are standard domain assumptions in games on graphs. No free parameters are fitted or tuned — the algorithm is parameter-free.

assumptions (4)

domain assumption Turn-based deterministic arenas are deadlock-free (every vertex has at least one successor)
Stated in Section 2: 'We assume that the graph is deadlock-free.' Standard in the games-on-graphs literature.
standard math Objectives are measurable subsets of Plays
Section 2: 'An objective is a measurable subset of Plays.' Required for the probability measures P^σ_v to be well-defined.
domain assumption Every ENE is an SPE for the class of objectives considered (reachability, safety, 0-2 Muller)
Used in the proof of Theorem 7 to reduce SPE existence to ENE existence. The paper states 'every ENE is an SPE in this setting' but the proof relies on the observation that a profitable deviation in a subgame Gh implies a profitable deviation in G, which holds because the objectives are prefix-independent or shift-invariant. This is stated but not proven as a separate lemma.
standard math In a leaf SCC with uniform random play, the set of vertices visited infinitely often is almost surely the entire SCC
Implicit in Rule 1(b) and the computation of Wv. This is a standard result from Markov chain theory for finite irreducible chains.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Simple Nash Equilibria for Qualitative Multiplayer Games." pith.science (2026). https://pith.science/paper/5SFCM45P

@misc{pith2026260707151,
  author       = {Pith},
  title        = {Pith review of: Simple Nash Equilibria for Qualitative Multiplayer Games},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5SFCM45P}},
  note         = {Machine review of arXiv:2607.07151}
}

abstract

We investigate memory requirements for Nash and subgame-perfect equilibria in turn-based deterministic games with $\omega$-regular objectives. We prove that memoryless randomised (i.e., stationary) subgame-perfect equilibria always exist in games with reachability, safety, and 0-2 Muller objectives (i.e., Muller objectives for which accepting sets are either up- or downward closed), and any combination of these objectives. We provide an algorithm to construct such an equilibrium. We also show that randomisation may be required to construct memoryless equilibria in games with reachability or B\"uchi as well as safety or CoB\"uchi objectives, and that memoryless equilibria need not exist for any other class of Muller objectives (with respect to the Mostowski hierarchy).

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

[1]

3 Endre Boros, Vladimir Gurvich, Martin Milanic, Vladimir Oudalov, and Jernej Vicic

doi:10.1007/978-3-319-10575-8\_27. 3 Endre Boros, Vladimir Gurvich, Martin Milanic, Vladimir Oudalov, and Jernej Vicic. A three- person deterministic graphical game without Nash equilibria.Discrete Applied Mathematics, 243:21–38,

work page doi:10.1007/978-3-319-10575-8
[2]

2018.01.008

URL:https://doi.org/10.1016/j.dam.2018.01.008, doi:10.1016/J.DAM. 2018.01.008. 4 Patricia Bouyer, Romain Brenguier, and Nicolas Markey. Nash equilibria for reachability objectives in multi-player timed games. In Paul Gastin and François Laroussinie, editors, Proceedings of the 21st International Conference on Concurrency Theory, CONCUR 2010, Paris, France...

work page doi:10.1016/j.dam.2018.01.008 2018
[3]

6Patricia Bouyer, Stéphane Le Roux, Youssouf Oualhadj, Mickael Randour, and Pierre Vand- enhove

URL:https: //doi.org/10.4230/LIPIcs.FSTTCS.2011.375,doi:10.4230/LIPICS.FSTTCS.2011.375. 6Patricia Bouyer, Stéphane Le Roux, Youssouf Oualhadj, Mickael Randour, and Pierre Vand- enhove. Games where you can play optimally with arena-independent finite memory.Logical Methods in Computer Science, 18(1), 2022.doi:10.46298/lmcs-18(1:11)2022. 7 Romain Brenguier....

work page doi:10.4230/lipics.fsttcs.2011.375 2011
[4]

2020.104594,doi:10.1016/J.IC.2020.104594

URL: https://doi.org/10.1016/j.ic. 2020.104594,doi:10.1016/J.IC.2020.104594. 9 Thomas Brihaye, Véronique Bruyère, Aline Goeminne, and Nathan Thomasset. On relevant equilibria in reachability games.Journal of Computer and System Sciences, 119:211–230,

work page doi:10.1016/j.ic 2020
[5]

10 Thomas Brihaye, Julie De Pril, and Sven Schewe

doi:10.1016/j.jcss.2021.02.009. 10 Thomas Brihaye, Julie De Pril, and Sven Schewe. Multiplayer cost games with simple Nash equilibria. In Sergei N. Artëmov and Anil Nerode, editors,Proceedings of the International Symposium on Logical Foundations of Computer Science, LFCS 2013, San Diego, CA, USA, January 6–8, 2013, volume 7734 ofLecture Notes in Computer...

work page doi:10.1016/j.jcss.2021.02.009 2021
[6]

13 Antonio Casares and Pierre Ohlmann

URL: https: //doi.org/10.4230/LIPIcs.FSTTCS.2023.1,doi:10.4230/LIPICS.FSTTCS.2023.1. 13 Antonio Casares and Pierre Ohlmann. Characterising memory in infinite games.Logical Methods in Computer Science, 21(1),

work page doi:10.4230/lipics.fsttcs.2023.1 2023
[7]

L-Vector: Neural Label Embedding for Domain Adaptation

URL:https://doi.org/10.46298/lmcs-21(1: 28)2025,doi:10.46298/LMCS-21(1:28)2025. 14 Krishnendu Chatterjee. Optimal strategy synthesis in stochastic Müller games. In Helmut Seidl, editor,Proceedings of the 10th International Conference on Foundations of Software Science and Computational Structures, FoSSaCS 2007, Held as Part of ETAPS 2007, Braga, Portugal,...

work page Pith review arXiv doi:10.46298/lmcs-21(1: 2025
[8]

18 Rodica Condurache, Emmanuel Filiot, Raffaella Gentilini, and Jean-François Raskin

doi: 10.1007/s00236-013-0182-6. 18 Rodica Condurache, Emmanuel Filiot, Raffaella Gentilini, and Jean-François Raskin. The complexity of rational synthesis. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors,Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome,...

work page doi:10.1007/s00236-013-0182-6 2016

Show all 23 references

[9]

ICALP.2016.121

URL:https://doi.org/10.4230/LIPIcs.ICALP.2016.121, doi:10.4230/LIPICS. ICALP.2016.121. 19Julie De Pril.Equilibria in Multiplayer Cost Games. PhD thesis, UMONS,

2016 doi
[10]

Games on graphs.CoRR, abs/2305.10546, 2023.doi:10.48550/ arXiv.2305.10546

20 Nathanaël Fijalkow, Nathalie Bertrand, Patricia Bouyer-Decitre, Romain Brenguier, Arnaud Carayol, John Fearnley, Hugo Gimbert, Florian Horn, Rasmus Ibsen-Jensen, Nicolas Markey, Benjamin Monmege, Petr Novotný, Mickael Randour, Ocan Sankur, Sylvain Schmitz, Olivier Serre, an...

2023 arXiv
[11]

23 Hugo Gimbert and Wiesław Zielonka

URL:https://doi.org/ 10.1287/moor.21.4.1016,doi:10.1287/MOOR.21.4.1016. 23 Hugo Gimbert and Wiesław Zielonka. Games where you can play optimally without any memory. In Martín Abadi and Luca de Alfaro, editors,Proceedings of the 16th International Conference on Concurrency Theo...

2005 doi
[12]

Mona Alluwaym, James C

doi:10.1007/11539452_33. Mona Alluwaym, James C. A. Main, and Sven Schewe 17 24 Erich Grädel, Wolfgang Thomas, and Thomas Wilke, editors.Automata, Logics, and Infinite Games: A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001], volume 2500 ofLecture Note...

2001 doi
[13]

27 Shizuo Kakutani

doi:10.4230/LIPIcs.STACS.2009.1848. 27 Shizuo Kakutani. A generalization of Brouwer’s fixed point theorem.Duke Mathematical Journal, 8(3):457 – 459, 1941.doi:10.1215/S0012-7094-41-00838-4. 28 Athanasios Kehagias. A note on the Nash equilibria of some multi-player reachability/...

2009 doi
[14]

org/article/id/43859522-c0c8-48c1-88e2-b0f3cd6ef0ef,doi:10.3934/jdg.2021028

URL:https://www.aimsciences. org/article/id/43859522-c0c8-48c1-88e2-b0f3cd6ef0ef,doi:10.3934/jdg.2021028. 29 Jeroen Kuipers, János Flesch, Gijs Schoenmakers, and Koos Vrieze. Pure subgame-perfect equilibria in free transition games.European Journal of Operational Research, 199...

doi
[15]

URL:https://doi.org/10.1016/j.ejor.2008.11.038, doi:10.1016/J.EJOR.2008.11

2008 doi
[16]

Extending finite-memory determinacy to multi-player games.Information and Computation, 261:676–694, 2018.doi:10.1016/j.ic.2018.02.024

30 Stéphane Le Roux and Arno Pauly. Extending finite-memory determinacy to multi-player games.Information and Computation, 261:676–694, 2018.doi:10.1016/j.ic.2018.02.024. 31 James C. A. Main. Arena-independent memory bounds for Nash equilibria in reachability games.Information...

2018 doi
[17]

ic.2026.105425,doi:10.1016/J.IC.2026.105425

URL: https://doi.org/10.1016/j. ic.2026.105425,doi:10.1016/J.IC.2026.105425. 32 James C. A. Main and Mickael Randour. Different strokes in randomised strategies: Re- visiting Kuhn’s theorem under finite-memory assumptions.Information and Computation, 301:105229,

2026 doi
[18]

2024.105229

URL: https://doi.org/10.1016/j.ic.2024.105229, doi:10.1016/J.IC. 2024.105229. 33 Andrzej Wlodzimierz Mostowski. Regular expressions for infinite trees and a standard form of automata. In Andrzej Skowron, editor,Computation Theory - Fifth Symposium, Zaborów, Poland, December 3-...

2024 doi
[19]

48, arXiv:https://www.pnas.org/doi/pdf/10.1073/pnas.36.1.48, doi:10.1073/pnas.36

URL:https://www.pnas.org/doi/abs/10.1073/pnas.36.1. 48, arXiv:https://www.pnas.org/doi/pdf/10.1073/pnas.36.1.48, doi:10.1073/pnas.36. 1.48. 35 Pierre Ohlmann. Characterizing positionality in games of infinite duration over infinite graphs.TheoretiCS, 2,

doi
[20]

36 Amir Pnueli

URL: https://doi.org/10.46298/theoretics.23.3, doi: 10.46298/THEORETICS.23.3. 36 Amir Pnueli. The temporal logic of programs. InProceedings of the 18th Annual Symposium on Foundations of Computer Science, FOCS 1977, Providence, Rhode Island, USA, October 31 – November 1, 1977,...

1977 doi
[21]

39 Reinhard Selten

URL: https://doi.org/10.1007/s001820200092, doi:10.1007/S001820200092. 39 Reinhard Selten. Spieltheoretische Behandlung eines Oligopolmodells mit Nachfrageträgheit: Teil I: Bestimmung des dynamischen Preisgleichgewichts.Zeitschrift für die gesamte Staat- swissenschaft, 121(2):301–324,

doi
[22]

Rational behaviour and strategy construction in infinite multiplayer games

41 Michael Ummels. Rational behaviour and strategy construction in infinite multiplayer games. In S. Arun-Kumar and Naveen Garg, editors,Proceedings of the 26th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FST TCS 2006, Kolkat...

2006 doi
[23]

URL: http://darwin.bth.rwth-aachen.de/opus3/volltexte/ 2011/3451/pdf/3451.pdf

2011

Pith tools

Reviewed July 9, 2026 · model on record in the stance chip above.

[1] [1]

3 Endre Boros, Vladimir Gurvich, Martin Milanic, Vladimir Oudalov, and Jernej Vicic

doi:10.1007/978-3-319-10575-8\_27. 3 Endre Boros, Vladimir Gurvich, Martin Milanic, Vladimir Oudalov, and Jernej Vicic. A three- person deterministic graphical game without Nash equilibria.Discrete Applied Mathematics, 243:21–38,

work page doi:10.1007/978-3-319-10575-8

[2] [2]

2018.01.008

URL:https://doi.org/10.1016/j.dam.2018.01.008, doi:10.1016/J.DAM. 2018.01.008. 4 Patricia Bouyer, Romain Brenguier, and Nicolas Markey. Nash equilibria for reachability objectives in multi-player timed games. In Paul Gastin and François Laroussinie, editors, Proceedings of the 21st International Conference on Concurrency Theory, CONCUR 2010, Paris, France...

work page doi:10.1016/j.dam.2018.01.008 2018

[3] [3]

6Patricia Bouyer, Stéphane Le Roux, Youssouf Oualhadj, Mickael Randour, and Pierre Vand- enhove

URL:https: //doi.org/10.4230/LIPIcs.FSTTCS.2011.375,doi:10.4230/LIPICS.FSTTCS.2011.375. 6Patricia Bouyer, Stéphane Le Roux, Youssouf Oualhadj, Mickael Randour, and Pierre Vand- enhove. Games where you can play optimally with arena-independent finite memory.Logical Methods in Computer Science, 18(1), 2022.doi:10.46298/lmcs-18(1:11)2022. 7 Romain Brenguier....

work page doi:10.4230/lipics.fsttcs.2011.375 2011

[4] [4]

2020.104594,doi:10.1016/J.IC.2020.104594

URL: https://doi.org/10.1016/j.ic. 2020.104594,doi:10.1016/J.IC.2020.104594. 9 Thomas Brihaye, Véronique Bruyère, Aline Goeminne, and Nathan Thomasset. On relevant equilibria in reachability games.Journal of Computer and System Sciences, 119:211–230,

work page doi:10.1016/j.ic 2020

[5] [5]

10 Thomas Brihaye, Julie De Pril, and Sven Schewe

doi:10.1016/j.jcss.2021.02.009. 10 Thomas Brihaye, Julie De Pril, and Sven Schewe. Multiplayer cost games with simple Nash equilibria. In Sergei N. Artëmov and Anil Nerode, editors,Proceedings of the International Symposium on Logical Foundations of Computer Science, LFCS 2013, San Diego, CA, USA, January 6–8, 2013, volume 7734 ofLecture Notes in Computer...

work page doi:10.1016/j.jcss.2021.02.009 2021

[6] [6]

13 Antonio Casares and Pierre Ohlmann

URL: https: //doi.org/10.4230/LIPIcs.FSTTCS.2023.1,doi:10.4230/LIPICS.FSTTCS.2023.1. 13 Antonio Casares and Pierre Ohlmann. Characterising memory in infinite games.Logical Methods in Computer Science, 21(1),

work page doi:10.4230/lipics.fsttcs.2023.1 2023

[7] [7]

L-Vector: Neural Label Embedding for Domain Adaptation

URL:https://doi.org/10.46298/lmcs-21(1: 28)2025,doi:10.46298/LMCS-21(1:28)2025. 14 Krishnendu Chatterjee. Optimal strategy synthesis in stochastic Müller games. In Helmut Seidl, editor,Proceedings of the 10th International Conference on Foundations of Software Science and Computational Structures, FoSSaCS 2007, Held as Part of ETAPS 2007, Braga, Portugal,...

work page Pith review arXiv doi:10.46298/lmcs-21(1: 2025

[8] [8]

18 Rodica Condurache, Emmanuel Filiot, Raffaella Gentilini, and Jean-François Raskin

doi: 10.1007/s00236-013-0182-6. 18 Rodica Condurache, Emmanuel Filiot, Raffaella Gentilini, and Jean-François Raskin. The complexity of rational synthesis. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors,Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome,...

work page doi:10.1007/s00236-013-0182-6 2016