1 Introduction↩︎

1.1 Model and Motivation↩︎

Many parameters of interest in economic models satisfy a finite number of moment conditions. The seminal paper of [1] developed a systematic approach to identification, estimation, and inference when all economic variables in the moment condition model are observable in one data set. Since then, the generalized method of moments has become an influential tool in empirical research in economics. However, researchers often do not have access to a single data set that contains observations on all variables and must rely on multiple data sources that cannot be matched; see the discussion in Section 1.3. This paper develops the first systematic method to study the identification of parameters in moment condition models using multiple data sets.

Specifically, consider the following moment model, \[\mathbb{E}_{o}\left[m\left(Y_{1},Y_{0},X;\theta^{\ast}\right)\right]=\boldsymbol{0}\text{,}\label{UnconditionalM}\tag{1}\] where \(Y_{1}\in\mathcal{Y}_{1}\subseteq\mathbb{R}^{d_{1}},Y_{0}\in\mathcal{Y}_{0}\subseteq\mathbb{R}^{d_{0}}\), and \(X\in\mathcal{X}\subseteq\mathbb{R}^{d_{x}}\) denote three distinct random variables; \(\theta^{\ast}\in\Theta\subseteq\mathbb{R}^{d_{\theta}}\) is the true unknown parameter; \(m\) is a known \(k\) dimensional moment function; and \(\mathbb{E}_{o}\) denotes the expectation with respect to the true but unknown joint distribution \(\mu_{o}\) of \(\left(Y_{1},Y_{0},X\right)\).

This paper studies identification of \(\theta^{\ast}\) (and known functions of \(\theta^{\ast}\))⁶ in a prevalent case of incomplete data in empirical research, where the relevant information on \(\left(Y_{1},Y_{0},X\right)\) is contained in two datasets, and the units of observations in different datasets cannot be matched: the first dataset identifies the distribution of \(\left(Y_{1},X\right)\) and the second dataset identifies the distribution of \(\left(Y_{0},X\right)\). We develop the first general unified methodology for studying the sharp identified set (identified set, hereafter) of \(\theta^{\ast}\) (and known functions of \(\theta^{\ast}\)) in the general moment model (1 ) with incomplete data. Our method allows for (non-additively separable) moment function of any finite dimension, parameter \(\theta^{*}\) of any finite dimension, and two arbitrary random variables \(Y_{1}\) and \(Y_{0}\), each of any finite dimension.

1.2 Main Contributions↩︎

General Contributions

The available sample information in the incomplete data scenario that we study in this paper allows identification of the distribution functions of \(\left(Y_{1},X\right)\) and \(\left(Y_{0},X\right)\), but does not identify the distribution of \(\left(Y_{1},Y_{0},X\right)\) without additional assumptions on the joint distribution of \(\left(Y_{1},Y_{0},X\right)\). For the general moment model (1 ), we establish a characterization of the identified set of \(\theta^{\ast}\) in terms of a continuum of inequalities involving conditional optimal transport (COT hereafter).⁷

For an important class of affine moment models, where the moment function \(m\left(\cdot;\theta\right)\) can be written as an affine transformation of \(\theta\) with the expectation of the linear transformation matrix being identifiable, but not the translation vector, we show that by applying our general characterization, the identified set for \(\theta^{\ast}\) in this class of models is characterized by a continuum of linear inequalities and is thus convex. Furthermore, we derive the expression of the support function of the convex identified set and show that the value of the support function in each direction can be obtained by solving a COT problem. As we demonstrate using several running examples, our novel characterization through COT allows us to make use of theoretical and computational tools for optimal transport (OT hereafter; e.g., [4], [5], [6], and [7]) to further simplify the characterization and develop computationally more tractable identified sets for specific models than the existing ones in the literature.⁸ The well-known Fréchet problem reviewed in Section 1.3 is a simple example of an affine moment model to which our characterization of the identified set applies. We show in Section 3.2 that bounding causal effect in [12] is an example of the Fréchet problem and the COTs in our characterization provide closed-form expressions for the dual optimizations in Corollary 1 in [12].⁹

To take full advantage of our results for affine moment models, we propose a two-step procedure to obtain the identified set of the parameter of interest. In the first step of this procedure, we construct an auxiliary parameter that satisfies an affine moment model and establish its identified set. The auxiliary parameter is chosen so that the parameter of interest can be written as a known transformation of the auxiliary parameter. In the second step, we compute the identified set of the parameter of interest from the known transformation of the convex identified set obtained in the first step. The two-step procedure substantially broadens the applicability of our results, since it applies to parameters of interest that may not even satisfy the moment model (1 ) as we illustrate via the algorithmic measures in Examples 2 and 3.

Results for Running Examples

To demonstrate the versatility and advantages of our general method and the proposed two-step procedure, we study three examples of partially identified parameters with incomplete data and establish their identified sets using our approach. We show that our method leads to novel and significantly improved results in all examples compared with those in the literature.

Example 1 is a linear projection model. We consider two different types of sample information, where the first extends that in [17] and [18]; the second data structure extends that in [19]. The moment function is, in general, not affine, and the identified set of the parameter of interest may not be convex. We employ the proposed two-step procedure, where like [18], we express the parameter of interest as a known function of an unknown parameter \(\theta^{\ast}\) satisfying an affine moment model. In the first step, we show that the identified set of \(\theta^{\ast}\) is convex and its support function is given by an integral of COT with quadratic costs, the most studied OT problem; see [20], [6], and [7]. In the second step, we obtain the identified set of the parameter of interest from that of \(\theta^{*}\). Using Proposition 2.17 in [6], we show that when specialized to the model in [17], our identified set reduces to that in [17]. When specialized to [18], our result leads to the identified set that is a proper subset of the superset proposed in [18]. Based on our characterization of the identified set, we also propose a computationally simpler outer set that is also a subset of the superset in [18].

Examples 2 and 3 are two algorithmic measures first studied in [21] (KMZ, hereafter) in the data combination setup. The measures themselves do not satisfy the moment model (1 ). To apply our results, we first express them as known transformations of some auxiliary parameter \(\theta^{*}\), such that \(\theta^{*}\) satisfies model (1 ) with an affine moment function. Consequently, the two-step procedure applies, and the results we establish for the identified set of affine models apply to \(\theta^{*}\) in both examples. Specifically, for Example 2 on the demographic disparity (DD) measure, we provide a closed-form expression for the support function of the identified set for any collection of DD measures and any number of protected classes. Furthermore, we show that the identified set is a polytope with a closed-form expression for its vertices. For the specific collection of DD measures studied in KMZ, our closed-form expression solves the infinite dimensional linear programming formulation in KMZ. We analyze the theoretical time complexity of both our support function and vertex-based procedures and show that they are significantly faster than KMZ’s method. Using the empirical example in KMZ, we demonstrate that the improvement can be over 15,000-fold.

For the true-positive rate disparity (TPRD) measure in Example 3, KMZ propose to construct the convex hull of the identified set. They characterize the support function of the convex hull through a computationally costly, NP-hard non-convex optimization problem. Choosing the auxiliary parameter vector \(\theta^{\ast}\) cleverly, we express the identified set for any finite number of TPRD measures as a continuous map of the identified set for \(\theta^{\ast}\), where the identified set for \(\theta^{\ast}\) is convex. Consequently, the identified set for any finite number of TPRD measures is connected, and any single TPRD measure is a closed interval regardless of the number of protected classes. For a single TPRD measure, we provide closed-form expressions for the lower and upper bounds of the closed interval extending the result in KMZ developed for two protected classes. For multiple TPRD measures, we demonstrate that the support function of the identified set for the auxiliary parameter \(\theta^{\ast}\) can be computed through a conditional partial optimal transport problem. Technically, we show that the conditional partial OT problem always admits a solution with monotone support. Exploring the monotone support of the solution, we develop a novel algorithm, called Dual Rank Equilibration AlgorithM (DREAM), for computing the identified set for \(\theta^{\ast}\) and for any collection of TPRD measures. We establish its theoretical time complexity and demonstrate that DREAM is faster than linear programming using the empirical example in KMZ.

1.3 Related Work↩︎

Data combination problems are pervasive in applied work. Examples include studies of the effect of age at school entry on the years of schooling by combining data from the US censuses in 1960 and 1980 ([22]); differentiated product demand using both micro and macro survey data ([23]); studies of long-run returns to college attendance using PSID/NLSY and Addhealth data ([13], [14]); repeated cross-sectional data in difference-in-differences designs ([24]); evaluations of long-term treatment effects combining experimental and observational data ([25]); algorithmic fairness analysis where decision outcomes and protected attributes are recorded in separate datasets ([21]); study of neighborhood effects, where longitudinal residence information and information on individual heterogeneity are contained in separate datasets ([18]); inter-generational income mobility, where linked income data across generations are often unavailable ([26]); consumption research, where income and consumption are often measured in two different datasets ([27]); and counterfactual analyses of actual choice using stated and revealed preference data ([12]).

Existing works in the incomplete data case fall into two broad categories. The first category considers the case where the moment function is additively separable in \(Y_{1}\) and \(Y_{0}\) and establishes point identification of \(\theta^{\ast}\) under weak conditions. See, e.g., [22], [28], [29], [30], and [25].

The second category develops partial identification results for specific models. Except for the running examples we describe below, most existing work studying partial identification under data combination can be reformulated as examples of a special case of model (1 ), where the moment function is \[m\left(y_{1},y_{0},x;\theta\right)=\theta-h\left(y_{1},y_{0}\right)\label{Eq:32Univariate}\tag{2}\] for a known function \(h\) of dimension \(k=1\). Equivalently, \(\theta^{\ast}=\mathbb{E}_{o}\left[h\left(Y_{1},Y_{0}\right)\right]\). For univariate \(Y_{1}\) and \(Y_{0}\) with given marginals, computing lower and upper bounds for \(\theta^{*}\) for a known function \(h\) has a long history in probability literature, and is referred to as the (general) Fréchet problem; see [31] and Section 3 in [32] for a detailed discussion of this problem, including early references and its relation to copulas. These bounds have been used to establish identified sets for \(\theta^{*}\) in a broad range of applications, including distributional treatment effects in program evaluation and bivariate option pricing in finance; see e.g., [33], [34], [35], [36], and [37]. More recently, [38] study identification in model (1 ) with general moment function \(m\) and univariate \(Y_{1}\) and \(Y_{0}\) via the copula approach and propose a valid inference procedure.¹⁰ However, the copula approach is limited to univariate \(Y_{1}\) and \(Y_{0}\). For multivariate \(Y_{1}\) and \(Y_{0}\), the lower and upper bounds on \(\theta^{*}\) are defined by COTs with ground cost function \(h\) or \(-h\). [39] propose consistent estimation using the primal formulation of COT, while [40] study estimation and inference using their dual formulation.

Organization

Section 2 introduces our sample information and three motivating examples. In Section 3, we first characterize the identified set for \(\theta^{\ast}\) in our model (1 ) in terms of a continuum of inequalities, and then study the properties of the identified set for the special class of affine moment models. Finally, we apply our characterization to the Fréchet problem in (2 ) and revisit [12]. Sections 4 to 6 apply our general results to each of the motivating examples. The last section offers some concluding remarks. Technical proofs are relegated to Appendix 9. Appendix 10 contains additional results on each motivating example.

Notation

We let \(\boldsymbol{0}\) denote the zero vector and \(I_{d}\) denote the identity matrix of dimension \(d\times d\). We use \(\mathbb{1}\left\{ \cdot\right\}\) to denote the indicator function. For any vector \(v\in\mathbb{R}^{d}\), we use \(\left\Vert v\right\Vert\) to denote its Euclidean norm. We denote \(\mathbb{S}^{d}\) as the unit sphere of dimension \(d\). For any function \(h\) and measure \(\mu\), we denote \(\int \vert h\vert d\mu < \infty\) by \(h \in L^{1}(\mu)\). For any cumulative distribution function \(F\) defined on \(\mathbb{R}\), we let \(F^{-1}\left(t\right)\equiv\inf\left\{ x:F\left(x\right)\geq t\right\}\) denote the quantile function. For any two random variables \(W\) and \(V\), we use \(F_{W\mid v}^{-1}\left(\cdot\right)\) to denote the quantile function derived from the distribution of \(W\) conditioning on \(V=v\).

2 Model and Motivating Examples↩︎

Our model is defined by (1 ) and Assumption 1 below, where \(\mu_{1X}\) and \(\mu_{0X}\) denote probability distributions of \(\left(Y_{1},X\right)\) and \(\left(Y_{0},X\right)\), respectively.

We maintain Assumption 1 throughout the paper. To avoid the trivial case, we assume that \(d_{1}\geq1\) and \(d_{0}\geq1\), but \(d_{x}\geq0\). If \(d_{x}=0\), then there is no common \(X\) in both datasets. Assumption 1 (iii) can be interpreted as a comparability assumption. Consider, for example, the first dataset that contains only observations on \(\left(Y_{1},X\right)\). Since \(Y_{0}\) is missing, the distribution of \(\left(Y_{0},X\right)\) is not identifiable. Assumption 1 (iii) requires the underlying probability distribution of \(\left(Y_{0},X\right)\) in the first dataset to be the same as the one of \(\left(Y_{0},X\right)\) in the second dataset. The latter probability distribution \(\mu_{0X}\) is identifiable because the second dataset contains observations on \(\left(Y_{0},X\right)\). Furthermore, it implies that the distribution of \(X\) in both datasets is the same.

In the rest of this section, we present three motivating examples and use them to illustrate our main results throughout the paper.

3 Identified Set for \(\theta^{\ast}\) and its COT Characterization↩︎

Let \(\Theta_{I}\subseteq\Theta\) denote the identified set for \(\theta^{\ast}\). It is defined as \[\Theta_{I}\equiv\left\{ \theta\in\Theta:\mathbb{E}_{\mu}\left[m\left(Y_{1},Y_{0},X;\theta\right)\right]=\boldsymbol{0}\text{ for some }\mu\in\mathcal{M}\left(\mu_{1X},\mu_{0X}\right)\right\} ,\label{Def::32Theta32I}\tag{6}\] where \(\mathbb{E}_{\mu}\) denotes the expectation taken with respect to some probability measure \(\mu\in\mathcal{M}\left(\mu_{1X},\mu_{0X}\right)\), and \(\mathcal{M}\left(\mu_{1X},\mu_{0X}\right)\) is the class of probability measures whose projections on \(\left(Y_{1},X\right)\) and \(\left(Y_{0},X\right)\) are \(\mu_{1X}\) and \(\mu_{0X}\).

Equivalently, the identified set \(\Theta_{I}\) can be defined via conditional distributions. Let \(\mu_{1\mid x}\) and \(\mu_{0\mid x}\) be the conditional distributions of \(Y_{1}\) on \(X=x\) and \(Y_{0}\) on \(X=x\), respectively. Denote \(\mu_{X}\) as the probability distribution of \(X\). Recall that \(\mathcal{Y}_{1}\), \(\mathcal{Y}_{0}\), and \(\mathcal{X}\) are the supports of random variables \(Y_{1}\), \(Y_{0}\), and \(X\). For any \(x\in\mathcal{X}\), let \(\mathcal{M}\left(\mu_{1\mid x},\mu_{0\mid x}\right)\) denote the class of probability distributions whose projections on \(Y_{1}\) and \(Y_{0}\) are \(\mu_{1\mid x}\) and \(\mu_{0\mid x}\).¹² The identified set \(\Theta_{I}\) defined in (6 ) can be equivalently expressed as \[\Theta_{I}=\left\{ \theta\in\Theta:\begin{array}{c} \int\left[\int\int m\left(y_{1},y_{0},x;\theta\right)d\mu_{10\mid x}\left(y_{1},y_{0}\right)\right]d\mu_{X}\left(x\right)=\boldsymbol{0}\text{ }\\ \text{ for some }\mu_{10\mid x}\in\mathcal{M}\left(\mu_{1\mid x},\mu_{0\mid x}\right)\textrm{ for any }x\in\mathcal{X} \end{array}\right\} .\label{Def::32Theta95I32Conditioning}\tag{7}\] To simplify the notation, from now on, we omit the integration variables when there is no confusion.

3.1 A General Characterization of \(\Theta_{I}\) via COT↩︎

This section provides a COT approach to characterize the identified set for \(\theta^{*}\) in model (1 ). Consider the following set defined through a continuum of inequalities: \[\begin{align} & \Theta_{o}=\left\{ \theta\in\Theta:\int\mathcal{KT}_{t^{\top}m}\left(\mu_{1\mid x},\mu_{0\mid x};x,\theta\right)d\mu_{X}\leq0\text{ for all }t\in\mathbb{S}^{k}\right\} \textrm{, where }\label{Def::Theta95o32Conditioning}\\ & \mathcal{KT}_{t^{\top}m}\left(\mu_{1\mid x},\mu_{0\mid x};x,\theta\right)\equiv\inf_{\mu_{10\mid x}\in\mathcal{M}\left(\mu_{1\mid x},\mu_{0\mid x}\right)}\int\int t^{\top}m\left(y_{1},y_{0},x;\theta\right)d\mu_{10\mid x}.\nonumber \end{align}\tag{8}\] For any given \(x\in\mathcal{X}\) and \(\theta\in\Theta\), \(\mathcal{KT}_{t^{\top}m}\left(\mu_{1\mid x},\mu_{0\mid x};x,\theta\right)\) is the COT cost between conditional measures \(\mu_{1\mid x}\) and \(\mu_{0\mid x}\) with (ground) cost function \(t^{\top}m\left(y_{1},y_{0},x;\theta\right)\). Here we state the explicit dependence of \(\mathcal{KT}_{t^{\top}m}\left(\mu_{1\mid x},\mu_{0\mid x};x,\theta\right)\) on \(x\) and \(\theta\) because the cost function \(t^{\top}m\left(y_{1},y_{0},x;\theta\right)\) is allowed to depend on \(x\) and \(\theta\). With the following assumption, we show that \(\Theta_{I}=\Theta_{o}\).

Assumption 2 (i) holds automatically when the supports of \(\mu_{0\mid x}\) and \(\mu_{1\mid x}\) are finite for every \(x\in\mathcal{X}\), i.e., \(\mu_{0\mid x}\) and \(\mu_{1\mid x}\) are discrete measures, because any function on a finite set is continuous. Assumption 2 (ii) is satisfied if \(m\) is bounded. It also holds if \(m\) does not depend on \(x\), both \(\mathcal{Y}_{1}\) and \(\mathcal{Y}_{0}\) are bounded, and Assumption 2 (i) holds. As a result, Examples 2 and 3 satisfy Assumption 2. For Example 1, the moment function satisfies Assumption 2 (ii) if \(\mathbb{E}\left[\left\Vert Y_{1}\right\Vert ^{2}\right]<\infty\) and \(\mathbb{E}\left[\left\Vert Y_{0}\right\Vert ^{2}\right]<\infty\).

Proofs of theorems and propositions in this paper are provided in the appendix. The proof of Theorem 1 relies on the minimax theorem derived in [42] and the result on the weak compactness of \(\mathcal{M}\left(\mu_{1\mid x},\mu_{0\mid x}\right)\) in the proof of Proposition 2.1 in [43].

Theorem 1 characterizes the identified set for \(\theta^{\ast}\) via a continuum of inequality constraints on the integral of the COT cost \(\mathcal{KT}_{t^{\top}m}\left(\mu_{1\mid x},\mu_{0\mid x};x,\theta\right)\) with respect to \(\mu_{X}\). This novel characterization allows us to explore both theoretical and computational tools, including duality theory developed in the OT literature, to study the identified set \(\Theta_{I}\); see e.g., [4], [5], [6], and [7].

Covariate-Assisted Identified Set

The conditioning variable \(X\) provides information on the joint distribution of \(\left(Y_{1},Y_{0}\right)\) by restricting the conditional distributions of \(Y_{1}\) on \(X=x\) and \(Y_{0}\) on \(X=x\) to be \(\mu_{1\mid x}\) and \(\mu_{0\mid x}\), which are identifiable from the datasets. The identified set obtained using only subvectors of \(X\) can be potentially larger than the covariate-assisted identified set, which explores the information of the full vector \(X\).

Partition \(X\equiv\left(X_{p},X_{np}\right)\), where \(X_{p}\in\mathbb{R}^{d_{x_{p}}}\) and \(X_{np}\in\mathbb{R}^{d_{x_{np}}}\). Suppose that the moment function only depends on \(X_{p}=x_{p}\) and denote it as \(m\left(y_{1},y_{0},x_{p};\theta\right)\). This includes Fréchet problem (2 ) and Examples 1-3 for \(d_{x_{p}}=0\). Denote by \(\mu_{1\mid x_{p}}\) and \(\mu_{0\mid x_{p}}\) the conditional distributions of \(Y_{1}\) and \(Y_{0}\) on \(X_{p}=x_{p}\), respectively. Let \(\mu_{X_{p}}\) be the probability distribution of \(X_{p}\). Define the following set constructed using only \(X_{p}\): \[\begin{align} & \Theta^{O}=\left\{ \theta\in\Theta:\int\mathcal{KT}_{t^{\top}m}\left(\mu_{1\mid x_{p}},\mu_{0\mid x_{p}};x_{p},\theta\right)d\mu_{X_{p}}\leq0\text{ for all }t\in\mathbb{S}^{k}\right\} \textrm{, where }\\ & \mathcal{KT}_{t^{\top}m}\left(\mu_{1\mid x_{p}},\mu_{0\mid x_{p}};x_{p},\theta\right)\equiv\inf_{\mu_{10\mid x_{p}}\in\mathcal{M}\left(\mu_{1\mid x_{p}},\mu_{0\mid x_{p}}\right)}\int\int t^{\top}m\left(y_{1},y_{0},x_{p};\theta\right)d\mu_{10\mid x_{p}}. \end{align}\] The following proposition shows that \(\Theta_{I}\) is at most as large as \(\Theta^{O}\).

Proposition 1 extends Theorem 3.3 in [36] established for Fréchet problem (2 ) with univariate \(Y_{1}\) and \(Y_{0}\). As long as \(X_{np}\) is not independent of both \(Y_{1}\) and \(Y_{0}\), we expect the covariate-assisted identified set \(\Theta_{I}\) to be smaller than \(\Theta^{O}\). In general, the stronger \(X\) and \(Y_{1}\) (or \(Y_{0}\)) are dependent on each other, the smaller is the covariate-assisted identified set for \(\theta^{\ast}\). The second part of the proposition shows that if the conditional measure \(\mu_{0\mid x}\) is Dirac at \(g_{0}(x)\), then \(\Theta_{I}\) reduces to the identified set for the moment model with complete data \((Y_{1},X)\). Therefore, when one of \(Y_{1}\) and \(Y_{0}\) is perfectly dependent on \(X\), \(\theta^{\ast}\) is point identified under the standard rank condition. Without the common \(X\) in both datasets, this would only be possible in the extreme case that one of \(Y_{1}\) and \(Y_{0}\) is constant almost surely.

3.2 Affine Moment Model↩︎

In this section, we show that if the moment function \(m\) is affine in \(\theta\), then \(\Theta_{I}\) is convex with a simple expression for its support function. Throughout the discussion, we assume that Assumption 2 holds so that Theorem 1 applies.

For each running example, we formulate the moment functions and \(\theta\) in a way that ensures Assumption 3 holds. Without loss of generality, we focus on the first decomposition in the following discussion. Define \[\mathcal{KT}_{t^{\top}m_{b}}\left(\mu_{1\mid x},\mu_{0\mid x};x\right)\equiv\inf_{\mu_{10\mid x}\in\mathcal{M}\left(\mu_{1\mid x},\mu_{0\mid x}\right)}\int\int t^{\top}m_{b}\left(y_{1},y_{0},x\right)d\mu_{10\mid x}.\label{eq:AInner}\tag{9}\] Note that \(\mathcal{KT}_{t^{\top}m_{b}}\left(\mu_{1\mid x},\mu_{0\mid x};x\right)\) does not depend on \(\theta\), because the cost function \(t^{\top}m_{b}\left(y_{1},y_{0},x\right)\) does not depend on \(\theta\).

Under Assumption 4, the convexity of \(\Theta_{I}\) follows immediately from Theorem 2 (i), because the constraints in the expression of \(\Theta_{I}\) in Theorem 2 (i) are affine in \(\theta\).

3.2.1 The Support Function of \(\Theta_{I}\)↩︎

For a convex set \(\Psi\subseteq\mathbb{R}^{d_{\theta}}\), its support function \(h_{\Psi}\left(\cdot\right):\mathbb{S}^{d_{\theta}}\rightarrow\mathbb{R}\) is defined pointwise by \(h_{\Psi}\left(q\right)=\sup_{\psi\in\Psi}q^{\top}\psi\). Our novel characterization of the identified set in Theorem 2 provides a straightforward way to obtain its support function. Define \[\Theta_{R}\equiv\left\{ \theta\in\mathbb{R}^{d_{\theta}}:t^{\top}\mathbb{E}\left[m_{a}\left(Y_{0},X\right)\right]\theta\leq-\int\mathcal{KT}_{t^{\top}m_{b}}\left(\mu_{1\mid x},\mu_{0\mid x};x\right)d\mu_{X}\text{ for all }t\in\mathbb{S}^{k}\right\} ,\] where \(\mathcal{KT}_{t^{\top}m_{b}}\left(\mu_{1\mid x},\mu_{0\mid x};x\right)\) is defined in (9 ). We make the following two additional assumptions. The first assumption is on the parameter space \(\Theta\).

By definition, we have that \(\Theta_{R}\cap\Theta=\Theta_{I}\). Assumption 5 requires that the parameter space \(\Theta\) does not provide additional information on the identified set \(\Theta_{I}\) given \(\Theta_{R}\). It implies that the boundary of \(\Theta_{I}\) is completely determined by the continuum of inequalities in Theorem 2 (i). For all the running examples, we can easily choose \(\Theta\) to make Assumption 5 hold. The second assumption is on the moment function.

Assumption 6 requires that the number of moments is the same as the number of parameters, and that the coefficient matrix is of full rank. It implies that if the joint distribution \(\mu_{o}\) of \(\left(Y_{1},Y_{0},X\right)\) is identifiable from the data, then \(\theta^{\ast}\) is just identified but not overly-identified. For the examples in the paper, Assumption 6 is satisfied either automatically because \(\mathbb{E}\left[m_{a}\left(Y_{0},X\right)\right]\) is a diagonal matrix with positive diagonal entries or under very mild conditions.

Under Assumption 6, the expression of \(\Theta_{I}\) in Theorem 2 (i) is equivalent to \[\begin{align} \Theta_{I}= & \left\{ \theta\in\Theta:q^{\top}\theta\leq s\left(q\right)\text{ for all }q\in\mathbb{S}^{d_{\theta}}\right\} \textrm{, where }\nonumber \\ s\left(q\right)\equiv & -\int\mathcal{KT}_{q^{\top}\mathbb{E}\left[m_{a}\left(Y_{0},X\right)\right]^{-1}m_{b}}\left(\mu_{1\mid x},\mu_{0\mid x};x\right)d\mu_{X}\label{eq:support32function32-32general}\\ = & -\int\left[\inf_{\mu_{10\mid x}\in\mathcal{M}\left(\mu_{1\mid x},\mu_{0\mid x}\right)}\int\int q^{\top}\mathbb{E}\left[m_{a}\left(Y_{0},X\right)\right]^{-1}m_{b}\left(y_{1},y_{0},x\right)d\mu_{10\mid x}\right]d\mu_{X}.\nonumber \end{align}\tag{11}\] As a result, we have that \(q^{\top}\theta\leq s\left(q\right)\) for all \(\theta\in\Theta_{I}\). Moreover, applying the result in [45], we establish that \(s(q)\) is indeed the support function of \(\Theta_{I}\), as it is a positively homogeneous, proper, closed, and convex function satisfying \(s(0) = 0\).

Proposition 2 shows that we can obtain the value of the support function for any direction \(q\) by computing the OT cost \(\mathcal{KT}_{q^{\top}\mathbb{E}\left[m_{a}\left(Y_{0},X\right)\right]^{-1}m_{b}}\left(\mu_{1\mid x},\mu_{0\mid x};x\right)\) for each \(x\) and then integrating with respect to \(\mu_{X}\). Moreover, if the parameter of interest is expressed as a linear map from \(\theta^{\ast}\) through the linear operator \(L\), then based on Proposition 2, the support function of the identified set for the parameter of interest can be simply calculated as \(s\left(L^{\star}q\right)\), where \(L^{\star}\) is the adjoint operator with respect to the inner product.

4 The Linear Projection Model↩︎

In this and the next two sections, we construct identified sets for the parameters in Examples 1-3 by applying our general results, and compare them with the existing results for each example. For Example 1, we maintain the assumption that \(\mathbb{E}\left[\left\Vert Y_{1}\right\Vert ^{2}\right]<\infty\) and \(\mathbb{E}\left[\left\Vert Y_{0}\right\Vert ^{2}\right]<\infty\), an assumption that is also imposed in both [17] and [18].

4.1 Identified Sets for \(\theta^{*}\) and \(\delta^{*}\)↩︎

Given the identified set \(\Theta_{I}\) for \(\theta^{\ast}\), the identified set for \(\delta^{*}\) can be obtained by mapping each element in \(\Theta_{I}\) through (3 ), (4 ), or (5 ), depending on the model. We focus our discussion on constructing the identified set \(\Theta_{I}\) in this section. We provide a detailed analysis for the first data type and summarize the identified set for the second data type in Remark 3.

The moment function for \(\theta^{*}\) is affine by its functional form: \[\begin{align} & m\left(y_{1},y_{0},x;\theta\right)=\theta+m_{b}\left(y_{1},y_{0},x\right)\textrm{, where}\\ & m_{b}\left(y_{1},y_{0},x\right)\equiv-\left(y_{0}^{\top}y_{1s},y_{0}^{\top}y_{1r,1},\ldots,y_{0}^{\top}y_{1r,\left(d_{1}-1\right)}\right)^{\top}. \end{align}\] Theorem 2 implies that the identified set for \(\theta^{\ast}\) is \[\Theta_{I}=\left\{ \theta\in\Theta:t^{\top}\theta\leq-\int\mathcal{KT}_{t^{\top}m_{b}}\left(\mu_{1\mid x},\mu_{0\mid x};x\right)d\mu_{X}\text{ for all }t\in\mathbb{S}^{d_{0}d_{1}}\right\} .\label{eq:32LP32Theta32I32general}\tag{12}\] Partitioning \(t\) as \(\left(t_{s}^{\top},t_{r,1}^{\top},\ldots,t_{r,\left(d_{1}-1\right)}^{\top}\right)^{\top}\) with \(t_{s}\in\mathbb{R}^{d_{0}}\) and \(t_{r,j}\in\mathbb{R}^{d_{0}}\) for \(j=1,\ldots,d_{1}-1\), we can express \(\mathcal{KT}_{t^{\top}m_{b}}\left(\mu_{1\mid x},\mu_{0\mid x};x\right)\) as a COT with a product cost function: \[\begin{align} & \mathcal{KT}_{t^{\top}m_{b}}\left(\mu_{1\mid x},\mu_{0\mid x};x\right)\nonumber \\ = & \inf_{\mu_{10\mid x}\in\mathcal{M}\left(\mu_{1\mid x},\mu_{0\mid x}\right)}\int\int-\left(t_{s}^{\top}y_{0},t_{r,1}^{\top}y_{0},\cdots,t_{r,\left(d_{1}-1\right)}^{\top}y_{0}\right)y_{1}d\mu_{10\mid x}\label{eq:LP32Full32OT}\nonumber \\ = & \frac{1}{2}\inf_{\mu_{10\mid x}\in\mathcal{M}\left(\mu_{1\mid x},\mu_{0\mid x}\right)}\int\int\left\Vert \left(t_{s}^{\top}y_{0},t_{r,1}^{\top}y_{0},\cdots,t_{r,\left(d_{1}-1\right)}^{\top}y_{0}\right)-y_{1}\right\Vert ^{2}d\mu_{10\mid x}\nonumber \\ & -\frac{1}{2}\int\left\Vert \left(t_{s}^{\top}y_{0},t_{r,1}^{\top}y_{0},\cdots,t_{r,\left(d_{1}-1\right)}^{\top}y_{0}\right)\right\Vert ^{2}d\mu_{0\mid x}-\frac{1}{2}\int\left\Vert y_{1}\right\Vert ^{2}d\mu_{1\mid x}. \end{align}\tag{13}\] The first term on the right-hand side of Equation (13 ) is half of the Wasserstein distance between the conditional distribution of \(\left(t_{s}^{\top}Y_{0},t_{r,1}^{\top}Y_{0},\cdots,t_{r,\left(d_{1}-1\right)}^{\top}Y_{0}\right)\) and that of \(Y_{1}\) given \(X=x\). Wasserstein distance is the value function of the most studied and best understood OT problem. Recent breakthroughs in computational OT have contributed to the surge in its applications in diverse disciplines; see [7] for a comprehensive account of computational methods and applications. In addition, when both marginals are Gaussian, closed-form expressions for Wasserstein distance are known; see the discussion in [6] and [9].

One important feature of the OT problem in (13 ) is that the ‘effective’ dimension of the marginal measures is equal to the dimension of \(Y_{1}\) regardless of the dimension of \(Y_{0}\), which can be high. Consequently, the computational burden only depends on \(d_{1}\) and is independent of \(d_{0}\). Moreover, in Appendix 10.1.1, we show that by reordering elements of \(\theta^{\ast}\), we can obtain a similar but alternative characterization of \(\Theta_{I}\) such that the COT consists of a Wasserstein distance between the conditional distribution of \(\left(t_{1}^{\top}Y_{1},\cdots,t_{d_{0}}^{\top}Y_{1}\right)\) and that of \(Y_{0}\) given \(X=x\) with \(t_{j}\in\mathbb{R}^{d_{1}}\) for \(j=1,\ldots,d_{0}\). For such a characterization, the computational burden would only depend on \(d_{0}\).

When \(d_{1}>1\) as in [18], the value function of Equation (13 ) does not have a closed-from solution. However, a celebrated theorem of [20] implies that under mild regularity condition on \(\mu_{1|x}\), the solution to (13 ) concentrates on the gradient of a convex function, and the value function can be written as \(\int-\nabla\phi_{t}\left(y_{1},x\right)y_{1}d\mu_{1\mid x},\) where \(\nabla\phi_{t}\left(Y_{1},x\right)\) denotes the gradient of \(\phi_{t}\left(\cdot,x\right)\), a convex function for each \(t\) and \(x\).

Due to the functional form of \(G\left(\cdot\right)\), the resulting set \(\Delta_{I}\) may not be convex. On the other hand, because \(\Theta_{I}\) is convex and \(G\left(\cdot\right)\) is continuous, the set \(\Delta_{I}\) is connected and the projection of \(\Delta_{I}\) onto any one-dimensional subspace is a connected interval.

4.2 The Model in [17]↩︎

In [17], \(d_{1}=1\). Proposition 2.17 in [6] implies that Equation (13 ) has a closed-form solution and \[\begin{align} \mathcal{KT}_{t^{\top}m_{b}}\left(\mu_{1\mid x},\mu_{0\mid x};x\right)= & \inf_{\mu_{10\mid x}\in\mathcal{M}\left(\mu_{1\mid x},\mu_{0\mid x}\right)}\int\int-\left(t^{\top}y_{0}\right)y_{1}d\mu_{10\mid x}\\ = & -\int_{0}^{1}F_{t^{\top}Y_{0}\mid x}^{-1}\left(u\right)F_{Y_{1}\mid x}^{-1}\left(u\right)du. \end{align}\] Consequently, we derive the identified set \(\Theta_{I}\) from (12 ) as \[\Theta_{I}=\left\{ \theta\in\Theta:t^{\top}\theta\leq\int\int_{0}^{1}F_{t^{\top}Y_{0}\mid x}^{-1}\left(u\right)F_{Y_{1}\mid x}^{-1}\left(u\right)dud\mu_{X}\text{ for all }t\in\mathbb{S}^{d_{0}}\right\} .\label{eq:32DHau32Theta32I}\tag{14}\]

Following [17], we let \(\Theta=\mathbb{R}^{d_{0}}\). Assumptions 4 and 5 are both satisfied. For any \(q_{0}\in\mathbb{S}^{d_{0}}\), Proposition 2 provides the support function of \(\Theta_{I}\): \[h_{\Theta_{I}}\left(q_{0}\right)=\int\int_{0}^{1}F_{q_{0}^{\top}Y_{0}\mid x}^{-1}\left(u\right)F_{Y_{1}\mid x}^{-1}\left(u\right)dud\mu_{X}.\label{eq:DHau32Theta32I32suppor}\tag{15}\]

Assume that the inverse of the second moment matrix \(\mathbb{E}\left[\left(Y_{0}^{\top},X_{p}^{\top}\right)^{\top}\left(Y_{0}^{\top},X_{p}^{\top}\right)\right]\) exists, and denote its block partition by \(\left(A_{ij}\right)_{i,j\in\left\{ 0,p\right\} }\). The same assumption is imposed in [17]. It follows from Equation (4 ) that \(\delta^{\ast}=\left(A_{00}^{\top},A_{p0}^{\top}\right)^{\top}\theta^{\ast}+\left(A_{0p}^{\top},A_{pp}^{\top}\right)^{\top}\mathbb{E}\left[X_{p}Y_{1}\right]\), which is an affine map. The standard result on the support function provides the following proposition on the support function of \(\Delta_{I}\), which coincides with Theorems 1 and 2 of [17].

5 Demographic Disparity Measures in KMZ↩︎

5.1 Identified Sets for DD Measures and Its Vertex Representation↩︎

The moment function \(m\) is affine with \[\begin{align} & m_{a}\left(y_{0},x\right)=\mathrm{diag}\left(\mathbb{1}\left\{ y_{0}=a_{1}\right\} ,\ldots,\mathbb{1}\left\{ y_{0}=a_{J}\right\} \right)\textrm{ and }\\ & m_{b}\left(y_{0},y_{1},x\right)=-\left(\mathbb{1}\left\{ y_{1}=1,y_{0}=a_{1}\right\} ,\ldots,\mathbb{1}\left\{ y_{1}=1,y_{0}=a_{J}\right\} \right)^{\top}. \end{align}\] The identified set \(\Theta_{I}\) of \(\theta^{\ast}\) follows from Theorem 2 (i), where \[\mathcal{KT}_{t^{\top}m_{b}}\left(\mu_{1\mid x},\mu_{0\mid x};x\right)=\inf_{\mu_{10\mid x}\in\mathcal{M}\left(\mu_{1\mid x},\mu_{0\mid x}\right)}\int\int\sum_{j=1}^{J}-t_{j}\mathbb{1}\left\{ y_{1}=1,y_{0}=a_{j}\right\} d\mu_{10\mid x}.\] Let \(\mathtt{\boldsymbol{d}}\left(y_{1}\right)=\mathbb{1}\left\{ y_{1}=1\right\}\) and \(\mathtt{\boldsymbol{d}}_{t}\left(y_{0}\right)=\sum_{j=1}^{J}t_{j}\mathbb{1}\left\{ y_{0}=a_{j}\right\}\). Then \(\mathcal{KT}_{t^{\top}m_{b}}\left(\cdot\right)\) equals to \[\inf_{\mu_{10\mid x}\in\mathcal{M}\left(\mu_{1\mid x},\mu_{0\mid x}\right)}\int\int-\mathtt{\mathtt{\boldsymbol{d}}}\left(y_{1}\right)\times\mathtt{\mathtt{\boldsymbol{d}}}_{t}\left(y_{0}\right)d\mu_{10\mid x}\left(y_{1},y_{0}\right)=-\int_{\Pr\left(Y_{1}=0\mid x\right)}^{1}F_{D_{t}\mid x}^{-1}\left(u\right)du\] with \(D_{t}\equiv \mathtt{\boldsymbol{d}}_{t}\left(Y_{0}\right)\). The last equality follows from the monotone rearrangement inequality.

Given \(p\), \(D_{E^{\top}p}\) is a discrete random variable. As a result, we can easily obtain its quantile function. The closed-form expression of the support function of \(\Delta_{DD}\) in (?? ) provides an easy way to obtain the identified set for any single DD measure \(\delta_{DD}^{\ast}\left(j,j^{\dagger}\right)\) for \(J\geq2\); see Appendix 10.2.1 for details. Furthermore, the analytical expression of the support function in (?? ) allows us to obtain the vertex representation of the identified set \(\Delta_{DD}\), which substantially simplifies its computation.

In the following, we prove that both \(\Theta_{I}\) and \(\Delta_{DD}\) are polytopes and provide their vertex representations. We first derive the vertices for \(\Theta_{I}\) whose support function is \[h_{\Theta_{I}}\left(q\right)=\int\int_{\Pr\left(Y_{1}=0\mid x\right)}^{1}F_{D_q\mid x}^{-1}\left(u\right)dud\mu_{X}.\label{eq:theta32support32function}\tag{16}\] The ones for \(\Delta_{DD}\) can be obtained by premultiplying \(E\) to the vertices for \(\Theta_{I}\).

We need to introduce some notation. For the set \(M\equiv\left\{ 1,\ldots,J\right\}\), define \(\mathfrak{S}_{M}\) as its symmetric group, which is the group of all permutations of \(M\). Let \(\sigma\) denote a generic element of \(\mathfrak{S}_{M}\), i.e., a permutation of \(M\). The order of \(\mathfrak{S}_{M}\), denoted as \(\left|\mathfrak{S}_{M}\right|\), equals \(J!\). We can enumerate each element of \(\mathfrak{S}_{M}\) as \(\sigma_{s}\) for \(s=1,\ldots,\left|\mathfrak{S}_{M}\right|\). The values of \(\Pr\left(Y_{0}=a_{j}\right)\) for \(j\in M\) are identifiable from the sample information. For any \(\sigma_{s}\in\mathfrak{S}_{M}\), we define the following polyhedral region of \(q\): \[R_{s}\equiv\left\{ q\in\mathbb{R}^{J}:q_{\sigma_{s}\left(1\right)}\Pr\left(Y_{0}=a_{\sigma_{s}\left(1\right)}\right)^{-1}\leq\ldots\leq q_{\sigma_{s}\left(J\right)}\Pr\left(Y_{0}=a_{\sigma_{s}\left(J\right)}\right)^{-1}\right\} .\] Given \(q\in R_{s}\), for any \(s=1,\ldots,\left|\mathfrak{S}_{M}\right|\), the quantile function \(F_{D_{q}\mid x}^{-1}\left(u\right)\) is a step function taking the value \(\sum_{j=1}^{J}\frac{q_{\sigma_{s}\left(j\right)}}{\Pr\left(Y_{0}=a_{\sigma_{s}\left(j\right)}\right)}U\left(u,j,x\right)\), where \[U\left(u,j,x\right)\equiv\mathbb{1}\left\{ \sum_{j=1}^{j-1}\Pr\left(Y_{0}=a_{\sigma_{s}\left(j\right)}\mid x\right)<u<\sum_{j=1}^{j}\Pr\left(Y_{0}=a_{\sigma_{s}\left(j\right)}\mid x\right)\right\}\] and \(\Pr\left(Y_{0}=a_{j}\mid x\right)\) denotes the conditional probability of \(Y_{0}=a_{j}\) given \(X=x\). This is a linear function of \(q\). Since the integrations with respect to \(u\) and \(\mu_{X}\left(x\right)\) in Equation (16 ) do not affect linearity, it holds that \(h_{\Theta_{I}}\left(q\right)\) is linear in \(q\) for \(q\in R_{s}\). Because each \(R_{s}\) is a convex cone and \(\cup_{s=1}^{\left|\mathfrak{S}_{M}\right|}R_{s}=\mathbb{R}^{J}\), \(h_{\Theta_{I}}\left(q\right)\) is a piecewise linear function in \(q\in\mathbb{R}^{J}\) on a finite number of convex cones. Theorem 2.3.4 in [46] shows that \(\Theta_{I}\) is a polytope. Furthermore, for each \(s=1,\ldots,\left|\mathfrak{S}_{M}\right|\), because \(h_{\Theta_{I}}\left(q\right)\) is linear in \(q\) for \(q\in R_{s}\), there is a vector \(v_{s}\) such that \(h_{\Theta_{I}}\left(q\right)=q^{\top}v_{s}\) for \(q\in R_{s}\). Let \(v_{s}\equiv\left(v_{s,1},\ldots,v_{s,J}\right)\). Then each element \(v_{s,\sigma_{s}\left(j\right)}\) for \(j=1,\ldots,J\) can be computed by \[\int\int_{\Pr\left(Y_{1}=0\mid x\right)}^{1}\frac{1}{\Pr\left(Y_{0}=a_{\sigma_{s}\left(j\right)}\right)}U\left(u,j,x\right)dud\mu_{X}.\] There are \(\left|\mathfrak{S}_{M}\right|\) number of vectors \(v_{s}\) (not necessarily unique) such that \(h_{\Theta_{I}}\left(q\right)=q^{\top}v_{s}\) for \(q\in R_{s}\). The set \(\left\{ v_{1},\ldots,v_{\left|\mathfrak{S}_{M}\right|}\right\}\) contains all the vertices of the identified set \(\Theta_{I}\).¹³ This proves the following proposition.

5.2 Numerical Comparison with KMZ↩︎

KMZ study a specific collection of DD measures: \(E^{\star}\theta^{\ast}=\left[\delta_{DD}^{\ast}\left(1,J\right),\ldots,\delta_{DD}^{\ast}\left(J-1,J\right)\right]\). Denote \(\Delta_{DD}^{\star}\) as the identified set for \(E^{\star}\theta^{\ast}\). They propose to construct \(\Delta_{DD}^{\star}\) using its support function as \[\Delta_{DD}^{\star}\equiv\left\{ \delta :p^{\top}\delta\leq\int\varPhi_{K}\left(p,x\right)d\mu_{X}\left(x\right)\textrm{ for all }p\in\mathbb{S}^{J-1}\right\} ,\] where \(\int\varPhi_{K}\left(p,x\right)d\mu_{X}\left(x\right)\) is the value of the support function evaluated at \(p\). Based on their Proposition 10, KMZ propose a linear programming approach to computing \(\varPhi_{K}\left(p,x\right)\). For any given \(p\) and \(x\), there are \(2J\) variables and about \(5J\) (equality and inequality) constraints in their linear program. In Appendix 10.2.2, we discuss the time complexity of the approach in KMZ and our methods, and show that both our support function approach and vertex representation approach are significantly more computationally efficient than the KMZ method.

For the numerical comparison, we use the empirical application in KMZ, which studies the identified set for demographic disparity in mortgage credit decisions using HMDA (Home Mortgage Disclosure Act) dataset. Following KMZ, we focus on three racial groups: White, Black, and Asian and Pacific Islander (API). We consider three sets of proxy variables for race: geolocation (county) only, annual income only, and both geolocation and annual income. To construct \(\Delta_{DD}\), we apply the vertex representation \(\textrm{conv}\left\{ Ev_{1},\ldots,Ev_{\left|\mathfrak{S}_{M}\right|}\right\}\) as discussed in Proposition 6. In practice, this representation requires only the conditional probabilities \(\Pr\left(Y_{1}=0\mid x_{i}\right)\) and \(\Pr\left(Y_{0}=a_{j}\mid x_{i}\right)\) for \(j=1,\ldots,J\), where \(x_{i}\) for \(i=1,\ldots,n\) are observations of \(X\). Since these values are provided in the KMZ code, we use them directly instead of recomputing them from the raw data.¹⁵ For the KMZ method, we rely on their published code and set the number of direction vectors to 100. As both methods require the same conditional probabilities, the comparison of computational time considers only the steps after these probabilities are obtained. Additional details on this empirical analysis are provided in Appendix [subsec:Additional-Details-Empirical].

Figure 1 shows that our method and the approach in KMZ yield the same identified set. However, our method is substantially faster. The vertex representation approach computes the identified set for each proxy variable in under 70 milliseconds, whereas the KMZ method requires approximately 20 minutes. This corresponds to a speed improvement of over 15,000-fold relative to the KMZ method.

6 True-Positive Rate Disparity Measures in KMZ↩︎

6.1 Identified Sets for TPRD Measures—Partial Optimal Transport Characterization↩︎

The moment function is affine with \(m_{a}\left(y_{0},x\right)\) being the \(2J\times2J\) identity matrix and \[\begin{align} m_{b}\left(y_{1},y_{0},x;\theta\right)= & -\left(\mathbb{1}\left\{ y_{1}=\left(1,1\right),y_{0}=a_{1}\right\} ,\ldots,\mathbb{1}\left\{ y_{1}=\left(1,1\right),y_{0}=a_{J}\right\} ,\right.\\ & \left.\mathbb{1}\left\{ y_{1}=\left(0,1\right),y_{0}=a_{1}\right\} ,\ldots,\mathbb{1}\left\{ y_{1}=\left(0,1\right),y_{0}=a_{J}\right\} \right)^{\top}. \end{align}\] Consequently, the identified set for \(\theta^{*}\) is \[\Theta_{I}=\left\{ \theta\in\Theta:\sum_{j=1}^{2J}t_{j}\theta_{j}\leq-\int\mathcal{KT}_{t^{\top}m_{b}}\left(\mu_{1\mid x},\mu_{0\mid x};x\right)d\mu_{X}\text{ for all }t\in\mathbb{S}^{2J}\right\}\] with support function for any \(q\in\mathbb{S}^{2J}\) given by \[h_{\Theta_{I}}\left(q\right)=-\int\mathcal{KT}_{q^{\top}m_{b}}\left(\mu_{1\mid x},\mu_{0\mid x};x\right)d\mu_{X}.\label{eq:TPRD32support32function}\tag{17}\]

Let \(\Delta_{TPRD}\) denote the identified set for \(K\) different TPRD measures represented by \(G\left(\theta^{\ast}\right)\). We can compute \(\Delta_{TPRD}\) as a non-linear map from \(\Theta_{I}\): \[\Delta_{TPRD}=\left\{ \delta=G\left(\theta\right):\theta\in\Theta_{I}\right\} =\left\{ \delta=G\left(\theta\right):q^{\top}\theta\leq h_{\Theta_{I}}\left(q\right)\textrm{ for all }q\in\mathbb{S}^{2J}\right\} ,\] where \(h_{\Theta_{I}}\left(\cdot\right)\) is defined in (17 ). Because \(\Theta_{I}\) is convex and the map \(G\) is continuous, we know that \(\Delta_{TPRD}\) is connected, which implies that the identified set for any single TPRD measure is a closed interval. In Appendix 10.3.1, we derive the closed-form expressions for the lower and upper endpoints of the interval, extending the result in KMZ established for \(J=2\).

For multiple TPRD measures, we need to compute \(\mathcal{KT}_{q^{\top}m_{b}}\left(\cdot\right)\), for which we propose a novel computationally efficient algorithm in Section 6.2. Our algorithm solves the reformulation of \(\mathcal{KT}_{q^{\top}m_{b}}\left(\cdot\right)\) as the value function of a linear programming problem in (18 ).

Given \(q\equiv\left(q_{1},\ldots,q_{2J}\right)\), define \(c\left(i,j\right)\equiv-q_{\left(1-i\right)J+j}\) for \(i=0,1\) and \(j=1,\ldots,J\). Because \(Y_{1}\) and \(Y_{0}\) are discrete random variables, we define, with a slight abuse of notation, \[\begin{align} & \mu_{0\mid x}\left(j\right)\equiv\int\mathbb{1}\left\{ y_{0}=a_{j}\right\} d\mu_{0\mid x}\left(y_{0}\right)=\Pr\left(Y_{0}=a_{j}\mid X=x\right)\textrm{, }\\ & \mu_{1\mid x}\left(i,1\right)\equiv\int\mathbb{1}\left\{ y_{1s}=i,y_{1r}=1\right\} \mu_{1\mid x}\left(y_{1s},y_{1r}\right)=\Pr\left(Y_{1s}=i,Y_{1r}=1\mid X=x\right)\textrm{, and }\\ & \mu_{10\mid x}\left(i,1,j\right)\equiv\int\int\mathbb{1}\left\{ y_{1}=\left(i,1\right),y_{0}=a_{j}\right\} d\mu_{10\mid x}\left(y_{1},y_{0}\right). \end{align}\] The COT cost \(\mathcal{KT}_{t^{\top}m_{b}}\left(\cdot\right)\) can then be rewritten as the following optimization problem with the argument \(\mu_{10\mid x}\left(i,1,j\right)\): \[\begin{align} & \mathcal{KT}_{q^{\top}m_{b}}\left(\mu_{1\mid x},\mu_{0\mid x};x\right)=\min_{\mu_{10\mid x}}\sum_{j=1}^{J}\sum_{i=0}^{1}c\left(i,j\right)\mu_{10\mid x}\left(i,1,j\right)\label{eq:Partial32transport32problem}\\ \textrm{s.t. } & \textrm{\textrm{(i) }}\mu_{10\mid x}\left(i,1,j\right)\geq0\textrm{ for }i=0,1\textrm{ and }j=1,\ldots,J\textrm{;}\nonumber \\ & \textrm{(ii) }\sum_{i=0}^{1}\mu_{10\mid x}\left(i,1,j\right)\leq\mu_{0|x}\left(j\right)\textrm{ for }j=1,\ldots,J\textrm{;}\nonumber \\ & \textrm{(iii) }\sum_{j=1}^{J}\mu_{10\mid x}\left(i,1,j\right)=\mu_{1\mid x}\left(i,1\right)\textrm{ for }i=0,1.\nonumber \end{align}\tag{18}\] Note that the second constraint is an inequality rather than an equality because the COT cost \(\mathcal{KT}_{q^{\top}m_{b}}\left(\cdot\right)\) does not involve \(\mu_{10\mid x}\left(y_{1},y_{0}\right)\) for \(y_{1}=\left(y_{1s},0\right)\). Consequently, (18 ) is actually a conditional partial optimal transport, where \(\mu_{0\mid x}\left(j\right)\) and \(\mu_{1\mid x}\left(i,1\right)\) are identified from the sample information. Furthermore, since \(i\) in the optimization problem (18 ) takes two values only, we can always make \(c\left(i,j\right)\) submodular by relabeling the index \(j\). Without loss of generality, we will assume from now on that the cost function \(c\left(i,j\right)\) in (18 ) is submodular.

The following lemma shows that this reformulation of the partial optimal transport problem admits a solution whose support is monotone.

6.2 Dual Rank Equilibration Algorithm↩︎

Exploiting the structure of the solution, we propose Algorithm 2 to compute \(\mathcal{KT}_{q^{\top}m_{b}}\left(\cdot\right)\) and call it Dual Rank Equilibration AlgorithM (DREAM). DREAM is built on an equivalent characterization of (18 ) which allows it to use the ranks of \(c\left(i,j\right)\) to equilibrate between minimizing the partial transport cost and respecting the constraints in (18 ). The equilibration is done twice by first separately adjusting \(\mu_{10\mid x}^{\ast}\left(0,1,j\right)\) and \(\mu_{10\mid x}^{\ast}\left(1,1,j\right)\) across index \(j\) and then jointly adjusting \(\mu_{10\mid x}^{\ast}\left(0,1,j\right)\) and \(\mu_{10\mid x}^{\ast}\left(1,1,j\right)\) for a fixed \(j\)—Dual Rank Equilibration AlgorithM. Appendix 10.3.2 provides a detailed description of DREAM. DREAM involves only basic arithmetic, comparison, and logical operations, making it straightforward to implement directly in code. In fact, it can be executed by hand. In Appendix 10.3.3, we provide theoretical time complexity analysis of DREAM and show that it is faster than directly solving the linear programming (18 ), particularly when \(J\) is large.

Different from our approach, KMZ study the convex hull of the identified set for a collection of TPRD measures instead of the identified set itself. They focus on \(\left[\delta_{TPRD}^{\ast}\left(1,J\right),\ldots,\delta_{TPRD}^{\ast}\left(J-1,J\right)\right]\), which is one example of our TPRD measures with \(G^{\star}\left(\theta^{\ast}\right)\equiv\left[g_{1,J}\left(\theta^{\ast}\right),\ldots,g_{J-1,J}\left(\theta^{\ast}\right)\right]\). In their Proposition 11, KMZ propose to compute the support function of the convex hull at each direction from a complicated double optimization problem, where the inner maximization problem is a linear program and the outer maximization is a non-convex optimization problem, which is known to be NP-hard.

We applied DREAM and [47], a general-purpose linear programming solver, to the empirical application studied in KMZ.¹⁶ The application investigates TPRD in Warfarin dosing with the ClinPGx/PharmGKB dataset used in [48].¹⁷ The analysis focuses on three protected attributes (White, Black, and Asian) and three specifications of proxy variables: genetic factors alone, current medications alone, and both genetic factors and current medications jointly. Because values of \(\mu_{0\mid x}\left(\cdot\right)\) and \(\mu_{1\mid x}\left(\cdot\right)\) in \((\ref{eq:Partial32transport32problem})\) for each observed \(X\) have been computed in KMZ, we use them directly. During implementation, we first sample vectors \(q_{1},\ldots,q_{N_{q}}\) uniformly from the \(2J\)-dimensional unit sphere, along with vectors \(\theta_{1},\ldots,\theta_{N_{\theta}}\) from \(\prod_{j=1}^{2J}\left[\theta_{j}^{L},\theta_{j}^{U}\right]\), where \(\theta_{j}^{L}\) and \(\theta_{j}^{U}\) are lower and upper bounds for each \(\theta_{j}\) that are defined in Appendix Corollary 2. Then, we construct the set \(\widehat{\Theta}_{I}=\left\{ \theta\in\left\{ \theta_{1},\ldots,\theta_{N_{\theta}}\right\} :q^{\top}\theta\leq h_{\Theta_{I}}\left(q\right)\textrm{ for all }q=q_{1},\ldots,q_{N_{q}}\right\}\). Finally, we apply the mapping to each \(\theta\in\widehat{\Theta}_{I}\) to obtain an approximation of \(\Delta_{TPRD}\): \(\widehat{\Delta}_{TPRD}=\left\{ \delta=G\left(\theta\right):\theta\in\widehat{\Theta}_{I}\right\}\).¹⁸ Appendix [subsec:Additional-Details-Empirical] provides more detail.

Figure 4 plots the identified sets obtained from DREAM, which are identical to the sets produced by the [47] solver up to a negligible numerical error. The runtime comparison shows that our approach is more than twice as fast as the commercial linear programming solver.

7 Concluding Remarks↩︎

In this paper, we have developed the first unified approach to study the identified set for a finite-dimensional parameter in a general moment equality model with incomplete data.¹⁹ Through several examples, we have demonstrated the advantages and simplicity of our approach. By exploring recent developments in optimal transport, our method often leads to equivalent, yet computationally more tractable, identified sets for specific models than the existing ones in the literature.

This paper provides the first step towards developing a complete set of econometric techniques for moment models under data combination. Building on the identification analysis in this paper, the next step is to construct valid estimation and inference in the general moment model (1 ) with incomplete data. For Example 1 without common covariate \(X\), [17] develops estimation and inference for \(\theta^{*}\). For the special case that \(k=1\) and \(\theta^{*}=\mathbb{E}\left[h\left(Y_{1},Y_{0},X)\right)\right]\), [40] and [39] construct estimation and inference using primal and dual formulation, respectively. We leave the general case for future work.

8 Acknowledgment↩︎

We thank Stéphane Bonhomme, Xiaohong Chen, Marc Henry, Ruixuan Liu, and participants of the BIRS Workshop on Optimal Transport and Distributional Robustness in March 2024, 2025 IAER Econometrics Workshop, and 2025 China Annual Conference of the Chinese Economists Association; seminar participants in the statistics department at the University of Washington, economics departments at Johns Hopkins University and Yale University, as well as Amazon in October 2024 for useful feedback. Brendan Pass is pleased to acknowledge the support of the Natural Sciences and Engineering Research Council of Canada Discovery Grant numbers 04658-2018 and 04864-2024.

References↩︎

---

1. Department of Economics, University of Washington↩︎

2. Center for Industrial and Business Organization and Institute for Advanced Economic Research, Dongbei University of Finance and Economics↩︎

3. Department of Mathematical and Statistical Sciences, University of Alberta↩︎

4. School of Economics, University of Sydney↩︎

5. This is a substantially revised version of the previously circulated paper titled “Partial Identification in Moment Models with Incomplete Data via Optimal Transport” available at: https://arxiv.org/abs/2503.16098v1, March 21, 2025.↩︎

6. When \(\delta^{\ast}=G\left(\theta^{\ast}\right)\) is the parameter of interest for some function \(G\left(\cdot\right)\), we say \(G\left(\cdot\right)\) is known if either its functional form is known or (point) identifiable.↩︎

7. Conditional optimal transport is an optimal transport between two conditional measures; see [2] and [3] for rigorous accounts of COT. For expositional simplicity, we often use optimal transport even though it is a conditional optimal transport in this paper.↩︎

8. Other works that have employed optimal transport in partial identification analysis in different set-ups from ours include [8], [9], and [10]. We refer interested readers to [11] for a recent survey.↩︎

9. Mathematically, the bounds problem in [12] is similar to that in [13], [14]. All are variations of the short and long regression in [15]; see also [16].↩︎

10. [38] include a point-identified nuisance parameter \(\gamma^{\ast}\) in their moment function to separate the parameter of interest \(\theta^{\ast}\) from \(\gamma^{\ast}\). Model (1 ) can be accommodated to having the nuisance parameter by appending \(\gamma^{\ast}\) to \(\theta^{\ast}\).↩︎

11. We note that the variable \(X_{np}\) is observed in both datasets, but does not enter the linear projection model. In the textbook complete data case, \(X_{np}\) is an irrelevant variable. But as we discuss in Remark 4, in the incomplete data case, \(X_{np}\) may shrink the identified set and becomes relevant.↩︎

12. All the statement with “for any \(x\in\mathcal{X}\)” can be relaxed to “for almost any \(x\in\mathcal{X}\) with respect to \(\mu_{X}\) measure”. We ignore such mathematical subtlety to simplify the discussion.↩︎

13. Not all \(v_{s}\) for \(s=1,\ldots,\left|\mathfrak{S}_{M}\right|\) are vertices. Some may lie inside the convex hull of others.↩︎

14. Here we derive the vertex representation of \(\Delta_{DD}\) from that of \(\Theta_{I}\). Given the analytic expression of the support function of \(\Delta_{DD}\), we can also obtain the vertex representation of \(\Delta_{DD}\) directly from its support function.↩︎

15. The computed conditional probabilities in Sections 5.2 and 6.2 can be downloaded from https://github.com/CausalML/FairnessWithUnobservedProtectedClass.↩︎

16. We tried and failed to replicate the figures in KMZ using their approach due to the computational challenge of the NP-hard non-convex optimization involved.↩︎

17. The dataset can be downloaded from https://www.clinpgx.org/downloads.↩︎

18. Based on DREAM, the solution to (18 ) depends only on the ranks of linear combinations of \(c\left(i,j\right)\) for \(i=0,1\) and \(j=1,\ldots,J\) (or equivalently elements of the direction vector \(q\)). As a result, one can show that \(\Theta_{I}\) is a polytope, and obtain its vertex representation by following the similar analysis in Section 5.1. However, because the representation is complex and we still need to sample \(\theta\) to construct \(\widehat{\Delta}_{TPRD}\), we recommend using \(\widehat{\Theta}_{I}\).↩︎

19. The methods developed in this paper could, in principle, be extended to the case of more than two datasets using results in [49]. We leave extensions for future work.↩︎

20. We ignore the effect of the bit-length, which refers to the number of bits required to represent the input data of the problem.↩︎

21. The algorithms used in modern solvers, such as Mosek and [47], share the ideas of the simplex method and interior-point methods. The information on the exact time complexity of these solvers is often not public.↩︎