{'fraction_non_alphanumeric': 0.05190425127123041, 'fraction_numerical': 0.010654121553841364, 'mean_word_length': 4.097328749008199, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Algorithmic Bayesian persuasion with combinatorial actions

Bayesian persuasion is a model for understanding strategic information revelation: an agent with an informational advantage, called a sender, strategically discloses information by sending signals to another agent, called a receiver. In algorithmic Bayesian persuasion, we are interested in efficiently designing the sender's signaling schemes that lead the receiver to take action in favor of the sender. This paper studies algorithmic Bayesian-persuasion settings where the receiver's feasible actions are specified by combinatorial constraints, e.g., matroids or paths in graphs. We first show that constant-factor approximation is NP-hard even in some special cases of matroids or paths. We then propose a polynomial-time algorithm for general matroids by assuming the number of states of nature to be a constant. We finally consider a relaxed notion of persuasiveness, called CCE-persuasiveness, and present a sufficient condition for polynomial-time approximability.


Introduction
Information asymmetry is ubiquitous. For example, a seller has more information about a product than a customer, and a client sometimes knows more about a delegated task than a worker. Such an agent with an informational advantage often strategically discloses information to influence the receiver's decisions. A fundamental question in information economics asks how much influence an informational advantage has or what kind of information disclosure strategy the sender should use.
Bayesian persuasion [Kamenica and Gentzkow, 2011] is a model for understanding strategic information disclosure. In the standard setting, there are two agents called the sender and the receiver. The sender, who has an informational advantage, strategically reveals information by sending a signal to the receiver. Then, according to the revealed information, the receiver selects an action that maximizes his expected utility. The receiver's action also affects the sender's utility, which is usually different from the receiver's utility. The sender's goal is to design a strategy for information disclosure, called a signaling scheme, to lead the receiver to select an action that is favorable for the sender. In this paper, we are interested in the algorithmic aspect of Bayesian persuasion: when can we efficiently compute (approximately) optimal signaling schemes?
In many practical scenarios, the receiver's actions are specified by some combinatorial constraints. For example, a receiver's action may be a path in a network or a portfolio of a limited number of stocks. In such cases, lists of the receiver's actions can be prohibitively large, making standard methods for computing the sender's signaling schemes impractical. To reveal when we can efficiently compute optimal signaling schemes in the presence of such combinatorial actions is an important question, but it remains unexplored as mentioned in [Dughmi, 2017, Open Question 2.8]. This paper addresses this open question and elucidates several classes of problems for which we can/cannot efficiently compute (approximately) optimal signaling schemes.
To motivate our work, we below give concrete situations where the receiver's actions are combinatorial. An important application of Bayesian persuasion is financial advice. Suppose the sender and the receiver to be a financial adviser and an investor, respectively. The sender knows accurate predictions on stock returns, which are unknown to the receiver. Since the sender's returns are not always aligned with those of the receiver, the sender strategically reveals information to increase her returns. After receiving a signal (advice) from the sender, the receiver decides which stocks to buy. In practice, there are a huge number of stocks, and it is unrealistic to assume that the receiver can hold a portfolio of arbitrarily many stocks. Thus, a cardinality constraint is often imposed when optimizing portfolios [Ito et al., 2018, Zhu et al., 2020. In this situation, each receiver's action is a combination of a limited number of stocks.
More complicated combinatorial constraints can appear in other applications. For example, let us imagine that a boss (sender) asks a subordinate (receiver) to create a committee by choosing a representative for each of several groups. An action of the receiver is a set of people that contains a single person from each group. In another example, the receiver is a company that constructs an electrical grid connecting all electricity consumers, and the sender is a government that requests the construction. An action of the receiver is a tree in a network that covers all electricity consumers.

Our Results
We study Bayesian persuasion with combinatorial actions, each of which is a subset of a finite set, denoted by E, and satisfies some combinatorial constraints. We call each component of E an element, i.e., an action is a combination of some elements. Utility functions of the sender and the receiver are set functions defined on E. The main issue of this setting is that there may exist exponentially many actions in |E|. We aim to clarify under what conditions we can/cannot compute (approximately) optimal signaling schemes efficiently with respect to input sizes, including |E|.
First, we prove that it is NP-hard to achieve constant-factor approximation even in some special cases of matroid or path constraints. For partition matroid constraints, we utilize a hardness result studied in public Bayesian persuasion with no externalities [Dughmi and Xu, 2017]. For other combinatorial constraints, including uniform matroid constraints, graphic matroid constraints, and path constraints, we construct reductions from an existing hard problem called LINEQ MA [Guruswami and Raghavendra, 2009], which asks to determine whether a large fraction of linear equations can hold or even a small fraction cannot hold. These reductions have connections to the NP-hardness proof for the O S problem [Castiglioni et al., 2020] and, as a by-product of our result on partition matroids, we obtain a hardness result for the O S problem. Next, we develop a polynomial-time algorithm for general matroid constraints by assuming the number of states of nature to be a constant (we explain what states and nature are in Section 2). We formulate the problem as an exponentially large linear program (LP) and then show that its size can be reduced by enumerating only relevant variables and constraints. To enumerate them efficiently, we utilize a computational-geometric algorithm. For some special matroids, we show that the LP size can be further reduced.
Finally, we consider a relaxed persuasiveness condition called CCE-persuasiveness [Xu, 2020, Celli et al., 2020, which is based on the concept of Bayes coarse correlated equilibria. We provide a sufficient condition under which a polynomial-time approximation algorithm exists. Specifically, if we can approximately maximize a sum of the sender's and receiver's utilities so that only the sender's has an approximation factor, we can compute approximately optimal CCE-persuasive schemes in polynomial time. This result is applicable to important cases where the sender's utility is a monotone submodular function. Kamenica and Gentzkow [2011] proposed the original Bayesian-persuasion model. Utilizing the model, researchers analyzed various social situations, including voting [Schnakenberg, 2015, Alonso andCâmara, 2016], financial sector stress tests [Goldstein and Leitner, 2018], financial markets [Duffie et al., 2017], routing [Bhaskar et al., 2016], auctions [Dughmi et al., 2014], and information spread [Arieli and Babichenko, 2019]. On the other hand, various algorithms have been developed for Bayesian persuasion with additional settings: exponentially many states of nature [Dughmi and Xu, 2016], multiple receivers [Arieli and Babichenko, 2019], secretary problem [Hahn et al., 2020b], prophet inequalities [Hahn et al., 2020a], and payment [Dughmi et al., 2019].

Related Work
The closest setting to ours is Bayesian persuasion with no externalities [Babichenko and Barman, 2017, Dughmi and Xu, 2017, Arieli and Babichenko, 2019, Xu, 2020, Castiglioni et al., 2021b. In this setting, there are multiple receivers, and each one selects a binary action from {0, 1} to maximize his own utility, which does not depend on the other receivers' actions. This setting can be decomposed into two subclasses: private and public. The former supposes that the sender can send a signal to each receiver privately, while the latter supposes that the sender sends a public signal to all the receivers. As we prove in Section 3, public Bayesian persuasion with no externalities is equivalent to our setting with a special partition matroid constraint. Our study provides hardness results for other types of constraints and algorithms for general matroid constraints, thus going beyond the existing results on public Bayesian persuasion.
Some existing studies introduced constraints on Bayesian persuasion. A series of studies [Dughmi et al., 2014, Gradwohl et al., 2021 considered a setting where the sender can use only a limited number of bits for signaling. Babichenko et al. [2021] considered ex ante and ex post constraints, which restrict structures of posterior distributions induced by the sender's signals. Note that the constraints considered in those studies are imposed on the sender's signaling scheme, while we consider combinatorial constraints on the receiver's possible actions.

Problem Settings and Preliminaries
This section provides problem settings of Bayesian persuasion with combinatorial actions. We first describe the basic setting, where sender and receiver maximize their utility functions and the receiver's actions are represented by a matroid. We then present some basics and examples of matroids. We finally describe the setting with path constraints, where sender and receiver minimize their cost functions.
Notation. We denote the set of non-negative reals by R ≥0 . For any set X, let ∆ X := {p : X → R ≥0 | i∈X p(i) = 1} be the probability simplex over X.

Basic Setting
Let Θ be the family of states of nature. A state θ ∈ Θ is drawn from a distribution µ ∈ ∆ Θ , which is common knowledge shared by the sender and the receiver. In the remainder of this paper, we assume µ(θ) > 0 for all θ ∈ Θ. If this does not hold, we can remove such θ from the problem. The sender has the informational advantage of knowing the realized state θ, while the receiver cannot access θ directly.
After observing the state of nature θ, the sender sends a signal σ ∈ Σ to the receiver. The signals can be randomized, that is, the sender can select any distribution φ θ ∈ ∆ Σ for each θ ∈ Θ and send signal σ randomly sampled from φ θ depending on the observed state θ. A tuple (φ θ ) θ∈Θ of probability distributions over Σ is called a signaling scheme. The core assumption of Bayesian persuasion is the commitment assumption, which compels the sender to publicly commit to a signaling scheme before observing the state of nature θ. Under this assumption, the process goes on as follows: the sender publicly declares a signaling scheme (φ θ ) θ∈Θ , then observes the state of nature θ sampled from µ, and then sends signal σ to the receiver following the distribution φ θ .
Let E be a finite set of n elements. A combinatorial action is a combination of elements in E. Let I ⊆ 2 E be the set of all possible combinatorial actions the receiver can take. After observing signal σ, the receiver takes a combinatorial action S ∈ I. As a result of this action, the sender and the receiver obtain utility values, which are specified by non-negative set functions s θ : 2 E → R ≥0 and r θ : 2 E → R ≥0 , respectively, for each state of nature θ ∈ Θ. When receiving signal σ ∈ Σ, the receiver's belief on the state of nature is represented by the posterior distribution ξ σ ∈ ∆ Θ such that .
The receiver takes the best response according to this posterior distribution, that is, he selects S * σ ∈ I such that If there are multiple best responses, we assume that ties are broken in favor of the sender. Consequently, the sender, who commits to the signaling scheme (φ θ ) θ∈Θ , obtains the following payoff in expectation: The revelation principle [Kamenica and Gentzkow, 2011] claims that to consider only direct and persuasive signaling schemes is sufficient. A direct signaling scheme associates each signal with an action, i.e., Σ = I, and recommends action S ∈ I by sending the corresponding signal S ∈ Σ. A direct signaling scheme is persuasive if the receiver has no incentive to deviate from recommendation S ∈ I when receiving signal S ∈ Σ. The persuasiveness constraint requires signaling scheme (φ θ ) θ∈Θ to satisfy θ∈Θ ξ S (θ)r θ (S) ≥ θ∈Θ ξ S (θ)r θ (S ′ ) for every pair S, S ′ ∈ I, where ξ S is the posterior distribution when the receiver observes S ∈ Σ.
By considering the revelation principle, we can formulate the problem of computing an optimal signaling scheme as (1) The first constraint is the persuasiveness constraint, under which S must be one of the receiver's best responses when the sender sends signal S. The second constraint requires φ θ to be a probability distribution in ∆ I for each θ ∈ Θ.
In general, the utility set functions (s θ ) θ∈Θ and (r θ ) θ∈Θ do not have a polynomial-size representation in |E| and |Θ|. In such cases, we assume that we have value oracles, i.e., s θ (S) and r θ (S) values are available for any given θ ∈ Θ and S ⊆ E. Similarly, if the set I of the receiver's actions does not have a polynomial-size representation, we assume access to an independence oracle, which returns whether S ∈ I or not for any given S ⊆ E. These assumptions are common in combinatorial optimization.
For the hardness results in Section 3, we let (s θ ) θ∈Θ and (r θ ) θ∈Θ be linear functions, i.e., s θ (S) = i∈S s θ ({i}) and r θ (S) = i∈S r θ ({i}) for all S ⊆ E and θ ∈ Θ. Such (s θ ) θ∈Θ and (r θ ) θ∈Θ have polynomial-size representations. We also use sets I of actions that have polynomial-size representations. Thus, our hardness results indeed come from computational hardness, not from the hardness of representing problems. For the polynomial-time algorithms in Section 4, we assume (r θ ) θ∈Θ to be linear but allow (s θ ) θ∈Θ to be a general set function. For the CCE-persuasiveness result in Section 5, we allow both (s θ ) θ∈Θ and (r θ ) θ∈Θ to be general set functions, while we impose an approximability assumption as detailed later.

Matroids
Many of our results consider combinatorial constraints represented by matroids, which are useful to model various combinatorial actions that appear in practice.
A pair (E, I) of a finite set E and a non-empty set family I ⊆ 2 E is called a matroid if the following conditions hold: • S ⊆ T ∈ I implies S ∈ I.
• For any S, T ∈ I with |S| < |T |, there exists i ∈ T \ S such that S ∪ {i} ∈ I.
A set S ⊆ E is called independent if S ∈ I holds. Given a matroid (E, I) and a non-negative weight w(i) ∈ R ≥0 for each element i ∈ E, a maximum weight independent set S * ∈ argmax S∈I i∈S w(i) can be found by using the greedy algorithm, which starts with the empty set and, in descending order of weights, adds elements that maintain independence. Below, we introduce some special matroids that are useful in practical scenarios.
Uniform matroids. A uniform matroid is a matroid with I = {S ⊆ E | |S| ≤ k} for some integer k > 0. Under a uniform matroid constraint, the receiver selects at most k elements that yield the largest expected utility value. This constraint fits the portfolio optimization scenario, where the receiver selects k stocks expected to yield the largest return.
Partition matroids. Let E 1 , . . . , E P ⊆ E be a partition, i.e., E 1 ∪ · · · ∪ E P = E and E i ∩ E j = ∅ for every distinct i, j ∈ [P ]. Assign some positive integer k i for each i ∈ [P ]. A matroid with I = {S ⊆ E | ∀i ∈ [P ], |S ∩ E i | ≤ k i } is called a partition matroid. Under a partition matroid constraint, the receiver selects at most k i elements from the ith partition. This can model a scenario where the receiver creates a committee by choosing one person from each group.
Graphic matroids. Given an undirected graph (V, E), a graphic matroid (E, I) is a matroid with I = {S ⊆ E | S does not contain a cycle}. Any maximal independent set of a graphic matroid forms a spanning tree (or a spanning forest if graph (V, E) is not connected). If E is a set of all edges that can be used for constructing an electrical grid and V is a set of all electricity consumers, a graphic matroid constraint models the situation where the receiver constructs an electrical grid covering all consumers.

Minimization Setting with Path Constraints
Given a directed graph G = (V, E) with origin v s ∈ V and destination v t ∈ V , we consider a setting where the receiver selects a v s -v t path S ⊆ E according to a signal from the sender. This setting appears, for example, when the sender is an association that manages traffic by recommending a route, and the receiver is a taxi driver. In this setting, the sender and the receiver usually aim to minimize their costs rather than maximize utility functions. Thus, we focus on the minimization setting regarding path constraints (we distinguish maximization and minimization settings since some of our results concerning approximability cannot be translated from one to the other). The problem of computing an optimal signaling scheme can be formulated as a minimization version of (1), where I is the set of all v s -v t paths. The receiver selects a path that minimizes his expected cost based on the posterior distribution; therefore, we reverse the inequality sign of the persuasiveness constraint. The sender's goal is to minimize her expected cost.

Hardness Results
We show the NP-hardness of obtaining a constant-factor approximation for Bayesian persuasion with partition matroid, uniform matroid, graphic matroid, and path constraints. Throughout this section, we assume the utility functions of the sender and the receiver to be linear.

Partition Matroid Constraints
We show that Bayesian persuasion with a partition matroid constraint is intractable even in a special case where each partition has two elements. We prove this via a reduction from public Bayesian persuasion with no externalities. Dughmi and Xu [2017] proved that constant-factor approximation for public Bayesian persuasion with no externalities is NP-hard even if we restrict the sender's utility function to s θ (S) = |S| for each θ ∈ Θ. By associating each partition with a receiver of public Bayesian persuasion, we obtain the reduction, thus proving the following hardness result.
Theorem 1. For any constant α ∈ (0, 1], it is NP-hard to compute an α-approximate solution for Bayesian persuasion with a partition matroid constraint whose partitions are of size two.
The proof and the details of public Bayesian persuasion with no externalities are provided in Appendix B.1.
Remark 2. We can also construct a reduction for the opposite direction. Therefore, we establish an equivalence in terms of the approximability between public Bayesian persuasion with no externalities and Bayesian persuasion with a partition matroid constraint whose partitions are of size two.
As a by-product of Theorem 1, we can obtain a hardness result on the O S problem [Castiglioni et al., 2020], which is a variant of Bayesian persuasion where the receiver's utility depends on a random type that is unknown to the sender. We provide the details in Appendix B.2.

Uniform Matroid Constraints
We prove the NP-hardness of constant-factor approximation for Bayesian persuasion with a uniform matroid constraint. Our proof is inspired by that of the O S problem [Castiglioni et al., 2020], which is equivalent to the special case of partition matroid constraints, as mentioned above. Note that a uniform matroid cannot be represented by the special partition matroid with size-two partitions. Nevertheless, we can use a similar proof strategy to the one used for the O S problem. Specifically, we construct a reduction from a variant of an existing hard problem called LIENQ MA [Guruswami and Raghavendra, 2009], which asks us to distinguish whether a linear system Ax = c has a solution satisfying most of the equations or no solution satisfies even a small fraction of the equations. The definition of this problem and the proof of the following theorem are provided in Appendix B.3.
Theorem 3. For any constant α ∈ (0, 1], it is NP-hard to compute an α-approximate solution for Bayesian persuasion with a uniform matroid constraint.

Graphic Matroid Constraints
The hardness result for Bayesian persuasion with graphic matroid constraints can be proved in a similar way to that of uniform matroid constraints, i.e., we construct a reduction from the variant of the LINEQ MA problem. We provide the proof in Appendix B.4.
Theorem 4. For any constant α ∈ (0, 1], it is NP-hard to compute an α-approximate solution for Bayesian persuasion with a graphic matroid constraint.

Path Constraints
Recall that in this setting, the sender and the receiver aim to minimize their expected costs, while the above settings consider maximizing utilities. Thus, the approximation ratio for this problem is lower-bounded by 1, and a smaller value implies a better approximation. The proof is similar to those for uniform or graphic matroids (see Appendix B.5).
Theorem 5. For any constant α ∈ [1, ∞), it is NP-hard to compute an α-approximate solution for Bayesian persuasion with a path constraint.

Polynomial-time Algorithm for Constant Number of States
We present a polynomial-time algorithm for Bayesian persuasion with general matroid constraints by assuming the number of states of nature to be a constant, i.e., |Θ| = O(1). We denote by d the dimension of ∆ Θ , i.e., d := |Θ| − 1. Throughout this section, we assume the receiver's utility function to be linear, while the sender's is a general set function, and we regard computation costs that depend only on d as constants.
The main obstacle is the fact that the number of variables and constraints in LP (1) is exponential in n := |E|. In the case of matroid constants, however, we can show that only a small number of variables can take non-zero values and that a large fraction of constraints is unnecessary. Thus, if we can efficiently enumerate all relevant variables and constraints, we can obtain a smaller LP that is equivalent to the original LP (1) and can be solved more cheaply. This approach is inspired by the one studied in public Bayesian persuasion with no externalities [Xu, 2020], which is equivalent to Bayesian persuasion with a special partition matroid constraint, as mentioned Section 3.1. Our algorithm can be seen as an extension of [Xu, 2020] to the case of general matroids. Below we present the technical details.
A key observation is that if d is small, the number of combinatorial actions that the receiver can take is also small. We define the set I * of all combinatorial actions that can be the best response for some {2, 3} is the best.
holds and the complement. The receiver's best response is identical within each cell.
posterior distribution as By using this reduced set of combinatorial actions, we formulate a smaller LP as follows: This LP formulation has variables φ θ (S) only for S ∈ I * , and the first constraint exists only for S, S ′ ∈ I * . We can show that this reduced LP formulation (2) is equivalent to the original one (1). The proof is provided in Appendix C.1.
Proposition 6. There is a bijection between the feasible regions of (1) and (2) that does not change the objective value.
As illustrated in [Xu, 2020, Example 1], if the receiver's expected utility has certain degeneracy, the receiver may have exponentially many best responses, i.e., |I * | = Ω(2 n ). To exclude such troubling corner cases, we make a mild non-degeneracy assumption regarding the receiver's utility.
Under this assumption, we develop a polynomial-time algorithm, which first enumerates all combinatorial actions in I * and then solves the reduced LP (2). We below describe our algorithm for general matroids and then present faster algorithms for some special matroids.
Algorithm 1 Algorithm for Bayesian persuasion with a general matroid constraint Input: value oracles of s θ and r θ , independence oracle of I, µ. Output: signaling scheme (φ θ ) θ∈Θ .
Obtain the set of all cells C of the arrangement of H by using cell enumeration algorithm [Edelsbrunner, 1987].
Let ξ ∈ C be any interior point of C.

General Matroids
We explain how to enumerate I * ⊆ I in polynomial time when is at least that of j and the complement (see Figure 1). Thus, the set of hyperplanes H = {h ij | i, j ∈ E, i = j} divides aff(∆ Θ ) into small pieces, which we call cells. Within each cell, the descending order of expected utility values is identical.
Algorithm 1 presents the details of our algorithm. We first enumerate all cells and then use the greedy algorithm to obtain a maximum weight independent set for an interior point of each cell. Although H has degeneracy, by using an algorithm for constructing arrangements of hyperplanes [Edelsbrunner, 1987], we can enumerate all cells. Finally, we solve the reduced LP (2) where I * is replaced with the family of obtained independent sets, denoted by I C . Now, we show that I C obtained by the algorithm recovers I * , the family of possible best responses. The following lemma guarantees that considering only interior points of cells is sufficient for enumerating I * under Assumption 7, i.e., we do not need to care about the boundaries of cells.
Lemma 8. Let ψ 1 , . . . , ψ n ∈ R Θ be vectors that satisfy Assumption 7. Then, for any permutation π, Therefore, we can enumerate all possible best responses I * by collecting maximum weight independent sets returned by the greedy algorithm, whose behavior depends only on the descending order of the weights.
The proofs of the above lemma and theorem are provided in Appendix C.2. Since |H| = O(n 2 ), the cells can be enumerated in O(n 2d ) time [Edelsbrunner, 1987]. The resulting LP (2) has O(n 2d ) variables and O(n 4d ) constraints, which can be solved in poly(n d ) time.

Faster Algorithms for Special Matroids
As described above, our algorithm first enumerates every combinatorial action that can be the receiver's best response for some ξ ∈ ∆ Θ , and then solves the reduced LP. For several special cases of matroids, we can use faster enumeration algorithms and obtain better upper bounds on |I * |.
Uniform matroids. In this case, a receiver's action consists of top-k elements, and thus we can enumerate all possible best responses I * in a simpler manner. We consider n hyperplanes on ∆ Θ associated with n expected utility values, and enumerate all combinations of k hyperplanes that correspond to top-k elements for some ξ ∈ ∆ Θ . The enumeration problem is closely related to a discrete-geometric subject, called the k-level in an arrangement of hyperplanes. By using an algorithm of [Mulmuley, 1991] that enumerates all faces of level at most k, we can enumerate all k-level faces corresponding to Clarkson and Shor [1989] presented an upper bound on the number of faces of level at most k, which implies Partition matroids. As with the case of general matroids, we enumerate cells of the hyperplane arrangement, but the number of hyperplanes can be reduced. A key observation is that the maximum weight independent set is determined by the order of weights of elements in each partition, not by the order of weights of all elements. Therefore, it is sufficient to enumerate all possible orders of weights in each partition. Let n 1 := |E 1 |, n 2 := |E 2 |, . . . , n P := |E P | be the size of each partition. For each p ∈ [P ], we consider hyperplanes for all pair of distinct i, j ∈ E p . As with the case of general matroids, we can obtain I C ⊇ I * by enumerating the cells of the arrangement of those hyperplanes. If n 1 = · · · = n P , the number of hyperplanes is O(n 2 /P ). Therefore, in this case, we have |I * | = O(n 2d /P d ).
Graphic matroids. In this case, we need to enumerate all spanning trees S ∈ I that can attain the maximum weight for some ξ ∈ ∆ Θ . To this end, we can use existing results on the parametric spanning tree problem. When d = 1, by using an algorithm of [Fernández-Baca et al., 1996], we can enumerate all the spanning trees I * in O(|V ||E| log |V |) time. Moreover, when d = 1, it is known that |I * | = O(|E||V | 1/3 ) holds [Dey, 1998].
Remark 10. For path constraints, even if d = 1, the number of paths that can be the shortest path for some ξ ∈ ∆ Θ is known to be n Ω(log n) in general [Carstensen, 1983]. Thus, our approach, which enumerates every path that can be the shortest path for some ξ ∈ ∆ Θ , fails to run in polynomial time even if d is a constant. We need a different approach for obtaining an efficient algorithm for path constraints.

Polynomial-time Algorithm for CCE-Persuasiveness
We present how to compute approximately optimal CCE-persuasive signaling schemes for Bayesian persuasion with combinatorial actions. To motivate us to study CCE-persuasiveness, a relaxed notion of persuasiveness, in the combinatorial setting, let us consider the following investment example. Let the receiver be an investor wondering whether to buy an investment trust or build a portfolio by himself. If the investor decides to buy an investment trust, stocks are bought following a policy of a portfolio manager, who is the sender. The sender wants to sell the investment trust, and a signaling scheme corresponds to her portfolio-management policy. The receiver buys the investment trust if it is at least as beneficial as the portfolio built following his prior belief. In this example, in contrast to the standard setting, the sender's Algorithm 2 Algorithm for CCE-persuasiveness Input: value oracles of s θ and r θ , independence oracle of I, α-approximation oracle, µ, v min , v max , ǫ. Output: signaling scheme (φ θ ) θ∈Θ .
Apply the ellipsoid method with an α-approximate separation oracle to dual LP (4) with additional constraint −C · y + θ∈Θ x θ ≤ v.
recommendation is regarded as persuasive if it is better than the best action taken based on the receiver's prior belief. This idea of persuasiveness can be modeled by CCE-persuasiveness, as detailed below.
As pointed out by Bergemann and Morris [2016], Bayesian persuasion is the problem of finding a Bayes correlated equilibrium that is optimal for the sender. By relaxing the condition of Bayes correlated equilibria, we can obtain a broader class of equilibria called Bayes coarse correlated equilibria, as mentioned in several studies [Cai andPapadimitriou, 2014, Hartline et al., 2015]. In a Bayes coarse correlated equilibrium, the receiver has no incentive to ignore the signal, i.e., following the signal is at least as beneficial as the best action selected based on his prior distribution. Let C = max S∈I θ∈Θ µ(θ)r θ (S) be the receiver's utility when he selects the best action based on his prior distribution. The LP for computing an optimal CCE-persuasive signaling scheme can be written as follows: We present a sufficient condition for achieving a constant-factor approximation for the above LP. For public Bayesian persuasion, the equivalence between exact maximization of certain set functions and computation of CCE-persuasive schemes has been established in [Xu, 2020, Theorem 5.1]. Compared with the existing result, ours is restricted to one direction (maximization implies persuasion). However, it is applicable to important cases where maximization can be done only approximately. For example, we can allow the sender's utility to be a monotone submodular function, as explained later. To prove the result, we carefully combine an existing binary search framework for approximate separation oracles [Jansen, 2003, Jain et al., 2003 and the proof of [Xu, 2020, Theorem 5.1]. Throughout this section, we do not make any assumption on the sender's and the receiver's utility functions; instead, we assume that an approximate maximization oracle, together with upper and lower bounds on the optimal value, are available.
Theorem 11. Let α ∈ (0, 1]. For any y ≥ 0 and θ ∈ Θ, assume that a polynomial-time α-approximation oracle that returns S ∈ I with the following guarantee is available: s θ (S) + y · r θ (S) ≥ α · s θ (S ′ ) + y · r θ (S ′ ) for any S ′ ∈ I. Moreover, assume v min and v max to be given as inputs such that (i) OPT > 0 implies OPT > v min and (ii) OPT < v max , where OPT is the optimal value. Then, for any ǫ ∈ (0, α), there is a polynomial-time algorithm that computes an (α − ǫ)-approximate CCE-persuasive signaling scheme.
Proof. The dual of the LP (3) can be written with variables {x θ } θ∈Θ and y ∈ R as follows: We consider applying the ellipsoid method to this LP. Here, since we cannot directly use the α-approximation oracle as a separation oracle, we employ a binary-search framework of [Jansen, 2003, Jain et al., 2003, which enables us to combine the ellipsoid method with the following α-approximate separation oracle. The proof of the following lemma is provided in Appendix D.1.
Lemma 12. Under the assumption of Theorem 11, there is a polynomial-time α-approximate separation oracle such that for any {x θ } θ∈Θ and y, it either returns a separating hyperplane or guarantees the feasibility of {x θ /α} θ∈Θ and y/α.
We perform a binary search on [0, v max ] to estimate the optimal value of the dual LP (see Algorithm 2). Given an estimated value v ∈ R, we add −C · y + θ∈Θ x θ ≤ v to the constraints in (4) and check the feasibility of the resulting inequality system using the ellipsoid method with the α-approximate separation oracle. Note that since we can use only an α-approximate separation oracle, the ellipsoid method guarantees that the estimated value v is either approximately feasible or infeasible. The binary search continues until the interval becomes smaller than ǫ ′ = ǫv min . Let v * be the smallest approximately feasible value found by this binary search, and let ({x * θ } θ∈Θ , y * ) be its corresponding solution. From Lemma 12, ({x * θ /α} θ∈Θ , y * /α) satisfies the constraints of the dual LP (4), and thus the optimal value is at most v * /α. Furthermore, since v * − ǫ ′ is infeasible, the optimal value of the dual LP (4) If the binary search does not find any infeasible v, then v * ∈ [0, ǫv min ) and the optimal value is less than v min . From the assumption on v min , the optimal value is 0. Thus, any signaling scheme is optimal. Otherwise, to obtain a solution, we construct a restricted version of the primal LP (3) as follows. When executing the ellipsoid method for the smallest v such that v ≥ v * − ǫ ′ , we check polynomially many constraints, which are enough to conclude that the optimal value of the dual LP is larger than v * − ǫ ′ . This process yields a restricted dual LP with the polynomially many constraints, each of which corresponds to a primal variable. By allowing only those primal variables to be non-zero, we can obtain a restricted primal LP. From the strong duality, the optimal value of the restricted primal LP is also larger than v * − ǫ ′ . On the other hand, the weak duality implies that the optimal value of the (non-restricted) primal LP (3) is at most v * /α. Thus, by solving the restricted primal LP, we can compute an (α − ǫ)-approximate solution in polynomial time.
For several classes of utility functions, we can implement approximate separation oracles that run in polynomial time. For example, we can exactly solve max S∈I s θ (S) + y · r θ (S) if both s θ and r θ are linear and I is an independence system of a matroid. When s θ is a monotone submodular function, r θ is linear, and I is an independence system of a matroid, the continuous greedy algorithm can be used as a (1− 1/e)approximation oracle [Sviridenko et al., 2017, Theorem 1]. Furthermore, when s θ is a monotone submodular function, r θ is a gross substitute function, and I is an independence system of a uniform matroid, a variant of the continuous greedy algorithm serves as a (1−1/e)-approximation oracle [Soma and Yoshida, 2018]. By considering the minimization version, we can use a shortest-path algorithm as an exact separation oracle if both s θ and r θ are linear and I is the set of paths on some graph. We detail how to set v min and v max in Appendix D.

A Further Related Work
Castiglioni et al.
[2021a] studied a signaling problem in a Bayesian network congestion game, in which each of multiple receivers selects a path on a network whose edges are associated with uncertain costs. They developed a polynomial-time algorithm that computes an optimal signaling scheme under CCEpersuasiveness constraints. Their setting is similar to ours when we consider path constraints, but there are several differences. In their setting, there are multiple receivers whose actions affect other receivers' costs through congestion, while in our setting, there is only a single receiver. Moreover, they assume that the sender's objective is to minimize the social cost (the sum of the receivers' costs), while we do not make such an assumption on the sender's objective. Kremer et al. [2014] and Mansour et al. [2020] considered a similar algorithmic framework for signaling based on the multi-armed bandit problem. In their setting, an informed principal sends a signal to each of multiple myopic receivers who arrive one by one, and aims at maximizing the social welfare. Their analyses are based on the framework of regret minimization, and theoretically different from Bayesian persuasion.

B.1 Proof for Partition Matroid Constraints
We prove the hardness result for Bayesian persuasion with a partition matroid constraint by constructing a reduction from public Bayesian persuasion with no externalities.
We describe the problem setting of public Bayesian persuasion with no externalities, which was introduced by Arieli and Babichenko [2019]. There are n rec receivers, each of whom takes a binary action from {0, 1}. The ith receiver obtains a payoffr θ (i, 1) ∈ R ≥0 when he takes action 1 andr θ (i, 0) ∈ R ≥0 otherwise. From the assumption of no externalities, these values do not depend on the other receivers' actions. The sender's utility functions θ : 2 [nrec] → R ≥0 is a set function, whose value depends on the set S ⊆ [n rec ] := {1, . . . , n rec } of receivers who take action 1. We here consider the case wheres θ is linear. The sender and the receivers share the same prior distribution µ on θ ∈ Θ. The sender sends a common signal σ ∈ Σ to all the receivers, and then the receivers take an action based on the common posterior distribution. This problem can be formulated as wherer θ (i) =r θ (i, 1) −r θ (i, 0). Dughmi and Xu [2017] proved that constant-factor approximation for public Bayesian persuasion with no externalities is NP-hard even if we restrict the sender's utility function to s θ (S) = |S| for each θ ∈ Θ.
We use this result to prove our hardness result for Bayesian persuasion with partition matroid constraints. By regarding each receiver of public Bayesian persuasion as a partition, we can construct the reduction and obtain the following hardness result.
Theorem 1. For any constant α ∈ (0, 1], it is NP-hard to compute an α-approximate solution for Bayesian persuasion with a partition matroid constraint whose partitions are of size two. Proof. Suppose that a problem instance of public Bayesian persuasion with no externalities is given. We construct a problem instance of Bayesian persuasion with a partition matroid constraint whose partitions are of size two. We use the given set Θ of states of nature and the prior distribution µ. Let E i = {a i,0 , a i,1 } be a partition for each i ∈ [n rec ], and define the ground set E = i∈[nrec] E i . Let k 1 = · · · = k nrec = 1, i.e., I = {S ⊆ E | |S ∩ E i | ≤ 1}. Given the ith receiver's utilityr θ (i, 0) ∈ R ≥0 andr θ (i, 1) ∈ R ≥0 for each i ∈ [n rec ], we define the receiver's utility as r θ ({a i,0 }) =r θ (i, 0) and r θ ({a i,1 }) =r θ (i, 1). Given the sender's utility functions θ : 2 [nrec] → R ≥0 for each θ ∈ Θ, we define the sender's utility for Bayesian persuasion with the partition matroid constraint as s θ (S) =s θ ({i ∈ [n rec ] | a i,1 ∈ S}) for each θ ∈ Θ and S ⊆ E.

B.2 Hardness Result for O S Problem
We give an interesting connection between Bayesian persuasion with a partition matroid constraint and the O S problem [Castiglioni et al., 2020]. The O S problem is a variant of Bayesian persuasion where the receiver's utility depends on a random type. Specifically, let T be the set of possible types of the receiver and A be the set of the receiver's actions. We defines θ (t, a) ∈ R ≥0 andr θ (t, a) ∈ R ≥0 as the sender's and the receiver's utility functions, respectively, when the receiver takes action a ∈ A and his type is t ∈ T . The sender constructs a signaling scheme (φ θ ) θ∈Θ , which determines a probability distribution over signals Σ for each θ ∈ Θ. The receiver observes the type t ∈ T , as well as the signal σ from the sender, and then takes an action based on them. The receiver's type conforms to the uniform distribution ρ ∈ ∆ T , i.e., ρ(t) = 1 |T | for all t ∈ T . Our goal is to find a signaling scheme (φ θ ) θ∈Θ that maximizes the sender's expected utility. Castiglioni et al. [2020] proved that additive approximation for O S is NP-hard. Their proof uses a problem instance of O S with three actions, which yields the following result.
Below we prove a hardness result, which is incomparable to their result. Specifically, we prove the NPhardness of constant-factor approximation for O S with two actions by providing an approximationpreserving reduction from Bayesian persuasion with a partition matroid constraint whose partitions are of size two.
Theorem 15. For any constant α ∈ (0, 1], it is NP-hard to compute an α-approximate solution for O S even if the number of actions is two. Proof. We construct an approximation-preserving reduction from Bayesian persuasion with a partition matroid constraint whose partitions are of size two to O S with two actions. Given an instance of Bayesian persuasion with a partition matroid constraint, we construct an instance of O S as follows. If there exists a partition from which the receiver can select both of the two elements, then he always selects both elements since the utility of each element is non-negative. Thus, we can assume that the receiver can select only one element from each partition without loss of generality. Suppose there are P partitions, and let E t = {(t, 0), (t, 1)} be the tth partition for each t ∈ [P ]. Let A = {0, 1} be the set of actions for the O S instance, and T = [P ] be the set of types. The set Θ of the states of nature and the prior distribution µ ∈ ∆ Θ are identical to those of the partition-matroid instance. The distribution over types is the uniform distribution ρ(t) = 1 P for all t ∈ [P ]. Define the receiver's utility functionr θ : T × A → R asr θ (t, a) = |T |r θ ({(t, a)}). Similarly, define the sender's utility functions θ : T × A → R ass θ (t, a) = |T |s θ ({(t, a)}).
We consider applying the same signaling scheme to the partition-matroid instance and the O S instance. We show that the sender's expected utility of any signaling scheme in the partition-matroid instance is equal to that in the O S instance. Let (φ θ ) θ∈Θ be a signaling scheme. First, we consider the sender's expected utility in the O S instance. Define the expected utility of action a ∈ A for the receiver with type t ∈ T when signal σ ∈ Σ is received as .
Let a t σ ∈ argmax a∈Arσ (t, a) be one of the best responses to signal σ ∈ Σ for the receiver with type t ∈ T . Then, the sender's expected utility is 1 |T | t∈T σ∈Σ θ∈Θ µ(θ)φ θ (σ)s θ (t, a t σ ). Next, we consider the sender's expected utility in the partition-matroid instance. For each signal σ ∈ Σ, the receiver's expected utility of taking action S ⊆ E is Let S * σ ∈ I be the receiver's best response that maximizes this expected utility. From the definition of a partition matroid constraint, (t, a) ∈ S * σ is chosen independently for each t ∈ T . Therefore, the receiver's best response for each t ∈ T is argmax a∈Arσ (t, a) (ties are broken in favor of the sender). Thus, there exists a bijection between the receiver's best response in the partition-matroid instance and those in the O S instance, i.e., S * σ = {(t, a t σ ) | t ∈ T , a t σ ∈ argmax a∈Arσ (t, a)}. The sender's expected utility when the receiver takes action S * σ for signal σ ∈ Σ is σ∈Σ θ∈Θ which is equal to the sender's expected utility in the O S instance. Therefore, Theorem 1 implies the NP-hardness of achieving a constant-factor approximation for O S with two actions.

B.3 Proof for Uniform Matroid Constraints
We prove the NP-hardness of constant-factor approximation for Bayesian persuasion with a uniform matroid constraint. Our proof uses almost the same reduction as the one used for proving the NP-hardness of constant-factor approximation for the O S problem. Castiglioni et al. [2020] proved the hardness of the O S problem by reducing a binary-vector version of the LIENQ MA problem to the O S problem.
• Every x ∈ Q nvar satisfies less than a δ fraction of the equations.
In the original definition of LINEQ MA(1 − ζ, δ), the former case also considers x ∈ Q nvar instead of x ∈ {0, 1} nvar . However, the proof for the original LINEQ MA by Guruswami and Raghavendra [2009] shows that the binary-vector version is also NP-hard.
Completeness. Suppose there exists a vectorx ∈ {0, 1} nvar such that at least a 1 − ζ fraction of the equations in Ax = c are satisfied. Letx = 1 τx . If (Ax) t = c t , then (Āx) t =c t . We show that the optimal expected utility is greater than 1 − 2ζ, implying that an α-approximation algorithm for Bayesian persuasion with a uniform matroid constraint outputs a signaling scheme with an expected utility greater than that α(1 − 2ζ).
We consider the following signaling scheme (φ θ ) θ∈Θ with signals Σ = {σ 1 , σ 2 }. For each θ ∈ [n var ], we define φ θ (σ 1 ) = qx θ and φ θ (σ 2 ) = 1−φ θ (σ 1 ), where q = nvar(nvar−1) 1− nvar i=1x i . For θ = 0, we define φ 0 (σ 1 ) = 1 and φ 0 (σ 2 ) = 0. Then, the posterior distribution ξ σ 1 for signal σ 1 is for each θ ∈ [n var ] and ξ σ 1 (0) = 1 − nvar i=1x i . When σ 1 is observed, the expected weight of each element (t, a) ∈ E for the receiver can be calculated as For t ∈ [n eq ] with (Āx) t =c t , the receiver's expected utility of (t, a) is 1 for each a ∈ {a 0 , a 1 , a 2 }. For other t ∈ [n eq ], while the receiver's expected utility of (t, a 0 ) is 1, either (t, a 1 ) or (t, a 2 ) has a utility value greater than 1 and the other has a value smaller than 1. Under the uniform matroid constraint, the receiver selects the elements with the top-n eq expected utility values, and at most ζn eq elements have expected utilities greater than 1. Since we can break ties in favor of the sender, when σ 1 is observed, the receiver selects S ⊆ E that contains at most ζn eq elements (t, a) such that a = a 0 , i.e., at least (1 − ζ)n eq elements (t, a) ∈ S satisfy a = a 0 . Therefore, the expected utility of the sender is at least where the second inequality is obtained by letting n var be sufficiently large. Therefore, an α-approximation algorithm returns a signaling scheme with an expected utility greater than α(1 − 2ζ).
Soundness. We prove that if every vectorx ∈ Q nvar satisfies less than a δ fraction of the equations Ax = c, no algorithm for Bayesian persuasion with a uniform matroid constraint returns a signaling scheme with an expected utility more than or equal to δ. Suppose for contradiction that there exists a signaling scheme (φ θ ) θ∈Θ that provides the sender with an expected utility at least δ. We show there exists a vectorx ∈ Q nvar satisfying at least a δ fraction of the equationsĀx =c.
By an averaging argument, there exists a signal σ ∈ Σ such that the receiver's best response to σ yields the sender's expected utility that is at least δ. Let S * ⊆ E be this best response to σ, which contains elements with the top-n eq expected utility values. From the definition of the sender's utility, S * contains at least δn eq elements (t, a) such that a = a 0 . Let ξ σ ∈ ∆ Θ be the posterior probability distribution when σ is observed. The receiver's expected utility value for each element is Let T ′ = {t ∈ [n eq ] | nvar θ=1 ξ σ (θ)Ā tθ =c t } be the indices of the equations such that the receiver's expected utility values of (t, a 0 ), (t, a 1 ), and (t, a 2 ) are equal to 1. For t ∈ [n eq ] \ T ′ , while the receiver's expected utility of (t, a 0 ) is 1, one of the receiver's expected utility values of (t, a 1 ) or (t, a 2 ) is greater than 1 and the other is smaller than 1. Thus, S * contains n eq − |T ′ | elements whose expected utility is greater than 1 and |T ′ | elements whose expected utility equal to 1. Recall that S * contains at least δn eq elements (t, a) such that a = a 0 , whose expected utility is 1. Hence, we have δn eq ≤ |T ′ |. From the definition of T ′ , if we definex ∈ Q nvar so thatx θ = ξ σ (θ) holds for each θ ∈ [n var ], at least δn eq equations inĀx =c hold, hence a contradiction.

B.4 Proof for Graphic Matroid Constraints
We prove the hardness result for graphic matroid constraints. We use a reduction similar to the case of uniform matroids, but we need to construct an appropriate graph for obtaining the reduction.
For t ∈ [n eq ] with (Āx) t =c t , the receiver's expected utility For each of such t, since ties are broken in favor of the sender, the receiver selects a spanning tree consisting of {v t,1 , v t,2 }, {v t,0 , v t,1 }, and another edge. For t ∈ [n eq ] such that (Āx) t >c t , the expected utility values of {v t,0 , v t,2 } and {v t,1 , v t,3 } are greater than 1. For each of such t ∈ [n eq ], the receiver selects a spanning tree consisting of {v t,1 , v t,2 }, {v t,0 , v t,2 }, and {v t,1 , v t,3 }. Similarly, if (Āx) t <c t , then the expected utility values of {v t,0 , v t,3 } and {v t,2 , v t,3 } are greater than 1. For each of such t ∈ [n eq ], the receiver selects a spanning tree consisting of {v t,1 , v t,2 }, {v t,0 , v t,3 }, and {v t,2 , v t,3 }. Therefore, the expected utility of the sender is at least 1 − 2ζ as with the case of uniform matroids, where the second inequality is obtained by letting n var be sufficiently large. Hence, an α-approximation algorithm returns a signaling scheme with an expected utility greater than α(1 − 2ζ).

Soundness.
As with the case of uniform matroids, we prove by contradiction that if every vectorx ∈ Q nvar satisfies less than a δ fraction of the equations in Ax = c, no algorithm for Bayesian persuasion with a graphic matroid constraint returns a signaling scheme with an expected utility greater than or equal to δ.

B.5 Proof for Path Constraints
We prove the hardness result for path constraints. We again use almost the same reduction as the one used for uniform matroids, but we need to construct an appropriate graph and deal with the minimization setting.
Theorem 5. For any constant α ∈ [1, ∞), it is NP-hard to compute an α-approximate solution for Bayesian persuasion with a path constraint. We set weights of the other edges to zero, i.e., w θ (u t,i , v t ) = 0 for each t ∈ [n eq ], i ∈ {0, 1, 2}, and θ ∈ Θ. Using these weights, we define the receiver's cost of path S ⊆ E as r θ (S) = u, v). Define the sender's cost as Completeness. Supposex ∈ {0, 1} nvar to be a vector satisfying at least a 1 − ζ fraction of Ax = c and letx = 1 τx ; therefore, at most a ζ fraction ofĀx =c can be violated. We consider the same signaling scheme as the case of uniform matroids. When σ 1 is observed, for each t ∈ [n eq ], the expected weight of the edges for the receiver can be calculated as For t ∈ [n eq ] with (Āx) t =c t , the receiver's expected cost is identical for all of (v t−1 , u t,0 ), (v t−1 , u t,1 ), and (v t−1 , u t,2 ). Since we can break ties in favor of the sender, we can assume that the receiver selects (v t−1 , u t,0 ) and (u t,0 , v t ) for such t. On the other hand, for t ∈ [n eq ] such that (Āx) t =c t , the receiver selects either (v t−1 , u t,1 ) or (v t−1 , u t,2 ). Therefore, the expected cost of the sender is at most where the second inequality is obtained by letting n var be sufficiently large. Therefore, an α-approximation algorithm returns a signaling scheme with an expected cost at most αζ(1 + ζ).
Soundness. As with the case of uniform matroids, we prove by contradiction that if every vectorx ∈ Q nvar satisfies less than a δ fraction of the equations in Ax = c, no algorithm for Bayesian persuasion with path constraints returns a signaling scheme with an expected cost at most 1 − δ.
Suppose for contradiction that there exists a signaling scheme (φ θ ) θ∈Θ with which the sender incurs an expected cost at most 1 − δ. By an averaging argument, there exists a signal σ ∈ Σ such that the receiver's best response to σ yields the sender's expected cost at most 1 − δ. Let S * ⊆ E be this best response. Then, S * contains at most (1 − δ)n eq edges represented as (v t−1 , u t,1 ) or (v t−1 , u t,2 ) for some t ∈ [n eq ]. In other words, S * contains at least δn eq edges represented as (v t−1 , u t,0 ) for some t ∈ [n eq ]. Let ξ σ ∈ ∆ Θ be the posterior probability distribution when σ is observed. For each t ∈ [n eq ], the expected weight of each edge is Let T ′ = {t ∈ [n eq ] | nvar θ=1 ξ σ (θ)Ā tθ =c t } be the set of indices such that nvar θ=1 ξ σ (θ)Ā tθ =c t holds. For t ∈ [n eq ] \ T ′ , the receiver does not select (v t−1 , u t,0 ). Since S * contains at least δn eq edges represented as (v t−1 , u t,0 ) for some t ∈ [n eq ], it must hold that |T ′ | ≥ δn eq . If we definex ∈ Q nvar such thatx θ = ξ σ (θ) for each θ ∈ [n var ], then at least δn eq equations inĀx =c hold, hence a contradiction.

C.1 Proofs of the Equivalence of the LP Formulations
In this section, we prove the following proposition.
Proposition 6. There is a bijection between the feasible regions of (1) and (2) that does not change the objective value.
We first show that if S ∈ I is not one of the receiver's best responses for any posterior distribution ξ ∈ ∆ Θ , variable φ θ (S) never takes a non-zero value.
We then show that considering the first constraint θ∈Θ µ(θ)φ θ (S) (r θ (S) − r θ (S ′ )) ≥ 0 only for S ′ ∈ I * is sufficient. That is, although the reduced formulation (2) has the first constraint only for S ′ ∈ I * , any feasible solution to (2) also satisfies it for all S ′ ∈ I.
Proof. Fix any feasible solution (φ θ ) θ∈Θ to (2) and any S ∈ I * . From the first constraint of (2), it holds that for all S ′ ∈ I * . Since ξ ∈ ∆ Θ , if we let S * ∈ argmax S∈I θ∈Θ ξ(θ)r θ (S), then we have S * ∈ I * . For any S ′ ∈ I, we have where the first inequality is due to S * ∈ I * and (6), and the second inequality is due to the definition of S * .
From Propositions 18 and 19, any feasible solution to (1) can be converted to a feasible solution to (2) by removing variables corresponding to S ∈ I \I * , which are all zeros, and any feasible solution to (2) can be converted to a feasible solution to (1) by adding zero variables corresponding to S ∈ I \ I * . The latter is because thus obtained solution (φ θ ) θ∈Θ satisfies the first constraint of (1) for S ∈ I \ I * by making the left-hand side zero. Moreover, since the removed or added variables are all zeros, this conversion does not change the objective value. Therefore, Proposition 6 holds.

C.2 Proofs for Enumeration of the Best Responses
First, we prove the following lemma.
By using Lemma 8, we prove the following theorem.
From the construction of I C , there exists a maximum weight independent set S ′ ∈ I C for an interior point ξ ′ of C. Since bothξ and ξ ′ are interior points of C, the signs of θ∈Θξ (θ)(r θ ({i}) − r θ ({j})) and θ∈Θ ξ ′ (θ)(r θ ({i}) − r θ ({j})) are identical for every pair i, j ∈ E with i = j. Thus, the descending orders of the weights θ∈Θξ (θ)r θ ({·}) and θ∈Θ ξ ′ (θ)r θ ({·}) are also identical. Since the output of the greedy algorithm depends only on the descending order of the weights, we obtain S = S ′ . Hence, S ∈ I C , which leads to I * ⊆ I C .
Next, we provide an upper bound on |I C |. The set H contains one hyperplane for each pair distinct i, j ∈ E. Hence |H| = O(n 2 ). From the well-known fact that n hyperplanes decompose R d into O(n d ) cells (see, e.g., Edelsbrunner [1987]), we obtain |I C | = O(n 2d ).

D.1 Proof for Approximate Separation Oracles
We prove the following lemma.
Lemma 12. Under the assumption of Theorem 11, there is a polynomial-time α-approximate separation oracle such that for any {x θ } θ∈Θ and y, it either returns a separating hyperplane or guarantees the feasibility of {x θ /α} θ∈Θ and y/α.

D.2 On the Parameters of the Binary Search
As claimed in Theorem 11, Algorithm 2 needs v min and v max as inputs such that (i) OPT > 0 implies OPT > v min and (ii) OPT < v max , where OPT is the optimal value. We describe how to compute v min and v max for Algorithm 2 when s θ is an integer-valued monotone submodular function and r θ is an integer-valued gross substitute function for each θ ∈ Θ. We can deal with special cases where s θ or r θ is linear in the same way.
First, we consider how to set v max , which must upper-bound OPT. Let (φ θ ) θ∈Θ be any signaling scheme. Since the sender's expected utility is a linear combination of the sender's utility for each θ and S, we have θ∈Θ S∈I where the second inequality is due to submodularity of s θ . Thus, by setting v max > |E| max θ∈Θ max i∈E s θ ({i}), we obtain OPT < v max .