Persuasion with limited communication capacity∗
Maël Le Treust† and Tristan Tomala‡

arXiv:1711.04474v3 [] 9 Jan 2018

January 10, 2018

Abstract
We consider a Bayesian persuasion problem where the persuader and the decision
maker communicate through an imperfect channel which has a fixed and limited
number of messages and is subject to exogenous noise. Imperfect communication
entails a loss of payoff for the persuader. We establish an upper bound on the
payoffs the persuader can secure by communicating through the channel. We also
show that the bound is tight: if the persuasion problem consists of a large number
of independent copies of the same base problem, then the persuader can achieve this
bound arbitrarily closely by using strategies which tie all the problems together. We
characterize this optimal payoff as a function of the information-theoretic capacity
of the communication channel.

JEL Classification Numbers: C72, D82, D83.

∗

The authors thank James Best, Olivier Gossner, Frédéric Koessler, Marie Laclau, Daniel Martin,
Ludovic Renou, Thomas Rivera, Jakub Steiner, Colin Stewart for stimulating discussions and comments.
We also thank participants of: the 6th workshop on Stochastic Methods in Game Theory, Erice May
2017; the 13th European Meeting on Game Theory (SING13), Paris July 2017; the XXVI Colloque
Gretsi, Juan-Les-Pins, September 2017; the 10th Transatlantic Theory Workshop, Paris September 2017;
the 55th Allerton Conference, Monticello, Illinois, October 2017. We thank the Institute Henri Poincaré
for hosting numerous research meetings.
†
ETIS UMR 8051, Université Paris Seine, Université Cergy-Pontoise, ENSEA, CNRS, F-95000, Cergy,
France; mael.le-treust@ensea.fr; sites.google.com/site/maelletreust/. This research has been conducted as
part of the project Labex MME-DII (ANR11-LBX-0023-01).
‡
HEC Paris and GREGHEC, 1 rue de la Libération, 78351 Jouy-en-Josas, France; tomala@hec.fr;
studies2.hec.fr/jahia/Jahia/tomala. Tristan Tomala gratefully acknowledges the support the HEC foundation and ANR/Investissements d’Avenir under grant ANR-11-IDEX-0003/Labex Ecodec/ANR-11-LABX0047.

1

1

Introduction
In modern internet societies, pieces of information are repeatedly and continuously

disclosed by informed agents to decision makers. Information transmission is aﬀected by
at least two sources of friction. First, the sender and the receiver of a given message
may have non-aligned incentives, in which case the sender might be unwilling to transmit
truthful information. Second, communication between agents is often imperfect. The
sender and the receiver may have time constraints to write or read messages, so that the
sender has to summarize his arguments and cannot convey all the details. Further, there
might be discrepancies between the informational content of a message that is intended
by the sender and the one understood by the receiver, for instance if the mother tongue’s
of the sender and of the receiver are diﬀerent, there are possible translation errors (see
Blume, Board, and Kawamura, 2007). Also, messages travelling in a network of computers
might be subject to random shocks, internal errors or protocol failures. Studying the eﬀect
of noise in communication channels is the starting point of information theory (Shannon,
1948).
How does imperfect communication reduce the possibilities of persuasion in a senderreceiver interaction and how the sender should optimally disclose information when facing
limits on its capacity of communication?

In this paper, we consider a sender and a receiver who communicate over an imperfect
channel and are engaged in a series of n ≥ 1 persuasion problems. The sender observes n
independent and identically distributed pieces of information and sends k ≥ 1 messages
to the receiver. Messages are sent through a channel which consists of two ﬁnite sets X, Y
of respectively inputs and outputs messages and of a transition probability Q from X
to Y : when the sender chooses input message x, the receiver receives output message y
with probability Q(y|x). Upon receiving k output messages from the channel, the receiver
chooses n actions, one for each problem. Payoﬀs are additively separable across persuasion
problems. We assume that the sender is able to commit to a disclosure strategy which
maps sequences of pieces of information to sequences of input messages.
2

We analyze the optimal average payoﬀ secured by the sender by committing to a
strategy. We give an upper bound on this optimal payoﬀ and show that this bound
is approximately achieved when the numbers n and k grow large with ﬁxed ratio n/k.
We call this payoﬀ the value of the optimal splitting problem with information constraint,
which represents the best payoﬀ that the sender can achieve by sending a message, subject
to the constraint that the mutual information between the state and the message is no
more than the capacity of the channel. We show that this value is given by the concave
hull of the payoﬀ function of the sender, subject to a constraint on the entropy of posterior
beliefs. This is also the concave hull of a modiﬁed payoﬀ function, where the sender pays
a cost proportional to the mutual information between the state and the message.
Motivating example. Consider an innovating ﬁrm who has several projects to be
ﬁnanced by investors. The board of investors audits the ﬁrm who is given a limited
amount of time to present all the projects. How to best organize the arguments in order
to get a maximum number of projects approved?
To be speciﬁc, let’s assume that all projects are ex-ante identical and equally likely to
be of good or bad quality. When a project is approved, it yields a positive return of +1
to the investors if it is good, and a negative return of −7 if it is bad; rejecting a project
yields a payoﬀ of 0. The objective of the ﬁrm is to get a maximum number of projects
approved. This example has the same structure as the main example of Kamenica and
Gentzkow (2011), revisited by Bergemann and Morris (2017).
Suppose that the ﬁrm is able to commit to an information disclosure policy à la
Kamenica and Gentzkow (2011) and has unlimited time to present arguments. In order
to invest, the board of investors needs to be persuaded that the project is good with
probability at least 7/8. Thus for each project, the ﬁrm would optimally draw a good
message g or a bad message b with the following probabilities:

P(g | project is good) = 1,

P(g | project is bad) = 1/7.

3

This way, the belief that the project is good upon receiving the good message is:

P(project is good | g) = 7/8,

and the project is accepted with probability 4/7 (details are in Section 3).
Now, suppose that the auditing board gives the ﬁrm only half the time it would require
to talk about all projects. Namely, there is an even number n of projects, but the ﬁrm
has to present n/2 messages. What is the optimal information disclosure policy of the
ﬁrm?
A simple strategy the ﬁrm can adopt is to select half of the projects, focus on them,
and communicate optimally for each of them. With this strategy, half of the projects
are accepted with probability 4/7 each, so in expectation the average number of accepted
projects is 2/7. This is not optimal, a better strategy would be to pair projects by two
and to draw one message g, b for each pair in the following way.

P(g | both projects are good) = 1,

P(g | both projects are bad) = 0,

P(g | only one project is good) = 1/6.
The total probability of g is 1/3 and upon observing this message, the beliefs about quality
are:
P(both projects are good | g) = 6/8,
P(only project 1 is good | g) = P(only project 2 is good | g) = 1/8.
Therefore each project is believed to be good with probability 7/8 and both projects are
accepted when g is received. Thus, the expected average number of accepted projects is
1/3 > 2/7. We show in Section 3 that this is the optimal way of pairing projects two by
two. Is it possible to ﬁnd a more complex strategy which improves the payoﬀ further?
Our main result Theorem 4.3 gives an upper bound on the expected average number
of accepted projects, when the number of messages is half the number of projects. The
upper bound is tight: the optimal value approaches it as the number of project increases.
4

On this example, the upper bound is λ∗ where (λ∗ , p∗ ) is the unique solution in [0, 1]×[0, 21 ]
of the system of equations,
1
7
= λ∗ + (1 − λ∗ )p∗ ,
2
8

 
1
7
∗
+ (1 − λ∗ )H(p∗ ),
=λ H
2
8

where H(p) = −p log(p) − (1 − p) log(1 − p) is the entropy function. The ﬁrst equation is
Bayes plausibility (Kamenica and Gentzkow, 2011) coming from Bayes’ rule, saying that
the expected posterior belief is the prior belief. The second equation requires that the
expected entropy of the posterior is 12 , which means that the mutual information between
the quality of the project and the message sent to the receiver is equal to the number of
messages per project that the ﬁrm can transmit.
Numerically λ∗ ≈ 0.519 <

4
7

≈ 0.571. So for large n, the sender can achieve a payoﬀ

better than 1/3 but bounded away from the payoﬀ obtained with perfect communication.

Related literature. We now describe the relationships between our contribution and
the literature. This paper is at the junction of Bayesian persuasion and information
theory.
The traditional game theoretic approach to strategic information disclosure assumes
perfect communication and analyzes in isolation the problem of sending a single message.
These are the well-known sender-receiver games where an informed player, the sender,
communicates once with a receiver who takes an action. In the cheap talk version of
this game, the message sent by the sender is costless and unveriﬁable, see for instance the
seminal paper of Crawford and Sobel (1982). In the Bayesian persuasion game (Kamenica
and Gentzkow, 2011), the sender chooses veriﬁably an information disclosure device, prior
to learning his information. This model can be interpreted in several ways: (i) the sender
has full commitment power and displays publicly the mechanism which links states and
messages, (ii) the sender is not informed of the state parameter but is able to choose
a statistical experiment whose distribution depends on the state, (iii) the sender is an
information designer (Bergemann and Morris, 2016, 2017; Taneva, 2016) who chooses the
5

information or signalling structure which will release information to the decision maker.
In parallel, information theory considers agents with perfectly aligned interests and
analyzes the rate of information transmission over time. The sender observes an information flow, that is a stochastic process, and sends messages to the receiver over an
imperfect channel represented by a transition probability from input to output messages.
Truthful information transmission is the common goal of the sender and the receiver. The
rate of information transmission is the average number of correct guesses made by the
receiver over time. Shannon’s theory (Shannon, 1948, 1959) determines whether a source
of information can be transmitted over the channel with arbitrarily small probability of
error, and shows that the rate of the source of information has to be smaller than the
capacity of the channel deﬁned as the maximal mutual information between input and
output messages.

Our model of persuasion has two essential features. The sender and the receiver are
engaged in a large number of identical copies of the same game and communication is
restricted to an imperfect channel. As Kamenica and Gentzkow (2011), we consider the
payoﬀ obtained by the sender as a function of the belief of the receiver, when the receiver
takes an optimal action given his belief.
With unrestricted communication, that is on a perfect channel with large set of inputs,
the optimal payoﬀ for the sender is given by the concave hull of this function. Then,
solving any number of identical games amounts to solving each copy separately.
With a single copy, the game of persuasion with a noisy channel is studied by Tsakas
and Tsakas (2017) who prove the existence of optimal solutions and show monotonicity of
the sender’s payoﬀ with respect to the noise of the channel. We give a detailed example
in section 3.2.
Considering many copies of the base game and restricted communication, we show that
linking independent problems together yields a better payoﬀ to the sender: the optimal
strategy correlates all messages with the state parameters of all problems. In this respect,
our work bears some similarity with Jackson and Sonnenschein (2007), who showed that

6

a mechanism designer could achieve more outcomes in an incentive compatible manner
by linking many identical problems together.
The optimal payoﬀ that we characterize is related to models where the cost of information is measured by mutual information. Such measurements of information costs
have been introduced in the literature on rational inattention by Sims (2003), (see e.g.
Martin, 2017, for a strategic context). Matejka and McKay (2015) and Steiner, Stewart,
and Matejka (2017) consider models where mutual information is either a direct cost paid
by the agent, or where the agent is constrained to extract less information than some
capacity. In the context of persuasion, Gentzkow and Kamenica (2014) consider a model
where the sender gets his payoﬀ from the game, minus a cost which is proportional to
the mutual information between the state and the message. With Lagrangian methods,
we ﬁnd that the value of our optimal splitting problem with information constraint is
the concave hull of the payoﬀ function, net of such an information cost. Diﬀerently from
those papers, the mutual information is not a primitive of our model. Our ﬁnding is that
the noise and limitations in communication induce a shadow cost measured by the mutual
information.
Entropy and mutual information appear endogenously in several papers on repeated
games (Gossner and Tomala, 2006, 2007; Gossner and Vieille, 2002; Neyman and Okada,
1999, 2000). A related paper is Gossner, Hernández, and Neyman (2006), henceforth
GHN, who also consider a sender-receiver game. In GHN, the sender and the receiver play
an inﬁnitely repeated game with common interests: both the sender and the receiver want
to choose the action that matches the state. The sender knows the inﬁnite sequence of
states and can communicate with the receiver only through his actions. GHN characterize
the best average payoﬀ that the sender (and the receiver) can achieve. Their solution
resembles ours: the optimal value is the payoﬀ obtained when the sender can send a
direct message to the receiver, subject to an information constraint.
There are important diﬀerences with our work. First, GHN study a cheap talk game
with common interests. By contrast, we do not assume common interests and we assume
commitment power for the sender. Second, GHN is truly a repeated game model: at any

7

given time t both players choose actions and the information of the receiver at this time
consists of past actions. In our case, the sender knows a ﬁnite sequence of states, chooses
a ﬁnite sequence of input messages, the receiver observes the ﬁnite sequence of output
messages and chooses a sequence of actions. This is why, rather than seeing our model as
a repeated game of persuasion, we view it as a spatial model with identical copies of the
same problem co-existing at the same time. This also explains why the number of copies
n need not be equal to the number of messages k that the sender is able to input into
the channel. Our result characterizes the optimal payoﬀ as a function of the ratio of the
number n of pieces of information to the number k of messages. In particular, this allows
to analyze cases where the channel is perfect (i.e. not subject to random noise) but with
limited input size: there are fewer messages than states or actions.
Cheap talk with a noisy channel has been studied by Blume, Board, and Kawamura
(2007) who show that the presence of noise is possibly welfare improving. Such a phenomenon cannot happen in the persuasion context as the sender could commit to replicate
the noise. Relatedly, Hernández and von Stengel (2014) consider a sender-receiver game
with common interests over an imperfect channel. In that paper, there is only one state
known by the sender and one action taken by the receiver, while the channel can be used
a ﬁxed number of times. Hernández and von Stengel (2014) characterize all the Nash
equilibria of this game and study the diﬀerences with Shannon’s coding methods. Again,
we do not assume common interests and assume commitment power for the sender. More
importantly, our focus is diﬀerent and more in line with GHN: we do not treat a single
persuasion problem but a large sequence of them and use information theory to study the
asymptotics of the problem.
Our work is also related to some information theoretic literature. Following GHN,
a line of papers study empirical coordination between a sender and a receiver (Cuﬀ,
Permuter, and Cover, 2010), by communicating over a perfect (Cuﬀ and Zhao, 2011)
or imperfect channel (Le Treust, 2017). Those papers implicitly assume common interest
between the sender and the receiver and characterize the empirical distributions of (states,
messages, actions) which are achievable, given the information structure and the noisy

8

channel. These characterizations are related to the information theoretical problems of
source coding (Wyner and Ziv, 1976) and channel coding (Gelfand and Pinsker, 1980)
with partial information about the state (Le Treust and Bloch, 2016), whose solution
is still not available for some simple cases. In a recent paper, Akyol, Langbort, and
Başar (2017) have considered the problem of Bayesian persuasion for Gaussian state and
channel. The authors calculate explicitly the optimal strategies for the quadratic cost
functions considered by Crawford and Sobel (1982) and prove that they are linear.
The closest paper in this literature is Le Treust and Tomala (2016) where we have
studied the empirical coordination between a persuader and a decision maker. In this
proceeding, we have characterized the limit set of empirical distributions of states, messages and actions induced by approximate equilibria of the game with n copies and n
messages, as n tends to inﬁnity. There are several new contributions in the current paper. First, considering a large number of identical copies of a base persuasion game, we
compare precisely the solution of the large game with the solution of the base game, with
and without noisy channel. Second, rather than looking at approximate equilibria, we
characterize the best payoﬀ the sender can secure, given that the receiver chooses actions
which are optimal for his Bayesian belief on the sequence of states. Third, to achieve
this characterization, we introduce the optimal splitting problem under information constraint. The detailed study of this problem allows us to construct a strategy of the sender
such that the best response of the receiver induces the target payoﬀ. Fourth, the concaviﬁcation under information constraint is easy to interpret and oﬀers a nice interpretation
of the mutual information as an information cost.

The paper is organized as follows. The model is described in section 2. In section
3, we provide benchmarks by studying examples where we calculate the solution of the
single persuasion game with and without a noisy channel. In section 4, we consider large
copies of identical problems, state our main result, and revisit the examples. In section
5, we study the concaviﬁcation under information constraint. Section 6 discusses the
cardinality of messages sets. Proofs are in the Appendix.

9

2

Model

2.1

Bayesian persuasion with restricted communication

We consider a Bayesian persuasion problem between two players, a sender (S) and a
receiver (R). There is a ﬁnite state space Ω with a common prior µ ∈ ∆(Ω) and a ﬁnite
set of actions A. Player i = S, R cares about the state ω and the action taken a and has
payoﬀ ui (ω, a).
In the persuasion game with unrestricted communication, the sender chooses a signaling structure, consisting of a ﬁnite set of messages M and a transition probability
σ : Ω → ∆(M). Once chosen, the signaling structure is known to the receiver. Then,
a state ω is drawn with probability µ(ω), a message m ∈ M is drawn with probability
σ(m|ω), the message is observed by the receiver. The receiver then chooses an action
a ∈ A.
In concrete settings, communication possibilities may be restricted, for instance messages may be subject to exogenous noise, or the number of possible messages may be
smaller than the number of states or actions. We represent an imperfect communication
channel by a transition probability Q : X → ∆(Y ), where X, Y are ﬁxed ﬁnite sets of
messages (words, letters or abstract symbols) and ∆(Y ) is the set of probability distributions over Y . The set X represents the possible messages that the sender can input into
the channel, the set Y is the set of messages that the receiver can possibly receive. When
the sender chooses message x, message y is received with probability Q(y|x).
Example 2.1. Binary symmetric channel. As an example, take binary sets of messages
X = {x0 , x1 }, Y = {y0 , y1 } and assume that the channel has a noise level ε ∈ [0, 21 ], that
is Q(yj |xi ) = ε for j 6= i, see Figure 1. The generic case is ε ∈ (0, 12 ) where the label
of the message (0 or 1) is changed with positive probability, but observing a label 1 is
still more likely when the input label is 1. When ε = 12 , the distribution of the output
message is independent from the input message, so the channel completely disrupts the
communication.
A special case is the binary perfect channel when ε = 0: identifying together the sets
10

1−ε

x0

b

y0

b

y1

b

ε
ε
x1
b

1−ε
Figure 1: Binary symmetric channel.

X and Y , an input message x is received with certainty. Communication is then restricted
only by the number of available messages, i.e. the cardinality of X.
In the persuasion game with communication restricted by the channel, the set of messages is ﬁxed to be X and the sender can only choose a transition probability σ : Ω →
∆(X) which we will refer to as the strategy of the sender. Once chosen, it is known by
the receiver. Then, in state ω, an input message x is drawn with probability σ(x|ω), an
output message y is drawn from the channel with probability Q(y|x) and announced to
the receiver, who chooses an action a.
Our general objective is to characterize the best payoﬀ that the sender can secure
in a robust way. That is, what is the best payoﬀ the sender can secure, for all optimal
strategies of the receiver.
A strategy of the receiver is a mapping τ : Y → A. Knowing σ, the receiver chooses
a best-reply τ which maximizes the expected payoﬀ. That is, for each1 y,

τ (y) ∈ arg max
a∈A

X

ω,x

µ(ω)σ(x|ω)Q(y|x)uR(ω, a).

Denote BR(σ) the set of best replies of the receiver to the strategy σ.
Definition 2.2. The optimal robust payoﬀ of the sender is,
US∗ (µ, Q) = sup min
σ

τ ∈BR(σ)

X

ω,x,y

µ(ω)σ(x|ω)Q(y|x)uS (ω, τ (y)).

This is the best payoﬀ that the sender can achieve, provided that the receiver takes
1

Since once chosen, σ is fixed and known, requiring optimality for all y’s, or for all y’s in the support,
does not affect the solutions.

11

any optimal strategy. In case the receiver is indiﬀerent between several actions, we want
this quantity to be robust to the exact speciﬁcation of the optimal action. Thus, we
assume that if there are several optimal strategies, the receiver chooses the one which is
the least preferred by the sender.
Note that this quantity depends on the prior and on the communication channel.

2.2

Linking independent problems

We consider now persuasion problems composed of a large number of independent
identical copies of the same base problem. Communication is still restricted by the channel
and by the number of times it can be used.
Precisely, the state space is now Ωn for some positive integer n, so that a state is a
sequence ω n = (ω1 , . . . , ωn ). We assume that the (ωt )’s are independently and identically
Q
distributed, so that the prior probability µn on Ωn is given by µn (ω n ) = nt=1 µ(ωt ). The
receiver chooses a sequence of actions an = (a1 , . . . , an ) and the payoﬀ for player i = S, R

is,
ūi (ω n , an ) =

1 Xn
ui (ωt , at ).
t=1
n

The communication resource available to the sender is the repeated use of the channel
which is assumed to be memoryless. Precisely, the sender can choose a sequence of
k messages xk = (x1 , . . . , xk ) to input into the channel, and the receiver will observe
Q
y k = (y1 , . . . , yk ) with probability Qk (y k |xk ) = kt=1 Q(yt |xt ).

A strategy of the sender is now a mapping σ : Ωn → ∆(X k ), which is known by the

receiver, once chosen. A strategy of the receiver is τ : Y k → An . The optimal robust
payoﬀ of the sender in this problem is denoted:
US∗ (µn , Qk ) = sup min
σ

τ ∈BR(σ)

X

ω n ,xk ,y k

µn (ω n )σ(xk |ω n )Qk (y k |xk )ūS (ω n , τ (y k )).

Our main goal is to provide a characterization of the optimal robust payoﬀ for large
problems, that is when n and k grow.

12

3

Benchmarks and examples
Before stating our main results, we recall as a benchmark what happens with unre-

stricted communication and examine the case of a single problem on a communication
channel.

3.1

Persuasion with unrestricted communication

Take a simple persuasion problem with state space Ω, prior µ, action set A, payoﬀs
ui , assume that the receiver can choose messages in an arbitrarily large ﬁnite set M, and
that messages are perfectly observed by the receiver.
The solution to this game is well-known (Kamenica and Gentzkow, 2011). Given
a strategy σ : Ω → ∆(M), message m is received with total probability, Pσ (m) =
P
ω µ(ω)σ(m|ω) and the posterior belief νσ (·|m) upon receiving message m is given by

νσ (ω|m) = µ(ω)σ(m|ω)
(for all messages m such that Pσ (m) > 0). Bayes’ rule dictates that
Pσ (m)
P
µ = m Pσ (m)νσ (·|m).

From the splitting lemma (Aumann and Maschler, 1995) or Bayes plausibility (Ka-

menica and Gentzkow, 2011), each decomposition of the prior into a convex combination
P
of posteriors µ = m λm νm is induced by the following strategy σ(m|ω) = λm νm (ω)/µ(ω).
Such a convex combination will be henceforth referred to as a splitting of µ. There is

a one-to-one correspondance between the strategies of the sender and the splittings of the
prior. From now on, we will use letter µ to denote the prior belief and letter ν to denote
a generic belief or posterior of the receiver. With a slight abuse of notation, we identify
P
the convex combination µ = m λm νm with the distribution of beliefs where the receiver
has belief νm with probability λm .

The optimal robust payoﬀ of the sender is then easily found by the concaviﬁcation
method. For each belief ν ∈ ∆(Ω), denote A∗ (ν) the set of optimal actions for the
receiver with belief ν,
A∗ (ν) = arg max
a∈A

X

ω

ν(ω)uR(ω, a).

Then, τ is optimal given σ when for each m, the action τ (m) belongs to A∗ (νσ (·|m)). Call

13

the robust payoff US (ν) of the sender at the belief ν, the payoﬀ he gets when the receiver
chooses the optimal action which is worst for S. Denote,

US (ν) = min
∗

a∈A (ν)

X

ω

ν(ω)uS (ω, a).

With the same logic as in Kamenica and Gentzkow (2011), the optimal robust payoﬀ
is the concaviﬁcation of US at µ,

cav US (µ) = sup

nX

m

λm US (νm ) :

X

m

o
λm νm = µ ,

where the supremum is over the set of splittings of the prior: the numbers λm are nonnegative summing up to 1 and νm ∈ ∆(Ω) for each m.
Observe that, contrary to Kamenica and Gentzkow (2011), we assume that in case of
indiﬀerence, the receiver breaks ties in the worst way for the sender. This choice is motivated by robustness since any optimal action is legitimate for the receiver. Although for
generic problems the choice of tie-breaking rule does not change the concaviﬁcation function, in the above formula the supremum might not be reached exactly, but approximated
arbitrarily closely, see Example 3.1.
Example 3.1. Persuading to invest. This example will be running throughout the paper
and revisited in various contexts. The sender is a ﬁrm who persuades the receiver to
invest in a risky project. If the receiver does not invest (action a0 ), the payoﬀ is 0 for
both players. If the receiver invests (action a1 ), the projects has return −7 in the bad
state ω0 and +1 in the good state ω1 . Both states are equally likely. The sender receives
a fee of +1 only if the receiver invests. The payoﬀ table is as follows, the entries are pairs
of payoﬀs for the players i = S, R depending on the state and action.
a0

a1

µ

ω0

(0, 0)

(1, −7)

1
2

ω1

(0, 0)

(1, 1)

1
2

14

The receiver invests for sure only when he holds a belief ν such that ν(ω1 ) > 7/8. If
ν(ω1 ) = 7/8 he is indiﬀerent. Assuming that in case of indiﬀerence he does not invest,
the robust payoﬀ of the sender US (ν) is 1 if ν(ω1 ) > 7/8 and 0 otherwise.
US (ν)
b

1

cav US ( 21 ) =

4
7
b

0

b

1
2

•7
8

1

ν(ω1 )

Figure 2: Concaviﬁcation.

The concaviﬁcation function cav US (ν) is continuous and equal to 78 ν(ω1 ) for ν(ω1 ) ≤

7
8

and 1 otherwise. It is easy to see that it does not depend on the action chosen by the
receiver at ν(ω1 ) = 87 , see Figure 2.
If the receiver would choose a1 at the point of indiﬀerence, then the optimal splitting
for the sender would be,



1 1
,
2 2





 4 1 7
3
= 1, 0 +
,
,
7
7 8 8

where a belief is denoted ν = (ν(ω0 ), ν(ω1 )). This yields a payoﬀ of

4
7

which is the highest

that the sender can achieve given the uniform prior. For any small ε > 0, let’s perturb
the previous splitting a little bit to get,


1 1
,
2 2

which achieves the payoﬀ






3 + 8ε
4
1
7
=
1, 0 +
− ε, + ε ,
7 + 8ε
7 + 8ε 8
8

4
7+8ε

irrespective of the tie-breaking rule. Letting ε tend 0, we

see that the sender achieves a payoﬀ arbitrarily close to 47 . This is indeed the optimal
robust payoﬀ.
15

Note that the tie-breaking rule might be relevant in non-generic cases. To see this,
let’s imagine that we change the payoﬀs of the receiver in order to push the indiﬀerence
point from

7
8

up to 1. In that case, the sender gets a payoﬀ only when ν(ω1 ) = 1 and the

receiver chooses the sender-preferred action. In such a case, the concaviﬁcation depends
on the choice of the sender at the indiﬀerence point.
All examples in the paper will be generic, so that to calculate the concaviﬁcation, it
is without loss to assume that the receiver chooses the action preferred by the sender at
indiﬀerence points.
Remark 3.2. Copies of independent problems with unrestricted communication. With
unrestricted communication, the optimal robust payoﬀ does not change if we take identical
copies of the same persuasion problem. Indeed, the receiver treats each copy as a separate
problem and takes an optimal action. Therefore, the sender cannot achieve more than
cav US (µ) for each copy, and he will thus also handle the problems separately.

3.2

Persuasion over the channel for a single problem

We consider again a simple persuasion problem but now, the set of messages for the
sender is X, the set of messages for the receiver is Y and messages are ﬁltered by the
channel Q : X → ∆(Y ).
Also in this context, any strategy σ : Ω → ∆(X) translates into a splitting of the prior
into posteriors which writes,
µ=

X

y∈Y

λy νy ,

where λy is the total probability of y and νy is the posterior belief, conditional on y.
Obviously, the number of diﬀerent posteriors is at most the cardinality of Y . Such a
splitting is feasible if and only if there exists σ : Ω → ∆(X) such that,

λy =

X

ω,x

µ(ω)σ(x|ω)Q(y|x)

and
νy (ω) = µ(ω)

X

x

σ(x|ω)Q(y|x)/λy .

16

The channel imposes severe restrictions on the set of feasible splittings which is studied
in Tsakas and Tsakas (2017). Consider the following example.
Example 3.3. Binary symmetric channel. Consider the binary symmetric channel described in Example 2.1. Let a strategy σ be parametrized by σ(x0 |ω0 ) = 1 − α and
σ(x1 |ω1 ) = 1 − β, see Figure 3.
µ(ω0 )

b

ω1
b

1−α

ω0

b

b

α
β

µ(ω1 )

b

1−β

b

x1
b

1−ε

x0

b

y0

b

y1

ε
ε
1−ε

Figure 3: Strategy on the binary symmetric channel.

Then,
Pσ (y1 |ω0 ) = α(1 − ε) + (1 − α)ε := α ⋆ ε,
Pσ (y0 |ω1 ) = β(1 − ε) + (1 − β)ε := β ⋆ ε.
It follows that Pσ (y1 ) = µ(ω0)α ⋆ ε + µ(ω1 )(1 − β ⋆ ε) and from Bayes’ rule,

Pσ (ω1 |y1 ) =

µ(ω1 )(1 − β ⋆ ε)
,
µ(ω0 )α ⋆ ε + µ(ω1)(1 − β ⋆ ε)

Pσ (ω1 |y0 ) =

µ(ω1)β ⋆ ε
.
µ(ω0 )(1 − α ⋆ ε) + µ(ω1 )β ⋆ ε

It is easy to see that since α ⋆ ε ∈ [ε, 1 − ε], all the numbers (Pσ (y1 |ω0 ), Pσ (y0 |ω1 ), Pσ (y0 ),
Pσ (ω1 |y1 ), Pσ (ω1 |y0 )) belong to the interval [ε, 1 − ε]. Let’s characterize the feasible
splittings.
A pair of posteriors (ν0 , ν1 ) is feasible if there exists a number λ ∈ [0, 1] such that,

(µ(ω0 ), µ(ω1 )) = λ(ν0 (ω0 ), ν0 (ω1 )) + (1 − λ)(ν1 (ω0 ), ν1 (ω1 )).

17

Lemma 3.4. A pair of posteriors (ν0 , ν1 ) is feasible if and only if ν1 = ν0 = µ or,

ε≤

ν0 (ω1 )(ν1 (ω1 ) − µ(ω1 ))
≤1−ε
µ(ω1 )(ν1 (ω1 ) − ν0 (ω1 ))

and
ε≤

(1 − ν0 (ω1 ))(µ(ω1) − ν0 (ω1 ))
≤ 1 − ε.
(1 − µ(ω1 ))(ν1 (ω1 ) − ν0 (ω1 ))

The proof is in the Appendix (A.1.1). As an illustration, take the uniform prior ( 12 , 12 )
and a level of noise ε = 14 . The feasible posteriors are shown by the colored regions (green)
on Figure 4.
ν0 (ω1 )
1

3
4

1
2

1
4

0

1
4

1
2

3
4

1

ν1 (ω1 )

Figure 4: Feasible posteriors.

Example 3.5. Persuading to invest over a noisy channel. Consider the persuasion problem given in Example 3.1 and assume that communication is ﬁltered through the binary
symmetric channel with noise ε =

1
4

studied in Example 3.3. From the previous discus-

sion, it is impossible to induce beliefs with ν(ω1 ) > 43 . Therefore, the receiver will never
be conﬁdent enough to invest and the payoﬀ is 0 for the sender.
This example demonstrates how exogenous noise in the communication limits the persuasion possibilities. Now, we consider the motivating example given in the introduction
18

where the channel is noiseless and contains few messages, that is less than the number of
states or the number of actions.
Example 3.6. Persuading to invest with few words. Consider two independent copies of
the persuasion problem given in Example 3.1. The state space is {ω0 , ω1 } × {ω0 , ω1 }, with
uniform prior. The receiver has to choose two actions, one for each problem, so that the
action set is {a0 , a1 } × {a0 , a1 }. The payoﬀ for each player is the average of payoﬀs in the
two problems. With perfect communication, the sender can achieve
so

4
7

4
7

in each problem,

on average.

Now, suppose that the channel is perfect but has only two messages |X| = |Y | = 2.
The sender is able to send a perfect message but only from a binary set, whereas there
are four states and four actions. How much can he achieve?
Achieving an average payoﬀ of

2
7

is easy. The sender focuses on the ﬁrst state and

communicates optimally about it, revealing nothing about the second state. This yields
a payoﬀ of

4
7

for the ﬁrst problem, and 0 for the second one.

Claim 3.7. The optimal robust payoff is


1 1 1 1
, , ,
4 4 4 4



1
3

for this example. It is achieved by the splitting





2 6 5 5
1 1 6
1
=
0, , ,
,
, , ,0 +
3 16 16 16
3
8 8 8

which corresponds to the following strategy,
1
σ(x1 |ω0 , ω0 ) = 0, σ(x1 |ω0, ω1 ) = σ(x1 |ω1 , ω0 ) = , σ(x1 |ω1 , ω1 ) = 1.
6
The intuition is the following. Since there are only two messages, any strategy induces
two posteriors. Bayes’ plausibility (or the splitting constraint) implies that one posterior
must lie in the region where the receiver does not invest at all. So either the sender
persuades the receiver to invest for only one of the two problems, or to invest for both of
them. We show that it is optimal to persuade to invest for both problems. If the state is
either the worst one (ω0 , ω0 ) or the best one (ω1 , ω1), it is fully disclosed. The strategy is
the same in the two intermediary states (ω0 , ω1 ) and (ω1 , ω0 ) and both messages are sent
with positive probability. The proof is in the Appendix (A.1.2).
19

The insight gained from this example is that the sender is better oﬀ by linking the
two problems together, that is, the distribution of the message depends on both states.
The advantage of linking problems together grows with the number of copies as our main
result shows in the next section.

4

Main results
In this section we state our main result which is a characterization of optimal robust

payoﬀs for large number of copies of the same problem. First, we introduce tools borrowed
from information theory.

4.1

Mutual information and channel capacity

We start by recalling useful notions from information theory, the reader is referred to
Cover and Thomas (2006). Let x be a random variable with values in some ﬁnite set with
distribution p. The (Shannon) entropy of x is,

H(x) = −E log p(x) = −

X

x

p(x) log p(x),

where the logarithm has basis 2 and 0 log 0 = 0. Since this depends only on p, this is also
denoted H(p). Let (x, y) be a pair of ﬁnite random variables with distribution P(x, y).
The conditional entropy of y given x is,

H(y|x) = Ex H(y|x = x) = −

X

P(x)
x

X

y

P(y|x) log P(y|x).

The mutual information between x and y is,

I(x; y) = H(y) − H(y|x) = H(x) − H(x|y).

Take a communication channel Q : X → ∆(Y ). If y is obtained from inputing a random
variable x with distribution p into the channel, then the pair (x, y) has joint distribu-

20

tion P(x, y) = p(x)Q(y|x). The mutual information I(x; y) depends only on this joint
distribution and is thus a function of p and Q.
Definition 4.1. The capacity of the channel Q : X → ∆(Y ) is

C(Q) = max I(x; y),
p∈∆(X)

where the maximum is over the marginal distribution p of x.
For instance, take X = Y and assume that the channel is perfect so that H(y|x) = 0.
The entropy of x is maximal and equal to log |X| when x is uniformly distributed. The
capacity of the perfect channel is thus log |X|. Intuitively, the capacity of the channel
is the maximal number of bits of information that the channel can transmit. A perfect
binary channel can transmit 1 bit of information. If |X| = 2m , the channel can transmit
m bits of information.
An another example, consider the binary symmetric channel with noise ε. Then the
conditional distribution of y given x is (ε, 1 − ε) or its permutation. Again, H(x) is
maximal when x is uniformly distributed. The capacity of the noisy binary channel is
thus C = 1 − H(ε), where with a slight abuse of notation, H(ε) stands for the entropy of
the binary distribution (ε, 1 − ε).

4.2

Splitting with information constraint

Consider a base persuasion problem with state space Ω, prior µ, action sets A and
payoﬀs ui , i = S, R.
A splitting of µ =

P

m

λm µm can be seen as a joint distribution P of a random pair

(ω, m) in Ω × M such that, the marginal distribution of ω is P(ω = ω) = µ(ω), the
marginal distribution of m is P(m = m) = λm and the conditional distribution of ω
given m = m is P(ω = ω|m = m) = µm (ω).
The mutual information of the splitting is the mutual information between ω and m:

I(ω; m) = H(ω) − H(ω|m) = H(µ) −
21

X

m

λm H(µm ).

Let us consider an auxiliary optimisation problem where the sender has access only to the
splittings whose mutual information is at most some given positive number C.
Definition 4.2. For any C ≥ 0, the optimal splitting problem with information constraint
is:

V (µ, C) = sup
ω,m

n

Eω,m US : I(ω; m) ≤ C

o

= sup
s.t.

X

X

m

λm US (µm )

λm µm = µ,
X
and H(µ) −
λm H(µm ) ≤ C.
m

m

If we interpret the mutual information as the cost of the signaling structure (Gentzkow
and Kamenica, 2014; Sims, 2003), the value of this optimisation problem is the optimal
payoﬀ the sender can get with a signaling structure whose cost does not exceed the
capacity C.
The mutual information constraint can be re-ordered as

P

m

λm H(µm) ≥ H(µ) − C

which says that the expected entropy of the posteriors cannot be two low. That is,
posteriors cannot be too precise, the precision being limited both by the entropy of the
prior and the available capacity. Observe that if H(µ) ≤ C, the constraint is satisﬁed by
all splittings. The value of the problem is thus the concaviﬁcation of US in this case.

4.3

The characterization

We are now ready to state the main result of the paper. We are considering n identical
copies of the persuasion problem with communication k times through the channel and
recall that US∗ (µn , Qk ) denotes the optimal robust payoﬀ of the sender.
Theorem 4.3.

1. The optimal robust payoff of the sender is no more than the value

of the optimal splitting with information constraint. For all k, n,
k
US∗ (µn , Qk ) ≤ V (µ, C(Q)).
n
2. The optimal robust payoff of the sender converges to the optimal splitting with infor22

mation constraint as n, k tend to infinity. For any rational number r and all ε > 0,
there exists an integer N(ε) such that for all (k, n) such that k = rn and n ≥ N(ε),
US∗ (µn , Qrn ) ≥ V (µ, rC(Q)) − ε.
To get some intuition, assume n = k for the time being.

The result says that

US∗ (µn , Qn ) ≤ V (µ, C(Q)) for all n, and US∗ (µn , Qn ) → V (µ, C(Q)) as n tends to inﬁnity.
The intuition is as follows. The optimal splitting problem with information constraint
represents the best payoﬀ the sender can achieve by sending a message whose mutual
information with the state is no more than the capacity of the channel. The ﬁrst clause
of the theorem states that this is an upper bound on payoﬀs that the sender can reach by
communicating over the channel. The proof of this necessary condition is simple. Indeed,
the mutual information between the sequence of states and the sequence of messages
to the receiver cannot exceed the capacity of the channel. Therefore, the upper bound
derives naturally from properties of mutual information.
The second clause of the theorem states that the value of the optimal splitting problem
with information constraint, can be obtained approximately for large problems. When n
is large, the intuition that the capacity of the channel is the amount of information that
the channel can transmit per unit of time, can be made concrete by appropriate use of laws
of large numbers. More precisely, Shannon’s coding theory says the following. Suppose
that the mutual information between the random state ω and a random message m is
no more than the capacity I(ω; m) ≤ C. It is then possible for the sender to associate
with the sequence of states (ω 1 , . . . , ω n ), a sequence of intended messages (m1 , . . . , mn )
and a sequence of actual input messages (x1 , . . . , xn ), such that upon receiving the actual
output messages (y 1 , . . . , y n ), the receiver is able to recover most intended messages with
high probability. The coding scheme of our proof uses both of the original Shannon’s
source and channel coding schemes deﬁned in Shannon (1948, 1959), the reader is also
referred to the textbooks Cover and Thomas (2006, Chapters 7 and 10) and Gamal and
Kim (2011, Chapter 3).
To complete the proof, we show that it is indeed optimal for the receiver to ﬁnd out
23

most of the intended messages from the messages actually received. Intuitively, it is optimal for the receiver to extract as much information as possible from the messages and
thus to decode correctly the messages intended by the sender. We prove that the actual
Bayesian beliefs of the receiver about the sequence of states (ω 1 , . . . , ω n ) are close to those
induced by the intended messages (m1 , . . . , mn ). The technical proof is deferred to the
Appendix (A.3).

Now, there is no reason why the number n of pieces of information should be equal to
the number k of times that the channel can be used. The result says that only the ratio
k
n

matters. Indeed, when k = rn, then it is (asymptotically) equivalent to take k = n and

to multiply the capacity by r.
To be concrete, assume that k = 2n. This means intuitively that the channel can be
used two times for each piece of information, so that the capacity is doubled. Alternatively,
assuming 2k = n means that the channel can only be used once for every pair of problems.
As in instance, consider 2k = n copies of Example 3.6 where the number of messages is
half the number of states.
When the ratio r =

k
n

is large, rC ≥ H(µ) and the entropy constraint is automatically

satisﬁed. Intuitively, if the channel could be used many times for each problem, the sender
would be able to convey any message he wants.

4.4

Examples

Example 4.4. Persuading to invest over a noisy channel. Let us revisit Example 3.1
given by the following table.
a0

a1

µ

ω0

(0, 0)

(1, −7)

1
2

ω1

(0, 0)

(1, 1)

1
2

Consider a large number n of independent copies with communication n times over a
binary channel with noise ε = 41 . Recall that in the single problem, the receiver cannot
24

be persuaded to invest and the payoﬀ is 0.
Let us compute the optimal value of splitting with information constraint. The capacity of the channel is 1 − H( 14 ), the entropy of the uniform prior is 1, therefore the
P
information constraint is m λm H(µm) ≥ H( 41 ). Figure 5 shows the set of pairs of posteriors for the splittings which satisfy this constraint (green and blue region).
ν0 (ω1 )
1

3
4

1
2

1
4

0

1
2

1
4

3
4

1

ν1 (ω1 )

Figure 5: Feasible posteriors under information constraint.

Under this constraint the optimal splitting for the sender satisﬁes:

and

1 1
,
2 2





1 7
=λ ,
8 8



+ (1 − λ)(ν(ω0 ), ν(ω1 ))

 
 
7
1
= λH
+ (1 − λ)H(ν(ω1 )).
H
4
8

To see why it is optimal, ﬁrst consider that the sender has to bring on some posterior ν
with ν(ω1 ) >

7
8

in order to get some payoﬀ. To get it with the highest probability, he

should aim for ν(ω1 ) = 87 . Among the posteriors that induce investment, this is also the
one with highest entropy. Second, to maximize expected payoﬀs, the remaining posteriors
must be as far away as possible from the prior, that is, the entropy constraint should
bind. Also, note that only one posterior will be generated in the region ν(ω1 ) < 78 . Since
25

the entropy is strictly concave, replacing two posteriors on this region by their average
does not change the payoﬀ and increases the entropy.
Solving these two equations numerically we get, ν(ω1 ) ≈ 0.340 and V (µ, Q) = λ ≈
0.298 which is about 52.1% of the unconstrained optimum 74 , see Figure 6.
H(ν)
b

1
b

H( 41 )

•

H( 87 )
b

V (µ, Q) = λ ≈ 0.298
b

1
4

b

ν(

0

•7

1
2

8

1

ν(ω1 )

)≈
ω1
0.
34
0
Figure 6: Optimal splitting with information constraint

Example 4.5. Persuading to invest with few words. Consider n = 2k copies of the
previous example where a perfect binary channel is used k times. That is, the number of
messages is half the number of states. This can be seen as k copies of the problem with
4 states given in Example 3.6. The capacity of the binary perfect channel is 1, but since
the channel is used half of the times, it is like the capacity is 21 . So from Theorem 4.3, we
want to calculate the best payoﬀ under the information constraint:
X

 
1
1
1
− ·1= .
λm H(µm ) ≥ H
m
2
2
2

Remark that this is the same constraint one would obtain (with k = n) on a noisy binary
symmetric channel with ε such that H(ε) =

26

1
2

so ε ≈ 0.11. Under this constraint the

optimal splitting for the sender satisﬁes:

and

1 1
,
2 2





1 7
=λ ,
8 8



+ (1 − λ)(ν(ω0 ), ν(ω1 ))

 
1
7
+ (1 − λ)H(ν(ω1)).
= λH
2
8

Solving these equations numerically gives ν(ω1 ) ≈ 0.095 and
1
2
7
8

V (µ, C(Q)) = λ =

− ν(ω1 )
≈ 0.519,
− ν(ω1 )

see Figure 7. This is about 90.8% of the unconstrained optimum

4
7

≈ 0.571.

H(ν)
b

1

1
2

b

1
2

ν(

0

b
•
•
b

b

•

)≈
ω1

7
8

V (µ, C(Q)) ≈ 0.519

1

ν(ω1 )

0.
09
5
Figure 7: Optimal splitting with small perfect channel

27

5

Concavification with information constraint
In this section, we analyze the problem of maximizing the sender’s payoﬀ under the

information constraint:

V (µ, C) = sup

nX

m

λm US (µm ) :

X

m

λm µm = µ, H(µ) −

X

m

o
λm H(µm) ≤ C .

There are two ways to relate this problem to the concaviﬁcation method. First, we show
that this is the concaviﬁcation of the extension of the payoﬀ function on the hypograph
of the entropy function. Second, we show that a Lagrangian method can be used, that is,
we can express this value as the concaviﬁcation of a Lagrangian function. These ﬁndings
are presented in the next theorem.

Theorem 5.1. For each µ ∈ ∆(Ω) and C ≥ 0,
1. V (µ, C) is the concavification of the function USH : ∆(Ω) × R → R,

USH (ν, η) :=




US (ν)


−∞

if η ≤ H(ν),
otherwise,

calculated at (ν, η) = (µ, H(µ) − C).

n
o
2. V (µ, C) = inf t≥0 cav (US + tH)(µ) − t(H(µ) − C) .
The proof is in the Appendix (A.2). A direct implication of the second point is that there
exists2 t∗ = t∗ (µ, C) such that,
V (µ, C) = cav (US + t∗ H)(µ) − t∗ (H(µ) − C).
To see the existence of t∗ , notice that cav (US +tH)(µ)−t(H(µ)−C) ≥ (US +tH)(µ)−t(H(µ)−C) =
US (µ) + tC, which tends to +∞ as t → +∞. Therefore, t 7→ cav (US + tH)(µ) − t(H(µ) − C) reaches a
minimum at some t∗ .
2

28

∗
If (λ∗m , νm
)m is an optimal splitting, let I ∗ = H(µ) −

mation. We have,

V (µ, C) =

X

m

P

m

∗
λ∗m H(νm
) be its mutual infor-

∗
) − t∗ (I ∗ − C).
λ∗m US (νm

(1)

We ﬁnd then the usual Kuhn-Tucker slackness conditions. If I ∗ < C, then t∗ = 0, the
unconstrained optimum is feasible.
If t∗ > 0, the constraint is binding. The Lagrange multiplier t∗ can be interpreted as
the shadow price of capacity, that is, the marginal value of an extra unit of communication
capacity.
This characterization has to be related with the cost of information considered in the
literature on rational inattention (see Sims, 2003) where the agent pays a cost proportional
to the mutual information between the state and the signal he observes. For persuasion
games, Gentzkow and Kamenica (2014) assume that the sender pays a cost for choosing
a disclosure strategy which is also related to the mutual information. In order to deﬁne
this cost independently of the prior, they consider the mutual information between the
state and the message for a fixed exogenous distribution of the state.
Our main result and its implication Equation (1) can be seen as a way to justify the
use of mutual information as the information cost: we obtain it as a shadow cost. The
optimal value of persuasion for a large number of copies of problems with communication
over a noisy channel has the same value as a problem of persuasion with an information
cost. There are some diﬀerences though. First, the information cost is not the mutual
information, but the diﬀerence between the mutual information and the capacity of the
channel. That is, a cost reduces the payoﬀ only when the sender would like to send more
information bits than the capacity. Second, the unit price of capacity is endogenous and
given by the Lagrange multiplier of the information constraint.

29

6

Number of messages
In this section, we study the minimal number of messages required to achieve the op-

timal payoﬀ. In unrestricted persuasion problems, it is known that the necessary number
of messages to achieve the best payoﬀ for the receiver is no more than the number of
states (see Kamenica and Gentzkow, 2011).
With restricted communication, that is under information constraint, Theorem 5.1
shows that we are calculating the concaviﬁcation of the payoﬀ function with respect to
an extra dimension, which suggests that an extra message might be needed.
Intuitively, it might be optimal to split on an extra posterior which does not yield a
good payoﬀ, but helps in satisfying the information constraint.
Lemma 6.1. In the optimization problem,

V (µ, C) = sup

nX

m

λm US (µm ) :

X

m

λm µm = µ, H(µ) −

X

m

o
λm H(µm) ≤ C ,

the number of posteriors can be restricted to |Ω| + 1. That is, without loss of generality,
the supremum is taken over families (λm , νm )m=1,...,|Ω|+1.
To make this intuition concrete, consider the following example.
Example 6.2. Two-sided investment. Consider the following payoﬀ table.
a0

a1

a2

ω0

(0, 0)

(1, −7)

(1, 1)

1
2

ω1

(0, 0)

(1, 1)

(1, −7)

1
2

There are two risky projects (a1 and a2 ) and the sender wants to persuade the receiver
to invest in any of them. The sender invests only if ν(ω1 ) > 7/8 or ν(ω1 ) < 1/8.
With unrestricted communication, the solution is clear: the sender fully discloses
the state and gets a payoﬀ of 1. However, with a binary symmetric channel with noise
ε = 1/4, the sender gets 0 in the single problem. Consider now n copies and assume that
the channel can be used n times (n large).
30

The “one-sided” solution of Example 4.4 is feasible. Recall that this is the splitting
such that,



and

1 1
,
2 2





1 7
=λ ,
8 8



+ (1 − λ)(ν(ω0 ), ν(ω1 ))

 
 
7
1
= λH
+ (1 − λ)H(ν(ω0 ), ν(ω1 )).
H
4
8

with ν(ω1 ) ≈ 0.340 and λ ≈ 0.298. It is easy to see that this is optimal among the
splittings with two posteriors. Indeed, it is not possible that the two posteriors induce
investment while satisfying the information constraint.
However, this is not optimal. The optimal splitting has three posteriors and is the
following.

with



1 1
,
2 2





1 1
= (1 − λ) ,
2 2







λ 1 7
λ 7 1
+
+
,
,
2 8 8
2 8 8

 
 
 
 
1
λ
λ
1
1
7
H
= (1 − λ)H
+ H
+ H
.
4
2
2
8
2
8

This pins down a unique λ and solving numerically yields λ ≈ 0.413. Since λ is the
probability of investment, we get V (µ, Q) ≈ 0.413 which is about 38% better than what
is achieved with a splitting with two points.
H(ν)
b

1
H( 41 )
H( 81 )

0

b

b

•
1
8

b

1
4

1
2

3
4

•
7
8

1

ν(ω1 )

To see that this is optimal, ﬁrst since there are two states, we know that three posteriors are suﬃcient. Second, it is not possible to have all posteriors in the investment region
31

and to satisfy the information constraint. If there is only one posterior in the investment
region, then the splitting is achieving no more than the “one-sided” solution. Therefore, it
is optimal to have two posteriors in the investment region and one outside of the region.
But then, it is optimal to choose the point in the middle region to be ( 21 , 12 ), since this is
the one with the highest entropy.

Note that this example involves three actions. Indeed, the number of required messages
can be bounded by the number of actions.
Lemma 6.3. In the optimization problem,

V (µ, C) = sup

nX

m

λm US (νm ) :

X

m

λm νm = µ,

X

m

o
λm H(νm ) ≥ H(µ) − C ,

the number of points can be restricted to min{|A|, |Ω| + 1}.
We have already seen that the number of points can be chosen less than or equal to
|Ω| + 1. Now intuitively, the number of actions is enough because two posteriors inducing
the same action could be replaced by their average without changing payoﬀs and still
satisfying the information constraint, see the Appendix (A.2) for the formal proof.

32

A

Appendix
This appendix contains all the formal proofs. The proof of Theorem 4.3 appears last

as it is the most involved and uses some auxiliary results from the proofs of the other
results.

A.1
A.1.1

Proofs for Section 3
Proof of Lemma 3.4

For a, b in [0, 1], consider the system,

ν1 (ω1 ) =

µ(ω1 )(1 − b)
,
µ(ω0 )a + µ(ω1 )(1 − b)

ν0 (ω1 ) =

µ(ω1 )b
.
µ(ω0)(1 − a) + µ(ω1 )b

(2)

If ν1 = ν0 = µ, then it must be that a = 1 − b. Otherwise, ν1 (ω1 ) 6= ν0 (ω1 ). It is easily
veriﬁed that the system has a unique solution given by,

b=

ν0 (ω1 )(ν1 (ω1 ) − µ(ω1 ))
µ(ω1 )(ν1 (ω1 ) − ν0 (ω1 ))

and
a=

(1 − ν0 (ω1 ))(µ(ω1 ) − ν0 (ω1 ))
.
(1 − µ(ω1 ))(ν1 (ω1 ) − ν0 (ω1 ))

Take a strategy σ deﬁned by σ(x0 |ω0) = 1 − α and σ(x1 |ω1 ) = 1 − β and a binary
symmetric channel with noise ε. The posteriors ν1 , ν0 are given by the system (2) for
a = α ⋆ ε and b = β ⋆ ε. As α, β vary in [0, 1], α ⋆ ε and β ⋆ ε range freely over [ε, 1 − ε],
{(α ⋆ ε, β ⋆ ε) : (α, β) ∈ [0, 1]2 } = [ε, 1 − ε]2 .

This concludes the proof.
A.1.2



Proof of Claim 3.7

A generic belief over {ω0 , ω1 } × {ω0 , ω1 } is denoted ν. An action for the receiver is a
pair in {a0 , a1 } × {a0 , a1 } and we denote it a = (a(1), a(2)).
33

The receiver has to choose actions in two separate decision problems. In each problem,
he will invest if the probability of the high state is above 78 . For the sake of the calculation,
we assume that the receiver invests in case of indiﬀerence (otherwise, we know that the
optimal value is obtained with arbitrary precision).
The receiver with belief ν chooses:
a(1) = a1 if ν(ω1 , ω0 ) + ν(ω1 , ω1 ) ≥ 87 , a(1) = a0 otherwise;
a(2) = a1 if ν(ω0 , ω1 ) + ν(ω1 , ω1 ) ≥ 87 , a(2) = a0 otherwise.
Consider a splitting of the uniform prior µ = ( 41 , 41 , 41 , 41 ) = λν0 + (1 − λ)ν1 . We have,
1
= µ(ω1 , ω0 ) + µ(ω1 , ω1 ) = λ(ν0 (ω1 , ω0 ) + ν0 (ω1 , ω1 )) + (1 − λ)(ν1 (ω1 , ω0 ) + ν1 (ω1 , ω1 )).
2
Suppose that ν0 (ω1 , ω0 ) + ν0(ω1 , ω1 ) ≥ 87 , then it must be that ν0 (ω1 , ω0 ) + ν0 (ω1 , ω1 ) < 21 .
This implies that for any splitting with two posteriors, the receiver chooses (a0 , a0 ) at one
of the two posteriors. Then, there are two possibilities. At the other posterior, either the
receiver invests in only one of the problems and the average payoﬀ is

1
2

for the sender, or

the receiver invests in both and the average payoﬀ is 1 for the sender.
In the ﬁrst case, by symmetry, say that the receiver invests in the ﬁrst problem only.
The sender then gets optimally

4
7

in the ﬁrst problem and 0 in the second, thus an average

payoﬀ of 72 .
In the second case, we look for the optimal way of splitting the uniform prior between
ν0 and ν1 with ν1 (ω1 , ω0 ) + ν1 (ω1 , ω1 ) ≥

7
8

and ν1 (ω0 , ω1 ) + ν1 (ω1 , ω1) ≥ 87 .

First, let us remark that it is without loss of generality to consider posteriors with
the following symmetry ν(ω0 , ω1 ) = ν(ω1 , ω0 ). To see this, given a belief ν, deﬁne ν̃ such
that ν̃(ωi , ωj ) = ν(ωj , ωi ). For a splitting µ = λν0 + (1 − λ)ν1 , the symmetrized splitting
µ = λν̃0 + (1 − λ)ν̃1 achieves the same payoﬀ. Thus the sender gets the same payoﬀ with,

µ=λ

ν1 + ν̃1
ν0 + ν̃0
+ (1 − λ)
2
2

which is symmetric. A symmetric posterior with ν1 (ω1 , ω0 )+ν1 (ω1 , ω1 ) ≥

34

7
8

and ν1 (ω0 , ω1 )+

ν1 (ω1 , ω1 ) ≥

7
8

can thus be written as,

(ν(ω0 , ω0 ), ν(ω1 , ω0 ), ν(ω0 , ω1 ), ν(ω1 , ω1 )) = (1 − 2p − q, p, p, q),
7
8

with p + q ≥

and 2p + q ≤ 1.

Second, among this set, it is optimal to split on a posterior such that p + q =

7
.
8

Indeed, a line segment joining ( 41 , 41 , 41 , 14 ) to some (1 − 2p′ − q ′ , p′ , p′, q ′ ) with p′ + q ′ ≥ 87 ,
must contain some (1 − 2p − q, p, p, q) with p + q = 87 . The optimal splitting is thus of the
form



1 1 1 1
, , ,
4 4 4 4





1
7
= (1 − λ)(1 − 2p̃ − q̃, p̃, p̃, q̃) + λ
− p, p, p, − p
8
8

with p ∈ [0, 81 ], p̃ + 2q̃ ≤ 1 (and necessarily p̃ + q̃ ≤

1
).
2



Then optimally, we choose

(1 − 2p̃ − q̃, p̃, p̃, q̃) on the boundary of the probability simplex. Actually, we can choose
q̃ = 0. Precisely, for every p ∈ [0, 81 ], there exists λ ∈ [0, 1] and p̃ ∈ [0, 21 ] such that,


1 1 1 1
, , ,
4 4 4 4






1
7
= (1 − λ)(1 − 2p̃, p̃, p̃, 0) + λ
− p, p, p, − p .
8
8

Solving this equation yields,

λ=

7
− 4p
2
and p̃ = 4
.
7 − 8p
5 − 8p

It is easy to verify that λ ∈ [0, 1] and p̃ ∈ [0, 21 ]. The payoﬀ for this splitting is λ =
which is maximal for p = 18 , thus the optimal value of 13 .

A.2
A.2.1

2
7−8p



Proofs for Sections 5 and 6
Proof of Theorem 5.1

In this section, we prove a statement more general than Theorem 5.1. As a matter
of fact, there is nothing speciﬁc to the entropy function, and a similar result holds for
general functions.
Let f : X → R ∪{−∞} be a real-valued function deﬁned on a convex domain X of Rd .

35

The concavification of f is the smallest function cav f : X → R ∪ {−∞} which is concave
and majorizes f on X. This is the concave function whose hypograph is the convex hull
of the hypograph of f . It is given by the following optimisation problem:

cav f (x) = sup

nX

m

λm f (xm ) :

X

m

o
λm xm = x ,

where the supremum ranges over all convex combinations (λm , xm )m , xm ∈ X, λm ≥ 0,
P
P
m λm = 1 and
m λm xm = x (see Rockafellar, 1970, p. 36).
We introduce now a concaviﬁcation with constraint. Let f, g : X → R ∪ {−∞} be two
functions deﬁned on X. For x ∈ X and γ ∈ R consider the problem:

cavg f (x, γ) := sup

nX

m

λm f (xm ) :

X

m

λm xm = x,

X

m

o
λm g(xm ) ≥ γ .

The optimal splitting under information constraint is an instance of this problem:

sup

nX

m

λm US (νm ) :

X

m

λm νm = µ,

X

m

o
λm H(νm ) ≥ H(µ) − C .

Lemma A.1. Let f g : X × R → R ∪ {−∞} defined by,

f g (x, γ) =

Then for each (x, γ) ∈ X × R,




f (x)


−∞

if γ ≤ g(x),
otherwise.

cavg f (x, γ) = cav f g (x, γ).

(3)

That is, the problem of optimal splitting with payoﬀ function f under the constraint
P

m

λm g(xm ) ≥ γ is in fact the concaviﬁcation of a bi-variate function, which is the ex-

tension of f to the hypograph of the constraint g.

36

Proof. [Lemma A.1] The function cav f g (x, γ) is given by the following program:

sup
s.t.

X

X

m

m

λm f (xm )
λm xm = x,

X

m

λm γ m = γ

and ∀m, γm ≤ g(xm ).

Take a family (λm , xm , γm )m feasible for this program. We have

P

m

λm g(xm ) ≥ γ, thus

this family is feasible for cavg f (x, γ). Therefore, cav f g (x, γ) ≤ cavg f (x, γ).
P
P
Conversely, take a family (λm , xm )m such that m λm xm = x and m λm g(xm ) ≥ γ.
P
P
Let γ̄ = m λm g(xm ) and for each m, γm = g(xm ) + γ − γ̄. Then, m λm γm = γ and

since γ̄ ≥ γ, for each m, γm ≤ g(xm ). Thus, (λm , xm , γm )m is feasible for cav f g (x, γ) and
cav f g (x, γ) ≥ cavg f (x, γ).



This characterization readily applies to the optimal splitting problem under information constraint.



Now, we show that the Lagrangian approach is valid for the problem,

cavg f (x, γ) = sup

Proposition A.2.

nX

m

λm f (xm ) :

X

m

λm xm = x,

X

m

o
λm g(xm ) ≥ γ .

n
o
cavg f (x, γ) = inf cav (f + tg)(x) − tγ .
t≥0

That is, the concaviﬁcation under constraint corresponds to the concaviﬁcation of a
Lagrangian.
Proof. [Proposition A.2] Recall that the Fenchel conjugate of f : X ⊆ Rd → R is f ∗ (p) =
supx {x · p − f (x)}, where x · p denotes the inner product. Then, the largest convex
function below f is equal to (f ∗ )∗ (Rockafellar, 1970, Corollary 12.1.1, p. 103), therefore
(f ∗ )∗ (x) = −cav (−f )(x). Playing with signs, it follows that,

cav f (x) = inf x · p + sup{f (y) − p · y} .
p



y

37

(4)

We apply this formula to the function:

f g (x, γ) =

This gives,




f (x)


−∞

if γ ≤ g(x),
otherwise.



g
cav f (x, γ) = inf p · x + zγ + sup{f (y, η) − p · y − zη}
p,z
y,η


= inf p · x + zγ + sup {f (y) − p · y − zη} .
g

p,z

y,η: η≤g(y)

If z > 0 then by letting η → −∞, the sup is +∞. Therefore in the inﬁmum we can
restrict to z ≤ 0. Setting t = −z ≥ 0 we get,

g

cav f (x, γ) = inf

t≥0,p



p · x − tγ +

sup

{f (y) − p · y + tη}

y,η: η≤g(y)







= inf p · x − tγ + sup{f (y) − p · y + tg(y)}
t≥0,p
y


n
o
= inf inf p · x + sup{f (y) + tg(y) − p · y} − tγ
t≥0

p

y

where the second line holds since t ≥ 0 and the third line is just re-organizing. The result
n
o
follows by remarking that inf p p · x + supy {f (y) + tg(y) − p · y} = cav (f + tg)(x). 
This proves the second point of Theorem 5.1.

A.2.2

Proof of Lemma 6.1

Lemma 6.1 follows from a well-known fact about concaviﬁcation.
Fact A.3. In the optimisation problem,

cav f (x) = sup

nX

m

λm f (xm ) :

X

m

o
λm xm = x ,

where f is defined on X ⊆ Rd , the number of points can be restricted to d + 1. That is,

38

without loss of generality, the supremum is taken over families (λm , xm )d+1
m=1 .
The reader is referred to Rockafellar (1970, Corollary 17.1.5, p. 157). This implies
that in a persuasion problem with unrestricted communication, the number of messages
can be bounded by the dimension of ∆(Ω) plus one, that is the number of states.
Corollary A.4. In the optimisation problem,

cavg f (x, γ) = sup

nX

m

λm f (xm ) :

X

m

λm xm = x,

X

m

λm g(xm ) ≥ γ

o

where f is defined on X ⊆ Rd , the number of points can be restricted to d + 2.
This follows from Lemma A.1 and Fact A.3, since the function f g is deﬁned on X × R ⊆
Rd+1 . Applying to the problem of optimal splitting under information constraint, gives a
number of messages bounded by the dimension of ∆(Ω) plus two, that is the number of
states plus one.



A.2.3

Proof of Lemma 6.3


P
∗
e
Let A(ν)
= argmin
be the set of optimal actions of
ω ν(ω)uS (ω, a) : a ∈ A (ν)

the receiver at ν which are worst for the sender.

e
Claim A.5. For any action a, the set of ν’s such that a ∈ A(ν)
is convex.

Proof. Observe ﬁrst that the set of ν’s such that a ∈ A∗ (ν) is deﬁned by linear inequalities,
e 1 ) ∩ A(ν
e 2 ) and let’s
i.e. the optimality of a, therefore is convex. Consider now a ∈ A(ν

e 1 + (1 − t)ν2 ) for t ∈ (0, 1). We have a ∈ A∗ (ν1 ) ∩ A∗ (ν2 ) and by the
show that a ∈ A(tν

remark above, a ∈ A∗ (tν1 + (1 − t)ν2 ). Take b ∈ A∗ (tν1 + (1 − t)ν2 ). We have thus,
X

ω

X

(tν1 (ω) + (1 − t)ν2 (ω))uR(ω, a) =

ω

(tν1 (ω) + (1 − t)ν2 (ω))uR(ω, b).

Since a ∈ A∗ (ν1 ) ∩ A∗ (ν2 ),
X

ω

ν1 (ω)uR(ω, a) ≥

X

ω

ν1 (ω)uR (ω, b),

X

39

ω

ν2 (ω)uR(ω, a) ≥

X

ω

ν2 (ω)uR(ω, b).

e 1 ) ∩ A(ν
e 2 ),
Combined together, we get that b ∈ A∗ (ν1 ) ∩ A∗ (ν2 ). Since a ∈ A(ν
X

ω

ν1 (ω)uR (ω, a) ≤

X

ω

ν1 (ω)uR (ω, b),

X

ω

ν2 (ω)uS (ω, a) ≤

X

ω

ν2 (ω)uS (ω, b).

Taking the convex combination of these two inequalities proves the claim.



P
P
Consider a feasible splitting (λm , µm ) such that m λm νm = µ and m λm H(νm ) ≥
n
o
e m ) = {a} . Denote λ̃a =
H(µ) − C. For each action a, deﬁne M(a) = m : A(ν
P
m∈M (a) λm and
X
λm
νm .
ν̃a =
m∈M (a) λ̃
a
We have,

µ =
=
=

X
X

X

λm νm
X
λ̃a

m
a

a

m∈M (a)

λm
νm
λ̃a

λ̃a ν̃a .

This deﬁnes a splitting of µ with |A| elements. We argue that the payoﬀ is the same as
the initial splitting. Let’s calculate the expected payoﬀ. From the previous claim, for
e a ). We have thus,
each action a, a ∈ A(ν̃
X

m

λm US (νm ) =
=
=

X

X

X

a

a
a

λ̃a
λ̃a

X

X

m∈M (a)

ω

λm X
νm (ω)US (ω, a)
ω
λ̃a

ν̃a (ω)US (ω, a)

λ̃a US (ν̃a ).

To conclude the proof, we check that the information constraint is satisﬁed. This follows

40

from the concavity of entropy. Indeed,

H(ν̃a ) ≥

X

λ̃a H(ν̃a ) ≥

X

m∈M (a)

λm
H(νm )
λ̃a

and thus,
X

a

m

λm H(νm ) ≥ H(µ) − C.


A.3
A.3.1

Proof of Theorem 4.3
Proof of Theorem 4.3, point 1, the upper bound

1. For all k, n, US∗ (µn , Qk ) ≤ V (µ, nk C(Q)).
Proof. Let us ﬁx a strategy σ of the sender. This induces a probability distribution Pσ of sequences in Ωn ×X k ×Y k , the associated random sequences are denoted (ω n , xk , y k ). Let t
be a uniformly distributed random variable over {1, . . . , n}, independent from (ω n , xk , y k )
and denote m = (y k , t) taking values in M = Y k × {1, . . . , n}.
e ω, m) the joint probability distribution of (ω, m) deﬁned by:
We denote P

e ω, m) =P
e ω = ω, (yk , t) = m
P


e = t) · P
e ω = ω, y k = y k t = t
=P(t

1
= · Pσ ω t = ω, y k = y k .
n

e ω, m) on Ω is equal to the prior µ:
Note that the marginal distribution of P
e ω) =
P

X

X

t,y k


e ω = ω, y k = y k , t = t
P


1
k
k
·
P
ω
=
ω,
y
=
y
σ
t
t,y k n
Xn 1

· Pσ ω t = ω
=
t=1 n
 Xn 1
=Pσ ω ·
= µ(ω).
t=1 n
=

41

Fix now a strategy τ of the receiver τ : Y k → An and deﬁne τ̃ : M → A where τ̃ (m) =
τ̃ (y k , t) = τt (y k ), the t-th coordinate of τ (y k ). The expected average payoﬀ of player
i = R, S writes:
"

#


Xn
1
Pσ (ω n , xk , y k )
ui ωt , τt (y k )
ω n ,xk ,y k
t=1
n


Xn X
1
k
k
k
=
·
P
(ω
,
x
,
y
)
·
u
ω
,
τ
(y
)
σ
t
i
t
t
t=1
ωt ,xk ,y k n


Xn X
1
k
k
·
P
(ω
,
y
)
·
u
ω
,
τ
(y
)
=
σ
t
i
t t
t=1
ωt ,y k n


X
e
=
P(ω,
y k , t) · ui ω, τ̃ (y k , t)
ω,y k ,t


X
e
=
P(ω,
m) · ui ω, τ̃ (m) .

  X
Eσ,τ ūi =

ω,m

(5)
(6)
(7)
(8)
(9)

Equation (6) implies Equation (7) by summing over xk which does not enter the payoﬀ
function. All other steps are re-orderings and change of variables.

A strategy τ is a best-reply to σ if and only if:
τ (y k ) ∈ arg max
n
n
a ∈A

X

⇐⇒ τ̃ (m) ∈ arg max
a∈A

µ(ω n )σ(xk |ω n )Q(y k |xk )ūR (ω n , an )

ω n ,xk ,y k

X

ω,m

e
P(ω,
m) · uR (ω, a)

X
⇐⇒ τ̃ (m) ∈ arg max
ν̃σ (ω|m) · uR (ω, a)
ω
a∈A


⇐⇒ τ̃ (m) ∈ A∗ ν̃σ (·|m)

e
where ν̃σ (ω|m) = P(ω|m).
We deduce for any strategy σ of the sender and any best-reply
τ of the sender, the expected average payoﬀs are those induced by the splitting

µ(ω) =

X

m

e
P(m)ν̃
σ (ω|m).

42

Now, we bound the mutual information of this splitting. For any strategy σ, we have:
0 ≤ I(xk ; y k ) − I(ω n ; y k )
(10)
Xn
Xn
Xk
Xk
H(ω t |y k , ωt−1 )
H(ω t |ω t−1 ) +
H(y t |xk , y t−1 ) −
H(y t |y t−1 ) −
=
t=1

t=1

t=1

t=1

(11)

Xn
H(ωt |y k )
H(y t |xt ) − n · H(ω) +
t=1
t=1
t=1
Xn
Xk
P(t = t) · H(ω|y k , t = t)
I(xt ; y t ) − n · H(ω) + n ·
=

≤

Xk

H(y t ) −

Xk

(12)
(13)

t=1

t=1

≤ k · max I(x; y) − n · H(ω) + n · H(ω|y k , t)

(14)

= k · max I(x; y) − n · H(ω) + n · H(ω|m)

(15)

= k · max I(x; y) − n · I(ω; m).

(16)

P(x)

P(x)

P(x)

- Equation (10) holds since the triple (ω n , xk , y k ) has the Markov chain property that is,
its join distribution writes µ(ω n)σ(xk |ω n )Q(y k |xk ). This implies I(xk ; y k ) ≥ I(ω n ; y k ),
that is xk is more informative that ω n about y k (Cover and Thomas, 2006, Theorem
2.8.1, p. 34).
- Equation (11) comes from the chain rule of entropy H(y k ) =

Pk

t=1

H(y t |y t−1 ).

- Equation (12) follows since the channel is memoryless H(y t |xk , y t−1 ) = H(y t |xt ),
the sequence of states is i.i.d. H(ωt |ω t−1 ) = H(ωt ), and conditioning reduces entropy
H(ωt |y k , ω t−1 ) ≤ H(ω t |y k ).
- Equation (13) is a simple re-writing with the introduction of the uniform random variable t ∈ {1, . . . , n}.
- Equation (14) comes from taking the maximum over the marginal distribution P(x).
- Equation (15) comes from the change of variable m = (y k , t).
Then, Equation (16) is equivalent to:

k · max I(x; y) − n · I(ω; m) ≥ 0
P(x)

k
· max I(x; y)
n P(x)
X
k
λm H(µm) ≥ H(µ) − · C(Q).
m
n

⇐⇒ H(ω|m) ≥ H(ω) −
⇐⇒

43

Therefore, for any strategy σ and all n, k, we have:

min

τ ∈BR(σ)

= min

τ̃ ∈BR(σ)

=

X

X

m

X

X

ω n ,xk ,y k

ω,m

e
P(m)

µ(ω n )σ(xk |ω n )Q(y k |xk )ūS (ω n , τ (y k ))



e
P(ω,
m) · uS ω, τ̃ (m)
min
∗

τ̃ (m)∈A (ν̃σ (·|m))

X

ω



ν̃σ (·|m) · uS ω, τ̃(m)


e
P(m)
· US ν̃σ (·|m)
m
X

e
≤ sup
P(m)
· US ν̃σ (·|m)
=

m

σ

X

s.t.

m

X

e
P(m)
· ν̃σ (·|m) = µ,


k
e
and
P(m)
· H ν̃σ (·|m) ≥ H(µ) − · C(Q)
m
n
X

= sup
λm · US νm



m

s.t.

and

X

m

X

m

λm νm = µ,
λm H νm

k
= V (µ, C(Q)).
n



k
≥ H(µ) − · C(Q)
n



This proves that for all n and k we have:
US∗ (µn , Qk ) = sup min
σ

τ ∈BR(σ)

X

ω n ,xk ,y k

µ(ω n )σ(xk |ω n )Q(y k |xk )ūS (ω n , τ (y k ))

k
≤V (µ, C(Q))
n
as desired.
A.3.2



Proof of Theorem 4.3, point 2, the limit value

2. For any rational number r and all ε > 0, there exists an integer N(ε) such that for
all (k, n) such that k = rn and n ≥ N(ε), US∗ (µn , Qrn ) ≥ V (µ, rC(Q)) − ε.

Zero capacity. First, let’s investigate the case C(Q) = 0.
44

Lemma A.6. If the channel capacity is equal to zero: maxp(x) I(x; y) = 0, then for all
k, n, we have:
k
US∗ (µn , Qk ) = V (µ, C(Q)).
n
Proof. [Lemma A.6] Let (x, y) be a pair of random variables such that the conditional
probability of {y = y} given {x = x} is Q(y|x). If the capacity of the channel is 0,
then I(x, y) = H(y) − H(y|x) = 0 which implies that x and y are independent: no
information can be sent through the channel.
This implies that for any splitting which satisﬁes the information constraint, the random variables ω and m are independent, and for all m ∈ M we have νm = µ. Hence:
k
V (µ, C(Q)) = US (µ).
n
Moreover, for any strategy σ, the sequence of messages y k of the receiver is independent
from the sequence of states ω n . It follows that,
US∗ (µn , Qk ) = sup min

X

µn (ω n )σ(xk |ω n )Qk (y k )ūS (ω n , τ (y k ))
σ τ ∈BR(σ)

 X
X
n
1
k
n
n
k k
uS (ωt , τt (y ))
= min
µ (ω )Q (y )
t=1
ω n ,y k
τ ∈BR(σ)
n
X
1 Xn
=
min
µ(ωt )uS (ωt , at )
t=1 at ∈A∗ (µ)
ωt
n
X
= min
µ(ω)uS (ω, a) = US (µ),
∗
a∈A (µ)

ω n ,xk ,y k

ω

which concludes the proof.



Positive capacity. We assume from now on C(Q) > 0. The goal is to take a splitting of
the prior which satisﬁes the information constraint, and to show that the associated payoﬀ
can be approximately achieved by strategy σ of the sender and a best-reply τ ∈ BR(σ) of
the receiver. The next lemma states that we can focus on splittings such that the infor45

mation constraint is satisﬁed with strict inequality and where the action of the receiver
is unique for each posterior in the splitting. Concretely, we prove that such splittings are
dense in the set of feasible splittings.

e the set of worst optimal actions when the belief is ν ∈ ∆(Ω),
Recall that we denote A(ν)
e
A(ν)
= argmin

X

∗

ω



ν(ω)uS (ω, a) : a ∈ A (ν) .

Consider the following program:
k
Vb (µ, C(Q)) = sup
n

X
s.t.

m

X

λm US (νm )

λm νm = µ,
X
k
and H(µ) −
λm H(νm ) < C(Q)
m
n

e m ) is a singleton .
and ∀m, A(ν
m

Lemma A.7. For all integers (k, n), µ ∈ ∆(Ω) and Q such that C(Q) > 0 we have:
k
k
V (µ, C(Q)) = Vb (µ, C(Q)).
n
n

(17)

Proof. [Lemma A.7]
Remark A.8. From Lemma 6.3, we know that we can restrict the number of messages,
i.e. the number of posteriors to K = min{|A|, |Ω|+1}. Therefore, from now on a splitting
(λm , νm )m will be understood to be a composed of λ = (λ1 , . . . , λK ) ∈ ∆({1, . . . , K}) and
(νm )m ∈ (∆(Ω))K . The set of splittings of µ is thus a convex and compact subset of
∆({1, . . . , K}) × (∆(Ω))K

which itself is a compact and convex set in some ﬁnite dimension space. All statements below about closed or open sets of splittings relate to the topology induced by the Euclidean
topology on this ﬁnite dimension space.
46

We consider the following sets:

S1 =



(λm , νm )m ,

s.t.
and

S2 =



(λm , νm )m ,

s.t.
and

S3 =



(λm , νm )m ,

s.t.
and

X

m

X

m

X

m

X

λm νm = µ,


k
λm H(νm ) ≥ H(µ) − C(Q) ,
m
n
λm νm = µ,

e m ) is a singleton
∀m, A(ν
X



,

λm νm = µ,


k
λm H(νm ) > H(µ) − C(Q) .
m
n

We will prove that the set S2 ∩ S3 is dense in S1 , which implies that Equation (17) is
e
satisﬁed. We ﬁrst argue that A(ν)
is a singleton for an open and dense set of posteriors

ν.

Definition A.9. Two actions a and b are equivalent a ∼i b for player i = S, R, if for all
ω ∈ Ω, ui (ω, a) = ui (ω, b).
We say that two actions a and b are completely equivalent if they are equivalent for
both players. Without loss of generality, we assume that no two actions are completely
equivalent. Otherwise, we can merge them into one single action and work on the reduced
problem.
Denote Fi ⊆ ∆(Ω) the set of beliefs for which player i ∈ {S, R} is indiﬀerent between
two actions which are not equivalent:

Fi =



ν ∈ ∆(Ω) : ∃a, b, a ≁i b,

X

ω

ν(ω)ui (ω, a) =

X

ω


ν(ω)ui (ω, b) .



Let F c = ∆(Ω) \ FR ∪ FS be the set of beliefs where at least one player is not indiﬀerent

between any two actions.

e
Claim A.10. The set F c is open and dense in ∆(Ω) and for each ν ∈ F c , A(ν)
is a
singleton.

47

Proof. [Claim A.10] For each i and each pair of actions a, b with a ≁i b, the set,

Fi (a, b) =



ν ∈ ∆(Ω) :

X

ω

ν(ω)ui (ω, a) =

X

ω

ν(ω)ui (ω, b)



is a closed hyperplane of dimension dim(Fi (a, b)) ≤ |Ω| − 2. Thus, FR and FS are closed
and FR ∪ FS is included in a ﬁnite union of hyperplanes of dimension at most |Ω| − 2.
The complementary set is thus open and dense in ∆(Ω).
e
Then, if A(ν)
contains two distinct actions a 6= b, both players are indiﬀerent between

e
a and b at ν. So if ν ∈ F c , A(ν)
is a singleton.



It follows that S2 is open and dense in S1 .

Claim A.11. If the channel capacity is strictly positive C(Q) > 0, the set S3 is nonempty, open and dense in S1 .
Proof. [Claim A.11] Take a feasible splitting (λm , νm )m in S1 :
X

m

λm H(νm ) ≥ H(µ) −

k
C(Q).
n

For ε > 0, consider the perturbed splitting (λm , (1 − ε)νm + εµ)m . From concavity of the
entropy,
X

m

λm H((1 − ε)νm + εµ) ≥ (1 − ε)

X

m

λm H(νm ) + εH(µ),

k
k
C(Q) + ε C(Q)
n
n
k
> H(µ) − C(Q),
n

≥ H(µ) −

thus the information constraint is satisﬁed with strict inequality for ε > 0. It follows that
S3 is non-empty and dense in S1 . By continuity of the entropy, S3 is open in S1 .



Since S2 and S3 are open and dense, we conclude that S2 ∩ S3 is dense in S1 and that
V (µ, nk C(Q)) = Vb (µ, nk C(Q)) as desired.



48

Given a strategy σ of the sender, we denote the induced expected payoﬀ as follows:
bS,σ (µn , Qk ) = min
U

τ ∈BR(σ)

X

ω n ,xk ,y k

µ(ω n )σ(xk |ω n )Q(y k |xk )ūS (ω n , τ (y k )),



= min Eω n ,xk ,yk ūS (ω n , τ (y k )) .
τ ∈BR(σ)

Our goal now is to prove the following.
Proposition A.12. For any rational number r and all ε > 0, there exists an integer N(ε)
such that for all (k, n) such that k = rn and n ≥ N(ε), there exists a strategy σ such that:
bS,σ (µn , Qk ) − Vb (µ, rC(Q)) ≤ ε.
U

(18)

Proof. [Proposition A.12] Let us ﬁx from now on a splitting (λm , νm )m which satisﬁes the
three conditions:
X

λm νm = µ,
X
H(µ) −
λm H(µm) < rC(Q),
m

m

e m ) is a singleton.
∀m, A(ν

(19)
(20)
(21)

Let M = {1, . . . , |M|} be the set of messages associated to this splitting. We will
consider a strategy of the sender as a mapping
σ : Ωn → ∆(M n × X k ).

This means that conditional on the sequence of states ω n , the sender chooses a sequence of
messages mn ∈ M n and a sequence of symbols xk ∈ X k which he inputs into the channel.
Observe that any strategy, i.e. any mapping from Ωn to ∆(X k ), can be deﬁned in this
way. The messages mn are immaterial and can be seen as a pure mental construct of the
sender. Nevertheless, they are important in our construction. These are the messages
that the sender intends to send to the receiver through the symbols xk , and that the
receiver should decoded from the sequence y k .
49

The strategy σ induces a joint probability distribution Pσ over Ωn × M n × X k × Y k ,
Pσ ω n , mn , xk , y k ) =

Yn

t=1

µ(ωt ) × σ(mn , xk |ω n ) ×

Yn

t=1

Q(yt |xt )

σ
k
Let us denote νt,y
k ∈ ∆(Ω) the posterior belief on ω t conditional on the sequence y .

That is,

σ
k
νt,y
.
k (ω) = Pσ ω t = ω | y

For each sequence y k of messages and for each t, the receiver chooses an optimal action
σ
e σ
at ∈ A∗ (νt,y
k ). In the worst case (for the sender), this action at belongs to A(νt,y k ). It

follows that,

Claim A.13.
bS,σ (µn , Qk ) =
U

X

mn ,y

Pσ (mn , y k )
k

1 Xn
σ
US (νt,y
k ).
t=1
n

Now, we will deﬁne an event B ⊆ M n × Y k such that for every (mn , y k ) ∈ B,
Pn
P
1
σ
t=1 US (νt,y k ) is close to
m λm US (νm ). We need some notations. For ν1 , ν2 ∈ ∆(Ω),
n
P
the ℓ1 distance is kν1 − ν2 k = ω |ν1 (ω) − ν2 (ω)|. The Kullback-Leibler (KL) divergence
is,

D(ν1 kν2 ) =

X

ω

ν1 (ω) log

ν1 (ω)
.
ν2 (ω)

These two distances are related by Pinsker’s inequality (Cover and Thomas, 2006, Lemma
11.6.1, p. 370):
kν1 − ν2 k ≤

p

2 ln 2 D(ν1 kν2 ).

We will introduce several positive parameters α, γ, δ, to be thought of as small.
Notation A.14. For a sequence (mn , y k ) and α > 0, denote
n
α2 o
σ
Tα (m , y ) = t ∈ {1, . . . , n} : D(νt,yk kνmt ) ≤
.
2 ln 2
n

k

50

σ
This is the set of indices t = 1, . . . , n such that the posterior belief νt,y
k about ω t is

close to the theoretical belief νmt . Intuitively, this is the set of indices where the message
mt is approximately transmitted.
e
Remark A.15. Since the set of posteriors ν such that A(ν)
is a singleton is open, there

exists α0 > 0 such that for all m,

e
e m ).
D(νkνm ) ≤ α0 ⇒ A(ν)
= A(ν

e is a singleton, denote A(ν)
e
Whenever A(ν)
= {ã(ν)} the unique (worst) optimal action.

From now on, we assume that α ∈ (0, α0 ). With the remark above, this implies that for
each t ∈ Tα (mn , y k ), the action chosen by the receiver for problem t is τt (mn , y k ) = ã(νmt ).
So precisely, Tα (mn , y k ) is the set of indices t such that the receiver plays the action ã(νmt )
which corresponds to the message mt . So in this sense, this is the set of indices for which
the information transmission is successful.
Notation A.16. For a sequence (mn , y k ) and m ∈ M, denote
freq m (mn , y k ) =

1
{t = 1, . . . , n : mt = m}
n

the empirical frequency of message m in the sequence mn .
For α, γ, δ > 0, let

Bα,γ,δ

n

o
X
|Tα (mn , y k )|
n
k
= (m , y ) :
≥ 1 − γ and
|λm − freq m (m , y )| ≤ δ
m
n
n

k

Lemma A.17. For each (mn , y k ) ∈ Bα,γ,δ ,
X
1 Xn
σ
US (νt,y
λm US (νm ) ≤ (α + 2γ + δ)kuk,
k) −
t=1
m
n
where kuk = maxω,a |uS (ω, a)| is the largest absolute value of payoffs for the receiver.

51

Proof. Denote u∗ =

P

m

λm US (νm ). We have

1X
1X
1 Xn
σ
∗
σ
∗
σ
∗
US (νt,y
≤
+
(U
(ν
)
−
u
)
(US (νt,y
k) − u
k
k) − u )
S t,y
t=1
t∈Tα (mn ,y k )
t∈T
/ α (mn ,y k )
n
n
n
1X
σ
∗
≤
(US (νt,y
k ) − u ) + γkUk
n ,y k )
t∈T
(m
α
n
Then,
1X
1X
σ
∗
σ
(U
(ν
(US (νt,y
k) − u ) ≤
k ) − US (νmt ))
S
t,y
t∈Tα (mn ,y k )
t∈Tα (mn ,y k )
n
n
1X
+
(US (νmt ) − u∗ )
t∈Tα (mn ,y k )
n
n
k
σ
Since α ≤ α0 , for each t ∈ Tα (mn , y k ), ã(νt,y
k ) = ã(νmt ). Therefore, for t ∈ Tα (m , y )

σ
US (νt,y
k ) − US (νmt ) ≤

X

ω

σ
σ
|νt,y
k (ω) − νmt (ω))| · |uS (ω, a)| ≤ kνt,y k − νmt k · kuk ≤ αkuk,

where the latter inequality comes from Pinsker’s inequality and the deﬁnition of Tα (mn , y k ).
It follows,
1X
1X
σ
∗
(U
(ν
(US (νmt ) − u∗ )
k ) − u ) ≤ αkuk +
S
t,y
n ,y k )
n ,y k )
t∈T
(m
t∈T
(m
α
α
n
n
Now from

|Tα (mn ,y k )|
n

≥ 1 − γ, we have,

1 Xn
1X
∗
(US (νmt ) − u∗ ) + γkuk.
)
−
u
)
≤
(U
(ν
S
m
t
t=1
t∈Tα (mn ,y k )
n
n
Then,
X
1 Xn
(freq m (mn , y k ) − λm )US (νm )
(US (νmt ) − u∗ ) =
m
t=1
n
X
freq m (mn , y k ) − λm · US (νm )
≤
m

≤ kukδ.

Collecting all inequalities together yields the desired conclusion.

52



We have the direct consequence:
Corollary A.18.
bS,σ (µn , Qk ) − Vb (µ, rC(Q)) ≤ (α + 2γ + δ)kuk + (1 − Pσ (Bα,γ,δ ))kuk.
U
We see from this inequality that estimating the probability of the set Bα,γ,δ is key. The
last step of the proof is the actual construction of the strategy. The idea is that, since
the information constraint is satisﬁed i.e. I(ω; m) < rC(Q), there is enough capacity
to transmit m over the channel. More precisely, we construct a strategy such that the
set Bα,γ,δ has probability close to 1. This way, for most sequences (ω n , mn , xk , y k ), the
receiver gets the right message in most stages. That is, at most stages the receiver plays
the action corresponding to the message.

We turn now to the actual construction. We use standard information theoretic techniques for Channel Coding (Gamal and Kim, 2011, Chap. 3.1, p. 38) and Lossy Source
Coding (Gamal and Kim, 2011, Chap. 3.6, p. 56). Using information theoretic language,
the sender is viewed as an encoder who encrypts his intended mn messages in sequences
of inputs xk . The encoding is such that a decoder who reads the sequence y k , is able to
ﬁnd out the correct mn with high probability. This is described as follows.
For δ > 0, we deﬁne the set of typical sequences Aδ as follows:

Aδ =



(ω n , mn , xk , y k ),

s.t.
and

X

X

ω,m

λm µm (ω) − freq ω,m (ω n , mn ) ≤ δ,
k

x,y

k

(22)


P(x) × Q(y|x) − freq x,y (x , y ) ≤ δ .

(23)

A pair of sequences (ω n , mn ) which satisﬁes Equation (22) will be called jointly typical.
Similarly, pair of sequences (xk , y k ) which satisﬁes Equation (23) will be called jointly
typical. With a slight abuse of notation, we will write (ω n , mn ) ∈ Aδ or (xk , y k ) ∈ Aδ to
indicate jointly typical sequences.
Since condition (20) is satisﬁed with strict inequality, there exists a small parameter

53

η > 0 and a “rate” R ≥ 0, such that:

R =H(µ) −

X

m

λm H(µm) + η,

(24)
(25)

R ≤rC(Q) − η.

Moreover, we can assume that nR is an integer for n large enough.
• Random codebook. A codebook is a family c of |J| = 2nR sequences mn (j) and xk (j)
indexed by j ∈ J. A random codebook is the draw of a codebook from the marginal
i.i.d. probability distributions (λm )⊗n and P(x)⊗n . The selected codebook is known
by the encoder and the decoder.
• Encoding function. The encoder observes the sequence of states ω n ∈ Ωn . It ﬁnds
an index j ∈ J such that the sequences (ω n , mn (j)) ∈ Aδ are jointly typical, i.e.
satisfy Equation (22). The encoder sends the sequence xk (j) corresponding to the
index j ∈ J.
• Decoding function. The decoder observes the sequence of channel output y k ∈ Y k .

It ﬁnds an index ĵ ∈ J such that the sequences xk (ĵ), y k ∈ Aδ are jointly typical,
i.e. satisfy Equation (23). The decoder decodes the sequence mn (ĵ).

• Error Event. We introduce the indicator of error Eδ ∈ {0, 1} deﬁned as follows:

Eδ =

(

0 if

j = ĵ and

1 if

j 6= ĵ or


ω n , mn , xk , y k ∈ Aδ ,

ω n , mn , xk , y k ∈
/ Aδ .

(26)

An error Eδ = 1 occurs in the coding process if: 1) the indexes j ∈ J and ĵ ∈ J are

not equal or 2) the sequences of symbols ω n , mn , xk , y k ∈
/ Aδ , i.e. are not jointly
typical.

An important result in information theory is that the expected probability of error
over the random codebook is small.
Expected error probability. For all ε2 > 0, for all η > 0, there exists a δ̄ > 0, for all
δ ≤ δ̄ there exists n̄ such that for all n ≥ n̄ and k = r · n, the expected probability of the
54

following error events are bounded by ε2 :
 


n
n
E Pc ∀j ∈ J,
ω , m (j) ∈
/ Aδ
≤ ε2 ,
 


′
k
k ′
E Pc ∃j 6= j, s.t. y , x (j ) ∈ Aδ
≤ ε2 .

(27)
(28)

- Equation (27) comes from Equation (24) and the Covering Lemma A.19, (Gamal and
Kim, 2011, Lemma 3.3, p. 62).
- Equation (28) comes from Equation (25) and the Packing Lemma A.20, (Gamal and
Kim, 2011, Lemma 3.1, p. 46).

If the expected probability of error is small over the codebooks, then it has to be small
for at least one codebook. Following a standard analysis of the error probability, (Gamal
and Kim, 2011, pp. 42–43, 60–61), Equations (27), (28) imply that:

∀ε2 > 0, ∀η > 0, ∃δ̄ > 0, ∀δ ≤ δ̄, ∃n̄ > 0, ∀n ≥ n̄,

∃c⋆ ,


Pc⋆ Eδ = 1 ≤ ε2 .

(29)

The strategy σ of the sender consists in using this codebook c⋆ in order to ﬁnd the
sequence mn (j) which is jointly typical with ω n , and in sending the sequence xk (j). By
construction, this satisﬁes Equation (29), i.e. it has a low probability of error.

Control of the Beliefs. This construction has the property that the decoder who uses
the decoding schemes, makes an error with small probability. Now, the receiver needs
not use the decoding scheme. Actually, the receiver calculates the posterior belief on the
sequence of states ω n , given y k . The next step shows that those beliefs are close to the

55

prescribed beliefs νm at most stages. We have the following chain of inequalities.
#


1 Xn
σ
Eδ = 0
D νt,y
Eσ
k νmt
t=1
n


X
1 Xn
n
k
σ
=
P
(m
,
y
|E
=
0)
·
(30)
ν
D
ν
k
σ
δ
mt
t,y
mn ,y k
t=1
n
1X
1
1 Xn
n
n
k
Q
H(ω t |y k , Eδ = 0)
=
P
(ω
,
m
,
y
|E
=
0)
·
log
−
σ
δ
n
2
t=1
(ω n ,mn ,y k )∈Aδ
n
n
(ω
)
ν
t
t=1 mt
"

(31)

≤

1X
1 Xn
1
n
n
k
Q
P
(ω
,
m
,
y
|E
=
0)
·
log
−
H(ω t |mn , y k , Eδ = 0)
σ
δ
n
2
n
n
k
(ω ,m ,y )∈Aδ
t=1
n
n
t=1 νmt (ωt )
(32)

≤


 1
1X
n
n
k
P
(ω
,
m
,
y
|E
=
0)
·
n
·
H(ω|m)
+
δ
− H(ω n |mn , y k , Eδ = 0)
σ
δ
(ω n ,mn ,y k )∈Aδ
n
n

(33)


1
1
≤ I(ω n ; mn , y k |Eδ = 0) − I(ω; m) + δ + + log2 |Ω| · Pσ Eδ = 1
n
n

1
2
≤ I(ω n ; mn |Eδ = 0) − I(ω; m) + δ + + 2 log2 |Ω| · Pσ Eδ = 1
n
n

2
≤η + δ + + 2 log2 |Ω| · Pσ Eδ = 1 .
n

(34)
(35)
(36)

- Equation (30) comes from the deﬁnition of the expected K-L divergence.
- Equation (31) comes from the conditioning by Eδ = 0, since the support of Pσ (ω n , mn , y k |Eδ =
0) is included in Aδ .
- Equation (32) comes from the property of the entropy H(ω t |mn , y k , Eδ = 0) ≤ H(ωt |y k , Eδ =
0).
- Equation (33) comes from the property of typical sequences (ω n , mn ) ∈ Aδ , stated in
Lemma A.21 and in Gamal and Kim (2011, Property 1, pp. 26), and the chain rule for
entropy:
H(ω n |mn , y k , Eδ = 0) ≤

Xn

t=1

H(ω t |mn , y k , Eδ = 0).

- Equation (34) comes from Lemma A.23 (see section A.4), which implies,
1
1
1
H(ωn |Eδ = 0) − H(ω n ) + + log2 |Ω| · Pσ (Eδ = 1) ≥ 0.
n
n
n
56

Adding this expression to Equation (33) yields Equation (34).
- Equation (35) comes from Lemma A.23 (see section A.4) which implies that,
I(ω n ; y k |mn , Eδ = 0) ≤ I(ω n ; y k |mn )+1+n·log2 |Ω|·Pσ (Eδ = 1) = 1+n·log2 |Ω|·Pσ (Eδ = 1),
where I(ω n ; y k |mn ) = 0, from the Markov chain property of the triple (ω n , mn , y k ).
- Equation (36) comes from the cardinality of the codebook:
I(ω n ; mn |Eδ = 0) ≤ H(mn ) ≤ log2 |J| = n · R = n · (I(ω; m) + η).
The last argument is inspired by Merhav and Shamai (2007, Equation (23)) for the problem of “Information Rates Subject to State Masking”.
Then we have:
c
1 − Pσ (Bα,γ,δ ) := Pσ (Bα,γ,δ
)
c
c
=Pσ (Eδ = 1)Pσ (Bα,γ,δ
|Eδ = 1) + Pσ (Eδ = 0)Pσ (Bα,γ,δ
|Eδ = 0)
c
≤Pσ (Eδ = 1) + Pσ (Bα,γ,δ
|Eδ = 0)
c
≤ε2 + Pσ (Bα,γ,δ
|Eδ = 0).

(37)

57

Moreover:
c
Pσ (Bα,γ,δ
|Eδ = 0)


X
n
k
c
E
=
0
=
P
(m
,
y
)
∈
B
δ
σ
α,γ,δ
n k
m ,y

X

|Tα (mn , y k )|
< 1 − γ Eδ = 0
mn ,y
n
!




2
#
α
σ
=Pσ
≤
t, s.t. D νt,y
< 1 − γ Eδ = 0
k νmt
n
2 ln 2
!




2
α
#
σ
>
t, s.t. D νt,y
≥ γ Eδ = 0
=Pσ
k νmt
n
2 ln 2
"
#

2 ln 2
1 Xn
σ
≤ 2 · Eσ
D νt,y
k νmt
t=1
α γ
n



2 ln 2
2
≤ 2 · η + δ + + 2 log2 |Ω| · Pσ Eδ = 1 .
α γ
n
=

Pσ (mn , y k )
k

s.t.

(38)
!

(39)
(40)
(41)
(42)
(43)

- Equations (38) to (41) are simple reformulations.
- Equation (42) comes from a use of Markov’s inequality, detailed in Lemma A.22 (see
section A.4).
- Equation (43) comes from equation (36).

Combining equations (29), (37), and (43) we obtain the following statement:
∀ε3 > 0, ∀γ > 0, ∃η̄, ∀η ≤ η̄, ∃δ̄, ∀δ ≤ δ̄, ∃n̄, ∀n ≥ n̄, ∃σ, such that:
c
Pσ (Bα,γ,δ
)




2 ln 2
2
≤ 2 · Pσ Eδ = 1 + 2 · η + δ + + 2 log2 |Ω| · Pσ Eδ = 1 ≤ ε3
α γ
n


To conclude the proof of Proposition A.12, we take the inequality of Corollary A.18.
We choose the parameters α, γ, η, δ small and then n large, in order to get:
bS,σ (µn , Qk ) − Vb (µ, rC(Q)) ≤ (α + 2γ + δ)kuk + (1 − Pσ (Bα,γ,δ ))kuk ≤ ε.
U
This ends the proof.



58

A.4

Additional lemmas

The next three lemmas are standard results in information theory. They are recalled
for the convenience of the reader.
Lemma A.19 (Covering lemma: compression of information source, Lemma 3.3, p.
62 in Gamal and Kim (2011)). Consider a random sequence ω n with i.i.d. distribution

P⊗n (ω) and a family of 2nR sequences mn (j) j∈{1,...,2nR } independently drawn from the
i.i.d. distribution P⊗n (m). Assume that R = I(ω; m) + η with η > 0.

For all ε > 0, there exists δ̄ > 0, such that for all δ ≤ δ̄, there exists n̄, such that for
all n ≥ n̄:

P ∀j ∈ J,

n



n

ω , m (j) ∈
/ Aδ



≤ ε.

Lemma A.20 (Packing lemma: transmission over a noisy channel, Lemma 3.1, p. 46
Gamal and Kim (2011)). Consider a random sequence y k drawn with i.i.d. distribution

P⊗k (y) and a family of 2kR sequences xk (j) j∈{1,...,2kR } independently drawn from the i.i.d.
distribution P⊗k (x). Assume that R = I(x; y) − η with η > 0.

For all ε > 0, there exists δ̄ > 0, such that for all δ ≤ δ̄, there exists k̄, such that for
all k ≥ k̄:

P ∃j ∈ J,

k

x (j), y

k



∈ Aδ



≤ ε.

Lemma A.21 (Typical sequences, Property 1, p. 26 in Gamal and Kim (2011)). The
typical sequences (ω n , mn ) ∈ Aδ satisfy:
∀δ2 > 0, ∃δ̄2 > 0, ∀δ ≤ δ̄2 , ∀n, ∀(ω n , mn ) ∈ Aδ ,
1
1
− H(ω|m) ≤ δ2 ,
· log2 Qn
n
t=1 P(ωt |mt )
where δ̄2 = δ2 · H(ω|m).
The next two lemmas are easy ancillary results that were used in the proofs and were
59

omitted in the previous section to ease the reading.
Lemma A.22 (Markov’s inequality). For all ε1 > 0, ε2 > 0 we have:

#
1 Xn
D Pσ (ω t |y n , Eδ = 0) P(ω t |mt )
≤ ε0
(44)
Eσ
t=1
n
!




#
ε0
=⇒Pmn ,yn
t, s.t. D Pσ (ω t |y n , Eδ = 0) P(ω t |mt ) > ε1 > ε2 ≤
. (45)
n
ε1 · ε2
"


Proof. [Lemma A.22] We denote by Dt = D Pσ (ω t |y n , Eδ = 0) P(ω t |mt ) and D n =
{Dt }t the K-L divergence. We have that:

!
!




#
1 Xn
P
t, s.t. Dt > ε1 > ε2 =P
1 Dt > ε 1 > ε 2
·
t=1
n
n

n
o
Pn
1
E n·
t=1 1 Dt > ε1
≤
ε
 2n
o
P
n
1
·
t=1 E 1 Dt > ε1
n
=
ε
2

P
n
1
P
D
>
ε
·
t
1
t=1
n
=
ε2
P
n
E[Dt ]
1
·
t=1 ε1
n
≤
ε2


1
ε0
1 Xn
=
Dt ≤
·E
·
.
t=1
ε1 · ε2
n
ε1 · ε2

(46)

(47)

(48)
(49)
(50)
(51)

Equations (46), (48), (49), (51) are reformulations of probabilities and expectations.
Equations (47), (50), come from Markov’s inequality P(X ≥ α) ≤ E[X]/α.



Lemma A.23. Consider an i.i.d. random sequence ω n . For all ε > 0, there exists n̄ ∈ N
such that for all n ≥ n̄ we have:


H(ω |Eδ = 0) ≥ n · H(ω) − ε .
n

60

(52)

Proof. [Lemma A.23]


1
n
n
· H(ω |Eδ = 1) − P(Eδ = 1) · H(ω |Eδ = 1)
H(ω |Eδ = 0) =
P(Eδ = 0)
n

(53)

≥H(ω n |Eδ ) − P(Eδ = 1) · H(ω n |Eδ = 1)

(54)

≥H(ω n ) − H(Eδ ) − P(Eδ = 1) · H(ωn |Eδ = 1)

(55)

≥H(ω n ) − n · ε.

(56)

Equation (53) comes from the deﬁnition of the conditional entropy.
Equation (54) comes from the property P(Eδ = 0) ≤ 1.
Equation (55) comes from the property H(ω n |Eδ ) = H(ω n , Eδ ) − H(Eδ ) ≥ H(ωn ) −
H(Eδ ).
Equation (56) comes from the i.i.d. property of the state ω and the deﬁnition of the error
event Eδ = 1. Hence for all ε, there exists a n̄ ∈ N such that for all n ≥ n̄ we have:
H(P(Eδ = 1)) + P(Eδ = 1) · log2 |Ω| ≤ ε.



References
Akyol, E., C. Langbort, and T. Başar (2017): “Information-Theoretic Approach
to Strategic Communication as a Hierarchical Game,” Proceedings of the IEEE, 105(2),
205–218.
Aumann, R., and M. Maschler (1995): Repeated Games with Incomplete Information.
MIT Press, Cambrige, MA.
Bergemann, D., and S. Morris (2016): “Information Design, Bayesian Persuasion, and
Bayes Correlated Equilibrium,” American Economic Review Papers and Proceedings,
106(5), 586–591.
(2017): “Information Design: a Uniﬁed Perspective,” Cowles Foundation Discussion Paper No 2075.

61

Blume, A., O. J. Board, and K. Kawamura (2007): “Noisy Talk,” Theoretical Economics, 2, 395–440.
Cover, T. M., and J. A. Thomas (2006): Elements of information theory. 2nd. Ed.,
Wiley-Interscience, New York.
Crawford, V. P., and J. Sobel (1982): “Strategic Information Transmission,” Econometrica, 50(6), 1431–1451.
Cuff, P., H. Permuter, and T. Cover (2010): “Coordination Capacity,” IEEE Transactions on Information Theory, 56(9), 4181–4206.
Cuff, P., and L. Zhao (2011): “Coordination using implicit communication,” Proceedings of the IEEE Information Theory Workshop (ITW), pp. 467– 471.
Gamal, A. E., and Y.-H. Kim (2011): Network Information Theory. Cambridge University Press.
Gelfand, S. I., and M. S. Pinsker (1980): “Coding for channel with random parameters,” Problems of Control and Information Theory, 9(1), 19–31.
Gentzkow, M., and E. Kamenica (2014): “Costly Persuasion,” American Economic
Review, 104, 457 – 462.
Gossner, O., P. Hernández, and A. Neyman (2006): “Optimal Use of Communication Resources,” Econometrica, 74(6), 1603–1636.
Gossner, O., and T. Tomala (2006): “Empirical distributions of beliefs under imperfect observation,” Mathematics of Operation Research, 31(1), 13–30.
(2007): “Secret Correlation in Repeated Games with Imperfect Monitoring,”
Mathematics of Operation Research, 32(2), 413–424.
Gossner, O., and N. Vieille (2002): “How to play with a biased coin?,” Games and
Economic Behavior, 41(2), 206–226.

62

Hernández, P., and B. von Stengel (2014): “Nash codes for noisy channels,” Operations Research, 62(6), 1221–1235.
Jackson, M. O., and H. F. Sonnenschein (2007): “Overcoming Incentive Constraints
by Linking Decisions,” Econometrica, 75(1), 241 – 257.
Kamenica, E., and M. Gentzkow (2011): “Bayesian Persuasion,” American Economic
Review, 101, 2590 – 2615.
Le Treust, M. (2017): “Joint Empirical Coordination of Source and Channel,” IEEE
Transactions on Information Theory, 63(8), 5087–5114.
Le Treust, M., and M. Bloch (2016): “Empirical Coordination, State Masking and
State Ampliﬁcation: Core of the Decoder’s Knowledge,” Proceedings of the IEEE International Symposium on Information Theory (ISIT).
Le Treust, M., and T. Tomala (2016): “Information Design for Strategic Coordination of Autonomous Devices with Non-Aligned Utilities,” Proceedings of the IEEE 54th
Allerton conference, Monticello, Illinois, pp. 233–242.
Martin, D. (2017): “Strategic Pricing with Rational Inattention to Quality,” Games and
Economic Behavior, 104, 131–145.
Matejka, F., and A. McKay (2015): “Rational Inattention to Discrete Choices: A New
Foundation for the Multinomial Logit Model,” American Economic Review, 105(1),
272–98.
Merhav, N., and S. Shamai (2007): “Information Rates Subject to State Masking,”
IEEE Transactions on Information Theory, 53(6), 2254–2261.
Neyman, A., and D. Okada (1999): “Strategic Entropy and Complexity in Repeated
Games,” Games and Economic Behavior, 29(1–2), 191–223.
(2000): “Repeated Games with Bounded Entropy,” Games and Economic Behavior, 30(2), 228–247.

63

Rockafellar, R. (1970): Convex Analysis, Princeton landmarks in mathematics and
physics. Princeton University Press.
Shannon, C. (1948): “A mathematical theory of communication,” Bell System Technical
Journal, 27, 379–423.
(1959): “Coding theorems for a discrete source with a ﬁdelity criterion,” IRE
National Convention Record, Part 4, pp. 142–163.
Sims, C. (2003): “Implication of Rational Inattention,” Journal of Monetary Economics,
50(3), 665–690.
Steiner, J., C. Stewart, and F. Matejka (2017): “Rational Inattention Dynamics:
Inertia and Delay in Decision-Making,” Econometrica, 84(2), 521–553.
Taneva, I. (2016): “Information Design,” Manuscript, School of Economics, The University of Edinburgh.
Tsakas, E., and N. Tsakas (2017): “Noisy persuasion,” Working Paper.
Wyner, A. D., and J. Ziv (1976): “The rate-distortion function for source coding with
side information at the decoder,” IEEE Transactions on Information Theory, 22(1),
1–11.

64

