Addressing Bias in Online Selection with Limited Budget of Comparisons

We thank the reviewer for their feedback on our submission. We fully agree with the positive evaluation made, both in terms of strengths (solid theoretical study and introduction of a novel and realistic variant of the multi-color secretary problem) and in terms of future work (rigorous theoretical study of the multiple group case). We provide a detailed reply to the weaknesses and questions raised below.

• Focus on two groups. The single threshold algorithm is studied for multiple groups, and the analysis shows how the dependence between $K$ and $B$ impacts the success probability. For algorithms with group-dependent thresholds, the analysis with two groups is already technically challenging and necessitates heavy computations. The analysis for an arbitrary number of groups $K$ should be technically possible. We believe that this study constitutes a logical future work for a journal version of this paper.

• Minor comments. We thank the reviewers for pointing out the typos. We went carefully through the paper and corrected all of them.

  • Regarding Figure 2, we preferred to display both acceptance regions depending on $\lambda t$ because the dynamic programming algorithm uses as a parameter the number of observed elements in $|G^1_t|$; $|G^2_t|$ is implicitly given by $t - |G^1_t|$. We believe that the current figure gives a good intuitive understanding of the inner logic of the algorithm.
  • $|G_t^{1/2}|$ should be $|G_t^{1}|$ instead. We corrected it.

• Alternative model. The single threshold algorithm with $K$ groups can be adapted for the first comparison model at a cost of $K-1$ additional costly comparisons. After the first $\alpha N$ candidates are rejected, $K-1$ comparisons are made between the maximum candidates from each group to identify the best candidate so far. The algorithm then keeps track of this best candidate. Whenever a new candidate becomes the best in their group, they can be compared to the current best candidate using a single comparison and the latter is updated accordingly. This approach enjoys the same guarantees as in Theorem 3.2, but with a budget of $K + B - 1$ instead of $B$.

  In the case of two groups, both models are equivalent, as freely comparing a candidate with the best in their group and then making a costly comparison with the best candidate from the other group is sufficient to determine if they are the best so far. Thus, the guarantees on algorithms for the case of two groups remain the same.

  This discussion was removed from the paper due to page limits and it was not included in the appendix by mistake.

Thank you for your response. Regarding the alternate model: You seem to have some space available still in your main body, so it would be worth including this as a brief discussion. Please also clarify in an update version of the paper what the lines in your figures mean, i.e. what do dashed and continuous lines each represent. I am updating my score.

We thank the reviewer for their feedback on our submission. We fully agree with the positive evaluations made, both in terms of strengths (solid theoretical study and introduction of a novel and realistic variant of the multi-color secretary problem) and in terms of future work (rigorous theoretical study of the multiple group case). We provide a detailed reply to the weaknesses and questions raised below.

• Weakness 1. The title of the paper is meant to reference the paper "Fairness and Bias in Online Selection" in ICML 2021. The bias here refers to the difficulty of accurately comparing candidates from different groups and our paper suggests that these comparisons can be made at a cost.
• Weakness 2. We thank the reviewer for this observation. We went carefully through the paper and corrected all the typos and presentation mistakes.
• Question. The analysis presented in Section 4 can be generalized to multiple groups, but this would significantly increase the overall complexity as the computations are already cumbersome and technically challenging for the case of two groups. Additionally, the results would become much more difficult to interpret and/or visualize (e.g., Figure 2 would be way heavier). For the aforementioned reasons we decided to postpone this study for a journal version of the paper, yet we agree that this constitutes a logical direction for future work.

Thanks for the rebuttal from the authors. I have no further questions. After reading the paper again and all the reviews, I think my previous rating is adequate.

We thank the reviewer for their feedback on our submission. We generally agree with the positive evaluations made in terms of strengths (solid theoretical study and introduction of a novel and realistic variant of the multi-color secretary problem). We provide a detailed reply to the weaknesses and questions raised below.

• Real datasets. In the secretary problem, the actual values of the items observed by the algorithm are irrelevant; only their relative order matters. Consequently, conducting experiments on real datasets is equivalent to using synthetic data. The key factors to consider are the budget, group proportions, and the number of candidates. We conducted experiments with various values of these parameters for two groups and additional experiments involving multiple groups are presented in Appendix A. We plan to include these experiments in the main body of the paper upon acceptance, as an additional page is allowed.
• Baseline methods. Since the multi-color secretary problem has not been previously studied with budget constraints, the only available baselines are the algorithms proposed by Correa et al. (ICML 2021), which are optimal for the case of zero budget, and the classical $1/e$ strategy for an infinite budget. In our experiments, we compare our algorithms to the success probability of $1/e$ and the optimal algorithms for a zero-budget scenario.