Nash equilibria in symmetric graph games with partial observation

DOI10.1016/J.IC.2016.10.010zbMATH Open1371.91021arXiv1404.0839OpenAlexW2963845824MaRDI QIDQ528190FDOQ528190

Authors: Patricia Bouyer, Nicolas Markey, Steen Vester 

Publication date: 12 May 2017

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

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.

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

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

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)

Cites Work

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

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)