The Hidden Cost of Waiting for Accurate Predictions

We thank the reviewer for their insightful comments and for offering a fresh perspective on this problem. We agree that using statistical and machine learning tools to allocate resources presents a rich intersection of techniques from multiple disciplines. We appreciate the reviewer’s viewpoint and the different lens through which to study this issue. In the following, we discuss how our view is connected to the classic ML view and then discuss our modeling assumptions.

A risk predictor involves two types of uncertainty. First, the risk predictor may not be the optimal predictor for failure, given observations from the individual. This epistemic uncertainty, also known as the generalization gap, decreases as the planner collects more historical data and fits a better model. This is the focus of classical learning theory. Second, even with the Bayes-optimal predictor, the planner cannot fully resolve the uncertainty about an individual due to the limited number of observations available for that individual. This uncertainty can only be reduced by waiting to gather more information. The focus of our study is on the dynamics of this type of uncertainty and the tradeoff it introduces. But we agree that the first uncertainty is also an interesting and fundamental question.

With this context, we next discuss our modeling assumptions.

Re. $\tilde{p}$ is an increasing function. Do you have any examples about situations where it should be the case?

We interpret each observation as a signal about the unknown failure probability of an individual. Examples include a student passing or failing an exam, or a patient receiving a positive or negative lab result. It is natural to assume that a positive observation is positively correlated with the failure probability; equivalently, $\tilde{p}$ is an increasing function. In the examples above, this means that a student at greater risk of dropping out is more likely to fail an exam, or a patient at higher risk of diabetes is more likely to receive a positive test result.

Re. $\tilde{p}$ are assumed to be known, while in practice we might have access only to an (reasonably good) estimator.

We would like to clarify that, as discussed in line 162 and more formally in Proposition E.4, under our binary observation model and assuming a monotone $\tilde{p}(\cdot)$, the optimal ranking simply involves sorting individuals based on their number of positive observations. So we do not assume that the planner knows $\tilde{p}$. However, in analyzing the ranking and allocation, we do study how the functional form of $\tilde{p}$​ influences the conclusions.

Re. $o_i^t$ is essentially a binary variable. A more realistic assumption would have been to consider $o_i^t$ is a feature vector $x \sim P(x)$.

We agree with the reviewer that supposing binary observations is an assumption that was necessary to make our study of the dynamics of optimal ranking tractable. Though it is a stylized assumption, we believe it remains applicable in a number of real-world settings or serves as a reasonable approximation. For instance, medical lab results are often interpreted as binary outcomes, and a lot of key information about students, e.g., attendance or disciplinary action, is collected as binary information. Further, information like test scores is often reduced to pass/fail or other coarse information. That being said, we agree with the reviewer that enriching how the planner collects information is interesting, and we hope that with the foundations that this paper provides, it will be an area of further exploration.

We discuss the other concerns raised by the reviewer in the followup comment.

Re. The experiment's description could be expanded. … more examples with other realistic datasets might strengthen the overall message.

We thank the reviewer for this suggestion. We have updated the paper to clarify that, in this experiment, failure refers to dropping out of school, which is recorded in the data. We also define inequality as the smallest $G$ such that the distribution of dropout probabilities is $G$-decaying. While we agree that additional experiments could further enrich the paper, our goal in Section 5 is to demonstrate that our algorithm can find the optimal allocation in a realistic setting. Even in the simplest non-contrived settings, the tradeoff between gaining more observations and losing vulnerable individuals is evident. We thank the reviewer for this suggestion and believe that further empirical work is an excellent direction for future research.

Re. Algorithm 1 is not ``efficient'' in a computational sense … I would suggest the authors rephrase it in the manuscript.

We appreciate the reviewer for pointing this out. Our focus was on efficiency in terms of its independence from the number of individuals, which is often a significant bottleneck in resource allocation problems, as well as from the budget. However, we agree with the reviewer that the dependence on $T$ is also important. As a result, we have revised the language around efficiency in the updated version, using more precise terminology (e.g., lines 343 and 380).

Re. Minor nitpicking

We completely agree with the reviewer. In the current manuscript, we prioritized providing a comprehensive review of related work in the appendix rather than a brief one in the main text. We will certainly consider including a more concise version of the related work in the final version and appreciate the reviewer for highlighting this.

I thank the authors for their answers to my review. All my concerns and questions have been addressed and resolved. After reading the other reviews and the corresponding rebuttals, I have updated my score accordingly.

We thank the reviewer for their insightful review and helpful feedback. In the following, we address the points and questions raised by the reviewer.

Re. [Calling Algorithm 1] ``efficient'' might be misleading. … Can you discuss practical limitations with larger $T$ values?

We appreciate the reviewer for pointing this out. Our focus was on efficiency in terms of its independence from the number of individuals, which is often a significant bottleneck in resource allocation problems, as well as from the budget. However, we agree with the reviewer that the dependence on $T$ is important. We have revised the language around efficiency in the updated version, using more precise terminology (e.g., lines 343 and 380). While we typically consider time scales of months or years in social contexts, we acknowledge that at finer time scales, our algorithm may not be efficient, and a standard policy learning approach, such as reinforcement learning, would be more appropriate. We thank the reviewer for highlighting this point and helping to refine our language.

Re. (Minor, organisational) Section 3 could benefit from a restructuring

This is a great suggestion! We agree with the reviewer that presenting the main result earlier in this section enhances clarity. Accordingly, we have restructured Section 3 to present the main result immediately after introducing ranking risk, followed by a discussion of the steps leading to its proof. We appreciate the reviewer’s input and believe this change has improved the readability of our paper.

Re. (Minor, related works)

We thank the reviewer for pointing out additional related works. Azizi et al. is indeed a valuable complement to Kube et al. We also agree that our proposed dynamic is closely related to dynamic models of opportunity allocation (Heidari et al.) and the dynamics of wealth across generations (Acharya et al.). We have updated our literature review to include the suggested papers and appreciate the reviewer’s helpful input!

Re. The runtime for Algorithm 1 is with the general utility class, could it be faster with fully effective treatments?

This is an excellent question that we spent considerable time contemplating. Unfortunately, while we could improve the dependence on $T$ to something like $T/2$, as suggested by Theorem 4.3, we cannot eliminate the exponential dependency on $T$ when solving for the exact solution. Therefore, we maintain the presentation of Algorithm 1 in its most general way. We thank the reviewer for this insightful question, which prompted us to rethink this aspect!

Re. W1: The visualizations in Section 5.3 effectively illustrate the theories discussed. … Incorporating experiments or even basic numerical examples would make the theoretical results [in Sections 3 and 4] more accessible and intuitive.

We are glad that the reviewer found the visualization in Section 5 helpful. We agree that a similar illustration can benefit other sections, particularly Section 4. To further clarify the role of budget size and inequality in deriving the theoretical results of Section 4, we have added a one-page illustrative example in Appendix C, including an extensive discussion and visualization. This example intuitively demonstrates why high inequality, reflected in a low $G$, or a large budget, may favor earlier one-time allocations. We thank the reviewer for this valuable suggestion and believe the new illustration has enriched our paper!

Re. W2: The writing in Sections 3, 4, and 5, while necessarily technical, sometimes read dense.

We appreciate the reviewer’s suggestion to provide further intuition and summary to enhance the clarity of the results. We have improved the readability and clarity of the paper, in particular, we have restructured Section 3 to present the main result earlier, provided an illustration for Section 4, and further elaborated on Definition 4.2. If there are any remaining parts the reviewer recommends revisiting, we welcome any further thoughts.

Re. W3: Additional explanations could clarify specific aspects of the formulation. … [The paper] might also consider scenarios in which qualification probabilities are predicted instead.

To make sure we understand the reviewer’s question: We assume that by a qualification probability, the reviewer means a metric like student GPA, job applicant score, health measure, and so on rather than predicting school dropout, job retention, or hospital admission.

In this case, if the planner’s objective is still to prevent poor outcomes, then they may use these qualification metrics: e.g., by setting some threshold on these metrics, to predict poor outcomes. In this way, these metrics serve as a proxy. In our work, we formulated the predictions to use all available information at a time to make the best possible prediction, so limiting to a single proxy like GPA would only weaken the planner’s prediction and our insights would hold even more strongly.

If the planner’s objective is different than preventing poor outcomes, e.g., if they instead want to maximize the average GPA, then we agree with the reviewer that our framework does not easily map to this setting and indeed this is an entirely different set of questions that would require defining different objectives and problem formulations around, e.g., the effect of allocations.

In our work we focus on the prevention of poor outcome problems as that also is well-studied and well-motivated. We agree however that there may be similar insights that might hold in this continuing setting with different objectives and believe this too could be a promising area for exploration.

Re. W3 (Cont.): … resource allocation problems often involve various constraints beyond following the ranks among individuals. A discussion … would add to the completeness of the paper.

We also agree with the reviewer that there are ways to enrich the model further, such as by considering various constraints beyond just the ranks of the individuals. One example would be to introduce welfare weights among the individuals, allowing the policymaker to prioritize one individual over another, even if they have the same failure probabilities. We could also consider other constraints: for instance, in the context of over-time allocation, there may be barriers to concentrating expenditures around the same time point. It is straightforward to adapt our results to some of these constraints, e.g., adding welfare weights, whereas others ought to be areas for future exploration. As the reviewers point out, since our insights hold even in this simplified version of the model, additional constraints may make the tradeoffs we highlight here even more pronounced, though this requires deeper investigation. We have updated our discussion section to provide a more extensive discussion around these and other promising directions highlighted by the reviewer.

We thank the reviewer for their detailed feedback and insightful questions. We are pleased to read the reviewer’s appreciation about the novelty of the questions around prediction and downstream decision performance, as well as the broad applicability of the insights.

Below, we first address the reviewer’s questions and then outline other improvements made to the paper in response to the feedback.

Re. Q1: What are the connections, if any, between the measure of inequality [in Section 4] and the variance of individual failure probabilities as adopted in Section 3?

We are grateful to the reviewer for this question, which highlights a tight relationship that exists between our formulation of inequality and the variance. We were intrigued by this question and spent quite a bit of time thinking about this connection. In the updated version of the paper, we provide a precise characterization of the connection between our notions of inequality in the new Proposition E.10. Specifically, we present a tight lower bound for the variance in terms of $G$ and demonstrate that this lower bound decreases with $G$. In other words, a low value of $G$, which corresponds to high inequality, guarantees a high variance. Therefore, we could also present a slightly weaker version of Theorem 3.1 in terms of $G$ instead of $\text{Var}^t[p]$. We thank the reviewer again and believe these new observations have enriched our paper!

Re. Q2: … are all individuals assumed to require the same budget? … will assigning different budgets to different individuals affect the presented results?

Yes, this is correct. Intervening on any individual incurs a unit cost. In our results, we aimed to avoid imposing additional structure on the intervention costs to highlight that these counterintuitive insights arise even in such simple settings. Also, some generalizations of the cost structure may already be implicitly captured in a version of our problem. For example, if it costs $c(p)$ to intervene on an individual with a failure probability of p, as long as $u^t(p)/c(p)$ remains monotone increasing in $p$, we can still use predictions of $p$ to optimally rank and allocate. However, when monotonicity is broken, we can no longer make simple arguments about the optimal ranking. We believe these are promising directions for follow-up work from the research community.

We are heartened to read the reviewer’s summary of our paper and their perspective about its potential feedback!

Re. ... there are numerous potential directions that can build upon this work. For example, … one can imagine similar characterizations for when information gain may hurt when applying interventions in non-welfare maximizing ways.

We thank the reviewer for highlighting this excellent potential avenue for future research. We agree that the tradeoffs between acting early and waiting to reduce uncertainty extend beyond our utilitarian framework. Singh et al. provide the right framework for considering uncertainty in fairness-sensitive settings, and we believe our dynamic model can be extended in this direction. We appreciate this suggestion and have included it into our updated discussion.

Re. … the independence in Assumption 4.2 and line 102 should be discussed more. In particular, imagine the mechanism designer is potentially intervening on a pool of students.

We thank the reviewer for this insightful suggestion. In our framework, we avoid imposing additional structure to the problem by assuming independence of observations. However, we fully acknowledge that these assumptions may not hold in problems with additional structure, such as the example provided by the reviewer. Specifically, we rely on two key assumptions: (1) failure events are independent, which does not apply in scenarios where students share the same teacher, for instance; and (2) intervention effects are independent, meaning there are no spillover effects. We appreciate the reviewer highlighting these points and have clarified the implications of these assumptions in the updated manuscript. We will discuss Assumption 4.2 in the following in response to another question from the reviewer.

Re. … assumption 4.4 can also be discussed in more detail. … perhaps a note in the appendix about what kind of utilities this can capture, or some common examples, may be useful.

We thank the reviewer for this excellent suggestion! We agree that including additional examples illustrating $(\lambda_1, \lambda_2)$-decaying utilities would improve the paper's clarity. Therefore, we added a few more examples, such as when the treatment is partially effective, under a new Proposition E.11, and have referenced this proposition in the main text. We believe these additions improve the clarity of our work and appreciate the reviewer’s valuable input!

Re. How should I think about $\gamma$?

We thank the reviewer for the clarifying questions. The introduction of $\gamma$ in the observation model was primarily to simplify certain proofs without explicitly imposing Lipschitz continuity or bounding the curvature of $\tilde{p}(\cdot)$. So, it is more of a proof artifact than a fundamental aspect of the model. That being said, in most proofs, a large gamma implies that individuals with small $p$ may have highly distinct observation probabilities, making them easier to distinguish, while individuals with large $p$ tend to have more similar observation probabilities, making them harder to differentiate. This often encourages making additional observations to better identify individuals in need. However, we emphasize that this interpretation is more of an intuitive explanation rather than a formal claim, as $\gamma$ is mainly a technical construct.

Re. minor comments

We fixed the typo and cited the significant positive effect observed from allocating housing vouchers to homeless families in line 269. We thank the reviewer for these suggestions!