Monday, November 10, 2014

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.
  

No comments: