BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:Online stochastic matching under the first-come-first-matched poli
cy
DTSTART:20231114T085000Z
DTEND:20231114T095000Z
DTSTAMP:20240228T235000Z
UID:indico-event-10898@indico.math.cnrs.fr
DESCRIPTION:Speakers: Celine Comte (LAAS)\n\nWe consider the following onl
ine stochastic matching problem. Items from different classes arrive accor
ding to independent Poisson processes. Matching compatibilities between it
ems are described by a simple graph over the classes\, so that two items c
an be matched if and only if their classes are neighbors in the graph. Thi
s graph is assumed to be connected and non-bipartite. Each incoming item i
s matched immediately with the oldest compatible unmatched item\, if any.
The evolution of the sequence of unmatched item classes\, ordered by arriv
al times\, defines an irreducible Markov chain. Previous work has derived
(i) a necessary and sufficient condition for this Markov chain to be posit
ive recurrent\, which we assume is satisfied\, and (ii) a closed-form expr
ession for its stationary distribution. In this presentation\, we first pr
ovide more direct method to derive the stationary distribution\, based on
quasi-reversibility\, a notion introduced by Kelly (1979). We then derive
new closed-form expressions for several performance metrics\, such as the
waiting probability and the mean waiting time\, which can be efficiently i
mplemented using dynamic programming. Both these formulas and the numerica
l results that they allow us to derive are used to better understand the i
mpact of parameters on performance. In particular\, we characterize perfor
mance in a so-called heavy-traffic regime\, in which the number of items o
f a subset of the classes goes to infinity while items of other classes be
come scarce.This presentation is based on the paper “Stochastic non-bipa
rtite matching models and order-independent loss queues”\, published in
Stochastic Models (Taylor & Francis) and available at https://doi.org/10.
1080/15326349.2021.1962352.\n\nhttps://indico.math.cnrs.fr/event/10898/
LOCATION:Amphi Schwartz (IMT)
URL:https://indico.math.cnrs.fr/event/10898/
END:VEVENT
END:VCALENDAR