Nash equilibria in symmetric graph games with partial observation

DOI10.1016/J.IC.2016.10.010MaRDI QIDQ528190zbMATH OpenOpenAlexFDO

Authors Patricia Bouyer, Nicolas Markey, Steen Vester

Publication date 12 May 2017

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.0839, https://orbit.dtu.dk/en/publications/f87bbce7-e1e4-4c14-89ed-323ab4b6b577

zbMATH Keywords

symmetrygames on graphsNash equilibriumnetwork of systems

Mathematics Subject Classification ID

Noncooperative games (91A10) (n)-person games, (n>2) (91A06) Games involving graphs (91A43)

Abstract: We investigate a model for representing large multiplayer games, which satisfy strong symmetry properties. This model is made of multiple copies of an arena; each player plays in his own arena, and can partially observe what the other players do. Therefore, this game has partial information and symmetry constraints, which make the computation of Nash equilibria difficult. We show several undecidability results, and for bounded-memory strategies, we precisely characterize the complexity of computing pure Nash equilibria (for qualitative objectives) in this game model.

Recommendations

• Nash equilibria in symmetric games with partial observation
• Symmetries and the complexity of pure Nash equilibrium
• Equilibria of graphical games with symmetries
• Symmetries and the Complexity of Pure Nash Equilibrium
• The complexity of Nash equilibria in stochastic multiplayer games

Cites work

• scientific article; zbMATH DE number 5301288 (Why is no real title available?)
• scientific article; zbMATH DE number 5585443 (Why is no real title available?)
• A course in game theory.
• Alternating-time temporal logic
• Augmenting ATL with strategy contexts
• Automata, logics, and infinite games. A guide to current research
• CONCUR 2004 - Concurrency Theory
• Computer Science Logic
• Concurrent games with ordered objectives
• Control of parameterized discrete event systems
• Equilibrium points in n -person games
• Games with secure equilibria
• Mixed Nash equilibria in concurrent terminal-reward games
• Modular strategies for recursive game graphs
• Multiagent Systems
• Non-cooperative games
• Parameterized Model Checking of Token-Passing Systems
• Parameterized model checking of rendezvous systems
• Playing with probabilities in reconfigurable broadcast networks
• Positional strategies for mean payoff games
• Pure Nash equilibria in concurrent deterministic games
• Reasoning about strategies
• Reasoning about strategies: on the model-checking problem
• Reasoning about systems with many processes
• Stochastic Games
• Strategy logic
• Symmetries and the complexity of pure Nash equilibrium
• The Existence of Equilibrium in Discontinuous Economic Games, I: Theory
• The complexity of Nash equilibria in stochastic multiplayer games
• The complexity of finding Nash equilibria
• The complexity of propositional linear temporal logics

Cited in

(7)

• A generative relation for Nash equilibria on symmetric action graph games
• Nash equilibria and values through modular partitions in infinite games
• Observation, measurement, and computation in finite games
• A game-theoretic approach to indistinguishability of winning objectives as user privacy
• Games on graphs with a public signal monitoring
• Nash equilibria in symmetric games with partial observation
• Game-based Synthesis of Distributed Controllers for Sampled Switched Systems

This page was built for publication: Nash equilibria in symmetric graph games with partial observation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q528190)