Fair Secretaries with Unfair Predictions
Authors: Eric Balkanski
Will Ma
Andreas Maggiori
Venue: NeurIPS 2024 poster (2024)
Keywords: Secretary problem
fairness
algorithms with predictions
online algorithms
Primary area: optimization
TL;DR: We study fairness in the context of the secretary problem with predictions.

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.

Fair Secretaries with Unfair Predictions
Eric Balkanski Columbia University eb32248columbia edu
Will Ma
Columbia University
wm24280gsb. col wwllumbia..... edu
Andreas Maggiori Columbia University
am62928columbia.c edu
Abstract
Algorithms with predictions is a recent framework for decision-makinn under un- certainty that leverages the power of machine-learne 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 maintain- ing acceptable guarantees when the predictions are erroneous. A serious concern with algorithms that use predictions that these predictions can be biased and, result, cause the algorithm to make decisions that are deemed unfair. We show that this concern manifests itself in the classical secretary problem the learning- learning-augmentt augmented setting the state-of-the-art algorithm can have zero probabil- ity of accepting the best candidate, which we deem unfair, despite promising to accept candidate whose expected value is at least max(1 1 O(e)) times the optimal value, where E the prediction error. We show how to preserve this promise while also guaranteeing to accept the best candidate with probability (((1). Our algorithm and analysis are based on new "pegging" idea that diverges from existing works and simplifies/uniiis some of their results. Finally, we extend to the k-secretary problem and complement our theoretical analysis with experiments.
Introduction
As machine learning algorithms are increasingly used in socially impactful mitisionnmaking applica- tions, 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 of central importance include loan/credit-rist evaluation (52
40
50], hiring [11 17 recidivism evaluation
53
15 19
childhood welfare systems [66] job recommendations
44 price discrimination
18
resource allocation [51], and others 34 33
35
49
A lot of work in recent years has been
devoted to formally defining different notions of fairness algorithms that satisfy these different definitions
47
38
26 20 42 41), designing
37
36
12
13
55 and investigating trade-offs
between fairness and other optimization objectives 9
10
While most faimess work concentrates classification problems where the instance is known offline, we explore the problem of making fair decisions when the input revealed in an online manner. Although fairness in online algorithms is an interesting line of research per se, faireess considerations have become increasingly important due to the recent interest incorporating (possibly biased) machine learning predictions into the design of classical online algorithms. This framework, usually referred to as porninng-augmented algorithms or algorithms with predictions, was first formalized in [48). In contrast to classical online algorithms problems where it is assumed that no information is known about the future, Barning--augmette online algorithms are given as input,
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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 [45] 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 learning- augmented 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 parsimonious formulation of the secretary problem with predictions, motivated by fairness in hiring candidates.
The problem. In the classical secretary problem, there are candidates who each have 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 [27] accepts the best candidate with a constant probability, that equals the best-possible 1/e.
In the Barning-augmente formulation of the problem proposed by Fujii and Yoshida (30, the algorithm 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(5 - [e)}} times the maximum value, where ε 2 0 is the prediction error. The strength of this guarantee is that it approaches 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 I.T). Of course, 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 (30) that approaches when the prediction error is low.
Outline of results. We first formally show that the algorithm of (30) may in fact accept the best candidate with 0 probability. Our main result is then new algorithm for secretary with predictions that: obtains expected value at least max (1x))
O(s)} times the maximum value, like [30]; and ensures that, under any predictions, the best candidate is hired with 22(1) probability. This result takes advantage of potentially biased predictions to achieve a guarantee on expected value that approaches when the prediction error is small, while also providing 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 (a less informative form of prediction). This algorithm accepts the best candidate with constant probability but it does not provide guarantee on the expected value accepted that approaches 1 as the prediction error approaches O. Similarly, Dynkin's 's algorithm for the classical secretary problem accepts the best candidate with constant probability but does not make use of predictions at all.
Our algorithm is fundamentally different from existing algorithms for secretary with predictions, as our "pegging" idea, i.e., the idea not to accept possibly suboptimal candidate if there is a future candidate with high enough predicted value, is important to achieve our fairness desideratum. We also note that the definitions of the prediction error e differ in 30 and [ the former error definition uses the maximum ratio over all candidates between their predicted and true value while the latter uses the absolute difference. Our techniques present arguably simpler analysis and extend to general family of prediction error measures that includes both of these error definitions.
We then extend our approach to the multiple choice or le k-secretary problem where the goal is to accept at most & candidates and maximize the total of their values, which the most technical part of the paper. We design an algorithm that obtains expected total value at least max (11)), 1 O times the optimum (which is the sum of the k highest values), while simultaneously guaranteeing the highest- candidates a constant probability of being accepted. We also have a refined guarantee that provides a higher acceptance probability for the (1 - 8)k highest-values candidates, for any 5 e (0, 1).

---

Finally, we simulate our algorithms in the exact experimental setup of Fujii and Yoshida [30] We find that they perform well both in terms of expected value accepted and fairness, whereas benchmark algorithms compromise on one of these desiderata.
1.1
Related work
The secretary problem. After Gardner 31 introduced the secretary problem, Dynkin 277 developed simple and optimal stopping rule algorithm that, with probability at least 1/ee, accepts the candidate with maximum value. Due to its general and simple formulation, the problem has received a lot of and references therein) and it was later extended to more general versions matrooi--secretryy
attention (see, c.g.. 46 32]
such as k-secretary
77] 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 [30]. Both works design algorithms that use predictions regarding the values of the candidates to improve the performance guarantee of Dynkin's 's algorithm when the predictions are accurate while also maintaining robustness guarantees when the predictions are arbitrarily wrong. Antoniadis et al. K 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 [30] receives prediction for each candidate and defines the error the maximum multiplicative difference between true and predicted value among all candidates. Very recently, Choo and Ling [14] showed that any secretary algorithm that is 1-consistent cannot achieve robustness better than 1/3 + o(1), even with predictions for each candidate. This result implies that, if we wish to maintain the 1 - (E)) competitive ratio guarantee from 30 then the probability of accepting the best candidate cannot be better than 1 1/3 + (1).
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 this line of work include the prophet secretury problems where each candidate draws its valuation from a known distribution [28 22 23 5 and the sample secretary problem where the algorithm designer has only sample access to this distribution [39 21). 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 incorrect. Dütting et al. (25 investigate a general model for advice where both values and advice 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 assumees that the error probability of the binary advice is known.
setting, we receive point predictions that could be completely
Fairness in stopping algorithms. We say that 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 challenging one. That notion can be characterized as an individual fairness notion similar to the ademtity-independerd fairrdess 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 '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 bound by the performance of the best algorithm in the classical worst-case analysis setting. is also interesting to note the similarities with the poset secretary problem in [54]. 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 (54 no information about the values of future candidates available and the performance of their algorithms upper bounded by the best possible performance in the worst-case analysis setting.
learning-augmented
3

---

2 Preliminaries
Secretary problem with predictions. Candidates i = ,,...,, n have true values u, and predicted values ūg The number of candidates n and their predicted values are known in advance. The candidates arrive 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 denote the indices of the candidates with the maximum true and predicted value respectively. An instance I consists of the 2n values ui,,.. Un, . ün which, for convenience, are assumed to be positive and mutually distinct We let (Z) denote its prediction error. For simplicity, we focus on the additive prediction error ET) = max, (i; - uzl. but we consider an abstract generalization that includes the multiplicative prediction enror of [30] in Appendix A.2
argmax, U, and argmax, ü;
Objectives. We let A be a random variable denoting the candidate accepted by a given algorithm on 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:
E[uA] 2 - C. CC), VZ
(smoothness)
PIA 1") F, VZ.
(fairness)
Since the prediction error e is an additive prediction error, we define smoothness to provide an additive approximation guarantee that depends e (Z). When considering the multiplicative predic- tion error of 300, smoothness is defined to provide an approximation guarantee that is multiplicative instead of additive (see Theorem
We aim 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 Existing algorithms for secretary with predictions do not simultaneously satisfy these desiderata, as shown by our examples in Appendix I I
Comparison to other objectives. Existing algorithms for secretary with predictions do satisfy weaker notion called R-robustness, where E[ua] 2 R ut- for some constant R > 0. Our desideratum of fairness implies F-robustness and aligns with the classical secretary formulation where one only rewarded for accepting the best candidate. Another notion of interest in existing literature is consistency, which is how E[uA] compares to uhe- when s(Z) 0. Our smoothness desideratum implics I-consistency, the best possible consistency result, and guarantees a smooth degradation e e() increases beyond O.
3 Algorithm and Analysis
We first present and analyze ADDITIVE- PEEGIING in Algorithm [ which achieves the desiderata from Section 2 Then, we mention how using more abstract prediction error and an almost identical analysis, permits us to generalize ADDITIVE- PEGGING to PEGGING which achieves comparable guarantees for more general class of error functions that includes the multiplicative error.
Our algorithms assume that each candidate i arrives an independently random arrival time t, drawn uniformly from [0, 1]. The latter continuous-time arrival model is equivalent to candidates arriving in a uniformly random order and simplifies the algorithm description and analysis. We also write e, as shorthand for Iu: us|. as shorthand for e(T) (so that max; 6;) and < j if I < <lj.
Description of ADDITIVE-PEGGIN ing a candidate whose value is close to which, as we argue, is at least uş- - 2 E. To see this, note that u; 2 - E; 2 0,. 6; 2 6,. - u.- -2, where we used that ú; 2 û.- (by definition of i) and E 2 max G (by definition of e). Consequently, for smoothness, our algorithm defines the literal C = (i = i) at each new arrival, which is true and only if i has the highest predicted value. Accepting while C holds would maintain smoothness.
SADITIVE-PEGGINE ensures smoothness by always accept-
For the faimeess desideratum, we note that Dynkin's algorithm (27 for the classical secretary problem relies on the observation that if a constant fraction of the candidates have arrived and the candidate
'Our results for additive error allow negative values, but extension multiplicative emror in Appendix A.2 requires positive values.
"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 allows for unique argmax in the definitions of E" and i.

---

who just arrived has the maximum true value so far, then this candidate has a constant probability of being the best overall. The same high-level intuition is used in our algorithm. Every time new candidate arrives, we check if i is the maximum so far and if 4 1/2; namely, we compute the literal F. Accepting when
true, which is what Dynkin's algorithm does, would ensure fairness.
However, there are two crucial situations where ADDITIVE-PEGGINE differs from Dynkin's algorithm. The first such situation is when the candidate with maximum predicted value arrives and have that is not the maximum far or 1/2, i.e., C. A F is true. In this case, we cannot always reject 2. as Dynkin's ss algorithm would, because that would not guarantee smoothness. Instead, we reject future candidate whose prediction is sufficiently high compared u4- We call
i only if there Jpegged the set of those candidates. The main idea behind the pegged set /Pegged is that it contains the last candidate to arrive who can guarantee the smoothness property, which is why we accept that candidate when they arrive. The second situation where our algorithm departs from Dynkin's ' algorithm is when candidate arrives with * i + iPagged and we have that J is true, in which case Algorithm executes the if statement under the case Č A F. In this situation, cannot always accept as Dynkin's 's algorithm would, because that would again violate smoothness. Instead, we accept only if u, be lower bounded by Et, noting that if conversely u, + ét, is smaller than ús, then accepting might be detrimental to our quest of ensuring smoothness.
Algorithm I ADDITIVE-PEGGING
I/ The algorithm stops when it accepts a candidate by executing A <- i. 8// Initialization: /Peaged +- ()
while agent i arrives at time 4 do if i /pegged then
if / = then
A
else
/Pegged
peggged {i}
F+ (u; > max, uz) (t, > 1/2), C (i==)), + maxja, - unl
if C A F then
A +
else if C A then
pegged
+ [j ij i <ū + tr, (note that = i)
if /pegged = 0 then
A 4-
else if C F then
if 14 > in Et. then
Ati
Analysis of the ADDITIVE-PEGGIO algorithm.
Lemma 1. ADDITIVE-PEGGINS satisfies u.A u.- 4e(Z), VI with probability 1.
Proof. Let pegged denote the last arriving candidate in /pegged
We first argue that PEGGING always accepts a candidate irrespective of the random arrival times of the candidates. We focus any instance where ADDITIVE-PEGGING does not accept candidate until time f;- At time fę either C A F or C A F are true. Since in the former case candidate i is accepted, focus on the latter case and in particular whenever the [Peaged which computed is non-empty (otherwise, candidate i is accepted). In that case, it is guaranteed that by time tyoeedd AdDITIVE- PEGGING will accept a candidate.
We now argue that all cases ADDITIVE-PEGGINE maintains smoothness. Using 6, e definitions and the fact that is the candidate with the maximum predicted value we have:
> û;- u.- - 6,- 2 u4- E. If candidate is accepted then using the latter lower bound we get us > 0; 6 2 u³- - - 6; 2 u4- 2 s. If we accept A and the statement of Č ^ is executed at time t; then have u;
Et, U, E-E,, u.+ 2c. Finally, need to lower bound the value Ugaaasdd in case algorithm terminates accepting iPegged Note that from the way
5

---

the pegged set ] is updated when CA F is true we always have di < &igaaand + Ets- Since
Uigerons 2 Ulpmoon Eypegget we can conclude that Uigreo Ut Ess Espegrd 2 U4- 4E.
Lemma 2. ADDITIVE-PEGGINS satisfies PIA- 14] 2 1/ 16, VI.
Proof. In the following, we assume that the number of candidates larger or equal The proof for the case where n = 2 is almost identical while the faimess guarantee in that case is 1/4. We denote by i the index of the candidate with the highest true value except i* and i.e., = argmax ; Ui- Note that depending on the value of uz. 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 i' or i + i". For each of those cases, we define an event and argue that: (I) the event happens with constant probability, and (2) if that event happens then ADDITIVE- PEGGIING accepts i"
i = i we define event E = (42 < 1/2 < 4--) for which P F]] = 1/4. E implies that our algorithm does not accept any candidate until time ti- Indeed, note that at any point in time before fy-, both literals F and C are simultaneously false. On the contrary, at time fy-, both C and F are true and our algorithm accepts i".
On the other hand, if i" * i we distinguish between two sub-cases. First, we show that either Ug i4- + G Us- > Ci- is true. By contradiction, assume that both inequalities do not hold, then
Ui 2 ú.. + Ei
U.- 2us
Ui Ui- + Ei 7 Ug- ú.- E:
241
6,-
Ei
Uy S ûg- - Ei- "o Ui < ûs - E.- = E.. úz Ui
G2
Ri
Es-
< Ei
which is a contradiction. We now define two events Ei and Ei₂ which imply that i is always accepted whenever {ux- < û. + e and {u.- ú; - } are true respectively.
If uz < ug- + c, then we define event E1 = (t+ < 1/2} A ft, < 1/2} A (1/2 < t which is composed by 3 independent events and it happens with probability P[E.] = 1/2 1 = E1 implies that t5- < t.- = Et.- 2 e,, thus we can deduce that uq- > u; 2 ú; - 4 û, - Et... Consequently. if until time fü- all candidates are rejected, E implies that C A AF A (u,- > ûq- - -G-} is true at time 44- and candidate i" is hired. To argue that no candidate accepted before time 44-, note that F false at all times before 4. and at time & (when literal C is true) the set {j > i: us < új + St, } 2 { > i un < ú, } contains i*
If uh- > 0z Cs,, then we define Eg = {t; < 1/2 < tt- < tt} which happens with probability
P[Ez] P(t, < 1/2] PI1/2 <4 <}}
P[4 < 1/2) P[1/2< min(1=,,44 44 A min(4i-,44 (2) = -4-1 P[4 < 1 PI1/2 < min(4=, [3]] Plmin(Le 43 = 4--1
(1/2) (1/4) (1/2)
Note that until time f.- no candidate is accepted since C and F are both false at all times. Indeed, between times 0 and 1/2 only i could have been accepted but its arrival time is after ti-, and between times 1/2 and fy- no candidate has a true value larger than uy. Finally, note that at time ty. we have εt.. 2 Eç- and consequently Č A F A {u., > ûn &t.- J is true and i* gets accepted.
Theorem 3. ADDITIVE-PEGGINE satisfies smoothness and fairness with C = 4 and F = 11-1116 1/16.
Theorem 3 follows directly from Lemmas I and 2 We note that Lemma actually implics a stronger notion of smoothness that holds with probability 1.
The general PEGGING algorithm. In Appendix A.2 we generalize the ADDITIVE- PPEGGING algorithm to the PEGGING algorithm to provide fair and smooth algorithms for different prediction error definitions. defined as the maximum absolute difference between true and predicted values among candidates. To further demonstrate the generality of PEGGING, we also instantiate over the same prediction error definition eZZ max; 1 úu:/ uu//us as in 30 and recover similar smoothness bounds while also ensuring fairness. We name the latter instantiation MULTIPLICATIVE. PEGGIIG and present its guarantees in Theorem
SEDITIVE-PEGGINE is an instantiation of PEGGING when the prediction error is

---

Theorem 4. Let= max; |1 0z/ uu/ and assume u4 û, > O'v E [n]. Then MULTIPLICATIVE PEGGING satisfies fairness with F 1/16 and selects a candidate A such that U, 2 Ue- - (1-4.s(T) with probability I.
Fujüi and Yoshida [30 define the prediction error as in Theorem and design an algorithm that accepts
candidate with expected value at least u4-- max {(1 =) e), 0.215). Since (1 -=)/(11+ (1++) 2
1 1 2 their algorithm satisfies a smoothness desideratum similar to the one in Theorem 4 but as we prove in Appendix A.1 it violates the faimess desideratum.
4 Extension: k-Secretary problem with predictions
We consider the generalization to the k-secretary problem, where k 2 1 candidates can be accepted. To simplify notation we label the candidates in decreasing order of predicted value, so that ú₁ > Un and denote Tτ to be the index of the candidate with the f' highest true value so that Mr, > Ur,, The prediction error is again defined as E(Z) == max; [M ú, and we let S denote the random set of candidates accepted by given algorithm a fixed instance. The extension of our two objectives to this setting is
E LiES
Ur, - C-E(I), AI
(smoothness for k-secretary)
[=1
P(re E S]
Z Ft, VV k, VI.
(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 the candidates ranked l = 1.....A k to be accepted with probability Fe. The k-secretary problem with predictions has been studied by Fujii and Yoshida [30], who derive an Ommxx, |1 - uu (ú//ua)) Σ Urz
algorithm satisfying E [Eies u.] 2 max [1 (log k/ k/vR), but without any fairness guarantees. We derive algorithm k- k-PEGGING that satisfies the following.
Theorem 5. k-PEGGING satisfies smoothness and fairness for k-secretary with C = 4k and F2 - max { (113))+3 1-(++33)/k for all 1=,,..,,
256
We note that the algorithm of Kleinberg (43 for k-Secretary (without predictions) obtains in expecta- tion at least
(1-5/)
5
ur 5Vk
Urz
Vk
which has better asymptotic dependence on than our smoothness constant C 4k the prediction error is relatively large, i.e., s(T) guarantee, if one only considers our fairness desideratum for k-secretary, then simple algorithm suffices achieve F/ 1/4 for all L 1.....K k. namely: reject all candidates with t, 1/2; accept any candidate i with 4; > 1/2 whose true value u; is among the & highest true values observed so far, space permitting. For any of the top & candidates, i.e., candidate re with & [k), their value Mr, is always greater than the threshold т, which our algorithm recomputes upon the arrival of each candidate. Consequently, candidate re is added to our solution if the following conditions are satisfied: (1) tr. 1/2: and (2) there is space available in the solution when T/ arrives. For condition (2) to hold, it suffices that at least of the 2h - 1 candidates with the highest values other than Te arrive before time 1/2. This ensures that at most k - I candidates other than can be accepted after time 1/2. The probability of both conditions (1) and (2) being satisfied is at least P(,,, > 1/2 Binom (2k- 1, }]] = P(rr, > 1/2] P [2inom(22 1, 1) 2 ke] establishing that F₃ = 1 for all & k.
maxx; ui/ uz/Vk). On the other hand, regarding our fairness
Assuming k is constant, C' and Fi...., F3 in Theorem 5 are constants that do not depend on n or the instance Z. For large values of the first term in Fr is exponentially decaying, but the second term still guarantees candidate (E++ 13)/k: bounded away from More precisely, for k 2 52 and I S k/22 we have that candidate Te is accepted with probability at least 1024 i.c., every candidate among the top k k/2 is accepted
probability of acceptance that is independent of k as long as
7

---

with probability at least 1024 thus E (iss"" u.! multiplicative guarantee on total value that does not depend on à when it is large.
E
1024 2==1
thy 2
2046 L(=1 Mr. This implies
Σ
The algorithm. While we defer the proof of Theorem S Appendix B we present the intuition and the main technical difficulties the design of k- k-PEGGING. The algorithm maintains in an online manner the following sets: (1) the solution set 5 which contains all the candidates that have already been accepted; (2) a set H that we call the "Hopefuls" and contains the k - |S] future candidates with highest predicted values; (3) a set B that we call the blaming set, which 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 candidate in B. In addition, we use function peg to store the "pegging responsibility", i.e., if peg (i) = j. for some candidates i. where had one of the k highest predicted values, then not accepted the time of its arrival and pegged j. We use
peg (j) = to denote that j was pegged by i.
Algorithm 2 k 4--PEGGING
//* The algorithm stops when it accepts i candidates, i.e., when |S] k. *//
Initialization: H + [k], S <- 0, P + 0, B <
while agent arrives at time 1 do if' i E P then
D Case 1
Add to S, remove from P. and remove peg 1 (i) from
T f 4 highest true value strictly before t
F + (u4 r) A (t, 1/2) (i H), Et, + maxza,gulū Uz]
if A then
D Case
Add to S and remove from H
else if C A AF then
D Case subcase
if [j > i: u, û, + + (PU [k]) 0 then
Add i to S and remove i from H
else
subcase b
j' + An arbitrary candidate from {j > i: uy < ûj + + (PU Add j' to P. add to B, remove i from H, and set peg (i) = j'
else è A AF then
b Case
if [j E B: uz {z} + then
subcase
j' + An arbitrary candidate from (j E B: u; >> =zz} Add
S. remove j' from B, and remove peg (j') from P
else if (j E H u, > új -,,}
} + 0 then
b subcase b
j' f An arbitrary candidate from (j H u, > ûj - Et,}
Add i to S and remove j' from H
To satisfy the fairness property, we check if the current candidate has arrived at time 1, > 1/2 and u; is larger than the 4th highest value seen so far. We refer to these two conditions as the faireess conditions. If P (case 1) or i H and the fairness conditions hold (case 2), then we accept i. If the fairness conditions hold but & H then we accept if there is a past candidate in B with lower true value than u, (subcase 4u), or a future candidate H with low predicted value compared u; (subcase 4b). The main technical challenge in generalizing the pegging idea to k > arises when candidate i H arrives, but the fairness conditions do not hold (case 3). In this situation, it is unclear whether to reject i and peg a future candidate, or accept i. For instance, consider a scenario where the prediction error is consistently large (i.c., Et, is always large), such that when i arrives, the set {j > i: u, < ú + s, (P U [K]) is always non-empty. If f. < 1/2 and we accept i, we risk depleting our budget too quickly before time 1/2, leaving insufficient capacity accept candidates not in [k] who arrive later. Conversely, if we reject we deny it the possibility of acceptance in the overall acceptance probability. k-PEGGING
first half of the time horizon, potentially reducing balances this tradeoff while achieving smoothness. To establish smoothness, we demonstrate that the candidates with the highest predicted values can be mapped to the solution set S, ensuring that the true values within our solution set are pairwise "close" to the values of candidates in
..2....... (1,2....,k] This is proven Lemma g by constructing an injective function m(-) from set S to [1, (1,2....,k) such that for each j S, U, Um(s))
8

---

5 Experiments
We simulate our ADDITIVE E-EHIIIG and MULTIPLICATIVE- PEGGIIG algorithms in the exact experimental setup of Fujii and Yoshida 30
to test its average-case performance.
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 scalar e E [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- -E) and the rest of the candidates have a value of 1. All predictions are set to 1. In Uniform, the exponential distribution with parameter 1. The exponential distribution generates a large value with small probability and consequently models 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., ú, 6,- Ug where 5, is sampled uniformly and independently from [1 E, 1 + e]. 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 e in the following manner: if i belongs to the top half of candidates in terms of true value, then á; = (1 - =)- uy; if i belongs the bottom half, then û, = (1 + E) u4 Finally, in Unfair all candidates have values that are at most a (1++) multiplicative factor apart. Formally, u, is uniform value in [1 4/4, + s/4), and since (1 + e/4)/(1 e/4) S (1 + =) we have that the smallest and largest value are indeed very close. We set 0z = Un-r(()+1 where r(i) is the rank of us, i.e., predictions create a completely inverted order.
Experimental Setup. Fujii and Yoshida 30
sample each u, independently from
We compare ADDITIVE-PEGGING and MULTIPLICATIVE PEGGING against LEARNED- -YNNINN 30), HIGHEST-PREDICTIN classical DYNKIN algorithm which does not use the predictions. Following (30], we set the number of candidates 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 e, in Figure Our code is written in Python 3. 1.1. 1.5 and we conduct experiments on an M3 Pro CPU with 18 GB of RAM. The total runtime is less than 5 minutes.
which always accepts the candidate with the highest prediction, and the
The results are summarized in figure Since ADDITIVE-PEGGII PEGGING achieve almost the same competitive ratio and fairness for all instance types and values of E we only present ADDITIVE-PEGGINT in figure 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 e 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 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.
Results.
and MULTIPLICATIVE:
In terms of fairesss, predictions do not offer any information regarding the ordinal comparison between candidates' true values and this is why for small values of e the probability of HIGHEST- PREDICTION and LEARNED-DYNKIN of accepting the best candidate is close to 1/100 1/n, i..., 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 E the highest predicted candidate is the
9

---

ALMOST CONSTANT
UNIFORM
ADVERSARIAL
UNFAIR
ADDIIIV--PEGEING PEGGING
LEARNED- DYNKIN
Fairness
DVKKIN
0.66
HICHEST-PREEMCTIE
0.2
Competitive ratin
0.4
1
0.4
02
0.6
0.8
0.4
Figure 1: Competitive ratio and fairness of different algorithms, for each instance type and level of
true highest and ODDITIVE-PEGGING LEARNED-DYNKIN and HIGHEST-PREDICTE all accept that candidate having 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 competitive ratio for all values of e and achieve a close 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 west-performing and most robust. The HIGHEST-PREDICTE algorithm does perform slightly better on Uniform instances and Adversarial instances under most values of c, but performs consistently worse on Almost-constand and Unfair instances, especially in terms of fairness. Our algorithms perform better than LEARNED-DYNER in almost all situations.
Limitations and Future Work
We study notion of fairness that is tailored to the secretary problem with predictions and build algorithms based this notion. However, there alternative notions of fairness 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 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, 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 [ we use an individual fairness notion which does not model other natural desiderata like hiring from underprivileged populations 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 fair selection with predictions.
Regarding trade-off's our guarantees: for the single-secretary problem, we can improve the faimess guarantee from 1/16 to 0.074 by optimizing the constants in our algorithm. However, choose not to do so, as the performance increase is marginal, and we aim to keep the proof as simple as possible. Additionally, as we noted in Section I.] any constant C for smoothness implies an upper 1/3 o(1) for faimess. Finding the Pareto-opting optimal curve in terms of smoothness
bound of and fairness an interesting direction. 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
- Ce, which reaches ratio of when the predictions are exactly correct. Thus, regardless the smoothness guarantee, we must achieve competitive ratio of when predictions are fully accurate. This constraint makes it challenging to improve the fairness guarantee even at the cost of a less favorable smoothness constant C.
10

---

References
[1] Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias: There's software used across the country to predict future criminals. and it's biased against blacks. ProPublica, May 23 2016. URL https://www, propublica orgg/rtiiler..r...ooo.rr.o.m..ee
in- seriminal-Sentenne
[2] Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, and Bertrand Simon. On- line metric algorithms with untrusted predictions. In Proceedings of the 37th International Conference Machine Learning (ICML), pages 345-355, 2020.
[3] Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. Secretary and online matching problems with machine learned advice. Proceedings of the 33rd Annual Conference on Neural Information Processing Systems (NeurIPS), pages 7933-7944, 2020.
[4] Makis Arsenis and Robert Kleinberg. Individual faimess in prophet inequalities. In Proceedings of the 23rd ACM Conference on Economics and Computation (EC), page 245, 2022.
[5] Yossi Azar, Ashish Chiplunkar, and Haim Kaplan. Prophet secretary: Surpassing the 1/c barrier. In Proceedings of the 19th ACM Conference on Economics and Computation (EC), pages 303-318, 2018.
[6] Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. A knapsack secretary problem with upplications. In Proceedings of the 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 16-28, 2007.
[7] Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. Matroids, secretary problems, and online mechanisms. In Proceedings of the 18th Annual ACM-SIAN Symposium on Discrete Algorithms (SODA), page 434 443, 2007.
[8] Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. Regularized online allocation problems: Fairness and beyond. In Proceedings of the 38th International Conference on Machine Learning (ICML), pages 130-639,110 2021.
[9] Dimitris Bertsimas, Vivek F. Farias, and Nikolaos Trichakis. The price of fairness. Operations Research, 59(1): 2011.
[10] Dimitris Bertsimas, Vivek F. Farias, and Nikolaos Trichakis. On the efficiency-fairness trade-off. Management Science, 12:2234-2250, 2012.
[11] Miranda Bogen and Aaron Rieke. Help wanted: examination of hiring algorithms. Equity, and Bias, Uplurn (December 2018), 2018.
[12] L. Elisa Celis, Damian Straszak, and Nisheeth K. Vishnoi. Ranking with fairness constraints. In Proceedings of the 45th International Colloquiumm Automata, Languages and Programming (ICALP), 2018
[13] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvtiskii. Matroids, matchings, and fairness. In Proceedings of the 2nndInternationa Conference Artificial Intelligence and Statistics (AISTATS), pages 2212-2220, 2019.
[14] Davin Choo and Chun Kai Ling. A short note about the learning arXiv preprint arXiv:2410.0658.3 2024.
learning-augmentee augmented secretary problem.
[15] Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big Data, 5(2):153-163, June 2017.
[16] Alexandra Chouldechova, Diana Benavides- Praado, Oleksandr Fialko, and Rhema Vaithianathan. A case study of algorithm-assiss assiiseed decision making in child maltreatment hotline screening decisions. In Proceedings of the Ist Conference on Fairness, Accountability and Transparency (FAccT), pages 134-148, 2018.
[17] Lee Cohen, Zachary C. Lipton, and Yishay Mansour. Efficient candidate screening under multiple tests and implications for faimesss. In Proceedings of the 1st Symposium on the foundations of responsible computing (FORC), page 1-20, 2019.

---

[18] Maxime C. Cohen, Adam N. Elmachtoub, and Xiao Lei. Price discrimination with fairness constraints. Management Science, 68(12).8536 8552, 2022.
[19] COMPAS (software).
( (software)
[20] Sam Corbett-Davics Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq. Algorithmic decision making and the cost of faimess. In Proceedings the 23rd International Conference on Knowledge Discovery and Data Mining (KDD), page 797-806, 2017.
[21] José R. Correa, Andrés Cristi, Laurent Feuilloley, Tim Oosterwijk, and Alexandros Tsigonias- Dimitriadis. The secretary problem with independent sampling. In Proceedings of the 32nd Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pages 2047-2058, 2021.
[22] José R. Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vredeveld. Posted price mechanisms and optimal threshold strategies for random arrivals. Mathematics of Operations Research, 46(4): 2021.
[23] José R. Correa, Raimundo Saona, and Bruno Ziliotto. Prophet secretary through blind strategies. Mathematical Programming, 190())1483-52, 2021.
[24] Julia Dressel and Hany Farid. The accuracy, fairness, and limits of predicting recidivism. Science Advances, 4(1), 2018.
[25] Paul Dütting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii. Secretaries with advice. In Proceedings of the 22nd ACM Conference on Economics and Computation (EC), page 409-429, 2021.
[26] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (ITCS), page 214-22122020222 116,22,,222 2012.
[27] E. B. Dynkin. The optimum choice of the instant for stopping a markov process. Sovier Mathematics Doklady, 4:627-629, 1963.
[28] Hossein Esfandiari, MohammadTaghi Hajiaghayi, Vahid Liaghat, and Morteza Monemizadeh. Prophet secretary. SIAM Journal on Discrete Mathematics (SIDMA), 31(3):1685-1700 2017.
[29] Michael Feldman, Sorelle A. Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasub- ramanian. Certifying and removing disparate impact. In Proceedings of the 21th International Conference on Knowledge Discovery and Data Mining (KDD), page 259 259-268, 2015.
[30] Kaito Fujii and Yuichi Yoshida. The secretary problem with predictions. In Mathematics of Operations Research, 2023.
[31] Martin Gardner. Mathematical games. Scientific American, 202(3):172-186, 1960.
[32] John P. Gilbert and Frederick Mosteller. Recognizing the maximum of sequence. Journal of the American Statistical Association, 61:35-73, 73, 1966.
[33] Lev Grossman. Are face-detection cameras racist? Time, 2010.
[34] Alex Hern. Artificial intelligence beauty contest doesn't like black people. The Guardian, September 2016. URL artificial- htw.acaallinnlllgggeeoeeeeoooooo
doesnt -tw.ea/tteettoteeeeeeee-eeeaaaaa
[35] Howard and J Borenstein. The ugly truth about ourselves and our robot creations: The problem of bias and social inequity. Science and Engineering Ethics, 24(5):1521-15233 October 2018.
[36] Matthew Joseph, Michael Kearns, Jamie H Morgenstern, and Aaron Roth. Fairness in learning: Classic and contextual bandits. Proceedings of the 29th Annual Conference on Neural Information Processing Systems (NeurIPS), 2016.
12

---

[37] Toshihiro Kamishima, Shotaro Akaho, and Jun Sakuma. Fairesss- aware learning through regularization approach. In Proceedings of the I1thlnterattinall Conference on Data Mining Workshops (ICDMW), pages 643-656 2011.
[38] Toshihiro Kamishima, Shotaro Akaho, Hideki Asoh, and Jun Sakuma. Fairness- classifier with prejudice remover regularizer. In Peter A. Flach, Tijl De Bie, and Nello Cristianini, editors, Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Datahases (ECML-PKDD)), volume 7524, 2012.
[39] Haim Kaplan, David Naori, and Danny Raz. Competitive analysis with a sample and the secretary problem. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2082-2002 2095, 2020.
[40] Amir H. Khandani, Adlar J. Kim, and Andrew W. Lo. Consumer credit-risk models via machine-learning algorithms. Journal of Banking & Finance, 34(11)2777-2777, 2010. URL
[41] Jon Kleinberg and Manish Raghavan. Inherent trade-offs in the fair determination of risk scores. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (TTCS),
2017.
[42] Jon Kleinberg, Himabindu Lakkaraju, Jure Leskovec, Jens Ludwig, and Sendhil Mullainathan. Human Decisions and Machine Predictions. The Quarterly Journal of Economics, 133(1): 237-293, 2017.
[43] Robert D. Kleinberg. A multiple-choice secretary algorithm with applications to online auctions. In Proceedings of the 16th Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pages 630-631, 2005.
[44] Anja Lambrecht and Catherine Tucker. Algorithmic bias? an empirical study of apparent gender-based discrimination in the display of stem career ads. Management Science, 65(7): 2966-2981, 2019.
[45] Alexander Lindermayr and Nicole Megow. Algorithms with predictions. wwwhhhmwwwtt--eiihiiihcccee wtt.eddiiiiosss.ituuu....o
https://
[46] D. V. Lindley. Dynamic programming and decision theory. Journal of the Royal Statistical Society: Series C (Applied Statistics), 10(1):39-51, 1961.
[47] Binh Thanh Luong, Salvatore Ruggieri, and Franco Turini. k-nn as an implementation of situation testing for discrimination discovery and prevention. In Proceedings of the 17th International Conference on Knowledge Discovery and Data Mining (KDD), page 502-510, 2011.
[48] Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. In Proceedings of the 35th International Conference Machine Learning (ICML), pages 3302-3311, 2018
[49] Will Ma, Pan Xu, and Yifan Xu. Group-level fairesss maximization in online bipartite matching. In Proceedings of the s1 International Conference on Autonomous Agents and Multiagent Systems, page 1687-1689, 2022.
[50] Rashmi Malhotra and D. Malhotra. Evaluating consumer loans using neural networks. Omega, (1))83339 2003. URL wtt.tttps:/ htttps://Econaapertttt repec. org/RePEc:eess jomeaa jomega 27:1::::2003:1:::p:888----
[51] Vahideh Manshadi, Rad Niazadeh, and Scott Rodilitz. Fair dynamic rationing. Management Science, (9(11))6818--88 2023.
[52] Amitabha Mukerjee, Rita Biswas, Kalyanmoy Deb, and Amrit P. Mathur. Multi Multi-objective evolutionary algorithms for the risk-return trade-off in bank loan management. International Transactions in Operational Research, 955:5835597, 2002.
13

---

[53] David B. Mustard. Reexamining criminal behavior: The importance of omitted variable bias. The Review of Economics and Statistics, 85(1):205-211, 2003.
[54] Jad Salem and Swati Gupta. Secretary problems with biased evaluations using partial ordinal information. Management Science, 70(8):5337-5366, 2023.
[55] Ke Yang and Julia Stoyanovich. Measuring fairness in ranked outputs. In Proceedings of the 29th International Conference on Scientific and Statistical Database Management (SSDBM),
2017.
14

---

A Additional discussion and missing analysis for single secretary
A.1 Unfair outcomes in previous work
In this section we present the Garning-augmenteds algorithms of [2] and [30], and argue that they fail to satisfy simultancously the smoothness and faimesss desiderata described in section We follow the same notation as in the main paper where the 2", 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 that candidate, we use the symbol to denote such value.
Algorithm 3 LEARNED-DYNKIN [30]
0 < 0.646, t + 0.313, mode + Prediction
while agent i arrives at time i do
maxx+4 < Uj 1 0// / > 0 then
mode + Secretary.
mode Prediction and i then
A + i.
mode Secretary and t and u, > r then
A +- i.
Algorithm VALUE MAXIMIAMXIMIZAATION SECRETARY 2
Input: parameters c, À such that À 2 0 and c > 1. t" <- (-1((e((11((ee))
t" + exp ( (-1(cc(())c))
while agent/ arrives at time t do
T < " Ujj
if < t4 tx and u, max (T" }} then
A+i
T" maxjit, <r" Uj
if 4 h* and U, > 77" then
i+i
LEARNED-DYNKEN Fujii and Yoshida (30) receives a predicted valuation for all candidates and defines the prediction error of candidate i as [1 û//u:l If the prediction error of a candidate is higher than 0 then it switches to Secretary mode where it mimics the classical DYNKIN algorithm where all candidates the first candidate whose valuation is the maximum overall is hired. Note that if candidates have very low prediction error then LEARNED -ARNED-DYYNIN remains in the Prediction mode and the candidate with the higher prediction is hired. One instance where LEARNED- -YNNIIN never accepts candidate candidates with true valuations #1 1 8 8'/2, U2 and predicted valuations ú = 1 + 8/2, û2 = + I' where f' < = 0.646. The prediction error equal to o' < 0 = 0.646. Consequently BEARREDD-YNKII does not switch to Prediction mode, and it never accepts the candidate with true valuation + 8/2, violating the Fairness desideratum.
rejected for constant fraction of the stream and after that rejection phase
i" is the following: there
VALUE-MAXIMIZATION SECRETARY of 2 receives only one prediction regarding the max- imum value i' and the prediction error defined as E = |u.- a+1. The latter algorithm parametrized by X 2 0 and 2 1 which control the relationship between the robustness and smooth- ness bounds. VALUE- MALLUE-MXIMIZATIIO SECRETARY has three distinct phases defined by the time ranges [0, t*], (t", ("*) and [t**, respectively, where t", h are defined using the Lambert functions --land W The first phase is used as an "exploration" phase where all candidates are rejected and the end of the phase threshold 7* is computed. During the second phase the algorithm accepts candidate and only if the true value the candidate larger than max(r", (r, ú" A}. Finally, if at the end of the second phase candidate has been selected then the algorithm accepts candidate if their true value is the maximum so far (note that in the pseudocode this is done by computing the threshold ?**).
To demonstrate the failure of VALUF-MAXXMIZAATION SECRETARY let A be the random variable denoting the candidate it accepts. For any E (0, 1) we define instance with predicted maximum
15

---

value x" = and true values {ui, Ug..... Un where all numbers are distinct, u1 = 1 and Uy [0, Vi E n2.....n). The prediction error that instance Note that 1 1 arrives in SECRETARY can
the first phase then the maximum value of a candidate that VALUU--AXIIMIZATIOO accept in the second and third phases most &. Thus, we can upper bound the expected value of candidate A as follows: A[ & p( 2 (*] t4.- + P(,,- < (*] E (1 yu. + tt
We emphasize that in the learning-augmeetted setting, there no assumption regarding the quality of the prediction; thus, the parameters e and À cannot depend on the prediction error. For any parameter 2 (and any A), we have that > is constant that is bounded away from MAXIMIZATION SECRETARY satisfies the smoothness
Towards a contradiction, assume that desideratum described in section for some parameter C. Then, we have that E[ua] u,- C.
Consequently, (1 - 1*) )u, +1 ui C. -,-=1 (1-10 (1-1) + . which leads to contradiction when we let 0.
A.2 The PEGGING algorithm
In this subsection, we generalize the DODITIVE-PEGGIAN algorithm as to provide fair and smooth algorithms for different prediction error defiittoos. We use the direct sum symbol @ to denote the addition or multiplication operation, O for its inverse operation, i.e., subtraction or division, and for the identity element of @ i.e, either the number 0 if ( denotes the classical addition operation or 1 if + denotes the multiplication operation.
To model the "difference" between predictions and true values we use a function e: Ryo Rzo Ryo- We assume that receives input only tuples of strictly positive reals so that the multiplicative error definition of (30] is not ill-defined Furthermore, as noted in the main paper, we assume distinct true and predicted values. This is achieved by introducing arbitrarily small perturbations, simplification that does not affect our algorithm's 's performance and simplifies proof's by avoiding potentially cumbersome case distinctions arising from subtractions involving zero
Our techniques require the following inequality to be true:
Assumption 6. u + (0 e(u, ú)) 2 à 2 u + (0 - e(u, ū)), Vu, E R u +
Assumption 6 essentially demands that prediction á can be upper and lower bounded function of the true value u and the "distance" e(u, ú) between true and predicted value. While the notation is left abstract to highlight the generality of Theorem 7 we provide examples on how to instantiate the error function and operators for natural prediction errors such as the absolute difference that we used in ADDITIVE- PEGGING and multiplicative prediction error function that is used by Fujii and Yoshida [30 To be specific, it is easy to check that Assumption holds when:
is addition, 0, and e(u, û) j u| |u a|:
is multiplication, 0 = 1. and c(u, a) = -111-// -û/ul:
+ is multiplication, 0 1, and cuu, ù) = =1 max (u. út/ //mminfu, u, @) (this follows from above because |1 max u, / min u, aHl 2 a/ul).
It is worth noting that Assumption 6 does not hold when ① represents the scalar multiplication,
= 1, and e(u, ú) = 1al-u/a u/ul. However, this definition of e(u, û) arguably less conventional than (u, ú) = |1 ú/ ul] which is employed in (30].
Using the new abstract notation, we write e; e(u; ûg) and define the prediction error of our instance as & = max, eg. We can generalize ADDIIIVE-PEGGING to PEGGING by making the following modifications:
1. Update the condition u; > ús St, + uj + Ct; ûu to uy ④ (0 + E1,) > 0z.
2. Redefine the update rule of the "pegging" set from pregged + [j > i ú + teu to Ipegged
{j > i ① (0 E.,)) < }
We proceed stating and proving the main theorem of this subsection.
'While we could allow zero vero-valued inputs by extending the image set to Rxo U foo). we avoid this for simplicity.
16

---

Algorithm 5 PEGGING
1/ The algorithm stops when it accepts candidate by executing A <- i. *//
Initialization: /Peaged 6- 0
while agent i arrives at time do if E lpagged then
if | 1 then A -
else
Tpegged Toegged {i)
F (u:
max u2) A (4, 1/2), C (i= + max fj
if C A F then
A +-
else C AFF then
if + (0
+ s..)
0; then
A
else if CA CAFRA then
ppegged
(j > i: u @ (0 (0--E,) =x) < 0z}
/Pegged
0 then
Theorem 7. Suppose that @ represents either scalar addition or scalar multiplication, with O being inverse. Suppose that the error function c(.,-) satisfies Assumption 6 Then PEGGING accepts the maximum value candidate with probability at least 1 and its expected value is at least max @ (0 (
16
16 w:-}
Proof. The proof that PEGGING always accepts candidate is the same in Lemma I and therefore we omit it. To prove the smoothness bound we argue that the selected candidate has a true value that is close to the true value of i which is in turn close to the true value of 8"
To lower bound ùn we use the right-hand side of Assumption and the fact that is the candidate with the maximum predicted value, and get 0; 2 û;-
( [0 (+-
We also lower bound u4 follows: from the left-hand side of Assumption 6 we get that uy (0
e;) as u; 2 û; e (0 + ez). Combining the latter with the previously argued lower bound
i I
d + (0 ex-) we have:
U 04 (0 Es) u + - c e (0++)
The latter inequality lower bounds the value accrued by our algorithm whenever candidate î is selected, ie.. literal C true the time of the selection. candidate is accepted using the if it-ttnttment corresponding to literal C A F then have u, @ (0+ + sx.)) 2
in (0 + Ex,) and again
using the lower bound ûe get
u
Ui.
0 Eg. (0+
Note that up until this moment we considered but one case where our algorithm may accept candidate and terminate. Indeed, we still need to lower bound the value of the last candidate in the pegging set since it may be the one accepted by our algorithm. the index of that candidate be peggedd
17

---

Note that for all E 1 / it holds that u4 ① (0 - Et,) < dg. Thus for grogged
using the left hand
side of Assumption 6
have:
U. Uppaaed
(0 + Eppcesed)
ppeaaed
El posseed
Uipaagedd
Uippaased
O (0 Cypaxred)
Ut Uppoaged
2
Ut
+ (0 Et,) @ (0 + Eppoxeed)
lower bound of
U.paagedd
2
Ui
(0 C3- @ (0 + c2)
+ (0 Et. a (0 + Epperge))
Hipaaged
2 Uy
@ (0 E) @ 00 2)
E)
Combining all the lower bounds on the value of the accepted candidate we deduce the first part of the lower bound.
We proceed proving fairness and, consequently robustness. The proof of the latter follows the same line of thinking as the proof of Lemma 2 We repeat it here to conform with the abstract notation and also assume (as Lemma 2 that the number of candidates is at least (if there are two candidates, then the proof remains essentially the same and the fairness bound improves to 1 1/4). Let 7 be the index of the candidate with the highest true value except i and i.e., argmax 14..
if
define event E' {4 < 1/2 < 6--) for which P 1/4. E implies that our algorithm does not accept any candidate until time li=. Indeed, note that at any point in time before 4+-, both literals F and C simultaneously false. On the contrary, time 4--, both C and F are and our algorithm accepts i"
On the other hand, if * 2 we distinguish between two sub-cases, namely when (u ú and {u. + (0+ > ū.). We continue arguing that (u, @ (0 (4- < V 2 20+cc) > i,)
is always true. Indeed if (u; (0
6x- 2 (g.-) have that:
right hand side of Assumption
U/ + (0
Es) -ي
① (0
6s) IV M
cx-
left hand side Assumption
+ 0 e3- 2 Us 1 (0 + cs)
Mg + 0 cr- 2 ús
where for (+) we need to prove that
Wq 5 u4- @ (0 <x-) uy- ① (0+ 2 me (0 + 6z)
If denotes the addition operation then we have that:
Us + (0- E) 2 Ui + (0 E1-) +
ue >us
6,- - E 2 Ui Us
E/ > Eg
U3 + + + cx.) > us + (0++)
Likewise if @ denotes the multiplication operation then:
Ws (1 <s) Z Ui- 6x-) 4>
Mr Sag
Ug UgC 2 U4- Ui
By- Bn-
Up Eg > U:E
E4- + up > Usc Ui +
Ug (1+ > u; (1 + ei)
We now define two events Fr and Eg which imply that i* is always accepted whenever (u:0(0-<5) < â--) and {u,- + (0 + Ex-) ) are true respectively.
18

---

< < If {uz + (0 1000-h <x) < ú;- }. then we define event E = ft= < A <
< t.- which
composed by 3 independent events and it happens with probability P[Ei] = 1/28 1/8. Ei implies that 1a < 4;- 7 Et. 2 62. thus we can deduce that:
us 2u 2cc
left hand side of Assumption
ue + (0 + st,-)
2
+ (0 + ei)
2
Consequently, if until time &.- all candidates {u- @ (0 + st,-) 2 ûn} is true at time ti- and candidate i is hired. To argue that no candidate is accepted before time tu. note that F is false at all times before tie and at time t; (when literal C. is true) the set {j > i: u; + (0 Et,) < رz} 2 {j > 8: un @ (0 - E3) < úz} contains i*.
rejected, E₁ implies that A F A
If {u-- @ (0 4-) > ús}, then we define E2 ft= < 1/2 < t.- < t&} which happens with probability
P[Ez] P[t: < 1/2] P11/2 4. < 4s]
= P(t; < 1/2] PI1/2 < min(4 44 A min 12) = 4--] P[4 < 1 P[1/2 min((e, 4+]) Plmin(li,,1 (4] 4-1]
= -(1/2) (1/2)-(1/4)- (1/4)- 1/16
Note that until time 4.- no candidate is accepted since C and F are both false at all times. Indeed, between times 0 and 1/2 only i could have been accepted but its arrival time is after 4ir, and between times 1/2 and f.- no candidate has a true value larger than ug. Finally, note that at time t.. we have Et,- 2 Ez- and consequently A F A {(0 + Et.- t us- ús} } is true and i* gets accepted.
Note that by instantiating @ e to the usual scalar addition and subtraction and defining e(u, ú)) |u - û| we get that, E = max; |4:- - ü.s and Theorem 7 recovers Theorem 3
We further demonstrate the generality of PEGGING by instantiating @b, e. and recovering similar smoothness and robustness bounds as [30] while also ensuring fairness. Fujii and Yoshida [30] define the prediction eтrоr as E = max; |1 ú./u/ /u, and design an algorithm which accepts a candidate i whose expected value at least u4- max {(1 (11=)/(1 e) + e). 0.215]. Since (1-+)/(1++) 2 1-2 the latter algorithm satisfies the Smoothness desideratum of Section but, as we prove in Appendix A. it violates the Fairness desideratum.
To that end, let SAADIIPLICAATVE-PEGGIIN be the instantiation of PEGGING when @ e denote the classical multiplication and division operations, and e(u, û) recover Theorem 4 which is restated below for convenience.
ú/ul.. We now use Theorem to
Theorem 4. Let e(I) max, |1 â./u:l and assume uy û, 0 Vi E [m]. Then MULTIPLICATIVE. PEGGING satisfies fairness with F = 1/16 and selects a candidate A such that UA 2 ut- (1-4.e(I)) with probability 1.
Proof. Function <(u, ú) = 11 â/ul satisfies the properties of Assumption 6 Consequently, us- accepts candidate whose expected value is least 2 u. max {1 4e, 1/16), where we used the inequalities
ing Theorem 7
max - ()), 1/(1+e) 2 (1 =)) and (1 - =)* 2 4-
B Missing analysis for the k-secretary pegging algorithm
In Lemma 8 we prove that k-PEGGING satisfies the smoothness desideratum. Lemma 8. Ejes 2 ΣL ur 4k eZ), VI with probability 1.
Proof. Similarly to the single choice secretary problem proceed in two steps, first prove that
Ur:
< 2k e
and then we prove that
Σ
U4 Σ
2
xE(K]
JES
19

---

Note that combining those two inequalities is enough to prove the current lemma.
The first inequality is proven follows:
Σ Ur S()) E(n S(2) ket Σ ûi S(a) ket Σ us + 24 +
Σ u4
where (1) and (3) are by definition of E and (2) since û, is tth largest predicted value. We proceed to argue that:
Σ
S
2k
<E[R]
JES
We now define an injective function m [k] + for which we have:
d; mm) S 2e, Vi E [k]
Note that the existence of such a function implies the desired Σie(s] U, 4 Ejen Uj 2 inequality.
Note that each candidate j' E [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.
The first where j' is deleted from H without being added B, occurs either in case 2, 3a, 4b of the algorithm. Let be the current candidate at the time t; when the latter happens. If case 2 or 3a happens then j' i, define m(j') j' and uy Um(j') = 0 < 2c. If case 4h happens then have that at that time t, j' {j H conclude that u, (i) u, uy S u 4y + Et, I c + E,, 2E.
0 =t,} and we define m(i) j'. Consequently,
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 ty via case 3b. In that case, candidate peg (j") either remains in P until time 'peg("") and
added to S at that time or earlier. In both cases, j' is removed from B at the respective time. Thus, we conclude that j' gets deleted from B at time ppeg("") or before. If the deletion happens at time ppe((i) then it must happen through case 1, we define m(j') = pog (j') and we have that Uj Um((i)) Uyy Mpee(r") S Opeg((") + St,, - "ppe(j") = (ppgg()") Upeg()")) + Et,, S. Epeg(") + Etg S 2s, where in the first inequality we used that Upeg()") > Uy - Etg. since peg (j') was pegged by j' at time ty. If j' is deleted from B before time (peg(?) it must happen via subcase 4a due to the arrival of a candidate I that is added to S. In that case we define m(j') = and from the condition of subcase 4a we have that j E at time by' have that uy "m((') ug u4 0 26.
deleted from P
We now move on to prove the fairness desideratum. Lemma 9, For all i E [k]: P(r; E S] 2 (1/3)*+5
Proof. We start arguing that if r4 E [k]. i.c., if candidate r, is among the k-highest prediction candidates, then P(r, E S) 2 (1/2)*+1, We define event E, which happens with probability (1 (1/2)*+1 and implies that ry is added to the solution S. Let
= A 1E(K+1]M0
(nr < <1/2] (tr, 1/2]
During the interval [0, 1/2], only candidates in [k] may be added S. In addition, & implies that the threshold 7 is greater than Ure4a after time 1/2, and only candidate r, has a value exceeding t after that time. Thus, other than r; the only candidates that may be added to S during the interval [1/2, 1, are candidates pegged by a candidate j E [k.] In summary, & implies that S consists of candidates in [k] or candidates which were pegged by some candidate in E [K] which is not part of the solution set S. Thus, |S| < & before time ty., and at that time r; is added to S through case I.
In the rest of the proof, we focus on the case where r; & [k]. Note that since i [k] and E [k] then Rj E [k] such that uy 2 ur, > Ujs i.e., j has true value which is not among the k-highest true values. We now argue that {uj ār. + + } {ur, > a Ey: is always true. Similarly to the proof
20

---

of Lemma 2 assume towards contradiction that both inequalities can be inverted and hold at the same time, then we end up in contradiction as follows:
dry Suy Ur. Ur; EEj + ur -Ur, > Ej
en 2un, -uri
Uj 2 ür; + Ej
Er; 2Ej
"ysunig uj < úz - Er: = Er. < <ūg uu =2āر وسررو uy CrZ <
Ur S ūj - Er,
For each those cases, i.e., whether {u, < 0r; + + or {ur, > ūj cr,} } is true we define an event which implies that r; is added to the solution set S.
If (ur, > ū, Cr. J is true then we define the following event:
3 =
A
(4 < 1/2) A (1/2 tr < {1}}
Note that:
l|g] = P <n <()]-
II
Plan < 1//2
{ PeaM
minftr.. ty) ftr, <t,]l.
II
(1/2)
1/31 P(tre <ty]-
II (1/2)
P[1/2 < mminft.,, Pltr. <ty (1/2)
(1/4) (1/2) (1/2)**2
(1/2) k+5
We now argue that & implies that r; is added to S.
The first literal of & ensures that T 2 Ure+ after time 1/2 and, consequently, the only candidate with true value higher than the threshold conditions of case 4 are true only for ry. We now argue that: (1) before time fy, less than candidates added to S: and (2) the conditions of subcase 4b are true for r; at time lr.-
any time t [1/2, fr, is r, That observation implies that
For (1) first note that: (a) initially we have SS B maintains the invariant B E H 0, B H C [k): and (c) every time a candidate is added to the solution then a candidate is deleted from either B, as in case and subcase 4a, or H as in case 2, subcase3a, and subcase 4b. Thus, at all times B + H + |S] remains constant and since initially is equal to k we conclude that at all times |B] + H + |S| = k. In addition, a candidate not yet arrived may be removed from H only through subcase 4b. Since argued that conditions of case 4 are true only for ri, we have that right before r arrival j E H and [S] = k [B| [ < k - [ < k 1 < k. For (2), to argue that conditions of subcase 4b are met at time t is enough to prove that j E { : ur, > ûg Et., } (note that j E H and & implics that 1ú l.,). To see this, note that by the definition of st,, it holds that Et,, cr, and consequently,
| = k; (b) at all times our algorithm
(j' ur, új- Et,, } (j' uh, úz - -r, 9 j.
Before proceeding to the second case we introduce the following notation:
1f 1= peg (j)
(peg())
xo
otherwise
that is, if at time I, candidate I is added to the pegging set P then we use (peg()) to denote the arrival time of candidate 1. However, if at time lj no candidate is added to set P then we define (peg(s) to be equal to oo so that the literal (tpek(i) > x is true for every R.
now analyze the case where {u, < ûr; + +eg is true and define the following event:
E =
A Meaaa
{tn < 1/3) A (1/3 <t, 1/23 A (tr, > 1/23 (tpeg() tr.
21

---

To simplify notation, let P, be the random variable denoting the pegging set at time ł, before the execution of the while loop because of j's arrival. We let F; = { - Uj < uy + Et, (P, ( be the random variable which contains all candidates that could be "pegged" at time fz.
In addition we define event T as follows:
T
(tr < <1/33 A 11/3 < < 1/2) A tt, 1/2]
(r1 (Pa0::
Before lower bounding the probability of event & we argue that:
Pl(pegts) 2 cr, T N 2/3
Let Fj denote the set of all non non-empty subsets of [n] such that PIF, = fj []] > 0. Note that
P(F, = 0 7 + ,,, P(F, = fg [
From the law of total probability we have:
P( P((peg(s) 2 tr; [T]
(1)
P(((per(i) 2 (r (F, 0) 17] + p(tlie))) 2.d A (F, # I7]
(2)
P[E 0 [1] P((lpe(() 2 t. A (4) + 0} [7|
(3)
P(F, 0 1
Σ P((tpeg()) 2 4r {F, f,} 17]
(4)
f55
= PIF, = 0 7 +
P((DeR() tr. [FF = AT) P(F, = 5z 17 FEEF
Σ
(5)
Where from (2) to (3) we use that if Fj 0 then the condition of subcase3b is false, thus no candidate is "pegged" and consequently {pog(s) = oc. From (3) to (4) we used that {Py * 0} = V V,, (F, fz}. We now focus lower bounding the summation term
Σ Plepeet 2 br - [3) AT 11 17 hE
Σ
P(tpeg(i) 2 tr [14 = f3} AT: PIF = fa f
7|+
1 (EFepeelj))
Σ
P(tpog(i) 2 tr (F, ff} AT P(F, = fj IT|
Σ
1. P.P = f3 17 +
Σ
Pl(peg() 2 br [ = AAATT] PLT, S 17]
We proceed lower bounding the term P P(opt) 2t,, 1FF= T| for all f, E E peg (5) # ri Note that the conditioning {F, = -5}} ^ changes the distribution of random variables (peg()): lr, as follows: tr, is uniformly drawn from [1/2, 1] and fpgg(s) is uniformly drawn from [z, 1] for some E [1/3, 1/2] which equals the realization of the random variable tj. We define a random variable (egg() which is stochastically dominated by (peg(s) and is drawn uniformly from [1/3, 1] as follows: let f be uniformly drawn from [1/3, 2) and B ~ Bernoulli((z - 1/3)/ 1/3)) then we define:
{peR(s) B B B) tpek())
Note that since 7 S (pea(s) then also (pee(t) S (pez()) holds almost surely.
Therefore we have:
P P((pez() 2tr, tr, (FF = fAATT] 2 P (peai) tr, 1{F = f AT]
2 3/8
22

---

We proceed to bound the initial summation as follows:
Σ
plu,
24, 4n
= f1
Σ
1. 1 +
Σ
P P(ur, 4n (F3 f3) AT
P(P, = 15
2
Σ
P[F = 13 17
Σ
(3/8) P(Fj = 13 17
2 (3/8)
Σ
P(F} = 1z [T]
GEF
We then have:
Pl(peg() 2 lr [
(6)
= P[F, = T + Σ
P M1 2 tr (FF = ATAT P(F, = 13 17)
(7)
PlF, 0 01 (3/8)
Σ
P(F = 17
88)
SEE
2 (3/8)
P(F, = 1
Σ P(F, = f, 1
(9)
fEF
3/8
(10)
We are now ready to lower bound the probability of event & as follows
P[g] = P[T] P Plepeg() 2 L, [T]
2 P[T]- (3/8)
II
PIu 1/3] PIL/3 <t 11/2)-(3/8)
2 (1/3)*. (1/2 - 1/3)- (3/8)
= k1/
Similar to the analysis of the first case the first literal of & 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 ry. In addition, since t, 1/2 then have that j remains in H until least time t,. 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 E's implications regarding the execution of our algorithm at j's arrival by distinguishing between two mutually exclusive cases, that is whether r; is in P before time ty or not.
If rs is not in the pegging set exactly before time ty then we have that the conditions of case 3b are true. Indeed note that since
S Et, we have:
(j' J j uy < uy + &t, 2 jj:uauua dy + + \ (P) 9
Thus, are in the candidate j is added to B and (peg(r) < co. Due to the literal (peg(s) 2 b,, of & 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 Ti, can deduce that at time fr. is still in B. Thus, at time fr, the conditions of subcase 4a are true and rú is added to S. If r; is in the pegging set exactly before time t, then since the conditions of case 4 are false for any candidate except possibly r; can deduce that at time (,,, candidate r; is still in the pegging set and is added to the solution through case I.
where at time Lú candidate (which may be r:) is added the pegging set,
Combining all the different lower bounds on P(r: S] we conclude the lemma.
23

---

Lemma 10. For all E (1.2....,,ky, k3: P(r E S] 1-
256
Proof. Let 8 12/k be such that i (1 (1-8")k 8') 1. We now argue that proving P/r. E S] 2 8//256 suffices to prove the lemma.
First, we underline that such 8' exists only for i < k- 13. Indeed,
i i+1 61>12/k
- 81- = d =
i k- 13
k
For all < k 13 we have:
1+1
i+
P(ra E S) 2 8 255
K
&
256
256
For i 2 l: 13 the statement of the lemma is vacuous, since:
1 ++113
plr, S] 2 0
256
Consequently, from now on we focus on proving that Pfr; E 2 8/56.. We do so by defining an event & for which P 8/ /256 and argue that & implies r; being accepted.
Before defining & we need to introduce some auxiliary notation. call replacement set and denote by R the set of indexes initially in H with value lower than ur, i.e., R = (i Ury > Uj} n [A] and by j juorse- = argmaxjeR the index of the candidate with the highest error in R. For any
which contains all indexes except and jworse of candidates arrived between times and t'. Also, for æ [n]
t, E [0, 1] we define the random variable Ar,'' = [j : t tj S 1'} {
we define the set function 1₂2 2(n] + 20x1, such that for any subset Y C Ln) contains the æ indexes with highest true value in Y. For E (0, 1/2) let (a) R1 RRn Ag.1/2+6 and R2 Rn 1//26611 the random variables denoting candidates of R [[woorse) arriving before and after time 1/2 + ő respectively; and (b) let M [[1++25)k] (Aa.1/245) A1/2,1/2-5 denote the random variable containing candidates which arrived between times 1/2 and 1/2 d with the [(1 + J5 higher true value among the ones arrived before time 1/2 + 5 (excluding r; and padjjwnn jworse).
We now define event & Let d = 8//16:
ع {
1/2 25 5 8'k } A {IM 48k) A (1/2 <1/2 A (tyworsa < <tr
The literal {IM] < 45k} implies that at most 48k candidates not in H or not "pegged" by a previously arrived candidate in H may be added to our solution between times 1/2 and 1/2 5. In addition, each candidate in M through subcase 4b may delete from H at most one candidate with arrival time after 1/2 + 8. Consequently, the number of candidates in R that are in H until time 1/2 + ō are at least
|R2l - MM. We first argue that { Rg 2 1/2-25 8' k} and |M] < 48k implies that R2 |M] > ie.. until time 1/2 + å at least one candidate from the replacement set R is still (note that initially we have R C H [k].
1/2 28 8'k 46k
[R2l |M|
1 1
1
8 48k
> (8'/3 48)k
2 (8'/3 48' 11/1
2/ (6'/12)k
where in the second inequality we used that 8 = 8' /16 < 1/16 < 1/10.
We continue arguing that E implics that the conditions of subcase 4b are true at time t,, For every candidate j E Rz it holds that:
Ur > Uj 2 úg 2 ú, Cjworse 2 û - Et.;
24

---

Where the first inequality comes from the definition of set R since R2 C R. the second from the definition of the error, the third from the definition of juarse and the last from the fact that lymorse < lr; implies Et. 2 'jworse, Thus, we have that at time 4r there is at least one candidate in H for which Ur, 2 ûj - Et.," 1 consequently the conditions of subcase 4a are true, and candidate r; added to our solution.
We now lower bound the probability of event E. Since R2 and M do not contain neither r' nor j ju we have that events R| 2 - 8' {MM] < 46k} are independent of the time arrival of j jworse
and ri. Thus,
1/2- 28 1-6
P[ε] P [[
8'k} A {IM < 48k}
P[L/2 < t,, < 0] Plt, suorse < 1/22
1/2 28
P (112a)
8'k) A {1M) < 4ōk}
8 (L/2)
1 5
[1 1/2 25 25
(8' /32) P
8kk} A {| < 48k)
1-6
(32/ P (1Rg1 < |R| 1/2 - 28
1-6 8'k} A {I < 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ı and it is such that M stochastically dominates JM). We prove the stochastic dominance of M using a coupling argument.
Note that every candidate accepts an arrival time & uniformly at random from [0, 1]. We now describe an equivalent procedure create the arrival times t.. Each candidate i draws three independent random variables B; ~ Bernoulli + 8), e ~ Uniform([0, 1/2 + 8)) and 12 Uniform([[]] + 6, 1]). Note that we can construct random variables L using B,, 1 and 2
as follows:
+ 4 B.)- -
4 4 B
Let l = (41440))(Aoo.121/41 and denote by hi,..., by the set of candidates in (000-10)(Aoo1122-2-
We define random variables [,,... ........ ......,,11... ((1+ follows: For each j {I....,{} we define i, 1, and for each j E {l (1+1) I,...,,.. 1 + 45k} we define &, ~ Uni forf + 6)). We define M
E [(1++18k1 T {T, > 1/2} and since M - M = Ei ((1+25) T [T, > 1/2} we have that M 2 | almost surely. Note that random variables i, and random variables B; are independent. Consequently, since RR EiER B, have that events {M < y) and { < æ) are independent. Combining
these observations we have:
1/2 28
P [RR < |R|
8'k} A {1 < 40k}
1-6
1/2- - 25
>
(RR) < |R|
8'k} ^ {M < 48k}
1-
1/2
28
>
R1 < [R|
8'k
PPM < 48k]
1 1 8
1/2
26
>
R N
8'k
PMM < 45k]
1 8
To upper bound P[M < 48k] note that M = ((1+45)k] 5
1/2-a < 35k, where the last inequality
holds since 1/2 1/16 2 8' 1//16 6. From Markov's inequality, we have that:
25

---

PIM > 48k) = PIM > (4/3) 35k]
S PIM (4/3) E[
I (3/4)
Consequently
PIM < 48k) > (1/4)
Note that since i < -1--00 (1-8')k 1 we have that [R] 2 8'k +
R2I] = |R \ (worse [1 112 8) 2 8'k(1/2-6)
From Markov's inequality, have that:
1/2 - 20
1/2 28
P R2
1-8 J'k:
P R2
E R2ll
(1 8) (1/2 6)
(1 8) - (1/2 8)
1/2- 25
(1 8) (1 (1-
1 48
(1 8)
Consequently,
P[E] 2 (6'/32) (1/4).(1-0 (1-
2 (6'/32) (1/4) (1/2)
2 (6'6)
]
Theorem K-PEGGING satisfies smoothness and fairness for k-secretary with and 1-(++33)/k j for all ê t= =1,...,k
Fe max (1/3)k+
256
Proof. The theorem follows directly from Lemmas to 10
C Additional experimental results
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
26

---

Table I: Competitive ratio (mean # std deviation) on Almost-constant
ADD.-PEGCING
MULT.-PEGGING
LEARNED-DYNKIN
DYNKIN
HIGHEST-PRED.
0.0
1.00 0.00
1,00 0.00
1.00 + 0.00
0.64 + 0.48
1.00 + 0.00
0.05
0.97 +.02
0.97
0.95 0.00
0.62 0.47
0.95 # 0.00
0.1
0.05
0.05
0.90
0.61
0.90
0.15
0.00
0.07
0.85 0.00
0
0.85
0.2
0.09
0.89
0.00
0.59
0.80
0.25
0.83 0.12
0.83
0.02
0.57
0.75 #
0.3
0.14
0.14
0.70
0.44
0.70
0.35
0.17
0.17
0.003
0.54
0.03
0.4
0.19
0.19
0.00
0.43
0.00
0.45
0.20
0.70
0.004
0.53
0.04
0.5
0.27
0.27
0.50
0.51
0.50
0.55
0.26
0.64
0.06
0.49
0.06
0.6
0.29
0.21
0.06
0.48
0.06
0.65
0.37
0.37
0.36
0.46
0.06
0.7
0.34
0.33
0.36
0.45
0.31
0.75
0.36
0.36
+.36
0.44
0.26
0.8
0.37
0.38
0
0.42
0.21 =
0.85
0.400
0.40
0.31 0.39
0.446
0.16
0.9
0.40
0.40
0.28 + 0.40
0.39 0.46
0.11
0.95
0.445
0.37 1377004 0.45
0.26 + 0.41
0.38 + 0.47
0.06
Table 2: Competitive ratio (mean std deviation) on Uniform
ADD.-PEGCING
MULT.-PEGGING
LEARNED-DYNKIN
DYNKIN
HIGHEST-PRED.
0.0
1,00 = 0.00
1.00 - 0,00
1,00 # 0.00
0.57 = 0.45
1.00 # 0.00
0.05
1.00 0.01
1.00 0.01
1.00 # 0.01
0.58 0.45
1.00 #
0.1
0.02
0.99
0.99 + 0.02
0.58
0.99 = 0.02
0.15
0.98
0.98
0.99 + 0.04
0.57
+ +.09
0.2
0.07
0.06
0.98 0.05
0.57
0.98 0.05
0.25
0.96
0.96
0.007
0.445
0.97
0.3
0.12
0.14
0.95 0.08
0.44
0.95 0
0.35
0.11
0.12
0.110
0.44
0.14
0.4
0.19
0.10
0.93
0.56
0.93
0.45
0.17
0.19
0.92
0.54
0.92
0.5
0.20
0.17
0.13
0.58
0.11
0.55
0.22
0.86
0.90
0.57
0.10
0.6
0.21
0.24
0.89
0.57
0.8940.14
0.65
0.79
0.23
0.22
0.58
0.89 0.15
0.7
0.27
0.21
0.66
0.57
0.88 0.15
0.75
0.76
0.80
0.44
0.57
0.87 0.16
0.8
0.73
0.78
0.44
0.44
0.87 0.16
0.85
0.33
0.77
0.443
0.58 0.45
0.86
0.9
0.30
0.26
0.61 0.43
0.57 0.44
0.86
0.95
0.38
0.22
0.61 0.43
0.57 0.45
0.85
27

---

Table 3: Competitive ratio (mean + std deviation) on Adversarial
ADD.-PEGGING
MULT.-PEGGING
LEARNED-DYNKIN
DYNKIN
HIGHEST-PRED.
0.0
1.00 = 0.00
1,00 0.00
1.00 + 0.00
0.57 + 0.45
1.00 + 0.00
0.05
1.00 0.01
1.001
0.000
0.57 0.45
= 1.00
0.1
0.09
0.09
1.00
0.57
1.00
0.15
0.05
0.05
1.00
0.47
1.00
0.2
0.06
0.06
1.00
0.47
1.00
0.25
0.00
0.98
1.00 0.000
0.445
1.00
0.3
0.07
0.07
1.00
0.58
1.00
0.35
0.97
0.97
1.00 0.00
0.44
1.00
0.4
0.07
0.07
+.00
0.58
1.00
0.45
0.97
0.97
1.00
0.44
1.00 0.00
0.5
0.97
0.97
1.00
0.57
1.00
0.55
0.97
0.97
1.00
0.57
1.00
0.6
0.17
0.17
1.00
0.57
1.05
0.65
0.16
0.13
0.40
0.47
0.98
0.7
0.22
0.22
0.60
0.57
0.88
0.75
0.32
0.31
0.40
0.58
0.64
0.8
0.36
0.39
0.40
0.54
0.34
0.85
0.47
0.42
0.59 0.44
0.47
0.17
0.9
0.57
0.42
0.61 0.43
0.58 0.45
0.14
0.95
0.56
0.49
0.60 # 0.44
0.58 + 0.45
0.14
Table 4: Competitive ratio (mean + std deviation) Unfair
E
ADD.-PEGCING
MULT.-PEGGING
LEARNED-DYNKIN
DYNKIN
HIGHEST-PRED
0.0
1.00 0.00
1.00 0,00
1,00 # 0.00
0.63 # 0.48
1.00 = 0.00
0.05
0.99
0.99 2 0.01
0.98 0.00
0.63 # 0.48
0.98 # 0.00
0.1
0.02
0.99
0.00
0.64
0.95 # 0.00
0.15
0.98 0.02
0.02
0.000
0.65
0.93 # 0.00
0.2
0.03
0.08
0.91
0.64
0.91 # 0.00
0.25
0.04
0.04
0.000
0.44
0.88 # 0.00
0.3
0.04
0.96
0.00
0.64
0.86
0.35
0.05
0.05
0.000
0.64
0.80
0.4
0.06
0.05
0.02
0.64
0.82
0.45
0.95
0.06
0.00
0.448
0.80
0.5
0.94
0.04
0.78
0.64
0.00
0.55
0.94
0.94
0.76
0.44
0.76
0.6
0.93
0.98
0.74
0.64
0.74
0.65
0.99
0.09
0.73
0.44
0.73
0.7
0.92
0.12
0.70
0.64
0.71
0.75
0.12
0.92
0.000
0.64
0.69
0.8
0.92
0.92
0.67
0.64
0.67
0.85
0.91
0.91
0.000
0.64
0.66 0..00
0.9
0.91
0.91
0.64 0.00
0.64
0.64
0.95
0.90
0.90
0.00
0.64
0.02
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes].
Justification: Each claim in the contributions is made as 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 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 long is clear that these goals are not attained by the paper.
2. Limitations
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 the main paper.
Guidelines:
The answer NA means that the paper has 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 (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn 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 few datasets or with 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, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
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 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
29

---

Answer: [Yes].
Justification: All theorems are clearly stated and proofs are written in detail either in the main paper in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes].
Justification: In the experiments section we describe in full detail the experimental setup and also submit the code in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
30

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions 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.
Please see the NeurlPS code and data submission guidelines (https://nnis.cc
aublic/guudees/Cdeeeuuii.. wtw.eeeewuumissioooooooooooo for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ wttps/cccppplcccuui.eeaeaecccuea
www.ssssiicggoooooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, 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 the core the paper to 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, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes].
Justification: We present the mean and standard deviation of the competitive ratio for each dataset/prediction error/algorithm tuple 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 emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
31

---

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 the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer:[Yes
Justification: Yes, we mention the characteristics of the CPU 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 include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums 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).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https::/neurips.. https////bll/tcciiccceeeeeeeeeee
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 NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. 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 discuss fairness notion and how it relates to other fairness notions in the literature, and in the limitations section we discuss how different notions required to capture different faimess considerations.
Guidelines:
32

---

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 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 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 unintentional) misuse of the technology.
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).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
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 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 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make 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 used and, 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.
33

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
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 not available online, the authors are encouraged to reach out to the asset's s creators.
13. 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/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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.
14. Crowdsoureing 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 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 the supplemental material is fine, but if the main contribu- tion 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.
15. 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 equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA].
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending 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.
34

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere 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.
35


Reviews:
[{"review_id": "4JYRyaQiqO", "reviewer": "Reviewer_3Mim", "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.", "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. \n\n2) 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.\n\n3) In Figure 1, why does the competitive ratio of Dynkin go down with increasing epsilon? Shouldn't it be independent of prediction error?\n\n4) 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": "Yes, limitations have been addressed.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "The biggest strength of this work is its originality; it is one of the first works in the area of algorithms with predictions to study fairness of these algorithms. This work has the potential to spur up similar interesting questions for other existing problems/algorithms in the literature.   The key ideas are simple and the analysis is sound.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and effort in reviewing this paper.\n\n- \"Can you please define I_pegged formally?\" and \"clarify initial conditions for Algorithm 1?\":\n> $I^{pegged}$ should have been initialized to the empty set before the start of the while loop. We will fix that omission. With this initialization and subcase 2b in Algorithm 1, $I^{pegged}$ is then defined formally. \n\n- \"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.\":\n> We used the model where candidates have arrival times $t_i \\in [0,1]$ to simplify the analysis. As mentioned in lines 164-166, that model is equivalent to the model where candidates arrive in a uniform random order. We agree that the algorithm would be easier to read with your suggestions; thank you. We will introduce a random permutation $\\sigma(t)$ mapping time steps $t \\in 1 … n$ to indices of candidates and update the algorithm to have, as suggested, a for loop over $t \\in 1 … n$ as well as return statements.\n\n\n- \"why does the competitive ratio of Dynkin go down with increasing epsilon? Shouldn't it be independent of prediction error?\":\n> In general, the competitive ratio of Dynkin should indeed be independent of the prediction error. However, in this experimental setting, the construction of the instance itself depends on the prediction error, which is why the performance of all algorithms (including Dynkin) depends on the prediction error. We will make this clearer in the future. We also emphasize that this experimental setting is replicated from the earlier work of Fujii-Yoshida as we aim to compare our algorithm to theirs.\n\n\n- \"it might be illuminating to have a simple example of unfairness of an existing methods at the end of Section 2\":\n> We expand on why previous algorithms lead to unfair outcomes in Appendix A but we acknowledge that a short paragraph at the end of Section 2 would improve our paper’s readability. Thanks for the suggestion; we will add such a paragraph.\n\n\n- \"minor typos at the top of Page 3 incorrectly referencing [3] instead of [4].\":\n> Thanks for catching the wrong reference; we will fix it!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8gFqDoJPCB", "reviewer": "Reviewer_3Rre", "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.", "questions": "If we require $1-C\\epsilon$-smoothness, does that imply an upper bound on the achievable $F$ for fairness, and vice-versa?", "limitations": "The authors have adequately discussed limitations regarding their definition of fairness.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "This paper identifies an interesting and overlooked issue for the secretary problem with predictions, giving an elegant solution to it, for both the single-choice and multiple-choice secretary problems with predictions, and validates this using the experimental setup from prior work [25].  The presentation is overall clear.", "weaknesses": "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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and effort in reviewing this paper.\n\n- “Upper bound (impossibility results) are not explored, making it unclear if these are the tightest results for this setting” and “If we require $1 - C\\epsilon$ smoothness, does that imply an upper bound on the achievable $F$ for fairness, and vice-versa?”:\n> Our main goal was to achieve constant-smoothness and constant-fairness and we did not focus on optimizing the constants. Thus we believe that the constants can be improved. Indeed our algorithm is 4-smooth and 0.0625-fair and with some further optimizations, we can achieve fairness with parameter 0.074. \nIn terms of impossibility results, we can show that constant smoothness implies an upper bound of $F = 0.348$ for fairness. The proof follows from previous work: Fujii and Yoshida prove that for any constant $C$, there is no randomized algorithm with a competitive ratio better than $\\max(1 - C\\epsilon, 0.348)$. Since a $C$-smooth and $F$-fair algorithm has a competitive ratio of at least $\\max(1 - C\\epsilon, F)$, this impossibility result implies that the best achievable fairness for any $C$-smooth (where $C$ is a constant) algorithm is $0.348$. We will include this in the paper, along with a discussion on impossibility results and future research directions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DMfSCoBxom", "reviewer": "Reviewer_uZ3G", "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.\n\nThis 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.", "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": "The authors are sufficiently discussing limitations of the model and algorithm in the limitations section.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper is well-organized, clearly written, and easy to follow. The proofs are involved, and most of them are deferred to the appendix, but the main idea is clearly addressed in the main body.\n- The problem setting is based on the existing study by Fujii and Yoshida (2023). This paper proposes a new algorithm for this setting with the property of choosing the best candidate with a constant probability (the authors call this property ``fair''). This is an interesting improvement.\n- The extension to the multiple-choice secretary problem is a good technical contribution. Fujii and Yoshida also considered this setting, but they proposed only an algorithm with $1-O(\\log k/k)$-type guarantee. This paper proposes a constant-factor guaranteed algorithm, also with a property of choosing top-$k$ candidates with a constant probability.\n- The experimental results clearly show the empirical superiority of the proposed algorithm.", "weaknesses": "- 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.\n- 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.\n- 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.\n\nMinor comments:\n- The last line of page 2 contains wrong links to the reference (matroid secretary and knapsack secretary).\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and effort in reviewing this paper.\n\n- “Although I am not familiar with the existing literature on fairness, I do not fully understand why the authors adopt this terminology.”: \n> The literature on fairness contains many different definitions of fairness. We propose one definition in the context of secretaries with predictions that is motivated by the potential unfairness caused by erroneous predictions. We consider the true best candidate to be the most deserving candidate for selection and, as mentioned in lines 55-56, we consider it unfair for this true best candidate to have no chance of being selected due to some erroneous prediction. That being said, we believe there might be other definitions of fairness that would be interesting to explore in the secretaries with predictions problem.\n\n\n- \"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.\":\n> An alternate motivation for deriving our result is that the negative result in Fujii-Yoshida is also an upper bound on what we call “Fairness”, i.e. an upper bound on the probability of accepting the best candidate. By contrast, their algorithm only has a non-trivial lower bound on the competitive ratio in terms of valuations, and in fact (as we show in Appendix A.1) can have zero probability of accepting the best candidate.  Our result was motivated by their paper, and one of our initial goals was bridging this gap between their upper and lower bounds, which we view as a theoretically natural question.\n\n\n- “The constants in the guarantees are not optimized, probably for theoretical simplicity. 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.”:\n> As explained in our previous response, we are looking to guarantee\n$$P[A = i^*]  \\geq  F \\quad (I)$$\nfor some constant $F$, which is stronger than guaranteeing\n$$E[u_A] \\geq F \\cdot u_{i^*}\\quad (II)$$\n(as done in Fujii-Yoshida).  We believe that a priori, it was unclear how to even achieve a constant $F$ for (I) while preserving 1-consistency (optimal competitive ratio when the predictions are exactly correct).  This is why we did not focus on optimizing constants, although with a bit of work, we are able to increase our guarantee on $F$ from $1/16=0.0625$ to $0.074$.  We will include this improved bound in the updated version. While we acknowledge that this ratio is still much smaller than the $0.215$ from Fujii-Yoshida, we emphasize that constants are much harder to achieve for (I) than for (II).\nWe believe that achieving the optimal guarantees for this problem and characterizing the pareto-optimal curve in terms of smoothness and fairness is an interesting and challenging open direction.\n\n- “The last line of page 2 contains wrong links to the reference (matroid secretary and knapsack secretary)” and “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.”:\n> Thank you; we will fix the references as follows: the matroid secretary was introduced by Babaioff et al.in SODA 2007 (Matroids, secretary problems, and online mechanisms) and the knapsack secretary was introduced in [7].\n\n- “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?”\n> For Dynkin the probability of selecting the highest true value candidate is around $0.37 \\simeq 1/e$. A necessary condition for that to happen is that this candidate arrives between times $[1/e,1]$. However that condition is not sufficient as the second highest true value candidate could also be selected if it arrives before the highest and after time $1/e$. The $0.37$ probability comes from a delicate analysis of all such events and we defer to Dynkin's algorithm analysis in [29].\nFor our algorithm the probability of selecting the highest true value candidate varies from $0.33$ to $0.34$. 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. (see the function generate_data_sets in our code for further details).\nWhile it may be difficult to find a closed form solution to this probability, similarly to Dynkin’s algorithm, the highest true value candidate arriving in $[1/2,1]$ is not a sufficient condition to be selected. Indeed, if the second true value highest candidate arrives after $1/2$ and before the highest true value then it may be selected by case 4 of our algorithm as predicted and true values of all candidates except the highest true value are equal to $1$ (modulo the small noise that we add to break ties).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "V1aZjcfJvc", "reviewer": "Reviewer_Le4z", "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.", "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?\n\n- 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": "Yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- This paper addresses an important and timely topic by investigating algorithmic fairness in the presence of potentially biased machine-learned predictions. The authors effectively identify the potential unfairness introduced by biased predictions and propose a novel algorithm to resolve these fairness issues within the context of secretary problems with predictions.    \n\n- The pegging idea used for the design and analysis of the algorithm for the secretary problem with predictions is both interesting and effective. Additionally, this idea can be extended to the k-secretary problem, and the treatment of general prediction errors is also noteworthy.\n\n- Extensive empirical tests clearly demonstrate the advantages of the proposed algorithm over SOTA learning-augmented algorithms in terms of both fairness and competitiveness.", "weaknesses": "- 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.\n  \n\n\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and effort in reviewing this paper.\n\n- “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?”\n> The formal fairness definition (see line 148) is the probability of selecting the candidate with the true maximum value. The motivation for our definition of fairness, which is based on providing guarantees only for the first-best candidate, is the following: in the offline setting where all the true values are known to the decision-maker we consider that the most deserving candidate of being selected is the first-best candidate and that the fair and optimal decision would be to select the first-best candidate with probability 1 (and the second-best candidate with probability 0, even if the true value of this candidate is very close to the true value of the best candidate). This offline setting motivates why our notion of fairness does not provide guarantees for the second-best candidate. \nThat being said, we do agree that other notions of fairness would be interesting to explore. For example, as suggested by the reviewer, it would be interesting to explore a notion of fairness that provides guarantees not only for the first-best, but all candidates who are in the top-$\\ell$, for some integer $\\ell$, and/or those whose value is close to the value of the best candidate. We also note that our fairness definition for the $k$-secretary problem aligns with this direction.\n\n\n- “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?”\n> $C=4$ comes from the fact that the true values of the candidate $i^*$ and $\\hat{i}$ can differ by at most $2 \\epsilon$ and the true value of any candidate in the set $I^{pegged}$ and $\\hat{i}$ can also differ by at most $2 \\epsilon$. We could change the definition of $I^{pegged}$ to include ``more exploration’’ on finding the best candidate which would lead to a larger value of $C$. However, with our current analysis, we do not see how such a change can improve the fairness constant $F$.\nRegarding other trade-offs: we can improve the fairness guarantee from $1/16 = 0.0625$ to $0.074$ and show that constant smoothness implies an upper bound of $F = 0.348$ for fairness. The proof of the latter follows from previous work: Fujii and Yoshida prove that for any constant $C$, there is no randomized algorithm with a competitive ratio better than $\\max(1 − C \\epsilon, 0.348)$. Since a $C$-smooth and $F$-fair algorithm has a competitive ratio of at least $\\max(1 − C \\epsilon, F)$, this impossibility result implies that the best achievable fairness for any $C$-smooth (where $C$ is a constant) algorithm is $0.348$. \nExploring other trade-offs and finding the pareto-optimal curve in terms of smoothness and fairness are interesting directions. The main reason why achieving a smooth tradeoff between fairness and smoothness is challenging is the following: any bound on C for the smoothness implies a competitive ratio of $1- C \\epsilon$, which implies a competitive ratio of 1 when the predictions are exactly correct. Thus, regardless of what the smoothness guarantee is, we must achieve a competitive ratio of 1 when the predictions are exactly correct, which makes it challenging to improve the fairness guarantee F, even at the expense of a worse smoothness constant C.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)