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. 

Course allocation at Wharton: looking under the hood

A new paper by Budish, Cachon, Kessler and Othman gives more detail on how the course allocation tool at Wharton works at a computational level. It's a great example of practical market design as economic engineering.

Course Match: A Large-Scale Implementationof Approximate Competitive Equilibrium from Equal Incomesfor Combinatorial Allocation⇤
Eric Budish, Gerard P. Cachon, Judd Kessler, and Abraham Othman¶
July 23, 2015

Abstract:  Combinatorial allocation involves assigning bundles of items to agents when the use of money is not allowed. Course allocation is one common application of combinatorial allocation, in which the bundles are schedules of courses and the assignees are students. Existing mechanisms used in practice have been shown to have serious flaws, which lead to allocations that are inefficient, unfair, or both. A new mechanism proposed by Budish [2011] is attractive in theory, but has several features that limit its feasibility for practice: reporting complexity, computational complexity, and approximations that can lead to violations of capacity constraints. This paper reports on the design and implementation of a new course allocation mechanism, Course Match, that enhances the Budish [2011] mechanism in various ways to make it suitable for practice. To find allocations, Course Match performs a massive parallel heuristic search that solves billions of Mixed-Integer Programs to output an approximate competitive equilibrium in a fake-money economy for courses. Quantitative summary statistics for two semesters of full-scale use at a large business school (Wharton, which has about 1,700 students and up to 350 courses in each semester) demonstrate that Course Match is both fair and efficient, a finding reinforced by student surveys showing large gains in satisfaction and perceived fairness
*****************

In the conclusion, they write

"A critical feature for the success of Course Match is its “strategy-proof” property — a student’s best strategy is to report her true preferences no matter what preferences other students report or what capacities are assigned to each course. This greatly simplifies the student’s reporting task because the student need not form beliefs about how other students will “play” or what clearing prices might be for courses. In contrast, the Wharton Auction (as well as all other course-allocation mechanisms implemented in practice) was not strategy-proof. For example, if a student desires a course but believes that it will have a zero clearing price, then the student should rationally submit a low bid and save tokens to bid on other courses. However, the student may make a mistake and not receive the course she desires if the clearing price turns out to be higher than expected. This bidding mistake is not trivial and it could even lead a student with ample tokens to receive zero courses. Such errors do not happen with Course Match because Course Match effectively bids on behalf of students after all of the clearing prices have been revealed."
...
"while the Course Match mechanism has many desirable theoretical properties, if the preference language given to students is not sufficiently rich (i.e., it does not allow students to express critical preferences) or if students are not able to “speak” this language (i.e., they cannot use the language to correctly report their preferences), then Course Match may not yield desirable results. We are not able to provide direct evidence of the quality of the Course Match preference reporting language and user interface, but the high overall student satisfaction scores provide indirect evidence that the Course Match language is su!ciently rich and easy to use."
...
"We do not claim that the Course Match computational architecture is “optimal.” Indeed, an important question left for future research is whether there are better approaches to finding approximate market-clearing prices than that described here. We do show, however, that the Course Match computational architecture works at Wharton. To borrow a common analogy (e.g., Roth [2002]), ours is an exercise of engineering rather than physics."

State by state variations in organ donation policy in the U.S. have little effect: JAMA Internal Medicine

The Effect of State Policies on Organ Donation and Transplantation in the United States  
Paula Chatterjee; Atheendar S. Venkataramani ; Anitha Vijayan ; Jason R. Wellen; Erika G. Martin

JAMA Intern Med. Published online June 01, 2015. doi:10.1001/jamainternmed.2015.2194


Abstract:
"Importance  Shortages in transplantable solid organs remain a critical public health challenge in the United States. During the past 2 decades, all states have implemented policies to increase organ supply, although their effectiveness is unknown.

Objective  To determine the effects on organ donation and transplantation rates of state policies to provide incentives for volunteer donation.

Design, Setting, and Participants  Using a quasi-experimental design and difference-in-differences regression analyses, we estimated the effect of policies in all 50 states and the District of Columbia on organ donors per capita and the number of transplantations from January 1, 1988, to December 31, 2010. Analyses were also stratified by type of donor (living vs deceased). Data were derived from the United Network for Organ Sharing. All data collection occurred between July 7 and September 27, 2013.

Exposures  Policies of interest were the presence of first-person consent laws, donor registries, dedicated revenue streams for donor recruitment activities, population education programs, paid leave for donation, and tax incentives. Information on states’ passage of various policies was obtained from primary legislative and legal sources.

Main Outcomes and Measures  The number of organ donors and transplantations per state, per year, during the study period.

Results  From 1988 to 2010, the number of states passing at least 1 donation-related policy increased from 7 (14%) to 50 (100%). First-person consent laws, donor registries, public education, paid leave, and tax incentives had no robust, significant association with either donation rates or number of transplants. The establishment of revenue policies, in which individuals contribute to a protected state fund for donation promotion activities, was associated with a 5.3% increase in the absolute number of transplants (95% CI, 0.57%-10.1%; P = .03). These associations were driven by a 4.9% increase in organ donations (95% CI, 0.97%-8.7%; P = .01) and an 8.0% increase in transplants (95% CI, 3.1%-12.9%; P = .001) from deceased donors as opposed to changes among living donors or transplants from living donors.


Conclusions and Relevance  Nearly all state-level policies to encourage organ donation have had no observable effect on the rate of organ donation and transplantation in the United States. The one exception was the establishment of revenue policies to promote organ donation, which may have led to small increases in organ donations and transplantations from deceased donors. New policy designs are needed to increase donation rates and curtail the widening gap between organ supply and demand."

Journal of Human Trafficking, Issue 1, 2015, on kidneys

Issue 1 of the Journal of Human Trafficking contains this article by Alexander Capron and Frank Delmonico. I've highlighted in the abstract two points worth noting--the first involves some untested, but testable empirical claims about what would happen if countries in the first world allowed compensation for donors. (It would be nice to have some empirical evidence...)  The second point is that it is now agreed by everyone that financial disincentives for donating should be removed. (Let's get organized on that, shall we?)

Preventing Trafficking in Organs for Transplantation: An Important Facet of the Fight Against Human Trafficking

DOI:10.1080/23322705.2015.1011491

Alexander M. Caprona & Francis L. Delmonico

pages 56-64

Published online: 28 Apr 2015

Abstract

Most countries now have national legislation that outlaws both human trafficking and organ trafficking. However, international conventions and domestic laws alone have not been enough to stop the trade in organs. As of 2007, a conservative estimate was that 5% of the approximately 100,000 organs transplanted annually were derived from exploiting the poorest and most vulnerable people in society; anti-trafficking efforts have since reduced, though not eliminated, this practice. The Declaration of Istanbul (DoI) was created in 2008 to engage medical professional societies to collaborate with governments and others in combating organ sales, transplant tourism, and trafficking in human organs. In 2010, the Declaration of Istanbul Custodian Group (DICG) was formed to actively promote and to monitor the implementation of the DoI principles. The removal of prohibitions on organ purchases, which is now being promoted in some wealthy nations, is unlikely to shorten transplant waitlists (because organ sales crowd out voluntary, unpaid donation) and would be based on the false view that such sales do not exploit the sellers. To combat such exploitation, the DICG advocates for ratification and enforcement of the new “Council of Europe Convention against Trafficking in Human Organs,” as a complement the Palermo Protocol to the United Nations organized crime convention that prohibits human trafficking for organ removal. To increase ethical organ donation by living related donors, the DICG encourages countries to adopt means to cover donors’ financial costs, which now discourage donation. It also works with the World Health Organization to encourage ministries of health to develop deceased donation to its maximum potential toward the goal of achieving national self-sufficiency in organ transplantation so that patients do not need to travel to foreign destinations to undergo organ transplantation using kidneys and partial livers purchased from poor and vulnerable people. Success in combating human trafficking for organ removal and organ trafficking will be greatly enhanced through organizations like the DICG forging strong relationships with human rights organizations.

Elias, Lacetera and Macis on the repugnance of paying for organs or prostitution: a survey experiment

Markets and Morals: An Experimental Survey Study
Julio J. Elias , Nicola Lacetera , Mario Macis

PLOS One. Published: June 1, 2015DOI: 10.1371/journal.pone.0127069

Abstract: Most societies prohibit some market transactions based on moral concerns, even when the exchanges would benefit the parties involved and would not create negative externalities. A prominent example is given by payments for human organs for transplantation, banned virtually everywhere despite long waiting lists and many deaths of patients who cannot find a donor. Recent research, however, has shown that individuals significantly increase their stated support for a regulated market for human organs when provided with information about the organ shortage and the potential beneficial effects a price mechanism. In this study we focused on payments for human organs and on another “repugnant” transaction, indoor prostitution, to address two questions: (A) Does providing general information on the welfare properties of prices and markets modify attitudes toward repugnant trades? (B) Does additional knowledge on the benefits of a price mechanism in a specific context affect attitudes toward price-based transactions in another context? By answering these questions, we can assess whether eliciting a market-oriented approach may lead to a relaxation of moral opposition to markets, and whether there is a cross-effect of information, in particular for morally controversial activities that, although different, share a reference to the “commercialization” of the human body. Relying on an online survey experiment with 5,324 U.S. residents, we found no effect of general information about market efficiency, consistent with morally controversial markets being accepted only when they are seen as a solution to a specific problem. We also found some cross-effects of information about a transaction on the acceptance of the other; however, the responses were mediated by the gender and (to a lesser extent) religiosity of the respondent—in particular, women exposed to information about legalizing prostitution reduced their stated support for regulated organ payments. We relate these findings to prior research and discuss implications for public policy.

Is sniping bad for eBay? New paper by Bakus, Blak, Masterov and Tadelis

Is Sniping A Problem For Online Auction Markets? by Matt Backus, Tom Blak,  Dimitriy V. Masterov, and Steve Tadelis

Abstract: "A common complaint about online auctions for consumer goods is the presence of “snipers,” who place bids in the final seconds of sequential ascending auctions with predetermined ending times. Roth and Ockenfels (2002) and Bajari and Hortacsu (2003) conjecture that snipers are best-responding to the existence of “incremental” bidders that bid up to their valuation only as they are outbid. Snipers aim to catch these incremental bidders at a price below their reserve, with no time to respond.  As a consequence, these incremental bidders may experience regret when they are outbid at the last moment at a price below their reservation value. We measure the effect of this experience on a new buyer’s propensity to participate in future auctions. We also consider an alternative explanation, rooted in the behavioral literature on the endowment effect. Bidders may gradually develop an attachment to the object while they are the high bidder, implying that the regret should increase with time spent in the lead. We show that the two narratives are econometrically separable,
and estimate them using a carefully selected subset of auctions from eBay.com."

They find that first-time bidders who are outbid in the final seconds of an auction are less likely to return to eBay: here's a graph of the probability of not returning, as a function of how close to the end of th auction the first time bidder was successfully sniped...

They conclude: "As a result, sniping has a negative impact on the growth rate of the auction platform."

More Money, More Problems? Can High Pay Be Coercive and Repugnant?

One of the places where medical ethicists' intuitions are most different from those of economists is whether certain monetary transactions can become repugnant when the amount of money involved becomes high enough to be "coercive." Here's a brief paper that tries to bridge that gap.

Ambuehl, Sandro, Muriel Niederle, and Alvin E. Roth. 2015. "More Money, More Problems? Can High Pay Be Coercive and Repugnant?" American Economic Review, 105(5): 357-60.

IRBs can disallow high incentives they deem coercive. A vignette study on MTurk concerning participation in medical trials shows that a substantial minority of subjects concurs. They think high incentives cause more regret, and that more people would be better off without the opportunity to participate. We model observers as judging the ethicality of incentives by partially using their own utility. The model predicts that payments are repugnant only to the extent that they affect the participation decision, and more so for larger transactions. Incentivizing poorer participants is more repugnant, and in-kind incentives are less repugnant than monetary incentives.

Sandro Ambuehl is at the forefront of exploring the nexus of high pay, repugnance and coercion. He'll be on the market next year...and is definitely worth keeping an eye on.

Kidney exchange in Switzerland

Here's a paper reviewing kidney exchange around the world, from an Australian perspective (Paolo Ferrari has been one of the Australian pioneers), and advocating for a national kidney exchange program in Switzerland...

Kidney paired donation: a plea for a Swiss National Programme

Karine Hadayaa,b, Thomas Fehrc, Barbara Rüsic, Sylvie Ferrari-Lacrazd, Jean Villardd, Paolo Ferrarie,f

a Service of Nephrology. Geneva University Hospital, Geneva, Switzerland
b Service of Transplantation, Geneva University Hospital, Geneva, Switzerland
c Service of Nephrology and Histocompatibility laboratory, Zurich University Hospital, Switzerland
d Transplant Immunology Unit and National Reference Laboratory for Histocompatibility (LNRH), Division of Immunology, Allergy and Laboratory Medicine, Geneva, Switzerland
e Department of Nephrology, Prince of Wales Hospital and Clincal School, University of New South Wales, Randwick, Sydney, Australia
f Organ and Tissue Authority, Australia

Summary

Growing incidence of end-stage renal disease, shortage of kidneys from deceased donors and a better outcome for recipients of kidneys from living donor have led many centres worldwide to favour living donor kidney transplantation programmes. Although criteria for living donation have greatly evolved in recent years with acceptance of related and unrelated donors, an immunological incompatibility, either due to ABO incompatibility and/or to positive cross-match, between a living donor and the intended recipient, could impede up to 40% of such procedures. To avoid refusal of willing and healthy living donors, a number of strategies have emerged to overcome immunological incompatibilities. Kidney paired donation is the safest way for such patients to undergo kidney transplantation. Implemented with success in many countries either as national or multiple regional independent programmes, it could include simple exchanges between any number of incompatible pairs, incorporate compatible pairs and non-directed donors (NDDs) to start a chain of compatible transplantations, lead to acceptance of ABO-incompatible matching, and integrate desensitising protocols. Incorporating all variations of kidney paired donation, the Australian programme has been able to facilitate kidney transplantation in 49% of registered incompatible pairs. This review is a plea for implementing a national kidney paired donation programme in Switzerland.

Swiss Med Wkly. 2015;145:w14083