Computational Aspects of Bayesian Persuasion under Approximate Best Response

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.

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.

Questions

see weaknesses

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

yes

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.

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. (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. (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. (4) [Quality] Discussion of related works, especially Appendix A, is comprehensive and clear. (5) [Clarity] Writing is clear. The introduction nicely summarizes the technical contributions and high-level ideas.

Weaknesses

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

(Q1) What is the running time of the QPTAS you design for the general case (Theorem F.1)?

Rating

7

Confidence

4

Soundness

3

Presentation

4

Contribution

3

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.

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.

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. [1] Jiarui Gan, Minbiao Han, Jibang Wu, and Haifeng Xu. Generalized Principal-Agency: Contracts, Information, Games and Beyond.

Questions

Please address my concern in the weakness section.

Rating

3

Confidence

5

Soundness

3

Presentation

2

Contribution

1

Limitations

n/a

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.

Strengths

- The paper studies an interesting problem for the Bayesian persuasion community. - 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. - 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

- Is the approach discussed above with small state spaces a possible approach? - Is your approach employable for a multi-type receiver?

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

2

Limitations

NA

I think this paper has enough technique contribution to the literature

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.