Information Design in Spatial Resource Competition
Pu Yang Krishnamurthy Iyer Peter Frazier

[
    David Soriano-Paños^1,2, Gourab Ghoshal^3,4, Alex Arenas ^5 and Jesús Gómez-Gardeñes^1,2
    September 2019; updated September 2020
============================================================================================





  We consider the information design problem in spatial resource
  competition settings. Agents gather at a location deciding whether
  to move to another location for possibly higher level of resources,
  and the utility each agent gets by moving to the other location
  decreases as more agents move there. The agents do not observe the
  resource level at the other location while a principal does and the
  principal would like to carefully release this information to
  attract a proper number of agents to move. We adopt the Bayesian
  persuasion framework and analyze the principal's optimal signaling
  mechanism design problem. We study both private and public signaling
  mechanisms. For private signaling, we show the optimal mechanism can
  be computed in polynomial time with respect to the number of
  agents. Obtaining the optimal private mechanism involves two steps:
  first, solve a linear program to get the marginal probability each
  agent should be recommended to move; second, sample the moving
  agents satisfying the marginal probabilities with a sequential
  sampling procedure.  For public signaling, we show the sender
  preferred equilibrium has a simple threshold structure and the
  optimal public mechanism with respect to the sender preferred
  equilibrium can be computed in polynomial time. We support our
  analytical results with numerical computations that show the optimal
  private and public signaling mechanisms achieve substantially higher
  social welfare compared with no information or full information
  benchmarks in many settings.










§ INTRODUCTION


We study information design in the spatial resource competition settings, where a group of agents migrate across a network of locations, competing for stochastic time-varying resources at each location. This setting characterizes many real world scenarios: on crowd-sourced transportation platforms, drivers migrate across different neighborhoods of a city, competing for ride demands; in unskilled labor markets, workers migrate across different cities for more job opportunities; in nomadic animal husbandry, pastoralists migrate across different range lands, competing for water and pastures, etc.


In these scenarios, information about other locations largely affects an agent's decision about whether to leave her current location, and where to explore. However, such information is usually limited or even unavailable to the agents. Meanwhile, in many cases, there is a principal who has access to more information than any individual agent, e.g., platforms such as Uber and Lyft in the ride sharing market, or the government agencies in labor markets, or non-profits in the case of pastoralists. Using this information, the principal can influence the decisions of the migrating agents, better locate them and improve the total social welfare. For example, Uber and Lyft show the demand trend at different neighborhoods as a heatmap to the drivers <cit.> in order to locate them to areas with higher demands, and government agencies provide information about employment and job openings in various sectors.  

However, sharing information may not always bring higher welfare, if the information is not released in a careful way: if a sports match or a concert at a stadium is about to finish and Uber informs every available driver in the nearby area, too many drivers may flood to this area, with many of them failing to find a customer due to over-supply. In such cases, it might be wiser for the platform to only inform a particular group of drivers to better match supply and demand. How to choose such a group? More generally, spatial resource competition scenarios typically exhibit negative externalities. In presence of such negative externalities, how should a principal effectively communicate her information to the agents in order to better position them?

Answering this question for a large network of locations is challenging: the effect of a signal that attracts a group of agents to a particular location may percolate across the entire network through agents' subsequent migration. On the other hand, signals can take very complicated forms in large networks, depending on many factors, including the number of locations and agents, the dynamics at each location, and the agents' belief about the state of the system and other agents' strategies. With the goal of obtaining insights to this spatial information design problem while retaining a tractable analysis, we consider a two-location model, which serves as a foundation for more complicated analysis.



 §.§ Overview of Model and Main Results


We consider a model with 2 locations, ℓ_0, ℓ_1, and N agents. Initially, all the agents are at ℓ_0, and must decide whether to move to ℓ_1, which has a stochastic resource. The utility each agent receives upon moving to ℓ_1 depends on the stochastic resource level at ℓ_1, as well as how many other agents move there. The agents do not know the resource level at ℓ_1 while a principal can observe it. The principal would like to design a mechanism to share this information to the agents in order to attract a proper number of agents to move to ℓ_1. 

We adopt the framework of Bayesian persuasion <cit.> to study this information design problem. The principal's goal is to choose a signaling mechanism that maximizes the expected social welfare, i.e., the total expected utility of the agents.  In this work, we consider both private signaling mechanisms, where the principal sends personalized signals to each agent privately, as well as public signaling mechanisms, where the principal sends the same information to all the agents.

The standard approach using a revelation-principle style argument <cit.> to find the optimal private signaling mechanism leads to a linear program in 2^N variables, rendering the computation challenging. Instead, our first main result in Section <ref> characterizes a computationally efficient two-step approach to find the optimal private signaling mechanism. First, we perform a change-of-variables and instead of the signaling mechanism, we focus on the marginal probabilities p_ik that an agent i is recommended to move to ℓ_1 along with k-1 other agents, for each i and k. We show that the marginal probabilities { p_ik}_i,k corresponding to the optimal private signaling mechanism can be found by solving a linear program in O(N^2) variables. Then, we describe an efficient sampling procedure that samples sets of agents according to the the optimal marginal probabilities {p_ik}_i,k. The optimal private signaling mechanism then asks the sampled set of agents to move to ℓ_1 and the rest to stay at ℓ_0. Finally, we provide a condition on the model parameters under which the optimal signaling mechanism has a simple threshold structure and can be computed in O(log N) time. 



Although private signaling mechanisms provide the principal more flexibility, a number of practical concerns often render private mechanisms infeasible <cit.>. First, private mechanisms make the strong assumption of no "information leakage" among the agents, i.e., the agents do not share their personalized information with each other. This assumption may easily fail in practice. Furthermore, fairness considerations may prevent a principal from sharing different information with different agents; a fair-minded principal may even seek to avoid the semblance of providing conflicting information to different agents. 

Owing to these reasons, in Section <ref>, we analyze the problem of finding the optimal public signaling mechanism, where the principal shares the same information with all the agents. To do this, we first characterize the equilibria of the incomplete information game among the agents subsequent to receiving any public signal. While the equilibrium set is quite complex, we show that for any common posterior belief of the agents, the equilibrium that maximizes the social welfare has a simple threshold structure. Using this result, we show that the optimal public signaling mechanism can be found as a solution to a linear program with O(N) variables and constraints. Furthermore, we show that the optimal mechanism only randomizes over two signals.





Finally, we numerically investigate the performance of the optimal private and public signaling mechanisms, and show that these achieve substantially higher social welfare than the no-information or full-information mechanisms. 

The main point of departure of our work from past literature on information design is the modeling of negative externality among the agents. Past work on information design has focused mainly on settings with no externalities <cit.> or settings where there is positive externalities among the agents <cit.>. In such settings, correlation among the agents' choice of action is beneficial, whereas the main challenge in our work is in de-correlating the agents' actions. This is especially challenging under public signaling, where public signals naturally tend to correlate the agents' actions. 

To conclude this section, we note that our approach for finding the optimal private signaling mechanism is not restricted to our model, but applies more broadly to settings where an agents' utility upon taking the action depends on the number of agents who take that action. Thus, our results on the computation of the optimal private signaling mechanism might be of independent interest to the research community. 










 §.§ Related Work


Our work focuses on information design in a resource competition scenario, adopting the Bayesian persuasion framework. We briefly survey here the related works on information design and Bayesian persuasion.

Information design problems on how a sender should persuade one or more receivers date back to <cit.> and <cit.>. The two mainstream frameworks studying this problem is the Bayesian persuasion framework, originating from <cit.> and the “cheap talk” model <cit.>, where the main difference is the former assumes the signal sender has the power to commit to a particular information sharing mechanism. 

<cit.> studies the basic setting with one sender and one receiver. <cit.> considers the more general “one sender, many receivers” setting and provide unified frameworks of deriving the optimal mechanism in such general settings. <cit.> considers a setting where multiple senders wish to influence one receiver. 

For general “one sender, many receivers” information sharing settings, tractable computation of the optimal mechanism remains an open problem. A lot of works have studied various special cases. <cit.> considered the simplest scenario: each receiver's action imposes no externalities on other agents. <cit.> characterize polynomial time computable optimal mechanisms when the sender's utility is supermodular or anonymous submodular. <cit.> provide an (1-1/e) optimal mechanism for general submodular sender utilities. For more general settings where agents' payoffs depend on other agents' actions,
 <cit.>
provides polynomial time computable optimal mechanism for binary action settings when the sender's utility is supermodular, and similar result is given in <cit.>. Both works point out that the optimal policy correlates recommendations to take the positive action as much as possible. Our work considers resource competition in settings where agents' actions have negative externalities, and to the best of our knowledge, is the first to study such settings. 

Information design and Bayesian persuasion are studied in many other settings, including voting <cit.>, ad auction <cit.>, 
online retailing <cit.>, bilateral trade <cit.>, advertising <cit.>, security games <cit.>, customer queues with delays <cit.>, Stackelberg competition between firms <cit.> and team formation <cit.>, etc. A more thorough  review of this topic can be found in <cit.>.
Beyond the one-time persuasion setting considered in most of the work we listed, several other works 
<cit.> considered the problem of sequentially persuading a group of agents.

 





§ MODEL AND PRELIMINARIES





 §.§ Model



We consider a model with N agents, a principal, and 2 locations,
denoted by ℓ_0 and ℓ_1. Initially, all the agents are at
location ℓ_0. There is a stochastic resource at ℓ_1, with
the resource level denoted by θ. We primarily focus on the
binary setting, with θ∈Θ{0, 1} capturing the
presence or absence of a resource; our model can be extended to the
case where Θ is a finite set. Without observing θ, each
agent at ℓ_0 independently decides whether or not to move to
ℓ_1, where she obtains a utility that depends on θ, as
well as the number of other agents who also choose to move to
ℓ_1. In addition, we assume that each agent incurs a moving cost
if she moves to ℓ_1. 




Formally, each agent i∈ [N] simultaneously chooses an action
a_i ∈{0, 1}, where a_i=0 implies the agent chooses to stay at
ℓ_0 and a_i = 1 implies she chooses to move to ℓ_1. Let
a = (a_i, a_-i) denote the profile of actions chosen by all the
agents, and A {0,1}^N denote the set of action
profiles. Note that for any a ∈ A, the number of agents that
choose to move to ℓ_1 is given by n(a) = ∑_i=1^N
a_i. Then, for any action profile a and any resource level
θ, an agent i's utility, U_i : Θ× A →,
is given by

    U_i(θ, a) =
      θ· F(∑_j=1^N a_j ) - r(i),    if a_i=1;
    
        0,    if a_i = 0.

Here, F: [N] →_+ is the resource sharing function that
determines how the resource at ℓ_1 is shared among the agents at
ℓ_1, and r(i) denotes agent i's moving cost. In particular,
an agent i who chooses to move to ℓ_1 receives an utility of
θ F(n(a)) from the resource, and incurs a cost r(i) for
moving. Furthermore, we have normalized the utility of staying at
ℓ_0 to be zero. Without loss of generality, we assume that r(i)
is increasing in i, i.e., r(1) ≤ r(2) ≤⋯ r(N). For
notational convenience, in the following, we let r(0) = 0 and
F(0) = F(1).










We make the following assumptions on the resource sharing function
F:
 The resource sharing function F(n) is decreasing
  and convex in n ≥ 1.  Furthermore, the total utility from the
  resource nF(n) is increasing and concave in n ≥ 0.

The first condition is meant to capture the fact that in most resource
sharing settings, the amount of resource each agent receives decreases
as competition increases, with the decrement diminishing with the
level of competition due to market saturation. On the other hand, the
second condition captures the fact that as the competition increases,
the total level of resource available to the agents also increases,
albeit also at a diminishing rate. This is especially common
in platform markets, where the presence of more agents on one side leads to
better service quality for the other side of the market, leading to
more conversion.



 












 §.§ Information structure


We assume that the principal and the agents hold a common prior belief
μ∈Δ(Θ) about the resource level θ, where
μ(1) denotes the prior probability that θ=1, and
μ(0) = 1 - μ(1). While the resource level θ is unobserved
by the agents, we assume that the principal observes θ prior to
the agents' choice of actions. The principal's goal is to communicate
this information about θ to the agents prior to their moving
decision, in order to better position them at the two locations. (We
describe the principal's objectives in more detail below.)

Following the methodology of Bayesian persuasion, the principal
commits to a signaling mechanism as a means to share information
with the agents. Formally, a signaling mechanism (Σ, ϕ)
consists of a signal set Σ and a signaling scheme
ϕ: Θ→Δ(Σ^N). Given a signaling mechanism
(Σ, ϕ) and upon observing the resource level θ, the
principal first chooses a signal profile
s = (s_1, ⋯, s_N) ∈Σ^N with probability
ϕ(s|θ) ∈ [0,1].  Then, the principal (privately) reveals
the signal s_i to agent i. In particular, s_i is not revealed to
an agent j ≠ i.

Note that ϕ(s|θ) denotes the conditional probability that
the signal profile is s, given the resource level is θ. In
particular, we have ∑_s ∈Σ^Nϕ(s|θ) = 1 for
each θ∈Θ.  Analogously, we define
ϕ(θ, s) = μ(θ) ϕ(s | θ) to be the unconditional
joint probability that the signal profile is s and the resource
level is θ. Finally, we let ϕ(s) denote the probability of
the principal selecting the signal profile s ∈Σ^N, given by
ϕ(s) = ϕ(0,s) + ϕ(1,s).



A special case of a signaling mechanism is a public signaling
mechanism, where the principal publicly announces the information
about θ to all the agents. In other words, the principal always
shares the same information with all the agents. Such public signaling
can be captured by a signaling mechanism (Σ, ϕ) where
ϕ(s|θ) =0 for any s ∈Σ^N with s_i ≠ s_j for
some i,j ∈ [N]. Finally, we refer to any signaling mechanism that
is not public as a private signaling mechanism.








 §.§ Strategies and equilibrium



Since an agent i does not have access to the signals of the other
agents, she maintains a belief over both the resource level θ
and the signals s_-i of the other agents. Upon receiving her
signal s_i from the principal, the agent updates her belief using
Bayes' rule, before deciding whether to move.  Let q_i(· | s_i)
denote posterior belief of agent i about the resource level and the
signals sent to other agents, given by

    q_i(θ, s_-i | s_i) = μ(θ)ϕ(s_i, s_-i | θ)/∑_θ', s'_-iμ(θ')ϕ(s_i, s'_-i | θ').

A strategy p_i : Σ→ [0,1] for agent i specifies, for each
possible signal s_i, the probability p_i(s_i) with which she
decides to move to location ℓ_1. Each agent, given her posterior
belief and the strategies p_-i of the other agents, seeks to
choose a strategy p_i that maximizes her expected utility. More
precisely, given a signaling mechanism (Σ, ϕ) and the
strategies p_-i of the other agents, the expected utility of an
agent i for moving to location ℓ_1 upon receiving a signal
s_i is given by

    u_i(s_i, 𝗆𝗈𝗏𝖾,  p_-i) = _q_i [ U_i(θ,a_i=1, a_-i) | a_-i∼  p_-i(s_-i)],

Then, in a Bayes-Nash equilibrium, each agent i, upon
receiving a signal s_i, decides to move to ℓ_1 if her expected
utility u_i(s_i, 𝗆𝗈𝗏𝖾, p_-i) is positive. We have the
following formal definition:

  Given a signaling mechanism (Σ, ϕ), a strategy profile
  (p_1, …, p_N) forms a Bayes-Nash equilibrium (BNE), if for
  each i ∈ [N] and s_i ∈Σ,
  
    p_i(s_i)    =  1    if u_i(s_i, 𝗆𝗈𝗏𝖾,
            p_-i) > 0;
    
          0    if u_i(s_i, 𝗆𝗈𝗏𝖾,
            p_-i) < 0.

  (If u_i(s_i,𝗆𝗈𝗏𝖾, p_-i) = 0, then
  p_i(s_i) ∈ [0,1].)





























As mentioned earlier, the principal's goal is to choose a signaling
mechanism to maximize the expected social welfare. Formally, the
social welfare W : Θ× A → is defined as

    W(θ, a) θ· n(a) ·  F(n(a))  - ∑_j=1^N a_j r(j).

Here the first term denotes the total utility obtained by the
n(a) = ∑_j=1^N a_j agents from the resource at ℓ_1, and
the second term denotes the total moving costs incurred by the
agents. We assume that the principal knows the agents' moving
costs. Then, the principal's decision problem is to choose a signaling
mechanism (Σ, ϕ) such that in a resulting Bayes-Nash
equilibrium (p_1, ⋯, p_N) among the agents, the expected social
welfare, given by
[ W(θ, a) | a_i ∼ p_i(s_i) , (θ, s) ∼ϕ],
is maximized. In the next section, we study the problem of computation
of the optimal signaling mechanism and characterize its
structure. Subsequently, in Section <ref>, we
analyze the related problem of optimal public signaling, where the
principal is restricted to sharing information via public signaling
mechanisms.








§ PRIVATE SIGNALING MECHANISM









From a standard revelation-principle style argument
<cit.>, there exists a
straightforward and persuasive signaling mechanism that optimizes the expected social welfare. In a straightforward mechanism, the principal makes an action recommendation to each agent, and if it is optimal for each agent to follow the recommendation (assuming all others do so), then the mechanism is said to be persuasive. Thus, to obtain an optimal private mechanism, it is sufficient to restrict our attention to persuasive straightforward mechanisms. This implies that it suffices for the principal to determine the subset of agents to recommend to move for each resource level. 

For θ=0,1 and S ⊆ [N], let ϕ(S |θ) be the probability of recommending the set S of agents to move to ℓ_1,  given resource level θ. We abuse the notation to let
 
    W(θ, S) θ |S|F(|S|) - ∑_i ∈ S r(i)

be the social welfare when resource level is θ and agents in S move to ℓ_1. The optimal signaling scheme ϕ is then obtained as solution to the following linear program:

    max_ϕ     ∑_θ=0,1μ(θ) ∑_ S ⊆ [N]ϕ(S |θ) W(θ, S) 
    
    s.t.      ∑_θ=0,1μ(θ) ∑_ S: i∈ Sϕ(S | θ)(θ F(|S|) - r(i)) ≥  0,    i ∈ [N],  
    [eq:lp-private](LP.1)   ∑_θ=0,1μ(θ) ∑_S: i∉ Sϕ(S | θ)(θ F(|S|+1) - r(i)) ≤  0,    i ∈ [N],  
       ∑_S ⊆ [N]ϕ(S | θ) = 1,   θ=0,1,  
       ϕ(S | θ) ≥ 0,   θ=0,1;  S ⊆ [N].

The first two sets of constraints ensure ϕ is persuasive: the first constraint states that any agent i who is recommended to move to ℓ_1 must have non-negative utility for moving, whereas the second constraint states that any agent i who is recommended to stay must have non-positive utility for moving. The other constraints ensure that ϕ(· | θ) is a valid probability distribution for both θ=0,1. Note that this linear program has O(2^N) variables, and is computationally challenging. As a first step towards simplifying the problem, we note the following lemma, which allows us to only consider mechanisms that recommend all agent to stay at ℓ_0 when θ=0.


For any persuasive mechanism, there exists another persuasive mechanism that recommends every agent to stay at ℓ_0 when θ=0, and achieves a higher social welfare than the original mechanism.


We provide proofs of all results in Appendix <ref>. Although Lemma <ref> reduces the size of <ref> by half, this linear program is still computationally challenging. However, taking a closer look at each agent's utility function, we notice that each agent i's payoff for moving when θ=1 depends only on how many other agents are moving. With this observation, we now consider an alternative formulation of <ref>.

Given a persuasive signaling scheme ϕ satisfying Lemma <ref>, i.e., ϕ(∅ | 0) = 1, we define p_ik to be the joint probability,  given θ=1, that this signaling scheme recommends k agents to move and agent i is among them, i.e., 

    p_ik = ∑_Sϕ(S | 1) ·{ i ∈ S, |S| = k}.

The following lemma allows us to write the objective and persuasive constraints of <ref> in terms of p={p_ik: i ∈ [N], k ∈ [N]}.


The objective (<ref>) of <ref> can be written as

    μ(1) ∑_k=1^N ∑_i=1^N p_ik(F(k)-r(i)),

and the persuasive constraints (<ref>), (<ref>) can be written as

    ∑_k=1^N p_ik(F(k)-r(i)) ≥ 0,     i∈ [N], 
       ∑_k=1^N-1(1/k∑_j=1^N p_jk -p_ik)(F(k+1) - r(i)) 
        + (1 - ∑_k=1^N 1/k∑_j=1^N p_jk)(F(1) - r(i))  ≤μ(0)/μ(1)r(i)  ,     i∈ [N].



Our main result in this section shows the converse is also true: 
given p={p_ik > 0: i ∈ [N], k ∈ [N]} satisfying persuasive constraints (<ref>) and (<ref>), with a few more linear constraints ensuring the p_ik's are valid joint probabilities, there exists a persuasive signaling scheme ϕ satisfying Lemma <ref> such that (<ref>) holds. Furthermore, there exists a polynomial time sequential sampling procedure that samples the set of agents to recommend to move as per the signaling scheme ϕ.





Assume p = {p_ik>0: i,k ∈ [N]} satisfies the persuasive constraints (<ref>) and (<ref>). If p further satisfies

    ∑_k=1^N 1/k∑_i=1^N p_ik≤ 1, [3]
        kp_ik≤∑_j=1^N p_jk,     k∈ [N], i∈ [N],



then there exists a persuasive signaling scheme ϕ such that ϕ(∅ | 0) = 1 and ϕ(· | 1) satisfies (<ref>).


Note that if p_ik is the joint probability that k agents are recommended to move to ℓ_1 and agent i is among them, then q_k 1/k∑_i=1^N p_ik
is the probability that k agents are recommended to move. Upon letting q_0 = 1 - ∑_k=1^N q_k, we note that (<ref>) ensures {q_k}_k=0^N is a valid probability distribution over {0, …, N}. On the other hand,
q_ikp_ik/q_k = kp_ik/∑_j=1^N p_jk
is the conditional marginal probability that agent i is recommended to move
given there are k agents asked to move, and (<ref>) ensures q_ik's are valid probabilities. To summarize, (<ref>) and (<ref>) requires for each k ∈ [N], the conditional marginal probabilities {q_ik}_i=1^N are in the k-uniform matroid polytope.

We briefly describe the sketch of the proof of Lemma <ref>, and omit the details due to space limit. The main idea is that there exists a sampling procedure that samples a set of agents such that for each i,k ∈ [N], p_ik is the probability that k agents are sampled and agent i is among them.  Specifically, this sampling procedure first samples the size k' of the output set according {q_k}_k=0^N. Following that, given any k' > 0, we adopt a sequential sampling subroutine presented by <cit.> to sample k' agents. This subroutine eliminates one agent from agents 1, …, N at each step, and ensures the probability a particular agent i still remains in the pool after each step is either 1, or strictly less than 1 while proportional to p_ik'. If (<ref>) is satisfied, when N-k' agents are eliminated, the probability each agent i remains in the output set is ensured by this subroutine to be q_ik, and the joint probability that k' agents are sampled and agent i is included is then p_ik'. We briefly describe this subroutine in Appendix <ref> and omit its details and proof of correctness, and refer interested readers to <cit.>. We then let ϕ(· | 1) be the probability distribution of the set sampled according to this procedure, and note that ϕ(· | 1) thereby satisfies (<ref>) and the persuasive constraints. 

Summarizing the preceding discussion, from Lemma <ref> and Lemma <ref>, to obtain the optimal private signaling mechanism, we first solve the following linear program <ref> to obtain the optimal solution p^*.

    max_p_ik: i, k ∈ [N]     ∑_k=1^N ∑_i=1^N p_ik(F(k)-r(i))  
    
    s.t.      ∑_k=1^N p_ik(F(k)-r(i)) ≥ 0,     i∈ [N],   
       ∑_k=1^N-1(1/k∑_j=1^N p_jk -p_ik)(F(k+1) - r(i)) 
    [lp:reformulate](LP.2)    + (1 - ∑_k=1^N 1/k∑_j=1^N p_jk)(F(1) - r(i))  ≤μ(0)/μ(1)r(i)  ,     i∈ [N], 
       ∑_k=1^N 1/k∑_i=1^N p_ik≤ 1, [3] 
        kp_ik≤∑_j=1^N p_jk,     k∈ [N], i∈ [N],  
        p_ik≥  0,    k∈ [N], i∈ [N],

After obtaining p^*, we sample the set of agents to recommend to move according to the following procedure given in Algorithm <ref>. Let ϕ^* be the persuasive signaling mechanism corresponding to p^* and Algorithm <ref>, as given by Lemma <ref>. ϕ^* must be feasible for <ref>. Furthermore, the objective corresponding to ϕ^* in <ref> is equal to that of p^* in <ref>. Therefore ϕ^* must be the optimal solution to <ref>, and is the optimal private signaling mechanism. 

Note that <ref> has N^2 variables and N^2+2N+1 constraints, therefore can be solved efficiently in polynomial time. The sequential sampling subroutine in <cit.> takes at most N steps to sample the set of agents to move, and in each step it takes polynomial time to determine which agent to eliminate. Therefore, the entire process to obtain the set of agents to recommend to move under the optimal private signaling mechanism can be completed in polynomial time.




We summarize our main result in this section as the following theorem.

The optimal private signaling mechanism can be computed by first solving <ref>, then sampling the set of agents to recommend to move according to Algorithm <ref>.


To conclude this section, we provide an observation that under certain conditions of modeling parameters, recommending the agents to follow the social optimal strategy profile is persuasive.  

Let W̃(n)  nF(n) - ∑_i=1^n r(i) be the social welfare when θ=1 and the first n agents move to ℓ_1. Since nF(n) is concave and r(i) is increasing in i, W̃(n) is also concave in n. Let i^* max{i: i ∈_0 ≤ i' ≤ NW̃(i') } be the largest maximizer of W̃.  In the following proposition, we show the strategy profile that all agents staying when θ=0, and the first i^* agents moving when θ=1, achieves the highest social welfare among all strategy profiles, and we give a sufficient condition under which recommending the agents to follow this strategy profile is persuasive.



If μ(1)  ≤ r(i^*+1)/F(i^*+1), then recommending all agents to stay when θ=0 and recommending the first i^* agents to move when θ=1 is an optimal persuasive mechanism.



Remark.  Note that r(i^*+1)/F(i^*+1) does not depend on
μ. Thus, this proposition gives an upper bound on μ(1) for
achieving the maximum possible social welfare using signaling mechanisms. In
Appendix <ref> we compute this upper bound for μ(1)
under several typical families of resource sharing functions and cost
structures. Also, since W̃ is concave, computing for i^*
takes only O(log N) time, reducing the computational time for the
optimal mechanism substantially compared with the general method.





§ PUBLIC SIGNALING MECHANISM



Having characterized the optimal private signals, we next consider the principal's problem under the restriction that the signaling mechanism be public. One reason for studying this restriction is that private signaling makes strong assumptions of no information leakage among the agents, an assumption that can easily fail in practice. Public signaling by construction avoids this information leakage concern. From a practical standpoint, restriction to public signaling can arise due to fairness requirements, where the principal seeks to avoid the semblance of providing conflicting information to different agents. 

A main technical difficulty in analyzing public signaling is the failure of the revelation principle argument<cit.>: it no longer suffices to optimize only over on straightforward and persuasive public mechanisms. To overcome this difficulty, we first note that in a public signaling mechanism, after any information transmission from the principal, all the agents have a common belief about the resource level θ, and participate in a Bayesian game under this common belief, where each agent simultaneously chooses whether to move to ℓ_1. Thus, we begin our analysis of public signaling mechanisms by first analyzing the structure of the equilibria of this Bayesian game under any common belief of the agents. 






 §.§ Equilibrium structure




Subsequent to receiving a public signal, let q ∈ [0,1] denote the common belief of the agents that θ = 1. The Bayes-Nash equilibrium of the subsequent game can be represented by a strategy profile p = (p_1, ⋯, p_N), where p_i denotes the probability that agent i chooses to move to ℓ_1. Our goal is to identify, for any common belief q ∈ [0,1], the equilibrium profile that achieves the highest expected social welfare, given by W(q,p) = q [W(1,a) | a ∼ p] = q [ n(a) F(n(a)) | a ∼ p] - ∑_i p_i r_i. 

We first note that the set of equilibria of this game can be quite complex. First, there can be a multiplicity of equilbria for any q ∈ [0,1], as the following example illustrates for an instance with 2 agents:

Example: Let N=2, F(1) = 1, F(2) = 0.6, r(1) = 0.5 and r(2) = 0.6. For q ∈ [0,0.5), the only equilibrium is p(q) = (0,0). For q ∈ [0.5, 0.6), the only equilibrium is p(q) = (1,0). For q ∈ [0.6, 5/6], there are three equilibria: p_1(q) = (1,0), p_2(q) = (0,1) and p_3(q) = ((5q-3)/2q,(10q-5)/4q). For q ∈ (5/6,1), there is a unique equilibrium (1,0) and for q=1, there are two equilibria, (1,0) and (1,1). 

Secondly, as the following proposition shows, the equilibria themselves have very counterintuitive features, where if multiple agents randomize, then the one with larger moving costs must move with a higher probability:


For an equilibrium profile (p_1, …, p_N) under a common belief q, let ⊆ [N] be the set of agents who randomize: {i ∈ [N]: 0 < p_i <1 }. For any agent i, j∈ where i < j, it must be that that p_i ≤  p_j.

While the preceding result goes counter to the intuition that agents with higher moving cost should be less likely to move, it is explained by the fact that in order for an agent with higher moving cost to be indifferent between moving and staying, it must be that she must find location ℓ_1 to be less competitive than the one with the lower moving cost, which implies that the one with the lower moving cost must move to ℓ_1 with lower probability. 

Despite the complexity of the equilibrium set, one can nevertheless consider a simple class of equilibria, namely the threshold equilibria, defined as follows:
 For common belief q ∈ [0,1], an equilibrium p = (p_1, ⋯, p_N) is said to be a threshold equilibrium, if there exists a t ∈ [0,N] such that

    p_i= 1,    if i < ⌈ t ⌉;
    
    t + 1- ⌈ t ⌉,    if i = ⌈ t ⌉;
    
    0,    if i> ⌈ t ⌉,

where ⌈ t ⌉ is the smallest integer that is greater than or equal to t. We denote such an equilibrium by (q,t).    

In a threshold equilibrium (q,t), at most one agent randomizes between moving and staying. Furthermore, all agents i < ⌈ t ⌉ move to ℓ_1, whereas all agents i > ⌈ t ⌉ stay at ℓ_0. Thus, threshold equilibria capture the intuition that agents with higher moving costs should move with lower probability. Our first result shows that, indeed, for any q ∈ [0,1], there exists a threshold equilibrium. Before we state our result, we define the following quantities for any common belief q:

    (q)    max{i ∈{0, …, N}: qF(i)  - r(i) ≥ 0}, 
    (q)    max{i ∈{0, …, N}: qF(i) - r(i) > 0}.
 
Note that q F(i) - r(i) denotes the expected utility of agent i for moving to location ℓ_1, if all agents j<i move to ℓ_1 and all agents j>i stay in ℓ_0. Thus, (q) denotes the agent with the largest moving cost who strictly prefers to move to ℓ_1, if all agents with smaller moving costs move, and those with larger moving costs stay. Similarly, (q) denotes the agent with the largest moving cost who does not strictly prefer to stay, under similar choices of other agents. Moreover, since F(i) is decreasing in i and r(i) is increasing in i, we have (q) ≥(q) for any belief q. Furthermore, since qF(0) - r(0) ≥ 0, we have (q) ≥ 0 and hence [(q) , (q)] ∩ [0,N] ≠∅. We have the following result:


For any q ∈ [0,1], and any t ∈ [0,N], (q,t) is a threshold equilibrium if and only if t ∈ [(q), (q)].

The preceding lemma guarantees the existence of threshold equilibria. The question then is how do threshold equilibria fare against other equilibria in terms of their expected social welfare. The following result, our main theorem of this section, establishes that for any common belief, the expected social welfare over all equilibria is attained at a threshold equilibrium.


For any common belief q ∈ [0,1], the expected social welfare W(q,p) under any equilibrium (q,p) is no more than that under the threshold equilibrium (q, (q)): 

    W(q, (q)) ≥ W(q,p),   for any equilibrium p.


The preceding theorem has the following implications: First, the expected social welfare is always maximized at a pure equilibrium (q, (q)): no agent strictly randomizes between moving and staying. Second, under the optimal public signaling mechanism (Σ, ϕ), for any signal s and the induced common belief q ∈ [0,1], it must be that the resulting equilibrium among the agents is (q, (q)). For otherwise, one can always (publicly) recommend the agents to move to this equilibrium and improve the expected social welfare. In the next section, we use these two facts to completely characterize the optimal public signaling mechanism as a solution to linear program.



 §.§ Optimal Public Signaling Mechanism


The results in the preceding section imply the following structure for the optimal public signaling mechanism: For each θ, the principal (publicly) recommends the threshold i number of agents to move to location ℓ_1, with the constraint that, under the induced common belief q upon receiving the recommendation i, it must be the case that (q) = i. This follows from an argument similar to the revelation-principle style argument for the private signaling mechanism, with the modification where the condition (q) = i plays the same role of the persuasive constraints. We omit the details due to its similarity to that of the private signaling case.

Thus, the public signaling mechanism can be described by choosing the signal set to be Σ = {0,⋯, N} and ϕ : Θ→Δ(Σ), where ϕ(i|θ) denotes the probability that the principal recommends the first i agents to move to ℓ_1 when the resource level is θ. The common belief upon sending a public signal s=i is then given by q_i = μ(1)ϕ(i|1)/ (μ(1) ϕ(i|1) + μ(0)ϕ(i|0)). The equilibrium constraint is thus (q_i) = i for each i ∈Σ. Note that the definition of (q) then implies that 

    q_i F(i) - r(i)    > 0
    
        q_i F(i+1) - r(i+1)    ≤ 0.

Finally, the expected social welfare is given by ∑_θ = 0,1μ(θ)  ∑_i=0^N ϕ(i|θ) W(θ, i), where W(θ,i) = θ iF(i) - ∑_j ≤ i r_j. 
Taken together, using the fact that q_i = μ(1)ϕ(i|1)/ (μ(1) ϕ(i|1) + μ(0)ϕ(i|0)) and letting ϕ(θ, i) = μ(θ)ϕ(i|θ), we obtain the following LP in ϕ:

    max_ϕ  ∑_θ =0, 1∑_i =0^N  W(θ, i) ·ϕ( θ,i)  
    s.t.  (F(i) - r(i))·ϕ(1,i) - r(i)·ϕ(0,i)    ≥ 0,     for all i ∈{1, ⋯, N};
    (F(i+1) - r(i+1))·ϕ(1,i) -r(i+1)·ϕ(0,i)    ≤ 0,   for all i ∈{0, ⋯, N-1};
    ∑_i =0, …, Nϕ(θ, i) = μ(θ),   ϕ(θ, i)    ≥ 0,   for θ =0, 1,  for all i ∈{0, ⋯, N}.

In (<ref>), the objective is the expected social welfare under ϕ. The first two sets of constraints encode (<ref>), ensuring that each signal i indeed induces the corresponding threshold equilibrium. (Note that since W(θ, i) is decreasing in i, the strict inequality in (<ref>) can be replaced by the weaker inequality without loss of optimality.) The last constraints ensure ϕ(· |θ) is a valid probability distribution for each θ. Note that the preceding LP has 2(N+1) variables and 2(N+1) constraints, and thus can be efficiently solved in polynomial time.

Remark. With a similar argument as that in <cit.>, one can show the optimal public signaling mechanism sends at most two signals with positive probabilities. That is, the optimal public signaling mechanism randomizes over two thresholds, with different weights for θ=0 and θ=1. Our results in this section can be easily extended to allow for larger state space Θ, with cardinality any finite K. In this case, the optimal public signal is the solution to a linear program with O(NK) number of variables and constraints, and the optimal public scheme sends at most K signals with positive probability.





































§ COMPUTATIONAL RESULTS












In this section, we compare numerically the social welfare under the optimal private and public signaling mechanisms with three benchmarks: the no-information benchmark, the full-information benchmark, and the social optimal benchmark, where all agents choose the social optimal action, that is, all agents stay when θ=0, and the first i^* agents move when θ=1 and i^* is defined earlier as the largest maximizer of W̃(n) = nF(n) - ∑_i=1^n r(i). Note the third benchmark may not be achievable through a signaling mechanism, but rather provides an upper bound for the social welfare any signaling mechanism can generate.

We consider three different resource sharing function F(i)=1/i^α for α=0.2, 0.5, 0.9. The parameter α controls the curvature of the resource sharing function, representing different resource sharing scenarios. We consider three different cost structures, constant costs where r(i)=0.5r, linear costs where r(i)=0.1ri and quadratic costs where r(i)=0.02ri^2, where r is the cost coefficient and we vary r to represent different cost functions. We compute the social welfare of the optimal mechanisms and the benchmarks for different resource sharing and cost functions and plot the results in Figure <ref>.

Numerical results in Figure <ref> show that the optimal private signaling mechanism generates a social welfare close to the social optimal benchmarks in most cases, and the optimal public signaling mechanism also generates social welfare higher than the full information or no information benchmark in most scenarios. The benefit of private signaling is high when agents have similar costs, as illustrated by the subplots in the first column. <cit.> and <cit.> show that when agents' actions have positive externalities, the optimal private mechanism should correlate the recommendations to take the positive action for every agent as much as possible. Here in our setting where agents' actions have negative externalities, a different phenomenon is observed: private signaling  de-correlates the agents' recommendations and generates more expected social welfare compared to public signaling where agents' actions are more correlated.



In Proposition <ref>, we give an upper bound for μ(1) under which the social optimal benchmark is achievable via private signaling. We also study numerically how much social welfare can be generated when this condition does not hold, by considering different priors. We presents these results in Appendix <ref>.







§ DISCUSSION



We consider information design in a two location resource competition model. For private signaling, we provide a method to compute the optimal mechanism in polynomial time, and also characterize a condition of model parameters under which the optimal mechanism has a simple threshold structure. For public signaling mechanisms, we characterize the structure of the socially optimal equilibrium and establish the form of the optimal public signaling mechanism. Numerical results show the optimal private and public signaling mechanisms increase the social welfare substantially compared with the no-information and full-information setting.

Readers may have noticed that our method for obtaining the optimal private signaling mechanism does not restrict to the resource sharing setting we are considering. In fact, it is applicable to all settings where the externality of each agent's action is anonymous (the utility of an agent depends only on how many other agents are taking the same action, but not on which agents are taking this action). Formally, for information design settings with binary action spaces where receiver i's utility has form f_i(a_i, ∑_j  i a_j) and the sender's utility has form f(∑_i a_i) + ∑_i g_i(a_i), our method can be used to obtain the optimal private signaling mechanism in polynomial time. Such utility functions can be found in many settings, for example, in most voting settings where the sender does not differentiate across voter.



Going beyond our model, in many spatial settings, there are more than two locations. The form of signals and the action and belief structure of the agents can be much more complicated. Fully solving the optimal signaling mechanism in such a system may be computationally intractable, while it is hopeful heuristic mechanisms with theoretical guarantee or good empirical performance on the social welfare generated may exist and is an interesting future research path. Meanwhile, in most settings, agents migrate among locations so signaling is not “one-shot” but rather a sequential and dynamic process, where signals sent at a time impact the actions and beliefs of agents ever since hence affect signals that should be sent later. The Bayesian persuasion framework does not extend naturally to these settings. Building models and analyze such dynamic signaling process is an important future path for better understanding real world spatial signaling problems.





10

alonso2016persuading
Ricardo Alonso and Odilon Câmara.
Persuading voters.
American Economic Review, 106(11):3590–3605, 2016.

arieli2019private
Itai Arieli and Yakov Babichenko.
Private bayesian persuasion.
Journal of Economic Theory, 182:185–217, 2019.

babichenko2016computational
Yakov Babichenko and Siddharth Barman.
Computational aspects of private bayesian persuasion.
arXiv preprint arXiv:1603.01444, 2016.

babichenko2017algorithmic
Yakov Babichenko and Siddharth Barman.
Algorithmic aspects of private bayesian persuasion.
In 8th Innovations in Theoretical Computer Science Conference
  (ITCS 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.

badanidiyuru2018targeting
Ashwinkumar Badanidiyuru, Kshipra Bhawalkar, and Haifeng Xu.
Targeting and signaling in ad auctions.
In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on
  Discrete Algorithms, pages 2545–2563. SIAM, 2018.

bardhi2018modes
Arjada Bardhi and Yingni Guo.
Modes of persuasion toward unanimous consent.
Theoretical Economics, 13(3):1111–1149, 2018.

bergemann2015limits
Dirk Bergemann, Benjamin Brooks, and Stephen Morris.
The limits of price discrimination.
American Economic Review, 105(3):921–57, 2015.

bergemann2016bayes
Dirk Bergemann and Stephen Morris.
Bayes correlated equilibrium and the comparison of information
  structures in games.
Theoretical Economics, 11(2):487–522, 2016.

bergemann2019information
Dirk Bergemann and Stephen Morris.
Information design: A unified perspective.
Journal of Economic Literature, 57(1):44–95, 2019.

caillaud2007consensus
Bernard Caillaud and Jean Tirole.
Consensus building: How to persuade a group.
American Economic Review, 97(5):1877–1900, 2007.

candogan2019persuasion
Ozan Candogan.
Persuasion in networks: Public signals and k-cores.
Available at SSRN, 2019.

candogan2017optimal
Ozan Candogan and Kimon Drakopoulos.
Optimal signaling of content accuracy: Engagement vs. misinformation.
Misinformation (October 11, 2017), 2017.

chakraborty2014persuasive
Archishman Chakraborty and Rick Harbaugh.
Persuasive puffery.
Marketing Science, 33(3):382–400, 2014.

crawford1982strategic
Vincent P Crawford and Joel Sobel.
Strategic information transmission.
Econometrica: Journal of the Econometric Society, pages
  1431–1451, 1982.

drakopoulos2018persuading
Kimon Drakopoulos, Shobhit Jain, and Ramandeep S Randhawa.
Persuading customers to buy early: The value of personalized
  information provisioning.
2018.

dughmi2017survey
Shaddin Dughmi.
Algorithmic information structure design: a survey.
15(2):2–24, 2017.

dughmi2017algorithmic
Shaddin Dughmi and Haifeng Xu.
Algorithmic persuasion with no externalities.
In Proceedings of the 2017 ACM Conference on Economics and
  Computation, pages 351–368. ACM, 2017.

farrell1987cheap
Joseph Farrell.
Cheap talk, coordination, and entry.
The RAND Journal of Economics, pages 34–39, 1987.

gentzkow2017bayesian
Matthew Gentzkow and Emir Kamenica.
Bayesian persuasion with multiple senders and rich signal spaces.
Games and Economic Behavior, 104:411–429, 2017.

grossman1981informational
Sanford J Grossman.
The informational role of warranties and private disclosure about
  product quality.
The Journal of Law and Economics, 24(3):461–483, 1981.

hssaine2018information
Chamsi Hssaine and Siddhartha Banerjee.
Information signal design for incentivizing team formation.
arXiv preprint arXiv:1809.00751, 2018.

kamenica2011bayesian
Emir Kamenica and Matthew Gentzkow.
Bayesian persuasion.
American Economic Review, 101(6):2590–2615, 2011.

kremer2014implementing
Ilan Kremer, Yishay Mansour, and Motty Perry.
Implementing the “wisdom of the crowd”.
Journal of Political Economy, 122(5):988–1012, 2014.

lingenbrink2017queue
David Lingenbrink and Krishnamurthy Iyer.
Optimal signaling mechanisms in unobservable queues with strategic
  customers.
In Proceedings of the 2017 ACM Conference on Economics and
  Computation, pages 347–347. ACM, 2017.

lingenbrink2018retail
David Lingenbrink and Krishnamurthy Iyer.
Signaling in online retail: Efficacy of public signals.
In Proceedings of the 13th Workshop on Economics of Networks,
  Systems and Computation, NetEcon '18, pages 10:1–10:1, New York, NY, USA,
  2018. ACM.

mathevet2017information
Laurent Mathevet, Jacopo Perego, and Ina Taneva.
On information design in games.
Unpublished paper, Department of Economics, New York
  University.[1115], 2017.

milgrom1981good
Paul R Milgrom.
Good news and bad news: Representation theorems and applications.
The Bell Journal of Economics, pages 380–391, 1981.

rayo2010optimal
Luis Rayo and Ilya Segal.
Optimal information disclosure.
Journal of political Economy, 118(5):949–987, 2010.

taneva2015information
Ina A Taneva.
Information design.
2015.

tille1996elimination
Yves Tillé.
An elimination procedure for unequal probability sampling without
  replacement.
Biometrika, 83(1):238–241, 1996.

ubersurge
Uber.
How surge pricing works, 2019.

wang2013bayesian
Yun Wang.
Bayesian persuasion with multiple receivers.
Available at SSRN 2625399, 2013.

xu2016signaling
Haifeng Xu, Rupert Freeman, Vincent Conitzer, Shaddin Dughmi, and Milind Tambe.
Signaling in bayesian stackelberg games.
In Proceedings of the 2016 International Conference on
  Autonomous Agents & Multiagent Systems, pages 150–158. International
  Foundation for Autonomous Agents and Multiagent Systems, 2016.

xu2015exploring
Haifeng Xu, Zinovi Rabinovich, Shaddin Dughmi, and Milind Tambe.
Exploring information asymmetry in two-stage security games.
In Twenty-Ninth AAAI Conference on Artificial Intelligence,
  2015.










§ PROOFS




 


Let ϕ be an arbitrary persuasive straightforward signaling scheme, where for any S ⊆ [N], ϕ(S | θ) is the probability of recommending agents in S to move, condition on resource state is θ. We construct another straightforward signaling scheme ϕ' where ϕ'(S | 1) = ϕ(S|1) for all S  ⊆ [N]; ϕ'(∅ | 0) = 1 and  ϕ'(S | 0) = 0 for all S ⊆ [N] and S {∅}. We would show ϕ' is also persuasive and achieves at least the same social welfare as ϕ. The expected social welfare under ϕ is

    ∑_θ=0,1, S ⊆ [N]μ(θ) ϕ(S | θ) W(θ, S)
    
    =    ∑_θ=0,1, S ⊆ [N]ϕ(θ, S) W(θ, S) 
    
    =   ∑_S ⊆ [N]ϕ(1, S) W(1, S) + ∑_S ⊆ [N]ϕ(0, S)W(0, S) 
    
    =   ∑_S ⊆ [N]ϕ(1, S) W(1, S) - ∑_S ⊆ [N]ϕ(0, S) ∑_i ∈ S r(i) [3]
    ≤   ∑_S ⊆ [N]ϕ(1, S) W(1, S) 
    
    =    ∑_S ⊆ [N]ϕ'(1, S) W(1, S) + ϕ'(0, ∅) W(0, ∅) 
    
    =    ∑_θ=0,1, S ⊆ [N]ϕ'(θ, S) W(θ, S),

which is the social welfare under ϕ'. 

Next, we show (Σ, ϕ') satisfies the persuasive constraints (<ref>) and (<ref>). For each agent i, since ϕ'(S | 0)=0 for S ∅ and ϕ'(S | 1)= ϕ(S | 1) for any subset S, we have

    ∑_θ, S: i ∈ Sϕ'(θ, S)(θ F(|S|) - r(i))  
    
    =    ∑_S: i ∈ Sϕ'(1, S)(F(|S|) - r(i))  
    
    =    ∑_S: i ∈ Sϕ(1, S)(F(|S|) - r(i)) [3]
    ≥     -r(i) ∑_S: i ∈ Sϕ(0, S) + ∑_S: i ∈ Sϕ(1, S)(F(|S|) - r(i)) 
    
    =    ∑_θ, S: i ∈ Sϕ(θ, S)(θ F(|S|) - r(i)) 
    ≥    0,

where the last inequality is because ϕ is persuasive. Therefore we have shown (<ref>) holds for agent i.

On the other hand, for each agent i, we have

    ∑_θ, S: i∉ Sϕ'(θ, S)(θ F(|S|+1) - r(i)) 
    
    =     -r(i) ∑_S: i ∉ Sϕ'(0, S) + ∑_S: i∉ Sϕ'(1, S)( F(|S|+1) - r(i)) 
    
    =     -r(i)μ(0) + ∑_S: i∉ Sϕ(1, S)( F(|S|+1) - r(i)) 
    ≤    -r(i) ∑_S: i ∉ Sϕ(0, S) + ∑_S: i∉ Sϕ(1, S)( F(|S|+1) - r(i)) 
    
    =    ∑_θ, S: i∉ Sϕ(θ, S)(θ F(|S|+1) - r(i)) 
    ≤     0,

where the first inequality is because ∑_S: i ∉ Sϕ(0, S) ≤μ(0), and the last inequality holds because ϕ is persuasive. Thus we have shown (<ref>) holds for agent i.



 


Let  be the random subset of agents recommended to move under ϕ. For each agent i, let X_i = 1{i ∈} be the random variable denoting that agent i is recommended to move.  Let  and  denote the probability measure and expectation induced by ϕ.


Since p_ik = (||=k, i ∈ | θ=1) = (||=k | θ=1) (i ∈ | ||=k, θ=1), 
and

    k = [∑_i=1^N X_i | ||=k, θ=1 ] = ∑_i=1^N [X_i | ||=k, θ=1]  = ∑_i=1^N(i ∈ | ||=k, θ=1),

we have 

    ∑_i=1^N p_ik = (|| = k | θ=1 ) ∑_i=1^N (i ∈ | ||=k, θ=1) = k (||=k | θ=1),

and therefore (||=k | θ=1) = ∑_i=1^N p_ik / k.
 
The objective (<ref>) of <ref> can be written as
[1]

    μ(0) ∑_ S ⊆ [N]ϕ(S |θ) W(0, S) +  μ(1) ∑_ S ⊆ [N]ϕ(S |θ) W(1, S) 
    
    =    μ(0)ϕ(∅ | 0)W(0, ∅) + μ(1)∑_ S ⊆ [N]ϕ(S|1) (|S| F(|S|) -∑_i ∈ Sr(i) ) 
    
    =    μ(1) ∑_k=1^N ∑_S :|S|=kϕ(S|1) (k F(k) -∑_i ∈ Sr(i) )
    
    =    μ(1)∑_k=1^N kF(k)∑_S: |S|=kϕ(S|1) - μ(1) ∑_k=1^N ∑_S : |S|=kϕ(S|1) ∑_i ∈ S r(i) 
     
    =    μ(1)∑_k=1^N kF(k)(||=k | θ=1) - μ(1) ∑_k=1^N  ∑_i=1^N r(i) ∑_S: |S|=k, i∈ Sϕ(S|1) 
    
    =    μ(1) ∑_k=1^N kF(k) ∑_i=1^N p_ik/k - μ(1) ∑_k=1^N ∑_i=1^N r(i) p_ik
    
    =    μ(1) ∑_k=1^N ∑_i=1^N p_ik(F(k) - r(i)).

 
Next, we write the persuasive constraints in terms of the p_ik's. For each agent i, the left hand side of (<ref>) can be written as 

    ∑_θ=0,1μ(θ) ∑_ S: i∈ Sϕ(S | θ)(θ F(|S|) - r(i))
    
    =    μ(1) ∑_S : i ∈ Sϕ(S | 1)(F(|S|)- r(i)) 
    
    =    μ(1) ∑_k=1^N ∑_S : |S|=k, i ∈ Sϕ(S|1)(F(k)-r(i)) 
    
    =    μ(1) ∑_k=1^N(F(k)-r(i)) ∑_S : |S|=k, i ∈ Sϕ(S|1)
    
    =    μ(1) ∑_k=1^N p_ik(F(k)-r(i)).

Therefore for agent i, constraint (<ref>) is equivalent as

    ∑_k=1^N p_ik(F(k) - r(i)) ≥ 0.

On the other hand, for each agent i, the left hand side of (<ref>) can be written as 

    ∑_θ=0,1μ(θ) ∑_S: i∉ Sϕ(S | θ)(θ F(|S|+1) - r(i)) 
    
    =     -μ(0)r(i) + μ(1)∑_S: i∉ Sϕ(S | 1)( F(|S|+1) - r(i)) 
    
    =      -μ(0)r(i) + μ(1) ∑_k=0^N-1∑_S: |S|=k,  i∉ Sϕ(S|1) (F(k+1) - r(i)) 
    
    =     -μ(0) r(i) + μ(1)∑_k=0^N-1( ∑_S: |S|=kϕ(S|1) (F(k+1) - r(i)) - ∑_S: |S|=k, i ∈ Sϕ(S|1) (F(k+1) - r(i)) ) 
    
    =     -μ(0) r(i) + μ(1)∑_k=0^N-1 (F(k+1) - r(i)) ∑_S: |S|=kϕ(S|1)  - μ(1)∑_k=1^N-1  (F(k+1) - r(i)) ∑_S: |S|=k, i ∈ Sϕ(S|1) 
    
    =     -μ(0) r(i) + μ(1)∑_k=0^N-1 (F(k+1) - r(i))(||=k | θ=1) - μ(1)∑_k=1^N-1  (F(k+1) - r(i)) p_ik
    
    =     -μ(0) r(i) - μ(1)∑_k=1^N-1  (F(k+1) - r(i)) p_ik  + μ(1)∑_k=1^N-1 (F(k+1) - r(i))(||=k | θ=1) 
        + μ(1)(F(1) - r(i))(||=0 | θ=1) 
    
    =    -μ(0) r(i) + μ(1)∑_k=1^N-1  (F(k+1) - r(i))((||=k | θ=1) - p_ik) 
        + μ(1)(F(1) - r(i))(1  -∑_k=1^N (||=k|θ=1) ) 
    
    =     -μ(0) r(i) + μ(1)∑_k=1^N-1  (F(k+1) - r(i))(∑_i=1^N  p_ik/k  - p_ik) 
        + μ(1)(F(1) - r(i))(1  -∑_k=1^N ∑_i=1^N  p_ik/k) 
    
    =     -μ(0) r(i) +μ(1) ((1 - ∑_k=1^N 1/k∑_j=1^N p_jk)(F(1) - r(i))  +∑_k=1^N-1(1/k∑_j=1^N p_jk -p_ik)(F(k+1) - r(i)) .

Therefore for agent i, constraint (<ref>) is equivalent as

    -μ(0)r(i) + μ(1) ((1 - ∑_k=1^N 1/k∑_j=1^N p_jk)(F(1) - r(i))  +∑_k=1^N-1(1/k∑_j=1^N p_jk -p_ik)(F(k+1) - r(i)) ) ≤ 0





 


For any k > 0, <cit.> presents a sequential elimination subroutine that eliminates one agent from agents 1, …, N at each step, and outputS the remaining k agents, ensuring the probability each agent i is included in the sample is kp_ik/∑_j=1^N p_jk, so long as (<ref>) holds for p_ik's.

Specifically, at each step n=N-1, N-2, …, k, this subroutine computes π(i | n) for each i ∈ [N] in the following way. It first computes for each i the quantity

    np_ik/∑_j=1^N p_jk .

For each agent i such that this quantity is larger than 1, it assigns this quantity to π(i | n). It then recomputes this quantity for remaining agents, with the multiplier in the numerator being the number of remaining agents instead of n. This process is repeated until for all i ∈ [N], π(i| n) is in [0, 1]. After this process, some π(i | n) is equal to 1 and others are strictly proportional to p_ik.

This subroutine then computes for each i ∈ [N]

    r_ni = 
         1 - π(i|n),    if n=N-1;
    
        1 - π(i|n)/π(i | n+1),    if n < N-1.


For each n, let S_n be the set of remaining agents at the beginning of step n, it can be verified {r_ni}_i ∈ S_n is a valid probability distribution, and this subroutine samples one agent according to this distribution and eliminate this agent from the pool. If (<ref>) holds, this subroutine ensures after the final step k, the probability each agent i is included in the sample is kp_ik/∑_j=1^Np_jk = q_ik.

The rest of the proof of this lemma is given in the main paper.



 
















 


First we show F(i^*) ≥ r(i^*). This claim holds trivially when i^*=0. Assume i^* ≥ 1 and assume for contradiction F(i^*) < r(i^*). We have

    W̃(i^*) - W̃(i^*-1) 
    
    =      i^*F(i^*) - ∑_j=1^i^* r(j) - (  (i^*-1)^*F(i^*-1) - ∑_j=1^i^*-1 r(j) ) 
    
    =     (i^*-1)(F(i^*) - F(i^*-1)) + F(i^*) - r(i^*) 
    ≤    F(i^*) - r(i^*) 
    
    <     0.

Therefore i^* is not maximizer of W̃, leading to a contradiction.

Let x be the probability distribution over the subsets of [N] such that x({1, …, i^*})=1 and x(S)=0 for any other S ⊆ [N]. To show recommending the agents to follow the social optimal strategy profile is persuasive, it suffices to show x satisfies the constraints of the linear program <ref>.

For agent i ≤ i^*, x(S) = 0 for all S such that i ∉ 
S so the second constraint in <ref> is satisfied. Also,

    ∑_S: i ∈ S x(S)(F(|S|)  -r(i)) =  x({1, …, i^*})(F(i^*) - r(i))
     =  F(i^*) - r(i)  
     ≥  F(i^*) - r(i^*) ≥ 0,
 
hence the first constraint is also satisfied.

On the other hand, for agent i > i^*, x(S) = 0 for all S such that i ∈ S so the first constraint in <ref> is satisfied. Also,

    ∑_S: i ∉ S x(S)(F(|S|+1)  -r(i)) 
    
     =     F(i^*+1) - r(i) 
    ≤     F(i^*+1) - r(i^*+1) [3]
    ≤   r(i^*+1)/μ(1) - r(i^*+1) 
    
    =     μ(0)/μ(1)r(i^*+1)
    ≤   μ(0)/μ(1)r(i),

so the second constraint is satisfied. Therefore x is persuasive. 

The social welfare corresponding to x is μ(1)W̃(i^*). Note that for any S ⊆ [N], 

    |S|F(|S|) - ∑_i ∈ S r(i) ≤ |S|F(|S|) - ∑_i=1^|S| r(i) = W̃(|S|) ≤W̃(i^*).

Therefore for any signaling scheme ϕ, the social welfare with respect to ϕ is 

    μ(0) ∑_S ⊆{[N]}ϕ(S | 0) (-∑_i ∈ S r(i) )+  μ(1)∑_S  ⊆ [N]ϕ(S | 1)(|S|F(|S|) - ∑_i ∈ S r(i)) 
    ≤   μ(1) ∑_S  ⊆ [N]ϕ(S|1) W̃(i^*) 
    ≤   μ(1)W̃(i^*),

hence x gives the optimal signaling mechanism.






Since agent i is randomizing between moving and staying in equilibrium, assuming all other agents follow the given strategy profile, she should be indifferent in moving and staying, hence the expected payoff for agent i choosing to move should be equal to r(i). Let N_-ij be the number of agents who choose to move besides agent i and j, we have 

    q(p_j[F(N_-ij+2)] + (1-p_j)[F(N_-ij+1)]) = r(i) 
    ⇒    p_j = [F(N_-ij+1)]- r(i)/q/[F(N_-ij+1) - F(N_-ij+2)] .

Similarly, agent j is indifferent in moving and staying given other agents' strategies, which gives 

    p_i = [F(N_-ij+1)]- r(j)/q/[F(N_-ij+1) - F(N_-ij+2)] .

Since F is decreasing, [F(N_-ij+1) - F(N_-ij+2)] > 0 and r(i) ≤ r(j) implies p_i ≤ p_j.







For any t ∈ [(q), (q)], let p = t + 1 - ⌈ t ⌉. We consider the utility for each agent i choosing to move assuming all other agents follow their strategy in the threshold equilibrium.

For i < ⌈ t ⌉, agent i' s expected utility for moving is 

    q(pF( ⌈ t ⌉ ) + (1-p)F(⌈ t ⌉ -1)) ≥ qF( ⌈ t ⌉ )≥ F((q)) ≥ r((q)) ≥ r(i),

hence she has no incentive to alter her strategy in the threshold equilibrium. 

For agent ⌈ t ⌉, her expected utility for moving is qF(⌈ t ⌉ ). If t > (q), we have (q) < ⌈ t ⌉≤(q), and by definition of (q) and 
(q), we have qF(⌈ t ⌉ ) = r(⌈ t ⌉) so agent ⌈ t ⌉ would not alter her strategy. On the other hand, if t =(q), by definition of (q) we know agent ⌈ t ⌉ would also choose to move, same as her strategy in the threshold equilibrium.

Finally, for agent i > ⌈ t ⌉, her expected utility for moving is q(pF( ⌈ t ⌉ +1) + (1-p)F( ⌈ t ⌉ )). In the case t > (q), this utility is upper bounded by qF( ⌈ t ⌉ ) ≤ qF((q)+1); and in the case t = (q), we have p=1 and the utility for moving is also qF((q)+1). We have
qF((q)+1) ≤ r((q)+1) ≤ r(i) so agent i would not alter her equilibrium strategy, which completes the proof for (i).

The “only if” part is straightforward and we omit the details. 













We first prove the following lemma.



W(q, n) is concave in n and W(q, (q)) ≥ W(q, (q)+1).


Concavity is straightforward since nF(n) is concave and r(i)'s are increasing in i so -∑_i=1^n r(i) is also concave. To show W(q, (q)) ≥ W(q, (q)+1), we have

    W(q, (q)+1) - W(q, (q)) 
    
    =       q((q)+1)F((q)+1) - ∑_i=1^(q)+1 r(i) - ( q(q) F((q)) - ∑_i=1^(q) r(i) ) 
    
    =    q(q)(F((q)+1) - F((q))) + qF((q)+1) - r((q)+1) 
    ≤     0,

where the inequality is from qF((q)+1) ≤ r((q)+1) and F is decreasing.



Let p=(p_1, …, p_N) be an arbitrary equilibrium strategy profile under belief q. Define ,  and  as: {1 ≤ i ≤ N: p_i=1}, {1 ≤ i ≤ N: p_i=0} and {1 ≤ i ≤ N: 0 < p_i <1}, denoting the agents who moves, stays and randomizes between moving and staying. Recall W(q, p) denote the principal's expected utility with respect to belief q and  this strategy profile. We aim to show W(q, p) ≤ W(q, (q)).

We have

    W(q, p) =    ∑_S ⊆∏_j ∈ S p_j ∏_ j ∈\ S (1-p_j) ( q(|S| + ||)F(|S| + ||) - ∑_j ∈∪ S r(j))
    ≤   ∑_S ⊆∏_j ∈ S p_j ∏_ j ∈\ S (1-p_j) ( q(|S| + ||)F(|S| + ||) - ∑_j =1^|| + |S| r(j)) [3] 
    
    =    ∑_n=0^||( q(|| + n)F(|| + n) - ∑_j=1^||+nr(j) ) ∑_S ⊆: |S|=n∏_j ∈ S p_j ∏_ j ∈\ S (1-p_j)
    
    =   ∑_n=0^|| W(q, || + n)  ∑_S ⊆: |S|=n∏_j ∈ S p_j ∏_ j ∈\ S (1-p_j) .


The inequality is from that r(i)'s are increasing in i. Let X be the number of agents in  that chooses to move. The right-hand side of the last equality of (<ref>) equals [W(q, ||+X)]. Since W is concave, by Jensen's inequality we have 

    [W(q, ||+X)] ≤ W(q, || + [X]).

Therefore, U(p_1, …, p_N) ≤ W(q, || + [X]). Next, we show ||  + [X] ≥(q) in Lemma <ref>. 



 ||  + [X] ≥(q).



Define G(n)  qF(n) , n ∈ [N]. Since G is convex, by Jensen's inequality, we have

    G(|| + [X] + 1) ≤[G(|| + X+ 1)].


For any agent i ∈, her expected utility if she chooses to move is [G(|| + X+ 1)]. Since she prefers staying, we have [G(|| + X+ 1)] ≤ r(i). On the other hand, for any agent i ∈, let X^(i) denote the number of agents in  besides agent i who chooses to move. Agent i's expected utility if she chooses to move is [G(|| + X^(i) + 1)]. Since agent i is indifferent in moving and staying, we have [G(|| + X^(i) + 1)] = r(i). Clearly X^(i) X where “𝗌𝖽” denotes first-order stochastic dominance, and since G is a decreasing function, we have G(|| + X+ 1)  G(|| + X^(i) + 1). Therefore [G(|| + X+ 1)] ≤[G(|| + X^(i) + 1)] = r(i). Summarizing the above, we have

    [G(|| + X+ 1)] ≤min_i ∈∪ r(i).

Let j min∪ and we show it must hold that j ≤(q). Assume, for contradiction, j > (q). First observe that since j is the agent in ∪ with the smallest index, it must hold j ≤ || + 1, which implies || ≥ j-1 ≥(q). 
Meanwhile, if j ∈, we have r(j) = [G(|| + X^(j) + 1)] ≤ G(||+1); and if j ∈, we have r(j) ≤[G(|| + X + 1)] ≤ G(||+1). Therefore, 

    r((q)+1) ≤ r(j) ≤   G(|| + 1) ≤ G((q)+1) .

However by definition of (q) it must be that G((q)+1) < r((q)+1), which leads to a contradiction. 

From j ≤(q), along with (<ref>) and (<ref>), we have 

    G(|| + [X] + 1) ≤[G(|| + X+ 1] ≤ r(j) ≤ r((q)).

By definition of (q) we have G((q)) ≥ r((q)). In the case G((q)) > r((q)), we have G((q))  > G(|| + [X] + 1) hence || + [X] + 1> (q) since G is decreasing. Note when G((q)) > r((q)), (q) = (q), so we have  || + [X] ≥(q). On the other hand, if G((q)) = r((q)), we have (q) < (q) so || + [X] + 1≥(q) > (q) and we also get || + [X] ≥(q). 


By Lemma <ref>, W(i) is decreasing on i ≥(q). Since ||  + [X] ≥(q) we have 
W(q, || + [X]) ≤ W(q, (q)). Along with (<ref>), (<ref>) and Lemma <ref> we have

    W(q,p) ≤[W(q, || + X)] ≤ W(q, | + [X]) ≤ W(q, (q)),

completing the proof.





§ UPPER BOUND OF TEXT




In this section, we compute the upper bound r(i^*+1)/F(i^*+1) for μ(1) given in Proposition <ref>, which ensures recommending the agents following the social optimal strategy profile is persuasive, for several typical resource sharing functions and cost structures.

Specifically, we consider cost function F(i) =1/i^α for α=0.2, 0.4, 0.6, 0.8, with different α controlling the curvature of F and representing different resource sharing scenarios. We consider 3 different cost structures: constant costs , linear costs, and quadratic costs. We fix the total number of agents N=20 since i^* does not depend on N. The result is given in Table <ref>.









§ ADDITIONAL COMPUTATIONAL RESULTS



In this section, we present computational results on how much social welfare can be generated by the optimal private and public signaling mechanism under different priors. We consider three different resource sharing function F(i)=1/i^α for α=0.2, 0.5, 0.9; and three different cost structures: constant costs where r(i)=0.5r, linear costs where r(i)=0.1ri and quadratic costs where r(i)=0.02ri^2, and r is the cost coefficient. The results are given in Figure <ref>.









