Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
105,241 characters · 19 sections · 124 citation commands
Externally Valid Selection of Experimental Sites via the k-Median Problem
\onehalfspacing
\onehalfspacing
A common concern in randomized evaluations of new policies is their external validity; that is, whether the estimated effects of a policy intervention carry over to new samples or populations duflo2007using,al2012generalizability,list2020non,vivalt2020much, gechter2024generalizing. A recent literature argues that the external validity of randomized evaluations can be improved by explicitly incorporating this goal into the experimental design by, for example, carefully deciding where to experiment; see degtiar2023review for an overview and references and chassang2022designing for some recent work. For instance, if a researcher has access to multiple sites to experimentally evaluate a new policy, it is possible to use the information available before the evaluation (such as site-level characteristics) to nonrandomly select one or more sites. Recently, egamidesigning and gechter2023site argued that a research design which nonrandomly selects experimental sites---referred to broadly in the literature as purposive sampling cook2002experimental---may improve the external validity of randomized evaluations.
We present a decision-theoretic justification for viewing the question of how to best nonrandomly select $k$ sites to experiment---or, equivalently, how to best design a purposive sampling scheme---with the goal of optimizing external validity as a $k$-median problem. This is a classical problem in computer science and operations research shmoys2011design,cohen2022improved. Broadly speaking, in a $k$-median problem, there is a set of facilities and a set of clients; the goal is to open at most $k$ facilities and connect each client to at least one facility at minimal total connection cost. The $k$-facilities that solve the $k$-median problem are the locations that are closest to the clients, where closeness is defined by the total connection cost. As we will explain below, the $k$ sites selected for experimentation by solving the $k$-median problem will be the $k$ sites that are, broadly speaking, the most representative of the target populations to which the new policy will be scaled up. We next provide more specific details on how we use statistical decision theory to establish a formal connection between the site-selection problem to optimize external validity and the \emph{k-median problem}.
{ The Site-Selection Problem:} Suppose that some experimental sites can be used by a policymaker (or a researcher) to gather experimental evidence on the effectiveness of a policy or treatment of interest. Because of logistical or budget constraints, we assume that the policymaker can choose at most $k$ sites to experiment. Based on the experimental outcomes of these sites, the policymaker will decide whether it is worthwhile to scale up the policy or treatment of interest in a set of policy-relevant sites. The experimental and policy-relevant sites may or may not overlap. How should the policymaker decide where to experiment? gechter2023site formalize the site-selection problem using a statistical decision theory framework in which, after experimentation, the policymaker observes a vector of unbiased and normally distributed estimates of the policy effects of interest at the selected experimental sites. The policy effects are allowed to be heterogeneous across sites. The policymaker is assumed to have access to a vector of baseline site-level covariates for all sites.\footnote{The baseline model assumes that the policymaker has no access to individual-level covariates. This means that the policymaker does not have enough information to estimate conditional average treatment effects (CATEs) that could be transported (e.g., via reweighting) to learn the treatment effects of interest at policy-relevant sites. At the end of Section (ref), we discuss how individual-level covarites, if available, could be used in the site-selection problem.}
{ Connection to the k-median Problem:} Under conditions that will be explained clearly in Sections (ref) and (ref), our main result (Theorem (ref)) shows that the worst-case (welfare-based) regret of any purposive sampling scheme that experiments in at most $k$ sites is approximately equal---and sometimes exactly equal---to the objective function of a $k$-median problem with the following features: the sites available for experimentation are treated as facilities; the sites where the policymaker would like to implement the new policy are treated as clients; the connection cost between clients and facilities is proportional to the Euclidean distance between corresponding site-level covariate values. Importantly, the solution of the $k$-median problem is exactly minimax-regret optimal (among purposive sampling schemes) when i) the candidate sites for experimentation and the policy-relevant sites are disjoint and ii) the treatment effect heterogeneity across sites accommodated in the parameter space is substantial (in a sense Theorem (ref) makes precise). When ii) holds but i) does not, we show that the optimized value of the $k$-median problem only approximates the minimax-regret value, and that the approximation error improves as either the number of policy-relevant sites increases or the experiments conducted become more precise. The link with the $k$-median problem established in this paper thus shows that selecting the $k$ sites that have the most central vector of covariates tends to optimize external validity (in a minimax-regret sense).
In order to formalize the connection between the site selection problem and the $k$-median problem, we leverage recent developments in the literature on treatment choice problems with partial identification yata2021,ishihara2021, olea2023decision. Note first that in the $k$-median problem, each client is typically connected to only one facility (otherwise, the connection cost would not be minimized). In the context of the site selection problem, a connection between a site $i$ (where an experiment was conducted) and a site $j$ (where no experimentation occurred) means that the estimated effects obtained in site $i$ are used to inform policy decisions in site $j$. This means that even when experimental outcomes in $k>1$ sites are available, the solution to the $k$-median problem would prescribe the policymaker to only use the information from the site with the smallest connection cost: the nearest neighbor. But when is it decision-theoretically optimal for a policymaker to behave in this way? After $k$ sites have been selected for experimentation, It turns out that, conditionally on having selected experimental sites, the policymaker faces the “evidence aggregation” problem introduced in ishihara2021 and recently discussed in yata2021, christensen2022optimal, and olea2023decision. This literature has established conditions under which it is minimax-regret optimal to base decisions on the nearest neighbor's data, provided the true treatment effects are allowed to vary substantially as a function of site-level covariates; see, for example, olea2023decision. Moreover, in this case, the optimized worst-case regret is proportional to the distance between the baseline covariates of the site of interest and those of its nearest neighbor. Thus, these results on treatment choice problems with partial identification are a building block of our decision-theoretic justification for the use of the $k$-median (clustering) problem to optimize external validity.
{ Algorithms:} The connection with the $k$-median problem clarifies the problem's difficulty but also suggests efficient algorithms. To see the need for those, recall that any purposive sampling scheme optimizes over “$n$ choose $k$” potential site combinations, where $n$ is the total number of sites available for experimentation. Optimization over purposive sampling schemes also requires the evaluation of some measure of performance that depends on the dimension of the site-level covariates, $d$. Thus, optimally choosing a purposive sampling scheme by simply evaluating the performance of each combination is costly when “$n$ choose $k$” or $d$ is large.
Conceptually, the connection with the $k$-median problem allows us to understand the computational complexity of finding a minimax-regret optimal purposive sampling scheme under the conditions of Theorem (ref). Since the $k$-median problem is known to be NP-hard kariv1979algorithmic, megiddo1984complexity,cohen2018bane, there is no algorithm for finding a minimax-regret optimal purposive sampling scheme whose computational time scales polynomially in all of the problem's inputs; namely, $(d,k,n)$.
However, from a practical perspective, it is known that the $k$-median problem admits a linear integer program formulation shmoys2011design, and is routinely solved using off-the-shelf algorithms such as different versions of the branch-and-bound method bertsimas2005optimization. In addition, different branch-and-bound algorithms either find a solution with provable optimality or, if stopped early, generate a report on the suboptimality of the solution found AOSBertsimas. As we explain later, in our application with $n=41$, $d=13$, any problem for $k \in \{1,\ldots, 10\}$ can be solved to provable optimality in just a few seconds using a personal laptop (see Figure (ref) in Section (ref)).
{ Related Literature:} Our results build on two recent papers that present novel purposive sampling strategies to select experimental sites so as to optimize external validity. gechter2023site present an elegant decision-theoretic approach that frames external validity as a policy problem and---under the assumption that the policymaker has a priori information about the effects of the new policy across sites---recommend a Bayesian approach for choosing where to experiment. egamidesigning use the principle behind synthetic control abadie2010synthetic to recommend the synthetic purposive sampling of sites; specifically, they select good donor sites whose weighted average of covariates is close to those of the sites of interest.\footnote{The idea of using the synthetic control method for experimental design was first introduced in abadie2021synthetic.} It is important to note that the site selection achieved by solving the $k$-median problem can be interpreted as a degenerate synthetic purposive sampling strategy, whereby each unit's associated synthetic unit is just its nearest neighbor.
We also contribute to the literature arguing that a “modern, decision-theoretic framework can help clarify important practical questions of experimental design” banerjee2017decision. Although decision-theoretic approaches to external validity are recent, a large body of work used statistical decision theory to analyze other aspects of experimental design such as sample size determination raiffa1961applied,manski2016sufficient,manski2019trial,azevedo2020b,azevedo2023b,hu2024minimax. Finally, our notion of external validity is conceptually related to areas of research in econometrics, machine learning, and statistics such as domain adaptation mansour2009domain, ben2010theory, distributional shifts duchi2021learning,sugiyama2007covariate,adjaho2022externally, learning under biased sampling sahoo2022learning, and cross-domain transfer estimation and performance andrews2022transfer, menzel2023transfer. To the best of our knowledge, none of these papers contains decision-theoretic analyses of where to experiment. Our site selection problem is also related to optimal regression design (e.g., sacks1984some) and kriging (e.g., stein1999interpolation); both consider a mean square error criterion with either Bayes or minimax optimality, while our approach focuses on minimax welfare regret optimality. See also karmakar2022approximation and references therein for the study of blocked randomization designs in stratified experiments to improve precision of treatment effect estimates.
{ Outline:} This paper is organized as follows. Section (ref) introduces the formal framework. Section (ref) presents our main result linking the $k$-median problem to considerations of external validity. Section (ref) presents the linear integer program formulation of the $k$-median problem. Section (ref) presents two illustrative empirical applications. Section (ref) considers extensions of the baseline model. Section (ref) concludes. Proofs of the main results can be found in Appendix (ref). Additional results are collected in the Supplementary Appendix.
A policymaker considers a set of $S \in \mathbb{N}$ candidate sites to evaluate and, eventually, implement a new policy of interest. The sites are indexed by $s \in \mathcal{S} \equiv \{1, \ldots, S\}$. For any $\tilde{\mathcal{S}}\subseteq\mathcal{S}$, let $\#\tilde{\mathcal{S}}: =\textrm{card}(\tilde{\mathcal{S}})$. In order to accommodate situations in which the policymaker is not necessarily able to experiment in all the candidate sites, we assume there is a nonempty subset $\mathcal{S}_{E} \subseteq \mathcal{S}$ of what we term experimental sites.\footnote{As discussed in allcott2015site, there are often systematic reasons determining the eligibility of certain sites for experimentation. For example, in microfinance RCT studies, experiments often require large sample sizes and well-managed microfinance institutions (MFIs), characteristics more commonly found in older and larger institutions. To qualify for clinical trials involving a new surgical procedure, hospitals and surgeons need to have both experience in the procedure and a history of low mortality rates.} Throughout the paper, and to avoid a trivial instance of the site selection problem, we assume that there are at least two experimental sites (i.e., $\#\mathcal{S}_{E} \geq 2$). It is also possible that institutional restrictions preclude the eventual implementation of the policy of interest in all of the candidate sites. Thus, it will be convenient to denote by $\mathcal{S}_{P} \subseteq \mathcal{S}$ the nonempty set of policy or policy-relevant sites.
We allow for overlap between experimental and policy sites, i.e., $\mathcal{S}_{E} \cap \mathcal{S}_{P} \neq \emptyset$. However, the case in which these sets are disjoint allows for particularly succinct analysis. This case also makes the extrapolation problem particularly stark: A policy decision must be made in sites where no experimental evaluations are available.
For each site, the policymaker observes a vector of site characteristics $X_s \in \mathbb{R}^d$ that may affect the treatment effect. Thus, we allow for treatment effect heterogeneity across sites, but we restrict this heterogeneity by assuming that it depends on observable site-level characteristics. Specifically, let the function $\tau:\mathbb{R}^d \rightarrow \mathbb{R}$ define conditional (on $X$) average treatment effects. We posit that any pair of sites with similar observed characteristics also have similar treatment effects, formally by assuming the following:
This assumption is not innocuous, but we will argue that it can be replaced by other continuity-like conditions. For example, in Section (ref), we give a version of our main results using a weaker version that includes H\"{o}lder continuous functions. Moreover, in Section (ref), we discuss how to further relax this assumption by assuming that $\tau$ belongs to a convex and centrosymmetric space of functions.\footnote{Such a restriction has been used recently in the econometrics literature to analyze estimation, inference, and other decision problems that arise in a nonparametric regression setup yata2021,armstrong2018optimal.} In Section (ref), we also discuss how Assumption (ref) can be modified to accommodate some forms of unobserved treatment heterogeneity. Perhaps it is important to note at this point that the purpose of our paper is not to present a solution to the site selection problem under the most general set of conditions on the parameter space and the statistical model. Instead, our goal is to show that under reasonable assumptions, the principle of selecting the sites that are most representative of the policy-relevant sites can be fully rationalized using a statistical decision-theoretic framework, and in addition can be implemented using off-the-shelf algorithms in optimization. We let $\textrm{Lip}_C(\mathbb{R}^d)$ denote the space of all Lipschitz functions from $\mathbb{R}^{d}$ to $\mathbb{R}$ with constant $C$.
In addition to Assumption (ref), we also impose a regularity condition on site-level covariates. That is, we assume that all observed covariates are different:
Even if this were not the case in raw data, one would presumably want to induce it by adding site fixed effects.
As in gechter2023site, the policymaker must choose a strict subset of experimental sites $\mathscr{S} \subset \mathcal{S}_{E}$.\footnote{We require $\mathscr{S}$ to be a strict subset of $\mathcal{S}_{E}$ because if we allow the policymaker to experiment in all sites, and there is no cost of experimentation that varies at the site level, then there is no site selection problem. We consider the case in which $\mathscr{S}$ is allowed to equal $\mathcal{S}_{E}$ in Section (ref).} As discussed in the introduction, we focus on the case in which there is a restriction on the total number of experimental sites that the policymaker can select. That is, there is an integer $k \in \mathbb{N}$, $k < \#\mathcal{S}_{E}$, such that $\mathscr{S}$ must belong to the set
Our notation also allows for the possibility that the policymaker does not want to experiment at all.
If the policymaker decides to experiment in a nonempty set $\mathscr{S} \in \mathcal{A}(k)$ of cardinality $\#\mathscr{S} \leq k$, then she will observe $\#\mathscr{S}$ treatment effect estimates. We collect these estimates in a vector of dimension $\#\mathscr{S}$. In a slight abuse of notation, let $\mathscr{S}_{1} < \mathscr{S}_{2} < \ldots < \mathscr{S}_{\#\mathscr{S}}$ denote the indices of the $\#\mathscr{S}$ experimental sites in $\mathscr{S}$. Letting $\widehat{\mathcal{\tau}}_{s}$ denote the estimated treatment effect in site $s$, we can define the vector
Analogously, we can denote the vector of true treatment effects for the experimental sites in $\mathscr{S}$ as
We assume that the treatment effect estimators obtained in each site are normally (and independently) distributed around the vector of true effects:
Following gechter2023site, we furthermore treat $\Sigma_{\mathscr{S}}$ as known.
The normality assumption in (ref) is unlikely to hold exactly; however, it is common to assume that treatment effect estimates from randomized controlled trials are asymptotically normal with asymptotic variances that can be estimated consistently. Treating the limiting normal model as an exact finite-sample statistical model eases exposition and allows us to focus on the core features of the site selection problem. Indeed, working directly with such a limiting model is common in applications of statistical decision theory to econometrics; see muller2011efficient and the references therein for theoretical support and applications in the context of testing problems and ishihara2021, stoye2012minimax, or tetenov2012statistical for precedents in closely related work. gechter2023site use the same statistical model, but our parameter space has a more specific form as treatment effects are controlled by the Lipschitz function $\mathcal{\tau}$.
After observing $\widehat{\mathcal{\tau}}_{\mathscr{S}}$, the policymaker chooses an action $a_s\in[0,1]$ at each policy-relevant site $s \in \mathcal{S}_{P}$. We interpret this action as the proportion of a population in the site that will be randomly assigned to the new policy. Thus, $a_s=1$ means that everyone in site $s$ is exposed to the new policy, and $a_s=0$ means that the status quo at the site is preserved. Under this interpretation, $a_s=.5$ means that 50% of the population at site $s$ will be exposed at random to the new policy; however, the formal development equally applies to either individual or population-level randomization. Our interpretation abstracts from integer issues arising with small populations.
Thus, we can define a treatment rule $T$ as a (measurable) function $T: \mathbb{R}^{\#\mathscr{S}} \rightarrow [0,1]^{\#\mathcal{S}_P}$ that maps experimental outcomes to (possibly) randomized policy actions in each of the policy-relevant sites. It will sometimes be convenient to use $T_{s}(\cdot)$ to denote the specific treatment rule for site $s \in \mathcal{S}_{P}$ implied by $T$ and $\mathcal{T}_{\mathscr{S}}$ to denote the set of all treatment rules. Note that we index the treatment rules by the selected experimental sites, $\mathscr{S}$, to be explicit about the fact that the data used to inform policy will vary depending on the choice of $\mathscr{S}$. We call $T\in \mathcal{T}_{\mathscr{S}}$ nonrandomized if for every $s \in \mathcal{S}_P$ we have $T_{s}( z ) \in\{0,1\}$ for (Lebesgue) almost every $z \in\mathbb{R}^{\#\mathscr{S}}$. Otherwise, we say that the rule is randomized. For the moment, and for the sake of exposition, we assume that there is no cost of experimentation. While this assumption is clearly unrealistic, we later show that the main conclusions of our analysis are robust to adding fixed costs to the objective function of the $k$-median problem.
Our setup only allows for treatment effect heterogeneity as a function of site-level covariates. This is partly motivated by the fact that detailed individual-level data may not be available for all sites in empirical applications. If individual-level covariates were available, and if there were no heterogeneity of CATEs (defined via individual-level characteristics) across sites, one could estimate CATEs with data from experimental sites and then reweight them to derive average treatment effects for policy-relevant sites; see, for example, the discussion in list2024optimally. In this case, many state-of-the-art methods for estimating ATE with experimental data could be employed. However, one might still be concerned about external validity, namely that those CATEs vary at the site level. A pure reweighting method would then not work, and some extrapolation would still be required. Our approach already offers a practical solution to deal with the individual-level covariates, at least in the case in which there is a single policy-relevant site: One can estimate site-specific CATEs and take $\widehat{\tau}_s$ to be the average of these CATEs over the distribution of covariates in the policy-relevant site. Then we are back to the original set-up of our problem, in which we need to decide how to aggregate these transported estimators to make policy choices in the site of interest. Since the payoff relevant parameter continues to be the site-level treatment effect, we think it is reasonable to model treatment effect heterogeneity as a function of the site-level characteristics.
We assume that the welfare of a decision rule $T$, given that sites $\mathscr{S}$ are selected for experimentation, corresponds to the average expected welfare across policy-relevant sites:
where $\mathbb{E}_{\tau_{\mathscr{S}}}[T_{s}(\widehat{\tau}_{\mathscr{S}})]$ means that the expectation is taken assuming $\widehat{\tau}_{\mathscr{S}} \sim \mathcal{N}_{\#\mathscr{S}}(\tau_{\mathscr{S}},\Sigma_{\mathscr{S}})$, and $\tau(X_{s})$ is the true treatment effect at site $s$.
The regret of policy $(T,\mathscr{S})$ equals
Our focus will be on finding the purposive sampling scheme that minimizes worst-case regret.
In the standard definition of MMR optimality, the decision maker may select randomized decision rules. Definition (ref) implies an asymmetric treatment of randomization: While we allow the policymaker to randomize policy implementation choices, we are restricting her to pick the experimental sites in a deterministic fashion. In Section (ref), we discuss challenges we encountered in trying to allow for the random selection of experimental sites.
This section presents our main result: Finding the MMR purposive sampling scheme is approximately, and sometimes exactly, equal to solving a $k$-median problem. To develop this, for each policy site $s\in\mathcal{S}_{P}$ and every $\mathscr{S}\in\mathcal{A}(k)$, denote by $N_{\mathscr{S}}(s)\in\mathscr{S}$ its nearest neighbor in $\mathscr{S}$ (or the nearest neighbor with the smallest index in case of multiplicity). That is, for every $s \in \mathcal{S}_{P}$: \[ \|X_{s} - X_{N_{\mathscr{S}}(s)} \|\leq \|X_{s} - X_{s'} \| \; \: \forall s' \in \mathscr{S}.\] Recall the following definition:
In Definition (ref), the policy-relevant sites (with indexes in $\mathcal{S}_{P}$) are clients and the experimental sites (with indexes in $\mathcal{S}_{E}$) are facilities. The connection cost between a facility $i$ and a client $j$ is the Euclidean distance $\| X_j - X_i\|$. Since the goal of the $k$-median problem is to choose the $k$ facilities that minimize connection cost, each client $s \in \mathcal{S}_{P}$ gets connected to the facility that is closest among those in $\mathscr{S}$. Hence, the term $X_{N_{\mathscr{S}}(s)}$ appears in Definition (ref). Finally, Equation (ref) can be also written as
where the equality follows from the fact that for each facility $s \in \mathcal{S}_{P}$ that is also a client $s \in \mathscr{S}$, connection cost becomes zero.
Our main result depends on treatment effect heterogeneity being possibly substantial. To formalize this, define $C^*:= \underset{\mathscr{S}\in \mathcal{A}(k), s\in\mathcal{S}_{P} \backslash \mathscr{S}}{\max}\left\{ \sqrt{\frac{\pi}{2}}\frac{\sigma_{N_{{\mathscr{S}}(s)}}}{\left\Vert X_{s}-X_{N_{{\mathscr{S}}(s)}}\right\Vert }\right\}<\infty$. Let $\sigma_{E}$ denote the largest standard deviation among the potential experimental sites. We then have:
The left-hand expression in (ref), i.e., $\inf_{T \in \mathcal{T}_{\mathscr{S}}} \sup_{\tau \in \textrm{Lip}_{C}(\mathbb{R}^{d})} \mathcal{R}(T,\mathscr{S},\tau)$, is the worst-case regret of the purposive sampling scheme $\mathscr{S}$ assuming optimality of subsequent treatment choices. Theorem (ref) thus shows that the (optimized) worst-case regret of any purposive sampling scheme can be uniformly approximated (after scaling by the factor $C/(2 \# \mathcal{S}_{P}$)) by the objective function of the k-median problem in Definition (ref), which in turn is the objective function on the right-hand side of Equation (ref). Note that our Assumption (ref) implies that the treatment effect heterogeneity between site $s$ and $s^\prime$ is governed by the product of $C$ and $\Vert X_s-X_{s^\prime}\Vert$. Given $\mathscr{S}\in \mathcal{A}(k)$, a smaller value of $\left\Vert X_{s}-X_{N_{{\mathscr{S}}(s)}}\right\Vert$ for $s\in\mathcal{S}_P$ indicates more similarity between policy and experimental sites, i.e., less treatment heterogeneity with $C$ fixed. Consequently, a larger $C^*$ is needed to allow for overall treatment heterogeneity to be substantial.\qed
Under conditions of Theorem (ref), when the candidate sites for experimentation $(\mathcal{S}_{E})$ and the policy-relevant sites $(\mathcal{S}_{P})$ are disjoint, then for any $\mathscr{S} \in \mathcal{A}(k)$:
Consequently, any solution of the $k$-median problem is then an exact minimax-regret solution for the site selection problem. This follows from the fact that if a purposive sampling scheme, $\mathscr{S}^*$, minimizes the right-hand side of Equation (ref), then it will also minimize the left-hand side, which, by Remark (ref), defines a minimax-regret optimal purposive sampling scheme. \qed
Theorem (ref) implies that even in the case where $\mathcal{S}_{E} \cap \mathcal{S}_{P} \neq \emptyset$,
is at most equal to (ref). Thus, the quality of this approximation improves as either the number of policy-relevant sites increases or the potential experiments conducted become more precise ($\sigma_E$ becomes smaller). The approximation deteriorates as $k$ increases. This happens because in approximating the worst-case regret of a purposive sampling scheme, we ignored the regret associated with sites selected for experimentation; see also further discussion of Lemma (ref) below. This means that, as $k$ increases, more sites will be ignored in our approximation and the upper bound will become looser. \qed
Theorem (ref) follows from the following two lemmas, which bound the site selection problem's MMR value from above and below.
We finish this section by mentioning that---even when experimental and policy-relevant sites are disjoint and Assumptions (ref)-(ref) hold---we were not able to find an exact MMR sampling scheme (whether purposive or randomized) for all possible values of $C$ (the Lipschitz constant that controls treatment effect heterogeneity). One challenge is that, absent enough treatment effect heterogeneity, the optimal treatment rule for each policy-relevant site will tend to aggregate information from multiple experimental sites, and will generally trade-off the representativeness of a candidate set of experimental sites (as measured by the distance between covariates) against the precision of the corresponding treatment effect estimators. To see this, consider the extreme case where there is no site-level heterogeneity; i.e., $C=0$. In this scenario, any experimental site provides an unbiased estimator for the true treatment effect in any policy-relevant site. Consequently, making policy choices for the policy-relevant sites based only on the information available for its nearest-neighbor tends to be suboptimal. One can show that for each set of experimental sites, $\mathscr{S}$, and for each policy-relevant site, $s\in\mathcal{S}_{P}$, the optimal treatment rule at the policy-relevant site $s$ is a weighted linear combination of the treatment effects in the experimental sites: \[ T_s(\widehat{\tau}_{\mathscr{S}})=\mathbf{1}\left\{ w_{\mathscr{S}}^{\top}\widehat{\tau}_{\mathscr{S}}\geq0\right\}, \textrm{ where } w_{\mathscr{S}}=\bigl(w_{\mathscr{S}_{1}},w_{\mathscr{S}_{2}},\ldots, w_{\mathscr{S}_{\#\mathscr{S}}}\bigr)^{\top} \text{ and } w_{\mathscr{S}_{i}}=\frac{1/\sigma_{\mathscr{S}_{i}}^{2}}{\sum_{i=1}^{\#\mathscr{S}}\left(1/\sigma_{\mathscr{S}_{i}}^{2}\right)}.\] That is, the optimal treatment assignment aggregates an inverse-variance weighted average of all experimental sites---which provides an efficient estimator, given the available information, of the treatment effect at any policy-relevant site $s$. Thus, the optimal sampling scheme would simply choose the $k$ sites in $\mathcal{S}_{E}$ that lead to the smallest-variance estimator of the true treatment effect.
In the more general case, where $C>0$, it is possible to characterize the optimal treatment rule at each policy-relevant site; see olea2023decision. However, this site-by-site solution only provides an upper bound on the problem's MMR value. Moreover, implementing this upper bound has the additional challenge that the ex-ante variance of the hypothetical estimate from each experimental site needs to be known.
In contrast, a strength of our $k$-median proposal is that it does not require ex-ante knowledge of these variances. In addition, for general values of $C$, our approach also provides a nontrivial upper bound on the problem's MMR value: Just i) force the treatment decision $T_s$ to only depend on site $N_{\mathscr{S}}(s)$ and ii) compute worst-case expected regret separately across sites, ignoring that the regret-maximizing parameter configurations may be mutually inconsistent across sites. Both manipulations increase regret and therefore define an upper bound, which is furthermore easy to compute for any given sampling scheme because the induced MMR treatment choice problem was solved in stoye2012minimax. For $C$ large enough, the bound will recover Theorem (ref). The caveat is that, in general, choosing the sites that minimize this bound will require brute-force enumeration.
The $k$-median problem in (ref) can be formulated as the following linear integer program shmoys2011design:
Here, the choice variables are the binary-valued $y_i$ and $x_{i,j}$ (for $i \in \mathcal{S}_{E}, j \in \mathcal{S}_{P}$); $y_i$ indicates whether site $i$ is chosen for experimentation, and $x_{i,j}$ indicates whether experimental site $i$ is used for policy choices at the policy-relevant site $j$. The total number of sites chosen for experimentation cannot exceed $k$, and site $i$ can only be used for making policy choices at policy site $j$ if site $i$ is indeed chosen for experimentation. The connection cost between facility $i$ and client $j$ is $c(j,i):=\| X_i - X_j \|$.\footnote{The connection cost in the objective function of the integer program differs from the connection cost in the $k$-median problem in (ref) by a constant factor $C/(2 \#\mathcal{S}_P)$, which does not affect the solution of the $k$-median problem. Solving the linear integer program described above is equivalent to solving (ref).}
A major advantage of this integer programming formulation is that most ecosystems for scientific computing offer different solvers for linear and nonlinear integer programs. For the applications in this paper, we use the MIP solver in Gurobi gurobi through the Python package gurobipy. The Gurobi software is highly optimized, especially for large-scale problems, and it offers an academic license. Even though the scale of the applications presented in Section (ref) is not large enough for the efficiency advantages of Gurobi to become salient over other solvers, we wanted to showcase its ease of use. It also integrates seamlessly with Google Colab, providing us a way to build self-contained and reproducible examples.\footnote{\href{https://colab.research.google.com/}{https://colab.research.google.com/}}
The MIP solver uses a version of the branch-and-bound algorithm; see bertsimas2005optimization, Chapter 11.1, for a general description of this algorithm. Broadly speaking, this algorithm works by first finding the solution to the linear programming (LP) relaxation of the original integer problem. This is known as the relaxation step. Then, the problem is split into two sub-problems (branching) according to the integer constraints. This gives bounds on the integer solution; the algorithm is applied recursively until the lower bound and the upper bound converge up to a tolerance parameter. The recursion creates nodes, and there are some strategies to determine which nodes should be explored further; for example, nodes that have integer solutions do not require any more branching.
Gurobi implements several additional steps that help the branch-and-bound algorithm be more efficient.\footnote{See \href{https://www.gurobi.com/resources/mixed-integer-programming-mip-a-primer-on-the-basics/}{https://www.gurobi.com/resources/mixed-integer-programming-mip-a-primer-on-the-basics/}.} The presolve step reduces the number of effective constraints of the problem by checking if the integer requirement can eliminate some of them. As the name suggests, it is performed before the start of the branch-and-bound algorithm. Cutting planes tightens the feasible region by adding linear inequalities to eliminate fractional solutions; it is performed during the branch-and-bound process, and for this reason, the algorithm used by Gurobi can be referred to as a version of a “branch-and-cut" algorithm. Finally, the MIP solver implements several heuristics, for example by rounding the component of a solution that is closest to an integer, fixing it, and hoping the other components will converge to integers more quickly.
In principle, one can always solve (ref) by enumerating all possible size $k$ subsets of $\mathcal{S}_{E}$. Such an algorithm runs in time proportional to ${{\#\mathcal{S}_{E}}\choose{k}} \cdot \#\mathcal{S}_{P} \cdot k \cdot d$ and therefore scales poorly when ${{\#\mathcal{S}_{E}}\choose{k}}$ is large. However, we are able to evaluate the performance of our preferred solver by brute-force solving smaller but nontrivial instances of the problem, notably the entire application in Section (ref).
Figure (ref) in Appendix (ref) shows an example of the output obtained after using the MIP solver in Gurobi to solve the linear integer program for the application in Section (ref). In this example, the scale of the problem is given by $\#\mathcal{S}_E = \#\mathcal{S}_P = 15, k = 6$, and $d = 8$. We defer the details of the application to Section (ref).
While we do not use it in this paper, we finally note that there is a large literature studying efficient (polynomial-time) approximation algorithms for the $k$-median problem, going back to seminal work of charikar2002constant. A basic idea in these algorithms is to consider a linear programming relaxation of the integer program associated with the $k$-median problem shmoys2011design. Even though the scale of the problems analyzed in this paper does not require the implementation of any of these algorithms, there are several papers that present theoretical performance guarantees for them; see for example cohen2022improved and also the references in cohen2018bane. Finally, it is worth mentioning that when $k$ is fixed (and not viewed as part of the problem's input), there is an approximate algorithm that runs in time proportional to $n \cdot d$; see kumar2010linear. Such an algorithm could be useful when $n$ and $d$ are large and $k$ is small.
lee2021poverty conducted a randomized controlled trial in Bangladesh to estimate the effects of encouraging rural households to receive money transfers from migrant family members. They specifically conducted an encouragement design where poor rural households with family members who had migrated to a larger urban destination receive a 30--45 minute training about how to register and use the mobile banking service “bKash” to send instant remittances back home.
The experiment was conducted in the Gaibandha district, one of Bangladesh's poorest regions. It focused on households that had migrant workers in the Dhaka district, the administrative unit in which the capital of Bangladesh is located. lee2021poverty measured several outcomes of both receiving households and sender migrants; see their Figures 3 and 4. To give a concrete example of the measured outcomes, one question of interest is whether families that adopt the mobile banking technology are more (or less) likely to declare that the monga, the seasonal period of hunger in September through November, was not a problem for their household. lee2021poverty (Table 9, Column 7) present results for this specific variable showing that households that used a bKash account in the treatment group are 9.2 percentage points more likely to declare that monga was not a problem.
We ask: Do the findings in lee2021poverty generalize to other migration corridors, i.e., combinations of origin and destination districts, in Bangladesh? Is the corridor selected by lee2021poverty a good choice for a researcher who is concerned about external validity? Following gechter2023site, we name the corridors using a destination-origin format; for example, the migration corridor studied in lee2021poverty is “Dhaka-Gaibandha”. Figure (ref) displays this corridor along with other common ones. The $41$ migration corridors analyzed in gechter2023site are depicted as dotted lines connecting an origin and a destination.\footnote{We thank Michael Gechter for gracefully sharing part of the dataset used in gechter2023site.}
In lee2021poverty's lee2021poverty words, “[t]he particular nature of our sample potentially limits the external validity” of the analysis. In short, migration corridors differ in characteristics ranging from distance between origin and destination to cost of living and average wages. Figure (ref) presents a box plot of $d= 13$ (standardized) characteristics that gechter2023site collected for each of the $41$ migration corridors. We take these corridors to be our potential experimental and policy-relevant sites. That is, $\mathcal{S}_E = \mathcal{S}_P$, and $\#\mathcal{S}_E=\#\mathcal{S}_P = 41$. Below we present results for $k \in \{1,2\}$.
{ Selected Site when $k=1$:} When $k=1$, the selected site based on the $k$-median problem is Dhaka-Pabna. This is also the solution obtained by using the synthetic purposive sampling approach (henceforth, SPS) in egamidesigning.
Figure (ref) presents a visual comparison of the covariates of Dhaka-Pabna (blue circles) and Dhaka-Gaibandha (pink diamonds), the original site selected by lee2021poverty. The covariate values for Dhaka-Gaibandha are slightly outside the interquartile range for at least three covariates: migrant density, mean remittance, and mean household size. In comparison, all but one covariate value for Dhaka-Pabna are within the interquartile range. The figure also shows that two key covariates of Dhaka-Gaibandha are right at the edges of the interquartile range: distance between sites in the corridor (3rd quartile) and mean household income (1st quartile). One might conjecture that the effects of adopting a mobile banking technology to transfer money particularly depend on distance and household incomes, suggesting that the Dhaka-Gaibandha corridor may not be the most representative.\footnote{gechter2023site suggest that these qualities could explain the large treatment effects found by lee2021poverty.} Dhaka-Pabna has opposite features: The distance between destination and origin in this corridor is short (1st quartile) and households are relatively better off in terms of income (3rd quartile). The use of the minimax criterion might explain why a corridor with these characteristics may be a good choice for extrapolating experimental results.
Figure (ref) also presents the covariates of Dhaka-Noakhali (yellow triangles), the migration corridor selected by the Bayesian approach of gechter2023site.\footnote{By construction, the solution of gechter2023site depends on the choice of prior. The results herein reported are based on their preferred prior specification; see Section 5.3 p.p.23 in gechter2023site.} For 10 out of the 13 variables that control treatment effect heterogeneity, Dhaka-Noakhali has covariates that are typically outside the interquartile range.
{ Selected Sites when $k=2$:} When $k=2$, the $k$-median solution is to again pick Dhaka-Pabna and additionally Dhaka-Pirojpur. Figure (ref) presents the covariates of Dhaka-Pabna (filled, blue circle) and Dhaka-Pirojpur (hollow, blue circle). While four covariate values of Dhaka-Pirojpur are outside the interquartile range, they still appear more central than Dhaka-Gaibandha and Dhaka-Noakhali. However, relative to Dhaka-Pabna, the solution for $k=2$ adds a considerably less central site; Figure (ref) illustrates that this site is a good nearest neighbor for some sites that would not otherwise be well matched.
Figure (ref) presents the solutions of egamidesigning (squares) and gechter2023site (triangles).\footnote{gechter2023site impose an additional constraint on purposive sampling schemes: they require the two migration corridors selected for experimentation to have origins in different divisions. We note that both the solutions of egamidesigning and the $k$-median problem satisfy this constraint as well.} The solution of the $k$-median problem and synthetic purposive sampling are no longer the same. We also note that the two sites selected by synthetic purposive sampling differ from the site selected by this procedure when $k=1$.
Figure (ref) presents a simple visualization of optimal connections between sites under different optimality criteria. The underlying scatter plots in both panels are the same; they visualize the location of corridors in (distance, household income)-space. Panel (ref) indicates which sites were selected through solving the $k$-median problem and which of these sites any other site was matched to, where blue circles represent matches with Dhaka-Pabna and orange crosses represent matches with Dhaka-Pirojpur. Figure (ref) also presents the sites selected by gechter2023site, i.e. Dhaka-Magura and Dhaka-Noakhali, both marked with dark blue triangles. They appear close to the sites selected by the $k$-median problem, but in terms of that problem's criterion function, they only rank $455$ among $820$ candidate solutions and miss the problem's optimal value by $17\%$. Panel (ref) similarly visualizes the sites selected by egamidesigning's (egamidesigning) synthetic purposive sampling approach, i.e. Dhaka-Gopalganj (orange square) and Dhaka-Barguna (blue square).\footnote{We generated this figure by using egamidesigning's (egamidesigning) code on gechter2023site's (gechter2023site) data.} We also visualize how policy sites are matched with experimental sites: Orange crosses correspond to migration corridors that assign all of their weight to Dhaka-Gopalganj; blue circles correspond to migration corridors that assign all of their weight to Dhaka-Barguna; all other sites (gray crossed circles) assign strictly positive weights to both donor sites. This illustrates that these sampling schemes meaningfully differ. This would even be true if the synthetic purposive sampling approach were implemented but forcing degenerate (single donor) matches, because egamidesigning's (egamidesigning) approach would then reduce to a $k$-mean problem, i.e. using squared Euclidean distance as connection cost. Note also that we decided not to report how policy sites are matched with experimental sites in the Bayesian solution of gechter2024generalizing. This is simply because, under standard Gaussian process priors, the posterior mean for the treatment effect at each policy relevant site uses the information available for all experimental sites. It would be interesting to analyze whether treatment assignment rules that only use the information of some experimental sites could arise from sparsity-inducing priors such as those discussed in datta2016hierarchical.
{ Computational Costs:} The above examples are small enough so that the $k$-median problem could easily be solved by brute-force enumeration of $41$ and $820$ candidate solutions, respectively. Needless to say, such an approach would not scale---for example, in this same application, $k=10$ induces $1,121,099,408$ candidate solutions.
Indeed, Figure (ref) compares time to solve the $k$-median problem for $k \in \{1,\ldots, 10\}$ using a) the integer program formulation of the $k$-median problem in Section (ref) and b) brute-force enumeration. The MIP solver in Gurobi solves all instances of the problem to provable optimality in less than one second each. In contrast, brute-force enumeration takes approximately $5$ hours for $k = 10$.\footnote{This was run in a Windows XPS with $10$ cores and $32$GB of RAM using R. The code is parallelized, and to avoid memory issues when $k > 8$, it runs a C++ function in the background to evaluate one combination at a time. This ensures that we are giving brute-force enumeration the best chance of success. }
One potential benefit of brute-force enumeration is that one can check for multiple solutions, which actually occurred at $k=6$. In Gurobi, an ad hoc search could be conducted by modifying the \href{https://www.gurobi.com/documentation/current/refman/seed.html}{random number seed} or using the \href{https://www.gurobi.com/documentation/9.5/refman/concurrent_optimizer.html#sec:ConcurrentControl}{concurrent optimizer}, but discovery would not be guaranteed.
Figure (ref) reports the time needed to implement the synthetic purposive sampling approach of egamidesigning. This was done by using the spsR package with the option to use the Gurobi solver on the background. We consider it to be fast, taking less than $40$ seconds for $k = 10$. However, while synthetic purposive sampling can be formulated as a quadratic mixed integer program, $k$-median is linear and correspondingly faster to solve; indeed, solutions were almost instant for every $k$ up to $10$.
Our second application revisits a multi-country survey experiment originally conducted and analyzed in naumann2018attitudes and discussed in egamidesigning. The question of interest is whether native-born inhabitants of a particular country are more supportive of immigration depending on whether the potential migrants are high-skilled or low-skilled. naumann2018attitudes carried out a survey experiment in $15$ European countries listed in Figure (ref). Respondents were native-born individuals and were randomly assigned to report their attitudes towards either high-skilled (“treatment”) or low-skilled (“control”) immigrants.
While the experiments have already been conducted and outcomes of each experiment are available for all countries, we follow egamidesigning and consider the situation of a researcher that can only conduct $k=6$ experiments. We let all $15$ countries be both potential experimental and policy-relevant sites. That is, $\mathcal{S}_E = \mathcal{S}_P$, and $\#\mathcal{S}_E= \#\mathcal{S}_P = 15$.\footnote{A potential situation we have in mind is one of a researcher who would like to give policy advice to the policymakers in these countries on whether to initiate an immigration reform that could favor either high-skilled or low-skilled immigrants. The researcher knows that policymakers are interested in voters' attitudes towards these types of reforms. We assume that the researcher is only able to experiment in a subset of countries due to administrative or budget constraints, and that he/she needs to extrapolate voters' attitudes of the other policy-relevant sites based on the experimental estimates. The researcher needs to decide whether to recommend the implementation of an immigration reform directed to either high-skilled or low-skilled immigrants.}
The only data needed to solve the $k$-median problem are site-level covariates of both experimental and policy-relevant sites. We use the same covariates as egamidesigning.\footnote{These are: Gross Domestic Product (GDP), size of migrant population, unemployment rate, proportion of females, mean age, mean education, baseline level of support for immigration by the general public, and a categorical variable that indicates the subregions in Europe (i.e., South, North, East, and West). The covariate data can be accessed in the open-source software R package, \href{https://naokiegami.com/spsR}{spsR}.} They are in different scales: For example, GDP is measured in 2015 U.S. dollars, while the unemployment rate is reported in percentage points. As is commonly recommended in clustering problems and also done in egamidesigning, we standardize all of them.
When $k=6$, the $k$-median problem is solved by the Czech Republic, Denmark, France, Ireland, Spain, and Switzerland. Figure (ref) visualizes the distribution of standardized covariates, along with the sites selected by both the $k$-median and the synthetic purposive sampling approach. Four of the six selected sites are common to both approaches (Czech Republic, Denmark, Spain, Switzerland), but synthetic purposive sampling chooses Germany and the Netherlands instead of France and Ireland.
Figure (ref) visualizes the connection networks induced by the different solutions. In both panels, red circles represent countries that are selected for experimentation. The gray lines in Figure (ref) indicate the connections between the experimental sites and the policy-relevant sites that were not selected for experimentation (blue circles). For example, we can see that each policy-relevant site is connected to exactly one experimental site, i.e. its nearest neighbor; for example, the United Kingdom uses only the information of France. The connection network in Figure (ref) is considerably more dense, with all policy-relevant sites connected to more than one experimental site. For instance, the synthetic experiment for United Kingdom assigns positive weights to the Czech Republic, Netherlands, and Germany. To further aid the visual interpretation of the connection network, we color each connection differently to capture its strength. For example, for the United Kingdom, the strongest connection is to the Netherlands $(0.74)$, whereas the weakest connection of the United Kingdom is to the Czech Republic $(0.01)$.
Figure (ref) also shows that three selected countries in the $k$-median problem (Switzerland, Czech Republic, and Spain) are not connected to any of the other policy-relevant sites, suggesting that they were selected because no other country provides a close enough match for themselves. In contrast, in Figure (ref), these countries receive positive weights from at least five other countries.
{ Approximation Error in Theorem (ref):} Because experimental estimates and corresponding standard errors are available for all $15$ countries, we can compute the approximation error in Theorem (ref). Define the relative approximation error of the $k$-median approximation to MMR as
Algebraic manipulations shows that this expression is bounded from below by
and from above by
where $B \equiv \arg \max_{z \geq 0} z \Phi(-z)$. The closer the lower and upper bounds are, the better the $k$-median approximation is.
Figure (ref) displays these bounds for values of $k \in \{1, \ldots, 10\}$. As $k$ increases, the approximation becomes worse; as mentioned before, this is driven by ignoring the experimental sites themselves in bounding regret. In this application, the $k$-median solution still works relatively well when $k=6$, with a relative error of about $\pm 13\%$. As $k$ increases to $10$, the relative error is about $\pm 50\%$.\footnote{For these computations, we picked $C$ to be the smallest Lipschitz constant needed to capture the heterogeneity of estimated treatment effects in the data. That is, we pick $C$ as
where $\widehat{\tau}_s$ denote the estimated treatment effects for site $s$. It turns out that this $C$ is comfortably “large” in the sense of Theorem (ref). We provide additional details in Appendix (ref).}
We next allow for the possibility that running an experiment in a site $s \in \mathcal{S}_{E}$ has a fixed cost $c_s$. This means that the welfare of a decision rule $T$, given that sites $\mathscr{S}$ are selected for experimentation, corresponds to
Based on this welfare function, the oracle action for the policymaker is to implement the policy in any policy-relevant site $s$ for which $\tau(X_s) \geq 0$. Expected regret of $(T,\mathscr{S})$ becomes
Under the assumptions of Theorem (ref), one can show that \[ \inf_{\mathscr{S} \in \mathcal{A}(k)} \left( \inf_{T \in \mathcal{T}_{\mathscr{S}}} \sup_{\tau \in \textrm{Lip}_{C}(\mathbb{R}^{d})} \mathcal{R}_c(T,\mathscr{S},\tau) \right) \] can be approximated by $(C/2 \# \mathcal{S}_{P})$ times
and that the approximation error is the same as the one given in Theorem (ref).
The problem in (ref) is the metric uncapacitated $k$-facility location problem discussed in Remark (ref). This is a common extension of the $k$-median problem where there is a fixed cost of opening each facility. It can also be formulated as a linear integer program, namely
Just as before, the choice variable $y_i$ indicates whether facility $i$ is open, and $x_{i,j}$ indicates whether client $j$ is assigned to facility $i$. Constraints are imposed to ensure that each client $j$ is assigned to at least one facility, that there are no more than $k$ facilities in total, and that a client can only be assigned to an open facility. The connection cost between a facility $i$ and a client $j$ is still given by $\| X_i - X_j \|$, but now there is a fixed cost $c^*_i \equiv 2 c_i / C$ of opening a facility $i$. Choosing the optimal sites now requires knowledge of the Lipschitz constant $C$ as this constant appears explicitly in the fixed cost $c^*_i$. Consequently, every time a new site is considered for experimentation, there is a trade-off between its contribution to reduce regret and the fixed cost of experimentation. When $C$ is large, the fixed costs in the objective function become negligible, and the solution of the uncapacitated facility location problem can be approximated by the solution of the $k$-median problem.
So far, our analysis focused on minimizing the worst-case (welfare-based) regret among all purposive sampling schemes that select at most $k$ sites. That is, we excluded randomized (including nonuniformly randomized) sampling schemes. This is an important limitation---a widespread view among experimenters is that “the external validity of randomized evaluations for a given population (say, the population of a country) would be maximized by randomly selecting sites and, within these sites, by randomly selecting treatment and comparison groups” duflo2007using. A similar point is made in list2024optimally: “if the researcher chooses locations at random in an initial stage of the experimental design, the this will lead to generalizable results across all potential locations.”
We now extend our baseline framework (which excludes fixed costs of experimentation) to allow for randomized site selection. First, we note that whether randomization is potentially desired delicately depends on the decision-theoretic setup. For example, the optimal sampling scheme in the Bayesian setting of gechter2023site will typically be purposive. Whether randomization improves minimax regret depends on how exactly the decision problem is formulated, which can be related to what we refer to as the timing assumptions in an implicit game that the decision maker plays against a malicious “nature”. We will first clarify this observation and then provide a brief illustration of randomized solutions.
To formalize the discussion, let $M$ denote the cardinality of $\mathcal{A}(k)$. Let $\Delta \left( \mathcal{A}(k) \right)$ denote the set of all probability distributions over the $M$ elements of $\mathcal{A}(k)$. We define a randomized site selection as a probability distribution $p := (p_1, \ldots, p_{M}) \in \Delta \left( \mathcal{A}(k) \right)$. The econometrician will pick a subset from the experimental sites by drawing one realization of a distribution $p^* \in \Delta \left( \mathcal{A}(k) \right)$ that she specified. Denote the randomly selected sites by $\mathscr{S}^*$.
In our setting, whether the decision maker will want to randomize crucially depends on timing assumptions; that is, the moment in the statistical game in which nature can move. Consider first the case in which an adversarial nature may choose $\tau$ after seeing the realization of $\mathscr{S^*}$ (and knowing $\mathcal{T}_{\mathscr{S}^*}$). Then, the risk of using treatment rule $T \in \mathcal{T}_{\mathscr{S}^*}$ is \[ \mathcal{R}(T,\mathscr{S}^*,\tau) \] and the worst-case payoff becomes \[ \sup_{\tau \in \textrm{Lip}_{C}(\mathbb{R}^{d})} \mathcal{R}(T,\mathscr{S}^*,\tau). \]
The minimax problem faced by the econometrician after $\mathscr{S}^*$ has been realized is: \[ V( \mathscr{S}^* ) : = \inf_{T \in \mathcal{T}_{\mathscr{S}^*}} \sup_{\tau \in \textrm{Lip}_{C}(\mathbb{R}^{d})} \mathcal{R}(T,\mathscr{S}^*,\tau). \]
With slight abuse of notation, let $p(\mathscr{S}^*)$ denote the probability of choosing $\mathscr{S}^*$ at random under $p \in \Delta \left( \mathcal{A}(k) \right)$. The (ex ante) expected payoff of any randomized site selection is \[ \sum_{ \mathscr{S}^* \in \mathcal{A}(k) } p(\mathscr{S}^*) \cdot V(\mathscr{S}^*), \] and the optimal randomized site selection solves \[ \inf_{p \in \Delta(\mathcal{A}(k))} \sum_{ \mathscr{S}^* \in \mathcal{A}(k) } p(\mathscr{S}^*) \cdot V(\mathscr{S}^*) . \] But this problem is solved by any $p$ supported on $\arg \min_{\mathscr{S}} V(\mathscr{S})$, the set of purposive sampling schemes that solve the site selection problem. If that problem's solution is unique, the policymaker will never randomize under this timing of the game. Furthermore, this “sequential” timing may feel natural in applications that we have in mind.
That said, the timing that seems more in line with Wald1950's (Wald1950) original application of the minimax principle is one in which the policymaker commits to both a randomized sampling scheme and a set of contingent (on sampling scheme) decision rules and nature adversarially picks $\tau$ before any randomization was realized. We next briefly discuss this possibility.
To see that randomization might strictly speaking be optimal, consider a stylized example where $k=1$ and the covariates of each site are equal to its index: $S_E=\{1,4\}$, and $S_P=\{2,3\}$. For simplicity, suppose furthermore that $\widehat{\tau}_s=\tau_s$, i.e. there is no sampling uncertainty in the treatment effects. This example can be solved for those combinations of sampling scheme and treatment assignment rule that achieve exact MMR. As we formally show in Appendix (ref), the exact MMR attainable by purposive sampling equals $3C/4$, whereas the exact MMR with randomized sampling equals $C/2$.\footnote{The assumption of perfect signals is for simplicity. The example is rigged to resemble cases analyzed in olea2023decision and stoye2012minimax, and we would accordingly be able to generalize it, but for our present purpose, solving for arbitrary sampling variances would only add tedium.} Thus, in principle there can be a gain to randomized sampling.
To see that solving this problem can quickly become very hard, consider now the same example, except that the experimental sites coincide with the policy sites at $\{1,2\}$. Then we can find the MMR optimal combination of purposive sampling scheme and treatment assignment rule, and we can also verify that randomized site selection will strictly reduce worst-case regret. However, we are unable to characterize the exact solution for this, still extremely structured, case.
In related work, fernandez2024 further explores the use of the Hedge Algorithm for finding the minimax regret optimal randomized site selection. Their results suggest that even if randomization is allowed, it is possible that choosing the site that is most representative for the policy-relevant site could still be approximately minimax regret optimal. Moreover, in the application they consider, the approximately optimal randomized selection schemes are far from uniform sampling.
To see how our results can allow for other types of distances, let $m(x,x^{\prime}):\mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow\mathbb{R}_{+}$ be a distance metric on $\mathbb{R}^d$.\footnote{That is, we assume that $m(x,x') > 0$ for any $x \neq x'$, and that for any $x$ we have $m(x,x)=0$. We also assume that the function is symmetric, in that $m(x,x')=m(x',x)$. And finally, we assume that $m$ satisfies the triangle inequality $m(x,x') \leq m(x,x'')+m(x',x'')$ for any $x,x',x''$. Also see dudley02. } Then, Assumption (ref) may be modified as:
For example, $m(x,x^{\prime})=\bigl((x-x^{\prime})^{\top}(x-x^{\prime})\bigr)^{1/2}$ is the Euclidean distance in Assumption (ref) and $m(x,x^{\prime})=\bigl((x-x^{\prime})^{\top}W(x-x^{\prime})\bigr)^{1/2}$ for some positive definite matrix $W$ is a weighted Euclidean distance. Choosing $m(x,x^{\prime})=\left[\tilde{m}(x,x^{\prime})\right]^{\alpha}$ for some $\alpha\in(0,1)$ and some distance measure $\tilde{m}(\cdot,\cdot)$ also effectively allows us to model $\tau$ as a H\"{o}lder continuous function of order $\alpha$ dudley02. With Assumptions (ref) and (ref), $N_{\mathscr{S}}(s)$ is understood to be a nearest neighbor in $\mathscr{S}$ measured in terms of metric $m(\cdot,\cdot)$ that appears in Assumption (ref). Moreover, $\text{Lip}_{C}(\mathbb{R}^d)$ now stands for the space of all Lipschitz functions from $\mathbb{R}^{d}$ to $\mathbb{R}$ with constant $C$, but in terms of metric $m(\cdot,\cdot)$. We here slightly abuse notation because we are not using $m$ to index the nearest-neighbor function $N_{\mathscr{S}}(s)$ or the Lipschitz functional class $\text{Lip}_{C}(\mathbb{R}^d)$ although their definitions depend on the choice of metric $m(\cdot,\cdot)$. Under a general metric $m(\cdot,\cdot)$, the $k$-median problem is simply modified as follows.
Since the proof of Theorem (ref) does not rely on any specific property of Euclidean distance (other than the fact that it is a distance), Theorem (ref) still holds after replacing the Euclidean distance $\left\Vert \cdot-\cdot\right\Vert$ with an arbitrary metric $m(\cdot,\cdot)$.
A natural question that arises in light of the objective function in (ref) is whether there is a weaker version of Assumption (ref) where $m(\cdot,\cdot)$ is not necessarily a metric. Such a result could be helpful, for example, to provide a decision-theoretic foundation for use of the k-means algorithm for site selection, which would arise by setting $m(x,x')=\| x-x'\|^2$. Unfortunately, it is known that the squared Euclidean distance is not a metric (as it violates triangle inequality). Moreover, it is also known that if one insists in having a version of Assumption (ref) with $m(x,x')=\| x-x'\|^2$, the only functions that satisfy this property in $\mathbb{R}^{d}$ are constant functions, which preclude treatment effect heterogeneity. Thus, while arbitrary Lipschitz-type conditions for general functions $m(\cdot,\cdot)$ are likely not useful, in Section (ref) we discuss the extent to which we can generate results for a further generalization of Assumption (ref) that considers a convex and centrosymmetric space of functions.
In practice, as with matching estimators, distance measures must weight covariates, but there is no obvious best way to do so, and the solution to the $k$-median problem will be sensitive to this choice. Following the literature imbens2004nonparametric,imbens2009recent,imbens2015causal, we think two metrics are reasonable: Mahalanobis metric, i.e., $m(x,x^{\prime})=\bigl((x-x^{\prime})^{\top}\Sigma_X^{-1}(x-x^{\prime})\bigr)^{1/2}$, where $\Sigma_X$ is the covariance matrix of site-level covariates; or the modification thereof that sets all off-diagonal elements of $\Sigma_X^{-1}$ to zero. Relative to Euclidean distance, the Mahalanobis metric has the advantage of being invariant to changes in the scale of covariates (and more generally, to affine transformations of covariates). However, this metric is not invariant to other transformations and it is not usually recommended for categorical variables. For alternative options, in Section (ref) below we also discuss how a structural model for treatment effects can be used naturally to define a metric $m(\cdot,\cdot)$ over covariates.
Our assumptions can also be modified to accommodate some forms of unobserved treatment heterogeneity. Instead of viewing policy effects as a function of observed covariates $X$ only, we now model the policy effects at the site level. Specifically, for each $s\in\mathcal{S}$, denote by $\tau_s\in \mathbb{R}$ the policy effect in site $s$. Then, instead of viewing $\tau$ as a function, we will let $\tau:=(\tau_1,\tau_2,...,\tau_S)^{\top}\in\mathbb{R}^{S}$ be a vector of dimension $S$ that represents the policy effects of all sites in $\mathcal{S}$. Then, Assumptions (ref) and (ref) can be replaced with the following:
Assumption (ref) allows sites with the same covariates to have different policy effects. The difference, however, is assumed to be at most $c$. We motivate Assumption (ref) using a simple linear regression model in Appendix (ref). Denote by $\mathcal{F}_{C,c}\subset \mathbb{R}^{S}$ the collection of all vectors of dimension $\mathbb{R}^{S}$ satisfying ((ref)). For this parameter class, the MMR purposive sampling scheme and treatment rule are redefined to solve
Then the purposive sampling scheme that solves (ref) can still be approximated by the solution of the $k$-median problem in Definition (ref) with a different cost function. To see this, note that the functional class $\mathcal{F}_{C,c}$ is still convex and centrosymmetric. Thus, we can show that, for the evidence aggregation problem studied in olea2023decision, the conclusion of their Proposition 1(iii) extends to $\mathcal{F}_{C,c}$ as well. Then, under Assumption (ref), Lemmas (ref) and (ref) continue to hold with minor modifications. In particular, when $C$ is large enough (with a threshold that can be exactly characterized), we have that \[ \inf_{T\in\mathcal{T}_{\mathscr{S}}}\sup_{\tau\in\mathcal{F}_{C,c}}\mathcal{R}(T,\mathscr{S},\tau)~\leq~\;\frac{B}{\#\mathcal{S}_{P}}\sum_{s\in\mathscr{S}\cap\mathcal{S}_{P}}\sigma_{s}~+~\frac{1}{\#\mathcal{S}_{P}}\sum_{s\in\mathcal{S}_{P}\backslash\mathscr{S}}\frac{Cm(X_{s},X_{N_{\mathscr{S}}(s)})+c}{2}. \] In addition, the following lower bound can also be verified to hold: \[ \inf_{T\in\mathcal{T}_{\mathscr{S}}}\sup_{\tau\in\mathcal{F}_{C,c}}\mathcal{R}(T,\mathscr{S},\tau)\geq\;\frac{1}{\#\mathcal{S}_{P}}\sum_{s\in\mathcal{S}_{P}\backslash\mathscr{S}}\frac{Cm(X_{s},X_{N_{\mathscr{S}}(s)})+c}{2}. \] These bounds imply that, even when treatment effect heterogeneity is characterized by Assumption (ref), the optimized value of the minimax problem (ref) can still be uniformly approximated by \[ \inf_{\mathscr{S} \in \mathcal{A}(k)}~\frac{1}{\#\mathcal{S}_{P}}\sum_{s\in\mathcal{S}_{P}\backslash\mathscr{S}}\frac{Cm(X_{s},X_{N_{\mathscr{S}}(s)})+c}{2}. \] When $\mathcal{S}_{E} \cap \mathcal{S}_{P} = \emptyset$, the solution to the problem above is the same as \[ \inf_{\mathscr{S} \in \mathcal{A}(k)}~\frac{1}{\#\mathcal{S}_{P}}\sum_{s\in\mathcal{S}_{P}}\frac{Cm(X_{s},X_{N_{\mathscr{S}}(s)})+c}{2}. \] This problem is equivalent to the $k$-median problem in Definition (ref), where the connection cost between sites $s$ and $s'$ is given by $m(X_{s},X_{s'})$.
Our approach can also accommodate structural models of treatment heterogeneity. To see this, let $\tau(X_s)=g(\theta,X_s)$ be the treatment effect of site $s$, built from a structural model $g(\cdot,\cdot)$ with parameters $\theta\in\Theta$ gechter2023site. Then, the site-level treatment effect is governed by $\tau:=\left\{ \tau(\cdotp)\mid\tau(\cdotp)=g(\theta,\cdotp),\theta\in\Theta\right\}$. We may define the metric \[m(x,x^\prime):=\sup_{\theta\in\Theta}\left|g(\theta,x)-g(\theta,x^{\prime})\right|,\] implying that $\tau(\cdot)$ informed by the structural model is $1$-Lipschitz continuous with respect to the redefined $m(\cdot,\cdot)$ metric. Moreover, suppose we have a plausible structural estimate $\theta^*$ derived from previous studies. One may incorporate such information by analogously defining \[m(x,x^\prime):=\sup_{\theta\in\Theta^*}\left|g(\theta,x)-g(\theta,x^{\prime})\right|,\] where $\Theta^* \subset\Theta$ is a subset of parameter values (possibly a singleton) containing $\theta^*$.
Instead of Assumption (ref), suppose $\tau(\cdotp)\in L_{cc}$, where $L_{cc}$ is a convex and centrosymmetric (i.e., $\tau(\cdotp)\in L_{cc}$ implies $-\tau(\cdotp)\in L_{cc}$) parameter space. It turns out that we can still derive a tractable upper bound for the associated MMR optimal purposive sampling scheme. For example, suppose $\mathcal{S}_{E}\cap\mathcal{S}_{P}=\emptyset$. Given $\mathscr{S}\in \mathcal{A}(k)$, let \[ \overline{I}_{s,\mathcal{\mathscr{S}}}(0):=\sup\left\{ u\in\mathbb{R}\mid\tau(X_{s})=u,\tau(X_{\mathscr{S}_{j}})=0,j=1,\ldots,\#\mathscr{S},\tau\in L_{cc}\right\} \] be the upper bound of the identified set for the treatment effect in policy relevant site $s\in\mathcal{S}_{P}$ when the treatment effects for each of the experimental sites in $\mathscr{S}$ equals 0. Applying yata2021 and olea2023decision for general convex and centrosymmetric parameter space, we may derive the following upper bound (following analogous steps of Lemma (ref)): For every $\mathscr{S}\in \mathcal{A}(k)$, whenever $\max\limits _{\mathscr{S}\in\mathcal{A}(k),s\in\mathcal{S}_{P}}\left\{ \overline{I}_{s,\mathcal{\mathscr{S}}}(0)\right\} $ is sufficiently large, we have
Therefore, one may still try to solve the site selection problem by minimizing
However, this foregoes two advantages of Lipschitz restrictions. In terms of algorithms, the objective function in ((ref)) does not give a direct connection to a distance metric given the general nature of $\overline{I}_{s,\mathcal{\mathscr{S}}}(0)$, implying additional computational burden; in terms of theory, it may be more challenging to show that the upper bound in ((ref)) is tight, while in the Lipschitz case, we are able to explicitly construct a function in $\textrm{Lip}_C(\mathbb{R}^d)$ under which the upper bound is attained (Lemma (ref)).
This paper presented a decision-theoretic justification for viewing the question of how to best choose where to experiment in order to optimize external validity as a $k$-median problem. More concretely, we presented conditions under which minimizing the worst-case, welfare-based regret among all purposive (nonrandomized) schemes that select $k$ sites is approximately equal, and can be exactly equal, to finding the $k$ most central vectors of baseline site-level covariates.
We believe there are many interesting directions for future work. For example, while we focused on purposive sampling schemes, it would be interesting to better understand the value of randomized sampling schemes and whether site-level covariates can be used to design such randomized selection with an eye on external validity. We also think that discussions around the relation between the $k$-median problem and synthetic purposive sampling of egamidesigning open interesting research directions to provide a decision-theoretic justification for the use the synthetic control of abadie2010synthetic.