Computational Aspects of Bayesian Persuasion under Approximate Best Response
Authors: Kunhe Yang
Hanrui Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: Bayesian persuasion
computational complexity
robustness
approximate best response.
Primary area: algorithmic_game_theory
TL;DR: We give algorithms and hardness results for Bayesian persuasion under approximate best response.

Abstract: We study Bayesian persuasion under approximate best response, where the receiver may choose any action that is not too much suboptimal, given their posterior belief upon receiving the signal.  We focus on the computational aspects of the problem, aiming to design algorithms that efficiently compute (almost) optimal strategies for the sender.  Despite the absence of the revelation principle --- which has been one of the most powerful tools in Bayesian persuasion --- we design polynomial-time exact algorithms for the problem when either the state space or the action space is small, as well as a quasi-polynomial-time approximation scheme (QPTAS) for the general problem.  On the negative side, we show there is no polynomial-time exact algorithm for the general problem unless $\mathsf{P} = \mathsf{NP}$.  Our results build on several new algorithmic ideas, which might be useful in other principal-agent problems where robustness is desired.

Computational Aspects of Bayesian Persuasion under Approximate Best Response
Kunhe Yang University of California, Berkeley zunheyang@berKeley, edu
Hanrui Zhang Chinese University of Hong Kong hanrui@cse cuhk. edu. hk
Abstract
We study Bayesian persuasion under approximate best response, where the receiver may choose any action that is not too much suboptimal, given their posterior belief upon receiving the signal. We focus on the computational aspects of the problem, aiming to design algorithms that efficiently compute (almost) optimal strategies for the sender. Despite the absence of the revelation principle which has been one of the most powerful tools in Bayesian persuasion we design polynomial-time exact algorithms for the problem when either the state space or the action space is approximation scheme (QPTAS) for the
small, as well as potasi-polynomil-ttmi general problem. On the negative side, we show there is no polynomial -ime exact algorithm for the general problem unless P NP. Our results build on several new algorithmic ideas, which might be useful in other principal-agee problems where robustness is desired.
Introduction
Bayesian persuasion Kamenica and Gentzkow 2011 concerns the problem where principal (the "sender") incentivizes a self-interested agent (the "receiver") to act in certain ways by selectively revealing information about the state of the world. commonly cited simplistic example which nonetheless illustrates the essence of the problem - is that of selling apples.
Example 1.1. Suppose a buyer (the receiver) is debating whether they should buy an apple from a seller (the sender). A priori, the buyer believes the apple (which is, say, random apple from large batch of apples) to be a " "good" one with probability 1/3, and a "bad" one with probability 2/3. Moreover, suppose the buyer derives utility from buying good apple, and -1 -frrmm buying a bad one. Then, aiming to maximize their expected utility, without any further information, the buyer should simply not buy the apple, because buying it would lead expected utility 1 x (- The seller, who has perfect knowledge of the quality of the apple, and wants to "persuade" the buyer to buy the apple, can of course simply reveal the quality of the apple. Assuming the seller can do so in credible way (which is a fundamental assumption in Bayesian persuasion). the buyer will buy the apple whenever is good, which happens with probability 1/3.
In fact, the seller can do even better by employing the following strategy: the seller promises to send "signal" the buyer regarding the quality of the apple, which can be either "probubly good" or "definitely bad". More specifically, if the apple is good, the sender signals that it is "probably good"; the apple is bad, the seller signals randomly, that is "probably good" notwithstanding with probability 0.499, and that it is "definitely bad" with probability 0.501. Now consider the buyer's perspective, assuming the seller does act up their promises. the signal says "definitely bad". then the buyer should certainly not buy the apple. If. however, the signal says "probably good", then the buyer faces more interesting decision. All the buyer knows that the probability of (1) receiving "probably good" and (2) the apple is actually good, happening simultaneously. is 1 1/3, and that the probability of (1) receiving "probably good" and (2) the apple is actually bad, happening
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

simultaneously is 2/3 x 0.499 < 1/3. So, given the signal, the conditional probability that the apple good is larger than 1/2. which means the conditional expected utility of buying the apple is now positive. In other words, the seller has persuaded the rational buyer to buy the apple whenever the signal is "probably good", which happens with probability 1/3 + 2/3 x 0.499 Rs 2/3. This turns out to be (almost) the best that the seller can do.
Since its introduction by Kamenica and Gentzkow 2011 Bayesian persuasion has attracted enormous attention from both economists and computer scientists. Indeed, satisfactory solution to the problem often twofold, involving an economic characterization that confines the sender's strategy space without loss of generality, and an efficient algorithm that finds the optimal strategy within this confined strategy space. For example, in the standard (and somewhat idealized) model of Bayesian persuasion, prominent principle in economics, namely the revelation principle, states that without loss of generality. the sender's optimal strategy is to simply recommend an action (depending on the state of the world, effectively revealing partial information thereof) for the receiver to take, and make sure is in the receiver's best interest to always follow such a recommendation, given their posterior belief of the state of the world. The computational problem of searching for the optimal strategy within this structured space of strategies turns out to be much easier than that of searching over the unconstrained strategy space. Such characterize-and-shoe successful in Bayesian persuasion at least in settings where they apply.
approaches have proved extremely
The real world, unfortunately, is less precise than the idealized model. Even in the simplistic example of selling apples. there appear to numerous subtleties that could potentially derail the supposedly (almost) optimal strategy of the seller. To name few: the sender may not know exactly the receiver's s prior belief, which might be different from the true distribution of the state of the world; the sender may not know exactly the receiver's ss utility function, which might be hard to evaluate even for the receiver themself; the device that generates randomness for the sender may be imperfect, affecting the receiver's 'ss posterior belief formed upon receiving signal. In all these cases, the small inaccuracy can completely change the receiver's behavior: in the example of selling apples, the buyer would never buy the apple if they believe the apple is good a priori with probability 0.32 instead of 1/3, if buying a good apple gives them utility 0.98 instead of 1, or if the device that generates randomness for the seller works in way such that when the apple is bad, the seller actually signals "probably good" with probability 0.501 instead of 0.499. From the perspective of the sender, it would appear as if the receiver is acting in somewhat suboptimal and unexpected way. As we will show later, the powerful revelation principle no longer applies in such cases, and the problem of finding the sender's 's optimal strategy becomes much trickier. On top of that, things become even more complicated when there are more than 2 possible states of the world, and/or more than 2 actions for the receiver to choose between. All this brings to main question: despite the lack of structural characterization, is there a principled and efficient way of finding the optimal strategy for the sender that is robust against such inaccuracy?
1.1 Our Results and Techniques
In this paper, we study Bayesian persuasion in natural model that accounts for the kind of subtleties discussed above: roughly speaking, the model allows the receiver to choose any action that is "not too much suboptimal", given their posterior belief upon receiving the signal. We focus our attention on computational aspects of the problem, aiming to design algorithms that efficiently compute (almost) optimal strategies.
Direct-revalation signaling schemes are suboptimal. Our first finding is negative: there exists extremely simple problem instances (with only 2 possible actions and 3 possible states), where any divect-revelation signaling scheme (i.e., a strategy of the sender where each possible signal is recommendation of a single action, as discussed above) is suboptimal at least by a factor of 2, or an additive gap of 1/2. This implies that the revelation principle ceases to work in our model, and the characterize-ant cittize--nd-ssae -nl-s approach can no longer be employed.
LP formulation, and efficient algorithm with small action spaces. The above result highlights the need for new algorithmic ideas, and we present several of them in this paper. The first one is a linear program (LP) formulation for optimal strategies. The IP formulation has a similar high-level structure to the standard one for Bayesian persuasion: the variables correspond to probabilities that each signal is sent in each possible state of the world, and the constraints enforce the "semanties" of
2

---

the signals, in terms of how the receiver is expected to respond. However, one complication (among others) in our model is that multiple actions might be taken as the response to any fixed signal, so the semantics of signal must be rich enough to encode the subset of actions that are possible in response to that signal (plus any additional information required to describe a signal). this means in general, the number of possible signals is exponential in the number of actions. As such, the LP formulation alone implies an efficient algorithm for our problem only when the number of actions is constant or logarithmic. Nonetheless, the LP formulation serves as building block of our further algorithmic results.
particular,
Efficient algorithm with small state spaces. Next we design an efficient algorithm when the number of states is constant. To see how this is possible, observe that a subset of actions can each be chosen as the response to a signal, only if the posterior utilities corresponding to these actions are all close the best possible. In other words, if there does not exist a posterior belief given which a subset of actions are all almost optimal, then this subset itself is "infeasible" as a set of possible responses. Such a subset of actions can never describe a signal in any strategy. Now the hope is to argue that the number of feasible subsets of actions is not too large. It turns out this can be obtained as a consequence of result in combinatorial geometry, which bounds the number of "cells" in low-dimensional space cut by a number of hyperplanes. We show that all feasible subsets induce a partition of these cells, so the same bound applies to the number of subsets too. In fact, one can show that the number of feasible subsets of actions is n ((m), where n and m are the number of actions and that of states, respectively.
Now we know the number of relevant subsets of actions cannot be too large, but it remains problem to find these subsets. To this end, we make yet another geometric observation: the cells that correspond to feasible subsets of actions form single "connected component", which means can enumerate all feasible subsets by traversing this component. More specifically, we start from any feasible subset, and try all its "neighbors" by swapping in or out single possible action. For each neighbor, we check its feasibility by solving another LP. By repeating this procedure we can reach all feasible subsets, in time polynomial in the number of feasible subsets. Once we have computed all feasible subsets, we simply solve the LP for optimal strategies restricted to these subsets, which is of polynomial size when the number of states m is constant. This gives an efficient algorithm with constant-size state spaces.
Hardness of exact computation of the general problem. Knowing that the problem can be solved with small action spaces or small state spaces, it is then natural seek an efficient algorithm that works unconditionally, without restrictions on any parameters of the problem. We show, unfortunately, that such an algorithm does not exist unless P = NP. We do so by reducing from an "equally hard" variant of the subset sum problem: given a set of 2n integers that sum to 0, decide whether there are n integers out of the 2n that also sum to O. The idea of the reduction is that such a set of r integers corresponds to signal that gives the sender the highest posterior utility possible. To ensure this, the utility functions need to exhibit delicate structures, such that a signal that corresponds to either too many too few integers must be suboptimal. The latter appears to be a quite ambivalent condition in fact, this is only possible with the kind of inaccuracy that we consider. We believe the ideas of our reduction are potentially useful in other principal-agent problems where robustness is required.
Approximation in quasi-polynomial time. In light of the hardness result, we turn our attention to approximation algorithms. We present a quasi-polynomial-ting approximation scheme (QPTAS): for any target additive error 5 > O, give an e-approximate algorithm that runs in time quasi- polynomial in m and n, where the time complexity may depend on E. The idea is to cover the space of all possible posterior utility functions using small cells, and consider a representative point in each cell with a small error. It is known that a covering of size O(log n/=²) exists, which has already proven useful in other game-theoretie computational problems [Althöter 1994 Lipton et al.) 2003 Gan et al. 2023). However, one difficulty in our model is that there are certain types of errors that are unacceptable, no matter how small. For example, fixing a strategy, the sender's utility can be discontinuous in the receiver's 's utility function, and any error near points of discontinuity can lead to a huge gap in the sender's utility. Similarly, because of the robustness component in the model, a small error in the sender's utility may lead to totally different response from the receiver. To avoid such gaps, we allow approximation only in the sender's utility, and refrain from estimating the action that the receiver will respond with. Instead, we consider the approximate worst-case utility of the
3

---

sender, which turns out to be tractable using linear constraints involving approximate utility functions. Combining this with the LP formulation discussed above, we have an LP of quasi-polynome size, which can be solved in quasi-polynomial time.
1.2 Related Works
We defer detailed discussion of related work to Appendix A Our work connects to two lines of
work, the computational aspect of Bayesian persuasion Dughmi and Xu 2016 Dughmi
2017 2014
Bhaskar et al., 2016,] [ubbinstein] 2017 Babichenko and Barman 2016 2017 Xu 2020 Zhou et al.
2022
and various notions of robust Bayesian persuasion dd Clippel and Zhang 2022 Chen and Lin
2023
Camara et al. 2020 Zu et al. 2022 Collina al. 2023 Kosterina 2022 Dworczak and Pavan
2022
Hu and Weng 2021 Castiglioni et al. 2020) Wu et al. 2022 Babichenko et al.
2022]. We also
discuss the comparison between our paper and that Gan al. [2033 on robust Stackelherg games.
2
Preliminaries
Our model builds on the classic Bayesian persuasion model with a single sender and single receiver. At high level, the model formalizes a scenario where the sender, possessing private information about the true state, aims to influence the receiver's decision-making by strategically sending partial information about the true state according to a pre-committed signaling scheme. We start by introducing the basic setting and notations, and then introduce the robust Bayesian persuasion model that considers receiver who acts not exactly, but approximately in accordance with their best interest in the pecision-making process.
2.1 Bayesian persuasion: the classical model
Basic setting and notations. Let Ω be the states of the world with [o]] = m, and (S2) be the set of all probability distributions on Q. For all distributions μ E A(Q), let supp(1s) be the support of μr, i.e., supp(u) A {w Ω p(w) > 0}. We use μo0 E A()) denote the prior distribution over states and assume that Ho is common knowledge between the sender and the receiver.
Signaling scheme. Let E (E < 20) be finite set of signals. A signaling scheme & Ω E a randomized mapping from the states of the world to probability distributions over signals. In the Bayesian persuasion protocol, the sender first commits to a signaling scheme y2, then observes the true state of the world w ~ (40, and sends signal a ~ pfw) to the receiver. We use so(w, o) to denote the probability of sending signal conditioning observing as the true state, and sp(a) = Euren (o(w")((w' )p(w',)) o)) to denote the marginal probability of a signal a E Σ being realized.
Upon receiving the signal the receiver performs Bayes update on using knowledge about the scheme π to obtain a posterior belief fsa E A(2), i.e..
Mu (u(w)p(w.o)
Ho (w)
p0(a)
In addition, algebraic manipulations based on the Bayes' rule suggest that the signaling scheme yp can be viewed the process of creating distribution posterior distributions that satisfy the Bayes plausibility condition [Kamenica and Gentzkow 2011 Gentzkow and Kamenica 2016):
Va S2
Po(w)
Σ p(()) (w(w).
(Bayes plausibility)
WER
Throughout this paper, we will frequently adopt this perspective, especially in the characterization of (robust) utilities.
Utilities and best response sets Although only the receiver can take actions, their action influences both the sender and the receiver's utility, both of which also depend on the state of the world. Let A be the action space of the receiver with [A| n. We use Ω x A + [0. 1] to denote the sender's s utility and r : Ω x A - (0, 1] to denote the receiver's utility, where both utilities are normalized to be between 0 and 1. Additionally, for distributions j E A()), we abuse the notations and use s(1s, a) = Euowa s(w, a) and r(u,, a) Rawe r(w, a) to denote the sender and receiver's 's expected utilities under the state distribution μ.

---

Receiver's strategies A receiver's s strategy, denoted with p Σ - A, is (possibly randomized) mapping from the observed signals actions which specifies the receiver's strategy of choosing responses. Given signaling scheme and receiver strategy p, we use S(P; p) to denote the expected sender utility, which computed as
p) - Σ ((() OEE
ΣΣ no (ww)))(w,o)ssw,ppp p(o)).
WER
The classical model Bayesian persuasion assumes that the receiver's strategy p(or) is always the exact best response of the posterior distribution Mo that maximizes their expected posterior utility (ties are broken in favor of the sender). Formally, the best response action action is defined as
(1a) - argmax r(uor a)
aEA
and the receiver's 's strategy is assumed to satisfy p(o) = a ((o)). this paper, we will relax this exact best-response assumption allow for approximate best responses.
2.2 Robust Bayesian persuasion with approximate best responses
In this paper, we allow for some degree of suboptimality in the receiver's response. Specifically, we assume that the expected utility under receiver's response p(or) is not too suboptimal compared the best action a (Ua). Formally, we use (-a(-) to denote the set 8-optimal responses on the input belief:
(R) {a E A |r(p,a) > r(u, a" (())) -},
(1)
then receiver's strategy p: Σ + AA 8-best response (or ò-BR) if satisfies p(ar) E BR& for all E. We use (Gp) to denote the set of all 6-BR strategies under the signaling scheme yp
Robust sender utility this paper, we adopt the max- min adversarial robustness perspective and aim to offer robustness guarantees against worst-case 5-BR strategies. We use the robust utility Ss of signaling scheme to characterize the expected utility under the worst-case 6-BR strategy:
Sa((p) = min
S((p (
The sender aims to maximize the robust utility through optimizing the signaling scheme. Equivalently, the sender faces bi-level optimization problem of the following max-min form:
$3 max Ss(1²)
max sp*
min (BE
pp))
(sender's objective)
Solving the optimization problem in (sender's objective) includes (1) finding appropriate signal space that is sufficient to achieve the optimal utility and (2) optimizing for the optimal signaling scheme given the signal space.
Remark 2.1 (worst-case 5-BR strategy). It is not hard to see that the worst-case 8- B-BR strategy Ps that achieves (sender's objectiveD will choose the worst action that minimizes the sender's utility for each posterior distribution separately, i.e.,
pa(a) E argmin s( a). aEBRs(po)
Therefore, the robust utility under any signaling scheme ip can be equivalently written as
3s(4) = Σ p(a) s(Ma.)o(o)) = Σ p(a)
min s(Po, a). aEBR,(p.)
oEE
OEE
Remark 2.2 (Strict inequality in definition of BR; set). Injeg. (1) we use strict inequality so that the
sender's strategy space closed and compact, and the sender's objective is well-defieed. This is non-essential choice: one could instead define 8- BR responses using weak inequality and investigate the sender's 's supremum robust utility, which would not change the nature of the problem.
'When there are multiple actions a" (pz) that maximizes the receiver's utility, we detine a" (p.) to be the maximizer that achieves the highest sender's utility.
5

---

LP formulation and algorithm with small action spaces
As show in Appendix B the powerful revelation principle fails in the robustness model that study. In fact, we establish the following claim.
Proposition 3.1 (Proposition [.T in Appendix B). There exists sequence of Bayesian persuasion instances with a robustness level (()), such that the following holds in the limit: any direct- revelation scheme is suboptimal, least by a factor of additive gap of 2. That is, for any direct-revelation scheme 4,
1 Lt 25
Sa(p)
and Sa(e) S
2
The above proposition highlights the need for new algorithmic ideas to efficiently compute (approxi- mately) optimal robust schemes.
In this section, we present linear program (LP) that computes the optimal robust utility S and the optimal robust signaling scheme yp" Although the high-level idea is similar to the LP formulation for computing the optimal non-robust scheme in standard Bayesian persuasion [Dughmi and Xu 2016 Dughmi 2017). our robust LP Formulation follows significantly different semantics.
We characterize the maximum number of signals needed to achieve the optimal robust utility in Lemma 3.2 This lemma can viewed as generalized (and unfortunately, much less powerful due to lack of best responses) version of the revelation- prrincipeee style argument in [Kamenica and Gentzkow 2011 Proposition 1] that accounts for worst-case approximate best responses. See Appendixx Citor the proof of the lemma.
Lemma 3.2. There exists an optimal robust signaling scheme that is supported on at most - signals, in which each signal and (Ro(Ho).
corresponds to a unique pair of (A, ā) such that à = a (po)
According to Lemma 3.2 it suffices to consider following signal space:
Σ {(A,a) A A, à E A), where each signal a = (A, a) satisfies both at (po) = à and (Ro(Ho) = A. Recall from Remark 2. that the robust utility can be written
$
max
p((A,a))
min aEBRA(A(A.a)
s(((A,a)))
(A,E)
Translating this max min optimization to a constrained maximization problem, and enforcing the abovementioned semantics for each signal, we arrive at the following (non-lineary program in in(i.. Although the program in Fig. is not yet a linear program, both the first and second constraints can
maximize $2.00
Σ x(A,ū) @)
(A
subject to a" (m())) = à BR =
((M(A))))) s(M(A,)), x(A,a). =(A,,))
Vo E Σ, Va E A v(A,ū) E (A, E
Figure 1: program for the optimal robust signaling scheme supported on Σ = {(A, a)).
be equivalently written as linear constraints on the conditional probabilities (p(w, (A, a)) that define the signaling scheme ip, using the following observation based on the Bayes' rule:
Yo E Σ, (p())) s s(Ho, a)
(o(w))(w,a)) s(w, a).
(2)
wen
Therefore, it remains to characterize the 8-BR response sets, and would be ideal if they could also be cquivalently expressed as linear constraints. Unfortunately, the definition of 6-BR sets involves strict- inequality constraints due to the issues discussed in Remark 2.2 In particular, for each (A, â) e Σ, the third constraint equivalent
(1) Va E A, s(Ha, a) s(Ho, à) - (2) Va A s(Ho, S s(Ma, ā) 8,

---

where (I) involves a strict inequality and could lead to open polytopes. Due to such subtleties, we first consider the LP Fig. 2 which relaxation of the program in Fig. by dropping the strict-inequality constraint (1). The last two constraints in Fig. guarantee that variables s(w, A, @)
give rise a valid signal distribution for every state w E
maximize 6..
Σ x(A,ū) a)
(A.ö)en
subject to
x(A,a),
(
wE
No (o(w) A, (r(w,ū) r(w,))) 2 0,
V(A,)) E
WER
( A. (r(w, (w.a) - 5) 5 0,
V(A,a) V. A
WEn
Σ A, =1
Ve Ω
(A,A)E
(ww, A, 2 0.
Y(A, EΣ
Figure 2: Relaxed LP for the optimal robust signaling scheme
Since Fig. 2 is a relaxation the original program, its optimal objective provides an upper bound for Sz. However, as we will show later, not only does the optimal objective value exactly equal S but the optimal variables sp* also exactly characterize the optimal robust signaling scheme that achieves this Sj. This gives us an algorithm that efficiently computes the optimal robust signaling scheme when the number of action spaces is constant or polynomial. We formalize this in Proposition 3.3 and provide a proof in Appendix C
Proposition 3.3 (Efficient algorithm for small action space). The optimal robust signaling scheme can be computed by the linear program in Fig. 2 with size (2 mn).
4 Efficient algorithm with small state spaces
In this section, we focus on the robust persuasion instances where the action space large, but the state space small. For such instances, key observation is that among the (n 1)2" tuples in y, only a small fraction of them can be realized by posterior distributions and therefore serve as feasible signal candidates. In In/eccioon 4.1] characterize the structural properties of feasible tuples (A, a) E D' and draw connection to the polytopes in the simplex supported on the state space. In Section 4.2, we leverage these structural insights and design an efficient algorithm that accelerates The computation of the optimal robust signaling scheme.
4.1 Structural properties
We formally define the feasibility of a candidate tuple (A, E Σ according to the existence of posterior distribution that has its 5-BR set and à as best response action.
Definition 4.1 (Feasible subset-action tuple). A tuple (A, ā) E E is feasible if there exists some posterior distribution E A(2) such that a" (p.) = à and BR (p) = A. We use Σt to denote the set of all feasible tuples E.
For each feasible tuple (A, a) E Σt, let ((A,a) be the set of posterior distributions that satisfy both constraints in Definition 4.1l
( {n E A( (=)))= = ā, BRx(H) = A}}
not hard to see that the subsets A (A,a) partitions the simplex, because each distribution in simplex is associated with unique best response action and 8-BR set. That is,
A(2)=
U ((A,))-
(A,ā)ES!

---

In addition, each ((A,a) is a polytope in the simplex that is defined by the following constraints that are linear the distribution jc:
r(u,a) - r(u,
Va E A;
J1 E (A.a)
r(u,a) > r(u,ā)- - 5, Va E A; r(u,a) r(u,a) 5, Va A
(3)
Our key observation is that the linear constraints that characterize different (A.a) all take one of the following two forms based ordered pair of actions (a, E A x A:
1. Either r(u, a) S (r(,,a)) 6, its complement r(u, a) r(u, 8:
2. r(p, a) S r(),a)).
which give rise to more than 2n hyperplanes. Although the number of hyperplanes scales with the potentially large number of actions, when the state space is small, these hyperplanes, and the polytopes they define, all live within low-dimensional space. According to fundamental theorem in computational geometry (see, e.g., Theorem 28.1.1 in [Halperin and Sharir 2017)) these hyperplanes cut the m--dimensional into most O (2n2)m-1) cells. This observation helps to bound the number of feasible tuples the following lemma. The proof of Lemma 4.2 deferred to Appendix D.2
Lemma 4.2. The size of the feasible tuples Σt satisfy | < min 1022-1,,00mg
Next, we establish some structural properties on the set of feasible tuples o that could facilitate the efficient search over candidate signals. the remainder of this section, we first define a bounded- degree synmetric difference graph on all tuples in 2, then show that all feasible tuples in Σ form connected component in the symmetric difference graph.
Definition 4.3 (Symmetric difference graph). In the symmetric difference graph G F), each vertex tuple (A, â) E E. Each edge {AA,, ā1), (A2, ā2)} E represents that the symmetric difference between tuples (A1, ā1) and (Ag, ā2) is of size I, which is satisfied for the following two cases:
A = Ag, and ā1 # ā2.
â1 à2 E A Ag and (A1 \ A2) (A2 \ A1)
The symmetric difference graph G characterizes the structural relationship between tuples in Σ, in which only any two tuples are connected if and only if their symmetric difference is small enough. Together with the following lemma, G provides a useful framework for us to search within the exponentially large vertex set.
Lemma 4.4 (Connectivity). The subgraph of induced by Et is connected.
We defer the proof of Lemma 4.4 to Appendix D. At a high level, the proof translates the connectivity of the polytopes A (A,a) in the simplex space the connectivity of feasible tuples in the symmetric distance graph G by analyzing the geometric properties of the common face of shared by every pair of adjacent polytopes.
4.2 Algorithm
In this section, we present Algorithm I that leverages the connectivity of the feasible tuples to efficiently search for Σt This algorithm essentially performs depth-first-search (DFS) on the connectivity graph by recursively searching all the neighbors with symmetric difference size to the given tuple that it's currently searching. The initial tuple to start the EXPLORE procedure can be set to any tuple that is already known to feasible, e.g., the ò-BR set and the optimal response associated with the prior distribution (Ap-
Note that each tuple (A, E Σ is feasible if and only if there exists μ E Σ that satisfies all three constraints in Equuatinn (3) simultaneously. which can be written as checking the feasibility of corresponding LP (with strict-inequality constraints) on the distributions μ.. To replace strict-inequality constraints with non-strict constraints, we propose to check the LP via a margin- maximization trick in Fig. @jof[Appendin D.3) This I.P defined on closed polytope, and asserts fcasibility if and only if the optimal margin is strictly positive, i.c., g* > 0.

---

Algorithm 1: EXPLORE
Input: tuple (A, a) E
Check the feasibility of (A, a) by solving the LP in Fig. 4 g* +- optimal objective value;
2 ef then
Mark (A, â) checked and feasible;
for actions a E {a} do
If (A {a}, a) is unchecked, call EXPLORE((A (a)))) (a).a);;
(A, a) is unchecked, call EXPLORE((A..)): end
for actions E A
A do
( {a},a) unchecked, call EXPLORE((A U (a).4));
10
end
11 end
else
13
Mark (A, @) checked and infeasible
end
Theorem 4.5. Running Algorithm 2 with initial tuple (BRs(uo): a² (po)) finds all feasible tuples E C by solving most n ((m) LPs, each of size O n).
Proof. The correctness of this algorithm is ensured by the connectivity property in Lemma 4.4
remains to upper bound the number of feasibility checks performed. Since Algorithm 1 ooolyy checks new vertex when it has not been checked before, the total number of feasibility checks is upper bounded by the size of the closed neighborhood of y Since each tuple (A, ā) E Σ has at most (n) neighbors, the degree of any vertex the symmetric difference graph G is upper bounded by O(n).
Therefore, the size of the closed neighborhood is at most O(n) Σt S O(m),
The final step for optimizing signaling schemes is to solve the LP in Fig. with the original signal space Σ replaced by feasible tuples E, We summarize the entire procedure and its complexity in Algorithm and Corollary 4.6
Corollary 4.6, When the number of states mn small, the optimal signaling scheme can be efficiently
computed by Algorithm 2 which involves solving n O(m) LPs of size O + n) and then solve
single LP of size m n. ((m)
Algorithm 2: ALGORITHM FOR SMALL STATE SPACES
(Ao, ao) + (BR((po) at (po));
Search for Σ by running SEARCH(Ad, āo): Solve the LP in Fig. 2 with Σ replaced by Er.
Approximation algorithm for the general problem
In this section, first show that the general problem without any restrictions is computationally hard, then present quasi-poly quasi-polynomial time approximation scheme (QPTAS) for the problem. The following claim (proof defered to Appendix E. establishes the computational hardness of finding the exact optimal robust signaling scheme. This result implies that a polynomial-tine -ime exact algorithm for the robust persuasion problem does not exist unless NP.
Theorem 5.1. The problem of computing the exact optimal robust utility is NP-hard.
In the following, we present QPTAS that computes an E-approximate optimal 8-robust signaling scheme @ for any given > such that
35(G)
S

---

Our 6-optimal signaling scheme is supported on a significantly different signal space compared to the optimal schemes for cases of small state space and small action space. The high-level idea is, instead of enumerating each (BR a² (44) set, we partition the simplex A into small cells, each centered around k-uniform distribution y (to be defined later), and incorporate additional semantics to ensure that the utility profiles <Tzz. -) are representative enough for all distributions within this cell. It is useful to have the utilities at ş being representative because we can then determine the 8-BR sets according to the relative magnitude of utilities and translate the requirements into linear constraints.
Formally, for an integer k. distribution μ E A(22) is k-uniform if Vou E Q pسw) kw for some integer kw I k. Let 9* S (S2) denote the set of all k-uniform distributions on the state space. We log (2n)
x
have |Ga| (mn*) Moreover, by Althhfeer 1994], for lig
have:
Vy E A(2), 3e E Gk., s.t. Accordingly, we define the s-cell around μ 9k to be
Va E A, 1s(1, a) s(T,, a)l Se.
CH {u E ((2)) Va E A, (s(H,,) s(ā,, a)l seJ.
Note that given and μ. E C is equivalent to set of 2n linear constraints on We consider the following signal space:
log(2n) 2((')2
Σ (TT, ā, a) T 9k.r a. A), where kig
(4)
Define LP variables (pw,, Jr, ā, à) for each w E Ω and each signal (ī, à) E Σ to represent the conditional probabilities of sending that signal. Each signal (TT, a, à) is specified by the k- uniform distribution jı that centers the cell, the best response action ū, and the action à in ò-BR set that minimizes the sender's strategy. The LP defined in Fig. 3
maximize 6,
Σ Ho(w)
Σ (T
a(u,
WESt
subject to
Σ Holw) F. (s(w, - s(H, a) +E) (Va E A, V(z,ā, E Σ
w
Σ Ho(w)<(w, (w, (. ( -po))ss(Too00 a) - -E) = 0 (Va A, V(ū. a,) Σ
WE
Σ Ho(w) (r(w, - r(w, a)) 20,
A v(u,a,)) E E
WER
Σ
Ho(w) F. (r(w, - r(w, a) -8) 20
WEn
(Va 8(7,, a) < s à) 25')
(V(T,, 0, à) E Σ) (Vw E !)
Σ
p(,,A,
(,,
( Dz, a, à) > 0.
(Vw E S V(T, ā, à) E Σ
Figure 3: QPTAS for computing an E-approximate robust signaling scheme, where e' f
Intuitively, the first two constraints in Fig. 3 are designed to ensure (izaa,a CH The third and fourth constraints describe the semantics of the receiver's response strategy. Finally, the last two constraints guarantee that &p represents valid signal distribution on each state. We summarize the and guarantee of the QPTAS in Theorem 5.2 and formally prove in appendix F
Theorem 5.2. For any ε > 0 and ā > 0, the optimal solution to the LP in Fig. 3 an e-approximate 8- 5-robust signaling scheme that is supported on O n 12.5 (og((2)/(s2)) signals.
10

---

Acknowledgments
This material is based upon work supported by the National Science Foundation under Grant No. DMS-1928930 1928930 and by the Alfred P. Sloan Foundation under grant G-2021-16778, while Hanrui Zhang was in residence at the Simons Laufer Mathematical Sciences Institute (formerly MSRI) in Berkeley, California, during the Fall 2023 semester.
References
Ricardo Alonso and Odilon Câmara. Persuading voters. American Economic Review, 106(11); 3590-3605, 2016.
Ingo Althöfer. On sparse approximations to randomized strategies and convex combinations. Linear Algebra and its Applications, 199:339-355, 1994.
Itai Arieli and Yakov Babichenko. Private Bayesian persuasion. Journal of Economic Theory, 182: 185-217, 2019.
Robert J Aumann, Michael Maschler, and Richard E Stearns. Repeated games with incomplete information. MIT press, 1995.
Yakov Babichenko and Siddharth Barman. Computational aspects of private bayesian persuasion. arXiv preprint IrXiv:1603.0m 00444, 2016.
Yakov Babichenko and Siddharth Barman. Algorithmic aspects of private Bayesian persuasion. In Proceedings of the 8th Innovations Theoretical Computer Science Conference (ITCS), 2017.
Yakov Babichenko, Inbal Tolgam-Cohen, Haifeng Xu, and Konstantin Zabarnyi. Regret-minimizing bayesian persuasion. Games and Economic Behavior, 136:226-248, 2022.
Arjada Bardhi and Yingni Guo. Modes of persuasion toward unanimous consent. Theoretical Economics, 13():1111-1149) 2018.
Dirk Bergemann and Stephen Morri. Bayes correlated equilibrium and the comparison of information structures in games. Theoretical Economics, 11(2):87-522, 2016.
Dirk Bergemann and Stephen Morris, Information design; A unified perspective. Journal of Economic Literature, 57(1):44-95, 2019.
Dirk Bergemann and Martin Pesendorfer. Information structures in optimal auctions. Journal of economic theory, 137(1))580-609 2007.
Dirk Bergemann, Benjamin Brooks, and Stephen Morris. The limits of price discrimination. American Economic Review, 105(3):921-99) 2015.
Umang Bhaskar, Yu Cheng, Young Kun Ko, and Chaitanya Swamy. Hardness results for signaling in bayesian zero-sum and network routing games. In Proceedings of the 17th ACM Conference on Economics and Computation (EC), pages 479-496. 2016.
Isabelle Brocas and Juan D Carrillo. Influence through ignorance. The RAND Journal of Economics, 38(4):931-947) 2007.
Modibo K Camara, Jason D Hartline, and Aleck Johnsen. Mechanisms for no-regret agent: Beyond the common prior. Proceedings of the 61 Annual Symposium on Foundations of Computer Science (FOCS), pages 259-270. IEEE, 2020.
Ozan Candogan. Information design in operations. In Pushing the Boundaries: Frontiers in Impactful OR/OM Research, pages 176-201. INFORMS, 2020.
Matteo Castiglioni, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Online bayesian persuasion. Advances in Neural Information Processing Systems (NeurIPS), 33:16188-1611 16198, 2020.
Yiling Chen and Tao Lin. Persuading behavioral agent: Approximately best responding and learning. arXiv preprint ar X321::230..03719, 2023.

---

Natalie Collina. Aaron Roth, and Han Shao. Efficient prior-free mechanisms for no-regret agents. arXiv preprint arX1v:2311.0774,, 2023.
Geoffroy de Clippel and Xu Zhang. Non-bayesian persuasion. Journal of Political Economy, 130 (10):2594-2642, 2022.
Shaddin Dughmi. On the hardness of signaling. In Proceedings of the 55th Annual Symposium on Foundations of Computer Science (FOCS), pages 354-363. IEEE, 2014.
Shaddin Dughmi. Algorithmic information structure design: survey. ACM SIGecom Exchanges, 15 (2):2-24, 2017.
Shaddin Dughmi and Haifeng Xu. Algorithmic Bayesian persuasion. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), pages 412-425, 2016.
Piotr Dworezak and Alessandro Pavan. Preparing for the worst but hoping for the best: Robust (bayesian) persuasion. Econometrica, 9015)22117- 2022.
Yiding Feng, Ju Ho, and Wei Tang. Rationality robbust information design: Bayesian persuasion under quantal response. In Proceedings of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 501-546. SIAM, 2024.
Jiarui Gan, Minbiao Han, Jibang Wu, and Haifeng Xu. Robust stackelberg equilibria. In Proceedings of the 24th ACM Conference on Economics and Computation (EC), page 735, 2023.
Matthew Gentzkow and Emir Kamenica. A rothschild-stigee stiglitz approach to bayesian persuasion. American Economic Review, 106(5):597-605) 2016.
Dan Halperin and Micha Sharir. Arrangements. In Handbook of discrete and computational geometry, pages 723-762. Chapman and Hall/CRC, 2017.
Ju Hu and Xi Weng. Robust persuasion of privately informed receiver. Economic Theory, 72: 009-953,200 2021.
Emir Kamenica. Bayesian persuasion and information design. Annual Review of Economics, 11: 249-272, 2019.
Emir Kamenica and Matthw Gentzkow. Bayesian persuasion. American Economic Review, 101(6):
2590-2615, 2011.
Jon Kleinberg and Eva Tardos. Algorithm design. Pearson Education India, 2006.
Svetlana Kosterina. Persuasion with unknown beliefs. Theoretical Economics, 17(3):0755-1107, 2022.
Ilan Kremer, Yishay Mansour, and Motty Perry. Implementing the "wisdom of the crowd".. Journal of Political Economy, 122(5):988-1012, 2014.
Richard Lipton, Evangelos Markakis, and Aranyak Mehta. Playing large games using simple strategies. In Proceedings of the 4th ACM Conference on Electronic Commerce, pages 36 36-41, 2003.
Yishay Mansour, Aleksandrs Slivkins, and Vasilis Syrgkanis. Bayesian incentive-compatille bandit exploration. Operations Research, 13(4):1132-111 2020.
Yishay Mansour, Aleksandrs Slivkins, Vasilis Syrgkanis, and Zhiwei Steven Wu. Bayesian explo- ration: Incentivizing exploration in bayesian games. Operations Research, 70(2):1105-1122 2022.
Aviad Rubinstein. Honest signaling in zero-sum games is hard, and lying is even harder. Schloss Dagstuhl-Lebmizz-ZZeruun fuer Informatik, 2017.
Keith Schnakenberg. Expert advice to voting body. Journal of Economic Theory, 160: 102-133
2015.
12

---

Yun Wang. Bayesian persuasion with multiple receivers. Available at SSRN 2625399, 2013.
Jibang Wu, Zixuan Zhang, Zhe Feng, Zhaoran Wang, Zhuoran Yang, Michael Jordan, and Haifeng Xu. Sequential information design: Markov persuasion process and its efficient reinforcement learning. In Proceedings of the 23rd ACM Conference on Economics and Computation (EC), pages 471 1722,4722220 2022.
Haifeng Xu. On the tractability of public persuasion with no externalities. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algoritimss (SODA), pages 2708-2727. SIAM, 2020.
Chenghan Zhou, Thanh H Nguyen, and Haifeng Xu. Algorithmic information design in multi-player games: Possibilities and limits in singleton congestion. In Proceedings of the 23rd ACM Conference on Economics and Computation (EC), pages 869-869, 2022.
You Zu, Krishnamurthy Iyer, and Haifeng Xu. Learning to persuade on the fly: Robustness against ignorance. In Proceedings of the 22nd ACM Conference on Economics and Computation (EC), pages 927-928, 2021.
A Related Works
Bayesian persuasion. Our paper generalizes the canonical model of Bayesian persuasion for information design that introduced by the seminal work Af et al. [995]] Kamenica and Gentzkow [211]] [Brccas and Carrillo [2007). This framework has been extended to multi-receiver
settings |Bergemann and Morris 2016 2019] and supports many important applications, such as voting [Schnakenberg. 2015] Alonso and Câmara 2016 Bardhi and Guo, 2018 Wang 2013 Arieli
and Babichenko 2019). bilateral trades |Bergemann al.) 2015 Bergemann and Pesendorfer 2007]
incentivizing exploration [Mansour et al. [2200] 2022 Kremer et al. 2014]. to name few. We refer
the readers to survey papers [Candogan] 2020 Kamenica 2019 for a comprehensive overview.
Computational aspects of Bayesian persuasion and information design. Our work examines the computational aspects of Bayesian persuasion, which has gained significant attention since the seminal work of Dughmi and Xu (2066). (ughmmi (2017) that study the algorithmic complexity of the sender's optimization tasks several natural input models. In the multi-receiver settings, computational challenges are more pronounced, as demonstrated by Dughmil (2014), Bhaskar et al. (2016) who showed the hardness of computing the optimal signaling scheme Bayesian zero-sum games. In addition, Rubinstein (0177) established the hardness of finding even an approximate solution, revealing that obtaining an c-approximate signaling scheme in two-player zero-sum games requires quasi-polynoon
time. On the positive side, (Babichekoo and Barman (2017) studied private persuasion with binary action space and presented an efficient approximation of the optimal signaling scheme. Xu [2020] addressed the tractability of optimizing signaling schemes without externalities between the receiver's 's payoffs. Recently, Zhou et al. [2022] studied algorithmic information design of public and private signaling in atomic singleton congestion games, achieving efficient exact optimization of optimal signaling schemes when the number of resources is constant.
Robust Bayesian persuasion. Recent research on robust Bayesian persuasion has explored various notions address the uncertainty and robustness in sender-receiver interactions.. The existing literature can be roughly divided into two main approaches: max-min models and faulty receiver models.
Maximin models consider scenarios in which the sender aims to maximize their worst-case utility under various types of uncertainty. For instance, Dworczak and Pavan [2022] study two-layer model where the first layer accounts for arbitrary exogenous information receivers may have, including pes- simistic scenarios where receivers fully learn the state from exogenous information. The optimization at the second layer assumes common prior but is constrained to policies that secure the sender's 's maximin payoff at the first layer. Kosterina [022) considers a setting where the sender does know the receiver's 's prior belief and assumes that the receiver's 's prior can be any distribution that assigns at least a fixed state-dependent probability to each state. Hu and Weng [022 consider a model where starting from common prior, the receiver gets private signal resulting in an arbitrary random belief supported on given subset of the simplex. They show (1) when the subset is the entire simplex, full revelation is optimal, and (2) when the subset is a small neighborhood of the common prior, the cost
13

---

of robustness vanishes as the size of the neighborhood vanishes. Babichenko et al. [2022] study model with binary actions and the receiver's utility being uncertain. They show that full uncertainty is extremely harmful, while if the sender knows the ordinal preferences of the receiver over states, then there's $ constant additive gap between the maximin strategy and the omniscient one. Chen and Lin 2023 consider a model similar to ours with e-best responding receivers. They present continuity result that bounds the cost of robustness by OE)).
On the other hand, faulty receiver models usually assume the sender has full knowledge of the receiver's behavioral model, often incorporating bounded rationality or non-standard Bayesian updates. Feng et al. [2024] sstdyy the bounded rationality model through quantal response, which is a smoothed version of exact best response that models mistakes or "trembling hands". They focus on binary actions and identify conditions under which the optimal policy against a best-responding receiver remains almost optimal under quantal response. They also construct approximately optimal policies oblivious to the level of bounded rationality. de Clippel and Zhang [2022) consider "non- Bayesian" updates by the receiver according to an arbitrary but fixed rule. They provide structural results and rankings of updating rules in terms of both the sender's ' and receiver's utilities. These works differ from ours in that they assume the sender has full knowledge about the receiver's fixed response rule, whereas in our setting, the sender must anticipate worst-case responses from set of approximate best responses.
Comparison with [Gan et al. 2023). Another closely related work that Gan al. 2023
which studies the computational complexity of robust Stackelberg equilibria under approximate best responses. While Stackelberg games provide a more general model for prineipal-agent interactions, the computational complexity results in [Gan et al. 2023] are not directly applicable to Bayesian persuasion due differences in problem representation. Specifically, Bayesian persuasion instances are typically represented in a more compact form than the "flat" representation used for Stackelberg games, where principal's strategy space includes all feasible signaling schemes. This distinction limits the direct application of algorithms from Gan et al. 2023 to Bayesian persuasion by framing as a Stackelberg game instance.
There are also important algorithmic differences between Stackelberg games and Bayesian persuasion. In Stackelberg games, the search space is constrained the simplex of probability distributions over the principal's is action set. In contrast, in Bayesian persuasion, the search space for signaling schemes not pre-defined it requires constructing a signal space, making the design of signal spaces an important part of the problem. Our paper introduces algorithmic techniques specifically designed for Bayesian persuasion that achieves a complexity of poly onl (mm) when the state space size m is small. In comparison, approaches in Gan al. (2033 result in complexity exponential in n.
B Failure of revelation principle
In classical Bayesian persuasion problem where receivers always best respond, an argument via the revelation principle (see, e.g., [Kamenica and Gentzkow 2011 Proposition 1J) shows that it suffices to consider direct revelation schemes that give direct recommendations of which actions to play. This argument implies that without loss of generality, the number of signals needed is at most the number of actions. However, in this section, we will show that when robustness enters the picture, direct revelation schemes fail even to achieve any nontrivial approximation ratios of the optimal robust utility. Indeed, similar phenomenons were observed by Gan et al. (2023) in the context of Stackelberg games. As they argue, the absence of the revelation principle in their setting makes the respective problems more challenging, which is also what happens in our model.
Below we present a simple example with 3 states and actions where direct revelation schemes fail to match the optimal utility with any nontrivial approximation factor.
Proposition B.1 (Suboptimalityy of direct-revelation schemes). There exists a sequence of Bayesian persuasion instances with robustness level 8 = ((1), such that the following holds in the limit: any direct-revelation scheme &p is suboptimal, at least by a factor of 2 or an additive gap of z That is, for any direct-revelation scheme s,,
1 1 S,(pp) S 53 and 36(()) s S$
14

---

The claim in Proposition B.1 can be established using the family of robust persuasion instances constructed Example B.2] The main idea to create relatively large robustness level so that disadvantageous actions enter the receiver's approximate best response set as long the posterior is mixed distribution. Therefore, achieve the optimal robust utility, the sender has to adopt signaling scheme that deterministically discloses the true state, which requires signaling space larger than the action space.
Example B.2. Consider the following family of robust Bayesian persuasion instances parametrized by E. Every instance in this family has state space Q = {Wi, wo, W1 and action space A = {ao, a1}. The prior distribution po puts very small probability mass on state w., and divides the rest of the probability mass eventy between and w2. Formally, for an infinitesimal & > 0, we have
No (o(W1)= =,, po(wo) = [o(w)) 1--
2
The utility functions satisfy s, where both the receiver obtains utility if the index of the action matches that of the state (i.e., in the case of (w1,01) and (Wo, on)) and otherwise (see Table The approximate best response level is 1.
actions (A)
states (52)
ag
a
W
wlp
W1
Table The utility function for both the sender and the receiver. the state is wi, then both players have 0 utility. Otherwise, both players get utility 1 if and only if the receiver's action matches the true state.
the optimal robust utility S is at least - which can be achieved by a full-revelation signaling scheme yp supported on 3 signals. More specifically, şp is deterministic mapping from f2 ternary signal space Σ 1 oo J1 such that yp(ws; a, for E {1. O, 1). Since this signaling scheme is deterministic, we have oo (a;) (w((w)), and each posterior distribution Mo, is the degenerate distribution wi. They lead to the following approximate best response sets:
Proof of Proposition B.I In example B.2
(RA(HaL) = (ao, an (Rr()o)) {ool: BRa(H,,) {a
Therefore, the sender's robust utility is given by
$o(x*) = Σ (t) min s(po,a) a)
(EBRE(MM)
oEx
=mo(wL) s(Ho,, a0) + (wlw)) s(Mogs ao) + Ho(wi) s(Mo, a1) 1-8
1-8
=0
2
On the other hand, we claim that any signaling scheme &p :::0 Ω + Σ with ΣΣ] = has to suffer a suboptimal utility of Sa((p) < 1- To see this, note that if a posterior distribution fl of a signal E Σ supported on more than one state, then the receiver's utility the optimal action is at most max (wn), [a((w) < 1, which is smaller than the robustness level ý = 1. Therefore, any posterior Ho that is mixed distribution must have BRa(Ho) = {oo, a1), which implies
min s(pa a) min {s(Ha, an), s(Ha a1)) min (wo), Mo (w1)). (p.))
Let us denote the two signals in Σ as do and Ø1. At least one of the posterior distributions Moo, and Ho, has to be supported on 2 2 states because [[2] = 3. We have two following cases:
Case 1. Both signals have mixed posteriors. In this case, we have
Sa(p) (600=E(p
p(0)-
min s(oo, a) aEBR, (1x))
15

---

=p(oo) min (Po (wo), Hoo (wi)} + (((1)) minn {No, (wo), po, (wi)}
sp(oo) Moo (wo) p((r) Moi (wo)
=mo(wp) sp(wo, σo) + (o(w)) p(wb: mo(wo) = - 2
where the last few steps follow from the Bayes' rule.
Case Only one signal has mixed posterior. WLOG, assume Mag a mixed distribution whereas Moi is a pure (degenerate) distribution. It is also WLOG to assume that Mor is degenerate distribution on w1. because wy and wi are symmetric and w1 has 0 utility under both actions. Therefore, we have that σi is only sent on state w1, and p((1)) (u(w1). As for the robust utillit, we have
35(l) Σ p(o)) min aEBRa(ua)
s(Ho a)
aes
=p(an) min (Moo(w)) Map (wi)} + p((r)) ,(wn,
=p(0o) 0+ ((11)-
=po(w1) 1-E
where the second-to-last step follows from Ma (wi) 0 because is only sent on state
Combining the two cases above, arrive at the conclusion that any scheme with two signals has robust utility most 3 which is half of the optimal robust utility Sj. In addition, note that 3 - (p())) = ع and the above analysis holds for any > 0. Therefore, sending - 0 proves the additive gap.
C Omitted proofs in Section 3
Proof of Lemma 3.2 Let E' {(A,a) A A, e A). Given any signaling scheme y f2 -+ E, we use Σ(A.a) to denote the subset of signals o E E that lead to the same best response a* = à and the same 8-BR set (Ro = A, i.c.
E(A = (o EE oEE: a (16) = à, (Ro = A}.
Consider alternative signaling scheme s' Ωt + E' that merges signals in each subset {(,,a):
v(A,a) e E', (' (A.ā))
Σ p(w.o).
oEE(A.a)
The subsets E((A,)) naturally form a partition of the original signal space Σ.
We first claim that a" (({A.a)) à. BRs(P(A,;)) = A. The first claim follows directly from the revelation principle - since à is the best response to each a E E(A,a), it must also the best response to the merged signal. For the second claim, from the Bayes' rule, the posterior of receiving each signal (A, à) under the newly constructed scheme yp' satisfies
Vo E Ω ((A,a)(w) = ExErI ((o))o(w)
(5)
EnE (00))
therefore, for each a A, we have
r(M(A,))) a) = EoeS ((()r((o:O) EoEsiAn ( -)
r(((A,)) -
EoeD ((0)
Eoe ((0)
Similarly, for each a E A A, we can conclude that
r(M(A,a), a) S r(u(A,)), a)
16

---

The two cases together established the second claim that (Ra()( = A. Finally, for the sender's utility, we have
min o' ('((Aā) min ((((A,)): aEA
E
((o))((a, a)
(Bayes' rule in eq. (5)
oED(a.a)
min ( acA
(Jensen's 's inequality)
Since the above inequalities hold for any (A,a) E E, the robust utility satisfies
So(p') = Σ
& ((()ā))
min s(((A.)) aEA
(A,
Σ
Σ
f( (0)) min s(Ma a) = 3o((p,
aeA
(A,ā) oEL(A.
where the last step follows since {F(A.a) (A,ū) E } forms a partition of Σ.
We have shown that restricting the signal space to {(A,a) A S A. E A} by merging signals never decreases the robust utility. Therefore, there must exist optimal signaling scheme
supported on at most |Σ'] n 2n signals.
Proof of Proposition 3.3 We use OPT to denote the optimal objective value of Fig. 2 and use
40" x² to denote the optimal variables that achieve OPT, In addition, let yp" : Q + Σ be a signaling scheme induced by the optimal LP variables 40 (w, A, a) Since Fig. 2 relaxation of the original problem for computing $7. we have OPT 2 Sz. Therefore, establish the optimality of y=t
suffices to show that OPT S Ss(p"), because it implies
OPT < Ss((p)) max Sa(() S s OPT,
which all the inequalities must tight.
Now we prove OPT < S.(("). Since the third constraint Fig. 2 ensures that actions excluded form A must have suboptimality gap 2 8, A is an overestimate of the true 6-BR set, i.e., A 2 (R..a))))). Therefore, we have
3x(p*)=
Σ (A, (A,)EE
min (EBRA(((A.s))
{(((Aa))))
Σ (A,)EE
min (EBRE(M(A.a)
Mulw)yp (w, A, d,ā))(((AA.)).)
WER
Σ
min aEA
Σ
(A (Ra(A())))
(A,ajE
WER
Σ x: (A,
(first constraint in Fig. 2
(M,)e
=OPT,
(optimality of x (A, ā) in Fig.
which completes the proof.
Omitted Proofs from Section
D.1 Proof of Lemma 4.4
Proof. We establish this theorem by showing that any two adjacent polytopes A(A,,))) (As, the m-dimennsional simplex corresponds to neighboring vertices (Ai, ā.) and (A2, u2) in the symmetric difference graph. Since polytopes (A.a) form partition of the convex simplex A(?), any path through the simplex's polytopes translates into connected path in the symmetric difference graph G, therefore establishing the connectivity of the subgraph induced by y
17

---

If A (A), (Ag,as) are adjacent, they must share common face, which belongs to hyperplane in H. Consider the following two cases:
Case 1. If the hyperplane is Ewen (r())((w,))) a) - r(w, a²)) ))- = 0 for some pair of actions (a, d'). that that defines each polytope, it must be the case that a, a' each ã1 and a' dg. Therefore, show that
According to the semanties in eq. (3)
corresponds
action in á1, ag. WLOG assume {(A1,01), (Ag, ā E E, it suffices to establish A1 = A2-
Consider two posteriors Yn E (()) and P2 E (AA),z)) such that || - 12 l v E for an infinitesimal > O, and both Ml, l22 have a distance at least en from all other hyperplanes in H. Such choice implies
Va A, a)) r(2,, S | p2l11 =.
r((1,,1) - min r(u1, a) s å Eo, and r(u2, 22) minae ( a) S Eu-
Consider the process of fixing Eo and sending + For any a E A (R1 we have r(u2, a) 2 r(u1, a) - 2 r(u1, ā1) - (6 - -0) - 2 r(p2, ā1) 8 + 5o 2s > r(u2, ā1) - 6, which implies a E BR₂( = A2 and therefore A1 S A2. In addition, symmetric argument implies that A S A1. Therefore, must be the case that A A2.
Case 2. If the hyperplane is Ewen ()())((wwa)) - r(w, a")) = 8 for some pair of actions (a, d'). Once again, we can find two posteriors μ1 E (())a and u22 E (Ag.ag) such that || - p2 ll S for infinitesimal E > O, and both μl, #2 have distance of at least Eo from all other hyperplanes in H. This immediately implies ã = 22 because otherwise the hyperplane Ewen [(w) (r(w, an) - r(w, a2)) = will have to separate μ4 and 122. A similar continuity argument to that the previous case shows that d2 = and (Ai \ A2) U (A2 A1) {a'}. Therefore, in both cases we can conclude that {(A1, (A2, ā2)} e E. This finishes the proof of Lemma 4.4]
D.2
Proof of Lemma
Proof. The first bound follows from following set of hyperplanes defined by every pair of receiver's actions:
|Σ|
m22=1_ For the second bound, consider the
[u(w)((e. -(w,,,))))) - }
H U Σ ((w)(r(w))) a(), = 0, Σ LEB
wER
They cut the (m dimeessiia simplex into at most
2n² S m
S n ((m)
cells (Halperin and Sharir 2017
Theorem 28.1.1]. Since the boundaries of each open polytope (AA,a are defined by a subset of hyperplanes in H with either strict or non-strict incqualities, each polytopes remain undivided by any hyperplane. Therefore, we have |Σ|| < n O(m),
D.3 LP for checking the feasibility of state-action tuples
E Proof Theorem 5.1
Proof. For any given E (0, 1), we establish the NP-hardness by constructing a reduction from the NP-complete problem of Subset Sum (see, e.g., Section 8.8 of [Kleinberg and Tardos 2006 to the problem of finding the optimal 8-robust sender utility in Bayesian persuasion against approximate responses. This reduction maps instances of the Subset Sum problem to instances of 8-robust Bayesian persuasion such that an instance of the Subset Sum problem has a solution (a YES instance) if and only if the corresponding 5-robust persuasion instance yields an optimal utility of least J.
We start by introducing the format of subset sum instance. subset sum instance is given by set X (-1,-" } of integers where sum(X) Σn It 0. The problem is to decide whether
18

---

maximize E
6:/4
subject to
Σ ((w) (r(w,)) - ((w,a) 20,
WESt
Σ (w) ( a) - aw) =d -,
Va E A
WEf
Σ (w) (r(w, a) - rww, a²) 2 d
Va' E A A
WER
Σ (w) =
WER
p(w)
2
Yw E Ω.
Figure 4: LP for checking the feasibility of (A,â) E. The tuple is feasible if and only if 0.
or not there exists subset of indices J C [nx] such that [J] 2 and sum(X.) EYEe x, 0. If there exists such J, then X YES instance. Otherwise, it NO instance. One may check the above version of the problem is also NP-hard. In particular, the requirements that sum(X] = 0 and [J] = 3 are without loss of generality, because one may add an additional integer to offset the sum of all integers if it is nonzero to begin with, as well as enough 0's so there is always subset of size that sums to 0 iff we have a YES instance. We construct robust persuasion instance as follows.
States and prior distribution The state space is defined as Ω = {wi,... ,.,) with |S2| = [X] = n, and the prior distribution μi Unif(S?) a uniform distribution over the entire state space.
Receiver's action space The receiver's action space A = AUBUC consists of three categories of actions: malicious guessing actions A {ai, ".p J. benign guessing actions B (bi, }. and sign matching actions C' = [c+, c-
Utility functions We define the sender's utility and receiver's utility follows. For ease of presentation, the range of the receiver's utility is designed to be [0, 2]. but it not hard to rescale it to [0, to fit our modeling assumptions.
For a malicious guess a, E and any i E [n]. the utility functions are defined as
=
r(wy, 0.) max {1 1 1-2, =1- 0). i swwj. az) 0.
(6)
At high level, malicious guesses result in constant O utility on the sender, but the penalty incorrect guesses on the receiver's s side relatively minor - on top of the base utility of 1, the receiver only suffers a utility loss of _ (when d < 1 2) for an incorrect state guess, which implies that the receiver secures a utility of 2 1 5 as long as the guess is correct with a probability at least 2. This choice utility function guarantees that to obtain nontrivial utilities, the sender must prevent the receiver from adopting malicious guesses by creating enough dispersion the posterior distributions. In particular, the posterior probability any state should not exceed 2
For benign guess b, E B for any i E [n), the utility functions are defined as
[1, {1 5. i
i=j s(w,,b))
i=j itj"
b,) b(w,,b))
At a high level, benign guesses, correct, are beneficial for both the sender and receiver. They are intended to encourage the sender to concentrate more probability mass on some certain state in the posterior distribution. To see this, note that as long as the state w; is in the support of the receiver's posterior, the excepted utility of the receiver will exceed 1 8
19

---

and the corresponding benign guessing action b, enters the ó-BR set. For the sender, the expected utility under malicious guess b, reaches I only when the posterior probability on Wi is at least 2. Therefore, to guarantee that the sender has an expected utility of at least 1/2, the posterior of any state in the support should be no less than 2/n.
For the matching actions C' [c++ c- the utility functions are defined as
1
(0) 4M J)
sww,,
4M 23
(8)
where M M=En Ezex | > 0. In this case, the receiver gains utility when her chosen action matches the sign of the expected value of x; under the posterior distribution, whereas the sender loses proportional amount of utility. Specifically, when the posterior is uniform on a subspace of size 2 - a design choice that is encouraged by the first two categories of actions- the receiver chooses agn-matching actions based on the sign of the sum of the corresponding subset's elements. In this special case, the sender's utility falls below < unless the subset sum equals zero.
Now, we formally show the reduction from the subset sum problem to d-robust optimal signaling scheme by dividing the proof into two claims.
Claim E.1. If X is YES instance, then S3 Ss((") ) 2
Proof of Claim E. For notation convenience, for any subset of indices J S [12] and any set Q s.t. the elements of 32 are indexed by [n], we use X, to denote the subset of elements with indices in J, ie., X, = fwy j E J). Let J C [n] such that |J] =
2 and sum(X,) = Σje, Ty = 0. Consider the following signaling scheme: sp" (w),0+) = 1 [i J] 40t (w,,a_) = 1 [ ([n] \ J)]- Since the signaling scheme deterministic, we have Mo+ Unif([l,) and pa_ Uni((S(m)..))
To compute the robust utility of up", we first compute the 6-BR set BRs(Mo.). ). For the sign-matching actions e E C, we have
r r(po c)
=1
8
2
Σ
zj 1.
4M
JEJ
because the subset X, is of sum O. For malicious guesses a; E A, note that Po+ (wy) S 2/n for any wy E Ω2 thus we have
r(po : a:) -
2 + (1-2) n -1
8
1 8.
For any benign guesses by E B, we have
r(Uor, bi) 1 (wi) (1 - 5)(1 Mo+ (wi)) 10--81 5(1 Mo (wi));
which implies that r(Moy b.) > 1 - 8 if and only if Mo+ (wi) > 0. Therefore, we have BRo(Hot)
By UC.
As for the sender's robust utility, we have
2
2
2
1
s(uoy, =1
+
1
2
4b, E B
nl
2'
2
1
8
1 sum(X))
spoo c) = 4M
n
2
F
4M
n
2'
EeEC. C.
jEJ
Therefore, have min. s (1o4 a)
A similar analysis show that BR3 B[nlyJ U C and min
Therefore,
S > So((p) (04)
min aEBRs(0+)
s(Po4 a) + (o-()- aEBRe(o_)
min s( , a) 2
Claim E.2. If the optimal sender's utility satisfies S3 1. then X must be YES instance.
20

---

Proof Claim E.2 For every posterior distribution No. we show that the worst-case expected sender utitiliy fs(pa) - (R, s (Mo, a) I 2. and the equality holds only when Hoa = (nif(X)) where |] = and sum( O. Therefore, if $ 2 2. then fo (1r) S must hold with equality for all E x, which implies the existence of subset with size and sum O i.e., X is YES instance.
Consider the following cases:
Case 1. If E (1a) for some [n]] then fa(Po) I a
=
Case 2. IF (R n A Consider two subcases based on whether not r(Ho, a (pa)) > In the case of r(Pa. a (pa)) > 1, it must be that a" (Pa) C' because other actions all have receiver utility S From the design of sign-matching utilities, the sender's utility exceeds and only if the receiver's utility is strictly lower than 1, so we must have fō(wz) S s(Ma a" (H=)) < 2' Therefore, it remains consider the of r(Po; a" (px) S 1.
On the one hand, combining with the fact that BRs (Ha) n this gives
max r(Ma, a.) & r(Ha, a" (pa)) - < - = a:EA
max Ma (wi) 1 sE[n]
Which implies that all posterior probabilities should be no larger than On the other hand, let supp(u<), then for all E J, have
r(Ho, by) > 1 - 8 2 r(ua, a² ((a)) 6,
which implies B, S BR)( We further consider the following two subcases:
If li E J, s.t. ( (w;) 2 then we have f6( S s(M,, b,) 1. +1 2)
Otherwise, have minjeJ Po (w,) i... all non-zero posterior probabilities should be smaller than 2, Since Equation (9) implies that all posterior probabilities should also be n. no larger than it must be the case that they are exactly n i... Hg is uniform distribution n supported on exactly [J] = elements. Therefore,
1 2
1
fo(Ma) min spo. b.) = 1 7 YEJ
(1-2/1)
2
1
2
Moreover, the uniform distribution also implies r(po, c+) = 1 Together with the fact that r(pa, a" (po)) I 1, have
+
5
2. (sum(()))
2
4M
8
r r(Ha: Cagn(sum(X,, x,))) = 1 +
sum (X,)) & r(po, ("(o) s + sum(Xy) = 0.
2Mn
(10)
Therefore, C [ri] subset of size that satisfies sum(X)) 0, and thus X is YES instance. In this case, we have BR(Hg) B, U C and fa
In conclusion, we have shown that all but the last case have fs( < 1. whereas the last has both fa(u=) and that the subset sum problem is a YES instance. This finishes the proof of the claim.
Combining Claim E. and Claim E.2 implies that S 2 if and only if the subset sum problem X is YES instance. We have thus established a reduction from the subset sum problem to that of computing the optimal 8-robust signaling scheme, which proves the NP-hardness of the later problem.
D
F Proof Theorem 5.2
Proof of Theorem 5.2 Let OPT be the optimal objective value and let & be the signaling scheme induced by the optimal solution sp' We divide the proof into two parts: the first part proves
21

---

OPT 2 $3 - and the second part proves Sx( 2 OPT - 4s'. Putting both together establishes the claim because
(x( 2 OPT - 45' 2 53 4E'
S 55' 5 E,
where the last step follows from setting ='= in Fig.
To prove the first inequality of OPT 2 Sg -e', we show that the optimal robust signaling scheme can be discretized to fit our LP with no more than discretization error. Specifically, let yp Ω + be an optimal signaling scheme that has S((t)) = =g.- We will construct LP variables that are feasible in Fig.
For each a E E. there exists Th GE such that Va E A, |s(Ha, a) s(T,. a)l S E. let ((z,a,) 3
be the subset of signals a E E with ş = Po: (Po) â, and
à
argmin
a))
(11)
We define yp as merging the signals in (maa))- Formally,
(( &
((w,
(12)
Such a construction immediately satisfy the last two constraints the LP, because all the subsets E(,āū,)) S Σ where (jz, a, à) Σ form partition of the original signal space E. The first two constraints are also satisfied because for each şı E Jk.
Σ No (w))) H,, (s(w) a') s(T, a) ++)
WER
-E (w(w))
Σ
o(w,o) (s(w,a') s(T a) +
(definition of yp in (12)
WEs
(E..)....)))
2 Σ (w)
Σ
o(w,o) (s(w, - s(Mo, a))
(s(Ho, a) - s s(Ti,) a)l <
WEll
(EL
Σ
Σ
Mo(w)yp(w, 0) al) s(Mo, a)) = =0,
(Bayes' rule)
dEE(T, WER
and similar analysis verifies Ewen (pww H., ã, ()) a') s a) - =) S. For the third constraint, since à is the best response to every E a) it should also be the best response to the combined signal (n, à, i). For the fourth constraint, for tuple (1, a, â) E and an action a such that (11, a) < <s(,, à) 25', we have
Yo E [(paaa)):
s(Ha, a) S s(H,,) a) < < - s s(No,a)
Together with the choice of à in Equation (11) that à minimizes s(Ho a) for all a E (Ra we have r(Ho, S r(Mo, à) for every ((, Therefore, the fourth constraint is satisfied as
Σ (o(w) T, à) (r(w,a) r(w, 0) WEB
Σ oEL
p(a) (r(po a) r(Mo, 8) 2 0.
Finally, for the LP's objective value, we have
OPT
Σ
(o(w)
Σ plu,
WER
(n.ā,)eE
Σ (o(w) Σ
((w,,,,, (5(14, à) e')
(the first constraint)
WER
(nā,aeet
Σ Ho(w) Σ ((w, (s(F.) -e))
TT. - T for all e a)))))
wen
min (MMa)
Σ (o(W)<((w, σ) o)s(To) a) -
(definition of eq. (11)
22

---

-S((p) -'' Sž E'.
We proceed to prove the second part of the theorem, namely the signaling scheme & induced by optimal LP solution 4² satisfies (F) 2 OPT - 4e'. The key step to establishing this claim is to show that, v(μ, a, â) E Σ, the sender's utility under the worst-case 6-BR strategy pa((z,, a, û)) is not much worse than that under action à. We establish this using proof by contradiction, Suppose an action a (5((TT â, a)) E (Rg(Hp.a.c) satisfies s()),,ä,a) a) < ((A(y,ā.)): Q) 4 then we should have o(T,, a) < a a) 2s' because the first and second constraints of the LP in Fig. ensures
s ( a) {( a) + < s(P(u,,))) d) 35' s( à) -2e..
However, from the fourth constraint, in the case of S(T, a) 8(T,,a) 2e', we have
Σ Ho(w)y(u, T,, â) (r(w, ā) r(w,a) a) 6) 0 WE
T(Mmaa)) a) T(M a) 8,
which contradicts the assumption of s(Umza,a); a) 2 s s((iZa,)))) 4s'.
Therefore, must have
(13)
Finally, for the sender's robust utility, we have
So( = Σ mo(w)
Σ a(w,p,ā,a) a(w, po((u, a a,)))
WER
(M,
Σ
G((,, a)) ((UT,,,))) (s(F,,,,
(Bayes' rule)
(M..,))E
Σ
G( ā, a)) (s(M a) -E")
(From Equation (13)
(T
Σ Mo(w)
Σ
llw, a, s(w, à) 45'
(Bayes' rule)
WE
(T,
-OPT -
23

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction discuss technical results and noting else.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In particular, we discuss why the general problem is computationally intractable unless P NP.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]

---

Justification:
The full model is given and all claims are proved.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
No experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
25

---

Answer:
[NA]
Justification:
No data or code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ cppppi.ccppulli//uuuiu wwwtii/gguie///eeeeceoocc CoodeSubeiiie ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
No experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
No experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
26

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
No experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: httpp:s:///errpss.../ htt.:/p.............ttt.ccs.....
Answer:
[Yes]
Justification: In particular, have done our best preserve anonymity.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper is purely theoretical without immediate societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
27

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No data models used.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: No assets used.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwppppswpptseeee whworee.wthhhe....c. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
28

---

Answer:
[NA]
Justification: No assets introduced.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing human subjects involved.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No human subjects involved.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
29


Reviews:
[{"review_id": "u08M7gIxNR", "reviewer": "Reviewer_BTN6", "summary": "This paper studies Bayesian persuasion settings under approximate best response, where the receiver may choose suboptimal actions based on their beliefs. The authors develop efficient algorithms to compute an (almost) optimal sender commitment. First, they show the failure of the revelation principle. Furthermore, the paper develops polynomial-time exact algorithms for small state or action spaces and a quasi-polynomial-time approximation scheme (QPTAS) for the general problem. It also shows that no polynomial-time exact algorithm exists for the general problem unless P = NP.", "questions": "- Is the approach discussed above with small state spaces a possible approach?\n- Is your approach employable for a multi-type receiver?", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The paper studies an interesting problem for the Bayesian persuasion community.\n - The paper shows some interesting results and characterizations.", "weaknesses": "- The two main results, QPTAS and the hardness result, are presented at the end of the paper without explanations or intuitions. I believe this aspect should be improved.\n\n- Why, in the 'algorithm with small state spaces', you need the 'explore' algorithm and you introduce the 'Symmetric difference graph'? Maybe I am wrong, so please correct me if I am, but I think you can simply take the vertices of the regions $\\Delta_{(A,a)}$ (which are clearly exponential in $m$) and instantiate an LP with those vertices in the space of posterior distributions (see, e.g., Section 2.1 in [1]). This approach would require at most half a page and would simplify the current approach.\n\n- It is unclear to me how different your approach is compared to the one used by [2] when either the number of states or actions is fixed.\n\n- Finally, the knowledge of $\\delta>0$ limits the contribution of the work.\n\n[1] Castiglioni, M., Celli, A., Marchesi, A., and Gatti, N. Online bayesian persuasion. Advances in Neural Information Processing Systems, 33, 2020.\n\n[2] Jiarui Gan, Minbiao Han, Jibang Wu, and Haifeng Xu. Robust stackelberg equilibria. In Proceedings of the 24th ACM Conference on Economics and Computation (EC), page 735, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed and insightful comments.\n\n**QPTAS and hardness not explained**: we agree this is suboptimal.  We made a hard choice here due to the strict page limit.  There is a high-level description of the QPTAS in Appendix F.  We find the proof of the hardness result particularly interesting from a technical perspective, though we couldn't find a more concise way to describe the main idea due to the nature of such hardness reductions.  We will use the extra page afforded by the camera-ready version to provide more explanations in the main paper.\n\n**Small state spaces algorithm**: we are not sure if we correctly understand your proposal, but based on what we understand: our algorithm is essentially doing what you proposed.  The \"explore\" subroutine is needed precisely because we need to *find* the vertices of the regions $\\Delta_{(A, \\tilde a)}$ -- we don't know which $(A, \\tilde a)$ pairs to consider a priori, and we can't consider all of them because just the enumeration would cost too much (time exponential in $n$). Therefore, we abstract the structures of polytopes in the “space of posterior distributions” into the “symmetric difference graph”, on which we can utilize the graph algorithms to efficiently find all feasible signals, i.e., “vertices” that you described. We are happy to continue the discussion if you find the above unsatisfactory.\n\n**Fixed-parameter algorithms, comparison to Gan et al.**: very superficially, our algorithm has to deal with states, while Gan et al.'s doesn't.  In particular, we are not aware of techniques similar to the \"explore\" subroutine used in the fixed-number-of-states algorithm (given that it is in fact necessary) in similar contexts.  Even our fixed-number-of-actions algorithm combines the classical LP for Bayesian persuasion with the structural property that we prove (Lemma 3.2), whereas Gan et al.'s algorithm generalizes the classical algorithm for Stackelberg equilibrium by Conitzer and Sandholm (\"Computing the Optimal Strategy to Commit to\").  As a result, our algorithm solves a single LP (which is in a sense necessary), and Gan et al.'s enumerates the follower's response and solves one LP for each possibility.  Please also refer to our response to Reviewer zPak for more detail.\n\n**Knowing $\\delta$**: the assumption can be partially relaxed since the sender can estimate $\\delta$, e.g., through binary search.  Once a guess of $\\delta$ has been made, the sender can implement the corresponding strategy and determine if the guess is too optimistic by observing whether the realized payoff is lower than expected.  Note that here we need certain monotonicity properties: if the guess is too small, then the payoff will be upper bounded by the actual optimal payoff, which is upper bounded by the optimal payoff under the guess; if the guess is too large, then the implemented strategy also works for any smaller $\\delta$ (including the actual one), and the resulting payoff will be at least as good.  We will discuss this if space permits.\n\n**Multi-type receiver**: our results should generalize to the case of a fixed number of types.  The idea is to construct the type-free LP for each type separately, and then consider the \"product LP\" where each product signal is a vector of signals, one for each type.  One would also modify the objective function to incorporate the prior distribution over types.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vrrY3m2DTg", "reviewer": "Reviewer_FR8F", "summary": "This paper studies the Bayesian Persuasion problem under the condition that the receiver may respond suboptimally. The authors provide a few computational results on the problem from its computational hardness to the approximation algorithms.", "questions": "Please address my concern in the weakness section.", "limitations": "n/a", "rating": 3, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 1, "strengths": "The paper considers an important and realistic problem on how to optimize the sender's information design when the receiver may not respond optimally. The paper provides a few computational results on the problem, which is a valuable addition to the existing literature.", "weaknesses": "The result of this paper is almost a copy-paste of the paper, Robust Stackelberg Equilibria, by Gan et al. [2023]. Both the hardness result and the design approximation algorithm are identical, and it is unclear what is the technical contribution of this paper, except a slight change of the problem setup. Moreover, it has already been noticed by the community that the Stackelberg game and the Bayesian Persuasion problem share the same structure, and it is not clear what is the new insight that this paper provides. See e.g. [1]. While the paper Gan et al. [2023] is cited, none of the similarities in the technical results are discussed in the paper. This can raise an ethical flag. Hence, I urge the authors to provide a thorough discussion of the technical contribution of this paper and how it is different from the existing literature.\n\n[1] Jiarui Gan, Minbiao Han, Jibang Wu, and Haifeng Xu. Generalized Principal-Agency: Contracts, Information, Games and Beyond.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments.\n\nWe respectfully disagree with the view that our paper is \"almost a copy-paste\" of the work by Gan et al., and that the results are \"identical\".  While we recognize the high-level similarities between Stackelberg games and Bayesian persuasion, we believe that the community continues to find independent interest in each of these problems. In particular: \n\n**High-level differences between Stackelberg games and Bayesian persuasion**: one could certainly argue that Bayesian persuasion instances are a particular class of Stackelberg games -- in fact, one could make similar arguments about other important fields of algorithmic game theory / economics, such as dominant strategy mechanism design.  However, such a reductionist approach offers little help in understanding the specific structure of Bayesian persuasion even in the most basic settings (see, e.g., \"Bayesian Persuasion\" by Kamenica and Gentzkow).  When it comes to computation (which is the main focus of our paper), yet another issue arises: the computational complexity of a problem depends crucially on its representation.  The standard representation of an instance of Bayesian persuasion is typically much more succinct than the flat representation of the corresponding Stackelberg game (where the leader's strategy space is all feasible policies of the sender in the Bayesian persuasion instance), which means an \"efficient\" algorithm under the latter representation may not be \"as efficient\" under the former representation.\n\nBelow we provide a **detailed comparison to the work by Gan et al.**  We will focus on concrete differences, which are easier to describe and verify.  In particular, it should be clear from the differences below that the results are not \"identical\".\n\n- **Model**: allowing the \"agent\" / \"follower\" / \"receiver\" to choose a response that is suboptimal by a given amount is a standard approach in algorithmic game theory when robustness is desired.  Both our work and that of Gan et al. take this approach.  However, the first major difference (both conceptual and technical) already shows in the respective models: the succinct representation of a Bayesian persuasion instance has the additional component of *states*.  This in particular means the sender's strategy is a randomized mapping from states to posterior beliefs, which is, superficially speaking, of much higher dimensions than a Stackelberg equilibrium.  In fact, since the classical revelation principle is no longer valid, one may suspect the former strategy space is infinite-dimensional (we show this is not the case).  As we argue below, this has significant technical implications to the computation of an (almost) optimal strategy.\n\n- **Structure of optimal strategies**: our positive results rely crucially on a structural property of optimal strategies that we prove (Lemma 3.2), which doesn't have a counterpart in robust Stackelberg games.  The property says that while there are infinitely many possible signals, restricted to optimal strategies, many of them can be grouped, and we only need to consider a finite number of representative signals.  This in particular means the effective strategy space of the sender is finite-dimensional.  Note that here, the receiver may choose different actions depending on the signal sent.  In contrast, the leader's strategy space in a robust Stackelberg game is naturally finite dimensional, and the follower always chooses a fixed action in response to the leader's strategy.\n\n- **Algorithm for fixed number of actions**: our algorithm when the number of actions is fixed (Proposition 3.3) is a natural combination of the classical LP for Bayesian persuasion and the above structural property.  In particular, we solve a single LP for the sender's optimal strategy.  For comparison, the fixed-$n$ algorithm by Gan et al. generalizes the algorithm by Conitzer and Sandholm (\"Computing the Optimal Strategy to Commit to\"), which enumerates the follower's response and solves one LP for each possibility.\n\n- **Algorithm for fixed number of states**: here we deviate significantly from existing techniques.  In particular, our algorithm relies crucially on the notion of symmetric difference graphs and connectivity therein.  To our knowledge, such techniques have not been employed in the context of Bayesian persuasion or Stackelberg games.  In contrast, there are no states in Stackelberg games to begin with.  Note that the parameter $m$ in Stackelberg games plays an intrinsically different role than the number of states in our model, and Gan et al. present no efficient algorithm when $m$ is fixed (though the comparison itself may not be meaningful in the first place).\n\n- **Hardness result**: first we note that it's not uncommon for a well-motivated problem to be computationally hard, and the fact that both our problem and Gan et al.'s are hard doesn't necessarily mean the two are otherwise similar.  Our hardness result is based on a fundamentally different reduction from Gan et al.'s.  In particular, we reduce from the problem of Subset Sum, whereas Gan et al. reduce from Exact Cover by 3-Sets.  Details of the two reductions bear virtually no similarity.\n\n- **Approximation algorithm**: our algorithm shares the same high-level idea with Gan et al.'s (as well as many other approximation algorithms involving the probability simplex): one first discretizes the probability simplex into a reasonable number of representative points, and then considers the problem restricted to these points.  Despite this high-level similarity, the concrete algorithms are sufficiently different.  Specifically, the two algorithms are based on their exact (and inefficient) versions respectively, which means our algorithm solves a single LP, and Gan et al.'s enumerates the follower's response and solves one LP for each possibility.  Our algorithm also has to deal with additional challenges introduced by the states and the prior distribution.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HzrrXUDt4M", "reviewer": "Reviewer_R1Q8", "summary": "This paper studies a variant of the Bayesian persuasion problem where, instead of best-responding, the receiver $\\delta$-approximately best responds to the sender. Specifically, upon receiving a signal, the receiver takes the $\\delta$-optimal action that is worst for the sender on the induced posterior belief. The authors study the complexity of computing the optimal robust signaling scheme for the sender, obtaining four results:\n\n(1) Unlike the classical best-response model where direct-revelation signaling schemes are sufficient to be optimal, direct-revelation schemes are sub-optimal by a factor of 2 in the approximate-best-response model.\n\n(2) The authors give a linear program with size $O(2^n nm)$ to compute an optimal robust signaling scheme (which is not a direct-revelation scheme); $n$ is the number of actions and $m$ is the number of states. The signal in this signaling scheme is interpreted as a tuple $\\sigma = (A, \\tilde a)$ of a set of $\\delta$-best-responding actions $A$ and a best-responding action $\\tilde a$.\n\n(3) Then, based on the observation that the number of feasible tuples $\\sigma = (A, \\tilde a)$ cannot be more than $O(n^{O(m)})$, the authors design an algorithm to compute the optimal robust signaling scheme with $poly( n^{O(m)} )$ complexity.\n\n(4) Finally, for the case of large $n$ and $m$, the authors show NP-hardness of exactly computing the optimal robust signaling scheme and give a quasi-polynomial-time approximation algorithm.", "questions": "(Q1) What is the running time of the QPTAS you design for the general case (Theorem F.1)?", "limitations": "**Suggestions:**\n\n(1) Typo: The equation between Lines 192 and 193: \"$r(\\mu_\\sigma, a)$\".\n\n(2) Typo: the $s$ in Definition 2.1 should be $\\sigma$.\n\n(3) Typo: In Remark 2.2, the phrase \"that achieves sender's objective\" is confusing and can be deleted.\n\n(4) It is better to explicitly write $\\sigma = (A, \\tilde a)$ in the first contraint of the optimization problem in the Figure 1.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "(1) [Significance] Bayesian persuasion with an approximately-best-responding receiver is a natural extension to the classical best-response model. As showed by the authors, this problem presents significant technical challenges because the classic idea of restricting to direct-revelation schemes no longer works. So, this problem is both conceptually and technically interesting.\n\n(2) [Quality] The results are comprehensive and non-trivial. Both positive and negative results for the general case are given. And positive results for the special cases of constant number of actions and constant number of states are also given.\n\n(3) [Originality] To design an efficient algorithm for the case of constant number of states (Section 4), the authors make the key observation that the number of feasible tuples is $O(n^{O(m)})$, proved using a fundamental theorem in computational geometry. This observation is unexpected at first sight and the connection with computational geometry is interesting.\n\n(4) [Quality] Discussion of related works, especially Appendix A, is comprehensive and clear.\n\n(5) [Clarity] Writing is clear. The introduction nicely summarizes the technical contributions and high-level ideas.", "weaknesses": "I don't see significant weaknesses.\n\nI only have a minor concern regarding the fit to NeurIPS. Most of the algorithmic game theory papers on NeurIPS are related to machine learning in some ways, but this paper is a pure AGT paper with no obvious machine learning components (at least in my opinion).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed and insightful comments.\n\n**Suggestions**: Thank you for the helpful suggestions, we will revise our paper accordingly.\n\n**Running time of the QPTAS**: the running time generally depends on the specific algorithm chosen to solve the LP given in Theorem F.1.  Algorithms for LP are quickly evolving, but we can apply their result as a black box to obtain running time guarantees in our problem.  From a quick search, the state-of-the-art algorithm (or something close enough) for general LP seems to run in time $\\tilde{O}(n^{2 + 1/18}L)$, where $n$ is the total number of variables and constraints, and $L$ is the number of bits required to encode input numbers.  Combining this with the bound on the size of the LP in Theorem F.1, we get a running time of $\\tilde{O}(n^4 m^{25\\log(2n) / \\varepsilon^2} L)$.  It might be possible to apply special-purpose LP algorithms that exploit the structure of our LP formulation to get a better running time.  In any case, the running time is polynomial in $n$, $m^{\\log n / \\varepsilon}$, and $L$ (the number of bits required to encode input numbers).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wgyjO1VOdt", "reviewer": "Reviewer_zPak", "summary": "The paper considers the problem of BP under \\delta-best responses of the receivers. This means that there might be multiple actions that are BR to a specific signalling scheme. This creates non trivial problems of the algorithmic problem of computing the optimal signalling scheme. The paper provides poly-time algorithms with constant number of actions or states and quasi-polynomial algorithms for general case.", "questions": "see weaknesses", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper extends the problem of stackelberg equilibria with delta-BR to the special case of Bayesian persuasion. This is an interesting problem and has somewhat different flavour then the general stakelberg.", "weaknesses": "I would like to know more about the connection between the robust Stackelberg paper. Why do you need to prove again the hardness and do not reduct from the hardness of the robust Stackelberg paper? What are the differences between the results there and here. The current work for sure cite that one but fails to discuss properly what is implied and what is not. I feel that I need to be convinced that even if the results and the techniques of the two papers are similar, this one deserves a spot at neurips. I hope that the authors would discuss this in details in the rebuttal and then add such the discussion to the new version of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments.\n\n**Need for a new reduction**: the fundamental reason that the two problems are not necessarily \"comparably hard\" is that the computational complexity depends crucially on (1) the representation and (2) additional special structure.  It is certainly true that the Bayesian persuasion problem can be viewed as a Stackelberg game, but:\n- The flat representation of the Stackelberg game corresponding to a Bayesian persuasion instance has a huge strategy space.  In particular, each candidate strategy of the sender is a (randomized) mapping from states to signals.  This means the sender's strategy space is at least exponentially larger even in the classical setting where the revelation principle holds.  As a result, a polynomial-time algorithm under the Stackelberg game representation might very well be an exponential-time algorithm under the Bayesian persuasion representation.  This in particular means the Bayesian persuasion version might not be easier than the Stackelberg game version.\n- On the other hand, Bayesian persuasion is a *special* class of Stackelberg games, which means it might exhibit additional structure that makes the computational problem much easier despite the difference in representations.  This in particular means the Bayesian persuasion version might not be harder than the Stackelberg game version.  Indeed, our proof of hardness directly reduces from Subset Sum.\n\n**Comparison with Gan et al.**: below we provide a detailed comparison to the work by Gan et al.  We will focus on concrete differences, which are easier to describe and verify.  We will also include a shortened version in the main paper (if there's space), as well as the full comparison in an appendix.\n\n- Model: allowing the \"agent\" / \"follower\" / \"receiver\" to choose a response that is suboptimal by a given amount is a standard approach in algorithmic game theory when robustness is desired.  Both our work and that of Gan et al. take this approach.  However, the first major difference (both conceptual and technical) already shows in the respective models: the succinct representation of a Bayesian persuasion instance has the additional component of *states*.  This in particular means the sender's strategy is a randomized mapping from states to posterior beliefs, which is, superficially speaking, of much higher dimensions than a Stackelberg equilibrium.  In fact, since the classical revelation principle is no longer valid, one may suspect the former strategy space is infinite-dimensional (we show this is not the case).  As we argue below, this has significant technical implications to the computation of an (almost) optimal strategy.\n\n- Structure of optimal strategies: our positive results rely crucially on a structural property of optimal strategies that we prove (Lemma 3.2), which doesn't have a counterpart in robust Stackelberg games.  The property says that while there are infinitely many possible signals, restricted to optimal strategies, many of them can be grouped, and we only need to consider a finite number of representative signals.  This in particular means the effective strategy space of the sender is finite-dimensional.  Note that here, the receiver may choose different actions depending on the signal sent.  In contrast, the leader's strategy space in a robust Stackelberg game is naturally finite dimensional, and the follower always chooses a fixed action in response to the leader's strategy.\n\n- Algorithm for fixed number of actions: our algorithm when the number of actions is fixed (Proposition 3.3) is a natural combination of the classical LP for Bayesian persuasion and the above structural property.  In particular, we solve a single LP for the sender's optimal strategy.  For comparison, the fixed-$n$ algorithm by Gan et al. generalizes the algorithm by Conitzer and Sandholm (\"Computing the Optimal Strategy to Commit to\"), which enumerates the follower's response and solves one LP for each possibility.\n\n- Algorithm for fixed number of states: here we deviate significantly from existing techniques.  In particular, our algorithm relies crucially on the notion of symmetric difference graphs and connectivity therein.  To our knowledge, such techniques have not been employed in the context of Bayesian persuasion or Stackelberg games.  In contrast, there are no states in Stackelberg games to begin with.  Note that the parameter $m$ in Stackelberg games plays an intrinsically different role than the number of states in our model, and Gan et al. present no efficient algorithm when $m$ is fixed (though the comparison itself may not be meaningful in the first place).\n\n- Hardness result: first we note that it's not uncommon for a well-motivated problem to be computationally hard, and the fact that both our problem and Gan et al.'s are hard doesn't necessarily mean the two are otherwise similar (also see our response to the first question above).  Our hardness result is based on a fundamentally different reduction from Gan et al.'s.  In particular, we reduce from the problem of Subset Sum, whereas Gan et al. reduce from Exact Cover by 3-Sets.  Details of the two reductions bear virtually no similarity.\n\n- Approximation algorithm: our algorithm shares the same high-level idea with Gan et al.'s (as well as many other approximation algorithms involving the probability simplex): one first discretizes the probability simplex into a reasonable number of representative points, and then considers the problem restricted to these points.  Despite this high-level similarity, the concrete algorithms are sufficiently different.  Specifically, the two algorithms are based on their exact (and inefficient) versions respectively, which means our algorithm solves a single LP, and Gan et al.'s enumerates the follower's response and solves one LP for each possibility.  Our algorithm also has to deal with additional challenges introduced by the states and the prior distribution.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper studies a “robust” version of the classical Bayesian persuasion problem, in which the receiver plays approximate best responses rather than exact ones. Specifically, the paper focuses on the computational aspects of the problem. 

One of the main concerns raised by the Reviewers (Reviewers BTN6, FR8F, and zPaK in particular) is about the similarity of the paper with “Robust Stackelberg Equilibria” by Gan et al. [2023]. The latter addresses Stackelberg games in which the follower plays approximate best responses in place of exact ones, in the same vein of the present paper. The concern of the Reviewers is on the technical novelty of the paper compared to [Gan et al., 2023].

Reviewers BTN6 and zPaK, despite concluding that the novelty of some of the results in the paper is somehow limited in the light of [Gan et al., 2023], are generally (weakly) positive about the paper overall. Instead, Reviewer FR8F is largely negative about the paper, claiming that “the result of this paper is almost a copy-paste” of the paper “Robust Stackelberg Equilibria” by Gan et al. [2023]. The claim of Reviewer FR8F is specifically targeted to the hardness result and the quasi-polynomial time approximation scheme (QPTAS) presented in the paper. In support of their claim, Reviewer FR8F is advancing the argument that “it has already been noticed by the community that the Stackelberg game and the Bayesian Persuasion problem share the same structure”.

After reading the paper, the reviews, Authors’ rebuttals, and the following discussion, I developed some considerations that motivate my final decision. I summarize them below.

1. I believe that the claim of Reviewer FR8F on the paper being a “copy-paste” of the work by Gan et al. [2023] is exaggerated. There are indeed some similarities between the works, but these are inevitable given that the present paper is extending the one by Gan et al. [2023] from Stackelberg games to Bayesian persuasion problems. However, I agree with the Reviewers that the authors should have discussed the differences with the work by by Gan et al. [2023] more carefully in their paper.

2. I tend to disagree on the fact that Stackelberg games and Bayesian persuasion problems share the same structure. Bayesian persuasion can indeed be formulated as a particular Stackelberg game, but this completely disrupts the problem representation of Bayesian persuasion and its particular structure. Thus, it is almost always the case that algorithms and results for Stackelberg games are **not** directly applicable to Bayesian persuasion problems. Indeed, if this were the case, then all the research on algorithmic Bayesian persuasion would be pointless, given that we already know almost everything about Stackelberg games.

3. I think that the paper makes nice contributions that completely depart from the results derived by Gan et al. [2023]. As Reviewer R1Q8 is pointing out, one of the most important (and surprising) contributions of the paper is that, in the small-state-space case ($m$ is small), it is possible to obtain a $poly(n^{O(m)})$ algorithm to find an optimal robust signaling scheme. By following the approach in [Gan et al., 2023], one can only get a $poly(2^n, n, m)$ exponential-time algorithm.

In conclusion, given the considerations above and the fact that the paper provides a valuable extension of the model in “Robust Stackelberg Equilibria” by Gan et al. [2023] to the Bayesian persuasion setting, **I recommend that the paper is accepted subject to** the fact that the Authors carefully address Reviewers’ concerns in the final version of the paper. In particular, the authors should provide a detailed discussion of the similarities between the paper and “Robust Stackelberg Equilibria” by Gan et al. [2023].
Decision: Accept (poster)