  Many-to-one matching markets exist in numerous different forms, such as
college admissions, matching medical interns to hospitals for residencies,
assigning housing to college students, and the classic firms and workers
market. In all these markets, externalities such as complementarities and peer
effects severely complicate the preference ordering of each agent. Further,
research has shown that externalities lead to serious problems for market
stability and for developing efficient algorithms to find stable matchings. In
this paper we make the observation that peer effects are often the result of
underlying social connections, and we explore a formulation of the many-to-one
matching market where peer effects are derived from an underlying social
network. The key feature of our model is that it captures peer effects and
complementarities using utility functions, rather than traditional preference
ordering. With this model and considering a weaker notion of stability, namely
two-sided exchange stability, we prove that stable matchings always exist and
characterize the set of stable matchings in terms of social welfare. We also
give distributed algorithms that are guaranteed to converge to a two-sided
exchange stable matching. To assess the competitive ratio of these algorithms
and to more generally characterize the efficiency of matching markets with
externalities, we provide general bounds on how far the welfare of the
worst-case stable matching can be from the welfare of the optimal matching, and
find that the structure of the social network (e.g. how well clustered the
network is) plays a large role.
