Addressing bias in online selection with limited budget of comparisons

Summary

The paper studies an extension of the online secretary problems in which candidates from multiple groups arrive. The goal is to find the best candidate, but while within-group comparisons are free, inter-group comparisons are not available a priori and we have a limit of B queries to a comparison oracle for such comparisons. The authors study the single threshold algorithm in which we wait up until some time t and then either selects the first candidate if its the best among all groups so far (by doing a comparison) or if comparisons have been used up selects a candidate if it is the best candidate in its group seen so far. The authors derive a lower bound on the probability of success that converges rapidly to 1/e as the budget B tends to infinity. This algorithm is independent of the group proportions. For the case of two groups, they analyse a double threshold algorithm and show a more fine-grained analysis that does depend on the group proportions. They further provide the optimal memoryless algorithm for the case of two groups, facilitating the computation of the optimal bounds. They show that the double threshold algorithm fares well in comparison and that the optimal memoryless algorithm behaves like a double threshold algorithm in the large candidate limit.

Strengths

The idea of costly comparisons is interesting and the authors provide an interesting initial model to study this problem. I think this is a thorough and very well written paper. Although the results pertain to special case, they seem difficult to obtain. The numerical experiments are helpful and give insights into the problem, that may be hard to prove theoretically, such as Figure 4.

Weaknesses

The focus on the case of two groups is rather restrictive. Furthermore, it is unclear whether the techniques would generalise to further groups, or very much rely on this special case. In any case, the case for more groups seems non-trivial. The discussion on the alternate model is missing from the main body and appendix, despite available space in the main body. The figures would benefit from an explanation of what the dashed lines and what the continuous lines each represent. Detailed/minor comments: The sentence on line 36 is incomplete. Line 93: cardinal -> cardinality Line 148-151: Make the notation consistent with the pseudocode (whichever way around). Line 110: full stop missing Figure 2 and line? Why does the second row in Figure 2 not have (1-\lambad)t displayed instead? 256: cardinal-> cardinality What is |G_t^{1/2}| Line 259-260: The phrasing is unclear.

Questions

2. 103-104: While I appreciate listing two possible models (indeed, I think he first one seems more natural), you claim here that throughout the paper you discuss how to extend the results to model 1 (which to me appears more natural). However, reading the main body I didn’t see this. Can you please explain what the results are and specify where in the paper you discuss the first model?

Rating

7

Confidence

3

Soundness

3

Presentation

4

Contribution

3

Limitations

No concerns.

Summary

This paper studies a novel extension of multi-color secretary problem, where comparing candidates from different groups is possible at a cost. With a limited budget total, a Dynamic-Threshold algorithms family is introduced, and the success probability of a special case, i.e. single-threshold algorithm for K groups, is comprehensively analyzed. Moreover, in-depth theories have been studied in the scenario of two groups, including double threshold algorithms and the optimal memory-less algorithm.

Strengths

1. This paper investigates a novel variant of the multi-color secretary problem that allows comparisons between candidates from different groups at a certain cost. This problem setting is appropriate for some real-world recruitment scenarios. 2. The algorithms proposed in this article are supported by solid theoretical results and are simple to implement yet effective. 3. This paper is well-organized and presented in a concise, clear and fluent manner.

Weaknesses

1. The title of this paper is not quite appropriate, since bias defined in the field of statistics does not seem to exist in the multi-color secretary problem. I understand that there are different definitions of bias in real-life scenarios, but this could mislead readers in various areas. 2. There are some mistakes in the presentation of this article. For example, line 36 is not complete. Besides, the citation form in line 73 is not correct.

Questions

I would like to know whether the theories in Section 4 can be generalized to the case of more than 2 groups. If so, is the generalization straightforward?

Rating

6

Confidence

4

Soundness

4

Presentation

3

Contribution

4

Limitations

The authors adequately discussed the limitations of the paper.

Summary

This paper tackles an online hiring selection with budget problem. The authors propose a dynamic threshold method and provides theoretical analysis on the algorithm performance. The numerical experiments confirm the findings of the algorithm.

Strengths

1. This paper is well motivated, and the proposed method is technical sound. 2. Related work is extensively discussed and surveyed. 3. Extensive and rigorous theoretical analysis is provided.

Weaknesses

1. Although the problem is well motivated, it lacks of empirical analysis on real datasets and applications. 2. No baseline methods are compared in the experiments.

Questions

See above weakness.

Rating

5

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

See above weakness.