ISSN (Print) 0473-453X

Discussion Paper No. 1089

ISSN (Online) 2435-0982

CONNECTINGHETEROGENEOUS AGENTS
UNDER
INCOMPLETE INFORMATION

Masaki Aoyagi

June 2020

The Institute of Social and Economic Research
Osaka University
6-1 Mihogaoka, Ibaraki, Osaka 567-0047, Japan

Connecting Heterogeneous Agents under Incomplete
Information∗
Masaki Aoyagi†
June 8, 2020

Abstract
This paper studies the problem of a monopolistic platform which oﬀers
agents connection with one another. Agents have heterogeneous characteristics
that are valued by some other agents and observed privately by the principal.
The agents are privately informed about their heterogeneous preferences overthe characteristics of the other agents. The platform solicits information fromthe agents about their preferences and then oﬀers an allocation that consistsof groups of connected agents and subscription fees. We study mechanisms
which induce truthful reporting and acceptance of the proposed allocation as aunique equilibrium outcome. We identify asymptotically optimal mechanisms
which fully extract the agents’ informational rents in the limit as the market
becomes large.
Key words: platform, network externalities, random graph, revenue maximization, strategy-proof.
JEL Codes: D42, D47, D62, D82, L12

1

Introduction

Platforms as intermediaries of economic activities are gaining importance in themodern economy. Credit cards facilitate trade between businesses and consumers,
internet auction houses bring out demand and supply and realize gains from trade,and SNS connects people and disseminates information that helps decision making.
Economic theory has by now devoted much attention to the functioning of platforms,∗

I am grateful to seminar audiences at various universities and particularly to Satyanath Bhat.
Financial support from the JSPS (grant numbers: 21653016, 24653048, 15K13006, 22330061,
15H03328 and 15H05728), the Joint Usage/Research Center at ISER, Osaka University, and theInternational Joint Research Promotion Program of Osaka University is gratefully acknowledged.
†
ISER, Osaka University (aoyagi@iser.osaka-u.ac.jp).

1and oﬀers a variety of theories. This paper presents yet another theory of platforms
focusing on their role in connecting heterogeneous market participants. Speciﬁcally,
we focus on the monopoly power exercised by a platform based on its proprietary
access to information about market participants, and study its consequence on thedesign of a mechanism that oﬀers connections among them. Speciﬁcally, we consider
a market in which a platform has information about some qualitative characteristics
of agents referred to here as their salience types.1 An agent’s characteristic for example is the type of good a seller supplies to the market, the type of skill a worker
can provide to a prospective employer, or the type of project that an entrepreneur
requires funding for. In short, a salience type of an agent is his value to various othermarket participants. The assumption on proprietary access to such information bya platform models the ability of large online platforms to privately collect big dataon the subscribers’ activities and use them to project their characteristics.2
We assume that the agents are heterogeneous in the sense that no two agents
share the same characteristics. Although the platform has access to information
about the agents’ salience types, we assume that it does not directly observe theirpreferences over those types, and must collect information about them. We represent
these preferences of each agent by their preference types, and assume for simplicity
that each preference type regards each salience type as either preferable or not.
The agents are heterogeneous also in their preferences so that no salience type is
ex ante more popular than any other salience type. Agents value connection to any
agent with their preferred salience type, but must use the service of a monopolistic
platform to achieve it. The platform oﬀers them connections by forming groups
whose members are connected with each other. The value of a group to each member
i equals v > 0 if i ﬁnds preferable the salience type of another member, and zerootherwise. An allocation is a pair of such a group assignment and a subscription fee
proﬁle. The platform’s objective is to maximize the subscription revenue by creating
an optimal group assignment. In contrast to the literature on platform design thatassumes that agents are vertically diﬀerentiated by their quality types and thatevery agent uniformly prefers to be matched with agents of higher quality, we study
the problem under the assumption of horizontal diﬀerentiation across agents.3
Formally, a mechanism used by the platform forms an allocation based on reported preference types. We require such a mechanism to be strategy-proof in thesense that truth-telling is weakly dominant for every agent when reporting their1

We use the term “salience type” following Gomes & Pavan (2016).
A similar motivation is discussed in Fainmesser & Galeotti (2016). See Section 2.
3
While we assume that the platform observes the agents’ salience types but not their preference
types, our argument would be essentially unchanged if it observes the preference types and not thesalience types.
22

preference types. By deﬁnition, implementation of a strategy-proof mechanism does
not require knowledge about the probability distribution of the agents’ types. Unless the platform can force an allocation on the agents, however, strategy-proofness
does not itself solve the multiplicity of equilibria under adoption externalities. Thatis, if the agents may choose whether or not to accept the platform’s oﬀer of an allocation, their optimal decision depends on the acceptance decisions of other agents:
The agent may be willing to accept if and only if the other agents also accept. The
multiplicity of equilibria in such an adoption game is a central concern in the analysis of network externalities, and our analysis is no exception.4 In order to address
this concern, we build on the idea of a revelation-suggestion mechanism proposed byMyerson (1982), and consider a mechanism consisting of two stages: The platform
creates an allocation based on solicited preference types in the ﬁrst stage, and lets
the agents play an adoption game in the second stage. The mechanism is designed
so that acceptance is a uniquely optimal action for each agent. As far as we areaware, this is the ﬁrst attempt to introduce such a requirement in the formulationof a mechanism.
In our model, whether agent i ﬁnds the salience type of agent j preferable or
not is independent of whether j ﬁnds i’s salience type preferable, or whether iﬁnds the salience type of yet another agent k ̸= j preferable. We denote by p
the probability with which each agent ﬁnds the salience type of any other agent
preferable. When the total number of agents equals n, the value (n − 1)p is the key
quantity that represents the expected number of agents whose salience types eachagent ﬁnds preferable, and hence can be interpreted as the density of the preference
relationship among them.
Our objective is to characterize a mechanism that fully extracts the agents’
informational rents and achieves the ﬁrst-best allocation for the platform. First,
we observe that in any market of ﬁxed size n and for any probability p ∈ (0, 1),
no mechanism extracts full surplus if it is required to induce truth-telling in theﬁrst stage, and acceptance as a uniquely optimal action in the second stage. Thisobservation prompts us to examine what happens when the market size n grows
large and the probability p may change with n. In particular, we consider the limit
as n grows large while focusing on the behavior of (n − 1)p as a function of n.
Our analysis identiﬁes asymptotically optimal mechanisms in the following twocases. We call a market dense if (n − 1)p increases (slowly) as n grows large. The
case where p is a constant is a special case of a dense market. On the other hand,
we call a market sparse if (n − 1)p vanishes as n grows large. In a dense market,
4

See Dybvig & Spatt (1983). The multiplicity problem is also known as “chicken and egg” inthe two-sided market literature. See for example Caillaud & Jullien (2003).

3

we consider a single group mechanism that creates a single group consisting of a
preﬁxed agent i1 and all those agents who ﬁnd the salience type of i1 preferable
either directly or indirectly in any number of steps: These are set J1 of agents who
ﬁnd i1 preferable, set J2 of agents who ﬁnd agents in J1 preferable, set J3 of agents
who ﬁnd agents in J2 preferable, and so on. Agent i1 is oﬀered a small subsidy
for inclusion into the group, but all other agents who are included in the group arecharged a subscription fee close to their valuation of the group. The single groupmechanism induces truth-telling and also induces acceptance as a uniquely optimal
action through the iterative elimination of strictly dominated actions. When thecondition for a dense market holds, this mechanism is asymptotically optimal in thesense that as n grows large, the associated revenue approaches the maximal level
achievable under complete information about the agents’ preferences. In a sparse
market, on the other hand, we propose a multiple group mechanism which constructs
multiple groups which again include two sets of agents. The ﬁrst set consists ofagents who themselves ﬁnd (the salience type of) no other agent preferable but havesalience types which are found preferable by others, or the set of agents in which
every agent ﬁnds the salience type of another agent preferable either directly or
indirectly. The second set consists of agents who ﬁnd the salience type of some of
the ﬁrst set of agents preferable either directly or indirectly. Again, the ﬁrst set of
agents are oﬀered a small subsidy for subscription into their group, but the second
set of agents are charged a subscription fee close to their valuation of their group.
The multiple group mechanism induces truth-telling, and also induces acceptanceas a uniquely optimal action. Under the conditions for a sparse market, we showthat this mechanism is asymptotically optimal in the limit as n grows large.
The paper is organized as follows. We discuss the related literature in Section
2 and formulate a model in Section 3. Section 4 provides the description of themechanism and the properties required of it. The benchmark case of complete
information is analyzed in Section 5. Section 6 presents the analysis of the models
with incomplete information: Subsection 6.1 analyzes the single group mechanism
for a dense market, and Subsection 6.2 analyzes the multiple group mechanism fora sparse market. We conclude with a discussion in Section 7.

2

Related Literature

The present paper belongs to the literature that studies the problem of a monopolistic platform which oﬀers privately informed agents connection to each other.
Damiano & Li (2007) study a two-sided market where each side of the market consists of agents with heterogeneous quality, and the value of a match between two

4

agents is a supermodular function of the two individual qualities. When a monopolist divides the market into groups within which matches can be formed, Damiano &Li (2007) derive the conditions under which the proﬁt-maximizing fee schedules forthe groups are eﬃcient. Adopting the framework of Damiano & Li (2007), Hoppeet al. (2011) analyze the performance of the coarse matching scheme in which themarket is divided into only two groups. Gomes & Pavan (2016) study eﬃcientand proﬁt-maximizing platforms for many-to-many matching in a two-sided market
where agents have private types. Gomes & Pavan (2016) discuss the distinction
between the salience and preference types of an agent, and assume in their main
analysis that those two types are functions of a single private type of an agent. In
Board (2009), a monopolist in a one-sided market creates and assigns groups to the
population of agents with heterogeneous quality. Under various speciﬁcations of thefunctional relationship between the quality of a group and the qualities of its members, Board (2009) shows that the proﬁt maximizing group structure is ineﬃcientfrom a welfare point of view and attributes the ineﬃciencies to the creation of too
many groups. On the other hand, Veiga (2013) shows that when the value of alarger group is always higher than that of a smaller group, the proﬁt maximizing
group structure always entails a single group.
There are some important diﬀerences between the present paper and the papers
in the literature mentioned above: First, the ubiquitous assumption in the literatureis that agents are vertically diﬀerentiated, and every agent prefers to be matchedwith agents of a higher type. In contrast, we suppose that agents are horizontallydiﬀerentiated and their preferences over other agents are heterogeneous. In particular, an agent does not necessarily prefer to be matched with an agent who happens
to be popular among other agents. Second, we assume that each agent’s type is
two-dimensional and one of the dimensions is privately observed by the platform.
This assumption corresponds to the reality of online platforms that have proprietary access to data on their subscribers. Third, the literature assumes a screening
mechanism in which an agent’s allocation is determined by his type only and not by
the entire type proﬁle. In contrast, we consider a full mechanism where allocation
is determined by the type proﬁle of all agents.
A platform is a good with network externalities in the sense that its value toeach agent depends positively on the adoption decisions of other agents. We mayview the platform in our model trying to sell connection to agents. Monopoly saleof a network good under incomplete information is studied by Aoyagi (2013), wherethe value of the good to each agent is a function of the agent’s private type andthe number of subscriptions. Some models of network goods monopoly express local
network externalities by agents located at the nodes of a network as in the present

5paper. Among them, Fainmesser & Galeotti (2016) explore the possibilities thata platform has varying degrees of knowledge about the externalities relationshipamong consumers. Speciﬁcally, they study scenarios where the platform has accessto information on how susceptible or inﬂuential each consumer is to the decisions ofothers. Although we also suppose that a platform has access to information aboutmarket participants, our formulation is diﬀerent in that the realization of the externalities relationship is random and that the platform needs to collect information
about it.5
Extensive literature on matching theory is on the design of a mechanism thatmatches agents with heterogeneous preferences as in the present model. Most closely
related among them are the papers on coalition formation, which consider the problem of partitioning the set of agents into groups when the value of a group to any
member is a function of the types of other members. For example, Cechlárová &Romero-Medina (2001) assume that the value of a group to any of its member isequal to the value of either his most-preferred member, or his least-preferred member, Alcalde & Revilla (2004) introduce a preference which evaluates groups basedon the best subset of them, Dimitrov et al. (2006) suppose that each agent regards
other agents as either friends or enemies and compares the numbers of friends andenemies when evaluating the quality of a group, and Rodrı́guez-Álvarez (2009) considers the preference domain that includes the friend-enemy preferences studied byDimitrov et al. (2006). However, the primary focus of the literature on coalition formation is on the stability of matching, whereas our focus is on proﬁt maximization
through the extraction of informational rents. The agents’ preferences over otheragents assumed in this paper are binary so that each agent ﬁnds the salience type ofanother agent either preferable or not. This substantial simpliﬁcation of the generalpreference speciﬁcations used in the matching literature enables us to characterize mechanisms that achieve asymptotic optimality under the unique enforceability
requirement.

3

Model

The market consists of the set I of n agents. Each agent i has a salience type βiand a preference type θi . Agents are heterogeneous in the sense that βi ̸= βj for5

Ohter models of monopoly under local network externalities include Candogan et al. (2012),
who characterize the relationship between the location of a buyer in the network and the price hefaces under imperfect and perfect price discrimination, and Bloch & Quérou (2013), who examine
the optimality of price discrimination when each buyer is privately informed about the stand-alone
valuation of the monopolist’s good. Models of price competition between sellers of goods with local
network externalities include Aoyagi (2018), Chen et al. (2018), and Chen et al. (2020).

6

any pair of agents i and j. Speciﬁcally, when B denotes the set of salience types in
the population, there is a one-to-one correspondence ϕ : I → B such that ϕ(i) ∈ B
is the salience type of agent i. Let Φ be the set of all such correspondences. We
assume that the platform privately observes the random realization of ϕ, but theagents don’t. Our interpretation of this assumption is that it is prohibitively costly
for participants in a large and physically spread market to ﬁnd out if any otheragent has the characteristics by randomly approaching them.
Agent i’s preference type θi describes their preferences over the salience typesof other agents. These preferences classify each salience type as either preferable ornot. Formally, given ϕ, agent i’s preference type θi is a subset of the set B \ {ϕ(i)}of salience types of other agents, and ϕ(j) ∈ θi implies that i ﬁnds salience type ϕ(j)of agent j preferable. Let θ = (θi )i∈I denote a preference type proﬁle, and Θϕ be theset of preference type proﬁles under ϕ. A visual representation of (θ, ϕ) is a directed
graph in which the agents are nodes and the type proﬁle θ represents directed links
among them: If i ﬁnds j’s salience type ϕ(j) preferable (i.e., ϕ(j) ∈ θi ), then it isidentiﬁed with a directed link from i to j and denoted i → j. We call this directed
graph a preference network and denote it by D(θ, ϕ). In D(θ, ϕ), agent i indirectlyprefers agent j, denoted i ; j, if there exists a sequence of agents i0 , . . . , iK (K ≥ 1)
in I such that i0 = i, iK = j, and for every ik and ik+1 (k = 0, . . . , K − 1), ik ﬁnds
ϕ(ik+1 ) preferable (i.e., ϕ(ik+1 ) ∈ θik ). In terms of the preference network D(θ, ϕ),i indirectly prefers j if there is a directed path from i to j: a directed link ik → ik+1
exists for every such k. For each θ and i ∈ I, deﬁne
C;i (θ) = {j ̸= i : j ; i}to be the set of agents who indirectly prefer ϕ(i).6 A subset H ⊂ I of two or moreagents is strongly preference-connected if i ; j for every i, j ∈ H. H ⊂ I is a strong
component if it is strongly preference-connected and there exists no H ′ ̸⊃ H thatis strongly preference-connected. A component of the preference network D(θ, ϕ) is
the set of agents who are connected by the preference links when their direction is
ignored.
A group is a set of two or more salience types, and an assignment is a collection
g of disjoint (non-overlapping) groups. The interpretation is that agents i and j areconnected to each other if and only if their salience types belong to the same group.
Let G be the set of all possible assignments. Denoting by S ≡ S(g) the set of indicesof groups in assignment g ∈ G, we express g ∈ G as g = (Gs )s∈S , where each Gs is agroup in g. Given g = (Gs )s∈S , let G = ∪s∈S Gs be the set of salience types included
6

For simplicity, ϕ is omitted in the description of a preference network when it is understood.
We also often say that agent i prefers agent j when i ﬁnds j’s salience type ϕ(j) preferable.

7

in some group in g. For example, if B = {1, . . . , 8}, then g = ({1, 3}, {5, 7, 8}) ∈ G is
an assignment that consists of two groups (S = {1, 2}) and excludes salience types
2, 4 and 6. Agent i’s valuation ui (g, ϕ, θi ) of assignment g = (Gs )s∈S is determinedby his preference type θi as follows: For a constant v > 0,{v if ϕ(i) ∈ Gs and θi ∩ Gs ̸= ∅ for some s ∈ S,
ui (g, ϕ, θi ) =(1)0 otherwise.
In other words, the value of an assignment to any agent i equals v if there is anothermember of the same group who has his preferred salience type, and zero if there isno such member, or if i does not belong to any group.
Upon observing the agents’ salience types, a platform collects information about
their preference types and determines an allocation, which consists of an assignment
and transfers. Formally, an allocation rule is a pair (g, x), where g : Θ × Φ → G and
x = (xi )i∈I : Θ×Φ → RI . In other words, g(θ, ϕ) and x(θ, ϕ) = (xi (θ, ϕ))i∈I are theassignment and subscription fee proﬁle, respectively, under the reported preference
type proﬁle θ and the salience type proﬁle ϕ. We also denote by S(θ, ϕ) the set ofindices of groups in g(θ, ϕ), and by Gs (θ, ϕ) the group s ∈ S(θ, ϕ).
Each correspondence ϕ ∈ Φ that determines the agents’ salience types is equally
likely. Conditional on ϕ, the probability distribution of the type θi is independentand identical across agents. We also suppose that for any agent i, his preferences
over other agents j and k are independent (i.e., for j ̸= k, two events j ∈ θi andk ∈ θi are independent), and that the probability that i ﬁnds any agent j ̸= i
preferable equals p. Let Pp denote the joint probability distribution of type proﬁle θ
given p, and Ep the corresponding expectation. For any i, the marginal distributionof θi is given byPr(θi | ϕ) ≡ Pp (θi ) = p|θi | (1 − p)n−1−|θi | ,where |θi | denotes the number of elements in θi . We will allow the probability p todepend on the number n of agents in the market.
The platform’s cost of including any single agent into an assignment equals c,
which is assumed to satisfyv
0<c< .
(2)
2
It follows that social surplus generated when a group of two agents is formed isnegative (= −2c) when neither agent ﬁnds the other agent preferable, but is positive(≥ v − 2c) when at least one agent ﬁnds the other agent preferable. Denote byR(θ | g, x) the platform’s payoﬀ from (g, x) when the type proﬁle is θ:∑R(θ | g, x) =xi (θ) − |G(θ)|c.
i∈I8The platform’s expected payoﬀ R(g, x) under (g, x) is deﬁned accordingly:[]
R(g, x) = Ep R(θ | g, x) .

4

An Enforceable Mechanism

As mentioned in the Introduction, we address the multiplicity of equilibria in the
adoption decisions by considering a version of a revelation-suggestion mechanism
proposed by Myerson (1982). Speciﬁcally, we suppose that the platform oﬀers theagents an allocation while giving them an option to reject it. The proposed mechanism works over two stages 1 and 2 as follows. In stage 1, the platform determines
an allocation (g(θ̂, ϕ), x(θ̂, ϕ)) as a function of the reported preference type proﬁleθ̂ and the observed salience type proﬁle ϕ. In stage 2, the platform publicly announces the allocation (g(θ̂, ϕ), x(θ̂, ϕ)) as well as (θ̂, ϕ) and then lets the agentssimultaneously choose whether or not to accept the allocation.
Formally, the mechanism Γ consists of the allocation rule (g, x), an action set∏
Ai = {0, 1} for every agent (A = i∈I Ai ), and a collection of outcome functions(f g )g∈G . Ai is the set of actions available to agent i ∈ I in the subscription gameplayed in stage 2: ai = 0 and ai = 1 represent rejection and acceptance, respectively,of the proposed allocation. When allocation (g, x) with g = (Gs )s∈S is oﬀered andthe agents choose action proﬁle a ∈ A in the subscription game, f g : A → G modiﬁes
g by excluding those agents i ∈ G who have chosen rejection.7 Accordingly, if θi isagent i’s true type, his payoﬀ under the action proﬁle a in the subscription gamefollowing (g, x) is written in terms of the payoﬀ function deﬁned in (1) bygui (f (a), ϕ, θi ) − xi if ai = 1 and ϕ(i) ∈ G,
Ui (a, θi | g, x, ϕ) =

−xi


0

if ai = 1 and ϕ(i) ∈
/ G,

(3)

if ai = 0.

The ﬁrst line corresponds to an accepting agent (whose salience type is) included in
the assignment, the second line to an accepting agent not included in the assignment,
and the third line to a rejecting agent (who makes no transfer payment and gains
no connection to other agents).8 Importantly, the adoption game does not result in
the inclusion of an excluded agent to the assignment, or reassignment of any agent
to a diﬀerent group.
7

It is not crucial whether accepting agents are included or not. For example, the assignmentf (a) may include all accepting agents, or may exclude all agents (so that no group will be formed).
8
Any agent excluded from the assignment chooses acceptance if and only if his transfer payment
is non-positive.
g9

Upon the public announcement of the report proﬁle θ̂ = (θ̂i )i∈I by the platformin stage 2, the agents form beliefs about the other agents’ preference types. Letµi : Θ → ∆(Θ−i ) denote agent i’s belief given the public announcement: µi (θ̂)(θ−i )is i’s belief that the other agents’ true preferences equal θ−i when the report proﬁleequals θ̂.9 Deﬁne µ∗ = (µ∗i )i∈I to be the belief corresponding to truthful reporting:µ∗i (θ̂)(θ̂−i ) = 1 for every θ̂ ∈ Θ and i ∈ I.
Given that every agent is ex ante symmetric in terms of their salience types, we willin what follows focus on anonymous mechanisms that respect the agents’ salience
types but ignore their identities. Speciﬁcally, we focus on (g, x) such that for everyϕ, ϕ̂ ∈ Φ and every θ ∈ Θ,g(θ, ϕ) = g(θ, ϕ̂) and xi (θ, ϕ) = xi (θ, ϕ̂) for every i.
That is, as long as the preference type proﬁle θ is the same, the mechanism speciﬁes
the same assignment of salience types and transfers regardless of who has whichsalience type. We will then denote (g, x) as a function of θ only, and our analysis
in the subsequent sections identiﬁes the agents’ salience types with their names:
ϕ(i) = i for every i.
In stage 1, we suppose that Γ induces truthful reporting as a weakly dominantaction conditional on the acceptance of the platform’s oﬀer (g(θ), x(θ)) by every
agent for every θ in stage 2. Speciﬁcally, Γ is strategy-proof if
ui (g(θi , θ−i ), ϕ, θi ) − xi (θi , θ−i ) ≥ ui (g(θi′ , θ−i ), ϕ, θi ) − xi (θi′ , θ−i )for every θi , θi′ , θ−i , and i ∈ I, and individually rational if (g, x) satisﬁes
ui (g(θi , θ−i ), ϕ, θi ) − xi (θi , θ−i ) ≥ 0
for every θi , θ−i , and i ∈ I.
In stage 2, a mechanism Γ is uniquely acceptable if for any type proﬁle θ ∈ Θ,∗
a = (1, . . . , 1) is the unique Bayes Nash equilibrium of the subscription game when
the agents’ belief about the distribution of θ is given by µ∗ , and agent i’s payoﬀ
function is given by Ui in (3). In other words, acceptance of the suggested allocationis the uniquely optimal action for every agent i conditional on truthful reporting by
every agent in stage 1. A mechanism is uniquely enforceable if it is strategy-proof,
individually rational, and uniquely acceptable.10
9Since reporting is done privately and the types are independent, we ignore the dependence ofµi on his own type.
10
Note that unique enforceability does not imply the uniqueness of a PBE in the two-stage game.

10

By strategy-proofness, no unilateral deviation that involves misreporting in stage
1 and acceptance in stage 2 is proﬁtable. No unilateral deviation that involves
rejection in stage 2 is proﬁtable either since any such deviation yields zero, whereas
truthful reporting and acceptance yield at least zero by individual rationality. We
hence have the following result.
Proposition 1. If Γ is uniquely enforceable, then it implements (g, x) in PBE of
the two-stage game.

5

Complete Information

We begin our analysis with the benchmark case where the platform has complete
information about the agents’ preference type proﬁle θ, or equivalently, the underlying preference network D(θ). In this case, we only require the mechanism Γ tobe IR and uniquely acceptable. Deﬁne R∗ (θ) to be the supremum of the platform’s
payoﬀ from such mechanisms:R∗ (θ) = sup {R(θ | g, x) : Γ is IR and uniquely acceptable},and R∗ = Ep [R∗ (θ)].
Consider the components of the preference network D(θ) consisting of two or
more agents, and index them by s. Let S(θ) be the set of such indices. For eachcomponent Cs (θ) ⊂ I of D(θ), take any subset F of Cs (θ) and let
C;F (θ) = ∪i∈F C;i (θ)
be the set of agents who are strongly preference-connected to some i ∈ F . Deﬁne(Fs (θ), Ys (θ)) to be a solution to the maximization problem:{
F , Y ⊂ Cs (θ),
max |Y |(v − c) − |F |c subject to(4)(F,Y )
Y = C;F (θ) \ F.
(4) has a solution since Cs (θ) is ﬁnite, and gives the maximal payoﬀ that the platform can generate from this component. The intuition is as follows: The objectivefunction corresponds to the platform’s payoﬀ when it forms a group F ∪ Y by offering free subscription to agents in F , but charging v to agents in Y . Since Y ischosen so that its members are strongly preference-connected to some agent in F ,agents in Y are indeed willing to pay up to v for subscription into an assignment
if it also includes F . The platform then maximizes its payoﬀ by taking Y as large
as possible (since v − c > 0), while taking F as small as possible (since c > 0).
Note that the maximized payoﬀ is strictly positive for every component of two or11

more agents since 2c < v. When the component C is as described in Figure 1, forexample, (4) has the solution F = {3, 6} and Y = {1, 2, 4, 7, 8, 9, 10}, and its value
equals 7(v − c) − 2c = 7v − 9c.11
7
Y
8

1

9
6
F
10
2
5
3
4

Figure 1: Optimal Mechanism under Complete Information
We next show that for any ε > 0, there exists a mechanism Γ such that R(θ |∑g, x) = s∈S(θ) {|Ys (θ)|(v − c) − |Fs (θ)|c} − ε for the solution (Fs (θ), Ys (θ)) to (4)(s ∈ S(θ)). First, for each θ, let group Gs (θ) be deﬁned by Gs (θ) = Fs (θ) ∪ Ys (θ),
and assignment g(θ) by g(θ) = (Gs (θ))s∈S(θ) . In line with the intuition provided
above, the transfer is speciﬁed so that agents in Fs (θ) are oﬀered a small subsidy
whereas agents in Ys (θ) are charged a fee close to their full valuation v. Formally,let
F (θ) = ∪s∈S(θ) Fs (θ), and Y (θ) = ∪s∈S(θ) Ys (θ),
and for ε ∈ (0, v), deﬁnexi (θ) ={− nε

if i ∈/ Y (θ),12v − nε11

if i ∈ Y (θ).

(5)

Recall that an agent’s salience type is identiﬁed with his index. Note that this is not theunique solution to the maximization problem. The same value can be achieved when, for example,
F = {3, 8} and Y = {1, 2, 4, 7, 8, 9, 10}.

12

Proposition 2. Suppose that the platform has complete information about θ. Then∑R∗ (θ) ={|Ys (θ)|(v − c) − |Fs (θ)|c}.
s∈S(θ)

Furthermore, Γ with (g, x) deﬁned in (5) is IR and uniquely acceptable, and satisﬁes
R(θ | g, x) = R∗ (θ) − ε for every θ.
In the subscription stage, acceptance is a strictly dominant action for every agent
in F , and is an iteratively strictly dominant action for agents in Y . The numberof iteration required for each agent in Y to ﬁnd out that acceptance is an optimal
action equals the length of the shortest directed path that connects him with agentsin F .

6

Incomplete Information

We now return to the incomplete information environment in which the platformcannot directly observe the realization of θ. With incomplete information, the ﬁrstbest payoﬀ R∗ is not achievable as shown in the following proposition.
Proposition 3. For any market size n and probability p, there exists κ ≡ κ(n, p) > 0
such that if Γ is a uniquely enforceable mechanism, then the platform’s expected
payoﬀ under (g, x) is bounded away from the optimal level by κ: R(g, x) ≤ R∗ − κ.
The proposition is based on the observation that a mechanism is uniquely acceptable only if it oﬀers a negative subscription fee to at least one agent. We shouldemphasize that κ, which is interpreted as a lower bound for the agents’ informational
rents, depends on both p and n. For a ﬁxed market size n, the extreme values of theprobability p eliminate those information rents: On the one hand, as p approaches
zero, all agents become isolated with probability close to one, and hence the platform’s payoﬀ from any IR mechanism approaches zero. On the other hand, as p
approaches one, the underlying preference network becomes complete (i.e., there isa two-way link between every pair of agents) with probability close to one, and themechanism described in the following subsection that forms a single group will become optimal. Our primary interest hence is on what happens for the less extreme
values of p as the market size n grows large. As seen below, diﬀerent mechanisms
entail diﬀerent allocations of the informational rents among the agents.
12

In this speciﬁcation, note that agents not included in the assignment are also oﬀered a small
subsidy.

13

6.1

Single Group Mechanism

We ﬁrst consider the case where the expected number of agents (n − 1)p in any
agent’s preference set θi (slowly) increases with the market size n. The expected
total number of links n(n−1)p in the underlying network D(θ) hence grows (a little)
faster than linearly with n.
A single group mechanism forms at most one group regardless of the underlying preference network. Speciﬁcally, for some predetermined agent i1 , the single
platform is formed if the set of agents who are strongly preference-connected toi1 is non-empty, and the group includes i1 and all those agents who are strongly
preference-connected to him. No group is formed if no agent is strongly preferenceconnected to i1 . Deﬁne Y (θ) ≡ C;i1 (θ) to be the set of agents strongly preferenceconnected to i1 . Formally, Γ is a single group mechanism based on i1 if there existsε ∈ (0, v) such that for every θ: S(θ) is a singleton, and1) if Y (θ) = ∅, then G(θ) = ∅ and xi (θ) = − nε for every i;2) if Y (θ) ̸= ∅, then G(θ) = {i1 } ∪ Y (θ), andxi (θ) ={v − nεif i ∈ Y (θ),− nεif i ∈/ Y (θ).

Figure 2 illustrates the construction of a single group mechanism based on i1 = 6.
It is important that the speciﬁcation of i1 cannot be contingent on the realizationof θ. Note also that only agent i1 may possibly enjoy informational rents close to v
under this mechanism.
Proposition 4. A single group mechanism Γ is uniquely enforceable.
For a ﬁxed market size n, the single group mechanism is ineﬃcient unless p
is very large since with non-negligible probability, only a few agents are strongly
preference-connected to i1 , and hence the platform formed is small compared withthe total market size. In Figure 2, for example, a single group mechanism based on
i1 = 1 or 2 will create no group. As seen below, however, this problem becomes lessserious as the market size grows as far as the probability p does not vanish “veryfast” with n. Formally, let Γ be the single group mechanism speciﬁed above, anddenote by Θε (n) the set of type proﬁles θ at which the expected revenue under the
single group mechanism Γ described above is within ε of the optimal level:Θε (n) = {θ : R(θ | g, x) > R∗ (θ) − ε}.

14

7
Y

1

8

9
6
i1

10
2

5
3
4

Figure 2: Construction of a Single Network Mechanism when i1 = 6

Proposition 5. Let γ > 0 and suppose that p(n) ≥ (1+γ)nlog n for every large n.
Then the single group mechanism Γ is asymptotically optimal in the sense that forevery ε > 0,lim Pp (θ ∈ Θε (n)) = 1.
n→∞

The proposition builds on a theory of random graphs. A directed graph D is
Hamiltonian if there exists a directed closed trail that goes through every node ofD exactly once as in Figure 3. If D(θ) is Hamiltonian, then every agent is strongly
preference-connected to every other agent, and hence to i1 . It follows that if i1
subscribes, then all other agents are willing to pay up to v for subscription. It is
known that when the probability p(n) satisﬁes the condition stated in Proposition
5, the probability that D(θ) is Hamiltonian approaches one as the market becomeslarge.
Proposition 5 includes as a special case where the probability p of each link is
independent of the market size.
Corollary 1. Suppose p > 0 is a constant. Then the single group mechanism Γ isasymptotically optimal as n → ∞.

15

7
Y
8

1

9
6
i1

10
2

5
3
4

Figure 3: Hamiltonian graph
The directed path indicated by the solid line visits every agent just once andreturns to the original agent.

6.2

Multiple Group Mechanism

We next consider the case where the expected number of agents (n − 1)p in any
agent’s preference set θi vanishes as the market size n → ∞. However, n(n − 1)p,which is the expected total number of links in the underlying network D(θ), may
still increase with n.
Given i ∈ I and Y ⊂ I, we say that j is strongly preference-connected to i within
Y , and denote j ;Y i, if there is a directed path j → i1 → · · · → ik → i from j to isuch that all intermediate agents i1 , . . . , ik on the path belong to Y . Given any F ,Y ⊂ I with F ∩ Y = ∅, deﬁne also
C;F (Y, θ) = {j ∈/ F : j ;Y i for some i ∈ F }to be the set of agents outside F who are strongly preference-connected to some iin F within Y in the network D(θ). If Y satisﬁes Y ⊂ C;F (Y, θ), then conditionalon subscription by agents in F , every agent i ∈ Y has acceptance as an iteratively
dominant action when a subscription fee is less than v.
For any θ, consider a collection F(θ) of subsets F of I such that either
1) F = {i} for some i such that θi = ∅ and C;i (θ) ̸= ∅, or2) |F | ≥ 2 and F is a strong component.
16

F is a set of candidates who are oﬀered free subscription. The only complication isthat there may be an overlap of agents who ﬁnd preferable two diﬀerent free agents iand j. In such a case, agent j is redundant in attracting those agents in the overlap.
In this sense, the optimal assignment must partition the set of agents who ﬁnd free
agents preferable, and eliminate any redundant free agents. Formally, let S̄(θ) be
set of indices of elements of F(θ), and denote its generic element by Fs . Let() ()
Y = ∪s∈S̄(θ) C;Fs (θ) \ ∪s∈S̄(θ) Fs .
Y is the set of agents who are outside ∪s∈S̄(θ) Fs but are strongly preferenceconnected to some Fs . If Y ̸= ∅, partition Y into disjoint subsets (Ys )s (allowing
Ys = ∅ for some s) such thatYs ⊂ C;Fs (Ys , θ).
That is, each j ∈ Ys is strongly preference-connected within Ys to Fs so that they
are willing to pay up to v if agents in Fs also subscribe. If there are multiple
such partitions, take the one that minimizes the number of free agents included, or
equivalently, the number of elements in the set{s : Fs = {i} and Ys ̸= ∅}.
Let now S(θ) ⊂ S̄(θ) be the subset of indices such that
S(θ) = {s ∈ S̄(θ) : Fs = {i} and Ys ̸= ∅} ∪ {s ∈ S̄(θ) : |Fs | ≥ 2}.
Let Gs (θ) = Fs (θ) ∪ Ys (θ) for each s ∈ S(θ), andF (θ) = ∪s∈S(θ) Fs (θ),

and Y (θ) = ∪s∈S(θ) Ys (θ).

Consider a mechanism such that for each θ, its groups are given by Gs (θ) fors ∈ S(θ), and agents in Y (θ) are charged subscription fees close to v, while otheragents are oﬀered small subsidies. Formally, for ε ∈ (0, v), deﬁne a multiple groupmechanism Γ byg(θ) = (Gs (θ))s∈S(θ) ,and xi (θ) ={v − nεif i ∈ Y (θ),− nεotherwise.

Figure 4 illustrates the construction of a multiple group mechanism, where F =F1 ∪ F2 .13
13

Note that agents 3 and 4 are not included in the assignment since they are redundant in termsof the agents they attract.

17

F1

Y2

F4
F2
F3

Figure 4: Construction of a Multiple Group Mechanism

Proposition 6. A multiple group mechanism Γ is uniquely enforceable.
As seen, the multiple group mechanism leaves the informational rents to a strong
component of agents, and hence can be ineﬃcient when the probability p is high.
On the other hand, it is almost eﬃcient when there is no strong component as seenin the following lemma.
Lemma 1. Let Γ be a multiple group mechanism. If D(θ) contains no strong component, then R(θ | g, x) = R∗ (θ) − ε.
When the expected cardinality (n − 1)p of the type set θi of each agent becomes
small as n grows large, the probability that there exists a strong component becomes
small. It then follows from Lemma 1 that in such a market, the multiple groupmechanism becomes almost eﬃcient. As before, let Θε (n) be the set of type proﬁlesθ at which the expected revenue under the multiple group mechanism Γ describedabove is within ε of the optimal level:Θε (n) = {θ : R(θ | g, x) > R∗ (θ) − ε}.
Proposition 7. Suppose that p(n) = τ (n)n for every n for some function τ : N →R++ satisfying limn→∞ τ (n) = 0. Then the multiple group mechanism is asymptotically optimal in the sense that for every ε > 0,lim Pp (θ ∈ Θε (n)) = 1.

n→∞

18

The key insight behind this result also comes from a result on random graphs.
Let U (θ) be the undirected graph obtained from D(θ) by ignoring the directionof its links. When the probability p(n) satisﬁes the condition of Proposition 7, it
can be shown that the probability that there is a cycle of three or more agents inU (θ) approaches zero as n → ∞. If there is no such cycle in U (θ), then there isno directed cycle of three or more agents in D(θ). Furthermore, it can be readily
shown that the probability that D(θ) contains directed cycles of just two agents also
approaches zero as n → ∞. It follows that the probability that there is a strong
component in D(θ) approaches zero as n → ∞, and hence a small subsidy needs tobe oﬀered only to those agents with θi = ∅. These agents, however, must also be
oﬀered small subsidies under complete information, and hence there is no loss in theplatform’s payoﬀ compared with the complete information benchmark.

7

Conclusion

We study platform design when a platform oﬀers connections to agents when it
exercises a monopoly power based on its proprietary access to information about theagents’ heterogeneous salience types. The platform collects information about theagents’ preferences and proposes an allocation that consists of groups of connectedagents and transfer payments. Our focus is on uniquely enforceable mechanisms thatwork over two stages and make truthful reporting of private preference types weakly
dominant in the ﬁrst stage, and acceptance of the proposed allocation a uniquely
optimal action for every agent in the second stage. The latter requirement addresses
the multiplicity of equilibria in the adoption decisions in the presence of network
externalities. We show that in the limit as the number of market participants grows
large, there exist uniquely enforceable mechanisms that extract full informational
surplus from the agents. These mechanisms are classiﬁed by the number of groupsof connected agents they create. Speciﬁcally, the classiﬁcation is based on how the
expected number (n − 1)p of salience types that each agent ﬁnds preferable varies
with the market size n. In markets where each agent ﬁnds a relatively large numberof salience types preferable, an optimal mechanism forms one group of connectedagents and oﬀers a small subsidy just to one agent. In contrast, in markets where
each agent ﬁnds a relatively small number of salience types preferable, an optimalmechanism forms many small groups of connected agents.
The following are some open questions. First, one important case not covered by
our analysis is when the expected size of the preference set θi of each agent remains
constant regardless of n, i.e., p(n) = nk so that (n−1)p → k for some constant k. Thiscase, however, corresponds to the threshold in the existence of cycles in the large

19random graphs, and the asymptotic behavior of the preference network is diﬃcult toanalyze. Second, our market is one-sided in the sense that every agent is potentiallyinterested in a match with any other agent. On the other hand, platform design isoften studied in a two-sided market, where agents in one side are only interested tobe matched with some of the agents on the other side as in the case of sellers andbuyers of some good. While the present framework readily extends to accommodate
models of two-sided markets, extending the analysis requires a diﬀerent technique.
Third, we have assumed for simplicity that the value of a platform can take only
two values 0 and v > 0 for each agent. As mentioned earlier, models in the matching
literature assume more general value speciﬁcations, and it would be interesting tostudy their implications in our context. For example, one natural speciﬁcation is
one where the value of a group increases monotonically with the number of agentsin it with preferable salience types.

Appendix
Proof of Proposition 2. We ﬁrst show that∑R∗ (θ) ≤{|Ys (θ)|(v − c) − |Fs (θ)|c}.
s∈S(θ)Take any component Cs (θ) (s ∈ S(θ)). Suppose to the contrary that there exists
an IR and uniquely acceptable mechanism with the allocation rule (ĝ, x̂) that yields
the payoﬀ Rs (θ | ĝ, x̂) > |Ys (θ)|(v − c) − |Fs (θ)|c. Let Ŷ = {i ∈ Cs (θ) : x̂i (θ) > 0}
be the set of agents in Cs (θ) who are charged strictly positive subscription fees, andF̂ = {i ∈ Cs (θ) : x̂i (θ) ≤ 0} be the set of agents in Cs (θ) who are oﬀered subsidies
for subscription. By assumption, there exists i1 ∈ Ŷ who is not strongly preferenceconnected to F̂ . Let J1 = {i1 }, and let J2 ⊂ Ŷ be the set of agents to whom i1 isstrongly preference-connected: J2 = {j ∈ Ŷ : i1 ; j}. Since i1 is charged a positive
subscription fee, IR implies that J2 ̸= ∅, and furthermore, since i1 is not strongly
preference-connected to F̂ , no j ∈ J2 is strongly preference-connected to F̂ . Let
then J3 ⊂ Ŷ be the set of agents j to whom agents in J2 are strongly preferenceconnected. In the same way, we can iteratively construct a sequence J4 , J5 , . . . ofsubsets of Ŷ so that no agent in those subsets is strongly preference-connected toF̂ . Since Ŷ is ﬁnite, however, we will have Jk+1 ⊂ ∪kℓ=1 Jℓ for some k. We then havea contradiction to uniquely acceptable since then for agents i in the set ∪kℓ=1 Jℓ , nosubscription ai = 0 is a Nash equilibrium action since they are all charged positive
subscription fees.
The mechanism with allocation rule (g, x) deﬁned in (5) is clearly IR and also
uniquely acceptable: For i ∈ F (θ), xi (θ) < 0 so that subscription ai = 1 is a20

dominant action. For j ∈ Ys (θ), aj = 1 is an iteratively dominant action sinceYs (θ) consists of all agents who are strongly preference-connected to some i ∈ Fs (θ):
For any j ∈ Ys (θ), either i ∈ θj for some i ∈ Fs (θ) or there exists k ∈ Ys (θ) withk ∈ C;F (θ). Rejection is dominated in the second round of the iterative elimination
procedure in the ﬁrst case, whereas it is iteratively dominated for j in one roundafter it is dominated for k in the second case. Finally, the platform’s payoﬀ fromCs (θ) under (g, x) equals∑
R(θ | g, x) ={|Ys (θ)|(v − c) − |Fs (θ)|c} − ε.
s∈S(θ)

Since ε is arbitrary, R∗ (θ) ≥the stated conclusion.

∑s∈S(θ) {|Ys (θ)|(v − c) − |Fs (θ)|c}.

We hence obtain()n
Proof of Proposition 3. Let δ = min {p, 1 − p} ( 2 ) > 0 so that P (θ) ≥ δ for every
θ. Consider the set Θsc of type proﬁles θ such that D(θ) is strongly preferenceconnected. Deﬁneκ = δ |Θsc | (n − 1)(v − c) > 0.
Fix any uniquely enforceable mechanism with allocation rule (g, x), and write R(θ) =R(θ | g, x) for simplicity. For any θ ∈ Θsc , it is optimal to include every agent in
the assignment. Furthermore, one agent must be oﬀered free subscription sinceotherwise, there would be a NE of the adoption game in which no agent accepts.
Hence, the optimal revenue under complete information is given byR∗ (θ) = (n − 1)v − nc.
On the other hand, for any θ, let J(θ) = {j ∈ I : xj (θ) > 0} be the set of agents whoare charged positive subscription fees under (g, x). Since Γ is IR, J(θ) ⊂ G(θ), the setof agents included in the assignment. Since Γ is IR and uniquely acceptable, we mustagain have one agent included in the assignment with a non-positive subscription
fee so that the platform’s revenue under θ satisﬁes
R(θ) ≤ |J(θ)|v − (|J(θ)| + 1)c.
It follows that for any θ ∈ Θsc ,R∗ (θ) − R(θ) ≥ (n − |J(θ)| − 1)(v − c).

(6)Take any θ ∈ Θsc and j ∈ J(θ), and consider now a proﬁle (∅, θ−j ) where agent j’s
type is replaced by θj′ = ∅. Clearly, (∅, θ−j ) ∈/ Θsc and R∗ (∅, θ−j ) = (n − 1)v − nc.
We must have either j ∈/ G(∅, θ−j ) or θj ∩ G(∅, θ−j ) = ∅ since otherwise, agent j
21

would report θj′ = ∅ when his true type is θj , and since xj (∅, θ−j ) ≤ 0 by IR, hisutility from misreporting would be v − xj (∅, θ−j ) ≥ v > v − xj (θ), which is his payoﬀ
when he reports his type truthfully. It follows that G(∅, θ−j ) consists of at mostn − 1 agents, and hence the fact that Γ is IR and uniquely acceptable implies that
R(∅, θ−j ) ≤ (n − 2)v − (n − 1)c.
This further implies thatR∗ (∅, θ−j ) − R(∅, θ−j ) ≥ v − c.

(7)

We then have from (6) and (7),∑R∗ − R =P (θ) {R∗ (θ) − R(θ)}
θ

]
∑ [
∑
P (θ) (n − |J(θ)| − 1)(v − c) +P (∅, θ−j ) (v − c)
≥
θ∈Θsc

=δ

∑ [

j∈J(θ)(n − |J(θ)| − 1)(v − c) + |J(θ)| (v − c)

]

θ∈Θsc
sc

= δ |Θ | (n − 1)(v − c).

Proof of Proposition 4. Γ is clearly individually rational. To see that it is strategyproof, note ﬁrst that agent i1 has no incentive to misreport his type since the groupformed or his transfer is independent of his report. Take any i ̸= i1 .
1) If i is strongly preference-connected to i1 and hence belongs to the group(i ∈ Y (θ)) under θ, then his payoﬀ is given byui (g(θ), θi ) − xi (θ) = v − (v −

ε
ε
)= .
n
n

If i reports θi′ such that i still belongs to the group under (θi′ , θ−i ), then his
payoﬀ is unchanged. If i reports θi′ such that i is not strongly preferenceconnected to i1 , then he is not oﬀered an assignment and his payoﬀ equalsεn which is the transfer made to him. It follows that i has no incentive to
misreport his type.
2) If i is not strongly preference-connected to i1 and hence does not belong to
the group under θ, then his payoﬀ equals the transfer made to him: nε . If hereports θi′ that makes him still not strongly preference-connected to i1 under(θi′ , θ−i ), then his payoﬀ is unchanged. On the other hand, if he reports θi′22which makes him strongly preference-connected to i1 , then his payoﬀ equalsv − (v − nε ) = nε if the assignment g(θi′ , θ−i ) also includes some agent in θi , and−(v − nε ) otherwise. In every case, i has no incentive to misreport his type.
We have hence shown that Γ is strategy-proof. To see that Γ also is uniquely
acceptable, note that ai = 1 is a strictly dominant action for i = i1 , and ai = 1 isiteratively strictly dominant for any i ∈ Y (θ).
Proof of Proposition 5. Let ΘH (n) be the set of type proﬁles θ = (θ1 , . . . , θn ) suchthat the directed graph D(θ) has a Hamiltonian cycle: There exists a directed closed
path that goes through every agent. For any θ ∈ ΘH (n), hence, every agent j ̸= i isstrongly preference-connected to i, and hence the group formed by the single groupmechanism covers all the agents. This further implies that ΘH (n) ⊂ Θε (n). On theother hand, when the probability p(n) satisﬁes the stated condition, the probabilityof ΘH (n) approaches 1 as n → ∞ (McDiarmid 1981, Theorem 4.7).14 It follows thatlim Pp (θ ∈ Θε (n)) ≥ lim Pp (θ ∈ ΘH (n)) = 1.

n→∞

n→∞

Proof of Proposition 6.
1) Suppose ﬁrst that agent i ∈ Fs (θ) for some s ∈ S(θ).
If θi ̸= ∅, then Fs (θ) is a strong component of D(θ) by deﬁnition, and henceui (g(θ), θi ) = v. If θi = ∅, then ui (g(θ), θi ) = 0. Since xi (θ) = − nε in bothcases, i’s payoﬀ under θ equals{ε
if θi = ∅,ui (g(θ), θi ) − xi (θ) = n
εv + n otherwise.
If i reports θi′ such that i ∈ Fs′ (θi′ , θ−i ) for some s′ ∈ S(θi′ , θ−i ), then his payoﬀ
equals{εif θi ∩ Gs′ (θi′ , θ−i ) = ∅,′′ui (g(θi , θ−i ), θi ) − xi (θi , θ−i ) = n
v + nε otherwise.
Since θi = ∅ implies θi ∩ Gs′ (θi′ , θ−i ) = ∅, it follows that reporting θi′ is not
a proﬁtable deviation whether θi = ∅ or not. If i reports θi′ such that i ∈Ys′ (θi′ , θ−i ) for some s′ ∈ S(θi′ , θ−i ), then i’s payoﬀ equals{
0 − (v − nε ) if θi ∩ Gs′ (θi′ , θ−i ) = ∅,ui (g(θi′ , θ−i ), θi ) − xi (θi′ , θ−i ) =(8)v − (v − nε ) otherwise.
14

See also Bollobás (2001, p217).

23

If i reports θi′ such that i ∈/ G(θi′ , θ−i ), then his payoﬀ equals nε . It follows thatreporting θi′ is not a proﬁtable deviation in either case.
2) Suppose that agent i ∈ Ys (θ) for some s ∈ S(θ). Since then xi (θ) = v − nε andui (g(θi , θ−i ), θi ) = v, i’s payoﬀ under θ equalsεεui (g(θ), θi ) − xi (θ) = v − (v − ) = .
nnFurthermore, no j ∈ θi is strongly preference-connected to i under θ−i sinceotherwise, i and j would be part of a strong component and hence i ∈ Fs (θ)
would hold. If i reports θi′ such that i ∈ Fs′ (θi′ , θ−i ) for some s′ ∈ S(θi′ , θ−i ),then θi ∩ Gs′ (θi′ , θ−i ) = ∅ since by deﬁnition, Gs′ (θi′ , θ−i ) contains only thoseagents who are strongly preference-connected to i under θ−i , but as noted
above, no agent j ∈ θi is strongly preference-connected to i under θ−i . Hence,ui (g(θi′ , θ−i ), θi ) = 0. It follows that his payoﬀ equalsui (g(θi′ , θ−i ), θi ) − xi (θi′ , θ−i ) =ε.
n

If i reports θi′ such that i ∈ Ys′ (θi′ , θ−i ) for some s′ ∈ S(θi′ , θ−i ), then i’s payoﬀ/ G(θi′ , θ−i ), thenis given by (8), and hence ≤ nε . If i reports θi′ such that i ∈his payoﬀ equals nε . It follows that misreporting is not a proﬁtable deviationin any of these cases.
3) Suppose that agent i ∈/ G(θ). In this case, θi = ∅ and xi (θ) = − nε so thatui (g(θi , θ−i ), θi ) − xi (θi ) = nε . If i reports θi′ such that i ∈ Gs′ (θi′ , θ−i ) for somes′ ∈ S ′ (θ), then ui (g(θi′ , θ−i ), θi ) = 0 and xi (θi′ , θ−i ) = v − nε or − nε dependingon whether i belongs to a strong component of D(θi′ , θ−i ) or not. In either
case, ui (g(θi′ , θ−i ), θi ) − xi (θi′ , θ−i ) ≤ nε so that misreporting is not a proﬁtabledeviation.
The same argument as in the proof of Proposition 2 shows that Γ is uniquely
acceptable.
Proof of Lemma 1. Let Γ be a multiple group mechanism, and take any component
C of D(θ) with two or more agents. Deﬁne CF = {i ∈ C : θi = ∅} and CY ={i ∈ C : θi ̸= ∅}. Since D(θ) contains no strong component, F (θ) and Y (θ) in thedeﬁnition of a multiple group mechanism satisfy F (θ) ∩ C ⊂ CF and Y (θ) ∩ C = CY .
Denote F (θ)∩C = {h1 , . . . , hM }, and let (Ym (θ))M
m=1 be the corresponding partitionKof CY according to g. By deﬁnition, if (Fk , Yk )k=1 is any collection such that (Yk )K
k=1
is a partition of CY , (Fk )K
k=1 is a collection of distinct singleton subsets of CF , andYk ⊂ C;Fk (Yk , θ) for every k, thenM ≤ K.
24(9)

Since xi (θ) = − nε for every i ∈ CF and xi (θ) = v − nε for every i ∈ CY , the platform’s
payoﬀ under (g, x) from the component C is given byεεε− c) − |CF ∩ F (θ)| ( + c) − |CF \ F (θ)|
nnnε= |CY |(v − c) − |CF ∩ F (θ)|c − |C| .
n|CY | (v −On the other hand, we claim that the ﬁrst-best payoﬀ for the platform under complete information from the component C is given by|CY |(v − c) − |CF ∩ F (θ)|c.
Let (F ∗ , Y ∗ ) be the pair of disjoint subsets of C that solves (4). Since θi ̸= ∅ forevery i ∈ Y ∗ by deﬁnition, we have Y ∗ ⊂ CY . If Y ∗ ⊊ CY , let Y ′ = Y ∗ ∪ {i} fori ∈ CY \ Y ∗ and F ′ = F ∗ ∪ {j} for j ∈ CF such that j ∈ θi . Since v − 2c > 0, wethen have|Y ′ |(v − c) − |F ′ |c ≥ (|Y ∗ | + 1)(v − c) − (|F ∗ | + 1)c= |Y ∗ |(v − c) − |F ∗ |c + v − 2c
> |Y ∗ |(v − c) − |F ∗ |c,which contradicts our assumption that (F ∗ , Y ∗ ) maximizes (4). We hence haveY ∗ = CY = C ∩ Y (θ). Denote F ∗ = {i1 , . . . , iK } and note that there exists a∗∗
15 Indeed, if wepartition (Yk∗ )K
k=1 of CY such that Yk ⊂ C;ik (Yk , θ) for every k.
k−1
deﬁne Y1∗ = C;i1 (θ), and Yk∗ = C;ik (θ) \ (∪ℓ=1 Yℓ∗ ) for k = 2, . . . , K, then Yk∗ ⊂∗ K
C;ik (Yk∗ , θ) for every k.16 Since the collection ({ik }, Yk∗ )K
k=1 is such that (Yk )k=1 is
a partition of CY , and Yk∗ ⊂ C; (Yk∗ , θ) for every k, we have by (9) that M ≤ K.
This shows that (C ∩ F (θ), C ∩ Y (θ)) maximizes (4) so that |Y ∗ |(v − c) − |F ∗ |c =|C ∩ Y (θ)|(v − c) − |C ∩ F (θ)|c.
Under θ, hence, the platform’s payoﬀ from the component C under the multiple
group mechanism is within |C| nε of the corresponding ﬁrst-best payoﬀ. Hence, thediﬀerence in total payoﬀ under θ is at most ε.
Proof of Proposition 7. Consider ﬁrst the probability that D(θ) contains no pair(i, j) of agents who are strongly preference-connected to each other (i.e., both links
i → j and j → i exist). We havenPp (D(θ) contains no strongly preference-connected {i, j}) = (1 − p2 )( 2 ) .

It may be the case that Yk∗ = ∅ for some k.
Suppose to the contrary that there exists i ∈ Yk∗ such that for any directed path from i to ik ,k−1
there exists j ̸= ik such that j ∈/ Yk on the path. By deﬁnition, j ∈ ∪ℓ=1
Yℓ so that i ∈ Yℓ∗ for some∗∗ℓ < k, which is a contradiction. We hence have Yk ⊂ C;ik (Yk , θ).
15

16

25

2

If we let k = nτ 2 , then k → ∞ as n → ∞, and the above probability can be evaluated
as
(

)n

2 (2)

1−p

(
τ 2 ) n21 ) τ 2 k ((1 )k ) τ2> 1− 2= 1−= 1−→ 1 as n → ∞.
n
k
k
(

2

2

2

We next consider the probability that D(θ) contains a strongly preference-connected
set of three or more agents. For this, consider an auxiliary undirected graph U (θ)
obtained from D(θ) by ignoring direction of links in D(θ) and if there are two links
i → j and j → i between i and j, replacing them by a single undirected link. Then
Pp (U (θ) contains an (undirected) link ij) = 1 − (1 − p)2 < 2p,
and hence the stated condition on τ implies (Diestel 2000, p. 248) that
Pp (U (θ) contains an (undirected) cycle of length ≥ 3) → 0 as n → ∞.
Since
Pp (G(θ) contains a directed cycle of length ≥ 3)
≤ Pp (U (θ) contains an undirected cycle of length ≥ 3),
we conclude that Pp (G(θ) has a directed cycle of length ≥ 3) → 0 as n → ∞. Combining the above arguments, we have
Pp (G(θ) contains a strongly preference-connected set of agents) → 0 as n → ∞.

References
Alcalde, J. & Revilla, P. (2004), ‘Researching with whom? stability and manipulation’, Journal of Mathematical Economics 40(8), 869 – 887.
Aoyagi, M. (2013), ‘Coordinating adoption decisions under externalities and incomplete information’, Games and Economic Behavior 77(1), 77 – 89.
Aoyagi, M. (2018), ‘Bertrand competition under network externalities’, Journal of
Economic Theory 178(C), 517–550.
Bloch, F. & Quérou, N. (2013), ‘Pricing in social networks’, Games and Economic
Behavior 80, 243 – 261.
Board, S. (2009), ‘Monopolistic group design with peer eﬀects’, Theoretical Economics 4(1), 89–125.
26

Bollobás, B. (2001), Random Graphs, 2nd edn, Cambridge University Press.
Caillaud, B. & Jullien, B. (2003), ‘Chicken & egg: Competition among intermediation service providers’, The RAND Journal of Economics 34(2), 309–328.
Candogan, O., Bimpikis, K. & Ozdaglar, A. (2012), ‘Optimal pricing in networks
with externalities’, Operations Research 60(4), 883–905.
Cechlárová, K. & Romero-Medina, A. (2001), ‘Stability in coalition formation
games’, International Journal of Game Theory 29(4), 487–494.
Chen, Y., Zenou, Y. & Zhou, J. (2018), ‘Competitive pricing strategies in social
networks’, RAND Journal of Economics 49(3), 672–705.
Chen, Y., Zenou, Y. & Zhou, J. (2020), Network topology and market structure.
discussion paper, CEPR.
Damiano, E. & Li, H. (2007), ‘Price discrimination and eﬃcient matching’, Economic Theory 30(2), 243–263.
Diestel, R. (2000), Graph Theory, 2nd edn, Springer.
Dimitrov, D., Borm, P., Hendrick, R. & Shao, C. S. (2006), ‘Simple priorities andcore stability in hedonic games’, Social Choice and Welfare 26(2), 421–433.
Dybvig, P. H. & Spatt, C. S. (1983), ‘Adoption externalities as public goods’, Journalof Public Economics 20(2), 231 – 247.
Fainmesser, I. P. & Galeotti, A. (2016), ‘Pricing network eﬀects’, Review of Economic Studies 83(1), 165–198.
Gomes, R. & Pavan, A. (2016), ‘Many-to-many matching and price discrimination’,
Theoretical Economics 11(3), 1005–1052.
Hoppe, H. C., Moldovanu, B. & Ozdenoren, E. (2011), ‘Coarse matching with incomplete information’, Economic Theory 47(1), 75–104.
McDiarmid, C. (1981), ‘General percolation and random graphs’, Advances in applied probability 13(1), 40–60.
Myerson, R. B. (1982), ‘Optimal coordination mechanisms in generalized principalagent problems’, Journal of Mathematical Economics 10(1), 67–81.
Rodrı́guez-Álvarez, C. (2009), ‘Strategy-proof coalition formation’, International
Journal of Game Theory 38(3), 431–452.
27

Veiga, A. (2013), Platforms exclude but do not segregate. working paper, Toulouse
School of Economics.

28