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:20260505T103400Z
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