Title: Playing Games with Bounded Entropy,
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.