Entropy Games and Matrix Multiplication Games

DOI10.4230/LIPICS.STACS.2016.11zbMATH Open1390.91016arXiv1506.04885MaRDI QIDQ4601862FDOQ4601862

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

Publication date: 24 January 2018

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.

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

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

zbMATH Keywords

entropygame theoryjoint spectral radius

Mathematics Subject Classification ID

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

Cited In (13)

• Consensus in asynchronous multiagent systems. II: Method of joint spectral radius
• A convergent hierarchy of non-linear eigenproblems to compute the joint spectral radius of nonnegative matrices
• On convergence of infinite matrix products with alternating factors from two sets of matrices
• Minkowski games
• Title not available (Why is that?)
• Spectral inequalities for nonnegative tensors and their tropical analogues
• The operator approach to entropy games
• Minimax theorem for the spectral radius of the product of non-negative matrices
• Multi ping-pong and an entropy estimate in groups
• Entropic risk for turn-based stochastic games
• Consensus in asynchronous multiagent systems. III: Constructive stability and stabilizability
• The operator approach to entropy games
• The greedy strategy for optimizing the Perron eigenvalue

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)