Generalized Max-Weight Policies in Stochastic Matching

DOI10.1287/STSY.2022.0098MaRDI QIDQ6199151OpenAlexWikidataFDO

Authors Matthieu Jonckheere, Pascal Moyal, Nahuel Soprano-Loto

Publication date 23 February 2024

Published in Stochastic Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.04535

zbMATH Keywords

stabilityLyapunov functionmax-weightstochastic matching

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Queueing theory (aspects of probability theory) (60K25)

Abstract: We consider a matching system where items arrive one by one at each node of a compatibility network according to Poisson processes and depart from it as soon as they are matched to a compatible item. The matching policy considered is a generalized max-weight policy where decisions can be noisy. Additionally, some of the nodes may have impatience, i.e. leave the system before being matched. Using specific properties of the max-weight policy, we construct several Lyapunov functions, including a simple quadratic one. This allows us to establish stability results, to construct bounds for the stationary mean and variances of the total amount of customers in the system, and to prove exponential convergence speed towards the stationary measure. We finally illustrate some of these results using simulations on toy examples.

Recommendations

• Stability and Asymptotic Optimality of Generalized MaxWeight Policies
• A product form for the general stochastic matching model
• On the sub-additivity of stochastic matching
• Reward maximization in general dynamic matching systems
• A general stochastic matching model on multigraphs

Cited in

(6)

• Editorial introduction: second part of the special issue on product forms, stochastic matching, and redundancy
• On the sub-additivity of stochastic matching
• A fluid approximation for a matching model with general reneging distributions
• Multi-component matching queues in heavy traffic
• On the Stability Region of Maximum Weighted Matching Server Allocation Policy
• Editorial introduction: Special issue on product forms, stochastic matching, and redundancy

This page was built for publication: Generalized Max-Weight Policies in Stochastic Matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6199151)