A general characterization of optimal tie-breaker designs

Companies, charitable institutions, and clinicians often have ethical or economic reasons to prefer assigning a binary treatment to certain individuals. If this preference is expressed by the values of a scalar running variable $x$, a natural decision is to assign the treatment to a subject if and only if their $x$ is at least some threshold $t$. This is a regression discontinuity design, or RDD (Thistlethwaite and Campbell,, 1960). Unfortunately, treatment effect estimates from an RDD analysis typically have very high variance (Jacob et al.,, 2012; Goldberger,, 1972; Gelman and Imbens,, 2017), relative to those from a randomized control trial (RCT) that does not preferentially treat any individuals. To trade off between these competing statistical and ethical objectives, investigators can use a tie-breaker design (TBD). In a typical tie-breaker design, the top ranked subjects get the treatment, the lowest ranked subjects are in the control group and a cohort in the middle are randomized to treatment or control. The earliest tie-breaker reference that we are aware of is Campbell, (1969) where $x$ was discrete and the randomization broke ties among subjects with identical values of $x$.

Past settings for tie-breaker designs include the offer of remedial English to incoming university students based on their high school English proficiency (Aiken et al.,, 1998), a diversion program designed to reduce juvenile delinquency (Lipsey et al.,, 1981), scholarship offerings for two and four year colleges based on a judgment of the applicants’ needs and academic strengths (Abdulkadiroglu et al.,, 2017; Angrist et al.,, 2020), and clinical trials (Trochim and Cappelleri,, 1992), where they are known as cutoff designs.

The tie-breaker design problem is to choose treatment probabilities $p_{i}$ for subjects $i=1,\dots,n$ based on their running variables $x_{i}$. These probabilities are chosen before observing the response values $y_{1},\dots,y_{n}$ but with the running variables $x_{1},\dots,x_{n}$ known. We assume throughout that $p_{i}=p_{i^{\prime}}$ whenever $x_{i}=x_{i^{\prime}}$.

As is common in the optimal experimental design literature, the statistical objective is an “efficiency” criterion that measures estimation precision. Specifically, our criterion will be a function $\Psi(\cdot)$ of the information (scaled inverse variance) matrix $\mathcal{I}_{n}(p_{1},\dots,p_{n})$ for the model parameters $\beta=(\beta_{0},\beta_{1},\beta_{2},\beta_{3})^{\top}$ in a two line model relating the response $y_{i}$ to the running variable $x_{i}$ and a treatment indicator $z_{i}\in\{-1,1\}$:

This simple working model nonetheless poses some challenging design problems. In Section 6 we describe some more general modeling settings for tie-breaker models.

Throughout we assume that the running variable is centered, i.e. $(1/n)\sum_{i}x_{i}=0$, and that the $\varepsilon_{i}$ have common variance $\sigma^{2}$. Here $z_{i}=1$ indicates treatment and so $p_{i}=\Pr(z_{i}=1)=(1+\mathbb{E}(z_{i}))/2$). For model (1) the information matrix is $\mathcal{I}_{n}=\mathbb{E}(\mathcal{X}_{i}\mathcal{X}_{i}^{\top})$ where $\mathcal{X}_{i}=(1,x_{i},z_{i},x_{i}z_{i})^{\top}\in\mathbb{R}^{4}$ and the expectation is taken over the treatment assignments $z_{i}$, conditional on the running variables $x_{i}$ (whose values are known). The ordinary least squares estimate $\hat{\beta}$ of $\beta$ satisfies $\mathbb{E}(\mathrm{Var}(\hat{\beta})^{-1})=n\mathcal{I}_{n}/\sigma^{2}$. Common examples of efficiency criteria $\Psi(\cdot)$ in the literature, such as the D-optimality criterion $\Psi_{D}(\cdot)=\log(\det(\cdot))$, are concave in both $\mathcal{I}_{n}$ and $p=(p_{1},\ldots,p_{n})^{\top}$ (Boyd and Vandenberghe,, 2004). However, our theoretical results only require continuity of $\Psi(\cdot)$.

Our preference for treating individuals with higher running variables $x$ is expressed as an equality constraint on the scaled covariance $\overline{xp}\equiv(1/n)\sum_{i=1}^{n}x_{i}p_{i}$ between treatment and the running variable (recall the latter is known, hence viewed as non-random). Under the two-line model (1), this constraint has the following economic interpretation. We take $y$ to be something like economic value or student success, where larger $y$ is better. We expect that $\beta_{3}>0$ holds in most of our motivating problems. The expected value of $y$ per customer under (1) is then

where $\bar{p}\equiv(1/n)\sum_{i=1}^{n}p_{i}$. Equation (2) shows that the expected gain is unaffected by $\beta_{0}$ or $\beta_{1}$. Furthermore, we assume the proportion of treated subjects is fixed by an external budget, i.e., an equality constraint $\bar{p}=\widetilde{p}$ for some $\widetilde{p}\in(0,1)$. For instance, there might be only a set number of scholarships or perks to be given out. The only term affected by the design in (2) is then $\beta_{3}\cdot\overline{xp}$, as pointed out by Owen and Varian, (2020). For $\beta_{3}>0$, the short term average value per customer grows with $\overline{xp}$ and we would want that value to be large. Similar functionals are also commonly studied as regret functions in bandit problems (Goldenshluger and Zeevi,, 2013; Metelkina and Pronzato,, 2017).

We are now ready to formulate the tie-breaker design problem as the following constrained optimization problem. Given real values $x_{1}\leqslant x_{2}\leqslant\cdots\leqslant x_{n}$:

for some constants $\widetilde{p}$ and $\widetilde{xp}$. The first equality constraint in (3) is a budget constraint due to the cost of treatment and the second constraint is on the short term gain mentioned above. We consider two different sets $\mathcal{A}$ in detail. The first is $[0,1]^{n}$. The second is $\{\bm{p}\in[0,1]^{n}\mid 0\leqslant p_{1}\leqslant p_{2}\leqslant\cdots\leqslant p_{n}\leqslant 1\}$ which requires treatment probabilities to be non-decreasing in the running variable $x$. Such a monotonicity constraint prevents more qualified students from having a lower chance of getting a scholarship than less qualified ones or more loyal customers having a lower chance for a perk than others. It also eliminates perverse incentives for subjects to lower their $x_{i}$. To our knowledge, such a monotonicity constraint has not been received much attention in the optimal design literature, though it is enormously appealing in our motivating applications.

When the efficiency criterion $\psi(\cdot)$ is concave in $\bm{p}$, then a solution to (3) can be found numerically via convex optimization, as Morrison and Owen, (2022) do for vector valued $x_{i}$, and as Metelkina and Pronzato, (2017) mention for a similar problem. However, our particular setting with univariate $x_{i}$ is tractable enough to provide a simple yet complete analytical characterization of the optimal $p_{i}$, even if the efficiency criterion is not concave. We show, under general conditions, that we can always find optimal treatment probabilities that are piecewise constant in $x$, with the number of pieces small and independent of $n$.

There is a well-developed literature for optimal experiment design in the presence of multiple objectives. Early examples of a constrained optimization problem of the form (3) were designed to account for several of the standard efficiency objectives simultaneously (Stigler,, 1971; Lee,, 1987, 1988). Läuter, (1974, 1976) proposed maximizing a convex combination of efficiency objectives, a practice now typically referred to as a “compound” design approach. It is now well known (Cook and Wong,, 1994; Clyde and Chaloner,, 1996) that in many problems with concave objectives, optimal constrained and compound designs are equivalent. In this paper, we provide another approach to reduce the constrained problem (3) to a compound problem that can handle the monotonicity constraint. At the same time, we provide simple ways to compute our optimal designs that are based directly on the parameters $\widetilde{p}$ and $\widetilde{xp}$ in our constrained formulation (3), and do not require specifying the Lagrange multipliers appearing in the corresponding compound problem. Those Lagrange multipliers involve ratios of information gain to economic gain where each of those quantities is only known up to a multiplicative constant.

Problems similar to (3) have received significant attention in the sequential design of clinical trials. Biased-coin designs, beginning with the simple procedure of Efron, (1971), have been developed as a compromise between treatment balance and randomization; see Atkinson, (2014) for a review. Covariate-adaptive biased-coin designs often replace the balance objective with an efficiency criterion such as D-optimality (Atkinson,, 1982; Rosenberger and Sverdlov,, 2008). Response-adaptive designs also optimize for some efficiency objective but simultaneously seek to minimize the number of patients receiving the inferior treatment for ethical reasons (Hu and Rosenberger,, 2006). Various authors such as Bandyopadhyay and Biswas, (2001) and Hu et al., (2015) propose sequential designs to effectively navigate this trade-off. When they also account for covariate information, they are called covariate-adjusted response-adaptive (CARA) designs (Zhang et al.,, 2007; Zhang and Hu,, 2009).

In the CARA literature especially, there has been significant recent interest in optimal design for nonlinear models (Sverdlov et al.,, 2013; Metelkina and Pronzato,, 2017; Biswas and Bhattacharya,, 2018). Unlike optimal designs in linear models such as (1), designs in nonlinear models can typically only be locally optimal, meaning that their optimality depends on the values of the unknown parameters (Chernoff,, 1953). While we may be able to obtain increasingly reliable estimates of these parameters over time in sequential settings, in non-clinical settings subjects typically enter a tie-breaker study non-sequentially, i.e., we know the running variables for all subjects before designing the experiment. In these applications — such as measuring the impact of a scholarship on future educational attainment — it can take several years to collect a single set of responses on which to compute a parameter estimate. Locally optimal designs are therefore of limited utility in this setting, and so we focus on optimal design under the linear model (1) in a non-sequential setting, which already presents a sufficient challenge.

The existing literature on problems like (3) typically considers the running variable $x$ to be random. For example, Section 7 of Owen and Varian, (2020) study tie-breaker designs under the assumption that the running variable is either uniform or Gaussian, and exactly half the subjects are to be treated. They consider the typical three level tie-breaker design where subjects with running variable $x$ above some threshold $\Delta$ always get the treatment, subjects with running variable below $-\Delta$ never get the treatment, and the remaining subjects are randomized into treatment with probability $1/2$. They find that a $c$-optimality criterion of statistical efficiency is monotonically increasing in the width $\Delta$ of the randomization window, with the RCT ($\Delta\to\infty$) being most efficient and the RDD ($\Delta=0$) least efficient. Conversely, the short-term gain is decreasing in $\Delta$. They also show the three level design is optimal for any given level of short-term gain. In this article we show strong advantages to moving away from that three level design when the running variable is not symmetric, or we cannot treat half of the subjects.

Metelkina and Pronzato, (2017) studied a further generalization of the optimal tie-breaker design problem, motivated by CARA designs. In particular, their Example 1, an illustration of their Corollary 2.1, is similar¹¹1There are minor differences such as the lack of a treatment fraction constraint, an inequality constraint on short-term gain as opposed to an equality constraint, and the use of a common intercept for the treated and untreated individuals, i.e., assuming that $\beta_{2}=0$ in (1). to a random-$x$ generalization of (3). Crucially, however, the proof for their Corollary 2.1 does not generalize to the case where we require the treatment probabilities be monotone. Even without the monotonicity constraint, we provide a sharper characterization of the solutions to our more specific problem (Section 3.1).

We introduce a random-$x$ generalization of the problem (3) in Section 2. We show it encompasses both  (3) and the problem studied by Owen and Varian, (2020) as special cases. Then, Section 3 presents the main technical results characterizing the solutions to this more general problem. In particular, Theorem 2 shows that, under the monotonicity constraint, there always exists a solution to (3) corresponding to a simple, two-level stratified design where all subjects with running variable below some threshold $t^{\prime}$ have the same probability of treatment, all subjects with running variable above $t^{\prime}$ have an identical, higher probability of treatment, and those subjects with $x=t^{\prime}$ have a treatment probability between these two values. Section 4 then presents some results on the trade-off between a $D$-optimality efficiency criterion and short-term gain for these optimal designs; examples of this trade-off for some specific running variable distributions are given in Section 5. That section also includes a fixed-$x$ application based on Head Start, a government assistance program for low-income children. It also shows how to compute our optimal designs when $x$ is either fixed or random. Finally, Section 6 provides summarizes the main results.

Our random-$x$ generalization of (3) assumes the running variables $x_{i}$ are samples from a common distribution $F$, which we hereafter identify with the corresponding cumulative distribution function. It considers an information matrix that averages over both the random treatment assignments and randomness in the running variables. This allows us to characterize optimal designs for an as yet unobserved set of running variable values, when their distribution is known.

Before presenting the random-$x$ tie-breaker design problem, we briefly review the standard setting of optimal design in multiple linear regression models; see e.g. Atkinson et al., (2007) for further background. In the simplest case, the user assumes the standard linear model $y_{i}=\bm{x}_{i}^{\mathsf{T}}\bm{\beta}+\varepsilon_{i}$ with the goal of selecting covariate values $\bm{x}_{1},\dots,\bm{x}_{n}\in{}^{p}$ to optimize an efficiency criterion that is a function of the information matrix $\mathcal{X}^{\mathsf{T}}\mathcal{X}$, where $\mathcal{X}\in{}^{n\times p}$ is the design matrix with $i$-th row $\bm{x}_{i}^{\mathsf{T}}$. Perhaps the most common such criterion is D-optimality, which corresponds to maximizing $\log(\det(\mathcal{X}^{\mathsf{T}}\mathcal{X}))$. Another popular choice is $c$-optimality, which minimizes $c^{\mathsf{T}}(\mathcal{X}^{\mathsf{T}}\mathcal{X})^{-1}c$ for some choice of $c\in{}^{p}$. This can be interpreted as minimizing $\mathrm{Var}(c^{\top}\hat{\beta}\mid\mathcal{X})$, where $\hat{\beta}$ is the ordinary least squares estimator. The study of optimal design is often simplified by the use of design measures. A design measure $\xi$ is a probability distribution from which to generate the covariates $\bm{x}_{i}$. The relaxed optimal design problem involves selecting a design measure $\xi$ instead of a finite number of covariate values $\bm{x}_{1},\ldots,\bm{x}_{n}$. The objective is to optimize for the desired functional of the expected information matrix $\mathcal{I}(\xi)\equiv\mathbb{E}_{\xi}[\mathcal{X}^{\mathsf{T}}\mathcal{X}]$ over some space $\Xi$ of design measures $\xi$. For instance, a design measure $\xi^{*}$ is D-optimal (for the relaxed problem) if $\xi^{*}\in\operatorname*{arg\,max}_{\xi\in\Xi}\det(\mathcal{I}(\xi))$, and $c$-optimal if $\xi^{*}\in\operatorname*{arg\,min}_{\xi\in\Xi}c^{\top}\mathcal{I}(\xi)^{-1}c$. The original optimal design problem restricts $\Xi$ to only consist of discrete probability distributions supported on at most $n$ distinct points with probabilities that are multiples of $1/n$.

For the tie-breaker design problem, our regression model (1) includes both the running variables $x_{i}$ and the treatment indicators $z_{i}$ as covariates. But the experimenter does not have control over the entire joint distribution of $(x_{i},z_{i})$. The running variable is externally determined, so they can only specify the conditional distribution of the treatment indicator $z_{i}$ given the running variable $x_{i}$. This conditional distribution is specified by a design function $p:\real\to[0,1]$ such that $p(x)\equiv\Pr(z_{i}=1\mid x_{i}=x)$. As mentioned above, we assume $x_{i}\sim F$ for a known, fixed distribution $F$. This allows us to drop subscripts $i$ when convenient. For any two design functions $p$ and $p^{\prime}$ we say $p=p^{\prime}$ whenever $\Pr_{F}(\{x:p(x)=p^{\prime}(x)\})=1$. We only need a minimal assumption on $F$, which can be continuous, discrete, or neither:

The mean-centeredness part of Assumption 1 loses no generality, due to the translation invariance of estimation under the two-line model (1). All expectations involving $x$ hereafter omit the subscript $F$ from all such expectations with the implicit understanding that $x\sim F$.

The random-$x$ tie-breaker design problem is as follows:

Here $\widetilde{z}$ and $\widetilde{xz}$ are constants analogous to $\bar{p}$ and $\overline{xp}$, respectively, in (3), $\mathcal{F}$ is a collection of design functions, and $\mathcal{I}(p)$ is the expected information matrix under the model (1), averaging over both $x\sim F$ and $z\mid x\sim p$.

This problem can be viewed as a constrained relaxed optimal design problem under the regression model (1) where the set $\Xi$ of allowable design measures is indexed by the design functions $p\in\mathcal{F}$.

To interpret the equality constraints in (4) it is helpful to note that

for any $a\geqslant 0$ with $\mathbb{E}(|x|^{a})<\infty$. In particular, for each positive integer $a$, there exists an invertible linear mapping $\varphi_{a}:{}^{a+1}\to{}^{a+1}$ that does not depend on the design $p$ and maps $(\mathbb{E}_{p}(z),\ldots,\mathbb{E}_{p}(x^{a}z))$ to $(\mathbb{E}(p(x)),\ldots,\mathbb{E}(x^{a}p(x)))$. For example, $\varphi_{1}(x,y)=(1/2)(1+x,y)$. Taking $a=0$ in (5), we see the constraint $\mathbb{E}_{p}(z)=\widetilde{z}$ in (4) is equivalent to requiring the expected proportion of subjects to be treated to be $(1+\widetilde{z})/2$. This proportion is typically determined by the aforementioned budget constraints. Taking $a=1$ in (5) shows that the second constraint $\mathbb{E}_{p}(xz)=\widetilde{xz}$ in (4) sets the expected level of short-term gain. In Section 2.2, we provide some guidance on how to choose $\widetilde{xz}$ in practice.

From computing the expected information matrix $\mathcal{I}(p)$ in Section 2.3, we will see the problem (4) reduces to the finite-dimensional problem (3) when $F$ is discrete, placing probability mass $n^{-1}$ on each of the known running variable values $x_{1},\ldots,x_{n}$. Thus, to solve (3) it suffices to solve the problem (4) for any $F$ satisfying Assumption 1, which must hold for any discrete distribution with finite support.

To solve the constrained optimization problem (4), we begin by observing that the expected information matrix $\mathcal{I}(p)$, computed in (14), only depends on the design function $p$ through the quantities $\mathbb{E}_{p}(z)$, $\mathbb{E}_{p}(xz)$, and $\mathbb{E}_{p}(x^{2}z)$. Then the same is true for any efficiency objective $\Psi(\mathcal{I}(p))$. Consequently for any continuous $\Psi$ we can write $\Psi(\mathcal{I}(p)))=g_{\Psi}(\mathbb{E}_{p}(z),\mathbb{E}_{p}(xz),\mathbb{E}_{p}(x^{2}z))$ for some continuous $g_{\Psi}:{}^{3}\to\real$ that may depend on the running variable distribution $F$.

Fixing $(\widetilde{z},\widetilde{xz})\in\mathcal{J}$ and the set $\mathcal{F}$ of permissible design functions, we say a feasible design $p\in\mathcal{F}$ is one that satisfies the equality constraints in (4), i.e. $\mathbb{E}_{p}(z)=\widetilde{z}$ and $\mathbb{E}_{p}(xz)=\widetilde{xz}$. Thus, the efficiency criterion $\Psi(\mathcal{I}(p))$ can only vary among feasible designs $p$ through the single quantity $\mathbb{E}_{p}(x^{2}z)$. Furthermore, any two feasible designs $p$ and $q$ with $\mathbb{E}_{p}(x^{2}z)=\mathbb{E}_{q}(x^{2}z)$ must have the same efficiency. Thus, we can break down the problem (4) into two steps. First, we find a solution

where

is the set of values of $\mathbb{E}_{p}(x^{2}z)$ attainable by some feasible design $p\in\mathcal{F}$. Then we must find a feasible design $p\in\mathcal{F}$ that satisfies $\mathbb{E}_{p}(x^{2}z)=\widetilde{x^{2}z}^{*}(\widetilde{z},\widetilde{xz};\Psi)$.

The next result shows that when $\mathcal{F}$ is convex, $I_{\mathcal{F}}(\widetilde{z},\widetilde{xz})$ is an interval. For our two choices of $\mathcal{F}$ of interest, Propositions 1 and 2 will show it is a closed interval, so (17) will always have a solution when $\Psi(\cdot)$ is continuous.

The endpoints of $I_{\mathcal{F}}(\widetilde{z},\widetilde{xz})$ can be computed as the optimal values of the following constrained optimization problems:

Given solutions $p_{\max}$ and $p_{\min}$ to the problems (19), Lemma 2 shows that the design

solves the problem (4) for $\lambda=(\mathbb{E}_{p_{\max}}(x^{2}z)-\widetilde{x^{2}z}^{*}(\widetilde{z},\widetilde{xz};\Psi))/(\mathbb{E}_{p_{\max}}(x^{2}z)-\mathbb{E}_{p_{\min}}(x^{2}z))$. If $\mathbb{E}_{p_{\max}}(x^{2}z)=\mathbb{E}_{p_{\min}}(x^{2}z)$ then all feasible designs $p$ have the same efficiency, so any one of them is optimal.

The remainder of this section is concerned with characterizing the solutions to the problems (19) for two specific choices of design function classes $\mathcal{F}$: the set of all measurable functions into $[0,1]$, and the set of all such monotone functions. For these two choices of $\mathcal{F}$, solutions $p_{\max}$ and $p_{\min}$ exist for any $(\widetilde{z},\widetilde{xz})\in\mathcal{J}$ and are unique. Our argument uses extensions of the Neyman-Pearson lemma (Neyman and Pearson,, 1933) in hypothesis testing. These extensions are in Dantzig and Wald, (1951), whose two authors discovered the relevant results independently of each other. We use a modern formulation of their work, adapting the presentation by Lehmann and Romano, (2005):