Description
Design Management is a business discipline that uses project management, design, strategy, and supply chain techniques to control a creative process, support a culture of creativity, and build a structure and organisation for design.
ABSTRACT
Title of dissertation: TOPICS IN MARKET DESIGN
Thayer Morrill,
Doctor of Philosophy, 2008
Dissertation directed by: Professor Lawrence Ausubel
Department of Economics
My dissertation consists of two papers covering distinct topics within Microe-
conomic Theory. The ?rst chapter is drawn from Matching Theory. One of the
oldest but least understood matching problems is Gale and Shapley’s (1962) “room-
mates problem”: is there a stable way to assign 2N students into N roommate pairs?
Unlike the classic marriage problem or college admissions problem, there need not
exist a stable solution to the roommates problem. However, the traditional notion
of stability ignores the key physical constraint that roommates require a room, and
it is therefore too restrictive. Recognition of the scarcity of rooms motivates replac-
ing stability with Pareto optimality as the relevant solution concept. This paper
proves that a Pareto optimal assignment always exists in the roommates problem,
and it provides an e?cient algorithm for ?nding a Pareto improvement starting from
any status quo. In this way, the paper reframes a classic matching problem, which
previously had no general solution, to become both solvable and economically more
meaningful.
The second chapter focuses on the role networks play in market and social
organization. In network theory, externalities play a critical role in determining
which networks are optimal. Adding links can create positive externalities, as they
potentially make distant vertices closer. On the other hand, links can result in
negative externalities if they increase congestion or add competition. This paper will
completely characterize the set of optimal and equilibrium networks for a natural
class of negative externalities models where an agent’s payo? is a function of the
degree of her neighbors. These results are in sharp contrast to the optimal and
equilibrium networks for the standard class of positive externalities models where
payo? is a function of the distance two agents are apart. This highlights the role
externalities play in optimal and equilibrium network structure.
TOPICS IN MARKET DESIGN
by
Thayer Morrill
Dissertation submitted to the Faculty of the Graduate School of the
University of Maryland, College Park in partial ful?llment
of the requirements for the degree of
Doctor of Philosophy
2008
Advisory Committee:
Professor Lawrence Ausubel, Chair/Advisor
Professor Peter Cramton
Professor Emel Filiz Ozbay
Professor Daniel Vincent
Professor Subramanian Raghavan
c _ Copyright by
Thayer Morrill
2008
Dedication
I would like to dedicate this work to my wife, Melinda Sandler Morrill. I can
not imagine going through the process without her. What I can imagine is how
much worse the end product would have been.
ii
Acknowledgments
My second year at the University of Maryland was a pivotal year for me. I
was lucky enough to have Lawrence Ausubel, Peter Cramton, and Daniel Vincent as
instructors. I may not have learned all the economics I know from the three of them,
but it is not much of an overstatement to say I learned all the economics I enjoy
from them. My committee has been extremely supportive throughout my graduate
school experience, and for that, and for all I learned from them, I am extremely
grateful.
I would like to particularly thank my adviser Lawrence Ausubel. He is my
economic role model even if he more than once wrote empirical papers. I am forever
grateful for his mentorship and support.
My wife, Melinda Sandler Morrill deserves special acknowledgment. She has
read every word in this dissertation many times over. All of these ideas where shaped
while talking to her. If any of the thoughts in these papers are expressed clearly,
she is the one who deserves the credit.
I would like to thank Daniel Aromi, Jacques Cremer, Jonah Gelbach, Emel
Filiz Ozbay, Erkut Ozbay, and John Shea for their helpful suggestions. I received
very useful comments on my job market paper during many seminars, thank you to
those participants.
Finally, I would like to thank my dog and dissertation buddy, Jerry Sandler
Morrill. Almost everything you see here was written to the sounds of Jerry snoring.
iii
Table of Contents
List of Figures v
1 Introduction 1
2 The Roommates Problem Revisited 5
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 The Roommates Problem Revisited . . . . . . . . . . . . . . . . . . . 10
2.3 The Roommate Swap Algorithm . . . . . . . . . . . . . . . . . . . . . 16
2.4 Strategic Implications . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.5 Extensions and Modeling Issues . . . . . . . . . . . . . . . . . . . . . 28
2.5.1 Extensions to the Model . . . . . . . . . . . . . . . . . . . . . 28
2.5.2 Alternative Equilibrium Concepts . . . . . . . . . . . . . . . . 30
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.7 Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.7.1 Computational Complexity . . . . . . . . . . . . . . . . . . . . 34
3 Externalities in Networks 37
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2 Graph Theory Terminology . . . . . . . . . . . . . . . . . . . . . . . 44
3.3 Degree Based Utility Functions . . . . . . . . . . . . . . . . . . . . . 46
3.3.1 Pairwise Stability . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.3.2 Equilibrium with Transfers . . . . . . . . . . . . . . . . . . . . 51
3.4 A Reduced Form Utility Model . . . . . . . . . . . . . . . . . . . . . 62
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.6 Appendix - Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
Bibliography 73
iv
List of Figures
2.1 An example of a graph with four blocks. . . . . . . . . . . . . . . . . 17
2.2 An alternating cycle with its corresponding Pareto improvement. . . . 19
2.3 A “Blossom”. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.4 A blossom before and after contraction. . . . . . . . . . . . . . . . . . 23
2.5 A non-trivial block closed under roommates, but s
1
and s
2
are not
contained in any alternating-cycle. . . . . . . . . . . . . . . . . . . . . 25
2.6 An odd cycle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.1 A complete graph and a star. . . . . . . . . . . . . . . . . . . . . . . 45
3.2 An undesirable pairwise stable graph . . . . . . . . . . . . . . . . . . 50
3.3 Trivial graph for an even and odd number of vertices. . . . . . . . . . 66
v
Chapter 1
Introduction
Matching Theory, along with Auction Theory, are two of the great success
stories of microeconomic theory. One of the original matching theory papers was
Gale and Shapley’s 1962 paper College Admission and the Stability of Marriage.
This paper consists of a simple but interesting problem, a clever algorithm, and the
discovery that the solution space has a particularly desirable attribute. Theorists
continued to study the problem simply because it was interesting and the results
they discovered were so elegant. Eventually, about twenty years after the prob-
lems were introduced, economists started to recognize that the knowledge gained
from solving these problems could be applied to designing markets, speci?cally the
doctor-hospital resident market. In this way, matching theory has followed much
of mathematics. Academics studied the problems for years because the properties
discovered are beautiful, and eventually they recognized ways in which this elegant
theory can be applied.
The progress made in matching theory is almost completely contained in the
sub?eld of two-sided Matching Theory. In two-sided matching theory, we explore
how to best pair two types of distinct agents. This is commonly called the Marriage
Problem. Just as natural, and in fact more general, is the problem of how to best
pair two agents of the same type. This question, called the Roommates Problem,
1
has received almost no attention from the literature. This is because the very paper
that introduced it, Gale and Shapley (1962), proved that there does not need to
exist a stable solution to the Roommates Problem while there always exists a stable
solution to the Marriage Problem.
1
Economists accepted that an equilibrium need
not exist to the Roommate Problem and turned their attention elsewhere.
The second chapter in my dissertation seeks to rectify this situation. An
equilibrium does always exist in the Roommates Problem, but economists have
simply been looking in the wrong place. I introduce an alternative solution to the
classic formulation of the Roommates Problem. I prove that an equilibrium always
exists under this alternate notion of stability, and I discuss several algorithms for
making an equilibrium assignment and improving one that is in disequilibrium.
This is an original and signi?cant contribution to the ?eld of economics. I have
reframed a classic problem, which previously had no general solution, in a way that
is economically more meaningful and now solvable. This is particularly important
in the context of market design. As with the Marriage Problem, the mechanisms we
study for the Roommates Problem have the potential to be applied to help mitigate
market failure in some speci?c markets.
The third chapter in my dissertation looks at a di?erent sub?eld of microe-
conomic theory, Network Theory. Classical economic theory often assumes a con-
tinuum of agents in markets. There are situations where this is both convenient
and appropriate; however, the world is fundamentally a discrete place. There is no
1
A matching is stable if no two unassigned agents prefer each other to their current
assignment.
2
market with a continuum of agents, and there are many situations where the speci?c
combinatorial characteristics of the network are critical to the economic character-
istics of the market. For example, a car manufacturer does not buy brakes from a
market. Rather it has long term relationships with a few manufacturers. Moreover,
there are relatively few manufacturers of both cars and brakes. As such, the speci?c
relationships that the manufacturers do and do not have are critical to understand-
ing the market. It is precisely in this situation where a graph, and not a continuum,
is the appropriate way to model the market.
While Network Theory has received a lot of attention in recent years, there
has been little attention paid to how the choice of utility function a?ects which
networks will emerge. This is the focus of the third chapter in my dissertation. I am
able to completely characterize one of the most natural classes of utility functions:
when the payo? an agent receives is a nonincreasing function of the degree of her
neighbors. This is meant to model congestion or competition. An agent receives a
payo? for the relationships she has, but these relationships are less bene?cial the
more people she has to compete with. The classic example in the literature is a
model of co-authors. The bene?t an academic receives from having a co-author is
decreasing in the number of co-authors that person has as she will have less time to
devote to the project.
This characterization of degree based utility models is important for its own
sake, but especially as a contrast to the known results for distance based utility
functions. A utility function is distance based if the payo? two agents receive from
being connected is a nonincreasing function of the distance they are apart in the
3
network. The networks I ?nd to be optimal and stable for a degree based function are
strikingly di?erent from the optimal networks for a distance based utility function.
The fact that both models are intuitive yet lead to dramatically di?erent optimal
networks means that when a researcher is attempting to model an economic situation
with a network based model, she needs to be particularly careful how she chooses
the underlying utility function.
4
Chapter 2
The Roommates Problem Revisited
One of the oldest but least understood matching problems is Gale and
Shapley’s (1962) “roommates problem”: is there a stable way to assign
2N students into N roommate pairs? Unlike the classic marriage prob-
lem or college admissions problem, there need not exist a stable solution
to the roommates problem. However, the traditional notion of stability
ignores the key physical constraint that roommates require a room, and
it is therefore too restrictive. Recognition of the scarcity of rooms moti-
vates replacing stability with Pareto optimality as the relevant solution
concept. This paper proves that a Pareto optimal assignment always
exists in the roommates problem, and it provides an e?cient algorithm
for ?nding a Pareto improvement starting from any status quo. In this
way, the paper reframes a classic matching problem, which previously
had no general solution, to become both solvable and economically more
meaningful.
2.1 Introduction
Economics is often de?ned as the study of how to e?ciently allocate scarce
resources. As such, assignment problems are at the heart of economics. Two-sided
matching theory asks how to best match agents of two distinct types. Examples
include students and schools, residents and hospitals, or kidneys and people in need
of a transplant. A di?erent but related question asks how to best pair two agents
of the same type. Examples of these one-sided matches include roommates at a
university, lab partners in a science class, and partners in a police force. Two-
sided matching theory has been well studied by economists who have created an
elegant and applicable theory. One-sided matching theory has been comparatively
5
neglected
1
.
This neglect is likely due to the very paper that introduced it. In their classic
1962 article College Admissions and the Stability of Marriage, Gale and Shapley
introduce both the marriage problem and the roommates problem. While Gale and
Shapley prove a stable match always exists in a two-sided market, they introduce
the roommates problem to demonstrate that a stable pairing need not exist in a one-
sided market. Since a stable match need not exist, economists have been stymied in
their attempts to ?nd and analyze solutions to this important assignment problem.
Unfortunately, this has led many economists to turn their attention elsewhere, and
as a result, the economics literature on this classic problem is sparse.
This paper starts by questioning if stability is the correct equilibrium concept.
Gale and Shapley de?ne a set of marriages as unstable if either there exist a man
and woman who are not married but prefer each other to their current spouse or
there exists someone who would prefer to be single than married to their current
partner. Stability in the roommates problem is borrowed from the marriage model.
A pairing is unstable if two students prefer to live with each other rather than their
current assignment.
2
Stability ?ts the marriage model so well that no other solution
1
Roth and Sotomayor (1990) is an excellent introduction to the two-sided matching
literature. Gus?eld and Irving (1989) is also a nice introduction. Interestingly, although
the economics literature on the roommates problem is very small, there is a comparatively
large computer science literature on it. Roth and Sotomayor, two economists, mention
the roommates problem only as an example. In contrast, Gus?eld and Irving, two com-
puter scientists, devote nearly a quarter of the book to the roommates problem. Finding
a traditionally-stable roommate pairing (if one exists) is considered a “hard” algorithmic
question. The bulk of their presentation is a polynomial-time algorithm for ?nding a
traditionally-stable pairing when one exists. Tan (1991) establishes a necessary and su?-
cient condition for the existence of a stable pairing. Chung (2000) extends Tan’s result to
a su?cient condition for the existence of a stable pairing when preferences are weak.
2
I am interested in the case where each student is required to have a roommate. Con-
6
concept has been needed or suggested. The same is not true of the roommates
problem. Roommates face an additional constraint that married couples do not;
roommates must have a room in which to live. A student may prefer another to
her assigned roommate; however, she needs a room in which to live and presumably
does not have the right to evict her current roommate. Therefore, the traditional
notion of stability is too restrictive.
I will present Gale and Shapley’s original example to highlight this point.
Example (Gale and Shapley, 1962): A Stable Assignment Need Not Exist
Suppose there are four students: ?, ?, ? and ?. ?’s top choice is ?, ?’s top
choice is ?, ?’s top choice is ?, and all three rank ? last. Gale and Shapley de?ne an
assignment to be unstable if two students are not currently roommates but prefer
each other to their current assignment. Under this de?nition, there does not exist
a stable assignment since whoever is assigned to ? prefers the other two students to
? and is the top choice of one of these students. In the words of Gale and Shapley:
“...whoever has to room with ? will want to move out, and one of the
other two will be willing to take him in.”
While one of the other two may be willing to take him in, it is quite a di?erent
matter whether this student is able to take him in. In order to take him in, either
his current roommate must voluntarily leave, be evicted, or an additional room must
be available. With a scarcity of rooms and with no student willing to change his
sequently, I do not include in my de?nition of stability the additional requirement that
each student prefers her assignment to being unassigned.
7
assignment to ?, the original assignment is an equilibrium after all.
If an agent can dissolve her partnership unilaterally, then stability is the nat-
ural equilibrium concept. If she ?nds someone she prefers who also prefers her, then
both parties will dissolve their current partnership and pair together. As a result,
the original assignment is not an equilibrium. However, if a partnership requires
bilateral agreement to dissolve, then two agents wanting to change their assignment
is not enough to disturb the original pairing. If bilateral agreement is required, an
assignment will only be changed if all involved parties agree. Since an agent will
only agree if the new assignment makes her better o?, any deviation from the orig-
inal set of assignments must be a Pareto improvement. Therefore, when bilateral
agreement is required to dissolve a partnership, Pareto optimality, not stability, is
the proper equilibrium concept. If an assignment is Pareto optimal, then there is
no reassignment that all parties will consent to; therefore, the original assignment
will not be disturbed.
Most of matching theory studies assignments that can be unilaterally dissolved.
Assignments which can only be dissolved with bilateral agreement are an important
but little studied second category. As argued above for the roommates problem,
an essential but scarce input creates the need for bilateral agreement. Additional
examples include police o?cers who require a police car to do patrol and partners
in a science class who must work at a common laboratory. The same requirement
can be created by a legally binding contract that can only be modi?ed by mutual
consent. For example, many professional athletes have no-trade clauses in their
contract which they may waive at their discretion. In the presence of such clauses,
8
the assignment of an athlete to a team can only be disturbed when all relevant
parties approve the trade.
This paper focuses on the roommates problem as reconsidered using the equi-
librium concept of Pareto optimality. I will show there always exists an e?cient
assignment. Therefore, unlike the case where stability is applied, an equilibrium
always exists in the roommates problem. Moreover, I show an ine?cient assignment
can always be Pareto improved to an e?cient one. These results motivate several
questions. If an assignment has not been made, how should we make it? If an
assignment has been made, how can we determine if the assignment is e?cient? If
an assignment is ine?cient, how can we Pareto improve it? These questions are the
focus of this paper. In particular, the last two turn out to be complicated. To an-
swer them I introduce an algorithm, The Roommate Swap, which identi?es whether
an assignment is ine?cient and ?nds a Pareto improvement when it is.
Much of the analysis in this paper relies on tools from graph theory. Networks
are a natural way of representing assignment problems, particularly one like the
roommates problem where two agents are paired. In particular, my algorithm relies
heavily on applying Edmund’s Blossom algorithm
3
to the graph theoretic represen-
tation of the roommates problem.
The paper is organized as follows. Section 2 formally introduces the problem
and proves existence. Section 3 details the Roommate Swap algorithm. Section 4
examines the strategic implications of several assignment mechanisms. Section 5
looks at extensions and modeling issues, and section 6 concludes. The appendix
3
Edmunds (1965).
9
provides several technical proofs and a discussion of the computational complexity
of the Roommate Swap algorithm.
2.2 The Roommates Problem Revisited
We wish to assign 2N students to M rooms. Students have preferences over
all other students that are strict, complete, and transitive. All rooms are identical
and students have no preference as to which room they are assigned.
An assignment is a function that pairs students. Every student is assigned to
exactly one other student, and assignments are symmetric.
De?nition 1. Let S be a set of students with [S[ = 2N. A function µ : S ? S is
an assignment of S if:
1. µ(s) ,= s.
2. µ(s
1
) = µ(s
2
) ?s
1
= s
2
.
3. µ(µ(s)) = s.
The traditional equilibrium concept is based on the notion of a blocking pair.
De?nition 2. Two students s and t are a blocking pair to an assignment µ if
µ(s) ,= t but s ~
t
µ(t) and t ~
s
µ(s). An assignment is stable if there does not
exist a blocking pair
4
.
4
The traditional de?nition of stability also includes the constraint that the person
prefers her assignment to being unassigned. In my model every student must be assigned
to some room, so I omit this additional constraint.
10
As argued in the introduction, this is not the proper equilibrium concept for
the roommates problem. A roommate assignment is an equilibrium if it is Pareto
optimal.
De?nition 3. An assignment µ is ine?cient if there exists a di?erent assignment
µ
such that for every student s, µ
(s) _
s
µ(s). An assignment is Pareto optimal
(e?cient) if it is not ine?cient.
Since preferences are strict, if µ
Pareto improves µ, then at least four stu-
dents must strictly prefer µ
to µ. As the following result proves, the set of stable
assignments is a subset of the set of e?cient assignments.
Proposition 1. If an assignment is stable, then it is Pareto e?cient.
Proof. I will prove the contrapositive. If an assignment µ is ine?cient, then there
exists an assignment µ
that Pareto improves µ. Let s be any student such that
µ(s) ,= µ
(s). Since µ
is a Pareto improvement of µ, both µ
(s) ~
s
µ(s) and
s ~
µ
(s)
µ(µ
(s)). Therefore, s and µ
(s) form a blocking pair to µ.
Note that the reverse direction need not hold. An assignment can be Pareto
e?cient but not be stable. In Gale and Shapley’s original example, no assignment
is stable yet every assignment is Pareto e?cient.
With the following assumptions, the general case of 2N students and M rooms
reduces to the more familiar case of 2N students and N rooms:
Assumption 1. Each student prefers having a room to not having a room.
11
Assumption 2. Each student would rather have a room to herself than to be as-
signed a roommate.
Assumption 3. At most two students can be assigned to a room.
Note that if N > M, some students will not be assigned a room. Such a student
cannot be involved in a Pareto improving switch by Assumption 1. Similarly, if N <
M, a number of students will not be assigned a roommate. Assumption 2 implies
such a student will never be involved in a Pareto improving switch. Therefore, the
only set of students relevant for this problem are those who have been assigned a
roommate. By Assumption 3, this set has exactly twice as many students as rooms.
Without loss of generality, for the rest of the paper I will assume there are 2N
students and N rooms.
Gale and Shapley show that an assignment without a blocking pair need not
exist. However, an e?cient assignment always exists.
Proposition 2. An e?cient roommate assignment always exists.
Proof. (Random serial dictatorship
5
) Assign every student a priority (randomly or
otherwise). Assign the student with highest priority her most preferred roommate
and remove them both from consideration. From students who remain, assign the
student with highest priority her most preferred roommate among those students
that are unassigned. Remove these two from consideration and repeat until no
5
Abdulkadiroglu and Sonmez (1998) is a very nice paper on the Random Serial Dic-
tatorship mechanism. They analyze it in the context of a housing allocation problem
where n students are to be assigned to n rooms, but it is rather interesting how robust
the Random Serial Dictatorship is. The same mechanism can be used to make a Pareto
e?cient assignment of a student and a room, two students to be roommates, three or more
students to be roommates, students to be roommates and the room they will live in, etc.
12
students remain. This assignment is Pareto e?cient. To see this, note that if a
student is involved in a Pareto improvement, then necessarily her roommate must
be involved as well. The student with highest priority, s
1
, receives her top choice,
s
2
, so neither she nor her choice can be involved in a Pareto improvement. Let s
3
be
the student who chooses second. Since neither s
1
or s
2
are involved in any Pareto
improvements, if s
3
is part of a Pareto improvement she must be reassigned to a
student among S ¸ ¦s
1
, s
2
¦. However, s
3
already receives her top choice among this
set. Therefore, s
3
(and consequently the student she chooses) is not part of any
Pareto improvement. Similarly, the student who chooses third is not part of any
Pareto improvement, and so on.
The following is a stronger statement and implies Proposition 1. It is stated
to motivate the Roommate Swap algorithm.
Proposition 3. If an assignment µ is ine?cient, there exists an e?cient assign-
ment µ
which Pareto improves µ.
The proof is straightforward but is included as it motivates the need for the
Roommate Swap Algorithm.
Proof. Let µ be an assignment and PI(µ) be the set of strict Pareto improvements
of µ. Transitivity of preference implies ?µ
? PI(µ), PI(µ
) ? PI(µ). Since µ
?
PI(µ) ¸ PI(µ
), PI(µ
) ? PI(µ). Since there are only a ?nite number of possible
assignments, the following chain must converge to the empty set:
PI(µ) ? PI(µ
1
) ? PI(µ
2
) ? . . . , where µ
i
? PI(µ
i?1
)
13
In particular, there must exist an j such that PI(µ
j
) = ?. µ
j
is an e?cient assign-
ment which Pareto improves µ.
Put simply, if µ is not e?cient, there exists a Pareto improvement µ
1
. µ
1
is
either e?cient or can be Pareto improved to µ
2
, etc. We must eventually reach
an e?cient assignment, and since preferences are transitive, this assignment must
Pareto improve µ.
Propositions 2 and 3 motivate two distinct but related problems. The ?rst
problem is how to make an e?cient assignment when no assignment has yet been
made. The second is how to Pareto improve an ine?cient assignment to an e?cient
one. Although these two problems are very similar, it is surprising how di?erent
these processes end up being. The serial dictatorship used in Proposition 2 to
show existence provides a linear-time procedure for ?nding an e?cient assignment.
In contrast to the ease of ?nding an e?cient assignment, it is rather di?cult to
even determine if any given assignment is e?cient let alone how to improve it.
Preferences between students need not interact when assigning students, but they
interact directly when determining if one assignment Pareto improves another. This
makes it signi?cantly more complicated to determine if an assignment is e?cient
than it is to simply ?nd an e?cient assignment.
At this point the reader may object as there is an obvious and trivial algorithm
to determine if an assignment is e?cient. Namely, one could simply look at each
possible reassignment and determine if it Pareto improves the original. If no as-
signment Pareto improves the original, then the original is e?cient. Unfortunately,
14
Students Number of Possible Assignments
2 1
4 3
6 15
8 105
10 945
12 10,395
14 135,135
16 2,027,025
18 34,459,425
20 654,729,075
30 6,190,283,353,629,370
2N
(2N)!
2
N
(N!)
this algorithm is of no practical use as the growth of the number of assignments
relative to students being assigned is factorial. Speci?cally, given 2N students there
exists
(2N)!
2
N
(N!)
= (2N ? 1)(2N ? 3)(2N ? 5) (3)(1) many ways of assigning them
to be roommates.
6
Even for small N, this is prohibitively large. For example, there
exists on order of 6 quadrillion (6 10
15
) many ways to assign 30 students to be
roommates. Therefore, a more sophisticated process is required.
6
A short proof appears in the Appendix.
15
2.3 The Roommate Swap Algorithm
This section demonstrates an O(n
2
) algorithm for determining if an assignment
is e?cient. Moreover, when an assignment is ine?cient I provide an O(n
3
) algorithm,
The Roommate Swap, for ?nding a Pareto improvement.
7
Much of the analysis uses
tools from graph theory, so it is necessary to present some de?nitions and results.
This document is intended to be self-contained, but I refer the reader to Introduction
to Graph Theory, second edition, by Douglas West for a more detailed analysis of
graph theory.
A graph consists of vertices and edges between them. For my purposes, all
edges are undirected.
1. Two vertices are adjacent if there is an edge between them.
2. The degree of a vertex v, denoted d(v), is the number of vertices it is adjacent
to.
3. A path is a sequence of vertices ¦v
1
, v
2
, . . . , v
k
¦ such that no vertex appears
twice and any two consecutive vertices are adjacent.
4. A cycle is a sequence of vertices ¦v
1
, v
2
, . . . , v
k
¦ such that no vertex appears
twice, any two consecutive vertices are adjacent, and v
1
and v
k
are adjacent.
5. Two vertices are connected if there is a path between them. Since our graphs
are undirected, connected is a reciprocal relationship. A graph is connected if
all vertices are connected.
7
A discussion on the computational complexity of the algorithm appears in the ap-
pendix.
16
6. A vertex is incident to an edge if it is one of the edge’s endpoints. G ¸ v is
the graph that results from deleting the vertex v and all edges incident to v.
7. A vertex v is a cut-vertex if G is connected, but G¸ v is not.
8. A block is a maximal subgraph containing no cut vertex.
Note that the subgraph consisting of two vertices and an edge between them
contains no cut-vertex, so any edge is either a block or a subset of a block. I will
refer to any block containing only two vertices as a trivial block. Since every vertex
in our graph has at least one edge incident to it, this is the smallest block possible.
Figure 2.1 shows an example where the blocks have been circled.
Figure 2.1: An example of a graph with four blocks.
De?nition 4. Given an assignment µ, a set of students X is closed under room-
mates if s ? X implies µ(s) ? X.
Given a set of preferences ~ and assignment µ, I will induce a graph, G
µ
, as
follows:
• Each vertex corresponds to a student. Label the vertices s
1
through s
n
. When
referring to the graph, I will use the term vertex and student interchangeably.
17
• A solid edge is drawn between roommates. By de?nition, each vertex is inci-
dent to exactly one solid edge.
• Draw a dashed edge between any two students that form a blocking pair to µ.
That is to say, if s
i
prefers s
j
to her current roommate and vice versa.
When the preferences and assignment are clear from the context, I will just
refer to the graph as G. I will call a path that alternates between dashed and
solid edges (or vice versa) an alternating path. Similarly, a cycle that alternates
between dashed and solid edges is an alternating cycle.
Lemma 1. An assignment µ is e?cient under preferences ~ if and only if G
µ
contains no alternating cycle. Moreover, if µ
Pareto improves µ and s is a student
such that µ(s) ,= µ
(s), then s is contained in an alternating cycle in G
µ
.
The intuition for su?ciency is captured in Figure 2.2. In an alternating cycle,
we can simply “swap” roommates. We eliminate the solid edges, make the dashed
edges in the cycle solid, and leave everyone outside the cycle unchanged. This is a
well-de?ned reassignment that Pareto improves the initial assignment.
Proof. Suppose G
µ
contains an alternating cycle C. An alternating cycle is closed
under roommates as each vertex is incident to a solid edge in the cycle. This implies
V (G) ¸ C is closed under roommates as well (V(G) means the vertex set of G). We
will construct a Pareto improvement µ
. For every v ? V (G) ¸ C let µ
(v) = µ(v).
This is well de?ned since V (G) ¸ C is closed under roommates. For every v ? C, let
µ
(v) be the vertex it shares a dashed edge with in the cycle C. This is well de?ned
18
Figure 2.2: An alternating cycle with its corresponding Pareto improvement.
S
1
S
2
S
3
S
4
S
5
S
6
S
7
S
8
S
1
S
2
S
3
S
4
S
5
S
6
S
7
S
8
as each vertex is incident to exactly one dashed edge in the cycle and sharing a
dashed edge is a reciprocal relationship. A dashed edge indicates that both vertices
prefer each other to their original assignment. Therefore, µ
Pareto improves µ.
Suppose that µ
is a Pareto improvement of µ. Let G
be the subgraph consist-
ing of all solid edges in G
µ
and only the dashed edges between vertices not paired
by µ that are paired by µ
(since µ
is a Pareto improvement, there must be a dashed
edge between such vertices). Note that any vertex v in G
either has degree
8
1 (if
µ(v) = µ
(v)) or degree 2 (if µ(v) ,= µ
(v)). Moreover, for any vertex v, if d(v) = 2,
then d(µ(v)) = d(µ
(v)) = 2. Choose any vertex t such that d(t) = 2. t is con-
nected via a solid edge to µ(t). Since d(t) = 2, d(µ(t)) = 2 and so µ(t) must be
connected via a dashed edge to µ
(µ(t)). µ
(µ(t)) must be connected via a solid edge
to µ(µ
(µ(t))) which must be connected to a dashed edge via µ
(µ(µ
(µ(t)))), and so
on. Eventually this process must cycle as there is only a ?nite number of vertices.
However, a cycle to any vertex s ,= t would mean the degree of s is at least three
which is not possible. Therefore, the process must cycle back to our ?rst vertex t.
8
The degree of a vertex v, denoted d(v), is the number of edges v is incident to.
19
Moreover, it must cycle via a dashed edge as we have already exhausted t’s solid
edge. By construction, this is an alternating cycle.
Lemma 2. Let t be any student.
1. t and µ(t) are contained in a unique block, B
t
.
2. If t is part of an alternating-cycle C, then C ? B
t
.
3. If t is involved in a Pareto improvement, then B
t
is non-trivial. That is
to say if there exists an assignment µ
such that µ
Pareto improves µ and
µ
(t) ,= µ(t), then [B
t
[ > 2.
Proof.
1. Since there is an edge between t and µ(t), they are in at least one block
together. Since the intersection of two blocks contains at most one student,
9
t
and her roommate must be in exactly one block together. Call this block B
t
.
2. A cycle contains no cut-vertex, so it must be a subset of a block. An alternating-
cycle containing t must contain µ(t) since t lies on a solid edge in the alternating-
cycle. Since B
t
is the unique block containing t and µ(t), the cycle must be
contained in B
t
.
3. If t is involved in a Pareto improvement, then by Lemma 1 t is contained in an
alternating-cycle. By (2) this alternating-cycle is contained in B
t
, so B
t
must
9
See West pg. 156. The intuition is that if if two blocks B
1
and B
2
share two vertices,
then after cutting a vertex, at least one of the two must remain. Call this vertex v. v
is connected to all remaining vertices as it is in a block with each of them. But if every
vertex has a path to v, then all vertices are connected. Therefore B
1
?B
2
has no cut-vertex
contradicting the maximality of a block.
20
contain more than just t and µ(t).
Lemma 2, part (2) says that if a student t is part of a Pareto improvement
(and consequently an alternating-cycle), then she must be reassigned to a member
of B
t
. Therefore, no edge between t and a vertex outside of B
t
can be part of an
alternating-cycle. Let G
be the graph obtained by deleting all edges between t and
any vertex not in B
t
. Then G contains an alternating-cycle if and only if G
contains
an alternating-cycle. This motivates the following procedure.
Pruning a Graph
1. Start with a graph G.
2. Determine the set of blocks B
1
, B
2
, . . . , B
m
.
3. For each student-roommate pair s and µ(s), locate the unique block that both
are in. Remove all edges from either s or µ(s) to any student outside this
block.
A key point is that if a student s was in a block B with µ(s) ,? B, then after
pruning the graph, s is no longer in B. By iterating the pruning process we end up
with a graph in which all blocks are closed under roommates. Note that these blocks
may be trivial, but by Lemma 2, the students in such a block are not involved in
any Pareto improvements.
Proposition 4. Any non-trivial block closed under roommates contains an alter-
nating cycle.
21
Figure 2.3: A “Blossom”.
s
i?2
s
i?1
s
i
s
i+1
s
i+2
s
i+3
s
i+6
s
i+5
s
i+4
The algorithm in this proof was inspired by Edmunds’ Blossom Algorithm
from graph theory
10
and Gale’s Top-Trading Cycles Algorithm.
11
Proof. Look at any non-trivial block B closed under roommates. Every vertex v in
B must be incident to a dashed edge. Otherwise v is only connected (by a solid
edge) to µ(v) which would mean removing µ(v) disconnects v from the rest of the
block. This is not possible since a block contains no cut-vertices. Start with any
vertex s. First take a dashed edge to a new vertex s
1
then continue on a solid edge
to s
2
= µ(s
1
). Continue alternating between dashed and solid edges until we cycle.
We must eventually cycle since there is a ?nite number of vertices.
If our cycle is even (a cycle is even if it contains an even number of vertices),
then we are done. By construction, an even cycle alternates between dashed and
solid edges and is therefore an alternating cycle. Therefore, assume our cycle is
odd, ¦s
i
, s
i+1
, s
i+2
, . . . , s
i+2m
¦. By construction, any odd cycle looks like Figure 2.3,
except possibly of di?erent length. Edmunds refers to this as a blossom. The vertices
¦s
1
, s
2
, . . . , s
i
¦ are the stem, s
i
is the base of the blossom, and s
i
must connect to
s
i+1
and s
i+2m
via dashed edges.
10
Edmunds (1965). A discussion of the Blossom algorithm appears in West, page 142.
11
Shapley and Scarf (1974).
22
There must by a dashed edge from one of s
i+1
, s
i+2
, . . . , s
i+2m
to a vertex
outside the cycle. Otherwise s
i
would be a cut-vertex as deleting it would disconnect
s
i+1
, s
i+2
, . . . , s
i+2m
from the rest of the graph. What we will do is contract the
odd cycle into a single super-vertex S
1
i
. The superscript indicates the number of
contractions we performed to result in S
i
. See Figure 2.4 for an example. Make any
edge that was previously between a vertex in the cycle and a vertex t outside the
cycle now between S
1
i
and t. Note that there is a solid edge between s
i?1
and S
1
i
and
all other edges incident to S
1
i
must be dashed as for any s
j
? ¦s
i+1
, s
i+2
, . . . , s
i+2m
¦,
µ(s
j
) ? ¦s
i+1
, s
i+2
, . . . , s
i+2m
¦.
Now continue with one of the unexplored dashed edges incident to S
1
j
. Again,
we must eventually cycle. If the cycle is even, stop. If the cycle is odd, contract
the blossom and continue. There must always be an unexplored dashed edge out
of an odd cycle (or else the base vertex would be a cut vertex), so after any odd
cycle we will be able to continue. Since we have a ?nite number of vertices and
edges and each contraction reduces the number of vertices, we cannot continue
inde?nitely. The algorithm only stops with an even cycle, and since the algorithm
must eventually terminate, we must eventually reach an even cycle.
Figure 2.4: A blossom before and after contraction.
s
i?1
s
i
s
i+1
s
i+2
s
i+4
s
i+3
s
i+5
s
i?1
S
1
i
s
i+5
23
Any alternating cycle containing super-vertices can be expanded to an alter-
nating cycle containing no super-vertices. No matter how we enter the blossom,
either the edge to the left or to the right is solid. We can follow the cycle in the
direction of the solid edge all the way to base vertex. This is an alternating path
to the base, the cycle connects to the base with a dashed edge, and then continues
along the stem starting with a solid edge. So indeed, this expands an alternating
path through a super-vertex to an alternating path through the cycle that was con-
tracted. If our super-vertex is the result of multiple contractions, then our base
vertex is now a super-vertex but otherwise nothing changes. Moreover, the base is
a super-vertex containing fewer contractions, so we can proceed by induction on the
number of contractions to get the desired result.
Proposition 4 implies a simple procedure for determining whether an assign-
ment is e?cient.
Determining if an assignment µ is e?cient given preferences ~.
1. Induce graph G
µ
.
2. Iteratively prune G
µ
until all blocks are closed under roommates.
3. If all blocks are trivial, then our assignment is e?cient. If there exists a non-
trivial block, then by Proposition 4 and Lemma 1, our assignment is ine?cient.
The algorithm in the proof ?nds an alternating cycle when one exists. Once
we have located an alternating cycle then just as we did in Figure 2.2 on page
24
Figure 2.5: A non-trivial block closed under roommates, but s
1
and s
2
are not
contained in any alternating-cycle.
s
1
s
3
s
5
s
2
s
4
s
6
19, we “swap” roommates to get a Pareto improvement, . For this reason I call
the algorithm the Roommate Swap. Note that we have now answered the two
key questions from the previous section. The Roommate Swap identi?es if a given
assignment is e?cient. Moreover, when an assignment is ine?cient, it ?nds a Pareto
improvement.
The Roommate Swap determines if a given assignment is e?cient. However,
a particular student likely does not care whether the assignment can be Pareto im-
proved. Rather, she would like to know if she can be part of a Pareto improvement.
Unfortunately, Proposition 4 does not generalize to the statement if a student t is
contained in a non-trivial block closed under roommates, then t is involved in a
Pareto improvement. Figure 2.5 is a non-trivial block that is closed under room-
mates, but s
1
and s
2
are not part of any Pareto improvements.
The Roommate Swap does not determine if a particular student can improve
her assignment. However, it is not biased. If we randomly choose the vertex we
start with, and when we have a choice, we randomly choose which edge to continue
on, then the Roommate Swap will ?nd any Pareto improvement with probability
that is uniformly bounded away from zero. Therefore, if the Roommate Swap is
25
run repeatedly, it will determine if an individual student is involved in a Pareto
improvement with probability one.
2.4 Strategic Implications
This paper has focused on two problems: ?nding an e?cient assignment and
?nding an e?cient Pareto improvement of an ine?cient assignment. Continuing
the pattern from previous sections, ?nding a strategy-proof mechanism for making
an assignment is easier than ?nding a strategy-proof mechanism for improving an
assignment. In fact, we will ?nd that there does not exist a mechanism for select-
ing a Pareto improvement of a given assignment that makes truthful revelation of
preferences a dominant strategy. These results follow very closely the results for
two-sided matching theory presented in Roth and Sotomayor (1990).
Following the matching literature, I will use dominant strategy as my equilib-
rium concept.
De?nition 5. A dominant strategy is a strategy that is a best response to all
possible strategies of the other agents. An assignment mechanism is strategy proof
if it is a dominant strategy for each agent to reveal her preferences truthfully.
There does exist a strategy-proof mechanism for making an e?cient assign-
ment. In fact, we have already seen this mechanism several times.
Observation 1. The serial dictatorship is strategy proof.
In the serial dictatorship, a student’s preferences are irrelevant unless she is
the one choosing her roommate. Since she gets her top choice, she does best when
26
she submits her true preferences regardless of the preferences submitted by other
students.
Finding an incentive compatible, e?cient assignment mechanism is very closely
related to Social Choice theory and Arrow’s Impossibility Theorem. The Gibbard-
Satterthwaite Theorem says that if arbitrary preferences are possible, then the
unique incentive-compatible, Pareto optimal mechanism is the dictatorship mecha-
nism. Unfortunately this cannot be directly applied as we are restricting the domain
of allowable preferences. A students is only allowed to have preferences over her own
assignment, and therefore, she is forced to be indi?erent between many assignments.
For example, a student does not have a single most-preferred assignment, but rather,
she is indi?erent among all assignments that match her to her most-preferred room-
mate. A dictator mechanism would not be Pareto optimal as, among her top choices,
the dictator would select a Pareto optimal assignment only by chance. The serial
dictatorship is the generalization of the dictatorship mechanism that has the prop-
erties of incentive compatibility and Pareto optimality. Due to the corresponding
uniqueness results for the dictatorship mechanism, it seems likely that the serial
dictatorship is the unique incentive-compatible mechanism for selecting an e?cient
assignment.
Lemma 3. There does not exist a strategy-proof mechanism for selecting a Pareto
improvement of an ine?cient assignment.
Lemma 3 is proved in the appendix. This is quite a general result, but it is
rather easy to proof. A strategy-proof mechanism must be able to handle any initial
27
assignment and any pro?le of preferences. Following the path of Roth (1982), I
demonstrate a case that no mechanism is able to handle.
2.5 Extensions and Modeling Issues
2.5.1 Extensions to the Model
Not surprisingly, the existence of an e?cient solution is quite general. For
example, if students have preferences over both their roommate and the room they
are assigned, then Propositions 2 and 3 still hold. In fact, the same proofs are still
valid. Similarly, if more than two students are assigned to be roommates, the same
existence results hold.
This paper has focused on one-sided matches, but there are many interesting
examples of two-sided matches with a physical constraint. Whenever a two-sided
match requires bilateral approval to dissolve, then any Pareto optimal assignment
will be an equilibrium. For example, an airline matches a pilot with a navigator in
order to ?y an airplane. The presence of a physical constraint, the airplane, means
a blocking pair is not enough to disturb an assignment.
The extra structure inherent in a two-sided match makes it easier to ?nd a
Pareto improvement to a two-sided match than a one-sided match. Here we can
use a slight variation of the Top Trading Cycles algorithm
12
to determine if an
assignment is Pareto optimal and to Pareto improve the assignment when it is not.
For a given pilot p, de?ne a navigator n to be achievable for p if n weakly prefers p
12
See Shapley and Scarf, 1974.
28
to her current assignment. Have each pilot point to her most-preferred, achievable
navigator. Note that a pilot always has a navigator to point to as her current
assignment is achievable. Have each navigator point to their current assignment.
There must exist a cycle since there are only a ?nite number of agents and each
agent is pointing to someone. If the cycle is trivial (the pilot is pointing to the
navigator she is currently assigned to), then neither the pilot nor the navigator can
be involved in a Pareto improvement and we can remove them from consideration. If
the cycle is non-trivial, then it represents a strict Pareto improvement for all agents
in the cycle. Future drafts of this paper will contain a more detailed discussion of
two-sided matches with a physical constraint.
When students have preferences over both their roommate and the room they
are assigned, there still exists an e?cient assignment. However, the Roommate
Swap does not readily generalize to this case. The notion of a “swap” completely
characterizes a Pareto improvement when only one other factor is involved in a
pairing; however, with multiple dimensions a Pareto improvement can be much
more complicated.
However, there is one very speci?c but important case where the Roommate
Swap can be readily generalized. If students have lexicographical preferences over
their roommate and room, then we will be able to ?nd a Pareto improvement for
any ine?cient assignment. If the students care about the room ?rst and the room-
mate second, then we can run the Top Trading Cycles algorithm to ?nd a Pareto
improvement when one exists. If a student cares about her roommate ?rst and
her room second, then we can ?rst run the Roommate Swap and next run the Top
29
Trading Cycles algorithm. There are a variety of ways we can aggregate individ-
ual preferences over rooms to a single roommate-pairing preference over rooms that
will result in an e?cient allocation. Thus, starting with an arbitrary assignment
and lexicographical preferences over roommates and rooms, we can determine if an
assignment is e?cient, and if not, Pareto improve it to an e?cient one.
2.5.2 Alternative Equilibrium Concepts
This paper has focused on pairing two agents as this is the classic framing
of the roommates problem. While I believe e?ciency, not stability, is the correct
equilibrium concept for this classic problem, the more agents that are assigned to
be together, the less compelling e?ciency becomes as an equilibrium. If six people
are assigned to an o?ce, it is likely that a person can switch desks with a student in
another o?ce without requiring unanimous approval from her current o?cemates.
We can formulate an alternative equilibrium that has more appeal in this case.
Instead of assigning six people to be o?cemates, we make six keys to each o?ce and
give each person a key to one o?ce. Since the rooms are homogeneous, this is just
an indirect way of assigning o?cemates. If we allow students to trade keys, then
an assignment is an equilibrium if no two students wish to trade o?ces. Note that
we are honoring the physical constraint; no student is being evicted. Moreover, this
does not allow a student to block another student from switching her assignment.
Similar to stability, there need not exist an equilibrium if students can trade
rooms. Suppose there are four students, a, b, c, and d, with preferences as follows:
30
a : b is most preferred
b : c is most preferred
c : d is most preferred
d : a ~ c ~ b
If a is assigned to b and c is assigned to d, then b and d will trade places. If a
is assigned to d and b is assigned to c, then a and c will trade places. Finally, if a is
assigned to c and b is assigned to d, then a and d will trade places. Since these are
the only possible assignments, there is no equilibrium.
In general, an argument can be made for either equilibrium. The new equilib-
rium might be a reasonable model for condominiums or rooms in a group house. If a
person decides to sell her condominium, she does not need the approval of the other
condominium owners in the building. Note however that there also exists building
cooperatives. Here a sale does require the approval of the board, so in this context,
Pareto optimality is a more natural equilibrium concept. Similarly, depending on
the lease a person signs, subletting a room in an apartment or group house may or
may not require the approval of the landlord or other tenants. Therefore, whether
or not Pareto optimality is the best equilibrium concept depends on the particular
lease signed.
31
2.6 Conclusion
The roommates problem is one of three assignment problems introduced by
Gale and Shapley in their classic 1962 paper College Admissions and the Stability of
Marriage. This is the paper that created the ?eld of matching theory, and the reason
why the roommates problem was included is that it is such a natural assignment
problem. While their other two assignment problems, the marriage problem and the
college admission problem, have been studied extensively, little progress has been
made on the roommates problem. This paper hopes to make several contributions to
the matching theory literature on the roommates problem. First, identifying Pareto
optimality instead of stability as the proper equilibrium makes the roommates prob-
lem economically more meaningful. With this improved equilibrium concept, I have
shown that an equilibrium always exists. Most importantly, I demonstrate how to
improve an ine?cient assignment to an e?cient one if we are not in equilibrium.
For such a natural assignment problem as the roommates problem, this is likely
to have real world applications. Therefore, this paper reframes a classic matching
problem, which previously had no general solution, in a way that is both solvable
and economically more meaningful.
2.7 Appendix
Lemma 4. There are
(2N)!
2
N
(N!)
= (2N ?1)(2N ?3)(2N ?5) (3)(1) many ways to
assign 2N students to be roommates.
Proof. The proof is by induction. When N = 1, the result is trivial as there is only
32
one way to assign two students to be roommates. Assume N > 1 and by induction
there are (2N ?3)(2N ?5) (3)(1) many ways to assign 2(N-1) many students to
be roommates. Select a student s. There are 2N-1 possible roommates for s, and by
assumption, for any roommate we pick, there are (2N ?3)(2N ?5) (3)(1) many
ways to assign the remaining 2N-2 many students. Therefore, there is a total of
[2N ?1] [(2N ?3)(2N ?5) (3)(1)] many ways of assigning roommates.
Lemma 3 There does not exist a strategy-proof mechanism for selecting a
Pareto improvement of an ine?cient assignment.
Proof. Suppose there are four students, a, b, c, and d, and an initial assignment, µ
1
pairing a with b and c with d. Moreover, suppose the student’s preferences are as
follows.
a : c ~ d ~ b
b : c ~ d ~ a
c : b ~ a ~ d
d : b ~ a ~ c
With four students, there are three possible assignment. Note that an assign-
ment is completely determined by who a (or any other student) is assigned to. Let
µ
2
denote the assignment where a is paired with c and µ
3
denote the assignment
where a is paired with d. In our original assignment µ
1
, each person is paired with
their least preferred roommate, so µ
1
is Pareto dominated by both of the other as-
signments. Suppose for contradiction that their exists a strategy-proof mechanism
M for selecting an e?cient, Pareto improving assignment. Note that if a submits the
33
preferences c ~ b ~ d and all other students submit true preferences, then µ
2
is the
only assignment that Pareto improves µ
1
(relative to the submitted preferences). In
such a case, M must select µ
2
. Similarly, if b submits the preferences c ~ a ~ d
and all other students submit true preferences, then M must select µ
3
as it is now
the only Pareto improving assignment. When all students submit true preferences,
M must select either µ
2
or µ
3
. If M selects µ
2
, then b can do better by deviating
and submitting the preferences c ~ a ~ d. If M selects µ
3
, then a can do better by
submitting preferences c ~ b ~ d. Either way, M is not strategy proof which is a
contradiction.
2.7.1 Computational Complexity
The purpose of this section is to demonstrate that the Roommate Swap is a
polynomial time algorithm and therefore implementable. I demonstrate that it is at
worst an O(N
3
) algorithm where N is the number of students.
Each iteration of the algorithm involves the following steps, performed in se-
quence:
1. Induce the graph. This is at worst O(N
2
) as a graph is de?ned by its edges
and there are at most
N(N?1)
2
many edges.
2. Iteratively prune the graph until all blocks are closed under roommates. West
(2001), pg. 157, details an O(N) algorithm for determining blocks. We need to
iterate at most N times as each iteration eliminates at least one student from
each block or stops looking at a block if it is already closed under roommates.
34
Therefore iteratively pruning the graph is at worst O(N
2
).
3. Find an alternating-cycle. This process is O(N). At each step we either travel
to a previously unvisited vertex, which we can do at most N times, or contract
a minimum of two vertices, which we can do at most
N
2
times. So the algorithm
must conclude in at most N +
N
2
steps. As it takes at most N steps to expand
a cycle containing super-vertices to a proper cycle, ?nding an alternating-cycle
concludes in O(N) time.
Therefore each iteration is O(N
2
).
Observation 2. In each iteration of the Roommate Swap, at least one student is
reassigned her top achievable student.
Proof. The search process ends with an alternating-cycle that may or may not con-
tain super-vertices. Dashed edges from standard vertices are chosen to be the ver-
tex’s most preferred student among those who prefer her to their current assignment.
Therefore, if the alternating cycle contains no super-vertices, then half the students
receive their top achievable match. A grey edge from a super-vertex is not necessar-
ily the student’s most preferred achievable student. However, if the alternating-cycle
contains a super-vertex and we need to expand our contractions, then there must
be a last odd-cycle that needs to be expanded.
Figure 6 shows a last cycle with six vertices, but the analysis is the same for
fewer or greater vertices. Our alternating path must go through s
i
and either s
i+1
or s
i+6
. None of these edges involve super-vertices (this is our last expansion) so
35
Figure 2.6: An odd cycle.
s
i?2
s
i?1
s
i
s
i+1
s
i+2
s
i+3
s
i+6
s
i+5
s
i+4
by construction, s
i+1
is s
i
’s top achievable student and s
i
is s
i+6
’s top achievable
choice. Either way, at least one student receives her top achievable choice.
The signi?cance of this is that once a student has been assigned her top achiev-
able choice, neither she nor her roommate can ever be involved in another Pareto
improvement. Therefore we can eliminate them both from consideration. Since
we eliminate at least two students after every iteration, there can be at most
N
2
iterations.
The algorithm performs O(N) many iterations of an O(N
2
) process. Therefore
it is, at worst, O(N
3
).
36
Chapter 3
Externalities in Networks
In network theory, externalities play a critical role in determining which
networks are optimal. Adding links can create positive externalities, as
they potentially make distant vertices closer. On the other hand, links
can result in negative externalities if they increase congestion or add
competition. This paper introduces two new equilibrium concepts and
will completely characterize the set of optimal and equilibrium networks
for a natural class of negative externalities models where an agent’s pay-
o? is a function of the degree of her neighbors. These results are in sharp
contrast to the optimal and equilibrium networks for the standard class
of positive externalities models where payo? is a function of the distance
two agents are apart.
3.1 Introduction
Networks have long been studied in sociology, computer science, physics and
mathematics. However, economists have only recently begun to focus on networks.
This is surprising as graphs are a natural model of many economic situations. Most
people ?nd a job through a network of friends and associates.
1
Similarly, a car
manufacturer does not buy its brakes from a marketplace but rather has long term
relationships with its suppliers.
Fortunately, networks have started to receive the attention they deserve.
2
Whether out of convenience or necessity, virtually all networking papers employ
a reduced form utility function. However, there has been very little attention paid
1
See Granovetter (1973, 1995), Rees (1966), and Montgomery (1991).
2
Jackson (2003) is an excellent survey.
37
to how the choice of utility function a?ects structural predictions. In particular,
there is an interesting feature embedded in a utility function–whether or not ad-
ditional links cause positive or negative externalities to uninvolved vertices. This
paper seeks to show that the choice of underlying utility function and the treatment
of externalities is of critical importance to which networks are optimal.
Jackson and Wolinsky’s seminal paper A Strategic Model of Social and Eco-
nomic Networks [1996, JET], hereafter JW, introduced two reduced form models
and solved for the socially optimal network in each. These models can be described
by the utility an individual gets from a graph.
JW’s Connections Model
u
i
(G) =
j=i
?
d(i,j)
?c ? d
v
i
where 0 ? ? ? 1, d(i, j) is the length of the shortest path between v
i
and v
j
, and
d
v
i
is the number of agents v
i
has an edge with.
JW’s Co-author Model
u
i
(G) =
j:e
i,j
?E(G)
[
1
d
v
i
+
1
d
v
j
+
1
d
v
i
d
v
j
]
The Connections Model has a very nice solution space. If we measure aggregate
utility as the sum of individual utilities, then the socially optimal graph is either
empty, a star, or complete. A star is a network with one central agent involved
in every connection
3
. Moreover, for appropriate link costs, these graphs will be
pairwise stable. The Co-author Model has a much less interesting solution space.
3
See Figure 3.1 on page 45 for an example.
38
For an even number of participants, 2N, the socially optimal graph is simply N
pairs. It is possibly for this reason that the Connections Model (or derivations of
it) appears much more frequently in the subsequent literature.
The star turns out to be optimal for a wide class of models. Bloch and Jackson
(2007) de?ne a utility function to be distance based if there exist c and f such that
u
i
(G) =
j=i
f(d(i, j)) ?c ? d
v
i
where d(i, j) is the number of links in the shortest path between vertices i and j,
f is a nonincreasing function, and c is a cost per link. They demonstrate that the
unique non-trivial e?cient network is the star network. The star formation appears
frequently in the literature under a variety of di?erent utility functions. Given their
result, it is not surprising that the common ingredient among these models is they
are distance based.
The fact that the star is optimal for such a wide class of utility functions makes
a compelling case for it as a real world model. However, there are at least two points
of concern. First, in the star every vertex’s payo? is strictly increasing in the size
of the network, moreover at an increasing rate. Thus, not only do these models
predict the optimal network to be a star but the largest star possible. However,
we expect real-world networks to lose their value and start to break down as they
get too large. Moreover, the entire world organized as a star is clearly not ideal for
any situation. Another concern is that, although star networks are widely predicted
by economic theory, they are not commonly observed in practice. We may observe
star-like networks such as airlines’ hub-and-spoke systems, but I know of no true
39
star networks.
A distance based model is an environment where all externalities must be
positive. If two agents form a link, then they weakly decrease the distance all
other agents are apart and weakly increase the number of other agents they are
connected to. There are at least two important considerations that a model with
only positive externalities does not capture. First, in most networks we expect
there to be congestion issues. This is especially true if we are discussing a computer
network, but congestion also occurs in most economic networks. For example, JW’s
co-authors model is meant to capture that as the number of co-authors you have
increases, you have less time to devote to each one. We would expect the same thing
to occur in a network of friends, a communications network, a network of business
associates, etc. A star should be especially prone to congestion issues as there is a
clear bottleneck, the central node.
A second consideration is that most economic networks involve competition
among agents. In a network of buyers and sellers, an additional link literally means
increased competition. In a network of gamblers exchanging private information
about a horse race, the value of the information decreases with each additional
person who learns the inside tip. When an MBA student talks about networking,
they are referring to contacts to help them get a job. One can imagine it would be
very helpful to have a friend forward your resume to her boss. However, the value
of this is substantially decreased if she also forwards the resume of twenty other
friends.
4
4
Calvo-Armengol and Jackson (2004) captures this e?ect. In their model, when an
40
A natural way of modeling a network where an agent’s payo? is adversely
a?ected by competition or congestion is through a degree based utility model. I will
de?ne a utility function to be degree-based if there exists a ? such that
u
v
(G) =
w?N(v)
?(d
w
)
where ? is non-increasing and d
w
is the number of direct relationships w has
5
. In
this environment, externalities can only be negative. A new connection in a network
weakly increases the degree of each of an agent’s neighbors, so if the agent is not
directly involved with the new link, her payo? must weakly decrease. This paper
will completely characterize the socially optimal and equilibrium set of networks for
degree based utility functions.
First, I will show that the regular network is socially optimal for any degree
based utility function
6
. Next, I will introduce two new equilibrium concepts which
extend the traditional notion of pairwise stability. Under pairwise stability, an agent
is able to biilaterally add an edge or unilaterally drop an edge. Strong pairwise
stability, a natural extension of pairwise stability, allows an agent to both drop an
edge and add another concurrently. Under strong pairwise stability with transfers,
an agent is also able to transfer utility to her immediate neighbors. I will be able to
completely characterize the set of strongly-pairwise-stable networks for any degree
based utility function. Finally, with only a mild assumption on the consistency of
employed agent hears about a job, she randomly picks an unemployed acquaintance to
pass the job to. In this model, edges have negative externalities as an acquaintance
adding a connection decreases the chances you will be randomly chosen in the event you
are unemployed.
5
The notation w ? N(v) will be explained more fully in the section on Graph Theory
terminology, but it means any vertex w that has a direct edge with v.
6
A network is regular if all agents have the same number of connections
41
externalities, I will be able to show that a network is strongly pairwise stable with
transfers if and only if it is the socially optimal regular graph.
These results for degree based utility functions are not only interesting in their
own right but especially as a contrast to the positive externalities environment. If
we use as our metric maximum degree minus minimum degree, then the star and a
regular graph are as di?erent as two graphs can possibly be. It is interesting that two
very natural classes of utility functions can lead to such strikingly di?erent optimal
and equilibrium networks. As such, this should be taken as a note of caution for
researchers using a reduced form utility function to model a social network. The
choice of utility function and more broadly the treatment of externalities in these
networks are of critical importance to the predictions of the model.
As one of the ?rst papers in networks and speci?cally one that characterized
the solution space of two reduced form models, JW has greatly in?uenced the models
in subsequent papers. The solution space for the connections model, the star, is quite
interesting whereas the solution space for the co-authors model is trivial. Possibly for
this reason, most subsequent papers are based roughly on the connections model. As
a result they are positive externalities models. This is unfortunate as most situations
of interest to economists involve competition and thus exhibit negative externalities.
The ?nal contribution of this paper is to propose and solve a negative externalities
model that both has a more interesting solution space than the co-authors model
and is a more natural counterpoint to the connections model.
This paper is closely related to Bloch and Jackson (2007). The two papers,
in conjunction, are able to completely characterize the two most intuitive, general
42
classes of network models. The focus of Bloch and Jackson is on network forma-
tion. They introduce several games in which players make decisions about both
link formation and transfers to other agents in the network. Their paper highlights
the importance of externalities and demonstrates a reasonable way in which agents
might overcome them. The equilibrium concept I introduce, strong pairwise sta-
bility with transfers, is a core concept which complements the network formation
games introduced in their paper.
This paper is most closely related to Jackson and Wolinsky (1996). They
present and solve two reduced form models. Their ?rst model, the connections
model, is a distance based model, while their second, the co-authors model, is es-
sentially a degree based model. Therefore, the results presented here in conjunction
with the results in Bloch and Jackson (2007) can be viewed as a generalization of
JW.
There are at least two other papers, Currarini (2002) and Goyal and Joshi
(2002), that look at externalities in networks; however, both papers take a substan-
tially di?erent modeling approach than this paper. Currarini (2002) focuses on the
partition of vertices into connected components. In Currarini’s model the value of
a network depends only on this partition. Externalities are de?ned by whether the
value of a network increases or decreases when the partition becomes ?ner. The
network matters in that it determines the partition, but in Currarini’s framework
the role of network architecture is minimized. Goyal and Joshi’s (2002) approach
is more similar to this paper but still substantially di?erent. They examine two
interesting models where agents have varying degrees in equilibrium. The focus of
43
their paper is how di?ering degrees a?ect agent payo?. Externalities, in the form of
whether or not agents are strategic substitutes or compliments, end up being crucial
to solving their models, but their two games are not an attempt to actually model
externalities. In fact, strategic complementarities are de?ned speci?cally in terms of
the particular payo? function they use and their concept is not readily generalizable.
In contrast, this paper’s primary aim is to model network externalities in as general
a way as possible without diminishing the role of network architecture.
The remainder of this article is organized as follows. Section 2 provides a brief
overview of graph theory terminology. Section 3 introduces degree based utility
functions and completely characterizes the socially optimal and equilibrium networks
for any degree based utility function. Section 4 introduces and solves a speci?c
reduced form utility function. Section 5 concludes, and the Appendix provides
complete proofs.
3.2 Graph Theory Terminology
This paper uses no theoretical results from graph theory, but I will borrow
from its terminology to facilitate discussion. I will represent a network as a graph
where vertices represent agents and an edge represents a relationship between the
two agents. All edges are undirected.
The following are some de?nitions with corresponding notation:
• E(G) is the set of edges in a graph G. e
u,v
? E(G) is an edge between vertices
u and v.
44
• V(G) is the set of vertices in G.
• u and v are adjacent if e
u,v
? E(G). u ?v indicates u and v are adjacent.
• The neighborhood of v is the set of vertices adjacent to v. Symbolically, N(v) =
¦u ? V (G)[e
u,v
? E(G)¦.
• The degree of v is the number of vertices v is adjacent to. Symbolically,
d
v
= [N(v)[.
• G is complete if all vertices are adjacent.
• A star is a graph with one center vertex, in which all remaining vertices are
adjacent only to the center.
Figure 3.1: A complete graph and a star.
• A path between u and v is a set of edges
e
v
1
,v
2
, e
v
2
,v
3
, e
v
3
,v
4
, . . . , e
v
n?1
,vn
such
that v
1
= u and v
n
= v.
• u and v are connected if there exists a path between them. The components of a
graph are its maximal connected subgraphs. Note that the connection relation
45
is transitive, symmetric, and re?exive, so it is an equivalence relation. The
equivalence classes of the connection relation are the connected components.
This paper assumes the number of vertices are ?xed. Therefore, a graph is
completely characterized by its set of edges. As a result, I will slightly abuse notation
and use G and E(G) interchangeably. For example, G?e
u,v
represents the new graph
created by adding an edge between u and v.
3.3 Degree Based Utility Functions
In this section I will introduce a class of models which is a natural counterpoint
to the more widely studied distance based models. A utility function is degree-based
if there exists a ? such that
u
v
(G) =
w?N(v)
?(d
w
)
. A particularly desirable feature of degree based utility models is that they are
interesting even when links are costless to form. For any positive externalities model,
if links are costless then the complete network must be socially optimal as adding
links can not harm the agents but may help them. As a result, positive externalities
models are only interesting to study when links are costly. However, there are
situations where incurring a cost for a link does not have a clear interpretation. For
example, it is not clear how an agent incurs a cost that is completely separate from
the bene?t of having a friendship. Time spent maintaining a business relationship or
even expenses incurred “wining and dining” a potential partner might reasonably be
considered costs, but it is di?cult to apply this to a model of personal relationships.
46
After all, having someone to spend time with and someone to go to costly activities
such as dinners or baseball games are some of the bene?ts, not costs, of having a
friend. Therefore, it is particularly attractive that we do not need separate costs for
links in order to make a degree-based utility function nontrivial.
The star does not perform as well with a rival utility function. The perimeter
vertices only get utility from their immediate neighbor, the center of the star. How-
ever, the center is connected to so many vertices (the maximum possible) that its
value has decreased. Moreover, we do not expect the star to be an equilibrium of a
network game as two perimeter vertices would do better by dropping their connec-
tion to the center agent and forming a link to each other. In this environment, a
more symmetric graph does better socially and is more likely to be pairwise stable.
A regular graph, where all agents have the same number of connections, is the nat-
ural place to look. Unfortunately, regular graphs do not always exist.
7
However, a
regular graph always exists when there is an even number of vertices. I will de?ne
a new class of graphs which exist regardless of the parity of the number of agents.
De?nition 6. Let d = max ¦d(v) : v ? V (G)¦ and d = min ¦d(v) : v ? V (G)¦.
Then:
1. A graph is nearly-regular if (d ?d) ? 1.
2. A graph is nearly-n-regular if (n ?1) ? d ? d ? n.
7
For example, if we have an odd number of vertices, we can not have a (2a +1)-regular
graph. Since every edge contributes two to the sum of all vertex degrees, the total sum of
degrees must be even. An odd-regular graph with an odd number of vertices would have
an odd total degree sum which is not possible.
47
The next proposition completely characterizes the set of socially optimal net-
works when there is an even number of vertices. I will be able to simplify this
characterization once I impose a mild assumption on the consistency of externali-
ties.
Proposition 5. Suppose there is an even number of agents. A network G is socially
optimal if and only if for every vertex v, d
v
? arg max x?(x). In particular, for any
n ? arg max x?(x), all n-regular graphs are socially optimal.
Proof. Each agent receives a payo? from her neighbors and contributes utility to
her neighbors. As an accounting identity, the sum of what every agent receives must
equal the sum of what every agent contributes. In particular
U(G) =
N
i=1
u
i
(G) =
N
i=1
v
j
?N(v
i
)
?(d
v
j
) =
N
i=1
d
v
i
?(d
v
i
) (3.1)
Let n ? arg max x?(x). Since we have an even number of vertices, an n-regular
graph exists
8
. Pick any n-regular graph H. By Equation 3.1, H must be socially
optimal. Moreover, if J is a network with a vertex v such that d
v
,? arg max x?(x),
then U(J) < U(H).
8
To see this, label the vertices 0 through [V (G)[ ?1. If n is even, then connect vertex
i to vertices i ±jmod([V (G)[), for 1 ? j ?
n
2
. If n is odd, then connect vertex i to vertex
i +
|V (G)|
2
mod([V (G)[) and to vertices i ±jmod([V (G)[), for 1 ? j ?
n?1
2
48
3.3.1 Pairwise Stability
Pairwise stability is the standard equilibrium concept in Network Theory. In-
tuitively, it says no agent wishes to unilaterally drop one of her connections, and no
two agents wish to bilaterally add a connection. More formally:
De?nition 7. A graph G is pairwise stable if:
1. If e
i,v
? E(G), then u
i
(G) > u
i
(G?e
i,v
) and u
j
(G) > u
j
(G?e
i,v
).
2. If e
i,v
,? E(G), then either u
i
(G) > u
i
(G +e
i,v
) or u
j
(G) > u
j
(G +e
i,v
).
So far in this section we have assumed that links are costless. However, we
must add link costs in order to make pairwise stability interesting. Otherwise, as
long as ? is strictly positive, the only pairwise stable graph is the complete graph.
For the remainder of this subsection, I will assume u
v
(G) =
w?N(v)
?(d
w
) ?c d
v
.
Moreover, to avoid any nuisances, I will assume c ,= ?
for any n ? N. This
assumption is without loss of generality since one can perturb c by an arbitrarily
small .
This next structure appears several times so I will explicitly de?ne it.
De?nition 8. G is a maximal nearly-n-regular graph if it is nearly n regular
and there does not exist a nearly-n-regular graph G
such that E(G) ? E(G
).
Proposition 6. Let n = max ¦x ? N[?(x) > c¦. If utility is rival, then all maximal
nearly-n-regular graphs are pairwise stable.
Proof. Let G be any maximal nearly-n-regular graph. Look at any vertices u and v
such that e
u,v
/ ? E(G). The maximality of G implies at least one u or v must have
49
Figure 3.2: An undesirable pairwise stable graph
u
u u
u
uu
d
d
d
d
d
d
d
degree n. Without loss of generality, assume d
v
= n. Then u
i
(G + e
u,v
) ? u
i
(G) =
?(n + 1) ? c < 0 by the maximality of n. Similarly, look at any vertices u and v
such that e
u,v
? E(G). u
i
(G) ?u
i
(G?e
u,v
) ? ? ?c ? 0. Therefore G is pairwise
stable.
Pairwise stability is a fairly weak concept. Pairwise stability only allows a
vertex to unilaterally drop a connection or to bilaterally add a connection, but not
both. For example, if max ¦x ? N[?(x) ? c¦ = 3, then the graph in Figure 3.2 is
pairwise stable since u will be unwilling to add an edge with any vertex that already
has degree 3. However, this is unsatisfying as any of the vertices in the 4-clique
would be happy to exchange one of their edges for an edge with u. Similarly, as long
as the vertex is willing to drop one of her edges, u would be happy to form an edge
with any vertex in the 4-clique. This leads to a new solution concept.
De?nition 9. A graph G is Strongly Pairwise Stable if
1. G is pairwise stable
2. There does not exist a u, v, w ? V (g) such that u
u
(G
) > u
u
(G) and u
v
(G
) >
u
v
(G) where G
= G +e
u,v
?e
v,w
.
50
With this stronger solution concept, we are able to completely characterize
the set of strongly pairwise stable graphs.
Proposition 7. Let n = max ¦x ? N[?(x) > c¦ and suppose ? is strictly decreasing.
Then G is strongly pairwise stable if and only if G is a maximal nearly-n-regular
graph.
Proof. It is straightforward to verify that a maximal nearly-n-regular graph is strongly
pairwise stable. To prove the other direction, look at any strongly pairwise stable
graph G. First note that max ¦d
v
[v ? V (G)¦ = n since otherwise G would not be
pairwise stable.
9
Suppose for contradiction that G is not nearly-regular. Then
there exists a u and v such that d
v
? d
u
? 2. Let w ? N(v) ¸ N(u) ,= ? and let
G
= G +¦e
u,w
¦ ?¦e
v,w
¦. Note that u
w
(G
) > u
w
(G) since d
u
+ 1 < d
v
. Moreover,
u
u
(G
) > u
u
(G) since d
w
? n and ? > c. Therefore G is not strongly pairwise
stable, a contradiction. Since G has max degree n and is nearly-regular, it must be
nearly-n-regular. If G is not maximal, then there are two non-adjacent vertices of
degree n-1 and therefore G is not pairwise stable.
3.3.2 Equilibrium with Transfers
In this section I will introduce a new core concept which generalizes pairwise
stability to allow agents to make transfers. This complements the games introduced
in Block and Jackson (2007). They de?ne several new network games which extend
9
If the maximum degree is greater then n, some vertex would want to drop an edge.
If the max degree is less then n, any unconnected vertices would be better o? adding an
edge.
51
the traditional network games to allow players to make ?nancial transfers. In their
paper they make a distinction between who an agent is able to make a transfer to and
on what an agent is able to condition this transfer payment. In the direct transfer
game, an agent can only make a transfer for a link she is directly involved with. In
the indirect transfer games she can only make demands on her own relationships,
but she is free to subsidize any relationship. In their standard game, a transfer is
conditional only on a link forming, but in their game with contingent transfers, an
agent can condition a payment on the entire network structure.
Transfers are a natural concept in a social network. We often see situations
where maintaining the relationship is more important to one of the agents than the
other. In the business world, one person may be in a position of greater power
or may simply have more connections than the other. In the academic world, the
marginal value of publishing an article should decrease with the total number of
publications an author has. Therefore, even if two co-authors are equally talented,
the relationship should be relatively more valuable to the person with fewer publica-
tions. In such a situation, it is natural for a transfer to occur. The person to whom
the relationship is more valuable will have the incentive to put forth more e?ort into
the project or else might agree to do the less desirable aspects of the work.
I propose a new core concept which generalizes pairwise stability to allow
agents to make transfers to the people they have a relationship with. I only allow
direct transfers as I ?nd indirect transfers much less natural. A transfer between
two agents with a relationship can be non-pecuniary; however, there is less ?exibility
when the transfer is between two agents who are not linked. It is hard to interpret
52
an indirect transfer as anything other that a monetary payment. In some situations
this may be perfectly natural, but especially with social networks, direct monetary
transfers occur infrequently. An academic can do many things to either ease the
burden on her coauthor or make the relationship more valuable, but it would be
strange for her to pay an academic to not collaborate with any of her coauthors.
Despite this restriction, we will still be able to reach some powerful conclusions.
More formally, the game consists of a graph G and a matrix of transfers T.
In the transfer matrix, t
ij
represents the transfer from agent i to agent j. An agent
can only make a transfer to someone she has a direct relationship with. Therefore,
t
ij
> 0 only if e
ij
? G. To avoid ambiguity, I will require that t
ij
= ?t
ji
as we care
only about the net transfer.
Therefore, given a network G and transfers T, agent i receives a payo? of
?
i
(G, T) =
v
j
?N(v
i
)
[?(d
v
j
) +t
ji
] (3.2)
Individually, an agent should be able to drop any of her edges and change
the transfers she o?ers. Two agents should also be able to form a link if they so
desire. Anytime an agent changes her edges or transfers, she alters the payo? of her
neighbors and, therefore, potentially jeopardizes these relationships. However, if two
agents are able to move bilaterally to establish a mutually bene?cial relationship and
to adjust their transfers so that all of their neighbors are better o?, then they do
not jeopardize these relationships and surely the network is in disequilibrium.
De?nition 10. Given a network G with transfers T, agent v
i
blocks < G, T > if
53
there exists an agent v
j
10
, subsets A ? N(v
i
), B ? N(v
j
), and transfers T
on the
set ¦v
i
, v
j
, N(v
i
) ¸ A, N(v
j
) ¸ B¦ such that:
?
x
(G
, T +T
) > ?
x
(G, T)
for every x ? ¦v
i
, v
j
, N(v
i
) ¸ A, N(v
j
) ¸ B¦ where G
= G ? e
i,j
¸ ¦e
i,k
: k ? A¦ ¸
¦e
j,k
: k ? B¦.
This de?nition is purely a generalization of strong pairwise stability. An agent
can drop any edge, add an edge (as long as the other agent wishes to as well), or
do both simultaneously. If the agent is also able to compensate all the agents she
remains in a relationship with so that they are made better o? by the change, then
surely we are in disequilibrium.
De?nition 11. A network G is strongly pairwise stable with transfers if there
exists transfers T such that no agent blocks < G, T >. In such a case, we say the
transfers T support G.
When it is clear from context that it is a network with transfers, I will just
say strongly pairwise stable instead of strongly pairwise stable with transfers. With
a mild regularity assumption on externalities, I will prove that the only network
that is strongly pairwise stable with transfers is the socially optimal, nearly-regular
network.
Whenever an edge is added to an network, there is a social trade o?. There is a
direct bene?t to the two agents forming the relationship but at a cost of a decreased
10
We allow v
j
= ? in which case we interpret G? e
i,j
= G.
54
payo? to all the agents they already share an edge with. This trade-o? is captured
by the function:
to(x) = ?(x + 1) ?x(?(x) ??(x + 1)), 1 ? x ? [V (G)[ ?2
When an agent with degree x forms a new edge, she is contributing ?(x + 1) to
the new neighbor but at a cost of ?(x) ? ?(x + 1) to the x many agents she was
previously connected to. This motivates a regularity condition on externalities.
De?nition 12. The externalities in a network are consistent if to(x) is decreasing.
De?nition 13. Externalities are weakly consistent if any of the following condi-
tions hold:
1. to(x) > 0.
2. to(x) < 0.
3. There exists a integer M such that to(x) ? 0 for every x ? M and to(x) < 0
for every x > M.
For each respective case, we de?ne the threshold of to(x) to be:
1. [V (G)[ ?1
2. 1
3. M
to(x) is decreasing if ?(x) ??(x + 1) is increasing. Therefore, if ? is concave,
then externalities are consistent. However, this condition is much weaker than
concavity. Of course, if externalities are consistent then they are weakly consistent.
55
I will assume that if to(x) is weakly consistent with threshold M with 1 < M <
[V (G)[ ?1, then to(M) = 0. This does not change the results in any signi?cant way,
but it does make the proofs cleaner. Moreover, if to(M) ,= 0, then we can replace
?(x) by ?
(x) where ?
(x) = ?(x) ?to(M). Now:
to
?
= ?
(x + 1) ?x(?
(x) ??
(x + 1))
= ?(x + 1) ?to(M) ?x(?(x) ?to(M) ??(x + 1) +to(M))
= to
?
(x) ?to(M)
and therefore to
?
(M) = 0.
With this mild assumption on externalities, we can completely classify the set
of socially optimal networks. In a surprising result, once agents are able to make
transfers to their neighbors, these networks will also be the only strongly pairwise
stable networks.
Proposition 8. Suppose externalities are weakly consistent.
1. When 1 < M < [V (G)[ ? 1, then G is socially optimal if and only if G is
nearly-(M+1)-regular.
2. When M = [V (G)[?1, then the complete network is the unique socially optimal
network.
3. When M = 1, then the unique socially optimal network is the trivial network
11
.
11
The trivial network consists of
|V (G)|
2
many pairs if [V (G)[ is even and
|V (G)?3|
2
many
pairs plus the three remaining vertices connected as a path if [V (G)[ is odd. See Figure
3.3 on page 66 for an example.
56
I will prove Proposition 8.1 here. The remaining cases, which are more tech-
nical, are proved in the Appendix.
Proof. We know from the previous section that G is optimal if and only if every
vertex has degree from the argmaxx?(x). Note that
to(x) = ?(x + 1) ?x(?(x) ??(x + 1))
= (x + 1)?(x + 1) ?x?(x)
and therefore
2?i?x
to(i ?1) =
2?i?x
[i?(i) ?(i ?1)?(i ?1)]
= x?(x) ??(1)
since
2?i?x
[i?(i) ?(i ?1)?(i ?1)] is a telescoping series. In particular,
x?(x) = [
2?i?x
to(i ?1)] +?(1) (3.3)
Since, to(x) ? 0 for every x ? M and to(x) < 0 for every x > M, x?(x) is maximized
at x = M + 1. Note that
(M + 1)?(M + 1) = [
2?i?(M+1)
to(i ?1)] +?(1)
= to(M) + [
2?i?(M)
to(i ?1)] +?(1)
= 0 + [
2?i?(M)
to(i ?1)] +?(1)
= M?(M)
Where the second to last equality follows from our assumption that to(M) = 0.
Since to(x) ,= 0 for every x ,= M, argmax(to(x)) = ¦M, M + 1¦. As mentioned
57
previously, a nearly regular graph always exists. Therefore, a network is optimal if
and only if it is nearly-(M+1)-regular.
I will now prove the main theorem of this section.
Proposition 9. Suppose externalities are weakly consistent.
1. When 1 < M < [V (G)[ ?1, G is strongly pairwise stable with transfers if an
only if G is nearly-(M+1)-regular.
2. When M = [V (G)[ ? 1, the complete network is the unique network that is
strongly pairwise stable with transfers.
3. When M = 1, the unique network that is strongly pairwise stable with transfers
is the trivial network.
This proposition is proved with a sequence of lemmas. Complete proofs are
given in the Appendix, but I will list the lemmas and give the intuition to the proof
here.
Lemma 5. Suppose 1 < M < [V (g)[ ? 1 and let G be strongly pairwise stable. If
there exists a vertex u with degree less than M, then u is adjacent to every vertex
with degree less than or equal to M.
Intuition. If there are two non-adjacent agents with degree less than the thresh-
old, then adding an edge is socially bene?cial as the trade-o? for both agents is posi-
tive. Moreover, all the social gains are realized by the two agents. Since it is socially
58
bene?cial, they bene?t enough to be able to compensate all of their neighbors and
still improve their payo?.
Lemma 6. Suppose 1 < M < [V (g)[ ? 1 and let G be strongly pairwise stable. If
there exists a vertex u with degree greater than M +1, then u is not adjacent to any
vertex with degree greater than or equal to M + 1.
Intuition. It is socially bene?cial for the two agents with degree greater than
the threshold to cut their relationship. Their neighbors, who receive all the bene?t
from the two agents cutting an edge, are willing and able to increase their transfers
by enough to make it in u or v’s best interest to cut the edge. We have to be a little
more careful than in Lemma 5 since there may be transfers between the two agents
which would a?ect their willingness to drop the edge.
Lemma 7. Suppose T supports a network G. Then for every two agents i and j
such that e
i,v
? G,
t
ij
? ?(d
j
) ?(d
i
?1)(?(d
i
?1) ??(d
i
))
Proof. v
i
has d
i
?1 many neighbors who would be willing to pay up to ?(d
i
?1)??(d
i
)
for i to sever her relationship with j. i receives a bene?t of ?(d
j
) ? t
i
, j from her
relationship with j, so if ?(d
j
) ?t
ij
< (d
i
?1)(?(d
i
?1) ??(d
i
)) then i and all her
remaining neighbors do strictly better if i drops her relationship with j and accepts
a transfer of ?(d
i
?1) ??(d
i
) ? from each of her remaining neighbors.
Lemma 8. Suppose 1 < M < [V (g)[ ? 1 and let G be strongly pairwise stable. If
there exists a vertex u with d
u
> M + 1, then all of u’s neighbors are adjacent.
59
Intuition. If there is an agent u such that d
u
> M + 1, v, w ? N(u), but
e
vw
,? G, then v and w are better o? dropping their edges with u and creating
an edge between themselves. They do not need to compensate their neighbors for
such a move as their degree has not changed. We know from Lemma 6 that d
v
and
d
w
are both less than M + 1, so, both v and w are made better o? as they each
have degree less than u. The only thing we have to be careful about is that u may
be subsidizing her relationship with either or both of the agents, and when they
sever the relationship with u they forgo the subsidy. Lemma 7 sets a bound on the
transfer from u to v or w that ensures it will always be in v and w’s best interest to
forgo the transfer and establish a relationship with each other.
Lemma 9. Suppose 1 < M < [V (g)[ ?1 and let G be strongly pairwise stable. No
vertex in G has degree greater than M + 1.
Intuition. This is a pigeonhole argument. Suppose for contradiction there is a
vertex u with d
u
> M +1. By Lemma 6, every neighbor of u must have degree less
than or equal to M. By Lemma 8, all neighbors of u must be adjacent. However,
there are at least M + 1 neighbors of u. All are adjacent to the other neighbors of
u (there are at least M other neighbors of u) plus u itself. Therefore, all neighbors
of u must have degree at least M + 1, a contradiction.
Lemma 10. Suppose 1 < M < [V (g)[ ?1 and let G be socially optimal. No vertex
in G has degree less than M.
Intuition. If there exists a vertex u with d
u
< M, we know from Lemma 5
that u must be adjacent to all vertices with degree less than or equal to M. We can
60
establish that there must be two vertices, v and w that are adjacent to each other,
but neither of which are adjacent to u. Either of these agents would be better o?
dropping the edge with the other and instead establishing an edge with u. Moreover,
this will be socially bene?cial as both v and w must have degree M +1 and socially
we are indi?erent whether or not they are adjacent. However, since d
u
< M, we
strictly prefer that u create a new relationship. Since this switch is socially bene?cial
and all the gains are realized by u and the vertex that switches, they will be able to
compensate u’s neighbors for their decreased payo?. Again, we have to be careful
about transfers between v and w, but only one can be receiving a positive transfer
from the other.
Lemma 11. Suppose 1 < M < [V (g)[ ?1. If G is nearly-(M+1)-regular, then G is
strongly pairwise stable with transfers.
Proof. Let G be any nearly-(M+1)-regular graph. De?ne a set of transfers T by:
t
uv
=
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0 d
u
= d
v
?(M) ??(M + 1) d
u
= (M + 1), d
v
= M
?(M + 1) ??(M) d
u
= M, d
v
= M + 1
Every agent with degree M receives a total payo? of M?(M) and every agent with
degree M + 1 receives a payo? of (M + 1)?(M + 1). Since to(M) = 0, M?(M) =
(M + 1)?(M + 1).
A nearly-(M+1)-regular graph is optimal, so adding an edge cannot increase
social payo?. Since all the bene?ts are captured by the two agents adding an edge
and all costs are incurred by their neighbors, it is not possible for the two agents
61
adding the edge to make all their neighbors better o?. Similarly, an agent u has
no wish to delete one of her edges. u’s remaining neighbors receive all the bene?t,
while u incurs all the costs. Since the costs are greater than or equal to the bene?ts
(the original graph was socially optimal), u’s remaining neighbors will not be able
to compensate u so that all are better o?. Finally, two vertices u and v can not do
better by each dropping an edge and creating an edge with each other. The new
relationship is worth at most ?(M) which is exactly what they received from their
previous relationship.
Lemma 9 and Lemma 10 establishes the nearly-(M+1)-regularity is necessary
for strong pairwise stability with transfers. Lemma 11 establishes that being nearly-
(M+1)-regular is su?cient as well. This is a surprising and powerful result. In a
network of relationships, an agent should be able to sever any ties it chooses and
establish new ties when it is mutually desirable. Moreover, there should always
be informal ways an agent can exert e?ort that is costly for herself but makes the
relationship more bene?cial for a partner. My result establishes that if this is case,
then the only network which will be an equilibrium is the socially optimal network.
3.4 A Reduced Form Utility Model
A particular degree based utility function of interest is:
u
i
(G) = w
i
+
i?j
?
dv
j
w
i,j
?
i?j
c
i,j
, where 0 ? ? ? 1. (3.4)
62
Recall JW’s Connections Model is:
u
i
(G) = w
i
+
j=i
?
t
i,j
w
i,j
?
i?j
c
i,j
where t
i,j
is the length of the shortest path between v
i
and v
j
.
As mentioned before, the Connections Model has only positive externalities.
The co-authors model is the negative externalities model JW examine, but the
utility function presented in Equation 3.4 is a more natural negative externalities
counterpoint to the connections model. A vertex only gets utility from its neighbors,
and this utility is a decreasing function of each neighbor’s degree. This also ?ts
JW’s motivation for the co-authors model. The bene?t to working with a colleague
is decreasing in the number of co-authors she has as she will have less time to devote
to your project.
With our results from Section 3, we can quickly solve for the symmetric version
of Equation 3.4. Let
u
i
(G) =
i?j
?
dv
j
(3.5)
where 0 < ? < 1. Further, suppose ? =
?
?+1
for some integer ?.
By assumption:
to(x) = (x + 1)?
x+1
?x?
x
= ?
x
((x + 1)? ?x)
= ?
x
(x(? ?1) + 1)
which is a decreasing function of x. Moreover
to(?) = ?
?
((? + 1)? ??)
63
= ?
?
((? + 1)
?
? + 1
??)
= ?
?
((? ??)
= 0
Therefore all the assumptions of Proposition 3 on page 58 are met.
Proposition 10. Suppose u
i
(G) =
i?j
?
dv
j
. Then
1. G is socially optimal if and only if G is nearly-(? + 1)-regular.
2. G is strongly pairwise stable with transfers if and only if G is nearly-(? + 1)-
regular.
3.5 Conclusion
Distance based and degree based models are the two most intuitive models of
an agent’s payo? from a network. While much attention has been paid to distance
based models, very little has been paid to degree based models. This paper com-
pletely characterizes the set of optimal and stable networks for this natural class
of utility functions. The predicted networks are interesting in their own right but
especially so when taken in contrast to the optimal networks for distance based mod-
els. It is striking that two intuitive models can lead to such dramatically di?erent
predictions. In particular, this paper, taken in conjunction with the results from
Bloch and Jackson (2007), provides a generalization and simpli?cation of results in
the classic networks paper by Jackson and Wolinsky (1996).
64
3.6 Appendix - Proofs
The trivial network consists of
|V (G)|
2
many pairs if [V (G)[ is even and
|V (G)?3|
2
many pairs plus the three remaining vertices connected as a path if [V (G)[ is odd.
Proposition 8. Suppose externalities are weakly consistent.
1. When 1 < M < [V (G)[ ? 1, then G is socially optimal if an only if G is
nearly-(M+1)-regular.
2. When M = [V (G)[ ? 1, then the complete network is the unique socially
optimal network.
3. When M = 1, then the unique socially optimal network is the trivial network.
Proof. Proposition 8.2 Let G be any graph that contains two non-adjacent vertices
u and v, and suppose the threshold is [V (G)[ ?1. By the de?nition of the threshold,
to(x) > 0. Therefore,
U(G? e
u,v
) ?U(G) = (d
u
+ 1)?(d
u
+ 1) ?d
u
?(d
u
) + (d
v
+ 1)?(d
v
+ 1) ?d
v
?(d
v
)
= to(d
u
) +to(d
v
)
> 0
and G can not be optimal. Therefore, the only optimal network is one where all
vertices are adjacent.
Proposition 8.3 We know from Equation 3.1 on page 48 that
U(G) =
N
i=1
d
v
i
?(d
v
i
)
65
Figure 3.3: Trivial graph for an even and odd number of vertices.
1 2 3 4
5 6 7 8
1 2 3 4
5 6 7 8
9
and from Equation 3.3 on page 57 that
x?(x) = [
2?i?x
to(i ?1)] +?(1)
Since to(x) < 0 for every x > 0, x?(x) is strictly decreasing for x ? 1.
Therefore, if a 1-regular graph exists, it must be optimal. A 1-regular graph exists
when there is an even number of vertices (the trivial graph), but does not when the
number of vertices is odd. Since 2?(2) > 0, the trivial graph must be optimal when
there is an odd number of agents.
Lemma 5. Suppose 1 < M < [V (g)[?1 and let G be strongly pairwise stable.
If there exists a vertex u with degree less than M, then u is adjacent to every vertex
with degree less than or equal to M.
Proof. Suppose for contradiction that G is supported by transfers T and has two
non-adjacent vertices u and v with d
u
< M and d
v
? M. Let
t
vx
=
?
?
?
?
?
?
?
?(d
v
) ??(d
v
+ 1) + x ? N(v)
?(d
u
+ 1) ??(d
v
+ 1) x = u
t
ux
=
?
?
?
?
?
?
?
?(d
u
) ??(d
u
+ 1) + x ? N(u)
?(d
v
+ 1) ??(d
u
+ 1) x = v
66
Then
??
u
(G? e
i,j
, T +T
) = ?(d
v
+ 1) +t
vu
?
w?N
G
(u)
t
uw
= ?(d
v
+ 1) + [?(d
u
+ 1) ??(d
v
+ 1)] +d
u
(?(d
u
+ 1) ??(d
u
) ?)
= ?(d
u
+ 1) ?d
u
(?(d
u
) ??(d
u
+ 1)) ?d
u
? )
= to(d
u
) ?d
u
?
> 0
for su?ciently small.
For x ? N
G
(u)
??
x
(G? e
i,j
, T +T
) = ?(d
u
+ 1) ??(d
u
) +t
ux
= ?(d
u
+ 1) ??(d
u
) +?(d
u
) ??(d
u
+ 1) +
=
> 0
Similarly, ?
v
(G?e
i,j
, T +T
)??
v
(G, T) > 0 and ?
x
(G?e
i,j
, T +T
)??
u
(G, T) >
0 for every x ? N
G
(v). Therefore, u and v block < G, T >, contradicting the
assumption that T supports G.
Lemma 6. Suppose 1 < M < [V (g)[?1 and let G be strongly pairwise stable.
If there exists a vertex u with degree greater than M + 1, then u is not adjacent to
any vertex with degree greater than or equal to M + 1.
Proof. Suppose for contradiction that G is supported by transfers T and has two
adjacent vertices u and v with d
u
> M + 1 and d
v
? M + 1. Let r
xu
= ?(d
u
?
67
1) ? ?(d
u
) ? for every x ? N(v) ¸ u. In other words, each neighbor of u gives u
?(d
u
?1)??(d
u
)?. Similarly, let s
vx
= ?(d
v
)??(d
v
?1)+ for every x ? N(u)¸v.
Then if u drops its edge with v in order to receive transfers R, it loses the
bene?t from v, ?(d
v
), no longer makes the transfer t
u,v
, and gains the transfers R
from each of its remaining neighbors. Speci?cally,
??
u
(G¸ e
uv
, T +R) = ??(d
v
) +t
uv
+ (d
u
?1)(?(d
u
?1) ??(d
u
) ?)
Similarly,
??
v
(G¸ e
uv
, T +S) = ??(d
u
) +t
vu
+ (d
v
?1)(?(d
v
?1) ??(d
v
) ?)
Adding these two equations yields
??
u
(G¸ e
uv
, T +R) + ??
v
(G¸ e
uv
, T +S) =
?to(d
v
?1) ?to(d
u
?1) +t
uv
+t
vu
?(d
u
+d
v
?2) =
?to(d
v
?1) ?to(d
u
?1) ?(d
u
+d
v
?2) > 0
for su?ciently small . The ?rst equality comes from rearranging terms. The second
equality follows since t
uv
= ?t
vu
by de?nition. The ?nal inequality follows since
d
u
? 1 > M and d
v
? 1 ? M, so by the de?nition of the threshold, ?(d
u
? 1) < 0
and ?(d
v
?1) ? 0. But, since ??
u
(G¸ e
uv
, T +R) +??
v
(G¸ e
uv
, T +S) > 0, either
??
u
(G¸ e
uv
, T +R) > 0 or ??
v
(G¸ e
uv
, T +S) > 0.
By construction, ?
x
(G¸ e
uv
, T +R) ??
x
(G, T) > 0 for every x ? N(u) ¸ v and
?
x
(G¸ e
uv
, T +S) ??
x
(G, T) > 0 for every x ? N(v) ¸ u. Since
[?
u
(G¸ e
uv
, T +R) ??
u
(G, T)] + [?
v
(G¸ e
uv
, T +S) ??
v
(G, T)] > 0
68
at least one of [?
u
(G¸e
uv
, T +R)??
u
(G, T) > 0 or ?
v
(G¸e
uv
, T +S)??
v
(G, T) > 0.
Whichever one is greater than zero blocks G, a contradiction.
In equilibrium, there is a limit to how much an agent is willing to transfer
another agent.
Lemma 7. Suppose T supports a network G. Then for every two agents i
and j such that e
i,v
? G,
t
ij
? ?(d
j
) ?(d
i
?1)(?(d
i
?1) ??(d
i
))
.
Proof. v
i
has d
i
?1 many neighbors who would be willing to pay up to ?(d
i
?1)??(d
i
)
for i to sever her relationship with j. i receives a bene?t of ?(d
j
) ? t
i
, j from her
relationship with j, so if ?(d
j
) ?t
ij
< (d
i
?1)(?(d
i
?1) ??(d
i
)) then i and all her
remaining neighbors do strictly better if i drops her relationship with j and accepts
a transfer of ?(d
i
?1) ??(d
i
) ? from each of her remaining neighbors.
Lemma 8. Suppose 1 < M < [V (g)[ ? 1 and let G be strongly pairwise
stable. If there exists a vertex u with d
u
> M + 1, then all of u’s neighbors are
adjacent.
Proof. Suppose not, and let u be such that d
u
> M + 1, v, w ? N(u), but e
vw
,? G.
We know from Lemma 6 that d
v
, d
w
? M. Since v and w are not adjacent, we know
from Lemma 5 that neither v nor w has degree less than M. Therefore, d
v
= d
w
= M.
From Lemma 7
t
uv
? ?(d
v
) ?(d
u
?1)(?(d
u
?1) ??(d
u
))
69
= ?(d
v
) ??(d
u
) +?(d
u
) ?(d
u
?1)(?(d
u
?1) ??(d
u
))
= ?(M) ??(d
u
) +to(d
u
?1)
Similarly, t
uw
? ?(M) ??(d
u
) +to(d
u
?1). Therefore
??
v
(G +e
vw
¸ ¦e
uv
, e
uw
¦ , T) = ?(d
w
) ??(d
u
) ?t
uv
= ?(M) ??(d
u
) ?t
uv
? ?(M) ??(d
u
) ?(?(M) ??(d
u
) +to(d
u
?1))
= ?to(d
u
?1)
> 0
where the last inequality follows from d
u
> M + 1 and therefore, to(d
u
?1) < 0.
Similarly, ??
w
(G + e
vw
¸ ¦e
uv
, e
uw
¦ , T) > 0. Note that since the degree of
v and w has not changed, all vertices in N(v) ? N(w) ¸ u are indi?erent between
< G+e
vw
¸¦e
uv
, e
uw
¦ , T > and < G, T >. Therefore agents v and w block < G, T >
contradicting the stability of G.
Lemma 9. Suppose 1 < M < [V (g)[?1 and let G be strongly pairwise stable.
No vertex in G has degree greater than M + 1.
Proof. This is a pigeonhole argument. Suppose for contradiction there is a vertex u
with d
u
> M + 1. By Lemma 6, every neighbor of u must have degree less than or
equal to M. By Lemma 8, all neighbors of u must be adjacent. However, there are
at least M + 1 neighbors of u. All are adjacent to the other neighbors of u (there
70
are at least M other neighbors of u) plus u itself. Therefore, all neighbors of u must
have degree at least M + 1, a contradiction.
Lemma 10. Suppose 1 < M < [V (g)[ ?1 and let G be socially optimal. No
vertex in G has degree less than M.
Proof. Suppose for contradiction there exists a vertex u with d
u
< M. Since M <
[V (G)[ ?1, there exists a v not adjacent to u. By Lemma 5, d
v
> M. Therefore, by
Lemma 9, d
v
= M+1. Since v has M+1 neighbors and u has less than M neighbors,
there must exist a w which is adjacent to v but not adjacent to u. Repeating the
logic above, d
w
= M +1. We will demonstrate that u, w, and all of their neighbors
can be made better o? if u adds an edge with w and w drops it’s edge with v.
From Lemma 7
t
wv
? ?(d
v
) ?(d
w
?1)(?(d
w
?1) ??(d
w
))
= ?(M + 1) ?(M)(?(M) ??(M + 1))
= to(M)
= 0
Similarly t
vw
? 0, therefore t
wv
= t
vw
= 0. Let G
= G? e
uw
¸ e
vw
. Then
??
w
(G
, T) = ?(d
u
+ 1) ??(d
v
) ?t
v
w
= ?(d
u
+ 1) ??(d
v
)
??
u
(G
, T) = ?(d
w
)
??
x
(G
, T) = ?(d
u
+ 1) ??(d
u
) for every x ? N(u)
??
x
(G
, T) = 0 for every x ? N(w)
71
Let
t
ux
=
?
?
?
?
?
?
?
?(d
u
) ??(d
u
+ 1) + x ? N(u)
?(d
v
) ??(d
u
+ 1) +? x = w
t
wx
= ? for every x ? N(w) ¸ v.
Now
??
w
(G
, T +T
) = ? ?d
w
? ?
??
u
(G
, T +T
) = ?(d
u
+ 1) ?d
u
(?(d
u
) ??(d
u
+ 1)) ?d
u
? ??
= to(d
u
) ?d
u
? ??
??
x
(G
, T +T
) = for every x ? N(u)
??
x
(G
, T +T
) = ? for every x ? N(w)
Since d
u
< M, to(d
u
) > 0, and therefore, u, w and all of their neighbors can be
made better o? in G?e
uw
¸ e
vw
. This contradicts the strong pairwise stability of G.
72
Bibliography
[1] Abdulkadiroglu, A. and Sonmez, T. (1998), “Random Serial Dictatorship and
the Core from Random Endowments in House Allocation Problems,” Econo-
metrica 66: 689-701.
[2] Bala, V. and Goyal, S. (2000), “A Non-Cooperative Model of Network Forma-
tion,” Econometrica 68: 1181-1230.
[3] Bloch, F. and Jackson, M. (2007), “The Formation of Networks with Transfers
Among Players,” Journal of Economic Theory, 133: 83-110.
[4] Calvo-Armengol, T. and Jackson, M. (2004), The E?ects of Social Networks on
Employment and Inequality, American Economic Review, 94: 426-454.
[5] Chung, K. (2000), “On the Existence of Stable Roommate Matchings,” Games
and Economic Behavior 33: 206-230.
[6] Currarini, S. (2002) Stable Organizations with Externalities, mimeo: Universita
di Venezia.
[7] Edmunds, J. (1965), “Paths, Trees, and Flowers,” Canad. J. Math. 17: 449-467.
[8] Gale, D. and Shapley, L. (1962), “College Admissions and the Stability of
Marriage,” Amer. Math. Monthly 69: 9-15.
73
[9] Granovetter, M. (1973) “The Strength of Weak Ties,” American Journal of
Sociology, 78: 1360-80.
[10] Granovetter, M. (1995) “Getting a Job: A Study of Contacts and Careers,”
2nd Ed. Chicago: University of Chicago Press.
[11] Goyal, S. and Joshi, S. (2002) Unequal Connections, mimeo: University of
London and George Washington University.
[12] Gus?eld, D. and Irving, R. (1989), “The Stable Marriage Problem: Structure
and Algorithms,” MIT Press, Boston, MA.
[13] Jackson, M.O. (2003), “A Survey of Models of Network Formation: Stability
and E?ciency,” Mimeo, Cal-Tech.
[14] Jackson, M.O. and Wolinsky, A. (1996), “A Strategic Model of Social and
Economic Networks,” Journal of Economic Theory, 71: 44-74.
[15] Kranton, R. and Minehart, D. (2002), “A Theory of Buyer-Seller Networks,”
American Economic Review,
[16] Mongtomery, J. (1991), “Social Networks and Labor Market Outcomes: Toward
an Economic Analysis,” American Economic Review, 81: 1408-18.
[17] Rees, A. (1966) “Information Networks in Labor Markets,” American Economic
Review, 56: 559-66.
74
[18] Roth, A. E., and Sotomayor, M. (1990). “Two-Sided Matching: A Study in
Game-Theoretic Modeling and Analysis,” Econometric Society Monograph 18,
Cambridge Univ. Press, Cambridge.
[19] Shapley, L.and Scarf, H. ( 1974), “On Cores and Indivisibility,” Journal of
Mathematical Economics 1: 23-28.
[20] Tan, J. J. M. (1991). A Necessary and Su?cient Condition for the Existence of
a Complete Stable Matching, J. Algorithms 12: 154178.
[21] West, D.B. (1996) “Introduction to Graph Theory,” Upper Saddle River, NJ:
Prentice Hall.
75
doc_267214349.pdf
Design Management is a business discipline that uses project management, design, strategy, and supply chain techniques to control a creative process, support a culture of creativity, and build a structure and organisation for design.
ABSTRACT
Title of dissertation: TOPICS IN MARKET DESIGN
Thayer Morrill,
Doctor of Philosophy, 2008
Dissertation directed by: Professor Lawrence Ausubel
Department of Economics
My dissertation consists of two papers covering distinct topics within Microe-
conomic Theory. The ?rst chapter is drawn from Matching Theory. One of the
oldest but least understood matching problems is Gale and Shapley’s (1962) “room-
mates problem”: is there a stable way to assign 2N students into N roommate pairs?
Unlike the classic marriage problem or college admissions problem, there need not
exist a stable solution to the roommates problem. However, the traditional notion
of stability ignores the key physical constraint that roommates require a room, and
it is therefore too restrictive. Recognition of the scarcity of rooms motivates replac-
ing stability with Pareto optimality as the relevant solution concept. This paper
proves that a Pareto optimal assignment always exists in the roommates problem,
and it provides an e?cient algorithm for ?nding a Pareto improvement starting from
any status quo. In this way, the paper reframes a classic matching problem, which
previously had no general solution, to become both solvable and economically more
meaningful.
The second chapter focuses on the role networks play in market and social
organization. In network theory, externalities play a critical role in determining
which networks are optimal. Adding links can create positive externalities, as they
potentially make distant vertices closer. On the other hand, links can result in
negative externalities if they increase congestion or add competition. This paper will
completely characterize the set of optimal and equilibrium networks for a natural
class of negative externalities models where an agent’s payo? is a function of the
degree of her neighbors. These results are in sharp contrast to the optimal and
equilibrium networks for the standard class of positive externalities models where
payo? is a function of the distance two agents are apart. This highlights the role
externalities play in optimal and equilibrium network structure.
TOPICS IN MARKET DESIGN
by
Thayer Morrill
Dissertation submitted to the Faculty of the Graduate School of the
University of Maryland, College Park in partial ful?llment
of the requirements for the degree of
Doctor of Philosophy
2008
Advisory Committee:
Professor Lawrence Ausubel, Chair/Advisor
Professor Peter Cramton
Professor Emel Filiz Ozbay
Professor Daniel Vincent
Professor Subramanian Raghavan
c _ Copyright by
Thayer Morrill
2008
Dedication
I would like to dedicate this work to my wife, Melinda Sandler Morrill. I can
not imagine going through the process without her. What I can imagine is how
much worse the end product would have been.
ii
Acknowledgments
My second year at the University of Maryland was a pivotal year for me. I
was lucky enough to have Lawrence Ausubel, Peter Cramton, and Daniel Vincent as
instructors. I may not have learned all the economics I know from the three of them,
but it is not much of an overstatement to say I learned all the economics I enjoy
from them. My committee has been extremely supportive throughout my graduate
school experience, and for that, and for all I learned from them, I am extremely
grateful.
I would like to particularly thank my adviser Lawrence Ausubel. He is my
economic role model even if he more than once wrote empirical papers. I am forever
grateful for his mentorship and support.
My wife, Melinda Sandler Morrill deserves special acknowledgment. She has
read every word in this dissertation many times over. All of these ideas where shaped
while talking to her. If any of the thoughts in these papers are expressed clearly,
she is the one who deserves the credit.
I would like to thank Daniel Aromi, Jacques Cremer, Jonah Gelbach, Emel
Filiz Ozbay, Erkut Ozbay, and John Shea for their helpful suggestions. I received
very useful comments on my job market paper during many seminars, thank you to
those participants.
Finally, I would like to thank my dog and dissertation buddy, Jerry Sandler
Morrill. Almost everything you see here was written to the sounds of Jerry snoring.
iii
Table of Contents
List of Figures v
1 Introduction 1
2 The Roommates Problem Revisited 5
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 The Roommates Problem Revisited . . . . . . . . . . . . . . . . . . . 10
2.3 The Roommate Swap Algorithm . . . . . . . . . . . . . . . . . . . . . 16
2.4 Strategic Implications . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.5 Extensions and Modeling Issues . . . . . . . . . . . . . . . . . . . . . 28
2.5.1 Extensions to the Model . . . . . . . . . . . . . . . . . . . . . 28
2.5.2 Alternative Equilibrium Concepts . . . . . . . . . . . . . . . . 30
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.7 Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.7.1 Computational Complexity . . . . . . . . . . . . . . . . . . . . 34
3 Externalities in Networks 37
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2 Graph Theory Terminology . . . . . . . . . . . . . . . . . . . . . . . 44
3.3 Degree Based Utility Functions . . . . . . . . . . . . . . . . . . . . . 46
3.3.1 Pairwise Stability . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.3.2 Equilibrium with Transfers . . . . . . . . . . . . . . . . . . . . 51
3.4 A Reduced Form Utility Model . . . . . . . . . . . . . . . . . . . . . 62
3.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.6 Appendix - Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
Bibliography 73
iv
List of Figures
2.1 An example of a graph with four blocks. . . . . . . . . . . . . . . . . 17
2.2 An alternating cycle with its corresponding Pareto improvement. . . . 19
2.3 A “Blossom”. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.4 A blossom before and after contraction. . . . . . . . . . . . . . . . . . 23
2.5 A non-trivial block closed under roommates, but s
1
and s
2
are not
contained in any alternating-cycle. . . . . . . . . . . . . . . . . . . . . 25
2.6 An odd cycle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.1 A complete graph and a star. . . . . . . . . . . . . . . . . . . . . . . 45
3.2 An undesirable pairwise stable graph . . . . . . . . . . . . . . . . . . 50
3.3 Trivial graph for an even and odd number of vertices. . . . . . . . . . 66
v
Chapter 1
Introduction
Matching Theory, along with Auction Theory, are two of the great success
stories of microeconomic theory. One of the original matching theory papers was
Gale and Shapley’s 1962 paper College Admission and the Stability of Marriage.
This paper consists of a simple but interesting problem, a clever algorithm, and the
discovery that the solution space has a particularly desirable attribute. Theorists
continued to study the problem simply because it was interesting and the results
they discovered were so elegant. Eventually, about twenty years after the prob-
lems were introduced, economists started to recognize that the knowledge gained
from solving these problems could be applied to designing markets, speci?cally the
doctor-hospital resident market. In this way, matching theory has followed much
of mathematics. Academics studied the problems for years because the properties
discovered are beautiful, and eventually they recognized ways in which this elegant
theory can be applied.
The progress made in matching theory is almost completely contained in the
sub?eld of two-sided Matching Theory. In two-sided matching theory, we explore
how to best pair two types of distinct agents. This is commonly called the Marriage
Problem. Just as natural, and in fact more general, is the problem of how to best
pair two agents of the same type. This question, called the Roommates Problem,
1
has received almost no attention from the literature. This is because the very paper
that introduced it, Gale and Shapley (1962), proved that there does not need to
exist a stable solution to the Roommates Problem while there always exists a stable
solution to the Marriage Problem.
1
Economists accepted that an equilibrium need
not exist to the Roommate Problem and turned their attention elsewhere.
The second chapter in my dissertation seeks to rectify this situation. An
equilibrium does always exist in the Roommates Problem, but economists have
simply been looking in the wrong place. I introduce an alternative solution to the
classic formulation of the Roommates Problem. I prove that an equilibrium always
exists under this alternate notion of stability, and I discuss several algorithms for
making an equilibrium assignment and improving one that is in disequilibrium.
This is an original and signi?cant contribution to the ?eld of economics. I have
reframed a classic problem, which previously had no general solution, in a way that
is economically more meaningful and now solvable. This is particularly important
in the context of market design. As with the Marriage Problem, the mechanisms we
study for the Roommates Problem have the potential to be applied to help mitigate
market failure in some speci?c markets.
The third chapter in my dissertation looks at a di?erent sub?eld of microe-
conomic theory, Network Theory. Classical economic theory often assumes a con-
tinuum of agents in markets. There are situations where this is both convenient
and appropriate; however, the world is fundamentally a discrete place. There is no
1
A matching is stable if no two unassigned agents prefer each other to their current
assignment.
2
market with a continuum of agents, and there are many situations where the speci?c
combinatorial characteristics of the network are critical to the economic character-
istics of the market. For example, a car manufacturer does not buy brakes from a
market. Rather it has long term relationships with a few manufacturers. Moreover,
there are relatively few manufacturers of both cars and brakes. As such, the speci?c
relationships that the manufacturers do and do not have are critical to understand-
ing the market. It is precisely in this situation where a graph, and not a continuum,
is the appropriate way to model the market.
While Network Theory has received a lot of attention in recent years, there
has been little attention paid to how the choice of utility function a?ects which
networks will emerge. This is the focus of the third chapter in my dissertation. I am
able to completely characterize one of the most natural classes of utility functions:
when the payo? an agent receives is a nonincreasing function of the degree of her
neighbors. This is meant to model congestion or competition. An agent receives a
payo? for the relationships she has, but these relationships are less bene?cial the
more people she has to compete with. The classic example in the literature is a
model of co-authors. The bene?t an academic receives from having a co-author is
decreasing in the number of co-authors that person has as she will have less time to
devote to the project.
This characterization of degree based utility models is important for its own
sake, but especially as a contrast to the known results for distance based utility
functions. A utility function is distance based if the payo? two agents receive from
being connected is a nonincreasing function of the distance they are apart in the
3
network. The networks I ?nd to be optimal and stable for a degree based function are
strikingly di?erent from the optimal networks for a distance based utility function.
The fact that both models are intuitive yet lead to dramatically di?erent optimal
networks means that when a researcher is attempting to model an economic situation
with a network based model, she needs to be particularly careful how she chooses
the underlying utility function.
4
Chapter 2
The Roommates Problem Revisited
One of the oldest but least understood matching problems is Gale and
Shapley’s (1962) “roommates problem”: is there a stable way to assign
2N students into N roommate pairs? Unlike the classic marriage prob-
lem or college admissions problem, there need not exist a stable solution
to the roommates problem. However, the traditional notion of stability
ignores the key physical constraint that roommates require a room, and
it is therefore too restrictive. Recognition of the scarcity of rooms moti-
vates replacing stability with Pareto optimality as the relevant solution
concept. This paper proves that a Pareto optimal assignment always
exists in the roommates problem, and it provides an e?cient algorithm
for ?nding a Pareto improvement starting from any status quo. In this
way, the paper reframes a classic matching problem, which previously
had no general solution, to become both solvable and economically more
meaningful.
2.1 Introduction
Economics is often de?ned as the study of how to e?ciently allocate scarce
resources. As such, assignment problems are at the heart of economics. Two-sided
matching theory asks how to best match agents of two distinct types. Examples
include students and schools, residents and hospitals, or kidneys and people in need
of a transplant. A di?erent but related question asks how to best pair two agents
of the same type. Examples of these one-sided matches include roommates at a
university, lab partners in a science class, and partners in a police force. Two-
sided matching theory has been well studied by economists who have created an
elegant and applicable theory. One-sided matching theory has been comparatively
5
neglected
1
.
This neglect is likely due to the very paper that introduced it. In their classic
1962 article College Admissions and the Stability of Marriage, Gale and Shapley
introduce both the marriage problem and the roommates problem. While Gale and
Shapley prove a stable match always exists in a two-sided market, they introduce
the roommates problem to demonstrate that a stable pairing need not exist in a one-
sided market. Since a stable match need not exist, economists have been stymied in
their attempts to ?nd and analyze solutions to this important assignment problem.
Unfortunately, this has led many economists to turn their attention elsewhere, and
as a result, the economics literature on this classic problem is sparse.
This paper starts by questioning if stability is the correct equilibrium concept.
Gale and Shapley de?ne a set of marriages as unstable if either there exist a man
and woman who are not married but prefer each other to their current spouse or
there exists someone who would prefer to be single than married to their current
partner. Stability in the roommates problem is borrowed from the marriage model.
A pairing is unstable if two students prefer to live with each other rather than their
current assignment.
2
Stability ?ts the marriage model so well that no other solution
1
Roth and Sotomayor (1990) is an excellent introduction to the two-sided matching
literature. Gus?eld and Irving (1989) is also a nice introduction. Interestingly, although
the economics literature on the roommates problem is very small, there is a comparatively
large computer science literature on it. Roth and Sotomayor, two economists, mention
the roommates problem only as an example. In contrast, Gus?eld and Irving, two com-
puter scientists, devote nearly a quarter of the book to the roommates problem. Finding
a traditionally-stable roommate pairing (if one exists) is considered a “hard” algorithmic
question. The bulk of their presentation is a polynomial-time algorithm for ?nding a
traditionally-stable pairing when one exists. Tan (1991) establishes a necessary and su?-
cient condition for the existence of a stable pairing. Chung (2000) extends Tan’s result to
a su?cient condition for the existence of a stable pairing when preferences are weak.
2
I am interested in the case where each student is required to have a roommate. Con-
6
concept has been needed or suggested. The same is not true of the roommates
problem. Roommates face an additional constraint that married couples do not;
roommates must have a room in which to live. A student may prefer another to
her assigned roommate; however, she needs a room in which to live and presumably
does not have the right to evict her current roommate. Therefore, the traditional
notion of stability is too restrictive.
I will present Gale and Shapley’s original example to highlight this point.
Example (Gale and Shapley, 1962): A Stable Assignment Need Not Exist
Suppose there are four students: ?, ?, ? and ?. ?’s top choice is ?, ?’s top
choice is ?, ?’s top choice is ?, and all three rank ? last. Gale and Shapley de?ne an
assignment to be unstable if two students are not currently roommates but prefer
each other to their current assignment. Under this de?nition, there does not exist
a stable assignment since whoever is assigned to ? prefers the other two students to
? and is the top choice of one of these students. In the words of Gale and Shapley:
“...whoever has to room with ? will want to move out, and one of the
other two will be willing to take him in.”
While one of the other two may be willing to take him in, it is quite a di?erent
matter whether this student is able to take him in. In order to take him in, either
his current roommate must voluntarily leave, be evicted, or an additional room must
be available. With a scarcity of rooms and with no student willing to change his
sequently, I do not include in my de?nition of stability the additional requirement that
each student prefers her assignment to being unassigned.
7
assignment to ?, the original assignment is an equilibrium after all.
If an agent can dissolve her partnership unilaterally, then stability is the nat-
ural equilibrium concept. If she ?nds someone she prefers who also prefers her, then
both parties will dissolve their current partnership and pair together. As a result,
the original assignment is not an equilibrium. However, if a partnership requires
bilateral agreement to dissolve, then two agents wanting to change their assignment
is not enough to disturb the original pairing. If bilateral agreement is required, an
assignment will only be changed if all involved parties agree. Since an agent will
only agree if the new assignment makes her better o?, any deviation from the orig-
inal set of assignments must be a Pareto improvement. Therefore, when bilateral
agreement is required to dissolve a partnership, Pareto optimality, not stability, is
the proper equilibrium concept. If an assignment is Pareto optimal, then there is
no reassignment that all parties will consent to; therefore, the original assignment
will not be disturbed.
Most of matching theory studies assignments that can be unilaterally dissolved.
Assignments which can only be dissolved with bilateral agreement are an important
but little studied second category. As argued above for the roommates problem,
an essential but scarce input creates the need for bilateral agreement. Additional
examples include police o?cers who require a police car to do patrol and partners
in a science class who must work at a common laboratory. The same requirement
can be created by a legally binding contract that can only be modi?ed by mutual
consent. For example, many professional athletes have no-trade clauses in their
contract which they may waive at their discretion. In the presence of such clauses,
8
the assignment of an athlete to a team can only be disturbed when all relevant
parties approve the trade.
This paper focuses on the roommates problem as reconsidered using the equi-
librium concept of Pareto optimality. I will show there always exists an e?cient
assignment. Therefore, unlike the case where stability is applied, an equilibrium
always exists in the roommates problem. Moreover, I show an ine?cient assignment
can always be Pareto improved to an e?cient one. These results motivate several
questions. If an assignment has not been made, how should we make it? If an
assignment has been made, how can we determine if the assignment is e?cient? If
an assignment is ine?cient, how can we Pareto improve it? These questions are the
focus of this paper. In particular, the last two turn out to be complicated. To an-
swer them I introduce an algorithm, The Roommate Swap, which identi?es whether
an assignment is ine?cient and ?nds a Pareto improvement when it is.
Much of the analysis in this paper relies on tools from graph theory. Networks
are a natural way of representing assignment problems, particularly one like the
roommates problem where two agents are paired. In particular, my algorithm relies
heavily on applying Edmund’s Blossom algorithm
3
to the graph theoretic represen-
tation of the roommates problem.
The paper is organized as follows. Section 2 formally introduces the problem
and proves existence. Section 3 details the Roommate Swap algorithm. Section 4
examines the strategic implications of several assignment mechanisms. Section 5
looks at extensions and modeling issues, and section 6 concludes. The appendix
3
Edmunds (1965).
9
provides several technical proofs and a discussion of the computational complexity
of the Roommate Swap algorithm.
2.2 The Roommates Problem Revisited
We wish to assign 2N students to M rooms. Students have preferences over
all other students that are strict, complete, and transitive. All rooms are identical
and students have no preference as to which room they are assigned.
An assignment is a function that pairs students. Every student is assigned to
exactly one other student, and assignments are symmetric.
De?nition 1. Let S be a set of students with [S[ = 2N. A function µ : S ? S is
an assignment of S if:
1. µ(s) ,= s.
2. µ(s
1
) = µ(s
2
) ?s
1
= s
2
.
3. µ(µ(s)) = s.
The traditional equilibrium concept is based on the notion of a blocking pair.
De?nition 2. Two students s and t are a blocking pair to an assignment µ if
µ(s) ,= t but s ~
t
µ(t) and t ~
s
µ(s). An assignment is stable if there does not
exist a blocking pair
4
.
4
The traditional de?nition of stability also includes the constraint that the person
prefers her assignment to being unassigned. In my model every student must be assigned
to some room, so I omit this additional constraint.
10
As argued in the introduction, this is not the proper equilibrium concept for
the roommates problem. A roommate assignment is an equilibrium if it is Pareto
optimal.
De?nition 3. An assignment µ is ine?cient if there exists a di?erent assignment
µ
such that for every student s, µ
(s) _
s
µ(s). An assignment is Pareto optimal
(e?cient) if it is not ine?cient.
Since preferences are strict, if µ
Pareto improves µ, then at least four stu-
dents must strictly prefer µ
to µ. As the following result proves, the set of stable
assignments is a subset of the set of e?cient assignments.
Proposition 1. If an assignment is stable, then it is Pareto e?cient.
Proof. I will prove the contrapositive. If an assignment µ is ine?cient, then there
exists an assignment µ
that Pareto improves µ. Let s be any student such that
µ(s) ,= µ
(s). Since µ
is a Pareto improvement of µ, both µ
(s) ~
s
µ(s) and
s ~
µ
(s)
µ(µ
(s)). Therefore, s and µ
(s) form a blocking pair to µ.
Note that the reverse direction need not hold. An assignment can be Pareto
e?cient but not be stable. In Gale and Shapley’s original example, no assignment
is stable yet every assignment is Pareto e?cient.
With the following assumptions, the general case of 2N students and M rooms
reduces to the more familiar case of 2N students and N rooms:
Assumption 1. Each student prefers having a room to not having a room.
11
Assumption 2. Each student would rather have a room to herself than to be as-
signed a roommate.
Assumption 3. At most two students can be assigned to a room.
Note that if N > M, some students will not be assigned a room. Such a student
cannot be involved in a Pareto improving switch by Assumption 1. Similarly, if N <
M, a number of students will not be assigned a roommate. Assumption 2 implies
such a student will never be involved in a Pareto improving switch. Therefore, the
only set of students relevant for this problem are those who have been assigned a
roommate. By Assumption 3, this set has exactly twice as many students as rooms.
Without loss of generality, for the rest of the paper I will assume there are 2N
students and N rooms.
Gale and Shapley show that an assignment without a blocking pair need not
exist. However, an e?cient assignment always exists.
Proposition 2. An e?cient roommate assignment always exists.
Proof. (Random serial dictatorship
5
) Assign every student a priority (randomly or
otherwise). Assign the student with highest priority her most preferred roommate
and remove them both from consideration. From students who remain, assign the
student with highest priority her most preferred roommate among those students
that are unassigned. Remove these two from consideration and repeat until no
5
Abdulkadiroglu and Sonmez (1998) is a very nice paper on the Random Serial Dic-
tatorship mechanism. They analyze it in the context of a housing allocation problem
where n students are to be assigned to n rooms, but it is rather interesting how robust
the Random Serial Dictatorship is. The same mechanism can be used to make a Pareto
e?cient assignment of a student and a room, two students to be roommates, three or more
students to be roommates, students to be roommates and the room they will live in, etc.
12
students remain. This assignment is Pareto e?cient. To see this, note that if a
student is involved in a Pareto improvement, then necessarily her roommate must
be involved as well. The student with highest priority, s
1
, receives her top choice,
s
2
, so neither she nor her choice can be involved in a Pareto improvement. Let s
3
be
the student who chooses second. Since neither s
1
or s
2
are involved in any Pareto
improvements, if s
3
is part of a Pareto improvement she must be reassigned to a
student among S ¸ ¦s
1
, s
2
¦. However, s
3
already receives her top choice among this
set. Therefore, s
3
(and consequently the student she chooses) is not part of any
Pareto improvement. Similarly, the student who chooses third is not part of any
Pareto improvement, and so on.
The following is a stronger statement and implies Proposition 1. It is stated
to motivate the Roommate Swap algorithm.
Proposition 3. If an assignment µ is ine?cient, there exists an e?cient assign-
ment µ
which Pareto improves µ.
The proof is straightforward but is included as it motivates the need for the
Roommate Swap Algorithm.
Proof. Let µ be an assignment and PI(µ) be the set of strict Pareto improvements
of µ. Transitivity of preference implies ?µ
? PI(µ), PI(µ
) ? PI(µ). Since µ
?
PI(µ) ¸ PI(µ
), PI(µ
) ? PI(µ). Since there are only a ?nite number of possible
assignments, the following chain must converge to the empty set:
PI(µ) ? PI(µ
1
) ? PI(µ
2
) ? . . . , where µ
i
? PI(µ
i?1
)
13
In particular, there must exist an j such that PI(µ
j
) = ?. µ
j
is an e?cient assign-
ment which Pareto improves µ.
Put simply, if µ is not e?cient, there exists a Pareto improvement µ
1
. µ
1
is
either e?cient or can be Pareto improved to µ
2
, etc. We must eventually reach
an e?cient assignment, and since preferences are transitive, this assignment must
Pareto improve µ.
Propositions 2 and 3 motivate two distinct but related problems. The ?rst
problem is how to make an e?cient assignment when no assignment has yet been
made. The second is how to Pareto improve an ine?cient assignment to an e?cient
one. Although these two problems are very similar, it is surprising how di?erent
these processes end up being. The serial dictatorship used in Proposition 2 to
show existence provides a linear-time procedure for ?nding an e?cient assignment.
In contrast to the ease of ?nding an e?cient assignment, it is rather di?cult to
even determine if any given assignment is e?cient let alone how to improve it.
Preferences between students need not interact when assigning students, but they
interact directly when determining if one assignment Pareto improves another. This
makes it signi?cantly more complicated to determine if an assignment is e?cient
than it is to simply ?nd an e?cient assignment.
At this point the reader may object as there is an obvious and trivial algorithm
to determine if an assignment is e?cient. Namely, one could simply look at each
possible reassignment and determine if it Pareto improves the original. If no as-
signment Pareto improves the original, then the original is e?cient. Unfortunately,
14
Students Number of Possible Assignments
2 1
4 3
6 15
8 105
10 945
12 10,395
14 135,135
16 2,027,025
18 34,459,425
20 654,729,075
30 6,190,283,353,629,370
2N
(2N)!
2
N
(N!)
this algorithm is of no practical use as the growth of the number of assignments
relative to students being assigned is factorial. Speci?cally, given 2N students there
exists
(2N)!
2
N
(N!)
= (2N ? 1)(2N ? 3)(2N ? 5) (3)(1) many ways of assigning them
to be roommates.
6
Even for small N, this is prohibitively large. For example, there
exists on order of 6 quadrillion (6 10
15
) many ways to assign 30 students to be
roommates. Therefore, a more sophisticated process is required.
6
A short proof appears in the Appendix.
15
2.3 The Roommate Swap Algorithm
This section demonstrates an O(n
2
) algorithm for determining if an assignment
is e?cient. Moreover, when an assignment is ine?cient I provide an O(n
3
) algorithm,
The Roommate Swap, for ?nding a Pareto improvement.
7
Much of the analysis uses
tools from graph theory, so it is necessary to present some de?nitions and results.
This document is intended to be self-contained, but I refer the reader to Introduction
to Graph Theory, second edition, by Douglas West for a more detailed analysis of
graph theory.
A graph consists of vertices and edges between them. For my purposes, all
edges are undirected.
1. Two vertices are adjacent if there is an edge between them.
2. The degree of a vertex v, denoted d(v), is the number of vertices it is adjacent
to.
3. A path is a sequence of vertices ¦v
1
, v
2
, . . . , v
k
¦ such that no vertex appears
twice and any two consecutive vertices are adjacent.
4. A cycle is a sequence of vertices ¦v
1
, v
2
, . . . , v
k
¦ such that no vertex appears
twice, any two consecutive vertices are adjacent, and v
1
and v
k
are adjacent.
5. Two vertices are connected if there is a path between them. Since our graphs
are undirected, connected is a reciprocal relationship. A graph is connected if
all vertices are connected.
7
A discussion on the computational complexity of the algorithm appears in the ap-
pendix.
16
6. A vertex is incident to an edge if it is one of the edge’s endpoints. G ¸ v is
the graph that results from deleting the vertex v and all edges incident to v.
7. A vertex v is a cut-vertex if G is connected, but G¸ v is not.
8. A block is a maximal subgraph containing no cut vertex.
Note that the subgraph consisting of two vertices and an edge between them
contains no cut-vertex, so any edge is either a block or a subset of a block. I will
refer to any block containing only two vertices as a trivial block. Since every vertex
in our graph has at least one edge incident to it, this is the smallest block possible.
Figure 2.1 shows an example where the blocks have been circled.
Figure 2.1: An example of a graph with four blocks.
De?nition 4. Given an assignment µ, a set of students X is closed under room-
mates if s ? X implies µ(s) ? X.
Given a set of preferences ~ and assignment µ, I will induce a graph, G
µ
, as
follows:
• Each vertex corresponds to a student. Label the vertices s
1
through s
n
. When
referring to the graph, I will use the term vertex and student interchangeably.
17
• A solid edge is drawn between roommates. By de?nition, each vertex is inci-
dent to exactly one solid edge.
• Draw a dashed edge between any two students that form a blocking pair to µ.
That is to say, if s
i
prefers s
j
to her current roommate and vice versa.
When the preferences and assignment are clear from the context, I will just
refer to the graph as G. I will call a path that alternates between dashed and
solid edges (or vice versa) an alternating path. Similarly, a cycle that alternates
between dashed and solid edges is an alternating cycle.
Lemma 1. An assignment µ is e?cient under preferences ~ if and only if G
µ
contains no alternating cycle. Moreover, if µ
Pareto improves µ and s is a student
such that µ(s) ,= µ
(s), then s is contained in an alternating cycle in G
µ
.
The intuition for su?ciency is captured in Figure 2.2. In an alternating cycle,
we can simply “swap” roommates. We eliminate the solid edges, make the dashed
edges in the cycle solid, and leave everyone outside the cycle unchanged. This is a
well-de?ned reassignment that Pareto improves the initial assignment.
Proof. Suppose G
µ
contains an alternating cycle C. An alternating cycle is closed
under roommates as each vertex is incident to a solid edge in the cycle. This implies
V (G) ¸ C is closed under roommates as well (V(G) means the vertex set of G). We
will construct a Pareto improvement µ
. For every v ? V (G) ¸ C let µ
(v) = µ(v).
This is well de?ned since V (G) ¸ C is closed under roommates. For every v ? C, let
µ
(v) be the vertex it shares a dashed edge with in the cycle C. This is well de?ned
18
Figure 2.2: An alternating cycle with its corresponding Pareto improvement.
S
1
S
2
S
3
S
4
S
5
S
6
S
7
S
8
S
1
S
2
S
3
S
4
S
5
S
6
S
7
S
8
as each vertex is incident to exactly one dashed edge in the cycle and sharing a
dashed edge is a reciprocal relationship. A dashed edge indicates that both vertices
prefer each other to their original assignment. Therefore, µ
Pareto improves µ.
Suppose that µ
is a Pareto improvement of µ. Let G
be the subgraph consist-
ing of all solid edges in G
µ
and only the dashed edges between vertices not paired
by µ that are paired by µ
(since µ
is a Pareto improvement, there must be a dashed
edge between such vertices). Note that any vertex v in G
either has degree
8
1 (if
µ(v) = µ
(v)) or degree 2 (if µ(v) ,= µ
(v)). Moreover, for any vertex v, if d(v) = 2,
then d(µ(v)) = d(µ
(v)) = 2. Choose any vertex t such that d(t) = 2. t is con-
nected via a solid edge to µ(t). Since d(t) = 2, d(µ(t)) = 2 and so µ(t) must be
connected via a dashed edge to µ
(µ(t)). µ
(µ(t)) must be connected via a solid edge
to µ(µ
(µ(t))) which must be connected to a dashed edge via µ
(µ(µ
(µ(t)))), and so
on. Eventually this process must cycle as there is only a ?nite number of vertices.
However, a cycle to any vertex s ,= t would mean the degree of s is at least three
which is not possible. Therefore, the process must cycle back to our ?rst vertex t.
8
The degree of a vertex v, denoted d(v), is the number of edges v is incident to.
19
Moreover, it must cycle via a dashed edge as we have already exhausted t’s solid
edge. By construction, this is an alternating cycle.
Lemma 2. Let t be any student.
1. t and µ(t) are contained in a unique block, B
t
.
2. If t is part of an alternating-cycle C, then C ? B
t
.
3. If t is involved in a Pareto improvement, then B
t
is non-trivial. That is
to say if there exists an assignment µ
such that µ
Pareto improves µ and
µ
(t) ,= µ(t), then [B
t
[ > 2.
Proof.
1. Since there is an edge between t and µ(t), they are in at least one block
together. Since the intersection of two blocks contains at most one student,
9
t
and her roommate must be in exactly one block together. Call this block B
t
.
2. A cycle contains no cut-vertex, so it must be a subset of a block. An alternating-
cycle containing t must contain µ(t) since t lies on a solid edge in the alternating-
cycle. Since B
t
is the unique block containing t and µ(t), the cycle must be
contained in B
t
.
3. If t is involved in a Pareto improvement, then by Lemma 1 t is contained in an
alternating-cycle. By (2) this alternating-cycle is contained in B
t
, so B
t
must
9
See West pg. 156. The intuition is that if if two blocks B
1
and B
2
share two vertices,
then after cutting a vertex, at least one of the two must remain. Call this vertex v. v
is connected to all remaining vertices as it is in a block with each of them. But if every
vertex has a path to v, then all vertices are connected. Therefore B
1
?B
2
has no cut-vertex
contradicting the maximality of a block.
20
contain more than just t and µ(t).
Lemma 2, part (2) says that if a student t is part of a Pareto improvement
(and consequently an alternating-cycle), then she must be reassigned to a member
of B
t
. Therefore, no edge between t and a vertex outside of B
t
can be part of an
alternating-cycle. Let G
be the graph obtained by deleting all edges between t and
any vertex not in B
t
. Then G contains an alternating-cycle if and only if G
contains
an alternating-cycle. This motivates the following procedure.
Pruning a Graph
1. Start with a graph G.
2. Determine the set of blocks B
1
, B
2
, . . . , B
m
.
3. For each student-roommate pair s and µ(s), locate the unique block that both
are in. Remove all edges from either s or µ(s) to any student outside this
block.
A key point is that if a student s was in a block B with µ(s) ,? B, then after
pruning the graph, s is no longer in B. By iterating the pruning process we end up
with a graph in which all blocks are closed under roommates. Note that these blocks
may be trivial, but by Lemma 2, the students in such a block are not involved in
any Pareto improvements.
Proposition 4. Any non-trivial block closed under roommates contains an alter-
nating cycle.
21
Figure 2.3: A “Blossom”.
s
i?2
s
i?1
s
i
s
i+1
s
i+2
s
i+3
s
i+6
s
i+5
s
i+4
The algorithm in this proof was inspired by Edmunds’ Blossom Algorithm
from graph theory
10
and Gale’s Top-Trading Cycles Algorithm.
11
Proof. Look at any non-trivial block B closed under roommates. Every vertex v in
B must be incident to a dashed edge. Otherwise v is only connected (by a solid
edge) to µ(v) which would mean removing µ(v) disconnects v from the rest of the
block. This is not possible since a block contains no cut-vertices. Start with any
vertex s. First take a dashed edge to a new vertex s
1
then continue on a solid edge
to s
2
= µ(s
1
). Continue alternating between dashed and solid edges until we cycle.
We must eventually cycle since there is a ?nite number of vertices.
If our cycle is even (a cycle is even if it contains an even number of vertices),
then we are done. By construction, an even cycle alternates between dashed and
solid edges and is therefore an alternating cycle. Therefore, assume our cycle is
odd, ¦s
i
, s
i+1
, s
i+2
, . . . , s
i+2m
¦. By construction, any odd cycle looks like Figure 2.3,
except possibly of di?erent length. Edmunds refers to this as a blossom. The vertices
¦s
1
, s
2
, . . . , s
i
¦ are the stem, s
i
is the base of the blossom, and s
i
must connect to
s
i+1
and s
i+2m
via dashed edges.
10
Edmunds (1965). A discussion of the Blossom algorithm appears in West, page 142.
11
Shapley and Scarf (1974).
22
There must by a dashed edge from one of s
i+1
, s
i+2
, . . . , s
i+2m
to a vertex
outside the cycle. Otherwise s
i
would be a cut-vertex as deleting it would disconnect
s
i+1
, s
i+2
, . . . , s
i+2m
from the rest of the graph. What we will do is contract the
odd cycle into a single super-vertex S
1
i
. The superscript indicates the number of
contractions we performed to result in S
i
. See Figure 2.4 for an example. Make any
edge that was previously between a vertex in the cycle and a vertex t outside the
cycle now between S
1
i
and t. Note that there is a solid edge between s
i?1
and S
1
i
and
all other edges incident to S
1
i
must be dashed as for any s
j
? ¦s
i+1
, s
i+2
, . . . , s
i+2m
¦,
µ(s
j
) ? ¦s
i+1
, s
i+2
, . . . , s
i+2m
¦.
Now continue with one of the unexplored dashed edges incident to S
1
j
. Again,
we must eventually cycle. If the cycle is even, stop. If the cycle is odd, contract
the blossom and continue. There must always be an unexplored dashed edge out
of an odd cycle (or else the base vertex would be a cut vertex), so after any odd
cycle we will be able to continue. Since we have a ?nite number of vertices and
edges and each contraction reduces the number of vertices, we cannot continue
inde?nitely. The algorithm only stops with an even cycle, and since the algorithm
must eventually terminate, we must eventually reach an even cycle.
Figure 2.4: A blossom before and after contraction.
s
i?1
s
i
s
i+1
s
i+2
s
i+4
s
i+3
s
i+5
s
i?1
S
1
i
s
i+5
23
Any alternating cycle containing super-vertices can be expanded to an alter-
nating cycle containing no super-vertices. No matter how we enter the blossom,
either the edge to the left or to the right is solid. We can follow the cycle in the
direction of the solid edge all the way to base vertex. This is an alternating path
to the base, the cycle connects to the base with a dashed edge, and then continues
along the stem starting with a solid edge. So indeed, this expands an alternating
path through a super-vertex to an alternating path through the cycle that was con-
tracted. If our super-vertex is the result of multiple contractions, then our base
vertex is now a super-vertex but otherwise nothing changes. Moreover, the base is
a super-vertex containing fewer contractions, so we can proceed by induction on the
number of contractions to get the desired result.
Proposition 4 implies a simple procedure for determining whether an assign-
ment is e?cient.
Determining if an assignment µ is e?cient given preferences ~.
1. Induce graph G
µ
.
2. Iteratively prune G
µ
until all blocks are closed under roommates.
3. If all blocks are trivial, then our assignment is e?cient. If there exists a non-
trivial block, then by Proposition 4 and Lemma 1, our assignment is ine?cient.
The algorithm in the proof ?nds an alternating cycle when one exists. Once
we have located an alternating cycle then just as we did in Figure 2.2 on page
24
Figure 2.5: A non-trivial block closed under roommates, but s
1
and s
2
are not
contained in any alternating-cycle.
s
1
s
3
s
5
s
2
s
4
s
6
19, we “swap” roommates to get a Pareto improvement, . For this reason I call
the algorithm the Roommate Swap. Note that we have now answered the two
key questions from the previous section. The Roommate Swap identi?es if a given
assignment is e?cient. Moreover, when an assignment is ine?cient, it ?nds a Pareto
improvement.
The Roommate Swap determines if a given assignment is e?cient. However,
a particular student likely does not care whether the assignment can be Pareto im-
proved. Rather, she would like to know if she can be part of a Pareto improvement.
Unfortunately, Proposition 4 does not generalize to the statement if a student t is
contained in a non-trivial block closed under roommates, then t is involved in a
Pareto improvement. Figure 2.5 is a non-trivial block that is closed under room-
mates, but s
1
and s
2
are not part of any Pareto improvements.
The Roommate Swap does not determine if a particular student can improve
her assignment. However, it is not biased. If we randomly choose the vertex we
start with, and when we have a choice, we randomly choose which edge to continue
on, then the Roommate Swap will ?nd any Pareto improvement with probability
that is uniformly bounded away from zero. Therefore, if the Roommate Swap is
25
run repeatedly, it will determine if an individual student is involved in a Pareto
improvement with probability one.
2.4 Strategic Implications
This paper has focused on two problems: ?nding an e?cient assignment and
?nding an e?cient Pareto improvement of an ine?cient assignment. Continuing
the pattern from previous sections, ?nding a strategy-proof mechanism for making
an assignment is easier than ?nding a strategy-proof mechanism for improving an
assignment. In fact, we will ?nd that there does not exist a mechanism for select-
ing a Pareto improvement of a given assignment that makes truthful revelation of
preferences a dominant strategy. These results follow very closely the results for
two-sided matching theory presented in Roth and Sotomayor (1990).
Following the matching literature, I will use dominant strategy as my equilib-
rium concept.
De?nition 5. A dominant strategy is a strategy that is a best response to all
possible strategies of the other agents. An assignment mechanism is strategy proof
if it is a dominant strategy for each agent to reveal her preferences truthfully.
There does exist a strategy-proof mechanism for making an e?cient assign-
ment. In fact, we have already seen this mechanism several times.
Observation 1. The serial dictatorship is strategy proof.
In the serial dictatorship, a student’s preferences are irrelevant unless she is
the one choosing her roommate. Since she gets her top choice, she does best when
26
she submits her true preferences regardless of the preferences submitted by other
students.
Finding an incentive compatible, e?cient assignment mechanism is very closely
related to Social Choice theory and Arrow’s Impossibility Theorem. The Gibbard-
Satterthwaite Theorem says that if arbitrary preferences are possible, then the
unique incentive-compatible, Pareto optimal mechanism is the dictatorship mecha-
nism. Unfortunately this cannot be directly applied as we are restricting the domain
of allowable preferences. A students is only allowed to have preferences over her own
assignment, and therefore, she is forced to be indi?erent between many assignments.
For example, a student does not have a single most-preferred assignment, but rather,
she is indi?erent among all assignments that match her to her most-preferred room-
mate. A dictator mechanism would not be Pareto optimal as, among her top choices,
the dictator would select a Pareto optimal assignment only by chance. The serial
dictatorship is the generalization of the dictatorship mechanism that has the prop-
erties of incentive compatibility and Pareto optimality. Due to the corresponding
uniqueness results for the dictatorship mechanism, it seems likely that the serial
dictatorship is the unique incentive-compatible mechanism for selecting an e?cient
assignment.
Lemma 3. There does not exist a strategy-proof mechanism for selecting a Pareto
improvement of an ine?cient assignment.
Lemma 3 is proved in the appendix. This is quite a general result, but it is
rather easy to proof. A strategy-proof mechanism must be able to handle any initial
27
assignment and any pro?le of preferences. Following the path of Roth (1982), I
demonstrate a case that no mechanism is able to handle.
2.5 Extensions and Modeling Issues
2.5.1 Extensions to the Model
Not surprisingly, the existence of an e?cient solution is quite general. For
example, if students have preferences over both their roommate and the room they
are assigned, then Propositions 2 and 3 still hold. In fact, the same proofs are still
valid. Similarly, if more than two students are assigned to be roommates, the same
existence results hold.
This paper has focused on one-sided matches, but there are many interesting
examples of two-sided matches with a physical constraint. Whenever a two-sided
match requires bilateral approval to dissolve, then any Pareto optimal assignment
will be an equilibrium. For example, an airline matches a pilot with a navigator in
order to ?y an airplane. The presence of a physical constraint, the airplane, means
a blocking pair is not enough to disturb an assignment.
The extra structure inherent in a two-sided match makes it easier to ?nd a
Pareto improvement to a two-sided match than a one-sided match. Here we can
use a slight variation of the Top Trading Cycles algorithm
12
to determine if an
assignment is Pareto optimal and to Pareto improve the assignment when it is not.
For a given pilot p, de?ne a navigator n to be achievable for p if n weakly prefers p
12
See Shapley and Scarf, 1974.
28
to her current assignment. Have each pilot point to her most-preferred, achievable
navigator. Note that a pilot always has a navigator to point to as her current
assignment is achievable. Have each navigator point to their current assignment.
There must exist a cycle since there are only a ?nite number of agents and each
agent is pointing to someone. If the cycle is trivial (the pilot is pointing to the
navigator she is currently assigned to), then neither the pilot nor the navigator can
be involved in a Pareto improvement and we can remove them from consideration. If
the cycle is non-trivial, then it represents a strict Pareto improvement for all agents
in the cycle. Future drafts of this paper will contain a more detailed discussion of
two-sided matches with a physical constraint.
When students have preferences over both their roommate and the room they
are assigned, there still exists an e?cient assignment. However, the Roommate
Swap does not readily generalize to this case. The notion of a “swap” completely
characterizes a Pareto improvement when only one other factor is involved in a
pairing; however, with multiple dimensions a Pareto improvement can be much
more complicated.
However, there is one very speci?c but important case where the Roommate
Swap can be readily generalized. If students have lexicographical preferences over
their roommate and room, then we will be able to ?nd a Pareto improvement for
any ine?cient assignment. If the students care about the room ?rst and the room-
mate second, then we can run the Top Trading Cycles algorithm to ?nd a Pareto
improvement when one exists. If a student cares about her roommate ?rst and
her room second, then we can ?rst run the Roommate Swap and next run the Top
29
Trading Cycles algorithm. There are a variety of ways we can aggregate individ-
ual preferences over rooms to a single roommate-pairing preference over rooms that
will result in an e?cient allocation. Thus, starting with an arbitrary assignment
and lexicographical preferences over roommates and rooms, we can determine if an
assignment is e?cient, and if not, Pareto improve it to an e?cient one.
2.5.2 Alternative Equilibrium Concepts
This paper has focused on pairing two agents as this is the classic framing
of the roommates problem. While I believe e?ciency, not stability, is the correct
equilibrium concept for this classic problem, the more agents that are assigned to
be together, the less compelling e?ciency becomes as an equilibrium. If six people
are assigned to an o?ce, it is likely that a person can switch desks with a student in
another o?ce without requiring unanimous approval from her current o?cemates.
We can formulate an alternative equilibrium that has more appeal in this case.
Instead of assigning six people to be o?cemates, we make six keys to each o?ce and
give each person a key to one o?ce. Since the rooms are homogeneous, this is just
an indirect way of assigning o?cemates. If we allow students to trade keys, then
an assignment is an equilibrium if no two students wish to trade o?ces. Note that
we are honoring the physical constraint; no student is being evicted. Moreover, this
does not allow a student to block another student from switching her assignment.
Similar to stability, there need not exist an equilibrium if students can trade
rooms. Suppose there are four students, a, b, c, and d, with preferences as follows:
30
a : b is most preferred
b : c is most preferred
c : d is most preferred
d : a ~ c ~ b
If a is assigned to b and c is assigned to d, then b and d will trade places. If a
is assigned to d and b is assigned to c, then a and c will trade places. Finally, if a is
assigned to c and b is assigned to d, then a and d will trade places. Since these are
the only possible assignments, there is no equilibrium.
In general, an argument can be made for either equilibrium. The new equilib-
rium might be a reasonable model for condominiums or rooms in a group house. If a
person decides to sell her condominium, she does not need the approval of the other
condominium owners in the building. Note however that there also exists building
cooperatives. Here a sale does require the approval of the board, so in this context,
Pareto optimality is a more natural equilibrium concept. Similarly, depending on
the lease a person signs, subletting a room in an apartment or group house may or
may not require the approval of the landlord or other tenants. Therefore, whether
or not Pareto optimality is the best equilibrium concept depends on the particular
lease signed.
31
2.6 Conclusion
The roommates problem is one of three assignment problems introduced by
Gale and Shapley in their classic 1962 paper College Admissions and the Stability of
Marriage. This is the paper that created the ?eld of matching theory, and the reason
why the roommates problem was included is that it is such a natural assignment
problem. While their other two assignment problems, the marriage problem and the
college admission problem, have been studied extensively, little progress has been
made on the roommates problem. This paper hopes to make several contributions to
the matching theory literature on the roommates problem. First, identifying Pareto
optimality instead of stability as the proper equilibrium makes the roommates prob-
lem economically more meaningful. With this improved equilibrium concept, I have
shown that an equilibrium always exists. Most importantly, I demonstrate how to
improve an ine?cient assignment to an e?cient one if we are not in equilibrium.
For such a natural assignment problem as the roommates problem, this is likely
to have real world applications. Therefore, this paper reframes a classic matching
problem, which previously had no general solution, in a way that is both solvable
and economically more meaningful.
2.7 Appendix
Lemma 4. There are
(2N)!
2
N
(N!)
= (2N ?1)(2N ?3)(2N ?5) (3)(1) many ways to
assign 2N students to be roommates.
Proof. The proof is by induction. When N = 1, the result is trivial as there is only
32
one way to assign two students to be roommates. Assume N > 1 and by induction
there are (2N ?3)(2N ?5) (3)(1) many ways to assign 2(N-1) many students to
be roommates. Select a student s. There are 2N-1 possible roommates for s, and by
assumption, for any roommate we pick, there are (2N ?3)(2N ?5) (3)(1) many
ways to assign the remaining 2N-2 many students. Therefore, there is a total of
[2N ?1] [(2N ?3)(2N ?5) (3)(1)] many ways of assigning roommates.
Lemma 3 There does not exist a strategy-proof mechanism for selecting a
Pareto improvement of an ine?cient assignment.
Proof. Suppose there are four students, a, b, c, and d, and an initial assignment, µ
1
pairing a with b and c with d. Moreover, suppose the student’s preferences are as
follows.
a : c ~ d ~ b
b : c ~ d ~ a
c : b ~ a ~ d
d : b ~ a ~ c
With four students, there are three possible assignment. Note that an assign-
ment is completely determined by who a (or any other student) is assigned to. Let
µ
2
denote the assignment where a is paired with c and µ
3
denote the assignment
where a is paired with d. In our original assignment µ
1
, each person is paired with
their least preferred roommate, so µ
1
is Pareto dominated by both of the other as-
signments. Suppose for contradiction that their exists a strategy-proof mechanism
M for selecting an e?cient, Pareto improving assignment. Note that if a submits the
33
preferences c ~ b ~ d and all other students submit true preferences, then µ
2
is the
only assignment that Pareto improves µ
1
(relative to the submitted preferences). In
such a case, M must select µ
2
. Similarly, if b submits the preferences c ~ a ~ d
and all other students submit true preferences, then M must select µ
3
as it is now
the only Pareto improving assignment. When all students submit true preferences,
M must select either µ
2
or µ
3
. If M selects µ
2
, then b can do better by deviating
and submitting the preferences c ~ a ~ d. If M selects µ
3
, then a can do better by
submitting preferences c ~ b ~ d. Either way, M is not strategy proof which is a
contradiction.
2.7.1 Computational Complexity
The purpose of this section is to demonstrate that the Roommate Swap is a
polynomial time algorithm and therefore implementable. I demonstrate that it is at
worst an O(N
3
) algorithm where N is the number of students.
Each iteration of the algorithm involves the following steps, performed in se-
quence:
1. Induce the graph. This is at worst O(N
2
) as a graph is de?ned by its edges
and there are at most
N(N?1)
2
many edges.
2. Iteratively prune the graph until all blocks are closed under roommates. West
(2001), pg. 157, details an O(N) algorithm for determining blocks. We need to
iterate at most N times as each iteration eliminates at least one student from
each block or stops looking at a block if it is already closed under roommates.
34
Therefore iteratively pruning the graph is at worst O(N
2
).
3. Find an alternating-cycle. This process is O(N). At each step we either travel
to a previously unvisited vertex, which we can do at most N times, or contract
a minimum of two vertices, which we can do at most
N
2
times. So the algorithm
must conclude in at most N +
N
2
steps. As it takes at most N steps to expand
a cycle containing super-vertices to a proper cycle, ?nding an alternating-cycle
concludes in O(N) time.
Therefore each iteration is O(N
2
).
Observation 2. In each iteration of the Roommate Swap, at least one student is
reassigned her top achievable student.
Proof. The search process ends with an alternating-cycle that may or may not con-
tain super-vertices. Dashed edges from standard vertices are chosen to be the ver-
tex’s most preferred student among those who prefer her to their current assignment.
Therefore, if the alternating cycle contains no super-vertices, then half the students
receive their top achievable match. A grey edge from a super-vertex is not necessar-
ily the student’s most preferred achievable student. However, if the alternating-cycle
contains a super-vertex and we need to expand our contractions, then there must
be a last odd-cycle that needs to be expanded.
Figure 6 shows a last cycle with six vertices, but the analysis is the same for
fewer or greater vertices. Our alternating path must go through s
i
and either s
i+1
or s
i+6
. None of these edges involve super-vertices (this is our last expansion) so
35
Figure 2.6: An odd cycle.
s
i?2
s
i?1
s
i
s
i+1
s
i+2
s
i+3
s
i+6
s
i+5
s
i+4
by construction, s
i+1
is s
i
’s top achievable student and s
i
is s
i+6
’s top achievable
choice. Either way, at least one student receives her top achievable choice.
The signi?cance of this is that once a student has been assigned her top achiev-
able choice, neither she nor her roommate can ever be involved in another Pareto
improvement. Therefore we can eliminate them both from consideration. Since
we eliminate at least two students after every iteration, there can be at most
N
2
iterations.
The algorithm performs O(N) many iterations of an O(N
2
) process. Therefore
it is, at worst, O(N
3
).
36
Chapter 3
Externalities in Networks
In network theory, externalities play a critical role in determining which
networks are optimal. Adding links can create positive externalities, as
they potentially make distant vertices closer. On the other hand, links
can result in negative externalities if they increase congestion or add
competition. This paper introduces two new equilibrium concepts and
will completely characterize the set of optimal and equilibrium networks
for a natural class of negative externalities models where an agent’s pay-
o? is a function of the degree of her neighbors. These results are in sharp
contrast to the optimal and equilibrium networks for the standard class
of positive externalities models where payo? is a function of the distance
two agents are apart.
3.1 Introduction
Networks have long been studied in sociology, computer science, physics and
mathematics. However, economists have only recently begun to focus on networks.
This is surprising as graphs are a natural model of many economic situations. Most
people ?nd a job through a network of friends and associates.
1
Similarly, a car
manufacturer does not buy its brakes from a marketplace but rather has long term
relationships with its suppliers.
Fortunately, networks have started to receive the attention they deserve.
2
Whether out of convenience or necessity, virtually all networking papers employ
a reduced form utility function. However, there has been very little attention paid
1
See Granovetter (1973, 1995), Rees (1966), and Montgomery (1991).
2
Jackson (2003) is an excellent survey.
37
to how the choice of utility function a?ects structural predictions. In particular,
there is an interesting feature embedded in a utility function–whether or not ad-
ditional links cause positive or negative externalities to uninvolved vertices. This
paper seeks to show that the choice of underlying utility function and the treatment
of externalities is of critical importance to which networks are optimal.
Jackson and Wolinsky’s seminal paper A Strategic Model of Social and Eco-
nomic Networks [1996, JET], hereafter JW, introduced two reduced form models
and solved for the socially optimal network in each. These models can be described
by the utility an individual gets from a graph.
JW’s Connections Model
u
i
(G) =
j=i
?
d(i,j)
?c ? d
v
i
where 0 ? ? ? 1, d(i, j) is the length of the shortest path between v
i
and v
j
, and
d
v
i
is the number of agents v
i
has an edge with.
JW’s Co-author Model
u
i
(G) =
j:e
i,j
?E(G)
[
1
d
v
i
+
1
d
v
j
+
1
d
v
i
d
v
j
]
The Connections Model has a very nice solution space. If we measure aggregate
utility as the sum of individual utilities, then the socially optimal graph is either
empty, a star, or complete. A star is a network with one central agent involved
in every connection
3
. Moreover, for appropriate link costs, these graphs will be
pairwise stable. The Co-author Model has a much less interesting solution space.
3
See Figure 3.1 on page 45 for an example.
38
For an even number of participants, 2N, the socially optimal graph is simply N
pairs. It is possibly for this reason that the Connections Model (or derivations of
it) appears much more frequently in the subsequent literature.
The star turns out to be optimal for a wide class of models. Bloch and Jackson
(2007) de?ne a utility function to be distance based if there exist c and f such that
u
i
(G) =
j=i
f(d(i, j)) ?c ? d
v
i
where d(i, j) is the number of links in the shortest path between vertices i and j,
f is a nonincreasing function, and c is a cost per link. They demonstrate that the
unique non-trivial e?cient network is the star network. The star formation appears
frequently in the literature under a variety of di?erent utility functions. Given their
result, it is not surprising that the common ingredient among these models is they
are distance based.
The fact that the star is optimal for such a wide class of utility functions makes
a compelling case for it as a real world model. However, there are at least two points
of concern. First, in the star every vertex’s payo? is strictly increasing in the size
of the network, moreover at an increasing rate. Thus, not only do these models
predict the optimal network to be a star but the largest star possible. However,
we expect real-world networks to lose their value and start to break down as they
get too large. Moreover, the entire world organized as a star is clearly not ideal for
any situation. Another concern is that, although star networks are widely predicted
by economic theory, they are not commonly observed in practice. We may observe
star-like networks such as airlines’ hub-and-spoke systems, but I know of no true
39
star networks.
A distance based model is an environment where all externalities must be
positive. If two agents form a link, then they weakly decrease the distance all
other agents are apart and weakly increase the number of other agents they are
connected to. There are at least two important considerations that a model with
only positive externalities does not capture. First, in most networks we expect
there to be congestion issues. This is especially true if we are discussing a computer
network, but congestion also occurs in most economic networks. For example, JW’s
co-authors model is meant to capture that as the number of co-authors you have
increases, you have less time to devote to each one. We would expect the same thing
to occur in a network of friends, a communications network, a network of business
associates, etc. A star should be especially prone to congestion issues as there is a
clear bottleneck, the central node.
A second consideration is that most economic networks involve competition
among agents. In a network of buyers and sellers, an additional link literally means
increased competition. In a network of gamblers exchanging private information
about a horse race, the value of the information decreases with each additional
person who learns the inside tip. When an MBA student talks about networking,
they are referring to contacts to help them get a job. One can imagine it would be
very helpful to have a friend forward your resume to her boss. However, the value
of this is substantially decreased if she also forwards the resume of twenty other
friends.
4
4
Calvo-Armengol and Jackson (2004) captures this e?ect. In their model, when an
40
A natural way of modeling a network where an agent’s payo? is adversely
a?ected by competition or congestion is through a degree based utility model. I will
de?ne a utility function to be degree-based if there exists a ? such that
u
v
(G) =
w?N(v)
?(d
w
)
where ? is non-increasing and d
w
is the number of direct relationships w has
5
. In
this environment, externalities can only be negative. A new connection in a network
weakly increases the degree of each of an agent’s neighbors, so if the agent is not
directly involved with the new link, her payo? must weakly decrease. This paper
will completely characterize the socially optimal and equilibrium set of networks for
degree based utility functions.
First, I will show that the regular network is socially optimal for any degree
based utility function
6
. Next, I will introduce two new equilibrium concepts which
extend the traditional notion of pairwise stability. Under pairwise stability, an agent
is able to biilaterally add an edge or unilaterally drop an edge. Strong pairwise
stability, a natural extension of pairwise stability, allows an agent to both drop an
edge and add another concurrently. Under strong pairwise stability with transfers,
an agent is also able to transfer utility to her immediate neighbors. I will be able to
completely characterize the set of strongly-pairwise-stable networks for any degree
based utility function. Finally, with only a mild assumption on the consistency of
employed agent hears about a job, she randomly picks an unemployed acquaintance to
pass the job to. In this model, edges have negative externalities as an acquaintance
adding a connection decreases the chances you will be randomly chosen in the event you
are unemployed.
5
The notation w ? N(v) will be explained more fully in the section on Graph Theory
terminology, but it means any vertex w that has a direct edge with v.
6
A network is regular if all agents have the same number of connections
41
externalities, I will be able to show that a network is strongly pairwise stable with
transfers if and only if it is the socially optimal regular graph.
These results for degree based utility functions are not only interesting in their
own right but especially as a contrast to the positive externalities environment. If
we use as our metric maximum degree minus minimum degree, then the star and a
regular graph are as di?erent as two graphs can possibly be. It is interesting that two
very natural classes of utility functions can lead to such strikingly di?erent optimal
and equilibrium networks. As such, this should be taken as a note of caution for
researchers using a reduced form utility function to model a social network. The
choice of utility function and more broadly the treatment of externalities in these
networks are of critical importance to the predictions of the model.
As one of the ?rst papers in networks and speci?cally one that characterized
the solution space of two reduced form models, JW has greatly in?uenced the models
in subsequent papers. The solution space for the connections model, the star, is quite
interesting whereas the solution space for the co-authors model is trivial. Possibly for
this reason, most subsequent papers are based roughly on the connections model. As
a result they are positive externalities models. This is unfortunate as most situations
of interest to economists involve competition and thus exhibit negative externalities.
The ?nal contribution of this paper is to propose and solve a negative externalities
model that both has a more interesting solution space than the co-authors model
and is a more natural counterpoint to the connections model.
This paper is closely related to Bloch and Jackson (2007). The two papers,
in conjunction, are able to completely characterize the two most intuitive, general
42
classes of network models. The focus of Bloch and Jackson is on network forma-
tion. They introduce several games in which players make decisions about both
link formation and transfers to other agents in the network. Their paper highlights
the importance of externalities and demonstrates a reasonable way in which agents
might overcome them. The equilibrium concept I introduce, strong pairwise sta-
bility with transfers, is a core concept which complements the network formation
games introduced in their paper.
This paper is most closely related to Jackson and Wolinsky (1996). They
present and solve two reduced form models. Their ?rst model, the connections
model, is a distance based model, while their second, the co-authors model, is es-
sentially a degree based model. Therefore, the results presented here in conjunction
with the results in Bloch and Jackson (2007) can be viewed as a generalization of
JW.
There are at least two other papers, Currarini (2002) and Goyal and Joshi
(2002), that look at externalities in networks; however, both papers take a substan-
tially di?erent modeling approach than this paper. Currarini (2002) focuses on the
partition of vertices into connected components. In Currarini’s model the value of
a network depends only on this partition. Externalities are de?ned by whether the
value of a network increases or decreases when the partition becomes ?ner. The
network matters in that it determines the partition, but in Currarini’s framework
the role of network architecture is minimized. Goyal and Joshi’s (2002) approach
is more similar to this paper but still substantially di?erent. They examine two
interesting models where agents have varying degrees in equilibrium. The focus of
43
their paper is how di?ering degrees a?ect agent payo?. Externalities, in the form of
whether or not agents are strategic substitutes or compliments, end up being crucial
to solving their models, but their two games are not an attempt to actually model
externalities. In fact, strategic complementarities are de?ned speci?cally in terms of
the particular payo? function they use and their concept is not readily generalizable.
In contrast, this paper’s primary aim is to model network externalities in as general
a way as possible without diminishing the role of network architecture.
The remainder of this article is organized as follows. Section 2 provides a brief
overview of graph theory terminology. Section 3 introduces degree based utility
functions and completely characterizes the socially optimal and equilibrium networks
for any degree based utility function. Section 4 introduces and solves a speci?c
reduced form utility function. Section 5 concludes, and the Appendix provides
complete proofs.
3.2 Graph Theory Terminology
This paper uses no theoretical results from graph theory, but I will borrow
from its terminology to facilitate discussion. I will represent a network as a graph
where vertices represent agents and an edge represents a relationship between the
two agents. All edges are undirected.
The following are some de?nitions with corresponding notation:
• E(G) is the set of edges in a graph G. e
u,v
? E(G) is an edge between vertices
u and v.
44
• V(G) is the set of vertices in G.
• u and v are adjacent if e
u,v
? E(G). u ?v indicates u and v are adjacent.
• The neighborhood of v is the set of vertices adjacent to v. Symbolically, N(v) =
¦u ? V (G)[e
u,v
? E(G)¦.
• The degree of v is the number of vertices v is adjacent to. Symbolically,
d
v
= [N(v)[.
• G is complete if all vertices are adjacent.
• A star is a graph with one center vertex, in which all remaining vertices are
adjacent only to the center.
Figure 3.1: A complete graph and a star.
• A path between u and v is a set of edges
e
v
1
,v
2
, e
v
2
,v
3
, e
v
3
,v
4
, . . . , e
v
n?1
,vn
such
that v
1
= u and v
n
= v.
• u and v are connected if there exists a path between them. The components of a
graph are its maximal connected subgraphs. Note that the connection relation
45
is transitive, symmetric, and re?exive, so it is an equivalence relation. The
equivalence classes of the connection relation are the connected components.
This paper assumes the number of vertices are ?xed. Therefore, a graph is
completely characterized by its set of edges. As a result, I will slightly abuse notation
and use G and E(G) interchangeably. For example, G?e
u,v
represents the new graph
created by adding an edge between u and v.
3.3 Degree Based Utility Functions
In this section I will introduce a class of models which is a natural counterpoint
to the more widely studied distance based models. A utility function is degree-based
if there exists a ? such that
u
v
(G) =
w?N(v)
?(d
w
)
. A particularly desirable feature of degree based utility models is that they are
interesting even when links are costless to form. For any positive externalities model,
if links are costless then the complete network must be socially optimal as adding
links can not harm the agents but may help them. As a result, positive externalities
models are only interesting to study when links are costly. However, there are
situations where incurring a cost for a link does not have a clear interpretation. For
example, it is not clear how an agent incurs a cost that is completely separate from
the bene?t of having a friendship. Time spent maintaining a business relationship or
even expenses incurred “wining and dining” a potential partner might reasonably be
considered costs, but it is di?cult to apply this to a model of personal relationships.
46
After all, having someone to spend time with and someone to go to costly activities
such as dinners or baseball games are some of the bene?ts, not costs, of having a
friend. Therefore, it is particularly attractive that we do not need separate costs for
links in order to make a degree-based utility function nontrivial.
The star does not perform as well with a rival utility function. The perimeter
vertices only get utility from their immediate neighbor, the center of the star. How-
ever, the center is connected to so many vertices (the maximum possible) that its
value has decreased. Moreover, we do not expect the star to be an equilibrium of a
network game as two perimeter vertices would do better by dropping their connec-
tion to the center agent and forming a link to each other. In this environment, a
more symmetric graph does better socially and is more likely to be pairwise stable.
A regular graph, where all agents have the same number of connections, is the nat-
ural place to look. Unfortunately, regular graphs do not always exist.
7
However, a
regular graph always exists when there is an even number of vertices. I will de?ne
a new class of graphs which exist regardless of the parity of the number of agents.
De?nition 6. Let d = max ¦d(v) : v ? V (G)¦ and d = min ¦d(v) : v ? V (G)¦.
Then:
1. A graph is nearly-regular if (d ?d) ? 1.
2. A graph is nearly-n-regular if (n ?1) ? d ? d ? n.
7
For example, if we have an odd number of vertices, we can not have a (2a +1)-regular
graph. Since every edge contributes two to the sum of all vertex degrees, the total sum of
degrees must be even. An odd-regular graph with an odd number of vertices would have
an odd total degree sum which is not possible.
47
The next proposition completely characterizes the set of socially optimal net-
works when there is an even number of vertices. I will be able to simplify this
characterization once I impose a mild assumption on the consistency of externali-
ties.
Proposition 5. Suppose there is an even number of agents. A network G is socially
optimal if and only if for every vertex v, d
v
? arg max x?(x). In particular, for any
n ? arg max x?(x), all n-regular graphs are socially optimal.
Proof. Each agent receives a payo? from her neighbors and contributes utility to
her neighbors. As an accounting identity, the sum of what every agent receives must
equal the sum of what every agent contributes. In particular
U(G) =
N
i=1
u
i
(G) =
N
i=1
v
j
?N(v
i
)
?(d
v
j
) =
N
i=1
d
v
i
?(d
v
i
) (3.1)
Let n ? arg max x?(x). Since we have an even number of vertices, an n-regular
graph exists
8
. Pick any n-regular graph H. By Equation 3.1, H must be socially
optimal. Moreover, if J is a network with a vertex v such that d
v
,? arg max x?(x),
then U(J) < U(H).
8
To see this, label the vertices 0 through [V (G)[ ?1. If n is even, then connect vertex
i to vertices i ±jmod([V (G)[), for 1 ? j ?
n
2
. If n is odd, then connect vertex i to vertex
i +
|V (G)|
2
mod([V (G)[) and to vertices i ±jmod([V (G)[), for 1 ? j ?
n?1
2
48
3.3.1 Pairwise Stability
Pairwise stability is the standard equilibrium concept in Network Theory. In-
tuitively, it says no agent wishes to unilaterally drop one of her connections, and no
two agents wish to bilaterally add a connection. More formally:
De?nition 7. A graph G is pairwise stable if:
1. If e
i,v
? E(G), then u
i
(G) > u
i
(G?e
i,v
) and u
j
(G) > u
j
(G?e
i,v
).
2. If e
i,v
,? E(G), then either u
i
(G) > u
i
(G +e
i,v
) or u
j
(G) > u
j
(G +e
i,v
).
So far in this section we have assumed that links are costless. However, we
must add link costs in order to make pairwise stability interesting. Otherwise, as
long as ? is strictly positive, the only pairwise stable graph is the complete graph.
For the remainder of this subsection, I will assume u
v
(G) =
w?N(v)
?(d
w
) ?c d
v
.
Moreover, to avoid any nuisances, I will assume c ,= ?
for any n ? N. Thisassumption is without loss of generality since one can perturb c by an arbitrarily
small .
This next structure appears several times so I will explicitly de?ne it.
De?nition 8. G is a maximal nearly-n-regular graph if it is nearly n regular
and there does not exist a nearly-n-regular graph G
such that E(G) ? E(G
).
Proposition 6. Let n = max ¦x ? N[?(x) > c¦. If utility is rival, then all maximal
nearly-n-regular graphs are pairwise stable.
Proof. Let G be any maximal nearly-n-regular graph. Look at any vertices u and v
such that e
u,v
/ ? E(G). The maximality of G implies at least one u or v must have
49
Figure 3.2: An undesirable pairwise stable graph
u
u u
u
uu
d
d
d
d
d
d
d
degree n. Without loss of generality, assume d
v
= n. Then u
i
(G + e
u,v
) ? u
i
(G) =
?(n + 1) ? c < 0 by the maximality of n. Similarly, look at any vertices u and v
such that e
u,v
? E(G). u
i
(G) ?u
i
(G?e
u,v
) ? ?
?c ? 0. Therefore G is pairwisestable.
Pairwise stability is a fairly weak concept. Pairwise stability only allows a
vertex to unilaterally drop a connection or to bilaterally add a connection, but not
both. For example, if max ¦x ? N[?(x) ? c¦ = 3, then the graph in Figure 3.2 is
pairwise stable since u will be unwilling to add an edge with any vertex that already
has degree 3. However, this is unsatisfying as any of the vertices in the 4-clique
would be happy to exchange one of their edges for an edge with u. Similarly, as long
as the vertex is willing to drop one of her edges, u would be happy to form an edge
with any vertex in the 4-clique. This leads to a new solution concept.
De?nition 9. A graph G is Strongly Pairwise Stable if
1. G is pairwise stable
2. There does not exist a u, v, w ? V (g) such that u
u
(G
) > u
u
(G) and u
v
(G
) >
u
v
(G) where G
= G +e
u,v
?e
v,w
.
50
With this stronger solution concept, we are able to completely characterize
the set of strongly pairwise stable graphs.
Proposition 7. Let n = max ¦x ? N[?(x) > c¦ and suppose ? is strictly decreasing.
Then G is strongly pairwise stable if and only if G is a maximal nearly-n-regular
graph.
Proof. It is straightforward to verify that a maximal nearly-n-regular graph is strongly
pairwise stable. To prove the other direction, look at any strongly pairwise stable
graph G. First note that max ¦d
v
[v ? V (G)¦ = n since otherwise G would not be
pairwise stable.
9
Suppose for contradiction that G is not nearly-regular. Then
there exists a u and v such that d
v
? d
u
? 2. Let w ? N(v) ¸ N(u) ,= ? and let
G
= G +¦e
u,w
¦ ?¦e
v,w
¦. Note that u
w
(G
) > u
w
(G) since d
u
+ 1 < d
v
. Moreover,
u
u
(G
) > u
u
(G) since d
w
? n and ?
> c. Therefore G is not strongly pairwisestable, a contradiction. Since G has max degree n and is nearly-regular, it must be
nearly-n-regular. If G is not maximal, then there are two non-adjacent vertices of
degree n-1 and therefore G is not pairwise stable.
3.3.2 Equilibrium with Transfers
In this section I will introduce a new core concept which generalizes pairwise
stability to allow agents to make transfers. This complements the games introduced
in Block and Jackson (2007). They de?ne several new network games which extend
9
If the maximum degree is greater then n, some vertex would want to drop an edge.
If the max degree is less then n, any unconnected vertices would be better o? adding an
edge.
51
the traditional network games to allow players to make ?nancial transfers. In their
paper they make a distinction between who an agent is able to make a transfer to and
on what an agent is able to condition this transfer payment. In the direct transfer
game, an agent can only make a transfer for a link she is directly involved with. In
the indirect transfer games she can only make demands on her own relationships,
but she is free to subsidize any relationship. In their standard game, a transfer is
conditional only on a link forming, but in their game with contingent transfers, an
agent can condition a payment on the entire network structure.
Transfers are a natural concept in a social network. We often see situations
where maintaining the relationship is more important to one of the agents than the
other. In the business world, one person may be in a position of greater power
or may simply have more connections than the other. In the academic world, the
marginal value of publishing an article should decrease with the total number of
publications an author has. Therefore, even if two co-authors are equally talented,
the relationship should be relatively more valuable to the person with fewer publica-
tions. In such a situation, it is natural for a transfer to occur. The person to whom
the relationship is more valuable will have the incentive to put forth more e?ort into
the project or else might agree to do the less desirable aspects of the work.
I propose a new core concept which generalizes pairwise stability to allow
agents to make transfers to the people they have a relationship with. I only allow
direct transfers as I ?nd indirect transfers much less natural. A transfer between
two agents with a relationship can be non-pecuniary; however, there is less ?exibility
when the transfer is between two agents who are not linked. It is hard to interpret
52
an indirect transfer as anything other that a monetary payment. In some situations
this may be perfectly natural, but especially with social networks, direct monetary
transfers occur infrequently. An academic can do many things to either ease the
burden on her coauthor or make the relationship more valuable, but it would be
strange for her to pay an academic to not collaborate with any of her coauthors.
Despite this restriction, we will still be able to reach some powerful conclusions.
More formally, the game consists of a graph G and a matrix of transfers T.
In the transfer matrix, t
ij
represents the transfer from agent i to agent j. An agent
can only make a transfer to someone she has a direct relationship with. Therefore,
t
ij
> 0 only if e
ij
? G. To avoid ambiguity, I will require that t
ij
= ?t
ji
as we care
only about the net transfer.
Therefore, given a network G and transfers T, agent i receives a payo? of
?
i
(G, T) =
v
j
?N(v
i
)
[?(d
v
j
) +t
ji
] (3.2)
Individually, an agent should be able to drop any of her edges and change
the transfers she o?ers. Two agents should also be able to form a link if they so
desire. Anytime an agent changes her edges or transfers, she alters the payo? of her
neighbors and, therefore, potentially jeopardizes these relationships. However, if two
agents are able to move bilaterally to establish a mutually bene?cial relationship and
to adjust their transfers so that all of their neighbors are better o?, then they do
not jeopardize these relationships and surely the network is in disequilibrium.
De?nition 10. Given a network G with transfers T, agent v
i
blocks < G, T > if
53
there exists an agent v
j
10
, subsets A ? N(v
i
), B ? N(v
j
), and transfers T
on the
set ¦v
i
, v
j
, N(v
i
) ¸ A, N(v
j
) ¸ B¦ such that:
?
x
(G
, T +T
) > ?
x
(G, T)
for every x ? ¦v
i
, v
j
, N(v
i
) ¸ A, N(v
j
) ¸ B¦ where G
= G ? e
i,j
¸ ¦e
i,k
: k ? A¦ ¸
¦e
j,k
: k ? B¦.
This de?nition is purely a generalization of strong pairwise stability. An agent
can drop any edge, add an edge (as long as the other agent wishes to as well), or
do both simultaneously. If the agent is also able to compensate all the agents she
remains in a relationship with so that they are made better o? by the change, then
surely we are in disequilibrium.
De?nition 11. A network G is strongly pairwise stable with transfers if there
exists transfers T such that no agent blocks < G, T >. In such a case, we say the
transfers T support G.
When it is clear from context that it is a network with transfers, I will just
say strongly pairwise stable instead of strongly pairwise stable with transfers. With
a mild regularity assumption on externalities, I will prove that the only network
that is strongly pairwise stable with transfers is the socially optimal, nearly-regular
network.
Whenever an edge is added to an network, there is a social trade o?. There is a
direct bene?t to the two agents forming the relationship but at a cost of a decreased
10
We allow v
j
= ? in which case we interpret G? e
i,j
= G.
54
payo? to all the agents they already share an edge with. This trade-o? is captured
by the function:
to(x) = ?(x + 1) ?x(?(x) ??(x + 1)), 1 ? x ? [V (G)[ ?2
When an agent with degree x forms a new edge, she is contributing ?(x + 1) to
the new neighbor but at a cost of ?(x) ? ?(x + 1) to the x many agents she was
previously connected to. This motivates a regularity condition on externalities.
De?nition 12. The externalities in a network are consistent if to(x) is decreasing.
De?nition 13. Externalities are weakly consistent if any of the following condi-
tions hold:
1. to(x) > 0.
2. to(x) < 0.
3. There exists a integer M such that to(x) ? 0 for every x ? M and to(x) < 0
for every x > M.
For each respective case, we de?ne the threshold of to(x) to be:
1. [V (G)[ ?1
2. 1
3. M
to(x) is decreasing if ?(x) ??(x + 1) is increasing. Therefore, if ? is concave,
then externalities are consistent. However, this condition is much weaker than
concavity. Of course, if externalities are consistent then they are weakly consistent.
55
I will assume that if to(x) is weakly consistent with threshold M with 1 < M <
[V (G)[ ?1, then to(M) = 0. This does not change the results in any signi?cant way,
but it does make the proofs cleaner. Moreover, if to(M) ,= 0, then we can replace
?(x) by ?
(x) where ?
(x) = ?(x) ?to(M). Now:
to
?
= ?
(x + 1) ?x(?
(x) ??
(x + 1))
= ?(x + 1) ?to(M) ?x(?(x) ?to(M) ??(x + 1) +to(M))
= to
?
(x) ?to(M)
and therefore to
?
(M) = 0.
With this mild assumption on externalities, we can completely classify the set
of socially optimal networks. In a surprising result, once agents are able to make
transfers to their neighbors, these networks will also be the only strongly pairwise
stable networks.
Proposition 8. Suppose externalities are weakly consistent.
1. When 1 < M < [V (G)[ ? 1, then G is socially optimal if and only if G is
nearly-(M+1)-regular.
2. When M = [V (G)[?1, then the complete network is the unique socially optimal
network.
3. When M = 1, then the unique socially optimal network is the trivial network
11
.
11
The trivial network consists of
|V (G)|
2
many pairs if [V (G)[ is even and
|V (G)?3|
2
many
pairs plus the three remaining vertices connected as a path if [V (G)[ is odd. See Figure
3.3 on page 66 for an example.
56
I will prove Proposition 8.1 here. The remaining cases, which are more tech-
nical, are proved in the Appendix.
Proof. We know from the previous section that G is optimal if and only if every
vertex has degree from the argmaxx?(x). Note that
to(x) = ?(x + 1) ?x(?(x) ??(x + 1))
= (x + 1)?(x + 1) ?x?(x)
and therefore
2?i?x
to(i ?1) =
2?i?x
[i?(i) ?(i ?1)?(i ?1)]
= x?(x) ??(1)
since
2?i?x
[i?(i) ?(i ?1)?(i ?1)] is a telescoping series. In particular,
x?(x) = [
2?i?x
to(i ?1)] +?(1) (3.3)
Since, to(x) ? 0 for every x ? M and to(x) < 0 for every x > M, x?(x) is maximized
at x = M + 1. Note that
(M + 1)?(M + 1) = [
2?i?(M+1)
to(i ?1)] +?(1)
= to(M) + [
2?i?(M)
to(i ?1)] +?(1)
= 0 + [
2?i?(M)
to(i ?1)] +?(1)
= M?(M)
Where the second to last equality follows from our assumption that to(M) = 0.
Since to(x) ,= 0 for every x ,= M, argmax(to(x)) = ¦M, M + 1¦. As mentioned
57
previously, a nearly regular graph always exists. Therefore, a network is optimal if
and only if it is nearly-(M+1)-regular.
I will now prove the main theorem of this section.
Proposition 9. Suppose externalities are weakly consistent.
1. When 1 < M < [V (G)[ ?1, G is strongly pairwise stable with transfers if an
only if G is nearly-(M+1)-regular.
2. When M = [V (G)[ ? 1, the complete network is the unique network that is
strongly pairwise stable with transfers.
3. When M = 1, the unique network that is strongly pairwise stable with transfers
is the trivial network.
This proposition is proved with a sequence of lemmas. Complete proofs are
given in the Appendix, but I will list the lemmas and give the intuition to the proof
here.
Lemma 5. Suppose 1 < M < [V (g)[ ? 1 and let G be strongly pairwise stable. If
there exists a vertex u with degree less than M, then u is adjacent to every vertex
with degree less than or equal to M.
Intuition. If there are two non-adjacent agents with degree less than the thresh-
old, then adding an edge is socially bene?cial as the trade-o? for both agents is posi-
tive. Moreover, all the social gains are realized by the two agents. Since it is socially
58
bene?cial, they bene?t enough to be able to compensate all of their neighbors and
still improve their payo?.
Lemma 6. Suppose 1 < M < [V (g)[ ? 1 and let G be strongly pairwise stable. If
there exists a vertex u with degree greater than M +1, then u is not adjacent to any
vertex with degree greater than or equal to M + 1.
Intuition. It is socially bene?cial for the two agents with degree greater than
the threshold to cut their relationship. Their neighbors, who receive all the bene?t
from the two agents cutting an edge, are willing and able to increase their transfers
by enough to make it in u or v’s best interest to cut the edge. We have to be a little
more careful than in Lemma 5 since there may be transfers between the two agents
which would a?ect their willingness to drop the edge.
Lemma 7. Suppose T supports a network G. Then for every two agents i and j
such that e
i,v
? G,
t
ij
? ?(d
j
) ?(d
i
?1)(?(d
i
?1) ??(d
i
))
Proof. v
i
has d
i
?1 many neighbors who would be willing to pay up to ?(d
i
?1)??(d
i
)
for i to sever her relationship with j. i receives a bene?t of ?(d
j
) ? t
i
, j from her
relationship with j, so if ?(d
j
) ?t
ij
< (d
i
?1)(?(d
i
?1) ??(d
i
)) then i and all her
remaining neighbors do strictly better if i drops her relationship with j and accepts
a transfer of ?(d
i
?1) ??(d
i
) ? from each of her remaining neighbors.
Lemma 8. Suppose 1 < M < [V (g)[ ? 1 and let G be strongly pairwise stable. If
there exists a vertex u with d
u
> M + 1, then all of u’s neighbors are adjacent.
59
Intuition. If there is an agent u such that d
u
> M + 1, v, w ? N(u), but
e
vw
,? G, then v and w are better o? dropping their edges with u and creating
an edge between themselves. They do not need to compensate their neighbors for
such a move as their degree has not changed. We know from Lemma 6 that d
v
and
d
w
are both less than M + 1, so, both v and w are made better o? as they each
have degree less than u. The only thing we have to be careful about is that u may
be subsidizing her relationship with either or both of the agents, and when they
sever the relationship with u they forgo the subsidy. Lemma 7 sets a bound on the
transfer from u to v or w that ensures it will always be in v and w’s best interest to
forgo the transfer and establish a relationship with each other.
Lemma 9. Suppose 1 < M < [V (g)[ ?1 and let G be strongly pairwise stable. No
vertex in G has degree greater than M + 1.
Intuition. This is a pigeonhole argument. Suppose for contradiction there is a
vertex u with d
u
> M +1. By Lemma 6, every neighbor of u must have degree less
than or equal to M. By Lemma 8, all neighbors of u must be adjacent. However,
there are at least M + 1 neighbors of u. All are adjacent to the other neighbors of
u (there are at least M other neighbors of u) plus u itself. Therefore, all neighbors
of u must have degree at least M + 1, a contradiction.
Lemma 10. Suppose 1 < M < [V (g)[ ?1 and let G be socially optimal. No vertex
in G has degree less than M.
Intuition. If there exists a vertex u with d
u
< M, we know from Lemma 5
that u must be adjacent to all vertices with degree less than or equal to M. We can
60
establish that there must be two vertices, v and w that are adjacent to each other,
but neither of which are adjacent to u. Either of these agents would be better o?
dropping the edge with the other and instead establishing an edge with u. Moreover,
this will be socially bene?cial as both v and w must have degree M +1 and socially
we are indi?erent whether or not they are adjacent. However, since d
u
< M, we
strictly prefer that u create a new relationship. Since this switch is socially bene?cial
and all the gains are realized by u and the vertex that switches, they will be able to
compensate u’s neighbors for their decreased payo?. Again, we have to be careful
about transfers between v and w, but only one can be receiving a positive transfer
from the other.
Lemma 11. Suppose 1 < M < [V (g)[ ?1. If G is nearly-(M+1)-regular, then G is
strongly pairwise stable with transfers.
Proof. Let G be any nearly-(M+1)-regular graph. De?ne a set of transfers T by:
t
uv
=
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0 d
u
= d
v
?(M) ??(M + 1) d
u
= (M + 1), d
v
= M
?(M + 1) ??(M) d
u
= M, d
v
= M + 1
Every agent with degree M receives a total payo? of M?(M) and every agent with
degree M + 1 receives a payo? of (M + 1)?(M + 1). Since to(M) = 0, M?(M) =
(M + 1)?(M + 1).
A nearly-(M+1)-regular graph is optimal, so adding an edge cannot increase
social payo?. Since all the bene?ts are captured by the two agents adding an edge
and all costs are incurred by their neighbors, it is not possible for the two agents
61
adding the edge to make all their neighbors better o?. Similarly, an agent u has
no wish to delete one of her edges. u’s remaining neighbors receive all the bene?t,
while u incurs all the costs. Since the costs are greater than or equal to the bene?ts
(the original graph was socially optimal), u’s remaining neighbors will not be able
to compensate u so that all are better o?. Finally, two vertices u and v can not do
better by each dropping an edge and creating an edge with each other. The new
relationship is worth at most ?(M) which is exactly what they received from their
previous relationship.
Lemma 9 and Lemma 10 establishes the nearly-(M+1)-regularity is necessary
for strong pairwise stability with transfers. Lemma 11 establishes that being nearly-
(M+1)-regular is su?cient as well. This is a surprising and powerful result. In a
network of relationships, an agent should be able to sever any ties it chooses and
establish new ties when it is mutually desirable. Moreover, there should always
be informal ways an agent can exert e?ort that is costly for herself but makes the
relationship more bene?cial for a partner. My result establishes that if this is case,
then the only network which will be an equilibrium is the socially optimal network.
3.4 A Reduced Form Utility Model
A particular degree based utility function of interest is:
u
i
(G) = w
i
+
i?j
?
dv
j
w
i,j
?
i?j
c
i,j
, where 0 ? ? ? 1. (3.4)
62
Recall JW’s Connections Model is:
u
i
(G) = w
i
+
j=i
?
t
i,j
w
i,j
?
i?j
c
i,j
where t
i,j
is the length of the shortest path between v
i
and v
j
.
As mentioned before, the Connections Model has only positive externalities.
The co-authors model is the negative externalities model JW examine, but the
utility function presented in Equation 3.4 is a more natural negative externalities
counterpoint to the connections model. A vertex only gets utility from its neighbors,
and this utility is a decreasing function of each neighbor’s degree. This also ?ts
JW’s motivation for the co-authors model. The bene?t to working with a colleague
is decreasing in the number of co-authors she has as she will have less time to devote
to your project.
With our results from Section 3, we can quickly solve for the symmetric version
of Equation 3.4. Let
u
i
(G) =
i?j
?
dv
j
(3.5)
where 0 < ? < 1. Further, suppose ? =
?
?+1
for some integer ?.
By assumption:
to(x) = (x + 1)?
x+1
?x?
x
= ?
x
((x + 1)? ?x)
= ?
x
(x(? ?1) + 1)
which is a decreasing function of x. Moreover
to(?) = ?
?
((? + 1)? ??)
63
= ?
?
((? + 1)
?
? + 1
??)
= ?
?
((? ??)
= 0
Therefore all the assumptions of Proposition 3 on page 58 are met.
Proposition 10. Suppose u
i
(G) =
i?j
?
dv
j
. Then
1. G is socially optimal if and only if G is nearly-(? + 1)-regular.
2. G is strongly pairwise stable with transfers if and only if G is nearly-(? + 1)-
regular.
3.5 Conclusion
Distance based and degree based models are the two most intuitive models of
an agent’s payo? from a network. While much attention has been paid to distance
based models, very little has been paid to degree based models. This paper com-
pletely characterizes the set of optimal and stable networks for this natural class
of utility functions. The predicted networks are interesting in their own right but
especially so when taken in contrast to the optimal networks for distance based mod-
els. It is striking that two intuitive models can lead to such dramatically di?erent
predictions. In particular, this paper, taken in conjunction with the results from
Bloch and Jackson (2007), provides a generalization and simpli?cation of results in
the classic networks paper by Jackson and Wolinsky (1996).
64
3.6 Appendix - Proofs
The trivial network consists of
|V (G)|
2
many pairs if [V (G)[ is even and
|V (G)?3|
2
many pairs plus the three remaining vertices connected as a path if [V (G)[ is odd.
Proposition 8. Suppose externalities are weakly consistent.
1. When 1 < M < [V (G)[ ? 1, then G is socially optimal if an only if G is
nearly-(M+1)-regular.
2. When M = [V (G)[ ? 1, then the complete network is the unique socially
optimal network.
3. When M = 1, then the unique socially optimal network is the trivial network.
Proof. Proposition 8.2 Let G be any graph that contains two non-adjacent vertices
u and v, and suppose the threshold is [V (G)[ ?1. By the de?nition of the threshold,
to(x) > 0. Therefore,
U(G? e
u,v
) ?U(G) = (d
u
+ 1)?(d
u
+ 1) ?d
u
?(d
u
) + (d
v
+ 1)?(d
v
+ 1) ?d
v
?(d
v
)
= to(d
u
) +to(d
v
)
> 0
and G can not be optimal. Therefore, the only optimal network is one where all
vertices are adjacent.
Proposition 8.3 We know from Equation 3.1 on page 48 that
U(G) =
N
i=1
d
v
i
?(d
v
i
)
65
Figure 3.3: Trivial graph for an even and odd number of vertices.
1 2 3 4
5 6 7 8
1 2 3 4
5 6 7 8
9
and from Equation 3.3 on page 57 that
x?(x) = [
2?i?x
to(i ?1)] +?(1)
Since to(x) < 0 for every x > 0, x?(x) is strictly decreasing for x ? 1.
Therefore, if a 1-regular graph exists, it must be optimal. A 1-regular graph exists
when there is an even number of vertices (the trivial graph), but does not when the
number of vertices is odd. Since 2?(2) > 0, the trivial graph must be optimal when
there is an odd number of agents.
Lemma 5. Suppose 1 < M < [V (g)[?1 and let G be strongly pairwise stable.
If there exists a vertex u with degree less than M, then u is adjacent to every vertex
with degree less than or equal to M.
Proof. Suppose for contradiction that G is supported by transfers T and has two
non-adjacent vertices u and v with d
u
< M and d
v
? M. Let
t
vx
=
?
?
?
?
?
?
?
?(d
v
) ??(d
v
+ 1) + x ? N(v)
?(d
u
+ 1) ??(d
v
+ 1) x = u
t
ux
=
?
?
?
?
?
?
?
?(d
u
) ??(d
u
+ 1) + x ? N(u)
?(d
v
+ 1) ??(d
u
+ 1) x = v
66
Then
??
u
(G? e
i,j
, T +T
) = ?(d
v
+ 1) +t
vu
?
w?N
G
(u)
t
uw
= ?(d
v
+ 1) + [?(d
u
+ 1) ??(d
v
+ 1)] +d
u
(?(d
u
+ 1) ??(d
u
) ?)
= ?(d
u
+ 1) ?d
u
(?(d
u
) ??(d
u
+ 1)) ?d
u
? )
= to(d
u
) ?d
u
?
> 0
for su?ciently small.
For x ? N
G
(u)
??
x
(G? e
i,j
, T +T
) = ?(d
u
+ 1) ??(d
u
) +t
ux
= ?(d
u
+ 1) ??(d
u
) +?(d
u
) ??(d
u
+ 1) +
=
> 0
Similarly, ?
v
(G?e
i,j
, T +T
)??
v
(G, T) > 0 and ?
x
(G?e
i,j
, T +T
)??
u
(G, T) >
0 for every x ? N
G
(v). Therefore, u and v block < G, T >, contradicting the
assumption that T supports G.
Lemma 6. Suppose 1 < M < [V (g)[?1 and let G be strongly pairwise stable.
If there exists a vertex u with degree greater than M + 1, then u is not adjacent to
any vertex with degree greater than or equal to M + 1.
Proof. Suppose for contradiction that G is supported by transfers T and has two
adjacent vertices u and v with d
u
> M + 1 and d
v
? M + 1. Let r
xu
= ?(d
u
?
67
1) ? ?(d
u
) ? for every x ? N(v) ¸ u. In other words, each neighbor of u gives u
?(d
u
?1)??(d
u
)?. Similarly, let s
vx
= ?(d
v
)??(d
v
?1)+ for every x ? N(u)¸v.
Then if u drops its edge with v in order to receive transfers R, it loses the
bene?t from v, ?(d
v
), no longer makes the transfer t
u,v
, and gains the transfers R
from each of its remaining neighbors. Speci?cally,
??
u
(G¸ e
uv
, T +R) = ??(d
v
) +t
uv
+ (d
u
?1)(?(d
u
?1) ??(d
u
) ?)
Similarly,
??
v
(G¸ e
uv
, T +S) = ??(d
u
) +t
vu
+ (d
v
?1)(?(d
v
?1) ??(d
v
) ?)
Adding these two equations yields
??
u
(G¸ e
uv
, T +R) + ??
v
(G¸ e
uv
, T +S) =
?to(d
v
?1) ?to(d
u
?1) +t
uv
+t
vu
?(d
u
+d
v
?2) =
?to(d
v
?1) ?to(d
u
?1) ?(d
u
+d
v
?2) > 0
for su?ciently small . The ?rst equality comes from rearranging terms. The second
equality follows since t
uv
= ?t
vu
by de?nition. The ?nal inequality follows since
d
u
? 1 > M and d
v
? 1 ? M, so by the de?nition of the threshold, ?(d
u
? 1) < 0
and ?(d
v
?1) ? 0. But, since ??
u
(G¸ e
uv
, T +R) +??
v
(G¸ e
uv
, T +S) > 0, either
??
u
(G¸ e
uv
, T +R) > 0 or ??
v
(G¸ e
uv
, T +S) > 0.
By construction, ?
x
(G¸ e
uv
, T +R) ??
x
(G, T) > 0 for every x ? N(u) ¸ v and
?
x
(G¸ e
uv
, T +S) ??
x
(G, T) > 0 for every x ? N(v) ¸ u. Since
[?
u
(G¸ e
uv
, T +R) ??
u
(G, T)] + [?
v
(G¸ e
uv
, T +S) ??
v
(G, T)] > 0
68
at least one of [?
u
(G¸e
uv
, T +R)??
u
(G, T) > 0 or ?
v
(G¸e
uv
, T +S)??
v
(G, T) > 0.
Whichever one is greater than zero blocks G, a contradiction.
In equilibrium, there is a limit to how much an agent is willing to transfer
another agent.
Lemma 7. Suppose T supports a network G. Then for every two agents i
and j such that e
i,v
? G,
t
ij
? ?(d
j
) ?(d
i
?1)(?(d
i
?1) ??(d
i
))
.
Proof. v
i
has d
i
?1 many neighbors who would be willing to pay up to ?(d
i
?1)??(d
i
)
for i to sever her relationship with j. i receives a bene?t of ?(d
j
) ? t
i
, j from her
relationship with j, so if ?(d
j
) ?t
ij
< (d
i
?1)(?(d
i
?1) ??(d
i
)) then i and all her
remaining neighbors do strictly better if i drops her relationship with j and accepts
a transfer of ?(d
i
?1) ??(d
i
) ? from each of her remaining neighbors.
Lemma 8. Suppose 1 < M < [V (g)[ ? 1 and let G be strongly pairwise
stable. If there exists a vertex u with d
u
> M + 1, then all of u’s neighbors are
adjacent.
Proof. Suppose not, and let u be such that d
u
> M + 1, v, w ? N(u), but e
vw
,? G.
We know from Lemma 6 that d
v
, d
w
? M. Since v and w are not adjacent, we know
from Lemma 5 that neither v nor w has degree less than M. Therefore, d
v
= d
w
= M.
From Lemma 7
t
uv
? ?(d
v
) ?(d
u
?1)(?(d
u
?1) ??(d
u
))
69
= ?(d
v
) ??(d
u
) +?(d
u
) ?(d
u
?1)(?(d
u
?1) ??(d
u
))
= ?(M) ??(d
u
) +to(d
u
?1)
Similarly, t
uw
? ?(M) ??(d
u
) +to(d
u
?1). Therefore
??
v
(G +e
vw
¸ ¦e
uv
, e
uw
¦ , T) = ?(d
w
) ??(d
u
) ?t
uv
= ?(M) ??(d
u
) ?t
uv
? ?(M) ??(d
u
) ?(?(M) ??(d
u
) +to(d
u
?1))
= ?to(d
u
?1)
> 0
where the last inequality follows from d
u
> M + 1 and therefore, to(d
u
?1) < 0.
Similarly, ??
w
(G + e
vw
¸ ¦e
uv
, e
uw
¦ , T) > 0. Note that since the degree of
v and w has not changed, all vertices in N(v) ? N(w) ¸ u are indi?erent between
< G+e
vw
¸¦e
uv
, e
uw
¦ , T > and < G, T >. Therefore agents v and w block < G, T >
contradicting the stability of G.
Lemma 9. Suppose 1 < M < [V (g)[?1 and let G be strongly pairwise stable.
No vertex in G has degree greater than M + 1.
Proof. This is a pigeonhole argument. Suppose for contradiction there is a vertex u
with d
u
> M + 1. By Lemma 6, every neighbor of u must have degree less than or
equal to M. By Lemma 8, all neighbors of u must be adjacent. However, there are
at least M + 1 neighbors of u. All are adjacent to the other neighbors of u (there
70
are at least M other neighbors of u) plus u itself. Therefore, all neighbors of u must
have degree at least M + 1, a contradiction.
Lemma 10. Suppose 1 < M < [V (g)[ ?1 and let G be socially optimal. No
vertex in G has degree less than M.
Proof. Suppose for contradiction there exists a vertex u with d
u
< M. Since M <
[V (G)[ ?1, there exists a v not adjacent to u. By Lemma 5, d
v
> M. Therefore, by
Lemma 9, d
v
= M+1. Since v has M+1 neighbors and u has less than M neighbors,
there must exist a w which is adjacent to v but not adjacent to u. Repeating the
logic above, d
w
= M +1. We will demonstrate that u, w, and all of their neighbors
can be made better o? if u adds an edge with w and w drops it’s edge with v.
From Lemma 7
t
wv
? ?(d
v
) ?(d
w
?1)(?(d
w
?1) ??(d
w
))
= ?(M + 1) ?(M)(?(M) ??(M + 1))
= to(M)
= 0
Similarly t
vw
? 0, therefore t
wv
= t
vw
= 0. Let G
= G? e
uw
¸ e
vw
. Then
??
w
(G
, T) = ?(d
u
+ 1) ??(d
v
) ?t
v
w
= ?(d
u
+ 1) ??(d
v
)
??
u
(G
, T) = ?(d
w
)
??
x
(G
, T) = ?(d
u
+ 1) ??(d
u
) for every x ? N(u)
??
x
(G
, T) = 0 for every x ? N(w)
71
Let
t
ux
=
?
?
?
?
?
?
?
?(d
u
) ??(d
u
+ 1) + x ? N(u)
?(d
v
) ??(d
u
+ 1) +? x = w
t
wx
= ? for every x ? N(w) ¸ v.
Now
??
w
(G
, T +T
) = ? ?d
w
? ?
??
u
(G
, T +T
) = ?(d
u
+ 1) ?d
u
(?(d
u
) ??(d
u
+ 1)) ?d
u
? ??
= to(d
u
) ?d
u
? ??
??
x
(G
, T +T
) = for every x ? N(u)
??
x
(G
, T +T
) = ? for every x ? N(w)
Since d
u
< M, to(d
u
) > 0, and therefore, u, w and all of their neighbors can be
made better o? in G?e
uw
¸ e
vw
. This contradicts the strong pairwise stability of G.
72
Bibliography
[1] Abdulkadiroglu, A. and Sonmez, T. (1998), “Random Serial Dictatorship and
the Core from Random Endowments in House Allocation Problems,” Econo-
metrica 66: 689-701.
[2] Bala, V. and Goyal, S. (2000), “A Non-Cooperative Model of Network Forma-
tion,” Econometrica 68: 1181-1230.
[3] Bloch, F. and Jackson, M. (2007), “The Formation of Networks with Transfers
Among Players,” Journal of Economic Theory, 133: 83-110.
[4] Calvo-Armengol, T. and Jackson, M. (2004), The E?ects of Social Networks on
Employment and Inequality, American Economic Review, 94: 426-454.
[5] Chung, K. (2000), “On the Existence of Stable Roommate Matchings,” Games
and Economic Behavior 33: 206-230.
[6] Currarini, S. (2002) Stable Organizations with Externalities, mimeo: Universita
di Venezia.
[7] Edmunds, J. (1965), “Paths, Trees, and Flowers,” Canad. J. Math. 17: 449-467.
[8] Gale, D. and Shapley, L. (1962), “College Admissions and the Stability of
Marriage,” Amer. Math. Monthly 69: 9-15.
73
[9] Granovetter, M. (1973) “The Strength of Weak Ties,” American Journal of
Sociology, 78: 1360-80.
[10] Granovetter, M. (1995) “Getting a Job: A Study of Contacts and Careers,”
2nd Ed. Chicago: University of Chicago Press.
[11] Goyal, S. and Joshi, S. (2002) Unequal Connections, mimeo: University of
London and George Washington University.
[12] Gus?eld, D. and Irving, R. (1989), “The Stable Marriage Problem: Structure
and Algorithms,” MIT Press, Boston, MA.
[13] Jackson, M.O. (2003), “A Survey of Models of Network Formation: Stability
and E?ciency,” Mimeo, Cal-Tech.
[14] Jackson, M.O. and Wolinsky, A. (1996), “A Strategic Model of Social and
Economic Networks,” Journal of Economic Theory, 71: 44-74.
[15] Kranton, R. and Minehart, D. (2002), “A Theory of Buyer-Seller Networks,”
American Economic Review,
[16] Mongtomery, J. (1991), “Social Networks and Labor Market Outcomes: Toward
an Economic Analysis,” American Economic Review, 81: 1408-18.
[17] Rees, A. (1966) “Information Networks in Labor Markets,” American Economic
Review, 56: 559-66.
74
[18] Roth, A. E., and Sotomayor, M. (1990). “Two-Sided Matching: A Study in
Game-Theoretic Modeling and Analysis,” Econometric Society Monograph 18,
Cambridge Univ. Press, Cambridge.
[19] Shapley, L.and Scarf, H. ( 1974), “On Cores and Indivisibility,” Journal of
Mathematical Economics 1: 23-28.
[20] Tan, J. J. M. (1991). A Necessary and Su?cient Condition for the Existence of
a Complete Stable Matching, J. Algorithms 12: 154178.
[21] West, D.B. (1996) “Introduction to Graph Theory,” Upper Saddle River, NJ:
Prentice Hall.
75
doc_267214349.pdf