Econ 805 Advanced Micro Theory I Dan Quint Fall 2008 Lecture 17 November 4 2008 So two sided matching markets First off sources I ve updated the syllabus for the next few lectures As always most of the papers are available online But if you re interested in the topic I highly recommend picking up the Roth and Sotomayor book Two Sided Matching it s a paperback it s under 40 and it covers most of what we ll be doing the next few weeks Also if you re interested in the topic Al Roth s website just google Al Roth has a staggering amount of material papers references overviews applications and so on Check it out My plan roughly is to spend the next four lectures on the general theory of two sided matching markets The first two days will be on one to one matching Then one day on extending these results to the many to one case Then one day maybe more on what happens when you introduce money The last two or three days will be on extensions complications and applications Motivation The topic generally is two sided markets Can be men and women as in the Gale and Shapley paper Can be firms and workers in a labor market Or schools and applicants in a college admissions model Classic examples matching newly minted MDs to residency programs at hospitals which uses a centralized matching process and matching law school graduates to clerk jobs with judges which does not New York and Boston public schools econ PhDs and academic jobs The key is that there are two disjoint populations and everyone in the market is on either one side or the other We can model buyers and sellers this way but it must be that buyers are only buyers sellers are only sellers We ll see an example later today of why we can t use these techniques to analyze one sided markets that is settings where any player can match with any other player For today and Thursday we ll focus on the one to one matching case where each player wants to match with at most one player from the other side of the market We ll refer to the two sides as men and women 1 Start off with A set M of men m1 ma A set W of women w1 wb generally a b but doesn t matter Each man mi has strict preferences over mates W Allowing for indifferences actually complicates things a lot for the baseline model we ll assume preferences are all strict It s customary to indicate matching with no one as matching with yourself so a man i s preferences might be w3 m1 w1 m1 m1 mi m1 w5 m1 w2 The Roth and Sotomayor book states preferences by just listing the options in order of preference e g P mi w3 w1 mi w5 w2 Similarly each woman has strict preferences over potential mates including staying alone We refer to potential mates as acceptable if they re preferable to being alone matching to yourself So that s the basic environment As a first step we ll put aside the mechanism design problems of eliciting peoples preferences and mapping them to outcomes and look only at outcomes The types of outcomes we ll be looking at are called matchings A matching is just a pairing up of men and women Formally a matching is a mapping M W M W such that for any m M m W m for any w W w M w for any m M w W m w if and only if w m If m m man m matches to nobody if m w W m matches to w We assume that preferences are only over mates that is each player cares only about who they are matched to not who everyone else is matched to 2 Next a couple of characteristics that might be reasonable to expect of an outcome We ll say a matching is individually rational if everyone s mate is acceptable that is nobody matches to someone who they like less than being alone We say a pair m w block a matching if m and w are not matched to each other m 6 w but m prefers w to his mate m and w prefers m to her mate w That is a pair blocks a matching if they d both be happier leaving their mate and matching with each other And finally we say a matching is stable if it is individually rational and it is not blocked by any pair The name stable matching is pretty descriptive obviously if a matching is blocked by an individual or a pair you would expect it to be unstable Stable matchings in matching models roughly play the role of equilibria in other models we haven t yet said whether they always exist there may be more than one we haven t said how you arrive at one but once you re at one it s reasonable to think you might stay there As it happens in two sided matching markets stable matchings do always exist and there is a nice algorithm for picking out at least one or two of them But first an example to remind ourselves that this result is not obvious and also to show why economists like two sided markets more than one sided markets the roommate problem The roommate problem is a one sided market that is a game where people need to end up in pairs but anyone can match with anyone And it s very easy to generate an example of a roommate problem with no stable matching Suppose there are four players a b c and d Preferences P a b c d P b c a d P c a b d P d doesn t matter There is no stable matching Easiest way to see it d is everyone s last choice but still preferred to being alone d must match with someone Whoever he matches with is someone else s first choice so d s roommate and whoever likes that guy most block the matching Next a simple example that there can be more than one stable matching Two men and two women everyone acceptable to everyone P m1 w1 w2 P m2 w2 w1 P w1 m2 m1 P w2 m1 m2 Two stable matchings w1 m1 w2 m2 and w1 m2 w2 m1 logic 3 The Gale and Shapley paper despite being quite brief and very nontechnical was extremely influential it basically launched the matching literature although it took a long time to take off Probably the major result of the paper was this Theorem In a marriage market as we ve defined it a stable matching always exists and here s a way to find one The algorithm they introduced the deferred acceptance algorithm To run the deferred acceptance algorithm one side of the market is chosen as the proposer we ll let this be the men To begin each man proposes to his first choice Each woman tentatively …