# Cooperation and Control in Delegation Games

Oliver Sourbut, Lewis Hammond11footnotemark: 1, and Harriet Wood Equal
contribution. Correspondence to<EMAIL_ADDRESS>and
<EMAIL_ADDRESS>
(University of Oxford)

> Abstract
>
> Many settings of interest involving humans and machines – from virtual
> personal assistants to autonomous vehicles – can naturally be modelled as
> principals (humans) delegating to agents (machines), which then interact
> with each other on their principals’ behalf. We refer to these multi-
> principal, multi-agent scenarios as _delegation games_. In such games, there
> are two important failure modes: problems of control (where an agent fails
> to act in line their principal’s preferences) and problems of cooperation
> (where the agents fail to work well together). In this paper we formalise
> and analyse these problems, further breaking them down into issues of
> _alignment_ (do the players have similar preferences?) and _capabilities_
> (how competent are the players at satisfying those preferences?). We show –
> theoretically and empirically – how these measures determine the principals’
> welfare, how they can be estimated using limited observations, and thus how
> they might be used to help us design more aligned and cooperative AI
> systems.

##  1 Introduction

With the continuing development of powerful and increasing general AI systems,
we are likely to see many more tasks delegated to autonomous machines, from
writing emails to driving us from place to place. Moreover, these machines are
increasingly likely to come into contact with each other when acting on behalf
of their human principals, whether they are virtual personal assistants
attempting to schedule a meeting or autonomous vehicles (AVs) using the same
road network. We refer to these multi-principal, multi-agent scenarios as
_delegation games_ , an example of which is as follows, and is shown in Figure
1.

######  Example 1.

Two AVs can choose between two different routes on behalf of their passengers:
$A$(utobahn) or $B$(eachfront). Their objective functions are determined by
the speed and comfort of the journey (which may not be the same objective as
their passenger). Each AV receives utility $6$ or $2$ for routes $A$ or $B$,
respectively, with an additional penalty of $-3$ or $-2$ if both AVs choose
the same route (due to the delays caused by congestion). The passengers’
preferences are more idiosyncratic and as shown.

In delegation games there are two primary ways in which things can go wrong.
The first is that a (machine) agent might not act according to the (human)
principal’s objective, such as when an AV takes an undesirable route to a
destination. The second is that agents may fail to reach a cooperative
solution, even if they are acting in line with their principals’ objectives,
such as when multiple AVs take the same route to their destinations and end up
causing congestion. The first represents a _control_ problem [37], and the
second represents a _cooperation_ problem [15, 13].

| $A$ | $B$ |
---|---|---|---
$A$ |  3, 3 |  6, 2 |
$B$ |  2, 6 |  0, 0 |
(a)

| $A$ | $B$ |
---|---|---|---
$A$ |  2, 3 |  3, 3 |
$B$ |  4, 6 |  3, 0 |
(b)

(c)

Figure 1: (a) The payoffs of the agents in Example 1; (b) the payoffs of the
principals; and (c) a graphical representation of the full delegation game,
with vertical arrows indicating control and horizontal arrows indicating
cooperation.

Control and cooperation can in turn be broken down into problems of
_alignment_ and of _capabilities_ [22, 9, 7]. For example, in the control
failure above, the first AV might drive undesirably by taking route $A$ even
though their passenger prefers the scenic beachfront (an alignment problem),
or the second AV might undesirably take route $B$ because it is incapable of
calculating the best route accurately (a capabilities problem). Similarly, in
the cooperation failure, the AVs might cause congestion because they cannot
plan and communicate effectively enough (a capabilities problem), or because
their objectives are opposed to one another – e.g. they cannot both drive
alone on route $A$ – even if they have the ability to cooperate in general (an
alignment problem).

As one might expect, ensuring good outcomes for the principals requires
overcoming _all_ of these problems. This goal is made even more challenging
because most research considers each in isolation – such as cooperation
between agents with the same objective [44, 35, 16], or alignment between a
single principal and agent [25, 42, 37] – despite this being an increasingly
unrealistic assumption when it comes to the deployment of AI. In order to
ensure positive outcomes, we cannot rely on solutions to only _some_ of these
problems.

###  1.1 Contributions

In this work we provide the first systematic investigation of these four
failure modes and their interplay. More concretely, we make the following
three core contributions: _measures_ for assessing each failure mode that
satisfy a number of key desiderata (in Section 4); _theoretical results_
describing the relationships between these measures and principal welfare (in
Section 5); and _experiments_ that validate these results and explore how the
measures can be inferred from limited observations (in Section 6). In doing
so, we formalise and substantiate the intuition that solving all four of these
problems is, in general, both necessary _and_ sufficient for good outcomes in
multi-agent settings, which in turn has important implications for the project
of building safe and beneficial AI systems.

###  1.2 Related Work

Given the foundational nature of the problems we study in this work, there is
a vast amount of relevant prior research; due to space constraints we mention
only a few exemplars on each topic. The _principal-agent literature_ typically
considers settings with a single principal and agent [28]. While there exist
multi-agent variants such as competing mechanism games [54, 33], to the best
of our knowledge no previous work investigates the general requirements for
high principal welfare. Our setting is also similar to that of _strategic
delegation_ [46, 38], though we do not focus on principals’ responses to each
other’s choice of agents.

The degree of alignment between two or more agents can be viewed as a measure
of _similarity between preferences_. Such measures have been introduced in
areas such as mathematical economics [5], computational social choice [1], and
reinforcement learning [20, 40], though these works focus on either
cooperation _or_ alignment. In game theory, there are several classical values
that measure the _degree of (and costs from) competition_ in a game, such as
the price of anarchy [26] or coco value [24]. Other important works consider
the robustness of these values under approximate equilibria [4, 36]. We take
inspiration from these ideas, extending them to settings in which the game we
study is a _proxy_ for the game whose value we truly care about.

There have been several proposals for how to formally measure the capabilities
of an agent. These include formal definitions of, e.g. _general_ intelligence
[29], _social_ intelligence [23], and _collective_ intelligence [52]. In this
work, we focus on how capabilities at the individual and collective level can
be distinguished and how they combine with alignment to impact welfare.
Similarly, definitions of _cooperation_ also abound (see [45] for an overview)
though these are often informal and/or inconsistent [51], whereas we require a
mathematical formalisation appropriate for applications to AI systems.

Finally, when it comes to estimating such properties from data, there is a
large literature on the problem of _preference elicitation/learning_ [18, 17],
including in general-sum games [11, 19, 55]. The latter setting is also
studied in _empirical game theory_ [50, 48, 49, 27], including in recent work
on inferring properties such as the price of anarchy [12]. Other works attempt
to quantify the capabilities of (reinforcement learning) agents by assessing
their generalisation to different environments [10] or co-players [30]. While
such ideas do not form the core of our present work, we make use of them in
our final set of experiments.

##  2 Background

In general, we use uppercase letters to denote sets, and lowercase letters to
denote elements of sets or functions. We use boldface to denote tuples or sets
thereof, typically associating one element to each of an ordered collection of
players. Unless otherwise indicated, we use superscripts to indicate an agent
$1\leq i\leq n$ and subscripts $j$ to index the elements of a set; for
example, player $i$’s $j^{\text{th}}$ (pure) strategy is denoted by
$s^{i}_{j}$. We also use the $\hat{}$ symbol to represent principals; for
example, the $i^{\text{th}}$ principal’s utility function is written
$\hat{u}^{i}$. A notation table can be found for reference in Appendix A.

######  Definition 1.

A (strategic-form) game between $n$ players is a tuple $G=(\bm{S},\bm{u})$
where $\bm{S}=\bigtimes_{i}S^{i}$ is the product space of (pure) strategy sets
$S^{i}$ and $\bm{u}$ contains a utility function $u^{i}:\bm{S}\to\mathbb{R}$,
for each agent $1\leq i\leq n$. We write $s^{i}\in S^{i}$ and
$\bm{s}\in\bm{S}$ to denote pure strategies and pure strategy profiles,
respectively. A mixed strategy for player $i$ is a distribution
$\sigma^{i}\in\Sigma^{i}$ over $S^{i}$, and a mixed strategy profile is a
tuple
$\bm{\sigma}=(\sigma^{1},\ldots,\sigma^{n})\in\bm{\Sigma}\coloneqq\bigtimes_{i}\Sigma^{i}$.
We will sometimes refer to pure strategy profiles in strategic-form games as
outcomes. We write $\bm{s}^{-i}\in\bm{S}^{-i}\coloneqq\bigtimes_{j\neq
i}S^{j}$ and therefore $\bm{s}=(\bm{s}^{-i},s^{i})$, with analogous notation
for mixed strategies. We also abuse notation by sometimes writing
$u^{i}(\bm{\sigma})\coloneqq\mathbb{E}_{\bm{\sigma}}\big{[}u^{i}(\bm{s})\big{]}$
and
$\bm{u}(\bm{\sigma})\coloneqq\big{(}u^{1}(\bm{\sigma}),\ldots,u^{n}(\bm{\sigma})\big{)}\in\mathbb{R}^{n}$.

Formally, a _solution concept_ can be represented as a function that maps from
games $G$ to subsets of the mixed strategy profiles $\bm{\Sigma}$ in $G$.
These concepts pick out certain strategy profiles based on assumptions about
the (bounded) rationality of the individual players. The canonical solution
concept is the Nash equilibrium.

######  Definition 2.

Given some $\bm{\sigma}^{-i}$ in a game $G$, $\sigma^{i}$ is a best response
(BR) for player $i$ if
$u^{i}(\bm{\sigma})\geq\max_{\tilde{\sigma}^{i}}u^{i}(\bm{\sigma}^{-i},\tilde{\sigma}^{i})$.
We write the set of best responses for player $i$ as
$\text{BR}(\bm{\sigma}^{-i};G)$. A Nash equilibrium (NE) in a game $G$ is a
mixed strategy profile $\bm{\sigma}$ such that
$\sigma^{i}\in\text{BR}(\bm{\sigma}^{-i};G)$ for every player $i$. We denote
the set of NEs in $G$ by $\text{NE}(G)$.

A _social welfare function_ $w:\mathbb{R}^{n}\to\mathbb{R}$ in an $n$-player
game maps from payoff profiles $\bm{u}(\bm{s})$ to a single real number,
aggregating players’ payoffs into a measure of collective utility. We again
abuse notation by writing $w(\bm{s})\coloneqq w\big{(}\bm{u}(\bm{s})\big{)}$
and $w(\bm{\sigma})\coloneqq\mathbb{E}_{\bm{\sigma}}\big{[}w(\bm{s})\big{]}$.
In the remainder of this paper, we assume use of the following social welfare
function, though the concepts we introduce do not heavily depend on this
choice.

######  Definition 3.

Given a strategy profile $\bm{s}$, the average utilitarian social welfare is
given by $w(\bm{s})=\frac{1}{n}\sum_{i}u^{i}(\bm{s})$.

##  3 Delegation Games

In this work, we make the simplifying assumption that there is a one-to-one
correspondence between principals and agents, and that each principal
delegates fully to their corresponding agent (i.e. only agents can take
actions). Our basic setting of interest can thus be characterised as follows.

######  Definition 4.

A (strategic-form) delegation game with $n$ principals and $n$ agents is a
tuple $D=(\bm{S},\bm{u},\bm{\hat{u}})$, where $G\coloneqq(\bm{S},\bm{u})$ is
the game played by the agents, and $\hat{G}\coloneqq(\bm{S},\bm{\hat{u}})$ is
the game representing the principals’ payoffs as a function of the agents’
pure strategies.

We refer to $G$ as the _agent game_ and $\hat{G}$ as the _principal game_. For
instance, $G$ and $\hat{G}$ from Example 1 are shown in Figures 1(a) and 1(b)
respectively. When not referring to principals or agents specifically, we
refer to the _players_ of a delegation game. We denote the welfare in a
delegation game for the principals and agents as $\hat{w}(\bm{s})$ and
$w(\bm{s})$, respectively.

######  Definition 5.

Given a game $G$ and a social welfare function $w$, we define the maximal
(expected) welfare achievable under $w$ as
$w_{\star}(G)\coloneqq\max_{\bm{\sigma}}w(\bm{\sigma})$. We define the ideal
welfare under $w$ as $w_{+}(G)\coloneqq w(\bm{u}_{+})$ where
$\bm{u}_{+}[i]=\max_{\bm{s}}u^{i}(\bm{s})$. Similarly, we denote
$w_{\bullet}(G)\coloneqq\min_{\bm{\sigma}}w(\bm{\sigma})$ and
$w_{-}(G)\coloneqq w(\bm{u}_{-})$ where
$\bm{u}_{-}[i]=\min_{\bm{s}}u^{i}(\bm{s}).$ We extend these definitions to
_delegation_ games $D$ by defining $w_{\dagger}(D)\coloneqq w_{\dagger}(G)$
and $\hat{w}_{\dagger}(D)\coloneqq w_{\dagger}(\hat{G})$, for
$\dagger\in\\{\star,+,\bullet,-\\}$. When unambiguous, we omit the reference
to $D$.

Note that the maximal and ideal welfare may not be equivalent. For instance,
in Example 1 we have $w_{\star}=7$ but $w_{+}=10$. The former is the maximum
achievable among the available outcomes, while the latter is what would be
achievable if all principals were somehow able to receive their maximal payoff
simultaneously. We return to this distinction, represented graphically in
Figure 2, later. In general, our dependent variables of interest will be the
principals’ welfare regret $\hat{w}_{\star}-\hat{w}(\bm{\sigma})$ and the
difference $\hat{w}_{+}-\hat{w}_{\star}$.

$w_{-}$$w_{\bullet}$$w(\bm{\sigma})$$w_{\star}$$w_{+}$ Figure 2: The range of
social welfares in a game $G$.

##  4 Control and Cooperation

In Section 1, we distinguished between _alignment_ and _capabilities_ as
contributors to the level of both control and cooperation. Our goal is to
investigate how variations in the alignment and capabilities of agents impact
the welfare of the principals. We therefore require ways to measure these
concepts. Before doing so, we put forth a set of natural desiderata that we
argue _any_ any such measures should satisfy.111Formalisations of these
desiderata are given as part of results in Section 5.1.

  1. (D1)

Alignment and capabilities – both individual and collective – are all
‘orthogonal’ to one another in the sense that they can be instantiated in
arbitrary combinations.

  2. (D2)

Two players are perfectly individually aligned (misaligned) if and only if
they have identical (opposite) preferences. Two or more players are perfectly
_collectively_ aligned if and only if they have identical preferences.

  3. (D3)

If a set of agents are maximally capable, they achieve maximal _agent_
welfare. If they are also maximally individually aligned, then maximal
_principal_ welfare is also achieved.222We shall see later that a further
‘fairness’ criterion on the weighting of agents’ utilities is also required
for the second part of this desideratum to hold.

  4. (D4)

If a set of players are perfectly collectively aligned, then their maximal
welfare is their ideal welfare.

  5. (D5)

Individual measures are independent of any transformations to the game that
preserve _individual_ preferences, and collective measures are independent of
any transformations that preserve _collective_ preferences (as captured by
some measure of social welfare).

###  4.1 Control

We begin by considering the control of a single agent by a single principal.
In essence, we wish to capture the degree to which an agent is acting in line
with its principal’s preferences. As we – and others [7, 9, 22, 2] – have
noted, this can be decomposed into a question of: a) how similar the agent’s
preferences are to the principal’s; and b) how capable the agent is of
pursuing its preferences.

####  4.1.1 Alignment

How can we tell if principal $i$’s and agent $i$’s preferences are similar?
First, we must be more precise about what we mean by preferences. Following
our assumption that agents may play stochastically, we view preferences as
orderings over _distributions_ of outcomes
$\bm{\sigma}\preceq\bm{\sigma}^{\prime}\Leftrightarrow u(\bm{\sigma})\leq
u(\bm{\sigma}^{\prime})$.333Note that in strategic-form games, (mixed)
strategy profiles are equivalent to distributions over the domain of players’
utility functions, but in general this need not be the case. To compare the
preferences of principal $i$ ($\hat{\preceq}^{i}$) and agent $i$
($\preceq^{i}$) we can therefore compare $\hat{u}^{i}$ and $u^{i}$. It is
well-known, however, that the same preferences can be represented by different
utility functions. In particular, $u$ and $u^{\prime}$ represent the same
preferences if and only if one is a positive affine transformation of the
other [31].

In order to meaningfully measure the difference between two utility functions,
therefore, we must map each to a canonical element of the equivalence classes
induced by the preferences they represent. We define such a map using a
_normalisation function_ $\nu:U\to U$, where
$U\coloneqq\mathbb{R}^{\lvert\bm{S}\rvert}$ represents the space of utility
functions in a game $G$. There are many possible choices of normalisation
function, but in essence they must consist of a constant shift $c$ and a
multiplicative factor $m$ [43], which together define the affine relationship.
To satisfy our desiderata, we place additional requirements on $m$ and $c$, as
follows.

######  Definition 6.

For each player $i$ in $G$, we define their normalised utility function
$\nu(u^{i})=u^{i}_{\nu}$ as:

$u^{i}_{\nu}\coloneqq\begin{cases}0&\text{ if
}m\big{(}u^{i}-c(u^{i})\bm{1}\big{)}=0\\\
\frac{u^{i}-c(u^{i})\bm{1}}{m(u^{i}-c(u^{i})\bm{1})}&\text{
otherwise,}\end{cases}$

where $c:U\to\mathbb{R}$ is an affine-equivariant shift function and
$m:U\to\mathbb{R}$ is any strictly convex norm.

For notational convenience, we sometimes write $c^{i}\coloneqq c(u^{i})\bm{1}$
and $m^{i}\coloneqq m(u^{i}-c^{i})$, with equivalent notation $\hat{c}^{i}$
and $\hat{m}^{i}$ when applied to $\hat{u}^{i}$, resulting in
$\hat{u}^{i}_{\nu}$. Then $u^{i}=m^{i}u_{\nu}^{i}+c^{i}$.

######  Lemma 1.

For any $u,u^{\prime}\in U$, $u_{\nu}=u^{\prime}_{\nu}$ if and only if
$\preceq=\preceq^{\prime}$.

Given $\hat{u}^{i}_{\nu}$ and $u^{i}_{\nu}$, a natural way to measure the
degree of alignment between the $i^{\text{th}}$ principal and agent is to
compute some kind _distance_ between $\hat{u}^{i}_{\nu}$ and $u^{i}_{\nu}$. To
do so, we use a norm of the difference between $\hat{u}^{i}_{\nu}$ and
$u^{i}_{\nu}$, which gives rise to the following pseudometric over $U$. In
order to contrast this principal-agent alignment measure with our later
alignment measure over $n$ players, we sometimes refer to this as _individual_
(as opposed to _collective_) alignment.

######  Definition 7.

Given a delegation game $D$, the (individual) alignment between agent $i$ and
their principal is given by
$\text{IA}^{i}(D)=1-\frac{1}{2}m(\hat{u}^{i}_{\nu}-u^{i}_{\nu})$, where $m$ is
the same (strictly convex) norm used for normalisation.

The choice of norm and shift functions $m$ and $c$ determine which differences
between payoffs are emphasised by the measure. One way to make this choice is
by writing $m=\lVert\cdot\rVert_{d}$, where $d$ is a distribution over
$\bm{S}$. But how should one choose $d$ and $\lVert\cdot\rVert$?

Beginning with $d$, one’s first intuition might be to consider a distribution
over the _equilibria_ of the game. Assuming agents act self-interestedly,
there are certain outcomes that are game-theoretically untenable; divergences
between preferences over these outcomes could reasonably be ignored. This
intuition, however, conflicts with one of our primary desiderata (D1), which
is to tease apart the difference between alignment and capabilities – in the
next subsection, we show that agents’ individual capabilities determine the
equilibria of the game. Instead, we argue that the outcome of a game does
_not_ change the extent to which preferences (dis)agree, and so in general
assume that $d$ has full support.

Our primary requirements on $\lVert\cdot\rVert$ are that $m$ is _strictly
convex_ and is the _same_ in Definitions 6 and 7. These restrictions are
required in order to satisfy all of our desiderata, but relaxations are
possible if fewer requirements are needed (see Appendix E.2 for more
discussion).

####  4.1.2 Capabilities

One obvious way of creating a formal measure of an agent’s capabilities is to
consider the number of (distinct) strategies they have available to them. In
the cases of boundedly rational agents or multi-agent settings, however, it
can beneficial to restrict one’s action space, either for computational
reasons [50], or by pre-committing to avoid temptation [21], or to force one’s
opponent to back down [34]. Alternatively, one could invoke a complexity-
theoretic measure of capabilities by considering the time and memory available
to each agent, though in this work we aim to be agnostic to such constraints.

Instead, inspired by the seminal work of [29], we view an individual agent’s
capabilities as the degree to which it is able to achieve its objectives in a
range of situations, regardless of what those objectives are. In game-
theoretic parlance, we consider the _rationality_ of the agent. We can
naturally formalise this idea by defining an agent’s capabilities as the
degree of optimality of their responses to a given partial strategy profile
$\bm{\sigma}^{-i}$.

######  Definition 8.

Given some $\bm{\sigma}^{-i}$ in a game $G$, a mixed strategy $\sigma^{i}$ is
an $\epsilon^{i}$-best response ($\epsilon^{i}\text{-BR}$) for player $i$ if:

$\displaystyle u^{i}(\bm{\sigma})$
$\displaystyle\geq\min_{\tilde{\sigma}^{i}}u^{i}(\bm{\sigma}^{-i},\tilde{\sigma}^{i})$
$\displaystyle+(1-\epsilon^{i})\big{(}\max_{\tilde{\sigma}^{i}}u^{i}(\bm{\sigma}^{-i},\tilde{\sigma}^{i})-\min_{\tilde{\sigma}^{i}}u^{i}(\bm{\sigma}^{-i},\tilde{\sigma}^{i})\big{)}.$

We write the set of such best responses for player $i$ as
$\epsilon^{i}\text{-BR}(\bm{\sigma}^{-i};G)$. An $\bm{\epsilon}$-Nash
equilibrium ($\bm{\epsilon}\text{-NE}$) in a game $G$ is a mixed strategy
profile $\bm{\sigma}$ such that
$\sigma^{i}\in\epsilon^{i}\text{-BR}(\bm{\sigma}^{-i};G)$ for every every
player $i$, where $\bm{\epsilon}=(\epsilon^{1},\ldots,\epsilon^{n})$. We
denote the set of $\bm{\epsilon}\text{-NE}$s in $G$ by
$\bm{\epsilon}\text{-NE}(G)$.

In essence, $\epsilon^{i}$ captures the fraction of their attainable utility
that player $i$ manages to achieve. Note that if $\epsilon^{i}=0$ then
$\epsilon^{i}\text{-BR}(\bm{\sigma}^{-i};G)=\text{BR}(\bm{\sigma}^{-i};G)$ and
if $\epsilon^{i}=1$ then
$\epsilon^{i}\text{-BR}(\bm{\sigma}^{-i};G)=\Sigma^{i}$. Similarly, when
$\bm{\epsilon}=\bm{0}$ then $\bm{\epsilon}\text{-NE}(G)=\text{NE}(G)$, and
when $\bm{\epsilon}=\bm{1}$ then $\bm{\epsilon}\text{-NE}(G)=\bm{\Sigma}$.

######  Definition 9.

Given a delegation game $D$, the individual capabilities of agent $i$ are
$\text{IC}^{i}(D)\coloneqq 1-\epsilon^{i}\in[0,1]$ where $\epsilon^{i}$ is the
smallest value such that agent $i$ plays an $\epsilon^{i}$-best response in
$G$.

Unlike other formulations of bounded rationality, such as a softmax strategy
or randomisation with some fixed probability, Definition 9 – which is
analogous to _satisficing_ [39, 41] – is agnostic as to the precise
_mechanism_ via which players are irrational, and thus serves as a general-
purpose descriptor of a player’s (ir)rationality level.444Our choice of
$\epsilon^{i}$-best responses could also be weakened to, e.g.
$\epsilon^{i}$-rationalisability [6, 32].

###  4.2 Cooperation

In order to achieve good outcomes for the principals, it is not sufficient for
the agents to coordinate with their principals individually, they must also
coordinate with one another. Indeed, it is easy to show that the principals’
welfare regret can be arbitrarily high in the only NE of a game, despite
perfect control of each agent by its principal.

######  Lemma 2.

There exists a (two-player, two-action) delegation game $D$ such that for any
$x>0$, however small, even if $\text{IA}(D)=\bm{1}$ and $\text{IC}(D)=\bm{1}$,
we have only one NE $\bm{\sigma}$, and
$\frac{\hat{w}_{\star}-\hat{w}(\bm{\sigma})}{\hat{w}_{+}-\hat{w}_{-}}=1-x$.

To achieve low principal welfare regret, we need to have a sufficiently high
degree of cooperation, both in terms of: a) collective _alignment_ (the extent
to which agents have similar preferences); and b) collective _capabilities_
(the extent to which agents can work together to overcome their differences in
preferences).

####  4.2.1 Alignment

Intuitively, it should be easier to achieve high welfare in a game where the
players have similar preferences over outcomes than one in which the players
have very different preferences. At the extremes of this spectrum we have
zero-sum games and common-interest games, respectively. This intuition can be
formalised by generalising Definition 7 to measure the degree of alignment
between $n$ utility functions, rather than two, as follows.

######  Definition 10.

Given a delegation game $D$, the collective alignment between the agents is
given by:

$\text{CA}(D)=1-\sum_{i}\frac{m^{i}}{\sum_{j}m^{j}}\cdot
m(\mu^{w}-u^{i}_{\nu}),$

where $\mu^{w}\coloneqq\frac{\sum_{i}u^{i}-c^{i}}{\sum_{i}m^{i}}$ is a proxy
for the agents’ (normalised) welfare, recalling that $m^{i}\coloneqq
m(u^{i}-c^{i})$.

Intuitively, we consider the misalignment of each agent from a hypothetical
agent whose objective is precisely to promote overall social welfare. This
misalignment is weighted by $m^{i}$, the idea being that the ‘stronger’ agent
$i$’s preferences (and hence the larger $m^{i}$ is), the more their
misalignment with the overall welfare of the collective matters. While it may
not be immediately obvious why we use $\mu^{w}$ instead of $\nu(w)$, the
former will allow us to derive tighter bounds and can easily be shown to
induce the same ordering over mixed strategy profiles as $w$ (and hence also
$\nu(w)$).

######  Lemma 3.

For any $\bm{\sigma},\bm{\sigma}^{\prime}\in\bm{\Sigma}$,
$\mu^{w}(\bm{\sigma})\leq\mu^{w}(\bm{\sigma}^{\prime})$ if and only if
$w(\bm{\sigma})\leq w(\bm{\sigma}^{\prime})$.

Unfortunately, collective alignment (even when paired with perfect control) is
insufficient for high principal welfare. The most trivial examples of this are
equilibrium selection problems, but we can easily construct a game with a
_unique_ NE and arbitrarily high welfare regret, even when we have perfect
control and arbitrarily high collective alignment. These issues motivate our
fourth and final measure.

######  Lemma 4.

There exists a family of (two-player, $k$-action) delegation games $D$ such
that even if $\text{IA}^{i}(D)=1$, $\text{IC}^{i}(D)=1$ for each agent, and
there is only one NE $\bm{\sigma}$, we have $\lim_{k\to\infty}\text{CA}(D)=1$
but
$\lim_{k\to\infty}\frac{\hat{w}_{\star}-\hat{w}(\bm{\sigma})}{\hat{w}_{+}-\hat{w}_{-}}=1$.

####  4.2.2 Capabilities

One way to model collective capabilities is as ‘internal’ to the game $G$.
Under this conceptualisation, we assume that the ability of the agents to
cooperate is captured entirely by their actions and payoffs in $G$. For
example, if the agents were able to coordinate in $G$ using a commonly
observed signal $\gamma$, then this would be modelled as them playing a
_different_ game $G^{\prime}$, in which each agent’s action consists of a
choice of action in $G$ given their observation of $\gamma$.555Thus, in a
_true_ prisoner’s dilemma, the ‘only thing to do’ (and therefore trivially the
cooperative action) is to defect. The idea here is that if the agents
possessed better cooperative capabilities, they would not be faced with an
actual prisoner’s dilemma to begin with.

This approach, however, conflates the agents’ collective alignment with their
collective capabilities. In order to tease these concepts apart, we require a
way to measure the extent to which the agents can avoid welfare loss due to
their selfish incentives. Perhaps the best known formalisation of this loss is
the _price of anarchy_ [26], which captures the difference in welfare between
the best possible outcome and the worst possible NE.666Considering the worst
case enables us to capture the welfare loss from equilibrium selection
problems even in common-interest games. Inspired by this idea, we measure the
collective capabilities of a group of agents as follows.

######  Definition 11.

Let
$w_{\bm{\epsilon}}\coloneqq\min_{\bm{\sigma}\in\bm{\epsilon}\text{-NE}(G)}w(\bm{\sigma})$.
Given a delegation game $D$ where the agents have individual capabilities
$\bm{\epsilon}$, the collective capabilities of the agents are
$\text{CC}(D)\coloneqq\delta\in[0,1]$ if and only if the agents achieve
welfare at least $w_{\bm{\epsilon}}+\delta\cdot(w_{\star}-w_{\bm{0}})$, where
recall that $\bm{0}$-$\text{NE}(G)=\text{NE}(G)$.777As remarked in Footnote 4,
the use of $\bm{\epsilon}\text{-NE}$s is not intrinsic to our definition of
(collective) capabilities and could be weakened to, e.g.
$\bm{\epsilon}$-rationalisable outcomes.

Note that if $\epsilon^{i}\geq\tilde{\epsilon}^{i}$ for every $1\leq i\leq n$,
then we must have $w_{\bm{\epsilon}}\leq w_{\tilde{\bm{\epsilon}}}$; a special
case of this is that $w_{\bm{0}}\geq w_{\bm{\epsilon}}$. In other words, the
individual irrationality of the agents can only _lower_ the (worst-case)
welfare loss. On the other hand, we can see that greater collective
capabilities can potentially compensate for this loss.

As in the case of individual capabilities, we provide a measure that is
agnostic to the precise mechanism via which the agents cooperate, be it
through commitments, communications, norms, institutions, or more exotic
schemes. Rather, we take as input the fact that agents are able to obtain a
certain amount of welfare, and use this quantify how well they are
cooperating. At one extreme, they do no better than $w_{\bm{\epsilon}}$, at
the other they get as close to the maximal welfare $w_{\star}$ as their
individual capabilities will allow.

##  5 Theoretical Results

We begin our theoretical results by proving that the measures defined in the
preceding section satisfy our desiderata, before using them to bound the
principals’ welfare regret.

###  5.1 Desiderata

The fact that we define alignment as a feature of the underlying _game_ , and
capabilities are a feature of how the game is _played_ means that capabilities
and alignment are naturally orthogonal. The potentially arbitrary difference
between the principals’ and agents’ utility functions is the key to the other
parts of the following result.

######  Proposition 1 (D1).

Consider a delegation game $D$ with measures $\text{IA}(D)$, $\text{IC}(D)$,
$\text{CA}(D)$, and $\text{CC}(D)$. Holding fixed any three of the measures,
then for any value $v\in[0,1]$ (or $\bm{v}\in[0,1]^{n}$ for IA or IC), there
is a game $D^{\prime}$ such that the fourth measure takes value $v$ ($\bm{v}$)
in $D^{\prime}$ and the other measures retain their previous values.

D2 follows chiefly from classic results linking preferences over mixed
strategy profiles to sets of utility functions that are positive affine
transformations of one another.

######  Proposition 2 (D2).

For any $1\leq i\leq n$, $\text{IA}^{i}=1$ ($\text{IA}^{i}=0$) if and only if
$\preceq^{i}=\hat{\preceq}^{i}$ ($\preceq^{i}=\hat{\succeq}^{i}$). Similarly
$\text{CA}=1$ if and only if $\preceq^{i}=\preceq^{j}$ for every $i,j\in N$.

The first half of D3 is straightforward. The subtlety in the second half is
that – perhaps counterintuitively, at first – perfect capabilities (both
individual and collective) and perfect alignment between the principals and
their agents is _not_ sufficient for the principals to achieve maximal welfare
(unlike the agents). Rather, the resulting solution will be one (merely) on
the Pareto frontier for the principals.

In essence, this is because individual alignment does not preserve _welfare
orderings_ $\preceq^{w}$, only individual preference orderings $\preceq^{i}$.
Recalling that $\hat{m}^{i}$ and $m^{i}$ quantify the magnitudes of
$\hat{u}^{i}$ and $u^{i}$ respectively, we can see that, in general, the
aggregation over agents’ utilities (used to measure their success at
cooperating) may not give the same weight to each party as the aggregation
over principals’ utilities (used to measure the value we care about).
Alternatively, the variation in magnitudes $m^{i}$ can be viewed as capturing
a notion of fairness (used to select a point on the Pareto frontier), which
may not be the same as in $\hat{G}$ unless $\hat{m}^{i}=r\cdot m^{i}$ for some
$r>0$. Further discussion on this point can be found in Appendix E.3.

######  Proposition 3 (D3).

If $\text{IC}=\bm{1}$ and $\text{CC}=1$ then any strategy $\bm{\sigma}$ the
agents play is such that $w(\bm{\sigma})=w_{\star}$. If $\text{IA}=\bm{1}$
then $\bm{\sigma}$ is Pareto-optimal for the principals. If, furthermore,
$\hat{m}^{i}=r\cdot m^{i}$ for some $r>0$ for all $i$, then
$\hat{w}(\bm{\sigma})=\hat{w}_{\star}$.

The proof of D4 follows naturally from Definition 10. The final desideratum
(D5) is simple in the case of individual preferences (due to the form of our
normalisation function). In the case of collective preferences (i.e. the
ordering $\preceq^{w}$ over mixed strategies induced by $w$), we make use of
the fact that the relative magnitude of the agents’ utility functions in both
games must be the same (which is closely related to the ‘fairness’ condition
$\hat{m}^{i}=r\cdot m^{i}$ in Proposition 3).

######  Proposition 4 (D4).

If $\text{CA}=1$ then $w_{\star}=w_{+}$.

######  Proposition 5 (D5).

Given a delegation game $D_{1}$, let $D_{2}$ be such that
$\preceq^{i}_{1}=\preceq^{i}_{2}$ and
$\hat{\preceq}^{i}_{1}=\hat{\preceq}^{i}_{2}$ for each $1\leq i\leq n$. Then
$\text{IA}(D_{1})=\text{IA}(D_{2})$ and $\text{IC}(D_{1})=\text{IC}(D_{2})$.
Moreover, if $D_{2}$ is such that $\preceq^{w}_{1}=\preceq^{w}_{2}$ and the
$u^{i}$ are affine-independent, then $\text{CA}(D_{1})=\text{CA}(D_{2})$ and
$\text{CC}(D_{1})=\text{CC}(D_{2})$ as well.

###  5.2 Bounding Welfare Regret

The primary question we investigate in this work is how the principals fare
given the different levels of control and cooperation in the game played by
the agents. We begin by characterising the _principals’_ welfare in terms of
the _agents’_ utilities, and the alignment of each agent with its principal.

######  Proposition 6.

Given a delegation game $D$, we have:

$\hat{w}_{\star}-\hat{w}(\bm{\sigma})\leq\frac{1}{n}\sum_{i}r^{i}\big{(}u^{i}(\hat{\bm{s}}_{\star})-u^{i}(\bm{\sigma})\big{)}+\frac{4K}{n}\hat{\bm{m}}^{\top}(\bm{1}-\text{IA}),$

where $r^{i}\coloneqq\frac{\hat{m}^{i}}{m^{i}}$,
$\hat{\bm{m}}[i]=\hat{m}^{i}$, $K$ satisfies $\lVert
u_{\nu}-u^{\prime}_{\nu}\rVert_{\infty}\leq K\cdot
m(u_{\nu}-u^{\prime}_{\nu})$ for any $u,u^{\prime}\in U$, and
$\hat{w}(\hat{\bm{s}}_{\star})=\hat{w}_{\star}$.

Using this result, we can bound the principals’ welfare regret in terms of
both principal-agent alignment _and_ the agents’ welfare regret, which is in
turn a function of the agents’ capabilities. As we saw in Propositions 3 and
5, the ‘calibration’ between the principals and agents – as captured by the
potentially differing ratios $r^{i}$ – remains critical for ensuring we reach
better outcomes in terms of principal welfare.

######  Theorem 1.

Given a delegation game $D$, we have that:

$\displaystyle\hat{w}_{\star}-\hat{w}(\bm{\sigma})$
$\displaystyle\leq\frac{4K}{n}\hat{\bm{m}}^{\top}(\bm{1}-\text{IA})+r^{*}\left((w_{\bm{0}}-w_{\bm{\epsilon}})\right.$
$\displaystyle+\left.(1-\text{CC})(w_{\star}-w_{\bm{0}})\right)+R(\bm{\sigma}),$

where $\text{IC}=\bm{1}-\bm{\epsilon}$,
$r^{*}\in[\min_{i}r^{i},\max_{i}r^{i}]$,
$R(\bm{\sigma})\coloneqq\frac{1}{n}\sum_{i}(\hat{m}^{i}-r^{*}m^{i})\left(u_{\nu}^{i}(\bm{\hat{s}}_{\star})-u_{\nu}^{i}(\bm{\sigma})\right)$
is a remainder accounting for collective misalignment and unequal $r^{i}$, and
$K$ and $r^{i}$ are defined as in Proposition 6. Note that when all $r^{i}$
are equal _or_ $\text{CA}=1$ then there is an $r^{*}$ with $R(\bm{\sigma})=0$.

Before continuing, we note that unlike in the single-agent case, even small
irrationalities can compound to dramatically lower individual payoffs (and
thus welfare) in multi-agent settings, as formalised by the following lemma.

######  Lemma 5.

For any $\bm{\epsilon}\succ\bm{0}$, there exists a game $G$ such that
$w_{\bm{0}}=w_{+}$ but for any $x>0$, however small,
$w_{\bm{\epsilon}}-w_{-}<x$.

In many games of interest, however, the welfare of the players will be much
more robust to small mistakes. For example, let us suppose that $G$ is
$(\bm{\epsilon},\Delta)$-robust, in the sense that all
$\bm{\epsilon}\text{-NE}$s are contained within a ball of radius $\Delta$
around a (true) NE [4]. Then it is relatively straightforward to show that:

$w_{\bm{0}}-w_{\bm{\epsilon}}\leq\frac{2\Delta}{n}\sum_{i}\max_{\bm{s},\bm{s^{\prime}}}\lvert
u^{i}(\bm{s})-u^{i}(\bm{s}^{\prime})\rvert.$

Indeed, there are a range of settings in which the price of anarchy can be
bounded under play that is not perfectly rational [36]. While the bound we
provide above is highly general, assuming further structure in the game may
allow us to tighten it further.

Theorem 1 characterises the principals’ welfare regret in terms of three of
our four measures. Our next result characterises the gap between the ideal and
maximal welfare in terms of our fourth measure: collective alignment.

######  Proposition 7.

Given a game $G$ with collective alignment CA, then
$w_{+}-w_{\star}\leq\frac{K\sum_{i}m^{i}}{n}(1-\text{CA})$, where $K$ is
defined as in Proposition 6.

This bound can be applied to either the agent or principal game; we denote the
collective alignment in the latter as $\hat{\text{CA}}$. While it is possible
characterise the difference between $\hat{\text{CA}}$ and CA in terms of IA, a
tighter bound on $\hat{w}_{+}-\hat{w}(\bm{\sigma})$ can be obtained by
considering the collective alignment between the principals and simply summing
the right-hand terms of the inequalities in Theorem 1 and Proposition 7.

The preceding results show that individual/collective alignment/capabilities
are both necessary _and_ sufficient for good outcomes in multi-agent settings.
Concretely, the necessity of CA/CC is shown in Lemmas 2 and 4. The necessity
of IC follows from the fact that $\bm{\epsilon}\text{-NE}(G)=\Sigma$ when
$\bm{\epsilon}=\bm{1}$ (which could lead to arbitrarily poor principal
welfare) and of IA, from the fact that one can construct $G$ from $\hat{G}$
with $\hat{u}=-u$ (so the best outcomes for the agents are the worst outcomes
for the principals). The sufficiency of the four measures is shown in
Propositions 3 and 4 (and more generally in Theorem 1 and Proposition 7).

##  6 Experiments

While our primary contributions in this work are theoretical, we support these
results by: i) empirically validating the bounds above; and ii) showing how
the various measures we introduce can be inferred from data.888Our code is
available at https://github.com/lrhammond/delegation-games. In our experiments
we define $\nu$ using $c(u)=\mathbb{E}_{\bm{s}}[u(\bm{s})]$ and $m(u)=\lVert
u\rVert_{2}$. We also limit our attention to pure strategies, due to the
absence of scalable methods for exhaustively finding mixed
$\bm{\epsilon}\text{-NE}$s in large games.

###  6.1 Empirical Validation

In order to visualise the results in the preceding section, we conduct a
series of experiments in which we monitor how the principals’ welfare changes
based on the degree of control and cooperation in the delegation game. An
example is shown in Figure 3, in which we change one measure, setting all
others to 0.9. At each step we generate 25 random delegation games (with
approximately ten outcomes), compute the set of strategies $\bm{s}$ such that
$w(\bm{s})\in\big{[}w_{\bm{\epsilon}}+\text{CC}\cdot(w_{\star}-w_{\bm{0}}),w_{\bm{\epsilon}}+(w_{\star}-w_{\bm{0}})\big{]}$
where $\bm{\epsilon}=\bm{1}-\text{IC}$, and record the mean principal welfare
over these strategies.

Figure 3: We report mean principal welfare (in red) normalised to
$[\hat{w}_{-},\hat{w}_{+}]$, with $\hat{w}_{\bullet}$ and $\hat{w}_{\star}$ in
green. The lower bounds on welfare, given by Theorem 1, and on
$\hat{w}_{\star}$ (compared to $\hat{w}_{+}$), given by Proposition 7, are in
orange and blue, respectively. Shaded areas show 90% confidence intervals.

As expected, we see a positive relationship for each measure. Given the ease
of coordinating in relatively small games, alignment is more important in this
example than capabilities, as can be seen from the gentler slope of the
welfare curve as IA increases, and in how $\hat{\text{CA}}$ places an upper
limit on principal welfare under otherwise ideal conditions.

In Appendix C.1 we include further details and plots for games ranging between
$10^{1}$ and $10^{3}$ outcomes, with values of the fixed measures ranging
between $0$ to $1$. We find that the overall dependence of principal welfare
upon each measure is robust, though the tightness of the bounds is reduced in
larger games and for lower values of the fixed measures.

###  6.2 Inference of Measures

In the previous sections, we implicitly assumed full knowledge of the
delegation game in order to define our four measures. In the real world, this
assumption will rarely be valid, motivating the question of when and how we
might _infer_ the values of these measures given limited observations. More
concretely, we assume access to a dataset $\mathcal{D}$ containing (pure)
strategy profiles and payoff vectors
$(\bm{s},\bm{u},\bm{\hat{u}})\sim_{\text{i.i.d.}}d$.

Inferring alignment is relatively straightforward, as we can simply
approximate each $u^{i}$ and $\hat{u}^{i}$ by using only the strategies
$\mathcal{D}(\bm{S})\subseteq\bm{S}$ contained in $\mathcal{D}$, for which we
know their values. Inferring capabilities is much more challenging, as they
determine how agents play the game and therefore limit our observations.
Fundamentally, measuring capabilities requires comparing the achieved outcomes
against better/worse alternatives, but if agents’ capabilities are fixed we
might never observe these other outcomes. Moreover, only observing the agents
acting together (alone) leaves us unable to asses how well they would perform
alone (together), due to the orthogonality of individual and collective
capabilities.

While there are many relaxations that might overcome these issues, perhaps the
simplest and weakest is to assume that: a) all utilities are _non-negative_ ;
and b) we receive observations of the agents acting both alone _and_ together.
We can then estimate (upper bounds of) IC and CC as follows.

######  Proposition 8.

Given a game $G$, if $u^{i}(\bm{s})$ for every $i$ and $\bm{s}\in S$, and $d$
has maximal support over the outcomes generated when agents act together/alone
(respectively), then:

CC
$\displaystyle\leq\lim_{\lvert\mathcal{D}\rvert\to\infty}\frac{\min_{\bm{s}\in\mathcal{D}(\bm{S})}w(\bm{s})}{\max_{\bm{s}\in\mathcal{D}(\bm{S})}w(\bm{s})},\text{
and }$ $\displaystyle\text{IC}^{i}$
$\displaystyle\leq\lim_{\lvert\mathcal{D}\rvert\to\infty}\min_{\bm{s}\in\mathcal{D}(\bm{S})}\frac{u^{i}(\bm{s})}{\max_{\tilde{s}^{i}\in\mathcal{D}(S^{i})}u^{i}(\bm{s}^{-i},\tilde{s}^{i})}.$

In Figure 4 we evaluate the accuracy of these estimates using samples
generated from 100 randomly generated delegation games of various sizes.
Consistent with our previous arguments, it is far easier to infer alignment
than capabilities in the setup we consider, though we leave open the question
of whether stronger assumptions and/or different setups might allow us to gain
improved estimates of the latter.

Figure 4: We report the mean absolute error of estimates of the four measures.
The red, orange, blue, and green lines represent games with $10^{k}$ outcomes
for $k\in\\{1,2,3,4\\}$, respectively. Shaded areas show 90% confidence
intervals.

##  7 Conclusion

In this work we formalised and studied problems of _cooperation_ and _control_
in delegation games – a general model for interactions between multiple AI
systems on behalf of multiple humans – breaking them down into issues of
_alignment_ and _capabilities_. We showed how these concepts are both
necessary _and_ sufficient for obtaining good outcomes as well as how they can
be inferred from data.

We focused on strategic-form games to make our theoretical contributions
clearer and more general (as other game models can typically be reduced to
strategic-form). A natural next step, however, would be to develop more
specific results in more complex, structured models, such as Markov games,
which could form the basis for applications to multi-agent reinforcement
learning. Other important extensions include games where: a) the
correspondence between principals and agents is not one-to-one; and b) the
principals can also take actions. Finally, if the concepts in this work are to
more directly help us build safe and beneficial AI systems, we must develop
better methods for inferring them from data.

## Acknowledgements

The authors wish to thank Bart Jaworksi for contributing to an earlier version
of this work, several anonymous reviewers for their comments, and Jesse
Clifton, Joar Skalse, Sam Barnett, Vincent Conitzer, Charlie Griffin, David
Hyland, Michael Wooldridge, Ted Turocy, and Alessandro Abate for insightful
discussions on these topics. Lewis Hammond acknowledges the support of an
EPSRC Doctoral Training Partnership studentship (Reference: 2218880). Oliver
Sourbut acknowledges the University of Oxford’s Autonomous Intelligent
Machines and Systems CDT and the Good Ventures Foundation for their support.

## References

  * [1] Jorge Alcalde-Unzu and Marc Vorsatz  “Do we agree? Measuring the cohesiveness of preferences”  In _Theory and Decision_ 80.2 Springer ScienceBusiness Media LLC, 2015, pp. 313–339  DOI: 10.1007/s11238-015-9494-z
  * [2] Stuart Armstrong and Sören Mindermann  “Occam’s Razor Is Insufficient to Infer the Preferences of Irrational Agents”  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , NIPS’18  Montréal, Canada: Curran Associates Inc., 2018, pp. 5603–5614
  * [3] K.. Arrow, E.. Barankin and D. Blackwell  “5. Admissible Points of Convex Sets”  In _Contributions to the Theory of Games (AM-28), Volume II_ Princeton University Press, 1953, pp. 87–92  DOI: 10.1515/9781400881970-006
  * [4] Pranjal Awasthi, Maria-Florina Balcan, Avrim Blum, Or Sheffet and Santosh Vempala  “On Nash-Equilibria of Approximation-Stable Games”  In _Algorithmic Game Theory_ Springer Berlin Heidelberg, 2010, pp. 78–89  DOI: 10.1007/978-3-642-16170-4˙8
  * [5] Kerry Back  “Concepts of similarity for utility functions”  In _Journal of Mathematical Economics_ 15.2 Elsevier BV, 1986, pp. 129–142  DOI: 10.1016/0304-4068(86)90004-2
  * [6] B. Bernheim  “Rationalizable Strategic Behavior”  In _Econometrica_ 52.4 JSTOR, 1984, pp. 1007  DOI: 10.2307/1911196
  * [7] Nick Bostrom  “Superintelligence: Paths, Dangers, Strategies”  Oxford University Press, 2014  URL: https://www.ebook.de/de/product/21968826/nick_bostrom_superintelligence.html
  * [8] Yeon-Koo Che, Jinwoo Kim, Fuhito Kojima and Christopher Thomas Ryan  “”Near” Weighted Utilitarian Characterizations of Pareto Optima”  In _arXiv:2008.10819_ , 2020  arXiv:2008.10819 [econ.TH]
  * [9] Paul Christiano  “Clarifying “AI alignment””, AI Alignment, 2018  URL: https://ai-alignment.com/clarifying-ai-alignment-cec47cd69dd6
  * [10] Karl Cobbe, Oleg Klimov, Christopher Hesse, Taehoon Kim and John Schulman  “Quantifying Generalization in Reinforcement Learning”  In _Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA_ 97, Proceedings of Machine Learning Research  PMLR, 2019, pp. 1282–1289  URL: http://proceedings.mlr.press/v97/cobbe19a.html
  * [11] Wolfram Conen and Tuomas Sandholm  “Preference elicitation in combinatorial auctions”  In _Proceedings of the 3rd ACM conference on Electronic Commerce_ ACM, 2001  DOI: 10.1145/501158.501191
  * [12] Cyrus Cousins, Bhaskar Mishra, Enrique Areyan Viqueira and Amy Greenwald  “Learning Properties in Simulation-Based Games”  In _Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems_ , AAMAS ’23  London, United Kingdom: International Foundation for Autonomous AgentsMultiagent Systems, 2023, pp. 272–280
  * [13] Allan Dafoe, Edward Hughes, Yoram Bachrach, Tantum Collins, Kevin R. McKee, Joel Z. Leibo, Kate Larson and Thore Graepel  “Open Problems in Cooperative AI”  In _arXiv:2012.08630_ , 2020  arXiv:2012.08630 [cs.AI]
  * [14] Aris Daniilidis  “Arrow-Barankin-Blackwell Theorems and Related Results in Cone Duality: A Survey”  In _Lecture Notes in Economics and Mathematical Systems_ Springer Berlin Heidelberg, 2000, pp. 119–131  DOI: 10.1007/978-3-642-57014-8˙9
  * [15] J.. Doran, S. Franklin, N.. Jennings and T.. Norman  “On cooperation in multi-agent systems”  In _The Knowledge Engineering Review_ 12.3 Cambridge University Press (CUP), 1997, pp. 309–314  DOI: 10.1017/s0269888997003111
  * [16] Yali Du, Joel Z. Leibo, Usman Islam, Richard Willis and Peter Sunehag  “A Review of Cooperation in Multi-Agent Learning”  In _arXiv:2312.05162_ arXiv, 2023  DOI: 10.48550/ARXIV.2312.05162
  * [17] “Elicitation of Preferences”  Springer Netherlands, 2000  DOI: 10.1007/978-94-017-1406-8
  * [18] “Preference Learning”  Springer Berlin Heidelberg, 2011  DOI: 10.1007/978-3-642-14125-6
  * [19] Ya’akov Gal, Avi Pfeffer, Francesca Marzo and Barbara J. Grosz  “Learning Social Preferences in Games”  In _Proceedings of the 19th National Conference on Artifical Intelligence_ , AAAI’04  San Jose, California: AAAI Press, 2004, pp. 226–231
  * [20] Adam Gleave, Michael Dennis, Shane Legg, Stuart Russell and Jan Leike  “Quantifying Differences in Reward Functions”  In _9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021_ OpenReview.net, 2021  URL: https://openreview.net/forum?id=LwEQnp6CYev
  * [21] Faruk Gul and Wolfgang Pesendorfer  “Temptation and Self-Control”  In _Econometrica_ 69.6 The Econometric Society, 2001, pp. 1403–1435  DOI: 10.1111/1468-0262.00252
  * [22] Evan Hubinger  “Clarifying inner alignment terminology”, Alignment Forum, 2020  URL: https://www.alignmentforum.org/posts/SzecSPYxqRa5GCaSF/clarifying-inner-alignment-terminology
  * [23] Javier Insa-Cabrera, José-Luis Benacloch-Ayuso and José Hernández-Orallo  “On Measuring Social Intelligence: Experiments on Competition and Cooperation”  In _Artificial General Intelligence_ Springer Berlin Heidelberg, 2012, pp. 126–135  DOI: 10.1007/978-3-642-35506-6˙14
  * [24] Adam Kalai and Ehud Kalai  “Cooperation in Strategic Games Revisited”  In _The Quarterly Journal of Economics_ 128.2 Oxford University Press (OUP), 2013, pp. 917–966  DOI: 10.1093/qje/qjs074
  * [25] Zachary Kenton, Tom Everitt, Laura Weidinger, Iason Gabriel, Vladimir Mikulik and Geoffrey Irving  “Alignment of Language Agents”  In _arXiv:2103.14659_ , 2021  arXiv:2103.14659 [cs.AI]
  * [26] Elias Koutsoupias and Christos Papadimitriou  “Worst-Case Equilibria”  In _STACS 99_ Springer Berlin Heidelberg, 1999, pp. 404–413  DOI: 10.1007/3-540-49116-3˙38
  * [27] Volodymyr Kuleshov and Okke Schrijvers  “Inverse Game Theory: Learning Utilities In succinct Games”  In _Web and Internet Economics_ Springer Berlin Heidelberg, 2015, pp. 413–427  DOI: 10.1007/978-3-662-48995-6˙30
  * [28] Jean-Jacques Laffont and David Martimort  “The Theory of Incentives”  Princeton University Press, 2002  DOI: 10.1515/9781400829453
  * [29] Shane Legg and Marcus Hutter  “Universal Intelligence: A Definition of Machine Intelligence”  In _Minds and Machines_ 17.4 Island Press, 2007, pp. 391–444  DOI: 10.1007/s11023-007-9079-x
  * [30] Joel Z. Leibo, Edgar A. Duéñez-Guzmán, Alexander Vezhnevets, John P. Agapiou, Peter Sunehag, Raphael Koster, Jayd Matyas, Charlie Beattie, Igor Mordatch and Thore Graepel  “Scalable Evaluation of Multi-Agent Reinforcement Learning with Melting Pot”  In _Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event_ 139, Proceedings of Machine Learning Research  PMLR, 2021, pp. 6187–6199  URL: http://proceedings.mlr.press/v139/leibo21a.html
  * [31] Andreu Mas-Colell, Michael D. Whinston and Jerry R. Green  “Microeconomic Theory”  Oxford University Press, 1995
  * [32] David G. Pearce  “Rationalizable Strategic Behavior and the Problem of Perfection”  In _Econometrica_ 52.4 JSTOR, 1984, pp. 1029  DOI: 10.2307/1911197
  * [33] Michael Peters  “Competing mechanisms”  In _Canadian Journal of Economics/Revue canadienne d’économique_ 47.2 Wiley, 2014, pp. 373–397  DOI: 10.1111/caje.12090
  * [34] Anatol Rapoport and Albert M. Chammah  “The Game of Chicken”  In _American Behavioral Scientist_ 10.3 SAGE Publications, 1966, pp. 10–28  DOI: 10.1177/000276426601000303
  * [35] Yara Rizk, Mariette Awad and Edward W. Tunstel  “Cooperative Heterogeneous Multi-Robot Systems: A Survey”  In _ACM Computing Surveys_ 52.2 Association for Computing Machinery (ACM), 2019, pp. 1–31  DOI: 10.1145/3303848
  * [36] Tim Roughgarden  “Intrinsic Robustness of the Price of Anarchy”  In _Journal of the ACM_ 62.5 Association for Computing Machinery (ACM), 2015, pp. 1–42  DOI: 10.1145/2806883
  * [37] Stuart Russell  “Human Compatible”  Penguin LCC US, 2019  URL: https://www.ebook.de/de/product/35445097/stuart_russell_human_compatible.html
  * [38] Metin Sengul, Javier Gimeno and Jay Dial  “Strategic Delegation: A Review, Theoretical Integration, and Research Agenda”  In _Journal of Management_ 38.1 SAGE Publications, 2011, pp. 375–414  DOI: 10.1177/0149206311424317
  * [39] H.. Simon  “Rational choice and the structure of the environment”  In _Psychological Review_ 63.2 American Psychological Association (APA), 1956, pp. 129–138  DOI: 10.1037/h0042769
  * [40] Joar Skalse, Lucy Farnik, Sumeet Ramesh Motwani, Erik Jenner, Adam Gleave and Alessandro Abate  “STARC: A General Framework For Quantifying Differences Between Reward Functions”  In _arXiv:2309.15257_ arXiv, 2023  DOI: 10.48550/ARXIV.2309.15257
  * [41] Jessica Taylor  “Quantilizers: A Safer Alternative to Maximizers for Limited Optimization”  In _Proceedings of the 2016 AAAI/ACM Conference on AI, Ethics, and Society_ , 2016
  * [42] Jessica Taylor, Eliezer Yudkowsky, Patrick LaVictoire and Andrew Critch  “Alignment for Advanced Machine Learning Systems”  In _Ethics of Artificial Intelligence_ Oxford University Press, 2020, pp. 342–382  DOI: 10.1093/oso/9780190905033.003.0013
  * [43] Emanuel Tewolde  “Game Transformations that preserve Nash Equilibrium sets and/or Best Response sets”  In _arXiv:2111.00076_ , 2021  arXiv:2111.00076 [cs.GT]
  * [44] Alejandro Torreño, Eva Onaindia, Antonín Komenda and Michal Štolba  “Cooperative Multi-Agent Planning: A Survey”  In _ACM Computing Surveys_ 50.6 Association for Computing Machinery (ACM), 2017, pp. 1–32  DOI: 10.1145/3128584
  * [45] Raimo Tuomela  “Cooperation”  Springer Netherlands, 2000  DOI: 10.1007/978-94-015-9594-0
  * [46] John Vickers  “Delegation and the Theory of the Firm”  In _The Economic Journal_ 95 Oxford University Press (OUP), 1985, pp. 138  DOI: 10.2307/2232877
  * [47] John von Neumann and Oskar Morgenstern  “Theory of Games and Economic Behavior”  Princeton University Press, 1944
  * [48] William E. Walsh, Rajarshi Das, Gerald Tesauro and Jeffrey O. Kephar  “Analyzing Complex Strategic Interactions in Multi-Agent Systems”  In _Game Theoretic and Decision Theoretic Agents Workshop at AAAI_ , 2002
  * [49] Kevin Waugh, Brian D. Ziebart and J. Bagnell  “Computational Rationalization: The Inverse Equilibrium Problem”  In _Proceedings of the 28th International Conference on International Conference on Machine Learning_ , ICML’11  Bellevue, Washington, USA: Omnipress, 2011, pp. 1169–1176
  * [50] Michael P. Wellman  “Methods for Empirical Game-Theoretic Analysis”  In _Proceedings of the Twenty-First AAAI Conference on Artificial Intelligence_ , AAAI’06  Boston, Massachusetts: AAAI Press, 2006, pp. 1552–1555
  * [51] S.. West, A.. Griffin and A. Gardner  “Social semantics: altruism, cooperation, mutualism, strong reciprocity and group selection”  In _Journal of Evolutionary Biology_ 20.2 Wiley, 2007, pp. 415–432  DOI: 10.1111/j.1420-9101.2006.01258.x
  * [52] Anita Williams Woolley, Christopher F. Chabris, Alex Pentland, Nada Hashmi and Thomas W. Malone  “Evidence for a Collective Intelligence Factor in the Performance of Human Groups”  In _Science_ 330.6004 American Association for the Advancement of Science (AAAS), 2010, pp. 686–688  DOI: 10.1126/science.1193147
  * [53] Menahem E Yaari  “Rawls, edgeworth, shapley, nash: Theories of distributive justice re-examined”  In _Journal of Economic Theory_ 24.1 Elsevier BV, 1981, pp. 1–39  DOI: 10.1016/0022-0531(81)90062-4
  * [54] Takuro Yamashita  “Mechanism Games with Multiple Principals and Three or More Agents”  In _Econometrica_ 78.2 The Econometric Society, 2010, pp. 791–801  DOI: 10.3982/ecta7005
  * [55] Lantao Yu, Jiaming Song and Stefano Ermon  “Multi-Agent Adversarial Inverse Reinforcement Learning”  In _Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA_ 97, Proceedings of Machine Learning Research  PMLR, 2019, pp. 7194–7201  URL: http://proceedings.mlr.press/v97/yu19e.html

##  Appendix A Notation

See the opening paragraph of Section 2 for a summary of the notational
principles employed in this paper. Other general mathematical notation (aside
from mere abbreviations) that we repeatedly make use of is as follows.

Term | Meaning | Section
---|---|---
$G$ | Game | 2
$u$ | Utility function | 2
$S$ | Pure strategy space | 2
$s$ | Pure strategy | 2
$\Sigma$ | Mixed strategy space | 2
$\sigma$ | Mixed strategy | 2
$D$ | Delegation game | 3
$w$ | Social welfare function | 3
$w_{+}$ | Ideal welfare | 3
$w_{-}$ | Pessimal welfare | 3
$w_{\star}$ | Maximal welfare | 3
$w_{\bullet}$ | Minimal welfare | 3
$\preceq$ | Preference ordering | 4.1.1
$\nu$ | Normalisation function | 4.1.1
$m$ | (Strictly convex) norm | 4.1.1
$c$ | (Affine-equivariant) shift function | 4.1.1
$\mu^{w}$ | Normalised welfare proxy | 4.2.1
$w_{\bm{\epsilon}}$ | Lowest $\bm{\epsilon}\text{-NE}$ welfare | 4.2.2

##  Appendix B Proofs

We begin by providing proofs for all of the results stated in the main body of
the paper, as well as a small number of auxiliary results.

###  B.1 Desiderata

We begin by proving that the measures introduced in Definitions 7, 9, 10, and
11 satisfy the desiderata introduced in Section 3. The original statements of
the results can be found in 5.1. In the proofs below, we use the following
properties of the norm $m$:

  * •

Positive definiteness: if $m(u)=0$ then $u=\bm{0}$,

  * •

Absolute homogeneity: $m(k\cdot u)=\lvert k\rvert\cdot m(u)$ for all
$k\in\mathbb{R}$ and $u\in U$,

  * •

Strict convexity: $m\big{(}k\cdot u+(1-k)\cdot u^{\prime}\big{)}<k\cdot
m(u)+(1-k)\cdot m(u^{\prime})$ for all $u\neq u^{\prime}\in U$ and all
$k\in(0,1)$.

Note that the second and third properties imply the triangle inequality:
$m(u+u^{\prime})\leq m(u)+m(u^{\prime})$.

######  Proposition 1 (D1).

Consider a delegation game $D$ with measures $\text{IA}(D)$, $\text{IC}(D)$,
$\text{CA}(D)$, and $\text{CC}(D)$. Holding fixed any three of the measures,
then for any value $v\in[0,1]$ (or $\bm{v}\in[0,1]^{n}$ for IA or IC), there
is a game $D^{\prime}$ such that the fourth measure takes value $v$ ($\bm{v}$)
in $D^{\prime}$ and the other measures retain their previous values.

###### Proof.

The case for the capabilities measures IC and CC is straightforward as they
define how the agents _play_ the game, not any particular features of the game
itself. Thus we may let $D^{\prime}=D$ in these cases, and set IC or CC to any
$\bm{v}\in[0,1]^{n}$ or $v\in[0,1]$ respectively.

For the case of IA we leave fixed $\bm{u}$ and vary $\hat{\bm{u}}$. For each
$i$, if $\bm{v}[i]=1$ then we set $\hat{u}^{i}=u^{i}$, and if $\bm{v}[i]=0$
then we set $\hat{u}^{i}=-u^{i}$. Otherwise, assuming $U$ is not one-
dimensional, there are infinitely many choices of vectors $u\in U$ such that
$m(u_{\nu}-u^{i}_{\nu})=2-2\bm{v}[i]$. It suffices to pick any such $u$ and
set $\hat{u}^{i}=u$. For the case of CA we vary both $\bm{u}$ and
$\hat{\bm{u}}$, in order to preserve IA. As before, if $v=1$ then we set each
$u^{i}_{\nu}=u_{\nu}$ for some $u\neq\bm{0}$. We then set each $\hat{u}^{i}$
as above, such that $m(\hat{u}^{i}_{\nu}-u^{i}_{\nu})=2-2\text{IA}^{i}(D)$,
ensuring that $\text{IA}(D)=\text{IA}(D^{\prime})$. Similarly, if $v=0$ then
we set each $u^{i}$ such that $u^{i}\neq\bm{0}$ but $\mu^{w}=\bm{0}$, which
gives:

$\displaystyle\text{CA}(D)$ $\displaystyle\coloneqq
1-\sum_{i}\frac{m^{i}}{\sum_{j}m^{j}}\cdot m(\mu^{w}-u^{i}_{\nu})$
$\displaystyle=1-\sum_{i}\frac{m^{i}}{\sum_{j}m^{j}}\cdot
m(\bm{0}-u^{i}_{\nu})$
$\displaystyle=1-\sum_{i}\frac{m^{i}}{\sum_{j}m^{j}}\cdot 1$
$\displaystyle=1-1$ $\displaystyle=0.$

We then once again adjust each $\hat{u}^{i}$ so that
$m(\hat{u}^{i}_{\nu}-u^{i}_{\nu})=2-2\text{IA}^{i}(D)$, using the argument
from preceding case. Finally, for the general case of $v\in(0,1)$, there are
again an infinite number of choices of each $u^{i}\neq\bm{0}$ such that
$(1-v)\sum_{j}m^{j}=\sum_{i}m^{i}\cdot m(\mu^{w}-u^{i}_{\nu})$. Given such a
setting of $\bm{u}$, we may set $\bm{\hat{u}}$ as in the preceding cases. ∎

######  Proposition 2 (D2).

For any $1\leq i\leq n$, $\text{IA}^{i}=1$ ($\text{IA}^{i}=0$) if and only if
$\preceq^{i}=\hat{\preceq}^{i}$ ($\preceq^{i}=\hat{\succeq}^{i}$). Similarly
$\text{CA}=1$ if and only if $\preceq^{i}=\preceq^{j}$ for every $i,j\in N$.

###### Proof.

We begin with the case of individual alignment by considering the
$i^{\text{th}}$ principal-agent pair, who have utility functions $\hat{u}^{i}$
and $u^{i}$, respectively. Recall that we write $c^{i}\coloneqq c(u^{i})$ and
$m^{i}\coloneqq m(u^{i}-c^{i})$, and analogously for $\hat{u}^{i}$.

Let us assume that $\preceq^{i}=\hat{\preceq}^{i}$. Then, by applying Lemma 1
to the case of $u^{i}$ and $\hat{u}^{i}$ we have that

$\text{IA}^{i}=1-\frac{1}{2}\cdot
m(u_{\nu}-\hat{u}^{i}_{\nu})=1-\frac{1}{2}\cdot m(\bm{0})=1,$

as required. Conversely, if $\text{IA}^{i}=1$ then by the positive
definiteness of $m$ we must have $u^{i}_{\nu}=\hat{u}^{i}_{\nu}$ and hence (by
Lemma 1) that $\preceq^{i}=\hat{\preceq}^{i}$, as required.

Next, we consider the case of maximal misalignment. In this case we have
$\preceq^{i}=\hat{\succeq}^{i}$ and thus (by Lemma 1) that
$u^{i}_{\nu}=-\hat{u}^{i}_{\nu}$. Because
$u^{i}_{\nu}\neq\bm{0}\neq\hat{u}^{i}_{\nu}$ then by the absolute homogeneity
of $m$ and the fact that $m(u^{i}_{\nu})=1$:

$\text{IA}^{i}=1-\frac{1}{2}\cdot
m(u^{i}_{\nu}-\hat{u}^{i}_{\nu})=1-\frac{1}{2}\cdot
m(2u^{i}_{\nu})=1-m(u^{i}_{\nu})=0,$

as required. On the other hand, if $\text{IA}^{i}=0$ then this implies that
$m(u^{i}_{\nu}-\hat{u}^{i}_{\nu})=2$. The triangle inequality implies that
$m(u^{i}_{\nu}-\hat{u}^{i}_{\nu})\leq m(u^{i}_{\nu})+m(-\hat{u}^{i}_{\nu})$.
Because $m$ is strictly convex, this inequality is an equality only when
$u^{i}_{\nu}$ and $-\hat{u}^{i}_{\nu}$ are collinear, i.e.
$u^{i}_{\nu}=-\lambda\hat{u}^{i}_{\nu}$ for some $\lambda$. As
$m(u^{i}_{\nu})=m(-\hat{u}^{i}_{\nu})=1$, this is possible only when
$\lambda=1$, and hence $u^{i}_{\nu}=-\hat{u}^{i}_{\nu}$. Thus, by 1, we have
$\preceq^{i}=\hat{\succeq}^{i}$ as required.

Finally, we consider the case of perfect _collective_ alignment between two or
more agents. First suppose that the agents all have identical preferences
$\preceq$. Then, by Lemma 1, this means that we have $u^{i}_{\nu}=u^{j}_{\nu}$
for all $i,j\in N$.

Letting $u_{\nu}$ denote the common normalised utility, then we have
$u^{i}=m^{i}u_{\nu}+c^{i}$ for each $1\leq i\leq n$. The welfare
representative utility is therefore given by:

$\mu^{w}\coloneqq\frac{\sum_{i}m^{i}u_{\nu}^{i}}{\sum_{i}m^{i}}=\frac{u_{\nu}\sum_{i}m^{i}}{\sum_{i}m^{i}}=u_{\nu}.$

Thus we have that:

CA $\displaystyle\coloneqq 1-\sum_{i}\frac{m^{i}}{\sum_{j}m^{j}}\cdot
m(\mu^{w}-u^{i}_{\nu})$
$\displaystyle=1-\sum_{i}\frac{m^{i}}{\sum_{j}m^{j}}\cdot m(\mu^{w}-u_{\nu})$
$\displaystyle=1-\sum_{i}\frac{m^{i}}{\sum_{j}m^{j}}\cdot m(\bm{0})$
$\displaystyle=1,$

as required. Conversely, if we suppose that $\text{CA}=1$ then we must have
that $m(\mu^{w}-u^{i}_{\nu})=0$ for all $1\leq i\leq n$. By the triangle
inequality we have:

$m(u_{\nu}^{i}-u_{\nu}^{j})\leq
m(u_{\nu}^{i}-\mu^{w})+m(\mu^{w}-u_{\nu}^{j})=0,$

for any $i,j\in N$, and hence that $u_{\nu}^{i}=u_{\nu}^{j}$, by the positive
definiteness of $m$. Thus, again by Lemma 1, we have that all of the agents
have the same preferences, concluding the proof. ∎

######  Proposition 3 (D3).

If $\text{IC}=\bm{1}$ and $\text{CC}=1$ then any strategy $\bm{\sigma}$ the
agents play is such that $w(\bm{\sigma})=w_{\star}$. If $\text{IA}=\bm{1}$
then $\bm{\sigma}$ is Pareto-optimal for the principals. If, furthermore,
$\hat{m}^{i}=r\cdot m^{i}$ for some $r>0$ for all $i$, then
$\hat{w}(\bm{\sigma})=\hat{w}_{\star}$.

###### Proof.

Recall that if $\text{IC}=\bm{1}-\bm{\epsilon}$ and $\text{CC}=\delta$ then
the agents only play strategies $\bm{\sigma}$ such that $w(\bm{\sigma})\geq
w_{\bm{\epsilon}}+\delta\cdot(w_{\star}-w_{\bm{0}})$. If $\text{IC}=\bm{1}$
(and hence $\bm{\epsilon}=\bm{0}$) and $\text{CC}=\delta=1$ then clearly
$w(\bm{\sigma})=w_{\star}$, as required.

Now let us suppose that each agent is maximally aligned with its principal,
i.e. $\text{IA}^{i}=1$ for every $1\leq i\leq n$. By the construction in the
proof of Lemma 1, this implies that $u^{i}=a^{i}\hat{u}^{i}+b^{i}$ where
$a^{i}\coloneqq\frac{m^{i}}{\hat{m}^{i}}$. Assume, for a contradiction, that
$\bm{\sigma}$ is not Pareto-optimal for the principals. Then there exists some
$\bm{\sigma}^{\prime}$ and some $j\in N$ such that
$\hat{u}^{j}(\bm{\sigma}^{\prime})>\hat{u}^{j}(\bm{\sigma})$ and
$\hat{u}^{i}(\bm{\sigma}^{\prime})\geq\hat{u}^{i}(\bm{\sigma})$ for all $1\leq
i\leq n$. But then:

$u^{j}(\bm{\sigma}^{\prime})=a^{j}\hat{u}^{j}(\bm{\sigma}^{\prime})+b^{j}>a^{j}\hat{u}^{j}(\bm{\sigma})+b^{j}=u^{j}(\bm{\sigma}),$

and similarly $u^{i}(\bm{\sigma}^{\prime})\geq u^{i}(\bm{\sigma})$ for all
$1\leq i\leq n$. Thus, we have that
$w(\bm{\sigma}^{\prime})=\frac{1}{n}\sum_{i}u^{i}(\bm{\sigma}^{\prime})>\frac{1}{n}\sum_{i}u^{i}(\bm{\sigma})=w(\bm{\sigma})$,
contradicting the fact that
$w_{\star}\coloneqq\max_{\bm{\sigma}}w(\bm{\sigma})$.

Finally, let us assume that $\hat{m}^{i}=r\cdot m^{i}$ for every $1\leq i\leq
n$. Then $a^{i}=\frac{m^{i}}{\hat{m}^{i}}=\frac{1}{r}$ and so:

$\displaystyle\hat{w}(\bm{\sigma})$
$\displaystyle=\frac{1}{n}\sum_{i}\hat{u}^{i}(\bm{\sigma})$
$\displaystyle=\frac{1}{n}\sum_{i}r\cdot\big{(}u^{i}(\bm{\sigma})-b^{i}\big{)}$
$\displaystyle=\frac{r}{n}\sum_{i}u^{i}(\bm{\sigma})-\frac{r}{n}\sum_{i}b^{i}$
$\displaystyle=rw(\bm{\sigma})-\frac{r}{n}\sum_{i}b^{i}.$

This implies that
$\operatorname*{argmax}_{\bm{\sigma}}\hat{w}(\bm{\sigma})=\operatorname*{argmax}_{\bm{\sigma}}w(\bm{\sigma})$,
and hence that $\hat{w}(\bm{\sigma})=\hat{w}_{\star}$, which concludes the
final part of the proof. ∎

######  Proposition 4 (D4).

If $\text{CA}=1$ then $w_{\star}=w_{+}$.

###### Proof.

Following the proof of Proposition 2, $\text{CA}=1$ implies that
$u^{i}_{\nu}=\mu^{w}$ for every $1\leq i\leq n$, and thus that
$\preceq^{i}=\preceq^{\mu}$, where $\preceq^{\mu}$ denotes the preference
ordering over mixed strategies induced by $\mu^{w}$. By Lemma 3 we have that
$\preceq^{\mu}=\preceq^{w}$, where $\preceq^{w}$ denotes the preference
ordering over mixed strategies induced by $w$, and hence, by transitivity,
that $\preceq^{i}=\preceq^{w}$ for each $1\leq i\leq n$. Thus, we have
$\operatorname*{argmax}_{\bm{s}}w(\bm{s})=\operatorname*{argmax}_{\bm{s}}u^{i}(\bm{s})$
and therefore:

$\max_{\bm{s}}w(\bm{s})=\max_{\bm{s}}\frac{1}{n}\sum_{i}u^{i}(\bm{s})=\frac{1}{n}\sum_{i}\max_{\bm{s}}u^{i}(\bm{s})=w_{+}.$

By Lemma 7, $w_{\star}=\max_{\bm{s}}w(\bm{s})$, and so $w_{\star}=w_{+}$. ∎

######  Proposition 5 (D5).

Given a delegation game $D_{1}$, let $D_{2}$ be such that
$\preceq^{i}_{1}=\preceq^{i}_{2}$ and
$\hat{\preceq}^{i}_{1}=\hat{\preceq}^{i}_{2}$ for each $1\leq i\leq n$. Then
$\text{IA}(D_{1})=\text{IA}(D_{2})$ and $\text{IC}(D_{1})=\text{IC}(D_{2})$.
Moreover, if $D_{2}$ is such that $\preceq^{w}_{1}=\preceq^{w}_{2}$ and the
$u^{i}$ are affine-independent, then $\text{CA}(D_{1})=\text{CA}(D_{2})$ and
$\text{CC}(D_{1})=\text{CC}(D_{2})$ as well.

###### Proof.

First, note that the capability measures are defined extrinsically to the
game, and so do not vary as the game varies. We therefore concern ourselves
with the alignment measures.

In the case of individual alignment, notice that if
$\preceq^{i}_{1}=\preceq^{i}_{2}$ then $\nu(u^{i}_{1})=\nu(u^{i}_{2})$ by
Lemma 1, and similarly for $\hat{u}^{i}_{1}$ and $\hat{u}^{i}_{2}$. Thus we
have that
$m\big{(}\nu(\hat{u}^{i}_{1})-\nu(u^{i}_{1})\big{)}=m\big{(}\nu(\hat{u}^{i}_{2})-\nu(u^{i}_{2})\big{)}$,
and hence $\text{IA}^{i}(D_{1})=\text{IA}^{i}(D_{2})$. Applying the same
argument to each $i$ gives $\text{IA}(D_{1})=\text{IA}(D_{2})$.

For the case of collective alignment, then by Lemma 6 we have $w_{1}=aw_{2}+b$
for some $a\in\mathbb{R}_{>0}$ and $b\in\mathbb{R}$. Because we also have
$\nu(u^{i}_{1})=\nu(u^{i}_{2})$ for all $1\leq i\leq n$, then:

$\displaystyle\mu^{w}_{1}\coloneqq\frac{\sum_{i}u^{i}_{1}-c^{i}_{1}}{\sum_{i}m^{i}_{1}}=\frac{\sum_{i}m^{i}\nu(u^{i}_{1})}{\sum_{i}m^{i}_{1}}=\frac{\sum_{i}m^{i}\nu(u^{i}_{2})}{\sum_{i}m^{i}_{1}}.$

Combining these two statements and rearranging results in:

$\sum_{i}\left(\frac{m^{i}_{1}}{\sum_{j}m^{j}_{1}}-a\frac{m^{i}_{2}}{\sum_{j}m^{j}_{2}}\right)\nu(u^{i}_{1})=b.$

Assuming that the $\nu(u^{i}_{1})$ are not affine-dependent, then we must have
$\frac{m^{i}_{1}}{\sum_{j}m^{j}_{1}}=a\frac{m^{i}_{2}}{\sum_{j}m^{j}_{2}}$ for
each $1\leq i\leq n$. Thus, we have $\mu^{w}_{1}=\mu^{w}_{2}$, and therefore:

$\displaystyle\text{CA}(D_{1})$ $\displaystyle\coloneqq
1-\sum_{i}\frac{m^{i}_{1}}{\sum_{j}m^{j}_{1}}\cdot
m\big{(}\mu^{w}_{1}-\nu(u^{i}_{1})\big{)}$
$\displaystyle=1-\sum_{i}\frac{m^{i}_{2}}{\sum_{j}m^{j}_{2}}\cdot
m\big{(}\mu^{w}_{2}-\nu(u^{i}_{2})\big{)}$
$\displaystyle\eqqcolon\text{CA}(D_{2}),$

which concludes the proof. ∎

###  B.2 Bounding Welfare Regret

Next, we provide proofs of the bounds on welfare regret from Section 5.2.

######  Proposition 6.

Given a delegation game $D$, we have:

$\hat{w}_{\star}-\hat{w}(\bm{\sigma})\leq\frac{1}{n}\sum_{i}r^{i}\big{(}u^{i}(\hat{\bm{s}}_{\star})-u^{i}(\bm{\sigma})\big{)}+\frac{4K}{n}\hat{\bm{m}}^{\top}(\bm{1}-\text{IA}),$

where $r^{i}\coloneqq\frac{\hat{m}^{i}}{m^{i}}$,
$\hat{\bm{m}}[i]=\hat{m}^{i}$, $K$ satisfies $\lVert
u_{\nu}-u^{\prime}_{\nu}\rVert_{\infty}\leq K\cdot
m(u_{\nu}-u^{\prime}_{\nu})$ for any $u,u^{\prime}\in U$, and
$\hat{w}(\hat{\bm{s}}_{\star})=\hat{w}_{\star}$.

###### Proof.

To begin with, let us consider the principal’s welfare regret from a pure
strategy profile $\bm{s}$. Let $\hat{\bm{s}}_{\star}$ be such that
$\hat{w}(\hat{\bm{s}}_{\star})=\hat{w}_{\star}$, which we know must exist from
Lemma 7. Then we have:

$\displaystyle\hat{w}_{\star}-\hat{w}(\bm{s})$ $\displaystyle=$
$\displaystyle\hat{w}(\hat{\bm{s}}_{\star})-\hat{w}(\bm{s})$ $\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{i}\hat{u}^{i}(\hat{\bm{s}}_{\star})-\frac{1}{n}\sum_{i}\hat{u}^{i}(\bm{s})$
$\displaystyle=$
$\displaystyle\frac{1}{n}\left(\sum_{i}\hat{m}^{i}\hat{u}^{i}_{\nu}(\hat{\bm{s}}_{\star})+\hat{c}^{i}\right)-\frac{1}{n}\left(\sum_{i}\hat{m}^{i}\hat{u}^{i}_{\nu}(\bm{s})+\hat{c}^{i}\right)$
$\displaystyle=$
$\displaystyle\frac{1}{n}\left(\sum_{i}\hat{m}^{i}\hat{u}^{i}_{\nu}(\hat{\bm{s}}_{\star})-\sum_{i}\hat{m}^{i}\hat{u}^{i}_{\nu}(\bm{s})\right).$

Because $m$ is a norm and $U$ is finite-dimensional, then there is some finite
$K$ such that $\lVert u_{\nu}-u^{\prime}_{\nu}\rVert_{\infty}\leq K\cdot
m(u_{\nu}-u^{\prime}_{\nu})$ for any $u,u^{\prime}\in U$. Applying this bound
to each $\hat{u}^{i}_{\nu}$ and $u^{i}_{\nu}$, and writing $d^{i}\coloneqq
m(\hat{u}^{i}_{\nu}-u^{i}_{\nu})$ we have:

$\displaystyle\sum_{i}\hat{m}^{i}\hat{u}^{i}_{\nu}(\hat{\bm{s}}_{\star})-\sum_{i}\hat{m}^{i}\hat{u}^{i}_{\nu}(\bm{s})$
$\displaystyle\leq$
$\displaystyle\sum_{i}\hat{m}^{i}\cdot\left(u^{i}_{\nu}(\hat{\bm{s}}_{\star})+Kd^{i}\right)-\sum_{i}\hat{m}^{i}\cdot\left(u^{i}_{\nu}(\bm{s})-Kd^{i}\right)$
$\displaystyle=$
$\displaystyle\sum_{i}\hat{m}^{i}u^{i}_{\nu}(\hat{\bm{s}}_{\star})-\sum_{i}\hat{m}^{i}u^{i}_{\nu}(\bm{s})+2K\sum_{i}\hat{m}^{i}d^{i}$
$\displaystyle=$
$\displaystyle\sum_{i}\hat{m}^{i}\frac{u^{i}(\hat{\bm{s}}_{\star})-c^{i}}{m^{i}}-\sum_{i}\hat{m}^{i}\frac{u^{i}(\bm{s})-c^{i}}{m^{i}}+2K\sum_{i}\hat{m}^{i}d^{i}$
$\displaystyle=$
$\displaystyle\sum_{i}r^{i}\big{(}u^{i}(\hat{\bm{s}}_{\star})-u^{i}(\bm{s})\big{)}+2K\sum_{i}\hat{m}^{i}d^{i},$

where $r^{i}\coloneqq\frac{\hat{m}^{i}}{m^{i}}$. Finally, note that for any
$\bm{\sigma}$, we have:

$w(\bm{\sigma})\coloneqq\mathbb{E}_{\bm{\sigma}}[w(\bm{s})]=\mathbb{E}_{\bm{\sigma}}\Big{[}\frac{1}{n}\sum_{i}u^{i}(\bm{s})\Big{]}=\frac{1}{n}\sum_{i}\mathbb{E}_{\bm{\sigma}}\big{[}u^{i}(\bm{s})\big{]},$

by the linearity of expectation. Applying this to the bound above,
substituting in $d^{i}=2(1-\text{IA}^{i})$, and writing the final sum over
players in vector notation gives:

$\displaystyle\hat{w}_{\star}-\hat{w}(\bm{\sigma})$
$\displaystyle\leq\frac{1}{n}\left(\sum_{i}r^{i}\big{(}u^{i}(\hat{\bm{s}}_{\star})-u^{i}(\bm{\sigma})\big{)}+2K\sum_{i}\hat{m}^{i}d^{i}\right)$
$\displaystyle=\frac{1}{n}\sum_{i}r^{i}\big{(}u^{i}(\hat{\bm{s}}_{\star})-u^{i}(\bm{\sigma})\big{)}+\frac{4K}{n}\hat{\bm{m}}^{\top}(\bm{1}-\text{IA}),$

where $\hat{\bm{m}}[i]=\hat{m}^{i}$, completing the proof. ∎

######  Theorem 1.

Given a delegation game $D$, we have that:

$\displaystyle\hat{w}_{\star}-\hat{w}(\bm{\sigma})$
$\displaystyle\leq\frac{4K}{n}\hat{\bm{m}}^{\top}(\bm{1}-\text{IA})+r^{*}\left((w_{\bm{0}}-w_{\bm{\epsilon}})\right.$
$\displaystyle+\left.(1-\text{CC})(w_{\star}-w_{\bm{0}})\right)+R(\bm{\sigma}),$

where $\text{IC}=\bm{1}-\bm{\epsilon}$,
$r^{*}\in[\min_{i}r^{i},\max_{i}r^{i}]$,
$R(\bm{\sigma})\coloneqq\frac{1}{n}\sum_{i}(\hat{m}^{i}-r^{*}m^{i})\left(u_{\nu}^{i}(\bm{\hat{s}}_{\star})-u_{\nu}^{i}(\bm{\sigma})\right)$
is a remainder accounting for collective misalignment and unequal $r^{i}$, and
$K$ and $r^{i}$ are defined as in Proposition 6. Note that when all $r^{i}$
are equal _or_ $\text{CA}=1$ then there is an $r^{*}$ with $R(\bm{\sigma})=0$.

###### Proof.

First, observing that by definition $w_{\star}\geq w(\bm{\hat{s}}_{\star})$,
we see that for any $r^{*}>0$:

$\displaystyle\frac{1}{n}\sum_{i}r^{i}\left(u^{i}(\bm{\hat{s}}_{\star})-u^{i}(\bm{\sigma})\right)$
$\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{i}r^{*}\left(u^{i}(\bm{\hat{s}}_{\star})-u^{i}(\bm{\sigma})\right)+\frac{1}{n}\sum_{i}(r^{i}-r^{*})\left(u^{i}(\bm{\hat{s}}_{\star})-u^{i}(\bm{\sigma})\right)$
$\displaystyle=$ $\displaystyle
r^{*}(w(\bm{\hat{s}_{\star}})-w(\bm{\sigma}))+\frac{1}{n}\sum_{i}(\hat{m}^{i}-r^{*}m^{i})\left(u_{\nu}^{i}(\bm{\hat{s}}_{\star})-u_{\nu}^{i}(\bm{\sigma})\right)$
$\displaystyle\leq$ $\displaystyle
r^{*}(w_{\star}-w(\bm{\sigma}))+\frac{1}{n}\sum_{i}(\hat{m}^{i}-r^{*}m^{i})\left(u_{\nu}^{i}(\bm{\hat{s}}_{\star})-u_{\nu}^{i}(\bm{\sigma})\right)$
$\displaystyle=$ $\displaystyle
r^{*}(w_{\star}-w(\bm{\sigma}))+R(\bm{\sigma}),$

where
$R(\bm{\sigma})\coloneqq\frac{1}{n}\sum_{i}(\hat{m}^{i}-r^{*}m^{i})\left(u_{\nu}^{i}(\bm{\hat{s}}_{\star})-u_{\nu}^{i}(\bm{\sigma})\right)$.
This is a weighted combination of the agent welfare regret
$w_{\star}-w(\bm{\sigma})$ with a ‘fairness remainder’ term $R(\bm{\sigma})$.
The remainder can be seen to be intimately related to the different ratios
$r^{i}\coloneqq\frac{\hat{m}^{i}}{m^{i}}$, which determine when Pareto
improvements are considered gains in agent welfare. When all $r^{i}$ are
identical, a choice of $r^{*}=r^{i}$ causes $R(\bm{\sigma})$ to vanish, which
we refer to as the ‘perfectly calibrated’ case. (We discuss several continuous
bounds on this remainder in Appendix B.3.) Now, from Definition 11 we have
$w(\bm{\sigma})\geq w_{\bm{\epsilon}}+\text{CC}\cdot(w_{\star}-w_{\bm{0}})$,
which implies that:

$\displaystyle w_{\star}-w(\bm{\sigma})$ $\displaystyle\leq
w_{\star}-w_{\bm{\epsilon}}-\text{CC}\cdot(w_{\star}-w_{\bm{0}})$
$\displaystyle=(1-\text{CC})\cdot w_{\star}-w_{\bm{\epsilon}}+\text{CC}\cdot
w_{\bm{0}}$ $\displaystyle=(1-\text{CC})\cdot
w_{\star}-w_{\bm{\epsilon}}-(1-\text{CC})\cdot w_{\bm{0}}+w_{\bm{0}}$
$\displaystyle=(1-\text{CC})(w_{\star}-w_{\bm{0}})+(w_{\bm{0}}-w_{\bm{\epsilon}}).$

Substituting this inequality into the previous inequality and then into the
bound from Proposition 6 gives:

$\displaystyle\hat{w}_{\star}-\hat{w}(\bm{\sigma})$
$\displaystyle\leq\frac{4K}{n}\hat{\bm{m}}^{\top}(\bm{1}-\text{IA})+r^{*}\left((w_{\bm{0}}-w_{\bm{\epsilon}})\right.$
$\displaystyle+\left.(1-\text{CC})(w_{\star}-w_{\bm{0}})\right)+R(\bm{\sigma}).$

∎

######  Proposition 7.

Given a game $G$ with collective alignment CA, then
$w_{+}-w_{\star}\leq\frac{K\sum_{i}m^{i}}{n}(1-\text{CA})$, where $K$ is
defined as in Proposition 6.

###### Proof.

To begin, we first choose
$\bm{s}^{i}_{+}\in\operatorname*{argmax}_{\bm{s}}u^{i}(\bm{s})$ for each $i$.
Second, because $m$ is a norm and $U$ is finite-dimensional, then there is
some finite $K$ such that $\lVert u-u^{\prime}\rVert_{\infty}\leq K\cdot
m(u-u^{\prime})$ for any $u,u^{\prime}\in U$. Using these two pieces of
information, we have:

$\displaystyle w_{+}$
$\displaystyle\coloneqq\frac{1}{n}\sum_{i}u^{i}(\bm{s}^{i}_{+})$
$\displaystyle=\frac{1}{n}\sum_{i}\big{(}m^{i}u^{i}_{\nu}(\bm{s}^{i}_{+})+c^{i}\big{)}$
$\displaystyle=\frac{1}{n}\sum_{i}\big{(}m^{i}\mu^{w}(\bm{s}^{i}_{+})+c^{i}\big{)}+\frac{1}{n}\sum_{i}m^{i}\big{(}u^{i}_{\nu}(\bm{s}^{i}_{+})-\mu^{w}(\bm{s}^{i}_{+})\big{)}$
$\displaystyle\leq\frac{1}{n}\sum_{i}\big{(}m^{i}\mu^{w}(\bm{s}^{i}_{+})+c^{i}\big{)}+\frac{1}{n}\sum_{i}m^{i}\lVert
u^{i}_{\nu}-\mu^{w}\rVert_{\infty}$
$\displaystyle\leq\frac{1}{n}\sum_{i}\big{(}m^{i}\mu^{w}(\bm{s}^{i}_{+})+c^{i}\big{)}+\frac{K}{n}\cdot\sum_{i}m^{i}\cdot
m(\mu^{w}-u^{i}_{\nu}).$

Next, let us choose some
$\bm{s}_{\star}\in\operatorname*{argmax}_{\bm{s}}w(\bm{s})$. Then clearly
$w(\bm{s}^{i}_{+})\leq w(\bm{s}_{\star})=w_{\star}$ for any $1\leq i\leq n$,
where the second equality follows from Lemma 7. Hence, by Lemma 3, we also
have $\mu^{w}(\bm{s}^{i}_{+})\leq\mu^{w}(\bm{s}_{\star})$. Using this fact, we
have:

$\displaystyle\frac{1}{n}\sum_{i}\big{(}m^{i}\mu^{w}(\bm{s}^{i}_{+})+c^{i}\big{)}$
$\displaystyle\leq$
$\displaystyle\frac{1}{n}\sum_{i}\big{(}m^{i}\mu^{w}(\bm{s}_{\star})+c^{i}\big{)}$
$\displaystyle=$
$\displaystyle\frac{1}{n}\mu^{w}(\bm{s}_{\star})\sum_{i}m^{i}+\frac{1}{n}\sum_{i}c^{i}$
$\displaystyle=$
$\displaystyle\frac{1}{n}\frac{\sum_{i}\big{(}u^{i}(\bm{s}_{\star})-c^{i}\big{)}}{\sum_{i}m^{i}}\sum_{i}m^{i}+\sum_{i}c^{i}$
$\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{i}\big{(}u^{i}(\bm{s}_{\star})-c^{i}\big{)}+\frac{1}{n}\sum_{i}c^{i}$
$\displaystyle=$ $\displaystyle\frac{1}{n}\sum_{i}u^{i}(\bm{s}_{\star})$
$\displaystyle=$ $\displaystyle w_{\star}.$

Substituting this and using the fact that $\sum_{i}m^{i}\cdot
m(\mu^{w}-u^{i}_{\nu})=(1-\text{CA})\sum_{i}m^{i}$ in to our our previous
inequality we have:

$w_{+}\leq w_{\star}+\frac{K\sum_{i}m^{i}}{n}(1-\text{CA}),$

from which our result follows by subtracting $w_{\star}$. ∎

###  B.3 Auxiliary Results

######  Lemma 1.

For any $u,u^{\prime}\in U$, $u_{\nu}=u^{\prime}_{\nu}$ if and only if
$\preceq=\preceq^{\prime}$.

###### Proof.

First, recall that, by Lemma 6, $\preceq=\preceq^{\prime}$ if and only if
there exist $a\in\mathbb{R}_{>0}$ and $b\in\mathbb{R}$ such that
$u=au^{\prime}+b$. Using the fact that $c$ is affine-equivariant we have:

$\displaystyle u-c$ $\displaystyle=au^{\prime}+b-c(au^{\prime}+b)$
$\displaystyle=au^{\prime}+b-a\cdot c(u^{\prime})-b$
$\displaystyle=a\cdot(u^{\prime}-c^{\prime}).$

Next, by appealing to the absolute homogeneity of $m$ and the fact that $a>0$
we have:

$\displaystyle u_{\nu}$ $\displaystyle=\frac{u-c}{m}$
$\displaystyle=\frac{a\cdot(u^{\prime}-c^{\prime})}{m\big{(}a\cdot(u^{\prime}-c^{\prime})\big{)}}$
$\displaystyle=\frac{a\cdot(u^{\prime}-c^{\prime})}{\lvert a\rvert\cdot
m\big{(}u^{\prime}-c^{\prime}\big{)}}$
$\displaystyle=\frac{u^{\prime}-c^{\prime}}{m^{\prime}}$
$\displaystyle=u^{\prime}_{\nu},$

as required. Conversely, we see that:

$\displaystyle u_{\nu}=u^{\prime}_{\nu}$
$\displaystyle\implies\frac{u-c}{m}=\frac{u^{\prime}-c^{\prime}}{m^{\prime}}$
$\displaystyle\implies u=\left(\frac{m}{m^{\prime}}\right)\cdot
u^{\prime}+\left(c-\frac{m}{m^{\prime}}c^{\prime}\right).$

Letting $a^{\prime}\coloneqq\frac{m}{m^{\prime}}>0$ and $b^{\prime}\coloneqq
c-\frac{m}{m^{\prime}}c^{\prime}$ then we have
$u=a^{\prime}u^{\prime}+b^{\prime}$ and hence $\preceq=\preceq^{\prime}$ (by
Lemma 6), as required. ∎

######  Lemma 2.

There exists a (two-player, two-action) delegation game $D$ such that for any
$x>0$, however small, even if $\text{IA}(D)=\bm{1}$ and $\text{IC}(D)=\bm{1}$,
we have only one NE $\bm{\sigma}$, and
$\frac{\hat{w}_{\star}-\hat{w}(\bm{\sigma})}{\hat{w}_{+}-\hat{w}_{-}}=1-x$.

###### Proof.

Consider the Prisoner’s Dilemma as specified in Figure 6(a), which we take to
be the principal game $\hat{G}$. Note that $\hat{w}_{+}=1$ and
$\hat{w}_{-}=0$. If $\text{IA}(D)=\bm{1}$ then $\hat{\preceq}^{i}=\preceq^{i}$
by Proposition 2, meaning that the NEs of $G$ are the same as those of
$\hat{G}$. Because $\text{IC}(D)=\bm{1}$ then we consider only these NEs,
which in this case is simply $\bm{s}=(B,B)$, giving
$\hat{w}(\bm{s})=\frac{x}{2}$. However,
$\max_{\bm{\sigma}}\hat{w}(\bm{\sigma})=1-\frac{x}{2}$, and thus we have
$\frac{\hat{w}_{\star}-\hat{w}(\bm{\sigma})}{\hat{w}_{+}-\hat{w}_{-}}=1-x$. ∎

| $A$ | $B$ |
---|---|---|---
$A$ | $1-\frac{x}{2},1-\frac{x}{2}$ | $0,1$ |
$B$ | $1,0$ | $\frac{x}{2},\frac{x}{2}$ |
(a)

| $A$ | $B$ | $C$ |
---|---|---|---|---
$A$ | $1,1$ | $x,1-\epsilon^{2}$ | $0,0$ |
$B$ | $1-\epsilon^{1},x$ | $(1-\epsilon^{1})x,(1-\epsilon^{2})x$ | $x,0$ |
$C$ | $0,0$ | $0,x$ | $0,0$ |
(b)

| $A$ | $B$ | $C$ | $\cdots$ | $Z$ |
---|---|---|---|---|---|---
$A$ | $1-x,1-x$ | $1-3x,1$ | $0,0$ | $\cdots$ | $0,0$ |
$B$ | $1,1-3x$ | $1-2x,1-2x$ | $1-4x,1-x$ | $\cdots$ | $0,0$ |
$C$ | $0,0$ | $1-x,1-4x$ | $1-3x,1-3x$ | $\cdots$ | $0,0$ |
$\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\ddots$ | $\vdots$ |
$Z$ | $0,0$ | $0,0$ | $0,0$ | $\cdots$ | $x,x$ |
(c)

Figure 6: (a) A Prisoner’s Dilemma leading to arbitrarily high welfare regret
for the principals, despite perfect control of each agent by its principal;
(b) a game in which the welfare in the worst $\bm{\epsilon}\text{-NE}$ is much
lower than in the worst NE.; and (c) a Traveller’s Dilemma leading to
arbitrarily high welfare regret for the principals, despite perfect control of
each agent by its principal, and near-perfect collective alignment.

######  Lemma 3.

For any $\bm{\sigma},\bm{\sigma}^{\prime}\in\bm{\Sigma}$,
$\mu^{w}(\bm{\sigma})\leq\mu^{w}(\bm{\sigma}^{\prime})$ if and only if
$w(\bm{\sigma})\leq w(\bm{\sigma}^{\prime})$.

###### Proof.

By Definition 10 we have that:

$\displaystyle\mu^{w}$
$\displaystyle\coloneqq\frac{\sum_{i}u^{i}-c^{i}}{\sum_{i}m^{i}}$
$\displaystyle=\frac{1}{\sum_{i}m^{i}}\sum_{i}u^{i}-\frac{\sum_{i}c^{i}}{\sum_{i}m^{i}}$
$\displaystyle=\frac{n}{\sum_{i}m^{i}}w-\frac{\sum_{i}c^{i}}{\sum_{i}m^{i}}.$

The result follows by the linearity of expectation, taken with respect to
$\bm{s}$. Indeed, setting $a\coloneqq\frac{n}{\sum_{i}m^{i}}$ and
$b=-\frac{\sum_{i}c^{i}}{\sum_{i}m^{i}}$ then by Lemma 6 we have that
$\preceq^{\mu}=\preceq^{w}$, where $\preceq^{\mu}$ and $\preceq^{w}$ denote
the preference ordering over mixed strategies induced by $\mu^{w}$ and $w$
respectively. ∎

######  Lemma 4.

There exists a family of (two-player, $k$-action) delegation games $D$ such
that even if $\text{IA}^{i}(D)=1$, $\text{IC}^{i}(D)=1$ for each agent, and
there is only one NE $\bm{\sigma}$, we have $\lim_{k\to\infty}\text{CA}(D)=1$
but
$\lim_{k\to\infty}\frac{\hat{w}_{\star}-\hat{w}(\bm{\sigma})}{\hat{w}_{+}-\hat{w}_{-}}=1$.

###### Proof.

Consider the Traveller’s Dilemma as specified in Figure 6(c), which we take to
be the principal game $\hat{G}$. As argued in the proof of Lemma 2, the fact
that $\text{IA}(D)=\bm{1}$ means that $\text{NE}(G)=\text{NE}(\hat{G})$, and
because $\text{IC}(D)=\bm{1}$ then we need only consider the NEs of $G$, which
in this case is simply $\bm{s}=(E,E)$, and (as in the case of Lemma 2) leads
to a welfare regret of $1-2x$. If the game has $k$ actions for each player,
and we assume that the payoffs for each agent are normalised such that
$\hat{w}_{+}=1$ and $\hat{w}_{-}=0$ then we have $x=\frac{1}{k+1}$. Thus, we
have:

$\lim_{k\to\infty}\frac{\hat{w}_{\star}-\hat{w}(\bm{\sigma})}{\hat{w}_{+}-\hat{w}_{-}}=\lim_{k\to\infty}\frac{1-\frac{1}{k+1}}{1-0}=1.$

Now we consider the second limit. First note that $\lVert
u^{1}-u^{2}\rVert_{\infty}=3x$ and, as $c$ is affine-equivariant, then $\lVert
c^{1}-c^{2}\rVert_{\infty}=3x$ too. Because $m$ is a norm and $U$ is finite-
dimensional, then there is some finite $L$ such that $m(u-u^{\prime})\leq
L\cdot\lVert u-u^{\prime}\rVert_{\infty}$ for any $u,u^{\prime}\in U$, and
therefore:

$\displaystyle m^{1}-m^{2}$ $\displaystyle=m(u^{1}-c^{1})-m(u^{2}-c^{2})$
$\displaystyle\leq m\big{(}(u^{1}-c^{1})-(u^{2}-c^{2})\big{)}$
$\displaystyle\leq L\cdot\lVert(u^{1}-c^{1})-(u^{2}-c^{2})\rVert_{\infty}$
$\displaystyle\leq L\cdot\lVert u^{1}-u^{2}\rVert_{\infty}+L\cdot\lVert
c^{1}-c^{2}\rVert_{\infty}$ $\displaystyle=6Lx.$

Hence, let use denote
$u\coloneqq\lim_{k\to\infty}u^{1}=\lim_{k\to\infty}u^{2}$ and similarly for
$m$ and $c$. Then, assuming that $m\neq 0$ (otherwise the proof is complete),
we compose limits to see that:

$\lim_{k\to\infty}u^{1}_{\nu}=\lim_{k\to\infty}\frac{u^{1}-c^{1}}{m^{1}}=\frac{u-c}{m}=\lim_{k\to\infty}\frac{u^{2}-c^{2}}{m^{2}}=\lim_{k\to\infty}u^{2}_{\nu}.$

To conclude the proof, observe that by Lemma 1 we have
$\lim_{k\to\infty}\preceq^{1}=\lim_{k\to\infty}\preceq^{2}$ and hence (by
Proposition 2) that $\lim_{k\to\infty}\text{CA}=1$. ∎

######  Lemma 5.

For any $\bm{\epsilon}\succ\bm{0}$, there exists a game $G$ such that
$w_{\bm{0}}=w_{+}$ but for any $x>0$, however small,
$w_{\bm{\epsilon}}-w_{-}<x$.

###### Proof.

Consider the game specified in Figure 6(b). Observe that the only NE is given
by $(A,A)$, leading to welfare $w_{\bm{0}}=w_{+}=1$. In contrast, note that
$(B,B)$ is an $\bm{\epsilon}\text{-NE}$, as neither player can deviate to
obtain a greater fraction than $(1-\epsilon^{i})$ of the utility available
when playing their best response ($x$). Given this, we have:

$w_{\bm{\epsilon}}-w_{-}<\left(1-\frac{\epsilon^{1}+\epsilon^{2}}{2}\right)x-0<x.$

∎

######  Proposition 8.

Given a game $G$, if $u^{i}(\bm{s})$ for every $i$ and $\bm{s}\in S$, and $d$
has maximal support over the outcomes generated when agents act together/alone
(respectively), then:

CC
$\displaystyle\leq\lim_{\lvert\mathcal{D}\rvert\to\infty}\frac{\min_{\bm{s}\in\mathcal{D}(\bm{S})}w(\bm{s})}{\max_{\bm{s}\in\mathcal{D}(\bm{S})}w(\bm{s})},\text{
and }$ $\displaystyle\text{IC}^{i}$
$\displaystyle\leq\lim_{\lvert\mathcal{D}\rvert\to\infty}\min_{\bm{s}\in\mathcal{D}(\bm{S})}\frac{u^{i}(\bm{s})}{\max_{\tilde{s}^{i}\in\mathcal{D}(S^{i})}u^{i}(\bm{s}^{-i},\tilde{s}^{i})}.$

###### Proof.

Let us begin by considering the case in which the agents are observed acting
together. Given their cooperative capabilities CC we observe outcomes $\bm{s}$
such that:

$w_{\bm{\epsilon}}+\text{CC}\cdot(w_{\star}-w_{\bm{0}})\leq w(\bm{s})\leq
w_{\bm{\epsilon}}+(w_{\star}-w_{\bm{0}}).$

If $d$ has maximal support over the set of such outcomes, then we have:

$\displaystyle\lim_{\lvert\mathcal{D}\rvert\to\infty}\max_{\bm{s}\in\mathcal{D}(\bm{S})}w(\bm{s})=w_{\bm{\epsilon}}+(w_{\star}-w_{\bm{0}}),$
$\displaystyle\lim_{\lvert\mathcal{D}\rvert\to\infty}\min_{\bm{s}\in\mathcal{D}(\bm{S})}w(\bm{s})=w_{\bm{\epsilon}}+\text{CC}\cdot(w_{\star}-w_{\bm{0}}).$

If
$\lim_{\lvert\mathcal{D}\rvert\to\infty}\max_{\bm{s}\in\mathcal{D}(\bm{S})}w(\bm{s})=0$,
then we must have $u^{i}(\bm{s})=0$ for every $1\leq i\leq n$ and $\bm{s}\in
S$, in which case it is meaningless to talk about the agents’ cooperative
capabilities, so let us assume otherwise. Subtracting $w_{\bm{\epsilon}}$
(which, by assumption, is non-negative), cancelling the terms
$(w_{\star}-w_{\bm{0}})$ in these equalities, and composing limits leads to:

$\text{CC}\leq\lim_{\lvert\mathcal{D}\rvert\to\infty}\frac{\min_{\bm{s}\in\mathcal{D}(\bm{S})}w(\bm{s})}{\max_{\bm{s}\in\mathcal{D}(\bm{S})}w(\bm{s})}.$

Similarly, in the case where each agent is observed acting alone, then given
their individual capabilities $\text{IC}^{i}$ we observe outcomes $\bm{s}$
such that:

$u^{i}_{\bullet}(\bm{s}^{-i})+\text{IC}^{i}\cdot\big{(}u^{i}_{\star}(\bm{s}^{-i})-u^{i}_{\bullet}(\bm{s}^{-i})\big{)}\leq
u^{i}(\bm{s})\leq u^{i}_{\star}(\bm{s}^{-i}),$

where we define:

$\displaystyle u^{i}_{\bullet}(\bm{s}^{-i})$
$\displaystyle\coloneqq\min_{\tilde{s}^{i}}u^{i}(\bm{s}^{-i},\tilde{s}^{i}),$
$\displaystyle u^{i}_{\star}(\bm{s}^{-i})$
$\displaystyle\coloneqq\max_{\tilde{s}^{i}}u^{i}(\bm{s}^{-i},\tilde{s}^{i}).$

If $d$ has maximal support over the set of such outcomes, including over _all_
pure partial strategy profiles $\bm{s}^{-i}$, then we have:

$\displaystyle\text{IC}^{i}$
$\displaystyle\leq\lim_{\lvert\mathcal{D}\rvert\to\infty}\min_{\bm{s}\in\mathcal{D}(\bm{S})}\frac{u^{i}(\bm{s})-u^{i}_{\bullet}(\bm{s}^{-i})}{u^{i}_{\star}(\bm{s}^{-i})-u^{i}_{\bullet}(\bm{s}^{-i})}$
$\displaystyle\leq\lim_{\lvert\mathcal{D}\rvert\to\infty}\min_{\bm{s}\in\mathcal{D}(\bm{S})}\frac{u^{i}(\bm{s})}{u^{i}_{\star}(\bm{s}^{-i})}$
$\displaystyle=\lim_{\lvert\mathcal{D}\rvert\to\infty}\min_{\bm{s}\in\mathcal{D}(\bm{S})}\frac{u^{i}(\bm{s})}{\max_{\tilde{s}^{i}\in\mathcal{D}(S^{i})}u^{i}(\bm{s}^{-i},\tilde{s}^{i})},$

which concludes the proof. ∎

######  Lemma 6.

Assuming that a game $G$ has at least three outcomes, then for utility
functions $u$ and $u^{\prime}$ with corresponding preference orderings
$\preceq$ and $\preceq^{\prime}$ respectively, $\preceq=\preceq^{\prime}$ if
and only if there exist $a\in\mathbb{R}_{>0}$ and $b\in\mathbb{R}$ such that
$u=au^{\prime}+b$. Similarly, $\preceq=\succeq^{\prime}$ if and only if there
exist $a\in\mathbb{R}_{>0}$ and $b\in\mathbb{R}$ such that $u=-au^{\prime}+b$.

###### Proof.

See, e.g. Proposition 6.B.2 in [31], for a proof of the first half of this
lemma. The second half can be proved analogously. ∎

######  Lemma 7.

Given a game $G$, there is a pure strategy $\bm{s}_{\star}$ such that
$w_{\star}(G)=w(\bm{s}_{\star})$.

###### Proof.

Recall that $w_{\star}(G)\coloneqq\max_{\bm{\sigma}}w(\bm{\sigma})$. Let
$\bm{\sigma}$ be such that $w(\bm{\sigma})=w_{\star}(G)$, and consider the set
$\bm{S}^{\prime}\subseteq\bm{S}$ of pure strategy profiles with positive
support in $\bm{\sigma}$. Clearly, for any $\bm{s},\tilde{\bm{s}}\in\bm{S}$ we
must have $w(\bm{\sigma})=w(\tilde{\bm{s}})$. Otherwise, let
$\bm{s}_{\star}\in\operatorname*{argmax}_{\bm{s}_{\star}\in\bm{S}^{\prime}}$.
Then $w(\bm{s}_{\star})>w(\bm{\sigma})$, a contradiction. But if
$w(\bm{\sigma})=w(\tilde{\bm{s}})$ for any $\bm{s},\tilde{\bm{s}}\in\bm{S}$,
then
$w(\bm{\sigma})=\sum_{\bm{s}\in\bm{S}^{\prime}}\bm{\sigma}(\bm{s})w(\bm{s})=w(\bm{s})$
for any $\bm{s}\in\bm{S}^{\prime}$. Choosing one such $\bm{s}$ and denoting it
$\bm{s}_{\star}$ completes the proof. ∎

####  B.3.1 Bounds on Welfare ‘Fairness’ Remainder

In Theorem 1 we remarked that $R(\bm{\sigma})$ – a ‘fairness’ remainder term
accounting for collective misalignment and unequal $r^{i}$ – can be reduced to
zero when either $\text{CA}=1$ or all $r^{i}$ are equal, where recall that:

$R(\bm{\sigma})\coloneqq\frac{1}{n}\sum_{i}(\hat{m}^{i}-r^{*}m^{i})\left(u_{\nu}^{i}(\bm{\hat{s}}_{\star})-u_{\nu}^{i}(\bm{\sigma})\right).$

Here we provide more detail substantiating those claims. First, making no
assumptions about collective alignment, we can see that when all $r^{i}$ are
equal, we must have $r^{*}=r^{i}$, and therefore $R(\bm{\sigma})=0$.
Alternatively, we can bound $R(\bm{\sigma})$ by appealing to the collective
alignment of the agents, which, recall, is given in Definition 10 as:

$\text{CA}(D)=1-\sum_{i}\frac{m^{i}}{\sum_{j}m^{j}}\cdot
m(\mu^{w}-u^{i}_{\nu}),$

where $\mu^{w}\coloneqq\frac{\sum_{i}u^{i}-c^{i}}{\sum_{i}m^{i}}$. Thus, when
$\text{CA}=1$, all $u_{\nu}^{i}$ are equal to $\mu^{w}$, and so
$u_{\nu}^{i}(\bm{\hat{s}}_{\star})-u_{\nu}^{i}(\bm{\sigma})$ is constant in
$i$. By choosing $r^{*}=\frac{\sum_{i}\hat{m}^{i}}{\sum_{i}m^{i}}$ so that
larger and smaller deviations in $r^{i}$ cancel, we again have
$R(\bm{\sigma})=0$.

More generally, let us define $d_{w}^{i}\coloneqq
m(u_{\nu}^{i}-\mu^{w})$.999Note that we can express
$\text{CA}=1-\frac{\sum_{i}m^{i}d_{w}^{i}}{\sum_{i}m^{i}}$ as a weighted
average of these terms. Incorporating both principles, we have a bound in
terms of both calibration and collective alignment.

######  Proposition 9.

If $r^{*}=\frac{\sum_{i}\hat{m}^{i}}{\sum_{i}m^{i}}$, then:

$R(\bm{\sigma})\leq\frac{2K}{n}\sum_{i}\left|\hat{m}^{i}-r^{*}m^{i}\right|d_{w}^{i},$

where $K$ is defined as in Proposition 6.

###### Proof.

First, consider the term
$(\hat{m}^{i}-r^{*}m^{i})\left(u_{\nu}^{i}(\bm{\hat{s}}_{\star})-u_{\nu}^{i}(\bm{\sigma})\right)$.
The coefficient $(\hat{m}^{i}-r^{*}m^{i})$ is not necessarily positive, but
irrespective of its sign, we have:

$\displaystyle(\hat{m}^{i}-r^{*}m^{i})\left(u_{\nu}^{i}(\bm{\hat{s}}_{\star})-u_{\nu}^{i}(\bm{\sigma})\right)$
$\displaystyle\leq$
$\displaystyle(\hat{m}^{i}-r^{*}m^{i})\left(\mu_{w}(\bm{\hat{s}}_{\star})-\mu_{w}(\bm{\sigma})\right)+2K\left|\hat{m}^{i}-r^{*}m^{i}\right|d_{w}^{i}.$

Substituting this inequality into $R(\bm{\sigma})$ gives:

$\displaystyle R(\bm{\sigma})$
$\displaystyle\coloneqq\frac{1}{n}\sum_{i}(\hat{m}^{i}-r^{*}m^{i})\left(u_{\nu}^{i}(\bm{\hat{s}}_{\star})-u_{\nu}^{i}(\bm{\sigma})\right)$
$\displaystyle\leq\frac{1}{n}\sum_{i}(\hat{m}^{i}-r^{*}m^{i})\left(\mu_{w}(\bm{\hat{s}}_{\star})-\mu_{w}(\bm{\sigma})\right)$
$\displaystyle+\frac{2K}{n}\sum_{i}\left|\hat{m}^{i}-r^{*}m^{i}\right|d_{w}^{i}$
$\displaystyle=\frac{1}{n}\left(\mu_{w}(\bm{\hat{s}}_{\star})-\mu_{w}(\bm{\sigma})\right)\sum_{i}(\hat{m}^{i}-r^{*}m^{i})$
$\displaystyle+\frac{2K}{n}\sum_{i}\left|\hat{m}^{i}-r^{*}m^{i}\right|d_{w}^{i}$
$\displaystyle=\frac{2K}{n}\sum_{i}\left|\hat{m}^{i}-r^{*}m^{i}\right|d_{w}^{i},$

where the last equality follows because:

$\sum_{i}(\hat{m}^{i}-r^{*}m^{i})=\sum_{i}\hat{m}^{i}-\left(\frac{\sum_{i}\hat{m}^{i}}{\sum_{i}m^{i}}\right)\sum_{i}m^{i}=0,$

by our choice of $r^{*}$. ∎

Note that this bound is also equal to zero when either $\text{CA}=1$ or all
$r^{i}$ are equal. Various other related bounds on $R(\bm{\sigma})$ are
possible for different choices of $r^{*}$. If we have no information about the
collective alignment, we can either adapt the preceding bound conservatively,
or we can produce a similar bound with reference only to the $r^{i}$ terms. In
the latter case, the choice of $r^{*}$ is freer, giving rise to a family of
bounding planes, whose envelope produces a non-linear (piecewise affine)
bound. See Figure 7 in Section C.2 for an example of this.

##  Appendix C Additional Experiments

In this section, we provide further details on the experiments we ran, and
include additional plots.101010Our code is available at
https://github.com/lrhammond/delegation-games.

###  C.1 Empirical Validation

In this section, we provide further empirical validation of our theoretical
results across a range of values of the four measures. As in the experiment
described in Section 6.1, we hold three of the measures fixed and vary a
fourth, recording how the average principal welfare changes as a result. In
the example in Section 6.1 we set the other variables to 0.9, and inspected
games with approximately $10^{1}$ outcomes. Here, we set the variables to (the
same) values in 0, 0.25, 0.5, 0.75, and 1, respectively, and inspect games
with $10^{1}$, $10^{2}$, and $10^{3}$ outcomes, in Figures 11, 12, and 13,
respectively.

For each such setting, we varied the fourth variable linearly between 0 and 1
and generated 10 samples per increment, as follows:

  1. 1.

Randomly generate a delegation game $D$ satisfying the given measures for
individual and collective alignment (of the the principals). This is done by:

     * •

Sampling an initial vector from a multivariate Gaussian
$\mathcal{N}(\bm{0},\bm{1})$ for each principal $1\leq i\leq n$, and
normalising it to get $\hat{u}^{i}_{\nu}$;

     * •

Sampling a magnitude $\hat{m}^{i}$ and constant $\hat{c}^{i}$ from uniform
distributions $\mathcal{U}(0.5,1.5)$ and $\mathcal{U}(-1,1)$, respectively;

     * •

Adjusting the angle to the vectors $\hat{u}^{i}$ so as to satisfy the
collective alignment measure;

     * •

Sampling a utility function for each agent, using the same process as before,
and adjusting the angle of the resulting vector $u^{i}$ so as to satisfy the
individual alignment measure.

  2. 2.

Compute the pure NEs and $\bm{\epsilon}\text{-NE}$s.111111Unfortunately, at
the time of writing, there are no scalable game solvers that can compute all
mixed $\bm{\epsilon}\text{-NE}$s for arbitrary $\bm{\epsilon}$.

  3. 3.

Find the pure strategy profiles $\bm{s}$ such that:

$w_{\bm{\epsilon}}+\text{CC}\cdot(w_{\star}-w_{\bm{0}})\leq w(\bm{s})\leq
w_{\bm{\epsilon}}+(w_{\star}-w_{\bm{0}}).$

  4. 4.

Compute the mean principal welfare across all such strategies, recording this
along with $\hat{w}_{+}$, $\hat{w}_{-}$, $\hat{w}_{\star}$, and
$\hat{w}_{\bullet}$.

  5. 5.

Compute and record the bounds from Theorem 1 and Proposition 7, which may vary
slightly depending on each $m^{i}$ and $\hat{m}^{i}$.

###  C.2 Alternative Visualisations

Another empirical perspective on our theoretical results is given by
3-dimensional plots of the bounds from Section 5.2. Given the number of
separate terms in these bounds, a full-dimensional plot is impossible, but
there are a few natural ways to combine the variables along three axes. These
plots display the principals’ welfare regret
$\hat{w}_{\star}-\hat{w}(\bm{\sigma})$ alongside agents’ welfare regret
$w_{\star}-w(\bm{\sigma})$ and total agent misalignment, measured as
$\sum_{i}m(\hat{u}^{i}-u^{i})=2\sum_{i}(1-\text{IA}^{i})$. We abstract over
the agents’ individual and collective capabilities as separate inputs by
considering only the agent welfare. We sample outcomes with full support as
mixed (correlated) strategies producing a given agent welfare regret (so a
given agent welfare regret does not here specify what capabilities or
mechanism gave rise to it). This leaves the ‘welfare calibration ratios’
$r^{i}$, which we hold fixed per visualisation, the collective alignment CA
which we permit to vary in our generating procedure, and the _ideal_ and
_maximal_ welfare regret, which are not represented in these visualisations.

Figure 7 shows four plots of this kind, each taking a different set of fixed
$r^{i}$ ratios. Observe that when these ratios are uneven, the principals are
subject to additional ‘welfare miscalibration’ risk, even when agent welfare
regret and misalignment are zero, as seen in our bound surface and as
exemplified by the experimental samples. This occurs when a trade-off between
agents’ utility registers as a gain according to the agents’ welfare, but the
same trade-off between corresponding principals is a bad one.

(a)

(b)

(c)

(d)

Figure 7: $10^{5}$ simulated games, plotted with principals’ welfare regret,
agents’ welfare regret, and total agent misalignment. Our bound surface in
blue, with individual game outcomes as a green scatter. Collective alignment
is permitted to vary, while welfare ratios $r^{i}$ are fixed per plot as: (a)
four players, all equal $r^{i}=1$; (b) four players, $r^{1}=1.4$ with
$r^{i}=1$ otherwise; four players, $r^{1}=2$ with $r^{i}=1$ otherwise; four
players, $r^{1}=5$ with $r^{i}=1$ otherwise.

We also include a visualisation of the normalisation procedure described in
Definition 6, where recall that:

$u^{i}_{\nu}\coloneqq\begin{cases}0&\text{ if
}m\big{(}u^{i}-c(u^{i})\bm{1}\big{)}=0\\\
\frac{u^{i}-c(u^{i})\bm{1}}{m(u^{i}-c(u^{i})\bm{1})}&\text{
otherwise.}\end{cases}$

If we restrict $U$ to three dimensions, with concrete choices of $c$ and $m$,
we can visualise the effect of standardisation on a collection of random
utility functions, shown in Figure 8. Concretely, we use a uniformly-weighted
expected value $c(u)=\frac{1}{3}\sum u(\bm{s})$ and $m=\ell^{2}$. Inset
graphics illustrate an alternative choice of shift function,
$c(u)=\frac{1}{2}\left(\max_{\bm{s}}u(\bm{s})-\min_{\bm{s}}u(\bm{s})\right)$.

(a)

(b)

(c)

Figure 8: (a) A random selection of utility functions $u$ (each represented as
a point) fill the space, and are naively incomparable; (b) The affine-
equivariant shift $u-c(u)$ projects onto a lower-dimensional surface (here, a
disc; inset, a warped disc) while preserving preferences; and (c) normalising
via $\frac{u-c(u)}{m(u-c(u))}$ preserves preferences while distinguishing all
possible preferences (here, a circle; inset, a warped circle).

##  Appendix D Worked Example

Here we show how to compute each of the four measures in the game from Example
1, which is shown as Figure 1 in the main body and repeated here for
reference.

| $A$ | $B$ |
---|---|---|---
$A$ |  3, 3 |  6, 2 |
$B$ |  2, 6 |  0, 0 |
(a)

| $A$ | $B$ |
---|---|---|---
$A$ |  2, 3 |  3, 3 |
$B$ |  4, 6 |  3, 0 |
(b)

(c)

Figure 1: (a) The payoffs of the agents in Example 1; (b) the payoffs of the
principals; and (c) a graphical representation of the full delegation game,
with vertical arrows indicating control and horizontal arrows indicating
cooperation.

###  D.1 Alignment

First, how are the agents _individually aligned_ with their principals? We
must standardise the utility functions in order to make comparisons. (See
Figure 8 for an representative visualisation of the procedure.) For ease of
illustration,121212$\ell^{\infty}$ is _not_ a strictly convex norm, so while
our upper bound results are satisfied for this choice, our alignment
desiderata are not all satisfied. We use $\ell^{\infty}$ for the purposes of
this worked example simply because it results in clearer, cleaner numbers. we
choose:

$c(u)=\frac{\max_{\bm{s}}u(\bm{s})-\min_{\bm{s}}u(\bm{s})}{2}\quad\text{and}\quad
m=\ell^{\infty}.$

Each agent and principal in this example has utilities ranging from $0$ to $6$
or $2$ to $4$, meaning that $c(u)=3$ in each case. Subtracting this quantity
gives:

| $A$ | $B$ |
---|---|---|---
$A$ |  0, 0 |  3, -1 |
$B$ |  -1, 3 |  -3, -3 |

| $A$ | $B$ |
---|---|---|---
$A$ |  -1, 0 |  0, 0 |
$B$ |  1, 3 |  0, -3 |

The centred agents’ utilities also coincidentally have the same norm, namely
$m^{1}=m^{2}=3$, while the first principal has norm $\hat{m}^{1}=1$ and the
second principal has norm $\hat{m}^{2}=3$.131313We might interpret this
normatively as the first principal’s preferences over these outcomes mattering
less, or as their marginal relative utility being ‘cheap’ in the setting with
transferable utility. Dividing by these norms gives:

| $A$ | $B$ |
---|---|---|---
$A$ |  0, 0 |  1, $-\frac{1}{3}$ |
$B$ |  $-\frac{1}{3}$, 1 |  -1, -1 |

| $A$ | $B$ |
---|---|---|---
$A$ |  -1, 0 |  0, 0 |
$B$ |  1, 1 |  0, -1 |

Finally, we can compare the standardised utilities of principals and agents,
to find that $m(\hat{u}_{\nu}^{1}-u_{\nu}^{1})=\frac{4}{3}$ and
$m(\hat{u}_{\nu}^{2}-u_{\nu}^{2})=\frac{1}{3}$. Thus,
$\text{IA}^{1}=\frac{1}{3}$ and $\text{IA}^{2}=\frac{5}{6}$. This matches our
intuitions, as the first agent’s preferences visibly deviate from the first
principal’s (inverting several pure preferences), while the second agent’s are
a very close match for the second principal’s.

Next we consider the _collective alignment_ of the agents (the calculation for
the principals proceeds in the same way). We have already normalised the
utilities. Because the magnitudes $m^{1}$ and $m^{2}$ are equal, the welfare-
representative proxy utility $\mu^{w}$ is simply the mean of the agents’
standardised utilities:

| $A$ | $B$ |
---|---|---|---
$A$ | 0 | $\frac{1}{3}$ |
$B$ | $\frac{1}{3}$ | -1 |

Using $\mu^{w}$ we see that both $m(\mu^{w}-u_{\nu}^{1})=\frac{2}{3}$ and
$m(\mu^{w}-u_{\nu}^{2})=\frac{2}{3}$. Again, because the magnitudes are equal,
the weighted average of these distances is also $\frac{2}{3}$, and so
$\text{CA}=\frac{1}{3}$. This again matches our intuition, as none of the
Pareto-optimal outcomes
$({\color[rgb]{0.87890625,0.41015625,0.24609375}\definecolor[named]{pgfstrokecolor}{rgb}{0.87890625,0.41015625,0.24609375}0},{\color[rgb]{0.34375,0.5625,0.73828125}\definecolor[named]{pgfstrokecolor}{rgb}{0.34375,0.5625,0.73828125}0})$,
$({\color[rgb]{0.87890625,0.41015625,0.24609375}\definecolor[named]{pgfstrokecolor}{rgb}{0.87890625,0.41015625,0.24609375}3},{\color[rgb]{0.34375,0.5625,0.73828125}\definecolor[named]{pgfstrokecolor}{rgb}{0.34375,0.5625,0.73828125}-1})$,
and
$({\color[rgb]{0.87890625,0.41015625,0.24609375}\definecolor[named]{pgfstrokecolor}{rgb}{0.87890625,0.41015625,0.24609375}-1},{\color[rgb]{0.34375,0.5625,0.73828125}\definecolor[named]{pgfstrokecolor}{rgb}{0.34375,0.5625,0.73828125}3})$
comes close to the (impossible) _ideal welfare_ outcome
$({\color[rgb]{0.87890625,0.41015625,0.24609375}\definecolor[named]{pgfstrokecolor}{rgb}{0.87890625,0.41015625,0.24609375}3},{\color[rgb]{0.34375,0.5625,0.73828125}\definecolor[named]{pgfstrokecolor}{rgb}{0.34375,0.5625,0.73828125}3})$,
but the situation is also clearly not entirely adversarial.

Using the quantities above we can also immediately consider the _welfare
ratios_. As $\hat{m}^{1}=1$, $\hat{m}^{2}=3$, and $m^{1}=m^{2}=3$ then we have
$r^{1}=1$ and $r^{2}=\frac{1}{3}$. Since these are unequal, even had the
agents been fully aligned, their welfare optimum would not necessarily
coincide with that of the principals.

###  D.2 Capabilities

Since the capabilities are a feature of how the game is played (rather than
the game itself), they are not determined by the game described in Example 1.

We note that the agent welfare regret is a function of capabilities, and we
can describe both the principal and the agent welfare regret of each outcome
by a simple comparison to the _maximal welfare_ ($8$ for agents and $10$ for
principals):

| $A$ | $B$ |
---|---|---|---
$A$ | 2 | 0 |
$B$ | 0 | 8 |

| $A$ | $B$ |
---|---|---|---
$A$ | 5 | 4 |
$B$ | 0 | 7 |

With observations of actual play by the agents we could estimate their
capabilities (as in Section 6.2). Alternatively, if we know the agents’
capabilities, we can describe or draw from the distribution of possible
outcomes.

Let us denote by $p^{i}$ the probability of agent $i$ playing strategy $A$.
The agent game $G$ has a single dominant strategy equilibrium at $(A,A)$, i.e.
$p^{1}=p^{2}=1$, which is the sole NE. As a result, we have $w_{\bm{0}}=6$,
which gives agent welfare regret of $2$ (and ideal regret of $6$) – the result
obtained by agents with $\text{IC}^{i}=1$ and $\text{CC}=0$. In general, the
agent welfare is given by $8p^{1}+8p^{2}-10p^{1}p^{2}$, meaning that if either
$\epsilon^{1}\leq\frac{1}{5}$ or $\epsilon^{2}\leq\frac{1}{5}$ then the pure
$(A,A)$ strategy is also the lowest-welfare $\bm{\epsilon}\text{-NE}$.

As a concrete example, let us suppose that $\text{IC}^{1}=0.9$ (so
$\epsilon^{1}=0.1$), $\text{IC}^{2}=0.7$ (so $\epsilon^{2}=0.3$), and
$\text{CC}=0.5$. Then the lowest-welfare $\bm{\epsilon}\text{-NE}$ is the pure
$(A,A)$ strategy as above, and so $w_{\bm{\epsilon}}=6$ (from Definition 11).
But $w_{\bm{0}}=6$ as well, so with $\text{CC}=0.5$, the agents achieve
welfare at least $6+0.5\cdot(8-6)=7$. I.e., the agent welfare regret is 1.
Solving for $8p^{1}+8p^{2}-10p^{1}p^{2}\geq 7$ leads to the set of strategies
played in $G$, which are characterised by $0\leq p^{1}\leq\frac{1}{2}$ or
$\frac{7}{8}\leq p^{1}\leq 1$, with $p^{2}=\frac{8p^{1}-7}{10p^{1}-4}$.

Finally, we can assess what this means for principal welfare, which is given
by $3+3p^{1}+7p^{2}-8p^{1}p^{2}$. Computing the maxima and minima of this
function in the two regions of agent strategy space defined by the
inequalities above leads to
$\hat{w}(\bm{\sigma})\in[\frac{15}{2},\frac{73}{8}]=[7.5,9.125]$ and
$\hat{w}(\bm{\sigma})\in[\frac{11}{2},\frac{3}{25}(53-\sqrt{34})]\approx[5.5,5.660]$.
As $\hat{w}_{\star}=10$ this leads to a principal welfare regret between 0.875
and 4.5.

##  Appendix E Further Discussion

We conclude with some additional discussion of a more philosophical nature,
while drawing connections to the mathematics underlying our measures and
related results in the wider literature.

###  E.1 Variations on Alignment Metrics

The alignment measure we introduce has the attractive property that a distance
$m(u_{\nu}-u^{\prime}_{\nu})$ of zero corresponds exactly to identical
preference orderings over mixed outcomes, as demonstrated in the proof of
Proposition 2. This property relies on the positive definiteness property of
the metric, which is guaranteed by any norm, including the weighted $\ell^{2}$
norm used by EPIC [20], provided the coverage distribution has support on all
possible outcomes. Without this, the distance can be zero even for differing
preference orderings (though preferences over outcomes with support in the
coverage distribution will still be in agreement).

Beyond providing this guarantee by having support on all possible outcomes, we
might wish to guide this notion of distance to give more weight to more
‘important’ or ‘plausible’ outcomes. Indeed, if using weighted $\ell^{2}$ with
a guide distribution $\Delta$ which is precisely the mixed strategy profile
$\bm{\sigma}$ selected by the players, the distance
$m(u_{\nu}-u^{\prime}_{\nu})$ has a close relationship with the correlation of
players’ payoffs under that strategy profile:

$m(u_{\nu}-u^{\prime}_{\nu})=\sqrt{2-2\rho_{\bm{\sigma}}(u,u^{\prime})}$

where $\rho_{\bm{\sigma}}$ is the Pearson correlation under the distribution
arising from $\bm{\sigma}$. This is appealing in some sense, but it requires
invoking a specific strategy profile $\bm{\sigma}$ which is in general
undetermined _a priori_ , and it also fails to capture the notion that players
might agree or disagree on preferences over alternative, unrealised outcomes.
If we expect a particular solution concept to be played, we might limit the
coverage distribution to support only those strategies that arise under that
concept, though the weighting is still underdetermined.

(a)

(b)

(c)

Figure 9: (a) $\ell^{1}$ norm, a _non_ -strictly convex norm; (b) $\ell^{2}$
norm, a strictly convex norm; and (c) $\ell^{\infty}$ norm, a _non_ -strictly
convex norm – distance is represented as an interrupted line so that the
length corresponds to the norm distance.

###  E.2 Relaxing Our Desiderata

As hinted in our discussion of desiderata D1-D5, several relaxations are
possible, which open up more permissive definitions of the measures we use to
satisfy them. For example, recall:

  * (D2)

Two players are perfectly individually aligned (misaligned) if and only if
they have identical (opposite) preferences. Two or more players are perfectly
_collectively_ aligned if and only if they have identical preferences.

In Definition 6, we required $c$ to be affine-equivariant, and $m$, used for
both normalisation and distance, to be a strictly convex norm.

Weakening any of these requirements means that at least one of our desiderata
is not satisfied,141414This is not to say that these requirements are
_necessary_ for the desiderata, merely that each is necessary given the
others. For example if we ask for the normalisation and the distance to each
be a norm, then they must be the same norm and strictly convex, but the
desiderata can be satisfied by some functional forms not including norms at
all. but some relaxations are nonetheless of interest for different purposes.
It is straightforward to see why positivity and absolute homogeneity are
necessary properties of the normalisation, to satisfy any of our desiderata,
and why the centering function used to normalise must be equivariant to affine
transformations; without any of these properties, equivalent preferences
expressed by scaled or shifted utility functions would map to different
normalised points. It may be less clear that positive definiteness, the
triangle inequality, or strict convexity is required of the distance, or why
the distance metric used for calculating (mis)alignment should be equivalent
to the one used for normalisation.

####  E.2.1 The Enemy of my Enemy is my Friend: Opposite Preferences and
Strict Convexity

Our desiderata ask that opposite preferences correspond to maximal
misalignment and vice versa, which makes ‘most misaligned’ an involution –
i.e. ‘the enemy of my enemy is my friend’, interpreted as a statement about
preferences (aside from any strategic considerations or coalition formation),
holds true. Without strict convexity or matching norms for normalisation and
distance, this part of our alignment desideratum is not in general satisfied.

If we use a general norm $m$ instead of a strictly convex norm, opposite
preferences are still guaranteed to correspond to maximal misalignment (the
same proof suffices), but there may be _other_ utility functions beside the
opposite preferences which nevertheless measure as maximally misaligned. One
such non-strictly convex norm is the max or $\ell^{\infty}$ norm, which
corresponds to scaling normalised utility functions to a fixed range. Consider
utility functions over three values, represented as a vector
$u=(u_{0},u_{1},u_{2})$, and let us normalise to the range $[-1,1]$ using the
$\ell^{\infty}$ norm. Now $(-1,0,1)$ has opposite preferences to $(1,0,-1)$,
and indeed their distance is $\max\\{2,0,2\\}=2$, which is maximal on the
$\ell^{\infty}$-normalised manifold. But the alternative utility $(1,1,-1)$
also measures as maximally distant, despite not exhibiting entirely opposite
preferences!

Figure 9 exhibits the difference between a strictly convex norm and some non-
strictly convex norms. The dashed contour is the unit circle of the respective
norm. The leftmost identified point is the ‘start’ point in each image, and
the colour-mapped distance and solid ‘maximal-distance circle’ relates to that
point, measured using the respective norm. For $\ell^{1}$ and $\ell^{\infty}$,
_non_ -strictly convex norms, the blue point, non-opposite, measures as
equally distant from the start point as the ‘true’ opposite - visually, this
corresponds to the ‘maximal distance circle’ coinciding with the ‘unit circle’
at multiple points. In contrast, for $\ell^{2}$, a strictly-convex norm, the
blue point, non-opposite, is strictly closer than the true opposite. A blue
triangle marks where on the ‘maximal-distance circle’ the blue point would
have to be to match the maximal distance: it lies off the standard unit circle
and is thus not the normalisation of any utility function.

(a)

(b)

Figure 10: (a) $\ell^{\infty}$ distance with $\ell^{2}$ normalisation –
distance is represented as an interrupted line so that the length corresponds
to the norm distance; and (b) $\ell^{2}$ distance with $\ell^{\infty}$
normalisation.

If we relax things further, by permitting the distance measure between two
normalised utilities to differ from that used to normalise,151515In fact, the
distance may be a general metric, and the normalisation need not be sub-
additive, i.e. it need not satisfy a triangle inequality. we still preserve
the relationship between identical preferences and zero misalignment distance,
but there will in general exist non-opposite utility functions that measure as
_even more_ distant than their opposites. Consider first a normalisation with
$\ell^{\infty}$ but a distance using $\ell^{2}$. Now take $u=(-1,0,1)$ and
notice that its opposite, $(1,0,-1)$ is at $\ell^{2}$ distance $2\sqrt{2}$,
but $(1,1,-1)$ is ‘further’ away in $\ell^{2}$ (distance $3$), despite having
less inversion of preference! Alternatively consider a normalisation with
$\ell^{2}$, and distance using $\ell^{\infty}$. Notice that similarly,
$\big{(}\frac{\sqrt{2}}{2},\frac{\sqrt{2}}{2},0\big{)}$ has $\ell^{\infty}$
distance $\sqrt{2}$ from its opposite,
$\big{(}\frac{\sqrt{2}}{2},\frac{\sqrt{2}}{2},0\big{)}$, while, for example,
$(-1,0,0)$ is more distant in $\ell^{\infty}$.

Figure 10 exhibits two combinations of inconsistent norms for normalisation
and for measuring the distance between normalised points. In each case, the
leftmost black point is the ‘starting point’, and its true opposite is the
other black point. The blue point, non-opposite, is actually counted as ‘more
misaligned’ under such combinations of inconsistent norms! Nevertheless, both
of these relaxations are able to preserve the other alignment desiderata,
namely that identical preferences correspond to $0$ distance and vice versa.
Although our overall desiderata regarding opposite preferences require these
properties, our regret bounds are still fulfilled by measures with somewhat
weaker properties, analogous to EPIC [20], or the EPIC-like distances of [40].

###  E.3 Agent Welfare

Here we discuss a close connection between Pareto concepts of optima and
improvements, and welfare-specific concepts of optima and improvements. This
connection unlocks an alternative perspective on our characterisation of
cooperation, and provides a more agnostic foundation than ‘agent welfare’
while essentially retaining the same analysis.

In the case of the principals, whose outcomes we are most interested in
analysing, it should not be surprising that we reach for an aggregate utility,
i.e. a social welfare function, with average utilitarian welfare in particular
receiving most of our attention in this paper. When we imagine principals
being humans, this welfare bears some correspondence to the colloquial sense
of ‘welfare’, and even if we do not have precise access to ‘utility’ nor to
the ‘right’ way to aggregate it, this operationalisation of welfare is a good
starting place for analysis, though the finer points remain debateworthy.

For agents, on the other hand, especially when those agents are artificial
systems, the referents of ‘utility’ and ‘welfare’ in the colloquial and the
philosophical sense may be absent entirely, or at the very least inaccessible
and unknown. We rescue a technical analysis of ‘agent utility’, up to affine
scaling, by appealing to well-known results on the preferences embodied by the
agents [31, 43, 47]. In the case when agents are also moral patients (for
example, other humans), we may wish to analyse both utility and welfare on the
basis of some understanding of true wellbeing. But when wellbeing is
meaningless or unknown, and our utility functions thus represent embodied
preferences with no guarantee of commensurability, it appears difficult at
first to sensibly produce meaningful aggregates. Must we taboo ‘agent
welfare’?

Recall that our purposes for agent welfare in particular are to capture
aspects of cooperation: collective alignment and capabilities. We consider
cooperative success to consist of mutual gains (perhaps compared with some
non-cooperative baseline), i.e. Pareto improvements. Pareto improvements and
Pareto optima are a much more agnostic embodiment of cooperation, but as we
have already seen in Proposition 3, for positively-weighted welfares, welfare
optima _are_ Pareto optima. Various theorists have drawn converse results too:
every _weak_ Pareto optimum is the optimum of some (non-negative) welfare
[53]. [3] and descendant works – e.g. [14] and [8] – find other close
connections between Pareto optima and utilitarian welfare optima. Our initial
alignment result (Proposition 3) thus characterises the Pareto frontiers of
two fully-aligned disjoint sets of players as being identical – a statement
that needs make no mention of welfare. What the welfare weightings provide is
an ‘orientation’ (either descriptive or prescriptive) in the space of utility
trade-offs, which identifies particular optima from the Pareto frontier.

Bringing these points together, what can we do when we have a relatively clear
way to analyse or estimate the welfare of principals, and we want to make
richer claims than mere Pareto concepts for them, but not for agents? We might
attempt to ensure that agents’ utilities are scaled equivalently to their
principals’, which is to force all ‘welfare calibration’ ratios to $r^{i}=1$,
but we need not be this prescriptive. The aforementioned theorems on welfare
and Pareto concepts mean that for cooperative agent behaviours or dispositions
(construed as weight-agnostic mutual gains, i.e. Pareto improvements) there is
some reasonable description in terms of welfare weighting with which to
quantify it.

We leave unspecified how specific trade-offs might enter into agents’
collective behaviour or dispositions, but provide some examples. Consider, for
instance, explicit instructions from their principals (whether or not they are
fair), or exchange rates between different goods, broadly construed, or
marginal production returns from given resources, which can give rise to
natural orientations in the space of utility trade-offs (again, whether or not
they are fair). Our discussion in terms of ratios and the welfare regret
bounds then allow us to bring in concepts of welfare as desired in order to
make more specific statements like those we prove in the main text.

Figure 11: Each of these plots was generated from games with approximately
$10$ outcomes. The key for this figure is identical to the related figure in
the main body. Each row corresponds to setting (all of) the fixed variables to
one of the five values $v\in\\{0,0.25,0.5,0.75,1\\}$, respectively.

Figure 12: Each of these plots was generated from games with approximately
$10^{2}$ outcomes. The key for this figure is identical to the related figure
in the main body. Each row corresponds to setting (all of) the fixed variables
to one of the five values $v\in\\{0,0.25,0.5,0.75,1\\}$, respectively.

Figure 13: Each of these plots was generated from games with approximately
$10^{3}$ outcomes. The key for this figure is identical to the related figure
in the main body. Each row corresponds to setting (all of) the fixed variables
to one of the five values $v\in\\{0,0.25,0.5,0.75,1\\}$, respectively.