|
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. Recognizing that many assignments, such as a roommates assignment, require bilateral approval to dissolve motivates a new matching problem: matching agents subject to an initial assignment. A particularly important example of this is kidney exchange where after an assignment has been made, subsequent tests may determine that a patient and donor are incompatible. This paper introduces an efficient algorithm for finding a Pareto improvement starting from any status quo roommates assignment.
Externalities
in Networks (2008, revise and resubmit International Journal of Game Theory) 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). |
