Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper considers a problem of academic recruitment where the committee aims to select a set of candidates that maximizes the total expected reward minus the penalty caused by deviation from the target (i.e., over-hiring or under-hiring). It considers three simple greedy algorithms: (1) PGREEDY: selecting candidates in order based on their likelihood to accept the offer $p_i$; (2) XGREEDY: selecting candidates in order based on their value (qualification) $x_i$; (3) XPGREEDY: selecting candidates in order based on $x_i\cdot p_i$. The authors conduct the accuracy analysis of these greedy algorithms under certain settings and show both positive and negative results. For different penalty functions (i.e., one-sided and two-sided linear/square loss), the paper also proposes algorithms that attain fully polynomial-time approximation and constant-factor approximation to the optimal objective. 
strengths_and_weaknesses: Strengths: 

1. The paper studies an interesting problem. In practical academic recruitments, multiple offers are typically made in parallel and target number of positions is typically treated as a soft constraint. This is captured in the model considered in this work.
2. The paper considers several simple greedy algorithms and conducts theoretical analysis. These results provide insights for better hiring practices. 


Weaknesses:

1. My biggest concern is the restrictive conditions/assumptions of the results. The analytical results highly rely on the structure of penalty functions (i.e., induced cost as a function of the target and the actual number of hires). The paper primarily considers two types of penalty function (one-sided linear loss and two-sided square loss), and most results and algorithms are limited to these function types. In practice, we don’t know the exact penalty function, and we see from the results that different penalty functions may lead to completely different conclusions. As a result, the proposed method may not be easily deployed in practice. 
2. The experiments only validate the proposed algorithms in synthetic settings; there is no real-world data that can be used for validation. Moreover, there is no other baseline method to compare with. The experiments show that when the candidate’s value $x_i$ and probability $p_i$ are negatively correlated (a realistic setting), the accuracy seems to be very low (e.g., in Figure 1, accuracy drops by almost half compared to the positive correlation case). It’s not clear how serious such a decrease is. What is the best attainable objective value $U(S*)$ for each target? It is important to highlight $U(S*)$ in the figures.

questions: 
1. In lines 215-218, the authors explained briefly why it’s difficult to analyze the algorithms under one-sided L2+ loss. Can you elaborate more? What does “quadratic factorization” mean and why it is an important property the objective needs to have? Why linearity is necessary for analyzing the one-sided loss?   

2. In experiments, the authors construct synthetic data based on the approach of Purohit et al. Can you explain why this is good modeling? How will the algorithms perform on data with other distributions?

3. The experiments show that when $x$ and $p$ are negatively correlated, the performance of all algorithms drops significantly compared to positive and no correlation (Figure 1). Does it suggest that algorithms should be developed by incorporating such a negative correlation?

4. In practice, penalty functions may deviate from one-sided linear functions. While the performance of algorithms is theoretically guaranteed under a one-sided linear function, they can still be evaluated empirically on other types of loss functions. I suggest authors conduct experiments on settings with other loss functions to examine the robustness of the algorithms. 

5. Algorithm 2, missing “{“ in lines 1-3; what are the notations $x|N_L$, $p|N_L$?
limitations: Yes
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper considers a recruitment problem in which a agent can make offers to a set of possible candidates. Each candidate is characterized by a value and a probability of accepting the offer. The agent must make a single batch of offers, choosing a subset of the possible candidates. The objective is to maximize the expected value associated to the candidates that accept, minus a penalty term the depends on the deviation from a target number of desired acceptances.
They consider different types of deviations: $L_1$ and $L_2$ losses, and $L_1^+$ and $L_2^+$ losses in which recruiting less candidates that the target number is not penalized.
The authors characterized the computational complexity of computing optimal strategies and provide approximation results when the problem is intractable.
Finally, they perform an experimental analysis. 
strengths_and_weaknesses: The paper introduces a new computational problem. A similar problem was studied with sequential interaction, while this paper considers a different interaction with a single batch of  offers. This model is more realistic in many settings.

The paper is well written, easy to follow, and provides a detailed analysis of previous works.

The technical results are technically involved and provide a complete picture of the problem.
questions: No questions.
limitations: Yes
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper investigates the problem of batch hiring in an academic recruitment setting. While previous works consider a hard budget constraint on the number of acceptance, the authors argue that this assumption is inconsistent in practice and carries computational hardness. Instead, they view the budget as a soft constraint with a penalty for overshooting the target. Under these assumptions, the paper shows that greedy heuristics demonstrate some desirable properties. Finally, the authors provide an algorithm that approximates the optimal solution within a constant factor in polynomial time.
strengths_and_weaknesses: Strengths:

- The paper provides a novel algorithm for the case of one-sided L_1 loss between the realized outcome and the target number of hires.

- The paper is well-written and well-organized. 

- The related work section is sufficient. 

- The discussion of greedy heuristics performances is sufficient and provides good baseline intuition for the algorithm.

- The theoretical guarantee of algorithm ONESIDEDL1+ is significant and improves upon the greedy heuristics in experiments. 

- The theoretical claims are supported by discussions that provide intuition to the proof.

- The numerical experiments section contains a sufficient discussion of the setting and explanations for choices of hyperparameters. The results of these experiments support the theoretical claims made. 

Weaknesses:

- There are a few inconsistencies in the numerical experiments section. In the description of Figure 1, the paper stated "n=50". However, in line 304, at the end of the line, the paper stated "n=40". In line 337, "\lambda = 1", there is no plot for such value. Instead, in Figure 2, there are plots for $\lambda$ with values 1.5, 5, and 30.
  
questions: - While the greedy heuristic is a natural benchmark, is there any other algorithm/benchmark that can be used for comparison in this setting? 

- Although the result for L_2 loss is discussed, does the same result hold for the two-sided L_1 loss? 
limitations: The authors have adequately addressed the limitations and potential negative societal impact in their paper.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes strategies to find the optimal batch of offers to make in a recruitment scenario, where the goal is to maximize the quality of the recruited candidates but there is a soft constraint on the maximum number of candidates that can be recruited (and it is uncertain whether candidates will accept an offer or not). When the penalty function that characterizes the soft constraint is based on the mean squared error, the authors provide a polynomial-time strategy that can be made arbitrarily close to being optimal; when the penalty function is one-sided and linear, they provide a polynomial-time strategy that has a constant approximation factor.
strengths_and_weaknesses: The problem seems to be well motivated. I especially like the explanation of why the sequential and hard-constrained setting studied previously in the literature fails to capture the more practical complexities of recruitment (as opposed to single-batch and soft-constrained setting considered in this paper). However, most of the evidence for this seems to be anecdotal, maybe it could be supported with more references.

The problem is explored fully. In particular, a practical strategy is proposed for both a two-sided penalty function (where recruiting fewer candidates than targeted is penalized explicitly) as well as a one-sided penalty function (where recruiting fewer candidates is not penalized explicitly, but it would implicitly lower the total quality of the recruited candidates). However, it is not discussed when would one strategy/penalty function would be preferred to the other. While a one-sided penalty function seems natural to me, it would have been nice to have examples where under-recruiting would require explicit penalty (on top of the opportunity cost of not recruiting as many candidates as possible).

The experiments seem to be the weakest part of the paper; I have put my questions regarding the experiments below.
questions: In all experiments presented, xGreedy seems to be equivalent to, if not better than, LowValueL1+. What is the reason behind this result? Is it because LowValueL1+ was run with $\tau=0$? If so, how sensitive is LowValueL1+ to the choice of $\tau$ and how would one tune $\tau$ for their specific problem instance? Is it because $p_{\text{min}}$ is not low enough to see the advantage of LowValueL1+ being a constant-factor approximation (as opposed to xGreedy whose performance depends on $p_{\text{min}}$)? If so, how does the performance difference between xGreedy and LowValueL1+ varies with respect to $p_{\text{min}}$? Since the performance xGreedy is lower bounded in terms of $p_{\text{min}}$, I assume it should be possible to make LowValueL1+ arbitrarily better than xGreedy. Is it possible to show this empirically? I believe more experiments are needed to answer these questions.

Also, I think evaluating the performance of the strategy proposed for $L_2$ with respect to the greedy strategies would have still been valuable. I understand that $L_2$ can be made arbitrarily close to being optimal but how would that compare to the greedy strategies? LowValueL1+ had different theoretical guarantees that made it more preferable over the greedy strategies, but the experiments revealed that xGreedy could perform better than a practical implementation of LowValueL1+ for most problem instances considered.
limitations: One limitation is that the strategies proposed in the paper are specifically designed for $L_2$ or $L_1^{+}$ penalty functions whereas a user might want to design their own penalty function according to the characteristics of their own problem instance based on historical data.
review_title: null

Meta-review: metareview: Thank the authors for their submission.

The paper studies a hiring problem, arguably a more realistic formulation compared to prior work. An agent has access to a pool of candidates, each with its own value and probability of accepting a hiring offer. The goal is to select a batch of candidates as to maximize the cumulative value of the candidates accepting the offer minus a penalty term for deviating from a target number of candidates.

The problem is fully explored considering multiple types of penalty terms. Optimal algorithms are provided whenever possible and otherwise approximation algorithms are shown, all attained using simple greedy strategies. Synthetic experiments are also provided. The paper is well-written and easy to follow.
confidence: Certain
Decision: Accept