Social Networks and Stable Matchings
The Stable Marriage Problem is a famous problem in Mathematics and Computer Science (certainly familiar to those who have taken Introduction to Algorithms at Cornell), and its concepts are applicable to various real world situations such as matching between candidates and companies for job searches, matching prospective students to Universities, and to some extent matching consumers to online retailers.
To those unfamiliar with SMP, it roughly states the following: Given two disjoint sets A,B where each and every element in A has a preference list to match all elements in B, and each and every element in B has a preference list to match all elements in A, devise a stable matching between all the elements in A and B. A matching is said to be NOT stable if there exists some matching (a1,b1) and (a2,b2) between elements in A and B such that a1 prefers b2 over b1, and b2 also prefers a1 over a2. There is a known efficient algorithm that will compute stable matchings for any two disjoint sets given a preference lists for each of the elements (called the Gale-Shapley algorithm). The SMP is conceptually similar (give and take some constraints) to Network Exchange problems covered in class. The algorithm presented in class solves the problem through a similar strategy as Gale-Shapley, by placing a bias in one set to “request” matchings to the members of the other set, and performing re-matching if any collisions occur between two members of the first set to request the same member of the second set.
The paper makes an argument that the traditional algorithm is not always applicable to real life situations where there are what the author calls “externalities”, or effects arising from peers participating in the matching. Often times these peer effects are intimately connected with the underlying social network of the participating members and can be modeled based on them. The paper then proposes an algorithm that generates a stable matching by representing effects of peers and preferences as a utility function rather than a static preference list, and proves is efficiency, its correctness in outputting a stable matching, and presents an analysis of the interplay between stable matching outputs and the structure of the underlying social network of the input instance.
The paper makes a bold statement when presenting its new method, but it also has a valid reasoning behind it. For example, in one of the use cases of SMP we have presented the student-College matching problem. It is reasonable to assume that a specific student’s preference for a perspective college is not a static list, but rather dynamic with respect to who in his social network is applying to where, and who in his social network is accepted to which colleges and which college they are planning to go to. The paper presents yet another example of how classroom-level theory and algorithms can only go so far in representing and solving real-life problems.
Source:
http://users.cms.caltech.edu/~adamw/papers/sagt_short.pdf