Playing Games with Bounded Entropy: Convergence Rate and Approximate Equilibria
share
We consider zero-sum repeated games in which the players are restricted to strategies that require only a limited amount of randomness. Let v_n be the max-min value of the n stage game; previous works have characterized _n→∞v_n, i.e., the long-run max-min value. Our first contribution is to study the convergence rate of v_n to its limit. To this end, we provide a new tool for simulation of a source (target source) from another source (coin source). Considering the total variation distance as the measure of precision, this tool offers an upper bound for the precision of simulation, which is vanishing exponentially in the difference of Rényi entropies of the coin and target sources. In the second part of paper, we characterize the set of all approximate Nash equilibria achieved in long run. It turns out that this set is in close relation with the long-run max-min value.
READ FULL TEXT