# Improving Social Welfare While Preserving Autonomy via a Pareto Mediator

Stephen McAleer
Department of Computer Science
University of California, Irvine
<EMAIL_ADDRESS>&John Lanier
Department of Computer Science
University of California, Irvine
<EMAIL_ADDRESS>Michael Dennis
Department of Computer Science
University of California, Berkeley
<EMAIL_ADDRESS>&Pierre Baldi
Department of Computer Science
University of California, Irvine
<EMAIL_ADDRESS>&Roy Fox
Department of Computer Science
University of California, Irvine
<EMAIL_ADDRESS>
###### Abstract

Machine learning algorithms often make decisions on behalf of agents with
varied and sometimes conflicting interests. In domains where agents can choose
to take their own action or delegate their action to a central mediator, an
open question is how mediators should take actions on behalf of delegating
agents. The main existing approach uses delegating agents to punish non-
delegating agents in an attempt to get all agents to delegate, which tends to
be costly for all. We introduce a Pareto Mediator which aims to improve
outcomes for delegating agents without making any of them worse off. Our
experiments in random normal form games, a restaurant recommendation game, and
a reinforcement learning sequential social dilemma show that the Pareto
Mediator greatly increases social welfare. Also, even when the Pareto Mediator
is based on an incorrect model of agent utility, performance gracefully
degrades to the pre-intervention level, due to the individual autonomy
preserved by the voluntary mediator.

##  1 Introduction

We often choose to delegate our decisions to algorithms. What should a
decision-support system do when multiple people choose to delegate their
actions to the same algorithm? When someone uses an app to get directions,
accepts recommendations for who to follow on social media, or takes a
recommended job on a gig app, they are allowing an algorithm to make a
decision for them which not only affects their own commute, news feed, or
income, but also affects the outcomes of others.

In this paper we consider a middle ground between central planning and anarchy
where a third-party mediator is able to act on behalf of any player who
chooses to delegate control to the mediator. The mediator simultaneously plays
moves on behalf of all players who have chosen to delegate to the mediator.
This notion is natural in settings where there already exist reliable
administrators in place. For example, markets that take place on managed
platforms, or computer networks that communicate through routers.

Existing literature has proposed mediators that can implement efficient
mediated equilibria [25, 47, 52], but that probably will not work in practice,
because they rely on punishing agents who do not delegate which can be costly
to all agents involved. For example, on a platform for making restaurant
reservations, if a single person does not allow the platform to choose a
restaurant for them, the platform would send everyone else to the same
restaurant to punish them, harming everyone.

We introduce a mediator that is much less risky for agents to delegate actions
to. Instead of using delegating agents as punishers, our mediator tries to
maximize their utility subject to a Pareto improvement constraint. Our Pareto
Mediator works as follows: every agent submits an action in the original game
and a binary value signifying if they want the mediator to act for them. After
everyone submits their actions, the mediator finds a set of actions for the
delegating agents in the original game that maximizes the delegating agents’
social welfare, without making any delegating agent worse off.

Table 1 illustrates the proposed mediator in the prisoner’s dilemma. In the
mediated game on the right, the top left quadrant is the original game which
corresponds to both players choosing not to delegate. The third and fourth row
and column correspond to taking the first and second actions but also choosing
to delegate. The outcome $(2,2)$ associated with both players cooperating is
now a strong Nash equilibrium (D$+$, D$+$), with higher social welfare than
the original Nash equilibrium.

22[][] & C D
C $2,2$ $0,3$
D $3,0$ $1,1$
44[][] & C$-$ D$-$ C$+$ D$+$
C$-$ $2,2$ $0,3$ $2,2$ $0,3$
D$-$ $3,0$ $1,1$ $3,0$ $1,1$
C$+$ $2,2$ $0,3$ $2,2$ $0,3$
D$+$ $3,0$ $1,1$ $3,0$ $2,2$

Table 1: Prisoner’s Dilemma with a Pareto Mediator. Left: the original
prisoner’s dilemma. The only Nash equilibrium is for both players to defect
(D, D), to receive a reward of $(1,1)$. Right: the mediated game with a Pareto
Mediator. Agents submit an action (C or D) and a bit ($+$ or $-$) indicating
whether or not they want to delegate to the mediator. If up to one agent
delegates the game is unchanged. If both agents delegate, the Pareto Mediator
replaces each outcome with another outcomes that Pareto dominates it. In this
case the Pareto Mediator replaces $(1,1)$ with $(2,2)$. This results in (D$+$,
D$+$) becoming a strong Nash equilibrium in the mediated game, with higher
utility for both players.

The Pareto Mediator has several desirable theoretical properties. First, in
two-player games, delegating an action always weakly dominates taking that
action in the original game. Second, all pure Nash equilibria in the mediated
game have at least as much total utility as any pure Nash equilibria in the
original game. Third, the Pareto Mediator is much less risky than the
Punishing Mediator in most games of interest. If an agent is uncertain whether
all other agents will delegate, it can be very risky to delegate to the
Punishing Mediator, because the agent could carry the burden of punishing
others. Conversely, delegating to the Pareto Mediator tends to be much less
risky because the group of delegators are all guaranteed to get higher utility
than they would have if none of them delegated.

We run simulations with online learning agents on normal form games and a
restaurant reservation game. Empirically, we find that the Pareto Mediator
achieves much higher social welfare than the Punishing Mediator. Moreover, a
much higher percentage of agents choose to delegate actions to the Pareto
Mediator than to the Punishing Mediator. Importantly, when the mediator does
not have true rewards for the agents, the agents choose not to delegate
actions, and the welfare is better than a central planner would have achieved.
We also run experiments with reinforcement learning (RL) agents in sequential
social dilemmas and find that the agents always choose to delegate their
actions to the Pareto Mediator and get much higher reward than with the
Punishing Mediator.

##  2 Preliminaries

###  2.1 Games and Mediators

A normal form game $\Gamma$ has three elements: a finite set of players
$P=\\{1,...,N\\}$, a pure strategy (action) space $S_{i}$ for each player $i$,
and payoff functions $u_{i}(s)$ for each profile $s=(s_{1},...,s_{N})$ of
strategies. All players other than some player $i$ are denoted by $-i$. We
focus on finite games where $S=\bigtimes_{i}S_{i}$ is finite. A mixed strategy
$\sigma_{i}$ is a probability distribution over actions. The space of player
$i$’s mixed strategies is denoted as $\Sigma_{i}$, where $\sigma_{i}(s_{i})$
is the probability player $i$ assigns to $s_{i}$. We denote the expected
payoff to player $i$ of mixed profile $\sigma$ by $u_{i}(\sigma)$.

######  Definition 1.

A mixed-strategy profile $\sigma^{*}$ is a Nash equilibrium if, for all
players $i$, $u_{i}(\sigma^{*}_{i},\sigma^{*}_{-i})\geq
u_{i}(s_{i},\sigma^{*}_{-i})$ for all $s_{i}\in S_{i}$. If $\sigma^{*}\in S$
then it is a pure Nash equilibrium.

Mediators are third parties to whom players in a game can delegate actions. In
this paper we consider mediators that can condition on the actions of non-
delegating players.

A mediated game $\Gamma(M)$ takes a game $\Gamma$ and adds an extra binary
action that agents take along with their original action to indicate whether
to delegate their action to the mediator $M$. So for a player $i$, their
mediated strategy space is $S_{i}\times\\{0,1\\}$. A mediator $M$ is a
function that takes in a joint mediated strategy profile
$s_{m}=(s_{i},d_{i})_{i\in P}$ and outputs a joint strategy profile
$s^{\prime}=M(s_{m})$ for the original game, thus setting
$u_{i}(s_{m})=u_{i}(M(s_{m}))$ in the mediated game. Mediators may only act on
behalf of agents that choose to delegate, so that $s^{\prime}_{i}=s_{i}$ if
$d_{i}=0$. If $d_{i}=1$, the mediator is free to choose a new action
$s^{\prime}_{i}$ for that player. We denote the set of delegating agents by
$D\subseteq P$.

Figure 1: Left: In the restaurant game (Section 4.3), agents simultaneously
reserve restaurants (arrows) and can choose to delegate (square around their
emoji). Restaurants have known capacity (number of chairs). If restaurant
reservations exceed capacity, a random subset of agents get to eat there and
the rest don’t get to eat anywhere. Center: The Punishing Mediator makes all
delegating agents go to the same restaurant as the non-delegating agent to
maximally punish him, but at a high cost to the punishing agents as well.
Right: The Pareto Mediator makes the cowboy go to a restaurant with extra
capacity, which doesn’t make any delegating agent worse off but makes the
cowboy and the robot better off.

###  2.2 Comparison to Other Concepts

Mediators can be seen as a middle ground between anarchy, represented by the
original game, and central planning, in which the best strategy profile is
dictated. In our experiments and in previous theoretical results, it has been
shown that allowing agents the ability to delegate to mediators can improve
social welfare compared to social welfare under anarchy. Central planning can
implement any outcome by forcing all agents to take particular actions, but in
many situations such forcing may not be feasible or desirable. For example,
when the mediator does not have full information about agent utilities,
central planning may produce inferior solutions. Furthermore, central
solutions concentrate power in the hands of one agent, which can make the
system vulnerable to malicious attacks.

Another type of mediator is one that is allowed to jointly recommend actions
to all players. If no player has incentive to deviate from their recommended
action, the joint distribution is called a correlated equilibrium [5]. This
mediator is weaker than the mediators we consider because it must allow for
the possibility that its suggested actions are not subsequently taken by the
players. On the other hand, correlated equilibria are more broadly applicable,
due to the ubiquity of situations in which mediators are able to recommend
actions but not take them on behalf of agents. However, as with the mediators
we study, there remains an open question of how to choose which correlated
equilibrium to suggest to the agents when there are several correlated
equilibria.

###  2.3 Punishing Mediator

One existing approach to implement desired outcomes by mediated equilibria is
to use what we term a “Punishing Mediator” [25, 47, 52]. If every agent in the
game decides to delegate, then the Punishing Mediator will take actions for
every agent to lead to the desired outcome. Otherwise, it will use the agents
that did delegate to maximally punish the agents that did not delegate. The
idea behind this mediator is to incentivize all agents to delegate, at which
point the mediator implements an outcome that satisfies a social choice
criterion.

If not all agents delegate, the Punishing Mediator minimizes (perhaps
approximately) the social welfare of non-delegating agents

$\displaystyle\mathop{\mathrm{argmin}}_{s^{\prime}}$ $\displaystyle\sum_{i\in
P\setminus D}u_{i}(s^{\prime})$ (1) s.t. $\displaystyle s^{\prime}_{j}=s_{j}$
$\displaystyle\forall j\in P\setminus D.$

Otherwise if all agents delegate, the Punishing Mediator outputs the outcome
that maximizes some social welfare function. In this paper we have the social
welfare function be the sum of utilities

$\displaystyle\mathop{\mathrm{argmax}}_{s^{\prime}}$ $\displaystyle\sum_{i\in
P}u_{i}(s^{\prime}),$ (2)

but it could also be another social welfare function such as maximin.

Formally, the Punishing Mediator outputs the following joint strategy profile:

$M(s_{m})=\begin{cases}\text{Eq. }\eqref{punish}&\text{if }D\subsetneq P\\\
\text{Eq. }\eqref{nice}&\text{if }D=P.\\\ \end{cases}$

In order to incentivize every agent to delegate, the Punishing Mediator is
very harsh when not every agent delegates. In games with a large number of
agents that are learning and exploring, it can be unlikely for every agent to
choose to delegate at the same time. In this setting, the Punishing Mediator
lowers the utility of the non-delegating agents by having them punished and
may also lower the utility of the delegating agents by having them punish the
non-delegating agents. As we show in our experiments, this may cause all
agents to have very low utility, and to opt out of delegating and punishing.
In the next section, we introduce the Pareto Mediator which, instead of
forcing delegating agents to punish non-delegating agents, tries to simply
improve the delegating agents’ utility.

##  3 Pareto Mediator

The Pareto Mediator works by trying to make all the delegating agents better
off without making any of them worse off. When the Pareto Mediator receives
the joint strategy $s_{m}=(s_{i},d_{i})_{i\in P}$ of all players in the
mediated game, it first calculates for each agent $i$ the utility $u_{i}(s)$
that it would have gotten in the original game. Next, the mediator finds
mediated outcomes where every delegating agent $i\in D$ gets utility at least
$u_{i}(s)$. Of these outcomes, it picks the one that maximizes some social
welfare function for the delegating agents. As before, in this paper we use
the sum of utilities as our social welfare function, but any could be used
instead.

Formally, the Pareto Mediator solves a constrained optimization problem to
maximize social welfare for the delegating agents while ensuring that the
utility they each get is not lower than they would have if nobody delegated.
Then for a given game and joint mediated strategy $s_{m}$, if two or more
agents delegate, the Pareto Mediator returns a (possibly approximate) solution
to the following optimization problem:

$\displaystyle\mathop{\mathrm{argmax}}_{s^{\prime}}$ $\displaystyle\sum_{i\in
D}u_{i}(s^{\prime})$ (3) s.t. $\displaystyle u_{i}(s^{\prime})\geq u_{i}(s)$
$\displaystyle\forall i\in D$ $\displaystyle s^{\prime}_{j}=s_{j}$
$\displaystyle\forall j\in P\setminus D$

######  Proposition 1.

In two-player games, delegating to the Pareto Mediator is weakly dominant.

###### Proof.

Let $s_{m}=(s_{i},d_{i})_{i=1,2}$ be a joint mediated strategy where agent $i$
delegates, $d_{i}=1$, and $s^{\prime}=M(s_{m})$. Since the Pareto Mediator
only changes agent actions if two or more agents delegate, if agent $-i$ does
not delegate, $d_{-i}=0$, then $M(s_{m})=s$, and agent $i$ is indifferent
between delegating or not, $u_{i}(s_{m})=u_{i}(s)$. If agent $-i$ does
delegate, then the mediator guarantees that agent $i$ is not worse off,
$u_{i}(s_{m})\geq u_{i}(s)$. ∎

Proposition 1 implies that in two player games, under mild conditions, players
will always choose to delegate to a Pareto Mediator. Note that this property
does not hold for the Punishing Mediator. However, in games with more than two
players, not delegating may sometimes weakly dominate delegating to the Pareto
Mediator.

######  Proposition 2.

Any pure Nash equilibrium in a two-player game where both players delegate to
the Pareto Mediator has at least as high total utility as any pure Nash
equilibrium in the original game.

###### Proof.

The proof is contained in the appendix. ∎

Consider a two-player game in which the agents learn through best-response
dynamics, that is, they iteratively switch to their best strategy given the
other player’s strategy. This dynamics, if and when it converges, results in a
pure Nash equilibrium. Since delegating weakly dominates not delegating in
two-player games, Proposition 1 suggests that in this equilibrium both players
will often delegate, in which case Proposition 2 guarantees that the social
welfare will be at least as high as what the same dynamics could find in the
original game. Also, since the outcomes only change if both agents delegate,
Proposition 2 implies that all pure Nash equilibria in the mediated game have
higher total utility than the lowest utility pure Nash equilibrium in the
original game.

While both the Punishing Mediator and the Pareto Mediator have different
static properties, we argue that much more important is their performance in
non-equilibrium dynamics. Since the Punishing Mediator uses the delegating
agents to punish the non-delegating agents, overall all agents will have a
very low reward, unless all agents simultaneously decide to delegate. If that
is not the case, overall utility can be much lower than even in the original
game without a mediator. In our Pareto Mediator, instead of using delegating
agents to punish non-delegating agents, the mediator tries to improve their
social welfare. As a result, in non-equilibrium situations and in scenarios
where not everyone is delegating, the Pareto Mediator will tend to have much
higher social welfare than the Punishing Mediator.

In the next section, we provide empirical evidence, through simulations on a
number of different games, that (1) learning agents do not all delegate to the
Punishing Mediator; and (2) the social welfare induced by the Pareto Mediator
is higher than both the original game and the Punishing Mediator game.

Figure 2: In the matching game (left), agents simultaneously point to another
agent. If both agents point to each other, they both get some positive reward,
and otherwise get zero reward. In the cleanup environment (right), agents can
choose to eat apples and get a positive reward, clean the river at a cost, or
fire a beam to hurt the other player. If nobody cleans the river, apples will
stop growing.

##  4 Experiments

Agent-based simulations have long served as a tool in Game Theory for better
understanding how agents dynamically learn in games [11, 43]. While static
analysis such as finding Nash equilibria is a useful tool, equally useful is
the exercise of simulating how agents might play a particular game. In the
experiments below, we use agents that are some form of reinforcement learning
agents. The first three games are normal form games, and we use online
learners, in particular epsilon-greedy agents where epsilon is decayed by
$\frac{1}{t}$. In the third experiment, we test our approach on a sequential
social dilemma, and use independent PPO [49] agents.

###  4.1 Random Normal Form Games

Figure 3: Top: Average population reward with independent epsilon-greedy
agents on random normal form games in the original as well as Pareto and
Punishing mediated games. Bottom: Average percentage of game population agents
who choose to delegate their actions to the mediators in corresponding Pareto
and Punish games.

We create random normal form games by sampling outcome utilities independently
from a continuous $[0,1)$ Uniform distribution. We then create new games that
correspond to the mediated games from the Pareto Mediator and the Punishing
Mediator. To create these games, we exactly solve the optimization problem by
searching through all outcomes. Since these matrices grow exponentially in the
number of players, we only include results on small games. As shown in Figure
3, we find that the Punishing Mediator can achieve total utility as high as
the Pareto Mediator on random two-player, two-action games. However, as the
number of actions or the number of agents increase, the performance of the
Punishing Mediator becomes progressively worse. Interestingly, we also find
that in games with larger action spaces, a very low percentage of agents
choose to delegate actions to the Punishing Mediator.

###  4.2 Matching Game

In the matching game (Figure 2, left), every agent simultaneously picks a
partner to match with. If two agents pick each other, they get a reward.
Rewards are match-dependent and asymmetric. In these experiments, we sample
rewards from a uniform distribution. The Pareto Mediator simply matches
unmatched delegating agents with each other. The Punishing Mediator checks to
see if any delegating agent is matched with any non-delegating agent and if so
unmatches them. As shown in Figure 4, the Pareto Mediator gets much higher
reward than the Punishing Mediator and the original game. We find that
performance increases as the number of agents grows, intuitively because it
becomes harder to find a match in the original game.

###  4.3 Restaurant Reservations

In the restaurant game, as shown in Figure 1, agents can simultaneously make
reservations at restaurants on a platform. Every restaurant has a different
capacity level, and when it is exceeded each agent’s utility decreases in
proportion to the number of agents reserving at the same restaurant. Each
agent has private utilities for each restaurant, but the platform only has
access to public ratings. From these ratings, the platform builds a
recommender system and uses these predicted ratings as utilities. In this
experiment we use the Yelp Dataset [55], restricted to restaurants in
Massachusets, and we only consider agents who have given 5 or more reviews. We
then build a simple recommender system using collaborative filtering [1].

Figure 4: In the matching game, as the number of agents increases, the Pareto
Mediator achieves higher relative social welfare compared to the original game
and the Punishing Mediator.

Formally, there are players $P$, and a set of restaurants $R$. For each $r\in
R$, there is a restaurant capacity $c_{r}$. Every iteration, each agent $i$
takes an action $r_{i}$ which corresponds to picking a restaurant. Each agent
has a restaurant-specific utility $u_{i}(r)=u^{k}_{i}(r)+\alpha u^{u}_{i}(r)$
where $u^{k}_{i}(r)$ is the known reward that is available to the platform via
the recommender system and $u^{u}_{i}(r)$ is the agent-specific private
reward, which we model as drawn from an independent Uniform $[0,1)$
distribution. The number of agents that choose a restaurant is given by
$n_{r}=|\\{i\in P:r_{i}=r\\}|$. When $n_{r}\leq c_{r}$, each agent receives
their restaurant-specific utility $u_{i}(s)=u_{i}(r_{i})$. When $n_{r}>c_{r}$,
each agent receives an expected value of snagging a table:
$u_{i}(s)=\frac{c_{r_{i}}}{n_{r_{i}}}u_{i}(r_{i})$.

The Pareto Mediator works as follows. After every agent has submitted their
actions, the non-delegating actions are taken as fixed. Next, new restaurant
capacities are deduced and the Pareto Mediator approximately solves the max-
utility objective with Pareto constraints by converting it into an assignment
problem. To do so, the mediator creates a set of “tables” $T$, where each
table $t$ is a unique remaining spot at a vacant restaurant $r(t)$. To account
for the constraint that no delegating agent $i$ is worse off with a new choice
$r^{\prime}_{i}$ of restaurant instead of $r_{i}$, the Pareto Mediator creates
a new utility function $\hat{u}$ whose value $\hat{u}_{i}(r^{\prime})$ equals
$u_{i}(r^{\prime})$ if the restaurant is feasible ($u_{i}(r^{\prime})\geq
u_{i}(r_{i})$), otherwise negative infinity. The Pareto Mediator then finds a
bijection $f:D\mapsto T$ that solves the following assignment problem using a
polynomial-time assignment problem solver [9].

$\max_{f}\sum_{i\in D}\hat{u}_{i}(r(f(i))$ (4)

Note that this solution approximates the original social welfare objective,
and we conjecture that improving it is sufficient for improving the overall
performance of the Pareto Mediator.

For the Punishing Mediator, if everyone delegates, we approximately solves the
same assignment problem (4), but with $u$ instead of $\hat{u}$. If not
everyone delegates, then the Punishing Mediator sends everyone to one
restaurant that a non-delegating agent chose.

We run two sets of experiments. In the first, we set $\alpha=0$ so that the
utility given by the recommendation system is the true agent reward. We
include 300 restaurants and randomly sample restaurant capacities from $1$ to
$10$. As shown in Figure 5 (left), the Pareto Mediator achieves higher total
reward compared to the Punishing Mediator and the original game. The total
utility achieved in this regime is nearly the same as the central planning
solution, which is defined as the solution to (4) with $D=P$ (all agents
delegate). Furthermore, when we set $\alpha=2$ so that the true reward is
overshadowed by the unknown private reward (Figure 5, center), total utility
achieved by the Pareto Mediator is still higher than the original game and the
Punishing Mediator. Notably, the Pareto Mediator reward is now much higher
than the central planning solution. Since the central planner only has access
to the recommendation system rewards, it often forces agents to go to
restaurants they do not want to go to. By preserving autonomy through a
voluntary mediator, higher social welfare can be achieved.

###  4.4 Sequential Social Dilemmas

Finally, we test the effect of Pareto and Punishing mediators on independent
reinforcement learners in the sequential social dilemma game Cleanup (Figure
2, right) [54, 29, 21, 23]. In this environment, two agents operate
temporospatially in a grid-world containing apples and a river with waste in
it. Waste spawns in the river periodically and inversely affects the frequency
at which apples spawn in the world. Agents must balance the short-term gains
from consuming apples for immediate reward with long term gains of cleaning
the waist to increase the likelihood of more apples spawning. Agents are
independently optimized with PPO [49]. They receive a top-down view of the
world, can move in four directions, and must be near other objects in order to
interact with them. Agents can also fire a beam at other nearby agents to
inflict a reward penalty upon them.

In the mediated versions of this game, during the first time step, agents can
choose to delegate all further actions in the episode to the mediator, which
will act on their behalf for the rest of the episode. The Pareto Mediator uses
a joint policy that is trained to maximize cumulative reward. If one agent
delegates but not the other, both agents play their original policies. But if
both agents delegate, the mediator plays the joint pre-trained cooperative
policy. The Punishing Mediator also plays the joint pre-trained cooperative
policy if both agents delegate. But if only one delegates, the mediator plays
a punishing policy that is pre-trained to minimize the opponent’s reward.

In Figure 5 (right), we show the average and minimum reward for both players
over 100-episode windows throughout training. The Punishing Mediator achieves
similar average utility as in the original game, but achieves much lower
minimum reward than the original game. In contrast, when a Pareto Mediator
option is provided, both the average and minimum population reward is much
higher than in the original game and Punishing Mediator game. Agents playing
the Pareto Mediator game learn to delegate 100% of the time because doing so
weakly dominated not delegating. However, agents playing the Punishing
Mediator game never learn to delegate because most of the time when they
delegate, the other agent was not delegating, and both agents received low
reward by punishing or being punished.

Figure 5: Left: Total reward (top) and percentage of population delegating
(bottom) in the restaurant game with $\alpha=0$ and $\alpha=2$. Right: Total
reward (top) and minimum reward (bottom) in Cleanup.

##  5 Related Work

#### Mediators and Commitment Devices.

In economics there are many models for the design of mechanisms that maintain
individual agent autonomy. Program equalibria is a model where both players
present a program to play on their behalf, which can then react to the program
submitted by the other player, which allows for a kind of commitment device
[52]. More generally, commitment device games are a class of mechanisms which
allow the designer to introduce an arbitrary class of commitment devices for
the players to optionally access [25]. Our work builds off of a formally
similar model of mediators, developed concurrently to commitment device games
[53]. There is a broad set of literature around mediators mostly focusing on
analyzing their equalibria behavior in specific settings [41, 37, 47, 40, 46,
3]. The most closely related is [45] which proposes a general market matching
algorithm for constructing a mediator. Their construction ensures incentive
compatibility of entering the market, and shows promising results for
applications in labor markets. However, though the aim of this work is
similar, the mediator mechanism, its analysis, and the target domains are all
quite distinct.

Correlated equilibria are a closely related concept to mediators in which
agents are given the choice to follow the recommendations of a centralized
recommender [4, 15]. However, mediators are a stronger concept, as they allow
the mediator not only to recommend actions, but to direct other agents to
change their behavior based on which agents accept the recommendation,
resulting in a strictly larger class of achievable equalibria.

#### Mechanism Design and Solution Concepts.

In the economics literature, designing incentives to motivate agents to behave
in a desired fashion has long been studied in the field of mechanism design
[22]. A popular objective in that literature is to design mechanisms which
minimize the price of anarchy, which is the ratio of the worst Nash
equilibrium to the maximal social welfare achievable by the mechanism [28,
12]. The price of anarchy can be seen as a proxy for the true performance of
the mechanism when deployed with learning agents. An alternative model is to
evaluate mechanisms based on how they empirically perform with popular
learning models. Learning in games is a broad field, and while many of these
methods converge to popular equilibrium concepts in restricted settings [26,
18, 32], many natural algorithms do not converge to Nash equilibria [16]. A
construct that is often more predictive for these methods is risk dominance,
which prioritizes one equilibrium over another if its utility is less
sensitive to unpredictable behavior of other agents [19].

Related to mechanism design is the field of social choice theory, which
studies voting mechanisms which combine preferences to promote the general
welfare [2]. There has been a large body of work proving impossibility results
for social choice theory [2, 39, 48, 17]. Though our work does not explicitly
study social choice, it is closely related. For instance, using a Pareto
Mediator in the context of voting mechanisms would be a reasonable model for
delegates or representatives. Our approach avoids the impossibility results
prevalent in social choice by having no notion of “truthfully reporting your
preferences”.

#### Multi-Agent Reinforcement Learning.

Much work in multi-agent RL has focused on the setting of zero-sum games, to
great success [20, 51, 38, 7, 36, 35]. However, in general-sum games,
solutions are much less established. In the context of this work, one line of
work of particular relevance is the agenda around Cooperative AI [10]. In
broad strokes, this agenda lays out a set of problems which aim to use AI to
further coordination and cooperation both in interactions between humans and
AI and interactions between individual humans. Our work can be seen as
building in that direction by designing mechanisms to coordinate human actions
while aiming to avoid reducing human autonomy. One target domain of interest
is that of studying RL systems in sequential social dilemmas [42]. This
follows work on social dilemmas in game theory [6], aiming to understand the
effects of different strategies of promoting cooperation in sequential multi-
agent environments [14, 21, 13, 23, 34, 30, 44]. We propose our method as a
mechanism for promoting cooperation without reducing the autonomy of the
individual agents.

Our approach follows other work, using machine learning agents to better
understand the effectiveness of certain mechanisms [33, 24]. That work itself
follows in a line of work aiming to better understand the multi-agent bandit
setting more broadly [8, 50]. We believe more theoretical insights from these
directions could aid the analysis of the Pareto Mediator, though more work
would be needed to achieve bounds that are applicable in our setting.

##  6 Conclusion

In this work we argued that mediators can serve as a middle ground between
fully centralized control and anarchy. Existing mediators, such as the
Punishing Mediator, achieve low social welfare when not at equilibrium. We
propose the Pareto Mediator, which seeks to improve welfare of delegating
agents without making any worse off. Through a series of experiments we show
that the Pareto Mediator can be a simple and effective mediator with a wide
range of potential applications. Future work can extend Pareto Mediators to
the transferable utility setting. In sequential domains, adding delegating
options during the game instead of only at the beginning holds potential for
preserving higher autonomy and addressing state-dependent uncertainty of agent
utilities. Finally, the theoretical properties of the Pareto Mediator in
static settings can be better understood, in order to provide guarantees and
improved mechanisms.

## References

  * [1] C. C. Aggarwal et al.  Recommender systems, volume 1.  Springer, 2016.
  * [2] K. J. Arrow.  Social choice and individual values, volume 12.  Yale university press, 2012.
  * [3] I. Ashlagi, D. Monderer, and M. Tennenholtz.  Mediators in position auctions.  Games and Economic Behavior, 67(1):2–21, 2009.
  * [4] R. J. Aumann.  Subjectivity and correlation in randomized strategies.  Journal of Mathematical Economics, pages 67––96, 1974.
  * [5] R. J. Aumann.  Correlated equilibrium as an expression of bayesian rationality.  Econometrica: Journal of the Econometric Society, pages 1–18, 1987\.
  * [6] R. Axelrod and W. D. Hamilton.  The evolution of cooperation.  Science, 211(4489):1390–1396, 1981.
  * [7] N. Brown and T. Sandholm.  Libratus: the superhuman ai for no-limit poker.  In Proceedings of the 26th International Joint Conference on Artificial Intelligence, pages 5226–5228, 2017.
  * [8] N. Cesa-Bianchi, C. Gentile, Y. Mansour, and A. Minora.  Delay and cooperation in nonstochastic bandits.  In Conference on Learning Theory, pages 605–622. PMLR, 2016.
  * [9] D. F. Crouse.  On implementing 2d rectangular assignment algorithms.  IEEE Transactions on Aerospace and Electronic Systems, 52(4):1679–1696, 2016.
  * [10] A. Dafoe, E. Hughes, Y. Bachrach, T. Collins, K. R. McKee, J. Z. Leibo, K. Larson, and T. Graepel.  Open problems in cooperative ai.  arXiv preprint arXiv:2012.08630, 2020.
  * [11] P. Davidsson.  Agent based social simulation: A computer science view.  Journal of artificial societies and social simulation, 5(1), 2002\.
  * [12] P. Dubey and J. D. Rogawski.  Inefficiency of nash equilibria in strategic market games.  BEBR faculty working paper; no. 1104, 1985.
  * [13] T. Eccles, E. Hughes, J. Kramar, S. Wheelwright, and J. Z. Leibo.  The Imitation Game: Learned Reciprocity in Markov games.  In 18th International Conference on Autonomous Agents and Multiagent Systems, pages 1934–1936, 2019.
  * [14] J. Foerster, R. Y. Chen, M. Al-Shedivat, S. Whiteson, P. Abbeel, and I. Mordatch.  Learning with opponent-learning awareness.  Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, 1:122–130, 2018.
  * [15] D. P. Foster and R. V. Vohra.  Calibrated learning and correlated equilibrium.  Games and Economic Behavior, 21(1-2):40, 1997.
  * [16] D. Fudenberg, F. Drew, D. K. Levine, and D. K. Levine.  The theory of learning in games, volume 2.  MIT press, 1998.
  * [17] A. Gibbard.  Manipulation of voting schemes: a general result.  Econometrica: journal of the Econometric Society, pages 587–601, 1973.
  * [18] S. HARADA, E. TAKIMOTO, and A. MARUOKA.  Approximation to bayes risk in repeated play approximation to bayes risk in repeated play, 1957.  IEICE transactions on information and systems, 89(8):2340–2347, 2006.
  * [19] J. C. Harsanyi, R. Selten, et al.  A general theory of equilibrium selection in games.  MIT Press Books, 1, 1988.
  * [20] J. Heinrich, M. Lanctot, and D. Silver.  Fictitious self-play in extensive-form games.  In International conference on machine learning, pages 805–813, 2015.
  * [21] E. Hughes, J. Z. Leibo, M. Phillips, K. Tuyls, E. Dueñez-Guzman, A. G. Castañeda, I. Dunning, T. Zhu, K. McKee, R. Koster, H. Roff, and T. Graepel.  Inequity aversion improves cooperation in intertemporal social dilemmas.  Advances in Neural Information Processing Systems, pages 3326–3336, 2018.
  * [22] L. Hurwicz and S. Reiter.  Designing economic mechanisms.  Cambridge University Press, 2006.
  * [23] N. Jaques, A. Lazaridou, E. Hughes, C. Gulcehre, P. A. Ortega, D. J. Strouse, J. Z. Leibo, and N. de Freitas.  Social influence as intrinsic motivation for multi-agent deep reinforcement learning.  36th International Conference on Machine Learning, pages 5372–5381, 2019.
  * [24] R. Johari, V. Kamble, and Y. Kanoria.  Matching while learning.  Operations Research, 2021.
  * [25] A. T. Kalai, E. Kalai, E. Lehrer, and D. Samet.  A commitment folk theorem.  Games and Economic Behavior, 69(1):127–137, 2010.
  * [26] E. Kalai and E. Lehrer.  Rational learning leads to nash equilibrium.  Econometrica: Journal of the Econometric Society, pages 1019–1045, 1993.
  * [27] D. P. Kingma and J. Ba.  Adam: A method for stochastic optimization.  In Y. Bengio and Y. LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
  * [28] E. Koutsoupias and C. Papadimitriou.  Worst-case equilibria.  In Annual Symposium on Theoretical Aspects of Computer Science, pages 404–413. Springer, 1999.
  * [29] J. Z. Leibo, V. Zambaldi, M. Lanctot, J. Marecki, and T. Graepel.  Multi-agent reinforcement learning in sequential social dilemmas.  Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, pages 464 – 473, 2017.
  * [30] A. Letcher, J. Foerster, D. Balduzzi, T. Rocktäschel, and S. Whiteson.  Stable opponent shaping in differentiable games.  In International Conference on Learning Representations, 2019.
  * [31] E. Liang, R. Liaw, R. Nishihara, P. Moritz, R. Fox, K. Goldberg, J. Gonzalez, M. Jordan, and I. Stoica.  RLlib: Abstractions for distributed reinforcement learning.  In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3053–3062, Stockholmsmässan, Stockholm Sweden, 10–15 Jul 2018. PMLR.
  * [32] N. Littlestone and M. K. Warmuth.  The weighted majority algorithm.  Information and computation, 108(2):212–261, 1994.
  * [33] L. T. Liu, H. Mania, and M. Jordan.  Competing bandits in matching markets.  In International Conference on Artificial Intelligence and Statistics, pages 1618–1628. PMLR, 2020.
  * [34] S. Majumdar, S. Khadka, S. Miret, S. Mcaleer, and K. Tumer.  Evolutionary reinforcement learning for sample-efficient multiagent coordination.  In International Conference on Machine Learning, pages 6651–6660, 2020.
  * [35] S. McAleer, J. Lanier, P. Baldi, and R. Fox.  XDO: A double oracle algorithm for extensive-form games.  Reinforcement Learning in Games Workshop, AAAI, 2021.
  * [36] S. McAleer, J. Lanier, R. Fox, and P. Baldi.  Pipeline PSRO: A scalable approach for finding approximate nash equilibria in large games.  In Advances in Neural Information Processing Systems, 2020.
  * [37] D. Monderer and M. Tennenholtz.  Strong mediated equilibrium.  Artificial Intelligence, 173(1):180–195, 2009.
  * [38] M. Moravčík, M. Schmid, N. Burch, V. Lisỳ, D. Morrill, N. Bard, T. Davis, K. Waugh, M. Johanson, and M. Bowling.  Deepstack: Expert-level artificial intelligence in heads-up no-limit poker.  Science, 356(6337):508–513, 2017.
  * [39] R. B. Myerson and M. A. Satterthwaite.  Efficient mechanisms for bilateral trading.  Journal of economic theory, 29(2):265–281, 1983.
  * [40] B. Peleg and A. D. Procaccia.  Mediators enable truthful voting.  Intelligence, 8(6):5, 2007.
  * [41] B. Peleg and A. D. Procaccia.  Implementation by mediated equilibrium.  International Journal of Game Theory, 39(1-2):191–207, 2010.
  * [42] J. Perolat, J. Z. Leibo, V. Zambaldi, C. Beattie, K. Tuyls, and T. Graepel.  A multi-agent reinforcement learning model of common-pool resource appropriation.  Advances in Neural Information Processing Systems, 2017-Decem(Nips):3644–3653, 2017.
  * [43] S. F. Railsback, S. L. Lytinen, and S. K. Jackson.  Agent-based simulation platforms: Review and development recommendations.  Simulation, 82(9):609–623, 2006.
  * [44] C. Roman, M. Dennis, A. Critch, and S. Russell.  Accumulating risk capital through investing in cooperation.  In Proceedings of the 20th International Conference on Autonomous Agents and Multi Agent Systems, pages 1073–1081, 2021.
  * [45] B. N. Roth and R. I. Shorrer.  Making marketplaces safe: Dominant individual rationality and applications to market design.  Management Science, 2020.
  * [46] O. Rozenfeld and M. Tennenholtz.  Strong and correlated strong equilibria in monotone congestion games.  In International Workshop on Internet and Network Economics, pages 74–86. Springer, 2006.
  * [47] O. Rozenfeld and M. Tennenholtz.  Routing mediators.  In International Joint Conference on Artificial Intelligence, pages 1488–1493, 2007.
  * [48] M. A. Satterthwaite.  Strategy-proofness and arrow’s conditions: Existence and correspondence theorems for voting procedures and social welfare functions.  Journal of economic theory, 10(2):187–217, 1975.
  * [49] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov.  Proximal policy optimization algorithms.  CoRR, abs/1707.06347, 2017.
  * [50] S. Shahrampour, A. Rakhlin, and A. Jadbabaie.  Multi-armed bandits in multi-agent networks.  In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 2786–2790. IEEE, 2017.
  * [51] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, et al.  Mastering the game of go without human knowledge.  Nature, 550(7676):354–359, 2017.
  * [52] M. Tennenholtz.  Program equilibrium.  Games and Economic Behavior, 49(2):363–373, 2004.
  * [53] M. Tennenholtz.  Game-theoretic recommendations: some progress in an uphill battle.  In International Conference on Autonomous Agents and Multi Agent Systems, pages 10–16, 2008.
  * [54] E. Vinitsky, N. Jaques, J. Leibo, A. Castenada, and E. Hughes.  An open source implementation of sequential social dilemma games.  https://github.com/eugenevinitsky/sequential_social_dilemma_games/issues/182, 2019\.  GitHub repository.
  * [55] Yelp dataset.  https://www.yelp.com/dataset.  Accessed: 2020-04-21.

##  Appendix A Proof of Proposition 2

Proposition 2. Any pure Nash equilibrium in a two-player game where both
players delegate to the Pareto Mediator has at least as high total utility as
any pure Nash equilibrium in the original game.

###### Proof.

Let $u_{i}(a,b)$ be the utility for player $i$ in the new game when player 0
takes action $a$ and player 1 takes action $b$. Similarly, $v_{i}(a,b)$ is the
utility in the old game. To refer to an outcome for both players, we write
$u(a,b)$ or $v(a,b)$. Define $U(a,b):=\sum_{i}{u_{i}(a,b)}$ and
$V(a,b):=\sum_{i}{v_{i}(a,b)}$. If an outcome $u(a,b)$ Pareto dominates
another outcome $u(a^{\prime},b^{\prime})$ then we write that as
$u(a,b)\succeq u(a^{\prime},b^{\prime})$.

Assume we have a pure Nash in the new game where player 0 takes action $a_{0}$
and player 1 takes action $a_{1}$ and that it has lower sum of utility than a
pure Nash in the original game where player 0 takes action $b_{0}$ and player
1 takes action $b_{1}$. So $U(a_{0},a_{1})<V(b_{0},b_{1}).$

Then it can’t be the case that both $v(b_{0},b_{1})\succeq v(a_{0},b_{1})$ and
$v(b_{0},b_{1})\succeq v(b_{0},a_{1})$. To see why, if it were the case, then
$u(a_{0},b_{1})\succeq v(b_{0},b_{1})$ and $u(b_{0},a_{1})\succeq
v(b_{0},b_{1})$ by definition of how we create the new game. But
$u_{0}(a_{0},a_{1})\geq u_{0}(b_{0},a_{1})$ and $u_{1}(a_{0},a_{1})\geq
u_{1}(a_{0},b_{1})$ because $u(a_{0},a_{1})$ is a Nash in the new game. So
then $U(a_{0},a_{1})=u_{0}(a_{0},a_{1})+u_{1}(a_{0},a_{1})\geq
u_{0}(b_{0},a_{1})+u_{1}(a_{0},b_{1})\geq
v_{0}(b_{0},b_{1})+v_{1}(b_{0},b_{1})=V(b_{0},b_{1})$ which is a
contradiction.

Because one of the original "corners" isn’t Pareto dominated by the original
Nash, we can assume it is the bottom left one. Without loss of generality,
assume $v(b_{0},b_{1})\not\succeq v(b_{0},a_{1})$. We know that
$v_{1}(b_{0},a_{1})\leq v_{1}(b_{0},b_{1})$ because $v(b_{0},b_{1})$ is a
Nash. So it must be that $v_{0}(b_{0},a_{1})>v_{0}(b_{0},b_{0})$.

We know that $u_{0}(a_{0},a_{1})\geq u_{0}(b_{0},a_{1})$ and
$u_{1}(a_{0},a_{1})\geq u_{1}(a_{0},b_{1})$ because $u(a_{0},a_{1})$ is a Nash
in the new game. Suppose that $v_{1}(a_{0},b_{1})\geq v_{1}(b_{0},b_{1})$.
Then $U(a_{0},a_{1})=u_{0}(a_{0},a_{1})+u_{1}(a_{0},a_{1})\geq
u_{0}(b_{0},a_{1})+u_{1}(a_{0},b_{1})\geq
v_{0}(b_{0},a_{1})+v_{1}(a_{0},b_{1})>v_{0}(b_{0},b_{1})+v_{1}(b_{0},b_{1})=V(b_{0},b_{1})$
which is a contradiction. So it must be that
$v_{1}(a_{0},b_{1})<v_{1}(b_{0},b_{1})$.

Now since $V(b_{0},b_{1})$ is a Nash in the original game,
$v_{0}(a_{0},b_{1})\leq v_{0}(b_{0},b_{1})$. Then in the old game,
$v(b_{0},b_{1})\succeq v(a_{0},b_{1})$, so in the new game
$u(a_{0},b_{1})\succeq v(b_{0},b_{1})$. But this causes a contradiction
because then $U(a_{0},a_{1})=u_{0}(a_{0},a_{1})+u_{1}(a_{0},a_{1})\geq
u_{0}(b_{0},a_{1})+u_{1}(a_{0},b_{1})\geq
v_{0}(b_{0},a_{1})+u_{1}(a_{0},b_{1})>v_{0}(b_{0},b_{1})+v_{1}(b_{0},b_{1})=V(b_{0},b_{1})$.
∎

##  Appendix B Description of Experiments

###  B.1 Yelp Restaurant Data

In this experiment we use the Yelp Dataset [55], restricted to restaurants in
Massachusets, and we only consider agents who have given 5 or more reviews. We
then build a simple recommender system using collaborative filtering [1]. All
code and data will be released for the final version.

###  B.2 Sequential Social Dilemmas

The Pareto and Punish Mediator PPO policies used in the Cleanup Sequential
Social Dilemma game were pretrained with independent optimization for each
agent to maximize the sum of agent rewards (for Pareto) or the negative of the
other agent’s reward (for Punish).

The multiagent PPO optimization process was built on top of the RLlib
framework [31]. Each independently learning agent used a single experience
gathering worker process with a single environment.

The CNN-LSTM network model was shared between the actor and critic. The model
was comprised of one CNN layer with six 3x3 filters, stride 1 and relu
activation followed by a two fully-connected layers size of 32 with tanh
activations, then an LSTM with cell size 256, and finally two branching fully
connected layers for discrete action logits and value function outputs.

Any hyperparameters not listed below were set to the default RLlib version
0.8.5 values.

discount factor | 0.99
---|---
GAE $\lambda$ | 1.0
entropy coeff | 0.001
clip param | 0.3
KL coeff | 0.2
KL target | 0.01
value function loss coeff | 0.0001
learning rate | 0.0001
optimizer | Adam [27]
grad clip | 40
train batch size | 1000
sgd minibatch size | 250
num sgd iters on train batch | 10
LSTM unroll length | 20
Table 2: PPO hyperparameters

We used a single NVIDIA TITAN X GPU for all experiments and used 8 CPU cores.
We will release all the code for all experiments in the final version.


* [6] J. A. Backer, D. Klinkenberg, and J. Wallinga.  Incubation period of 2019 novel coronavirus (2019-nCoV) infections among travellers from Wuhan, China, 20–28 January 2020.  Eurosurveillance, 25(5), 2020.
  * [7] F. Ball.  Stochastic and deterministic models for SIS epidemics among a population partitioned into households.  Mathematical Biosciences, 156(1):41–67, 1999.
  * [8] F. Ball, T. Britton, T. House, V. Isham, D. Mollison, L. Pellis, and G. Scalia Tomba.  Seven challenges for metapopulation models of epidemics, including households models.  Epidemics, 10:63 – 67, 2015.  Challenges in Modelling Infectious Disease Dynamics.
  * [9] F. Ball, T. Britton, and D. Sirl.  Household epidemic models with varying infection response.  Journal of Mathematical Biology, 63(2):309–337, 2011.
  * [10] F. Ball, D. Mollison, and G. Scalia-Tomba.  Epidemics with two levels of mixing.  The Annals of Applied Probability.
  * [11] F. Ball, L. Pellis, and P. Trapman.  Reproduction numbers for epidemic models with households and other social structures II: Comparisons and implications for vaccination.  Mathematical Biosciences, 274:108 – 139, 2016.
  * [12] F. Ball, L. Pellis, and P. Trapman.  Reproduction numbers for epidemic models with households and other social structures II: comparisons and implications for vaccination.  Mathematical Biosciences, 274:108–139, 2016.
  * [13] F. G. Ball, E. S. Knock, and P. D. O’Neill.  Stochastic epidemic models featuring contact tracing with delays.  Mathematical Biosciences, 266:23–35, 2015.
  * [14] M. Biggerstaff, F. S. Dahlgren, J. Fitzner, D. George, A. Hammond, I. Hall, D. Haw, N. Imai, M. A. Johansson, S. Kramer, et al.  Coordinating the real-time use of global influenza activity data for better public health planning.  Influenza and Other Respiratory Viruses, 14(2):105–110, 2020.
  * [15] A. J. Black, N. Geard, J. M. McCaw, J. McVernon, and J. V. Ross.  Characterising pandemic severity and transmissibility from data collected during first few hundred studies.  Epidemics, 19:61–73, 2017.
  * [16] T. Britton and G. Scalia Tomba.  Estimation in emerging epidemics: Biases and remedies.  Journal of the Royal Society Interface, 16(150):20180670, 2019.
  * [17] D. Butler.  Models overestimate Ebola cases.  Nature, 515(7525):18, 2014.
  * [18] S. Cauchemez, F. Carrat, C. Viboud, A. J. Valleron, and P. Y. Boëlle.  A Bayesian MCMC approach to study transmission of influenza: application to household longitudinal data.  Statistics in Medicine, 23(22):3469–3487, 2004.
  * [19] S. Cauchemez, C. A. Donnelly, C. Reed, A. C. Ghani, C. Fraser, C. K. Kent, L. Finelli, and N. M. Ferguson.  New England Journal of Medicine.
  * [20] C. Chew and G. Eysenbach.  Pandemics in the age of Twitter: content analysis of Tweets during the 2009 H1N1 outbreak.  PloS One, 5(11), 2010.
  * [21] M. Chinazzi, J. T. Davis, M. Ajelli, C. Gioannini, M. Litvinova, S. Merler, A. P. y Piontti, K. Mu, L. Rossi, K. Sun, et al.  The effect of travel restrictions on the spread of the 2019 novel coronavirus (COVID-19) outbreak.  Science, 2020.
  * [22] Care Quality Commission.  CQC care directory - with ratings (1 April 2020), 2020.
  * [23] Department of Health and Social Care.  SPI-M modelling summary for pandemic influenza, Edition: Nov 2018.
  * [24] Z. Du, X. Xu, Y. Wu, L. Wang, B. J. Cowling, and L. A. Meyers.  The serial interval of COVID-19 from publicly reported confirmed cases.  medRxiv, 2020.
  * [25] L. Fang, G. Karakiulakis, and M. Roth.  Are patients with hypertension and diabetes mellitus at increased risk for COVID-19 infection?  The Lancet Respiratory Medicine, 8(4):e21, 2020.
  * [26] V. T. Farewell, A. M. Herzberg, K. W. James, L. M. Ho, and G. M. Leung.  SARS incubation and quarantine times: when is an exposed individual known to be disease free?  Statistics in Medicine, 24(22):3431–3445, 2005.
  * [27] N. M. Ferguson, D. Laydon, G. Nedjati-Gilani, N. Imai, K. Ainslie, M. Baguelin, S. Bhatia, A. Boonyasiri, Z. Cucunubá, G. Cuomo-Dannenburg, et al.  Impact of non-pharmaceutical interventions (NPIs) to reduce COVID-19 mortality and healthcare demand.
  * [28] L. Ferretti, C. Wymant, M. Kendall, L. Zhao, A. Nurtay, L. Abeler-Dörner, M. Parker, D. Bonsall, and C. Fraser.  Quantifying SARS-CoV-2 transmission suggests epidemic control with digital contact tracing.  Science, 2020.
  * [29] C. Fraser.  Estimating individual and household reproduction numbers in an emerging epidemic.  PloS One, 2(8), 2007.
  * [30] S. Funk, E. Gilad, C. Watkins, and V. A. A. Jansen.  The spread of awareness and its impact on epidemic outbreaks.  Proceedings of the National Academy of Sciences, 106(16):6872–6877, 2009.
  * [31] P. Ganyani, C. Kremer, D. Chen, A. Torneri, C. Faes, J. Wallinga, and N. Hens.  Estimating the generation interval for COVID-19 based on symptom onset data.  medRxiv, 2020.
  * [32] E. Goldstein, K. Paur, C. Fraser, E. Kenah, J. Wallinga, and M. Lipsitch.  Reproductive numbers, epidemic spread and control in a community of households.  Mathematical Biosciences, 221(1):11–25, 2009.
  * [33] K. M. Gostic, A. C. R. Gomez, R. O. Mummah, A. J. Kucharski, and J. O. Lloyd-Smith.  Estimated effectiveness of symptom and risk screening to prevent the spread of COVID-19.  eLife, 9:1–18, 2020.
  * [34] W. Guan, Z. Ni, Y. Hu, W. Liang, C. Ou, J. He, L. Liu, H. Shan, C. Lei, D. S. C. Hui, et al.  Clinical characteristics of coronavirus disease 2019 in China.  New England Journal of Medicine, 2020.
  * [35] Thomas Hale et al.  Oxford COVID-19 Government Response Tracker (OxCGRT), 2020.  https://www.bsg.ox.ac.uk/research/research-projects/oxford-covid-19-government-response-tracker.
  * [36] T. House and M. J. Keeling.  Deterministic epidemic models with explicit household structure.  Mathematical Biosciences, 213(1):29–39, 2008.
  * [37] T. House and M. J. Keeling.  Epidemic prediction and control in clustered populations.  Journal of Theoretical Biology, 272(1):1–7, 2011.
  * [38] S. Jack.  Coronavirus: GSK and Sanofi join forces to create vaccine, 2020.
  * [39] J. D. Kalbfleisch and J. F. Lawless.  Regression models for right truncated data with applications to AIDS incubation times and reporting lags.  Statistica Sinica, pages 19–32, 1991.
  * [40] W. Keju.  China braces for world’s biggest travel rush around Spring Festival, 2019.
  * [41] D. G. Kendall et al.  On the generalized “birth-and-death” process.  The Annals of Mathematical Statistics, 19(1):1–15, 1948.
  * [42] W. O. Kermack and A. G. McKendrick.  A contribution to the mathematical theory of epidemics.  Proceedings of the Royal Society of London. Series A, Containing papers of a mathematical and physical character, 115(772):700–721, 1927.
  * [43] T. Kinyanjui, J. Middleton, S. Güttel, J. Cassell, J. Ross, and T. House.  Scabies in residential care homes: Modelling, inference and interventions for well-connected population sub-units.  PLOS Computational Biology, 14(3):e1006046, 2018.
  * [44] M. U. G. Kraemer, C. Yang, B. Gutierrez, C. Wu, B. Klein, D. M. Pigott, L. du Plessis, N. R. Faria, R. Li, W. P. Hanage, et al.  The effect of human mobility and control measures on the covid-19 epidemic in china.  Science, 368(6490):493–497, 2020.
  * [45] M. S.Y. Lau, B. D. Dalziel, S. Funk, A. McClelland, A. Tiffany, S. Riley, C. J. E. Metcalf, and B. T. Grenfell.  Spatial and temporal dynamics of superspreading events in the 2014-2015 West Africa Ebola epidemic.  Proceedings of the National Academy of Sciences of the United States of America, 114(9):2337–2342, 2017.
  * [46] S. A. Lauer, K. H. Grantz, Q. Bi, F. K. Jones, Q. Zheng, H. Meredith, A. S. Azman, N. G. Reich, and J. Lessler.  The incubation period of 2019-nCoV from publicly reported confirmed cases: estimation and application.  medRxiv, 2020.
  * [47] C. R. Lesko, A. P. Keil, and J. K. Edwards.  The Epidemiologic Toolbox: Identifying, Honing, and Using the Right Tools for the Job.  American Journal of Epidemiology.
  * [48] Q. Li, X. Guan, P. Wu, X. Wang, L. Zhou, Y. Tong, R. Ren, K. S. M. Leung, E. H. Y. Lau, J. Y. Wong, et al.  Early transmission dynamics in Wuhan, China, of novel coronavirus–infected pneumonia.  New England Journal of Medicine, 2020.
  * [49] R. Li, S. Pei, B. Chen, Y. Song, T. Zhang, W. Yang, and J. Shaman.  Substantial undocumented infection facilitates the rapid dissemination of novel coronavirus (SARS-CoV2).  Science, 2020.
  * [50] H. Lin, W. Liu, H. Gao, J. Nie, and Q. Fan.  Trends in transmissibility of 2019 novel coronavirus-infected pneumonia in Wuhan and 29 provinces in China.  Available at SSRN 3544821, 2020.
  * [51] N. M. Linton, T. Kobayashi, Y. Yang, K. Hayashi, A. R. Akhmetzhanov, S. Jung, B. Yuan, R. Kinoshita, and H. Nishiura.  Incubation period and other epidemiological characteristics of 2019 novel coronavirus infections with right truncation: A statistical analysis of publicly available case data.  Journal of Clinical Medicine, 9(2):538, 2020.
  * [52] T. Liu, J. Hu, J. Xiao, G. He, M. Kang, Z. Rong, L. Lin, H. Zhong, Q. Huang, A. Deng, et al.  Time-varying transmission dynamics of novel coronavirus pneumonia in China.  bioRxiv, 2020.
  * [53] Y. Liu, A. A. Gayle, A. Wilder-Smith, and J. Rocklöv.  The reproductive number of COVID-19 is higher compared to SARS coronavirus.  Journal of Travel Medicine, 2020.
  * [54] F. M. G. Magpantay, M. A. Riolo, M. Domenech de Cellès, A. A. King, and P. Rohani.  Epidemiological Consequences of Imperfect.  SIAM Journal on Applied Mathematics, 74(6):1810–1830, 2014.
  * [55] E. Mahase.  China coronavirus: what do we know so far?  BMJ, 368, 2020.
  * [56] M. S. Majumder and K. D. Mandl.  Early in the epidemic: impact of preprints on global discourse about COVID-19 transmissibility.  The Lancet Global Health.
  * [57] K. Mizumoto, K. Kagaya, A. Zarebski, and G. Chowell.  Estimating the asymptomatic proportion of coronavirus disease 2019 (COVID-19) cases on board the Diamond Princess cruise ship, Yokohama, Japan, 2020.  Eurosurveillance, 25(10):2000180, 2020.
  * [58] H. Morris.  The largest human migration on the planet: What happens in China when 1.4bn go on holiday at the same time.  https://www.telegraph.co.uk/travel/news/chinese-new-year-chunyun-in-numbers/.
  * [59] J. Mossong, N. Hens, M. Jit, P. Beutels, K. Auranen, R. Mikolajczyk, M. Massari, S. Salmaso, G. Scalia Tomba, J. Wallinga, et al.  Social contacts and mixing patterns relevant to the spread of infectious diseases.  PLoS Medicine, 5(3), 2008.
  * [60] H. Nishiura.  Time variations in the generation time of an infectious disease: implications for sampling to appropriately quantify transmission potential.  Mathematical Biosciences & Engineering, 7(4):851–869, 2010.
  * [61] H. Nishiura, T. Kobayashi, T. Miyama, A. Suzuki, S. Jung, K. Hayashi, R. Kinoshita, Y. Yang, B. Yuan, A. R. Akhmetzhanov, et al.  Estimation of the asymptomatic ratio of novel coronavirus infections (COVID-19).  medRxiv, 2020.
  * [62] Office for National Statistics.  Families and households, Edition: 15 November 2019.  https://www.ons.gov.uk/peoplepopulationandcommunity/birthsdeathsandmarriages/families/datasets
/familiesandhouseholdsfamiliesandhouseholds.

  * [63] Office for National Statistics.  2001 census aggregate data, Edition: May 2011.
  * [64] World Health Organisation.  Coronavirus disease 2019 (COVID-19). Situation Report - 69., 2020.
  * [65] L. Pellis, F. Ball, and P. Trapman.  Reproduction numbers for epidemic models with households and other social structures. I. definition and calculation of ${R}_{0}$.  Mathematical Biosciences, 235(1):85 – 97, 2012.
  * [66] L. Pellis, S. Cauchemez, N. M. Ferguson, and C. Fraser.  Systematic selection between age and household structure for models aimed at emerging epidemic predictions.  Nature Communications, 11(1), 2020.
  * [67] L. Pellis, N. M. Ferguson, and C. Fraser.  Epidemic growth rate and household reproduction number in communities of households, schools and workplaces.  Journal of Mathematical Biology, 63(4):691–734, 2011.
  * [68] L. Pellis, F. Scarabel, H. B. Stage, C. E. Overton, L. H. K. Chappell, K. A. Lythgoe, E. Fearon, E. Bennett, J. Curran-Sebastian, R. Das, M. Fyles, H. Lewkowicz, X. Pang, B. Vekaria, L. Webb, T. House, and I. Hall.  Challenges in control of Covid-19: short doubling time and long delay to effect of interventions, 2020.
  * [69] J. M. Read, J. R. E. Bridgen, D. A. T. Cummings, A. Ho, and C. P. Jewell.  Novel coronavirus 2019-nCoV: early estimation of epidemiological parameters and epidemic predictions.  MedRxiv, 2020.
  * [70] A. Remuzzi and G. Remuzzi.  COVID-19 and italy: what next?  The Lancet, 2020.
  * [71] . Rimmer.  COVID-19: Disproportionate impact on ethnic minority healthcare workers will be explored by government.  BMJ, 369, 2020.
  * [72] J. V. Ross, T. House, and M. J. Keeling.  Calculation of disease dynamics in a population of households.  PLOS ONE, 5(3):e9666, 2010.
  * [73] R. Ross.  The Prevention of Malaria.  Dutton, 1910.
  * [74] G. J. Rubin, R. Amlôt, L. Page, and S. Wessely.  Public perceptions, anxiety, and behaviour change in relation to the swine flu outbreak: cross sectional telephone survey.  BMJ, 339:b2651, 2009.
  * [75] G. Scalia Tomba, Å. Svensson, T. Asikainen, and J. Giesecke.  Some model based considerations on observing generation times for communicable diseases.  Mathematical Biosciences, 223(1):24–31, 2010.
  * [76] T. Sellke.  On the asymptotic distribution of the size of a stochastic epidemic.  Journal of Applied Probability, 20(2):390–394, 1983.
  * [77] L. M. Shaw.  SIR epidemics in a population of households.  PhD thesis, University of Nottingham, 2016.
  * [78] Y. Su and J. Wang.  Modeling left-truncated and right-censored survival data with longitudinal covariates.  Annals of statistics, 40(3):1465, 2012.
  * [79] J. Sun.  Empirical estimation of a distribution function with truncated and doubly interval-censored data and its application to AIDS studies.  Biometrics, pages 1096–1104, 1995.
  * [80] K. Sun, J. Chen, and C. Viboud.  Early epidemiological analysis of the coronavirus disease 2019 outbreak based on crowdsourced data: a population-level observational study.  The Lancet Digital Health, 2020.
  * [81] Å. Svensson.  A note on generation times in epidemic models.  Mathematical Biosciences, 208(1):300–311, 2007.
  * [82] D. J. Taylor, M. A. Weaver, and R. E. Roddy.  Evaluating factors associated with STD infection in a study with interval-censored event times and an unknown proportion of participants not at risk for disease.  Statistics in medicine, 22(13):2191–2204, 2003.
  * [83] E. Valdano, C. Poletto, P. Boelle, and V. Colizza.  Reorganization of nurse scheduling reduces the risk of healthcare associated infections.  medRxiv, pages 1–18, 2019.
  * [84] M. D. Van Kerkhove and N. M. Ferguson.  Epidemic and intervention modelling: a scientific rationale for policy decisions? Lessons from the 2009 influenza pandemic.  Bulletin of the World Health Organization, 90:306–310, 2012.
  * [85] M. Varia, S. Wilson, S. Sarwal, A. McGeer, E. Gournis, E. Galanis, and B. H. For.  Investigation of a nosocomial outbreak of severe acute respiratory syndrome (SARS) in Toronto, Canada.  Canadian Medical Association Journal, 169(4):285–292, 2003.
  * [86] V. Virlogeux, V. J. Fang, M. Park, J. T. Wu, and B. J. Cowling.  Comparison of incubation period distribution of human infections with MERS-CoV in South Korea and Saudi Arabia.  Scientific Reports, 6(1):35839, 2016.
  * [87] A. Wilder-Smith, C. J. Chiew, and V. J. Lee.  Can we contain the COVID-19 outbreak with the same measures as for SARS?  The Lancet Infectious Diseases, 2020.
  * [88] J. T. Wu, K. Leung, M. Bushman, N. Kishore, R. Niehus, P. M. de Salazar, B. J. Cowling, M. Lipsitch, and G. M. Leung.  Estimating clinical severity of COVID-19 from the transmission dynamics in Wuhan, China.  Nature Medicine, pages 1–5, 2020.
  * [89] Z. Wu and J. M. McGoogan.  Characteristics of and important lessons from the coronavirus disease 2019 (COVID-19) outbreak in China: summary of a report of 72 314 cases from the Chinese Center for Disease Control and Prevention.  Jama, 2020.
  * [90] J. Yang, Y. Zheng, X. Gou, K. Pu, Z. Chen, Q. Guo, R. Ji, H. Wang, Y. Wang, and Y. Zhou.  Prevalence of comorbidities in the novel Wuhan coronavirus (COVID-19) infection: a systematic review and meta-analysis.  International Journal of Infectious Diseases, 2020.
  * [91] F. Zhou, T. Yu, R. Du, G. Fan, Y. Liu, Z. Liu, J. Xiang, Y. Wang, B. Song, X. Gu, et al.  Clinical course and risk factors for mortality of adult inpatients with COVID-19 in Wuhan, China: a retrospective cohort study.  The Lancet, 2020.