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.

Matching and Market Design at INFORMS in San Francisco, Sunday November 9

There's a lot of market design at the INFORMS annual meeting, Nov 9-12.

On Sunday I'll start the day off with a talk from  10-10:50 called
"Market Design and the Economist as Engineer."

That will be followed by a cluster of talks organized by Itai Ashlagi called (embarrassingly)
Matching and Market Design (in honor of Al Roth), consisting of the following sessions

Cluster :	Matching and Market Design (in honor of Al Roth)
Session Information		: Sunday Nov 09, 11:00 - 12:30
Title:	Empirical Market Design
Chair:	Ramesh Johari,Stanford University,
Abstract Details
Title:	Quality Externalities and the Limits of Reputation in Two-Sided Markets
	Presenting Author:	Steve Tadelis,Professor, UC Berkeley, Haas School of Business, 2220 Piedmont Ave, Berkeley, United States of America, stadelis@haas.berkeley.edu
	Co-Author:	Chris Nosko,Booth School of Business, University Of Chicago, Chicago, United States of America, cnosko@chicagobooth.edu
Abstract:		Using data from eBay, we argue that platforms can mitigate externalities by actively screening sellers and promoting the prominence of better quality sellers. Exploiting the bias in feedback, we create a measure of seller quality and demonstrate the benefits of our approach through a controlled experiment that prioritizes better quality sellers to a random subset of buyers. .
Title:	On the Near Impossibility of Measuring the Returns to Advertising
	Presenting Author:	Randall Lewis,Economic Research Scientist, Google Inc., 1600 Amphitheatre Parkway, Mountain View Ca 94043, United States of America, randall@econinformatics.com
	Co-Author:	Justin Rao,Economic Research Scientist, Microsoft Research, New York City NY, United States of America, Justin.Rao@microsoft.com
Abstract:		Firms have a hard time measuring the causal impact of advertising expenditures on profit. In twenty-five online field experiments, individual-level sales are volatile relative to the per capita cost of a campaign--a small impact on a noisy dependent variable can generate positive returns. Experiments can need more than ten million person-weeks. Further, small selection biases can severely bias observational estimates. Weak informational feedback and technological advances shape ad marketplaces.
Title:	Corporate Prediction Markets: Evidence from Google, Ford, and Firm X
	Presenting Author:	Bo Cowgill,UC Berkeley, 1931 Diamond St Apt 3, SAN FRANCISCO Ca 94131, United States of America, bo.cowgill@gmail.com
	Co-Author:	Eric Zitezwitz,Dartmouth College, 6106 Rockefeller Hall, Hanover NH, United States of America, zitzewitz@dartmouth.edu
Abstract:		We examine data from prediction markets run by Google, Ford and Firm X (a large private materials company). Despite theoretically adverse conditions, we find these markets are relatively efficient, and improve upon the forecasts of experts at all three firms by as much as a 25% reduction in MSE. The most notable inefficiency is an optimism bias in the markets at Google and Ford. The inefficiencies that do exist become smaller over time for reasons we document.
Title:	At What Quality and What Price? Inducing Separating Equilibria as a Market Design Problem
	Presenting Author:	John Horton,Professor, NYU Stern School of Business, Kaufman Management Center, 44 West Fourth St, 8-81, New York NY 10012, United States of America, john.joseph.horton@gmail.com
	Co-Author:	Ramesh Johari,Stanford University, Huang 311, Stanford, United States of America, ramesh.johari@stanford.edu
Abstract:		A tool to promote revelation of buyers' price/quality preferences was experimentally introduced into an online labor market. In the treatment cells of the experiment, upon posting a job, buyers chose what price/quality level they were seeking from sellers. We find that buyers readily reveal their preferences and that this revelation---which itself was experimentally manipulated---strongly induced seller-side sorting.

Title:	******** Matching and Market Design
Chair:	Jacob Leshno,Columbia University,
Abstract Details
Title:	Matching in Networks
	Presenting Author:	Michael Ostrovsky,Associate Professor of Economics, Stanford Graduate School of Business, 655 Knight Way, Stanford CA 94305, United States of America, ostrovsky@stanford.edu
Abstract:		In this talk, I will present results on the existence and properties of stable outcomes in trading networks.
Title:	Matching with Peers in School Choice
	Presenting Author:	Atila Abdulkadiroglu,Professor, Duke University, 213 Social Sciences Building, Durham NC 27708, United States of America, atila.abdulkadiroglu@duke.edu
Abstract:		We develop a theory for matching of students to schools with peers and study various matching mechanisms with field data.
Title:	Endogenous preferences and the role of the mechanism in school choice
	Presenting Author:	Estelle Cantillon,Senior Research Fellow, Université Libre de Bruxelles (ECARES), 50, av FD Roosevelt, CP 114, Brussels 1050, Belgium, Estelle.Cantillon@ulb.ac.be
Abstract:		We consider a school choice model where preferences over schools are endogenous because students care about the quality of their peers. In such a setting, the mechanism affects the degree of preference polarization. We show how mechanisms can be designed to reduce polarization and improve the distribution of ranks of assigned schools in students’ preferences. A policy change in the city of Ghent (Belgium) provides a test for the predictions of the theory.
Title:	Evidence of Strategic Behavior in Hospital Claims Reporting
	Presenting Author:	Hamsa Bastani,Stanford University, Stanford, Stanford, United States of America, hsridhar@stanford.edu
	Co-Author:	Mohsen Bayati,Stanford Graduate School of Business, Stanford CA 94305, United States of America, bayati@gsb.stanford.edu
		Joel Goh,joelgoh@stanford.edu
		Stefanos Zenios,Charles A. Holloway Professor of Operations, Information, and Technology and Professor of Health Care Management, Stanford Graduate School of Business, 655 Knight Way, Stanford CA 94305, United States of America, stefzen@GSB.Stanford.Edu
Abstract:		We provide evidence from Medicare claims data that hospitals engage in upcoding behavior when reporting hospital-acquired infections that are no longer reimbursed by Medicare. In particular, we show that hospitals sometimes mark a hospital-acquired infection as present-on-admission, presumably in order to collect greater reimbursement.

*******

Title:	Matching Markets
Chair:	Yash Kanoria,Columbia Business School,
Abstract Details
Title:	Stable Matching in Large Economies
	Presenting Author:	Fuhito Kojima,Stanford University, 579 Serra Mall, Stanford CA 943055007, United States of America, fkojima@stanford.edu
Abstract:		Complementarities of preferences have been known to jeopardize stability of two-sided matching markets, yet they are a pervasive feature in many matching markets. In large markets, we demonstrate that if each firm's choice changes continuously as the set of available workers changes, then there exists a stable matching even if firm preferences exhibit complementarity. Building on this result, we show that there exists an approximately stable matching in any large finite economy.
Title:	The Prior-Independence Approach
	Presenting Author:	Inbal Talgam-Cohen,PhD Candidate, Stanford University, 86 Hulme Ct, Apt 108, Stanford CA 94305, United States of America, italgam@stanford.edu
	Co-Author:	Tim Roughgarden,Stanford, 353 Serra Street, Stanford, United States of America, tim@cs.stanford.edu
Abstract:		The matching literature has recently begun to consider priors on agents’ utilities. One of the barriers to adopting this potentially very fruitful approach is that priors add significant informational assumptions to the model. We survey a successful alternative approach from mechanism design called prior independence, which alleviates such assumptions while still reaping most benefits. We discuss both sampling-based methods and methods based on ensuring sufficient competition in the market.
Title:	The structure of the core in assignment markets
	Presenting Author:	Yash Kanoria,Columbia Business School, 404 Uris Hall, New York NY 10027, United States of America, ykanoria@columbia.edu
	Co-Author:	Daniela Saban,Columbia University, Uris Hall, 4I, New York, United States of America, dhs2131@columbia.edu
		Jay Sethuraman,Columbia University, IEOR Department, New York, United States of America, jay@ieor.columbia.edu
Abstract:		Assignment markets (Shapley & Shubik 1971) involve matching with transfers, as in labor markets and housing markets. We consider a two-sided assignment market with agent types and stochastic structure similar to models used in empirical studies. Each agent has a randomly drawn "productivity" associated with each type on the other side. We characterize how the structure of the core, i.e., the set of stable outcomes, is determined by market characteristics.

Kidney Exchange and Operations Research: Edelman award presentation (video)

Here are all the 2014 Edelman Award Presentations, including the one my colleagues and I gave on kidney exchange, on March 31. Ours is the second from the top (the winning entry is first), and to see the video you have to scroll to the bottom of the description or our lecture (reproduced below) and click on "View Presentation." (I couldn't figure out how to embed it here.)

The video of our presentation (35 minutes) is more elaborate than most of the lectures I've done, since it includes some video footage. I joined Josh Morrison of the Alliance for Paired Donation and Itai Ashlagi of MIT in making the presentation.  Mike Rees spoke in some of the videos. Ross Anderson and David Gamarnik joined us to answer questions, and Tayfun Sonmez and Utku Unver joined for the celebratory dinner later in the day. (For our efforts, we are all 2014 Edelman Laureates.)

Alliance for Paired Donation with Boston College, Stanford University and MIT: Kidney Exchange

Presented by: Josh Morrison, Alvin E. Roth, Itai Ashlagi Authors: Alliance for Paired Donation:  Michael A. Rees, Michael.Rees2@utoledo.edu; Josh Morrison,joshcmorrison@gmail.com; Boston College: Tayfun Sönmez,sonmezt@bc.edu; M. Utku Ünver, unver@bc.edu MIT: Itai Ashlagi, iashlagi@mit.edu; Ross Anderson, rma350@gmail.com; David Gamarnik,gamarnik@mit.edu Stanford University:  Alvin E. Roth, alroth@stanford.edu Abstract: Many end-stage renal disease sufferers who require a kidney transplant to prolong their lives have relatives or associates who have volunteered to donate a kidney to them, but whose kidney is incompatible with their intended recipient. This incompatibility can be sometimes overcome by exchanging kidneys with another incompatible donor pair. Such kidney exchanges have emerged as a standard mode of kidney transplantation in the United States. The Alliance for Paired Donation (APD) developed and implemented an innovative operations research based methodology of non-simultaneous extended altruistic donor (NEAD) chains, which, by allowing a previously binding constraint (of simultaneity) to be relaxed, allowed better optimized matching of potential donors to patients, which greatly increases the number of possible transplants. Since 2006, the APD has saved more than 220 lives through its kidney exchange program, with more than 75% of these achieved through long non-simultaneous chains. The technology and methods pioneered by APD have been adopted by other transplant exchanges, resulting in thousands of lives already saved, with the promise of increasing impact in coming years. The percentage of transplants from non-simultaneous chains has already reached more than 6% of the total number of transplants from live donors (including directed living donors) in the last year. We describe the long-term optimization and market design research that supports this innovation. We also describe how the team of physicians and operations researchers worked to overcome the skepticism and resistance of the medical community to the NEAD innovation.

Some memories of Cy Derman

Annals of Operations Research has published online a paper on the life and work of Cyrus Derman, by Katehakis, Olkin and Ross.

1. OriginalPaper

   On the life and work of Cyrus Derman

   Michael N. Katehakis, Ingram Olkin, Sheldon M. Ross…
   

   Download PDF (1150KB) View Article

I knew Derman as an undergrad at Columbia. So, in the manner of undergrads, I didn't know him at all well. I nevertheless remember him fondly.

1. Letter

   Some memories of Cy Derman

   Alvin E. Roth
   

   Download PDF (117KB) View Article

Here's the text of my letter:

I came to Columbia in 1968 as an undergraduate in the engineering school. I didn’t know what I wanted to major in, and declared an interest in nuclear engineering, so that I could take as many physics courses as I wanted. But the summer after my freshman year I took a summer job in Washington D.C. at an Army lab for which I had qualified by taking a civil service exam. They had an OR group, and I returned to school as an OR major.

In the manner of undergraduates, I didn’t have a clear idea of what my teachers did. But I recall admiring Cy Derman’s attitude: he seemed not to take himself too seriously. I recall he wore turtleneck shirts and talked about tennis, and summers at Stanford.

When it came time to think about graduation, Cy urged me to think about grad school in OR, and volunteered to write a letter for me. Some time later, in a reflective moment, he said something to me like “I wrote you a very good letter. I’m not exactly sure why; you didn’t do all that well in your courses. But I have a feeling that you might be good at research.” Cornell and Stanford were the programs he recommended, and when I was accepted at both, his preference was clear, and I followed his advice, which set me on a path I’m still following.