Computational Aspects of Bayesian Persuasion under Approximate Best Response

Authors: kunhe  yang
hanrui  zhang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 16:43:27

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.

Main paper: 
 introduction: 
 Bayesian persuasion [Kamenica and Gentzkow, 2011] concerns the problem where a 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. A 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, a random apple from a 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 1 from buying a good apple, and -1 from 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 to expected utility 1× 1 3 +(-1)× 2 3 = -1 3 < 0. 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 a credible way (which is a fundamental assumption in Bayesian persuasion), the buyer will buy the apple whenever it 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 a "signal" to the buyer regarding the quality of the apple, which can be either "probably good" or "definitely bad". More specifically, if the apple is good, the sender signals that it is "probably good"; if the apple is bad, the seller signals randomly, that it 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 to their promises. If 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 a more interesting decision. All the buyer knows is that the probability of (1) receiving "probably good" and (2) the apple is actually good, happening simultaneously, is 1/3, and that the probability of (1) receiving "probably good" and (2) the apple is actually bad, happening simultaneously, is 2/3 × 0.499 < 1/3. So, given the signal, the conditional probability that the apple is 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 × 0.499 ≈ 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, a satisfactory solution to the problem is 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, a 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 it 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-solve approaches have proved extremely successful in Bayesian persuasion -at least in settings where they apply.The real world, unfortunately, is less precise than the idealized model. Even in the simplistic example of selling apples, there appear to be numerous subtleties that could potentially derail the supposedly (almost) optimal strategy of the seller. To name a few: the sender may not know exactly the receiver'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 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 posterior belief formed upon receiving a 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, or 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 a 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 a 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 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 us to our main question: despite the lack of a structural characterization, is there a principled and efficient way of finding the optimal strategy for the sender that is robust against such inaccuracy?In this paper, we study Bayesian persuasion in a 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 direct-revelation signaling scheme (i.e., a strategy of the sender where each possible signal is a 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-and-solve 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 LP 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 "semantics" of 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 a 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). In particular, 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 a building block of our further algorithmic results.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 to 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 a result in combinatorial geometry, which bounds the number of "cells" in a 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 O(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 a problem to find these subsets. To this end, we make yet another geometric observation: the cells that correspond to feasible subsets of actions form a single "connected component", which means we 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 a 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 us 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 to 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 0. The idea of the reduction is that such a set of n integers corresponds to a 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 or too few integers must be suboptimal. The latter appears to be a quite ambivalent conditionin 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-time approximation scheme (QPTAS): for any target additive error ε > 0, we give an ε-approximate algorithm that runs in time quasipolynomial in m and n, where the time complexity may depend on ε. 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/ε 2 ) exists, which has already proven useful in other game-theoretic computational problems [Althöfer, 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 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 a 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 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-polynomial size, which can be solved in quasi-polynomial time.We defer a 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 , Rubinstein, 2017 , Babichenko and Barman, 2016 , 2017 , Xu, 2020 , Zhou et al., 2022] and various notions of robust Bayesian persuasion [de Clippel and Zhang, 2022 , Chen and Lin, 2023 , Camara et al., 2020 , Zu et al., 2021 , Collina et 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 of Gan et al. [2023] on robust Stackelberg games. 
preliminaries: 
 Our model builds on the classic Bayesian persuasion model with a single sender and a single receiver. At a 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 a receiver who acts not exactly, but approximately in accordance with their best interest in the decision-making process.Basic setting and notations. Let Ω be the states of the world with |Ω| = m, and ∆(Ω) be the set of all probability distributions on Ω. For all distributions µ ∈ ∆(Ω), let supp(µ) be the support of µ, i.e., supp(µ) ≜ {ω ∈ Ω | µ(ω) > 0}. We use µ 0 ∈ ∆(Ω) to denote the prior distribution over states and assume that µ 0 is common knowledge between the sender and the receiver.Signaling scheme. Let Σ (|Σ| < ∞) be a finite set of signals. A signaling scheme φ : Ω → Σ is 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 φ, then observes the true state of the world ω ∼ µ 0 , and sends signal σ ∼ φ(ω) to the receiver. We use φ(ω, σ) to denote the probability of sending signal σ conditioning on observing ω as the true state, and φ(σ) = ω ′ ∈Ω µ 0 (ω ′ )φ(ω ′ , σ) to denote the marginal probability of a signal σ ∈ Σ being realized.Upon receiving the signal σ, the receiver performs a Bayes update on µ 0 using knowledge about the scheme π to obtain a posterior belief µ σ ∈ ∆(Ω), i.e.,µ σ (ω) = µ 0 (ω)φ(ω, σ) φ(σ) .In addition, algebraic manipulations based on the Bayes' rule suggest that the signaling scheme φ can be viewed as the process of creating a distribution over posterior distributions that satisfy the Bayes plausibility condition [Kamenica and Gentzkow, 2011, Gentzkow and Kamenica, 2016] :∀ω ∈ Ω, µ 0 (ω) = ω∈Ω φ(σ) • µ σ (ω).(Bayes plausibility)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 s : Ω × A → [0, 1] to denote the sender's utility and r : Ω × A → [0, 1] to denote the receiver's utility, where both utilities are normalized to be between 0 and 1. Additionally, for distributions µ ∈ ∆(Ω), we abuse the notations and use s(µ, a) = E ω∼µ s(ω, a) and r(µ, a) = E ω∼µ r(ω, a) to denote the sender and receiver's expected utilities under the state distribution µ.Receiver's strategies A receiver's strategy, denoted with ρ : Σ → A, is a (possibly randomized) mapping from the observed signals to actions which specifies the receiver's strategy of choosing responses. Given a signaling scheme φ and a receiver strategy ρ, we use S(φ, ρ) to denote the expected sender utility, which is computed asS(φ, ρ) ≜ σ∈Σ φ(σ) • s(µ σ , ρ(σ)) = ω∈Ω σ∈Σ µ 0 (ω)φ(ω, σ)s(ω, ρ(σ)).The classical model of Bayesian persuasion assumes that the receiver's strategy ρ(σ) is always the exact best response of the posterior distribution µ σ that maximizes their expected posterior utility (ties are broken in favor of the sender). Formally, the best response action action is defined asa ⋆ (µ σ ) ≜ argmax a∈A r(µ σ , a), 1and the receiver's strategy is assumed to satisfy ρ(σ) = a ⋆ (µ σ ). In this paper, we will relax this exact best-response assumption to allow for 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 ρ(σ) is not too suboptimal compared to the best action a ⋆ (µ σ ). Formally, if we use BR δ (•) to denote the set of δ-optimal responses on the input belief:EQUATIONthen a receiver's strategy ρ :Σ → A is δ-best response (or δ-BR) if it satisfies ρ(σ) ∈ BR δ (µ σ ) for all σ ∈ Σ.We use BR δ (φ) to denote the set of all δ-BR strategies under the signaling scheme φ.Robust sender utility In this paper, we adopt the max-min adversarial robustness perspective and aim to offer robustness guarantees against worst-case δ-BR strategies. We use the robust utility S δ of a signaling scheme to characterize the expected utility under the worst-case δ-BR strategy:S δ (φ) = min ρ δ ∈BR δ (φ) S(φ, ρ δ ).The sender aims to maximize the robust utility through optimizing the signaling scheme. Equivalently, the sender faces a bi-level optimization problem of the following max-min form:S ⋆ δ ≜ max φ ⋆ S δ (φ ⋆ ) = max φ ⋆ min ρ δ ∈BR δ (φ ⋆ ) S(φ ⋆ , ρ δ ). (sender's objective)Solving the optimization problem in (sender's objective) includes (1) finding an 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 δ-BR strategy). It is not hard to see that the worst-case δ-BR strategy ρ δ that achieves (sender's objective) will choose the worst action that minimizes the sender's utility for each posterior distribution separately, i.e.,ρ δ (σ) ∈ argmin a∈BR δ (µσ) s(µ σ , a).Therefore, the robust utility under any signaling scheme φ can be equivalently written asS δ (φ) = σ∈Σ φ(σ) • s(µ σ , ρ δ (σ)) = σ∈Σ φ(σ) • min a∈BR δ (µσ) s(µ σ , a).Remark 2.2 (Strict inequality in definition of BR δ set). In eq.(1), we use strict inequality so that the sender's strategy space is closed and compact, and the sender's objective is well-defined. This is a non-essential choice: one could instead define δ-BR responses using weak inequality and investigate the sender's supremum robust utility, which would not change the nature of the problem. 
lp formulation and algorithm with small action spaces: 
 As we show in Appendix B, the powerful revelation principle fails in the robustness model that we study. In fact, we establish the following claim. Proposition 3.1 (Proposition B.1 in Appendix B). There exists a sequence of Bayesian persuasion instances with a robustness level δ = Θ(1), such that the following holds in the limit: any directrevelation scheme φ is suboptimal, at least by a factor of 2 or an additive gap of 1 2 . That is, for any direct-revelation scheme φ,S δ (φ) ≤ 1 2 S ⋆ δ , and S δ (φ) ≤ S ⋆ δ - 1 2 .The above proposition highlights the need for new algorithmic ideas to efficiently compute (approximately) optimal robust schemes.In this section, we present a linear program (LP) that computes the optimal robust utility S ⋆ δ and the optimal robust signaling scheme φ ⋆ . 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 be viewed as a generalized (and unfortunately, much less powerful due to lack of best responses) version of the revelation-principle style argument in [Kamenica and Gentzkow, 2011 , Proposition 1] that accounts for worst-case approximate best responses. See Appendix C for the proof of the lemma. Lemma 3.2. There exists an optimal robust signaling scheme that is supported on at most n • 2 n-1 signals, in which each signal σ ∈ Σ corresponds to a unique pair of (A, ã) such that ã = a ⋆ (µ σ ) and A = BR δ (µ σ ).According to Lemma 3.2, it suffices to consider the following signal space:Σ = {(A, ã) | A ⊆ A, ã ∈ A},where each signal σ = (A, ã) satisfies both a ⋆ (µ σ ) = ã and BR δ (µ σ ) = A. Recall from Remark 2.1 that the robust utility can be written asS ⋆ δ = max φ (A,ã)∈Σ φ((A, ã)) • min a∈BR δ (µ (A,ã) )s(µ (A,ã , a).Translating this max-min optimization to a constrained maximization problem, and enforcing the abovementioned semantics for each signal, we arrive at the following (non-linear) program in Fig. 1 . Although the program in Fig. 1 is not yet a linear program, both the first and second constraints can be equivalently written as linear constraints on the conditional probabilities φ(ω, (A, ã)) that define the signaling scheme φ, using the following observation based on the Bayes' rule:maximize φ,x (A,ã)∈Σ x(A, ã) subject to φ(µ (A,ã) ) • s(µ (A,ã) , a) ≥ x(A, ã). ∀σ ∈ Σ, ∀a ∈ A a ⋆ (µ σ ) = ã ∀(A, ã) ∈ Σ BR δ (µ (A,ã) ) = A ∀(A, ã) ∈ ΣEQUATIONTherefore, it remains to characterize the δ-BR response sets, and would be ideal if they could also be equivalently expressed as linear constraints. Unfortunately, the definition of δ-BR sets involves strictinequality constraints due to the issues discussed in Remark 2.2. In particular, for each(A, ã) ∈ Σ, the third constraint is equivalent to (1) ∀a ∈ A, s(µ σ , a) > s(µ σ , ã) -δ; (2) ∀a ∈ A \ A, s(µ σ , a) ≤ s(µ σ , ã) -δ,where (1) involves a strict inequality and could lead to open polytopes. Due to such subtleties, we first consider the LP in Fig. 2 which is a relaxation of the program in Fig. 1 by dropping the strict-inequality constraint (1). The last two constraints in Fig. 1 guarantee that variables φ(ω, A, ã) give rise to a valid signal distribution for every state ω ∈ Ω.maximize φ,x (A,ã)∈Σ x(A, ã) subject to ω∈Ω µ 0 (ω)φ(ω, A, ã)s(ω, a) ≥ x(A, ã), ∀(A, ã) ∈ Σ, ∀a ∈ A ω∈Ω µ 0 (ω)φ(ω, A, ã) (r(ω, ã) -r(ω, a)) ≥ 0, ∀(A, ã) ∈ Σ, ∀a ∈ A ω∈Ω µ 0 (ω)φ(ω, A, ã) (r(ω, ã) -r(ω, a) -δ) ≤ 0, ∀(A, ã) ∈ Σ, ∀a ∈ A\A (A,ã)∈Σ φ(ω, A, ã) = 1 ∀ω ∈ Ω φ(ω, A, ã) ≥ 0. ∀(A, ã) ∈ Σ Figure 2:Relaxed LP for the optimal robust signaling scheme Since Fig. 2 is a relaxation of the original program, its optimal objective provides an upper bound for S ⋆ δ . However, as we will show later, not only does the optimal objective value exactly equal S ⋆ δ , but the optimal variables φ ⋆ also exactly characterize the optimal robust signaling scheme that achieves this S ⋆ δ . 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 O(2 n mn).Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) • The experimental setting should be presented in the core of the paper to a 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, confidence intervals, or statistical significance tests, at least for the experiments that support the 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, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean.• 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 a 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 of range (e.g. negative error rates). Justification: In particular, we have done our best to 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 circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used toWhen there are multiple actions a ⋆ (µσ) that maximizes the receiver's utility, we define a ⋆ (µσ) to be the maximizer that achieves the highest sender's utility. 
efficient algorithm with small state spaces: 
 In this section, we focus on the robust persuasion instances where the action space is large, but the state space is small. For such instances, our key observation is that among the (n -1)2 n tuples in Σ, only a small fraction of them can be realized by posterior distributions and therefore serve as feasible signal candidates. In Section 4.1, we characterize the structural properties of feasible tuples (A, ã) ∈ Σ 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.We formally define the feasibility of a candidate tuple (A, ã) ∈ Σ according to the existence of a posterior distribution that has A as its δ-BR set and ã as its best response action. Definition 4.1 (Feasible subset-action tuple). A tuple (A, ã) ∈ Σ is feasible if there exists some posterior distribution µ ∈ ∆(Ω) such that a ⋆ (µ) = ã and BR δ (µ) = A. We use Σ † to denote the set of all feasible tuples in Σ.For each feasible tuple (A, ã) ∈ Σ † , let ∆ (A,ã) be the set of posterior distributions that satisfy both constraints in Definition 4.1:∆ (A,ã) ≜ {µ ∈ ∆(Ω) | a ⋆ (µ) = ã, BR δ (µ) = A }It is not hard to see that the subsets ∆ (A,ã) partitions the simplex, because each distribution in the simplex is associated with a unique best response action and δ-BR set. That is,∆(Ω) = (A,ã)∈Σ † ∆ (A,ã) .In addition, each ∆ (A,ã) is a polytope in the simplex that is defined by the following constraints that are linear in the distribution µ:µ ∈ ∆ (A,ã) ⇐⇒    r(µ, a) ≤ r(µ, ã), ∀a ∈ A; r(µ, a) > r(µ, ã) -δ, ∀a ∈ A; r(µ, a) ≤ r(µ, ã) -δ, ∀a ∈ A \ a.(3)Our key observation is that the linear constraints that characterize different ∆ (A,ã) all take one of the following two forms based on an ordered pair of actions (a, a ′ ) ∈ A × A:1. Either r(µ, a) ≤ r(µ, a ′ ) -δ, or its complement r(µ, a) > r(µ, a ′ ) -δ; 2. r(µ, a) ≤ r(µ, a ′ ),which give rise to no more than 2n 2 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 a low-dimensional space. According to a fundamental theorem in computational geometry (see, e.g., Theorem 28.1.1 in [Halperin and Sharir, 2017] ), these hyperplanes cut the m-dimensional into at most O (2n 2 ) m-1 cells. This observation helps us to bound the number of feasible tuples in the following lemma. The proof of Lemma 4.2 is deferred to Appendix D.2. Lemma 4.2. The size of the feasible tuplesΣ † satisfy |Σ † | ≤ min n2 n-1 , n O(m) .Next, we establish some structural properties on the set of feasible tuples Σ † that could facilitate the efficient search over candidate signals. In the remainder of this section, we first define a boundeddegree symmetric difference graph on all tuples in Σ, then show that all feasible tuples in Σ † form a connected component in the symmetric difference graph. Definition 4.3 (Symmetric difference graph). In the symmetric difference graph G(Σ, E), each vertex is a tuple (A, ã) ∈ Σ. Each edge {(A 1 , ã1 ), (A 2 , ã2 )} ∈ E represents that the symmetric difference between tuples (A 1 , ã1 ) and (A 2 , ã2 ) is of size 1, which is satisfied for the following two cases:• A 1 = A 2 , and ã1 ̸ = ã2 .• ã1 = ã2 ∈ A 1 ∩ A 2 , and |(A 1 \ A 2 ) ∪ (A 2 \ A 1 )| = 1.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 G induced by Σ † is connected.We defer the proof of Lemma 4.4 to Appendix D.1. At a high level, the proof translates the connectivity of the polytopes ∆ (A,ã) in the simplex space to 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.In this section, we present Algorithm 1 that leverages the connectivity of the feasible tuples to efficiently search for Σ † . This algorithm essentially performs depth-first-search (DFS) on the connectivity graph by recursively searching all the neighbors with symmetric difference of size 1 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 be feasible, e.g., the δ-BR set and the optimal response associated with the prior distribution µ 0 .Note that each tuple (A, ã) ∈ Σ is feasible if and only if there exists µ ∈ Σ that satisfies all three constraints in Equation (3) simultaneously, which can be written as checking the feasibility of the 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 marginmaximization trick in Fig. 4 of Appendix D.3. This LP is defined on a closed polytope, and asserts feasibility if and only if the optimal margin is strictly positive, i.e., ε ⋆ > 0.Algorithm 1: EXPLORE Input: tuple (A, ã) ∈ Σ Check the feasibility of (A, ã) by solving the LP in Fig. 4 , ε ⋆ ← optimal objective value; if ε ⋆ > 0 then Mark (A, ã) checked and feasible; Proof. The correctness of this algorithm is ensured by the connectivity property in Lemma 4.4. It remains to upper bound the number of feasibility checks performed. Since Algorithm 1 only checks new a 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 Σ † . Since each tuple (A, ã) ∈ Σ has at most O(n) neighbors, the degree of any vertex in the symmetric difference graph G is upper bounded by O(n). Therefore, the size of the closed neighborhood is at mostfor actions a ∈ A \ {ã} do If (A \ {a}, ã) is unchecked, call EXPLORE((A \ {a}, ã)); If (A, a) is unchecked, call EXPLORE((A, a)); end for actions a ∈ A \ A do If (A ∪ {a}, ã) is unchecked, call EXPLORE((A ∪ {a}, ã));O(n) • |Σ † | ≤ n O(m) .The final step for optimizing signaling schemes is to solve the LP in Fig. 2 with the original signal space Σ replaced by feasible tuples Σ † . We summarize the entire procedure and its complexity in Algorithm 2 and Corollary 4.6. Corollary 4.6. When the number of states m is small, the optimal signaling scheme can be efficiently computed by Algorithm 2, which involves solving n O(m) LPs of size O(m + n) and then solve a single LP of size m • n O(m) .Algorithm 2: ALGORITHM FOR SMALL STATE SPACES (A 0 , ã0 ) ← (BR δ (µ 0 ), a ⋆ (µ 0 )); Search for Σ † by running SEARCH(A 0 , ã0 ); Solve the LP in Fig. 2 with Σ replaced by Σ † . 
approximation algorithm for the general problem: 
 In this section, we first show that the general problem without any restrictions is computationally hard, then present a 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-time exact algorithm for the robust persuasion problem does not exist unless P = NP. Theorem 5.1. The problem of computing the exact optimal robust utility is NP-hard.In the following, we present a QPTAS that computes an ε-approximate optimal δ-robust signaling scheme φ for any given δ > 0, such thatS δ ( φ) ≥ S ⋆ δ -ε.Our δ-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 ⋆ (µ)) set, we partition the simplex ∆(Ω) into small cells, each centered around a k-uniform distribution µ (to be defined later), and incorporate additional semantics to ensure that the utility profiles s(µ, •) 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 δ-BR sets according to the relative magnitude of utilities at µ and translate the requirements into linear constraints.Formally, for an integer k,a distribution µ ∈ ∆(Ω) is k-uniform if ∀ω ∈ Ω, µ(ω) = kω k for some integer k ω ≤ k. Let G k ⊆ ∆(Ω)denote the set of all k-uniform distributions on the state space. We have |G k | = O(m k ). Moreover, by [Althöfer, 1994] , for k ε = log(2n) 2ε 2, we have:∀µ ∈ ∆(Ω), ∃µ ∈ G kε , s.t. ∀a ∈ A, |s(µ, a) -s(µ, a)| ≤ ε.Accordingly, we define the ε-cell around µ ∈ G k to beC µ ε = {µ ∈ ∆(Ω) : ∀a ∈ A, |s(µ, a) -s(µ, a)| ≤ ε} .Note that given ε and µ, µ ∈ C µ ε is equivalent to a set of 2n linear constraints on µ. We consider the following signal space:Σ = (µ, ã, a) | µ ∈ G k ε ′ , ã, ȧ ∈ A ,whereEQUATIONDefine LP variables φ(ω, µ, ã, ȧ) for each ω ∈ Ω and each signal (µ, ã, ȧ) ∈ Σ to represent the conditional probabilities of sending that signal. Each signal σ = (µ, ã, ȧ) is specified by the kuniform distribution µ that centers the cell, the best response action ã, and the action ȧ in δ-BR set that minimizes the sender's strategy. The LP is defined in Fig. 3 .maximize φ,x ω∈Ω µ 0 (ω) (µ,ã, ȧ)∈ Σ φ(ω, µ, ã, ȧ)s(ω, ȧ) subject to ω∈Ω µ 0 (ω)φ(ω, µ, ã, ȧ) • (s(ω, a) -s(µ, a) + ε ′ ) ≥ 0 (∀a ∈ A, ∀(µ, ã, ȧ) ∈ Σ) ω∈Ω µ 0 (ω)φ(ω, µ, ã, ȧ) • (s(ω, a) -s(µ, a) -ε ′ ) ≤ 0 (∀a ∈ A, ∀(µ, ã, ȧ) ∈ Σ) ω∈Ω µ 0 (ω)φ(ω, µ, ã, ȧ) (r(ω, ã) -r(ω, a)) ≥ 0, (∀a ∈ A, ∀(µ, ã, ȧ) ∈ Σ) ω∈Ω µ 0 (ω)φ(ω, µ, ã, ȧ) (r(ω, ã) -r(ω, a) -δ) ≥ 0, (∀a s.t. s(µ, a) < s(µ, ȧ) -2ε ′ ) (∀(µ, ã, ȧ) ∈ Σ) (µ,ã, ȧ)∈ Σ φ(ω, µ, ã, ȧ) = 1 (∀ω ∈ Ω) φ(ω, µ, ã, ȧ) ≥ 0. (∀ω ∈ Ω, ∀(µ, ã, ȧ) ∈ Σ)Figure 3 : QPTAS for computing an ε-approximate robust signaling scheme, where ε ′ = ε 5 .Intuitively, the first two constraints in Fig. 3 are designed to ensure µ (µ,ã, ȧ) ∈ C µ ε . The third and fourth constraints describe the semantics of the receiver's response strategy. Finally, the last two constraints guarantee that φ represents a valid signal distribution on each state. We summarize the guarantee of the QPTAS in Theorem 5.2 and formally prove it in appendix F. Theorem 5.2. For any ε > 0 and δ > 0, the optimal solution to the LP in Fig. 3 is an ε-approximate δ-robust signaling scheme that is supported on O n 2 m ⌈12.5 log(2n)/(ε 2 )⌉ signals. Bayesian persuasion. Our paper generalizes the canonical model of Bayesian persuasion for information design that was introduced by the seminal work of Aumann et al. [1995] , Kamenica and Gentzkow [2011] , Brocas 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 et al., 2015, Bergemann and Pesendorfer, 2007] , incentivizing exploration [Mansour et al., 2020 , 2022 , Kremer et al., 2014] , to name a 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 [2016] , Dughmi [2017] that study the algorithmic complexity of the sender's optimization tasks in several natural input models. In the multi-receiver settings, computational challenges are more pronounced, as demonstrated by Dughmi [2014] , Bhaskar et al. [2016] who showed the hardness of computing the optimal signaling scheme in Bayesian zero-sum games. In addition, Rubinstein [2017] established the hardness of finding even an approximate solution, revealing that obtaining an ϵ-approximate signaling scheme in two-player zero-sum games requires quasi-polynomial time. On the positive side, Babichenko 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 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 to 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 a two-layer model where the first layer accounts for arbitrary exogenous information receivers may have, including pessimistic scenarios where receivers fully learn the state from exogenous information. The optimization at the second layer assumes a common prior but is constrained to policies that secure the sender's maximin payoff at the first layer. Kosterina [2022] considers a setting where the sender does know the receiver's prior belief and assumes that the receiver's prior can be any distribution that assigns at least a fixed state-dependent probability to each state. Hu and Weng [2021] consider a model where starting from a common prior, the receiver gets a private signal resulting in an arbitrary random belief supported on a 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 of robustness vanishes as the size of the neighborhood vanishes. Babichenko et al. [2022] study a 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 a constant additive gap between the maximin strategy and the omniscient one. Chen and Lin [2023] consider a model similar to ours with ε-best responding receivers. They present a continuity result that bounds the cost of robustness by O(ε).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] study 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 a set of approximate best responses.Comparison with [Gan et al., 2023] . Another closely related work is that of Gan et al. [2023] which studies the computational complexity of robust Stackelberg equilibria under approximate best responses. While Stackelberg games provide a more general model for principal-agent interactions, the computational complexity results in [Gan et al., 2023] are not directly applicable to Bayesian persuasion due to 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 it 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 to the simplex of probability distributions over the principal's action set. In contrast, in Bayesian persuasion, the search space for signaling schemes is not pre-defined as 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(n O(m) ) when the state space size m is small. In comparison, approaches in Gan et al. [2023] result in a complexity exponential in n.In classical Bayesian persuasion problem where receivers always best respond, an argument via the revelation principle (see, e.g., [Kamenica and Gentzkow, 2011, Proposition 1] ) 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 2 actions where direct revelation schemes fail to match the optimal utility with any nontrivial approximation factor.There exists a sequence of Bayesian persuasion instances with a robustness level δ = Θ(1), such that the following holds in the limit: any direct-revelation scheme φ is suboptimal, at least by a factor of 2 or an additive gap of 1 2 . That is, for any direct-revelation scheme φ,S δ (φ) ≤ 1 2 S ⋆ δ , and S δ (φ) ≤ S ⋆ δ - 1 2 .The claim in Proposition B.1 can be established using the family of robust persuasion instances constructed in Example B.2. The main idea is to create a relatively large robustness level so that disadvantageous actions enter the receiver's approximate best response set as long as the posterior is a mixed distribution. Therefore, to achieve the optimal robust utility, the sender has to adopt a signaling scheme that deterministically discloses the true state, which requires a signaling space larger than the action space. Example B.2. Consider the following family of robust Bayesian persuasion instances parametrized by ε. Every instance in this family has state space Ω = {ω ⊥ , ω 0 , ω 1 } and action space A = {a 0 , a 1 }.The prior distribution µ 0 puts a very small probability mass on state ω ⊥ , and divides the rest of the probability mass evenly between ω 1 and ω 2 . Formally, for an infinitesimal ε > 0, we haveµ 0 (ω ⊥ ) = ε, µ 0 (ω 0 ) = µ 0 (ω 1 ) = 1 -ε 2 .The utility functions satisfy r = s, where both the receiver obtains utility 1 if the index of the action matches that of the state (i.e., in the case of (ω 1 , a 1 ) and (ω 0 , a 0 )) and 0 otherwise (see Table 1 ).The approximate best response level is δ = 1.states (Ω) actions (A) a 0 a 1 ω ⊥ 0 0 ω 0 1 0 ω 1 0 1 Table 1:The utility function for both the sender and the receiver. If the state is ω ⊥ , then both players have 0 utility. Otherwise, both players get utility 1 if and only if the receiver's action matches the true state.Proof of Proposition B.1. In example B.2, the optimal robust utility S ⋆ δ is at least 1 -ε, which can be achieved by a full-revelation signaling scheme φ ⋆ supported on 3 signals. More specifically, φ ⋆ is a deterministic mapping from Ω to a ternary signal space Σ = {σ ⊥ , σ 0 , σ 1 }, such that φ(ω i ) ≡ σ i for i ∈ {⊥, 0, 1}. Since this signaling scheme is deterministic, we have φ ⋆ (σ i ) = µ 0 (ω i ), and each posterior distribution µ σi is the degenerate distribution on ω i . They lead to the following approximate best response sets:BR δ (µ σ ⊥ ) = {a 0 , a 1 }, BR δ (µ σ0 ) = {a 0 }, BR δ (µ σ1 ) = {a 1 }.Therefore, the sender's robust utility is given byS δ (φ ⋆ ) = σ∈Σ φ ⋆ (σ) • min a∈BR δ (µσ) s(µ σ , a) =µ 0 (ω ⊥ ) • s(µ σ ⊥ , a 0 ) + µ 0 (ω 0 ) • s(µ σ0 , a 0 ) + µ 0 (ω 1 ) • s(µ σ1 , a 1 ) =ε • 0 + 1 -ε 2 • 1 + 1 -ε 2 • 1 = 1 -ε.On the other hand, we claim that any signaling scheme φ : Ω → Σ with |Σ| = 2 has to suffer a suboptimal utility of S δ (φ) ≤ 1-ε 2 . To see this, note that if a posterior distribution µ σ of a signal σ ∈ Σ is supported on more than one state, then the receiver's utility of the optimal action is at most max{µ σ (ω 0 ), µ σ (ω 1 )} < 1, which is smaller than the robustness level δ = 1. Therefore, any posterior µ σ that is a mixed distribution must have BR δ (µ σ ) = {a 0 , a 1 }, which impliesmin a∈BR δ (µσ) s(µ σ , a) = min {s(µ σ , a 0 ), s(µ σ , a 1 )} = min {µ σ (ω 0 ), µ σ (ω 1 )} .Let us denote the two signals in Σ as σ 0 and σ 1 . At least one of the posterior distributions µ σ0 and µ σ1 has to be supported on ≥ 2 states because |Ω| = 3. We have two following cases:• Case 1. Both signals have mixed posteriors. In this case, we haveS δ (φ) = σ∈Σ φ(σ) • min a∈BR δ (µσ) s(µ σ , a) =φ(σ 0 ) • min {µ σ0 (ω 0 ), µ σ0 (ω 1 )} + φ(σ 1 ) • min {µ σ1 (ω 0 ), µ σ1 (ω 1 )} ≤φ(σ 0 ) • µ σ0 (ω 0 ) + φ(σ 1 ) • µ σ1 (ω 0 ) =µ 0 (ω 0 ) • φ(ω 0 , σ 0 ) + µ 0 (ω 0 ) • φ(ω 0 , σ 1 ) = µ 0 (ω 0 ) = 1 -ε 2 ,where the last few steps follow from the Bayes' rule.• Case 2. Only one signal has a mixed posterior. WLOG, assume µ σ0 is a mixed distribution whereas µ σ1 is a pure (degenerate) distribution. It is also WLOG to assume that µ σ1 is a degenerate distribution on ω 1 , because ω 0 and ω 1 are symmetric and ω ⊥ has 0 utility under both actions. Therefore, we have that σ 1 is only sent on state ω 1 , and φ(σ 1 ) = µ 0 (ω 1 ). As for the robust utility, we haveS δ (φ) = σ∈Σ φ(σ) • min a∈BR δ (µσ) s(µ σ , a) =φ(σ 0 ) • min {µ σ0 (ω 0 ), µ σ0 (ω 1 )} + φ(σ 1 ) • s(ω σ1 , a 1 ) =φ(σ 0 ) • 0 + φ(σ 1 ) • 1 =µ 0 (ω 1 ) = 1 -ε 2 ,where the second-to-last step follows from µ σ0 (ω 1 ) = 0 because σ 1 is only sent on state ω 1 .Combining the two cases above, we arrive at the conclusion that any scheme with two signals has robust utility at most 1-ε 2 , which is half of the optimal robust utility S ⋆ δ . In addition, we note that S ⋆ δ -S δ (φ) = 1-ε 2 and the above analysis holds for any ε > 0. Therefore, sending ε → 0 proves the 1 2 additive gap.Proof of Lemma 3.2. Let Σ ′ = {(A, ã) | A ⊆ A, ã ∈ A}. Given any signaling scheme φ : Ω → Σ, we use Σ (A,ã) to denote the subset of signals σ ∈ Σ that lead to the same best response a ⋆ = ã and the same δ-BR set BR δ (µ σ ) = A, i.e.,Σ (A,ã) = {σ ∈ Σ | σ ∈ Σ : a ⋆ (µ σ ) = ã, BR δ (µ σ ) = A}.Consider an alternative signaling scheme φ ′ : Ω → Σ ′ that merges signals in each subset Σ (A,ã) :∀(A, ã) ∈ Σ ′ , φ ′ (ω, (A, ã)) = σ∈Σ (A,ã) φ(ω, σ).The subsets Σ (A,ã) naturally form a partition of the original signal space Σ.We first claim that a ⋆ (µ(A,ã) ) = ã, BR δ (µ (A,ã) ) = A.The first claim follows directly from the revelation principle -since ã is the best response to each σ ∈ Σ (A,ã) , it must also be 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 φ ′ satisfiesEQUATIONtherefore, for each a ∈ A, we haver(µ (A,ã) , a) = σ∈Σ (A,ã) φ(σ)r(µ σ , a) σ∈Σ (A,ã) φ(σ) > σ∈Σ (A,ã) φ(σ)(r(µ σ , ã) -δ) σ∈Σ (A,ã) φ(σ) = r(µ (A,ã) , ã) -δ.Similarly, for each a ∈ A \ A, we can conclude thatr(µ (A,ã) , a) ≤ r(µ (A,ã) , ã) -δ, If ∆ (A1,ã1) , ∆ (A2,ã2) are adjacent, they must share a common face, which belongs to a hyperplane in H. Consider the following two cases:Case 1. If the hyperplane is ω∈Ω µ(ω)(r(ω, a) -r(ω, a ′ )) = 0 for some pair of actions (a, a ′ ).According to the semantics in eq. ( 3) that defines each polytope, it must be the case that a, a ′ each corresponds to an action in ã1 , ã2 . WLOG assume a = ã1 and a ′ = ã2 . Therefore, to show that{(A 1 , ã1 ), (A 2 , ã2 )} ∈ E, it suffices to establish A 1 = A 2 .Consider two posteriors µ 1 ∈ ∆ (A1,ã1) and µ 2 ∈ ∆ (A2,ã2) such that ∥µ 1 -µ 2 ∥ 1 ≤ ε for an infinitesimal ε > 0, and both µ 1 , µ 2 have a distance of at least ε 0 from all other hyperplanes in H. Such a choice implies• ∀a ∈ A, |r(µ 1 , a) -r(µ 2 , a)| ≤ ∥µ 1 -µ 2 ∥ 1 = ε. • r(µ 1 , ã1 ) -min a∈A1 r(µ 1 , a) ≤ δ -ε 0 , and r(µ 2 , ã2 ) -min a∈A2 r(µ 2 , a) ≤ δ -ε 0 .Consider the process of fixing ε 0 and sending ε → 0. For any a ∈ A 1 = BR δ (µ 1 ), we haver(µ 2 , a) ≥ r(µ 1 , a) -ε ≥ r(µ 1 , ã1 ) -(δ -ε 0 ) -ε ≥ r(µ 2 , ã1 ) -δ + ε 0 -2ε > r(µ 2 , ã1 ) -δ, which implies a ∈ BR δ (µ 2 ) = A 2 and therefore A 1 ⊆ A 2 .In addition, a symmetric argument implies that A 2 ⊆ A 1 . Therefore, it must be the case thatA 1 = A 2 .Case 2. If the hyperplane is ω∈Ω µ(ω)(r(ω, a) -r(ω, a ′ )) = δ for some pair of actions (a, a ′ ).Once again, we can find two posteriors µ 1 ∈ ∆ (A1,ã1) and µ 2 ∈ ∆ (A2,ã2) such that ∥µ 1 -µ 2 ∥ 1 ≤ ε for an infinitesimal ε > 0, and both µ 1 , µ 2 have a distance of at least ε 0 from all other hyperplanes in H. This immediately implies ã1 = ã2 because otherwise the hyperplane ω∈Ω µ(ω)(r(ω, a 1 )r(ω, a 2 )) = 0 will have to separate µ 1 and µ 2 . A similar continuity argument to that in the previous case shows that a 1 = a 2 = a and(A 1 \ A 2 ) ∪ (A 2 \ A 1 ) = {a ′ }.Therefore, in both cases we can conclude that {(A 1 , ã1 ), (A 2 , ã2 )} ∈ E. This finishes the proof of Lemma 4.4.Proof. The first bound follows from |Σ † | ≤ |Σ| ≤ n2 n-1 . For the second bound, consider the following set of hyperplanes defined by every pair of receiver's actions:H = a,a ′ ∈A ω∈Ω µ(ω)(r(ω, a) -r(ω, a ′ )) = 0, ω∈Ω µ(ω)(r(ω, a) -r(ω, a ′ )) = δ They cut the (m -1)-dimensional simplex into at most |H| ≤ m ≤ 2n 2 ≤ m ≤ n O(m)cells [Halperin and Sharir, 2017, Theorem 28.1.1] . Since the boundaries of each open polytope ∆ (A,ã) are defined by a subset of hyperplanes in H with either strict or non-strict inequalities, 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 of Theorem 5.1Proof. For any given δ ∈ (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 δ-robust sender utility in Bayesian persuasion against approximate responses. This reduction maps instances of the Subset Sum problem to instances of δ-robust Bayesian persuasion such that an instance of the Subset Sum problem has a solution (a YES instance) if and only if the corresponding δ-robust persuasion instance yields an optimal utility of at least 1 2 . We start by introducing the format of a subset sum instance. A subset sum instance is given by a setX = {x 1 , • • • , x n } of integers where sum(X) = n i=1 x i = 0. The problem is to decide whether maximize ε,µ ε subject to ω∈Ω µ(ω) (r(ω, ã) -r(ω, a)) ≥ 0, ∀a ∈ A ω∈Ω µ(ω) (r(ω, ã) -r(ω, a)) ≤ δ -ε, ∀a ∈ A ω∈Ω µ(ω) (r(ω, ã) -r(ω, a ′ )) ≥ δ, ∀a ′ ∈ A \ A ω∈Ω µ(ω) = 1 µ(ω) ≥ 0 ∀ω ∈ Ω.Figure 4 : LP for checking the feasibility of (A, ã) ∈ Σ. The tuple is feasible if and only if ε ⋆ > 0.or not there exists a subset of indices J ⊂ [n] such that |J| = n 2 and sum(X J ) = j∈J x j = 0. If there exists such a J, then X is a YES instance. Otherwise, it is a 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| = n 2 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 a subset of size n 2 that sums to 0 iff we have a YES instance. We construct a robust persuasion instance as follows.States and prior distribution The state space is defined as Ω = {ω 1 , • • • , ω n } with |Ω| = |X| = n,We define the sender's utility s and receiver's utility r as follows. For ease of presentation, the range of the receiver's utility is designed to be [0, 2], but it is not hard to rescale it to [0, 1] to fit our modeling assumptions.• For a malicious guess a i ∈ A and any i ∈ [n], the utility functions are defined asEQUATIONAt a high level, malicious guesses result in a constant 0 utility on the sender, but the penalty of incorrect guesses on the receiver's side is relatively minor -on top of the base utility of 1, the receiver only suffers a utility loss of δ 1-2 n (when δ < 1 -2 n ) for an incorrect state guess, which implies that the receiver secures a utility of ≥ 1 -δ as long as the guess is correct with a probability at least 2 n . This choice of utility function guarantees that to obtain nontrivial utilities, the sender must prevent the receiver from adopting malicious guesses by creating enough dispersion in the posterior distributions. In particular, the posterior probability on any state should not exceed 2 n . • For benign guess b i ∈ B for any i ∈ [n], the utility functions are defined asEQUATION)At a high level, benign guesses, if 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 ω i is in the support of the receiver's posterior, the excepted utility of the receiver will exceed 1 -δ and the corresponding benign guessing action b i enters the δ-BR set. For the sender, the expected utility under malicious guess b i reaches 1 2 only when the posterior probability on ω i is at least 2 n . 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 asEQUATIONwhere M = x∈X |x| > 0. In this case, the receiver gains utility when her chosen action matches the sign of the expected value of x i under the posterior distribution, whereas the sender loses a proportional amount of utility. Specifically, when the posterior is uniform on a subspace of size n 2 -a design choice that is encouraged by the first two categories of actions -the receiver chooses sign-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 < 1 2 unless the subset sum equals zero. Now, we formally show the reduction from the subset sum problem to δ-robust optimal signaling scheme by dividing the proof into two claims.Claim E.1. If X is a YES instance, then S ⋆ δ = S δ (φ ⋆ ) ≥ 1 2 .Proof of Claim E.1. For notation convenience, for any subset of indices J ⊆ [n] and any set Ω s.t. the elements of Ω are indexed by [n], we use X J to denote the subset of elements with indices in J, i.e., X J = {ω j | j ∈ J}. Let J ⊂ [n] such that |J| = n 2 and sum(X J ) = j∈J x j = 0. Consider the following signaling scheme:φ ⋆ (ω i , σ + ) = 1 [i ∈ J] , φ ⋆ (ω i , σ -) = 1 [i ∈ ([n] \ J)].Since the signaling scheme is deterministic, we have µ σ+ = Unif(Ω J ) and µ σ-= Unif(Ω [n]\J ).To compute the robust utility of φ ⋆ , we first compute the δ-BR set BR δ (µ σ+ ). For the sign-matching actions c ∈ C, we haver(µ σ+ , c) = 1 ± δ 4M • 2 n j∈J x j = 1.because the subset X J is of sum 0. For malicious guesses a i ∈ A, note that µ σ+ (ω j ) ≤ 2/n for any ω j ∈ Ω, thus we haver(µ σ+ , a i ) ≤ 2 n + 1 - 2 n • 1 - δ 1 -2 n = 1 -δ.i ∈ B, we have r(µ σ+ , b i ) = 1 • µ σ+ (ω i ) + (1 -δ)(1 -µ σ+ (ω i )) = 1 -δ(1 -µ σ+ (ω i )), which implies that r(µ σ+ , b i ) > 1 -δ if and only if µ σ+ (ω i ) > 0. Therefore, we have BR δ (µ σ+ ) = B J ∪ C.As for the sender's robust utility, we haves(µ σ+ , b i ) =1 • 2 n + 1 - 2 n • 1 2 -2 n 1 -2 n = 1 2 , ∀b i ∈ B J ; s(µ σ+ , c) = 1 2 ∓ δ 4M • 2 n j∈J x j = 1 2 ∓ δ 4M • 2 n sum(X J ) = 1 2 , ∀c ∈ C.Therefore, we have min a∈BR δ (σ+) s(µ σ+ , a) = 1 2 . A similar analysis show that BR δ (µ σ-) = B [n]\J ∪ C and min a∈BR δ (σ-) s(µ σ-, a) = 1 2 . Therefore,S ⋆ δ ≥ S δ (φ ⋆ ) = φ ⋆ (σ + ) min a∈BR δ (σ+) s(µ σ+ , a) + φ ⋆ (σ -) min a∈BR δ (σ-) s(µ σ-, a) = 1 2 .Claim E.2. If the optimal sender's utility satisfies S ⋆ δ ≥ 1 2 , then X must be a YES instance.= S(φ ⋆ ) -ε ′ = S ⋆ δ -ε ′ .We proceed to prove the second part of the theorem, namely the signaling scheme φ induced by optimal LP solution φ ⋆ satisfies S δ ( φ) ≥ OPT -4ε ′ . The key step to establishing this claim is to show that, ∀(µ, ã, ȧ) ∈ Σ, the sender's utility under the worst-case δ-BR strategy ρ δ ((µ, ã, ȧ)) is not much worse than that under action ȧ. We establish this using proof by contradiction. Suppose an action a = ρ δ ((µ, ã, ȧ)) ∈ BR δ (µ µ,ã, ȧ) satisfies s(µ (µ,ã, ȧ) , a) < s(µ (µ,ã, ȧ) , ȧ) -4ε ′ , then we should have s(µ, a) < s(µ, a) -2ε ′ because the first and second constraints of the LP in Fig. 3 ensuress(µ, a) ≤ s(µ (µ,ã, ȧ) , a) + ε ′ < s(µ (µ,ã, ȧ) , ȧ) -3ε ′ ≤ s(µ, ȧ) -2ε ′ .However, from the fourth constraint, in the case of s(µ, a) < s(µ, a) -2ε ′ , we haveω∈Ω µ 0 (ω)φ(ω, µ, ã, ȧ) (r(ω, ã) -r(ω, a) -δ) ≥ 0 ⇐⇒ r(µ (µ,ã, ȧ) , a) ≤ r(µ (µ,ã, ȧ) , ȧ) -δ,which contradicts the assumption of a ∈ BR δ (µ (µ,ã, ȧ) ). Therefore, we must haveEQUATIONFinally, for the sender's robust utility, we haveS δ ( φ) = ω∈Ω µ 0 (ω) (µ,ã, ȧ)∈ Σ φ(ω, µ, ã, ȧ) • s(ω, ρ δ ((µ, ã, ȧ))) = (µ,ã, ȧ)∈ Σ φ((µ, ã, ȧ)) • s(µ (µ,ã, ȧ) , ρ δ ((µ, ã, ȧ))) (Bayes' rule) ≥ (µ,ã, ȧ)∈ Σ φ((µ, ã, ȧ)) • s(µ (µ,ã, ȧ) , ȧ) -4ε ′ (From Equation (13)) = ω∈Ω µ 0 (ω) (µ,ã, ȧ)∈ Σ φ(ω, µ, ã, ȧ) • s(ω, ȧ) -4ε ′ (Bayes' rule) =OPT -4ε ′ .NeurIPS Paper Checklist 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 in 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 on 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
 
 Appendix:  


Decision: 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].

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.

- 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.

- 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.

- Finally, the knowledge of $\delta>0$ limits the contribution of the work.

[1] Castiglioni, M., Celli, A., Marchesi, A., and Gatti, N. Online bayesian persuasion. Advances in Neural Information Processing Systems, 33, 2020.

[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.
questions: questions: - Is the approach discussed above with small state spaces a possible approach?
- Is your approach employable for a multi-type receiver?
limitations: limitations: NA
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

[1] Jiarui Gan, Minbiao Han, Jibang Wu, and Haifeng Xu. Generalized Principal-Agency: Contracts, Information, Games and Beyond.
questions: questions: Please address my concern in the weakness section.
limitations: limitations: n/a
paper_summary: paper_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:

(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.

(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$.

(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.

(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.
strength_weakness: strength_weakness: I don't see significant weaknesses.

I 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).
questions: questions: (Q1) What is the running time of the QPTAS you design for the general case (Theorem F.1)?
limitations: limitations: **Suggestions:**

(1) Typo: The equation between Lines 192 and 193: "$r(\mu_\sigma, a)$".

(2) Typo: the $s$ in Definition 2.1 should be $\sigma$.

(3) Typo: In Remark 2.2, the phrase "that achieves sender's objective" is confusing and can be deleted.

(4) It is better to explicitly write $\sigma = (A, \tilde a)$ in the first contraint of the optimization problem in the Figure 1.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: see weaknesses
limitations: limitations: yes

Comments: title: I think this paper has enough technique contribution to the literature
comment: Thank you for your response. We would like to highlight the difference in the search space between the Stackelberg game and the Bayesian persuasion problem (although both are infinite). In Stackelberg games, the search space is constrained to the simplex of probability distributions over the principal's action set. In contrast, in Bayesian persuasion, the search space of signaling schemes is not pre-defined because one needs to define the signal space first, where designing signal space is also an important part of the problem. We also appreciate the reviewer's acknowledgment of our result with small state/action spaces, and we will include a more detailed discussion in revised versions of the paper.
Thanks for your support of our paper! We'll add a more detailed discussion of our technical contributions and highlight our results in the small state space setting in revisions of the paper.
Thank you for your response.

Lemma 3.2 is a generalization of the revelation principle to the approximate best response setting. The key distinction between this lemma and the result (Proposition 1) of Gan et al is that, in Stackelberg games, the search space (probability simplex of principal’s strategies) can be directly partitioned into sub-regions in terms of eps-best response sets, whereas in the Bayesian persuasion problem, there is no pre-defined search space since the signal space needs to be defined first. In terms of techniques, to prove that this signal space suffices, our approach requires an iterative proof that begins with any signal space and merges signals without reducing robust utility. This step is unnecessary in the robust Stackelberg games setting.

We also want to emphasize that the fact that the impracticality of considering this many signals is exactly the motivation for our results with a small state space. We show that one can greatly reduce the number of signals to $n^{O(m)}$ by leveraging the structural insights of how delta response regions correspond to polytopes cut by polynomially many hyperplanes in a low-dimensional space. We further abstract the connectivity of those polytopes into a symmetric different graph, on which we then apply graph algorithms to efficiently search for the $n^{O(m)}$ number of useful signals. In contrast, the $2^n\cdot poly(m,n)$ complexity of Gan et. al’s algorithm does not benefit from this speed-up because the above structure is unique to the Bayesian persuasion setting.
I have read the rebuttal as well as other reviews. While I appreciated the detailed comparison to the work by Gan et al. missing in the paper, I am still not convinced that the contribution from this paper is significant enough over Gan et al.. For example, I am not sure whether Lemma 3.2 should be viewed as a positive result (unique to this paper). To me this is an easy result based out of Gan et al.., where the number of \delta-best response regions in robust Stackelberg game is exactly the number of the signals to consider in the robust Bayesian persuasion. I do not think this observation is conceptually new. It is also somewhat unrealistic to consider this many signals in the persuasion problem. The hardness results are also expected (despite a deduction to different hard problems), because function concavification (in bayesian persuasion) is at least as hard as function maximization. In summary, I believe the paper needs to be further improved by explicitly exploring the connections and differences between Stackelberg game and bayesian persuasion problem.
I thank the authors for their responses. After carefully reading all the reviews and rebuttals, I still believe that the paper presents several technical similarities to the one by Gan et al. (2023). This is somewhat expected, given that the two settings share many similarities, but it certainly limits the contribution of the work. For this reason, I will keep my score unchanged.
I am happy with the authors' response and keep my rating of 7.  Below, I'd like to discuss my support for this paper. 

I read other reviews.  A common issue raised by other reviewers is the similarity to [Gan et al (2023), Robust Stackelberg Equilibria].  I am convinced by the authors' response to reviewer zPak that their work is significantly different from [Gan et al (2023)].  Although Bayesian persuasion and Stackelberg games are similar at a high level (they both belong to a class of Generalized Principal-Agent Problem as pointed out by reviewer FR8F), they require different techniques.  For example, in Stackelberg games, the leader only needs to choose one mixed strategy (and this mixed strategy is unconstrained), while in Bayesian persuasion, the sender needs to choose a distribution over posteriors (subject to the constraint that the average of posteriors is equal to the prior) and the support of this distribution might be infinite.  These two scenarios are significantly different just as unconstrained and constrained convex optimization problems are significantly different. The authors also mentioned other differences with [Gan et al, 2023] in their rebuttal.  Although some of the authors' techniques for robust Bayesian persuasion are inspired by [Gan et al (2023)]'s techniques for robust Stackelberg games, the latter does not apply directly to Bayesian persuasion, as the authors argue in their rebuttal.  So, I think this work has enough technical contribution to the literature, although the authors didn't discuss their contributions clearly in their submitted draft.

Another contribution of this work that was not emphasized enough by the authors, in my opinion, is that: in the small-state-space case ($m$ is small), the authors obtain a $poly(n^{O(m)})$ algorithm to find the optimal robust signaling scheme, where $n$ is the number of actions of the receiver.  But by following [Gan et al 2023]'s approach, one can only get a $poly(2^n, n, m)$ exponential-time algorithm because the algorithm needs to enumerate all the $2^n$ subsets of the $n$ actions to check whether they can be induced as a set of $\delta$-best-responding actions.  The authors observe that the number of such feasible subsets cannot be more than $n^{O(m)}$ and design an efficient algorithm (Algorithm 1) to find all of them without enumerating all $2^n$ subsets.  This observation is interesting, and it is a significant improvement over [Gan et al 2023] and a good contribution to the literature.
I'm not convinced by the authors response about the intrinsic differences between their work and the robust Stakelberg paper. For example the fact that you have to deal in principle with infinite strategies is obviously also true for Stakelberg games, and also in Stakelberg games many of those can be grouped (as your second bullet point).
However I agree that the poly-time algorithms with constant number of actions or states are interesting and should be given more space.
That said I cannot increase my score that was already somewhat on the positive side