Amsterdam school choice: next year will be single tie-breaking deferred acceptance (instead of multiple tie-breaking)

In Amsterdam, the school choice debates have been resolved for now. Next year, there will be a deferred acceptance algorithm with single tie-breaking, which replaces deferred acceptance with multiple tie breaking. The reason is to avoid inefficiencies that could leave students wanting to trade places.
 Hessel Oosterbeek forwards the following press release:

Nu toch matching voor toewijzing van scholen aan nieuwe brugklassers
Osvo herziet besluit plaatsingsprocedure en volgt Amsterdamse gemeenteraad in wens tot matching
Datum: 27 november 2015


Google translate renders it into English like this:

Now surely matching for allocation of new schools graders
Osvo revises decision placement procedure and following Amsterdam city council in desire to matching
Date: November 27, 2015

The Amsterdam secondary schools united in Osvo match yet again to bring out high school students in a school of choice. In matching children fill a preferred list of several schools, and the computer most favorable and fairest possible distribution calculates. Last year was also matched, but according to a different algorithm. With the currently chosen variant will be more students in the school of their first choice, but there will be more children who are considerably lower on their preferred list. In any case, there is not the problem afterwards between students can be exchanged for a better result.

Osvo still goes first consult with the alderman of education Simone Kukenheim the practical assistance that will get the schools of the municipality for the implementation of the matching. Concrete will be requested from the municipality together with Osvo a central project, the information to parents and children and to take complaints to themselves.

A broad majority in the city council gave to know the alderman of education for this variant of matching. The alderman asked Osvo thereafter published the decision on October 29 to return to draw, to reconsider. With the amended decision in favor of the matching variant Osvo hopes for this year to be able to count on political and social support in the implementation, but also for the results of the placement.

The selected system is also preferred by a large group of parents who made ​​their wish to keep matching known through a petition, in a variant they call matching 2.0. This variant is referred to as DA STB or RSD. DA STB earlier this year in a scientific analysis for the evaluation Osvo compared with DA MTB, which was used in the 2015 matching. DA STB recently came second in the bus in the quest of Osvo to a procurement procedure for 2016. For the pros and cons refer to 
http://www.verenigingosvo.nl/wp-content/uploads/2013/09/Evaluatie_Matching_simulaties.pdf

Osvo has always its decision to match last year defended by pointing to the starting point of an optimal and fair distribution of the few places in schools where more children enroll than there are places. After a storm of protest about the system, its implementation and information about Osvo selected after extensive review and in consultation with the municipality for a combination of items and match. It would be students in a first-round no preferred list can draw for their school of choice, followed by a relatively small group of about 500 children would be placed on matching the schools still places available. The second round would be conducted according to the system which now is put the whole group of students.


See previous posts:

Friday, June 26, 2015

School choice in Amsterdam goes to court over tie-breaking

Thursday, July 2, 2015

The Amsterdam court rules on school choice

BBC show on algorithms and kidney exchange (tv documentary)

David Manlove writes from Scotland:

"BBC4 have just shown a documentary on algorithms, which featured the Gale-Shapley algorithm and kidney exchange in the UK.  In particular, it shows an excerpt of you and Lloyd Shapley receiving the Nobel Prize.

The programme was shown on 24 September – see http://www.bbc.co.uk/algorithms.  Viewers outside the UK probably cannot watch the footage, but I noticed that someone has posted the programme on YouTube.  It can currently be seen at https://www.youtube.com/watch?v=Itvwa85YkEg.  The stable marriage part starts at 20:50 and the kidney exchange part follows (from 25:40).  You and Lloyd Shapley are shown at 21:35.

In general I reckon they did a great job of making a complex subject accessible - and I thought that Marcus du Sautoy in particular was very engaging.”

*********

David's work on kidney exchange in the UK is featured in the video, which you can also see below

What do employers learn from interviews? Can they be replaced?

The NY Times had a recent column covering the latest version of this old debate about the informativeness of interviews:

ROBO RECRUITING--Can an Algorithm Hire Better Than a Human?

"A new wave of start-ups — including Gild, Entelo, Textio,Doxa and GapJumpers — is trying various ways to automate hiring. They say that software can do the job more effectively and efficiently than people can. Many people are beginning to buy into the idea. Established headhunting firms like Korn Ferry are incorporating algorithms into their work, too.

"If they succeed, they say, hiring could become faster and less expensive, and their data could lead recruiters to more highly skilled people who are better matches for their companies. Another potential result: a more diverse workplace. The software relies on data to surface candidates from a wide variety of places and match their skills to the job requirements, free of human biases."

School choice and medical residency matching in Forbes

I was in New York City yesterday for an IIPSC-organized conference on school choice, and it was a nice coincidence to see that Forbes had an article on school choice and other matching processes, that mentions IIPSC.

Prerna Sinha writes about deferred acceptance algorithms, in the medical match and in NYC high school choice: Quantifying Harmony: The Matchmaking Algorithm That Pairs Residents With Hospitals, Students With Schools

"In 2003 Professor Roth (Stanford), who has played a major role in the dissemination of the deferred acceptance algorithm, worked with Atila Abdulkadiroglu (Duke) and Parag Pathak (M.I.T.) to replace the broken high school match system that was previously in place in New York City.Roth realized similar to a stable marriage or residency-student match, a high school-student match would work if individuals and schools were permitted to select alternative options after their most preferred options were rejected.

He is confident that the deferred acceptance algorithm provides a significant improvement over the system that was previously in place, but he believes the school choice system could work better. He clarified, “... there is a problem with how to disseminate information to families about schools.” He also suggested that there would be less congestion and it would be a more efficient process if all charter schools and private schools participated too.
...
 Roth continues to work closely with Neil Dorosin, who was the director of high-school admissions in New York City at the time of the redesign. Dorosin is now the Executive Director of Institute of Innovation in Public School Choice (IIPSC), and Roth sits on the advisory board. IIPSC is a team of specialists in the design and implementation of enrollment and school choice systems. The organization helps communities integrate the latest market design research and technology to solve school choice problems.

Roth calls Dorosin the “Johnny Appleseed” of getting systems like the one in NYC into New Orleans, Denver, and Washington.

Dorosin told FORBES, “Public school choice, this two sided matching market where there are two interested parties (schools and students), exists all over the country, in every big city and most small cities too. In most cases the systems that are set up to organize that two sided matching market, unintentionally, are failing. Failing the kids and the families that are supposed to use them, failing the systems of schools that are supposed to be administering them.”

Private dealings between parents and schools, limited resources and information for some parties, and congestion caused by lack of centralized communication are examples of market malfunctions that lead to disorganized systems.

According to Dorosin, the market design approach (deferred acceptance) addresses the central problem of matching students with schools: high school seats are a scarce resource that needs to be allocated efficiently and transparently in a manner that allows students and parents to feel safe when participating.

Parents and students need to feel safe in listing their preferential choice of schools, free of fear that ranking School A as a top choice will hurt their chances of getting into School B, their second choice. Efficiency involves getting optimal results on the first try and avoiding numerous offers or back and forth between parties. Transparency would allow lottery numbers, school information, and reports about outcomes to be easily accessible by all in a centralized location.

Dorosin says, “These are the elements that lead to a better system. We call this universal enrollment.”

The deferred acceptance algorithm, which is the basis of Dorosin’s universal enrollment concept, has a proven track record with the students of New York City and medical residents across the country. It may yet have applications beyond those it has now. At the very least, you can expect urban districts around the country and possibly around the world to continue to adopt some of the principles."

Kidney exchange in the UK: Algorithms

David F. Manlove and Gregg O’Malley. 2015. Paired and Altruistic Kidney Donation in the UK: Algorithms and Experimentation. J. Exp. Algorithmics19, Article 2.6 (January 2015), 1.11 pages. DOI=10.1145/2670129 http://doi.acm.org/10.1145/2670129

"We study the computational problem of identifying optimal sets of kidney exchanges in the UK. We show how to expand an integer programming-based formulation due to Roth et al. [2007] in order to model the criteria that constitute the UK definition of optimality. The software arising from this work has been used by the National Health Service Blood and Transplant to find optimal sets of kidney exchanges for their National Living Donor Kidney Sharing Schemes since July 2008. We report on the characteristics of the solutions that have been obtained in matching runs of the scheme since this time. We then present empirical results arising from experiments on the real datasets that stem from these matching runs, with the aim of establishing the extent to which the particular optimality criteria that are present in the UK influence the structure of the solutions that are ultimately computed. A key observation is that allowing four-way exchanges would be likely to lead to a moderate number of additional transplants."

Finding long chains in kidney exchange: new algorithms

Here's a new paper just published online before print, January 5, 2015, doi: 10.1073/pnas.1421853112, PNAS January 5, 2015.

It's about the algorithms we're presently using to find optimal cycles-and-chains solutions in the kinds of sparse kidney exchange graphs we're encountering in the several programs with which we work most closely.

Finding long chains in kidney exchange using the traveling salesman problem
by Ross Anderson, Itai Ashlagi,  David Gamarnik,  and Alvin E. Roth

Abstract: As of May 2014 there were more than 100,000 patients on the waiting list for a kidney transplant from a deceased donor. Although the preferred treatment is a kidney transplant, every year there are fewer donors than new patients, so the wait for a transplant continues to grow. To address this shortage, kidney paired donation (KPD) programs allow patients with living but biologically incompatible donors to exchange donors through cycles or chains initiated by altruistic (nondirected) donors, thereby increasing the supply of kidneys in the system. In many KPD programs a centralized algorithm determines which exchanges will take place to maximize the total number of transplants performed. This optimization problem has proven challenging both in theory, because it is NP-hard, and in practice, because the algorithms previously used were unable to optimally search over all long chains. We give two new algorithms that use integer programming to optimally solve this problem, one of which is inspired by the techniques used to solve the traveling salesman problem. These algorithms provide the tools needed to find optimal solutions in practice.
************

Update: now published,  PNAS | January 20, 2015 | vol. 112 | no. 3 | 663–668