New papers on matching by Yeon-Koo Che and Olivier Tercieux (large markets and top trading cycles)

In the Cowles Foundation working paper series:

"Efficiency and Stability in Large Matching Markets" 
Cowles Foundation Discussion Paper No. 2013

YEON-KOO CHE, Columbia University
Email: yc2271@columbia.edu
OLIVIER TERCIEUX, Paris-Jourdan Sciences Economiques (PSE)
Email: Tercieux@pse.ens.fr

We study efficient and stable mechanisms in matching markets when the number of agents is large and individuals’ preferences and priorities are drawn randomly. When agents’ preferences are uncorrelated, then both efficiency and stability can be achieved in an asymptotic sense via standard mechanisms such as deferred acceptance and top trading cycles. When agents’ preferences are correlated over objects, however, these mechanisms are either inefficient or unstable even in an asymptotic sense. We propose a variant of deferred acceptance that is asymptotically efficient, asymptotically stable and asymptotically incentive compatible. This new mechanism performs well in a counterfactual calibration based on New York City school choice data.

"An Analysis of Top Trading Cycles in Two-Sided Matching Markets" 
Cowles Foundation Discussion Paper No. 2014

YEON-KOO CHE, Columbia University
Email: yc2271@columbia.edu
OLIVIER TERCIEUX, Paris-Jourdan Sciences Economiques (PSE)
Email: Tercieux@pse.ens.fr

We study top trading cycles in a two-sided matching environment (Abdulkadiroglu and Sonmez (2003)) under the assumption that individuals’ preferences and objects’ priorities are drawn iid uniformly. The distributions of agents’ preferences and objects’ priorities remaining after a given round of TTC depend nontrivially on the exact history of the algorithm up to that round (and so need not be uniform iid). Despite the nontrivial history-dependence of evolving economies, we show that the number of individuals/objects assigned at each round follows a simple Markov chain and we explicitly derive the transition probabilities.

"Payoff Equivalence of Efficient Mechanisms in Large Matching Markets" 
Cowles Foundation Discussion Paper No. 2014

YEON-KOO CHE, Columbia University
Email: yc2271@columbia.edu
OLIVIER TERCIEUX, Paris-Jourdan Sciences Economiques (PSE)
Email: Tercieux@pse.ens.fr

We study Pareto efficient mechanisms in matching markets when the number of agents is large and individual preferences are randomly drawn from a class of distributions, allowing for both common and idiosyncratic shocks. We show that, as the market grows large, all Pareto efficient mechanisms -- including top trading cycles, serial dictatorship, and their randomized variants -- are uniformly asymptotically payoff equivalent “up to the renaming of agents,” yielding the utilitarian upper bound in the limit. This result implies that, when the conditions of our model are met, policy makers need not discriminate among Pareto efficient mechanisms based on the aggregate payoff distribution of participants. 

Refugee resettlement as a matching problem

There are a lot of displaced people in the world today, both outside their country of origin and within. The conflict in Syria is a big contributor. The poverty in Africa is another. Here's a recent NY Times story, about a UN report, whose headline summarizes the story well:
60 Million People Fleeing Chaotic Lands, U.N. Says

The international refugee accords place most responsibility for resettlement on the "country of first asylum."  If you were smuggling yourself out of Africa, or Syria, you'd have good reason, therefore, to try to get to Sweden before declaring yourself a refugee, but it's a lot easier to get to Turkey or Greece or Italy.  However some classes of refugee can seek resettlement elsewhere, and the U.S. takes a small number of these (around 70,000/year).

American policy is to try to settle refugees across the country, the idea being that this might ease assimilation, and avoid overburdening particular cities and towns. But, of course, once refugees get to the U.S., they are completely free to move around. So there's a matching problem of refugees and cities.

The case of Somali refugees makes this clear: although they've been resettled around the country, many of them quickly move to join the growing community in and around Lewiston, Maine. (Here's a nice story dated 2007...
Letter From Maine: New in Town--Somali refugees began arriving in Lewiston, Maine (pop. 36,000) six years ago. Word spread that Lewiston had good schools, a low crime rate and cheap housing — and the Somalis began arriving in droves.

And here's a Wikipedia page: History of the Somalis in Maine

The point of all this is that people aren't passive, you can't keep them where they are sent if they don't want to stay there (even if moving means giving up various kinds of refugee assistance).

Hillel Rapoport of the Paris School of Economics has been thinking of this in a European context, in which one of the questions is to which countries should refugees be resettled?  How a tradable refugee-admission quota system could help solve the EU’s migration crisis.  Even in Europe, I'm not sure how well refugees can be resettled in the countries to which they are assigned, but the barriers to moving are probably substantially higher than for moves in the U.S.

The EU is thinking about moving refugees, maybe in directions they want to go (although this isn't clear): see e.g. this recent story. EU leaders agree to relocate 40,000 migrants. "EU leaders holding late-night talks in Brussels have agreed to relocate tens of thousands of migrants who have arrived in Italy and Greece." But it's hard, and they aren't really reaching agreement: In Testy Debate, E.U. Leaders Fail to Agree on Quotas to Spread Migrants Across Bloc

So, we have a matching problem here. How to resettle refugees to places that they are willing to stay in, while meeting the other goals that we'd like to achieve?

It's not a bad question to ponder on the 4th of July, for a nation made up of immigrants, many of whom escaped from somewhere to come to the USA.

9th workshop Matching in Practice June 8 - June 9 in Barcelona

9th workshop Matching in Practice, June 8 - June 9

The program for the 9th workshop of Matching in Practice is up:

Scientific Program

Day 1: June 8, 2015 

11:00 – 11:30     Welcome Coffee 

11:30 – 12:00     Registration

12:00 – 13:30    Keynote presentation – Christopher Avery (Harvard Kennedy School of Government)

The Common Application and the DA Algorithm in School Assignment (with Cara Nickolaus and Parag Pathak)

13:30 – 14:30     Lunch

14:30 – 16:30     Strategic Choice and Affirmative Action

Dynamic Reserves in Matching Markets with Contracts: Theory and Applications, by Orhan Aygün and Bertan Turhan

College Admission with Multidimensional Privileges: The Brazilian Affirmative Action Case, by Orhan Aygün and Inacio Bo

Self-selection in School Choice, by Li Chen and Juan Sebastián Pereyra

16:30 – 17:00     Coffee break

17:00 – 18:30     Empirical Estimation of Preferences in School Choice

Demand Analysis using Strategic Reports: An application to a school choice  mechanism, by Nikhil Agarwal and Paolo Somaini

Structural Estimation of a Model of School Choices: the Boston Mechanism vs. Its Alternatives, by Caterina Calsamiglia, Chou Fu and Maia Güell

20:00                  Dinner

Day 2: June 9, 2015 

9:30 – 11:00       Educational Choice, Incentives and Welfare

College Diversity and Investment Incentives, by Thomas Gall, Patrick Legros and Andrew F. Newman

 Socio-economic status and enrollment in higher education: Do costs matter? by Koen Declercq and Frank Verboven

 11:00 – 11:30     Coffee break 

11:30 – 12:15       Re-matching

The Design of Teacher Assignment: Theory and Evidence, by Julien Combe, Olivier Tercieux and Camille Terrier

12:15 – 13:00      Panel discussion on matching practices (TBD)

13:30                     Lunch

Scientific Committee: Dorothea Kübler, Antonio Miralles and Joana Pais

Registrations If you plan to attend the meeting (and are not a speaker), please contact Antonio Miralles at amirallesasensio@gmail.com

Venue: Universitat Pompeu Fabra, Edifici Balmes, Carrer Balmes 132, Barcelona

Matching dogs to animal shelters, by air and by land

Volunteer Pilots Fly Shelter Dogs to New Homes to Save Them From Euthanasia
"One of the biggest issues for animal shelters nation-wide is that some regions are overflowing with adoptable dogs while others never have enough. Wings Of Rescue, an extraordinary volunteer organization run by dedicated pilots, flies dogs from shelters overflowing with animals to those that can find them new homes. Often, the dogs they transport would have been euthanized hours later if it weren’t for these pilots.
The organization has saved over 12,000 dogs since 2009, when it was formed. Flights cost roughly $80 per dog, and you can donate to their cause on their website."

Rescue Waggin’ 
"Location is everything: Some cities have too many homeless dogs and puppies; others have waiting adopters.

"So every day, the PetSmart Charities® Rescue Waggin’ program picks up selected dogs and puppies from partner shelters in areas where there are more dogs and puppies than can be placed through adoption. Then we transport them to places where they get adopted, often within days.

"In fact, the Rescue Waggin' program has helped save the lives of more than 70,000 dogs and puppies since we started it in 2004."



HT: Nicole Immorlica and Christine Exley

The Stable Marriage Problem and School Choice, at the American Mathematical Society--column by David Austin

The American Mathematical Society has a column by David Austin on The Stable Marriage Problem and School Choice 

He writes:
"This column will present the game-theoretic results contained in the original Gale-Shapley paper along with Roth's subsequent analysis. Pathak calls the deferred acceptance algorithm "one of the great ideas in economics," and Roth and Shapley were awarded the 2012 Nobel Prize in economics for this work...

He gives a straightforward mathematical treatment of some of the main theoretical results, in context:

"Using ideas described in this column, economists Atila Abdulkadiroglu, Parag Pathak, and Alvin Roth designed a clearinghouse for matching students with high schools, which was first implemented in 2004. This new computerized algorithm places all but about 3000 students each year and results in more students receiving offers from their first-choice schools. As a result, students now submit lists that reflect their true preferences, which provides school officials with public input into the determination of which schools to close or reform. For their part, schools have found that there is no longer an advantage to underrepresenting their capacity.

The key to this new algorithm is the notion of stability, first introduced in a 1962 paper by Gale and Shapley. We say that a matching of students to schools is stable if there is not a student and a school who would prefer to be matched with each other more than their current matches. Gale and Shapley introduced an algorithm, sometimes called deferred acceptance, which is guaranteed to produced a stable matching. Later, Roth showed that when the deferred acceptance algorithm is applied, a student can not gain admittance into a more preferred school by strategically misrepresenting his or her preferences."

- See more at: http://www.ams.org/samplings/feature-column/fc-2015-03#sthash.LoiUEphE.dpuf