# The Pairwise Matching Design is Optimal under Extreme Noise and Assignments

David Azriel Electronic address<EMAIL_ADDRESS>Faculty of Data and
Decision Sciences, The Technion, Haifa, Israel Abba M. Krieger Electronic
address<EMAIL_ADDRESS>Department of Statistics, The Wharton
School of the University of Pennsylvania, USA  Adam Kapelner Electronic
address<EMAIL_ADDRESS>Principal Corresponding author Department of
Mathematics, Queens College, CUNY, USA

###### Abstract

We consider the general performance of the difference-in-means estimator in an
equally-allocated two-arm randomized experiment under common experimental
endpoints such as continuous (regression), incidence, proportion, count and
uncensored survival. We consider two sources of randomness: the subject-
specific assignments and the contribution of unobserved subject-specific
measurements. We then examine mean squared error (MSE) performance under a
new, more realistic _simultaneous tail criterion_. We prove that the pairwise
matching design of Greevy et al. (2004) performs best asymptotically under
this criterion when compared to other blocking designs. We also prove that the
optimal design must be less random than complete randomization and more random
than any deterministic, optimized allocation. Theoretical results are
supported by simulations in all five response types.

Keywords: experimental design, optimal design, pairwise matching, blocking,
incidence endpoint, count endpoint

##  1 Background

We consider a classic problem: a randomized experiment with $2n$ _subjects_
(_individuals_ , _participants_ or _units_). The experiment has two _arms_
(_treatments_ , _manipulations_ or _groups_), which we will call treatment and
control denoted $T$ and $C$. The goal herein is to infer the causal sample
average treatment effect (SATE) and thus, we randomize subjects thereby
assigning them into the two groups.

Formally defined, the _randomization_ (_allocation_ or an _assignment_) is a
vector $\boldsymbol{w}:=\left[w_{1},\ldots,w_{2n}\right]^{\top}$ whose entries
indicate whether the subject received $T$ (coded numerically as +1) or $C$
(coded numerically as -1) and thus this vector is an element in
$\left\\{-1,+1\right\\}^{2n}$. The only liberty the experimenter has is to
choose the entries of $\boldsymbol{w}$. The random process that results in the
allocation of the $2n$ subjects to the two arms is termed an experimental
_design_ (_strategy_ , _algorithm_ , _method_ or _procedure_.) Experimental
design may be viewed as a random draw (most often with equal probability) from
a set of $\boldsymbol{w}$’s; this process we denote as random variable
$\boldsymbol{W}$.

After the experiment concludes, we measure one _outcome_ (_response_ or
_endpoint_) of interest for the $2n$ subjects denoted
$\boldsymbol{y}=\left[y_{1},\ldots,y_{2n}\right]^{\top}$ which is of a general
data type: either continuous, incidence, count or uncensored survival and we
use these values along with the assignment $\boldsymbol{w}$ to perform
inference for the SATE.

If nothing is known about the subjects before assignment, the typical “gold-
standard” design is the balanced complete randomization design (BCRD, Wu, ,
1981, p. 1171). This design has $\binom{2n}{n}$ allocations each that satisfy
the balance constraint $\sum_{i}w_{i}=0$. Each allocation is then chosen with
equal probability.

If the subjects have observed characteristics, other designs which incorporate
these a priori measurements are more popular. We now assume each subject has
$p$ real-valued observed subject-specific _covariates_ (_measurements_ ,
_features_ or _characteristics_) collected into a row vector denoted
$\boldsymbol{x}_{i}$ for the $i$th subject. The setting we investigate is
where all $\boldsymbol{x}_{i}$’s are known beforehand and considered fixed.
This non-sequential setting was studied by Fisher,  (1925) when assigning
treatments to agricultural plots and is still of great importance today. In
fact, this setting is found in “many phase I studies [that] use ‘banks’ of
healthy volunteers … [and] … in most cluster randomised trials, the clusters
are identified before treatment is started” (Senn, , 2013, page 1440). The
more common _sequential_ experimental setting where subjects arrive one-by-one
and must be assigned on the spot (hence all $\boldsymbol{x}_{i}$’s are not
seen beforehand), will be left for future work.

When, observing subject-specific characteristics, should BCRD still be
employed? The consensus is “no” due to a reason that was noted immediately by
Fisher: under some unlucky $\boldsymbol{w}$’s there are large differences in
the distribution of observed covariates between the two arms. The amount of
covariate value heterogeneity between groups we term _observed imbalance_.
This observed imbalance creates bias during estimation from the perspective of
any single $\boldsymbol{w}$ but it is more canonical to say that it creates
variance from the perspective of considering all $\boldsymbol{w}$’s.

Thus, “restricted” designs are employed which restrict the allowable
$\boldsymbol{w}$’s in an effort to minimize the observed imbalance among the
two arms. Restricted designs have a long literature once again starting with
Fisher,  (1925, p. 251) who wrote “it is still possible to eliminate much of
the …heterogeneity, and so increase the accuracy of our [estimator], by laying
restrictions on the order in which the strips are arranged”. Here, he
introduced the _block design_ , a restricted design still popular today,
especially in clinical trials. Another early mitigation approach can be found
in Student,  (1938, p. 366) who wrote that after an unlucky, highly imbalanced
randomization, “it would be pedantic to [run the experiment] with [an
assignment] known beforehand to be likely to lead to a misleading conclusion”.
His solution is for “common sense [to prevail] and chance [be] invoked a
second time”. In foregoing the first assignment and _rerandomizing_ to find a
better assignment, all allocations worse than a predetermined threshold of
observed imbalance are eliminated. This classic strategy has been rigorously
investigated only recently (Morgan and Rubin, , 2012; Li et al., , 2018) in
the case of equal allocation. Another idea is to allocate treatment and
control among similar subjects by using a pairwise matching (PM) design
(Greevy et al., , 2004) which creates $n$ pairs of subjects which minimize an
overall average covariate distance within pair. In each pair, one subject
receives T and the other receives C with equal probability.

One may wonder about the “optimal” restricted design strategy. The design
$\boldsymbol{W}$ is a multivariate Bernoulli random variable has $2^{2n}-1$
parameters, an exponentially large number (Teugels, , 1990, Section 2.3).
Finding the optimal design is thus tantamount to solving for exponentially
many parameters using only the $2n$ observations, a hopelessly unidentifiable
task. Thus, to find an “optimal” design, the space of designs must be limited.
One way of limiting the space of designs is to do away with any notion of
randomization whatsoever and instead compute a deterministic perfect balance
(PB) optimal allocation; this is a design with two allocation vectors
$\boldsymbol{w}_{*}$ and the allocation where its subjects switched arms
$-\boldsymbol{w}_{*}$. An early advocate of this approach was Smith,  (1918)
and a good review of classic works advocating this approach such as Kiefer and
Wolfowitz,  (1959) is given in Steinberg and Hunter,  (1984, Chapter 3). A
particularly edgy advocate of PB is Harville,  (1975) who penned an article
titled “Experimental Randomization: Who Needs It?”.

We have introduced thus far a continuum of designs from the most random (BCRD)
and thus has the highest expected observed imbalance to the least random (one
optimized, deterministic $\boldsymbol{w}$) which has the lowest expected
observed imbalance. Other designs such as blocking, rerandomization and PM are
thus located somewhere in the middle of these two extremes. A natural question
to ask is do these two considerations (degree of randomness and degree of
observed imbalance) trade off among each other? Yes, since randomization
balances both observed and unobserved covariates, the less random a design is,
the more likely the unobserved covariate measurements will be imbalanced. This
imbalance in unseen characteristics has the potential to wreak havoc on
estimation error. Thus, the assumptions about these unobserved covariates and
how they are incorporated into the experimental performance metric become
critically important.

This trade-off was investigated in Kapelner et al.,  (2021) for the case of a
continuous outcome. They analyzed three unobserved covariate scenarios (I)
nature provides the worst possible values of unobserved covariates, (II) the
unobserved covariates are random noise that will be averaged over (i.e.,
colloquially, “margined out”) and (III) the unobserved covariates are random
noise but the concern is about values of these unobserved covariates that
produce terrible estimator performance. Naturally, there was a threefold
answer to what the optimal design would be. Under (I), the experimenter should
never sacrifice any randomness and thus BCRD is optimal; under (II), the
experimenter can sacrifice all randomness and employ the deterministic design
(although unpalatable to modern ears); and under (III), the experimenter
should sacrifice some randomness and use a design in between the two extremes.
Azriel et al.,  (2023), henceforth called our “previous work”, extended these
results to general response models and unequal allocation. They found that the
unequal randomization case admits the same results. But response types that
are not continuous are more complicated. Under (I), the problem is intractable
but when limited to the space of all block designs, then BCRD is the optimal
design. Under (II), the deterministic design is still optimal but impossible
as it requires knowledge of the latent parameters within the response model.
Under (III), the problem is again intractable but when limited to the space of
all block designs, then block designs with few blocks are optimal (a number of
blocks of order between $n^{1/4}$ and $n$).

Our work herein extends our previous work by examining (III) under a different
tail criterion, one that we believe to be more realistic. In our previous
work, the tail was defined as a large quantile (e.g. 95%, 99%, etc) over the
observed covariates of the expected squared error of the estimator over
assignments. This tail criterion is realistic in that it considers values of
observed covariates that can lead to poor performance. However, the inner
expectation over all assignments is troublesome. In any single experiment,
only one $\boldsymbol{w}$ is realized. Herein, we define the tail criterion to
be the quantile over the joint distribution of the possible unobserved
covariates simultaneous with the possible design assignments. We seek designs
that minimize these tail events that will ruin an experiment. Our optimal
design results are found to be fundamentally different.

When examining performance gauged by this _simultaneous tail criterion_ ,
locating the optimal design is, as expected, unidentifiable. But, when
limiting our design space to blocking designs, we find PM to be asymptotically
optimal. We define our experimental setting formally in Section 2, discuss
criterions of performance and theoretical results in Section 3, provide
simulation evidence of our results in Section 4 and conclude in Section 5.

##  2 Problem Setup

The problem setup is identical to our previous work’s setup section. We cannot
reprint it here because it will be flagged as plagiarism. Sorry for making you
click on the link. We must however reprint Table 1 below because we reference
it later in this work.

Response type name | $\mathcal{Y}$ | Model Name |  Common $\mu_{T,i}$ and $\mu_{C,i}$ | $\Theta$
---|---|---|---|---
Continuous | $\mathbb{R}$ | Linear | $\beta_{0}+\boldsymbol{\beta}^{\top}\boldsymbol{x}_{i}+\beta_{T}w_{i}$ | $\mathbb{R}$
Incidence | $\left\\{0,1\right\\}$ | Log Odds | $\left(1+e^{-(\beta_{0}+\boldsymbol{\beta}^{\top}\boldsymbol{x}_{i}+\beta_{T}w_{i})}\right)^{-1}$ | $(0,1)$
Proportion | $(0,1)$ | Linear
Count | $\left\\{0,1,\ldots\right\\}$ | Log Linear | $e^{\beta_{0}+\boldsymbol{\beta}^{\top}\boldsymbol{x}_{i}+\beta_{T}w_{i}}$ | $(0,\infty)$
Survival | $(0,\infty)$
Table 1: Response types considered where $\beta$’s are unknown parameters.

##  3 Analyzing Designs

It is impossible to employ the MSE as the criterion in which we compare
different designs since $\boldsymbol{v}$ is not observed (as
$\boldsymbol{z}_{T}$ and $\boldsymbol{z}_{C}$ are not observed). Our previous
work has design recommendation results for (I) the criterion of the _worst
case MSE_ , i.e. the worst $\boldsymbol{z}_{T}$ and $\boldsymbol{z}_{C}$; and
results under (II) the “mean MSE”, i.e. the average $\boldsymbol{z}_{T}$ and
$\boldsymbol{z}_{C}$. The _worst case MSE_ design only considers the most
improbable tail event and thus is too conservative. The _mean MSE_ design is
either intractable or might lead to idiosyncratic $\boldsymbol{z}_{T}$’s and
$\boldsymbol{z}_{C}$’s that introduce large mean squared error with non-
negligible probability. Thus, we wish to analyze a criterion that balances
these two extremes; one such criterion is a tail event MSE. Our previous paper
defined the “single quantile tail criterion” which measures this tail event,

$\displaystyle\text{Quantile}_{\boldsymbol{Z}_{T},\boldsymbol{Z}_{C}}\left[\mathbb{M}\text{SE}_{\boldsymbol{W}}\left[\hat{\tau}\right],q\right].$
(1)

In order to define the quantile operator above, we must formally let
$\boldsymbol{Z}_{T}$ and $\boldsymbol{Z}_{C}$ be the vector random variables
that generate the $\boldsymbol{z}_{T}$ and $\boldsymbol{z}_{C}$ vectors
respectively (quantities that are canonically denoted with the Greek letter
epsilon). We assume
$\mathbb{E}\left[\boldsymbol{Z}_{T}\right]=\mathbb{E}\left[\boldsymbol{Z}_{C}\right]=\boldsymbol{0}_{n}$
and that the components in $\boldsymbol{Z}_{T}$ are independent, the
components of $\boldsymbol{Z}_{C}$ are independent and the components of the
former and latter are mutually independent. Although the distributional form
of both $\boldsymbol{Z}_{T}$ and $\boldsymbol{Z}_{C}$ are implicitly
constrained by the response type specified by $\mathcal{Y}$, we do not make
any formal distributional assumptions beyond vague moment assumptions in the
next section.

As explained in Section 1, the tail event of Equation 1 is unrealistic as it
averages over every possible assignment vector $\boldsymbol{w}$. However, in
the real world, any experiment has only one $\boldsymbol{w}$. A more realistic
criterion is thus the “simultaneous quantile tail criterion” which considers
potentially ruinous joint
$\left\\{\boldsymbol{w},\boldsymbol{z}_{T},\boldsymbol{z}_{C}\right\\}$
realizations,

$\displaystyle\text{Quantile}_{\boldsymbol{W},\boldsymbol{Z}_{T},\boldsymbol{Z}_{C}}\left[(\hat{\tau}-\tau)^{2},q\right]=\mathbb{E}_{\,\boldsymbol{W},\boldsymbol{Z}_{T},\boldsymbol{Z}_{C}}\left[(\hat{\tau}-\tau)^{2}\right]+c_{\boldsymbol{W},q}\sqrt{\mathbb{V}\text{ar}_{\boldsymbol{W},\boldsymbol{Z}_{T},\boldsymbol{Z}_{C}}\left[(\hat{\tau}-\tau)^{2}\right]}$

where $\boldsymbol{W}$ and $q$ determine the constant $c_{\boldsymbol{W},q}$.
Although the design also affects the constant $c_{\boldsymbol{W},q}$, our
simulation results indicate that it remains more or less constant with respect
to a certain quantile over a wide variety of designs. We henceforth consider
our criterion as an approximate quantile which treats $c_{\boldsymbol{W},q}$
as a fixed number,

$\displaystyle Q$ $\displaystyle:=$
$\displaystyle\mathbb{E}_{\,\boldsymbol{W},\boldsymbol{Z}_{T},\boldsymbol{Z}_{C}}\left[(\hat{\tau}-\tau)^{2}\right]+c_{q}\sqrt{\mathbb{V}\text{ar}_{\boldsymbol{W},\boldsymbol{Z}_{T},\boldsymbol{Z}_{C}}\left[(\hat{\tau}-\tau)^{2}\right]}.$
(2)

Section A.2 in the Supplementary Material shows the expectation term in (2) is
equal to

$\displaystyle\mathbb{E}_{\,\boldsymbol{W},\boldsymbol{Z}_{T},\boldsymbol{Z}_{C}}\left[(\hat{\tau}-\tau)^{2}\right]=\frac{1}{4n^{2}}\boldsymbol{\mu}^{\top}\boldsymbol{\Sigma}_{W}\boldsymbol{\mu}+c_{Z}$
(3)

where $\boldsymbol{\mu}:=\boldsymbol{\mu}_{T}+\boldsymbol{\mu}_{C}$ and
$c_{Z}$ is a constant with respect to the design $\boldsymbol{W}$. Our
previous work named this the “mean criterion”. The variance expression is
complicated as it has fourth moments in $\boldsymbol{W}$.

It is impossible to locate the optimal design according to criterion $Q$ as
the entries of $\boldsymbol{\mu}$ are unknown (they are dependent on unknown
parameters) and further, many designs share the same
$\boldsymbol{\Sigma}_{W}$. However, if we limit our scope to the space of
block designs, the problem becomes tractable. The largest block size has $B=1$
and is equivalent to BCRD; the smallest block size has $B=n$ and is equivalent
to PM. We consider all homogeneous block designs where $B$ divides $2n$. To
create blocks, we assume knowledge of $\boldsymbol{\mu}$ and order the $2n$
subjects by the indices of the order statistics
$\mu_{(1)},\mu_{(2)},\ldots,\mu_{(2n)}$ and thus $\boldsymbol{\mu}$ is assumed
sorted going forward. We then divide the subjects into $B$ blocks retaining
that order. When $p=1$, then the order of the entries of vector
$\boldsymbol{\mu}$ has the same order of the entries of the vector
$\boldsymbol{x}$ among the monotonic response models we consider (Table 1).
Thus, the order of $\boldsymbol{\mu}$ can be assumed known. For $p>1$,
knowledge of $\boldsymbol{\mu}$’s values is unrealistic. However, the
simulations of Section 4 demonstrate that our main results hold under the
approximate sorting of $\boldsymbol{\mu}$ accomplished by standard blocking
procedures.

Our main results found in the next two sections are (1) PM has optimal
performance as measured by $Q$ among block designs and (2) deterministic
perfect balance (PB) performs worse than PM. Following our previous work,
these two results imply the optimal design exists between these two extremes
(i.e., more random than PB and less random than BCRD).

###  3.1 The PM design is Optimal Among Block Designs

By Equation 2, the quantile criterion is minimized for any value of
$c_{\boldsymbol{W},q}$ when both the expectation and the variance of
$(\hat{\tau}-\tau)^{2}$ are minimal. Below we show that the same claim holds
asymptotically for
$\mathbb{V}\text{ar}_{\boldsymbol{W},\boldsymbol{Z}_{T},\boldsymbol{Z}_{C}}\left[(\hat{\tau}-\tau)^{2}\right]$
implying that PM is asymptotically optimal among block designs regardless of
the value of the constant.

Let $\rho_{i}=\mathbb{V}\text{ar}\left[Z_{i}\right]$. Assume

######  Assumption 3.1.

$\mathbb{E}\left[Z_{i}^{4}\right]$ is bounded for all $i$,

######  Assumption 3.2.

$\frac{1}{2n}\sum_{i=1}^{2n}\rho_{i}\to\bar{\rho}$,

######  Assumption 3.3.

$\frac{1}{n}\sum_{i=1}^{n}(\mu_{2i}-\mu_{2i-1})^{2}\to 0$,

which are standard assumptions about moments being bounded. Let
$\boldsymbol{W}_{B}$ denote the block design with $B$ blocks constructed via
the explanation found in the previous section. Section A.3 proves the follow
result.

######  Theorem 3.1.

Under Assumptions 3.1, 3.2 and 3.3,

  1. (a)

$\lim\inf_{n\to\infty}n^{2}\,\mathbb{V}\text{ar}_{\boldsymbol{W}_{B},\boldsymbol{Z}_{T},\boldsymbol{Z}_{C}}\left[(\hat{\tau}-\tau)^{2}\right]\geq\frac{\bar{\rho}^{2}}{8}$.

  2. (b)

For PM,
$\lim_{n\to\infty}n^{2}\,\mathbb{V}\text{ar}_{\boldsymbol{W}_{n},\boldsymbol{Z}_{T},\boldsymbol{Z}_{C}}\left[(\hat{\tau}-\tau)^{2}\right]=\frac{\bar{\rho}^{2}}{8}$.

Thus, $\bar{\rho}^{2}/8$ is a lower bound for the asymptotic variance of the
MSE for block designs, and this lower bound is attained under PM. Theorem 3.3
of our previous work implies that the expectation term in the tail (Equation
3) is minimized under PM. Combining this with Theorem 3.1 above implies our
main result,

######  Corollary 3.1.1.

Under Assumptions 3.1, 3.2 and 3.3, PM is the asymptotically optimal block
design when performance is measured by criterion $Q$ for all response types
under consideration and for all values of the constant $c_{q}$.

This result will also hold for many other criterions which are a function of
the mean and variance.

###  3.2 PM Outperforms PB and the Optimal Design is Harmony

In the case of equal allocation, the PB design is composed of a single
$\boldsymbol{w}_{*}$ and its mirror $-\boldsymbol{w}_{*}$ that both uniquely
minimize $|(\boldsymbol{\mu}_{T}+\boldsymbol{\mu}_{C})^{\top}\boldsymbol{w}|$.
If $\boldsymbol{\mu}_{T}+\boldsymbol{\mu}_{C}$ were known (which they are not
except in the case of the linear continuous response with $p=1$, in which they
are known up to a linear transformation), the expected value term in the MSE
(Equation 3) is negligible; it is of order of $O(n^{3}2^{-2n})$ as shown in
Kallus,  (2018, Section 3.3). In Section A.4 of the Supplementary Material we
show

$\displaystyle\lim_{n\to\infty}n^{2}\,\mathbb{V}\text{ar}_{\boldsymbol{W}_{n},\boldsymbol{Z}_{T},\boldsymbol{Z}_{C}}\left[(\hat{\tau}-\tau)^{2}\right]=\frac{\bar{\rho}^{2}}{2}.$

This implies that the variance of the MSE under PB is approximately four times
larger than under PM (cf. Theorem 3.1b). Notice that under both PB and PM, the
mean MSE is negligible compared to the standard error of the MSE, as the
latter is of order $1/n$ for both PB and PM and the former is of smaller
order.

Thus, similar to BCRD, PB performs worse than PM. This result combined with
the demonstration that PM performs better than BCRD (Corollary 3.1.1) implies
that the optimal design according to criterion $Q$ is more random than BCRD
and less random than PB (i.e., the optimal design has less observed covariate
imbalance than BCRD and more observed covariate imbalance than PB).

##  4 Simulations

We simulate under a variety of scenarios to verify the performance of the
simple estimator (Equation LABEL:eq:estimator) under the mean criterion
(Equation 3) and the $q=.95$ tail criterion (Equation 2) comports with our
main result (Corrolary 3.1.1).

The sample size simulated is $2n=96$ so that we have both a realistically-
sized experiment and a wide variety of homogeneously-sized blocking designs,
$B\in\left\\{1,2,3,4,6,8,12,16,24,48\right\\}$. We simulate under a different
number of covariates $p\in\left\\{1,2,5\right\\}$. We use all five common
response types: continuous, incidence, proportion, count and survival. All
response mean models are GLMs and hence contain an internal linear component
$\mu_{i}:=\beta_{0}+\boldsymbol{\beta}_{1}\boldsymbol{x}_{i}+\beta_{T}w_{i}$
(see columns 3 and 4 of Table 1). The values of the covariate coefficients are
kept constant for all response types: $\beta_{0}=0$,
$\boldsymbol{\beta}=\left[10~{}-2.5~{}-2.5~{}-2.5~{}-2.5\right]$ and
$\beta_{T}=0.001$. The covariates were chosen to be highly representative in
the response function and the treatment effect was chosen to be small; these
settings in tandem serve to emphasize performance differences among the block
designs. One set of fixed covariates are drawn for each pair of response type
and number of covariates $p$. Covariate values are always drawn iid and
response values are always drawn independently. Covariate distributions,
response distributions and other response parameters used in this simulation
are found in Table 2.

Response | Covariate | Response | Response
---|---|---|---
type name | Distribution | Distribution | Parameters
Continuous | $U(-0.5,0.5)$ | $\mathcal{N}\left(\mu_{i},\,\sigma^{2}\right)$ | $\sigma=1$
Incidence | $U(-10,10)$ | $\mathrm{Bernoulli}\left(\mu_{i}\right)$ | N/A
Proportion | $U(-0.5,0.5)$ | $\mathrm{Beta}\left(\phi\mu_{i},\,\phi(1-\mu_{i})\right)$ | $\phi=4$
Count | $U(-0.5,0.5)$ | $\mathrm{Poisson}\left(\mu_{i}\right)$ | N/A
Survival | $U(-0.5,0.5)$ | $\mathrm{Weibull}\left(\mu_{i}/\Gamma\left(1+1/k\right),\,k\right)$ | $k=2$
Table 2: Simulation settings and parameters.

The tail criterion is computed on the distribution of the MSE over
$\boldsymbol{Z}_{T},\boldsymbol{Z}_{C}$. To approximate this quantile, we
generate $N_{y}:=100,000$ pairs $\boldsymbol{y}_{T},\boldsymbol{y}_{C}$ using
draws from the response distribution (and hence implicitly draw pairs
$\boldsymbol{z}_{T},\boldsymbol{z}_{C}$). Using these draws, we compute
$\boldsymbol{v}$ and then can exactly compute the MSE via the quadratic form
of Equation LABEL:eq:mse. (The entries of $\boldsymbol{\Sigma}_{W}$ are for
each block design specified by the specific $B$). We approximate the $q=.95$
tail criterion using the empirical 95th percentile of the $N_{y}$ MSE values.

For our theoretical results to hold for block designs, the subjects (and thus
the entries of $\boldsymbol{v}$) must be ordered in blocks corresponding to
the block-diagonal structure of $\boldsymbol{\Sigma}_{W}$. For $p=1$, simply
ordering the subjects in the order of the one covariate measurement satisfies
this requirement for all $B$ given our monotonic GLM response form. For $p>1$,
block designs were constructed as a function of the first two covariates (as
the number of blocks increases exponentially in $p$, a common problem in
experimental practice). We approximate an optimal block design for two
covariates by first ordering the subjects by the first covariate. Then within
blocks of size $2n_{B}$, we sort by the second covariate. Thus, we emphasize,
simulation results for $p>1$ will be approximate.

The mean criterion and $q=.95$ tail criterion $Q$ simulation results for
$p=1,5$ are presented in Figure 1 (the $p=2$ results are substantively the
same). We can see that that PM is the best performing design for criterion
$Q$. This empirical result also vindicates the assumptions made about the
blocking design (Assumptions 3.1, 3.2 and 3.3) and additionally demonstrates
the asymptotic results apply in the realistic experimental sample size of
$n\approx 100$. The incidence outcome has a more discrete relationship between
the MSE and $B$. This is due to the difficulty of obtaining
$(y_{T,i},y_{C,i})$ dis/concordant pairs; given the small sample size there is
not much variation in the number of ties.

Figure 1: Simulated average MSE (plotted in red) and empirical simultaneous
95%ile MSE tail (plotted in blue) with 95% bootstrap confidence intervals
(plotted in black) by value of $B$, $n=96$, $p=1,5$, all five investigated
response types and all appropriate block sizes (where $B=1$ is BCRD and $B=48$
is PM). The squared error (the y-axis) is relative to each of the ten
individual $p~{}\times$ response type plots and thus its numeric tick labels
are unshown.

For $p>1$, our theorems do not exactly apply as the $v_{i}$’s are not
precisely ordered into the blocks, but only approximately blocked by the
arrangement of two covariates. Notwithstanding, the results for $p=5$ overall
demonstrate the robustness of our theoretical results to situations of
imperfect blocking; and imperfect blocking is the blocking design employed in
real-world experiments.

In this previous simulation, PM was not implemented as one does in the
practice for $p>1$. In practice, one first calculates the proportional
between-subjects Mahalanobis distance (Stuart, , 2010, Section 2.2) via
$(\boldsymbol{x}_{\ell}-\boldsymbol{x}_{m})^{\top}\hat{\Sigma}_{X}^{-1}(\boldsymbol{x}_{\ell}-\boldsymbol{x}_{m})$
where $\hat{\Sigma}_{X}^{-1}$ is the $p\times p$ sample variance covariance
matrix of the $2n$ subjects’ covariate vectors for all the $\binom{2n}{n}$
pairs of subjects with indices $\ell,m$. This results in a symmetric distance
matrix of size $2n\times 2n$. Then, one runs the optimal nonbipartite matching
algorithm that finishes in polynomial time (Lu et al., , 2011) which runs on
the distance matrix returning the best-matched set of pairs of indices and
then sorts the subjects into these pairs (the order of the pairs does not
matter as $\boldsymbol{\Sigma}_{W}$ will remain the same). We run a second
simulation to both (a) check our PM performance as measured by the
simultaneous $Q$ for $p>1$ and (b) ensure PM also outperforms PB as a check
our result of Section 3.2. Here, we compare BCRD, PM and PB.

The second simulations’ settings were the same as the first simulation except
$N_{y}=30,000$. For PM, we used the procedure outlined in the previous
paragraph implemented in the R package nbpMatching (Beck et al., , 2016). For
$p=1$ for all response types, this procedure is identical to sorting the
$\boldsymbol{v}$ vector but for $p>1$, it can only approximately sort the
$\boldsymbol{v}$ vector. For PB, recall the location of $\boldsymbol{w}_{*}$
is an NP-hard problem. To approximate $\boldsymbol{w}_{*}$, we used the greedy
pair switching procedure of Krieger et al.,  (2019) using 10,000 starting
allocation vectors and letting the best ending allocation vector of the 10,000
being considered $\boldsymbol{w}_{*}$. As PB is a deterministic procedure,
this $\boldsymbol{w}_{*}$ was retained for all $N_{y}$ draws of the response
values.

The results of the second simulation can be found in Figure 2. Here we see
that PM outperforms PB as measured by $Q$. It also outperforms PB when
measured by the mean in non-continuous response types. This is expected as the
true $\boldsymbol{w}_{*}$ is unknowable from the observed covariate values
alone. We also see that for $p>1$ (which our theory does not describe), the
same results hold as the $\boldsymbol{v}$ vector is approximately sorted and
sectioned into pairs. At first glance, it is surprising that PM outperforms PB
for the continuous response with $p=5$. But keep in mind that PB is computing
an allocation purely on the $\boldsymbol{x}_{i}$’s without access to the
uneven covariate weights, $\boldsymbol{\beta}$. Given that the first covariate
is weighted within the response as much as the other four covariates, making
the value of $x_{1}$ similar within subjects pairs (PM) provides superior
estimation performance compared to making all five covariate averages in the
two arms similar (PB).

Figure 2: Simulated average MSE (plotted in red) and empirical simultaneous
95%ile MSE tail (plotted in blue) with 95% bootstrap confidence intervals
(plotted in black) by design, $n=96$, $p=1,5$, all five investigated response
types and all appropriate block sizes. The squared error (the y-axis) is
relative to each of the ten individual $p~{}\times$ response type plots and
thus its numeric tick labels are unshown.

##  5 Discussion

Randomized experimentation comes with the choice of “how to randomize”? A
default design is complete randomization independent of subjects’ covariates.
This is seldom done as the inevitable imbalance among the arms implies a
highly visible risk of bias. Can we design one perfect assignment that
minimizes covariate imbalance across arms? Although this may “feel” optimal,
it is not (except in the case of $p=1$ and a linear response) as the
covariate-response models are arbitrarily complicated. Further, this one
perfect assignment is NP-hard to compute.

Commonly employed designs are between the two extremes mentioned above; they
sacrifice some randomness to get some imbalance reduction. Kapelner et al.,
(2021) investigated how to harmonize these two considerations for a continuous
response to choose a design. Therein we proposed a “single quantile tail
criterion” which averages MSE over the design and then takes the quantile of
the MSE over unobserved covariate realizations. We showed this a performance
metric is a trade-off of both degree of randomness and degree of observed
covariate imbalance reduction.

Herein, we propose a more realistic related criterion called the “double
quantile tail criterion” which takes the quantile of the MSE over both the
experimental allocation and the unobserved covariates for general response
types. We then prove that the asymptotically optimal block design is achieved
with pairwise matching (PM) and this is our unconditional advice for
experimenters. Although this work focuses on estimation, these blocking
designs should have high power as well as many allocations can be generated
which are highly independent (Krieger et al., , 2020). Additional simulation
results (unshown) under larger values of the average treatment effect
parameters shows that the design difference performance is especially
sensitive to PM versus other blocking designs in cases of small treatment
effects; it can make the difference between finding the effect or not.

There are many other avenues to explore. First, although we proved that PM is
asymptotically optimal, we did not prove it is uniquely optimal as we only
considered block designs. We only proved its optimality for the case of
knowing the ordering of the mean response function contributions (a function
of the observed covariates and treatment). We would like to prove its
optimality under PM in the real-world which uses Mahalanobis-distance
matching.

Another area of exploration could be understanding the tail criterion for
other designs such as rerandomization and greedy pair switching. Additionally,
survival is an important experimental endpoint in clinical trials but this
work only considered uncensored survival measurement while the vast majority
of survivals collected in real-world experiments are censored. Also, in
Kapelner et al.,  (2021, Section 2.3), we explored the ordinary least squares
(OLS) estimator for continuous response. We believe the performance of the OLS
estimator in our tail criterion can be analyzed and our intuition is that PM
would also emerge as optimal among block designs. However, this avenue would
be difficult to explore for general response types as the analogous estimators
do not have closed form (e.g. if the response is binary, the multivariate
logistic regression estimates are the result of computational iteration).
Finally, our tail criterion is only one metric that combines mean and standard
deviation of MSE. Other criterions can also be useful such as their ratio (the
Sharpe measure). Also, work can be done to find the optimal imbalance design
under unequal allocation ($n_{T}\neq n_{C}$). We can also investigate optimal
designs for sequential experiments, the most common type of clinical trial.

## Funding

This research was supported by Grant No 2018112 from the United States-Israel
Binational Science Foundation (BSF).

## References

  * Azriel et al., (2023) Azriel, D., Krieger, A. M., and Kapelner, A. (2023).  The optimality of blocking designs in equally and unequally allocated randomized experiments with general response.  arXiv (2212.01887).
  * Beck et al., (2016) Beck, C., Lu, B., and Greevy, R. (2016).  nbpmatching: Functions for optimal non-bipartite matching. r package version 1.5.1.
  * Fisher, (1925) Fisher, R. A. (1925).  Statistical methods for research workers.  Edinburgh Oliver & Boyd.
  * Freedman, (2008) Freedman, D. A. (2008).  On regression adjustments to experimental data.  Advances in Applied Mathematics, 40(2):180–193.
  * Greevy et al., (2004) Greevy, R., Lu, B., Silber, J. H., and Rosenbaum, P. (2004).  Optimal multivariate matching before randomization.  Biostatistics, 5(2):263–275.
  * Harville, (1975) Harville, D. A. (1975).  Experimental randomization: Who needs it?  The American Statistician, 29(1):27–31.
  * Kallus, (2018) Kallus, N. (2018).  Optimal a priori balance in the design of controlled experiments.  Journal of the Royal Statistical Society: Series B (Statistical Methodology), 80(1):85–112.
  * Kapelner et al., (2021) Kapelner, A., Krieger, A. M., Sklar, M., Shalit, U., and Azriel, D. (2021).  Harmonizing optimized designs with classic randomization in experiments.  The American Statistician, 75(2):195–206.
  * Kiefer and Wolfowitz, (1959) Kiefer, J. and Wolfowitz, J. (1959).  Optimum designs in regression problems.  The Annals of Mathematical Statistics, pages 271–294.
  * Krieger et al., (2019) Krieger, A. M., Azriel, D., and Kapelner, A. (2019).  Nearly random designs with greatly improved balance.  Biometrika, 106(3):695–701.
  * Krieger et al., (2020) Krieger, A. M., Azriel, D., Sklar, M., and Kapelner, A. (2020).  Improving the power of the randomization test.  arXiv preprint arXiv:2008.05980.
  * Li et al., (2018) Li, X., Ding, P., and Rubin, D. B. (2018).  Asymptotic theory of rerandomization in treatment–control experiments.  Proceedings of the National Academy of Sciences, 115(37):9157–9162.
  * Lin, (2013) Lin, W. (2013).  Agnostic notes on regression adjustments to experimental data: Reexamining freedman’s critique.  The Annals of Applied Statistics, 7(1):295–318.
  * Lu et al., (2011) Lu, B., Greevy, R., Xu, X., and Beck, C. (2011).  Optimal nonbipartite matching and its statistical applications.  The American Statistician, 65(1):21–30.
  * Morgan and Rubin, (2012) Morgan, K. L. and Rubin, D. B. (2012).  Rerandomization to improve covariate balance in experiments.  The Annals of Statistics, pages 1263–1282.
  * Rosenberger and Lachin, (2016) Rosenberger, W. F. and Lachin, J. M. (2016).  Randomization in clinical trials: theory and practice.  John Wiley & Sons, second edition.
  * Rubin, (2005) Rubin, D. B. (2005).  Causal inference using potential outcomes: Design, modeling, decisions.  Journal of the American Statistical Association, 100(469):322–331.
  * Senn, (2013) Senn, S. (2013).  Seven myths of randomisation in clinical trials.  Statistics in Medicine, 32(9):1439–1450.
  * Smith, (1918) Smith, K. (1918).  On the standard deviations of adjusted and interpolated values of an observed polynomial function and its constants and the guidance they give towards a proper choice of the distribution of observations.  Biometrika, 12(1/2):1–85.
  * Steinberg and Hunter, (1984) Steinberg, D. M. and Hunter, W. G. (1984).  Experimental design: review and comment.  Technometrics, 26(2):71–97.
  * Stuart, (2010) Stuart, E. A. (2010).  Matching methods for causal inference: A review and a look forward.  Statistical science, 25(1):1.
  * Student, (1938) Student (1938).  Comparison between balanced and random arrangements of field plots.  Biometrika, pages 363–378.
  * Teugels, (1990) Teugels, J. L. (1990).  Some representations of the multivariate bernoulli and binomial distributions.  Journal of multivariate analysis, 32(2):256–268.
  * Wu, (1981) Wu, C. F. (1981).  On the robustness and efficiency of some randomized designs.  The Annals of Statistics, pages 1168–1177.

Supplementary Materials for
“The Pairwise Matching Design is Optimal under Extreme Noise and Assignments”

by David Azriel, Abba Krieger and Adam Kapelner

##  Appendix A Technical Proofs

###  A.1 Estimator Computation

The contribution to $\hat{\tau}$ from individual $i$ is $\frac{y_{Ti}}{n}$
when $w_{i}=1$ and $-\frac{y_{Ci}}{n}$ when $w_{i}=-1$. This contribution can
be summarized as $((y_{Ti}-y_{Ci})+w_{i}(y_{Ti}+y_{Ci}))/(2n)$. When this is
summed over all individuals $i$ we have our result

$\displaystyle\hat{\tau}=\frac{1}{2n}\left(\boldsymbol{1}_{2n}^{\top}\left(\boldsymbol{y}_{T}-\boldsymbol{y}_{C}\right)+\boldsymbol{W}^{\top}\left(\boldsymbol{y}_{T}+\boldsymbol{y}_{C}\right)\right).$

###  A.2 Expectation of the MSE

For this section and following sections, let
$\boldsymbol{Z}:=\boldsymbol{Z}_{T}+\boldsymbol{Z}_{C}$ and
$\boldsymbol{\mu}:=\boldsymbol{\mu}_{T}+\boldsymbol{\mu}_{C}$.

$\displaystyle=$
$\displaystyle\mathbb{E}_{\,\boldsymbol{Z}_{T},\boldsymbol{Z}_{C}}\left[\mathbb{E}_{\,\boldsymbol{W}}\left[(\hat{\tau}-\tau)^{2}\right]\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\,\boldsymbol{Z}_{T},\boldsymbol{Z}_{C}}\left[\frac{1}{4}\left(\frac{\boldsymbol{\mu}_{T}+\boldsymbol{Z}_{T}}{n}+\frac{\boldsymbol{\mu}_{C}+\boldsymbol{Z}_{C}}{n}\right)^{\top}\boldsymbol{\Sigma}_{W}\left(\frac{\boldsymbol{\mu}_{T}+\boldsymbol{Z}_{T}}{n}+\frac{\boldsymbol{\mu}_{C}+\boldsymbol{Z}_{C}}{n}\right)\right]$
$\displaystyle=$
$\displaystyle\frac{1}{4n^{2}}\mathbb{E}_{\,\boldsymbol{Z}}\left[\left(\boldsymbol{\mu}+\boldsymbol{Z}\right)^{\top}\boldsymbol{\Sigma}_{W}\left(\boldsymbol{\mu}+\boldsymbol{Z}\right)\right]$
$\displaystyle=$
$\displaystyle\frac{1}{4n^{2}}\mathbb{E}_{\,\boldsymbol{Z}}\left[\boldsymbol{\mu}^{\top}\boldsymbol{\Sigma}_{W}\boldsymbol{\mu}+2\boldsymbol{\mu}^{\top}\boldsymbol{\Sigma}_{W}\boldsymbol{Z}+\boldsymbol{Z}^{\top}\boldsymbol{\Sigma}_{W}\boldsymbol{Z}\right]$
$\displaystyle=$
$\displaystyle\frac{1}{4n^{2}}\left(\boldsymbol{\mu}^{\top}\boldsymbol{\Sigma}_{W}\boldsymbol{\mu}+\mathbb{E}_{\,\boldsymbol{Z}}\left[\boldsymbol{Z}^{\top}\boldsymbol{\Sigma}_{W}\boldsymbol{Z}\right]\right)$
$\displaystyle=$
$\displaystyle\frac{1}{4n^{2}}\left(\boldsymbol{\mu}^{\top}\boldsymbol{\Sigma}_{W}\boldsymbol{\mu}+\text{tr}\left[\boldsymbol{\Sigma}_{W}\boldsymbol{\rho}\right]\right)$

where $\boldsymbol{\rho}$ denotes the diagonal variance-covariance matrix of
$\boldsymbol{Z}$. To compute the trace, we need to consider only the diagonal
entries of $\boldsymbol{\Sigma}_{W}\boldsymbol{\rho}$. The $i$th diagonal
entry of this product is
${\boldsymbol{\Sigma}_{W}}_{i\,\cdot}{\boldsymbol{\Sigma}_{Z}}_{\cdot\,i}={\boldsymbol{\Sigma}_{W}}_{i\,i}{\boldsymbol{\Sigma}_{Z}}_{i\,i}$
due to $\boldsymbol{\rho}$ being diagonal. From Assumption
LABEL:ass:equal_chance_T, we know that all the diagonal entries of
$\boldsymbol{\Sigma}_{W}$ are 1 and thus
$\text{tr}\left[\boldsymbol{\Sigma}_{W}\boldsymbol{\rho}\right]=\text{tr}\left[\boldsymbol{\rho}\right]$.
Upon substitution, the result is

$\displaystyle\mathbb{E}_{\,\boldsymbol{W},\boldsymbol{Z}_{T},\boldsymbol{Z}_{C}}\left[(\hat{\tau}-\tau)^{2}\right]$
$\displaystyle=$
$\displaystyle\frac{1}{4n^{2}}\left(\boldsymbol{\mu}^{\top}\boldsymbol{\Sigma}_{W}\boldsymbol{\mu}+\text{tr}\left[\boldsymbol{\Sigma}_{W}\boldsymbol{\rho}\right]\right)+\underbrace{\frac{1}{4n^{2}}\text{tr}\left[\boldsymbol{\rho}\right]}.$

where the underbraced term is design-independent and denoted as $c_{Z}$.

###  A.3 Proof of Theorem 3.1

By Equation LABEL:eq:estimator, the MSE can be expressed as

$\text{MSE}:=(\hat{\tau}-\tau)^{2}=\frac{1}{4n^{2}}\left(\boldsymbol{W}^{\top}\left(\boldsymbol{Y}_{T}+\boldsymbol{Y}_{C}\right)\right)^{2}$

where this notation depresses its dependence on
$\boldsymbol{W},\boldsymbol{Z}_{T},\boldsymbol{Z}_{C}$. The variance of the
MSE is

$\mathbb{V}\text{ar}_{\boldsymbol{Z},\boldsymbol{W}}\left[\text{MSE}\right]=\mathbb{V}\text{ar}_{\boldsymbol{Z}}\left[\mathbb{E}_{\,\boldsymbol{W}}\left[\text{MSE}\,|\,\boldsymbol{Z}\right]\right]+\mathbb{E}_{\,\boldsymbol{Z}}\left[\mathbb{V}\text{ar}_{\boldsymbol{W}}\left[\text{MSE}\,|\,\boldsymbol{Z}\right]\right]$
(4)

where $\boldsymbol{Z}$ denotes the collection of
$\boldsymbol{Z}_{T},\boldsymbol{Z}_{C}$.

#### Proof of part (a)

Consider the variance decomposition in Equation 4. It follows that

$\mathbb{V}\text{ar}_{\boldsymbol{Z},\boldsymbol{W}_{B}}\left[\text{MSE}\right]\geq\mathbb{E}_{\,\boldsymbol{Z}}\left[\mathbb{V}\text{ar}_{\boldsymbol{W}_{B}}\left[\text{MSE}\,|\,\boldsymbol{Z}\right]\right].$

Below the latter term is analyzed.

Recall that $\boldsymbol{v}:=\boldsymbol{\mu}+\boldsymbol{Z}$. Consider first
the case of $B=n$, i.e., PM. We have that

$\boldsymbol{v}^{T}\boldsymbol{W}_{n}=U_{1}(v_{2}-v_{1})+U_{2}(v_{4}-v_{3})+\cdots+U_{n}(v_{2n}-v_{2n-1}),$

where $U_{1},\ldots,U_{n}$ are iid with $P(U=1)=P(U=-1)=1/2$. Since
$U_{i}^{2}=1$,

$4n^{2}\text{MSE}=(\boldsymbol{v}^{T}\boldsymbol{W}_{n})^{2}=\sum_{i=1}^{n}(v_{2i}-v_{2i-1})^{2}+2\sum_{1\leq
i<j\leq n}U_{i}U_{j}(v_{2i}-v_{2i-1})(v_{2j}-v_{2j-1})$

The variance of $U_{i}U_{j}$ for $i\neq j$ is 1 and the covariance between
$U_{i}U_{j}$ and $U_{i^{\prime}}U_{j^{\prime}}$ is 0 if
$(i,j)\neq(i^{\prime},j^{\prime})$, $i<j,i^{\prime}<j^{\prime}$; therefore,

$\mathbb{V}\text{ar}_{\boldsymbol{W}_{n}}\left[\text{MSE}\,|\,\boldsymbol{Z}\right]=\frac{1}{16n^{4}}\sum_{1\leq
i<j\leq n}(v_{2i}-v_{2i-1})^{2}(v_{2j}-v_{2j-1})^{2}.$ (5)

Thus,

$\mathbb{E}_{\,\boldsymbol{Z}}\left[\mathbb{V}\text{ar}_{\boldsymbol{W}_{n}}\left[\text{MSE}\,|\,\boldsymbol{Z}\right]\right]\\\
=\frac{1}{16n^{4}}\sum_{1\leq i<j\leq
n}[(\mu_{2i}-\mu_{2i-1})^{2}(\mu_{2j}-\mu_{2j-1})^{2}+(\mu_{2i}-\mu_{2i-1})^{2}(\rho_{2j}+\rho_{2j-1})+(\mu_{2j}-\mu_{2j-1})^{2}(\rho_{2i}+\rho_{2i-1})]\\\
+\frac{1}{16n^{4}}\sum_{1\leq i<j\leq
n}(\rho_{2i}+\rho_{2i-1})(\rho_{2j}+\rho_{2j-1}).$ (6)

Hence,

$\mathbb{E}_{\,\boldsymbol{Z}}\left[\mathbb{V}\text{ar}_{\boldsymbol{W}_{n}}\left[\text{MSE}\,|\,\boldsymbol{Z}\right]\right]\geq\frac{1}{16n^{4}}\sum_{1\leq
i<j\leq n}(\rho_{2i}+\rho_{2i-1})(\rho_{2j}+\rho_{2j-1})\\\
=\frac{1}{32n^{4}}\sum_{i,j\in\\{1,\ldots,n\\}}(\rho_{2i}+\rho_{2i-1})(\rho_{2j}+\rho_{2j-1})+O(1/n^{3})=\frac{1}{32n^{4}}(\boldsymbol{1}_{2n}^{\top}\boldsymbol{\rho})^{2}+O(1/n^{3})=\frac{\bar{\rho}^{2}}{8n^{2}}+o(1/n^{2}).$
(7)

Consider now a block design with $B$ blocks and recall that
$\boldsymbol{W}_{B}$ is a random allocation from this design. The vector
$\boldsymbol{W}_{B}$ can be thought of as a mixture over pairwise designs in
the following way. Let $2n_{B}$ be the number of subjects in each block. Let
$P_{b}$ be a random partition of the $2n_{B}$ subjects into $n_{B}$ pairs for
block $b$. A random partition is then $P_{J}:=P_{1}\times
P_{2}\times\ldots\times P_{B}$. Each random partition produces $n$ pairwise
matches. Then

$\displaystyle\mathbb{V}\text{ar}_{\boldsymbol{W}_{B}}\left[\text{MSE}\,|\,\boldsymbol{Z}\right]$
$\displaystyle=\mathbb{E}_{\,P_{J}}\left[\mathbb{V}\text{ar}_{\boldsymbol{W}_{B}}\left[\text{MSE}\,|\,\boldsymbol{Z},P_{J}\right]\,|\,\boldsymbol{Z}\right]+\mathbb{V}\text{ar}_{P_{J}}\left[\mathbb{E}_{\,\boldsymbol{W}_{B}}\left[\text{MSE}\,|\,\boldsymbol{Z},P_{J}\right]\,|\,\boldsymbol{Z}\right]$
$\displaystyle\geq\mathbb{E}_{\,P_{j}}\left[\mathbb{V}\text{ar}_{\boldsymbol{W}_{B}}\left[\text{MSE}\,|\,\boldsymbol{Z},P_{J}\right]\,|\,\boldsymbol{Z}\right]$

and therefore,

$\mathbb{E}_{\,Z}\left[\mathbb{V}\text{ar}_{\boldsymbol{W}_{B}}\left[\text{MSE}\,|\,\boldsymbol{Z}\right]\right]\geq\mathbb{E}_{\,Z}\left[\mathbb{E}_{\,P_{J}}\left[\mathbb{V}\text{ar}_{\boldsymbol{W}_{B}}\left[\text{MSE}\,|\,\boldsymbol{Z},P_{J}\right]\,|\,\boldsymbol{Z}\right]\right]=\mathbb{E}_{\,Z,P_{J}}\left[\mathbb{V}\text{ar}_{\boldsymbol{W}_{B}}\left[\text{MSE}\,|\,\boldsymbol{Z},P_{J}\right]\right].$

Since given $P_{J}$, $\boldsymbol{W}_{B}$ is a PM design, Equation 7 implies
that for every $P_{J}$

$\mathbb{E}_{\,Z}\left[\mathbb{V}\text{ar}_{\boldsymbol{W}_{B}}\left[\text{MSE}\,|\,\boldsymbol{Z},P_{J}\right]\,|\,P_{J}\right]\geq\frac{\bar{\rho}^{2}}{8n^{2}}+o(1/n^{2}),$

which completes the proof of the part (a) because

$\mathbb{E}_{\,P_{J}}\left[\mathbb{E}_{\,Z}\left[\mathbb{V}\text{ar}_{\boldsymbol{W}_{B}}\left[\text{MSE}\,|\,\boldsymbol{Z},P_{J}\right]\,|\,P_{J}\right]\right]=\mathbb{E}_{\,Z,P_{J}}\left[\mathbb{V}\text{ar}_{\boldsymbol{W}_{B}}\left[\text{MSE}\,|\,\boldsymbol{Z},P_{J}\right]\right].$

#### Proof of part (b)

Consider the variance decomposition in Equation 4. Theorem 3.4 of our previous
paper implies that if the fourth moment of $Z_{i}$ is bounded (Assumption 3.1)
then for PM

$\mathbb{V}\text{ar}_{\boldsymbol{Z}}\left[\mathbb{E}_{\,\boldsymbol{W}_{n}}\left[\text{MSE}\,|\,\boldsymbol{Z}\right]\right]=O(1/n^{3}).$

Hence, when multiplying by $n^{2}$ this term vanishes.

Consider now
$\mathbb{E}_{\,\boldsymbol{Z}}\left[\mathbb{V}\text{ar}_{\boldsymbol{W}_{n}}\left[\text{MSE}\,|\,\boldsymbol{Z}\right]\right]$.
By Equation 6,

$\displaystyle
n^{2}\mathbb{E}_{\,\boldsymbol{Z}}\left[\mathbb{V}\text{ar}_{\boldsymbol{W}_{n}}\left[\text{MSE}\,|\,\boldsymbol{Z}\right]\right]$
$\displaystyle=$ $\displaystyle\frac{1}{16n^{2}}\sum_{1\leq i<j\leq
n}(\mu_{2i}-\mu_{2i-1})^{2}(\mu_{2j}-\mu_{2j-1})^{2}+$ (10)
$\displaystyle\frac{n-1}{8n^{2}}\sum_{i=1}^{n}(\mu_{2i}-\mu_{2i-1})^{2}(\rho_{2i}+\rho_{2i-1})+$
$\displaystyle\frac{1}{16n^{2}}\sum_{1\leq i<j\leq
n}(\rho_{2i}+\rho_{2i-1})(\rho_{2j}+\rho_{2j-1}).$

The term in Equation 10 vanishes asymptotically because

$\displaystyle\frac{1}{n^{2}}\sum_{1\leq i<j\leq
n}(\mu_{2i}-\mu_{2i-1})^{2}(\mu_{2j}-\mu_{2j-1})^{2}$
$\displaystyle\leq\frac{2}{n^{2}}\sum_{i=1}^{n}\sum_{j=1}^{n}(\mu_{2i}-\mu_{2i-1})^{2}(\mu_{2j}-\mu_{2j-1})^{2}$
$\displaystyle=2\left(\frac{1}{n}\sum_{i=1}^{n}(\mu_{2i}-\mu_{2i-1})^{2}\right)^{2}$

which goes to 0 by the assumption that
$\frac{1}{n}\sum_{i=1}^{n}(\mu_{2i}-\mu_{2i-1})^{2}\to 0$. The term in
Equation 10 vanishes because we assumed that
$\frac{1}{n}\sum_{i=1}^{n}(\mu_{2i}-\mu_{2i-1})^{2}\to 0$ and that the
$\rho$’s are bounded. Thus, the dominant term is in Equation 10, and it is
equal to

$\displaystyle\footnotesize\frac{1}{16n^{2}}\sum_{1\leq i<j\leq
n}(\rho_{2i}+\rho_{2i-1})(\rho_{2j}+\rho_{2j-1})$ $\displaystyle=$
$\displaystyle\frac{1}{32n^{2}}\sum_{i,j\in\\{1,\ldots,n\\}}(\rho_{2i}+\rho_{2i-1})(\rho_{2j}+\rho_{2j-1})+O\left(n^{-1}\right)$
$\displaystyle=$
$\displaystyle\frac{1}{8}\left(\frac{1}{2n}\sum_{i=1}^{2n}\rho_{i}\right)^{2}+O\left(n^{-1}\right)$
$\displaystyle=$ $\displaystyle\frac{\bar{\rho}^{2}}{8}+o(1),$

thereby completing the proof. ∎

###  A.4 The variance of the MSE under PB

Consider $\boldsymbol{w}_{*}$ and its mirror $-\boldsymbol{w}_{*}$, vectors
that both uniquely minimize
$|(\boldsymbol{\mu}_{T}+\boldsymbol{\mu}_{C})^{\top}\boldsymbol{w}|$. The PB
design is composed of the random variable $\boldsymbol{W}$ that draws
$\boldsymbol{w}_{*}$ and $-\boldsymbol{w}_{*}$ each with probability 1/2.
Thus, conditional on $\boldsymbol{Z}$,

$\text{MSE}:=(\hat{\tau}-\tau)^{2}=\frac{1}{4n^{2}}\left(\boldsymbol{W}^{\top}\left(\boldsymbol{Y}_{T}+\boldsymbol{Y}_{C}\right)\right)^{2}$

is constant implying that
$\mathbb{V}\text{ar}_{\boldsymbol{W}}\left[\text{MSE}\,|\,\boldsymbol{Z}\right]=0$.
The decomposition of the variance of the MSE (Equation 4) is thus only

$\mathbb{V}\text{ar}_{\boldsymbol{Z},\boldsymbol{W}}\left[\text{MSE}\right]=\mathbb{V}\text{ar}_{\boldsymbol{Z}}\left[\mathbb{E}_{\,\boldsymbol{W}}\left[\text{MSE}\,|\,\boldsymbol{Z}\right]\right].$

This expression was computed in Sections 3.3.3 and A.9 of Azriel et al.,
(2023) where it was shown that under Assumptions 3.1, 3.2 and 3.3,

$\mathbb{V}\text{ar}_{\boldsymbol{Z}}\left[\mathbb{E}_{\,\boldsymbol{W}}\left[\text{MSE}\,|\,\boldsymbol{Z}\right]\right]=\frac{1}{16n^{4}}\left(O(n)+2\left(\sum_{i=1}^{2n}\rho_{i}\right)^{2}\right)=\frac{1}{16n^{4}}\left(O(n)+8n^{2}\left(\bar{\rho}^{2}\right)\right).$

It follows that under PB,

$\displaystyle\lim_{n\to\infty}n^{2}\,\mathbb{V}\text{ar}_{\boldsymbol{W}_{n},\boldsymbol{Z}_{T},\boldsymbol{Z}_{C}}\left[(\hat{\tau}-\tau)^{2}\right]=\frac{\bar{\rho}^{2}}{2}.$


\begin{align}\label{e:l7_c_premise_derivative}
&-\int_{z^r}\beta \gamma \lambda(\theta(z))\frac{d(M(z)-W^U(z))}{d\gamma}dF(z) \geq \frac{\beta F(z^r)}{1-\beta \gamma}(R-W^s)\non \\
&  +\frac{1}{1-\beta \gamma F(z^r)}\left(\int_{z^r} \lambda(\theta(z))(1-\eta)(M(z)-W^U(z))dF(z)+\beta c\right)>0.
\end{align}

Using the above expressions we turn to investigate the implications of assuming $d(W^s-R)/d\gamma>0$ for $\frac{d\Exp[M(z)-W^U(z)]}{d\gamma}$. We can rewrite (<ref>), bringing next period's continuation values to the LHS, as

\begin{align*}
(1-\beta)\Exp[M(z)-W^U(z)]=&\int_{z^r} z-b - \beta \lambda(\theta(z))(1-\eta)(M(z)-W^U(z))dF(z) \non \\
&  + \int_{z^s}^{z^r} z-b + \beta (W^s-R)dF(z) \non \\
&  + \int^{z^s} z-b + \beta (W^s-R)-\beta (M(z)-W^s)dF(z).
\end{align*}

Taking derivatives with respect to $\gamma$, we find

\begin{align}\label{e:l7_em-wu_c_derivative}
(1-\beta)\frac{d\Exp[M(z)-W^U(z)]}{d\gamma}=&- \int_{z^r}\beta\lambda(\theta(z))(1-\eta)\frac{d(M(z)-W^U(z))}{d\gamma}dF(z) \non \\
&  + \int_{z^s}^{z^r} \beta \frac{d(W^s-R)}{d\gamma}dF(z) \non \\
&  +  \int^{z^s} \beta \Big(\frac{d(W^s-R)}{d\gamma}- \frac{d(M(z)-W^s)}{d\gamma}  \Big)dF(z),
\end{align}

where the first term is positive by virtue of (<ref>) and the second term is positive by assumption. For the third term it holds that

\begin{align*}
\frac{d(M(z)-W^s)}{d\gamma}=&(1-\gamma)\frac{d\Exp[M(z)-W^U(z)]}{d\gamma}+\gamma \beta \frac{d(W^s-R)}{d\gamma}  +(z-b+\beta (W^s-R)-\Exp[M(z)-W^U(z)]).
\end{align*}

Substituting out this expression in the third line of the RHS of (<ref>) and re-arranging implies that $\frac{d\Exp[M(z)-W^U(z)]}{d\gamma}>0$.

From $M(z)-W^U(z)=(1-\gamma)\Exp[M(z)-W^U(z)]+\gamma(z-b +\beta(1-\lambda(\theta(z))(1-\eta))(M(z)-W^U(z))$, it follows that for $z>z^r$

\begin{align}
\beta \gamma \lambda(\theta) \frac{dM(z)-W^U(z)}{d\gamma}=& \frac{\beta \gamma \lambda(\theta(z))}{1-\beta \gamma (1-\lambda(\theta(z)))}\bigg(\Big(z-b +\beta(1-\lambda(\theta(z))(1-\eta))(M(z)-W^U(z))\non \\
& \qquad \qquad -\Exp[M(z)-W^U(z)]\Big)+(1-\gamma)\frac{d\Exp[M(z)-W^U(z)]}{d\gamma} \bigg), \label{e:l7_c_M(y)-w^u(y)_derivative}
\end{align}

where we have used (<ref>) and (<ref>). Integrating this term over all $z>z^r$, we have

\begin{align}
\int_{z^r}  \beta \gamma \lambda(\theta(z))\frac{d(M(z)-W^U(z))}{d\gamma}dF(z)&\geq
\frac{\beta \gamma \lambda(\theta(z^r))}{1-\beta \gamma (1- \lambda(\theta(z^r)))} \bigg(\int_{z^r} (1-\gamma)\frac{d\Exp[M(z)-W^U(z)]}{d\gamma}dF(z) \non \\
&   + \frac{1}{\gamma}\int_{z^r} (M(z)-W^U(z)-\Exp[M(z)-W^U(z)])dF(z)\bigg) > 0, \label{e:l7_c_int derivative m(y)-w^u}
\end{align}

where the last inequality follows from the fact that $M(z)-W^U(z)-\Exp[M(z)-W^U(z)]$ and $\frac{\beta \lambda(\theta(z))}{1-\beta\gamma+\beta \gamma \lambda(\theta(z))}$ are increasing in $z$. Then $\int_{z^r} (M(z)-W^U(z)-\Exp[M(z)-W^U(z)])dF(z)>0$ and hence the LHS of (<ref>) is positive as stated, contradicting our premise in (<ref>). Equations (<ref>) and (<ref>) then imply that $\frac{d (z^r(\gamma)-z^s(\gamma))}{d \gamma}>0$ when $z^r>z^s$.

Next we turn to investigate the implications of assuming $d(W^s-R)/d\gamma>0$ on $\frac{d\Exp[M(z)-W^U(y)]}{d\gamma}$ for the case in which $W^s>R$ to obtain a contradiction. Here a relationship between $\frac{d(M(z)-W^U(z))}{d\gamma}$ and $\frac{d\Exp[M(z)-W^U(z)]}{d\gamma}$ can be derived directly:

\begin{align}\label{e:l7_em-wu_c_derivative_2}
(1-\beta)\frac{d\Exp[M(z)-W^U(z)]}{d\gamma}=&-\beta \int_{z^r}\lambda(\theta(z))\frac{d(M(z)-W^U(z))}{d\gamma}dF(z).
\end{align}

Using the above and (<ref>) we obtain that

\begin{align*}
-(1-\beta)\frac{d\Exp[M(z)-W^U(z)]}{d\gamma}=& \int_{z^s}\bigg(\frac{\beta \gamma \lambda(\theta(z))}{1-\beta \gamma (1-\lambda(\theta(z)))}\bigg(\Big(z-b +\beta(1-\lambda(\theta(z))(1-\eta))(M(z)-W^U(z))\non \\
& \qquad \qquad -\Exp[M(z)-W^U(z)]\Big)+(1-\gamma)\frac{d\Exp[M(z)-W^U(z)]}{d\gamma}\bigg)\bigg)dF(z),
\end{align*}

which in turn can be expressed as

\begin{align}\label{e:l7_c_M(y)-w^u(y)_derivative_3}
\frac{d\Exp[M(z)-W^U(z)]}{d\gamma}&\Bigg((1-\beta) +\frac{F(z^s)\beta \gamma \lambda(\theta(z))(1-\gamma)}{1-\beta\gamma+\beta \gamma \lambda(\theta(z))}\Bigg)= \non \\ & \qquad -\int_{z^s}\bigg(\frac{\beta \gamma \lambda(\theta(z))}{1-\beta \gamma (1-\lambda(\theta(z)))}\Big(z-b +\beta(1-\lambda(\theta(z))(1-\eta))(M(z)-W^U(z))  \non \\
& \qquad -\Exp[M(z)-W^U(z)]\Big)\Big)dF(z) < 0.
\end{align}

From (<ref>), it then follows that $\frac{d\Exp[M(z)-W^U(z)]}{d\gamma}<0$. Using equation (<ref>), we obtain that $W^s-R$ is decreasing in $\gamma$, where

\begin{align*}
\frac{d(W^  s-R)}{d\gamma}=\frac{d(W^s-\Exp[W^U(z)])}{d\gamma}=-\frac{1}{1-\beta}\int_{z^s}\gamma \lambda(\theta(z)) \frac{d(M(z)-W^U(z))}{d\gamma}<0,
\end{align*}

which leads to our required contradiction. Equation (<ref>) then imply that $\frac{d (z^r(\gamma)-z^s(\gamma))}{d\gamma}>0$ also when $z^s>z^r$. This complete the proof for Lemma H.1.

Proof of Lemma 2
Using the same setting as in Lemma H.1 we now introduce human capital $x$, assuming it enters in a multiplicative way in the production function. Keeping the same notation as in Lemma H.1, let $A=1$ such that total output is given by $zx$. Without loss of generality for the results derived in this lemma, normalize $x=1$. If we have an incremental improvement in $x$ that is occupational specific, the value of sampling will stay constant, at $R=\Exp[W^U(1,z)]-c$. However, the value of $W^s(x)$ will increases with $x$. Since $W^s(x)=(1-\gamma)\Exp[W^U(x,z)]+\gamma(b+\beta \max\{R, W^s(x)\})$ it follow that $W^s(x)$ is increasing in $x$ through $\Exp[W^U(x,z)]$.

To investigate the dependence between $W^s(x)$ and $\Exp[W^U(x,z)]$ when $x$ changes we first suppose that $R\geq W^s(x)$. The value of unemployment when $z\geq z^r(x)$ is given by

\begin{align*}
W^U(x,z)&=(1-\gamma)\Exp[W^U(x,z)]+\gamma(b+\beta\lambda(\theta(x,z)))(1-\eta)(M(x,z)-W^U(x,z))+\beta W^U(x,z)),
\end{align*}

while for $z^r(x)>z$ it is given by

\begin{align*}
W^s(x)&=(1-\gamma)\Exp[W^U(x,z)]+\gamma(b+\beta R).
\end{align*}

When comparing the expected value of separating with the expected value of moving to another occupations (reseting $x=1$), the difference is given by

\begin{align*}
W^s(x)-\Exp[W^U(1,z)]& = (1-\gamma) \Exp[W^U(x,z)]+C_{4},
\end{align*}

where $C_{4}$ denotes those terms that are constant in $x$.

As a result, $\frac{d(W^s(x)-\Exp[W^U(1,z)])}{dx}=(1-\gamma) \frac{d\Exp[W^U(x,z)]}{dx}$, where $\Exp[W^U(x,z)]$ can be expressed as

\begin{align}
\Exp[W^U(x,z)]=F(z^r(x))(b+\beta R)+\int_{z^r(x)} \Big[b+\beta \lambda(\theta(x,z))(1-\eta)(M(x,z)-W^U(x,z)) + \beta W^U(x,z)\Big]dF(z). \non
\end{align}

Using the expression $W^U(x,z)$, it then follows that

\begin{align*}
& \left(1- \frac{\beta(1-\gamma)}{1-\beta \gamma}(1-F(z^r(x)))\right)\Exp[W^U(x,z)] \non \\
& \qquad=F(z^r(x))(b+\beta R) + \frac{1-F(z^r(x))}{1-\beta \gamma} b + \int_{z^r(x)}\frac{\beta\lambda(\theta(x,z))(1-\eta)(M(x,z)-W^U(x,z))}{1-\beta \gamma}dF(z).
\end{align*}

Taking the derivative with respect to $x$ and using the envelope condition, which implies that the term premultiplying $dz^r(x)/dx$ equal zero, yields

\begin{align}\label{e:l7_x_dew^u/dx}
&\frac{d\Exp[W^U(x,z)]}{dx}= \frac{\beta\frac{d}{dx}\big(\int_{z^r(x)} [\lambda(\theta(x,z)) (1-\eta)(M(x,z)-W^U(x,z))]dF(z)\big)}{1-\beta(1-(1-\gamma)F(z^r(x)))}.
\end{align}

Since the denominator is positive, the sign of $d\Exp[W^U(x,z)]/dx$ is given by the sign of its numerator. By virtue of the envelope condition and equation (<ref>) in the proof of Lemma 1, the latter is given
\[\int_{z^r(x)} \beta \lambda(\theta(x,z)) \frac{d(M(x,z)-W^U(x,z))}{dx}dF(z),\]

\begin{align}
\frac{d(M(x,z)-W^U(x,z))}{dx}&=(1-\gamma)\frac{d\Exp[M(x,z)-W^U(x,z)]}{dx}+(1-\gamma)(z-\Exp[z])+\gamma z \non \\&
\qquad \qquad  \qquad + \beta \gamma (1-\lambda(\theta(x,z)))\frac{d(M(x,z)-W^U(x,z))}{dx}. \label{e:l7_dm-w^u/dx_y greater yr}
\end{align}

Hence the numerator of (<ref>) is given by

\begin{align}\label{e:derv_num}
\int_{z^r(x)}\left(\frac{\beta \lambda(\theta(x,z))(1-\gamma)}{1-\beta \gamma (1-\lambda(\theta(x,z)))}\left(\frac{d\Exp[M(x,z)-W^U(x,z)]}{dx}+z-\Exp[z]\right)+\frac{\beta \lambda(\theta(x,z)) \gamma }{1-\beta \gamma (1-\lambda(\theta(x,z)))}z \ \right) \ dF(z).
\end{align}

It is then clear that the sign of $d\Exp[W^U(x,z)]/dx$ is the same as the sign of $d\Exp[M(x,z)-W^U(x,z)]/dx$. To investigate the latter note that

\begin{align}\label{e:l7_x_expected surplus full}
\Exp[M(x,z)-W^U(x,z)]&=\int_{\underline{z}}^{\bar{z}} (xz-b) dF(z) + \int_{z^r(x)} \beta \lambda(\theta(x,z))(1-\eta)(M(x,z)-W^U(x,z))dF(z)  \non \\
&\ \  +\int_{z^s(x)}^{z^r(x)}\beta (M(x,z)-W^s(z))dF(z) +  \int^{z^r(x)}\beta(W^s(x)-R)dF(z).
\end{align}

We will now take the derivative of this expression with respect to $x$ to investigate its sign. For this purpose it is useful to note that

\begin{align*}
\int_{z^s(x)}^{z^r(x)} \frac{\beta d(M(x,y)-W^s(x))}{dx} dF(z)&= \beta \int_{z^s(x)}^{z^r(x)} \Big [(1-\gamma)\frac{d\Exp[M(x,y)-W^U(x,y)]}{dx}+(1-\gamma)(y-\Exp[y])+\gamma y \non \\
&  \qquad \qquad + \beta \gamma \frac{d(M(x,y)-W^s(x))}{dx} +\beta \gamma \frac{d(W^s(x)-R)}{dx} \Big ]dF(z),
\end{align*}

and that

\begin{align}
\int^{z^r(x)}\frac{\beta d(W^s(x)-R))}{dx} dF(z)&=\frac{\beta(1-\gamma)F(z^r(x))}{1-\beta(1-(1-\gamma)F(z^r(x)))} \times  \label{e:l7_dm-w^u/dx_y smaller ys} \\
& \ \ \int_{z^r}\bigg [ \frac{\beta \lambda(\theta(x,z))(1-\gamma)}{1-\beta \gamma (1-\lambda(\theta(x,z)))}\left(\frac{d\Exp[M(x,z)-W^U(x,z)]}{dx}+z-\Exp[z]\right) \non \\
&+\frac{\beta \lambda(\theta(x,z)) \gamma }{1-\beta \gamma (1-\lambda(\theta(x,z)))}z \bigg]dF(z). \non
\end{align}

Using (<ref>) and the above equations we obtain that  $\frac{d\Exp[M(x,z)-W^U(x,z)]}{dx}=$

\begin{align}
&\Exp(z)+ \int_{z^r(x)}\left(\frac{\beta \lambda(\theta(x,z))(1-\gamma)}{1-\beta \gamma (1-\lambda(\theta(x,z)))}\left(\frac{d\Exp[M(x,z)-W^U(x,z)]}{dx}+z-\Exp[z]\right)+\frac{\beta \lambda(\theta(x,z)) \gamma }{1-\beta \gamma (1-\lambda(\theta(x,z)))}z \ \right)dF(z) \non \\
&+ \frac{\beta}{1-\beta\gamma}  \int_{z^s(x)}^{z^r(x)} \Big[(1-\gamma)\left(\frac{d\Exp[M(x,z)-W^U(x,z)]}{dx}+z-\Exp[z]\right)  +\gamma z \Big]dF(z)\non \\
&+\left(\frac{\beta}{1-\beta \gamma}\frac{ (1-\gamma)F(z^r(x))}{1-\beta(1- (1-\gamma)F(z^r(x)))} \times \right. \label{e:l7_dm-w^u/dx_y between ys and yr} \\
& \ \ \left. \int_{z^r(x)}\left(\frac{\beta \lambda(\theta(x,z))(1-\gamma)}{1-\beta \gamma (1-\lambda(\theta(x,z)))}\left(\frac{d\Exp[M(x,z)-W^U(x,z)]}{dx}+z-\Exp[z]\right)+\frac{\beta \lambda(\theta(x,z)) \gamma }{1-\beta \gamma (1-\lambda(\theta(x,z)))}z \ \right) \ dF(z)\right). \non
\end{align}

The next step is to investigate whether the sum of all terms premultiplying $\frac{d\Exp[M(x,z)-W^U(x,z)]}{dx}$ in (<ref>) is less than 1. If this is the case, grouping all these terms and solving for $d\Exp[M(x,z)-W^U(x,z)]/dx$ will imply that $d\Exp[M(x,z)-W^U(x,z)]/dx>0$ as the reminder terms in the RHS of (<ref>) are positive because the integrating terms $z-\Exp[z]$ will also yield a positive term.

We proceed by noting that the terms premultiplying $\frac{d\Exp[M(x,z)-W^U(x,z)]}{dx}$ in the last three lines of (<ref>) are larger than in (<ref>). By replacing the premultiplication term in (<ref>) with the corresponding term in (<ref>) we will show that the entire term premultiplying $\frac{d\Exp[M(x,z)-W^U(x,z)]}{dx}$ in (<ref>) is less than one.
Some algebra establishes that to show the latter we need to verify that

\begin{align}\label{e:l7_desideratum}
\beta \left(\frac{d(M(x,y)-W^U(x,y))}{dx}+\frac{d(W^s-R)}{dx}\right)F(z^r(x))<1-\beta(1-\gamma)(1-F(z^r(x))).
\end{align}

By collecting the terms premultiplying $\frac{d\Exp [M(x,z) - W^U(x,z)] }{dx}+ z-\Exp[z]$, and substituting these into the LHS of (<ref>), we obtain that

\begin{align}
+\frac{\beta(1-\gamma)(\beta(1-\gamma)(1-F(z^r(x))))}{(1-\gamma\beta)(1-\beta+\beta(1-\gamma)F(z^r(x)))} \right) \non \\
& \quad = \frac{\beta(1-\gamma)(1-\beta+\beta(1-\gamma))}{(1-\gamma\beta)(1-\beta+\beta(1-\gamma)F(z^r(x)))}F(z^r(x)). \label{e:l7_x_toprove_LHS}
\end{align}

The RHS of (<ref>) can be rewritten as $1-\beta+\beta \gamma+\beta(1-\gamma)F(z^r(x))$. Noting that

\begin{align}
\beta \gamma&> \frac{\beta \gamma (\beta(1-\gamma))\Big(1-\beta+\beta(1-\gamma)\Big)F(z^r(x))}{(1-\gamma \beta)(1-\beta+\beta (1-\gamma) F(z^r(x)))}\label{e:l7_x_addup1}\\
\beta(1-\gamma)F(z^r(x))&>\frac{\beta(1-\gamma)(1-\gamma \beta)\big(1-\beta+\beta(1-\gamma)\big)F(z^r(x))}{(1-\gamma \beta)(1-\beta+\beta F(z^r(x)))}, \label{e:l7_x_addup2}
\end{align}

and adding them up we find that the RHS is precisely the term in (<ref>). Therefore $\beta \gamma + \beta(1-\gamma)F(z^r(x))$ is larger than (<ref>), from which the desired result follows as the remaining term, $1-\beta$, is larger than zero and the desired inequality is slack. This yields $d\Exp [M(x,z) - W^U(x,z)]/dx>0$. It then follows from (<ref>) that $d(M(x,z)-W^U(x,z))/dx>0$ and therefore, by (<ref>), that $d\Exp[W^U(x,z)]/dx>0$ and $d(W^s(x)-R)/dx>0$.

We now need to consider the case in which $W^s(x)>R$. Here we once again obtain that

\[
\frac{d(W^s(x)-R)}{dx}=(1-\gamma)\frac{d\Exp[W^U(x,z)]}{dx},
\]

\begin{align}
(1-\beta)\frac{d\Exp[W^U(x,z)]}{dx}=\int_{z^s(x)} \beta \lambda(\theta(x,z))\frac{d(M(x,z)-W^U(x,z))}{dx}dF(z) \label{e:l7_x_case2_1}
\end{align}

\begin{align}
\frac{d(M(x,z)-W^U(x,z))}{dx}&=(1-\gamma)\frac{d\Exp[M(x,z)-W^U(x,z)]}{dx}+(1-\gamma)(\Exp[z]-z) \non \\
&\qquad \qquad +\gamma(z +\beta (1-\lambda(\theta(x,z))))\left(\frac{d(M(x,z)-W^U(x,z))}{dx}\right),\label{e:l7_x_case2_2}
\end{align}

while the expected surplus evolves according to

\begin{align}\label{e:l7_x_case2_3}
\frac{d\Exp[M(x,z)-W^U(x,z)]}{dx}&= \int_{z^s(x)}z +\beta (1-\lambda(\theta(x,z)))\frac{d(M(x,z)-W^U(x,z))}{dx}.
\end{align}

Substituting (<ref>) into (<ref>), it follows that $\frac{d\Exp[M(x,z)-W^U(x,z)]}{dx}>0$, from which in turn it follows that (<ref>) is also positive.

Finally, we investigate the implications of a change in $x$ on $z^s(x)$ and $z^r(x)$. When $z^r(x)>z^s(x)$, these reservation cutoff functions are given by

\begin{align*}
M(x,z^s(x))-W^s(x)&=0 \\
\lambda(\theta(x,z^r(x)))(1-\eta)(M(x,z^r(x))-W^U(x,z^r(x)))+(W^s(x)-R)&=0.
\end{align*}

Further we can obtain that

\begin{align*}
M(x,z^s(x))-W^s(x)&=x z^s(x)-b+\beta (1-\gamma)\Exp[\max\{M(x,z)-W^U(x,z), W^s(x)-R\}]\non \\
& \qquad \qquad +\beta \gamma (W^s(x)-R) \\
M(x,z^r(x))-W^s(x)&=x z^r(x)-b+\beta (1-\gamma)\Exp[\max\{M(x,z)-W^U(x,z), W^s-R\}]\non \\
& \qquad \qquad +\beta \gamma (1-\lambda(\theta(x,z^r(x))(1-\eta)(M(x,z^r(x))-W^s(x)).
\end{align*}

Taking derivatives with respect to $x$ we find that

\begin{align*}
&  z^s(x)+\beta(1-\gamma) \frac{d}{dx}\Big(\Exp[\max\{M(x,z)-W^U(x,z), W^s(x)-R\}]\Big)+ \beta \gamma \frac{d(W^s(x)-R)}{dx}+ x\frac{d z^s(x)}{dx}=0 \\
& \frac{\lambda(\theta(x,z))}{1-\beta \gamma (1-\lambda(\theta(x,z)))}\bigg(z^r(x)+\beta(1-\gamma) \frac{d}{dx}\Big(\Exp[\max\{M(x,z)-W^U(x,z), W^s(x)-R\}]\Big)+x\frac{dz^r(x)}{dx}\bigg) \non \\
& \qquad + \frac{d(W^s(x)-R)}{dx}=0
\end{align*}

Since $\frac{d(W^s(x)-R)}{dx}>0$, this implies that

\begin{align}
z^s(x)+x\frac{d z^s(x)}{dx}\geq z^r(x)+x\frac{d z^r(x)}{dx}+ \frac{1-\beta \gamma }{\lambda(\theta(x,z))}\frac{d(W^s(x)-R)}{dx},
\end{align}

which implies that, evaluated at $x=1$,

\[\frac{d z^s(x)}{dx}-\frac{d z^r(x)}{dx}>z^r(x)-z^s(x).\]

The above result then yields that for $z^r>z^s$, more occupational human capital brings closer together the two cutoffs. For $z^r<z^s$, it holds in this simplified setting that $z^r$ jumps to the corner, $z^r=\underline{z}$, while $z^s$ decreases with $x$. This completes the proof of Lemma 2.

Proof of Lemma 3

To proof this lemma we use the equations (<ref>) - (<ref>), where we have assumed no human capital accumulation. Further, to simplify we let $\gamma=1$ such that the $z$-productivity does not change. We also focus on the case in which $z^r>z^s$ such that $z^r, z^s\in(\underline{z},\bar{z})$ and without loss of generality let $\delta=0$. In this stationary environment, described by $A$ and $z$, note that at labor markets whose $z$-productivities equal $z^{r}$ it holds that

\begin{equation}
\int_{\underline{z}}^{\bar{z}}W^{U}(A,z)dF(z)-c=W^{U}(A,z^{r})+\lambda(\theta (A,z^{r}))(W^{E}(A,z^{r})-W^{U}(A,z^{r})).  \label{delay resqual}
\end{equation}

Further, the expected value of unemployment for workers with $z<z^{r}$ is given by $W^{U}(A,z)=W^{U}(A,z^{r})$. This follows since over this range of $z$'s,

\[
\int_{\underline{z}}^{\bar{z}}W^{U}(A,z)dF(z)-c\geq W^{U}(A,z)+\lambda(\theta (A,z))(W^{E}(A,z)-W^{U}(A,z)))
\]

and unemployed workers prefer change occupations the period after arrival. On the other hand, the value of unemployment for workers with $z\geq z^{r}$ is given by

\begin{equation*}
W^{U}(A,z)=\frac{b+\beta \lambda (\theta (A,z))(W^{E}(A,z)-W^{U}(A,z))}{1-\beta }.
\end{equation*}

Equation (<ref>) can then be expressed as

\begin{align*}
\beta & \int_{\underline{z}}^{\bar{z}}\Big(\max \{\lambda (\theta(A,z))(W^{E}(A,z)-W^{U}(A,z)),\lambda (\theta(A,z^{r}))(W^{E}(A,z^{r})-W^{U}(A,z^{r}))\}\Big)dF(z) \\
& \quad \hspace{1cm}=\lambda (\theta(A,z^{r}))(W^{E}(A,z^{r})-W^{U}(A,z^{r}))+c(1-\beta ).
\end{align*}

Using $\eta \lambda(\theta(A,z))(W^{E}(A,z)-W^{U}(A,z))=(1-\eta )\lambda(\theta(A,z))J(A,z)=(1-\eta )\theta(A,z)k$, we have that $R(A)=W^U(A, z^r(A))$ can be expressed as

\begin{equation}
\frac{(1-\eta )k}{\eta }\Bigg(\beta \int_{\underline{z}}^{\bar{z}}\max\{\theta (A,z),\theta (A,z^{r})\}dF(z)\Bigg)-c(1-\beta )=\frac{(1-\eta )k}{\eta }\theta (A,z^{r}),  \label{res eq thetas discounted case}
\end{equation}

where the LHS describes the net benefit of moving to a different occupation and the RHS the benefit of staying in the same occupation. With this derivation we now analyse under what conditions $dz^{r}/dA>0$ and compare it to the competitive case.

To obtain the $dz^{r}/dA$ from (<ref>) we first use the free-entry condition and the Cobb-Douglas specification for the matching function to obtain an implicit function that solves for $\theta$,

\begin{equation*}
\theta (A,z)^{\eta -1}\frac{\eta (y(A,z)-b)-\beta (1-\eta )\theta (A,z)k}{1-\beta}-k\equiv E(\theta ;A,z)=0,
\end{equation*}

where differentiation then implies that $\theta $ is increasing in both $A$ and $z$,

\begin{equation*}
\frac{d\theta (A,z)}{dj}=\frac{\theta (A,z)}{w(A,z)-b}\frac{dy_{j}(A,z)}{dj}, \ \text{ for } j=A,z,
\end{equation*}

and it is straightforward to show that in this stationary environment the wage equation is given by

\begin{align*}
w(A,z)=(1-\eta )y(A,z)+\eta b+\beta (1-\eta )\theta (A,z)k.
\end{align*}

Next, to make precise the comparison with an economy in which occupations are segmented in many competitive labor markets, consider the same environment as above, with the exception that workers can match instantly with firms. As before, we assume free entry (without vacancy costs), and constant returns to scale production. This implies that every worker will earn his marginal product $y(A,z)$. Importantly, we keep the reallocation frictions the same: workers who change occupations have to forgo production for a period, and arrive at a random labor market in a different occupation at the end of the period. In the simple case of permanent productivity $(A,z)$, the value of being in a labor market with $z$, conditional on $y(A,z)>b$, is $W^{c}(A,z)=y(A,z)/(1-\beta)$, where to simplify we have not considered job destruction shocks.

Block recursiveness, given the free entry condition, is preserved and decisions are only functions of $(A,z)$. Unemployed workers optimally choose to change occupations, and the optimal policy is a reservation quality, $z^r_c$, characterised by the following equation

\begin{equation*}
\beta \int \max \{y(A,z), y(A,z^r_c)\} dF(z) + (b-c)(1-\beta) =y(A,z^r_c).
\end{equation*}

The LHS describes the net benefit of switching occupations, while the RHS the value of of staying employed earning $y$ in the (reservation) labor market.

Rearranging the above equations, the reservation $z$-productivities for the competitive and frictional case satisfy, respectively,

\begin{align*}
&b+ \beta \int_{\underline{z}}^{\bar{z}} \frac{\max \{y(A,z),y(A,z^r_c)\}}{1-\beta}dF(z)-\frac{y(A,z^r_c)}{1-\beta}-c_{c}=0 \\
&\frac{(1-\eta)k}{\eta} \left(\beta \int_{\underline{z}}^{\bar{z}} \frac{\max \{\theta(A,z), \theta(A,z^r)\}}{1-\beta}dF(z)-\frac{\theta(A,z^r)}{1-\beta}\right)-c_{s}=0.
\end{align*}

Using these equations, the response of the reservation $z$-productivity, for the competitive, and the frictional case is then given by

\begin{align*}
\frac{d z^r_c}{d A}& = \frac{\beta F(z^r_c)\frac{y_A(A,z^r_c)}{y_z(A,z^r_c)}+\beta \int_{z^r_c}^{\bar{z}} \frac{y_A(A,z)}{y_z(A,z^r_c)}dF(z)-\frac{y_A(A,z^r_c)}{y_z(A,z^r_c)}} {1-\beta F(z^r_c)} \\
\frac{d z^r}{d A}& = \frac{\beta F(z^r)\frac{y_A(A,z^r)}{y_z(A,z^r)}+\beta \int_{z^r}^{\bar{z}} \frac{\theta(A,z)(w(A,z^r)-b)}{\theta(A,z^r) (w(A,z)-b)} \frac{y_A(A,z)}{y_z(A,z^r)}dF(z)-\frac{y_A(A,z^r)}{y_z(A,z^r)}} {1-\beta F(z^r)}
\end{align*}

These are the expression shown in Lemma 3, where we have used the fact that $\frac{\theta(A,z)}{(w(A,z)-b)}\frac{(1-\eta)k}{\eta}=\frac{\lambda(\theta(A,z))}{1-\beta+\beta \lambda(\theta(A,z))}$ by virtue of

\[
\eta \frac{w(A,z)-b}{1-\beta+\beta \lambda (\theta (A,z))}=\frac{(1-\eta )k}{q(\theta (p,z))},
\]

which follows from the combination of the free entry condition and the Hosios. This completes the proof of Lemma 3.

Implications of Lemma 3

We now show two implications of Lemma 3. First we show that search frictions adds a procyclical force to occupational mobility decisions. Choosing $c_{c}, c_{s}$ appropriately such that $z^r_{c}=z^r$, the above expressions imply that $\frac{d z^r}{d A}>\frac{d z^r_c}{d A}$ if $\frac{\theta(A,z)}{w(A,z)-b}>\frac{\theta(A,z^r)}{w(A,z^r)-b}, \ \ \forall \ z>z^r$. Hence we now need to show that $\frac{\theta(A,z)}{w(A,z)-b}$ is increasing in $z$.

\begin{equation*}  \label{p2:eq2}
\frac{d\left(\frac{\theta(A,z)}{w(A,z)-b}\right)}{dz}=\frac{\theta y_z(A, z)}{(w(A,z)-b)^2}-\theta\left(\frac{(1-\eta)+(1-\eta)\beta \frac{\theta}{w(A,z)-b}k}{(w(A,z)-b)^2}\right) y_z(A,z),
\end{equation*}

which has the same sign as $\eta-(1-\eta)\beta k \frac{\theta}{w(A,z)-b}$ and the same sign as

\begin{align*}
\eta(1-\eta)&(y(A,z)-b)+\eta(1-\eta)\beta \theta k -(1-\eta)\beta \theta k
\notag \\
& \hspace{1in}= (1-\eta)(\eta(y(A,z)-b)-(1-\eta)\beta \theta k).
\end{align*}

But $\eta(y(A,z)-b)-(1-\eta)\beta \theta k=y(A,z)-w(A,z)>0$ and we have established that search frictions within labor markets make occupational mobility decisions more procyclical relative to the competitive benchmark, given the same $F(z)$ and the same initial reservation productivity $z^r=z^r_c$.

Second, we show that impact of the production function on the procyclicality of occupational mobility decisions. Here we want to show that with search frictions, if the production function is modular or supermodular (i.e. $y_{Az}\geq 0$), there exists a $c \geq 0$ under which occupational mobility decisions are procyclical. With competitive markets, if the production function is modular, occupational mobility decisions are countercyclical, for any $\beta<1$ and $c \geq 0$.

Note that modularity implies that $y_A(A,z)=y_A(A,\tilde{z}), \ \forall z>\tilde{z}$; while supermodularity implies $y_A(A,z) \geq y_A(A,\tilde{z}), \ \forall z>\tilde{z}$. Hence modularity implies

\begin{equation*}
\frac{d z^r_c}{d A}=\frac{1}{1-\beta F(z^r_c)}\frac{y_A(A,z^r_c)}{y_z(A,z^r_c)} \left(\beta F(z^r_c)+\beta \int_{z^r_c}^{\bar{z}} \frac{y_A(A,z)}{y_A(A,z^r_c)}dF(z)-1\right)<0, \ \forall \ \beta<1.
\end{equation*}

In the case with frictions,

\begin{equation*}
\frac{d z^r}{d A}=\frac{1}{1-\beta F(z^r)}\frac{y_A(A,z^r)}{y_z(A,z^r)}\left(\beta F(z^r)+\beta \int_{z^r}^{\bar{z}} \frac{\theta(A,z)(w(A,z^r)-b)}{\theta(A,z^r) (w(A,z)-b)} \frac{y_A(A,z)}{y_A(A,z^r)}dF(z)-1\right).
\end{equation*}

If we can show that the integral becomes large enough, for $c$ large enough, to dominate the other terms, we have established the claim. First note that $\frac{y_A(A,z)}{y_A(A,z^r)}$ is weakly larger than 1, for $z>z^r$ by the (super)modularity of the production function. Next consider the term $\frac{\theta(A,z)(w(A,z^r)-b)}{\theta(A,z^r) (w(A,z)-b)} $. Note that

\begin{equation*}
\lim_{z \downarrow y^{-1}(b;A)} \frac{\theta(A,z)}{w(A,z)-b}=\frac{\lambda(\theta(A,z))}{1-\beta+\beta \lambda(\theta(A,z))}=0,
\end{equation*}

because $\theta(A,z)\downarrow 0$, as $y(A,z^r) \downarrow b$. Hence, fixing a $z$ such that $y(A,z)>b$, $\frac{\theta(A,z)(w(A,z^r)-b)}{\theta(A,z^r) (w(A,z)-b)}\to \infty, \text{ as } y(a,z^r) \downarrow b $. Since this holds for any $z$ over which is integrated, the integral term becomes unboundedly large, making $d z^r/dA$ strictly positive if reservation $z^r$ is low enough. Since the integral rises continuously but slower in $z^r$ than the also continuous term $\frac{\theta(A,z^r)}{1-\beta}$, it can be readily be established that $z^r$ depends continuously on $c$, and strictly negatively so as long as $y(A,z^r)>b$ and $F(z)$ has full support. Moreover, for some $\bar{c}$ large enough, $y(A,\underline{z}^r)=b$, where $\underline{z}^r$ is a lower bound for $z^r$. Hence, as $c \uparrow \underline{z}^r$, $dz^r/dA>0$.

Job Separations Here we show the derivation of the slope of $z^s$ for the case $z^r(A)>z^s(A)$ for all $A$ described in Section C.1.2. Note that $R(A)=\frac{b+\beta \theta(A,z^r(A)) k (1-\eta)/\eta}{1-\beta}$. The derivative of this function with respect to $A$ equals

\begin{align}  \label{z^s lemma 1}
\frac{\beta k(1-\eta)}{(1-\beta)\eta}\frac{\theta}{w(A, z^r(A))-b}\left(y_A(A, z^r(A))+y_z(A, z^r(A))\frac{dz^r(A)}{dA}\right).
\end{align}

Since $w(A, z^r(A))-b=(W^E(A, z^r(A))-W^U(A,z^r(A)))(1-\beta(1-\delta)+\beta \lambda (\theta(A, z^r(A))))$ and $\frac{\theta \beta k (1-\eta)}{(1-\beta)\eta}=\beta \lambda (\theta(A,z^r(A)))(W^E(A, z^r(A))-W^U(A, z^r(A))$, we find that (<ref>) reduces to

\begin{align}  \label{z^s lemma 2}
\frac{\beta \lambda(\theta(A, z^r(A)))}{1-\beta(1-\delta)+\beta \lambda(\theta(A, z^r(A))}\left(y_A(A, z^r(A))+y_z(A, z^r(A))\frac{dz^r(A)}{dA}%
\right).
\end{align}

From the cutoff condition for separation, we find $(1-\beta)R(A)=y(A,z^{s}(A))$. Taking the derivative with respect to $A$ implies the left side equals (<ref>) and the right side equals $y_{A}(A,z^{s}(A))+y_{z}(A,z^{s}(A))\frac{dz^{s}(A)}{dA}$. Rearranging yields the equation in Section C.1.2.

§.§ Proofs of Competitive Search Model

Proof of Lemma 4

Fix any occupation $o$ and consider a firm that promised $W\geq W^{U}(A,z)$ to the worker with productivity $z$, delivers this value in such a way that his profit  $J(A,z,W)$ is maximized, i.e. solving (<ref>). Now consider an alternative offer $\hat{W}\neq W$, which is also acceptable to the unemployed worker, and likewise maximizes the profit given $\hat{W}$ for the firm, $J(A,z, \hat{W})$. Then an alternative policy that delivers $W$ by using the optimal policy for $\hat{W}$, but transfers additionally $W-\hat{W}$ to the worker in the first period must be weakly less optimal, which using the risk neutrality of the worker, results in

\begin{equation*}
J(A,z,W)\geq J(A,z,\hat{W})-(W-\hat{W})
\end{equation*}

Likewise, an analogue reasoning implies $J(A,z,\hat{W})\geq J(A,z,W)-(\hat{W}-W)$, which together with the previous equation implies

\begin{equation*}
J(A,z,W)\geq J(A,z,\hat{W})-(W-\hat{W})\geq J(A,z,W)-(\hat{W}-W)-(W-\hat{W}),
\end{equation*}

and hence it must be that $J(A,z,W)= J(A,z,\hat{W})-(W-\hat{W})$, for all $M(A,z)\geq W,\hat{W}\geq W^{U}$. Differentiability of $J$ with slope -1 follows immediately. Moreover, $M(A,z,W)=W+J(A,z,\hat{W})+\hat{W}-W=M(A,z,\hat{W})\equiv M(A,z)$. Finally, if $W^{\prime }(A^{\prime},z^{\prime}) < W^{U}(A^{\prime},z^{\prime})$ is offered tomorrow while $M(A^{\prime},z^{\prime})>W^{U}(A^{\prime},z^{\prime})$, it is a profitable deviation to offer $W^{U}(A^{\prime},z^{\prime})$, since $M(A^{\prime},z^{\prime})-W^{U}(A^{\prime},z^{\prime})=J(A^{\prime},z^{\prime},W^{U}(A^{\prime},z^{\prime}))>0$ is feasible. This completes the proof of Lemma 4.

Proof of Lemma 5

Fix any occupation $o$ and consider productivity $z$, such that $M(A,z)-W^U(A,z)>0$. Since we confine ourselves to this productivity, with known continuation values $J(A,z,W)$ and $W^{U}(A,z)$ in the production stage, we drop the dependence on $A,z$ for ease of notation. Free entry implies $k=q(\theta)J(W)\Rightarrow \frac{dW}{d\theta }<0$. Notice that it follows that the maximand of workers in (<ref>), subject to (<ref>) is continuous in $W$, and provided $M>W^{U}$, has a zero at $W=M$ and at $W=W^{U}$, and a strictly positive value for intermediate $W$: hence the problem has an interior maximum on $[W^{U},M]$. What remains to be shown is that the first order conditions are sufficient for the maximum, and the set of maximizers is singular.

Solving the worker's problem of posting an optimal value subject to tightness implied by the free entry condition yields the following first order conditions (with multiplier $\mu$):

\begin{align*}
\lambda^{\prime}(\theta)[W-W^U]-\mu q^{\prime}(\theta)J(W)&=0 \\
\lambda(\theta)-\mu q(\theta) J^{\prime}(W) &=0 \\
\end{align*}

Using the constant returns to scale property of the matching function, one has $q(\theta)=\lambda (\theta)/\theta$. This implies, combining the three equations above, to solve out $\mu$ and $J(W)$,

\begin{equation*}  \label{e:Gfunction lemma}
0=\lambda ^{\prime}(\theta)[W(\theta)-W^U]+\frac{\theta q^{\prime}(\theta)}{%
q(\theta)}k\equiv G(\theta),
\end{equation*}

where we have written $W$ as a function of $\theta$, as implied by the free entry condition. Then, one can derive $G^{\prime}(\theta)$ as

\begin{equation*}
G^{\prime}(\theta)=\lambda ^{\prime\prime}(\theta)[W(\theta)-W^U]+\lambda
^{\prime}(\theta)W^{\prime}(\theta)+ \frac{d\varepsilon_{q,\theta}(\theta)}{%
\end{equation*}

where $\varepsilon_{q,\theta}(\theta)$ denotes the elasticity of the vacancy filling rate with respect to $\theta$ and

\begin{equation*}
\frac{d\varepsilon_{q,\theta}(\theta)}{d\theta}=\frac{q^{\prime}(\theta)k}{%
\theta)^2] k}{q(\theta)^2}.
\end{equation*}

Since the first two terms in the RHS are strictly negative, $G^{\prime}$ is strictly negative when $\varepsilon_{q,\theta}(\theta)\leq 0$. The latter then guarantees there is a unique $\tilde{W}_f$ and corresponding $\theta$ that maximizes the worker's problem. This completes the proof of Lemma 5.

[29] Carrillo-Tudela, C. and L. Visschers. 2013. “Unemployment and Endogenous Reallocations Over the Business Cycle ”. IZA Working Papers No. 7124.

[57] Hagedorn, M. and I. Manovskii. 2008. “The Cyclical Behavior of Equilibrium Unemployment and Vacancies Revisited”. American Economic Review, 98 (4): 1692-1706.

[58] Hosios, A. 1991. “On the Efficiency of Matching and Related Models of Search and Unemployment”. Review of Economic Studies, 57 (2): 279-298.

[59] Menzio, G. and S. Shi. 2010. “Directed Search on the Job, Heterogeneity and Aggregate Fluctuations ”. American Economic Review, 100 (2): 327-332.

[60] Menzio, G. I. Telyukova and L. Visschers. 2016. “Directed Search Over the Life-cycle ”. Review of Economic Dynamics, 19: 38-62.

[61] Moen, E. 1997. “Competitive Search Equilibrium”. Journal of Political Economy, 105 (2): 385-411.

[62] Mortensen, D. and E. Nagypal. 2007. “More on Unemployment and Vacancy Fluctuations”. Review of Economic Dynamics, 10: 327-347.

[26] Shimer, R. 2005. “The Cyclical Behavior of Equilibrium Unemployment and Vacancies”. American Economic Review, 95 (1): 25-49.