Fair Secretaries with Unfair Predictions

We thank the reviewer for their time and effort in reviewing this paper.

• “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?”

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.  That 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.

• “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?”

$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$. Regarding 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$.  Exploring 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.

We thank the reviewer for their time and effort in reviewing this paper.

• “Although I am not familiar with the existing literature on fairness, I do not fully understand why the authors adopt this terminology.”:

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.

• "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.":

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.

• “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.”:

As explained in our previous response, we are looking to guarantee $P[A = i^*] \geq F \quad (I)$ for some constant $F$, which is stronger than guaranteeing $E[u_A] \geq F \cdot u_{i^*}\quad (II)$ (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). We 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.

• “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.”:

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].

• “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?”

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]. For 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). While 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).

We thank the reviewer for their time and effort in reviewing this paper.

• “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?”:

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.  In 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.

We thank the reviewer for their time and effort in reviewing this paper.

• "Can you please define I_pegged formally?" and "clarify initial conditions for Algorithm 1?":

$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. 

• "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.":

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.

• "why does the competitive ratio of Dynkin go down with increasing epsilon? Shouldn't it be independent of prediction error?":

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.

• "it might be illuminating to have a simple example of unfairness of an existing methods at the end of Section 2":

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.

• "minor typos at the top of Page 3 incorrectly referencing [3] instead of [4].":

Thanks for catching the wrong reference; we will fix it!