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