## Bayesian Persuasion with Sequential Games

Andrea Celli Politecnico di Milano andrea.celli@polimi.it

Stefano Coniglio University of Southampton s.coniglio@soton.ac.uk

## Nicola Gatti

Politecnico di Milano nicola.gatti@polimi.it

## Abstract

We study an information-structure design problem (a.k.a. persuasion) with a single sender and multiple receivers with actions of a priori unknown types, independently drawn from action-specific marginal distributions. As in the standard Bayesian persuasion model, the sender has access to additional information regarding the action types, which she can exploit when committing to a (noisy) signaling scheme through which she sends a private signal to each receiver. The novelty of our model is in considering the case where the receivers interact in a sequential game with imperfect information , with utilities depending on the game outcome and the realized action types. After formalizing the notions of ex ante and ex interim persuasiveness (which differ in the time at which the receivers commit to following the sender's signaling scheme), we investigate the continuous optimization problem of computing a signaling scheme which maximizes the sender's expected revenue. We show that computing an optimal ex ante persuasive signaling scheme is NP -hard when there are three or more receivers. In contrast with previous hardness results for ex interim persuasion, we show that, for games with two receivers, an optimal ex ante persuasive signaling scheme can be computed in polynomial time thanks to a novel algorithm based on the ellipsoid method which we propose.

## 1 Introduction

Bayesian persuasion revolves around influencing the behavior of self-interested agents through the provision of payoff-relevant information [20]. Differently from traditional mechanism design , where the designer influences the outcome by providing tangible incentives, in Bayesian persuasion the designer influences the outcome by deciding who gets to know what [8]. Real-world applications are ubiquitous. For instance, this framework has been recently applied to security problems [28, 35, 36], financial-sector stress testing [16], voter coalition formation [1], and online advertisement [4, 14].

The classical Bayesian persuasion model involves a single sender and a single receiver where the sender, who has access to some private information, designs a signaling scheme in order to persuade the receiver to select a favorable action. The model assumes the sender's commitment power. This hypothesis is realistic in many settings where reputation and credibility are a key factor for the long-term utility of the sender [29], as well as whenever an automated signaling scheme either has to abide by a contractual service agreement or it is enforced by a trusted authority [10].

The extension to the case with multiple receivers is of major interest (see, e.g., its applications to private-value auctions [22]). In this setting, most of the works assume a public signal model in which all the receivers observe the same information [13, 1, 11]. A more general setting is the private signal one, in which the sender may tailor receiver-specific signals. Persuasion with private signals has

Preprint. Under review.

been explored only in very specific settings, such as two-agents two-action games [31], unanimity elections [5], binary auctions with no inter-agent externalities [2, 3], and voting with binary action spaces and binary states of Nature [34]. As pointed out by Dughmi [10], the problem of computing private signaling schemes in multi-receivers settings still lacks a general algorithmic framework.

Differently from classical Bayesian persuasion models, which typically assume that the receivers take their actions simultaneously [10, 21], we address, for the first time in the literature (to the best of our knowledge), the multi-receiver case with sequential interactions among receivers. As most of the real-world economic interactions take place sequentially, this allows for a greater modeling flexibility which could be exploited in the context of, e.g, sequential auctions [25]. In the paper, we show how to address sequential, multi-receiver settings algorithmically via the notion of ex ante persuasive signaling scheme, where receivers commit to following the sender's recommendations by only observing the signaling scheme. This is motivated by the fact that the classical notion of persuasiveness ( ex interim persuasiveness) which allows the receivers to deviate after observing the sender's signal renders most of the associated design problems (with the exception of very narrow settings) computationally intractable [12], ultimately making its adoption impractical in real-world applications where the receivers act sequentially.

Ex ante persuasive signaling schemes may be employed every time the environment allows for a credible receivers' commitment before the recommendations are revealed. As argued by Kamenica and Gentzkow [20], this is not unrealistic. On a general level, the receivers will uphold their ex ante commitment every time they reason with a long-term horizon where a reputation for credibility positively affects their utility [29]. In some cases, they could also be forced to stick to their ex ante commitment by contractual agreements. Many real-world problems involve ex ante commitments. This is the case, for example, of sequential auction in online advertising, where a (trusted) third party service (e.g., programmatic advertising platforms) could allow bidders for coordinated behaviors during the sequential auction, leading to better outcomes in terms of bidders' payoffs, and to more efficient allocations of the ads.

Original contributions . We investigate persuasion games with multiple receivers interacting in a sequential game, and study the continuous optimization problem of computing a private signaling scheme which maximizes the sender's expected utility. We focus on the framework with independent action types, similarly to what is done by Dughmi and Xu [12]. We introduce the notion of ex ante persuasive signaling scheme, and formalize its differences from ex interim persuasive schemes. Motivated by the hardness results for the ex interim setting with simultaneous moves provided by Dughmi and Xu [12], we study the problem of computing optimal ex ante signaling schemes. We show that one such scheme may be computed in polynomial time in settings with two receivers and independent action types, which makes ex ante persuasive signaling schemes a plausible persuasion tool in practice. In proving this result, we show that, given any behavioral strategy of a perfect-recall player, it is possible to find, in polynomial time, a realization-equivalent mixed strategy with a polynomially-sized support. when there are three or more receivers. Moreover, we show that the case with two receivers is the largest one, in terms of players, in which the problem of computing an optimal ex ante signaling scheme is tractable by showing that with three or more receivers the problem is NP -hard.

## 2 Bayesian Persuasion with Sequential Games

We assume, in our model, a sender denoted by S and a set of receivers R = { 1 , . . . , n } . Each receiver i ∈ R is faced with the problem of selecting actions from a set A i with a priori uncertain payoffs. We adopt the perspective of the sender, whose goal is persuading the receivers to take actions which are favorable for her. The fundamental feature of our model is that receivers confront themselves in a sequential decision problem, which we describe as an extensive-form game (EFG) with imperfect information and perfect recall.

Payoffs are a function of the actions taken by the receivers and of an unknown state of nature θ , drawn from a set of potential realizations Θ . We follow the standard framework of Dughmi and Xu [12] where each action a has a set of possible types Θ a and in which a state of nature θ is a vector specifying the realized type of each action of the receivers, i.e., θ ∈ Θ = × × i ∈R a ∈ A i Θ a . 1 We assume action types which are drawn independently from action-specific marginal distributions. We

1 Standard (i.e., non Bayesian) EFGs can be represented by assigning to each Θ a a singleton. Note that this model also encompasses Bayesian games á la Harsanyi [18].

denote them by ˜ π a ∈ int (∆ | Θ a | ) , where ˜ π a ( ) t is the probability of a having type t ∈ Θ a . 2 These marginal distributions form a common prior over the states of nature which we assume to be known explicitly to both sender and receivers. This common knowledge can be equivalently represented by the distribution µ 0 ∈ ∆ | Θ | , where µ 0 ( θ ) = ∏ i ∈R ∏ a ∈ A i ˜ π a ( θ a ) .

We now provide some background on EFGs, and describe our two models of optimal signaling .

## 2.1 Background on EFGs

An EFG-here denoted by Γ -is composed of a set H of nodes, each of which identified by the ordered sequence of actions leading to it from the root node. The set of terminal nodes of the game is denoted by Z ⊆ H . The game is played by the receivers R . A i is the set of actions available to each receiver i ∈ R . Let A = { A i } i ∈R . For each nonterminal node h ∈ H \ Z , we denote by, respectively, P h ( ) and A h ( ) the unique receiver acting at h and the set of actions available at that node. Imperfect information is represented via information sets (or infosets ), which group together decision nodes which are indistinguishable for a certain receiver. For each receiver i , we denote her set of infosets by I i . I i defines a partition of { h ∈ H | P h ( ) = i } . Each I ∈ I i is such that A h ( ) = A h ( ′ ) ∀ h, h ′ ∈ I . To simplify the notation, let A I ( ) be the set of actions available at each decision node in I . Receiver i has perfect recall if she has perfect memory of her past actions and observations.

We denote a behavioral strategy of receiver i by π i . It corresponds to a vector defining a probability distribution over A I ( ) , ∀ I ∈ I i . Given π i , let π i,I be the (sub)vector representing the probability distribution at I ∈ I i . Letting, for each receiver i , Σ = i × I ∈I i A I ( ) , a plan is a vector σ i ∈ Σ i which specifies an action for each of the receiver's infosets. We denote by σ i ( I ) the action selected at infoset I ∈ I i . Letting Σ = × i ∈P Σ i , we denote by σ ∈ Σ the tuple which specifies the plan chosen by each receiver. Finally, a mixed strategy x i is a probability distribution over Σ i . We let X i be the mixed strategy space of receiver i , and X be the set of joint probability distributions over Σ .

The sequence form [24, 32] of a game is a compact representation applicable to games with perfect recall. It decomposes strategies into sequences of actions and their realization probabilities. A sequence q i for receiver i associated with a node h is a tuple specifying receiver i 's actions on the path from the root to h . We denote the set of all sequences for receiver i by Q i . A sequence is said terminal if, together with some sequences of the other receivers, leads to a terminal node. We let q ∅ be the fictitious sequence leading to the root node and qa the extended sequence obtained by appending action a to q . A sequence-form strategy (or realization plan ) for a receiver i is a function r i : Q i → [0 , 1] such that r i ( q ∅ ) = 1 and, for each I ∈ I i and sequence q leading to I , -r i ( q ) + ∑ a ∈ A I ( ) r i ( qa ) = 0 . We denote by Q I ( ) the set of sequences originating in I . For each q ∈ Q i , we denote by I ↓ ( q ) ⊆ I i the set of infosets reachable by i after selecting q without making other intermediate moves, whereas I ↑ ( q ) ∈ I i denotes the unique infoset where the last action of q was taken. 3 We call two strategies of receiver i realization equivalent if, for any fixed strategy of the other receivers, they induce the same distribution over Z .

## 2.2 Ex interim Persuasiveness

Let u S : Σ × Θ → R and u i : Σ × Θ → R be the payoff functions of the sender and receiver i ∈ R . We assume that the sender is allowed to tailor signals to individual receivers through private communications. Let Ω i be the set of signals available to receiver i , and let Ω = × i ∈R Ω i . We assume that the sender has access to private information and her goal is designing a signaling scheme ϕ : Θ → ∆ | Ω | to persuade the receivers to select actions which are favorable for her. We denote by ϕ θ the probability distribution over Ω having observed θ . In the classical Bayesian persuasion framework [20], the receivers decide their behavior after observing the sender's signal and updating their posterior over Θ accordingly. The sender-receivers interaction goes as follows:

- · The sender chooses ϕ and publicly discloses it.
- · Nature draws a state θ ∼ µ 0 , observed by the sender.

2 int ( X ) is the interior of set X , and ∆ | X | is the set of all probability distributions on X .

3 When the context requires disambiguation between different games, we write I Γ ↓ ( q ) to denote the result for EFG Γ .

- · The sender draws a tuple ω ∼ ϕ θ and privately sends signal ω i to each receiver i ∈ R .
- · Sender and receivers receive, respectively, payoffs u S ( θ, σ ) and u i ( θ, σ ) , for all i ∈ R .
- · Each receiver i updates her posterior distribution knowing ϕ and having observed ω i . Then, each of the receivers selects a plan σ i ∈ Σ i . Together, their joint choices form the tuple σ = ( σ , . . . , σ 1 n ) .

In this setting, a result similar to the revelation principle (see, e.g., [27]) holds. Specifically, an optimal signaling scheme (i.e., a signaling scheme maximizing the sender's expected utility) can always be obtained by restricting the set of signals Ω to the set of plans Σ (see [20, Proposition 1]). In the following, we assume Ω = Σ (i.e., the sender recommends a plan to follow to each receiver). The receivers have an incentive to follow the sender's recommendation ˆ σ i if the recommended plan is preferred to any other action, conditional on the knowledge of ˆ σ i . We call this condition ex interim persuasiveness , which is precisely the kind of constraint characterizing a Bayes correlated equilibrium (BCE) [6, 7]. We remark that, according to the definition of BCE, the signaling scheme must necessarily be defined on plans and cannot be compactly represented by using sequences or actions.

Definition 1 ( Ex interim persuasiveness) . A signaling scheme ϕ : Θ → ∆ | Σ | is ex interim persuasive if the following holds for all i ∈ R and σ , σ i ′ i ∈ Σ i :

Definition 2. A signaling scheme ϕ : Θ → ∆ | Σ | is a BCE if it is ex interim persuasive.

$$\lambda _ { 1 } \circ \lambda _ { 2 } \circ \lambda _ { 3 }$$

## 2.3 Ex ante Persuasiveness

We introduce the setting in which receivers have to decide whether to follow the sender's recommendations before actually observing them, basing their decision only on the knowledge of µ 0 and ϕ . 4 The interaction between sender and receivers goes as follows:

- · The sender computes ϕ , and publicly discloses it.
- · Nature draws a state θ ∼ µ 0 , observed by the sender.
- · The receivers decide whether to adhere to the recommendations drawn according to ϕ or not.
- · If i ∈ R decided to opt-in to the signaling scheme:
- ◦ receiver i acts according to the recommended ˆ σ i .
- ◦ the sender draws ˆ σ i ∼ ϕ θ and privately communicates it to receiver i ;
- · Sender and receivers receive, respectively, payoffs u S ( θ, σ ) and u i ( θ, σ ) , ∀ i ∈ R , where σ i = ˆ σ i if i adhered to the scheme.

In this setting, the receivers adhere to the signaling scheme (i.e., σ i = ˆ σ i ) if it is ex ante persuasive:

Definition 3 ( Ex ante persuasiveness) . The signaling scheme ϕ : Θ → ∆ | Σ | is ex ante persuasive if, for all i ∈ R and σ i ∈ Σ i , the following holds:

$$\begin{array} {$$

Such constraints characterize Bayes coarse correlated equilibria (BCCE), i.e., the generalization of coarse correlated equilibria to incomplete-information games (see [15, 19, 9]): 5

Definition 4. A signaling scheme ϕ : Θ → ∆ | Σ | is a BCCE if it is ex ante persuasive.

## 2.4 Comparison

Figure 1 summarizes the interaction flow between sender and receivers in the two settings described above. The key difference is the time at which the receivers decide whether to adhere to the signaling scheme or not. We also propose the following illustrative example (in the basic single-receiver setting)

4 The receivers' commitment to follow a certain signaling scheme is not an unrealistic assumption for the same reason why it is realistic to assume the sender's commitment power (see Section 1).

5 The set of (non Bayesian) coarse correlated equilibria is characterized by the constraints of Definition 3, with | Θ a | = 1 ∀ a ∈ A .

Figure 1: Left: Interaction between sender and receivers in the ex ante and ex interim setting. Right: A game where ex ante persuasion guarantees the sender a higher expected utility with respect to ex interim persuasiveness.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00877v1-figure-c8626e18-2715-4198-8334-4044705f7f8a.jpg)

| choose   | observe                    | draw                                             |    | In Out       | P       |             |
|----------|----------------------------|--------------------------------------------------|----|--------------|---------|-------------|
| S ⇒ ϕ    | θ ∼ µ 0 ˆ σ ∼ ϕ θ          | u S                                              | E  | ( - 1 , 1)   | (1 , 0) | (0 , 1 / 2) |
| time R ⇒ | observe ϕ ex ante decision | observe ˆ σ i choose σ i u i ex interim decision | H  | ( - 1 , - 1) | (1 , 0) | (0 , 0)     |

to further illustrate the fundamental differences between the two notions of persuasiveness.

Example 1. The incumbent of an industry wants to persuade a potential new entrant to the market. The market can be either easy ( E ), with probability 0.3, or hard ( H ). The incumbent knows the state of the market. The entrant has three possible actions: entering the market ( In ), staying out of the market ( Out ), or proposing a partnership to the incumbent ( P ). Figure 1 depicts the utility matrix for the game (the first values are incumbent's payoffs).

The incumbent wants the entrant to stay out of the market, values its entrance negatively, and is indifferent towards a partnership. The entrant values entering the new market positively only when it has favorable conditions. A partnership in a hard market gives the entrant 0 (rather than a negative score) as no fixed costs have to be sustained. In this setting, forcing the entrant (contractually) to commit to following the incumbent's recommendations ex ante is strictly better (in terms of expected utility) for the incumbent.

An optimal ex ante signaling scheme (e.g., ϕ E ( In ) = ϕ E ( Out ) = 1 2 , ϕ H ( Out ) = 1 ) guarantees the sender an expected utility of 0 7 . . An optimal ex interim signaling scheme (e.g., ϕ E ( P ) = 1 , ϕ H ( Out ) = 11 14 , ϕ H ( P ) = 3 14 ,) guarantees a sender's expected utility of 0.55. Therefore, ex ante persuasion provides a 27% increase in utility for the incumbent w.r.t. ex interim persuasion.

We remark that the set of ex ante persuasive signaling schemes strictly includes the set of ex interim signaling schemes. In particular, an optimal ex ante persuasive signaling scheme may lead to an expected utility for the sender arbitrarily larger than the one she would obtain with an optimal ex interim scheme. This is shown via the following example:

Example 2. Consider the game in Figure 2, with two receivers with one information set each ( I 1 for receiver 1 and I 2 for receiver 2), and parametric in k glyph[greatermuch] 1 . Action a 1 1 ∈ A 1 is such that Θ a 1 1 = { t 1 , t 2 } and ˜ π a 1 1 ( t 1 ) = ˜ π a 1 1 ( t 2 ) = 1 2 / . The figure only reports the receivers' utilities, as we assume u S ( θ, σ ) = u 1 ( θ, σ ) + u 2 ( θ, σ ) , ∀ ( θ, σ ) . The signaling scheme with ϕ ′ t 1 ( a , a 1 1 1 2 ) = 1 / 2 , ϕ ′ t 1 ( a , a 2 1 2 2 ) = 1 / 2 , and ϕ ′ t 2 ( a , a 1 1 3 2 ) = 1 is ex ante persuasive but not ex interim persuasive. The optimal ex interim persuasive signaling scheme is such that ϕ ′′ t 1 ( a , a 2 1 2 2 ) = 1 , and ϕ ′′ t 2 ( a , a 1 1 3 2 ) = 1 . Scheme

Figure 2: A game with two receivers in which action a 1 1 has two possible types t 1 and t 2 . Terminal nodes report receivers' utilities.

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.00877v1-figure-88baf0d6-35ac-411a-a3dc-0f8282aedad9.jpg)

ϕ ′ grants the sender an expected utility of ( k +5) 4 / , while scheme ϕ ′′ guarantees 3 / 2 . Therefore, for increasing values of k an optimal ex ante signaling scheme provides an arbitrarily larger utility than what can be obtained by ex interim persuasion.

## 3 Positive Result

In the independent-actions setting, it is known that computing an optimal ex interim signaling scheme is # P -hard even with a single receiver [12]. Motivated by this negative result, we study the problem of computing an optimal (for the sender) ex ante persuasive signaling scheme. We denote this problem by OPT-EA . It amounts to computing a coarse correlated equilibrium (CCE) for the game of complete information obtained by treating Nature as a player with a trivial (i.e., constant everywhere) payoff function and subject to having marginal strategies constrained to be equal to µ 0 .

In contrast with the known hardness results for the ex interim setting, we show that OPT-EA with |R| = 2 can be solved in polynomial time (see Theorem 5). To prove our main theorem, we first show how to build, in polynomial time, small (i.e., with a support of polynomial size) mixed strategies which are realization-equivalent to a given behavioral strategy. Omitted proofs are presented in Appendix A.

## 3.1 Small Supported Mixed Strategies

Given a behavioral strategy profile π ∗ i for a generic perfect-recall player i , we show (see Theorem 4) that it is always possible to compute in polynomial time some x ∗ i ∈ X i such that (i) it is realizationequivalent to π ∗ i and (ii) it has a support of polynomial size. 6

For each σ i ∈ Σ i , let ξ σ ( i ) := { q ∈ Q i |∃ I ∈ I i , σ i ( I ) = q } (i.e., the set of sequences selected with probability 1 in a realization plan equivalent to σ i ). Analogously, ∀ σ = ( σ , σ 1 2 ) ∈ Σ we denote by ξ σ ( ) the set of tuples ( q 1 , q 2 ) such that q 1 ∈ ξ σ ( 1 ) and q 2 ∈ ξ σ ( 2 ) . In the remainder of the section, we drop the dependency on i when not strictly necessary. We denote by M an | Q i | × | Σ i | matrix where M q,σ ( ) = 1 iff q ∈ ξ σ ( ) and M q,σ ( ) = 0 otherwise. We denote by M q the row of M specifying the plans containing q in their support. Let r ∗ be the | Q i | -dimensional vector representing the realization plan of player i which is realization-equivalent to π ∗ . In order to compute x ∗ , it is enough to find an optimal solution to LP max x ∈ R | Σ i | { 1 glyph[latticetop] x s.t. Mx ≤ r ∗ } , which we denote

≥ 0 by A , which has a polynomial number of constraints and an exponential number of variables.

By relying on the assumption of perfect recall and proceeding by contradiction, we establish the following lemma:

Lemma 1. An optimal solution x ∗ to A satisfies Mx ∗ = r ∗ .

We now characterize an optimal solution to A by two properties which are proven by using Lemma 1 and the fact that, as LP A contains a polynomial number of constraints, it admits an optimal basic solution with only a polynomial number of nonzero variables:

Theorem 2. These two properties hold: (i) An optimal solution x ∗ to A is a normal-form strategy ( x ∗ ∈ X i ) realization equivalent to r ∗ , (ii) there exists an optimal solution x ∗ with supp ( x ∗ ) of polynomial size.

Let D be the dual of problem A . By showing that an optimal plan corresponding to a violated dual constraint can be found in polynomial time by backward induction, we establish the following:

Lemma 3. D admits a polynomial-time separation oracle.

Next, by relying on Lemma 3 and on the ellipsoid method we prove a result which is the basis for our main theorem, Theorem 5 (whose statement and proof are given in full in the next subsection):

Theorem 4. Given an EFG, a perfect-recall player i , and a behavioral strategy profile π ∗ for i (with the realization-equivalent realization plan r ∗ ), a solution to LP A can be found in polynomial time.

Finally, we show that we can efficiently compute a solution with support size of at most | Q i | by applying the ellipsoid method for at most a polynomial number of iterations:

Corollary 4.1. A basic feasible solution to

A can be computed in polynomial time.

## 3.2 Optimal Ex Ante Persuasive Schemes

Computing an ex ante persuasive signaling scheme is equivalent to computing a CCE for an EFG of complete information where Nature is treated as a player with constant utility and marginal strategies constrained to be equal to µ 0 . We focus on the setting where |R| = 2 and show that OPT-EA can be solved in polynomial time. We reason over an auxiliary game such that each action of the receivers is followed by one of Nature's nodes, determining its type. Marginal probabilities ˜ π determining action types are treated as behavioral strategies of the Nature player, which we denote by N . Formally:

Definition 5. Given an EFG Γ describing the interaction between receivers and a set of marginal distributions { ˜ π a ∈ int (∆ | Θ a | ) } a ∈ A , the auxiliary game ˆ Γ is an EFG such that:

6 As customary, we define the support of a mixed strategy x i ∈ X i as supp ( x i ) := { σ i ∈ Σ i | x i ( σ i ) &gt; 0 } .

- · It has a set of players R∪{ } N .
- · The receivers have the same information structures as in Γ , i.e., ∀ i ∈ R I , i = ˆ I i , and ∀ q ∈ Q i , I Γ ↓ ( q ) = I ˆ Γ ↓ ( q ) .
- · For each receiver i ∈ R , her utility function is the same as in Γ , i.e., ∀ ( θ, σ ) ∈ Θ × Σ , u i ( θ, σ ) = ˆ ( u i θ, σ ) . Nature has ˆ u N ( ) = · k ∈ R constant everywhere.
- · ∀ i ∈ R , each a ∈ A i is immediately followed by a singleton infoset I ∈ I N such that A I ( ) = Θ a .
- · ∀ I ∈ I N , with I following a ∈ A , N selects actions (types) at I according to the marginal distribution ˜ π a .

The first step is devising an LP to compute a BCCE with a polynomial number of constraints and an exponential number of variables. We do so by providing an LP to find an optimal CCE over ˆ Γ . First, notice that θ is a plan of player N in ˆ Γ . A distribution in ∆ | Θ | is a mixed strategy of N . Denote by µ ∗ the mixed strategy realization equivalent to ˜ π computed (in poly-time) as in the proof of Theorem 4. Let Θ ∗ := supp ( µ ∗ ) . Due to Corollary 4.1, the set Θ ∗ has polynomial size. Then, we write the problem as a function of γ ∈ ∆ | Σ × Θ ∗ | (i.e., we look for a correlated distribution in ˆ Γ , encompassing the Nature player). Let v i be the |I | i -dimensional vector of variables of the dual of the best-response problem for receiver i in sequence form. Moreover, we employ sparse ( |R| +1) -dimensional matrices describing the utility function of sender and receivers for the profiles ( θ, q 1 , q 2 ) leading to terminal nodes of ˆ Γ . We denote them by U i ∈ R | Θ ∗ |×| Q 1 |×| Q 2 | , with i ∈ R ∪ { S } . 7 In the following, we let q = ( q 1 , q 2 ) . The problem of computing a CCE over ˆ Γ reads:

$$q = ( q _ { 1 }, q _ { 2 } ). \, \text{$$$

$$\sigma \in \Sigma$$

We make the following observations on the above LP, which we denote by B :

- · The left term of constr. (2) is the expected utility of i at the equilibrium. Incentive constraints (3) and (4) are compactly encoded by exploiting the sequence form. Intuitively, we decompose the best-response problem locally at each infoset. The constraints impose that the utility at the equilibrium be no smaller than the value achieved when playing the plan obtained by letting the receiver best respond at each infoset.
- · Constraint (5) forces Nature's marginal distribution to equal the prior µ ∗ .
- · Once a solution γ ∗ to B has been computed, an optimal solution to OPT-EA is the signaling scheme which, having observed θ , recommends σ with probability γ ∗ ( θ, σ ) /µ ∗ ( θ ) .

```
ions on
y ( B ): \, \cfrac { \text{
```

The following key positive result holds:

Theorem 5. OPT-EA can be solved in polynomial time when |R| ≤ 2 .

7 U i employs both the sequence form (for receivers), and plans of N . However, polynomiality of Θ ∗ implies polynomiality of U i .

Proof. Let D B be the dual of B . Let α 1 , α 2 be the dual variables of constraints (2), β 1 ∈ R | Q 1 | and β 2 ∈ R | Q 2 | the dual variables of (3) and (4), and δ ∈ R | Θ ∗ | the dual variables of (5). We show that, given (¯ α , α 1 ¯ 2 , β ¯ 1 , β ¯ 2 , δ ¯ ) , the problem of finding either a hyperplane separating the solution from the feasible set of D B or proving that no such hyperplane exists can be solved in polynomial time. Along the lines of Theorem 4, this implies that B is solvable in polynomial time by the ellipsoid method. As the number of dual constraints corresponding to variables v i is linear, all these constraints can be checked efficiently for violation. Besides those, the dual problem D B features the following constraint for each ( θ, σ ) ∈ Θ ∗ × Σ :

$$\sum _ { i \in \mathcal { R } } \sum _ { q \in \xi ( \sigma ) } U _ { i } ( \theta, q ) \bar { \alpha } _ { i } + \frac { \bar { \delta } ( \theta ) } { \mu ^ { * } ( \theta ) } - \sum _ { q \in \xi ( \sigma ) } U _ { S } ( \theta, q ) - \sum _ { q \in Q _ { 1 } \times \xi ( \sigma _ { 2 } ) } U _ { 1 } ( \theta, q ) \bar { \beta } _ { 1 } ( q _ { 1 } ) - \sum _ { q \in \xi ( \sigma _ { 1 } ) \times Q _ { 2 } } U _ { 2 } ( \theta, q ) \bar { \beta } _ { 2 } ( q _ { 2 } ) \geq 0.$$

Given (¯ α , α 1 ¯ 2 , β ¯ 1 , β ¯ 2 , δ ¯ ) , the separation problem of finding a maximally violated inequality of D B reads:

$$\min _ { \theta, \sigma } \left \{ \sum _ { q \in \xi ( \sigma ) } \left [ \sum _ { i \in \mathcal { R } } U _ { i } ( \theta, q ) - U _ { S } ( \theta, q ) \right ] + \frac { \tilde { \delta } ( \theta ) } { \mu ^ { * } ( \theta ) } \, - \sum _ { q \in Q _ { 1 } \times \xi ( \sigma _ { 2 } ) } U _ { 1 } ( \theta, q ) \tilde { \beta } _ { 1 } ( q _ { 1 } ) \, - \sum _ { q \in \xi ( \sigma _ { 1 } ) \times Q _ { 2 } } U _ { 2 } ( \theta, q ) \tilde { \beta } _ { 2 } ( q _ { 2 } ) } \right \}.$$

A pair ( θ, σ ) yielding a violated inequality exists iff the separation problem admits an optimal solution of value &lt; 0 . If such a ( θ, σ ) exists, it can be determined in polynomial time by enumerating over the (polynomially many) ( θ, z ) ∈ Θ ∗ × ˆ Z , where ˆ Z is the outcomes set of ˆ Γ . For each pair ( θ, z ) , we look for a σ ∈ Σ which, together with some actions of N , minimizes the objective function of the separation problem and could lead to z . The procedure halts as soon as a plan σ such that ( θ, σ ) yielding a violated inequality is found; if it terminates without finding any, D B has been solved. First, by fixing a pair ( θ, z ) the first two terms of the objective function are completely determined. The remaining terms can be minimized independently for each receiver. Let us consider the problem of finding σ 2 ∈ Σ 2 (the other one is solved analogously). It reads max σ 2 ∈ Σ 2 { ∑ q 1 ∈ Q 1 ∑ q 2 ∈ ξ σ ( 2 ) U 1 ( θ, q 1 , q 2 ) ¯ β 1 ( q 1 ) } , subject to the constraint that σ 2 is an admissible plan for the given z (i.e., given the solution plan, it has to be possible to reach z together with some actions of the other players). This problem can be solved in poly-time as shown in Algorithm 1, where I z i and Q z i are, respectively, the set of infosets and sequences of i encountered on the path from the root to z . Once Q ∗ has been determined by visiting each I ∈ I 2 , the corresponding optimal σ 2 can be built directly. As in Corollary 4.1, an optimal solution to B has polynomial support size. Then, it is used to determine an optimal solution to OPT-EA in poly-time.

## 4 Negative Result

We conclude by showing that the approach of Section 3.2 cannot be extended to settings where |R| &gt; 2 and that, in particular, the border between easy and hard cases coincides with |R| = 2 . Indeed, the fact that computing an optimal CCE for a three-player EFG is NP -hard [33, Th. 1.3] directly implies the following:

Theorem 6. OPT-EA is NP -hard when |R| &gt; 2 .

In terms of D B , as a consequence of the equivalence between optimization and separation [17] the previous results maps in the following:

Theorem 7. Computing an optimal solution to D B is NP -hard when |R| &gt; 2 .

## 5 Discussion

We have studied persuasion in the multi-receiver setting with private signals, introducing, for the first time, a model encompassing receivers with sequential interactions, as well as the notion of ex ante persuasiveness. In contrast with previous complexity results on computing optimal CCEs and optimal ex interim persuasive schemes, we have shown that with |R| ≤ 2 an optimal ex ante scheme can be computed in polynomial time with the ellipsoid method by relying on a polynomial-time separation oracle. We have also shown that |R| = 2 constitutes the border between easy and hard cases as, even for |R| = 3 , the problem is NP -hard.

## References

- [1] R. Alonso and O. Câmara. Persuading voters. AM ECON REV , 106(11):3590-3605, 2016.
- [2] I. Arieli and Y . Babichenko. Private Bayesian persuasion. Available at SSRN 2721307 , 2016.
- [3] Y. Babichenko and S. Barman. Computational aspects of private Bayesian persuasion. arXiv:1603.01444 , 2016.
- [4] A. Badanidiyuru, K. Bhawalkar, and H. Xu. Targeting and signaling in ad auctions. In ACM-SIAM SODA , pages 2545-2563. SIAM, 2018.
- [5] A. Bardhi and Y. Guo. Modes of persuasion toward unanimous consent. THEOR ECON , 13(3): 1111-1149, 2018.
- [6] D. Bergemann and S. Morris. Robust predictions in games with incomplete information. ECONOMETRICA , 81(4):1251-1308, 2013.
- [7] D. Bergemann and S. Morris. Bayes correlated equilibrium and the comparison of information structures in games. THEOR ECON , 11(2):487-522, 2016.
- [8] D. Bergemann and S. Morris. Information design, Bayesian persuasion, and Bayes correlated equilibrium. AM ECON REV , 106(5):586-91, 2016.
- [9] I. Caragiannis, C. Kaklamanis, P. Kanellopoulos, M. Kyropoulou, B. Lucier, P.L. Renato, E. Tardos, et al. Bounding the inefficiency of outcomes in generalized second price auctions. J ECON THEORY , 156(C):343-388, 2015.
- [10] S. Dughmi. Algorithmic information structure design: a survey. ACM SIGEC EX , 15(2):2-24, 2017.
- [11] S. Dughmi. On the hardness of designing public signals. GAME ECON BEHAV , 2018.
- [12] S. Dughmi and H. Xu. Algorithmic Bayesian persuasion. In ACM STOC , pages 412-425. ACM, 2016.
- [13] S. Dughmi, N. Immorlica, and A. Roth. Constrained signaling in auction design. In ACM-SIAM SODA , pages 1341-1357, 2014.
- [14] Y. Emek, M. Feldman, I. Gamzu, R. Paes Leme, and M. Tennenholtz. Signaling schemes for revenue maximization. In ACM EC , pages 514-531, 2012.
- [15] F. Forges. Five legitimate definitions of correlated equilibrium in games with incomplete information. THEOR DECIS , 35(3):277-310, Nov 1993.
- [16] I. Goldstein and Y. Leitner. Stress tests and information disclosure. J ECON THEORY , 177: 34-69, 2018.
- [17] M. Grötschel, L. Lovász, and A. Schrijver. Geometric algorithms and combinatorial optimization . Springer Science &amp; Business Media, 2012.
- [18] John C Harsanyi. Games with incomplete information played by 'bayesian' players. MANAGE SCI , 14(3):159-182, 320-334, 486-502, 1967.
- [19] J. Hartline, V. Syrgkanis, and E. Tardos. No-regret learning in Bayesian games. In NeurIPS , pages 3061-3069, 2015.
- [20] E. Kamenica and M. Gentzkow. Bayesian persuasion. AM ECON REV , 101(6):2590-2615, 2011.
- [21] Emir Kamenica. Bayesian persuasion and information design. ANNU REV ECON , 11, 2018.
- [22] Todd R Kaplan and Shmuel Zamir. The strategic use of seller information in private-value auctions. Hebrew University, Center For Rationality Working Paper , (221), 2000.

| [23]   | L. G. Khachiyan. Polynomial algorithms in linear programming. USSR Computational Mathe- matics and Mathematical Physics , 20(1):53-72, 1980.           |
|--------|--------------------------------------------------------------------------------------------------------------------------------------------------------|
| [24]   | D. Koller, N. Megiddo, and B. von Stengel. Efficient computation of equilibria for extensive two-person games. GAME ECON BEHAV , 14(2):247-259, 1996.  |
| [25]   | Renato Paes Leme, Vasilis Syrgkanis, and Éva Tardos. Sequential auctions and externalities. In ACM-SIAM SODA , pages 869-886. SIAM, 2012.              |
| [26]   | M. Maschler, E. Solan, and S. Zamir. Game Theory . Cambridge University Press, 2013.                                                                   |
| [27]   | R.B. Myerson. Incentive compatibility and the bargaining problem. ECONOMETRICA , 47(1): 61-73, 1979.                                                   |
| [28]   | Z. Rabinovich, A.X. Jiang, M. Jain, and H. Xu. Information disclosure as a means to security. In AAMAS , pages 645-653, 2015.                          |
| [29]   | L. Rayo and I. Segal. Optimal information disclosure. J POLIT ECON , 118(5):949-987, 2010.                                                             |
| [30]   | L.S. Shapley and R.N. Snow. Basic solutions of discrete games. Contributions to the Theory of Games , 1:27-35, 1950.                                   |
| [31]   | I. Taneva. Information design. AM ECON J-MICROECON , 2019. Forthcoming.                                                                                |
| [32]   | B. von Stengel. Efficient computation of behavior strategies. GAME ECON BEHAV , 14(2): 220-246, 1996.                                                  |
| [33]   | B. von Stengel and F. Forges. Extensive-form correlated equilibrium: Definition and computa- tional complexity. MATH OPER RES , 33(4):1002-1022, 2008. |
| [34]   | Yun Wang. Bayesian persuasion with multiple receivers. Available at SSRN 2625399 , 2013.                                                               |
| [35]   | H. Xu, Z. Rabinovich, S. Dughmi, and M. Tambe. Exploring information asymmetry in two-stage security games. In AAAI , pages 1057-1063, 2015.           |
| [36]   | H. Xu, R. Freeman, V. Conitzer, S. Dughmi, and M. Tambe. Signaling in Bayesian Stackelberg games. In AAMAS , pages 150-158, 2016.                      |

## A Omitted Proofs

Lemma 1. An optimal solution x ∗ to A satisfies Mx ∗ = r ∗ .

Proof. Consider a behavioral strategy π ∗ whose realization-equivalent realization plan is denoted by r ∗ . Since player i has perfect recall, there always exists at least a mixed strategy ˆ x ∈ X i realization equivalent to π ∗ [26, Th. 6.11]. Therefore, the optimal value of A is 1 (since 1 glyph[latticetop] ˆ = 1 x ). Given ˆ x ∈ X i , a distribution assigning to each sequence q ∈ Q i value ∑ σ ∈ Σ : i q ∈ ξ σ ( ) ˆ x σ is a valid realization plan. Therefore, if x ∈ ∆ | Σ i | , then Mx is a well defined realization plan for i . Now, by contradiction, assume that x ∗ is an optimal solution of A and that there exists q ′ ∈ Q i such that M x &lt; r q ′ ∗ ∗ ( q ′ ) . Optimality implies 1 glyph[latticetop] x ∗ = 1 and, therefore, x ∗ ∈ ∆ | Σ i | . Let Mx ∗ = r . We have r q ( ′ ) &lt; r ∗ ( q ′ ) . Since the sequence-form constraints hold, there must exist at least one q ′′ ∈ Q i such that r q ( ′′ ) &gt; r ∗ ( q ′′ ) . This leads to a contradiction since x ∗ would not be a feasible solution.

Theorem 2. These two properties hold: (i) An optimal solution x ∗ to A is a normal-form strategy ( x ∗ ∈ X i ) realization equivalent to r ∗ , (ii) there exists an optimal solution x ∗ with supp ( x ∗ ) of polynomial size.

Proof. Since Mx ∗ = r ∗ (Lemma 1), we have M x q ∅ ∗ = r ∗ ( q ∅ ) , that is 1 glyph[latticetop] x ∗ = 1 . Therefore, x ∗ ∈ X i . Realization equivalence follows from Lemma 1 and from the fact that Mx ∗ defines a valid realization plan. Moreover, LP A admits a basic optimal solution with at most | Q i | variables with strictly positive values [30]. Then, there exists an optimal x ∗ with support of polynomial size.

Lemma 3. D admits a polynomial-time separation oracle.

Proof. Let α ∈ R | Q i | be the vector of dual variables (corresponding to constraints Mx ≤ r ∗ ). D is an LP with a polynomial number of variables ( | Q i | ) and an exponential number of constraints ( | Σ i | ). We show that, given ¯ α ∈ R | Q i | , the problem of finding a hyperplane separating ¯ α from the set of feasible solutions to D or proving that no such hyperplane exists can be solved in polynomial time. The problem amounts to determining whether there exists a violated (dual) constraint M α glyph[latticetop] σ ¯ ≥ 1 for some σ ∈ Σ i . Given ¯ α , the separation problem of finding one such constraint of maximum violation reads: min σ ∈ Σ i { M α glyph[latticetop] σ ¯ } . A plan σ yielding a violated constraint exists iff the separation problem admits an optimal solution of value &lt; 1 . One such plan (if any) can be found in polynomial time by reasoning in a backward induction fashion, starting from information sets of i originating only terminal sequences, and proceeding backwards. At each I ∈ I i , player i selects ˆ q ∈ Q I ( ) such that ˆ q ∈ arg min q ∈ Q I ( ) { ∑ I ′ ∈ I ↓ ( q ) w I ′ +¯( ) α q } , and subsequently sets w I := ∑ I ′ ∈ I ↓ (ˆ) q w I ′ +¯(ˆ) α q . This procedure requires a computing time linear in |I | i . Then, a maximally violated inequality can be found by building a plan according to the sequences determined at the previous step.

Theorem 4. Given an EFG, a perfect-recall player i , and a behavioral strategy profile π ∗ for i (with the realization-equivalent realization plan r ∗ ), a solution to LP A can be found in polynomial time.

Proof. Due to the equivalence between optimization and separation [17], since the separation problem for D can be solved in polynomial time one can solve D in polynomial time via the ellipsoid method [23]. As the ellipsoid method solves a primal-dual system encompassing both D and A , it also produces a solution to A .

Corollary 4.1. A basic feasible solution to A can be computed in polynomial time.

Proof. First, the ellipsoid method returns an optimal solution x ∗ with polynomial support size (say | supp ( x ∗ ) | = m ). This is because the number of iterations is polynomial and, by adding a new inequality to the dual per iteration, we also add a new variable to the primal per each iteration. If x ∗ is a basic feasible solution, its support is necessarily the smallest possible and we can halt the procedure. If not, x ∗ belongs to the relative interior of a face of the polytope defined by A . Suppose to have { e x j } m j =1 = supp ( x ) , where e j is the canonical vector with a single 1 in position j . To obtain an optimal basic-feasible solution, we proceed as follows. Let j := 1 . First, we restrict A to the

optimal face by adding the constraint 1 glyph[latticetop] x = 1 glyph[latticetop] x ∗ . Then, we reoptimize the LP maximizing the objective function e x j . If we do not obtain a basic-feasible solution, we iterate the procedure adding the constraint e x j = e x j ∗ and letting j := j +1 . The dimension of the LP is reduced by 1 at each iteration (and the number of steps is polynomial, as we have one for each of the polynomially-many variables in supp ( x ∗ ) ). This leads to optimizing over faces of A of increasingly smaller dimension. When the dimension reaches 1, the corresponding solution is necessarily a basic one.

Theorem 6. OPT-EA is NP -hard when |R| &gt; 2 .

Proof. Let |R| = 3 and, ∀ a ∈ A , | Θ a | = 1 . Then, the problem amounts to computing an optimal CCE for a three player EFG, which is NP -hard since the reduction of [33, Th. 1.3] directly applies.

Theorem 7. Computing an optimal solution to D B is NP -hard when |R| &gt; 2 .

Proof. Consider the case in which R = 3 , and D B is adapted accordingly. Let q = ( q 1 , q 2 , q 3 ) . Given dual variables (¯ α , α 1 ¯ 2 , α ¯ 3 , β ¯ 1 , β ¯ 2 , β ¯ 3 , δ ¯ ) , the separation problem reads:

$$\min _ { \theta, \sigma } \left \{ \sum _ { \alpha \in \xi ( \sigma ) } \left [ \sum _ { i \in \Re } U _ { 1 } ( \theta, q ) - U _ { S } ( \theta, q ) \right ] + \frac { \tilde { \delta } ( \theta ) } { \mu ^ { * } ( \theta ) } \, - \sum _ { \alpha \in Q _ { 1 } \times \xi ( \sigma _ { 2 } ) \times \xi ( \sigma _ { 3 } ) } U _ { 1 } ( \theta, q ) \tilde { \beta } _ { 1 } ( q _ { 1 } ) - \sum _ { \alpha \in \xi ( \sigma _ { 1 } ) \times Q _ { 2 } \times \xi ( \sigma _ { 3 } ) } U _ { 3 } ( \theta, q ) \tilde { \beta } _ { 2 } ( q _ { 2 } ) - \sum _ { \alpha \in \xi ( \sigma _ { 1 } ) \times \xi ( \sigma _ { 2 } ) \times Q _ { 3 } } U _ { 3 } ( \theta, q ) \tilde { \beta } _ { 3 } ( q _ { 3 } ) \right \}.$$

Consider a setting with the following features: ∀ θ ∈ Θ ∗ , ¯ ( δ θ ) = 0 (a valid assumption since δ ∈ R | Θ ∗ | ) ; ∀ ( θ, q ) ∈ Θ ∗ × ( × i ∈R Q i ) , U S ( θ, q ) = U 1 ( θ, q ) ; ∀ ( θ, q ) ∈ Θ ∗ × × ( i ∈R Q i ) , U 2 ( θ, q ) = U 3 ( θ, q ) = 0 . Then, finding a maximally violated inequality corresponds to solving: arg max θ,σ 2 ,σ 3 { ∑ q ∈ Q 1 × ξ σ ( 2 ) × ξ σ ( 3 ) U 1 ( θ, q ) ¯ β 1 ( q 1 ) } . Let U ′ 1 ∈ R | Θ ∗ |×| Q 2 |×| Q 3 | be such that, for each ( θ, q 2 , q 3 ) , U ′ 1 ( θ, q 2 , q 3 ) = ∑ q 1 ∈ Q 1 U 1 ( θ, q 1 , q 2 , q 3 ) ¯ ( β q 1 ) . If Θ ∗ is a singleton, the problem becomes arg max σ ,σ 2 3 { ∑ ( q 2 ,q 3 ) ∈ ξ σ ( 2 ) × ξ σ ( 3 ) U ′ 1 ( q 1 , q 2 ) } . This is a joint best-response problem between receivers 2 and 3, which is known to be NP -hard [33]. Therefore, the separation problem for constraints corresponding to primal variables γ is NP -hard. Due to the equivalence between optimization and separation [17], it follows that it is NP -hard to solve D B .
Andrea Celli Stefano Coniglio Nicola Gatti
Bayesian Persuasion with Sequential Games
We study an information-structure design problem (a.k.a. persuasion) with a
single sender and multiple receivers with actions of a priori unknown types,
independently drawn from action-specific marginal distributions. As in the
standard Bayesian persuasion model, the sender has access to additional
information regarding the action types, which she can exploit when committing
to a (noisy) signaling scheme through which she sends a private signal to each
receiver. The novelty of our model is in considering the case where the
receivers interact in a sequential game with imperfect information, with
utilities depending on the game outcome and the realized action types. After
formalizing the notions of ex ante and ex interim persuasiveness (which differ
in the time at which the receivers commit to following the sender's signaling
scheme), we investigate the continuous optimization problem of computing a
signaling scheme which maximizes the sender's expected revenue. We show that
computing an optimal ex ante persuasive signaling scheme is NP-hard when there
are three or more receivers. In contrast with previous hardness results for ex
interim persuasion, we show that, for games with two receivers, an optimal ex
ante persuasive signaling scheme can be computed in polynomial time thanks to a
novel algorithm based on the ellipsoid method which we propose.