|
The Roommates Problem Revisited
Job Market Paper
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
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 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 efficient algorithm for
finding 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.
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 analyzes in generality the two
extreme cases in which links cause either entirely positive or entirely
negative externalities. In each case, I am able to find the socially
optimal network for a wide class of utility functions. The paper provides
insight into why such an unusual structure as the star appears so widely in
the networks literature. It also provides a generalization and simplification
of results found in the classic networks paper by Jackson and Wolinsky
(1996).
|
