The Hidden Cost of Waiting for Accurate Predictions
Authors: Ali Shirali
Ariel D. Procaccia
Rediet Abebe
Venue: ICLR 2025 Oral (2025)
Keywords: Algorithmic Decision Making
Prediction
Resource Allocation
Social Welfare
Limits of Prediction
Primary area: alignment, fairness, safety, privacy, and societal considerations

Abstract: Algorithmic predictions are increasingly informing societal resource allocations by identifying individuals for targeting. Policymakers often build these systems with the assumption that by gathering more observations on individuals, they can improve predictive accuracy and, consequently, allocation efficiency. An overlooked yet consequential aspect of prediction-driven allocations is that of timing. The planner has to trade off relying on earlier and potentially noisier predictions to intervene before individuals experience undesirable outcomes, or they may wait to gather more observations to make more precise allocations. We examine this tension using a simple mathematical model, where the planner collects observations on individuals to improve predictions over time. We analyze both the ranking induced by these predictions and optimal resource allocation. We show that though individual prediction accuracy improves over time, counter-intuitively, the average ranking loss can worsen. As a result, the planner's ability to improve social welfare can decline. We identify inequality as a driving factor behind this phenomenon. Our findings provide a nuanced perspective and challenge the conventional wisdom that it is preferable to wait for more accurate predictions to ensure the most efficient allocations.

Published as a conference paper at ICLR 2025
THE HIDDEN COST OF WAITING FOR ACCURATE PREDICTIONS
Ali Shirali"!, Ariel Procaccia 12, and Rediet Abebe
University of California, Berkeley Harvard University
ELLIS Institute, Max Planck Institute for Intelligent Systems, & Tübingen Al Center
ABSTRACT
Algorithmic predictions are increasingly informing societal resource allocations by identifying individuals for targeting. Policymakers often build these systems with the assumption that by gathering more observations on individuals, they improve predictive accuracy and, consequently, allocation efficiency. An overlooked yet consequential aspect of prediction- -driven allocations is that of timing. The planner has trade off relying earlier and potentially noisier predictions to intervene before individuals experience undesirable outcomes, or they may wait gather more observations make more precise allocations. We examine this tension using simple mathematical model, where the planner collects observations on individuals to improve predictions over time. We analyze both the ranking induced by these predictions and optimal resource allocation. We show that though individual prediction accuracy improves over time, counter-intuitivel the average ranking loss can worsen. As result, the planner's ' ability to improve social welfare can decline. We identify inequality as driving factor behind this phenomenon. Our findings provide nuanced perspective and challenge the conventional wisdom that it is preferable to wait for more accurate predictions to ensure the most efficient allocations.
INTRODUCTION
Algorithmic predictions are playing central role in societal resource allocation. Policymakers and organizations are increasingly turning to algorithmically-divv scarce in order to target resources with greater precision (Eubanks, 2018; Kleinberg al., 2015; Kube et al., 2023; Mashiat et al., 2024; Perdomo et al., 2023; Toros & Flaming, 2018). Underpinning this growing reliance on predictions is the assumption that by gathering more observations about individuals over time, we can improve prediction accuracy and, consequently, allocation efficiency.
systems in contexts where resources
In practice, decisions around the timing of predictions and how they inform allocations reveal consequential trade-offs that the planner must navigate. On the one hand, the planner may wait collect extensive data to refine their predictions before intervening. On the other hand, they can intervene early by relying on coarser data and noisier predictions. The potential advantage of the latter that, in a fxed-horizon setting where the planner wants to prevent individuals from experiencing undesirable outcomes, the "window of opportunity" for this undesirable outcome to be realized closes. Furthermore, the underlying population changes with time, as those at greatest risk of experiencing such outcomes are more likely to "fail out" of the population early if they do not receive resources (Bierman, 2002; Abebe et al., 2020; Salganik et al., 2020). These factors pull in different directions, and it is not immediately apparent which factor dominates.
We examine this tension using a simple, versatile model where the planner predicts and intervenes on population over time. Modeling generic resource allocation problem, we assume the planner has a fixed budget of resources to prevent individuals from experiencing undesirable outcomes, such eviction, job loss, poor health, dropping of school (Mashiat al., 2024; Perdomo al.,
"Tii work was conducted during a visit at Harvard University.
A Alphabetiaal order.

---

Published as a conference paper at ICLR 2025
2023; Zezulka & Genin, 2024; Chan et al., 2012; Subbhuraam, 2021; Faria al., 2017; Mac Iver et al., 2019). At each time step, the planner collects observations about individuals to improve their estimate of their underlying failure probability. The planner then uses the rankings induced by these estimates to allocate resources. Specifically, we ask:
1. Ranking: How does the ranking loss change as the planner collects more data, but some individuals fail out of the population?
2. Allocation: For given instance of this problem, what is the optimal time to allocate resources? When is early intervention justified?
We present our results for two allocation problems: First, in a stylized setting, the planner is tasked with allocating all resources at once but can choose when to do so. We then use this as a building block to study the case where the planner can allocate resources over time. For both the ranking and allocation problems, we examine the role of inequality- measured by the variance in the underlying failure probabilities- and surface it as a driving factor behind the optimal solutions.
We show that although individual prediction accuracy improves with more observations, counter- intuitively, this does not translate into improvements in the average ranking loss. To observe this, decompose ranking loss into two counteracting effects: one due to improvements in prediction from additional observations and the second due to the change in population as individuals fail out of the active pool. We identify fundamental statistics that drive these two effects. We show that the change-ing in- inopullation effect negatively impacts ranking performance and that this effect grows at least proportionally the variance in the failure probabilities.
We then address both instantiations of the resource allocation problem. For the setting where the planner must allocate all resources simultaneously, derive an upper bound on the optimal allocation time. We explicitly identify the roles of inequality and budget in expediting or deferring the optimal allocation time. We show that with high inequality or a large budget, allocating resources earlier results in greater social welfare. For the setting where the planner can allocate the budget over time, we design provably optimal algorithm with a running time independent of the number of individuals. Using this algorithm, we then demonstrate that the optimal solution can concentrate the allocation around any time-point t, and it behaves consistently with our findings on one-time allocation.
Our results provide a nuanced perspective on the role of timing in prediction-driven allocations. In settings where the planner observes and intervenes on a population over time, they must balance the desire for more accurate predictions with the necessity for timely interventions. In the presence of significant inequality within the population, more accurate predictions do not necessarily lead to better ranking or improved allocations, providing a potential justification for early resource allocation.
For an extensive discussion on the related work and adjacent problem settings, refer to Appendix B.
2 MODEL AND PRELIMINARIES
In this section, we first introduce the notations necessary to present the basics of our model. We provide further notation, needed, throughout the paper and summarize the key notations in Table 1.
We model the population over which the planner acts We assume there is an initial population of N individuals and consider a finite horizon setting where i E [1, Each individual i has some failure probability p. E [o, 1]. which captures their likelihood of failing out of the population between time steps. In the absence of intervention, this failure probability remains the same across time, and failure events of different individuals are independent." 2 Once an individual fails, they are no longer in the active pool of the population. We denote this active pool at time t by A+.
Prediction and ranking. At each time step I, the planner observes a signal of from each active individual i E A These signals are analogous to observing loan or rental payments in housing and credit scoring, exam scores in education, and medical check-ups and tests in clinical settings. In our working model, these signals are drawn independently from a Bernoulli process
of ~ Ber(
'Though we primarily consider the finite horizon setting, the key insights hold in the infinite horizon setting. If the problem has further structure, such as when students share teacher, this assumption may not hold.
2

---

Published as a conference paper at ICLR 2025
where P3 is a function of p:- We drop the explicit dependence on P; from p(ps) for ease of notation.
We assume that p is an increasing function: The more likely an individual is to fail, the more likely we to observe signals indicating this possibility. An individual i will leave p./p, positive observations in expectation. Thus, a larger p results in more observations from individuals before they fail out.
The planner is interested in the predictions as means rank and prioritize individuals. Given observations drawn from Eq. (1) and a prior over the failure probability, we will examine how the ranking risk of the Bayes' optimal ranking, measured on the active population, changes over time. This is the subject of Section 3.
The planner has budget B of resources, such housing vouchers, unemployment insurance, and preventive health screenings, to allocate to individuals in the active pool. We assume that assigning resource an individual has fixed unit cost. We consider two common instantiations of allocation problems: We first study the one-time allocation problem, where the planner is tasked with finding the optimal time t to allocate B. We then consider an over-time allocation problem, where the planner aims to find the optimal distribution of the budget across time.
Targeting and allocation.
To measure the efficiency of allocations, we define by u' (p) the expected utility the planner gets from intervening on an individual with failure probability p. The planner's primary objective is to maximize the utility over all treated individuals when there is no spillover effect. We assume that u' u'(p) is non-increasing in and non-decreasing in p. which captures the idea that the planner does not get more utility from intervening on the same individual later or from intervening on a better-off individual. We further assume that the utility function is concave in p. reflecting diminishing returns. Without loss of generality, we let u' (0) = =..
The utility framework we define above allows for significant generality. In particular, note that for any individual i, the utility the planner gets from intervening on i may depend on i's unobserved characteristics, but this does not affect results. Further, we make basic assumptions on ut, allowing us to prove results in a general setting. To build intuition, at various points, we use a specific example of utilities, defined below.
Example 2.1 (Fully effective treatment). Suppose that once individual receives resource, they do not fail out of the population at subsequent time steps. The planner's 's utility then equals
u' (p) = 1- (1-p)T-+,
(2)
ie., allocating to individual has the same expected utility as the probability that this individual would have failed by time T without this intervention.
For the allocation problems consider, the planner uses the ranking induced by the predicted failure rates. We find that these rankings, in and of themselves, are interesting objects of study as they reveal complex trade-offs over time.
3 RANKING OVER TIME
In this section, we exclusively focus on ranking, which will form the basis for our main results on allocation presented in subsequent sections. We present our main ranking-related result separately both because it helps build intuition for the delicate tradcoff' a planner needs to consider for the allocation problems, but also because shows that these tradeoff's are present in other interventions that leverage risk-based rankings.
Informally, we show that even though individual predictions may improve as more observations become available over time, ranking quality can in fact decline. We demonstrate that inequality as defined by the variance in the failure follows: Although individual predictions improve over time. in high inequality settings, individuals with high p (which were easier to distinguish from low p individuals based on coarse information) more likely to drop out carlier, lcaving behind an active population that is harder to rank.
such settings. The intuition is as
Ranking risk. We define ranking quality using ranking risk RR at time t. We consider a common notion of ranking risk based pairwise ranking loss (Mohri, 2018). Given two individuals time t, the pairwise ranking problem predicts which individual has the higher failure probability based on observations up to I.. We assign loss of zero if the prediction is correct and one otherwise.
3

---

Published as a conference paper at ICLR 2025
We denote the number of positive observations from an active individual i up to time t by
Then ranking individuals based on their yf is Bayes optimal in terms of the zero-one pairwise ranking loss. Formally, the zero-one risk of optimal (pairwise) ranking at time t is
Rd (uf < V Pj 2 p.)
(4)
Here, (-( is the probability when we choose two active individuals from A'' independently.
Main result. We now present our main result on the dynamics of the optimal ranking risk. This result relies on certain approximations of the ranking risk, which we will detail later this section. Theorem 3.1. The ranking risk of the optimal ranking at can only improve in the next time step if
Var' [p]
O
aapprox
(5)
B 12)
change-in-popolation effect
gain in observations
where we assume that the inverse of p(-) is (1)-Lipschi,.. and Cappros. which we skip here for clarity of exposition.
The proof presents the exact form of O())
See proof on page 29. The necessary condition stated in Eq. (5) highlights two key insights into when ranking quality decreases over time. First, increases, the left-hand side-which measures the change-in-population effect-iiccreaes, whereas the right-hand side-which measures the gain in decraaiassseeeeesssseee.eeeee Second, as either the mean variance in failure probability increases, it is again harder to satisfy Eq. (5). Combined, these insights highlight that later rankings are only preferred under conditions where inequality and average failure probabilities are low.
We next discuss the main steps towards proving Theorem 3.1.
Approximating ranking risk. To approximate ranking risk, recall observations are drawn from (er Eq. (3) then implies y ~ Binomial(t, p). For analytic tractability, we approximate this with the normal distribution N, with mean I and variance t o², Here, 8² = p.p(11 p). The independence of the draws in Eq. (4) implies
v vl (p.. N(5 pi,
where 2 = 0, + +07- Denoting the cumulative distribution function of the standard normal distribution with (-), it is then straightforward to simplify R² as
|0 - V1]
R² ~ E
x
(6)
oij
Note that the dependence of Rs on appears in two places: inside ((-), which captures the effect of gathering more observations over time, and E which models change-in- -pooullationno effect.
Decomposing step-change in ranking risk. We denote the change Rd in one time step by AR' = = R Using Eq. (6),
decompose AR into two parts:
The change in & after one step, which we approximate by taking the derivative with respect to
The change of IE,, after one step. To compute this, denote the distribution in failure probability of the population A by pt. Since active individual at with failure probability p survives until t + with probability of 1 p, we can write
pt+ (p) 1 P 4
P'))),
where n² = E'pp]. Using this, compute the expected change in population follows:
E [ - p.) (1 p3) (+)
(1 - 12)2
Refer to Proposition E.4 for proof.
4

---

Published as a conference paper at ICLR 2025
Putting these two parts together, and approximating + with ranking risk after one time step
1 exp(-x² 1222/2/ /2), V2x
the change in
AR'
exp
(0) Pi)² 20
Tij Pr
P1) - ps) (1
p. Pi
}
(8)
V2Tt
Pj
20.
Intuitively, we can think of the exponential multiplier as a kernel enforcing similarity of pr and pj. Such filter pushes ARf towards positive values, which means that the filter becomes stricter for larger i, the effect of losing vulnerable individuals dominates the gain from collecting more observations
the remaining population. We make a mild assumption here that there exists constant a E (0, 1) bounded away from zero such that plugging exp(- -x²) zs 1 (exp(->** 2 a} into Eq. (8) does not change the value of AR'. Then Capprox. := In(1n///nn (1/a). The rest of the proof of Theorem 3.1 is straightforward, which we leave in the appendix.
4 ONE-TIME ALLOCATION
In the previous section, examined how ranking metrics evolve over time. In this section, explore how these dynamics impact the allocation problem driven by the ranking.
The allocation policy varies depending on when resources become available and any spending restrictions in place, We assume fixed budget for a specific population and explore two variations: In the general case, the budget can be allocated flexibly over time. For example, funding for a student cohort may be distributed across multiple years before graduation. In contrast, in the special case, the budget must be spent all at once, often due to administrative constraints, and the question becomes: when is the optimal time to allocate it? For example, cancer screenings may need to occur at certain age, or school empowerment programs may be restricted to a specific grade due to the high cost of developing materials and training staff for multiple grades.
We first focus on the one-time allocation problem. We do so not only because it may represent a real-world constrained allocation problem but also because it provides valuable intuition for the more general variation of the problem. Importantly, strong theoretical results from this analysis offer key insights into the timing. budget, and inequality dynamics that form the core of our contribution. Informally, our main result states:
Theorem (Informal). For the one-time allocation problem, there exists t" that is fraction of the horizon T, such that the planner can best optimize utility by allocating B before t This t" decreases, favoring earlier allocations, when inequality in the failure probabilities is high the budget is large.
To explicitly state this theorem, we need introduce additional terminology, concepts, and definitions. Formally, given a budget B, at chosen time f, the planner ranks active individuals A in descending order of their number of positive observations y", and allocates resources the first of them."
Denote the predicted ranking by injection r" AA' + [N']. where individual with r'(i) = 1 is the most eligible one. The total utility of allocating a budget at time is given by
W
u u'(p)) ((r((t) s B}.
Proving results requires establishing upper bound t* such that W can increase over the next steps only if t is less than t*. In other words, deferring allocation only justifiable if we have not reached this critical time. The results in this section show an intricate relationship between the timing of prediction/allocation with the inequality of the initial population and scarcity of resources.
Before presenting results in full generality, we first consider the fully effective treatment setting, where the utility function follows Eq. (2). Although many real-world treatments may not be fully effective, many are, in fact, sufficiently effective for this special case serve useful approximation for understanding their dynamics. For instance, consider housing vouchers or dropout prevention programs, which have been found to be very e Due to its significance and analytical tractability, we next present specific results for this case.
+ Prooposition E.4 implies this the Bayes optimal ranking our setting.
For instance, Gubits et al. (2016) found "significant positive impacts in families offered a voucher, and these impacts extended heyond housing stability."
5

---

Published as a conference paper at ICLR 2025
4.1 THE FULLY EFFECTIVE TREATMENT SETTING
Recall from Example 2.1 that the utility function in the case of fully effective treatments follows up()) 1 (1 11-p) p)=-r To state our results, we also need define a measure of inequality:
Definition 4.1 (G-decaying distribution). We say distribution P over is G-decaying for G' 2 0 if
P(p)
dp
dp 0.
Intuitively, G bounds the rate at which the distribution decreases. Smaller values of G correspond to greater inequality (see Proposition 10 for the relationship between G and Var(p)). For example, if P(p) x (1 p)g the probability density function of a Beta(1. 3) distribution-the P is (B (8-1) -eeccyying Under this definition, the highest level of inequality in the population corresponds to the uniform distribution, which is O-decaying.
Recall that at each time step i. the planner observes of Ber(f) from each active individual. To simplify notation, we assume the following concave observation model:
Assumption 4.2 (Observation model). We assume observations from an individual with failure
probability p are independently drawn from (er(ō), where P = - (1 - p1" and y > 1.
Under these assumptions, we present necessary condition for when waiting for additional observa- tions can improve the allocation efficiency of fully effective treatments:
Theorem 4.3 (Conditions for fully effective treatment), Suppose treatments are fully effective and the initial distribution over failure probabilities is G-decaying. The overall utility can improve after time only if < 1",, where
T +
G
+1) (1++1) In
N 1 B 11)
t =
+
2
4
4
See proof on page 29.
This theorem implies that we rarely need to go beyond the halfway point of the time horizon to optimally allocate resources, and that this t* can be even smaller when have high levels of inequality (corresponding to smaller G) or larger budget. We further illustrate the intuition behind this theorem with example in simple setting in Appendix C. Combined, these results indicate that high levels of inequality and scarcity of resources play an important and consistent role in determining optimal allocation time-an an insight we find carries over more general settings.
4.2 THE GENERAL CLASS OF UTILITY SETTING
We define the class of A2) deecaying utility functions below. The fully effective treatment setting corresponds to a (1, de-dcyyyn utility. Refer Proposition E1 for the proof and other examples. Definition 4.4 (()), A2) decaying utility). We say utility function u' (p) is (A1, decayyng for positive λ and Xa if at every and p.
n' (p) AP
(p) =
(bounded decrease over time)
1 1-p
A2 u (p) ( (u))(0).
(x <
(bounded increase with p)
1-p p
When there is no finite Ag such that the second bound holds, we say that the utility is x -e-decayn
Our definition of (A1, dec-ying utility functions contains the essential elements to describe the utility function's behavior: a higher λ₁ indicates a stronger decrease over time, while a higher X2 signifies a faster increase with p. Our main result of this section states:
Theorem 4.5 (Conditions for general class of utilities). For the general class of utilities, the overall utility can improve after time t only if < t" = (7 + In( ) or the following conditions hold:
WW make the concavity assumption for case of presentation, but discuss in the appendix, weaker version of result holds for any Lipschitz concave ğ with bounded curvature.

---

Published as a conference paper at ICLR 2025
1. When the utility function is (A1, 22) deeayyng with A 2 A2.
t-
(u)+)(()) Z
A2
1+ (2 + + GG 2--
2. When the utility function (x)--decaying.
t 1- 1"
(u*))((0) 2 A1
+1+
See proof on page 30.
This theorem shows that for wide-range of settings, the optimal allocation can happen early: Our assumptions about the concavity of the utility function and its zero value at = 0 imply that (1)) is decreasing function of t. Conversely, regardless of whether the utility is (A1, 22)- decaying or just -i-decaying, the right-hand side of the bounds increases with t. Determining the timing of the optimal allocation is intertwined with the level of inequality and the budget. In particular, consistent with the previous section, higher inequality and larger budget favor earlier allocations.
5 OVER-TIME ALLOCATION
The one-time allocation problem presented in the previous section helps as a building block for more general setting, which we now consider. We study the problem of allocating fixed budget over time to maximize total utility. First, we discuss the complexity of the problem under a naive optimization approach. Then, we characterize the optimal solution and present a method to find it regardless of the number of individuals. Through eemt-synthetic experiments, we demonstrate that the optimal allocation follows a similar intuition to one-time allocation, where higher incquality larger budget shifts the optimal allocation toward carlier times.
5.1 CHARACTERIZING THE OPTIMAL OVER-TIME ALLOCATION
We begin by describing Markov decision process (MDP) that governs the allocation problem. Let Al, denote the set of active individuals at time who have & positive observations, i.c., y k. We define the state at by No |A4s l. for & S I. An allocation policy specifies the individuals treat from A at each state. The policy, together with the current state and the prior distribution over p, is sufficient determine the distribution of the next state.
A naive approach to finding the optimal policy for the described MDP is as follows. Since individuals with higher y¹ yield a higher expected utility.? 7 the optimal allocation every time should treat those with the highest y'. Given budget of B, we can specify rollout of such a policy by the budget spent at each time step, resulting in (f+1) possibilities. In the case of many agents, and thus a large B, the MDP dynamic becomes almost deterministic, and the optimal policy converges to a single fixed rollout. However, iterating over all (+=)) rollouts to find the optimal policy is computationally infeasible. Next, we find a characterization of the optimal solution that significantly cuts down search space.
Theorem 5.1 (Optimal over-time allocation). The optimal over-time allocation the limit of many individuals follows a specific puttern: For non-decreusing sequence q [T] 1, 1..., T}, there exists a time step & E (T] such that,
Ar t + f, everyone with y 2 g(t) will be treated. At the next step, q(t + 1) E {q(t), g(t) + +1}.
Ai l i, everyone with 3¹ q(() and some with y² = =q({) will be treated. At the next step, q(t + 1) {q(t) + 1, q(t) + 2}.
See proof on page 33.
This theorem narrows down the search space of possible policies to three parameters: i, 7(+), and what portion of A (tt) to treat. In particular, our search space no longer depends on the budget B or the number of individuals.
Refer to Lemma E.5 for formal proof.
7

---

Published as a conference paper at ICLR 2025
5.2 AN ALGORITHM TO FIND THE OPTIMAL SOLUTION
In this section, we present an algorithm that uses Theorem 5, to find the optimal policy, ensuring that its runtime does not scale with the number of individuals the budget size. We build the algorithm to do so in pieces. First, we show that we can iterate over the joint space of unspecified parameters in O 22"-1) steps:
Lemma 5.2. By specifying the time step & [T), the initial value of the sequence q from the set of 1,2), and a binary sequence of length T - 1, we can iterate over the joint space of unknown parameters in Theorem 5.1 O(TS. 2T steps.
See proof page 34.
This lemma utilizes the structure of sequence g(-) in Theorem 5.1 and reduces it to binary sequence given i. also utilizes linear structure of total utility to determine how many people to treat from A (f)" These are the first steps Algorithm 1.
At the heart of Lemma 5.2 is Algorithm 2 that simulates trajectory. This algorithm uses backup formula that updates N based on N and |- Algorithm 2 also requires calculating expectation with respect to p ~ (- y' = k). In our simulation, this posterior has a closed form. However, in general, since is bounded scalar, the posterior calculation can be well-approximated by constant number operations.
Given efficient way to iterate over the search space, show that Algorithm can find the optimal policy without increasing the run time:
Theorem 5.3. Algorithum finds the optimal over-time allocation in O(T -2T) steps.
See proof on page 34.
In real-world settings, time steps are typically on the scale of month or a year. Therefore, T is usually small constant and the complexity of Algorithm I as stated in Theorem 5.3 is manageable. Compared to the naive iteration over (++1) possible trajectories, Algorithm I's complexity is significantly reduced by dropping the dependency on the number of individuals and B. Powered by this algorithm, we next visualize the optimal over-time allocation in semi-synthetic settings.
Algorithm 1 Optimal over-time allocation
1: Uopt <-
2: for i = 1 to T. and g(-) valid sequences (as constructed in Lemma 5.2) do
Simulate as Af,
((E) are all treated:
3:
{Nr ((F)
TT. SIMULATETRAI(] (Ng, N)).(.))
4:
Emax + 1(((1) 03 .N + + Nt q(()
b maximum expenditure
Simulate the difference as if no one in A² a(t) was treated:
5:
{AN: q +- SIMULATETRAI(i, {0. 0, No (()) .................... 0}, + 11(() = 0))
6:
AE
No. q(t)
Σt ET AN
decrease from the max. expenditure
9(1)
Find what proportion of A' to treat:
7:
0 Emas B
proportion of A 9())
to be left untreated
8:
if p 1 or O then continue to the next possible v(-) end if
Calculate the total utility:
9:
for t T' and le q(t) do UÉ + (PPP()E=))) [u'(p) end for
10:
U U (1
m(t)) ((o U Enjo(N' (ce) + AANT ( U + ( 0) N
11:
if U > Uopt then Uopt U, Copt + g, topt end if
check for optimality
12: end for
13: return Uopt: 9opt: fopt
8

---

Published as a conference paper at ICLR 2025
5.3 VISUALIZING THE OPTIMAL SOLUTION
Algorithm allows us to efficiently find the optimal over-time allocation. Using this algorithm, we next examine the effect of inequality, encoded in the prior distribution of p, and the budget size on the optimal over-time allocation.
Our goal is demonstrate that even in the simplest non-contrived settings, the tradeoff between gaining more observations and losing vulnerable individuals strongly exists. Therefore, we make minimal assumptions about the model: Suppose the treatments are fully effective, the observation model is P p, and the prior over failure probabilities follows Beta(a, 8). The beta distribution is common and expressive choice for modeling priors over [0, 1] bo-udndded random variables. is also the conjugate prior for the binomial distribution, which allows us to write the posterior distribution over failure probability in closed form: (. y² = k) = Beta(a + k. + k).
Data and parameters estimation. To make our simulations more realistic, choose the ini- tial distribution to reflect real-world data, In particular, we use National Education Longitudinal Study (NELS) of 1988, longitudinal study with follow-ups four points throughout the students' education." 8 this data, failure corresponds to student dropout and is recorded.
We estimate the beta distribution parameters in the following manner. Let mo and mi be the proportion of the initial pool of individuals who failed right before the first and second steps, respectively. Assuming there has been intervention at the first step, it follows from the central limit theorem that mig - x+3 and m - [a+))aa+++1 a fast rate of O(1/VN). By solving for a and B, we can accurately estimate the initial distribution as a Beta distribution. Our estimation gives a 0.028 and 0.35 for the case of NELS data. The mean of the estimated distribution
(a++1)
also aligns with the NELS-provide estimation of dropout probability, with both methods predicting a dropout rate of around 7%.
Results. We first study the effect of budget size. Theorem 4.3 suggests that in case of one-time allocation, the optimal allocation time shifts with In (n()). )) Fig. suggests that similar trend holds true the case of over-time allocation: larger budget favors earlier allocations."
109
of spent
butget
(a)
5%
8 N 10% (b)
(c)
Ø N 20%
Figure 1: Optimal over-time allocation for three sizes of the budget and fixed prior estimated from NELS data. The orange curve depicts the optimal q(-) and the filled circle corresponds to L
We next extend our analysis beyond the NELS data distribution to study the effect of initial distribution, particularly inequality, on the optimal allocation. Theorem 4.3 suggests that greater inequality can further favor earlier allocation. To simulate this effect, we fix N' 10% and consider three priors with differing tail decay. Fig. indicates that as the prior approaches a uniform distribution, corresponding to maximum inequality in terms of our definition of G-decaying distributions, optimal allocation significantly favors earlier times.
1
These visualizations confirm that a similar intuition as the one-time allocation setting also appears in the over-time allocation problem.
*https: puttps://ncee ://ces....//////// ed. htt..oo//suveess//eeeeee///////e
Coode is available at https: / thub. hatam//alliiaaliiiiaaaaa htt.a//wcooo...aaaaaaaaoaooooooa -ccoo cos...

---

Published as a conference paper at ICLR 2025
Initaal distribution
intial distribution
Intial distributton
budget sesttttttt....
%o of budgetspenn spent
% budget
11
919)
65
(a) Beta(a 0.4, 8
(b) Beta(a 0.2, 8 1)
(c) Beta(a 0.1,
curve depicts the optimal q(-) and the filled circle corresponds to t N = 10%. The orange
Figure 2: Optimal over-time allocation for three different priors and a fixed
DISCUSSION
Our work contributes timing dimension emerging body of research evaluating prediction- driven allocation. Predictive systems are introduced with the promise minimizing waste and increasing efficiency. This existing predisposition, amplified further by the traditional focus maximizing predictive accuracy, encourages practices that favor waiting to collect more information over acting early with noisier signals. Our study presents simple model that challenges this practice.
Our work opens numerous lines of inquiry. For instance, we assume the planner has fixed budget B, corresponding fixed unit-cost intervention, that they can allocate all once or over time. There are various natural variations worth exploring. For instance, we could consider heterogeneity in cost across time or different P; values. In the same spirit as Perdomo (2024), we can also consider trading off this B with other interventions or parameters in the problem. We also think the tradeoffs between acting early and waiting reduce uncertainty extend beyond our welfare-maximizing framework. For instance, future work could adapt our dynamic model to fairness-focused frameworks for studying uncertainty, such as those developed by Singh et (2021), and explore whether information gains consistently lead to improved outcomes.
make generic assumptions about the failure probabilities and collection of observations. settings motivating our study, the failure probabilities change time. favoring increasing incquality in the absence of interventions. Likewise collecting observations for vulnerable individuals may be more costly, contain less signal, may otherwise be undesirable (Monteiro Paes al., 2022). Another general assumption we made that, while individuals have heterogeneous values of p. we do not account for variations in their initial conditions "starting points." Enriching the model study to include such insights would only further justify early interventions in the presence of high inequality, though it would be interesting to examine the extent which does so. We should also point out that we consider the allocation problem in an unconstrained setting to highlight the generality of the tradeoffs. However, practical constraints can further limit the optimal allocation, in one way or another.
Our work introduces a potential lens through which to examine tradeoffs incurred by waiting to improve prediction accuracy. Our results, on their own, do not endorse early or late allocations for any specific setting. Each policy problem should be examined empirically, and policymakers must consider various community, policy, and practical considerations. Indeed, targeting as effective means of improving welfare-wlle which has fueled the use of predictive systems-a -is itself, an actively debated policy concept (Shirali et al., 2024a). Nonetheless, believe that the machine learning community can contribute to discussions around how to best evaluate predictive systems in such policy settings.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
We thank Jackie Baek, Joshua Blumenstock, Kate Donahue, Avi Feller, Moritz Hardt, Michael I. Jordan, and Jiduan Wu for their generous feedback and discussions. Abebe was partially supported by the Andrew Carnegie Fellowship. Procaccia was partially supported by the National Science Foundation under grants IIS-2147187 and IIS- 2229881; by the Office of Naval Research under grants N00014-24-1-2704 and N00014-25-1-2153;
and by grant from the Cooperative Al Foundation.
REFERENCES
Rediet Abebe, Jon Kleinberg, and S Matthew Weinberg. Subsidy allocations the presence of income shocks. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, pp. 7032-7039, 2020.
Krishna Acharya, Eshwar Ram Arunachaleswaran, Sampath Kannan, Aaron Roth, and Juba Ziani. Wealth dynamics over generations: Analysis and interventions. In 2023 IEEE Conference on Secure and Trustworthy Machine Learning (SaTMI.), pp. 42-57. IEFE, 2023.
Shipra Agrawal and Nikhil Devanur. Linear contextual bandits with knapsacks. Advances in Neural Information Processing Systems, 29, 2016.
Emily Aiken, Suzanne Bellue, Dean Karlan, Chris Udry, and Joshua Blumenstock. Machine learning and phone data can improve targeting of humanitarian aid. Nature, 603(7903):864-870, 2022.
Susan Athey. Beyond prediction: Using big data for policy problems. Science, 355(6324):483-885, 2017.
Susan Athey and Stefan Wager. Policy learning with observational data. Econometrica, 89(1): 133-161, 2021.
Mohammad Javad Azizi, Phebe Vayanos, Bryan Wilder, Eric Rice, and Milind Tambe. Designing fair, efficient, and interpretable policies for prioritizing homeless youth for housing resources. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 15th International Conference, CPAIOR 2018, Delft, The Netherlands, June 26-29, 2018, Proceedings 15, pp. 35-51. Springer, 2018.
Chelsea Barabas, Madars Virza, Karthik Dinakar. Joichi Ito, and Jonathan Zittrain. Interventions over predictions: Reframing the ethical debate for actuarial risk assessment. In Proceedings of the Ist ACM Conference on Fairness, Accountability, and Transparency, pp. 62-76, 2018.
Debopam Bhattacharya and Pascaline Dupas. Inferring welfare maximizing treatment assignment under budget constraints. Journal of Econometrics. 167(1):168-196 2012.
Karen Bierman. The implementation of the fast track program: An example of large-scale prevention science efficacy trial. Journal of Abnormal Child Psychology, 30:1-17, 2002.
Niclas Boehmer, Yash Nair, Sanket Shah, Lucas Janson, Aparna Taneja, and Milind Tambe. Eval- uating the effectiveness of index-based treatment allocation. arXiv preprint arXiv:240..11711 2024.
Carri W Chan, Vivek F Farias, Nicholas Bambos, and Gabriel Escobar. Optimizing intensive care unit discharge decisions with patient readmissions. Operations research, 60(6):
2012.
Raj Chetty, Nathaniel Hendren, and Lawrence F Katz. The effects of exposure to better neighborhoods on children: New evidence from the moving opportunity experiment. American Economic Review, 106(4):855-99)) 2016.
Xavier de Souza Briggs, Susan Popkin, and John Goering. Moving to opportunity: The story of an American experiment to fight ghetto poverty. Oxford University Press, 2010.
Ellora Derenoncourt. Can you move to opportunity? Evidence from the great migration. American Economic Review, 112(2)369-400) 2022.
11

---

Published as a conference paper at ICLR 2025
Adam N Elmachtoub and Paul Grigas. Smart "predict, then optimize". Management Science, 68(1): 26, 2022.
Adam Elmachtoub, Jason Cheuk Nam Liang, and Ryan McNellis. Decision trees for decision- making under the predict-then-opimizz framework. In International Conference on Machine Learning, pp. 2858-2867. PMLR, 2020.
Virginia Eubanks. Automating inequality: How high-tech tools profile, police, and punish the poor. St. Martin's Press, 2018.
Ann-Marie Faria, Nicholas Sorensen, Jessica Heppen, Jill Bowdon, Suzanne Taylor, Ryan Fisner, and Shandu Foster. Getting students track for graduation: Impacts of the early warning intervention and monitoring system after one year. Regional Educational Laboratory Midwest, 2017.
Lisa A Gennetian, Lisa Sanbonmatsu, Lawrence F Katz, Jeffrey R Kling, Matthew Sciandra, Jens Ludwig, Greg J Dunean, and Ronald C Kessler. The long-term effects of moving opportunity on youth outcomes. Cityscape, pp. 137-167, 2012.
Daniel Gubits, Marybeth Shinn, Michelle Wood, Stephen Bell, Samuel Dastrup, Claudia Solari, Scott Brown, Debi Mclnnis, Tom McCall, and Utsav Kattel. Family options study: 3-year impacts of housing and services interventions for homeless families. Available at SSRN 3055295, 2016.
Moritz Hardt and Michael P Kim. Is your model predicting the past? In Proceedings of the 3rd ACM Conference on Equity and Access in Algorithmss, Mechanisms, and Optimization, pp. 1-8, 2023.
Hoda Heidari and Jon Kleinberg. Allocating opportunities in dynamic model of intergenera- tional mobility. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pp. 15-25, 2021.
Toru Kitagawa and Aleksey Tetenov. Who should be treated? Empirical welfare maximization methods for treatment choice. Econometrica, 86(2):591-616, 2018.
Jon Kleinberg, Jens Ludwig, Sendhil Mullainathan, and Ziad Obermeyer. Prediction policy problems. American Economic Review, 105(5):491-499 2015
Amanda R Kube, Sanmay Das, and Patrick J Fowler. Fair and efficient allocation of scarce resources based on predicted outcomes: Implications for homeless service delivery. Journal of Artificial Intelligence Research, 11:1219-1255 2023.
Nir Levine, Koby Crammer, and Shie Mannor. Rotting bandits. Advances in neural information processing systems, 30, 2017.
Karen Levy, Kyla E Chasalow, and Sarah Riley. Algorithms and decision-making in the public sector. Annual Review of Law and Social Science, 17:309-334 2021.
Jens Ludwig, Jeffrey Liebman, Jeffrey R Kling, Greg J Dunean, Lawrence Katz, Ronald C Kessler, and Lisa Sanbonmatsu. What can we learn about neighborhood effects from the moving to opportunity experiment? American Journal of Sociology. 114(1):144-188) 2008
Jens Ludwig, Greg Duncan, Lisa Gennetian, Lawrence F Katz, Ronald C Kessler, Jeffrey R Kling, and Lisa Sanbonmatsu. Long-term neighborhood effects low-income families: Evidence from moving to opportunity. American Economic Review, 103(3):226-22) 23122661222222 2013.
Martha Abele Mac Iver, Mare L Stein, Marcia H Davis, Robert W Balfanz, and Joanna Hornig Fox. An efficacy study of ninth-grade early warning indicator intervention. Journal of Research on Educational Effectiveness, 12(3):363-390, 2019.
Tasfia Mashiat, Alex DiChristofano, Patrick J Fowler, and Sanmay Das. Beyond eviction prediction: Leveraging local spatiotemporal public records to inform action. arXiv preprint arXiv:2401. 16440, 2024.
Aditya Mate, Bryan Wilder, Apama Taneja, and Milind Tambe. Improved policy evaluation for randomized trials of algorithmic resource allocation. In International Conference on Machine Learning, pp. 222113... PMLR, 2023.
12

---

Published as a conference paper at ICLR 2025
Mehryar Mohri. Foundations of machine learning, 2018.
Lucas Monteiro Paes, Carol Long, Berk Ustun, and Flavio Calmon. On the epistemic limits of personalized prediction. Advances in Neural Information Processing Systems, 35:1979-1991, 2022.
Ayan Mukhopadhyay and Yevgeniy Vorobeychik. Prioritized allocation of emergency responders based on a continuous- time incident prediction model. In International Conference on Autonomous Agents and gent Systems, 2017.
Ziad Obermeyer and Ezekiel Emanuel. Predicting the future-big data, machine learning, and clinical medicine. The New England journal of medicine, 375(13):1216, 2016.
Juan Carlos Perdomo. The relative value of prediction in algorithmic decision making. In Forty-first International Conference on Machine Learning, 2024.
Juan Carlos Perdomo. Tolani Britton, Moritz Hardt, and Rediet Abebe. Difficult lessons social prediction from Wisconsin public schools. arXiv preprint arXiv:2304.06205, 2023.
Sina Rismanchian and Shayan Doroudi. Four interactions between ai and education: Broadening our perspective on what ai can offer education. In International Conference on Artificial Intelligence in Education, pp. 1-12. Springer, 2023.
Matthew Salganík, Ian Lundberg, Alexander T Kindel, Caitlin Ahearn, Khaled Al-Ghoneim, Abdullah Almaatoug, Drew M Altschul, Jennie E Brand, Nicole Bohme Carnegie, Ryan James Compton, et al. Measuring the predictability of life outcomes with scientific mass collaboration. Proceedings of the National Academy of Sciences, 117(15):8398 8403, 2020.
Thomas M Shapiro. The hidden cost of being African American: How wealth perpetuates inequality. Oxford University Press, 2004.
Ali Shirali. Sequential nature of recommender systems disrupts the evaluation process. In Inter- national Workshop on Algorithmic Bias in Search and Recommendation, pp. 21-34. Springer, 2022.
Ali Shirali, Rediet Abebe, and Moritz Hardt. Allocation requires prediction only if inequality is low. In Forty-first International Conference Machine Learning, 2024a.
Ali Shirali, Alexander Schubert, and Ahmed Alaa. Pruning the way to reliable policies: A multi- objective deep q-learning approach to critical care. IEEE Journal of Biomedical and Health Informatics, 2024b.
Ashudeep Singh, David Kempe, and Thorsten Joachims. Fairness in ranking under uncertainty. Advances in Neural Information Processing Systems, 34:1 118888169998 2021.
Aleksandrs Slivkins, Karthik Abinav Sankararaman, and Dylan Foster. Contextual bandits with packing and covering constraints: A modular lagrangian approach via regression. In Proceedings of the 36th Annual Conference on Learning Theory, pp. 4633-4656, 2023.
Nancy L Stokey. The Economics of Inaction: Stochastic Control models with fixed costs. Princeton University Press, 2008
Vinithasree Subbhuraam (ed.). Predictive Analytics in Healthcare. IOP Publishing, 2021.
Halil Toros and Daniel Flaming. Prioritizing homeless assistance using predictive algorithms: an evidence-based approach. Cityscape, 2771):117-146, 2018.
Angelina Wang. Sayash Kapoor, Solon Barocas, and Arvind Narayanan. Against predictive optimiza- tion: On the legitimacy of decision maaiinnnmmainng algorithms that optimize predictive accuracy. ACM Journal on Responsible Computing. 1(1):1-45, 2024.
Bryan Wilder and Pim Welle. Learning treatment effects while treating those in need. arXiv preprint arXiv:2407.07596, 2024.
13

---

Published as a conference paper at ICLR 2025
Bryan Wilder, Bistra Dilkina, and Milind Tambe. Melding the data-decisions pipeline: Decision- focused learning for combinatorial optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp.
2019.
Sebastian Zezulka and Konstantin Genin. From the fair distribution of predictions the fair distribu- tion of social goods: Evaluating the impact of fair machine learning on long-term unemployment. arXiv preprint wxxv:2401.14438, 2024.
Helen Zhou, Audrey Huang, Kamyar Azizzadenesheli, David Childers, and Zachary Lipton. Timing as an action: Learning when to observe and act. In International Conference on Artificial Intelligence and Statistics, pp. 3979-3987, PMLR, 2024.
14

---

Published as a conference paper at ICLR 2025
A
NOTATIONAL CONVENTIONS
The variables related to an individual are indexed with a subscript i. The variables related to time indexed with superscript The variables transformed with p(-) are denoted with tilde.
Symbol
Notion
t
Time step which takes value from to T
T
Horizon
Pa
Failure probability of individual
Binary observation from an active individual time
Noise on observation model of Eq. (1)
p(p) == (1 - <p + (1 f()))
of
Number of positive observations from active individual up to time v = Eveto
Set of active individuals at time /
Set of active individuals at with y" = k: A = {i yf = k}
Set of individuals treated at
Af excluding those who will be treated at t: A A I Number of initial individuals at time = 1
Number of individuals who made it time t: No |
Proportion of initial individuals who made it to time t: n² = N
n
A//N
O
Posterior over for an active individual at Posterior over p given individual has made t and y k Probability measure over active individuals time
P p' =k) k:)
(F(
Pr ())
Probability measure Probability that active individual at has y k Likelihood that an active individual with failure probability p shows y k Expectation over active individuals at time Expectation over active individuals at time with y Expectation over two independent active individuals and j at time t
independent active individuals i and time
Pr = -k)
Pr'(y' k p)
BHH
E
E (
a
Mean of failure probability at time t: μa¹ == ['[p] Mean failure probability at time given y م EM
Var"(]]
Variance under Pr²(-)
22 = D; -1-
- +0²
G())
Cumulative distribution function (CDF) of the standard normal distribution
g(-)
Probability density function (PDF) of the standard normal distribution
Table I: Glossary
15

---

Published as a conference paper at ICLR 2025
B RELATED WORK
Prediction for allocation. Algorithmic predictions are increasingly employed to identify individuals who are most in need of limited resources. In many of these upplications, the timing of prediction and allocation is of the utmost importance. Examples include directing assistance to tenants at risk of eviction based on their predicted risk (Mashiat et al., 2024), using early warning systems to identify students at risk of dropout (Faria et al., ;017; Mac Iver et al., 2019; Perdomo et al., 2023; Rismanchian & Doroudi, 2023), prioritizing homelessness assistance while considering population dynamics (Toros & Flaming, 2018; Azizi et al., 2018; Kube et al., 2023), making ICU discharge decisions based on readmission or mortality probability (Chan al., 2012; Shirali et al., 2024b), and improved targeting of humanitarian aids (Aiken et al., 2022). For discussion on the role of machine learning in clinical medicine in particular, refer to Obermeyer & Emanuel (2016).
The adoption of predictive tools in resource allocation often comes with promise that improvements in prediction accuracy can transfer to the allocation setting. Recent critical studies, however, have challenged this (Barabas et al., 2018; Shirali et al., 2024a; Perdomo, 2024). Our work gives new timing dimension to this problem where prediction improvement is entangled with the population dynamics. Our work also emphasizes the role of inequality in this dynamic setting. In line with Shirali et al. (2024a) we found inequality a determinant factor in deciding which form of allocation works best in the interest of social welfare.
maxiimiinaiiiiing treatment assignment under budget constraints is also a well-cstablished topic in economics (Bhattacharya & Dupas, 2012; Kitagawa & Tetenov, 2018). While much of the literature focuses on estimating static heterogeneous treatment effects for a fixed population, we extend this work by examining the problem's dynamic aspects. Our model also bypasses the need to estimate treatment effects in observational settings (Athey & Wager, 2021) by incorporating these complexities into a general class of utility function and emphasizing the ovven-overlooked role of timing in predictions and allocations.
Related problem settings. A related setting that introduces similar tradeoff to ours is when observations come at cost (Stokey, 2008; Zhou et al., 2024). Our setting distinct from this line of research as in our model, the cost of additional observations arises naturally from the loss of opportunity to intervene early, rather than being part of the modeling assumptions.
Our work is closely related to subsidy allocation in the presence of income shocks, studied by Abebe et al. (2020). Their model captures a more general dynamic where individuals fail after experieneing potentially multiple shocks. Unlike Abebe et al. (2020), we do not assume full information setting. In similar vein, our proposed dynamic is also related to the dynamic models of opportunity allocation (Heidari & Kleinberg, 2021) and the dynamics of wealth across generations (Acharya et al., 2023).
Generally, the best estimates of the treatment effect are obtained when the allocation is randomized. This is often not the case when we need to learn while treating those in need (Wilder & Welle, 2024). The sample independence assumption is often violated in these settings (Shirali, 2022) and recent works have proposed various estimators to improve the power of estimators (Mate et al., 2023; Bochmer et al., 2024). Our model largely circumvents this complexity, as a simple ranking based on available observations is always Bayes optimal.
Our discussion is related to recisionnffcusee learning (Mukhopadhyay & Vorobeychik, 2017; Wilder et al., 2019; Elmachtoub et al., 2020; Elmachtoub & Grigas, 2022) in the Operations Research community, where predictions are informed by their downstream applications. In our work, we employ simplified observation model that allows us to consistently obtain posterior distribution over hidden variables. This approach eircumvents the challenges that could arise from inaccurate or biased predictions. There is also direct connection between our Algorithm I and decision-focusee learning. If we consider prediction as the ranking of individuals at all time points, then this algorithm effectively identifies the optimal prediction tailored for the subsequent allocation step.
Our over-time allocation is also related to multi-armed bandit problems with resource constraints in addition to reward (or utiliiy) generation (Agrawal & Devanur, 2016; Slivkins et al., 2023). In particular, our model is most similar to the rotting bandit (Levine et al., 2017) where reward decreases over time. Unlike the standard bandit problems, in our problem observations are available from all
16

---

Published as a conference paper at ICLR 2025
individuals and not only those treated. The exploration/exxiootttinn tradeoff then lies in waiting for further information or treating those already estimated to be vulnerable.
Prediction and policy problems. Historically, policy planning has relied on aggregate data; however, the promise of improved resource allocation, reduced costs, and more preventative in- terventions has led to the widespread adoption of algorithmic systems on an individual basis in governments (Athey, 2017; Levy et al., 2021). Our work contributes to this discussion, our insights have direct implications for policy planning evolving social contexts.
While causal inference can inform policy-making, it is not always necessary (Kleinberg et al., 2015). Our framework falls under the category of prediction policy problems where an accurate ranking of individuals is sufficient for effective allocation. Related to this topic, Wang et al. (2024) raise concerns about the legitimacy of decision-making based on predictive optimization.
The debate surrounding risk assessment tools has largely centered around their inherently predictive nature. However, as emphasized by Barabas et (2018) in the context of the criminal justice system, the focus of risk assessment should be guiding interventions rather than merely making predictions. Our research aligns with this perspective by studying prediction not as an isolated task but as an integral part of the resource allocation process.
The Moving to Opportunity (MTO) experiment, spon- sored by the U.S. Department Housing and Urban Development, exemplifies an early intervention aimed at improving life outcomes by providing low-income families with children living in disad- vantaged urban public housing the opportunity to relocate to less distressed private-marke housing communities (de Souza Briggs et al., 2010; Ludwig et al., 2008; Gennetian et al., 2012; Ludwig et al., 2013; Chetty et al., 2016). The mixed findings of the MTO experiment across different age groups and the contrast between interim and long-term analyses highlight the crucial role that timing and the considered time horizon play in determining intervention's 's effect.
The long-lasting effect of interventions.
The MTO experiment also shows early interventions and environmental factors have long- lasting influence. In our model, we consider the extreme case of this when individuals subject to intervention are longer vulnerable at any future time point. Hardt & Kim (2023) discuss how these long-lasting effects inform future predictions.
Shapiro (2004) argues that initial differences, rather than wage disparities, the primary drivers of persistent inequality in the United States. Consistently, Derenoncourt (2022) show that while moving areas with better economic opportunities theoretically provided improved prospects, local responses counteracted many of the potential benefits. Such complexities are all abstracted into the probability of failure in our model. While this abstraction helps focus on specific aspects, we acknowledge that it does not capture the full range of dynamics in the real world.
17

---

Published as a conference paper at ICLR 2025
C AN ILLUSTRATION OF TRADEOFFS IN ONE-TIME ALLOCATION
To further illustrate why the budget and inequality are key factors in determining the cost of waiting for accurate predictions in one-time allocation, present the following example.
Suppose initially, pl = (eta G + 1). This ensures that pl is G-decaying according to Defini- tion 4.1. Consider the problem of whether postponing the allocation from beneficial, or equivalently, whether AW* = W W > 0. For simplicity of the illustration, we assume p and fully effective treatments.
+ is
Denoting the set of active individuals at é with y¹ = k by Ai and N = A a direct calculation gives
Ng = N 1] = N G+1
N1 = N NE = N
G
2+2
1(G+1)
2
N [E(L p) p)p1 = 2) + 3)
N2 N L p) N (G 2) +3)
Note that N2 N2 and N < N7 + N2.
Lemma E.5 implies that the optimal allocation at t, should treat those who have higher y². Therefore, in our example, assuming B N1. the optimal allocation at only treats those in A}. Similarly, at + 1 = 2, first treats those in AB and then Ap. So, defining U = (-1o" [u (p)), for B N7. is straightffrward to obtain
AW B -U3
N B > N
Lemma E.5 implies U1 2 UP. Therefore, increasing the budget after N3 can only decrease AWt and favors earlier allocations. The effect of inequality is also well-captured in U2 UJ. A direct calculation shows sign(U? Ut) sign ((G + 1)(T
6). Hence, AW20 necessitates
6
G>
1.
In other words, higher inequality, reflected in smaller values of G, can render postponing allocation from i to + unjustifiable.
We illustrate the effect of budget and inequality by simulating one-time allocation for T = and N = 10000 in Fig. 3. Consistent with the theory, high inequality corresponding to G < 2 can make W < W Even when this not the case, a high budget can still favor earlier allocation.
-12
B (%)
Figure Illustration of the effect the budget and inequality on one-time allocation.
18

---

Published as a conference paper at ICLR 2025
D SUPPLEMENTARY ALGORIHTMS
Algorithm 2 Simulate trajectory
1: inputs:
2: to : starting time of simulation
3:
{N Lo
& 1k=0 number of individuals with y = k for k: = 0,....40 4p
4:
[T( {0, 1, .....,,,.............. T): valid non-decreasing sequence according to Theorem 5.1
5: output:
6:
{Nr W number of individuals reaching y² q(t) who are not yet treated, for t 2 to
7: function SIMULATETRAI(Oo {Nta Jk= {()))
8: for t = to
1 do for k= = 0 t do Find the number of untreated individuals from the previous step:
9:
10:
No No-1. 1 (k: qt 1)),
No1 k-
1 No=
q(t 1))
Backup formula:
Nt. No b
1111 (1 p)(1 P)]
11:
+ N k-1 Pp
p) p]
12:
end for
end for
14:
return (N d(t) 1
15: end function
19

---

Published as a conference paper at ICLR 2025
E SUPPLEMENTARY STATEMENTS
E. GENERAL STATEMENTS
Lemma F.1. Suppose f [0, R is non-decreasing function p. Consider two probability density functions P and Q such that Plp) is a non-decreasing continuous function of p. Then, we have Ep(f(p)] Z Eolg(p)). As direct implication of this lemma, the sign of inequality flips if either f or the density ratio is non-increasing.
@p))
@(p) Since So Q(p) dp So o 1, and a is continuous, there should exist critical value p* such that a(p) for p 2 p", and a(p) - 1 for p < p". Using this critical value to decompose the expectations and the fact that f(-) is non-decreasing, we obtain
Proof. Define (p) = P(p)
Ep[[()]] - (e((())) S 1()) 2(p) (o(p) - 1)
[[ f(p) Q(p) (o(p) d) S0" f(v) o dp
-(0") [ Q(p) (o(p) 1) f(0") I-" Q(p) (1 o(p)
Lemma E.2. Consider two con-increasing functions - [0, and b R [0, 1]. If
1 b(x) dx is finite and non-zero, the following inequality always holds:
( b(x)² dz)
( ((z)) 2 (ʃ axx)² (()))
( b(z) dz)
(9)
Proof. Define the difference between the left-hand side and the right-hand side of the inequality given in Eq. (9) as A. For simplicity, consider integrals as a discrete sum with a step size ó. Increasing the value of a(x') would change the value of A by
dA
b(x') /
bx)) dr 2a(x') .f b(x) dr.
da(x')
This implies that for any x' such that b(x²) > 0, increasing a(x') will decrease A if and only if
1 b(x)²
a(x')b(x') 2 1_ b(x) dx
Since both and b are non-increasing non-negative functions, their multiplication is also non- increasing non-negative function. Therefore, increasing a(z') will decrease A if and only if x' is larger than critical value x The non-increasing constraint then implies that for fixed the minimum value of A corresponds to a constant function a(z) ag. In this case,
A (oo ag) (/- b(x)2
(
b(x)) dz)
For do E [0, 1]. the above equation is always greater than or equal to zero, which completes the proof.
E.2 STATEMENTS ABOUT THE OPTIMALITY OF RANKING
Lemma E.3 (Bayes optimal ranking). Consider statistical model P {po 8 (a, b]}
that induces a family of continuous probability distributions over a sample space X. Assume P. has univariant sufficient statistics T X R. Consider samples drawn independently from two probability distributions with distinct parameters: X1 ~ po,; X2 ~ Pag- For ranking
function 6 X x X > 11,,), define the ranking loss
Loss((0,, 0z); 8(211 22)) 1 (0)(11 01) < <0.
20

---

Published as a conference paper at ICLR 2025
Consider 1₁ and O2 independently drawn from prior P over Q ffr any 82 82, T(22)= 2 T(1) + pe, (x1) Pez (x2) Z Pa, (I2) Pa, (Z1), a.c. then for any choice P x(T(x2) 2 }-
(10)
P that has no point mass, the Bayes optimal ranking rule is 8 (11,
Proof. For , and 2₂ independently drawn from P, the Bayes risk of ranking
R(P=2:) 8) Ea,~p E Eximpe Xampea
[loss(())
X2))
9-~P
The independence also allows us to decompose the posterior over θ and O₂ given X1 = 21 and X2 = 22 as PO0, x1) P x2). It is well-known that the minimizer of the Bayes risk is
32) = arg min R(P32, 8) E arg min (Ra,)P(((21)) [loss((O),,))) ((,-))
X1 = 3 X2 Ø2
6E(-1.1) 02~2((-122)
Plugging the ranking loss into this, we can further simplify the conditional expectation and obtain 8* (111,22) E arg min (e.p)()))) [los(((), 22): [2]
66(-1,1) (2-2(()
1+0 8
Pr(O1 > O2 x2, + 1 Pr(01 - O2 x2,
arg min 2
6,(-1,1)
2
arg min 5 [Pr(O1 > O₂ 11, 11, x2) Pr(O1 S O₂ x1,
d6(-1,1)
= sign (Pr(O, s O₂ 31, x2) Pr(Oi > O2 x1,
Now, using change of variable trick and the Bayes' rule, we have
Pr(O) I 2 22) - Pr(O) > 2 11.
b
82
P(01 P(O2 x2)) d01 d02 [
01 P(0 [1)) (22) d02 d0,
I.
[P(02
x22) - P(02 x1) P(O, x2)] d0, d02
/ |
b 02 P(O,) P(02)
[po, (21) po, (x2) po, (x2) po, (m1) d0, d02.
Z(z1, 222)
where (x2) is the partition function. The integral bound enforces 02 2 0₁. Then if the condition of Eq. (10) holds, we can conclude
sign (Pr(O1 I 02 x2) Pr(O1 > O2 x2, = sign (T T(x1))
Proposition E.4. Consider the observation model o Ber(s), where p(-) is a non-decreasing function. Define y² = Eeeey o'. For any prior P over p that has no point mass, ranking individuals based their yf is Bayes optimal.
Proof. At any time t, define the statistical model P = {pe- (Ber()(0))) St 6 [0.1] 1]} where we can think of the model parameter 0 as the failure probability p. All the observations from individual until í can be interpreted straightforward to see y is sufficient statistic for P and (= gu' (1 0)--"' The increasing
a sample from model in P: X = (o ...... _o ~ Po- Then, it is
property of also implies that 0₂ 2 + 0₂ 2 01.
For 02 2 0,, plugging pe into the condition of Eq. (10) gives
0 1
0
v/3 vv
po, (I1) po, (22) 2 pe, (I2) po, (21)
1,
0 0₂
Since for 1 1> 02 > 0 O, we have 0 1- > 1, we can conclude
8, 1-P2
pe, (x1) pe, (I2) 2 pe, (x2) pe, (x1)
+
2 2 v
a.c.
Therefore, P meets the sufficient condition given in Eq. (10) of Lemma E.3, and ranking based on its sufficient statistic oy is Bayes optimal.
21

---

Published as a conference paper at ICLR 2025
E.3 STATEMENTS ABOUT THE EFFECT OF ONE MORE OBSERVATION OR ONE MORE TIME STEP
Lemma E.5 (Expected utility is monotone in the number of positive observations and time). For any utility function o' (p) that is non-decreasing in p. we have
E [u' (p)) 2 E [p)))
for every k < tt If the utility is also non non-increasing in t, we have
[il" > 1 [u + (p)],
for every & S t. Here, Ej denotes expectation with respect to p ~ Pk: = =P' y² k))
Proof. We first prove the monotonicity in k. The likelihood Pr' = k p) has closed-form of (1-)"=,, Using this, we have
(p)) (p)
Pr'ly=
k 1-p k
x
Pr'
This is non-decreasing continuous function of p and, consequently, of p. for every < t. Since the utility function is also non-decreasing in p. Lemma E.1 proves the monotonicity in k.
We next prove the monotonicity in t. Using the Bayes rule and the update rule of Eq. (7), we have
(p) x (p) (p+ P Pr (y++t & (T-
P'(p) Pr = k p)
Pr = k (p)
Pr (y
Plugging the closed-form expression of likelihoods into this, we obtain
(p( (p)
x (1 (1-p) (1-p)(1-p)
Again, this is non-decreasing continuous function of p and, consequently, of p. for every k < t. Since the utility function also non-decreasing in p. Lemma E.1 implies 11 [u' (p)] Ex [u' (p)). Using the fact that the utility is also non- non-increasing in f, completes the proof.
Lemma E.6 (A positive draw from Ber(p) is more informative than Ber(p)). Consider the ob- servation model o Ber(ÿ), where p(p) is a concave function with p(0) 0 and f(1) 1. Let z ~ Ber(p) be a random draw from an individual with failure probability For any utility function u² (p) non-increasing in t and non-decreasing in p. we have
EL (p) 2 Efti 11++11 (p)).
(11)
for every k S t. Here, [- denotes expectation with respect to ~ Pk = =P'--- (...111² (0-18'=A) = =k).
Proof. Expanding the left-hand side of Eq. (11), we have
Ex [r(( 1 p) u (p)
ESP- n (p)
B (p) 2 1]
E [Pr( = 1 p)]
On the other, expanding the right-hand side of Eq. (11) using the updating rule of pp- x ('(((( - p) from Eq. (7), we have
+
k. (p)
EE[(1 p)p ((+1(p)
(tt (p)
1) 11
BB1(1 p)p]
Defin g(p) = p)p We argue that g(p) is concave on [0. 1]. To see this, observe that
g"(p) +1
The concavity of y implies 8" < Then, given that p(0)
p(1) = 1, and the range of ò is within (0, 1). it follows that ş' < 0. Thus, we can conclude g (p) S 0
for E [o, 1]. A direct consequence of the concavity of g is that g' (0- 2 (0) - g(p) = -g(p).
A straightforward integration then shows that for arbitrary p2 2 P1 0.
P2
((22)
(12)
P1
g(p))
22

---

Published as a conference paper at ICLR 2025
This incquality will allow us to further bound [ [p)+ as follows. Using un (p) =v)))(ppp)))) difference of the expanded sides of Eq. (11) can be bounded by
(p), the
E (p19(p2) P29(p))) ut (pi)
Eg ((22)
where pi and p2 are two independent draws from Pk-- Using symmetry and the fact that the distribution has no point mass, we can write the numerator
Ex ((119(22) - P29(p1)) a (p1) (1 2 p1) + (p2 < p1l)]
= - [(P1g(p2) p=g(p=)) (p1) u (p2)) 1(p2 2 p1l]
Then the fact that utility is non-increasing in p and Eq. (12) imply the numerator is non-negative. This completes the proof.
Lemma E.7. Consider the observation model Ber(p). Define uèg == Fiipl and 8 = E p)p}, where [x denotes expectation with respect to ~ Pj = Pe (-1 = k). For any arbitrary
function f : [0, + R. the following identities hold:
= 1 - p1 - p) s(p)]
[[()]
1-14% - 3
1 E -p) [(D)]-
[
%%
Proof. Using the updating rule of (p+ (p) Pp) p) from Eq. (7), we have
[+(([(()] = [s()) Ft
- p) -1
[ - (1 - p) (w) (1-
E (1 1
(1 P) 8t -1 p)
[1 - p) D) f(p)
1 p1 5%
Using the same techniques, we also obtain
- = (spp) (1 - p)
E p)p f(p) (0 -
E++ g+ttti kp]
B'((1-) ph (1 p)r --)
E p)h [(D)].
Lemma E.8 (Bounding the effect of one more positive observation expected utility). Consider the observation model o ~ Bcr( where p(p) is a concave function with p(0) = 0 and ((1) = 1. Define U. = EE (u' (p)) and ph == Egp (p] as the expected utility and the expected failure probability of an active individual at time t who has k positive observations. For any concave (Ai, X2 -decaying Lu (t))--isschhtt, utility function w², we have
H1
Uti1 - -ULt T. 1). (A2 Uk+1). *xt1
1
Proof. Denote the cumulative distribution function corresponding to Pt by F The concavity of p and its boundary values imply 2(p) is non-decreasing in p. Then, straightforward argument shows < (p)
(p).
k+ (p). Let ग [0, 1] + j0, 1] be the optimal transport map from pt to ptt). The
definition of π implies
U++1 U++ E [ut+] (m(P) ++1 (p) k+1
Using the concavity of the utility function, we can upper bound the above by v [ (v) (T(p) pi]
++
Ut+1
23

---

Published as a conference paper at ICLR 2025
Our observation that F (p) (p) implies that T(p) p. In other words, the optimal map 2ill p
X I-p is an increasing function of ğ (and therefore p). it follows that T(p) - is non-decreasing in The concavity of utility also implies that (u++1((p)) is non-increasing. Then, Chebyshev's sum inequality allows us to bound Uti1 U.+ the product of two terms:
must always shift the mass to the right. Furthermore, since
*++1 U - E [(" (('+))())) (r()) - p] E ((*"(((+)))) (144) - 11 (13)
Since the utility is concave, (u* is non-increasing. This enables to apply Chebyshev's sum inequality, allowing us to write
E "5 (p)) (1 p)] 2 E ((x (1-p)))-1111 (1-
which gives an upper bound on E [(x Now, since the utility function is (A1, X2) -decaying we have
E [[u ((u ((p) (1 [1- p)]
E ())+
1// E++1 Lu(t + 1) x2= ( (1-))+1--
E++1 [ p)(+1 (1 - 1k 1
= L. 1) A2 U
1 1 t+1
Plugging this into Eq. (13) completes the proof.
Lemma E.9 (Bounding the effect of one more observation and one more time step on expected failure
probability). Consider the observation model o ~ Ber(p), where p(p) = 1 (1 10-pp p)? and y > 1.
Suppose the initial distribution pa is G-decaying. For any k t, the following inequalities hold:
[+1 11+1 2 Mk+11
(effect of one more time step)
1 2 +G) MK41 M1 S 1 (1-TT))
k+I 7(1-k)+1+1) -(11))+14))
(effect of one more observation)
Proof. The proof of the effect of one additional time step is straightforward: Starting from the definition of pha11 and using the updating rule p(+1(p) x Pt (p) p) from Eq. (7), we have
E'pp- 5 (1 1ンー
E+ (1 r1 -)
p
E EIG - 1ー
E [ -1 -
Then, since (1 - p) non-increasing p. direct application of Lemma E. gives 14 1+1 2 Mktl
In the second part, we prove the effect of one more observation. We start by writing M 1+1 as
[+1 Et (pp pt (1 -) -
B+ (p ap (xh+2) (1 -) (1-
(14)
g++ p -1
E++ L+ (1-p)(-k (1 (1-p))
Here, we used the identity ø' = -ー Using integration by parts, we can write the numerator as
d (5 (1h+1) (1 - -)-= k. (1 - p)] = p. p k+t (1 -) pe+ (p) pp)
po|!
g++ Jp-
dp
S g1t1e1 - pt+1 (p)(1 - p) dp
+7 1)) S p. p. 1 - p dp
1. p pt - +
d
(pt (p) p)) dp.
24

---

Published as a conference paper at ICLR 2025
Here, we again applied the identity p' = >-p to arrive at the third term. The first term is zero. We next simplify and bound the last term. Using the updating rule (p) x P'())(1 p) from Eq. (7) we can write
1-2
p++ (p) P1 (1))
Z1+1 where Z++1 is normalizing constant. Taking the derivative with respect to and simplifying equations, we obtain
d (p (p)) - p)) (p)(1 -( 1)ptt))))) (p)+ (P')(p)(1-P)) pp) p)
dp
Zt+1
Since pl is G-decaying, we have
d (p++) (p) p)) - (1 1/4++11 +))p++((p)
-(1 +1+ C(++++))'++ v
dp
Using these bounds in the expansion via integration by parts and simplifying the integrals as expecta- tions, we can impose the following bounds:
(t (1- / -1 E
[P- dp
Using similar arguments, we can also derive the following bounds:
d
? (t k+) t 1 k+1 dp
(ph+)). (1 (1=pp)= (1 ++
Plugging these bounds into Eq. (14), we obtain
(1- - k)) + 2) 11 +++1=
[+1
S 1 S - (++++))++++++ -1
(15)
7 (t - k) + + G+1
- kt-
Using the lower bound from Eq. (15), after a straightforward calculation, we obtain
1 1 1-1 M - m1t1)
G
(16)
1441
1-
One can verify that the maximum of the terms inside the brackets occurs only when x++1
reaches its
smallest or largest values. Here, we only present the case where 1+1 takes its smallest value, but similar bound will hold when it takes its largest value. Therefore, the last missing piece of the proof is a lower bound on M241-
(+1 Using the upper bound from Eq. (15), we have
1 ++ 1- (G 1)
2
(1 - k) + +1+1
Repetitively applying the above operation yields
k+1
k+1 7t +))++++++++++ (G (G+1)
1
Pkt1 2
7 (t +
k
An implication of Lemma E. is mh the lower bound
S 11+11
1+1
We also know
1+1
2 0. Using these, we can obtain
S
H+1 k+1
1 ++
(G+1))
where S= k+1 SkE K) + +
Using the naive bound S 2
k+1 714141 further
lower bound p as
1+1
++1 1 M + (k 1)(
[+1
Plugging this into Eq. (16) gives
ME+1 14
H+1
7 + (k 1) 1
(1-
Y ( - k) +
k++1 +++ (Is I)G
Without further ado, using h < t and simplifying the equations complete the proof:
#+1 14 1+1
1
2 -+
# (1- K+T
(t +1+++1
25

---

Published as a conference paper at ICLR 2025
E.4 OTHER STATEMENTS
Proposition E.10. Suppose the distribution P over p is G-decaying according to Definition 4.1. This
guarantees
1
11 = Elpl 2 μ 2+
2p
0² = Varlyl 2 - +
112..
du Note that ac
0 and
Oa² aG
< 0. The above inequalities are light for P = Beta (1,1 G).
Proof. Using G-decaying property of P and integrating by parts, we obtain
μ [/¹ p pP(p) dp 1 5.²0 (1 -p)p dP
G
dp
dp
d(1 p)p
- p)pP(p) - dp
2p
G
Rearranging the terms proves μ 2 = Similarly, using the G-decaying property P and integrating by parts again, we have
1
2+0
0² + 2 = Elp = { p² P(p)
1 [. (1 1r-ppp²
dP dp
dp
1
d(1 - p)p²
G
dp
2p 3E(p")
G
Rearranging the terms, we obtain
2p
Blp 2 3 G
This implies 2² 2 0² 3+G 2
Proposition E.11. The following notions of utility fit into our definition of (A1, Ae)-decaying utilities:
1. the treatment fully effective, the utility function is (1, 1) deccyinn
2. the trealment succeeds with probability and otherwise fails the individual, as in the case of risky medical procedure, the utility function is (c. decayynn
3. If the treatment succeeds with probability a and otherwise has no effect, the utility function is
(a, 1e-decaying.
4. If the treatment reduced failure probability from to p/7 for q > 1, the utility function is (1---11TT-t 1)) deddeayn
Proof. The proof follows by plugging up) each case into Definition 4.4:
1. In case of fully effective treatments, u²(p) (1 TT The decrease in utility over time is
u' ('(p) u +1 (p) (1 p) p.
Therefore, x < 1. The increase utility with is
(1 (1-p) (u)) (p) n' (1- (1-p)T-++ u'(p)
( (0)
So, Xa 1. Putting these together, w (p) is (1, 1-d1ayicc
26

---

Published as a conference paper at ICLR 2025
2. When treatment succeeds with probability and fails otherwise, u'(p) (1 --p) The decrease in utility over time is
a' ('() - u ++ (p) (1 - p) cp.
Therefore, A S c. The increase utility with is
(1 - p) (u') + +u((p) - (11 (t) (uty(0)
Hence, X2 2 Putting these together, up() is (c, -)-decnyn
3. When treatment succeeds with probability and has effect otherwise, u'(p) + (1 a1 p) T (1 p) -f a (1 p)"-² The decrease in utility over time
u' (p) + (p) - p) = a (1 p) ap.
So, Å1 S a. The increase in utility with p is bounded by
(1- - (1-p)"-+ u'()) ( (1- +as1. (1- p) (u))()) + ('(p) (1))
Hence, de 1. Putting these together, u' (p) is (a, 1) decayyin.
4. case treatment reduces p to p/v, we have ut (p) (1 -// (1 -) The decrease in utility over time is bounded by
p) u' (p) u ++| (p) (1 p) = -1 (1 -p/7)=---
(1 (1-1/7) (1-))
Hence, d1 S (1 - -( The increase in utility with p is bounded by
(p)
(1 - p) (ut) +'((p)
(1 - p) 1-1 - (1-
= (1 - p)
+ +(1 (11p//77 (1 -p)
1-1/7
[1 - -1)=-==+ - (1 - 1p//))) T--1
1/1//----111111 [1/1 p/- 1-117)-111111///1-1
(1 1/7)(1 (1/7)(11////1)1 p/7) 1-1/7
1 (1 ([1-pp T)- -)
-11-p16 ((11p/7)TT- P/
7
(1 pp/7) T-1-1 11.
1-1/7
So, A2 1. Putting these together, u' u'(p) is - --1---1 deeayyngg
Lemma E.12. Consider the observation model o ~ Ber(ÿ), where p(p) = 1 (1 (1-1111)) p)" and yy > 1. Suppose the initial distribution pt is non-increasing. Let 16 be the smallest se such that individual would be treated at t given budget of B to be spent at t. We have
1' (7+1)) In
B
Proof. For notational brevity, let k = F. Define the complementary cumulative distribution function (CCDF) of a binomial random variable by
b(k,t) = Σ
(1)
p" (1 (1-)) -K
W==+1
27

---

Published as a conference paper at ICLR 2025
Note that b(:.)) implicitly depends on p. which we have omitted from the notation for brevity. The following identity will be proved to be useful:
(
1 W
(1) (x) k/
(t (w)(
k'
(1 p)-
Σ
k)) pp (1 (1- p)
dp
k==+11
k-=+11
c-
= 1. 1. 1
Σ
t
(k' - l7) Ft 16-1( '(1 - -D)) p))-k(-1
k!
kt =+=
[-1
( [t-1
1-1
=t xppp p² + t
Σ
k'' 1 331-1(11 5)--k(-1
Σ
1d (1- -))
k-
W=
t
1. xp
(b(k - 1,, 1) - -
(b(k: 1) 5²)
1 - p
1
t - (b(k- - 1, 1) b(k:))
Intuitively, the above identity relates the derivative of the CCDF with respect to to its finite difference across time. The CCDF is also related the number of individuals with y² > k. Denoting the number of individuals with y' = k by N we can write:
N N -'((kk)))
--=++1
Using the two identities presented above, we have
No = - E" E - 1, 1)] - No EE'b(kt))
km
1+1
Nº B'- - No. RE 0) + _ [0-1(1 ())
<.b(kk 1)
dp
Now, applying the updating rule 1p) x ('( - p) from Eq. (7), we obtain
N
Σ k=k+1
No.- = No. E'1 P p
blki O) +
1 1
No E'I( 1 2 db(k, t)
dø
W=
2 1 No [11(1 p)
db(k:
(17)
dp
Using integration by parts, we can expand the expectation:
(1((1 ()) dp
db(k, t)
= (T) - p) b(ki,) ((::0);- 0 - b(k,
(P' - p)) dp.
Tp"
Here, P denotes the distribution over p. For k < I, the first term above is zero. To bound the second term, note that P'
Pp(pp=
Pp)))
Then, using the identity z = (11p)) we have
B
1 d (p) - p)) s -ー 7 dp
(P p)) dp
We used (p')(p) < 0 to arrive at the above inequality. Plugging this into Eq. (17) and doing straightforward calculation, we obtain
No.
k ==
By repetitively applying such inequalities, we have
t-
7 k
N
No.
++1
k k=0
28

---

Published as a conference paper at ICLR 2025
Since the last individual who is treated at has y' k. the right-hand side is lower bounded by B. The sum in the left-hand side is also bounded by the total number of initial individuals. These yield the following bound on k:
In
In 1
Using In(1 + 2 Itc completes the proof.
F MISSING PROOFS
Proof of Theorem 3.1. Using the step function approximation, the exponential multiplier in Eq. (8) is only non-zero if
Dj Pil
2 ll(11/a)
Øij
This implies the following lower bound AR!:
(1) Pj)
10 Pdl
2 2m((1/a]
In(1/a)
AR'
S
4x In(1/a)
(1 - 2²)²
t
4
Suppose # (.) is L Lipschitz continuous. Using this and 07 S 1/2, we can further bound A R by
E (1 - p
1-1
21((1/a)
(m(1/a)
AR 2
1-2c
1
4T In(1/a)
(1 12)22
4nt²
Var [p] - (u)) 1-2
21n(1/a)
In(1/a)
V 4n In(/aa
(1 1x
4m
The ranking improves over time when A AR < O. In this case, it is necessary for the lower bound presented above to be negative as well. This completes the proof with Capprox. ln(1/a).
Proof of Theorem 4.3. We build on the more general results of Theorem 4.5. First, observe from Proposition E.11 that the fully effective treatment corresponds (1, decccying utility function.
Define twarm-up (7 + 1) In ). Plugging d
A2 and (u + (0()) T t 1 into
Theorem 4.5, we have
t - twarm up
T - (+++11)
(18)
1 + C wwarn up
21 wwam +1
Here, we summarized 2 4 + + + G into C. Consider two cases depending on whether is less
than or larger than le2 == (T wwarm- uurrmnupp up - 1)/2. When le, we can relax the right-hand side of Eq. (18) by
twrrmuup
T (1+ + OKt
Simplifying this bound through straightforward calculation, get
T + (4warm up + 1)(C +1)
1 1+15
2 2+ (twarm--u up + 1)
T
(twarm-un up + 1)(5 + 1)
2 2 + (twarm up + 1)f
T
C
< 2
(twarm-up + 1)( +
Therefore, we can conclude, either < t, or the above bound should hold. Since the above bound is larger than for this is the looser bound. Setting this 1 completes the proof.
[
29

---

Published as a conference paper at ICLR 2025
Proof of Theorem 4.5. We use the following shorthands and notation throughout the proof. Let N = A where A is the set of active individuals at t with y' = =. In the limit of many individuals, No = N Ex (G) -1 (1-))))))) Denote the posterior over given y' = k by P/-- The Bayes" rule implies (p) & (p) - - Denote the expectation over individuals in Ak In the limit of many individuals, E [-1 = Ep-Pt oo.P.t)) [-]. We use the shorthand U to denote E [p)] and j to denote Ej,[p] and 8 to denote Ej[(1 - p)tp]
by [. J.
Assuming the prior over p has no point mass, Proposition E.4 implies ranking individuals in descend- ing order of y² is optimal. Therefore, given a budget of B, the optimal planner sorts individuals in descending order of y" and allocates to the top B. Let 1 be the lowest y² of an individual that has received the allocation.
Suppose at time i, we have 1 k. Then B > N2 implies t. We argue that postponing the allocation from time & to time & + 1 can only increase overall utility if (++1 is either k or k + 1:
We first rule out [++1 > k ++11 1. If [(+1 > k 1, only individuals with y/+1 A + 1 can be treated. This will be a subset of the individuals that could be treated at t. In particular, individuals with y' k will not be eligible t + 1. Therefore, the whole budget has not been spent which violates the optimality of allocation at t + 1.
We next rule out 1++1 < k. The key observation is Lemma E.6, which states that the expected utility of an individual with y' = k who fails at the next step is higher than that of an individual with tf k + 1. In other words, failing provides stronger signal than regarding the individual's likelihood of failure. Formally, when |++ < k. everyone who was eligible for treatment at time f and survived to + remains eligible. The individuals who failed during this transition are replaced by new individuals with yt+1 < k + 1. In the best case, the expected utility from each new individual is Ut+] However, Lemma E.6 suggests that the expected utility of those who failed and were replaced is at least U-+1- Therefore, postponing allocation cannot be justified.
In the remainder of the proof, we derive an upper bound on AW == W W when |++ either & k + 1. We will then further simplify this bound to obtain sufficient conditions for AW < 0.
We first examine the case where |++1 k. Suppose at time we are able to treat A' individuals from Af. This number changes to A++1 at time t + 1. The change in total utility after postponing allocation for one step can be written
(+1
AW = Wt+1 W = (A 1 (A+IUULL +
C - (A'UE +
Σ k=
NbUU).
W=++1
From Ai. ratio of n4g fail and ratio of 5 proceed the next step while revealing more positive observation. This allows to relate N with N2, and N for k 2 1:
N = (1 - 1he 5tx) + No. 8 -1-
(19)
Plugging this into W we obtain
t+1
W++ A U++UU+1 Σ
(1 - ph. )U
Σ k=k+1
- u
k=k+1
u
+
No ph - st. Uutt + 8 & U++1
k=
The summand above can be significantly simplified. Using Lemma E.7 with f = u 4+1, we have
(1 - 1 - s JUt + U = E [[1 p) - (p))
Since the utility is (A1, -dccyying we can upper bound the above by
E [(1 p) =a -a(+1(m)) (u' (p) A1p) Uh A1ple
(20)
30

---

Published as a conference paper at ICLR 2025
Plugging this into W+ allows to upper bound AW*:
AW' S A A - A + N
A Σ No
(21)
k==++1
Spending fixed budget requires
H+
A ++1
A' +
Σ
No
Ny. k'=++1
Σ
k'=++1
Using Eq. (19) and performing straightforward calculation, we can simplify A
++ A
NE
Nyr
(22)
M==++
Plugging this into Eq. (21), we obtain
AW S -A - - + NESL(UEt Ukt1)
Σ (A1 - -UtH). (23)
k=k+1
For a utility function non- non-increasing in time, we have Ut+1 S E E++
" [u' Since P (p)
(b) x
(1 p)(1 p) is continuous and decreasing in for utility function non-decreasing in p. Lemma E.1 implies E [u'(p) < [p)] Ug. Therefore, we can conclude the upper bound of Eq. (23) decreasing A Thus, we can further upper bound AW by finding an upper
bound on A' Since (--1 = k, it is necessary to have A 2 O. Using Eq. (22), this will impose
an upper bound on A:;
A
5 5
Σ
N
k-
Plugging this into Eq. (23), we have
AW < NES - U2)
Σ k=k+1
(1 - UU))
(24)
We next consider the case of [++1 = A: + 1. We follow steps similar to those in the previous case. The change in total utility after postponing allocation for one step is
AW = W W = ((A 1- -N++1
Σ
N
kr
P=k+1
(A + Σ N.U
#=k+1
Plugging N expansion from Eq. (19) into W obtain
W = (A 141
N
N
No. m S
Σ
1 o
U
k+1
= ++1 - U
Σ M=++1
NO - 1
St.
st
U
k++1
As showed in the previous case, the summand above can be bounded by Uj this into Wi++1 allows us to upper bound AW':
Aapk, Plugging
AW < (A+1- N N
A
Σ
No
(25)
M=k+1
31

---

Published as a conference paper at ICLR 2025
Spending fixed budget requires
++
A' (A [
Σ
E
No.
k=
k==+11
Using Eq. (19) and performing a straightforward calculation, we can simplify A 4++
A -A+
Σ
Nor.
kt km
Plugging this into Eq. (25), we obtain
AW" S (N A - - -
Up)
Σ NEr Uf). 1m
We argue postponing allocation is only justified U+1 > U.. Otherwise, the eligible individuals with the lowest y' at the previous step already have higher expected utility than the newly eligible individuals at t + 1. This implies that the above upper bound is increasing in A++1, The largest A [+1 happens when A ++1 approaches N The reader can already verify this will lead to the same bound the previous case (Eq. (24)).
1++1
Before proceeding to analyze the upper bound of Eq. (24), we make one more observation. Recall that in Eq. (20) we used (Λ1, Ade-cyyg property of the utility function. However, Lemma E.6 implies another complementary bound of this quantity:
E [11 - p) w (p)] & Up- [p u [p)) s UO - 14
Comparing this with the bound in Eg. (20), we observe that any result involving x can always be updated by substituting a with k41- Such update Eq. (24) results in
AW s (N
Σ ME - UU})
R=++1
Recall that deferring allocation requires Uf41 > Ug. The above equation further implies that & 2 Ei Ni. is also necessary. Now, looking back at Eq. (24), we can conclude that under these necessary conditions, the upper bound is decreasing in Uh- Hence, decreasing Už to U++1 can only increase the bound:
AW' S -
Σ
(An
(26)
k=k+1
We will use this inequality as a basis for the remainder of the proof.
The following identity will be useful:
5 No B'((1 p)D 5* (1 (1-1)<-1)
k +
NE+1 B-- B' 1itt k)
N
(27)
Here, we used the updating rule p(+1(p) = (p) from Eq. (7). Eq. (27) implies that individuals with y is who survive to the next step while showing one more positive observation. (141) of N++1 So we can conclude that the rest of k+1 comes from N Therefore, we
form k+1) have
N
N++1
(28)
Plugging this and Eq. (27) into Eq. (26), we obtain
AW* < N
te + 1
[utt]
t k ut
( ) (A1 -
(29)
k
In the rest the proof, we consider two cases where the utility function is either (21,22)-decayy decayyng or just λι -ddeccyn
32

---

Published as a conference paper at ICLR 2025
The case of (2)) utility. The difference (U l)+ in Eq. (29) captures the effect of one more observation on the expected utillit. For a (A1, 22) -decaying utility, Lemma E.8 upper bounds this effect by
- U S (1)+)((0) (A2 -
Utt))
R++
Here, we used (u/+1) ((0) in place of the Lipschitz constant u in the lemma because the utility function is concave. Plugging this into Eq. (29) and using the assumption that X 2 A2, obtain
2 t k p - M X2
AW* S cl(utt)
Mk+1
Pk
Here, we summarized all the terms multiplying before the bracket constant C. since these terms do not affect the sign AW!, straightforward to verify ud+1 2 (+1 and u S Pk+1 for > 1, Lemma E.9 yields
1+1 Then,
A s c
(30)
72+ G)
K+1 -
The upper bound of Eq. (30) is increasing in k. Therefore, the last missing piece of the proof is an upper bound on k. Lemma E.12 provides such an upper bound and completes this part of the proof.
The case of de-decyn utility. As we discussed above, decreasing Ut in Eq. (24) can only increase the bound. Setting Ug then gives
AW s NAstUtH
Σ
Nerpk) A1
k=
Plugging Eq. (28) into this, we obtain
k
U - ( (-- k k-1
AW" & N
k - 1
(31)
t ++1
Concavity of the utility function and its zero value at p = 0 imply
U S (1'+)'(0)) [+1 Plugging this into Eq. (31), we have
AW S ( ((=h))
k+1*
where all the factors outside of the brackets are summarized in C. Using the upper bound on k from Lemma completes this part of the proof.
Extending to all future times. As the final remark of the proof, note that the upper bounds provided in all cases are shrinking with Therefore, if AW* < O, then postponing allocation to any future time cannot be justified.
Proof of Theorem 5.1. Consider N individuals initially at time = 1. Denote the subset of A with y¹ k by AL. Define ni- | Denote the set of individuals treated at by It. Excluding I' from Af. denote the remaining by A == A'' I', and define ni. |.Ag. //N. In the limit of N + oo, we can treat n and nnf as continuous variables taking any value in [Ó. 1]. Step 1. The following property of the problem dynamics allows to infer whether Ar is empty not based on the previous step.
Lemma F.1. Defining nt al any time and for any k, we have
n 2+1 > 0 - n >0 0 or n > 0.
See proof page 35.
33

---

Published as a conference paper at ICLR 2025
Step 2. Consider two active individuals i and j at time t. If yf > vf. for any utility function non- decreasing in p. Lemma E.5 implies treating yields more utility than j in expectation. Therefore, the optimal allocation any point should not target individuals with lower y" while there are active individuals with a higher y'-
Step 3. We show that, except for the first time step, at each time t on the optimal path, the treated individuals & should have similar values of y².
Lemma F.2, For A' + 0 and 2 2 on the optimal path, for any i E D' we should have of = y3 max (i | E A.).
See proof on page 35.
Step 4. When an individual i with of = k 2 1 treated at t, not only is Ai. non-empty, but - is also non-empty.
Lemma F33 For k 2 1, if there exists i I' on the optimal path such that yt = k, then n > 0.
See proof on page 35.
Step 5. Using the structure imposed on the optimal solution in the previous steps, we next restrict I++1 based on It.
Lemma F.4. Suppose A' + and let = max(y/ i A*}. On the optimal path.
*ITT"= = =Ap either I++1 Att or I++1 = Att]
IfI' c Al. either I++1 C 1+ k+1 or I = =Aht2 = 0.
See proof on page 35.
Step 6. Except for one time step, at every on the optimal path, either I = 0 or I' treats everyone with 3² 2 k for some k. If there were two time steps l and L' violating this, because of the linearity of the expected utility in [I') and [Z' optimally, one would become zero treat everyone above cutoff. This and Lemma F.4 complete the proof.
Proof of Lemma 5.2. We first iterate over two of the three unspecified parameters, i and q(-) in Theorem 5.1. There are T possibilities for L. A valid sequence q(-) can then be determined by specifying g()) and a binary sequence of length T 1. The tt binary value in this sequence determines whether q(t + 1) - q(t) will be: 0 or 1 if + f, or 1 or 2 if = E. Since the maximum y' each time it is straightforward to verify that for any sequence that starts with q(1) 2, there exists another sequence with g() < 2 that treats similar individuals. Therefore, there are effectively only three choices for (1). Together, iterating over these parameters requires 3T 2 steps.
Given and valid sequence g(-). there remains to determine the allocation at based on the available budget. Let p denote the proportion of A q()) who are not treated. One can verify that for a fixed i and q(-), both the spending and the expected total utility linear in p. Therefore, find p. we only need to simulate an allocation for two distinct values of We then use these two points to identify the linear relationships and determine the optimal p under the budget constraint. In Algorithm 1, we perform this by simulating the trajectories for 0 and p 1, which takes ( operations. So. overall, we require O -1) operations to iterate over all rollouts.
Proof of Theorem 5.3. While iterating the search space through Lemma 5.2, we can store the number of individuals from Af. treated at each t and Then there remains to calculate Uc == Ep->"((lp"=>)> ju' (p)). Assuming the expectation under posterior distribution can be calculated ef- ficiently in constant steps. happening in the same loop of iteration as Lemma 5.2, it does not add to the asymptotic complexity of the algorithm.
calculate the total utility of an instance in O Since this is
34

---

Published as a conference paper at ICLR 2025
Proof of Lemma F.I. For k 2 I, A will consist of those in A' who survive and have d' 0, or those in A who survive and have 0²+1 =====10 1:
n = n p)(1 - p)] + n Ey p)]
Here. E denotes expectation with respect to p~ Pk
(- v = k). We implicitly used the fact
that the targeting cannot distinguish people with the same y". The same update rule works for k if we set n O. One can also verify that since the prior over p has no point mass, the expectations above are non-zero. This completes the proof.
Proof of Lemma F.2 The proof is by contradiction with optimality and has multiple steps:
Let k = max {vf | i E A²). Since n = 0, Lemma F.1 requires n mik (-1 0. On the other hand, when n > O. Lemma F.1 requires either f-11 f--1 fx-1 to be non-zero. Since we just argued f 11-1- 0, it is required have n >
Since h > 0, Lemma F.1 implies n individuals with different y", there should be two individuals i,j I' such that y k and y = =
Then Step 2 requires that if I' contains
Consider the following tie- neebbraking when treating individuals with a similar y": Assign a random priority value 2 E [0. 1) to each individual in the initial pool. At time t, update the priority value by 2 2 + of 2t-1, If any two individuals are a tie to receive the treatment, choose the one with the lowest priority value. This tie- breaking does not change the optimality of an allocation rule.
So far we showed n > 0, i.e. there exist some individuals in A left untreated at f - 1, but there exists j E 1 who is treated at We argue this is suboptimal as the budget to treat could have been spent earlier to treat those in AA,11, yielding higher utility. To see this, consider counterfactual allocation rule that treats one more individual from A/_l at 1, to be referred to as individual j'. This individual has either failed or made it to t. failed, Lemma E.6 implies that the counterfactual treatment could be more effective. If j' is active at t, she will either have vf.- = k or vfy- = k 1. If vf. = k. then she treated with others in A.. If g/y k 1. still j' is treated. This is because j' maintains the lowest priority value among Ai_ by the construction of the priority values. Since j' is treated in any case she makes it to 6, she could be treated earlier at t- - 1. This could yield higher similar utility as u is non-increasing in t. This contradiction shows v = V k.
Proof of Lemma F.3. The proof is obvious for / = 1 since k can only be and unless the budget is excessively large to treat everyone, we have ng > For t 2 Lemma F.2 requires ni. > 0 and n/+1 Then Lemma F. implies ni
and n 1 > 0, so n > O.
Proof of Lemma F.4. We first prove the first part the lemma. If = -Ai,, there are two possibilities
for k. If k = 0, then At = @ and Step 2 implies no one is left untreated at t. So, I'+1 1+11
A = 0. k 2 1, then Lemma F.3 implies ni > 0. Then Z A implies ni_ > 0 and Therefore, using Lemma F.2, treated individuals at + should be among A or no one will be treated.
n 0. Applying Lemma F.1 gives n f+1 > 0 and n
We next prove the second part of the lemma. I' Ak. have ni > 0 and nt+1 M 0. 1+1 > and n = Therefore, using Lemma F.2, treated individuals
Then Lemma F.1 implies n 1
at t + should be among 1++1
k+1 or no one will be treated.
35


Reviews:
[{"review_id": "rK8Y4KLI3m", "reviewer": "Reviewer_XpSw", "summary": "This paper considered resource allocation based on predictions of ranking among individuals. The resources are interventions to prevent individuals from experiencing undesirable outcomes. The authors examined the tension between relying on earlier, possibly noisier predictions to intervene before undesirable outcomes, and waiting to intervene with more precise allocations after gathering more observations.  Through statistical analysis, they showed that individual prediction accuracy could improve with more observations, but the overall ranking performance does not necessarily improve. Moreover, they identified inequality, which is the variance of individual failure probabilities, as a driving factor leading to this counterintuitive behavior. When the planner needs to allocate resource at once, an upper bound on the optimal allocation time was given in the paper. When the planner can allocate resources over time, an algorithm that is provably optimal with respect to the total utility is developed.", "questions": "1. In the derivation of Section 4.1, a measure of inequality is introduced in Definition 4.1. What are the connections, if any, between this measure of inequality and the variance of individual failure probabilities as adopted in Section 3? \n\n2. In the studied budget allocation setup, are all individuals assumed to require the same budget? If so, can these budgets be viewed as available slots to an opportunity, e.g. the number of students that can be enrolled in a support program, and will assigning different budgets to different individuals affect the presented results?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. The paper studied a novel problem of ranking prediction guided resource allocation. The connection between prediction quality and downstream decision performance is an important concept that is not well understood yet. The paper contributed new insights towards the gap. \n\n2. The paper highlighted interesting tradeoffs between waiting for observations to improve prediction accuracy and losing vulnerable individuals due to waiting. The connection to inherent inequality in the population further enriched these results.  \n\n3. The paper provided rigorous theoretical derivation of all the results. The problem formulation, despite necessary simplification, is general enough to represent broad application contexts.", "weaknesses": "1. The visualizations in Section 5.3 effectively illustrate the theories discussed in the section on sequential allocation. Sections 3 and 4 would benefit from similar empirical support. Incorporating experiments or even basic numerical examples would make the theoretical results more accessible and intuitive. For example, in Section 4, an experimental validation of the derived upper bound on the optimal timing would offer a concrete sense of how these bounds apply in practice.\n\n2. The writing in Sections 3, 4, and 5, while necessarily technical, sometimes read dense. It would be helpful to have clearer explanations of the formulas. In addition, discussing the intuition and the logic of complex derivations behind key theorems and algorithm would also help with the overall flow and clarity.\n\n3. Additional explanations could clarify specific aspects of the formulation. For instance, the paper focused on predicting failure probabilities as a basis for resource allocation; however, it might also consider scenarios in which qualification probabilities are predicted instead, and resources are allocated based on those rankings. A discussion on why the study emphasized failure probability as opposed to other potential metrics would be informative. In addition, resource allocation problems often involve various constraints beyond following the ranks among individuals. A discussion of whether such constraints could be incorporated—and if not, why they were excluded—would add to the completeness of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MFTQOQr1LQ", "reviewer": "Reviewer_qU3b", "summary": "The paper presents a stylistic framework for analyzing the utility of intervention strategies when information about individuals is revealed in an online / stepwise manner. In particular, suppose a mechanism designer has access to some intervention budget $B$ over a set of _active_ individuals $\\mathcal{A}$. At each time step $t$, each individual $i$ may drop out of the active pool $\\mathcal{A}_t$ based on sampling from a Bernoulli distribution with probability $\\tilde{p}_i$. The goal of the mechanism designer is to intervene with the high risk individuals (those at high risk of dropping out of the active pool). The challenge is that there is a tradeoff between the available amount of information on each individual (which improves via waiting for more time to pass), and the effectiveness and/or ability to intervene. The latter is impacted by two facts (1) high risk individuals benefitting most from interventions may drop out of the pool earlier; and (2) utility / welfare is higher when intervening at individuals earlier in the time horizon (the authors assume a concave welfare utility modeling function based on individual probabilities $p_i$).\n\nWith the general framework setup, the authors tackle three specific settings.\n1. Section 3: Bounding the _ranking risk_ for ranking all individuals at each time step based on their probability of dropping out of the active pool.\n2. Section 4: When the mechanism designer can intervene upon the $B$ individuals most at risk, but only at one specific point in time, how do we find the optimal point, and how good is it?\n3. Section 5: If the mechanism designer can spread out its intervention budget over the time horizon (i.e., intervene at different points in time), how can the optimal strategy be calculated / computed in a tractable manner?\n\nTo adress the first point, the authors derive an exact characterization of when the ranking risk improves with information collection (Theorem 3.1). At a high level, this charectizeration shows that the ranking risk improves only if the impact of individuals dropping out of the population is dominated by some function of the information gain, modulo constant factors. \n\nTo address (2), the authors show in Theorem 4.3 that (under the fully effective treatment assumption) the best time to intervene with the entire budget $B$ depends on the total time horizon $T$, the number of individuals, budget, and amount of inequality amongst the individuals (captured by a parameter $G$ for a $G$-decaying distribution). Higher inequality means that the intervention must be applied earlier in order to be most effective. A similar characterization is made for the more general setting where interventions are not 100% effective, but decay with time or depend on the underlying probabilities (Theorem 4.5).\n\nFinally, the authors move to the more complex setting where the budget may be distributed across different points of time $t$. They demonstrate that a naive approach of computing the best policy in the resulting MDP is intractable, but by using particular structure of the problem, can be simplified into searching over a much smaller number of parameters (Theorem 5.1). That is, the optimal intervention will have a specific structural form, whose parameters can be efficiently optimized over (Lemma 5.2).\n\nLastly, the authors run some experiments on real data from the national eduational longitudinal study. An important takeaway echoed in each of the sections is that it is often beneficial to intervene earlier — with noisier data — than it is to wait until better information is collected.", "questions": "How should I think about $\\gamma$ in Assumption 4.2 and the reliance on $\\gamma$ for Theorem 4.3?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This paper is extremely well-written, concise and clear, and also makes progress on a very important problem: how does information gain (in terms of improving accuracy of machine learned predictors) trade off with the potential harms / opportunity costs of intervention delays? \n\nOriginality: The stylistic framework seems reminiscent of an over time version of Shirali et al. — who ask about the utility of individual predictions when faced with intervention budgets — but most technical details are different. I believe the online ranking / budgeting setting of this work is quite natural, realistic, and novel.\n\nClarity: I found the writing precise and clear throughout.\n\nSignificance: Although the results are within a stylistic framework, the paper presents another datapoint (in addition to Shirali et al.) supporting the fact that accurate individual level predictions may not or should not be the end-all be-all goal when maximizing the effectiveness of interventions in school, healthcare, etc. These works together are surprisingly counter-intuitive, given that most of the work within the areas of algorithmic fairness and individual level predictions focuses on obtaining accurate predictions. This paper suggests that when viewed from a higher level within the _context_ of decision making and budgeted intervention, the accuracy of individual level predictions may matter far less than one might think. Overall, this work has the potential to guide much future research in the direction of what is actually most impactful within the context of real decision making and intervention systems. Because of this, I believe this work will be highly significant within the next few years.\n\nI also agree with the authors and think there are numerous potential directions that can build upon this work. For example, the fair ranking community has proposed alternatives to simply ranking individuals by their probability of dropping out (e.g., Singh et al. 2021). Whether or not this is the correct thing to do is certainly context dependent, but one can imagine similar characterizations for when information gain may hurt or help when applying interventions in non-welfare maximizing ways (in the interest of fairness).\n\nSingh et al. 2021: Fairness in ranking under uncertainty.", "weaknesses": "The only weaknesses I have are minor, although I have not carefully checked the proofs of the statements. First, I believe that 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 who are all enrolled in a particular “catch-up” class for low performing students. Since all students have the same teacher, we may expect that their observations may be correlated. For example, if the teacher is really good, then maybe nobody drops out of the pool and no intervention is necessary (the opposite also holds true).\n\nSimilarly, I think assumption 4.4 can also be discussed in more detail. I understand that this is a technical assumption, but perhaps a note in the appendix about what kind of utilities this can capture, or some common examples, may be useful. I may have missed this somewhere though!\n\nMinor comments\n1. Typo: line 807 “particular, Our model”\n2. Are there possible citations for line 266-267: “For instance, consider housing vouchers or dropout prevention programs, which have been found to be very effective.”?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gAfWnpapCK", "reviewer": "Reviewer_wWAe", "summary": "The authors study the tension between allocating resources based on early, noisy observations versus waiting for additional observations, with the risk of individuals dropping out or \"failing.\" The paper focuses on (i) how ranking loss changes with more observations and (ii) identifying the optimal timing for resource allocation. Section 3 analyses the variation in ranking loss with increasing observations, Section 4 finds the optimal timing for a full-resource allocation, and Section 5 extends this to multi-step, budgeted allocations, introducing an algorithm to compute the optimal over-time allocation.", "questions": "Please address the first bullet point in the weaknesses section.\nAlso, the runtime for Algorithm 1 is with the general utility class (Sec 4.2); could it be faster with fully effective treatments?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Sections 4 and 5 are well organised, covering one-time allocation and then extending this to over-time allocation.\n- The experiments in Section 5.3, with visualisations for one-time and over-time allocations offers useful insights on how larger budgets allow earlier allocations.", "weaknesses": "- Algorithm 1 scales exponentially with $T$; while this improves over naïve iteration, calling it “efficient” might be misleading. The experiments with NELS data used small $T$ values, but $T$ could be large with fine-grained data. Can you discuss practical limitations with larger T values?\n- (Minor, organisational) Section 3 could benefit from a restructuring:\n   1. Thoerem 3.1 can be moved to just before \"approximating ranking risk\", with a sentence on how the ranking risk can improve only if the change in population from failure is less than the gain in observations.\n  2. The computations for “dynamics of ranking risk” were tedious to parse and could be moved to the appendix in the interest of readability.\n- (Minor, related works) The paper does a good job covering related works in the appendix. The authors reference Abebe et al. (2020), which investigates optimal subsidy allocation to minimize failure probability. A useful addition to this line of work is Heidari & Kleinberg [1] and Acharya et al. [2], which examine welfare-optimizing policies under finite time horizons to support low-income groups. Additionally, Azizi et al. [3] (2021) on safe exits for homeless youth could complement Kube et al. (2023), which is already cited.\n\n[1] Allocating Opportunities in a Dynamic Model of Intergenerational Mobility \n\n[2] Wealth dynamics over generations: Analysis and interventions\n\n[3] Designing fair, efficient, and interpretable policies for prioritizing homeless youth for housing resources", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "V22T7fueFg", "reviewer": "Reviewer_S7QU", "summary": "The paper studies the problem of resource allocation by considering the trade-off between allocation efficiency and gathering further observations. In particular, the problem is relevant in the context of societal resource allocations, where we are tasked to identify the individuals to intervene (e.g., housing benefits). The authors propose a theoretical framework to study this issue and show that waiting to acquire more observations indeed increases the predictive accuracy, but it also reduces the average ranking loss. Lastly, the authors validate their theoretical findings on a simple semi-synthetic experiment.", "questions": "I have no questions for the authors.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The authors study an interesting problem related to allocating resources to maximize the overall utility, by trading-off acquiring information to improve the predictive accuracy and the allocation timing. This topic is not in my main research area, so I cannot comment on the novelty of the approach.", "weaknesses": "The authors tackle this problem from a statistical point of view, rather than the classical ML formalization. Thus, the theoretical framework might be considered too simple and lacking grounding in a realistic scenario. The authors simplify and put many assumptions in place to derive their theorems and bounds, but I believe some of them might not be considered reasonable. Some examples:\n- $o^t_i$ is essentially a binary variable. A more realistic assumption would have been to consider $o^t_i$  is a feature vector $x \\sim P(X)$.\n- $\\tilde{p}$ is an increasing function. Do you have any examples about situations where it should be the case?\n- $\\tilde{p}$ are assumed to be known, while in practice we might have access only to an (reasonably good) estimator.\n\nThe experiment's description could be expanded. It is not clear what is meant by “failure”, or “inequality” in the context of students. Moreover, the observation model is also not clear. Providing more examples with other realistic datasets might strengthen the overall message. \n\nAlgorithm 1 is not “efficient” in a computational sense. As shown by Lemma 5.2 and Theorem 5.3, the complexity is exponent in time $T$. Even if $T$ is manageable in a real setting (references?), I would not consider it as “efficient” in the broad sense (e.g., polynomial in $T$) and I would suggest the authors rephrase it in the manuscript. \n\n(Very) Minor nitpicking:\n- I would have preferred to see a small “related work” section in the main paper, citing at least the most important/relevant works in the area. It helps position the paper in the literature, and it helps unfamiliar readers to understand the relevance of the contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)