Fair Secretaries with Unfair Predictions

Authors: eric  balkanski
will  ma
andreas  maggiori
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 02:07:45

Abstract: Algorithms with predictions is a recent framework for decision-making under uncertainty that leverages the power of machine-learned predictions without making any assumption about their quality. The goal in this framework is for algorithms to achieve an improved performance when the predictions are accurate while maintaining acceptable guarantees when the predictions are erroneous. A serious concern with algorithms that use predictions is that  these predictions can be biased and, as a result, cause the algorithm to make decisions that are deemed unfair. We show that this concern manifests itself in the classical secretary problem in the learning-augmented setting---the state-of-the-art algorithm can have zero probability of accepting the best candidate, which we deem unfair, despite promising to accept a candidate whose expected value is at least $\max\{\Omega (1) , 1 - O(\varepsilon)\}$ times the optimal value, where $\varepsilon$ is the prediction error.
We show how to preserve this promise while also guaranteeing to accept the best candidate with probability $\Omega(1)$.  Our algorithm and analysis are based on a new ``pegging'' idea that diverges from existing works and simplifies/unifies some of their results. Finally, we extend to the $k$-secretary problem and complement our theoretical analysis with experiments.

Main paper: 
 introduction: 
 As machine learning algorithms are increasingly used in socially impactful decision-making applications, the fairness of those algorithms has become a primary concern. Many algorithms deployed in recent years have been shown to be explicitly unfair or reflect bias that is present in training data. Applications where automated decision-making algorithms have been used and fairness is of central importance include loan/credit-risk evaluation [46, 36, 45] , hiring [8, 13] , recidivism evaluation [47, 1, 19, 11, 14] , childhood welfare systems [12] , job recommendations [40] , and others [30, 28, 31] . A lot of work in recent years has been devoted to formally defining different notions of fairness [43, 34, 24, 21, 15, 38, 37] and designing algorithms that satisfy these different definitions [33, 32, 9, 10, 49] .While most fairness work concentrates on classification problems where the instance is known offline, we explore the problem of making fair decisions when the input is revealed in an online manner. Although fairness in online algorithms is an interesting line of research per se, fairness considerations have become increasingly important due to the recent interest in incorporating (possibly biased) machine learning predictions into the design of classical online algorithms. This framework, usually referred to as learning-augmented algorithms or algorithms with predictions, was first formalized in [44] . In contrast to classical online algorithms problems where it is assumed that no information is known about the future, learning-augmented online algorithms are given as input, possibly erroneous, predictions about the future. The main challenge is to simultaneously achieve an improved performance when the predictions are accurate and a robust performance when the predictions are arbitrarily inaccurate. A long list of online problems have been considered in this setting and we point to [41] for an up-to-date list of papers. We enrich this active area of research by investigating how potentially biased predictions affect the fairness of decisions made by learningaugmented algorithms, and ask the following question:Can we design fair algorithms that take advantage of unfair predictions?In this paper, we study this question on a parsimonious formulation of the secretary problem with predictions, motivated by fairness in hiring candidates.The problem. In the classical secretary problem, there are n candidates who each have a value and arrive in a random order. Upon arrival of a candidate, the algorithm observes the value of that candidate and must irrevocably decide whether to accept or reject that candidate. It can only accept one candidate and the goal is to maximize the probability of accepting the candidate with maximum value. In the classical formulation, only the ordinal ranks of candidates matter, and the algorithm of Dynkin [22] accepts the best candidate with a constant probability, that equals the best-possible 1/e.In the learning-augmented formulation of the problem proposed by Fujii and Yoshida [25] , the algorithm is initially given a predicted value about each candidate and the authors focus on comparing the expected cardinal value accepted by the algorithm to the maximum cardinal value. The authors derive an algorithm that obtains expected value at least max{Ω(1), 1 -O(ε)} times the maximum value, where ε ≥ 0 is the prediction error. The strength of this guarantee is that it approaches 1 as the prediction error decreases and it is a positive constant even when the error is arbitrarily large. However, because the algorithm is now using predictions that could be biased, the best candidate may no longer have any probability of being accepted. We view this as a form of unfairness, and aim to derive algorithms that are fair to the best candidate by guaranteeing them a constant probability of being accepted (we contrast with other notions of fairness in stopping problems in Section 1.1). Of course, a simple way to be fair by this metric is to ignore the predictions altogether and run the classical algorithm of Dynkin. However, this approach would ignore potentially valuable information and lose the improved guarantee of [25] that approaches 1 when the prediction error is low.Outline of results. We first formally show that the algorithm of [25] may in fact accept the best candidate with 0 probability. Our main result is then a new algorithm for secretary with predictions that: obtains expected value at least max{Ω(1), 1 -O(ε)} times the maximum value, like [25] ; and ensures that, under any predictions, the probability that the best candidate is accepted is at least 1/16. This result takes advantage of potentially biased predictions to achieve a guarantee on expected value that approaches 1 when the prediction error is small, while also providing a fairness guarantee for the true best candidate irrespective of the predictions. We note that Antoniadis et al. [3] also derive an algorithm for secretary with predictions, where the prediction is of the maximum value. This algorithm accepts the best candidate with constant probability but it does not provide a guarantee on the expected value accepted that approaches 1 as the prediction error approaches 0. Similarly, Dynkin's algorithm for the classical secretary problem accepts the best candidate with constant probability but does not make use of predictions at all. Finally, we note that the definitions of the prediction error ε differ in [25] and [3] ; the former error definition uses the maximum ratio over all candidates between their predicted and true value while the latter uses the maximum absolute difference. Our techniques present an arguably simpler analysis and extend to a general family of prediction error measures that includes both of these error definitions.We then extend our approach to the multiple choice or k-secretary problem where the goal is to accept at most k candidates and maximize the total of their values, which is the most technical part of the paper. We design an algorithm that obtains expected total value at least max{Ω(1), 1 -O(ε)} times the optimum (which is the sum of the k highest values), while simultaneously guaranteeing the k highest-valued candidates a constant probability of being accepted. We also have a refined guarantee that provides a higher acceptance probability for the (1 -δ)k highest-valued candidates, for any δ ∈ (0, 1).Finally, we simulate our algorithms in the exact experimental setup of Fujii and Yoshida [25] . We find that they perform well both in terms of expected value accepted and fairness, whereas benchmark algorithms compromise on one of these desiderata.The secretary problem. After Gardner [26] introduced the secretary problem, Dynkin [22] developed a simple and optimal stopping rule algorithm that, with probability at least 1/e, accepts the candidate with maximum value. Due to its general and simple formulation, the problem has received a lot of attention (see, e.g., [42, 27] and references therein) and it was later extended to more general versions such as k-secretary [39] , matroid-secretary [7] and knapsack-secretary [6] .Secretaries with predictions. The two works which are closest to our paper are those of Antoniadis et al. [3] and Fujii and Yoshida [25] . Both works design algorithms that use predictions regarding the values of the candidates to improve the performance guarantee of Dynkin's algorithm when the predictions are accurate while also maintaining robustness guarantees when the predictions are arbitrarily wrong. Antoniadis et al. [3] uses as prediction only the maximum value and defines the prediction error as the additive difference between the predicted and true maximum value while Fujii and Yoshida [25] receives a prediction for each candidate and defines the error as the maximum multiplicative difference between true and predicted value among all candidates.Secretaries with distributional advice. Another active line of work is to explore how distributional advice can be used to surpass the 1/e barrier of the classical secretary problem. Examples of this line of work include the prophet secretary problems where each candidate draws its valuation from a known distribution [23, 17, 18, 5] and the sample secretary problem where the algorithm designer has only sample access to these distribution [35, 16] . We note that in the former models, predictions are either samples from distributions or distributions themselves which are assumed to be perfectly correct, while in the learning-augmented setting, we receive point predictions that could be completely incorrect. Dütting et al. [20] investigate a general model for advice where both values and advice are revealed upon a candidate's arrival and are drawn from a joint distribution F. For example, their advice can be a noisy binary prediction about whether the current candidate is the best overall. Their main result uses linear programming to design optimal algorithms for a broad family of advice that satisfies two conditions. However, these two conditions are not satisfied by the predictions we consider. Additionally, we do not assume any prior knowledge of the prediction quality, whereas their noisy binary prediction setting assumes that the error probability of the binary advice is known.Fairness in stopping algorithms. We say that a learning-augmented algorithm for the secretary problem is F -fair if it accepts the candidate with the maximum true value with probability at least F . In that definition, we do not quantify unfairness as a prediction property but as an algorithmic one, since the algorithm has to accept the best candidate with probability at least F no matter how biased predictions are our fairness notion is a challenging one. That notion can be characterized as an individual fairness notion similar to the identity-independent fairness (IIF) and time-independent fairness (TIF) introduced in [4] . In the context of the secretary problem, IIF and TIF try to mitigate discrimination due to a person's identity and arrival time respectively. While these are very appealing fairness notions, the fair algorithms designed in [4] fall in the classical online algorithms setting as they do not make any assumptions about the future. Consequently, their performance is upper bounded by the performance of the best algorithm in the classical worst-case analysis setting. It is also interesting to note the similarities with the poset secretary problem in [48] . In the latter work the set of candidates is split into several groups and candidates belonging to different groups cannot be compared due to different biases in the evaluation. In some sense, we try to do the same; different groups of candidates may have predictions that are affected by different biases making the comparison difficult before the true value of each candidate is revealed. Again, in [48] no information about the values of future candidates is available and the performance of their algorithms is upper bounded by the best possible performance in the worst-case analysis setting. 
preliminaries: 
 Secretary problem with predictions. Candidates i = 1, . . . , n have true values u i and predicted values ûi . The number of candidates n and their predicted values are known in advance. The candidates arrive in a uniformly random order. Every time a new candidate arrives their true value is revealed and the algorithm must immediately decide whether to accept the current candidate or reject them irrevocably and wait for the next arrival. We let i * = argmax i u i and î = argmax i ûi denote the indices of the candidates with the maximum true and predicted value respectively. An instance I consists of the 2n values u 1 , . . . , u n , û1 , . . . , ûn which, for convenience, are assumed to be mutually distinct 1 and greater or equal to 12 . We let ε(I) denote its prediction error. For simplicity, we focus on the additive prediction error ε(I) = max i |û i -u i |, but we consider an abstract generalization that includes the multiplicative prediction error of [25] in Appendix A.2.Objectives. We let A be a random variable denoting the candidate accepted by a given algorithm on a fixed instance, which depends on both the arrival order and any internal randomness in the algorithm. We consider the following desiderata for a given algorithm:EQUATION)Our goal is to derive algorithms that can satisfy smoothness and fairness with constants C, F > 0 that do not depend on the instance I or the number of candidates n. Existing algorithms for secretary with predictions do not simultaneously satisfy these desiderata, as we explain in Appendix A.1.Comparison to other objectives. Existing algorithms for secretary with predictions do satisfy a weaker notion called R-robustness, whereE[u A ] ≥ R • u i * for some constant R > 0.Our desideratum of fairness implies F -robustness and aligns with the classical secretary formulation where one is only rewarded for accepting the best candidate. Another notion of interest in existing literature is consistency, which is how E[u A ] compares to u i * when ε(I) = 0. Our smoothness desideratum implies 1-consistency, the best possible consistency result, and guarantees a smooth degradation as ε(I) increases beyond 0.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] .Justification: We added a limitations section at the end of the main paper. The computational efficiency of the algorithms is discussed in the main paper.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
the algorithm: 
 We first present and analyze the ADDITIVE-PEGGING algorithm which achieves the desiderata from Section 2. Then, we mention how using a more abstract prediction error and an almost identical analysis, permits us to generalize ADDITIVE-PEGGING to PEGGING which achieves comparable guarantees for a more general class of error functions that includes the multiplicative error.Our algorithms assume that each candidate i arrives at an independently random arrival time t i drawn uniformly from [0, 1]. The latter continuous-time arrival model is equivalent to candidates arriving in a uniformly random order [29] and simplifies the algorithm description and analysis. We also write ϵ i as shorthand for |u i -ûi |, ε as shorthand for ε(I) (so that ε = max i ϵ i ) and i ≺ j if t i < t j .Description of ADDITIVE-PEGGING . ADDITIVE-PEGGING ensures smoothness by always accepting a candidate whose value is close to u î which, as we argue, is at leastu i * -2 ε. To see this, note that u î ≥ ûî -ϵ î ≥ ûi * -ϵ î ≥ u i * -ϵ i * -ϵ î ≥ u i * -2 ε, where we used that ûî ≥ ûi * (by definition of î) and ε ≥ max{ϵ i * , ϵ î} (by definition of ε). Because u i * -2 ε ≥ u i * (1 -2ε) from the assumption that u i * ≥ 1, this suggests that for smoothness it suffices to focus on comparing to u î.For this purpose, our algorithm computes the literal C = (i = î) at each new arrival, ensuring that any acceptance while C holds maintains smoothness.For the fairness desideratum, we note that Dynkin's algorithm [22] for the classical secretary problem relies on the observation that if a constant fraction of the candidates have arrived and the candidate who just arrived has the maximum true value so far, then this candidate has a constant probability of being the best overall. |I pegged | = 1 then A ← i else I pegged ← I pegged \ {i} F ← (u i > max j≺i u j ) , C ← (i = î) , ε ti ← max j:tj ≤ti |û j -u j | if C ∧ F then A ← i else if C ∧ F then if u i > ûî -ε ti then A ← i else if C ∧ F then I pegged ← {j ≻ î : u î < ûj + ε t î } if I pegged = ∅ then A ← iAnalysis of the ADDITIVE-PEGGING algorithm.Lemma 1. ADDITIVE-PEGGING satisfies u A ≥ u i * • (1 -4 ε(I)) , ∀I with probability 1.Proof. Let i pegged denote the last arriving candidate in I pegged .We first argue that PEGGING always accepts a candidate irrespective of the random arrival times of the candidates. We focus on any instance where ADDITIVE-PEGGING does not accept a candidate until time t î. At time t î either C ∧ F or C ∧ F are true. Since in the former case candidate î is accepted, we focus on the latter case and in particular whenever the set I pegged which is computed is non-empty (otherwise, candidate î is accepted). In that case, it is guaranteed that by time t i pegged ADDITIVE-PEGGING will accept a candidate.We now argue that in all cases ADDITIVE-PEGGING maintains smoothness. Using ε, ϵ i definitions and the fact that î is the candidate with the maximum predicted value we have:ûî ≥ ûi * ≥ u i * -ϵ i * ≥ u i * -ε.If candidate î is accepted then using the latter lower bound we getu î ≥ ûî -ϵ î ≥ u i * -ε -ϵ î ≥ u i * -2 ε. If we accept i ̸ = î and the if statement of C ∧ F is executed at time t i then we have u i > ûî -ε ti ≥ u i * -ε -ε ti ≥ u i * -2 ε.Finally, we need to lower bound the value u i pegged in case our algorithm terminates accepting i pegged . Note that from the way the pegged set I pegged is updated when C ∧ F is true we always have u î < ûi pegged + ε t î . Sinceu i pegged ≥ ûi pegged -ϵ i pegged we can conclude that u i pegged > u î -ε t î -ϵ i pegged ≥ u i * -4 ε. Finally, note that since u i * ≥ 1 we have that u i * -4 ε ≥ u i * (1 -4 ε). Lemma 2. ADDITIVE-PEGGING satisfies P [A = i * ] ≥ 1/16, ∀I.Proof. In the following we assume that the number of candidates is larger or equal to 3. The proof for the case where n = 2 is almost identical while the fairness guarantee in that case is 1/4. We denote by ĩ the index of the candidate with the highest true value except i * and î, i.e., ĩ = argmax i̸ =i * ,î u i . Note that depending on the value of u î, ĩ might denote the index of the candidate with the second or third highest true value. To prove fairness we distinguish between two cases: either î = i * or î ̸ = i * . For each of those cases, we define an event and argue that: (1) the event happens with constant probability; and (2) if that event happens then ADDITIVE-PEGGING accepts i * .If i * = î we define event E = {t ĩ < 1/2 < t i * } for which P [E] = 1/4. E implies that our algorithm does not accept any candidate until time t i * . Indeed, note that at any point in time before t i * , both literals F and C are simultaneously false. On the contrary, at time t i * , both C and F are true and our algorithm accepts i * .On the other hand, if i * ̸ = î we distinguish between two sub-cases. First, we show that either u î < ûi * + ϵ î or u i * > ûî -ϵ i * is true. By contradiction, assume that both inequalities do not hold, thenu î ≥ ûi * + ϵ î u i * >u î = ==== ⇒ u i * > ûi * + ϵ î = ⇒ u i * -ûi * > ϵ î ϵ i * ≥u i * -û i * ========⇒ ϵ i * > ϵ î u i * ≤ ûî -ϵ i * u i * >u î = ==== ⇒ u î < ûî -ϵ i * = ⇒ ϵ i * < ûî -u î ϵ î≥u î-ûî ======⇒ ϵ i * < ϵ îwhich is a contradiction. We now define two events E 1 and E 2 which imply that i * is always accepted whenever {u î < ûi * + ϵ î} and {u i * > ûî -ϵ i * } are true respectively.If u î < ûi * + ϵ î, then we define event E 1 = {t ĩ < 1/2} ∧ {t î < 1/2} ∧ {1/2 < t i * }P [E 2 ] = P [t ĩ < 1/2] • P [1/2 < t i * < t î] = P [t ĩ < 1/2] • P [1/2 < min{t i * , t î} ∧ min{t i * , t î} = t i * ] = P [t ĩ < 1/2] • P [1/2 < min{t i * , t î}] • P [min{t i * , t î} = t i * ] = (1/2) • (1/4) • (1/2) = 1/16Note that until time t i * no candidate is accepted since C and F are both false at all times. Indeed, between times 0 and 1/2 only î could have been accepted but its arrival time is after t i * , and between times 1/2 and t i * no candidate has a true value larger than u ĩ. Finally, note that at time t i * we have ε t i * ≥ ϵ i * and consequently C ∧ F ∧ {u i * > ûî -ε t i * } is true and i * gets accepted.Theorem 3. ADDITIVE-PEGGING satisfies smoothness and fairness with C = 4 and F = 1/16.Theorem 3 follows directly from Lemmas 1 and 2. We note that Lemma 1 actually implies a stronger notion of smoothness that holds with probability 1.The general PEGGING algorithm. In Appendix A.2 we generalize the ADDITIVE-PEGGING algorithm to the PEGGING algorithm to provide fair and smooth algorithms for different prediction error definitions. ADDITIVE-PEGGING is an instantiation of PEGGING when the prediction error is defined as the maximum absolute difference between true and predicted values among candidates.To further demonstrate the generality of PEGGING , we also instantiate it over the same prediction error definition ε(I) = max i |1 -ûi /u i | as in [25] and recover similar smoothness bounds as in [25] while also ensuring fairness. We name the latter instantiation MULTIPLICATIVE-PEGGING and present its guarantees in Theorem 4. Fujii and Yoshida [25] define the prediction error as in Theorem 4 and design an algorithm that accepts a candidate with expected value at leastEQUATIONε the latter algorithm satisfies the smoothness desideratum of Section 2, but, as we prove in Appendix A.1 it violates the fairness desideratum.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] .Justification: Yes, all results can be reproduced easily by running the jupyter notebook in the supplemental material. Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
extension: k-secretary problem with predictions: 
 We consider the generalization to the k-secretary problem, where k ≥ 1 candidates can be accepted.To simplify notation we label the candidates in decreasing order of predicted value, so that û1 >• • • > ûn and denote r i to be the index of the candidate with the i'th highest true value so that u ri > • • • > u rn . The prediction error is again defined as ε(I) := max i |u i -ûi | and we let S denote the random set of candidates accepted by a given algorithm on a fixed instance. The extension of our two objectives to this setting isE i∈S u i ≥ (1 -C • ε(I)) k i=1 u ri , ∀I (smoothness for k-secretary) P [r i ∈ S] ≥ F i , ∀i = 1, . . . , k, ∀I.(fairness for k-secretary)The smoothness desideratum compares the expected sum of true values accepted by the algorithm to the sum of the k highest true values that could have been accepted. The fairness desideratum guarantees each of these candidates in the top k to be accepted with probability F i . The k-secretary problem with predictions has been studied by Fujii and Yoshida [25] , who derive an algorithm satisfyingE i∈S u i ≥ max{1 -O(log k/ √ k), 1 -O(max i |1 -ûi /u i |)} k i=1u ri but without any fairness guarantees. We derive an algorithm K-PEGGING that satisfies the following. Theorem 5. K-PEGGING satisfies smoothness and fairness for k-secretary with C = 4 andF i = max (1/3) k+5 , 1-(i+13)/k 256 for all i = 1, . . . , k.Assuming k is a constant, C and F 1 , . . . , F k in Theorem 5 are constants that do not depend on n or the instance I. For large values of k the first term in F i is exponentially decaying, but the second term still guarantees candidate r i a probability of acceptance that is independent of k as long as i/k is bounded away from 1. More precisely, for any constant δ > 0 and i ≤ (1 -δ)k -13, candidate r i is accepted with probability at least δ/256. For large values of k, we can apply this fact with δ = 1/2 to see that all candidates in the top quarter are accepted with probability at least 1/512, getting a "robustness" constant that is independent of k:E i∈S u i ≥ 1 2048 k i=1 u ri .The algorithm. While we defer the proof of Theorem 5 to Appendix B, we present the intuition and the main technical difficulties in the design of K-PEGGING . K-PEGGING maintains in an online manner the following sets: (1) the solution set S which contains all the candidates that have already been accepted; (2) a set H that we call the hopeful set and contains the k -|S| future candidates with the highest predicted values; (3) a set B that we call the blaming set. B contains a subset of already arrived candidates that pegged a future candidate; and (4) the set P of pegged elements which contains all candidates that have been pegged by a candidate in B. In addition, we use function peg : {1, ..., k} -→ [n] to store the "pegging responsibility", i.e., if peg(i) = j then at time t i , i ∈ {1, ..., k}: (a) was not accepted; and (b) forced j to be pegged. We use peg -1 (j) = i to denote that j was pegged by i.Algorithm 2 K-PEGGING H ← [k], S ← ∅, P ← ∅, B ← ∅ while agent i arrives at time t i do τ ← k th highest value seen before time t i , ε ti ← max j:tj ≤ti |û j -u j | case 1: i ∈ P Add i to S, remove i from P and remove peg -1 (i) from B. case 2: i ∈ H and (t i ≤ 1/2 or u i ≤ τ ) subcase 2a: {j ≻ i : u i < ûj +ε ti }\(P ∪[k]) = ∅ or (C i = 0 with C i ∼ Bernoulli(1/2)) Add i to S, remove i from H subcase 2b: Otherwise Add argmin j∈{j≻i:ui<ûj +εt i }\(P ∪[k]) ûj to P , add i to B, remove i from H case 3: i ∈ H and (t i > 1/2 and u i > τ ) Add i to S and remove i from H case 4: i ̸ ∈ H and (t i > 1/2 and u i > τ )subcase 4a: {j ∈ B : u i > u j } ̸ = ∅ Add i to S, remove argmax j∈B:ui>uj u j from B, and remove peg(j) from P subcase 4b: {j ∈ H :u i > ûj -ε ti } ̸ = ∅ Add i to S and remove argmax j∈H:ui>ûj -εt i u j from HTo satisfy the fairness property, we check if the current candidate i has arrived at time t i ≥ 1/2 and if u i larger than the k th highest value seen so far. We refer to these two conditions as the fairness conditions. If i ∈ P (case 1) or i ∈ H and the fairness conditions hold (case 3), then we accept i. If the fairness conditions hold but i ̸ ∈ H then we accept only if there is a past candidate in B (subcase 4a) or a future candidate in H (subcase 4b) whose value is close to u i .The main technical challenge arises in order to generalize the pegging idea when a candidate i ∈ H arrives but one of the fairness conditions does not hold. Indeed, it is not clear if we should reject i and peg a future candidate or accept i. Consider an instance where the prediction error is high enough so that when i arrives there is always a future candidate that can be pegged and consider the case where t i < 1/2. If we accept then we may decrease our budget too aggressively until time 1/2 and do not have enough space in our solution to accept candidates not in [k] in the second half of the time.However, if we do not accept then we do not give i the possibility of being accepted in the first half of the time and we may decrease its probability of being accepted too much. K-PEGGING balances these two objectives while achieving smoothness by accepting a solution set S with values that are pairwise "close" to the values of candidates in {1, 2, . . . , k}. We prove the latter in lemma 8 by defining an injective function m(•) from set S to {1, 2, . . . , k} such that for each j ∈ S, u j ≈ u m(j) . Finally, we note that the running time of this algorithm is also O(n log n). 
experiments: 
 We simulate our ADDITIVE-PEGGING and MULTIPLICATIVE-PEGGING algorithms in the exact experimental setup of Fujii and Yoshida [25] , to test its average-case performance.Experimental Setup. Fujii and Yoshida [25] generate various types of instances. We follow their Almost-constant, Uniform, and Adversarial types of instances, and also create the Unfair type of instance to further highlight how slightly biased predictions can lead to very unfair outcomes. Both true and predicted values of candidates in all these instance types are parameterized by a scalar ε ∈ [0, 1) which controls the prediction error. Setting ε = 0 creates instances with perfect predictions and setting a higher value of ε creates instances with more erroneous predictions. Almost-constant models a situation where one candidate has a true value of 1/(1 -ε) and the rest of the candidates have a value of 1. All predictions are set to 1. In Uniform we sample each u i independently from the exponential distribution with parameter 1. The exponential distribution generates a large value with a small probability and consequently models a situation where one candidate is significantly better than the rest. All predicted values are generated by perturbing the actual value with the uniform distribution, i.e., ûi = δ i • u i , where δ i is sampled uniformly and independently from[1 -ε, 1 + ε].In Adversarial the true values are again independent samples from the exponential distribution with parameter 1. The predictions are "adversarially" perturbed while maintaining the error to be at most ε in the following manner: if i belongs to the top half of candidates in terms of true value, then ûi = (1 -ε) • u i ; if i belongs to the bottom half, then ûi = (1 + ε) • u i . Finally, in Unfair all candidates have values that are at most a (1 + ε) multiplicative factor apart. Formally, u i is a uniform value in [1 -ε/4, 1 + ε/4], and since (1 + ε/4)/(1 -ε/4) ≤ (1 + ε) we have that the smallest and largest value are indeed very close. We set ûi = u n-r(i)+1 where r(i) is the rank of u i , i.e., predictions create a completely inverted order.We compare ADDITIVE-PEGGING and MULTIPLICATIVE-PEGGING against LEARNED-DYNKIN [25], HIGHEST-PREDICTION which always accepts the candidate with the highest prediction, and the classical DYNKIN algorithm which does not use the predictions. Following [25] , we set the number of candidates to be n = 100. We experiment with all values of ε in {0, 1/20, 2/20, . . . , 19/20}. For each type of instance and value of ε in this set, we randomly generate 10000 instances, and then run each algorithm on each instance. For each algorithm, we consider instance-wise the ratio of the true value it accepted to the maximum true value, calling the average of this ratio across the 10000 instances its competitive ratio. For each algorithm, we consider the fraction of the 10000 instances on which it successfully accepted the candidate with the highest true value, calling this fraction its fairness. We report the competitive ratio and fairness of each algorithm, for each type of instance and each value of ε, in Figure 1 . Our code is written in Python 3.11.5 and we conduct experiments on an M3 Pro CPU with 18 GB of RAM. The total runtime is less than 5 minutes.Results. The results are summarized in figure 1 . Since ADDITIVE-PEGGING and MULTIPLICATIVE-PEGGING achieve almost the same competitive ratio and fairness for all instance types and values of ε we only present ADDITIVE-PEGGING in figure 1 but include the code of both in the supplementary material. Our algorithms are consistently either the best or close to the best in terms of both competitive ratio and fairness for all different pairs of instance types and ε values. Before discussing the results of each instance type individually it is instructive to mention some characteristics of our benchmarks. While DYNKIN does not use predictions and is therefore bound to suboptimal competitive ratios when predictions are accurate, we note that it accepts the maximum value candidate with probability at least 1/e, i.e., it is 1/e-fair. When predictions are non-informative this is an upper bound on the attainable fairness for any algorithm whether it uses predictions or not. HIGHEST-PREDICTION is expected to perform well when the highest prediction matches the true highest value candidate and poorly when the latter is not true. In Almost-constant for small values of ε all candidates have very close true values and all algorithms except DYNKIN have a competitive ratio close to 1. DYNKIN may not accept any candidate and this is why its performance is poorer than the rest of the algorithms. Note that as ε increases both our algorithms perform significantly better than all other benchmarks.In terms of fairness, predictions do not offer any information regarding the ordinal comparison between candidates' true values and this is why for small values of ε the probability of HIGHEST-PREDICTION and LEARNED-DYNKIN of accepting the best candidate is close to 1/100 = 1/n, i.e., random. Here, the fairness of our algorithms and DYNKIN is similar and close to 1/e. In both Uniform and Adversarial we observe that for small values of ε the highest predicted candidate is the true highest and ADDITIVE-PEGGING , LEARNED-DYNKIN and HIGHEST-PREDICTION all accept that candidate having a very close performance both in terms of fairness and competitive ratio. For higher values of ε the fairness of those algorithms deteriorates similarly and it approaches again 0.37 ≃ 1/e. In Unfair our algorithms outperform all other benchmarks in terms of competitive ratio for all values of ε and achieve a close to optimal fairness. This is expected as our algorithms are particularly suited for cases where predictions may be accurate but unfair.Overall, our algorithms are the best-performing and most robust. The HIGHEST-PREDICTION algorithm does perform slightly better on Uniform instances and Adversarial instances under most values of ε, but performs consistently worse on Almost-constant and Unfair instances, especially in terms of fairness. Our algorithms perform better than LEARNED-DYNKIN in almost all situations. 
limitations: 
 We study a notion of fairness that is tailored to the secretary problem with predictions and build our algorithms based on this notion. However, there are alternative notions of fairness one could consider in applications such as hiring, as well as variations of the secretary problem that capture other features in these applications. While our model allows for arbitrary bias in the predictions we assume that the true value of a candidate is fully discovered upon arrival, and define fairness based on hiring the best candidate (who has the highest true value) with a reasonable probability. Thus, we ignore considerations such as bias in how we get the true value of a candidate (e.g., via an interview process). In addition, as noted in Section 1, we use an individual fairness notion which does not model other natural desiderata like hiring from underprivileged populations or balance the hiring probabilities across different populations. These are considerations with potentially high societal impact which our algorithms do not consider and are interesting directions for future work on fair selection with predictions.Regarding trade-offs in our guarantees: for the single-secretary problem, we can improve the fairness guarantee from 1/16 to 0.074 by optimizing the constants in our algorithm. However, we choose not to do so, as the performance increase is marginal, and we aim to keep the proof as simple as possible. Additionally, any constant C for smoothness implies an upper bound of F = 0.348 for fairness. The proof of this follows from Fujii and Yoshida [25] , which shows that for any constant C, there is no randomized algorithm with a competitive ratio better than max{1 -Cϵ, 0.348}. Since a C-smooth and F -fair algorithm has a competitive ratio of at least max{1 -Cϵ, F }, their impossibility result implies that the best achievable fairness for any C-smooth (where C is a constant) algorithm is F = 0.348. Exploring other trade-offs and finding the Pareto-optimal curve in terms of smoothness and fairness are interesting directions. The main challenge in achieving a smooth trade-off between fairness and smoothness is as follows: any bound on C for smoothness implies a competitive ratio of 1 -Cϵ, which reaches a ratio of 1 when the predictions are exactly correct. Thus, regardless of the smoothness guarantee, we must achieve a competitive ratio of 1 when predictions are fully accurate. This constraint makes it challenging to improve the fairness guarantee F , even at the cost of a less favorable smoothness constant C.In this section we present the learning-augmented algorithms of [2] and [25] , and argue that they fail to satisfy simultaneously the smoothness and fairness desiderata described in section 2. We follow the same notation as in the main paper where the i * , î denote the index of the candidate with maximum true and predicted value respectively. Since the algorithm in [2] requires only the prediction about the maximum value but not the identity of that candidate, we use the symbol û * to denote such value.Algorithm 3 LEARNED-DYNKIN [25] θ ← 0.646, t ← 0.313, mode ← Prediction while agent i arrives at timet i do τ ← max j≺i u j if |1 -ûi /u i | > θ then mode ← Secretary. if mode = Prediction and i = î then A ← i. if mode = Secretary and t i > t and u i > τ then A ← i. Algorithm 4 VALUE-MAXIMIZATION SECRETARY [2] t * ← exp{W -1 (-1/(ce))}, t * * ← exp{W 0 (-1/(ce))} while agent i arrives at time t i do τ I ← max j:tj <t * u j if t * < t i < t * * and u i > max {τ * , û * -λ} then A ← i τ * * ← max j:tj <t * * u j if t i ≥ t * * and u i > τ * * then A ← iLEARNED-DYNKIN of Fujii and Yoshida [25] receives a predicted valuation for all candidates and defines the prediction error of candidate i as |1 -ûi /u i |. If the prediction error of a candidate is higher than θ then it switches to Secretary mode where it mimics the classical DYNKIN algorithm where all candidates are rejected for a constant fraction of the stream and after that rejection phase the first candidate whose valuation is the maximum overall is hired. Note that if all candidates have very low prediction error then LEARNED-DYNKIN remains in the Prediction mode and the candidate with the higher prediction is hired. One instance where LEARNED-DYNKIN never accepts candidate i * is the following: the true valuations are {1 + θ ′ , 1, u 3 , . . . , u n } and the predicted valuations are{1 + θ ′ , 1/(1 -θ ′ ), u 3 /(1 -θ ′ ), . . . , u n /(1 -θ ′ )}where θ ′ < θ = 0.646 and u 3 , . . . , u n are pairwise distinct numbers in (0, 1). Note that 1/(1 -θ ′ ) > 1 + θ ′ and the prediction error is as most θ ′ < θ = 0.616 for all candidates. Thus, LEARNED-DYNKIN does not switch to Prediction mode, it never accepts the candidate with valuation 1 + θ ′ and does not satisfy our Fairness desideratum. VALUE-MAXIMIZATION SECRETARY of [2] receives only one prediction regarding the maximum value û * and the prediction error is defined as ε = |u i * -û * |. The latter algorithm is parametrized by λ ≥ 0 and c ≥ 1 which control the relationship between the robustness and smoothness bounds. VALUE-MAXIMIZATION SECRETARY has three distinct phases defined by the time ranges [0, t * ], (t * , t * * ) and [t * * , 1] respectively, where t * , t * * are defined using the Lambert functions W -1 and W 0 . The first phase is used as an "exploration" phase where all candidates are rejected and at the end of the phase a threshold τ I is computed.Let A be the random variable denoting the candidate which is accepted by VALUE-MAXIMIZATION SECRETARY . For any ε ∈ (0, 1) we define an instance with predicted maximum value û * = 1-ε and true values {u 1 , u 2 , . . . , u n } where all numbers are distinct, u 1 = 1 and u i ∈ [0, ε] , ∀i ∈ {2, . . . , n}. The prediction error of that instance is ε. Note that if i * = 1 arrives in the first phase then the maximum value of a candidate that VALUE-MAXIMIZATION SECRETARY can accept in the second and third phases is at most ε. Thus, we can upper bound the expected value of candidate A as follows:E[u A ] ≤ P [t i * ≥ t * ] • u i * + P [t i * < t * ] • ε = (1 -t * )u i * + t * ε.We emphasize that in the learning-augmented setting, there is no assumption regarding the quality of the prediction, thus the parameters c and λ cannot depend on the prediction error. For any setting with c > 1 we have that t * > 0 is a constant that is bounded away from 0. Towards a contradiction, assume that VALUE-MAXIMIZATION SECRETARY satisfies the smoothness desideratum described in section 2 for some parameter C. Then, we have thatE[u A ] ≥ (1 -C • ε)u i * . Consequently, (1 -t * )u i * + t * ε ≥ (1 -C • ε)u i * u i * =1 = === ⇒ (1 -t * ) + t * ε ≥ (1 -C • ε) which leads to contradiction when we let ε - → 0.In this subsection we generalize the ADDITIVE-PEGGING algorithm so as to provide fair and smooth algorithms for different prediction error definitions. We use the direct sum symbol ⊕ to abstractly denote an operation, e.g., addition or multiplication, and ⊖ for its inverse operation, i.e., subtraction or division. To model the "difference" between predictions and true values we use two functionsd + : ℜ ≥0 × ℜ ≥0 - → ℜ and d -: ℜ ≥0 × ℜ ≥0 - → ℜ.The natural properties that we require from d + , d -with respect to operations ⊕ and ⊖ are described in assumption 6. We writed + i = d + (u i , ûi ), d - i = d -(u i , ûi) and define two prediction errors as follows:ε + = max i d + i and ε -= min i d - i .While the notation is left abstract to highlight the generality of theorem 7, we provide examples on how to instantiate those functions and operators for natural prediction errors as the absolute difference that we used in ADDITIVE-PEGGING and a multiplicative prediction error function that it is used by Fujii and Yoshida [25] .The only properties that we require from those functions with respect to operations ⊕ and ⊖ are described by assumption 6.Assumption 6. For all u, û, v, v, x, y ∈ ℜ ≥0 u ⊕ d + (u, û) ≥ û ≥ u ⊕ d -(u, û) (1) d + (u, û) ≥ d + (v, v) ⇔ d -(u, û) ≤ d -(v, v) (2) x ⊕ d -(u, û) ≥ y ⇔ x ≥ y ⊖ d -(u, û) and x ⊕ d + (u, û) ≥ y ⇔ x ≥ y ⊖ d + (u, û) (3) x ⊖ d -(u, û) ≥ y ⇔ x ≥ y ⊕ d -(u, û) and x ⊖ d + (u, û) ≥ y ⇔ x ≥ y ⊕ d + (u, û) (4)The first property permits us to upper and lower bound the prediction of a candidate with respect to its true value, the second property relates the functions d + and d -and the last two properties permit us to manipulate inequalities between true and predicted valuations.Using the new abstract notation we describe how one can generalize ADDITIVE-PEGGING to PEGGING by only changing the conditions of subcases 2a, 2b and 4b. In subcase 2a and 2b we do not have a strong indication that î is the true highest value candidate. Thus we "peg" a future candidate only if it is possible to maintain smoothness, or equivalently, if there is a future candidate whose predicted value is higher than u i * scaled down by the prediction error. Thus, we change the condition of subcase 2a to u î ⊕ d - î > max j≻i ûj and subcase 2b in the same manner. In subcase 4b, we have a strong indication of i ̸ = î being the true highest value candidate and we accept if u i scaled up by the prediction error is higher than ûî . Using our abstract notation this is equivalent to checking ifu i ⊕ d + i > ûî .Algorithm 5 PEGGING while agent i arrives at time t i do τ ← max j≺i u j case 1:i = i pegged A ← i case 2: i = î and (t î ≤ 1/2 or u î < τ ) subcase 2a: u î ⊕ d - î ≥ max j≻i ûj A ← î subcase 2b: u î ⊕ d - i < max j≻i ûj i pegged ← max ≻ {j : u î ⊕ d - i < ûj } case 3: i = î and t î > 1/2 and u î > τ A ← î case 4: i ̸ = î and t i > 1/2 and u i > τ subcase 4a: î has already arrived A ← i subcase 4b: u i ⊕ d + i > ûî A ← i Note: max ≻ {j : u î ⊕ d -i < ûj } denotes the last candidate j arriving and having its prediction lower bounded by u î ⊕ d - i . We cannot assign i pegged at time t î since we do not know when the last candidate with this property will arrive. We abuse notation ←to say that as long as there is a future candidate with that property, we update i pegged . We assume that every time a candidate arrives at most one case and one subcase is executed and the algorithm terminates whenever we execute a A ← i command, i.e., a candidate is accepted.We proceed stating and proving Theorem 3. Theorem 7. PEGGING accepts the maximum value candidate with probability at least 1 16 and its expected value is at leastmax{u i * ⊕ ε -⊕ ε -⊖ ε + ⊖ ε + , 1 16 u i * }Proof. We first lower bound ûî using the right-hand side of (1) from assumption 6 and the fact that î is the candidate with the maximum predicted valuation: ûî ≥ ûi * ≥ u i * ⊕ d - i * . We also lower bound u î as follows: from the left-hand side of (1) from assumption 6 we get that u î ⊕ d + î ≥ ûî = ⇒ u î ≥ ûî ⊖ d + î . Thus, also using the lower bound ûî ≥ u i * ⊕ d - i * we have:u î ≥ ûî ⊖ d + î ≥ u i * ⊕ d - i * ⊖ d + îIn subcase 2a and case 3 candidate î is accepted and in subcase 4a a candidate i with u i ≥ u î is accepted. Consequently, all these cases accept a candidate with value at leastu î ≥ u i * ⊕ d - i * ⊖ d + î . If i is accepted by subcase 4b we get that u i ⊕ d + i > ûî = ⇒ u i > ûî ⊖ d + i and again using that ûî ≥ u i * ⊕ d - i * we have u i > u i * ⊕ d - i * ⊖ d + i .Finally, we need to lower bound the value of a pegged candidate in case our algorithm terminates accepting i pegged . Note that from the way a pegged candidate is defined in subcase 2b, we always have u î ⊕ d - î < ûi pegged and again using the left-hand side of (1) from assumption 6 we have thatûi pegged ≤ u i pegged ⊕ d + i pegged = ⇒ u i pegged ≥ ûi pegged ⊖ d + i pegged . Thus, we get that u i pegged > u î ⊕ d - î ⊖ d + i peggedand using the lower bound on u î we conclude thatu i pegged > u i * ⊕ d - i * ⊖ d + î ⊕ d - î ⊖ d + i pegged .Combining all the lower bounds on the valuation of the accepted candidate deduce the first part of the lower bound.We proceed proving fairness and, consequently robustness. We denote by ĩ the index of the candidate with the highest true valuation except possibly i * and î, i.e., ĩ = argmax i̸ =i * ,î u i . Note that if i * = î then ĩ denotes the index of the candidate with the second highest true valuation. To prove fairness we distinguish between two cases: either î = i * or î ̸ = i * . For each of those cases, we define an event and argue that: (1) the event happens with constant probability; and (2) if that event happens then Algorithm 5 accepts i * .If i * = î we define event C = {t ĩ < 1/2 < t i * } for which P [C] = 1/4. C implies that our algorithm does not accept any candidate until time t i * . Indeed note that the conditions of case 1, 2, and 3 all happen after the arrival of î which is t i * . In addition to that after time 1/2 the threshold τ = u ĩ is larger than any valuation other than u i * and consequently the conditions of case 4 are not met before t i * . At time t i * all conditions of case 4 and subcase 4a are met and our algorithm hires i * .If i * ̸ = î we further distinguish between two cases. To that end, note that{u î ⊕ d - î < ûi * } ∨ {d + i * ⊕ u i * > ûî } is always true. Indeed if {u î ⊕ d - î > ûi * } we have that: u î ⊕ d - î > ûi * u î ⊕ d - î > u i * ⊕ d - i * d - î ⊖ d - i * > u i * ⊖ u î d - î ⊖ d - i * > 0 d - î > d - i * d + î < d + i *where 0 is the neutral element associated with operation ⊕, from the first to the second line we used the right-hand side of (1) from assumption 6, from the third to the fourth line we used that u i * ≥ u î by the definition of i * and from the fifth to the sixth line we used (2) of assumption 6. Consequently:d + i * ⊕ u i * > d + î ⊕ u i * ≥ d + î ⊕ u î ≥ ûîwhere we again used that u i * ≥ u î and in the last inequality we used the right-hand side of (1) from assumption 6.Thus, we define two events C 1 and C 2 which imply that i * is always accepted whenever {u î ⊕ d - î < ûi * } and {d + i * ⊕ u i * > ûî } are true respectively. If {u î ⊕ d - î < ûi * } is true then we define event C 1 = {t ĩ < 1/2} ∧ {t î < 1/2} ∧ {1/2 < t i * } which is composed by 3 independent events and it happens with probability P [C 1 ] = 1/2 3 = 1/8. C 1 implies that at time t i * the conditions of subcase 4a are satisfied. Consequently, if until time t i * all candidates are rejected then candidate i * is hired using either case 1 or subcase 4a. To argue that no candidate is hired before time t i * note that at time t î the set max ≻ {j : u î < ûj + ϵ î} contains i * and that after time 1/2 the condition τ > u i is not met until time t i * .+ i * ⊕ u i * > ûî } is true then we define C 2 = {t ĩ < 1/2 < t i * < t î} which happens with probability P [C 2 ] = P [t ĩ < 1/2] • P [1/2 < t i * < t î] = = P [t ĩ < 1/2] • P [1/2 < min{t i * , t î} ∧ min{t i * , t î} = t i * ] = = P [t ĩ < 1/2] • P [1/2 < min{t i * , t î}] • P [min{t i * , t î} = t i * ] = = (1/2) • (1/4) • (1/2) = = 1/16Note that until time t i * no candidate is accepted since the conditions of all cases are not satisfied. Indeed, between times 0 and 1/2 only î could have been accepted but its arrival time is after t i * , and between times 1/2 and t i * the threshold τ is equal to u ĩ and no candidate meets the condition of case 4 to have u i > τ . Finally, note that at time t i * the conditions of case 4b are satisfied and i * gets accepted.Note that by instantiating ⊕, ⊖ to the usual scalar addition and subtraction and d+ (u, û) = |u -û|, d -(u, û) = -|u -û| we get that d + i = ϵ i , d - i = -ϵ i .Consequently, ε + = max i ϵ i and ε -= -max i ϵ i . Substituting ε + and ε -to the guarantees of theorem 7 we recover theorem 3.Moreover, in theorem 4, we further demonstrate the generality of PEGGING by instantiating ⊕, ⊖, d + , d -and recovering similar smoothness and robustness bounds as [25] while also ensuring fairness. Fujii and Yoshida [25] define the prediction error as ε = max i |1 -ûi /u i | and design an algorithm which accepts a candidate i whose expected value is at leastu i * max {(1 -ε)/(1 + ε), 0.215}. Since (1 -ε)/(1 + ε) ≥ 1 -2 εthe latter algorithm satisfies the Smoothness desideratum of section 2, but, as we prove in appendix A.1 it violates the Fairness desideratum.To that end, let MULTIPLICATIVE-PEGGING be the instantiation of PEGGING when ⊕, ⊖ denote the classical multiplication and division operations, Proof. Functions d + , d -satisfy the properties of assumption 6. Note that ε + = 1 + ε and ε -= max {1 -ε, 0}. Consequently, using theorem 7 MULTIPLICATIVE-PEGGING accepts a candidate whose expected value is at leastu i * max (1 -ε) 2 /(1 + ε) 2 , 1/16 ≥ u i * max {1 -4 ε, 1/16},where we used the inequalities1/(1 + ε) ≥ (1 -ε) and (1 -ε) 4 ≥ 1 -4 ε.In Lemma 8 and Corollary 9 we prove that K-PEGGING satisfies the smoothness desideratum.j∈S u j ≥ k i=1 u ri -4k ε(I) , ∀I with probability 1.Proof. Similarly to the single choice secretary problem we proceed in two steps, first we prove that:i∈[k] u ri - i∈[k] u i ≤ 2k εand then we prove thati∈[k] u i - j∈S u j ≤ 2k εNote that combining those two inequalities is enough to prove the current lemma.The first inequality is proven as follows:k i=1 u ri ≤ (1) k i=1 (û ri + ε) ≤ (2) k ε + k i=1 ûi ≤ (3) k ε + k i=1 (u i + ε) = 2k ε + k i=1 u iwhere (1) and (3) are by definition of ε and (2) since ûi is i th largest predicted value.We proceed to argue that:i∈[k] u i - j∈S u j ≤ 2k εWe now define an injective function m : [k] -→ S for which we have:u i -u m(i) ≤ 2 ε, ∀i ∈ [k]Note that the existence of such a function implies the desired i∈[k] u i -j∈H u j ≤ 2k ε inequality.Note that each candidate j ′ ∈ [k] is initially added to H. During the execution of our algorithm candidate j ′ may be either (1) deleted from H without being added to B or (2) added to B.In the first case, j ′ is deleted from H without being added to B, which occurs either in case 2a, 3, or 4b of the algorithm. Let i be the current candidate at the time t i where the latter happens. If case 2a or 3 happens then j ′ = i, we define m(j ′ ) = j ′ and u j ′ -u m(j ′ ) = 0 ≤ 2 ε. If case 4b happens then we have that at that time t i : j ′ ∈ {j ∈ H : u i > ûj -ε ti } and we define m(i) = j ′ . Consequently, we conclude thatu i -u m(i) = u i -u j ′ ≤ u i -ûj ′ + ε t j ′ ≤ ε i +ε t j ′ ≤ 2 ε.We now consider the cases where j ′ is added to B during the execution of our algorithm. Note that for that to happen j must be added to B at time t j via case 2b. In that case, candidate peg(j ′ ) either remains in P until time t peg(j ′ ) and it is added to S at that time or it is deleted from P earlier. In both cases j ′ is removed from B at the respective time. Thus, we conclude that j ′ gets deleted from B at time t peg(j ′ ) or before. If the deletion happens at time t peg(j) then it must happen through case 1, we define m(j ′ ) = peg(j ′ ) and we have thatu j ′ -u m(j ′ ) = u j ′ -u peg(j ′ ) ≤ ûpeg(j ′ ) + ε t j ′ -u peg(j ′ ) = (û peg(j ′ ) -u peg(j ′ ) ) + ε t j ′ ≤ ε peg(j ′ ) +ε t j ′ ≤ 2 ε, where in the first inequality we used that ûpeg(j ′ ) > u j ′ -ε t j ′ since peg(j ′ ) was pegged by j ′ at time t j ′ . If j ′ is deleted from B before time t peg(j ′ ) it must happen via subcase 4a due to the arrival of a candidate l that is added to S. In that case we define m(j ′ ) = l and from the condition of subcase 4a we have that j ∈ E at time t j ′ we have thatu j ′ -u m(j ′ ) = u j ′ -u l < 0 ≤ 2 ε.Corollary 9. If u ri ≥ 1 ∀i ∈ {1, ..., k} then:j∈S u j ≥ k i=1 u ri (1 -4 ε(I)) , ∀I with probability 1.Proof. The proof follows from lemma 8 and noting that u ri ≥ 1 implies thatk i=1 u ri ≥ k and consequently k i=1 u ri -4k ε(I) ≥ k i=1 u ri (1 -4 ε(I)).We now move to prove the fairness desideratum.Lemma 10. For all i ∈ [k]: P [r i ∈ S] ≥ (1/3) k+5Proof. We start arguing that if r i ∈ [k], i.e., if candidate r i is among the k-highest prediction candidates, then P [r i ∈ S] ≥ 1/4. We define event C = {t ri < 1/2} ∧ {C ri = 0} for whichP [C] = P [t ri < 1/2] • P [C ri = 0] = (1/2) • (1/2) = 1/4Note that at time 0 we have that r i ∈ H. During the execution of Algorithm 2 from time 0 to time t ri , candidate r i may be removed from H without being added from S only if t ri ≥ 1/2. Consequently, C implies that at time t ri < 1/2 the conditions of case 2 and subcase 2a are true and candidate r i is added to S. Thus,P [r i ∈ S] ≥ P [C] = 1/4.In the rest of the proof, we focus on the case wherer i ̸ ∈ [k]. Note that since i ∈ [k] and r i ̸ ∈ [k] then ∃j ∈ [k] such that u ri ≥ u r k > u j , i.e., j has a true value which is not among the k-highest true values. We now argue that {u j < ûri + ε j } ∨ {u ri > ûj -ε ri } is always true. Similarly to the proof of lemma 2, assume towards a contradiction that both inequalities can be inverted and hold at the same time, then we end up in a contradiction as follows:u j ≥ ûri + ε j ur i >uj = ==== ⇒ u ri > ûri + ε j = ⇒ u ri -ûri > ε j εr i ≥ur i -ûr i ========⇒ ε ri > ε j u ri ≤ ûj -ε ri uj <ur i = ==== ⇒ u j < ûj -ε ri = ⇒ ε ri < ûj -u j εj ≥ûj -uj = ====== ⇒ ε ri < ε jFor each of those cases, i.e., whether {u j < ûri + ε j } or {u ri > ûj -ε ri } is true we define an event which implies that r i is added to the solution set S.If {u ri > ûj -ε ri } is true then we define the following event:C = (l):l∈[k+2]\{ri∪j} {t l < 1/2} ∧ {1/2 < t ri < t j } Let F j denote the set of all non-empty subsets of [n] such that P [F j = f j | T ] > 0. Note that P [F j = ∅ | T ] + fj ∈Fj P [F j = f j | T ] = 1.In addition, to alleviate notation we denote l fj = argmin j ′ ∈fj ûj ′ .From the law of total probability we have:EQUATIONwhere from ( 2) to (3) we use that if F j = ∅ then the condition of subcase 2b is false, thus no candidate is "pegged" and consequently t peg(j) = ∞. From ( 3) to ( 4) we used that {F j ̸ = ∅} = fj ∈Fj {F j = f j }. From ( 5) to ( 6) we used that event {F j = f j } ∧ T implies that conditions of case 2 and subcase 2b are true and consequently peg(j) = l fj by the definition of l fj .We now focus on lower bounding the summation termfj ∈Fj P t l f j ≥ t ri | {F j = f j } ∧ T • P [F j = f j | T ] = fj ∈Fj :l f j =ri P t l f j ≥ t ri | {F j = f j } ∧ T • P [F j = f j | T ]+ + fj ∈Fj :l f j ̸ =ri P t l f j ≥ t ri | {F j = f j } ∧ T • P [F j = f j | T ] = fj ∈Fj :l f j =ri P [t ri ≥ t ri | {F j = f j } ∧ T ] • P [F j = f j | T ]+ + fj ∈Fj :l f j ̸ =ri P t l f j ≥ t ri | {F j = f j } ∧ T • P [F j = f j | T ] = fj ∈Fj :l f j =ri 1 • P [F j = f j | T ] + fj ∈Fj :l f j ̸ =ri P t l f j ≥ t ri | {F j = f j } ∧ T • P [F j = f j | T ]We proceed lower bounding the term P t l f j ≥ t ri | {F j = f j } ∧ T for all f j ∈ F j : l fj ̸ = r i . Note that the conditioning {F j = f j } ∧ T changes the distribution of random variables t l f j , t ri as follows: t ri is uniformly drawn from [1/2, 1] and t l f j is uniformly drawn from [z, 1] for some z ∈ [1/3, 1/2] which equals the realization of the random variable t j . We define a random variable tl f j which is stochastically dominated by t l f j and is drawn uniformly from [1/3, 1] as follows: let t be uniformly drawn from [1/3, z] and B ∼ Bernoulli((z -1/3)/(1/2 -1/3)) then we define:tl f j = B • t + (1 -B) • t l f jNote that since t ≤ t l f j then also tl f j ≤ t l f j holds almost surely.Therefore we have:P t l f j ≥ t ri | {F j = f j } ∧ T ≥ P tl f j ≥ t ri | {F j = f j } ∧ T ≥ 2/3and we proceed bounding the initial summation as follows:fj ∈Fj P t l f j ≥ t ri | {F j = f j } ∧ T • P [F j = f j | T ] = = fj ∈Fj :l f j =ri 1 • P [F j = f j | T ] + fj ∈Fj :l f j ̸ =ri P t l f j ≥ t ri | {F j = f j } ∧ T • P [F j = f j | T ] ≥ fj ∈Fj :l f j =ri 1 • P [F j = f j | T ] + fj ∈Fj :l f j ̸ =ri (2/3) • P [F j = f j | T ] ≥ (2/3) fj ∈Fj P [F j = f j | T ]We then have:EQUATIONEQUATIONEQUATIONWe are now ready to lower bound the probability of event C as followsP [C] = P [T ] • P t peg(j) ≥ t ri | T ≥ P [T ] • (2/3) = (l):l∈[k+1]\{ri,j} P [t l < 1/3] • P [1/3 < t j < 1/2] • (2/3) ≥ (1/3) k • (1/2 -1/3) • (2/3) = (1/3) k+2Similar to the analysis of the first case the first literal of C ensures that the only candidate which may be accepted after time 1/2 without being at any point in time in the pegging set P is r i . In addition, since t j < 1/2 then we have that j remains in H until at least time t j . Indeed, a candidate in H that has not arrived yet may be removed from set H only through case 4b which happens exclusively after time 1/2. We now analyze C's implications regarding the execution of our algorithm at j's arrival by distinguishing between two mutually exclusive cases, that is whether r i is in P before time t j or not.If r i is not in the pegging set exactly before time t j then we have that the conditions of case 2b are true. Indeed note that {C j = 1} is a literal of C and since ε j ≤ ε tj we have:{j ′ ≻ j : u j < ûj ′ + ε tj } \ (P ∪ [k]) ⊇ {j ′ ≻ j : u j < ûj ′ + ε j } \ (P ∪ [k]) ∋ r iThus, we are in the case where at time t j a candidate (which may be r i ) is added to the pegging set, candidate j is added to B and t peg(j) < ∞. Due to the literal t peg(j) ≥ t ri of C and the fact that the only candidate which may be accepted after time 1/2 without being at any point in time in the pegging set P is r i , we can deduce that at time t ri j is still in B. Thus, at time t ri the conditions of subcase 4a are true and r i is added to S. If r i is in the pegging set exactly before time t j then since the conditions of case 4 are false for any candidate except possibly r i we can deduce that at time t ri , candidate r i is still in the pegging set P and is added to the solution through case 1.Combining all the different lower bounds on P [r i ∈ S] we conclude the lemma.Lemma 11. For all i ∈ {1, 2, . . . , k}:P [r i ∈ S] ≥ 1-i+13 k 256Proof. Let δ ′ > 12/k be such that i < (1 -δ ′ )k -1. We now argue that proving P [r i ∈ S] ≥ δ ′ /256 suffices to prove the lemma.First, we underline that such a δ ′ exists only for i < k -13. Indeed,i < (1 -δ ′ )k -1 = ⇒ δ ′ < 1 - i + 1 k δ ′ >12/k =====⇒ i < k -13For all i < k -13 we have:P [r i ∈ S] ≥ δ ′ /256 > 1 -i+1 k 256 > 1 -i+13 k 256For i ≥ k -13 the statement of the lemma is vacuous, since:P [r i ∈ S] ≥ 0 ≥ 1 -i+13 k 256Consequently, from now on we focus on proving that P [r i ∈ S] ≥ δ ′ /256. We do so by defining an event C for which P [C] ≥ δ ′ /256 and argue that C implies r i being accepted.Before defining C we need to introduce some auxiliary notation. We call replacement set and denote by R the set of indexes initially in H with value lower than u ri , i.e., R = {j :u ri > u j } ∩ [k]and by j worse = argmax j∈R ε j the index of the candidate with the highest error in R. For any t, t ′ ∈ [0, 1] we define the random variable A t,t ′ = {j : t ≤ t j ≤ t ′ } \ {r i , j worse } which contains all indexes except r i and j worse of candidates arrived between times t and t ′ . Also, for x ∈ [n] we define the set function L x : 2 [n] -→ 2 [n] , such that for any subset Y ⊆ [n], L x (Y ) contains the x indexes with highest true value in Y . For δ ∈ (0, 1/2) let (a) R 1 = R ∩ A 0,1/2+δ and R 2 = R ∩ A 1/2+δ,1 be the random variables denoting all candidates of R \ {j worse } arriving before and after time 1/2 + δ respectively; and (b) let M = L ⌊(1+4δ)k⌋ (A 0,1/2+δ ) ∩ A 1/2,1/2+δ denote the random variable containing candidates which arrived between times 1/2 and 1/2 + δ with the ⌊(1 + 4δ)k⌋ higher true value among the ones arrived before time 1/2 + δ (excluding r i and j worse ).We now define event C.C = {|R 2 | -|M | > 1} ∧ {1/2 < t ri < 1/2 + δ} ∧ {t j worse < t ri }Note that M contains all candidates not in H that may be added to our solution between times 1/2 and 1/2 + δ. In addition, each candidate in M through subcase 4b may delete from H at most one candidate with arrival time after 1/2 + δ.Consequently, the number of candidates in R that are in H until time1/2+δ is at least |R 2 |-|M | > 1.We now argue that conditions of subcase 4b are true at time t ri . Indeed, note that since t j worse < t ri we have that ε tr i > ε j worse and consequently, for every candidate j of R we have thatu ri > u j ≥ ûj -ε j ≥ ûj -ε j worse ≥ ûj -ε tr iwhere the first inequality comes from the definition of set R, the second from the definition of the error, the third from the definition of j worse and the last from the fact that ε tr i > ε j worse . Since R 2 ⊆ R, we have that at time t ri there is at least one candidate j in H for which u ri ≥ ûj -ε tr i and the conditions of subcase 4a are therefore true.We now proceed lower bounding the probability of event C. Let δ = δ ′ /16 we first argue that{|R 2 | ≥ 1/2-2δ 1-δ δ ′ k} and |M | < 4δk implies that |R 2 | -|M | > 1.Indeed note that:|R 2 | -|M | > 1/2 -2δ 1 -δ δ ′ k -4δk > 1 3 δ ′ k -4δk > (δ ′ /3 -4δ)k ≥ (δ ′ /3 -4δ ′ /16)k ≥ (δ ′ /12)k > 1where in the second inequality we used that δ = δ ′ /16 ≤ 1/16 < 1/10.We now lower bound the probability of the intersection of events{|R 2 | ≥ 1/2-2δ 1-δ δ ′ k}, {|M | < 4δk}, {1/2 < t ri < 1/2 +δ} and {t j worse < 1/2} since their intersection implies event C.Since R 2 and M do not contain neither r i nor j worse we have that events{|R 2 | ≥ 1/2-2δ1-δ δ ′ k}, {|M | < 4δk} are independent of the time arrival of j worse and r i . Thus,P [C] = P {|R 2 | ≥ 1/2 -2δ 1 -δ δ ′ k} ∧ {|M | < 4δk} • P [1/2 < t ri < 1/2 + δ] • P [t j worse < 1/2] = P {|R 2 | ≥ 1/2 -2δ 1 -δ δ ′ k} ∧ {|M | < 4δk} • δ • (1/2) = (δ ′ /32) • P {|R 2 | ≥ 1/2 -2δ 1 -δ δ ′ k} ∧ {|M | < 4δk} = (δ ′ /32) • P {|R 1 | < |R| - 1/2 -2δ 1 -δ δ ′ k} ∧ {|M | < 4δk}We continue by lower bounding the second term of the last expression. We do so by defining a random variable M which is independent of R 1 and it is such that M stochastically dominates |M |.We prove the stochastic dominance of M using a coupling argument.Note that every candidate i accepts an arrival time t i uniformly at random from [0, 1]. We now describe an equivalent procedure to create the arrival times t i . Each candidate i draws three independent random variablesB i ∼ Bernoulli(1/2 + δ), t 1 i ∼ U nif orm([0, 1/2 + δ]) and t 2 i ∼ U nif orm([1/2 + δ, 1]). Note that we can construct random variables t i using B i , t 1 i and t 2 i as follows:t i = B i • t 1 i + (1 -B i ) • t 2 i Let l = |L (1+4δ)k (A 0,1/2+δ)| and denote by h 1 , . . . , h l the set of candidates in L (1+4δ)k (A 0,1/2+δ ).We define random variables t1 , . . . , t(1+4δ)k as follows: For each j ∈ {1, . . . , l} we define tj = t 1hj and for each j ∈ {l + 1, . . . , 1 + 4δk} we define tj ∼ U nif orm([0, 1/2 + δ]). We define M = ⌊(1+4δ)k⌋ i=1I tj > 1/2 and since M -|M | = ⌊(1+4δ)k⌋ i=l+1I tj > 1/2 we have that M ≥ |M | almost surely. Note that random variables tj and random variables B i are independent. Consequently, since |R 1 | = i∈R B i we have that events {M < y} and {|R 1 | < x} are independent. Combining these observations we have:P {|R 1 | < |R| - 1/2 -2δ 1 -δ δ ′ k} ∧ {|M | < 4δk} ≥P {|R 1 | < |R| - 1/2 -2δ 1 -δ δ ′ k} ∧ {M < 4δk} ≥P |R 1 | < |R| - 1/2 -2δ 1 -δ δ ′ k • P [M < 4δk] ≥P |R 2 | ≥ 1/2 -2δ 1 -δ δ ′ k • P [M < 4δk] To upper bound P [M < 4δk] note that E[M] = ⌊(1+4δ)k⌋• δ 1/2+δ < 3δk, where the last inequality holds for any δ < 1/2. From Markov's inequality, we have that:P [M > 4δk] = P [M > (4/3) • 3δk] ≤ P [M > (4/3) • E[M]] ≤ (3/4)ConsequentlyP [M < 4δk] > (1/4) Note that since i < (1 -δ ′ )k -1 we have that |R| ≥ δ ′ k + 1. E[|R 2 |] = |R \ {j worse }|(1 -1/2 -δ) ≥ δ ′ k(1/2 -δ)From Markov's inequality, we have that:P |R 2 | > 1/2 -2δ 1 -δ δ ′ k| ≥ P |R 2 | > 1/2 -2δ (1 -δ) • (1/2 -δ) • E[|R 2 |] ≥ (1 -δ) • (1/2 -δ) 1/2 -2δ = (1 -δ) • (1 -2δ) 1 -4δ ≥ (1 -δ)Consequently, Proof. The theorem follows directly from corollary 9 and lemmas 10 and 11.P [C] ≥ (δ ′ /32) • (1/4) • (1 -δ) ≥ (δ ′ /32) • (1/4) • (1/2) ≥ (δ ′ /256)In this section we present the competitive ratio achieved by each algorithm as a function of the parameter ε which controls the predictions error in each of the datasets defined in Section 5. Justification: Each claim in the contributions is made as a theorem statement which is formally proved in the main text together with the appendices.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] .Justification: The pseudocode and all details of our experimental setup are described in the main paper.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] .Justification: We present the mean and standard deviation of the competitive ratio for each dataset/prediction error/algorithm tuple in the experimental section of the appendix.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. Justification: Yes, we mention the characteristics of the CPU we used, its memory and the time of execution in the experiments section of the main paper.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] .Justification: Our research conforms with every aspect of the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] .Justification: In the introduction we discuss our fairness notion and how it relates to other fairness notions in the literature, and in the limitations section we discuss how different notions are required to capture different fairness considerations.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] . Justification: The paper poses no such risks. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [Yes] . Justification: We are the creators of the code. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [Yes] .Justification: We provide the code in the supplementary material.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] .Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] .Justification: The paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.38th Conference on Neural Information Processing Systems (NeurIPS 2024).This is without loss as adding an arbitrarily small perturbation to each true and predicted value does not change the performance of our algorithms. This perturbation is convenient because it allows to never have ties.Our bounds can be expressed less elegantly when only assuming that the values are non-negative; see Appendix A 
 
 Appendix:  


Decision: This paper studies algorithms for the well-known secretary problem in an optimizing with predictions framework, focusing mostly on providing theoretical analysis and guarantees and with some empirical demonstration. Reviewers found the paper to be novel and interesting, appreciated the consideration of fairness concerns and its particular manifestation in the proposed problem setup (although the authors are encouraged to make precise their notion of fairness as it relates to how "fairness" is generally thought of currently in the learning community), and found the results to be relevant and useful. Overall the paper is clearly written, well executed, and will likely inspire future interest in this problem (e.g., improved constants, upper bound) and in related problems.

Reviews: review: paper_summary: paper_summary: This paper proposes new algorithm for the classical secretary problem in the algorithms with predictions framework. In particular, the paper introduces and tackles a new notion of fairness for this problem: the best candidate must have some probability of being accepted. The authors demonstrate how existing algorithms for this problem in the algorithms with predictions setting might lead to outcomes where the best candidate has zero probability of being accepted, and go on prove results on "fairness" and competitive ratio of their proposed methods Specifically, their algorithm (called Pegging), keeps a constant approximation ratio while also ensuring constant fairness. The paper also includes some experiments comparing to existing methods on synthetic examples.
strength_weakness: strength_weakness: The main area for improvement is presentation. For instance, the key ideas behind the main algorithm are hard to understand and the reader is left trying to infer them by reading the pseudocode presented in Algorithm 1.
questions: questions: 1) Can you please define I_pegged formally? It is never defined and only mentioned at a high level in the preceding text. The reader is left confused when they reach case 1 of Algorithm 1, and ends up having to infer what this set is from case 2b (aka how are you deciding what the set of elements that would guarantee smoothness is). It is always better to help the reader. 

2) Can you clarify the refine and clarify initial conditions for Algorithm 1? It would greatly help with readability if the algorithm presentation followed the standard format with input to the algorithm, initial values, and return. For instance, initialize I_pegged to empty set. Somewhat pedantic, but the while loop is ill-defined with the condition 'agent i arrives at time t_i'; for t in 1...T do ... with returns is a lot more sensible.

3) In Figure 1, why does the competitive ratio of Dynkin go down with increasing epsilon? Shouldn't it be independent of prediction error?

4) I understand there might be space limitations, but it might be illuminating to have a simple example of unfairness of an existing methods at the end of Section 2 or early in Section 3 to better shed light on the shortcomings (instead to relegating everything to the appendix). Also, minor typos at the top of Page 3 incorrectly referencing [3] instead of [4].
limitations: limitations: Yes, limitations have been addressed.
paper_summary: paper_summary: This paper examines the secretary problem with predictions and identifies a key shortcoming in prior work.  This problem is similar to the classic secretary problem in which a series of candidates with arbitrary unknown utilities $u_i$ arrive in a random order to be interviewed (revealing their utility upon arrival), and a decision maker must make an accept-or-reject decision without knowledge of the utility of future arrivals.  For the problem considered in this paper, the decision maker also has access to predictions $\hat u_i$ of the candidates' utilities.  Prior work gave algorithms guaranteed to accept a candidate with utility at least $\max(\Omega(1), 1- O(\epsilon))$ times the highest utility in expectation, where $\epsilon$ is a notion of error in the predictions.  When $\epsilon$ is very small, this can potentially be more desirable than the classical secretary algorithm which accepts the best candidate with probability $1/e$.  While this guarantee is achieved by the prior work and desirable for the decision maker, this paper shows that they do not accept the best candidate with constant probability (in fact.  This can be seen as highly unfair to the candidate with the highest utility.  The first main result of this paper is an algorithm that satisfies both types of guarantees.  In addition to this, an extension to the $k$-secretary problem and an experimental evaluation are considered.
strength_weakness: strength_weakness: Upper bound (impossibility results) are not explored, making it unclear if these are the tightest results for this setting.  The experiment section only addresses the single-choice secretary problem (although this is minor since the experiments already make a strong point).
questions: questions: If we require $1-C\epsilon$-smoothness, does that imply an upper bound on the achievable $F$ for fairness, and vice-versa?
limitations: limitations: The authors have adequately discussed limitations regarding their definition of fairness.
paper_summary: paper_summary: This paper considers the secretary problem with predictions. The decision maker is given predicted values for all the candidates in advance. The existing algorithm by Fujii and Yoshida (2023) hires the candidate with the **expected value** at least $\max ( \Omega(1), 1-O(\epsilon) )$ times the optimal candidate's value, where $\epsilon$ is the prediction error. On the other hand, the classical secretary algorithm hires the best candidate **with probability** $\Omega(1)$. Since hiring the best one with probability $p$ yields the expected value at least $p$ times the optimal value, the probability bound is stronger than the value bound.

This paper proposes an algorithm that hires the best candidate with probability $\Omega(1)$ and achieves the expected value at least $1-O(\epsilon)$ times the optimal. For the extension of hiring $k$ candidates, the proposed algorithm hires each of the top-$k$ candidates with probability depending on $k$ and achieves the expected value at least $1-O(\epsilon)$ times the optimal. The experimental results show the proposed algorithm outperforms the existing method in various benchmark instances.
strength_weakness: strength_weakness: - In this paper, hiring the best candidate with probability $\Omega(1)$ is called ``fair.'' Although I am not familiar with the existing literature on fairness, I do not fully understand why the authors adopt this terminology. In algorithmic studies on the secretary problem, the probability maximization and value maximization are considered as two important settings. The problem setting of this paper is a mix of these two settings; the probability maximization in the case where the predictions are inaccurate, and the value maximization in the case where the predictions are accurate. This interpretation sounds more natural than the fairness notion at least to me.
- The authors claim that fairness is motivation for improving on the existing result. For the reason mentioned above, I do not think this problem setting is very natural.
- The constants in the guarantees are not optimized, probably for theoretical simplicity. Since there is no known lower bound, the existing papers on this topic (Antoniadis et al. and Fujii and Yoshida) focused on restoring or approaching the original bound $1/e$. In terms of that aspect, this paper's bound is not close to $1/e$ and difficult to highly evaluate.

Minor comments:
- The last line of page 2 contains wrong links to the reference (matroid secretary and knapsack secretary).
- To my knowledge, the first paper that derives a constant-factor competitive ratio is the knapsack secretary paper. I think it should be mentioned somewhere.
questions: questions: If I understand correctly, in the experimental result for the Almost-Constant instance, the proposed algorithm and Dynkin's algorithm can choose the best candidate whenever the best one arrives in the latter half (time $[1/2,1]$ for the proposed algorithm and $[1/e,1]$ for Dynkin's algorithm). However, the experimental result shows both algorithms achieve the success probability approximately 0.3 or 0.4. Could you tell me how these algorithms work in this instance?
limitations: limitations: The authors are sufficiently discussing limitations of the model and algorithm in the limitations section.
paper_summary: paper_summary: This work studies algorithms with untrusted predictions for secretary problems, considering fairness. In this paper, an algorithm is deemed fair if it can accept the best candidate with at least a constant probability. This fairness definition implies that a good candidate deserves a fair chance. The paper first demonstrates that the SOTA learning-augmented algorithm is unfair due to potentially biased predictions, meaning it may accept the best candidate with zero probability. Subsequently, the paper proposes a new algorithm that takes biased predictions as input but ensures both fairness and smoothness (which captures the algorithm's competitive performance). The design and analysis of the algorithm are based on an interesting pegging idea and can be extended to the k-secretary problem. Finally, extensive experiments are conducted to compare the proposed algorithm with SOTA algorithms, showcasing its advantages in both competitive ratios and fairness.
strength_weakness: strength_weakness: - Although the motivation for the fairness definition in the paper is understandable and appreciated, the definition itself remains somewhat vague. If I understand correctly, the current fairness definition is more relevant when the best candidate is significantly better than the second-best candidate. In such cases, a fair algorithm should select the best candidate with a non-zero probability, implying that a good candidate should have a better chance of being chosen. However, when the values of the top two candidates are very close, it is unclear how the algorithm ensures fairness without providing guarantees for the second-best candidate. The paper would benefit from a more comprehensive discussion and validation of the fairness definition.
  


- It is quantitatively unclear what the price of enforcing fairness in algorithms with predictions is. The proposed algorithm guarantees both smoothness C (that indicates the effectiveness of using the predictions) and fairness F. There should inherently be a trade-off between C and F, which is not discussed in the paper. And one natural question is whether the current algorithm is flexible and can be tuned to adjust the trade-off.
questions: questions: - Can you provide formal comments on the definition of fairness? Is the current algorithm fair for the second-best candidate, especially when the value of the second-best candidate is very close to that of the best candidate?

- All proposed algorithms in the main paper provide a smoothness guarantee of C = 4. Is this by design or coincidence? If it is by design, why was C = 4 chosen, and is it possible to adjust the parameters in the algorithm to attain other trade-offs between consistency and robustness?
limitations: limitations: Yes

Comments: title: response to rebuttal
comment: Thanks for the clarifications! I will continue to recommend acceptance!
Thank you for the clarifications and additional discussions on the multi-way trade-offs in the design. My overall rating of the paper remains the same.
Thank you for the feedback. The authors appropriately answered my questions. Since the lower bound $0.074$ is still far from the upper bound $0.215$ and the standard $1/e$, it is difficult for me to strongly support the acceptance of this paper, but I believe the quality of this paper is very high and above the borderline of NeurIPS.

> In the following we remind that to break ties randomly but consistently we add to all predicted and true values a random noise which we make arbitrarily small so as to not interfere with the performance calculation.

This resolves my concern for the experimental results. I could not find any description about adding random noise in the dataset description. If there is space to write this information, I recommend adding this.
Thank you for your response and answering my question about trade-offs between smoothness and fairness.  My overall evaluation remains the same.