Trading-off price for data quality to achieve fair online allocation
Authors: Mathieu Molina
Nicolas Gast
Patrick Loiseau
Vianney Perchet
Venue: NeurIPS 2023 poster (2023)
Keywords: Fairness
Online allocation
Bandits algorithms

Abstract: We consider the problem of online allocation subject to a long-term fairness penalty. Contrary to existing works, however, we do not assume that the decision-maker observes the protected attributes---which is often unrealistic in practice. Instead they can purchase data that help estimate them from sources of different quality; and hence reduce the fairness penalty at some cost. We model this problem as a multi-armed bandit problem where each arm corresponds to the choice of a data source, coupled with the fair online allocation problem. We propose an algorithm that jointly solves both problems and show that it has a regret bounded by $\mathcal{O}(\sqrt{T})$. A key difficulty is that the rewards received by selecting a source are correlated by the fairness penalty, which leads to a need for randomization (despite a stochastic setting). Our algorithm takes into account contextual information available before the source selection, and can adapt to many different fairness notions.

Trading-off price for data quality to achieve fair online allocation
Mathieu Molina
Nicolas Gast
Inria, FairPlay Team, Palaiseau, France mathieu.molina@hna frria.ff
Univ. Grenoble Alpes. Inria, CNRS Grenoble INP, LIG, 38000 Grenoble, France nicolas.gast@innfs @nniafr
Patrick Loiseau
Vianney Perchet
Inria, FairPlay Team, Palaiseau, France patrick.loiseau @ inria.fr
CREST, ENSAE, Palaiseau, France Criteo AI Lab, Paris, France vianney.perchet@ noreeeeoooommllm.rrg.......
Abstract
We consider the problem online allocation subject to long-term fairness penalty. Contrary to existing works, however, we do not assume that the decision-maker observes the protected attributes-which they can purchase data that help estimate them from sources of different quality; and hence reduce the fairness penalty at some cost. We model this problem as a multi- aenti--rmeddd bandit problem where each arm corresponds to the choice of data source, coupled with the online allocation problem. We propose an algorithm that jointly solves both problems and show that it has a regret bounded by O (VVT). A key difficulty is that the rewards received by selecting a source are correlated by the fairness penalty, which leads to a need for randomization (despite a stochastic setting). Our algorithm takes into account contextual information available before the source selection, and can adapt to many different fairness notions. We also show that in some instances, the estimates used can be learned the fly.
often unrealistic in practice. Instead
Introduction
We consider the problem of online allocation with long-term fairness penalty: decision maker interacts sequentially with different types of users with the global objective of maximizing some cumulative rewards (e.g., number of views, clicks, or conversions): but she also has a second objective of taking globally "fair" decisions with respect to some protected/sensitive attributes such as gender or ethnicity (the exact concepts of fairness will discussed later). This problem is important because models a large number of practical online allocation situations where the additional fairness constraint might be crucial. For instance, in online advertising (where the decision maker chooses to which users ad is shown). some ads are actually positive opportunities such as job offers, and targeted advertising has been shown to be prone to discrimination Lambrecht & Tucker (2019); |; (Speicher et al.) (2018); Ali et al. (2019). Those questions also arise in many different fields such as workforce hiring (Dickerson et al. 2018), recommendation systems (Burke) (017). or placement in refugee settlements
(Ahani et al. 2021).
There has been flourishing trend research addressing fairness constraints in machine learning see e.g., (Chouldechoval 2017; Hardt et al. 2016 Kleinberg & Raghavan, 2018 8, Barocas et al. 2019 Emelianov et al. 22200) Molina Loiseau 2022) and in sequential fecision-making problems see e.g., (Joseph et al. [0166] Jabbari et al. 2011 ( Heidari & Krause [00 8) as algorithmic decisions have real consequences on the lives of individuals, with unfortunate observed discrimination (Buolamwini
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

& Gebru, 2018 Larson et al. 2016 Dastin 2018). In online allocation problems, general long-term constraints have been studied for instance by Agrawal & Devanur (2015) who maximize the utility of the allocation while ensuring the feasibility of the average allocation, or by Balseiro et al. (2020) who show how to handle hard budget constraints for online allocation problems. More directly related to fairness, Nasr & Tschantt (2020) formulate the problem of fair repeated auctions with a hard constraint on the difference between the number of ads shown to each group. Finally, in recent works, Balseiro et al. (202 Celli et al. (2022) consider the online allocation problem where non-separable penalty related to fairness is suffered by the decision maker at the end of the decision-making process instead of hard constraint- -ttrre works are the closest to ours.
All the aforementioned papers, unfortunately, assume that the protected attributes (which define the fairness constraints) are observed before taking decisions. In practice, it is often not the case-for for instance to respect users' privacy [Guarddian] 2023) and this makes it challenging to satisfy fairness constraints (Lipton et al. 2018). In online advertising for example, the decision-maker typically has access to some public "contexts" on each user, from which she could try to infer the value of the attribute; but it was shown that the amount of noise can be prohibitive and therefore ensuring that campaign reaches a non-diseriminatory audience is non-trivial Gelauff et al. (2020).
Our contribution. In this paper, we consider the online allocation problem under long-term fairness penalty, in the practical case where the protected attributes are not observed. Instead, we consider the case where the decision-maker maker can pay to acquire more precise information on the attributes (beyond the public context), either by directly compensating the user (the more precise the information on the attribute, the higher the price) or by buying additional data to some third parties data- Using this extra information, she should be able to estimate more precisely, and thus sequentially reduces, the unfairness of her decisions while keeping high cumulative net reward. The main question we aim at answering is how should the decision maker decide when, and from which source (or at what level of precision), to buy additional data in order to make fair optimal allocations?
Compared to the closest existing works (Balseiro et al., 2021 Celli et al. 2022) which study online allocation with long term fairness penalty, the main novelty in the setting we examine is two-fold: we allow for uncertainty on the attributes of each individual, and more importantly we consider jointly the fair online allocation problem with a source selection problem. Consequently, we present the efficient A Algorithm]] | that tackles both of these challenges concurrently. This algorithm combines a dual gradient descent for the fair allocation aspect and bandit algorithm for the source selection part. The final performance of an algorithm is its net cumulative utility (rewards minus costs of buying extra information) penalized by its long-term unfairness; that is quantified by the "regret": the difference between this performance and the one of some benchmarking "optimal" algorithm. We show that Algorithm| I has sub-linear regret bound under some stochastic assumptions. Notably, the performance achieved by Algorithm I Jsing randomized source selection is strictly better than when using a single fixed source, because of the interaction through the faimesss penalty- a key difference with standard bandit settings. On a more technical level we show how one can model the randomness and estimates for the protected attributes, how to bound the fair dual parameters which is crucial in order to use adversarial bandit techniques, and how to combine the analysis of the primal and dual steps of the algorithm.
There are many different definitions of group fairness that can be studied (e.g., demographic parity, equal opportunity, etc.). Instead of focusing on specific one, we consider a generic formulation that can be instantiated to handle most of those different concepts (see Section and Appendix AA. We also discuss in Section how to adapt our algorithm to different faimess penalties. This gives a higher level of generality to our results compared to existing approaches that can handle fewer fairness criteria (e.g.. Celli et al. (2022).
For the sake of clarity, we expose our key results in a simple setting. In particular, we assume binary decisions and a linear utility, and we assume that the expected utility conditional on the context is known. All these assumptions can be relaxed. In particular, we can learn the utilities (see Section 4.2) .. We can handle also more general decision variables and utility forms. This allows in particular to tackle problems of matching and auctions (albeit with some restrictions), we discuss that in Appendices B and C
'This setting includes as special cases the extremes where no additional information can be bought and where the full information is available.
2

---

Related work. The problem of online fair allocation is closely related to online optimization problems with constraints, which is studied in few papers. For instance, bandit problems with knapsack constraints where the algorithm stops once the budget has been depleted have been studied by /BBaanidiyuru et al. (2018); Agrawal & Devanur (2016). [Li & (2 ): Li et al. (2022) consider online linear programs, with stochastic and adversarial inputs. [iu et al. (2021) ) deal with linear bandits and general anytime constraints, which can be instantiated as fairness constraints. More recently Castiglioni et al. (2022alb) b) propose online algorithms for long-term constraints in the stochastic and adversarial cases with bandit or full information feedback. Some papers take into account soft long-temn constraints (Agrawal & Devanur 2015 Jenatton et al., 2016), and more recently in (Balseiro et al. 2021 Celli et al. 2022) where the long-term constraint can be instantiated as fairness penalty- also adopt a soft constraint. We depart from this literature by considering the case where the protected attributes (based on which fairness is defined) is not observed. We consider the case where the decision-maker
buy additional information estimate it (which adds considerable technical complexity), but even in the case where no additional information can be bought our work extends that of (Balseiro et al. 2021 Celli al., 2022).
As mentioned above, the fairness literature usually assumes perfect observation of the protected attributes yet noisy realizations of protected attributes or limited access to them to measure and compute fair machine learning models has also been considered (Lamy et al. 2019 Celis et al. 2021; Zhao et al. 22022) In some cases, the noise may come from privacy requirements, and the interaction between those two notions has been studied (Jagielski et al. 2019 Chang & Shokri 2021]. see (Fioretto et al. (022) for a survey. There are also works on data acquisition, which is similar to purchasing information from different sources of information; e.g.. Chen et al. (2018); Chen & Zheng (2019) study mechanisms acquire data
estimate some of the population's 's statistics. They use a mechanism design approach where the cost of data is unknown and do not consider fairness (or protected attributes). However, none of these approaches can handle sequential decision problems with fairness constraints or penalties (and choosing information sources).
2 Preliminaries
2.1 Model and assumptions
We present here a simpler model, and later-on discuss possible extensions. Consider a decision maker making sequential allocation decisions for known number of T users (or simply stages) in order to maximize her cumulative rewards. The user has some protected attributes ag E A C Rdd, that is not observed before taking decision 2,. On the other hand, the decision-maker first observes some public context 2, E Z, where Z is the finite set of all possible public contexts and she has the possibility to buy additional information. There are K different sources for additional information and choosing the source h; E [K] has a cost of pk,, but it provides a new piece of information, which together with the public information is summarized in the random variable Ctk (2z, data from kt). Based on this, the decision 2, E {0.1) can be made; this corresponds to include, or not, user in the cohort (for instance, to display ad or not). Including user generates some reward/utility ue. which might be unknown to the decision maker (as it may depend on the private attribute), but can be estimated using the different contexts.
To fix ideas, we show how this model applies to two examples: Imagine an advertiser aiming to display ads to an user, able to see some bare-bone information through cookies, such as which website was previously visited (z:). Based on this information, they can decide whether or not to buy additional information (Ces) from different data brokers that collect user activity. For example, if they observe that the user has browsed clothing stores, they might opt to acquire data containing purchase details from this website. This enables them to estimate the user's gender (a,) based on the type of clothing bought. Now consider the problem of fairly relocating refugees to different cities. When the organization in charge of resettlement receives resettlement case (z,). it can either decide to directly assign the refugee to a specific city, or to conduct an additional costly investigation (which might involve third party watch-dog) to get more information (Ctk) on some protected attributes of interest such as wealth or age (a,), which might have been intentionally misreported.
We assume that the global objective is to maximize the sum of three terms: the cumulative rewards of all selected users, minus the costs of the additional information bought, minus some unfairness penalty, represented by some function R(.). Denoting by ks (ki,-.. ,kT) and æ (ø1, 2T)
3

---

the sources and allocations selected during the T rounds, the total utility of the decision maker is then
U(ki x))
Ut PP. Pk. - TR Σ a.a)).
(I)
t=1
The penalty function R(.)) is convex penalty function that measures the fairness cost of the decision- making process, due to the unbalancedness of the selected users at the end of the 7 rounds. can be used to represent statistical parity (Kamishima et al.] (0TT))
measure of how far the allocation is
from this fairness notion. This fairness penalty R(.) is also used in Balseiro et al. (2021) Celli et al.
(2022). In fact, the objective ( is equal the one used in these papers minus the cost of additional information bought, >. Pk.
Knowns, unknowns and stochasticity We assume that users are independent and identically distributed (i.i.d.,, in the sense that the whole vectors (zz, Ut at Cet ....ck) are i.i.d., drawn from some underlying unknown probability distribution. While this may be a strong assumption, some applications such as online advertising correspond large T but to a short real dime-frame, hence incurring very little variation in the underlying distribution. The prices pk and the penalty function R()) are known beforchand. As mentioned several times, the only feedback received is Ctt. after selecting source k. and this should be enough to estimate u, and Qç- We therefore assume that the conditional expectations E[u, | Ctk,] and Elaa Ctk,] are known. The rationale behind this assumption is that these conditional expectations have been learned from past data.
Penalty examples and generalizations A typical example for a is the case of one-hot encoding: there are d protected categories of users and a, indicates the category of user t. For simplicity, assume that d 2, then the quantity E, aetty is the number of users of type i E {1,2) that have been selected. The choice of TR (TT//T) = E. ae - E, Gr2Tel amounts to penalizing the decision maker proportional to the absolute difference of users both groups. This generic setting can also model other notions of fairness, such as Equality of Opportunity (Hardt et al., 2016), by choosing other values for a and R(.), see examples and discussion in Appendix [
Similarly, the choice of Vy E 1) can be immediately generalized to any finite decision set or even continuous compact one (say, the reward at stage would then be u, 24 for some vector u,), which makes it possible to handle problems such as bipartite matching. Instead of deriving linear utility from selecting an user, general bounded upper comiicontiuuou (u.s.c.) utility functions can also be treated, and can be used to instantiate auctions mechanism (with some limitations detailed in Appendix C). We also explain how to relax the assumption that Elu, | Ctk,] is known in Section 4.2 by deriving an algorithm that actually learns it in an online fashion, following linear contextual bandit techniques (Abbasi-yadkor et al. 201T).
We show in Section 3.5 that the assumption that Z is finite can be relaxed if all conditional distributions depend smoothly on z, following techniques from Perchet & Rigollet (013))
Mathematical assumptions We shall assume |ue] S a. for all I, and that ||u||2 S for all a E A. We make, for now, no structural assumption on the variables cas. We mention here that the decision maker has to choose a single source at each stage, but this is obviously without loss of generality (by adding void or combination of sources).
We define A Conv(A (A U {0]), where Conv is the closed convex hull of set. Since A is compact, the set A is also convex and compact. The penalty function R : A + R is a proper closed convex function that is L--Lischiizz continuous for the Euclidean norm || 1|2- While the convexity assumption is pretty usual, the Lipschitzness assumption is rather mild as A is convex and compact. Nevertheless, interesting non-Lipschitz functions, such as the Kullback-Leibler divergence, can be modified to respect these assumptions (see Celli et al. (2022)). )
2.2 Benchmark and regret
A usual measure of performance for online algorithms is the regret that compares the utility obtained by an online allocation to the one obtained by an oracle that knows all parameters of the problem, yet not the realized sequence of private attributes. We denote the performance of this oracle by OPT:
OPT = max E
max E.. (K, x)) Cikes... CTky (0.1)
(2)
he(KK=gr
4

---

where the conditional expectation indicates that the oracle first chooses contextual policy he for all users that specifies which source kę hh{(2) to select as function of the variables 2,. It then observes all contexts Ctk, and makes for all the decisions based on that. different users with the same public information 2ς- As such, it differs from classical benchmarks in the contextual bandit literature that compare the performance of an algorithm to the best static choice of per context and whose performance would be
Denoting ALG the expected penalized utility of online algorithm, its expected regret is:
Reg = OPT -B|U (k, x)] = OPT ALG.
We remark that the benchmark of Equation 2 allows choosing different sources information for
static- OPTicc-PT:o = max max Bj ([((k))))ca x)(ck........................... CTkr] hE|K]* =<(0,1)
(4)
where the [K] policy that maps the public information to a source selection the same for all users.
The benchmark (4) is the typical benchmark in contextual multi-armed bandits, as the global impact of decisions at different epochs and for different contexts are independent. However, this is no longer the case with the unfairness penalty R(-) that requires coupling all decisions:
Proposition 2.1. There exist an instance of the problem and constant b 0 such that for all T:
static-OPT + bT OPT.
This result shows that an algorithm that only tries to identify the best source will have a linear regret compared to OPT. This indicates that the problem of source selection and fairness are strongly coupled, even without public information available, and cannot be solved through some sort of two-phase algorithm where each problem is solved separately. The proof of this result is presented in Appendix(F.1] In this paper, our primary emphasis lies in the examination of the performance disparity between an online algorithm and the offline optimum. Nevertheless, experiments in Appendix F.3 that investigate how variations in the prices py and the penalty It impact the solution of the offline optimum.
provide supplementary
3 Algorithm and Regret Bounds
In this part, we present our online allocation algorithm and its regret bound. For clarity of exposition, we first present the algorithm in the case |2| 1, i.e., without public information available (and thus we remove 24 from the algorithm). The extension to |2| > uses similar arguments and discussed
in Section 3.5
3.1 Overview of the algorithm
Algorithm [ devised to solve this problem is composed of two parts: a bandit algorithm for the source selection, and gradient descent to adjust the penalty regularization term. This requires dual parameter d₃ E ddd that used to perform the source selection as well as the allocation decision Ie.
The intuition is the following: the performance of each source is evaluated through some "dual value" for given dual parameter A. The optimal primal performance equal the dual value when is minimized in X, because R is convex and randomized combinations of sources is allowed thus there no duality gap. Hence the dual value of each source is iteratively evaluated in order to select the best source, and simultaneously minimize the dual value of the selected source through X, so that the source selected is indeed optimal.
Bandit part. For the source selection, we use the EXP3 algorithm (see Chapter 11 of Lattimore & Szepesvári (202)) virtual reward that depends on the dual parameter. Given dual parameter X R and a context Cuk, we define the virtual reward as
p((r,, Cak. k) max (B[u, cxx] E(a, cxl)), Ps+
(5)
where (Ae, Bla, c(x) denotes the scalar product between X and T8aa cuR.. compute this expectation, one needs to know the quantities pk. E[u, (fu/le [ce]] and E[a, [cx)).
5

---

To apply EXP3, a key property is to ensure that the virtual rewards are bounded, which requires A to remain bounded. As we show in Lemma this is actually guaranteed by the design of the gradient descent on X. This lemma implies that there exists E I such that (yp(),, Ctk) S m for all and k. Let us denote by Tek the probability that source le is chosen at time f and k Wy- We define the importance-weighter unbiased estimator vector 40(X, ce) E IR where each coordinate k E [K] is:
1[ke =k] m G(), Cck. k)
((,, Cek. k. k)) m
Tek
Using this unbiased estimator, we can apply the EXP3 algorithm to this virtual reward function.
Gradient descent part. Once the source ky for user chosen and Ctk, is observed, we can compute the decision (see (6). This is then used in (8)-9) to perform dual descent step on the multiplier λ Although using dual descent step classical, our implementation is different because we need to guarantee that the values of d remain bounded for EXP3. To do so, we modify the geometry of the convex optimization sub-problem by considering set of allocation targets larger than the original A. For 8 E A, we define the set As as the ball of center å and radius Diam(A). This ball contains A: A C A..
Algorithm uses any extension of R to = UsEa Ag that is convex and Lipschitz-ccontimouus, for instance, the following one (see Lemma
D.2
R(6)
inf (R(6") 1. - -
8'EA
that has the same Lipschitz-constant L R (which is the best Lipschitz-conssant possible).
3.2 Algorithm and implementation
This algorithm maintains a dual parameter X that encodes the history of unfairness that ensures that the fairness penalty R(-) is taken into account. This dual parameter X₂ is used in (6) to compute the allocation 2, and in (7) to choose the source of guarantees that we take R(.) into account.
Combining these different ideas leads to Algorithm T
information. The dual update 8
Algorithm Online Fair Allocation with Source Selection
Input: Initial dual parameter AØ. step sizes 1) and p. cumulative estimated rewards S, = R for [T' do
Draw source Kg ~ Ne where Tek cxp(pS(-1.tt) / exp(pSt-1,1). and observe Ctk.- Compute the allocation for user t:
{
1
1
if Efu Ctay) Bla cok,)) otherwise.
(6)
Update the estimated rewards sum and sources distributions for all k E [K]:
Su = S(r-1) 1)a + ((Ae, Cuk, ke k))
Let 6; = 2z cra,). Compute the dual fairness allocation target and update the dual parameter
Yt arggamas maxf (de, - R(y)), 7Eds,
(8)
A411 = A - -77 - 5z)-
end for
An interesting property of the dual gradient descent is that it manages provide good fair allocation while updating the source selection parameters simultaneously. Indeed if X were fixed, then we could solve the source selection part through y and a bandit algorithm. However, both the X and the m change over time, which may hint at the necessity of a two-phased algorithm as the combination of these two problems generates non-stationarity for both the dual update and also for the bandit problem. The dual gradient descent manages combine both updates in single-phase phased algorithm.

---

The different assumptions imply that the decision maker has access to the E[ay| and to Efu, | cukl for any possible context value Ctg- Such values could be indeed estimated from offline data. The knowledge of such values is sufficient to compute the allocation 2t in 6 the virtual value estimation e of (7). or to compute 6z. Once these values are computed, the only difficulty to solve ( In some cases, it might be solved analytically. Otherwise, it can also be solved numerically as it is an (a priori (owddimensional) convex optimization problem. Overall this is an efficient online algorithm which only uses the current algorithm parameters X Te, and current context Otky
3.3 Regret bound
We emphasize that Algorithm I Jses randomization among the different sources of information and does not aim to identify the best source. As shown in Proposition 2.1 this is important because using the best source of information can be strictly less good that using randomization. Moreover, it simplifies the analysis because it convexifies the set of strategies. This means that Sion's 's minimax theorem can be applied to some dual function, which allows for X and T., to be updated simultaneously, If one would try to target the best static source of information (static-OPT), one would need to determine the optimal dual parameter 2 of each source. This would lead an algorithm that is both more complicated and less efficient (because of Proposition 2.1
The following theorem shows that Algorithm has a sub-linear regret of order O(VT). This regret bound is comparable to those in Balseiro al. (202T); [elli al. (2022) but we handle the much more challenging case of having multiple sources of information, and imperfect information about ag and it.
Theorem 3.1. Assume that Algorithm is run with the parameters 1j = L/(2 Diam (A)T)) and that do E aR((), the subgradient of R at O. Then the expected regret of the algorithm is upper bounded by:
m = ū + L + max + 2nj Diam A), = (Tog(K)/(TKKn))
Reg $ 2(( + max|pel) K log(K) + LVd + L Diam(A)) + 2L K log(K).
consider reduces bandit with bounded rewards E max (u c. 0) P&] for arm k [K]. which has Q ((T)) regret lower bound (Lattimore & Szepesvári 2020). It is of the same order in T as our regret upper bound. Remark that R = 0 implies that 7. and we do recover the regret bound for the EXP3 algorithm. Similarly if K = 1 the bandit regret contribution disappears. In our analysis, the regret due to the interaction between the bandit and the online fair allocation is L K (og(K)T.
Note that this regret bound is tight: when R 0 the problem
K-armed
The time-horizon dependent parameters used in Algorithm can be adapted to obtain anytime algorithm. While using a doubling trick directly for r) is not possible as some protected attribute would already be selected when restarting the algorithm, m 0(1/V), Indeed due to the boundedness of the (At)tr (Lemma 3.2) we can act as if we had a finite diameter for the space of the A₁- This results in a slight increase regret, the constant term in
can
use adaptive learning rate of
Theorem 3.1 now scaling in ((VT).
3.4 Sketch of proof
As mentioned above, when K (resp. R = 0) the problem reduces to fair online allocation as in Balseiro al. (2021); :) Celli et al. (2022) (resp. to multi-armed bandits). The main technical difficulty thus lie in combining algorithms used in these problems. Ideally, we would have access to some optimal dual parameter Ag before we the algorithm that we can simply run bandit algorithm, which is obviously not possible as the selected source ke affects the fairness, and the selected parameter > affects the arms virtual rewards. In particular it is not clear how the de evolve in the worst case while the algorithm is running. Instead we alternate between those primal and dual updates. We thus need show that this alternation indeed achieves good performance.
We present two important lemmas used in the proof of Theorem 3.1, The first one guarantees that doing gradient descent with R implies that the dual values X remain bounded. This is crucial for EXP3 as it implies that the virtual values &p remain bounded along the path of the Ae-
Lemma 3.2. Let Xo E Rd, > O, and an arbitrary sequences (8 ō2,...) E A Assume that Xn E aR(O) and define recursively de by Equations and Then for all i, we have | < L + 2n Di.
7

---

Sketch of Proof. The main idea is to show that the distance of X to the reunion of subgradients of R (which bounded by Lipschitzness property) is a decreasing function in t. We can show this by using the K K'T conditions of the optimization problem. The convex set over which we optimize is a simple Euclidean ball, because of our modification, centered around the appropriate point hence allowing us to redirect the gradient A4+1 X towards this set. Moreover, we add some "security" around this set of the size of the gradient bound to make sure that the Xe remains in this set. The full proof can be found in Appendix D.3
The second lemma guarantees that having access to the conditional expectation E|a [cux] is enough to derive a good algorithm when considering the conditional expectation the total utility. This way we avoid the computation of the conditional expectation of R. which would be more difficult.
Lemma 3.3. For (I1...., 2T) and (k1....,ky kr) generated according to Algorithm ? B, Coke) we have the following upper bound:
with de
T S 2L
/ T
E
axar) R(
6e)l
Sketch of proof. We use the Lipschitz property of It and some inequalities to directly compare the difference of the sums. The variable 2, depends on the past history and needs to be carefully taken into account, through proper conditioning. Finally, we compute the variance of sum of martingale differences. See proof in Appendix D.4
Using these two Lemmas, we now give the main ideas of the proof of Theorem 3.1 First, we upper- bound OPT through a dual function involving the convex conjugate Rt, with similar arguments as in Balseiro et al. (2021); Celli et al. (2022). Then we need to lower-bound ALG with this dual function minus the regret. The main difficulty is that the source virtual rewards distribution changes with A and so does the average x target through Te. The performance of ALG can be decomposed at each step f into the sum of the virtual reward and term in R (Xt) encoding the faimess penalty. We deal with the virtual rewards using an adversarial bandits algorithm able to handle any reward sequence using techniques for adversarial bandits algorithm from Hazan (2022); Lattimore & Szepesvári (2020), as the X₂ are generated by a quite complicated Markov-Chall These rewards are bounded because of Lemma 3.2 This yields the two regret terms in /K (K), the second one stems from the difference between Á and A. For the fairness penalty, using the online gradient descent on the A end up being close to the penalty of the conditional expectations up to the regret term in Diam(A), This last term is close to the true penalty through Lemma 3.3 This provides us with a computable regret bound where all the parameters are known beforehand. The full proof can be found in Appendix E
3.5 Public contexts
We now go back to the general case with [ > 1 finite. We would like to derive good algorithm, which also takes into account the public information 2,. Reusing the analogy with bandit problems, this seems to be akin to the contextual bandit problem, where we would simply run the algorithm for each context in parallel. However, this would be incorrect: not only for fixed public context does the non-separability of I couples the source selection with the fairness penalty, it also couples all of the public contexts 2, together. Hence the optimal policy is not to take the best policy for each context, which is once again different from the classical bandit setting.
The solution is to run an anytime version of the EXP3 algorithm for each public context in Z, but to keep common X₂ for the evaluation of the virtual value. While it is technically not much more difficult and uses similar ideas to what was done for different sources when |2| 1, the fact that only one of the "block" of the algorithm (the bandit part) needs to be parallelized, is quite specific and surprisingly simple.
Proposition 3.4. For μ the probability distribution over Z finite, we can derive an algorithm that has a modified regret of order O( TK log( K) ELez V Vu(=)), where p(z) is the probubility that the public attribute is z.
8

---

The algorithm and its analysis are provided in Appendix L.1
Note that in the worst case, when 2 is finite, one has Σzez V f/(z)= & 2 by Jensen's inequality on the square root function.
Z is not finite but a bounded subset of a vector space set of dimension r, such as Z = [0, 1J". additional assumptions the smoothness of the conditional expectations are sufficient to obtain sub-linear regret algorithm:
Proposition 3.5. If the conditional expectations of and are both Lipschitz in then discretizing the space 2 = [0, 1|" through an c-cover and applying the previous algorithm considering that one public context corresponds one of the discretized bins, we obtain a regret bound of order ()
The proof of this result uses standard discretization arguments under Lipschitz assumptions from Perchet & Rigollet (2013), which can also be found in Chapter 8.2 of offSlivkins) (2019) or Exercise 19.3 of Lattimore & Szepesvári (2020). Specificities for this problem, such as these assumptions being enough to guarantee that yp is Lipschitz in z, can be found in Appendix J.2
4
Extensions
4.1 Other types of fairness penalty
The fairness penalty term of Equation 1 is quantified TR(E axx//T). While this term is the same as the one used in Celli et al. (2022) and can encode various fairness definitions (see the discussion in the aforementioned paper), this does encompass all possible faimess notions. For instance, one may want to express fairness as a function of Σ d,Dt// E, Tt, which is the conditional empirical distribution of the user's protected attributes given that they were selected. This would lead to replacing the original penalty term by (E, xz) R(E axxi/ Σ; zz).
As pointed out in Celli al. (2022), one possible issue is that R(E a/34// E. 24),, in general, is not is the perspective function of R(A(-)) (with A the matrix with columns the 0t), which is thus convex. Hence, Algorithm [ can be adapted to handle this new fairness penalty with two modifications. First, for the bandit part, we run the algorithm with new virtual reward function, expressed as:
convex in x, even R is convex. However (E. xz R{ O / E, xt)
(()e, Cak, k) = max(E[u: | cekl (Ae, Ela, cud) + (Ae),))) Pk.
This leads to an allocation I; if B[ue CoRy] + 18* (Ax) (Ae, Ela, cen,)) and 0 otherwise.
Second, we modify the set on which the dual descent is done. The set A now becomes Á = Conv(A (without the union with 0), and we now use d, E[a, Cck,] instead of 6, 2, CeR. Line (8 remains unchanged up to replacing 5 and A by 8 and Á. Finally the dual parameter update now becomes d++1 X rppa(1 Jz), which means that whenever 2; 0, d does not change.
With these modifications, the following theorem (whose proof is very similar to the one of Theorem 3.1 and detailed in Appendix G). shows that we recover similar regret bounds as previously, with some modified constants due to the presence of Ie the virtual reward, and the modified A. This yields a new class of usable fairness penalties which was previously not known to work.
Theorem 4.1. Using Algorithm I with the modifications detailed above, the regret with respect to the objective with the modified penalty (E, R(E axxt/ Σ, 51.) is of order O(VT).
4.2 Learning conditional utilities E[u, cea]
To compute the virtual values, the algorithm relies on the knowledge of Eluu | Cea] for all possible context values. We now show how relax this assumption even if the decision maker receives the feedback ue only when the user is selected (x, = 1). We shall make the usual structural assumption of the classical stochastic linear bandit model. The analysis relies on Chapters 19 and 20 Lattimoe & Szepesvári (2020), and only the main ideas are given here. For simplicity we will assume that there are no public contexts (|2) = 1).
We assume that the contexts Co are now feature vectors of dimension gk, and that for all l e [K]. there exists some vector 2h E 18 so that
U (t'R, Cak)s
(10)

---

is a zero mean 1-subgaussian random variable conditioned on the previous observation (see a more precise definition in Appendix H.. We make classical boundedness assumptions, that for all k: 1 I 1h, that |c S C, and that (v/x, Cea) S 1 for all possible values of Ctk-
Intuitively, we aim at running a stochastic linear bandit algorithm on each of the different sources for T' steps, where 73k is the number of times that source k is selected, but this breaks because of dependencies among the k sources. Hence, what we do to slightly change the rewards and contextual actions, so that we do something akin to artificially running K bandits in parallel for "' steps. We force a reward and action of O for source whenever is not selected, and consider that each source is run for T steps (even if it is actually selected less than T times). Thus we can directly leverage and modify the existing analysis for the stochastic linear bandit. The full algorithm given in Appendix H
Proposition 4.2. Given the above assumptions, the added regret of having to learn Elu, | Gaa] is of order O(v (Tg()))
If the decision maker knows the optimal combination of sources, she can simply select sources proportionally to this combination, and actually learn the conditional expectation independently for each source. The worst case is have pull each arm T/ K times, which then incurs an additional regret with the same vK constant. This shows that this bound is actually not too wasteful, as the cost of artificially running these bandits algorithm in parallel only impacts the logarithmic term.
5
Conclusion
We have shown how the problem of optimal data purchase for fair allocations can be tackled, using techniques from online convex optimization and bandits algorithms. We proposed a computationally efficient algorithm yielding a O TT) regret algorithm in the most general case. Interestingly, because of the non separable penalty R. the benchmark different from bandit algorithm, as randomization can strictly improve the performance for some instances, even though the setting is stochastic. We have also presented different types of fairness penalties that we can additionally tackle compared to previous works, in particular in the full information setting, and some instances where assumptions on the decision maker's 's knowledge can be relaxed.
Throughout the paper (even in Section 4.2 where we relax the assumption that Efuu Caa] is known), assumed that the decision-maker knows Baa; cek)- This assumption is reasonable as this is related to demographic data and not to a utility that may be specific to the decision maker. Yet, this assumption can also be relaxed in specific cases. As an example, suppose that the decision maker can pay different prices to receive more or less noisy versions of a, that correspond to the data sources (the pricing could be related to different levels of Local Differential Privacy for the users, see Dwork & Roth (2014)). Then, under some assumptions, E[aa details to Appendix[! !I]
cuk] can also be learned online we defer the
The works of Balseiro et al. 1 and Celli et al. (022)) can include hard constraints on some budget consumption when making the allocation decision xt, which did not include in our work. If this budget cost is measurable with respect to Cue, then our analysis does not preclude using similar stopping time arguments as was done in these two works. However if this budget consumption is completely random, our algorithm and analysis can not be directly applied as this budget consumption may give additional information on the a that was just observed. Regarding the i.i.d. assumption, in Balseiro et al. (202T) adversarial inputs are also considered, and the same could be done here for the contexts C₁ with similar results. However some stochasticity still needed so that E/u, cr,+] is well defined, which leads to an ambiguous mochastic-adversaan model. An open question would be consider an intermediate case where E u, c.,a] would depend on t, and take into account learning for non-stationary distributions.
Acknowledgements
This work has been partially supported by MIAI @ Grenoble Alpes LANR-19-P31A-0003 by the French National Research Agency (ANR) through grant ANR-20-CE23-0007 ANR- 199-119- and ANR- MIR-19-CF23-0026,, and from the grant "Investissements d' Avenir" (LabEx Ecodec/ANR-1 LABX-0047).
10

---

References
Abbasi-yadkori, Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, 2011.
Agrawal, S. and Devanur, N. Linear contextual bandits with knapsacks. In Advances in Neural Information Processing Systems, 2016.
Agrawal, S. and Devanur, N. R. Fast algorithms for online stochastic convex programming. In Proceedings of the 2015 Anmual ACM-SIAM Symposium on Discrete Algorithms, 2015.
Ahani, N., Gölz, P., Procaccia, A. D., Teytelboym, A., and Trapp, A. C. Dynamic placement in refugee resettlement. Proceedings of the 22nd ACM Conference on Economics and Computation, 2021.
Ali, M., Sapiezynski, P., Bogen, M.. Korolova, A., Mislove, A., and Rieke, Discrimination through Optimization: How Facebook's 's Ad Delivery can Lead to Biased Outcomes. In Proceedings of the ACM Conference on Computer Supported Cooperative Work, 2019.
Badanidiyuru, A., Kleinberg, R., and Slivkins, A. Bandits with knapsacks. J. ACM, 2018.
Balseiro, S., Lu, H., and Mirrokni, V. Dual mirror descent for online allocation problems. In Proceedings of the 37th International Conference on Machine Learning, 2020.
Balseiro, S., Lu, H., and Mirrokni, V. Regularized online allocation problems: Faimess and beyond. In Proceedings of the 38th International Conference on Machine Learning, 2021.
Balseiro, S. R., Besbes, O., and Weintraub, G. Y. Repeated auctions with budgets in ad exchanges: Approximations and design. Columbia Business School Research Paper Series, 2014.
Barocas, S., Hardt, M., and Narayanan, A. Fairness and Machine Learning. fairmlbook.org. 2019.
URL http:://www..iirmbbbboooo
Buolamwini, and Gebru, T. Gender shades: Intersectional accuracy disparities in commercial gender classification. In Proceedings of the 1st Conference on Fairness, Accountability and Transparency, 2018.
Burke, R. Multisided fairness for recommendation. In Proceedings of the Workshop on Fairness, Accountability and Trans- parency in Machine Learning, 2017. Available ArXiv:11077 1707.00093.
Castiglioni, M., Celli, A.. and Kroer, Online learning with knapsacks: the best of both worlds, In Proceedings of the 39th International Conference on Machine Learning, 2022a.
Castiglioni, M., Celli, A., Marchesi, A., Romano, G., and Gatti, N. A unifying framework for online optimization with long-term constraints, 2022b. Available as Axxiv22009074554
Celis, L. E., Huang, L., Keswani, V., and Vishnoi, N. K. Fair classification with noisy protected attributes: framework with provable guarantees. Proceedings of the 38th International Conference Machine Leurning, 2021.
Celli, A., Colini-Baldeschi, R., Kroer, C., and Sodomka, The parity ray regularizer for pacing in auction markets. In Proceedings of the ACM Web Conference, 2022.
Cesari, T. and Colomboni, R. A nearest neighbor characterization of lebesgue points in metric measure spaces. Mathematical Statistics and Learning. 3, 2020.
Chang. H. and Shokri, R. On the privacy risks of algorithmic fairness. In IEEE European Symposium on Security and Privacy, 2021.
Chen, Y. and Zheng, S. Prior-free data acquisition for accurate statistical estimation. Proceedings of the ACM Conference Economics and Computation, 2019.
Chen, Y., Immorlica, N., Lucier, B., Syrgkanis, V., and Ziani, Optimal data acquisition for statistical estimation. In Proceedings of the 2018 ACM Conference Economics and Computation, 2018.

---

Chouldechova, A. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments, Big Data, 5(2), 2017.
Dastin, Amazon scraps secret ai recruiting tool that showed bias against women, 2018. awwzon- jobs automation insight/ that showed bias against women
URL
amazon
idUSXCN1MK08C
Dickerson, J. P., Sankararaman, A., Srinivasan, A., and Xu, Balancing relevance and diversity in online bipartite matching via submodularity. In AAAI Conference Artificial Intelligence, 201 8.
Dwork, C. and Roth, A. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 2014.
Emelianov, V., Gast, N., Gummadi, K. P., and Loiseau, P. On fair selection in the presence of implicit variance. Proceedings of the 21 ACM Conference on Economics and Computation, 2020.
Fioretto, F., Tran, C., Van Hentenryck, P., and Zhu, K. Differrntial privacy and fairness in decisions and learning tasks: A survey. In Proceedings of the Thirty-First International Joint Conference Artificial Intelligence, 2022. Survey Track.
Flajolet, a. and Jaillet, P. Real-time bidding with side information. In Advances in Neural Information Processing Systems, 2017.
Gelauff, L. L., Goel, A., Munagala, K., and Yandamuri. S. Advertising for demographically fair outcomes. ArXiv, 2020. Available as arXiv:2006.03983.
Guardian. Facebook and instagram to restrict advertisers' access teenagers' data. The Guardian. and http://chcoolooo///////////a/aaa 2023. URL -os.ooo--ooiiteee-oootoiiiiiiiii restrictions around -eenandeeeeeeerrsee. data
to tiighee
Hardt, M., Price, E., and Srebro, N. Equality of opportunity in supervised learning. Advances in Neural Information Processing Systems, 2016.
Hazan, E. Introduction Online Convex Optimization. The MIT Press, 2nd edition, 2022.
Heidari, H. and Krause, A. Preventing disparate treatment in sequential decision making. In Proceedings the Twenty-Sevnnth International Joint Conference Artificial Intelligence, 2018.
Iyer, K., Johari, R., and Sundararajan, M. Mean field equilibria of dynamic auctions with learning: A dynamic revenue equivalence theorem. 49th Annual Allerton Conference on Communication, Control, and Computing, 2011.
Jabbari, S.. Joseph, M., Kearns, M., Morgenstern, J., and Roth, A. Fairness in reinforcement learning. In Proceedings of the 34th International Conference Machine Learning. 2017.
Jagielski, M., Kearns, M., Mao, J., Oprea, A., Roth, A., Malvajerdi, S. S., and Ullman. Differentially private fair learning. In Proceedings of the 36th International Conference on Machine Learning. 2019.
Jenatton, R., Huang, J., Csiba, D., and Archambeau, C. Online optimization and regret guarantees for non-additive long-te term constraints, 2016. Available
Joseph, M., Kearns, M., Morgenstern, J., and Roth, A. Fairness in learning: Classic and contextual bandits. In Advances in Neural Information Processing Systems, 2016.
Kamishima, T., Akaho, S., and Sakuma, J. Fairness-aware learning through regularization approach. In IEEE 1 1thh International Conference on Data Mining Workshops, 2011.
Kleinherg, J. and Raghavan, M. Selection problems in the presence of implicit bias. In 9th Innovations in Theoretical Computer Science Conference, 2018.
Lambrecht, and Tucker, Catherine, Algorithmic bias? an empirical study into apparent basder-based discrimination in the display of stem career ads. In Management Science, 2019.
12

---

Lamy, A., Zhong, Z., Menon, A. K. and Verma, N. Noise-tolerant fair classification. In Advances in Neural Information Processing Systems, 2019.
Larson, J., Mattu, S., Kirchner, L., and Angwin, J. How We Analyzed the COMPAS Recidivism Algorithm, 2016. URL
(ompas-ree rewrieeiiiiiinni www.ddiviis-aagrrtthm
Lattimore, T. and Szepesvári, C. Bandit Algorithms. Cambridge University Press, 2020.
Li, X. and Ye, Online linear programming: Dual convergence, new algorithms, and regret bounds. Operations Research, 2021.
Li, X., Sun, C., and Ye, Simple and fast algorithm for binary integer and online linear programming. Mathematical Programming. 2022.
Lipton, Z., McAuley, J., and Chouldechova, A. Does mitigating ml's impact disparity require treatment disparity? In Advances Neural Information Processing Systems, 2018.
Liu, X., Li, B., Shi, P., and Ying, L. An efficient pessimistic-optimitti algorithm for stochastic linear bandits with general constraints. In Advances in Neural Information Processing Systems, 2021.
Molina, M. and Loiseau, P. Bounding and approximating intersectional fairesss through marginal fairness. In Advances in Neural Information Processing Systems, 2022.
Nasr, M. and Tschantz, M. C. Bidding strategies with gender nondiscrimination constraints for online ad auctions. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, 2020.
Orabona, F. A modern introduction to online learning, 2019, Available as arXiv:1912.13:: 1912.13113.
Perchet, V. and Rigollet, P. The multi-armed bandit problem with covariates. The Annals of Statistics, 41(2), 2013.
Rockafellar, R. T. Convex Analysis. Princeton University Press, 1970.
Slivkins, A. Introduction to multi-arman armed bandits. Foundations and Trends@ in Machine Learning, 12 (1-2), 2019.
Speicher, T., Ali, M., Venkatadri, G., Ribeiro, F, N., Arvanitakis, G., BeneBennto, F., Gummadi, K. P., Loiseau, P., and Mislove, A. On the potential for discrimination in online targeted advertising. In Proceedings of the Ist Conference on Fairness, Accountability and Trunsparency. 2018.
Vershynin, R. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
Probability: An Introduction with Applications in Data Science.
Zhao, T., Dai, E., Shu, K., and Wang, S. Towards fair classifiers without sensitive attributes: Exploring biases in related features. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, 2022.
13

---

A Fairness Penalty
In the main part of the paper, we have considered a penalty with a general form R(E, (T). Here give examples of fairness notions that can be encoded through this general penalty.
Statistical parity Notions likes statistical parity are defined as constraints on the independence between protected attributes and selection decisions. More precisely, if X denotes a treatment variable, and A the protected attributes of an individual, we say that X and A are fair with respect to statistical parity if X and A are independent.
If X E X' and A E A can take finite number of values, this can be equivalently rewritten using probability distribution: satisfies statistical parity if for all (z, a) E X A:
Pr(A = a, = x) = Pr(A = a) Pr(X=
(11)
To encode statistical parity in our framework, we consider that the a are one-hot encoding of the protected attributes (i.e, a₃ a vector with d |AA| dimensions that is equal to 0 everywhere except on the coordinate corresponding to the protected attribute of individual t, that equals 1). For the decision variables æ 10, E, de is the number of individual selected and E, (ar)aa is the number of selected individual whose protected attributed is i E [d]. Hence, [I] rewrites as: for all i [d]:
En(o)) T
(xlande) T
Recall that the variables a, are i..dd and let us denote by a E Pa the probability distribution vector of the ag For large T, we have Ee / a. Which means that will say that allocation vector æ satisfies statistical parity if 21 0,34 TT = E, oax/TT which can be equivalently rewritten as
E. afr 0,
T
with o/ = ag a.
Penalties R corresponding to statistical parity In practice, achieving strict statistical parity is very constraining, and most the time some relaxation of this constraint allowed, at the price of some penalty (Ahani et al. 202I). In our paper, we penalize the non-independence through the function R. There different choices of penalty function that can be used:
A natural choice can be to penalize function of the distance between joint empirical distribution a/xx/TT and 0. For instance, one could use R(alxx//T) = ||//2//T|| for any given norm || and any parameter 3 0.
It is also possible measure the non-independence with the empirical distribution of the V, conditioned on a; a. which should be equal regardless of the protected group a A. In this case, the empirical distribution conditioned on the protected group E [d] is Σ, A.: Σ, au s Σ, 0.: far this vector from
(t:T)/(a;TT), (a;T). Similarly we the previous case, R can penalize how
In the two cases, the fairness penalty can be written TR(E, d/xx/TT,, for some modified of that are not necessarily one-hot encoder. This explains why we choose the set A to be more general than the set of one-hot encoders.
we want to target another specific proportion for each protected group, we can replace a by any other distribution Note that another possibility is to instead use the empirical distribution of the de conditioned on the æt. This time the form of the vector is slightly different, it is E, a,21/ E. mei this is the type of penalty tackled and discussed in Section 4.1
Equality of opportunity Another popular fairness notion is the one of equality of opportunity (Hardt al, (016)), where the probability distribution further conditioned on another finite random variable y/ taking some discrete value in y that indicates some fitness of the individual. For Y
14

---

random variable with an outcome y E Y considered as a positive opportunity, we say that X, A and Y are fair with respect equality of opportunity, if
X and A independent given [Y y)-
In order to adapt this notion in the online allocation setting, is sufficient to consider the cartesian product .A' A Y as an extended new set. Then we would like to penalize with metric related to equality of opportunity, we can for instance compose R with the projection over the coordinates corresponding to 8/2 1.
Overall, this shows that the choice of R, the type of fairness vectors, and the choice of A are all crucial when designing fairness penalty.
B A More General Online Allocation Setting
In the main body of the paper, we choose to simplify the exposition and to restrict ourselves to It {0, 1} and to formulate utilities as scalar variables ut, In the following, the regret bounds of Algorithm are obtained in a setting that is more general than the one previously introduced:
We now consider that the allocations decisions Iy are in some set X' C R This makes
possible to tackle bipartite matching problems, by letting X' = {o E R E 24 S 1} be matching polytope.
Instead of a random scalar u, being drawn, we suppose that random function ft X R is drawn. The functions f. are supposed u.s.c. and are all bounded in absolute value by some f. This could simply be a deterministic concave function of for instance. Remark that when we assume that the conditional expectation can be computed, the decision maker's required knowledge is more demanding, as she needs to be able to compute it for all E X.
Instead random vector, a continuous random function a, X - A can be drawn, with (z))2)l22 uniformly bounded for all a and x, and we define Á = Conv(A4. We suppose that || (2) $ 1, which can be done without loss of generality.
The setting of Section 2.1 is recovered by using fx())= uzz, dx(x)) aræ and X' {0, 1}. For the more general setting, we need to redefine the virtual value with ft and az as:
((),
max [xf
cak] Pk
(12)
This virtual reward is well defined by Lemma D.I We rewrite Algorithm [ using ft and this new virtual value to obtain Algorithm 2 There are two differences with Algorithm I First use the argmax function in (33 instead of the explicit form of Equation (6); Second we use the virtual value function 12) in Equation (14) instead of the virtual value function of Equation (5)
C Reduction from auctions
In the rest of the paper, we assume that the decision variables are the values zt. this section, we explain how our setting can be adapted the the case of targeted advertisement, that are usually allocated through auction mechanisms. the later, the decision variables are the bids but not the rz: the variables 2, are a consequence of the bids of the decision maker and of the bids of others.
Model The model that consider is follows: for I, after choosing source of information k,, the decision maker observes Crk, and decides to bid b, E B. The allocation = is given her bid is higher than the maximum bid of the other bidders. If the bidder wins the auction, then pays a price that depends on the auction format (e.g., be for first price auctions and the second highest bid for second price auctions), Assuming that the bid of the others are not affected by the decision maker's strategy, the bids of the others are i.i.d. (see Iyer et al. (2011); Balseiro et al. 2); |Flajolet & Jaillet (2017) for a discussion about the stationarity assumption). In this case, one falls back to our model with i.i.d. users, except that the decision variables are the variables b, and we have x; xx(b)). We can apply our algorithm to this setting, by replacing the set of strategies by the set of possible bids B, which is also compact. For that, we need to consider new utility function b + u, (b) (1))a(()) (b) which is a bounded u.s.c. function, and the new protected attributes function b + a:3, (b). Bla,o,(b) cal continuous in b, this falls under the setting that we described in Appendix B
15

---

Algorithm 2 Online Fair Allocation with Source Selection - General algorithm
Input: Initial dual parameter Ao, initial
To (1/K,.... 1/K), dual
gradient descent step size EXP3 step size p. cumulative estimated rewards Su = 0 R for t E [T] do
Draw source K2 ~ Tr, where (Te) x exp(pS(t-1))) and observe Ccke Compute the allocation for user
Tt arg max [f) (+))) cek.].
(13)
zEx
Update the estimated rewards sum and sources distributions for all k E [K]]
Sik SI-1AA + (pAe, Cuky ke),
(14)
Compute the expected protected group allocation 5, ((a)())) Ceky: va) and compute the dual protected groups allocation target and update the dual parameter:
Tte arg max (A,, 7) R(7)),
7Eax,
As+1 A 777 - 6z).
end for
first-price and second price auctions Let us denote by i2 the value of the user i for the decision maker, and by de the highest bid of the others for this user. The decision maker will win the auction if be 2 dz. Hence, the allocations will be x (b:)) = Il.,dd Moreover, the utility function will be:
Examples of utilities:
* fbb.)) = (w: - (b)) for first price auctions.
. f2(b.) = (ve- - (b)) for second price auctions.
These functions are u.s.c with respect to b;. Moreover, under mild assumption that the distribution of the highest bid of the others de has density, the function E(axxe(b))caa is continuous. Hence, our algorithm can be applied.
Difficulty: Knowledge is power To apply the algorithm, the main difficulty is to be able to compute the value that maximizes Equation 11).. For that is sufficient for the decision maker to have access to [ (bx) [cx,,] and E|a,0, (be) [c, This presupposes a lot of distributional knowledge from her part. In the case full information with a, and et directly given, Balseiro et al. 202 l);
Celli et al. (2022) were able to obtain an efficient reduction from online allocations to second price auctions, using the incentive compatible nature of this kind auction. Similarly, Flajolet Jaillet (2017) were able to derive efficient bidding strategies using limited knowledge for repeated auctions with budget constraints under some independence assumptions. Translating what is done these two lines of work our general model is difficult because would need rely on the assumption that a₂ and d, are independent conditioned on Cek, While we think that this assumption is not reasonable because different agents might have access different information sources, and because the a is common to all bidders it is correlated with all the bids hence also with d, we explain the remark below how assuming independence can lead simple algorithm for second price auctions. Some remarks:
For model, the first price and second price auctions equally difficult: The amount of knowledge needed to compute b, and n. is the same for both cases and first price auction is not difficult than the second-price auction setting (contrary to what usually happens).
During this whole reduction from auctions, we have not assumed that the d, (or xx) are observed as a feedback (whether the bidder wins the auction or not), and thus they are not assumed to be observed in the benchmark either. This is because observing d, or 2, could give us access to information on a, that are not contained in Cak,
If we do make the assumption that (u,, az) is independent of d, conditionally on Gak- then do recover easy algorithm for second price auctions, and can allow for
16

---

benchmark taking into account the feedback dy (simply because now this feedback does not give any additional information for the estimation a₁). Indeed, in that case the optimal bid is b, = 1E(v (de, ax) Cta). This follows from similar argument made in Flajoler & Jaillet 2017). as for be some Hr measurable bidding strategy we have:
EE [1 (De; at) dezt CeR,]
E E Ur-r2 - (Ae, ae)ar. dr He, de] Ctk.]
= E [1 CeN, Jaz - (Ae, Elag Cen,))0 = dryz Cek)
E pre (Eluz coR,) (Ae; Elat. cax,)) d,) cta)
s Blmax(BBlv Cen,] - (Ae, Bla caN,)) d2, 0) cak),
and this last incquality is reached for b, = Elu;- - (Ae, az) |co]].
D Technical & Useful Lemmas
In this section, we prove several lemmas that are useful for the proof of the main Theorem 3.1
D.1 Preliminary lemmas
We first provide some simple lemmas. For completeness, we provide proof' of results, even they almost direct consequences of the definitions.
Lemma D.1. The virtual value function ip is well defined by Equation 12 as the arg max is non-empty and the maximum reached.
Proof. We simply need to have that [[ff(z) cas] and - (A,, (x))()) ccu]) u.s.c. in æ. The continuity of at is used to guarantee that - (I)) is u.s.c. regardless of the values of A. This is immediate from the definition of upper semi-continuity and the Reverse Fatou Lemma. We detail it here for fi for completeness. We say that fa is u.s.c. if and only if
Vr E X if there is a sequenee (In)neN so that In
n T, then lim sup fe(xx) S f(()..
For x E X, let (Ia))eN) be sequence so that Fig x. Let P be probability distribution over fi conditionally on Ctk- The function [xx)] ] < f. fz(() is integrable, we can apply the Reverse Fatou Lemma for conditional expectation. If (2,,) not positive, we can apply fi f( which is positive. Using the Reverse Fatou Lemma and the upper semi-continuity of ft we obtain:
/ [(lan)dP S / [im sup le(xn)dP S [((T)d..
lim limsup n-+00
This means that + (x) cek is u.s.c. over X.
Because X' is compact, and because the maximum of an u.s.c. function is reached over a compact set, the maximum is well defined.
Lemma D.2. Let R. : 8 infres (R(0') + L|88 81112) Then R = R over A. Lip( Lip(R), and convex.
Proof. The function R is obtained through the explicit formula of the Kirszbraun theorem, which states that we can extend functions over Hilbert spaces with the same Lipschitz constant. Hence the equality over A and the same Lipschitz constant.
remains to prove the convexity. Note that because R is proper, it is lower semi-continuous, 1 as well, and A compact, hence the inf reached and it is actually minimum. Let 61, 52 in I. and a E [0, 1]. and let U1 and uz be the minimums of the optimization problem for respectively 51 and 62. Let and we have
au; + a2 We have A because A is convex, and using that R convex
R(u) + Ll((ad) + (1 - )))))) - ul12 S a(H(u)) + 4|6 vill2) + (1)))) + 41102 u2l12)
= a + R(52),
and taking the inf over A on the left hand-side we obtain the convexity of R.
17

---

D.2 Conditional expectation: notation and abuse of notations
In the analysis of the algorithm, we will consider conditional expectation by fixing some of the random variables to specific values. To simplify notations, we will use the following notation: if X and Y random variables and g measurable function, then we denote Ex1g(X Y)] the expectation with respect to X, that is:
Exlo(X,Y) - ((g(X'
where X' a random variable independent of that has the same law as X. This is equivalent to the random variable obtained by fixing Y and taking the expectation with respect to the law of X only.
In Algorithm 2. we have assumed that the decision maker able to compute (xe) Ctk. and (x4) C While the law of Cak, is complicated (because it involves all past decision up to time t), what the decision maker needs to compute the value ((Ctk,: T. ke), where ((c, æ, k) = [
Oek = c]. Those two quantities are equal because users are ii.d. and k, and fr are independent (conditioned on 2, and the history).
This manipulation is properly stated by Lemma D.3 Indeed by denoting H4-1 the whole history up to time 1, and applying this Lemma: for I; the decision generated by the algorithm which (H,-1, Ctk.) measurable, we have that
(x)e Cake, H ki] = S(Ctks, Tt, ks) = EE (xx))) CcN.]-
(15)
is identical for ox(2)): for C'(c, x, k) = Ela((x) | CeN = c| we have the following equality
(x)) Cak. H4-1, k,] = C'(Ckk Te, kq) Ee, ( c.k.).
(16)
The following Lemma is modification of the so-called "Freezing Lemma" (see Lemma 8 of Cesari & Colomboni (2020)) which helps simplifying conditional expectations by allowing you to "fix" the random variable if it measurable with respect to the conditioning of the expectation:
Lemma D.3. Let X,Y and 7. be random variables with (X, Z) independent of and some bounded measurable function. Let us denote by a (X) the sigma-alge algebra generated by the random variable X. Then
Eig(X, 2) (Y, 2)] Ex[g(X, 2, o()]
[Z)). To show that W is the conditional expectation of g(X, 2) given oY,, Z), we need to show that is ooY, Z) measurable and that for any bounded W that (Y, Z) measurable we have
Proof. Let (Y Ex 2)
E[VW]
Y,
We denote by the distribution of (X, 2) and v the distribution of Y. By the Doob-Dynkin Lemma, because ofx oY, Z) measurable, we have that W h(Y, 2) where i is measurable. First, by independence of Y and (X, 2), we have that the distribution of (X, Y. Z) is du & du. Thus
[X, Z)W] = / g(x, v. 2)h(y, (x, 2 2)dx(y).
Now let us compute the other expectation using Fubini theorem as both & and h are bounded:
/
B[VW]
/ du(s) (f (VVw, (fV(v=)) z)h(y, ())=)))(==))du(a)) =)du(=)
= f dv(v) (Ez(V(y, Z)h(y, 2)))
The random variable h(y, 2) (Z) measurable, thus because V Vi, Z) a conditional expectation given (2), we have
Ez (v.. (v. 2)] = Ex. Ex.zlg(X,,)) Z)h(v. 2)1 = g(x, (.r.v,2)000 (xd 2).
18

---

Using Fubini again we obtain
2ddu(z B[VW] /dvli) (f g(z, y, 2, s(2,
/ g(a, = = W)
which proves that this is indeed the conditional expectation, as the lemma stated.
D.3 Boundedness of X - proof of Lemma 3.2
We next show the proof of the boundedness of the X for the sequence generated by Algorithm Lemma. Let do E RR > O, and an arbitrary sequences (δ1, (2,,0,,,.)) E A.. We define recursively
!
X as follows:
7/. arg max ( (Ae,, R(7)};
yEAr,
A441 = de + n( - -7t).
Then for A (R(8) we have the following upper bound:
||elll S L + 2n (iam + Dist(Ao: A B(0, 2n Diam(A))),
where (00, 2ny Diam(A)) is the ball centered and of diameter 2np Diam( (A), with the diameter and the distance taken with respect to the euclidean L2 norm.
Proof. Recall that Á Us with As = fr 1h 8|12 S Diam Hence, for any E A and E A, we have |/ - 8112 S 2 Diam (A). Let A = L and C = Conv(A) B(0, 1/2 Diam( Using that is L-Lipschitz, we have that A is bounded by L for the norm || 1l2- and so does Conv(A). Thus C is bounded by L 2n Diam( (A) for || 112. This implies that, prove the theorem, it suffices to show that Dist Dist(Ac+1, < Dist(Ae, C) is true for all t. Indeed, this would imply that
| S sup |oll2 + Dist(A,, C) S L 27) Diam + (ist(Do.C). oEC
In the remainder of the proof, we show that Dist(A++1 C) (A,, C). First, let us remark that y the solution of a convex optimization problem, wit a constraint set As, that can be rewritten as single inequality ht(7) < O, with hx(7) = || 5, _2 Diam A) The derivative of this function h20 (r) = 2(y - 8c). As the point 6, in the interior (assuming that Diam(A) > 0) of As,- Slater's 's conditions hold, and we can apply the KKT conditions at the optimal point (7x). This implies
that there exists μ 2 such that - + aR(x) + p2(m) dy). This implies that there exists
As, @R(x)) such that
Ao A 2/ 7
The norm of the left-hand side of the above equation must be equal to the norm of its right-hand side, which means that || dellz 2, - 222 This determines the value of μ. Let Os nl1ō, 7 /// - Axl12, the value Ae+ is therefore equal to:
Ae+1 > + v16, 7)) d + ar(ss, Ar) (1 ar)dr + andd..
We now consider multiple cases:
Case 1. of > 1, then we rewrite Ac+1 as:
Aet1 = = + (1- (1-oa)(A As.)
A As.
= = + (116 - rell2 - ||As, - xelle)
1|, As 11
By assumption, the As. 2n Diam(A) because
E aPR())) A. Moreover, the norm of the second term is bounded by
|||6, 71l22
1e5, - -ellel 1|6, roll2 1As, -xel2 S. 2 Diam(A).
19

---

This implies that Act1 E Conv(A) + B(0, 2ny Diam A)) = C, and therefore that Dist(Ar41: C) S Dist(A,, C).
Case 2. ar S and d E C. In this case, A++1 is a convex combination of X8, and d As, As, A C C and d C, and because C is convex, have that A4+1 E C.
Case 3. at I and d & C, we define के = ) the projection d on C. Let yt = (1 as)= a,A5, Because is convex, az E [0, 11, As, E C, and E C, we have y/s C. This implies that
Dist C) < | - y/ yell2
(1 --a))lrrr TTll2
= (1 - -4.) (Ne,
S Dist(Ae. C).
This shows that for all cases, Dist(Ae+1. S Dist(Ae, C) which concludes the proof.
Using this previous Lemma, we can simply bound the virtual reward functions.
Lemma D.4. For do E &RR()), and x generated according Algorithm 7 the virtual reward function
s(Ae, Cek, k) max [[f((x) (Nes (x)) cta) Pk: #EA
bounded absolute value by
m: f + I. 21) Diam max [pkl-
Proof. Because (1()) used for the update of X A for all can apply Lemma 3.2 to bound the trajectory of the (Ae (EE) generated by the algorithm. Using triangle inequality first, then Cauchy- -chhwrtt inequality, and finally the boundedness assumptions on fi and a with the Lemma, we have
max [xf((x) (Ac. ax(xx)))))))))))))))))))) exkl - pkl S max (x) [alll + max (A,, (x()) [as]l + |Pk] #EX
=ex
- max (z) calll + max [[Aeellll))))))))((()()))))) cadl + |pel =EX
=Ex
S 2n Diam (A) + max ps
k
Lemma D.5. For λo OR(a) (for some a E A), and for generated according to Algorithm if the quantity ae de(x)/x ix is always well defined and in A for all as and all x, then the virtual reward
function
p(>,, Cak. k) max (E[fe(z) (Ae,a((z)) cekl + R (Ne) Pk.
x
is bounded in absolute value by
m = f + L 2n Diam A) + (ax((X(()) |AAl22 S L 2n Diam [A]} + max |pu].
Proof. The proof of this Lemma is identical to the previous one, except that we also need to bound Rº As convex conjugate, !² is convex. By Corollary 10.1.1 of Rockafellar (1970), every convex function from IRd to R is continuous. By Lemma 1 of Celli et al. (2022). we know that the domain of R is indeed Rd hence it is continuous.
Now let us look at the modified dual update A4+1 = to recover A4+1 d 2,7((7 az(21)/z2). Because of our hypothesis, az (xx2)/22;
= X + 7/(12; - (x:)). We can factorize by zt
A, therefore we can apply Lemma 3.2 with 77, = 1724, which upper bounded by n7. Hence the X are all in {X E Rd |||l|2 < 2n Diam ()) which is compact. By continuity of R' it is continuous this compact set hence bounded, and the virtual reward is bounded by m overall.
Li
Remark. We made the technical assumption that a;(x)/x E A. clear that when a; is linear, such as aræ, then uxz/z = E A C A and the condition is satisfied. Regardless, if (xr) is always well defined and bounded, we can simply increase the size of A, so that this quantity always remain in A. Of course, this will degrade the performance of the algorithm it depends on Diam(A).
20

---

D.4 Expected difference between penalty and penalty of expectation - Proof of Lemma
3.3
We next prove the following lemma, which tells us that observing the conditional expectation of the (x)))) is enough to observe the expectation of the penalty R:
Lemma. For (Z1,...,,7y) TT) and (k1s...,ky) kT) generated according Algorithm 7
we have the
following upper bound:
1 R
[E[R T Σ a,31))
Σ
Ea, (oo(xz)) ccu. ca.. S 224/ T
Proof. Let us denote by de = Eu, (x+) cus. the expectation of ax(xx) with 2, fixed. Using first the triangle inequality for the expectation, and then the Lipschitzness of R we have that
T
T (r()))) - R( Ba, (ac())))) caa. - B
T
T
R
al (x()))
R( 2 60ll
T
L
T
Bll
Σ
(ar(z)) - -5.)122
T
7 E1I
L
(or(xe) 86)1
(17)
where used Jensen's inequality with v for the last inequality.
denote by dz, the 1-th coordinate ő, for [d]. and similarly for deat. We have:
T
d
Σ -o.))
T
E
Σ (ar(x)) - 8:)1
By Equation [6). the sequence (x,( ) - Sr,1 is a Martingale difference sequence for the filtra- tion o ((0,, Crky : eit))e(t-1)) hit, C.k.). Hence, using that the expectation by the law of total expectation, we obtain that
27
T Var Σ [=1
T
E
Σ (a))((=)) -5,1)
(a),(())) 8,.11 =
Σ t=1
Varlar.(x:)) - 5,,]-
(18)
The terms (xz)) - 6r,1 are bounded in [-2, 2] by the assumption that [|a((r)]|2 S 1, therefore we can bound each of these variances by 4, for a total bound of 4T. Plugging this into Equation (17) concludes the proof.
E Proof of the main Theorem 3.1
The proof builds upon the proof used in the full information case (a, and fa are given) from Balseiro et al. (202T); Celli et al. (2022).
In order to bound the regret, upper bound the performance of OPT, and lower bound the performance of ALG. We proceed by first upper-bounding the optimum.
Recall that the convex conjugate Rt of R (which we consider as function from R2 R that is +oo outside of A) a function that associates to dual parameter À the quantity (A)::
(A)
max (r, >) R(7)} max (7, X) - R(7))-
7ER
YEA
The Fenchel-Moreau theorem, tells us that for proper convex function, the biconjugate is equal to the original function: R²*
Recall that is defined in Equation 5 We define the dual vector function D(A)
1), ,,,,),,,,,,,,... K)) which is vector representing the value of the dual conjugate problem.
For coordinate & E [K), it is defined
D(2,k) Elg(A, cuk, A)) R RC (A).
21

---

We denote the unit simplex of dimension K by Pk = f Th 20 E Th = 1/.
Lemma E.1. We have the following upper-bound for the offtine optimum:
OPT S T sup inf (T,, D(A)), TEPx AER
Proof. We upper bound the performance of OPT through Lagrangian relaxation using the convex conjugate of R, as was done similarly in Jenatton et al. (2016).
Let (k kr) E [K]² be the (deterministic) sequence of sources selected, and (TT E X2 the offline allocation. These x, are all (C1k) (Tkr)) measurable. We define = (((,,( cck,] and 6, = E., (x)( c.
Using Jensen's 's inequality for R convex we have
1
(((kkx) CIk):...,
(lfe(ae)) Pke Cik....., R
a (xt)) |ik).... cTkr]
T
< B[fe(xs) Pk. Ciki
cTkyl
TR(
au (x(2)) Cik).... crkrl)
T
Because the Te aCckk. (Tkr) measurable, and by independence of the (fr, at, Cti...., C.K) we have that (z)) oCcik....., = E,, (ar(rz) cxx,] = &g. With the same argument we
obtain that [(f((z)) (CCIk))... cn.)) Je(xz). Therefore
1
((((k CikI,..., S
f((x)) Pk. TR 5c).
(19)
We define the function L: c,, + (1())) - - (1, + TTR (A).
We now show that this function is always greater than the conditional expectation Ut:
L(k, C, x) 2 inf L(k, x,
XER
T
T
f((w.) Pke - T sup
(A,
Σ
5.)
-R* (*))
AER
T
t=1
1
Σ f((xs) Phe T
5z)
T 1=1
Σ fe(x..) Pk. -TR(
1
Σ kc)
T
> Eu x)) cRl]
(20)
the last equality results from applying Fenchel-Morent theorem, and the last inequality is obtained by using Equation (1)).
Let us now compute the max in (II, (CI,...,,7) IT) of L. Looking at the terms inside the sum, the only possible dependency of fi(zz) Pk, (X, 8e) to other contexts for t' is possible through the allocation zt, which can depend on the other contexts. Therefore the maximum of the sum the sum of the maximums. This yields that
max Lik, Cik,c,x,A (T))....T))))
Σ max (S((tt) - Pk. - ()))())))) ctk,) (A) EEEt
Σ
(p(), Caa k.) + R (A))..
22

---

Thus by taking the max in (#1...., on both sides of Equation (20) and then taking the expectation (which is over the contexts as everything measurable with respect to them), we obtain
B max (k, a:) C1R1) (111)))))))
eTkY] S
Σ Bla Ceky; ki) + [²)
Σ D(), (21) t=1
What is nice here, is that by looking at the dual problem which was originally address the non-separability in I, we also have the separability in kz-
We denote by Ta = Σi=1 1[k = k] the number of times source k is selected, and by á (Ti/T..... Tx/T) E Pk the selection proportions of each source over the T rounds. This vector of proportions can be seen as the empirical distribution of selected sources. We can rewrite in the following way the dual objective
T
Σ D(A,
= - TED(A,)) = 7 Nx D(, = (At, D(A))-
1=1
1=
Finally, using the previous equation with Equation 21 ka we can conclude:
taking first the inf in À and then the max in
OPT < T max inf (a, ((A)) S T sup inf (T, D(A)).
kr....rr AERd
*EPx AER
Remark. Note that the function ((A) is convex and lower semi-continuous (l.s.c.) (as the supremum of family of l.s.c. functions). In addition, (T. D(A) is concave and u.s.c. in by linearity, and Pk compact convex. Hence Sion's minimax theorem can be applied, and the sup is actually max.
We can now proceed to the rest of the proof of the main Theorem 3.1
Theorem E.2. For = L/ (iiiim)mAAA m = f + L + max: |pxl + 2n Diam (A), = Vlog( ())(K)/(TK))) and do aR(0), algorithm Algorithm ! Gass the following regret upper bound:
Reg < 2((L max|pp)) Klog(K)= Lvd + Diam (A)m(A))TTT + +2L K log(K)
Proof. We first lower bound the performance of the algorithm. Then we simply need to apply Lemma E. to get the regret bound. Let He the natural filtration generated by the (CrE, kir) (r()) Let Zt, k,, X and 7 defined in [ We denote by 8, = En, |a (z;) c= The quantity 6, in A because of the expectation and by convexity of A. Note that here these are all random variables, with Yt and A being H4-1 measurable and xe being H4 measurable.
To first get a broad picture on how we are going to lower bound the utility of the algorithm, let us decompose into different parts. It can be rewritten
T
T
1
E
f((1)) - Pk. TR
(x:)))
-E
f(() - Pk. - -R(7))
(22)
T
1=1
+
R(m) -TR( 1
Σ
61)
(23)
1=1
t=1
T
+ TR( 1
Σ 8z)
TT(
1 T
Σ ac (c(
(24)
The first line (Equation 22
corresponds to some adjusted separable rewards, and we bound by first reducing it to the virtual rewards so, and then using bandits algorithms techniques. The second line (Equation (23) corresponds the difference between the unfairness of the adjusted rewards, and the true unfairness, which is not big because of the gradient descent on A, Finally the last line (Equation (24)) corresponds to the difference between the penalty of the expected allocation and the expected penalty of the allocation, which we have already shown in Lemma 3.3 is bounded by (VT)).
23

---

Reduction of Equation (22) to a bandit problem with Using first the tower property of the conditional expectation, and then Equation (1)). we have that
[ = E (a) Hi] = E (E CeN,]l-
We add and remove (Xe, dt), and use that 2; is the allocation that yields the virtual reward function:
[l)f(r))) ph. EE [E c.a. -PE, (Aes de) + (Ae, 0,] = ()e Ceke ke) + (Ae, 6z)].
Using the definition of y as maximizer, we have
- -((+)) --((7)) (de, 71) (e) 7t) maax
{(),, 7) [(()) (des 7t)- 7ED::
Because A As, and, because R and R are equal over A recover lower bound with R"
max ((A,,7) - R(7)3 (Ae, 2 max (Me, 7) R(v)) - (Ae, m1) yEAs,
TEA
maxf (de, 2) - R(T)) - (Ar,7))
TEA
=R*(A.) (2)
Thus
E[f((1)) Pk. -R(%)) 2 Blp Cik, ko) (Ae) + (de, - 71)]-
(25)
Application of Bandits Algorithm Let be the distribution generated according to the algorithm. We actually have that ([(p(Ae, Ctk,) ) + RR" (Ae)] is just (through independence, measurability, and total expectation arguments) (T ((x)))] Hence the main idea is to apply Online Convex Optimization theorems to the linear rewards D with the decision variable T. (see Hazan (022),, Orabonal (2019) or Lattimore & Szepesvári 2020) for introductions to these types of problems). Here we don't t have access either to D(A.), nor even to D(A,, kx): we are in an adversarial bandit setting regarding the Åt, and also in stochastic setting regarding the expectation in D taken with respect to e;. Hence we use an unbiased estimator of the gradient D()+)) for the linear gain, which we will describe further down.
Notice that is crucial to able to deal with any sequence D(Ae), this is because these are neither independent nor related to martingales,
the 7, generated from a quite complicated Markov Chain with states (A₁, ct. Me, kt). Hence the outside expectation does not help us much, and we will face as losses (or here rewards) the random arbitrary sequence of the D().). We don't care about R (Ac) as it is H4-1 measurable.
Here the different arms of bandit problem correspond to different sources. Using the tower rule, we have
T
T
E
((e, Cik, kt) =
E
Blpp(rr Cik, ke) Ha-1]
To use results for adversarial bandits, the bandits rewards need to be bounded. By Lemma D.4 the virtual reward yp. and consequently its conditional expectation, is bounded by m := +
2n (A) max; |px|- Therefore E(yp(,,, czk, k) 14-1//m [-1, 1].
We now construct an unbiased estimator Flly((,, (A,, en k) He-1), which is the following importance weighted estimator:
(m (p Cak, k))
(p),, Ctk, k)) m -1(k, = k)
Tekk
This estimator is unbiased for the conditional expectation given H4-1. Indeed because Tek H4-1 measurable, and because l[k, k] and (p( cuk, k) are independent conditionally on H,-1
24

---

have:
1
( Cue
Ha-1]
[m(m p(>e, Cab. k)) k] H1-1)
Tikk
= m
Elm - cl cub. k) H k]] H4-1
Tik
Elmm (d)r; CeR. k) H1-1]
El Cek k) He-1],
which is exactly the reward needed.
We use the following Theorem 11.2 from Lattimore & Szepesvári (2020):
Theorem (EXP3 Regret Bound), Let X E [0, 1]Tx be the rewards of an adversarial bandit, then rumning EXP3 with with learning rate / loo(K)) (oT(K)/(TK)) and denoting kit the arm chosen at time t, achieves the following regret bound:
T
mnax
X
E L Xex, S 2
KEK
tm1
The fact that we can possibly have negative rewards instead in [0, 1] like requested in the theorem, just changes that the loss estimator used an intermediary is bounded by 2 instead of 1. Hence by selecting Vlog( //TK//// (TK,,, and using the importance weighted estimator (at,, Ct) we can use the EXP3 Theorem an apply the expectation obtaín the following regret bound:
E max AEE [E|
Elp(A,, Ca. R.) H4-111 E
p()e, Cek, k,)l s 2m TK log(K).
We know that any convex combination of the sum of the rewards of multiple sources is smaller than the sum of the rewards for the best source. Let us denote by (x") (x") the sequence of distributions that maximizes the dual objective Lemma E. We will use x² as convex combination, and taking the expectation over the regret bound we obtain:
T
K
T
(oe) Ctk, kx)
N E
Blyp(e,, Ca. k) He-1l - 2m /T log(K).
Moreover using that cea is independent of He-1 and that d H4-1 measurable we can deduce using the freezing Lemma that
E (5ee()e, Cek,
Cen, k) 7 R² (Xx) Ees (sp()e,, cas, k)] R² D(),, R).
Hence
T
K
T
D(Ae, k)] 2m / T log K)
T
t=1
D():)) 2m TK log(K)
inf (T" D(A)) 22m xER4
/ TK log(K)
Taking the limit in n + oo and by definition of x" we conclude that
E
((e,, ct..) (A.) T sup inf (T,, D(A)) 2m REPx XERd
/ TT log(K).
Using the above regret bound and Equation
25 we obtain
E
Σ f((x)) - Pk. -(())
T sup inf (TT, D(A)) -2m /TO/TKKK log(K) TP XER
E
Σ
(re 6 - 71)
(26)
25

---

Analysis of Equation 23 and dual gradient descent We will now compare TR(E==1 6,/T) and Σn= R(3:). Here consider modified version of R, which equal R over A and is equal +x outside of A, and will its convex conjugate Re (note that the convex conjugate of R without these modification would have been different !). Let
T (2))
À E arg max
(A,,
Σ t=1
6e)
AER
T
We have by the Fenchel-Moreau theorem that
R T Σ 5.)
-
R + Σ 6.) 6,) (2,
1
T Σ 8z)
(A).
By definition of the convex conjugate of R, for any 7 E R.d, thus in particular for all n. we have
R²*(A) 2 (2, m) - R(x))
Summing for every & [T] we obtain
TR (2) 2 Σ (8.70) R(w))
Hence
1
(A,
8z) TR
8.) >
(},7)) R(x))
T
t=1
T
(
mD 2
TR
8t)
Σ
R(x:).
Finally because R and R are equal A, and because inequality:
Σ
de/ E A, we derive the following
T
T
Σ R(x)) - TR
Σ
5.)
(2 7 -8))
(27)
We now would like to track the left-hand sum evaluated at the dual parameter Å. To do so we will use straightforward Online Gradient Descent on the linear function + (2, Tt. 52), with sub-gradients
T' Sr.
We will use Lemma 6.17 from Orabona (0119):
Theorem (Online Gradient Descent). For - de a sub- guab-gradiett of convex loss function le
with l|gella S G, for we generated according a gradient descent update with parameter TJ we have for any E Rd:
|ull2
Σ 4(we) (2))
+ TC.
2n
This is exactly our setting, and the way we update dç. Therefore
T
|
Σ (un 52) (i, 72 5,) S
2n + " TG2
Moreover, because Å is the arg max which yields the convex conjugate of R", we have e I TTT) 0 (Σ 5 T.) Because is L-Lipschitz for || 1|2, we have |lal|2 < L.
Hence
Des Vt be) - (2, 7: 8,) S
I,2 +
n TG.
2n
2
26

---

What do we lose by using R instead of R to generate in our gradient descent ? We have larger gradients bounds by factor in our case. Indeed instead having f Diam because "/t can be outside A, we have 7/ dell - 2 Diam(()) A). this case, choosing 7 = L/(2 Diam(A) is optimal, and yields the following regret bound:
T
(c. 7 6e) - 12,70 66) S 2L Diam (aaam(A)r (A)vT
(28)
Using both Equation 27 and Equation 28 yield:
T
T
Σ R(w) - TR(
2
2 1=1
(Ae, n 66) - -2 Diam () (
(29)
We can finally put everything together. Through the decomposition with Equations 22 to 24 using respectively Equations (26) and (29) and Lemma 3.3 for each of those differences and summing the inequalities, the terms in (Ae: Y òe) cancel out, and we obtain that
ALG 2 T sup inf (T, D()) 2m TK log(K) - 2T. Diam - =EPx AERd
By applying Lemma
E.1 we conclude that
Reg OPT ALG s [[[L+f+maxlpp) (ot K log(K).
The Importance of Randomizing Between Sources: OPT vs static-OPT
F1 Proof of Proposition 2.1
We can directly derive from the proof of Lemma E.1 and Algorithm the following proposition, which is rewriting of Proposition 2.1
Proposition. There are instances of the problem such that
static-OPT
OPT T
lim T-000
lim T-000
T
Proof.
What we have shown indirectly in the proof of Theorem 3.1 is that
IT max inf (T, D(A)) - OPT) S O(VT),
TEPR AER4
therefore +im OPT / +om max inf AE (M,, D(A)) which also gives sim- ple way to compute a close upper bound for OPT as a saddle point, instead of having to solve a combinatorial optimization problem.
Following the same arguments as in Lemma E. besides the last maximization step, we can also derive that
static- OPT S T max inf D(A, k)). kE(K] Aegd
It remains to find an example such that
max inf D(A,k) KE(K] AERa
< max inf (IT, D())). TEPx A
We used such an example in Appendix max infxeme D(A)) 0.25.
E22 where maxxe[K] inf D(A, 0 and
27

---

F.2 Simple example and numerical illustration
We illustrate Proposition 2.1 and give an example that shows that randomizing over the different sources can outperform the best performance achievable by single source.
We consider case where the utility u, E {-1, 1} and the protected attribute of a, {-1,1}
All combination of U4 and ar are equiprobable: PP( = u, dt a) = 11/4 for all u, E {-1,1) The penalty function is R(6) 5 There are K
sources of information. The first source capable identifying good indivduals group 1 gives a context <₃ = 1 when (ae, ", = (1, and 6r 0 otherwise. The second source does the same for good individuals of group 1: it gives C: = when (Gt, (e) = (-1, 1) and G2 = otherwise. In terms of conditional expectations, this translates into [[1=]]
Bla c21 C21 =1] 1] 1, E Ce1 -0] Elareer =0] -1/3 /3 for the first source; and E[[u, Ce2 C=2=1] = 1, Bla = - Beue/ = 1/33, Ela Ce2 00] = 1/3 for the second source.
We apply Algorithm to this example, and we compare its performance to (i) the one of an algorithm that has only access the first source (which is the best source since both sources symmetric),
(ii) greedy algorithm that only use the first source and selects 2t = 1 whenever E, Me cel 0, and (iki) the offline optimal bounds OPT and static-OPT. The results are presented in Figure [ We observe that our algorithm is close to OPT as shown in Theorem 3.1 It also vastly outperforms the algorithm that simply picks the best source, whose performance close static-OPT. The greedy has largely negative utility because it is unfair. Our randomizing algorithm picks an allocation Iy only when the context implies that u, algorithm that uses single source cannot be fair unless it chooses It = O, which is why OP0ic-OPT=O for this example. The 1s and 3rd quartiles are reported for multiple random seeds, the solid lines are the means. The computations were done on a laptop with an 77--05100 and 16 Gb of ram.
obtain fair allocation by switching sources. An
30000
Algorithm
Algorithm without source selection: k= or 2
25000
Greedy Algorithm
OPT
20000
static-OPT
Total Utility
15000
10000
5000
-5000
20000
40000
60000
80000
100000
Figure 1: Static source vs randomization: The red curve the total utility of Algorithm The blue the utility of Algorithm [ ran on the best-fixed source, and the green the utility of an unfair greedy algorithm. Black curves correspond the upper bounds T Tiimy (OPT /T) and similarly for static-OPT.
F.3 Additional experiments on the effect on OPT of sources and fairness prices
In the main body of the paper, we study how one able use the online algorithm Algorithm I so as to achieve a good total utility asymptotically close to that of the offline optimal OPT. However we only consider R and the prices Pt: the different sources as inputs for the algorithm, and we did not discuss how their variation actually affect the performance of OPT. While the previous illustrating example shows how mixture of sources may achieve strictly better performance, we now only focus on the static optimization problem and how various metrics may change vary R and pk.
28

---

We consider fairness penalty R(x) = r2² with r 2 0, and A [-1,1} so that ag can only be either- -1 or 1, encoding men and women for instance. We suppose that the protected attributes and the utility (ue, 0z) are distributed according to Pr(a; 1) Pr(e, -1) = 1/2 and We ~ M(a, 1). hence the group for which a = 1 is generally correlated to having better utilities than those for which 0; = -1 We suppose that there are no public context, and that there are K = 2 information sources, with 1t = (ar, ue) for source 1 associated with a price of p1 = p. and for source k- = 2 we can observe 22 = we with price of O. Here the sources are 'monotone' in that one contains strictly more information than the other, but is more expensive. Basically we are going to observe the utility u, in all cases, but before observing uh can pay p to additionally observe at- Note that when r = then R = O and there is no fairness penalty meaning that we don't t actually care about a and will always select source As 2, while when p 0 the information about a is free and there is no uncertainty.
Data model:
We study the asymptotic regime with T + oc, and compute the optimal solution of the offiine optimization problem through its dual problem. Figure 1 represent the quantities associated to the optimal solution for varying p and r: (top-left) x² the percentage of times information is bought (i.e., == is chosen), (top-right) the probability of group being selected Pr(a; = I₁ = 1), (bottom- left) the fairness cost relative to utility (etllaax)l//BBaale and (bottom-right) the information cost relative to utility pr" mE]
Analysis and interpretation:
(top-left) Looking the optimal action in terms of information (to buy the observation of at or not), we see that there are three regimes: x² = 1, '- = O and a transitive regime x² E (0, 1). When information (T* 0), this remains true as long as the cost of p is large over r. When = 0 there are costs to observe o and thus x¹ = 1 and this remains true as long as the fairness penalty r is large enough over p. In between, we may obtain optimal actions which are strictly between 0 and 1: in this case the best action is strict convex combination between the two sources and there is some trade-off between buying costly information and selecting an unfair allocation.
0 there is reason to care about ae, thus we simply do not buy
(top-right) Regarding the proportion of individuals of group 1 selected, we see that it is always higher than 0.5 as group a; = correlates to higher utility compared to group = 1. Therefore it is decreasing in r and goes towards the perfectly fair allocation 0.5 which would incur no penalty even for high r. It is also increasing in p as higher information costs make it less desirable to pay to observe dr. and thus more difficult to accurately achieve a fair allocation: the support of the utility uy conditioned on a = 1 and conditioned on a, = 1 are not disjoint, which makes it difficult only by observing u, to determine whether a- = 1 or 11
(bottom-left) For the relative fairness cost compared to utility, when the information cost p increases the allocation becomes more unfair as it becomes more difficult without access to a, to choose a fair allocation with good utility as describe above. Moreover the average utility u, of the selected groups tend to decrease as the individuals which are more likely to be a = -1 based on de have low utility. Therefore the ratio fairness penalty over expected utility tend to increase. When r' increases there are three conflicting effects: high r makes it more appealing to achieve a fair allocation at the cost of expected utility ue which makes the latter decrease, the expected group allocation becomes more fair as seen previously, and the scaling of R increases. When becomes high there is some balance between a fairer allocation and higher penalty, and when r = 0 the fairness penalty is clearly O. Overall for each fixed p there is some maximum in terms of fairness penalty relative to utility.
(bottom-right) Finally for the information cost relative to utility, it is increasing in Indeed due to large fairness penalties it is better to buy information thus π increases while p remains fixed, hence the product pa* increases. When p increases, we buy information less often (x decreases), and because pm = 0 for 0 or p large, there is some maximum for each fixed.
Overall, we see that higher fairness penalties tend to make it more likely to buy information and select fair allocation even at the cost of utility, while high information cost makes it unattractive to buy this information and can lead to unfairness due to the difficulty of identifying the protected attribute without this additional data.
29

---

Information selection: 77
Protected group allocation: Pr(a, = x 1) 0.62
33
0.84
6.7
8.
8.64
0.27
8:05
0.61 6.11 6.61 0.61
2.1 0.63 0.65 9.65 0.68 a.88 9.65 0.60
Faireess penalty coefficient:
0.90
0.76
0.63
0:53
0.36
0.18
0.8
Fairness penalty coefficient: r
2-0.22 6.62 0.82 6.44
0e6 0.65
0.8
0.69 0.7 6.7 0.
0080
0.86
0.75
2-0.88
0.88
0.77
0.4
0070
0
1.
0.72
6.72
0.8
0.84 0.84 0.84 0.84 0.84 0884 0.84 0.84 0.84 0.84
0.5
0.77
0.84 0.84 0.84
0.84 0.84 0.86 0.86 0.84 0.86 0.84 0.84 0.84
60
8 0.884 0:84 0.94 0.84 0.84 0.84 0.94 0.84 0.84 0.84 0.84 0.84 0.84
0.0 0.025 0.05 0.075 0.1 0.25 0.175 0.25 0.275 033
0.0
0.0 0.025 bs 0.075 o.1 0.25 0.150.1755 0.2 0.225 0.205 Information cost: p
Information cost: p
Relative fairness cost: R(s(axxx)ME(uxr)]
Relative total information cost: (pr \/[[ux]]]
35
0.08
0.98
0.08
0.08
0.1
0.12
9.13
0.18
0.21 0.27 0.28 0:88 028
0.05
0.1
0.15
0.17
0.18
0.21
0.17 0.12 0.03
0.200
3.
0.08
0.98
0.08
0.09
0.11
0.14
9.17
0.2 0.24 0.9
0.29
0.29 0.9
0.05
0.1
0.15
0.16
0.6
0.16
0.14
0.08
Faimess penalty coefficient:
Faimess penalty coefficient:
0.00
0.08
0.09
0.1
0.13
0.16
0.19
0.23
0.28
0.29
0.29
029 029
0.20
0.05
0.1
0.13
0.13
0.13
0.13
6.1 0.02
22
0.00
6.68
0.12 6.16
0.24 6.27
0.3 0.3 03
22
1..05
6.1
9.69
0.04
0.125
10
10
0.050
0.5
6.1
0.1
1
8.1
0.5
0.05
0.055
6.0
0,0
0.0 0.025 6.05 0.055
6.1 0125 0 0.175 62 0.225 0.25 0:275 0.3
0.0 0.025 0.65 0.075 611 0:225 0.15 0.2 0.225 0.25 0.275 0.3
Information cost: p
Information cost: p
Figure 2: For varying fairness scaling and information cost (top-left) optimal information purchase frequency π², (top-right) optimal probability of group selection Pr(a, 1| 1). (bottom-left) optimal fairness cost relative to utility R(B[a. [[]xx;), and (bottom-right) optimal information cost relative to utility pr") /B[upxz]
Here we looked a simple example try isolate how sensible is the optimal solution some variations on and Other parameters can lead to unfairness, such as unbalance in the protected group population where one would still need balanced allocation, penalty functions with varying convexity strength.
G
Other Fairness Penalty proof of Theorem 4.1
In this section, we consider an other type of faimess penalty as described Section 4.1 We redefine U(.) in the following way:
30

---

T -Vildt) pk.) - (E E
Σ E ae(Fe)
u(kx
(30)
Ei=1 Zt
When X' RR with 1, there two ways intuitively generalize this penalty for higher dimension allocations. We can replace Ei= Ia by Ei=Ei Pts. which is still a scalar and the proof follows directly. For instance, this corresponds for online bipartite matching with node arrival to fairesss condition on all online arriving nodes (it does not matter to which offline nodes they are matched), Otherwise we can instantiate n penalties Ri,... R. using >e Tti for each penalty Rù with E [n). This corresponds to fairness condition on the selected online nodes for each of the n offline node. This can be dealt with using one parameter X for each penalty RG For this proof will assume that n = without loss of generality.
We require the following technical assumption: (x I, E A for all Tr, a, and t. Of course, the size of A can be increased to guarantee- if possible that this quantity stays inside A, but with the trade-off that Diam ()) increases. Clearly, this assumption is verified for the special case of ar (2xx) az, for some A, the x E, Ie form convex combination.
Let us redefine the virtual reward associated to this other fairness penalty:
( Ctk. k)
max ([f((z) (Ae, (x)) cek] + xR (At)) Pk- #EX
We also redefine the unbiased estimator + with this new ş. We now Algorithm 3 There 4 differences with Algorithm 2 the function yp contains in addition x =R (A), 2; is the arg max with respect to this new virtual reward, is the arg max over A6,/2, instead of As,, and finally the update for Ac+1 uses 2 instead of ?/.
Algorithm 3 Online Fair Allocation with Source Selection Other fairness penalty
(1/K.... ..... 1/K), dual gradient descent step size EXP3 step size p. cumulative estimated rewards So = R² for f (T) do
Input: Initial dual parameter λo initial wawe--scccooooiirriiiooee
Draw source kg ~ nr, where (mt)a x (xp(pS((-1)a) and observe Ctk.-
Compute the allocation for user
arg max (B[f(ax) (Ne, (x))) Cak,) + xxx" (Ne)). xEx
(31)
Update the estimated rewards and sources distributions for all & E [K]:
S.k S + *pAe. Czk, he),
(32)
Compute the expected protected group allocation 6, = E(ar(1;) ) | CeRa, vx] and compute the dual protected groups allocation target and update the dual parameter:
Tt arg max ((x,7) R())},
7E
A4+1 = A -xenn% - 82/x1).
end for
Let us first prove upper bound OPT, which actually guides the design of the modified virtual reward i
Lemma G.1. We have the following upper-bound for the offline optimum:
OPT < T sup inf (T,, D(A)),
TEPx XER
where D(A) = 1). I).... D(A, K)) is vector representing the value of the dual conjugate problem, with [K] the coordinates
D(A, k) Ecss (i(A, ctk.
31

---

Proof.
The idea will be the same as in Lemma E.1 we only use a different lagrangian function.
We recall that the iy are (cikss--.. (tk.) measurable (because the hi deterministic). Let d₂ Ea, (ar(zz) cad. and (x()) = Ey, (ar())) caa.. Using Jensen's inequality for convex we have
-= (z(24)
(k, Ciky:...,
orkr (afe( Pke Cik,....... |Ib,...., EI{
3i R
OTkr
T
i=1 Tt
T
T
ar(z))
[l)f(a))) Pk. Cika CTKrl
3 BR)
|iki Orky]
2i=1 Ft
-1== 1= (r(21)
[[ff(ax)) Pk. CIk CTkrl
21) R
18
C1k eTkr
E It
t=1
t=1
E E 1=1 ae( Clk CTkr
Σ (x) Pk. CIk.............................
CTkyl
x1)R R
E 2t
Moreover by independence of the (fr, at Ctl..... ((K) we have that Bla, (2re) Eg, [ox(Tr)) | Gas, = 6,. This is basically an application of Lemma D.3 where we state it more
((C,,, Ctky )
carefully. With the same argument we obtain that (x(f( o((ck.
CTkr ) = f((x)). Therefore
21=1 8z 21=1 It
2)) cik)...., S
Σ f((a)) Pks 2
F R
(33)
1=1
We define the function L: (k, c, x, + Σt= fe(xz) - Pk. - xy (A, a.) + x, R (A).
Using the Fenchel- theorem, and the previous inequality we have
[(k, c. x,, inf A(),
AER
T
T Σ
f((x)) Pk. sup {(A,
Σ
x1)
((R((A))
XER
1=1
1=1
T
7 {(),
8
fa(ss) -h.
Tt
sup
-R"
t=1
AER
1=1 Zt
ΣT t=
8e
Σ Fe(ax) - -Ph.
2z R
Σ 21
T
|= 8z
T
= Σ f((x)) -pk.
21)
Σ Σ 24
1=1
2 Bu x> cxl.
(34)
We can then finish as we did for Lemma
We now proceed to the rest of the proof of Theorem 4.1
Theorem. For n = (2 Diam(A)/ii
m = f+ max |pal + 2m Diam (A) + m (m" is constant defined in the proof and depends A and Rt), p= Vlog(Kt /)/KK///// K Km, and do E dR(a)
for some a E A, algorithm Algorithm 7 modified as suggested in Section 4.1 has the following regret upper bound:
Reg < 2(( [ J max/pal + m²) Klog(K)+ + Lvd Diam A)) VT + 2L K log(K)
Proof. We present here only the parts that are different from the proof Theorem 3.1. and we refer to the corresponding proof for more details.
32

---

Comparison of performance with & By adding and removing -22 az) + I2 (Xc), and using that 24 is the maximizer that yields to we derive that
[xx) F (2Te ctR.] - (Ae; (Ae; de) + x1 (x)) xz. xr (Ar))
= El C.R,) + (Ae, 5z) - xIll" (A+))-
Because A C As. and, because Rt and I are equal over A we have:
R (Ne) = max 7) R())}
= max 7) R()}} YEA
I max {(Ax: 7) R(())
reda;
= (Ms, - R((+))
Thus
(x.) - Pk. 2, 2(1() 2 Elg cok.) + (2,,0 xmaMl.
(35)
Application of bandit algorithms Compared to the previous setting, the only change is that the function R is included in y, so we need to bound it as well. See Lemma D.5 This is where m" comes from.
Dual gradient descent Let us now focus in the tracking of the faimess parameter. the evaluation of our lower bound of the algorithm performance, we used R2,)( instead of the true penalty (E' 24 E() (x(2))/ Ei= ze). Because of small modification of Lemma 3.3 we only need to compare it with the penalty over the conditional expectation of a,2; Indeed, by the Lipschitz property of R, whether we re- ecale by T or Σ 24 does not change anything.
Hence will now compare those two penalties. Here we will consider a modified version of Rt which is equal to R over A and is equal to +00 outside of A, and will use its convex conjugate R (note that the convex conjugate of R without the modification would have been different !). Let
de Dt
Å E arg max (A. AER
R (*)))
We have by Fenchel-Moreau theorem that
Σ T
-= 52
Σ 8z
(1
(2)=
= R
Σ 1= 1
1= Ft.
1=1 81
= R
r=
1 Stt
Hence
T
T
-== 8c
T
(i,
8,)
R
(A).
21=1 Tt
F=1
By definition of the convex conjugate of R. for any 7 E Rd thus in particular for all n. we have
R (a) 2 ()) R(3e)
Multiplying by xe and summing for every 1 E [T] we obtain
T
R) (N)
Σ
A mm) -2,
1=1
Hence
T
T
T
-t= 6r
(A,
56)
3 R
>
(), mx31) - R((1))
1=1
1=1
Ft.
1=1
T
T
(A,
8, 24%) 2 Σ
R
Σ
x4 R(7)).
t=1
-
St
33

---

Finally because R and R are equal over A, and because Σ we have that
5e/
Ei=1
E A by the assumption,
T Σ 6
T
6x Ztml
T
R
Σ 24 R(H)
(36)
It
As we did earlier, we apply Online Gradient Descent to track the term evaluated Ả and obtain Equation (28). We just need make sure that before Î bounded. By the definition of A:
- 8t
-1=1 81
ΣT
6
OR
0R
OR
-1=1
E
21=1
21=1
Because is L-Lipschitz for || The rest of the proof is identical.
l12, we have ||²l12 - L.
H Learning u4 - proof of Proposition 4.2
We prove in this section the result regarding the added regret of learning wy. In terms of utility functions fi. protected attributes ae, and allocations I2. we go back to the setting of Section 2.1 with fa(z) = u. and X' = {0.1}.
In addition to the assumptions made in Section 4.2
we give more precision regarding the structure of 14. We define 0..- = [Ai k) the indicator variable of selecting source & at time t. We define the following filtration for all l E [K] and all E [
Fik o (x1, CI&, O1k, , Tt, Crk, Oik, We, 1,41, Cx4 1,8, 0,+1,
We assume that the contexts Cek. are now feature vectors of dimension gk, and that for all k E [K]. there exists some vector 2/a E 18 so that
= - (1/x, Cek);
(37)
a zero mean 1-subgaussian random variable conditionally on Ft-1,A-
Consider that each source A corresponds to one bandit problem, with action set at time & composed of two contextual actions (crx01x22 x E X} = {crKOek, 0}. and a reward u,z,00k. If Ozk = then the action selected is 0, and the new reward is 0. which means both are "observed". If Oex 1, then the feedback is un if 22 = 1, and otherwise. Regardless of the source selected, the feedback received and the action producing this feedback are observed for all arms in parallel. This is akin artificially playing all the [K] bandits in simultancously. This new reward still follows the conditional linearity assumption, and Ou is still F.-1,e conditionally I-subgaussian.
With these rewards and actions, we can define for each source vie and Vy the least squares estimator and the design matrix as done in Equations (19.5) and (19.6) Lattimore & Szepesvári (2020). Let 8 e (0, 1). We define the confidence set parameter (8 as
:))
to
VB. = 10 +
2 2
+ max Ok log kk
1+
(38)
max 9k
This parameter is independent of k. this will make the computations easier later on. We now define the ellipsoid confidence set of thy as
Ie (v R
Il Sra V S B.).
(39)
Algorithm iss modified in the following way. For each time t, let Ha arg max (b))))). We now select 24 using this optimistic estimate of vha
= arg max x (Vrr cat) (Ae, 2.))
(40)
=e (0.1)
34

---

Proposition. Given the above assumptions, the added regret of having to learn E[u, coal is of order OVVKT log(
The proof will proceed follows: we first highlight where the learning will impact the algorithm, leverage the concentration results from (Abbasi-yadkori et al. (2011) to decompose into a good event and bad event, and finally bound the loss over the good event.
Let us now analyze the main part of the proof in Appendix [ that is modified, which is "Comparison of performance with yp" because the only change is the quantity that 2; maximizes. Let æ be the maximizer obtained by replacing the optimistic estimate with the true parameter thk. Let â Ela, c.k.). Because 2, maximizes the quantity with the optimistic estimate we have
ry B,Blus cck. - xe ā.) = Iz (e C(k.) Ie ()e, ãe)
re((Kkk C(k,) (Week (ui))) DelWeeer Caki) ((kk - I (2e,
2 Ie (t'r. Vekes Cck.) + z (Viese Ctk.) - xi (A:;
Iy (Wkk, VeAro Cek.) + 27 (Wek 1Kk C(ki + 1/ (1ite Ceke) x2 (De, ae)
recik Weeee Cea.) + 27 (Deek Lkk. Ceke) (p(ee Cake ki.) + Pks
The last term O is the one we want, we now need to lower bound the first two terms.
By Theorem 20.5 of Lattimore & Szepesvári 2020), we know with probability at least 1 - 5 that Q/k E Iak for all t. By union bound, the probability that the tha are simultaneously all in their confidence set is at least 1 - K6. We denote this event by I.
Suppose that the event / is satisfied. Then by definition of thak, we have
2i (UiRa - thh,, Cok,) 2 0.
Now let us look at the last term. We first decompose it over the K sources:
K
(ee s/Ak, Ctke)
Σ O - Vin, cek)
Σ
(th
The, Oux.)ee))
k=
k=1
Now, consider one source k, and sum the difference term for every t. By remarking that Ocn 02 we have that
T
1e/2 - Ven (exx1CC))
Oell(tha (s/n - Ven 1exarceull
T
Osk 0
(dual-norm inequality)
Osh v B.l
(by the event /)
< Σ Orh v Br max 1000
(3, are increasing)
T
T
$ Br
02
max (1, (1. = } (C.S. inequality)
-=1
T
2v BT
Ozk
max (1, 10 }
T
22 Tk
max (1, 100.r. -
where Ty is the number of times source k is selected.
35

---

By Lemma 19.4 of Lattimore & Szepesvári 2020), we have that
Te
Σ
max |1 v } = 2qp log
1+
9k
Therefore, using Jensen inequality for the square root function which is concave over the Tk. and because >x Th = T, we obtain
T
K
Tc²
ΣΣ
1 Eee 0010raa
Σ
2
Br
Th
2gh log
1
9k
K
Tr²
I 22 Br
Tk
29h log
1
qb:
km 1
Te
3T
2k log
1
9k
This yields a O(v KT (()))) error.
And with probability at most K8 the concentration event / does not hold, but the error is bounded by for each Thus overall in expectation, it is bounded by KT. Picking 1/T, yields the desired sub-linear regret bound.
I Learning at
In this section, we provide further intuitions on the existence of [K] different sources, and how it is possible to adapt the algorithm to learn Ela, csk] on the fly. Let us consider the special case of our model, where the additional information given by each source is noisy observation öu of a,, with different noise levels; the main setting this can described as Cak (zt, âex). Sources with lower noise levels will have higher prices (one directly pays for the level of accuracy). This setting can be used to give users the level of privacy they are willing to give up (as in Local Differential Privacy (Dwork & Roth Roth (0144), by revealing some noisy information about their private data; of course, the more data is revealed (or the smaller the noise), the higher the compensation (the price).
Furthermore, if the source k corresponds to adding additive independent noise Lik and to returning âe = a, + Lik- then knowing the law of both Lu and a,, the decision maker can directly compute the conditional expectation of a, having observed âek- Nevertheless, if she only knows the noise distribution, but the law of a,, conditional expectation can still be learned in an online fashion in some cases.
Indeed, suppose for simplicity that a 1), Pr(a, = 1) = (0, (zt, u.) independent of a, (therefore we can focus only in dealing with az), and that the Lex are 0 mean sub-exponential random variables (see 2.7.5 Vershynin 2018)). We define the following running empirical estimate of a:
â
(ārk. +1/22.
T=1
It is unbiased estimator of
Elaa = E[a:] + E E(Lax] = 2a 10 1+0 2a 1.
Note that the ag are not independent, and the conditional expectation is not cispchit--onntnuuuu with respect to the parameter a. Still, we can derive an algorithm with sub-linear regret bound.
First let us state a Lemma on the concentration of ò Lemma I.1. We have the following concentration bound for Z log(T):
k2 log(T)
2
Pr
|dy - al 2
<
(41)
ct
T
36

---

Proof. We refer to Chapter of Vershynin (2018) for concentration results of sum of independent random variables. Let us recall some definitions, properties, and concentration inequality.
Let us consider the following Orlicz space norm for random variables. For a random variable X, we define
| infit > 0, ((/00((X)/0] s 2}.
If || i is finite, then X is called sub- sub-exponential. in [-,,1) we have | 12) (see exercise 2.5.7, example 2.5.8, and Lemma 2.7.6 of Vershynin (2018)). Hence because (a, + 1)/2 a E [-a, 1 - a) C [-1, 1J. for des the estimate obtained by always choosing source k, we have by triangle inequality that
a norm, and for a bounded variable X
|| ally S
+ Ok
log(2)
We now recall Bernstein's 's inequality:
Theorem (Theorem 2.8.1 of Vershynin 2018)). Let X,...., XN be N independent, mean 0, sub- exponential random variables, with max; [ Then for >> 0 constant, for every t 0 we have
N
NR.² - )
Pr
X
< 2 l
2 2exp
-emin
We want to apply this Theorem to (ōr,ks + 1)/2 - a the centered å, where we now change the source depending on kr. Remark that now however the â, is not sum of independent variables anymore because of k; which does depend on the previous realizations of the âz, Nevertheless it is martingale difference for the filtration Hg, and similar results will apply. We denote by 1/ 12g(2) + max; 02/2 an upper bound on the sub-exponential norm of the centered â conditional on H4-1- Then the martingale Σ â, a is also sub-exponential random variable.
This is a known result, which is stated here for completeness, but that can otherwise be skipped. Indeed from proposition 2.7.1 part e) of Vershnnnnn (2018), we know that finite sub-exponential norm for centered random variable X means that the moment generating function of X at y bounded by exp(ci [ Il 8²) for S X2/ with and C2 some positive constants.
Therefore, for y S c2/K, using the property of the conditional sub-exponentiality of âe, we have
Elexp(y Σ(á, (a, aa)] BB::EEEeee ExEepxp Σ (ār a)) Fr-1]]
Ejexp(y
(ār a)) E/xpp((() - a)) Fi-il]
$ Elexp(y
Σ 7=1
(a, [(xxp((c))))) F(-I]..
Iterating this inequality we obtain for y S 02/ that
Ejexp(y Σ (a, - a))] < Elexp(citx?
This yields inequality (2.24) in Vershynin (201)) the main element needed for the proof of Bernstein's 's Inequality. Thus Bernstein's inequality still holds for centered martingale sequence which are conditionally sub-exponential. We stress that this is not new concentration inequality result.
37

---

Let us now apply Bernstein's 's Inequality with deviation of order VR² (og(T)/((t)) fort 2 log(T)/c
x² <²
k²t
lāt- - al 2
Pr
Σ ==1
(ā, - -a)l
cl
c
log(T))
log(T)t
< 2 exp
-emin
2
Proposition I.2. Given these assumptions, using Algorithm with âg instead of a to compute the conditional expectations yields an added regret of order ( σk + 2 log(2)) vT log(T)).
Proof. There are two parts of the proof of Theorem 3.1 that need to modify, when the is involved, and when we compare the penalty. We will deal with the first part (the more complicated), and the second one follows immediately by the first highlight where the learning error occurs, then use the concentration result to decompose the error under good and bad event, and finally show that under the good event the error in expectation is small enough.
arguments. This will be done in steps:
Impact of learning error We suppose for simplicity that Luk has density over the support R, but this also holds for discrete random variables. We denote by ui the density of âtk. First let us express de = Ela Caa, as a function of åz = à and a:
Bla; âr.k. = â] Pr(a: = âc = Q) - Pr(a; = -1 âz = a)
Pr(a, = 1)gk,( (a - 1) Pr(at = - 1))g,, (a 1)
Vkg (a)
VR, (a)
ogg, (ā 1) - (1 -a)gk, (a +
agk, (â - 1) + (1 -a)gk, (a + 1)"
Let us define the plug-in estimate of ä, using u,-1 whenever a; is in [0, 1] by:
09-1 (ā 1) (1 -4-0 1)kk, (2 + 1) ā (a- 1) (1 04-1 (a + 1)
(()))
(42)
When the estimated parameter not [0, 1), we use 8, 0.
We define by 2, the maximisation of the virtual value function when replacing âe by st, and by nf the allocation obtained if were actually use ăz. Because 2; is maximizer of u,æ (De st we have
u ue3 (de, st) (de, s1)2,
2 u - (Ae, 8t) + (De, 8t) s0>e, dz, ke) + (Ne, ãt st)at (A,,
The term ()e; s, will be tracked with the help of the OGD, it remains to take care of (Ae, ār 8t)a By Cauchy Schwartz:
1(),, ā. st)=71 < || sel/2.
We know that Xa is already bounded, we only need bound the right- hand term. Decomposing depending on the values of k,, we can rewrite
St 0
1lk
k:(ss Ela. (xx)))
k=1
38

---

Decomposition under good and bad event Denote by Ct [| -a I (n² log the event of å concentrating around its mean. For large enough, that is to say 2 (K² log(T))/(emin((( 1 - a)). the event C, is included in [ā=-1 (0, 1)]. We can then decompose the analysis over these events using the triangle inequality: | S Cc-1 0e + c, 8 ue).
and we know that for the term multiplied by lc.,, we have that either is or 0; E [0, 1]. Let us consider such / 1 big enough, and first analyze the left-hand term with the "good" event.
Small error under good event in expectation We consider the conditional expectation of this sum given k,, and â;-1. By independence between (k,, ā E) and āz for all k, we have:
B| 1st
āel kr, ār-1)
K
1[ke ki] /
0 1gh 1) (1 1 +
agx(ā 1) - (1 a)gx( + 1)
1c..
Σ
Cg-1gh 1) + ar- 1)g + agn (ā + a)gx (a + vx(ā)dā.
k=1
Because Vk, (a) (aga - 1) a)ga(( + 1)) we can simplify the integral:
Ia 1)gx(a +
ax-1 & 1 c.-1
Σ
[kg = kl 2 -al
dá.
0 (a 1) (1 dz-1) (ā 1)
k=1
For E [0, 1), we have the following inequality:
ry az + - a1 max((x,)) S x
Thus using this inequality and the fact that It is density (which sums we obtain that
K
ga(ā + 1)dā + / ga - 1)dā)
B[Lc,-, 1sc ãel kr, ār-1] s 21c, 1all.--/a;-11- - a
lkk
k=1
41 Alc._ |a a
Σ
1 [kk k]
k=1
(T)
K
I 41 c(t 1) k=1
1 [ks = 1s).
Finally taking the full expectation yields
x2 log() c(t - 1]
E[Lc._, 1s, arll s $V
For the complementary event C,-1:
4
B[1g [s à.ll $ 2E 1g,
T
39

---

Putting everything back together Lemma
Now denoting by my the upper bound over the X obtained by
3.2 and summing over all
T
T
E
(Ac. ae s1)2;و1 & ma
Ells - ōell
x² log(T)
2m2
emin(a, 1 a) + +ma
Σ
Elis ā. |]
R lox(7)
2m2
cmin(a,1 a- +mx
x² log(())
E
(4 x² log(T))
4 + T
c(t - 1)
2 TT
n (og(())
log(T)
4
2m emin a, aa)
+ mA
(41
+
ct
T
x² lTg
< max
RT (T) + 2
emin(a, a)) + +4) O(vTToogT))
where we used a series-integral comparison of + 1/ve for the second last inequality.
There is second place where replacing 0e by 8, impacts the performance of the algorithm. Indeed, through the gradient descent on Åe, we will have a penalty converging towards R(E /T2:/T) and not R R 1=1 " This is because the Online Gradient Descent for the X uses s, and not a Nevertheless, because of the Lipschitz property of R:
T <
E 1==1 deTt
R
-1=
S
Σ
Bla sill ((VTTlogTT))
T
1=1
where the last inequality is obtained by similar manipulations on C. what we just did.
Overall, the added regret when using instead of ä, is of order (oogg(T) which still guarantees sub-linear regret.
Another algorithm is possible: first sample the source with the lowest sub-exponential constant T2/3 log(T) times, and then use the estimate obtained to compute (without updating it with the newest noise received). The advantage is that even though we incur 2/2 regret (this can be shown using basically the same methods), we can obtain lower k. Hence if there is big difference between the sub-exponential constant of the different sources, or even one source with infinite sub-exponential constant, this may be a viable algorithm.
J Public Contexts
For this section and order to make the dependence in the public context 2n appear more clearly, suppose that eæ represent only the additional information of the source k. and thus (Cak, 21) represent the whole information available at time / after selecting a source.
J.1 Finite number of Contexts proof of Proposition 3.4
We propose the following Algorithm
Proposition. For μ the probability distribution over Z finite, we can derive an algorithm that has a modified regret of order O( O(VTK log(K) Exez / vu(=]), where μ(z)) the probability that the public altribute is
Proof. Most of the proof consists identical to the proof of Theorem 3.1 and only the different parts will be highlighted, which is the upper bound of OPT, and applying bandits algorithms.
40

---

Algorithm 4 Online Fair Allocation with Source Selection With public contexts
Input: Initial dual parameter Ao, initial souree-slectoon-diiiibbiion To(2) (1/K,... ...., 1/K), dual gradient descent step size EXP3 step size pz(z) that uses doubling trick, cumulative estimated rewards Su(z) E Rx for all 2 E Z. for E [T] do
Observe 2, E Z
Draw source Kt ~ Ie (zt), where Tek x exp(o((21))(-1))(()) and observe Coke. Compute the allocation for user
St arg max Blf((z) (A,, (x()) Cekes 2].
aEx
Update the estimated rewards sum and sources distributions for all is E [K]:
Su(=)) (,-1,( (Ae, Ock: ke, zt); Sax() = (,-), V2 2 fzt)
Compute the expected protected group allocation 6, = E(a,(<)) Ctk, 2t, aie and compute the dual protected groups allocation target and update the dual parameter:
The arg max (Ae, R(7)),
7EAs,
A211 Ar 77 61).
end for
We first upper bound the performance of OPT. For all é let h4 [K]² be the deterministic source selection policies, k h2(2) the selected sources, I₁ X' be (2t, Ct,k,) measurable, and À Hd be a dual variable. In an identical manner to Equation (20) we can obtain the following inequality:
T
max (1(( kt) | 21, Ci,k1 TT, CT XEXT
max (f(( (e),)((x))) ze: Cak, Pkk +TR" (A). XEX
Pk.
Let us define *(A, Ctk k 2) = maxxEx (z) (A, at (xx)) 2, cual Pk. and ux=) Pr(z: = 2). We also define (=)))= = Σt= [1+(2) = k the total number of times we would have selected source for the public context
We now take the expectation of the sum. We obtain by tower property of the conditional expectation, and using the i.i.d. assumption:
T
Σ Blsa(A, (eN,A,,C,,()) 21)1 = Σ c(, =]]
Elep(A, h,()),,, |=)(() [=]((=)
sE2
T
Blp(A,, c, hx(2), =]](())
2E2 tml
Σ
Σ
cl ==][())
RE(R]
T
Σ
Σ
(x(x)).lp(A, =][(z)).
ZEZ [E[K]
Clearly (x)2) Pk, thus if we maximize over this space for the (2))) instead of over ([K})TT,) will be higher. Therefore
OPT T sup inf TEPE AERd
R*(A)+
Σ Σ
(e(,)).l((A,,, 12]x(2)
(43)
2 KE[K]
41

---

Notice that μu2) plays important role in determining the optimal policy. If we had sim- ply run the previous algorithm for each context, this would be akin considering that the 2, are distributed uniformly according to juz) = 1/7, which would have yielded a sub-optimal policy m.
Now let us take care of the lower bound. As done in Equation 25 we have that
((f((x+)= Pk. R())) 2 Elp kr ze, Ctk.) R² (Ae) + (de, de 7))s
and as did before we will bandits algorithm these rewards.
We would now like to bound the following adversarial contextual bandit problem regret:
Reg-
Σ
max KE[K]
El Cr k, H ze]
Σ Blpp(Ae, ki, ze) He-1,
The weighted estimator & is unbiased as cpAr, cr, kr, 1e) = (T/ (z+) 2)) is still unbiased. Indeed, Or and ki are conditionally independent given (z:: He-1), and Ten (2+) is (ze: He-1) measurable. Thus
(o(,,, ca, ke, 21 ) H1-1. 21]
El or kr, 2)) = Ai] H4 24-1,21
E
(za)
(ze)
El Ce kiz 21) H 21 21 [hi = k) H4-1, 2x]
(11(21)
Elep(de, ct2 ke 21) 14-1, 2t].
As suggested section (18.1) Lattimore & Szepesvári (020)) running one anytime version of EX P3 (using a doubling trick for instance) each of these public contexts E 2, achieves regret bound
of order (V K log(K) Exez V ETT 1[2 = =]).
Taking the expectation (for 2;) of this regret bound, and using Jensen's inequality for the square root function we have a regret term of order
B[O(yKlon Klg(K) Σ 2EZ
Σ [E[T]
1[2 21)1 O(V K (K)
Σ
E
1 1
=1])
ZEZ
[E
0 (Kllg(()) K
m(=)).
(44)
#E2
Let (T") E (P be the sequence of contextual source mixing that maximizes the upper bound for OPT Equation (3). Then because the maximum of [K] points is greater than any convex combination, T" (2) in particular, we have
Σ 262
Σ KE[K]
max
Cl, H4-1, 2
Σ (2) Σ Els(Ar, He-1,
ZEZ kE[K]
T((x) c, He-1,
kE(K] 1=1
In expectation this yields:
E
max
Σ
Elp(de, H4-1,
2|] El Σ
Σ
H(e,) c, He-1,
KE[K]
2E2
kE[K]]
t=1
Σ
Σ
EEE c, 21) H4-1, 21] H4-1ll,
kE| t=1
where we used the linearity of the expectation, and the tower property of expectation for the last equality.
42

---

Because and 74 are independent, we can first use Lemma D.3 and then the freezing lemma to express the conditional expectation given H
(x) 14-1,, zr]
Hi I]] = E|
H4-1]
= E
Σ
2EZ
Hence,
T
Σ
max kE[K]
Gl k,,, H4-1;
=]]
E
Σ
Σ
=]]
REZ
1=1
KE[K] ZE2
Grouping together with the R (de) terms, and taking the inf over À derive that
T
E
Σ
(²()a))
+ Σ
max
Σ
Ci, k, H4-1,
kEIK
1=1
ZE
2r
E
inl AERd
+ E Σ
[=]
t=1
kE[K] #E2
T inf XER
(*)++++ E (M
KE[K] 2E
As 0o and by definition of π²", we conclude that
T
T Σ
E
(Ac)
+ Σ
max
(lepAee cc. ki He-1,2)
KE(K
ZEZ
T sup inf =EP AgRd
R*(A)+
Σ
Σ
(,,)), 12)((22 2))(22)
RE
2 OPT.
Finally, using Equation and the previous inequality we obtain
E
(, 2,) R*))))) 2 OPT OPTT-O(VKlogg log(K) K)
vi(=)).
(45)
The rest of the proof follows Appendix
E
Clearly, if μ has non-zero probability only for one recover the previous regret bound without public information.
J.2 Infinite number contexts - proof Proposition 3.5
Lemma. Ex) Cuk, ze] and Elf((z) Cuk. zı] are Lipschitz continuous in z with respective constants La and L for all X with respect to ||,, then so yp in with Lipschitz constant La + Lg.
Proof. Let A E Rd E [K], Cik the additional information, 21 E Z, and Tz, I2 E X be the maximizers that respectively yields pdA, cub, h. 21) and ( cek. k. 22). Because 22 is a maximizer, we have that
(a),, Ceky k 21) (((,, Crk, 22)
< B[f((a)) | Cik, 21] - (x)) Cek. 21] + (A Ela,(x1) Cak, 22] - E(((((1) Cak, 22])
< 1 =a|12 L. Lalla (2) )l 22112
< L + La.
Using the same arguments because T; is maximizer, obtain the symmetric inequality.
43

---

The main idea for the discretization (that averages the rewards over the discretized bins), is that the performance of the algorithm is close the discretized optimal, which itself is close to the continuous optimal for smoothness reasons. However here the discretization is applied not to the original total utility U1 but instead to the bandits reward part. The number of discretized bins is then tuned depending on the lipschitz constants and the space dimension r.
The proof of the proposition Proposition 3.5 then directly follows from exercise 19.5 of Lattimore & Szepesvári 2020) applied to the contextual bandit problem with rewards 4.
Remark. In the case when 2 is continuous, there are guarantees that there exists an optimal policy π². Indeed, if for the product topology the space P is compact (by Tychonoff's theorem), the dual function used to derive OPT is not continuous. Vice versa, for topology which makes this dual function continuous, it unlikely for this space of functions to be compact. Hence why we need to take maximizing sequence of The so that the dual function of these converges to the upper bound of OPT.
44


Reviews:
[{"review_id": "M7vqZ62HzG", "reviewer": "Reviewer_2Yz9", "summary": "This paper studies the problem of online resource allocation with long-term fairness constraints. Different from mainstream literature, the authors assume that the fairness context is not known to the player in advance. However, the player does have the option of paying to buy fairness context information from different sources to make more fair decisions. The algorithms consists of two parts, the first part focuses on source selection for buying protected fairness information and the second part focuses on the allocation decision. The regret of the proposed algorithm is analyzed and it is shown that it is $O(\\sqrt(T))$. Last, there are some additional discussions and results regarding some other notions of fairness. ", "questions": "see above.", "limitations": "n/a", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "++ It is interesting that the authors consider the setting where protected attributes (such as demographics) are unknown to the online decision maker, but the decision maker should still be fair. It makes sense that prior works on fair allocation would only consider the case where these are known, but the reviewer is not familiar enough with the literature to know whether that’s true. \n\n++ The assumption that a user’s protected attributes can be estimated from the online context and/or additional data which is purchased is an interesting addition to the setting. \n\n++   It’s nice that it can model multiple notions of fairness as discussed in the last section of the paper. ", "weaknesses": "-- The fairness in their setting is a penalty rather than a hard constraint. This should be clarified since the claim of long-term hard fairness constraints is mentioned multiple times in the paper. \n\n-- I was expecting to see more discussion about the trade-off between paying for additional information and paying for fairness — i.e., when fairness doesn’t cost much, how does that impact the allocation? Maybe the regret bounds still hold in either case, but it doesn’t tell us qualitatively how the algorithm actually creates fair allocations. Especially since this “trade-off” is explicitly mentioned in the title of the paper…\n\n\n-- The assumption that users are drawn i.i.d. from a probability distribution enables this second assumption that the conditional expectation of protected attributes given context is known (learned from past data). However, in practice, past data is often unfair, which means I think these estimates may be inaccurate, particularly for underrepresented groups, and that intuitively should impact fairness here. It seems that there is no discussion of distribution shift or, in general an acknowledgment that the past data might exhibit this property. They do mention in the conclusion that the estimate of protected attributes could be learned online.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for this review!\n\n– **Fairness Penalty**: We do mention that we consider a fairness penalty and not a hard constraint in the abstract and in the model (e.g., lines 1,5,10 and 119), but we will make it clearer by also mentioning it in the introduction. We feel that the confusion may have come from the mention of constraints. Here, we mean *soft* constraints, but we see how that can be misunderstood, and will correct this.\n\n– **Trade-off and fair allocations**:  The main goal of the paper is to study online algorithms that can handle the decision trade-off between fairness and the quality of various sources with missing information, and then analyze the value of our algorithm compared to optimal offline value (i.e., the regret). The trade-off is done ``automatically’’ in the algorithm through the use of the virtual value $\\varphi$ and dual fairness parameter $\\lambda$, which can be thought of as a fairness price. Indeed, the regret bound in our algorithm holds regardless of the magnitude of $R$ (which models the cost of fairness); but note that the regret bound depends on $R$ through its Lipschitz constant $L$---so, for instance, if $R$ is divided by $10$, then so is $L$ and so is the term related to fairness in the regret bound. \n\n Analyzing how the problem parameters impact the optimal solution for source selection and allocation is definitely another interesting problem, but more of an offline one since the optimal solution comes from the static part of the problem. This was not the focus of our work and a detailed analysis is out of the scope of this paper. Nonetheless, there is a (barebone) example in Figure 1 section F.2 in the Appendix showing an optimal solution. Additionally, we made numerical simulations in a simple case showing how the optimal allocation and other quantities vary as we vary some parameters. We refer the reviewer to the global response and the PDF attached to it for details about this simulation.\n\n– **The last comment of the reviewer contains two points, which we address separately**:\\\n**i.i.d inputs assumption**: Concerning the stationarity of the distribution, it is true that there could be a distribution shift but this shift can reasonably be neglected in some applications. This is the case for instance of advertising: ad campaigns are conducted over a short time period (but still for a large number of ads $T$), and consumer habits are unlikely to widely vary. We will add this comment near the i.i.d assumption. \n\n**Estimates of protected attributes**: Concerning the accuracy of the estimates, there are two quantities of interest, $a_t$ and $u_t$. For $u_t$, because this utility is specific to the decision maker (for instance in the advertising example, how much money categories of individuals are likely to spend), it is indeed more likely for this quantity to be biased. For this reason we showed in Section $4.2$ how under some structural assumptions these estimates can be learned in an online fashion. Concerning the protected attributes $a_t$, as it is usually some kind of demographic (age, wealth, gender) not depending on the decision-maker, it is more likely to be correctly captured by historical data and thus can be accurately estimated using this information (see discussion line 379). Still, we showed in Appendix I (indeed mentioned in the conclusion) how under some simplifying assumptions the estimates of $a_t$ can also be learned online. Other structural assumptions such as a logistic or linear structure on the $a_t$ are possible and should lead to a similar analysis as done in Section $4.2$. \n\nHowever we do agree that there could be decision makers using wrong or biased estimates (that they think are accurate), hence we will highlight more those two assumptions (iid and accurate estimates) in the model section. A very interesting question that the reviewer leads to would be to quantify how a decision maker using a priori biased estimates could impact the fairness of the allocation and the performance of the algorithm, which might be a natural next step. Here we mostly focused in this work on the (online) decision making aspect of using those estimates. \n\n\nWe hope to have clearly addressed all your concerns and are happy to discuss further during the discussion period.\n"}, {"review_id": "CoQsvJcr8n", "reviewer": "Reviewer_Gv3t", "summary": "This paper studies an online allocation problem with long-term fairness constraints where, unlike prior works, the protected attributes of online users (e.g., gender, ethnicity) are not observed, but they can be purchased from $K$ different sources for some additional cost. The goal is to maximize the overall utility of the users minus the cost of additional information that was bought minus a fairness penalty that is characterized by a convex function $R(\\cdot)$. The authors study this problem under an i.i.d. assumption on the users and propose Algorithm 1 with sublinear regret for the problem.", "questions": "- Can you provide a few motivating applications that could be cast into your framework and explain what data sources are and how they relate to each other?\n- Can you explain the connection between $a_t$, $z_t$, and $c_{tk_t}$ in the context of a motivating application? How do these quantities relate to each other? What is the dimension of each quantity? How is $\\mathbb{E}[a_t|c_{tk_t}]$ estimated?\n- Assuming that $\\sum_{t}x_t>0$, the function $(\\sum_t x_t)R(\\frac{\\sum_t a_tx_t}{\\sum_t x_t})$ is simply the perspective of the convex function $R(\\cdot)$ and therefore, it should be convex in $x=(x_1,\\dots,x_T)$. However, on lines 329-330, it is claimed that the opposite is true. Can you explain why convexity doesn't hold?\n- Is it possible to use Algorithm 1 to obtain results for the adversarial setting? What would be the main challenges?\n- On line 131, why is $c_{tk}$ enough to estimate $u_t$ and $a_t$? How about the public context information $z_t$, is it not helpful for estimation?\n\n\n--------------------------------\nI've read the authors' rebuttal, thanks for addressing my questions and concerns.", "limitations": "Discussion of potential negative societal impact is not necessary.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Addressing fairness constraints in online allocation is a very well-motivated problem and the authors' assumption that protected attributes are not observed is a more realistic model of the applications. Therefore, the contributions of this work are of potential interest to a wide audience.\n- Simultaneous source selection and dual gradient descent in Algorithm 1 is an important contribution that shows the naive approach of performing these two tasks separately is not good enough for this problem.\n- The proposed algorithm is compatible with various notions of group fairness.", "weaknesses": "- The problem setup is a bit confusing. I'm not sure how the public context $z_t$, protected attributes $a_t$, and the purchased piece of information $c_{tk_t}$ are related to each other. On line 152, the authors make the assumption that $c_{tk_t}$ contains $z_t$ and I'm not quite sure if I understand what that means.\n- The authors have distinguished their paper from prior works based on the fact that protected attributes are not observed and could only be purchased. However, a comparison of the paper with prior works in terms of techniques and proof ideas is missing. It appears that both primal and dual updates in Algorithm 1 are quite standard and the main challenge is to combine these two steps. This point needs to be highlighted and clarified.\n- Given the vagueness of the problem framework, explaining the setting in the context of a few motivating applications is very helpful. In particular, the process of purchasing data from data sources needs clarification.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for this review!\n\n**Relationship between various quantities and usefulness of $z_t$**: The quantities $(z_t,a_t,u_t,c_{t1},...,c_{tK})$ are random variables non necessarily independent, which are simultaneously drawn from some distribution, but which are only partially observed by the advertiser. Thus knowing $z_t$ may indeed yield more information on $a_t$ and $u_t$ and it is helpful to estimate them (of course if they are independent this is not the case). This information is used as $z_t$ is contained in $c_{t,k}$. The fact that $c_{tk}$ contains $z_t$ can be regarded more as a notation rather than an assumption. This was meant to avoid overloading notation; otherwise having to write $\\mathbb{E}[u_t \\mid (z_t,c_{tk_t})]$. We will simply define $c_{tk}=(\\text{new purchased information}, z_t)$. We will clarify this in line 152.\n\n**Motivating examples and quantities of interests contextualized**:  Here are some examples of the information purchase model: Suppose that an advertiser wants to show ads to a user and is able to see some barebone information through cookies, such as previously visited websites ($z_t$). Based on this information, they can decide whether or not  to buy additional information ($c_{tk}$) from different data brokers that collect user activity. For instance, if they see from the public context that clothing shops were visited, they may buy data that contains purchase information from this website, which enables estimating the user’s gender ($a_t$) based on type of clothing bought. Another example would be fair refugees resettlement to different cities. When the organization in charge of resettlement receives a case ($z_t$), it can either decide to directly assign the refugee to a specific city, or to conduct an additional costly investigation to get more information ($c_{tk}$) on some protected attributes of interest such as wealth or age ($a_t$), which might have been misreported. We will add these examples after the model presentation.\n\n**Contributions and differences with previous literature**: The reviewer is correct in that the main difference compared to Balseiro (2021) and Celli (2022) is considering jointly source selection and fairness penalty, as well as handling uncertainty on $u_t$ and $a_t$. On a technical level, the proofs use the arguments regarding the fairness penalty of these works, and the main differences are the following: A martingale argument (Lemma $3.3$) enables the previous algorithm to be modified to handle uncertainty for a single fixed source by using conditional expectation, yielding one $\\lambda_k$ per source $k$. Selecting the optimal source could be done by running a bandit algorithm for each $k$ using the optimal $\\lambda_k^*$, but the $\\lambda_k^*$ are not known a priori. Instead we instantiate a unique $\\lambda_t$ for a combination of sources $\\pi_t$, and handle the varying $\\pi_t$ through EXP3 and combine its analysis with the $\\lambda_t$ dual descent in Balseiro. An important condition in order to use EXP3 on the virtual values is for $\\lambda_t$ to be bounded. Hence we optimize over $\\Delta_{\\delta_t}$ instead of $\\Delta$ in Equation (8), which guarantees that $\\lambda_t$ will be bounded (Lemma $3.2$) as we show using KKT conditions.  We will highlight in the contributions paragraph (line 57) that the main difference with previous work is the combination of those primal and dual steps, and add the above comments on the technical comparison with previous work near Section 3.4 (Sketch of proof).\n\n**Dimension of the various parameters**: the quantity $a_t$ is of dimension $d$ as defined in line $108$. For the decision making aspect, the dimension of $c_{tk}$ does not matter as it is only present in the conditioning of the expectation: what really matters is the sigma algebra generated by $c_{tk}$. When $\\mathcal{Z}$ is finite (line 110) the same argument applies. If we want learn $\\mathbb{E}[u_t \\mid c_{t,k}]$ (Section 4.2), or deal with $\\vert \\mathcal{Z} \\vert=\\infty$ (Section 3.5), additional structure is needed: $c_{tk} \\in \\mathbb{R}^{q_k}$ (line 350) and $z_t \\in \\mathbb{R}^r$ (line 310).\n\n**Estimation of $\\mathbb{E}[a_t \\mid c_{tk}]$**: See reply \"Estimates of protected attributes\" to reviewer 2Yz9.\n\n**Convexity of the perspective of $R$**: There is indeed a typo, we meant to say that $R(\\sum_t a_t x_t/ \\sum_t x_t)$ is not convex, and the reviewer is correct that the function $\\sum_t x_t R(\\sum_t a_t x_t/ \\sum_t x_t)$ is convex as the perspective of $R \\circ A$ (with $A$ the matrix with columns the $a_t$), We thank the reviewer for catching this mistake! We will correct it, and add the mention of the perspective function as a clear intuition of why this fairness version can also be handled.\n\n**Adversarial inputs**: Yes, it should be possible to use Algorithm 1 for adversarial inputs (adversarial contexts $c_{tk}$) directly without additional modifications under some additional assumptions for $R$ and when there are no public contexts. This would yield a sublinear $\\alpha$-regret bound instead of a sublinear regret bound (see Balseiro (2021) Theorem 2 for the assumption). The reason why the current analysis would still hold is that the EXP3 algorithm is able to handle adversarial inputs, and the boundedness of $\\lambda_t$ is deterministic. Using in the fashion as Balseiro (2022) the assumption on $R$ to handle adversarial inputs for the fairness penalty, the analysis should then be fairly straightforward. We haven’t discussed the adversarial case, because some stochasticity is still needed for $\\mathbb{E}[ u_t \\mid c_{t,k}]$ to be well defined, and we found this mixed stochastic-adversarial model to be ambiguous. We can add this comment to the conclusion for completeness.\n\nWe hope to have clearly addressed all your interrogations and thank you for the useful clarifying elements that were produced as a response to this review. We are happy to discuss any further concerns you might have during the discussion period."}, {"review_id": "lYsdJnoOLm", "reviewer": "Reviewer_uY3q", "summary": "The authors formulate the online fair allocation problem, where a decision maker may choose an information source $k_t$ based on public context $z_t$ and generate an allocation decision $x_t$ with a reward $1$ if $x_t=1$. The fairness penalty is some convex function that is minimized when the decision $x_t$ is uncoupled with the private type $a_t$. The authors developed a virtual-value-based algorithm that achieves $O(\\sqrt{T})$ online regret. ", "questions": "What is the theoretical lower bound for this problem?", "limitations": "No concerns here.", "rating": 5, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "The fairness problem is of interest to the community, especially when the private attributes are unseen. ", "weaknesses": "It seems that the source selection part is simply the exponential weight algorithm with some virtual values which can be updated by the EXP3 algorithm. The allocation is based on the dual value $\\lambda_t$ which can then be updated by the dual gradient descent. In my opinion, the authors did not make enough effort to explain the intuitions and justified the use of these algorithms, let alone the novelty of the work. Also, I'm not sure about the technical involvement, since it seems that the only challenge here is having multiple sources of information.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for this review!\n\n**Concerning the novelty and the technical difficulties**:\nAs discussed in the abstract (line 7-8) and in the introduction (line 57-58), the main novelty of this work is to consider jointly the problem of source selection and of long term fairness penalty. Indeed, those two difficulties in isolation are already studied in the literature: When $R=0$, the model reduces to a stochastic bandit problem which can be solved using UCB or EXP3 as mentioned by the reviewer, and when $K=1$ we recover the existing works of Balseiro (2021) and Celli (2022) for long term fairness penalty. While it may seem that the joint problem can be simply treated by naively handling them separately, this is *not* the case as the fairness penalty introduces non linearity, and introduces interaction between those two aspects. Thus to a fixed source $k$ corresponds an optimal fair parameter $\\lambda_k^*$, and to a fixed fairness parameter $\\lambda$ corresponds an optimal source $k_{\\lambda}^*$. Hence the selected source $k_t$ affects the fairness, and vice versa $\\lambda_t$ affects the virtual fair-penalized mean of source $k$: both parameters change simultaneously and we are not necessarily selecting the best source for the best fairness penalty. How can we combine these two algorithms? Moreover, we have also shown that the interaction between those two problems is strong (line 180-181, line 63-65), as while optimal solutions in bandits problems are usually a fixed arm $k^*$, here due to the nonlinearity of $R$ the optimal source selection can be a strict convex combination of the sources (Proposition 2.1). \n\nThus an important question is whether it is possible to combine the dual and primal step, and if yes, how. Perhaps surprisingly, alternating between the primal and dual step is sufficient and efficient, and there is no need to instantiate and keep track of a dual fairness parameter $\\lambda_{k,t}$ for each source. This is, however, in no way obvious and is rather an outcome of our analysis. The main technical difficulty is then showing that this alternation does lead to a tight upper bound. On a more technical level we show how one can model the randomness and estimates, how we can bound the fair dual parameters to guarantee that adversarial bandits techniques can be used, and how to combine the analysis of primal and dual steps (see Sketch of Proof 3.4).\n\nTwo other novelties of this work concern Section $4.2$ where we show how to obtain online estimates, and Section $4.1$ where we show that a similar algorithm works for another formulation of fairness which was desired in Celli (2022), even when there is only one source of information.\n\n**Lower bound**: Regarding the lower bound, the specific case $R=0$ reduces the problem to a pure stochastic bandit problem, which has a problem-independent $\\Omega(\\sqrt{T})$ lower bound. Therefore the proposed algorithm and its analysis is tight in $T$. We will add this comment after the upper bound result. \n\nWe hope to have clarified the technical difficulties and novelty of our work, and would be happy to give more details during the discussion period."}, {"review_id": "wlctlaR007", "reviewer": "Reviewer_aPcw", "summary": "Existing works in the fair online allocation space assume that the decision-maker has access to protected attributes. In contrast, this paper studies the choice of a data source as a multi-armed bandit problem in conjunction with the primary allocation problem. This paper introduces a computationally efficient algorithm with sublinear regret in the general case. The contributions of this paper are exclusively theory-based, including regret bounds for various types of regret penalties.", "questions": "N/A", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This is the first paper to consider optimizing over data sources in the problem space of fair online allocation. This paper contributes an algorithm with proven regret bounds, which is significant. I believe that other researchers are likely to build off of this work, and that it advances research in a demonstrable way. \n\nThis paper is excellently written. It is clear, well organized, and adequately informs the reader. In particular, I am happy to see good explanations of the reasoning, limitations, and assumptions made in this work.\n", "weaknesses": "This paper does not contribute code or empirical results; both of which would be of interest to the research community.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for this review!\n\nRegarding code and experimental results, we have presented a simple numerical toy example in the appendix F.2. Additionally, we made additional numerical simulations in a simple case showing how the optimal solution and value vary as we vary some parameters. We refer the reviewer to the global response and the PDF attached to it for details about this simulation, and will provide the code in the supplementary material.\n\nWe are happy to discuss any additional questions you might have during the discussion period. \n"}]

Author rebuttal:
In response to reviewer 2Yz9 we have conducted an additional numerical experiment for a simple example on the impact of varying fairness and information cost over the allocations and other meaningful quantities. The results are presented in the figure of the one-page PDF attached to this global response. 

**Model**: For this numerical example, $a_t$ can take values $-1$ or $1$. We consider a fairness penalty $R(x)=r x^2$ with $r\geq 0$ and the following distribution for $(u_t,a_t)$: $\Pr(a_t=1)=\Pr(a_t=-1)=1/2$ and $u_t \sim \mathcal{N}(a_t,1)$. We assume $K=2$ with for source $k=1$, $p_1=p \in [0,1]$ and $c_{t,1}=(a_t,u_t)$, and for source $k=2$, $p_2=0$ and $c_{t,2}=u_t$. Basically we observe the utility $u_t$ in all cases, and before observing $u_t$ we can pay $p$ to additionally observe $a_t$. Note that when $r=0$ then $R=0$ and there is no fairness penalty, while when $p=0$ there is no uncertainty. 

We study the asymptotic regime with $T \rightarrow \infty$,  and compute the optimal solution of the offline optimization problem. Figure $1$ represent the quantities associated to the optimal solution for varying $p$ and $r$: (top-left) $\pi^*$ the percentage of times information is bought (i.e., $k=1$ is chosen), (top-right) the probability of group $1$ being selected $\Pr(a_t=1 \mid x_t=1)$, (bottom-left) the fairness cost relative to utility $R(\mathbb{E}[a_t x_t])/\mathbb{E}[u_t x_t]$, and (bottom-right) the information cost relative to utility $p \pi^*/\mathbb{E}[u_t x_t]$.

**Analysis and interpretation**: 
- (top-left) Looking at the optimal action in terms of information source selection (to buy the observation of $a_t$ or not), we see that there are three regimes: $\pi^*=1$, $\pi^*=0$ and a transitive regime $\pi^* \in (0,1)$. When $r=0$ there is no reason to care about $a_t$, thus we simply do not buy information $\pi^*=0$ and this remains true as long as the cost of $p$ is large over $r$. When $p=0$ there are no costs to observe $a_t$ and thus $\pi^*=1$ and this remains true as long as the fairness penalty $r$ is large enough over $p$. In between, we may obtain optimal actions which are strictly between $0$ and $1$: in this case the best action is a strict convex combination between the two actions and there is some trade-off between buying costly information and selecting an unfair allocation. 
- (top-right) Regarding the proportion of individuals of group $1$ selected, we see that they are always higher than $0.5$, this is because group $1$ correlates to higher utility compared to group $2$ (which corresponds to $a_t=-1$). Therefore it is decreasing in $r$ and goes towards the perfectly fair allocation $0.5$ which would incur no penalty even for high $r$. It is also increasing in $p$ as higher information costs make it less desirable to observe $a_t$, and thus more difficult to accurately make a fair allocation: the support of the utility $u_t$ conditioned on $a_t=1$ and conditioned on $a_t=-1$ are not disjoint, which makes it impossible only by observing $u_t$ to determine whether $a_t=1$ or $-1$. 
- (bottom-left) For the relative fairness cost compared to utility, when the information cost $p$ increases the allocation becomes more unfair as it becomes more difficult without access to $a_t$ to choose a fair allocation with good utility, moreover the average utility $u_t$ of the selected groups tend to decrease as the individuals which are more likely to be $a_t=-1$ based on $u_t$ have low utility. Therefore the ratio fairness penalty over expected utility increases. When $r$ increases there are three conflicting effects: high $r$ makes it more appealing to achieve a fair allocation at the cost of expected utility $u_t$ which makes the latter decrease, the expected group allocation becomes more fair as seen previously, and the scaling of $R$ increases. When $r$ becomes too high this leads towards a perfectly fair group allocation and thus a fairness penalty of $0$, and when $r=0$ the fairness penalty is also $0$. Overall for each fixed $p$ there is some maximum in terms of fairness penalty relative to utility. 
- (bottom-right) Finally for the information cost relative to utility, it is increasing in $r$: due to large fairness penalties it is better to buy information thus $\pi^*$ increases while $p$ remains fixed, hence the product $p\pi^*$ increases. When $p$ increases, we buy information less often ($\pi^*$ decreases), and because $p\pi^*=0$ for $p=0$ or $p$ large, there is some maximum for each $r$ fixed. 

Overall, we see that higher fairness penalties tend to make it more likely to buy information and select a fair allocation even at the cost of utility, while high information cost makes it unattractive to buy this information and can lead to unfairness due to the difficulty of identifying the protected attribute without this information. Given that the focus of our paper is on the online aspects of the problem and not the offline aspects discussed in this response (to address a comment of Reviewer 2Yz9), we plan to put this numerical example (figure and associated comments) in the supplementary material only. 

Meta-review: This paper looks at online allocation problems where long-term group unfairness is penalized *and* where the central platform does not directly and immediately observe group membership/sensitive attributes, but instead can pay to receive additional information about group membership.  Reviewers and this AC appreciate that motivation, as (i) many real-world platform allocation/matching problems either are not legally allowed to or otherwise do not collection group membership but (ii) can either pay human labelers to, at cost, get a better estimate of membership or can go through a third-party watchdog service to get some estimate.  The paper addresses a rather general form of group fairness that in this setting captures a few standard group fairness defs like demographic parity.  Reviewers appreciated the model but found issue with some restrictive assumptions (users drawn iid from a distribution that does not change, the mechanism combining public info and paid-for private info, and some lack of bounds.  Still, the reviewers and this AC appreciated the rebuttal and discussion and, when the authors make their rebuttal edits as promised, find the paper a worthy addition to the online allocation/matching + fairness + learning literature.
Decision: Accept (poster)