THE CONTROLLED BIASED COIN PROBLEM
Olivier Gossner, Tristan Tomala · 2005
Abstract. We study the maxmin value of a zero-sum repeated game where player 1 is restricted to pure strategies but privately observes the realizations of some random variables. This kind of problem was introduced by Gossner and Vieille [GV02] in the case where player 1 observes i.i.d. random variables. The paper solves the case where the law of the random variable (the coin) depends on player 1’s action. We also discuss the general case where the law of the coin is controlled by both players. 1. Model and definitions 1.1. The repeated game. Let (A,B, g) be a zero-sum game where, A (resp. B) is the finite set of actions of player 1 (resp.2) and g: A×B → R is the payoff function. Let S be a finite set of signals and µ: A → ∆(S) be a transition probability. The repeated game unfolds as follows. At each stage t = 1, 2,..., each player chooses an action in her own set of actions and if (a, b) ∈ A×B is the action profile played, the payoff for player 1 is g(a, b). A signal s is then drawn according to µ(·|a) and announced to player 1 only. A history of length n of the game [resp. for player 2] is an element hn of Hn = (A × B × S)n, [resp. h2n of H2n = (A × B)n]. A pure strategy σ for player 1 is a sequence (σn)n≥0 with σn: Hn → A. A behavioral strategy τ for player 2 is a sequence (τn)n≥0 with τn: H2n → ∆(B), where ∆(B) denotes the set of probabilities on B. A pair of strategies (σ, τ) with σ pure and τ behavioral induce a probability distribution Pσ,τ on the set of plays (A × B × S) ∞ endowed with the product σ-algebra. The average payoff up to stage n is: γn(σ, τ) = Eσ,τ [ 1n ∑n m=1 g(am,bm)] where (am,bm) is the random pair of actions at stage n. The uniform maxmin payoff of the repeated game is defined as follows (see [GV02] for this model and [MSZ94] for general repeated games): Definition 1. (1) Player 1 guarantees v ∈ R if: ∀ε> 0,∃σ,∃N s.t. ∀τ, ∀n ≥ N, γn(σ, τ) ≥ v − ε. (2) Player 2 defends v ∈ R if: ∀ε> 0,∀σ, ∃τ,∃N s.t. ∀n ≥ N, γn(σ, τ) ≤ v + ε. (3) The maxmin is v ∞ ∈ R such that I guarantees v ∞ and II defends v∞. 1.2. Information theory tools. Let x be a finite random variable with law P. Throughout the paper, we write log to denote the logarithm with base 2. By definition, the entropy of x is: H(x) = −E[logP (x)] = −