***Update 15 Oct 2012***
Lloyd Shapley and Al Roth are co-winners of this year's Nobel Prize in Economics for their work on matching mechanisms!!! Well deserved award.
Washington Post writeup here.
Marginal Revolution writeup here.
Nobel Prize writeup here.
What the are market design and matching mechanisms fields? I guarantee that most economists have no idea. Read below to find out. Lots of links and examples to impress your friends and colleagues at the water cooler.
8 Sept 2012
Nearly two years ago, while studying in Chile, I began research for my thesis and came to know and love a niche field within economics known as matching mechanisms, itself a sub-field of market design. There exists a very small group of academics working on these special problems and by the good fortune of a random conversation with a professor I was let in on a small secret.
(Throughout I have linked several articles from author's websites and suggest skimming the introduction and conclusions to get an understanding of the dilemma. Only after reading and comprehending Gale-Shapley (1962) would I recommend delving into the theory and analysis of these works.)
To give this some context there are probably several thousand serious economists working on macroeconomic issues such as monetary policy, international trade, growth, etc. At last year's National Bureau of Economic Research Market Design Working Group meeting there were probably 30-40 economists and computer scientists working on market design problems, maybe 10 of whom were dedicated to the investigation of matching mechanisms. My best guess is that these researchers represented about half of the entire field. Niche indeed. Some of the titans I had the pleasure to meet: Tayfun Sonmez, Susan Athey, Al Roth, and Parag Pathak.
I have put off blogging about this for a while because matching mechanisms can be difficult to explain. Market design research gets heavy into math proofs. The notation in the journal papers is especially difficult to follow. Regardless, the purpose of the writer is to make the complex a little less convoluted and marginally more accessible. If I am worth anything at all as a blogger then nearly anyone ought to be able to read this post and walk away with an appreciation of and at least a little knowledge about matching mechanisms. Matching mechanisms are especially interesting because of their use everywhere around us.
Start with a fundamental problem of economics, the creation and sustainment of a market. Market designers study how supply and demand interact to exchange goods and services and in the case of market failure conduct an autopsy to understand what went awry. Market design is essentially social engineering and is especially relevant to and heavily studied by all the e-commerce heavyweights such as eBay, Microsoft, Amazon, and Google. Market design experts ask how should a good be sold and bought? Through an auction? Should sellers present buyers with price-quantity offers or should buyers make proposals to sellers for a certain price and quantity? How much information about myself or the seller should be revealed to the other party? Can I weigh multiple offers at the same time or do I have to accept/reject them sequentially?
Another challenge market designers confront are marketplaces without a price system to allocate goods. Almost everything economists espouse as being great about the free market is possible because of the liberal movement of prices and the information conveyed by them. What happens when there are no prices? How do goods get efficiently or inefficiently allocated? Why would there even be markets without prices?
Here are some examples:
School Choice: There are public schools and there are students. An encouraging movement afoot in the USA is to allow families control as to where their children attend school. Obviously not every student can study at the school with the highest rating. Current policy does not allow families to pay for admission into public schools nor do cities permit public schools to pay top students to attend. In the absence of prices, what is the best, most efficient, fair, equitable, and easiest way to match students desires to the limited supply of seats in schools?
Organ/Kidney Transplants: If one need a kidney and could find a willing and suitable donor then there is no problem. But what if one has a willing but unsuitable donor? That is to say their blood types are not compatible or some other complication. In the absence of prices to clear the market (i.e. pay donors for their kidney) we need some way to match up patient-donor pairs with other pairs in similar situations. Even in the absence of prices we could still create a market to match donors and patients. There is also the problem of how do we move kidney's around and prevent people from breaking their promise. For example if Tom and Joe are a patient-donor pair and Kelly and Sara are another, do hospitals allow Joe to donate his kidney to Kelley in Boston and then have Sara travel to NYC to give Tom her kidney? Could one imagine the legal and moral quandary if en-route to NYC Sara had second doubts? To solve this issue hospitals do the kidney transplants simultaneously and some are now preparing to do exchanges with three or more pairs of patient-donors.
Doctor-Residency Programs: In the middle of every March, medical schools are abuzz with excitement as soon-to-be doctors find out which residency specialty program they will attend upon graduation. One would think that this labor market would function like any other....workers apply for work, negotiate wages, some are accepted some rejected, firms bid to highly skilled workers etc. However this market is unique because there is a fixed start date (usually June) by which all the new doctors need to be matched up to a hospital-specialty. Residency programs do not have rolling start dates....either begin work in June or wait another year. In the past this created chaos as young medical students received offers from hospitals and had to weigh the benefit of accepting the one on the phone or holding out for their dream job and the possibility of getting nothing. The law clerk industry is going through this right now as some judges are uninterested in giving up their market power for the sake of the labor market as a whole.
Cadet-Branch selection and link here: The military academies typically follow a simple method to match graduating cadets to their career specialty. The top ranked cadet gets to choose first among what is available and for which they qualify (females cannot choose Infantry, Armor, or Field Artillery and one must pass a medical exam to be a pilot). The next ranked cadet chooses and so on. The final cadet gets whatever is left over. The branches have no say in which cadets they prefer. A universal cadet ranking determines the priority listing. Presently, the Army is attempting to help cadets who are more likely to stay for longer careers into the specialties that will make them more satisfied. Cadets who are willing to pay an extra three years will be given priority over other cadets for the branch selection. This is what I studied for my thesis and the Army's unique, albeit imperfect, solution is a combination of a matching system and an auction. Studying this system gave me the feeling that I was observing the birth of price theory as this is an example of a very primitive market without prices in transition to one with a discreet set of two prices (5 versus 8 years of service).
These problems seem solvable enough but I promise that they are a lot more complicated than they look. Beginning with the end in mind we want to be sure that the matching results will have certain characteristics. Some of them are:
a) fairness: those with higher priorities will match to their desires over those with lower priorities. In the public school match it is typical that students with siblings already in a particular school will have priority for it or if a school is located in their neighborhood they will have priority. So we would want to see kids who prefer their neighborhood school to get matched ahead of kids from elsewhere.
Also b) strategy-proofness: the process should encourage people to display their true preferences. There should be no advantage or way to game the system by lying. Some people will be more sophisticated and have more information than others. Doctors should list the hospitals they want to work at in the order of their true preference instead of playing the thought experiment..."Well I really want A but I'm not sure if I'll get in so maybe I'll list B and C first to increase my chances of getting those". The Chilean university system suffers from this problem. If a college bound student does not list the Catholic University program in their top two choices then the university will not consider them for acceptance.
Finally, sometimes we want c) Pareto efficiency: once the match is complete I cannot make any changes to improve someone else's match without hurting someone else. That is if Cadet X gets infantry and Cadet Y gets armor but they would rather switch and both be better off then the match was not Pareto efficient.
Surprisingly the answer to most of the above problems can be found in a paper that is essentially the genesis of this field....Gale-Shapley (1962). The ideas in the paper are very simple. Again, the notation can be difficult but once one becomes comfortable this entire field is mostly accessible to the non-economist. In this paper the authors lay out a solution to most of the allocation problems, the deferred acceptance algorithm. This algorithm takes the preferences from both sides, the students and the colleges, the doctors and the hospitals, etc. and obtains a match which creates the most social benefit.
Using the school choice problem as an example the deferred acceptance algorithm can be imagined by all of the students on one side applying to their most preferred school on the other side. The schools conditionally accept their most preferred students of those who applied and reject the others. Those students who do not have a conditional acceptance then apply to their second-most preferred school. Again the schools evaluate the students whom they have conditionally accepted with the students who are applying to the school now, accept the students they prefer up to their capacity and reject the others. This process continues until all the students have a conditional acceptance at which time the matches become final. We use the words "apply", "accept" and "reject" somewhat misleadingly. Because students have listed all the possible schools in order of preference and the schools have their lists of preference over all the thousands of students this entire process takes place in the time required to run a computer program, a few min. Nobody gets acceptance or rejection letters or told that they have been conditionally accepted unless a more preferred student comes along. The algorithm simulates all process and knows what a student's next-most preferred school option would be if the previous one were found unavailable.
The example above is actually the student optimal deferred acceptance algorithm. This matching mechanism guarantees the best global outcome for the students. We could have run the algorithm where schools propose to the students and the students conditionally accept or reject schools. This would result in the best matches (globally) from the perspective of the school as it would guarantee that each school would receive more of the students that it most prefers compared to the student optimal deferred acceptance algorithm.
(The Air Force could transform some of its personnel programs by incorporating matching mechanisms. For example, one could imagine using these for assignment matching instead of the opaque process which takes place at Air Force Personnel Command. When a member nears the end of their current assignment they are presented a list of all the assignments across the spectrum for which they qualify based on rank, past assignments, qualifications etc. Likewise the commander of each billet that needs to be filled is given the relevant data on members who qualify for that position. The members rank all the assignments by order of preference. The commanders of the billets rank all the members by order of preference. AFPC need only be the gate keeper of the algorithm and ensure that the matching is satisfactory to the Air Force as a whole.)
Market design and matching mechanism practitioners have been around for a short time. Until about fifteen years ago there were only a handful of economists working on these problems and were considered oddballs. Now there are top students coming out of the best PhD programs able to take up these issues and be considered serious by the profession. A young economist looking to make their mark would find a welcome place in this area with no shortage of work.