Markovian Persuasion

The literature devoted to Bayesian persuasion studies optimal policies by which an informed agent, the sender, discloses information to an uninformed agent, the receiver. Kamenika and Gentzkow [16] present a case where a prosecutor, who is fully informed about the state of nature, i.e., whether the suspect is guilty or innocent, wishes to persuade a judge, e.g to convict the suspect of a crime. This is a static scenario: upon the prosecutor’s disclosure, the judge takes a decision and the game is over.

In this paper we study a dynamic model where the interaction between the sender, who has a commitment power, and the receiver evolves over time. At each period nature randomly chooses a state and the sender gets informed about it. The decision of how much information to disclose to the receiver at each stage is the choice of the sender. The latter publicly announces an information provision policy, to which he is committed throughout. The receiver knows the details of this policy and thus, when she receives a signal from the sender she updates her belief about the true state. She then takes an action that is based solely on her posterior belief. This action, together with the realized state, determines not only her own payoff, but also that of the sender. In short, in this dynamic signaling interaction, the sender is in charge of the informational aspects of the interaction (talking), while the receiver is in charge of doing. Neither may affect the evolution of the realized states, which is entirely exogenous.

We assume that the evolution of states follows a Markov chain. The dynamic of the receiver’s belief is governed by both the disclosure policy of the sender and a Markov transition matrix. After observing the signal sent by the sender, the receiver updates her belief according to Bayes’ law. Due to the Markovian transition law, this belief shifts to another belief. Since all terms are known to both players, the nature of the shift from prior belief to a posterior one is also known to both.

When committing to an information provision policy, the sender takes into account the resulting posterior belief of the receiver, which has two effects. The first is on the action taken by the receiver and directly on his own stage payoff. In a dynamic setting, as discussed here, it has also an effect on the belief over future states, and consequently on future payoffs. The posterior resulting from a Bayesian updating in one period is then shifted by the Markov transition matrix and becomes the initial belief in the next one. Balancing between these two, potentially contradicting effects, is the dynamic programming problem faced by the sender.

In this paper we study the long-run optimal values that the sender may achieve in an irreducible and aperiodic Markov chain.¹¹1In a companion paper we examine, based on the current study, the general case. This value depends on his discount factor. As in Aumann and Maschler [6] and in Kamenika and Gentzkow [16], the optimal signaling strategy follows a splitting scheme of beliefs in accordance with the concavification of a certain function²²2That is, the lowest concave function above a given function.. While in a static model this function is the payoff function of the sender, here, this function takes account of the underlying dynamics and combines present and future payoffs.

The first set of results deal with a patient sender. It turns out that the stationary distribution of the Markov chain plays a central role. The reason is that in case the sender keeps mute, the receiver’s beliefs become converge, very fast,³³3At an exponential rate (see e.g., Theorem 4.9 in [20]). to the stationary distribution.

We show that as the sender becomes increasingly patient,⁴⁴4The method of treating patient players in not new to the literature of dynamic interactions. Fudenberg and Maskin [11] introduced a Folk Theorem characterizing the set of equilibria in a repeated game played by patient players. Typically in these kind of games, it is impossible to provide a description of the value or of the set of equilibria that correspond to a specific discount factor more informative than that given by Bellman equation (see Abreu et. al. [1]). the optimal values converges to a certain level, called the asymptotic value. Moreover, this value cannot exceed the optimal level obtained in the static case when the prior belief is the stationary distribution. A natural question is under what conditions this static optimal value can be obtained in the dynamic model. Our main theorem provides a full characterization. In order to describe it we introduce the notion of an absorbing set.

A set $C$ of prior distributions is said to be absorbing, if any distribution $p$ in $C$ evolves by the Markov law to another distribution which is within the convex boundaries of $C$. The stationary distribution, for instance, is absorbing as it shifts to itself. The main theorem roughly asserts that the asymptotic value is as high as it can get (i.e., the static value at the stationary distribution), precisely when there is an absorbing set by which the optimal static value is defined (as a weighted average). The intuition behind this result is the following. If any set $A$ by means of which the optimal static value is defined is non-absorbing, then regardless of the policy the sender uses, the posterior beliefs of the receiver would exit the boundaries of $A$ infinitely often, at times having positive limit frequency. Upon each such exit, the sender’s payoff would take a hit which he would not be able to compensate for in subsequent time periods. Therefore, the dream scenario for a patient sender is to find a set $A$ by means of which the optimal static value is defined, so that he could confine the posteriors beliefs of the receiver within the convex boundaries of $A$ throughout the entire game.

The second type of results is non-asymptotic in nature. For a certain region around the stationary distribution we provide a closed form expression for the values corresponding to any level of patience. In the case where this region includes a neighborhood of the stationary distribution, we give asymptotically effective⁵⁵5That is, bounds whose difference is arbitrarily small for a patient enough sender. two-sided bounds for the values corresponding to any level of patience. Moreover, the effectiveness of those bounds depends on the geometry and size of the described neighborhood.

The closest paper to the present one is that of Renault et. al. [22]. It deals with a specific type of Markov chains, homothetic ones, and with a utility function which gives a fixed amount to the sender in a certain region and zero in its complement. Renault et. al. [22] show that in this model the optimal information provision policy is a greedy one (starting from a certain random time period on). Namely, the sender’s greedy policy instructs him to maximize his current stage payoff at any time period, ignoring future effects of this policy. Also closely related to our work are the works of Ely [9] and Farhadi and Teneketzis [12], which deal with a case where there are two states, whose evolution is described by a Markov chain with one absorbing state. In these two works, the receiver is interested in detecting the jump to the absorbing state, whereas the sender seeks to prolong the time to detection of such a jump.

In a broader context, our paper can be ascribed to a vast growing literature on dynamic information design problems, specifically with the analysis of situations in which the sender is required to convey signals sequentially to a receiver, which he may base on his additional private information. Without dwelling upon the exact details of their models, whose frameworks cover diverse methodological approaches, we refer the reader to Mailath and Samuelson [19], Honryo [14], Phelan [21], Lingenbrink and Iyer [18], Wiseman [26], Athey and Bagwell [4], Arieli and Babichenko [2], Arieli et. al. [3], Dziuda and Gradwohl [8], Escobar and Toikka [10], Ganglmair and Tarantino [13], and Augenblick and Bodoh-Creed [5] for an acquaintance with the literature.

The paper is organized as follows. Section 2 presents the model and an example by which we explain the notations, new concepts and the main results. The asymptotic results as well as the main theorem are provided in Section 3. Results related to non-asymptotic values are given in Section 4. Section 5 provides a characterization of homothetic matrices in terms of the asymptotic value. The proofs are given in Section 6.

Let $K=\{1,...,k\}$ be a finite set of states. Assume that $(X_{n})_{n\geq 1}$ is an irreducible and aperiodic Markov chain over $K$ with prior probability $p\in\Delta(K)$ and a transition rule given by the stochastic matrix $M$. We assume that $(X_{n})_{n\geq 1}$ are defined on the probability space $(\Omega,\mathcal{F},\mathbb{P})$.

A sender is an agent who is informed at each time period $n$ of the realized value $x_{n}$ of $X_{n}$. Upon obtaining this information a sender is prescribed to send a signal $s_{n}$, from a finite set of signals $S$ with cardinality at least $k$.⁶⁶6This assumption is in place to make sure the sender can disclose $(x_{n})_{n}$.

A receiver is an agent who, at any time period $n$, is instructed to make a decision $b_{n}$ from a set of possible set of decisions $B$, assumed to be a compact metric space. This decision may take into account the first $n$ signals $s_{1},...,s_{n}$ of the sender.

The payoffs of the sender and the receiver at time period $n$ are given by the utilities $v(x_{n},b_{n})$ and $w(x_{n},b_{n})$, respectively, so that they depend solely on the realized state $x_{n}$ and the decision $b_{n}$. Both the sender and the receiver discount their payoffs by a factor $\lambda\in[0,1)$. We denote this game by $\Gamma_{\lambda}(p)$. As in the models of Renault et. al. [22], Ely [9], and Farhadi and Teneketzis [12] the receiver receives information only through the sender.

A signaling strategy $\sigma$ of the sender in $\Gamma_{\lambda}(p)$ is described by a sequence of stage strategies $(\sigma_{n})$, where each $\sigma_{n}$ is a mapping $\sigma_{n}:(K\times S)^{n-1}\times K\to\Delta(S).$ Thus, the signal $s_{n}$, sent by the sender at time $n$ is distributed by the lottery $\sigma_{n}$, which may depend on all past states $x_{1},...,x_{n-1}$ and past signals $s_{1},...,s_{n}$ together with the current state $x_{n}$. Let $\Sigma$ be the space of all signaling strategies.

A standard assumption in many Bayesian persuasion models is that of commitment by the sender. That is, we assume that the sender commits to a signaling strategy $\sigma$ at the start of the game $\Gamma_{\lambda}(p)$, and makes it known to the receiver. The commitment assumption enables the receiver to update her beliefs on the distribution of states $(X_{n})$ based on the signals $(s_{n})$ he receives from the sender. Formally, by Kolmogorov’s Extension Theorem, each signaling strategy $\sigma$ together with $(X_{n})_{n\geq 1}$ induce a unique probability measure $\mathbb{P}_{p,\sigma}$ on the space $\mathcal{Y}=(K\times S)^{\mathbb{N}}$, determined by the laws

Thus, the posterior probability $p_{n}^{\ell}$ the receiver assigns to the event $\{X_{n}=\ell\}$, given the signals $s_{1},...,s_{n}$ and the strategy $\sigma$, is given by the formula

Set $p_{n}=(p_{n}^{\ell})_{\ell\in K}$. A second key assumption of our model is that the receiver’s decision at any time period $n$ depends only on $p_{n}$. Such an assumption includes the natural situation in which the receiver seeks to maximize her expected payoff based on his current belief (e.g., Renault et. al. (2015)). Denote by $\theta:\Delta(K)\to B$ the decision policy of the receiver, that is, the mapping which depicts the decision of the receiver as a function of his belief. The last assumption of our model is that the function $u:\Delta(K)\to\mathbb{R}$ defined by $u(q)=\sum_{\ell\in K}q^{\ell}v(\ell,\theta(q))$ is continuous. To summarize, our assumptions imply that the signaling strategy $\sigma$ of the sender determines his payoff at any time period $n$. Moreover, the total expected payoff to the sender in $\Gamma_{\lambda}(p)$ under the signaling strategy $\sigma$ can now be written as

where $\mathbb{E}_{p,\sigma}$ is the expectation w.r.t. $\mathbb{P}_{p,\sigma}$. The value of the game $\Gamma_{\lambda}(p)$ is $v_{\lambda}(p)=\sup_{\sigma\in\Sigma}\gamma_{\lambda}(p,\sigma)$.

The previous results shed light on the connection between $M$ and $u$. Specifically, the main theorem characterizes when $v_{\infty}=(\text{Cav}\,u)(\pi_{M})$ in terms of $M$ and $u$. A natural question arises as to when this result holds for a fixed $M$ and for every $u$. To answer this question, we need to introduce the notion of a homothety.

It is clear that when $\psi$ is a homothety with respect to $(v,\beta)$, the point $v$ is a fixed point of $\psi$. Moreover, $\psi$ reduces the distance from any point $x$ to $v$ by a factor of $\beta$. When $v\in\text{int}(\Delta(K))$, or equivalently¹⁴¹⁴14For any measure $\mu$ defined on a finite probability space, we denote by $\text{supp}(\mu)$ its support, i.e., the set of elements to which $\mu$ assigns a positive probability. $|\text{supp}(v)|=k$, and $\beta\in[0,1)$, the matrix $M^{\psi}$ defined by the homothety $\psi$ is an irreducible aperiodic stochastic matrix. In particular, the stationary distribution of $M$ is $v$. Therefore, we shall say that an irreducible aperiodic stochastic matrix $M$ is a homothety if the mapping $\phi:x\mapsto xM$ is a homothety of $\mathbb{R}^{k}$ with center $\pi_{M}$ and ration $\beta$, for some $\beta\in[0,1)$.

When a stochastic matrix is a homothety, the transition from one state to another follows this law: each state stays unchanged with probability $1-\beta$ and moves according to the distribution $v$ to other states with probability $\beta$.

We proceed by describing an interesting class of $M$-absorbing sets of a homothety $M$. A set $E\subseteq\Delta(K)$ is said to be star shaped around $p\in\Delta(K)$ if $[p,q]\subseteq E$ for every $q\in E$. In words, assume that an observer is located at the point $p\in\Delta(K)$. Then $E$ is star shaped around $p$ if the line of sight, $[p,q]$, to any point $q\in E$ lies entirely in $E$. Assume now that $E$ is star shaped around $\pi_{M}$. If $M$ is a homothety, then $qM\in[\pi_{M},q)\subseteq E\subseteq\text{conv}(E)$ for every $q\in E$. Hence, when $M$ is a homothety, every star shaped set around any $\pi_{M}$ is $M$-absorbing.

Let $M$ be irreducible and aperiodic. Our next result gives a characterization of when $M$ is homothety in terms of $v_{\infty}$. To make the result transparent, note that, by Theorem 1, $v_{\infty}$ is constant on $\Delta(K)$, and as such is simply a function of $u$ and $M$. In our new characterization we let $u$ vary over the space of all continuous functions defined on $\Delta(K)$.Therefore $v_{\infty}$ also varies accordingly.

We start this section by reviewing the notion of a split, a cornerstone in the field of Bayesian persuasion. This can be described informally as follows: Given a lottery $X$ over $K$ with law $p\in\Delta(K)$, to which extent can the sender manipulate (split) $p$ using his signals. The answer, given by Blackwell (1951) and Aumann and Maschler (1995), is that for every choice of distributions $q_{1},...,q_{|S|}\in\Delta(K)$ and convex weights $(\alpha_{i})_{i=1}^{|S|}\in\Delta(S)$ s.t. $\sum_{i=1}^{|S|}\alpha_{i}q_{i}=p$, the sender can correlate his lottery over signals, $Y$, with the lottery $X$, so that on the event that $s^{i}\in S$ is chosen (having marginal probability $\alpha_{i}$) the posterior belief over states becomes $q_{i}$. This lottery $Y$ will obey the rule

Thus, if we denote by

the set of all possible splits in $p\in\Delta(K)$, then the signaling strategy $\sigma$ can be interpreted as follows: At the first stage of $\Gamma_{\lambda}(p)$, $\sigma$ specifies which element of $\SS_{p}$ the sender should pick. Then, for each time period $n\geq 2$, given that $p_{n-1}=q$ for some $q\in\Delta(K)$, $\sigma_{n}$ prescribes which element of $\SS_{qM}$ the sender should pick. Indeed, prior to getting the signal $s_{n}$, the receiver updates her belief on the distribution of $X_{n}$, by taking the multiplication of her posterior belief $q$ on the distribution of $X_{n-1}$ with the transition matrix $M$, resulting in the belief $qM$. It thus follows that the sequence $(p_{n})$ satisfies the following important distributional law:

Consequently, $\mathbb{E}_{p,\sigma}\,p_{n+1}=(\mathbb{E}_{p,\sigma}p_{1})M^{n}=pM^{n}$ for every $n\geq 1$. In particular if $p=\pi_{M}$, then $\mathbb{E}_{\pi_{M},\sigma}\,p_{n}=\pi_{M}$ for every $n\geq 1$.

In light of this fresh view of $\sigma$, standard arguments (e.g., Theorem 2.20 in [25]) lead to the following ‘Bellman type’ recursive formula for $v_{\lambda}(p)$:

Consider the operator $\phi:\Delta(K)\to\Delta(K)$ defined by $\phi(q)=qM$. Since $|S|\geq k$, Carathéodory’s Theorem (see, e.g., Corollary 17.1.5 in [24]) implies that the expression on the right-hand side of Eq. (14) equals $(\text{Cav}\,\{(1-\lambda)u+\lambda v_{\lambda}\circ\phi\})(p)$. Thus, in conjunction with Eq. (14) we obtain the following key relation:

In particular, this shows that the function $v_{\lambda}:\Delta(K)\to\mathbb{R}$ is concave for every $\lambda$. As $\phi$ is linear, $v_{\lambda}\circ\phi$ is also concave. Then, by the definition of Cav we infer from Eq. (15) the following two-sided inequality:

Since the sender can always decide to not reveal any information at $p$, i.e., to choose the split $\{(q_{i},\alpha_{i})\}_{i}\in\SS_{p}$, where $q_{i}=p$ for all $i=1,...,|S|$, and thereafter play optimally in the game $\Gamma_{\lambda}(pM)$, we also have that $v_{\lambda}(p)\geq(1-\lambda)u(p)+\lambda(v_{\lambda}\circ\phi)(p)$. The latter combined with the right hand side of Eq. (16) gives the following result:

Set $\underline{v}(p):=\liminf_{\lambda\to 1^{-}}v_{\lambda}(p)$ and $\bar{v}(p):=\limsup_{\lambda\to 1^{-}}v_{\lambda}(p)$. Then, by (16), $\underline{v}(p)=\underline{v}(pM)$ and $\bar{v}(p)=\bar{v}(pM)$ for every $p\in\Delta(K)$. As our Markov chain is irreducible and aperiodic, the Convergence Theorem for Markov chains ensures that $pM^{n}\to\pi_{M}$ as $n\to\infty$. A combination of the above two arguments yields the following proposition.