Monday, November 17, 2014

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):


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."


Sunday, November 16, 2014

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."

Saturday, November 15, 2014

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?

Friday, November 14, 2014

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.

Thursday, November 13, 2014

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.

Wednesday, November 12, 2014

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. 

Tuesday, November 11, 2014

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


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 

Monday, November 10, 2014

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-Zentrum
Lá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

Matching and Market Design at INFORMS in San Francisco, Monday, Nov 10

More matching and market design today:

Cluster : Auctions

Session Information : Monday Nov 10, 13:30 - 15:00

Title: Analysis of Matching Markets
Chair: Thayer Morrill,NC State University, NC, thayer_morrill@ncsu.edu

Abstract Details

Title: New Algorithms for Fairness and Efficiency in Course Allocation
Presenting Author: Hoda Atef Yekta,PhD Candidate, University of Connecticut, School of Business, 2100 Hillside Road Unit 1041, Storrs CT 06269, United States of America, Hoda.AtefYekta@business.uconn.edu
Co-Author: Robert Day,University of Connecticut, 2100 Hillside Road, U-1041, Storrs CT, United States of America, Bob.Day@business.uconn.edu
Abstract: This research formulates the course allocation problem as a multi objective mathematical model considering both efficiency and measures of fairness. Results of four proposed heuristic algorithms are compared with existing mechanisms and we show that our new algorithms can improve both efficiency and fairness of the results.
Title: Internally Stable Matchings and Exchanges
Presenting Author: Yicheng Liu,liuyicheng1991@hotmail.com
Co-Author: Pingzhong Tang,Assistant Professor, Tsinghua University, Beijing, China, kenshinping@gmail.com
Abstract: We propose an alternative notion of stability for matchings and exchanges, coined internal stability, which only requires stability among matched agents. For internal stability, we analyze the social welfare bounds and computational complexity. Our results indicate that internal stability addresses both the social welfare and computational difficulties associated with traditional stability.
Title: The Secure Boston Mechanism
Presenting Author: Thayer Morrill,NC State University, NC, thayer_morrill@ncsu.edu
Co-Author: Umut Dur,umutdur@gmail.com
Robert Hammond,robert_hammond@ncsu.edu
Abstract: We introduce a new algorithm that is a hybrid between the Boston and Deferred Acceptance algorithm. While not strategy-proof, this ``secure’’ Boston algorithm significantly reduces the incentive for students to strategically manipulate their reported preferences while maintaining the desirable feature of the Boston mechanism of assigning as many students as feasible to their favorite school. We run an experiment in order to test the performance of our new assignment procedure.
Title: Two-sided Matching with Incomplete Information
Presenting Author: Sushil Bikhchandani,UCLA Anderson School of Management, University of California, Los Angeles CA, United States of America, sushil.bikhchandani@anderson.ucla.edu
Abstract: Stability in a two-sided matching model with non-transferrable utility (NTU), interdependent preferences, and one-sided incomplete information is investigated. The notion of incomplete-information stability used here is similar to that of Liu et al. (2014). With anonymous preferences, all strictly individually-rational matchings are incomplete-information stable. An ex post incentive-compatible mechanism exists for this model. Extensions to two-sided incomplete information are investigated.

Cluster : Applied Probability Society

Session Information : Monday Nov 10, 08:00 - 09:30

Title: Matching in Markets
Chair: Ciamac Moallemi,Barbara and Meyer Feldberg Associate Professor of Business, Columbia Business School, 3022 Broadway, Uris 416, New York NY 10027, United States of America, ciamac@gsb.columbia.edu
Co-Chair: Costis Maglaras,Columbia Business School, New York NY, United States of America, cm479@columbia.edu

Abstract Details

Title: Dynamic Matching Markets with an Application in Residential Real Estate
Presenting Author: Hua Zheng,Columbia Business School, 3022 Broadway, Uris 4S, New York NY 10027, United States of America, hzheng14@gsb.columbia.edu
Co-Author: Costis Maglaras,Columbia Business School, New York NY, United States of America, cm479@columbia.edu
Ciamac Moallemi,Barbara and Meyer Feldberg Associate Professor of Business, Columbia Business School, 3022 Broadway, Uris 416, New York NY 10027, United States of America, ciamac@gsb.columbia.edu
Abstract: We study a dynamic microstructure model of a dynamic market where buyers and sellers arrive stochastically over time, and are heterogeneous with respect to their product characteristics and preferences and their idiosyncratic financial information. We analyze its dynamics, market depth, and buyer/seller bidding strategies. The motivating application stems from residential real estate.
Title: Optimal Allocation without Money: An Engineering Approach
Presenting Author: Itai Ashlagi,MIT, 100 Main st., Cambridge MA, United States of America, iashlagi@mit.edu
Co-Author: Peng Shi,MIT, 70 Pacific St, Apt. 348C, Cambridge MA 02139, United States of America, pengshi@mit.edu
Abstract: We study the allocation of heterogeneous services to agents without monetary transfers under incomplete information. The social planner's goal is to maximize a possibly complex public objective. We take an ``engineering'' approach, in which we solve a large market approximation, and convert the solution into a feasible finite market mechanism that still yields good results. We apply this framework to real data from Boston to design a mechanism that assigns students to public schools.
Title: Managing Congestion in Dynamic Matching Markets
Presenting Author: Nick Arnosti,Stanford University, Stanford CA, United States of America, narnosti@stanford.edu
Co-Author: Ramesh Johari,Stanford University, Huang 311, Stanford CA, United States of America, ramesh.johari@stanford.edu
Yash Kanoria,Columbia Business School, 404 Uris Hall, New York NY 10027, United States of America, ykanoria@columbia.edu
Abstract: It is often costly for agents in matching markets to determine whether potential partners are interested in forming a match. This creates friction in the marketplace, lowering welfare for all participants. We use a dynamic model to quantitatively study this effect. We demonstrate that by reducing visibility, the market operator may benefit both sides of the market. Somewhat counter-intuitively, benefits of showing fewer sellers to each buyer are greatest when there is a shortage of sellers.


Cluster :
 Auctions

Session Information : Monday Nov 10, 16:30 - 18:00

Title: Dynamic Matching Markets
Chair: John Dickerson,CMU, 9219 Gates-Hillman Center, Carnegie Mellon University, Pittsburgh PA 15213, United States of America, dickerson@cs.cmu.edu

Abstract Details

Title: Dynamic Matching Using Approximate Dynamic Programming
 Presenting Author: Nikhil Bhat,Columbia University, nbhat15@gsb.columbia.edu
 Co-Author: Ciamac Moallemi,Barbara and Meyer Feldberg Associate Professor of Business, Columbia Business School, 3022 Broadway, Uris 416, New York NY 10027, United States of America, ciamac@gsb.columbia.edu
 
Abstract: We provide tractable algorithms for a large number of challenging dynamic decision making problems such as 1) Allocation of cadaveric kidneys to patients, 2) Matching ads with impressions, 3) Cyclic paired transfer of kidneys, by analyzing them using a general model. Our policies are easy to compute and interpret, and further come with approximation guarantees. With simulation experiments on kidney allocation, we show that we obtain gain over existing algorithms in literature.
  
Title: Dynamic Matching Market Design
 Presenting Author: Mohammad Akbarpour,Stanford University, 579 Serra Mall, 265F, Stanford CA 94305, United States of America, mohamwad@stanford.edu
 Co-Author: Shengwu Li,Stanford University, 579 Serra Mall, 265B, Stanford CA 94305, United States of America, shengwu@stanford.edu
 Shayan Oveis Gharan,UC Berkeley, Berkeley Ca 94105, United States of America, oveisgharan@berkeley.edu
 
Abstract: We show that, in dynamic matching markets, waiting to thicken the market can be substantially more important than increasing the speed of transactions. In particular, simple local algorithms that wait to thicken the market can perform very close to optimal algorithms. We prove our claims by analyzing a simple but illuminating model of dynamic matching in networked markets where agents arrive and depart stochastically.
  
Title: The Roles of Common and Private Information in Two-Sided Matching with Interviews
 Presenting Author: Sanmay Das,Associate Professor, Washington University in St. Louis, sanmay@seas.wustl.edu
 Co-Author: Zhuoshu Li,Washington Univ. in St. Louis, One Brookings Dr, CB 1045, Saint Louis MO 63130, United States of America, zhuoshuli@wustl.edu
 
Abstract: We consider two sided matching markets where employers have a fixed budget for the number of applicants they may interview. Employers receive noisy signals of how good each applicant is, and these signals include common and private components. We analyze how the strengths of these two components affect matching outcomes (both differentially across different quality candidates, and in the aggregate number of matches) when decisions about whom to interview are strategic.
  
Title: FutureMatch: Learning to Match in Dynamic Environments
 Presenting Author: John Dickerson,CMU, 9219 Gates-Hillman Center, Carnegie Mellon University, Pittsburgh PA 15213, United States of America, dickerson@cs.cmu.edu
 Co-Author: Tuomas Sandholm,Carnegie Mellon University, 5000 Forbes Ave., Pittsburgh PA 15213, United States of America, sandholm@cs.cmu.edu
 
Abstract: Kidney exchange, an innovation where willing but incompatible donor-patient pairs can exchange organs, is inherently dynamic. We present FutureMatch, an empirical framework for learning to match in a general dynamic model. We validate it on real data. Not only does dynamic matching result in more expected transplants than myopic, but even dynamic matching under economically inefficient (equitable) objectives can result in significant increases in social welfare over efficient myopic matching.