The exact contents of citations.db main_text.text for this paper — one flattened LaTeX string, title through conclusion, appendix excluded, unmodified except for removing email addresses. This is what our citation measures are computed over.
105,241 characters
Externally Valid Selection of Experimental Sites via the k-Median Problem
\maketitle
\onehalfspacing
\begin{abstract}
We present a decision-theoretic justification for viewing the question of how to best choose \emph{where} to experiment in order to optimize external validity as a \emph{$k$-median problem}, a popular problem in computer science and operations research. We present conditions under which minimizing the \emph{worst-case}, welfare-based regret among \emph{all} nonrandom schemes that select $k$ sites to experiment is approximately equal---and sometimes exactly equal---to finding the $k$ most central vectors of baseline site-level covariates. The $k$-median problem can be formulated as a linear integer program. Two empirical applications illustrate the theoretical and computational benefits of the suggested procedure.
\end{abstract}
\onehalfspacing
\section{Introduction}
A common concern in randomized evaluations of new policies is their \emph{external validity}; that is, whether the estimated effects of a policy intervention carry over to new samples or populations \cite[Chapter 8,][]{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 \cite{degtiar2023review} for an overview and references and \cite{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 \emph{nonrandomly} select one or more sites. Recently, \cite{egamidesigning} and \cite{gechter2023site} argued that a research design which nonrandomly selects experimental sites---referred to broadly in the literature as \emph{purposive sampling} \cite[p. 511]{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 \emph{$k$-median problem}. This is a classical problem in computer science and operations research \citep{shmoys2011design,cohen2022improved}. Broadly speaking, in a $k$-median problem, there is a set of \emph{facilities} and a set of \emph{clients}; the goal is to open at most $k$ facilities and \emph{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, \emph{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 \emph{site-selection problem} to optimize external validity and the \emph{k-median problem}.
{\scshape The Site-Selection Problem:} Suppose that some \emph{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 \emph{policy-relevant sites}. The experimental and policy-relevant sites may or may not overlap. How should the policymaker decide where to experiment? \cite{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 \emph{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{subsection: model site selection}, we discuss how individual-level covarites, if available, could be used in the site-selection problem.}
{\scshape Connection to the k-median Problem:} Under conditions that will be explained clearly in Sections \ref{sec:notation} and \ref{sec:main}, our main result (Theorem \ref{thm:main}) shows that the \emph{worst-case} (welfare-based) \emph{regret} of \emph{any} purposive sampling scheme that experiments in at most $k$ sites is approximately equal---and \emph{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 \emph{disjoint} and ii) the treatment effect heterogeneity across sites accommodated in the parameter space is \emph{substantial} (in a sense Theorem \ref{thm:main} 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 \citep{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 \emph{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 \emph{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 \cite{ishihara2021} and recently discussed in \cite{yata2021}, \cite{christensen2022optimal}, and \cite{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, \citet[][Proposition 1]{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.
{ \scshape 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{thm:main}. Since the $k$-median problem is known to be NP-hard \citep{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 \citep[Chapter 7.7, p. 185]{shmoys2011design}, and is routinely solved using off-the-shelf algorithms such as different versions of the branch-and-bound method \citep[][Chapter 11.1]{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 \citep{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{fig:runtime} in Section \ref{section:application}).
{\scshape 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. \cite{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. \cite{egamidesigning} use the principle behind synthetic control \citep{abadie2010synthetic} to recommend the \emph{synthetic purposive sampling} of sites; specifically, they select good \emph{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 \cite{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'' \citep{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 \citep{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 \citep{mansour2009domain, ben2010theory}, distributional shifts \citep{duchi2021learning,sugiyama2007covariate,adjaho2022externally}, learning under biased sampling \citep{sahoo2022learning}, and cross-domain transfer estimation and performance \citep{andrews2022transfer, menzel2023transfer}. To the best of our knowledge, none of these papers contains decision-theoretic analyses of \emph{where} to experiment. Our site selection problem is also related to optimal regression design (e.g., \citealt{sacks1984some}) and kriging (e.g., \citealt{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 \cite{karmakar2022approximation} and references therein for the study of blocked randomization designs in stratified experiments to improve precision of treatment effect estimates.
{\scshape Outline:} This paper is organized as follows. Section \ref{sec:notation} introduces the formal framework. Section \ref{sec:main} presents our main result linking the $k$-median problem to considerations of external validity. Section \ref{section:kmedian} presents the linear integer program formulation of the $k$-median problem. Section \ref{section:application} presents two illustrative empirical applications. Section \ref{section:extensions} considers extensions of the baseline model. Section \ref{sec:conclusion} concludes. Proofs of the main results can be found in Appendix \ref{sec:app.main}. Additional results are collected in the Supplementary Appendix.
\section{Setting up the Decision Problem} \label{sec:notation}
\subsection{Notation and Assumptions}
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 \emph{experimental} sites.\footnote{As discussed in \cite{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 \emph{policy} or \emph{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 \emph{site characteristics} $X_s \in \mathbb{R}^d$ that may affect the treatment effect. Thus, we allow for \emph{treatment effect heterogeneity} across sites, but we restrict this heterogeneity by assuming that it depends on observable \emph{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:
\begin{assumption} \label{asm:Lips}
$\tau$ is a Lipschitz function (with respect to the Euclidean norm) with known constant $C$. That is, for any $x,x' \in \mathbb{R}^{d}$, $|\tau(x)-\tau(x')| \leq C \| x-x' \|,$ where $\|\cdot\|$ denotes the Euclidean norm.
\end{assumption}
\noindent This assumption is not innocuous, but
we will argue that it can be replaced by other continuity-like conditions. For example, in Section \ref{subsec:other.distance}, we give a version of our main results using a weaker version that includes \emph{H\"{o}lder continuous} functions. Moreover, in Section \ref{subsec:cc}, 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 \citep{yata2021,armstrong2018optimal}.} In Section \ref{subsec:unobserved}, we also discuss how Assumption \ref{asm:Lips} 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{asm:Lips}, we also impose a regularity condition on site-level covariates. That is, we assume that all observed covariates are different:
\begin{assumption} \label{asm:asm1}
$X_{s} \neq X_{s'} \ \forall \ s,s' \in \mathcal{S}$.
\end{assumption}
\noindent Even if this were not the case in raw data, one would presumably want to induce it by adding site fixed effects.
\subsection{Statistical Model for the Site Selection Problem} \label{subsection: model site selection}
As in \cite{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{subsection:fixed_costs}.}
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
\begin{equation*} \label{eqn:feasible_set}
\mathcal{A}(k):= \{ \mathscr{S} \subset \mathcal{S}_{E} \: | \: \#\mathscr{S} \leq k \}.
\end{equation*}
\noindent 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
\begin{equation*} \label{eqn:estimated_effects}
\widehat{\tau}_{\mathscr{S}} : = ( \widehat{\tau}_{\mathscr{S}_1} , \ldots, \widehat{\tau}_{\mathscr{S}_{\#\mathscr{S}}} )^{\top}.
\end{equation*}
Analogously, we can denote the vector of true treatment effects for the experimental sites in $\mathscr{S}$ as
\begin{equation*} \label{eqn:true_effects}
\tau_{\mathscr{S}} : = ( \tau(X_{\mathscr{S}_1}) , \ldots, \tau(X_{\mathscr{S}_{\#\mathscr{S}}}) )^{\top}.
\end{equation*}
We assume that the treatment effect estimators obtained in each site are normally (and independently) distributed around the vector of true effects:
\begin{equation} \label{eqn:stat_model}
\widehat{\tau}_{\mathscr{S}} \sim \mathcal{N}_{\#\mathscr{S}}
\left(
\tau_{\mathscr{S}} \: , \: \Sigma_{\mathscr{S}}
\right), \textrm{ where } \Sigma_{\mathscr{S}} := \operatorname{diag}(\sigma_{\mathscr{S}_1}^2,\ldots,\sigma_{\mathscr{S}_{\#\mathscr{S}}}^2).
\end{equation}
Following \cite{gechter2023site}, we furthermore treat $\Sigma_{\mathscr{S}}$ as known.
The normality assumption in \eqref{eqn:stat_model} 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 \cite{muller2011efficient} and the references therein for theoretical support and applications in the context of testing problems and \citet{ishihara2021}, \citet{stoye2012minimax}, or \citet{tetenov2012statistical} for precedents in closely related work. \cite{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 \emph{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 \emph{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}}$ \emph{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 \emph{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 \citet[][p. 493]{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.
\subsection{Welfare and Regret}
We assume that the \emph{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:
\begin{equation} \label{eqn:welfare}
\mathcal{W}(T,\mathscr{S},\tau) := \frac{1}{\# \mathcal{S}_{P}}\sum_{s \in \mathcal{S}_{P}} \tau(X_{s}) \mathbb{E}_{\tau_{\mathscr{S}}}[T_{s}(\widehat{\tau}_{\mathscr{S}})],
\end{equation}
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 \emph{regret} of policy $(T,\mathscr{S})$ equals
\begin{equation} \label{eqn:regret}
\mathcal{R}(T,\mathscr{S},\tau) := \frac{1}{\# \mathcal{S}_{P}} \sum_{s \in \mathcal{S}_{P}} \tau(X_{s}) \bigl( \mathbf{1}\{ \tau(X_s) \geq 0\} - \mathbb{E}_{\tau_{\mathscr{S}}}[T_{s}(\widehat{\tau}_{\mathscr{S}})] \bigr).
\end{equation}
Our focus will be on finding the purposive sampling scheme that minimizes worst-case regret.
\begin{defn}[\emph{MMR optimal purposive sampling scheme and treatment rule}] \label{def:mmr}
The pair $(T^*,\mathscr{S}^*) \in \mathcal{T}_{\mathscr{S}} \times \mathcal{A}(k)$ is minimax-regret (MMR) optimal among all purposive sampling schemes and treatment rules if
\begin{equation} \label{eqn:MMR}
\sup_{\tau \in \textrm{Lip}_{C}(\mathbb{R}^{d})} \mathcal{R}(T^*,\mathscr{S}^*,\tau) = \inf_{\mathscr{S} \in \mathcal{A}(k), T \in \mathcal{T}_{\mathscr{S}}} \sup_{\tau \in \textrm{Lip}_{C}(\mathbb{R}^{d})} \mathcal{R}(T,\mathscr{S},\tau).
\end{equation}
\end{defn}
In the standard definition of MMR optimality, the decision maker may select \emph{randomized} decision rules. Definition \ref{def:mmr} 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{section:extensions}, we discuss challenges we encountered in trying to allow for the random selection of experimental sites.
\begin{rem} \label{rem:double_inf}
It will sometimes be convenient to rewrite the right-hand side of \eqref{eqn:MMR} as
\[\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}(T,\mathscr{S},\tau) \right). \]
This suggests that, conceptually, the MMR problem can be solved in two steps. First, analyze the problem of policy implementation given the experimental outcomes at sites $\mathscr{S}$; then, optimize over the sites where to experiment.
This distinction is helpful because the first step is related to \citeauthor{ishihara2021}'s (\citeyear{ishihara2021} ``evidence aggregation'' problem, a key difference being that we typically have more than one policy-relevant site.
\qed
\end{rem}
\section{Main Result} \label{sec:main}
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 \emph{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:
\begin{defn}[\emph{$k$-median problem}] \label{def:k-median}
We say that a purposive sampling scheme, $\mathscr{S} \in \mathcal{A}(k)$, solves the $k$-median problem if it solves
\begin{equation} \label{eqn:k-median}
\inf_{\mathscr{S} \in \mathcal{A}(k)} \sum_{s \in \mathcal{S}_{P} } \|X_{s} - X_{N_{\mathscr{S}}(s)} \|.
\end{equation}
\end{defn}
In Definition \ref{def:k-median}, the policy-relevant sites (with indexes in $\mathcal{S}_{P}$) are \emph{clients} and the experimental sites (with indexes in $\mathcal{S}_{E}$) are \emph{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{def:k-median}. Finally, Equation \eqref{eqn:k-median} can be also written as
\begin{equation} \label{eqn:k-median_aux}
\inf_{\mathscr{S} \in \mathcal{A}(k)} \left( \sum_{s \in \mathcal{S}_{P} \cap \mathscr{S} } \|X_{s} - X_{N_{\mathscr{S}}(s)} \| + \sum_{s \in \mathcal{S}_{P} \backslash \mathscr{S} } \|X_{s} - X_{N_{\mathscr{S}}(s)} \| \right) = \inf_{\mathscr{S} \in \mathcal{A}(k)} \sum_{s \in \mathcal{S}_{P} \backslash \mathscr{S} } \|X_{s} - X_{N_{\mathscr{S}}(s)} \|,
\end{equation}
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:
\begin{theorem} \label{thm:main}
Suppose Assumptions \ref{asm:Lips}-\ref{asm:asm1} hold. If $C>C^*$, then for any $\mathscr{S} \in \mathcal{A}(k)$:
\begin{equation}
\label{eqn:main_thm}
\Bigg | \left( \inf_{T \in \mathcal{T}_{\mathscr{S}}} \sup_{\tau \in \textrm{Lip}_{C}(\mathbb{R}^{d})} \mathcal{R}(T,\mathscr{S},\tau) \right) - \frac{C}{2} \frac{1}{\# \mathcal{S}_{P}} \cdot \left( \sum_{s \in \mathcal{S}_{P} \backslash \mathscr{S} } \|X_{s} - X_{N_{\mathscr{S}}(s)} \| \right) \Bigg|
\end{equation}
is at most
\begin{equation}
B \cdot \sigma_{E} \cdot \frac{\min \{ \# \left( \mathcal{S}_{E} \cap \mathcal{S}_{P} \right) , k\} }{\# \mathcal{S}_{P}}, \label{eq:slack}
\end{equation}
where $B \equiv \arg \max_{z \geq 0} z \Phi(-z)$.
\end{theorem}
\begin{proof}
Follows directly from Lemma \ref{lem:Lemma1} and \ref{lem:Lemma2} below.
\end{proof}
The left-hand expression in \eqref{eqn:main_thm}, 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 \emph{worst-case regret} of the purposive sampling scheme $\mathscr{S}$ assuming optimality of subsequent treatment choices. Theorem \ref{thm:main} 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 \emph{k-median} problem in Definition \ref{def:k-median}, which in turn is the objective function on the right-hand side of Equation \eqref{eqn:k-median_aux}. Note that our Assumption \ref{asm:Lips} 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{thm:main}, 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)$:
\begin{equation} \label{eqn:same_objective_functions}
\inf_{T \in \mathcal{T}_{\mathscr{S}}} \sup_{\tau \in \textrm{Lip}_{C}(\mathbb{R}^{d})} \mathcal{R}(T,\mathscr{S},\tau) = \frac{C}{2} \frac{1}{\# \mathcal{S}_{P}} \cdot \sum_{s \in \mathcal{S}_{P} \backslash \mathscr{S} } \|X_{s} - X_{N_{\mathscr{S}}(s)} \| .
\end{equation}
Consequently, any solution of the $k$-median problem is then an \emph{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 \eqref{eqn:same_objective_functions}, then it will also minimize the left-hand side, which, by Remark \ref{rem:double_inf}, defines a minimax-regret optimal purposive sampling scheme. \qed
Theorem \ref{thm:main} implies that even in the case where $\mathcal{S}_{E} \cap \mathcal{S}_{P} \neq \emptyset$,
\begin{equation*}
\Bigg | \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}(T,\mathscr{S},\tau) \right) - \frac{C}{2} \frac{1}{\# \mathcal{S}_{P}} \cdot \inf_{\mathscr{S} \in \mathcal{A}(k)}\left( \sum_{s \in \mathcal{S}_{P} \backslash \mathscr{S} } \|X_{s} - X_{N_{\mathscr{S}}(s)} \| \right) \Bigg|
\end{equation*}
is at most equal to \eqref{eq:slack}. 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{lem:Lemma1} 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{thm:main} follows from the following two lemmas, which bound the site selection problem's MMR value from above and below.
\begin{lem}[Upper bound] \label{lem:Lemma1}
Suppose Assumptions \ref{asm:Lips}-\ref{asm:asm1} hold. For every $\mathscr{S} \in \mathcal{A}(k)$, there exists a constant $C(\mathscr{S})$ such that, if $C>C(\mathscr{S})$, then
\begin{equation*}
\inf_{T \in \mathcal{T}_{\mathscr{S}}} \sup_{\tau \in \textrm{Lip}_{C}(\mathbb{R}^{d})} \mathcal{R}(T,\mathscr{S},\tau) ~\leq ~\;
\frac{B}{\# \mathcal{S}_{P}} \sum_{s \in \mathscr{S} \cap \mathcal{S}_{P}} \sigma_s
~+~ \frac{C}{2} \frac{1}{\# \mathcal{S}_{P}} \sum_{s \in \mathcal{S}_{P} \backslash \mathscr{S} } \|X_{s} - X_{N_{\mathscr{S}}(s)} \| ,
\end{equation*}
where $B \equiv \arg \max_{z \geq 0} z \Phi(-z)$.
\end{lem}
\begin{proof}
See Appendix \ref{subsection:proof_Lemma1}.
\end{proof}
\begin{rem} \label{rem:uncapacitated_facility_location_remark}
Lemma \ref{lem:Lemma1} implies that the MMR value of the problem in Definition \ref{def:mmr} can be upper bounded by the solution of the \emph{uncapacitated $k$-facility location problem}.\footnote{Uncapacitated means that there is no capacity constraint on the number of clients that each facility can accommodate. See \cite[Chapter 4.5]{shmoys2011design} and \cite{zhang2007new}.} Just as in the $k$-median problem, there is a set of facilities $\mathcal{F}$ and a set of clients (or cities) $\mathcal{C}$. Now we assume that there is an opening cost $c_i \in \mathbb{R}_{+}$ associated with each facility $i \in \mathcal{F}$. The connection cost between facilities and clients is as before. The goal is to open at most $k$ facilities and connect each client to one facility so that total cost is minimized. Thus, the problem
\begin{equation*}
\inf_{\mathscr{S} \in \mathcal{A}(k)} \left( \frac{B}{\# \mathcal{S}_{P}} \sum_{s \in \mathscr{S} \cap \mathcal{S}_{P}} \sigma_s
~+~ \frac{C}{2} \frac{1}{\# \mathcal{S}_{P}} \sum_{s \in \mathcal{S}_{P} \backslash \mathscr{S} } \|X_{s} - X_{N_{\mathscr{S}}(s)} \| \right)
\end{equation*}
can be viewed as a $k$-facility location problem. Just as before, the set of facilities is $\mathcal{S}_{E}$ and the set of clients is $\mathcal{S}_{P}$. The connection cost between sites $s \in \mathcal{S}_{E}$ and $s' \in \mathcal{S}_{p}$ is $ (C/(2 \#\mathcal{S}_{P})) \| X_s- X_{s'} \|$. The opening cost for any facility $s \in \mathcal{S}_{E}$ is $(B/\#\mathcal{S}_{P}) \sigma_s$. Minimizing the upper bound in Lemma 1 is thus equivalent to solving the $k$-facility location problem. As shown in Appendix \ref{subsection:proof_Lemma1}, the upper bound arises by bounding the worst-case sum of regrets across sites by the corresponding sum of worst-case regrets. For selected sites that are both facilities and clients, the worst-case regret is obtained by solving a point-identified treatment choice problem. In this case, the optimal treatment rule for each $s \in \mathcal{S}_{P} \cap \mathscr{S}$ is to simply treat the whole population if $\hat{\tau}_s\geq0$.
For policy-relevant sites where no experiment was conducted, it is obtained by solving the partially-identified treatment choice problem in \cite{ishihara2021}, for which the optimal treatment rule for each site $s \in \mathcal{S}_{P} \backslash \mathscr{S}$, when $C>C^*$, depends only on the estimate from its nearest neighbor and may randomize \citep{yata2021,olea2023decision}. See Appendix \ref{subsection:proof_Lemma1} for the exact form of these treatment rules. When $\mathcal{S}_E$ and $\mathcal{S}_{P}$ are disjoint, the first component of the upper bound vanishes, and the bound becomes proportional to the solution of the $k$-median problem. \qed
\end{rem}
\begin{lem}[Lower bound] \label{lem:Lemma2}
Suppose Assumptions \ref{asm:Lips}-\ref{asm:asm1} hold. For every $\mathscr{S} \in \mathcal{A}(k)$:
\begin{equation*}
\inf_{T \in \mathcal{T}_{\mathscr{S}}} \sup_{\tau \in \textrm{Lip}_{C}(\mathbb{R}^{d})} \mathcal{R}(T,\mathscr{S},\tau) \geq \;
\frac{C}{2} \frac{1}{\# \mathcal{S}_{P}} \sum_{s \in \mathcal{S}_{P} \backslash \mathscr{S} } \|X_{s} - X_{N_{\mathscr{S}}(s)} \| .
\end{equation*}
\end{lem}
\begin{proof}
See Appendix \ref{subsection:proof_Lemma2}.
\end{proof}
\begin{rem}
Lemma 2 implies that the MMR value of the problem in Definition \ref{def:mmr} can be lower bounded by the solution of the \emph{k-median problem}
\begin{equation}
\label{eqn:kmedian}
\inf_{\mathscr{S} \in \mathcal{A}(k)} \left( \frac{C}{2} \frac{1}{\# \mathcal{S}_{P}} \sum_{s \in \mathcal{S}_{P} \backslash \mathscr{S} } \|X_{s} - X_{N_{\mathscr{S}}(s)} \| \right) .
\end{equation}
Theorem \ref{thm:main} thus follows by noting that the upper and lower bound match up to the \emph{opening costs} of the facilities. As noted before, the lower and upper bound match when $\mathcal{S}_{E} \cap \mathcal{S}_{P}=\emptyset$. \qed \end{rem}
\begin{rem}\label{rem:weighted.welfare}
Our results extend to non-equal weights on policy relevant sites with minor modifications.
Denote by $\omega_{s}>0$ a known weight for each site $s\in\mathcal{S}_{P}$.
Without loss of generality, assume that $\sum_{s\in\mathcal{S}_{P}}\omega_{s}=\#\mathcal{S}_{P}$.
We may define weighted welfare as
\[
\mathcal{W}^{\omega}(T,\mathscr{S},\tau):=\frac{1}{\#\mathcal{S}_{P}}\sum_{s\in\mathcal{S}_{P}}\omega_{s}\tau(X_{s})\mathbb{E}_{\tau_{\mathscr{S}}}[T_{s}(\widehat{\tau}_{\mathscr{S}})],
\]
with weighted regret
\begin{equation}
\mathcal{R}^{\omega}(T,\mathscr{S},\tau):=\frac{1}{\#\mathcal{S}_{P}}\sum_{s\in\mathcal{S}_{P}}\omega_{s}\tau(X_{s})\left(\mathbf{1}\{\tau(X_{s})\geq0\}-\mathbb{E}_{\tau_{\mathscr{S}}}[T_{s}(\widehat{\tau}_{\mathscr{S}})]\right).\label{eqn:regret}
\end{equation}
Then, the minimax-regret optimal purposive sampling scheme and treatment rule
are as in Definition \ref{def:mmr} but with the modified $\mathcal{R}^{\omega}$.
Inspecting proofs of Lemmas \ref{lem:Lemma1} and \ref{lem:Lemma2}, we find that the modified problem can be approximated by the alternative
$k$-median problem
\[
\inf_{\mathscr{S}\in\mathcal{A}(k)}\sum_{s\in\mathcal{S}_{P}}\omega_{s}\|X_{s}-X_{N_{\mathscr{S}}(s)}\|,
\]
i.e., the connection cost between client $j$ and facility $i$ is
now $\omega_{j}\|X_{j}-X_{i}\|$. Let $\omega_{P}:=\max_{s\in\mathcal{S}_{P}}\left\{ \omega_{s}\right\} $.
Theorem \ref{thm:main} can then be modified as follows: For the same
$C^{*}$ defined there and for any $\mathscr{S}\in\mathcal{A}(k)$,
\[
\Bigg|\left(\inf_{T\in\mathcal{T}_{\mathscr{S}}^{1/2}}\sup_{\tau\in\textrm{Lip}_{C}(\mathbb{R}^{d})}\mathcal{R}^{\omega}(T,\mathscr{S},\tau)\right)-\frac{C}{2}\frac{1}{\#\mathcal{S}_{P}}\cdot\sum_{s\in\mathcal{S}_{P}\backslash\mathscr{S}}\omega_{s}\|X_{s}-X_{N_{\mathscr{S}}(s)}\|\Bigg|
\]
is at most
\[
B\cdot\omega_{P}\cdot\sigma_{E}\cdot\frac{\min\{\#\left(\mathcal{S}_{E}\cap\mathcal{S}_{P}\right),k\}}{\#\mathcal{S}_{P}}.
\]
\qed\end{rem}
We finish this section by mentioning that---even when experimental and policy-relevant sites are disjoint and Assumptions \ref{asm:Lips}-\ref{asm:asm1} hold---we were not able to find an exact MMR sampling scheme (whether purposive or randomized) for \emph{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 \cite{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 \citet{stoye2012minimax}. For $C$ large enough, the bound will recover Theorem \ref{thm:main}. The caveat is that, in general, choosing the sites that minimize this bound will require brute-force enumeration.
\section{Integer Programming and the $k$-median Problem}
\label{section:kmedian}
The $k$-median problem in \eqref{eqn:kmedian} can be formulated as the following linear integer program \citep[Chapter 7.7, p. 185]{shmoys2011design}:
\begin{align*}
\min_{\{y_i,x_{i,j}\}_{i \in \mathcal{S}_{E}, j \in \mathcal{S}_{P}}} &\sum_{i \in \mathcal{S}_E, j \in \mathcal{S}_P } x_{i,j}\cdot c(j,i)\\
\text{such that } &\sum_{i \in \mathcal{S}_E} x_{i,j} = 1, \;\;\;\;\; \forall j \in \mathcal{S}_P, \\
&\sum_{i \in \mathcal{S}_E} y_i \le k,\\
& 0 \le x_{i,j} \le y_i, \;\;\;\;\; i \in \mathcal{S}_E, j \in \mathcal{S}_P,\\
& y_i \in \{0,1\}, x_{i,j} \in \{0,1\}, \;\;\;\;\; i \in \mathcal{S}_E, j \in \mathcal{S}_P.
\end{align*}
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 \eqref{eqn:kmedian} 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 \eqref{eqn:kmedian}.}
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 \texttt{MIP} solver in \texttt{Gurobi} \citep{gurobi} through the Python package \texttt{gurobipy}. The \texttt{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{section:application} is not large enough for the efficiency advantages of \texttt{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 \texttt{MIP} solver uses a version of the branch-and-bound algorithm; see \cite{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 \emph{relaxation} step. Then, the problem is split into two sub-problems (\emph{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 \emph{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.
\texttt{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 \emph{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. \emph{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 \texttt{Gurobi} can be referred to as a version of a ``branch-and-cut" algorithm. Finally, the \texttt{MIP} solver implements several \emph{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 \eqref{eqn:kmedian} 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{sec:multicountry}.
Figure \ref{fig:gurobi_output} in Appendix \ref{sec:Gurobi} shows an example of the output obtained after using the \texttt{MIP} solver in \texttt{Gurobi} to solve the linear integer program for the application in Section \ref{sec:multicountry}. 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{sec:multicountry}.
While we do not use it in this paper, we finally note that there is a large literature studying efficient (polynomial-time) \emph{approximation} algorithms for the $k$-median problem, going back to seminal work of \cite{charikar2002constant}. A basic idea in these algorithms is to consider a linear programming relaxation of the integer program associated with the $k$-median problem \citep[Chapter 7.7]{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 \cite{cohen2022improved} and also the references in \cite{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 \cite{kumar2010linear}. Such an algorithm could be useful when $n$ and $d$ are large and $k$ is small.
\section{Applications}
\label{section:application}
\subsection{Mobile Financial Services in Bangladesh}
\cite{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. \cite{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 \emph{monga}, the seasonal period of hunger in September through November, was not a problem for their household. \cite{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 \emph{monga} was not a problem.
We ask: Do the findings in \cite{lee2021poverty} generalize to other migration corridors, i.e., combinations of origin and destination districts, in Bangladesh? Is the corridor selected by \cite{lee2021poverty} a good choice for a researcher who is concerned about external validity? Following \cite{gechter2023site}, we name the corridors using a destination-origin format; for example, the migration corridor studied in \cite{lee2021poverty} is ``Dhaka-Gaibandha''. Figure \ref{fig:corridors} displays this corridor along with other common ones. The $41$ migration corridors analyzed in \cite{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 \cite{gechter2023site}.}
\begin{figure}[!ht]
\begin{center}
\includegraphics[width=\linewidth]{plots/bangladesh_migration_corridors_basic_with_lines_and_original_site.png}
\caption{Bangladesh Migration Corridors}
\label{fig:corridors}
\end{center}
{\raggedright \footnotesize \textit{Notes}: The map of Bangladesh with the origins of the migration corridors marked as light blue dots and the destinations marked as dark blue stars. Following the terminology used in \cite{gechter2023site}, \emph{origin} refers to a worker's home, and destination refers to where the worker migrates for work. The corridor where the experiment was originally implemented in \cite{lee2021poverty}, Dhaka-Gaibandha, is highlighted in yellow.}
\end{figure}
In \citeauthor{lee2021poverty}'s \citeyear{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{fig:characteristics_gechter} presents a box plot of $d= 13$ (standardized) characteristics that \cite{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\}$.
\begin{figure}[h!]
\begin{center}
\begin{subfigure}{.5\linewidth}
\centering
\includegraphics[width=\linewidth]{plots/boxplot_characteristics_k1_kmedian_Lee.png}
\caption{$k$-median}
\label{subfig:covariates_k_lee_1}
\end{subfigure}
\begin{subfigure}{.5\linewidth}
\centering
\includegraphics[width=\linewidth]{plots/boxplot_characteristics_k1_SPS_Gechter.png}
\caption{\cite{egamidesigning} and \cite{gechter2023site}}
\label{subfig:covariates_sps_gechter_1}
\end{subfigure}
\caption{Solution of the $k$-median Problem ($k=1$) and Distribution of Site-Level Covariates}
\label{fig:characteristics_gechter}
\end{center}
{\raggedright \footnotesize \textit{Notes}: For each covariate, the box represents the interquartile range (IQR), the vertical black line represents the median, and the horizontal line shows the ``theoretical minimum'' (defined as $Q_1 - 1.5$IQR) and ``theoretical maximum'' (defined as $Q_3 + 1.5$IQR). Black dots are outliers, defined as observations that fall beyond the theoretical minimum and maximum. Each panel depicts the sites selected by the different approaches when $k=1$.}
\end{figure}
{\scshape 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 \cite{egamidesigning}.
Figure \ref{subfig:covariates_k_lee_1} presents a visual comparison of the covariates of Dhaka-Pabna (blue circles) and Dhaka-Gaibandha (pink diamonds), the original site selected by \cite{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{\cite{gechter2023site} suggest that these qualities could explain the large treatment effects found by \cite{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{subfig:covariates_sps_gechter_1} also presents the covariates of Dhaka-Noakhali (yellow triangles), the migration corridor selected by the Bayesian approach of \cite{gechter2023site}.\footnote{By construction, the solution of \cite{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 \cite{gechter2023site}.} For 10 out of the 13 variables that control treatment effect heterogeneity, Dhaka-Noakhali has covariates that are typically outside the interquartile range.
{\scshape Selected Sites when $k=2$:} When $k=2$, the $k$-median solution is to again pick Dhaka-Pabna and additionally Dhaka-Pirojpur.
Figure \ref{subfig:covariates_k_2} 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{fig:hh_distance} illustrates that this site is a good nearest neighbor for some sites that would not otherwise be well matched.
Figure \ref{subfig:covariates_sps_gechter_2} presents the solutions of \cite{egamidesigning} (squares) and \cite{gechter2023site} (triangles).\footnote{\cite{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 \cite{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$.
\begin{figure}[h!]
\begin{center}
\begin{subfigure}{.5\linewidth}
\centering
\includegraphics[width=\linewidth]{plots/boxplot_characteristics_k2_kmedian.png}
\caption{$k$-median}
\label{subfig:covariates_k_2}
\end{subfigure}
\begin{subfigure}{.5\linewidth}
\centering
\includegraphics[width=\linewidth]{plots/boxplot_characteristics_k2_SPS_Gechter.png}
\caption{\cite{egamidesigning} and \cite{gechter2023site}}
\label{subfig:covariates_sps_gechter_2}
\end{subfigure}
\caption{Solution of the $k$-median Problem ($k=2$) and Distribution of Site-level Covariates}
\label{fig:characteristics_gechter_2}
\end{center}
{\raggedright \footnotesize \textit{Notes}: Box plots for the distribution of covariates among migration corridors, constructed as explained in Figure \ref{fig:characteristics_gechter}. Each panel depicts the site selected by the different approaches when $k=2$.}
\end{figure}
\begin{figure}[h!]
\begin{center}
\begin{subfigure}[b]{0.45\linewidth}
\includegraphics[width=\linewidth]{plots/distance_hh_kmedian.png}
\caption{$k$-median}
\label{subfig:hh_distance_kmedian}
\end{subfigure}
\hfill
\begin{subfigure}[b]{0.45\linewidth}
\includegraphics[width=\linewidth]{plots/distance_hh_sps.png}
\caption{\cite{egamidesigning}}
\label{subfig:hh_distance_sps}
\end{subfigure}
\caption{Optimal Experimental Sites for $k = 2$ on a Two-dimensional Covariate Plane}
\label{fig:hh_distance}
\end{center}
{\raggedright \footnotesize \textit{Notes}: Each point represents a destination-origin migration corridor (site) on the two-dimensional covariate plane, using two covariates: distance between the two ends of each corridor and average household income in the home district (where the average is taken over households with a reported migrant). The solutions of each method are indicated by the shapes of the solid dots. In Panel \ref{subfig:hh_distance_kmedian}, blue circles denote policy sites with Dhaka-Pabna as the nearest neighbor, and orange crosses represent those with Dhaka-Pirojpur as the nearest neighbor. Similarly, in Panel \ref{subfig:hh_distance_sps}, blue circles and orange crosses follow the same coding, indicating that these policy sites rely on a single experimental site for constructing their synthetic control. Additionally, gray cross-circles represent policy sites that use both experimental sites for their synthetic control.}
\end{figure}
Figure \ref{fig:hh_distance} 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{subfig:hh_distance_kmedian} 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{subfig:hh_distance_kmedian} also presents the sites selected by \cite{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{subfig:hh_distance_sps} similarly visualizes the sites selected by \citeauthor{egamidesigning}'s (\citeyear{egamidesigning}) synthetic purposive sampling approach, i.e. Dhaka-Gopalganj (orange square) and Dhaka-Barguna (blue square).\footnote{We generated this figure by using \citeauthor{egamidesigning}'s (\citeyear{egamidesigning}) code on \citeauthor{gechter2023site}'s (\citeyear{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 \citeauthor{egamidesigning}'s (\citeyear{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 \cite{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 \cite{datta2016hierarchical}.
{\scshape 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{subfig:Gurobi_vs_bruteforce} 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{section:kmedian} and b) brute-force enumeration. The \texttt{MIP} solver in \texttt{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 \texttt{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{subfig:Gurobi_vs_SPS} reports the time needed to implement the synthetic purposive sampling approach of \cite{egamidesigning}. This was done by using the \texttt{spsR} package with the option to use the \texttt{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$.
\begin{figure}[h!]
\begin{center}
\begin{subfigure}{.5\linewidth}
\centering
\includegraphics[width=\linewidth]{plots/gurobi_vs_brute_force_time.png}
\caption{Integer Program vs. Enumeration}
\label{subfig:Gurobi_vs_bruteforce}
\end{subfigure}
\begin{subfigure}{.5\linewidth}
\centering
\includegraphics[width=\linewidth]{plots/gurobi_vs_SPS_time.png}
\caption{Integer Program vs. SPS}
\label{subfig:Gurobi_vs_SPS}
\end{subfigure}
\caption{Time Needed to Solve the $k$-median Problem $k \in \{1,\ldots 10\}$}
\label{fig:runtime}
\end{center}
{\raggedright \footnotesize \textit{Notes}: Time comparison of different purposive sampling approaches. Time (vertical axis) is in minutes. The dark, blue line with circles represents the time it takes to solve the integer program in Section \ref{section:kmedian} using the \texttt{MIP} solver in \texttt{Gurobi} to provable optimality (Gurobi gives the solution in less than a second). The light, blue line with squares in Panel a) represents the time it takes to solve the $k$-median problem using brute-force enumeration. The red line with triangles in Panel b) represents the time needed to implement the synthetic purposive sampling approach using the \texttt{spsR} package.}
\end{figure}
\subsection{Multi-Country Survey Experiments in Europe}
\label{sec:multicountry}
Our second application revisits a multi-country survey experiment originally conducted and analyzed in \cite{naumann2018attitudes} and discussed in \cite{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. \cite{naumann2018attitudes} carried out a survey experiment in $15$ European countries listed in Figure \ref{fig:network}. 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 \cite{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 \cite{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}{\texttt{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 \citet{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{fig:covariates_multicntry} 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.
\begin{figure}[h!]
\begin{center}
\begin{subfigure}{.5\linewidth}
\centering
\includegraphics[width=\linewidth]{plots/boxplot_characteristics_k6_kmedian_multicountry.png}
\caption{$k$-median}
\label{subfig:boxplot_k6_kmedian_multicntry}
\end{subfigure}
\begin{subfigure}{.5\linewidth}
\centering
\includegraphics[width=\linewidth]{plots/boxplot_characteristics_k6_SPS_multicountry.png}
\caption{\cite{egamidesigning}}
\label{subfig:boxplot_k6_sps_multicntry}
\end{subfigure}
\caption{Distribution of Site-level Covariates in The Multi-Country Survey Experiment $(k = 6)$}
\label{fig:covariates_multicntry}
\end{center}
{\raggedright \footnotesize \textit{Notes}: Box plots showing the distribution of covariates among the fifteen countries. The box plots are constructed as explained in Figure \ref{fig:characteristics_gechter}. Each panel depicts the site selected by the different approaches when $k=6$. Solid shapes indicate sites that are in both the solution of the $k$-median problem and the synthetic purposive sampling approach. Hollow shapes indicate solutions that differ across methods. }
\end{figure}
Figure \ref{fig:network} 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{fig:network} 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{subfig:network-sps} 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{subfig:network-kmedian} 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{subfig:network-sps}, these countries receive positive weights from at least five other countries.
\begin{figure}[!ht]
\begin{center}
\begin{subfigure}{.5\linewidth}
\centering
\includegraphics[width=\linewidth]{plots/network_kmedian_reordered.png}
\caption{$k$-median}
\label{subfig:network-kmedian}
\end{subfigure}
\begin{subfigure}{.5\linewidth}
\centering
\raisebox{-2in}{\includegraphics[width=\linewidth]{plots/network_sps6_weighted.png}}
\caption{\cite{egamidesigning}}
\label{subfig:network-sps}
\end{subfigure}
\caption{Connection Network for $k=6$}
\label{fig:network}
\end{center}
{\raggedright \footnotesize \textit{Notes}: In Panel (\ref{subfig:network-kmedian}), a connection between a blue dot and a red dot indicates that the corresponding experimental site is the nearest neighbor of the policy site. In Panel (\ref{subfig:network-sps}), each blue dot may be connected to one or multiple red dots, indicating that the corresponding policy site uses the weighted average of one or more experimental sites to construct its synthetic control. The width and the transparency of the connection line indicate the weight that each policy site puts on the connecting experimental site.}
\end{figure}
{\scshape Approximation Error in Theorem \ref{thm:main}:} Because experimental estimates and corresponding standard errors are available for all $15$ countries, we can compute the approximation error in Theorem \ref{thm:main}. Define the \emph{relative} approximation error of the $k$-median approximation to MMR as
\begin{equation} \label{eqn:relative_approx}
\frac{\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}(T,\mathscr{S},\tau) \right)}{\frac{C}{2} \frac{1}{\# \mathcal{S}_{P}} \inf_{\mathscr{S} \in \mathcal{A}(k)}\sum_{s \in \mathcal{S}_{P} \backslash \mathscr{S} } \|X_{s} - X_{N_{\mathscr{S}}(s)} \| }.
\end{equation}
Algebraic manipulations shows that this expression is bounded from below by
\begin{equation*}
\label{eqn:approx_error_bound}
\max\left\{0, 1-\frac{B \cdot \sigma_{E} \cdot \frac{\min \{ \# \left( \mathcal{S}_{E} \cap \mathcal{S}_{P} \right) , k\} }{\# \mathcal{S}_{P}}}{\frac{C}{2} \frac{1}{\# \mathcal{S}_{P}} \inf_{\mathscr{S} \in \mathcal{A}(k)} \sum_{s \in \mathcal{S}_{P} \backslash \mathscr{S} } \|X_{s} - X_{N_{\mathscr{S}}(s)} \| } \right\},
\end{equation*}
and from above by
\begin{equation*}
\label{eqn:approx_error_upper_bound}
1+\frac{B \cdot \sigma_{E} \cdot \frac{\min \{ \# \left( \mathcal{S}_{E} \cap \mathcal{S}_{P} \right) , k\} }{\# \mathcal{S}_{P}}}{\frac{C}{2} \frac{1}{\# \mathcal{S}_{P}} \inf_{\mathscr{S} \in \mathcal{A}(k)} \sum_{s \in \mathcal{S}_{P} \backslash \mathscr{S} } \|X_{s} - X_{N_{\mathscr{S}}(s)} \| },
\end{equation*}
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{fig:approx_error} 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
\begin{equation}
\label{eqn:min_lipC}
\max_{s,s' \in \mathcal{S}_E \cup \mathcal{S}_P}\frac{|\widehat{\tau}_s - \widehat{\tau}_{s'}|}{\|X_s- X_{s'}\|},
\end{equation}
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{thm:main}. We provide additional details in Appendix \ref{subsection:LipsConstant}.}
\begin{figure}[h!]
\begin{center}
\includegraphics[width = 0.8\textwidth]{plots/approx_error_minC.png}
\caption{Approximation Error of The $k$-median Solutions}
\label{fig:approx_error}
\end{center}
{\raggedright \footnotesize \textit{Notes}: Approximation error of the $k$-median problem in terms of lower and upper bound on the fraction of the true minimax-regret solution over the $k$-median solution; cf. \eqref{eqn:relative_approx}. The Lipschitz constant is chosen to be the smallest Lipschitz constant that is needed to explain the data; cf. \eqref{eqn:min_lipC}.}
\end{figure}
\section{Extensions} \label{section:extensions}
\subsection{Fixed Costs of Experimentation} \label{subsection:fixed_costs}
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
\begin{equation*} \label{eqn:welfare_cost}
\mathcal{W}_c(T,\mathscr{S},\tau) := \frac{1}{\# \mathcal{S}_{P}} \left( \sum_{s \in \mathcal{S}_{P}} \tau(X_{s}) \mathbb{E}_{\tau_{\mathscr{S}}}[T_{s}(\widehat{\tau}_{\mathscr{S}})] - \sum_{s \in \mathscr{S}} c_s \right).
\end{equation*}
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
\begin{equation*} \label{eqn:regret_cost}
\mathcal{R}_c(T,\mathscr{S},\tau) := \frac{1}{\# \mathcal{S}_{P}} \sum_{s \in \mathscr{S}} c_s + \frac{1}{\# \mathcal{S}_{P}} \sum_{s \in \mathcal{S}_{P}} \tau(X_{s}) \left( \mathbf{1}\{ \tau(X_s) \geq 0\} - \mathbb{E}_{\tau_{\mathscr{S}}}[T_{s}(\widehat{\tau}_{\mathscr{S}})] \right).
\end{equation*}
Under the assumptions of Theorem \ref{thm:main}, 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
\begin{equation} \label{eqn:k-facility-location}
\inf_{\mathscr{S} \in \mathcal{A}(k)}\left(\sum_{s \in \mathscr{S}} \left(\frac{2}{C} \right) c_s + \sum_{s \in \mathcal{S}_{P} \backslash \mathscr{S} } \|X_{s} - X_{N_{\mathscr{S}}(s)} \| \right),
\end{equation}
and that the approximation error is the same as the one given in Theorem \ref{thm:main}.
The problem in \eqref{eqn:k-facility-location} is the \emph{metric uncapacitated $k$-facility location problem} discussed in Remark \ref{rem:uncapacitated_facility_location_remark}. 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
\begin{align*}
\min_{\{y_i,x_{i,j}\}_{i \in \mathcal{S}_{E}, j \in \mathcal{S}_{P}}} & \left( \sum_{i \in \mathcal{S}_E} y_i c^*_i + \sum_{i \in \mathcal{S}_E, j \in \mathcal{S}_P } x_{i,j}\cdot c(j,i) \right) \\
\text{such that } &\sum_{i \in \mathcal{S}_E} x_{i,j} = 1, \;\;\;\;\; \forall j \in \mathcal{S}_P, \\
&\sum_{i \in \mathcal{S}_E} y_i \le k,\\
& 0 \le x_{i,j} \le y_i, \;\;\;\;\; i \in \mathcal{S}_E, j \in \mathcal{S}_P,\\
& y_i \in \{0,1\}, x_{i,j} \in \{0,1\}, \;\;\;\;\; i \in \mathcal{S}_E, j \in \mathcal{S}_P.
\end{align*}
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.
\subsection{Random Selection of Experimental Sites}\label{subsec:randomize}
So far, our analysis focused on minimizing the worst-case (welfare-based) regret among all \emph{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 \emph{``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''} \citep[][p. 3953]{duflo2007using}. A similar point is made in \cite[p. 493]{list2024optimally}: \emph{``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 \citet{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 \emph{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 \emph{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 \emph{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 \citeauthor{Wald1950}'s (\citeyear{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{subsection:proof_randomize}, 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 \citet{olea2023decision} and \citet{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, \cite{fernandez2024} further explores the use of the \emph{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.
\subsection{Other Restrictions on Treatment Heterogeneity}\label{sec:other.resitrction}
\subsubsection{Other Distance Measure Based on Observed Covariates}\label{subsec:other.distance}
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 \citet[][p.20]{dudley02}. } Then, Assumption \ref{asm:Lips} may be modified as:
\begin{assumption}\label{asm:general.distance}
$\tau$ is a Lipschitz function (with respect to metric $m(\cdot,\cdot)$) with known constant $C$. That is, for any $x,x' \in \mathbb{R}^{d}$, $|\tau(x)-\tau(x')| \leq C m(x,x')$.
\end{assumption}
For example, $m(x,x^{\prime})=\bigl((x-x^{\prime})^{\top}(x-x^{\prime})\bigr)^{1/2}$ is the Euclidean distance in Assumption \ref{asm:Lips} 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$ \citep[][p. 56]{dudley02}.
With Assumptions \ref{asm:asm1} and \ref{asm:general.distance}, $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{asm:general.distance}. 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.
\begin{defn}\label{def:k-median-general-metric}
We say that a purposive sampling scheme, $\mathscr{S} \in \mathcal{A}(k)$, solves the $k$-median problem with a metric cost function $m(\cdot,\cdot)$ if it solves
\begin{equation} \label{eqn:k-median-general-metric}
\inf_{\mathscr{S} \in \mathcal{A}(k)} \sum_{s \in \mathcal{S}_{P} } m(X_{s}, X_{N_{\mathscr{S}}(s)}).
\end{equation}
\end{defn}
Since the proof of Theorem \ref{thm:main} does not rely on any specific property of Euclidean distance (other than the fact that it is a distance), Theorem \ref{thm:main} 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 \eqref{eqn:k-median-general-metric} is whether there is a weaker version of Assumption \ref{asm:general.distance} 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 \emph{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{asm:general.distance} 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{subsec:cc} we discuss the extent to which we can generate results for a further generalization of Assumption \ref{asm:general.distance} 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 \citep[][Section 18.5]{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{subsection:structural_model} below we also discuss how a structural model for treatment effects can be used naturally to define a metric $m(\cdot,\cdot)$ over covariates.
\subsubsection{Unobserved Treatment Heterogeneity}\label{subsec:unobserved}
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{asm:Lips} and \ref{asm:asm1} can be replaced with the following:
\begin{assumption}\label{asm:unobserved}
For any $s,s^{\prime} \in \mathcal{S}$, $s\neq s^{\prime}$,
$\tau$ satisfies:
\begin{equation}\label{eq:ass.1.alt}
|\tau_s-\tau_{s^{\prime}}| \leq C m(X_{s},X_{s^{\prime}})+c,
\end{equation}
where $C>0$ and $c>0$ are both known, and $m(\cdot,\cdot)$ is a metric.
\end{assumption}
Assumption \ref{asm:unobserved} 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{asm:unobserved} using a simple linear regression model in Appendix \ref{sec:app.unobserved}. Denote by $\mathcal{F}_{C,c}\subset \mathbb{R}^{S}$ the collection of all
vectors of dimension $\mathbb{R}^{S}$ satisfying (\ref{eq:ass.1.alt}). For this parameter class, the MMR purposive sampling scheme and treatment rule are redefined to solve
\begin{equation}\label{eq:mmr.alt}
\inf_{\mathscr{S}\in\mathcal{A}(k),T\in\mathcal{T}_{\mathscr{S}}}\sup_{\tau\in\mathcal{F}_{C,c}}\mathcal{R}(T,\mathscr{S},\tau).
\end{equation}
Then the purposive sampling scheme that solves \eqref{eq:mmr.alt} can still be approximated by the solution of the $k$-median problem in Definition \ref{def:k-median-general-metric} 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 \cite{olea2023decision}, the conclusion of their
Proposition 1(iii) extends to $\mathcal{F}_{C,c}$
as well. Then, under Assumption \ref{asm:unobserved}, Lemmas \ref{lem:Lemma1} and \ref{lem:Lemma2} 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{asm:unobserved}, the optimized value of the minimax problem \eqref{eq:mmr.alt} 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{def:k-median-general-metric}, where the connection cost between sites $s$ and $s'$ is given by $m(X_{s},X_{s'})$.
\subsubsection{Treatment Heterogeneity Implied by Structural Model} \label{subsection:structural_model}
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$ \citep{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^*$.
\subsubsection{General Convex and Centrosymmetric Class}\label{subsec:cc}
Instead of Assumption \ref{asm:Lips}, 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 \cite{yata2021} and \cite{olea2023decision} for general
convex and centrosymmetric parameter space, we may derive the following
upper bound (following analogous steps of Lemma \ref{lem:Lemma1}): 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
\begin{equation}
\inf_{T\in\mathcal{T}_{\mathscr{S}}}\sup_{\tau\in L_{cc}}\mathcal{R}(T,\mathscr{S},\tau)\leq\left(\frac{1}{2}\frac{1}{\#\mathcal{S}_{P}}\sum_{s\in\mathcal{S}_{P}}\overline{I}_{s,\mathcal{\mathscr{S}}}(0)\right).\label{eq:convex.centrosymmetric}
\end{equation}
Therefore, one may still try to solve the site selection problem by
minimizing
\begin{equation}
\inf_{\mathscr{S}\in \mathcal{A}(k)}\sum_{s\in\mathcal{S}_{P}}\overline{I}_{s,\mathcal{\mathscr{S}}}(0).\label{eq:algorithm.cc}
\end{equation}
However, this foregoes two advantages of Lipschitz restrictions. In terms of algorithms,
the objective function in (\ref{eq:algorithm.cc}) 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{eq:convex.centrosymmetric})
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{lem:Lemma2}).
\section{Conclusion}
\label{sec:conclusion}
This paper presented a decision-theoretic justification for viewing the question of how to best choose \emph{where} to experiment in order to optimize external validity as a \emph{$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 \cite{egamidesigning} open interesting research directions to provide a decision-theoretic justification for the use the synthetic control of \cite{abadie2010synthetic}.