In 1994 when my son was about to reach kindergarten age, I realized there were  glaring problems with the way the Minneapolis Public Schools operated their school choice placement program. With a bit of research I discovered a solution, patterned after the National Resident Matching Program that matches medical school graduates with residency programs in the U.S. I proposed this method to the school district. Although the guy who ran the school lottery program recognized that this would be a significant improvement, the idea never went any further due to bureaucratic inertia.

A couple of decades later, the problems I identified still exist. So does the potential solution. In fact, the designers of the NRMP algorithm, Lloyd Shapley and Alvin Roth, won the 2012 Nobel Prize in Economics for their work.

 

Mr. Denny Lander
Minneapolis Public Schools
807 NE Broadway
Minneapolis, MN 55413

Feb. 21, 1994

Dear Mr. Lander,

I am a computer consultant and (more importantly) a Minneapolis parent.  My son will be entering kindergarten in the fall of 1995.  My wife and I feel that choosing the right school for our son is important, and since we don’t want to be rushed in the decision we have already begun investigating the options available to us.

As I’ve talked with other parents who are going through this process, I’ve become aware of a dilemma that confronts many parents.  Certain schools are very popular, and the chances of  getting into them are slim.  Parents who list such a school as their first choice are not likely to get it.  But worse, because of the way the placement lottery works, they also take the risk that their second choice might fill up during the first round. Parents who list three popular schools as their 1st, 2nd, and 3rd choices are unlikely to get any of them.  They might therefore choose to list as their 1st choice a school that actually falls considerably further down their list of preferences.

This has undesirable consequences for both parents and the school district:

• Parents who understand the system are put in the uncomfortable position of weighing the odds.  They must decide whether to gamble or play it safe.
• These parents have to decide without sufficient information.  Since there is no way of knowing how many people will apply to each school, it’s difficult to evaluate the risk involved in requesting a popular school.
• Less sophisticated parents who naively list a popular school as their first choice are, in effect, penalized for their lack of understanding of probability.
• The school district receives invalid information about what parents want because many people are likely to list school choices that do not reflect their true preferences.

I believe there is a solution.  The National Residency Matching Program (NRMP) manages the placement of  medical school graduates in residency programs at hospitals around the US.  Applicants rank hospitals in their order of preference.  The matching algorithm works in such a way that applicants do not need to know or worry about their chances of getting into particular hospitals;  they are free to honestly rank their preferences without regard for the odds.  In fact, doing so gives an applicant the best possible chance for getting a hospital he or she likes.

This algorithm is perfectly suited to public school placement.  The only significant difference between the two situations is that hospitals submit their own lists of preferred applicants in rank order.  The public schools do not do this;  however, they do something similar by giving preference to siblings, children with special needs, etc.  A public school’s preference list can be generated automatically using these preference rules and random assignment of rank order within each preference group.

The beauty of this is that it requires no change at all from the viewpoint of parents.  They will still rank order their preferences just as they always have. The process actually becomes simpler for parents, because they no longer have to worry about the odds of getting into particular schools.  Of course, it would be good to publicize the change in algorithms so that parents know that they are now free to list their honest preferences.  And it might be desirable to allow parents to list more choices (say, up to five) in case their top three choices are all popular.

I’m enclosing some information that details how the matching algorithm works.  I hope you will take a few minutes to look it over and give me a call.

Sincerely,

David R. Woolley

 

The NRMP recently posted a new explanation of how the matching program works. But the following fable the NRMP published in the 1990’s also illustrates the process in a very easy-to-understand way.

 

The Matching Tale

How it started…

Once upon a time a shoemaker was in need of an apprentice. To find one, he went to the fair, set up his booth, and began extolling the virtues of his profession. Soon the young men gathered around him to sign up. The next year the plumber and the carpenter followed his example, as did the butcher, and various others. Over time, the fair became quite chaotic, and it was not easy to determine which of the conflicting claims sounded the best. Some groups took their booths outside the fair so they could catch fairgoers before the others did.

This went on for many years. Some of the young men learned to manipulate the system. To get the best place at the plumber’s booth they sported a button “I Love Plumbing.” As they walked to the next booth, they quickly turned their lapel showing another button with “I Love Carpentry.” Over time, someone thought, “There has to be a better way!” That is why the current system evolved.

First, it was decided that no contracts could be signed on the spot. During the fair everyone walked around with a notebook comparing the best of the preceptors and each of the applicants had to offer. After the fair, all went home to study their notes. A week later, they gathered again at the town square. Benches had been set up on either side, one side for the preceptors, one side for the future apprentices. In the center stood the town clerk, who had given each preceptor some tokens, one for each apprentice position he wanted to offer.

At the meeting…

As everyone was seated, the town clerk asked for silence and called the first preceptor. The first preceptor had three tokens. He looked at his notebook, and offered one token each to the three applicants at the top of his list. The applicants accepted the token and bowed politely. Then the town clerk called the second preceptor, then the third, fourth, and so on.

When the fifth preceptor stepped forward he offered a token to one of the youths who had received a token already. The youth stood up and said, “Thank you, Sir. I’m honored, but I already have a token that I like better.” The preceptor looked at his notebook and offered the token to the next one on his list.

Several preceptors later, another youth also received a second token. This youth replied, “Thank you, Sir.  I already had a token, but I prefer yours since you are closer to where my sweetheart lives.” The youth accepted the new token and handed his first token back to the town clerk, who returned it to the preceptor who had given it out earlier. That interrupted the sequence for a moment, since the earlier preceptor now had to look in his notebook to determine the next person to whom he would offer his token.

As the day progressed, this happened more often. Each time an applicant received a token that was higher on his list, he accepted it and turned in the earlier token;  that token then passed to someone else. In time, many applicants received better offers and were able to get closer to the top of their list. Several preceptors had to go farther down their lists than they had planned, but all were pleased with the way the town clerk conducted the meeting. There was no more screaming and yelling to get to the front row.

What happened…

This is how the first matching program was born. Let us take a look at some of the things that happened and at those that did not.

1. First, the town clerk did not have the power to make any decisions. His function was to make sure everyone followed the rules.

2. Preceptors did not ask “Who loves me the best?” Nor did they give their token to the one who yelled the loudest. Applicants did not need to approach each preceptor telling him that they liked him better than the next one. To whom each preceptor would give the next token was determined only by the list in his notebook.

3. Also, preceptors were not penalized for offering tokens to applicants who might well return them. Each token retained its full value. As their list came down to an applicant who wanted their token, that one would keep it, no matter how many had rejected it before.

4. Similarly, applicants did not need to worry that they used space in their notebook to list preceptors from whom they might not receive an offer. Those extra names had no effect. The only thing that mattered was the position of preceptors from whom they did get offers.

5. Neither did the applicants worry about the sequence in which the preceptors made their offers. Even if their favorite preceptor was the last one to step forward, they could still accept his token when it was finally offered and return the token they had held to that point.

How it evolved…

The town square meetings worked well, but after a while preceptors noted that it was not really necessary to go to the town square themselves, since all they did was read the lists they had prepared in advance. They could give this list to a friend or to a broker and ask him to go in their place. They would still be assured that the outcome would be exactly the same. Very soon the applicants reached the same conclusion. They, too, gave their lists to a broker to represent them.

This is exactly how the first manual matching programs were run: two persons, one with a stack of training program lists, and one with a stack of applicant lists, exchanging notes until all possible offers had been made.

Not long thereafter it was decided that not even the town clerk and the two brokers were needed. Since their actions were entirely predictable, they could be replaced by a computer program. Fortunately, the town clerk and the brokers are not out of work. They were rehired to become the computer programmer and data input operators.

This is how the Matching Program operates today. The computer program runs faster, but the steps it goes through are exactly the same as in the meeting on the town square. If you understood the town square meeting, you will understand the matching program logic.