Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
Rendered from LaTeX for readability, not typeset faithfully. Citation keys are highlighted; maths is left as source; figures, tables and equation environments are summarised rather than reproduced; unrecognised commands are greyed out so nothing is silently dropped. Email addresses are removed.
On the inconsistency of matching without replacement
abstract\begin{singlespace}
\noindentThe paper shows that matching without replacement on propensity scores produces estimators that generally are inconsistent for the average treatment effect of the treated.
To achieve consistency, practitioners must either assume that no units exist with propensity scores greater than one-half or assume that there is no confounding among such units.
The result is not driven by the use of propensity scores, and similar artifacts arise when matching on other scores as long as it is without replacement.
\end{singlespace}
\doparttoc
\faketableofcontents
Introduction
Matching aims to adjust for confounded treatment assignment when estimating treatment effects with observational data.
Each treated unit is matched to one or more similar control units according to some similarity measure based on the units' observed characteristics.
The treatment effect is estimated by the average difference between the outcomes of the treated units and their matched controls.
There are many variations to this basic recipe.
An important consideration is whether to match with or without replacement.
In the first case, several treated units can be matched to the same control.
In the second case, at most one treated unit can be matched to each control.
Matching with replacement produces matches of higher quality, but the information provided by the controls may be used inefficiently.
This is because fewer controls will be matched with treated units when the matching is with replacement, and unmatched units are discarded from the analysis.
Practitioners sometimes opt for matching without replacement to avoid such issues.
This type of matching has previously been discussed and studied by Dehejia2002Propensity, Rosenbaum2002Observational, Stuart2010Matching and Abadie2012Martingale, among others.
The purpose of this paper is to investigate the asymptotic properties of the matching estimator when the matching is done without replacement.
The main result is that the matching estimator generally is inconsistent for the treatment effect it aims to estimate.
The underlying idea is conceptually straightforward.
The sample must contain more controls than treated units to construct a matching without replacement.
If not, one would run out of control units, and some treated units would be left unmatched.
For the matching estimator to be consistent, the quality of the matches must improve as the sample grows in size.
This is only possible if there are more controls than treated units for every possible value of the observed covariates.
If not, one would run out of control units for some covariate values, which would force some treated units to be matched with distant control units.
To ensure that control units are locally abundant, the propensity score must be less than one half everywhere on the support of the covariates.
This condition is considerably stronger than typically assumed when matching is used.
The result suggests that practitioners may want to consider alternatives to matching without replacement when adjusting for confounding.
These alternatives include matching with replacement and various weighting methods.
It is also possible to modify the matching procedure to mitigate the problem.
For example, a caliper that diminishes in the sample size would ensure consistency as long as the estimator is modified to account for the fact that the caliper implicit reweights the treated units.
A concern with this modification, and others like it, is that it would undo much of the potential efficiency gains that prompt practitioners to use matching without replacement in the first place.
The key technical contribution of the paper is that the analysis does not condition on the observed covariates.
To the best of my knowledge, all previous investigations of the behavior of matching without replacement are based on such conditioning, or they consider asymptotic regimes that produce a similar effect, as discussed in Section (ref).
Once one conditions on the observed covariates, the matching is deterministic, and one may ignore the stochastic behavior of the matching procedure.
The practice greatly simplifies the analysis, but it may be problematic for two reasons.
First, the stochastic behavior of the matching procedure may be a non-negligible source of imprecision of the matching estimator, which is ignored.
Second, to investigate large sample performance, the behavior of the matching method must be stipulated.
This may, for example, be an assumption that the distance between matched units diminishes asymptotically.
However, such assumptions leave practitioners wondering whether matching without replacement in fact behaves in this way when units are sampled from a population.
The worry is that matchings that satisfy the stipulated behavior may be rare, in which case the analyses in the previous literature would condition on an event that practitioners are unlikely to meet in practice.
The technical innovation of this paper is an approach that allows for an unconditional analysis of the matching function and its asymptotic behavior in a standard sampling framework.
Illustration
An illustration using a categorical covariate will fix ideas.
Consider a population in which $10\%$ of the units belong to a certain covariate category $A$, and $3 / 4$ of these units are treated.
Among the treated units in category $A$, only an expected fraction of $1 / 3$ will be matched to controls in the same category.
This is because controls in the category run out after the first third of the treated units have been matched.
The remaining $2 / 3$, which are $5\%$ of the total sample in expectation, must be matched to controls in other categories.
Unless these other units are representative of the treated units in category $A$, which we have no reason to believe that they are, the poor quality matches will prevent the estimator from concentrating around the treatment effect.
The argument applies as soon as more than half of the units in any category are treated.
Thus, to achieve consistency, there cannot be any such categories.
The purpose of the rest of this paper is to demonstrate that this phenomenon occurs more generally and to derive the asymptotic bias in closed form.
Preliminaries
Notation and regularity conditions
Consider a population described by a distribution $\braces{X, W, \POpop{0}, \POpop{1}, Y}$, where $X \in \mathcal{X}$ is a covariate in some, possibly multi-dimensional, covariate set, $W \in \setb{0, 1}$ is an indicator of treatment assignment, $\POpop{0}$ and $\POpop{1}$ are real-valued potential outcomes, and $Y = \POpop{W}$ is the realized outcome.
The notation requires that the potential outcomes are unambiguous for each treatment condition, ruling out, for example, that the treatment assigned to one unit affects the outcome of another unit.
A sample of $n$ units is drawn from the population, and the observations are indexed by $\mathcal{U} = \setb{1, \dotsc, n}$.
The potential outcomes are never directly observed, and the available information for unit $i$ is $\paren{X_{i}, W_{i}, Y_{i}}$.
The population is assumed to be large, so the observations can be seen as independent and identically distributed according to the population distribution.
The parameter of interest is the treatment effect of the treated units in the population:
equation[equation omitted — 151 chars of source]
The main inferential challenge is that treatment assignment is suspected to be confounded.
That is, the two conditional distributions of $\POpop{0}$ given $W$ may not be the same.
Our hope is that we have observed all confounding variables so that we can adjust for the difference in the conditional distributions.
The focus here is when this adjustment is done using matching without replacement.
To formalize the method, let $\mathcal{T} = \setb{i \in \mathcal{U} :\allowbreak\mathopen{} W_{i} = 1}$ and $\mathcal{C} = \setb{i \in \mathcal{U} :\allowbreak\mathopen{} W_{i} = 0}$ be the sets of treated and control units in the sample.
Let $N_1 = \card{\mathcal{T}}$ and $N_0 = \card{\mathcal{C}}$ denote their sizes.
A matching can be described as an injective function $m : \mathcal{T} \to \mathcal{C}$ where $\mgen{i}$ gives the match for $i \in \mathcal{T}$.
The function is injective because the matching is without replacement: $\mgen{i} \neq \mgen{j}$ for all $i \neq j$.
Let $\mathcal{M}$ collect all such functions, which is the set of all admissible matchings.
Several methods have been devised to select a suitable $m$ from $\mathcal{M}$.
This paper considers optimal matching as described by Rosenbaum1989Optimal.
The covariate set is here endowed with a metric, $d : \mathcal{X} \times \mathcal{X} \to \mathbb{R}^+$.
The resulting metric space captures how similar the units are with respect to their covariates.
That is, if $\dist{X_{i}}{X_{j}} < \dist{X_{i}}{X_{k}}$, then unit $i$ is deemed more similar to unit $j$ than to $k$.
A continuity assumption will later give the metric meaning by connecting it to the potential outcomes.
Optimal matchings are those that minimize the sum of distances between matched units:
equation[equation omitted — 136 chars of source]
If there is not a unique optimal matching, a matching is picked arbitrarily from the set of optimal matchings in a deterministic fashion.
The selected optimal matching $m^* \in \mathcal{M}^*$ is thus completely determined by $\paren{X_{1}, \dotsc, X_{n}}$ and $\paren{W_{1}, \dotsc, W_{n}}$.
If one were to condition on the covariates and treatment assignments, $m^*$ is not random.
However, as noted in the introduction, no such conditioning will be done here, and the matching is random.
The sets $\mathcal{T}$, $\mathcal{C}$ and $\mathcal{M}$ are also random.
With $m^*$ in hand, the treatment effect $\tau_{\normalfont\textsc{att}}$ is estimated by the average difference in observed outcomes between each treated unit and its matched control:
equation[equation omitted — 130 chars of source]
This is the estimator studied by Abadie2006Large,Abadie2012Martingale, and it is widely used by practitioners.
The estimator as stated is not defined when the sample contains no treated units or when it contains more treated units than controls.
Practitioners do not tend to use matching without replacement in either of those two cases, and the conditions below ensure they happen with a probability approaching zero at an exponential rate.
Nevertheless, for completeness, the estimator is defined to be zero in these cases.
To motivate the use of matching adjustment, the population is assumed to satisfy a set of conditions.
A key aspect of these conditions is the propensity score: the fraction of units in the population assigned to treatment.
Let $\bar{\pi} = \Pr{W = 1}$ be the overall fraction of treated units, and let $\pscore{x} = \Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} X = x}$ be the fraction conditional on the covariate.
conditionThe population satisfies:
\begin{enumerate}[label=\roman*.,left=16pt]
• Unconfoundedness: $\POpop{0}$ is conditionally independent of $W$ given $X = x$ on the support of $X$.
• Overlap: $\pscore{x}$ is bounded away from one on the support of $X$.
• Existence of treated units: $\bar{\pi}$ is greater than zero.
• Abundance of control units: $\bar{\pi}$ is less than one-half.
• Well-behaved outcomes: $\E{Y^2}$ exists.
\end{enumerate}
The first condition states that all confounding variables are observed.
This ensures that covariate adjustment in principle could resolve the confounding.
The second condition states that the support of the covariate for the treated units is in the interior of the support for the controls.
This ensures that there is enough information in the population for the adjustment.
The combination of the two conditions is sometimes called ignorable treatment assignment Rosenbaum1983Central.
Ignorable assignment is, however, typically taken to also include unconfoundedness for the other potential outcome and a lower bound on the propensity score.
This is not needed here because the treatment effect of the treated units is the focus Heckman1997Matching.
The third and fourth conditions are the ones mentioned above.
They ensure that large samples almost always contains more controls than treated units and at least some treated units.
This, in turn, ensures that it is possible to construct a matching without replacement with a probability approaching one.
The fifth condition ensures that the outcome distribution in the population does not have tails that are too heavy.
Asymptotic bias and consistency
The focus in the following section is the asymptotic bias of the estimator.
However, the bias itself is not of interest in this paper.
The reason for this focus is that asymptotic unbiasedness is a necessary condition for consistency for the matching estimator given Condition (ref).
The following two lemmas provide the details.
All proofs are presented in the supplement.
lemmaIf an estimator $\hat{\theta}$ is consistent for a parameter $\theta$, then it is asymptotically unbiased or its variance is asymptotically unbounded:
\begin{equation}
\lim_{\varepsilon \to 0} \lim_{n \to \infty} \Pr[\big]{\abs{\hat{\theta} - \theta} \geq \varepsilon} = 0 \quad \implies \quad
\lim_{n \to \infty} \E{\hat{\theta}} = \theta \quador\quad \limsup_{n \to \infty}\Var{\hat{\theta}} = \infty.
\end{equation}
lemmaGiven Condition \refmain{cond:reg-cond},
\begin{equation}
\limsup_{n \to \infty}\Var{\hat{\tau}_{\normalfontatt}} \leq \frac{4\E{Y^2}}{\bar{\pi}^2} < \infty.
\end{equation}
Lemma (ref) states that the expectation of a consistent estimator must concentrate around the parameter it aims to estimate unless its variance grows without limit in the sample size.
This holds for any estimator, and not only for the matching estimator.
The intuition is that consistency implies that only a negligible mass of the estimator's sampling distribution is outside a small neighborhood of the parameter.
If this small mass is enough to affect the estimator's expectation, the mass must move away from the bulk of the sampling distribution, leading to asymptotically unbounded variance.
The lemma implies that an estimator that is known to have asymptotically bounded variance can only be consistent if it is asymptotically unbiased.
That is, it is necessary (but not sufficient) for consistency that the expectation of the estimator concentrates around the parameter.
Lemma (ref) shows that the variance of the matching estimator is asymptotically bounded, so it is an estimator of this kind.
Of course, our hope is that the variance will approach zero under suitable conditions.
The purpose of Lemma (ref) is to show that the variance is bounded no matter what these additional conditions might be.
corollaryGiven Condition \refmain{cond:reg-cond}, if the matching estimator is asymptotically biased with respect to the average treatment effect of the treated, then it is inconsistent:
\begin{equation}
\limsup_{n \to \infty} \abs[\big]{\E{\hat{\tau}_{\normalfontatt}} - \tau_{\normalfontatt}} > 0
\quad \implies \quad
\lim_{\varepsilon \to 0} \limsup_{n \to \infty} \Pr[\big]{\abs{\hat{\tau}_{\normalfontatt} - \tau_{\normalfontatt}} \geq \varepsilon} > 0.
\end{equation}
Matching on propensity scores
Matching on high-dimensional covariates do not tend to perform well.
As shown by Beyer1999When and others, random points in high-dimensional spaces tend to be equidistant, which makes their distances uninformative.
Indeed, Abadie2006Large show that the rate of convergence of the matching estimator is negatively affected by the dimensionality of the covariates when the matching is done with replacement.
Practitioners using matching should for this reason be motivated to reduce the dimensionality of the covariates before matching.
To achieve this, a function can be applied to each unit's covariate, providing a coarser description of its characteristics.
A matching can then be constructed as above but with the coarsened covariates substituted for the raw covariates.
A concern when coarsening the covariates is that one may lose valuable information; unconfoundedness may not hold for the coarsened covariates even if it does so for the raw covariates.
A way to maintain unconfoundedness is to use a coarsening function that still balances the raw covariates.
Such a function is called a balancing score, and Rosenbaum1983Central show that the propensity score, as defined above, is the coarsest balancing score.
A metric based on the propensity scores is therefore an attractive alternative to, for example, Euclidean distances on raw covariates, and it is the focus of this paper.
Matching on other scores, including the raw covariates, is discussed in the supplement.
The propensity score is often not known in advance, and it must then be estimated.
I will, however, disregard the estimation step in this paper, and take the propensity score as known.
This will avoid some technical complications of little interest for the current discussion.
In particular, consistent estimation of the propensity score is generally not possible unless additional assumptions are imposed Robins1997Curse.
By focusing on the setting with a known propensity score, I hope to highlight that the results below are not driven by the challenges in this estimating step.
Put differently, it is not surprising that the matching estimator performs poorly when one fails to estimate the propensity score well, but that is not the point I make in this paper.\footnote{
It has been shown that one can improve efficiency by using an estimated propensity score even when the true score is known Heckman1998Matching,Hirano2003Efficient,Abadie2016Matching.
The intuition is that the estimation can implicitly adjust for chance imbalances between treated and control units in the sample.
This consideration is not relevant here because the focus is on the asymptotic bias.
}
Because the propensity score takes a prominent position, dedicated notation will expedite the discussion.
Let $\Pi = \pscore{X}$ be a random variable describing the distribution of the propensity score in the population.
Similarly, let $\Pi_{i} = \pscore{X_{i}}$ be the propensity score for unit $i$ in the sample.
The metric used for the matching is the absolute difference between units' propensity scores: $\dist{x}{x'} = \abs{\pscore{x} - \pscore{x'}}$.
That is, the optimal matching is the one that minimizes the sum of $\abs[\big]{\Pi_{i} - \Pi_{\mgen{i}}}$ over the treated units $i \in \mathcal{T}$.
A matching metric must be coupled with a restriction on the potential outcomes to give it meaning.
Matching adjustment is implicitly motivated by an assumption that units that are similar with respect to the matching metric are expected to be similar also with respect to their potential outcomes, but Condition (ref) only ensures that units with identical covariate values are comparable.
The following condition formalizes this assumption.
condition[Continuity]
$\Es{\POpop{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} \Pi = p}$ is Lipschitz continuous on the support of $\Pi$.
Inconsistency of the matching estimator
The question at hand is how $\hat{\tau}_{\normalfont\textsc{att}}$ behaves when the sample is drawn from a population satisfying Conditions (ref) and (ref).
As noted in the introduction, the reason this question may be beyond reach is that matching without replacement is not asymptotically stable.
This is in contrast to matching with replacement and many other adjustment methods.
When several treated units are allowed to be matched to the same control, small perturbations of the sample will have small effects.
For example, if we were to remove one unit and replace it with a new unit drawn from the population, the only affected units are those matched to the unit that was removed and those close to the unit that replaces it.
Asymptotically, these units will be a negligible fraction of the sample.
This stability makes an analysis tractable, which, for example, facilitated the investigation by Abadie2006Large.
The concern when the matching is done without replacement is that such small perturbations can initiate chain effects.
This is because at most one treated unit can be matched to each control.
If we, as above, were to replace one matched control unit with a new unit drawn from the population, then the treated unit that was matched to the replaced unit needs to find a new match.
If this new match was previously matched to another treated unit, that treated unit must also find a new match.
This could potentially start a chain of units forced to find new matches, and the chain could potentially be long.
Thus, replacing just a single unit could induce large changes in the matching.
It might be reasonable to believe that such long chain effects are rare, and the set of matched controls will in any case be more stable than the matching itself.
The instability of the matching nevertheless complicates the analysis.
It turns out that the following lemma provides enough leverage to characterize the matching in large samples.
definitionA matching $m$ is said to contain crossing matches if
\begin{equation}
\maxf[\big]{\Pi_{i}, \Pi_{\mgen{j}}} < \minf[\big]{\Pi_{j}, \Pi_{\mgen{i}}}
\qquadfor some\qquad
i, j \in \mathcal{T}.
\end{equation}
lemmaAn optimal propensity score matching contains no crossing matches.
The intuition behind the lemma is that the matching objective, the sum of within-match propensity score differences, can be made smaller if two matches are crossing.
We simply need to switch the controls the two treated units are matched to.
An implication of Lemma (ref) is that if we observe an unmatched control unit with propensity score $p$ in an optimal matching, then we know that no unit with a propensity score greater than $p$ is matched with a unit with a propensity score less than $p$.
The insight provides a way to separate the investigation into two parts, making an analysis tractable.
If there is a point $p^*$ where an unmatched unit exists with high probability asymptotically, then the units to the left and right of $p^*$ can be seen as two unconnected matching problems, which can be analyzed separately.
The point we are looking for is the smallest value $p$ such that at least half of the units in the population with propensity scores greater or equal to $p$ are treated.
In particular, consider $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} \Pi \geq p}$.
This is the probability that a unit with a propensity score greater or equal to $p$ is treated.
We know that this probability is greater than $p$ because $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} \Pi = p} = p$.
For example, at least half of the units with $\Pi \geq 1 / 2$ are treated, so $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} \Pi \geq 1 / 2} \geq 1 / 2$.
The point that partitions the matching problem is
equation[equation omitted — 161 chars of source]
No such point exists when $\Pr{\Pi \geq 1 / 2} = 0$.
Let $p^* = 1 / 2$ in that case, so $p^*$ always is defined.
Provided that there are some units in the population with $\Pi \geq 1 / 2$, there will be an unmatched unit in a small neighborhood around $p^*$ with high probability in large samples, and this gives us the partition we seek.
The first part consists of units with $\Pi_{i} > p^*$, and the second part consists of units with $\Pi_{i} < p^*$.
The properties of the matching are remarkably different in these two parts.
On the one hand, controls will be scarce above $p^*$, so all units are matched.
This means that there here will be a limit to how much the quality of the matching can improve as the sample grows.
On the other hand, controls are abundant below $p^*$, and the match quality improves without limit here, although it may be at a slow rate.
The argument does not apply to units with $\Pi_{i} = p^*$, and such units complicate the discussion without adding any profound insights.
A simple way to avoid the concern is to assume that there is no atom at $p^*$, so $\Pr{\Pi = p^*} = 0$.
The following condition does the same but is slightly weaker.
It effectively says that if there is an atom at $p^*$, then we can consider those units to belong to the group with propensity scores greater than $p^*$.
conditionThe set $\setb{p :\allowbreak\mathopen{} \Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} \Pi \geq p} \geq 1 / 2}$ is left-closed or empty.
propositionGiven Conditions \refmain{cond:reg-cond}, \refmain{cond:pscore-lipschitz} and \refmain{cond:left-closed}, when the matching is constructed without replacement using the true propensity score,
\begin{equation}
\lim_{n \to \infty} \E{\hat{\tau}_{\normalfontatt}} = \tau_{\normalfontatt} + \frac{\Pr{\Pi \geq p^*}}{2\bar{\pi}} \bracket[\Big]{\Es[\big]{\POpop{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1, \Pi \geq p^*} - \Es[\big]{\POpop{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0, \Pi \geq p^*}}.
\end{equation}
The proposition captures consequences of poor match quality among units with $\Pi_{i} \geq p^*$.
Specifically, it shows that the poor quality translates into bias.
There are two ways to achieve asymptotic unbiasedness, and thereby possibly consistency.
The first option is to assume that there is no confounding among units with $\Pi_{i} \geq p^*$:
equation[equation omitted — 225 chars of source]
Note that these expectations condition on a range of propensity scores rather than an exact score, so Condition (ref) does not imply that the expectations are equal.
The second option is to assume that there are no units above $p^*$, so that $\Pr{\Pi \geq p^*} = 0$.
This is only possible if $\Pr{\Pi \geq 1 / 2} = 0$.
This is a strengthening of the overlap assumption in Conditions (ref), requiring that $\pscore{x}$ is less than $1 / 2$ almost everywhere on the support of the covariate.
Neither option is attractive.
Some readers may object that the conditions used for Proposition (ref) are weaker than those typically used in applications and claim that consistency is achieved under slightly stronger conditions.
However, the proposition holds for all populations satisfying Conditions (ref), (ref) and (ref).
A strengthening of the conditions will therefore not lead to consistency unless the strengthening is exactly one of the two options discussed in the previous paragraph.
Their disjunction is a necessary condition for consistency in this setting.
Diminishing fraction of treated units
The paper has so far considered settings where the population is fixed throughout the asymptotic sequence.
Matching methods have also been studied in other asymptotic regimes.
For example, in addition to the regime used in this paper, Abadie2006Large investigate matching with replacement when the treated units are a diminishing fraction of the population.
They assume that the treated and control units are sampled separately in proportions such that $N_1^r / N_0 \to k$ for some $r > 1$ and $k < \infty$.
In other words, they consider the case in which $\bar{\pi} \to 0$.
The alternative regime is a better approximation of situations in which it is considerably easier to sample additional controls than it is to sample additional treated units.
One example is when a novel medical treatment is evaluated using conventional treatment as comparison.
The only patients with $W = 1$ are those in the hospitals offering the new treatment.
By virtue of being a novel treatment, such patients are rare.
However, patients with $W = 0$ are easy to find because there are many hospitals that offer the conventional treatment.
In an imagined sequence of samples, it is here appropriate to assume that the fraction of treated units would approach zero.
Abadie2012Martingale study matching without replacement in this regime, and they show that the matching estimator is consistent.
Their main contribution is a characterization of the large sample distribution of the estimator using a martingale representation.
The representation consists of a conditional bias term and a martingale array, of which the latter is the primary focus.
However, to achieve consistency, the conditional bias must be shown to diminish, which the authors demonstrate in an appendix.
This result critically depends on additional conditions on the asymptotic behavior of the population distribution.
In the standard asymptotic regime, all aspects of the population are fixed.
Besides $\bar{\pi}$, this includes the propensity score and the conditional densities of the treated and control units over the covariate set.
When we let $\bar{\pi} \to 0$, some of these other aspects must also change.
We cannot simultaneously hold the propensity score and the conditional densities fixed if the fraction of treated units approaches zero.
The route that Abadie2012Martingale take is to fix the conditional densities.
The consequence is that the propensity score approaches zero everywhere on the support of the covariate.
That is, they implicitly assume that $\pscore{x} \to 0$ for almost all $x$ on the support of $X$.
While it may be reasonable to consider the case $\bar{\pi} \to 0$, it may not always be reasonable to assume that $\pscore{x} \to 0$ holds everywhere.
The example with the hospitals and the novel treatment provides an illustration.
We can here sample patients with the conventional treatment much easier than we sample patients with the new treatment.
However, all these additional controls will be of a special type.
They will be patients in hospitals offering only the conventional treatment.
Among patients in hospitals offering the new treatment, a non-negligible fraction will be treated, so $\pscore{x} \to 0$ does not hold.
The illustration mirrors a sentiment that appears to be common among practitioners: when controls are abundant, most of them are not useful because they are too different from the treated units.
Put differently, it might be easy to find controls, but it is hard to find controls that are good.
A more appropriate regime might therefore be one that holds the propensity score fixed when $\bar{\pi} \to 0$, and adjusts the conditional densities as needed.
An inspection of the proof of Proposition (ref) suggests that not much would change under this regime, except that the relevant scaling is $\bar{\pi} n$ rather than $n$.
This means that consistency would require $\Pr{\Pi \geq p^*} / \bar{\pi} \to 0$, unless one assumes that there is no confounding among units above $p^*$.
Discussion
Practitioners often see consistency as an integral property of an estimator, and the result in this paper is discouraging for matching without replacement.
The picture becomes even grimmer with the realization that the variance of the estimator may converge to zero even if the bias does not.
Confidence intervals based on estimated standard errors would in that case be dangerously misleading.
This may prompt practitioners to reconsider whether matching without replacement is appropriate for their studies.
It would, however, be too rash to categorically dismiss matching without replacement based on these results.
Practitioners may be willing to accept the bias introduced by the method in light of its benefits, such as ease of analysis and a potential reduction in variance.
Furthermore, practitioners often examine the balance between treatment groups after matching.
The asymptotic bias demonstrated above would be mirrored by an imbalance in the propensity scores between the treatment groups.
In other words, to examine whether the concern raised here applies to a specific context, one can estimate $\Pr{\Pi \geq 1 / 2}$ and test if it differs from zero.
Practitioners may also use calipers when they construct their matchings Cochran1973Controlling.
The approach avoids matches of poor quality by excluding problematic units from the estimation.
Consistency would be achieved, at the cost of efficiency, if the caliper approaches zero as the sample grows, provided that the observations are weighted appropriately to account for the excluded treated units.
Abadie2011Bias describe a bias adjustment approach when the matching is done with replacement.
The purpose is to addresses the concern raised by Abadie2006Large that the unadjusted matching estimator sometimes converges at a slower than root-$n$ rate.
The adjustment requires estimates of the full response surfaces of the potential outcomes.
If these surfaces can be estimated consistently, a similar bias adjustment approach would address the concern raised in this paper.
However, consistency is then achieved solely because of our ability to estimate the response surfaces, and the matching step becomes largely redundant.
If the response surfaces are presumed to take some particular form, such as when they are estimated by a parametric model, then consistency would require functional form assumptions.
The feature that creates the asymptotic bias is the fact that the matching is done without replacement rather than that it is done using the propensity score.
This paper focused on propensity score matching for expositional reasons.
The supplement extends Proposition (ref) to matching without replacement using arbitrary matching scores and metrics.
This includes other balancing scores, various prognostic scores as discussed by Hansen2008prognostic, and Euclidean and Mahalanobis distances on raw or transformed covariates.
The form of the bias is similar to the form when using the propensity score, but the interpretation is somewhat more intricate, and additional regularity conditions are needed to derive the bias in closed form.
Nevertheless, the lesson is the same: matching without replacement is not generally consistent.
The focus of this paper was point estimation in the tradition of Abadie2006Large,Abadie2012Martingale.
An alternative approach to analyze matched samples is the randomization-based inference framework.
Rosenbaum2002Observational provides an overview.
Some features of this framework makes it difficult to judge whether the results in this paper also apply there.
For example, this literature rarely considers point estimators, and when they are considered, they are of the Hodges--Lehmann-type, which differ greatly from the type of estimator considered here.
Inherent to the permutation approach used in this literature is also that the analysis is conditional on the matching.
Still, the concerns raised here should motivate practitioners to be cautious also when working in the randomization-based framework.
Using the terminology of Rosenbaum2002Observational, this paper shows that there can be substantial “overt bias” even if the sample is large and all conventional matching conditions hold.
Therefore, practitioners should make sure to follow the recommendations by Rosenbaum2002Observational and others on how to address overt bias no matter the size of their sample.
Furthermore, practitioners should be wary about theoretical investigations that condition on the matching and assume the quality of the matching will improve without limit as the sample grows.
singlespace
\mtcaddpart[Supplement]
\setcounter{section}{0}
\setcounter{table}{0}
\setcounter{figure}{0}
\setcounter{equation}{0}
\setcounter{conjecture}{0}
\setcounter{corollary}{0}
\setcounter{lemma}{0}
\setcounter{proposition}{0}
\setcounter{theorem}{0}
\setcounter{assumption}{0}
\setcounter{condition}{0}
\setcounter{definition}{0}
\setcounter{remark}{0}
\setcounter{example}{0}
\renewcommand#1.\arabic{section}{S.\arabic{section}}
\renewcommand#1.\arabic{table}{S.\arabic{table}}
\renewcommand#1.\arabic{figure}{S.\arabic{figure}}
\renewcommand#1.\arabic{equation}{S.\arabic{equation}}
\renewcommand#1.\arabic{conjecture}{S.\arabic{conjecture}}
\renewcommand#1.\arabic{corollary}{S.\arabic{corollary}}
\renewcommand#1.\arabic{lemma}{S.\arabic{lemma}}
\renewcommand#1.\arabic{proposition}{S.\arabic{proposition}}
\renewcommand#1.\arabic{theorem}{S.\arabic{theorem}}
\renewcommand#1.\arabic{assumption}{S.\arabic{assumption}}
\renewcommand#1.\arabic{condition}{S.\arabic{condition}}
\renewcommand#1.\arabic{definition}{S.\arabic{definition}}
\renewcommand#1.\arabic{remark}{S.\arabic{remark}}
\renewcommand#1.\arabic{example}{S.\arabic{example}}
\renewcommand#1\arabic{section}{S\arabic{section}}
\renewcommand#1\arabic{table}{S\arabic{table}}
\renewcommand#1\arabic{figure}{S\arabic{figure}}
\renewcommand#1\arabic{equation}{S\arabic{equation}}
\renewcommand#1\arabic{conjecture}{S\arabic{conjecture}}
\renewcommand#1\arabic{corollary}{S\arabic{corollary}}
\renewcommand#1\arabic{lemma}{S\arabic{lemma}}
\renewcommand#1\arabic{proposition}{S\arabic{proposition}}
\renewcommand#1\arabic{theorem}{S\arabic{theorem}}
\renewcommand#1\arabic{assumption}{S\arabic{assumption}}
\renewcommand#1\arabic{condition}{S\arabic{condition}}
\renewcommand#1\arabic{definition}{S\arabic{definition}}
\renewcommand#1\arabic{remark}{S\arabic{remark}}
\renewcommand#1\arabic{example}{S\arabic{example}}
center[center omitted — 40 chars of source]
\parttoc
Matching with arbitrary scores and metrics
Extension of main proposition
\DeclarePairedDelimiterXPP\distS[2]{d_S}{\lparen}{\rparen}{#1, #2}
The main paper showed that the estimator of the average treatment effect of the treated was not generally consistent when matching without replacement using the propensity score.
That is, the metric $d : \mathcal{X} \times \mathcal{X} \to \mathbb{R}^+$ used for the matching was the absolute differences in propensity scores: $\dist{x}{x'} = \abs{\pscore{x} - \pscore{x'}}$.
This section extends this result to matching without replacement using arbitrary metrics over arbitrary scores.
In the interest of space, the proof of the extension will be somewhat informal.
Let $s \colon \mathcal{X} \to \mathcal{S}$ be a score function summarizing the covariates.
This function could be any type of dimensionality reduction, including the propensity score, other balancing scores and prognostic scores.
The score can be multidimensional, so that $\func{s}{X}$ is a vector.
The score can also be the identity function, so that $X = \func{s}{X}$.
Let $S = \func{s}{X}$ be a random variable describing the distribution of the score in the population.
For convenience, we assume that the score $S$ is continuously distributed.
Let $\mathcal{S}_{\normalfont\textsc{supp}}$ be the support of $S$.
The score is associated with some metric $d_S : \mathcal{S} \times \mathcal{S} \to \mathbb{R}^+$ that captures similarity between different scores.
If the score is scalar, this will often be the absolute difference $\distS{s}{s'} = \abs{s - s'}$.
For multidimensional scores, it might be Euclidean or Mahalanobis distances.
However, the current discussion is not restricted to these particular metrics; it applies to any metric satisfying the conditions below.
Note that the score function and its associated metric induces a pseudometric on the raw covariates: $\dist{x}{x'} = \distS{\func{s}{x}}{\func{s}{x'}}$.
We will extend the standard matching assumptions specified in Conditions \refmain{cond:reg-cond} and \refmain{cond:pscore-lipschitz} in the main paper to the score $S$ considered here.
This is formalized in the following three conditions.
conditionThe population satisfies:
\begin{enumerate}[label=\roman*.,ref=\ref*{cond:reg-cond-arb-score}.\roman*]
• Unconfoundedness: $\POpop{0}$ is conditionally independent of $W$ given $S = s$ on $\mathcal{S}_{\normalfont\textsc{supp}}$.
• Overlap: $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S = s}$ is bounded away from one on $\mathcal{S}_{\normalfont\textsc{supp}}$.
• Existence of treated units: $\Pr{W = 1}$ is greater than zero.
• Abundance of control units: $\Pr{W = 1}$ is less than one-half.
• Well-behaved outcomes: $\E{Y^2}$ exists.
\end{enumerate}
condition[Continuity]
$\Es{\POpop{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S = s}$ is Lipschitz continuous on $\mathcal{S}_{\normalfont\textsc{supp}}$ with respect to metric $d_S$.
That is, there exists a constant $c$ such that for all $s,s' \in \mathcal{S}_{\normalfont\textsc{supp}}$,
\begin{equation}
\abs[\big]{\Es{\POpop{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen S = s} - \Es{\POpop{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen S = s'}} \leq c \times \distS{s}{s'}.
\end{equation}
condition[Assignment continuity]
$\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S = s}$ is Lipschitz continuous on $\mathcal{S}_{\normalfont\textsc{supp}}$ with respect to metric $d_S$.
Conditions (ref) and (ref) correspond directly to Conditions \refmain{cond:reg-cond} and \refmain{cond:pscore-lipschitz} in the main paper, but there is no condition in the main paper that corresponds to Condition (ref).
Indeed, the condition is satisfied by construction when $S$ is the propensity score, because $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S = s} = s$ in that case.
Continuity of the conditional assignment probability function does not hold by construction for other scores, and it is therefore explicitly imposed here.
The purpose of Condition (ref) is to rule out situations where the assignment mechanism is highly fragmented with respect to the score, so that minute perturbations of the score could lead to large changes in the probability of being treated.
Such fragmented assignment mechanisms could facilitate identification using local extrapolation rather than the conventional overlap motivation.
Indeed, consider a scalar, real-valued score $S$ and an assignment mechanism for which $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S = s} = 0$ if $s$ is a rational number and $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S = s} = 1$ otherwise.
Overlap does not hold in this case, but identification of the average treatment effect for the treated is possible because the rationals are dense in the reals, so Condition (ref) allows us to extrapolate $\Es{\POpop{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S = s}$ from the rationals to the remaining real numbers.
Given an appropriate marginal distribution of $S$, matching without replacement could be consistent in this setting.
Condition (ref) rules out this alternative motivation for matching, instead focusing the discussion on the conventional setting.
The condition can be weakened at the cost of additional complexity.
To extend the result in the main paper to arbitrary matching scores, we will consider subsets of $\mathcal{S}_{\normalfont\textsc{supp}}$ defined based on the local probability of being treated.
Let
equation[equation omitted — 185 chars of source]
collect all scores for which the corresponding conditional probability of being treated is one half or greater.
Let $\mathcal{A}$ collect all supersets of $\mathcal{S}_{+}$ for which exactly one half of the constituent units are treated.
That is, $\mathcal{A}$ contains all sets $\mathcal{Q} \subseteq \mathcal{S}_{\normalfont\textsc{supp}}$ such that
equation[equation omitted — 174 chars of source]
Condition (ref) together with continuity of $S$ ensure that $\mathcal{A}$ is not empty.
For any $\mathcal{Q} \in \mathcal{A}$, let $\nu_{\mathcal{Q},w}$ be the density of the score $S$ conditional on $S \in \mathcal{Q}$ and $W = w$.
That is, if $f$ is the probability density function of $S$, then
equation[equation omitted — 97 chars of source]
For any $\mathcal{Q} \in \mathcal{A}$, let $\func{\Gamma}{\mathcal{Q}}$ collect all couplings between $\nu_{\mathcal{Q},1}$ and $\nu_{\mathcal{Q},0}$.
That is, $\func{\Gamma}{\mathcal{Q}}$ contains all joint densities over $\mathcal{Q} \times \mathcal{Q}$ such that the two marginal densities of each $\gamma \in \func{\Gamma}{\mathcal{Q}}$ equal $\nu_{\mathcal{Q},1}$ and $\nu_{\mathcal{Q},0}$, respectively.
This allows us to define the Wasserstein distance of order one between $\nu_{\mathcal{Q},1}$ and $\nu_{\mathcal{Q},0}$:
equation[equation omitted — 166 chars of source]
We will consider a lower bound on a weighted version of the Wasserstein distance in the set $\mathcal{A}$:
equation[equation omitted — 198 chars of source]
The weight $\Pr{S \in \mathcal{Q} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} W = 1}$ gives the proportion of treated units that are in $\mathcal{Q}$.
condition[Existence of minimum]
There exists some $\mathcal{S}^{*} \in \mathcal{A}$ that attains the infimum, so that $\Pr{S \in \mathcal{S}^{*} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} W = 1} \times \func{\mathcal{W}}{\mathcal{S}^{*}} = \mathcal{W}^*$.
Condition (ref) is akin to Condition \refmain{cond:left-closed} in the main paper, which allowed us to disregard situations where the boundary of the partition needed to be split between the two parts of the partition.
Similar to Condition \refmain{cond:left-closed}, it is possible to remove this assumption, at the cost of considerably technical complexity.
As this added complexity would bring no interesting insights, we proceed under the assumption that $\mathcal{S}^{*}$ exists.
We are now ready to state the extension of Proposition \refmain{prop:pscore-bias}.
propositionGiven Conditions (ref), (ref), (ref) and (ref), when the matching is constructed without replacement using the score $S$ and metric $d_S$,
\begin{equation}
\lim_{n \to \infty} \E{\hat{\tau}_{\normalfontatt}} = \tau_{\normalfontatt} + \frac{\Pr{S \in \mathcal{S}^{*}}}{2\bar{\pi}} \bracket[\Big]{\Es[\big]{\POpop{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1, S \in \mathcal{S}^{*}} - \Es[\big]{\POpop{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0, S \in \mathcal{S}^{*}}}.
\end{equation}
proof[Sketch of proof]
The proof uses a partitioning argument similar to the one used in the main paper.
Consider constructing a matching in the population.
The set $\mathcal{S}_{+}$ is the region of $\mathcal{S}_{\normalfont\textsc{supp}}$ where, at every point, there are at least as many treated units as control units.
Unless $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S = s} = 1/2$ for all $s \in \mathcal{S}_{+}$, we have that $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S \in \mathcal{S}_{+}} > 1/2$.
That is, there will be an abundance of treated units in the region $\mathcal{S}_{+}$.
Because each treated unit must be matched to a unique control unit, there will not be enough control units in $\mathcal{S}_{+}$.
In other words, an abundance of treated units in $\mathcal{S}_{+}$ means that some of these units must be matched to control units outside of $\mathcal{S}_{+}$.
In particular, a share
\begin{equation}
\frac{\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen S \in \mathcal{S}_{+}} - \Pr{W = 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen S \in \mathcal{S}_{+}}}{\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen S \in \mathcal{S}_{+}}}
\end{equation}
of the treated units in $\mathcal{S}_{+}$ will be matched to control units outside of $\mathcal{S}_{+}$.
Consider which control units these excess treated units will be matched to.
Let $\mathcal{S}_{c} \subset \mathcal{S}_{\normalfont\textsc{supp}}$ be some set that does not overlap with $\mathcal{S}_{+}$, so that $\mathcal{S}_{+} \cap \mathcal{S}_{c} = \emptyset$.
Because $\mathcal{S}_{+}$ contains all points with $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S = s} \geq 1/2$, the set $\mathcal{S}_{c}$ must contain points for which $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S = s} < 1/2$.
Hence, there will be an abundance of control units in $\mathcal{S}_{c}$.
Naively, we could take all control units in $\mathcal{S}_{c}$ and match with the excess treated units in $\mathcal{S}_{+}$ to address the problem that there is an abundance of treated units in $\mathcal{S}_{+}$.
If there are sufficiently many control units in $\mathcal{S}_{c}$, so that
\begin{equation}
\Pr{W = 0, S \in \mathcal{S}_{c}} \geq \Pr{W = 1, S \in \mathcal{S}_{+}} - \Pr{W = 0, S \in \mathcal{S}_{+}},
\end{equation}
then we can match all treated units in $\mathcal{S}_{+}$ with control units in either $\mathcal{S}_{+}$ or $\mathcal{S}_{c}$.
However, unless there are only control units in $\mathcal{S}_{c}$, so that $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S \in \mathcal{S}_{c}} = 0$, this naive approach will potentially leave treated units in $\mathcal{S}_{c}$ unmatched.
Consider the union $\mathcal{Q} = \mathcal{S}_{+} \cup \mathcal{S}_{c}$.
Following the naive approach, this union may still contain an abundance of treated units, because the treated units in $\mathcal{S}_{c}$ must also be matched, but they cannot be matched with control units in $\mathcal{S}_{c}$ if all those units have been matched with treated units in $\mathcal{S}_{+}$.
Thus, to properly address the problem that there is an abundance of treated units in $\mathcal{S}_{+}$, we need to find a set $\mathcal{S}_{c}$ such that the union $\mathcal{Q} = \mathcal{S}_{+} \cup \mathcal{S}_{c}$ consists of exactly half treated units:
\begin{equation}
\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen S \in \mathcal{Q}} = 1/2.
\end{equation}
The set $\mathcal{A}$ defined above collects all such unions $\mathcal{Q}$.
In order words, $\mathcal{A}$ collects all possible solutions to the problem that there is an abundance of treated units in $\mathcal{S}_{+}$.
We will now break the overall matching problem into two steps.
The first step is to find a partition of $\mathcal{S}_{\normalfont\textsc{supp}}$ into sets $\mathcal{Q}$ and $\mathcal{Q}^\mathsf{c}$, such that $\mathcal{Q} \in \mathcal{A}$.
The second step is to find the optimal matching within each of the two sets.
If there are no matches in the optimal matching bridging $\mathcal{Q}$ and $\mathcal{Q}^\mathsf{c}$, so that no unit in $\mathcal{Q}$ is matched with a unit in its complement $\mathcal{Q}^\mathsf{c} = \mathcal{S}_{\normalfont\textsc{supp}} \setminus \mathcal{Q}$, then we can consider these two matching problems separately.
For this approach to work, we must verify that the optimal solution can be partitioned in this way.
To show this, let $\mathcal{B}$ collect all sets $\mathcal{Q} \subseteq \mathcal{S}_{\normalfont\textsc{supp}}$ satisfying three properties.
The first property is that $\mathcal{S}_{+}$ is a subset of $\mathcal{Q}$.
The second property is that at most half of the units in $\mathcal{Q}$ are treated: $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S \in \mathcal{Q}} \leq 1/2$.
The third property is that no unit in $\mathcal{Q}$ is matched to a unit in $\mathcal{Q}^\mathsf{c}$ in the optimal matching solution.
Note that $\mathcal{B}$ is non-empty; for example, Condition (ref) ensures that $\mathcal{S}_{\normalfont\textsc{supp}} \in \mathcal{B}$.
We will show that $\mathcal{B}$ contains one set $\mathcal{Q}$ with $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S \in \mathcal{Q}} = 1/2$, which implies $\mathcal{Q} \in \mathcal{A}$, as desired.
Consider some partition $\mathcal{Q} \in \mathcal{B}$ for which $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S \in \mathcal{Q}} < 1/2$.
We will show that there is a set $\mathcal{Q}' \subset \mathcal{Q}$ such that $\mathcal{Q}' \in \mathcal{B}$.
Because $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S \in \mathcal{Q}} < 1/2$, there will be a region $\mathcal{R} \in \mathcal{Q}$ with unmatched control units in an infinitesimally small neighborhood around every point $s \in \mathcal{R}$.
Let $M$ denote whether a control unit is matched.
That is, $M = 1$ denotes a control unit that is matched with a treated unit; for example, $\Pr{M = 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} W = 0}$ is the share of control units that are not matched.
The region $\mathcal{R} \in \mathcal{Q}$ is such that $\Pr{M = 0, W = 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S = s} > 0$ for all $s \in \mathcal{R}$.
Condition (ref) ensures that there exists a $\mathcal{R}$ that is connected.
Note that all treated units in $\mathcal{R}$ are matched with control units infinitesimally close to them.
If they were not, we could improve the matching by changing their matches to infinitesimally close unmatched control units, which we know exists by construction of $\mathcal{R}$.
Hence, if any control units in $\mathcal{R}$ are matched to treated units that are not infinitesimally close, they must be matched to units outside of $\mathcal{R}$.
Consider the share of control units in $\mathcal{R}$ that are matched with treated units outside of $\mathcal{R}$:
\begin{equation}
\Pr{M = 1, S \in \mathcal{R}} - \Pr{W = 1, S \in \mathcal{R}}.
\end{equation}
Note that this difference cannot be negative, because all treated units in $\mathcal{R}$ are matched with control units in $\mathcal{R}$.
We will now show that the difference cannot be positive.
If the difference is positive, consider a subset $\mathcal{K} \subset \mathcal{R}$ such that
\begin{equation}
\Pr{M = 0, W = 0, S \in \mathcal{R}}
= \Pr{W = 0, S \in \mathcal{K}} - \Pr{W = 1, S \in \mathcal{K}}.
\end{equation}
The left hand side is the share of unmatched control units in $\mathcal{R}$.
The right hand side is the share of excess control units in $\mathcal{K}$; that is, the leftover control units after all treated units in $\mathcal{K}$ have been matched with control units in $\mathcal{K}$.
Because $\mathcal{R}$ is connected and all matched control units in $\mathcal{R}$ are matched with treated units outside of $\mathcal{R}$ if they are not matched with treated units that are not infinitesimally close, we can pick $\mathcal{K}$ to be the region farthest from the excess treated units outside of $\mathcal{R}$.
For example, if $S$ is uniformly distributed, $\mathcal{R} = \braces{s' : \distS{s'}{s} \leq r}$ is a ball centered at $s$ with $r$ as radius, $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S = s}$ is constant in $\mathcal{R}$, and the treated units outside of $\mathcal{R}$ that are matched with control units in $\mathcal{R}$ are evenly distributed around $\mathcal{R}$, then $\mathcal{K} = \braces{s' : \distS{s'}{s} \leq r'}$ will be a ball centered at $s$ with some radius $r' < r$.
Because $\mathcal{K}$ is farthest from the treated units outside of $\mathcal{R}$, no control unit in $\mathcal{K}$ will be matched to treated units outside of $\mathcal{K}$, so
\begin{equation}
\Pr{M = 1, S \in \mathcal{K}} = \Pr{W = 1, S \in \mathcal{K}}.
\end{equation}
But this would imply that all control units that are in $\mathcal{R} \setminus \mathcal{K}$ are matched:
\begin{equation}
\Pr{W = 0, S \in \mathcal{R} \setminus \mathcal{K}} = \Pr{M = 1, S \in \mathcal{R} \setminus \mathcal{K}}.
\end{equation}
To see this, write
\begin{align}
\Pr{W = 0, S \in \mathcal{R} \setminus \mathcal{K}} &= \Pr{W = 0, S \in \mathcal{R}} - \Pr{W = 0, S \in \mathcal{K}},
\\
\Pr{M = 1, S \in \mathcal{R} \setminus \mathcal{K}} &= \Pr{M = 1, S \in \mathcal{R}} - \Pr{M = 1, S \in \mathcal{K}},
\end{align}
so that
\begin{multline}
\Pr{W = 0, S \in \mathcal{R} \setminus \mathcal{K}} - \Pr{M = 1, S \in \mathcal{R} \setminus \mathcal{K}}
\\
= \Pr{W = 0, S \in \mathcal{R}} - \Pr{M = 1, S \in \mathcal{R}} + \Pr{M = 1, S \in \mathcal{K}} - \Pr{W = 0, S \in \mathcal{K}}.
\end{multline}
Note that
\begin{equation}
\Pr{W = 0, S \in \mathcal{R}} - \Pr{M = 1, S \in \mathcal{R}} = \Pr{M = 0, W = 0, S \in \mathcal{R}},
\end{equation}
which by construction of $\mathcal{K}$ is equal to
\begin{equation}
\Pr{W = 0, S \in \mathcal{K}} - \Pr{W = 1, S \in \mathcal{K}}.
\end{equation}
Furthermore, $\mathcal{K}$ was constructed so that
\begin{equation}
\Pr{M = 1, S \in \mathcal{K}} = \Pr{W = 1, S \in \mathcal{K}}.
\end{equation}
It then follows that
\begin{multline}
\Pr{W = 0, S \in \mathcal{R} \setminus \mathcal{K}} - \Pr{M = 1, S \in \mathcal{R} \setminus \mathcal{K}}
\\
= \Pr{W = 0, S \in \mathcal{K}} - \Pr{W = 1, S \in \mathcal{K}} + \Pr{W = 1, S \in \mathcal{K}} - \Pr{W = 0, S \in \mathcal{K}},
\end{multline}
which is zero.
We have concluded that if
\begin{equation}
\Pr{M = 1, S \in \mathcal{R}} - \Pr{W = 1, S \in \mathcal{R}} > 0,
\end{equation}
then
\begin{equation}
\Pr{W = 0, S \in \mathcal{R} \setminus \mathcal{K}} = \Pr{M = 1, S \in \mathcal{R} \setminus \mathcal{K}}.
\end{equation}
However, this contradicts the definition of $\mathcal{R}$, which stipulated that there were unmatched control units in an infinitesimally small neighborhood around every point $s \in \mathcal{R}$.
The only possibility is therefore that $\mathcal{K} = \mathcal{R}$, but $\mathcal{K}$ was such that
\begin{equation}
\Pr{M = 1, S \in \mathcal{K}} = \Pr{W = 1, S \in \mathcal{K}},
\end{equation}
which again contradicts
\begin{equation}
\Pr{M = 1, S \in \mathcal{R}} - \Pr{W = 1, S \in \mathcal{R}} > 0,
\end{equation}
because $\mathcal{K} = \mathcal{R}$.
We have now showed that for any $\mathcal{Q} \in \mathcal{B}$ such that $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S \in \mathcal{Q}} < 1/2$, there exists a $\mathcal{R}\in \mathcal{Q}$ with the properties stipulated above and
\begin{equation}
\Pr{M = 1, S \in \mathcal{R}} = \Pr{W = 1, S \in \mathcal{R}}.
\end{equation}
In other words, no unit in $\mathcal{R}$ is matched with a unit in $\mathcal{Q}' = \mathcal{Q} \setminus \mathcal{R}$.
We will now consider $\mathcal{Q}'$ in lieu of $\mathcal{Q}$.
Recall that $\mathcal{R}$ contains an excess of control units.
Therefore, when we remove $\mathcal{R}$ from $\mathcal{Q}$ to construct $\mathcal{Q}'$, we have
\begin{equation}
\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen S \in \mathcal{Q}} < \Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen S \in \mathcal{Q}'},
\end{equation}
and because no treated unit in $\mathcal{Q}'$ is matched with a control unit outside of $\mathcal{Q}'$, we also have
\begin{equation}
\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen S \in \mathcal{Q}'} \leq 1/2.
\end{equation}
It follows that $\mathcal{Q}' \in \mathcal{B}$.
Continuity of $S$ implies that we can apply this procedure recursively until we reach a $\mathcal{Q}'$ such that
\begin{equation}
\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen S \in \mathcal{Q}'} = 1/2,
\end{equation}
which implies that $\mathcal{Q}' \in \mathcal{B}$ and $\mathcal{Q}' \in \mathcal{A}$, as desired.
We have now showed that we can reformulate the overall matching problem in the population into two parts.
The first part is to find a partition of $\mathcal{S}_{\normalfont\textsc{supp}}$ into sets $\mathcal{Q}$ and $\mathcal{Q}^\mathsf{c}$, such that $\mathcal{Q} \in \mathcal{A}$, and the second part is to find an optimal matching within each of the sets $\mathcal{Q}$ and $\mathcal{Q}^\mathsf{c}$ separately.
We will consider this problem in reverse.
Starting with the second step, we can use transport theory to characterize the optimal matching in $\mathcal{Q}$.
We use a bijection between the treated and control units in $\mathcal{Q}$ to describe the matching between the units.
For infinite populations, we can describe such a matching as a coupling between the conditional distributions of the score within $\mathcal{Q}$.
Let $\func{\nu_{\mathcal{Q},w}}{s} = \func{f}{s \mid S \in \mathcal{Q}, W = w}$ be the conditional density of $S$ for units in $\mathcal{Q}$ that are assigned treatment $W = w$.
Consider a density $\gamma$ over $\mathcal{Q} \times \mathcal{Q}$ with the property that its marginals are equal to $\nu_{\mathcal{Q},1}$ and $\nu_{\mathcal{Q},0}$.
The matching objective for the optimal matching within $\mathcal{Q}$ is therefore given by
\begin{equation}
\func{\mathcal{W}}{\mathcal{Q}} = \inf_{\gamma \in \func{\Gamma}{\mathcal{Q}}} \int_{\mathcal{Q} \times \mathcal{Q}} \distS{s}{s'} \mathrm{d} \gamma.
\end{equation}
It is straightforward to characterize the optimal matching in $\mathcal{Q}^\mathsf{c} = \mathcal{S}_{\normalfont\textsc{supp}} \setminus \mathcal{Q}$.
Recall that no control unit in this region is matched with any treated unit in $\mathcal{Q}$.
Furthermore, because $\mathcal{S}_{+} \subseteq \mathcal{Q}$, we have that $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S = s} < 1/2$ for all $s \in \mathcal{Q}^\mathsf{c}$.
That is, at every point in $\mathcal{Q}^\mathsf{c}$, there is an abundance of control units in a small neighborhood around that point.
This means that all treated units in $\mathcal{Q}^\mathsf{c}$ can be matched to a control unit that is infinitesimally close with respect to the score.
For this reason, the optimal matching in $\mathcal{Q}^\mathsf{c}$ will attain a value of the matching objective that is zero.
Continuing with the first step, which was to find the partition into $\mathcal{Q}$ and $\mathcal{Q}^\mathsf{c}$, the overall matching objective is the weighted sum of the matching objective within $\mathcal{Q}$, with weight $\Pr{S \in \mathcal{Q} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} W = 1}$, and the matching objective within $\mathcal{Q}^\mathsf{c}$, with weight $\Pr{S \not\in \mathcal{Q} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} W = 1}$.
In other words, the overall matching objective is
\begin{equation}
\Pr{S \in \mathcal{Q} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1} \times \func{\mathcal{W}}{\mathcal{Q}} + \Pr{S \not\in \mathcal{Q} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1} \times 0,
\end{equation}
which is lower bounded in $\mathcal{A}$ by
\begin{equation}
\mathcal{W}^* = \inf_{\mathcal{Q} \in \mathcal{A}} \Pr{S \in \mathcal{Q} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1} \times \func{\mathcal{W}}{\mathcal{Q}}.
\end{equation}
Condition (ref) states that this lower bound is attainable by some $\mathcal{S}^{*} \in \mathcal{A}$:
\begin{equation}
\Pr{S \in \mathcal{S}^{*} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1} \times \func{\mathcal{W}}{\mathcal{S}^{*}} = \mathcal{W}^*.
\end{equation}
This means that $\mathcal{S}^{*}$ is the partition of the optimal matching.
Note that the partition of $\mathcal{S}_{\normalfont\textsc{supp}}$ into $\mathcal{S}^{*}$ and $\mathcal{S}^\mathsf{c} = \mathcal{S}_{\normalfont\textsc{supp}} \setminus \mathcal{S}^{*}$ resembles the partition in the main paper.
In particular, all control units in $\mathcal{S}^{*}$ are matched with treated units, while there is an abundance of control units at every point in $\mathcal{S}^\mathsf{c}$.
The behavior of the matching is therefore radically different in $\mathcal{S}^{*}$ and $\mathcal{S}^\mathsf{c}$.
We can use this fact to characterize the bias.
As above, let $M$ denote whether a control unit is matched.
The population version of the matching estimator considered in the main paper is
\begin{equation}
\E{Y \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1} - \E{Y \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen M = 1} = \Es{\POpop{1} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1} - \Es{\POpop{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen M = 1},
\end{equation}
which gives a population bias with respect to $\tau_{\normalfont\textsc{att}} = \Es{\POpop{1} - \POpop{0}\nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} W = 1}$ equal to
\begin{equation}
\Es{\POpop{0}\nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1} - \Es{\POpop{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen M = 1}.
\end{equation}
Use the law of total expectation and the partition of $\mathcal{S}_{\normalfont\textsc{supp}}$ into $\mathcal{S}^{*}$ and $\mathcal{S}^\mathsf{c}$ to decompose the terms of the bias:
\begin{align}
\Es{\POpop{0}\nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1} &= \Pr{S \in \mathcal{S}^{*} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1} \Es[\big]{\POpop{0}\nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1, S \in \mathcal{S}^{*}}
\\
&\qquad\qquad+ \Pr{S \in \mathcal{S}^\mathsf{c} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1} \Es[\big]{\POpop{0}\nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1, S \in \mathcal{S}^\mathsf{c}},
\\[0.5em]
\Es{\POpop{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen M = 1} &= \Pr{S \in \mathcal{S}^{*} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen M = 1} \Es[\big]{\POpop{0}\nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen M = 1, S \in \mathcal{S}^{*}}
\\
&\qquad\qquad+ \Pr{S \in \mathcal{S}^\mathsf{c} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen M = 1} \Es[\big]{\POpop{0}\nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen M = 1, S \in \mathcal{S}^\mathsf{c}}.
\end{align}
The fact that no unit in $\mathcal{S}^{*}$ is matched with a unit in $\mathcal{S}^\mathsf{c}$ implies that
\begin{equation}
\Pr{S \in \mathcal{S}^{*} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1} = \Pr{S \in \mathcal{S}^{*} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen M = 1}
\end{equation}
and
\begin{equation}
\Pr{S \in \mathcal{S}^\mathsf{c} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1} = \Pr{S \in \mathcal{S}^\mathsf{c} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen M = 1}.
\end{equation}
We can therefore write the bias as
\begin{multline}
\Pr{S \in \mathcal{S}^{*} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1} \bracket[\Big]{ \Es[\big]{\POpop{0}\nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1, S \in \mathcal{S}^{*}} - \Es[\big]{\POpop{0}\nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen M = 1, S \in \mathcal{S}^{*}} },
\\
+
\Pr{S \in \mathcal{S}^\mathsf{c} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1} \bracket[\Big]{ \Es[\big]{\POpop{0}\nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1, S \in \mathcal{S}^\mathsf{c}} - \Es[\big]{\POpop{0}\nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen M = 1, S \in \mathcal{S}^\mathsf{c}} }.
\end{multline}
Recall that each treated unit in $\mathcal{S}^\mathsf{c}$ will be matched to a control unit that is infinitesimally close.
This fact together with Condition (ref) implies that
\begin{equation}
\Es[\big]{\POpop{0}\nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1, S \in \mathcal{S}^\mathsf{c}} = \Es[\big]{\POpop{0}\nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen M = 1, S \in \mathcal{S}^\mathsf{c}},
\end{equation}
so the second term of the bias is zero.
Also recall that all control units in $\mathcal{S}^{*}$ are matched, which implies that
\begin{equation}
\Es[\big]{\POpop{0}\nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen M = 1, S \in \mathcal{S}^{*}} = \Es[\big]{\POpop{0}\nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0, S \in \mathcal{S}^{*}}.
\end{equation}
Finally, use Bayes' rule to write
\begin{equation}
\Pr{S \in \mathcal{S}^{*} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1}
= \frac{\Pr{S \in \mathcal{S}^{*}} \Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen S \in \mathcal{S}^{*} }}{\Pr{W = 1}}
= \frac{\Pr{S \in \mathcal{S}^{*}}}{2 \bar{\pi}},
\end{equation}
which follows from $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S \in \mathcal{S}^{*} } = 1/2$ and $\Pr{W = 1} = \bar{\pi}$.
Taken together, we have showed that the bias in the population is
\begin{equation}
\frac{\Pr{S \in \mathcal{S}^{*}}}{2 \bar{\pi}} \bracket[\Big]{ \Es[\big]{\POpop{0}\nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1, S \in \mathcal{S}^{*}} - \Es[\big]{\POpop{0}\nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0, S \in \mathcal{S}^{*}} },
\end{equation}
which is the statement in the proposition.
As mentioned in the beginning of this section, the proof of Proposition (ref) is informal compared to the proof of the result in the main paper presented below.
The most notable omission is that the proof here solely considers matching in the population.
To make the proof rigorous and complete, one would need to show that the sequence of matchings in the samples convergences in an appropriate sense to the population matching.
The bulk of the proof of Proposition \refmain{prop:pscore-bias} consists of showing this type of convergence, and it has been omitted in the proof of the extension in the interest of space.
Example: Prognostic score
This section provides an example that illustrates the result in the previous section.
The focus is when the score used for to construct the matching is a prognostic score as described by Hansen2008prognostic.
Consider a three-dimensional covariate $X = \paren{X_1, X_2, X_3}$, for which each coordinate is uniformly distributed on $[0, 1]$ and independent of the other two.
Let the propensity score be the product of the first and second covariates when the second covariate is taken to the power of $a \geq 1/3$:
equation[equation omitted — 120 chars of source]
Consider a score function $s \colon \mathcal{X} \to \mathcal{S}$ given by $\func{s}{x} = x_1 + x_3$, so that $S = X_1 + X_3$ with probability one.
The density of $S$ is $\func{f}{s} = s$ when $s \leq 1$, and $\func{f}{s} = 2 - s$ when $s > 1$.
Note that $\mathcal{S}_{\normalfont\textsc{supp}} = [0, 2]$.
The metric for the score is the absolute difference: $\distS{s}{s'} = \abs{s - s'}$.
Let the potential outcomes be distributed as
equation[equation omitted — 106 chars of source]
where $\varepsilon_0$ and $\varepsilon_1$ are independent standard normal variates.
This means that the average treatment effect of the treated is one, $\tau_{\normalfont\textsc{att}} = 1$, irrespectively of $a$.
Note that $S$ is a prognostic score: $\POpop{0} \protect\mathpalette{\protect\@indep}{\perp} X \mid S$.
We will now verify that this data generating process satisfies Conditions (ref), (ref) and (ref).
Unconfoundedness follows directly from the fact that $S$ is a prognostic score.
To verify overlap, consider the probability of being treated given the score:
equation[equation omitted — 346 chars of source]
where the first equality follows from binary $W$, the second equality follows from the definition of the propensity score, and the third equality follows from that $X_1$, $X_2$ and $X_3$ are mutually independent.
Note that
equation[equation omitted — 85 chars of source]
To derive $\E{X_1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S = s}$, note that $X_1 = S - X_3$ with probability one, so we can write
equation[equation omitted — 259 chars of source]
We have $\E{X_1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S = s} = \E{X_3 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S = s}$ because of symmetry, so $\E{X_1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S = s} = s / 2$.
Taken together, we have
equation[equation omitted — 205 chars of source]
Note that $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S = s}$ is increasing in $s$, and that $S$ takes its highest value when $X_1 = X_3 = 1$, in which case $S = 2$.
The conditional probability $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S = s}$ is therefore at most $1 / \paren{ a + 1 }$, which is bounded away from one as long as $a > 0$.
We have thus verified the overlap part of Condition (ref).
To verify the existence of treated units and abundance of control units, note that
equation[equation omitted — 163 chars of source]
where the final equality follows from that $\E{S} = \E{X_1} + \E{X_3} = 2 \times 0.5$.
Hence, $\Pr{W = 1} > 0$ as long as $a < \infty$, and $\Pr{W = 1} < 1/2$ as long as $a > 0$.
The fifth part of Condition (ref), which is that $\E{Y^2}$ exists, is satisfied by the fact that $\abs{S}$ is bounded by two.
Condition (ref) is satisfied by independence of $\varepsilon_0$, which implies that $\Es{\POpop{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S = s} = s^2$.
Condition (ref) is satisfied by the fact that $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S = s}$ here is a linear function.
We can conclude that this data generating process satisfies Conditions (ref), (ref) and (ref).
This means that Proposition (ref) applies, and we have
equation[equation omitted — 401 chars of source]
We proceed by deriving this bias term.
The first step is to find the sets $\mathcal{S}_{+}$ and $\mathcal{S}^{*}$.
Recall that
equation[equation omitted — 186 chars of source]
which for the current data generating process is $\mathcal{S}_{+} = [a + 1, 2]$.
If $a \geq 1$, then $\mathcal{S}_{+}$ has no mass.
Following the argument in the proof of Proposition (ref), we have $\mathcal{S}^{*} = \bracket{b, 2}$, where $b$ is such that $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S \in \mathcal{S}^{*}} = 1/2$.
Note that
equation[equation omitted — 379 chars of source]
where $\func{f}{s}$ is the density of $S$.
Calculate the integrals:
equation[equation omitted — 199 chars of source]
and
equation[equation omitted — 212 chars of source]
Hence, when $b \geq 1$,
equation[equation omitted — 135 chars of source]
and we attain $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S \in \bracket{b, 2}} = 1/2$ with $b = \paren{3a + 1} / 2$, provided that $a \geq 1/3$.
Therefore, $\mathcal{S}^{*} = \bracket{ \paren{3a + 1} / 2, 2 }$.
Finally, we need to calculate the difference between the conditional expectations of the potential outcomes in $\mathcal{S}^{*}$:
equation[equation omitted — 242 chars of source]
Start by noting that
equation[equation omitted — 353 chars of source]
because $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S \in \mathcal{S}^{*}} = \Pr{W = 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S \in \mathcal{S}^{*}} = 1/2$.
This means that we can write
multline[multline omitted — 469 chars of source]
Starting with the expectation for the treated units, note
multline[multline omitted — 517 chars of source]
where $\func{f}{s \mid W = 1, S \in \mathcal{S}^{*}}$ is the conditional density of $S$ given $W = 1$ and $S \in \mathcal{S}^{*}$.
Using Bayes' rule, we can write
equation[equation omitted — 222 chars of source]
As noted above, for $s \geq 1$, we have $\func{f}{s} = 2 - s$.
Furthermore,
equation[equation omitted — 198 chars of source]
whenever $s \geq \paren{3a + 1} / 2$.
Recall that $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} S = s} = s / \paren{2a + 2}$.
When $a \geq 1/3$, so that $\mathcal{S}^{*} = \bracket{ \paren{3a + 1} / 2, 2 }$, then
equation[equation omitted — 82 chars of source]
Hence, the conditional density is
equation[equation omitted — 122 chars of source]
and the condition expectation is
equation[equation omitted — 291 chars of source]
Next consider the conditional expectation for all units in $\mathcal{S}^{*}$.
By a similar argument as above, when $a \geq 1/3$, so that $\mathcal{S}^{*} = \bracket{ \paren{3a + 1} / 2, 2 }$, then
equation[equation omitted — 262 chars of source]
which implies that
equation[equation omitted — 295 chars of source]
Finally, when $1/3 \leq a \leq 1$, note that
equation[equation omitted — 108 chars of source]
Taken together, this gives
equation[equation omitted — 299 chars of source]
Hence, we have $\lim_{n \to \infty} \E{\hat{\tau}_{\normalfont\textsc{att}}} - \tau_{\normalfont\textsc{att}} = 0.1556$ when $a = 1/3$, which is a substantial bias relative to the treatment effect $\tau_{\normalfont\textsc{att}} = 1$.
The asymptotic bias becomes smaller as $a$ grows.
For example, we have $\lim_{n \to \infty} \E{\hat{\tau}_{\normalfont\textsc{att}}} - \tau_{\normalfont\textsc{att}} = 0.0804$ when $a = 4/9$.
When $a = 1$, we have $\Pr{S \in \mathcal{S}^{*}} = 0$, so $\lim_{n \to \infty} \E{\hat{\tau}_{\normalfont\textsc{att}}} - \tau_{\normalfont\textsc{att}} = 0$.
To confirm these theoretical results, I ran a small Monte Carlo study with the current data generating process and the three values of $a$ mentioned in the previous paragraph.
I used sample sizes ranging from one hundred to one million units, and ten thousand simulation rounds were drawn for each setting.
To facilitate the large sample sizes, I used an approximate version of optimal matching.
The error introduced by this approximation algorithm, compared to true optimal matching, is small relative to the bias introduced by the fact that the matching was done without replacement.
The error stemming from the approximation algorithm also converges to zero as the sample grows, unlike the bias from without replacement matching.
Table (ref) reports the results.
The first two columns specify the simulation setting.
The third column “Asymp.\ bias” gives the asymptotic bias as predicted by the theory.
The fourth column “Emp.\ bias” presents the empirical bias in the Monte Carlo simulation.
The empirical bias is considerably larger than the asymptotic bias for smaller sample sizes, but the empirical bias approaches the asymptotic bias as the sample grows.
For samples with one million units, the empirical and asymptotic biases are the same up to the fourth decimal.
The fifth column “Emp.\ SE” presents the empirical standard error of the estimator in the Monte Carlo simulation.
We see that the standard error approaches zero as the sample grows no matter the value of $a$.
Hence, the estimator is convergent in this setting, but it converges to the wrong limit.
table[table omitted — 1,042 chars of source]
Additional remarks
Estimation of average treatment effects
The main paper considered estimation of the average treatment effect of the treated units (ATT).
Practitioners are in some cases interested in the overall average treatment effect (ATE).
However, matching without replacement is generally not used to estimate this effect.
The reason is that to estimate the overall average treatment effect, one would need to match all treated units with control units, and then match all control units with treated units.
But if these matchings are to be constructed without replacement, there must be an equal number of treated units and control units in the sample.
This is rarely the case, and it will then not be possible to construct a matching without replacement.
Even if it is mechanically possible to construct such a matching, the resulting estimator would coincide with the unadjusted difference in average outcomes between the two treatment groups.
Hence, the approach implicitly presumes that the assignment mechanism is unconfounded without adjustment.
The conclusion is that matching without replacement cannot be used to estimate the overall average treatment effect (ATE).
Relation to criticisms of the use of propensity score
Propensity score matching has recently been criticized by King2019Why.
Using an analogy with experimental design, the authors argue that propensity score matching fail to emulate blocked randomized experiments, unlike some other matching methods.
This argument is unrelated to the discussion in the main paper.
Indeed, because the propensity score is the coarsest balancing score, matching on any other balancing score (including the raw covariates) would only aggravate the concerns highlighted here, so the recommendations by King2019Why would not be a solution.
A possible solution would be to match on a score that is coarser than the propensity score, but such a score cannot be a balancing score, so this approach would run the risk of not fully adjust for the confounding, and may fail to achieve consistency for that reason.
Variance estimation
The main paper solely considers point estimation.
However, the investigation suggests a possible approach to variance estimation.
Recall that $p^*$ partitions the sample into two groups based on the propensity scores.
Because the matching behaves vastly differently in these two groups, we can use the partition to estimate the variance.
In particular, asymptotically, all control units with $\Pi \geq p^*$ will be matched, so we can simply estimate the variance for these units, disregarding the matching.
Furthermore, for units with $\Pi < p^*$, the matching will asymptotically behave as if it was with replacement, so variance estimation techniques used for matching with replacement can be used here Abadie2006Large.
Combining the variance estimators in the two parts of the partition would produce a variance estimator for the overall sample.
This may therefore be an alternative to bootstrap estimators, which have been shown to not perform well for matching Abadie2008Failure.
However, it is questionable how useful such a variance estimator would be given the bias exhibited by the point estimator.
This bias may prompt practitioners not to use matching without replacement in the first place, in which case they are in no need of a variance estimator.
Even if they decided to use matching without replacement, the variance estimator would not capture the bias, so confidence intervals and hypothesis tests based on the variance estimator would be dangerously misleading, and should therefore not be used in practice.
Implications for weighting estimators
The matching estimator discussed in the main paper can be reinterpreted as a weighting estimator.
In particular, for a matching $m : \mathcal{T} \to \mathcal{C}$, we can define weights for the control units as
equation[equation omitted — 75 chars of source]
which allows us to write the matching estimator as
equation[equation omitted — 154 chars of source]
Matching without replacement imposes restrictions on these weights.
The first restriction is that $\nu_i \in \braces{0, 1}$, which ensures that each control is matched with at most one treated unit.
The second restriction is that $\sum_i^n \nu_i = N_1$, which ensures that all treated units are matched.
Using this representation of the estimator, it is possible to generalize the insights of this paper to other weighting estimators, such as kernel estimators.
The feature of matching without replacement that introduces bias is that the weights $\nu_i$ are restricted to $\braces{0, 1}$.
This means that we are prevented to upweight units in sparse regions of the covariate space to the degree we would like.
Compare this with matching with replacement, for which the weights are restricted to $\braces{0, 1, \dotsc, N_1}$.
While this also restricts us to integer weights, we are free to put as much weight as we would like on any one unit.
This suggests that similar issues would arise for other weighting estimators if they impose strict upper limits on the weights.
However, commonly used weighting estimators, such as the kernel estimator by \citet*{Heckman1997Matching,Heckman1998Matching}, do not impose such restrictions, so they should not exhibit the type of bias demonstrated in the main paper.
This representation suggests a way to mitigate the bias without necessary fully adopt matching with replacement.
If we relax the restriction on the weights so they can take values in $\braces{0, 1, \dotsc, k}$ for some $k < N_1$, we effectively allow more than one treated unit to be matched to the same control unit, although there cannot be more than $k$ units matched to the same unit.
This will facilitate consistency under weaker conditions than those in the main paper.
For example, if we impose $\nu_i \in \braces{0, 1, 2}$, it will be enough to assume that $\pscore{x} \leq 2/3$ on the support of $X$, rather than $\pscore{x} \leq 1/2$.
Miscellaneous definitions and propositions
definitionLet $\mathbf{\Pi}_{\normalfont\textsc{supp}}$ be the support of $\Pi$.
definitionLet $\Pi^-_{\normalfont\textsc{supp}} = \inf \mathbf{\Pi}_{\normalfont\textsc{supp}}$ and $\Pi^+_{\normalfont\textsc{supp}} = \sup \mathbf{\Pi}_{\normalfont\textsc{supp}}$.
definitionLet $\EPOPS{z}{p} = \E{\POpop{z} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} \Pi = p}$ be the conditional expectation of the potential outcome for treatment $z$ given propensity score $p$.
theoremLet $X_1, X_2, \dotsc, X_n$ be $n$ independent random variables such that $0 \leq X_i \leq 1$ with probability one.
Let $\bar{X} = n^{-1}\sum_{i=1}^{n} X_i$ and $\mu = \E{\bar{X}}$.
For $0 < t < 1 - \mu$ and $0 < s < \mu$:
\begin{equation}
\Pr{\bar{X} - \mu \geq t} \leq \expf{-2nt^2} \qquadand\qquad \Pr{\bar{X} - \mu \leq -s} \leq \expf{-2ns^2}.
\end{equation}
proofThe first inequality is Theorem 1 in Hoeffding1963Probability.
For the second inequality:
\begin{equation}
\Pr{\bar{X} - \mu \leq -s}
=
\Pr{-\bar{X} + \mu \geq s}
=
\Pr[\big]{\paren{1 - \bar{X}} - \paren{1 - \mu} \geq s},
\end{equation}
which is bounded by $\expf{-2ns^2}$ when $0 < s < 1 - \paren{1 - \mu}$ using the first inequality.
theoremUnder Condition \refmain{cond:reg-cond}, $\POpop{0}$ is conditionally independent of $W$ given $\Pi = p$ on the support of $\Pi$.
proofThe statement is Theorem 3 in Rosenbaum1983Central.
Proofs of lemmas
Proof of Lemma \refmain{lem:consistent-unbiased}
reflemma{\refmain{lem:consistent-unbiased}}
If an estimator $\hat{\theta}$ is consistent for a parameter $\theta$, then it is asymptotically unbiased or its variance is asymptotically unbounded:
\begin{equation}
\lim_{\varepsilon \to 0} \lim_{n \to \infty} \Pr[\big]{\abs{\hat{\theta} - \theta} \geq \varepsilon} = 0 \quad \implies \quad
\lim_{n \to \infty} \E{\hat{\theta}} = \theta \quador\quad \limsup_{n \to \infty}\Var{\hat{\theta}} = \infty.
\end{equation}
proofAssume $\hat{\theta}$ is consistent for $\theta$ but that the implication does not hold.
In other words, for some constant $c \geq 1$:
\begin{equation}
\limsup_{n \to \infty} \abs[\big]{\E{\hat{\theta}} - \theta} \geq 1 / c \qquad and \qquad \limsup_{n \to \infty}\Var{\hat{\theta}} \leq c.
\end{equation}
Let $\paren{\varepsilon_n}$ be a sequence in $\mathbb{R}^+$ such that $\varepsilon_n \to 0$ and $\Pr{\abs{\hat{\theta} - \theta} \geq \varepsilon_n} \to 0$.
Consistency ensures that such a sequence exists.
Let $A_n = \indicator[\big]{\abs{\hat{\theta} - \theta} \geq \varepsilon_n}$ be a sequence of random variables and let $\delta_n = \E{A_n} = \Pr{A_n = 1} = \Pr{\abs{\hat{\theta} - \theta} \geq \varepsilon_n}$.
By the law of total variance:
\begin{equation}
\Var{\hat{\theta}} = \E[\big]{\Var{\hat{\theta} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen A_n}} + \Var[\big]{\E{\hat{\theta} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen A_n}} \geq \Var[\big]{\E{\hat{\theta} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen A_n}}.
\end{equation}
Note that $\E[\big]{\E{\hat{\theta} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} A_n}} = \E{\hat{\theta}}$, so:
\begin{equation}
\Var[\big]{\E{\hat{\theta} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen A_n}}
= \E[\Big]{\paren[\big]{\E{\hat{\theta} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen A_n} - \E{\hat{\theta}}}^2}
= \frac{1 - \delta_n}{\delta_n} \paren[\Big]{\E{\hat{\theta}} - \E{\hat{\theta} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen A_n = 0}}^2.
\end{equation}
The last equality may need some elaboration.
Note:
\begin{multline}
\frac{1 - \delta_n}{\delta_n} \paren[\Big]{\E{\hat{\theta}} - \E{\hat{\theta} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen A_n = 0}}^2
=
\frac{\paren{1 - \delta_n} \paren{1 - \delta_n + \delta_n} }{\delta_n} \paren[\Big]{\E{\hat{\theta}} - \E{\hat{\theta} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen A_n = 0}}^2
\\
=
\frac{\paren{1 - \delta_n}^2}{\delta_n} \paren[\Big]{\E{\hat{\theta}} - \E{\hat{\theta} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen A_n = 0}}^2
+
\paren{1 - \delta_n} \paren[\Big]{\E{\hat{\theta}} - \E{\hat{\theta} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen A_n = 0}}^2.
\end{multline}
By the law of total expectation:
\begin{equation}
\E{\hat{\theta}} = \delta_n \E{\hat{\theta} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen A_n = 1} + \paren{1 - \delta_n} \E{\hat{\theta} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen A_n = 0},
\end{equation}
so:
\begin{multline}
\frac{\paren{1 - \delta_n}^2}{\delta_n} \paren[\Big]{\E{\hat{\theta}} - \E{\hat{\theta} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen A_n = 0}}^2
= \frac{\paren{1 - \delta_n}^2}{\delta_n} \paren[\bigg]{\E{\hat{\theta}} - \frac{\E{\hat{\theta}} - \delta_n \E{\hat{\theta} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen A_n = 1}}{1 - \delta_n}}^2
\\
= \frac{\paren{1 - \delta_n}^2}{\delta_n} \paren[\bigg]{\frac{\delta_n \E{\hat{\theta} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen A_n = 1} - \delta_n\E{\hat{\theta}}}{1 - \delta_n}}^2 = \delta_n \paren[\Big]{\E{\hat{\theta} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen A_n = 1} - \E{\hat{\theta}}}^2,
\end{multline}
and the equality follows from the law of total expectation and $\delta_n = \Pr{A_n = 1}$.
Focusing on the second factor, add and subtract $\theta$ to get:
\begin{equation}
\paren[\big]{\E{\hat{\theta}} - \E{\hat{\theta} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen A_n = 0}}^2 \geq \paren[\big]{\E{\hat{\theta}} - \theta}^2 + 2\paren[\big]{\E{\hat{\theta}} - \theta}\paren[\big]{\theta - \E{\hat{\theta} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen A_n = 0}}.
\end{equation}
Let $b_n = \abs{\E{\hat{\theta}} - \theta}$ be the magnitude of the bias.
Recall that $\abs{\hat{\theta} - \theta} < \varepsilon_n$ when $A_n = 0$, so $\abs[\big]{\theta - \E{\hat{\theta} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} A_n = 0}} < \varepsilon_n$.
It follows that:
\begin{equation}
2\paren[\big]{\E{\hat{\theta}} - \theta}\paren[\big]{\theta - \E{\hat{\theta} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen A_n = 0}} \geq - 2 b_n \varepsilon_n,
\end{equation}
and:
\begin{equation}
\paren[\big]{\E{\hat{\theta}} - \theta}^2 + 2\paren[\big]{\E{\hat{\theta}} - \theta}\paren[\big]{\theta - \E{\hat{\theta} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen A_n = 0}} \geq b_n\paren{b_n - 2 \varepsilon_n}.
\end{equation}
Taken together:
\begin{equation}
\Var{\hat{\theta}} \geq \frac{b_n \paren{b_n - 2 \varepsilon_n} \paren{1 - \delta_n}}{\delta_n}.
\end{equation}
Recall that the proof started by assuming:
\begin{equation}
\limsup_{n \to \infty} \abs[\big]{\E{\hat{\theta}} - \theta} \geq 1 / c \qquad and \qquad \limsup_{n \to \infty}\Var{\hat{\theta}} \leq c,
\end{equation}
for some constant $c \geq 1$.
Let $n'$ be such that $\varepsilon_n \leq 1 / 8 c$ and $\delta_n \leq 1 / 32c^3 \leq 1 / 2$ for all $n \geq n'$.
Consistency ensures that such an integer exists.
Asymptotic biasedness implies that $b_n \geq 1 / 2c$ an infinite number of times for $n \geq n'$, and in these cases:
\begin{equation}
\Var{\hat{\theta}}
\geq \frac{b_n \paren{b_n - 2 \varepsilon_n}\paren{1 - \delta_n}}{\delta_n}
\geq \frac{\paren{1 / 2c} \paren{1 / 2c - 2 / 8 c}\paren{1 - 1 / 2}}{1 / 32c^3}
= 2c,
\end{equation}
which contradicts $\limsup_{n \to \infty}\Var{\hat{\theta}} \leq c$.
Proof of Lemma \refmain{lem:bounded-var}
reflemma{\refmain{lem:bounded-var}}
Given Condition \refmain{cond:reg-cond},
\begin{equation}
\limsup_{n \to \infty}\Var{\hat{\tau}_{\normalfontatt}} \leq \frac{4\E{Y^2}}{\bar{\pi}^2} < \infty.
\end{equation}
proofConsider the expectation of the squared estimator:
\begin{equation}
\Var{\hat{\tau}_{\normalfontatt}} = \E{\hat{\tau}_{\normalfontatt}^2} - \paren[\big]{\E{\hat{\tau}_{\normalfontatt}}}^2 \leq \E{\hat{\tau}_{\normalfontatt}^2}.
\end{equation}
As noted in the proof of Lemma (ref), the estimator can be written using $\mathcal{M}^*$ when $1 \leq N_1 \leq N_0$.
Thus, in that case:
\begin{equation}
\hat{\tau}_{\normalfontatt}^2
= \paren[\Bigg]{\frac{1}{N_1} \sum_{i \in \mathcal{T}} Y_{i} - \frac{1}{N_1} \sum_{i \in \mathcal{M}^*} Y_{i}}^2
\leq \frac{1}{N_1^2} \paren[\Bigg]{\sum_{i \in \mathbf{A}} \abs{Y_{i}}}^2,
\end{equation}
where $\mathbf{A} = \mathcal{T} \cup \mathcal{M}^*$.
Recall that $\hat{\tau}_{\normalfont\textsc{att}} = 0$ when $N_1 = 0$ or $N_1 > N_0$, so:
\begin{equation}
\hat{\tau}_{\normalfontatt}^2 \leq \frac{1}{\maxf{1, N_1^2}} \paren[\Bigg]{\sum_{i \in \mathbf{A}} \abs{Y_{i}}}^2,
\end{equation}
holds no matter how many treated units there are in the sample.
Noting that $2ab \leq a^2 + b^2$ for any $a, b \in \mathbb{R}$:
\begin{equation}
\paren[\Bigg]{\sum_{i \in \mathbf{A}} \abs{Y_{i}}}^2 = \frac{1}{2}\sum_{i \in \mathbf{A}}\sum_{j \in \mathbf{A}} 2 \abs{Y_{i}Y_{j}} \leq \frac{1}{2}\sum_{i \in \mathbf{A}}\sum_{j \in \mathbf{A}}\paren{Y_{i}^2 + Y_{j}^2} \leq 2 N_1 \sum_{i \in \mathbf{A}}Y_{i}^2,
\end{equation}
because $\card{\mathbf{A}} = 2N_1$ when $N_1 \leq N_0$ and $\card{\mathbf{A}} < 2N_1$ when $N_1 > N_0$.
Separating the sum again gives:
\begin{equation}
\E{\hat{\tau}_{\normalfont\textsc{att}}^2} \leq \E[\Bigg]{\frac{2}{\maxf{1, N_1}} \sum_{i \in \mathcal{T}}Y_{i}^2} + \E[\Bigg]{\frac{2}{\maxf{1, N_1}} \sum_{i \in \mathcal{M}^*}Y_{i}^2}.
\end{equation}
As noted in the previous proofs, $\mathcal{T}$ contains no more information about $Y_{i}$ than $W_{i}$, so:
\begin{equation}
\E[\Bigg]{\frac{2}{\maxf{1, N_1}} \sum_{i \in \mathcal{T}}Y_{i}^2}
= 2 \E[\Bigg]{\frac{N_1}{\maxf{1, N_1}}} \E{Y^2 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1},
\end{equation}
and:
\begin{equation}
\E[\Bigg]{\frac{2}{\maxf{1, N_1}} \sum_{i \in \mathcal{M}^*}Y_{i}^2}
\leq \E[\Bigg]{\frac{2}{\maxf{1, N_1}} \sum_{i \in \mathcal{C}}Y_{i}^2}
= 2 \E[\Bigg]{\frac{N_0}{\maxf{1, N_1}}} \E{Y^2 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0}.
\end{equation}
Using the same argument as in the proof of Lemma (ref):
\begin{equation}
\E{Y^2 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1} \leq \frac{\E{Y^2}}{\bar{\pi}}
\qquad\text{and}\qquad
\E{Y^2 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0} \leq \frac{\E{Y^2}}{\bar{\pi}},
\end{equation}
so:
\begin{equation}
\E{\hat{\tau}_{\normalfont\textsc{att}}^2}
\leq \E[\Bigg]{\frac{N_1 + N_0}{\maxf{1, N_1}}} \frac{2\E{Y^2}}{\bar{\pi}}
= \E[\Bigg]{\frac{n}{\maxf{1, N_1}}} \frac{2\E{Y^2}}{\bar{\pi}}.
\end{equation}
Finally:
\begin{equation}
\E[\Bigg]{\frac{n}{\maxf{1, N_1}}}
\leq
n \Pr[\big]{N_1 = 0}
+ \Pr[\big]{N_1 > N_0}
+ \E[\Bigg]{\frac{n}{N_1} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0}.
\end{equation}
The first term is $n \paren{1 - \bar{\pi}}^n$ and converges to zero.
The second term was shown to converge to zero in the proof of Lemma (ref).
That proof also showed:
\begin{equation}
\limsup_{n \to \infty} \E[\bigg]{\frac{n}{N_1} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0} \leq \frac{2}{\bar{\pi}} \tag*{\qedhere}.
\end{equation}
Proof of Lemma \refmain{lem:no-crossing-matches}
reflemma{\refmain{lem:no-crossing-matches}}
An optimal propensity score matching contains no crossing matches.
\DeclarePairedDelimiterXPP\malt[1]{m'}{\lparen}{\rparen}{#1}
proofThe lemma is proven by demonstrating the contrapositive.
Consider a matching $m$ containing at least one pair of matches that are crossing according to Definition \refmain{def:crossing-matches}.
That is, for some $k, \ell \in \mathcal{T}$:
\begin{equation}
\maxf{\Pi_{k}, \Pi_{\mgen{\ell}}} < \minf{\Pi_{\ell}, \Pi_{\mgen{k}}}.
\end{equation}
Fix these indices throughout the proof, so $k$ and $\ell$ refer to two specific treated units.
Consider an alternative matching $m'$ that swaps the matched controls for $k$ and $\ell$:
\begin{equation}
\malt{i}
= \begin{cases}
\mgen{k} & if i = \ell,
\\
\mgen{\ell} & if i = k,
\\
\mgen{i} & otherwise.
\end{cases}
\end{equation}
The sum of within-match differences in the propensity scores for the two matchings are:
\begin{equation}
\sum_{i \in \mathcal{T}} \abs{\Pi_{i} - \Pi_{\mgen{i}}}
\qquadand\qquad
\sum_{i \in \mathcal{T}} \abs{\Pi_{i} - \Pi_{\malt{i}}},
\end{equation}
and their difference is:
\begin{equation}
\sum_{i \in \mathcal{T}} \paren[\big]{\abs{\Pi_{i} - \Pi_{\mgen{i}}} - \abs{\Pi_{i} - \Pi_{\malt{i}}}}
= \abs{\Pi_{k} - \Pi_{\mgen{k}}} - \abs{\Pi_{k} - \Pi_{\mgen{\ell}}} + \abs{\Pi_{\ell} - \Pi_{\mgen{\ell}}} - \abs{\Pi_{\ell} - \Pi_{\mgen{k}}},
\end{equation}
because they are identical apart from the matches for $k$ and $\ell$.
It remains to show that this difference is positive.
Because the matches are crossing, $\Pi_{\mgen{k}} > \Pi_{k}$ and $\Pi_{\ell} > \Pi_{\mgen{\ell}}$, so:
\begin{equation}
\abs{\Pi_{k} - \Pi_{\mgen{k}}} = \Pi_{\mgen{k}} - \Pi_{k} \qquad\qquad and \qquad\qquad \abs{\Pi_{\ell} - \Pi_{\mgen{\ell}}} = \Pi_{\ell} - \Pi_{\mgen{\ell}}.
\end{equation}
Define $B_k, B_\ell \in \setb{-1, 1}$ so that $B_k\Pi_{k} \geq B_k\Pi_{\mgen{\ell}}$ and $B_\ell\Pi_{\mgen{k}} \geq B_\ell\Pi_{\ell}$, and write:
\begin{equation}
\abs{\Pi_{k} - \Pi_{\mgen{\ell}}} = B_k\Pi_{k} - B_k\Pi_{\mgen{\ell}} \qquad\qquad and \qquad\qquad \abs{\Pi_{\ell} - \Pi_{\mgen{k}}} = B_\ell\Pi_{\mgen{k}} - B_\ell\Pi_{\ell},
\end{equation}
so the difference can be written as:
\begin{multline}
\abs{\Pi_{k} - \Pi_{\mgen{k}}} - \abs{\Pi_{k} - \Pi_{\mgen{\ell}}} + \abs{\Pi_{\ell} - \Pi_{\mgen{\ell}}} - \abs{\Pi_{\ell} - \Pi_{\mgen{k}}}
\\
=
\paren[\big]{1 + B_\ell} \Pi_{\ell} + \paren[\big]{1 - B_\ell} \Pi_{\mgen{k}} - \paren[\big]{1 + B_k} \Pi_{k} - \paren[\big]{1 - B_k} \Pi_{\mgen{\ell}}.
\end{multline}
Note that $\setb{1 + B_\ell, 1 - B_\ell} = \setb{0, 2}$ because $B_\ell \in \setb{-1, 1}$.
It follows that:
\begin{equation}
\paren[\big]{1 + B_\ell}\Pi_{\ell} + \paren[\big]{1 - B_\ell}\Pi_{\mgen{k}} \geq 2 \minf{\Pi_{\ell}, \Pi_{\mgen{k}}} > 2 \maxf{\Pi_{k}, \Pi_{\mgen{\ell}}},
\end{equation}
where the last inequality follows from $k$ and $\ell$ having crossing matches.
By a similar argument:
\begin{equation}
- \paren[\big]{1 + B_k}\Pi_{k} - \paren[\big]{1 - B_k}\Pi_{\mgen{\ell}} \geq -2 \maxf{\Pi_{k}, \Pi_{\mgen{\ell}}},
\end{equation}
which implies:
\begin{multline}
\paren[\big]{1 + B_\ell} \Pi_{\ell} + \paren[\big]{1 - B_\ell} \Pi_{\mgen{k}} - \paren[\big]{1 + B_k} \Pi_{k} - \paren[\big]{1 - B_k} \Pi_{\mgen{\ell}}
\\
> 2 \maxf{\Pi_{k}, \Pi_{\mgen{\ell}}} - 2 \maxf{\Pi_{k}, \Pi_{\mgen{\ell}}} = 0. \tag*{\qedhere}
\end{multline}
Proof of Proposition \refmain{prop:pscore-bias}
Overview of proof
The proof of Proposition \refmain{prop:pscore-bias} consists of four parts.
The first part is to show that the bias of the estimator is asymptotically equal the expectation of a random variable $D$, which is the normalized difference between the sum of $\PO{i}{0}$ among treated units and the sum of $\PO{i}{0}$ among matched controls (see Definition (ref) in Section (ref)).
This random variable has a non-random denominator, making it easier to analyze than the matching estimator itself.
The asymptotic equivalence is proven in Lemmas (ref), (ref), (ref), (ref), (ref) and (ref).
While necessary to rigorously prove Proposition \refmain{prop:pscore-bias}, the proofs of these lemmas are somewhat tedious and do not bring many interesting insights.
Next, $D$ is decomposed into three terms.
The remaining three parts of the proof consider these three terms in turn.
The proofs of these lemmas are also somewhat tedious, but they provide several insights, and readers may find interesting to study these proof somewhat more carefully.
The first term is the normalized difference between the sums of the potential outcomes of all control units with $\Pi_{i} \geq p^*$ and matched control with $\Pi_{i} \geq p^*$.
Lemmas (ref), (ref), (ref), (ref) and (ref) show that this term converges to zero.
The intuition behind this result is that, asymptotically, all control units with $\Pi_{i} \geq p^*$ will be matched, so the two sums in the difference are over the same units.
The second term is the normalized difference between the sums of the potential outcomes of treated units with $\Pi_{i} < p^*$ and matched control units with $\Pi_{i} < p^*$.
Lemmas (ref), (ref), (ref), (ref), (ref) and (ref) show that this term converges to zero.
The intuition behind this result is that, asymptotically, each treated units with $\Pi_{i} < p^*$ will be matched to a control unit that has a propensity score that is infinitesimally close to the score of the treated unit.
Condition \refmain{cond:pscore-lipschitz} thereby ensures that the average outcome of these matched control units is the same as the average potential outcome under the control condition for the treated units they are matched with.
The third term is the normalized difference between the sums of the potential outcomes of treated units with $\Pi_{i} \geq p^*$ and all control units with $\Pi_{i} \geq p^*$.
Lemma (ref) shows that this term converges to the quantity stipulated in the proposition.
This term does not depend on the matching, so the proof of this lemma is straightforward.
Figure (ref) is a diagram of the relationships between the proposition and its lemmas.
figure[figure omitted — 3,411 chars of source]
Definitions
definitionLet $\mathcal{M}^*$ collect all matched control units when the matching exists and all controls when it does not exist:
\begin{equation}
\mathcal{M}^* =
\begin{cases}
\setb{\mopt{i} :\allowbreak\mathopen i \in \mathcal{T}} & if N_1 \leq N_0,
\\
\mathcal{C} & if N_1 > N_0,
\end{cases}
\end{equation}
definitionLet $D$ be the sum of difference in the potential outcome under control between each treated unit and its matched control unit normalized by the expected number of treated units:
\begin{equation}
D = \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{T}} \PO{i}{0} - \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{M}^*} \PO{i}{0}.
\end{equation}
definitionPartition $\mathcal{U}$, $\mathcal{T}$ and $\mathcal{C}$ as:
\begin{align}
\mathcal{U}_+ &= \setb{i \in \mathcal{U} :\allowbreak\mathopen \Pi_{i} \geq p^*}, \qquad &\mathcal{T}_+ &= \setb{i \in \mathcal{T} :\allowbreak\mathopen \Pi_{i} \geq p^*}, \qquad &\mathcal{C}_+ &= \setb{i \in \mathcal{C} :\allowbreak\mathopen \Pi_{i} \geq p^*},
\\
\mathcal{U}_- &= \setb{i \in \mathcal{U} :\allowbreak\mathopen \Pi_{i} < p^*}, \qquad &\mathcal{T}_- &= \setb{i \in \mathcal{T} :\allowbreak\mathopen \Pi_{i} < p^*}, \qquad &\mathcal{C}_- &= \setb{i \in \mathcal{C} :\allowbreak\mathopen \Pi_{i} < p^*},
\end{align}
and partition $\mathcal{M}^*$ as:
\begin{equation}
\mathcal{M}^*_+ =
\begin{cases}
\setb{\mopt{i} :\allowbreak\mathopen i \in \mathcal{T}_+} & if N_1 \leq N_0,
\\
\mathcal{C}_+ & if N_1 > N_0,
\end{cases}
\qquad\quad
\mathcal{M}^*_- =
\begin{cases}
\setb{\mopt{i} :\allowbreak\mathopen i \in \mathcal{T}_-} & if N_1 \leq N_0,
\\
\mathcal{C}_- & if N_1 > N_0.
\end{cases}
\end{equation}
definitionLet $M^+_{i} = \indicator{i \in \mathcal{M}^*_+}$.
Main proof
refproposition{\refmain{prop:pscore-bias}}
Given Conditions \refmain{cond:reg-cond}, \refmain{cond:pscore-lipschitz} and \refmain{cond:left-closed}, when the matching is constructed without replacement using the true propensity score,
\begin{equation}
\lim_{n \to \infty} \E{\hat{\tau}_{\normalfontatt}} = \tau_{\normalfontatt} + \frac{\Pr{\Pi \geq p^*}}{2\bar{\pi}} \bracket[\Big]{\Es[\big]{\POpop{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1, \Pi \geq p^*} - \Es[\big]{\POpop{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0, \Pi \geq p^*}}.
\end{equation}
proofRecall the definition of $D$:
\begin{equation}
D = \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{T}} \PO{i}{0} - \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{M}^*} \PO{i}{0}.
\end{equation}
Lemma (ref) shows that:
\begin{equation}
\liminf_{n \to \infty} \E{\hat{\tau}_{\normalfontatt}} = \tau_{\normalfontatt} + \liminf_{n \to \infty} \E{D}
\qquadand\qquad
\limsup_{n \to \infty} \E{\hat{\tau}_{\normalfontatt}} = \tau_{\normalfontatt} + \limsup_{n \to \infty} \E{D},
\end{equation}
and the rest of the proof considers $D$.
Use the partitions of $\mathcal{T}$, $\mathcal{C}$ and $\mathcal{M}^*$ in Definition (ref) to write:
\begin{multline}
D = \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{T}_+} \PO{i}{0} + \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{T}_-} \PO{i}{0} - \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{M}^*_+} \PO{i}{0} - \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{M}^*_-} \PO{i}{0}
\\
+ \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{C}_+} \PO{i}{0} - \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{C}_+} \PO{i}{0}.
\end{multline}
After rearranging terms, taking expectations and limits, we get:
\begin{align}
\lim_{n \to \infty} \E{D}
&= \lim_{n \to \infty} \E[\bigg]{\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{C}_+} \PO{i}{0} - \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{M}^*_+} \PO{i}{0}}
\\
&\qquad\quad + \lim_{n \to \infty} \E[\bigg]{\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{T}_-} \PO{i}{0} - \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{M}^*_-} \PO{i}{0}}
\\
&\qquad\quad + \lim_{n \to \infty} \E[\bigg]{\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{T}_+} \PO{i}{0} - \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{C}_+} \PO{i}{0}},
\end{align}
assuming the limit exists.
The first two terms are shown to be zero by Lemmas (ref) and (ref).
Lemma (ref) completes the proof.
Proofs of Lemmas \ref*{lem:mdiscrep-bias}, \ref*{lem:mdiscrep-bias-step1}, \ref*{lem:bounded-POs}, \ref*{lem:mdiscrep-bias-step2}, \ref*{lem:mdiscrep-bias-step3} and \ref*{lem:mdiscrep-bias-step4}
lemmaGiven Condition \refmain{cond:reg-cond}:
\begin{equation}
\liminf_{n \to \infty} \E{D} = \liminf_{n \to \infty} \paren[\big]{\E{\hat{\tau}_{\normalfontatt}} - \tau_{\normalfontatt}}
\qquadand\qquad
\limsup_{n \to \infty} \E{D} = \limsup_{n \to \infty} \paren[\big]{\E{\hat{\tau}_{\normalfontatt}} - \tau_{\normalfontatt}}.
\end{equation}
proofRecall that:
\begin{equation}
D = \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{T}} \PO{i}{0} - \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{M}^*} \PO{i}{0}.
\end{equation}
Let:
\begin{equation}
D^\dagger = \frac{1}{\maxf{1, N_1}} \sum_{i \in \mathcal{T}} \PO{i}{0} - \frac{1}{\maxf{1, N_1}} \sum_{i \in \mathcal{M}^*} \PO{i}{0},
\end{equation}
so that:
\begin{equation}
\E{D} = \E{D^\dagger} + \E{D - D^\dagger}.
\end{equation}
Lemma (ref) shows that $\lim_{n \to \infty} \E{D - D^\dagger} = 0$, which implies:
\begin{equation}
\liminf_{n \to \infty} \E{D} = \liminf_{n \to \infty} \E{D^\dagger}
\qquadand\qquad
\limsup_{n \to \infty} \E{D} = \limsup_{n \to \infty} \E{D^\dagger}.
\end{equation}
Using the law of total expectation, write:
\begin{multline}
\E{D^\dagger}
=
\Pr{N_1 = 0} \E[\big]{D^\dagger \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen N_1 = 0} + \Pr{1 \leq N_1 \leq N_0} \E[\big]{D^\dagger \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0}
\\
+ \Pr{N_1 > N_0} \E[\big]{D^\dagger \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen N_1 > N_0}.
\end{multline}
Note $\E[\big]{D^\dagger \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} N_1 = 0} = 0$ and:
\begin{equation}
\Pr{1 \leq N_1 \leq N_0} = 1 - \Pr{N_1 = 0} - \Pr{N_1 > N_0},
\end{equation}
so:
\begin{multline}
\E{D^\dagger}
=
\E[\big]{D^\dagger \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0}
- \Pr{N_1 = 0} \E[\big]{D^\dagger \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0}
\\
+ \Pr{N_1 > N_0} \paren[\Big]{\E[\big]{D^\dagger \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen N_1 > N_0} - \E[\big]{D^\dagger \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0}}.
\end{multline}
Lemma (ref) therefore implies:
\begin{multline}
\liminf_{n \to \infty} \E{D^\dagger} = \liminf_{n \to \infty} \E[\big]{D^\dagger \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0}
\qquadand\qquad
\\
\limsup_{n \to \infty} \E{D^\dagger} = \limsup_{n \to \infty} \E[\big]{D^\dagger \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0}.
\end{multline}
By a similar argument:
\begin{multline}
\E{\hat{\tau}_{\normalfontatt}}
=
\Pr{N_1 = 0} \E[\big]{\hat{\tau}_{\normalfontatt} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen N_1 = 0} + \Pr{1 \leq N_1 \leq N_0} \E[\big]{\hat{\tau}_{\normalfontatt} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0}
\\
+ \Pr{N_1 > N_0} \E[\big]{\hat{\tau}_{\normalfontatt} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen N_1 > N_0}.
\end{multline}
Recall $\hat{\tau}_{\normalfont\textsc{att}} = 0$ when $N_1 = 0$ or $N_1 > N_0$, so:
\begin{equation}
\E{\hat{\tau}_{\normalfont\textsc{att}}}
=
\E[\big]{\hat{\tau}_{\normalfont\textsc{att}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0}
- \bracket[\big]{\Pr{N_1 = 0} + \Pr{N_1 > N_0}} \E[\big]{\hat{\tau}_{\normalfont\textsc{att}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0}.
\end{equation}
Lemma (ref) then implies:
\begin{multline}
\liminf_{n \to \infty} \E{\hat{\tau}_{\normalfont\textsc{att}}} = \liminf_{n \to \infty} \E[\big]{\hat{\tau}_{\normalfont\textsc{att}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0}
\qquad\text{and}\qquad
\\
\limsup_{n \to \infty} \E{\hat{\tau}_{\normalfont\textsc{att}}} = \limsup_{n \to \infty} \E[\big]{\hat{\tau}_{\normalfont\textsc{att}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0}.
\end{multline}
Lemma (ref) completes the proof by showing:
\begin{equation}
\E[\big]{\hat{\tau}_{\normalfont\textsc{att}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0} - \tau_{\normalfont\textsc{att}} = \E[\big]{D^\dagger \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0}. \tag*{\qedhere}
\end{equation}
lemmaUnder Condition \refmain{cond:reg-cond}:
\begin{equation}
\lim_{n \to \infty} \E[\Bigg]{\paren[\bigg]{\frac{1}{n \bar{\pi}} - \frac{1}{\maxf{1, N_1}}} \paren[\bigg]{\sum_{i \in \mathcal{T}} \PO{i}{0} - \sum_{i \in \mathcal{M}^*} \PO{i}{0}}} = 0.
\end{equation}
proofRearrange the factors as:
\begin{multline}
\paren[\bigg]{\frac{1}{\bar{\pi} n} - \frac{1}{\maxf{1, N_1}}} \paren[\bigg]{\sum_{i \in \mathcal{T}} \PO{i}{0} - \sum_{i \in \mathcal{M}^*} \PO{i}{0}}
\\
= \frac{\maxf{1, N_1} - \bar{\pi} n}{\maxf{1, N_1}} \paren[\bigg]{\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{T}} \PO{i}{0} - \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{M}^*} \PO{i}{0}},
\end{multline}
and then bound the expectation as:
\begin{multline}
\E[\Bigg]{\paren[\bigg]{\frac{\maxf{1, N_1} - \bar{\pi} n}{\maxf{1, N_1}}} \paren[\bigg]{\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{T}} \PO{i}{0} - \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{M}^*} \PO{i}{0}}}
\\
\leq \E[\Bigg]{\frac{\abs{\maxf{1, N_1} - \bar{\pi} n}}{\maxf{1, N_1}} \paren[\bigg]{\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{T}} \abs{\PO{i}{0}} + \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{M}^*} \abs{\PO{i}{0}}}}.
\end{multline}
Note that $\mathcal{M}^* \subseteq \mathcal{C}$, so:
\begin{equation}
\sum_{i \in \mathcal{M}^*} \abs{\PO{i}{0}}
\leq \sum_{i \in \mathcal{C}} \abs{\PO{i}{0}},
\end{equation}
and use the law of iterated expectations to get:
\begin{multline}
\E[\Bigg]{\frac{\abs{\maxf{1, N_1} - \bar{\pi} n}}{\maxf{1, N_1}} \paren[\bigg]{\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{T}} \abs{\PO{i}{0}} + \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{C}} \abs{\PO{i}{0}}}}
\\
=
\E[\Bigg]{\frac{\abs{\maxf{1, N_1} - \bar{\pi} n}}{\maxf{1, N_1}} \E[\bigg]{\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{T}} \abs{\PO{i}{0}} + \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{C}} \abs{\PO{i}{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \mathcal{T}}}.
\end{multline}
The set $\mathcal{T}$ contains no more information about $\PO{i}{0}$ than $W_{i}$, so:
\begin{equation}
\E[\bigg]{\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{T}} \abs{\PO{i}{0}} + \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{C}} \abs{\PO{i}{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \mathcal{T}}
= \frac{N_1}{\bar{\pi} n} \E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1} + \frac{N_0}{\bar{\pi} n} \E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0}.
\end{equation}
The law of total expectation gives:
\begin{equation}
\E[\big]{\abs{\POpop{0}}} = \bar{\pi} \E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1} + \paren{1 - \bar{\pi}}\E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0},
\end{equation}
so:
\begin{equation}
\E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1} \leq \frac{\E[\big]{\abs{\POpop{0}}}}{\bar{\pi}}.
\end{equation}
Lemma (ref) ensures that $\E[\big]{\abs{\POpop{0}}}$ exists.
By a similar argument:
\begin{equation}
\E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0} \leq \frac{\E[\big]{\abs{\POpop{0}}}}{1 - \bar{\pi}} \leq \frac{\E[\big]{\abs{\POpop{0}}}}{\bar{\pi}}.
\end{equation}
Because $N_1 + N_0 = n$:
\begin{equation}
\frac{N_1}{\bar{\pi} n} \E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1} + \frac{N_0}{\bar{\pi} n} \E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0}
\leq
\frac{\E[\big]{\abs{\POpop{0}}}}{\bar{\pi}^2}.
\end{equation}
It follows that:
\begin{multline}
\E[\Bigg]{\frac{\abs{\maxf{1, N_1} - \bar{\pi} n}}{\maxf{1, N_1}} \E[\bigg]{\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{T}} \abs{\PO{i}{0}} + \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{C}} \abs{\PO{i}{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \mathcal{T}}}
\\
\leq
\E[\Bigg]{\frac{\abs{\maxf{1, N_1} - \bar{\pi} n}}{\maxf{1, N_1}}} \frac{\E[\big]{\abs{\POpop{0}}}}{\bar{\pi}^2}.
\end{multline}
Consider the expectation for large samples.
In particular, consider when $\bar{\pi}^2 n / 4 \geq \logf{n} > 1$.
By the law of total expectation:
\begin{align}
&\E[\Bigg]{\frac{\abs{\maxf{1, N_1} - \bar{\pi} n}}{\maxf{1, N_1}}}
\\
&\quad =
\Pr[\Big]{\abs[\big]{N_1 - \bar{\pi} n} < \sqrt{n \logf{n}}} \E[\Bigg]{\frac{\abs{\maxf{1, N_1} - \bar{\pi} n}}{\maxf{1, N_1}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \abs[\big]{N_1 - \bar{\pi} n} < \sqrt{n \logf{n}}}
\\
&\qquad +
\Pr[\Big]{\abs[\big]{N_1 - \bar{\pi} n} \geq \sqrt{n \logf{n}}} \E[\Bigg]{\frac{\abs{\maxf{1, N_1} - \bar{\pi} n}}{\maxf{1, N_1}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \abs[\big]{N_1 - \bar{\pi} n} \geq \sqrt{n \logf{n}}}.
\end{align}
The first probability is crudely bounded as:
\begin{equation}
\Pr[\Big]{\abs[\big]{N_1 - \bar{\pi} n} < \sqrt{n \logf{n}}} \leq 1.
\end{equation}
Recall that $\bar{\pi}^2 n / 4 \geq \logf{n}$, which together with $\abs[\big]{N_1 - \bar{\pi} n} < \sqrt{n \logf{n}}$, implies that $N_1 > \bar{\pi} n / 2$.
Use this to bound the first expectation as:
\begin{equation}
\E[\Bigg]{\frac{\abs{\maxf{1, N_1} - \bar{\pi} n}}{\maxf{1, N_1}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \abs[\big]{N_1 - \bar{\pi} n} \leq \sqrt{n \logf{n}}}
\leq
\frac{2}{\bar{\pi}}\sqrt{\frac{\logf{n}}{n}}.
\end{equation}
Bound the second probability using Hoeffding's inequality (Theorem (ref)):
\begin{equation}
\Pr[\Big]{\abs[\big]{N_1 - \bar{\pi} n} \geq \sqrt{n \logf{n}}} = \Pr[\Big]{\abs[\big]{N_1 / n - \bar{\pi}} \geq \sqrt{\logf{n} / n}} \leq 2 \expf{-2\logf{n}} = \frac{2}{n^2},
\end{equation}
and the second expectation is bounded as:
\begin{equation}
\E[\Bigg]{\frac{\abs{\maxf{1, N_1} - \bar{\pi} n}}{\maxf{1, N_1}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \abs[\big]{N_1 - \bar{\pi} n} \geq \sqrt{n \logf{n}}}
\leq
n.
\end{equation}
Taken together, when $\bar{\pi}^2 n / 4 \geq \logf{n} > 1$:
\begin{equation}
\E[\Bigg]{\frac{\abs{\maxf{1, N_1} - \bar{\pi} n}}{\maxf{1, N_1}}} \leq \frac{2}{\bar{\pi}}\sqrt{\frac{\logf{n}}{n}} + \frac{2}{n} \leq \frac{4}{\bar{\pi}}\sqrt{\frac{\logf{n}}{n}}.
\end{equation}
Returning to the full expression:
\begin{equation}
\E[\Bigg]{\frac{\abs{\maxf{1, N_1} - \bar{\pi} n}}{\maxf{1, N_1}}} \frac{\E[\big]{\abs{\POpop{0}}}}{\bar{\pi}^2}
\leq
\frac{4 \E[\big]{\abs{\POpop{0}}}}{\bar{\pi}^3} \sqrt{\frac{\logf{n}}{n}}. \tag*{\qedhere}
\end{equation}
lemmaUnder Condition \refmain{cond:reg-cond}, $\E[\big]{\abs{\POpop{0}}}$ exists.
proofCondition \refmain{cond:reg-cond} states that $\E{Y^2}$ exists.
Together with Lyapunov's inequality, this implies that $\E[\big]{\abs{Y}}$ exists as well.
By the law of total expectation:
\begin{equation}
\E[\big]{\abs{Y}} = \bar{\pi} \E[\big]{\abs{Y} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1} + \paren{1 - \bar{\pi}}\E[\big]{\abs{Y} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0} \geq \paren{1 - \bar{\pi}} \E[\big]{\abs{Y} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0},
\end{equation}
so $\E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} W = 0} = \E[\big]{\abs{Y} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} W = 0}$ exists.
Using the law of iterated expectations and unconfoundedness with respect to the propensity score (Theorem (ref)):
\begin{equation}
\E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0}
= \E[\Big]{\E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi, W = 0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0}
= \E[\Big]{\E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0},
\end{equation}
Assuming for the moment that $\E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} W = 1}$ exists, then:
\begin{equation}
\E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1}
= \E[\Big]{\E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1}
= \frac{1 - \bar{\pi}}{\bar{\pi}} \E[\bigg]{\frac{\Pi}{1 - \Pi}\E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0},
\end{equation}
because $\Pi / \paren{1 - \Pi}$ is the ratio of treated units to control units at each value of the propensity score in the population, which is what the expectation is marginalizing over.
However, because the control units are more numerous in the population, the $\paren{1 - \bar{\pi}} / \bar{\pi}$ factor is needed for normalization.
Condition \refmain{cond:reg-cond} states that the propensity score is bounded away from one.
Hence, $\Pi \leq \Pi^+_{\normalfont\textsc{supp}} < 1$ with probability one, where $\Pi^+_{\normalfont\textsc{supp}} = \sup \mathbf{\Pi}_{\normalfont\textsc{supp}}$ is the upper bound of the support of $\Pi$.
Thus, with probability one:
\begin{equation}
\frac{\Pi}{1 - \Pi} \leq \frac{1}{1 - \Pi^+_{\normalfontsupp}},
\end{equation}
and:
\begin{multline}
\frac{1 - \bar{\pi}}{\bar{\pi}} \E[\bigg]{\frac{\Pi}{1 - \Pi}\E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0}
\leq
\frac{1}{\bar{\pi} \paren{1 - \Pi^+_{\normalfontsupp}}} \E[\Big]{\E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0}
\\
=
\frac{\E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0}}{\bar{\pi} \paren{1 - \Pi^+_{\normalfontsupp}}},
\end{multline}
where $\bar{\pi} > 0$ according to Condition \refmain{cond:reg-cond}.
The conclusion is that $\E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} W = 1}$ exists.
It follows from the law of total expectation that:
\begin{equation}
\bar{\pi} \E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1} + \paren{1 - \bar{\pi}} \E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0}
= \E[\big]{\abs{\POpop{0}}},
\end{equation}
exists as well.
lemmaUnder Condition \refmain{cond:reg-cond}:
\begin{multline}
\lim_{n \to \infty} \Pr{N_1 = 0} \E[\big]{D^\dagger \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0} = 0
\qquadand
\\
\lim_{n \to \infty} \Pr{N_1 > N_0} \paren[\Big]{\E[\big]{D^\dagger \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen N_1 > N_0} - \E[\big]{D^\dagger \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0}} = 0,
\end{multline}
where $D^\dagger$ is defined in the proof of Lemma (ref).
proofStarting with the probabilities, note that $\Pr{N_1 = 0} = \paren{1 - \bar{\pi}}^n$.
Next:
\begin{equation}
\Pr{N_1 > N_0} = \Pr{N_1 / n > 1 / 2} = \Pr[\big]{N_1 / n - \bar{\pi} > \paren{1 - 2\bar{\pi}} / 2}.
\end{equation}
Note that $\bar{\pi} < 1 / 2$, so by Hoeffding's inequality (Theorem (ref)):
\begin{equation}
\Pr[\big]{N_1 / n - \bar{\pi} > \paren{1 - 2\bar{\pi}} / 2} \leq \expf[\big]{-n\paren{1 - 2\bar{\pi}}^2 / 2}.
\end{equation}
It follows that:
\begin{equation}
\lim_{n \to \infty} \Pr{N_1 = 0} = 0
\qquadand\qquad
\lim_{n \to \infty} \Pr{N_1 > N_0} = 0.
\end{equation}
Now consider the expectations.
Note $\mathcal{M}^* \subseteq \mathcal{C}$, so:
\begin{equation}
\abs[\big]{\E{D^\dagger \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \mathcal{T}}} \leq \E[\bigg]{\frac{1}{N_1} \sum_{i \in \mathcal{T}} \abs{\PO{i}{0}} + \frac{1}{N_1} \sum_{i \in \mathcal{C}} \abs{\PO{i}{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \mathcal{T}},
\end{equation}
when $N_1 \geq 1$.
The set $\mathcal{T}$ contains no more information about $\PO{i}{0}$ than $W_{i}$, so:
\begin{equation}
\E[\bigg]{\frac{1}{N_1} \sum_{i \in \mathcal{T}} \abs{\PO{i}{0}} + \frac{1}{N_1} \sum_{i \in \mathcal{C}} \abs{\PO{i}{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \mathcal{T}}
= \E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1} + \frac{N_0}{N_1}\E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0}.
\end{equation}
As shown in the proof of Lemma (ref):
\begin{equation}
\E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0} \leq \frac{\E[\big]{\abs{\POpop{0}}}}{\bar{\pi}} \qquadand\qquad \E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1} \leq \frac{\E[\big]{\abs{\POpop{0}}}}{\bar{\pi}},
\end{equation}
so:
\begin{equation}
\E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1} + \frac{N_0}{N_1}\E[\big]{\abs{\POpop{0}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0}
\leq
\paren[\bigg]{1 + \frac{N_0}{N_1}} \frac{\E[\big]{\abs{\POpop{0}}}}{\bar{\pi}}.
\end{equation}
One of the expectations is thus bounded as:
\begin{equation}
\abs[\big]{\E{D^\dagger \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen N_1 > N_0}} \leq \E[\bigg]{1 + \frac{N_0}{N_1} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen N_1 > N_0} \frac{\E[\big]{\abs{\POpop{0}}}}{\bar{\pi}} \leq \frac{2 \E[\big]{\abs{\POpop{0}}}}{\bar{\pi}}.
\end{equation}
For the other expectation, write:
\begin{equation}
\abs[\big]{\E{D^\dagger \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0}} \leq \E[\bigg]{\frac{n}{N_1} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0} \frac{\E[\big]{\abs{\POpop{0}}}}{\bar{\pi}}.
\end{equation}
Consider samples large enough to satisfy $\bar{\pi} n \geq 2$, and:
\begin{multline}
\E[\bigg]{\frac{n}{N_1} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0}
= \frac{n \Pr[\big]{1 \leq N_1 \leq \bar{\pi} n / 2}}{\Pr[\big]{1 \leq N_1 \leq N_0}} \E[\bigg]{\frac{1}{N_1} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq \bar{\pi} n / 2}
\\
+ \frac{\Pr[\big]{\bar{\pi} n / 2 < N_1 \leq N_0}}{\Pr[\big]{1 \leq N_1 \leq N_0}} \E[\bigg]{\frac{n}{N_1} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \bar{\pi} n / 2 < N_1 \leq N_0}.
\end{multline}
By Hoeffding's inequality (Theorem (ref)):
\begin{equation}
n \Pr[\big]{1 \leq N_1 \leq \bar{\pi} n / 2} \leq n \Pr[\big]{N_1 \leq \bar{\pi} n / 2} = n \Pr[\big]{N_1 / n - \bar{\pi} \leq -\bar{\pi} / 2} \leq n \expf{-n\bar{\pi}^2 / 2},
\end{equation}
so $\lim_{n \to \infty} n \Pr[\big]{1 \leq N_1 \leq \bar{\pi} n / 2} = 0$.
The start of the proof implies:
\begin{equation}
\lim_{n \to \infty} \Pr[\big]{1 \leq N_1 \leq N_0} = 1,
\end{equation}
because $\Pr[\big]{1 \leq N_1 \leq N_0} = 1 - \Pr{N_1 = 0} - \Pr{N_1 > N_0}$.
Bound the other parts as:
\begin{multline}
\E[\bigg]{\frac{1}{N_1} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq \bar{\pi} n / 2} \leq 1,
\qquad
\Pr[\big]{\bar{\pi} n / 2 < N_1 \leq N_0} \leq 1
\qquadand
\\
\E[\bigg]{\frac{n}{N_1} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \bar{\pi} n / 2 < N_1 \leq N_0} \leq \frac{2}{\bar{\pi}}.
\end{multline}
Hence:
\begin{multline}
\limsup_{n \to \infty} \E[\bigg]{\frac{n}{N_1} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0} \leq \frac{2}{\bar{\pi}}
\qquadand\qquad
\\
\limsup_{n \to \infty} \abs[\big]{\E{D^\dagger \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0}} \leq \frac{2 \E[\big]{\abs{\POpop{0}}}}{\bar{\pi}^2}. \tag*{\qedhere}
\end{multline}
lemmaUnder Condition \refmain{cond:reg-cond}:
\begin{equation}
\lim_{n \to \infty} \bracket[\big]{\Pr{N_1 = 0} + \Pr{N_1 > N_0}} \E[\big]{\hat{\tau}_{\normalfontatt} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0} = 0.
\end{equation}
proofThe proof follows the structure of the proof of Lemma (ref) closely.
It was there shown that:
\begin{equation}
\lim_{n \to \infty} \Pr{N_1 = 0} = 0
\qquadand\qquad
\lim_{n \to \infty} \Pr{N_1 > N_0} = 0.
\end{equation}
It remains to show that the expectation is bounded.
Recall that $\mathcal{M}^* = \setb{\mopt{i} :\allowbreak\mathopen{} i \in \mathcal{T}}$ when $1 \leq N_1 \leq N_0$, so in that case:
\begin{equation}
\hat{\tau}_{\normalfontatt} = \frac{1}{N_1} \sum_{i \in \mathcal{T}} \paren[\big]{Y_{i} - Y_{\mopt{i}}} = \frac{1}{N_1} \sum_{i \in \mathcal{T}} Y_{i} + \frac{1}{N_1} \sum_{i \in \mathcal{M}^*} Y_{i}.
\end{equation}
As above, note $\mathcal{M}^* \subseteq \mathcal{C}$, so when $1 \leq N_1 \leq N_0$:
\begin{equation}
\abs[\big]{\E{\hat{\tau}_{\normalfontatt} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \mathcal{T}}} \leq \E[\bigg]{\frac{1}{N_1} \sum_{i \in \mathcal{T}} \abs{Y_{i}} + \frac{1}{N_1} \sum_{i \in \mathcal{C}} \abs{Y_{i}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \mathcal{T}}.
\end{equation}
The set $\mathcal{T}$ contains no more information about $Y_{i}$ than $W_{i}$, so:
\begin{equation}
\E[\bigg]{\frac{1}{N_1} \sum_{i \in \mathcal{T}} \abs{Y_{i}} + \frac{1}{N_1} \sum_{i \in \mathcal{C}} \abs{Y_{i}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \mathcal{T}}
= \E[\big]{\abs{Y} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1} + \frac{N_0}{N_1}\E[\big]{\abs{Y} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0}.
\end{equation}
and by the same argument as in the previous proofs:
\begin{equation}
\E[\big]{\abs{Y} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1} + \frac{N_0}{N_1}\E[\big]{\abs{Y} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0} \leq
\paren[\bigg]{1 + \frac{N_0}{N_1}} \frac{\E[\big]{\abs{Y}}}{\bar{\pi}},
\end{equation}
where Condition \refmain{cond:reg-cond} ensures that $\E[\big]{\abs{Y}}$ exists.
It follows that:
\begin{equation}
\abs[\big]{\E{\hat{\tau}_{\normalfontatt} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0}} \leq \E[\bigg]{\frac{n}{N_1} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0} \frac{\E[\big]{\abs{Y}}}{\bar{\pi}}.
\end{equation}
The first expectation on the right-hand side was shown to be asymptotically bounded in the proof of Lemma (ref), so:
\begin{equation}
\limsup_{n \to \infty} \abs[\big]{\E{\hat{\tau}_{\normalfontatt} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0}} \leq \frac{2 \E[\big]{\abs{Y}}}{\bar{\pi}^2}. \tag*{\qedhere}
\end{equation}
lemma\begin{equation}
\E[\big]{\hat{\tau}_{\normalfontatt} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0} - \tau_{\normalfontatt} = \E[\bigg]{\frac{1}{N_1} \sum_{i \in \mathcal{T}} \PO{i}{0} - \frac{1}{N_1} \sum_{i \in \mathcal{M}^*} \PO{i}{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0}.
\end{equation}
proofIn was shown in the proof of Lemma (ref) that:
\begin{equation}
\hat{\tau}_{\normalfontatt} = \frac{1}{N_1} \sum_{i \in \mathcal{T}} Y_{i} - \frac{1}{N_1} \sum_{i \in \mathcal{M}^*} Y_{i},
\end{equation}
when $1 \leq N_1 \leq N_0$.
Add and subtract $N_1^{-1}\sum_{i \in \mathcal{T}} \PO{i}{0}$ from the estimator to get:
\begin{multline}
\E[\big]{\hat{\tau}_{\normalfontatt} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0} = \E[\bigg]{\frac{1}{N_1} \sum_{i \in \mathcal{T}} \PO{i}{0} - \frac{1}{N_1} \sum_{i \in \mathcal{M}^*} \PO{i}{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0}
\\
+ \E[\bigg]{\frac{1}{N_1} \sum_{i \in \mathcal{T}} \PO{i}{1} - \frac{1}{N_1} \sum_{i \in \mathcal{T}} \PO{i}{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0}.
\end{multline}
where $Y_{i} = \PO{i}{1}$ for $i \in \mathcal{T}$ and $Y_{i} = \PO{i}{0}$ for $i \in \mathcal{M}^* \subseteq \mathcal{C}$ was used.
As above, $\mathcal{T}$ contains no more information about $\PO{i}{0}$ or $\PO{i}{1}$ than $W_{i}$, so when $N_1 \geq 1$:
\begin{equation}
\E[\bigg]{\frac{1}{N_1} \sum_{i \in \mathcal{T}} \PO{i}{1} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \mathcal{T}} = \E{\POpop{1} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1}
\quadand\quad
\E[\bigg]{\frac{1}{N_1} \sum_{i \in \mathcal{T}} \PO{i}{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \mathcal{T}} = \E{\POpop{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1}.
\end{equation}
It follows that:
\begin{equation}
\E[\bigg]{\frac{1}{N_1} \sum_{i \in \mathcal{T}} \PO{i}{1} - \frac{1}{N_1} \sum_{i \in \mathcal{T}} \PO{i}{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen 1 \leq N_1 \leq N_0} = \E{\POpop{1} - \POpop{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1} = \tau_{\normalfontatt}. \tag*{\qedhere}
\end{equation}
Proofs of Lemmas \ref*{lem:pscore-mdiscrep-term1}, \ref*{lem:pscore-mdiscrep-term1-no-upper-unmatched}, \ref*{lem:pscore-mdiscrep-term1-no-upper-unmatched-middle-part}, \ref*{lem:pscore-mdiscrep-term1-no-upper-unmatched-atom-point} and \ref*{lem:pscore-mdiscrep-term1-upper-balance}
lemmaUnder Conditions \refmain{cond:reg-cond}, \refmain{cond:pscore-lipschitz} and \refmain{cond:left-closed}:
\begin{equation}
\lim_{n \to \infty} \E[\bigg]{\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{C}_+} \PO{i}{0} - \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{M}^*_+} \PO{i}{0}} = 0.
\end{equation}
proofThe matching only depends on $W_{1}, \dotsc, W_{n}$ and $\Pi_{1}, \dotsc, \Pi_{n}$, so $\mathcal{M}^*_+$ is determined by those variables, and:
\begin{multline}
\E[\bigg]{\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{M}^*_+} \PO{i}{0}}
=
\E[\Bigg]{\E[\bigg]{\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{M}^*_+} \PO{i}{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W_{1}, \dotsc, W_{n}, \Pi_{1}, \dotsc, \Pi_{n}}}
\\
= \E[\bigg]{\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{M}^*_+} \E[\big]{\PO{i}{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W_{i}, \Pi_{i}}}
= \E[\bigg]{\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{M}^*_+} \EPOPS{0}{\Pi_{i}}},
\end{multline}
where the last equality follows from unconfoundedness with respect to the propensity score (Theorem (ref)).
By a similar argument:
\begin{equation}
\E[\bigg]{\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{C}_+} \PO{i}{0}}
= \E[\bigg]{\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{C}_+} \EPOPS{0}{\Pi_{i}}}.
\end{equation}
Partition $\mathcal{C}_+$ and $\mathcal{M}^*_+$ as:
\begin{multline}
\mathcal{C}_+ = \paren[\big]{\mathcal{C}_+ \setminus \paren{\mathcal{C}_+ \cap \mathcal{M}^*_+}} \cup \paren{\mathcal{C}_+ \cap \mathcal{M}^*_+}
\qquadand
\\
\mathcal{M}^*_+ = \paren[\big]{\mathcal{M}^*_+ \setminus \paren{\mathcal{C}_+ \cap \mathcal{M}^*_+}} \cup \paren{\mathcal{C}_+ \cap \mathcal{M}^*_+}.
\end{multline}
Observe that the operands in both unions are disjoint, so we can write:
\begin{equation}
\sum_{i \in \mathcal{C}_+} \EPOPS{0}{\Pi_{i}} - \sum_{i \in \mathcal{M}^*_+} \EPOPS{0}{\Pi_{i}}
= \sum_{i \in \mathcal{C}_+ \setminus \paren{\mathcal{C}_+ \cap \mathcal{M}^*_+}} \EPOPS{0}{\Pi_{i}} - \sum_{i \in \mathcal{M}^*_+ \setminus \paren{\mathcal{C}_+ \cap \mathcal{M}^*_+}} \EPOPS{0}{\Pi_{i}},
\end{equation}
because the two terms summing over $\mathcal{C}_+ \cap \mathcal{M}^*_+$ cancel.
It follows that:
\begin{equation}
\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{C}_+} \EPOPS{0}{\Pi_{i}} - \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{M}^*_+} \EPOPS{0}{\Pi_{i}}
\leq \frac{1}{\bar{\pi} n} \sum_{i \in \mathbf{A}} \abs{\EPOPS{0}{\Pi_{i}}},
\end{equation}
where $\mathbf{A} = \paren[\big]{\mathcal{C}_+ \setminus \paren{\mathcal{C}_+ \cap \mathcal{M}^*_+}} \cup \paren[\big]{\mathcal{M}^*_+ \setminus \paren{\mathcal{C}_+ \cap \mathcal{M}^*_+}}$.
Condition \refmain{cond:reg-cond} implies that $\EPOPS{0}{a}$ exists for some $a \in \mathbf{\Pi}_{\normalfont\textsc{supp}}$.
By Condition \refmain{cond:pscore-lipschitz}, $\EPOPS{0}{p}$ is Lipschitz continuous on $\mathbf{\Pi}_{\normalfont\textsc{supp}}$.
Together with $\mathbf{\Pi}_{\normalfont\textsc{supp}} \subset \bracket{0, 1}$, this implies that $\EPOPS{0}{p}$ is bounded on $\mathbf{\Pi}_{\normalfont\textsc{supp}}$.
Let $c_\mu \in \mathbb{R}$ be this bound.
That is, $\abs{\EPOPS{0}{p}} \leq c_\mu$ for all $p \in \mathbf{\Pi}_{\normalfont\textsc{supp}}$.
It follows that:
\begin{equation}
\E[\bigg]{\frac{1}{\bar{\pi} n} \sum_{i \in \mathbf{A}} \abs{\EPOPS{0}{\Pi_{i}}}}
\leq
\frac{c_\mu}{\bar{\pi}} \E[\bigg]{\frac{\card{\mathbf{A}}}{n}}.
\end{equation}
Because the union operands in $\mathbf{A}$ are disjoint:
\begin{equation}
\card{\mathbf{A}} = \card[\big]{\mathcal{C}_+ \setminus \paren{\mathcal{C}_+ \cap \mathcal{M}^*_+}} + \card[\big]{\mathcal{M}^*_+ \setminus \paren{\mathcal{C}_+ \cap \mathcal{M}^*_+}},
\end{equation}
and because $\paren{\mathcal{C}_+ \cap \mathcal{M}^*_+} \subset \mathcal{C}_+$ and $\paren{\mathcal{C}_+ \cap \mathcal{M}^*_+} \subset \mathcal{M}^*_+$:
\begin{align}
\card{\mathbf{A}}
&= \card{\mathcal{C}_+} - \card{\mathcal{C}_+ \cap \mathcal{M}^*_+} + \card{\mathcal{M}^*_+} - \card{\mathcal{C}_+ \cap \mathcal{M}^*_+}
\\
&= 2\paren[\big]{\card{\mathcal{C}_+} - \card{\mathcal{C}_+ \cap \mathcal{M}^*_+}} + \paren[\big]{\card{\mathcal{M}^*_+} - \card{\mathcal{C}_+}}
\\
&= 2\card{\mathcal{C}_+ \setminus \mathcal{M}^*_+} + \paren[\big]{\card{\mathcal{M}^*_+} - \card{\mathcal{C}_+}},
\end{align}
where the last equality follows from:
\begin{equation}
\card{\mathcal{C}_+ \setminus \mathcal{M}^*_+} = \card{\mathcal{C}_+ \setminus \paren{\mathcal{C}_+ \cap \mathcal{M}^*_+}} = \card{\mathcal{C}_+} - \card{\mathcal{C}_+ \cap \mathcal{M}^*_+}.
\end{equation}
The proof is completed by:
\begin{equation}
\frac{c_\mu}{\bar{\pi}} \E[\bigg]{\frac{\card{\mathbf{A}}}{n}}
=
\frac{2c_\mu}{\bar{\pi}} \E[\bigg]{\frac{\card{\mathcal{C}_+ \setminus \mathcal{M}^*_+}}{n}}
+
\frac{c_\mu}{\bar{\pi}} \E[\bigg]{\frac{\card{\mathcal{M}^*_+} - \card{\mathcal{C}_+}}{n}},
\end{equation}
and Lemmas (ref) and (ref).
lemmaUnder Conditions \refmain{cond:reg-cond}, \refmain{cond:pscore-lipschitz} and \refmain{cond:left-closed}:
\begin{equation}
\lim_{n \to \infty} \E[\bigg]{\frac{\card{\mathcal{C}_+ \setminus \mathcal{M}^*_+}}{n}} = 0.
\end{equation}
\DeclarePairedDelimiterXPP\IntervalPSpoint[1]{K_n}{\lparen}{\rparen}{#1}
proofUnits in $\mathcal{C}_+ \setminus \mathcal{M}^*_+$ are control units with $\Pi_{i} \geq p^*$ not in $\mathcal{M}^*_+$, so:
\begin{multline}
\E[\bigg]{\frac{\card{\mathcal{C}_+ \setminus \mathcal{M}^*_+}}{n}}
= \E[\bigg]{\frac{1}{n}\sum_{i=1}^{n} \indicator[\big]{M^+_{i} = 0, W_{i} = 0, \Pi_{i} \geq p^*}}
\\
= \frac{1}{n}\sum_{i=1}^{n} \Pr[\big]{M^+_{i} = 0, W_{i} = 0, \Pi_{i} \geq p^*},
\end{multline}
where $M^+_{i} = \indicator{i \in \mathcal{M}^*_+}$.
The summation on the right-hand side of the equation cannot be removed at this point because the matching may not be symmetric with respect to the unit indices.
For example, if tie breaking is done by picking units with lower indices as matches, then $\Pr{M^+_{1} = 0, W_{1} = 0, \Pi_{1} \geq p^*}$ may be less than $\Pr{M^+_{n} = 0, W_{n} = 0, \Pi_{n} \geq p^*}$.
Furthermore, the probability cannot be written with respect to the population distribution because $M^+_{i}$ is only defined in the sample.
The proof is completed immediately if $\Pr{\Pi \geq p^*} = 0$ because $\mathcal{C}_+$ is empty with probability one in that case.
Next consider when $p^* = \Pi^+_{\normalfont\textsc{supp}}$.
This means:
\begin{equation}
\frac{1}{n}\sum_{i=1}^{n} \Pr[\big]{M^+_{i} = 0, W_{i} = 0, \Pi_{i} \geq p^*}
=
\frac{1}{n}\sum_{i=1}^{n} \Pr[\big]{M^+_{i} = 0, W_{i} = 0, \Pi_{i} = p^*},
\end{equation}
and Lemma (ref) immediately completes the proof because $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} \Pi \geq p^*} = 1 / 2$ when $p^* = \Pi^+_{\normalfont\textsc{supp}}$.
The rest of the proof considers the case when $\Pr{\Pi \geq p^*} > 0$ and $p^* < \Pi^+_{\normalfont\textsc{supp}}$.
It cannot be that $\Pi^+_{\normalfont\textsc{supp}} < 1 / 2$ here because $\setb{p :\allowbreak\mathopen{} \Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} \Pi \geq p} \geq 1 / 2}$ would then be empty and $p^* = 1 / 2$, which contradicts $p^* < \Pi^+_{\normalfont\textsc{supp}}$.
Similarly, $\Pi^+_{\normalfont\textsc{supp}} = 1 / 2$ implies $p^* = 1 / 2$.
It must thus be $\Pi^+_{\normalfont\textsc{supp}} > 1 / 2$, and then $p^* < 1 / 2$, so this is the case to be considered.
Let $\paren{\varepsilon^+_n}$ be a sequence in $\mathbb{R}^+$ such that $\varepsilon^+_n \to 0$ at a sufficiently slow rate so to satisfy:
\begin{equation}
\Pr{\Pi \geq \Pi^+_{\normalfontsupp} - \varepsilon^+_n} \geq \sqrt{\logf{n} / n},
\end{equation}
for sufficiently large $n$.
Similarly, let $\paren{\varepsilon^-_n}$ be a sequence in $\mathbb{R}^+$ such that $\varepsilon^-_n \to 0$ and:
\begin{equation}
\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi \geq p^* + \varepsilon^-_n} \geq 1 / 2 + \sqrt{\logf{n} / n},
\end{equation}
for sufficiently large $n$.
Finally, let:
\begin{equation}
\IntervalPSpoint{p}
=
\begin{cases}
0 & if p < p^*,
\\
1 & if p = p^*,
\\
2 & if p^* < p < p^* + \varepsilon^-_n,
\\
3 & if p^* + \varepsilon^-_n \leq p \leq \Pi^+_{\normalfontsupp} - \varepsilon^+_n,
\\
4 & \text{if } \Pi^+_{\normalfont\textsc{supp}} - \varepsilon^+_n < p < \Pi^+_{\normalfont\textsc{supp}},
\\
5 & \text{if } p = \Pi^+_{\normalfont\textsc{supp}}.
\end{cases}
\end{equation}
In other words, $\IntervalPSpoint{p}$ partitions the support of $\Pi$ into six groups based on the quantities defined above.
Write the quantity under consideration as:
\begin{align}
\frac{1}{n}\sum_{i=1}^{n} \Pr[\big]{M^+_{i} = 0, W_{i} = 0, \Pi_{i} \geq p^*}
&= \frac{1}{n}\sum_{i=1}^{n} \Pr[\big]{M^+_{i} = 0, W_{i} = 0, \IntervalPSpoint{\Pi_{i}} = 3}
\\
&\qquad + \frac{1}{n}\sum_{i=1}^{n} \Pr[\big]{M^+_{i} = 0, W_{i} = 0, \IntervalPSpoint{\Pi_{i}} \in \setb{1, 5}}
\\
&\qquad + \frac{1}{n}\sum_{i=1}^{n} \Pr[\big]{M^+_{i} = 0, W_{i} = 0, \IntervalPSpoint{\Pi_{i}} \in \setb{2, 4}}.
\end{align}
Lemmas (ref) demonstrates that the first term converges to zero, and Lemma (ref) does the same for the second term.
This is because Condition \refmain{cond:left-closed} implies $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} \Pi \geq p^*} = 1 / 2$, and $\Pi^+_{\normalfont\textsc{supp}} > 1 / 2$ implies $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} \Pi \geq \Pi^+_{\normalfont\textsc{supp}}} > 1 / 2$, so the premise of Lemma (ref) holds for the second term.
For the third term, write:
\begin{equation}
\Pr[\big]{M^+_{i} = 0, W_{i} = 0, \IntervalPSpoint{\Pi_{i}} \in \setb{2, 4}}
\leq \Pr[\big]{\IntervalPSpoint{\Pi} \in \setb{2, 4}},
\end{equation}
so:
\begin{multline}
\frac{1}{n}\sum_{i=1}^{n} \Pr[\big]{M^+_{i} = 0, W_{i} = 0, \IntervalPSpoint{\Pi_{i}} \in \setb{2, 4}}
\\
\leq \Pr[\big]{p^* < \Pi < p^* + \varepsilon^-_n} + \Pr[\big]{\Pi^+_{\normalfont\textsc{supp}} - \varepsilon^+_n < \Pi < \Pi^+_{\normalfont\textsc{supp}}},
\end{multline}
and $\varepsilon^-_n \to 0$ and $\varepsilon^+_n \to 0$ ensure that also this term converges to zero.
lemmaGiven $p^* < 1 / 2 < \Pi^+_{\normalfont\textsc{supp}}$ and Conditions \refmain{cond:reg-cond}, \refmain{cond:pscore-lipschitz} and \refmain{cond:left-closed}:
\begin{equation}
\lim_{n \to \infty} \frac{1}{n}\sum_{i=1}^{n} \Pr[\big]{M^+_{i} = 0, W_{i} = 0, \IntervalPSpoint{\Pi_{i}} = 3} = 0,
\end{equation}
where $\IntervalPSpoint{p}$ is defined in the proof of Lemma (ref).
\DeclarePairedDelimiterXPP\PSBalCount[2]{B_{#1}}{\lparen}{\rparen}{#2}
\DeclarePairedDelimiterXPP\AvgPSBalCount[1]{\bar{H}}{\lparen}{\rparen}{#1}
\DeclarePairedDelimiterXPP\UnitAvgPSBalCount[2]{H_{#1}}{\lparen}{\rparen}{#2}
\DeclarePairedDelimiterXPP\ExpoPS[1]{S}{\lparen}{\rparen}{#1}
proofNote that:
\begin{equation}
\Pr[\big]{M^+_{i} = 0, W_{i} = 0, \IntervalPSpoint{\Pi_{i}} = 3}
\leq \Pr[\big]{M^+_{i} = 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W_{i} = 0, \IntervalPSpoint{\Pi_{i}} = 3},
\end{equation}
and write:
\begin{equation}
\Pr[\big]{M^+_{i} = 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W_{i} = 0, \IntervalPSpoint{\Pi_{i}} = 3}
= \E[\Big]{\Pr[\big]{M^+_{i} = 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W_{i} = 0, \Pi_{i}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W_{i} = 0, \IntervalPSpoint{\Pi_{i}} = 3}.
\end{equation}
Let $\PSBalCount{i}{p} = \sum_{j \neq i} \paren{2W_{j} - 1} \indicator{\Pi_{j} \geq p}$ count the balance of treated and control units with propensity scores greater than or equal to $p$ excluding unit $i$.
For example, if there are $25$ treated units and $19$ control units with $\Pi_{j} \geq p$ for $j \neq i$, then $\PSBalCount{i}{p} = 25 - 19 = 6$.
Use the law of total probability to write:
\begin{align}
&\Pr[\big]{M^+_{i} = 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W_{i} = 0, \Pi_{i} = p}
\\
&\qquad \qquad =
\Pr[\big]{\PSBalCount{i}{p} \geq 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W_{i} = 0, \Pi_{i} = p} \Pr[\big]{M^+_{i} = 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W_{i} = 0, \Pi_{i} = p, \PSBalCount{i}{p} \geq 1}
\\
&\qquad \qquad \qquad +
\Pr[\big]{\PSBalCount{i}{p} \leq 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W_{i} = 0, \Pi_{i} = p} \Pr[\big]{M^+_{i} = 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W_{i} = 0, \Pi_{i} = p, \PSBalCount{i}{p} \leq 0}.
\end{align}
Bound two of the factors as:
\begin{equation}
\Pr[\big]{\PSBalCount{i}{p} \geq 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W_{i} = 0, \Pi_{i} = p} \leq 1
\quadand\quad
\Pr[\big]{M^+_{i} = 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W_{i} = 0, \Pi_{i} = p, \PSBalCount{i}{p} \leq 0} \leq 1,
\end{equation}
to get:
\begin{multline}
\Pr[\big]{M^+_{i} = 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W_{i} = 0, \Pi_{i} = p}
\leq \Pr[\big]{M^+_{i} = 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W_{i} = 0, \Pi_{i} = p, \PSBalCount{i}{p} \geq 1}
\\
+ \Pr[\big]{\PSBalCount{i}{p} \leq 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W_{i} = 0, \Pi_{i} = p}.
\end{multline}
Now for the key step of the proof, namely showing that:
\begin{equation}
\Pr[\big]{M^+_{i} = 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W_{i} = 0, \Pi_{i} = p, \PSBalCount{i}{p} \geq 1} = 0,
\end{equation}
for all $i \in \mathcal{U}$.
There are five scenarios to consider:
\begin{enumerate}[label=(\alph*)]
• $N_1 = 0$,
• $N_1 > N_0$,
• $1 \leq N_1 \leq N_0$ and $i \not\in \mathcal{M}^*$,
• $1 \leq N_1 \leq N_0$ and $i \in \mathcal{M}^*_-$,
• $1 \leq N_1 \leq N_0$ and $i \in \mathcal{M}^*_+$.
\end{enumerate}
The first scenario can be ignored because $\PSBalCount{i}{p} \geq 1$ implies that at least one treated unit exists in the sample.
In the second scenario, $\mathcal{M}^*_+ = \mathcal{C}_+$.
This implies $M^+_{i} = 1$ because $\mathcal{C}_+ = \setb{i \in \mathcal{C} :\allowbreak\mathopen{} \Pi_{i} \geq p^*}$ and we are only considering control units with $\Pi_{i} \geq p^*$.
In the third scenario, $M^+_{i} = 0$, but such a matching cannot be optimal.
In particular, $\PSBalCount{i}{p} \geq 1$ means that there is at least one treated unit $k$ with $\Pi_{k} \geq p$ that is matched with a control unit $j$ with $\Pi_{j} < p$.
Because unit $i$ is unmatched, we could match unit $k$ with $i$ without otherwise changing the matching, and the sum of within-match propensity score differences would then change by:
\begin{equation}
\paren{\Pi_{k} - \Pi_{i}} - \paren{\Pi_{k} - \Pi_{j}} = \Pi_{j} - \Pi_{i} < 0,
\end{equation}
because $\Pi_{j} < p$ and $\Pi_{i} = p$.
Hence, the matching in the third scenario cannot be optimal.
The fourth scenario follows a similar argument.
Also in this scenario, $M^+_{i} = 0$, but again such a matching cannot be optimal.
As before, $\PSBalCount{i}{p} \geq 1$ means that there is at least one treated unit $k$ with $\Pi_{k} \geq p$ that is matched with a control unit $j$ with $\Pi_{j} < p$.
Because $i \in \mathcal{M}^*_-$, there exists a treated unit $\ell$ with $\Pi_{\ell} < p$ that is matched with $i$.
Taken together:
\begin{equation}
\maxf{\Pi_{\ell}, \Pi_{\mopt{k}}} < p \leq \minf{\Pi_{k}, \Pi_{\mopt{\ell}}},
\end{equation}
which means that $m^*$ contains crossing matches, but Lemma \refmain{lem:no-crossing-matches} tells us that no such matching is optimal.
The conclusion is that the only possible scenarios are the second and fifth, and then $M^+_{i} = 1$.
It follows that:
\begin{equation}
\Pr[\big]{M^+_{i} = 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W_{i} = 0, \Pi_{i} = p, \PSBalCount{i}{p} \geq 1} = 0,
\end{equation}
as desired, which gives:
\begin{equation}
\Pr[\big]{M^+_{i} = 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W_{i} = 0, \Pi_{i} = p}
\leq \Pr[\big]{\PSBalCount{i}{p} \leq 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W_{i} = 0, \Pi_{i} = p}.
\end{equation}
Note that $\PSBalCount{i}{p}$ does not depend on $W_{i} = 0$ or $\Pi_{i} = p$ other than through the value $p$ because unit $i$ is excluded from the count in $\PSBalCount{i}{p}$.
It follows that:
\begin{equation}
\Pr[\big]{\PSBalCount{i}{p} \leq 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W_{i} = 0, \Pi_{i} = p} = \Pr[\big]{\PSBalCount{i}{p} \leq 0}.
\end{equation}
Note that $\Pr[\big]{\PSBalCount{i}{p} \leq 0} = \Pr[\big]{\PSBalCount{j}{p} \leq 0}$ for all $i, j \in \mathcal{U}$ and $p \in \mathbf{\Pi}_{\normalfont\textsc{supp}}$ because the probability does not depend on the matching and the observations are otherwise identically distributed.
The rest of the proof uses $\Pr[\big]{\PSBalCount{i}{p} \leq 0}$ for $i = 1$ to represent all units in $\mathcal{U}$.
Consider a normalized version of $\PSBalCount{1}{p}$:
\begin{equation}
\AvgPSBalCount{p} = \frac{1}{n - 1} \sum_{i = 2}^n \UnitAvgPSBalCount{i}{p},
\qquadwhere\qquad
\UnitAvgPSBalCount{i}{p} =
\begin{cases}
W_{i} & if \Pi_{i} \geq p,
\\
1 / 2 & if \Pi_{i} < p.
\end{cases}
\end{equation}
In particular:
\begin{equation}
\AvgPSBalCount{p} = \frac{1}{2} + \frac{\PSBalCount{1}{p}}{2\paren{n - 1}}.
\end{equation}
Consider its expectation:
\begin{equation}
\E[\big]{\AvgPSBalCount{p}} = \frac{1}{2} + \frac{\Pr{W = 1, \Pi \geq p} - \Pr{W = 0, \Pi \geq p}}{2}.
\end{equation}
Define $\ExpoPS{p} = \Pr{\Pi \geq p} \bracket[\big]{\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} \Pi \geq p} - 1 / 2}$, so:
\begin{align}
&\Pr{W = 1, \Pi \geq p} - \Pr{W = 0, \Pi \geq p}
\\
&\qquad \qquad = \Pr{\Pi \geq p} \bracket[\big]{\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi \geq p} - \Pr{W = 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi \geq p}}
\\
&\qquad \qquad = \Pr{\Pi \geq p} \bracket[\big]{2\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi \geq p} - 1}
\\
&\qquad \qquad = 2 \ExpoPS{p},
\end{align}
and $\E[\big]{\AvgPSBalCount{p}} = 1 / 2 + \ExpoPS{p}$.
It follows that:
\begin{equation}
\Pr[\big]{\PSBalCount{1}{p} \leq 0} = \Pr[\big]{\AvgPSBalCount{p} \leq 1 / 2} = \Pr[\Big]{\AvgPSBalCount{p} - \E[\big]{\AvgPSBalCount{p}} \leq - \ExpoPS{p}}.
\end{equation}
Apply Hoeffding's inequality (Theorem (ref)) to get:
\begin{multline}
\Pr[\Big]{\AvgPSBalCount{p} - \E[\big]{\AvgPSBalCount{p}} \leq - \ExpoPS{p}}
\leq \expf[\big]{- \paren{n - 1} \bracket{\ExpoPS{p}}^2}
\\
= \expf[\big]{\bracket{\ExpoPS{p}}^2} \expf[\big]{- n \bracket{\ExpoPS{p}}^2}
\leq 2 \expf[\big]{- n \bracket{\ExpoPS{p}}^2},
\end{multline}
where the last inequality follows from $\exp\paren[\big]{\bracket{\ExpoPS{p}}^2} \leq \exp\paren{1 / 4} \leq 2$.
Recapitulating what we have shown so far, for all $i \in \mathcal{U}$:
\begin{multline}
\E[\Big]{\Pr[\big]{M^+_{i} = 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W_{i} = 0, \Pi_{i}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W_{i} = 0, \IntervalPSpoint{\Pi_{i}} = 3}
\\
\leq
2 \E[\Big]{\expf[\big]{- n \bracket{\ExpoPS{\Pi}}^2} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0, \IntervalPSpoint{\Pi} = 3}.
\end{multline}
Recall that $p^* < 1 / 2 < \Pi^+_{\normalfont\textsc{supp}}$, which means:
\begin{equation}
\Pr{\Pi \geq 1 / 2} > 0
\qquadand\qquad
\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi \geq 1 / 2} > 1 / 2.
\end{equation}
Also recall that $\IntervalPSpoint{p} = 3$ means $p^* + \varepsilon^-_n \leq p \leq \Pi^+_{\normalfont\textsc{supp}} - \varepsilon^+_n$.
The rest of the proof considers sufficiently large $n$ so that $p^* + \varepsilon^-_n < 1 / 2 < \Pi^+_{\normalfont\textsc{supp}} - \varepsilon^+_n$.
Such samples exist because $\varepsilon^-_n \to 0$ and $\varepsilon^+_n \to 0$.
Consider the events $p^* + \varepsilon^-_n \leq \Pi \leq 1 / 2$ and $1 / 2 < \Pi \leq \Pi^+_{\normalfont\textsc{supp}} - \varepsilon^+_n$.
The function $\ExpoPS{p} = \Pr{\Pi \geq p} \bracket[\big]{\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} \Pi \geq p} - 1 / 2}$ is key here.
Note that $\Pr{\Pi \geq p}$ is non-negative and decreasing in $p$, and $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} \Pi \geq p}$ is non-negative and increasing in $p$.
Thus, for any $p$ such that $p^* + \varepsilon^-_n \leq p \leq 1 / 2$:
\begin{equation}
\ExpoPS{p} \geq \Pr{\Pi \geq 1 / 2} \bracket[\big]{\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi \geq p^* + \varepsilon^-_n} - 1 / 2}.
\end{equation}
Furthermore, $\varepsilon^-_n$ was defined so that:
\begin{equation}
\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi \geq p^* + \varepsilon^-_n} \geq 1 / 2 + \sqrt{\logf{n} / n},
\end{equation}
for sufficiently large $n$, and then:
\begin{equation}
\ExpoPS{p} \geq \Pr{\Pi \geq 1 / 2} \sqrt{\logf{n} / n}.
\end{equation}
Similarly, by the definition of $\varepsilon^+_n$, for any $p$ such that $1 / 2 < p \leq \Pi^+_{\normalfont\textsc{supp}} - \varepsilon^+_n$:
\begin{multline}
\ExpoPS{p}
\geq \Pr{\Pi \geq \Pi^+_{\normalfontsupp} - \varepsilon^+_n} \bracket[\big]{\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi \geq 1 / 2} - 1 / 2}
\\
\geq \sqrt{\logf{n} / n} \bracket[\big]{\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi \geq 1 / 2} - 1 / 2},
\end{multline}
for sufficiently large $n$.
Let $C = \bracket[\Big]{\minf[\big]{\Pr{\Pi \geq 1 / 2}, \Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} \Pi \geq 1 / 2} - 1 / 2}}^2$, so:
\begin{equation}
\ExpoPS{p} \geq \sqrt{C \logf{n} / n},
\end{equation}
for all $p$ such that $\IntervalPSpoint{p} = 3$ when $n$ is sufficiently large.
It follows that:
\begin{equation}
2 \E[\Big]{\expf[\big]{- n \bracket{\ExpoPS{\Pi}}^2} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0, \IntervalPSpoint{\Pi} = 3}
\leq
2 \expf[\big]{- C \logf{n}}
=
\frac{2}{n^C}.
\end{equation}
As noted above, $p^* < 1 / 2 < \Pi^+_{\normalfont\textsc{supp}}$ implies that $C > 0$.
lemmaGiven $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} \Pi \geq p} \geq 1 / 2$:
\begin{equation}
\lim_{n \to \infty} \frac{1}{n}\sum_{i=1}^{n} \Pr[\big]{M^+_{i} = 0, W_{i} = 0, \Pi_{i} = p} = 0.
\end{equation}
\DeclarePairedDelimiterXPP\PSBalCountAtom[1]{B}{\lparen}{\rparen}{#1}
\DeclarePairedDelimiterXPP\CountAtom[1]{C}{\lparen}{\rparen}{#1}
proofThe proof is completed immediately if $\Pr{\Pi = p} = 0$ because:
\begin{equation}
\Pr[\big]{M^+_{i} = 0, W_{i} = 0, \Pi_{i} = p} \leq \Pr{\Pi = p}.
\end{equation}
The rest of the proof considers the case when $\Pr{\Pi = p} > 0$.
Let $\PSBalCountAtom{p} = \sum_{i=1}^{n} \paren{2W_{i} - 1} \indicator{\Pi_{i} \geq p}$ and let $\CountAtom{p} = \sum_{i=1}^{n} \indicator{W_{i} = 0, \Pi_{i} = p}$.
By the same argument as in the proof of Lemma (ref), if $\PSBalCountAtom{p} \geq 0$, then $M^+_{i} = 1$ must be true for all control units with $\Pi_{i} = p$.
If $\PSBalCountAtom{p} < 0$, then some of these units may not be matched.
However, all treated units with $\Pi_{i} \geq p$ will be matched with control units with $\Pi_{i} \geq p$ if possible.
This means that at most:
\begin{equation}
-\PSBalCountAtom{p} = \CountAtom{p} - \sum_{i=1}^{n} \indicator{W_{i} = 1, \Pi_{i} = p} - \sum_{i=1}^{n} \paren{2W_{i} - 1} \indicator{\Pi_{i} > p},
\end{equation}
control units with $\Pi_{i} = p$ are unmatched, and:
\begin{equation}
\sum_{i=1}^{n} \indicator[\big]{M^+_{i} = 0, W_{i} = 0, \Pi_{i} = p} \leq \maxf[\big]{0, \minf[\big]{\CountAtom{p}, - \PSBalCountAtom{p}}}.
\end{equation}
Write:
\begin{align}
\frac{1}{n}\sum_{i=1}^{n} \Pr[\big]{M^+_{i} = 0, W_{i} = 0, \Pi_{i} = p}
&= \E[\bigg]{\frac{1}{n}\sum_{i=1}^{n} \indicator[\big]{M^+_{i} = 0, W_{i} = 0, \Pi_{i} = p}}
\\
&\leq \E[\Big]{\maxf[\big]{0, \minf[\big]{\CountAtom{p}, - \PSBalCountAtom{p}}} / n}
\\
&\leq \E[\Big]{\maxf[\big]{0, - \PSBalCountAtom{p}} / n},
\end{align}
and:
\begin{align}
&\E[\Big]{\maxf[\big]{0, - \PSBalCountAtom{p}} / n}
\\
&\qquad\qquad = \Pr[\Big]{\PSBalCountAtom{p} \leq -\sqrt{n \logf{n}}} \E[\Big]{\maxf[\big]{0, - \PSBalCountAtom{p}} / n \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \PSBalCountAtom{p} \leq -\sqrt{n \logf{n}}}
\\
&\qquad\qquad\qquad + \Pr[\Big]{\PSBalCountAtom{p} > -\sqrt{n \logf{n}}} \E[\Big]{\maxf[\big]{0, - \PSBalCountAtom{p}} / n \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \PSBalCountAtom{p} > -\sqrt{n \logf{n}}}.
\end{align}
Bound two of the factors as:
\begin{equation}
\E[\Big]{\maxf[\big]{0, - \PSBalCountAtom{p}} / n \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \PSBalCountAtom{p} \leq -\sqrt{n \logf{n}}} \leq 1
\qquadand\qquad
\Pr[\Big]{\PSBalCountAtom{p} > -\sqrt{n \logf{n}}} \leq 1,
\end{equation}
so:
\begin{multline}
\E[\Big]{\maxf[\big]{0, - \PSBalCountAtom{p}} / n}
\leq \Pr[\Big]{\PSBalCountAtom{p} \leq -\sqrt{n \logf{n}}}
\\
+ \E[\Big]{\maxf[\big]{0, - \PSBalCountAtom{p}} / n \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \PSBalCountAtom{p} > -\sqrt{n \logf{n}}}.
\end{multline}
Consider the first term:
\begin{align}
\Pr[\Big]{\PSBalCountAtom{p} \leq -\sqrt{n \logf{n}}}
&= \Pr[\Big]{\PSBalCountAtom{p} / n \leq -\sqrt{\logf{n} / n}}
\\
&= \Pr[\Big]{\PSBalCountAtom{p} / n - \E{\PSBalCountAtom{p} / n} \leq - \E{\PSBalCountAtom{p} / n} - \sqrt{\logf{n} / n}}
\\
&\leq \Pr[\Big]{\PSBalCountAtom{p} / n - \E{\PSBalCountAtom{p} / n} \leq - \sqrt{\logf{n} / n}},
\end{align}
where the last inequality follows from:
\begin{align}
\E{\PSBalCountAtom{p} / n}
&= \Pr{W = 1, \Pi \geq p} - \Pr{W = 0, \Pi \geq p}
\\
&= \Pr{\Pi \geq p} \bracket[\big]{\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi \geq p} - \Pr{W = 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi \geq p}}
\\
&= 2 \Pr{\Pi \geq p} \bracket[\big]{\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi \geq p} - 1 / 2}
\\
&\geq 0,
\end{align}
which in turn holds because $\Pr{\Pi \geq p} > 0$ and $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} \Pi \geq p} \geq 1 / 2$.
Apply Hoeffding's inequality (Theorem (ref)) to get:
\begin{equation}
\Pr[\Big]{\PSBalCountAtom{p} / n - \E{\PSBalCountAtom{p} / n} \leq - \sqrt{\logf{n} / n}}
\leq \expf[\big]{-2\logf{n}}
= \frac{1}{n^2}.
\end{equation}
Complete the proof by noting:
\begin{equation}
\E[\Big]{\maxf[\big]{0, - \PSBalCountAtom{p}} / n \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \PSBalCountAtom{p} > -\sqrt{n \logf{n}}}
\leq
\sqrt{\frac{\logf{n}}{n}}. \tag*{\qedhere}
\end{equation}
lemmaUnder Conditions \refmain{cond:reg-cond} and \refmain{cond:left-closed}:
\begin{equation}
\lim_{n \to \infty} \E[\bigg]{\frac{\card{\mathcal{M}^*_+} - \card{\mathcal{C}_+}}{n}} = 0.
\end{equation}
proofWrite:
\begin{equation}
\E[\bigg]{\frac{\card{\mathcal{M}^*_+} - \card{\mathcal{C}_+}}{n}}
=
\E[\bigg]{\frac{\card{\mathcal{M}^*_+} - \card{\mathcal{T}_+}}{n}} + \E[\bigg]{\frac{\card{\mathcal{T}_+} - \card{\mathcal{C}_+}}{n}}.
\end{equation}
Consider the absolute value of the first expectation:
\begin{equation}
\abs[\bigg]{\E[\bigg]{\frac{\card{\mathcal{M}^*_+} - \card{\mathcal{T}_+}}{n}}}
= \Pr[\big]{N_1 > N_0} \abs[\bigg]{\E[\bigg]{\frac{\card{\mathcal{M}^*_+} - \card{\mathcal{T}_+}}{n} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen N_1 > N_0}}
\leq \Pr[\big]{N_1 > N_0},
\end{equation}
because $\card{\mathcal{M}^*_+} = \card{\setb{\mopt{i} :\allowbreak\mathopen{} i \in \mathcal{T}_+}} = \card{\mathcal{T}_+}$ when $N_1 \leq N_0$.
As noted in the proof of Lemma (ref):
\begin{equation}
\lim_{n \to \infty} \Pr[\big]{N_1 > N_0} = 0,
\end{equation}
given Condition \refmain{cond:reg-cond}.
Next:
\begin{equation}
\E[\bigg]{\frac{\card{\mathcal{T}_+} - \card{\mathcal{C}_+}}{n}}
=
\Pr{W = 1, \Pi \geq p^*} - \Pr{W = 0, \Pi \geq p^*},
\end{equation}
because $\mathcal{T}_+ = \setb{i \in \mathcal{T} :\allowbreak\mathopen{} \Pi_{i} \geq p^*}$ and $\mathcal{C}_+ = \setb{i \in \mathcal{C} :\allowbreak\mathopen{} \Pi_{i} \geq p^*}$.
Condition \refmain{cond:left-closed} implies that $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} \Pi \geq p^*} = 1 / 2$, so:
\begin{align}
&\Pr{W = 1, \Pi \geq p^*} - \Pr{W = 0, \Pi \geq p^*}
\\
&\qquad\qquad = \Pr{\Pi \geq p^*} \bracket[\big]{\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi \geq p^*} - \Pr{W = 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi \geq p^*}}
\\
&\qquad\qquad = 2\Pr{\Pi \geq p^*} \bracket[\big]{\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi \geq p^*} - 1 / 2}
\\
&\qquad\qquad = 0,
\end{align}
because $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} \Pi \geq p^*} + \Pr{W = 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} \Pi \geq p^*} = 1$.
Proofs of Lemmas \ref*{lem:pscore-mdiscrep-term2} and \ref*{lem:pscore-mdiscrep-term2-bin-overflow}
lemmaUnder Conditions \refmain{cond:reg-cond}, \refmain{cond:pscore-lipschitz} and \refmain{cond:left-closed}:
\begin{equation}
\lim_{n \to \infty} \E[\bigg]{\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{T}_-} \PO{i}{0} - \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{M}^*_-} \PO{i}{0}} = 0.
\end{equation}
\DeclarePairedDelimiterXPP\emopt[1]{m^*_e}{\lparen}{\rparen}{#1}
\DeclarePairedDelimiterXPP\mrest[1]{m_r}{\lparen}{\rparen}{#1}
proofBy the same argument as in the proof of Lemma (ref), namely that the matching only depends on $W_{1}, W_{2}, \dotsc, W_{n}$ and $\Pi_{1}, \Pi_{2}, \dotsc, \Pi_{n}$ and unconfoundedness with respect to the propensity score (Theorem (ref)):
\begin{equation}
\E[\bigg]{\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{T}_-} \PO{i}{0} - \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{M}^*_-} \PO{i}{0}}
= \E[\Bigg]{\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{T}_-} \EPOPS{0}{\Pi_{i}} - \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{M}^*_-} \EPOPS{0}{\Pi_{i}}}
\end{equation}
The unit index will now be extended beyond $\mathcal{U}$.
For any $i > n$, set $\Pi_{i} = -1$.
Also extend $\EPOPS{0}{p}$ so that $\EPOPS{0}{-1} = 0$.
Define:
\begin{equation}
\mathcal{T}_e
=
\begin{cases}
\mathcal{T}_- & if N_1 \leq N_0
\\
\mathcal{T}_- \cup \setb{n + i :\allowbreak\mathopen 1 \leq i \leq \card{\mathcal{C}_-} - \card{\mathcal{T}_-}} & if N_1 > N_0
\end{cases}
\end{equation}
so $\card{\mathcal{T}_e} = \card{\mathcal{M}^*_-}$ no matter whether $N_1 \leq N_0$ or $N_1 > N_0$, because:
\begin{equation}
\mathcal{M}^*_- =
\begin{cases}
\setb{\mopt{i} :\allowbreak\mathopen i \in \mathcal{T}_-} & if N_1 \leq N_0,
\\
\mathcal{C}_- & if N_1 > N_0.
\end{cases}
\end{equation}
Because we defined $\EPOPS{0}{-1} = 0$, we can write:
\begin{equation}
\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{T}_-} \EPOPS{0}{\Pi_{i}} - \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{M}^*_-} \EPOPS{0}{\Pi_{i}}
=
\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{T}_e} \EPOPS{0}{\Pi_{i}} - \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{M}^*_-} \EPOPS{0}{\Pi_{i}}
\end{equation}
Let $\mathcal{M}_e$ be all injective functions from $\mathcal{T}_e$ to $\mathcal{C} \setminus \mathcal{M}^*_+$.
Select a $m^*_e \in \mathcal{M}_e$ satisfying:
\begin{equation}
m^*_e \in \operatorname*{arg\,min}_{m \in \mathcal{M}_e} \sum_{i \in \mathcal{T}_e} \abs{\Pi_{i} - \Pi_{\mgen{i}}}.
\end{equation}
If $N_1 \leq N_0$, then select $m^*_e = m^*$, so $\emopt{i} = \mopt{i}$ for all $i \in \mathcal{T}_e = \mathcal{T}_-$.
This is possible because $\mathcal{M}^*_- \subseteq \mathcal{C} \setminus \mathcal{M}^*_+$.
If $N_1 > N_0$, then $\mathcal{M}^*_- = \mathcal{C}_- = \mathcal{C} \setminus \mathcal{M}^*_+$.
This means that $m^*_e$ is a bijection from $\mathcal{T}_e$ to $\mathcal{M}^*_-$ no matter whether $N_1 \leq N_0$ or $N_1 > N_0$, and:
\begin{multline}
\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{T}_e} \EPOPS{0}{\Pi_{i}} - \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{M}^*_-} \EPOPS{0}{\Pi_{i}}
=
\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{T}_e} \paren[\big]{\EPOPS{0}{\Pi_{i}} - \EPOPS{0}{\Pi_{\emopt{i}}}}
\\
\leq
\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{T}_e} \abs[\big]{\EPOPS{0}{\Pi_{i}} - \EPOPS{0}{\Pi_{\emopt{i}}}}
\end{multline}
Condition \refmain{cond:pscore-lipschitz} stipulates that $\EPOPS{0}{p}$ is Lipschitz continuous on the support of $\Pi$.
The task now is to extend Lipschitz continuity to also include the point $p = -1$.
Condition \refmain{cond:reg-cond} implies that $\EPOPS{0}{a}$ exists for some $a \in \mathbf{\Pi}_{\normalfont\textsc{supp}}$.
By the triangle inequality, for any $p \in \mathbf{\Pi}_{\normalfont\textsc{supp}}$:
\begin{equation}
\abs[\big]{\EPOPS{0}{-1} - \EPOPS{0}{p}} \leq \abs[\big]{\EPOPS{0}{-1} - \EPOPS{0}{a}} + \abs[\big]{\EPOPS{0}{a} - \EPOPS{0}{p}}
\end{equation}
Recall $\EPOPS{0}{-1} = 0$, and $a$ was picked so $\EPOPS{0}{a}$ existed, so $\abs[\big]{\EPOPS{0}{-1} - \EPOPS{0}{a}}$ exists.
Furthermore:
\begin{equation}
\abs[\big]{\EPOPS{0}{a} - \EPOPS{0}{p}} \leq c,
\end{equation}
for all $p \in \mathbf{\Pi}_{\normalfont\textsc{supp}}$ because of Lipschitz continuity on $\mathbf{\Pi}_{\normalfont\textsc{supp}} \subseteq \bracket{0, 1}$ and $a \in \mathbf{\Pi}_{\normalfont\textsc{supp}}$.
The constant $c$ is the Lipschitz constant.
It follows that $\EPOPS{0}{p}$ is Lipschitz continuous on $\mathbf{\Pi}_{\normalfont\textsc{supp}} \cup \setb{-1}$ with Lipschitz constant $c_\mu = c + \abs[\big]{\EPOPS{0}{a}}$.
By virtue of being Lipschitz continuous:
\begin{equation}
\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{T}_e} \abs[\big]{\EPOPS{0}{\Pi_{i}} - \EPOPS{0}{\Pi_{\emopt{i}}}}
\leq
\frac{c_\mu}{\bar{\pi} n} \sum_{i \in \mathcal{T}_e} \abs[\big]{\Pi_{i} - \Pi_{\emopt{i}}}
\end{equation}
Now for the key step of the proof.
Consider a weakly growing sequence $\paren{b_n}$ in $\mathbb{N}$ such that $b_n \geq 1$ and $b_n \to \infty$.
The growth rate is, however, sufficiently slow so that:
\begin{equation}
\lim_{n \to \infty} b_n \logf{n} / n = 0.
\end{equation}
Let $w_n = \paren{p^* - \Pi^-_{\normalfont\textsc{supp}}} / b_n$.
For $k \in \setb{1, \dotsc, b_n}$, let:
\begin{align}
\mathcal{U}_{k,n} &= \setb{i \in \mathcal{U}_- :\allowbreak\mathopen \Pi^-_{\normalfontsupp} + \paren{k - 1} w_n \leq \Pi_{i} < \Pi^-_{\normalfontsupp} + k w_n}
\\
\mathcal{T}_{k,n} &= \setb{i \in \mathcal{T}_- :\allowbreak\mathopen \Pi^-_{\normalfont\textsc{supp}} + \paren{k - 1} w_n \leq \Pi_{i} < \Pi^-_{\normalfont\textsc{supp}} + k w_n}
\\
\mathcal{C}_{k,n} &= \setb{i \in \mathcal{C}_- :\allowbreak\mathopen \Pi^-_{\normalfont\textsc{supp}} + \paren{k - 1} w_n \leq \Pi_{i} < \Pi^-_{\normalfont\textsc{supp}} + k w_n}
\end{align}
Recall that $\mathcal{M}_e$ contains all injective functions from $\mathcal{T}_e$ to $\mathcal{C} \setminus \mathcal{M}^*_+$.
Consider a matching $m_r \in \mathcal{M}_e$ such that $\setb{\mrest{i} :\allowbreak\mathopen{} i \in \mathcal{T}_{k,n}} \subseteq \mathcal{C}_{k,n} \setminus \mathcal{M}^*_+$ if $\card{\mathcal{T}_{k,n}} \leq \card{\mathcal{C}_{k,n} \setminus \mathcal{M}^*_+}$, and $\mathcal{C}_{k,n} \setminus \mathcal{M}^*_+ \subseteq \setb{\mrest{i} :\allowbreak\mathopen{} i \in \mathcal{T}_{k,n}}$ if $\card{\mathcal{T}_{k,n}} > \card{\mathcal{C}_{k,n} \setminus \mathcal{M}^*_+}$.
In other words, $m_r$ is such that units in $\mathcal{T}_{k,n}$ are first matched with control units in $\mathcal{C}_{k,n}$ not matched to a treated unit in $\mathcal{T}_+$ in $m^*$, and if there are not sufficient many such units, the remaining units in $\mathcal{T}_{k,n}$ are matched arbitrarily.
Because $m^*_e$ is an optimum in $\mathcal{M}_e$ and $m_r \in \mathcal{M}_e$:
\begin{equation}
\frac{c_\mu}{\bar{\pi} n} \sum_{i \in \mathcal{T}_e} \abs[\big]{\Pi_{i} - \Pi_{\emopt{i}}}
\leq
\frac{c_\mu}{\bar{\pi} n} \sum_{i \in \mathcal{T}_e} \abs[\big]{\Pi_{i} - \Pi_{\mrest{i}}}
\end{equation}
Let $\mathcal{T}_{0,n} = \setb{i \in \mathcal{T}_e :\allowbreak\mathopen{} \Pi_{i} = -1}$, and for completeness, let $\mathcal{U}_{0,n} = \mathcal{T}_{0,n}$ and $\mathcal{C}_{0,n} = \emptyset$.
This means that $\mathcal{T}_{0,n}, \mathcal{T}_{1,n}, \dotsc, \mathcal{T}_{b_n,n}$ partition $\mathcal{T}_e$, so:
\begin{equation}
\frac{c_\mu}{\bar{\pi} n} \sum_{i \in \mathcal{T}_e} \abs[\big]{\Pi_{i} - \Pi_{\mrest{i}}}
=
\frac{c_\mu}{\bar{\pi} n} \sum_{i \in \mathcal{T}_{0,n}} \abs[\big]{\Pi_{i} - \Pi_{\mrest{i}}}
+
\frac{c_\mu}{\bar{\pi} n} \sum_{k = 1}^{b_n} \sum_{i \in \mathcal{T}_{k,n}} \abs[\big]{\Pi_{i} - \Pi_{\mrest{i}}}
\end{equation}
Note $\abs{\Pi_{i} - \Pi_{\mrest{i}}} \leq 2$ for $i \in \mathcal{T}_{0,n} = \setb{i \in \mathcal{T}_e :\allowbreak\mathopen{} \Pi_{i} = -1}$, so:
\begin{equation}
\frac{c_\mu}{\bar{\pi} n} \sum_{i \in \mathcal{T}_{0,n}} \abs[\big]{\Pi_{i} - \Pi_{\mrest{i}}}
\leq
\frac{2 c_\mu \card{\mathcal{T}_{0,n}}}{\bar{\pi} n}
\end{equation}
By a similar argument, $\abs{\Pi_{i} - \Pi_{\mrest{i}}} \leq 1$ for $i \in \mathcal{T}_{k,n}$ and $k \geq 1$.
However, we sometimes have a sharper bound.
If $\card{\mathcal{T}_{k,n}} \leq \card{\mathcal{C}_{k,n} \setminus \mathcal{M}^*_+}$, then $\setb{\mrest{i} :\allowbreak\mathopen{} i \in \mathcal{T}_{k,n}} \subseteq \mathcal{C}_{k,n} \setminus \mathcal{M}^*_+$, so all matches are inside the bin, and $\abs{\Pi_{i} - \Pi_{\mrest{i}}} \leq w_n$ for $i \in \mathcal{T}_{k,n}$.
If instead $\card{\mathcal{T}_{k,n}} > \card{\mathcal{C}_{k,n} \setminus \mathcal{M}^*_+}$, then $\abs{\Pi_{i} - \Pi_{\mrest{i}}} \leq w_n$ holds only for a subset of $\mathcal{T}_{k,n}$ of size $\card{\mathcal{C}_{k,n} \setminus \mathcal{M}^*_+}$.
Taken together, this means that $\abs{\Pi_{i} - \Pi_{\mrest{i}}} \leq w_n$ is true for $\minf[\big]{\card{\mathcal{T}_{k,n}}, \card{\mathcal{C}_{k,n} \setminus \mathcal{M}^*_+}}$ units in $\mathcal{T}_{k,n}$, and $\abs{\Pi_{i} - \Pi_{\mrest{i}}} \leq 1$ for the remaining units.
It follows that, for any $1 \leq k \leq b_n$:
\begin{equation}
\sum_{i \in \mathcal{T}_{k,n}} \abs[\big]{\Pi_{i} - \Pi_{\mrest{i}}}
\leq
w_n \minf[\big]{\card{\mathcal{T}_{k,n}}, \card{\mathcal{C}_{k,n} \setminus \mathcal{M}^*_+}}
+
\paren[\Big]{\card{\mathcal{T}_{k,n}} - \minf[\big]{\card{\mathcal{T}_{k,n}}, \card{\mathcal{C}_{k,n} \setminus \mathcal{M}^*_+}}}
\end{equation}
In the first term, bound the minimum as:
\begin{equation}
\minf[\big]{\card{\mathcal{T}_{k,n}}, \card{\mathcal{C}_{k,n} \setminus \mathcal{M}^*_+}} \leq \card{\mathcal{T}_{k,n}}.
\end{equation}
For the second term:
\begin{equation}
\card{\mathcal{T}_{k,n}} - \minf[\big]{\card{\mathcal{T}_{k,n}}, \card{\mathcal{C}_{k,n} \setminus \mathcal{M}^*_+}}
=
\maxf[\big]{0, \card{\mathcal{T}_{k,n}} - \card{\mathcal{C}_{k,n} \setminus \mathcal{M}^*_+}}
\end{equation}
Note that $\mathcal{C}_{k,n} \setminus \mathcal{M}^*_+ = \mathcal{C}_{k,n} \setminus \paren{\mathcal{C}_{k,n} \cap \mathcal{M}^*_+}$, so $\card{\mathcal{C}_{k,n} \setminus \mathcal{M}^*_+} = \card{\mathcal{C}_{k,n}} - \card{\mathcal{C}_{k,n} \cap \mathcal{M}^*_+}$.
Write:
\begin{multline}
\maxf[\big]{0, \card{\mathcal{T}_{k,n}} - \card{\mathcal{C}_{k,n} \setminus \mathcal{M}^*_+}}
=
\maxf[\big]{0, \card{\mathcal{T}_{k,n}} - \card{\mathcal{C}_{k,n}} + \card{\mathcal{C}_{k,n} \cap \mathcal{M}^*_+}}
\\
\leq
\maxf[\big]{0, \card{\mathcal{T}_{k,n}} - \card{\mathcal{C}_{k,n}}} + \card{\mathcal{C}_{k,n} \cap \mathcal{M}^*_+}
\end{multline}
so that:
\begin{multline}
\frac{c_\mu}{\bar{\pi} n} \sum_{k = 1}^{b_n} \sum_{i \in \mathcal{T}_{k,n}} \abs[\big]{\Pi_{i} - \Pi_{\mrest{i}}}
\leq
\frac{c_\mu}{\bar{\pi} n} \sum_{k = 1}^{b_n} w_n \card{\mathcal{T}_{k,n}}
+
\frac{c_\mu}{\bar{\pi} n} \sum_{k = 1}^{b_n} \maxf[\big]{0, \card{\mathcal{T}_{k,n}} - \card{\mathcal{C}_{k,n}}}
\\
+
\frac{c_\mu}{\bar{\pi} n} \sum_{k = 1}^{b_n} \card{\mathcal{C}_{k,n} \cap \mathcal{M}^*_+}
\end{multline}
The sets $\mathcal{T}_{1,n}, \mathcal{T}_{2,n}, \dotsc, \mathcal{T}_{b_n,n}$ partition $\mathcal{T}_-$, so:
\begin{equation}
\sum_{k = 1}^{b_n} w_n \card{\mathcal{T}_{k,n}} = w_n \card{\mathcal{T}_-}
\end{equation}
Similarly, $\mathcal{C}_{1,n}, \mathcal{C}_{2,n}, \dotsc, \mathcal{C}_{b_n,n}$ partition $\mathcal{C}_-$, and:
\begin{multline}
\mathcal{C}_- \cap \mathcal{M}^*_+
=
\paren{\mathcal{C}_{1,n} \cup \mathcal{C}_{2,n} \cup \dotsb \cup \mathcal{C}_{b_n,n}} \cap \mathcal{M}^*_+
\\
=
\paren{\mathcal{C}_{1,n} \cap \mathcal{M}^*_+} \cup \paren{\mathcal{C}_{2,n} \cap \mathcal{M}^*_+} \cup \dotsb \cup \paren{\mathcal{C}_{b_n,n} \cap \mathcal{M}^*_+}
\end{multline}
so:
\begin{equation}
\sum_{k = 1}^{b_n} \card{\mathcal{C}_{k,n} \cap \mathcal{M}^*_+}
= \card{\mathcal{C}_- \cap \mathcal{M}^*_+}
\end{equation}
To continue, note that $\mathcal{C}_+$ and $\mathcal{C}_-$ partition $\mathcal{C}$, so:
\begin{equation}
\card{\mathcal{C}_+ \cap \mathcal{M}^*_+} + \card{\mathcal{C}_- \cap \mathcal{M}^*_+} = \card{\mathcal{C} \cap \mathcal{M}^*_+} = \card{\mathcal{M}^*_+}
\end{equation}
where the last equality follows from $\mathcal{M}^*_+ \subset \mathcal{C}$.
This implies:
\begin{multline}
\card{\mathcal{C}_- \cap \mathcal{M}^*_+}
= \card{\mathcal{M}^*_+} - \card{\mathcal{C}_+ \cap \mathcal{M}^*_+}
= \paren[\big]{\card{\mathcal{M}^*_+} - \card{\mathcal{C}_+}} + \paren[\big]{\card{\mathcal{C}_+} - \card{\mathcal{C}_+ \cap \mathcal{M}^*_+}}
\\
= \paren[\big]{\card{\mathcal{M}^*_+} - \card{\mathcal{C}_+}} + \card{\mathcal{C}_+ \setminus \mathcal{M}^*_+}
\end{multline}
where the last equality follows from:
\begin{equation}
\card{\mathcal{C}_+ \setminus \mathcal{M}^*_+} = \card{\mathcal{C}_+ \setminus \paren{\mathcal{C}_+ \cap \mathcal{M}^*_+}} = \card{\mathcal{C}_+} - \card{\mathcal{C}_+ \cap \mathcal{M}^*_+}
\end{equation}
Recapitulating what we have shown so far:
\begin{equation}
\E[\bigg]{\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{T}_-} \PO{i}{0} - \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{M}^*_-} \PO{i}{0}}
\leq
\E[\bigg]{\frac{c_\mu}{\bar{\pi} n} \sum_{i \in \mathcal{T}_e} \abs[\big]{\Pi_{i} - \Pi_{\mrest{i}}}}
\end{equation}
and:
\begin{multline}
\E[\bigg]{\frac{c_\mu}{\bar{\pi} n} \sum_{i \in \mathcal{T}_e} \abs[\big]{\Pi_{i} - \Pi_{\mrest{i}}}}
\leq
\frac{2 c_\mu}{\bar{\pi}} \E[\bigg]{\frac{\card{\mathcal{T}_{0,n}}}{n}}
+
\frac{c_\mu w_n}{\bar{\pi}} \E[\bigg]{\frac{\card{\mathcal{T}_-}}{n}}
+
\frac{c_\mu}{\bar{\pi}} \E[\bigg]{\frac{\card{\mathcal{C}_+ \setminus \mathcal{M}^*_+}}{n}}
\\
+
\frac{c_\mu}{\bar{\pi}} \E[\bigg]{\frac{\card{\mathcal{M}^*_+} - \card{\mathcal{C}_+}}{n}}
+
\frac{c_\mu}{\bar{\pi}} \E[\bigg]{\frac{1}{n}\sum_{k = 1}^{b_n} \maxf[\big]{0, \card{\mathcal{T}_{k,n}} - \card{\mathcal{C}_{k,n}}}}
\end{multline}
For the first term, recall that $\mathcal{T}_{0,n} = \emptyset$ when $N_1 \leq N_0$, and $\card{\mathcal{T}_{0,n}} \leq n$ otherwise.
It follows:
\begin{equation}
\E[\bigg]{\frac{\card{\mathcal{T}_{0,n}}}{n}} \leq \Pr[\big]{N_1 > N_0},
\end{equation}
which was shown to converge to zero given Condition \refmain{cond:reg-cond} in the proof of Lemma (ref).
For the second term, note that $\card{\mathcal{T}_-} \leq n$, so:
\begin{equation}
\frac{c_\mu w_n}{\bar{\pi}} \E[\bigg]{\frac{\card{\mathcal{T}_-}}{n}} \leq \frac{c_\mu w_n}{\bar{\pi}},
\end{equation}
which converges to zero because $b_n \to \infty$ implies that $w_n \to 0$.
Lemmas (ref) and (ref) demonstrate that the third and fourth terms converge to zero.
Lemma (ref) completes the proof.
lemmaUnder Conditions \refmain{cond:reg-cond}, \refmain{cond:pscore-lipschitz} and \refmain{cond:left-closed}:
\begin{equation}
\lim_{n \to \infty} \E[\bigg]{\frac{1}{n}\sum_{k = 1}^{b_n} \maxf[\big]{0, \card{\mathcal{T}_{k,n}} - \card{\mathcal{C}_{k,n}}}} = 0.
\end{equation}
where $b_n$, $\mathcal{T}_{k,n}$ and $\mathcal{C}_{k,n}$ are defined in the proof of Lemma (ref).
\DeclarePairedDelimiterXPP\ExpCountBink[1]{\bar{T}_{k,n}}{\lparen}{\rparen}{#1}
proofRecall $\mathcal{U}_{k,n} = \mathcal{T}_{k,n} \cup \mathcal{C}_{k,n}$, so:
\begin{equation}
\maxf[\big]{0, \card{\mathcal{T}_{k,n}} - \card{\mathcal{C}_{k,n}}}
=
\maxf[\big]{0, 2 \card{\mathcal{T}_{k,n}} - \card{\mathcal{U}_{k,n}}}.
\end{equation}
Use the law of iterated expectations to write:
\begin{equation}
\E[\Big]{\maxf[\big]{0, 2 \card{\mathcal{T}_{k,n}} - \card{\mathcal{U}_{k,n}}}}
=
\E[\bigg]{\E[\Big]{\maxf[\big]{0, 2 \card{\mathcal{T}_{k,n}} - \card{\mathcal{U}_{k,n}}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \card{\mathcal{U}_{k,n}}}},
\end{equation}
and:
\begin{align}
&\E[\Big]{\maxf[\big]{0, 2 \card{\mathcal{T}_{k,n}} - \card{\mathcal{U}_{k,n}}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \card{\mathcal{U}_{k,n}} = u}
\\
&\qquad =
\Pr[\Big]{\card{\mathcal{T}_{k,n}} < u / 2 + \sqrt{u\logf{n}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \card{\mathcal{U}_{k,n}} = u}
\\
&\qquad \qquad \qquad \times \E[\Big]{\maxf[\big]{0, 2 \card{\mathcal{T}_{k,n}} - \card{\mathcal{U}_{k,n}}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \card{\mathcal{T}_{k,n}} < u / 2 + \sqrt{u\logf{n}}, \card{\mathcal{U}_{k,n}} = u}
\\
&\qquad \qquad +
\Pr[\Big]{\card{\mathcal{T}_{k,n}} \geq u / 2 + \sqrt{u\logf{n}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \card{\mathcal{U}_{k,n}} = u}
\\
&\qquad \qquad \qquad \times \E[\Big]{\maxf[\big]{0, 2 \card{\mathcal{T}_{k,n}} - \card{\mathcal{U}_{k,n}}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \card{\mathcal{T}_{k,n}} \geq u / 2 + \sqrt{u\logf{n}}, \card{\mathcal{U}_{k,n}} = u}.
\end{align}
Bound the first probability as:
\begin{equation}
\Pr[\Big]{\card{\mathcal{T}_{k,n}} < u / 2 + \sqrt{u\logf{n}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \card{\mathcal{U}_{k,n}} = u} \leq 1,
\end{equation}
and the first expectation as:
\begin{equation}
\E[\Big]{\maxf[\big]{0, 2 \card{\mathcal{T}_{k,n}} - \card{\mathcal{U}_{k,n}}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \card{\mathcal{T}_{k,n}} < u / 2 + \sqrt{u\logf{n}}, \card{\mathcal{U}_{k,n}} = u} \leq 2\sqrt{u\logf{n}},
\end{equation}
and the second expectation as:
\begin{equation}
\E[\Big]{\maxf[\big]{0, 2 \card{\mathcal{T}_{k,n}} - \card{\mathcal{U}_{k,n}}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \card{\mathcal{T}_{k,n}} \geq u / 2 + \sqrt{u\logf{n}}, \card{\mathcal{U}_{k,n}} = u} \leq u.
\end{equation}
Consider the second probability when $u \geq 1$:
\begin{multline}
\Pr[\Big]{\card{\mathcal{T}_{k,n}} \geq u / 2 + \sqrt{u\logf{n}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \card{\mathcal{U}_{k,n}} = u}
\\
=
\Pr[\Big]{\card{\mathcal{T}_{k,n}} / u \geq 1 / 2 + \sqrt{\logf{n} / u} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \card{\mathcal{U}_{k,n}} = u}.
\end{multline}
Next, let $\ExpCountBink{u} = \E[\big]{\card{\mathcal{T}_{k,n}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} \card{\mathcal{U}_{k,n}} = u}$, so:
\begin{multline}
\Pr[\Big]{\card{\mathcal{T}_{k,n}} / u \geq 1 / 2 + \sqrt{\logf{n} / u} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \card{\mathcal{U}_{k,n}} = u}
\\
=
\Pr[\Big]{\card{\mathcal{T}_{k,n}} / u - \ExpCountBink{u} / u \geq 1 / 2 - \ExpCountBink{u} / u + \sqrt{\logf{n} / u} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \card{\mathcal{U}_{k,n}} = u}.
\end{multline}
Note that:
\begin{equation}
\ExpCountBink{u} / u
= \Pr[\big]{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi^-_{\normalfontsupp} + \paren{k - 1} w_n \leq \Pi < \Pi^-_{\normalfontsupp} + k w_n},
\end{equation}
because $\mathcal{T}_{k,n} = \mathcal{U}_{k,n} \cap \mathcal{T}$ and $\mathcal{U}_{k,n} = \setb{i \in \mathcal{U}_- :\allowbreak\mathopen{} \Pi^-_{\normalfont\textsc{supp}} + \paren{k - 1} w_n \leq \Pi_{i} < \Pi^-_{\normalfont\textsc{supp}} + k w_n}$.
Recall that $\Pi^-_{\normalfont\textsc{supp}} + b_n w_n = p^* \leq 1 / 2$, so for all $k \in \setb{1, 2, \dotsc, b_n}$:
\begin{equation}
\Pr[\big]{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi^-_{\normalfontsupp} + \paren{k - 1} w_n \leq \Pi < \Pi^-_{\normalfontsupp} + k w_n} \leq 1 / 2,
\end{equation}
and:
\begin{multline}
\Pr[\Big]{\card{\mathcal{T}_{k,n}} / u - \ExpCountBink{u} / u \geq 1 / 2 - \ExpCountBink{u} / u + \sqrt{\logf{n} / u} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \card{\mathcal{U}_{k,n}} = u}
\\
\leq
\Pr[\Big]{\card{\mathcal{T}_{k,n}} / u - \ExpCountBink{u} / u \geq \sqrt{\logf{n} / u} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \card{\mathcal{U}_{k,n}} = u}.
\end{multline}
Apply Hoeffding's inequality (Theorem (ref)) to get:
\begin{equation}
\Pr[\Big]{\card{\mathcal{T}_{k,n}} / u - \ExpCountBink{u} / u \geq \sqrt{\logf{n} / u} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \card{\mathcal{U}_{k,n}} = u}
\leq \expf[\big]{-2\logf{n}}
= \frac{1}{n^2}.
\end{equation}
Taken together:
\begin{equation}
\E[\Big]{\maxf[\big]{0, 2 \card{\mathcal{T}_{k,n}} - \card{\mathcal{U}_{k,n}}} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \card{\mathcal{U}_{k,n}} = u}
\leq 2\sqrt{u\logf{n}} + \frac{u}{n^2},
\end{equation}
and:
\begin{equation}
\E[\Big]{\maxf[\big]{0, 2 \card{\mathcal{T}_{k,n}} - \card{\mathcal{U}_{k,n}}}}
=
\E[\bigg]{2\sqrt{\card{\mathcal{U}_{k,n}} \logf{n}} + \frac{\card{\mathcal{U}_{k,n}}}{n^2}},
\end{equation}
so:
\begin{equation}
\E[\bigg]{\frac{1}{n}\sum_{k = 1}^{b_n} \maxf[\big]{0, \card{\mathcal{T}_{k,n}} - \card{\mathcal{C}_{k,n}}}}
\leq
\frac{1}{n^3}\sum_{k = 1}^{b_n} \E[\big]{\card{\mathcal{U}_{k,n}}}
+
\frac{2\sqrt{\logf{n}}}{n}\sum_{k = 1}^{b_n} \E[\bigg]{\sqrt{\card{\mathcal{U}_{k,n}}}}.
\end{equation}
First consider:
\begin{equation}
\frac{1}{n^3}\sum_{k = 1}^{b_n} \E[\big]{\card{\mathcal{U}_{k,n}}}
= \frac{1}{n^3} \E[\bigg]{\sum_{k = 1}^{b_n} \card{\mathcal{U}_{k,n}}}
= \frac{\E[\big]{\card{\mathcal{U}_-}}}{n^3}
= \frac{\Pr{\Pi < p^*}}{n^2}
\leq \frac{1}{n^2},
\end{equation}
because $\mathcal{U}_{1,n}, \mathcal{U}_{2,n}, \dotsc, \mathcal{U}_{b_n,n}$ partition $\mathcal{U}_-$.
It follows that the first term converges to zero.
Next, use Jensen's inequality and concavity of the square root to get:
\begin{equation}
\frac{2\sqrt{\logf{n}}}{n}\sum_{k = 1}^{b_n} \E[\bigg]{\sqrt{\card{\mathcal{U}_{k,n}}}}
\leq
\frac{2\sqrt{\logf{n}}}{n}\sum_{k = 1}^{b_n} \sqrt{\E[\big]{\card{\mathcal{U}_{k,n}}}}.
\end{equation}
Use Jensen's inequality once more:
\begin{equation}
\frac{2\sqrt{\logf{n}}}{n}\sum_{k = 1}^{b_n} \sqrt{\E[\big]{\card{\mathcal{U}_{k,n}}}}
\leq
\frac{2 \sqrt{b_n \logf{n}}}{n} \sqrt{\sum_{k = 1}^{b_n}\E[\big]{\card{\mathcal{U}_{k,n}}}},
\end{equation}
and, finally:
\begin{equation}
\frac{2 \sqrt{b_n \logf{n}}}{n} \sqrt{\sum_{k = 1}^{b_n}\E[\big]{\card{\mathcal{U}_{k,n}}}}
=
\frac{2 \sqrt{b_n \logf{n}}}{n} \sqrt{n \Pr{\Pi < p^*}}
\leq
2 \sqrt{\frac{b_n \logf{n}}{n}},
\end{equation}
which implies that also this term converges to zero because $b_n$ was defined in the proof Lemma (ref) so that:
\begin{equation}
\lim_{n \to \infty} \frac{b_n \logf{n}}{n} = 0. \tag*{\qedhere}
\end{equation}
Proof of Lemma \ref*{lem:pscore-mdiscrep-term3}
lemmaUnder Condition \refmain{cond:left-closed}:
\begin{multline}
\E[\bigg]{\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{T}_+} \PO{i}{0} - \frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{C}_+} \PO{i}{0}}
\\
=
\frac{\Pr{\Pi \geq p^*}}{2\bar{\pi}} \paren[\Big]{\E[\big]{\POpop{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1, \Pi \geq p^*} - \E[\big]{\POpop{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0, \Pi \geq p^*}}.
\end{multline}
proofThe proof is completed immediately if $\Pr{\Pi \geq p^*} = 0$ because $\mathcal{T}_+$ and $\mathcal{C}_+$ are then empty with probability one.
The rest of the proof considers the case when $\Pr{\Pi \geq p^*} > 0$.
By the same argument as in the previous proofs, $i \in \mathcal{T}_+$ provides no more information about $\PO{i}{0}$ than $W_{i} = 1$ and $\Pi_{i} \geq p^*$, so:
\begin{equation}
\E[\bigg]{\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{T}_+} \PO{i}{0}}
= \frac{\E[\big]{\card{\mathcal{T}_+}}}{\bar{\pi} n} \E[\big]{\POpop{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 1, \Pi \geq p^*}.
\end{equation}
Similarly, $i \in \mathcal{C}_+$ provides no more information about $\PO{i}{0}$ than $W_{i} = 0$ and $\Pi_{i} \geq p^*$, and:
\begin{equation}
\E[\bigg]{\frac{1}{\bar{\pi} n} \sum_{i \in \mathcal{C}_+} \PO{i}{0}}
= \frac{\E[\big]{\card{\mathcal{C}_+}}}{\bar{\pi} n} \E[\big]{\POpop{0} \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen W = 0, \Pi \geq p^*}.
\end{equation}
Note that $\E[\big]{\card{\mathcal{T}_+}} = n \Pr{W = 1, \Pi_{i} \geq p^*}$, and similarly for $\E[\big]{\card{\mathcal{C}_+}}$ so:
\begin{multline}
\frac{\E[\big]{\card{\mathcal{T}_+}}}{\bar{\pi} n} = \frac{\Pr{\Pi_{i} \geq p^*} \Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi_{i} \geq p^*}}{\bar{\pi}}
\qquadand
\\
\frac{\E[\big]{\card{\mathcal{C}_+}}}{\bar{\pi} n} = \frac{\Pr{\Pi_{i} \geq p^*} \Pr{W = 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi_{i} \geq p^*}}{\bar{\pi}}.
\end{multline}
Condition \refmain{cond:left-closed} and $\Pr{\Pi \geq p^*} > 0$ imply that $\Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen{} \Pi_{i} \geq p^*} = 1 / 2$.
It follows that:
\begin{equation}
\Pr{W = 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi_{i} \geq p^*}
= 1 - \Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi_{i} \geq p^*}
= 1 / 2
= \Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi_{i} \geq p^*},
\end{equation}
and:
\begin{equation}
\frac{\Pr{\Pi_{i} \geq p^*} \Pr{W = 1 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi_{i} \geq p^*}}{\bar{\pi}}
= \frac{\Pr{\Pi_{i} \geq p^*} \Pr{W = 0 \nonscript\:\delimsize\vert\allowbreak\nonscript\:\mathopen \Pi_{i} \geq p^*}}{\bar{\pi}}
= \frac{\Pr{\Pi_{i} \geq p^*}}{2 \bar{\pi}}. \tag*{\qedhere}
\end{equation}