publications

2025

1. In preparation

   Online matching on stochastic block model

   Maria Cherifa, Clément Calauzènes, and Perchet Vianney

   Mar 2025

2024

1. MATCHUP

   Dynamic online matching with budget refills

   Maria Cherifa, Clément Calauzènes, and Vianney Perchet

   Matchup workshop 2024 Sep 2024

   Abs Bib URL PDF Slides

   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∈U is endowed with a budget b_u,t∈\lN 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...

   @article{Cherifa,
     title = {Dynamic online matching with budget refills},
     author = {Cherifa, Maria and Calauzènes, Clément and Perchet, Vianney},
     journal = {Matchup workshop 2024},
     url = {https://hal.science/ENSAE/hal-04573598v1},
     year = {2024},
     month = sep,
   }

2. NEURIPS

   Optimizing the coalition gain in Online Auctions with Greedy Structured Bandits

   Dorian Baudry, Hugo Richard, Maria Cherifa, Clément Calauzènes, and Vianney Perchet

   NeurIPS 2024 Dec 2024

   Abs Bib URL PDF Slides

   Motivated by online display advertising, this work considers repeated second-price auctions, where agents sample their value from an unknown distribution with cumulative distribution function F. In each auction t, a decision-maker bound by limited observations selects n_t agents from a coalition of N to compete for a prize with p other agents, aiming to maximize the cumulative reward of the coalition across all auctions. The problem is framed as an N-armed structured bandit, each number of player sent being an arm n, with expected reward r(n) fully characterized by F and p+n. We present two algorithms, Local-Greedy (\LG) and Greedy-Grid (\GG), both achieving \emphconstant problem-dependent regret. This relies on three key ingredients: \bf 1. an estimator of r(n) from feedback collected from any arm k, \bf 2. concentration bounds of these estimates for k within an estimation neighborhood of n and \bf 3. the unimodality property of r under standard assumptions on F. Additionally, \GG exhibits problem-independent guarantees on top of best problem-dependent guarantees. However, by avoiding to rely on confidence intervals, \LG practically outperforms \GG, as well as standard unimodal bandit algorithms such as \OSUB or multi-armed bandit algorithms.

   @article{baudry:hal-04896482,
     title = {Optimizing the coalition gain in Online Auctions with Greedy Structured Bandits},
     author = {Baudry, Dorian and Richard, Hugo and Cherifa, Maria and Calauz{\`e}nes, Cl{\'e}ment and Perchet, Vianney},
     url = {https://ephe.hal.science/FOUNDRY/hal-04896482v1},
     journal = {{NeurIPS 2024}},
     year = {2024},
     month = dec,
     hal_id = {hal-04896482},
   }

2022

1. PREPRINT

   Flow Redirection for Epidemic Reaction-Diffusion Control

   Pierre-yves Massé, Quentin Laborde, Maria Cherifa, Jules Olayé, and Laurent Oudre

   Arkiv Feb 2022

   Abs Bib URL PDF

   We show we can control an epidemic reaction-diffusion on a directed, and heterogeneous, network by redirecting the flows, thanks to the optimisation of well-designed loss functions, in particular the basic reproduction number of the model. We provide a final size relation linking the basic reproduction number to the epidemic final sizes, for diffusions around a reference diffusion with basic reproduction number less than 1. Experimentally, we show control is possible for different topologies, network heterogeneity levels, and speeds of diffusion. Our experimental results highlight the relevance of the basic reproduction number loss, compared to more straightforward losses.

   @article{Cherifa4,
     title = {Flow Redirection for Epidemic Reaction-Diffusion Control},
     author = {Massé, Pierre-yves and Laborde, Quentin and Cherifa, Maria and Olayé, Jules and Oudre, Laurent},
     journal = {Arkiv},
     url = {https://cnrs.hal.science/hal-03554713/},
     year = {2022},
     month = feb,
   }