Reward maximization in general dynamic matching systems

DOI10.1007/S11134-018-9593-YMaRDI QIDQ2326234zbMATH OpenOpenAlexWikidataFDO

Authors Mohammad Reza Nazari, Alexander L. Stolyar

Publication date 7 October 2019

Published in Queueing Systems (Search for Journal in Brave)

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

zbMATH Keywords

stabilityoptimal controlutility maximizationdynamic matchingvirtual queuesEGPD algorithm

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Abstract: We consider a matching system with random arrivals of items of different types. The items wait in queues -- one per each item type -- until they are "matched." Each matching requires certain quantities of items of different types; after a matching is activated, the associated items leave the system. There exists a finite set of possible matchings, each producing a certain amount of "reward". This model has a broad range of important applications, including assemble-to-order systems, Internet advertising, matching web portals, etc. We propose an optimal matching scheme in the sense that it asymptotically maximizes the long-term average matching reward, while keeping the queues stable. The scheme makes matching decisions in a specially constructed virtual system, which in turn control decisions in the physical system. The key feature of the virtual system is that, unlike the physical one, it allows the queues to become negative. The matchings in the virtual system are controlled by an extended version of the greedy primal-dual (GPD) algorithm, which we prove to be asymptotically optimal -- this in turn implies the asymptotic optimality of the entire scheme. The scheme is real-time, at any time it uses simple rules based on the current state of virtual and physical queues. It is very robust in that it does not require any knowledge of the item arrival rates, and automatically adapts to changing rates. The extended GPD algorithm and its asymptotic optimality apply to a quite general queueing network framework, not limited to matching problems, and therefore is of independent interest.

Recommendations

• Optimal dynamic matching
• Compromises and rewards: stable and non-manipulable probabilistic matching
• A stochastic policy search model for matching behavior
• Incentive compatibility constraints and dynamic programming in continuous time
• Incentives in two-sided matching with random stable mechanisms
• Bayesian incentive compatibility via matchings
• Bayesian incentive compatibility via matchings
• Stabilizing policies for probabilistic matching systems
• Dynamic stochastic matching under limited time

Cites work

• Control of systems with flexible multi-server pools: a shadow routing approach
• Exact FCFS matching rates for two infinite multitype sequences
• Fcfs infinite bipartite matching of servers and customers
• Greedy primal-dual algorithm for dynamic resource allocation in complex networks
• Matching theory
• Maximizing queueing network utility subject to stability: greedy primal-dual algorithm
• On the dynamic control of matching queues
• Online matching and ad allocation
• Optimal control of a high-volume assemble-to-order system with maximum leadtime quotation and expediting
• Reversibility and further properties of FCFS infinite bipartite matching
• Stability of the bipartite matching model
• Stability of the stochastic matching model
• Stabilizing policies for probabilistic matching systems
• The Double-Ended Queue with Bulk Service and Limited Waiting Space

Cited in

(17)

• Stability regions of systems with compatibilities and ubiquitous measures on graphs
• Editorial introduction: second part of the special issue on product forms, stochastic matching, and redundancy
• On the sub-additivity of stochastic matching
• A stochastic matching model on hypergraphs
• Fluid and diffusion approximations of probabilistic matching systems
• A general stochastic matching model on multigraphs
• Multi-component matching queues in heavy traffic
• Technical note -- Greedy algorithm for multiway matching with bounded regret
• A fluid model for one-sided bipartite matching queues with match-dependent rewards
• Asymptotically Optimal Control of a Centralized Dynamic Matching Market with General Utilities
• Editorial introduction: Special issue on product forms, stochastic matching, and redundancy
• On the optimal design of a bipartite matching queueing system
• A product form for the general stochastic matching model
• Generalized Max-Weight Policies in Stochastic Matching
• Adaptive matching for expert systems with uncertain task types
• On the dynamic control of matching queues
• Matching while learning

This page was built for publication: Reward maximization in general dynamic matching systems

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