pith. sign in

arxiv: 2605.19954 · v1 · pith:N5H5KJ2Bnew · submitted 2026-05-19 · 💻 cs.GT · cs.FL· cs.MA

Equilibria in Multiplayer Graph Games: An Algorithmic Study

L\'eonard Brice This is my paper

Pith reviewed 2026-05-20 04:17 UTC · model grok-4.3

classification 💻 cs.GT cs.FLcs.MA
keywords multiplayer graph gamesequilibrium conceptsconstrained existencecomputational complexityNash equilibriumalgorithmic game theorystrategy profiles
0
0 comments X

The pith

The constrained existence problem for each of five equilibrium notions in multiplayer graph games has a specific complexity classification.

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

The paper examines the computational complexity of determining whether multiplayer graph games possess equilibria satisfying payoff constraints for each player. It addresses five distinct equilibrium concepts, including the well-known Nash equilibrium. Establishing these complexity results matters because it informs when automated verification tools can efficiently check for robust strategy profiles in systems with multiple interacting agents. A sympathetic reader would care because it bridges theoretical game theory with practical algorithmic questions in protocol and program verification.

Core claim

For each of the five equilibrium notions studied, the constrained existence problem—deciding if there exists an equilibrium where each player's payoff lies within a given interval—admits a precise complexity classification in the context of multiplayer graph games.

What carries the argument

The constrained existence problem applied to five equilibrium notions in standard multiplayer graph games with payoff functions.

If this is right

  • The existence of such equilibria can be decided algorithmically for each notion.
  • Hardness results apply differently across the five concepts.
  • This enables targeted approaches for verifying multi-agent systems.
  • The results distinguish the computational difficulty of different robustness notions.

Where Pith is reading between the lines

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

  • These classifications could guide the design of synthesis tools for multi-agent protocols.
  • Extending to infinite games or other payoff structures might yield similar complexity patterns.
  • Connections to temporal logic specifications could be explored for automated checking.

Load-bearing premise

The underlying model consists of standard multiplayer graph games equipped with the usual payoff functions and the standard definitions of the five equilibrium concepts.

What would settle it

Discovery of a multiplayer graph game where the existence of a constrained equilibrium for one of the notions falls outside the claimed complexity class.

Figures

Figures reproduced from arXiv: 2605.19954 by L\'eonard Brice.

Figure 1
Figure 1. Figure 1: Game associated with a hydroelectric dam [PITH_FULL_IMAGE:figures/full_fig_p017_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Our main complexity results [PITH_FULL_IMAGE:figures/full_fig_p025_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Dependences between chapters Similarly, Chapter 3 presents results on Nash equilibria but also introduces the game classes studied in later chapters. Those already familiar with parity, mean-payoff, discounted-sum, or energy games may skip it, but for others, reading it before Part III is strongly recommended. Within Part III, Chapter 4 should be read before Chapter 5, which in turn should be read before C… view at source ↗
Figure 4
Figure 4. Figure 4: A game Example 1. We give in [PITH_FULL_IMAGE:figures/full_fig_p036_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: A non-deterministic one-player memory structure [PITH_FULL_IMAGE:figures/full_fig_p038_5.png] view at source ↗
Figure 7
Figure 7. Figure 7: A game constructed from an instance of the TDS problem [PITH_FULL_IMAGE:figures/full_fig_p046_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Another game constructed from the same instance of [PITH_FULL_IMAGE:figures/full_fig_p047_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: A machine that halts on (0, 0) 𝑞0 𝑞1 𝑞f 𝐶 + 1 𝐶 − 1 𝐶1 = 0 [PITH_FULL_IMAGE:figures/full_fig_p051_9.png] view at source ↗
Figure 11
Figure 11. Figure 11: Gadgets simulates a terminating sequence of transitions of K (note that one transition may be represented by several edges). We must now prove that this run is valid, i.e. that tests are simulated correctly. • Let us assume that at some point along the play 𝜋, from a vertex 𝑞, player 𝐶 ⊤ 𝑖 , with 𝑖 ∈ {1, 2}, does not take the edge to the vertex 𝑞 ′ while her energy level is zero. Then, her energy level dr… view at source ↗
Figure 12
Figure 12. Figure 12: The memory structure M ▶ Recursive enumerability Recursive enumerability will be a consequence of the following result. Lemma 4. For every NE 𝜎¯ in the energy game G↾𝑣0 , there exists a finite-memory NE 𝜎¯ ★ with 𝜇(𝜎¯) = 𝜇(𝜎¯ ★). Proof. Let 𝜎¯ be an NE in the game G↾𝑣0 . Let 𝜋 = ⟨𝜎¯⟩. By Dickson’s lemma, there exist two indices 𝑚 and 𝑛, with 𝑚 < 𝑛, such that 𝜋𝑚 = 𝜋𝑛 and such that for every player 𝑖 that d… view at source ↗
Figure 13
Figure 13. Figure 13: Two Nash equilibria If 𝜎𝑖 is a strategy in the game G↾𝑣0 , its substrategy after ℎ𝑣 is the strategy 𝜎𝑖↾ℎ𝑣 in the game G↾ℎ𝑣 , defined by 𝜎𝑖↾ℎ𝑣 (ℎ ′ ) = 𝜎𝑖(ℎℎ′ ) for every ℎ ′ ∈ Hist𝑖G↾ℎ𝑣 . Remark 2. The initialized game G↾𝑣0 is also the subgame of G after the one-vertex history 𝑣0. We can now define subgame-perfect equilibria. Definition 18 (Subgame-perfect equilibrium). Let G↾𝑣0 be a game. The strategy pr… view at source ↗
Figure 14
Figure 14. Figure 14: The construction of 𝜎¯ every history ℎ𝑣 ∈ HistG↾𝜋0 , we have: sup 𝜏𝑖 𝜇𝑖⟨𝜎¯−𝑖↾ℎ𝑣, 𝜏𝑖⟩ ≤ 𝜇𝑖⟨𝜎¯↾ℎ𝑣 ⟩ + 𝜀. By taking the infima over ℎ𝑣, we deduce: inf ℎ𝑣∈HistG↾𝜋0 sup 𝜏𝑖 𝜇𝑖⟨𝜎¯−𝑖↾ℎ𝑣, 𝜏𝑖⟩ ≤ inf ℎ𝑣 𝜇𝑖⟨𝜎¯↾ℎ𝑣 ⟩ + 𝜀 = 𝜆(𝑣) + 𝜀. Let us now notice that all the strategy profiles of the form 𝜎¯−𝑖↾ℎ𝑣 are 𝜆-rational. Thus, we obtain: inf 𝜏¯−𝑖 ∈𝜆Rat(𝑣) sup 𝜏𝑖 𝜇𝑖⟨𝜏¯⟩ ≤ 𝜆(𝑣) + 𝜀, that is, we obtain nego(𝜆) (𝑣) ≤ 𝜆(𝑣) + 𝜀, … view at source ↗
Figure 15
Figure 15. Figure 15: The strategy profile 𝜎¯ is an SPE. profile 𝜏¯ 𝑣∗ . Moreover, all the plays constructed are 𝜆-consistent, hence the strategy profile 𝜏¯ 𝑣∗ −𝑖 is 𝜆-rational assuming the strategy 𝜏 𝑣∗ 𝑖 , as desired. Construction of 𝜎¯. Let us now construct inductively the strategy profile 𝜎¯ itself: we will prove in the next part of the proof that it is an 𝜀-SPE. We proceed inductively, by defining all the plays ⟨𝜎¯↾ℎ𝑣 ⟩, … view at source ↗
Figure 16
Figure 16. Figure 16: A concrete negotiation game Steady negotiation. Moreover, if 𝜏𝔓 is optimal, then the 𝜆-rational strategy profile 𝜎¯−𝑖 realizes the infimum: inf 𝜎¯−𝑖 ∈𝜆Rat(𝑣0 ) sup 𝜎 ′ 𝑖 𝜇𝑖⟨𝜎¯−𝑖 , 𝜎′ 𝑖 ⟩, hence if there exists such an optimal strategy for every vertex 𝑣0, then the game G is with steady negotiation. ▶ Second direction: the inequality valℭ  conc𝜆𝑖(G)↾𝑣 c 0  ≤ nego(𝜆) (𝑣0). Let 𝜎¯−𝑖 be a 𝜆-rational strateg… view at source ↗
Figure 17
Figure 17. Figure 17: A Büchi game. 73 [PITH_FULL_IMAGE:figures/full_fig_p075_17.png] view at source ↗
Figure 18
Figure 18. Figure 18: The game G 𝜑 Note that Solver and Witness can only get the payoffs 0 or 1, and that in every play, exactly one of them gets the payoff 1. Another player 𝑥 gets the payoff 1 in a play that never visits (or finitely often, or infinitely often but with negligible frequence) a vertex of the form (𝐶, 𝑥). Otherwise, he may get any payoff between 0.5 and 1, depending on the frequence with which such a vertex is … view at source ↗
Figure 19
Figure 19. Figure 19: An example of mean-payoff game Definition 31 (Linear equations, inequations, systems). Let 𝐷 be a finite set. A linear equation in R 𝐷 is a pair (𝑎, 𝑏 ¯ ) ∈ R 𝐷 \  0¯  ×R. The solution set of the equation (𝑎, 𝑏 ¯ ) is the set Sol=(𝑎, 𝑏 ¯ ) = {𝑥¯ ∈ R 𝐷 | 𝑎¯·𝑥¯ = 𝑏}, where · denotes the canonical scalar product on the euclidian space R 𝐷 . A set 𝑋 ⊆ R 𝐷 is a hyperplane of R 𝐷 if it is the solution set of … view at source ↗
Figure 20
Figure 20. Figure 20: A game without SPE If there is no deviation in 𝐾. Then, let us notice that deviations are the only edges that go from a vertex of the form (·, 𝑀) to a vertex of the form (·, 𝑀′ ) with 𝑀′ ⊂ 𝑀. Therefore, necessarily, there exists a set 𝑀 ⊆ 𝑉 such that all vertices in 𝐾 have the form (·, 𝑀). By Lemma 10, the set of possible values of 𝜇( ¤𝜋) for all plays 𝜋 in 𝐾 is exactly the set: 𝑋 = ⌞  Conv 𝑐∈SCyc(𝐾) 𝜇( … view at source ↗
Figure 21
Figure 21. Figure 21: A game where the negotiation sequence is not ultimately constant [PITH_FULL_IMAGE:figures/full_fig_p093_21.png] view at source ↗
Figure 22
Figure 22. Figure 22: The reduced negotiation game – if 𝑔𝑘−1𝑔𝑘 = [ℎ ′ 𝑣]𝑣 or (𝑐, 𝑣)𝑣, then ℎ (𝑘) is empty; and that definition is naturally extended to plays: for example, if G is the game of Figure 19a and if 𝜋 = 𝑎[𝑎𝑏∞𝑎 𝜔] [𝑎𝑎]𝑎[𝑎𝑏∞𝑎 𝜔] (𝑏, 𝑏)𝑏 [𝑏 ∞𝑎 𝜔]⊤𝜔, then we write 𝜋¤ = 𝑎 · 𝑎𝑏2 2 · 𝑎𝑏7 2 𝑎 𝜔 = 𝑎 2 𝑏 4𝑎𝑏49𝑎 𝜔; • the payoff function 𝜇 r is defined, for each play 𝜋, by 𝜇 r ℭ (𝜋) = −𝜇 r 𝔓 (𝜋) = +∞ if 𝜋 reaches the vertex ⊥, … view at source ↗
Figure 23
Figure 23. Figure 23: Gadgets [PITH_FULL_IMAGE:figures/full_fig_p110_23.png] view at source ↗
Figure 24
Figure 24. Figure 24: A game where infinite memory is necessary to make player [PITH_FULL_IMAGE:figures/full_fig_p113_24.png] view at source ↗
Figure 25
Figure 25. Figure 25: A product game • Leader controls the set 𝑉 × 𝔏 = ∅, each player 𝑖 ≠ 𝔏, 𝔇 controls the set 𝑉 × 𝑖 = 𝑉𝑖 × 𝑄 × 𝑄, and Demon controls the set 𝑉 × 𝔇 = (𝑉 × 𝑄) ∪ (𝑉𝔏 × 𝑄 × 𝑄); • the set 𝐸 × contains: – the edge (𝑢, 𝑝) (𝑢, 𝑝, 𝑞) for each transition (𝑝, 𝑢, 𝑞) ∈ Δ (if 𝑢 ∉ 𝑉𝔏), or (𝑝, 𝑢, 𝑞, 𝑣) ∈ Δ (if 𝑢 ∈ 𝑉𝔏); – the edge (𝑢, 𝑝, 𝑞) (𝑣, 𝑞) for each transition (𝑝, 𝑢, 𝑞, 𝑣) ∈ Δ (if 𝑢 ∈ 𝑉𝔏); – the edge (𝑢, 𝑝, 𝑞) (𝑣, 𝑞) f… view at source ↗
Figure 26
Figure 26. Figure 26: The temptation of chaos: an illustration [PITH_FULL_IMAGE:figures/full_fig_p120_26.png] view at source ↗
Figure 27
Figure 27. Figure 27: The game G↾𝑎 • for each clause 𝐶𝑗 , a vertex 𝐶𝑗 ∈ 𝑉𝐶𝑗 ; • a sink vertex ▽ (drawn three times in [PITH_FULL_IMAGE:figures/full_fig_p126_27.png] view at source ↗
Figure 28
Figure 28. Figure 28: The temptation of chaos in a discounted-sum game [PITH_FULL_IMAGE:figures/full_fig_p129_28.png] view at source ↗
Figure 29
Figure 29. Figure 29: Exchange between Adélaïde and Barthélémy only. [PITH_FULL_IMAGE:figures/full_fig_p134_29.png] view at source ↗
Figure 30
Figure 30. Figure 30: Exchange between Adélaïde and Barthélémy with a trusted third party. [PITH_FULL_IMAGE:figures/full_fig_p135_30.png] view at source ↗
Figure 31
Figure 31. Figure 31: Expected exchanged items between Adélaïde, Barthélémy, and Capucine. [PITH_FULL_IMAGE:figures/full_fig_p136_31.png] view at source ↗
Figure 32
Figure 32. Figure 32: Game to encode QSat instance ∃𝑥1∀𝑥2 · · · ∃𝑥𝑛−1∀𝑥𝑛 Ó𝑝 𝑖=1 Ô𝑚𝑖 𝑗=1 ℓ𝑖𝑗 into the existence of an SSE with payoff (1, . . . , 1, 1, 1). Round vertices belong to Solver, hexagonal vertices belong to Opponent, rectangular vertices belong to the literal indicated in the bottom right corner (if any). The red cloud lists the set of players for which this vertex is in the co-Büchi condition. to the co-Büchi set of… view at source ↗
Figure 33
Figure 33. Figure 33: The game G † ↾𝑣1 0 1 A𝑖 𝑞1, . . . , 𝑞𝑛, ▽ 𝑣0 𝑣 ∈ 𝑉 \ {𝑣0} 𝑞1, . . . , 𝑞𝑛, ▽ ∗ (a) Parity automata A † 𝑖 for player 𝑖 to win 0 1 𝑞1, . . . , 𝑞𝑛, ▽, 𝑣 ∈ 𝑉 \ {𝑣0} 𝑣0 ∗ (b) Parity automaton A † 𝔅 . 1 0 𝑞1, . . . , 𝑞𝑛, ▽, 𝑣 ∈ 𝑉 \ {𝑣0} 𝑣0 ∗ (c) Parity automaton A † 𝔄 [PITH_FULL_IMAGE:figures/full_fig_p148_33.png] view at source ↗
Figure 34
Figure 34. Figure 34: Automata associated to the game G † either choose to continue or reach a sink state ▽, as depicted by [PITH_FULL_IMAGE:figures/full_fig_p148_34.png] view at source ↗
Figure 35
Figure 35. Figure 35: A game where randomization might be useful [PITH_FULL_IMAGE:figures/full_fig_p152_35.png] view at source ↗
Figure 36
Figure 36. Figure 36: A game without SPE multiplayer game. In this case, its purpose is no longer to prevent a player, viewed as an opponent, from using some information, but rather to use randomness to distribute payoffs among several players in such a way that they are satisfied with the expected payoff they receive. Example 16. Consider the mean-payoff game depicted in [PITH_FULL_IMAGE:figures/full_fig_p152_36.png] view at source ↗
Figure 37
Figure 37. Figure 37: A stochastic MDP Risk measures. A risk measure captures the perception that a player has of what their payoff will be. In that sense, they generalize the notion of expected payoff. Various risk measures exist in the literature, and have been used extensively in the field of economics and finance. Some of these risk measures include expected shortfall (ES), value at risk (VaR) [Aue18], variance [Bra99], en… view at source ↗
Figure 38
Figure 38. Figure 38: Each curve represents the perceived reward of a player choosing only blue strategy, only red, [PITH_FULL_IMAGE:figures/full_fig_p155_38.png] view at source ↗
Figure 39
Figure 39. Figure 39: Converting simple quantitative games into reachability games [PITH_FULL_IMAGE:figures/full_fig_p160_39.png] view at source ↗
Figure 40
Figure 40. Figure 40: Some games involving two pessimistic players [PITH_FULL_IMAGE:figures/full_fig_p169_40.png] view at source ↗
Figure 41
Figure 41. Figure 41: Construction of a game G𝜑 from a 3Sat formula 𝜑 ▶ Construction of the game G𝜑 : vertices, edges and payoffs For each literal ℓ, we define two players □ℓ and ◦ℓ. We add one other player 𝐶𝑖 for each clause 𝐶𝑖 , and an additional constraining player ^. All players are pessimists. Each player owns at most one vertex in the game, and therefore, we will refer to the player and vertex interchangeably. There is o… view at source ↗
read the original abstract

To verify the robustness of a program or protocol, it is common in the computer science community to rely on the theoretical framework of game theory. In particular, if one seeks to enforce a desired property, or specification, despite an unpredictable environment, a useful abstraction is to model the situation as a two-player zero-sum game. The goal is then to find a strategy for the system that guarantees the specification against any strategy of the environment. However, to model more complex situations, such as multiple systems with different objectives or an environment composed of various agents, the richer framework of multiplayer games must be considered. In this setting, a natural question is to identify equilibria, i.e., strategy profiles that are robust in the sense that no player has an incentive to deviate. The most well-known equilibrium concept is the Nash equilibrium, but several alternatives exist. We study five such notions and, for each of them, we provide complexity results for the constrained existence problem, which consists of deciding whether a given game contains an equilibrium that ensures each player a payoff within a specified interval.

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 / 3 minor

Summary. The paper examines five equilibrium notions in multiplayer graph games and classifies the computational complexity of the constrained existence problem for each: deciding whether there exists an equilibrium strategy profile such that every player's payoff lies in a given interval.

Significance. If the classifications are correct, the results map out the complexity landscape for equilibrium computation in non-zero-sum multiplayer settings on graphs, extending standard two-player zero-sum verification techniques to multi-agent scenarios with payoff constraints. This is useful for protocol and system verification where multiple components have distinct objectives.

minor comments (3)
  1. The abstract lists five notions but does not name them explicitly; §1 should enumerate the five concepts (e.g., Nash, subgame-perfect, etc.) with forward references to their formal definitions.
  2. Notation for payoff intervals and strategy profiles is introduced without a consolidated table; a small table in §2 summarizing the five notions, their payoff functions, and the decision problem would improve readability.
  3. The complexity claims are stated as 'PSPACE-complete' or similar for each notion; the reduction sections should include a short paragraph contrasting the proof techniques across the five cases to highlight where the arguments diverge.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our work and for recommending minor revision. The referee's assessment correctly identifies the core contribution: complexity classifications for the constrained existence problem across five equilibrium notions in multiplayer graph games on graphs.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper classifies the complexity of the constrained existence problem for five standard equilibrium notions in multiplayer graph games. It relies on the usual definitions of graph games, payoff functions, and equilibrium concepts, then establishes results via reductions to known complexity problems. No derivation step reduces by construction to its own inputs, no fitted parameters are relabeled as predictions, and no load-bearing self-citation chain or imported uniqueness theorem appears. The central claims remain independent of the paper's own outputs and align with standard algorithmic game theory methodology.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard definitions from algorithmic game theory with no free parameters, new entities, or ad-hoc axioms introduced in the abstract.

axioms (1)
  • domain assumption Standard definitions of multiplayer graph games, strategy profiles, and the five equilibrium concepts are assumed to hold.
    The abstract relies on established models in the field without re-deriving them.

pith-pipeline@v0.9.0 · 5714 in / 1071 out tokens · 41202 ms · 2026-05-20T04:17:14.568417+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

294 extracted references · 294 canonical work pages · 4 internal anchors

  1. [1]

    1838 , publisher =

    Augustin Cournot , title =. 1838 , publisher =

    work page

  2. [2]

    Subgame-Perfect Equilibria in Mean-Payoff Games , booktitle =

    L. Subgame-Perfect Equilibria in Mean-Payoff Games , booktitle =. 2021 , url =. doi:10.4230/LIPICS.CONCUR.2021.8 , timestamp =

    work page doi:10.4230/lipics.concur.2021.8 2021

  3. [3]

    2025 , eprint=

    Finding equilibria: simpler for pessimists, simplest for optimists , author=. 2025 , eprint=

    work page 2025

  4. [4]

    , title =

    Kuhn, Harold W. , title =. Contributions to the Theory of Games, Volume II , editor =

    work page

  5. [5]

    Heinrich von Stackelberg , title =

    work page

  6. [6]

    Synthesizing Protocols for Digital Contract Signing

    Chatterjee, Krishnendu and Raman, Vishwanath. Synthesizing Protocols for Digital Contract Signing. Verification, Model Checking, and Abstract Interpretation. 2012

    work page 2012

  7. [7]

    Henzinger and Marcin Jurdziński , keywords =

    Krishnendu Chatterjee and Thomas A. Henzinger and Marcin Jurdziński , keywords =. Games with secure equilibria , journal =. 2006 , note =. doi:https://doi.org/10.1016/j.tcs.2006.07.032 , url =

    work page doi:10.1016/j.tcs.2006.07.032 2006

  8. [8]

    Rational Synthesis

    Fisman, Dana and Kupferman, Orna and Lustig, Yoad. Rational Synthesis. Tools and Algorithms for the Construction and Analysis of Systems. 2010

    work page 2010

  9. [9]

    Infinite sequential games with real-valued payoffs , year =

    Le Roux, St\'. Infinite sequential games with real-valued payoffs , year =. Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) , articleno =. doi:10.1145/2603088.2603120 , abstract =

    work page doi:10.1145/2603088.2603120

  10. [10]

    Raskin and M

    J.-F. Raskin and M. Samuelides and L. Games for Counting Abstractions , journal =. 2005 , note =. doi:https://doi.org/10.1016/j.entcs.2005.04.005 , url =

    work page doi:10.1016/j.entcs.2005.04.005 2005

  11. [11]

    Subgame perfection in recursive perfect information games , journal =

    Jeroen Kuipers and J. Subgame perfection in recursive perfect information games , journal =. 2021 , doi =

    work page 2021

  12. [12]

    Bishop , title =

    Christopher M. Bishop , title =. 2006 , isbn =

    work page 2006

  13. [13]

    Proceedings of the Fifth International Congress of Mathematicians, Cambridge 1912 , volume =

    Zermelo, Ernst , title =. Proceedings of the Fifth International Congress of Mathematicians, Cambridge 1912 , volume =. 1913 , publisher =

    work page 1912

  14. [14]

    Patricia Bouyer and Romain Brenguier and Nicolas Markey and Michael Ummels , title =. Log. Methods Comput. Sci. , volume =. 2015 , url =. doi:10.2168/LMCS-11(2:9)2015 , timestamp =

    work page doi:10.2168/lmcs-11(2:9)2015 2015

  15. [15]

    26th International Symposium on Temporal Representation and Reasoning (TIME 2019) , pages =

    Bouyer, Patricia , title =. 26th International Symposium on Temporal Representation and Reasoning (TIME 2019) , pages =. 2019 , volume =. doi:10.4230/LIPIcs.TIME.2019.3 , annote =

    work page doi:10.4230/lipics.time.2019.3 2019

  16. [16]

    Pessimism of the Will, Optimism of the Intellect: Fair Protocols with Malicious but Rational Agents , journal =

    L. Pessimism of the Will, Optimism of the Intellect: Fair Protocols with Malicious but Rational Agents , journal =. 2024 , url =. doi:10.48550/ARXIV.2405.18958 , eprinttype =. 2405.18958 , timestamp =

    work page doi:10.48550/arxiv.2405.18958 2024

  17. [17]

    Rational Verification for

    L. Rational Verification for. 48th International Symposium on Mathematical Foundations of Computer Science,. 2023 , url =. doi:10.4230/LIPICS.MFCS.2023.26 , timestamp =

    work page doi:10.4230/lipics.mfcs.2023.26 2023

  18. [18]

    The Complexity of

    L. The Complexity of. 49th International Colloquium on Automata, Languages, and Programming,. 2022 , url =. doi:10.4230/LIPICS.ICALP.2022.116 , timestamp =

    work page doi:10.4230/lipics.icalp.2022.116 2022

  19. [19]

    On the Complexity of

    L. On the Complexity of. 30th. 2022 , url =. doi:10.4230/LIPICS.CSL.2022.10 , timestamp =

    work page doi:10.4230/lipics.csl.2022.10 2022

  20. [20]

    Subgame-perfect Equilibria in Mean-payoff Games (journal version) , journal =

    L. Subgame-perfect Equilibria in Mean-payoff Games (journal version) , journal =. 2023 , url =. doi:10.46298/LMCS-19(4:6)2023 , timestamp =

    work page doi:10.46298/lmcs-19(4:6)2023 2023

  21. [21]

    Annals of Mathematics , year =

    John Nash , title =. Annals of Mathematics , year =

    work page

  22. [22]

    Martin , title =

    Donald A. Martin , title =. Annals of Mathematics , pages =. 1975 , timestamp =

    work page 1975

  23. [23]

    2007 , month = jan, note =

    Schumann, Ricardo , title =. 2007 , month = jan, note =

    work page 2007

  24. [24]

    Contributions to the Theory of Games, Volume III , editor =

    Everett, Hugh , title =. Contributions to the Theory of Games, Volume III , editor =. 1957 , publisher =. doi:10.1515/9781400829156-014 , url =

    work page doi:10.1515/9781400829156-014 1957

  25. [25]

    Algorithms for Omega-Regular Games with Imperfect Information , journal =

    Jean. Algorithms for Omega-Regular Games with Imperfect Information , journal =. 2007 , url =. doi:10.2168/LMCS-3(3:4)2007 , timestamp =

    work page doi:10.2168/lmcs-3(3:4)2007 2007

  26. [26]

    Martin , title =

    Donald A. Martin , title =. J. Symb. Log. , volume =. 1998 , url =. doi:10.2307/2586667 , timestamp =

    work page doi:10.2307/2586667 1998

  27. [27]

    Henzinger and Philippe Rannou , editor =

    Krishnendu Chatterjee and Laurent Doyen and Herbert Edelsbrunner and Thomas A. Henzinger and Philippe Rannou , editor =. Mean-Payoff Automaton Expressions , booktitle =. 2010 , timestamp =

    work page 2010

  28. [28]

    Pareto Curves of Multidimensional Mean-Payoff Games , booktitle =

    Romain Brenguier and Jean. Pareto Curves of Multidimensional Mean-Payoff Games , booktitle =. 2015 , url =. doi:10.1007/978-3-319-21668-3\_15 , timestamp =

    work page doi:10.1007/978-3-319-21668-3 2015

  29. [29]

    Infinite Runs in Weighted Timed Automata with Energy Constraints , booktitle =

    Patricia Bouyer and Ulrich Fahrenberg and Kim Guldstrand Larsen and Nicolas Markey and Jir. Infinite Runs in Weighted Timed Automata with Energy Constraints , booktitle =. 2008 , url =. doi:10.1007/978-3-540-85778-5\_4 , timestamp =

    work page doi:10.1007/978-3-540-85778-5 2008

  30. [30]

    A Characterization of Subgame-Perfect Equilibrium Plays in

    J. A Characterization of Subgame-Perfect Equilibrium Plays in. Math. Oper. Res. , volume =. 2017 , url =. doi:10.1287/moor.2016.0843 , timestamp =

    work page doi:10.1287/moor.2016.0843 2017

  31. [31]

    Weak Subgame Perfect Equilibria and their Application to Quantitative Reachability , booktitle =

    Thomas Brihaye and V. Weak Subgame Perfect Equilibria and their Application to Quantitative Reachability , booktitle =. 2015 , series =

    work page 2015

  32. [32]

    Reinhard Selten , journal =

    work page

  33. [34]

    1997 , isbn =

    Michael Sipser , title =. 1997 , isbn =

    work page 1997

  34. [35]

    Solution Concepts and Algorithms for Infinite Multiplayer Games , volume =

    Erich Gr. Solution Concepts and Algorithms for Infinite Multiplayer Games , volume =

    work page

  35. [36]

    Multiplayer Cost Games with Simple

    Thomas Brihaye and Julie. Multiplayer Cost Games with Simple. Logical Foundations of Computer Science, Int. Symp.,. 2013 , url =. doi:10.1007/978-3-642-35722-0\_5 , timestamp =

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

  36. [38]

    1999 , institution=

    On the impossibility of fair exchange without a trusted third party , author=. 1999 , institution=

    work page 1999

  37. [39]

    Robust Equilibria in Mean-Payoff Games , booktitle =

    Romain Brenguier , editor =. Robust Equilibria in Mean-Payoff Games , booktitle =. 2016 , month = apr, url =. doi:10.1007/978-3-662-49630-5\_13 , timestamp =

    work page doi:10.1007/978-3-662-49630-5 2016

  38. [40]

    Modalities for model checking: branching time logic strikes back , journal =

    E. Modalities for model checking: branching time logic strikes back , journal =. 1987 , issn =. doi:https://doi.org/10.1016/0167-6423(87)90036-0 , url =

    work page doi:10.1016/0167-6423(87)90036-0 1987

  39. [41]

    Complexity Bounds for Regular Games , booktitle=

    Hunter, Paul and Dawar, Anuj. Complexity Bounds for Regular Games , booktitle=. 2005 , publisher=

    work page 2005

  40. [42]

    Parameterized complexity of games with monotonically ordered omega-regular objectives , booktitle =

    V. Parameterized complexity of games with monotonically ordered omega-regular objectives , booktitle =. 2018 , url =. doi:10.4230/LIPICS.CONCUR.2018.29 , timestamp =

    work page doi:10.4230/lipics.concur.2018.29 2018

  41. [43]

    Symbolic Reactive Synthesis for the Safety and

    Daniel Hausmann and Mathieu Lehaut and Nir Pitermann , year=. Symbolic Reactive Synthesis for the Safety and. 2305.02793 , archivePrefix=

    work page arXiv

  42. [44]

    Tree Automata Techniques and Applications , year = 2007, month = nov, url=

    Comon. Tree Automata Techniques and Applications , year = 2007, month = nov, url=

    work page 2007

  43. [45]

    Lower bounds for natural proof systems , year=

    Kozen, Dexter , booktitle=. Lower bounds for natural proof systems , year=

    work page

  44. [46]

    2016 , eprint=

    Pure and Stationary Optimal Strategies in Perfect-Information Stochastic Games with Global Preferences , author=. 2016 , eprint=

    work page 2016

  45. [47]

    Michael Wehar , title =

    work page

  46. [48]

    Multi-Player Quantitative Games: Equilibria and Algorithms , school =

    No\'. Multi-Player Quantitative Games: Equilibria and Algorithms , school =

    work page

  47. [49]

    On the Existence of Weak Subgame Perfect Equilibria , booktitle =

    V. On the Existence of Weak Subgame Perfect Equilibria , booktitle =. 2017 , series =

    work page 2017

  48. [50]

    The complexity of mean payoff games , volume =

    Uri Zwick and Mike Paterson , year =. The complexity of mean payoff games , volume =. LNCS , publisher =

    work page

  49. [51]

    RatFish: A File Sharing Protocol Provably Secure against Rational Users , booktitle =

    Backes, Michael and Ciobotaru, Oana and Krohmer, Anton , editor =. RatFish: A File Sharing Protocol Provably Secure against Rational Users , booktitle =. 2010 , month = 9, publisher =

    work page 2010

  50. [52]

    2006 , isbn =

    Abraham, Ittai and Dolev, Danny and Gonen, Rica and Halpern, Joe , title =. 2006 , isbn =. doi:10.1145/1146381.1146393 , booktitle =

    work page doi:10.1145/1146381.1146393 2006

  51. [53]

    A formal model of rational exchange and its application to the analysis of Syverson's protocol , journal =

    Levente Butty. A formal model of rational exchange and its application to the analysis of Syverson's protocol , journal =. 2004 , doi =

    work page 2004

  52. [54]

    and Schneider, Fred B

    Clarkson, Michael R. and Schneider, Fred B. , title =. doi:10.3233/JCS-2009-0393 , journal =

    work page doi:10.3233/jcs-2009-0393 2009

  53. [55]

    45th International Symposium on Mathematical Foundations of Computer Science,

    Kristoffer Arnsfelt Hansen and Steffan Christ S. 45th International Symposium on Mathematical Foundations of Computer Science,. 2020 , url =. doi:10.4230/LIPICS.MFCS.2020.45 , timestamp =

    work page doi:10.4230/lipics.mfcs.2020.45 2020

  54. [56]

    42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) , pages =

    Gallego-Hern\'. 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) , pages =. 2025 , volume =. doi:10.4230/LIPIcs.STACS.2025.37 , annote =

    work page doi:10.4230/lipics.stacs.2025.37 2025

  55. [57]

    2024 , issue_date =

    Rakotonirina, Itsaka and Barthe, Gilles and Schneidewind, Clara , title =. 2024 , issue_date =. doi:10.1145/3632906 , journal =

    work page doi:10.1145/3632906 2024

  56. [58]

    and Jurdzi \' n ski, Marcin

    Chatterjee, Krishnendu and Henzinger, Thomas A. and Jurdzi \' n ski, Marcin. Games with Secure Equilibria. Formal Methods for Components and Objects. 2005

    work page 2005

  57. [59]

    A Game-Based Verification of Non-Repudiation and Fair Exchange Protocols , volume =

    Kremer, Steve and Raskin, Jean-Fran. A Game-Based Verification of Non-Repudiation and Fair Exchange Protocols , volume =. Journal of Computer Security , number =. 2003 , url =

    work page 2003

  58. [60]

    Secure equilibria in weighted games , booktitle =

    V. Secure equilibria in weighted games , booktitle =

    work page

  59. [61]

    Frankfurter Allgemeine Zeitung , year =

    Ariel Rubinstein , title =. Frankfurter Allgemeine Zeitung , year =

    work page

  60. [63]

    2000 , howpublished =

    Bernard Guerrien , title =. 2000 , howpublished =

    work page 2000

  61. [64]

    Simon , title =

    Herbert A. Simon , title =. Psychological Review , volume =. 1956 , doi =

    work page 1956

  62. [65]

    The Adversarial

    Filiot, Emmanuel and Gentilini, Raffaella and Raskin, Jean-Fran. The Adversarial. 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) , pages =. 2020 , volume =. doi:10.4230/LIPIcs.ICALP.2020.127 , annote =

    work page doi:10.4230/lipics.icalp.2020.127 2020

  63. [66]

    Henzinger and Nir Piterman , title =

    Krishnendu Chatterjee and Thomas A. Henzinger and Nir Piterman , title =. Inf. Comput. , volume =. 2010 , url =. doi:10.1016/j.ic.2009.07.004 , timestamp =

    work page doi:10.1016/j.ic.2009.07.004 2010

  64. [67]

    Computer Aided Synthesis:

    V. Computer Aided Synthesis:. Developments in Language Theory - 21st International Conference,. 2017 , series =

    work page 2017

  65. [68]

    Romain Brenguier and Lorenzo Clemente and Paul Hunter and Guillermo A. P. Non-Zero Sum Games for Reactive Synthesis , booktitle =

    work page

  66. [69]

    Perfect-Information Games with Lower-Semicontinuous Payoffs , journal =

    J. Perfect-Information Games with Lower-Semicontinuous Payoffs , journal =

    work page

  67. [70]

    Proceedings of The 10th Computer Security Foundations Workshop , pages=

    Zhou, Jianying and Gollmann, Dieter , title=. Proceedings of The 10th Computer Security Foundations Workshop , pages=

    work page

  68. [71]

    The Non-Cooperative Rational Synthesis Problem for Subgame Perfect Equilibria and omega-regular Objectives , journal =

    V. The Non-Cooperative Rational Synthesis Problem for Subgame Perfect Equilibria and omega-regular Objectives , journal =. 2024 , url =. doi:10.48550/ARXIV.2412.08547 , eprinttype =. 2412.08547 , timestamp =

    work page doi:10.48550/arxiv.2412.08547 2024

  69. [72]

    The Complexity of Rational Synthesis , booktitle =

    Rodica Condurache and Emmanuel Filiot and Raffaella Gentilini and Jean. The Complexity of Rational Synthesis , booktitle =. 2016 , url =. doi:10.4230/LIPICS.ICALP.2016.121 , timestamp =

    work page doi:10.4230/lipics.icalp.2016.121 2016

  70. [73]

    Karp , title =

    Richard M. Karp , title =. Discret. Math. , volume =

    work page

  71. [74]

    Wooldridge , title =

    Julian Gutierrez and Muhammad Najib and Giuseppe Perelli and Michael J. Wooldridge , title =. Ann. Math. Artif. Intell. , volume =. 2023 , url =. doi:10.1007/S10472-022-09804-3 , timestamp =

    work page doi:10.1007/s10472-022-09804-3 2023

  72. [75]

    Annals of Mathematics , volume=

    Recursive unsolvability of Post's problem of "tag" and other topics in theory of Turing machines , author=. Annals of Mathematics , volume=. 1961 , publisher=

    work page 1961

  73. [76]

    Journal of Mathematical Economics , volume =

    Deterministic multi-player. Journal of Mathematical Economics , volume =. 2003 , issn =. doi:https://doi.org/10.1016/S0304-4068(03)00021-1 , url =

    work page doi:10.1016/s0304-4068(03)00021-1 2003

  74. [77]

    Henzinger and Alexander Moshe Rabinovich and Jean

    Yaron Velner and Krishnendu Chatterjee and Laurent Doyen and Thomas A. Henzinger and Alexander Moshe Rabinovich and Jean. The complexity of multi-mean-payoff and multi-energy games , journal =

    work page

  75. [78]

    The Complexity of Subgame Perfect Equilibria in Quantitative Reachability Games , booktitle =

    Thomas Brihaye and V. The Complexity of Subgame Perfect Equilibria in Quantitative Reachability Games , booktitle =. 2019 , url =. doi:10.4230/LIPIcs.CONCUR.2019.13 , timestamp =

    work page doi:10.4230/lipics.concur.2019.13 2019

  76. [79]

    Henzinger and Jan Otop , title =

    Udi Boker and Thomas A. Henzinger and Jan Otop , title =. 30th Annual. 2015 , url =. doi:10.1109/LICS.2015.74 , timestamp =

    work page doi:10.1109/lics.2015.74 2015

  77. [80]

    Memoryless determinacy of parity and mean payoff games: a simple proof , journal =

    Henrik Bj. Memoryless determinacy of parity and mean payoff games: a simple proof , journal =. 2004 , url =. doi:10.1016/S0304-3975(03)00427-4 , timestamp =

    work page doi:10.1016/s0304-3975(03)00427-4 2004

  78. [81]

    Half-Positional Determinacy of Infinite Games , booktitle =

    Eryk Kopczynski , editor =. Half-Positional Determinacy of Infinite Games , booktitle =. 2006 , timestamp =

    work page 2006

  79. [82]

    The Complexity of

    Michael Ummels , editor =. The Complexity of. Foundations of Software Science and Computational Structures, 11th International Conference,. 2008 , url =. doi:10.1007/978-3-540-78499-9\_3 , timestamp =

    work page doi:10.1007/978-3-540-78499-9 2008

  80. [83]

    2008 , publisher=

    Modern actuarial risk theory , author=. 2008 , publisher=

    work page 2008

Showing first 80 references.