# The Relative Value of Prediction
in Algorithmic Decision Making

Juan Carlos Perdomo
Harvard University

###### Abstract

Algorithmic predictions are increasingly used to inform the allocations of
goods and interventions in the public sphere. In these domains, predictions
serve as a means to an end. They provide stakeholders with insights into
likelihood of future events as a means to improve decision making quality, and
enhance social welfare. However, if maximizing welfare is the ultimate goal,
prediction is only a small piece of the puzzle. There are various other policy
levers a social planner might pursue in order to improve bottom-line outcomes,
such as expanding access to available goods, or increasing the effect sizes of
interventions.

Given this broad range of design decisions, a basic question to ask is: What
is the relative value of prediction in algorithmic decision making? How do the
improvements in welfare arising from better predictions compare to those of
other policy levers? The goal of our work is to initiate the formal study of
these questions. Our main results are theoretical in nature. We identify
simple, sharp conditions determining the relative value of prediction vis-à-
vis expanding access, within several statistical models that are popular
amongst quantitative social scientists. Furthermore, we illustrate how these
theoretical insights may be used to guide the design of algorithmic decision
making systems in practice.

##  1 Introduction

Algorithmic predictions are increasingly used in the public sphere to improve
the allocation of scarce resources. At their core, these prediction algorithms
aim to provide decision makers with valuable information regarding the impacts
of particular interventions, or the likelihood of future events, in order to
determine who will receive a social good. ††Email<EMAIL_ADDRESS>
For instance, in education, over half of US public schools use tools that
predict which of their students are likely to drop out in order to target
their limited counseling resources to students that need them the most
[Balfanz and Byrnes, 2019, U.S Department of Education, 2016]. Similarly, in
Israel, officials build risk predictors to determine the likelihood
individuals will develop serious pulmonary disease in order to prioritize
people for the Covid vaccine [Barda et al., 2020]. Beyond these specific
examples, this idea that better predictions implies better decisions, and
hence higher welfare, is pervasive, and underlies the design of risk
prediction tools used in numerous other domains (see Section 2 for a list of
examples).

From a system design perspective, we see that prediction is really a means to
an end, rather than an end in of itself. Predictions help inform decision
making with the ultimate goal of increasing some context-dependent notion of
social welfare (e.g. the number of on-time high school graduates). And, if
improving social welfare truly is the goal, there are of course many different
policy levers one could experiment with.

To name a few, apart from optimizing the quality of decision making via better
predictions, one could keep the current predictor fixed and focus efforts on
expanding access to the available resources (e.g., invest in more counselors
so as to intervene on more students). Alternatively, instead of expanding
access or improving prediction, one could also focus on improving the value of
the interventions themselves (e.g., boost the quality of tutoring).

Those tasked with solving these resource allocation problems do not always
have the luxury to simultaneously pursue all these various avenues of
improvement. Given the broad space of design decisions, we inevitably need to
identify the most cost efficient ways of improving overall welfare. Therefore,
we ask:

_What is the relative value of prediction in algorithmic decision making?_

In this work, we initiate the formal study of this question. We aim to develop
a principled understanding of how improvements in welfare arising from better
prediction compare to those induced through other policy levers such expanding
access or enhancing quality.

As a byproduct of our inquiry into the relative value of prediction, we also
aim to shed light on a related question: What does it mean for a predictor to
be “good enough” for decision making? At what point do we decide that we no
longer need to collect more features or train a more accurate predictor?
Summarizing briefly, we argue that predictions are sufficient to enable
reliable decisions if the relative value of improving prediction is _small_.
That is, if it is relatively more cost-efficient to improve welfare by keeping
the current predictor fixed and instead focusing efforts on expanding access
or pursuing other policy levers. Our theoretical results establish simple and
precise criteria for when these conditions hold true.

###  1.1 Overview of Framework & Contributions

In this paper, we study problems where a social planner is tasked with making
a single binary decision for every member of a population, subject to a
resource constraint. The reader may think about the decision as whether or not
an intervention, or social good, is allocated to a particular individual unit.
Constraints reflect limits on the total amount of goods or interventions that
can be allocated. While there is a single decision being made per unit,
crucially, the welfare effects of these decisions differ across units
(alternatively, individuals). The goal of the planner is to efficiently select
which units are allocated goods in order to maximize overall welfare.

More formally, we assume that there is a distribution ${\cal D}$ over units
represented as pairs $(x_{i},w_{i})$. Here, $x_{i}\in\mathcal{X}$ is the
feature representation of unit $i$ and $w_{i}\in\mathbb{R}$ is the _welfare
improvement_ achieved by making a positive decision (intervening) on unit $i$.
The planner uses these features to decide on an assignment policy
$\pi:\mathcal{X}\rightarrow\\{0,1\\}$, where $\pi(x_{i})=1$ if unit $i$ is
intervened on and is 0 otherwise. We formalize the idea that resources are
scarce by requiring that $\operatorname*{\mathbb{E}}[\pi(x)]\leqslant\alpha$
for some $\alpha\in(0,1)$. Writing this out as an optimization problem, the
planner solves:

$\displaystyle\max_{\pi\in\\{\mathcal{X}\rightarrow\\{0,1\\}\\}}\quad$
$\displaystyle\operatorname*{\mathbb{E}}_{(x_{i},w_{i})\sim{\cal
D}}[w_{i}\cdot\pi(x_{i})]$ (1) subject to
$\displaystyle\operatorname*{\mathbb{E}}_{{\cal D}}[\pi(x)]\leqslant\alpha$

Learning plays a central role in these problems since the optimal solution is
to first predict the expected welfare improvement
$\operatorname*{\mathbb{E}}[w\mid x]$ and then allocate positive decisions to
the top $\alpha$ fraction of units,
$\pi_{*}(x)=\mathbf{1}\\{\operatorname*{\mathbb{E}}[w\mid x]>t(\alpha)\\}$,
where $t(\alpha)$ is some threshold. In practice,
$\operatorname*{\mathbb{E}}[w\mid x]$ is of course not known and we
approximate the solution by finding a predictor $f$ such that
$f(x)\approx\operatorname*{\mathbb{E}}[w\mid x]$.

#### The Prediction-Access Ratio

We formalize the relative value of prediction through a technical notion we
call the _prediction-access ratio_. Put simply, this is the ratio of the
marginal improvement in social welfare that comes from improving the predictor
$f$, and the improvement achieved by keeping prediction fixed and expanding
access.

$\displaystyle\emph{\text{Prediction Access Ratio}}=\frac{\emph{\text{Marginal
Improvement from Expanding Access}}}{\emph{\text{Marginal Improvement from
Improving Prediction}}}$

The reader can think of the marginal improvement from prediction as the
increase in the objective function,
$\operatorname*{\mathbb{E}}[w_{i}\pi(x_{i})]$, that comes from finding a
predictor with smaller error,
$\operatorname*{\mathbb{E}}(w_{i}-f(x_{i}))^{2}$. On the other hand, the
improvement from expanding access corresponds to the change in the optimal
value of $\operatorname*{\mathbb{E}}[w_{i}\pi(x_{i})]$ that comes from
increasing $\alpha$ in the constraint
$\operatorname*{\mathbb{E}}[\pi(x_{i})]\leqslant\alpha$ being able to assign
goods or interventions to more people.

Calculating this ratio is a fundamental step in deciding which system changes
are (locally) the most cost-effective. In particular, to decide whether small
improvements in access or prediction are more effective, we simply calculate
the following cost benefit ratio:

$\displaystyle\underbrace{\frac{\emph{\text{Marginal Improvement from
Expanding Access}}}{\emph{\text{Marginal Improvement from Improving
Prediction}}}}_{\emph{\text{Prediction Access
Ratio}}}\times\frac{\emph{\text{Marginal Cost of Improving
Prediction}}}{\emph{\text{Marginal Cost of Expanding Access}}}.$ (2)

The decision whether to expand access or improve prediction hinges on whether
this expression is smaller or larger than 1.

While costs are relatively simple to calculate across different settings
(e.g., it costs $y$ dollars to hire an extra teacher and expand access to
tutoring), the prediction access ratio is more subtle and requires
counterfactual analysis (e.g., what would the world look like if my decisions
were slightly better versus if I could just treat more people?).

The main technical contribution of our work is to calculate this ratio in the
context of workhorse statistical models that are commonly used amongst
quantitative social scientists. We start by stating our main result for the
case where the effects of interventions are real-valued (e.g., increases in
life expectancy from receiving a hip replacement).

######  Theorem 1.1 (Informal).

Assume that welfare improvements follow a linear regression model where $w$ is
real-valued and normally distributed. If the predictor $f$ explains a
$\gamma_{s}^{2}$ fraction of the variance in outcomes $w$, and at most an
$\alpha$ fraction of the population can be intervened on, then the prediction
access ratio is equal to:

$\displaystyle\frac{\gamma_{s}}{\alpha}.$

Essentially, the theorem states that if resources are very scarce in the sense
that $\alpha$ is very small, and the predictor explains a non-trivial fraction
of the variance (say $1\%$) then the relative value of prediction is _small_ :
The gains in social welfare that arise from expanding access far outweigh the
gains that arise from improving prediction.111Note that explaining $1\%$ of
the variance means $\gamma_{s}^{2}=.01$ and $\gamma_{s}\geqslant 1/10$. Simple
predictors of life outcomes that use basic demographic features typically
explain at least a single digit fraction of the variance [Salganik et al.,
2020]. Resources are typically (but not always) much more heavily constrained,
and hence we think of $\alpha$ as small relative to $\gamma_{s}$. See Section
2 for further discussion. In particular, as long as the costs of expanding
access are not $1/\alpha$ times larger than those of collecting more data or
more features, then the cost-efficient way of making progress is to focus
efforts on treating more people.

Another way to interpret this result is to plug in the value of the prediction
access ratio into the cost-benefit analysis from Equation 2. A direct
corollary of this first theorem is that as long as

$\displaystyle\sqrt{\emph{\text{Current Variance
Explained}}}\geqslant\frac{\emph{\text{Marginal Cost of Expanding
Access}}}{\emph{\text{Marginal Cost of Expanding
Prediction}}}\times\emph{\text{Current Level of Access}}$

then the expression from Equation 2 is greater than 1, implying that the
relative value of prediction is small and that expanding access is locally
optimal. As per the previous discussion, this also constitutes a sufficient
condition for a predictor to be “good enough” for algorithmic decision making:
From a welfare perspective, it is efficient to leave the predictor as is and
focus on other aspects of the broader system.

To get a better sense of how these insights extend to other settings, we also
calculate the prediction access ratio for problems where welfare improvements
are discrete (e.g., changes in employment status or high school graduation
outcomes), rather than real valued.

######  Theorem 1.2 (Informal).

Assume welfare improvements follow a probit regression model where $w$ is
binary $w=\mathbf{1}\\{z>0\\}$, and $z$ is a real valued and normally
distributed score. If the predictor $f$ explains a $\gamma_{s}^{2}$ fraction
of the variance in $z$, and at most an $\alpha$ fraction of the population can
be intervened on, then the prediction access ratio is equal to

$\displaystyle\frac{\gamma_{t}}{\alpha^{1/\gamma_{t}^{2}}}$

where $\gamma_{t}^{2}=1-\gamma_{s}^{2}$ is the fraction of unexplained
variance in the underlying score $z$.

Since $1/\gamma_{t}^{2}>1$ for all $\gamma_{s}\in(0,1)$, the prediction access
ratio is almost always _larger_ in this discrete case than in the previous,
real-valued setting. Hence, the relative value of prediction is smaller and
one should be more willing to expand access vis-à-vis improving prediction. As
before, one can similarly factor costs into the equation, and again invert the
bound to identify simple conditions under which it is cost-efficient to expand
access vs improve prediction, or vice versa (see Equation 20 in Section 4).

###  1.2 Implications

At a high level, our main finding is that if a predictor explains even a small
fraction of the variance in outcomes and resources are significantly
constrained, the benefits of expanding access far outweigh the welfare
benefits induced by improving prediction.

We believe that these results regarding the relative value of prediction are
counter-narrative, if not quite counter-intuitive. It makes sense that if
interventions have mostly positive effects, we are better off intervening on
two people, rather than painstakingly improving prediction to identify the
single person who will benefit the most from an intervention. While prediction
is a means to an end, expanding access is an end in and of itself.

Crucially, these insights regarding the limits to prediction hold even in this
highly optimistic setting where prediction problem is _well-specified_ and
welfare improvements $w_{i}$ are directly _learnable_.222By well-specified, we
mean that that $w=f_{*}(x)$ for $f_{*}$ within some know class of models
$\mathcal{{\cal F}}$. Furthermore, $f_{*}$ is efficiently learnable in the
sense that there exist algorithms find predictors which converge to $f_{*}$ as
the number of samples grows. This not only requires strong representational
assumptions over your class of predictors, but also strong causal
identifiability conditions on the data distribution, see Section 5. In
practice, the variables we predict (e.g., pneumonia risk) are proxies for the
true welfare improvement we care about (e.g., treatment effect of the Covid
vaccine). The relative value of prediction is likely even smaller if our
prediction targets are misspecified.

Recent advances in machine learning have been inspiring and will hopefully
yield progress in a wide range of domains. However, the goal of this research
is try and understand: _to what extent is prediction really the highest order
bit in algorithmic decision making?_ We show that, at least in the context of
various workhorse models commonly used by practitioners (linear and probit
regression), once we’ve identified a reasonable prediction function, any
further improvements in accuracy are more of a second order concern.
Structural improvements like expanding access have significantly larger “bang
for buck” than the efficiency gains achieved from building a better prediction
system.

Note that neither one of these improvements comes for free. While expanding
access is expensive, so is improving prediction. In particular, the salient
way to improve a predictor of social outcomes is to collect more features for
the people in your population (i.e, perform additional in-person surveys,
medical tests) rather than changing the algorithm, or spending money on
additional compute.

Lastly, given the lack of previous work in this area, in this paper we have
opted to provide sharp answers regarding the relative value of prediction in
simple, yet foundational, statistical models. We view this as a first step
towards a more general theory of the connections between prediction systems
and social welfare. And, we hope to see future work that analyzes quantities
like the prediction access ratio under more general assumptions on the
underlying population.

#### Paper Organization.

In Section 2, we discuss related work and highlight how various examples of
real-world algorithmic decision making systems fit into the formalism we
develop. Then, in Section 3 we present our analysis of the prediction access
ratio for the case where welfare improvements are linear. And, in Section 4 we
present the analogous results for the discrete case. We close with some brief
remarks in Section 5

##  2 Motivating Applications and Related Work

Our work lies at the intersection of various threads of research from computer
science, economics, and related fields that aim to use statistical learning
techniques to inform decision making. We briefly discuss connections to some
of the most relevant technical scholarship and list examples from the applied
literature that motivate our setup.

#### Economics

Recently, there has been significant excitement amongst economists to
incorporate modern tools from machine learning into the traditional
econometric toolbox. Influential work by Kleinberg et al. [2015], coins the
term _prediction policy problems_ to refer to policy questions, which do not
directly require causal inference, and can be solved via pure prediction
techniques. This framing has led to several impactful analyses of problems in
health policy [Obermeyer et al., 2019], legal decision making [Kleinberg et
al., 2018], and hiring [Chalfin et al., 2016]. A parallel line of work by
Susan Athey and collaborators [Athey, 2017, 2018, Athey and Imbens, 2019,
Athey and Wager, 2021] aims to establish further connections between machine
learning, causality, and applied policy problems. Our work contributes to this
growing agenda by introducing a formal framework studying how improvements in
prediction compare to other structural avenues of improving welfare.

On the methods side, Bhattacharya and Dupas [2012] study the design of optimal
targeting mechanisms under budget constraints. They provide a complementary
analysis regarding the estimation of optimal decision rules under finite
samples, both in parametric and nonparametric settings. Manski [2004] and
Kitagawa and Tetenov [2018] investigate statistical questions related to
interventions targeting from a minimax estimation perspective.

#### Computer Science

The statistical targeting problem we consider can be viewed as an offline
version of problems studied in the online learning and contextual bandits
literature. In one version of this formalism, at every time step, a decision
maker sees features describing a unit, makes a binary decision, and observes a
reward (welfare improvement) for those units that were intervened on. Agrawal
and Devanur [2016] and Slivkins et al. [2023] this problem under knapsack
(resource) constraints, where the goal is to design algorithms that have low
regret with respect to some comparator class. These papers treat the design
parameters (resource constraints) as fixed, whereas we view them as a design
decision. Dudík et al. [2011] study how to estimate the value of a particular
decision making policy using offline data, rather than computing the optimal
policy online. Bertsimas et al. [2019] examine algorithms that yield
interpretable decision making policies.

Lastly, Liu et al. [2023] analyze the extent to which accurate predictions of
future outcomes can help a decision maker looking to choose from multiple
different interventions. Relative to their work, we consider a simpler setting
where there is just one treatment, the prediction task is well-specified, and
there are a limited number of people who may be intervened on.

###  2.1 Example Applications

Before moving on to formally presenting our main results, we highlight several
application domains that motivate our research and that we believe broadly
fall into the class of resource allocation problems outlined in Equation 1.

The following list of examples is by no means meant to be exhaustive, but
rather to convey the wide range of programs that follow the paradigm outlined
in the introduction. There is a single good or intervention to be allocated,
predictions are used to figure out which units would experience the largest
welfare improvements if acted upon, and the decision maker allocates decisions
to the top fraction.

#### Education

Over half of US public schools deploy _early warning systems_ [U.S Department
of Education, 2016]. These are tools that predict students’ likelihood of on-
time high school graduation, in order to determine which students should be
prioritized to receive additional counseling and interventions. In these
settings, on-time graduation is a proxy variable for the treatment effect
(welfare improvement) of receiving additional school resources.

Other decision problems in education following this broad pattern include:
predicting teacher value added in order to use limited school funds most
efficiently [Chalfin et al., 2016] (the interventions here are hiring
decisions), and predicting youth gun violence to allocate limited spots in
mentoring programs [Rockoff et al., 2011].

#### Healthcare

The use of individual risk predictors to determine treatment effects and
prioritize patients for interventions is ubiquitous throughout healthcare. In
Israel, one of the major public health agencies regularly predicts outcomes
such as COVID-19 mortality risk [Barda et al., 2020] or the likelihood of
hepatitis C [Leventer-Roberts et al., 2022], to prioritize patients for
vaccines or other medications. In motivating prediction policy problems,
Kleinberg et al. [2015] point out how ML predictions could be used to reliably
identify the riskiest patients, in order to improve the allocation of
expensive surgical procedures like hip replacements. Bhattacharya and Dupas
[2012] consider the task of predicting the prevalence of malaria in order to
distribute bug nets amongst households in Kenya. In some of these cases,
resources are sigificantly constrained, especially during the initial rollout
of the program [UNICEF, 2022].

#### Government

The 1993 Unemployment Compensation Amendments Act _requires_ that U.S. states
use profiling tools to predict the likelihood someone will remain unemployed
after exhausting regular benefits [Sen. Moynihan, 1993] in order to decide who
will receive additional job training resources. Aiken et al. [2022] study the
possibility of predicting poverty using satellite imagery in order to target
cash transfers to the poorest members of society. Chalfin et al. [2016] study
how algorithms can be used to predict which are the best police officers as a
means to guide hiring decisions and efficiently make use of human capital.
Similarly, Black et al. [2022] study questions of fairness and efficiency in
using algorithmic predictions to target IRS audits. Researchers have also
studied the use of machine learning to efficiently target building safety
inspections [Johnson et al., 2023, Hino et al., 2018, Glaeser et al., 2016].

##  3 Linear Regression Model & Real Valued Outcomes

In this section, we present our first set of main results analyzing the
prediction-access ratio for the case where welfare improvements follow a
linear regression model.

Linear regression is the workhorse method of analysis amongst economists,
sociologists and other quantitative social scientists. It has been applied,
with varying degrees of success [Freedman, 1999], to infer causal effects
(welfare improvements) in consequential domains such as education [Angrist and
Lavy, 1999, Yule, 1899] and public health [Chandler et al., 2011].
Furthermore, amongst theoreticians, linear models are the _drosophilia_ of
formal inquiry into more complex mathematical questions. According to Pearl,
“many concepts and phenomena in causal analysis were first detected,
quantified, and exemplified in linear structural equation models before they
were understood in full generality and applied to nonparametric problems”
[Pearl, 2013]. As such, they are a natural starting point to study the
prediction access ratio.

###  3.1 Model Definition and Technical Preliminaries

#### Model Definition.

Throughout this section, we assume data satisfy the following model

######  Definition 3.1 (Linear Regression Model).

We say that welfare improvements follow a linear regression model if

$\displaystyle w_{i}=\langle x_{i},\;\beta\rangle+\mu\quad\text{ where
}x_{i}\sim{\cal N}(0,I),$ (3)

and $\beta\in\mathbb{R}^{d}$ is a vector of unknown coefficients. Here,
$\mu=\operatorname*{\mathbb{E}}[w_{i}]$ is the average welfare improvement and
$\lVert\beta\rVert_{2}^{2}=\operatorname*{\mathbb{E}}[(w_{i}-\mu)^{2}]$
captures the heterogeneity in outcomes.333Since we can always whiten the
covariates, the restriction that $x_{i}\sim{\cal N}(0,I)$ is purely for
notational convenience and comes with no further loss in generality in this
linear, Gaussian setting. In particular, if $x\sim{\cal N}(0,\Sigma)$, we get
the same model by replacing $\beta$ with $\Sigma^{1/2}\beta$ since if
$x\sim{\cal N}(0,\Sigma)$ then $\langle x,\beta\rangle\stackrel{{\scriptstyle
d}}{{=}}\langle x^{\prime},\beta^{\prime}\rangle$ where $x^{\prime}\sim{\cal
N}(0,I)$ and $\beta^{\prime}=\Sigma^{1/2}\beta.$

While outcomes $w_{i}$ are deterministic functions of $x_{i}$, the social
planner does not observe the full vector of features, but rather only a
subset. In particular, we assume that features $x$ are partitioned into
$x=(x_{s},x_{t})\in\mathcal{X}_{s}\times\mathcal{X}_{t}$: a set of observed
features $x_{s}$ and unobserved features $x_{t}$. For example, the impacts of
educational interventions on the likelihood of on-time graduation are the
function of many variables. Some of these variables (e.g., student
demographics, test scores, attendance rate) are observed, and some are
typically unobserved (e.g., level of at-home instruction and parental
support).

Using the available data, the social planner aims to maximize average welfare,
subject to a resource constraint that at most an $\alpha$ fraction of the
population can be treated. We formally define the planner’s targeting problem
below:

######  Definition 3.2 (Planner’s Targeting Problem).

Given access to the observable features $x_{s}$, the planner solves the
following optimization problem:

$\displaystyle\max_{\pi\in\\{\mathcal{X}_{s}\rightarrow\\{0,1\\}\\}}\quad$
$\displaystyle\operatorname*{\mathbb{E}}_{(x_{i,s},w_{i})\sim{\cal
D}}[w_{i}\cdot\pi(x_{i,s})]$ (4) subject to
$\displaystyle\operatorname*{\mathbb{E}}_{\cal
D}[\pi(x_{i,s})]\leqslant\alpha.$

In this regression setting, we assume that given the partition of features
into observables and unobservables,

$\displaystyle w_{i}=\langle x_{i},\;\beta\rangle+\mu=\underbrace{\langle
x_{i,s},\;\beta_{s}\rangle+\mu}_{\emph{\text{Observable}}}+\underbrace{\langle
x_{i,t},\;\beta_{t}\rangle}_{\emph{\text{Unobservable}}},$

the planner has enough data that they can learn the coefficients $\beta_{s}$,
corresponding to the observable components $x_{s}$ exactly. In practice, one
would estimate $\beta_{s}$ in finite samples through procedures like ordinary
least squares and find an estimate $\widehat{\beta_{s}}$ such that
$\lVert\beta_{s}-\widehat{\beta_{s}}\rVert_{2}\leqslant{\cal
O}(\sqrt{\mathrm{dim}(\beta_{s})/n})$.

However, for the class of problems we are interested, data typically come
administrative databases collected by some centralized government authority,
where the number of samples $n$ is typically much larger than the number of
features, $\dim(x_{s})$. For example, in the Wisconsin early warning system
studied in Perdomo et al. [2023], there are about 40 features and $n$ is over
300k (all public school students in Wisconsin). Given these relevant scales,
the salient axis for improving prediction in these settings is to collect more
features (e.g conduct more tests, increase $\dim(x_{s})$) rather than
collecting more samples, since finite sample errors are essentially
negligible. We reflect this reality in our model to streamline our
presentation.

#### Technical Preliminaries.

We adopt the following notation. Let,

$\displaystyle\phi(z)=\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{z^{2}}{2}\right)\text{
and }\Phi(t)=\int_{-\infty}^{t}\phi(z)dz,$

be the PDF and CDF for a standard Normal random variable, ${\cal N}(0,1)$.
Lastly, define
$\Phi^{-1}(\alpha)=\inf\\{t\in\mathbb{R}:\alpha\leqslant\Phi(t)\\}$ to be the
associated quantile function. The optimal assignment policy $\pi^{*}_{s}$ for
the planner’s targeting problem can be easily expressed in terms of these
quantities.

######  Lemma 3.3.

Assume $w_{i}$ satisfy the linear regression model (Definition 3.1) and that
$x=(x_{s},x_{t})$. The optimal assignment policy $\pi^{*}_{s}$ solving the
planner’s targeting problem (Definition 3.2) is equal to:

$\displaystyle\pi^{*}_{s}(x_{i,s})=\mathbf{1}\\{\langle
x_{i,s},\;\beta_{s}\rangle\geqslant\Phi^{-1}(1-\alpha)\lVert\beta_{s}\rVert_{2}\\}\cdot\mathbf{1}\\{\langle
x_{i,s},\;\beta_{s}\rangle+\mu\geqslant 0\\}.$ (5)

###### Proof.

In general, the optimal solution to the planner’s targeting problem is to
intervene on the top $\alpha$ fraction of the population, conditional on those
expected welfare effects being positive (see Proposition A.1):

$\displaystyle\pi^{*}_{s}(x_{i})=\mathbf{1}\\{E[w_{i}\mid
x_{s}]>F^{-1}_{s}(1-\alpha)\\}\cdot\mathbf{1}\\{E[w_{i}\mid x_{s}]>0\\}.$ (6)

Here, $F_{s}$ is the CDF of the random variable
$\operatorname*{\mathbb{E}}[w_{i}\mid X_{s}]$, and $F_{s}^{-1}$ is its
quantile function. In the linear model (Definition 3.1), both of these
functions have tractable expressions. Since,

$\displaystyle w_{i}=\langle x_{i,s},\;\beta_{s}\rangle+\langle
x_{i,t},\;\beta_{t}\rangle+\mu,$

where $\langle x_{i,s},\;\beta_{s}\rangle\sim{\cal
N}(0,\lVert\beta_{s}\rVert_{2}^{2})$ and $\langle
x_{i,t},\;\beta_{t}\rangle\sim{\cal N}(0,\lVert\beta_{t}\rVert_{2}^{2})$ are
independent, then:

$\displaystyle E[w_{i}\mid x_{i,s}]=\langle
x_{i,s},\;\beta_{s}\rangle+\mu,\text{ and
}F_{s}^{-1}(1-\alpha)=\Phi^{-1}(1-\alpha)\lVert\beta_{s}\rVert_{2}+\mu.$

The result follows from plugging these expressions into (6). ∎

The value $\operatorname*{\mathbb{E}}[w_{i}\pi^{*}_{s}(x_{i,s})]$ achieved by
the policy $\pi^{*}_{s}$ is intimately tied to the variance explained by the
observable features $x_{s}$. We say that the observable features $x_{s}$ have
an $r^{2}$ value of $\gamma_{s}^{2}$ if the associated predictor, $\langle
x_{s},\;\beta_{s}\rangle$, explains a $\gamma_{s}^{2}$ fraction of the
variance in the outcomes $w$.444Due to the tight correspondence between
features and predictors in this linear model, we will use the phrases, the
features (or predictor) have an $r^{2}$ value of $\gamma_{s}^{2}$
interchangeably to refer to the condition in Equation 7.

######  Definition 3.4 ($r^{2}$ \- Linear Regression).

For $w_{i}$ satisfying the linear regression model (Definition 3.1), we say
that observable features $x_{s}$ have an $r^{2}$ value of $\gamma^{2}_{s}$,
$r^{2}(x_{s})=\gamma^{2}_{s}\in[0,1]$, if

$\displaystyle r^{2}(x_{s})=1-\frac{\operatorname*{\mathbb{E}}(w-\langle
x_{i,s},\;\beta_{s}\rangle)^{2}}{\operatorname*{\mathbb{E}}(w_{i}-\mu)^{2}}=\frac{\lVert\beta_{s}\rVert_{2}^{2}}{\lVert\beta\rVert_{2}^{2}}=\gamma_{s}^{2}.$
(7)

Note that the predictor that uses all the available features $x_{s}=x$, has an
$r^{2}$ value of 1, while a model that uses no features has an $r^{2}$ value
of 0. With this notation, we can define the value of a policy: the overall
welfare improvement achieved as a function of the distribution of the $w_{i}$,
the level of access $\alpha$ and the variance explained by the observed
features $x_{i}$.

######  Proposition 3.5 (Value Function, Linear Regression).

For $w_{i}$ satisfying the linear regression model (Definition 3.1), define
$V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})$ to be,555We parametrize the value
function in terms of $\gamma_{s}$ instead of the set of observed features
$x_{s}$ since the value of the features in this model is exactly captured by
$\gamma_{s}$.

$\displaystyle
V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})=\max_{\pi\in\\{\mathcal{X}_{s}\rightarrow\\{0,1\\}\\}}\operatorname*{\mathbb{E}}_{(x_{i,s},w_{i})\sim{\cal
D}}[w_{i}\cdot\pi(x_{i,s})]\quad\mathrm{s.t}\quad$
$\displaystyle\operatorname*{\mathbb{E}}_{\cal
D}[\pi(x_{i,s})]\leqslant\alpha\text{ and }r^{2}(x_{s})=\gamma_{s}^{2},$ (8)

the value achieved by the optimal policy $\pi^{*}_{s}$ (5) that uses features
$x_{s}$ and has an associated $r^{2}$ value equal to $\gamma^{2}_{s}$. Then,
for $\alpha<1/2$ and $\lVert\beta\rVert_{2},\mu>0$,

$\displaystyle
V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})=\alpha\mu+\gamma_{s}\lVert\beta\rVert_{2}\phi(\Phi^{-1}(1-\alpha)),$
(9)

where $\phi(\cdot)$ and $\Phi^{-1}()$ are again the PDF and quantile functions
for a standard normal ${\cal N}(0,1)$.

In this linear setting, the value function for the optimal policy admits a
simple closed-form solution (Equation 9) and has a intuitive interpretation.
In particular, $V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})$ consists of two
terms. The first term, $\alpha\mu$ is exactly the value achieved by a random
assignment policy. For $w_{i}\sim{\cal N}(\mu,\lVert\beta\rVert_{2}^{2})$, if
you select who gets treated on the basis of a random coin toss,
$\pi_{\mathrm{rand}}(x_{i,s})\sim\mathrm{Ber}(\alpha)$, the expected welfare
is equal to
$\operatorname*{\mathbb{E}}[w_{i}\pi_{\mathrm{rand}}(x_{i,s})]=\operatorname*{\mathbb{E}}[w_{i}]\operatorname*{\mathbb{E}}[\pi_{\mathrm{rand}}(x_{i,s})]=\alpha\mu$.
666Here, $\mathrm{Ber}(\alpha)$ is a Bernoulli random variable with parameter
$\alpha$. Under $\pi_{\mathrm{rand}}$, each unit $i$ receives the good, or
intervention, independently with probability $\alpha$.

On the other hand, the second term in Equation 9 captures the value of
predictions that are better than random (and hence have $\gamma_{s}>0$).
Recall that for $w_{i}=\langle\beta,\;x_{i}\rangle$ and $x_{i}\sim{\cal
N}(0,I)$, the total variance in the outcomes is $\lVert\beta\rVert_{2}^{2}$
and the variance captured by the features is $\lVert\beta_{s}\rVert_{2}^{2}$
(since $\langle x_{i,s},\;\beta_{s}\rangle\sim{\cal
N}(0,\lVert\beta_{s}\rVert_{2}^{2})$. Therefore, the marginal value of using
prediction, versus random assignment, scales with the square root of the
variance explained,
$\lVert\beta_{s}\rVert_{2}=\gamma_{s}\lVert\beta\rVert_{2}$, and a quantity
that depends on the level of access: $\phi(\Phi^{-1}(1-\alpha))$.

As a final note before discussing our main result for this section, we pause
to point out that if there is very little variance in the outcome variable
(i.e., $\lVert\beta\rVert_{2}^{2}$ is small) then, random assignment (i.e.,
deciding allocations according to
$\pi_{\mathrm{rand}}(x_{i,s})\sim\mathrm{Ber}(\alpha)$) is near optimal.
Statistical targeting, above and beyond simple random allocations, only makes
sense if there is significant variance in the outcomes $w_{i}$.

######  Remark 3.6.

Let
$V_{\mathrm{random}}(\alpha)=\operatorname*{\mathbb{E}}[w_{i}\pi_{\mathrm{rand}}(x_{i,s})]$
for $\pi_{\mathrm{rand}}(x_{i,s})=\mathrm{Ber}(\alpha)$. Then, for
$\alpha,\mu,\lVert\beta\rVert_{2}>0$,

$\displaystyle\frac{V_{\mathrm{random}}(\alpha)}{V_{*}^{\mathrm{lin}}(\alpha,1)}=\frac{1}{1+\frac{\lVert\beta\rVert_{2}}{\mu}\alpha^{-1}\phi(\Phi^{-1}(1-\alpha))},$

where $V_{*}^{\mathrm{lin}}(\alpha,1)$ Equation 9) is the value of the policy
$\pi^{*}(x)$ with $r^{2}(x)=1$ that observes all features.

The result follows directly from plugging in the expressions from Proposition
3.5. The main takeaway from this calculation is that, as
$\lVert\beta\rVert_{2}/\mu\rightarrow 0$, then
$V_{\mathrm{random}}(\alpha)/V_{*}^{\mathrm{lin}}(\alpha,1)\rightarrow 1$ and
$\pi_{\mathrm{rand}}$ is optimal. While somewhat trite, it is nevertheless an
important, common-sense sanity check. Prediction-enabled targeting only makes
sense if the variance is large relative to the mean. Since the goal of our
work is to study the relative value of prediction, in settings where
prediction makes sense to begin with, we will assume for the remainder that
$\lVert\beta\rVert_{2}/\mu$ is not too small.

###  3.2 The Prediction Access Ratio for Linear Regression

#### Defining Policy Levers.

In the context of the linear regression model, various policy levers such as
improving prediction and expanding access have simple, formal counterparts.

  * –

_Improving Prediction_ : Optimizing prediction in this setting equates to
enlarging the set of measured features. This yields a new partition of
observed and unobserved covariates
$(x_{s},x_{t})\rightarrow(x_{s^{\prime}},x_{t^{\prime}})$ such that if
$r^{2}(x_{s})=\gamma_{s}$ then,
$r^{2}(x_{s^{\prime}})=r^{2}(x_{s})+\Delta_{r^{2}}$ for some
$\Delta_{r^{2}}>0$.

As per our notation from Equation 8, the relevant improvement in welfare is
equal to:

$\displaystyle
V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s}+\Delta_{r^{2}})-V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})\quad\emph{\text{(Marginal
Improvement from Improving Prediction})}.$

  * –

_Expanding Access_. This corresponds to keeping the current policy
$\pi^{*}_{s}$ fixed and slackening the resource constraint $\alpha$ to
$\alpha+\Delta_{\alpha}$. The increase in average welfare is equal to

$\displaystyle
V_{*}^{\mathrm{lin}}(\alpha+\Delta_{\alpha},\gamma_{s})-V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})\quad\emph{\text{(Marginal
Improvement from Expanding Access})}.$

Given current system parameters $(\alpha,\gamma_{s})$, and proposed
improvements $\Delta_{r^{2}},\Delta_{\alpha}\in(0,1)$, the prediction-access
ratio determines the relative impact of these changes on overall welfare:

$\displaystyle\frac{V_{*}^{\mathrm{lin}}(\alpha+\Delta_{\alpha},\gamma_{s})-V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})}{V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s}+\Delta_{r^{2}})-V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})}.$
(10)

Values of the ratio larger than 1 indicate that an $\Delta_{\alpha}$ increase
in access yields a larger increase in welfare than an $\Delta_{r^{2}}$
improvement in prediction. The reverse is true if the ratio is smaller than 1.

The following theorem is the main result of this section, effectively
identifying this ratio (up to a small constant) for the linear regression
model.

######  Theorem 3.7 (Prediction-Access Ratio, Linear Regression).

Assume that $w_{i}$ satisfy the linear regression model (Definition 3.1) with
$\lVert\beta\rVert_{2},\mu>0$. For any $\gamma_{s},\Delta_{r^{2}}\in(0,1)$ and
$\Delta_{\alpha}$ satisfying
$\alpha+\Delta_{\alpha}<.05,\Delta_{\alpha}\leqslant 4\alpha$, the following
inequalities hold:777In this theorem statement, we assume bounds on $\alpha$
to simplify the resulting analytic expressions. From our analysis in Section
A, we can prove a more general result that holds for larger values of
$\alpha$, yet the resulting expressions are significantly less interpretable
due to the nature of the quantities involved. Likewise, the constants
appearing the bounds can be improved as the expense of assuming tighter bounds
on $\alpha,\Delta_{\alpha}$.

$\displaystyle\frac{1}{4}\cdot\frac{1}{\alpha}\left(\frac{\mu}{\lVert\beta\rVert_{2}\Phi^{-1}(1-\alpha)}+\gamma_{s}\right)\frac{\Delta_{\alpha}}{\Delta_{r^{2}}}\leqslant\frac{V_{*}^{\mathrm{lin}}(\alpha+\Delta_{\alpha},\gamma_{s})-V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})}{V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s}+\Delta_{r^{2}})-V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})}\leqslant\frac{1}{\alpha}\left(\frac{\mu}{\lVert\beta\rVert_{2}\Phi^{-1}(1-\alpha)}+\gamma_{s}\right)\frac{\Delta_{\alpha}}{\Delta_{r^{2}}}.$

###### Proof Sketch.

The proof is a direct calculation using Taylor’s theorem and facts about
Gaussians. In particular, from Taylor’s theorem, we know that

$\displaystyle
V_{*}^{\mathrm{lin}}(\alpha+\Delta_{\alpha},\gamma_{s})-V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})$
$\displaystyle=\frac{\partial}{\partial\alpha}V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})\cdot\Delta_{\alpha}+{\cal
O}(\Delta_{\alpha}^{2})$ $\displaystyle
V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s}+\Delta_{r^{2}})-V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})$
$\displaystyle=\frac{\partial}{\partial\gamma_{s}}V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})\cdot\Delta_{r^{2}}+{\cal
O}(\Delta^{2}_{r^{2}}).$

Recall from Proposition 3.5 that
$V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})=\alpha\mu+\gamma_{s}\cdot\lVert\beta\rVert_{2}\phi(\Phi^{-1}(1-\alpha))$.
Hence, we can directly calculate,

$\displaystyle\frac{\partial}{\partial\alpha}V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})=\mu+\gamma_{s}\lVert\beta\rVert_{2}\Phi^{-1}(1-\alpha)\text{
and
}\frac{\partial}{\partial\gamma_{s}}V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})=\lVert\beta\rVert_{2}\phi(\Phi^{-1}(1-\alpha)).$

The key insight is that $\phi(\Phi^{-1}(1-\alpha))$ is well-approximated by
$\alpha\Phi^{-1}(1-\alpha)$ for small values of $\alpha$. Therefore, local
changes in $\gamma_{s}$ are a factor of $\alpha$ smaller than local changes in
$\alpha$. More specifically,

$\displaystyle
V_{*}^{\mathrm{lin}}(\alpha+\Delta_{\alpha},\gamma_{s})-V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})$
$\displaystyle\approx\Delta_{\alpha}(\mu+\gamma_{s}\lVert\beta\rVert_{2}\Phi^{-1}(1-\alpha))=\widetilde{\Theta}(1)$
$\displaystyle
V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s}+\Delta_{r^{2}})-V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})$
$\displaystyle\approx\Delta_{r^{2}}\lVert\beta\rVert_{2}\Phi^{-1}(1-\alpha)\alpha=\widetilde{\Theta}(\alpha).$
(11)

The remainder of the argument deals with making the Taylor approximations
precise and controlling the quadratic terms. ∎

#### Discussion.

The main message of this theorem is that, if resources are scarce in the sense
that $\alpha$ is small, then the local improvements induced by expanding
access are far larger than the improvements in welfare that come from better
targeting.

More specifically, if we fix $\Delta_{\alpha}=\Delta_{r^{2}}$ and assume
$\gamma_{s}$ to be bounded below by a constant (say 5%), the prediction access
ratio is order $1/\alpha$.888Apart from the $\alpha^{-1}$ term in the
prediction access ratio, there is a second term in the expression,
$\Phi^{-1}(1-\alpha)$ that depends on $\alpha$. The quantile function
$\Phi^{-1}(1-\alpha)$ is $\Theta(\sqrt{\log(1/\alpha)})$ for small values of
$\alpha$ (see Proposition A.7). Because this is lower order, the behavior of
the ratio is still dominated by $1/\alpha$. This is unbounded as we send
$\alpha\rightarrow 0$, hence the amount we should be willing to pay to expand
access _increases_ the smaller $\alpha$ is. Said otherwise, the relative value
of prediction in these targeting problems _decreases_ with the level of
scarcity.

Recall from the introduction that to decide which policy lever makes sense, we
only need to factor costs into the equation. Here, we encourage the reader to
think of costs in a broad sense. The costs of improving prediction are
monetary (e.g., compute bills, labor) as well as _social_ (e.g., the privacy
costs of people releasing personal information to a central authority, or
subjecting individuals to a means test). A similar comment applies to the
costs of other policy levers. However, for the sake of modeling, we can
imagine functions $C_{\alpha}$ and $C_{r^{2}}$ from
$[0,1]\rightarrow\mathbb{R}_{\geqslant 0}$ that give costs numeric values. The
decision to expand access vs improve prediction hinges on whether the cost-
benefit ratio, formally defined for this linear regression model as,

$\displaystyle\frac{V_{*}^{\mathrm{lin}}(\alpha+\Delta_{\alpha},\gamma_{s})-V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})}{V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s}+\Delta_{r^{2}})-V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})}\times\frac{C_{r^{2}}(\Delta_{r^{2}})}{C_{\alpha}(\Delta_{\alpha})},$
(12)

is larger than 1. Theorem 3.7 essentially states that as long as
$C_{\alpha}(\Delta_{\alpha})<\gamma_{s}/\alpha C_{r^{2}}(\Delta_{r^{2}})$,
expanding access is the cost-efficient policy decision.

To see this in more detail, we can reinterpret the result as establishing a
_threshold_ for when a set of features is sufficiently “good” for targeting.
As long as,

$\displaystyle\gamma_{s}\gtrsim\frac{\Delta_{r^{2}}C_{\alpha}(\Delta_{\alpha})}{\Delta_{\alpha}C_{r^{2}}(\Delta_{r^{2}})}\cdot\alpha-\frac{\mu}{\lVert\beta\rVert_{2}\Phi^{-1}(1-\alpha)},$
(13)

the cost-benefit ratio from Equation 12 is greater that 1 and expanding access
makes economic sense.999We say $a\gtrsim b$ if $a\geqslant cb$ for some
universal constant $c$. Otherwise, if the inequality above holds in the
opposite direction, the focus should be on building a better predictor (since
the bounds on the prediction access ratio are essentially
tight).101010Equation 13 formalizes the condition previously stated informally
in the introduction regarding when a predictor is good enough. As per Remark
3.6, we think of $\lVert\beta\rVert_{2}/\mu$ as large. Hence, we simplified
the initial exposition of the equation accordingly by setting the second term
on the right hand side to zero.

#### Visualization

We examine this threshold visually in Figure 1. In particular, in each plot we
illustrate the cost benefit ratio (Equation 12), for various choices of the
ratio $C_{r^{2}}(\Delta_{r^{2}})/C_{\alpha}(\Delta_{\alpha})$ where in each
case $\Delta_{\alpha}=\Delta_{r^{2}}=.01$.

As predicted by our theory (Theorem 3.7 and Equation 13), we see that for
small values of $\alpha$ the threshold at which one is indifferent between
expanding access vs improving prediction is of the form
$\gamma_{s}\propto\alpha$. That is, given any pairs of level of access
$\alpha$ and prediction $\gamma_{s}$, the cost benefit ratio is above 1 if
$\alpha\lesssim\gamma_{s}$ and below 1 if $\alpha\gtrsim\gamma_{s}$. The exact
constant depends on the relative costs of prediction and expanding access. As
per Equation 13, changing the relative costs only changes the slope of the
line.

A different way to interpret this finding is that in the linear regression
model, the optimal values of $(\alpha,\gamma_{s})$ go “hand in hand”. That is,
if a predictor explains a $\gamma_{s}^{2}$ fraction of the the variance, then
the _efficient_ level of access is to set $\alpha\propto\gamma_{s}$: One
should increase access until it matches the (square root of) the explained
variance. This in effect establishes priorities for how a decision making
system should be built out.

Figure 1: Visualization of the cost benefit ratio, the prediction access ratio
times the ratio of marginal costs, for the linear regression model with
$\mu=1,\lVert\beta\rVert_{2}=10$. In the left plot, the costs of expanding
access are 4 times that of improving prediction, and on the right plot we they
are only twice as large. For each value of $\alpha$ (x-axis) and $\gamma_{s}$
(y-axis), we use our closed form expression for $V_{*}^{\mathrm{lin}}$ from
Proposition 3.5 to compute the cost benefit ratio (Equation 12) numerically
and display its value, clipped to the interval [1/2, 2], via the color bar.
The black dotted line indicates the level set of points for which the cost
benefit ratio is equal to 1. For points $(\alpha,\gamma_{s})$ below this line,
the ratio is less than 1, implying that prediction is the cost efficient way
of improving welfare. For points above the line, expanding access is cost
efficient.

#### The Relative Value of Improving Quality

So far, we have focused on the relative impacts of prediction and access on
welfare. However, there are other policy levers one might experiment with, for
instance, improving the quality of the allocated goods. One way to formalize
this, in this regression model it to consider increasing
$\mu=\operatorname*{\mathbb{E}}[w]$, the average welfare improvement.

Recall from Proposition 3.5 that the value function of the optimal policy is
equal to:

$\displaystyle\mu\alpha+\gamma_{s}\lVert\beta\rVert_{2}\phi(\Phi^{-1}(1-\alpha)).$

Since the value function is linear in the average quality $\mu$, increasing
$\mu$ to $\mu+\Delta_{\mu}$ increases the value function by an additive factor
$\Delta_{\mu}\alpha$. Hence, in this regression model, improvements in mean
outcomes yield improvements in welfare that are on the same order as
improvements in prediction. Both are $\widetilde{\Theta}(\alpha)$ (see
Equation 11), and significantly smaller than improvements in access, which are
$\widetilde{\Theta}(1)$.

#### Local vs Global Decision Making

The value of the prediction access ratio is that it helps guide which kind of
_local_ improvement is most effective. That is, it answers questions of the
form: Given that my current system treats an $\alpha$ fraction of the
population and explains a $\gamma_{s}^{2}$ fraction of the variance in
treatment effects, is it better to expand access by 1% or improve prediction
by 1%? This is motivated by the fact that that there is often significant
inertia in the overall design of algorithmic decision making systems. Large
government-run programs, like developing an early warning system or a vaccine
rollout come involve large administrative components and one cannot always
“start from scratch”. Pragmatically speaking, only local changes are viable in
these large scale endeavors.

Evaluating the impact of local changes is also more mathematically
interesting. For various problems, it is not hard to read off the globally
optimal values of $\alpha$ and $\gamma_{s}$. For example in the regression
model, we simply set $\gamma_{s}=1$ and $\alpha=\mathrm{Pr}[w_{i}\geqslant
0]$.

##  4 Probit Regression Model & Discrete Outcomes

Depending on the way in which we measure outcomes, welfare improvements and
treatment effects are often binary (e.g., graduating from high school on-time)
rather than real valued as the linear regression setting analyzed previously.

Therefore, to gain a more complete understanding of the relative value of
prediction in targeting problems, in this section we study the prediction
access in the context of a discrete model for outcomes: probit regression.
Like linear regression, probit regression is one of the most popular
statistical models used in the quantitative social sciences. On a technical
level, it belongs to the class of generalized linear models. These apply a
nonlinearity (link function) to the real-valued outputs of a regression,
$\langle x,\beta\rangle\in\mathbb{R}$, in order to transform them into a
different space (e.g., probabilities in [0,1]).111111The other popular model
in this class is logistic regression. Both probit and linear regression
transform the real valued outputs of a regression model into a score in
$[0,1]$ (a probability). The exact transformation is technically different,
but morally they tend to provide similar “bottom-line” insights when applied
in practice [Stock et al., 2003, Scott Long, 1997]. We focus on the probit
model since we found it simpler to analyze.

###  4.1 Model Definition and Technical Preliminaries

######  Definition 4.1.

We say that welfare improvements follow a probit regression model if

$\displaystyle w_{i}=\mathbf{1}\\{\langle
x_{i},\;\beta\rangle+\mu>0\\}\quad\text{ where }x_{i}\sim{\cal N}(0,I),$ (14)

where again $\beta\in\mathbb{R}^{d}$ is a vector of coefficients. Furthermore,
we denote by $b=\mathrm{Pr}[w_{i}>0]$ the base rate of positive welfare
improvements in the population.

As before, we assume that features $x$ are partitioned into observed and
unobserved components, $(x_{s},x_{t})$ and that the planner collects enough
data to learn the subset of coefficients $\beta_{s}$ exactly. In the model
outlined above, these parameters can be recovered in finite samples via convex
programming at similar $\sqrt{\dim(x_{s})/n}$ rates [Fahrmeir and Kaufmann,
1985]. Given the observable components $x_{s}$, the planner again solves the
targeting problem (Definition 3.2) where the data now follows the probit model
(Definition 4.1).

Due to the nonlinearity (thresholding) being applied, parameters like $\mu$
and $\lVert\beta\rVert_{2}$ in this setting no longer directly correspond to
natural quantities like mean and variance of $w_{i}$ as in the linear case.
Yet, the optimal policy for the probit case is conveniently the same as
before.

######  Lemma 4.2.

Assume $w_{i}$ satisfy the probit regression model (Definition 4.1) and that
$x=(x_{s},x_{t})$. The optimal assignment policy $\pi^{*}_{s}$ for the
planner’s targeting problem (Definition 3.2) is equal to:

$\displaystyle\pi^{*}_{s}(x_{i,s})=\mathbf{1}\\{\langle
x_{i,s},\beta_{s}\rangle\geqslant\Phi^{-1}(1-\alpha)\lVert\beta_{s}\rVert_{2}\\}.$
(15)

###### Proof.

Since $\operatorname*{\mathbb{E}}[w_{i}\mid x_{i,s}]$ is always greater than
0, the optimal policy is simply to treat the units with the highest values of
$\operatorname*{\mathbb{E}}[w_{i}\mid x_{i,s}]$. In this case,

$\displaystyle\operatorname*{\mathbb{E}}[w_{i}\mid
x_{i,s}]=\mathrm{Pr}[w_{i}=1\mid x_{i,s}]=\Phi(\mu+\langle
x_{i,s},\beta_{s}\rangle).$

Because $\Phi(z)$ is strictly monotonic in its argument, $z=\mu+\langle
x_{i,s},\beta_{s}\rangle$, the top $1-\alpha$ quantile for $\Phi(z)$ is the
same as the top $1-\alpha$ quantile for $z$ itself. ∎

Given the binary nature of the outcome variable, there is no standard, agreed-
upon measure for the coefficient of determination as in the continuous case,
with various “pseudo”-$r^{2}$ definitions proposed. However, we find it
convenient to deal with the same measure as before.

######  Definition 4.3 ($r^{2}$ \- Probit Regression).

Assume that $(w_{i},x_{i})$ satisfy the probit regression model (Definition
4.1). We say that the features $x_{s}$ have an $r^{2}$ value of
$\gamma^{2}_{s}$, $r^{2}(x_{s})=\gamma^{2}_{s}$, if

$\displaystyle r^{2}(x_{s})=1-\frac{\operatorname*{\mathbb{E}}(z_{i}-\langle
x_{i,s},\;\beta_{s}\rangle)^{2}}{\operatorname*{\mathbb{E}}(z_{i}-\mu)^{2}}=\frac{\lVert\beta_{s}\rVert_{2}^{2}}{\lVert\beta\rVert_{2}^{2}}=\gamma_{s}^{2}\in[0,1]$
(16)

for $z_{i}=\langle x_{i},\beta\rangle+\mu$ and
$w_{i}=\mathbf{1}\\{z_{i}>0\\}$.121212While our results are meant to be more
qualitative than quantitative, one could in principle still calculate this
$r^{2}$ statistic from data by first estimating $\beta_{s}$ and $\mu$ via
regression and then computing $\lVert\beta\rVert_{2}$ by solving the equation
$\mathrm{Pr}[w_{i}>0]=\Phi^{-1}(\mu\lVert\beta\rVert_{2}^{-1})$.

We parametrize the value function for the probit case again in terms of
$\gamma_{s}$ and $\alpha$.

######  Proposition 4.4.

For $w_{i}$ satisfying the probit regression model (Definition 3.1), let
$V_{*}^{\mathrm{pr}}(\alpha,\gamma_{s})$ be

$\displaystyle
V_{*}^{\mathrm{pr}}(\alpha,\gamma_{s})=\max_{\pi\in\\{\mathcal{X}_{s}\rightarrow\\{0,1\\}\\}}\operatorname*{\mathbb{E}}_{(x_{i,s},w_{i})\sim{\cal
D}}[w_{i}\cdot\pi(x_{i,s})]\quad\mathrm{s.t}\quad$
$\displaystyle\operatorname*{\mathbb{E}}_{\cal
D}[\pi(x_{i,s})]\leqslant\alpha\text{ and }r^{2}(x_{s})=\gamma_{s}^{2}$ (17)

the value achieved by the optimal policy $\pi^{*}_{s}$ (Lemma 4.2) that uses
features $x_{s}$ that have an $r^{2}$ value equal to $\gamma^{2}_{s}$
(Definition 4.3). Then,

$\displaystyle
V_{*}^{\mathrm{pr}}(\alpha,\gamma_{s})=\int_{\Phi^{-1}(1-\alpha)}^{\infty}\Phi\left(\frac{\gamma_{s}z_{s}+\mu\lVert\beta\rVert_{2}^{-1}}{\gamma_{t}}\right)\phi(z_{s})dz_{s}$
(18)

where $\gamma_{t}^{2}=1-\gamma_{s}^{2}$ is the fraction of unexplained
variance in the scores $z_{i}=\langle x_{i},\;\beta\rangle+\mu$.

The nonlinear nature of the probit model complicates calculations so that the
value functions no longer have simple expressions in terms of analytical
functions. Interestingly enough, while $V_{*}^{\mathrm{pr}}$ has no closed-
form solution, the prediction access ratio does.

###  4.2 The Prediction-Access Ratio for Probit Regression

We define policy levers for the probit model in a similar fashion as before.

  * –

_Improving Prediction_ : Expanding the set of measured features
$(x_{s},x_{t})\rightarrow(x_{s^{\prime}},x_{t^{\prime}})$ so that if
$r^{2}(x_{s})=\gamma_{s}^{2}$ then,
$r^{2}(x_{s^{\prime}})=r^{2}(x_{s})+\Delta_{r^{2}}=\gamma_{s^{\prime}}^{2}$
for some $\Delta_{r^{2}}>0$. Formally, this translates to:

$\displaystyle
V_{*}^{\mathrm{pr}}(\alpha,\gamma_{s}+\Delta_{r^{2}})-V_{*}^{\mathrm{pr}}(\alpha,\gamma_{s})\quad\emph{\text{(Marginal
Improvement from Improving Prediction})}.$

  * –

_Expanding Access_. Again corresponds to weakening the resource constraint
$\alpha$ to $\alpha^{\prime}=\alpha+\Delta_{\alpha}$. The change in welfare is
equal to:

$\displaystyle
V_{*}^{\mathrm{pr}}(\alpha+\Delta_{\alpha},\gamma_{s})-V_{*}^{\mathrm{pr}}(\alpha,\gamma_{s})\quad\emph{\text{(Marginal
Improvement from Expanding Access})}.$

######  Theorem 4.5 (Prediction-Access Ratio, Probit Regression).

For any $\gamma_{s}\in(0,1)$, $b=\mathrm{Pr}[w_{i}=1]<.1$, and constant
$\varepsilon\in(0,.1)$, if $\Delta_{\alpha}\leqslant\alpha$ the following
inequalities hold for values of $\alpha$ and $\Delta_{r^{2}}$ smaller than
some threshold t > 0,

$\displaystyle\frac{V_{*}^{\mathrm{pr}}(\alpha+\Delta_{\alpha},\gamma_{s})-V_{*}^{\mathrm{pr}}(\alpha,\gamma_{s})}{V_{*}^{\mathrm{pr}}(\alpha,\gamma_{s}+\Delta_{r^{2}})-V_{*}^{\mathrm{pr}}(\alpha,\gamma_{s})}\leqslant
3\cdot\gamma_{t}\cdot\frac{1}{b\Phi^{-1}(1-b)}\left(\frac{1}{\sqrt{2\pi}}\cdot\frac{1}{\alpha\Phi^{-1}(1-\alpha)}\right)^{1/\gamma_{t}^{2}\cdot(1+\varepsilon^{\prime})^{2}}\cdot\frac{\Delta_{\alpha}}{\Delta_{r^{2}}}$

where $\varepsilon^{\prime}=\varepsilon/(1-\varepsilon)$ and

$\displaystyle\frac{V_{*}^{\mathrm{pr}}(\alpha+\Delta_{\alpha},\gamma_{s})-V_{*}^{\mathrm{pr}}(\alpha,\gamma_{s})}{V_{*}^{\mathrm{pr}}(\alpha,\gamma_{s}+\Delta_{r^{2}})-V_{*}^{\mathrm{pr}}(\alpha,\gamma_{s})}\geqslant\frac{3}{10}\cdot\gamma_{t}\cdot\frac{1}{b\Phi^{-1}(1-b)}\left(\frac{1}{1.01\sqrt{2\pi}}\cdot\frac{1}{\alpha\Phi^{-1}(1-\alpha)}\right)^{1/\gamma_{t}^{2}\cdot(1-\varepsilon)^{2}}\cdot\frac{\Delta_{\alpha}}{\Delta_{r^{2}}}.$

Here, $\gamma_{t}^{2}=1-\gamma_{s}^{2}$ is again the fraction of unexplained
variance in the scores $z_{i}=\langle x_{i},\;\beta\rangle+\mu$.

#### Discussion.

Ignoring constants and lower order terms, we see that the prediction access
ratio is essentially

$\displaystyle\widetilde{\Theta}\left(\frac{\gamma_{t}}{b}\alpha^{-1/\gamma_{t}^{2}}\right)$

where we’ve used the fact that $\Phi^{-1}(1-c)$ is $\Theta(\sqrt{\log(1/c)})$.
Assuming $\alpha\ll\gamma_{s}$, one of the main takeaways from this theorem is
that the prediction access ratio in the probit case is significantly _larger_
than in the linear case. Since $1/\gamma_{t}^{2}>1$, the ratio behaves like
$\alpha^{-c}$ for some $c>1$ rather than $\alpha^{-1}$ as before.

Interestingly, this finding implies that the relative value of prediction is
_smaller_ in this discrete case that in the real valued case. One should be
relatively _more_ willing to expand access, even if the predictor explains
only a very small fraction of the outcome variable.

To see this, we can go through a similar calculation as before. The benefits
of expanding access outweigh those of improving prediction if, the cost-
benefit ratio (specialized here to the probit setting),

$\displaystyle\frac{V_{*}^{\mathrm{pr}}(\alpha+\Delta_{\alpha},\gamma_{s})-V_{*}^{\mathrm{pr}}(\alpha,\gamma_{s})}{V_{*}^{\mathrm{pr}}(\alpha,\gamma_{s}+\Delta_{r^{2}})-V_{*}^{\mathrm{pr}}(\alpha,\gamma_{s})}\times\frac{C_{r^{2}}(\Delta_{r^{2}})}{C_{\alpha}(\Delta_{\alpha})},$
(19)

is greater than 1. Here,
$C_{\alpha}(\Delta_{\alpha}),C_{r^{2}}(\Delta_{r^{2}})>0$ are the again costs
associated with expanding access and improving prediction. Plugging in the
bounds on the prediction access ratio from Theorem 4.5, this condition
approximately holds for values $(\gamma_{t},\alpha)$ satisfying:

$\displaystyle\gamma_{t}\gtrsim\frac{C_{\alpha}(\Delta_{\alpha})}{C_{r^{2}}(\Delta_{r^{2}})}\alpha^{1/\gamma^{2}_{t}}b.$
(20)

To build some intuition, assume that a predictor explains 1% of the variance
so that $\gamma_{s}^{2}=.01$, that 1% of the population is treated
$(\alpha=.01$), and that effects are 1 for 10% of the population
$(\mathrm{Pr}[w_{i}=1]=b=.1)$. This means that
$\gamma_{t}=(1-\gamma_{s}^{2})^{1/2}\approx 1$ and
$\alpha^{1/\gamma_{t}^{2}}\approx.01$. As long as the costs of expanding
access are not several orders of magnitude higher than those of improving
prediction, increasing $\alpha$ is the cost-efficient avenue of improvement.

Due to the fact that we prove both upper and lower bounds on the ratio, one
should prefer expanding prediction if the inequality above holds in the
opposite direction.

Figure 2: Visualization of the cost benefit ratio for the probit model with
$b=.1$. For each value of $\alpha$ (x-axis) and $\gamma_{s}$ (y-axis), we use
our closed form expression for $V_{*}^{\mathrm{pr}}$ (Equation 18) to compute
the cost-benefit ratio (Equation 19) numerically for
$\Delta_{r^{2}}=\Delta_{\alpha}=1e-3$ and
$C_{r^{2}}(\Delta_{r^{2}})/C_{\alpha}(\Delta_{\alpha})=1/2,1/4$. We display
its value –clipped to the interval [1/2, 2]– via the colorbar. The black
dotted line indicates the level set of points for which the cost-benefit ratio
is equal to 1. For small values of $\alpha$, the ratio is well above 1, for
all values of $\gamma_{s}$.

#### Visualizations

As before, we complement these theoretical insights with numerical
simulations, now presented in Figure 2. The plot displays values of the cost
benefit ratio, Equation 19, for various choices of system parameters
$(\alpha,\gamma_{s})$ and cost ratios
$C_{r^{2}}(\Delta_{r^{2}})/C_{\alpha}(\Delta_{\alpha})$.

The visualization further illustrate the technical point made previously: In
this probit model the relative value of prediction is _smaller_ than in the
linear regression case. In particular, if the level of access $\alpha$ is well
below the base rate of positive improvements, $\alpha\ll
b=\mathrm{Pr}[w_{i}=1]$, the cost benefit ratio is always significantly larger
than 1, _regardless_ of the level of prediction $\gamma_{s}$.

Due to the nonlinear nature of the problem, the threshold at which one is
indifferent between expanding prediction versus expanding access is no longer
linear (as seen from the relationship deduced in Equation 20). In this
setting, prediction and access do not go “hand in hand” as before. Rather, as
long as $\gamma_{s}>0$, the focus should always be to expand access until
$\alpha\approx b$, at which point the focus should switch to improving the
predictor.

##  5 Discussion

#### Allocating Goods vs Harms

In this work, we’ve studied the relative value of prediction in settings where
the interventions being allocated could truly be thought of as social _goods_
, and not harms. In particular, both models we analyzed satisfy the property
that there was a large fraction of the population for which welfare
improvements were positive, $\mathrm{Pr}[w_{i}>0]=b>0$. Furthermore, our main
results regarding the prediction access ratio hold only in the regime where
the level of access $\alpha$ is smaller than this fraction $b$. They do not
apply to domains where this distinction between goods and harms is not so
clear. For example, if prediction systems are used to prioritize patients for
invasive medical exams, the interventions may prevent future disease, but also
cause harm through a misdiagnosis. The relevant analysis of the relative value
of prediction in these settings differs significantly from the models we
consider. We hope these will be the subject of future work.

#### Proxy Variables and Misspecification

As discussed in the introduction, we’ve restricted our analysis to cases where
the prediction problem is well-specified and the planner is able to directly
predict the individual treatment effects of interventions. In the language of
potential outcomes [Neyman, 1923, Rubin, 1974], the welfare improvements
$w_{i}$ are treatment effects: the difference between outcomes under
treatment, $y_{i}(1)$, and no treatment, $y_{i}(0)$,

$\displaystyle w_{i}=y_{i}(1)-y_{i}(0).$

Directly predicting heterogenous treatment effects is in general a very
difficult problem. More often than not, planners opt to target interventions
by predicting _proxy_ outcomes that are hopefully well-correlated with
treatment effects. For example, in the early warning system studied in Perdomo
et al. [2023], educators predict $y_{i}(0)$, the likelihood of on-time
graduation absent intervention, with the assumption that treatment effects
$y_{i}(1)-y_{i}(0)$ are largest for students that are least likely to graduate
to graduate without further help.

The intricacies of how to choose the right proxy variables to target
interventions is an interesting question for future work. While we do not
study this problem directly, one insight from our work is that if the relative
value of prediction is small in the well-specified case, it is likely even
smaller in the misspecified setting.

#### The Sufficiency of Weak Signals

When designing prediction systems for social decision making, it’s not always
clear what are the right guarantees we need from our prediction system in
order to make reliable decisions. We believe that one of the main insights
from our work is that you don’t necessarily need to predict something very
accurately, in order to act upon it effectively. For instance, in the probit
model, the prediction access ratio is always large for small values of
$\alpha$, regardless of the $r^{2}$ of the model. As visualized in Figure 2,
it is cost-effective to expand access to allocated goods on the basis of a
predicted score, even if that predicted score explains only a very small
fraction of the variance in outcomes. While perfect predictions are certainly
sufficient for reliable decision making, they are also far from being truly
necessary.

## Acknowledgments

We would like to thank Peter Bartlett, Matthew DosSantos DiSorbo, Cynthia
Dwork, Moritz Hardt, Michael P. Kim, Esther Rolf, and Keyon Vafa for
insightful comments on our work. Conversations with Nathaniel ver Steeg were
very helpful in the initial formulation of the project. This work was in part
supported by the Harvard Center for Research on Computation and Society.

## References

  * Agrawal and Devanur [2016] S. Agrawal and N. Devanur.  Linear contextual bandits with knapsacks.  _Advances in Neural Information Processing Systems_ , 2016.
  * Aiken et al. [2022] E. Aiken, S. Bellue, D. Karlan, C. Udry, and J. E. Blumenstock.  Machine learning and phone data can improve targeting of humanitarian aid.  _Nature_ , 2022.
  * Angrist and Lavy [1999] J. D. Angrist and V. Lavy.  Using maimonides’ rule to estimate the effect of class size on scholastic achievement.  _The Quarterly Journal of Economics_ , 1999.
  * Athey [2017] S. Athey.  Beyond prediction: Using big data for policy problems.  _Science_ , 2017.
  * Athey [2018] S. Athey.  The impact of machine learning on economics.  In _The Economics of Artificial Intelligence: An Agenda_. University of Chicago Press, 2018.
  * Athey and Imbens [2019] S. Athey and G. W. Imbens.  Machine learning methods that economists should know about.  _Annual Review of Economics_ , 2019.
  * Athey and Wager [2021] S. Athey and S. Wager.  Policy learning with observational data.  _Econometrica_ , 2021.
  * Balfanz and Byrnes [2019] R. Balfanz and V. Byrnes.  Early warning indicators and intervention systems: State of the field.  _Handbook of Student Engagement Interventions_ , 2019.
  * Barda et al. [2020] N. Barda, D. Riesel, A. Akriv, J. Levy, U. Finkel, G. Yona, D. Greenfeld, S. Sheiba, J. Somer, E. Bachmat, et al.  Developing a covid-19 mortality risk prediction model when individual-level data are not available.  _Nature Communications_ , 2020.
  * Bertsimas et al. [2019] D. Bertsimas, J. Dunn, and N. Mundru.  Optimal prescriptive trees.  _INFORMS Journal on Optimization_ , 2019.
  * Bhattacharya and Dupas [2012] D. Bhattacharya and P. Dupas.  Inferring welfare maximizing treatment assignment under budget constraints.  _Journal of Econometrics_ , 2012.
  * Black et al. [2022] E. Black, H. Elzayn, A. Chouldechova, J. Goldin, and D. Ho.  Algorithmic fairness and vertical equity: Income fairness with irs tax audit models.  In _ACM Conference on Fairness, Accountability, and Transparency_ , 2022.
  * Chalfin et al. [2016] A. Chalfin, O. Danieli, A. Hillis, Z. Jelveh, M. Luca, J. Ludwig, and S. Mullainathan.  Productivity and selection of human capital with machine learning.  _American Economic Review_ , 2016.
  * Chandler et al. [2011] D. Chandler, S. D. Levitt, and J. A. List.  Predicting and preventing shootings among at-risk youth.  _American Economic Review_ , 2011.
  * Dudík et al. [2011] M. Dudík, J. Langford, and L. Li.  Doubly robust policy evaluation and learning.  _International Conference on International Conference on Machine Learning_ , 2011.
  * Fahrmeir and Kaufmann [1985] L. Fahrmeir and H. Kaufmann.  Consistency and asymptotic normality of the maximum likelihood estimator in generalized linear models.  _The Annals of Statistics_ , 1985.
  * Freedman [1999] D. Freedman.  From association to causation: some remarks on the history of statistics.  _Journal de la Société Française de Statistique_ , 1999\.
  * Glaeser et al. [2016] E. L. Glaeser, A. Hillis, S. D. Kominers, and M. Luca.  Crowdsourcing city government: Using tournaments to improve inspection accuracy.  _American Economic Review_ , 2016.
  * Hino et al. [2018] M. Hino, E. Benami, and N. Brooks.  Machine learning for environmental monitoring.  _Nature Sustainability_ , 2018.
  * Johnson et al. [2023] M. S. Johnson, D. I. Levine, and M. W. Toffel.  Improving regulatory effectiveness through better targeting: Evidence from osha.  _American Economic Journal: Applied Economics_ , 2023.
  * Johnson and Kotz [1970] N. Johnson and S. Kotz.  _Continuous Univariate Distributions_.  J. Wiley, 1970.
  * Kitagawa and Tetenov [2018] T. Kitagawa and A. Tetenov.  Who should be treated? empirical welfare maximization methods for treatment choice.  _Econometrica_ , 2018.
  * Kleinberg et al. [2015] J. Kleinberg, J. Ludwig, S. Mullainathan, and Z. Obermeyer.  Prediction policy problems.  _American Economic Review_ , 2015.
  * Kleinberg et al. [2018] J. Kleinberg, H. Lakkaraju, J. Leskovec, J. Ludwig, and S. Mullainathan.  Human decisions and machine predictions.  _The Quarterly Journal of Economics_ , 2018.
  * Leventer-Roberts et al. [2022] M. Leventer-Roberts, N. Dagan, J. M. Berent, I. Brufman, M. Hoshen, M. Braun, R. D. Balicer, and B. S. Feldman.  Using population-level incidence of hepatitis c virus and immigration status for data-driven screening policies: a case study in israel.  _Journal of Public Health_ , 2022.
  * Liu et al. [2023] L. T. Liu, S. Barocas, J. Kleinberg, and K. Levy.  On the actionability of outcome prediction.  _arXiv preprint arXiv:2309.04470_ , 2023.
  * Manski [2004] C. F. Manski.  Statistical treatment rules for heterogeneous populations.  _Econometrica_ , 2004.
  * Neyman [1923] J. Neyman.  Sur les applications de la théorie des probabilités aux experiences agricoles: Essai des principes.  _Roczniki Nauk Rolniczych_ , 1923.
  * Obermeyer et al. [2019] Z. Obermeyer, B. Powers, C. Vogeli, and S. Mullainathan.  Dissecting racial bias in an algorithm used to manage the health of populations.  _Science_ , 2019.
  * Pearl [2013] J. Pearl.  Linear models: A useful “microscope” for causal analysis.  _Journal of Causal Inference_ , 2013.
  * Perdomo et al. [2023] J. C. Perdomo, T. Britton, M. Hardt, and R. Abebe.  Difficult lessons on social prediction from wisconsin public schools.  _arXiv preprint arXiv:2304.06205_ , 2023.
  * Rockoff et al. [2011] J. E. Rockoff, B. A. Jacob, T. J. Kane, and D. O. Staiger.  Can you recognize an effective teacher when you recruit one?  _Education Finance and Policy_ , 2011.
  * Rubin [1974] D. B. Rubin.  Estimating causal effects of treatments in randomized and nonrandomized studies.  _Journal of Educational Psychology_ , 1974.
  * Salganik et al. [2020] M. J. Salganik, I. Lundberg, A. T. Kindel, C. E. Ahearn, K. Al-Ghoneim, A. Almaatouq, D. M. Altschul, J. E. Brand, N. B. Carnegie, R. J. Compton, et al.  Measuring the predictability of life outcomes with a scientific mass collaboration.  _Proceedings of the National Academy of Sciences_ , 2020.
  * Scott Long [1997] J. Scott Long.  Regression models for categorical and limited dependent variables.  _Advanced Quantitative Techniques in the Social Sciences_ , 1997.
  * Sen. Moynihan [1993] D. P. Sen. Moynihan.  Emergency unemployment compensation amendments of 1993, 1993.  URL https://www.congress.gov/bill/103rd-congress/senate-bill/382.
  * Slivkins et al. [2023] A. Slivkins, K. A. Sankararaman, and D. J. Foster.  Contextual bandits with packing and covering constraints: A modular lagrangian approach via regression.  In _Conference on Learning Theory_ , 2023.
  * Stock et al. [2003] J. H. Stock, M. W. Watson, et al.  _Introduction to econometrics_.  2003\.
  * UNICEF [2022] UNICEF.  Fighting malaria with long-lasting insecticidal nets, 2022.  URL https://www.unicef.org/supply/stories/fighting-malaria-long-lasting-insecticidal-nets-llins.
  * U.S Department of Education [2016] U.S Department of Education.  Issue brief: Early warning systems, 2016.  URL https://www2.ed.gov/rschstat/eval/high-school/early-warning-systems-brief.pdf.  Available at https://www2.ed.gov/rschstat/eval/high-school/early-warning-systems-brief.pdf.
  * Waggoner [2018] B. Waggoner.  Tight bounds for gaussian tails and hazard rates.  https://www.bowaggoner.com/blog/2018/03-17-gaussian-tails/, 2018\.
  * Yule [1899] G. U. Yule.  An investigation into the causes of changes in pauperism in england, chiefly during the last two intercensal decades.  _Journal of the Royal Statistical Society_ , 1899.

##  Appendix A Supporting Arguments for Linear Regression Model

The following result is a general statement regarding the optimal policy for
targeting problems that aim to maximize the expected welfare in the
population. Nearly identical results are well-known and have appeared in
numerous places (see e.g. Bhattacharya and Dupas [11]). We include a
derivation here purely for the sake of having a self-contained presentation.

######  Proposition A.1.

For all distributions ${\cal D}$ over $(x,w)$ supported on a discrete set of
elements, the optimal policy maximizing the social planner’s targeting
problem,

$\displaystyle\max_{\pi\in\\{\mathcal{X}_{s}\rightarrow\\{0,1\\}\\}}\quad$
$\displaystyle\operatorname*{\mathbb{E}}_{(x_{i,s},w_{i})\sim{\cal
D}}[w_{i}\cdot\pi(x_{i,s})]$ subject to
$\displaystyle\operatorname*{\mathbb{E}}_{\cal
D}[\pi(x_{i,s})]\leqslant\alpha,$

is equal to,

$\pi^{*}_{s}(x_{i,s})=\mathbf{1}\\{E[w_{i}\mid
x_{i,s}]>F^{-1}_{s}(1-\alpha)\\}\cdot\mathbf{1}\\{E[w_{i}\mid x_{i,s}]>0\\},$

where $F_{s}^{-1}$ is the quantile function for the random variable
$\operatorname*{\mathbb{E}}[w_{i}\mid X_{s}]$.

###### Proof.

This proof follows from viewing the optimization problem through the lens of
linear programming. We start by expanding out the expectations as sums:

$\displaystyle\operatorname*{\mathbb{E}}[w\cdot\pi(x_{s})]=\sum_{x_{s},w}w\cdot\pi(x_{s})\cdot\mathrm{Pr}[x_{s},w]$
$\displaystyle=\sum_{x_{s}}\mathrm{Pr}[x_{s}]\pi(x_{s})\sum_{w}w\cdot\mathrm{Pr}[w\mid
x]=\sum_{x_{s}}\mathrm{Pr}[x_{s}]\pi(x_{s})\operatorname*{\mathbb{E}}[w\mid
x_{s}]$ $\displaystyle\operatorname*{\mathbb{E}}[\pi(x_{s})]$
$\displaystyle=\sum_{x}\pi(x_{s})\mathrm{Pr}[x_{s}].$

Therefore the optimization problem can be equivalently written as maximizing a
linear cost function, while satisfying a linear constraint:

$\displaystyle\max_{\pi\in\\{\mathcal{X}_{s}\rightarrow\\{0,1\\}\\}}\quad$
$\displaystyle\sum_{x_{s}}\pi(x_{s})v(x_{s})$ subject to
$\displaystyle\sum\pi(x_{s})c(x_{s})\leqslant\alpha.$

Here, $v(x_{s})=\mathrm{Pr}[x_{s}]\operatorname*{\mathbb{E}}[w\mid x_{s}]$ and
$c(x_{s})=\mathrm{Pr}[x_{s}]$. Without loss of generality, we can assume that
$\mathrm{Pr}[x_{s}]>0$ for all $x_{s}$, otherwise the terms can be removed
from both sums.

The optimal solution to this program is to set $\pi(x_{s})=1$, for the $x_{s}$
that maximize the ratio $v(x_{s})/c(x_{s})$ until the constraint is reached.
Intuitively, setting $\pi(x_{s})=1$ “costs” $c(x_{s})$ units and “returns”
$v(x_{s})$ units. In this setting, this ratio is equal to the conditional
expectation:

$\displaystyle\frac{v(x_{s})}{c(x_{s})}=\operatorname*{\mathbb{E}}[w|x_{s}].$

By definition of the quantile function, assigning $\pi(x_{s})=1$ to the
$x_{s}$ with the top $\alpha$ values of $\operatorname*{\mathbb{E}}[w\mid
x_{s}]$ is equivalent to choosing

$\displaystyle\pi(x_{s})=\mathbf{1}\\{\operatorname*{\mathbb{E}}[w|X_{s}]\geqslant
F_{s}^{-1}(1-\alpha)\\}.$

Since we can always choose to treat fewer than an $\alpha$ fraction of the
units, the second indicator function ensure that each term adds a nonnegative
amount to the objective. ∎

###  A.1 Value Function for Linear Regression Model: Proof of Proposition 3.5

Since $w$ is Gaussian and we assume that $\alpha<.5$, $\mu>0$, the condition
that $\operatorname*{\mathbb{E}}[w_{i}\mid x_{i,s}]\geqslant
F_{s}^{-1}(1-\alpha)$ implies that $\operatorname*{\mathbb{E}}[w_{i}\mid
x_{i,s}]>0$.

Plugging in our expression for $\pi_{s}^{*}$ (Lemma 3.3) into the objective
function, $\operatorname*{\mathbb{E}}[w_{i}\pi_{s}^{*}(x_{i,s})]$, and using
the functional form for $w_{i}$ from the linear regression model, we have
that,

$\displaystyle\operatorname*{\mathbb{E}}[w_{i}\pi_{s}^{*}(x_{i,s})]$
$\displaystyle=\operatorname*{\mathbb{E}}[(\langle
x_{i,s},\;\beta_{s}\rangle+\langle
x_{i,t},\;\beta_{t}\rangle+\mu)\cdot\mathbf{1}\\{\langle
x_{i,s},\;\beta_{s}\rangle\geqslant\Phi^{-1}(1-\alpha)\lVert\beta_{s}\rVert_{2}\\}]$
$\displaystyle=\alpha\mu+\operatorname*{\mathbb{E}}[\langle
x_{i,s},\;\beta_{s}\rangle\cdot\mathbf{1}\\{\langle
x_{i,s},\;\beta_{s}\rangle\geqslant\Phi^{-1}(1-\alpha)\lVert\beta_{s}\rVert_{2}\\}].$

Here, we’ve used the fact that the unobserved $\langle
x_{i,t},\;\beta_{t}\rangle$ and observed components $\langle
x_{i,s},\;\beta_{s}\rangle$ are independent to conclude that,

$\displaystyle\operatorname*{\mathbb{E}}[\langle
x_{i,t},\;\beta_{t}\rangle\cdot\mathbf{1}\\{\langle
x_{i,s},\;\beta_{s}\rangle\geqslant\Phi^{-1}(1-\alpha)\lVert\beta_{s}\rVert_{2}\\}]=\operatorname*{\mathbb{E}}[\langle
x_{i,t},\;\beta_{t}\rangle]\operatorname*{\mathbb{E}}[\mathbf{1}\\{\langle
x_{i,s},\;\beta_{s}\rangle\geqslant\Phi^{-1}(1-\alpha)\lVert\beta_{s}\rVert_{2}\\}]=0,$

since $\operatorname*{\mathbb{E}}[\langle x_{i,t},\;\beta_{t}\rangle]=0$. Now,
using the general identity, that holds for any random variable $Z$ and event
$A$,

$\displaystyle\operatorname*{\mathbb{E}}[Z\cdot\mathbf{1}_{A}]=\operatorname*{\mathbb{E}}[Z\mid
A]\mathrm{Pr}[A],$

we have that, for $w_{i,s}=\langle x_{i,s},\;\beta_{s}\rangle$, the
expectation
$\operatorname*{\mathbb{E}}[w_{i,s}\cdot\mathbf{1}\\{w_{i,s}\geqslant\Phi^{-1}(1-\alpha)\lVert\beta_{s}\rVert_{2}\\}]$
is equal to

$\displaystyle\operatorname*{\mathbb{E}}[w_{i,s}\mid
w_{i,s}\geqslant\Phi^{-1}(1-\alpha)\lVert\beta_{s}\rVert_{2}]\cdot\mathrm{Pr}[w_{i,s}\geqslant\Phi^{-1}(1-\alpha)\lVert\beta_{s}\rVert_{2}].$

By the Mills Ratio identity (Lemma A.3), since $w_{i,s}\sim{\cal
N}(0,\lVert\beta_{s}\rVert_{2}^{2})$, the first term is equal to,

$\displaystyle\operatorname*{\mathbb{E}}[w_{i,s}\mid
w_{i,s}\geqslant\Phi^{-1}(1-\alpha)\lVert\beta_{s}\rVert_{2}]$
$\displaystyle=\lVert\beta_{s}\rVert_{2}\frac{\phi(\frac{\Phi^{-1}(1-\alpha)\lVert\beta_{s}\rVert_{2}}{\lVert\beta_{s}\rVert_{2}})}{1-\Phi(\frac{\Phi^{-1}(1-\alpha)\lVert\beta_{s}\rVert_{2}}{\lVert\beta_{s}\rVert_{2}})}=\frac{\lVert\beta_{s}\rVert_{2}\phi(\Phi^{-1}(1-\alpha))}{\alpha},$

since $1-\Phi(\Phi^{-1}(1-\alpha))=\alpha$. And, by definition of the quantile
function,

$\displaystyle\mathrm{Pr}[w_{i,s}\geqslant\Phi^{-1}(1-\alpha)\lVert\beta_{s}\rVert_{2}]=\alpha.$

Therefore,

$\displaystyle\operatorname*{\mathbb{E}}[w_{i,s}\mid
w_{i,s}\geqslant\Phi^{-1}(1-\alpha)\lVert\beta_{s}\rVert_{2}]=\lVert\beta_{s}\rVert_{2}\phi(\Phi^{-1}(1-\alpha)),$

and

$\operatorname*{\mathbb{E}}[w_{i}\pi_{s}^{*}(x_{i,s})]=\alpha\mu+\lVert\beta_{s}\rVert_{2}\phi(\Phi^{-1}(1-\alpha)).$

The exact expression follows by substituting
$\lVert\beta_{s}\rVert_{2}=\gamma_{s}\lVert\beta\rVert_{2}$ (Definition 3.4).

###  A.2 Prediction Access Ratio for Linear Regression: Proof of Theorem 3.7

Recall that the goal is to prove upper and lower bounds on the ratio,

$\displaystyle\frac{V_{*}^{\mathrm{lin}}(\alpha+\Delta_{\alpha},\gamma_{s})-V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})}{V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s}+\Delta_{r^{2}})-V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})}.$

To do so, we deal with the numerator and the denominator separately.

#### Quantifying Prediction Improvement.

We start with the denominator. This part is relatively simple because the
value function is linear in $\gamma_{s}$. Recall from Proposition 3.5 that:

$\displaystyle
V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})=\alpha\mu+\gamma_{s}\lVert\beta\rVert_{2}\phi(\Phi^{-1}(1-\alpha)).$

Therefore,

$\displaystyle
V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s}+\Delta_{r^{2}})-V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})=\Delta_{r^{2}}\lVert\beta\rVert_{2}\phi(\Phi^{-1}(1-\alpha)).$

Now, if we apply Lemma A.6 and our assumption on $\alpha$, we get that,

$\displaystyle\Delta_{r^{2}}\lVert\beta\rVert_{2}\alpha\Phi^{-1}(1-\alpha)\leqslant
V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s}+\Delta_{r^{2}})-V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})\leqslant\Delta_{r^{2}}\lVert\beta\rVert_{2}\alpha\Phi^{-1}(1-\alpha)(1+f(\alpha)),$
(21)

where $f(\alpha)=\Phi^{-1}(1-\alpha)^{2}/(\Phi^{-1}(1-\alpha)^{2}-1)-1$ is
$o(1)$ and less than 1 for $\alpha<.05$.

#### Quantifying Access Improvement.

Using the closed form expression for the value function, we get that:

$\displaystyle
V_{*}^{\mathrm{lin}}(\alpha+\Delta_{\alpha},\gamma_{s})-V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})$
$\displaystyle=\Delta_{\alpha}\cdot\mu+\gamma_{s}\lVert\beta\rVert_{2}\left(\phi(\Phi^{-1}(1-\alpha-\Delta_{\alpha}))-\phi(\Phi^{-1}(1-\alpha))\right).$

Applying Lemma A.2, we get that:

$\displaystyle\frac{1}{2}\Delta_{\alpha}\Phi^{-1}(1-\alpha)\leqslant\phi(\Phi^{-1}(1-\alpha-\Delta_{\alpha}))-\phi(\Phi^{-1}(1-\alpha))\leqslant\Delta_{\alpha}\Phi^{-1}(1-\alpha).$

Therefore,

$\displaystyle\Delta_{\alpha}(\mu+\frac{1}{2}\gamma_{s}\lVert\beta\rVert_{2}\Phi^{-1}(1-\alpha))\leqslant
V_{*}^{\mathrm{lin}}(\alpha+\Delta_{\alpha},\gamma_{s})-V_{*}^{\mathrm{lin}}(\alpha,\gamma_{s})\leqslant\Delta_{\alpha}(\mu+\gamma_{s}\lVert\beta\rVert_{2}\Phi^{-1}(1-\alpha)).$
(22)

The statement follows from combining the bounds in Equation 22 and Equation
21.

######  Lemma A.2.

Define $g(\alpha)=\phi(\Phi^{-1}(1-\alpha))$, then for $\alpha+\Delta<.05$ and
$\Delta\leqslant 4\alpha$,

$\displaystyle\Delta\Phi^{-1}(1-\alpha)\geqslant
g(\alpha+\Delta)-g(\alpha)\geqslant\frac{1}{2}\Phi^{-1}(1-\alpha)\Delta.$

###### Proof.

From Lemma A.4, we have that

$\displaystyle g^{\prime}(\alpha)=\Phi^{-1}(1-\alpha)\text{ and
}g^{\prime\prime}(\alpha)=\frac{-1}{\phi(\Phi^{-1}(1-\alpha))}.$

By Taylor’s theorem, there exists a value $c\in[0,1]$ such that:

$\displaystyle g(\alpha+\Delta)-g(\alpha)$
$\displaystyle=g^{\prime}(\alpha)\Delta+\frac{1}{2}\Delta^{2}g^{\prime\prime}(\alpha+c\Delta)$
$\displaystyle=\Delta\Phi^{-1}(1-\alpha)-\frac{1}{2}\Delta^{2}\frac{1}{\phi(\Phi^{-1}(1-\alpha-c\Delta))}$
$\displaystyle\leqslant\Delta\Phi^{-1}(1-\alpha).$

To prove the lower bound on $g(\alpha+\Delta)-g(\alpha)$ it suffices to
establish that

$\displaystyle\frac{1}{2}\Delta^{2}\frac{1}{\phi(\Phi^{-1}(1-\alpha-c\Delta))}\leqslant\frac{1}{2}\Delta\Phi^{-1}(1-\alpha).$
(23)

Or equivalently, that
$\Delta\leqslant\Phi^{-1}(1-\alpha)\phi(\Phi^{-1}(1-\alpha-c\Delta))$. To show
this, we know that by Lemma A.6, for $\alpha+\Delta<.15$,

$\displaystyle\phi(\Phi^{-1}(1-\alpha-c\Delta))\geqslant(\alpha+c\Delta)\Phi^{-1}(1-\alpha-c\Delta)\geqslant\sqrt{2}\alpha.$

The second inequality follows from the fact that
$\Phi^{-1}(1-a)\geqslant\sqrt{2}$ for all $a<.05$ and that $c\Delta>0$.
Therefore, in order for,

$\Delta\leqslant\Phi^{-1}(1-\alpha)\phi(\Phi^{-1}(1-\alpha-c\Delta)),$

it suffices for $\Delta\leqslant 4\alpha$. This ensures that the inequality in
Equation 23 is true and concludes the proof of the lower bound. ∎

###  A.3 Supporting Technical Lemmas

######  Lemma A.3 (Inverse Mills Ratio).

Let $z\sim{\cal N}(\mu,\sigma^{2})$, then

$\displaystyle\operatorname*{\mathbb{E}}[z\mid
z>a]=\mu+\sigma\frac{\phi(a)}{1-\Phi(a)}.$

###### Proof.

This is a well known property of Gaussians, see e.g [21]. ∎

######  Lemma A.4.

$\displaystyle\frac{\partial}{\partial\alpha}\Phi^{-1}(1-\alpha)$
$\displaystyle=-\frac{1}{\phi(\Phi^{-1}(1-\alpha))}$
$\displaystyle\frac{\partial}{\partial\alpha}\phi(\Phi^{-1}(1-\alpha))$
$\displaystyle=\Phi^{-1}(1-\alpha)$

###### Proof.

These identities are also standard, we include a proof for the sake of
completeness. By definition of inverse functions,

$\displaystyle\frac{\partial}{\partial x}f^{-1}(f(x))=\frac{\partial}{\partial
x}x=1,$

and by the chain rule,

$\displaystyle\frac{\partial}{\partial
x}f^{-1}(f(x))=f^{\prime}(f^{-1}(x))(f^{-1})^{\prime}(x).$

Combining these two we get that:

$\displaystyle\frac{\partial}{\partial
x}f^{-1}(x)=\frac{1}{f^{\prime}(f(x))}\text{ and }\frac{\partial}{\partial
x}f^{-1}(1-x)=-\frac{1}{f^{\prime}(f(x))}.$

Since $\Phi^{\prime}=\phi$ ($\Phi$ is the CDF and $\phi$ is a PDF), then we
can use the second identity above to conclude that:

$\displaystyle\frac{\partial}{\partial\alpha}\Phi^{-1}(1-\alpha)$
$\displaystyle=-\frac{1}{\phi(\Phi^{-1}(1-\alpha))}.$

For the second calculation, we use the fact that $\phi^{\prime}(x)=-x\phi(x)$
as well as the result from the first part. By the chain rule,

$\displaystyle\frac{\partial}{\partial\alpha}\phi(\Phi^{-1}(1-\alpha))$
$\displaystyle=-\Phi^{-1}(1-\alpha)\phi(\Phi^{-1}(1-\alpha))\left(\frac{\partial}{\partial\alpha}\Phi^{-1}(1-\alpha)\right)$
$\displaystyle=\Phi^{-1}(1-\alpha).$

∎

######  Lemma A.5.

Let $z\sim{\cal N}(0,1)$, then, for all $t>0$:

$\displaystyle\frac{\phi(t)}{t}(1-t^{-2})\leqslant\mathrm{Pr}(z\geqslant
t)\leqslant\frac{\phi(t)}{t}.$

###### Proof.

These bounds appear in numerous sources, this particular result is drawn from
a writeup from Bo Waggoner [41]. ∎

######  Lemma A.6.

For all $\alpha<.15$,

$\displaystyle\alpha\Phi^{-1}(1-\alpha)\leqslant\phi(\Phi^{-1}(1-\alpha))\leqslant\Phi^{-1}(1-\alpha)\alpha(1+f(\alpha)),$

where $f(\alpha)=\Phi^{-1}(1-\alpha)^{2}/(\Phi^{-1}(1-\alpha)^{2}-1)-1$ is
o(1) and less than 1 for all $\alpha<.05$.

###### Proof.

The main idea is to use Lemma A.5 and set $t=\Phi^{-1}(1-\alpha)$. By
definition of the quantile function, if $z$ is a standard normal:

$\displaystyle\mathrm{Pr}(z\geqslant\Phi^{-1}(1-\alpha))=\alpha.$

From our assumption on $\alpha$, $t=\Phi^{-1}(1-\alpha)>0$ and hence applying
Lemma A.5 we get that,

$\displaystyle\frac{\phi(\Phi^{-1}(1-\alpha))}{\Phi^{-1}(1-\alpha)}\left(1-\frac{1}{\Phi^{-1}(1-\alpha)^{2}}\right)\leqslant\alpha\leqslant\frac{\phi(\Phi^{-1}(1-\alpha))}{\Phi^{-1}(1-\alpha)}.$

The final statement follows from rearranging these inequalities. ∎

######  Proposition A.7.

$\displaystyle\Phi^{-1}(1-\alpha)=\Theta(\sqrt{\log(1/\alpha)})\text{ as
}\alpha\rightarrow 0$

###### Proof.

From the definition of the quantile function, we have that

$\displaystyle\Phi^{-1}(1-\alpha)=\operatorname*{arg\,max}_{t}\mathrm{Pr}(z\geqslant
t)\leqslant\alpha.$

From the Lemma A.5, for $t\geqslant\sqrt{2}$,

$\displaystyle\frac{\phi(t)}{2t}\leqslant\mathrm{Pr}[z\geqslant
t]\leqslant\frac{\phi(t)}{t}.$

Therefore, $\Phi^{-1}(1-\alpha)\geqslant t_{1}$ where $t_{1}$ solves,

$\displaystyle\frac{\phi(t_{1})}{t_{1}}=\alpha,$

and $\Phi^{-1}(1-\alpha)\leqslant t_{2}$ where $t_{2}$ solves,

$\displaystyle\frac{\phi(t_{2})}{2t_{2}}=\alpha.$

Using the definition of $\phi$, it suffices to solve for the values of $t$
that solve the equation,

$\displaystyle\frac{1}{\sqrt{2\pi}}\exp(-t^{2}/2)\frac{1}{c_{0}t}=\alpha,$

for $c_{0}\in\\{1,2\\}$. Moving everything into logs, this becomes

$\displaystyle\frac{t^{2}}{2}-\log(\frac{1}{\sqrt{2\pi}})-\log(\frac{1}{ct})=\log(1/\alpha).$

For small values of $\alpha$, the $t^{2}$ term dominates and we get that

$\displaystyle t\approx\sqrt{\log(1/\alpha)}.$

∎

##  Appendix B Supporting Arguments for Probit Regression Model

###  B.1 Value Function for Probit Regression: Proof of Lemma 4.2

Using the lemma regarding the functional form for the optimal targeting policy
(Lemma 4.2), and the definition of $w_{i}$ from the probit model, we can
expand out the value of the optimal policy as follows:

$\displaystyle\operatorname*{\mathbb{E}}[w_{i}\pi^{*}_{s}(x_{s})]=$
$\displaystyle=\operatorname*{\mathbb{E}}[\mathbf{1}\\{x_{s}^{\top}\beta_{s}+x_{t}^{\top}\beta_{t}+\mu>0\\}\cdot\mathbf{1}\\{x_{s}^{\top}\beta_{s}+\mu\geqslant\mu+\lVert\beta_{s}\rVert_{2}\Phi^{-1}(1-\alpha)]$
$\displaystyle=\operatorname*{\mathbb{E}}[\mathbf{1}\\{x_{s}^{\top}\beta_{s}+x_{t}^{\top}\beta_{t}+\mu>0\\}\cdot\mathbf{1}\\{x_{s}^{\top}\beta_{s}\geqslant\lVert\beta_{s}\rVert_{2}\Phi^{-1}(1-\alpha)].$
(24)

Using the fact that the random variables $x_{s}^{\top}\beta_{s}\sim{\cal
N}(0,\lVert\beta_{s}\rVert_{2}^{2})$ and $x_{t}^{\top}\beta_{t}\sim{\cal
N}(0,\lVert\beta_{t}\rVert_{2}^{2})$ are independent and Gaussian, we can
rewrite these as,

$\displaystyle x_{s}^{\top}\beta_{s}=\lVert\beta_{s}\rVert_{2}z_{s}\text{ and
}x_{t}^{\top}\beta_{t}=\lVert\beta_{t}\rVert_{2}z_{t},$

where $z_{s},z_{t}\sim{\cal N}(0,1)$ are i.i.d. Adopting this notation, we can
rewrite the previous expression for the value function in Equation 24 as:

$\displaystyle=\operatorname*{\mathbb{E}}[\mathbf{1}\\{\lVert\beta_{s}\rVert_{2}z_{s}+\lVert\beta_{t}\rVert_{2}z_{t}+\mu>0\\}\cdot\mathbf{1}\\{\lVert\beta_{s}\rVert_{2}z_{s}\geqslant\lVert\beta_{s}\rVert_{2}\Phi^{-1}(1-\alpha)]$
$\displaystyle=\operatorname*{\mathbb{E}}[\mathbf{1}\\{\lVert\beta_{s}\rVert_{2}z_{s}+\lVert\beta_{t}\rVert_{2}z_{t}+\mu>0\\}\cdot\mathbf{1}\\{z_{s}\geqslant\Phi^{-1}(1-\alpha)]$
$\displaystyle=\mathrm{Pr}[\mathbf{1}\\{\lVert\beta_{s}\rVert_{2}z_{s}+\lVert\beta_{t}\rVert_{2}z_{t}+\mu>0,\;z_{s}\geqslant\Phi^{-1}(1-\alpha)]$
$\displaystyle=\mathrm{Pr}[z_{t}\geqslant\frac{-\lVert\beta_{s}\rVert_{2}z_{s}-\mu}{\lVert\beta_{t}\rVert_{2}},\;z_{s}\geqslant\Phi^{-1}(1-\alpha)]$
$\displaystyle=\int_{\Phi^{-1}(1-\alpha)}^{\infty}\int_{\frac{-\lVert\beta_{s}\rVert_{2}z_{s}-\mu}{\lVert\beta_{t}\rVert_{2}}}^{\infty}\phi(z_{t})\phi(z_{s})dz_{t}dz_{s}$
$\displaystyle=\int_{\Phi^{-1}(1-\alpha)}^{\infty}\left(1-\Phi\left(\frac{-\lVert\beta_{s}\rVert_{2}z_{s}-\mu}{\lVert\beta_{t}\rVert_{2}}\right)\right)\phi(z_{s}).$

Here, we’ve again used $\phi$ denote the pdf for a standard Gaussian. Using
the identity, $1-\Phi(-a)=\Phi(a)$, this last expression is equal to the
following integral:

$\displaystyle\int_{\Phi^{-1}(1-\alpha)}^{\infty}\Phi\left(\frac{\lVert\beta_{s}\rVert_{2}z_{s}+\mu}{\lVert\beta_{t}\rVert_{2}}\right)\phi(z_{s})dz_{s}.$

The exact statement follows from substituting
$\lVert\beta_{s}\rVert_{2}=\gamma_{s}\lVert\beta\rVert_{2}$ and
$\lVert\beta_{t}\rVert_{2}=\gamma_{t}\lVert\beta\rVert_{2}$.

###  B.2 Prediction Access Ratio for Probit Regression: Proof of Theorem 4.5

Recall from the definition of the probit model that,

$\displaystyle\mathrm{Pr}[\langle x,\beta\rangle+\mu>0]=b\in(0,1),$

and hence, $\mu\lVert\beta\rVert_{2}^{-1}=\Phi^{-1}(b)=-\Phi^{-1}(1-b)$.

#### Quantifying Improvements by Expanding Access

By Taylor’s theorem, there exists some $c\in(0,1)$ such that:

$\displaystyle
V_{*}^{\mathrm{pr}}(\alpha+\Delta_{\alpha},\gamma_{s})-V_{*}^{\mathrm{pr}}(\alpha,\gamma_{s})=\Delta_{\alpha}\cdot\frac{\partial}{\partial\alpha}V_{*}^{\mathrm{pr}}(\alpha+c\Delta_{\alpha},\gamma_{s}).$

The last term is the derivative of the value function evaluated at the point
$(\alpha+c\Delta_{\alpha},\gamma_{s})$. From, Lemma B.2, we know that

$\displaystyle\frac{\partial}{\partial\alpha}V_{*}^{\mathrm{pr}}(\alpha+c\Delta_{\alpha},\gamma_{s})=\Phi\left(\frac{\gamma_{s}\Phi^{-1}(1-\alpha-c\Delta_{\alpha})+\mu\lVert\beta\rVert_{2}^{-1}}{\gamma_{t}}\right).$

Using the identity, $\mu\lVert\beta\rVert_{2}^{-1}=-\Phi^{-1}(1-b)$, we can
rewrite this as

$\displaystyle\Phi\left(\frac{\gamma_{s}\Phi^{-1}(1-\alpha-c\Delta_{\alpha})+\mu\lVert\beta\rVert_{2}^{-1}}{\gamma_{t}}\right)=\Phi\left(\frac{1}{\gamma_{t}}\big{(}\gamma_{s}\Phi^{-1}(1-\alpha-c\Delta_{\alpha})-\Phi^{-1}(1-b)\big{)}\right).$
(25)

Assuming that $\Delta_{\alpha}\leqslant\alpha$ and that $\alpha$ is small
enough so that $\gamma_{s}\Phi^{-1}(1-2\alpha)\geqslant\Phi^{-1}(1-b)$, then,

$\displaystyle\gamma_{s}\Phi^{-1}(1-\alpha-c\Delta_{\alpha})\geqslant\gamma_{s}\Phi^{-1}(1-2\alpha)\geqslant\Phi^{-1}(1-b),$

and we have that the expression in (25) is of the form $\Phi(x)$ for some
$x\geqslant 0$. Therefore, by properties of the Gaussian CDF,

$\displaystyle\frac{\partial}{\partial\alpha}V_{*}^{\mathrm{pr}}(\alpha+c\Delta_{\alpha},\gamma_{s})\in[1/2,1].$

Hence,

$\displaystyle\frac{1}{2}\Delta_{\alpha}\leqslant
V_{*}^{\mathrm{pr}}(\alpha+\Delta_{\alpha},\gamma_{s})-V_{*}^{\mathrm{pr}}(\alpha,\gamma_{s})\leqslant\Delta_{\alpha}.$
(26)

#### Quantifying Improvements via Prediction

We use the same strategy as in the previous part. By Taylor’s theorem, there
exists some $c\in(0,1)$ such that:

$\displaystyle
V_{*}^{\mathrm{pr}}(\alpha,\gamma_{s}+\Delta_{r^{2}})-V_{*}^{\mathrm{pr}}(\alpha,\gamma_{s})=\Delta_{r^{2}}\cdot\frac{\partial}{\partial\gamma_{s}}V_{*}^{\mathrm{pr}}(\alpha,\gamma_{s}+c\Delta_{r^{2}}).$

Now, let $\gamma_{s,c}=\gamma_{s}+c\Delta_{r^{2}}$ and
$\gamma_{t,c}=\sqrt{1-\gamma_{s,c}^{2}}$. Then, by Lemma B.3,

$\displaystyle\frac{\partial}{\partial\gamma_{s}}V_{*}^{\mathrm{pr}}(\alpha,\gamma_{s}+c\Delta_{r^{2}})$
$\displaystyle=\frac{1}{\gamma_{t,c}}\phi\left(\frac{\mu}{\lVert\beta\rVert_{2}}\right)\phi\left(\frac{\Phi^{-1}(1-\alpha)+\mu\lVert\beta\rVert_{2}^{-1}\gamma_{s,c}}{\gamma_{t,c}}\right)$
$\displaystyle=\underbrace{\frac{1}{\gamma_{t,c}}\phi\left(\frac{\mu}{\lVert\beta\rVert_{2}}\right)}_{T_{1}}\underbrace{\phi\left(\frac{\Phi^{-1}(1-\alpha)-\Phi^{-1}(1-b)\gamma_{s,c}}{\gamma_{t,c}}\right)}_{T_{2}}.$

We start by analyzing bounds on $T_{2}$. For any $\varepsilon_{1}>0$, there
exists a value $t_{1}(\varepsilon_{1},\gamma_{t})$, depending on
$\varepsilon_{1}$ and $\gamma_{t}$, such that for all $\Delta_{r^{2}}\leqslant
t_{1}(\varepsilon_{1},\gamma_{t})$, we have that
$.5\gamma_{t}\leqslant(1-\varepsilon_{1})\gamma_{t}\leqslant\gamma_{t,c}\leqslant\gamma_{t}.$
Assuming this condition holds, since $\gamma_{s,c}\Phi^{-1}(1-b)>0$, we get
that:

$\displaystyle\frac{\Phi^{-1}(1-\alpha)-\Phi^{-1}(1-b)\gamma_{s,c}}{\gamma_{t,c}}\leqslant\Phi^{-1}(1-\alpha)\frac{1}{(1-\varepsilon_{1})\gamma_{t}}.$

Furthermore, since $\gamma_{t,c}\leqslant\gamma_{t}$ and
$\gamma_{s,c}\leqslant 1$, for any fixed $\varepsilon_{2}$, there exists a
value $t_{2}(b,\gamma_{t})$, depending on $\gamma_{t}$ and $b$, such that for
all $\alpha\leqslant t_{2}(b,\gamma_{t},\varepsilon_{2})$:

$\displaystyle\frac{\Phi^{-1}(1-\alpha)-\Phi^{-1}(1-b)\gamma_{s,c}}{\gamma_{t,c}}\geqslant\frac{\Phi^{-1}(1-\alpha)-\Phi^{-1}(1-b)}{\gamma_{t,c}}\geqslant\frac{\Phi^{-1}(1-\alpha)}{\gamma_{t}}(1-\varepsilon_{2}).$

Using these last two lines, and the fact that
$\phi(x^{\prime})\leqslant\phi(x)$ for $0<x\leqslant x^{\prime}$, we get that

$\displaystyle\phi\left(\frac{1}{(1-\varepsilon_{3})}\frac{\Phi^{-1}(1-\alpha)}{\gamma_{t}}\right)\leqslant\phi\left(\frac{\Phi^{-1}(1-\alpha)-\Phi^{-1}(1-b)\gamma_{s,c}}{\gamma_{t,c}}\right)\leqslant\phi\left(\frac{\Phi^{-1}(1-\alpha)}{\gamma_{t}}(1-\varepsilon_{3})\right).$

where $\varepsilon_{3}=\max\\{\varepsilon_{1},\varepsilon_{2}\\}$. Now, by
Lemma B.5, for $\alpha$ smaller than some value
$t_{3}(\alpha,\varepsilon_{3})>0$,

$\displaystyle
T_{2}\leqslant\phi\left(\frac{\Phi^{-1}(1-\alpha)}{\gamma_{t}}(1-\varepsilon_{3})\right)$
$\displaystyle\leqslant\frac{1}{\sqrt{2\pi}}\left(1.01\sqrt{2\pi}\alpha\Phi^{-1}(1-\alpha)\right)^{\frac{1}{\gamma_{t}^{2}}(1-\varepsilon_{3})^{2}}.$

And,

$\displaystyle
T_{2}\geqslant\phi\left(\frac{1}{(1-\varepsilon_{3})}\frac{\Phi^{-1}(1-\alpha)}{\gamma_{t}}\right)$
$\displaystyle\geqslant\frac{1}{\sqrt{2\pi}}\left(\sqrt{2\pi}\alpha\Phi^{-1}(1-\alpha)\right)^{\frac{(1-\varepsilon_{3})^{-2}}{\gamma_{t}^{2}}}$
$\displaystyle=\frac{1}{\sqrt{2\pi}}\left(\sqrt{2\pi}\alpha\Phi^{-1}(1-\alpha)\right)^{\frac{1}{\gamma_{t}^{2}}(1+\varepsilon_{4})^{2}},$

where we have rewritten the last expression in a more convenient form by
letting $\varepsilon_{4}=\varepsilon_{3}/(1-\varepsilon_{3})$.

Analyzing $T_{1}$ is simple. Recall that
$\mu\lVert\beta\rVert_{2}^{-1}=\Phi^{-1}(1-b)$ where $b=\mathrm{Pr}[w_{i}>0]$.
Hence,

$\displaystyle\phi\left(\frac{\mu}{\lVert\beta\rVert_{2}}\right)=\phi(-\Phi^{-1}(1-b))=\phi(\Phi^{-1}(1-b)).$

Then for all $b<.15$, Lemma A.6 ensures that:

$\displaystyle
b\Phi^{-1}(1-b)\leqslant\phi\left(\frac{\mu}{\lVert\beta\rVert_{2}}\right)\leqslant
2b\Phi^{-1}(1-b).$

Furthermore, by our initial calculation, we can set $\varepsilon_{1}<.5$ so
that $.5\gamma_{t}\leqslant\gamma_{t,c}\leqslant\gamma_{t}.$ and hence:

$\displaystyle\frac{1}{\gamma_{t}}\leqslant\frac{1}{\gamma_{t,c}}\leqslant\frac{2}{\gamma_{t}}.$

This implies that $T_{1}$ satisfies the bounds:

$\displaystyle b\Phi^{-1}(1-b)\leqslant T_{1}\leqslant
4\frac{1}{\gamma_{t}}b\Phi^{-1}(1-b).$

Combining our bounds for $T_{1}$ and $T_{2}$, we get that for appropriately
small $b,\alpha,\Delta_{r^{2}}$,

$\displaystyle
V_{*}^{\mathrm{pr}}(\alpha,\gamma_{s}+\Delta_{r^{2}})-V_{*}^{\mathrm{pr}}(\alpha,\gamma_{s})$
$\displaystyle\leqslant\Delta_{r^{2}}\frac{2}{\gamma_{t}}\sqrt{\frac{2}{\pi}}\cdot
b\Phi^{-1}(1-b)\cdot\left(1.01\sqrt{2\pi}\alpha\Phi^{-1}(1-\alpha)\right)^{\frac{1}{\gamma_{t}^{2}}(1-\varepsilon_{3})^{2}}$
$\displaystyle
V_{*}^{\mathrm{pr}}(\alpha,\gamma_{s}+\Delta_{r^{2}})-V_{*}^{\mathrm{pr}}(\alpha,\gamma_{s})$
$\displaystyle\geqslant\Delta_{r^{2}}\frac{1}{\gamma_{t}}\frac{1}{\sqrt{2\pi}}\cdot
b\Phi^{-1}(1-b)\left(\sqrt{2\pi}\alpha\Phi^{-1}(1-\alpha)\right)^{\frac{1}{\gamma_{t}^{2}}(1+\varepsilon_{4})^{2}}.$

The final statement comes from combining these inequalities with those in (26)
and simplifying the constants.

###  B.3 Supporting Technical Lemmas

######  Lemma B.1 (Leibniz’s Rule).

$\displaystyle\frac{d}{dx}\int_{a(x)}^{b(x)}f(x,t)\,dt=f(x,b(x))\cdot\frac{d}{dx}b(x)-f(x,a(x))\cdot\frac{d}{dx}a(x)+\int_{a(x)}^{b(x)}\frac{\partial}{\partial
x}f(x,t)\,dt$

######  Lemma B.2.

$\displaystyle\frac{\partial}{\partial\alpha}V_{*}^{\mathrm{pr}}(\alpha,\gamma_{s})=\Phi\left(\frac{\gamma_{s}\Phi^{-1}(1-\alpha)+\mu\lVert\beta\rVert_{2}^{-1}}{\gamma_{t}}\right)$

###### Proof.

By Leibniz’s Rule (Lemma B.1), the derivative has only one nonzero term:

$\displaystyle\frac{\partial}{\partial\alpha}\int_{\Phi^{-1}(1-\alpha)}^{\infty}\Phi\left(\frac{\gamma_{s}z_{s}+\mu\lVert\beta\rVert_{2}^{-1}}{\gamma_{t}}\right)\phi(z_{s})dz_{s}$
$\displaystyle=-\Phi\left(\frac{\gamma_{s}\Phi^{-1}(1-\alpha)+\mu\lVert\beta\rVert_{2}^{-1}}{\gamma_{t}}\right)\phi(\Phi^{-1}(1-\alpha))\left(\frac{\partial}{\partial\alpha}\Phi^{-1}(1-\alpha)\right)$

To finish, we can apply Lemma A.4, to evaluate,

$\displaystyle\frac{\partial}{\partial\alpha}\Phi^{-1}(1-\alpha)=-(\phi(\Phi^{-1}(1-\alpha)))^{-1},$

and then simplify. ∎

######  Lemma B.3.

$\displaystyle\frac{\partial}{\partial\gamma_{s}}V_{*}^{\mathrm{pr}}(\alpha,\gamma_{s})=\frac{1}{\gamma_{t}}\phi\left(\frac{\mu}{\lVert\beta\rVert_{2}}\right)\phi\left(\frac{\Phi^{-1}(1-\alpha)+\mu\lVert\beta\rVert_{2}^{-1}\gamma_{s}}{\gamma_{t}}\right)$

###### Proof.

Starting with the chain rule, we have that,

$\displaystyle\frac{\partial}{\partial\gamma_{s}}\int_{\Phi^{-1}(1-\alpha)}^{\infty}\Phi\left(\frac{\gamma_{s}z_{s}+\mu\lVert\beta\rVert_{2}^{-1}}{\gamma_{t}}\right)\phi(z_{s})dz_{s},$

is equal to:

$\displaystyle\int_{\Phi^{-1}(1-\alpha)}^{\infty}\phi\left(\frac{\gamma_{s}z_{s}+\mu\lVert\beta^{-1}\rVert_{2}}{\gamma_{t}}\right)\phi(z_{s})\left(z_{s}\cdot\frac{\partial}{\partial\gamma_{s}}\left(\frac{\gamma_{s}}{\gamma_{t}}\right)+\frac{\partial}{\partial\gamma_{s}}\left(\frac{\mu\lVert\beta\rVert_{2}^{-1}}{\gamma_{t}}\right)\right).$
(27)

Now, we can calculate the remaining derivatives explicitly,

$\displaystyle\frac{\partial}{\partial\gamma_{s}}\left(\frac{\gamma_{s}}{\gamma_{t}}\right)$
$\displaystyle=\frac{\partial}{\partial\gamma_{s}}\left(\frac{\gamma_{s}}{\sqrt{1-\gamma_{s}^{2}}}\right)=\frac{1}{(1-\gamma_{s}^{2})^{3/2}}=\frac{1}{\gamma_{t}^{3}}$
$\displaystyle\frac{\partial}{\partial\gamma_{s}}\left(\frac{\mu\lVert\beta\rVert_{2}^{-1}}{\gamma_{t}}\right)$
$\displaystyle=\frac{\partial}{\partial\gamma_{s}}\left(\frac{\mu\lVert\beta\rVert_{2}^{-1}}{\sqrt{1-\gamma_{s}^{2}}}\right)=\frac{\mu\lVert\beta\rVert_{2}^{-1}\gamma_{s}}{(1-\gamma_{s}^{2})^{3/2}}=\frac{\mu\lVert\beta\rVert_{2}^{-1}\gamma_{s}}{\gamma_{t}^{3}},$

and we can rewrite the product of pdfs as:

$\displaystyle\phi(\frac{\gamma_{s}z_{s}+\mu\lVert\beta\rVert_{2}^{-1}}{\gamma_{t}})\phi(z_{s})=\phi\left(\frac{\mu}{\lVert\beta\rVert_{2}}\right)\phi\left(\frac{z_{s}+\mu\lVert\beta\rVert_{2}^{-1}\gamma_{s}}{\gamma_{t}}\right).$

Going back to the initial expression in (27) and substituting in these last
three identities, we have that the derivative can be written as:

$\displaystyle\frac{1}{\gamma_{t}^{3}}\phi\left(\frac{\mu}{\lVert\beta\rVert_{2}}\right)\int_{\Phi^{-1}(1-\alpha)}^{\infty}\phi\left(\frac{z_{s}+\mu\lVert\beta\rVert_{2}^{-1}\gamma_{s}}{\gamma_{t}}\right)\left(z_{s}+\mu\lVert\beta\rVert_{2}^{-1}\gamma_{s}\right)dz_{s}.$
(28)

These integrals we can indeed evaluate:

$\displaystyle\int_{\Phi^{-1}(1-\alpha)}^{\infty}\phi\left(\frac{z_{s}+\mu\lVert\beta\rVert_{2}^{-1}\gamma_{s}}{\gamma_{t}}\right)dz_{s}$
$\displaystyle=\gamma_{s}\cdot\Phi\left(\frac{z_{s}+\mu\lVert\beta\rVert_{2}^{-1}\gamma_{s}}{\gamma_{t}}\right)\Bigg{|}_{\Phi^{-1}(1-\alpha)}^{\infty}$
$\displaystyle=\gamma_{t}\left(1-\Phi\left(\frac{\Phi^{-1}(1-\alpha)+\mu\lVert\beta\rVert_{2}^{-1}\gamma_{s}}{\gamma_{t}}\right)\right).$

And,

$\displaystyle\int_{\Phi^{-1}(1-\alpha)}^{\infty}\phi\left(\frac{z_{s}+\mu\lVert\beta\rVert_{2}^{-1}\gamma_{s}}{\gamma_{t}}\right)z_{s}dz_{s}$
$\displaystyle=-\gamma_{t}^{2}\left[\phi\left(\frac{z_{s}+\mu\lVert\beta\rVert_{2}^{-1}\gamma_{s}}{\gamma_{t}}\right)+\frac{\mu\lVert\beta\rVert_{2}^{-1}\gamma_{s}}{\gamma_{t}}\Phi\left(\frac{z_{s}+\mu\lVert\beta\rVert_{2}^{-1}\gamma_{s}}{\gamma_{t}}\right)\right]\Bigg{|}_{\Phi^{-1}(1-\alpha)}^{\infty},$

is equal to:

$\displaystyle-\gamma_{t}^{2}\left[-\phi\left(\frac{\Phi^{-1}(1-\alpha)+\mu\lVert\beta\rVert_{2}^{-1}\gamma_{s}}{\gamma_{t}}\right)+\frac{\mu\lVert\beta\rVert_{2}^{-1}\gamma_{s}}{\gamma_{t}}\left(1-\Phi\left(\frac{\Phi^{-1}(1-\alpha)+\mu\lVert\beta\rVert_{2}^{-1}\gamma_{s}}{\gamma_{t}}\right)\right)\right].$

Plugging in the solutions to the integrals back into (28), we get that the
final expression is:

$\displaystyle\frac{1}{\gamma_{t}}\phi\left(\frac{\mu}{\lVert\beta\rVert_{2}}\right)\phi\left(\frac{\Phi^{-1}(1-\alpha)+\mu\lVert\beta\rVert_{2}^{-1}\gamma_{s}}{\gamma_{t}}\right).$

∎

######  Lemma B.4.

Assume that $\gamma_{s}^{2}+\gamma_{t}^{2}=1$ and that $\gamma_{s},\gamma_{t}$
and both in $(0,1)$. Then,

$\displaystyle\phi(\frac{\gamma_{s}z_{s}+\mu\lVert\beta\rVert_{2}^{-1}}{\gamma_{t}})\phi(z_{s})=\phi\left(\frac{\mu}{\lVert\beta\rVert_{2}}\right)\phi\left(\frac{z_{s}+\mu\lVert\beta\rVert_{2}^{-1}\gamma_{s}}{\gamma_{t}}\right).$

###### Proof.

The main idea is to expand out the exponents and complete the square:

$\displaystyle\phi(\frac{\gamma_{s}z_{s}+\mu\lVert\beta\rVert_{2}^{-1}}{\gamma_{t}})\phi(z_{s})$
$\displaystyle=\frac{1}{2\pi}\exp\left(-\frac{(\gamma_{s}z_{s}+\mu\lVert\beta\rVert_{2}^{-1})^{2}}{2\gamma_{t}^{2}}-\frac{z_{s}^{2}}{2}\right)$
$\displaystyle=\frac{1}{2\pi}\exp\left(-\frac{((\gamma_{s}^{2}+\gamma_{t}^{2})z_{s}^{2}+\mu^{2}\lVert\beta\rVert_{2}^{-2}+2\mu\lVert\beta\rVert_{2}^{-1}\gamma_{s}z_{s})}{2\gamma_{t}^{2}}\right)$
$\displaystyle=\frac{1}{2\pi}\exp\left(-\frac{\mu^{2}\lVert\beta\rVert_{2}^{-2}}{2\gamma_{t}^{2}}\right)\exp\left(-\frac{(z_{s}^{2}+2\mu\lVert\beta\rVert_{2}^{-1}\gamma_{s}z_{s}\pm\mu^{2}\lVert\beta\rVert_{2}^{-1}\gamma_{s}^{2})}{2\sigma_{t}^{2}}\right)$
$\displaystyle=\frac{1}{2\pi}\exp\left(-\frac{\mu^{2}\lVert\beta\rVert_{2}^{-2}}{2\gamma_{t}^{2}}\right)\exp\left(\frac{-(z_{s}+\mu\lVert\beta\rVert_{2}^{-1}\gamma_{s})^{2}+\mu^{2}\lVert\beta\rVert_{2}^{-2}\gamma_{s}^{2})}{2\gamma_{t}^{2}}\right)$
$\displaystyle=\frac{1}{2\pi}\exp\left(-\frac{\mu^{2}\lVert\beta\rVert_{2}^{-2}}{2\gamma_{t}^{2}}\right)\exp\left(-\frac{1}{2}\left(\frac{z_{s}+\mu\lVert\beta\rVert_{2}^{-1}\gamma_{s}}{\gamma_{t}}\right)^{2}\right)\exp\left(\frac{\mu^{2}\lVert\beta\rVert_{2}^{-2}\gamma_{s}^{2}}{2\gamma_{t}^{2}}\right).$

In the third line, we used the fact that $1=\gamma_{t}^{2}+\gamma_{s}^{2}$.
Using this same identity, we can further simplify two of the remaining terms
as:

$\displaystyle\exp\left(-\frac{\mu^{2}\lVert\beta\rVert_{2}^{-2}}{2\gamma_{t}^{2}}\right)\exp\left(\frac{\mu^{2}\lVert\beta\rVert_{2}^{-2}\gamma_{s}^{2}}{2\gamma_{t}^{2}}\right)=\exp\left(\frac{-\mu\lVert\beta\rVert_{2}^{-2}(1-\gamma_{s}^{2})}{\gamma_{t}^{2}}\right)=\exp\left(-\frac{\mu^{2}}{\lVert\beta\rVert_{2}^{2}}\right).$

Hence,

$\displaystyle\phi(\frac{\gamma_{s}z_{s}+\mu\lVert\beta\rVert_{2}^{-1}}{\gamma_{t}})\phi(z_{s})=\phi\left(\frac{\mu}{\lVert\beta\rVert_{2}}\right)\phi\left(\frac{z_{s}+\mu\lVert\beta\rVert_{2}^{-1}\gamma_{s}}{\gamma_{t}}\right).$

∎

######  Lemma B.5.

For any $k,\varepsilon>0$ there exists a value $t(\varepsilon)>0$, that
depends only $\varepsilon$, such that for all $\alpha\leqslant
t(\varepsilon)$, the followings inequalities hold:

$\displaystyle\frac{1}{\sqrt{2\pi}}(\sqrt{2\pi}\alpha)^{k^{2}}(\Phi^{-1}(1-\alpha))^{k^{2}}\leqslant\phi(k\cdot\Phi^{-1}(1-\alpha))\leqslant\frac{1}{\sqrt{2\pi}}\left((1+\varepsilon)\cdot\sqrt{2\pi}\alpha\Phi^{-1}(1-\alpha)\right)^{k^{2}}$

###### Proof.

The proof is just a direct calculation that follows from expanding out the
definition of the Gaussian PDF $\phi(\cdot)$, and then applying Lemma A.6:

$\displaystyle\phi(k\cdot\Phi^{-1}(1-\alpha))$
$\displaystyle=\frac{1}{\sqrt{2\pi}}\exp\left(\frac{-k^{2}(\Phi^{-1}(1-\alpha))^{2}}{2}\right)$
$\displaystyle=(2\pi)^{\frac{k^{2}-1}{2}}\left[\frac{1}{\sqrt{2\pi}}\exp\left(\frac{-(\Phi^{-1}(1-\alpha))^{2}}{2}\right)\right]^{k^{2}}$
$\displaystyle=(2\pi)^{\frac{k^{2}-1}{2}}\left[\phi(\Phi^{-1}(1-\alpha))\right]^{k^{2}}.$

Moving onto the second part, for $\alpha$ small enough, we have that by Lemma
A.6,

$\displaystyle\alpha\Phi^{-1}(1-\alpha)\leqslant\phi(\Phi^{-1}(1-\alpha))\leqslant\alpha\Phi^{-1}(1-\alpha)(1+\varepsilon).$

Therefore,

$\displaystyle(2\pi)^{\frac{k^{2}-1}{2}}\left[\alpha\cdot\Phi^{-1}(1-\alpha)\right]^{k^{2}}\leqslant\phi(k\cdot\Phi^{-1}(1-\alpha))\leqslant(2\pi)^{\frac{k^{2}-1}{2}}\left[(1+\varepsilon)\alpha\cdot\Phi^{-1}(1-\alpha)\right]^{k^{2}}.$

The precise inequality then follows from simplifying this expression above. ∎