The Complexity of Nash Equilibria in Limit-Average Games

DOI10.1007/978-3-642-23217-6_32zbMath1343.68177arXiv1109.6220OpenAlexW3105321970MaRDI QIDQ3090850

Dominik Wojtczak, Michael Ummels

Publication date: 2 September 2011

Published in: CONCUR 2011 – Concurrency Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1109.6220

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items

Equilibria for games with combined qualitative and quantitative objectives, Extending finite-memory determinacy to multi-player games, Reasoning about equilibria in game-like concurrent systems, Incentive Stackelberg Mean-Payoff Games, The Complexity of Infinitely Repeated Alternating Move Games, Mean-payoff games with \(\omega\)-regular specifications, On Pure Nash Equilibria in Stochastic Games, On the complexity of rational verification, Unnamed Item, Unnamed Item, Incentive Engineering for Concurrent Games, Unnamed Item, Unnamed Item, Unnamed Item, Equilibria in multi-player multi-outcome infinite sequential games, A Note on Game Theory and Verification, Unnamed Item, Unnamed Item, Unnamed Item, Robust Equilibria in Mean-Payoff Games, Unnamed Item, A game-theoretic approach for the synthesis of complex systems, Iterated Boolean games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• New complexity results about Nash equilibria
• Positional strategies for mean payoff games
• A characterization of the minimum cycle mean in a digraph
• The complexity of mean payoff games on graphs
• Perfect information stochastic games and related classes
• Two-player stochastic games. I: A reduction
• Two-player stochastic games. II: The case of recursive games
• Deterministic graphical games
• Concurrent reachability games
• Generalized Mean-payoff and Energy Games
• Church Synthesis Problem for Noisy Input
• On the Complexity of Nash Equilibria and Other Fixed Points
• The Complexity of Nash Equilibria in Stochastic Multiplayer Games
• Settling the complexity of computing two-player Nash equilibria
• Rational Synthesis
• Nash Equilibria for Reachability Objectives in Multi-player Timed Games
• On Omega-Languages Defined by Mean-Payoff Conditions
• The Complexity of Nash Equilibria in Simple Stochastic Multiplayer Games
• On the Complexity of Numerical Analysis
• The Complexity of Computing a Nash Equilibrium
• The Complexity of Nash Equilibria in Infinite Multiplayer Games
• Equilibrium points in n -person games
• Stochastic Games
• Stochastic games