Near-optimal Adaptive Policies for Dynamic Matching Markets
Event details
| Date | 30.03.2026 |
| Hour | 11:15 › 12:00 |
| Speaker | Alireza Amanihamedani, PhD candidate in Operations Research at London Business School, United Kingdom |
| Location | |
| Category | Conferences - Seminars |
| Event Language | English |
Abstract:
We study a continuous-time, infinite-horizon dynamic bipartite matching problem. Suppliers arrive according to a Poisson process; while waiting, they may abandon the queue at a uniform rate. Customers on the other hand must be matched upon arrival. The objective is to minimize the expected long-term average cost subject to a throughput constraint on the total match rate.
Previous literature on dynamic matching focuses on "static" policies, where the matching decisions do not depend explicitly on the state of the supplier queues, achieving constant-factor approximations. By contrast, we design "adaptive" policies, which leverage queue length information, and obtain near-optimal polynomial-time algorithms for several classes of instances.
First, we develop a bi-criteria fully polynomial-time approximation scheme for dynamic matching on networks with a constant number of queues--that computes a (1-ε)-approximation of the optimal policy in time polynomial in both the input size and 1/ε. A key new technique is a hybrid LP relaxation, which combines static and state-dependent LP approximations of the queue dynamics, after a decomposition of the network. Networks with a constant number of queues are motivated by deceased organ donation schemes, where the supply types can be divided according to blood and tissue types.
The above algorithm, combined with a careful spatial decomposition gives an efficient polynomial-time approximation scheme for dynamic matching on Euclidean networks of fixed dimension. The Euclidean case is of interest in ride-hailing and spatial service platforms, where the goal is to fulfill as many trips as possible while minimizing driving distances.
Biography:
Alireza Amanihamedani is a final-year PhD candidate in Operations Research at London Business School, advised by Prof. Ali Aouad. His research interests are in online and dynamic optimization with applications to market design. Alireza’s research has been supported by the Google PhD fellowship in algorithms and optimization (2025).
We study a continuous-time, infinite-horizon dynamic bipartite matching problem. Suppliers arrive according to a Poisson process; while waiting, they may abandon the queue at a uniform rate. Customers on the other hand must be matched upon arrival. The objective is to minimize the expected long-term average cost subject to a throughput constraint on the total match rate.
Previous literature on dynamic matching focuses on "static" policies, where the matching decisions do not depend explicitly on the state of the supplier queues, achieving constant-factor approximations. By contrast, we design "adaptive" policies, which leverage queue length information, and obtain near-optimal polynomial-time algorithms for several classes of instances.
First, we develop a bi-criteria fully polynomial-time approximation scheme for dynamic matching on networks with a constant number of queues--that computes a (1-ε)-approximation of the optimal policy in time polynomial in both the input size and 1/ε. A key new technique is a hybrid LP relaxation, which combines static and state-dependent LP approximations of the queue dynamics, after a decomposition of the network. Networks with a constant number of queues are motivated by deceased organ donation schemes, where the supply types can be divided according to blood and tissue types.
The above algorithm, combined with a careful spatial decomposition gives an efficient polynomial-time approximation scheme for dynamic matching on Euclidean networks of fixed dimension. The Euclidean case is of interest in ride-hailing and spatial service platforms, where the goal is to fulfill as many trips as possible while minimizing driving distances.
Biography:
Alireza Amanihamedani is a final-year PhD candidate in Operations Research at London Business School, advised by Prof. Ali Aouad. His research interests are in online and dynamic optimization with applications to market design. Alireza’s research has been supported by the Google PhD fellowship in algorithms and optimization (2025).
Practical information
- General public
- Free
Organizer
- Prof. Maryam Kamgarpour