Fair Secretaries with Unfair Predictions

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.

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. - 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. - 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. - It is quantitatively unclear what the price of enforcing fairness in algorithms with predictions is. The proposed algorithm guarantees both smoothness C (that indicates the effectiveness of using the predictions) and fairness F. There should inherently be a trade-off between C and F, which is not discussed in the paper. And one natural question is whether the current algorithm is flexible and can be tuned to adjust the trade-off.

Questions

- Can you provide formal comments on the definition of fairness? Is the current algorithm fair for the second-best candidate, especially when the value of the second-best candidate is very close to that of the best candidate? - All proposed algorithms in the main paper provide a smoothness guarantee of C = 4. Is this by design or coincidence? If it is by design, why was C = 4 chosen, and is it possible to adjust the parameters in the algorithm to attain other trade-offs between consistency and robustness?

Rating

7

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

Yes

Summary

This paper considers the secretary problem with predictions. The decision maker is given predicted values for all the candidates in advance. The existing algorithm by Fujii and Yoshida (2023) hires the candidate with the **expected value** at least $\max ( \Omega(1), 1-O(\epsilon) )$ times the optimal candidate's value, where $\epsilon$ is the prediction error. On the other hand, the classical secretary algorithm hires the best candidate **with probability** $\Omega(1)$. Since hiring the best one with probability $p$ yields the expected value at least $p$ times the optimal value, the probability bound is stronger than the value bound. This paper proposes an algorithm that hires the best candidate with probability $\Omega(1)$ and achieves the expected value at least $1-O(\epsilon)$ times the optimal. For the extension of hiring $k$ candidates, the proposed algorithm hires each of the top-$k$ candidates with probability depending on $k$ and achieves the expected value at least $1-O(\epsilon)$ times the optimal. The experimental results show the proposed algorithm outperforms the existing method in various benchmark instances.

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. - 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. - 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. - 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. - The authors claim that fairness is motivation for improving on the existing result. For the reason mentioned above, I do not think this problem setting is very natural. - The constants in the guarantees are not optimized, probably for theoretical simplicity. Since there is no known lower bound, the existing papers on this topic (Antoniadis et al. and Fujii and Yoshida) focused on restoring or approaching the original bound $1/e$. In terms of that aspect, this paper's bound is not close to $1/e$ and difficult to highly evaluate. Minor comments: - The last line of page 2 contains wrong links to the reference (matroid secretary and knapsack secretary). - To my knowledge, the first paper that derives a constant-factor competitive ratio is the knapsack secretary paper. I think it should be mentioned somewhere.

Questions

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?

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors are sufficiently discussing limitations of the model and algorithm in the limitations section.

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.

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

Questions

If we require $1-C\epsilon$-smoothness, does that imply an upper bound on the achievable $F$ for fairness, and vice-versa?

Rating

8

Confidence

4

Soundness

3

Presentation

3

Contribution

4

Limitations

The authors have adequately discussed limitations regarding their definition of fairness.

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.

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.

Questions

1) Can you please define I_pegged formally? It is never defined and only mentioned at a high level in the preceding text. The reader is left confused when they reach case 1 of Algorithm 1, and ends up having to infer what this set is from case 2b (aka how are you deciding what the set of elements that would guarantee smoothness is). It is always better to help the reader. 2) Can you clarify the refine and clarify initial conditions for Algorithm 1? It would greatly help with readability if the algorithm presentation followed the standard format with input to the algorithm, initial values, and return. For instance, initialize I_pegged to empty set. Somewhat pedantic, but the while loop is ill-defined with the condition 'agent i arrives at time t_i'; for t in 1...T do ... with returns is a lot more sensible. 3) In Figure 1, why does the competitive ratio of Dynkin go down with increasing epsilon? Shouldn't it be independent of prediction error? 4) I understand there might be space limitations, but it might be illuminating to have a simple example of unfairness of an existing methods at the end of Section 2 or early in Section 3 to better shed light on the shortcomings (instead to relegating everything to the appendix). Also, minor typos at the top of Page 3 incorrectly referencing [3] instead of [4].

Rating

6

Confidence

3

Soundness

4

Presentation

2

Contribution

4

Limitations

Yes, limitations have been addressed.

response to rebuttal

Thank you for the clarifications and additional discussions on the multi-way trade-offs in the design. My overall rating of the paper remains the same.