Online Matching and Ad Allocation: A Random Graphs perspective

Département Information Systems et Operations Management

Intervenant: Flore Sentenac (ENSAE)

Salle Bernard Ramanantsoa

Abstract:
The theory of online matching in graphs received a gain of interest in recent years due to its application to ad allocation on the internet. A large body of work considered the problem in general classes of graphs, introducing algorithms with worst-case guarantees.
Beyond this worst-case approach, we study online matching in models of random graphs relevant to the ad allocation problem. In particular, we will look at the so-called configuration model and geometric random graphs.
We estimate the performance of the most straightforward algorithm, GREEDY, by approximating some relevant stochastic discrete processes by their continuous counterparts, which are solutions of an explicit system of partial differential equations. Thanks to these techniques, we theoretically highlight in which instances GREEDY far outperforms its worst-case guarantee. We can also explain how some graph characteristics, such as the degree distribution, affect the performance of the algorithm.