# Information Design for Spatial Resource Allocation

Ozan Candogan
University of Chicago, Booth School of Business,
<EMAIL_ADDRESS>Manxi Wu
Cornell University, Operations Research and Information Engineering,
<EMAIL_ADDRESS>

###### Abstract

In this paper, we study platforms where resources and jobs are spatially
distributed, and resources have the flexibility to strategically move to
different locations for better payoffs. The price of the service at each
location depends on the number of resources present and the market size, which
is modeled as a random state. Our focus is on how the platform can utilize
information about the underlying state to influence resource repositioning
decisions and ultimately increase commission revenues. We establish that in
many practically relevant settings a simple monotone partitional information
disclosure policy is optimal. This policy reveals state realizations below a
threshold and above a second (higher) threshold, and pools all states in
between and maps them to a unique signal realization. We also provide
algorithmic approaches for obtaining (near-)optimal information structures
that are monotone partitional in general settings.

Keywords:  Information design, spatial resource allocation, monotone
partitional information mechanisms.

##  1 Introduction

In many operational settings, resources that serve jobs are spatially
distributed, and mismatch between the locations of jobs and resources causes
inefficiencies. To complicate things further, in recent years, platforms where
resources are self-interested independent contractors have become prevalent.
In these platforms the resources decide whether or not to provide service and
how to relocate from one region to another. This may further exacerbate the
spatial frictions increasing the aforementioned inefficiencies. Such dynamics
are common and increasingly relevant in many platforms, including ride-sharing
platforms (such as Uber and Lyft), online freight marketplaces (such as Convoy
and Uber Freight), food delivery services (such as DoorDash and GrubHub), and
other last mile delivery services (such as Amazon Flex, Gopuff, and
Instacart).

To combat the mismatch of supply and demand in settings with self-interested
resources, platforms have taken two main approaches. The first, “market
driven”, approach relies on offering different prices for services that take
place in different locations. Surge pricing that is common in ride-sharing is
an example, and in fact such spatial price differences predate platforms and
have been employed in freight brokerage industry while determining freight
rates. The second approach involves sharing information with the resources
about the spatial distribution of jobs, so that the resources can reposition
themselves to locations that are in need of additional resources. A common
example of such a lever is an heat map that designates the regions that have
the highest amount of unfilled jobs (see Figure 1(a)). Another related version
combines this approach with the first one, and highlights regions where the
demand is high relative to supply, and service prices are surging, as well as
how much they are surging (see 1(b)). A third version does not explicitly
state how much the prices are surging, but only designates the regions where
the prices are surging, and in effect the high/low demand regions, leaving the
inference on price changes to the resources (in this case the drivers; see
Figure 1(c)).111It is worth noting that firms have experimented with different
versions of these ideas, and not only that different versions of these heat
maps are in use by different firms, but also over the years some firms have
switched back and forth between different alternatives.

(a) Grubhub

(b) Doordash

(c) Uber

Figure 1: Examples of heat maps used by different platforms.

The recent literature has explored in depth how platforms should design
spatial price discrimination policies to improve their profits, or mitigate
inefficiencies (see, e.g., Bimpikis et al. (2019); Banerjee et al. (2022)).
However, the question of leveraging information to influence the decisions of
self-interested resources has not received as much attention. The objective of
this paper is to close this gap in the literature, offer a framework for using
information as a lever for spatial resource allocation, and shed light on when
different types of practically-relevant information structures are relevant.

To that end, we focus on an undirected network model where each node
corresponds to a different location. Nodes are initially endowed with a set of
resources, which can reposition from their original node to another node. The
edges connect pairs of nodes between which the resources can reposition, and
are associated with cost terms that capture the cost a resource incurs when it
repositions from one end point to the other end point of the edge. The number
of available resources in each region after possible repositioning decisions,
impacts the service price. In practice, the service price in a location is
also influenced by the demand shocks in this location. Our model accommodates
this, by allowing for random shocks (which we refer to as the state) that
shift the price curve in a location. The platform can commit to a mechanism
that shares information about the aforementioned shocks once they are
realized. For instance, the realization of the shock can be fully revealed, or
the platform can reveal whether the realization is below or above a threshold,
or it can employ other alternatives.

The platform collects a commission for facilitating matches between the
resources and the jobs, which is modeled as a constant fraction of the
generated revenues. The resources are self-interested and they try to maximize
their payoffs (payment received for providing service minus commission and
relocation costs). Thus, revealing information appropriately, influences the
resources’ repositioning decisions, and, in turn, the induced service prices
and the platform’s revenue. We investigate how the platform can maximize its
revenue by using appropriate information structures. In the context of the
applications mentioned earlier, this question can be equivalently cast as the
question of designing heat maps (which assign different demand levels to
different signal realizations) that maximize the platform’s revenue.222In
terms of the examples in Figure 1, our setting is closer to (a) and (c) – the
platform sends signals about the demand shocks, without explicitly revealing
the impact on prices. That said, in our equilibrium model, the drivers can
infer the implied expected service price. Thus, revealing price information in
a consistent way as in (b) could also be accommodated in our model.

Our first contribution is a characterization of the equilibrium repositioning
decisions of resources. We show that these can be obtained by solving a simple
convex (in fact quadratic) optimization problem. This characterization is made
possible through a connection to potential games, and applies for any shock
realization profile, including shocks that impact multiple nodes.

We then use this result to explore when _monotone partitional mechanisms_ are
optimal. These mechanisms partition the state space into subintervals, and for
each subinterval either (i) pool all of the states in this subinterval and map
them to a unique signal, or (ii) reveal the state. We focus on these
mechanisms for two reasons. The first reason is their practical relevance.
They allow for grouping states to low/medium/high regions and simply reveal
the region to which the state realization belongs – which is consistent with
the way the heat map examples in Figure 1 work. Second, perhaps surprisingly,
we show that this class of mechanisms is in fact optimal under fairly general
and practically relevant assumptions.

To obtain the latter insight, we focus on a setting where there is a single
node that is exposed to shocks, and impose two regularity conditions: The
first requires an initial “demand balance” condition which ensures that pre-
shock the supply is distributed in a way that induces identical prices at all
locations. The second condition requires no market depletion: i.e., the shock
is not so large (resp. small) that all the resources in a non-shock (resp.
shock) location will leave their location leaving zero resource available in
that location.

Our main theorem establishes the optimality of monotone partitional mechanisms
under practically relevant conditions on the market sizes of different
locations (characterized in terms of the intercepts of the price curves).
Specifically, we study the change in the market sizes relative to the change
in the distance from the shock center. If the ratio of these quantities,
hereafter the market size change rate, is small, we say that the market sizes
are similar relative to distances. More formally, we require the absolute
value of the aforementioned rate of change to be bounded by a constant given
by the reciprocal of the net income rate of the resources (i.e., one minus the
commission paid to the platform). Conversely, if the rate of change is
positive (resp. negative) and strictly larger (resp. smaller) in absolute
value than the aforementioned constant, then we say that the market sizes
increase (resp. decrease) relative to distances. Our result shows that when
the market sizes closest to or furthest away from the shock center have
similar sizes, and they are increasing or decreasing in between, monotone
partitional mechanisms with a special “reveal-pool-reveal” structure are
optimal. More precisely, these mechanisms reveal low and high states, while
pooling the states in between and mapping them to a unique signal realization.
It is worth emphasizing that the initial or latter (or both) similarity
regions may be empty, in which case the state pooling region will not be
sandwiched in between two regions where the state is fully revealed. The
region where the market size changes monotonically can be empty (i.e., all
market sizes are similar), in which case always revealing the state becomes
optimal.

Our result yields an important insight: substantial changes in market sizes of
nearby regions may require witholding some information from the resources to
improve revenues (of both the resources and the platform). Intuitively, fully
revealing information in such cases may lead to accumulation of too many
resources in some locations, thereby leading to “congestion” and low prices.
Appropriately pooling some states, and in effect providing information with
lower fidelity, can eliminate this problem. Similarly, our result establishes
that pooling information is an especially important lever in the regime where
the platform’s commission rate is small, whereas in the other extreme with
very high commission rates (where the platform captures most of the revenues)
the optimal thing to do is full revelation.

Empirically, it has been observed that the requests of ride-hailing services
are often higher in regions close to the central business districts Dong et
al. (2018); Dean and Kockelman (2021). Thus, abstracting away the details, a
city can be modeled as a collection of (i) central locations with large market
sizes, (ii) suburban locations with small market sizes, and (iii) a transition
region around the central core where market sizes get progressively smaller as
one gets further away from the center. Assuming that the sizes of the markets
in (i) (resp. (ii)) are similar to each other, our results imply that both for
shocks in central locations, and those in suburban locations it is optimal to
use monotone information structures.

We also relax the initial demand balance and no market depletion assumptions.
Without these assumptions the model is very rich, which in turn makes it
harder to provide intuitive certificates for the optimality of monotone
partitions. Still, we are able to characterize the conditions under which
monotone partitions are optimal. On the methodological side, these results
contribute to the general theory of monotone partitions, by providing novel
tools for their study that apply when the designer’s payoff is piecewise
linear in the posterior mean her signal induces.

Our final contributions address algorithmic aspects of our information design
problem. When the aforementioned conditions do not hold, the optimal
information structure may not be monotone partitional. We offer a convex
optimization formulation to characterize the optimal information structure in
such cases, noting that a double-interval structure may be required for
maximizing the platform’s payoff, as detailed in Candogan (2019). In addition,
we provide a dynamic programming approach for obtaining near-optimal monotone
information structures and demonstrate its applicability to practical
scenario-based models providing a valuable toolkit for spatial resource
allocation problems with multiple shocks. Due to page limitations, the last
set of contributions are relegated to Appendix A.

#### Related literature:

The question of information design for influencing agents’ spatial
distribution was previously studied in Yang et al. (2019). In this paper, the
authors focus on a setting with two locations and binary state, where
initially all agents are in one location. The other location may have a
resource, whose availability is stochastic, and is represented by a binary
state. If agents move to the latter location, they derive a utility that
depends on the state as well as the number of agents who relocate
there.333Note that in our paper agents are resources who serve customer
demand, whereas in Yang et al. (2019) agents “consume” resources that possibly
become available in one of the locations. Leaving aside the difference in
nomenclature, the models capture similar frictions. For instance, in both
models the utility the agents derive from being in one location decreases in
the number of agents who are present there. The paper studies the design of
optimal public and private information structures (where all receivers see
identical or possibly different signals, respectively). Two main differences
from our work are worthwhile highlighting. First, the paper leaves open the
design of optimal information structures when there are more than two
locations – which is the setting we focus on. Second, due to binary state,
unlike the continuous state space in our paper, the question of monotone
partitional mechanisms is outside the scope of that paper. By contrast, our
focus is on understanding when such mechanisms are optimal, and our main
result shows this to be the case in fairly broad and practically-relevant
settings.

Dworczak and Martini (2019) introduces monotone partitional information
mechanisms, and also provide necessary and sufficient condition on the
sender’s payoff function under which a monotone partitional signal is optimal
_for any prior distribution of the state_. In our problem, the sender’s payoff
function has additional structure: It is piecewise linear. Exploiting this
observation we provide a refinement of the results of the aforementioned
paper, and provide novel conditions – this time jointly on the payoff function
and the distribution – for the optimality of monotone partitions. In addition,
we identify regimes for the parameters of our problem where these conditions
hold, and argue that a particular (reveal-pool-reveal type) monotone
partitional information structure turns out to be optimal in many practically
relevant cases.

Information design tools have been employed in different operational settings.
Vasserman et al. (2015); Das et al. (2017); Tavafoghi and Teneketzis (2017);
Wu and Amin (2019); Meigs et al. (2020) investigate the role of information
design in managing equilibrium flows in incident-prone traffic networks.
Alizamir et al. (2020); De Véricourt et al. (2021); Shah et al. (2022) study
the optimal information disclosure for the risk of pandemic. Lingenbrink and
Iyer (2019) studies how a designer can reveal informative signals on the queue
length to influence customers’ decisions on whether to join a queue.
Drakopoulos et al. (2018) and Lingenbrink and Iyer (2018) explore how a seller
can signal product availability to influence the purchase decisions of buyers.
Küçükgül et al. (2022) focuses on a dynamic setting where the seller can
disclose information to persuade new coming buyers to purchase the product.
Candogan and Drakopoulos (2020); Candogan (2022) study how information design
can be a useful tool to induce desired outcomes in social networks where
agents’ actions influence their neighbors’ payoffs. Papanastasiou et al.
(2018), Gur et al. (2019), and Johari et al. (2019) explore how platforms
leverage information to achieve desired outcomes, focusing on incentivizing
exploration, enabling dynamic pricing for third-party sellers, and signaling
agent quality in two-sided platforms to boost transaction value. Candogan and
Gurkan (2023) studies how downstream retailers can reveal demand information
to upstream suppliers in supply chains, so as to reduce supply chain costs.
The present paper contributes to this growing literature by shedding light on
practically relevant mechanisms for spatial resource allocation problems which
are prevalent in many modern platforms.

##  2 Model and preliminaries

###  2.1 Networks and agents

We consider an _undirected_ network $(V,E)$, where $V=\\{0,1,\dots,n\\}$ is
the set if nodes, and $E$ is the set of edges. A set of resources, modeled as
nonatomic agent populations, are distributed at nodes $i\in V$ in the network
with mass vector $m=(m_{i})_{i\in V}$, where $m_{i}\geq 0$ is the mass of
agent population originating from node $i$. The agent population at each node
$i$ decides if they stay at their origin node or reposition to another node in
the network. The cost of agents repositioning from node $i$ to $j$ is
$c_{ij}\geq 0$, and $c_{ii}=0$ for all $i\in V$. We denote agents’ strategy
distribution as $x=(x_{ij})_{i,j\in V}$, where $x_{ij}$ is the mass of agents
originating at node $i$ who choose the strategy of repositioning to node $j$
for $j\in V\setminus\\{i\\}$ or staying at their origin node $i$ for $j=i$. A
repositioning strategy distribution $x\in X$ is feasible if

$\displaystyle\sum_{j\in V}x_{ij}=m_{i},\quad\forall i\in V,\quad x_{ij}\geq
0,\quad\forall i,j\in V.$

The distribution of agents induced by $x$ is $q=(q_{i})_{i\in V}$, where

$\displaystyle q_{i}=\sum_{j\in V}x_{ji},\quad\forall i\in V.$ (1)

The service price at node $i$, denoted as $p_{i}(q_{i})$, is a linear function
of $q_{i}$:444All results generalize to piecewise linear price functions. In
particular, a node with a piecewise price function composed of $n$ linear
pieces can be equivalently represented as $n$ nodes at the same location of
the network, each with a linear price functions.

$\displaystyle p_{i}(q_{i})=s_{i}-\beta_{i}q_{i},\quad\forall i\in V.$

where $s_{i}\geq 0$ is the _market size_ at node $i$, and $\beta_{i}\geq 0$ is
the _price elasticity_ at node $i$. For every transaction, the platform
collects commission with a _fixed_ rate $r\in[0,1]$. Thus, the payoff received
by an individual agent is $(1-r)p_{i}(q_{i})$, and the total commission (i.e.
revenue) collected by the platform at node $i$ is $rp_{i}(q_{i})q_{i}$.

One or multiple nodes in the network may experience demand shocks that affect
the market sizes. We denote the state of the network as the vector of the
realized market sizes $s=(s_{i})_{i\in V}\in\mathcal{S}$, where
$\mathcal{S}=\prod_{i\in V}\mathcal{S}_{i}$ such that each $\mathcal{S}_{i}$
is a continuous and closed interval of $\mathbb{R}$. The cumulative
distribution of the state, referred as _the prior_ , is
$F:\mathcal{\mathcal{S}}\to[0,1]$. The prior $F$ is common knowledge. For most
of our analysis, we assume that state realizations belong to a $1$-dimensional
subspace of $\cal S$, and assume that $F$ restricted to this subspace is
absolutely continuous. The platform observes the realization $s$, but the
agents do not.

###  2.2 Platform’s design problem

The platform designs a _public_ information provision mechanism
$(\mathcal{T},\pi)$, where $\mathcal{T}$ is the set of possible signal
realizations, denoted generically as $t$, and $\pi(\cdot|s)$ is the
probability density function of signal realization given state $s$. We
consider the setting where the state and the signal sets are continuous. We
assume that $\pi$ satisfies mild measurability conditions that ensure that the
conditional expectations below are well defined.

The platform commits to their information mechanism $(\mathcal{T},\pi)$ before
observing the state realization. After observing the state $s$, the platform
generates a signal $t$ according to $\pi(\cdot|s)$ and sends the signal to
_all_ agents. Two special cases of information mechanisms are: (i) the
platform provides _full information_ if $\mathcal{T}=\mathcal{S}$ and
$\pi(t|s)=1$ for all $t=s$; and (ii) the platform provides _no information_ if
$\pi(\cdot|s)$ does not depend on $s$. When $(\mathcal{T},\pi)$ does not
belong to (i) or (ii), the information mechanism provides partial information
of the state.

After receiving the realized signal $t$, agents compute the expected value of
the state $\mathbb{E}[s|t]$, and make repositioning decisions based on the
received signal, i.e. the strategy distribution $x(t):\mathcal{T}\to X$. The
utility of agents who reposition from $i$ to $j$ equals to the expected payoff
received at node $j$ minus the repositioning cost $c_{ij}$:

$\displaystyle
u_{ij}(x|t)=(1-r)(\mathbb{E}[s_{j}|t]-\beta_{j}q_{j}(t))-c_{ij},\quad\forall
i,j\in V,$

where $q(t)$ is the distribution of agents induced by $x(t)$ as in (1). Agents
are self-interested in that they make repositioning decisions to maximize
their expected utility. Given signal $t$, we define the equilibrium strategy
distribution $x^{*}(t)$ as follows:

######  Definition 1.

For any $t\in\mathcal{T}$, a strategy profile $x^{*}(t)$ is a Wardrop
equilibrium if

$\displaystyle x^{*}_{ij}(t)>0,\quad\Rightarrow\quad u_{ij}(x^{*}|t)\geq
u_{ij^{\prime}}(x^{*}|t),\quad\forall j,j^{\prime}\in V,\quad\forall i\in V.$

That is, in equilibrium, the mass of agents repositioning from node $i$ to $j$
is nonzero if the expected utility $u_{ij}(x^{*}|t)$ based on the observed
signal is the maximum compared to staying at node $i$ or repositioning to any
other node in the network.

The objective of the platform is to design the optimal information mechanism
to maximize the total expected revenue – the total commission collected at all
nodes. For any signal $t$, the platform’s expected revenue $R(t)$ in
equilibrium is given by:

$\displaystyle R(t)$ $\displaystyle=r\sum_{i\in
V}(\mathbb{E}[s_{i}|t]-\beta_{i}q^{*}_{i}(t))q^{*}_{i}(t).$ (2)

Thus, the total expected revenue of the platform given mechanism
$(\mathcal{T},\pi)$ is

$\displaystyle R$
$\displaystyle=\int_{s\in\mathcal{S}}\int_{t\in\mathcal{T}}R(t)\pi(t|s)dF(s)dt.$
(3)

###  2.3 Potential function of the repositioning game

We first show that given any signal $t$, the induced repositioning game is a
population potential game, and $x^{*}(t)$ can be computed as the maximizer of
a potential function.

######  Proposition 1.

For any $t\in\mathcal{T}$, $x^{*}(t)$ can be computed by maximizing the
following potential function $\Phi(x|t)$:

$\begin{split}\max_{x\in X}\quad&\Phi(x|t):=(1-r)\sum_{i\in
V}\int_{0}^{q_{i}(t)}(\mathbb{E}[s_{i}|t]-\beta_{j}z)dz-\sum_{i,j\in
V}c_{ij}x_{ij}(t),\\\ s.t.\quad&x(t)\in X,\quad\text{and $q(t)$ satisfies
\eqref{eq:q_x}.}\end{split}$ (4)

Moreover, the agents’ distribution in equilibrium $q^{*}(t)$ is unique for all
$t\in\mathcal{T}$.

In (4), the potential function $\Phi(x|t)$ is quadratic, and the feasibility
constraints are linear. Thus, $x^{*}(t)$ can be computed as the maximizer of
the quadratic program in polynomial time. Proposition 1 also demonstrates that
equilibrium is essentially unique in that the agents’ distribution $q^{*}(t)$
is unique. As a result, the expected service price at each node and the
revenue $R(t)$ is unique in equilibrium for any $t\in\mathcal{T}$. 555The
uniqueness of $q^{*}(t)$ holds for any strictly increasing price function. In
addition, Proposition 1 does not require single dimensional shocks or absolute
continuity of the state.

Furthermore, we know from Proposition 1 and (2) that both $q^{*}(t)$ and
$R(t)$ only depend on the realized signal $t$ through the induced posterior
mean estimate of the state $\mathbb{E}[s|t]$, i.e.
$q^{*}(t)=q^{*}(t^{\prime})$ for any two signals $t,t^{\prime}\in\mathcal{T}$
such that $\mathbb{E}[s|t]=\mathbb{E}[s|t^{\prime}]$. Therefore, we know that
the platform’s total expected revenue $R$ depends on the distribution of the
posterior mean of the state $\mathbb{E}[s|t]$ induced by the information
mechanism $(\mathcal{T},\pi)$. The set of all possible posterior means is the
state set $\mathcal{S}$. We denote the cumulative distribution of the
posterior mean as $G:\mathcal{S}\to[0,1]$.

With slight abuse of notation, we denote the strategy profile associated with
any posterior mean that takes the value $s\in S$ as $x(s)$, agents’
distribution as $q(s)$, and the revenue function as $R(s)$. We re-write the
total expected revenue $R$ in (3) as follows:

$\displaystyle R$
$\displaystyle=\int_{s\in\mathcal{S}}R(s)dG(s)=r\int_{s\in\mathcal{S}}\sum_{i\in
V}(s-\beta_{i}q^{*}_{i}(s))q^{*}_{i}(s)dG(s).$ (5)

In Sec. 3 – 4, we focus on the single shock case, where only node $0$ is prone
to demand shock. We denote the set of states as $\mathcal{S}_{0}$ with generic
member $s_{0}$. Here, $s_{0}$ is a real number and $\mathcal{S}_{0}$ is a
closed interval of $\mathbb{R}$. In this case, a posterior mean distribution
$G$ is feasible (i.e. induced by an information mechanism given the prior $F$)
if and only $F$ is a mean-preserving spread of $G$, denoted as $G\preceq F$
(see Blackwell (1953); Gentzkow and Kamenica (2016); Kolotilin (2018); also a
formal definition is given in Appendix E for completeness). Therefore, the
optimal posterior mean distribution $G^{*}$ can be solved as follows in a
single shock case:

$\displaystyle\max_{G}\int_{z\in\mathcal{S}_{0}}R(z)dG(z),\quad s.t.\quad
G\preceq F.$ (6)

We define the value of information design $V^{*}_{F}$ as the difference
between the revenue with optimal information mechanism $R_{G^{*}}$ minus the
revenue with no information provision $R_{F}$, i.e.
$V^{*}_{F}=R_{G^{*}}-R_{F}$. We show that the value of information design is
higher for $F^{\prime}$ that is a mean-preserving spread of $F$. This result
builds on the fact that the feasible set of $G$ in (6) is larger with
$F^{\prime}$ than with $F$.666Proposition 2 holds for any information design
problem with one-dimensional state space.

######  Proposition 2.

For any $F\preceq F^{\prime}$, $V^{*}_{F}\leq V^{*}_{F^{\prime}}$.

##  3 Single shock with homogeneously balanced markets

In this section, we focus on identifying the conditions under which optimal
revenue can be achieved through information mechanisms with simple partitional
structure. Such mechanism involves partitioning the state space
$\mathcal{S}_{0}$ into intervals, and within each interval, the information
mechanism either fully reveals the state realization or only provides
information indicating that the realized state falls within that specific
interval. Formally, this type of information mechanism is referred to as a
_monotone partitional information mechanism_ (Dworczak and Martini (2019)):

######  Definition 2 (Monotone partitional information mechanism).

An information mechanism is monotone partitional if there exists a finite
partition of the state set $\mathcal{S}_{0}$ into intervals
$\mathcal{S}_{0}=\cup_{k\in\mathcal{K}}[z^{k},z^{k+1}]$ such that for each
$k$, the information mechanism either (i) fully reveals the state for all
$s_{0}\in[z^{k},z^{k+1}]$ (full revelation); or (ii) only reveals that the
realized state is in $[z^{k},z^{k+1}]$ (pooling).

Given a monotone partitional information mechanism, for any state realization
$s_{0}\in[z^{k},z^{k+1}]$, the corresponding signal is $t=s_{0}$ if interval
$k$ is a full revelation interval. If $k$ is a pooling interval, without loss
of generality, we set the signal realization to the associated posterior mean,
i.e., $t=\mathbb{E}_{F}[S_{0}|S_{0}\in[z^{k},z^{k+1}]]$. In either case, each
state realization corresponds to a unique signal realization and higher
realized state corresponds to a higher signal realization. Therefore, monotone
partitional information mechanisms have the advantage of sending deterministic
and monotone signals. In theory, monotone partitional information mechanisms
may or may not be optimal. In this section, we characterize verifiable
conditions that guarantee the optimality of monotone partitional information
mechanism. To better demonstrate the intuition and practical implications, we
first present our results under two assumptions – homogeneously balanced
market condition and no market depletion condition. We will remove these two
assumptions when generalizing our results in the next section.

For all $i\in V$, we let $d_{i}=c_{i0}$, where $c_{i0}$ is the distance of the
shortest path between node $0$ and node $i$ (recall that the underlying
network is undirected). Assumption 1 ensures that with no information
provision, markets at all nodes have homogeneous prices so that agents have no
incentive to move across nodes.777In practice, this assumption typically holds
in the long run when agents’ repeated repositioning decisions even out payoff
differences across nodes. In the short term, two nodes may still have
different prices especially when the distance between them is large.

######  Assumption 1 (Homogeneously balanced markets).

Given the initial distribution of agents $m$, the service price is identical
across all nodes. Without loss of generality, we normalize the price to zero,
i.e.

$\mathbb{E}_{F}[s_{0}]-\beta_{0}m_{0}=s_{i}-\beta_{i}m_{i}=0,\quad\forall i\in
V.$

Assumption 2 imposes bounds on the maximum realization of demand shock, and
rules out the possibility that agents at one node are all drawn away in
response to a high demand realization at node $0$, or all agents leave node 0
when the demand realization is low (Lemma 1).

######  Assumption 2 (No market depletion).

$\sup\mathcal{S}_{0}\leq\max_{i\in
V\setminus\\{0\\}}s_{i}+\frac{d_{i}}{1-r},\quad\inf\mathcal{S}_{0}\geq-\frac{m_{0}+\sum_{i=1}^{\hat{k}}\frac{d_{i}}{(1-r)\beta_{i}}}{\sum_{i=1}^{\hat{k}}\frac{1}{\beta_{i}}},$

where $\hat{k}$ satisfies:

$-d_{\hat{k}}\geq-\frac{m_{0}+\sum_{i=1}^{\hat{k}}\frac{d_{i}}{(1-r)\beta_{i}}}{\sum_{i=1}^{\hat{k}}\frac{1}{\beta_{i}}}\geq-
d_{\hat{k}+1}.$

######  Lemma 1.

Under Assumption 2, the agents’ equilibrium distribution $q^{*}(s_{0})$
satisfies $q^{*}_{i}(s_{0})>0$ for all $i\in V$ and all
$s_{0}\in\mathcal{S}_{0}$.

###  3.1 Equilibrium characterization

In this section, we provide a closed form characterization of the equilibrium
strategy distributions and the platform’s revenue. We show that the revenue is
a piecewise linear function of the posterior mean of demand at node 0. We
partition nodes in $V$ into $\\{0\\}\cup\\{\cup_{n=1}^{N}V_{n}\\}$, where all
nodes in $V_{n}$ have the same distance $d_{n}$ to node $0$. We label
$n=1,\dots,N$ in increasing order of $d_{n}$, i.e.
$0<d_{1}<d_{2}<\cdots<d_{N}$. Clearly, $N\leq|V|$.

######  Proposition 3.

Under Assumptions 1 and 2, the equilibrium agent distribution $q^{*}$ and
platform’s revenue $R$ are piecewise linear functions of the posterior state
mean $s_{0}$, and exhibit $K+\tilde{K}+1$ regimes, where

$\displaystyle K$
$\displaystyle=\max\left\\{k=1,\dots,N\left|~{}s_{0}[k]\leq\sup\mathcal{S}_{0}\right.\right\\},\quad\tilde{K}=\max\left\\{k=1,\dots,N\left|~{}s_{0}[-k]\geq\inf\mathcal{S}_{0}\right.\right\\},$

and the regime thresholds are given by:

$\displaystyle s_{0}[k]$
$\displaystyle=\mathbb{E}_{F}[S_{0}]+\frac{d_{k}}{1-r}+\sum_{i\in\cup_{n=1}^{k}V_{n}}\frac{\beta_{0}(d_{k}-d_{i})}{\beta_{i}(1-r)},\quad\forall
k=1,\dots,K,$ (7a) $\displaystyle s_{0}[-k]$
$\displaystyle=\mathbb{E}_{F}[S_{0}]-\frac{d_{k}}{1-r}-\sum_{i\in\cup_{n=1}^{k}V_{n}}\frac{\beta_{0}(d_{k}-d_{i})}{\beta_{i}(1-r)},\quad\forall
k=1,\dots,\tilde{K}.$ (7b)

Regime 0: $s_{0}[-1]\leq s_{0}<s_{0}[1]$.

$\displaystyle q^{*}_{0}$ $\displaystyle=m_{0},\quad
q^{*}_{i}=m_{i},\quad\forall i\in V\setminus\\{0\\}.$ (8)

Regime $\\{k\\}_{k=1}^{K}$: $s_{0}[k]\leq s_{0}<s_{0}[k+1]$.

$\displaystyle q^{*}_{0}$
$\displaystyle=\frac{1}{\beta_{0}\left(\sum_{i\in\cup_{n=1}^{k}V_{n}}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}\left(m_{0}+\sum_{i\in\cup_{n=1}^{k}V_{n}}\frac{1}{\beta_{i}}\left(s_{0}-\frac{d_{i}}{1-r}\right)\right),$
(9a) $\displaystyle q^{*}_{i}$
$\displaystyle=\frac{1}{\beta_{i}}\left(s_{i}-s_{0}+\frac{d_{i}}{1-r}\right)+\frac{\beta_{0}}{\beta_{i}}q^{*}_{0},\quad\forall
i\in\cup_{n=1}^{k}V_{n},\quad q^{*}_{i}=m_{i},\quad\forall i\in
V\setminus({\cup_{n=1}^{k}V_{n}\cup\\{0\\}}).$ (9b)

Regime $\\{-k\\}_{k=1}^{\tilde{K}}$: $s_{0}[-k-1]\leq s_{0}<s_{0}[-k]$.

$\displaystyle q^{*}_{0}$
$\displaystyle=\frac{1}{\beta_{0}\left(\sum_{i\in\cup_{n=1}^{k}V_{n}}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}\left(m_{0}+\sum_{i\in\cup_{n=1}^{k}V_{n}}\frac{1}{\beta_{i}}\left(s_{0}+\frac{d_{i}}{1-r}\right)\right),$
(10a) $\displaystyle q^{*}_{i}$
$\displaystyle=\frac{1}{\beta_{i}}\left(s_{i}-s_{0}-\frac{d_{i}}{1-r}\right)+\frac{\beta_{0}}{\beta_{i}}q^{*}_{0},\quad\forall
i\in\cup_{n=1}^{k}V_{n},\quad q^{*}_{i}=m_{i},\quad\forall i\in
V\setminus(\cup_{n=1}^{k}V_{n}\cup\\{0\\}).$ (10b)

Moreover, the platform’s revenue $R(s_{0})=r\sum_{i\in V}q^{*}_{i}p^{*}_{i}$
is a continuous piecewise linear function of $s_{0}$. In each regime $k$,
$R(s_{0})$ is a linear function of $s_{0}$, and the derivative of the linear
function, denoted as $\frac{dR(s_{0})}{ds_{0}}[k]$, is given by:

$\displaystyle\frac{dR(s_{0})}{ds_{0}}[k]$
$\displaystyle=\left\\{\begin{array}[]{ll}rm_{0},&\quad k=0,\\\ &\\\
r\frac{m_{0}+\sum_{i\in\cup_{n=1}^{k}V_{n}}\left(m_{i}+d_{i}/\beta_{i}(1-r)\right)}{\beta_{0}\left(\sum_{i\in\cup_{n=1}^{k}V_{n}}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)},&\quad\forall
k=1,\dots,K,\\\ &\\\
r\frac{m_{0}+\sum_{i\in\cup_{n=1}^{k}V_{n}}\left(m_{i}-d_{i}/\beta_{i}(1-r)\right)}{\beta_{0}\left(\sum_{i\in\cup_{n=1}^{k}V_{n}}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)},&\quad\forall
k=-1,\dots,-\tilde{K}.\end{array}\right.$

Proposition 3 shows that when the demand realization exceeds the prior mean,
agents from nodes in proximity to node 0 move to node 0, starting from nodes
with the smallest distances $d_{1}$ and gradually progressing to more distant
nodes as the demand realization further increases. The equilibrium price at
node 0 is equal to the price at each node $i$ where agents move to node 0,
plus the distance $d_{i}$. Conversely, when the demand realization decreases
below the prior mean, agents from node 0 begin to move to other nodes.
Initially, they move to nodes with small distances $d_{1}$, as the demand
further decreases, they move to more distant nodes. In this scenario, the
price at node 0 is equivalent to the price at each node $i$ where agents move
to, minus the distance $d_{i}$.

When $x_{i0}>0$ (resp. $x_{0i}>0$) for some $i\in V$, we say that agents move
from $i$ to $0$ (resp. from $0$ to $i$) in equilibrium, due to a demand shock
that yields a higher (resp. lower) realization than the prior mean at node
$0$. Proposition 3 demonstrates that equilibrium regimes are distinguished by
the changes of the set of affected nodes – the set of affected nodes is
$\cup_{n=1}^{k}V_{n}$ in regimes $k$ and $-k$. Moreover, due to agents’
movements in equilibrium, the price sensitivity at node 0 (with respect to the
change of demand) depends on the price sensitivity of all of the nodes that
are affected. As a result, the derivative of the platform’s revenue with
respect to the demand realization changes as the regime changes.

###  3.2 Optimal partitional information mechanism

In this section, we demonstrate the efficacy of monotone partitional
information mechanisms by showing that under a set of practically relevant
conditions on market size distributions, optimal revenue can be achieved by
simple monotone partitional mechanisms with at most one pooling interval. We
also provide an algorithm for computing such simple partitional mechanism.

Before presenting the theorem, we first define similar and monotone market
sizes. We say that the market sizes are _similar relative to distances_ for
nodes $i$ and $j$ with $d_{i}\neq d_{j}$ if $s_{i}$ and $s_{j}$ satisfy:

$\displaystyle\left|\frac{s_{i}-s_{j}}{d_{i}-d_{j}}\right|\leq\frac{1}{1-r},$
(11)

This indicates that the proportion of the changes of market sizes between any
two nodes $i$ and $j$ with respect to the differences of their distances to
node $0$ is upper bounded by $1/(1-r)$, which increases as the commission rate
$r$ increases (Recall that this rate is less than 1). Additionally, we say
that market sizes _increase relative to distances_ (resp. _decrease relative
to distances_) for nodes $i$ and $j$ with $d_{i}>d_{j}$ if $s_{i}$ and $s_{j}$
satisfy (12a) (resp. (12b)):

$\displaystyle\frac{s_{i}-s_{j}}{d_{i}-d_{j}}>\frac{1}{1-r},$ (12a)
$\displaystyle\frac{s_{i}-s_{j}}{d_{i}-d_{j}}<-\frac{1}{1-r},$ (12b)

Equation (12a) (resp. (12b)) indicates that the nodes that are further away
(resp. closer) to node $0$ have larger (resp. smaller) market sizes, and the
rate of increase (resp. decrease) with respect to the change of distances is
larger than $1/(1-r)$.

We define $D$ as the maximum distance of nodes that can be affected by demand
shock in equilibrium, i.e. $D=\max\\{d_{-\tilde{K}},d_{K}\\}$. Agents from any
nodes with distances higher than $D$ will not move in equilibrium given any
demand realization, and thus the market sizes of these nodes are irrelevant
for information design. The following theorem shows that a monotone
partitional information mechanism is optimal if there exists a monotone
_transition region_ , where nodes with distances between $\underline{d}$ and
$\bar{d}$ have monotonically increasing or decreasing market sizes relative to
their distances to node $0$.

######  Theorem 1.

Under Assumptions 1 and 2, suppose that there exists
$0\leq\underline{d}\leq\bar{d}\leq D$ such that nodes with distances less than
$\underline{d}$ have similar market sizes, nodes with distances in
$[\underline{d},\bar{d}]$ have decreasing or increasing market sizes, and
nodes with distances higher than $\bar{d}$ also have similar market sizes
relative to distances. Given any prior distribution $F$, there exists an
optimal monotone partitional information mechanism with thresholds
$\inf\mathcal{S}_{0}\leq\underline{z}\leq\bar{z}\leq\sup\mathcal{S}_{0}$ that
fully reveals states $s_{0}\leq\underline{z}$ and $s_{0}\geq\bar{z}$, and
pools states $s_{0}\in[\underline{z},\bar{z}]$ with posterior mean
$z^{*}=\mathbb{E}_{F}[S_{0}|\underline{z}\leq S_{0}\leq\bar{z}]$.
Specifically,

  1. (i)

$\underline{z}=\bar{z}$ if $\underline{d}=\bar{d}$. That is, full information
revelation is optimal if all nodes have similar market sizes relative to
distances.

  2. (ii)

$z^{*}>\mathbb{E}_{F}[S_{0}]$ if nodes with distances in
$[\underline{d},\bar{d}]$ have decreasing market sizes relative to distances.

  3. (iii)

$z^{*}<\mathbb{E}_{F}[S_{0}]$ if nodes with distances in
$[\underline{d},\bar{d}]$ have increasing market sizes relative to distances.

Theorem 1 shows that the optimal information mechanism reveals at least
partial demand information to agents and has a simple partitional structure
with up to three intervals.888Since the revenue function $R(s_{0})$ is
piecewise linear, fully revealing state information is equivalent to revealing
the regime interval in which the state realization resides. These intervals
consist of one pooling interval between $\underline{z}$ and $\bar{z}$, and two
full information revelation intervals for demands below $\underline{z}$ and
above $\bar{z}$. When all market sizes are similar relative to distances to
node 0 (case (i) as shown in Fig. 2(a)), maximum revenue is achieved by
revealing all information, resulting in a degenerate pooling interval. In both
cases (ii) and (iii) as shown in Figures 2(d)and 2(f), the optimal information
mechanism includes a pooling interval. In case (ii) (resp. case (iii)), the
pooling interval generates a posterior mean that induces agents to move to
node 0 (resp. move away from node 0) when the transition region has decreasing
(resp. increasing) market sizes.

To understand the intuition behind cases (ii) and (iii) and the value of
pooling more clearly, consider a simple example with three nodes on a line,
where node $0$ is prone to demand shocks. Suppose nodes $1$ and $2$ with
distances $d_{1}<d_{2}$ do not have similar market sizes, and one of them is
small whereas the other one is large. Consider positive shocks at node $0$,
which always improve the platform’s revenues. If the shock is large enough to
influence the resources only in the small market, then this will have only
marginal impact on the revenue change rate at node $0$, but if it influences
the large market, then the revenue change rate becomes substantially larger
(see Proposition 3). This implies that if nodes $1$ and $2$ exhibit increasing
market sizes, then the revenue function in the positive shock regime is
convex, but in the decreasing market sizes case it is concave. This (local)
concavity of the revenue function implies that as opposed to revealing the
state, with appropriate pooling the platform can ensure higher profits.
Specifically, in the positive shock regime, with decreasing market sizes, when
the state realization is relatively small, revealing the states induces a few
resources to reposition to $0$ preserving a relatively high price there.
However, when the realization is large, revealing the state leads to too many
resources to reposition to $0$, and in some realizations it may even
incentivize the resources in the further out small markets to move, thereby
leading to excessively low prices. While in the former case, pooling may lower
revenues, in the latter case, by eliminating low prices, it ensures higher
revenues. Concavity of the revenue function ensures that the latter effect
dominates, and the expected revenues are higher with pooling. With increasing
market sizes, convexity in the positive shock regime may at first suggest that
pooling should not help. However, it turns out that in this case, in the
negative shock regime we have local concavity of the payoff function. Hence,
appropriate pooling, once again, improves revenues.

The scenario of similar or monotone market sizes described in Theorem 1 are of
practical interests. Empirical studies Dong et al. (2018); Dean and Kockelman
(2021) have demonstrated that the requests of ride-hailing services are often
higher in regions close to the central business districts, which have more
jobs, services and other economic activities, and decrease in regions far away
from the central business districts. In Theorem 1, case (i) corresponds to the
scenario where all affected nodes are within or close to the central business
district, and thus all nodes have similar market sizes. Additionally, case
(ii) corresponds to the scenario where the shock affects a node within the
central business district and affect nodes that are outside of the district,
which have decreasing market sizes relative to distances. On the other hand,
case (iii) corresponds to the scenario where the shock happens at a node that
is far away from the central business district, and therefore nodes that are
further away from node 0 have higher market sizes. Theorem 1 demonstrates that
in both cases, a simple partitional information mechanism with one pooling
interval is optimal.

_Proof sketch._ The proof of Theorem 1 builds on the duality theory of optimal
information design introduced in Dworczak and Martini (2019). This duality
theory demonstrates that the optimal posterior mean distribution $G^{*}$ can
be constructed by finding an upper closure $\nu(s_{0})$ of the objective
function $R(s_{0})$ that satisfies (i) the function $\nu(s_{0})$ is convex and
$\nu(s_{0})\geq R(s_{0})$; (ii) the expected value of $\nu(s_{0})$ with
respect to $G^{*}$ is the same as that with $R(s_{0})$; (iii) The optimal
posterior $G^{*}$ is a mean preserving spread of the prior $F$, and the
support set of $G^{*}$ is a subset of $\\{S_{0}|\nu(s_{0})=R(s_{0})\\}$ (Lemma
7 in Appendix D).

Building on the general theory, we further show that the construction of such
convex upper closure function is associated with the second-order properties
(convexity or concavity) of the revenue function $R(s_{0})$. In our problem,
the second order property of $R(s_{0})$ is governed by how the derivative of
the linear revenue function changes from one equilibrium regime to another.
From Proposition 3, we find that the changes of the derivatives depend on the
market sizes of nodes that are affected. Since nodes are added to the affected
set according to their distances to node $0$, the change of derivatives depend
on the changes of market sizes relative to the distances.

We show that under Assumptions 1 – 2 and the condition that market sizes are
similar or monotone with respect to their distances to node 0, there exists at
most one sub-interval of states $[\underline{s}_{0},\bar{s}_{0}]$ such that
$R(s_{0})$ is concave in $[\underline{s}_{0},\bar{s}_{0}]$ and convex to the
left or right of this interval (Lemma 6 in Appendix D). In particular, the
sub-interval is empty and the function $R(s_{0})$ is convex if all nodes have
similar market sizes with respect to distances. Thus, $\nu(s_{0})=R(s_{0})$,
$G^{*}=F$ satisfy conditions (a) – (c) indicating that the optimal information
mechanism is to fully reveal the demand realization (Fig. 2(b)).

Additionally, in cases (ii) (resp.(iii)), the concave subinterval results in a
higher (resp. lower) posterior mean than the prior mean. We prove that in both
cases, the convex closure function can be constructed as
$\nu(s_{0})=\max\\{g(s_{0}),R(s_{0})\\}$, where $g(s_{0})$ is an affine
function tangent to the concave piece of the revenue function $R(s_{0})$. We
show that the optimal information mechanism exhibits a simple partitional
structure with one pooling interval that associated with the interval of
states such that $\nu(s_{0})=g(s_{0})$, and the remaining states out of this
interval are fully revealed. The posterior mean of the pooled state equals to
tangent point $z^{*}$, which is higher than (resp. lower than) the prior mean
in case (ii) (resp. case (iii)). In Fig. 2(f) and 2(d), we illustrate the
pooling and revealing intervals, and the affine function $f$ associated with
the optimal information mechanism for cases (ii) – (iii), respectively.

(a)

(b)

(c)

(d)

(e)

(f)

Figure 2: (a)-(b) Nodes with similar market sizes and convex revenue function
associated with full information revelation mechanism; (c)-(d) Nodes with
decreasing transition region and revenue function associated with one pooling
interval; (e)-(f) Nodes with increasing transition region and revenue function
associated with one pooling interval.

The next corollary shows that when all nodes have monotone market sizes
relative to their distances, one full information revelation interval becomes
degenerate.

######  Corollary 1.

If all nodes have monotonically decreasing (resp. increasing) market sizes
relative to distances, then given any prior distribution $F$, the optimal
information mechanism pools states $s_{0}\geq\underline{z}$ (resp.
$s_{0}\leq\bar{z}$) such that $\underline{z}<\mathbb{E}_{F}[S_{0}]$ (resp.
$\bar{z}>\mathbb{E}_{F}[S_{0}]$) and fully reveal states $s_{0}<\bar{z}$
(resp. $s_{0}>\bar{z}$).

Corollary 1 builds on Theorem 1: When all nodes have decreasing (resp.
increasing) market sizes, the revenue function is concave (resp. convex) for
$s_{0}>\mathbb{E}_{F}[S_{0}]$ and convex (resp. concave) for
$s_{0}<\mathbb{E}_{F}[S_{0}]$. Consequently, we show that one of the two full
revelation region becomes empty, and the optimal information mechanism pool
states above threshold $\underline{z}$ (resp. below $\bar{z}$).

Furthermore, we show that when the commission rate $r$ exceeds a certain
threshold, all market sizes are categorized as being similar as in (11).
Therefore, full information revelation is optimal with high commission rate
following case (i) in Theorem 1.

######  Corollary 2.

Under Assumptions 1 and 2, for any prior state distribution $F$ and any
sequence of market sizes $\\{s_{i}\\}_{i\in V}$, full information provision
mechanism is optimal for any $r>\bar{r}$, where

$\bar{r}=1-\min_{i,j\in\\{V|d_{i}\neq
d_{j}\\}}\left|\frac{d_{i}-d_{j}}{s_{i}-s_{j}}\right|.$

Finally, we present an algorithm to compute the thresholds $\bar{z}$ and
$\underline{z}$ of the monotone partitional information mechanism.

######  Proposition 4.

Under Assumptions 1 and 2, suppose that there exists
$0\leq\underline{d}\leq\bar{d}\leq D$ such that nodes with distances less than
$\underline{d}$ or higher than $\bar{d}$ have similar market sizes relative to
distances, and nodes with distances in $[\underline{d},\bar{d}]$ have
increasing or decreasing market sizes relative to distances. The thresholds of
the pooling interval $\underline{z},\bar{z}$ and the posterior mean $z^{*}$
are computed by Algorithm 1.

Proposition 4 and Algorithm 1 build on the proof of Theorem 1. In particular,
if the derivative of the linear revenue function in each regime is non-
decreasing, then Algorithm 1 returns identical $\underline{z}$ and $\bar{z}$
indicating that the pooling interval is degenerate. Otherwise, we identify a
concave interval from regime $\underline{k}$ to $\bar{k}$. Building on Theorem
1, Algorithm 1 computes the pooling interval by searching for the affine
function $g(s_{0})$ that is tangent to $R(s_{0})$. In particular, the
algorithm starts with the affine function being the revenue function
associated with regime $\underline{k}$, and iteratively proceeds to regimes
with increasing $k$ until $\bar{k}$. In each iteration, the algorithm computes
the interval thresholds as the intersection of the affine function and the
revenue function, and computes the mean of the state within the corresponding
interval. The algorithm terminates by finding the interval such that the state
mean equals to the point, where the affine function is tangent to the revenue
function. The proof of Theorem 1 ensures that such interval exists, and is the
optimal pooling region.

Input: $\frac{dR(s_{0})}{ds_{0}}[k]$ for
$k=-\tilde{K},-\tilde{K}+1,\dots,-1,0,1,\dots,K-1,K$.

if  _$\frac{dR(s_{0})}{ds_{0}}[k]$ is non-decreasing for all $k$ _ then

$\underline{z}\leftarrow\mathbb{E}_{F}[S_{0}]$,
$\bar{z}\leftarrow\mathbb{E}_{F}[S_{0}]$

else

$\underline{k}\leftarrow\min_{k}\left\\{k\left|\frac{dR(s_{0})}{ds_{0}}[k]>\frac{dR(s_{0})}{ds_{0}}[k+1]\right.\right\\}$,
$\bar{k}\leftarrow\max_{k}\left\\{k\left|\frac{dR(s_{0})}{ds_{0}}[k-1]>\frac{dR(s_{0})}{ds_{0}}[k]\right.\right\\}$

$j\leftarrow\underline{k}$

while  _$j\leq\bar{k}$_ do

$g_{j}(z)=\frac{dR(s_{0})}{ds_{0}}[j](z-s_{0}[j])+R(s_{0}[j]).$
$\underline{z}[j]\leftarrow\max\left\\{z\in S_{0}\left|z\leq s_{0}[j],\quad
g_{j}(z)\geq R(z)\right.\right\\}$, $\bar{z}[j]\leftarrow\min\left\\{z\in
S_{0}\left|z\geq s_{0}[j+1],\quad g_{j}(z)\geq R(z)\right.\right\\}$.

if  _$\mathbb{E}_{F}[S_{0}|\underline{z}[j]\leq S_{0}\leq\bar{z}[j]]\leq
s_{0}[j+1]$_ then

break

else

$j\leftarrow j+1$.

if  _$\mathbb{E}_{F}[S_{0}|\underline{z}[j]\leq S_{0}\leq\bar{z}[j]]\geq
s_{0}[j]$_ then

$\underline{z}\leftarrow\underline{z}[j]$, $\bar{z}\leftarrow\bar{z}[j]$,
$z^{*}\leftarrow\mathbb{E}_{F}[S_{0}|\underline{z}[j]\leq
S_{0}\leq\bar{z}[j]]$

else

$z^{*}\leftarrow s_{0}[j]$, and $\bar{z},\underline{z}$ are solutions of the
following equations:  $\displaystyle z^{*}$
$\displaystyle=\mathbb{E}_{F}[S_{0}|\underline{z}\leq
S_{0}\leq\bar{z}],~{}g_{\gamma}(z)=\gamma(z-s_{0}[j])+R(s_{0}[j]),~{}\frac{dR(s_{0})}{ds_{0}}[j+1]\leq\gamma\leq\frac{dR(s_{0})}{ds_{0}}[j],$
$\displaystyle\underline{z}$ $\displaystyle=\max\left\\{z\in
S_{0}\left|z<s_{0}[j],~{}g_{\gamma}(z)\geq
R(z)\right.\right\\},~{}\bar{z}=\min\left\\{z\in
S_{0}\left|z>s_{0}[j],~{}g_{\gamma}(z)\geq R(z)\right.\right\\}.$

Output: $\bar{z},\underline{z},z^{*}$.

ALGORITHM 1 Computation of thresholds $\underline{z},\bar{z}$ in the optimal
monotone partitional information mechanism.

##  4 Generalized results for single shock

###  4.1 Generalization of optimal partitional information mechanism

In this section, we drop Assumptions 1 and 2, and instead make the following
assumption on the initial market balance – no agents have incentives to move
across nodes. This assumption is without loss of generality since under any
reasonable equilibrium model agents will always make repositioning decisions
so that $m$ satisfies the balancedness condition before the platform reveals
any information of demand realization.

######  Assumption 3 (Initial market balance).

The market is initially balanced in that no agents have incentive to move
given the initial agent distribution $m$, i.e.

$\displaystyle(1-r)(s_{j}-\beta_{j}m_{j})-c_{ij}\leq(1-r)(s_{i}-\beta_{i}m_{i})\leq(1-r)(s_{j}-\beta_{j}m_{j})+c_{ij},\quad\forall
i,j\in V\setminus\\{0\\},$
$\displaystyle(1-r)(s_{i}-\beta_{i}m_{i})-c_{i0}\leq(1-r)(\mathbb{E}_{F}(S_{0})-\beta_{0}m_{0})\leq(1-r)(s_{i}-\beta_{i}m_{i})+c_{i0},\quad\forall
i\in V\setminus\\{0\\},$

where $\mathbb{E}_{F}[S_{0}]=\int_{s_{0}}s_{0}dF(s_{0})$ is the prior mean of
the state $s_{0}$.

We only describe the ideas of equilibrium characterization and regime
computation in the main text. The formal algorithm of computing equilibrium
regimes and complete characterization of equilibrium agent distribution and
revenue function are included in Appendix C. Our characterization approach
closely follows the one in the previous section, but we need to have slight
modifications since we now impose a more permissive initial market balance
condition. In particular, in the general case, the equilibrium regimes are
jointly determined by the distance $d_{i}$ and the price with the initial
agent mass $s_{i}-\beta_{i}m_{i}$ for all nodes. For each
$s_{0}>\mathbb{E}_{F}[s_{0}]$, there exists a set of nodes $\Gamma$, where
agents move to node 0, and the agents from the remaining nodes
$V\setminus\Gamma$ do not move. Moreover, agents from a subset of nodes
$\Gamma^{\dagger}\subseteq\Gamma$ may entirely move to node 0 since the no
depletion assumption is no longer imposed.

In Appendix C, we develop Algorithm 2 to compute equilibrium regimes for all
$s_{0}\geq\mathbb{E}_{F}[S_{0}]$. The algorithm starts with regime 0, where
both sets $\Gamma[0]$ and $\Gamma^{\dagger}[0]$ are empty, and all agents stay
at their origin nodes. As $s_{0}$ increases, agents from node $i\in
V\setminus\\{0\\}$ with the maximum initial payoff plus distance (i.e.
$(1-r)(s_{i}-\beta_{i}m_{i})+d_{i}$) start to move to node 0 in equilibrium of
regime $1$, and thus node $i$ is added to the set $\Gamma[1]$. The regime
threshold $s_{0}[1]$ is computed as the state realization such that agents at
node $i$ are indifferent between staying at $i$ and moving to node $0$.
Similarly, Algorithm 2 computes all possible equilibrium regimes
$k=1,\dots,K$, where the regime change from $k$ to $k+1$ occurs when either a
node
$i\in\operatorname*{arg\,max}_{V\setminus\Gamma[k]}(1-r)(s_{i}-\beta_{i}m_{i})+d_{i}$
is added to the set $\Gamma[k+1]$ or the price at node $0$ surpasses the
maximum payoff plus the distance $(1-r)s_{i}+d_{i}$ of a node in $\Gamma[k]$
so that all agents leave node $i$ (i.e. node $i$ is added into
$\Gamma^{\dagger}[k+1]$). The algorithm terminates with regime $K$ such that
all agents move to node $0$. Since any node can only be added to $\Gamma$ and
$\Gamma^{\dagger}$ once, the maximum number of regimes $K\leq 2|V|$, and the
algorithm terminates in less than $2|V|$ iterations.

Likewise, for any $s_{0}<\mathbb{E}_{F}[S_{0}]$, agents at node $0$ move to a
subset of nodes $\tilde{\Gamma}$, while the remaining agents do not move. In
particular, as $s_{0}$ decreases, nodes are included into $\tilde{\Gamma}$ in
decreasing order of $(1-r)(s_{i}-\beta_{i}m_{i})-d_{i}$. In Appendix C,
Algorithm 3 computes the set $\tilde{\Gamma}[k]$ for each regime
$-k=-1,\dots,-\tilde{K}$, and the regime boundaries
$\\{s_{0}[-k]\\}_{k=1}^{\tilde{K}}$. Since each node is only added to
$\tilde{\Gamma}$ once, $\tilde{K}\leq|V|$ and the algorithm terminates in less
than $|V|$ iterations.

Based on the equilibrium characterization, we show that the platform’s revenue
function is a continuous piecewise linear function of $s_{0}$ and the
derivative of the linear piece $\frac{dR(s_{0})}{ds_{0}}[k]$ depends on the
sets $\Gamma[k]$ and $\Gamma^{\dagger}[k]$ in regime $k$, and
$\tilde{\Gamma}[-k]$ in regime $-k$ (Proposition 7 in Appendix C). We next
generalize Theorem 1 to provide verifiable conditions that guarantee the
existence of an optimal monotone partitional information mechanism under the
following mild regularity condition of the revenue function $R(s_{0})$.999 It
can be seen that this condition generically holds. More precisely, for any
revenue function that violates Assumption 4 with $k_{a},k_{b},k_{c}$, a slight
perturbation of agent mass $m_{i}$ for $i\in\Gamma[k_{c}]$ (or
$\tilde{\Gamma}[k_{c}]$ if $k_{c}<0$) will make
$\\{(s_{0}[k_{j}],R(s_{0}[k_{j}]))\\}_{j=a,b,c}$ not lie on the same line, and
thus leads to satisfaction of this condition.

######  Assumption 4.

There does not exist $k_{a}<k_{b}<k_{c}$ such that
$\\{(s_{0}[k_{j}],R(s_{0}[k_{j}]))\\}_{j=a,b,c}$ lie on the same line.

We define _concave intervals_ of the revenue function $R(s_{0})$ as
$\\{[s_{0}[k_{\ell,a}],s_{0}[k_{\ell,b}]]\\}_{\ell=1}^{L}$, where
$-\tilde{K}\leq k_{1,a}\leq k_{1,b}<k_{2,a}\leq k_{2,b}<\cdots<k_{L,a}\leq
k_{L,b}\leq K$. The platform’s revenue function $R(s_{0})$ is strictly concave
(resp. strictly convex) at $s_{0}[k]$ if
$\frac{dR(s_{0})}{ds_{0}}[k-1]>(\text{resp.}<)\frac{dR(s_{0})}{ds_{0}}[k]$ and
concave (resp. convex) at $s_{0}[k]$ if
$\frac{dR(s_{0})}{ds_{0}}[k-1]\geq(\text{resp.}\leq)\frac{dR(s_{0})}{ds_{0}}[k]$.
For each interval $\ell$, the revenue function is strictly concave at
$s_{0}[k_{\ell,a}]$ and $s_{0}[k_{\ell,b}]$, and concave for all $s_{0}[k]$
with $k_{\ell,a}<k<k_{\ell,b}$. Moreover, $R(s_{0})$ is convex for all
$k_{\ell,b}<k<k_{\ell+1,a}$ and strictly convex for at least one
$k_{\ell,b}<\hat{k}<k_{\ell+1,a}$.101010This condition is to ensure that two
cannot intervals cannot be combined into a single concave interval.

Before presenting the result, we first introduce the four conditions (C1) –
(C4):
(C1) $L\leq 1$, i.e. the revenue function has at most one concave interval.
(C2) There does not exist $\ell<\ell^{\prime}$ such that

$\displaystyle\frac{dR(s_{0})}{ds_{0}}[k_{\ell,a}-1]\left(s_{0}-s_{0}[k_{\ell,a}]\right)+R\left(s_{0}[k_{\ell,a}]\right)-R(s_{0})\geq
0,\quad\forall
s_{0}\in\left[s_{0}[k_{\ell^{\prime},a}],s_{0}[k_{\ell^{\prime},b}]\right],$
(13a)
$\displaystyle\frac{dR(s_{0})}{ds_{0}}[k_{\ell^{\prime},b}]\left(s_{0}-s_{0}[k_{\ell^{\prime},b}]\right)+R\left(s_{0}[k_{\ell^{\prime},b}]\right)-R(s_{0})\geq
0,\quad\forall s_{0}\in\left[s_{0}[k_{\ell,a}],s_{0}[k_{\ell,b}]\right],$
(13b) $\displaystyle\exists
s_{0}\in\left[s_{0}[k_{\ell^{\prime},a}],s_{0}[k_{\ell^{\prime},b}]\right],\quad
s.t.\quad\frac{dR(s_{0})}{ds_{0}}[k_{\ell,b}]\left(s_{0}-s_{0}[k_{\ell,b}]\right)+R\left(s_{0}[k_{\ell,b}]\right)-R(s_{0})<0,$
(13c) $\displaystyle\exists
s_{0}\in\left[s_{0}[k_{\ell,a}],s_{0}[k_{\ell,b}]\right],\quad
s.t.\quad\frac{dR(s_{0})}{ds_{0}}[k_{\ell^{\prime},a}-1]\left(s_{0}-s_{0}[k_{\ell^{\prime},a}]\right)+R\left(s_{0}[k_{\ell^{\prime},a}]\right)-R(s_{0})<0.$
(13d)

The following lemma shows that when condition (C2) is not satisfied (i.e.
there exists $\ell<\ell^{\prime}$ that satisfy (13)), there exists a unique
linear function that is tangent to the concave intervals $\ell$ and
$\ell^{\prime}$ of $R(s_{0})$. Otherwise, such linear tangent function does
not exist.

######  Lemma 2.

For any $\ell<\ell^{\prime}$, there exists a unique linear function
$g(z)=\gamma z+\lambda$ such that
$g(s_{0}[k_{\ell}^{*}])=R(s_{0}[k_{\ell}^{*}]),\quad
g(s_{0}[k_{\ell^{\prime}}^{*}])=R(s_{0}[k_{\ell^{\prime}}^{*}])$ for some
$k_{\ell,a}\leq k_{\ell}^{*}\leq k_{\ell,b}$ and $k_{\ell^{\prime},a}\leq
k_{\ell^{\prime}}^{*}\leq k_{\ell^{\prime},b}$ and
$\gamma\in[\frac{dR(s_{0})}{ds_{0}}[k_{\ell}^{*}],\frac{dR(s_{0})}{ds_{0}}[k_{\ell}^{*}-1]]\cap[\frac{dR(s_{0})}{ds_{0}}[k_{\ell^{\prime}}^{*}],\frac{dR(s_{0})}{ds_{0}}[k_{\ell^{\prime}}^{*}-1]]$
if and only if (13) is satisfied.

(C3) For any pair of concave intervals $\ell<\ell^{\prime}$ that satisfies
(13), consider the associated affine function $g(z)$ and
$x=s_{0}[k_{\ell}^{*}]$ (resp. $y=s_{0}[k_{\ell^{\prime}}^{*}]$) that
satisfies $R(x)=g(x)$, $R(y)=g(y)$. Define
$\underline{z}_{\ell}=\max\\{z<x|R(z)\geq g(z)\\}$ and
$\bar{z}_{\ell^{\prime}}=\min\\{z>y|R(z)\leq g(z)\\}$. Then, either
$x,y<\mathbb{E}_{F}[S_{0}],\bar{z}_{\ell^{\prime}}=\sup\mathcal{S}_{0}$ or
$x,y>\mathbb{E}_{F}[S_{0}],\underline{z}_{\ell}=\inf\mathcal{S}_{0}$.

(C4) For any pair of concave intervals $\ell<\ell^{\prime}$ that satisfy (13),
and $g(z)$, $x$, $y$, $\underline{z}_{\ell}$ and $\bar{z}_{\ell^{\prime}}$
defined as in (C3),

$\displaystyle\int_{[\underline{z}_{\ell},y]}zdF(z)\geq
x,\quad\int_{[x,\bar{z}_{\ell^{\prime}}]}zdF(z)\leq
y,\quad\left(F^{-1}\left(\tilde{z}\right)-x\right)\tilde{z}\geq\int_{\underline{z}_{\ell}}^{F^{-1}\left(\tilde{z}\right)}(F(z)-F(\underline{z}_{\ell}))dz,$
(14)

where

$\displaystyle\tilde{z}$
$\displaystyle=\frac{yF(\bar{z}_{\ell^{\prime}})-xF(\underline{z}_{\ell})-z^{*}}{y-x},\qquad
z^{*}=\int_{\underline{z}_{\ell}}^{\bar{z}_{\ell^{\prime}}}zdF(z).$ (15)

######  Proposition 5.

There exists an optimal information mechanism that is monotone partitional if
any of the four conditions (C1) – (C4) is satisfied.

Proposition 5 provides four verifiable conditions on the revenue function $R$
and the prior $F$ that guarantee the optimality of monotone partitional
information mechanism. Among the four conditions, (C1) – (C2) only concern the
revenue function, while (C3) – (C4) set conditions on $R$ and $F$ jointly.

In particular, (C1) ensures that the revenue function has at most one concave
interval so that the optimal information mechanism can have at most one
pooling region – recall that cases (i) – (iii) in Theorem 1 satisfy this
condition. (C2) ensures that we cannot find an affine function that is tangent
with two concave intervals. The theory of optimal information design shows
that the existence of such affine functions indicates that the optimal
information mechanism may contain double-interval structures that are not
monotone – pooling high and low states in the interval to generate one
posterior mean, and pooling the remaining states in the middle to generate
another posterior mean. Specifically, the two posterior means take values of
the two tangent points Candogan (2019); Dworczak and Martini (2019); Arieli et
al. (2023). Both (C1) and (C2) ensure the optimality of monotone partitional
mechanism by ruling out the existence of such affine functions. Thus, these
two conditions are equivalent to the “affine closure” condition of Dworczak
and Martini (2019) for the optimality of monotone partitional mechanisms, and
they are easy to verify given the piecewise linear payoff struture in our
problem.

Moreover, Proposition 5 extends the result in Dworczak and Martini (2019) by
providing two other conditions (C3) – (C4) that allow the revenue function not
to be affine closed, but can still guarantee the optimality of monotone
partitional mechanism. Here, (C3) ensures that any posterior mean distribution
that generates the two posterior mean values associated with the tangent
points cannot be mean preserving spread of the prior, and thus is infeasible.
Additionally, (C4) characterizes conditions on the prior $F$ to ensure that no
feasible double-interval structure can be constructed to generate posterior
means associated with any pair of tangent points, and we show that in that
case the optimal information mechanism is necessarily monotone partitional.

###  4.2 Computing optimal information mechanism

In this section, we present the approach of computing an optimal information
mechanism. We first show that any two posterior mean distributions lead to the
same revenue if they induce the same expected posterior mean value and
probability in each equilibrium regime, where the revenue function is linear.

######  Lemma 3.

For any two information mechanisms with posterior mean distribution $G$ and
$G^{\prime}$ such that for all $k=-\tilde{K},\dots,K$,

$\displaystyle\int_{s_{0}[k-1]}^{s_{0}[k]}zdG(z)=\int_{s_{0}[k-1]}^{s_{0}[k]}zdG^{\prime}(z),\quad
G(s_{0}[k])-G(s_{0}[k-1])=G^{\prime}(s_{0}[k])-G^{\prime}(s_{0}[k-1]),$

we have $R_{G}=R_{G^{\prime}}$, where $R_{G}$ ($R_{G^{\prime}}$) is the
platform’s revenue induced by the posterior mean distribution $G$ (resp.
$G^{\prime}$).

The proof of Lemma 3 leverages the fact that revenue function $R(s_{0})$ is a
continuous and piecewise linear function of $s_{0}$. Thus, the revenue only
depends on the posterior mean of the state
$y_{k}=\int_{s_{0}[k-1]}^{s_{0}[k]}zdG(z)/(G(s_{0}[k])-G(s_{0}[k-1]))$ and the
probability of inducing this posterior mean $p_{k}=G(s_{0}[k])-G(s_{0}[k-1])$
in each regime $k$, rather than the exact posterior mean distribution $G$.
That is, any two posterior mean distributions that induce the same tuples
$\\{(p_{k},y_{k})\\}_{k=-\tilde{K}}^{K}$ achieve the same revenue. The
following proposition further shows that the optimal
$\\{(p_{k},y_{k})\\}_{k=-\tilde{K}}^{K}$ can be computed by a convex
optimization program.

######  Proposition 6.

The tuple $\\{(p_{k},y_{k})\\}_{k=-\tilde{K}}^{K}$ associated with the optimal
information mechanism can be computed as an optimal solution of the following
convex program:

$\displaystyle\max_{p,y}~{}$
$\displaystyle\sum_{k=-\tilde{K}}^{K}p_{k}R(y_{k}/p_{k}),$ $\displaystyle
s.t.\quad$
$\displaystyle\sum_{j=-\tilde{K}}^{k}y_{j}\leq\int_{1-\sum_{j=-\tilde{K}}^{k}p_{j}}^{1}F^{-1}(x)dx,\quad\forall
k=-\tilde{K},\dots,K,$ (16a) $\displaystyle s_{0}[k-1]p_{k}\leq y_{k}\leq
s_{0}[k]p_{k},\quad\forall k=-\tilde{K},\dots,K,$ (16b)
$\displaystyle\sum_{k=-\tilde{K}}^{K}p_{k}=1,\quad p_{k}\geq 0,\quad\forall
k=-\tilde{K},\dots,K.$ (16c)

Proposition 6 builds on Lemma 3 and the convex optimization framework
developed in Candogan (2019). In particular, Candogan (2019) demonstrated that
the optimal information mechanism can be constructed from an optimal
$\\{(p_{k},y_{k})\\}_{k=-\tilde{K}}^{K}$, where each $k$ with probability mass
$p_{k}>0$ is associated with a posterior mean $y_{k}/p_{k}$ given the optimal
information mechanism. Moreover, the tightness of constraint (16a) indicates
whether or not each posterior mean is induced by a single pooling interval or
by a double-interval structure, and the interval thresholds can be explicitly
constructed from the optimal $\\{(p_{k},y_{k})\\}_{k=-\tilde{K}}^{K}$. The
details closely follow Candogan (2019); Candogan and Strack (2021), and are
omitted for brevity.

## References

  * Alizamir et al. [2020] Saed Alizamir, Francis de Véricourt, and Shouqiang Wang.  Warning against recurring risks: An information design approach.  _Management Science_ , 66(10):4612–4629, 2020\.
  * Arieli et al. [2023] Itai Arieli, Yakov Babichenko, Rann Smorodinsky, and Takuro Yamashita.  Optimal persuasion via bi-pooling.  _Theoretical Economics_ , 18(1):15–36, 2023.
  * Banerjee et al. [2022] Siddhartha Banerjee, Daniel Freund, and Thodoris Lykouris.  Pricing and optimization in shared vehicle systems: An approximation framework.  _Operations Research_ , 70(3):1783–1805, 2022\.
  * Bertsimas and Tsitsiklis [1997] Dimitris Bertsimas and John N Tsitsiklis.  _Introduction to linear optimization_ , volume 6.  Athena scientific Belmont, MA, 1997.
  * Bimpikis et al. [2019] Kostas Bimpikis, Ozan Candogan, and Daniela Saban.  Spatial pricing in ride-sharing networks.  _Operations Research_ , 67(3):744–769, 2019.
  * Blackwell [1953] David Blackwell.  Equivalent comparisons of experiments.  _The annals of mathematical statistics_ , pages 265–272, 1953.
  * Candogan [2019] Ozan Candogan.  Persuasion in networks: Public signals and k-cores.  In _Proceedings of the 2019 ACM Conference on Economics and Computation_ , pages 133–134, 2019.
  * Candogan [2020] Ozan Candogan.  On information design with spillovers.  _Available at SSRN 3537289_ , 2020.
  * Candogan [2022] Ozan Candogan.  Persuasion in networks: Public signals and cores.  _Operations Research_ , 70(4):2264–2298, 2022\.
  * Candogan and Drakopoulos [2020] Ozan Candogan and Kimon Drakopoulos.  Optimal signaling of content accuracy: Engagement vs. misinformation.  _Operations Research_ , 68(2):497–515, 2020.
  * Candogan and Gurkan [2023] Ozan Candogan and Huseyin Gurkan.  Value of information design in supply chain management.  _Available at SSRN 4378997_ , 2023.
  * Candogan and Strack [2021] Ozan Candogan and Philipp Strack.  Optimal disclosure of information to privately informed agents.  _Available at SSRN 3773326_ , 2021.
  * Das et al. [2017] Sanmay Das, Emir Kamenica, and Renee Mirka.  Reducing congestion through information design.  In _2017 55th annual allerton conference on communication, control, and computing (allerton)_ , pages 1279–1284. IEEE, 2017.
  * De Véricourt et al. [2021] Francis De Véricourt, Huseyin Gurkan, and Shouqiang Wang.  Informing the public about a pandemic.  _Management Science_ , 67(10):6350–6357, 2021\.
  * Dean and Kockelman [2021] Matthew D Dean and Kara M Kockelman.  Spatial variation in shared ride-hail trip demand and factors contributing to sharing: Lessons from chicago.  _Journal of Transport Geography_ , 91:102944, 2021.
  * Dong et al. [2018] Yongqi Dong, Shuofeng Wang, Li Li, and Zuo Zhang.  An empirical study on travel patterns of internet based ride-sharing.  _Transportation research part C: emerging technologies_ , 86:1–22, 2018.
  * Drakopoulos et al. [2018] Kimon Drakopoulos, Shobhit Jain, and Ramandeep S Randhawa.  Persuading customers to buy early: The value of personalized information provisioning.  _Available at SSRN 3191629_ , 2018.
  * Dworczak and Martini [2019] Piotr Dworczak and Giorgio Martini.  The simple economics of optimal persuasion.  _Journal of Political Economy_ , 127(5):1993–2048, 2019.
  * Gentzkow and Kamenica [2016] Matthew Gentzkow and Emir Kamenica.  A rothschild-stiglitz approach to bayesian persuasion.  _American Economic Review_ , 106(5):597–601, 2016\.
  * Gur et al. [2019] Yonatan Gur, Gregory Macnamara, and Daniela Saban.  On the disclosure of promotion value in platforms with learning sellers.  _arXiv preprint arXiv:1911.09256_ , 2019.
  * Johari et al. [2019] Ramesh Johari, Bar Light, and Gabriel Weintraub.  Quality selection in two-sided markets: A constrained price discrimination approach.  _arXiv preprint arXiv:1912.02251_ , 2019.
  * Kolotilin [2018] Anton Kolotilin.  Optimal information disclosure: A linear programming approach.  _Theoretical Economics_ , 13(2):607–635, 2018\.
  * Küçükgül et al. [2022] Can Küçükgül, Özalp Özer, and Shouqiang Wang.  Engineering social learning: Information design of time-locked sales campaigns for online platforms.  _Management Science_ , 68(7):4899–4918, 2022\.
  * Lingenbrink and Iyer [2018] David Lingenbrink and Krishnamurthy Iyer.  Signaling in online retail: Efficacy of public signals.  _Available at SSRN 3179262_ , 2018.
  * Lingenbrink and Iyer [2019] David Lingenbrink and Krishnamurthy Iyer.  Optimal signaling mechanisms in unobservable queues.  _Operations Research_ , 67(5):1397–1416, 2019\.  ISSN 0030-364X.  doi: 10.1287/opre.2018.1819.
  * Meigs et al. [2020] Emily Meigs, Francesca Parise, Asuman Ozdaglar, and Daron Acemoglu.  Optimal dynamic information provision in traffic routing.  _arXiv preprint arXiv:2001.03232_ , 2020.
  * Papanastasiou et al. [2018] Yiangos Papanastasiou, Kostas Bimpikis, and Nicos Savva.  Crowdsourcing exploration.  _Management Science_ , 64(4):1727–1746, 2018\.
  * Shah et al. [2022] Sohil Shah, Saurabh Amin, and Patrick Jaillet.  Optimal information provision for strategic hybrid workers.  In _2022 IEEE 61st Conference on Decision and Control (CDC)_ , pages 3807–3814. IEEE, 2022.
  * Tavafoghi and Teneketzis [2017] Hamidreza Tavafoghi and Demosthenis Teneketzis.  Informational incentives for congestion games.  In _2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , pages 1285–1292. IEEE, 2017.
  * Vasserman et al. [2015] Shoshana Vasserman, Michal Feldman, and Avinatan Hassidim.  Implementing the wisdom of waze.  In _Twenty-Fourth International Joint Conference on Artificial Intelligence_ , 2015.
  * Wu and Amin [2019] Manxi Wu and Saurabh Amin.  Information design for regulating traffic flows under uncertain network state.  In _2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , pages 671–678. IEEE, 2019.
  * Yang et al. [2019] Pu Yang, Krishnamurthy Iyer, and Peter Frazier.  Information design in spatial resource competition.  _arXiv preprint arXiv:1909.12723_ , 2019.

##  Appendix A Discussion: Computing best partitional mechanisms

In earlier sections we identified conditions under which partitional
mechanisms are optimal. In this section we focus on more general settings
where they are not optimal. Due to their simple and intuitive features, from a
practical point of view, it may still be of interest to identify the best
partitional mechanism in such settings. We provide an approach for obtaining
(near-optimal) partitional mechanisms.

To this end, we first discretize the state space that induces $\epsilon$
increments in the quantile space. We assume that we have access to an oracle
that evaluates the inverse CDF function at the desired point, though the
results go through even if these can be only approximately computed. We then
argue that the dynamic programming (DP) approach of Candogan [2020] applies in
this setting to derive the optimal partitional mechanism whose cutoffs are
restricted to these points. It is easy to see that the payoffs are Lipshitz
continuous in the cutoffs of the partitional mechanism. This, together with
the fact that our DP runs in polynomial time in $1/\epsilon$ ensures that the
resulting algorithm is a fully polynomial-time approximation scheme (FPTAS).
We first describe the approach for the single shock case, and then discuss its
extensions to the multiple shock case.

Let $c_{\ell}=F^{-1}(\epsilon\ell)$ for $k\in{\cal I}:=\\{0,\dots,\lfloor
1/\epsilon\rfloor\\}$. If $c_{\ell}\neq 1$ for any $\ell$, then let
$c_{\lfloor 1/\epsilon\rfloor+1}=1$. Define the set of feasible cutoffs as
$\\{c_{\ell}\\},$ and the associated index set by ${\cal I}$. Let $\max{\cal
I}=L$ For any $\ell_{1},\ell_{2}\in{\cal I}$ where $\ell_{1}\leq\ell_{2}$, let
$p(\ell_{1},\ell_{2})=F(c_{\ell_{2}})-F(c_{\ell_{1}})$, and
$w(\ell_{1},\ell_{2})=R\left(\mathbb{E}[s_{0}|s_{0}\in[c_{\ell_{1}},c_{\ell_{2}}]\right)\bigg{/}p(\ell_{1},\ell_{2})$.
Suppose that we choose indices ${\cal
I}_{c}=\\{\ell_{0},\ell_{1},\dots,\ell_{K}\\}\subseteq{\cal I}$ with
$\ell_{0}=0$, $\ell_{K}=L$. In this case, it can be seen that the expected
payoff of the designer can be expressed as
$\sum_{k=1}^{K}w(\ell_{k-1},\ell_{k})$. It can be readily seen that any
feasible partitional mechanism (with cutoffs in $\\{c_{k}\\}_{k\in{\cal I}}$)
can be associated with an index set of the type ${\cal I}_{c}$, the problem
reduces to finding the best such set.

However, this problem can naturally be formulated as a DP. Specifically,
suppose that we sequentially add indices to ${\cal I}_{c}$ starting with
$\\{L\\}$, at each step adding a new index that is smaller than the previously
added ones, and stopping once index $0=\min{\cal I}$ is added to ${\cal
I}_{c}$. Suppose we have a set ${\cal I}_{c}=\\{\ell_{k+1},\dots,\ell_{K}\\}$
with $\ell_{k+1}<\dots<\ell_{K}=L$, of indices that are already chosen, and
suppose that we next add index $\ell_{k}<\ell_{k+1}$ to ${\cal I}_{c}$. Denote
the stage payoff for adding an index $\ell_{k}$ to the current set by
$w(\ell_{k},\ell_{k+1})$, and denote the continuation payoff by $V(\ell_{k})$.
It can be readily seen that the objective value associated with the optimal
mechanism (with cutoffs in $\\{c_{k}\\}_{k\in{\cal I}}$) is $V(L)$, and we
have the following Bellman equation:

$V(\ell_{k})=\max_{\ell<\ell_{k}|\ell\in{\cal I}}V(\ell)+w(\ell,\ell_{k}).$
(17)

This equation can be solved via standard dynamic programming techniques, and
yield the optimal partitional mechanism with cutoffs restricted to ${\cal I}$,
which in turn yields an FPTAS as explained earlier.111111See Candogan [2020]
for a detailed algorithm description. The aforementioned paper’s algorithm
also applies in richer settings where different groups of agents have access
to different signals, and information can spill over from one agent to another
according to an underlying communication network.

In the discussion above, we did not specify which of the assumptions
(Assumption 1,2, 3) should be imposed. This is deliberate. If these
assumptions hold, then the $R(\cdot)$ function can be obtained in closed form,
and it can be used to construct $w(\cdot,\cdot)$ as described earlier.
Otherwise, for any $\ell_{1},\ell_{2}\in{\cal I}$ and the posterior mean level
$\mathbb{E}[s_{0}|s_{0}\in[c_{\ell_{1}},c_{\ell_{2}}]]$ we can solve the
optimization formulation in Proposition 1 to obtain the distribution of agents
for different posterior mean levels that are induced by partitional mechanisms
with cutoffs in $\\{c_{\ell}\\}_{\ell\in{\cal I}}$. We then evaluate the
induced revenue. After solving these auxiliary optimization problems we
evaluate the $R(\cdot)$ function at all relevant posterior mean levels and, in
turn, construct the $w(\cdot,\cdot)$ function.

We next extend our approach to the multiple shock case. To start, we need to
extend the definition of partitional information structures to the multiple
shock case. A natural idea is to choose partitions for each $\\{S_{i}\\}$
separately, and reveal the partition elements to which each $S_{i}$ belongs.
However, there is a fundamental difficulty: The number of possible signal
realizations grows exponentially in the number of shock centers, thereby
leading to computational difficulties when large number of nodes are impacted
by shocks. This is to some extent expected, since in the aforementioned
settings the designer’s payoff is piecewise linear with exponentially many
pieces, and solving an optimization involving such a rich class of functions
is nontrivial.

That said, there is a practically relevant version of the problem that is also
tractable. Specifically, suppose that we have finitely many scenarios
$\\{\sigma_{k}\\}_{k\in\Sigma}$ and an associated probability distribution
$\\{\rho_{k}\\}_{k\in\Sigma}$, where $\Sigma=\\{1,\dots,D\\}$. Associated with
scenario $k$ is a fixed shock vector $\nu^{k}$, and random variable
$\theta^{k}$ with distribution $F^{k}$. When this scenario is realized the
price curve in node $i$ takes the form

$p_{i}(q_{i})=s_{i}+\theta^{k}\nu^{k}_{i}.$

In other words, when this scenario is realized the intercept of the price
curve in each node is perturbed according to the vector $\nu^{k}$. Note that
we do not make any restrictions on the entries of $\nu^{k}$. For instance,
multiple entries can be nonzero, e.g., capturing the fact that multiple nodes
simultaneously experience varying degrees of shocks (which in the ride-sharing
application can capture some regions of the city jointly experiencing demand
shocks, e.g., due to weather events or special events leading to demand surge
in a wide area). We also allow for negative entries/shocks (that in the ride-
sharing application can capture reduced demand in some areas while others are
experiencing increased demand, e.g., due to shocks in the public transit
system).

As before, we discretize the support of each $\theta^{k}$ in a way that leads
to $\epsilon$ increments in the quantile space. Denote the corresponding
cutoffs for scenario $k$ by $\\{c^{k}_{\ell}\\}_{\ell}$, and the associated
index set by ${\cal I}^{k}$. For each scenario $k$, and indices
$\ell_{1},\ell_{2}\in{\cal I}^{k}$, we compute the induced payoff of the
platform when the posterior mean vector is
$\mathbb{E}_{F^{k}}[s+\theta^{k}\nu^{k}|\theta^{k}\in[c_{\ell_{1}},c_{\ell_{2}}]]$.
While, unlike the single shock case, this quantity is not possible to obtain
in closed form, Proposition 1 still applies to characterize equilibrium agent
distribution for each scenario and pairs of discretization indices
$(k,\ell_{1},\ell_{2})$.

We once again focus on partitional mechanisms. However, note that without the
knowledge of the underlying scenario, the partitional structure is not very
intuitive or practical.121212For instance, suppose that two scenarios
represent demand surging in two different parts of the city. Without revealing
which scenario is realized it is not meaningful to reveal that the demand is
in top, say, 20% of the possible levels. Motivated by this, we restrict
attention to mechanisms that (i) reveal the scenario that is realized, and
(ii) use partitional information structures to map state realization to
signals for each scenario.

It can be readily seen that for such mechanisms, the design problem decouples
over different scenarios. That is, the partition chosen for one scenario has
no impact on the payoff obtained when another scenario is realized. As such,
for each scenario we have a DP recursion of the type (17), where $V(\cdot)$
and $w(\cdot,\cdot)$ (and more fundamentally the revenue function $R(\cdot)$)
are now scenario-specific.

In short, the DP approached introduced earlier readily extends to multiple
demand shock scenarios. This gives a simple and computationally efficient
recipe for constructing practically relevant information disclosure
mechanisms.

##  Appendix B Proofs of statements in Sections 2

_Proof of Proposition 1._ For any $t\in\mathcal{T}$, $\Phi(x|t)$ is a
potential function since:

$\displaystyle\frac{d\Phi(x|t)}{dx_{ij(t)}}=(1-r)(\mathbb{E}[s_{j}|t]-\beta_{j}q_{j}(t))-c_{ij}=u_{ij}(x|t),\quad\forall
i,j\in V.$

Therefore, following , we know that $x^{*}$ is a maximizer of the potential
function.

Moreover, given any $q^{*}(t)$, since the associated equilibrium strategy
$x^{*}(t)$ maximizes the potential function, $x^{*}(t)$ must be an optimal
solution of the following problem:

$\begin{split}\min_{x}\quad&\sum_{i,j\in V}c_{ij}x_{ij}(t),\\\
s.t.\quad&\sum_{i\in V}x_{ij}(t)=q^{*}_{j}(t),\quad\forall j\in V,\\\
&\sum_{j\in V}x_{ij}(t)=m_{i},\quad\forall i\in V,\\\ &x_{ij}(t)\geq
0,\quad\forall i,j\in V.\end{split}$ (18)

From the duality theory, the optimal value $\psi(q^{*}|t)=\sum_{i,j\in
V}c_{ij}x^{*}_{ij}(t)$ is a convex function of $q^{*}(t)$ (Theorem 5.1 on page
213 in Bertsimas and Tsitsiklis [1997]). Moreover, we denote
$\phi(q|t)=(1-r)\sum_{i\in
V}\int_{0}^{q_{i}(t)}(\mathbb{E}[s_{i}|t]-\beta_{j}z)dz$ note that

$\displaystyle\frac{\partial^{2}\phi(q|t)}{\partial q_{i}\partial
q_{j}}=\left\\{\begin{array}[]{ll}-(1-r)\beta_{i},&\quad i=j,\\\ 0,&\quad
i\neq j.\end{array}\right.$

That is, $\phi(q|t)$ is strictly concave in $q$. We can re-write the potential
function as a function of $q$, $\phi(q|t)-\psi(q|t)$, which is strictly
concave in $q$. Thus, the equilibrium agents’ distribution $q^{*}(t)$ is
unique for all $t\in\mathcal{T}$. $\square$

_Proof of Proposition 2._ We note that the feasible set of the optimization
problem (6) associated with $F^{\prime}$ is super set of that associated with
$F$. Therefore, $R_{G^{{}^{\prime}*}}\geq R_{G^{*}}$, where $G^{{}^{\prime}*}$
(resp. $G^{*}$) is the optimal posterior mean distribution given prior
$F^{\prime}$ (resp. $F$). Moreover, since
$\mathbb{E}_{F}[s_{0}]=\mathbb{E}_{F^{\prime}}[s_{0}]$, we have
$R_{F}=R(\mathbb{E}_{F}[s_{0}])=R(\mathbb{E}_{F^{\prime}}[s_{0}])=R_{F^{\prime}}$.
Therefore, $V^{*}_{F}\leq V^{*}_{F^{\prime}}$. $\square$

##  Appendix C Equilibrium characterization for the single shock case

In this section, we provide a complete equilibrium characterization for the
single shock case under Assumption 3.

The following lemma demonstrates structural properties of equilibrium strategy
profile and agents’ distribution. In particular, for any
$s_{0}>\mathbb{E}_{F}[s_{0}]$, that there exists an equilibrium strategy
profile such that the nodes in the network are partitioned into three sets
$V=(V\setminus\Gamma)\cup(\Gamma\setminus\Gamma^{\dagger})\cup\Gamma^{\dagger}$,
where agents from $i\in(V\setminus\Gamma)$ do not move, a fraction of agents
from $i\in(\Gamma\setminus\Gamma^{\dagger})$ move to node $0$ and the rest
stay at node $i$, and all agents from $i\in\Gamma^{\dagger}$ move to node $0$
in equilibrium. Additionally, for any $s_{0}<\mathbb{E}_{F}[s_{0}]$, nodes are
partitioned into two sets $V=(V\setminus\tilde{\Gamma})\cup\tilde{\Gamma}$
such that agents from node $i$ move to nodes in $\tilde{\Gamma}$, and agents
from the rest of the network do not move.

######  Lemma 4.

For any $s_{0}>\mathbb{E}_{F}[s_{0}]$, the unique agents’ distribution in
equilibrium $q^{*}$ satisfies:

$\displaystyle
q^{*}_{i}=\frac{1}{\beta_{i}}\left(s_{i}-s_{0}+\frac{d_{i}}{1-r}\right)+\frac{\beta_{0}}{\beta_{i}}q^{*}_{0}\in(0,m_{i}),\quad\forall
i\in\Gamma\setminus\Gamma^{\dagger},$ (19a) $\displaystyle
q^{*}_{i}=0,\quad\forall i\in\Gamma^{\dagger},$ (19b) $\displaystyle
q^{*}_{i}=m_{i},\quad\forall i\in V\setminus\\{\Gamma\cup\\{0\\}\\},$ (19c)

where

$\displaystyle\Gamma=\\{V|(1-r)(s_{i}-\beta_{i}m_{i})+d_{i}<(1-r)(s_{0}-\beta_{0}q^{*}_{0})\\},$
(20a)
$\displaystyle\Gamma^{\dagger}=\\{V|(1-r)s_{i}+d_{i}\leq(1-r)(s_{0}-\beta_{0}q^{*}_{0})\\},$
(20b)

and there exists an equilibrium strategy profile such that

$\displaystyle x^{*}_{00}=m_{0},\quad x^{*}_{i0}=m_{i}-q^{*}_{i},\quad
x^{*}_{ii}=q^{*}_{i},\quad x^{*}_{ij}=0,\quad\forall i\in
V\setminus\\{0\\},\quad\forall j\in V\setminus\\{0,i\\}.$ (21)

For any $s_{0}<\mathbb{E}_{F}[s_{0}]$, the unique agents’ distribution in
equilibrium $q^{*}$ satisfies:

$\displaystyle
q^{*}_{i}=\frac{1}{\beta_{i}}\left(s_{i}-s_{0}-\frac{d_{i}}{1-r}\right)+\frac{\beta_{0}}{\beta_{i}}q^{*}_{0}>m_{i},\quad\forall
i\in\tilde{\Gamma},$ (22a) $\displaystyle q^{*}_{i}=m_{i},\quad\forall i\in
V\setminus\\{\tilde{\Gamma}\cup\\{0\\}\\},$ (22b)

where

$\displaystyle\tilde{\Gamma}=\\{V|(1-r)(s_{i}-\beta_{i}m_{i})-d_{i}>(1-r)(s_{0}-\beta_{0}q^{*}_{0})\\},$
(23)

and there exists an equilibrium strategy profile such that

$\displaystyle x^{*}_{0i}$ $\displaystyle=q^{*}_{i}-m_{i},\quad\forall
i\in\tilde{\Gamma},\quad x^{*}_{0i}=0,\quad\forall i\in
V\setminus\\{0\cup\tilde{\Gamma}\\},\quad x^{*}_{00}=q^{*}_{0},$ (24a)
$\displaystyle x^{*}_{ii}$ $\displaystyle=m_{i},\quad\forall i\in
V\setminus\\{0\\},\quad x^{*}_{ij}=0,\quad\forall j\in V\setminus\\{0,i\\}.$
(24b)

Furthermore, $q^{*}_{0}$ increases in $s_{0}$.

_Proof of Lemma 4._ We first prove that given any
$s_{0}>\mathbb{E}_{F}[s_{0}]$, agents originating from all nodes do not have
incentive to deviate from their equilibrium strategy $x^{*}$ as in (21) given
$q^{*}$ in (19). We first note that $q^{*}$ as in (19) ensures that

$\displaystyle(1-r)(s_{i}-\beta_{i}q^{*}_{i})=(1-r)(s_{0}-\beta_{0}q^{*}_{0})-d_{i},\quad\forall
i\in\Gamma\setminus\Gamma^{\dagger}.$ (25)

(1) For any $i\in V\setminus\\{\Gamma\cup\\{0\\}\\}$, we note that the payoff
of staying at node $i$ is
$(1-r)(s_{i}-\beta_{i}q^{*}_{i})=(1-r)(s_{i}-\beta_{i}m_{i})$, which is higher
or equal to $(1-r)(s_{0}-\beta_{0}q^{*}_{0})-d_{i}$ – the expected payoff of
moving to node $0$. Thus, agents at node $i$ has no incentive to move to node
$0$ in equilibrium. Additionally, following (25), we have

$\displaystyle(1-r)(s_{j}-\beta_{j}q^{*}_{j})-c_{ij}$
$\displaystyle=(1-r)(s_{0}-\beta_{0}q^{*}_{0})-d_{j}-c_{ij}\stackrel{{\scriptstyle(a)}}{{\leq}}(1-r)(s_{0}-\beta_{0}q^{*}_{0})-d_{i}$
$\displaystyle\leq(1-r)(s_{i}-\beta_{i}m_{i})=(1-r)(s_{i}-\beta_{i}q^{*}_{i}),\quad\forall
j\in\Gamma,$

where (a) is due to the triangular inequality of distances, i.e. $d_{i}\leq
d_{j}+c_{ij}$ for any $i,j\in V$. Therefore, agents at node $i\in
V\setminus\\{\Gamma\cup\\{0\\}\\}$ have no incentive to move to any node in
$\Gamma\setminus\Gamma^{\dagger}$. Furthermore, for any
$j\in\Gamma^{\dagger}$,

$\displaystyle(1-r)(s_{j}-\beta_{j}q^{*}_{j})-c_{ij}$
$\displaystyle=(1-r)s_{j}-c_{ij}\leq(1-r)(s_{0}-\beta_{0}q^{*}_{0})-d_{j}-c_{ij}\leq(1-r)(s_{0}-\beta_{0}q^{*}_{0})-d_{j}$
$\displaystyle\leq(1-r)(s_{i}-\beta_{i}m_{i})=(1-r)(s_{i}-\beta_{i}q^{*}_{i}),\quad\forall
j\in\Gamma^{\dagger}.$

Thus, agents originating from node $i$ have no incentive to move to any node
$j\in\Gamma^{\dagger}$. Additionally, we know from Assumption 3 that agents at
$i$ have no incentive to move to any node $j\in
V\setminus\\{\Gamma\cup\\{0\\}\\}$, where the equilibrium agent distribution
$q^{*}_{j}=m_{j}$. Thus, we conclude that agents originating from node $i\in
V\setminus\\{\Gamma\cup\\{0\\}\\}$ have no incentive to move to any node in
$V$, i.e. have no incentive to deviate given the equilibrium strategy profile
in (19) and (21).

(2) For any $i\in\Gamma\setminus\Gamma^{\dagger}$, we know from (25) and (20a)
that

$(1-r)(s_{i}-\beta_{i}q^{*}_{i})=(1-r)(s_{0}-\beta_{0}q^{*}_{0})-d_{i}>(1-r)(s_{i}-\beta_{i}m_{i}),$

and thus $q^{*}_{i}<m_{i}$. Additionally, since $i\notin\Gamma^{\dagger}$,

$(1-r)s_{i}>(1-r)(s_{0}-\beta_{0}q^{*}_{0})-d_{i}=(1-r)(s_{i}-\beta_{i}q^{*}_{i}),$

we have $q^{*}_{i}>0$. Thus, we have proved that $x^{*}_{i}\in(0,m_{i})$
indicating that agents originating from node
$i\in\Gamma\setminus\Gamma^{\dagger}$ split between staying at $i$ and moving
to node $0$. We know from (25) that indeed agents are indifferent between
staying at node $i$ and moving to $0$. It remains to show that agents at $i$
do not strictly prefer to move to any other node $j\in V\setminus\\{0,i\\}$.
We note that agents do not strictly prefer to move to any node
$j\in\Gamma\setminus\Gamma^{\dagger}$ since

$\displaystyle(1-r)(s_{i}-\beta_{i}q^{*}_{i})$
$\displaystyle=(1-r)(s_{0}-\beta_{0}q^{*}_{0})-d_{i}=(1-r)(s_{j}-\beta_{j}q^{*}_{j})+d_{j}-d_{i}$
$\displaystyle\geq(1-r)(s_{j}-\beta_{j}q^{*}_{j})-|d_{i}-d_{j}|\geq(1-r)(s_{j}-\beta_{j}q^{*}_{j})-c_{ij},$

where the last inequality arises from the triangular inequality. Similarly,
agents do not strictly prefer to move to any $j\in\Gamma^{\dagger}$ since

$\displaystyle(1-r)(s_{i}-\beta_{i}q^{*}_{i})$
$\displaystyle=(1-r)(s_{0}-\beta_{0}q^{*}_{0})-d_{i}\geq(1-r)s_{j}+d_{j}-d_{i}=(1-r)(s_{j}-\beta_{j}q^{*}_{j})+d_{j}-d_{i}$
$\displaystyle\geq(1-r)(s_{j}-\beta_{j}q^{*}_{j})-|d_{i}-d_{j}|\geq(1-r)(s_{j}-\beta_{j}q^{*}_{j})-c_{ij},\quad\forall
j\in\Gamma^{\dagger}.$

Finally, since $q^{*}_{i}\leq m_{i}$, we know that the payoff of staying at
node $i$ with $q^{*}_{i}$ is no less than the payoff with the original agent
mass $m_{i}$. Since agents at node $i$ have no incentive to move to any $j\in
V\setminus\\{\Gamma\cup\\{0\\}\\}$, and the price at node $j$ does not change
after the repositioning, we know that agents at node $i$ have no incentive to
move to node $j\in V\setminus\\{\Gamma\cup\\{0\\}\\}$. We can thus conclude
that agents at node $i$ do not strictly prefer to move to any node $j\in
V\setminus\\{0,i\\}$, and hence $x^{*}$ and $q^{*}$ are equilibrium for agents
at node $i$.

(3) For any $i\in\Gamma^{\dagger}$, (19) and (21) indicate that all agents
move from $i$ to 0 in equilibrium. We note that agents do not strictly prefer
to move to other nodes $j\in\Gamma\setminus\Gamma^{\dagger}$:

$\displaystyle(1-r)(s_{0}-\beta_{0}q^{*}_{0})-d_{i}=(1-r)(s_{j}-\beta_{j}q^{*}_{j})+d_{j}-d_{i}\geq(1-r)(s_{j}-\beta_{j}q^{*}_{j})-c_{ij},\quad\forall
j\in\Gamma\setminus\Gamma^{\dagger}.$

or $j\in\Gamma^{\dagger}$:

$\displaystyle(1-r)(s_{0}-\beta_{0}q^{*}_{0})-d_{i}>(1-r)(s_{j}-\beta_{j}q^{*}_{j})+d_{j}-d_{i}\geq(1-r)(s_{j}-\beta_{j}q^{*}_{j})-c_{ij},\quad\forall
j\in\Gamma^{\dagger}.$

Moreover, agents also do not prefer to move to nodes $j\in V\setminus\Gamma$
since

$\displaystyle(1-r)(s_{i}-\beta_{i}q^{*}_{i})=(1-r)s_{i}>(1-r)(s_{i}-\beta_{i}m_{i})\geq(1-r)(s_{j}-\beta_{j}m_{j})-c_{ij}\quad\forall
j\in V\setminus\Gamma,$

where the last inequality follows from Assumption 3.

(4) For agents at node $0$, we know from (25) that the payoff of staying at
node $0$ is higher than moving to any node
$i\in\Gamma\setminus\Gamma^{\dagger}$. Following analogous argument as in (1),
we know that agents from node $i$ also do not have incentive to move to nodes
in $\Gamma^{\dagger}$ and nodes in $V\setminus\\{\Gamma\cup\\{0\\}\\}$.

From (1) - (4), we conclude that no agents have strict incentive to deviate
given $q^{*}$ and $x^{*}$ as in (19) and (21). Thus, $q^{*}$ and $x^{*}$ are
the agents’ equilibrium distribution and equilibrium strategy profile.

Similarly, we prove that given any $s_{0}<\mathbb{E}_{F}[s_{0}]$, $q^{*}$ as
in (22) is the agents’ distribution in equilibrium and $x^{*}$ in (24) is an
associated equilibrium strategy profile by showing that agents originating
from all nodes do not have incentive to deviate.

(i) For any $i\in V\setminus\tilde{\Gamma}$, we note that the payoff of
staying at node $0$, $(1-r)(s_{0}-\beta_{0}q^{*}_{0})$, is higher or equal to
$(1-r)(s_{i}-\beta_{i}q^{*}_{i})-d_{i}$, i.e. the expected payoff of moving to
node $i$. Thus, agents from node $0$ have no incentive to move to node $i\in
V\setminus\tilde{\Gamma}$ in equilibrium. Additionally, we note that $q^{*}$
as in (22) ensures that

$\displaystyle(1-r)(s_{i}-\beta_{i}q^{*}_{i})-d_{i}=(1-r)(s_{0}-\beta_{0}q^{*}_{0}),\quad\forall
i\in\tilde{\Gamma}.$ (26)

That is, agents from node $0$ are indifferent between staying at node $0$ or
moving to a node $i\in\tilde{\Gamma}$. Thus, $x^{*}_{0}$ as in (24) is
equilibrium strategy for agents from node $0$.

(ii) For any $i\in\tilde{\Gamma}$, agents from $i$ do not strictly prefer to
move to any other nodes $j\in\tilde{\Gamma}$ compared to staying at node $i$
since

$\displaystyle(1-r)(s_{j}-\beta_{j}q^{*}_{j})-c_{ij}$
$\displaystyle=(1-r)(s_{0}-\beta_{0}q^{*}_{0})+d_{j}-c_{ij}\leq(1-r)(s_{0}-\beta_{0}q^{*}_{0})+d_{i}$
$\displaystyle=(1-r)(s_{i}-\beta_{i}m_{i}),\quad\forall j\in\Gamma,$

Moreover, agents also do not strictly prefer to move to any $j\in
V\setminus\tilde{\Gamma}$ since

$\displaystyle(1-r)(s_{j}-\beta_{j}q^{*}_{j})-c_{ij}$
$\displaystyle\leq(1-r)(s_{0}-\beta_{0}q^{*}_{0})+d_{j}-c_{ij}\leq(1-r)(s_{0}-\beta_{0}q^{*}_{0})+d_{i}$
$\displaystyle=(1-r)(s_{i}-\beta_{i}m_{i}),\quad\forall j\in
V\setminus\tilde{\Gamma}.$

Thus, agents originating from node $i$ have no incentive to move to any other
node in $V\setminus\\{i\\}$, i.e. $x^{*}_{ii}=m_{i}$ is an equilibrium
strategy. Additionally, since
$(1-r)(s_{i}-\beta_{i}m_{i})>(1-r)(s_{0}-\beta_{0}q^{*}_{0})+d_{i}$ and
$(1-r)(s_{i}-\beta_{i}q^{*}_{i})=(1-r)(s_{0}-\beta_{0}q^{*}_{0})+d_{i}$, we
know that $q^{*}_{i}>m_{i}$ for all $i\in\tilde{\Gamma}$.

(iii) For any $i\in V\setminus\tilde{\Gamma}$, we know from Assumption 3 that
agents from $i$ do not strictly prefer to move to $j\in
V\setminus\tilde{\Gamma}$. Additionally, since agents from $i$ do not strictly
prefer to move to $j\in\tilde{\Gamma}\cup\\{0\\}$ with the initial agent
distribution $m_{i}$ and $q^{*}_{j}>m_{j}$, agents also do not strictly prefer
to move to $j\in\tilde{\Gamma}\setminus\\{0\\}$ in equilibrium. Thus,
$x^{*}_{ii}=m_{i}$ is an equilibrium strategy for $i\in\tilde{\Gamma}$.

From (i) - (iii), we conclude that no agents have strict incentive to deviate
given $q^{*}$ and $x^{*}$ as in (22) and (24). Thus, $q^{*}$ and $x^{*}$ are
indeed equilibrium agents’ equilibrium distribution and equilibrium strategy
profile.

Finally, we prove that $q^{*}_{0}$ is increasing in $s_{0}$. Consider any
$s_{0}<s^{\prime}_{0}$. We denote the equilibrium agents’ distribution at node
$0$ associated with $s_{0}$ and $s^{\prime}_{0}$ as $q^{*}_{0}$ and
$q^{*^{\prime}}_{0}$, respectively. For any
$s_{0}<\mathbb{E}_{F}[s_{0}]<s^{\prime}_{0}$, we must have
$q^{*}_{0}<m_{0}<q^{*^{\prime}}_{0}$. For any
$\mathbb{E}_{F}[s_{0}]<s_{0}<s^{\prime}_{0}$, we assume for the sake of
contradiction that $q^{*^{\prime}}_{0}<q^{*}_{0}$. From (19) and (20a), we
know that $\Gamma\subseteq\Gamma^{\prime}$, and $q^{*}_{i}\geq
q^{*^{\prime}}_{i}$ for all $i\in\Gamma$. Therefore,

$\sum_{i\in\Gamma}m_{i}=q^{*}_{0}+\sum_{i\in\Gamma}q^{*}_{i}>q^{*^{\prime}}_{0}+\sum_{i\in\Gamma}q^{*^{\prime}}_{i}\geq\sum_{i\in\Gamma}m_{i},$

which is a contradiction. Thus, we must have $q^{*^{\prime}}_{0}\geq
q^{*}_{0}$.

Analogously, for any $s_{0}<s^{\prime}_{0}<\mathbb{E}_{F}[s_{0}]$, we assume
for the sake of contradiction that $q^{*^{\prime}}_{0}<q^{*}_{0}$. From (22)
and (23), we know that $\tilde{\Gamma}\supseteq\tilde{\Gamma}^{\prime}$, and
$q^{*^{\prime}}_{i}<q^{*}_{i}$ for all $i\in\Gamma^{\prime}_{-}$. Therefore,

$\sum_{i\in\tilde{\Gamma}^{\prime}}m_{i}\geq
q^{*}_{0}+\sum_{i\in\tilde{\Gamma}^{\prime}}q^{*}_{i}>q^{*^{\prime}}_{0}+\sum_{i\in\tilde{\Gamma}^{\prime}}q^{*^{\prime}}_{i}=\sum_{i\in\tilde{\Gamma}^{\prime}}m_{i},$

which is a contradiction. Thus, we must have $q^{*^{\prime}}_{0}\geq
q^{*}_{0}$. We conclude that $q^{*}_{0}$ is increasing in $s_{0}$. $\square$

From Lemma 4, we know that as $s_{0}$ increases above $\mathbb{E}_{F}[s_{0}]$,
$q^{*}_{0}$ increases, and consequently the sets $\Gamma$ and
$\Gamma^{\dagger}$ as in (20) are non-decreasing. On the other hand, as
$s_{0}$ decreases below $\mathbb{E}_{F}[s_{0}]$, the set $\tilde{\Gamma}$ is
non-decreasing. Based on this lemma, we construct Algorithm 2 to generate the
sequence of $\Gamma$ and $\Gamma^{\dagger}$ associated with the increasing
$s_{0}$, and Algorithm 3 to generate the sequence of $\tilde{\Gamma}$
associated with the decreasing $s_{0}$ below $\mathbb{E}_{F}[s_{0}]$. In each
algorithm, we compute the interval of $s_{0}$ such that $\Gamma$,
$\Gamma^{\dagger}$, and $\tilde{\Gamma}$ are associated with the support set
of equilibrium strategies.

$k\leftarrow 0$, $\Gamma[0]\leftarrow\emptyset$,
$\Gamma^{\dagger}[0]\leftarrow\emptyset$,
$s_{0}[k]\leftarrow\mathbb{E}_{F}[s_{0}]$.

while  _$\Gamma^{\dagger}[k]\neq V\setminus\\{0\\}$_ do

$\displaystyle\tau_{1}\leftarrow\min_{i\in
V\setminus\Gamma[k]}\\{(1-r)(s_{i}-\beta_{i}m_{i})+d_{i}\\},\quad\tau_{2}\leftarrow\min_{i\in\Gamma[k]\setminus\Gamma^{\dagger}[k]}\\{(1-r)s_{i}+d_{i}\\}$
(27) if  _$\tau_{1} <\tau_{2}$_ then

$\displaystyle
s_{0}[k+1]=\frac{\tau_{1}\beta_{0}}{1-r}\left(\sum_{i\in\Gamma^{\dagger}[k]}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)+\beta_{0}\left(m_{0}+\sum_{i\in\Gamma[k]}m_{i}-\sum_{i\in\Gamma^{\dagger}[k]}\frac{1}{\beta_{i}}\left(s_{i}+\frac{d_{i}}{1-r}\right)\right).$
(28) $\Gamma[k+1]\leftarrow\Gamma[k]\cup\operatorname*{arg\,min}_{i\in
V\setminus\Gamma[k]}\\{(1-r)(s_{i}-\beta_{i}m_{i})+d_{i}\\}$,
$\Gamma^{\dagger}[k+1]\leftarrow\Gamma^{\dagger}[k]$

else if  _$\tau_{1} >\tau_{2}$_ then

$\displaystyle
s_{0}[k+1]=\frac{\tau_{2}\beta_{0}}{1-r}\left(\sum_{i\in\Gamma^{\dagger}[k]}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)+\beta_{0}\left(m_{0}+\sum_{i\in\Gamma[k]}m_{i}-\sum_{i\in\Gamma^{\dagger}[k]}\frac{1}{\beta_{i}}\left(s_{i}+\frac{d_{i}}{1-r}\right)\right).$
(29) $\Gamma[k+1]\leftarrow\Gamma[k]$,
$\Gamma^{\dagger}[k+1]\leftarrow\Gamma^{\dagger}[k]\cup\operatorname*{arg\,min}_{i\in\Gamma^{\dagger}[k]}\\{(1-r)s_{i}+d_{i}\\}$

else

$\displaystyle
s_{0}[k+1]=\frac{\tau_{1}\beta_{0}}{1-r}\left(\sum_{i\in\Gamma^{\dagger}[k]}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)+\beta_{0}\left(m_{0}+\sum_{i\in\Gamma[k]}m_{i}-\sum_{i\in\Gamma^{\dagger}[k]}\frac{1}{\beta_{i}}\left(s_{i}+\frac{d_{i}}{1-r}\right)\right)$
(30) $\Gamma[k+1]\leftarrow\Gamma[k]\cup\operatorname*{arg\,min}_{i\in
V\setminus\Gamma[k]}\\{(1-r)(s_{i}-\beta_{i}m_{i})+d_{i}\\}$

$\Gamma^{\dagger}[k+1]\leftarrow\Gamma^{\dagger}[k]\cup\operatorname*{arg\,min}_{i\in\Gamma^{\dagger}[k]}\\{(1-r)s_{i}+d_{i}\\}$

$k\leftarrow k+1$

$K_{\mathrm{max}}\leftarrow k$

Output: $K_{\mathrm{max}}$,
$\\{\Gamma[k],\Gamma^{\dagger}[k],s_{0}[k]\\}_{k=1}^{K_{\mathrm{max}}}$

ALGORITHM 2 Computation of
$\\{\Gamma[k],\Gamma^{\dagger}[k],s_{0}[k]\\}_{k=1}^{K_{\mathrm{max}}}$.

$k\leftarrow 0$, $\tilde{\Gamma}[0]\leftarrow\emptyset$,
$s_{0}[0]\leftarrow\mathbb{E}_{F}[s_{0}]$.

while  _$\tilde{\Gamma}[-k]\neq V\setminus\\{0\\}$_ do

$\tau\leftarrow\max_{i\in
V\setminus\tilde{\Gamma}[-k]}\\{(1-r)(s_{i}-\beta_{i}m_{i})-d_{i}\\}$

$\displaystyle
s_{0}[-k-1]=\frac{\tau\beta_{0}}{1-r}\left(\sum_{i\in\tilde{\Gamma}[-k]}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)+\beta_{0}\left(m_{0}+\sum_{i\in\tilde{\Gamma}[-k]}m_{i}-\sum_{i\in\tilde{\Gamma}[-k]}\frac{1}{\beta_{i}}\left(s_{i}-\frac{d_{i}}{1-r}\right)\right).$
(31)

if  _
$s_{0}[-k-1]\leq\frac{1}{\sum_{i\in\tilde{\Gamma}[-k]}\frac{1}{\beta_{i}}}\left(-m_{0}+\sum_{i\in\tilde{\Gamma}[-k]}\frac{1}{\beta_{i}}\left(s_{i}-\frac{d_{i}}{1-r}-m_{i}\beta_{i}\right)\right)$
_ then

$s_{0}[-k-1]\leftarrow\frac{1}{\sum_{i\in\tilde{\Gamma}[-k]}\frac{1}{\beta_{i}}}\left(-m_{0}+\sum_{i\in\tilde{\Gamma}[-k]}\frac{1}{\beta_{i}}\left(s_{i}-\frac{d_{i}}{1-r}-m_{i}\beta_{i}\right)\right)$

$k\leftarrow k+1$

break

else

$\tilde{\Gamma}[-k-1]\leftarrow\tilde{\Gamma}[-k]\cup\operatorname*{arg\,max}_{i\in
V\setminus\tilde{\Gamma}[-k]}\\{(1-r)(s_{i}-\beta_{i}m_{i})-d_{i}\\}$

$k\leftarrow k+1$

$\tilde{K}_{\mathrm{max}}\leftarrow k$

Output: $\tilde{K}_{\mathrm{max}}$,
$\\{\tilde{\Gamma}[-k],s_{0}[-k]\\}_{k=1}^{\tilde{K}_{\mathrm{max}}}$

ALGORITHM 3 Computation of
$\\{\tilde{\Gamma}[-k],s_{0}[-k]\\}_{k=1}^{\tilde{K}_{\mathrm{max}}}$.

Based on the outputs of the two algorithms, we next characterize the
equilibrium regimes in our problem.

######  Proposition 7.

Under Assumptions 3, the equilibrium agent distribution $q^{*}(s_{0})$ and
platform’s revenue $R(s_{0})$ are piecewise linear functions of the posterior
state mean $s_{0}$, and exhibit $K+\tilde{K}+1$ regimes, where

$\displaystyle K$
$\displaystyle=\max\left\\{k=1,\dots,K_{\mathrm{max}}\left|~{}s_{0}[k]\leq\sup
S_{0}\right.\right\\},\quad\tilde{K}=\max\left\\{k=1,\dots,\tilde{K}_{\mathrm{max}}\left|~{}s_{0}[-k]\geq\inf
S_{0}\right.\right\\}.$

Regime 0: $s_{0}[-1]\leq s_{0}<s_{0}[1]$.

$\displaystyle q^{*}_{i}(s_{0})$ $\displaystyle=m_{i},\quad\forall i\in V,$
(32)

and in the interior of regime 0,

$\frac{dR(s_{0})}{ds_{0}}=rm_{0}.$

Regime $\\{k\\}_{k=1}^{K}$: $s_{0}[k]\leq s_{0}<s_{0}[k+1]$ with
$s_{0}[K+1]=\sup S_{0}$.

$\displaystyle q^{*}_{0}(s_{0})$
$\displaystyle=\frac{1}{\beta_{0}\left(\sum_{i\in\Gamma^{\dagger}[k]}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}\left(m_{0}+\sum_{i\in\Gamma[k]}m_{i}+\sum_{i\in\Gamma^{\dagger}[k]}\frac{1}{\beta_{i}}\left(s_{0}-s_{i}-\frac{d_{i}}{1-r}\right)\right),$
(33)

and $q^{*}_{i}(s_{0})$ is given by (19) for all $i\in V\setminus\\{0\\}$.
Moreover, in the interior of regime $k$,

$\displaystyle\frac{dR(s_{0})}{ds_{0}}=\frac{m_{0}+\sum_{i\in\Gamma[k]}\left(m_{i}+d_{i}/\beta_{i}(1-r)\right)}{\beta_{0}\left(\sum_{i\in\Gamma^{\dagger}[k]}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}.$
(34)

Regime $\\{-k\\}_{k=1}^{\tilde{K}-1}$: $s_{0}[-k-1]\leq s_{0}<s_{0}[-k]$.

$\displaystyle q^{*}_{0}(s_{0})$
$\displaystyle=\frac{1}{\beta_{0}\left(\sum_{i\in\tilde{\Gamma}[-k]}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}\left(m_{0}+\sum_{i\in\tilde{\Gamma}[-k]}m_{i}+\sum_{i\in\tilde{\Gamma}[-k]}\frac{1}{\beta_{i}}\left(s_{0}-s_{i}+\frac{d_{i}}{1-r}\right)\right),$
(35)

and $q^{*}_{i}(s_{0})$ is given by (22) for all $i\in V\setminus\\{0\\}$.
Moreover, in the interior of regime $-k$,

$\displaystyle\frac{dR(s_{0})}{ds_{0}}=r\frac{m_{0}+\sum_{i\in\tilde{\Gamma}[k]}\left(m_{i}-d_{i}/\beta_{i}(1-r)\right)}{\beta_{0}\left(\sum_{i\in\tilde{\Gamma}[k]}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}.$
(36)

Regime $-\tilde{K}$: $s_{0}[-\tilde{K}-1]\leq s_{0}<s_{0}[-\tilde{K}]$ with
$s_{0}[-\tilde{K}-1]=\inf S_{0}$. If

$s_{0}[-\tilde{K}]>\frac{1}{\sum_{i\in\tilde{\Gamma}[-k]}\frac{1}{\beta_{i}}}\left(-m_{0}+\sum_{i\in\tilde{\Gamma}[-k]}\frac{1}{\beta_{i}}\left(s_{i}-\frac{d_{i}}{1-r}-m_{i}\beta_{i}\right)\right),$

then $q^{*}(s_{0})$ and $\frac{dR(s_{0})}{ds_{0}}$ are as in (35) and (36).
Otherwise,

$\displaystyle q^{*}_{0}(s_{0})=0,\quad
q^{*}_{i}(s_{0})=q^{*}_{i}(s_{0}[-\tilde{K}]),\quad\forall i\in
V\setminus\\{0\\},\quad\frac{dR(s_{0})}{ds_{0}}=0.$ (37)

_Proof of Proposition 7._ In regime $k$, we know from Lemma 4 that a fraction
of agents from nodes $\Gamma[k]\setminus\Gamma^{\dagger}[k]$ and all agents
from nodes $\Gamma^{\dagger}[k]$ move to node 0, and agents from the remaining
nodes $V\setminus\Gamma[k]$ do not move. Therefore, the sum of $q^{*}_{i}$ for
$i\in\Gamma[k]\cup\\{0\\}$ equals to the sum of the masses of agents initially
locating at those nodes, i.e.

$\displaystyle
q^{*}_{0}+\sum_{i\in\Gamma[k]}q^{*}_{i}=q^{*}_{0}+\sum_{i\in\Gamma[k]\setminus\Gamma^{\dagger}[k]}q^{*}_{i}=m_{0}+\sum_{i\in\Gamma[k]}m_{i},$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:q_positive_relation}}}{{\Rightarrow}}\quad$
$\displaystyle
q^{*}_{0}=\frac{1}{\beta_{0}\left(\sum_{i\in\Gamma^{\dagger}[k]}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}\left(m_{0}+\sum_{i\in\Gamma[k]}m_{i}+\sum_{i\in\Gamma^{\dagger}[k]}\frac{1}{\beta_{i}}\left(s_{0}-s_{i}-\frac{d_{i}}{1-r}\right)\right).$

Therefore, the equilibrium price of node 0 is given by:

$\displaystyle p^{*}_{0}$
$\displaystyle=s_{0}-\beta_{0}q^{*}_{0}=s_{0}-\frac{1}{\left(\sum_{i\in\Gamma^{\dagger}[k]}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}\left(m_{0}+\sum_{i\in\Gamma[k]}m_{i}+\sum_{i\in\Gamma^{\dagger}[k]}\frac{1}{\beta_{i}}\left(s_{0}-s_{i}-\frac{d_{i}}{1-r}\right)\right)$
$\displaystyle=\frac{1}{\left(\sum_{i\in\Gamma^{\dagger}[k]}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}\left(\frac{1}{\beta_{0}}s_{0}+\sum_{i\in\Gamma^{\dagger}[k]}\frac{1}{\beta_{i}}\left(s_{i}+\frac{d_{i}}{1-r}\right)-m_{0}-\sum_{i\in\Gamma[k]}m_{i}\right).$

We now prove that $[s_{0}[k],s_{0}[k+1]]$ is the range of $s_{0}$ for regime
$k$. Since $q^{*}_{0}$ and the associated $\Gamma$ and $\Gamma^{\dagger}$ as
in (20a) are increasing in $s_{0}$ (Lemma 4), from regime $k$ to $k+1$, there
are three possible cases: (a) agents from nodes in $V\setminus\Gamma[k]$ with
the minimum $\\{(1-r)(s_{i}-\beta_{i}m_{i})+d_{i}\\}$ start to move to node
$0$, and thus these nodes are included in $\Gamma[k+1]$; (b) agents from nodes
in $\Gamma[k]\setminus\Gamma^{\dagger}[k]$ with the minimum
$\\{(1-r)s_{i}+d_{i}\\}$ all move to node $0$, and thus these nodes are
included in $\Gamma^{\dagger}[k+1]$; (c) both (a) and (b) happen
simultaneously. We denote $\tau_{1}$ and $\tau_{2}$ as in (27). Then, case (a)
corresponds to $\tau_{1}<\tau_{2}$. In this case,
$(1-r)(s_{0}[k+1]-\beta_{0}q^{*}_{0})=\tau_{1}$, and $s_{0}[k+1]$ is given by
(28). Similarly, $\tau_{2}<\tau_{1}$ in case (b) so that
$(1-r)(s_{0}[k+1]-\beta_{0}q^{*}_{0})=\tau_{2}$ and $s_{0}[k+1]$ is given by
(29). In case (c), $\tau_{1}=\tau_{2}$ and $s_{0}[k+1]$ is given by (30).
Furthermore, the lower bound threshold $s_{0}[k]$ can be similarly computed
given by $\Gamma[k-1],\Gamma[k],\Gamma^{\dagger}[k-1],\Gamma^{\dagger}[k]$.

Additionally, in regime $k$, the experienced payoff of agents originating from
$i\in\Gamma[k]$ is $(1-r)p^{*}_{0}-d_{i}$. In particular, for
$i\in\Gamma[k]\setminus\Gamma^{\dagger}[k]$, the price of node $i$ is
$p^{*}_{i}=p^{*}_{0}-d_{i}/(1-r)$, and agents at node $i$ is indifferent
between repositioning to node $0$ and staying at node $i$. For
$i\in\Gamma^{\dagger}[k]$, the price at node $i$ is
$s_{i}<p^{*}_{0}-\frac{d_{i}}{1-r}$, and agents from node $i$ move to node
$0$, and the utility of these agents is $(1-r)p^{*}_{0}-d_{i}$. We compute the
total utility of all agents, denoted as $U$, as follows:

$\displaystyle
U^{*}=(1-r)p^{*}_{0}m_{0}+\sum_{i\in\Gamma[k]}\left((1-r)p^{*}_{0}-d_{i}\right)m_{i}+\sum_{i\in
V\setminus\\{\Gamma[k]\cup\\{0\\}\\}}(1-r)(s_{i}-\beta_{i}m_{i})m_{i}.$

Moreover, $U^{*}$ can be alternatively expressed as the total received service
prices minus the cost of repositioning:

$\displaystyle U^{*}=(1-r)\sum_{i\in
V}p^{*}_{i}q^{*}_{i}-\sum_{i\in\Gamma[k]}(m_{i}-q^{*}_{i})d_{i}.$

Therefore,

$\displaystyle R(s_{0})=$ $\displaystyle r\sum_{i\in
V}p^{*}_{i}q^{*}_{i}=\frac{r}{1-r}\left(U^{*}+\sum_{i\in\Gamma[k]}(m_{i}-q^{*}_{i})d_{i}\right)$
$\displaystyle=$ $\displaystyle
r\left(p^{*}_{0}\left(m_{0}+\sum_{i\in\Gamma[k]}m_{i}\right)+\sum_{i\in
V\setminus\\{\Gamma[k]\cup\\{0\\}\\}}(s_{i}-\beta_{i}m_{i})m_{i}-\sum_{i\in\Gamma[k]}\frac{d_{i}q^{*}_{i}}{1-r}\right).$

Since $p^{*}_{0}$ and $q^{*}_{i}$ are linear in $s_{0}$, we know that
$R(s_{0})$ is also linear in $s_{0}$. Particularly,

$\displaystyle\frac{dR(s_{0})}{ds_{0}}$
$\displaystyle=r\frac{dp^{*}_{0}}{ds_{0}}\left(\sum_{i\in\Gamma[k]}m_{i}+m_{0}\right)-\frac{r}{1-r}\left(\sum_{i\in\Gamma[k]}d_{i}\left(\frac{-\frac{1}{\beta_{i}}}{\beta_{0}\left(\sum_{i\in\Gamma^{\dagger}[k]}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}\right)\right)$
$\displaystyle=r\frac{\left(\sum_{i\in\Gamma[k]}m_{i}+m_{0}\right)}{\beta_{0}\left(\sum_{i\in\Gamma^{\dagger}[k]}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}+\frac{r}{1-r}\left(\frac{\sum_{i\in\Gamma[k]}d_{i}/\beta_{i}}{\beta_{0}\left(\sum_{i\in\Gamma^{\dagger}[k]}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}\right)$
$\displaystyle=r\frac{m_{0}+\sum_{i\in\Gamma[k]}\left(m_{i}+d_{i}/\beta_{i}(1-r)\right)}{\beta_{0}\left(\sum_{i\in\Gamma^{\dagger}[k]}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}.$

Analogously, in regime $-k$, we know from Lemma 4 that agents from node $0$
move to nodes in $\tilde{\Gamma}[-k]$ and all agents from the remaining nodes
do not move. Therefore, the sum of $q^{*}_{i}$ for
$i\in\tilde{\Gamma}[-k]\cup\\{0\\}$ equals to the sum of the masses of agents
initially locating at those nodes, i.e.

$\displaystyle
q^{*}_{0}+\sum_{i\in\tilde{\Gamma}[-k]}q^{*}_{i}=m_{0}+\sum_{i\in\tilde{\Gamma}[-k]}m_{i},$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:qeq_negative}}}{{\Rightarrow}}\quad$
$\displaystyle
q^{*}_{0}=\frac{1}{\beta_{0}\left(\sum_{i\in\tilde{\Gamma}[-k]}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}\left(m_{0}+\sum_{i\in\tilde{\Gamma}[-k]}m_{i}+\sum_{i\in\tilde{\Gamma}[-k]}\frac{1}{\beta_{i}}\left(s_{0}-s_{i}+\frac{d_{i}}{1-r}\right)\right).$

The equilibrium price of node 0 is given by:

$\displaystyle p^{*}_{0}$
$\displaystyle=s_{0}-\beta_{0}q^{*}_{0}=s_{0}-\frac{1}{\left(\sum_{i\in\tilde{\Gamma}[-k]}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}\left(m_{0}+\sum_{i\in\tilde{\Gamma}[-k]}m_{i}+\sum_{i\in\tilde{\Gamma}[-k]}\frac{1}{\beta_{i}}\left(s_{0}-s_{i}+\frac{d_{i}}{1-r}\right)\right)$
$\displaystyle=\frac{1}{\left(\sum_{i\in\tilde{\Gamma}[-k]}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}\left(\frac{1}{\beta_{0}}s_{0}+\sum_{i\in\tilde{\Gamma}[-k]}\frac{1}{\beta_{i}}\left(s_{i}-\frac{d_{i}}{1-r}\right)-m_{0}-\sum_{i\in\tilde{\Gamma}[-k]}m_{i}\right).$

We now prove that $[s_{0}[-k-1],s_{0}[-k]]$ is the range of $s_{0}$ for regime
$-k$. From Lemma 4, we know that as $s_{0}$ decreases from regime $-k$ to
$-k-1$, agents from node $0$ start to move to nodes in
$V\setminus\tilde{\Gamma}[-k]$ with the maximum
$\\{(1-r)(s_{i}-\beta_{i}m_{i})-d_{i}\\}$, and thus these nodes are included
in $\tilde{\Gamma}[-k-1]$. The threshold $s_{0}[-k-1]$ corresponds to the case
that $(1-r)(s_{0}[-k-1]-\beta_{i}q^{*}_{0})\\}=\tau=\max_{i\in
V\setminus\tilde{\Gamma}[-k]}\\{(1-r)(s_{i}-\beta_{i}m_{i})-d_{i}\\}$, and
$s_{0}[-k-1]$ is given by (31). Similarly, we can compute the threshold
$s_{0}[-k]$ using $\tilde{\Gamma}[-k]$ and $\tilde{\Gamma}[-k-1]$.

Moreover, we can check that if
$s_{0}=\hat{s}_{0}=\frac{1}{\sum_{i\in\tilde{\Gamma}[-k]}\frac{1}{\beta_{i}}}\left(-m_{0}+\sum_{i\in\tilde{\Gamma}[-k]}\frac{1}{\beta_{i}}\left(s_{i}-\frac{d_{i}}{1-r}-m_{i}\beta_{i}\right)\right)$,
then $q^{*}_{0}$ as in (22) equals to 0 indicating that all agents leave node
$0$. Then, for any $s_{0}<\hat{s}_{0}$, $q^{*}_{0}=0$ and $q^{*}$ does not
change with $s_{0}$. Algorithm 3 terminates when the computed threshold for
the next regime $s_{0}[-k-1]\leq\hat{s}_{0}$ (Line 5-8). If
$s_{0}[-\tilde{K}]\geq\hat{s}_{0}$, then the range of states $S_{0}$ does not
include states that are smaller than $\hat{s}_{0}$, and $q^{*}$ is the same as
that in regime $-\tilde{K}+1$. Otherwise, $s_{0}[-\tilde{K}]=\hat{s}_{0}$, and
$q^{*}$ is given by (37).

In regime $-k$, For all $i\in\tilde{\Gamma}[-k]$, the experienced payoff of
agents originating from $i$ is $(1-r)p^{*}_{0}+d_{i}$. The total welfare of
all agents is given by:

$\displaystyle
U^{*}=(1-r)p^{*}_{0}m_{0}+\sum_{i\in\tilde{\Gamma}[-k]}\left((1-r)p^{*}_{0}+d_{i}\right)m_{i}+\sum_{i\in
V\setminus\tilde{\Gamma}[-k]}(1-r)(s_{i}-\beta_{i}m_{i})m_{i}.$

Moreover, since $U^{*}$ can be alternatively expressed as:

$\displaystyle U^{*}=(1-r)\sum_{i\in
V}p^{*}_{i}q^{*}_{i}-\sum_{i\in\tilde{\Gamma}[-k]}(q^{*}_{i}-m_{i})d_{i},$

we must have

$\displaystyle R(s_{0})$
$\displaystyle=\frac{r}{1-r}\left(U^{*}+\sum_{i\in\tilde{\Gamma}[-k]}(q^{*}_{i}-m_{i})d_{i}\right)$
$\displaystyle=r\left(p^{*}_{0}\left(m_{0}+\sum_{i\in\tilde{\Gamma}[-k]}m_{i}\right)+\sum_{i\in
V\setminus\tilde{\Gamma}[-k]}(s_{i}-\beta_{i}m_{i})m_{i}+\sum_{i\in\tilde{\Gamma}[-k]}\frac{d_{i}q^{*}_{i}}{1-r}\right).$

Since $p^{*}_{0}$ and $q^{*}_{i}$ are linear in $s_{0}$, we know that
$R(s_{0})$ is also linear in $s_{0}$. Particularly,

$\displaystyle\frac{dR(s_{0})}{ds_{0}}$
$\displaystyle=r\frac{dp^{*}_{0}}{ds_{0}}\left(\sum_{i\in\tilde{\Gamma}[-k]}m_{i}+m_{0}\right)+\frac{r}{1-r}\left(\sum_{i\in\tilde{\Gamma}[-k]}d_{i}\left(\frac{-\frac{1}{\beta_{i}}}{\beta_{0}\left(\sum_{i\in\Gamma}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}\right)\right)$
$\displaystyle=r\frac{\left(\sum_{i\in\tilde{\Gamma}[-k]}m_{i}+m_{0}\right)}{\beta_{0}\left(\sum_{i\in\tilde{\Gamma}[-k]}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}-\frac{r}{1-r}\left(\frac{\sum_{i\in\tilde{\Gamma}[-k]}d_{i}/\beta_{i}}{\beta_{0}\left(\sum_{i\in\tilde{\Gamma}[-k]}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}\right)$
$\displaystyle=r\frac{m_{0}+\sum_{i\in\tilde{\Gamma}[-k]}\left(m_{i}-d_{i}/\beta_{i}(1-r)\right)}{\beta_{0}\left(\sum_{i\in\tilde{\Gamma}[-k]}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}.$

In the last regime $-\tilde{K}$, if node $0$ is depleted, then
$\frac{dR(s_{0})}{ds_{0}}=0$. $\square$

##  Appendix D Proofs of statements in Section 3

_Proof of Proposition 3._ In regime 0, since no agents move, we know that
$q^{*}_{i}(s_{0})=m_{i}$ for all $i\in V$ and $dR(s_{0})/ds_{0}=0$.

Under Assumptions 1, we know from Proposition 7 that in each regime
$k=1,\dots,K$, the set of nodes where agents move to node $0$ is
$\Gamma[k]=\cup_{n=1}^{k}V_{n}$. Additionally, since no nodes are depleted
given Assumption 2, $\Gamma^{\dagger}[k]=\emptyset$ for all $k$. As a result,
we know from (33) that

$\displaystyle q^{*}_{0}(s_{0})$
$\displaystyle=\frac{1}{\beta_{0}\left(\sum_{i\in\Gamma^{\dagger}[k]}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}\left(m_{0}+\sum_{i\in\Gamma[k]}m_{i}+\sum_{i\in\Gamma^{\dagger}[k]}\frac{1}{\beta_{i}}\left(s_{0}-s_{i}-\frac{d_{i}}{1-r}\right)\right)$
$\displaystyle=\frac{1}{\beta_{0}\left(\sum_{i\in\cup_{n=1}^{k}V_{n}}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}\left(m_{0}+\sum_{i\in\cup_{n=1}^{k}V_{n}}\frac{1}{\beta_{i}}\left(s_{0}+m_{i}\beta_{i}-s_{i}-\frac{d_{i}}{1-r}\right)\right)$
$\displaystyle=\frac{1}{\beta_{0}\left(\sum_{i\in\cup_{n=1}^{k}V_{n}}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}\left(m_{0}+\sum_{i\in\cup_{n=1}^{k}V_{n}}\frac{1}{\beta_{i}}\left(s_{0}-\frac{d_{i}}{1-r}\right)\right).$
(38)

Additionally, $q^{*}_{i}(s_{0})$ is given by (19a) following Lemma 4. From
(34), we have:

$\displaystyle\frac{dR(s_{0})}{ds_{0}}=\frac{m_{0}+\sum_{i\in\Gamma[k]}\left(m_{i}+d_{i}/\beta_{i}(1-r)\right)}{\beta_{0}\left(\sum_{i\in\Gamma^{\dagger}[k]}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}=\frac{m_{0}+\sum_{i\in\cup_{n=1}^{k}V_{n}}\left(m_{i}+d_{i}/\beta_{i}(1-r)\right)}{\beta_{0}\left(\sum_{i\in\cup_{n=1}^{k}V_{n}}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}.$

In regime $-k$ with $k=1,\dots,\tilde{K}$,
$\tilde{\Gamma}[k]=\cup_{n=1}^{k}V_{n}$ under Assumption 1. Therefore,
following (35),

$\displaystyle q^{*}_{0}(s_{0})$
$\displaystyle=\frac{1}{\beta_{0}\left(\sum_{i\in\cup_{n=1}^{k}V_{n}}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}\left(m_{0}+\sum_{i\in\cup_{n=1}^{k}V_{n}}m_{i}+\sum_{i\in\cup_{n=1}^{k}V_{n}}\frac{1}{\beta_{i}}\left(s_{0}-s_{i}+\frac{d_{i}}{1-r}\right)\right)$
$\displaystyle=\frac{1}{\beta_{0}\left(\sum_{i\in\cup_{n=1}^{k}V_{n}}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}\left(m_{0}+\sum_{i\in\cup_{n=1}^{k}V_{n}}\frac{1}{\beta_{i}}\left(s_{0}+\frac{d_{i}}{1-r}\right)\right).$

and $q^{*}_{i}(s_{0})$ is given by (22a). From (36), we have:

$\displaystyle\frac{dR(s_{0})}{ds_{0}}=r\frac{m_{0}+\sum_{i\in\tilde{\Gamma}[k]}\left(m_{i}-d_{i}/\beta_{i}(1-r)\right)}{\beta_{0}\left(\sum_{i\in\tilde{\Gamma}[k]}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}=r\frac{m_{0}+\sum_{i\in\cup_{n=1}^{k}V_{n}}\left(m_{i}-d_{i}/\beta_{i}(1-r)\right)}{\beta_{0}\left(\sum_{i\in\cup_{n=1}^{k}V_{n}}\frac{1}{\beta_{i}}+\frac{1}{\beta_{0}}\right)}.$

$\square$

_Proof of Lemma 1._ From (38), we can check that under Assumption 2,
$q^{*}_{0}(s_{0})\geq 0$ for all $i\in V$. $\square$

Before proving Theorem 1, we first present the following two lemmas:

######  Lemma 5.

For any $a,b,c,d\in\mathbb{R}$ such that $c,d>0$. If
$\frac{a}{c}<\frac{b}{d}$, then $\frac{a}{c}<\frac{a+b}{c+d}<\frac{b}{d}$.
Moreover, if $\frac{a}{c}>\frac{b}{d}$, then
$\frac{a}{c}>\frac{a+b}{c+d}>\frac{b}{d}$.

_Proof of Lemma 5._ If $\frac{a}{c}<\frac{b}{d}$, then $ad<bc$ since $c,d>0$.
By adding $ac$ and dividing $(c+d)c$, we have $\frac{a}{c}<\frac{a+b}{c+d}$.
By adding $bd$ and dividing $(c+d)d$ on both sides, we have
$\frac{a+b}{c+d}<\frac{b}{d}$. Similarly, if $\frac{a}{c}>\frac{b}{d}$, then
$ad>bc$ since $c,d>0$. By adding $ac$ on both sides and divide by $(c+d)c$, we
have $\frac{a}{c}>\frac{a+b}{c+d}$. By adding $bd$ and dividing $(c+d)d$ on
both sides, we have $\frac{a+b}{c+d}>\frac{b}{d}$. $\square$

######  Lemma 6.

In case (i), the function $R(s_{0})$ is convex in $s_{0}$. In case (ii) (resp.
case (iii)), there exists an interval $[\underline{s}_{0},\bar{s}_{0}]$ with
$\mathbb{E}_{F}[S_{0}]\leq\underline{s}_{0}\leq\bar{s}_{0}\leq\sup\mathcal{S}_{0}$
(resp.
$\inf\mathcal{S}_{0}\leq\underline{s}_{0}\leq\bar{s}_{0}\leq\mathbb{E}_{F}[S_{0}]$)
such that $R(s_{0})$ is concave in $[\underline{s}_{0},\bar{s}_{0}]$ and
convex in $\mathcal{S}_{0}\setminus[\underline{s}_{0},\bar{s}_{0}]$.

_Proof of Lemma 6._ In case (i), since all nodes have similar market sizes
relative to their distances,

$\displaystyle\left|\frac{s_{i}-s_{0}}{d_{1}}\right|\leq\frac{1}{1-r},\quad\forall
i\in
V_{1},\quad\left|\frac{s_{i}-s_{j}}{d_{n}-d_{n-1}}\right|\leq\frac{1}{1-r},\quad\forall
i\in V_{n},j\in V_{n-1},~{}\forall n\leq\max\\{K,\tilde{K}\\}.$ (39)

For $n=1$, we sort all nodes $i\in V_{1}$ in increasing order of $s_{i}$, and
we denote the maximum index in $V_{1}$ as $\hat{i}$. Then, from (39), we note
that

$s_{0}\leq s_{1}+d_{1}/(1-r)\leq\cdots\leq s_{i}+d_{1}/(1-r)\leq\cdots\leq
s_{\hat{i}}+d_{1}/(1-r).$

From Assumption 1, we know that $s_{i}=\beta_{i}m_{i}$ for all $i\in V$, and
thus

$\frac{m_{0}}{\frac{1}{\beta_{0}}}\leq\frac{m_{1}+d_{1}/\beta_{1}(1-r)}{\frac{1}{\beta_{1}}}\leq\cdots\leq\frac{m_{i}+d_{1}/\beta_{i}(1-r)}{\frac{1}{\beta_{i}}}\leq\cdots\leq\frac{m_{\hat{i}}+d_{1}/\beta_{\hat{i}}(1-r)}{\frac{1}{\beta_{\hat{i}}}}.$

We denote the derivative of $R(s_{0})$ in the interior of each regime $k$ as
$\frac{dR(s_{0})}{ds_{0}}[k]$. From Lemma 5, we have

$\displaystyle\frac{dR(s_{0})}{ds_{0}}[0]=rm_{0}=\frac{r}{\beta_{0}}\frac{m_{0}}{\frac{1}{\beta_{0}}}$
$\displaystyle\leq$
$\displaystyle\frac{r}{\beta_{0}}\frac{m_{0}+(m_{1}+d_{1}/\beta_{1}(1-r))}{\frac{1}{\beta_{0}}+\frac{1}{\beta_{1}}}\leq\cdots\leq\frac{r}{\beta_{0}}\frac{m_{0}+\sum_{i\in
V_{1}}(m_{i}+d_{1}/\beta_{i}(1-r))}{\frac{1}{\beta_{0}}+\sum_{i\in
V_{1}}\frac{1}{\beta_{i}}}=\frac{dR(s_{0})}{ds_{0}}[1].$

Following the same procedure, we can iteratively show that

$\frac{dR(s_{0})}{ds_{0}}[1]\leq\frac{dR(s_{0})}{ds_{0}}[2]\leq\cdots\leq\frac{dR(s_{0})}{ds_{0}}[K].$

On the other hand,

$s_{0}\geq s_{1}-d_{1}/(1-r)\geq\cdots\geq s_{i}-d_{1}/(1-r)\leq\cdots\geq
s_{\hat{i}}-d_{1}/(1-r).$

Thus,

$\frac{m_{0}}{\frac{1}{\beta_{0}}}\geq\frac{m_{1}-d_{1}/\beta_{1}(1-r)}{\frac{1}{\beta_{1}}}\geq\cdots\geq\frac{m_{i}-d_{1}/\beta_{i}(1-r)}{\frac{1}{\beta_{i}}}\geq\cdots\geq\frac{m_{\hat{i}}-d_{1}/\beta_{\hat{i}}(1-r)}{\frac{1}{\beta_{\hat{i}}}},$

and

$\displaystyle\frac{dR(s_{0})}{ds_{0}}[0]=rm_{0}\geq\cdots\geq\frac{r}{\beta_{0}}\frac{m_{0}+\sum_{i\in
V_{1}}(m_{i}-d_{1}/\beta_{i}(1-r))}{\frac{1}{\beta_{0}}+\sum_{i\in
V_{1}}\frac{1}{\beta_{i}}}=\frac{dR(s_{0})}{ds_{0}}[-1].$

Consequently, we have
$\frac{dR(s_{0})}{ds_{0}}[-1]\geq\frac{dR(s_{0})}{ds_{0}}[-2]\geq\cdots\geq\frac{dR(s_{0})}{ds_{0}}[-\tilde{K}]$.
Therefore, the function $R(s_{0})$ is convex in $s_{0}$ in case (i).

In case (ii), since nodes within distance $\underline{d}$ have similar market
sizes relative to distances, following the same argument as in case (i), we
know that $R(s_{0})$ is convex in
$[s_{0}[-\underline{n}],s_{0}[\underline{n}]]$, where
$\underline{n}=\max\\{n=1,\dots,N|d_{n}\leq\underline{d}\\}$, i.e.

$\displaystyle\frac{dR(s_{0})}{ds_{0}}[-\underline{n}]\leq\frac{dR(s_{0})}{ds_{0}}[-\underline{n}+1]\leq\cdots\leq\frac{dR(s_{0})}{ds_{0}}[0]\leq\cdots\leq\frac{dR(s_{0})}{ds_{0}}[\underline{n}].$

Since nodes with distances between $\underline{d}$ and $\bar{d}$ have
decreasing market sizes relative to distances as in (12b), we know that for
nodes $i\in\cup_{i=\underline{n}+1}^{\bar{n}}V_{n}$, where
$\bar{n}=\max\\{n=1,\dots,N|d_{n}\leq\bar{d}\\}$, satisfy:

$\displaystyle s_{i}+d_{i}/(1-r)<s_{j}+d_{j}/(1-r),\quad i\in V_{n},j\in
V_{n-1},\quad n=\underline{n}+1,\dots,\bar{n},$ (40a)
$\displaystyle\Rightarrow\quad$ $\displaystyle
s_{i}-d_{i}/(1-r)<s_{j}-d_{j}/(1-r),\quad i\in V_{n},j\in V_{n-1},\quad
n=\underline{n}+1,\dots,\bar{n}.$ (40b)

Additionally, since nodes with distances higher than $\bar{d}$ have similar
market sizes relative to distances as in (11), we have:

$\displaystyle s_{i}-d_{i}/(1-r)\leq s_{j}-d_{j}/(1-r),\quad i\in V_{n},j\in
V_{n-1},\quad n>\bar{n}.$

Following Lemma 5 and (36), we have:

$\frac{dR(s_{0})}{ds_{0}}[-\tilde{K}]\leq\cdots\leq\frac{dR(s_{0})}{ds_{0}}[-\underline{n}]\leq\frac{dR(s_{0})}{ds_{0}}[-\underline{n}+1]\leq\cdots\leq\frac{dR(s_{0})}{ds_{0}}[0]\leq\cdots\leq\frac{dR(s_{0})}{ds_{0}}[\underline{n}],$

i.e. $R(s_{0})$ is convex for $s_{0}\leq s_{0}[\underline{n}]$.

Additionally, following (40a), we know that

$\displaystyle\frac{\sum_{i\in V_{n}}(m_{i}+d_{n}/\beta_{i}(1-r))}{\sum_{i\in
V_{n}}\frac{1}{\beta_{i}}}\leq\frac{\sum_{i\in
V_{n-1}}(m_{i}+d_{n-1}/\beta_{i}(1-r))}{\sum_{i\in
V_{n-1}}\frac{1}{\beta_{i}}},\quad\forall n\in[\underline{n}+1,\bar{n}]$ (41)

If

$\frac{dR(s_{0})}{ds_{0}}[\underline{n}]>\frac{\sum_{i\in
V_{\underline{n}+1}}(m_{i}+d_{\underline{n}+1}/\beta_{i}(1-r))}{\sum_{i\in
V_{\underline{n}+1}}\frac{1}{\beta_{i}}},$

then we know from Lemma 5 that
$\frac{dR(s_{0})}{ds_{0}}[\underline{n}]>\frac{dR(s_{0})}{ds_{0}}[\underline{n}+1]>\cdots>\frac{dR(s_{0})}{ds_{0}}[\bar{n}]$.
On the other hand, if

$\frac{dR(s_{0})}{ds_{0}}[\underline{n}]\leq\frac{\sum_{i\in
V_{\underline{n}+1}}(m_{i}+d_{\underline{n}+1}/\beta_{i}(1-r))}{\sum_{i\in
V_{\underline{n}+1}}\frac{1}{\beta_{i}}},$

then
$\frac{dR(s_{0})}{ds_{0}}[\underline{n}]\leq\frac{dR(s_{0})}{ds_{0}}[\underline{n}+1]$.
We apply this step iteratively until either (1) we find $\hat{n}\leq\bar{n}$
such that

$\frac{dR(s_{0})}{ds_{0}}[\hat{n}]>\frac{\sum_{i\in
V_{\hat{n}+1}}(m_{i}+d_{\hat{n}+1}/\beta_{i}(1-r))}{\sum_{i\in
V_{\hat{n}+1}}\frac{1}{\beta_{i}}},$

or (2) such $\hat{n}\leq\bar{n}$ does not exist. In scenario (1), we know that
$R(s_{0})$ is convex in $[s_{0}[\underline{n}],s_{0}[\hat{n}]]$ and strictly
concave in $[s_{0}[\hat{n}],s_{0}[\bar{n}]]$. In scenario (2), the strictly
concave interval is empty (i.e.
$\underline{s}_{0}=\bar{s}_{0}=\sup\mathcal{S}_{0}$)

Furthermore, since nodes with distances larger than $\bar{d}$ have similar
market sizes relative to distances, following the same argument as for nodes
with distances less than $\underline{d}$, we know that $R(s_{0})$ is convex in
$[s_{0}[\bar{n}+1],\sup\mathcal{S}_{0}]$. Therefore, we can conclude that
$R(s_{0})$ is strictly concave in an interval
$[s_{0}[\hat{n}],s_{0}[\bar{n}]]$ (which can be empty) and convex below
$s_{0}[\hat{n}]$ and above $s_{0}[\bar{n}]$.

In case (iii), since nodes within distance $\underline{d}$ have similar market
sizes relative to distances, following the same argument as in case (i), we
know that $R(s_{0})$ is convex in
$[s_{0}[-\underline{n}],s_{0}[\underline{n}]]$, where
$\underline{n}=\max\\{n=1,\dots,N|d_{n}\leq\underline{d}\\}$. Since nodes with
distances between $\underline{d}$ and $\bar{d}$ have increasing market sizes
relative to distances as in (12a), we know nodes
$i\in\cup_{i=\underline{n}+1}^{\bar{n}}V_{n}$, where
$\bar{n}=\max\\{n=1,\dots,N|d_{n}\leq\bar{d}\\}$, satisfy:

$\displaystyle s_{i}-d_{i}/(1-r)>s_{j}-d_{j}/(1-r),\quad i\in V_{n},j\in
V_{n-1},\quad n=\underline{n}+1,\dots,\bar{n},$ (42a)
$\displaystyle\Rightarrow\quad$ $\displaystyle
s_{i}+d_{i}/(1-r)>s_{j}+d_{j}/(1-r),\quad i\in V_{n},j\in V_{n-1},\quad
n=\underline{n}+1,\dots,\bar{n},$ (42b)

and $R(s_{0})$ is convex in $[s_{0}[\underline{n}],s_{0}[\bar{n}]]$.
Additionally, since nodes with distances higher than $\bar{d}$ have similar
market sizes relative to distances as in (11), $R(s_{0})$ is convex in
$[s_{0}[\bar{n}],\sup\mathcal{S}_{0}]$. Thus, $R(s_{0})$ is convex in
$[s_{0}[-\underline{n}],\sup\mathcal{S}_{0}]$.

Following Lemma 5 and (42a), we know that

$\displaystyle\frac{\sum_{i\in V_{n}}(m_{i}-d_{n}/\beta_{i}(1-r))}{\sum_{i\in
V_{n}}\frac{1}{\beta_{i}}}>\frac{\sum_{i\in
V_{n-1}}(m_{i}-d_{n-1}/\beta_{i}(1-r))}{\sum_{i\in
V_{n-1}}\frac{1}{\beta_{i}}},\quad\forall n\in[\underline{n}+1,\bar{n}]$ (43)

If

$\frac{dR(s_{0})}{ds_{0}}[-\underline{n}]<\frac{\sum_{i\in
V_{\underline{n}+1}}(m_{i}-d_{\underline{n}+1}/\beta_{i}(1-r))}{\sum_{i\in
V_{\underline{n}+1}}\frac{1}{\beta_{i}}},$

then we know from Lemma 5 that
$\frac{dR(s_{0})}{ds_{0}}[-\underline{n}]<\frac{dR(s_{0})}{ds_{0}}[-\underline{n}-1]<\cdots<\frac{dR(s_{0})}{ds_{0}}[-\bar{n}]$,
i.e. $R(s_{0})$ is strictly concave in
$[s_{0}[-\bar{n}],s_{0}[-\underline{n}]]$. On the other hand, if

$\frac{dR(s_{0})}{ds_{0}}[-\underline{n}]\geq\frac{\sum_{i\in
V_{\underline{n}+1}}(m_{i}-d_{\underline{n}+1}/\beta_{i}(1-r))}{\sum_{i\in
V_{\underline{n}+1}}\frac{1}{\beta_{i}}},$

then
$\frac{dR(s_{0})}{ds_{0}}[-\underline{n}]\geq\frac{dR(s_{0})}{ds_{0}}[-\underline{n}-1]$.
We apply this step iteratively until either (1) we find $\hat{n}\leq\bar{n}$
such that

$\frac{dR(s_{0})}{ds_{0}}[-\hat{n}]<\frac{\sum_{i\in
V_{-\hat{n}-1}}(m_{i}-d_{\hat{n}+1}/\beta_{i}(1-r))}{\sum_{i\in
V_{-\hat{n}-1}}\frac{1}{\beta_{i}}},$

or (2) such $\hat{n}\leq\bar{n}$ does not exist. In scenario (1), we know that