on my reading list (but not yet read)--recent papers on school choice, resident matching, and kidney exchange

Inefficient School Choice in a Long-Run Urban Equilibrium

Ulrich Kamecke 

Humboldt University of Berlin - Faculty of Economics
September 29, 2014

CESifo Working Paper Series No. 4969 
Abstract:      

We model centralized school matching as a second stage of a simple Tiebout-model and show that the two most discussed mechanisms, the deferred acceptance and the Boston algorithm, both produce inefficient outcomes and that the Boston mechanism is more efficient than deferred acceptance. This advantage vanishes if the participants get to know their priorities before they submit their preferences. Moreover, the mechanism creates artificial social segregation at the cost of the disadvantaged if the school priorities are based on ex ante known (social) differences of the applicants.

The History and Rationale of the American Urological Association Residency Matching Program

Steven J. Weissbart, 

Jeffrey A. Stock

A new perspective on Kesten's school choice with consent idea ^☆

• Qianfeng Tang^, , 
• Jingsheng Yu 

Abstract We revisit the school choice problem with consent proposed by Kesten [12], which seeks to improve the efficiency of the student-optimal deferred acceptance algorithm (DA) by obtaining students' consent to give up their priorities. We observe that for students to consent, we should use their consent only when their assignments are Pareto unimprovable. Inspired by this perspective, we propose a new algorithm which iteratively reruns DA after removing students who have been matched with underdemanded schools, together with their assignments. While this algorithm is outcome equivalent to Kesten's EADAM, it is more accessible to practitioners due to its computational simplicity and transparency on consenting incentives. We also adapt this algorithm for school choice problems with weak priorities to simplify the stable improvement cycles algorithm proposed by Erdil and Ergin [8].

Kidney Exchange with Long Chains: An Efficient Pricing Algorithm for Clearing Barter Exchanges with Branch-and-Price

Kristiaan M. Glorie
Econometric Institute, Erasmus University Rotterdam, 3000 DR Rotterdam, The Netherlands
glorie@ese.eur.nl,

J. Joris van de Klundert
Institute of Health Policy and Management, Erasmus University Rotterdam, 3000 DR Rotterdam, The Netherlands
vandeklundert@bmg.eur.nl,

Albert P. M. Wagelmans
Econometric Institute, Erasmus University Rotterdam, 3000 DR Rotterdam, The Netherlands
wagelmans@ese.eur.nl

Abstract Barter exchange markets are markets in which agents seek to directly trade their goods with each other. Exchanges occur in cycles or in chains in which each agent gives a good to the next agent. Kidney exchange is an important type of barter exchange market that allows incompatible patient–donor pairs to exchange kidneys so the involved patients can receive a transplant. The clearing problem is to find an allocation of donors to patients that is optimal with respect to multiple criteria. To achieve the best possible score on all criteria, long cycles and chains are often needed, particularly when there are many hard-to-match patients. In this paper we show why this may pose difficulties for existing approaches to the optimization of kidney exchanges. We then present a generic iterative branch-and-price algorithm that can deal effectively with multiple criteria, and we show how the pricing problem may be solved in polynomial time for a general class of criteria. Our algorithm is effective even for large, realistic patient–donor pools. Our approach and its effects are demonstrated by using simulations with kidney exchange data from the Netherlands and the United States.

Mini course in market design: video of the short course (4 lectures) I gave in Brazil

Here is the link to lecture 1 of 4, with links to the other three lectures as well.

IWGTS 2014 - Mini-course: Market Design

These lectures were delivered as part of the  Conference on game theory in honor of Marilda Sotomayor: July 2014.

Pope Francis on euthanasia and in vitro fertilization

In connection with recent developments concerning medically assisted suicide/death with dignity, the Catholic Church has strongly reaffirmed its opposition to that and other repugnant transactions, particularly involving reproduction.

Pope Francis denounces euthanasia as 'sin against God'. The Pope strongly condemns the 'right to die' movement, and warns against abortion, IVF and stem cell research

"Pope Francis denounced the right to die movement on Saturday, saying that euthanasia is a sin against God and creation.

"The Latin American pontiff said it was a “false sense of compassion” to consider euthanasia as an act of dignity.

"Earlier this month, the Vatican’s top bioethics official condemned as “reprehensible” the death by assisted suicide of a 29-year-old American woman, Brittany Maynard, who was suffering terminal brain cancer and said she wanted to die with dignity.

“This woman (took her own life) thinking she would die with dignity, but this is the error,” said Monsignor Ignacio Carrasco de Paula, the head of the Pontifical Academy for Life.

“Suicide is ... a bad thing because it is saying no to life and to everything it means with respect to our mission in the world and towards those around us,” he said, describing assisted suicide as “an absurdity”.
...
"The Pope also condemned in vitro fertilization, describing it as “the scientific production of a child” and embryonic stem cell research, which he said amounted to “using human beings as laboratory experiments to presumably save others.”

“This is playing with life,” he said. “Beware, because this is a sin against the creator, against God the creator.”

"The Pope considers the assisted suicide movement as a symptom of a contemporary “throw-away culture” that views the sick and elderly as a drain on society.

"Francis urged doctors to take “courageous and against-the-grain” decisions to uphold church teaching on the dignity of life."

Congestion and signaling in college admissions

The college application season is approaching, and Ariel Kaminer in the NY Times notes the stress and congestion: Applications by the Dozen, as Anxious Seniors Hedge College Bets

"For members of the class of 2015 who are looking at more competitive colleges, their overtaxed counselors say, 10 applications is now commonplace; 20 is taking on a familiar ring; even 30 is not beyond imagining. And why stop there?
...
"A spokeswoman for Naviance, an online tool that many high school students and their counselors use to keep track of applications, said one current user’s “colleges I’m applying to” tab already included 60 institutions. Last year the record was 86, she said.

"A number of factors have contributed to this rapid escalation.

"One is the growing popularity of the Common Application, a standardized form that more than 500 colleges now honor, making the process of applying to multiple institutions far easier. Another is the tough economy, which drives students to look ever farther afield for a college that can meet their financial aid needs.

"But perhaps the most pressing factor has been plain old fear.

“Every year the story is that college is harder to get into, so kids panic and think they have to apply to more places,” said Jim Jump, academic dean and director of guidance at St. Christopher’s School in Richmond, Va. The resulting surfeit of applications drives acceptance rates down even further, making the next year’s high school seniors even more panicked.
...
"According to the National Association for College Admission Counseling, in 1990 just 9 percent of students applied to seven or more colleges. By 2011, the year of its most recent survey, that group had risen to 29 percent.

"In the class of 2014, according to Naviance, 16.5 percent of seniors using the system said they intended to apply to 11 to 20 colleges. (Naviance did not have figures on how many applications were actually filed.)
...
"But the most compelling reason not to apply to dozens of colleges, counselors say, is that more applications do not necessarily mean better odds. “It’s not like the lottery,” said Michael Carter of St. Stephen’s & St. Agnes School in Alexandria, Va.

"Ms. Sohmer said she had found that when students file 20 or more applications, “they’ve loaded on lots of ultracompetitive schools, so their list becomes disproportionately top-heavy. Or they throw in lots of schools at the end where they’re overqualified.” A far better way to increase one’s chances, she and many others agree, is to come up with a manageable but carefully selected list of schools and get serious about them.
...
"As a result, many colleges have begun emphasizing “demonstrated interest” — tiny but telling indications of how badly students want to attend. “If they’re within a reasonable distance of the campus, did they visit?” asks Patrick O’Connor, associate dean of college counseling at the Cranbrook Kingswood Upper School in Bloomfield Hills, Mich. “Did they attend a college night and fill out a card? Have they contacted a rep to ask some legitimate questions?”

Who Gets What--And Why: The New Economics of Matching and Market Design

I finally finished my book on market design for a general audience:) (except for copy editing and galleys which are still to come...) The publication date (at the moment) is June 2...

Coming in June, my book :

Here's the publisher's blurb:
A Nobel laureate reveals the often surprising rules that govern a vast array of activities — both mundane and life-changing — in which money may play little or no role.

If you’ve ever sought a job or hired someone, applied to college or guided your child into a good kindergarten, asked someone out on a date or been asked out, you’ve participated in a kind of market. Most of the study of economics deals with commodity markets, where the price of a good connects sellers and buyers. But what about other kinds of “goods,” like a spot in the Yale freshman class or a position at Google? This is the territory of matching markets, where “sellers” and “buyers” must choose each other, and price isn’t the only factor determining who gets what.

Alvin E. Roth is one of the world’s leading experts on matching markets. He has even designed several of them, including the exchange that places medical students in residencies and the system that increases the number of kidney transplants by better matching donors to patients. In Who Gets What — And Why, Roth reveals the matching markets hidden around us and shows how to recognize a good match and make smarter, more confident decisions.

Matching and market design at the SAET conference in 2015 in Cambridge, UK

Fuhito Kojima writes:

I'm organizing a session at SAET conference 2015;

http://www.saet.uiowa.edu/2015/

and I'm wondering if you could spread the word through your blog, if you have a slot for an entry.

I am planning a session on matching and market design, and have two slots for presentations left.

Thanks a lot in advance!

Best,

Fuhito

Society for the Advancement of Economic Theory

15th SAET Conference on Current Trends in Economics
University of Cambridge, UK, July 27-31, 2015

The 15th Annual SAET Conference will be held July 27-31, 2015 at the University of Cambridge, UK.

Why some people don't register as deceased organ donors

In The Atlantic, Tiffanie Wen reports: Why Don't People Want to Donate Their Organs?


" In the United States alone, 21 people die everyday waiting for an organ transplant. Though about 45 percent of American adults are registered organ donors, it varies widely by state. More than 80 percent of adults in Alaska were registered donors in 2012, compared to only 12.7 percent in New York, for example. In New York alone, there are more than 10,000 people currently waiting for organ transplants. According to data compiled by the Organ Procurement and Transplantation Network, more than 500 people died in New York last year, waiting for an organ to become available.

"Given this shortage of organs, why don’t more people donate?

"It’s a touchy question, something non-donors aren’t necessarily keen to answer. But experts say there is a large disparity between the number of people who say that they support organ donation in theory and the number of people who actually register. In the U.K., for example, more than 90 percent of people say they support organ donation in opinion polls, but less than one-third are registered donors. What keeps well-intentioned people from ultimately donating is something that academics, doctors, and organ-donation activists are trying to figure out.

"In a recent literature review, researchers at the University of Geneva examined several social and psychological reasons why people choose not to donate, either by not registering as an organ donor during their lives, or electing not to donate the organs of their next of kin.

"The study cites mistrust in the medical field and lack of understanding about brain death as major barriers to donation. A 2002 study in Australia, for example, illustrates the controversy surrounding brain death. Some participants indicated that they wouldn’t donate the organs of their next of kin if his or her heart were still beating, even if they were proclaimed brain-dead.

"Studies have also shown that the less people trust medical professionals, the less likely they are to donate. The mistrust can come from personal experience—one study in New York showed, for example, that next of kin who perceived a lower quality of care during a loved one’s final days were less likely to consent to donation—or from misconceptions about how the medical community treats registered organ donors.

“There are a lot of people who subscribe to the belief that if a doctor knows you are a registered donor, they won’t do everything they can to save your life,” says Brian Quick, an associate professor of communication at the University of Illinois."


HT: Zeeshan Butt

Matchmakers for religious schools in Israel

Assaf Romm writes

"The following article in Hebrew tells the story of the Haredi (ultra orthodox jewish) "yeshiva ktana" (=~ elementary school) students and the way they get accepted into "yeshiva gdola" (=~ high school):

http://www.ynet.co.il/articles/0,7340,L-4587559,00.html

The interesting parts are that there are many-to-one matchmakers that make a lot of money by cutting deals between students and high schools, and between elementary schools and high schools. For example, a deal can be getting a group of students from the same elementary school in which there are 12 excellent students and 3 mediocre students to an excellent high school, or paying the matchmaker certain amount of money for convincing excellent students to come to a certain high school. There are also reports of some of the students joining in by going to the matchmakers/elementary school teachers and asking to share the profit. Finally, there are also some mentions of unraveling, and an agreement to not start recruiting students before a certain date.

My thoughts about this: a centralized computer system might not be a good idea in this case, because of this population's complete mistrust in technology, because there isn't any centralized organization that governs all these activities, and because the transfers may make it very hard to achieve near-strategyproofness for both sides, which could be extremely important here."

Repugnant transactions: the right to say "God" in Malay

Thomas Fuller has the story in the NY Times: The Right to Say ‘God’ Divides a Diverse Nation

This is one of those stories whose URL is more informative than the headline:
http://www.nytimes.com/2014/11/04/world/asia/in-malaysia-allah-is-reserved-for-muslims-only.html

"According to a series of government orders and rulings by Malaysia’s Islamic councils, the word for God in the Malay language — “Allah” — is reserved for Muslims. Malay-language Bibles are banned everywhere except inside churches. State regulations ban a list of words, including Allah, in any non-Muslim context."

Interview on market design

Here's an interview I did with a British financial reporter, Vikas Shah: Is It Time to Re-Design our Markets?

More on Nimrod Megiddo winning the INFORMS von Neumann Theory Prize

Here's the citation for Nimrod Megiddo winning the John von Neumann Theory Prize

John von Neumann Theory Prize

2014 Winner(s): Nimrod Megiddo, IBM

Citation:

Of all of the areas in which he has worked, Megiddo has had perhaps the most profound impact on the theory of linear programming. His work on the probabilistic analysis of the simplex method, alone and with Adler, established some of the most important results in the area, including the best (quadratic) bound for the complexity of a complete parametric pivoting method and an explanation of why this is possible for the lexicographic version but not the standard Lemke perturbation. He also established a quadratic lower bound for this method. This, along with work of Smale, Borgwardt, and Haimovich, together with independent proofs of the quadratic result by Adler-Karp-Shamir and Todd provided the first theoretical justification for the success of the simplex method. 

Megiddo was an early leader in the theory of interior-point methods, and laid the framework for the development of primal-dual methods in his seminal paper on pathways to the solution. This paper was the foundation for the hugely successful primal-dual interior-point methodology for linear programming, implementations of which are now included in every serious software package. His contributions to interior-point methods culminated in his work on the linear complementarity problem with Kojima and Noma. 

Megiddo’s work has also played a role in highlighting the question, still unresolved today, of whether there is a strongly polynomial algorithm for linear programming. Megiddo made two strikingly beautiful contributions in the design of strongly polynomial algorithms: his innovative multi-dimensional searching technique that yielded a strongly polynomial algorithm for linear programming in constant dimensions, and its forerunner in parametric search algorithms, which showed how to leverage an algorithm to optimize a linear objective into a corresponding strongly polynomial algorithm to optimize a rational objective function over the same feasible region. 

In algorithmic game theory, Megiddo has done groundbreaking work that anticipated by two decades the more recent blossoming of the field. In particular, Megiddo raised the question of the complexity of equilibrium computation in the 80’s and showed that the usual notion of NPhardness is not adequate to capture the apparent difficulty of the problem, anticipating and opening the way to subsequent developments in the area. On the algorithmic side, his later work (with Kholler and von Stengel) also showed how equilibrium solutions for 2-person games can be computed in polynomial time, even if the game were given in extensive form. Bridging between concepts in game theory and traditional combinatorial optimization, Megiddo initiated the investigation of computing fair flows in networks, and did path-setting work on efficient algorithms to compute the fair allocation of costs in a number of game-theoretic settings. 

In summary, Nimrod Megiddo has made fundamental contributions across a broad range of areas of operations research and management science, most notably in linear programming, combinatorial optimization, and algorithmic game theory. His work has been highly influential, in both identifying key concepts and in developing new algorithmic approaches for fundamental problems.

An open letter supporting experiments on providing benefits to kidney donors

An open letter to President Obama and Congress calls for pilot studies on the effects of providing benefits to kidney donors.

An Open Letter to President Barack Obama, Secretary of Health and Human Services Sylvia Mathews Burwell, Attorney General Eric Holder and Leaders of Congress


Here are the conclusions, and the list of initiating signers

CONCLUSION

We applaud the President’s declaration that 2014 is a “year of action” when he will use executive powers and the regulatory process to ensure the health and well-being of Americans and end unnecessary health expenditures. As part of this process, we call on the President to take executive action on organ transplantation and initiate pilot studies on benefits to donors.

We call on HHS to develop the necessary regulatory process for conducting such studies and to implement them.

We call on the Attorney General to smooth the way for such pilot programs by recognizing that they are consistent with the intent of the National Organ Transplant Act.

Finally, we call on Congress to pass legislation that allocates the necessary funding for these programs and clears the way for their implementation.

Kidney disease has for too long been neglected by all branches of government. It is time to act.

Initiating signers*:

Nir Eyal, Associate Professor of Global Health and Social Medicine, Harvard Medical School and Harvard University
Julio Frenk, Dean, Harvard School of Public Health, Harvard University
Michele B. Goodwin, Chancellor’s Chair in Law, University of California-Irvine Law School
Lori Gruen, Professor of Philosophy, Feminist, Gender, and Sexuality Studies, and Environmental Studies at Wesleyan University
The Very Reverend Gary R. Hall, Dean, Washington Cathedral
Douglas W. Hanto, Professor of Surgery and Associate Director Vanderbilt Transplant Center, Vanderbuilt University, Tennessee
Frances Kissling, President, The Center for Health, Ethics and Social Policy
Ruth Macklin, Professor of Bioethics, Albert Einstein College of Medicine
Steven Pinker, Johnstone Family Professor, Department of Psychology, Harvard University
Lloyd E. Ratner, Professor of Surgery, Columbia University
Harold T. Shapiro, President Emeritus, Princeton University
Peter Singer, Ira W. DeCamp Professor of Bioethics, Princeton University
Andrew W. Torrance, Professor of Law, University of Kansas and Visiting Scholar MIT Sloan School of Management
Robert D. Truog, Director, Center for Bioethics, Harvard University, Harvard Medical School
Robert M. Veatch, Professor of Medical Ethics at the Kennedy Institute of Ethics, Georgetown University

Together with the long list of other signers, the letter has a lot of support from a diverse group of people, including many transplant professionals who I know and respect. It's a sign that the discussion is changing.

Market design in Spanish: Diseño de Mercados by Alvin E. Roth, Gary E. Bolton and Paul Klemperer

Here is a book on market design in Spanish that arrived unexpectedly in my mailbox: it's by me, Gary Bolton and Paul Klemperer.

You can buy it here (it's cheap, if you read Spanish).

It was unexpected because I didn't know that the first three chapters of the Handbook of Market Design were being translated to form this much briefer new book.


Roth, Alvin E. Gary E. Bolton, and Paul Klemperer, “Diseño de Mercados,” Breviarios del Fondo de Cultura Economica, Mexico, Translated by Karina Azanza, Maria Teresa Franco Gonzalez, and Brian McDougall (2014) [Spanish translation of Chapters 1-3 of The Handbook of Market Design. 

Possibilities for kidney exchange in Mexico

Last week Mike Rees and I spoke at the Centro Medico ABC in Mexico City, to try to help them organize kidney exchange in Mexico.  I'm looking forward to seeing what develops...

Here is some media coverage in Spanish...I can't tell (from Google translate) how clearly various conversations are reported...since I don't speak Spanish, some interviews were also conducted through translators.

Alvin Roth y su mercado de riñones

DISEÑÓ Y ARMÓ UN MERCADO DE RIÑONES FUNCIONALLas repugnantes transacciones 
de Alvin Roth

Radio interview
El Premio Nobel de Economía 2012 viene a contarnos sobre un nuevo esquema para resolver el problema de donación de órganos.

Promueven en México intercambio de riñón para trasplante


A photographic agency seems to be selling photos from the talk I gave at the hospital, at http://agencia.cuartoscuro.com/agencia/categories.php?cat_id=142&sessionid=85691f499806cd80127beb46f415fab0 

****************
Update: here are other news stories with maybe some confusion in the first about the connection between kidney exchange and repugnant transactions...
Nobel de economía diseña mercado de riñones para salvar más vidas

Premio Nobel de Economía al servicio de la medicina 

Nimrod Megiddo awarded the John von Neumann Theory Prize at INFORMS 2014

Nimrod Megiddo was announced as the winner of the 2014 von Neumann Theory Prize at the INFORMS meeting yesterday (although as of this writing the web page hasn't been updated).

He is a deserving member of a distinguished club:

Past Awardees

2013 Winner(s)

Michel L Balinski, C.N.R.S. and Ecole Polytechnique

2012 Winner(s)

George L. Nemhauser, Georgia Institute of TechnologyLaurence A. Wolsey, Université Catholique de Louvain

2011 Winner(s)

Gerard P. Cornuejols, Carnegie Mellon University, Tepper School of Business

2010 Winner(s)

Peter Glynn, Stanford UniversitySøren Asmussen, Aarhus University, Denmark

2009 Winner(s)

Yurii Nesterov, CORE/UCLYinyu Ye, Stanford University, Department of Management Science & Engineering

2008 Winner(s)

Frank P. Kelly, Centre for Mathematical Science, University of Cambridge

2007 Winner(s)

Arthur F. Veinott, Jr., Stanford University

2006 Winner(s)

Martin Grötschel, ZIB
Konrad-Zuse-ZentrumLászló Lovász, Eotvos University, Institute of MathematicsAlexander Schrijver, CWI, National Research Institute for Mathematics & Computer Science

2005 Winner(s)

Robert J. Aumann, The Hebrew University of Jerusalem, Center for Rationality

2004 Winner(s)

J. Michael Harrison, Stanford University, Graduate School of Business

2003 Winner(s)

Arkadi Nemirovski, Georgia Institute of Technology, School of ISyEMichael J. Todd, Cornell University
School of Operations Research and Information

2002 Winner(s)

Cyrus Derman, Professor Operations Research, Columbia UniversityDonald L. Iglehart, Stanford University

2001 Winner(s)

Ward Whitt, Columbia University, Industrial Engineering & Operations Research Dept.

2000 Winner(s)

Ellis L. Johnson, School of Industrial & Systems Engineering, Georgia Institute of TechnologyManfred W. Padberg, New York University, Stern School of Business

1999 Winner(s)

R. Tyrrell Rockafellar, University of Washington, Dept. of Mathematics

1998 Winner(s)

Fred W. Glover, OptTek Systems, Inc.

1997 Winner(s)

Peter Whittle

1996 Winner(s)

Peter C. Fishburn

1995 Winner(s)

Egon Balas, Carnegie Mellon University, Tepper School of Business

1994 Winner(s)

Lajos Takacs

1993 Winner(s)

Robert Herman, University of Texas-Austin

1992 Winner(s)

Alan J. Hoffman, IBMPhilip S. Wolfe, IBM

1991 Winner(s)

Richard E. Barlow, University of California-BerkeleyFrank Proschan

1990 Winner(s)

Richard M. Karp, University of California - Berkeley, Dept. of Electrical Engineering & Computer Science

1989 Winner(s)

Harry M. Markowitz , Baruch College

1988 Winner(s)

Herbert A. Simon

1987 Winner(s)

Samuel Karlin , Stanford University
Dept of Mathematics

1986 Winner(s)

Kenneth J. Arrow , Stanford University, Dept. of Economics

1985 Winner(s)

Jack Edmonds, University of Waterloo, Dept. of Combinatorics & Optimization

1984 Winner(s)

Ralph E. Gomory , Alfred P. Sloan Foundation

1983 Winner(s)

Herbert E. Scarf, Yale University

1982 Winner(s)

Abraham CharnesWilliam W. Cooper, University of Texas - Austin, MSIS DepartmentRichard J. Duffin

1981 Winner(s)

Lloyd S. Shapley , University of California - Los Angeles, Dept. of Economics

1980 Winner(s)

David GaleHarold W. Kuhn, Princeton UniversityAlbert W. Tucker

1979 Winner(s)

David Blackwell , University of California - Berkeley

1978 Winner(s)

John F. Nash, Princeton University, Mathematics Dept.Carlton E. Lemke

1977 Winner(s)

Felix Pollaczek

1976 Winner(s)

Richard Bellman

1975 Winner(s)

George B. Dantzig, Stanford University