Playing Games with Bounded Entropy
Mehrdad Valizadeh, Amin Gohari
Department of Electrical Engineering, Sharif University of Technology, Tehran, Iran
(valizadeh@ee.sharif.edu, aminzadeh@sharif.edu)

Abstract

arXiv:1702.05719v3 [cs.IT] 19 Jan 2018

In this paper we consider zero-sum repeated games when the maximizer (player or team)
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 (the
Neyman-Okada/Gossner-Vieille 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, while in the second model (the Gossner and Tomala model) the maximizer is a
team of players who are free to randomize privately their corresponding actions but do
not 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 while we utilize the idea of random hashing which is the core of randomness
extractors in the information theory literature. Besides we adopt the well-studied tool of
simulation of a source from another source. By utilizing this tools, we are able to not
only simplify the prior results, but also generalize them. We give a full characterization
of the maxmin payoff of the maximizer in the repeated games under study. Particularly,
the maxmin value of the first model is fully described by the function J (h) where J (h)
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), which has not received much attention in the game theory literature. We observe the equivalence of this problem with entropy minimization
problems in other scientific contexts. Next, we provide three explicit lower bounds on the
entropy-payoff tradeoff curve. To do this, we provide and utilize new results for the set
Preprint submitted to Games and Economic Behavior

January 22, 2018

of distributions that guarantee a certain payoff for Alice (mixed strategies corresponding
to a security level 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.
Keywords:
Repeated Games, Bounded Entropy, Randomness Extraction, Source Simulation,
Entropy Minimization, Information Theory
Contents
1 Introduction

3

2 Preliminaries

9

2.1

Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2

Entropy function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3 Repeated games with a bounded randomness source

9

11

3.1

Problem definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3.2

Simplifying the proof of Gossner and Vieille (2002) . . . . . . . . . . . . . 13

3.3

Generalized model: leakage of the randomness source . . . . . . . . . . . . 17
3.3.1

Alice can secure Jcav (H(X|Y )) . . . . . . . . . . . . . . . . . . . . 18

3.3.2

Bob can defend Jcav (H(X|Y )) . . . . . . . . . . . . . . . . . . . . . 21

4 Secret correlation in repeated games with imperfect monitoring

22

4.1

Problem definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4.2

Payoff secured by the team A . . . . . . . . . . . . . . . . . . . . . . . . . 24

4.3

Player B can defend w . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

A short version of this paper was presented at the 2017 IEEE Symposium On Information Theory
(ISIT 2017).

2

5 Computation of min-entropy function

33

5.1

Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

5.2

On the set PU (w) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.2.1

5.3

On the min-entropy function . . . . . . . . . . . . . . . . . . . . . . 38

Lower and upper bounds on the min-entropy function . . . . . . . . . . . . 39

6 Proofs

46

6.1

Proof of Proposition 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

6.2

Proof of Proposition 17 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

6.3

Proof of Theorems 20 and 21

6.4

Proof of Theorem 23 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

6.5

Proof of Theorem 26 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

6.6

Proof of Theorem 30 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

6.7

Proof of Theorem 31 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

Appendix A

. . . . . . . . . . . . . . . . . . . . . . . . . 50

Review of the randomness extraction literature

60

Appendix A.1

Conditional collision entropy . . . . . . . . . . . . . . . . . . 60

Appendix A.2

Randomness extraction . . . . . . . . . . . . . . . . . . . . . 62

Appendix B

Proof of Lemma 36

67

1. Introduction
Nash (1950) proved that if the players of a given one shot game can randomize on their
pure strategies set according to any probability distribution, then the game has at least
one Nash equilibria in the randomized mixed strategies. Nevertheless, if the players have
restrictions on implementing their random actions, then implementable Nash equilibria
does not necessarily exist. More specifically, assume that one of the players is restricted to
constructing her actions as a deterministic function of a given random source. In this setup
Nash equilibria does not necessarily exist. Similarly, in a class of repeated games including
two-player zero-sum games, the Nash equilibria does not exist if sufficient random bits
3

are not available to the players (See Hubáček et al. (2016) and Budinich and Fortnow
(2011)). If the players are limited to a given amount of randomness, the maximum payoff
that each player can guarantee regardless of what the other players play, is of interest.
In this paper we study the maximum guaranteed payoff in repeated zero-sum games with
bounded randomness under two models. In the first model we consider a finitely repeated
version of a two-player zero-sum game where the private randomness available to one of
the players is limited. The second model is a zero-sum game between a team and an
adversary player where the players of the team are free to randomize their corresponding
actions privately but do not have access to any explicit source of shared randomness to
cooperate their actions. It is assumed that the adversary player monitors the played
actions imperfectly; hence the history of actions observed by the players of the team is
an implicit and limited random source for cooperation of the team.
A version of the first model is studied by Gossner and Vieille (2002). They study a
repeated version of a zero-sum game G between two players Alice and Bob where Alice is
the maximizer and Bob is the minimizer. At each stage, first Alice observes an independent drawing of a random source X whose distribution is a common knowledge. Next,
both players play an action which is monitored by the other player. Alice is restricted to
choose the action of each stage as a deterministic function of the observed random source
up to that stage and the history of the previous actions whereas Bob chooses his actions
at each stage as a random function of the history of the previous actions. Note that the
only source of randomization for Alice is the outcomes of random source X while Bob
can freely randomize his actions. For the one-shot game G, define J (h) as the maximum
expected payoff that Alice can secure (regardless of what Bob plays) by playing mixed
actions of entropy at most h. Let Jcav (.) be the upper concave envelope of J (.). Gossner and Vieille (2002) prove that the maximum expected average payoff of Alice in the
repeated game converges to Jcav (H(X)) where H(X) is the entropy of random variable
X. This is similar to Shannon’s compression formula H(X) which is defined on a single
copy of the source (single letter ), but gives the ultimate compression limit when multiple

4

copies of the source are observed.
Generalizing the model of Gossner and Vieille (2002) we study a repeated zero-sum
game that considers the possibility of leakage of Alice’s random source sequence to Bob;
thus we call repeated game with leaked randomness source. In other words, we assume that
Bob can imperfectly monitor the random source of Alice. More specifically, we assume an
i.i.d. sequence of pairs (X1 , Y1 ), (X2 , Y2 ), . . . distributed according to a given distribution
p(x, y). The sequence X1 , X2 , . . . is revealed symbol by symbol (causally) to Alice as the
game is played out, while the sequence Y1 , Y2 , . . . is revealed symbol by symbol to Bob. We
can view Yi as the leakage that Bob obtains about Alice’s observation. As before, Alice
cannot randomize freely and can only use the randomness in the sequence X1 , X2 , . . ..
We show that Jcav (H(X|Y )) is the maximum payoff that Alice can secure regardless of
Bob’s actions. This result is a generalization of the result of Gossner and Vieille (2002)
since when Y is a constant random variable, the conditional entropy H(X|Y ) reduces to
the unconditional entropy H(X). Furthermore, it is obtained that if a genie provides the
values of Y1 , Y2 , . . . symbol by symbol to Alice, the maximum payoff she can secure remains
unchanged. In other words, knowledge of what Bob knows about Alice’s observations is
not helpful to Alice.
The second model originally studied by Gossner and Tomala (2007) takes into account
the limited access of players of a team to shared randomness needed for cooperation
against an adversary. This model, which is called secret correlation in repeated games
with imperfect monitoring, consists of a zero-sum game G played between team A and
player B, repeatedly. Team A which consists of m players is the maximizer and player B is
the minimizer. At each stage, first, all players choose an action from their corresponding
set of actions and then the players of team A observe all of the actions played, while
player B observes a noisy version of the action profile of team A. To choose the action of
each stage, each player can privately randomize on her action and utilize the history of
her observations up to that stage. Since the action profile of team A is revealed to player
B just through a noisy channel, the players of team A could extract shared random bits

5

from the profile of actions while the extracted bits are independent of the observations
of player B. These shared bits can be utilized by players of team A to correlate their
actions in the upcoming stages. Although the players of team A can randomize their
actions privately and extract shared random bits, the extracted shared bits are limited.
Therefore in this setup the players of team A are constrained in the amount of shared
randomness they could extract and use.
In the model of Gossner and Tomala (2007), at each stage t, player B monitors the
action profile of team A through a noisy channel with output signal St . Gossner and
Tomala assume that St is not only seen by player B but also by the players of team A.
Generalizing the result of Gossner and Tomala (2007) we remove the assumption that the
players of team A observe St , and show that this causes no reduction in the payoff of team
A.
The above generalizations of the results of Gossner and Vieille (2002) and Gossner
and Tomala (2007) is immediate from our different proof technique. To explain this,
first observe that in order to construct the optimal strategies for the above two models of
repeated games, we need to simulate random actions from the available source of randomness. In the first model, the source of randomness is the random sequence X1 , X2 , . . .; in
the second model, the source of randomness is the history of (the imperfectly monitored)
played actions. Authors in Gossner and Vieille (2002) and Gossner and Tomala (2007)
introduce a new notion of absolute Kullback distance which is not used in the information
theory literature. They take the absolute Kullback distance as the measure of accuracy of
the simulation and utilize the method of types to simulate the desired random actions from
the source of randomness. On the other hand, we consider the total variation distance
as the measure of accuracy and utilize the standard method of random hashing. The
method of types alone is insufficient for obtaining the generalizations discussed in this
paper, and hashing is necessary. We separate the simulation of random actions from the
source of randomness into two steps: first we extract sufficient private random bits from
the randomness source and then simulate the desired actions using the extracted random

6

bits. Thus we need to use two tools for “randomness extraction”, and “simulation of a
source from another source”. These tools are available in the literature of information
theory for stationary or nonstationary/ergodic or nonergodic sources (the information
spectrum methods). Randomness extraction is reviewed in Appendix A of this paper for
completeness. By utilizing these tools we are able to simplify the proofs and generalize
the results of Gossner and Vieille (2002) and Gossner and Tomala (2007).
As stated above the maximum guaranteed payoff of Alice in the repeated game with
leaked randomness source (first model) is characterized in terms of J (h), the maximum
payoff that Alice can secure in the one shot game by choosing mixed actions with entropy
at most h. In this paper, we also study the computational aspects of J (h). Equivalently,
we study the inverse function of J (h) denoted by F (w). F (w) is the minimum entropy
of the randomness consumed by Alice to guarantee payoff w in the one shot game. We
may call F (w), the min-entropy function.

1

To compute F (w), one has to first consider the set of distributions on the action of
Alice that would secure a payoff w for her. This set will be a polytope in the space of all
probability distributions. Then, one should solve an entropy minimization problem over
this polytope in the space of probability distributions. In fact, minimizing and maximizing
entropy arises in a wide range of contexts. Computing maximum entropy under a set
of linear constraints is a well-studied problem with a wide range of applications, e.g.,
see Fang et al. (2012)(Cover and Thomas, 2012, p.367) and the principle of maximum
entropy. It is shown in Kapur et al. (1995) that computing the minimum entropy can
be also quite important. Furthermore, Watanabe (1981) shows that many algorithms for
clustering and pattern recognition are essentially solving entropy minimization problems.
An important special case of the entropy minimization problem (with its own applications)
is that of finding a joint probability of minimum entropy given its marginal distributions
(the marginal distribution is a linear constraint on the joint probability distribution); see
1

One should not confuse our “min-entropy function” with the term “min-entropy” commonly used to

denote the Rényi entropy of order infinity.

7

Kocaoglu et al. (2016); Cicalese et al. (2017); Kovaevi et al. (2015). Finally, Shor (2004)
shows that the quantum version of the entropy minimization problem is closely related to
a number of important problems in quantum information theory.
It is shown by Kovacevic et al. (2012) that entropy minimization problem is an NPhard non-convex optimization problem. Since the entropy is a concave function over the
probability simplex, its minimum occurs at a vertex of the feasible domain. As a result,
computation of F (w) leads to a search problem over an exponentially large set. Srikanth
et al. (2003) have proposed an algorithm to solve the entropy minimization problem (hence
could be used to compute F (w)), but it has no guarantee of finding the global minimum
for all polytopes.
F (w) provides a game theoretic interpretation of the entropy minimization problem.
In Section 5 we study the properties of function F (w) and utilize probabilistic tools to
give a number of easy-to-compute bounds on the value of F (w). While the literature
on game theory makes extensive use of total variation distance between distributions, we
use the χ2 –divergence (or the Tsallis divergence of order two) to derive a lower bound for
F (w). This lower bound is strictly tighter than the bound derived using the total variation
distance showing the applicability of χ2 –divergence in the context of game theory.
The rest of this paper is organized as follows: In Section 2 we introduce the notation
of this paper and present a brief discussion of Shannon entropy. In Section 3 we study a
version of our first model studied by Gossner and Vieille (2002) and simplify the proof.
The complete version of our first model namely the repeated game with leaked randomness source will be studied in Section 3.3. In Section 4 we study the problem of secret
correlation in repeated games with imperfect monitoring and simplify the proof of Gossner and Tomala (2007) and extend the results. Section 5 is devoted for the computational
aspects of the min-entropy function. Finally, in Section 6 we give the proofs. Some of the
details including a discussion on randomness extraction are left for the appendices.

8

2. Preliminaries
2.1. Notation
In this paper we use the notation xj to represent a sequence of variables (x1 , x2 , . . . , xj ).
The same notation is used to represent sequences of random variables, i.e., X j = (X1 , X2 , . . . , Xj ).
Note that this notation is used for sequences that have two subscripts the same way i.e.,
Xkj = (Xk,1 , Xk,2 , . . . , Xk,j ). Calligraphic letters such as X , Y, A, B, . . . represent finite
sets and |X | denotes the cardinality of finite set X . Real vectors are represented by bold
lower case letters and bold uppercase letters are used to represent random vectors. For
example the probability mass function (pmf) of a random variable X with finite sample
space X = {1, 2, . . . , n}, beside the representation pX (x), will be also denoted by a vector
p = (p1 , . . . , pn ). When it is obvious from the context we drop the subscript and use p(x)
instead of pX (x). We say that X n is drawn i.i.d. from p(x) if
n

p(x ) =

n
Y

p(xi ).

i=1

We use ∆(A) to denote the probability simplex on alphabet A, i.e., the set of all probability distributions on the finite set A. The total variation distance between pmfs pX and
qX is denoted by d1 (pX , qX ) or kpX − qX kT V and is defined as:
d1 (pX , qX ) = kpX − qX kT V ,

1X
|pX (x) − qX (x)|.
2 x∈X

When the pmfs are represented by vectors p and q the total variation distance between
them is represented by d1 (p, q) or kp−qkT V . Some of the properties of the total variation
distance are summarized in the following lemma.
Lemma 1. The following properties hold for the total variation distance:
Property 1: kpE pF |E − qE pF |E kT V = kpE − qE kT V ;
Property 2: kpE pF |E − qE qF |E kT V ≥ kpE − qE kT V ;
Property 3: kpE1 pF1 − pE2 qF2 kT V ≤ kpE1 − pE2 kT V + kpF1 − qF2 kT V ;
9

Property 4: For arbitrary deterministic function f on the sample space of E1 and E2
we have kpf (E1 ) − pf (E2 ) kT V ≤ kpE1 − pE2 kT V ;
Property 5: kpE1 pF − pE2 pF kT V = kpE1 − pE2 kT V .

2.2. Entropy function
Let X ∈ X and Y ∈ Y be two random variables with joint probability distribution
pX,Y and respective marginal distributions pX and pY . The Shannon entropy (or simply
the entropy) of the random variable X is defined to be:
H(X) =

X

−pX (x) log(pX (x))

x∈X

where 0 log(0) = 0 by continuity and all logarithms in this paper are in base two. Since
the entropy is a function of the pmf pX , we sometimes write H(pX ) (or H(p) when the
pmf is denoted by probability vector p) instead of H(X).
The conditional Shannon entropy (or simply the conditional entropy) of X given Y is
defined as:
H(X|Y ) =

X

−pXY (x, y) log(pX|Y (x|y))

(x,y)∈X ×Y

=

X

pY (y)H(X|Y = y),

y∈Y

where H(X|Y = y) =

P

x∈X

−pX|Y (x|y) log(pX|Y (x|y)).

Using the definition of entropy and conditional entropy one can check that
H(X, Y ) = H(Y ) + H(X|Y )
holds. Utilizing the above property iteratively, the chain rule for a sequence of random
variables is obtained:
n

H(X ) = H(X1 ) +

n
X

H(Xi |X i−1 ).

i=2

Furthermore, the following properties hold for the entropy function:
10

• H(X) ≥ 0.
• H(X1 , X2 ) ≥ H(X1 ).
• Let f (x) be arbitrary deterministic function then H(f (X)) ≤ H(X).
3. Repeated games with a bounded randomness source
In this section we revisit the repeated game studied in Gossner and Vieille (2002).
The high level picture of the proof of Gossner and Vieille (2002) is as follows: it uses
the so-called “block-Markov” proof technique of information theory, where we divide time
into a number of blocks; Alice uses its observation in each block to produce its actions
for the next block. Our goal is to show that the high level picture of the proof of Gossner
and Vieille (2002) can be made precise in an easier manner using standard information
theory tools.
3.1. Problem definition
Let us first begin with reviewing the definition of the repeated game with a bounded
randomness source studied in Gossner and Vieille (2002). Consider a T stage repeated
zero-sum game between players Alice(A) and Bob(B) with respective finite action sets
A = {1, . . . , n} and B = {1, . . . , n0 } where n and n0 are natural numbers. Let X T =
(X1 , X2 , . . . , XT ) be a sequence of random variables drawn i.i.d. from sample space X with
law pX . In every stage t ∈ {1, 2, . . . , T }, first Alice observes random source Xt privately
then Alice and Bob choose actions At ∈ A and Bt ∈ B respectively. At the end of stage
t both players observe the chosen actions At and Bt and Alice gets stage payoff uAt ,Bt
from Bob. In order to choose actions at stage t, players make use of the history of their
observations until stage t which is denoted by Ht1 = (X1 , A1 , B1 , . . . , Xt−1 , At−1 , Bt−1 , Xt )
for Alice and Ht2 = (A1 , B1 , . . . , At−1 , Bt−1 ) for Bob. Let σt : (A × B)t−1 × X t → A
and τt : (A × B)t−1 → B be the functions mapping the history of observations of Alice
and Bob to actions at stage t, thus At = σt (Ht1 ) and Bt = τt (Ht2 ). Note that Alice
does not have access to any private sources of randomness besides Ht1 thus she has to
11

use deterministic function σt (·) while Bob can utilize random function τt (·). We call the
T -tuples σ = (σ1 , σ2 , . . . , σT ) and τ = (τ1 , τ2 , . . . , τT ) the strategies of Alice and Bob
respectively. The expected average payoff for Alice up to stage T induced by strategies σ
and τ is denoted by λT (σ, τ ) which is:
"
λT (σ, τ ) = Eσ,τ

T
1X
uA ,B
T t=1 t t

#
(1)

where Eσ,τ denotes expectation with respect to the distribution induced by i.i.d. repetitions
of pX and strategies σ and τ . Alice (Bob) wishes to maximize (minimize) λT (σ, τ ).
Definition 2. Let v be arbitrary real value:
• Alice can secure v if there exists a strategy σ ∗ for Alice such that for all strategy τ
of Bob we have lim inf T →∞ λT (σ ∗ , τ ) ≥ v.
• Bob defends v if given an arbitrary strategy σ for Alice there exists a strategy τ ∗ for
Bob such that lim supT →∞ λT (σ, τ ∗ ) ≤ v.
• v is the maxmin value of the repeated game if Alice can secure v and Bob can defend
v.

Theorem 3 (Gossner and Vieille (2002)). The maxmin value of the repeated game with
bounded randomness source defined in Section 3.1 is Jcav (H(X)), where Jcav (h) is the
upper concave envelope of
J (h) =

max

min Ep [uA,b ],

p∈∆(A),H(p)≤h b∈B

(2)

where ∆(A) is the probability simplex on A and Ep denotes the expectation with respect
to p .
In Section 3.2 we give a simplified proof of Gossner and Vieille (2002) that justifies
Alice can secure Jcav (H(X)). The complete proof is left for Section 3.3 where we present
a generalized version of the above result.
12

3.2. Simplifying the proof of Gossner and Vieille (2002)
As mentioned in Gossner and Vieille (2002), the upper concave envelope Jcav (·) at
h = H(X) can be expressed as the convex combination
(1)

(2)

γJ(H(pA )) + (1 − γ)J(H(pA ))
(1)

(2)

(1)

for some γ ∈ [0, 1] and input distributions pA and pA on A that secure payoffs J (H(pA ))
(2)

and J (H(pA )) respectively in the one-shot game, and satisfy
(1)

(2)

γH(pA ) + (1 − γ)H(pA ) = H(X).
(1)

(2)

As a result, it suffices to show that for any pA and pA satisfying
(1)

(2)

γH(pA ) + (1 − γ)H(pA ) < H(X),
Alice can use the source of randomness X to secure payoffs arbitrarily close to
γ min Ep(1) [uA,b ] + (1 − γ) min Ep(2) [uA,b ],
b∈B

b∈B

A

A

(1)

(2)

which is the weighted average of the payoffs that input distributions pA and pA secure.
The game is played for T stages. Take some T of the form T = N L, and divide the
total T stages into N blocks of length L. Excluding the first block, we generate the action
sequence of each block as a function of the random source observed during the previous
block (we ignore the payoff of the first block throughout the discussion, since by taking
the number of blocks N large enough, the contribution of the first block in Alice’s net
average payoff becomes negligible). More specifically, excluding the first block, each block
is further divided into two subblocks, with the first subblock taking up γ fraction of the
block as in Fig. 1. Alice aims to use her observed random source during the previous
(1)

block to play almost i.i.d. according to pA during the first subblock, and almost i.i.d.
(2)

according to pA during the second subblock. In addition, Alice wants her action at any
given stage to be also (almost) independent of Bob’s previous observation history in that
stage. Observe that if Alice could produce actions that are perfectly i.i.d. according to
13

(1)

(2)

pA in the first subblock and perfectly i.i.d. according to pA in the second subblock, both
independent of Bob’s history, then in γ fraction of the games in a block, she secures the
average payoff of minb∈B Ep(1) [uA,b ] per action, and in the remaining 1 − γ fraction secures
A

the payoff of minb∈B Ep(2) [uA,b ]. This gives Alice a total payoff of
A

γ min Ep(1) [uA,b ] + (1 − γ) min Ep(2) [uA,b ],
b∈B

b∈B

A

A

and will complete the proof.
(1)

It remains to show that Alice can play almost i.i.d. according to pA during the first
(2)

subblock of each block, and almost i.i.d. according to pA during the second subblock of
(1)

(2)

each block. Remember that γH(pA ) + (1 − γ)H(pA ) < H(X). Intuitively speaking, since
Alice’s observation from a block has entropy LH(X), which is larger than the entropy of
(1)

(2)

her intended action in the next block LγH(pA ) + L(1 − γ)H(pA ), she should be able to
find a proper mapping to produce her actions in the current block from her observations
in the preceding block. Gossner and Vieille (2002) propose such a mapping and put effort
to prove its correctness. This is where most of the effort is spent. The essential problem
here is to simulate a source from another source (here the observations from one block to
actions in the next block). This problem is solved in the information theory literature.
As stated below in Lemma 6 which is adopted from (Han, 2003, p. 110), the measure of
relevance to compare between the two sources is inf-entropy and sup-entropy, rather than
entropy. However, for i.i.d. sources (or concatenation of i.i.d. sources), inf-entropy and
sup-entropy reduce to the normal Shannon entropy, as discussed in Remark 5 below.
Definition 4. Sup-entropy and inf-entropy of a random source Z1 , Z2 , . . . are denoted by
H(Z) and H(Z), respectively and defined as follows,
H(Z) = p- lim inf

1
1
,
log
L
pZ L (Z L )

H(Z) = p- lim sup

1
1
log
,
L
pZ L (Z L )

L→∞

L→∞

where for a random sequence {Wt },
n
o
p- lim inf Wt = sup β| lim Pr[Wt < β] = 0 ,
t→∞

t→∞

14

n
o
p- lim sup Wt = inf β| lim Pr[Wt > β] = 0 .
t→∞

t→∞

Remark 5. If Z L = (Z1 , Z2 , . . . , ZL ) is a concatenation of two sequence of i.i.d. random
variables on Z with distribution
dγLe
L

pZ L (z ) =

Y

L
Y

(1)

p (zi )

i=1

p(2) (zi ),

i=dγLe+1

where dae is the smallest integer greater than or equal to a, then we have


dγLe
L
X
X
1
1
1
1
1 
log (1)
lim log
= lim 
+
log (2)
L
L→∞ L
L→∞
pZ L (Z )
L i=1
p (Zi )
p (Zi )
i=dγLe+1

=γ

X

p(1) (z) log

z∈Z

1
p(1) (z)

+ (1 − γ)

X

p(2) (z) log

z∈Z

1

with probability 1

p(2) (z)

= γH(p(1) ) + (1 − γ)H(p(2) )

with probability 1,

where the first equality results from the independence of the random variables Z1 , Z2 , . . .
and the second equality follows from the weak law of large numbers.Thus
p- lim inf

1
1
log
= γH(p(1) ) + (1 − γ)H(p(2) ),
L
pZ L (Z L )

p- lim sup

1
1
log
= γH(p(1) ) + (1 − γ)H(p(2) ),
L
pZ L (Z L )

L→∞

L→∞

hence H(Z) = H(Z) = γH(p(1) ) + (1 − γ)H(p(2) ) = limL→∞ 1/LH(Z L ).
Lemma 6 (Simulation of a source from another source). For each natural number L, con(L)

sider an arbitrary distribution pX L on sequences (x1 , x2 , . . . , xL ) ∈ X L . Similarly, for each
(L)

natural number L, consider an arbitrary distribution qAL on sequences (a1 , a2 , . . . , aL ) ∈
AL . Then, if H(X) > H(A), for each natural number L, there exists a mapping ϕL :
X L → AL such that the total variation distance between the distributions of ϕL (X L ) and
AL vanishes asymptotically, i.e.,
(L)

(L)

lim kqAL − pϕL (X L ) kT V = 0.

L→∞

15

Remark 7. Observe that limL→∞ kpAL − pϕL (X L ) kT V = 0 in the above lemma implies
that ϕL (X L ) is almost statistically indistinguishable from pAL for large values of L. In
other words, there is no statistical test that can distinguish between pAL and pϕL (X L ) with
a non-negligible probability.
(1)

(2)

Take some  > 0. Since γH(pA )+(1−γ)H(pA ) < H(X), from Lemma 6 and Remark
5 there exist mappings ϕL : X L → AL such that for large L, the pmf of AL = ϕL (X L ) is
approximated (in total variation distance) as
dγLe
L

pAL (a ) −

Y

L
Y

(1)
pA (at )

t=1

(2)

≤ .

pA (at )

t=dγLe+1

(3)

TV

Therefore by dividing the T stages into N blocks of L stages, we construct a strategy σ
for Alice as follows: in each block (excluding the first block) Alice chooses action sequence
ALc = ϕL (XpL ) where XpL is the randomness source observed during the previous block;
i.e., ALc is for the current block but XpL is for the previous block.
QL
Q
(2)
(1)
The ideal distribution dγLe
t=dγLe+1 pA (at ) gives Alice a payoff of
t=1 pA (at )
dγLe min Ep(1) [uA,b ] + (L − dγLe) min Ep(2) [uA,b ].
b∈B

b∈B

A

A

Alice’s actual distribution is within  total variation distance of the ideal distribution. By
relating the total variation distance to the payoff differences, we obtain that difference
between the payoff under the actual distribution and the ideal one is at most  times 2LM
where M is the maximum absolute value entry of the game table (LM is the maximum
absolute value entry of the L repetitions of the game). Thus, the distance between the
average payoff of the block differs by at most 2M from the average payoff under the ideal
distribution. This completes the proof.
Remark 8. We constructed the strategy σ for the case T = N L. In general for T = N L+δ
where δ < L one can extend the first block to contain L + δ stages and choose N large
enough to diminish the effect of first block on average payoff.

16

3.3. Generalized model: leakage of the randomness source
We generalize the model of repeated game in Section 3 and define the repeated
game with leaked randomness source as follows: Let X T = (X1 , X2 , . . . , XT ) and Y T =
(Y1 , Y2 , . . . , YT ) be two sequences of random variables, such that (Xt , Yt ) for t ∈ {1, 2, . . . , T },
are drawn i.i.d. from a given pmf pXY . In every stage t ∈ {1, 2, . . . , T }, Alice and Bob
respectively observe random sources Xt and Yt privately, and choose actions At ∈ A and
Bt ∈ B. Thus the only difference of this model with the model of Section 3 is that in every
stage t Bob observes Yt which is related to the observation of Alice Xt , hence the history
of observations of Bob is Ht2 = (Y1 , A1 , B1 , . . . , Yt−1 , At−1 , Bt−1 , Yt ) and Bt = τt (Ht2 ) where
τt : (A × B)t−1 × Y t → B; on the other hand, the history of observations of Alice remains
unchanged. Note that Alice does not have access to any private sources of randomness
besides Ht1 thus she has to use deterministic function σt (·) while Bob can utilize random
function τt (·). Alice (Bob) wishes to maximize (minimize) the expected average payoff
λT (σ, τ ) which is defined in equation (1).
The above repeated zero-sum game between players Alice(A) and Bob(B) reduces to
the one considered in Section 3 if we set Yt to be constant random variables. The maxmin
value of the repeated game with leaked randomness source is defined as in Definition 2
and characterized as follows:
Theorem 9. The maxmin value of the repeated game with leaked randomness source
defined in Section 3.3 is Jcav (H(X|Y )), where Jcav (.) is defined as in Theorem 3.

Corollary 10. Consider the case in which besides the sequence X1 , X2 , . . . , Alice also
observes the sequence Y1 , Y2 , . . . , therefore Xt0 = (Xt , Yt ) is the observation of Alice at
stage t. Since H(X 0 |Y ) = H(X|Y ), the maxmin value of the game is still Jcav (H(X|Y ))
which is equal to the maxmin value of the game when Alice does not observe the sequence
Y1 , Y2 , . . . . Therefore, Alice’s access to Y1 , Y2 , . . . does not help her. This parallels the
classical result of Slepian and Wolf (1973) in information theory.

17

Example 11. (Matching pennies) Consider the matching pennies game with A = B =
{0, 1} and payoffs:
u0,0 = u1,1 = 1,

u0,1 = u1,0 = 0.

Assume that Alice observes (symbol by symbol) an i.i.d. sequence of binary random variables X1 , X2 , . . ., where
pXi (0) = q,

pXi (1) = 1 − q.

Each Xi is revealed to Bob with probability α ∈ [0, 1]. Thus, Bob observes (symbol by
symbol) a sequence Y1 , Y2 , . . . such that with probability α, Yi = Xi and with probability
1 − α, Yi = null.
Roughly speaking α fraction of the bits of Alice are revealed to Bob. If Alice is made
aware of which of its bits are compromised and leaked to Bob, she can drop the compromised bits and keep the 1 − α fraction of the secret bits. In this way, she can distill
an average of (1 − α)H(q) random bits per observation. It is known from Gossner and
Vieille (2002) that for the matching pennies game Jcav (h) = h/2. Thus, using (1−α)H(q)
bits randomness per stage, Alice can secure a payoff (1 − α)H(q)/2. The above theorem
says that Alice can secure the same payoff even without knowing which of its bits are
compromised.
The proof uses a known fact in information theory that H(X|Y ) is the amount of
random bits extracted from source X1 , X2 , . . . that are almost independent of the observations of Bob (Y1 , Y2 , . . . ). As in Section 3.2, the optimal strategy for Alice utilizes the
random sources to extract randomness and use them to randomize her actions. To prove
Theorem 9, in Section 3.3.1 we show that Alice can secure Jcav (H(X|Y )) and in Section
3.3.2 we show that Bob can defend Jcav (H(X|Y )). Therefore, by definition Jcav (H(X|Y ))
is the maxmin value of the repeated game.
3.3.1. Alice can secure Jcav (H(X|Y ))
To show that Alice can secure any payoff less than Jcav (H(X|Y )), we extend and
simplify the proof of Gossner and Vieille (2002). As before, the upper concave envelope
18

1 2

...

L 1

1

. . . dγLe

...

L

1

. . . dγLe

2

...

L

...

3

...

1

. . . dγLe

...

L

N

Time slots of the first block in which Alice plays pure action 1 ∈ A
(1)

Time slots in which Alice draws random action with law pA

(2)

Time slots in which Alice draws random action with law pA

Figure 1: Illustration of block Markov strategy

Jcav (·) at h = H(X|Y ) can be expressed as the convex combination
(1)

(2)

γJ(H(pA )) + (1 − γ)J(H(pA ))
(1)

(2)

(1)

for some γ ∈ [0, 1] and input distributions pA and pA on A that secure payoffs J (H(pA ))
(2)

and J (H(pA )) respectively in the one-shot game, and satisfy
(2)

(1)

γH(pA ) + (1 − γ)H(pA ) = H(X|Y ).
(1)

(2)

As a result, it suffices to show that for any pA and pA satisfying
(1)

(2)

γH(pA ) + (1 − γ)H(pA ) < H(X|Y ),
Alice can secure payoffs arbitrarily close to
γ min Ep(1) [uA,b ] + (1 − γ) min Ep(2) [uA,b ].
b∈B

b∈B

A

A

Again, the idea is to utilize the block-Markov proof technique. Take some T of the
form T = N L, and divide the total T stages into N blocks of length L. Each block is
divided into two subblocks as before. Excluding the first block, Alice wants to play almost
(1)

(2)

i.i.d. according to pA during the first subblock, and almost i.i.d. according to pA during
the second subblock.
By symmetry, we only need to consider the payoff that Alice gets in one of the blocks.
For notational simplicity, we denote the observations of Alice and Bob in the previous
block by XpL and YpL respectively, and use ALc and BcL to denote their actions in the
19

current block. Instead of Lemma 6 in the previous section, the proof relies on the following
proposition whose proof is given in Section 6.1:
(1)

(2)

Proposition 12. Let 0 ≤ γ ≤ 1 be an arbitrary real number and pA and pA be arbitrary
(1)

(2)

distributions on A such that γH(pA ) + (1 − γ)H(pA ) < H(X|Y ). Then, for any  > 0,
there exists a natural number L̃ and mappings ψL : X L → AL such that for all L ≥ L̃
dγLe

pALc ,YpL (aLc , ypL )

−

pYpL (ypL )

Y

L
Y

(1)

pA (ac,t )

t=1

(2)

pA (ac,t )

t=dγLe+1

< ,

(4)

TV

where (XpL , YpL ) are i.i.d. according to pXY (xp , yp ) and ALc = ψL (XpL ).
Note that pYpL (ypL )

QdγLe
t=1

(1)

pA (ac,t )

(2)

QL

t=dγLe+1

pA (ac,t ) is the ideal independent actions

by Alice, whereas pALc ,YpL (aLc , ypL ) is the real joint distribution.
Let Alice use the actions ALc = (Ac,1 , Ac,2 , . . . , Ac,L ) in the current block where ALc =
ψL (XpL ). Because the X-source is i.i.d., the X-source for different blocks are independent,
and random variable ALc (a function of XpL ) is independent of Alice’s action in all the previous blocks. As a result, even though Bob has access to the entire past history of the game
and his Y -source observations, he obtains information about XpL only through his source
YpL and Alice’s prior actions in the current block. In other words, Bob’s action at the t-th
t−1
stage of the current block Bc,t is conditionally independent of XpL given YpL , At−1
c , Bc .

Since ALc = ψL (XpL ), Bc,t is also conditionally independent of Ac,t+1 , Ac,t+2 , · · · , Ac,L given
t−1
YpL , At−1
c , Bc . Thus,

p(bLc |ypL , aLc ) =

L
Y

t−1
p(bc,t |ypL , at−1
c , bc ).

t=1

Then, utilizing the first property of total variation in Lemma 1 for random variables
E = (ALc , YpL ) and F = BcL we conclude from (4) that
pALc ,YpL (aLc , ypL )

L
Y

t−1
p(bc,t |ypL , at−1
c , bc )

(5)

t=1
dγLe

−

pYpL (ypL )

Y
t=1

L
Y

(1)
t−1
pA (ac,t )p(bc,t |ypL , at−1
c , bc )

t=dγLe+1

20

(2)

t−1
pA (ac,t )p(bc,t |ypL , at−1
c , bc )

< .
TV

Utilizing the second property of total variation in Lemma 1 for random variables E =
(ALc , BcL ) and F = YpL we conclude that the distance between the actual actions pALc ,BcL (aLc , bLc )
and the ideal one is less than or equal to , i.e.,
dγLe

pALc ,BcL (aLc , bLc )

−

Y

(1)
t−1
pA (ac,t )p(bc,t |at−1
c , bc )

t=1

L
Y

(2)

t−1
pA (ac,t )p(bc,t |at−1
c , bc )

t=dγLe+1

< .
TV

(6)
As before, by relating the total variation distance to the payoff differences, we obtain
that the average payoff differs by at most 2M from the average payoff under the ideal
distribution. This completes the proof.
3.3.2. Bob can defend Jcav (H(X|Y ))
This is an extension of the proof given in Neyman and Okada (2000); Gossner and
Vieille (2002). Let σ be an arbitrary strategy for Alice and generate strategy τ for Bob
as follows: given ht2 , an arbitrary history of observations of Bob until stage t, τt (ht2 ) is the
best choice of Bob that minimizes the expected payoff at stage t, i.e.


τt (ht2 ) ∈ arg minEσ uAt ,j |Ht2 = ht2
j∈B

where Eσ denotes expectation with respect to the probability distribution induced by σ
and pX,Y . Thus,




Eσ,τ uAt ,Bt |Ht2 = ht2 ≤ J H(At |Ht2 = ht2 ) ≤ Jcav H(At |Ht2 = ht2 ) ,

(7)

since conditional on the observations ht2 of Bob, Alice’s action At has entropy H(At |Ht2 =
ht2 ). Therefore,
Eσ,τ [uAt ,Bt ] =

X





Pr Ht2 = ht2 Eσ,τ uAt ,Bt |Ht2 = ht2

ht2 ∈(A×B)t−1 ×X2t

≤

X




Pr Ht2 = ht2 Jcav H(At |Ht2 = ht2 )

ht2 ∈(A×B)t−1 ×X2t


≤ Jcav 


 t

Pr H2 = ht2 H(At |Ht2 = ht2 )

X
ht2 ∈(A×B)t−1 ×X2t


= Jcav H(At |Ht2 ) .

(8)
21

The first inequality results from (7) and by using Jensen’s inequality for concave function
Jcav (·) the second inequality follows. By definition of λT (σ, τ ) and using (8) we have
T
X

1
λT (σ, τ ) ≤
Jcav H(At |Ht2 )
T
t=1
!
T
X
1
t
≤ Jcav
H(At |H2 )
T
t=1

!
T
X
1
= Jcav
H(At |Y t , At−1 , B t−1 )
T
t=1
!
T
X
1
= Jcav
H(At |Y T , At−1 )
T

 t=1
1
T
T
H(A |Y )
= Jcav
T


1
T
T
≤ Jcav
H(X |Y )
T
= Jcav (H(X|Y ))

(9)

where the second inequality follows by using Jensen’s inequality for concave function Jcav .
Note that given the strategy τ for Bob, B t−1 is a deterministic function of Y t and At−1
thus H(At |Y t , At−1 , B t−1 ) = H(At |Y t , At−1 ) and as At and Bt are causally generated from
i.i.d. sequences X T and Y T hence (At , At−1 , Y t ) is independent of (Yt+1 , Yt+2 , . . . , YT ) and
H(At |Y t , At−1 ) = H(At |Y T , At−1 ) follows. Therefore the second equality is correct. To
prove the final equality consider that given strategies of the players and the sequence Y T ,
AT is a deterministic function of X T thus H(X T |Y T ) ≥ H(AT |Y T ) and as Jcav (·) is an
increasing function, the final equality holds.
Thus for all strategy σ of Alice there exists a strategy τ such that lim supT →∞ λT (σ, τ ) ≤
Jcav (H(X|Y )). Hence Bob can defend Jcav (H(X|Y )).
4. Secret correlation in repeated games with imperfect monitoring
In this section we revisit and extend the repeated game with imperfect monitoring
studied by Gossner and Tomala (2007). The main contribution of this part is to simplify
22

the construction of the optimal strategy and generalize the result of Gossner and Tomala
(2007).
4.1. Problem definition
Consider a T stage repeated zero-sum game between team A and player B. Team A
consists of m players {1, 2, . . . , m} with respective finite actions sets A1 , A2 , . . . , Am . Let
A = A1 × A2 × · · · × Am and B denote the finite pure actions sets of team A and player B,
respectively. In every stage t ∈ {1, 2, . . . , T }, each player in team A and player B choose
an action from their corresponding actions sets. Let At denote the action profile of team
A and Bt denote the action of player B at stage t. At the end of stage t, team A gets
payoff uAt ,Bt from player B and all players of team A observe the chosen actions At and
Bt but player B observes Bt and St ∈ S where St is a noisy version of At with conditional
distribution Pr[St = st |At = at ] = pS|A (st |at ). In order to choose the actions at stage
t, players make use of the history of their observations until stage t which is denoted by
Ht1 = (At−1 , B t−1 ) for players of team A and Ht2 = (B t−1 , S t−1 ) for player B. Let σi,t :
(A × B)t−1 → Ai and τt : (B × S)t−1 → B be the random functions mapping the history
of observations of arbitrary player i in team A and player B to their actions at stage t,
thus At = (σ1,t (Ht1 ), σ2,t (Ht1 ), . . . , σm,t (Ht1 )) and Bt = τt (Ht2 ). Let σt = (σ1,t , σ2,t , . . . , σm,t ).
Then we call the T -tuples σ = (σ1 , σ2 , . . . , σT ) and τ = (τ1 , τ2 , . . . , τT ) the strategies of
team A and player B respectively. The expected average payoff for team A, λT (σ, τ ), and
the maxmin value of the game are defined in a similar way as in Section 3.1.
Remark 13. In the definition of the repeated game with imperfect monitoring, Gossner
and Tomala (2007) assume that the signals St are also observed by the players of team A
but we assume that the signals St are not observed by the players of team A. We generalize
the result of Gossner and Tomala (2007) by showing that the maxmin value of the game
remains the same with this change in assumption.
Definition 14. Let Π ⊂ ∆(A) denote the set of independent probability distributions on
the sets of actions of players in team A. Given dependent random variables R ∈ R and
23

A ∈ A, let π(A) (the security level of A) and π(A|R) (the security level of A given R)
are defined as follows

π(A) = min E[uA,b ],
b∈B

π(A|R) = ER


min EA|R [uA,b |R] .
b∈B

Theorem 15. The maxmin value of the repeated game with imperfect monitoring is
w = max π(A|R),
where the maximization is over all random variables A ∈ A, S ∈ S, R ∈ {0, 1} and
Q ∈ Q = {1, 2, 3, · · · , |A|}, satisfying
pS,A,R,Q (s, a, r, q) = pRQ (r, q)pA|Q (a|q)pS|A (s|a),
pA|Q (a|q) ∈ Π,

(10)
(11)

H(QA|SR) ≥ H(Q|R).

(12)

Remark 16. The statement of the above theorem has a different (but equivalent form)
than the one given in Gossner and Tomala (2007). In particular, Gossner and Tomala
(2007) expresses the solution as an optimization problem over the set of “distributions of
distributions”. Because all the variables in our characterization have finite alphabet sets,
the above form is computable and is expressed as a maximization problem over a compact
and bounded set of probability distribution.
In Section 4.2 we show that team A can secure w = max π(A|R) and in Section 4.3 we
show that player B can defend w even when players of team A, in addition to At and Bt
observe the signals St at the end of stage t. Thus, w is the maxmin value of the repeated
game with imperfect monitoring regardless of whether team A observe St or not.
4.2. Payoff secured by the team A
We show that team A can secure payoff w = max π(A|R) if pRQAS satisfies (12) with
strict inequality, i.e.,
H(QA|RS) > H(Q|R).
24

(13)

One can obtain the boundary case H(QA|RS) = H(Q|R) since π(A|R) is a continuous
function of pRQAS and the set of distributions pRQAS satisfying (10) and (11) is bounded.
Since
π(A|R) = pR (0) min E[uA,b |R = 0] + pR (1) min E[uA,b |R = 1],
b∈B

b∈B

it suffices to show that players of team A can choose their actions almost i.i.d. according
to pA|R (a|0) in γ = pR (0) portion of stages and almost i.i.d according to pA|R (a|1) in
1 − γ = pR (1) portion of stages, while the action of each stage is almost independent of
the history of observations of player B until that stage.
In the rest of the proof the ideal joint distribution pRQAS is assumed to be given and
fixed. Random variable A should be not be confused with A1 or AT = (A1 , A2 , · · · , AT )
which denote the distribution of the action of players of team A at the first stage and the
T time instances respectively.
The block-Markov technique: As in the previous section, team A utilizes the
block-Markov proof technique. We assume that the game is played over one block of
length kL (the first block) followed by N blocks of length L. Therefore, the total number
of repetitions of the game is T = kL + N L. The first block is of length kL which will
be specified later; this block is sufficiently long block to provide enough randomness to
initialize the block-Markov strategy for the N blocks of length L. Excluding the first
block, each block is divided into two subblocks of length dγLe and L − dγLe. Team A
aims to play almost i.i.d. according to pA|R (a|0) in the first subblock and according to
pA|R (a|1) in the second subblock, while the action of each stage is almost independent of
the history of observations of player B until that stage. To do so, in each block the players
of team A extract a sequence of shared randomness independent of the observations of
player B to correlate their actions in the next block. For arbitrary block i ≥ 3 (the current
block) let QLc ∈ QL denote the sequence of shared randomness extracted in previous block
and ALc denote the sequence of actions of team A played in the current block. Players of
team A produce their actions in the current block ALc only from the shared randomness
QLc , and their private randomness in the manner that is described in details below. With
25

team A playing Ac,t in the t-th stage of the current block, player B gets the signal Sc,t
constructed from Ac,t with the conditional distribution pS|A .
For simplicity of the notation, the sequence of shared randomness, actions of team A,
actions of player B and the signals observed by player B are denoted by QLc , ALc , BcL , ScL
for the current block (i-th block), QLp , ALp , BpL , SpL for the previous block ((i − 1)-th block)
when i ≥ 3. The actions of team A, actions of player B and the signals observed by
player B in the second block are denoted by QLs , ALs , BsL , SsL . For the first block we use
kL
kL
AkL
f , Bf and Sf to denote these random variables.

First block: In the first block players of team A start off without any shared ran(0)

domness. They choose their actions independently and i.i.d. according to some pA ∈ Π
(0)

satisfying H(A(0) |S (0) ) > 0 . Since pA ∈ Π and the players of team A have access to
private randomness, they can implement it distributively. Thus,
kL kL
pAkL
kL (af , sf )
f ,Sf

=

kL
Y

(0)

pA (af,t )pS|A (sf,t |af,t ).

t=1

The length of the first block is kL where L will be specified later; here k is a natural
number satisfying
k>

H(Q|R)
.
H(A(0) |S (0) )

(14)

Second block: Equation (14) implies that kH(A(0) |S (0) ) > H(Q|R). Then according
to Proposition 12 for arbitrary  > 0, there exist mappings ϕL : AkL → QL such that if
we take QLs = ϕL (AkL
f ) then for sufficiently large L we have:
dγLe

pQLs ,SfkL (qsL , skL
f )

−

pSfkL (skL
f )

Y

pQ|R (qs,t |0)

t=1

L
Y
t=dγLe+1

pQ|R (qs,t |1)

≤ .

(15)

TV

This implies that each of the players of team A can extract shared randomness QLs which is
almost independent of the observation of player B in the first block. Let H2,s = (SfkL , Bfkl )
denote the history of observations of player B before starting the second block. Since
BfkL is produced locally by player B from SfkL , random variable BfkL is conditionally
independent of QLs given SfkL . Thus using the first property of total variation in Lemma 1
26

for random variables E = (SfkL , QLs ) and F = BfL we have
dγLe

pQLs ,H2,s (qsL , h2,s )

− pH2,s (h2,s )

Y

L
Y

pQ|R (qs,t |0)

t=1

pQ|R (qs,t |1)

t=dγLe+1

≤ .

(16)

TV

In the second block, the players of team A (all of whom know QLs ) choose As,t with
distribution pAs,t |Qs,t = pA|Q from A, that is
pALs |QLs ,H2,s (aLs |qsL , h2,s )

L
Y

=

pA|Q (as,t |qs,t ).

t=1

Because pA|Q ∈ Π, actions of players of team A are mutually independent given QLs and
they can realize it using private randomness. Then player B gets signal Ss,t constructed
from As,t with the conditional distribution pS|A , i.e.,
pSsL |ALs ,QLs ,H2,s (sLs |aLs , qsL , h2,s )

=

L
Y

pS|A (ss,t |as,t ).

t=1

In the i-th block for i ≥ 3: Let QLp , ALp , BpL , SpL be the variables of the previous
block, i.e., the (i − 1)-th block. Note that QLp , ALp is available to all players of team A.
The idea is to construct the current block’s shared randomness QLc from QLp , ALp of the
previous block. To do this, we need to find a suitable mapping ψL : QL × AL → QL
and set QLc = ψL (QLp , ALp ). Once the shared randomness QLc is constructed in the current
block, players of team A construct their actions in the current block solely based on QLc
using the conditional distribution pAc,t |Qc,t = pA|Q as follows:
pALc |QLc (aLc |qcL )

=

L
Y

pA|Q (ac,t |qc,t ).

t=1

In other words, while players of team A observe the entire past history of the actions,
their actions in stage t of the current block depends only on Qc,t . As before, because
pA|Q ∈ Π, distributed implementation of this conditional distribution is feasible with the
private randomness of the team A players.

27

Considering (16) as the basis step of induction, suppose that in the previous block
((i − 1)-th block) we have
dγLe

pQLp ,H2,p (qpL , h2,p )

− pH2,p (h2,p )

Y

L
Y

pQ|R (qp,t |0)

t=1

≤ 3(i−3) ,

pQ|R (qp,t |1)

t=dγLe+1

(17)

TV

where H2,p is the observations of player B before starting the previous block. Our first
goal is to identify an appropriate mapping ψL : QL × AL → QL to construct the shared
randomness of current block QLc such that
dγLe

pQLc ,H2,c (qcL , h2,c )

− pH2,c (h2,c )

Y

L
Y

pQ|R (qc,t |0)

t=1

t=dγLe+1

≤ 3(i−2) ,

pQ|R (qc,t |1)

(18)

TV

holds where H2,c = (H2,p , SpL , BpL ) is the observations of player B before starting the current
block.
Random variables ALp and SpL are produced in the previous block as follows:
pALp ,SpL |QLp (aLp , sLp |qpL ) =

L
Y

pA|Q (ap,t |qp,t )pS|A (sp,t |ap,t ).

t=1

From the first property of total variation in Lemma 1 for E = (QLp , H2,p ) and F = (ALp , SpL )
along with Equation (17) we obtain
pQLp ,ALp ,SpL ,H2,p (qpL , aLp , sLp , h2,p ) − pH2,p (h2,p )×
dγLe

Y
t=1

pQAS|R (qp,t , ap,t , sp,t |0)

L
Y

≤ 3(i−3) .

pQAS|R (qp,t , ap,t , sp,t |1)

t=dγLe+1

TV

(19)
We use the following proposition which is a generalization of Proposition 12.
Proposition 17. Let (U, X, Y ) ∈ {0, 1} × X × Y and (V, Z) ∈ {0, 1} × Z be arbitrary
random variables with respective distributions pU XY and pV Z with finite supports such that
H(X|Y U ) > H(Z|V ).
28

We also define random variables (X1 , · · · , XL , Y1 , · · · , YL , W ) with the joint distribution
pX L Y L W such that
dpU (0)Le
L

L

pX L Y L W (x , y , w) − pW (w)

Y

L
Y

pXY |U (xt , yt |0)

t=1

pXY |U (xt , yt |1)

t=dpU (0)Le+1

≤ δ1 .
TV

Then, for arbitrary δ2 > 0 there exist a natural number L̄ such that if L ≥ L̄, there is a
mapping ψL : X L → Z L such that Z L = ψL (X L ) satisfies
dpV (0)Le
L

L

L

pZ L ,Y L ,W (z , y , w) − pW (w)pY L (y )

Y

L
Y

pZ|V (zt |0)

t=1

pZ|V (zt |1)

t=dpV (0)Le+1

≤ 2δ1 +δ2 .
TV

Proof. Proof of Proposition 17 is provided in Section 6.2.
We use Proposition 17 with the choice of X = (Q, A), Y = S, U = R, V = Q, Z = R,
X L = (QLp , ALp ), Y L = SpL , Z L = QLc and W = H2,p . The assumptions of Proposition 17
are satisfied by Equations (13) and (19). Then, we obtain that for sufficiently large L,
there exist a mapping ψL : QL × AL → QL such that for QLc = ψL (QLp , ALp ) we have
dγLe

pQLc ,SpL ,H2,p (qcL , sLp , h2,p )

−

pSpL (sLp )pH2,p (h2,p )

Y

L
Y

pQ|R (qc,t |0)

t=1

pQ|R (qc,t |1)

t=dγLe+1

TV

≤ 2 × 3(i−3)  +  ≤ 3(i−2) .

(20)

Let H2,c = (H2,p , SpL , BpL ) denote the observations of player B before starting the current block. Since BpL is conditionally independent of QLc given (H2,p , SpL ), using the first
property of total variation in Lemma 1 for E = (QLc , SpL , Ht,p ) and F = BpL we have
dγLe

pQLc ,H2,c (qcL , h2,c )

− pH2,c (h2,c )

Y

pQ|R (qc,t |0)

t=1

L
Y

≤ 3(i−2) .

pQ|R (qc,t |1)

t=dγLe+1

(21)

TV

Therefore by induction Equation (21) holds for arbitrary i ≥ 3.
Calculation of the payoff of the i-th block for i ≥ 2: Actions of team A and the
signals ScL were produced according to
pALc ,ScL |H2,c ,QLc (aLc |h2,c , qcL )

=

L
Y
t=1

29

pA|Q (ac,t |qc,t )pS|A (sc,t |ac,t ).

Player B constructs its action Bc,t from the observations available to him at stage t of
the current block, that is
pBcL |H2,c ,QLc ,ALc ,ScL (bLc |h2,c , qcL , aLc , sLc ) =

L
Y

t−1
pBc,t |H2,c ,Sct−1 ,Bct−1 (bc,t |h2,c , st−1
c , bc ).

t=1

Therefore using the first property of total variation in Lemma 1 for random variables
E = (H2,c , QLc ) and F = (ALc , BcL , ScL ) in Equation (21), we obtain
pQLc ,ALc ,ScL ,H2,c ,BcL (qcL , aLc , sLc , h2,c , bLc ) − pH2,c (h2,c )×
dγLe

Y

t−1
pQ|R (qc,t |0)pA|Q (ac,t |qc,t )pS|A (sc,t |ac,t )pBc,t |H2,c ,Sct−1 ,Bct−1 (bc,t |h2,c , st−1
c , bc )×

t=1
L
Y

t−1
pQ|R (qc,t |1)pA|Q (ac,t |qc,t )pS|A (sc,t |ac,t )pBc,t |H2,c ,Sct−1 ,Bct−1 (bc,t |h2,c , st−1
c , bc )

t=dγLe+1

TV

≤ 3(i−2) .
Then by using the second property of total variation in Lemma 1 for random variables
E = (ALc , BcL ) and F = (QLc , H2,c , ScL ) and considering that i − 2 ≤ N we have
dγLe

pALc ,BcL (aLc , bLc )

−

Y

t−1 t−1
pA|R (ac,t |0)pBc,t |At−1
,Bct−1 (bc,t |ac , bc )×
c

t=1
L
Y

t−1 t−1
pA|R (ac,t |1)pBc,t |At−1
,Bct−1 (bc,t |ac , bc )
c

t=dγLe+1

≤ 3N .

(22)

TV

Note that by repeating the above arguments, (18) concludes that the inequality (22)
holds for the second block as well i.e., substituting the subscripts ‘c‘ with ‘s‘, the inequality
(22) still holds. By relating total variation distance to payoff, Equation (22) results that
the payoff of team A at second and current block (in the i-th block for any i ≥ 2) is
at most in 2M3N  distance of the payoff of team A when they played i.i.d. according to
pA|R (a|0) in γ portion of stages and i.i.d. according to pA|R (a|1) in remaining 1−γ portion
of stages, where M is the maximum absolute value of the payoff table. Thus it suffices
to take N large enough so that the effect of the first block in the average payoff of total
30

stages is diminished, and then take  small enough (consequently take L large enough
such that Equations (15) and (20) are satisfied) to make 2M3N  as small as desired.
Remark 18. We have shown that fixing some k and N , for any large enough L, we can
achieve the desired payoff in T = L(k + N ) stages. If T is not divisible by k + N , we can
make the first block slightly longer but because k + N  T for large enough T , this has
negligible effect on the achieved payoff.
4.3. Player B can defend w
Since we have given the solution expression in a different form than the one given by
Gossner and Tomala (2007), we adapt the proof of Gossner and Tomala (2007) to our
solution form.
In this subsection we assume that at the end of each stage t, the players of team
A in addition to At and Bt observe the signal St . We show that even with the more
information available to players of team A, player B can still defend w. Let σ be an
arbitrary strategy for team A. We generate strategy τ for player B as follows: given ht2 ,
an arbitrary history of observations of player B until stage t, τt (ht2 ) is the best choice of
player B that minimizes the expected payoff at stage t i.e.


τt (ht2 ) ∈ arg minEσ uAt ,b |Ht2 = ht2
b∈B

where Eσ denotes the expectation with respect to the probability distribution induced by
σ. Let team A and player B play with respective strategies σ and τ and let AT , B T and
S T denote the sequence of actions and signals generated during the T stages of the game.
Define:
R = (I, B I−1 , S I−1 ),

Q = (I, AI−1 , B I−1 , S I−1 ),

Ã = AI

and S̃ = SI ,

where I is a uniformly distributed random variable on I = {1, 2, . . . , T } and independent
of (AT , B T , S T ). Random variable I is the so-called time sharing random variable. Note
that R is a function of Q. Therefore,
pS̃,Ã,R,Q (s, a, r, q) = pRQ (r, q)pÃ|Q (a|q)pS|A (s|a).
31

Since the action profile At is implemented distributively by conditioning on (At−1 , B t−1 , S t−1 ),
the conditional distribution pÃ|Q (a|q) ∈ Π. Next we need to show that H(QÃ|S̃R) ≥
H(Q|R). Note that
H(QÃ|S̃R) − H(Q|R) = H(ÃS̃|QR) − H(S̃|R).

(23)

The inequality H(ÃS̃|QR) − H(S̃|R) ≥ 0 follows from
H(ÃS̃|QR)−H(S̃|R) = H(AI SI |I, AI−1 , B I−1 , S I−1 ) − H(SI |I, B I−1 , S I−1 )
T
X

1
H(At , St |At−1 , B t−1 , S t−1 ) − H(St |B t−1 , S t−1 )
=
n
t=1

(24)

T
X

1
=
H(At |B t , S t ) − H(At−1 |B t−1 , S t−1 )
T
t=1

(25)

=

1
H(AT |B T , S T ) ≥ 0,
T

where (24) follows from the fact that I is uniform and independent of (AT , B T , S T ) and
(25) follows from
H(At |B t , S t ) − H(At−1 |B t−1 , S t−1 )
= H(At−1 |B t , S t ) + H(At |B t , S t , At−1 ) − H(At−1 |B t−1 , S t−1 )
= H(At−1 , Bt , St |B t−1 , S t−1 ) − H(Bt , St |B t−1 , S t−1 ) + H(At , Bt , St |At−1 , B t−1 , S t−1 )
− H(Bt , St |At−1 , B t−1 , S t−1 ) − H(At−1 |B t−1 , S t−1 )
= H(At , Bt , St |At−1 , B t−1 , S t−1 ) − H(Bt , St |B t−1 , S t−1 )
= H(At , St |At−1 , B t−1 , S t−1 ) − H(St |B t−1 , S t−1 ) + H(Bt |At , B t−1 , S t ) − H(Bt |B t−1 , S t )
= H(At , St |At−1 , B t−1 , S t−1 ) − H(St |B t−1 , S t−1 ),

(26)

where (26) holds because the random variable Bt is conditionally independent of (At , St )
given (B t−1 , S t−1 ).

32

Now we relate the payoff of σ and τ to R and Ã :
T
X


1 X
λT (σ, τ ) =
pB t−1 ,S t−1 (bt−1 , st−1 ) max E uAt ,b |B t−1 = bt−1 , S t−1 = st−1
b∈B
T t−1 t−1
t=1
b
,s
X


(27)
=
pR (r) max E uÃ,b |R = q = π(Ã|R).
r

b∈B

We have identified random variables (R, Q, Ã, S̃) satisfying the constraint of the problem,
except for the cardinality bounds on R and Q. Cardinality of R and Q can be reduced
using the standard arguments such as the support lemma adopted from (El Gamal and
Kim, 2011, Appendix C), or the Fenchel-Bunt extension to the Caratheodory’s theorem.
Because the argument is standard, we briefly sketch it here: to reduce the cardinality of R,
we fix pQÃS̃|R and vary pR to maximize π(A|R) (linear in pR ), while H(QA|SR)−H(Q|R)
(linear in pR ) is preserved. To reduce the cardinality of Q, we proceed as follows: given
any value of R = r for r ∈ {0, 1}, we reduce the cardinality of Q such that H(ÃS̃|Q, R =
r) − H(S̃|R = r) and π(A|R = r) are preserved. To do this, we fix pÃS̃|Q,R=r and vary
pQ|R=r to maximize H(ÃS̃|Q, R = r) (linear in pQ|R=r ), while the marginal distribution
of pÃS̃|R=r is preserved. Preserving the marginal distribution of pÃS̃|R=r ensures that the
terms H(S̃|R = r) and π(A|R = r) are preserved.
5. Computation of min-entropy function
Consider a one shot zero sum game between players Alice (maximizer) and Bob (minimizer) and let J (h) be the maximum expected payoff that Alice can secure (regardless
of what Bob plays) with playing mixed actions of entropy at most h (as defined in Equation (2)). As stated in Theorems 3 and 9, J (h) characterizes the maxmin values of the
repeated game with bounded entropy (Section 3) and the repeated game with leaked
randomness (Section 3.3). The main goal of this section is to study the computational
aspects of J (h).
Let F (w) denote the inverse function of J (h). F (w) is the minimum entropy Alice
needs to secure payoff w, thus we call it the min-entropy function. To compute F (w),
33

one has to minimize the concave function of entropy over the polytope of mixed actions
that secure payoff w for Alice. The problem of entropy minimization over a polytope is
a standard problem and is known to be NP-hard(see Kovacevic et al. (2012)). Thus the
computation of F (w) (or J (h)) is NP-hard. In this section we study J (h) thorough its
inverse, F (w), and provide some computationally efficient upper and lower bounds for it.

5.1. Problem statement
Consider a zero-sum game between players Alice (A) and Bob (B) with respective
pure strategies sets A = {1, . . . , n} and B = {1, . . . , n0 } where n and n0 are natural
numbers. The payoff matrix is denoted by U = [uij ] where uij is the real valued payoff
that player A gets from player B when i ∈ A and j ∈ B are played. Player A (B) wishes to
maximize (minimize) the expected payoff. The set of all randomized strategies of players
A and B are denoted by ∆(A) and ∆(B) respectively which are probability simplexes
on sample spaces A and B respectively. Thus, Alice’s strategy corresponds to a pmf
p = (p1 , p2 , . . . , pn ), which can be also illustrated as a column vector with non-negative
entries that add up to one.
Assume that player A uses randomized strategy p. Then the payoff of Alice if Bob
P
plays j ∈ B is i pi uij . We say that Alice secures payoff w with randomized strategy p
P
(regardless of the action of player B) if i pi uij ≥ w for all j ∈ B. Thus, the set of all
distributions that guarantee payoff w for player A can be expressed as
PU (w) = {p ∈ ∆(A) : pT U ≥ w1T },

(28)

where pT is the transpose of the column vector p, 1 is a column vector of all ones and
v1 ≥ v2 means any element of v1 is greater than or equal to the corresponding element
at v2 .
We define
FU (w) , min H(p).
p∈PU (w)

If the set PU (w) is empty, we set FU (w) = +∞.
34

(29)

A remark on notation: Two-player zero-sum games are completely characterized
by payoff matrix. For the sake of simplicity, we call two-player zero-sum games with their
payoff matrix. Thus, game U refers to a game with payoff table U.
Definition 19. Given a game U = [uij ], parameters m, m, v and w∗ are defined as:
• m (m) is the minimum (maximum) element of matrix U : m = mini,j uij (m =
maxi,j uij ).
• v is the maximum payoff secured by pure actions ( pure-strategy security level):
v = maxi minj uij .
• w∗ is the value of the game U, which is the maximum guaranteed payoff with unlimited
access to random sources:
w∗ =

max

w.

w: PU (w)6=∅

(30)

Note that by definition, m ≤ v ≤ w∗ ≤ m.
According to Definition 19, v is the payoff that is guaranteed without consumption of
any randomness whereas w∗ is the maximum guaranteed payoff when unlimited randomness is available. Thus, it is interesting to consider the min-entropy function FU (w) in the
domain v ≤ w ≤ w∗ . If w ≤ v, then FU (w) = 0; if w > w∗ the feasible set of optimization
problem in 29 is empty and FU (w) = +∞. When v ≤ w ≤ w∗ , the function FU (w) is not
necessarily convex or concave as a function of w: it is strictly increasing and piecewise
concave (Neyman and Okada, 2000, p. 241).

2

5.2. On the set PU (w)
The function FU (w) is defined in (29) using PU (w), which is the set of all distributions
that guarantee a security level w for player A. Observe that
PU (w) = {p ∈ ∆(A) : pT U ≥ w1T },
2

This property is stated in Neyman and Okada (2000) in terms of the function J(·).

35

(31)

PU (w1 )
PUc (w2 )
∆(A)
Figure 2: Illustration of PU (w1 ), PUc (w2 ) and ∆(A)

is a polytope defined via some linear constraints. As the matrix U is completely arbitrary,
with a change of variables, one can convert it to many different equivalent polytopes. We
only need to study PU (w) for v ≤ w ≤ w∗ . It is immediate from the definition of PU (w)
that this set is decreasing in w, i.e., for any w1 ≥ w2 ,
PU (w1 ) ⊆ PU (w2 ).

(32)

We are interested to see if the inclusion in (32) is strict, and if yes, quantify to what
extent it is. To do this, we look at the distance between the set PU (w1 ) and the compliment
of PU (w2 ) (that is PUc (w2 ) = ∆(A) − PU (w2 )). The sets PU (w1 ), PUc (w2 ) and ∆(A) are
illustrated in Figure 2. The distance between any two sets can be defined as
d(S1 , S2 ) ,

inf

p∈S1 ,q∈S2

d(p, q),

where d(p, q) can be any arbitrary distance measure. The standard option is the total
variational distance
d1 (p, q) =

1X
|pi − qi |.
2 i

With this choice of the distance, we have
Theorem 20. For any w1 , w2 satisfying v ≤ w2 ≤ w1 ≤ w∗ , we have
d1 (PUc (w2 ), PU (w1 )) ≥
36

|w1 − w2 |
.
|m − m|

Observe that the quantities m and m can be simply computed from U. The idea of
the proof of Theorem 20 is standard (e.g., see (Gossner and Vieille, 2002, eq. (4)) for a
similar derivation), but is included in Section 6.3 for completeness.
In this paper, we propose use of the Rényi divergence of order two between p and q
to quantify the distance between two distributions:3
X p2
i
d2 (p, q) , log(
) = log(1 + χ2 (p, q)).
qi
i
Our first result gives the following bound:
Theorem 21. For any w1 , w2 satisfying v ≤ w2 ≤ w1 ≤ w∗ , we have


(w1 − w2 )2
c
d2 (PU (w2 ), PU (w1 )) ≥ log 1 +
.
(w1 − m)(m − w1 )
The proof can be found in Section 6.3. The above result is derived by a probabilistic
approach, which we believe is novel in the context of linear programming.
Our second result is less crucial, but still useful. It gives a compact formula for the
supporting hyperplanes of PU (w) in terms of the Nash equilibrium of a game. We need a
definition:
Definition 22. Val(U) denotes the value of a two-player zero-sum game with payoff table
U = [uij ].
Val(U) is the maximum value that Alice can guarantee using arbitrary mixed strategies.
It is known that in a zero-sum game, while the game might have multiple Nash equilibria,
the value of Alice in all of the equilibria is the same (See e.g., Narahari (2014), p.145).
Given values a1 , a2 , . . . , an ∈ R, let us construct a new table whose (i, j) entry is
ũij = uij + ai . In other words, we add ai to the entries in the i-th row of U. The new
table can be expressed as Ũ = U + a · 1T where a is a column vector whose entries are
a1 , a2 , . . . , an and 1T is a row vector of all ones. Observe that the table Ũ can be intuitively
3

In this definition, we set p2i /qi to be zero if pi = qi = 0, and infinity if pi > 0 while qi = 0. We have

that d2 (p, q) ≥ 0, and d2 (p, q) = 0 if and only if p = q.

37

understood as giving an additional incentive ai to Alice for playing her i-th action (it is
actually a disincentive or “tax” if ai < 0).
Theorem 23. The set PU (w) can be characterized as follows:
(
X
PU (w) = p ∈ ∆(A)
ai pi ≤ Val(U + a1T ) − w,

)
∀a .

i

P
Remark 24. Note that maxp∈PU (w) ( i ai pi ) is simply a linear program. Equivalence
of linear program and Nash equilibria are known in the literature Dantzig (1951); Adler
(2013). However, our construction of the game Ũ based on incentive or tax is new to best
of our knowledge.
In Section 6.4, we give the proof of Theorem 23 as well as a geometric picture of the
Nash equilibrium strategies of Alice.
5.2.1. On the min-entropy function
We begin with a property of the min-entropy function. To state the property, we need
the following definition:
Definition 25. Consider two games with payoff matrixes U1 and U2 . Let U3 = U1 ⊕ U2 be
the direct-sum of U1 and U2 . Then U3 defines a new game in which players simultaneously
play one instance of U1 and one instance of U2 and the resulting payoff is the sum of
payoffs from U1 and U2 .
Theorem 26. For every game U, FU⊕U (w) = FU (w/2). Similarly, for every natural number
k, F⊕k U (w) = FU (w/k) where ⊕k U is k times direct sum of U.
Proof of Theorem 26 is provided in Section 6.5.
An application of the above theorem is that given an expression GU (w) that bounds
FU (w) from below for all w and U, we can conclude that G⊕k U (kw) ≤ F⊕k U (kw) = FU (w).
Thus, maxk G⊕k U (kw) is also a (potentially better) lower bound to FU (w). As a result, we
expect that a “good” lower (or upper bound) on FU (w) should have the correct scaling
behavior as we simultaneously play more and more copies of the game.
38

5.3. Lower and upper bounds on the min-entropy function
The min-entropy function FU (w) in (29) is the minimum of a concave function on a
polytope PU (w). This minimum occurs at a vertex of PU (w). This leads to a search in the
exponentially large set of vertexes of the polytope PU (w), which is computationally hard.
We desire to find bounds on FU (w) that are either explicit, or else can be computed in
polynomial time. Observe that
FU (w) = min H(p) = log(|A|) − max D(pkpu )
p∈PU (w)

(33)

p∈PU (w)

where pu is the uniform distribution over A, and D(pkq) =

P

i

pi log(pi /qi ) is the

Kullback–Leibler (KL) divergence. Thus, we are interested in finding the vertex of PU (w)
which has maximum distance from the uniform distribution (with respect to KL divergence).
Lower bound: To prove lower bounds for
FU (w) = min H(p),

(34)

p∈PU (w)

one idea is to replace the entropy function with a smaller function and compute the
minimum over PU (w). The second idea is to minimize the min-entropy function FU (w)
over all payoff tables with given properties such as m, m and v. Another idea is to
also relax the set of distributions PU (w) and replace it with a potentially bigger set. We
proceed with the first idea, then elaborate the second idea and finally comment on the
third idea. Using the fact that the Rényi entropy is decreasing in its order, we obtain
that for any α > 1
FU (w) = min H(p) ≥ min Hα (p),
p∈PU (w)

(35)

p∈PU (w)

where Hα (p) is the Rényi entropy of order α:
1
Hα (p) =
log2
1−α

!
X

pαi

.

i

The case of α = 2 is related to the Euclidean norm and results in an optimization problem
similar to the one given in (33) for the Euclidean norm instead of the KL divergence, which
39

is still not tractable. However, the case α = ∞ relates to the maximum norm and results
in the following lower bound:
(1)
GU (w)


= − log2


max max pi .

p∈PU (w) i∈A

For each i, the problem of finding the maximum of pi over p ∈ PU (w) is a linear program.
From Theorem 23, we can find an upper bound on the value of this linear program,
yielding

(1)
GU (w) ≥ − log2 max Val(U + ei 1T ) − w ,
i

(36)

where ei is a vector of length |A| = n whose i-th coordinate is one, and all its other
(1)

coordinates are zero. The lower bound GU (w), or its relaxed version in (36) can be
found in polynomial time, even though they are not in explicit forms.
To obtain an explicit lower bound, observe that log2 (1/pi ) = d2 (ei , p). Note that the
vector ei is a probability vector associated to a deterministic random variable that chooses
i with probability one. Take some  > 0. By definition, deterministic strategies cannot
secure a payoff of more than v. Hence ei ∈ PUc (v + ). Thus,


(1)
GU (w) = − log2 max max pi
p∈PU (w) i∈A

1
= min min log2 ( )
i∈A
p∈PU (w)
pi
= min min d2 (ei , p)
p∈PU (w) i∈A

≥ min
min d2 (q, p)
p∈PU (w) q∈PUc (v+)


(w − v − )2
≥ log2 1 +
,
(w − m)(m − w)

(37)

where (37) follows from Theorem 21. Letting  → 0, we obtain


(w − v)2
(2)
FU (w) ≥ GU (w) , log2 1 +
∀w : v ≤ w ≤ w∗ .
(w − m)(m − w)
With a similar argument and using the fact that pi = 1 − d1 (ei , p), we obtain the
following lower bound utilizing Theorem 20:


w−v
(3)
FU (w) ≥ GU (w) , − log2 1 −
m−m
40

∀w : v ≤ w ≤ w∗ .

(2)

(3)

Observe that when v = m, GU (w) equals GU (w). When v 6= m, a simple calculation
(3)

(2)

shows that GU (w) ≥ GU (w) if and only if w ≥ (m + v)/2.
Example 27. Consider a game with payoff

−1


U= 1

1

matrix:
1
0.5
1

1





1

0.5

From payoff matrix we have v = .5, m = −1, m = 1 and w∗ = 0.778. Therefore for
(2)

(3)

w ≥ 0.75, GU (w) gives a better lower bound than GU (w) on FU (w).
Remark 28. One can inspect that just like the min-entropy function, the explicit lower
(2)

(3)

bounds GU (w) and GU (w) satisfy
(i)

(i)

GU⊕U (w) = GU (w/2),

i = 2, 3,

thus have the correct scaling behavior. Additionally, by replacing entropy with Rényi
entropy in the proof of Theorem 26, one also obtains that
(1)

(1)

GU⊕U (w) = GU (w/2).
(2)

The function GU (w) has second derivative for all v ≤ w ≤ w∗ , while the second
derivative of the piecewise concave function FU (w) is defined everywhere except for a finite
(2)

number of kink points. The second derivative of the function GU (w) may be positive or
(1)

negative, while FU (w) is piecewise concave. On the other hand, the function GU (w)
is piecewise convex. The reason is that if maxi∈A maxp∈PU (w) pi is attained by i∗ and a
particular vertex of PU (w) for w ∈ [w1 , w2 ], in this interval maxi∈A maxp∈PU (w) pi varies
(1)

linearly in w. Then, convexity of − log2 (·) results in convexity of GU (w) in the interval
[w1 , w2 ].
Remark 29. Inequality (37) shows that

−1
(w − v)2
max pi ≤ 1 +
p∈PU (w)
(w − m)(m − w)

∀w : v ≤ w ≤ w∗ and ∀i = 1, . . . , n
41

(38)

which gives an upper bound for the linear programming of maxp∈PU (w) pi . Note that PU (w)
is a very generic polytope, parameterized by a variable w. By a change of variables (scaling
and shifting), one can convert maxp∈PU (w) pi to a wide class of linear programs (with no
immediate connection to the probability simplex), and then use the bound given in (38).
Let m, m and v be the minimum entry, maximum entry and pure strategy security
(2)

(3)

level of the payoff table U. The lower bounds GU (w) and GU (w), just rely on the
parameters m, m and v. We seek to answer the following question: given that we just
know the parameters m, m and v from payoff table U what is the tightest lower bound for
the min-entropy function? To compute the tightest lower bound it suffices to minimize
the min-entropy function over all payoff tables (of arbitrary size) with parameters m, m
(4)

and v. Let denote this lower bound by GU (w), then,
(4)

GU (w) = min
min H(p),
0
U

(39)

p∈PU0 (w)

where the first minimization is computed over all payoff tables U0 with minimum entry
m, maximum entry m and pure-strategy security level v. We simplify the expression of
Equation (39) in the following theorem:
Theorem 30. Let m, m,v and w be some known real numbers such that m ≤ v ≤ w ≤ m.
We have
(4)
GU (w)






m−v m−w
m−w
= min
min H(p) = −
log
−
U0 p∈PU0 (w)
m−w m−v
m−v








m−v m−w
m−v m−w
1−
log 1 −
m−w m−v
m−w m−v

where bac is the greatest integer smaller than or equal to a and the first minimization is
computed over all payoff tables U0 (of arbitrary size) with minimum entry m, maximum
entry m and pure-strategy security level v.
The proof of the above theorem is provided in Section 6.6. Theorem 30 gives another
explicit form lower bound for the min-entropy function which is optimal in the sense

42

that it is the tightest lower bound that utilizes just the information of minimum entry,
maximum entry and pure-strategy security level of the payoff table.
Let us now turn to the third idea to prove a lower bound for FU (w) in (34), namely
replacing the set of distributions PU (w) with a potentially bigger set. As mentioned earlier,
minimization of the entropy over the set
PU (w) = {p ∈ ∆(A) : pT U ≥ w1T }
can be difficult. However, it could be possible to solve it (or find good lower bounds for
it) for special choices of the matrix U.4 We show how a result for an special case of U
can be utilized to find a bound (computable in polynomial time) for an arbitrary U. In
particular, let us assume that one has a way to minimize entropy over the set
Q(r) , {p ∈ ∆(A) : pT U∗ ≥ rT }
for some given matrix U∗ , and any arbitrary column vector r. Then, we are interested in
a value for r such that
PU (w) ⊆ Q(r).

(40)

Then, we can relax minimization of the entropy over the set PU (w) by instead, computing
its minimum over the set Q(r). Note that an appropriate r in (40) can be found by solving
a number of linear programs: the product pT U∗ consists of a number of linear functions of
coordinates of p, and the minimum of each linear function over the set PU (w) is a linear
program (see also Theorem 23).
Upper bound: It is clear that FU (w) ≤ H(p) for any arbitrary choice of p ∈ PU (w).
The following theorem gives a number of upper bounds, each of which are obtained by
identifying p ∈ PU (w) in different ways.
Theorem 31. Consider a game with payoff matrix U and parameters v, m, m and w∗
defined in Definition 19. Let h∗ be the entropy of some Nash strategy of player A and
4

For instance, if each row of U has only one non-zero element, the set of constraints will be on the

individual coordinates of the vector p and minimizing entropy for such constraints is tractable.

43

define
(1)
QU (w)




w−v
∗ w−v ∗
= min h , ∗
h +h
w −v
w∗ − v

(2)

QU (w) = min H(p∗max,i ),
i∈A

(3)

pi

p∈P(w)

QU (w) = min
j∈B

p∗max,i ∈ arg max

max

p∈PU (w):pT Uej =w

H(p)
(2)

where h(α) = −α log(α) − (1 − α) log(1 − α) and QU (w) can be defined with any choice
of p∗max,i from the argmax set (if there are multiple possible choices). We have
(r)

FU (w) ≤ QU (w),

r = 1, 2, 3.

Proof of Theorem 31 can be found in Section 6.7.
(1)

(1)

Remark 32. The second derivative of QU (w) is negative for v ≤ w ≤ w∗ . Thus QU (w)
is a concave function of w and one can readily inspect that:
(1)
(1) w
QU⊕U (w) = QU ( ).
2
(2)

As arg maxp∈P(w) pi may contain multiple elements, QU (w) is not a well defined function
(3)

of w. The function QU (w) is not necessarily scalable for game U ⊕ U.
Example 33. Consider two games with the following payoff tables:


3
1
0 −2 0 −2





1
0 1 1
3 −2 0 −2 0 






 0 −2 3
 1 0 .5
1
0 −2
0



U=
,
U
=


−2 0
 1 .5 0
1
3 −2 0 





 0 −2 0 −2 3
.5 1 1
1


−2 0 −2 0
1
3


.5


1
.

1

0

Figures 3 and 4 illustrate the behavior of the bounds for the games U and U0 , respectively.
(3)

(2)

In this examples since v = m, GU (w) coincides with GU (w) thus it has not been depicted
in the figures.

44

3

FU (w)
(1)

min entropy function and bounds (bit)

GU

(w)

(2)
GU (w)
(4)
GU (w)
(1)
QU (w)
(2)
QU (w)
(3)
QU (w)

2.5

2

1.5

1

0.5

0
-2

-1.8

-1.6

-1.4

-1.2

-1

-0.8

-0.6

-0.4

-0.2

0

w
Figure 3: Illustration of the bounds on min-entropy function for the game U defined in example 33. The

Min entropy function and the bounds (bit)

horizontal line depicts w and vertical line depicts the value of bounds.

2.5

FU0 (w)
(1)

G 0 (w)
U
(2)
G 0 (w)
U

2

(4)

G 0 (w)
U
(1)

Q 0 (w)
U

1.5

(2)

Q 0 (w)
U
(3)
Q 0 (w)
U

1

0.5

0
0

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

0.5

0.55

0.6

w
Figure 4: Illustration of the bounds on min-entropy function for the game U0 defined in example 33. The
horizontal line depicts w and vertical line depicts the value of bounds.

45

6. Proofs
6.1. Proof of Proposition 12
To prove Proposition 12 we make use of Lemmas 34 and 6. A breif discussion on
randomness extraction and proof of Lemma 34 is provided in Appendix A.
Lemma 34. Consider the correlated random sequences XpL and YpL drawn i.i.d. from respective spaces X and Y by joint probability distribution pX,Y . Let Q(L) be a random variable independent of YpL and uniformly distributed on {1, 2, . . . , 2RL } where R < H(X|Y )
is a real number, then there exist mappings BL : X L → {1, 2, . . . , 2RL } such that
lim kpBL (XpL )YpL − pQ(L) YpL kT V = 0.

L→∞

(1)

(2)

Choose a real number R such that γH(pA ) + (1 − γ)H(pA ) < R < H(X|Y ) and LR
is a natural number (for a sufficiently large L).
We define random variables Q(L) and ÂL that are mutually independent of each other,
and of YpL with the following marginal distributions: let Q(L) be a uniformly distributed
random variable on {1, 2, . . . , 2RL }, and ÂL be distributed as follows:
dγLe
L

pÂL (a ) =

Y

(1)

pA (at )

t=1

L
Y

(2)

pA (at ).

t=dγL)e+1

Note that R < H(X|Y ); thus according to Lemma 34 there exists mappings BL : X L →
{1, 2, . . . , 2RL } satisfying
lim kpBL (XpL )YpL − pQ(L) YpL kT V = 0.

L→∞

On the other hand we have
p- lim sup
L→∞

1
1
(1)
(2)
= γH(pA ) + (1 − γ)H(pA )
log
L
L
pÂL (Â )
1
1
< R = p- lim inf log
,
L→∞ L
pQL (QL )

46

(41)

therefore according to Lemma 6 there exists mappings ϕL : {1, 2, . . . , 2RL } → AL such
that
lim kpϕL (Q(L) ) − pÂL kT V = 0.

L→∞

Considering the fact that ϕL (Q(L) ) and ÂL both are independent of YpL , the above equation
results in
lim kpϕL (Q(L) )YpL − pÂL YpL kT V = 0.

L→∞

(42)

Furthermore note that
kpϕL (BL (XpL ))YpL − pÂL YpL kT V ≤ kpϕL (BL (XpL ))YpL − pϕL (Q(L) )YpL kT V + kpϕL (Q(L) )YpL − pÂL YpL kT V
≤ kpBL (XpL )YpL − pQ(L) YpL kT V + kpϕL (Q(L) )YpL − pÂL YpL kT V
(43)
where the first inequality follows from the triangle inequality for the total variation distance, and the second inequality follows from the fourth property of total variation in

Lemma 1. Let ALc = ψL (XpL ) = ϕL BL XpL . Then by combining equations (45), (42)
and (50) we have
lim kpALc YpL − pÂL YpL kT V = 0.

L→∞

(44)

Thus ψL (·) = ϕL (BL (·)) is the desired mapping.
6.2. Proof of Proposition 17
Choose real numbers R1 and R2 such that
R1 < H(X|Y, U = 0),

R2 < H(X|Y, U = 1),

pU (0)R1 + pU (1)R2 > H(Z|V ),

and for sufficiently large L, dpU (0)LeR1 and dpU (1)LeR2 are natural numbers. Since
H(X|Y U ) = pU (0)H(X|Y, U = 0) + pU (1)H(X|Y, U = 1) > H(Z|V ),
real numbers R1 and R2 with the above properties exist.
Let L̂ = dpU (0)Le, L̃ = L − dpU (0)Le. Observe that L = L̂ + L̃. We will consider
three sets of random variables, and relate their joint distributions later:
47

• (Set 1): Random variables (X1 , · · · , XL , Y1 , · · · , YL , W ) defined in the statement of
the proposition with the joint distribution pX L Y L W satisfying
dpU (0)Le
L

L

pX L Y L W (x , y , w) − pW (w)

Y

L
Y

pXY |U (xt , yt |0)

t=1

pXY |U (xt , yt |1)

t=dpU (0)Le+1

≤ δ1 .
TV

• (Set 2): Mutually independent random variables W 0 , (X̂ L̂ , Ŷ L̂ ) and (X̃ L̃ , Ỹ L̃ ). Here
pW 0 = pW . Furthermore, (X̂ L̂ , Ŷ L̂ ) and (X̃ L̃ , Ỹ L̃ ) are i.i.d. according to pXY |U (x̂, ŷ|0)
and pXY |U (x̃, ỹ|1), respectively.
• (Set 3): Two independent random variables Q̂(L̂) and Q̃(L̃) with uniform distributions
on {1, 2, . . . , 2L̂R1 } and {1, 2, . . . , 2L̃R2 } respectively.
Since R1 < H(X|Y, U = 0) and R2 < H(X|Y, U = 1) according to Lemma 34 for
arbitrary δ 0 > 0 there exist mappings B̂L̂ : X L̂ → {1, 2, . . . , 2R1 L̂ } and B̃L̃ : X L̃ →
{1, 2, . . . , 2R2 L̃ } satisfying
kpB̂ (X̂ L̂ )Ŷ L̂ − pQ̂(L̂) pŶ L̂ kT V ≤ δ 0 ,
L̂

kpB̃ (X̃ L̃ )Ỹ L̃ − pQ̃(L̃) pỸ L̃ kT V ≤ δ 0 ,
L̃

(45)

for sufficiently large L̂ and L̃. Next let Q(L) = (Q̂(L̂) , Q̃(L̃) ) and BL : X L → {1, 2, . . . , 2R1 L̂+R2 L̃ }
be the mapping BL (X̂ L̂ , X̃ L̃ ) = (B̂L̂ (X̂ L̂ ), B̃L̃ (X̃ L̃ )). Using Equation (45), independence
of (X̂ L̂ , Ŷ L̂ ) from (X̃ L̃ , Ỹ L̃ ), and independence of Q̂(L̂) from Q̃(L̃) , we have
kpBL (X̂ L̂ ,X̃ L̃ )Ŷ L̂ Ỹ L̃ − pQ(L) pŶ L̂ pỸ L̃ kT V ≤ 2δ 0 ,
where we used the third property of total variation in Lemma 1 for random variables E1 =
(B̂L̂ (X̂ L̂ ), Ŷ L̂ ), F1 = (B̃L̃ (X̃ L̃ ), Ỹ L̃ ), E2 = (Q̂(L̂) , Ŷ L̂ ) and F2 = (Q̃(L̃) , Ỹ L̃ ). Then using the
fifth property of total variation in Lemma 1 for random variables E1 = (BL (X̂ L̂ , X̃ L̃ ), Ŷ L̂ , Ỹ L̃ ),
E2 = (Q(L) , Ŷ L̂ , Ỹ L̃ ) and F = W 0 , we get
kpW 0 pBL (X̂ L̂ ,X̃ L̃ )Ŷ L̂ Ỹ L̃ − pW 0 pQ(L) pŶ L̂ pỸ L̃ kT V ≤ 2δ 0 .

(46)

The above inequality relates the distribution of the Set 2 of random variables to the
distribution of the Set 3 of random variables. Now, we consider the Set 1 of random
48

variables. By applying the mapping BL on sequence X L we have that
kpW BL (X L )Y L − pW pQ(L) pY L kT V ≤ kpW BL (X L )Y L − pW 0 pBL (X̂ L̂ ,X̃ L̃ )Ŷ L̂ Ỹ L̃ kT V +
kpW 0 pBL (X̂ L̂ ,X̃ L̃ )Ŷ L̂ Ỹ L̃ − pW 0 pQ(L) pŶ L̂ pỸ L̃ kT V +
kpW 0 pQ(L) pŶ L̂ pỸ L̃ − pW pQ(L) pY L kT V
≤ 2δ1 + 2δ 0 ,

(47)

where the first inequality follows from the triangle inequality for the total variation distance, and the second inequality results from Equation (46) and the following two facts:
• kpW BL (X L )Y L − pW 0 pBL (X̂ L̂ ,X̃ L̃ )Ŷ L̂ Ỹ L̃ kT V ≤ δ1 . This is a consequence of the statement
of the proposition that the variables (W, X L , Y L ) are in δ1 distance from the ideal
variables (W 0 , X̂ L̂ , X̃ L̃ , Ŷ L̂ , Ỹ L̃ ), combined with the fourth property of total variation
in Lemma 1.
• kpW 0 pQ(L) pŶ L̂ pỸ L̃ − pW pQ(L) pY L kT V ≤ δ1 . To see that this inequality is correct first
note that as stated in the statement of the proposition the variables (W, X L , Y L )
are in δ1 distance from the ideal variables (W 0 , X̂ L̂ , X̃ L̃ , Ŷ L̂ , Ỹ L̃ ) hence the second
property of total variation in Lemma 1 implies that Y L is in δ1 distance of (Ŷ L̂ , Ỹ L̃ ).
Then the fact that pW 0 = pW along with the fifth property of total variation in
Lemma 1 gives the desired inequality.
Now, Let Ẑ L be an ideal sequence with distribution
dpV (0)Le
L

pẐ L (ẑ ) =

Y

pZ|V (ẑt |0)

t=1

L
Y

pZ|V (ẑt |1).

t=dpV (0)Le+1

Then we have
p- lim sup
L→∞

1
1
log
= H(Z|V )
L
pẐ L (Ẑ L )
< pU (0)R1 + pU (1)R2 = p- lim inf
L→∞

49

1
1
log
.
L
pQL (QL )

Therefore according to Lemma 6 there exists mappings ϕL : {1, 2, . . . , 2R1 L̂+R2 L̃ } → Z L
such that for sufficiently large L
kpϕL (Q(L) ) − pẐ L kT V ≤ δ 0 .

(48)

By using the fifth property of total variation in Lemma 1 for random variables E1 =
ϕL (Q(L) ), E2 = Ẑ L and F = (W, Y L ), Equation (48) results
kpϕL (Q(L) ) pY L pW − pẐ L pY L pW kT V ≤ δ 0 .

(49)

Thus we have
kpϕL (BL (X L ))Y L W − pẐ L pY L pW kT V ≤ kpϕL (BL (X L ))Y L W − pϕL (Q(L) ) pY L pW kT V +
kpϕL (Q(L) ) pY L pW − pẐ L pY L pW kT V
≤ kpBL (X L )Y L W − pQ(L) pY L pW kT V + δ 0
≤ 2δ1 + 3δ 0

(50)

where the first inequality follows from the triangle inequality for the total variation distance, the second inequality is a consequent of Equation (49) and the fourth property of
total variation in Lemma 1 where E1 and E2 are replaced by BL (X L )Y L W and Q(L) Y L W
respectively and the third inequality results from Equation (47).

Let Z L = ϕL BL (X L ) and take δ 0 small enough that 3δ 0 ≤ δ2 . Then from Equation
(50) we have
kpZ L Y L W − pẐ L pY L pW kT V ≤ 2δ1 + δ2 ,
and the proof is complete.
6.3. Proof of Theorems 20 and 21
Take arbitrary p ∈ PUc (w2 ) and q ∈ PU (w1 ). Since p ∈ PUc (w2 ), when Alice plays
according to p, Bob has a (pure) strategy j ∈ B that reduces Alice’s expected payoff
to a number less than w2 . We can define a random variable W̃ that represents the
payoff of Alice when Alice plays p and Bob plays j. Then, the alphabet set of W̃ is
50

{u1j , u2j , . . . , unj }, and its probability distribution over this set is p. We must have
E[W̃ ] < w2 .
Let us assume that Alice adopts q, but Bob keeps playing the same j ∈ B. Let W
be the random variable, describing the payoff of Alice when she plays according to q.
Because q ∈ PU (w1 ), E[W ] ≥ w1 . We can think of W as taking uij with probability pi .
Theorem 20 follows from the following chain of inequalities:
|E[W ] − E[W̃ ]| =

X

(pi − qi )uij

i



m+m
(pi − qi ) uij −
(51)
=
2
i
X

m+m
≤
|pi − qi | max uij −
i
2
i


|m − m|
,
(52)
≤ (2d1 (p, q))
2
P
P
where (51) follows from the fact that 1/2(m + m) is constant and i pi = i qi = 1.
X

To prove Theorem 21, the key step is to relate the Rényi divergence to variance.
Remember that d2 (p, q) = log(1 + χ2 (p, q)). The following lemma follows from the
Chapman–Robbins bound:
Lemma 35. Take an arbitrary sequence of real numbers (x1 , x2 , . . . , xn ) and two probability distributions p = (p1 , p2 , . . . , pn ) and q = (q1 , q2 , . . . , qn ). Let W be a random variable
that takes value xi with probability qi , and W̃ be a random variable that takes value xi
with probability pi . Then, we have
χ2 (p, q) ≥

(E[W ] − E[W̃ ])2
.
Var[W ]

(53)

Furthermore, the above inequality becomes an equality if we set xi = (pi − qi )/qi .
Observe that the left hand side of (53) depends only on the probability values pi and
qi , while the right hand side depends not only on the probabilities, but also the values
that W and W̃ take. Using this lemma and the fact that E[W̃ ] < w2 < w1 ≤ E[W ], we
51

can conclude
(E[W ] − w2 )2
.
Var[W ]
Observe that m ≤ W ≤ m holds with probability one. The proof is finished by the
χ2 (p, q) ≥

following lemma.
Lemma 36. For any w1 > w2 , we have
(E[W ] − w2 )2
(w1 − w2 )2
≥
,
Var[W ]
(w1 − m)(m − w1 )
provided that E[W ] ≥ w1 , and m ≤ W ≤ m.
The proof of this lemma is given in Appendix B.
6.4. Proof of Theorem 23
In this section we provide additional details and build a geometric picture. This picture
implies Theorem 23, but also gives a geometric interpretation of Nash strategies.
Let
L(a1 , a2 , . . . , an ) = Val(U + a1T ),

∀a ∈ Rn .

Observe that the table Ũ can be intuitively understood as giving an additional incentive
ai to Alice for playing her i-th action (it is actually a disincentive if ai < 0). Also, since
L(a1 + c, a2 + c, . . . , an + c) = L(a1 , a2 , . . . , an ) + c,
we only need to understand L when the sum of the incentives ai is zero.
We need the following definition:
Definition 37. Let
K(p1 , p2 , . . . , pn ) = min
j

X

pi uij

i

be the payoff that Alice can guarantee with playing distribution (p1 , . . . , pn ) with table U.
We extend the definition of K(·) to arbitrary (p1 , p2 , . . . , pn ) ∈ Rn by setting
K(p1 , p2 , . . . , pn ) = −∞,
when the tuple (p1 , p2 , . . . , pn ) does not form a valid probability distribution, i.e., when any
P
of the pi ’s becomes negative, or i pi 6= 1.
52

Note that
n
o
PU (w) = p K(p) ≥ w .
A full geometric picture of PU (w) as well as Nash strategies are provided in the following
theorem:
Theorem 38. We have
1. The function L(a1 , a2 , . . . , an ) is the convex conjugate dual of K(p1 , p2 , . . . , pn ) in
the following sense:
"
L(a) = maxn K(p) +
p∈R

n
X

#
p i ai ,

∀a ∈ Rn .

(54)

i=1

The function L(a1 , a2 , . . . , an ) is jointly convex in (a1 , a2 , . . . , an ), while K(p1 , p2 , . . . , pn )
is jointly concave in (p1 , p2 , . . . , pn ).
Furthermore, the supporting hyperplanes to the convex curve a 7→ L(a) characterize
Alice’s Nash strategies as follows: for any arbitrary a, p is a Nash strategy of Alice
for table Ũ = U + a1T if and only if p is a subgradient of the function L at a. In
other words, take some arbitrary vector a. Then,
L(b1 , b2 , . . . , bn ) ≥ L(a1 , a2 , . . . , an ) +

X

∀b ∈ Rn ,

(bi − ai )pi ,

(55)

i

if and only if p is a Nash strategy of Alice for the payoff table Ũ = U + a1T .
2. Given a probability vector p, we have
L(a1 , a2 , . . . , an ) ≥ w +

X
(ai − bi )pi ,

∀a,

i

if and only if p guarantees a payoff of at least w for game U + b1T . In particular,
setting bi = 0,
L(a1 , a2 , . . . , an ) ≥ w +

X

ai p i ,

∀a,

(56)

i

if and only if p guarantees a payoff of at least w for game U, i.e., p ∈ PU (w). Thus,
P
having a payoff w, we look for hyperplanes of the form w + i pi ai that pass through
w at (a1 , a2 , . . . , an ) = (0, 0, . . . , 0), and lie below the curve of L.
53

Observe that the second part of Theorem 38 is equivalent with Theorem 23.
Proof of Theorem 38. We begin with the first part of the theorem. Using the max-min
formulation for the value of a game Ũ, we have
L(a1 , a2 , . . . , an ) =

max
P

pi ≥0,

i

min

X

j

pi =1

pi (uij + ai )

i

"
=

!

i

#
+

X

K(p1 , p2 , . . . , pn ) +

X

max
P

pi ≥0,

X

min
j

pi =1

pi uij

i

p i ai

i

"
=

max
P

pi ≥0,

i

pi =1

#
p i ai .

i

"

#

= max K(p1 , p2 , . . . , pn ) +
pi ∈R

X

p i ai .

(57)

i

where (57) follows from the fact that K(p) is minus infinity when p is not a probability
distribution. This shows the duality of L(·) and K(·). Next, note that K(·) is a minimum
of linear functions; hence it is a concave function. Convexity of L(·) can be directly seen
from (55) which implies that at least one supporting hyperplane to its curve exists at
any given point (since at least one Nash strategy exists for any arbitrary game). Thus, it
remains to prove (55).
Without loss of generality, it suffices to prove (55) for b = 0 (bi = 0), and get the
result for arbitrary b by changing variable U → U + b1T . The inequality
L(a1 , a2 , . . . , an ) ≥ L(0, 0, . . . , 0) +

X

ai p i ,

∀a,

(58)

i

can be also expressed as
!
min L(a1 , a2 , . . . , an ) −
a

X

ai p i

≥ L(0, 0, . . . , 0).

i

From the duality relation (57) and utilizing the Fenchel’s duality theorem, the left hand
side is K(p1 , p2 , . . . , pn ). Thus, the expression is equivalent with (58) can be written as
K(p1 , p2 , . . . , pn ) ≥ L(0, 0, . . . , 0) = Val(U),
54

which is equivalent with p being a Nash strategy.
To proof for the second part of the theorem is similar. As before bi can be set to zero.
Then, we can express (56) as
!
min L(a1 , a2 , . . . , an ) −

X

a

ai p i

≥ w.

i

From the duality relation (57) and the Fenchel’s duality theorem, this is equivalent with
K(p1 , p2 , . . . , pn ) ≥ w, or p ∈ PU (w).

6.5. Proof of Theorem 26
Let pA (a) be an arbitrary distribution that secures payoff w/2 in game U. From the
linearity of expectation we conclude that pA1 A2 (a1 , a2 ) = 1(a1 = a2 )pA (a1 ) secures payoff
w in game U ⊕ U, where 1(·) is the indicator function. In this case H(pA1 A2 ) = H(pA ) thus
the function FU⊕U (w) is bounded above as follows:
w
FU⊕U (w) ≤ FU ( ).
2

(59)

On the other hand, let p∗A1 A2 ∈ PU⊕U (w) be a distribution with minimum entropy that
secures arbitrary payoff w in game U ⊕ U, i.e., H(p∗A1 A2 ) = FU⊕U (w). Note that such a
distribution p∗A1 A2 exists because PU⊕U (w) is compact. We have
w ≤ min Ep∗A A [uA1 ,j1 + uA2 ,j2 ]
1 2
j1 ,j2 ∈B


= min Ep∗A A [uA1 ,j1 ] + Ep∗A A [uA2 ,j2 ]
j1 ,j2 ∈B

1

2

1

2

= min Ep∗A [uA1 ,j1 ] + min Ep∗A [uA2 ,j2 ],
j1 ∈B

j2 ∈B

1

2

(60)

where p∗A1 and p∗A2 are the marginal distributions of p∗A1 A2 . Equation (60) implies that
there exists k ∈ {1, 2} such that
min Ep∗A [uAk ,jk ] ≥
jk ∈B

k

55

w
.
2

Thus, p∗Ak secures payoff w/2 in game U. Hence,
(a)
w
FU⊕U (w) = H(p∗A1 A2 ) ≥ H(p∗Ak ) ≥ FU ( ),
2

(61)

where (a) follows from the properties of entropy.
Equations (59) and (61) conclude FU⊕U (w) = FU (w/2). The above line of proof can be
extended for every natural number k to prove F⊕k U (w) = FU (w/k).
6.6. Proof of Theorem 30
If v = m then there exists a pure strategy a ∈ A that guarantees the maximum
achievable payoff m in any permissible payoff table U0 . Pure strategies have zero entropy
(4)

(4)

and GU (w) = 0. The explicit expression that we wish to prove for GU (w) also vanishes
as v tends to m, and the claim holds when v = m. Hence for the rest of the proof we
suppose that v < m.
We claim that an optimal table for the minimization problem in the statement of the
theorem is as follows:







∗
U =







m m m

m

m

v

m

m

m m

v

m

m m m
.. .. ..
. . .

v
..
.

m m m ···

···

m





m 


··· m 


··· m 

. 
..
. .. 

··· v
···

,

(62)

m×m

where the above square table is of size m = b(m − v)/(m − w)c + 2. We first show that
there is an optimal payoff table with the structure given in (62) for some value of m and
then optimize over m, the size of the table.
Take some arbitrary table U0 = [u0i,j ] and distribution p ∈ PU0 (w). Since mini∈A minj∈B u0i,j =
m thus there exists a row i and a column j such that u0i,j = m. By reordering of
rows and columns of the table, we may assume that u01,1 = m. Furthermore, since
maxi∈A minj∈B u0i,j = v, for all i there exists a ji such that u0i,ji ≤ v. Thus, u0i,j ≤ u00i,j
56

where U00 = [u00i,j ] is defined as follows:

u00i,j =




m, i = 1, j = 1,






m, i = 1, j 6= 1,



m, i 6= 1, j =
6 ji ,





v, i =
6 1, j = ji .

The table U00 has higher payoffs for Alice than the table U0 in each cell. Hence, p ∈ PU00 (w).
The table U00 also belongs to the feasible set of the minimization problem because it has
one row containing one entry with value m and all other rows contain an entry with value
v.
Next, we can do two more operations: if there is a column with all m entries, we delete
that column. Because we are restricting the action set of Bob, Alice can still secure payoff
w with the same distribution p. If two rows of the table U00 are the same, we can merge
them together into one row. In other words, for instance the second and third rows are the
same, i.e., j2 = j3 , we can merge the second and third rows together and assign the sum
probability p2 + p3 to this merged row. This will reduce the entropy of the probability
vector p, while leaving the payoff of Alice unchanged. With these two operations and
row/column permutation, we either obtain the table given in (62) for some value of m, or
the following m × (m − 1) table

m m


 v m


 m v


 m m

 .. ..
 . .

m m

m

m

···

m

m

m

···

m

m

m

···

m

v
..
.

m
..
.

··· m
.
..
. ..

m ···

···

v
















.

(63)

m×(m−1)

One can directly verify that any probability distribution p for the payoff of Alice from
the table in (63) is less than or equal to the payoff of Alice from the table in (62).
57

Having showed that a table with the structure given in (62) is optimal, we now optimize
(4)

over m, the size of the table and compute GU (w). The constraint p = (p1 , p2 , . . . , pm ) ∈
PU (w) is equivalent to:
mp1 + m(1 − p1 ) ≥ w,
vpi + m(1 − pi ) ≥ w,

∀i > 1,

which simplifies to
p1 ≤

m−w
,
m−m

pi ≤

m−w
,
m−v

∀i > 1.

We claim that without loss of generality, we can assume that p1 = 0. Since
we have p1 ≤

m−w
.
m−v

(64)
m−w
m−v

≥

m−w
,
m−m

Now, if we have a distribution (p1 , p2 , . . . , pm ) on a table of the

form (62) for some m, we can consider the distribution (0, p1 , p2 , . . . , pm ) on a table with
size m + 1; the entropy of (0, p1 , p2 , . . . , pm ) is the same as (p1 , p2 , . . . , pm ) and achieves
the payoff of w. Therefore, the problem essentially reduces to the following: what is
the minimum possible entropy for the set of all probability distributions (p1 , p2 , . . . , pm )
satisfying
pi ≤

m−w
,
m−v

∀i.

(65)

The answer is the pmf p∗ where


(m − w)/(m − v),
i = 1, 2, . . . , b(m − v)/(m − w)c,
∗
pi =

1 − b(m − v)/(m − w)c(m − w)/(m − v), i = b(m − v)/(m − w)c + 1.
The distribution p∗ is the pmf that includes as much elements with value (m−w)/(m−v)
as possible. This distribution has minimum entropy because it majorizes all other pmfs
in PU (w) (Nielsen, 2002, Theorem 8.0.1). In other words, for any distribution p satisfying
P
Pi
↓
(65), we have for all i ≤ m, i`=1 p∗↓
` ≥
`=1 p` . Here, for a probability mass function
p = (p1 , p2 , . . . , pm ), we let p↓ = (p↓1 , p↓2 , . . . , p↓m ) be the vector whose elements are the
elements of p reordered into non-decreasing order.

58

The entropy of p∗ equals




m−v m−w
m−w
∗
log
−
H(p ) = −
m−w m−v
m−v








m−v m−w
m−v m−w
1−
log 1 −
m−w m−v
m−w m−v
as desired.
6.7. Proof of Theorem 31
Let p∗ be a Nash strategy for player A where H(p∗ ) = h∗ , and i∗ ∈ arg maxi∈A minj∈B uij
be the pure strategy that guarantees payoff v for player A. For v ≤ w ≤ w∗ define
α = (w∗ − w)/(w∗ − v) and p = αei∗ + (1 − α)p∗ where ei∗ is a vector of all zero elements
except for its i∗ th element which is 1. The pmf p guarantees payoff w since
pT U = αeTi∗ U + (1 − α)p∗ T U ≥ αv1 + (1 − α)w∗ 1 = w1
Using properties of entropy one can inspect that:
H(p) ≤ αH(ei∗ )+(1−α)H(p∗ )+H(α, 1−α) = (1−α)h∗ −α log2 (α)−(1−α) log2 (1−α).
Therefore FU (w) ≤ H(p) ≤ (1 − α)h∗ − α log2 (α) − (1 − α) log2 (1 − α). Additionally, as
(1)

h∗ secures payoff w∗ ≥ w then FU (w) ≤ h∗ . These two facts imply FU (w) ≤ QU (w) once
we substitute the value of α.
From the definition of p∗max,i it follows that p∗max,i ∈ PU (w). Therefore for every i ∈ A,
(2)

FU (w) ≤ H(p∗max,i ) and FU (w) ≤ QU (w) follows.
For an arbitrary j ∈ B if p0 ∈ {p ∈ PU (w) : pT Uej = w} then as p0 also belongs to
PU (w) we have FU (w) ≤ H(p0 ). Then, for every j ∈ B:
FU (w) ≤

max

p∈PU (w):pT Uej =w

H(p).
(3)

The above inequality is correct for every j ∈ B thus FU (w) ≤ QU (w).

59

Appendix A. Review of the randomness extraction literature
In this appendix we review some results about randomness extraction which plays a
key role in the construction of optimal strategies for the maximizer in the repeated games
studied in this paper. The results of this section are adopted from Renner (2008) who
considered the randomness extraction problem in the framework of quantum information
theory.
Randomness extraction is the process of deriving some almost fair random bits from
a given source X. More precisely, let X ∈ X and Y ∈ Y be two random variables with
joint distribution pXY and let f : X → {1, 2, 3, . . . , 2` } be a deterministic mapping such
that for B = f (X) and  > 0 we have
pBY − pUB pY

≤ ,
TV

where pBY is the joint distribution of B and Y and pUB is the uniform distribution on
{1, 2, 3, . . . , 2` }. Then we say f extracts ` fair bits independent of Y from X with precision
.
To precede we need the definition of conditional collision entropy for a given pair of
random variables. The following subsection is devoted for this definition.
Appendix A.1. Conditional collision entropy
Let X ∈ X and Y ∈ Y be two random variables with joint probability distribution
pXY and let qY be an arbitrary probability distribution on the sample space Y. The
conditional collision entropy of pXY given qY is defined as follows:5
X

H2 (pXY |qY ) = − log

(x,y)∈X ×Y

pXY (x, y)2
,
qY (y)

and the conditional collision entropy of pXY given Y is defined as:
H2 (pXY |Y ) = max H2 (pXY |qY ),
qY ∈∆(Y)

5

In this and upcoming definitions, we set qY (y)/pXY (x, y) to be zero if qY (y) = pXY (x, y) = 0, and

infinity if qY (y) > 0 while pXY (x, y) = 0.

60

where ∆(Y) is the probability simplex on the sample space Y.
The conditional collision entropy as defined above, is not a continuous function of the
input probability distribution and a slight change of the probability distribution might
result in a large deviation in its conditional collision entropy. The smoothed version of
conditional collision entropy resolves this drawback. Let  be an arbitrary positive number
and pXY and qY be some probability distributions on X × Y and Y, respectively. The
-smooth conditional collision entropy of pXY given qY is
H2 (pXY |qY ) =

max

pXY ∈B (pXY )

H2 (pXY |qY ),

where
B (pXY ) = {pXY ∈ ∆(X × Y); kpXY − pXY kT V ≤ }.
As before, the -smooth conditional collision entropy of pXY given Y is defined as
H2 (pXY |Y ) = max H2 (pXY |qY ).
qY ∈∆(Y)

In the following remark we show that for i.i.d. sources the smoothed conditional collision entropy is related to the shannon entropy of the source.
Remark 39. Let (X n , Y n ) ∈ X n × Y n be drawn i.i.d. from probability distribution pXY =
(n)

pY pX|Y and for arbirtary  > 0, the set of typical sequences, τ , be defined as


1
n n
(n)
n n
n
n
τ = (x , y ) ∈ X × Y : − log pX n |Y n (x |y ) − H(X|Y ) ≤  ,
n
Q
where pX n |Y n (xn , y n ) = ni=1 pX|Y (xi |yi ) is the conditional distribution of X n given Y n .
Considering that E[− log pX|Y (X|Y )] = H(X|Y ) and
n

1X
1
− log pX n |Y n (X n |Y n ) = −
− log pX|Y (Xi |Yi ),
n
n i=1
the weak law of large numbers results that for sufficiently large n,


Pr (X n , Y n ) ∈ τ(n) ≥ 1 − .

61

(A.1)

Next let pX n Y n be a probability distribution on X n × Y n defined as

n n)

(n)

i
 phX n Yn n (xn ,y (n)
(xn , y n ) ∈ τ ,
Pr
(X
,Y
)∈τ

pX n Y n (xn , y n ) =


0
otherwise.
The definition above along with Equation (A.1) implies that kpX n Y n − pX n Y n kT V ≤  holds
for sufficiently large n. Therefore for sufficiently large n we have
H2 (pX n Y n |Y n ) ≥ H2 (pX n Y n |pY n )

X
= − log 

n

(xn ,y n )∈X n ×Y n

= − log



pX n Y n (x , y ) 
pY n (y n )


pX n Y n (xn , y n )


≥ − log

n

max

(xn ,y n )∈X n ×Y n

max
(n)
(xn ,y n )∈τ

pX n |Y n (xn |y n )
!

pX n |Y n (xn |y n )

≥ n(H(X|Y ) − ).
Appendix A.2. Randomness extraction
In this subsection we present the main tools regarding the extraction of randomness
from a given source with known distribution.
Theorem 40. Let X ∈ X and Y ∈ Y be two random variables with joint distribution
pXY . For arbitrary ` let F : X → {1, 2, 3, . . . , 2` } be a random mapping constructed by
assigning to F (x) uniformly at random one element of {1, 2, 3, . . . , 2` } and independently
for distinct inputs x, x0 ∈ X . Then we have
X

pF (f ) pf (X)Y − pUB pY

TV

f

1 1
≤ 2− 2 (H2 (pXY |Y )−`) ,
2

where pF is the probability distribution of the random mapping F , pf (X)Y is the joint
distribution of Y and f (X) and pUB is the uniform distribution on the set {1, 2, 3, . . . , 2` }.
Therefore there exist a deterministic mapping f : X → {1, 2, 3, . . . , 2` } such that
pf (X)Y − pUB pY

TV

1 1
≤ 2− 2 (H2 (pXY |Y )−`) .
2
62

Proof. To begin the proof we need a corollary of the Cauchy-Schwarz inequality stated in
the following lemma.
Lemma 41. Let s1 , s2 , . . . , sn and γ1 , γ2 , . . . , γn be two sequences of real numbers such
P
that for all i = 1, 2, . . . , n, γi ≥ 0 and ni=1 γi ≤ k where k > 0. then
v
u n 2
n
X
u X si
),
|si | ≤ tk(
γ
i=1
i=1 i
where 0/0 is taken as being zero and 1/0 = ∞.
Proof. If for some i, |si | > 0 and γi = 0 then the right hand side of the inequality in the
statement of the lemma becomes infinity thus it holds. Otherwise, let for all i = 1, . . . , n,
if |si | > 0 then γi > 0 hence by using Cauchy-Schwarz inequality we have
v
v
u n
u n 2
n
n
n
2
X
X
X
X
u
u X si
s
√ |si |
i
|si | =
γi √ ≤ t(
γi )(
) ≤ tk(
),
γi
γ
γ
i=1
i=1
i=1
i=1 i
i=1 i
where we take 0/0 = 0, in accordance with the statement of the lemma.
Let qY be an arbitrary probability distribution on Y and f be an arbitrary realization
of F , then from Lemma 41 we have
1X
|pf (X)Y (b, y) − pUB (b)pY (y)|
2 b,y
v
!
u
X |pf (X)Y (b, y) − pU (b)pY (y)|2
1u
B
≤ t2`
2
qY (y)
b,y
v
!
u
X pY (y)2 X
1u
2
pf (X)|Y (b|y) − pUB (b)
= t2`
.
2
q
(y)
Y
y
b

kpf (X)Y − pUB pY kT V =

63

(A.2)

The term
X

P

b

|pf (X)|Y (b|y) − pUB (b)|2 is characterized as

pf (X)|Y (b|y) − pUB (b)

2

b

=

X

=

X

pf (X)|Y (b|y) − 2−`

2

b

pf (X)|Y (b|y)2 − 2−`

b

=

X

pX|Y (x|y)pX|Y (x0 |y) 1(f (x) = f (x0 )) − 2−`



x,x0 ∈X

=

X

pX|Y (x|y)2 1 − 2−`



x∈X

+

X

pX|Y (x|y)pX|Y (x0 |y) 1(f (x) = f (x0 )) − 2−`



x6=x0

≤

X

pX|Y (x|y)2 +

X


pX|Y (x|y)pX|Y (x0 |y) 1(f (x) = f (x0 )) − 2−` ,

x6=x0

x∈X

(A.3)
where 1(·) is the indicator function. Then by taking the average with respect to F we
have
X
f

pF (f )

X

pf (X)|Y (b|y) − pUB (b)

2

b

≤
=

X

pX|Y (x|y)2 +

x∈X

x6=x0

X

X

pX|Y (x|y)2 +

X

pX|Y (x|y)pX|Y (x0 |y)

X

pF (f )1(f (x) = f (x0 )) − 2−`

!

f

pX|Y (x|y)pX|Y (x0 |y) Pr[F (x) = F (x0 )] − 2−`



x6=x0

x∈X

=

X

pX|Y (x|y)2 ,

(A.4)

x∈X

where the inequality follows from (A.3) and the last equality holds because for distinct

64

x, x0 ∈ X , F (x) coincides with F (x0 ) with probability 2−` . Therefore
v
!
u
X
X
X pY (y)2 X
u
1
2
pF (f ) pf (X)Y − pUB pY T V ≤
pF (f )t2`
pf (X)|Y (b|y) − pUB (b)
2
q
(y)
Y
y
f
f
b
v
!
u
X pY (y)2 X
X
1u
2
≤ t2`
pF (f )
pf (X)|Y (b|y) − pUB (b)
2
q
(y)
Y
y
f
b
v
!
u
X pY (y)2 X
1u
≤ t2`
pX|Y (x|y)2
2
q
(y)
Y
y
x∈X
v 

u
u
2
X
pXY (x, y) 
1u
= t2` 
2
qY (y)
(x,y)∈X ×Y

1 1
= 2− 2 (H2 (pXY |qY )−`) ,
2
where the first inequality follows from (A.2), the second inequality follows from utilizing
√
the Jensen’s inequality for concave function ·, the third inequality follows from (A.4)
and the second equality follows from the definition of H2 (pXY |qY ). Since qY is arbitrary,
the above equation results in
X

pF (f ) pf (X)Y − pUB pY

f

TV

1 1
≤ 2− 2 (H2 (pXY |Y )−`) .
2

Now we could utilize Theorem 40 to obtain another bound in terms of the smoothed
conditional collision entropy. Let  > 0 be an arbitrary real number and X ∈ X and Y ∈ Y
be two random variables with joint probability distribution pXY . Let pXY ∈ B (pXY ) be
the probability distribution such that
H2 (pXY |Y ) = H2 (pXY |Y ),
and f : X → {1, 2, 3, . . . , 2` } be the mapping of Theorem 40 satisfying
pf (X)Y − pUB pY

TV

1 1
1 1 
≤ 2− 2 (H2 (pXY |Y )−`) = 2− 2 (H2 (pXY |Y )−`) .
2
2
65

(A.5)

Thus we have
pf (X)Y − pUB pY

TV

≤ pf (X)Y − pf (X)Y

TV

+ pf (X)Y − pUB pY

TV

+ pUB pY − pUB pY

TV

1 1 
≤ 2 + 2− 2 (H2 (pXY |Y )−`) ,
2
where the first inequality results from the triangular inequality for the total variation
distance an the second inequality follows from (A.5) and the fact that total variation does
not increase under deterministic functions. Hence the following corollary of Theorem 40
is concluded.
Corollary 42. For random variables X ∈ X and Y ∈ Y with joint distribution pXY and
 > 0 there exist a mapping f : X → {1, 2, . . . . , 2` } such that
pf (X)Y − pUB pY

TV

1 1 
≤ 2 + 2− 2 (H2 (pXY |Y )−`) ,
2

where pUB is the uniform distribution on {1, 2, . . . , 2` }.
Next we utilize Corollary 42 in combination with Remark 39 to conclude that for the
random sequence (X n , Y n ) drawn i.i.d. from pXY there exists a mapping that extracts
nH(X|Y ) bits from X n with desired precision given that n is sufficiently large. This
observation is presented in the following lemma.
Lemma 43. Let X n ∈ X n and Y n ∈ Y n be two correlated random sequences drawn
i.i.d. from joint probability distribution pX,Y . Let Q(n) be a random variable uniformly
distributed on {1, 2, . . . , 2Rn } where R < H(X|Y ) is a real number, then there exist mappings Bn : X n → {1, 2, . . . , 2Rn } such that
lim kpBn (X n )Y n − pQ(n) pY n kT V = 0.

n→∞

Proof. For arbitrary δ > 0 choose some positive number  such that  < δ/2 and  <
H(X|Y ) − R. Let Bn be the mapping of Corollary 42 satisfying
1 1 
n
kpBn (X n )Y n − pQ(n) pY n kT V ≤ 2 + 2− 2 (H2 (pX n Y n |Y )−nR) .
2
66

thus by using Remark 39, for sufficiently large n we have
1 n
kpBn (X n )Y n − pQ(n) pY n kT V ≤ 2 + 2− 2 (H(X|Y )−R−) .
2
Since  < δ/2 and H(X|Y ) − R −  > 0 there exists a natural number n0 such that for all
n

n > n0 , 2 + 12 2− 2 (H(X|Y )−R−) ≤ δ hence for sufficiently large n,
kpBn (X n )Y n − pQ(n) pY n kT V ≤ δ.

Appendix B. Proof of Lemma 36
Let us minimize the expression (E[X] − w2 )2 /Var[X] over all random variables X that
satisfy m ≤ X ≤ m and E[X] ≥ w1 :








 (µ − w2 )2 
(E[X] − w2 )2
(E[X] − w2 )2 


min
= min
= min 
min
w1 ≤µ≤m
w1 ≤µ≤m  max Var[X] 
m≤X≤m
m≤X≤m
Var[X]
Var[X]
E[X]≥w1

m≤X≤m
E[X]=µ

E[X]=µ







(µ − w2 )2
.
= min 
w1 ≤µ≤m  −µ2 + max E[X 2 ] 

(B.1)

m≤X≤m
E[X]=µ

We claim that
max E[X 2 ] = (m − µ)(µ − m) + µ2 .

m≤X≤m
E[X]=µ

(B.2)

Observe that if X ∗ is the following binary random variable
P[X ∗ = m] =

m−µ
,
m−m

P[X ∗ = m] =

µ−m
m−m

(B.3)

we have E[X ∗ ] = µ and E[(X ∗ )2 ] = (m − µ)(µ − m) + µ2 . As a result,
max E[X 2 ] ≥ (m − µ)(µ − m) + µ2 .

m≤X≤m
E[X]=µ

67

(B.4)

On the other hand, the function f (x) = x2 is convex and lies below the line that connects
the two points (m, m2 ) and (m, m2 ) for any x ∈ [m, m], i.e.,
x2 ≤ m2 + (x − m)(m + m),

∀x ∈ [m, m2 ].

Thus,
E[X 2 ] ≤ m2 + (E[X] − m)(m + m) = (m − µ)(µ − m) + µ2 .
Thus, equation (B.2) holds. As a result, equation (B.1) becomes
(E[X] − w2 )2
= min g(µ),
w1 ≤µ≤m
m≤X≤m
Var[X]
min

(B.5)

E[X]≥w1

where
(µ − w2 )2
g(µ) =
.
(m − µ)(µ − m)
Note that the function g(·) is increasing for any µ satisfying m ≤ w2 ≤ µ ≤ m as
dg(µ)
(µ − w2 ) [(m − µ)(µ + w2 − 2m) + (µ − m)(µ − w2 )]
=
≥ 0.
dµ
(m − µ)2 (µ − m)2
Since w2 ≤ w1 , this would then imply that the minimum on the right hand side of (B.5)
is obtained at µ = w1 . This will complete the proof.
Acknowledgements
The authors would like to thank Yury Polyanskiy for pointing out the connection with
the ChapmanRobbins bound. The authors also want to thank the anonymous reviewers for their helpful suggestions. This work was supported by the Sharif University of
Technology under Grant QB950607.
References
References
Adler, I., 2013. The equivalence of linear programs and zero-sum games. International
Journal of Game Theory 42 (1), 165–177.
68

Budinich, M., Fortnow, L., 2011. Repeated matching pennies with limited randomness.
In: Proceedings of the 12th ACM conference on Electronic commerce. ACM, ACM, pp.
111–118.
Cicalese, F., Gargano, L., Vaccaro, U., 2017. How to find a joint probability distribution
of minimum entropy (almost), given the marginals. arXiv preprint arXiv:1701.05243.
Cover, T. M., Thomas, J. A., 2012. Elements of information theory. John Wiley and Sons.
Dantzig, G. B., 1951. A proof of the equivalence of the programming problem and the
game problem. Activity analysis of production and allocation (13), 330–338.
El Gamal, A., Kim, Y.-H., 2011. Network information theory. Cambridge university press.
Fang, S.-C., Rajasekera, J. R., Tsao, H.-S. J., 2012. Entropy optimization and mathematical programming. Vol. 8. Springer Science and Business Media.
Gossner, O., Tomala, T., 2007. Secret correlation in repeated games with imperfect monitoring. Mathematics of Operations Research 32 (2), 413–424.
Gossner, O., Vieille, N., 2002. How to play with a biased coin? Games and Economic
Behavior 41 (2), 206–226.
Han, T. S., 2003. Information-spectrum methods in information theory. Vol. 50. Springer
-Verlag Berlin Heidelberg.
Hubáček, P., Naor, M., Ullman, J., 2016. When can limited randomness be used in
repeated games? Theory of Computing Systems 59 (4), 722–746.
Kapur, J. N., Baciu, G., Kesavan, H. K., 1995. The minmax information measure. International Journal of Systems Science 26 (1), 1–12.
Kocaoglu, M., Dimakis, A. G., Vishwanath, S., Hassibi, B., 2016. Entropic causal inference. arXiv preprint arXiv:1611.04035.

69

Kovacevic, M., Stanojevic, I., Senk, V., 2012. On the hardness of entropy minimization
and related problems. In: Information Theory Workshop (ITW), 2012 IEEE. IEEE,
IEEE, pp. 512–516.
Kovaevi, M., Stanojevi, I., enk, V., 2015. On the entropy of couplings. Information and
Computation 242, 369–382.
Narahari, Y., 2014. Game Theory and Mechanism Design. Vol. 4. World Scientific.
Nash, J. F., 1950. Equilibrium points in n-person games. Proceedings of the national
academy of sciences 36 (1), 48–49.
Neyman, A., Okada, D., 2000. Repeated games with bounded entropy. Games and Economic Behavior 30 (2), 228–247.
Nielsen, M. A., 2002. An introduction to majorization and its application to quantum
mechanics. Lecture Notes, Department of physics, University of Queensland, Australia.
Renner, R., 2008. Security of quantum key distribution. International Journal of Quantum
Information 06 (01), 1–127.
URL http://www.worldscientific.com/doi/abs/10.1142/S0219749908003256
Shor, P. W., 2004. Equivalence of additivity questions in quantum information theory.
Communications in Mathematical Physics 246 (3), 453–472.
Slepian, D., Wolf, J., 1973. Noiseless coding of correlated information sources. IEEE
Transactions on information Theory 19 (4), 471–480.
Srikanth, M., Kesavan, H., Roe, P., 2003. Computation of the MinMax measure. Springer,
pp. 239–251.
Watanabe, S., 1981. Pattern recognition as a quest for minimum entropy. Pattern Recognition 13 (5), 381–387.

70

