Playing games with bounded entropy

DOI10.1016/J.GEB.2019.03.013zbMATH Open1411.91077arXiv1702.05719OpenAlexW2925652365WikidataQ128098533 ScholiaQ128098533MaRDI QIDQ2416656FDOQ2416656

Authors: Mehrdad Valizadeh, Amin Gohari 

Publication date: 24 May 2019

Published in: Games and Economic Behavior (Search for Journal in Brave)

Abstract: In this paper, we consider zero-sum repeated games in which the maximizer is restricted to strategies requiring no more than a limited amount of randomness. Particularly, we analyze the maxmin payoff of the maximizer in two models: the first model forces the maximizer to randomize her action in each stage just by conditioning her decision to outcomes of a given sequence of random source, whereas, in the second model, the maximizer is a team of players who are free to privately randomize their corresponding actions but do not have access to any explicit source of shared randomness needed for cooperation. The works of Gossner and Vieille, and Gossner and Tomala adopted the method of types to establish their results; however, we utilize the idea of random hashing which is the core of randomness extractors in the information theory literature. In addition, we adopt the well-studied tool of simulation of a source from another source. By utilizing these tools, we are able to simplify the prior results and generalize them as well. We characterize the maxmin payoff of the maximizer in the repeated games under study. Particularly, the maxmin payoff of the first model is fully described by the function $J(h)$ which is the maximum payoff that the maximizer can secure in a one-shot game by choosing mixed strategies of entropy at most $h$. In the second part of the paper, we study the computational aspects of $J(h)$. We offer three explicit lower bounds on the entropy-payoff trade-off curve. To do this, we provide and utilize new results for the set of distributions that guarantee a certain payoff for Alice. In particular, we study how this set of distributions shrinks as we increase the security level. While the use of total variation distance is common in game theory, our derivation indicates the suitability of utilizing the Renyi-divergence of order two.

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

Recommendations

• Repeated games with bounded entropy
• On finite strategy sets for finitely repeated zero-sum games.
• Strategic entropy and complexity in repeated games

zbMATH Keywords

information theoryrepeated gamesrandomness extractionentropy minimizationbounded entropysource simulation

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Multistage and repeated games (91A20)

Cites Work

• Equilibrium points in n -person games
• Repeated games with bounded entropy
• On the entropy of couplings
• Title not available (Why is that?)
• Secret Correlation in Repeated Games with Imperfect Monitoring
• Equivalence of additivity questions in quantum information theory
• Noiseless coding of correlated information sources
• Title not available (Why is that?)
• The equivalence of linear programs and zero-sum games
• How to play with a biased coin?
• Informationally optimal correlation
• The MinMax information measure
• Pattern recognition as a quest for minimum entropy
• Game theory and mechanism design
• Title not available (Why is that?)

Cited In (7)

• Simulation of a random variable and its application to game theory
• On finite strategy sets for finitely repeated zero-sum games.
• Shannon-like games are difficult
• How to play with a biased coin?
• Bounds on entropy in a guessing game
• Two-player location-price game in a spoke market with linear transportation cost
• Entropy Games and Matrix Multiplication Games

This page was built for publication: Playing games with bounded entropy

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