# Black Loans Matter: Distributionally Robust Fairness for Fighting Subgroup
Discrimination

Mark Weber
IBM Research
MIT-IBM Watson AI Lab
<EMAIL_ADDRESS>
&Mikhail Yurochkin
IBM Research
MIT-IBM Watson AI Lab
<EMAIL_ADDRESS>
&Sherif Botros
Wells Fargo
<EMAIL_ADDRESS>
&Vanio Markov
Wells Fargo
<EMAIL_ADDRESS>

###### Abstract

Algorithmic fairness in lending today relies on group fairness metrics for
monitoring statistical parity across protected groups. This approach is
vulnerable to subgroup discrimination by proxy, carrying significant risks of
legal and reputational damage for lenders and blatantly unfair outcomes for
borrowers. Practical challenges arise from the many possible combinations and
subsets of protected groups. We motivate this problem against the backdrop of
historical and residual racism in the United States polluting all available
training data and raising public sensitivity to algorithimic bias. We review
the current regulatory compliance protocols for fairness in lending and
discuss their limitations relative to the contributions state-of-the-art
fairness methods may afford. We propose a solution for addressing subgroup
discrimination, while adhering to existing group fairness requirements, from
recent developments in individual fairness methods and corresponding fair
metric learning algorithms.

##  1 Introduction

Lending is a key opportunity space for artificial intelligence in banking. It
is also a domain fraught with intractable bias due to our reliance on
historical data, which is irreparably poisoned by structural and cultural
racism, past and present. This problem is particularly acute in the United
States, which continues to grapple with its racial history and the residuals
of injustice therein. Today, tens of millions of creditworthy prospective
borrowers are excluded from credit access or charged with “racial premiums” on
interest rates because their creditworthiness is determined by models failing
to disambiguate historical oppression and present merit. As a result, machine
learning can become a vehicle for perpetuating and even accelerating prejudice
in a reinforcing loop of bias training data.

In a landmark study of 3.2 million mortgage applications and 10.0 million
refinance applications from Fannie Mae and Freddie Mac, Bartlett et al. (2019)
found evidence of racial discrimination in face-to-face lending as well as in
algorithmic lending. Overall, Latinx and African-American indviduals suffered
rejection rates of greater than 60.6% versus 47.6% for everyone else.
Moreover, Latinx and African-American borrowers payed racial premiums of 7.9
and 3.6 basis points more in interest for home-purchase and refinance
mortgages, amounting to an additional $765M per annum, a staggering disparity
for modern times. Algorithmic lending was found to improve acceptance rate
parity, but it was guilty of imposing racial premiums of 5.3 basis points for
purchase mortgages and 2.0 basis points for refinance mortgages. This is the
algorithmic equivalent of reverse redlining, the unlawful predatory practice
of targeting minorities for exploitative interest rates relative to their
white counterparts. The researchers speculate this may be due to the ability
of an algorithm to discriminate on the basis of intragroup variation such as
neighborhood or shopping behavior. The fact that such discrimination can pass
the compliance protocols of lenders is the subject of this paper.

Meanwhile, the Consumer Financial Protection Bureau (CFPB) estimates 20% of
the U.S. adult population is under-served for credit and this population is
more likely to be from minority and protected groups (Bureau, 2019). These are
the so called “credit invisible” customers who are undocumented by the major
credit reporting agencies, as well as the “thin-file” customers who are
visible but whose files are either incomplete or stale for the purpose of
accurately predicting creditworthiness.

The problem of algorithmic discrimination is being raised at the highest
levels of government and society. U.S. senators Warren and Jones (2019) cited
Bartlett et al. (2019) along with other studies in a special letter to the
Board of Governors of the Federal Reserve System, the Office of the
Comptroller of the Currency, the Federal Deposit Insurance Corporation, and
the Consumer Financial Protection Bureau, with detailed admonishment to do
more to combat algorithmic lending discrimination. Amidst a resurgence of
social justice activism led by Black Lives Matter in 2020, we are especially
mindful of lending outcomes for black Americans, whose financial prospects
have been most undermined by structural and cultural prejudice, past and
present. As modern decision-making processes have become increasingly
dependent on machine learning, public backlash has spiked in numerous sectors
as people grapple with the incongruence of modern values and the historical
data skeletons unearthed by our amoral learning algorithms.

Researchers, lending practitioners, and policymakers alike should pay heed to
the zeitgeist. Predatory lending practices notwithstanding, access to
affordable credit is an important tool for extending equal opportunity to
minority households and minority-owned businesses; this is the public policy
motivation. Banks being principally motivated by profit, expansion of the
customer lending base is a business opportunity aligned with the societal
interests of financial inclusion. Add the risks of government fines and
reputational damage, which are important checks on predatory practices
disguised as inclusion, and fairness is clearly a profitability factor in
modern times.

Banking and regulation move slowly, but the field of artificial intelligence
moves fast. The purpose of this paper is to flag a key vulnerability in the
standard fairness protocols in lending, namely group fairness via statistical
parity, which we speculate may be a factor in the aforementioned algorithmic
injustices that somehow persist in the face of rigorous compliance protocols.
We evaluate the problem of subgroup discrimination and explain how recent
advances in individual fairness may have a contribution to make to the cause
of justice in lending.

##  2 Fairness in Lending

Access to affordable credit is an important factor in socioeconomic stability
and professional outcomes for individuals and households around the world. As
such, governments have enacted laws and regulations to protect consumers from
unfair discrimination when applying for credit. In the United States, the two
most relevant laws are the Fair Credit Reporting Act (FCRA) (United States
House of Representatives, 1970) and the Equal Credit Opportunity Act (ECOA)
(United States House of Representatives, 1974). ECOA is the law designed to
protect consumers against discrimination. It prohibits lenders from
discriminating based on certain protected attributes such as race, gender,
national origin, religion, age, marital status or whether the applicant
receives public assistance. There are two criteria for claiming
discrimination: disparate treatment and disparate impact. Disparate treatment
is when a lender treats a consumer differently based on a protected
characteristic such as race. Disparate impact occurs when the lender’s policy
or algorithm results in a disproportionate negative impact on a protected
group. For the purpose of this paper, we define fairness simply as the
avoidance of disparate treatment and disparate impact, but we refine this
definition to account for subgroup complexity.

###  2.1 Inside the bank

There are three key aspects to the enforcement of fairness in lending inside a
bank. The first involves the organizational structure of the bank, the second
involves the data that can be collected and considered in modeling, and the
third involves the statistical techniques used by compliance officers to
monitor fairness.

#### Separation

In adherence to current regulation, banks have internal walls between model
development and model risk, meaning model developers are actively excluded
from the process of ensuring algorithmic fairness. This is intended to prevent
model developers from gaming the system. However, this silo structure largely
prevents model developers from evaluating and using state-of-the-art fairness
algorithms, and it drives inefficiency for the bank; both undermine the
objective of producing fair algorithms.

#### Blindness

Generally, neither model developers nor compliance officers have access to
protected attributes because banks are not allowed to collect this data
(mortgage applications are an exception because applicants can volunteer some
protected information such as race). Since it is difficult to ensure fairness
for protected groups when protected attributes are unavailable, the Consumer
Financial Protection Bureau releases guidance on how to construct proxies for
race and ethnicity from public information such as census data. Specifically,
the Bureau’s Office of Research (OR) and Division of Supervision, Enforcement,
and Fair Lending (SEFL) use a method called Bayesian Improved Surname
Geocoding (BISG) to combine geography and surname-based information into a
single proxy probability for race and ethnicity (Bureau, 2014). This is a
strange policy framework: we blind ourselves from protected attributes, only
to reconstruct probabilistic proxies for those same protected attributes.

#### Group Fairness

Group fairness metrics are utilized by a bank’s risk office to compute some
group statistic for all protected groups; these should more or less match the
statistics of the majority group. These are among the most common group
fairness metrics:

  * •

Demographic parity. The distribution of outcomes for each group should be the
same. For example the percentage of loans accepted from the majority group
should be more or less the same as the percentage accepted from different
minority groups.

  * •

Equal Odds. Conditioned on the target variable (for example people who paid
their loans and people who did not), the groups should have the same
statistics. For example, for all the people who paid their loans, the
algorithm should have the same true positive, false positive, true negative
and false negative rates for all groups. Similarly for all people who did not
pay their loans. This allows for the possibility that different groups may
have different rates of default.

  * •

Equal Opportunity. This is similar to equal odds, except that we do not care
about all statistics. We only care about the positive outcomes like loan
approvals. For example, the acceptance rate for loans among the pool of
qualified applicants should be the same for all groups. While equal odds and
equal opportunities allow for more accuracy in the case when there are real
discrepancies between groups, it does not fix any historical injustice.

  * •

Prediction Rate Parity. This is another metric that is conditioned on the
prediction. For any prediction value (e.g. person will likely default or not),
the true and false rates for the different groups should match.

##  3 Subgroup Discrimination

The aforementioned group fairness metrics have a limitation: they require a
definition of the protected group (e.g. African Americans). In the real world,
identity is much more complex and heterogeneous with numerous subgroups and
subgroup combinations within and across protected groups. This has been
observed by scholars of behavioral medicine, for example, who argue that
inattention to subgroup diversity can result in disparate outcomes for
significant minority populations (Birnbaum-Weitzman, 2013). Group-level
statistical metrics can easily be manipulated by humans and (especially) by
machine learning algorithms enforcing fairness as a constrained optimization
problem. A given subgroup may be large enough to pose a legal and reputational
risk if treated unfairly while remaining sufficiently small enough to pass the
meta-group fairness metrics. We call this subgroup discrimination.

Suppose a machine learning model optimizing for accuracy within group fairness
constraints decides to use zipcode proxies for race to favor African Americans
in the wealthiest black communities in America (see “Black Type 1” in Table 1)
with extraordinarily favorable credit terms (more favorable than white
customers of the same financial means) while offering extremely unfavorable
terms to African Americans everywhere else (more unfavorable than their white
counterparts). The hypothetical values in the table show how group parity can
be satisfied even while subgroup discrimination takes place. Similar
individuals are clearly not treated similarly irrespective of race. Not only
is this problematic for the cause of true fairness, such group fairness
policies also pose serious regulatory and reputational risks to institutions
relying on them.

Consider the 2019 controversy over the Goldman Sachs credit card collaboration
with Apple, which triggered a now pending government investigation. Viral
anecdotal accounts from Twitter indicated that Goldman Sachs’ credit limit
policy discriminated against women. Reviewing the details of the claims and
Goldman Sachs’ response, we speculate the policy may have penalized homemakers
relative to their working partners by virtue of prioritizing personal income
and employment status while ignoring household-level financials. The majority
of homemakers in the United States today are female. Thus, a significant
subgroup of women may indeed have received disparate treatment, even while all
women as a protected group may have been treated with statistical parity to
men, which we may safely assume based on the fact that the policy passed
Goldman Sachs’ model risk assessments before release. This is illustrative of
our argument that it is not only the whole group that poses risk, but
sufficiently large subgroups (e.g. homemakers) within a protected meta-group.

Table 1: Simple example of subgroup discrimination, where group fairness by statistical parity is still satisfied, and where Type 1’s and Type 2’s respectively are similar to one another except for race. | Black Type 1 | Black Type 2 | White Type 1 | White Type 2
---|---|---|---|---
Acceptance Rate | 80% | 20% | 60% | 40%
Annual Percentage Rate (APR) | 10% | 30% | 25% | 15%

##  4 Algorithms for Equal Treatment Across Subgroups

Subgroup fairness has been proposed in the literature as a way to interpolate
between group and individual fairness (Hébert-Johnson et al., 2017; Kearns et
al., 2018; Kim et al., 2019). When there is a limited number of known
subgroups, it can be achieved with group fairness algorithms. However when
subgroups are not clearly defined, or there are many of them, individual
fairness is a more practical approach.

In banking, we could consider enforcing group fairness not only for a limited
set of protected attributes, e.g. race and gender, but also their
intersections. For example, achieving statistical parity on four groups
simultaneously: African-American women, Africa-American men, White women and
White men. This problem can be solved with group fairness techniques. We note
that such approach, while helpful to improve fairness overall, is unlikely to
prevent the zip code example discrimination as it does not consider low income
zip code as a subgroup. Adding “zip code” as a protected group could prevent
the problem, but it is practically difficult if not impossible to anticipate
all possible subgroups and combinations of subgroups. This problem becomes
more pronounced with the increasing number of a features being utilized by a
machine learning model in modern banking, which is optimizing for profit
within risk constraints, and may prove quite sophisticated at exotic forms of
subgroup discrimination.

Individual fairness emerges as a mechanism by which we can deal with subgroup
complexity. We will outline our algorithmic recommendations for machine
learning practitioners in banking. We will also provide a real data example
where enforcing individual fairness prevented an unaccounted latent
discrimination, while pursuing group fairness actually exacerbated it.

###  4.1 Individual fairness

We review individual fairness definitions and the recent algorithmic advances
for achieving it in practice.

Let a machine learning model be a map $h:\mathcal{X}\to\mathcal{Y}$, where
$\mathcal{X}$ and $\mathcal{Y}$ are the input and output spaces. Dwork et al.
(2011) defined individual fairness as follows:

$d_{y}(h(x_{1}),h(x_{2}))\leq Ld_{x}(x_{1},x_{2})\text{ for all
}x_{1},x_{2}\in\mathcal{X},$ (4.1)

where $d_{x}$ and $d_{y}$ are metrics on the input and output spaces and
$L\geq 0$ is a Lipschitz constant. The fair metric $d_{x}$ encodes our
intuition of which samples should be treated similarly by the machine learning
model. There are two major challenges: (i) it is not possible to provide any
practical generalization guarantees due to a requirement that the inequality
holds for all possible pairs of individuals; (ii) defining an appropriate fair
metric.

Yurochkin et al. (2020) proposed Distributionally Robust Fairness (DRF), a
distributional definition of individual fairness to address the first
challenge. They define a machine learning model $h:\mathcal{X}\to\mathcal{Y}$
as $({\epsilon},\delta)$-DRF with respect to the fair metric $d_{x}$ if and
only if

$\max\limits_{P:W(P,P_{n})\leq{\epsilon}}\int_{\mathcal{X}\times\mathcal{Y}}\ell(x,y,h)dP(x,y)\leq\delta,$
(4.2)

where $\ell:\mathcal{X}\times\mathcal{Y}\times\mathcal{H}\to{\mathbb{R}}_{+}$
is a loss function, $h\in\mathcal{H}$ is the machine learning model, $P_{n}$
is the empirical distribution of the data, ${\epsilon}>0$ is a small tolerance
parameter, and $W(P,P_{n})$ is the Wasserstein distance between distributions
$P$ and $P_{n}$ with the cost
$d((x_{1},y_{1}),(x_{2},y_{2}))=d_{x}(x_{1},x_{2})+\infty\cdot\mathbf{1}(y_{1}\neq
y_{2})$. Comparing this definition to individual fairness in (4.1), here the
loss function replaces the metric on the output space $d_{y}$ and the
tolerance parameter ${\epsilon}$ is analogous to the Lipshitz constant $L$.
The crucial difference is that DRF (4.2) considers average violations of
individual fairness making it amendable to statistical analysis establishing
generalization guarantees. DRF measures by how much the loss can increase when
considering the fair neighborhood of the observed data.

In the neighborhood redlining and reverse-redlining example, if the fair
metric $d_{x}$ considers individuals with similar household income to be
similar regardless of their zip code, where zip code can be used as a proxy
for race, DRF will raise an alarm by taking $P$ as $P_{n}$ where the zip codes
of all with high household income is set to the zip codes of those with the
low income records a significant loss increase.

Yurochkin et al. (2020) derived the dual formulation of (4.2) amendable to an
efficient training algorithm, called Sensitive Subspace Robustness (SenSR),
similar to those used in the adversarial robustness literature (Madry et al.,
2017; Sinha et al., 2017).

###  4.2 Fair metrics

In general, individual fairness does not imply group fairness, which may seem
unsuitable in the context of existing legal regulations in finance. It may
also seem that defining an appropriate fair metric requires significant
expertise, such as knowing which zip codes are more or less racially
homogeneous. Fortunately, recent literature offers a variety of ways to learn
fair metric from data, (Ilvento, 2019; Mukherjee et al., 2020; Yurochkin et
al., 2020; Wang et al., 2019) alleviating the need for the expert knowledge. A
subset of these practises can account for the information about protected
groups, bridging the gap between individual and group fairness to satisfy
existing regulations. We review two approaches.

First, consider a Mahalanobis-type fair metric of the form:

$d_{x}(x_{1},x_{2})=\langle(x_{1}-x_{2}),\Sigma(x_{1}-x_{2})\rangle,$ (4.3)

where $\Sigma$ is a positive semi-definite matrix. $\Sigma$ can control what
features should be ignored or amplified when evaluating similarity between
individuals. Yurochkin et al. (2020) proposed to construct $\Sigma$ based on
the _sensitive subspace_. This subspace contains variation in the data due to
protected attributes, such as differences between black and white individuals.
Let $V=\\{v_{1},\dots,v_{k}\\}$ be a set of _sensitive directions_ , i.e.
vectors spanning a sensitive subspace. Then $\Sigma=I-P_{V}$, where $P_{V}$ is
the projection onto the span of $V$ ($\Sigma$ is an orthocomplement
projection). Sensitive directions can be obtained by fitting linear predictors
to sensitive attributes and taking vectors orthogonal to the decision
boundary. For example, let $v$ be a vector of coefficients of a logistic
regression fitted to predict race (black or white here). Then $v$ is a
sensitive direction. An individually fair classifier trained with such a fair
metric will treat individuals of different races similarly while correctly
ignoring features in the data that correlate with race (i.e. racial proxies).
Because this fair metric accounts for the protected attribute, intuitively,
the corresponding individually fair classifier should also satisfy group
fairness, which is important for satisfying existing legal regulations. It is
then straightforward to account for multiple protected groups as well as their
subsets and intersections (i.e. subgroups).

The second approach we review also utilizes Mahalanobis-type fair metric as in
(4.3), but uses a different procedure to learn $\Sigma$. Mukherjee et al.
(2020) proposed EXPLORE, an algorithm to learn $\Sigma$ from pairs of
comparable and incomparable samples. On a high level, EXPLORE is a logistic
regression variant on input pairs. It learns $\Sigma$ such that when fair
distance is small, the corresponding logistic regression predicts
“comparable,” and when the fair distance is large it predicts “incomparable.”
Consider race as protected attribute. To bridge the gap between individual and
group fairness, they defined pairs for learning $\Sigma$ as follows: any pair
of individuals with same class label but different race are comparable; any
pair of individuals with different class label are incomparable.

Table 2: Summary of the Adult experiment from Mukherjee et al. (2020). | B-Acc,% | S-Con. | $\mathrm{Gap}_{G}^{\mathrm{RMS}}$ | $\mathrm{Gap}_{R}^{\mathrm{RMS}}$ | $\mathrm{Gap}_{G}^{\mathrm{max}}$ | $\mathrm{Gap}_{R}^{\mathrm{max}}$
---|---|---|---|---|---|---
SenSR+EXPLORE | 79.4 | .966 | .065 | .044 | .084 | .059
SenSR | 78.9 | .934 | .068 | .055 | .087 | .067
Baseline | 82.9 | .848 | .179 | .089 | .216 | .105
Adv. debiasing | 81.5 | .807 | .082 | .070 | .110 | .078

###  4.3 A case study: income prediction from Census data

To illustrate how individual fairness can prevent subgroup discrimination,
including subgroups not explicitly considered at training time and while
satisfying legal group fairness regulations, we review the experiment
considered in Yurochkin et al. (2020); Mukherjee et al. (2020). The task is to
predict individuals’ income based on the Census data, known as the Adult
dataset (Bache and Lichman, 2013) in the fairness literature. Specifically, we
discuss the performance of SenSR trained with two fair metrics discussed in
the previous section, naive training by empirical risk minimization, and one
of the prior group fairness algorithms.

The results of their experiment are summarized in Table 2. First we describe
the comparison metrics: B-Acc stands for balanced accuracy measuring
classification performance; Gap metrics measure equal odds group fairness
violations (0 is an ideal value); S-Con. stands for spouse consistency and
measures the counterfactual invariance of the classifier’s prediction when the
“relationship” feature is modified. The “relationship” feature takes values
such as “husband’,’ “wife,” and “unmarried.” This is an example of a feature
that correlates with one of the protected attributes (gender), but could be
easily overlooked at the training stage (analogous to the “zip code” feature
in our earlier example). In this experiment “relationship” was treated as any
other general (i.e. not protected) feature and thus may become the basis of an
overlooked subgroup.

Our first observation, is that enforcing group fairness may result in a
subgroup of women, e.g. unmarried women, being treated unfairly even when the
equal odds violation for gender is small. Adversarial debiasing (Zhang et al.,
2018) is one of the recent group fairness methods at our disposal: it reduces
group fairness violations in comparison to the Baseline (i.e. naive training).
However, it actually _worsens_ spouse consistency, producing a significant
subgroup fairness violation. In contrast, enforcing individual fairness with
SenSR (either using sensitive subspace or EXPLORE to obtain fair metric from
data) yields a higher spouse-consistency score and the least amount of group
fairness violations. This experiment illustrates that individual fairness is
effective for satisfying legal group fairness requirements, as well as
safeguarding against unintentional subgroup discrimination.

##  5 Recommendations

Having reviewed the subgroup discrimination vulnerability of group fairness
and the improvement opportunities individual fairness algorithms afford, we
return to the specifics of lending and the practical considerations for
implementing fair algorithms.

###  5.1 For lenders

Training an individually fair classifier consists of three stages: (i)
defining/learning a fair metric; (ii) training an individually fair model with
respect to the given fair metric; (iii) assessing fairness and performance.
The aforementioned departmental separation of model development and model risk
in banks naturally aligns with this pipeline. We recommend the risk department
take charge of (i) and (iii) and the modeling department take charge of (ii).
While defining and learning the fair metric may require protected attributes
(or proxies) to promote group fairness, the fair metric itself does not
explicitly expose protected attributes (or their proxies). This observation
suggests that it may be permissible for a risk department to provide a fair
metric for the modeling department allowing undue gamesmanship of the metrics.

On the other hand, the department separation goes against modern group
fairness algorithms. For example, Agarwal et al. (2018) proposed to formulate
group fairness as a constraint optimization problem. The constraints are
defined based on the group fairness requirements and corresponding protected
attributes (or their proxies) and need to be evaluated routinely during
training. In the context of banking, the model risk department defines group
fairness requirements, hence the constraints, but keeps these and the
protected attributes (or proxies) secret from the modelers, making it
impossible to efficiently solve the corresponding constraint optimization
problem during training. This undermines the cause of fairness and further
motivates the adoption of our recommendations for a shift to individual
fairness with the departmental delineations described above.

###  5.2 For policymakers

In a feature rich environment, machine learning models can learn a variety of
sophisticated subgroup discrimination schemes while satisfying group fairness
metrics for compliance. We therefore urge policymakers to update the
regulatory guidances to account for subgroup discrimination and the
corresponding algorithmic toolbox available to lenders. Banks should be
encouraged if not required to use state-of-the-art methods for algorithmic
fairness.

We also recommend a re-evaluation of the requirement to blind model developers
from sensitive attributes. While we provide an approach for lenders that
satisfies this constraint, the practice both limits the algorithmic fairness
toolbox for banks and drives inefficiency in the development of certifiably
fair models, which ultimately affects the people seeking fair treatment at any
given moment in time. The approach seems akin to the now debased ideology of
”color blindness,” criticized by sociologists and justice advocates as
promoting willfull ignorance of and complacence with structural and cultural
systems of racial oppression. In other words, pretending race does not exist
does not result in fair outcomes; in fact, the opposite happens because the
underlying problem of racial injustice is not properly dealt with or accounted
for. Similarly, “fairness by unawareness” in lending is susceptible to racial
discrimination because model developers can hide behind a guise of objectivity
while a machine learning model learns how to discriminate by proxy and/or by
subgroup. This topic requires further examination, but we recommend for
consideration the voluntary inclusion of one’s racial identification
information in the service of improving algorithmic fairness, where banks are
disallowed from claiming racial ignorance i.e. “color blindness.” Since the
government is already providing sophisticated racial proxies, of which the
general citizenry is likely unaware, it seems appropriate to consider
abandoning this practice in favor of a more transparent, voluntary approach
that may also yield more just outcomes for minorities.

##  6 The urgency of algorithmic fairness

We have observed that both traditional lending and algorithmic lending are
subject to racial discrimination. We have reviewed the current banking
practices on fairness in lending. We have flagged the problem of subgroup
discrimination and discussed methods to mitigate it. We have recommended
individual fairness frameworks including distributionally robust fairness
(DRF) and we have explained how they can be implemented within the current
compliance regime. We have challenged the notion that separation and blindness
are effective in promoting algorithmic fairness in lending.

The human tapestry is not as black-and-white as black and white. It is rich in
complex subgroups and combinations. No algorithm can change the history of
racial oppression in the United States, nor male privilege, nor any injustice
embedded in historical data. Nevertheless, we have a responsibility to find
ways to to make sure that each and every person is treated fairly, not just
special subsets of people, even within a protected class. Decisions made on
the basis of racially bias historical data produce racially bias results,
which in turn become the data we train on tomorrow. This threatens to
perpetuate and accelerate racial bias by propagating it into the future. This
why fairness in lending, and indeed in every part of our increasingly
algorithmic society, is not only an important issue, but an urgent one.

## Broader Impact

This work addresses the ethical and societal consequences of suboptimal
policies and practices in algorithmic fairness for lending. If correct in its
analysis, our work should benefit groups and subgroups who suffer from
prejudiced historical data affecting current lending decisions by virtue of
enabling banks to identify good prospective borrowers irrespective of
protected attributes and proxies. It should also benefit lenders who seek to
avoid legal and reputational risk by violating, or being perceived to violate,
fairness regulations and public principles in lending. This topic is extremely
complex, particularly given the racial history of the United States. Our
recommendations are measured accordingly, not as definitive solutions but as
prudent considerations for model developers, compliance officers, and policy
makers charged with ensuring fairness. Such experts should evaluate our
arguments and weigh the potential problems or unintended consequences of our
recommendations.

## References

  * Agarwal et al. [2018] Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wallach.  A Reductions Approach to Fair Classification.  _arXiv:1803.02453 [cs]_ , July 2018.
  * Bache and Lichman [2013] K. Bache and M. Lichman.  UCI machine learning repository.  2013\.
  * Bartlett et al. [2019] Robert Bartlett, Adair Morse, Richard Stanton, and Nancy Wallace.  Consumer-lending discrimination in the fintech era.  Working Paper 25943, National Bureau of Economic Research, June 2019.  URL http://www.nber.org/papers/w25943.
  * Birnbaum-Weitzman [2013] Orit Birnbaum-Weitzman.  _Minority Subgroups_ , pages 1252–1255.  Springer New York, New York, NY, 2013.  ISBN 978-1-4419-1005-9.  doi: 10.1007/978-1-4419-1005-9_1437.  URL https://doi.org/10.1007/978-1-4419-1005-9_1437.
  * Bureau [2014] Consumer Financial Protection Bureau.  Using publicly available information to proxy for unidentified race and ethnicity, 2014.
  * Bureau [2019] Consumer Financial Protection Bureau.  Who are the credit invisibles? how to help people with limited credit histories, December 2019.
  * Dwork et al. [2011] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Rich Zemel.  Fairness Through Awareness.  _arXiv:1104.3913 [cs]_ , April 2011.
  * Hébert-Johnson et al. [2017] Ursula Hébert-Johnson, Michael P Kim, Omer Reingold, and Guy N Rothblum.  Calibration for the (computationally-identifiable) masses.  _arXiv preprint arXiv:1711.08513_ , 2017.
  * Ilvento [2019] Christina Ilvento.  Metric Learning for Individual Fairness.  _arXiv:1906.00250 [cs, stat]_ , June 2019.
  * Kearns et al. [2018] Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu.  Preventing fairness gerrymandering: Auditing and learning for subgroup fairness.  In _International Conference on Machine Learning_ , pages 2564–2572, 2018.
  * Kim et al. [2019] Michael P Kim, Amirata Ghorbani, and James Zou.  Multiaccuracy: Black-box post-processing for fairness in classification.  In _Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society_ , pages 247–254, 2019.
  * Madry et al. [2017] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks.  _arXiv preprint arXiv:1706.06083_ , 2017.
  * Mukherjee et al. [2020] Debarghya Mukherjee, Mikhail Yurochkin, Moulinath Banerjee, and Yuekai Sun.  Two simple ways to learn individual fairness metrics from data.  In _International Conference on Machine Learning_ , July 2020\.
  * Sinha et al. [2017] Aman Sinha, Hongseok Namkoong, and John Duchi.  Certifying Some Distributional Robustness with Principled Adversarial Training.  _arXiv:1710.10571 [cs, stat]_ , October 2017.
  * United States House of Representatives [1970] United States House of Representatives.  _Fair Credit Reporting Act_ , volume 15 U.S.C. § 1681.  1970\.
  * United States House of Representatives [1974] United States House of Representatives.  _Equal Credit Opportunity Act_ , volume 15 U.S.C. § 1691.  1974\.
  * Wang et al. [2019] Hanchen Wang, Nina Grgic-Hlaca, Preethi Lahoti, Krishna P. Gummadi, and Adrian Weller.  An Empirical Study on Learning Fairness Metrics for COMPAS Data with Human Supervision.  _arXiv:1910.10255 [cs]_ , October 2019.
  * Warren and Jones [2019] Elizabeth Warren and Doug Jones.  Dear chairman powell, comptroller otting, chairman mcwilliams, and director kraninger, June 2019.
  * Yurochkin et al. [2020] Mikhail Yurochkin, Amanda Bower, and Yuekai Sun.  Training individually fair ml models with sensitive subspace robustness.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=B1gdkxHFDH.
  * Zhang et al. [2018] Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell.  Mitigating Unwanted Biases with Adversarial Learning.  _arXiv:1801.07593 [cs]_ , January 2018.


nameyeardelim,

# Optimal Delegation in a Multidimensional World

Andreas Kleiner Department of Economics, Arizona State University. Email:
<EMAIL_ADDRESS>
We study a model of delegation in which a principal takes a multidimensional
action and an agent has private information about a multidimensional state of
the world. The principal can design any direct mechanism, including stochastic
ones. We provide necessary and sufficient conditions for an arbitrary
mechanism to maximize the principal’s expected payoff. We also discuss simple
conditions which ensure that some convex delegation set is optimal. A key step
of our analysis shows that a mechanism is incentive compatible if and only if
its induced indirect utility is convex and lies below the agent’s first-best
payoff.

##  1 Introduction

In many economic and political environments, a principal delegates decisions
to a better-informed agent: a firm appoints a manager to choose investment
levels in different projects; US Congress delegates power to federal agencies;
a legislative forms a committee to draft bills; a regulator lets a monopolist
choose prices. Following [18], an extensive literature models such delegation
problems by assuming that both the action and the state of the world lie in a
one-dimensional space. A main result of this literature characterizes when it
is optimal for the principal to constrain the agent’s choice to lie in an
interval, and this conclusion has been used to explain why managers face
spending caps, regulators impose price ceilings, and trade agreements specify
maximum tariff levels.

The assumption that the action and state space are one-dimensional is made for
tractability. In many applications, the underlying states and actions are more
complex and more realistically modeled as multidimensional: managers invest in
several projects, Congress delegates many decisions to the EPA, and committees
draft multiple bills. What mechanisms are optimal in such multidimensional
settings? How robust are conclusions obtained for one-dimensional models? And
can we still expect that relatively simple mechanisms are often optimal?

To study these questions, we consider a principal that takes a
multidimensional action and faces an agent with private information about a
multidimensional state of the world (the agent’s type). Payoffs depend on the
action and the state of the world, and transfers are infeasible. The principal
can design arbitrary mechanisms, including stochastic ones, to maximize her
expected payoff. Our main result characterizes, for an arbitrary mechanism,
when this mechanism is optimal. Often, it is optimal to delegate the decision
to the agent but to constrain the agent by requiring that her action lies in
some set. For convex delegation sets, we provide a simple characterization,
which is a direct analog of conditions characterizing when interval delegation
is optimal in one-dimensional models. Our results illustrate how a principal
can benefit from optimally bundling independent decisions. Even for one-
dimensional models, our approach provides new insights: Our main result
characterizes for arbitrary mechanisms—not just interval delegation sets—when
this mechanism is optimal. And as corollaries, we obtain a novel condition
under which some interval delegation set will be optimal and a comparative
statics result showing when the agent will get more discretion.

A key step to deriving our results lies in obtaining a simple characterization
of the set of feasible mechanisms. Given a mechanism, the corresponding
indirect utility assigns to any type the payoff this type would get by
choosing his report optimally. This payoff must be less than the first-best
payoff, i.e., the payoff this type would get if he could choose the action
without any constraints. Moreover, the indirect utility must be a convex
function since it is the maximum of a family of affine functions. Lemma 1
shows that any function satisfying these two properties is the indirect
utility of an incentive-compatible mechanism.

This characterization is easy to use and already helpful for one-dimensional
delegation models. Our formulation differs from the previous literature, which
often considered only deterministic mechanisms. Since the convex combination
of two incentive-compatible mechanisms is not necessarily incentive
compatible, the set of deterministic mechanisms is not even convex.111Some
earlier papers also consider stochastic mechanisms (or allow for money
burning/restricted transfer) and obtain a convex set of mechanisms; see, for
example, [2, 25, 5, 3, 21, 22]. Moreover, a common approach is to first treat
the model as one with transfers and then impose that these transfers are zero
(or negative). Compared to this approach, formulating the problem via indirect
utilities is more direct and provides valuable geometric insights into which
mechanisms can be optimal. For the multidimensional problem, the approach via
indirect utilities provides additional benefits because it circumvents
intricate characterizations of incentive compatibility [33, see].

To find the optimal mechanism, we formulate the principal’s problem in terms
of indirect utilities. In this formulation, the problem becomes a linear
program, and we use linear programming duality to derive necessary and
sufficient conditions for a given mechanism to be optimal. Typically, optimal
mechanisms pool certain types, and our main result shows that a mechanism is
optimal if conditional on any pooling region, a stochastic dominance condition
(using the convex order) is satisfied. Intuitively, this condition requires
that restricted to the pooling region (where the indirect utility function is
affine), any convex indirect utility yields a lower payoff. If the pooling
regions are at most one-dimensional, the stochastic dominance condition has a
simple formulation in terms of majorization. Using this observation, we
provide necessary and sufficient conditions for a convex delegation set with a
smooth boundary to be optimal. These conditions are easy to check and are
straightforward extensions of conditions that ensure the optimality of
interval delegation sets in one-dimensional models [2, see].

#### Related Literature

The literature on delegation has focused mainly on problems in which the
principal delegates a single one-dimensional decision and therefore assumed
that both the action and state spaces are one-dimensional; see, for example,
[18, 19, 30, 1, 2, 24].

A few delegation papers do consider richer action and/or type spaces. [6]
considers an agent with two-dimensional private information and discusses
several applications. Since the principal’s action is assumed to be one-
dimensional (and only interval delegation sets are considered), there is only
limited scope to screen two-dimensional types in his analysis. [23]
characterize the optimal mechanism in a setting where two decisions depend on
a single-dimensional underlying state. [15] considers multidimensional
information and actions but restricts the principal’s choice to a particular
class of “budgeting mechanisms”. The closest paper to ours is [14], which
studies the delegation of several independent decisions, which yield
multidimensional action and state spaces. For quadratic preferences with a
constant bias, he shows that if the states are independently and identically
distributed according to normal distributions then it is optimal to delegate a
‘half space’. Without the normality assumption, he shows that the principal’s
payoff from such a mechanism converges to the first-best as the number of
independent decision problems grows. [13] also considers multidimensional
delegation problems and characterizes the max-min optimal mechanism, which
maximizes the principal’s payoff against the worst-case preference type of the
agent.

The elicitation of information about multiple independent decisions from a
biased agent has been studied in general mechanism design [20, e.g.,] and
cheap talk environments [9, 26]. [20] show that by linking independent
decisions, the principal’s payoff converges to the first-best as the number of
decisions grows. Our results can be used to show how the principal should
optimally link decisions, which can be important if there is a limited number
of decisions.

On a methodological level, our work is related to the literature on
multidimensional mechanism design, and in particular on multiproduct
monopolists [33, 27, 28, 10, 16, see, e.g.,].

##  2 Model

A principal chooses an action $a\in\mathbb{R}^{n}$. An agent is privately
informed about the state of the world $s\in S$, where
$S\subseteq\mathbb{R}^{n}$ is compact and convex. The agent’s and principal’s
payoffs depend on both the action and the state of the world, and are given by

$\displaystyle u_{A}(a,s)$ $\displaystyle:=a\cdot s+b(a)$ $\displaystyle
u_{P}(a,s)$ $\displaystyle:=a\cdot g(s)+\kappa b(a),$

respectively, where $b:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is strictly
concave, differentiable with a Lipschitz-continuous gradient mapping, and
satisfies $\lim_{\lVert a\rVert\rightarrow\infty}\frac{b(a)}{\lVert
a\rVert}=-\infty$,222Since we do not artificially constrain the set of
actions, some assumptions are needed to ensure that for every type $s\in S$
there is an optimal action. The current assumptions ensure this and simplify
some arguments, but weaker conditions on $b$ could be imposed.
$g:S\rightarrow\mathbb{R}^{n}$ is continuous, and $\kappa>0$.

We assume that the state $s$ is distributed according to a probability
distribution $F$ with differentiable density $f$ and support $S$. The
principal aims to maximize her expected payoff and can design arbitrary
mechanisms.

The revelation principle applies and we define a _mechanism_ to be a function
$m:S\rightarrow\Delta(\mathbb{R}^{n})$ such that expected payoffs are
integrable.333We denote by $\Delta(\mathbb{R}^{n})$ the Borel $\sigma$-algebra
on $\mathbb{R}^{n}$. To simplify notation, we extend the domain of $b(\cdot)$
and $u_{i}(\cdot,s)$ linearly to include probability distributions over
$\mathbb{R}^{n}$, so that $b(m(s))=\mathbb{E}_{m(s)}[b(a)]$ and analogously
for $u_{i}(\cdot,s)$. A mechanism is _incentive compatible_ if for all $s$ and
$s^{\prime}$ in $S$,

$\displaystyle u_{A}(m(s),s)\geq u_{A}(m(s^{\prime}),s).$

##  3 Characterizing incentive-compatible mechanisms

We characterize the set of incentive-compatible mechanisms in terms of their
indirect utilities. To any incentive-compatible mechanism $m$ corresponds an
_indirect utility_ $U:\mathbb{R}^{n}\rightarrow\mathbb{R}$ defined by

$U(s):=\sup_{s^{\prime}\in S}\mathbb{E}[m(s^{\prime})]\cdot
s+b(m(s^{\prime})).$

Which indirect utilities correspond to some incentive-compatible mechanism?
First, any indirect utility is convex as the supremum of a family of functions
that are affine in the state $s$. Second, in the absence of transfers the
agent’s utility cannot be higher than if he was free to choose his action.
Defining the first-best payoff $h:\mathbb{R}^{n}\rightarrow\mathbb{R}$ by

$h(s):=\sup_{a\in\mathbb{R}^{n}}a\cdot s+b(a),$

$U\leq h$ is clearly necessary.444We denote the pointwise order by $\leq$, so
$U\leq h$ means $U(s)\leq h(s)$ for all $s$ in the common domain of $U$ and
$h$. The following result shows that these two conditions characterize the set
of feasible indirect utilities.

######  Lemma 1.

An indirect utility $U$ corresponds to an incentive-compatible mechanism if
and only if $U$ is convex and lies below the first-best payoff: $U\leq h$.

Figure 1: The function $U$ satisfies $U(s)\leq h(s)$ for all $s\in S$ but does
not correspond to a feasible mechanism. To see this, note that there is no
convex extension of $U$ to $\mathbb{R}$ such that the extension lies below
$h$. Lemma 1 then implies that $U$ is not the indirect utility of any feasible
mechanism.

Intuitively, if $U$ is convex then it would correspond to an incentive-
compatible mechanism if transfers were available and the agent had quasi-
linear preferences. If the required transfers are all negative then we can use
the agent’s risk aversion (coming from the strict concavity of $b$) to
simulate these transfers via stochastic actions. One can show that $U\leq h$
implies that the required transfers are negative. This last step relies on the
domain of $U$ and $h$ being large enough and it would not suffice to require
only that $U(s)\leq h(s)$ for all $s\in S$. Figure 1 illustrates a convex
function $U$ which lies below $h$ on all of $S$, but which does not correspond
to a mechanism because the lotteries assigned to low types would yield a
strictly higher payoff than the first-best payoffs for some hypothetical
types, an impossibility.

  * Proof.

Let us first state three basic observations from convex analysis. The convex
conjugate of a function $U$ is denoted by $U^{*}$ and defined by
$U^{*}(a):=\sup_{s\in\mathbb{R}^{n}}a\cdot s-U(s)$. We will use the following
facts, which follow immediately from this definition: (i) $h=(-b)^{*}$, (ii)
$U\leq h$ implies $h^{*}\leq U^{*}$, and (iii) $a\in\partial U(s)$ implies
$U^{*}(a)=a\cdot s-U(s)$.555Here, $\partial U(s)$ denotes the subdifferential
of $U$ at $s$. To see (iii), note that the definition of $U^{*}$ implies
$U^{*}(a)\geq a\cdot s-U(s)$. Conversely, convexity of $U$ implies that for
all $s^{\prime}$, $a\cdot s-U(s)\geq a\cdot s^{\prime}-U(s^{\prime})$. Taking
the supremum of the right-hand side with respect to $s^{\prime}$ yields
$a\cdot s-U(s)\geq U^{*}(a)$.

Suppose $U$ is convex and satisfies $U\leq h$. Let the mechanism $m$ assign to
any type $s\in S$ a lottery with expected value $a\in\partial U(s)$ that
yields the payoff $a\cdot s+b(a)-U^{*}(a)+h^{*}(a)$. Such a lottery exists
because $a\cdot s+b(a)$ would be the payoff for type $s$ from always getting
action $a$, because fact (ii) implies that the agents payoff is lower, and
because $b$ is strictly concave.666More formally, strict concavity of $b$
implies that for any $a\in\mathbb{R}^{n}$ and nonzero $d\in\mathbb{R}^{n}$
there is $\varepsilon>0$ such that $1/2[b(a+d)+b(a-d)]<b(a)-\varepsilon$. It
follows that for any $\lambda>1$, $1/2[b(a+\lambda d)+b(a-\lambda d)]\leq
b(a)-\lambda\varepsilon.$ Therefore, by choosing $\lambda$ arbitrarily large,
one can design lotteries with expected value $a$ that yield arbitrarily low
payoff to the agent.  Then facts (i) and (iii) imply that the payoff of a
truthful type $s$ is $U(s)$:

$\displaystyle u_{A}(m(s),s)=s\cdot a+b(a)-U^{*}(a)+h^{*}(a)=U(s).$

It remains to show that $m$ is incentive compatible. For all $s$ and
$s^{\prime}$,

$\displaystyle u_{A}(m(s),s)=U(s)\geq
U(s^{\prime})+\mathbb{E}[m(s^{\prime})]\cdot(s-s^{\prime})$ $\displaystyle=$
$\displaystyle\mathbb{E}[m(s^{\prime})]\cdot
s^{\prime}+b(m(s^{\prime}))+\mathbb{E}[m(s^{\prime})]\cdot(s-s^{\prime})=u_{A}(m(s^{\prime}),s),$

where the first inequality follows since $E[m(s)]\in\partial U(s^{\prime})$. ∎

Figure 2 illustrates the result for one-dimensional types and quadratic
payoffs. It shows four indirect utilities that, according to Lemma 1,
correspond to incentive-compatible mechanisms. In 2(a), all types between
$s_{1}$ and $s_{2}$ obtain their first-best utility and $U$ is affine below
$s_{1}$ and above $s_{2}$. This indirect utility can be obtained by letting
types choose their preferred action from the interval of deterministic actions
$[s_{1},s_{2}]$. In 2(b), the menu of actions from which the agent can choose
contains an additional deterministic action above $s_{2}$. The indirect
utility in 2(c) contains an affine piece that lies strictly below the graph of
$h$. This part of the indirect utility corresponds to types that obtain a
(nondegenerate) stochastic action, which yields no type its first-best payoff.
Finally, 2(d) illustrates an indirect utility corresponding to a mechanism in
which types in two adjacent regions obtain a stochastic action.

(a) Interval delegation

(b) A deterministic mechanism

(c) A stochastic mechanism

(d) A stochastic mechanism with two adjacent stochastic actions

Figure 2: Examples of indirect utilities. The blue curves show the function
$h$ for one-dimensional types and quadratic payoffs (i.e., assuming
$b(a)=-\frac{a^{2}}{2}$). The green curves show indirect utilities
corresponding to incentive-compatible mechanisms.

##  4 Characterizing optimal mechanisms

We characterize the optimal mechanisms in this section. To do so, we first
formulate the principal’s problem in terms of indirect utilities (Section
4.1). We then state the main characterization of optimal mechanisms in Section
4.2 and illustrate the result for particular mechanisms. Finally, we outline
the proof of the main result in Section 4.3.

###  4.1 Formulating the principal’s problem

Consider an indirect utility $U$ that corresponds to some incentive-compatible
mechanism. In general, there are many incentive-compatible mechanisms that
induce the same indirect utility; however, all such mechanism induce the same
payoff for the principal. To see this, let $m$ be an incentive-compatible
mechanism with corresponding indirect utility $U$. Using $\nabla
U(s)=\mathbb{E}[m(s)]$ (by an Envelope theorem) and $U(s)=\nabla U(s)\cdot
s+b(m(s))$, the principal’s payoff from mechanism $m$ in state $s$ is
completely determined by $U$:

$\displaystyle\mathbb{E}[m(s)]\cdot g(s)+\kappa b(m(s))=\nabla
U(s)\cdot[g(s)-\kappa s]+\kappa U(s).$

This observation implies that the principal’s payoff is a linear function of
$U$. Therefore, a solution to the principal’s problem can be found at an
extreme point of the feasible set. Returning to Figure 2, it is easy to see
that the indirect utilities in Figures 2(a)–2(c) are extremal in that they
cannot be written as a nontrivial convex combination of two feasible indirect
utilities. In contrast, the indirect utility in 2(d) can be written as such a
convex combination. This implies that whenever this mechanism is optimal,
there is another (and simpler) mechanism which is also optimal. Intuively, one
can write this indirect utility as a convex combination because two adjacent
regions obtain distinct stochastic actions. This insight shows how, without
loss of optimality, one can restrict attention to a smaller class of
mechanism.777[22] develop this point more formally in the context of one-
dimensional types/actions and quadratic utilities and characterize the set of
extremal mechanisms. Formulating the problem in terms of indirect utilities
and using our Lemma 1, one can obtain this characterization more directly. It
would be interesting to extend this characterization of extremal mechanisms to
the multidimensional setting. For multidimensional settings, analogous
arguments show that many complicated mechanisms are not extremal and therefore
the principal need not consider these mechanisms.

As is standard in multidimensional mechanism design [[, see, for
example,]]rochet1998ironing, we can use the divergence theorem to reformulate
the objective function as follows:

$\displaystyle\int\big{[}\kappa U(s)+\nabla U(s)\cdot[g(s)-\kappa
s]\big{]}\,\mathrm{d}F(s)$ $\displaystyle=$ $\displaystyle\int
U(s)\big{[}\kappa f(s)-\operatorname{div}[(g(s)-\kappa
s)f(s)]\big{]}\,\mathrm{d}s+\int_{\operatorname{bd}S}U(s)[g(s)-\kappa
s]f(s)\cdot\hat{\mathbf{n}}_{S}(s)\,\mathrm{d}\mathcal{H}(s),$

where $\div$ denotes the divergence of a function, for any set $A$,
$\operatorname{bd}A$ denotes the boundary of $A$, $\mathcal{H}$ denotes the
$n-1$-dimensional Hausdorff measure on the boundary of $S$, and
$\hat{\mathbf{n}}_{S}(s)$ denotes the outward normal vector to the convex set
$S$ at $s\in\operatorname{bd}S$.

This allows us to write the principal’s problem as888The existence of a
maximizer follows from standard arguments.

$\displaystyle\max_{U\text{ convex}}\int U(s)\,\mathrm{d}\mu(s)$
$\displaystyle\text{s.\,t. }U\leq h,$

where the measure $\mu$ is defined by

$\displaystyle\mu(E)=\int_{E}\nu(s)\,\mathrm{d}\lambda(s),$

$\lambda$ is the Lebesgue measure on $S$ plus the Hausdorff measure on the
boundary of $S$, and

$\displaystyle\nu(s):=\begin{cases}\kappa f(s)-\operatorname{div}[(g(s)-\kappa
s)f(s)]&\text{ if }s\in\operatorname{int}S\\\ [g(s)-\kappa
s]f(s)\cdot\hat{\mathbf{n}}_{S}(s)&\text{ if
}s\in\operatorname{bd}S.\end{cases}$

Cearly, $\nu$ plays an important role in determining which mechanisms are
optimal. Heuristically, $\nu(s)$ measures how much the prinicipal’s payoff
increases if the indirect utility of type $s$ is increased, but where types on
the boundary get extra weight.

To illustrate $\nu$ and for later use, let use compute $\nu$ for a one-
dimensional type space $S=[\underline{s},\overline{s}]$:

$\displaystyle\nu(s):=\begin{cases}\kappa
f(s)-[g^{\prime}(s)-\kappa]f(s)-[g(s)-\kappa s]f^{\prime}(s)&\text{ if
}s\in(\underline{s},\overline{s})\\\
[g(\overline{s})-\kappa\overline{s}]f(\overline{s})&\text{ if
}s=\overline{s}\\\
[\kappa\underline{s}-g(\underline{s})]f(\underline{s})&\text{ if
}s=\underline{s}.\end{cases}$ (1)

######  Example 1.

Suppose $S=[-\frac{1}{2},\frac{1}{2}]^{n}$ and $F$ is the uniform distribution
on $S$. Let us assume payoffs are quadratic and that $g(s)=\alpha s$ for some
$\alpha\in(0,\kappa]$; this implies that the principal is biased towards the
ex-ante optimal action $0$. In that case, $\nu$ simplifies to

$\displaystyle\nu(s):=\begin{cases}\kappa+(\kappa-\alpha)n&\text{ if
}s\in\operatorname{int}S\\\
(\alpha-\kappa)s\cdot\hat{\mathbf{n}}_{S}(s)&\text{ if
}s\in\operatorname{bd}S.\end{cases}$ (2)

###  4.2 Optimal mechanisms

Given an indirect utility $U$, we let $\mathcal{Q}$ denote a coarsest
partition of $\mathbb{R}^{n}$ such that $U$ is affine on each partition
element. We denote by $\\{\mu|_{Q}\\}_{Q\in\mathcal{Q}}$ a conditional measure
of $\mu$ given $Q$.

######  Theorem 1.

Let $U$ be a feasible indirect utility. Then $U$ is optimal if for all
$Q\in\mathcal{Q}$, $\mu|_{Q}(Q)\geq 0$ and $\mu|_{Q}\leq_{cx}\delta_{Q}$,
where $\delta_{Q}$ is a point mass of mass $\mu|_{Q}(Q)$ at $s$ if there is
$s\in Q$ satisfying $U(s)=h(s)$ and $\delta_{Q}$ is the zero-measure
otherwise.

Moreover, this condition is necessary for $U$ to be optimal if $U$ is
differentiable $|\mu|$-almost everywhere.

Two comments on the conditions in Theorem 1 are in order. First, if there is
$s\in Q$ such that $U(s)=h(s)$ then it is unique because $U$ is affine on $Q$
and $h$ is strictly convex. Second, for the necessity result, observe that $U$
is differentiable Lebesgue-almost everywhere since it is a convex function.
Since $|\mu|$ is absolutely continuous with respect to the Lebesgue measure on
the interior of $S$, $U$ is differentiable $|\mu|$-almost everywhere if, for
example, the density $f$ is zero on the boundary of $S$ or if $U$ is
differentiable $\mathcal{H}$-almost everywhere on the boundary of $S$. In the
one-dimensional case, this last condition can always be satisfied.

Why are the conditions in Theorem 1 sufficient for $U$ to be optimal? Consider
a partition element $Q\in\mathcal{Q}$ and suppose $\delta_{Q}$ is a point mass
at $s^{*}$. Then any feasible indirect utility $V$ will be convex and lie
below $U$ at $s^{*}$. Also, $\mu|_{Q}\leq_{cx}\delta_{Q}$ implies $\int
V(s)\,\mathrm{d}\mu|_{Q}(s)\leq\int V(s)\,\mathrm{d}\delta_{Q}(s)$. Moreover,
if $a$ is an affine function that coincides with $V$ at the barycenter of
$\mu|_{Q}$ then we get $\int V(s)\,\mathrm{d}\mu|_{Q}(s)\leq\int
a(s)\,\mathrm{d}\mu|_{Q}(s)$. Since $U$ restricted to $Q$ is affine, lies
above $V$ at $s^{*}$, and $\mu|Q(Q)\geq 0$, this implies that conditional on
the type belonging to $Q$, the principal’s expected payoff under $U$ is higher
than under $V$. And if $\delta_{Q}$ is the zero measure then $V$ might lie
above $U$ but the same conclusion follows since $\mu|_{Q}(Q)=0$ and
conditional on $Q$, adding a constant to the indirect utility does not change
the principal’s payoff. The conclusion that these conditions are also
essentially necessary shows that the problem can in some sense be decomposed:
whenever the principal can improve $U$ conditional on $Q$, she can extend this
improved version to a feasible indirect utility that yields unconditionally a
higher payoff.

A particularly simple mechanism is if the principal delegates the decision to
the agent, potentially restricting the agents action to belong to some set
$A$. Note that any deterministic mechanism can be implemented as an indirect
mechanism in this way. For a closed set $A\subseteq S$, we say that
_delegating to $A$_ is optimal if an optimal mechanism takes the form that any
type in $A$ gets her first-best action, and any other type gets her most
preferred action among the first-best actions of types in $A$. For example, if
$n=1$ and $A=[s_{1},s_{2}]$ then delegating to $A$ is optimal if there is an
optimal mechanism in which any type below $s_{1}$ gets the first-best action
of type $s_{1}$, any type in $[s_{1},s_{2}]$ gets her first best action, and
any type above $s_{2}$ gets the first-best action of type $s_{2}$. In the
following we will specialize Theorem 1 and discuss under what conditions such
a mechanism is optimal.

We can simplify the conditions in Theorem 1 by recalling that the convex order
has a simple structure for one-dimensional spaces. A cdf $H_{1}$ on a one-
dimensional interval $[x,y]$ dominates a cdf $H_{2}$ in the convex order if
and only if $H_{2}$ _majorizes_ $H_{1}$:

$\int_{s}^{y}H_{1}(z)\,\mathrm{d}z\leq\int_{s}^{y}H_{2}(z)\,\mathrm{d}z$

for all $s\in[x,y]$ with equality for $s=x$ [[]Theorem
3.A.1]shaked2007stochastic. This observation simplifies the characterization
in Theorem 1 whenever $U$ is affine on at most one-dimensional sets. As we
will see, this is useful even if the type space is multidimensional. To
illustrate the simpler conditions, we first consider when interval delegation
is optimal with one-dimensional types [[, for earlier characterizations,
see]]AM:08,AB:13.

######  Corollary 1.

Suppose $n=1$ and $s_{1},s_{2}\in S$ with $s_{1}<s_{2}$. Delegating to the
interval $[s_{1},s_{2}]$ is optimal if and only if

  1. (i)

$\nu(s)\geq 0$ for all $s\in[s_{1},s_{2}]$,

  2. (ii)

$\int_{s}^{\overline{s}}(x-s)\nu(x)\,\mathrm{d}\lambda(x|x\geq s_{2})\leq 0$
for all $s\geq s_{2}$ with equality for $s=s_{2}$, and

  3. (iii)

$\int_{\underline{s}}^{{s}}(s-x)\nu(x)\,\mathrm{d}\lambda(x|x\leq s_{1})\leq
0$ for all $s\leq s_{1}$ with equality for $s=s_{1}$.

  * Proof.

Note that the partition $\mathcal{Q}$ induced by $U$ has elements
$[\underline{s},s_{1}]$, $[s_{2},\overline{s}]$, and $\\{s\\}$ for all
$s\in(s_{1},s_{2})$. For all $s\in(s_{1},s_{2})$, $\nu(s)\geq 0$ is equivalent
to $\mu|_{Q}(Q)\geq 0$ and $\mu|_{Q}\leq_{cx}\delta_{Q}$ for
$Q=\\{s\\}$.999For $s\in\\{s_{1},s_{2}\\}$, if $s\in\operatorname{int}S$ then
$\nu(s)\geq 0$ follows because $\nu$ is continuous on the interior of $S$. And
if $s\in\operatorname{bd}S$, there is $Q\in\mathcal{Q}$ with $Q\cap S=\\{s\\}$
and hence $\mu|_{Q}(Q)\geq 0$ implies $\nu(s)\geq 0$. Now consider
$Q=[s_{2},\overline{s}]$ and let $\lambda(x|x\geq s_{2})$ denote the
conditional distribution of $\lambda$ conditional on $x\geq s_{2}$. Since
$\delta_{Q}$ is a point mass of mass $\mu|_{Q}(Q)$ at $s_{2}$, we can use
majorization to rewrite $\mu|_{Q}\leq_{cx}\delta_{Q}$ as

$\int_{s}^{\overline{s}}\int_{x}^{\overline{s}}\nu(z)\,\mathrm{d}\lambda(z|z\geq
s_{2})\,\mathrm{d}x\leq 0$

for all $s\geq s_{2}$ with equality for $s=s_{2}$. Integrating by parts, this
becomes condition (ii). Moreover, since the derivative with respect to $s$ of
the left-hand side evaluated at $s_{2}$ is negative, we obtain
$\mu|_{Q}(Q)\geq 0$. The argument for $Q=[\underline{s},s_{1}]$ is analogous.
∎

Figure 3: Optimality of interval delegation

Figure 3 illustrates condition (ii). Suppose that starting with interval
delegation (represented by the solid indirect utility), the principal changes
the mechanism and assigns a lottery with expected value strictly above $\nabla
U(s_{2})$ to all types above $s$. This tilts the indirect utility starting at
$s$ upwards (see the dashed indirect utility) and therefore increases the
indirect utility for every type $x\geq s$ in proportion to $x-s$. The change
in the principal’s expected payoff is therefore proportional to
$\int_{s}^{\overline{s}}(x-s)\nu(x)\,\mathrm{d}\lambda(x|x\geq s_{2})$.
Consequently, condition (ii) ensures that such changes are not profitable.
Equality for $s=s_{2}$ implies, in addition, that it would not be profitable
to marginally reduce the action for all types above $s_{2}$ either.

Interestingly, the conditions identified in Corollary 1 are in our setting
equivalent to the ones obtained in [2, Proposition 2a ]. This might initially
be surprising since we characterize optimality of interval delegation in the
class of stochastic mechanisms and [2] characterize optimality in the class of
deterministic mechanisms (and stochastic mechanisms can do strictly better in
general). Figure 3 illustrates why the conditions are the same: Suppose the
principal strictly benefits from deviating to the dashed indirect utility,
which represents a stochastic mechanism. Since her payoff is linear in $U$,
the arguments in the previous paragraph imply that she also benefits from
deviating to the dotted indirect utility. Since the dotted linear utility
corresponds to a deterministic mechanism, we conclude that conditions (ii) in
(iii) in Corollary 1 are necessary for interval delegation to be optimal in
the class of deterministic mechanisms (and necessity of condition (i) can be
shown easily). Later, it will become clear that this equivalence is specific
to the one-dimensional setting.

######  Corollary 2.

If $n=1$ and $\\{s\in S:\nu(s)\geq 0\\}$ is an interval, then delegating to an
interval is optimal.

The key insight for this result is that any pooling region (i.e., any $Q$ such
that $Q\cap S$ is not a singleton) must contain types $s$ with $\nu(s)\geq 0$
(since $\mu|_{Q}(Q)\geq 0$) and types $s$ with $\nu(s)\leq 0$ (since no point
measure $\delta_{Q}$ can dominate a distinct positive measure in the convex
order). If $\nu$ is positive on an interval, it follows that there can be at
most two pooling regions. A simple argument then shows that delegating to an
interval is an optimal mechanism.

Corollary 2 extends Proposition 2(a) in [4], which in our notation requires
$\nu$ to be positive on $(\underline{s},\overline{s})$. An simple implication
of our result is the following, which can be useful for applications.

######  Corollary 3.

Suppose the type space is one-dimensional (i.e., $n=1$), $\kappa=1$, and the
agent has a constant bias (i.e., $g(s)=s+\beta$ for some
$\beta\in\mathbb{R}$). If $f$ is logconcave then delegating to an interval is
optimal.

As another illustration, let us return to Example 1 specializing to a one-
dimensional type space.

######  Example 1 (continued).

For $n=1$ and $\kappa=1$, the objective function simplifies to
$\nu(s)=2\kappa-\alpha$ for $s\in(\underline{s},\overline{s})$,
$\nu(\underline{s})=(\kappa-\alpha)\underline{s}$, and
$\nu(\overline{s})=(\alpha-\kappa)\overline{s}$. Since $\nu$ is positive on an
interval, Corollary 2 implies that delegating to an interval is optimal, and
it only remains to find the best interval.

The optimal interval must satisfy Condition (ii) as an equality for $s=s_{2}$,
which requires

$(2-\alpha)\left[\frac{1}{8}-\frac{1}{2}s_{2}^{2}-s_{2}\left(\frac{1}{2}-s_{2}\right)\right]=0,$

and simple algebra yields $s_{2}=\frac{\alpha}{2-\alpha}$. Using symmetry, it
follows that it is optimal to delegate to the interval
$\left[-\frac{\alpha}{2-\alpha},\frac{\alpha}{2-\alpha}\right]$.

For a one-dimensional type space, the approach used in Corollary 1 can be used
to simplify the conditions in Theorem 1 for any mechanism, not just interval
delegation. More generally, this approach is useful even with multidimensional
types. To see this, let $A$ be a closed and convex set and, for
$s\in\operatorname{bd}A$, let $N_{A}(s)$ denote the normal cone to $A$ at $s$.
With quadratic payoffs, if the principal delegates $A$ and
$s\in\operatorname{bd}A$, then all types in $s+N_{A}(s)$ will choose action
$s$. Moreover, if the boundary of $A$ is differentiable then $N_{A}(s)$ is a
(one-dimensional) ray and we can again use majorization to simplify the convex
dominance conditions in Theorem 1.

Figure 4: Indirect utility for delegation to a convex set.

######  Corollary 4.

Suppose payoffs are quadratic and $A\subseteq S$ is closed, convex, has
nonempty interior and a differentiable boundary. Delegating to $A$ is optimal
if and only if

  1. (i)

$\nu(s)\geq 0$ for all $s\in A$ and

  2. (ii)

for all $s\in\operatorname{bd}A$ and $z>0$,

$\int_{z}^{\infty}(x-z)\nu(s+x\hat{\mathbf{n}}_{A}(s))\,\mathrm{d}\lambda(s+x\hat{\mathbf{n}}_{A}(s)|s+N_{A}(s))\leq
0$

with equality for $z=0$.

The conditions in Corollary 4 closely resemble those in Corollary 1. Indeed,
Condition (i) in either case requires that $\nu$ is positive on the set of
types that obtain their first-best payoffs, and Condition (ii) (and Conditions
(ii) and (iii), respectively) impose that for each point on the boundary the
analogous stochastic dominance condition holds.

The economic interpretation of Condition (ii) is analogous to how we
interpreted Condition (ii) in Corollary 1. This condition ensures that the
principal does not benefit from marginally tilting the indirect utility along
line segments that are orthogonal to the boundary of $A$, e.g., the solid line
segment in Figure 4. Observe that there is a stochastic mechanism in which the
indirect utility is increased only in a small neighborhood of the solid line
segment (by Lemma 1). On the other hand, there is no deterministic mechanism
achieving this because for any deterministic action the indirect utility would
have to increase significantly along the solid line segment (in order to reach
the first-best payoff for some type) and convexity then requires that all
types in a neighborhood of the line segment obtain higher indirect utilities.
This indicates that our characterization relies in the multidimensional
setting on stochastic mechanisms being feasible.

######  Example 1 (continued).

Consider a two-dimensional example and recall that $F$ is the uniform
distribution and $g(s)=\alpha s$ for some $\alpha\in[0,\kappa)$. We assume
quadratic payoffs; in that case, the problem is separable across dimensions:
the principal’s optimal action in dimension 1 depends only on the first
component of the state and is independent of the action in dimension 2.

Suppose first that there are two agents: For $i=1,2$, agent $i$ has private
information about $s_{i}$ (but not $s_{j}$ for $j\neq i$) and cares only about
the action and state in dimension $i$. It follows that the principal faces two
independent delegation problems, and our earlier analysis implies that it is
optimal to let each agent choose any action in
$\left[-\frac{\alpha}{2-\alpha},\frac{\alpha}{2-\alpha}\right]$. In effect,
the agents’ choice will be the action in the red square in Figure 5 that is
closed to the realized state.

Now compare this to the situation where there is only one agent. This agent
has private information about both dimensions of the state and cares about
both dimensions of the action. How can the principal improve her expected
payoff? Intuitively, she could offer the agent to take more extreme actions in
one dimension if he moderates his action in the other dimension. How can the
principal optimally bundle the two decision problems?

Corollary 4 provides insights into how to solve the problem: if one can find a
$A$ satisfying the conditions stated there, delegating to this set will be an
optimal mechanism. Since $\nu$ is positive on the interior of $S$ and strictly
negative on the boundary of $S$, Condition (i) will be satisfied if
$A\subseteq\operatorname{int}S$ and Condition (ii) will be satisfied if, for
every $s\in\operatorname{bd}A$, equality holds in Condition (ii) for $z=0$.
This yields a second-order differential equation, whose solution describes the
boundary of the optimal delegation set, see the blue curve in Figure 5 for an
illustration.

Figure 5: Optimal bundling

###  4.3 Proof Sketch

To proof Theorem 1, we use duality in linear programming. To formulate the
dual program, it is more convenient to work with indirect utilities that are
defined on a compact domain. But recall that it is not enough to only require
that $U(s)\leq h(s)$ for all $s\in S$. The following technical result ensures
that we can restrict the indirect utilities to have a compact domain as long
as this domain is chosen large enough.

######  Lemma 2.

There is a compact $X\subseteq\mathbb{R}^{n}$ such that the principal’s
problem can be written as $\max\\{\int
U\,\mathrm{d}\mu|U:X\rightarrow\mathbb{R},\ U\text{ convex},\ U\leq h\\}$.

Formally, we show that if $X$ is chosen large enough then for any solution to
the above problem there is a corresponding solution to the original problem.
For a convex function $U$ defined on $S$, we consider the smallest convex
function defined on $\mathbb{R}^{n}$ that extends $U$. If this extension lies
below $h$ on a large set $X$ then $h(y)<U(y)$ for some $y$ is possible only if
$\lVert\nabla U(s)\rVert$ is large for some $s\in S$, i.e., the expected
action for some type is large. We show that this implies that the principal’s
expected payoff is low, contradicting that $U$ is a solution.

Now let $X$ be as in the above lemma and denote by $\mathcal{U}$ the set of
convex continuous functions that map $X$ to $\mathbb{R}$ and by
$\mathcal{M}_{+}$ the set of positive measures on $X$. We can formulate the
principal’s problem as follows (and call this formulation the primal problem):

$\displaystyle\max_{U\in\mathcal{U}}\int U(s)\,\mathrm{d}\mu(s)$ (P)
$\displaystyle\text{s.\,t. }U\leq h$

#### The dual problem

We will show that the following problem is the dual problem:

$\displaystyle\inf_{\gamma\in\mathcal{M}_{+}}\int h(s)\,\mathrm{d}\gamma(s)$
(D) $\displaystyle\text{s.\,t. }\gamma\geq_{cx}\mu,$

where $\geq_{cx}$ denotes the convex order on the space of measures.

Note that $h$ is a convex function; therefore, if $\mu$ was a positive
measure, this would be a trivial problem with solution $\gamma=\mu$. However,
since $\mu$ is a signed measure and $\gamma$ has to be a positive measure,
$\mu$ is not feasible in general.

It is easy to see that weak duality holds, that is, the value of the primal
problem (P) is always below the value of the dual problem (D). Indeed, for any
feasible $U$ and $\gamma$,

$\displaystyle\int U(s)\,\mathrm{d}\mu(s)\underbrace{\leq}_{(i)}\int
U(s)\,\mathrm{d}\gamma(s)\underbrace{\leq}_{(ii)}\int
h(s)\,\mathrm{d}\gamma(s)$ (3)

since (i) $U$ is convex and $\mu\leq_{cx}\gamma$ and (ii) $\gamma$ is a
positive measure and $U\leq h$. The following result shows that strong duality
holds, that is the optimal values of both problems are equal and the dual
problem has a solution.

######  Lemma 3 (Strong duality).

A feasible mechanism $U$ is optimal if and only if there exists a positive
measure $\gamma\geq_{cx}\mu$ such that

$\displaystyle U(s)$ $\displaystyle=h(s)\text{ for $\gamma$-almost every\ $v$
}$ (4) $\displaystyle\int U(s)\,\mathrm{d}\mu(s)$ $\displaystyle=\int
U(s)\,\mathrm{d}\gamma(s).$ (5)

This result is an analogue of a result in the revenue-maximization problem of
a multiproduct monopolist [[, see Theorem 2 in]]daskalakis-etal2017. Our
formulation of the delegation problem allows us to easily deduce strong
duality. Note that there is a convex function $U$ such that $h(x)-U(x)>0$ for
all $x\in X$. Therefore, Slater’s condition is satisfied and standard results
from linear programming imply that the dual problem has a solution and that
the optimal solutions of the primal and dual problems achieve the same value.
Since both inequalities in (3) have to hold as equalities, Lemma 3 follows.

#### Proof idea for Theorem 1.

It is easy to show that the conditions in Theorem 1 imply that $U$ is optimal:
by aggregating the measures $\delta_{Q}$, one obtains a positive measure
$\gamma$ satisfying the complementary slackness conditions (4) and (5) and
$\gamma\geq_{cx}\mu$. Lemma 3 then implies that $U$ is optimal.

For the converse direction, suppose $U$ is optimal. By Lemma 3, there is a
positive measure $\gamma$ such that the complementary slackness conditions (4)
and (5) hold and $\gamma\geq_{cx}\mu$. Letting $\mu^{+}$ ($\mu^{-}$) denote
the positive (negative) part of $\mu$, this last condition is equivalent to
$\gamma+\mu^{-}\geq_{cx}\mu^{+}$. Strassen’s theorem then implies that
$\gamma+\mu^{-}$ is a mean-preserving spread of $\mu^{+}$: one can obtain the
measure $\gamma+\mu^{-}$ by taking, for every $s$, the mass $\mu^{+}$ puts on
$s$ and spreading it according to a probability measure $D_{s}$ with expected
value $s$. Since $U$ is convex, Jensen’s inequality implies that $U(s)\leq\int
U(x)\,\mathrm{d}D_{s}(x)$ and equality holds only if $U$ is affine on the
convex hull of the support of $D_{s}$. Since equality must hold by (5), we
obtain that for all $Q\in\mathcal{Q}$ and $s\in Q$, the support of $D_{s}$ is
contained in the closure of $Q$. To simplify this informal discussion, suppose
that for all $Q\in\mathcal{Q}$ and $s\in Q$, the support of $D_{s}$ is
actually contained in $Q$ (and not just the closure of $Q$) and consider a
partition element $Q$ of positive measure. Then the conditional measure
$\gamma|_{Q}$ is positive (since $\gamma$ is positive) and satisfies
$\gamma|_{Q}+\mu^{-}|_{Q}\geq_{cx}\mu^{+}|_{Q}$ (since the left-hand side is a
mean-preserving spread of the right-hand side). Moreover, by (5) we get
$U(s)=h(s)$ for every $s$ in the support of $\gamma|_{Q}$. Since $h$ is
strictly convex and $U$ is affine on $Q$, there is at most one $s\in Q$ with
$U(s)=h(s)$ and therefore $\gamma|_{Q}$ is a point mass at this $s$ or the
zero measure. It follows that $\mu|_{Q}\leq_{cx}\delta_{Q}$, where
$\delta_{Q}$ is a point mass at $s$ or is the zero measure. The proof in the
Appendix follows this sketch but uses the additional assumption in Theorem 1
and additional arguments to deal with the case where the support of $D_{s}$ is
a subset of the closure of $Q$ but not a subset of $Q$.101010If $s$ lies in
the closure of $Q$ and $Q^{\prime}\neq Q$, then $U$ is not differentiable at
$s$ and, therefore, $U(s)<h(s)$. If follows from (4) that such points have
measure zero under $\gamma$. The additional assumption ensures that such
points also have measure zero under $\mu^{+}$ and $\mu^{-}$, and hence play no
role.

## References

  * [1] Ricardo Alonso and Niko Matouschek  “Optimal Delegation”  In _Review of Economic Studies_ 75.1, 2008, pp. 259–293.
  * [2] Manuel Amador and Kyle Bagwell  “The Theory of Optimal Delegation with an Application to Tariff Caps”  In _Econometrica_ 81.4, 2013, pp. 1541–1599
  * [3] Manuel Amador and Kyle Bagwell  “Money burning in the theory of delegation”  In _Games and Economic Behavior_ 121, 2020, pp. 382–412  DOI: https://doi.org/10.1016/j.geb.2020.02.010
  * [4] Manuel Amador, Kyle Bagwell and Alex Frankel  “A Note on Interval Delegation”  In _Economic Theory Bulletin_ 6.2, 2018, pp. 239–249  DOI: 10.1007/s40505-017-0133-4
  * [5] Attila Ambrus and Georgy Egorov  “Delegation and Nonmonetary Incentives”  In _Journal of Economic Theory_ 171, 2017, pp. 101–135
  * [6] Mark Armstrong  “Delegating Decision-Making to an Agent with Unknown Preferences” unpublished, 1995
  * [7] Vladimir Igorevich Bogachev  “Measure theory”  Springer, 2007
  * [8] Vladimir Igorevich Bogachev  “Measure theory”  Springer, 2007
  * [9] Archishman Chakraborty and Rick Harbaugh  “Comparative cheap talk”  In _Journal of Economic Theory_ 132.1 Elsevier, 2007, pp. 70–94
  * [10] Constantinos Daskalakis, Alan Deckelbaum and Christos Tzamos  “Strong Duality for a Multiple-Good Monopolist”  In _Econometrica_ 85.3 Blackwell Publishing Ltd, 2017, pp. 735–767  DOI: 10.3982/ECTA12618
  * [11] F Dragomirescu and C Ivan  “The smallest convex extensions of a convex function”  In _Optimization_ 24.3-4 Taylor & Francis, 1992, pp. 193–206
  * [12] Nelson Dunford and Jacob T. Schwartz  “Linear Operators, Part 1: General Theory”  John WileySons, 1988
  * [13] Alex Frankel  “Aligned delegation”  In _American Economic Review_ 104.1, 2014, pp. 66–83
  * [14] Alex Frankel  “Delegating multiple decisions”  In _American Economic Journal: Microeconomics_ 8.4, 2016, pp. 16–53
  * [15] Simone Galperti  “A theory of personal budgeting”  In _Theoretical Economics_ 14.1 Wiley Online Library, 2019, pp. 173–210
  * [16] Nima Haghpanah and Jason Hartline  “When is pure bundling optimal?”  In _The Review of Economic Studies_ 88.3 Oxford University Press, 2021, pp. 1127–1156
  * [17] Jean-Baptiste Hiriart-Urruty and Claude Lemaréchal  “Fundamentals of convex analysis”  Springer Science & Business Media, 2004
  * [18] Bengt Holmström  “On Incentives and Control in Organizations” Ph.D. Thesis, Stanford University, 1977
  * [19] Bengt Holmström  “On the Theory of Delegation”  In _Bayesian Models in Economic Theory_ North Holland, 1984, pp. 115–141
  * [20] Matthew O Jackson and Hugo F Sonnenschein  “Overcoming incentive constraints by linking decisions”  In _Econometrica_ 75.1 Wiley Online Library, 2007, pp. 241–257
  * [21] Navin Kartik, Andreas Kleiner and Richard Van Weelden  “Delegation in veto bargaining”  In _American Economic Review_ 111.12, 2021, pp. 4046–87
  * [22] Andreas Kleiner, Benny Moldovanu and Philipp Strack  “Extreme points and majorization: Economic applications”  In _Econometrica_ 89.4 Wiley Online Library, 2021, pp. 1557–1593
  * [23] Frédéric Koessler and David Martimort  “Optimal delegation with multi-dimensional decisions”  In _Journal of Economic Theory_ 147.5 Elsevier, 2012, pp. 1850–1881
  * [24] Anton Kolotilin and Andriy Zapechelnyuk  “Persuasion meets Delegation” unpublished, 2019
  * [25] Eugen Kováč and Tymofiy Mylovanov  “Stochastic Mechanisms in Settings Without Monetary Transfers: The Regular Case”  In _Journal of Economic Theory_ 144.4, 2009, pp. 1373–1395
  * [26] Elliot Lipnowski and Doron Ravid  “Cheap talk with transparent motives”  In _Econometrica_ 88.4 Wiley Online Library, 2020, pp. 1631–1660
  * [27] Alejandro M Manelli and Daniel R Vincent  “Bundling as an optimal selling mechanism for a multiple-good monopolist”  In _Journal of Economic Theory_ 127.1 Elsevier, 2006, pp. 1–35
  * [28] Alejandro M Manelli and Daniel R Vincent  “Multidimensional mechanism design: Revenue maximization and the multiple-good monopoly”  In _Journal of Economic theory_ 137.1 Elsevier, 2007, pp. 153–185
  * [29] Albert W Marshall, Ingram Olkin and Barry C Arnold  “Inequalities: theory of majorization and its applications”  Springer, 2010
  * [30] Nahum Melumad and Toshiyuki Shibano  “Communication in Settings with No Transfers”  In _RAND Journal of Economics_ 22.2, 1991, pp. 173–198
  * [31] Robert R Phelps  “Lectures on Choquet’s theorem”  Springer, 2001
  * [32] Chris Preston  “Some Notes on Standard Borel and Related Spaces”  arXiv, 2008  DOI: 10.48550/ARXIV.0809.3066
  * [33] Jean-Charles Rochet  “A necessary and sufficient condition for rationalizability in a quasi-linear context”  In _Journal of Mathematical Economics_ 16.2 Elsevier, 1987, pp. 191–200
  * [34] Jean-Charles Rochet and Philippe Choné  “Ironing, sweeping, and multidimensional screening”  In _Econometrica_ JSTOR, 1998, pp. 783–826
  * [35] Moshe Shaked and J George Shanthikumar  “Stochastic orders”  Springer, 2007
  * [36] Alexander Shapiro  “On duality theory of conic linear problems”  In _Semi-Infinite Programming: Recent Advances_ Springer, U.S.A., 2010

##  Appendix A Omitted Proofs

  * Proof of Lemma 2.

Let $B_{r}$ denote a ball of radius $r$ around $0$ and let $U$ be a solution
to $\max\\{\int U\,\mathrm{d}\mu|U:B_{r}\rightarrow\mathbb{R},\ U\text{
convex},\ U\leq h\\}$. We will show that $U$ can be extended to a solution to
the principal’s original problem. Let $\tilde{U}$ denote the smallest convex
extension to $\mathbb{R}^{n}$ of the restriction of $U$ to $S$ [[,
see]]dragomirescu92. If $\tilde{U}$ is not feasible for the original problem
then there is $y\not\in B_{r}$ such that $\tilde{U}(y)>h(y)$ and there is
$s\in S$ such that $\tilde{U}(y)=U(s)+\nabla U(s)\cdot(y-s)$ (since
$\tilde{U}$ is the smallest convex extension). Using strong convexity of $h$
(which follows since $b$ has Lipschitz-continuous gradients, see Theorem
E.4.2.2 in [17]), one can show that $U(s)<h(s)-z(r)$, where
$z(r)\rightarrow\infty$ as $r\rightarrow\infty$.111111 Let $c^{\prime}$ denote
modulus of convexity of $h$. Then, for all $y\in B_{r}$ that lie on the line
segment from $s$ to x, and all $t\in\partial(h-\tilde{U})(y)$,
$h(s)-\tilde{U}(s)\geq[h(y)-\tilde{U}(y)]+t\cdot(s-y)+\frac{c^{\prime}}{2}\lVert
y-s\rVert^{2}.$ Since $\tilde{U}(s)=U(s)$ and the first two terms of the RHS
are positive, the claim follows. Then either $U(s^{\prime})\leq h(s)-z(r)/2$
for all $s^{\prime}\in S$ or, on a set of positive Lebesgue-measure, $\nabla
U(s^{\prime})\not\in B_{r/c}$ for some constant $c>0$ independent of $r,s$ and
$s^{\prime}$. Since $\lim_{\lVert a\rVert\rightarrow\infty}b(a)=-\infty$ by
assumption, this implies that in either case for $r$ large enough, the
principals payoff from $U$ will be less than her payoff from taking the ex-
ante optimal action. This contradicts our assumption that $U$ was optimal.
Hence, any solution can be extended to a solution of the original problem. ∎

  * Proof of Lemma 3.

Let $\mathcal{C}(X)$ denote the vector space of continuous functions on $X$
with the supremum norm and recall that its dual space is the space of (Radon)
measures on $X$, which we denote by $\mathcal{M}(X)$. Let
$\mathcal{V}:=\\{g\in\mathcal{C}(X):\forall x\in V,g(x)\geq 0\\}$; the polar
cones of $\mathcal{U}$ and $\mathcal{V}$ are defined by

$\displaystyle\mathcal{U}^{*}$
$\displaystyle:=\\{\gamma\in\mathcal{M}(X):\forall U\in\mathcal{U},\int
U\,\mathrm{d}\gamma\geq 0\\}$ $\displaystyle\mathcal{V}^{*}$
$\displaystyle:=\\{\gamma\in\mathcal{M}(X):\forall g\in\mathcal{V},\int
g\,\mathrm{d}\gamma\geq 0\\}.$

The principal’s problem can be written as $\max_{U\in\mathcal{U}}\int
U\,\mathrm{d}\mu$ subject to $h-U\in\mathcal{V}$. This is a conical linear
program and its dual is $\inf_{\gamma\in\mathcal{V}^{*}}\int
h\,\mathrm{d}\gamma$ subject to $\mu-\gamma\in U^{*}$ [[, e.g.,]]shapiro10.
Since $\mathcal{V}^{*}=\mathcal{M}_{+}(X)$ by the Riesz representation theorem
[[]p. 65]dunford-schwartz88a and $\mu-\gamma\in U^{*}$ is equivalent to
$\mu\geq_{cx}\gamma$, (D) is the dual problem.

Since there is $U\in\mathcal{U}$ such that $h-U$ is in the interior of
$\mathcal{V}$, Slater’s condition is satisfied and standard results imply that
strong duality holds [[, e.g.,]Proposition 2.8]shapiro10. Therefore, $U$ is
optimal if and only if there is a positive measure $\gamma\geq_{cx}\mu$ such
that $\int U\,\mathrm{d}\mu=\int h\,\mathrm{d}\gamma$, which implies the
result. ∎

  * Proof of Theorem 1.

Given $s\in X$, we denote by $Q(s)$ the partition element of $\mathcal{Q}$
that contains $s$.

“$\Leftarrow$”: Let $\gamma:=\int\delta_{Q(s)}\,\mathrm{d}|\mu|(s)$. Given the
properties of $\mu|_{Q}$, we conclude that $\gamma\in\mathcal{M}_{+}$ and
$\operatorname{supp}\gamma\subseteq\\{s:U(s)=h(s)\\}$. Moreover, for all
$c\in\mathcal{U}$,

$\displaystyle\int c(x)\,\mathrm{d}\gamma(x)=\int\int
c(x)\,\mathrm{d}\delta_{Q(s)}(x)\,\mathrm{d}|\mu|(s)\geq\int\int
c(x)\,\mathrm{d}\mu|_{Q(s)}\,\mathrm{d}|\mu|(s)=\int c(x)\,\mathrm{d}\mu(x).$

and equality holds for $c\equiv U$ because (i) $U$ is affine on each
$Q\in\mathcal{Q}$ and (ii) $\delta_{Q}\geq_{cx}\mu|_{Q}$ implies $\int
a(x)\,\mathrm{d}\delta_{Q}=\int a(x)\,\mathrm{d}\mu|_{Q}$ for any affine
function $a\in\mathcal{C}(X)$. Therefore, $\gamma$ is feasible for the dual
problem and satisfies the complementary slackness conditions (4) and (5). We
conclude that $U$ is optimal.

“$\Rightarrow$”: By Lemma 3, $U$ is optimal if and only if there is
$\gamma\in\mathcal{M}_{+}$ satisfying (4), (5), and $\gamma\geq_{cx}\mu$.
Letting $\mu^{+}$ and $\mu^{-}$ denote the positive and negative parts of
$\mu$, respectively, the last condition becomes
$\gamma+\mu^{-}\geq_{cx}\mu^{+}$. Since both sides of the inequality are
positive measures, Strassen’s theorem [[, see, for example,]p. 93-94]phelps01
implies that there is a dilation $D_{s}$ (that is, for each $s$, $D_{s}$ is a
probability measure with barycenter $s$) satisfying $\gamma+\mu^{-}=\int
D_{s}\,\mathrm{d}\mu^{+}(s)$.

Let $\mu|_{Q}$ be a (regular, proper) system of conditional measures (such
conditional measures exist by Example 10.4.11 in [8]), which by definition
satisfies

$\int_{X}c(s)\,\mathrm{d}\mu(s)=\int_{X}\int_{X}c(y)\,\mathrm{d}\mu|_{Q(s)}(y)\,\mathrm{d}|\mu|(s)$

for all $c\in\mathcal{C}(X)$. Letting $\alpha_{Q}:=\int
D_{s}\,\mathrm{d}\mu|_{Q}^{+}(s)-\mu|_{Q}^{-}$, we claim that there is
$\mathcal{Q}^{\prime}\subseteq\mathcal{Q}$ such that $\mathcal{Q}^{\prime}$
has $|\mu|$-measure 0 and, for all
$Q\in\mathcal{Q}\setminus\mathcal{Q}^{\prime}$, $\alpha_{Q}$ is a positive
measure that has support on $Q\cap\\{s:U(s)=h(s)\\}$.

Before proving this claim, we show that it implies the result: From the
definition of $\alpha_{Q}$ it follows that if $\alpha_{Q}$ is a positive
measure then $\mu|_{Q}(Q)\geq\alpha_{Q}(Q)\geq 0$. Also,
$\alpha_{Q}\geq_{cx}\mu|_{Q}$ since $D_{s}$ is a dilation; therefore, if
$\alpha_{Q}$ has support in $Q\cap\\{s:U(s)=h(s)\\}$ then
$\delta_{Q}\geq_{cx}\mu|_{Q}$, where $\delta_{Q}$ is a point mass at
$Q\cap\\{s:U(s)=h(s)\\}$ or the zero measure if $U(s)<h(s)$ for all $s\in Q$.
For each $Q\in\mathcal{Q}^{\prime}$, we let $\mu|_{Q}$ be the zero measure and
observe that $\mu|_{Q}$ is still a conditional measure for $\mu$ since
$\mathcal{Q}^{\prime}$ has measure 0. This proves the result.

First, suppose there is $\mathcal{Q}^{\prime}\subseteq\mathcal{Q}$ with
strictly positive $|\mu|$-measure such that, for all
$Q^{\prime}\in\mathcal{Q}^{\prime}$, the support of $\alpha_{Q^{\prime}}$ is
not a subset of the closure of $Q$. Fix arbitrary
$Q^{\prime}\in\mathcal{Q}^{\prime}$. Since the support of
$\alpha_{Q^{\prime}}$ is not contained in the closure of $Q^{\prime}$, there
is a set $A\subseteq Q^{\prime}$ of strictly positive
$\mu|_{Q^{\prime}}^{+}$-measure such that, for all $x\in A$, the support of
$D_{x}$ is not contained in the closure of $Q^{\prime}$. Since Jensen’s
inequality is strict whenever the convex function is not affine on the convex
hull of the support [[]Proposition 16.C.1]marshall79, we obtain

$\int U(s)\,\mathrm{d}\mu|_{Q^{\prime}}^{+}(s)<\int\left[\int
U(x)\,\mathrm{d}D_{s}(x)\right]\,\mathrm{d}\mu|_{Q^{\prime}}^{+}(s).$

This yields

$\displaystyle\int U(s)\,\mathrm{d}\mu(s)$ $\displaystyle=\int\left[\int
U(x)\,\mathrm{d}\mu|_{Q(s)}^{+}(x)-\int
U(x)\,\mathrm{d}\mu|_{Q(s)}^{-}(x)\right]\,\mathrm{d}|\mu|(s)$
$\displaystyle<\int\left[\int\left(\int
U(y)\,\mathrm{d}D_{x}(y)\right)\,\mathrm{d}\mu|_{Q(s)}^{+}(x)-\int
U(x)\,\mathrm{d}\mu|_{Q(s)}^{-}(x)\right]\,\mathrm{d}|\mu|(s)$
$\displaystyle=\int\int U(y)\,\mathrm{d}D_{s}(y)\,\mathrm{d}\mu^{+}(s)-\int
U(x)\,\mathrm{d}\mu^{-}(s)$ $\displaystyle=\int U(s)\,\mathrm{d}\gamma(s),$

which contradicts (5). We conclude that, except possibly on a $|\mu|$-Null
set, the support of $\alpha_{Q}$ is a subset of the closure of $Q$.

Second, we show that $\alpha_{Q(s)}$ is a positive measure for $|\mu|$-almost
every $s$: Let

$B:=\\{s\in X:s\in\operatorname{cl}Q\cap\operatorname{cl}Q^{\prime}\text{ for
}Q\neq Q^{\prime}\\},$

and note that for any $s\in B$, $U$ is not differentiable at $s$ and therefore
$U(s)<h(s)$. Since $\operatorname{supp}\gamma\subseteq\\{s:U(s)=h(s)\\}$ by
(4), $\gamma(B)=0$. Moreover, $\mu^{-}(B)=0$ because $U$ is continuously
differentiable $|\mu|$-almost everywhere by assumption. Let $\mathcal{G}$
denote the $\sigma$-algebra generated by $\mathcal{Q}$ and note that the Borel
$\sigma$-algebra on $X$ is generated by some countable algebra
$\\{A_{1},A_{2},...\\}$ [[]Propositions 3.1 and 3.3]preston08. For each $n$
and $G\in\mathcal{G}$,

$\displaystyle\int_{G}\alpha_{Q(s)}(A_{n})\,\mathrm{d}|\mu|(s)=$
$\displaystyle\int_{G}\int_{X}D_{s^{\prime}}(A_{n})\,\mathrm{d}\mu|_{Q(s)}^{+}(s^{\prime})-\mu|_{Q(s)}^{-}(A_{n})\,\mathrm{d}|\mu|(s)$
$\displaystyle=$
$\displaystyle\int_{G}D_{s}(A_{n})\,\mathrm{d}\mu^{+}(s)-\mu^{-}(A_{n}\cap G)$
$\displaystyle\geq$ $\displaystyle\left[\int_{X}D_{s}(A_{n}\cap
G)\,\mathrm{d}\mu^{+}(s)-\mu^{-}(A_{n}\cap G)\right]-\int_{X\setminus
G}D_{s}(A_{n}\cap G)\,\mathrm{d}\mu^{+}(s).$

The bracketed term equals $\gamma(A_{n}\cap G)$ and is therefore positive. The
last term is zero since

$\int_{X\setminus G}D_{s}(A_{n}\cap G)\,\mathrm{d}\mu^{+}(s)\leq\int
D_{s}(A_{n}\cap G\cap B)\,\mathrm{d}\mu^{+}(s)-\mu^{-}(A_{n}\cap G\cap
B)=\gamma(A_{n}\cap G\cap B)=0$

(recall that $\gamma(B)=\mu^{-}(B)=0$). Since $\alpha_{Q(s)}(A_{n})$ is
$\mathcal{G}$-measurable in $s$, it follows that there is a $|\mu|$-Null set
$Z_{n}$ such that $\alpha_{Q(s)}(A_{n})\geq 0$ for all $s\in X\setminus
Z_{n}$. Letting $Z:=\bigcup_{n=1}^{\infty}Z_{n}$, for all $s\in X\setminus Z$
and Borel sets $A$, $\alpha_{Q(s)}(A)\geq 0$ by Caratheodory’s extension
theorem [[, see]Theorem 1.5.6 and the comment afterward]bogachev07a.

Finally, if it is not true that for $|\mu|$-almost every $s$, the support of
$\alpha_{Q(s)}$ is a subset of $\\{s:U(s)=h(s)\\}$, then $\int
U\,\mathrm{d}\gamma<\int h\,\mathrm{d}\gamma$, contradicting (4). Moreover,
for any $s\in\operatorname{cl}Q\setminus Q$, $U$ is not differentiable at $s$
and therefore $U(s)<h(s)$ (because $U\leq h$ and $h$ is differentiable). We
conclude that there is a collection $\mathcal{Q}^{\prime}\subset\mathcal{Q}$
with $|\mu|$-measure 0 such that, for all
$Q\in\mathcal{Q}\setminus\mathcal{Q}^{\prime}$, $\alpha_{Q}$ is a positive
measure that has support on $Q\cap\\{s:U(s)=h(s)\\}$. ∎

  * Proof of Corollary 2.

Let $U$ be an optimal indirect utility and $\mathcal{Q}$ a corresponding
partition. Since $\mu|_{Q}(Q)\geq 0$ and $\mu|_{Q}\leq_{cx}\delta_{Q}$, any
pooling region121212That is, any $Q$ such that $Q\cap S$ contains strictly
more than one element. $Q\in\mathcal{Q}$ must contain types with $\nu(s)\geq
0$ and types with $\nu(s)\leq s$.

If $\nu(\underline{s})\geq 0$ and $\nu(\overline{s})\geq 0$, $\nu$ is positive
everywhere and the claim follows. So suppose $\nu(\underline{s})<0$; then
there is a pooling region $Q:=[x,y]\in\mathcal{Q}$ which contains
$\underline{s}$ and some $s$ with $\nu(s)>0$. If $\nu(y)<0$, then
$[x,y]\subseteq Q$ must hold and the claim follows. Therefore, assume
$\nu(y)\geq 0$. The measure $\delta_{Q}$ from Theorem 1 must be a point mass
at some $z\in Q$ with $\nu(z)\geq 0$ (if $\delta_{Q}$ were the zero measure or
a point mass at $z^{\prime}$ with $\nu(z^{\prime})<0$, then $\int
x-x^{*}\,\mathrm{d}\mu|_{Q}>\int x-x^{*}\,\mathrm{d}\delta_{Q}$ whenever
$x^{*}=\inf\\{x:\nu(x)\geq 0\\}$, which contradicts
$\mu|_{Q}\leq_{cx}\delta_{Q}$). It follows that $U(z)=h(z)$.

If $\nu(\overline{s})\geq 0$ then $\nu(s)\geq 0$ for all
$s\in[z,\overline{s}]$ and delegating to $[z,\overline{s}]$ is optimal. If
$\nu(\overline{s})<0$, repeating our previous argument implies that there is
an interval $[x^{\prime},y^{\prime}]\in\mathcal{Q}$ which contains
$\overline{s}$ and some $z^{\prime}$ with $\nu(z^{\prime})\geq 0$ and
$U(z^{\prime})=h(z^{\prime})$. Since $\nu(s)\geq 0$ for all
$s\in[z,z^{\prime}]$, delegating to $[z,z^{\prime}]$ is optimal. If
$\nu(\underline{s})\geq 0$ and $\nu(\overline{s})<0$, a symmetric argument
applies. ∎

  * Proof of Corollary 3.

It follows from (1) that
$\nu(s)=f(s)\left[1-\beta\frac{f^{\prime}(s)}{f(s)}\right]$ for
$s\in(\underline{s},\overline{s})$. If $\beta\geq 0$ then $\nu$ is
singlecrossing from below on $(\underline{s},\overline{s})$ (since $f$ is
logconcave) and $\nu(\underline{s})\leq 0$. The claim then follows from
Corollary 2. ∎

  * Proof of Corollary 4.

The corresponding indirect utility induces the partition with the following
elements: for any $a$ in the interior of $A$, $\\{a\\}$, and for any
$a\in\operatorname{bd}A$, the normal cone $N_{A}(a)$, which is a ray through
$a$ and orthogonal to $\operatorname{bd}A$. For any such normal ray $Q$,
condition (ii) is equivalent to $\mu|_{Q}\geq_{cx}\delta_{Q}$ by the same
argument as in Corollary 1.

“$\Leftarrow$”: Condition (i) ensures that $\mu|_{\\{a\\}}$ is positive for
all $a$ in the interior of $A$. Since it has singleton support,
$\mu|_{\\{a\\}}\geq_{cx}\delta_{\\{a\\}}$. For any normal ray $Q$,
$\mu|_{Q}\geq_{cx}\delta_{Q}$ by condition (ii) and $\mu|_{Q}(Q)\geq 0$ since
$\int_{0}^{\infty}\nu(s+x\hat{\mathbf{n}}_{A}(s))\,\mathrm{d}\lambda(s+x\hat{\mathbf{n}}_{A}(s)|ray)\geq
0$ follows from condition (ii). It follows from Theorem 1 that $U$ is optimal.

“$\Rightarrow$”: If $\nu(a)<0$ for some $a$ in the interior of $A$ then there
is a subset of $A$ with positive $|\mu|$-measure on which $\nu$ is strictly
negative, which implies $\mu|_{Q}(Q)<0$ on a set of positive measure, which
contradicts optimality of $U$. Similarly, if $\nu(a)<0$ for some
$a\in\operatorname{bd}A$ then it can be shown that $\mu|_{Q}(Q)<0$ on a set of
positive measure, which contradicts optimality of $U$ by Theorem 1.

If condition (ii) is violated, $\mu|_{Q}\not\geq_{cx}\delta_{Q}$ on a set of
positive measure, which again contradicts optimality of $U$ by Theorem 1. ∎