# Hyper Association Graph Matching with Uncertainty Quantification for
Coronary Artery Semantic Labeling

Chen Zhao1, Michele Esposito2, Zhihui Xu3, Weihua Zhou1

###### Abstract

Coronary artery disease (CAD) is one of the leading causes of death worldwide.
Accurate extraction of individual arterial branches from invasive coronary
angiograms (ICA) is critical for CAD diagnosis and detection of stenosis.
However, deep learning-based models face challenges in generating semantic
segmentation for coronary arteries due to the morphological similarity among
different types of coronary arteries. To address this challenge, we propose an
innovative approach using the hyper association graph-matching neural network
with uncertainty quantification (HAGMN-UQ) for coronary artery semantic
labeling on ICAs. The graph-matching procedure maps the arterial branches
between two individual graphs, so that the unlabeled arterial segments are
classified by the labeled segments, and the coronary artery semantic labeling
is achieved. By incorporating the anatomical structural loss and uncertainty,
our model achieved an accuracy of 0.9345 for coronary artery semantic labeling
with a fast inference speed, leading to an effective and efficient prediction
in real-time clinical decision-making scenarios.

## Introduction

Coronary artery disease (CAD) has been recognized as a primary cause of
mortality worldwide (Boden et al. 2007). Invasive coronary angiography (ICA)
remains the gold standard for CAD diagnosis (Li et al. 2015). ICAs are
instrumental to aid cardiologists in identifying blockages within the coronary
arteries. Nevertheless, it is crucial to acknowledge the limitations inherent
in this subjective visual assessment (Xian et al. 2020).

The coronary vascular tree consists of two major systems: the left coronary
artery (LCA) and the right coronary artery trees. The LCA is more clinically
relevant, as it supplies most of the blood to the left ventricle (Parikh et
al. 2012). The LCA system further bifurcates into three main coronary
arteries: the left anterior descending (LAD) artery, the left circumflex (LCX)
artery, and the left main artery (LMA). The LAD gives rise to diagonal
branches (D), while the LCX gives rise to obtuse marginal (OM) branches.
Automatically identifying the correct anatomical branches offers valuable
insights for the automatic generation of diagnosis reports and quantification
of region of interests.

Our proposed approach includes a hyper association graph-based graph-matching
network with uncertainty quantification (HAGMN-UQ) to establish semantic
correspondences between coronary arterial segments from ICAs. The semantic
segmentation problem is transformed into a task of classifying the type of an
unlabeled arterial segment by searching for the most similar labeled arterial
segment in a template set. The individual graph of the coronary artery tree is
generated based on its topology, with each node representing a segment of the
coronary artery and each edge indicating the connectivity between arterial
segments. A hyper association graph is constructed from two individual graphs,
where each vertex corresponds to two nodes in two different individual graphs,
representing the correspondence between arterial segments. This transforms the
coronary artery semantic labeling task into a vertex classification task using
the generated hyper association graph. HAGMN-UQ incorporates an encoder module
that embeds vertex and edge features using graph transformer networks, and a
decoder module that facilitates feature representation readout. By examining
the positive vertices in the association graph, indicating matched nodes from
individual graphs, HAGMN-UQ accomplishes the semantic labeling task by
assigning mapped labels to coronary arterial segments. The workflow of the
proposed HAGMN-UQ for coronary artery semantic labeling is illustrated in Fig.
1.

Figure 1: Workflow of HAGMN-UQ for coronary artery semantic labeling. Two ICAs
are selected for graph matching. The binary mask is generated by feature
pyramid U-Net++ (Zhao et al. 2021) and the semantic masks are manually
annotated and confirmed by experienced interventional cardiologists. The
centerlines and key points are extracted and the individual graphs are
generated for graph matching.

The highlights and novelty of this paper are shown below:

  * •

The utilization of graph matching for coronary artery semantic labeling using
hyper association graph.

  * •

Node attention and edge attention implemented by the graph transformer network
are employed to dynamically aggregate features for graph matching.

  * •

Structural loss characterized by the coronary anatomy and the true
classification probability loss are employed to perform a trustworthy graph
matching, reducing the processing time and improving the accuracy.

## Related works

### Coronary Artery Semantic Segmentation

Identifying individual coronary arteries in ICAs is challenging due to the
morphological similarities among different segments (Zhao et al. 2023b). The
projection of the 3D vascular tree into a 2D plane during ICA image
acquisition leads to overlaps between arteries, making it difficult to discern
intricate structures and boundaries of the coronary arteries (Zhang et al.
2022). Various deep learning-based approaches have been proposed for pixel-to-
pixel based methods, achieving impressive results in segmenting main arteries
(Xian et al. 2020; Zhang et al. 2022; Jun et al. 2020). However, these models
focus solely on main branches and may not adequately label side branches,
limiting their applicability for comprehensive CAD analysis.

Segment identification-based methods involve vascular tree binary segmentation
followed by segment classification. The developed coronary artery semantic
labeling using 3D Coronary Computed Tomography Angiography (CCTA) data
achieved satisfactory results (Cao et al. 2017; Wu et al. 2019); however, they
cannot be applied directly to 2D ICAs. Zhao et al. introduced an association
graph-based graph-matching network (Zhao et al. 2023b) and an edge attention
graph matching network (Zhao et al. 2023a) for coronary artery semantic
labeling on ICAs. These methods demonstrate the capability to label side
branches. However, a limitation lies in the slow inference speed, making it
unsuitable for real-time scenarios. This study aims to accurately label
coronary arteries and achieve real-time clinical applicability through
satisfactory performance and fast inference speed.

### Graph Matching

The objective of graph matching is to establish a meaningful correspondence
between nodes and edges across different graphs. Graph-matching poses a
challenging combinatorial optimization problem based on graph structures
(Vesselinova et al. 2020), which becomes NP-hard or practically infeasible for
large-scale scenarios.

Traditional graph-matching approaches primarily rely on combinatorial
techniques, comparing and matching structural components of graphs. In
contrast, learning-based methods take a different route by incorporating
feature extraction and affinity learning, which excel in handling large-scale
and high-dimensional data, and enable the discovery of meaningful patterns and
relationships within graphs (Khalil et al. 2017). Graph neural network (GNN)
has further enriched learning-based graph matching. GNN models structured
information and transforms the graph-matching problem into a linear assignment
task (Nowak et al. 2018; Wang, Yan, and Yang 2021, 2020).

However, the existing graph-matching algorithms have mainly been explored in
domains like nature images, and their application to medical images, with
crucial topological features, remains underexplored. Given the significance of
topological features in medical image analysis, there is a growing demand for
dedicated research to develop graph-matching algorithms tailored specifically
to medical imaging. Such algorithms should account for the intricate
interactions between structural elements and leverage the inherent knowledge
of anatomical connectivity to achieve more accurate and meaningful matching
outcomes.

### Uncertainty Quantification

Uncertainty quantification (UQ) is a crucial aspect in the optimization of the
decision-making process, as it helps mitigate the effects of uncertainties and
enhances the reliability of predictions (Abdar et al. 2021). Existing UQ
methods have found successful applications in diverse fields, including image
classification, image segmentation, and medical applications (Baumgartner et
al. 2019). However, despite its widespread application, UQ for graph matching
remains understudied. Exploring and developing UQ techniques specific to
graph-matching tasks could open new avenues for improving the accuracy and
robustness of graph-matching.

## Methodology

This study presents a novel coronary artery semantic labeling method, HAGMN-
UQ, focusing on segment identification-based approaches. HAGMN-UQ establishes
the node-to-node correspondence between individual graphs while reducing
graph-matching inference time. Each node represents a coronary arterial
segment, and HAGMN-UQ aims to build one-to-one or one-to-zero mappings for
segments in distinct vascular trees, as depicted in Fig. 1.

### Individual Graph Generation

FP-U-Net++ (Zhao et al. 2021) is employed to extract the vascular tree and
experienced cardiologists provide pixel-level semantic labels. Arterial
centerlines are extracted and key points are identified using an edge-linking
algorithm to segment the vascular tree. An individual graph is created, where
the nodes represent arterial segments and edges indicate connections. Features
from (Zhao et al. 2023b), including topology, pixel, and position features,
are used (121 features in total) for artery feature extraction.

### Hyper Graph Matching for Coronary Artery Semantic Labeling

Hypergraph is a mathematical structure that generalizes the concept of a
graph, where each edge connects multiple nodes simultaneously. Hypergraph
matching is an extension of graph matching that allows for matching vertices
and hyperedges between individual hypergraphs, exploiting the higher orders
between the nodes and edges to provide a robust matching (Wang, Yan, and Yang
2021). This study concentrates on a 3-uniform hypergraph where each hyperedge
contains three nodes and the graph matching network is performed to determine
a third-order correspondence between hypergraphs. Formally, the individual
3-uniform hypergraph represented by an attributed undirected graph is defined
as $\mathcal{G}=(\mathbb{V},\mathbb{E},\mathcal{V},\mathcal{E})$, where

  * •

$\mathbb{V}=\left\\{V_{i}\right\\}$ s.t. $i\in\\{1,\cdots,n\\}$ represents
node set, and $|\mathbb{V}|=n$

  * •

$\mathbb{E}=\left\\{E_{ijk}\right\\}$ s.t. $i,j,k\in\\{1,\cdots,n\\}$
indicates the set of hyperedges and $|\mathbb{E}|=n_{e}$.

  * •

$\mathcal{V}=\left\\{v_{i}\right\\}$ indicates the attribute vectors for each
node.

  * •

$\mathcal{E}=\left\\{e_{ijk}\right\\}$ indicates the attribute vectors
associated with each hyperedge.

A hyperedge is added when physically connected nodes $V_{i}$, $V_{j}$, and
$V_{k}$ are adjacent in hypergraphs. Thus,
$\mathbb{E}=\\{(V_{i},V_{j},V_{k})\\}=\\{E_{ijk}\\}$. Hypergraph matching
finds node correspondence between two undirected individual hypergraphs
$\mathcal{G}^{1}=(\mathbb{V}^{1},\mathbb{E}^{1},\mathcal{V}^{1},\mathcal{E}^{1})$
and
$\mathcal{G}^{2}=(\mathbb{V}^{2},\mathbb{E}^{2},\mathcal{V}^{2},\mathcal{E}^{2})$
using node-to-node and hyperedge-to-hyperedge affinities. Without loss of the
generality, it is supposed that $n_{1}\leq n_{2}$. The node-to-node
correspondence can be represented by an assignment matrix
$M\in\\{0,1\\}^{n_{1}\times n_{2}}$. To eliminate ambiguity, the node in the
individual graph is defined as a node, while the node in the association graph
is defined as a vertex. Inspired by the success of applying association graph
in combinatorial optimization (Wang, Yan, and Yang 2021), the hyper
association graph is constructed using the individual hypergraphs and the
graph matching is transformed into a vertex binary classification task, as
shown in Fig. 2.

Figure 2: Architecture of HAGMN-UQ. (a) Individual hypergraph generation; (b)
Hyper association graph generation; (c) Feature embedding; (d) Feature
representation learning; (e) Vertex classification according to the learned
feature representations.

#### Hyper association graph construction.

Formally, the hyper association graph is denoted as
$\mathcal{G}^{H}=(\mathbb{V}^{H},\mathbb{E}^{H},\mathcal{V}^{H},\mathcal{E}^{H})$,
where

  * •

$\mathbb{V}^{H}=\left\\{V_{i}^{H}\right\\}$ s.t. $i\in\\{1,\cdots,n_{1}\times
n_{2}\\}$ represents the node set, and $|\mathbb{V}^{H}|=n_{1}\times n_{2}$

  * •

$\mathbb{E}^{H}=\left\\{E_{ijk,abc}^{H}\right\\}$ s.t.
$i,j,k\in\\{1,\cdots,n_{1}\\}$ and $a,b,c\in\\{1,\cdots,n_{2}\\}$, indicating
the set of edges.

  * •

$\mathcal{V}^{H}=\left\\{v_{ia}^{H}\right\\}$ indicates the attributes for
each vertex.

  * •

$\mathcal{E}^{H}=\left\\{e_{ijk,abc}^{H}\right\\}$ are the attributes for each
hyperedge.

Each vertex $V_{i}^{H}$ in $\mathcal{G}^{H}$ combines the two nodes from the
two individual hypergraphs. Thus
$V^{H}=\\{(V_{1}^{1},V_{1}^{2}),\cdots,(V_{n_{1}}^{1},V_{n_{2}}^{2})\\}$,
where $V_{i}^{1}$ and $V_{a}^{2}$ are nodes from $\mathcal{G}^{1}$ and
$\mathcal{G}^{2}$, respectively. And each hyperedge in $\mathcal{G}^{H}$ is
derived from two hyperedges in the individual hypergraphs. If the node
$V_{i}^{1}$, $V_{j}^{1}$ and $V_{k}^{1}$ from $\mathcal{G}^{1}$ are connected,
and node $V_{a}^{2}$, $V_{b}^{2}$ and $V_{c}^{2}$ from $\mathcal{G}^{2}$ are
connected, then a hyperedge
$E_{ijk,abc}=(V_{i}^{1},V_{j}^{1},V_{k}^{1},V_{a}^{2},V_{b}^{2},V_{c}^{2})$ is
constructed in $\mathcal{G}^{H}$.

The vertex of the hyper association graph is constructed by concatenating the
nodes in the individual hypergraphs, and the feature of $v_{ia}^{H}$ is
derived by concatenating the features of $V_{i}^{1}$ and $V_{a}^{2}$, as shown
in Eq. 1.

$V_{ia}^{H}=[v_{i},v_{a}]\in\mathbb{R}^{2d}$ (1)

where $[\cdot]$ indicates concatenation. $d$ indicates the feature dimension.
Here, each node is assigned 121 handcrafted features, leading to $d=121$.

The hyperedge features in the individual graph are constructed using the
features of the included nodes, as shown in Eq. 2.

$e_{ijk}=\left[v_{i},v_{j},v_{k}\right]\in\mathbb{R}^{3d}$ (2)

Similarly, the hyperedge features in the hyper association graph are
constructed by concatenating the features of hyperedges in the individual
hypergraphs, as shown in Eq. 3.

$e_{ijk,abc}^{H}=\left[e_{ijk},e_{abc}\right]\in\mathbb{R}^{6d}$ (3)

####  $L^{1}$-Norm constraint regularization.

The core spectral hypergraph matching issue is its uniform solution (Duchenne
et al. 2011), implying challenges in obtaining a precise 0 and 1 assignment
matrix in $M$. As in Liao et al.’s hypergraph matching (Liao, Xu, and Ling
2021), we adopt row and column hyperedge constraints. Formally, the hyper
association graph is converted into
$\mathcal{G}^{H}=(\mathbb{V}^{H},\mathbb{E}^{H},\mathbb{R}^{H},\mathbb{C}^{H},\mathcal{V}^{H},\mathcal{E}^{H},\mathcal{R}^{H},\mathcal{C}^{H})$,
where $\mathbb{R}^{H}$ and $\mathbb{C}^{H}$ indicate the row and column
hyperedge; $\mathcal{R}^{H}\in\mathbb{R}^{1}$ and
$\mathcal{C}^{H}\in\mathbb{R}^{1}$ represent features of row and column
hyperedges; and they are initialized as zeros. In addition,
$\mathcal{R}^{H}=\\{r_{i}^{H}\\}$ s.t. $i\in\\{1,\cdots,n_{1}\\}$ and
$\mathcal{C}^{H}=\\{c_{j}^{H}\\}$ s.t. $j\in\\{1,\cdots,n_{2}\\}$.

#### Feature embedding.

The proposed HAGMN-UQ first performs feature representation learning using
multilayer perceptron (MLP). Formally, four MLPs are employed to perform
feature embedding, as defined in Eq. 4 to Eq. 7.

$v_{ia}^{emb}=f_{v}^{emb}\left(v_{ia}^{H}\right)$ (4)

$e_{ijk,abc}^{emb}=f_{e}^{emb}\left(e_{ijk,abc}^{H}\right)$ (5)

$r_{i}^{emb}=f_{r}^{emb}\left(r_{i}^{H}\right)$ (6)

$c_{j}^{emb}=f_{c}^{emb}\left(c_{j}^{H}\right)$ (7)

where $f_{v}^{emb}$, $f_{e}^{emb}$, $f_{r}^{emb}$ and $f_{c}^{emb}$ are MLPs
for vertex, hyperedges, row and column regularization embeddings,
respectively.

#### Hyperedge graph convolution using graph transformer.

After performing feature representation learning, the graph transformer
(Dwivedi and Bresson 2020) is employed to update the edge feature first. The
core idea of graph convolution networks (GCN) lies in performing graph
convolutions by equally pooling information from neighboring nodes and edges.
However, for topology-based medical image semantic labeling, distinct artery
types contribute uniquely to the central artery segment. Employing the self-
attention mechanism from the Transformer (Vaswani et al. 2017), the graph
transformer processes nodes and edges, capturing inter-element dependencies
and enabling dynamic neighbor integration for graph-level computations.

The edge graph transformer (EGT) is employed to aggregate features, where the
hyperedge-embedded features serve as queries, while vertex-embedded features
act as keys and values for attention. The calculated attention weights and the
vertex attention values for EGT are shown in Eqs. 8 and 9.

$w_{ijk,abc}^{E}=\sigma\left(a_{e}^{Q}\left(e_{ijk,abc}^{emb}\right)\cdot\sum_{\forall
V_{ml}}\frac{a_{e}^{K}\left(v_{ml}^{emb}\right)}{\left|N_{v}(E_{ijk,abc})\right|}\right)$
(8)

$att_{ijk,abc}^{E}=w_{ijk,abc}^{E}\cdot\sum_{\forall
V_{ml}}\frac{a_{e}^{V}\left(v_{ml}^{emb}\right)}{\left|N_{v}\left(E_{ijk,abc}\right)\right|}$
(9)

where $\sigma$ denotes softmax classification; $a_{e}^{Q}$, $a_{e}^{K}$ and
$a_{e}^{V}$ are MLPs for multi-head attention; $a_{e}^{Q}(e_{ijk,abc}^{emb})$,
$a_{e}^{K}(v_{ia}^{emb})$ and $a_{e}^{V}(v_{ia}^{emb})$ are the queries, keys
and values for edge feature attention, respectively.
$N_{v}\left(E_{ijk,abc}\right)$ represents the set of the connected vertices
for hyperedge $E_{ijk,abc}$ in $\mathcal{G}^{H}$ and
$|N_{v}\left(E_{ijk,abc}\right)|$ is the number of vertices in the set. In
other words, $V_{ml}\in N_{v}\left(E_{ijk,abc}\right)$. Then, the features of
hyperedges are updated in Eq. 10.

$e_{ijk,abc}^{gcn}=g_{e}^{gcn}\left(\left[e_{ijk,abc}^{emb},att_{ijk,abc}^{E}\right]\right)$
(10)

where $g_{e}^{gcn}$ is an MLP.

Then, the vertex features are updated using a vertex graph transformer (VGT),
which dynamically integrates the features of the connected hyperedges of the
vertex. The embedded features of vertices serve as queries, and the features
of hyperedges act as keys and values. Formally, the calculated attention
weights and edge attention values for VGT are shown in Eqs. 11 and 12.

$w_{ia}^{V}=\sigma\left(a_{v}^{Q}\left(v_{ia}^{emb}\right)\cdot\sum_{\forall
E_{nml,n^{\prime}m^{\prime}l^{\prime}}}\frac{a_{v}^{K}\left(e_{nml,n^{\prime}m^{\prime}l^{\prime}}^{gcn}\right)}{\left|N_{e}\left(V_{ia}\right)\right|}\right)$
(11)

$att_{ia}^{V}=w_{ia}^{V}\cdot\sum_{\forall
E_{nml,n^{\prime}m^{\prime}l^{\prime}}}\frac{a_{v}^{V}\left(e_{nml,n^{\prime}m^{\prime}l^{\prime}}^{gcn}\right)}{\left|N_{e}\left(V_{ia}\right)\right|}$
(12)

where $a_{v}^{Q}$, $a_{v}^{K}$ and $a_{v}^{V}$ are MLPs for multi-head
attention; $N_{e}(V_{ia})$ represents the set of connected hyperedges for
vertex $V_{ia}$ in $\mathcal{G}^{H}$ and $|N_{e}(V_{ia})|$ is the number of
hyperedges in the set. Similarly, $E_{nml,n^{\prime}m^{\prime}l^{\prime}}\in
N_{e}\left(V_{ia}\right)$. Then, the features for vertices are updated
according to Eq. 13.

$v_{ia}^{gcn}=g_{v}^{gcn}\left(\left[v_{ia}^{emb},att_{ia}^{V}\right]\right)$
(13)

For the row and column regularization terms, the plain GCN is employed to
update the features in Eqs. 14 and 15.

$r_{i}^{gcn}=g_{r}^{emb}\left(\left[r_{i}^{emb},\sum_{j}^{n_{2}}\frac{v_{ij}^{gcn}}{n_{2}}\right]\right)$
(14)

$c_{j}^{gcn}=g_{c}^{emb}\left(\left[c_{j}^{emb},\sum_{i}^{n_{1}}\frac{v_{ij}^{gcn}}{n_{1}}\right]\right)$
(15)

#### Iterative Graph Convolution.

Graph convolution iterates on the embedded hyper association graph for
$N_{mp}$ rounds. This repetition enhances information flow and captures
higher-order dependencies. Such iteration fosters a deeper and more nuanced
comprehension of graph-structured data, leading to improved performance in
graph matching.

#### Decoder and Classification.

A decoder layer is employed to transform the embedded vertex features in Eq.
13 into classification probabilities with a Softmax classifier. Formally, the
decoder layer is represented by an MLP and the predicted vertex class is shown
in Eq. 16.

$\hat{y}_{ia}=\sigma(f_{v}^{dec}(v_{ia}^{gcn}))$ (16)

where $\hat{y}_{ia}\in\mathbb{R}^{2}$ indicates the one-hot encoded
probability that the vertex $V_{i}$ in $\mathcal{G}^{1}$ matches the vertex
$V_{a}$ in $\mathcal{G}^{2}$. $f_{v}^{dec}$ is the decoder implemented by
MLPs.

#### Optimization.

The node-to-node correspondence between the vertex classification results and
the ground truth is used to optimize the model. The ground truth and
classification results are denoted as two permutation matrices
$M\in\mathbb{R}^{n_{1}\times n_{2}}$ and $\hat{M}\in\mathbb{R}^{n_{1}\times
n_{2}}$, where the element $M_{ia}$ indicates the relationship between node
$V_{i}^{1}\in G^{1}$ and node $V_{a}^{2}\in G^{2}$, and
$\hat{M}_{ia}=\text{argmax}\hat{y}_{ia}$. The permutation loss (Wang, Yan, and
Yang 2021), computed by cross-entropy between predicted vertex class and
ground truth, serves as the objective function, as shown in Eq. 17.

$\mathcal{L}_{perm}=-\sum_{i=1}^{n_{1}}\sum_{a=1}^{n_{2}}\left(1-\hat{M}_{ia}\right)\log\left(1-M_{ia}\right)+\hat{M}_{ia}\log
M_{ia}$ (17)

To explicitly reflect the confidence of the graph-matching and further
accelerate the inference procedure, the true class probability (TCP) (Corbière
et al. 2019) is employed to quantify the classification confidence. TCP uses
the softmax output probability corresponding to the real label as confidence.
Formally, TCP for vertex $V_{ia}^{H}$ is defined in Eq. 18.

$TCP^{ia}=M_{ia}\cdot\hat{y}_{ia}^{M_{ia}}$ (18)

where $\hat{y}_{ia}^{M_{ia}}$ indicates $M_{ia}$-th element of $\hat{y}_{ia}$.
A confidence neural network implemented using MLP is introduced to approximate
$TCP^{ia}$, which is denoted as $f_{v}^{c}$. The approximated TCP is defined
in Eq. 19.

$\widehat{TCP}^{ia}=f_{v}^{c}(f_{v}^{dec}(v_{ia}^{gcn}))$ (19)

The confidence loss is defined as the mean squared error between the TCP and
the approximated TCP in Eq. 20. And the overall loss function is defined in
Eq. 21.

$\mathcal{L}_{TCP}=\sum_{i=1}^{n_{1}}\sum_{a=1}^{n_{2}}(\widehat{TCP}^{ia}-TCP^{ia})^{2}$
(20)

$\mathcal{L}=\mathcal{L}_{perm}+\alpha\mathcal{L}_{TCP}$ (21)

where $\alpha$ is a hyperparameter balancing the weights between the graph
matching loss and the confidence loss.

### Training and Testing

The dataset is split into three subsets, including $D_{tr}$ for training,
$D_{te}$ for testing, and $D_{tp}$ for the template set. Experienced
cardiologists labeled each arterial segment. By leveraging the labeled data,
the node correspondences between arterial segments are automatically
identified, and a ground truth permutation matrix $M$ is generated. The pairs
of individual graphs from $D_{tr}$ are chosen, and a hyper association graph
is generated based on these selected pairs to train the HAGMN-UQ using Eq. 21.
It is noted that ICAs are chosen from the same view angle due to variations in
the anatomy and visual characteristics of the coronary arteries between these
specific view angles.

During the testing, $\mathcal{G}^{1}$ represents the tested ICA from $D_{te}$,
and $\mathcal{G}^{2}$ is the template ICA from $D_{tp}$. The hyper association
graph is constructed and the permutation matrix $\hat{M}$ is calculated. The
Hungarian algorithm (Kuhn 1955) is further applied to discretize $\hat{M}$ and
an assignment matrix is generated.

The previously developed graph matching-based methods for coronary artery
semantic labeling (Zhao et al. 2023b, a) are limited by the relatively slow
prediction during the testing, as each tested ICA in $D_{te}$ is compared with
every ICA in $D_{tp}$. In this paper, a structural loss characterized by the
coronary artery anatomy and the approximated TCP in Eq. 19 are employed to
perform UQ so that reduces the number of the compared graphs and accelerates
the inference speed.

Structural Loss. In the coronary artery system, the coronary arteries follow
strict topology based on cardiovascular anatomy. For example, the first parts
of LCX and LAD are connected to LMA, the side D branches are connected to LAD
and the side OM branches are connected to LCX. If the predicted arterial
labels don’t follow the anatomy, a weighted penalty is applied to the graph-
matching results. We designed a look-up table that stores the physical
connectivity between the arterial branches. If the connected arteries of the
predicted artery are identical to the arterial branches in the look-up table,
then the prediction is confident. In contrast, if not all the connected
branches of the predicted artery are identical to the arteries in the look-up
table, we calculated the percentage of the error connections as the weight to
penalize the prediction. Formally, the penalty weight is denoted as
$T_{e}^{i}$ for $i$-th node in the tested ICA.

Test using TCP. The error weight in structural loss is multiplied by
approximated TCP in Eq. 19 as the adjusted confidence, denoted as
$T_{e}^{i}\cdot\widehat{TCP}^{i}$. If the adjusted confidence is greater than
the confidence threshold, $T_{c}$, then we accept this prediction. If each
node in the tested ICA has a confident match, the testing procedure is
terminated. The remaining ICAs in the $D_{tp}$ are no longer needed, reducing
the number of the compared ICAs and accelerating the graph matching during the
inference.

Algorithm 1 Testing process of our proposed HAGMN-UQ.

Input:
$\mathcal{G}_{te}$: Tested individual graph with $n_{1}$ nodes
$D_{tp}=\\{\mathcal{G}_{tp}^{1},\cdots\mathcal{G}_{tp}^{N_{tp}}\\}$: Template
set
$T_{c}$: confidence threshold
Output: Labels for nodes in $\mathcal{G}_{1}$.

1: $A=\\{False,\cdots,False\\}$ with $n_{1}$ elements.

2: for $i\in\\{1,\cdots,N_{tp}\\}$ do

3: if $\mathcal{G}_{te}$ and $\mathcal{G}_{tp^{i}}$ are from the same view
angle then

4: Construct hyper association graph $\mathcal{G}^{H}$.

5: Calculate assignment matrix $\hat{M}$ by HAGMN-UQ.

6: Discretize $\hat{M}$ by Hungarian algorithm.

7: for $j\in\\{1,\cdots,n_{1}\\}$ do

8: if No structural loss presented in $V_{j}$ then

9: $A_{j}=True$

10: end if

11: end for

12: if $\forall a\in A$ is True then

13: break. # Terminate graph matching

14: else

15: for $j\in\\{1,\cdots,n_{1}\\}$ do

16: if $T_{e}^{j}\cdot\widehat{TCP}^{j}\geq T_{c}$ and $A_{j}=False$ then

17: $A_{j}=True$

18: end if

19: end for

20: end if

21: end if

22: end for

23: return Labels for nodes in $\mathcal{G}_{1}$.

The designed algorithm for testing using our HAGMN-UQ with confidence loss is
shown in Algorithm 1. The template graphs in $D_{tp}$ are sequentially
selected for graph matching with $\mathcal{G}_{te}$. Each element in the
boolean vector $A$ defined in Line 1 indicates whether the node in
$\mathcal{G}_{te}$ has been matched with high confidence. During the testing,
if the node $V_{j}\in\mathcal{G}_{te}$ has no structural loss, then we accept
the prediction, as shown in Lines 7. For the node with structural loss, the
approximated TCP multiplied by the weights of the structure loss is used to
determine if the prediction is confident, as shown in Lines 15 to 19. If all
nodes have been assigned a confidence label, then the testing is terminated.
Otherwise, the next graph in $D_{tp}$ is selected for graph matching with
$\mathcal{G}_{te}$, as the for loop in Line 2.

### Evaluation

The coronary artery semantic labeling problem is converted into a multi-class
classification problem among arterial segments. The accuracy (ACC), macro
precision (PREC), macro recall (REC), and macro F1-score (F1) are used to
evaluate the model performance.

## Experiments

### Dataset

In this study, 263 and 455 ICAs from Site 1 and Site 2 are enrolled,
respectively. All the images were resized into $512\times 512$. Table 1 shows
the number of images in each view angle.

### Implementation details

We implemented the proposed HAGMN-UQ using TensorFlow 2 and the grid search
was performed to fine-tune the optimal hyperparameters. The MLPs in Eq. 4 to
Eq. 16 were set as 2 with 64 neurons with a ReLU activation function. The
number of graph convolution, $N_{mp}$, was set as 2. The $\alpha$ in Eq. 21
was set as 0.1. The UQ threshold, $T_{c}$, was set as 0.4. An Adam optimizer
with a learning rate of $0.0001$ was employed to train the HAGMN-UQ.

Site | View angle | LAO | RAO | AP | TOTAL
---|---|---|---|---|---
Site 1 | CRA | 42 | 19 | 18 | 79
Site 1 | CAU | 18 | 116 | 56 | 190
Site 2 | CRA | 44 | 16 | 123 | 183
Site 2 | CAU | 20 | 220 | 26 | 266
Total | CAU | 124 | 371 | 223 | 718
Table 1: View angles and number of enrolled subjects

### Coronary Artery Semantic Labeling Performance

10% of the ICAs were randomly selected as $D_{tp}$ and the rest ICAs were used
for 5-fold cross-validation. The performance on the five-folds was reported in
Table 2. As illustrated in Table 2, the proposed HAGMN-UQ achieved an ACC Of
0.9345, indicating 93.45% of the arterial segments were correctly classified
during the testing.

Artery Type | ACC | PREC | REC | F1
---|---|---|---|---
LMA | .9960 | .9979 | .9960 | .9969
LAD | .9550 | .9517 | .9556 | .9536
LCX | .9210 | .9250 | .9217 | .9234
D | .9350 | .9313 | .9361 | .9337
OM | .8830 | .8890 | .8841 | .8865
weighted avg | .9345 | .9390 | .9387 | .9389
Table 2: Achieved performance for coronary artery semantic labeling using
HAGMN-UQ

We also compared the performance of the proposed HAGMN-UQ with the existing
segment-based coronary artery semantic labeling and other graph-matching
methods, including

  * •

BiTL (Cao et al. 2017): The bidirectional tree LSTM (BiTL) is initially
applied for coronary artery semantic labeling using CCTA. We adopted the same
network architecture but extracted the spatial locations and directions of
coronary arteries in 2D.

  * •

IPCA (Wang, Yan, and Yang 2020). Iterative Permutation Cross-graph Affinity
(IPCA) is designed for graph matching by comparing node features between
individual graphs iteratively with cross-graph feature embedding.

  * •

NGM (Wang, Yan, and Yang 2021). The neural graph-matching network (NGM)
employs the association graph-induced affinity matrix for graph matching.

  * •

AGMN (Zhao et al. 2023b): association graph-based graph matching network is
developed for coronary artery semantic labeling based on association graph
using ICAs.

  * •

EAGMN (Zhao et al. 2023a): edge attention graph-based graph matching network
is an extension of AGMN by adding the edge attention mechanism.

For each baseline, we performed the 5-fold cross-validation using the enrolled
718 ICAs. For the graph matching-based networks, we also split the enrolled
subjects into a $D_{tr}$, $D_{te}$ and $D_{tp}$. However, during the testing,
each tested ICA was compared with every ICA in $D_{tp}$. The performance
comparisons are shown in Table 3.

Model | LMA | LAD | LCX | D | OM | ACC
---|---|---|---|---|---|---
BiTL | .600 | .938 | .677 | .739 | .532 | .7291
AGMN | .990 | .873 | .864 | .832 | .808 | .8639
EAGMN | .994 | .893 | .884 | .851 | .796 | .8767
IPCA | .998 | .911 | .894 | .896 | .839 | .9003
NGM | .988 | .922 | .896 | .900 | .840 | .9039
ours | .996 | .955 | .921 | .935 | .883 | .9345
Table 3: Comparison of coronary artery semantic labeling between different
models in ACC.

Table 3 displays that HAGMN-UQ achieved the highest accuracy of 0.9345 for
coronary artery semantic labeling. BiTL, originally designed for 3D CCTA
datasets, is unsuitable for ICAs, underlining the challenge of labeling
coronary arteries from 2D images. For the graph matching-based methods, IPCA
first performs feature embedding using individual graphs, and then performs
cross-graph feature embeddings using GCNs. Compared to association graph-based
graph matching algorithms, individual graph-based matching methods are
computationally efficient and suitable for simpler graphs but may struggle
with complex graph structures. NGM first embeds features of nodes of the
individual graphs to calculate the affinity matrix and uses the calculated
affinity matrix as the adjacency matrix for the association graph. Then, NGM
performs the feature embedding according to the node features for vertex
classification.

On the contrary, AGMN, EAGMN and HAGMN-UQ concatenate the node features of the
individual graphs and perform the vertex embedding using the concatenated
features. The adjacency matrix of the association graph is generated by the
connectivity of the individual graphs rather than the affinity matrix used by
NGM. HAGMN-UQ also incorporates high-order edge affinity using hyperedges.
Experimental results indicate that the anatomical connections between
different arterial segments and high-order affinity provides valuable cues and
constraints that guide the matching process. It helps ensure that the matched
arterial segments are not only similar in appearance or position but also
consistent with the underlying anatomical structure. HAGMN-UQ achieved the
highest performance with an ACC of 0.9345 for all types of artery labeling,
indicating the superiority of the usage of hypergraph and uncertainty
quantification for graph matching.

### Computation Complexity

For model complexity evaluation, we compared inference time, weight count,
averaged compared graphs count during inference, and total required Floating-
Point Operations (FLOPs) in Table 4. All tests were performed on an RTX 3090
workstation.

Model | Time | # Weights | # GM | FLOPs
---|---|---|---|---
BiTL | .016 | 25.793K | 1.000 | 129.0K
AGMN | .551 | 296.612K | 17.744 | 16.9M
EAGMN | .659 | 301.380K | 17.744 | 13.5M
IPCA | .202 | 40.512K | 17.744 | 904.9M
NGM | .295 | 66.181K | 17.744 | 2501.9M
ours | .102 | 234.033K | 1.085 | 432.9M
Table 4: Comparison of the computation complexity. The inference time (in
seconds), number of weights, averaged number of compared graphs for each
tested graph, and the required total FLOPs are presented.

In HAGMN-UQ, the averaged compared individual graphs in $D_{tp}$ was 1.085
during testing until filling the assignment vector in Line 1 of Algorithm 1,
substantially reducing prediction time. Conversely, in other graph-matching-
based algorithms (e.g., AGMN, EAGMN, NGM, IPCA), all individual graphs in
$D_{tp}$ are utilized for graph matching, and final predictions are obtained
through majority voting. As a result, the computation complexity of the
proposed HAGMN-UQ was significantly reduced, signifying the enhancement of
decision-making confidence through UQ incorporation in graph matching. This,
in turn, results in efficient predictions in clinical decision-making
scenarios, rendering graph matching for coronary artery semantic labeling more
feasible for real-time clinical applications. IPCA, NGM, and HAGMN-UQ all
outperformed BiTL, AGMN, and EAGMN, with HAGMN-UQ requiring 432.9M FLOPs,
which was lower than the demands of IPCA and NGM. The average inference time
per image stood at 0.102 seconds, affirming its practicability in clinical
settings.

### Ablation Study

The proposed HAGMN-UQ for coronary artery semantic labeling includes three
major modules, EGT, VGT and UQ. To verify the effectiveness of the designed
modules and the proposed testing algorithm, we built the models with and
without using EGT and VGT, and performed the graph matching with and without
using UQ. The results of the ablation study are shown in Table 5.

VGT | EGT | UQ | ACC | PREC | REC | F1
---|---|---|---|---|---|---
|  |  | .9070 | .9123 | .9123 | .9121
|  | ✓ | .9245 | .9292 | .9295 | .9293
| ✓ |  | .9068 | .9110 | .9103 | .9104
| ✓ | ✓ | .9274 | .9321 | .9322 | .9321
✓ |  |  | .8991 | .9046 | .9041 | .9040
✓ |  | ✓ | .9253 | .9300 | .9300 | .9300
✓ | ✓ |  | .9123 | .9164 | .9159 | .9158
✓ | ✓ | ✓ | .9345 | .9390 | .9387 | .9389
Table 5: Ablation results of the employment of EGT, VGT and UQ.

According to Table 5, integrating VGT and EGT simultaneously improved the
model’s performance in ACC. Additionally, incorporating the UQ strategy
proposed in Algorithm 1 significantly enhanced the ACC by 2.22 % (from 0.9123
to 0.9345). For each baseline model, using the UQ strategy improved the
performance by approximately 2% in ACC. These results indicate that VGT and
EGT work effectively together, and the incorporation of UQ is crucial in
making final decisions.

## Conclusion

In this paper, we present the development and validation of a novel algorithm
for coronary artery semantic labeling in ICAs, which exhibits both high
accuracy and fast inference speed. The results obtained from our research
showcase the promise of our HAGMN-UQ algorithm in computer-aided image
analysis for interventional cardiology.

## References

  * Abdar et al. (2021) Abdar, M.; Pourpanah, F.; Hussain, S.; Rezazadegan, D.; Liu, L.; Ghavamzadeh, M.; Fieguth, P.; Cao, X.; Khosravi, A.; Acharya, U. R.; et al. 2021.  A review of uncertainty quantification in deep learning: Techniques, applications and challenges.  _Information fusion_ , 76: 243–297.
  * Baumgartner et al. (2019) Baumgartner, C. F.; Tezcan, K. C.; Chaitanya, K.; Hötker, A. M.; Muehlematter, U. J.; Schawkat, K.; Becker, A. S.; Donati, O.; and Konukoglu, E. 2019.  Phiseg: Capturing uncertainty in medical image segmentation.  In _Medical Image Computing and Computer Assisted Intervention–MICCAI 2019: 22nd International Conference, Shenzhen, China, October 13–17, 2019, Proceedings, Part II 22_ , 119–127. Springer.
  * Boden et al. (2007) Boden, W. E.; O’Rourke, R. A.; Teo, K. K.; Hartigan, P. M.; Maron, D. J.; Kostuk, W. J.; Knudtson, M.; Dada, M.; Casperson, P.; Harris, C. L.; et al. 2007\.  Optimal medical therapy with or without PCI for stable coronary disease.  _New England journal of medicine_ , 356(15): 1503–1516.
  * Cao et al. (2017) Cao, Q.; Broersen, A.; de Graaf, M. A.; Kitslaar, P. H.; Yang, G.; Scholte, A. J.; Lelieveldt, B. P.; Reiber, J. H.; and Dijkstra, J. 2017.  Automatic identification of coronary tree anatomy in coronary computed tomography angiography.  _The international journal of cardiovascular imaging_ , 33: 1809–1819.
  * Corbière et al. (2019) Corbière, C.; Thome, N.; Bar-Hen, A.; Cord, M.; and Pérez, P. 2019.  Addressing failure prediction by learning model confidence.  _Advances in Neural Information Processing Systems_ , 32.
  * Duchenne et al. (2011) Duchenne, O.; Bach, F.; Kweon, I.-S.; and Ponce, J. 2011.  A tensor-based algorithm for high-order graph matching.  _IEEE transactions on pattern analysis and machine intelligence_ , 33(12): 2383–2395.
  * Dwivedi and Bresson (2020) Dwivedi, V. P.; and Bresson, X. 2020.  A generalization of transformer networks to graphs.  _arXiv preprint arXiv:2012.09699_.
  * Jun et al. (2020) Jun, T. J.; Kweon, J.; Kim, Y.-H.; and Kim, D. 2020.  T-net: Nested encoder–decoder architecture for the main vessel segmentation in coronary angiography.  _Neural Networks_ , 128: 216–233.
  * Khalil et al. (2017) Khalil, E.; Dai, H.; Zhang, Y.; Dilkina, B.; and Song, L. 2017.  Learning combinatorial optimization algorithms over graphs.  _Advances in neural information processing systems_ , 30.
  * Kuhn (1955) Kuhn, H. W. 1955.  The Hungarian method for the assignment problem.  _Naval research logistics quarterly_ , 2(1-2): 83–97.
  * Li et al. (2015) Li, Z.; Zhang, Y.; Liu, G.; Shao, H.; Li, W.; and Tang, X. 2015.  A robust coronary artery identification and centerline extraction method in angiographies.  _Biomedical Signal Processing and Control_ , 16: 1–8.
  * Liao, Xu, and Ling (2021) Liao, X.; Xu, Y.; and Ling, H. 2021.  Hypergraph neural networks for hypergraph matching.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 1266–1275.
  * Nowak et al. (2018) Nowak, A.; Villar, S.; Bandeira, A. S.; and Bruna, J. 2018.  Revised note on learning quadratic assignment with graph neural networks.  In _2018 IEEE Data Science Workshop (DSW)_ , 1–5. IEEE.
  * Parikh et al. (2012) Parikh, N. I.; Honeycutt, E. F.; Roe, M. T.; Neely, M.; Rosenthal, E. J.; Mittleman, M. A.; Carrozza Jr, J. P.; and Ho, K. K. 2012.  Left and codominant coronary artery circulations are associated with higher in-hospital mortality among patients undergoing percutaneous coronary intervention for acute coronary syndromes: report From the National Cardiovascular Database Cath Percutaneous Coronary Intervention (CathPCI) Registry.  _Circulation: Cardiovascular Quality and Outcomes_ , 5(6): 775–782.
  * Vaswani et al. (2017) Vaswani, A.; Shazeer, N.; Parmar, N.; Uszkoreit, J.; Jones, L.; Gomez, A. N.; Kaiser, Ł.; and Polosukhin, I. 2017.  Attention is all you need.  _Advances in neural information processing systems_ , 30.
  * Vesselinova et al. (2020) Vesselinova, N.; Steinert, R.; Perez-Ramirez, D. F.; and Boman, M. 2020.  Learning combinatorial optimization on graphs: A survey with applications to networking.  _IEEE Access_ , 8: 120388–120416.
  * Wang, Yan, and Yang (2020) Wang, R.; Yan, J.; and Yang, X. 2020.  Combinatorial learning of robust deep graph matching: an embedding based approach.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_.
  * Wang, Yan, and Yang (2021) Wang, R.; Yan, J.; and Yang, X. 2021.  Neural graph matching network: Learning lawler’s quadratic assignment problem with extension to hypergraph and multiple-graph matching.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 44(9): 5261–5279.
  * Wu et al. (2019) Wu, D.; Wang, X.; Bai, J.; Xu, X.; Ouyang, B.; Li, Y.; Zhang, H.; Song, Q.; Cao, K.; and Yin, Y. 2019.  Automated anatomical labeling of coronary arteries via bidirectional tree LSTMs.  _International journal of computer assisted radiology and surgery_ , 14: 271–280.
  * Xian et al. (2020) Xian, Z.; Wang, X.; Yan, S.; Yang, D.; Chen, J.; and Peng, C. 2020.  Main coronary vessel segmentation using deep learning in smart medical.  _Mathematical Problems in Engineering_ , 2020: 1–9.
  * Zhang et al. (2022) Zhang, H.; Gao, Z.; Zhang, D.; Hau, W. K.; and Zhang, H. 2022.  Progressive perception learning for main coronary segmentation in X-ray angiography.  _IEEE Transactions on Medical Imaging_ , 42(3): 864–879.
  * Zhao et al. (2021) Zhao, C.; Vij, A.; Malhotra, S.; Tang, J.; Tang, H.; Pienta, D.; Xu, Z.; and Zhou, W. 2021.  Automatic extraction and stenosis evaluation of coronary arteries in invasive coronary angiograms.  _Computers in biology and medicine_ , 136: 104667.
  * Zhao et al. (2023a) Zhao, C.; Xu, Z.; Hung, G.-U.; and Zhou, W. 2023a.  Coronary Artery Semantic Labeling using Edge Attention Graph Matching Network.  _arXiv preprint arXiv:2305.12327_.
  * Zhao et al. (2023b) Zhao, C.; Xu, Z.; Jiang, J.; Esposito, M.; Pienta, D.; Hung, G.-U.; and Zhou, W. 2023b.  AGMN: Association graph-based graph matching network for coronary artery semantic labeling on invasive coronary angiograms.  _Pattern Recognition_ , 143: 109789.


Adaptive Mechanism Design: Learning to Promote Cooperation

Tobias Baumann Thore Graepel John Shawe-Taylor University College London, UK, email<EMAIL_ADDRESS>
In the future, artificial learning agents are likely to become increasingly widespread in our society. They will interact with both other learning agents and humans in a variety of complex settings including social dilemmas. We consider the problem of how an external agent can promote cooperation between artificial learners by distributing additional rewards and punishments based on observing the learners' actions.
We propose a rule for automatically learning how to create the right incentives by considering the players' anticipated parameter updates. Using this learning rule leads to cooperation with high social welfare in matrix games in which the agents would otherwise learn to defect with high probability. We show that the resulting cooperative outcome is stable in certain games even if the planning agent is turned off after a given number of episodes, while other games require ongoing intervention to maintain mutual cooperation. However, even in the latter case, the amount of necessary additional incentives decreases over time.

§ INTRODUCTION

Social dilemmas highlight conflicts between individual and collective interests. Cooperation allows for better outcomes for all participants, but individual participants are tempted to increase their own payoff at the expense of others. Selfish incentives can therefore destabilize the socially desirable outcome of mutual cooperation and often lead to outcomes that make everyone worse off [25].

Cooperation often emerges due to direct reciprocity [23] or indirect reciprocity [15]. However, even if these mechanisms are not sufficient on their own, humans are often able to establish cooperation by changing the structure of the social dilemma. This is often referred to as mechanism design. For instance, institutions	such as the police and the judicial system incentivize humans to cooperate in the social dilemma of peaceful coexistence, and have succeeded in dramatically reducing rates of violence [17].

Studies of social dilemmas have traditionally focused on the context of human agents. However, in the future, artificial learning agents will likely be increasingly widespread in our society, and be employed in a variety of economically relevant tasks. In that case, they will interact both with other artificial agents and humans in complex and partially competitive settings.

This raises the question of how we can ensure that artificial agents will learn to navigate the resulting social dilemmas productively and safely. Failing to learn cooperative policies would lead to socially inefficient or even disastrous outcomes. In particular, the escalation of conflicts between artificial agents (or between artificial agents and humans) may pose a serious security risk in safety-critical systems. The behaviour of artificial agents in cooperation problems is thus of both theoretical and practical importance.

In this work, we will examine how mechanism design can promote beneficial outcomes in social dilemmas among artificial learners. We consider a setting with $N$ agents in a social dilemma and an additional planning agent that can distribute (positive or negative) rewards to the players after observing their actions, and aims to guide the learners to a socially desirable outcome (as measured by the sum of rewards).

We derive a learning rule that allows the planning agent to learn how to set the additional incentives by looking ahead at how the agents will update their policy parameter in the next learning step.
We also extend the method to settings in which the planning agent does not know what internal parameters the other agents use and does not have direct access to the opponents' policy.

We evaluate the learning rule on several different matrix game social dilemmas. The planning agent learns to successfully guide the learners to cooperation with high social welfare in all games, while they learn to defect in the absence of a planning agent. We show that the resulting cooperative outcome is stable in certain games even if the planning agent is turned off after a given number of episodes. In other games, cooperation is unstable without continued intervention. However, even in the latter case, we show that the amount of necessary additional rewards decreases over time.

§ RELATED WORK

The study of social dilemmas has a long tradition in game theory, theoretical social science, and biology. In particular, there is a substantial body of literature that fruitfully employs matrix games to study how stable mutual cooperation can emerge [2]. Key mechanisms that can serve to stabilize the socially preferred outcome of mutual cooperation include direct reciprocity [23], indirect reciprocity [15], and norm enforcement [1]. [3] examine how cooperation can be stabilized via supplemental payments from an external party.

Our work is inspired by the field of mechanism design, pioneered by [27], which aims to design economic mechanisms and institutions to achieve certain goals, most notably social welfare or revenue maximization. [19] studies how informal and formal incentives for cooperative behaviour can prevent a tragedy of the commons. [13] considers a setting in which an interested party can commit to non-negative monetary transfers, and studies the conditions under which desirable outcomes can be implemented with a given amount of payment. Mechanism design has also been studied in the context of computerized agents [26] and combined with machine learning techniques [14].

We also draw on the rich literature on multi-agent reinforcement learning. It is beyond the scope of this work to review all relevant methods in multi-agent reinforcement learning, so we refer the reader to existing surveys on the subject [4, 24]. However, we note that most work in multi-agent reinforcement learning considers coordination or communication problems in the fully cooperative setting, where the agents share a common goal [16, 6].

As an exception, [9] study the learned behaviour of deep Q-networks in a fruit-gathering game and a Wolfpack hunting game that represent sequential social dilemmas. [22] successfully train agents to play Pong with either a fully cooperative, a fully competitive, or a mixed cooperative-competitive objective. [5] introduce a learning algorithm that uses novel mechanisms for generating and acting on signals to learn to cooperate with humans and with other machines in iterated matrix games. Finally, [11] propose a centralized actor-critic architecture that is applicable to both the fully cooperative as well as the mixed cooperative-competitive setting.

However, these methods assume a given set of opponent policies as given in that they do not take into account how one's actions affect the parameter updates on other agents. In contrast, [7] introduce Learning with Opponent-Learning Awareness (LOLA), an algorithm that explicitly attempts to shape the opponent's anticipated learning. The LOLA learning rule includes an additional term that reflects the effect of the agent's policy on the parameter update of the other agents and inspired the learning rule in this work. However, while LOLA leads to emergent cooperation in an iterated Prisoner's dilemma, the aim of LOLA agents is to shape the opponent's learning to their own advantage, which does not always promote cooperation.

§ BACKGROUND

§.§ Markov games

We consider partially observable Markov games [10] as a multi-agent extension of Markov decision processes (MDPs). An $N$-player Markov game $\cM$ is defined by a set of states $\cS$, an observation function $O: \cS \times \{1,\dots,N\} \rightarrow \bR^d$ specifying each player's $d$-dimensional view, a set of actions $\cA_1, \dots, \cA_N$ for each player, a transition function $\cT: \cS \times \cA_1 \times \dots \times \cA_N \rightarrow \cP(\cS)$, where $\cP(\cS)$ denotes the set of probability distributions over $\cS$, and a reward function $r_i: \cS \times \cA_1 \times \dots \times \cA_N \rightarrow \bR$ for each player. To choose actions, each player uses a policy $\pi_i : \cO_i \rightarrow \cP(\cA_i)$, where $\cO_i = \{ o_i~|~s \in \cS, o_i = O(s,i)\}$ is the observation space of player $i$. Each player in a Markov game aims to maximize its discounted expected return $R_i = \RTi$, where $\gamma$ is a discount factor and $T$ is the time horizon.

§.§ Policy gradient methods

Policy gradient methods [21] are a popular choice for a variety of reinforcement learning tasks. Suppose the policy $\pi_\theta$ of an agent is parametrized by $\theta$. Policy gradient methods aim to maximize the objective $J(\theta) = \bE_{s\sim p^{\pi_\theta},a\sim\pi_\theta}[R]$ by updating the agent's policy steps in the direction of $\nabla_\theta J(\theta)$.

Using the policy gradient theorem [20], we can write the gradient as follows:

\begin{equation}
\nabla_\theta J(\theta) = \bE_{s\sim p^{\pi_\theta},a\sim\pi_\theta}[\nabla_\theta \log \pi_\theta(a|s)\  Q^{\pi_\theta}(s,a)]
\end{equation}

where $p^{\pi_\theta}$ is the state distribution and $Q^{\pi_\theta}(s,a) = \bE[R| s_t = s, a_t = a]$.

§.§ Matrix game social dilemmas

A matrix game is the special case of two-player perfectly observable Markov games with $|\cS| = 1$, $T=1$ and $\cA_1 = \cA_2 = \{\text{C},\text{D}\}$. That is, two actions are available to each player, which we will interpret as cooperation and defection.

Payoff matrix of a symmetric 2-player matrix game. A cell of $X,Y$ represents a utility of $X$ to the row player and $Y$ to the column player.

C     D

C     $R, R$     $S, T$

D     $T, S$     $P, P$

Table <ref> shows the generic payoff structure of a (symmetric) matrix game. Players can receive four possible rewards: $R$ (reward for mutual cooperation), $P$ (punishment for mutual defection), $T$ (temptation of defecting against a cooperator), and $S$ (sucker outcome of cooperating against a defector).

A matrix game is considered a social dilemma if the following conditions hold [12]:

* Mutual cooperation is preferable to mutual defection: $R > P$

* Mutual cooperation is preferable to being exploited: $R > S$

* Mutual cooperation is preferable to an equal probability of unilateral defection by either player: $R > \frac{T+S}{2}$

* The players have some reason to defect because exploiting a cooperator is preferable to mutual cooperation ($T > R$) or because mutual defection is preferable to being exploited ($P > S$).

The last condition reflects the mixed incentive structure of matrix game social dilemmas. We will refer to the motivation to exploit a cooperator (quantified by $T-R$) as greed and to the motivation to avoid being exploited by a defector ($P-S$) as fear. As shown in Table <ref>, we can use the presence or absence of greed and fear to categorize matrix game social dilemmas.

The three canonical examples of matrix game social dilemmas with different reasons to defect. In Chicken, agents may defect out of greed, but not out of fear. In Stag Hunt, agents can never get more than the reward of mutual cooperation by defecting, but they may still defect out of fear of a non-cooperative partner. In Prisoner's Dilemma (PD), agents are motivated by both greed and fear simultaneously.

Chicken      C     D

C     $3, 3$     $1, 4$

D     $4, 1$     $0, 0$

Stag Hunt     C     D

C     $4, 4$     $0, 3$

D     $3, 0$     $1, 1$

PD     C     D

C     $3 ,3$     $0, 4$

D     $4, 0$     $1, 1$

§ METHODS

§.§ Amended Markov game including the planning agent

Suppose $N$ agents play a Markov game described by $\cS$, $\cA_1 \dots \cA_N$, $r_1,\dots,r_n$, $\cO$ and $\cT$. We introduce a planning agent that can hand out additional rewards and punishments to the players and aims to use this to ensure the socially preferred outcome of mutual cooperation.

To do this, the Markov game can be amended as follows. We add another action set $\cA_p \subset \bR^N$ that represents which additional rewards and punishments are available to the planning agent. Based on its observation $\cO_p: \cS \times \{1,\dots,N\} \rightarrow \bR^d$ and the other player's actions $a_1,\dots,a_n$, the planning agent takes an action $a_p = (r_1^p,\dots, r_N^p) \in \cA_p \subset \bR^N$.[Technically, we could represent the dependence on the other player's actions by introducing an extra step after the regular step in which the planning agent chooses additional rewards and punishments. However, for simplicity, we will discard this and treat the player's actions and the planning action as a single step. Formally, we can justify this by letting the planning agent specify its action for every possible combination of player actions.] The new reward function of player $i$ is $r_i^{(tot)} = r_i + r_i^p$, i.e. the sum of the original reward and the additional reward, and we denote the corresponding value functions as $\vintot = \vin + \vinp$. Finally, the transition function $\cT$ formally receives $a_p$ as an additional argument, but does not depend on it ($\cT(s,a_1,\dots,a_N,a_p) = \cT(s,a_1,\dots,a_N)$).

§.§ The learning problem

Let $\theta_1,\dots,\theta_N$ and $\theta_p$ be parametrizations of the player's policies $\pi_1,\dots,\pi_N$ and the planning agent's policy $\pi_p$.

The planning agent aims to maximize the total social welfare $\vtn := \sum_{i=1}^N \vin$, which is a natural metric of how socially desirable an outcome is. Note that without restrictions on the set of possible additional rewards and punishments, i.e. $\cA_p = \bR^N$, the planning agent can always transform the game into a fully cooperative game by choosing $r_i^p = \sum_{j=1, j\neq i}^N r_j$.

However, it is difficult to learn how to set the right incentives using traditional reinforcement learning techniques. This is because $\vtn$ does not depend directly on $\theta_p$. The planning agent's actions only affect $\vtn$ indirectly by changing the parameter updates of the learners. For this reason, it is vital to explicitly take into account how the other agents' learning changes in response to additional incentives.

This can be achieved by considering the next learning step of each player (cf. [7]). We assume that the learners update their parameters by simple gradient ascent:

\begin{equation}
\begin{aligned}
\Delta\theta_i &= \eta_i\nabla_i\vintot \\
&= \eta_i(\nabla_i\vin+\nabla_i\vinp)
\end{aligned}
\end{equation}

where $\eta_i$ is step size of player $i$ and $\nabla_i := \nabla_{\theta_i}$ is the gradient with respect to parameters $\theta_i$.

Instead of optimizing $\vtn$, the planning agent looks ahead one step and maximizes $\vtnnext$. Assuming that the parameter updates $\Delta\theta_i$ are small, a first-order Taylor expansion yields

\begin{equation}
\begin{aligned}
&\vtnnext \approx \\
&\approx \vtn + \sum_{i=1}^N (\Delta\theta_i)^T \nabla_i\vtn
\end{aligned}
\end{equation}

We use a simple rule of the form $\Delta\theta_p = \eta_p \nabla_p\vtnnext$ to update the planning agent's policy, where $\eta_p$ is the learning step size of the planning agent. Exploiting the fact that $\vtn$ does not depend directly on $\theta_p$, i.e. $\nabla_p\vtn = 0$, we can  calculate the gradient:

\begin{equation}
\begin{aligned}
\nabla_p&\vtnnext \approx \\
&\approx \sum_{i=1}^N \nabla_p(\Delta\theta_i)^T \nabla_i\vtn \\
&= \sum_{i=1}^N \eta_i(\nabla_p\nabla_i\vintot)^T \nabla_i\vtn \\ %fix layout, maybe drop this line
&= \sum_{i=1}^N \eta_i(\nabla_p\nabla_i\vinp)^T \nabla_i\vtn \\ %maybe drop arguments for simplicity.
\end{aligned}
\label{eq:gradp_differentiate_through}
\end{equation}

since $\nabla_i\vin$ does not depend on $\theta_p$ either.

§.§ Policy gradient approximation

If the planning agent does not have access to the exact gradients of $\vinp$ and $\vtn$, we use policy gradients as an approximation. Let $\tau = (s_0, \mathbf{a^{0}},a_p^0, \mathbf{r^{0}} \dots, s_T, \mathbf{a^{T}}, a_p^T, \mathbf{r^{T}})$ be a state-action trajectory of horizon $T+1$, where $\mathbf{a}^{t} = (a_1^t,\dots,a_N^t)$, $\mathbf{r}^{t} = (r_1^t,\dots,r_N^t)$, and $a_p^t = = (r_{1,p}^t,\dots,r_{N,p}^t)$ are the actions taken and rewards received in time step $t$. Then, the episodic return $R_i^0(\tau) = \RTi$ and $R_{i,p}^0(\tau) = \sum_{t=0}^T \gamma^t r_{i,p}^t$ approximate $\vin$ and $\vinp$, respectively. Similarly, $R^0(\tau) = \sum_{i=0}^N R_i^0(\tau)$ approximates the social welfare $\vtn$.

We can now calculate the gradients using the policy gradient theorem:

\begin{equation}
\begin{aligned}
\nabla_i\vin &\approx \nabla_i\bE[R_i^0(\tau)] 	\\
&= \bE[\nabla_i\log \pi_i(\tau) R_i^0(\tau)] %more steps as in LOLA paper
\end{aligned}
\end{equation}

The other gradients $\nabla_i\vtn$ and $\nabla_p\nabla_i\vinp$ can be approximated in the same way. This yields the following rule for the parameter update of the planning agent:

\begin{equation}
\begin{aligned}
\Delta\theta_p = \eta_p \sum_{i=1}^N \eta_i&\left(\bE\left[\nabla_p\log \pi_p(\tau) \nabla_i\log \pi_i(\tau) R_{i,p}^0(\tau)\right]\right)^T \\
\cdot &\bE\left[\nabla_i\log \pi_i(\tau) R^0(\tau)\right]
\end{aligned}
\label{eq:update_pg}
\end{equation}

§.§ Opponent modeling

Equations <ref> and <ref> assume that the planning agent has access to each agent's internal policy parameters and gradients. This is a restrictive assumption. In particular, agents may have an incentive to conceal their inner workings in adversarial settings. However, if the assumption is not fulfilled, we can instead model the opponents' policies using parameter vectors $\hat{\theta}_1,\dots,\hat{\theta}_N$ and infer the value of these parameters from the player's actions [18]. A simple approach is to use a maximum likelihood estimate based on the observed trajectory:

\begin{equation}
\label{eq:opp_modeling}
\hat{\theta_i} = \argmax_{\theta_i^{'}} \sum_{t=0}^T \log \pi_{\theta_i^{'}}(a_t^i|s_t).
\end{equation}

Given this, we can substitute $\hat{\theta}_i$ for $\theta_i$ in equation <ref>.

§.§ Cost of additional rewards

In real-world examples, it may be costly to distribute additional rewards or punishment. We can model this cost by changing the planning agent's objective to $\vtnnext - \alpha ||\vpn||_2$, where $\alpha$ is a cost parameter and $V^p = (V_1^p,\dots,V_N^p)$. The modified update rule is (using equation <ref>)

\begin{equation}
\label{cost_eq}
\small
\Delta\theta_p \!= \eta_p \!\!\left(\!\!\!\!
\begin{array}{r}
\displaystyle\sum_{i=1}^N \eta_i(\nabla_p\nabla_i\vinp)^T \nabla_i\vtn \\
- \alpha\nabla_p||\vpn||_2
\end{array}
\!\!\!\right)
\end{equation}

§ EXPERIMENTAL SETUP

In our experiments, we consider $N = 2$ learning agents playing a matrix game social dilemma (MGSD) as outlined in section <ref>. The learners are simple agents with a single policy parameter $\theta$ that controls the probability of cooperation and defection: $P(C) = \frac{\exp(\theta)}{1+\exp(\theta)}$, $P(D)=\frac{1}{1+\exp(\theta)}$. The agents use a centralized critic [11] to learn their value function.

The agents play 4000 episodes of a matrix game social dilemma. We fix the payoffs $R=3$ and
$P=1$, which allows us to describe the game using the level of greed and fear. We will consider
three canonical matrix game social dilemmas as shown in Table <ref>.

Levels of fear and greed and resulting temptation $(T)$ and sucker $(S)$ payoffs in three matrix games. Note that the level of greed in Chicken has to be smaller than 1 because it is otherwise not a social dilemma ($R > \frac{T+S}{2}$ is not fulfilled).

Game      Greed     Fear     $T$     $S$

Prisoner's Dilemma     1     1     4     0

Chicken     0.5     -1     3.5     2

Stag Hunt     -1     1     2     0

The planning agent's policy is parametrized by a single layer neural network. We limit the maximum amount of additional rewards or punishments (i.e. we restrict $\cA_p$ to vectors that satisfy $\max_{i=1}^N |r_i^p| \leq c$ for a given constant $c$).
Unless specified otherwise, we use a step size of 0.01 for both the planning agent and the learners, use cost regularisation (Equation <ref>) with a cost parameter of 0.0002, set the maximum reward to 3, and use the exact value function. In some experiments, we also require that the planning agent can only redistribute rewards, but cannot
change the total sum of rewards (i.e. $\cA_p$ is restricted to vectors that satisfy $\sum_{i=1}^N r_i^p = 0$). We refer to this as the revenue-neutral setting.

§ RESULTS

In this section, we summarize the experimental results.[Source code available at <https://github.com/tobiasbaumann1/Adaptive_Mechanism_Design>]
We aim to answer the following questions:

* Does the introduction of the planning agent succeed in promoting significantly higher levels of cooperation?

* What qualitative conclusions can be drawn about the amount of additional incentives needed to learn and maintain cooperation?

* In which cases is it possible to achieve cooperation even when the planning agent is only active for a limited timespan?

* How does a restriction to revenue-neutrality affect the effectiveness of mechanism design?

\includegraphics[height=2in]{Player_Action_Probabilities} &
\includegraphics[height=2in]{Additional_Rewards} \\
\text{(a) Probability of cooperation}\label{fig:action_probs} & \text{(b) Additional rewards for player 1}\label{fig:planning_rewards} \\
\includegraphics[height=2in]{Modified_Fear_and_Greed} &
\includegraphics[height=2in]{Cumulative_Additional_Rewards} \\
\text{(c) Fear and greed in the modified game}\label{fig:fear_and_greed} & \text{(d) Cumulative additional rewards}	\label{fig:cum_planning_rewards}
\end{array}$$

Mechanism design over 4000 episodes of a Prisoner's Dilemma. The initial probability of cooperation is 0.25 for each player. Shown is (a) the probability of cooperation over time, (b) the additional reward for the first player in each of the four possible outcomes, (c) the resulting levels of fear and greed including additional rewards, and (d) the cumulative amount of distributed rewards.

Figure 1a illustrates that the players learn to cooperate with high probability if the planning agent is present, resulting in the socially preferred outcome of stable mutual cooperation. Thus the planning agent successfully learns how to distribute additional rewards to guide the players to a better outcome.

Figure 1b shows how the planning agent rewards or punishes the player conditional on each of the four possible outcomes. At first, the planning agent learns to reward cooperation, which creates a sufficient incentive to cause the players to learn to cooperate. In Figure 1c we show how this changes the level of fear and greed in the modified game. The levels of  greed and fear soon drop below zero, which means that the modified game is no longer a social dilemma.

Note that rewarding cooperation is less costly than punishing defection if (and only if) cooperation is the less common action. After the player learns to cooperate with high probability, the planning agent learns that it is now less costly to punish defection and consequently stops handing out additional rewards in the case of mutual cooperation outcome. As shown in Figure 1d, the amount of necessary additional rewards converges to 0 over time as defection becomes increasingly rare.

Table <ref> summarizes the results of all three canonical social dilemmas. Without adaptive mechanism design, the learners fail to achieve mutual cooperation in all cases. By contrast, if the planning agent is turned on, the learners learn to cooperate with high probability, resulting in a significantly higher level of social welfare.

Comparison of the resulting levels of cooperation after 4000 episodes, a) without mechanism design, b) with mechanism design, and c) when turning off the planning agent after 4000 episodes and running another 4000 episodes. Each cell shows the mean and standard	deviation of ten training runs. $P(C,C)$ is the probability of mutual cooperation at the end of training and $V$ is the expected social welfare that results from the players' final action probabilities. The initial probability of cooperation is 0.25 for each player.

Dilemma     Chicken     Stag Hunt
Greed     1     0.5     -1
Fear     1     -1     1

21cmNo mech. design     $P(C,C)$     0.004%
$\pm$0.001%     3.7%
$\pm$1.3%     0.004%
$V$     2.024
$\pm$0.003     5.44
$\pm$0.01     2.00

21cmWith mech. design     $P(C,C)$     98.7%
$\pm$0.1%     99.0%
$\pm$0.1%     99.1%
$V$     5.975
$\pm$0.002     5.995
$\pm$0.001     5.964

off     $P(C,C)$     0.48%
$\pm$0.4%     53.8%
$\pm$29.4%     99.6%
$V$     2.60
$\pm$0.69     5.728
$\pm$0.174     5.986

The three games differ, however, in whether the cooperative outcome obtained through mechanism design is stable even when the planning agent is turned off. Without additional incentives, mutual cooperation is not a Nash equilibrium in the Prisoner's Dilemma and in Chicken [8], which is why one or both players learn to defect again after the planning agent is turned off. These games thus require continued (but only occasional) intervention to maintain cooperation. By contrast, mutual cooperation is a stable equilibrium in Stag Hunt [8]. As shown in Table <ref>, this means that long-term cooperation in Stag Hunt can be achieved even if the planning agent is only active over a limited timespan (and thus at limited cost).

Resulting levels of cooperation and average additional rewards (AAR) per round for different variants of the learning rule. The variants differ in whether they use the exact value function (Equation <ref>) or an estimate (Equation <ref>) and in whether the setting is revenue-neutral or unrestricted.

Dilemma     Chicken     Stag Hunt
Greed     1     0.5     -1
Fear     1     -1     1
4c|Exact $V$
$P(C,C)$     98.7%
$\pm$0.1%     99.0%
$\pm$0.1%     99.1%
AAR     0.77
$\pm$0.21     0.41
$\pm$0.02     0.45
4c|Exact $V$
$P(C,C)$     91.4%
$\pm$1.0%     98.9%
$\pm$0.1%     69.2%
AAR     0.61
$\pm$0.04     0.31
$\pm$0.02     0.19
4c|Estimated $V$
$P(C,C)$     61.3%
$\pm$20.0%     52.2%
$\pm$18.6%     96.0%
AAR     3.31
$\pm$0.63     2.65
$\pm$0.31     4.89

Table <ref> compares the performance of different variants of the learning rule.	Interestingly, restricting the possible planning actions to redistribution leads to lower probabilities of cooperation in Prisoner's Dilemma and Stag Hunt, but not in Chicken. We hypothesize	that this is because in Chicken, mutual defection is not in the individual interest of the players anyway. This means  that the main task for the planning agent is to prevent (C,D) or (D,C) outcomes,
which can be easily achieved by redistribution. By contrast, these outcomes are fairly unattractive (in terms of individual interests) in Stag Hunt, so the most effective intervention is to make (D,D) less attractive and (C,C) more attractive, which is not feasible by pure redistribution. Consequently, mechanism design by redistribution works best in Chicken and worst in Stag Hunt.

Using an estimate of the value function leads to inferior performance on all three games, both in
terms of the resulting probability of mutual cooperation and with respect to the amount of distributed additional results. However, the effect is by far least pronounced in Stag Hunt. This may be because mutual cooperation is an equilibrium in Stag Hunt, which means that a beneficial outcome can more easily arise even if the incentive structure created by the planning agent is imperfect.

Finally, we note that the presented approach is also applicable to settings with more than two players.[Source code available in a separate repository at <https://github.com/tobiasbaumann1/Mechanism_Design_Multi-Player>] We consider a multi-player Prisoner's Dilemma with $N=10$ agents.[The payoffs are as follows: 3 if all players cooperate, 1 if all players defect, 4 if you are the only to defect, 0 if you are the only to cooperate. Payoffs of intermediate outcomes, where some fraction of players cooperate, are obtained by linear interpolation.]

\includegraphics[height=2in]{Fraction_of_cooperators_with_MD} & \includegraphics[height=2in]{Fraction_of_cooperators} \\
\makecell{\text{(a) Average probability of cooperation with} \\ \text{mechanism design}} \label{fig:coop_probs_with_MD} & \makecell{\text{(b) Average probability of cooperation without} \\ \text{mechanism design}} \label{fig:coop_prob_without_MD}
\end{array}$$

Mechanism design in a multi-player Prisoner's Dilemma. The initial probability of cooperation is 0.25 for each player. Shown is the average probability of cooperation over time (a) in the presence of a planning agent, (b) without mechanism design.

Figure 2a illustrates that, just as in the case of $N=2$, the players learn to cooperate with high probability if the planning agent is present. By contrast, without mechanism design, the players (unsurprisingly) converge to the socially undesirable outcome of mutual defection. This shows that the presented approach for learning how to distribute additional rewards scales easily to multi-agent social dilemmas.

§ CONCLUSIONS AND FUTURE WORK

We have presented a method for learning how to create the right incentives to ensure cooperation
between artificial learners. Empirically, we have shown that a planning agent that uses the proposed learning rule is able to successfully guide the learners to the socially preferred outcome of mutual cooperation in several different matrix game social dilemmas, while they learn to defect with high probability in the absence of a planning agent. The resulting cooperative outcome is stable in certain games even if the planning agent is turned off after a given number of episodes, while other games require continued (but increasingly rare) intervention to maintain cooperation. We also showed that restricting the planning agent to redistribution leads to worse performance in Stag Hunt, but not in Chicken.

In the future, we would like to explore the limitations of adaptive mechanism design in more complex
environments, particularly in games with more than two players, without full observability of the
players' actions, and using opponent modeling (cf. Equation <ref>). Future work could also consider settings in which the planning agent aims to ensure
cooperation by altering the dynamics of the environment or the players' action set (e.g. by
introducing mechanisms that allow players to better punish defectors or reward cooperators).

Finally, under the assumption that artificial learners will play vital roles in future society, it is worthwhile to develop policy recommendations that would facilitate mechanism design for these agents (and the humans they interact with), thus contributing to a cooperative outcome in potential social dilemmas. For instance, it would be helpful if the agents were set up in a way that makes their intentions as transparent as possible and allows for simple ways to distribute additional rewards and punishments without incurring large costs.

[1]
Robert Axelrod, `An Evolutionary Approach to Norms', American Political
Science Review, (1986).

[2]
Robert Axelrod and William D. Hamilton, `The Evolution of Cooperation', Evolution, (1981).

[3]
Yoram Bachrach, Edith Elkind, Reshef Meir, Dmitrii Pasechnik, Michael
Zuckerman, Jörg Rothe, and Jeffrey S Rosenschein, `The cost of stability
in coalitional games', in International Symposium on Algorithmic Game
Theory, pp. 122–134. Springer, (2009).

[4]
Lucian Busoniu, Robert Babuska, and Bart De Schutter, `A Comprehensive Survey
of Multiagent Reinforcement Learning', Systems, Man, and Cybernetics,
Part C: Applications and Reviews, (2008).

[5]
Jacob W. Crandall, Mayada Oudah, Fatimah Ishowo-Oloko, Sherief Abdallah,
Jean-François Bonnefon, et al., `Cooperating with machines', Nature communications, 9(1),  233, (2018).

[6]
Jakob Foerster, Ioannis Alexandros Assael, Nando de Freitas, and Shimon
Whiteson, `Learning to Communicate with Deep Multi-Agent Reinforcement
Learning',  2137–2145, (2016).

[7]
Jakob N. Foerster, Richard Y. Chen, Maruan Al-Shedivat, Shimon Whiteson, Pieter
Abbeel, and Igor Mordatch, `Learning with Opponent-Learning Awareness',

[8]
Drew Fudenberg and Jean Tirole, Game Theory, MIT Press, Cambridge, MA,

[9]
Joel Z. Leibo, Vinicius Zambaldi, Marc Lanctot, Janusz Marecki, and Thore
Graepel, `Multi-agent Reinforcement Learning in Sequential Social
Dilemmas', Proceedings of the 16th Conference on Autonomous Agents and
MultiAgent Systems, (2017).

[10]
Michael L. Littman, `Markov games as a framework for multi-agent reinforcement
learning', in Machine Learning Proceedings 1994, (1994).

[11]
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch,
`Multi-agent actor-critic for mixed cooperative-competitive environments', in
Advances in Neural Information Processing Systems, pp. 6382–6393,

[12]
Michael W. Macy and Andreas Flache, `Learning Dynamics in Social Dilemmas.',
Proceedings of the National Academy of Sciences of the United States of
America, (2002).

[13]
Dov Monderer and Moshe Tennenholtz, `k-implementation', Journal of
Artificial Intelligence Research, 21,  37–62, (2004).

[14]
Harikrishna Narasimhan, Shivani Brinda Agarwal, and David C Parkes, `Automated
mechanism design without money via machine learning', (2016).

[15]
Martin A. Nowak and Karl Sigmund.
Evolution of Indirect Reciprocity, 2005.

[16]
Shayegan Omidshafiei, Jason Pazis, Christopher Amato, Jonathan P. How, and John
Vian, `Deep Decentralized Multi-task Multi-Agent Reinforcement Learning
under Partial Observability', (2017).

[17]
Steven Pinker, `The Better Angels of Our Nature', (2011).

[18]
Stephane Ross, Geoffrey J. Gordon, and J. Andrew Bagnell, `A Reduction of
Imitation Learning and Structured Prediction to No-Regret Online Learning',

[19]
Paul Seabright, `Managing Local Commons: Theoretical Issues in Incentive
Design', Journal of Economic Perspectives, 7(4),  113–134,

[20]
Richard S. Sutton, David A. McAllester, Satinder P. Singh, and Yishay Mansour,
`Policy gradient methods for reinforcement learning with function
approximation',  1057–1063, (2000).

[21]
RS Sutton and AG Barto, Reinforcement learning: An introduction, 1998.

[22]
Ardi Tampuu, Tambet Matiisen, Dorian Kodelja, Ilya Kuzovkin, Kristjan Korjus,
Juhan Aru, Jaan Aru, and Raul Vicente, `Multiagent cooperation and
competition with deep reinforcement learning', PLoS ONE, (2017).

[23]
Robert L. Trivers, `The Evolution of Reciprocal Altruism', The Quarterly
Review of Biology, (1971).

[24]
Karl Tuyls and Gerhard Weiss, `Multiagent Learning: Basics, Challenges, and
Prospects', AI Magazine, (2012).

[25]
Paul A. M. Van Lange, Jeff Joireman, Craig D. Parks, and Eric Van Dijk, `The
Psychology of Social Dilemmas: A Review', Organizational Behavior and
Human Decision Processes, 120(2),  125–141, (2013).

[26]
Hal R. Varian, `Economic mechanism design for computerized agents.', in USENIX workshop on Electronic Commerce, pp. 13–21, (1995).

[27]
William Vickrey, `Counterspeculation, Auctions, and Competitive Sealed
Tenders', The Journal of Finance, 16(1),  8–37, (1961).