Computer Science – Computer Science and Game Theory
Scientific paper
2009-10-06
Computer Science
Computer Science and Game Theory
19 pages. A preliminary version will appear at the 5th International Workshop on Internet and Network Economics, WINE 2009
Scientific paper
For most people, social contacts play an integral part in finding a new job. As observed by Granovetter's seminal study, the proportion of jobs obtained through social contacts is usually large compared to those obtained through postings or agencies. At the same time, job markets are a natural example of two-sided matching markets. An important solution concept in such markets is that of stable matchings, and the use of the celebrated Gale-Shapley algorithm to compute them. So far, the literature has evolved separately, either focusing on the implications of information flowing through a social network, or on developing a mathematical theory of job markets through the use of two-sided matching techniques. In this paper we provide a model of the job market that brings both aspects of job markets together. To model the social scientists' observations, we assume that workers learn only about positions in firms through social contacts. Given that information structure, we study both static properties of what we call locally stable matchings (i.e., stable matchings subject to informational constraints given by a social network) and dynamic properties through a reinterpretation of Gale-Shapley's algorithm as myopic best response dynamics. We prove that, in general, the set of locally stable matching strictly contains that of stable matchings and it is in fact NP-complete to determine if they are identical. We also show that the lattice structure of stable matchings is in general absent. Finally, we focus on myopic best response dynamics inspired by the Gale-Shapley algorithm. We study the efficiency loss due to the informational constraints, providing both lower and upper bounds.
Arcaute Esteban
Vassilvitskii Sergei
No associations
LandOfFree
Social Networks and Stable Matchings in the Job Market does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Social Networks and Stable Matchings in the Job Market, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Social Networks and Stable Matchings in the Job Market will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-357357