Insensitivity for Matching Systems
Open Access
- 2 June 2025
- journal article
- research article
- Published by Springer Nature in Queueing Systems
- Vol. 109 (2) , 1-20
Abstract
We study matching queues motivated by applications in ride-sharing platforms, where items (e.g., drivers and riders) arrive over time and are matched based on a compatibility graph. Our model generalizes classical compatibility queueing models and queue-based ride-sharing models by allowing exogenous driver arrivals, queues for both drivers and riders, and arbitrary bipartite compatibility structures. We provide sufficient conditions under which the stationary distribution exhibits insensitivity to 1) service-time (drive-time) distributions and 2) the matching policies of drivers and riders, respectively. Using tools from Kelly networks and order-independent queues, we provide simple and unified proofs of insensitivity to service-time distributions and to matching policies for a broad class of models. Our policy insensitivity result requires a finite buffer; we demonstrate through counterexamples that such insensitivity may fail when the buffer is infinite. Our results also shed light on insensitivity in related redundancy systems, offering new insights into their stationary behavior.Keywords
Funding Information
- NWO gravitation project Networks (024.002.003)
- European Union’s Horizon 2020 research and innovation program under the Marie Sklodowska-Curie grant (101034253)
- University of California Berkeley, Ronald W. Wolff Chancellor’s Chair Fund
- University of California Berkeley, Ronald W. Wolff Chancellor’s Chair Fund
This publication has 13 references indexed in Scilit:
- Approximations to Study the Impact of the Service Discipline in Systems with Redundancy2024
- The stationary distribution of the redundancy-d model with random order of serviceACM SIGMETRICS Performance Evaluation Review, 2023
- Stochastic non-bipartite matching models and order-independent loss queuesStochastic Models, 2021
- Product forms for FCFS queueing models with arbitrary server-job compatibilities: an overviewQueueing Systems, 2020
- A Queueing Loss Model with Heterogeneous Skill Based Servers Under Idle Time Ordering PoliciesJournal of Applied Probability, 2015
- A LOSS SYSTEM WITH SKILL-BASED SERVERS UNDER ASSIGN TO LONGEST IDLE SERVER POLICYProbability in the Engineering and Informational Sciences, 2012
- A product form solution to a system with multi-type jobs and multi-type serversQueueing Systems, 2012
- Order independent loss queuesQueueing Systems, 1996
- Quasi-reversible multiclass queues with order independent departure ratesQueueing Systems, 1995
- Open, Closed, and Mixed Networks of Queues with Different Classes of CustomersJournal of the ACM, 1975