ISSN (Print) 0473-453X

Discussion Paper No. 1186

ISSN (Online) 2435-0982

MANY-TO-MANY MATCHING
ON A SKILL-SHARING PLATFORM

Masaki Aoyagi

August 2022

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

Many-to-Many Matching on a Skill-Sharing Platform∗
Masaki Aoyagi†
August 30, 2022

Abstract
Each agent in a market needs to supplement his skill with a particular skillof another agent to complete his project. A platform matches the agents andallows members of the same match to share their skills. A match is valuable toan agent if he is matched with any agent who possesses a skill complementary to
his own skill. When the platform uses the divide-and-conquer pricing strategy,
we study the properties of incentive compatible mechanisms in relation to thereciprocal property of the complementary relationships among different skills,
and when the market expands in its size.
Key words: platform, network externalities, divide and conquer, revenue maximization, ex post IC.
JEL Codes: D42, D47, D62, D82, L12

1

Introduction

Platforms as intermediaries of economic activities are gaining importance in themodern economy with the development of information technology. Two-sided platforms that match firms and workers, men and women, entrepreneurs and investors,
and so on, are all popular forms of matching platforms that help subscribers realize economic gains. Among them, this paper focuses on skill-sharing platforms foragents who are entrepreneurs endowed with heterogeneous skills. Each entrepreneur
has a private project that yields a positive value to them when completed. To complete their own project, however, each agent must supplement their own skill withanother skill, which may be possessed by other agents. For example, an agent with∗

I am grateful to Satyanath Bhat for his comment on an earlier version of this paper. Financial
support from the JSPS (grant numbers: 21653016, 24653048, 15K13006, 22330061, 15H03328,
15H05728 and 20H05631), 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

a food delivery project needs to complement his cooking skill with a financial skill,or an agent with an advertising business project needs to complement his IT skill
with a graphic design skill, and so on. The platform matches entrepreneurs andallows subscribing members of the same match to share their skills. Our analysis
considers both a one-sided market in which every agent is ex ante homogeneous anddraw their skills from the same set, and a two-sided market in which there exist twoclasses of agents who draw their skills from disjoint sets. In a two-sided market,
we assume that complementary skills of an agent on one side can be possessed only
by agents on the other side. We may suppose, for example, agents on one side areendowed with dexterity skills while those on the other side are equipped with hardskills.
The platform is a monopolist and designs a mechanism that operates in twostages. In the first stage, it collects information about the private skill type fromeach agent and then matches them based on their reported types. In the second
stage, the platform presents to the agents the matching along with discriminatory
subscription prices, which the agents accept or reject. We require (ex post) incentive
compatibility in the first stage so that it is weakly dominant for each agent to reporttheir skill types truthfully. Addition of the second stage addresses the possibilityof coordination failures under network externalities when the platform cannot force
the matching on the agents: Whether an agent should subscribe or not depends onthe decisions of other agents in the same match who have a complementary skill
required for his own project. Subscription for a positive price is worthwhile to theagent only if other subscribing agents have useful skills for him.1 We require thatthe mechanism resolve such uncertainty by making acceptance a unique equilibriumoutcome when the agents strategically respond to the subscription offers, and saythat a mechanism is uniquely enforceable if it has this property along with incentive
compatibility.
The relationship between any skill and the set of its complementary skills is captured by what we call a complementary-skill network. Specifically, a complementaryskill network is a directed network with a link from skill s to skill t if and only if t iscomplementary for skill s. The complementary-skill network can take many different forms. In particular, the network is perfectly reciprocal if for any pair of skillss and t, “s is complementary for t” ⇒ “t is complementary for s,” and is perfectly
non-reciprocal if for any pair of skills s and t, “s is complementary for t” ⇒ “t isnot complementary for s.” There are numerous intermediate patterns between these1

The equilibrium multiplicity in the game of adoption decisions is a central concern in theanalysis of network externalities. See Dybvig and Spatt (1983). The multiplicity problem is also
known as “chicken and egg” in the two-sided market literature (Caillaud and Jullien (2003)).

2

two extremes. Furthermore, we say that a complementary-skill network is r-regular
if the number of complementary skills is the same and equals r for every skill.
In the complete information benchmark where the platform observes the agents’skill types, unique enforceability requires that the platform combine matching withthe divide-and-conquer pricing strategy: A small subsidy is offered to some membersof a match and positive price is charged to others for whom the skills of the subsidized
agents are complementary. In the optimum, the number of agents in the first set isminimized whereas that in the latter set is maximized. We say that a mechanism
extracts full surplus under incomplete information if it yields the same expected
revenue as the optimal mechanism under complete information.
Under incomplete information, we present a class of uniquely enforceable matching mechanisms also based on the divide-and-conquer pricing strategy. These mechanisms, called single-match mechanisms, create at most one match. Specifically, thismechanism targets a fixed set I1 of agents as the core agents, and identifies the set
I2 of agents for whom the skills possessed by the members of I1 are complementary.
It then identifies the set I3 of agents for whom the skills possessed by the membersof I2 are complementary, and so on, and creates a single match involving all theseagents. The core agents in I1 are offered a small subsidy, whereas the agents in
I2 , I3 , . . . , are charged a price close to the value of the completed project. The set I1of core agents is a choice variable in the formulation of a single-match mechanism.
The standard pricing strategy in a two-sided market that offers a subsidy to allagents on one-side and charges positive prices to all agents on the other side corresponds to one single-match mechanism in which many agents belong to I1 . In theother extreme, a single-match mechanism may set I1 = {i1 } for some single agent
i1 .
The revenue performance of any given single-match mechanism generally depends on the choice of the set I1 of subsidized agents as well as the underlying
complementary-skill network. For example, the single-match mechanism performs
poorly if the number of complementary skills for each skill is small and if I1 has a
few agents since then the skills collectively possessed by I1 will not be complementary to many other agents either directly or indirectly. On the other hand, it will
perform better if each skill has many complementary skills. Suppose then that thecomplementary-skill network is regular so that each skill has the same number ofcomplementary skills. In such a case, the probability distribution of the number of
agents involved in the match is uniquely determined independently of the specification of reciprocity as mentioned above. This rather surprising conclusion, which
is a consequence of the percolation theorem (McDiarmid, 1981), implies revenue
equivalence for any pair of complementary-skill networks that are both r-regular.

3In comparison with the first-best benchmark under complete information, a small
degree of non-reciprocity of the complementary-skill network implies that the optimal mechanism under incomplete information fails to extract full surplus when themarket size is fixed. This observation prompts us to study the asymptotic properties of the above mechanisms when the market expands in its size. We show thatthe single-match mechanism based on a single agent i1 is asymptotically optimal
provided that the underlying complementary-skill network is a supergraph of any 1regular network. In particular, as the market expands, the probability that i1 ’s skill
is complementary to every agent either directly or indirectly approaches one, implying that the platform can charge a price close to the value of the completed project
to every agent but i1 with probability close to one. This result uses the fact thatwhen the number of agents becomes large, the complementary-agent network is connected with probability close to one provided that the complementary-skill network
is perfectly reciprocal. This result can be generalized to the complementary-skill
network that is not perfectly reciprocal because of the revenue equivalence result
described above.
The contribution of the paper can be summarized as follows: First, it offers
a first analysis of a model in which the deterministic complementary relationships
among the skills translate to random complementary relationships among the agentsthrough the random realization of their types, and identifies how the reciprocity
property of the complementary skills may or may not be important from the perspective of revenue maximization by a monopolistic platform. Specifically, it showsthat the application of the percolation theorem yields a revenue equivalence result
as mentioned above.
Second, the single-match mechanism generalizes the standard divide-and-conquer
strategy in a two-sided market that subsidizes all agents on one side and charges
positive prices to agents on the other side. Our result demonstrates its effectivenessunder incomplete information and also shows that a single subsidy is all it takes toattract all agents when the market expands in its size provided that the underlying
complementary-skill network remains constant and satisfies some mild condition as
described above.
The paper is organized as follows. We discuss the related literature in Section 2.
Section 3 presents a model and Section 4 describes the requirements of unique enforceability. The benchmark case of complete information is analyzed in Section 5,
and the implication of incomplete information is discussed in Section 6. We formulate the single-match mechanisms in Section 7 and present the revenue equivalence
result in Section 8. The asymptotic optimality of these mechanisms is presented in
Section 9. We conclude with a discussion in Section 10.

4

2

Related Literature

The present paper belongs to the literature on a monopolistic platform that provides
privately informed agents access to each other for subscription prices. The pioneering
work by Damiano and Li (2007) studies a two-sided market where each side of themarket consists of agents with heterogeneous quality, and the value of a match
between any pair of agents is the product of the two individual qualities. The
platform maximizes revenue by creating multiple “rooms” for agents, and each agent
is randomly matched with the agents from the other side who are assigned the sameroom. Adopting the framework of Damiano and Li (2007), Hoppe et al. (2011)
analyze the performance of the coarse matching scheme in which the market isdivided into only two matches. Gomes and Pavan (2016) study eﬀicient and profitmaximizing platforms for many-to-many matching in a two-sided market where eachagent has a private type that determines the match value. Board (2009) studies
matching in a one-sided market, and shows that the profit maximizing planner
creates too many matches from a welfare point of view under various specifications of
the match value as a function of the qualities of its members. Veiga (2013) shows thatthe profit maximizing planner always creates a single match when a larger match
always has a higher quality than a smaller match. The common assumption in these
papers is that agents have vertically differentiated qualities so that agents with highqualities are unanimously preferred. In contrast, agents in our model are horizontallydifferentiated and different agents prefer to be matched with different skill types.
Our framework is hence closer to that in the two-sided matching literature where
each agent is assumed to have a heterogeneous preference ordering over agents on theother side.2 Extensive literature on matching theory is on the design of a mechanismthat matches agents with private preferences over other agents. Most closely related
among them are the papers on coalition formation, which consider the problem ofpartitioning the set of agents into matches and the value of a match to any member
is a function of the types of other members. For example, Cechlárová and RomeroMedina (2001) assume that the value of a match to any member is equal to either his
most-preferred member, or his least-preferred member, Alcalde and Revilla (2004)
introduce a preference which evaluates matches based on the best subset of them,and Dimitrov et al. (2006) and Rodríguez-Álvarez (2009) suppose that each agent
evaluates the quality of a match based on the numbers of friends and enemies in it.
While the primary focus of the matching literature is on the stability of matching,
Marx and Schummer (2021) present the revenue analysis of a monopolistic two-sided
platform when it matches agents one-to-one using a deferred acceptance algorithm.
2

Another difference is that the literature studies a screening mechanism which determines anagent’s assignment as a function only of his type and not of the type profile of all agents.

5

Unlike these papers, however, the present paper assumes that the agents’ preferences
are over the skills possessed by other agents rather than over the agents themselves.
One key difference from the matching literature implied by this assumption is thatthe present model is one of interdependent values since the value of a match to any
agent is a function of not only his own type, but also the types of the agents he ismatched with.
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. Monopoly
sale of a network good under incomplete information is studied by Aoyagi (2013),
where the value of the good to each agent is the product of the agent’s private
type and the size of adoption. Some models of network goods monopoly express
local network externalities by networks of agents as in the present paper. Amongthem, Candogan et al. (2012) characterize the relationship between the location ofa buyer in the network and the price he faces under imperfect and perfect pricediscrimination, and Bloch and Quérou (2013) examine the optimality of price discrimination when each buyer is privately informed about the stand-alone valuationof the monopolist’s good. Aoyagi (2018), Chen et al. (2018), and Chen et al. (2020)
formulate models of price competition between sellers of goods with local network
externalities. Among them, Aoyagi (2018) examines the extent to which the divideand-conquer pricing strategy influences the equilibrium price configuration. Thesemodels of local network externalities, however, assume that the agent network isfixed and publicly observed unlike in the current paper.

3

Model

The market consists of the set I of n ≥ 2 agents. Each agent i owns a project andalso is endowed with a private skill θi drawn from a finite set Θi . Denote by Θ theset of skill profiles θ = (θi )i∈I .
The market is one-sided if the agents are ex ante homogeneous and two-sided if
there exist two ex ante heterogeneous classes of agents. If the market is two-sided,
we refer to the two class as side A and side B, and use the same symbols to denotethe corresponding subsets of agents. Let na = |A| and nb = |B| denote the numbersof agents on the two sides (n = na + nb ).
Let Σ be the finite set of skills. In a one-sided market, each agent draws his skill
from Σ so that Θi = Σ for every i ∈ I. In a two-sided market, on the other hand,Σ consists of an even number of skills and is partitioned into two groups ΣA andΣB of the same size. An agent draws his skill from ΣA if he is on side A and from
ΣB if he is on side B: Θi = ΣA if i ∈ A and Θi = ΣB if i ∈ B. In what follows,6we denote by S ≥ 2 the total number of skills (S = |Σ|) if the market is one-sided,
and the number of skills on each side S = |ΣA | = |ΣB | if the market is two-sided.
In each case, we assume that each skill type is equally likely for every agent:Pr(θi = s) =1
Sfor every s ∈ Σ and i ∈ I.

Each project yields v > 0 to its owner if completed and 0 otherwise. Agent i’s project
can be successfully completed if his skill θi is complemented with a particular skillof a different kind. A complementary skill for any skill s is a skill that leads to thecompletion of the project owned by the agent who has skill s. For any skill s ∈ Σ,
denote by C(s) ⊂ Σ the set of complementary skills for skill s. In a two-sided market,
complementary skills exist only on the other side of the market so that C(s) ⊂ ΣB
if s ∈ ΣA and C(s) ⊂ ΣA if s ∈ ΣB . Define Zst to be the binary variable that equals
one if and only if skill t is complementary to skill s:(
1 if t ∈ C(s),Zst =0 otherwise.
It is useful to interpret Z as a directed graph which has skills as nodes: There is a linkfrom skill s to skill t if and only if Zst = 1. We call this graph a complementary-skill
network. In a two-sided market, a complementary-skill network is a directed bipartite
graph with node partition (ΣA , ΣB ) since no link exists within ΣA or within ΣB . A
complementary-skill network is r-regular if |C(s)| = r for every s ∈ Σ. Equivalently,
it is r-regular if the indegree and outdegree of every node equals r ≥ 1:
X
X
Zst′ =
Zs′ t = r.
t′s′

A pair of skills s, t ∈ Σ are reciprocal if Zst = 1 ⇒ Zts = 1, and non-reciprocal if
Zst = 1 ⇒ Zts = 0. A complementary-skill network Z is perfectly reciprocal if every
pair of skills are reciprocal, perfectly non-reciprocal if every pair of skills are nonreciprocal, and partially reciprocal if there exist both reciprocal and non-reciprocal
pairs. Figures 1 and 2 illustrate some complementary-skill networks in a one-sided
market and a two-sided market, respectively.
The realizations of random skill types are independent across agents. Given any
type profile θ ∈ Θ and any pair of agents i and j, define Xij (θ) by
Xij (θ) = Zθi θj .
In other words, Xij (θ) = 1 if and only if agent j possesses a complementary skill
for agent i. Let Xij be the corresponding random variable. Just as in the case of
7

s

s
w

t

w

t

v

u

s

v

u

Z5R

w

t
v

u
Z5I

Z5N

Figure 1: Complementary-skill networks in a one-sided market
Σ = {s, t, u, v, w}. The networks are all 2-regular, and perfectly reciprocal (Z5R ), perfectly
non-reciprocal (Z5N ), and imperfectly reciprocal (Z5I ).

sA

sB

sA

sB

sA

sB

tA

tB

tA

tB

tA

tB

uA

uB

uA

uB

uA

uB

R
Z3,3

N
Z3,3

I
Z3,3

Figure 2: Complementary-skill networks in a two-sided market
ΣA = {sA , tA , uA } and ΣB = {sB , tB , uB }. The networks are all 1-regular, and perfectlyRNI
reciprocal (Z3,3), perfectly non-reciprocal (Z3,3), and partially reciprocal (Z3,3).

8the complementary-skill network Z, we identify X = (Xij )i,j∈I as a directed graphwhich now has the agents as nodes: Xij = 1 if and only if this graph has a directed
link i → j. We refer to X as a complementary-agent network. When the market
is two-sided, X(θ) is a directed bipartite graph on the partition (A, B) for any θ.
Unlike Z, however, the complementary-agent network X is randomly determined by
θ. In X(θ), agent i is strongly connected to agent j, denoted i ;θ j, if there is adirected path from i to j: 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), there is adirected link ik → ik+1 (⇔ Xik ik+1 (θ) = 1). We write ; instead of ;θ when θ isevident. A subset H ⊂ I of agents is strongly connected if i ; j for every pair (i, j)of agents in H. H ⊂ I is a strong component if it is strongly connected and there
exists no H ′ ̸⊃ H that is strongly connected. i is connected to j if there is a pathfrom i to j when the direction of each link is ignored. H ⊂ I is component if any
pair of agents in H are connected, and no H ′ ̸⊃ H has such a property.
A matching g = (gi )i∈I ∈ G ≡ {0, 1, . . . , n}n is the partition of agents. Agent i
is assigned to match k if gi = k ≥ 1, and not assigned to any match if gi = 0. For
k ≥ 1, let Gk = {j : gj = k} denote the set of agents who are assigned to match k,
and G = ∪k≥1 Gk the set of agents who are assigned to some match. We say that theplatform offers subscription to agent i if i ∈ G. We will use g and G interchangeably
to express a matching. Agents i and j (i ̸= j) can share their skills if and only ifthey belong to the same match: gi = gj ≥ 1. Given the skill profile θ ∈ Θ, agent i’svaluation ui (g, θ) of the matching g = (gi )i∈I is determined as follows:(ui (g, θ) =v

if i ∈ Gk (θ) and0

otherwise.

P

j∈Gk (θ) Xij (θ) ≥ 1 for some k ≥ 1,

In other words, the value of a matching to any agent equals the value v of thecompleted project if a member of his match has a complementary skill for him, andequals zero otherwise. Note that the value of a match to any agent is independent of
the exact number of agents who possess complementary skills for him or the numberof agents who find those skills useful. In other words, once in a match each skill istreated as a public good.3
A (many-to-many) matching mechanism of the platform solicits reports from theagents about their skill types, and then offers a matching along with subscription
prices as a function of the reported types. Formally, it is characterized by a pairof a matching rule g : Θ → G and a transfer rule t = (ti )i∈I : Θ → RI : g(θ) is amatching, and ti (θ) is monetary transfer from i, both when the reported type profile
3

Since a skill of no agent is available to any agent outside the match, we may consider the skill
to be an excludable public good.

9

is θ.
The platform’s cost of providing subscription service to any single agent equals
c, which is assumed to satisfyv
0<c< .
(1)
2
It follows that the net social surplus is negative (= −c) when the platform offers
subscription to a single (unmatched) agent i, but is positive (≥ v − 2c) when it
matches two agents i and j either of whom finds the other’s skill complementary(θj ∈ C(θi )). Denote by R(θ | Γ) the platform’s payoff when it employs mechanism
Γ and the agents’ type profile is θ:X
R(θ | Γ) =ti (θ) − |G(θ)|c.
i∈IThe platform’s expected payoff R(Γ) under the mechanism Γ is defined accordingly:R(Γ) = E R(θ | Γ) .

4

An Enforceable Mechanism

A mechanism Γ with (g, t) is ex post incentive compatible (ex post IC) if for every
θi , θi′ ∈ Θi , θ−i ∈ Θ−i , and i ∈ I,
ui (g(θi , θ−i ), θi , θ−i ) − ti (θi , θ−i ) ≥ ui (g(θi′ , θ−i ), θi , θ−i ) − ti (θi′ , θ−i ),and individually rational if for every θi ∈ Θi , θ−i ∈ Θ−i , and i ∈ I,
ui (g(θi , θ−i ), θi , θ−i ) − ti (θi , θ−i ) ≥ 0.
As mentioned in the Introduction, we address equilibrium multiplicity under adoption externalities by considering a version of a revelation-suggestion mechanism as in
Myerson (1982). Specifically, we suppose that the platform makes take-it-or-leave-it
offers to the agents by presenting the matching and subscription prices ((g(θ), t(θ))
along with the reported type profile θ, and the agents play a subscription game inwhich they simultaneously decide to accept or reject the offers. If any agent rejects the offer, then he takes the outside option whose value is normalized to zero.
Formally, let Ai = {0, 1} denote the set of actions available to agent i ∈ I in the subscription game, where ai = 0 and ai = 1 represent rejection and acceptance of theoffer, respectively.4 The platform makes offers expecting acceptance by every agent,
4

If agent i is not offered subscription gi = 0, then his choice ai only determines whether or not
he accepts the transfer ti . For any such i, hence, ai = 1 implies a non-positive transfer ti ≤ 0, andhis decision is irrelevant to the adoption decisions of those who are offered subscription.

10

or equivalently, action profile a∗ = (1, . . . , 1). When the agents instead choose theaction profile a ̸= a∗ , the realized matching is different from what is proposed. We
suppose that the action profile a in response to the offer g results in a matchingg a = (gia )i∈I such that for every i,(
gi if ai = 1,
gia =0 otherwise.
That is, only those agents who accept their subscription offers will be matched.5
Accordingly, given the offer (g, t) and the reported type profile θ, agent i’s payofffrom the action profile a is given by(ui (g a , θ) − ti if ai = 1,
Ui (a, θ | Γ) =0otherwise.
We say that a mechanism Γ with (g, t) is uniquely acceptable if for every type profile
θ, the action profile a∗ = (1, . . . , 1) is the unique Nash equilibrium of the subscription game (I, A, (Ui (a, θ | g(θ), x(θ)))i∈I ) for every θ ∈ Θ. Since agent i’s payoffui (g(θ), θ) − ti (θ) in equilibrium must be non-negative, (g, t) is individually rational
if it is uniquely acceptable. A mechanism is uniquely enforceable if it is ex post
IC and uniquely acceptable.6 By ex post IC, no unilateral deviation that involves
misreporting in stage 1 and acceptance in stage 2 is profitable. No unilateral deviation that involves rejection in stage 2 is profitable either since any such deviation
yields zero, whereas truthful reporting and acceptance yield at least zero by uniqueacceptability. We hence have the following observation.
Proposition 1. If Γ is uniquely enforceable, then it implements (g, t) 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’ skill profile θ, or equivalently, the underlying
complementary-agent network X(θ). In this case, we only require the mechanism
Γ to be uniquely acceptable. Define R∗ (θ) to be the supremum of the platform’s
payoff from such mechanisms:R∗ (θ) = sup {R(θ | Γ) : Γ is uniquely acceptable},
We may alternatively suppose that gia = 0 if a ̸= a∗ so that no agent subscribes when someagent rejects the offer.
6Note that unique enforceability does not imply the uniqueness of a PBE in the two-stage game,making our requirement different from that for unique (full) implementation.
5

11and R∗ = E[R∗ (θ)].
For any set F ⊂ I of agents and i ∈/ F , we write i ; F if i ;θ j for some j ∈ F .
Define (F ∗ , Y ∗ ) ≡ (F ∗ (θ), Y ∗ (θ)) to be a solution to the following maximization
problem:(
F , Y ⊂ I,
(2)
max |Y |(v − c) − |F |c subject to(F,Y )
Y = {j ∈/ F : j ;θ F }.
(2) has a solution since I is finite, and gives the maximal payoff that the platform
can achieve from any uniquely acceptable mechanism as seen in Proposition 2 below.
The intuition is as follows: The objective function corresponds to the platform’s
payoff when it offers subscription for free to agents in F , but for the price v toagents in Y . Since Y is chosen so that its members are strongly connected to someagent in F , agents in Y are indeed willing to pay up to v for subscription if it also
includes F . The platform then maximizes its payoff by taking Y as large as possible(since v − c > 0), while taking F as small as possible (since c > 0).
We next show that for any ε > 0, there exists a uniquely acceptable mechanism
Γ such that R(θ | Γ) = |Y ∗ (θ)|(v − c) − |F ∗ (θ)|c − ε for the solution (F ∗ (θ), Y ∗ (θ))
to (2). Let the matching rule g be defined by(
1 if i ∈ F ∗ (θ) ∪ Y ∗ (θ),
gi (θ) =(3)0 otherwise.
In other words, g matches all agents in F ∗ with those strongly connected to them.
The transfer rule t is given by(− nε
if i ∈/ Y ∗ (θ),(4)
ti (θ) =v − nε if i ∈ Y ∗ (θ),
In other words, agents in F ∗ (θ) are offered a small subsidy whereas agents in Y ∗ (θ)
are charged a fee close to their full valuation v.7
Proposition 2. Suppose that the platform has complete information about θ. ThenR∗ (θ) = |Y ∗ (θ)|(v − c) − |F ∗ (θ)|c.
Furthermore, Γ with (g, t) defined in (2) and (4) is uniquely acceptable, and satisfies
R(θ | Γ) = R∗ (θ) − ε for every θ.
7

As specified, agents who are offered no subscription are also given a small subsidy. This is toensure that the equilibrium of the adoption game is unique, but is irrelevant for the decisions ofagents who are offered subscription.

12

Note that the maximized payoff is strictly positive for every component of two
or more agents since 2c < v. When the complementary-agent network X(θ) is as
described in Figure 3, for example, (2) has the solution F ∗ = {5, 6} and Y ∗ ={1, 2, 4, 7, 8, 9, 10}, and its value equals R∗ = 7(v − c) − 2c = 7v − 9c. Note thatagent 3 is not offered subscription since it is not possible to make positive profits outof him, and also any agent who can be attracted by agent 3 (i.e., agent 9) can also
be attracted by another agent (i.e., agent 5) who is already offered subscription. In
the subscription stage, acceptance is a strictly dominant action for every agent inF ∗ , and is an iteratively strictly dominant action for agents in Y ∗ . The number of
iteration required for each agent in Y ∗ to find out that acceptance is an optimal
action equals the length of the shortest directed path that connects him with agentsin F ∗ .
A

F∗

B

1

6 F∗

2

7

3

8

4

9

5

10

Y∗

Figure 3: Optimal mechanism under complete information
The figure depicts a two sided-market but the construction is the same in a one-sided market.

6

Limits on Rent Extraction under Incomplete Information

We now return to the incomplete information environment in which the realizationof s is not observable to the platform. Specifically, we show that when there exists minimal imperfection in the reciprocity of complementary skills, the optimalmechanism Γ leaves informational rents to the agents as shown in the following
13

proposition.8
Proposition 3. Suppose that the complementary-skill network Z is such that there
exist skills s, s′ , t ∈ Σ such that
Zss′ = 0,(Zst , Zts ) = (1, 0),and (Zs′ t , Zts′ ) = (0, 1).

Then there exists κ ≡ κ(n, Z) > 0 such that if the expected revenue under a uniquely
enforceable mechanism Γ is bounded away from the optimal level by κ: R(Γ) ≤ R∗ −κ.
Note that when the market is two-sided, Zst = Zts′ = 1 in the second and third
conditions implies that the skills s and s′ are on the same side and hence implies
the first condition Zss′ = 0. The proposition is based on the observation that fora mechanism to prevent agent j with skill type θj from misreporting his type as θj′against some skill profile θ−j of others, it has to either exclude j from subscription
or create a separate match for j when he reports θj′ so that he would not gain accessto any agent who has a complementary skill for the skill type θj . In either case, it
results in a loss of revenue for the platform since exclusion implies less agents paying
positive subscription prices and creation of another match requires at least one agent
to be offered free subscription. We should emphasize that κ, which is interpreted
as a lower bound for the agents’ informational rents, depends on both Z and n.
For a fixed market size n, if the complementary-skill network is such that Zst = 0
for most skill pairs (s, t), then the complementary-agent network is empty (i.e.,
Xij = Xji = 0 for every pair (i, j) ∈ A × B) with probability close to one, and hence
the platform’s payoff approaches zero even under complete information. On theother hand, if Zst = 1 for most skill pairs (s, t), the complementary-agent network
is complete (i.e., Xij = Xji = 1 for every pair (i, j) ∈ A × B) with probability close
to one, and the mechanism described in the next section that creates a single match
will become optimal. Our primary interest hence is on what happens for the lessextreme specifications of Z.

7

Single-Match Mechanism

In this section, we describe a class of uniquely enforceable mechanisms under incomplete information. Specifically, we consider a single-match mechanism which
specifies some non-empty subset of agents I1 and matches with I1 all agents whoare strongly connected to I1 , provided that the set of such agents is non-empty.
The mechanism offers a subsidy to every agent in I1 while charging a positive price8

When the complementary-skill network is perfectly reciprocal, it is an open question whether
or not there exists a mechanism that achieves the first-best.

14

to other matched agents. Formally, the single-match mechanism Γs (I1 ) based on
I1 ̸= ∅ has the matching rule g : Θ → {0, 1} and the transfer rule t : Θ → Rn suchthat(
1 if {j : j ;θ I1 } ̸= ∅ and i ∈ I1 ∪ {j : j ;θ I1 },gi (θ) =0 otherwise,and for ε > 0,(ti (θ) =v − nεif i ;θ I1 ,− nεotherwise.

Figure 4 illustrates a single-match mechanism based on I1 = {6}. Note that agent
i1 is the only agent who may possibly enjoy informational rents close to v under thismechanism. It is also important that the specification of I1 cannot be contingent
on the realization of θ. If the skill types were observable, it is tempting to target
the most “popular” agents as I1 (i.e., agent i whose skill is found complementaryby the largest number of agents). 9 With unobservable types, however, choice of I1
according to their popularity based on the agents’ reported types potentially createsa serious incentive problem. For example, if the most popular agent i is tied withanother agent j, then it can create room for profitable misreporting by j: Insteadof reporting his true type θj for which Xji (θj , θ−j ) = 1, j can report θj′ such thatPP
Xji (θj′ , θ−j ) = 0 and k Xkj (θj′ , θ−j ) ≥ k Xkj (θ). Such misreporting reduces i’svotes by one, while not reducing j’s votes, making j the uniquely most popular
agent under (θj′ , θ−j ).
Under the single-match mechanism, note that agent i1 has no incentive to misreport his type since it does not change the outcome in any way. Any agent j forwhom i1 ’s skill is complementary also has no misreporting incentive: If j reports atype for which i1 ’s type is not complementary, he will be offered no subscription,
whereas if he reports a type for which i1 ’s type is complementary, it will result inthe same outcome as truth-telling. The same reasoning applies to other agents who
are offered subscription, implying the following conclusion.10
Proposition 4. For any I1 ̸= ∅, the single-match mechanism Γs (I1 ) based on I1 isuniquely enforceable.
9Bernstein and Winter (2012) present comprehensive analysis of the optimal divide-and-conquer
pricing strategy under complete information when the externalities are heterogeneous and discuss
its relationship with the popularity of each agent.
10
Unique enforceability of the single match mechanism hinges on the ability of the platform to
make public the profiles of the agents’ reported types θ and price offers t(θ): This enables theagents to identify the uniquely optimal action choice through iterative reasoning. See Miklós-Thaland Shaffer (2017).

15

A

B

1

6 F = {i1 }

2

7

3

8

4

9

5

10

Y

Figure 4: Single match mechanism based on i1 = 6

When the set I1 of subsidized agents is small compared with the market size n,sΓ (I1 ) is typically ineﬀicient unless p is very large since with non-negligible probability, only a few agents are strongly connected to I1 : The platform can charge apositive price only to a small number of agents. In Figure 4, for example, a singlematch mechanism based on i1 = 4, 7 or 9 ends up with matching no agents andfails to make positive profits. When the market is very large, on the other hand, it
is clear that for any skill, some members of a very large match have the skills complementary to it. It follows that such a match is valuable to every agent and theagents would be willing to pay up to v for subscription if they were not concerned
about coordination failures. There is, however, no guarantee that such coordinationis achieved when the platform offers a subscription price close to v to every agent.
As seen in Section 9, however, the problem of the single match being not too large
and that of coordination failures can simultaneously be resolved when the market
grows in its size.

8

Percolation Theorem and Revenue Equivalence

In this section, we invoke the percolation theorem of McDiarmid (1981) to establishthat when the complementary skill network Z is r-regular for some r, the singlematch mechanism Γs introduced in Section 7 yields the same expected revenue
regardless of the reciprocity property of Z.
Recall that S = |Σ| is the number of total skills in the case of the one-sided
market and the number of skills on each side S = |ΣA | = |ΣB | in the case of16

Xij \ Xji

1

0

1
0

2q
S2

2q
r
S − S22q
1 − 2rS + S22q
r
S − S2

Table 1: Joint distributions of Xij and Xji when Z is r-regular(i, j) ∈ A × B in the case of a two-sided market.

the two-sided market. When the complementary-skill network Z is r-regular, theprobability that there is a link between any pair (i, j) of agents on the different sides
is given byr
Pr(Xij = 1) = .
S
The key implication of the regularity of Z is the independence of the occurrence oflinks between any different pairs of agents.
Lemma 5. Suppose that the complementary-skill network Z is regular. Then Xij
and Xi′ j ′ are independent unless (i, j) = (i′ , j ′ ) or (i, j) = (j ′ , i′ ).
This result is an important step toward the application of the percolation theorem below since it requires the independence of the link occurrence between different
pairs. As can be seen from the proof of Lemma 5, a suﬀicient condition for such
independence is that Pr(s ∈ C(θi )) and Pr(θi ∈ C(t)) are all the same for every i ∈ I
and s, t ∈ Σ. Regularity of Z ensures that this holds under our assumption thatevery skill type is equally likely.
Turning now to the two links Xij and Xji of opposite directions between thesame pair of agents (i, j), we see that they are not independent. In fact, different
specifications of the reciprocity of the complementary-skill network Z imply different degrees of correlation between them. Clearly, Xij = Xji when Z is perfectly
reciprocal, and Xij Xji = 0 when Z is perfectly non-reciprocal. More generally,
define q to be the number of reciprocal pairs of skills in Z as follows.11
q=1{(s, t) : Zst = Zts = 1} .
2When Z is r-regular, the joint distribution of (Xij , Xji ) is a function of q as describedin Table 1.
The percolation theorem of McDiarmid (1981, Theorem 4.2) shows that for any
set J ⊂ I \ I1 of agents, the probability that all agents in J are strongly connectedwith I1 in X is the same regardless of the joint distribution of Xij and Xji as long11

For example, q = 5, 0, and 2 in Z5R , Z5N and Z5I , respectively, in Figure 1.

17

as the link occurrence between different pairs of agents is independent.12 It thenfollows from Lemma 5 that when Z is r-regular, the expected revenue from thesingle-match mechanism is also independent of q, or equivalently the reciprocity
property of Z.
Proposition 6. (Revenue equivalence of the single-match mechanism) Let I1 ⊊ I
be given, and suppose that Γs is a single-match mechanism based on I1 . If thecomplementary-skill networks Z and Z ′ are both r-regular for some r ≥ 1, then the
expected revenue R(Γs ) from Γs is the same under Z and Z ′ .
One implication of Proposition 6 is that the expected revenue from the standard
pricing strategy in the two-sided market that subsidizes all agents on one side andcharges the positive price v on the other side is independent of the reciprocity
property of the underlying complementary-skill network as long as it is regular.

9

Asymptotic Optimality of Single-Match Mechanisms

We now investigate the performance of the single-match mechanism when the market expands in its size. In the case of a two-sided market, we assume that market
expansion takes place while keeping the relative size of each side in balance. Specifically, we say that a sequence of two-sided markets is balanced if there exists ρ > 1such that for every n,
1
nb
<
< ρ.
ρ
na
Define Θ;I1 to be the set of type profiles such that every agent is strongly connected
to I1 :
Θ;I1 = {θ : i ̸= i1 ⇒ i ;θ I1 }.
Lemma 7. Suppose that the complementary-skill network Z is perfectly reciprocal
and regular. Consider any sequence of one-sided markets or any balanced sequenceof two-sided markets for n = 2, . . ., and let I1 be a non-empty subset of agents which
may also be a function of the size n of the market. Then for every ε > 0, there
exists N > 0 such that if n > N , thenPr Θ;I1 > 1 − ε.
The intuition behind the result is as follows. When the complementary-skill
network is regular and perfectly reciprocal, the corresponding complementary-agent
12

To gain some intuition, assume I = {1, 2, 3} and verify that the probability that both 2 and 3
are strongly connected to 1 equals 3( Sr )2 − 2( Sr )3 regardless of the value of q.

18

network X is such that Xij = 1 if and only if Xji = 1, so that we can identify
X(θ) with an undirected graph G(θ) which has a link between i and j if and only
if Xij = Xji = 1 in X(θ). Note that every agent j ∈/ I1 is strongly connected to
I1 in X if G is connected. Furthermore, since Lemma 5 implies that Xij and Xi′ j ′between two different pairs (i, j) and (i′ , j ′ ) are independent when Z is regular, G
is the standard Erdős-Rényi type random graph. Lemma 7 is then established if
the probability that G is connected approaches one as n → ∞. This holds in both
one-sided and two-sided markets when Pr(Xij = 1) is held constant as n increases.
Now denote by Θsε (n) the set of type profiles θ at which the expected revenue
from the single-match mechanism Γs described above is within ε of the optimal level:Θsε = {θ : R(θ | Γs ) > R∗ (θ) − ε}.
Let Z be the set of all complementary-skill networks such that every Ẑ ∈ Z isa supergraph of some 1-regular complementary-skill network Z. In other words,Ẑ ∈ Z is a complementary-skill network obtained by adding directed links to some
1-regular complementary-skill network Z.
Proposition 8. Let the complementary-skill network Z ∈ Z be given. For any
sequence of one-sided markets, or any balanced sequence of two-sided markets, thesingle-match mechanism Γs based on a single agent I1 = {i1 } is asymptotically
optimal: For every ε > 0, there exists N > 0 such that if n > N , thenPr(θ ∈ Θsε ) > 1 − ε.

(5)When every agent is strongly connected to i1 in X, the single-match mechanism
based on i1 charges a subscription price close to v to all agents but i1 , and hence
its revenue is close to the bound R∗ achieved under complete information. Since
the probability that X is strongly connected to i1 approaches one by Lemma 7
when Z is 1-regular and perfectly reciprocal, the single-match mechanism Γs is
asymptotically optimal for such a Z. It then follows from Proposition 6 that thesame holds true if Ẑ is any complementary-skill network that is 1-regular but not
perfectly reciprocal. Finally, take any Z̄ ∈ Z. By assumption, Z̄ can be obtained byadding directed links to some 1-regular complementary-skill network Z. Let X̄ and
X be the complementary-agent networks corresponding to Z̄ and Z, respectively.
For any θ ∈ Θ, X(θ) is a subgraph of X̄(θ) since whenever there is a directed link
between i and j in X(θ), there is a link of the same direction between them in X̄(θ).
It follows that if an agent is strongly connected to i1 in X(θ), then he is also strongly
corrected to i1 in X̄(θ). We can hence conclude that the single-match mechanism is
asymptotically optimal for any Z ∈ Z.
19

As mentioned earlier, the standard pricing strategy in a two-sided market takes
the form of the divide-and-conquer strategy that corresponds to the single-matchmechanism Γs based on either I1 = A or B. What is the performance of sucha strategy in a large two-sided market? For concreteness, suppose the two sides
are of the same size na = nb = n2 and consider Γs (A) based on I1 = A. If thecomplementary-agent network X is strongly connected, then it is clear that allagents on side B subscribe for a full price under Γs (A) while all but one agent
subscribe for a full price under the single-match mechanism Γs (i1 ) based on a single
agent. Since when Z ∈ Z, X is strongly connected with probability close to one forn large, it follows that Γs (i1 ) raises approximately twice as much revenue as Γs (A).
When the market is not so large, on the other hand, the number of agents in B who
are strongly connected to A is on average much larger than the number of agents
who are strongly connected to i1 , and hence Γs (A) would yield a higher expected
revenue than Γs (i1 ).
As an application of Theorem 8, consider the following model which takes adifferent interpretation of a skill type of each agent. Suppose that there exists a
set Λ of two or more skills that are required to complete the project of any agent
regardless of his type. The skill type of each agent corresponds to a subset of Λ:Σ = {s : s ⊂ Λ, s ̸= Λ, ∅}.
The skill type t is complementary to the skill type s if all the required skills arecovered by them. Hence, the complementary-skill network Z is given by(
1 if s ∪ t = Λ,Zst =0 otherwise.
It follows that Z is perfectly reciprocal but not regular since different skill types
with different numbers of elements have different numbers of complementary skills.
Figure 5 illustrates a complementary-skill network when |Λ| = 3. Note that the skill
type {λ} has one complementary skill type {µ, ν}, whereas the skill type {λ, µ} has
three complementary skill types {ν}, {λ, ν}, and {µ, ν}.
The complementary-skill network Z is a supergraph of a 1-regular network: Z ∈Z. In fact, if we define Ẑ by(
1 if s ∪ t = Σ and s ∩ t = ∅,Ẑst =
0 otherwise,
then Ẑ is 1-regular and a subgraph of Z. It follows that the single-match mechanism
Γs (i1 ) based on a single agent is asymptotically optimal by Proposition 8.
20

{λ}{λ, µ}{λ, ν}{µ}{ν}{µ, ν}

Figure 5: Complementary-skill network Z when Λ = {λ, µ, ν}.

10Conclusion

The complementary-skill network describes the relationship between any skill andthe set of their complementary skills that are required to complete the project owned
by each agent. Through random and private realization of the skill type of eachagent, the complementary-skill network translates into the random complementary
network over agents endowed with heterogeneous skills. Agents share their skills
when matched by a platform and hence a match has positive value to any agent if
it involves another agent who has a complementary skill to his own skill.
While divide-and-conquer in a two-sided market typically subsidizes all agentson one side and charges a positive price to the other side, the uniquely enforceable
mechanisms we study generalizes such a pricing scheme by allowing the platform
to subsidize any subset I1 of agents. We show that the platform’s revenue under
this class of mechanisms satisfies the following properties. First, when the set I1of subsidized agents is fixed, the platform’s expected revenue from the single-matchmechanism is independent of the reciprocity properties of the complementary-skill
network as long as each skill type has the same number of complementary skills.
Second, provided that each skill type has at least one complementary skill and eachskill is complementary to at least one skill type, the expected revenue associated withthe single-match mechanism that subsidizes just a single agent I1 = {i1 } approaches
the first-best level that is achievable under the complete information benchmark as
the market expands in its size.
Possible extensions are as follows. First, we have assumed that an agent’s skill
becomes a public good within a match so that its value to each agent is independentof the level of congestion. More generally, we may suppose that a match value foran agent is higher in when more members of his match has complementary skills,
or lower when more members of his match compete for the same complementary
21

skills. In a large market, however, the simpler specification that we adopt is not too
restrictive in the environment of Proposition 8 since the single-match mechanism
matches every agent with high probability in a large market and since the fractionof each skill type averages out because of the law of large numbers.
Second, we have assumed that there is a single complementary skill for eachagent.13 We may suppose instead that each agent needs to be matched with two
or more agents with different skills to complete their projects. For concreteness,
suppose that each agent has a single skill but needs to access two other skills ofother agents. The single match mechanism based on a single agent i1 is clearly notuniquely enforceable since subscription is not a dominant action for any agent evenconditional on i1 ’s subscription decision. It is not clear if providing subsidies to two
agents is useful. On the other hand, the single-match mechanism that subsidizes
all agents on one side in a two-sided market is uniquely enforceable even with thismodification. The smallest number of subsidies that ensure unique enforceability is
an open question.

Appendix
Proof of Proposition 2. We first show thatR∗ (θ) ≤ |Y ∗ (θ)|(v − c) − |F ∗ (θ)|c.
Suppose to the contrary that a uniquely acceptable mechanism Γ̂ with (ĝ, t̂) yields
the payoff R(θ | Γ̂) > |Y (θ)|(v − c) − |F (θ)|c. Let Ŷ = {i ∈ I : t̂i (θ) > 0}
be the set of agents who are offered subscription for strictly positive prices, andF̂ = {i ∈ I : t̂i (θ) ≤ 0} be the set of agents who are offered subscription for nonpositive prices. Note first that there exists i1 ∈ Ŷ who is not strongly connected toF̂ since otherwise, (F̂ , Ŷ ) would be feasible in (2). Let J1 = {i1 }, and let J2 ⊂ Ŷ
be the set of agents in Ŷ to whom i1 is strongly connected: J2 = {j ∈ Ŷ : i1 ; j}.
Since i1 is charged a positive price, IR implies that J2 ̸= ∅, and furthermore, since
i1 is not strongly connected to F̂ , no j ∈ J2 is strongly connected to F̂ . Let thenJ3 ⊂ Ŷ be the set of agents j to whom agents in J2 are strongly connected. In thesame way, we can iteratively construct a sequence J4 , J5 , . . . of subsets of Ŷ so thatno agent in those subsets is strongly connected to F̂ . Since Ŷ is finite, however,
we will have Jk+1 ⊂ ∪kℓ=1 Jℓ for some k. We then have a contradiction to uniqueacceptability since then for agents i in the set ∪kℓ=1 Jℓ , rejection ai = 0 is a Nashequilibrium action since they are all charged positive subscription prices.
13

However, each skill type may correspond to multiple skills as in the last example of Section 9.

22

Ã

j

Ã

B̃

B̃

s

t

s

t

s

t

s

t

s

t

s′

t

j

Figure 6: Type profiles θ (left) and θ′ (right)(Ã, B̃) = (A, B) if the market is two-sided. Only agent j changes his type from s to s′ .

The mechanism Γ with (g, t) defined in (3) and (4) is clearly uniquely acceptable:
For i ∈ F ∗ (θ), ti (θ) < 0 so that subscription ai = 1 is a dominant action. For
j ∈ Y ∗ (θ), aj = 1 is an iteratively dominant action since Y ∗ (θ) consists of all agents
who are strongly connected to some i ∈ F ∗ (θ): For any j ∈ Y ∗ (θ), either i ∈ θjfor some i ∈ F ∗ (θ) or there exists k ∈ Y (θ) with k ∈ C;F ∗ (θ) (θ). Rejection isdominated in the second round of the iterative elimination procedure in the firstcase, whereas in the second case, it is iteratively dominated for j in one round after
it is dominated for k. Finally, the platform’s payoff under Γ equals
R(θ | Γ) = |Y ∗ (θ)|(v − c) − |F ∗ (θ)|c − ε.
Since ε is arbitrary, R∗ (θ) ≥ |Y ∗ (θ)|(v − c) − |F ∗ (θ)|c. We hence obtain the statedconclusion.
n
Proof of Proposition 3. Let δ = S1
> 0 so that P (θ) ≥ δ for every θ ∈ Θ. By′
assumption, we can take s, s ∈ ΣA and t ∈ ΣB such that
Zss′ = 0,(Zst , Zts ) = (1, 0),and (Zs′ t , Zts′ ) = (0, 1).

Let (Ã, B̃) be a binary partition of the set I of agents such that both Ã and B̃ are
non-empty. Specifically, we take Ã = A and B̃ = B if the market is two-sided. Letña = |Ã| and ñb = |B̃|. Take any agent j ∈ Ã and consider the type profiles θ andθ′ as follows (Figure 6):(s if i ∈ Ã \ {j},s if i ∈ Ã,
θi =and θi = s′ if i = j,
t if i ∈ B̃.
t if i ∈ B̃.

23

Since every agent in Ã is strongly connected to every agent in B̃ but no agent
in B̃ is strongly corrected to any agent in Ã under θ, the optimal mechanism Γ∗under complete information creates a single match consisting of all agents in Ã andone agent in B̃, and the supremum of the revenue from such a mechanism equalsR∗ (θ) = ña v − (ña + 1)c. On the other hand, since every agent i ̸= j is strongly
connected to j under θ′ , the optimal mechanism Γ∗ under complete information
again creates a single match and its revenue equals R∗ (θ′ ) = (n − 1)v − nc.
Let R(·) denote the supremum of the revenue from a uniquely enforceable mechanism under incomplete information. We claim that max {R∗ (θ) − R(θ), R∗ (θ′ ) −R(θ′ )} ≥ c. We derive a contradiction by supposing that there exists a uniquely
enforceable mechanism Γ such that R∗ (θ) − R(θ | Γ) < c and R∗ (θ′ ) − R(θ′ | Γ) < c.
Consider first θ. Since the subscription price can be positive only for agents in
Ã, if Γ offers subscription to a total of ma agents in Ã and mb agents in B̃, andoffers non-positive prices to Ka agents in Ã, thenR(θ | Γ) ≤ (ma − Ka ) v − (ma + mb ) c = ma v − (ma + 1) c − Ka v − (mb − 1) c.
If ma < ña , Ka ≥ 1, or mb > 1, then R(θ) ≤ ña v − (ña + 2)c.14 Since this implies
that R∗ (θ) − R(θ | Γ) ≥ c, it follows that ma = ña , Ka = 0, and mb = 1 must hold.
In other words, Γ creates a single match consisting of all agents in Ã and one agent
in B̃, and charges positive prices to the agents in Ã.
Consider next θ′ . If Γ offers subscription to a total of m agents (in Ã ∪ B̃), andoffers non-positive prices to K of them, thenR(θ) ≤ (m − K) v − m c = (m − 1) v − mc − (K − 1) v.
If m < n, or K ≥ 2, then R(θ) ≤ (n − 2)v − (n − 1)c. Since this implies thatR∗ (θ) − R(θ | Γ) ≥ v − c > c, it follows that m = n and K = 1 must hold. In otherwords, Γ creates a single match consisting of all agents and offers a non-positive
price to one of them. Note that the agent who is offered free subscription must be
agent j since Zs′ s = Zs′ t = 0.
To summarize, under Γ, the subscription price for j ∈ Ã is positive when thereported profile is θ, but is non-positive when it is θ′ . In both cases, however, j isa member of the single match that also includes an agent on side A. Since Zst = 1,
against θ−j , j has an incentive to misreport his type as s′ when his true type is s.
This is a contradiction.
Since max {R∗ (θ) − R(θ), R∗ (θ′ ) − R(θ′ )} ≥ c, the expected revenue under Γ14Note that kv − (k + 1)c is strictly increasing in k.

24

satisfies
R∗ − R(Γ) =XPr(θ̃) R∗ (θ̃) − R(θ̃)θ̃

≥ Pr(θ) R∗ (θ) − R(θ) + Pr(θ′ ) R∗ (θ′ ) − R(θ′ )≥ δc.
The proof is complete once we let κ = δc.
Proof of Proposition 4. To see that Γs is ex post IC, note first that agent i1 has no
incentive to misreport since the allocation (g(θ), x(θ)) is independent of his report.
Take any i ̸= i1 .
1) If i ;θ i1 , his transfer equals ti (θ) = v − nε and hence his payoff is given byui (g(θ), θ) − ti (θ) = v − (v −εε) = > 0.
nn

If i reports θi′ such that i ;(θi′ ,θ−i ) i1 , then his payoff is unchanged. If i reports
θi′ such that i ̸;(θi′ ,θ−i ) i1 , then his payoff equals nε . It follows that i has no
incentive to misreport.
2) If i ̸;θ i1 , then his transfer equals − nε and hence his payoff is given by̸ (θi′ ,θ−i ) i1 , then his
ui (g(θ), θ) − ti (θ) = nε . If he reports θi′ such that i ;′payoff is unchanged. If he reports θi such that i ;(θi′ ,θ−i ) i1 , then his payoff
equals −(v − nε ) < 0. In either case, i has no incentive to misreport.
We have hence shown that Γs is ex post IC. To see that Γs is uniquely acceptable,
note that ai = 1 is a strictly dominant action for i = i1 , and ai = 1 is iteratively
strictly dominant for any i such that i ;θ i1 .
Proof of Lemma 5. Independence of types implies that Xij and Xi′ j ′ are independent if i ̸= i′ and j ̸= j ′ . Suppose that Z is r-regular for some r ≥ 1. For any i ∈ I
and s ∈ Σ,Pr(θi ∈ C(s)) =X

1{t∈C(s)} Pr(θi = t) =

t∈Σ

and
Pr(s ∈ C(θi )) =

X

1 X
r
Zst = ,SSt∈Σ

1{s∈C(t)} Pr(θi = t) =

t∈Σ

1 X
r
Zst = .
S
S
t∈Σ

25

To see the independence of Xij and Xik (j ̸= k), since the types θi , θj and θk are
independent, note that
X
Pr(Xij = 1, Xik = 1) =Pr(θi = s, θj , θk ∈ C(s))
s∈Σ

=

X

Pr(θi = s) Pr(θj ∈ C(s)) Pr(θk ∈ C(s))

s∈Σ

=

X

Pr(θi = s)s∈Σ=

 r 2S r 2S.

It hence follows that Pr(Xij = 1, Xik = 1) = Pr(Xij = 1) Pr(Xik = 1). We cansimilarly show that Pr(Xij = 1, Xik = 0) = Pr(Xij = 1) Pr(Xik = 0) and so on.
The proofs of the independence of Xji and Xki , and that of Xji and Xik (j ̸= k) aresimilar and omitted.
Proof of Proposition 6. Since Z is r-regular, Xij and Xi′ j ′ are independent unless(i, j) = (i′ , j ′ ) or (j ′ , i′ ) by Lemma 5 and Pr(Xij = 1) = Sr independently of thereciprocity property of Z. For any I1 ⊊ I, consider the single-match mechanism Γsbased on I1 , and let J ⊂ I \ I1 be any subset of agents outside I1 . Define ΘJ to be
the set of type profiles such that agent i ∈/ I1 is strongly connected to I1 if and only
if i ∈ J:
ΘJ = {θ ∈ Θ : i ;θ I1 ⇔ i ∈ J}.
By Theorem 4.2 of McDiarmid (1981), then, for any J ⊂ I \ I1 , the probabilityPr(θ ∈ ΘJ ) is independent of the specification of the joint distribution of (Xij , Xji )(i ̸= j). Since the expected revenue R(Γs ) from Γs is given by
X
R(Γs ) =Pr(θ ∈ ΘJ ) |J|v − ε,J⊂I\{i1 }it is also independent of the specification of Z as long as it is r-regular.
Proof of Lemma 7. As noted in the text, X is identified with an undirected graph
G and θ ∈ Θ;I1 is implied by the connectedness of G. When the market is onesided, G is the standard Erdős-Rényi type random graph, and the probability that
G is connected approaches one as n → ∞ since Pr(Xij = 1) = Sr remains constantas n increases.15 When the market is two-sided, on the other hand, Wright (1982,
Theorem 1) shows that there exists K > 0 (independent of na and nb ) such that the15

See, for example, Diestel (2000, p. 239).

26

probability that a random bipartite graph is connected approached one providedmin {na , nb } > K log max {na , nb }. This implies that
lim

n→∞
1 na
ρ < nb <ρPr(G(θ) is connected) = 1.

Proof of Proposition 8. Suppose first that Z is 1-regular and perfectly reciprocal.
Since Θsε ⊃ Θ;i1 , we have Pr(θ ∈ Θsε ) ≥ Pr(θ ∈ Θ;i1 ) → 1 as n → ∞ by Lemma 7.
It then follows from Proposition 6 that for any Z that is 1-regular but not necessarily
perfectly reciprocal, we have Pr(θ ∈ Θsε ) → 1. Finally, if Ẑ is a supergraph of any
1-regular Z, then i → i1 in X(θ) implies i → i1 in X̂(θ) so that we again havePr(θ ∈ Θsε ) → 1 as n → ∞.

References
J. Alcalde and P. Revilla. Researching with whom? stability and manipulation.
Journal of Mathematical Economics, 40(8):869–887, 2004.
doi:
doi.org/10.1016/j.jmateco.2003.12.001.
M. Aoyagi. Coordinating adoption decisions under externalities and incomplete information. Games and Economic Behavior, 77(1):77–89, 2013. doi:
doi.org/10.1016/j.geb.2012.09.004.
M. Aoyagi. Bertrand competition under network externalities. Journal of Economic
Theory, 178(C):517–550, 2018. doi: 10.1016/j.jet.2018.10.006.
S. Bernstein and E. Winter. Contracting with Heterogeneous Externalities. American Economic Journal: Microeconomics, 4(2):50–76, May 2012.
F. Bloch and N. Quérou. Pricing in social networks. Games and Economic Behavior,
80:243–261, 2013. doi: doi.org/10.1016/j.geb.2013.03.006.
S. Board. Monopolistic group design with peer effects. Theoretical Economics, 4(1):89–125, 2009.
B. Caillaud and B. Jullien. Chicken & egg: Competition among intermediation
service providers. The RAND Journal of Economics, 34(2):309–328, 2003.
15

Although the theorem assumes that Pr(Xij = Xji = 1) = 12 , the same holds when Pr(Xij =Xji = 1) = Sr since the measure induced by the latter is absolutely continuous with respect to themeasure induced by the former.

27

O. Candogan, K. Bimpikis, and A. Ozdaglar.
Optimal pricing in networks with externalities. Operations Research, 60(4):883–905, 2012. doi:
10.1287/opre.1120.1066.
K. Cechlárová and A. Romero-Medina. Stability in coalition formation games.
International Journal of Game Theory, 29(4):487–494, May 2001.
doi:
10.1007/s001820000053.
Y. Chen, Y. Zenou, and J. Zhou. Competitive pricing strategies in social networks.
RAND Journal of Economics, 49(3):672–705, September 2018. doi: 10.1111/17562171.12249.
Y. Chen, Y. Zenou, and J. Zhou. Network topology and market structure. discussion
paper, CEPR, 2020.
E. Damiano and H. Li. Price discrimination and eﬀicient matching. Economic
Theory, 30(2):243–263, 2007. doi: 10.1007/s00199-005-0058-2.
R. Diestel. Graph Theory. Springer, 2nd edition, 2000.
D. Dimitrov, P. Borm, R. Hendrick, and C. S. Shao. Simple priorities and corestability in hedonic games. Social Choice and Welfare, 26(2):421–433, 04 2006.
P. H. Dybvig and C. S. Spatt. Adoption externalities as public goods. Journal of Public Economics, 20(2):231–247, 1983. doi: doi.org/10.1016/0047-2727(83)90012-9.
R. Gomes and A. Pavan. Many-to-many matching and price discrimination. Theoretical Economics, 11(3):1005–1052, 2016. doi: 10.3982/TE1904.
H. C. Hoppe, B. Moldovanu, and E. Ozdenoren. Coarse matching with incomplete
information. Economic Theory, 47(1):75–104, 2011. doi: 10.1007/s00199-0090514-5.
P. Marx and J. Schummer. Revenue from matching platforms. Theoretical Economics, 16(3):799–824, 2021.
C. McDiarmid. General percolation and random graphs. Advances in applied probability, 13(1):40–60, 1981.
J. Miklós-Thal and G. Shaffer. Private contracting with externalities: Divide andconquer? International Journal of Industrial Organization, 50(C):460–472, 2017.
doi: 10.1016/j.ijindorg.2016.0.

28

R. B. Myerson. Optimal coordination mechanisms in generalized principalagent problems. Journal of Mathematical Economics, 10(1):67–81, 1982. doi:
doi.org/10.1016/0304-4068(82)90006-4.
C. Rodríguez-Álvarez. Strategy-proof coalition formation. International Journal ofGame Theory, 38(3):431–452, Nov 2009. doi: 10.1007/s00182-009-0162-9.
A. Veiga. Platforms exclude but do not segregate. working paper, Toulouse Schoolof Economics, July 2013.
E. M. Wright. The k-connectedness of bipartite graphs. Journal of the London
Mathematical Society, s2-25(1):7–12, 1982.

29