Maria Cherifa

Maria Cherifa

Dynamic online matching with budget refills

Quand

6 juin 2025    
15h30 - 16h30

Salle du Conseil, Espace Turing
45 rue des Saints-Pères, Paris, 75006

Type d’évènement

Inspired by sequential budgeted allocation problems, we explore the online matching problem with budget refills. Specifically, we consider an online bipartite graph $G=(U,V,E)$, where the nodes in $V$ are discovered sequentially and nodes in $U$ are known beforehand. Each $u\in U$ is endowed with a budget $b_{u,t}\in \mathbb{N}$ that dynamically evolves over time. Unlike the canonical setting, where budgets are fixed, many practical applications involve periodic budget refills. This added dynamic introduces a richer and more complex problem, which we investigate here. Intuitively, adding extra budgets in $U$ seems to ease the matching task, and our results support this intuition. In fact, for the stochastic framework considered where we analyze the matching size built by Greedy algorithm on an Erdős–Rényi random graph, we show that the matching size generated by Greedy converges with high probability to a solution of an explicit system of ordinary differential equations (ODE). Moreover, under specific conditions, the competitive ratio (performance measure of the algorithm) can even tend to $1$. For the adversarial part, where the graph considered is deterministic and the algorithm used is Balance, the $b$-matching bound holds when the refills are scarce. However, when refills are regular, our results suggest a potential improvement in the algorithm performance. In both cases, Balance algorithm manages to reach the performance of the upper bound on the adversarial graphs considered.

Vous aimerez aussi...