Matching Market Design Explained | Parag Pathak Lecture

[00:00:02]okay everyone good morning my name is Parag Pathak and I'm very excited to be here I actually was a student in the summer school back in 2006 so it's a treat to be on the other side of the aisle here telling you about a new set of issues that we're gonna talk about in this summer school having to deal with matching market and issues on matching market design so the structure of the next four lectures today this morning I'm going to introduce some very basic theoretical ideas from the literature on matching markets following that Nikki Allegra Wall is going to talk about some empirical issues and in particular he's going to discuss how to do revealed preference analysis in matching models so that's more closely related to some of the ideas that we saw earlier in the course and then tomorrow we're gonna extend some of those ideas in different directions and kind of consistent with the theme of this course we're going to be talking about a mix of theory and empirical issues so stop me at any time I'd love to get any questions this is going to be really a helicopter tour of many issues and let me get right into it okay so you know one of the first questions that you have to ask yourself as a design economist is why is it necessary to design a market okay and a very closely related question to that is what instruments does a designer have at his disposal these are very deep questions questions that I cannot do justice to that probably merits summer schools of the by themselves but I think it's useful to set the stage a little bit by talking about one of my favorite examples of a design problem and that is what's shown in this picture here okay so this is a picture of an allocation mechanism that was devised in the United States this was in the late 1800s the president of the US Benjamin Harrison thought it was a good idea to reclaim about two million acres of land from the natives and the scheme that was adopted was a scheme where at high noon in the spring of 1889 settlers were asked to stand behind a line a gun was shot and whoever claimed a plot of land first was able to get to that was able to obtain that that plot of land and so when you see a scheme like this you can't help but ask is there a better way and a couple of years after the Oklahoma experience Georgia actually used a centralized mechanism more centralized mechanism with lotteries okay and as far as I know auctions have never been used to allocate land like this and when I hope this case study illustrates is some resource allocation problems are designs folks are making decisions about how resources are going to be designed and they often don't use all available instruments okay so a prices in particular we're not used here this was a queueing based mechanism and there are many other examples of markets where explicit prices are not used so in several countries we have forced conscription or lottery based systems for military service in the u.s. green cards are allocated through a lottery system as is jury duty and kind of the starting point for the mechanisms I want to talk about it's always this question why aren't we using prices and one set of arguments about why prices are not directly used has to deal with the trade-off between willingness to pay of agents and the ability to pay of agents so roughly speaking the argument is if we have a priced or market based on location system then that's going to allow for preferences to be expressed willingness to pay to be expressed but if a market clearing price is used then income is going to play a large role those who have the ability to pay well dominate the allocation on the other hand if we don't use a price based system and use some form of rationing that may be preferred if we're concerned about equity we want to meet true needs the potential pitfall of a rationing based scheme is we may be delivering goods to those who do not really value the items so we satisfy the constraint about ability to pay but we may be miss allocating in terms of willingness to pay so this is a fairly loose discussion it's an idea that's been formalized in several generations I think starting with Marty Weitzman in a very early article and made more modern with the tools of mechanism design in this last article by Gucci and co-authors other arguments that we often see involve things like technological constraints it's hard to compute price based equilibrium or enforcement constraints if we buy and sell organs does that mean when I declare bankruptcy the courts can take a claim on my kidney do I have to declare that and then another set of issues that are often described as moral and quotes or repugnance constraints you know our starting point is we like prices in Lutron matching markets but sometimes they are not use or cannot be used so let's try to understand what we can say in a set of models without prices okay so that's going to be my agenda for the lecture today I'm going to introduce several key canonical mechanisms in markets where there's indivisibility x' and prices may not exist okay and will be on building on these mechanisms in the subsequent lectures so the five basic ideas I want to tell you about the first involves what I call a serial dictatorship so we're going to start from the simplest possible allocation problem and then make the model increasingly more complex the second key idea is top trading cycles so then we'll talk about stable mechanisms or the literature on deferred acceptance the fourth area is the literature on the Boston mechanism of what's now known as the immediate acceptance algorithm and then lastly and I'm not sure I'm going to have time is an effort to try to link some of these models in matching to models and auction theory so let me get into it yeah that's right yep so I'm thinking about today one-shot allocation problems where there's a centralized mechanism and there's no resale afterwards and that'll become clear when I show you that a specific example yeah so that so that's right well there is no no price and the you know the very first example maybe this will become clear as I tell you so why don't I tell you this and then we can come back to this you know what it really means to say no prices is actually quite a subtle issue so I want to take your point on that and let me tell you about this very first model okay and this is what's known in the literature as the house allocation model so interestingly matching theory often talks about these canonical models of house allocation marriage and college all of life's important decisions so in the house allocation problem our setting is we have a finite number of houses and we have a finite number of agents okay in the model we will say agents have strict preferences over houses okay and each agent wants at most one house and an allocation here is going to be a function a matching that specifies each agents assignment such that no house is assigned to more than one agent okay so this is the simplest possible allocation problem you can entertain and in this environment a very natural mechanism is a surreal dictatorship okay so what is a serial dictatorship we have an ordering of agents given that ordering of agents we assign the first stage in his top choice the next agent his top choice among remaining houses the third agent is assigned his top choice among remaining houses and so on and so forth okay so this is like a queue if we think about a serial dictatorship as a direct mechanism it has some very nice properties the first property is that it is strategy proof okay what does that mean that means it is weakly dominant for agents to report their preferences truthfully to the mechanism okay why is that well if I am participating in this mechanism I cannot influence the order the serial order by my report that's just given in this mechanism and when it's my turn I can do no better than telling the mechanism what I want truthfully because if it's available that's what I will get okay second property that this mechanism has is that it is Pareto efficient okay that is there is no other assignment no other allocation where some agent is getting something strictly better and no agent is getting something worse okay and that's also quite simple to see suppose the allocation where Pareto inefficient we find the first agent who's getting something different in the Pareto dominating allocation and you can see that since he's the first agent to get something different when it's his turn to choose the house that he prefers was available under the serial dictatorship so there's no way there could have been someone who's getting something that's better okay so this is the simplest possible mechanism the variance of this mechanism that we often see in the field typically involve some kind of randomization so that leads us to what's called a random serial dictatorship so what do we do in a random serial dictatorship we draw the ordering of agents namely hey say there's a uniform distribution from which we draw agents and that mechanism is going to be strategy proof as well random Cyril dictatorship okay so that is another term to tell you about now let's enrich the model in one direction okay let's take our house allocation problem and add endowments okay suppose we start the model with agents having endowments okay and that's what leads to what we call the house housing market model okay and you can think of our first problem the house allocation problem as a situation where the houses are collectively owned by society whereas in a housing market problem we will have the same set of primitives houses agents and the new ingredient is everyone starts off endowed with a particular house okay now everything else is as before so the housing market model is the simplest possible exchange economy okay and as soon as we introduce an exchange economy this raises the question that was asked for what do we mean by absence of prices so we could define a competitive equilibrium concept here we need not do that and some of the ideas that we want to explore for the housing market problem when we have endowments involve individual rationality so if we start the model with agents with endowments it may be desirable to ensure that agents are doing at least as well as their starting point so that's what we mean by individual rationality here another concept is the core ok the core is the idea that there is no coalition of agents who prefer to contract amongst themselves then their outcome in the housing markets solution concept okay so can we compute a core outcome and that's the question I want to talk about next and the answer is yes and that leads us to the second very important mechanism that I want you to know about and this is called the top trading cycles algorithm so the the literature actually calls us gales top trading cycles algorithm because this algorithm first appeared in an article by Shapley in scarf in 1974 and you know what they say in that article the history of this is they were interested in this very simple exchange economy setting and whether we could find a core outcome and a Gale came up with this method to do this ok so this is why even though Gale didn't write the paper it's called gales top trading cycles algorithm how does this work ok so what we're trying to do at a very high level is look for swaps or exchanges between agents in the market ok so these are going to be organized as top cycles or agents are going to be trading first trying to trade their top choices so in the algorithm in step one each agent is going to point to the owner of his favorite house ok since this is a finite model there is at least one cycle so I'm pointing to Erik because I would like the house that he's endowed with Erik is pointing back to me because he would like the house that I'm endowed with that's a cycle ok when we find a cycle we implement the cycle so I trade with Erik I'm assigned Erik's house and Erik is assigned my house and then we leave the problem ok now in step one there can be cycles involving one agent if the house that I'm endowed with ends up being say my top choice I'm just going to point to myself cycles can involve more than two agents there can be more than one cycle in a given step but each agent is at in it in at most one cycle in any given step here ok so what we do after the conclusion of step one we remove all of these top cycles if there is at least one remaining agent we'll proceed with the next step so in the generic step every remaining agent is going to point to the owner of his favorite house the remaining houses every agent in a cycle is assigned the house of the agent he points to and is removed from the market with his assignment and we continue as so long as there is one agent remaining okay so this is TTC and like a serial dictatorship TTC has some very nice properties okay so let me tell you a little bit about those properties so the first property is that the outcome of top trading cycles is going to be a core outcome and in this model it is the unique core outcome okay so we have a way to compute a core outcome very simply we can define a notion of competitive equilibrium here so that would be what we would find familiar from first-year microeconomics agents are maximizing their utility there is a price vector a price for every house imagine the prices are such that the houses that are transacted in the first step have higher prices and the houses in the second step the houses in the second step have higher prices than those in the third step and you can show that that price vector and the outcome of TTC support a competitive equilibrium where agents will be maximizing their preferences subject to their budget constraint okay now if we think about the core as a mechanism agents report their preferences the core as a direct mechanism is a strategy proof mechanism okay so what that means again just like in a serial dictatorship I have a weakly dominant strategy to report my ranking of houses truthfully okay and in this domain we have an even sharper result which is that the core is the only mechanism that is Pareto efficient individually rational and strategy proof for the housing market problem okay so this is a very sharp characterization in terms of these three axioms you can think of it that way efficiency individual rationality and strategy proof miss this is all we can do now oh yes question yep four so that the only Pareto efficient and strategy proof mechanism is a serial we have results that are very close to that so we need some other axiom to complete the characterization there so there's typically some kind of neutrality a type axiom that our consistency type of axiom there yeah yes say that again so 8c so I like your house okay yeah yeah so we ought we would all trade we would have a cycle you can have a 3-way cycle if there's n agents we can have an N way cycle where we all all trade right exactly right so cycles gonna also involve just one person and that's exactly the reason why it's Pareto efficient right we're looking for mutually agreeable swaps in a particular fashion here exactly are there any other questions okay so this is now we're now into 1980s okay and the literature here was I think we resuscitated in some respects by an interest in a hybrid scenario between the case where we had no endowments where we started with that house allocation problem and a case where we have endowments the housing market model what if we have a situation where not everyone has an endowment okay we can think of that model as a model where the agents who do not have endowments maybe have some kind of existing property right or priority for vacant houses okay so where could these property rights or priorities have come from in some settings we can think of these as due to the outcome of lottery drawers so imagine we're trying to allocate dorm rooms there are some incumbents who have their existing dorm room there's some freshmen newcomers maybe there's a queue based on lottery draws and we can take this TTC idea and make a very minor tweak to it the way I first described TTC is I have agents pointing to other agents okay and we look for cycles where the cycles are between agents suppose instead of having agents pointing to the owner of the house we have agents actually point to houses okay that is the the adaptation of TTC that allows for its use in richer environments so rather than pointing to a given house I point to the rather than pointing to the owner of a house I point to the house itself what does this accommodate this accommodates the possibility that a house may not have an owner okay and so what the house is going to do in this setting is point to the agent who's got the highest priority okay and that allows me to deal with the situation where not all agents have endowments and some houses don't have owners okay and so this a basic observation actually was central to initial proposals for thinking about top trading cycles in environments where there are some priorities okay so we start the model where agents may not have an endowment but there are some existing structure of property rights like in the case of school allocation okay so our situation of school allocation is one where we have students who have preferences over schools in the simplest model schools prioritize students ok those priorities could be based on things like lottery numbers or test scores and we can implement a top trading cycles based algorithm simply by having the schools point to the student who's got the highest property right or the highest at the school okay and everything else proceeds as before and so let me show you a very real-world example of this but there are some questions before I do that yes Eric yeah that's correct yeah so that there's a tie so yeah so turns out a lot of things change okay so I'm gonna come to that out let me defer that that's a great question okay that that's maybe one of the most important new wrinkles in the school assignment problem yeah but your question on the on the school side rankings the priorities yet if I'm one of those ten and I'm endowed with that house I would I would get it yeah so in in the top trading cycles model right all ten people will be pointing to my house right I will be pointing somewhere else okay let's say there's only 10 guys so I'll be pointing to one of those 10 guys the person for whom I trade with would get the house so I'd be pointing to you you point to me we trade exactly so that that's what determines the outcome yeah there are two two results on that question the first paper is won by Sylvia Popeye and econometrics and that is so that just again what is a question right so you know one way we can tie the bow on this literature are results like this that say this is all we got this is the class of mechanisms that satisfy these three desirable properties what happens in this particular domain right is the question and there's yes so there's two papers I'd point you to we can talk more about this afterwards so Sylvia Popeye's econometrics a paper that paper relies on a new axiom that only appears in that paper actually so it's maybe not something that is as familiar as efficiency and strategy proofing there's a paper that came out in theoretical economics last year by Mark pitcher and COO n'ver that gets rid of that axiom so it has a complete characterization of efficient and strategy proof mechanisms in this hybrid scenario so you can take a look at that right you know what do those mechanisms look like they look like very elaborate versions of top training cycles okay where the priorities are allowed to change based on the sets of cycles that might form and things like that okay let me go back to this picture here because this illustrates what I just talked about so suppose we want to use top trading cycles in a situation where we have priorities and not necessarily endowments this is how this was described to folks in New Orleans where a mechanism based on operating cycles was actually used to allocate children to school so in New Orleans they're talking about two different scenarios so this is from the newspaper and you know I always find this interesting because this is how the public learns about these algorithms so in Scenario a we have a self cycle a cycle involving a student number one where it says here you can't read this well probably a student number one is a ranked school a is our top choice and in this scenario student one gets a seat at her top-ranked school because it's just a cycle where he's pointing to the school for which he's got the highest priority in Scenario B we have that example of a 3-way cycle that we just talked about school a is now pointing to student one who points to school be his top choice B points to student 2 who's got the highest priority at school B student who then goes on to point to school C student 3 is the highest priority student at school C so C points to student 3 and we complete the cycle by student 3 pointing back to school a okay so in the actual allocation system we implement this cycle in the case of school assignment schools have more than one seat so suppose school a had 10 seats we find a cycle like this we would reduce the capacity of a by one and we would just continue yeah question so we can define a competitive equilibrium in in this class of models here we have to think a little bit about the priorities in that case so we have to be a little bit more clever about the price factor that we play with but you know my perspective why bother I mean we don't need it right so we can directly compute the outcome without relying on prices so great ok so question yeah great well in every cycle if I'm trading as a student I'm getting my most preferred option among what's available right so that's why it's Pareto efficient for students but you're asking something and I'm going to come to next which is what about the school side and how should we think about their considerations okay so let me come to that after introducing the third class of mechanisms that I want you to know about okay so that are the class of stable mechanisms or da deferred acceptance okay so deferred acceptance is defined as follows so this is again is an idea due to Gale and also Shapley here so what is our environment so we've gone from a situation where we have agents wanting houses to a situation where maybe the houses have some priorities over the agents okay and we're assuming throughout that these are like strict okay so the house is prioritized agents in a strict manner we can relate that model and think of this as simply men in women and this is what Gale and Shapley initially proposed we have men who have preferences over women women have strict preferences over men and we're looking for a way to pair them together okay so this is why this is called a marriage problem and the college admissions variation on this is students have preferences over colleges colleges have preferences over students but now colleges have more than one seat okay so that's the model that's called a many to one matching model okay so again the jargon okay that I think often when you see this literature this feels like there's a lot of jargon here the house problem the marriage problem the college problem housing is a one-sided matching problem because it's agents being matched to houses we don't really care about the utility of the houses okay in in the model at least so in the literature on deferred acceptance we call it a two sided matching model because there are two sides you know men and women or students and colleges and we make about welfare of both sides here okay so that's why it's related to that earlier question so let me tell you about how deferred acceptance works okay so in deferred acceptance in step one each student so I'm going to do this with a student school language he's going to propose to her first choice each school is going to tentatively assign its seats to its proposers one at a time following the priority order of the school okay the key word here is tentative so in step one the proposals are tentatively held any remaining proposer is rejected and in the general step step K here each student who was rejected in the previous step proposes to her next choice the schools are going to consider these new proposals together with the applicants that they had tentatively accepted up to date up to that round and select the best in that group okay and how is going to select the best well one at a time according to the priority order and any remaining proposers are going to be rejected so this algorithm will terminate when there are either no new proposals or each student has exhausted their rank order list okay so you know one of the things whenever I talk about deferred acceptance you know I say you know in deferred acceptance it could happen it could be the case that I've listed a school say 12 and Eric has ranked at first and I get assigned that school over Eric and that sounds kind of unintuitive why would that happen well it could happen because eric has Tennant you know applied to his school that he's listed first the school has tentatively held him throughout the process of this algorithm I on the other hand have applied to 12 other schools and eventually I would apply to the school that Eric has ranked first I'd only do that if I've been rejected from all of my higher ranked choices so at the stage in which I would apply to the same school as Eric you can think of that as my effective top choice why I've been rejected from all of my higher ranked choices and the way this algorithm works the deferring the tentative assignment here so central is when my proposal comes in the school will look at me versus Eric and say I actually like Parag better than Eric so Eric is rejected okay so that sounds very counterintuitive actually despite that what I'm going to tell you about is this mechanism you know amazingly has been discovered in the field several times okay so one reason why this mechanism is so iconic is that the very first time that this was widely deployed was in the 1950s in the United States in the u.s. medical residency labor market so every year in the US and now this is true in many other countries if you graduate from medical school you go through a centralized Clearinghouse to get your first job ok and in the 30s and 20s there were different procedures at different regional labour markets experimented with and finally the association of medical students and the major residency training programs came together in the early 50s and said why don't we integrate the market across the United States and why don't we use a you know it wasn't called deferred acceptance at the time but why don't we use the Boston Poole plan algorithm which turns out to be equivalent to the different acceptance algorithm and what's really quite amazing about that is this happened more than a decade before Gail and Shockley's first article on this topic so this was a mechanism that was invented by the participants themselves and I'll tell you a couple more examples where we've seen deferred acceptance emerge organically from the field before telling you about those examples they'll let me tell you about some very important results on deferred acceptance ok so again here this is really a helicopter tour so I won't be able to give you the proofs of these results there's a book by Roth and Sotomayor that has some of these results but the main results that I want you to know about are the following so the first is what I'm calling side optimality and opposing interest so the way we defined this algorithm here students are proposing to schools you could have easily thought of the opposite schools proposing to students and that would define another version of deferred acceptance the first important result about deferred acceptance that actually Gale and Shapley pointed out in that very initial article is that the side who proposes ends up at an outcome that is a stable outcome that is best for the proposing side so let me first define what I mean by a stable outcome a stable outcome is an outcome that is not blocked by either an individual or by a student and school pair what does it mean to block by an individual a block by an individual means at the outcome of after we have an allocation I as an individual can say I'd rather not participate I'd rather be matched to myself than what the mechanism prescribed for me if that's the case it's not individually rational and we would say it's blocked by an individual a block by a pair is a situation where the student in the school want to get a divorce from one another okay and would rather read contract with someone else okay so more specifically an allocation is not blocked by a pair if there is no student in school for whom the student would rather be match to another school and that school would rather have that student than someone who's been assigned to it okay so the deferred acceptance algorithm is a algorithm that produces an outcome that is stable okay and in this problem stability is sufficient for it to be a core outcome okay so these are the same themes that we saw with top trading cycles we have a core outcome yes Ariel in the model we have a lot of flexibility with what we want to do there so if I think about this for schools I would be you know leaving the district going to private school maybe going to an alternative sector that's not in the match exactly so for this allocation rule you never have a situation where what you assign me is actually a school that I would turn down and rather leave the out leave the market yeah people do think hard about that so one of the challenges there so that's a really an interesting question so suppose you had data from a matching system and the data rank order list of students ranking school what do we want to interpret if the ranking is not complete okay so a natural thing to say is if I rank three schools and then that's it my fourth choice is leave the market and go elsewhere right and people have different approaches to that that question sometimes people ignore that question and look at just at inside good demand in other situations folks have access to better data on the outside option so you can actually see where people are going and that tells you the relative ranking of goods in the market versus goods outside of the market but it's a it's a real challenge actually for empirical work because it seems like it's almost costless to rank everything right in practice if I really want to leave the market I could submit our complete rank order list look at what choice I get and then leave the market so why is it that people don't have complete lists in practice right and there are yeah so that that's an issue that this empirical work I said I think Nikhil may talk a little bit about this yeah a bit more when we talk about the data from these systems okay great okay so let me now continue with this helicopter tour of important results so we've just said that deferred acceptance produces a stable outcome one that's not blocked by an individual or by a pair it turns out it produces a stable outcome that is best for the proposing size so that's what I mean by side optimality if the students proposed as I've just described it here the outcome of the student proposing deferred acceptance algorithm is a student optimal stable matching okay and indeed if we have a model where the preferences are strict throughout there is a unique student optimal stable matching and that's computed by deferred acceptance okay now opposing interest refers to this idea that what's good for one side of the market is bad for the other side of the market so the student optimal stable matching is actually the least preferred stable matching for schools okay and vice-versa if we had that version of this algorithm where schools proposed to students we would have the school optimal stable matching and that is the worst stable matching for students okay and so that's a consistent theme that we see throughout the literature on two-sided matching markets that there is a lot of consensus on the same side as to what's good for that side and a lot of conflict across the two sides of the market the next result is a result about incentives okay so this takes us to the early 1980s if I think about the deferred acceptance algorithm as a direct mechanism where we have the students and the schools report their preferences the first result is that there is no strategy proof mechanism for both sides of the market okay so there is no way to get to a stable outcome that in a strategy proof way when both men and women are permitting their preferences if instead we focus our attention to one side of the market we have a possibility result and that result is in the man proposing variation of deferred acceptance it is a dominant strategy weakly dominant strategy for men to report their preferences truthfully and vice-versa for women and you know just a little bit of history here right so you know in the as I understand this and you know Eric can correct me if I'm wrong you know in the 1970s there was a very exciting research program trying to look at strategy proof miss as a goal in design and that research program quickly ran up against these impossibility results okay so that's the Gifford Satterthwaite theorem and it's cousins and you know gibbered Satterthwaite is very closely connected to arrows impossibility theorem as we know and what was very exciting about this class of model someone described this to me as a breath of fresh air we actually found real plausible mechanisms that our strategy proof so that's one thing that's quite exciting we have systems that are strategy proof even if in this limited way for one side side of the market so all three of these mechanism serial dictatorship top trading cycles and deferred acceptance our strategy proof yep the impossibility problem it's not so you're absolutely right so everything I'm working with here is with ordinal preferences so that's just a ranking so the question is thinking suppose we put numeric values say I like school one you know you know much 10 times more than school - can I do do more with that I can't surmount the impossibility results there are a series of recent papers trying to ask whether we can use that kind of information to improve the performance of deferred acceptance and I think if my reading of that is it's still quite mixed it's not clear it there's this other complication that we never really see in these domains where these models appear Cardinal information directly elicited so that's why I think people haven't explored that that much now the last thing I'll say about that is strategy proofing us is a very demanding concept because it's a finite economy concept right so for me to show something is not strong I just need to come up with an example where you know someone can manipulate them the mechanism are these examples relevant for practice and design they may not be that relevant in situations where maybe there's many agents and so they have yeah that's that's a great comment right so you know one place where that kind of ideas sometimes used is in what they call funny money systems like if I'm trying to allocate courses at a business school some of the schemes try to implement versions of that idea they're not strategy proof but you know just like the competitive mechanism is not strategy proof in some large market sense we can say people are like price takers and so your ability to gain from a manipulation is shrinking say as the market gets large so we may not need to worry about that actually so let me actually jump to that this is kind of the this point number six here and we'll come back to these other points so one of the the newer things that you would not see say in the Roth Sotomayor book on matching but it's something that we've learned in the last two decades or so is that in actual two-sided matching markets we tend to find that the set of stable outcomes is quite small so this is a phenomena for instance seen in the US medical residency matching market in several school assignment markets even though in principle we could have many different stable matchings core core matchings in practice we typically see you know at most one or two or and so there is an attempt to try to explain that phenomena and what's important about that is when we have in the marriage problem say a singleton Cora a unique stable matching then there is a no possibility for agents to manipulate so if we know the primitives are such that will have a unique stable matching there's no way we'd want to manipulate so that's one sense in which maybe we don't need to worry so much about this impossibility result so how have folks gone about number six so there's really two stress strands of literature thinking about matching in large markets one is a strand of literature that looks at continuum models of matching so the idea is we take a given economy and we replicate it so take the students in schools and make a copy of them okay so for every student will say there's actually types of students and we have two copies of each type we have three copies of each type so on and so forth this is a very old idea from general equilibrium theory this type replication idea is actually very much what folks were looking at with the core and competitive equilibria in the 1960s the second class of models that folks have looked at our random preference models where we make some assumption about the data distribute the data generating process for preferences and think about what happens as we expand the market size and in kind of both classes of models we now have some understanding of of this small core phenomena okay so that's that's number six and that's related to the strategy proof in this idea let me jump back up to number three and number three is what I'm calling rural hospitals okay so I've chosen these names hopefully so that you remember this I don't know if I'm going to succeed on that but rural hospitals is this idea that I think you can remember by a story on the de that led to what's called rural hospitals so here is the debate so in the United States they're using deferred acceptance for medical students and what you tended to see is in many rural areas of the United States the hospitals are not meeting their capacity so I'm a residency training program that has ten slots and I only have say five doctors who are a match to me people were concerned well why is it that rural hospitals appear to be discriminated against they're not getting their quota is it because of the algorithm okay and what the rural hospitals theorem says and there's very different versions of this is that if I am NOT meeting my quota and I matched five people I will be matched those same five people in all stable matchings okay so you cannot blame the algorithm for the fact that I didn't exactly meet my quota okay so other versions of this are if I look across the set of stable matchings the agents who are unassigned are the same across all stable magics okay so there again if we want to minimize unassigned students don't blame stability as the concept okay so that's the third I think important result the fourth result is what I'm calling order independence okay so this is also actually not in the Roth Sotomayor book this is an important result because what it says is when I actually implement deferred acceptance on a computer the way I defined it here involves simultaneous proposals in each step right I could have equally well done this in an iterative way where I take a given student have him proposed to his top choice take another student have him propose to his top choice if he causes a rejection of that first student put that first student back in the queue you know take my second SUNY's tentatively he'll take a third student it could be a different student it could be the first student have them propose so on and so forth if I think about different acceptance as a recursive procedure of proposal and rejection I can iterate through students in any order and I will get the same exact outcome as the simultaneous proposing version of deferred acceptance okay and so this makes it very easy to implement deferred acceptance in practice I think it's one reason why we tend to see people discover deferred acceptance in the field because this is a maybe a natural thing let's just pick people one at a time according to any order have them apply to their most preferred thing and then pick the next person have them apply to their most preferred thing okay and you can see very quickly that the set of proposals and rejections from this iterative sequential version of deferred acceptance will be identical to the simultaneous version yep so so my model here I'm assuming we we start with strict preferences of students and schools yeah okay the last thing I want to tell you about is a result that's actually due to a mathematician John Conway and that's a result that tells us a bit more about the structure of stable matchings it turns out that we can take any two stable matchings and define the following operator take the two matchings pick the allocation that is better for one side and construct another matching so if I'm a man and I match to my first choice under one stable matching and my fifth choice under another stable matching I'm going to combine these two stable matchings for each men I'm going to look at which assignment I prefer so I prefer my first two my fifth and construct a matching where each man is assigned to his most preferred alternative and the flip of that each is each woman is assigned to or at least preferred of those two stable matchings and it turns out that that itself creates another stable matching okay so I have this way to take any arbitrary two stable matchings apply this join operator we can call it where I basically choose the better assignment for one side and I construct another stable matching okay and this is an important result for two reasons I think the first is it illustrates the supposing interest idea yet again right so I can construct a matching from two separate matchings by choosing what's better for one-side okay that's going to be a stable Mac so there's some unanimity in terms of what one side wants and what's good for one side is bad for the other side the other reason this is important is we've learned in the last you know 15 20 years that the mathematics of lattices are very powerful an economic theory and people have used those ideas to understand this structure of two-sided matching models in a lot more detail so that's one of the big achievements of this last literature on the generalizations of deferred acceptance okay great and so we've talked about small cores in large markets so here is my five-minute summary of this massive literature on two-sided matching models let me make one last comment something I've kind of glossed over so I said there's this marriage model which is the one to one matching model and then there's the college admissions model the many to one matching model in the many to one case if a call it has many seats we have to think a little bit carefully about how is the college going to evaluate groups of students okay and for all of this technology to work for all of these results to apply we typically need some additional structure on the colleges preferences over groups of students that structure comes in the form of some notion of a substitutes condition okay so that is students are substitutable for one another and once we assume some kind of notion of substitutes everything will work without that nothing works okay so it's a pretty sharp demanding requirements why is this important for practical applications if we worry about some kind of complementarities in a real matching market like it's really essential for me if I'm building say a school that I have both Eric and Ariel teaching at the school but I don't want either of them in isolation then we're gonna run into trouble with using these ideas okay if on the other hand if I like both Ariel and Eric at my school would but I'm also willing to take Eric by himself and Ariel by himself then in a good situation okay so that's what substitutes is gonna be imposing okay so now we've talked about one-sided match and we've talked about two-sided matching let me talk a little bit more about school assignment because this is a class of environments it's right at the middle of one-sided matching and two-sided matching it's right at the middle because it raises the question of what do we think of a school is a school someone whose preferences or priorities we need to respect do we think about them as part of the welfare calculation about allocations or our schools passive objects like houses for which maybe we don't care so much about the welfare of houses so so that's the first thing I've written here so the new question with school assignment involves what do we think about our interpretation of schools and their preferences so the dominant environment in the United States is schools actually do not actively rank students the ranking comes from some exogenously given criteria like do you live in the walk zone or do you have a sibling at the school so when we think about stability this idea that there's no blocking if a school is ranking someone based on say a lottery number maybe we don't need to care so much about an interpretation of stability coming from recon tracting okay because it's not the case that the school is going to go after the market is run and said well actually I wanted you and you wanted me if the school is just using a lottery number okay so in that passive object view of a school stability is maybe not motivated by a recon tracting motivation the motivation for something like stability could come instead from an equity concern so we don't want to have a situation where a student can say I'd rather go to a school and I actually had a higher claim to that school I say I lived in the walk zone and you assigned someone that school who doesn't live in the walk zone that would be something we may want to care about if we cared about respecting priorities in some sense what the literature calls that is a situation where we have eliminated justified envy okay so that's a mouthful but what does that mean let's break that down so a situation of envy is a situation where I would I'm envious of the assignment of someone else okay I'd rather get something that someone else got justified Envy means my envy is actually justified it would be justified for instance if I had a higher claim to that school okay so that sounds very much like a blocking pair and it is just relabeled for the case where we think of schools as passive objects and so if we have an allocation where we've eliminated justified and we have an allocation where there is no blocking pair we could call that a stable allocation but the literature tends to call this the elimination of justified Envy because they want to give or endow stability with this different interpretation okay so that's something that's an important new wrinkle here and this shows exactly the sense in which school assignment is in in between one sided and two sided matching the second issue here is something that was actually already asked what do we do in the situation where rankings are not strict okay yes yeah what's this oh okay huh yeah yeah from a social point of view how many students had justified claims they don't yeah yeah yeah so that there is that that's a beautiful question connect can I wait one slide and I'll tell you about a new result on that okay actually so but let me give you a little bit more context for that result so let's go back to our two algorithms that we've talked about deferred acceptance and top trading cycles right we know that deferred acceptance is going to produce an outcome that's stable and if we want to interpret schools as passive objects that will be free from justified envy top trading cycles will not do that okay top trading cycles because of you know that example that we just talked about we can have a situation where someone trades into a school by virtue of the fact that someone is pointing to them that allows for a situation where we have kind of overridden the priority right we prioritized trading of students over the property rights structure and so there's this real tension do we care about eliminating justified envy or do we care about efficiency okay and that's one of the things we need to resolve when we think about do we like deferred acceptance as a solution or top trading cycles as a solution so I'm going to talk a little bit about that more on the next slide but before I do it let me mention a couple more things okay and so these this is a second really interesting thing so these models we've talked about so far are assuming that preferences are strict when rankings are not strict we have a whole host of new issues to deal with okay so the first sense in which rankings are not strict is on the school side right so school side ranking need not be strict in practice the priorities are often very coarse like someone has a sibling out of school many people have sibling so how do we adjudicate claims between those applicants the walk zone concept so that's like a catchment area around a school many students are on the walk zone how should we break ties amongst that group okay and there are many ways to think about breaking ties but as soon as we start a model where the rankings are not strict we need to go back to first principles and ask which of our properties still hold and so there is a literature trying to do that and one of the kind of headlines of that literature is in the model where preferences are strict on both sides and deferred acceptance we have a unique optimal matching for the proposing side as soon as we introduce any in differences there's no longer a unique optimal stable matching for the proposing side so there's multiplicity there's a question of how do we resolve that multiplicity another very practical question is how should we break ties so there one possibility is we use the same random number at every school so say L Hana and I've applied to school a in school B we draw a one random number and I have a better number than upon on I will outrank him at a and I also outrank him at B the alternative is maybe we draw separate lottery numbers at a and at B and the question is what's better okay and this is a question that I can say in every school district I've interacted with this question has come up so this kind of fun because this is a question I don't think we would have asked had we not actually talked to school districts about their matching protocols and there are results that argue that having one random number tends to be better than having a separate random number for each possible school great okay yeah Ariel yeah yeah yeah why do we additionally have that in the mechanism yeah that's a great question so you're absolutely right if you look at the patterns of choice people care a lot about proximity right so in some sense that's baked in to the allocation people will be assigned as schools close to home because that's that's what they want one rationale for walk zones actually comes back to the big debate about why do we have a choice system to begin with and you know there's a sense in which we want to give extra priority to folks to attend schools in in their neighborhood so I could flip your question on the head and say why don't we have a hundred percent of seats use a walk zone right if we want people to go to schools close them that's what people want why don't we try to respect that claim right and the way that I tend to see this actually play out is walk zones emerges some kind of compromise between these two factions so one faction who says I don't like choice at all I just want to have a neighborhood school system where I go to school down the street the closest school to where I live and another faction that says that's not fair that's particularly not fair for the neighborhoods that don't have very good schools so why don't we have some notion of a walk zone where some fraction of seats are reserved for kids from the walk zone so this is typically a political compromise the same question you could ask for any of the priorities actually why do we have a sibling priority you know it should be baked into preferences if parents want to send their kids to the same school they would rank the same school in some sense we want the system to honor those claims and maybe prioritize those claims that's why we have a sibling priorities so that that's an additional lever I will say you know the hot button issue in districts with these choice systems involves this priority design question what is a fair way for children to be admitted into schools so Boston for instance and we'll talk a little bit more about this used to use a walk zone system so every school half the seats were reserved for kids from the walk zone and in 2014 they said we're going to do away with walk zones there's no more of a walk so people are always tinkering with this lever and it's really kind of a this equity district distributional consideration that they're thinking about another place where this is very very active if you look at the US press right now there are very strong debates on should we have test based criteria to admit children into schools so that's something that several cities most prominently New York City is actively considering so the mayor in New York City came out a couple weeks ago and said we have schools that admit children based on test scores that's not fair I want to get rid of this at least for some fraction of the seats is that a good system or not okay okay so let me come down to a Holland's question so this question about deferred acceptance versus top trading cycles what do we know in terms of the trade-offs between these mechanisms so let me tell you about a few results and then I'll tell you about something that's a bit newer that we've understood about this so the kind of starting point is there is this tension between getting to an efficient outcome and getting to an outcome that's free of justified envy and that tension was first shown in an example by Roth in 1982 which said it's possible that we have a matching that's free of justified Envy that's not Pareto efficient so because that exists there is no mechanism that is going to be both Pareto efficient and without justified to envy so you could ask for something a little bit less demanding can I find a mechanism that is strategy proof that selects an outcome that is Pareto efficient and free of justified Envy if that happens to exist okay so we know that doesn't always exist but suppose we're in a economy where that exists is there a way to get there and what Caston shows us no there's no strategy proof way to get there okay so the kind of logic is if I'm thinking about a allocation system and my kind of ranking of axioms is is the following I care about strategy proof finish first and then I care about eliminating to fight envy and then I care about efficiency you could think of the results of gal and Shapley that there is a student optimal matching as a natural recipe for us okay I run the student proposing deferred acceptance algorithm that's going to be strategy proof it's going to be free of justified envy and within that class it is going to be the constrained efficient allocation that is free from justified envy okay so the argument went if we value the elimination of justified envy first and then Pareto efficiency deferred acceptance is a natural choice what we don't know is suppose our preferences were different we cared about Pareto efficiency first and then the elimination of justified envy what is the good choice of a mechanism ok so put another way I can give you a formal basis for choosing deferred acceptance as solving some kind of constrained maximization problem can I give you a similar basis for top trading cycles ok and so you could say well what else would you do well I said top trading cycles is strategy proof and it's efficient in this context I haven't given you any formal sense in which how it uses priorities right so if I said we want something that's try to do proof inefficient you could tell me why don't we just do a serial dictatorship in the context of school ISM that's also strategy proof and that's also efficient and there's something uncomfortable about that in a serial dictatorship we're not really using the priorities right in top trading cycles the priorities set up this property rights regime which is the basis for trade right and a serial dictatorship it's the serial order that determines everything so what I want to tell you about very briefly is a some work trying to give a formal basis for top trading cycles and to do that I'm going to introduce this idea of a problem wise comparison as follows so suppose I have two mechanisms SCI and Phi I will so that Phi has less envy then sigh for a given set of priorities so that's what the this notation refers to if for any set of preferences P and student school pair is if student school pair is block mechanism by then student school pair is block mechanism sigh okay so what am I doing here I'm coming up with a way to say one mechanism has less envy than another mechanism and that is a comparison that is a problem by problem comparison okay and I'm going to say if there's ever a blocking pair under one mechanism that blocking pair has to be there under the other mechanism okay so this is a subset relationship I'm looking at the set of blocking pairs this is not an account a Bocking pairs and we can think about a notion of having strictly less envy so we'll say Phi has strictly less envy then sigh if Phi has less envy than side but side does not have less NB then Phi okay and finally we'll say that Phi minimizes Envy if there is no mechanism sigh that has strictly less Envy than Phi okay so this is an ordering that I'm proposing and the reason I'm giving you this ordering is for the following result okay so it's a partial order yeah exactly yeah you know this is actually related to some work you did with Das Gupta I I think we should talk about that at some point by the way with your unanimity result you had I'm gonna come to another thing that's related to that so I'd love to talk about that offline so let me tell you about the result okay so here is a theorem so suppose each school has one seat okay that is a very strong assumption okay and something I'll talk about in just a second then if Phi is a Pareto efficient and strategy proof mechanism if Phi has less envy than top trading cycles for a given set of priorities and it must be the case that the outcome of Phi and top trading cycles is the same okay maybe put in a more intuitive way what this result tells us is that top trading cycles minimizes envy in the class of Pareto efficient and strategy proof mechanisms okay and what you can show is that another natural mechanism of serial dictatorship does not okay so you can think of this is the dual of the Gale Shapley result right Gale Shapley says deferred acceptance is going to give me the most efficient and be free justified envy free allocation this is saying in the special case where each school is one seat top trading cycle is going to give me the Pareto efficient allocation that minimizes justified Envy okay yep we have a counter example let me tell you about that let me jump to that question here actually so for us to show this we definitely need each school to have have one seat when you have schools with more than one seat like the models that were motivated by there there is no sharp characterization of the env minimizing efficient mechanism we know it something has to exist because everything here is finite but there's no natural characterization of that you can say something if you make more assumptions so if you think about the random preference model that I just briefly mentioned you can share a result that top trading cycles has sorry less justified envy than serial dictatorship and if you actually look at the data and from cities like Boston and New Orleans and compare efficient allocations computed by top trading cycles and thorough dictatorship you see that there's significantly less justified Envy from a serial that from a top trading cycles than a serial dictatorship and now we know of course deferred acceptance would have no justified Envy but it's not going to be Pareto efficient okay so this result we draw Pareto efficiency we know we can find a way to minimize justified envy so instead we impose Pareto efficiency there's a choice of mechanisms and you can use this result to say somehow TTC is standing out in that class of mechanisms okay so let me now spend the last 15 minutes or so talking about the fourth important mechanism in this literature you have question of the students correct yeah there it would be preferences are strict on both sides so if preferences of schools for instance some of the schools are ranking kids like say in New York City about a third of the schools actually interview kids and have them go through auditions or take specialized tests but the remaining are not ranking kids so there's some kind of indifference you could say it's borough specific priority or sibling priority in that model if we thought of both sides students and schools it's not the case that deferred acceptance is Pareto efficient so that's just another sense in which as soon as we introduce some know some form of in differences we have to be very careful about these properties right but you're absolutely right if we have strict preferences on both sides and we care about both sides deferred acceptance is Pareto efficient okay okay so let me spend the last couple minutes here now talking about the Boston mechanism and I always like to show this picture from Boston history whenever I talk about this mechanism because it goes to the question I think Ariel had asked about a second ago why do we have these priorities where does this come from okay so you know from those of you who are not from the US this is a very iconic picture in American history this is a picture from government Center in Boston where there's a big protest in the 70s in Boston involving school assignment and this is not unique to Boston but the situation was probably most tense and in Boston where the courts came in and said even though the law says you cannot have segregated schools the schools are de facto segregated so we're going to introduce a form of busing where we're going to send minority children from neighborhoods like Roxbury into wider neighborhoods of South Boston and vice versa okay and the city reacted quite harshly to this a lot of people left Boston and here is an individual about who was Ted landmark he's still in Boston a famous character in Boston history about to get impaled by the American flag and you know roughly speaking the one group is in favor of neighborhood school schools close to where you live another group is in favor of integration and the expansion of choice to deal with inequities across neighborhoods okay and if we fast-forward to the 20 years after this picture was taken the city of Boston came up with an assignment plan that is known as the Boston mechanism and it's known as the Boston mechanism in part because this is one of the few districts that actually publicized what their rules are okay so the you know the history in Boston is so layered and complex the district has been quite transparent about what rules are using and many places are not as transparent what is the Boston mechanism so the Boston mechanism is also called the immediate acceptance algorithm and that's to create a contrast with deferred acceptance so in deferred acceptance we defer everything until the very end so I can displace Eric even though I've ranked something 12th and Eric is ranked at first under this procedure that you can't do that okay so let me read to you how this works in round one we're only going to look at the first choices of students we're going to go to each school and consider the students who have ranked at first and assign students one at a time according to the priority order until there's no seats left or there's no student left who's listed as their first choice excuse me so if Erica's applied their school first and he's high enough priority he will be assigned to that school okay and he's immediately accepted okay in the generic around in round K we'll look at the students who are still not assigned and look at their case choices for each school with still available seats look at students who've ranked at caithe assign them one at a time according to the priority order until there are no seats left or there is no student left who's listed as a Kate's choice okay so this mechanism is putting a lot of weight on what schools you've ranked first it's not going to be the case that I can displace Eric if I've ranked at 12th and he's ranked at first even if I have the highest priority at that school in this mechanism the fact that he's ranked at first will trump any priority that I have and that creates this complicated strategic calculus that we need to think about should I rank a school first that I may not get maybe and don't have a high enough priority for or if I do that should I have a safe second choice perhaps I shouldn't even waste my first choice on that popular school and choose something that's a safe choice as my first choice so this is clearly not a strategy proof mechanism and this is something that is understood by participants at least some participants okay so here's an example of the kind of information that's given about this mechanism so this is what Boston used to advertise to families every year when this mechanism was in place in their school brochure for a better chance of your quote first-choice school consider choosing less less popular schools okay my favorite story comes from the West's own parents group so this is an online google group at the time that used to meet to discuss heuristics on ranking in the Boston mechanism so they are frequently asked questions and their introductory meeting minutes states one school choice strategy is to find a school you like that is under subscribe and put it as a top choice or find a school that you like that is popular and put it as a first choice and find a school that is less popular for a quote safe second choice okay so this is a heuristic that as emerged and you know broadly speaking there is I think evidence of some sophisticated behavior by by some players and unsophisticated behavior by others lots of evidence in Boston for instance that a substantial fraction of applicants have ranked to very popular schools as their first and second choice that's not a great idea in this mechanism because if your first choice is very popular you might not get it but your second choice being very popular means that it will have filled up with people who've listed it first right so if someone had that rank order list and knew that those schools were going to be heavily oversubscribed it would be inadvisable to rank that second choice school as a very if it's a very popular school you have questioned the these kinds of strategies well different acceptance as a strategy proof mechanism so certainly not this kind of advice so right now in Boston for instance they say you should rank your schools truthfully it's the best you can do that's the quote is something like New York City has a similar advice like that there is a separate question what do people understand right so that is a point I certainly take and you know there's some lab evidence that people point to there's also some survey evidence that even within strategy proof mechanisms people may not understand that its strategy proof and they may be using some heuristics that that make no sense but the appeal of a strategy proof mechanism at least you can give clear advice that yeah you won't be able to give otherwise you have question for the Boston mechanism so you know it's a great question we still think this is the most popular assignment mechanism in the world I think this is a very intuitive idea let's try to give everyone their first choice okay and you know in round one look at first choices try to assign first choices that's where I think this comes from this is from you know these aren't algorithm experts coming up with these schemes these are district officials who have come up with this scheme right right so why not you know it's not fair for me to displace Eric if I've ranked at 12th and he's ranked at first maybe Eric should get into that school what that's missing is that creates this kind of strategic pressure on us to rank schools so I don't think is that unnatural correct that's another thing I mean we have to think about preferences being submitted but for the submitted preferences this will be an efficient outcome whereas deferred acceptance will not I have yet another rationale that I'm gonna give you actually for why Boston may continue to persist okay and that has to do with a political economy of having a manipulable mechanism okay so suppose we have players who are sophisticated and those who are not sophisticated one of the comments that the superintendent of Boston made about the debate in the assignment mechanism that took place in the 2000s is the following now superintendents don't talk like this so this was definitely after a lot of interaction with people who study this he but he said the following point which I think resonates a strategy proof mechanism levels the playing field between those by diminishing the harm done to parents who do not strategize or do not strategize well so he's kind of thinking about protecting the innocent as a rationale and so we can be a little bit more formal about that idea by considering a model where we have sophisticated and unsophisticated players and we'll take this a premise that the sincere player so you can't call her players unsophisticated when you're talking about public school families so that's an important lesson I learned when talking about this the sincere players are restricted to only report their true preferences whereas we'll say the sophisticated players best respond okay so these are highly sophisticated players and we're going to consider what happens in the game where you have these two types of players under the Boston mekin is and then what happens under the deferred acceptance algorithm and let me just kind of get to the the point here what you can show in this model are the following three main kinds of results okay now the first is we can characterize the equilibrium outcomes of this Boston game in terms of a economy where we take the priorities at schools and say any sincere student who's ranked at school second or lower is getting demoted in the priority ordering relative to a sophisticated student okay so if I do this transformation and construct what we call the Augmented economy where basically we demote sincere students at their second choice and lower in the priority ordering and use the original priority ordering within this choices of students then the set of stable matchings of that augmented economy is equal to the set of Nash equilibrium outcomes of this game so the lesson that comes from that is you know because of this manipulation possibility of in the Boston mechanism the sincere guys are effectively losing their priority to sophisticated guys at their second choice or lower okay the second thing you can show in this model is if I focus on the assignment of a sophisticated student in the best Nash equilibrium the Pareto dominant Nash equilibrium of this game that's going to be at least as good as her assignment under the dominant strategy equilibrium of deferred acceptance so to an honors question why would you have the Boston mechanism what this result says if we take the model literally is that sophisticated students get some type of strategic rents from knowing how to manipulate or how to participate game the mechanism at the expense of sincere students okay and so why do Boston type systems persist well maybe some families have invested in learning how the mechanism works and they don't want to lose that advantage that they get okay so that's maybe another story you know when when the policy decision happened in Boston the leader of the Westone parents group that that quote I just actually got up and made the claim we shouldn't change the mechanism we should give us gift families more resources to make more sophisticated choices so that that's consistent with that and so that that's a yet another reason no this is the model I think Nikhil is going to talk a little bit more about data and what we actually know about these issues how important is this trade-off between sophisticated and unsophisticated students exactly what are the welfare implications of the Boston mechanism is it really so bad in practice let me spend so it's almost I'm almost out of time I want to talk about a couple more things because every time I think the literature on the Boston mechanism is done there's a new place where something Boston Laika emerges so here's a new setting that I stumbled upon a couple of years ago where in Taiwan they came up with a new assignment mechanism as part of their comprehensive reform of their education system okay and several articles came on in the local press documenting major protests in Taipei and other cities with regards to the Taiwan mechanism okay so these protests so fortunately I'm working with a student on this project who can read that Chinese language I can they're translated as fill out the school preference form for us it's like gambling another protest is abolished and ranking order deduction so what is the Taiwan mechanism so here's how this works and it's very much Boston like in Taiwan every child has to take an exam okay they have a single exam and the officials in Taiwan came up with a following brilliant idea you could say why don't we take the test scores of kids and modify the score is based on how the school is ranked okay so if I scored a hundred honest on the exam will use my score of a hundred for my first choice for my second choice I'm going to did doc ten points from your tests so we're gonna act as if your score was ninety okay for my third choice I'm gonna do doc twenty points so will act like your score is eighty okay so that's this deduction schedule so and you go on the websites and Taiwan all of the 15 districts in Taiwan have different deduction rules so in Taipei it's just a one-point reduction so my hundred becomes 99 for my second choice my third choice becomes 98 and this is what they're protesting about it this becomes kind of complicated do I think about you know using my high score for a school that I might not get into if I don't I'm gonna face this deduction I'm gonna get taxed for a lower ranked choice isn't one thing that's neat about this is in the environment where there's no deduction this is deferred acceptance right in the environment where we make the deduction very very large this is the Boston mechanism right because in the Boston mechanism first choices always beat second choices okay so you can ask the question and this is what we do can we think about the properties of this mechanism okay in particular you know one thing we can show is if you did docked more points from each choice the mechanism becomes more manipulable okay it becomes more game Abul and of course in the limit this becomes a Boston mechanism so the Boston mechanism is the most manipulating this class of Taiwan mechanisms yeah before actually so yeah yeah yeah so in principle you can do as far as I know this is persist for the last three years they're still using this this mechanism in the field you know again why do they do this I don't know if this doesn't seem like a great idea I mean there is some sense in which it's complicated to rank choices and I think some of these ideas are used to simplify the ranking submission problem or you could think of better ways to do that but here they're making you think very hard about what schools you actually rank because of this deduction thing that could also be a rationale for the Boston mechanism alie you had a question I mean we'd have to think about a richer model I mean the quick answer is of course we're only focusing here on just allocating people into you know seats in a classroom so if we thought about the funding of those classrooms or you know that comes a little bit to areolas question where do these priorities coming from what are the goals that we're trying to achieve in the background here then we think a bit more about these mechanisms the one thing I will say is I think it's important to have a strategy proof mechanism at the heart of this and then tinker with those levers because by having a strategy proof mechanism we may be takin some of the complexity off of the parents and we can ask these counterfactual questions and think about these issues more clearly so priority of design I think one reason why Boston got rid of walks on priority for instance is now that they have a strategy proof mechanism they can actually understand what the consequences of different walks on priorities are are ya yeah and in its a continuum now right as given by these deduction points exactly if you if you believe that Boston represents some kind of optimum but you know I do I really believe that I give you a rationale for why it may exist would I recommend the Boston mechanism no I wouldn't in practice right so and just like here in Taiwan if the issue is we want to help people make a limited number of choices I think there are many other instruments to do that then putting the strategic complexity on to parents let me show you about one last thing okay just and this is another kind of amazing story I think about this Boston idea and this comes from the city of Chicago so here's an article from the Chicago sun-times describing their admissions process to their elite college prep so these are testing schools in the city of Chicago they say high scoring kids were being rejected simply because of the order in which they listed their college prep preferences I couldn't believe it it's terrible CPS officials said Wednesday they've decided to let any 8th grader who applied to a school we rank their preferences to better conform with a new selection system okay previously some eighth graders were listing the most competitive college preps as their top choice for going their chances of getting into other schools that would have accepted them if they had ranked those schools higher so hopefully by now you hear the word Boston mechanism in that paragraph right in the old Chicago system they said we're going to look at test scores and first assign everyone their first choice okay and continue as much as possible till a school is filled then only will we consider second choices so it can happen that Eric gets into a school that he's ranked first over me who's ranked at 12th even though his score is a zero in mine is a perfect score right in this mechanism right and that's what they're saying is terrible okay so what the officials did in Chicago as they changed the system actually 15,000 letters went out to students throughout the district and they said we're gonna actually do a serial dictatorship where we simply order students by the test score the admissions exam whoever's got the highest score gets his first choice whoever's got the next highest choice gets his first top choice so on and so forth and what's kind of unusual about the Chicago experiences in the old mechanism you were allowed to rank up to four schools out of eight in that first year and they continue to do that restriction in the new mechanism okay so this is unusual because I said a serial dictatorship has these very nice properties when you restrict the number of schools you can rank all those properties go away so it's no I think you know this is the thing we've been talking about it's there's some notion of complexity that we don't have like a formal language to talk about so yeah so I've made that claim to Chicago after learning about this and they said thank you professor that's very kind I didn't hear from them for another year and they said okay instead of having four choices we're gonna allow you to rank six choices and what you can show and I won't go into the details is you know neither of these mechanisms of strategy proof but there is a formal sense in which this is less manipulable than this mechanism moreover this mechanism where you can rank four choices is more manipulable than the mechanism where you can like six choices and of course we have the ideal strategy proof inefficient mechanism in this domain when there's no constraint on the number of choices okay so that's that's what this is about here when I'm skipping also just in the interest of time and I'll wrap up is another case in which the Boston mechanism was condemned and that happened in England so we can talk about this at the break if you're interested it turns out that in England they had independently discovered deferred acceptance in many regions and through an act of Parliament in 2007 they actually outlawed the Boston mechanism and Parliament in England they call it the first preferences first mechanism and most districts and England use what's called equal preferences which is Queen's English for deferred acceptance so so we won't have time to talk about this and you know we we mentioned this a little bit you know we've seen that the Boston mechanism has been rejected in a number of places you know midstream in Chicago is banned by Parliament and England yet it's still widespread why and one reason is its intuitive and another is a strategic rents idea there's now an empirical literature that's trying to put some quantitative magnitudes on the trade-offs involved in these mechanisms and I think the keel is going to talk a little bit more about that so let me wrap up with some of the things I wish I had time to tell you more about which are active areas in matching theories so one thing I'm particularly interested in is actually related to Ariel's question where do these priorities come from what are a good priorities how does how do these relate to kind of broader aspects of the market kind of as Olli was was saying so that's particularly germane and debates about affirmative action policies so if you guys looked at the New York Times this morning the Trump administration offered some guidance that says you can't you cannot use explicit racial criteria in K through 12 public school admissions there's always this back-and-forth on what's exactly allowable so several districts have experimented with kind of race-neutral alternatives to race-based affirmative action there's a host of very interesting issues to study there other directions where things are quite active involved pushing the limits of deferred acceptance thinking about incorporating prices into different acceptance static versus dynamic models so Nikhil will talk a bit about kidney exchange that's a place where dynamics are quite important and this literature's are often inspired by very practical applications so that's something that continues one of the most exciting domains people are working on now or involve refugee assignment issues related to ways refugees get placed into different countries and within countries okay thank you for giving me a couple extra minutes let me stop here and I can take questions at the break [Applause]