Stability of the stochastic matching model
From MaRDI portal
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Queues and service in operations research (90B22)
Abstract: We introduce and study a new model that we call the {em matching model}. Items arrive one by one in a buffer and depart from it as soon as possible but by pairs. The items of a departing pair are said to be {em matched}. There is a finite set of classes for the items, and the allowed matchings depend on the classes, according to a {em matching graph} on . Upon arrival, an item may find several possible matches in the buffer. This indeterminacy is resolved by a {em matching policy}. When the sequence of classes of the arriving items is i.i.d., the sequence of buffer-contents is a Markov chain, whose stability is investigated. In particular, we prove that the model may be stable if and only if the matching graph is non-bipartite.
Recommendations
Cited in
(33)- On the instability of matching queues
- Equivalences between two matching models: stability
- The stability of conventions: random and lattice matching networks compared
- Introduction to shape stability for a storage model
- Matching queues with reneging: a product form solution
- Directed FCFS infinite bipartite matching
- Reward maximization in general dynamic matching systems
- Stabilizing policies for probabilistic matching systems
- Stability in dynamic matching markets
- Fluid and diffusion approximations of probabilistic matching systems
- A stable matching model with an entrance criterion applied to the assignment of students to dormitories at the Technion
- Stability of the bipartite matching model
- Exact FCFS matching rates for two infinite multitype sequences
- E-stability in the stochastic Ramsey model
- Stability in referral systems
- A product form for the general stochastic matching model
- A general stochastic matching model on multigraphs
- A stochastic matching model on hypergraphs
- Stochastic non-bipartite matching models and order-independent loss queues
- On the optimal design of a bipartite matching queueing system
- Fluid models of parallel service systems under FCFS
- Stability regions of systems with compatibilities and ubiquitous measures on graphs
- Editorial introduction: Special issue on product forms, stochastic matching, and redundancy
- Heavy traffic analysis of multi-class bipartite queueing systems under FCFS
- Multi-component matching queues in heavy traffic
- Editorial introduction: second part of the special issue on product forms, stochastic matching, and redundancy
- Performance paradox of dynamic matching models under greedy policies
- On the sub-additivity of stochastic matching
- Toward organ shortage resilient allocation policies using real-time queueing models for liver transplantation
- Online matching for the multiclass stochastic block model
- Performance paradox of dynamic bipartite matching models
- Perfect sampling of stochastic matching models with reneging
- Admission control of quasi-reversible queueing systems: optimization and reinforcement learning
This page was built for publication: Stability of the stochastic matching model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2956511)
