# Incentives to Form Larger Coalitions when Players Have the Power to Choose

Yao Zhang&Dengji ZhaoShanghaiTech University{zhangyao1,
<EMAIL_ADDRESS>
###### Abstract

We study a cooperative game setting where the grand coalition may change since
the initial players are willing to invite their neighbours and also want to
incentivize them to invite more players to join. We focus on the monotone
games, i.e., adding more players to the grand coalition is not harmful. We
model the invitation relationship as a forest since we require that each
player can only accept the invitation at most once. Our goal is to design a
solution mechanism to this new cooperative game setting. In this paper, we
characterize the weighted permission Shapley value (inspired by permission
structure and the weighted Shapley value), which is diffusion incentive
compatible, i.e., all players are incentivized to invite their neighbours to
join the coalition. Our solution offers the very first attempt to incentivize
players to invite more players to form a larger coalition via their private
connections, which has many potential applications in other real-world.

##  1 Introduction

Cooperative game is a classical research topic studied in game theory Nisan et
al. (2007); Narahari (2014). The study focused on settings where a fixed set
of players form coalitions to share a reward. A common assumption behind the
game is that more players collaborate together creates a higher reward. Then
one immediate question is how we can gather all the players initially, which
is not tackled in traditional settings. With the rapid development of Internet
and social media, people now can remotely form a group online to collaborate
on a project via, for example, crowdsourcing platforms (e.g. Amazon Mechanical
Turk) and Q&A platforms (e.g. Stack Overflow). However, we may still fail to
get enough participants via these online platforms, because participants need
to constantly check what projects are available before joining them.

Therefore, in this paper we want to design a mechanism where existing
participants are motivated to invite others to join a project via their social
connections. We see this kind of mechanism is highly demanded in practice. For
instance, when a research team wants to collect a large scale dataset, they
may propagate the requirements via social networks to seek more data providers
Singla et al. (2015); Jeong et al. (2013). When a company wants to select a
set of users for a product trial, it may diffuse the recruitment via social
networks to find the target users. Again, we may use social networks to find a
missing person quickly. The most famous red balloon challenge host by DARPA is
a well-known example where collaboration formed via social networks played a
critical role Pickard et al. (2011).

Similar to the classical setting, the key challenge here is to design a reward
distribution mechanism for all players in the coalition. The difference is
that in our setting players are connected as a network and a player cannot
join a coalition without the invitation from her neighbours (simply because
the player is not aware of the collaboration without others’ invitation).
_More precisely, our challenge is to design reward distribution mechanisms
such that existing players of the coalition are incentivized to invite their
neighbours to join the coalition._

The Shapley value is a classical solution concept in a cooperative game to
distribute rewards in a coalition, which was first presented in Shapley
(1953). However, in the calculation of the Shapley value, all the players are
completely symmetric, which is not the case in our setting where players are
structured by their social connections. Because of that, the Shapley value
cannot be directly applied here to incentivize players to invite others.

To combat this problem, we combine two novel concepts of the permission
structure and weighted Shapley value for the first time. The weighted Shapley
value is the very first concept that applies asymmetry to the cooperative game
Chun (1991). Kalai and Samet Kalai and Samet (1987) firstly gave the idea of
the weight system and an axiomatic characterization of weighted Shapley
values. A recent perspective of the weighted Shapley value is illustrated in
Radzik (2012), which gave new axioms for the weighted Shapley value and
provided simpler formula of weighted Shapley value. However, the asymmetry
introduced by the weighted Shapley value cannot reflect the structure of the
connections between players, which will be explained in Section 3.1.

The permission structure concept seems a closer solution to our problem, which
was first introduced in Gilles et al. (1992) and Gilles et al. (1999). In the
permission structure, players need permissions from other players before they
are allowed to cooperate, where permission is very similar to invitation in
our model. Gilles et al. Gilles et al. (1992, 1999) considered the cases where
each player has to get permissions from all or at least one of her superiors,
which is called the conjunctive and disjunctive approach respectively. The
axiomatic characterization of the Shapley value under these two approaches are
given in van den Brink and Gilles (1996) and Van Den Brink (1997). The Banzhaf
permission value of the two approaches was described in van den Brink (2010),
which defined the importance or power index for each player in a network based
on the permission structure. In this paper, we extend the permission structure
by mixing the conjunctive and disjunctive approaches, which can deal with
instances like: player $a$ has to get permissions from superiors $b$ and $c$,
or just superior $d$.

Our solution is a novel combination of the weighted Shapley value and the
permission structure with the mixed approach, which is the very first attempt
to incentivize players to invite others in a cooperative game. The well-known
winning solution for the DARPA red balloon challenge is a special case of our
solution Pickard et al. (2011). Our new model of incentivizing collaboration
in cooperative games and the proposed solution have very promising
applications for task allocations via social networks such as crowdsourcing
and question answering. Our contributions advance the state of the art in the
following ways:

  * •

We formally model the (social) connections between players in a coalitional
game and, for the first time, define the concept of _diffusion incentive
compatibility (DIC)_ for players to utilize their connections to form larger
coalitions.

  * •

We extend the permission structure concept and combine it with weighted
Shapley value to define a family of reward distribution mechanisms to achieve
DIC.

  * •

We also, for the first time, formally model the awarding winning solution for
the 2009 DARPA red balloon challenge as a special case of our solution, which
justifies that why it has attracted so many participants in a short period
(because inviting all their social neighbours is a dominant strategy).

There are some interesting related work investigating information diffusion on
social networks with non-cooperative settings Emek et al. (2011); Li et al.
(2017); Zhao et al. (2018); Sinha and Wellman (2019). Emek et al. Emek et al.
(2011) firstly investigated the setting of multi-level marketing, where
players promote a sale of products to their neighbours in a tree. For
incentivizing players to invite friends to a single-item auction, Li et al. Li
et al. (2017) proposed the very first mechanism. Later, Zhao et al. Zhao et
al. (2018) generalized the auction in the setting of multiple items. Our model
and solution share a similar high level motivation with them, but cannot be
handled with their techniques.

The remainder of the paper is organized as follows. In Section 2, we give a
formal description of our model and the definition of diffusion incentive
compatibility. In Section 3, we start our discussion from the cases where the
social connection is a tree. We give a family of mechanisms that incentivize
diffusion and the well-known solution for the 2009 DARPA red balloon challenge
is a member of it. Then in Section 4, we define the permission structure with
our mixed approach and give the general mechanism in DAGs.

##  2 The Model

We study a cooperative game where players are connected to build a network and
a player cannot join the coalition without an invitation from her neighbours.
In real-world applications, their connections can represent friendship or
leadership. A person/boss who is in the coalition can invite her
friends/employees to join the coalition. Without the invitation, her friends
will not be informed about the coalition. We investigate the reward
distribution mechanism under this setting to incentivize players in the
coalition to invite all their neighbours to join the existing coalition. This
is not achievable with the existing mechanisms such as the Shapley value.

Formally, let $\mathcal{N}=\\{1,2,\dots,N\\}$ be the set of all players in the
resulting network after invitation. There is a special player set
$\mathcal{I}\subset\mathcal{N}$ who are in the coalition without invitation.
We call $\mathcal{I}$ the initiate set, who have a task request for the
coalition. Since the invitation has to start from the initial players, we
model the network as a forest $G=(\mathcal{N},\mathcal{E})$. Each edge
$e=(x,y)\in\mathcal{E}$ indicates that player $x$ can invite $y$. For each
player $i\in\mathcal{N}$, denote her parent by $p(i)$. Note that $p(i)=null$
if and only if $i\subset\mathcal{I}$ and we assume that all players can be
reached from at least one of the initial players.

There is a non-negative characteristic function
$v:2^{\mathcal{N}}\rightarrow\mathbb{R}$. We assume that $v$ is monotone,
i.e., $v(\emptyset)=0$ and $v(E)\leq v(F)$ for all $E\subset
F\subset\mathcal{N}$. The monotone property is necessary, otherwise, there is
no need to invite more people to join the coalition if fewer people can do
better.

Let $\mathcal{G}(\mathcal{N})$ be the space of all networks satisfy our
setting and $\mathcal{V}(\mathcal{N})$ be the space of all characteristic
functions satisfying our setting. We define the reward distribution mechanism
as follows.

######  Definition 1.

A reward distribution mechanism is defined by
$\mathcal{M}:\mathcal{G}(\mathcal{N})\times\mathcal{V}(\mathcal{N})\rightarrow\mathbb{R}^{|\mathcal{N}|}$,
where $\mathcal{M}(G,v)=(\phi_{1},\dots,\phi_{|\mathcal{N}|})$ assigns the
reward $\phi_{i}$ to each player $i$ in $\mathcal{N}$ given
$G\in\mathcal{G}(\mathcal{N})$ and $v\in\mathcal{V}(\mathcal{N})$.

A good reward distribution mechanism should distribute exactly what the
coalition can generate. This is called _efficiency_.

######  Definition 2.

A reward distribution mechanism $\mathcal{M}$ is efficient if for all
$G\in\mathcal{G}(\mathcal{N})$ and all $v\in\mathcal{V}(\mathcal{N})$

$\sum_{i}\mathcal{M}(G,v)_{i}=v(\mathcal{N})$

Under the reward distribution mechanism, we want to incentivize all players
who are already in the coalition to invite all their neighbours to join the
coalition. This requires that inviting all neighbours is a dominant strategy
for all players. We call this property _diffusion incentive compatible_.

######  Definition 3.

A reward distribution mechanism $\mathcal{M}$ is diffusion incentive
compatible (DIC) if for all $i\in\mathcal{N}$ and any edge set
$X\subseteq\\{(x,y)\mid(x,y)\in\mathcal{E},x=i\\}$

$\mathcal{M}(G,v)_{i}\geq\mathcal{M}(G^{\prime},v)_{i}$

where $G^{\prime}=(\mathcal{N}^{\prime},\mathcal{E}^{\prime})$ is the deduced
graph from $G$ after removing $X$, i.e.,
$\mathcal{N}^{\prime}=\\{i\mid\text{if }\exists n\in\mathbb{N}_{+}\text{ and a
sequence }j_{1},j_{2},\dots,j_{n}\text{ where
}j_{1}\in\mathcal{I},j_{n}=i\text{ and }\forall 1\leq
k<n,(j_{k},j_{k+1})\in\mathcal{E}\setminus X\\}$ and
$\mathcal{E}^{\prime}=\\{(i,j)\mid i,j\in\mathcal{N}^{\prime}\text{ and
}(i,j)\in\mathcal{X}\\}$

In the rest of the paper, we first propose a class of reward distribution
mechanisms satisfying efficiency and DIC. Then we characterize our class of
mechanisms along with a couple of other important issues in cooperative games.

##  3 Diffusion Incentives in a Tree

In this section, we investigate the special cases when the player network $G$
is a tree. An instance of the tree model is illustrated in Example 1 below.

######  Example 1.

Consider the case where a single requester $r$ wants to find answers to a
question, i.e., $\mathcal{I}=\\{r\\}$. The answers are held by several people
in the network.

As illustrated in Figure 1, $r$ firstly asks to her friends $a$ and $b$, and
then $a$ and $b$ further propagate the query to their friends and so on. Such
a tree model of query networks is firstly studied in Kleinberg and Raghavan
(2005). In this example, we assume that the holders of the answers are players
$f$, $e$ and $h$, where $e$ and $h$ hold the same answer.

$r$$a$$b$$c$$d$$e$$f$$g$$h$ Figure 1: An example of the cooperative game in a
tree. The red nodes are players who have contribution to the coalition.

Suppose each answer worth one unit reward, then it becomes a cooperative game
where $\mathcal{N}$ contains players $a$ to $h$ and $r$. The graph $G$ is the
query tree rooted at $r$ and the characteristic function $v$ is defined as:

$v(E)=\begin{cases}0&\text{if }|\\{e,f,h\\}\cap E|=0\\\ 1&\text{if
}|\\{e,f,h\\}\cap E|=1\\\ &\text{or }|\\{e,f,h\\}\cap E|=2,f\notin E\\\
2&\text{if }|\\{e,f,h\\}\cap E|=2,f\in E\\\ &\text{or }|\\{e,f,h\\}\cap
E|=3\end{cases}$

for every $E\subset\mathcal{N}$.

Let us first apply the classical Shapley value Winter (2002) in the above
example. Let $\mathcal{R}(E)$ denote the set of all orders $R$ of players in
the coalition $E$. For an order $R$ in $\mathcal{R}(\mathcal{N})$, we denote
by $B^{R,i}$ the set of players preceding $i$ in the order $R$. For a given
game $v$ and order $R$, the marginal contribution of player $i$ in $R$ is
$C_{i}(v,R)=v(B^{R,i}\cup\\{i\\})-v(B^{R,i})$. Then the classical Shapley
value of game $v$ for $i$ is the expectation of $i$’s marginal contribution:

$\phi_{i}(v)=\mathbb{E}_{\mathcal{U}_{\mathcal{R}(\mathcal{N})}}(C_{i}(v,\cdot))$

where $\mathcal{U}_{\mathcal{R}(\mathcal{N})}$ is a uniform distribution on
$\mathcal{R}(\mathcal{N})$.

Applying the Shapley value to the game in Example 1, we can derive that
$\phi_{f}=1$, $\phi_{e}=\phi_{h}=1/2$ and $\phi_{i}=0$ for $i\neq e,f,h$.
Intuitively, the Shapley value only distributes the reward to those who
provide answers. Therefore, there is no incentive for $a$, $b$ and $c$ to
invite their friends to join the coalition. Moreover, if $e$ does not invite
$h$, her Shapley value will be increased to 1. Hence, the Shapley value alone
does not satisfy the DIC property.

###  3.1 Applying Shapley Value with Permission Structure

Taking the structure of the diffusion tree into account, we see that some
players need others’ participation to create value. For example, without
player $c$, player $f$ cannot provide the answer to the requester. This
suggests applying Shapley value with a permission structure.

The idea of permission structure was first proposed in Gilles et al. (1992).
Gilles et al. Gilles et al. (1992, 1999) give the permission restriction on
cooperative games via the conjunctive and disjunctive approach respectively.
The axiomatic characterizations of the Shapley value via permission structure
of the two approaches are given by van den Brink and Gilles van den Brink and
Gilles (1996); Van Den Brink (1997). A permission structure is normally
defined as the following.

######  Definition 4.

A permission structure on $\mathcal{N}$ is an asymmetric mapping
$S:\mathcal{N}\rightarrow 2^{\mathcal{N}}$, i.e., $j\in S(i)$ implies that
$i\notin S(j)$.

Here, $S(i)$ is the set of players who invite $i$ into the coalition.
Especially, in the tree model, for each player $i$, $S(i)$ only contains her
unique parent or is empty if $i$ is the requester (the root of the tree). Note
that since every player except the root is only invited by one other player in
the tree model, there is no need to discuss the difference between conjunctive
and disjunctive approaches. Then, in this case, we can define the autonomous
coalition as following.

######  Definition 5.

A coalition $E\subset\mathcal{N}$ is autonomous in a permission structure $S$
if for any player $i\in E$, $S(i)\subset E$.

Then in the tree model, a coalition $E\subset\mathcal{N}$ is autonomous if and
only if for every player $i\in E$, all her ancestors also belong to $E$. The
property of autonomous indicates whether a coalition has a chance to generate
rewards. Denote the collection of all autonomous coalitions in permission
structure $S$ as $A_{S}$. Then for an arbitrary coalition
$E\subset\mathcal{N}$, we consider the largest autonomous part of it.

######  Definition 6.

Let $S$ be a permission structure on $\mathcal{N}$. Then the autonomous part
of a coalition $E\subset\mathcal{N}$ is defined by:

$\alpha(E)=\bigcup\\{F\mid F\subset E\text{ and }F\in A_{S}\\}$

For the case of the tree model, let the subgraph of the tree $T$ deduced by
$E$ is $T_{E}$, then the autonomous part of the coalition $E$ is the connected
component of $T_{E}$ that contains the root $r$.

On the other hand, we consider the smallest autonomous coalition that
precisely contains $E$:

######  Definition 7.

Let $S$ be a permission structure on $\mathcal{N}$. Then the authorizing
coalition of a coalition $E\subset\mathcal{N}$ is defined by:

$\lambda(E)=\bigcap\\{F\mid E\subset F\text{ and }F\in A_{S}\\}$

For the case of the tree model, the authorizing coalition of a coalition $E$
is taking union with all the players which are on the paths from the root to
the players in $E$.

With the restriction of the permission structure, we can map the
characteristic function $v$ of the cooperative game in the tree to a
projection $v^{\prime}$ on $S$ Gilles et al. (1992)

$v^{\prime}(E)=v(\alpha(E)),\qquad\text{for every }E\subset\mathcal{N}.$

Intuitively, it means that the contribution given by a coalition $E$ is only
from those players who can be invited in the coalition $E$.

Another perspective to this projection is to express the mapping in terms of
the unanimity basis. The unanimity basis was first introduced by Harsanyi
(1959), which plays an important role in analysing cooperative games. An
unanimity basis of the cooperative game on player set $\mathcal{N}$ is
$\\{u_{E}\mid E\subset\mathcal{N},E\neq\emptyset\\}$, where an unanimity game
$u_{E}$ is defined as:

$u_{E}(F)=\begin{cases}1&\text{if }E\subset F\\\
0&\text{otherwise}\end{cases}.$

i.e., there is unit value being created when the player set $E$ exists in the
coalition.

Then any characteristic function $v$ can be expressed as:

$v=\sum_{E\subset\mathcal{N}}d^{v}(E)u_{E}$

where $d^{v}(E)$ is called the dividend of coalition $E$ in $v$ Harsanyi
(1959); Chalkiadakis et al. (2011) and can be calculated as follows.

$d^{v}(E)=\sum_{F\subset E}(-1)^{|E|-|F|}v(F)$

The following gives the mapping with the restriction of the permission
structure in terms of unanimity basis:

$v^{\prime}=\sum_{E\in A_{S}}\left(\sum_{F:\lambda(F)=E}d^{v}(F)\right)u_{E}$

Again applying the Shapley value on this new characteristic function
$v^{\prime}$, the distributed reward in Example 1 will be:
$\phi^{\prime}_{a}=\phi^{\prime}_{c}=\phi^{\prime}_{f}=1/4$,
$\phi^{\prime}_{b}=\phi^{\prime}_{e}=1/3$, $\phi^{\prime}_{r}=7/12$ and
$\phi^{\prime}_{d}=\phi^{\prime}_{g}=\phi^{\prime}_{h}=0$.

To see the intuition of the Shapley value with permission structure here, we
first consider the special cases where an additive assumption is applied,
i.e., for each player $i\in\mathcal{N}$, $v(\\{i\\})\geq 0$ and for each two
disjoint subsets of players $E_{1}$, $E_{2}\subset\mathcal{N}$ that $E_{1}\cap
E_{2}=\emptyset$, we have $v(E_{1}\uplus E_{2})=v(E_{1})+v(E_{2})$. Under this
assumption, denote $v(\\{i\\})$ by $v_{i}$, the depth of $i$ in the tree by
$d_{i}$ (the depth of the requester $r$ is 0) and the subtree rooted by $i$ by
$T_{i}$. Then the Shapley value with permission structure of the player $i$
will be:

$\phi^{\prime}_{i}=\sum_{k\in T_{i}}\frac{1}{d_{k}+1}v_{k}\qquad\text{for
every }i\in\mathcal{N}.$

Intuitively speaking, the reward will be uniformly distributed along the
invitation chain.

We can show that if we use the Shapley value with permission structure as the
reward distribution mechanism, the propagation is indeed incentivized under
the additive assumption.

######  Proposition 1.

For the additive cooperative game in a tree, if the reward distribution
mechanism $\mathcal{M}$ is the Shapley value with permission structure, then
$\mathcal{M}$ is efficient and DIC.

###### Proof.

The efficiency is easily derived since it is a variation of the Shapley value.

For the diffusion incentive compatibility, first consider a leaf node player
$j$ and her parent $i$. Denote the number of total players as $n$, then:

  * •

If $i$ does not invite $j$, suppose the total contribution of $i$ to all
orders of players with permission structure is
$C=\sum_{R}C_{i}(v^{\prime},R)$, then the Shapley value with permission
structure of $i$ is $\phi^{\prime}_{i}=C/(n-1)!$.

  * •

If $i$ does invite $j$, for each order where $j$ comes after $i$, the
contribution of $i$ remains the same; for each order $j$ comes before $i$, the
marginal contribution of $i$ is increased by either $v_{j}$ or 0. Then, for
$\phi^{\prime\prime}_{i}$, which is the Shapley value of $i$ if $i$ does
invite $j$, satisfies

$\displaystyle\frac{nC+\binom{n}{2}(n-2)!\cdot v_{j}}{n!}\geq$
$\displaystyle\phi^{\prime\prime}_{i}\geq\frac{nC+\binom{n}{2}(n-2)!\cdot
0}{n!}$ $\displaystyle\frac{C}{(n-1)!}+\frac{\binom{n}{2}}{n(n-1)}v_{j}\geq$
$\displaystyle\phi^{\prime\prime}_{i}\geq\frac{C}{(n-1)!}$
$\displaystyle\phi^{\prime}_{i}+\frac{1}{2}v_{j}\geq$
$\displaystyle\phi^{\prime\prime}_{i}\geq\phi^{\prime}_{i}$

Similarly, for every edge $(i,j)$ in the query tree, the Shapley value with
permission structure when $i$ invites $j$ is no less than that when $i$ does
not invite $j$. Therefore, the Shapley value with permission structure is a
DIC mechanism. ∎

For the general cases where the cooperative game is monotone, the marginal
contribution of $i$ in the second case of the above proof will not necessarily
be $v(\\{j\\})$ but still be positive. Hence, the following corollary can be
easily derived.

######  Corollary 1.

For the monotone cooperative game in a tree, if the reward distribution
mechanism $\mathcal{M}$ is the Shapley value with permission structure, then
$\mathcal{M}$ is efficient and DIC.

###  3.2 Using Weights to Further Utilize the Structure

However, the solution given by Shapley value with permission structure cannot
distinguish the differences among an players’ ancestors and hence it is not
the unique DIC mechanism. Another classic solution to an additive cooperative
game in the tree is given by the winning team from MIT in the DARPA red
balloon challenge Pickard et al. (2011). In the challenge, each team needed to
find ten positions of the red balloons and each balloon would bring $4000 as
rewards. The solution proposed by the winning team is that they promised $2000
per balloon for the first person who found it and $1000 to the person who
invited the finder and so on.

This suggests that weights can be introduced to distinguish the differences
among an player’s ancestors. Kalai and Samet Kalai and Samet (1987) first
illustrated the weighted Shapley value as an alternative solution to the
cooperative games. Radzik Radzik (2012) further discussed the variants and
properties of the weighted Shapley value and Dragan Dragan (2008) provided
computation method for weighted Shapley value. Normally, the weighted Shapley
value can be defined as:

$\hat{\phi}_{i}(v)=\mathbb{E}_{\mathcal{D}}(C_{i}(v,\cdot))$

where $\mathcal{D}$ is some distribution on $\mathcal{R}(\mathcal{N})$.

Thus, the weights are put on different orders of the players. Another neat
approach to define weighted Shapley value is in terms of unanimity basis Kalai
and Samet (1987). Let the weights $\omega$ be positive values assigned to each
player, i.e., $\omega\in\mathbb{R}^{|\mathcal{N}|}_{+}$. Then for each
unanimity game $u_{E}$, the weighted Shapley value is defined as following:

$\phi^{\omega}_{i}(u_{E})=\frac{\omega_{i}}{\sum_{j\in E}\omega_{j}}$

for $i\in E$ and 0 otherwise.

Note that when $\omega=1^{|\mathcal{N}|}$, the weighted Shapley value is the
classical Shapley value. This can be seen as a weighted reward distribution in
each unanimity game $u_{E}$ rather than an equal distribution in the classical
case.

The following two lemmas show that the Shapley value with permission structure
and weighted Shapley value are two different classes of solutions to
cooperative games.

######  Lemma 1.

There exists a cooperative game $v$ with permission structure $S$ such that
there is no $\omega\in\mathbb{R}^{|\mathcal{N}|}_{+}$ that satisfies

$\forall i\in\mathcal{N},\qquad\phi^{\omega}_{i}(v)=\phi_{i}(v^{\prime})$

where $v^{\prime}$ is the $v$’s projection on $S$.

###### Proof.

Consider the characteristic function $v$ on the player set $\\{1,2\\}$:
$v_{\\{1\\}}=0$ and $v_{\\{2\\}}=v_{\\{1,2\\}}=1$; and the permission
structure $S$: $S(1)=\emptyset$ and $S(2)=\\{1\\}$. Then
$v^{\prime}_{\\{1\\}}=v^{\prime}_{\\{2\\}}=0$, $v^{\prime}_{\\{1,2\\}}=1$ and
thus $\phi_{1}(v^{\prime})=\phi_{2}(v^{\prime})=1/2$.

Suppose $\omega=(\omega_{1},\omega_{2})$ satisfies
$\phi^{\omega}_{i}(v)=\phi_{i}(v^{\prime})$ for $i=1,2$. This implies that (i)
$\frac{\omega_{1}\cdot 0}{\omega_{1}}=\frac{1}{2}$, (ii)
$\frac{\omega_{2}\cdot 1}{\omega_{2}}=\frac{1}{2}$, which has no solution to
$(\omega_{1},\omega_{2})$. Therefore, such a weight $\omega$ cannot exist. ∎

######  Lemma 2.

There exists a cooperative game $v$ with a weight
$\omega\in\mathbb{R}^{|\mathcal{N}|}_{+}$ such that there is no permission
structure $S$ that satisfies

$\forall i\in\mathcal{N},\qquad\phi_{i}(v^{\prime})=\phi^{\omega}_{i}(v)$

where $v^{\prime}$ is the $v$’s projection on $S$.

###### Proof.

Consider the characteristic function $v$ on the player set $\\{1,2\\}$:
$v_{\\{1\\}}=1$, $v_{\\{2\\}}=2$ and $v_{\\{1,2\\}}=4$; and the weight
$\omega$: $\omega_{1}=1$, $\omega_{2}=3$. Then
$\phi^{\omega}_{1}(v)=\frac{5}{4}$ and $\phi^{\omega}_{2}(v)=\frac{11}{4}$.

There are only three different permission structures on $\\{1,2\\}$:

  1. 1.

$S$: $S(1)=S(2)=\emptyset$. In this case, $\phi^{\prime}_{1}=\frac{3}{2}$ and
$\phi^{\prime}_{2}=\frac{5}{2}$.

  2. 2.

$S$: $S(1)=\emptyset$, $S(2)=\\{1\\}$. In this case,
$\phi^{\prime}_{1}=\frac{5}{2}$ and $\phi^{\prime}_{2}=\frac{3}{2}$.

  3. 3.

$S$: $S(1)=\\{2\\}$, $S(2)=\emptyset$. In this case, $\phi^{\prime}_{1}=1$ and
$\phi^{\prime}_{2}=3$.

Thus, there is no permission structure $S$ satisfies
$\phi_{i}(v^{\prime})=\phi^{\omega}_{i}(v)$ for $i=1,2$. ∎

Intuitively, the permission structure shows some kinds of “external” relations
of the players: how players are connected in a social network; while the
weights show some “internal” relations: which player takes a more important
role in a coalition. Thus, these two solution concepts are of different
classes. In our reward distribution mechanism, we may want to consider not
only the “external” structures but also “internal” relations between players
involved. Therefore, we introduce the weighted Shapley value with the
permission structure.

######  Definition 8.

For a cooperative game $v$ on the player set $\mathcal{N}$, given a permission
structure $S$ and a weight $\omega\in\mathbb{R}^{|\mathcal{N}|}_{+}$, the
weighted Shapley value with permission structure for a player
$i\in\mathcal{N}$ is:

$\phi^{\omega,S}_{i}(v)=\sum_{E\in
A_{S}}\left(\sum_{F:\lambda(F)=E}d^{v}(F)\right)\phi^{\omega}_{i}(u_{E})$

We now show the mechanism given by the DARPA winning team can be expressed as
the weighted Shapley value with permission structure as follows:

  1. 1.

$S$ is the tree structure i.e., for each $i$, $S(i)=p(i)$ ($p(i)$ is the
parent set of $i$);

  2. 2.

for each $i$,

$\omega_{i}=\begin{cases}1&\text{if }d_{i}=0\\\
2^{d_{i}-1}&\text{otherwise}\\\ \end{cases}$

where $d_{i}$ is the depth of player $i$ in the tree.

We can verify that the result of this weighted Shapley value with permission
structure is just the same as the mechanism given by DARPA winning team.
Furthermore, we suggest a family of mechanisms to cooperative games in a tree.

  1. 1.

Let $S$ be the tree structure i.e., for each $i$, $S(i)=p(i)$ ($p(i)$ is the
parent set of $i$);

  2. 2.

for each $i$, $\omega_{i}=f(d_{i})$, where $d_{i}$ is the depth of player $i$
in the tree and $f:\mathbb{N}\rightarrow\mathbb{R}_{+}$ is any positive
function.

  3. 3.

Output $\mathcal{M}(G,v)=\phi^{\omega,S}(v)$

In the special case where $f$ is a constant function, the mechanism
degenerates to the Shapley value with permission structure. The following two
examples show different cases when applying different $f$ functions.

######  Example 2.

For the cooperative game $v$ and the tree structure shown in Figure 1, use the
weighted Shapley value with permission structure and let $\omega$ be:

$\omega_{i}=\begin{cases}1&\text{if }d_{i}=0\\\
d_{i}&\text{otherwise}\end{cases}$

where $d_{i}$ is the depth for each player $i$. Then the reward distributed to
each player is:

$\begin{cases}\phi^{\omega,S}_{f}=3/7,\quad\phi^{\omega,S}_{c}=2/7,\quad\phi^{\omega,S}_{a}=1/7\\\
\phi^{\omega,S}_{e}=1/2,\quad\phi^{\omega,S}_{b}=1/4\\\
\phi^{\omega,S}_{r}=11/28\\\
\phi^{\omega,S}_{d}=\phi^{\omega,S}_{g}=\phi^{\omega,S}_{h}=0\end{cases}$

######  Example 3.

For the cooperative game $v$ and the tree structure shown in Figure 1, use the
weighted Shapley value with permission structure and let
$\omega_{i}=2^{-d_{i}}$, where $d_{i}$ is the depth for each player $i$. Then
the reward distributed to each player is:

$\begin{cases}\phi^{\omega,S}_{f}=1/15,\quad\phi^{\omega,S}_{c}=2/15,\quad\phi^{\omega,S}_{a}=4/15\\\
\phi^{\omega,S}_{e}=1/7,\quad\phi^{\omega,S}_{b}=2/7\\\
\phi^{\omega,S}_{r}=116/105\\\
\phi^{\omega,S}_{d}=\phi^{\omega,S}_{g}=\phi^{\omega,S}_{h}=0\end{cases}$

Note that the reward distribution in this case is some kind of reverse version
of the DARPA winning team solution.

Again, to see the intuition of the mechanism, consider the special case for
the additive characteristic function $v$ in a tree. Denote $v(\\{i\\})$ by
$v_{i}$, and the subtree rooted by $i$ by $T_{i}$. Then the weighted Shapley
value with permission structure and weight $\omega:\omega_{i}=f(d_{i})$ of the
player $i$ is:

$\phi^{\omega,S}_{i}=\sum_{k\in
T_{i}}\frac{f(d_{i})}{\sum_{j=0}^{d_{k}}f(j)}v_{k}$

Precisely speaking, the reward will be distributed along the invitation chain
according to the ratio of the weights rather than uniformly divided. Now we
show that using a mechanism from our proposed family as the reward
distribution mechanism, all players will be incentivized to invite their
neighbours to join the coalition.

######  Theorem 1.

For the additive cooperative game in a tree, if the reward distribution
mechanism $\mathcal{M}$ is a member of the family of the weighted Shapley
value with permission structure, then $\mathcal{M}$ is efficient and DIC.

###### Proof.

The efficiency can be easily derived since it is a variation of the Shapley
value.

For the diffusion compatibility, similar to the proof in Proposition 1, the
total contribution of player $i$ without inviting player $j$ is a weighted sum
of contributions in all orders without $j$. If $i$ does invite $j$, for each
order where $j$ comes after $i$, the marginal contribution of $i$ will not
change; for each order $j$ comes before $i$, the marginal contribution of $i$
is increased by either $v_{j}$ or $0$. Suppose $R$ is an order in
$\mathcal{R}(\mathcal{N}\setminus\\{j\\})$, and $R_{j}^{p}$ is the order with
$j$ inserts at position $p$ in $R$. Then

$\sum_{p}w^{\prime}_{R_{j}^{p}}C_{i}(v^{\prime},R_{j}^{p})\geq\sum_{p}w^{\prime}_{R_{j}^{p}}C_{i}(v^{\prime},R)=w^{\prime}_{R}C_{i}(v^{\prime},R)$

Here, $w^{\prime}$ is the weight of the orders, which can be computed from
weights $\omega$ Kalai and Samet (1987) and
$\sum_{p}w^{\prime}_{R_{j}^{p}}=w^{\prime}_{R}$ since all the players’ weight
do not change (the weight only depends on the depth) except $j$’s. Note that
the left-hand term is player $i$’s reward after inviting $j$ while the right-
hand term is $i$’s reward without inviting $j$. Thus, the reward of $i$ when
she invites $j$ is no less than that when she does not invite $j$.

Therefore, the mechanism from our proposed family is DIC. ∎

For the general cases where the cooperative game is monotone, the marginal
contribution after inviting a new player is still non-negative. Hence, we can
directly derive the following corollary.

######  Corollary 2.

For the monotone game in a tree, if the reward distribution mechanism
$\mathcal{M}$ is a member of the family of the weighted Shapley value with
permission structure, then $\mathcal{M}$ is efficient and DIC.

##  4 From Tree to DAG

In this section, we extend our result in the tree model to a general DAG
model. An instance of a cooperative game in a DAG where an player may be
invited by several other players is shown in Example 4 below.

######  Example 4.

Consider the case where the initial players $r_{1}$ and $r_{2}$ wants to
invite more players to their project, i.e., $\mathcal{I}=\\{r_{1},r_{2}\\}$.
As illustrated in Figure 2, firstly $r_{1}$ asks to her friends $a$ and $c$
and $r_{2}$ asks to her friends $b$ and $c$. Then $a$, $b$ and $c$ further
propagate the query to their friends and so on. Each player may be informed
several times, then finally, the structure constructed via diffusion will
become a DAG with source nodes $r_{1}$ and $r_{2}$. The player $c$ will
participate in the project if $r_{2}$ invites her or $r_{1}$ and $a$ both
invite her and the player $e$ will participate in the project if $b$ invites
her or $c$ and $d$ both invite her.

$c$$r_{1}$$r_{2}$$a$$b$$d$$e$ Figure 2: An example of a cooperative game in
DAG. The green nodes are initial players.

Suppose for $\mathcal{N}=\\{r_{1},r_{2},a,b,c,d,e\\}$, the characteristic
function $v$ will be:

$v(E)=\begin{cases}2&\text{if }e\in E\\\ 1&\text{if }\\{r_{1},r_{2}\\}\cap
E\neq\emptyset,e\notin E\\\ 0&\text{otherwise}\end{cases}$

for every $E\subset\mathcal{N}$.

###  4.1 Permission Structure with Mixed Approach

Note that there is no existed approach of permission structure can handle the
case in Example 4. Hence to generalize the result in a tree to DAG, we first
propose the permission structure with mixed approach.

A permission structure with mixed approach $\varrho$ on $\mathcal{N}$ is a
pair $(S,\Phi)$ where $S$ is a mapping $\mathcal{N}\rightarrow
2^{\mathcal{N}}$. The mapping $S$ is asymmetric, i.e., for any pair $i$,
$j\in\mathcal{N}$, $j\in S(i)$ implies that $i\notin S(j)$ and $j$ is called a
superior of $i$. On the other hand, define $S^{-1}(i)=\\{j\in\mathcal{N}\mid
i\in S(j)\\}$ as the set of $i$’s successors. We assume that $S$ is acyclic,
which means the set $H_{S}=\\{i\in\mathcal{N}\mid S(i)=\emptyset\\}$ is not
empty. The set $\Phi=\\{\varphi_{i}\mid i\in\mathcal{N}\\}$ consists of
players’ satisfiable expressions. For a coalition $E\subset\mathcal{N}$, the
expression set $L_{E}$ is recursively defined as following:

  1. 1.

$i\in L_{E}$ for any $i\in E$;

  2. 2.

$a\vee b\in L_{E}$ for any $a$, $b\in L_{E}$;

  3. 3.

$a\wedge b\in L_{E}$ for any $a$, $b\in L_{E}$.

Given an expression $\varphi\in L_{E}$ and a coalition $F\in\mathcal{N}$, the
evaluation $\varphi(F)$ is the boolean result of $\varphi$ when $i=1$ if $i\in
F$ and $i=0$ otherwise for any $i\in E$. Then for $i\in\mathcal{N}$, her
satisfiable expression $\varphi_{i}\in L_{S(i)}$, indicates how her superiors
hold the authority of permission: only when $\varphi_{i}$ is true, $i$ can get
the permission to create value. In the special case that $i\in H_{S}$,
$\varphi_{i}$ is always true since $i$ does not need any others’ permission.
For instance, in Example 4, $\phi_{c}=r_{2}\vee(r_{1}\wedge a)$ and
$\phi_{e}=b\vee(c\wedge d)$.

Under this generalized permission structure, a coalition can be formed
independently if all members in the coalition can get permission.

######  Definition 9.

A coalition $E\subset\mathcal{N}$ is autonomous in the permission structure
$\varrho=(S,\Phi)$ if for any $i\in E$, $\varphi_{i}(E)=1$. The set of all
autonomous coalition in $\varrho$ is denoted by $A_{\varrho}$.

The set $A_{\varrho}$ satisfies the following property naturally:

######  Lemma 3.

Let $\varrho$ be a permission structure on $\mathcal{N}$, then (i)
$\emptyset\in A_{\varrho}$, (ii) $N\in A_{\varrho}$ and (iii) for every
$E,F\in A_{\varrho}$, $E\cup F\in A_{\varrho}$.

###### Proof.

(i) Since there is no $i\in\emptyset$, then $\emptyset\in A_{\varrho}$. (ii)
for any $\varphi\in L_{E}$, $E\subset\mathcal{N}$, $\varphi(\mathcal{N})=1$
since all variables are true. Thus, $\mathcal{N}\in A_{\varrho}$. (iii) for
any $i\in E\cup F$, if $i\in E$, $\varphi_{i}(E)=1$ implies $\varphi_{i}(E\cup
F)=1$ since more variables get true; if $i\in F$, similarly we have
$\varphi_{i}(E\cup F)=1$. Thus, $E\cup F\in A_{\varrho}$. ∎

Since $A_{\varrho}$ is closed when taking union, the definition of an
autonomous part of a coalition can be directly given as follows:

######  Definition 10.

Let $\varrho$ be a permission structure on $\mathcal{N}$. Then the autonomous
part of a coalition $E\subset\mathcal{N}$ is defined by:

$\alpha(E)=\bigcup\\{F\mid F\subset E\text{ and }F\in A_{\varrho}\\}$

Note that $\alpha(E)\in A_{\varrho}$ and it is the largest autonomous sub-
coalition of $E$, which suggests that for any player $i\in
E\backslash\alpha(E)$, she cannot get permission to create value in coalition
$E$. On the other hand, we consider the minimal autonomous coalitions that
contains $E$:

######  Definition 11.

Let $\varrho$ be a permission structure on $\mathcal{N}$. Then
$F\subset\mathcal{N}$ is an authorizing coalition of a coalition
$E\subset\mathcal{N}$ if (i) $F\in A_{\varrho}$, (ii) $E\subset F$ and (iii)
for any $G\in A_{\varrho}$, $E\subset G\subset F\Rightarrow G=F$. Denote the
set of all authorizing coalitions of $E$ by $\Lambda(E)$.

According to Lemma 3, the union of autonomous coalitions is still autonomous.
Thus a special set of coalitions that contains $E$ is considered as
$\Lambda^{*}(E)=\\{F=\cup_{i=1}^{m}F_{m}\mid F_{i}\in\Lambda(E),1\leq i\leq
m,m\in\mathbb{Z}^{+}\\}$. Clearly, $\Lambda^{*}(E)\subset A_{\varrho}$.

The mixed permission structure introduces a mapping $\mathcal{P}_{\varrho}$
that transform a cooperative game $v$ to a new characteristic function
$v^{\prime}$, where $v^{\prime}$ is called the permission restriction of $v$
on $\varrho$. Obviously, for every coalition $E\subset\mathcal{N}$, we have
$\mathcal{P}_{\varrho}(v)(E)=v(\alpha(E))$.

######  Theorem 2.

For characteristic function $v$ and permission structure $\varrho$, the
permission restriction will be

$\mathcal{P}_{\varrho}(v)=\sum_{E\subset
A_{\varrho}}\left(\sum_{F:E\in\Lambda^{*}(F)}d^{\mathcal{P}_{\varrho}(u_{F})}(E)\cdot
d^{v}(F)\right)u_{E}$

###### Proof.

First we consider $\mathcal{P}_{\varrho}(u_{E})$. Consider a non-empty
coalition $F\subset N$: define $\lambda_{E}(F)=\cup\\{G\mid
G\in\Lambda(E)\text{ and }G\subset F\\}$. If $\lambda_{E}(F)=\emptyset$, we
directly know that $E\backslash\alpha(F)\neq\emptyset$ and hence
$d^{\mathcal{P}_{\varrho}(u_{E})}(F)=0$.

If $\lambda_{E}(F)\neq\emptyset$, we directly know that
$\lambda_{E}(F)\in\Lambda^{*}(E)$. If $F\in\Lambda^{*}(E)$, then
$F\backslash\lambda_{E}(F)\neq\emptyset$. Take $i\in
F\backslash\lambda_{E}(F)$, then for every coalition $G\subset
F\backslash\\{i\\}$,
$\mathcal{P}_{\varrho}(u_{E})(G)-\mathcal{P}_{\varrho}(u_{E})(G\cup\\{i\\})=u_{E}(\alpha(G))-u_{E}(\alpha(G\cup\\{i\\}))=0$
and hence $d^{\mathcal{P}_{\varrho}(u_{E})}(F)=0$. In conclude,
$d^{\mathcal{P}_{\varrho}(u_{E})}(F)=0$ if $F\notin\Lambda^{*}(E)$. Therefore,
we can write that:

$\mathcal{P}_{\varrho}(u_{E})=\sum_{F\in\Lambda^{*}(E)}d^{\mathcal{P}_{\varrho}(u_{E})}(F)\cdot
u_{F}$

Then we can get the expression for the characteristic function $v$ as
following:

$\displaystyle\mathcal{P}_{\varrho}(v)$
$\displaystyle=\sum_{E\subset\mathcal{N}}d^{v}(E)\mathcal{P}_{\varrho}(u_{E})$
$\displaystyle=\sum_{E\subset\mathcal{N}}d^{v}(E)\left(\sum_{F\in\Lambda^{*}(E)}d^{\mathcal{P}_{\varrho}(u_{E})}(F)\cdot
u_{F}\right)$ $\displaystyle=\sum_{E\subset
A_{\varrho}}\left(\sum_{F:E\in\Lambda^{*}(F)}d^{\mathcal{P}_{\varrho}(u_{F})}(E)\cdot
d^{v}(F)\right)u_{E}$

∎

From Theorem 2 we can know that the results of permission structure with
conjunctive or disjunctive approach are indeed the special cases of the mixed
approach. We will see that the permission restriction will preserve the
properties of monotone and super-additive.

######  Definition 12.

A game $v$ is super-additive if $\forall E$, $F\subset\mathcal{N}$ with $E\cap
F=\emptyset$, we have $v(E)+v(F)\leq v(E\cup F)$.

######  Theorem 3.

Let $v$ be a characteristic function of a monotone cooperative game and
$\varrho$ be a permission structure on $\mathcal{N}$, then (i)
$\mathcal{P}_{\varrho}(v)$ is a monotone game; (ii) if $v$ is super-additive,
then $\mathcal{P}_{\varrho}(v)$ is super-additive.

###### Proof.

(i) For $E,F\subset\mathcal{N}$ with $E\subset F$,
$\alpha(E)\subset\alpha(F)$, then

$\mathcal{P}_{\varrho}(v)(E)=v(\alpha(E))\leq
v(\alpha(F))=\mathcal{P}_{\varrho}(v)(F)$

(ii) For $E,F\subset\mathcal{N}$ with $E\cap F=\emptyset$,
$\alpha(E)\cap\alpha(F)=\emptyset$, then

$\displaystyle\mathcal{P}_{\varrho}(v)(E)+\mathcal{P}_{\varrho}(v)(F)$
$\displaystyle=v(\alpha(E))+v(\alpha(F))$ $\displaystyle\leq
v(\alpha(E)\cup\alpha(F))\leq v(\alpha(E\cup F))$
$\displaystyle=\mathcal{P}_{\varrho}(v)(E\cup F)$

∎

###  4.2 Weighted Shapley Value on Permission Structure

At last, we introduce weighted Shapley value with mixed permission structure
as a larger class of solution concept beyond these two special cases.

######  Definition 13.

For a cooperative game $v$ on the player set $\mathcal{N}$, given a permission
structure $\varrho$ and a weight $\omega\in\mathbb{R}^{|\mathcal{N}|}_{+}$,
the weighted Shapley value with mixed permission structure for a player
$i\in\mathcal{N}$ is:

$\phi^{\omega,\varrho}_{i}(v)=\sum_{E\subset
A_{\varrho}}\left(\sum_{\begin{subarray}{c}F:\\\
E\in\Lambda^{*}(F)\end{subarray}}d^{\mathcal{P}_{\varrho}(u_{F})}(E)\cdot
d^{v}(F)\right)\phi^{\omega}_{i}(u_{E})$

If applying the weighted Shapley value with mixed permission structure on the
cooperative game in Example 4 and letting $\omega=1^{|\mathcal{N}|}$, then the
reward distributed to each player is:

$\begin{cases}\phi^{\omega,\varrho}_{r_{1}}=11/15\\\
\phi^{\omega,\varrho}_{r_{2}}=2/3\\\
\phi^{\omega,\varrho}_{a}=\phi^{\omega,\varrho}_{c}=\phi^{\omega,\varrho}_{d}=\phi^{\omega,\varrho}_{e}=1/15\\\
\phi^{\omega,\varrho}_{b}=1/3\\\ \end{cases}$

Intuitively, the reward is distributed on all paths from the initial players
to the other players.

Finally, we give the family of reward distribution mechanism in a DAG:

  1. 1.

Let $\varrho=(S,\Phi)$, where $S$ is the structure of DAG and $\Phi$ is the
permission requirements;

  2. 2.

for each $i$, $\omega_{i}=f(d_{i})$, where $d_{i}$ is the distance of player
$i$ to the initial players $\mathcal{I}$ in the graph, i.e. the minimum
distance between $i$ to one of the initial players
($\min_{j\in\mathcal{I}}\\{d_{ji}\\}$) and
$f:\mathbb{N}\rightarrow\mathbb{R}_{+}$ is any positive and monotone
decreasing function.

  3. 3.

Output $\mathcal{M}(G,v)=\phi^{\omega,\varrho}(v)$

Similar to the mechanisms in a tree, we can conclude that this family of
mechanisms will incentive players to propagate the task to their neighbours.

######  Theorem 4.

For the monotone game in a DAG, if the reward distribution mechanism
$\mathcal{M}$ is a member of the family of weighted Shapley value with mixed
permission structure, then $\mathcal{M}$ is efficient and DIC.

###### Proof.

The efficiency can be easily derived since it is a variation of the Shapley
value.

For the diffusion compatibility, if we consider each player $i$ and edge
$e=(i,j)\in\mathcal{E}$, there are two cases that may happen if $i$ does not
invite $j$.

(i) if $j$ cannot join the coalition, the proof is similar to the Theorem 1
that shows player $i$ will not get more reward without inviting $j$.

(ii) if $j$ still can join the coalition, suppose $R$ is an order in
$\mathcal{R}(\mathcal{N})$. Let $v^{\prime}$ be the projection game when $i$
does invite $j$ and $v^{\prime\prime}$ be the projection game when $i$ does
not invite $j$, then

$\begin{cases}C_{i}(v^{\prime},R)=C_{i}(v^{\prime\prime},R)&\text{if }i\text{
comes before }j\text{ in }R\\\ C_{i}(v^{\prime},R)\geq
C_{i}(v^{\prime\prime},R)&\text{if }j\text{ comes before }i\text{ in
}R\end{cases}$

The above inequality holds because (1) if $i$ is at the position before $j$,
the marginal contribution of $i$ unchanged; (2) if $i$ is at the position
after $j$, the marginal contribution is decreased by $c$: $v(\\{j\\})\geq
c\geq 0$ when $i$ does not invite $j$. Noting that $d_{k}$ will not change for
any player $k\neq j$. Let $d_{j}^{\prime}$ be the distance of player $j$ to
initial players if $i$ does not invite $j$ and hence $d_{j}^{\prime}\geq
d_{j}$. Thus, (1) if $d_{j}^{\prime}=d_{j}$, then the weights of all players
will not change and so do the weights of the orders $w$, which can be computed
from weights $\omega$ Kalai and Samet (1987). Hence we have

$\phi_{i}^{\omega,\varrho}=\sum_{R\in\mathcal{R}(\mathcal{N})}w_{R}C_{i}(v^{\prime},R)\geq\sum_{R\in\mathcal{R}(\mathcal{N})}w_{R}C_{i}(v^{\prime\prime},R)=\bar{\phi}_{i}^{\omega,\varrho}$

where $\phi_{i}^{\omega,\varrho}$ is player $i$’s reward when she invites $j$
and $\bar{\phi}_{i}^{\omega,\varrho}$ is player $i$’s reward when she does not
invite $j$. (2) if $d_{j}^{\prime}>d_{j}$, then note that we must have
$d_{i}<d_{j}$. Since the function $f$ is monotone decreasing, then
$f(d_{i})\geq f(d_{j})\geq f(d_{j}^{\prime})$. Let
$R_{ij}\in\mathcal{R}(\mathcal{N})$ be some order where $i$ comes before $j$
and $R_{ji}$ is the order where $i$ and $j$’s positions are exchanged.
According to the computation for weights of orders Kalai and Samet (1987), we
have
$\frac{w(R_{ij})}{w(R_{ji})}\geq\frac{w^{\prime}(R_{ij})}{w^{\prime}(R_{ji})}$.
Hence we have

$\displaystyle\phi_{i}^{\omega,\varrho}$
$\displaystyle=\sum_{R_{ij}\in\mathcal{R}(\mathcal{N})}w_{R_{ij}}C_{i}(v^{\prime},R)+\sum_{R_{ji}\in\mathcal{R}(\mathcal{N})}w_{R_{ji}}C_{i}(v^{\prime},R)$
$\displaystyle\geq\sum_{R_{ij}\in\mathcal{R}(\mathcal{N})}w^{\prime}_{R_{ij}}C_{i}(v^{\prime\prime},R)+\sum_{R_{ji}\in\mathcal{R}(\mathcal{N})}w^{\prime}_{R_{ji}}C_{i}(v^{\prime\prime},R)$
$\displaystyle=\bar{\phi}_{i}^{\omega,\varrho}$

Therefore, the reward of $i$ when she invites $j$ is no less than that when
she does not invite $j$. As a result, $\mathcal{M}$ is DIC. ∎

##  5 Conclusion

In this paper, we formalize the problem of diffusion incentives in cooperative
games for the first time. We design a family of reward distribution mechanisms
such that players are incentivized to invite their neighbours to join the
coalition. The family of reward distribution mechanisms combines the idea of
the Shapley value with permission structure and weight system, which well
explains the classic solution given by the winning team of DARPA 2009 red
balloon challenge. To make our solution more applicable to a broader settings,
we also proposed a generalized approach to permission structure. Our work has
very promising applications via social networks such as resource acquisition
and question answering. One interesting future direction is to characterize
the necessary and sufficient conditions for diffusion incentive compatibility.
We also believe that our solutions cover almost all DIC mechanisms for DAGs.

## References

  * Chalkiadakis et al. [2011] Georgios Chalkiadakis, Edith Elkind, and Michael Wooldridge.  Computational aspects of cooperative game theory.  Synthesis Lectures on Artificial Intelligence and Machine Learning, 5(6):1–168, 2011.
  * Chun [1991] Youngsub Chun.  On the symmetric and weighted shapley values.  International Journal of Game Theory, 20(2):183–190, 1991.
  * Dragan [2008] Irinel C Dragan.  On the computation of weighted shapley values for cooperative tu games.  Technical report, University of Texas at Arlington, 2008.
  * Emek et al. [2011] Yuval Emek, Ron Karidi, Moshe Tennenholtz, and Aviv Zohar.  Mechanisms for multi-level marketing.  In Proceedings of the 12th ACM conference on Electronic commerce, pages 209–218. ACM, 2011.
  * Gilles et al. [1992] Robert P Gilles, Guillermo Owen, and Rene van den Brink.  Games with permission structures: the conjunctive approach.  International Journal of Game Theory, 20(3):277–293, 1992.
  * Gilles et al. [1999] Robert P Gilles, Guillermo Owen, et al.  Cooperative games and disjunctive permission structures.  Tilburg University Tilburg, the Netherlands, 1999.
  * Harsanyi [1959] John C Harsanyi.  A bargaining model for the cooperative n-person game.  Contributions to the Theory of Games, 4:325–355, 1959.
  * Jeong et al. [2013] Jin-Woo Jeong, Meredith Ringel Morris, Jaime Teevan, and Dan Liebling.  A crowd-powered socially embedded search engine.  In Seventh International AAAI Conference on Weblogs and Social Media, 2013.
  * Kalai and Samet [1987] Ehud Kalai and Dov Samet.  On weighted shapley values.  International Journal of Game Theory, 16(3):205–222, 1987.
  * Kleinberg and Raghavan [2005] Jon Kleinberg and Prabhakar Raghavan.  Query incentive networks.  In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), pages 132–141. IEEE, 2005.
  * Li et al. [2017] Bin Li, Dong Hao, Dengji Zhao, and Tao Zhou.  Mechanism design in social networks.  In Thirty-First AAAI Conference on Artificial Intelligence, 2017\.
  * Narahari [2014] Yadati Narahari.  Game theory and mechanism design, volume 4.  World Scientific, 2014.
  * Nisan et al. [2007] Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V Vazirani.  Algorithmic game theory.  Cambridge university press, 2007.
  * Pickard et al. [2011] Galen Pickard, Wei Pan, Iyad Rahwan, Manuel Cebrian, Riley Crane, Anmol Madan, and Alex Pentland.  Time-critical social mobilization.  Science, 334(6055):509–512, 2011.
  * Radzik [2012] Tadeusz Radzik.  A new look at the role of players’ weights in the weighted shapley value.  European Journal of Operational Research, 223(2):407–416, 2012\.
  * Shapley [1953] Lloyd S Shapley.  A value for n-person games.  Contributions to the Theory of Games, 2(28):307–317, 1953.
  * Singla et al. [2015] Adish Singla, Eric Horvitz, Pushmeet Kohli, Ryen White, and Andreas Krause.  Information gathering in networks via active exploration.  In Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015.
  * Sinha and Wellman [2019] Arunesh Sinha and Michael P Wellman.  Incentivizing collaboration in a competition.  In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pages 556–564. International Foundation for Autonomous Agents and Multiagent Systems, 2019.
  * van den Brink and Gilles [1996] René van den Brink and Robert P Gilles.  Axiomatizations of the conjunctive permission value for games with permission structures.  Games and Economic Behavior, 12(1):113–126, 1996.
  * Van Den Brink [1997] René Van Den Brink.  An axiomatization of the disjunctive permission value for games with a permission structure.  International Journal of Game Theory, 26(1):27–43, 1997.
  * van den Brink [2010] René van den Brink.  Axiomatizations of banzhaf permission values for games with a permission structure.  International Journal of Game Theory, 39(3):445–466, 2010.
  * Winter [2002] Eyal Winter.  The shapley value.  Handbook of game theory with economic applications, 3:2025–2054, 2002.
  * Zhao et al. [2018] Dengji Zhao, Bin Li, Junping Xu, Dong Hao, and Nicholas R Jennings.  Selling multiple items via social networks.  In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pages 68–76. International Foundation for Autonomous Agents and Multiagent Systems, 2018.


:
LEAVE UNSET 2021 LEAVE UNSET LEAVE UNSET Machine Learning for Health (ML4H)
2021

# Brain dynamics via Cumulative Auto-Regressive Self-Attention

Usman Mahmood<EMAIL_ADDRESS>
Zening Fu<EMAIL_ADDRESS>
Vince Calhoun vcalhoun.gsu.edu
Sergey Plis<EMAIL_ADDRESS>
Tri-institutional Center for Translational Research in Neuroimaging and Data
Science (TReNDS)  Georgia State University  Georgia Tech  Emory

###### Abstract

Multivariate dynamical processes can often be intuitively described by a
weighted connectivity graph between components representing each individual
time-series. Even a simple representation of this graph as a Pearson
correlation matrix may be informative and predictive as demonstrated in the
brain imaging literature. However, there is a consensus expectation that
powerful graph neural networks (GNNs) should perform better in similar
settings. In this work we present a model that is considerably shallow than
deep GNNs, yet outperforms them in predictive accuracy in a brain imaging
application. Our model learns the autoregressive structure of individual time
series and estimates directed connectivity graphs between the learned
representations via a self-attention mechanism in an end-to-end fashion. The
supervised training of the model as a classifier between patients and controls
results in a model that generates directed connectivity graphs and highlights
the components of the time-series that are predictive for each subject. We
demonstrate our results on a functional neuroimaging dataset classifying
schizophrenia patients and controls.

###### keywords:

Structure Learning, functional MRI, Schizophrenia, Classification

##  1 Introduction

Study and predictive diagnostics of mental disorders have been a growing area
of research Lynall et al. (2010); Khosla et al. (2019); Plis et al. (2014);
Mahmood et al. (2021). The research focuses on building classification models
for such disorders in the hope to learn disease specific regions and their
interaction. Abnormal function of specific brain regions is often a
characteristic of specific mental disorder of the subject Jones et al. (2012);
Fu et al. (2021); Ebdrup et al. (2010); Andreasen and Pierson (2008). Often
these two research problems—classification and brain region interactions
(FNC)—are handled separately. Approaches that create a single method to handle
these two problems simultaneously remain vastly unexplored.

In this paper, we use resting state functional magnetic resonance imaging (rs-
fMRI)—spatio-temporal brain data—and present an approach that simultaneously
classifies schizophrenia subjects from healthy controls, and learns the
effective connectivity structure (graph) among different components/regions.

We present an approach to learn brain regions’ interaction as a graph learning
method. In this graph, different fMRI regions/components represent nodes and
their interaction/connectivity serve as edge weights. As, the underlying
ground truth graph structure is missing, our method could be considered an un-
supervised graph learning approach. However, as the training is supervised,
although to a different task, it is more precisely classified as a self-
supervised method. Our proposed approach can also be considered as graphical
representation learning. The input data consist of components created using
independent component analysis (ICA) on rs-fMRI data (see Section 2.4).

Existing unsupervised and self-supervised graph learning methods Kipf et al.
(2018); Shang et al. (2021) often rely on predicting future values in time of
the components/objects in the space they are defined using the learned graph
structure. Learning is performed by maximizing similarity between prediction
and the ground truth time courses. The problem with these approaches,
especially for fMRI, is that predicting future very far in time is
significantly more difficult for real than for simulated data because of the
presence of noise, and many features which are responsible of future values,
are often missing from input data. Also, the variance in input values is not
that large. As shown in the experiments of Kipf et al. (2018), one gets a very
small error by just keeping future values equal to current value. The error is
even smaller for fMRI data as the variance is of much smaller magnitude than
the simulated data used in Kipf et al. (2018). Lastly, the effect of the
learned graph on classification remains unknown by just decreasing prediction
loss, and because of un-supervised learning the efficacy of the learned graph
in terms of classification remains unclear as the ground truth graph is not
available.

We turn the problem into graph classification, and with high classification
accuracy we can rely on the learned graph structure. Since classifying mental
disorders is a significantly more difficult task than predicting few time
points in future, the learned graph structure can be trusted with higher
confidence. Finally, we use a selection method to select a sparse set of
important nodes (referred as components/regions in the paper) for
classification. Recently, there has been a surge of research in GNNs and many
models have been proposed Zhang and Chen (2018); Parisot et al. (2018); Kazi
et al. (2018); Kipf and Welling (2017); Bianchi et al. (2021); Ying et al.
(2018); Zhang et al. (2018). These models are used for different tasks and can
be easily modified for graph classification. GNN models are often deep and
have multiple GNN layers/steps, to gather information from distant neighbors.
Most of the GNNs models used for graph classification task (GCT) are
supervised and assume that the underline true graph structure of data is
available, which is highly unlikely in many cases. Such models can be used by
assuming a complete graph, but can greatly impact classification performance.

In this paper, we show that to simultaneously learn and classify a graph
structure, a traditional deep GNN model is not required. We present a
relatively shallow model (in terms of learned parameters) which demonstrates
remarkable performance. Our method relies on cumulative auto-regressive
representations obtained from individual time series using a recurrent neural
network, which are subsequently recombined via a self-attention mechanisms. We
call our model CARSA for cumulative auto-regressive self-attention. An
application to an fMRI dataset demonstrates its efficacy.

##  2 CARSA architecture

We present CARSA as an end-to-end learning architecture based on
classification to learn functional connectivity between components. Our model
first learns the effective connectivity between time courses of an individual
component’s sequence. Learning the connectivity helps in creating a single
embedding of the entire sequence which incorporates the effects a sequence
through time. We use bidirectional long-short term memory (biLSTM) Schuster
and Paliwal (1997) to learn these relations between time courses occurring in
succession. With the learned embeddings of the sequences we apply the same
concept which we used across time courses to sequence embeddings.

Unlike time courses of a sequence, different sequences are not successive,
rather a sequence can have relation with any single or multiple other
sequences. The connectivity between sequences can be represented as functional
connectivity or graph edge weights and we capture this connectivity via self-
attention based model presented in Vaswani et al. (2017). Finally, to acquire
subject specific discriminating sequences we use a learnable pooling method
Gao and Ji (2019); Knyazev et al. (2019). In our experiments we use encoded
rsfMRI ICA time courses as our sequences, with each subject having multiple
components. Refer to Figure 1 for complete architecture of our model. We
explain the architecture details including hyper-parameters and importance of
each important part in further sections. Our architecture is relatively a
shallow network which shows high performance which we consider as an advantage
over very deep neural networks.

###  2.1 LSTM for Single Components

We use a single layer biLSTM with hidden dimension of size $64$. The LSTM
receives $x^{i}_{t}$ at each time step. $x^{i}_{t}$ represents the ICA value
of component $i$ at time step $t$. $x^{i}_{t}$ is dependant on many factors,
one of them being the values of $x^{i}_{1...t-1}$. These relationships are
very hard to capture and unlike many other time series, can’t be computed
using a fixed method or formula. Also, it is unknown how farther in time a
component’s effect remains in the time series. Learning the effective
connectivity helps in identifying different time series which eventually leads
to better classification. LSTMs with the help of memory and forget gates
learns all these unknown factors and relationships. We learn these factors by
using an end-to-end learning by classifying subjects. The two hidden vectors
of the LSTM at step $s$ representing forward and backward passes are
concatenated to create a single vector $c^{i}_{t}$ for component $i$ at time
$t$. With $f_{\theta}$ representing LSTM with parameters $\theta$. This vector
can be presented as:

$\displaystyle c^{i}_{t}=f_{\theta}(x^{i}_{t}\ |\ f_{\theta}(x^{i}_{j})\ ;\
j=1\to t-1)$

Finally, to obtain a single vector for the complete sequence/time series for
component $i$ we sum all the vectors $c^{i}$’$s$.

$y^{i}=\sum_{t=1}^{n}c^{i}_{t}$

Figure 1: CARSA architecture. The architecture has three distinct parts. 1)
LSTM, 2) Self-Attention and 3) Pooling.

###  2.2 Self-Attention Across Components

To capture the effective connectivity between components we use a self-
attention model inspired from Vaswani et al. (2017), with embedding dimension
of size $64$. A self-attention module computes the weights between different
components and use that to create new embeddings $z^{i}$ for each component
$i$. As, mentioned before the components are not just affected by their
previous values but also by other components. This in terms of brain signals
can be seen as different brain regions affecting one other. In our data we
look to find the relationship between ICA components. This is known as
functional connectivity which is usually computed using Pearson product-moment
correlation coefficients (PCC) method, and can be used as edge weights for
graphs. We learn the functional connectivity, via an end to end learning of
classification. This provides insights into how these components interact with
each other in terms of downstream classification. With function $f_{\phi}$
representing the self-attention function with parameters $\phi$ The resultant
vector $z^{i}$ representing component $i$ of a subject can be represented as:

$\displaystyle z^{i}=f_{\phi}(y^{i}\ |\ y^{j}\ ;\ j=\ 1\to m)$

###  2.3 Pooling and FCN

Not all components are equally discriminating for classification. The
components can vary across subjects and diseases. To learn the important
components we select the top ’k’ components for each subject using top-k
pooling Gao and Ji (2019); Knyazev et al. (2019). We use 3 layers of such
pooling dropping $20\%$ components at each layer. To obtain a final vector for
the entire subject we use average pooling summing all the components after
each top-k pooling layer. In the end we sum the three vectors to create a
single vector representing a subject. For classification we use two fully
connected layers with size $64$ and $2$.

###  2.4 Dataset

We worked with the data from Function Biomedical Informatics Research Network
(FBIRN) Keator et al. (2016) dataset including SZ patients and HC for testing
our model. Resting fMRI data from the phase III FBIRN were analyzed for this
project. The dataset has $368$ total subjects.The fMRI data was preprocessed
using statistical parametric mapping (SPM12,
http://www.fil.ion.ucl.ac.uk/spm/) under MATLAB 2020 environment. After the
preprocessing, subjects were included in the analysis if the subjects have
head motion $\leq 3^{\circ}$ and $\leq 3$ mm, and with functional data
providing near full brain successful normalization Fu et al. (2019).

We selected subjects for further analysis if the subjects had head motion
$\leq 3^{\circ}$ and $\leq 3$ mm, and with functional data providing near full
brain successful normalization Fu et al. (2019).

This result in a total of $311$ subjects with $151$ healthy controls and $160$
subjects with schizophrenia. Lastly, $100$ ICA components are acquired using
the same procedure described in Fu et al. (2019).

fig:AUCcomparision

Figure 2: We show the mean and median of all trials across $4$ folds of cross
validation. Our model out-performs ML and DL methods.

fig:FC [FNC - Important Components] [FNC - Noise Components]

Figure 3: 3 shows the connectivity between the imporant components, grouped
into 7 domains. 3 shows the FNC between noise components. Our method
accurately depicts high connectivity between important components. Visual
components have high connectivity with components of all other domains. SC-
Subcortical, AU-Auditory, SM-Sensorimotor, VI-Visual, CC-Cognitive Control,
DM-Default Mode, and CB-Cerebellum.

###  2.5 Results

In our experiments we used 4 fold cross validation with training and
validation size of $\sim 80$. The division does not follow the common norm
because of the low number of subjects, and any further reduction of validation
or test data results in higher variance in the results but the average remains
same. We perform $10$ randomly seed trials for each fold.

Classification: The classification results in figure LABEL:fig:AUCcomparision
show the efficacy of our model with performance better than machine learning
deep learning methods Mahmood et al. (2020, 2021). BrainGNN uses region-based
data, we tried using ICA data with BrainGNN but we couldn’t make it work.

Functional connectivity:  Figure LABEL:fig:FC show the functional connectivity
learned via the attention part of the model. We divide the $100$ components
into important and noise category and further divide important components into
$7$ domains following Allen et al. (2011). These connectivity matrices can be
used as the graph structure between components by either a) using the matrix
directly as weights or b) creating a probabilistic graph structure using these
matrices as parameters.

##  3 Discussion & Future work

We present a novel and relatively shallow deep learning architecture which
provides state-of-the-art classification results for schizophrenia. Our model
learns the functional connectivity between rsfMRI ICA components which can be
used as a graph structure and hence result in an individual graph for each
subject. Learning connectivity/graph structure in an end to end fashion helps
us to not use a fixed method, as such methods does not provide high
classification or interpretable results.

The high classification result we obtained provides evidence that the
functional connectivity and sparse components learned by the model are correct
and are important, especially for classification.

For future work, we plan to look into the final regions selected by the
pooling method and compare those regions across healthy and schizophrenic
patients. We also plan to apply our method directly on rs-fMRI to not only
reduce but also find disease specific regions.

Data for Schizophrenia classification was used in this study were acquired
from the Function BIRN Data Repository
(http://bdr.birncommunity.org:8080/BDR/), supported by grants to the Function
BIRN (U24-RR021992) Testbed funded by the National Center for Research
Resources at the National Institutes of Health, U.S.A. and from the
Collaborative Informatics and Neuroimaging Suite Data Exchange tool (COINS;
http://coins.trendscenter.org). This work was in part supported by NIH grants
1RF1MH12188 and 2R01EB006841.

## References

  * Allen et al. (2011) Elena Allen, Erik Erhardt, Eswar Damaraju, William Gruner, Judith Segall, Rogers Silva, Martin Havlicek, Srinivas Rachakonda, Jill Fries, Ravi Kalyanam, Andrew Michael, Arvind Caprihan, Jessica Turner, Tom Eichele, Steven Adelsheim, Angela Bryan, Juan Bustillo, Vincent Clark, Sarah Feldstein Ewing, Francesca Filbey, Corey Ford, Kent Hutchison, Rex Jung, Kent Kiehl, Piyadasa Kodituwakku, Yuko Komesu, Andrew Mayer, Godfrey Pearlson, John Phillips, Joseph Sadek, Michael Stevens, Ursina Teuscher, Robert Thoma, and Vince Calhoun.  A baseline for the multivariate comparison of resting-state networks.  _Frontiers in Systems Neuroscience_ , 5:2, 2011.  ISSN 1662-5137.  10.3389/fnsys.2011.00002.  URL https://www.frontiersin.org/article/10.3389/fnsys.2011.00002.
  * Andreasen and Pierson (2008) Nancy Andreasen and Ronald Pierson.  The role of the cerebellum in schizophrenia.  _Biological psychiatry_ , 64:81–8, 08 2008.  10.1016/j.biopsych.2008.01.003.
  * Bianchi et al. (2021) Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi.  Graph neural networks with convolutional arma filters.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , pages 1–1, 2021.  10.1109/TPAMI.2021.3054830.
  * Ebdrup et al. (2010) Bjørn Ebdrup, Birte Glenthøj, Hans Rasmussen, Bodil Aggernaes, Annika Langkilde, Olaf Paulson, Henrik Lublin, Arnold Skimminge, and William Baaré.  Hippocampal and caudate volume reductions in antipsychotic-naive first-episode schizophrenia.  _Journal of psychiatry & neuroscience : JPN_, 35:95–104, 03 2010.  10.1503/jpn.090049.
  * Fu et al. (2019) Zening Fu, Arvind Caprihan, Jiayu Chen, Yuhui Du, John C Adair, Jing Sui, Gary A Rosenberg, and Vince D Calhoun.  Altered static and dynamic functional network connectivity in alzheimer’s disease and subcortical ischemic vascular disease: shared and specific brain connectivity abnormalities.  _Human Brain Mapping_ , 2019.  10.1002/hbm.24591.
  * Fu et al. (2021) Zening Fu, Jing Sui, Jessica A. Turner, Yuhui Du, Michal Assaf, Godfrey D. Pearlson, and Vince D. Calhoun.  Dynamic functional network reconfiguration underlying the pathophysiology of schizophrenia and autism spectrum disorder.  _Human Brain Mapping_ , 42(1):80–94, 2021.  https://doi.org/10.1002/hbm.25205.  URL https://onlinelibrary.wiley.com/doi/abs/10.1002/hbm.25205.
  * Gao and Ji (2019) Hongyang Gao and Shuiwang Ji.  Graph u-nets, 2019.
  * Jones et al. (2012) David Jones, Prashanthi Vemuri, Matthew Murphy, Jeffrey Gunter, Matthew Senjem, Mary Machulda, Scott Przybelski, Brian Gregg, Kejal Kantarci, David Knopman, Brad Boeve, Ronald Petersen, and Clifford Jack.  Non-stationarity in the “resting brain’s” modular architecture.  _PloS one_ , 7:e39731, 06 2012.  10.1371/journal.pone.0039731.
  * Kazi et al. (2018) Anees Kazi, S. Arvind krishna, Shayan Shekarforoush, Karsten Kortuem, Shadi Albarqouni, and Nassir Navab.  Self-attention equipped graph convolutions for disease prediction, 2018\.
  * Keator et al. (2016) David B Keator, Theo GM van Erp, Jessica A Turner, Gary H Glover, Bryon A Mueller, Thomas T Liu, James T Voyvodic, Jerod Rasmussen, Vince D Calhoun, Hyo Jong Lee, et al.  The function biomedical informatics research network data repository.  _Neuroimage_ , 124:1074–1079, 2016.  10.1016/j.neuroimage.2015.09.003.
  * Khosla et al. (2019) Meenakshi Khosla, Keith Jamison, Gia H Ngo, Amy Kuceyeski, and Mert R Sabuncu.  Machine learning in resting-state fMRI analysis.  _Magnetic resonance imaging_ , 2019.
  * Kipf et al. (2018) Thomas Kipf, Ethan Fetaya, Kuan-Chieh Wang, Max Welling, and Richard Zemel.  Neural relational inference for interacting systems, 2018.
  * Kipf and Welling (2017) Thomas N. Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks, 2017\.
  * Knyazev et al. (2019) Boris Knyazev, Graham W. Taylor, and Mohamed R. Amer.  Understanding attention and generalization in graph neural networks, 2019\.
  * Lynall et al. (2010) Mary-Ellen Lynall, Danielle S. Bassett, Robert Kerwin, Peter J. McKenna, Manfred Kitzbichler, Ulrich Muller, and Ed Bullmore.  Functional connectivity and brain networks in schizophrenia.  _Journal of Neuroscience_ , 30(28):9477–9487, 2010.  ISSN 0270-6474.  10.1523/JNEUROSCI.0333-10.2010.  URL https://www.jneurosci.org/content/30/28/9477.
  * Mahmood et al. (2020) Usman Mahmood, Md Mahfuzur Rahman, Alex Fedorov, Noah Lewis, Zening Fu, Vince D. Calhoun, and Sergey M. Plis.  Whole milc: Generalizing learned dynamics across tasks, datasets, and populations.  _Lecture Notes in Computer Science_ , page 407–417, 2020.  ISSN 1611-3349.  10.1007/978-3-030-59728-3_40.  URL http://dx.doi.org/10.1007/978-3-030-59728-3_40.
  * Mahmood et al. (2021) Usman Mahmood, Zening Fu, Vince D. Calhoun, and Sergey Plis.  A deep learning model for data-driven discovery of functional connectivity.  _Algorithms_ , 14(3):75, Feb 2021.  ISSN 1999-4893.  10.3390/a14030075.  URL http://dx.doi.org/10.3390/a14030075.
  * Parisot et al. (2018) Sarah Parisot, Sofia Ira Ktena, Enzo Ferrante, Matthew Lee, Ricardo Guerrero, Ben Glocker, and Daniel Rueckert.  Disease prediction using graph convolutional networks: Application to autism spectrum disorder and alzheimer’s disease.  _Medical Image Analysis_ , 48:117–130, 2018.  ISSN 1361-8415.  https://doi.org/10.1016/j.media.2018.06.001.  URL https://www.sciencedirect.com/science/article/pii/S1361841518303554.
  * Plis et al. (2014) Sergey M Plis, Devon Hjelm, Ruslan Salakhutdinov, Elena A Allen, Henry Jeremy Bockholt, Jeffrey D Long, Hans J Johnson, Jane Paulsen, Jessica A Turner, and Vince D Calhoun.  Deep learning for neuroimaging: a validation study.  _Frontiers in Neuroscience_ , 8(229), 2014.  ISSN 1662-453X.
  * Schuster and Paliwal (1997) M. Schuster and K.K. Paliwal.  Bidirectional recurrent neural networks.  _IEEE Transactions on Signal Processing_ , 45(11):2673–2681, 1997.  10.1109/78.650093.
  * Shang et al. (2021) Chao Shang, Jie Chen, and Jinbo Bi.  Discrete graph structure learning for forecasting multiple time series.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=WEHSlH5mOk.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, undefinedukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , NIPS’17, page 6000–6010, Red Hook, NY, USA, 2017. Curran Associates Inc.  ISBN 9781510860964.
  * Ying et al. (2018) Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec.  Hierarchical graph representation learning with differentiable pooling.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.  URL https://proceedings.neurips.cc/paper/2018/file/e77dbaf6759253c7c6d0efc5690369c7-Paper.pdf.
  * Zhang and Chen (2018) Muhan Zhang and Yixin Chen.  Link prediction based on graph neural networks, 2018.
  * Zhang et al. (2018) Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen.  An end-to-end deep learning architecture for graph classification.  In _AAAI_ , pages 4438–4445, 2018.