2023Activity reportProject-TeamFAIRPLAY

2.1.1 Multi-agent systems

Any company developing and implementing ML algorithms is in fact one agent within a large network of users and other firms. Assuming that the data is i.i.d. and can be treated irrespectively of the environment response—as is done in the classical ML paradigm—might be a good first approximation, but should be overcome. Users, clients, suppliers, and competitors are adaptive and change their behavior depending on each other's interactions. The future of many ML companies—such as Criteo—will consist in creating platforms matching the demand (created by their users) to the offer (proposed by their clients), under the system constraints (imposed by suppliers and competitors). Each of these agents have different, conflicting interests that should be taken into account in the model, which naturally becomes a multi-agent model.

Each agent in a multi-agent system may be modeled as having their own utility function $u_i$ that can depend on the action of other agents. Then, there are two main types of objectives: individual or collective 99. If each agent is making their own decision, then they can be modeled as each optimizing their own individual utility (which may include personal benefit as well as other considerations such as altruism where appropriate) unilaterally and in a decentralized way. This is why a mechanism providing correct incentives to agents is often necessary. At the other extreme, social welfare is the collective objective defined as the cumulative sum of utilities of all agents. To optimize it, it is almost always necessary to consider a centralized optimization or learning protocol. A key question in multi-agent systems is to apprehend the “social cost” of letting agents optimize their own utility by choosing unilaterally their decision compared to the one maximizing social welfare; this is often measured by the “price of anarchy”/“price of stability” 108: the ratio of the maximum social welfare to the (worst/best) social welfare when agents optimize individually.

The natural language to model and study multi-agent systems is game theory—see below for a list of tools and techniques on which FAIRPLAY relies, game theory being the first of them. Multi-agent systems have been studied in the past; but not with a focus on learning systems where agents are either learning or providing data, which is our focus in FAIRPLAY and leads to a blend of game theory and learning techniques. We note here again that, wherever appropriate, we shall reflect (in part together with colleagues from HSS) on the soundness of the utility framework for the considered applications.

2.1.2 Societal aspects and ethics

There are several important ethical aspects that must be investigated in multi-agent systems involving users either as data providers or as individuals affected by the ML agent decision (or both).

Game theory and economics

Game theory 72 is the natural mathematical tool to model multiple interacting decision-makers (called players). A game is defined by a set of players, a set of possible actions for each player, and a payoff function for each player that can depend on the actions of all the players (that is the distinguishing feature of a game compared to an optimization problem). The most standard solution concept is the so-called Nash equilibrium, which is defined as a strategy profile (i.e., a collection of possibly randomized action for each player) such that each player is at best response (i.e., has the maximum payoff given the others' strategies). It is a “static” (one-shot) solution concept, but there also exist dynamic solution concepts for repeated games 56, 103.

Online and reinforcement learning 49

In online learning (a.k.a. multi-armed bandit 50, 110), data is gathered and treated on the fly. For instance, consider an online binary classification problem. Some unlabelled data $X_t\in R^d$ is observed, and the agent predicts its label $Y_t$; let us denote ${\widehat{Y}}_t\in \pm 1$ the prediction. The agent potentially observes the loss $1\{Y_t\ne {\widehat{Y}}_t\}$ and then receives another new unlabeled data example $X_{t+1}$. In that specific problem, the typical learning objective is to perform asymptotically as good as the best classifier $f^{*}$ in some given class $ℱ$, i.e., such that the loss ${\sum }_{t=1}^{T}1\{Y_t\ne {\widehat{Y}}_t\}$ is $o\left(T\right)$-close to ${max}_{f\in ℱ}{\sum }_{t=1}^{T}1\{Y_t\ne f\left(X_t\right)\}$; the difference between those terms is called regret. The more general model with an underlying state of the world $S_t\in 𝒮$ that evolves at each step following some Markov Decision Process (MDP, i.e., the transition matrix from $S_t$ to $S_{t+1}$ depend on the actions of the agent) and impacts the loss function is called reinforcement learning (RL). RL is an incredibly powerful learning technique, provided enough data are available since learning is usually quite slow. This is why the recent successes involve settings with heavy simulations (like games) or well-understood physical systems (like robots).

These techniques will be central to our approach as we aim to model problems where ground truth data is not available upfront and problems involving sequential decision making. There have been some successful first results in that direction. For instance, there are applications (e.g., cognitive radio) where several agents (users) aim at finding a matching with resources (the different bandwidth). They can do that by “probing” the resources, estimating their preferences and trying to find some stable matchings 47, 95.

Online algorithms 45 and theoretical computer science

Online algorithms are closely related to online learning with a major twist. In online learning, the agent has “0-look ahead”; for instance, in the online binary classification example, the loss at stage $t$ was $1\{Y_t\ne {\widehat{Y}}_t\}$ but $Y_t$ was not known in advance. The comparison class, on the other hand, was the empirical performance of a given set of classifiers. In online algorithms, the agents have “1-look ahead”; in the classification example, this means that $Y_t$ is known before choosing ${\widehat{Y}}_t$. But the overall objective is obviously no longer the minimisation of the empirical error, but the minimisation of this error plus the total number of changes (say). The comparison class is then larger, namely a subset of admissible (or the whole set) sequences of prediction ${\{\pm 1\}}^T$. The typical and relevant example of online problem relevant for Criteo that will be investigated is the matching problem: agents and resources arrive sequentially and must be, if possible, paired together as fast as possible (and as successfully as possible). Variants of these problems include the optimal stopping time question (when/how make a final decision) such as prophet inequalities and related questions 62,

Optimal transport 120

Optimal transport is a quite old problem introduced by Monge where an agent aims at moving a pile of sand to fill a hole at the smallest possible price. Formally speaking, given two probability measures $\mu$ and $\nu$ on some space $𝒳$, the optimal transport problem consist in finding (if it exists, otherwise the problem can be relaxed) a transport map $T:𝒳\to 𝒳$ that minimizes ${\int }_{𝒳}c(x,T\left(x\right))d\mu \left(x\right)$ for some cost function $c:{𝒳}^2\to R$, under the constraint that $T♯\mu =\nu$, where $T♯\mu$ is the push-forward measure of $\mu$ by $T$. Interestingly, when $\mu$ and $\nu$ are empirical measures, i.e., $\mu =\frac{1}{N}{\sum }_{n=1}{\delta }_{x_n}$ and $\nu =\frac{1}{N}{\sum }_{n=1}{\delta }_{y_n}$, a transport map is nothing more than a matching between $\left\{x_n\right\}$ and $\left\{y_n\right\}$ that minimizes the cost ${\sum }_{n}c(x_n,T\left(x_n\right))$.

Recently, optimal transport gained a lot of interest in the ML community 109 thanks to its application to images and to new techniques to compute approximate matchings in a tractable way 112. Even more unexpected applications of optimal transport have been discovered: to protect privacy 48, fairness 41, etc. Those connections are promising, but only primitive for the moment. For instance, consider the problem of matching students to schools. The unfairness level of a school can be measured as the Wasserstein distance between the distribution of the students within that school compared to the overall distribution of students. Then the matching algorithms could have a constraint of minimizing the sum of (or its maximum) unfairness levels; alternatively, we could aim at designing mechanisms giving incentives to schools to be fair in their allocation (or at least in their list preferences), typically by paying a higher fee if the unfairness level is high.

3.1.1 Fairness in auction-based systems

Online ads platforms are nowadays used to advertise not just products, but also opportunities such as jobs, houses, or financial services. This makes it crucial for such platforms to respect fairness criteria (be it only for legal reasons), as an unfair ad system would deprive a part of the population of some potentially interesting opportunities. Despite this pressing need, there is currently no technical solution in place to provably prevent discriminations. One of the main challenge is that ad impression decisions are the outcome of an auction mechanism that involves bidding decisions of multiple self-interested agents controlling only a small part of the process, while group fairness notions are defined on the outcome of a large number of impressions. We propose to investigate two mechanisms to guarantee fairness in such a complex auction-based system (note that we focus on online ad auctions but the work has broader applicability).

• Advertiser-centric (or bidder-centric) fairness

  We first focus on advertiser-centric fairness, i.e., the advertiser of a third-party needs to make sure that the reached audience is fair independently of the ad auction platform. A key difficulty is that the advertiser does not control the final decision for each ad impression, which depends on the bids of other advertisers competing in the same auction and on the platform's mechanism. Hence, it is necessary that the advertiser keeps track of the auctions won for each of the groups and dynamically adjusts its bids in order to maintain the required balance.

  A first difficulty is to model the behavior of other advertisers. We can first use a mean-field games approach similar to 81 that approximates the other bidders by an (unknown) distribution and checks equilibrium consistency; this makes sense if there are many bidders. We can also leverage refined mean-field approximations 75 to provide better approximations for smaller numbers of advertisers. Then a second difficulty is to find an optimal bidding policy that enforces the fairness constraint. We can investigate two approaches. One is based on an MDP (Markov Decision Process) that encodes the current fairness level and imposes a hard constraint. The second is based on modeling the problem as a contextual bandit problem. We note that in addition to fairness constraints, privacy constraints may complicate the optimal solution finding.

• Platform-centric (or auction-centric) fairness

  We also consider the problem from the platform's perspective, i.e., we assume that it is the platform's responsibility to enforce the fairness constraint. We also focus here on demographic parity. To make the solution practical, we do not consider modification of the auction mechanism, instead we consider a given mechanism and let the platform adapt dynamically the bids of each advertiser to achieve the fairness guarantee. This approach would be similar to the pacing multipliers used by some platforms 61, 60, but using different multipliers for the different groups (i.e., different values of the sensitive attribute).

  Following recent theoretical work on auction fairness 54, 80, 58 (which assumes that the targeted population of all ads is known in advance along with all their characteristics), we can formulate fairness as a constraint in an optimization problem for each advertiser. We study fairness in this static auction problem in which the auction mechanism is fixed (e.g., to second price). We then move to the online setting in which users (but also advertisers) are dynamic and in which decisions must be taken online, which we approach through dynamic adjustment of pacing multipliers.

3.1.2 Fairness in matching and selection problems

In this second part, we study fairness in selection and matching problems such as hiring or college admission. The selection problem corresponds to any situation in which one needs to select (i.e., assign a binary label to) data examples or individuals but with a constraint on the number of maximum number of positive labels. There are many applications of selection problems such as police checks, loan approvals, or medical screening. The matching problem can be seen as the more general variant with multiple selectors. Again, a particular focus is put here on cases involving repeated selection/matching problems and multiple decision makers.

• Fair repeated multistage selection

  In our work 69, we identified that a key source of discrimination in (static) selection problems is differential variance, i.e., the fact that one has quality estimates that have different variances for different groups. In practice, however, the selection problem is often ran repeatedly (e.g., at each hiring campaign) and with partial (and increasing) information to exploit for making decisions.

  Here, we consider the repeated multistage selection problem, where at each round a multistage selection problem is solved. A key aspect is that, at the end of a round, one learns extra information about the candidates that were selected—hence one can refine (i.e., decrease the variance of) the quality estimate for the groups in which more candidates were selected. We will first rethink fairness constraints in this type of repeated decision making problems. Then we will both study the discrimination that come out of natural (e.g., greedy) procedure as well as design (near) optimal ones for the constraints at stake. We also investigate how the constraints affect the selection utility.

• Multiple decision-makers
  Next, we investigate cases with multiple decision-makers. We propose two cases in particular. The first one is the simple two-stage selection problem but where the decision-maker doing the first-stage selection is different from the decision-maker doing the second-stage selection. This is a typical case for instance for recruiting agencies that propose sublists of candidates to different firms that wish to hire. The second case is when multiple-decision makers are trying to make a selection simultaneously—a typical example of this being the college admission problem (or faculty recruitment). We intend to model it as a game between the different colleges and to study both static solutions as well as dynamic solutions with sequential learning, again modeling it as a bandit problem and looking for regret-minimizing algorithms under fairness constraints. A number of important questions arise here: if each college makes its selection independently and strategically (but based on quality estimates with variances that differ amongst groups), how does it affect the “global fairness” metrics (meaning in aggregate across the different colleges) and the “local fairness” metrics (meaning for an individual college)? What changes if there is a central admission system (such as Parcoursup)? And in this later case, how to handle fairness on the side of colleges (i.e., treat each college fairly in some sense)?
• Fair matching with incentives in two-sided platforms

  We will study specifically the case of a platform matching demand on one side to offer on the other side, with fairness constraints on each side. This is the case for instance in online job markets (or crowdsourcing). This is similar to the previous case but, in addition, here there is an extra incentives problem: companies need to give the right incentives to job applicants to accept the jobs; while the platform doing the match needs to ensure fairness on both sides (job applicants and companies). This gives rise to a complicated interplay between learning and incentives that we will tackle again in the repeated setting.

  We finally mention that, in many of these matching problems, there is an important time component: each agent needs to be matched “as soon as possible”, yielding a trade-off between the delay to be matched and the quality of the match. There is also a problem of participation incentives; that is how the matching algorithm used affect the behavior of the participants in the matching “market” (participation or not, information revelation, etc.). In the long-term, we will incorporate these aspects in the above models.

Throughout the work in this theme, we will also consider a question transverse and present in all the models above: how can we handle multidimensional fairness, that is, where there are multiple sensitive attributes and consequently an exponential number of sub-groups defined by all intersections; this combinatorial is challenging and, for the moment, still exploratory.

3.3.1 Leveraging structure in online matching

Finding large matchings in graphs is a longstanding problem with a rich history and many practical and theoretical applications 102, 79, 39, 38. Recall that given a graph $G=\left(ℰ\right)$—where $isasetofverticesand$E$isasetofedges---,amatching$ME$isasubsetofedgessuchthateachvertexbelongstoatmostoneedge$eM$.Inthatcontext,aperfectmatching$M$isamatchingwhereeachvertex$v is associated to an edge $e\in ℳ$, and a maximum matching is a matching of maximum size (one can also consider weights on edges). Here, we study an online setting, which is more adequate in applications such as Internet advertising where ad impressions must be assigned to available ad slots 102, 51. Consider a bipartite graph, where $U\cup V$ is the union of two disjoints sets. Nodes $u\in U$ are known beforehand, whereas nodes $v\in V$ are discovered one at a time, along with the edges they belong to, and must be either immediately matched to an available (i.e., unmatched yet) vertex $u\in U$ or discarded. Online bipartite matching is relevant in two-sided markets besides ad allocations such as assigning tasks to workers 79.

A natural measure for the quality of an online matching algorithm is the “competitive ratio” (CR): the ratio between the size of the created matching to the size of the optimal one 102. The seminal work 86 introduced an optimal algorithm for the adversarial case 42, that guarantees a CR of $1-\frac{1}{e}$; but focusing on a pessimistic worst-case. In practice, some relevant knowledge (either given a priori or learned during the process) on the underlying structure of the problem can be leveraged. The focus then shifted to models taking into account some type of stochasticity in the arrival model, mostly for the i.i.d. model where arriving vertices $v\in V$ are drawn from a fixed distribution $𝒟$82, 40, 70, 85, 97, 98. The classical approach consists in optimizing the CR over the distribution $𝒟$. Even in this seemingly optimistic framework, however, it is now known that there is no hope for a CR of more than 0.823 98. Moreover, this generally leads to very large linear programs (LP).

A more recent approach restricts the distribution $𝒟$ over which the problem is optimized to classes of graphs with an underlying stochastic structure. The benefit of this approach is two-fold: it gives hope for higher competitive ratios, and for simpler algorithms. Experiments also proved that complex algorithms optimized on $𝒟$ fared no better than simple greedy heuristics on “real-life” graphs 46. A few results along these lines show that is a promising path. For instance, 51 studied the problem on graphs where each vertex has degree at least $d$ and found a competitive ratio of $1-{(1-1/d)}^d$. On d-regular graphs, 59 designed a $1-O(\sqrt{logd}/\sqrt{d})$ competitive algorithm. 100 showed that greedy algorithms were highly efficient on Erdös-Renyi random graphs, with a competitive ratio of 0.837 in the worst case. 37 showed that in a specific market with two types of matching agents, the behavior of the matching algorithm varies with the homogeneity of the market. Our goal here is to go beyond the independence assumption underlying all these works.

• Introducing correlation and inhomogeneity

  We will start by deriving and studying optimal online matching strategies on widely studied classes of graphs that present simple inhomongeneity or correlation structures (which are often present in applications). The stochastic block model 34 is often used to generate graphs with an underlying community structure. It presents a simple correlation structure: two vertices in the same community are more likely to have a common neighbors than two vertices in different communities. Another focus point will be a generalized version of the Erdös-Renyi model, where the inplace vertices $u\in 𝒰$ are divided into sets $s_i$, where $u\in s_i$ generates an edge with probability $p_i=\frac{c_i}{n}$. These two settings should give us a better understanding of how heterogeneity and correlation affect the matching performance.

  Deriving the competitive ratio implies to study the asymptotic size of maximum matchings in random graphs. Two methods are usually used. The first and constructive one is the study of the Karp-Sipser algorithm on the graph 43. The second one involves the rich theory of graph weak local convergence 44. A straightforward application of the methods, however, requires the graph to have independence properties; adapting them to graphs with a correlation structure will require new ideas.

• Configuration models and random geometric graphs
  A configuration model is described as follows (in the bi-partite case). Each vertex $u\in 𝒰$ has a number of half-edges drawn for the same distribution ${\pi }_{𝒰}$ and each vertex $v\in hasanumberofhalf-edgesdrawnfrom$V$(withtheassumptionthattheexpectedtotalnumbersofhalfedgesfrom$U$and$ are the same). Then a vertex $v\in thatarrivesinthesequentialfashionhasitshalf-edges``complete{d}^{\text{'}\text{'}}bya\left(stillfree\right)half-edgeof$U$.Thisisastandardwayofcreatingrandomgraphswith\left(almost\right)fixeddistributionofdegrees.Herethequestionwouldsimplybethecompetitiveratioofsomegreedyalgorithm,whetherthedistributions$U$and$$areknownbeforehandorlearnedonthefly.Aninterestingvariantofthisproblemwouldbetoassumetheexistenceofa\left(hiddenornot\right)geometricgraph.Each$u U$isdrawni.i.din$Rd$\left(sayaGaussiancenteredat0\right)andsimilarlyfor$v . Then there is an edge between $u$ and $v$ with a probability depending on the distance between them. Here again, interesting variants can be explored depending on whether the distribution is known or not, and whether the locations of $u$ and/or $v$ are observed or not.
• Learning while matching
  In practical applications, the full stochastic structure of the graphs may not be known beforehand. This begs the question: what will happen to the performance of the algorithms if the graph parameters are learned while matching? In the generalized Erdös-Renyi graph, this will correspond to learning the probability of generating edges. For the stochastic block model, the matching algorithm will have to perform online community detection.

3.3.2 Exploiting side-information in sequential learning

We end with an open direction that may be relevant to many of the problems considered above: how to use side-information to speed-up learning. In many sequential learning problems where one receives feedback for each action taken, it is actually possible to deduce, for free, extra information from the known structure of the problem. However, how to incorporate that information in the learning process is often unclear. We describe it through two examples.

• One-sided feedback in auctions
  In online ad auctions, the advertisers' strategy is to bid in a compact set of possible bids. After placing a bid, the advertiser learns whether they won the auction or not; but even if they do not observe the bids of other advertisers, they can deduce for free some extra information: if they win they learn that they would have won with any higher bid and if they loose they learn that they would have lost with any lower bid 121, 55. We will investigate how to incorporate this extra information in RL procedures devised in Theme 1. One option is by leveraging the Kaplan-Meier estimator.
• Side-information in dynamic resource allocation problems and matching
  Generalizing the idea above, one can observe side-information in many other problems 36. Typically, in resource allocation problems (e.g., how to allocate a budget of ad impressions), one can leverage a monotony property: one would not have gained more by allocating less. Similarly, in matching with unknown weights, it is often possible upon doing a particular match to learn the weight of other potential pairs.

Auctions 90

There are many different types of auctions that an agent can use to sell one or several items in her possession to $n$ potential buyers. This is the typical way in which spots to place ads are sold to potential advertisers. In case of a single item, the seller ask buyers to bid $b_i\in [0,1]$ on the item and the winner of the item is designating via an “allocation rule” that maps bids $b\in {[0,1]}^n$ to a winner in $\{0,...,n\}$ (0 refers to the no winner case). Then the payment rule $p:{[0,1]}^n\to {[0,1]}^n$ indicates the amount of money that each bidder must pay to the seller. Auctions are specific cases of a broader family of “mechanisms”. Knowing the allocation and payment rules, bidders have incentives to bid strategically. Different auctions (or rules) end up with different revenue to the seller, who can choose the optimal rules. This is rather standard in economics, but these interactions become way more intricate when repeated over time (as in the online ad market 106), when several items are sold at the same time (for instance in bundles), when the buyers have partial information about the actual value of the item 121 and/or reciprocally when the seller does not know the value distributions of the buyer. In that case, she might be tempted to try to learn them from the previous bids in order to design the optimal mechanism. Knowing this, the bidders have incentives to long term strategic behaviors, ending up in a quite complicated game between learning algorithms 107. This setting of interacting algorithms is actually of interest by itself, irrespectively of ad auctions. It is noteworthy also that traditional auction mechanisms do not guarantee any fairness notion and that the literature on fixing that (for applications where it matters) is only nascent 54, 105, 58, 80.

Matching 89, 104

A matching is nothing more than a bi-partite graph between some agents (patients, doctors, students) and some resources (respectively, organs, hospital, schools). The objective is to figure out what is the “optimal” matching for a given criterion. Interestingly, there are two different—and mostly unrelated yet—concepts of “good matching”. The first one is called “stable” in the sense that each agent expresses preferences over resources (and vice-versa) and be such that no couple (agent-resource) that are un-paired would prefer to be paired together than with their current paired resource/agent. In the other concept of matching, agents and resources are described by some features (say vectors in $R^d$, denoted by $a_n$ for agents and $r_m$ for resources) and pairing $a_n$ to $r_m$ incurs a cost of $c(a_n,r_m)$, for some a given function $c:{\left(R^d\right)}^2\to [0,1]$. The objective is then to minimize the total cost of the matching ${\sum }_{n}c(a_n,r_{\sigma \left(n\right)})$, where $\sigma \left(n\right)$ is the resource allocated to agent $n$.

Matching is used is many different applications such as university admission (e.g., in Parcoursup). Notice that strategic interactions arise in matching if agents or resources can disclose their preferences/features to each other. Learning is also present as soon as not everything is known, e.g., the preferences or costs. Many applications of matching (again, such as college admission) are typical examples where fairness and privacy are of utmost importance. Finally, matching is also at the basis of several Internet applications and Criteo products, for instance to solve the problem of matching a given ad budget to fixed ad slots.

Ethical notions in those use-cases

In both problems, individual users are involved and there is a clear need to consider fairness and privacy. However, the precise motivation and instantiation of these notions depends on the specific use-case. In fact, it is often part of the research question to decide which are the most relevant fairness and privacy notions, as mentioned in Section 2.1. We will throughout the team's life put an important focus on this question, as well as on the question of the impact of the chosen notion on performance.

4.2.1 Online advertisement

Online advertising offers an application area for all of the research themes of FAIRPLAY; which we investigate primarily with Criteo.

First, online advertising is a typical application of online auctions and we consider applications of the work on auctions to Criteo use-cases, in particular the work on advertiser-centric fairness where the advertiser is Criteo. From a practical point of view, privacy will have to be enforced in such applications. For instance, when information is provided to advertisers to define audiences or to visualize the performance of their campaigns (insights) there is a possibility of leaking sensitive information on users. In particular, excellent proxies on protected attributes should probably not be leaked to advertisers, or transformed before (e.g., with the differential privacy techniques). This is therefore also an application of the fairness-vs-privacy research thread.

Note that, even before considering those questions, the first very important theoretical question is to determine what is the more appropriate definition of fairness (as there are, as mentioned above, many different variations) in those applications. We recall that it is well-known that usual fairness metrics are not compatible 88. Moreover, in online advertising, fairness can be measured in term of bidding and recommendation or in term of what ads are actually displayed. Being fair on bidding does not lead to fairness in ads displaying 105, mainly because of the other advertising actors. While fairness in bidding and/or recommendation seem the most important because they only rely on our models, external auditors can easily get data on which ads we display.

We will also investigate applications of fair matching techniques to online advertsing and to Criteo matching products—namely retargeting (personalized ads displayed on a website) and retail media (sponsored products on a merchant website). Indeed, one of Criteo major products, retail media can be cast as an online matching problem. On a given e-commerce website (say, target), several advertisers—currently brands—are running campaigns so that their products are “sponsored” or “boosted”, i.e., they appear higher on the list of results of a given query. The budgets (from a Criteo perspective) must be cleared (daily, monthly or annually). This constraint is easy thanks to the high traffic, but the main issue is that, without control/pacing/matching in times, the budget is depleted after only a few hours on a relatively low quality traffic (i.e., users that generate few conversions hence a small ROI for the advertisers). The question is therefore whether an individual user should be matched or not to boosted/sponsored products at a given time so that the ROI of the advertisers is maximized, the campaign budget is depleted and the retailer does not suffer too much from this active corruption of its organic results. Those are three different and concurrent objectives (for respectively the advertisers, Criteo and the retailers) that must be somehow conciliated. This problem (and more generally this type of problems) offers a rich application area to the FAIRPLAY research program. Indeed, it is crucial to ensure that fairness and privacy are respected. On the other hand, users, clicks, conversion arrival are not “worst case”. They rather follow some complicated—but certainly learnable—process; which allows applying our results on exploiting structure.

4.2.2 “Physical matching”

We investigate a number of other applications of matching: assignment of daycare slots to kids, mutation of professors to different academies, assignment of kidneys to patients, assignment of job applicants to jobs. In all these applications, there are crucial constraints of fairness that complicate the matching. We leverage existing partnership with the CNAF, the French Ministry of Education and the Agence de la biomédecine in Paris for the first three applications; for the last we will consolidate a nascent partnership with Pole Emploi and LinkedIn.

6.2.1 Learning in games

In citefiegel:hal-04416177, we study how to learn $ϵ$-optimal strategies in zero-sum imperfect information games (IIG) with trajectory feedback. In this setting, players update their policies sequentially based on their observations over a fixed number of episodes, denoted by $T$. Existing procedures suffer from high variance due to the use of importance sampling over sequences of actions (Steinberger et al., 2020; McAleer et al., 2022). To reduce this variance, we consider a fixed sampling approach, where players still update their policies over time, but with observations obtained through a given fixed sampling policy. Our approach is based on an adaptive Online Mirror Descent (OMD) algorithm that applies OMD locally to each information set, using individually decreasing learning rates and a regularized loss. We show that this approach guarantees a convergence rate of $\tilde{O}\left(T^{-1/2}\right)$ with high probability and has a near-optimal dependence on the game parameters when applied with the best theoretical choices of learning rates and sampling policies. To achieve these results, we generalize the notion of OMD stabilization, allowing for time-varying regularization with convex increments.

6.2.2 Bandits, control and reinforcement learning

In 10, we consider the problem of regret minimization in non-parametric stochastic bandits. When the rewards are known to be bounded from above, there exists asymptotically optimal algorithms, with asymptotic regret depending on an infimum of Kullback-Leibler divergences (KL). These algorithms are computationally expensive and require storing all past rewards, thus simpler but non-optimal algorithms are often used instead. We introduce several methods to approximate the infimum KL which reduce drastically the computational and memory costs of existing optimal algorithms, while keeping their regret guaranties. We apply our findings to design new variants of the MED and IMED algorithms, and demonstrate their interest with extensive numerical simulations.

In 17, we introduce Dynamic Contextual Markov Decision Processes (DCMDPs), a novel reinforcement learning framework for history-dependent environments that generalizes the contextual MDP framework to handle non-Markov environments, where contexts change over time. We consider special cases of the model, with a focus on logistic DCMDPs, which break the exponential dependence on history length by leveraging aggregation functions to determine context transitions. This special structure allows us to derive an upper-confidence-bound style algorithm for which we establish regret bounds. Motivated by our theoretical results, we introduce a practical model-based algorithm for logistic DCMDPs that plans in a latent space and uses optimism over history-dependent features. We demonstrate the efficacy of our approach on a recommendation task (using MovieLens data) where user behavior dynamics evolve in response to recommendations.

In 4, we consider the diffusive limit of a typical pure-jump Markovian control problem as the intensity of the driving Poisson process tends to infinity. We show that the convergence speed is provided by the Hölder constant of the Hessian of the limit problem, and explain how correction terms can be constructed. This provides an alternative efficient method for the numerical approximation of the optimal control of a pure-jump problem in situations with very high intensity of jump. We illustrate this approach in the context of a display advertising auction problem.

6.2.3 Online (and offline) algorithms

In 15, we study online algorithms with advice querying under a budget constraint. Several problems have been extensively studied in the learning-augmented setting, where the algorithm has access to some, possibly incorrect, predictions. However, it is assumed in most works that the predictions are provided to the algorithm as input, with no constraint on their size. In this paper, we consider algorithms with access to a limited number of predictions, that they can request at any time during their execution. We study three classical problems in competitive analysis, the ski rental problem, the secretary problem, and the non-clairvoyant job scheduling. We address the question of when to query predictions and how to use them.

In 16, we also study online algorithms with predictions. A popular approach to go beyond the worst-case analysis of online algorithms is to assume the existence of predictions that can be leveraged to improve performances. Those predictions are usually given by some external sources that cannot be fully trusted. Instead, we argue that trustful predictions can be built by algorithms, while they run. We investigate this idea in the illustrative context of static scheduling with exponential job sizes. Indeed, we prove that algorithms agnostic to this structure do not perform better than in the worst case. In contrast, when the expected job sizes are known, we show that the best algorithm using this information, called Follow-The-Perfect-Prediction (FTPP), exhibits much better performances. Then, we introduce two adaptive explore-then-commit types of algorithms: they both first (partially) learn expected job sizes and then follow FTPP once their self-predictions are confident enough. On the one hand, ETCU explores in "series", by completing jobs sequentially to acquire information. On the other hand, ETCRR, inspired by the optimal worst-case algorithm Round-Robin (RR), explores efficiently in "parallel". We prove that both of them asymptotically reach the performances of FTPP, with a faster rate for ETCRR. Those findings are empirically evaluated on synthetic data.

In 9, we study scheduling of moldable tasks, in the offline setting. Moldable tasks allow schedulers to determine the number of processors assigned to each task, thus enabling efficient use of large-scale parallel processing systems. We consider the problem of scheduling independent moldable tasks on processors and propose a new perspective of the existing speedup models: as the number p of processors assigned to a task increases, the speedup is linear if $p$ is small and becomes sublinear after $p$ exceeds a threshold. Based on this, we propose an efficient approximation algorithm to minimize the makespan. As a by-product, we also propose an approximation algorithm to maximize the sum of values of tasks completed by a deadline; this scheduling objective is considered for moldable tasks for the first time while similar works have been done for other types of parallel tasks.

6.2.4 Statistical estimation

In 11, we discuss an application of Stochastic Approximation to statistical estimation of highdimensional sparse parameters. The proposed solution reduces to resolving a penalized stochastic optimization problem on each stage of a multistage algorithm; each problem being solved to a prescribed accuracy by the non-Euclidean Composite Stochastic Mirror Descent (CSMD) algorithm. Assuming that the problem objective is smooth and quadratically minorated and stochastic perturbations are sub-Gaussian, our analysis prescribes the method parameters which ensure fast convergence of the estimation error (the radius of a confidence ball of a given norm around the approximate solution). This convergence is linear during the first "preliminary" phase of the routine and is sublinear during the second "asymptotic" phase. We consider an application of the proposed approach to sparse Generalized Linear Regression problem. In this setting, we show that the proposed algorithm attains the optimal convergence of the estimation error under weak assumptions on the regressor distribution. We also present a numerical study illustrating the performance of the algorithm on high-dimensional simulation data.

In 8, we study a change-point detection problem. Given a times series $𝐘$ in ${ℝ}^n$, with a piece-wise contant mean and independent components, the twin problems of change-point detection and change-point localization respectively amount to detecting the existence of times where the mean varies and estimating the positions of those change-points. In this work, we tightly characterize optimal rates for both problems and uncover the phase transition phenomenon from a global testing problem to a local estimation problem. Introducing a suitable definition of the energy of a change-point, we first establish in the single change-point setting that the optimal detection threshold is $\sqrt{2loglog\left(n\right)}$. When the energy is just above the detection threshold, then the problem of localizing the change-point becomes purely parametric: it only depends on the difference in means and not on the position of the change-point anymore. Interestingly, for most change-point positions, including all those away from the endpoints of the time series, it is possible to detect and localize them at a much smaller energy level. In the multiple change-point setting, we establish the energy detection threshold and show similarly that the optimal localization error of a specific change-point becomes purely parametric. Along the way, tight optimal rates for Hausdorff and l 1 estimation losses of the vector of all change-points positions are also established. Two procedures achieving these optimal rates are introduced. The first one is a least-squares estimator with a new multiscale penalty that favours well spread change-points. The second one is a two-step multiscale post-processing procedure whose computational complexity can be as low as $O\left(nlog\right(n\left)\right)$. Notably, these two procedures accommodate with the presence of possibly many low-energy and therefore undetectable change-points and are still able to detect and localize high-energy change-points even with the presence of those nuisance parameters.

In 6, we study variable selection, monotone likelihood ratio and group sparsity. In the pivotal variable selection problem, we derive the exact non-asymptotic minimax selector over the class of all s-sparse vectors, which is also the Bayes selector with respect to the uniform prior. While this optimal selector is, in general, not realizable in polynomial time, we show that its tractable counterpart (the scan selector) attains the minimax expected Hamming risk to within factor 2, and is also exact minimax with respect to the probability of wrong recovery. As a consequence, we establish explicit lower bounds under the monotone likelihood ratio property and we obtain a tight characterization of the minimax risk in terms of the best separable selector risk. We apply these general results to derive necessary and sufficient conditions of exact and almost full recovery in the location model with light tail distributions and in the problem of group variable selection under Gaussian noise.

7.1.1 Visits of international scientists

7.1.2 Visits to international teams

Foundry (PEPR IA)

Participants: Patrick Loiseau.

• Title:
  Foundry: Foundation of robustness and reliability in AI
• Partner Institution(s):
  • Inria
  • CNRS
  • Université Paris Dauphine
  • Institut Mines Telecom
  • ENS de Lyon
• Date/Duration:
  2023-2027 (4 years)
• Additionnal info/keywords:
  PEPR IA projet cible, 245k euros. Fairness, matching, auctions.

FairPlay (ANR JCJC)

Participants: Patrick Loiseau.

• Title:
  FairPlay: Fair algorithms via game theory and sequential learning
• Partner Institution(s):
  • Inria
• Date/Duration:
  2021-2025 (4 years)
• Additionnal info/keywords:
  ANR JCJC project, 245k euros. Fairness, matching, auctions.

Explainable and Responsible AI (MIAI chair)

Participants: Patrick Loiseau.

• Title:
  Explainable and Responsible AI chair of the MIAI @ Grenoble Alpes institute
• Partner Institution(s):
  • Univ. Grenoble Alpes
• Date/Duration:
  2019-2023 (4 years)
• Additionnal info/keywords:
  Chair of the MIAI @ Grenoble Alpes institute co-held by Patrick Loiseau. Fairness, privacy.

BOLD (ANR)

Participants: Vianney Perchet.

• Title:
  BOLD: Beyond Online Learning for Better Decisions
• Partner Institution(s):
  • Crest, Genes
• Date/Duration:
  2019-2024 (4.5 years)
• Additionnal info/keywords:
  ANR project, 270k euros. online learning, optimization, bandits.

8.1.1 Scientific events: organisation

8.1.2 Scientific events: selection

8.1.3 Journal

8.1.4 Invited talks

• Patrick Loiseau:
  Alpine Game Theory Symposium (Grenoble), Columbia University, Ethics of Public Robots and AI (Skema)
• Vianney Perchet:
  Alpine Game Theory Symposium (Grenoble), Algorithms, Learning, and Games (Sicily), Optimization and Statistical Learning (les Houches), Mathematics of Data Science (Singapore), Seminar of the Maths Department of MIT (Boston), Games Learning and Networks (Singapore), Optimization 2023 (Seattle), Workshop on Information & Learning in Decisions & Operations (INSEAD), FILOFOCS 2023 (Paris), R. Cominetti's Feist (Chile), NeurIPS Workshop I cannot Believe It's Not Better (New Orleans), New Methods in Statistics (Marseille)
• Matthieu Lerasle
  Journées Statistiques du Sud, Journées ALEA, Colloquium Université Rouen, Séminaire Université du Luxembourg, Séminaire Geneva School of Economics and Management.
• Cristina Butucea
  University of Vienna, Séminaire de statistique IHP, Anniversary Conference M. Neumann University of Bamberg, Workshop on Tests and Bandits University of Potsdam
• Marc Abeille:
  UpperBound conference (2023), Reinforcement Learning Theory seminars
• Benjamin Heymann:
  Fundamental Challenges in Causality seminar workshop, Causality in Practice workshop, Causality Discussion Group
• Maxime Vono:
  Federated Learning One World Seminar

8.1.5 Scientific expertise

• Vianney Perchet:
  Expert for the evaluation of the LABEX MME:DII
• Cristina Butucea:
  Reviewer for tenure committee Harvard University, hiring committees France

8.2.1 Supervision

• Patrick Loiseau:
  PhD students: Rémi Castera, Mathieu Molina, Mélissa Tamine; postdocs: Felipe Garrido Lucero, Simon Finster, Denis Sokolov
• Vianney Perchet:
  PhD students: Sasila Ilandarideva, Flore Sentenac, Come Fiegel, Maria Cherifa, Mathieu Molina, Ziyad Benomar, Mike Liu, Hafedh El Ferchichi. postdocs: Felipe Garrido Lucero, Nadav Merlis, Dorian Baudry
• Matthieu Lerasle
  PhD Students: Clara Carlier, Hugo Chardon, Hafedh El Ferchichi.
• Cristina Butucea
  PhD students: Nayel Bettache, Henning Stein
• Marc Abeille:
  Lorenzo Croissant
• Clément Calauzènes:
  Morgane Goibert, Maria Cherifa
• Benjamin Heymann:
  Mélissa Tamine
• Maxime Vono:
  Mélissa Tamine

8.2.2 Juries

• Patrick Loiseau:
  PhD jury A. Bardou (reviewer), V. Do (reviewer)
• Vianney Perchet:
  PhD jury: J. Achddou (reviewer), D. Beaudry, A. Bismuth, C.-S. Gauthier (reviewer), H. Dakdouk (reviewer), S. Gaucher, F. Hu, G. Rizk, P. Muller, HDR jury: A. Simonetto (reviewer)
• Matthieu Lerasle
  PhD Jury: S. Arradi-Alaoui (reviewer), J. Cheng. HDR Jury: P. Mozharovskyi, A, Sabourin (internal reviewer).
• Cristina Butucea
  PhD Jury: E. Pilliat (Montpellier), C Deslandes (CMAP)

International journals

• 4 articleM.Marc Abeille, B.Bruno Bouchard and L.Lorenzo Croissant. Diffusive limit approximation of pure-jump optimal stochastic control problems.Journal of Optimization Theory and ApplicationsJanuary 2023HALDOIback to text
• 5 articleC.Cristina Butucea, A.Amandine Dubois and A.Adrien Saumard. Phase transitions for support recovery under local differential privacy.Mathematical Statistics and Learning61June 2023, 1-50HALDOIback to text
• 6 articleC.Cristina Butucea, E.Enno Mammen, M.Mohamed Ndaoud and A.Alexandre Tsybakov. Variable selection, monotone likelihood ratio and group sparsity.The Annals of Statistics511February 2023HALDOIback to text
• 7 articleC.Cristina Butucea, A.Angelika Rohde and L.Lukas Steinberger. Interactive versus noninteractive locally differentially private estimation: Two elbows for the quadratic functional.The Annals of Statistics512April 2023HALDOIback to text
• 8 articleN.Nicolas Verzelen, M.Magalie Fromont, M.Matthieu Lerasle and P.Patricia Reynaud-Bouret. Optimal Change-Point Detection and Localization.Annals of Statistics5142023, 1586-1610HALDOIback to text
• 9 articleX.Xiaohu Wu and P.Patrick Loiseau. Efficient approximation algorithms for scheduling moldable tasks.European Journal of Operational Research3101October 2023, 71-83HALDOIback to text

International peer-reviewed conferences

• 10 inproceedingsD.Dorian Baudry, F.Fabien Pesquerel, R.Rémy Degenne and O.-A.Odalric-Ambrym Maillard. Fast Asymptotically Optimal Algorithms for Non-Parametric Stochastic Bandits.Advances in Neural Information Processing Systems 36 (NeurIPS 2023)Thirty-seventh Conference on Neural Information Processing SystemsNew Orleans (Louisiana), United StatesDecember 2023HALback to text
• 11 inproceedingsY.Yannis Bekri, S.Sasila Ilandarideva, A. B.Anatoli B. Juditsky and V.Vianney Perchet. Stochastic Mirror Descent for Large-Scale Sparse Recovery.26th International Conference on Artificial Intelligence and Statistics (AISTATS)Valencia, SpainApril 2023HALback to text
• 12 inproceedingsE.Eleni Gkiouzepi, A.Athanasios Andreou, O.Oana Goga and P.Patrick Loiseau. Collaborative Ad Transparency: Promises and Limitations.SP 2023 - 44th IEEE Symposium on Security and PrivacySan Francisco, United StatesMay 2023HALback to text
• 13 inproceedingsJ.Johnnatan Messias, V.Vabuk Pahari, B.Balakrishnan Chandrasekaran, K. P.Krishna P Gummadi and P.Patrick Loiseau. Dissecting Bitcoin and Ethereum Transactions: On the Lack of Transaction Contention and Prioritization Transparency in Blockchains.Proceedings of Financial Cryptography and Data Security 2023FC 2023 - Financial Cryptography and Data Security 2023Bol, Brač, CroatiaMay 2023HALback to text
• 14 inproceedingsM.Mathieu Molina, N.Nicolas Gast, P.Patrick Loiseau and V.Vianney Perchet. Trading-off price for data quality to achieve fair online allocation.NeurIPS 2023 - 37th Conference on Neural Information Processing SystemsNew orleans, USA, United States2023, 1-43HALback to text
• 15 inproceedingsV.Vianney Perchet and Z.Ziyad Benomar. Advice Querying under Budget Constraint for Online Algorithms.NeurIPS 2023 - 37th Conference on Neural Information Processing SystemsNew Orleans, United StatesDecember 2023HALback to text
• 16 inproceedingsH.Hugo Richard, F.Flore Sentenac, C.Corentin Odic, M.Mathieu Molina and V.Vianney Perchet. Static Scheduling with Predictions Learned through Efficient Exploration.2023 International Conference on Machine LearningHonolulu (Hawai), United StatesMay 2022HALback to text
• 17 inproceedingsG.Guy Tennenholtz, N.Nadav Merlis, L.Lior Shani, M.Martin Mladenov and C.Craig Boutilier. Reinforcement Learning with History-Dependent Dynamic Contexts.ICMLHonolulu, United StatesMay 2023HALback to text

Conferences without proceedings

• 18 inproceedingsA.Artem Betlei, M.Mariia Vladimirova, M.Mehdi Sebbar, N.Nicolas Urien, T.Thibaud Rahier and B.Benjamin Heymann. Maximizing the Success Probability of Policy Allocations in Online Systems.AAAI2024Vancouver, CanadaarXiv2023HALDOIback to text
• 19 inproceedingsBest paperC.Côme Fiegel, P.Pierre Ménard, T.Tadashi Kozuno, R.Rémi Munos, V.Vianney Perchet and M.Michal Valko. Local and adaptive mirror descents in extensive-form games.2023 International Conference on Machine LearningNew Orleans, United StatesSeptember 2023HALback to text
• 20 inproceedingsS.Simon Finster, M. G.Michelle González Amador, E.Edwin Lock, F.Francisco Marmolejo-Cossío, E.Evi Micha and A. D.Ariel D. Procaccia. Welfare-Maximizing Pooled Testing.EC 2023 - The 24th ACM Conference on Economics and ComputationLondon, United Kingdom2023HALback to text
• 21 inproceedingsS.Simon Finster, P.Paul Goldberg and E.Edwin Lock. Substitutes markets with budget constraints: solving for competitive and optimal prices.WINE 2023 - The 19th Conference On Web And InterNet EconomicsShanghai, China2023HALback to text

Scientific book chapters

• 22 inbookA.Amandine Dubois, T.Thomas Berrett and C.Cristina Butucea. Foundations of Modern Statistics.425Foundations of Modern StatisticsSpringer Proceedings in Mathematics & StatisticsSpringer International Publishing2023, 53-119HALDOI

Edition (books, proceedings, special issue of a journal)

• 23 proceedingsD.Denis BelomestnyC.Cristina ButuceaE.Enno MammenE.Eric MoulinesM.Markus ReißV.Vladimir UlyanovFoundations of Modern Statistics.Festschrift in Honor of Vladimir Spokoiny425Springer Proceedings in Mathematics & StatisticsSpringer International Publishing; Springer International Publishing2023HALDOI

Reports & preprints

• 24 miscD.Dorian Baudry, N.Nadav Merlis, M.Mathieu Molina, H.Hugo Richard and V.Vianney Perchet. Multi-Armed Bandits with Guaranteed Revenue per Arm.January 2024HAL
• 25 miscZ.Ziyad Benomar, E.Evgenii Chzhen, N.Nicolas Schreuder and V.Vianney Perchet. Addressing bias in online selection with limited budget of comparisons.November 2023HAL
• 26 miscN.Nayel Bettache and C.Cristina Butucea. Two-sided Matrix Regression.March 2023HAL
• 27 miscC.Cristina Butucea, J.-F.Jean-François Delmas, A.Anne Dutfoy and C.Clément Hardy. Simultaneous off-the-grid learning of mixtures issued from a continuous dictionary.January 2024HAL
• 28 miscR.Rémi Castera, P.Patrick Loiseau and B.Bary Pradelski. Statistical Discrimination in Stable Matching.April 2023HAL
• 29 miscL.Lorenzo Croissant, M.Marc Abeille and B.Bruno Bouchard. Near-continuous time Reinforcement Learning for continuous state-action spaces.September 2023HAL
• 30 miscC.Côme Fiegel, P.Pierre Ménard, T.Tadashi Kozuno, R.Rémi Munos, V.Vianney Perchet and M.Michal Valko. Adapting to game trees in zero-sum imperfect information games.December 2022HAL
• 31 miscF.Felipe Garrido-Lucero, B.Benjamin Heymann, M.Maxime Vono, P.Patrick Loiseau and V.Vianney Perchet. DU-Shapley: A Shapley Value Proxy for Efficient Dataset Valuation.June 2023HAL
• 32 miscF.Flore Sentenac, N.Nathan Noiry, M.Matthieu Lerasle, L.Laurent Ménard and V.Vianney Perchet. Online Matching in Geometric Random Graphs.October 2023HAL