Entropy Games and Matrix Multiplication Games

DOI10.4230/LIPICS.STACS.2016.11MaRDI QIDQ4601862zbMATH OpenFDO

Authors Eugene Asarin, Julien Cervelle, Aldric Degorre, Cătălin Dima, Florian Horn, Victor Kozyakin

Publication date 24 January 2018

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

zbMATH Keywords

entropygame theoryjoint spectral radius

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10)

Abstract: Two intimately related new classes of games are introduced and studied: entropy games (EGs) and matrix multiplication games (MMGs). An EG is played on a finite arena by two-and-a-half players: Despot, Tribune and the non-deterministic People. Despot wants to make the set of possible People's behaviors as small as possible, while Tribune wants to make it as large as possible.An MMG is played by two players that alternately write matrices from some predefined finite sets. One wants to maximize the growth rate of the product, and the other to minimize it. We show that in general MMGs are undecidable in quite a strong sense.On the positive side, EGs correspond to a subclass of MMGs, and we prove that such MMGs and EGs are determined, and that the optimal strategies are simple. The complexity of solving such games is in NP&coNP.

Recommendations

• The combinatorial theory of matrix games
• The operator approach to entropy games
• The operator approach to entropy games
• scientific article; zbMATH DE number 908755
• On matrices, Nmatrices and games
• Entropy of hierarchical games
• Playing games with bounded entropy
• scientific article; zbMATH DE number 4211831
• Strategic entropy and complexity in repeated games
• Matrix games with nonuniform payoff distributions

Cited in

(14)

• On convergence of infinite matrix products with alternating factors from two sets of matrices
• Multi ping-pong and an entropy estimate in groups
• Spectral inequalities for nonnegative tensors and their tropical analogues
• The greedy strategy for optimizing the Perron eigenvalue
• Consensus in asynchronous multiagent systems. III: Constructive stability and stabilizability
• Consensus in asynchronous multiagent systems. II: Method of joint spectral radius
• The operator approach to entropy games
• Minimax theorem for the spectral radius of the product of non-negative matrices
• The operator approach to entropy games
• Minkowski games
• scientific article; zbMATH DE number 908755 (Why is no real title available?)
• Entropic risk for turn-based stochastic games
• Universal complexity bounds based on value iteration for stochastic mean payoff games and entropy games
• A convergent hierarchy of non-linear eigenproblems to compute the joint spectral radius of nonnegative matrices

This page was built for publication: Entropy Games and Matrix Multiplication Games

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