Matching Market Design: A Theoretical Overview | Parag Pathak

[00:00:05]okay thank you well let me move on and continue my lecture today is mostly going to be about some theoretical aspects of matching market design so that's an immense topic and I only be able to touch on a couple of issues here I want to start off by echoing one of the questions that al started with which is the the very first question any design economist needs to confront which is why do you need to design a market and a very closely related question to that is what determines the set of instruments that you can use for designing markets or a question that sometimes matching market designers get which is why can't you use prices here and these are pretty fundamental questions that economic theorists have debated for for decades so I won't have time to do justice to them but I do think it's helpful to set the stage by telling you a bit about one of my favorite design markets and that is the Oklahoma land rush of 1889 so this was a system used in the late 1800s devised by president Benjamin Harrison to allocate land parcels to settlers non-native settlers in Oklahoma the mechanism worked as follows settlers were asked to cue up on High Noon of April 22nd as soon as it was High Noon there was a race who ever got to a land parcel first was allowed to claim it okay and now not everyone played by the rule so some individuals jump the queue in fact those individuals became known as Sooners and some of you may have heard of a University of Oklahoma football team they're called the Sooners and as far as I know no economist was involved in designing this market when we see a situation like this it raises the question that many market designers start with could we have designed a better system and if you look at land parcel allocation and following this states like Georgia used a lottery as far as I know no state actually used an auction-based system but there are many examples markets that are designed by someone and many examples where prices are not used so some examples that may be familiar to a labor economist in particular include forced conscription so for a long time the United States had a draft despite Milton Friedman's urgings to get rid of the draft finally that was eliminated Gary Becker famously argued that green card should be auctioned that yet has not happened in the United States of green cards partly allocated by lottery and I sure would wish that I could pay someone to serve on a jury I've been served myself so why is it that we don't use prices in some of these settings and there are many reasons so one basic trade-off is the trade-off between the willingness to pay and the ability to pay so price based allocation has the benefit of allowing people to express their preferences but if market based price is used in income plays a large role rationing or lottery based systems may allow true needs to be met met so there could be an equity or fairness rationale for using a lottery rather than a price the problems include over delivery to those who do not really value items so this is an old idea first formalized by Marty Weitzman it's been refined by a number of authors when there's resale markets when the set of instruments is more complicated but this is one common reason why we don't see priced based allocation more generally why have we restricted the set of instruments there's often technological constraints contracts cannot be made rich enough there's enforcement constraints there are also moral or repugnance constraints these are fluid things and so what I want to do in my talk today is acknowledge that we like prices as much as any other economists but start from a position where we realize that they are not or sometimes cannot be used so the goal today is to give you a whirlwind tour of some of the canonical ideas and matching get design okay so I'm gonna start off talking about a class of environments that we call the one-sided matching environment simply allocating objects and that's environment I'm gonna introduce two big ideas first is what we call a serial dictatorship and the second big idea is Gail's top trading cycles then we'll move on to talk about two-sided matching environments and I'll quickly review the deferred acceptance literature that I'll described and talk about the the Boston mechanism and some of the variants that we've seen in the field and then depending on how much time we have I'll talk about a couple of new issues design issues designing choice functions and I'll conclude by telling you a little bit about some developments where deferred acceptance has been generalized to actually include richer commodities prices or even contracts and this is a very active theoretical frontier so let's get started okay so the first model I want to introduce is what's called a house allocation problem okay so many of these models are parables of big decisions in in one's life housing the marriage model of college admission so what happens in the housing model there's a finite set of houses okay there is a finite set of agents in the model we only work with ordinal preferences okay so agents have strict preferences over houses and an allocation in this setting is simply a matching okay so that is a function that specifies each agents assignment such that no house is assigned to more than one agent okay so this is what we get to start with now with these primitives in hand what are some things we could potentially do so a natural thing to do is what's called a serial dictatorship okay so given an ordering of agents in a serial dictatorship the first agent will be assigned his top choice the next agent is assigned his top choice among the remaining houses so on and so forth okay this is like a queue okay it's a it's a dictatorship because when it's your turn you are the dictator you get to choose and it's cereal because we're processing agents according to this ordering and this mechanism has some very nice properties okay the first properties this is a strategy proof mechanism what does that mean that means truth-telling is a weakly dominant strategy for all participants now it's worth pointing out that it's not that easy to find strategy proof mechanisms in fact we have very strong results saying in general we don't have many dominant strategy mechanisms so when we restrict the environment such that agents have preferences only over houses not over what other people got it is possible to find strategy proof mechanisms in practice so why is it strategy approval when it's your turn the best thing you can do is say the house that you want the most among what's available and you cannot influence when it's your turn because the ordering is given the other a property of this mechanism is Pareto efficiency so this is Pareto efficient that is there is no other allocation where an individual is doing strictly better and no individual is doing worse okay so this is as simple as it gets okay now what's a problem with this mechanism well a problem with this mechanism is the ordering determines everything right if I'm the last person in line I only get to pick among what's left over more formally we can say this mechanism doesn't satisfy a property known as the equal treatment of equals that is if two individuals have the same preferences they should get the same allocation okay so that can be seen as a fairness consideration and in this setting the only way you can satisfy equal treatment of equals is by using some kind of random or stochastic mechanism so how would we enrich this mechanism to make it random so that week would have two individuals with the same preference is getting the same outcome well we could do that by simply using a lottery a uniform lottery to determine the ordering okay that's what's known as a random serial dictatorship okay so a random serial dictatorship inherits the properties of a serial dictatorship it's also strategy proof and it's post Pareto efficient okay so far so good so this is as simple as it gets now let's make this a little bit more complicated by adding endowments to the problem okay so now here's the jargon so in the house allocation problem there are no endowment so the objects are collectively owned by everyone in a housing market problem we'll consider the same exact environment but our starting point is individuals enter with a house ok so you can imagine and this is a great tool for some of the students in first-year micro this is the simplest possible exchange economy every agent has an endowment of a house agents have strict preferences and once we introduce this idea of endowments in motivates thinking about a couple of other properties so the next property I want to introduce this individual rationality so that is what it sounds like so an allocation is individually rational if each agent is doing at least as well as its endowment ok and then the core property ok the core property allocation is a core allocation if there is no coalition of agents who would prefer to contract amongst themselves compared to what they get in the allocation ok so in the limit since we can consider any size coalition if there's a coalition of one individual asking an allocation to be in the core is the same thing as saying it's individually rational if the coalition was everyone it's the same thing as Pareto efficiency ok so the core is a central concept in this literature so we have endowments now how are we going to clear this market and that leads to one of the very prominent mechanisms in the literature here and this is Gail's top trading cycles algorithm ok so in fact this was described in an article not written by Gil I was in shock Lane scarfs article in 1974 so how does this work so in step one each agent points to the owner of his favorite house since the problem is finite there's going to be at least one cycle a cycle as an agent pointing to another agent that eventually points back to the initiating agent and once we find a cycle each agent in a cycle is assigned the house of the agent he points to and he's removed from the market so we execute that trade if there's at least one remaining agent we'll go on to the next step okay so we've looked for a top cycle okay top choices and we have the agents who are in the cycle trade amongst themselves if you're left over in the generic step you point to your favorite house that remains okay again because the problem is finite there will be a cycle an agent pointing to another agent so on and so forth if we remove the cycle now in any step there can be more than one cycle but each agent can only be part of one cycle and we execute those trades and we iterate okay so this is gales top trading cycles now this is a canonical mechanism because it has a number of fantastic properties okay so what are those properties first the outcome of top trading cycles is the unique core matching in this environment with individuals and houses and it's also the unique competitive equilibrium allocation okay so we can construct a price vector to decentralise this allocation and so that was one of the first results about this mechanism second result is we can think of the core top trading cycles as a direct mechanism and by that I mean it's a preference revelation mechanism individuals reveal their type and it is a strategy proof mechanism okay so here now is the second example where we have found a dominant strategy mechanism you cannot influence what you get by submitting a false report of what houses you want okay and loosely speaking there you can't influence which cycles form so you might as well report which houses you want correctly because the cycles that form will where the cycle in which you're involved will be the one that gives you the best house you can achieve a third result now is a bit of a specialist result but it says that this for this environment is the only mechanism you can use if you're interested in Pareto efficiency individual rationality and strategy proof miss okay so the case is sealed you could say we have an ideal mechanism great incentives great efficiency properties there's nothing else you can do okay now these results are kind of classic results but this mechanism has inspired some more recent literature by thinking of the following kind of extension okay so let's imagine a hybrid scenario we're not all agents have endowments okay there may be some agents who come to the problem owning a house and there's some agents who are newcomers okay or we can think of a scenario where instead of having endowments individuals start with property rights okay I have a property right over Pat for a given house because I'm older than Pat say or I've scored higher on a test than Pat or I have a better lottery draw than okay so you can think of that kind of like an endowment but it's probably more appropriate to think of this like a property right so in this kind of environment when we have these property rights are these priorities we can adapt top trading cycles by this following modification in the original version I said you point to the owner of the house that you want the most now instead why don't you point to the house that you want the most and the house or the object in this case well point to the agent who's got the highest property right okay so that's a very modest modification but it allows us to accommodate a richer set of problems okay now the reason I'm telling you about these old ideas is that this mechanism was actually used in practice as far as I know for the first time to allocate children to school in New Orleans okay so the recovery school district used a version of top trading cycles to allocate children to school to both traditional public schools and charter schools and so here's how this was described to the public okay so this is a clip of the algorithm in The Times Picayune okay so that's the now-defunct newspaper in New Orleans in Scenario a we have a cycle involving just one person so here student one is pointing to school a is top choice and the school is pointing to the student okay so a cycle can involve just one kid cycles can involve more than one kid of course so here's an example of scenario B student 1 is pointing to school B school B's the student who's got the highest claim the highest property right there is student 2 so that's why the school points 2 to 2 then says my first choice is school C so he's pointing to school C C gives 3 the highest priority 3 in turn one school a so we've found this trade we execute that trade by assigning the child to the school that they're pointing to okay and so the mechanism in the rst is Pareto efficient and it's also strategy proof okay so that's the class of one-sided matching models okay two big ideas serial dictatorships and gales top trading cycles now let's enrich the environment and think about matching two sides okay so this is closer to what I was talking about so here what's the jargon okay so we have a house allocation that's one-sided we have the marriage problem okay that's a fable of matching together men and women what's key about the marriage problem is it's a one-to-one matching problem okay so we can assign one man to more than one woman and vice versa so that's what we call the marriage problem College Admissions is a scenario where it's a many to one matching problem okay so the jargon there is it's many because the college could have many seats okay and the key concept so Al has already introduced the differed the celebrated deferred acceptance algorithm and stability stability in this context is individual rationality plus the absence of a parent block okay now the literature on deferred acceptance is by now immense so I looked at my undergraduate class lecture notes and said what are the most important results that someone would need to know about different acceptance okay and so I've summarized them here so the first result is what we call side optimality so there is a worker optimal stable matching and there is a firm optimal stable matching so I'll mention that already and indeed if I look at the worker optimal stable matching that's the best for workers but it's also firm pessimal so that's the worst for firms and vice-versa if I look at the firm optimal stable matching that's the worst stable matching for workers so that's what some people call the opposing interests or conflict between the two sides of the market here the second result that's important is the incentive results so we have a dominant strategy mechanism but in this case you have to restrict the set of agents so if we think about the deferred acceptance algorithm where workers propose to firms that version is a dominant strategy mechanism its strategy proof for workers okay in if we were to ask that we have a way to implement a stable allocation that strategy proof for both sides the answer is no so there's no way to do that unless we think about approximations like Al mentioned large market approximations the third result okay now again there's a little bit of jargon here it's what people call the rural hospitals result okay so what is the rural hospitals result that's a result that says something of a following sort across all stable matchings a set of agents who are matched is the same okay now why would you ever call this rural hospitals well one story about this is there's a long-standing concern that there's not enough doctors working in rural areas in the United States okay and one might have said well is that because of them the match the fact that they're using a stable matching algorithm well thanks to the rural hospitals theorem we know if you have a rural spittle that has an empty seat that no one wanted to go there it didn't matter which of the different stable points you chose in practice you would always have that hospital not have everyone taking a seat at that place so that's why I think one reason people call this a rural hospitals result okay fourth result okay this is a result that I'm calling order independence okay so the way deferred acceptance is usually described as what Al did he said everyone proposes all workers proposed propose two firms simultaneously but in practice we don't need simultaneous proposals with deferred acceptance we can do this in an iterative way in fact the sequence of proposals that are made does not matter what the order is will always get the same outcome okay so take a given worker have him propose to his first choice if he's rejected there we could go back to him and have him propose to a second choice we don't need to wait to see what happens to all the other workers okay and the reason we can do that is because this is a deferred process nothing is finalized until the very end