Computational Aspects of Bayesian Persuasion under Approximate Best Response

Thank you for your thoughtful comments.

Need for a new reduction: the fundamental reason that the two problems are not necessarily "comparably hard" is that the computational complexity depends crucially on (1) the representation and (2) additional special structure. It is certainly true that the Bayesian persuasion problem can be viewed as a Stackelberg game, but:

• The flat representation of the Stackelberg game corresponding to a Bayesian persuasion instance has a huge strategy space. In particular, each candidate strategy of the sender is a (randomized) mapping from states to signals. This means the sender's strategy space is at least exponentially larger even in the classical setting where the revelation principle holds. As a result, a polynomial-time algorithm under the Stackelberg game representation might very well be an exponential-time algorithm under the Bayesian persuasion representation. This in particular means the Bayesian persuasion version might not be easier than the Stackelberg game version.
• On the other hand, Bayesian persuasion is a special class of Stackelberg games, which means it might exhibit additional structure that makes the computational problem much easier despite the difference in representations. This in particular means the Bayesian persuasion version might not be harder than the Stackelberg game version. Indeed, our proof of hardness directly reduces from Subset Sum.

Comparison with Gan et al.: below we provide a detailed comparison to the work by Gan et al. We will focus on concrete differences, which are easier to describe and verify. We will also include a shortened version in the main paper (if there's space), as well as the full comparison in an appendix.

• Model: allowing the "agent" / "follower" / "receiver" to choose a response that is suboptimal by a given amount is a standard approach in algorithmic game theory when robustness is desired. Both our work and that of Gan et al. take this approach. However, the first major difference (both conceptual and technical) already shows in the respective models: the succinct representation of a Bayesian persuasion instance has the additional component of states. This in particular means the sender's strategy is a randomized mapping from states to posterior beliefs, which is, superficially speaking, of much higher dimensions than a Stackelberg equilibrium. In fact, since the classical revelation principle is no longer valid, one may suspect the former strategy space is infinite-dimensional (we show this is not the case). As we argue below, this has significant technical implications to the computation of an (almost) optimal strategy.

• Structure of optimal strategies: our positive results rely crucially on a structural property of optimal strategies that we prove (Lemma 3.2), which doesn't have a counterpart in robust Stackelberg games. The property says that while there are infinitely many possible signals, restricted to optimal strategies, many of them can be grouped, and we only need to consider a finite number of representative signals. This in particular means the effective strategy space of the sender is finite-dimensional. Note that here, the receiver may choose different actions depending on the signal sent. In contrast, the leader's strategy space in a robust Stackelberg game is naturally finite dimensional, and the follower always chooses a fixed action in response to the leader's strategy.

• Algorithm for fixed number of actions: our algorithm when the number of actions is fixed (Proposition 3.3) is a natural combination of the classical LP for Bayesian persuasion and the above structural property. In particular, we solve a single LP for the sender's optimal strategy. For comparison, the fixed-$n$ algorithm by Gan et al. generalizes the algorithm by Conitzer and Sandholm ("Computing the Optimal Strategy to Commit to"), which enumerates the follower's response and solves one LP for each possibility.

• Algorithm for fixed number of states: here we deviate significantly from existing techniques. In particular, our algorithm relies crucially on the notion of symmetric difference graphs and connectivity therein. To our knowledge, such techniques have not been employed in the context of Bayesian persuasion or Stackelberg games. In contrast, there are no states in Stackelberg games to begin with. Note that the parameter $m$ in Stackelberg games plays an intrinsically different role than the number of states in our model, and Gan et al. present no efficient algorithm when $m$ is fixed (though the comparison itself may not be meaningful in the first place).

• Hardness result: first we note that it's not uncommon for a well-motivated problem to be computationally hard, and the fact that both our problem and Gan et al.'s are hard doesn't necessarily mean the two are otherwise similar (also see our response to the first question above). Our hardness result is based on a fundamentally different reduction from Gan et al.'s. In particular, we reduce from the problem of Subset Sum, whereas Gan et al. reduce from Exact Cover by 3-Sets. Details of the two reductions bear virtually no similarity.

• Approximation algorithm: our algorithm shares the same high-level idea with Gan et al.'s (as well as many other approximation algorithms involving the probability simplex): one first discretizes the probability simplex into a reasonable number of representative points, and then considers the problem restricted to these points. Despite this high-level similarity, the concrete algorithms are sufficiently different. Specifically, the two algorithms are based on their exact (and inefficient) versions respectively, which means our algorithm solves a single LP, and Gan et al.'s enumerates the follower's response and solves one LP for each possibility. Our algorithm also has to deal with additional challenges introduced by the states and the prior distribution.

Thank you for your detailed and insightful comments.

Suggestions: Thank you for the helpful suggestions, we will revise our paper accordingly.

Running time of the QPTAS: the running time generally depends on the specific algorithm chosen to solve the LP given in Theorem F.1. Algorithms for LP are quickly evolving, but we can apply their result as a black box to obtain running time guarantees in our problem. From a quick search, the state-of-the-art algorithm (or something close enough) for general LP seems to run in time $\tilde{O}(n^{2 + 1/18}L)$, where $n$ is the total number of variables and constraints, and $L$ is the number of bits required to encode input numbers. Combining this with the bound on the size of the LP in Theorem F.1, we get a running time of $\tilde{O}(n^4 m^{25\log(2n) / \varepsilon^2} L)$. It might be possible to apply special-purpose LP algorithms that exploit the structure of our LP formulation to get a better running time. In any case, the running time is polynomial in $n$, $m^{\log n / \varepsilon}$, and $L$ (the number of bits required to encode input numbers).

Thank you for your comments.

We respectfully disagree with the view that our paper is "almost a copy-paste" of the work by Gan et al., and that the results are "identical". While we recognize the high-level similarities between Stackelberg games and Bayesian persuasion, we believe that the community continues to find independent interest in each of these problems. In particular:

High-level differences between Stackelberg games and Bayesian persuasion: one could certainly argue that Bayesian persuasion instances are a particular class of Stackelberg games -- in fact, one could make similar arguments about other important fields of algorithmic game theory / economics, such as dominant strategy mechanism design. However, such a reductionist approach offers little help in understanding the specific structure of Bayesian persuasion even in the most basic settings (see, e.g., "Bayesian Persuasion" by Kamenica and Gentzkow). When it comes to computation (which is the main focus of our paper), yet another issue arises: the computational complexity of a problem depends crucially on its representation. The standard representation of an instance of Bayesian persuasion is typically much more succinct than the flat representation of the corresponding Stackelberg game (where the leader's strategy space is all feasible policies of the sender in the Bayesian persuasion instance), which means an "efficient" algorithm under the latter representation may not be "as efficient" under the former representation.

Below we provide a detailed comparison to the work by Gan et al. We will focus on concrete differences, which are easier to describe and verify. In particular, it should be clear from the differences below that the results are not "identical".

• Model: allowing the "agent" / "follower" / "receiver" to choose a response that is suboptimal by a given amount is a standard approach in algorithmic game theory when robustness is desired. Both our work and that of Gan et al. take this approach. However, the first major difference (both conceptual and technical) already shows in the respective models: the succinct representation of a Bayesian persuasion instance has the additional component of states. This in particular means the sender's strategy is a randomized mapping from states to posterior beliefs, which is, superficially speaking, of much higher dimensions than a Stackelberg equilibrium. In fact, since the classical revelation principle is no longer valid, one may suspect the former strategy space is infinite-dimensional (we show this is not the case). As we argue below, this has significant technical implications to the computation of an (almost) optimal strategy.

• Structure of optimal strategies: our positive results rely crucially on a structural property of optimal strategies that we prove (Lemma 3.2), which doesn't have a counterpart in robust Stackelberg games. The property says that while there are infinitely many possible signals, restricted to optimal strategies, many of them can be grouped, and we only need to consider a finite number of representative signals. This in particular means the effective strategy space of the sender is finite-dimensional. Note that here, the receiver may choose different actions depending on the signal sent. In contrast, the leader's strategy space in a robust Stackelberg game is naturally finite dimensional, and the follower always chooses a fixed action in response to the leader's strategy.

• Algorithm for fixed number of actions: our algorithm when the number of actions is fixed (Proposition 3.3) is a natural combination of the classical LP for Bayesian persuasion and the above structural property. In particular, we solve a single LP for the sender's optimal strategy. For comparison, the fixed-$n$ algorithm by Gan et al. generalizes the algorithm by Conitzer and Sandholm ("Computing the Optimal Strategy to Commit to"), which enumerates the follower's response and solves one LP for each possibility.

• Algorithm for fixed number of states: here we deviate significantly from existing techniques. In particular, our algorithm relies crucially on the notion of symmetric difference graphs and connectivity therein. To our knowledge, such techniques have not been employed in the context of Bayesian persuasion or Stackelberg games. In contrast, there are no states in Stackelberg games to begin with. Note that the parameter $m$ in Stackelberg games plays an intrinsically different role than the number of states in our model, and Gan et al. present no efficient algorithm when $m$ is fixed (though the comparison itself may not be meaningful in the first place).

• Hardness result: first we note that it's not uncommon for a well-motivated problem to be computationally hard, and the fact that both our problem and Gan et al.'s are hard doesn't necessarily mean the two are otherwise similar. Our hardness result is based on a fundamentally different reduction from Gan et al.'s. In particular, we reduce from the problem of Subset Sum, whereas Gan et al. reduce from Exact Cover by 3-Sets. Details of the two reductions bear virtually no similarity.

• Approximation algorithm: our algorithm shares the same high-level idea with Gan et al.'s (as well as many other approximation algorithms involving the probability simplex): one first discretizes the probability simplex into a reasonable number of representative points, and then considers the problem restricted to these points. Despite this high-level similarity, the concrete algorithms are sufficiently different. Specifically, the two algorithms are based on their exact (and inefficient) versions respectively, which means our algorithm solves a single LP, and Gan et al.'s enumerates the follower's response and solves one LP for each possibility. Our algorithm also has to deal with additional challenges introduced by the states and the prior distribution.

Thank you for your detailed and insightful comments.

QPTAS and hardness not explained: we agree this is suboptimal. We made a hard choice here due to the strict page limit. There is a high-level description of the QPTAS in Appendix F. We find the proof of the hardness result particularly interesting from a technical perspective, though we couldn't find a more concise way to describe the main idea due to the nature of such hardness reductions. We will use the extra page afforded by the camera-ready version to provide more explanations in the main paper.

Small state spaces algorithm: we are not sure if we correctly understand your proposal, but based on what we understand: our algorithm is essentially doing what you proposed. The "explore" subroutine is needed precisely because we need to find the vertices of the regions $\Delta_{(A, \tilde a)}$ -- we don't know which $(A, \tilde a)$ pairs to consider a priori, and we can't consider all of them because just the enumeration would cost too much (time exponential in $n$). Therefore, we abstract the structures of polytopes in the “space of posterior distributions” into the “symmetric difference graph”, on which we can utilize the graph algorithms to efficiently find all feasible signals, i.e., “vertices” that you described. We are happy to continue the discussion if you find the above unsatisfactory.

Fixed-parameter algorithms, comparison to Gan et al.: very superficially, our algorithm has to deal with states, while Gan et al.'s doesn't. In particular, we are not aware of techniques similar to the "explore" subroutine used in the fixed-number-of-states algorithm (given that it is in fact necessary) in similar contexts. Even our fixed-number-of-actions algorithm combines the classical LP for Bayesian persuasion with the structural property that we prove (Lemma 3.2), whereas Gan et al.'s algorithm generalizes the classical algorithm for Stackelberg equilibrium by Conitzer and Sandholm ("Computing the Optimal Strategy to Commit to"). As a result, our algorithm solves a single LP (which is in a sense necessary), and Gan et al.'s enumerates the follower's response and solves one LP for each possibility. Please also refer to our response to Reviewer zPak for more detail.

Knowing $\delta$: the assumption can be partially relaxed since the sender can estimate $\delta$, e.g., through binary search. Once a guess of $\delta$ has been made, the sender can implement the corresponding strategy and determine if the guess is too optimistic by observing whether the realized payoff is lower than expected. Note that here we need certain monotonicity properties: if the guess is too small, then the payoff will be upper bounded by the actual optimal payoff, which is upper bounded by the optimal payoff under the guess; if the guess is too large, then the implemented strategy also works for any smaller $\delta$ (including the actual one), and the resulting payoff will be at least as good. We will discuss this if space permits.

Multi-type receiver: our results should generalize to the case of a fixed number of types. The idea is to construct the type-free LP for each type separately, and then consider the "product LP" where each product signal is a vector of signals, one for each type. One would also modify the objective function to incorporate the prior distribution over types.