Speaker: Dr. Suleyman Kerimov Stanford University
Date & Time: December 20, 2021, Monday, 17:30
Join Zoom Meeting
https://zoom.us/j/9937664491?pwd=R0FNalFFZUM0Wm9MaitiYWJrbVhodz09
Meeting ID: 993 766 4491
Passcode: 525871
Title: Near-Optimal Policies for Dynamic Matching
Abstract: We consider centralized dynamic matching markets with finitely many agent types and heterogeneous match values. A network topology determines the feasible matches in the market and the value generated from each match. An inherent trade-off arises between short- and long-term objectives. A social planner may delay match decisions to thicken the market and increase match opportunities to generate high value. This inevitably compromises short-term value, and the planner may match greedily to maximize short-term objectives.
A matching policy is hindsight optimal if the policy can (nearly) maximize the total value simultaneously at all times. We first establish that in multi-way networks, where a match can include more than two agent types, acting greedily is suboptimal, and a simple periodic clearing policy with a carefully chosen period length is hindsight optimal. Interestingly, in two-way networks, where any match includes two agent types, suitably designed greedy policies also achieve hindsight optimality. This implies that there is essentially no positive externality from having agents waiting to form future matches.
Central to our results is the general position gap, ε, which quantifies the stability or the imbalance in the network. No policy can achieve a regret that is lower than the order of 1/ε at all times. This lower bound is achieved by the proposed policies.
Bio: Süleyman Kerimov is a Ph.D. Candidate in Operations Research at Stanford University Department of Management Science and Engineering. He is interested in market design, matching theory, and applied probability. His research is motivated by the frictions that arise in various marketplaces such as kidney exchange, labor markets, and logistics. He holds a B.S. in Mathematics from Bilkent University.
