thmTheorem lemLemma propositionProposition

# Optimality of weighted contracts for multi-agent contract design with a
budget

Sumit Goel Wade Hann-Caruthers 111Supported at the Technion by a Zuckerman
fellowship. NYU Abu Dhabi<EMAIL_ADDRESS>0000-0003-3266-9035Technion
- Israel Institute of Technology<EMAIL_ADDRESS>0000-0002-4273-6249

(
(Link to latest version))

###### Abstract

We study a contract design problem between a principal and multiple agents.
Each agent participates in an independent task with binary outcomes (success
or failure), in which it may exert costly effort towards improving its
probability of success, and the principal has a fixed budget which it can use
to provide outcome-dependent rewards to the agents. Crucially, each agent’s
reward may depend not only on whether she succeeds or fails, but also on
whether other agents succeed or fail, and we assume the principal cares only
about maximizing the agents’ probabilities of success, not how much of the
budget it expends.

We first show that a contract is optimal for some objective if and only if it
gives no reward to unsuccessful agents and always splits the entire budget
among the successful agents. An immediate consequence of this result is that
piece-rate contracts and bonus-pool contracts, two types of contracts which
are well-studied and motivated in the literature on multi-agent contract
design, are never optimal in this setting. We then show that for any
objective, there is an optimal priority-based weighted contract, which assigns
positive weights and priority levels to the agents, and splits the budget
among the highest-priority successful agents, with each such agent receiving a
fraction of the budget proportional to her weight. This result provides a
significant reduction in the dimensionality of the principal’s optimal
contract design problem and gives an interpretable and easily implementable
optimal contract.

Finally, we discuss an application of our results to the design of optimal
contracts with two agents and quadratic costs. In this context, we find that
the optimal contract assigns a higher weight to the agent whose success it
values more, irrespective of the heterogeneity in the agents’ cost parameters.
This suggests that the structure of the optimal contract depends primarily on
the bias in the principal’s objective and is, to some extent, robust to the
heterogeneity in the agents’ cost functions.

##  1 Introduction

Consider a principal who has assigned individual tasks to multiple agents. The
agents exert some effort towards succeeding in their respective tasks, which
determines their probability of success. The principal does not observe the
effort exerted by the participants, but gets to observe whether the agents
succeeded or failed. For instance, consider a tech firm running a
crowdsourcing contest in which the participants work towards coming up with an
algorithm to solve a programming problem. The tech firm can check if a
participant’s submission works by running it on some test cases, but cannot
directly observe the effort exerted by the participants. Alternatively,
consider a sales manager for a firm who has hired some salespeople to sell the
firm’s product. The manager can observe if the salesperson was able to sell
the product or not, but cannot directly observe the effort that the
salesperson exerted towards making the sale. For such environments, we study
the principal’s problem of finding a contract, which is a mapping from
observed outcomes to a reward for each agent, so as to incentivize the agents
to expend effort into increasing their probability of success.

This environment presents a classic example of the hidden action assumption in
principal-agent models leading to problems of moral hazard. While there is a
vast literature studying such problems, it typically assumes that even though
the principal suffers a monetary cost from providing higher rewards/wages, it
is unconstrained in its capacity to reward the agents. But there are important
settings in which the principal might be budget constrained, and additionally,
might not care about how much of this budget it exhausts in incentivizing the
agents. For instance, the sales manager might be endowed with an exogenous and
fixed budget by the firm that it can use towards rewarding its sales force,
and the manager might not care how much of this budget it exhausts as long as
it able to get the sales in. For the tech firm, the returns from getting a
successful submission might be substantially higher than the cost of rewarding
the agents, and so it may not care so much about the expenses involved in
providing the rewards. With such considerations in mind, we consider the
principal’s contract design problem under the assumption that it is budget
constrained and that it does not care about how much of the budget is
exhausted in rewarding the participants.

Our first result identifies a class of contracts whose equilibria characterize
the Pareto frontier of the success probabilities that can be sustained in
equilibrium. This class of contracts, which we refer to as successful-get-
everything (SGE) contracts, has the property that only the successful agents
are rewarded, and in addition, the entire budget is split among them. An
important consequence of this result is that some contracts that have been
well-studied and motivated in the literature, like piece-rate contracts (each
agent gets a fixed reward if it succeeds and nothing if it fails) and bonus-
pool contracts (a group of agents get rewarded only if all of them succeed),
actually lead to Pareto inferior equilibria in our setting. In comparison to
these contracts, which support fully independent or fully joint evaluation of
the agents’ performance, SGE contracts can be interpreted as inducing
competition among the agents, since they are all competing for a fixed budget,
and their share of the prize is typically decreasing in the set of agents that
succeed. Thus, our result suggests that a budget-constrained principal who
does not care about how much of the budget it exhausts is better off designing
contracts that induce competition among the agents as compared to those that
foster teamwork or even treat them independently.

Next, we identify a natural subclass of SGE contracts, which we refer to as
priority-based weighted (PW) contracts, and we show that these contracts are
sufficient to implement the Pareto frontier. A priority-based weighted
contract assigns positive weights and priority levels to the agents, and
splits the budget among the highest-priority successful agents, with each such
agent receiving a fraction of the budget proportional to her weight. These
contracts can actually be well-approximated by simple weighted contracts which
are PW contracts in which all agents have the same priority. Since the
weighted contracts are defined by just a weight for each agent, the optimal
contract is easy to interpret, and the dimensionality of the search space is
reduced from exponential to linear in the number of agents. In other words, a
principal, whose objective is monotone increasing in the success
probabilities, can simply optimize over the much smaller class of weighted
contracts as compared to optimizing over all contracts or all SGE contracts.
We further show that for any equilibrium on the Pareto frontier there is a
unique PW contract that implements it, and hence the set of PW contracts is
minimal among sets of contracts that implement the Pareto frontier.

Lastly, we stress that both our results make no assumptions about
heterogeneity of the agents’ cost functions. This allows us to investigate the
question of how the structure of the optimal contract might depend on
environmental features like the heterogeneity between the agents and the
inherent bias of the principal. As an application, we study this for the
special case of two agents with quadratic costs and find that under the
optimal contract, the principal assigns a higher weight to the agent whose
success it values more, irrespective of the discrepancy in the agents’ cost
parameters. In particular, if the sales manager derives equal value from the
potential sales made by two salespeople, its optimal contract assigns equal
weights to them, irrespective of how talented each of them might be. Perhaps
surprisingly, this suggests that in some settings, the structure of the
optimal contract exhibits a degree of robustness to heterogeneity among the
agents.

### Related literature

There is a vast literature on principal-agent problems under moral hazard. In
the canonical model with a single agent (Holmström [18], Grossman and Hart
[15]), the principal offers a wage contract that defines the agent’s payment
as a function of its observed output, and then the agent chooses some
unobserved action (effort) that determines the distribution over outputs. A
key finding is that optimal contracts reward the agent for output realizations
that are informative about the target level of effort (informativeness
principle), and may therefore be non-monotone in output. There has since been
significant work studying variants of this single-agent model incorporating
flexible actions (Georgiadis et al. [13]), multiple tasks (Holmstrom and
Milgrom [21], Bond and Gomes [4]), bounded payments (Jewitt et al. [25]),
combinatorial actions (Dütting et al. [9], Ezra et al. [11]), and
informationally robust design (Carroll [5], Zhang [40]). See Georgiadis [12],
Holmström [20] for surveys of this literature. In particular, Bond and Gomes
[4] study a related model in which a single agent chooses effort levels for
multiple tasks, each of which may succeed or fail, and finds that there is
excessive concentration on certain tasks and the structure of the optimal
contract is fragile.

Our paper contributes to the literature studying a principal contracting with
multiple agents. A major focus in this domain has been on the comparison of
independent performance evaluation (through piece-rate contracts), joint
performance evaluation (through bonus-pool contracts), and relative
performance evaluation (through rank-order tournaments) in incentivizing the
agents. Even though relative performance evaluation is noisier and joint
performance evaluation may lead to free riding, the literature has identified
conditions under which the optimal contract incorporates features of rank-
order tournaments (Green and Stokey [14], Lazear and Rosen [27], Malcomson
[28], Mookherjee [30], Nalebuff and Stiglitz [31]) or bonus-pool contracts
(Itoh [24], Imhof and Kräkel [22], Kambhampati [26]). A related stream of
literature with multiple agents has studied moral hazard in teams where the
agents’ actions jointly determine the team output and the principal cannot
disentangle the contributions of individual agents (Babaioff et al. [1],
Holmstrom [19], Battaglini [3], Che and Yoo [7], Winter [39], Dütting et al.
[10], Ezra et al. [11], Prendergast [32], Dai and Toikka [8]). Some other
related papers include Castiglioni et al. [6], Haggiag et al. [16], Baiman and
Rajan [2], who study the multi-agent contract design problem from very
different perspectives.

##  2 Model

There is a principal and $n$ risk-neutral agents. Each agent $i\in[n]$
participates in an independent task, in which it may succeed or fail. Each
agent chooses a success probability, $p_{i}\in[0,1]$, and incurs a cost of
$c_{i}(p_{i})$ in doing so. We assume that the each agent’s cost function
$c_{i}$ is strictly convex with $c_{i}(0)=c_{i}^{\prime}(0)=0$ and
$c_{i}^{\prime\prime}>1$.

The principal would like to incentivize the agents to maximize the probability
that they succeed in their tasks. The principal does not observe the agents’
choices $p_{i}$, only whether each agent succeeds or fails in her task. Thus,
the principal can design a contract that rewards the agents only based on the
outcomes of the tasks. Additionally, we assume that the principal has a fixed
budget $B=1$222The choice of $B=1$ is for convenience in exposition; the same
results hold with an arbitrary $B>0$ with the assumption that
$c_{i}^{\prime\prime}>B$. that it can use to incentivize the agents so that
the total reward for the agents under any outcome cannot exceed the budget.

######  Definition 2.1.

A contract is a function
$f=(f_{1},\dots,f_{n}):2^{[n]}\to\mathbb{R}_{+}^{[n]}$ such that

  * •

$f_{i}(S)\geq 0$ (limited liability) and

  * •

$\sum_{j\in[n]}{f_{j}(S)}\leq 1$ (budget constraint)

for each $i\in[n]$ and $S\subseteq[n]$.

Under the contract $f$, if $S$ is the set of agents who succeed, then each
agent $i$ receives the reward $f_{i}(S)$. Thus, each agent’s reward may depend
not only on whether she succeeds, but also on the success of the other agents.
We will denote by $\mathcal{F}$ the set of contracts.

We assume that the principal cares only about maximizing the agents’
probabilities of success, not how much of the budget it expends. Formally, we
assume the principal’s preferences are represented by a continuous, strictly
increasing objective $V(p_{1},\dots p_{n})$. For example, the objective for a
risk-neutral principal who makes a profit of $w_{i}$ if agent $i$ succeeds in
her task would be given by

$\displaystyle V(p_{1},\dots,p_{n})=\sum_{i\in[n]}{w_{i}p_{i}}.$

A contract $f\in\mathcal{F}$ defines a normal-form game between the $n$
agents, in which each agent chooses $p_{i}\in[0,1]$ and agent $i^{\prime}s$
payoff under the profile $p=(p_{1},\dots,p_{n})$ is

$u_{i}(p)=\mathbb{E}[f_{i}(S)]-c_{i}(p_{i})=\sum_{S\subset[n]}f_{i}(S){\Pr}^{[n]}_{p}(S)-c_{i}(p_{i})$

where

${\Pr}^{[n]}_{p}(S)=\prod_{i:i\in S}p_{i}\prod_{j:j\in[n]\setminus
S}(1-p_{j}).$

Observe that since the expected reward
$\sum_{S\subset[n]}f_{i}(S){\Pr}^{[n]}_{p}(S)$ is linear in $p_{i}$ and the
cost functions are strictly convex, each agent’s utility function $u_{i}$ is
strictly concave in $p_{i}$. It follows then that for any contract
$f\in\mathcal{F}$, a pure-strategy Nash equilibrium exists333While we haven’t
been able to establish uniqueness in general, we can use the diagonally strict
concavity condition of Rosen [33] to show that equilibrium is unique if the
cost functions are sufficiently convex.. We will denote by $E(f)$ the set of
equilibria for the contract $f$, and by $E^{-1}(p)$ the set of contracts for
which $p$ is an equilibrium. We further denote by $\mathcal{E}$ the set of
profiles that can be induced as equilibria of some contract $f$:

$\displaystyle\mathcal{E}:=\\{p\in[0,1]^{n}\,:\,p\in E(f)\text{ for some
}f\in\mathcal{F}\\}.$

We say that $p\in\mathcal{E}$ is Pareto optimal444This definition of Pareto
optimality is non-standard; however, as we show, maximal elements of
$\mathcal{E}$ correspond to maximal equilibrium utility profiles in a sense
that we make precise later. if it is a maximal element of $\mathcal{E}$, and
we denote by $\mathcal{P}$ the set of Pareto optimal profiles.

The marginal utility of agent $i$ at profile $p$ is

$\displaystyle\dfrac{\partial u_{i}(p)}{\partial
p_{i}}=r_{i}(f,p_{-i})-c_{i}^{\prime}(p_{i}),$

where

$\displaystyle r_{i}(f,p_{-i})=\mathbb{E}[f_{i}(S)\,|\,i\in
S]-\mathbb{E}[f_{i}(S)\,|\,i\notin
S]=\sum_{S\subset[n]_{-i}}(f_{i}(S\cup\\{i\\})-f_{i}(S)){\Pr}^{[n]_{-i}}_{p_{-i}}(S)$

is agent $i$’s expected gain in reward from succeeding as compared to failing
in her task. It follows from concavity of $u_{i}$ that agent $i$ has a unique
best response given by the solution to the first order condition

$c_{i}^{\prime}(p_{i})=\max\\{0,r_{i}(f,p_{-i})\\}.$ (1)

We denote this unique best response by $b_{i}(f,p_{-i}).$ Note that the
assumption that $c_{i}^{\prime\prime}>1$ implies $c_{i}^{\prime}(1)>1$.
Together with the fact that under the principal’s budget constraint
$r_{i}(f,p_{-i})\leq 1$, this ensures that $b_{i}(f,p_{-i})<1$.

Finally, the principal’s problem is then to find a contract $f\in\mathcal{F}$
and an equilibrium $p\in E(f)$ which maximizes $V(p)$, Since $V$ is increasing
and continuous, it is sufficient to find a profile $p^{*}\in
argmax_{p\in\mathcal{P}}{V(p)}$ and a contract $f^{*}\in E^{-1}(p^{*})$. In
this paper, we will provide a characterization of $\mathcal{P}$ and a
canonical contract for each $p\in\mathcal{P}$. We will use this
characterization to solve for some natural objectives of the principal.

##  3 Main results

To set the stage, consider the single-agent case. In this case, a contract $f$
specifies the agent’s reward when she is successful, $f(\\{1\\})$, and her
reward when she fails, $f(\emptyset)$. The agent’s relative reward is

$\displaystyle r_{1}(f)=f(\\{1\\})-f(\emptyset)$

and her best response is

$\displaystyle b_{1}(f)=(c_{1}^{\prime})^{-1}(f(\\{1\\})-f(\emptyset)).$

Under any objective $V$, the principal wishes to maximize $b_{1}(f)$. Hence,
the principal should choose a contract $f$ that maximizes
$f(\\{1\\})-f(\emptyset)$. Since $f(\\{1\\})\leq 1$ and $f(\emptyset)\geq 0$,
this is uniquely achieved by using the contract $f$ with $f(\\{1\\})=1$ and
$f(\emptyset)=0$. Hence, the principal rewards the agent with the entire
budget if she is successful and gives her no reward if she fails.

Our first result shows that aspects of this optimal contract generalize when
there is more than one agent. We say that a contract is successful-get-
everything if it gives each agent no reward when she fails and it splits the
entire budget among those agents who are successful.

######  Definition 3.1.

A contract $f$ is successful-get-everything (SGE) if

  * •

$f_{i}(S)=0$ whenever $i\notin S$ and

  * •

$\sum_{i\in S}{f_{i}(S)}=1$ whenever $S\neq\emptyset$.

We denote by $\mathcal{F}_{SGE}$ the set of SGE contracts.

Suppose $p\in E(f)$. Then, $p\in\mathcal{P}$ if and only if
$f\in\mathcal{F}_{SGE}$.

Observe that contracts like a piece-rate contract (where each agent $i$ gets a
fixed reward if she is successful and $0$ otherwise), or a bonus pool contract
(where each agent gets a nonzero share of the budget only if all agents
succeed), are never successful-get-everything. It follows from Theorem 3 that
such contracts always produce Pareto inferior outcomes, and so the choice of
any such contract would be strictly suboptimal for any objective. In
comparison, SGE contracts induce competition between the agents as they are
all competing for a fixed budget and their share of the reward will typically
decrease (though not necessarily) as more agents are successful. Theorem 3
says that such contracts always lead to Pareto optimal equilibria. Thus, the
result suggests that in environments where the principal’s benefit from
agents’ success greatly exceeds the cost of incentivizing them, or if the
principal operates with an exogenously provided budget, so that it is not
concerned about budget exhaustion, fostering competition among the agents
through successful-get-everything contracts creates stronger incentives than
promoting teamwork via joint performance evaluation through bonus-pool
contracts or independent performance assessment through piece-rate contracts.

Proving Theorem 3 is quite involved and nontrivial in comparison to the
single-agent case. Intuitively, if the principal chooses a contract which is
not successful-get-everything, it can adjust the contract in such a way that
$r_{i}(f,p_{-i})$ increases for some agent. However, because $p$ is an
equilibrium object, it is not true that an arbitrary increase in reward to a
successful agent or decrease in reward to an unsuccessful agent will
necessarily produce a Pareto improvement. The proof of Theorem 3 essentially
demonstrates that there is always some adjustment that the principal can make
that will produce a Pareto improvement.

Observe that the set of SGE contracts is $\Theta(n2^{n})$-dimensional, and a
typical SGE contract is complex and hard to interpret. However, as our next
result shows, the principal can optimize over an $(n-1)$-dimensional, more
interpretable set of contracts. We say that $f$ is a weighted contract if
there exist $(\lambda_{1},\dots,\lambda_{n})$ with $\lambda_{i}>0$ such that

$\displaystyle f_{i}(S)=\begin{cases}\frac{\lambda_{i}}{\sum_{j\in
S}{\lambda_{j}}},&\text{if}\,i\in S\\\ 0,&\text{otherwise}\end{cases}$

Weighted contracts assigns weights to the agents and reward each successful
agent with a fraction of the budget proportional to her weight. While weighted
contracts alone are insufficient to implement the Pareto frontier, the
following class of contracts provides a slight generalization which is
sufficient.

######  Definition 3.2.

A contract $f$ is a priority-based weighted (PW) contract if there are weights
$(\lambda_{1},\dots,\lambda_{n})$ with $\lambda_{i}>0$ and a non-strict
ordering $\succcurlyeq$ on the agents such that

$\displaystyle
f_{i}(S)=\begin{cases}\frac{\lambda_{i}}{\sum_{j\in\text{Top}_{\succcurlyeq}(S)}{\lambda_{j}}},&\text{if}\,i\in\text{Top}_{\succcurlyeq}(S)\\\
0,&\text{otherwise}\end{cases}$

where $\text{Top}_{\succcurlyeq}(S)=\\{i\in S\,:\,i\succcurlyeq j\,\,\forall
j\in S\\}$.

Priority-based weighted contracts reward each highest-priority successful
agent with a fraction of the budget proportional to her weight. We denote by
$\mathcal{F}_{W}$ and $\mathcal{F}_{PW}$ the set of weighted and priority-
based weighted contracts, respectively. Note that
$\mathcal{F}_{W}\subset\mathcal{F}_{PW}\subset\mathcal{F}_{SGE}$.

If $p\in\mathcal{P}$, there is a unique contract $f\in\mathcal{F}_{PW}$ such
that $p\in E(f)$.

In words, if $p$ is Pareto optimal, then there is a unique priority-based
weighted contract that implements $p$. Note that since this contract is
unique, the set of PW contracts is minimal among sets of contracts that
implement the Pareto frontier. As a consequence of Theorem 3, it follows that
it is sufficient for the principal to optimize over the set of PW contracts.

######  Corollary 1.

For any strictly increasing, continuous objective $V(p)$,

$\sup_{f\in\mathcal{F}}\sup_{p\in
E(f)}V(p)=\max_{f\in\mathcal{F}_{PW}}\max_{p\in E(f)}V(p).$

We note that Theorems 3 and 3 hold irrespective of the heterogeneity in the
agents cost functions. To illustrate our results and investigate how the
structure of the optimal contract may depend on the heterogeneity of the cost
functions, we solve a tractable but nontrivial example with two agents,
quadratic costs, and linear objective.

Suppose $n=2$, $c_{i}(p_{i})=\frac{1}{2}C_{i}p_{i}^{2}$ with $C_{i}>1$, and
$V(p_{1},p_{2})=wp_{1}+\cdot p_{2}$. Then, the optimal contract, defined by
$\lambda_{1}(w)$, takes the form

$f_{i}(S)=\begin{cases}0,&\text{ if }i\notin S\\\ 1,&\text{ if }S=\\{i\\}\\\
\lambda_{i}(w),&\text{ if }S=\\{1,2\\}\end{cases},$

where $\lambda_{2}(w)=1-\lambda_{1}(w)$. Moreover, $\lambda_{1}(w)$ is
increasing in $w$ and in particular,

$\lambda_{1}(w)=\begin{cases}0,&\text{ if
}w\leq\frac{C_{1}C_{2}-C_{1}}{C_{1}C_{2}+C_{2}-1}\\\ \frac{1}{2},&\text{ if
}w=1\\\ 1,&\text{ if
}w\geq\frac{C_{1}C_{2}+C_{1}-1}{C_{1}C_{2}-C_{2}}\end{cases}.$

###### Proof.

We know from Theorem 3 that we can restrict attention to PW contracts. And
with only two agents, the set of PW contracts can be parametrized by a single
parameter $\lambda$, where $f_{i}(S)=0$ whenever $i\notin S$, $f_{i}(S)=1$
whenever $S=\\{i\\}$, and $f_{1}(\\{1,2\\})=1-f_{2}(\\{1,2\\})=\lambda$. The
equilibrium conditions for this contract from equation 1 are

$\displaystyle C_{1}p_{1}$ $\displaystyle=1-p_{2}+\lambda p_{2}$
$\displaystyle C_{2}p_{2}$ $\displaystyle=1-p_{1}+(1-\lambda)p_{1}.$

For each $\lambda$, this system of equations has a unique solution:

$p_{1}(\lambda)=\frac{C_{2}-(1-\lambda)}{C_{1}C_{2}-\lambda(1-\lambda)}\quad
p_{2}(\lambda)=\dfrac{C_{1}-\lambda}{C_{1}C_{2}-\lambda(1-\lambda)}\cdot$ (2)

Hence, the principal’s problem is equivalent to:

$\displaystyle\max_{\lambda\in[0,1]}{wp_{1}(\lambda)+p_{2}(\lambda)}.$

Using the first order condition, this is maximized either at $\lambda=0$, or
$\lambda=1$, or where

$\displaystyle\frac{p_{2}^{\prime}(\lambda)}{p_{1}^{\prime}(\lambda)}=-w\cdot$

Note that

$\displaystyle
p_{1}^{\prime}(\lambda)=\frac{(C_{1}C_{2}-\lambda(1-\lambda))-(C_{2}-(1-\lambda))(2\lambda-1))}{(C_{1}C_{2}-\lambda(1-\lambda))^{2}}=\frac{C_{1}C_{2}-C_{2}(2\lambda-1)-(1-\lambda)^{2}}{(C_{1}C_{2}-\lambda(1-\lambda))^{2}}$

and

$\displaystyle
p_{2}^{\prime}(\lambda)=\frac{-(C_{1}C_{2}-\lambda(1-\lambda))-(C_{1}-\lambda)(2\lambda-1)}{(C_{1}C_{2}-\lambda(1-\lambda))^{2}}=\frac{-C_{1}C_{2}-C_{1}(2\lambda-1)+\lambda^{2}}{(C_{1}C_{2}-\lambda(1-\lambda))^{2}}$

so

$\displaystyle\frac{p_{2}^{\prime}(\lambda)}{p_{1}^{\prime}(\lambda)}=\frac{-C_{1}C_{2}-C_{1}(2\lambda-1)+\lambda^{2}}{C_{1}C_{2}-C_{2}(2\lambda-1)-(1-\lambda)^{2}}=-\frac{C_{1}}{C_{2}}\cdot\frac{-\lambda^{2}/C_{1}+2\lambda+C_{2}-1}{-(1-\lambda)^{2}/C_{2}+2(1-\lambda)+C_{1}-1}$

Now observe that the numerator is increasing for $\lambda<C_{1}$ and the
denominator is decreasing for $\lambda>-(C_{2}-1)$. In particular, the
fraction is monotonically strictly increasing for $0<\lambda<1$, so
$\frac{p_{2}^{\prime}(\lambda)}{p_{1}^{\prime}(\lambda)}$ is monotonically
strictly decreasing. It follows then that there is a function $\lambda_{1}(w)$
such that the unique optimal choice of $\lambda$ is
$\lambda_{1}\left(w\right)$ and it is increasing in $w$. In particular,

$\displaystyle\frac{p_{2}^{\prime}(\lambda)}{p_{1}^{\prime}(\lambda)}\leq\frac{p_{2}^{\prime}(0)}{p_{1}^{\prime}(0)}=-\frac{C_{1}}{C_{2}}\cdot\frac{C_{2}-1}{-1/C_{2}+C_{1}+1}=-\frac{C_{1}C_{2}-C_{1}}{C_{1}C_{2}+C_{2}-1}$

and

$\displaystyle\frac{p_{2}^{\prime}(\lambda)}{p_{1}^{\prime}(\lambda)}\geq\frac{p_{2}^{\prime}(1)}{p_{1}^{\prime}(1)}=-\frac{C_{1}}{C_{2}}\cdot\frac{-1/C_{1}+C_{2}+1}{C_{1}-1}=-\frac{C_{1}C_{2}+C_{1}-1}{C_{1}C_{2}-C_{2}}$

Now if $w\leq-\frac{p_{2}^{\prime}(0)}{p_{1}^{\prime}(0)}$, the objective is
decreasing in $\lambda$ and thus $\lambda_{1}(w)=0$. And if
$w\geq-\frac{p_{2}^{\prime}(1)}{p_{1}^{\prime}(1)}$, the objective is
increasing in $\lambda$ and thus $\lambda_{1}(w)=1$.

Lastly, observe that

$\displaystyle\frac{p_{2}^{\prime}(\frac{1}{2})}{p_{1}^{\prime}(\frac{1}{2})}=-1$

irrespective of the costs $C_{1},C_{2}$. And thus, if $w_{1}=w_{2}$, we get
that $\lambda^{*}=\frac{1}{2}$ no matter how heterogeneous the agents are.

∎

With two agents, the set of PW contracts is parametrized by a single parameter
$\lambda$ that represents agent 1’s share of the budget when both agents
succeed, so that $f_{i}(S)=0$ whenever $i\notin S$, $f_{i}(S)=1$ whenever
$S=\\{i\\}$, and $f_{1}(\\{1,2\\})=1-f_{2}(\\{1,2\\})=\lambda$. Using equation
1, we solve for the unique equilibrium of such a contract to get that

$p_{1}(\lambda)=\frac{C_{2}-(1-\lambda)}{C_{1}C_{2}-\lambda(1-\lambda)}\quad\quad\quad
p_{2}(\lambda)=\dfrac{C_{1}-\lambda}{C_{1}C_{2}-\lambda(1-\lambda)}.$

With this, the principal’s problem becomes
$\max_{\lambda\in[0,1]}wp_{1}(\lambda)+p_{2}(\lambda)$. Theorem 3 follows from
a straightforward analysis of the first-order condition.

As Theorem 3 demonstrates, says that agent $1$’s share $\lambda_{1}(w)$ is
increasing in $w$, and perhaps more surprisingly, $\lambda_{1}(1)=\frac{1}{2}$
regardless of the $C_{i}$. Hence, if the principal cares equally about the
success of the two agents, it is optimal for the principal to design a
symmetric weighted contract that assigns equal weight to the two agents, even
if the agents’ costs are heterogeneous. More generally, the principal assigns
a higher weight to the agent whose success it values more, though the exact
weights might depend on the cost parameters. Thus, Theorem 3 suggests that the
structure of the optimal contract is, to some extent, robust to the
heterogeneity in the cost functions.

We finish the discussion of this example by comparing the performance of PW
contracts with that of piece-rate and bonus pool contracts. First, consider a
piece-rate contract where agent $i$ receives a reward of $\lambda_{i}$ if she
succeeds and $0$ otherwise. Under such a contract,
$p_{i}^{*}=\frac{\lambda_{i}}{C_{i}}$. Observe that for $\lambda\in(0,1)$,
$p_{i}^{*}<p_{i}(\lambda)$ for both agents, and for $\lambda\in\\{0,1\\}$,
$p_{i}^{*}<p_{i}(\lambda)$ for one of the agents. Hence, by increasing each
agent’s reward when she alone succeeds from $\lambda_{i}$ to the entire
budget, the principal can induce at least one of the agents to strictly
increase their probability of succeeding. Next, under a bonus-pool contract
where agent $i$ receives a reward of $\lambda_{i}$ if both agents succeed and
a reward of $0$ otherwise, both agents choose a probability of success of $0$
in equilibrium; hence, every PW contract is better than every bonus-pool
contract!

##  4 Pareto optimality

In this section, we will introduce and discuss the ideas and techniques that
are used to obtain the characterization of optimal contracts given in Theorem
3.

First, we show that a principal with arbitrary objectives (not necessarily
increasing in $p_{i}$) can without loss of generality focus on contracts in
which agents who fail get nothing.

######  Definition 4.1.

A contract $f$ is failures-get-nothing (FGN) if $f_{i}(S)=0$ whenever $i\notin
S$.

We denote by $\mathcal{F}_{FGN}$ the set of FGN contracts. Note that every SGE
contract is FGN.

If $p\in E$, there is a contract $g\in\mathcal{F}_{FGN}$ such that $p\in
E(g)$.

###### Proof.

Let $f\in\mathcal{F}$ be a contract for which $p$ is an equilibrium. Consider
the contract $g$ defined by

$\displaystyle g_{i}(S)=\begin{cases}\lambda_{i}f_{i}(S),&\text{ if }i\in S\\\
0,&\text{ otherwise }\end{cases}.$

where

$\displaystyle\lambda_{i}=\begin{cases}\dfrac{r_{i}(f,p_{-i})}{\mathbb{E}[f_{i}(S)\,|\,i\in
S]}&\text{ if }p_{i}>0\\\ 0&\text{ if }p_{i}=0.\end{cases}.$

Notice that it follows from the first-order condition in equation 1 that
$\lambda_{i}\leq 1$ so that $g$ is indeed an FGN contract. Now if $p_{i}>0$,
agent $i$’s marginal utility at profile $p$ under the contract $g$ is

$\displaystyle\dfrac{\partial u_{i}(p)}{\partial p_{i}}$
$\displaystyle=\mathbb{E}[g_{i}(S)\,|\,i\in S]-c_{i}^{\prime}(p_{i})$
$\displaystyle=\lambda_{i}\mathbb{E}[f_{i}(S)\,|\,i\in
S]-c_{i}^{\prime}(p_{i})$
$\displaystyle=r_{i}(f,p_{-i})-c_{i}^{\prime}(p_{i})$ $\displaystyle=0,$
$\displaystyle(\text{because }p\in E(f))$

so by concavity of payoffs, $b_{i}(g,p_{-i})=p_{i}$. If $p_{i}=0$, then
$g_{i}(S)=0$ for all $S$, so $b_{i}(g,p_{-i})=0=p_{i}$. Hence, $p\in E(g)$. ∎

Observe that, given an equilibrium profile $p\in\mathcal{E}$, the utilities of
the agents at $p$ generally depend on the choice of contract used to induce
$p$. For instance, $p_{i}=0$ for all $i\in[n]$ is the unique equilibrium under
contract $f$, defined by $f_{i}(S)=0$ for all $i\in[n]$ and $S\subset[n]$, and
also under the contract $g$, defined by $g_{i}(S)=0$ for $i\neq 1$ and
$g_{1}(S)=1$ for all $S\subset[n]$. But the equilibrium utility of agent $1$
is $0$ under $f$ and $1$ under $g$. However, as the following result shows, an
agent’s utility at $p$ is the same under every FGN contract for which $p$ is
an equilibrium.

If $f\in\mathcal{F}_{FGN}$ and $p\in E(f)$, then

$\displaystyle u_{i}(p)=p_{i}\cdot c_{i}^{\prime}(p_{i})-c_{i}(p_{i})$

under $f$ for every agent $i$.

###### Proof.

Since $f\in\mathcal{F}_{FGN}$, agent $i$’s utility at profile $p$ is

$\displaystyle u_{i}(p)=p_{i}\cdot r_{i}(f,p_{-i})-c_{i}(p_{i}).$

Observe that $r_{i}(f,p_{-i})\geq 0$ since $f\in\mathcal{F}_{FGN}$ And since
$p\in E(f)$, it follows from equation 1 that
$r_{i}(f,p_{-i})=c_{i}^{\prime}(p_{i})$ and the result follows. ∎

It follows from Lemmas 4 and 4 that for any $p\in\mathcal{E}$, we can write
$u(p)$ to unambiguously refer to the utility profile under any FGN contract
$f\in E^{-1}(p)$. Note that since the agents’ cost functions are strictly
concave,

$\displaystyle\frac{d}{dx}(x\cdot c_{i}^{\prime}(x)-c_{i}(x))=x\cdot
c_{i}^{\prime\prime}(x)>0$

for $x\in(0,1)$, so $u(p)$ is strictly increasing in $p$. Denote by
$\mathcal{U}$ the set of equilibrium utility profiles,

$\displaystyle\mathcal{U}:=\\{u\in\mathbb{R}^{[n]}\,:\,u(p)=u\text{ for some
}p\in E\\}.$

######  Corollary 2.

If $p\in\mathcal{E}$, then $p\in\mathcal{P}$ if and only if $u(p)$ is a
maximal element of $\mathcal{U}$.

This result squares our nonstandard definition of Pareto optimality with the
standard notion. An interesting consequence is that a principal restricted to
using FGN contracts who cared about maximizing the agents’ utilities rather
than their success probabilities could still maximize over $\mathcal{P}$, and
from Theorem 3, maximize over the class of PW contracts.

As described above, arbitrarily increasing the reward for some agent in the
case of success or decreasing the reward of some agent in case of failure does
not necessarily result in a Pareto improvement, since the increase in one
agents’ probability of success may incentivize another agent to decrease her
probability of success. However, in the case where some agent chooses
$p_{i}=0$, there is a simple modification that induces her to increase her
probability of success without affecting the other agents’ incentives. As a
consequence, it follows that every agent chooses a nonzero probability of
success in every Pareto optimal equilibrium profile.

If $p\in\mathcal{P}$, then $p_{i}>0$ for all $i$.

###### Proof.

Let $f\in E^{-1}(p)$ be an FGN contract, and suppose $p_{k}=0$. Consider the
contract $g$ where $g_{i}(S)=f_{i}(S\setminus\\{k\\})$ for $i\neq k$ and

$g_{k}(S)=\begin{cases}1,&\text{ if }S=\\{k\\}\\\ 0,&\text{ otherwise
}\end{cases}$

Let $p_{k}^{\prime}=b_{k}(g,p_{-i})$, and let
$p^{\prime}=(p_{k}^{\prime},p_{-k})$. Observe that since $b_{k}(g,p_{-i})>0$,
$p_{k}^{\prime}>0$, and for $i\neq k$,
$r_{i}(g,p_{-i}^{\prime})=r_{i}(f,p_{-i})$, so
$b_{i}(g,p_{-i^{\prime}})=b_{i}(f,p_{-i})=p_{i}$. Hence, $p^{\prime}\in E(g)$
and $p^{\prime}$ dominates $p$. Thus, if $p_{k}=0$ for some $k$, then
$p\notin\mathcal{P}$, and the result follows. ∎

An important and useful consequence of Lemma 4 is that if $p$ is Pareto
optimal, it must be that $0<p_{i}<1$ for all $i\in[n]$, and therefore, for any
$S\subset[n]$, $\Pr^{[n]}_{p}(S)>0$.

In the following lemma, we note a useful property of $FGN$ and $SGE$
contracts.

For any $p\in\mathcal{E}$, $E^{-1}(p)\cap\mathcal{F}_{FGN}$,
$E^{-1}(p)\cap\mathcal{F}_{SGE}$ are compact, convex subsets of $\mathcal{F}$.

###### Proof.

Note first that since $\mathcal{F}$ is defined by weak linear inequalities,
$\mathcal{F}$ is closed and convex. Since $|f_{i}(S)|\leq 1$ for every
$f\in\mathcal{F}$, $i\in[n]$, and $S\subseteq[n]$, $\mathcal{F}$ is bounded,
and it follows that $\mathcal{F}$ is compact. Since $\mathcal{F}_{FGN}$ and
$\mathcal{F}_{SGE}$ are defined by weak linear inequalities and
$\mathcal{F}_{SGE}\subseteq\mathcal{F}_{FGN}\subseteq\mathcal{F}$, they are
also bounded, so they are also compact and convex.

Now, recall from equation 1 that $f\in E^{-1}(p)$ if and only if
$c_{i}^{\prime}(p_{i})=\max\\{0,r_{i}(f,p_{-i})\\}$ for all $i$. If
$f\in\mathcal{F}_{FGN}$, then $r_{i}(f,p_{-i})\geq 0$, so $f\in E^{-1}(p)$ if
and only if $c_{i}^{\prime}(p_{i})=r_{i}(f,p_{-i})$ for all $i$. Since this is
a system of equations that is linear in $f$, it follows that
$E(p)\cap\mathcal{F}_{FGN}$ and $E(p)\cap\mathcal{F}_{SGE}$ are closed and
convex, and the result follows.

∎

This property is useful in that it allows us to obtain contracts that still
have the same equilibrium while also having some additional properties.

The following result will be the key to proving the optimality of SGE
contracts. For $p\in[0,1)^{n}$, define

$\displaystyle z(p)=\sum_{i}{p_{i}\cdot
c_{i}^{\prime}(p_{i})}+\prod_{i}(1-p_{i}).$

If $p\in\mathcal{E}$, then $z(p)\leq 1$, and if $p\in E(f)$ for some
$f\in\mathcal{F}_{SGE}$, then $z(p)=1$.

###### Proof.

Observe that for any FGN contract $f$ and profile $p$,

$\displaystyle\mathbb{E}\left[\sum_{i\in
S}{f_{i}(S)}\right]=\sum_{i}{\mathbb{P}[i\in
S]\cdot\mathbb{E}[f_{i}(S)\,|\,i\in S]}=\sum_{i}{p_{i}\cdot r_{i}(f,p_{-i})}.$

Hence, if $p\in E(f)$, then by equation 1,

$\displaystyle\mathbb{E}\left[\sum_{i\in
S}{f_{i}(S)}\right]=\sum_{i}{p_{i}\cdot
c_{i}^{\prime}(p_{i})}=z(p)-\mathbb{P}[S=\emptyset].$

so

$\displaystyle z(p)=\mathbb{E}\left[\sum_{i\in
S}{f_{i}(S)}\right]+\mathbb{P}[S=\emptyset].$

Moreover,

$\displaystyle\mathbb{E}\left[\sum_{i\in
S}{f_{i}(S)}\right]=\mathbb{P}[S\neq\emptyset]\cdot\mathbb{E}\left[\sum_{i\in
S}{f_{i}(S)}\,|\,S\neq\emptyset\right]\leq\mathbb{P}[S\neq\emptyset],$

with equality if and only if $f$ is SGE. Hence, for $p\in\mathcal{E}$,

$\displaystyle z(p)\leq\mathbb{P}[S\neq\emptyset]+\mathbb{P}[S=\emptyset]=1,$

and if $p$ is an equilibrium for some SGE contract, then $z(p)=1$.

∎

###  4.1 Characterization of optimal contracts

In this section, we discuss the key ideas to prove Theorem 3, which can be
reformulated equivalently as $p\in\mathcal{P}$ if and only if
$E^{-1}(p)\subseteq\mathcal{F}_{SGE}$. We first show that if $p\in E(f)$ is
Pareto optimal, then the contract $f$ must be SGE. If $p\in\mathcal{P}$ and
$p\in E(f)$, then $f\in\mathcal{F}_{SGE}$.

###### Proof.

Suppose $p\in\mathcal{P}$. Let

$\displaystyle K_{p}:=\\{S\subseteq[n]\,:\,\sum_{i\in S}{f_{i}(S)}<1\text{ for
some }f\in E^{-1}(p)\cap\mathcal{F}_{FGN}\\},$

and let

$\displaystyle\kappa_{p}:=\\{i\in[n]\,:\,\\{i\\}\in K_{p}\\}.$

We now show that $K_{p}=\\{\emptyset\\}$.

  1. 1.

Step 1: Suppose $S\in K_{p}$. For any $T\subset S$, $T\in K_{p}$.

Let $f\in E^{-1}(p)\cap\mathcal{F}_{FGN}$ be such that $\sum_{i\in
S}{f_{i}(S)}<1$. If $\sum_{i\in T}{f_{i}(T)}<1$, we are done. Otherwise, pick
an agent $i\in T$ such that $f_{i}(T)>0$ and consider a contract $g$ which
differs from $f$ only in its award for agent $i$ at $S$ and $T$. In
particular, let $g$ be such that $g_{i}(S)=f_{i}(S)+\epsilon$ and
$g_{i}(T)=f_{i}(T)-\delta$ where $\epsilon,\delta>0$ are chosen so that $p\in
E(g)$. Note that we can do this because we know from Lemma 4 that for all
$i\in[n]$, $0<p_{i}<1$ and therefore, ${\Pr}^{[n]_{-i}}_{p_{-i}}(S)>0$ for all
$i\in[n]$ and all $S\subset[n]_{-i}$. It follows then that $g\in
E^{-1}(p)\cap\mathcal{F}_{FGN}$ and $\sum_{i\in T}{g_{i}(T)}<1$. Thus, $T\in
K_{p}$.

  2. 2.

Step 2: Suppose $S,T\in K_{p}$. Then, $S\cup T\in K_{p}$.

Let $f,g\in E^{-1}(p)\cap\mathcal{F}_{FGN}$ be such that $\sum_{i\in
S}{f_{i}(S)}<1$ and $\sum_{i\in T}{g_{i}(T)}<1$. Consider the contract
$h=\frac{1}{2}f+\frac{1}{2}g$. From Lemma 4, $h\in
E^{-1}(p)\cap\mathcal{F}_{FGN}$ and also $\sum_{i\in S}{h_{i}(S)}<1$ and
$\sum_{i\in T}{h_{i}(T)}<1$. Now, if $\sum_{i\in S\cup T}{h_{i}(S\cup T)}<1$,
we are done. Otherwise, pick any agent $i\in S\cup T$ (WLOG, let $i\in S$)
such that $h_{i}(S\cup T)>0$ and consider a contract $h^{\prime}$ which
differs from $h$ only in its award for agent $i$ at $S\cup T$ and $S$. In
particular, let $h^{\prime}$ be such that $h^{\prime}_{i}(S\cup T)=h_{i}(S\cup
T)-\epsilon$ and $h^{\prime}_{i}(S)=h_{i}(S)+\delta$ where $\epsilon,\delta>0$
are chosen so that $p\in E(h^{\prime})$. Again, we can do this because we know
that for all $i\in[n]$, $0<p_{i}<1$. It follows then that $h^{\prime}\in
E^{-1}(p)\cap\mathcal{F}_{FGN}$ and $\sum_{i\in S\cup T}{h^{\prime}_{i}(S\cup
T)}<1$. Thus, $S\cup T\in K_{p}$.

Note that it follows from Steps 1 and 2 that $K_{p}=2^{\kappa_{p}}$.

  3. 3.

Step 3: Suppose $f\in E^{-1}(p)\cap\mathcal{F}_{FGN}$. Then, for all
$S\subset[n]$ such that $\kappa_{p}^{C}\cap S\neq\phi$, $f_{i}(S)=0$ for all
$i\in\kappa_{p}$.

Suppose towards a contradiction that there is an $S\subset[n]$ such that
$\kappa_{p}^{C}\cap S\neq\phi$ and $f_{i}(S)>0$ for some $i\in\kappa_{p}$. Let
$g\in E^{-1}(p)\cap\mathcal{F}_{FGN}$ be such that $g_{i}(\\{i\\})<1$.
Consider the contract $h=\frac{1}{2}f+\frac{1}{2}g$. Then $h\in
E^{-1}(p)\cap\mathcal{F}_{FGN}$ and also $h_{i}(S)>0$ and $h_{i}(\\{i\\})<1$.
Now, consider a contract $h^{\prime}$ which differs from $h$ only in its award
for agent $i$ at $S$ and $\\{i\\}$. In particular, let $h^{\prime}$ be such
that $h^{\prime}_{i}(\\{i\\})=h_{i}(\\{i\\})+\epsilon$ and
$h^{\prime}_{i}(S)=h_{i}(S)-\delta$ where $\epsilon,\delta>0$ are chosen so
that $p\in E(h^{\prime})$. We can do this because for all $i\in[n]$,
$0<p_{i}<1$. It follows then that $h^{\prime}\in
E^{-1}(p)\cap\mathcal{F}_{FGN}$ and $\sum_{i\in S}{h^{\prime}_{i}(S)}<1$. But
this means that $S\subset\kappa_{p}$ which is a contradiction.

  4. 4.

Step 4: Suppose $\kappa_{p}\neq\phi$. Then there is a $p^{\prime}$ that Pareto
dominates $p$.

For all $S\in K_{p}$, let $f^{S}\in E^{-1}(p)\cap\mathcal{F}_{FGN}$ be such
that $\sum_{i\in S}{f^{S}_{i}(S)}<1$. Consider the contract $g=\sum_{S\in
K_{p}}\frac{1}{|K_{p}|}f^{S}$. Then $g\in E^{-1}(p)\cap\mathcal{F}_{FGN}$ and
also $\sum_{i\in S}{g_{i}(S)}<1$ for all $S\in K_{p}$. Now, we can construct a
contract $h\in E^{-1}(p)\cap\mathcal{F}_{FGN}$ such that

$h_{i}(S)=\begin{cases}g_{i}(S),&\text{ if }S\in K_{p}\\\
h_{i}(S\setminus\kappa_{p}),&\text{ if }S\notin K_{p}\end{cases}$

by averaging over the outcomes of agents in $\kappa_{p}$ under $g$.

Observe that if we manipulate $h$ at any $S\subset\kappa_{p}$, it won’t change
the best responses for agents $i\notin\kappa_{p}$. We will now show that we
can manipulate the awards for $S\subset\kappa_{p}$ so that under the new
contract $h^{\prime}$, $p^{\prime}\in E(h^{\prime})$ where
$p^{\prime}_{i}>p_{i}$ for $i\in\kappa_{p}$ and $p^{\prime}_{i}=p_{i}$ for
$i\notin\kappa_{p}$. Towards this goal, let $A=\kappa_{p}$ and let
$p^{\prime}=(p_{i}+\epsilon)_{i\in A}$. For each $i\in A$, let
$t_{i}(\epsilon)$ solve

$c_{i}^{\prime}(p^{\prime}_{i})=t_{i}(\epsilon)\sum_{S\subset
A_{-i}}(h_{i}(S\cup\\{i\\})){\Pr}^{A_{-i}}_{p^{\prime}_{-i}}(S)$

Observe that as $\epsilon\to 0$, $t_{i}(\epsilon)\to 1$ for all $i\in A$.
Since $\sum_{i\in S}{h_{i}(S)}<1$ for all $S\subset A$ and $t_{i}(\epsilon)$
is continuous in $\epsilon$, we can find $\epsilon>0$ small enough so that the
contract $h^{\prime}_{i}(S)=h_{i}(S)*t_{i}(\epsilon)$ for all $S\subset A$ and
$i\in S$ is a feasible contract. By the definition of $t_{i}$, $p^{\prime}$
with $p_{i}^{\prime}=p_{i}+\epsilon$ for $i\in\kappa_{p}$ and
$p_{i}^{\prime}=p_{i}$ for $i\notin\kappa_{p}$ will be an equilibrium under
$h^{\prime}$. Thus, we have that $p$ is not Pareto optimal.

It follows then that $K_{p}=\\{\emptyset\\}$. By definition of $K_{p}$, this
means that for any $f\in E^{-1}(p)$, either $f\notin\mathcal{F}_{FGN}$ or
$f\in\mathcal{F}_{SGE}$. Now suppose there exists an $f$ such that
$f\notin\mathcal{F}_{FGN}$ and $p\in E(f)$. From Lemma 4, we can find
$g\in\mathcal{F}_{FGN}$ such that $p\in E(g)$. Moreover, we know from the
construction of $g$ in the argument of Lemma 4 that
$g\notin\mathcal{F}_{SGE}$. Thus, we have that
$g\in\mathcal{F}_{FGN},g\notin\mathcal{F}_{SGE},$ and $p\in E(g)$. But this
means that $K_{p}\neq\emptyset$ which is a contradiction. Therefore, it must
be that for any $f\in E^{-1}(p)$, $f\in\mathcal{F}_{SGE}$.

∎

One might suspect that when a contract $f$ has some slack at some
$S\subset[n]$, the principal can simply increase the reward of some agent
$i\in S$ and that this new contract $g$ will lead to a Pareto dominating
equilibrium $p^{\prime}$. It turns out this is not necessarily the case
because even though the marginal benefit for agent $i$ is higher under $g$
than $f$, and so the best response of agent $i$ will also be higher, this
increase in agent $i$’s response might diminish some other agent $j$’s
marginal benefit leading agent $j$ to reduce its $p_{j}$. Thus, because of
these equilibrium effects, such a transformation of a non SGE contract may not
necessarily lead to Pareto improvements.

However, if a contract $f$ is such that the budget is not being exhausted
under any outcome $S$, then we can actually scale the contract simultaneously
for all agents (which may involve increasing or decreasing an agent’s share)
and at all $S\subset[n]$ so as to obtain a Pareto superior equilibrium. Now to
prove Lemma 4.1, we basically show that if $p\in E(f)$,
$f\in\mathcal{F}_{FGN}$ and $f\notin\mathcal{F}_{SGE}$, then we can use the
previous lemmas, and in particular Lemma 4 about the convexity of
$E^{-1}(p)\cap\mathcal{F}_{FGN}$, to construct a contract $g\in
E^{-1}(p)\cap\mathcal{F}_{FGN}$ which has the property that the budget is not
exhausted under any outcome $S$. Going into more detail, for any
$p\in\mathcal{P}$, we define the set

$\displaystyle K_{p}:=\\{S\subseteq[n]\,:\,\sum_{i\in S}{f_{i}(S)}<1\text{ for
some }f\in E^{-1}(p)\cap\mathcal{F}_{FGN}\\},$

and show that if $K_{p}\neq\\{\phi\\}$, we can find a $p^{\prime}$ that Pareto
dominates $p$. First, we show that $K_{p}$ is closed under taking subsets. The
argument is that if $S\in K_{p}$ and $T\subset S$, we can pick an agent $i\in
T$ and decrease its reward under $T$ while increasing its reward in $S$ so
that $p$ is still an equilibrium. Then, we get that $T\in K_{p}$. By a similar
argument, we show that $K_{p}$ is also closed under unions and thus,
$K_{p}=2^{\kappa_{p}}$ where $\kappa_{p}\subset[n]$. Next, we show that for
any $f\in E^{-1}(p)\cap\mathcal{F}_{FGN}$, agents in $\kappa_{p}^{C}$ must
have priority over those in $\kappa_{p}$ in that if any agent in
$\kappa_{p}^{C}$ succeeds, agents in $\kappa_{p}$ get no reward. Using this,
we construct a contract $h\in E^{-1}(p)\cap\mathcal{F}_{FGN}$ such that
$\sum_{i\in S}h_{i}(S)<1$ for any $S\subset\kappa_{p}$ and the reward for
agent $i\notin\kappa_{p}$ do not depend on the success or failure of agents in
$\kappa_{p}$. We then show that we can manipulate the awards for
$S\subset\kappa_{p}$ to get a new contract $h^{\prime}$ such that
$p^{\prime}\in E(h^{\prime})$ where $p_{i}^{\prime}=p_{i}+\epsilon$ for
$i\in\kappa_{p}$ and $\epsilon>0$ while $p_{i}^{\prime}=p_{i}$ for
$i\notin\kappa_{p}$. Thus, it must be that $\kappa_{p}=\phi$ which complete
the proof of this part.

Observe that we get the following as an immediate consequence of Lemmas 4 and
4.1.

######  Corollary 3.

If $p\in\mathcal{P}$, then

$z(p)=\sum_{i}{p_{i}\cdot c_{i}^{\prime}(p_{i})}+\prod_{i}(1-p_{i})=1.$

Corollary 3 provides a simple equation in terms of the model parameters (cost
functions) whose solutions contain the Pareto frontier $\mathcal{P}$. So in
principle, the principal can potentially try to optimize its objective $V(p)$
over the set of solutions to the equation $z(p)=1$, and then check if there is
a contract $f\in\mathcal{F}_{SGE}$ that implements this optimal solution.

The second direction of the characterization says that if $f$ is an SGE
contract and $p\in E(f)$, then there is no $p^{\prime}\in E$ which dominates
$p$.

If $f\in\mathcal{F}_{SGE}$ and $p\in E(f)$, then $p\in\mathcal{P}$.

###### Proof.

Suppose $f\in\mathcal{F}_{SGE}$, $p\in E(f)$, but $p$ is not Pareto optimal.
Then, there must exist a Pareto optimal $q\in\mathcal{P}$ that Pareto
dominates $p$. Observe that since $p\in E(f)$ and $f\in\mathcal{F}_{SGE}$, we
have from Lemma 4 that $z(p)=1$. Also, since $q\in\mathcal{P}$, we have from
Corollary 3 that $z(q)=1$. Now, consider the following:

$\displaystyle\dfrac{\partial z}{\partial x_{i}}\Bigr{|}_{x\geq p}$
$\displaystyle=x_{i}c_{i}^{\prime\prime}(x_{i})+c_{i}^{\prime}(x_{i})-\prod_{j\neq
i}(1-x_{j})$ $\displaystyle>c_{i}^{\prime}(x_{i})-\prod_{j\neq i}(1-x_{j})$
$\displaystyle(\text{because }c_{i}\text{ is convex})$ $\displaystyle\geq
c_{i}^{\prime}(p_{i})-\prod_{j\neq i}(1-x_{j})$ $\displaystyle(\text{because
}c_{i}\text{ is convex})$ $\displaystyle\geq
c_{i}^{\prime}(p_{i})-\prod_{j\neq i}(1-p_{j})$ $\displaystyle(\text{because
}x_{j}\geq p_{j})$ $\displaystyle\geq 0$ $\displaystyle(\text{because }p\in
E(f))$

Note that the last inequality holds because we know from the first order
condition in equation 1 that $c_{i}^{\prime}(p_{i})=r_{i}(f,p_{-i})$ and
$r_{i}(f,p_{-i})\geq\prod_{j\neq i}(1-p_{j})$ since $f\in\mathcal{F}_{SGE}$.

Now, since $q$ Pareto dominates $p$, $q\geq p$ and it follows from above that
$z(q)>z(p)$. But this is a contradiction since $z(q)=z(p)=1$. It follows then
that $p\in E(f)$ is Pareto optimal. ∎

Together, Lemmas 4.1 and 4.1 give Theorem 3.

###  4.2 Implementing the Pareto frontier

As Theorem 3 shows, Pareto optimal equilibria are exactly the equilibria of
SGE contracts, so it is sufficient for the principal to optimize over SGE
contracts. Given the high dimensionality of the set of SGE contracts, this may
still present the principal with a computationally difficult problem, and the
optimal contract may be difficult to understand and implement. Theorem 3
provides a significant reduction in the complexity of the principal’s
optimization problem, reducing the search space from a
$(2^{n-1}(n-2)+1)$-dimensional space of difficult to interpret contracts to an
$(n-1)$-dimensional space of easily interpretable contracts.

To prove Theorem 3, we first obtain a useful relationship between any PW
contract $f$ and the best responses $b_{i}(f,p_{-i})$ under any Pareto optimal
profile $p\in\mathcal{P}$.

Suppose $p\in\mathcal{P}$ and $f\in\mathcal{F}_{PW}$. Then, for every
$i\in[n]$,

$\sum_{j:i\succcurlyeq
j}p_{j}\left[c_{j}^{\prime}\left(b_{j}\left(f,p_{-j}\right)\right)-c_{j}^{\prime}\left(p_{j}\right)\right]\leq
0.$

And in particular,

$\sum_{i\in[n]}p_{i}\left[c_{i}^{\prime}(b_{i}(f,p_{-i}))-c_{i}^{\prime}(p_{i})\right]=0.$

###### Proof.

We want to show that if $p\in\mathcal{P}$ and $f\in\mathcal{F}_{PW}$, then for
every $i\in[n]$,

$\sum_{j:i\succcurlyeq
j}p_{j}\left[c_{j}^{\prime}\left(b_{j}\left(f,p_{-j}\right)\right)-c_{j}^{\prime}\left(p_{j}\right)\right]\leq
0,$

where $\succcurlyeq$ denotes the priority relation induced by
$f\in\mathcal{F}_{PW}$.

Suppose $p\in\mathcal{P}$, $g\in E^{-1}(p)$, and $f\in\mathcal{F}_{PW}$. We
know from the first-order condition in equation 1 that for all $i\in[n]$,

$c_{i}^{\prime}\left(b_{i}\left(f,p_{-i}\right)\right)=\sum_{S\subset[n]_{-i}}f_{i}(S\cup\\{i\\})\operatorname{Pr}_{p_{-i}}^{[n]_{-i}}(S).$

Multiplying both sides by $p_{i}$ and adding up the equations for agents $j$
such that $i\succcurlyeq j$, we get

$\displaystyle\sum_{j:i\succcurlyeq j}p_{j}c_{j}^{\prime}(b_{j}(f,p_{-j}))$
$\displaystyle=\sum_{j:i\succcurlyeq j}\sum_{S:j\in
S}f_{j}(S)\operatorname{Pr}_{p}^{[n]}(S)$
$\displaystyle=\sum_{S\subseteq\left\\{j:i\succcurlyeq_{f}j\right\\}}\operatorname{Pr}_{p}^{[n]}(S)$
$\displaystyle(\text{because f is PW})$
$\displaystyle\leq\sum_{j:i\succcurlyeq j}\sum_{S:j\in
S}g_{j}(S)\operatorname{Pr}_{p}^{[n]}(S)$ $\displaystyle(\text{because
}g\in\mathcal{F}_{SGE})$ $\displaystyle=\sum_{j:i\succcurlyeq
j}p_{j}c_{j}^{\prime}(p_{j})$ $\displaystyle(\text{because }g\in E^{-1}(p))$

Note that the inequality becomes equality when we are adding up over all
$i\in[n]$ and thus, we get
$\sum_{i\in[n]}p_{i}\left[c_{i}^{\prime}(b_{i}(f,p_{-i}))-c_{i}^{\prime}(p_{i})\right]=0.$
∎

Now we are ready to show that for any Pareto optimal $p$, there exists a PW
contract that implements $p$.

Suppose $p\in\mathcal{P}$. Then, there exists $f\in\mathcal{F}_{PW}$ such that
$p\in E(f)$.

###### Proof.

Suppose $p\in\mathcal{P}$. For any $f\in\mathcal{F}_{PW}$, let

$Z(f):=\max_{i\in[n]}\left(c_{i}^{\prime}(b_{i}(f,p_{-i}))-c_{i}^{\prime}(p_{i})\right)$

and

$\mathcal{C}(f):=\\{i\in[n]\,:\,c_{i}^{\prime}(b_{i}(f,p_{-i}))-c_{i}^{\prime}(p_{i})=Z(f)\\}$

From Lemma 4.2, we know that $Z(f)\geq 0$ for all $f\in\mathcal{F}_{PW}$ and
so

$z=\inf_{f\in\mathcal{F}_{PW}}{Z(f)}\geq 0.$

We will now show that $z=0$.

Suppose towards a contradiction that $z>0$. Let $f\in\mathcal{F}_{PW}$ be such
that

  1. 1.

$Z(f)=z$ and

  2. 2.

for any other $g\in\mathcal{F}_{PW}$ such that $Z(g)=z$,
$\mathcal{C}(g)\not\subset\mathcal{C}(f)$.

Let $(X_{1},\dots,X_{\ell})$ be the ordered partition corresponding to
$\succcurlyeq$ and $\lambda_{1},\dots,\lambda_{n}$ be the weights that define
$f$.

Let $k$ be the maximum index such that $X_{k}\cap\mathcal{C}(f)\neq\emptyset$.

First suppose $k=\ell$. From Lemma 4.2, we know that there must be some $i\in
X_{l}$ such that $c_{i}^{\prime}(b_{i}(f,p_{-i}))-c_{i}^{\prime}(p_{i})<0$.
Now consider another PW contract $g$ which is the same as $f$, except that the
weight for agent $i$ is $\lambda_{i}^{\prime}=\lambda_{i}+\epsilon$. Thus,
when all agents in $[n]\setminus X_{l}$ have failed, agent $i$ gets a slightly
higher share of the reward if it succeeds under $g$ than it did under $f$.
Notice that for $j\notin X_{\ell}$,

$\displaystyle
c_{j}^{\prime}(b_{j}(g,p_{-j}))-c_{j}^{\prime}(p_{j})=c_{j}^{\prime}(b_{j}(f,p_{-j}))-c_{j}^{\prime}(p_{j})$

and for $j\in X_{\ell}\setminus\\{i\\}$,

$\displaystyle
c_{j}^{\prime}(b_{j}(g,p_{-j}))-c_{j}^{\prime}(p_{j})<c_{j}^{\prime}(b_{j}(f,p_{-j}))-c_{j}^{\prime}(p_{j})\leq
z.$

Moreover, for $\varepsilon$ sufficiently small,

$\displaystyle c_{i}^{\prime}(b_{i}(g,p_{-i}))-c_{i}^{\prime}(p_{i})<0$

by continuity. It follows that $Z(g)\leq z$. In particular, we either have
$Z(g)<z$ or $Z(g)=z$ and $\mathcal{C}(g)\subset\mathcal{C}(f)$. In either
case, we have a contradiction.

Thus, it must be that $k<\ell$. Now, consider another PW contract $g$ which
has the partition $(X_{1},\dots,X_{k-1},X_{k}\cup
X_{k+1},X_{k+2},\dots,X_{\ell})$ and weights

$\lambda_{i}^{\prime}=\begin{cases}\lambda_{i}&\text{ if }i\notin X_{k+1}\\\
\varepsilon\lambda_{i}&\text{ if }i\in X_{k+1}\end{cases}.$

Then for $j\notin X_{k}\cup X_{k+1}$,

$\displaystyle
c_{j}^{\prime}(b_{j}(g,p_{-j}))-c_{j}^{\prime}(p_{j})=c_{j}^{\prime}(b_{j}(f,p_{-j}))-c_{j}^{\prime}(p_{j})$

and for $j\in X_{k}$,

$\displaystyle
c_{j}^{\prime}(b_{j}(g,p_{-j}))-c_{j}^{\prime}(p_{j})<c_{j}^{\prime}(b_{j}(f,p_{-j}))-c_{j}^{\prime}(p_{j})\leq
z.$

Finally, for $\varepsilon$ sufficiently small and $j\in X_{k+1}$,

$\displaystyle c_{j}^{\prime}(b_{j}(g,p_{-j}))-c_{j}^{\prime}(p_{j})<z$

by continuity. It follows that $Z(g)\leq z$. In particular, we either have
$Z(g)<z$ or $Z(g)=z$ and $\mathcal{C}(g)\subset\mathcal{C}(f)$. In either
case, we have a contradiction. Thus, we have that
$\inf_{f\in\mathcal{F}_{PW}}{Z(f)}=0$. By compactness of $\mathcal{F}_{PW}$,
there exists an $f\in\mathcal{F}_{PW}$ such that $Z(f)=0$ which means

$\left[\max_{i\in[n]}\left(c_{i}^{\prime}(b_{i}(f,p_{-i}))-c_{i}^{\prime}(p_{i})\right)\right]=0.$

But from Lemma 4.2, we also know that

$\sum_{i\in[n]}p_{i}\left[c_{i}^{\prime}(b_{i}(f,p_{-i}))-c_{i}^{\prime}(p_{i})\right]=0.$

Therefore, it must be that for all $i\in[n]$,

$\left(c_{i}^{\prime}(b_{i}(f,p_{-i}))-c_{i}^{\prime}(p_{i})\right)=0$

which implies $f\in E^{-1}(p)$. Thus, for any Pareto optimal $p$, there is a
PW contract $f$ such that $p\in E(f)$. ∎

To prove Lemma 4.2, we define for any $f\in\mathcal{F}_{PW}$,

$Z(f):=\max_{i\in[n]}\left[c_{i}^{\prime}(b_{i}(f,p_{-i}))-c_{i}^{\prime}(p_{i})\right],$

and show that

$z=\inf_{f\in\mathcal{F}_{PW}}{Z(f)}=0.$

From Lemma 4.2, we already know that $z\geq 0$. To prove $z=0$, we basically
show that if $z>0$ and $f\in\mathcal{F}_{PW}$ attains $z$, then we can find
another contract $g\in\mathcal{F}_{PW}$ so that it attains $z^{\prime}<z$.
Informally, let $z={c_{i}^{\prime}(b_{i}(f,p_{-i}))-c_{i}^{\prime}(p_{i})}>0$,
where $i$ is chosen so that it has the lowest priority among all agents with
this property under $f$. Then all agents $j$ with lower priority than $i$ must
be such that ${c_{j}^{\prime}(b_{j}(f,p_{-j}))-c_{j}^{\prime}(p_{j})}<z$. We
then construct another PW contract $g$ by grouping together agents in priority
group of $i$ and those in the immediately lower priority group by giving a
small weight $\epsilon$ to agents in the lower priority group. Then, the best
response of any agent $j$ in $i$’s priority group to $p_{-j}$ will be smaller
under $g$ than $f$ while for any agents $j$ in the lower priority group, it
will be greater under $g$ than $f$. For $\epsilon>0$ small enough, we will
have $Z(g)<z$.

With $z=0$, we use compactness of $\mathcal{F}_{PW}$ and Lemma 4.2 to get that
there must be an $f\in\mathcal{F}_{PW}$ such that all $i\in[n]$,

$\left(c_{i}^{\prime}(b_{i}(f,p_{-i}))-c_{i}^{\prime}(p_{i})\right)=0$

which implies $f\in E^{-1}(p)$. Thus, for any Pareto optimal $p$, there is a
PW contract $f$ such that $p\in E(f)$. The following lemma establishes the
uniqueness of the PW contract that implements $p$.

Suppose $f\in\mathcal{F}_{PW}$ and $p\in E(f)$. Then for any
$g\in\mathcal{F}_{PW}$ such that $g\neq f$, $p\notin E(g)$.

###### Proof.

Consider the case where $f,g$ are weighted contracts and suppose towards a
contradiction that $p\in E(f)\cap E(g)$. Let $i\in[n]$ denote the agent with
the smallest weight ratio $\frac{\lambda^{g}_{i}}{\lambda_{i}^{f}}$, where
$\lambda^{f},\lambda^{g}$ represent the weights that define the contracts
$f,g\in\mathcal{F}_{W}$. It follows from the definition of weighted contracts
that for any $S\subset[n]$ such that $i\in S$, agent $i$’s reward is weakly
lower under $g$ than $f$. As a result, it must be that
$r_{i}(g,p_{-i})<r_{i}(f,p_{-i})$ and so it can’t be that
$b_{i}(g,p_{-i})=b_{i}(f,p_{-i})$. It follows that two different weighted
contracts cannot have the same equilibrium. The argument extends in a natural
way to PW contracts. ∎

Together, Lemmas 4.2 and 4.2 give Theorem 3. Moreover, it follows from Lemma
4.2 that the class of PW contracts is minimal among classes of contracts that
implement the Pareto frontier.

##  5 Conclusion

We study a contract design problem between a principal and multiple agents. In
a setting where the principal is budget-constrained and does not care about
how much of the budget is exhausted in incentivizing the agents, we show that
the maximal set of effort levels that can be sustained in equilibrium is
characterized by equilibria of contracts in which the entire budget is split
among agents that succeed. Hence, piece-rate and bonus-pool contracts are
never optimal in this setting. We further identify a natural subclass of
priority-based weighted contracts that are sufficient to implement the Pareto
frontier of equilibria that can be induced in equilibrium. The result provides
a significant reduction in dimensionality of the optimal contract design
problem. We illustrate this by applying our results to derive the optimal
contract for a special parametric case with two agents. Our result for this
case suggests that the structure of optimal contract is, to some extent,
robust to the heterogeneity in the agents’ cost functions. While it is
difficult to give a closed form for the optimal contract for a given
objective, the significant reduction in dimensionality and the simple
structure of $PW$ contracts suggests that approximating the optimal contract
for given objective may not be computationally hard. We leave this and related
questions for further work.

## References

  * Babaioff et al. [2012] Babaioff, M., M. Feldman, N. Nisan, and E. Winter (2012): “Combinatorial agency,” _Journal of Economic Theory_ , 147, 999–1034.
  * Baiman and Rajan [1995] Baiman, S. and M. V. Rajan (1995): “The informational advantages of discretionary bonus schemes,” _Accounting Review_ , 557–579.
  * Battaglini [2006] Battaglini, M. (2006): “Joint production in teams,” _Journal of Economic Theory_ , 130, 138–167.
  * Bond and Gomes [2009] Bond, P. and A. Gomes (2009): “Multitask principal–agent problems: Optimal contracts, fragility, and effort misallocation,” _Journal of Economic Theory_ , 144, 175–211.
  * Carroll [2015] Carroll, G. (2015): “Robustness and linear contracts,” _American Economic Review_ , 105, 536–563.
  * Castiglioni et al. [2023] Castiglioni, M., A. Marchesi, and N. Gatti (2023): “Multi-Agent Contract Design: How to Commission Multiple Agents with Individual Outcome,” _arXiv preprint arXiv:2301.13654_.
  * Che and Yoo [2001] Che, Y.-K. and S.-W. Yoo (2001): “Optimal incentives for teams,” _American Economic Review_ , 91, 525–541.
  * Dai and Toikka [2022] Dai, T. and J. Toikka (2022): “Robust incentives for teams,” _Econometrica_ , 90, 1583–1613.
  * Dütting et al. [2022] Dütting, P., T. Ezra, M. Feldman, and T. Kesselheim (2022): “Combinatorial contracts,” in _2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)_ , IEEE, 815–826.
  * Dütting et al. [2023] ——— (2023): “Multi-agent contracts,” in _Proceedings of the 55th Annual ACM Symposium on Theory of Computing_ , 1311–1324.
  * Ezra et al. [2024] Ezra, T., M. Feldman, and M. Schlesinger (2024): “On the (In) approximability of Combinatorial Contracts,” in _15th Innovations in Theoretical Computer Science Conference (ITCS 2024)_ , Schloss-Dagstuhl-Leibniz Zentrum für Informatik.
  * Georgiadis [2022] Georgiadis, G. (2022): “Contracting with moral hazard: A review of theory & empirics,” _Available at SSRN 4196247_.
  * Georgiadis et al. [2022] Georgiadis, G., D. Ravid, and B. Szentes (2022): “Flexible moral hazard problems,” Tech. rep., Working Paper.
  * Green and Stokey [1983] Green, J. R. and N. L. Stokey (1983): “A comparison of tournaments and contracts,” _Journal of Political Economy_ , 91, 349–364.
  * Grossman and Hart [1992] Grossman, S. J. and O. D. Hart (1992): “An analysis of the principal-agent problem,” in _Foundations of Insurance Economics: Readings in Economics and Finance_ , Springer, 302–340.
  * Haggiag et al. [2022] Haggiag, C., S. Oren, and E. Segev (2022): “Picking the Right Winner: Why Tie-Breaking in Crowdsourcing Contests Matters,” in _IJCAI-International Joint Conferences on Artificial Intelligence Organization_ , 307–313.
  * Halac et al. [2017] Halac, M., N. Kartik, and Q. Liu (2017): “Contests for experimentation,” _Journal of Political Economy_ , 125, 1523–1569.
  * Holmström [1979] Holmström, B. (1979): “Moral hazard and observability,” _The Bell journal of economics_ , 74–91.
  * Holmstrom [1982] Holmstrom, B. (1982): “Moral hazard in teams,” _The Bell journal of economics_ , 324–340.
  * Holmström [2017] Holmström, B. (2017): “Pay for performance and beyond,” _American Economic Review_ , 107, 1753–1777.
  * Holmstrom and Milgrom [1991] Holmstrom, B. and P. Milgrom (1991): “Multitask principal–agent analyses: Incentive contracts, asset ownership, and job design,” _The Journal of Law, Economics, and Organization_ , 7, 24–52.
  * Imhof and Kräkel [2014] Imhof, L. and M. Kräkel (2014): “Bonus pools and the informativeness principle,” _European Economic Review_ , 66, 180–191.
  * Innes [1990] Innes, R. D. (1990): “Limited liability and incentive contracting with ex-ante action choices,” _Journal of economic theory_ , 52, 45–67.
  * Itoh [1991] Itoh, H. (1991): “Incentives to help in multi-agent situations,” _Econometrica: Journal of the Econometric Society_ , 611–636.
  * Jewitt et al. [2008] Jewitt, I., O. Kadan, and J. M. Swinkels (2008): “Moral hazard with bounded payments,” _Journal of Economic Theory_ , 143, 59–82.
  * Kambhampati [2024] Kambhampati, A. (2024): “Robust Performance Evaluation of Independent and Identical Agents,” _arXiv preprint arXiv:2401.16542_.
  * Lazear and Rosen [1981] Lazear, E. P. and S. Rosen (1981): “Rank-order tournaments as optimum labor contracts,” _Journal of political Economy_ , 89, 841–864.
  * Malcomson [1986] Malcomson, J. M. (1986): “Rank-order contracts for a principal with many agents,” _The Review of Economic Studies_ , 53, 807–817.
  * Mirrlees [1976] Mirrlees, J. A. (1976): “The optimal structure of incentives and authority within an organization,” _The Bell Journal of Economics_ , 105–131.
  * Mookherjee [1984] Mookherjee, D. (1984): “Optimal incentive schemes with many agents,” _The Review of Economic Studies_ , 51, 433–446.
  * Nalebuff and Stiglitz [1983] Nalebuff, B. J. and J. E. Stiglitz (1983): “Prizes and incentives: towards a general theory of compensation and competition,” _The Bell Journal of Economics_ , 21–43.
  * Prendergast [1999] Prendergast, C. (1999): “The provision of incentives in firms,” _Journal of economic literature_ , 37, 7–63.
  * Rosen [1965] Rosen, J. B. (1965): “Existence and uniqueness of equilibrium points for concave n-person games,” _Econometrica: Journal of the Econometric Society_ , 520–534.
  * Ross [1973] Ross, S. A. (1973): “The economic theory of agency: The principal’s problem,” _The American economic review_ , 63, 134–139.
  * Segal [1999] Segal, I. (1999): “Contracting with externalities,” _The Quarterly Journal of Economics_ , 114, 337–388.
  * Segal [2003] ——— (2003): “Coordination and discrimination in contracting with externalities: Divide and conquer?” _Journal of Economic Theory_ , 113, 147–181.
  * Segev [2020] Segev, E. (2020): “Crowdsourcing contests,” _European Journal of Operational Research_ , 281, 241–255.
  * Siemroth [2021] Siemroth, C. (2021): “Ending wasteful year-end spending: On optimal budget rules in organizations,” _Available at SSRN 3991922_.
  * Winter [2010] Winter, E. (2010): “Transparency and incentives among peers,” _The RAND Journal of Economics_ , 41, 504–523.
  * Zhang [2023] Zhang, P. (2023): “Distributionally Robust Principal-Agent Problems and Optimality of Contract Menus,” _arXiv preprint arXiv:2303.07468_.


# Convergence of spectral truncations for compact metric groups

Yvann Gaudillot–Estrada  and  Walter D. van Suijlekom  Institute for
Mathematics, Astrophysics and Particle Physics, Radboud University Nijmegen,
Heyendaalseweg 135, 6525 AJ Nijmegen, The Netherlands.  yvann.gaudillot-
<EMAIL_ADDRESS><EMAIL_ADDRESS>
(Date: October 23, 2023)

###### Abstract.

We consider Gromov–Hausdorff convergence of state spaces for spectral
truncations of a compact metric group $G$. We work in the context of order-
unit spaces and consider orthogonal projections $P_{\Lambda}$ in $L^{2}(G)$
corresponding to finite subsets of irreducible representations
$\Lambda\subseteq\widehat{G}$. We then prove that the sequence of truncated
state spaces $\\{S(P_{\Lambda}C(G)P_{\Lambda})\\}_{\Lambda}$ Gromov–Hausdorff
converges to the original state space $S(C(G))$, when these are equipped with
a metric associated to a Lip-norm which in turn is induced by the action of
$G$.

##  1\. Introduction

This paper deals with the question of how one can approximate the geometric
structure of a compact metric group $G$ by finite-dimensional, so-called
spectral truncations. We work in the context of quantum metric spaces as
introduced by Rieffel [22] (and further developed in [12, 14, 15]) but employ
the classical notion of Gromov–Hausdorff convergence for compact metric
spaces. The spectral truncations we consider are defined by orthogonal
projections onto finite subsets of irreducible representations that appear in
the Peter–Weyl decomposition of $L^{2}(G)$; they yield so-called order-unit
spaces. The main advantage of the latter notion is that it allows to speak of
state spaces. Moreover, when the order-unit spaces are equipped with a
suitable Lip-norm, there is a metric on these state spaces that metrizes the
weak∗ topology. It is in this context that the question concerning
Gromov–Hausdorff convergence can be addressed, and, in the present paper,
resolved in the case of compact metric groups equipped with a bi-invariant
metric.

This work is closely related to some of our previous work on Gromov–Hausdorff
convergence for spectral truncations of Dirac operators on the circle [25, 9]
and tori [4, 16]. However, here we treat the case of general compact metric
groups equipped with a Lip-norm that is naturally induced by the group action
of $G$ (as in [21, 23]). We leave the more involved spectral truncations
associated to a Laplace or Dirac-type operator on $G$ —and the corresponding
induced Lip-norms— for future research. Also, the main difference with these
previous attempts is that we no longer use specifically the formal adjoint of
$C(G)\mapsto P_{\Lambda}C(G)P_{\Lambda}$ for the reverse map. This freedom
enables us to prove a more general convergence result. In fact, we prove that
the truncated state space $S(P_{\Lambda}C(G)P_{\Lambda})$ Gromov–Hausdorff
converges to the original state space $S(C(G))$, where the index $\Lambda$ is
a finite subset of the set $\widehat{G}$ of irreducible representations of
$G$. The net of truncations is parametrized by the directed set of finite
subsets of $\widehat{G}$.

Our result is also closely related to the recent work [24], which considers
discrete groups with polynomial growth. The author uses quantum
Gromov–Hausdorff distance instead of Gromov–Hausdorff distance as we do here,
but in fact our present results extend mutatis mutandis for the former notion
of convergence as well. We should note however that the two notions of
distance do not coincide in general [10].

Our results mean a great step forward in the study of spectral approximation
of geometric spaces, as initiated in [5, 8]. Subsequent results on the quantum
Gromov–Hausdorff convergence for quantum groups and/or homogeneous spaces are
now of course waiting to be explored. First examples of truncations of a
different kind —so-called Fourier truncations— have been analyzed in [1, 2,
20]. We expect that the well-known (co)representation theory of quantum groups
allows for a straight-forward generalization of our results to the quantum
world.

### Acknowledgements

We thank David Kyed and Malte Leimbach for suggestions and comments on a draft
of this paper.

##  2\. Preliminaries

###  2.1. Order-unit spaces

We start by recalling some basic notions on order-unit spaces, referring to
[3, Chapter II] for more details.

######  Definition 1.

An order-unit space is a real ordered vector space $A$ together with an
archimedean order unit, i.e. an element $e\in A$ that satisfies

  1. (1)

for each $a\in A$ there is an $r\in\mathbb{R}$ such that $a\leq re$;

  2. (2)

if $a\in A$ and if $a\leq re$ for all $r\in\mathbb{R}_{+}$ then $a\leq 0$.

A linear map $\phi:A\to B$ between two order-unit spaces is said to be an
order-unit morphism if it preserves the unit and the order.

Let $A$ be an order-unit space and let $\mathbb{R}$ be equipped with its
natural structure of order-unit space. There exists a unique order-unit
morphism $\mathbb{R}\to A$ and it is injective. We always consider
$\mathbb{R}$ as embedded in $A$ through that morphism. There is also a natural
order-unit norm $\|\cdot\|$ on $A$ defined by:

$\|a\|=\inf\,\\{t>0:-t\leq a\leq t\\},\qquad(\forall a\in A).$

Note that for $\phi:A\to B$ an order-unit morphism, we have:

$\|\phi(a)\|\leq\|a\|,\qquad(\forall a\in A).$

######  Definition 2 (State space).

A state on an order-unit space $A$ is an order-unit morphism
$\sigma:A\to\mathbb{R}$. We denote by $S(A)$ the set of all states on $A$.

The state space is compact for the weak∗ topology by a direct application of
the Banach-Alaoglu Theorem.

###  2.2. Lip-norms and Gromov–Hausdorff convergence of state spaces

To introduce a notion of distance for state spaces of order-unit spaces, we
follow [22, Section 2] and use Lipschitz semi-norms:

######  Definition 3 (Lip-norm).

Let $A$ be an order-unit space. A Lip-norm on $A$ is a seminorm $L$ on $A$
such that

  1. (1)

for $a\in A$ we have $L(a)=0$ iff $a\in\mathbb{R}$;

  2. (2)

the topology on $S(A)$ from the metric defined by

$d_{L}(\sigma,\tau)=\sup\,\\{|\sigma(a)-\tau(a)|:a\in A,L(a)\leq 1\\}$

is the weak∗ topology.

A convenient way to check the second condition is given by [21, Theorem 1.9],
stating that it holds iff

  1. (1)

for $a\in A$ we have $L(a)=0$ iff $a\in\mathbb{R}$;

  2. (2)

$d_{L}$ is bounded;

  3. (3)

the set $\mathcal{B}_{1}:=\\{a\in A:L(a)\leq 1,\|a\|\leq 1\\}$ is totally
bounded in $A$ for $\|\cdot\|$.

Note also that in [6, Proposition 4] it is shown that if $\\{a\in A:L(a)\leq
1\\}/\mathbb{R}$ is bounded, then $d_{L}$ is a metric.

Now, we can define a refinement of the category of order-unit spaces taking
into account this metric aspect:

######  Definition 4.

A quantum metric space is a pair $(A,L)$ with $A$ an order-unit space and $L$
a Lip-norm on $A$.

A morphism $(A,L_{A})\to(B,L_{B})$ between two quantum metric spaces is by
definition an order-unit morphism $\phi:A\to B$ such that:

$\quad L_{B}(\phi(a))\leq L_{A}(a);\qquad(\forall a\in A).$

This terminology is justified by the fact that if $(A,L)$ is a quantum metric
space, then $(S(A),d_{L})$ is a compact metric space (since $d_{L}$ metrizes
the weak∗ topology). As a matter of fact, we may consider $S$ as a functor
from the category of quantum metric spaces, to that of compact metric spaces,
and write accordingly $S(A,L)=(S(A),d_{L})$ as the state space of $(A,L)$.

######  Example 5.

Given a compact metric space $(X,d)$ we may speak about Lipschitz functions as
functions $f:X\to\mathbb{C}$ for which there exists a constant $k>0$ such
that:

$|f(x)-f(y)|\leq k\,d(x,y);\qquad(\forall x,y\in X).$

In that case, the lowest constant $k$ verifying the above property is denoted
by $L(f)$.

The algebra $\mathcal{A}$ of all Lipschitz functions on $X$ is a unital sub-
space of $C(X)$ (continuous real-valued functions on $X$) and hence inherits a
structure order-unit space. The semi-norm $L$ is actually a Lip-norm on
$\mathcal{A}$, so that $(\mathcal{A},L)$ is a quantum metric space. In this
case $S(\mathcal{A},L)=(\mathcal{M}(X),d)$, the space of Borel probability
measures on $X$ equipped with the Kantorovich–Rubinstein metric (cf. [18,
19]).

We end this preliminary section with the following general result on the
Gromov–Hausdorff convergence of state spaces [22] (cf. [25, Theorem 5]):

######  Theorem 6.

Let $(A,L_{A})$ and $(B,L_{B})$ be two quantum metric spaces. Assume that we
are given two morphisms of quantum metric spaces
$\phi_{AB}:(B,L_{B})\to(A,L_{A})$ and $\phi_{BA}:(A,L_{A})\to(B,L_{B})$. Let
$\epsilon$ be the lowest constant such that for all $a\in A$ and $b\in B$:

$\displaystyle\|\phi_{AB}\circ\phi_{BA}(a)-a\|$
$\displaystyle\leq\,\epsilon\,L_{A}(a)$
$\displaystyle\|\phi_{BA}\circ\phi_{AB}(b)-b\|$
$\displaystyle\leq\epsilon\,L_{B}(b).$

Then we have the following upper bound for the Gromov–Hausdorff distance
between $S(A,L_{A})$ and $S(B,L_{B})$:

$d_{GH}(\,S(A,L_{A}),S(B,L_{B})\,)\leq\epsilon.$

In [25] such a pair of maps $(\phi_{AB},\phi_{BA})$ was called a
$C^{1}$-approximate order isomorphism.

######  Remark 7.

This result actually extends to yield convergence in the quantum
Gromov–Hausdorff distance as well, as already exploited in [24]. We stress
that the quantum Gromov–Hausdorff distance and the Gromov–Hausdorff in general
may not agree, as witnessed by the interesting paper [10].

##  3\. Truncations of a compact metric group

We first recall the notion of metric group:

######  Definition 8.

A metric $d$ on a group $G$ is said to be bi-invariant if:

$d(gx,gy)=d(x,y)=d(xg,yg);\qquad(\forall g,x,y\in G).$

A metric group is a pair $(G,d)$ with $G$ a group and $d$ a bi-invariant
distance on $G$.

A metric group is in particular a metric space and a topological group. Let us
assume in the following that $(G,d)$ is a compact metric group. Then there
exists a unique Haar measure on $G$. The Hilbert space of $L^{2}$ functions
with respect to this measure will be denoted simply by $L^{2}(G)$. The left
(resp. right) regular action of $G$ on $L^{2}(G)$ is denoted by $U$ (resp.
$V$), i.e. for all $\psi\in L^{2}(G)$ and $g,x\in G$ we set

$\displaystyle(U_{g}\psi)(x)=\psi(g^{-1}x),\qquad(V_{g}\psi)(x)=\psi(xg).$

Recall that the Peter–Weyl Theorem (cf. [13, Theorem 1.12]) gives a
decomposition of $L^{2}(G)$ into irreducible unitary representations of $G$
with respect to these left and right actions:

(1) $L^{2}(G)=\widehat{\bigoplus}_{\nu\in\widehat{G}}E_{\nu}\otimes
E_{\nu}^{*},$

where $\widehat{G}$ is the set of equivalent classes of irreducible unitary
representations of $G$. The equality in (1) is intended to stress that in the
following we will in fact identify the left- and right-hand side.

We again write $\mathcal{A}$ for the algebra of real-valued Lipschitz
functions on $(G,d)$. An element $f$ of $\mathcal{A}$ acts as a bounded self-
adjoint operator on $L^{2}(G)$ acting by pointwise multiplication. In other
words, $\mathcal{A}$ can also be considered as a unital sub-space of the
order-unit space $\mathcal{B}(L^{2}(G))_{sa}$ of all bounded self-adjoint
operators on $L^{2}(G)$. Of course, the order-unit structures on $\mathcal{A}$
induced by the inclusion in $C(G)$ and $\mathcal{B}(L^{2}(G))_{sa}$ are the
same.

For all $g\in G$ we define:

$\begin{array}[]{cccccll}\lambda_{g}&:&\mathcal{B}(L^{2}(G))_{sa}&\longrightarrow&\mathcal{B}(L^{2}(G))_{sa}\\\
&&T&\longmapsto&U_{g}TU_{g}^{*}\end{array}$

and

$\begin{array}[]{cccccll}\rho_{g}&:&\mathcal{B}(L^{2}(G))_{sa}&\longrightarrow&\mathcal{B}(L^{2}(G))_{sa}\\\
&&T&\longmapsto&V_{g}TV_{g}^{*}.\end{array}$

The maps $\lambda$ and $\rho$ define two actions of $G$ on
$\mathcal{B}(L^{2}(G))_{sa}$ by order-unit automorphisms. Furthermore, they
preserve $\mathcal{A}$; indeed, they induce the maps given by left/right
translation of $G$ on itself, i.e.

(2) $\lambda_{g}(f)(x)=f(g^{-1}x),\qquad\rho_{g}(f)(x)=f(xg);\qquad(x,g\in
G,f\in\mathcal{A}).$

For $T\in\mathcal{B}(L^{2}(G))_{sa}$ we may now define three quantities (that
may be infinite):

$\displaystyle\|T\|_{\lambda}=\sup_{x\neq
y}\,\left\\{\frac{\|\lambda_{x}(T)-\lambda_{y}(T)\|}{d(x,y)}\right\\}$
$\displaystyle\|T\|_{\rho}=\sup_{x\neq
y}\,\left\\{\frac{\|\rho_{x}(T)-\rho_{y}(T)\|}{d(x,y)}\right\\}$
$\displaystyle\|T\|_{\lambda,\rho}=\max\,(\,\|T\|_{\lambda},\|T\|_{\rho}).$

Combining these definitions with Equation (2) we conclude that the Lip-norm
$L$ on $\mathcal{A}$ can also be expressed as :

(3) $L(f)=\|f\|_{\lambda}=\|f\|_{\rho};\qquad(\forall f\in\mathcal{A}).$

###  3.1. Spectral truncations of compact metric groups

Let us now define the main object of interest to us: the spectral truncations
of the metric space $(G,d)$. We would like to start by stressing that we
consider truncations induced by projections onto sets of irreducible
repesentations of $G$, rather than spectral projections of some Dirac
operator, as in previous works [4, 7, 25, 9, 16] (however see Remark 10
below).

More precisely, let $\mathcal{F}$ be the directed set of all finite subsets of
$\widehat{G}$. For any $\Lambda\in\mathcal{F}$ we may consider the irreducible
representations $\nu$ in $\Lambda$ that appear in $L^{2}(G)$. In view of
Equation (1) we thus consider the Hilbert subspaces

$L^{2}(G)_{\Lambda}:=\bigoplus_{\nu\in\Lambda}E_{\nu}\otimes
E_{\nu}^{*}\subseteq L^{2}(G).$

The orthogonal projections on $L^{2}(G)$ with image $L^{2}(G)_{\Lambda}$ are
denoted by $P_{\Lambda}$. Clearly, the algebra $\mathcal{A}$ of Lipschitz
functions on $G$ does not restrict to act on $L^{2}(G)_{\Lambda}$; instead, we
should compress $\mathcal{A}$ by $P_{\Lambda}$ to act on the Hilbert subspace
$L^{2}(G)_{\Lambda}$. More generally, we define an order-unit morphism
$\tau_{\Lambda}:\mathcal{B}(L^{2}(G))_{sa}\to\mathcal{B}(L^{2}(G)_{\Lambda})_{sa}$
by

$\tau_{\Lambda}(T)=P_{\Lambda}TP_{\Lambda},\qquad(\forall
T\in\mathcal{B}(L^{2}(G))_{sa}).$

Here, we identify $\mathcal{B}(L^{2}(G)_{\Lambda})$ with the space of bounded
self-adjoint operators on $L^{2}(G)$ commuting with $P_{\Lambda}$. Since
$P_{\Lambda}$ commutes with $U_{g}$ and $V_{g}$ for all $g\in G$, the order-
unit morphism $\tau_{\Lambda}$ commutes with the actions $\lambda$ and $\rho$.
We denote by $\mathcal{A}_{\Lambda}=P_{\Lambda}\mathcal{A}P_{\Lambda}$ the
image of $\mathcal{A}$ by $\tau_{\Lambda}$. Then both
$\mathcal{B}(L^{2}(G))_{sa}$ and $\mathcal{A}_{\Lambda}$ are preserved by
$\lambda$ and $\rho$.

######  Proposition 9.

Let $L_{\Lambda}$ be the restriction of $\|\cdot\|_{\lambda,\rho}$ to
$\mathcal{A}_{\Lambda}$. Then $L_{\Lambda}$ is a Lip-norm on
$\mathcal{A}_{\Lambda}$ and
$\tau_{\Lambda}:(\mathcal{A},L)\to(\mathcal{A}_{\Lambda},L_{\Lambda})$ is a
morphism of quantum metric spaces.

###### Proof.

Since $\mathcal{A}_{\Lambda}$ is finite dimensional total boundedness of the
Lip-ball $\mathcal{B}_{1}$ in $\mathcal{A}_{\Lambda}$ is automatic. It remains
to prove that $L_{\Lambda}(T)=0$ implies $T\in\mathbb{C}$ for all
$T\in\mathcal{A}_{\Lambda}$ (the other implication being obvious). By
definition of $L_{\Lambda}$ in terms of $\|\cdot\|_{\lambda,\rho}$ we have
$L_{\Lambda}(T)=0$ iff $\lambda_{x}(T)=T$ for all $x\in G$. Upon writing
$T=\tau_{\Lambda}(f)$ we then have

$T=\int\lambda_{x}(T)\,d\mu(x)=\tau_{\Lambda}\left(\int\lambda_{x}(f)\,d\mu(x)\right)$

The $C(G)$-valued integral $\int\lambda_{x}(f)\,d\mu(x)$ is actually a
constant function on $G$ (because of the invariance property of the Haar
measure $\mu$) so that $T\in\mathbb{R}$.

The fact that
$\tau_{\Lambda}:(\mathcal{A},L)\to(\mathcal{A}_{\Lambda},L_{\Lambda})$ is a
morphism of quantum metric spaces is straightforward from Equation (3). ∎

######  Remark 10.

As mentioned in the introduction, the spectral truncations that we consider in
the present paper are not always associated to the spectrum of some Laplace or
Dirac-type operator on $G$, in contrast to some of our previous works [25, 16]
(see also [4, 9]). Supposing that $G$ is a compact Lie group (so that Laplace
or Dirac-type operators exist) we would expect these to yield a restriction to
a subset $\mathcal{F}^{\prime}$ of $\mathcal{F}$ corresponding to the
eigenspaces of the pertinent operator. The main challenge is then to realize
the above Lip-norms $L_{\Lambda}$ as the norm of the commutator
$\|[D_{\Lambda},\cdot]\|$ with the truncated Dirac operator $D_{\Lambda}$, as
in [7]. Nevertheless, the Lip-norm we exploit here is regular in the sense of
[17, 20], i.e. it is finite on the linear span of the coordinate elements of
all finite-dimensional representations.

##  4\. Gromov–Hausdorff convergence of state spaces

We now establish that the net of compact metric spaces
$\left(S(\mathcal{A}_{\Lambda},L_{\Lambda})\right)_{\Lambda\in\mathcal{F}}$
converges to $S(\mathcal{A},L)$ in Gromov–Hausdorff sense. Our strategy
consists in constructing morphisms
$\upsilon_{\Lambda}:(\mathcal{A}_{\Lambda},L_{\Lambda})\to(\mathcal{A},L)$ and
then apply Theorem 6 to the maps $\upsilon_{\Lambda}$ and $\tau_{\Lambda}$.

######  Remark 11.

Note that for any $\Lambda\in\mathcal{F}$ the order-unit morphism
$\tau_{\Lambda}:\mathcal{A}\to\mathcal{A}_{\Lambda}$ is surjective. As a
consequence, the induced map at the level of state spaces,

$\begin{array}[]{cccccll}\tau_{\Lambda}^{*}&:&S(\mathcal{A}_{\Lambda})&\longrightarrow&S(\mathcal{A})\\\
&&\sigma&\longmapsto&\sigma\circ\tau_{\Lambda},\end{array}$

is injective. Since $\mathcal{A}$ is a dense unital sub-space of $C(G)$, the
state space $S(\mathcal{A})$ coincides with $S(C(G))$, which which can be
identified with the set of Borel probability measures on $G$ .

######  Definition 12.

Let $\Lambda\in\mathcal{F}$. A Borel probability measure $\mu$ on $G$
(considered as an element of $S(\mathcal{A})$ ) is said to be liftable (or
that it can be lifted) to a state on $\mathcal{A}_{\Lambda}$ if
$\mu\in\tau_{\Lambda}^{*}\,S(\mathcal{A}_{\Lambda})$. In this case the unique
antecedent of $\mu$ by $\tau_{\Lambda}^{*}$ will be denoted by
$\mu_{\Lambda}$; it thus satisfies $\mu_{\Lambda}\circ\tau_{\Lambda}=\mu$.

######  Remark 13.

If $\mu$ is a Borel probability measure that is liftable to a state on
$\mathcal{A}_{\Lambda_{0}}$ then for all $\Lambda\in\mathcal{F}$ containing
$\Lambda_{0}$, $\mu$ can also be lifted to a state on $\mathcal{A}_{\Lambda}$
and we have:

$\mu_{\Lambda}=\mu_{\Lambda_{0}}\circ(\tau_{\Lambda_{0}|\mathcal{A}_{\Lambda}}),$

with $\tau_{\Lambda_{0}|\mathcal{A}_{\Lambda}}$ the restriction of
$\tau_{\Lambda}$ to an order-unit morphism
$\mathcal{A}_{\Lambda}\to\mathcal{A}_{\Lambda_{0}}$.

######  Proposition 14.

Let $\Lambda\in\mathcal{F}$ and $\mu$ a Borel probability measure on $G$ which
is liftable to a state on $\mathcal{A}_{\Lambda}$. Let
$\upsilon_{\Lambda}^{\mu}:\mathcal{A}_{\Lambda}\to\mathcal{A}$ be the order-
unit morphism defined by:

$\upsilon_{\Lambda}^{\mu}(T)(g)=\mu_{\Lambda}(\rho_{g}(T)),\qquad(\forall
T\in\mathcal{A}_{\Lambda},\forall g\in G)$

Then
$\upsilon_{\Lambda}^{\mu}:(\mathcal{A}_{\Lambda},L_{\Lambda})\to(\mathcal{A},L)$
is a morphism of quantum metric spaces.

Moreover, we have

$d_{GH}(S(\mathcal{A}_{\Lambda},L_{\Lambda}),S(\mathcal{A},L))\leq\int_{G}d(e,x)d\mu(x).$

###### Proof.

The fact that $\upsilon_{\Lambda}^{\mu}$ is an order-unit morphism is
straightforward. For continuity with respect to the Lip-norm we compute

$\displaystyle L(\upsilon_{\Lambda}^{\mu}(T))$ $\displaystyle=\sup_{x\neq
y}\frac{\left|\upsilon^{\mu}_{\Lambda}(T)(x)-\upsilon^{\mu}_{\Lambda}(T)(y)\right|}{d(x,y)}$
$\displaystyle=\sup_{x\neq
y}\frac{\left|\mu_{\Lambda}(\rho_{x}(T)-\rho_{y}(T))\right|}{d(x,y)}\leq\|T\|_{\rho}.$

This shows that $\upsilon_{\Lambda}^{\mu}$ is a morphism of quantum metric
spaces.

We establish the second claim by showing that for the pair
$(\tau_{\Lambda},\upsilon_{\Lambda}^{\mu})$ the constant $\epsilon$ in Theorem
6 has the following upper bound:

$\epsilon\,\leq\int_{G}d(e,x)d\mu(x).$

We first consider the approximation property of the map
$\upsilon_{\Lambda}^{\mu}\circ\tau_{\Lambda}$. Let $f\in\mathcal{A}$ and let
us abbreviate
$f_{\Lambda}\equiv\upsilon_{\Lambda}^{\mu}\circ\tau_{\Lambda}(f)$. We have:

$f_{\Lambda}(g)=\int_{G}f(xg)d\mu(x),\qquad(\forall g\in G),$

or, equivalently, as a $C(G)$-valued integral:

$f_{\Lambda}=\int_{G}\lambda_{x^{-1}}(f)\,d\mu(x).$

Hence we have:

$\displaystyle\|f_{\Lambda}-f\|=$
$\displaystyle\left\|\int_{G}(\lambda_{x^{-1}}(f)-f)d\mu(x)\right\|\leq\int_{G}\|\lambda_{x^{-1}}(f)-f\|\,d\mu(x)$
$\displaystyle\leq$
$\displaystyle\int_{G}L(f)\,d(x^{-1},e)\,d\mu(x)\,=\,L(f)\int_{G}d(e,x)\,d\mu(x).$

For the composition $\tau_{\Lambda}\circ\upsilon_{\Lambda}^{\mu}$ consider an
arbitrary $T=\tau_{\Lambda}(f)\in\mathcal{A}_{\Lambda}$. We then have
$\upsilon_{\Lambda}^{\mu}(T)=f_{\Lambda}$ in the notation of the previous
paragraph, so that

$\tau_{\Lambda}\circ\upsilon_{\Lambda}^{\mu}(T)=\int_{G}\lambda_{x^{-1}}(T)\,d\mu(x),$

as an operator-valued integral, where we also used that $P_{\Lambda}$ commutes
with $\lambda_{x^{-1}}$ for all $x\in G$. But then it follows as before that

$\displaystyle\|\tau_{\Lambda}\circ\upsilon_{\Lambda}^{\mu}(T)-T\|=$
$\displaystyle\left\|\int_{G}(\lambda_{x^{-1}}(T)-T)d\mu(x)\right\|\leq\int_{G}\|\lambda_{x^{-1}}(T)-T\|\,d\mu(x)$
$\displaystyle\leq$
$\displaystyle\int_{G}L(T)\,d(x^{-1},e)\,d\mu(x)\,=\,L(T)\int_{G}d(e,x)\,d\mu(x).$

We thus obtain an upper bound for $\epsilon$ in Theorem 6 from which the
claimed upper bound on the Gromov–Hausdorff distance between
$S(\mathcal{A}_{\Lambda},L_{\Lambda})$ and $S(\mathcal{A},L)$ directly
follows. ∎

The remaining task in proving the Gromov–Hausdorff convergence is thus to find
a liftable $\mu$ for which the integral $\int_{G}d(e,x)d\mu(x)$ tends to 0. We
will take $\mu$ as close as possible to the Dirac mass $\delta_{e}$ with
respect to the weak topology; more precisely, we have:

######  Proposition 15.

Let
$S_{\mathcal{F}}=\bigcup_{\Lambda\in\mathcal{F}}\,\,\tau_{\Lambda}^{*}S(\mathcal{A}_{\Lambda})\subseteq
S(\mathcal{A})$ be the set of all Borel probability measures that can be
lifted to a state on some $\mathcal{A}_{\Lambda}$. Then $S_{\mathcal{F}}$ is a
dense subset of $S(\mathcal{A})$ for the weak∗ topology. In particular, for
all $\epsilon>0$ there exists $\mu\in S_{\mathcal{F}}$ such that:

(4) $\int_{G}d(e,x)d\mu(x)\leq\epsilon.$

###### Proof.

It is a standard result that density of the convex set $S_{\mathcal{F}}$ in
$S(\mathcal{A})$ will follow from the following equality: (see for instance
[11, Theorem 4.3.9]):

$\|f\|=\sup\,\\{|\sigma(f)|:\sigma\in S_{\mathcal{F}}\\},\qquad(\forall
f\in\mathcal{A}).$

Let $L^{2}(G)_{\mathcal{F}}=\sum_{\Lambda\in\mathcal{F}}L^{2}(G)_{\Lambda}$.
Since $L^{2}(G)_{\mathcal{F}}$ is a dense subspace of $L^{2}(G)$, we have for
all $f\in\mathcal{A}$:

$\|f\|=\sup\,\\{|\langle\psi,f\psi\rangle|:\psi\in
L^{2}(G)_{\mathcal{F}},\|\psi\|=1\\}.$

But $\langle\psi,\cdot\,\psi\rangle\in S_{\mathcal{F}}$ for all
$\psi\in\mathcal{F}$ such that $\|\psi\|=1$, so that we may conclude that
$S_{\mathcal{F}}$ is a dense subspace of $S(\mathcal{A})$ for the weak*
topology.

The state $\mu\in S_{\mathcal{F}}$ such that Equation (4) holds can then be
found as follows. Let $\delta_{e}$ be the state on $\mathcal{A}$ defined for
all $f\in\mathcal{A}$ by $\delta_{e}(f)=f(e)$. The function $\Delta:x\mapsto
d(e,x)$ is a Lipschitz function, hence an element of $\mathcal{A}$, so by
weak* density of $S_{\mathcal{F}}$ for all $\epsilon>0$ there exists $\mu\in
S_{\mathcal{F}}$ such that

$\int_{G}d(e,x)\,d\mu(x)=\left|\mu(\Delta)-\delta_{e}(\Delta)\right|\leq\epsilon,$

as desired. ∎

Now we can finally state and prove our main Theorem:

######  Theorem 16.

The net of compact metric spaces
$\left(S(\mathcal{A}_{\Lambda},L_{\Lambda})\right)_{\Lambda\in\mathcal{F}}$
converges to $S(\mathcal{A},L)$ in Gromov–Hausdorff sense.

###### Proof.

Let $\epsilon>0$ and let $\mu\in S_{\mathcal{F}}$ be a liftable probability
measure such as in Proposition 15, so that Equation (4) holds. In particular,
there is a $\Lambda_{0}\in\mathcal{F}$ such that $\mu$ is liftable to a state
on $\mathcal{A}_{\Lambda_{0}}$. Then for all $\Lambda\in\mathcal{F}$
containing $\Lambda_{0}$, the measure $\mu$ is liftable to a state on
$\mathcal{A}_{\Lambda}$. Applying Proposition 14 then yields for all
$\Lambda\in\mathcal{F}$ such that $\Lambda_{0}\subseteq\Lambda$ we have

$d_{GH}(S(\mathcal{A}_{\Lambda},L_{\Lambda}),S(\mathcal{A},L))\leq\epsilon,$

which completes the proof. ∎

## References

  * [1] K. Aguilar and J. Kaad.  The Podleś sphere as a spectral metric space.  J. Geom. Phys. 133 (2018) 260–278.
  * [2] K. Aguilar, J. Kaad, and D. Kyed.  The Podleś spheres converge to the sphere.  Comm. Math. Phys. 392 (2022) 1029–1061.
  * [3] E. M. Alfsen.  Compact convex sets and boundary integrals, volume Band 57 of Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas].  Springer-Verlag, New York-Heidelberg, 1971.
  * [4] T. Berendschot.  Truncated geometry.  Master’s thesis, Radboud University Nijmegen, 2019.
  * [5] A. Chamseddine and W. D. van Suijlekom.  A survey of spectral models of gravity coupled to matter.  In Advances in noncommutative geometry—on the occasion of Alain Connes’ 70th birthday, pages 1–51. Springer, Cham, 2019.
  * [6] A. Connes.  Compact metric spaces, Fredholm modules, and hyperfiniteness.  Ergodic Theory Dynam. Systems 9 (1989) 207–220.
  * [7] A. Connes and W. D. van Suijlekom.  Spectral truncations in noncommutative geometry and operator systems.  Comm. Math. Phys. 383 (2021) 2021–2067.
  * [8] A. Connes and W. D. van Suijlekom.  Tolerance relations and operator systems.  Acta Sci. Math. (Szeged) 88 (2022) 101–129.
  * [9] E. Hekkelman.  Truncated geometry on the circle.  Lett. Math. Phys. 112 (2022) Paper No. 20, 19.
  * [10] J. Kaad and D. Kyed.  A comparison of two quantum distances.  Mathematical Physics, Analysis and Geometry 26 (2023).
  * [11] R. V. Kadison and J. R. Ringrose.  Fundamentals of the theory of operator algebras. Vol. I, volume 100 of Pure and Applied Mathematics.  Academic Press Inc. [Harcourt Brace Jovanovich Publishers], New York, 1983\.  Elementary theory.
  * [12] D. Kerr.  Matricial quantum Gromov-Hausdorff distance.  J. Funct. Anal. 205 (2003) 132–167.
  * [13] A. W. Knapp.  Representation theory of semisimple groups, volume 36 of Princeton Mathematical Series.  Princeton University Press, Princeton, NJ, 1986.  An overview based on examples.
  * [14] F. Latrémolière.  The quantum Gromov-Hausdorff propinquity.  Trans. Amer. Math. Soc. 368 (2016) 365–411.
  * [15] F. Latrémolière.  The Gromov-Hausdorff propinquity for metric spectral triples.  Adv. Math. 404 (2022) Paper No. 108393, 56.
  * [16] M. Leimbach and W. D. van Suijlekom.  Gromov–Hausdorff convergence of spectral truncations for low-dimensional tori, arXiv:2302.07877.
  * [17] H. Li.  Compact quantum metric spaces and ergodic actions of compact quantum groups.  J. Funct. Anal. 256 (2009) 3368–3408.
  * [18] S. T. Rachev.  Probability metrics and the stability of stochastic models.  Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics. John Wiley & Sons, Ltd., Chichester, 1991.
  * [19] S. T. Rachev and L. Rüschendorf.  Mass transportation problems. Vol. I.  Probability and its Applications (New York). Springer-Verlag, New York, 1998.  Theory.
  * [20] M. A. Rieffel.  Convergence of Fourier truncations for compact quantum groups and finitely generated groups.  arXiv:2210.00387.
  * [21] M. A. Rieffel.  Metrics on states from actions of compact groups.  Doc. Math. 3 (1998) 215–229.
  * [22] M. A. Rieffel.  Gromov-Hausdorff distance for quantum metric spaces.  Mem. Amer. Math. Soc. 168 (2004) 1–65.
  * [23] M. A. Rieffel.  Matrix algebras converge to the sphere for quantum Gromov-Hausdorff distance.  Mem. Amer. Math. Soc. 168 (2004) 67–91.
  * [24] R. Toyota.  Quantum Gromov-Hausdorff convergence of spectral truncations for groups with polynomial growth, 2309.13469.
  * [25] W. D. van Suijlekom.  Gromov-Hausdorff convergence of state spaces for spectral truncations.  J. Geom. Phys. 162 (2021) Paper No. 104075, 11.