TL;DR
This paper develops rigorous fluid and diffusion approximations for double-ended queues—systems where both "buyers" and "sellers" arrive and wait for a match—under general renewal arrival processes and exponential abandonment. The authors show that these complex systems can be modeled as asymmetric Ornstein-Uhlenbeck (O-U) processes, providing a powerful toolkit for analyzing markets, taxi services, and organ transplant systems.
What Problem Does This Paper Address?
In a standard queue, customers wait for a service. In a double-ended queue, both sides of a transaction (e.g., taxis and passengers, or buyers and sellers in a stock market) arrive according to their own schedules. If a match is available, they trade and leave immediately; otherwise, they wait in their respective queues. Crucially, these participants are often "impatient"—if they wait too long without a match, they abandon the system.
While Poisson arrival processes (where arrivals are independent and memoryless) are well-studied, real-world arrivals often follow more complex renewal processes. Analyzing these systems directly is mathematically intractable. This paper seeks to bridge that gap by providing simplified "limit" models (fluid and diffusion) that remain accurate even when the arrival patterns are not Poisson.
Methods
The authors employ a sequence of systems indexed by $n$ to establish asymptotic limits:
- Fluid Approximation: By scaling the system by $n$, they derive an Ordinary Differential Equation (ODE) that describes the "average" behavior of the queue length over time.
- Diffusion Approximation: By scaling the centered process by $\sqrt{n}$, they show the system converges to an asymmetric Ornstein-Uhlenbeck (O-U) process. This is "asymmetric" because the drift (the rate at which the system returns to equilibrium) changes depending on whether there is a surplus of buyers or sellers.
- Heavy Traffic Analysis: They examine the "heavy traffic" regime, where the arrival rates of buyers and sellers are nearly balanced. In this state, the diffusion limit simplifies to a time-homogeneous asymmetric O-U process.
- Interchange of Limits: A significant theoretical contribution is proving that the steady-state distribution of the actual queue converges to the steady-state distribution of the diffusion model.
Datasets
As a theoretical probability paper, no real-world datasets were used. Instead, the authors validated their models using extensive Monte Carlo simulations in MATLAB. They tested four types of inter-arrival distributions:
- Exponential (The baseline Poisson case).
- Uniform.
- Erlang(2) (Lower variance than exponential).
- Hyper-exponential (Higher variance than exponential).
Key Insights and Ideas
- The Asymmetry of Impatience: Because buyers and sellers might have different patience levels (reneging rates $\theta$ and $\gamma$), the resulting diffusion process has a piecewise-linear drift. This makes the O-U process asymmetric, requiring specific mathematical treatment to find limiting distributions.
- Beyond Poisson: The paper demonstrates that if you assume arrivals are Poisson when they are actually Erlang or Hyper-exponential, your performance estimates (like average queue length) will be significantly off. The diffusion model corrects for this by incorporating the variance (squared coefficient of variation) of the arrival processes.
- Stability via Reneging: The authors highlight that positive reneging rates are essential for the stability of the system. Without abandonment, a double-ended queue with unbalanced arrival rates would drift toward infinity.
Key Results
- Model Accuracy: Numerical experiments showed that the heavy traffic diffusion model (Model I) performs exceptionally well across various parameters, especially when reneging rates are small relative to arrival rates.
- Moments and Distributions: The authors derived explicit formulas for the first and second moments (mean and variance) of the limiting distributions.
- Poisson vs. Diffusion: In non-exponential cases (like Uniform or Erlang arrivals), the proposed diffusion approximations were significantly more accurate than a simple Poisson approximation, which often failed to capture the true variance of the system.
Limitations and Future Work
- Patience Distributions: The current work assumes patience times are exponentially distributed. The authors suggest that extending this to generally distributed patience times (using hazard rate scaling) is a vital next step.
- State-Dependent Arrivals: The model assumes arrival rates are independent of the queue length. In reality, a "buyers' market" might attract more sellers. Modeling arrival processes that depend on the state of the queue would add another layer of realism.
- Multi-dimensionality: The authors note that modeling a full limit order book (with multiple price levels) would require a multi-dimensional double-ended queue, which presents a much harder challenge due to non-convex state spaces.
Summary updated