On Matching and Thickness in Heterogeneous Dynamic Markets
We study dynamic matching in an infinite-horizon stochastic market. Although all agents are potentially compatible with each other, some are hard to match and others are easy to match. Agents prefer to be matched as soon as possible, and matches are formed either bilaterally or indirectly through ch...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute for Operations Research and the Management Sciences (INFORMS)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/129346 |
| _version_ | 1811070280440741888 |
|---|---|
| author | Burq, Maximilien Jaillet, Patrick |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Burq, Maximilien Jaillet, Patrick |
| author_sort | Burq, Maximilien |
| collection | MIT |
| description | We study dynamic matching in an infinite-horizon stochastic market. Although all agents are potentially compatible with each other, some are hard to match and others are easy to match. Agents prefer to be matched as soon as possible, and matches are formed either bilaterally or indirectly through chains. We adopt an asymptotic approach and compute tight bounds on the limit of waiting time of agents under myopic policies that differ in matching technology and prioritization. We find that when hard-to-match agents arrive less frequently than easy-to-match ones, (i) bilateral matching is almost as efficient as chains (waiting times scale similarly under both, though chains always outperform bilateral matching by a constant factor), and (ii) assigning priorities to hard-to-match agents improves their waiting times. When hard-to-match agents arrive more frequently, chains are much more efficient than bilateral matching, and prioritization has no impact. Furthermore, somewhat surprisingly, we find that in a heterogeneous market and under bilateral matching, increasing the arrival rate of hard-to-match agents has a nonmonotone effect on waiting times. This behavior is in contrast with that of a homogeneous dynamic market, where increasing arrival rate always improves waiting time, and it highlights fundamental differences between heterogeneous and homogeneous dynamic markets. |
| first_indexed | 2024-09-23T08:33:58Z |
| format | Article |
| id | mit-1721.1/129346 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T08:33:58Z |
| publishDate | 2021 |
| publisher | Institute for Operations Research and the Management Sciences (INFORMS) |
| record_format | dspace |
| spelling | mit-1721.1/1293462022-09-30T09:40:01Z On Matching and Thickness in Heterogeneous Dynamic Markets Burq, Maximilien Jaillet, Patrick Sloan School of Management Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science We study dynamic matching in an infinite-horizon stochastic market. Although all agents are potentially compatible with each other, some are hard to match and others are easy to match. Agents prefer to be matched as soon as possible, and matches are formed either bilaterally or indirectly through chains. We adopt an asymptotic approach and compute tight bounds on the limit of waiting time of agents under myopic policies that differ in matching technology and prioritization. We find that when hard-to-match agents arrive less frequently than easy-to-match ones, (i) bilateral matching is almost as efficient as chains (waiting times scale similarly under both, though chains always outperform bilateral matching by a constant factor), and (ii) assigning priorities to hard-to-match agents improves their waiting times. When hard-to-match agents arrive more frequently, chains are much more efficient than bilateral matching, and prioritization has no impact. Furthermore, somewhat surprisingly, we find that in a heterogeneous market and under bilateral matching, increasing the arrival rate of hard-to-match agents has a nonmonotone effect on waiting times. This behavior is in contrast with that of a homogeneous dynamic market, where increasing arrival rate always improves waiting time, and it highlights fundamental differences between heterogeneous and homogeneous dynamic markets. National Science Foundation (U.S.) (Grant OR-1029603) United States. Office of Naval Research (Grants N00014-12-1-0033 and N00014-15-1-2083) 2021-01-08T15:44:29Z 2021-01-08T15:44:29Z 2019-06 2018-05 2020-12-21T18:11:52Z Article http://purl.org/eprint/type/JournalArticle 0030-364X 1526-5463 https://hdl.handle.net/1721.1/129346 Ashlagi, Itai et al. “On Matching and Thickness in Heterogeneous Dynamic Markets.” Operations Research, 67, 4 (June 2019): ii-iv, 905-1208 © 2019 The Author(s) en 10.1287/OPRE.2018.1826 Operations Research Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute for Operations Research and the Management Sciences (INFORMS) arXiv |
| spellingShingle | Burq, Maximilien Jaillet, Patrick On Matching and Thickness in Heterogeneous Dynamic Markets |
| title | On Matching and Thickness in Heterogeneous Dynamic Markets |
| title_full | On Matching and Thickness in Heterogeneous Dynamic Markets |
| title_fullStr | On Matching and Thickness in Heterogeneous Dynamic Markets |
| title_full_unstemmed | On Matching and Thickness in Heterogeneous Dynamic Markets |
| title_short | On Matching and Thickness in Heterogeneous Dynamic Markets |
| title_sort | on matching and thickness in heterogeneous dynamic markets |
| url | https://hdl.handle.net/1721.1/129346 |
| work_keys_str_mv | AT burqmaximilien onmatchingandthicknessinheterogeneousdynamicmarkets AT jailletpatrick onmatchingandthicknessinheterogeneousdynamicmarkets |