\setcopyright

ifaamas \acmConference[AAMAS ’22]Proc. of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022)May 9–13, 2022 Auckland, New ZealandP. Faliszewski, V. Mascardi, C. Pelachaud, M.E. Taylor (eds.) \copyrightyear2022 \acmYear2022 \acmDOI \acmPrice \acmISBN \acmSubmissionID143 \affiliation \institutionShanghaiTech University \cityShanghai \countryChina \affiliation \institutionShanghaiTech University \cityShanghai \countryChina

Incentives to Invite Others to Form Larger Coalitions

Yao Zhang [email protected] and Dengji Zhao [email protected]

Abstract.

We study a cooperative game setting where the grand coalition may change since the initial players can invite more players. We focus on monotone games, i.e., adding more players to the grand coalition is not harmful. We model the invitation relationship as a directed acyclic graph. Our goal is to design a reward distribution mechanism for this new cooperative game setting such that players are incentivized to invite new players. In this paper, we propose the weighted permission Shapley value (inspired by permission structure and the weighted Shapley value) to achieve the goal. Our solution offers the very first attempt to incentivize players to invite more players to form a larger coalition via their private invitations in cooperative settings.

Key words and phrases:

Mechanism design, Cooperative games, Diffusion incentives

1. Introduction

Cooperative game is a classical research topic studied in game theory Nisan et al. (2007); Narahari (2014). The study focused on games where a fixed set of players forms coalitions to share rewards. A common assumption behind the game is that more players collaborating create a higher reward and the goal is to incentivize all players to collaborate. 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 groups to collaborate on projects via, for example, crowdsourcing platforms (e.g. Amazon Mechanical Turk) and Q&A platforms (e.g. Stack Overflow). However, the players in these platforms are relatively independent and the tasks assigned to them are also independent. Thus the incentives for the players to actively participate in these platforms are not strong.

In this paper, we want to design a mechanism where existing participants are motivated to invite others to join a project via their private social connections. 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 tasks 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. Among them, the most famous red balloon challenge hosted by DARPA is a well-known example where collaboration formed via social networks played an essential role Pickard et al. (2011).

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

The Shapley value is a classical solution concept in cooperative games to distribute rewards Shapley (1953). However, in the calculation of the Shapley value, all the players are symmetric, which is not the case in our setting because some players are invited by the others and they cannot be treated equally. Therefore, it is easy to show that the Shapley value cannot be directly applied here to incentivize players to invite others.

To combat this problem, we combine the concepts of permission structure and weighted Shapley value for the first time to build our solution. The weighted Shapley value is the very first concept that applies asymmetry to cooperative games Chun (1991). Kalai and Samet Kalai and Samet (1987) offered the idea of the weight system and an axiomatic characterization of the weighted Shapley values. A recent understanding of the weighted Shapley value is illustrated in Radzik (2012), which gave new axioms and provided simpler formula for weighted Shapley value. However, the asymmetry introduced by the weighted Shapley value cannot reflect the structure of the invitations among the players in our setting.

The concept of permission structure 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 the permissions are very similar to the players’ invitations in our model. In our model, a player is not aware of the game without someone’s invitation. 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 is given in van den Brink and Gilles (1996) and Van Den Brink (1997).

Against this background, our solution is a novel combination of the weighted Shapley value and the permission structure. We use permission structure to represent the priorities between an inviter and invitee. We further assign different weights to the players to control the importance of their priorities. The well-known winning solution for the DARPA red balloon challenge is a special case of our solution Pickard et al. (2011). We expect that our solution will 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 cooperative game and, for the first time, define the concept of diffusion incentive compatibility (DIC) for players to utilize their connections to gather more players.
•

We define a weighted permission Shapley value as a reward distribution mechanism to achieve DIC.
•

We also formally model the query network as a diffusion cooperative game and show the only solution to it is the weighted permission Shapley value, which for the first time explains in theory why the winning solution of DARPA red balloon challenge worked and extends their solution to DAGs.

There are some interesting related works investigating information diffusion on social networks in 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 an auction, Li et al. Li et al. (2017) and Zhao et al. Zhao et al. (2018) proposed the very first mechanisms. Our model shares a similar motivation, but cannot be handled with their techniques as they focused on the non-cooperative setting and only a few players can get reward.

The remainder of the paper is organized as follows. Section 2 gives a formal description of the model. Sections 3 establishes the family of weighted permission Shapley value to incentivize diffusion in forests and Section 4 demonstrates its applicability in query networks. Section 5 extends the result to general DAGs.

2. The Model

We study a cooperative game where players are connected to form a network and not all players are aware of the game initially. In real-world applications, their connections can represent friendship or leadership. A person who is in the coalition can invite her friends who are not in the coalition yet to join. Without the invitation, these friends will not be informed of the coalition. We investigate the reward distribution mechanism in this setting to incentivize existing players to invite new players to join the coalition.

Formally, let $N=\{1,2,\dots,n\}$ be the set of all connected players in the underlying network. We model the network as a directed acyclic graph (DAG) $G=(N,E)$ . Each edge $e=(x,y)\in E$ indicates that player $x$ can invite $y$ . There is a special player set $\mathcal{I}\subseteq N$ who are in the coalition initially without invitation. We call $\mathcal{I}$ the initial set and the invitation has to start from the initial players. For each player $i\in N$ , let $p_{i}=\{j\mid(j,i)\in E\}$ . We have $p_{i}=\emptyset$ if and only if $i\in\mathcal{I}$ . We may assume w.l.o.g. that all players can be reached from at least one of the initial players in the underlying network. Let $\theta_{i}=\{j\mid(i,j)\in E\}$ be private type of player $i$ , which is the set of players who can be invited by $i$ . Since the mechanism does not know the real underlying network, the invitation process can be modelled as each player $i$ reporting her own type. Let $\theta_{i}^{\prime}\subseteq\theta_{i}$ is the report type of player $i$ , i.e., the actual player set invited by $i$ . Given any report profile $\theta^{\prime}=(\theta_{1}^{\prime},\dots,\theta_{n}^{\prime})$ , there is a directed graph induced by $\theta^{\prime}$ denoted by $G(\theta^{\prime})=(N,E(\theta^{\prime}))$ , where $E(\theta^{\prime})=\{(i,j)\mid i\in N,j\in\theta_{i}^{\prime}\}$ . Let $J_{\mathcal{I}}(G(\theta^{\prime}))$ be the set of players who can be reached from at least one player in $\mathcal{I}$ in $G(\theta^{\prime})$ . It is clear that only the players in $J_{\mathcal{I}}(G(\theta^{\prime}))$ can actually join the game, because the others cannot receive the proper invitation started from the initial players (in practice, this means that the others will not be informed about the game at all).

There is a non-negative and monotone characteristic function $v:2^{N}\rightarrow\mathbb{R}$ , s.t., $v(\emptyset)=0$ and $v(S)\leq v(T)$ for all $S\subseteq T\subseteq N$ . The monotone property is necessary in our setting; otherwise, there is no need to invite more people to join the coalition if fewer people can do better. Note that the definition of $v$ does not consider the connections between players, simply because the connections are their private information, which is what we want to discover. Let $\Theta(N)$ and $\mathcal{V}(N)$ be the space of all type profiles and all characteristic functions satisfying our setting respectively. We define the reward distribution mechanism as follows.

Definition \thetheorem.

A reward distribution mechanism $\mathcal{M}$ is defined by a reward policy $\Phi=\{\phi_{i}\}_{i\in N}$ , where each $\phi_{i}:\Theta(N)\times\mathcal{V}(N)\rightarrow\mathbb{R}$ assigns the reward to player $i\in N$ . Moreover, for all $\theta^{\prime}\in\Theta(N)$ and all $v\in\mathcal{V}(N)$ , $\phi_{i}(\theta^{\prime},v)=0$ if $i\notin J_{\mathcal{I}}(G(\theta^{\prime}))$ , where $\mathcal{I}$ is the initial set.

A desirable property of the reward distribution mechanism is to distribute exactly what the coalition of all participated players can generate. This is called efficiency.

Definition \thetheorem.

A reward distribution mechanism $\mathcal{M}$ is efficient if for all $\theta^{\prime}\in\Theta(N)$ and all $v\in\mathcal{V}(N)$ , we have

\sum_{i\in N}\phi_{i}(\theta^{\prime},v)=v\left(J_{\mathcal{I}}(G(\theta^{\prime}))\right)

Other than efficiency, we also want to incentivize all players who are already in the coalition to invite all their neighbours to join the coalition. This is the key property we want to achieve here, which requires that inviting all neighbours is a dominant strategy for all players. We call this property diffusion incentive compatibility. Let $\Theta_{i}$ be the type space of player $i$ , $\theta_{-i}$ be the report profile of players other than $i$ , and $\Theta_{-i}$ be the type space of players other than $i$ . We define diffusion incentive compatibility as follows.

Definition \thetheorem.

A reward distribution mechanism $\mathcal{M}$ is diffusion incentive compatible (DIC) if for all $i\in N$ with type $\theta_{i}\in\Theta_{i}$ , all $\theta_{i}^{\prime}\subseteq\theta_{i}$ , all $\theta_{-i}^{\prime}\in\Theta_{-i}$ and all $v\in\mathcal{V}(N)$ , we have

\phi_{i}((\theta_{i},\theta_{-i}^{\prime}),v)\geq\phi_{i}((\theta_{i}^{\prime},\theta_{-i}^{\prime}),v)

Finally, we consider a property of structural fairness that guarantees a player can gain reward at least as much as a fixed proportion of the reward gained by her invitees. Since the game is monotone, it is reasonable to give a promise of fairness compared to neighbours to all players before their invitations.

Definition \thetheorem.

A reward distribution mechanism $\mathcal{M}$ has the property of $\gamma$ -structural fairness ( $\gamma$ -SF) if for all $v\in\mathcal{V}(N)$ , all $\theta^{\prime}\in\Theta(N)$ and all $i,j\in J_{\mathcal{I}}(G(\theta^{\prime}))$ with $j\in\theta_{i}^{\prime}$ , we have $\phi_{i}(\theta^{\prime},v)\geq\gamma\phi_{j}(\theta^{\prime},v)$ .

3. Diffusion Incentives in a Forest

In this section, we first investigate the solution to satisfy efficiency and diffusion incentive compatibility when the network $G$ is a forest. An instance of the cooperative game in forests is illustrated in Example 3 below.

Example \thetheorem

Consider the case illustrated in Figure 1, where $N=\{1,2,3,4\}$ . Suppose the initial coalition is $\mathcal{I}=\{1,2\}$ . To form a larger coalition, agents 1 and 2 can invite their friends 3 and 4. Suppose the characteristic function $v$ is defined as

v(S)=\mathbb{I}(\{1,3\}\cap S\neq\emptyset)+\mathbb{I}(4\in S)

for all $S\subseteq N$ , where $\mathbb{I}(\cdot)$ is the indicator function.

Figure 1. An example of the cooperative game in a forest.

3.1. Shapley Value does not Work

The first question is what if we directly apply Shapley value Shapley (1953); Winter (2002), the classical solution for cooperative games, to our setting. Let $\mathcal{R}(S)$ denote the set of all orders $R$ of players in the coalition $S$ . For an order $R$ in $\mathcal{R}(N)$ , we denote by $B^{R,i}$ the set of players preceding $i$ in the order $R$ . For a given characteristic function $v$ and an 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:

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

where $\mathcal{U}_{\mathcal{R}(N)}$ is a uniform distribution on $\mathcal{R}(N)$ . We first show that Shapley value (on $J_{\mathcal{I}}(G(\theta^{\prime}))$ ) does not work in our new setting.

Proposition \thetheorem

If Shapley value is applied as a reward distribution mechanism $\mathcal{M}$ , then $\mathcal{M}$ is not diffusion incentive compatible.

Proof.

We prove this proposition by presenting a counterexample. Consider the game in Example 3. When applying Shapley value as the reward distribution mechanism, we get

\begin{cases}&\varphi_{1}=\varphi_{3}=1/2,\\ &\varphi_{2}=0,\quad\varphi_{4}=1.\end{cases}

Notice that agents 1 and 3 have same contribution to other agents and they will share the reward of that contribution. However, if agent 1 does not invite agent 3, her Shapley value will be increased to $1>1/2$ . Hence, directly applying Shapley value is not diffusion incentive compatible. ∎

3.2. Permission Structure in Forests

To tackle the failure of Shapley value, we recall an important concept called permission structure. Gilles et al. Gilles et al. (1992, 1999) gave the permission restriction on cooperative games. They defined the permission structure on DAGs via the conjunctive and the disjunctive approach, respectively. We will extend the notions on DAGs in Section 5.1. Here we only utilize existing work on forests. Intuitively, a permission structure can represent how players get involved in the game by others’ invitations. The formal definition is shown as below.

Definition \thetheorem.

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

Here, we define $P(i)$ as the set of players who invited $i$ into the coalition, i.e., $P(i)=p_{i}^{\prime}=\{j\mid i\in\theta^{\prime}_{j}\}$ . In particular, in the forest model, every player except the initial players has a unique parent who invites her ( $|p_{i}^{\prime}|=1$ ). For instance, in Example 3, $P(3)=\{1\}$ and $P(4)=\{2\}$ . Then, we can define the autonomous coalition.

Definition \thetheorem.

A coalition $S\subseteq N$ is autonomous in a permission structure $P$ if for all $i\in S$ , $P(i)\subseteq S$ .

A coalition $S\subseteq N$ is autonomous if and only if for each player $i\in S$ , all her ancestors are also in $S$ . The property of autonomous indicates whether a coalition has a chance to generate rewards by itself. For instance, in Example 3, $\{1,3\}$ is autonomous while $\{4\}$ is not autonomous. Denote the collection of all autonomous coalitions in permission structure $P$ by $A_{P}$ . Then for an arbitrary coalition $S\subseteq N$ , we consider the largest autonomous part of it.

Definition \thetheorem.

Let $P$ be a permission structure on $N$ . Then the largest autonomous part of a coalition $S\subseteq N$ is defined by

\alpha(S)=\bigcup\{T\mid T\subseteq S\text{ and }T\in A_{P}\}.

Intuitively, $\alpha(S)$ is the largest subset of $S$ that is autonomous. In particular, in the forest model, let $G_{S}$ be the subgraph of the forest $G$ formed by players in $S$ , then the largest autonomous part of the coalition $S$ is all the connected components of $G_{S}$ that contains at least one player in the initial set $\mathcal{I}$ . For instance, in Example 3, the largest autonomous part of set $\{1,3,4\}$ is $\{1,3\}$ .

3.3. Applying Permission Shapley Value

Taking the structure of the diffusion forest into account, we see that some players need others’ participation to create value. For instance, in Example 3, player 4 can only be invited by player 2. Hence, without player 2, player 4 cannot provide her contribution to the coalition. This suggests applying Shapley value with a permission structure.

Taking the notations in Section 3.2, with the restriction of the permission structure, we can map the characteristic function $v$ of the diffusion cooperative game to a projection $v^{P}$ on $P$ as

v^{P}(S)=v(\alpha(S))

for all $S\subseteq N$ Gilles et al. (1992). Intuitively, it means that the contribution given by a coalition $S$ is only from those players who can participate in the game in the coalition $S$ .

Define the permission Shapley value on characteristic function $v$ as $\varphi^{P}(v)=\varphi(v^{P})$ , i.e., the Shapley value on the game $v^{P}$ . Applying the permission Shapley value in Example 3, we have

v^{P}(S)=\mathbb{I}(1\in S)+\mathbb{I}(\{2,4\}\subseteq S)

and the reward distributed to players will be

\begin{cases}&\varphi^{P}_{1}=1,\quad\varphi^{P}_{3}=0,\\ &\varphi^{P}_{2}=\varphi^{P}_{4}=1/2.\end{cases}

From the example we can see two intuitions of the permission Shapley value. Firstly, if a player has the same contribution as her inviter (e.g., player 3 and her inviter player 1 in Example 3), then only the inviter will be rewarded for that contribution. This can be naturally obtained from the property of diffusion incentive compatibility. No matter how much reward the player shared with her inviter, the inviter will then have no incentives to invite the player. On the other hand, if a player invites another player who can create additional contribution (e.g., player 2 and player 4 in Example 3), then the reward for the contribution will be equally shared with them.

To see the intuition, we consider a special case where an additive assumption is applied, i.e., for each two disjoint subsets of players $S_{1}$ , $S_{2}\subseteq N$ such that $S_{1}\cap S_{2}=\emptyset$ , we have $v(S_{1}\cup S_{2})=v(S_{1})+v(S_{2})\geq 0$ . Under this assumption, denote the depth of $i$ in the tree $i$ belongs to by $d_{i}$ (the depths of the roots are 0) and the subtree rooted by $i$ by $T_{i}$ . Then the permission Shapley value of all player $i\in N$ is

\varphi^{P}_{i}=\sum_{k\in T_{i}}\frac{v(\{k\})}{d_{k}+1}\qquad\text{for every }i\in N.

Intuitively speaking, the contribution of a player will be uniformly distributed as the reward along the invitation chain.

Now, we show that permission Shapley value is a desirable reward distribution mechanism that satisfies efficiency and diffusion incentive compatibility for diffusion cooperative games in forests.

{theorem}

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

Proof.

(i) $\mathcal{M}$ is efficient since for all $\theta^{\prime}\in\Theta(N)$

\sum_{i\in N}\varphi_{i}^{P}(v)=\sum_{i\in N}\varphi_{i}(v^{P})=v^{P}(J_{\mathcal{I}}(G(\theta^{\prime})))=v(J_{\mathcal{I}}(G(\theta^{\prime}))).

(ii) For the diffusion incentive compatibility, we will show that for each player $i$ , her permission Shapley value is non-decreasing after she invites more players in the game. Consider a player set $X$ which cannot be informed of the game if $i$ does not invite some players. Let $P$ be the permission structure if $i$ does not invite these players and $P^{\prime}$ be the permission structure if $i$ invites these players. Then

•

Before $i$ invites some players to let $X$ get involved in the game, the permission Shapley value of $i$ is

$\varphi^{P}_{i}(v)=\varphi_{i}(v^{P})=\frac{1}{|N\setminus X|!}\sum_{R\in\mathcal{R}(N\setminus X)}C_{i}(v^{P},R).$

•

If $i$ invites players such that $X$ then can be involved in the game, notice that for all $R\in\mathcal{R}(N\setminus X)$ and all $Y\subseteq X$ , we have $v^{P}(B^{R,i})=v^{P^{\prime}}(B^{R,i}\cup Y)$ since $i$ is not in the coalition. Denote $C_{Y}(v^{P^{\prime}},R,i)=v^{P^{\prime}}(B^{R,i}\cup Y\cup\{i\})-v^{P^{\prime}}(B^{R,i}\cup\{i\})$ . Then the permission Shapley value of $i$ will become

	$\displaystyle\varphi^{P^{\prime}}_{i}($	$\displaystyle v)=\frac{1}{\|N\|!}\sum_{R\in\mathcal{R}(N)}C_{i}(v^{P^{\prime}},R)$
		$\displaystyle=\frac{\|X\|!}{\|N\|!}\sum_{R\in\mathcal{R}(N\setminus X)}\left[\binom{\|N\|}{\|X\|}C_{i}(v^{P},R)+\sum_{Y\subseteq X}C_{Y}(v^{P^{\prime}},R,i)\right]$
		$\displaystyle\geq\frac{\|X\|!}{\|N\|!}\sum_{R\in\mathcal{R}(N\setminus X)}\binom{\|N\|}{\|X\|}C_{i}(v^{P},R)$
		$\displaystyle=\frac{1}{(\|N\|-\|X\|)!}\sum_{R\in\mathcal{R}(N\setminus X)}C_{i}(v^{P},R)=\varphi_{i}^{P}(v)$

where the equality in the second line means the marginal contribution gained by $i$ when asserting the players in $X$ to all orders in $\mathcal{R}(N\setminus X)$ . Therefore, the permission Shapley value is DIC. ∎

For structural fairness, we show that permission Shapley value satisfies 1-SF. Intuitively, it means that if a player $i$ invites $j$ to the game, then she will gain at least as much as the reward that is distributed to $j$ .

{theorem}

For the monotone diffusion cooperative game in a forest, if the reward distribution mechanism $\mathcal{M}$ is the permission Shapley value, then $\mathcal{M}$ is 1-SF.

Proof.

For all $\theta^{\prime}\in\Theta$ , consider $i,j\in J_{\mathcal{I}}(G(\theta^{\prime}))$ with $j\in\theta_{i}^{\prime}$ . For all $S\subseteq N$ with $i\in S$ , let $Q^{i}_{S}=(|N|-|S|)!(|S|-1)!/|N|!$ , i.e., the probability of $B^{R,i}=S\setminus\{i\}$ in all orders $R\in\mathcal{R}(N)$ . Since $R$ is sampled with uniform distribution, then for all $S\subseteq N$ with $i,j\in N$ , $Q^{i}_{S}=Q^{j}_{S}$ . Hence, we have

$\displaystyle\varphi_{i}^{P}$	$\displaystyle=\sum_{S\ni i}Q^{i}_{S}\left[v^{P}(S)-v^{P}(S\setminus\{i\})\right]$
	$\displaystyle=\sum_{S\ni i,S\notni j}Q^{i}_{S}\left[v^{P}(S)-v^{P}(S\setminus\{i\})\right]$
	$\displaystyle\quad+\sum_{S\ni i,S\ni j}Q^{j}_{S}\left[v^{P}(S)-v^{P}(S\setminus\{i\})\right]+\sum_{S\notni i,S\ni j}Q^{j}_{S}\cdot 0$
	$\displaystyle\geq\sum_{S\ni i,S\ni j}Q^{j}_{S}\left[v^{P}(S)-v^{P}(S\setminus\{i\})\right]+\sum_{S\notni i,S\ni j}Q^{j}_{S}\cdot 0$	(1)
	$\displaystyle=\sum_{S\ni i,S\ni j}Q^{j}_{S}\left[v^{P}(S)-v^{P}(S\setminus\{i\})\right]$
	$\displaystyle\quad+\sum_{S\notni i,S\ni j}Q^{j}_{S}\cdot\left[v^{P}(S)-v^{P}(S\setminus\{j\})\right]$	(2)
	$\displaystyle\geq\sum_{S\ni i,S\ni j}Q^{j}_{S}\left[v^{P}(S)-v^{P}(S\setminus\{j\})\right]$
	$\displaystyle\quad+\sum_{S\notni i,S\ni j}Q^{j}_{S}\cdot\left[v^{P}(S)-v^{P}(S\setminus\{j\})\right]$	(3)
	$\displaystyle=\sum_{S\ni j}Q^{j}_{S}\left[v^{P}(S)-v^{P}(S\setminus\{j\})\right]=\varphi_{j}^{P}$

where the Inequality (1) is satisfied since the game is monotone; the Equality (2) is satisfied since for all $S\subseteq N$ with $i\notin S$ and $j\in S$ , $j\notin\alpha(S)$ and then $v^{P}(S)-v^{P}(S\setminus\{j\})=v(\alpha(S))-v(\alpha(S))=0$ ; the Inequality (3) is satisfied since for all $S\subseteq N$ with $i,j\in S$ , $\alpha(S\setminus\{i\})=\alpha(S\setminus\{i,j\})$ and then $v^{P}(S)-v^{P}(S\setminus\{i\})=v^{P}(S)-v^{P}(S\setminus\{i,j\})\geq v^{P}(S)-v^{P}(S\setminus\{j\})$ .

Therefore, the permission Shapley value is 1-SF. ∎

3.4. Using Weights to Further Utilize the Structure

Now we look back at the game illustrated in Example 3. The permission Shapley value suggests an equal share between players 2 and 4. However, in this example, player 2 has diffusion incentives if sharing any amount from player 4’s contribution. Simply applying permission Shapley value cannot tell the differences between these two players. Alternatively speaking, we need a method that can tune the parameter $\gamma$ in structural fairness. Therefore, this suggests that weights can be introduced to distinguish the differences among these players. Kalai and Samet Kalai and Samet (1987) introduced weights to the Shapley value as an alternative solution to cooperative games. Radzaik Radzik (2012) further discussed the variants and properties of the weighted Shapley value and Dragan Dragan (2008) provided a computation method for weighted Shapley value. Usually, the weighted Shapley value can be defined as:

\varphi^{\omega}_{i}(v)=\mathbb{E}_{\mathcal{D}(\omega)}(C_{i}(v,\cdot))

where $\omega=(\omega(1),\omega(2),\dots,\omega(n))\in\mathbb{R}^{N}_{+}$ are the weights assigned to players and $\mathcal{D}(\omega)$ is a distribution on $\mathcal{R}(N)$ based on $\omega$ .

To compute $\mathcal{D}(\omega)$ , consider an order $R\in\mathcal{R}(N)=(i_{1},i_{2},\dots,i_{n})$ , define $\omega_{R}=\prod_{k=1}^{m}$ $\left(\omega(i_{k})/\sum_{p=1}^{k}\omega(i_{p})\right)$ . This can be interpreted as the probability of sampling the order $R$ by agents’ weights, e.g., sampling last player as $i_{n}$ has probability $\omega(i_{n})/(\omega(i_{1})+\cdots+\omega(i_{n}))$ and sampling previous player as $i_{n-1}$ in the remaining players has probability $\omega(i_{n-1})/(\omega(i_{1})+\cdots+\omega(i_{n-1}))$ . Finally, in $\mathcal{D}(\omega)$ , the probability of selecting order $R$ is $\omega_{R}$ Kalai and Samet (1987). Table 1 shows an example of the weight assignments.

order $R$	$\omega_{R}$ ( $\omega(i)=1$ for all $i$ )	$\omega_{R}$ ( $\omega(1\text{ or }2)=1,\omega(3)=2$ )
(1, 2, 3)	1/6	1/4
(1, 3, 2)	1/6	1/6
(2, 1, 3)	1/6	1/4
(2, 3, 1)	1/6	1/6
(3, 1, 2)	1/6	1/12
(3, 2, 1)	1/6	1/12

Table 1. An example of computing the

\mathcal{D}(\omega)

from weights

\omega

. We can see when

\omega(3)

is larger, player 3 has more chance to appear the the later positions.

Note that when $\omega=1^{|N|}$ , the weighted Shapley value becomes the classical Shapley value. In our setting, we can also assign weights to players. 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. Moreover, from the perspective of fairness, the weights will decide how much a player $i$ can be rewarded by inviting her neighbours, i.e., the parameter $\gamma$ in structural fairness. Therefore, we introduce a new idea as weighted permission Shapley value.

Definition \thetheorem.

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

\varphi_{i}^{\omega,P}(v)=\varphi_{i}^{\omega}(v^{P}).

To apply weighted permission Shapley value to a diffusion cooperative game, we still set $P(i)=p^{\prime}_{i}$ and then we need a weight function $\omega(i)$ to set weights to each player $i$ . As an example, let the weight function be $\omega(i)=d_{i}+1$ , where $d_{i}$ is the depth of player $i$ in the tree $i$ belongs to¹¹1For players who are not in the set $J_{\mathcal{I}}(G(\theta^{\prime}))$ , they can be assigned arbitrary positive weight. We will not specify the conditions for these players later unless necessary.. Then applying the weighted permission Shapley value in Example 3, the rewards distributed to players are:

\begin{cases}&\varphi^{\omega,P}_{1}=1,\quad\varphi^{\omega,P}_{3}=0,\\ &\varphi^{\omega,P}_{2}=1/3,\quad\varphi^{\omega,P}_{4}=2/3.\end{cases}

From the example we can see that we make a difference between players 2 and 3’s rewards. Again, consider the special case for the additive characteristic function $v$ . Let $T_{i}$ be the subtree rooted by $i$ . Then the weighted permission Shapley value with weight $\omega:\omega(i)=f(d_{i})$ for all player $i\in N$ is

\varphi^{\omega,P}_{i}=\sum_{k\in T_{i}}\frac{f(d_{i})}{\sum_{j=0}^{d_{k}}f(j)}v(\{k\}).

Intuitively speaking, the reward will be distributed along the invitation chain according to the ratio of the weights rather than uniformly divided.

If we set weights as $1^{|\mathcal{N}|}$ , the weighted permission Shapley value will become normal permission Shapley value. Hence, the weighted permission Shapley value is a more general class of mechanisms and we will show that if we set weights properly, it is also a desirable solution to diffusion cooperative game that satisfies efficiency and diffusion incentive compatibility.

{theorem}

For the monotone diffusion cooperative game in a forest, if the reward distribution mechanism $\mathcal{M}$ is the weighted permission Shapley value with weight function $\omega(i)=f(d_{i})$ for all player $i$ , which only depends on her distance to initial players, then $\mathcal{M}$ is efficient and DIC.

Proof.

(i) $\mathcal{M}$ is efficient since for all $\theta^{\prime}\in\Theta(N)$ ,

\sum_{i}\varphi_{i}^{\omega,P}(v)=\sum_{i}\varphi_{i}^{\omega}(v^{P})=v^{P}(J_{\mathcal{I}}(G(\theta^{\prime})))=v(J_{\mathcal{I}}(G(\theta^{\prime}))).

(ii) For the property of DIC, suppose $X$ is the player set which cannot be informed of the game if $i$ does not invite some players. Let $P$ be the permission structure if $i$ does not invite these players and $P^{\prime}$ be the permission structure if $i$ invites these players. Then, the weighted permission Shapley value before $i$ let $X$ get involved in the game is

\varphi_{i}^{\omega}(v^{P})=\sum_{R\in\mathcal{R}(N\setminus X)}\omega_{R}C_{i}(v^{P},R)\left/\sum_{R\in\mathcal{R}(N\setminus X)}\omega_{R}\right..

Consider an order $R_{j}^{p}=(i_{1},\dots,i_{p-1},j,i_{p},\dots,i_{m})$ , which inserts player $j$ at the position $p$ in $R$ . Then from the definition we can derive that $\omega_{R}=\sum_{p=1}^{m+1}\omega_{R_{j}^{p}}$ if for all $k$ , $\omega(i_{k})$ will not change after $j$ joins in. More generally, for any additional player set $X$ , if for all $k$ , $\omega(i_{k})$ will not change after $X$ joins in, we have $\sum_{R^{\prime}\in R_{X}}\omega_{R^{\prime}}=\omega_{R}$ , where $R_{X}$ is the set of all possible orders that insert all players in $X$ into the order $R$ . Then if $i$ invites players such that $X$ can be involved in the game, since the weight function $\omega(i)=f(d_{i})$ only depends on $d_{i}$ , for all player $i\in N\setminus X$ , $\omega(i)$ will not change. Hence, the weighted permission Shapley value of $i$ becomes

	$\displaystyle\varphi^{\omega}_{i}$	$\displaystyle(v^{P^{\prime}})=\frac{1}{\sum_{R\in\mathcal{R}(N)}\omega_{R}}\sum_{R\in\mathcal{R}(N)}\omega_{R}C_{i}(v^{P^{\prime}},R)$
		$\displaystyle=\frac{1}{\sum_{R\in\mathcal{R}(N\setminus X)}\omega_{R}}\sum_{R\in\mathcal{R}(N\setminus X)}\sum_{R^{\prime}\in R_{X}}\omega_{R^{\prime}}C_{i}(v^{P},R^{\prime})$
		$\displaystyle\geq\frac{1}{\sum_{R\in\mathcal{R}(N\setminus X)}\omega_{R}}\sum_{R\in\mathcal{R}(N\setminus X)}\sum_{R^{\prime}\in R_{X}}\omega_{R^{\prime}}C_{i}(v^{P},R)$
		$\displaystyle=\frac{1}{\sum_{R\in\mathcal{R}(N\setminus X)}\omega_{R}}\sum_{R\in\mathcal{R}(N\setminus X)}\omega_{R}C_{i}(v^{P},R)=\varphi_{i}^{\omega}(v^{P}).$

Therefore, $\mathcal{M}$ is DIC.

∎

Moreover, by introducing weights, we can make the structural fairness more tunable to customize the requirements in different scenes.

{theorem}

For the monotone diffusion cooperative game in a forest, if the reward distribution mechanism $\mathcal{M}$ is the weighted permission Shapley value with weight function $\omega(i)$ that satisfies for all $\theta^{\prime}\in\Theta$ and for all $i,j\in J_{\mathcal{I}}(G(\theta^{\prime}))$ with $j\in\theta^{\prime}_{i}$ , $\omega(i)/\omega(j)\geq\gamma$ , then $\mathcal{M}$ is $\gamma$ -SF.

Proof.

For all $\theta^{\prime}\in\Theta$ , consider $i,j\in J_{\mathcal{I}}(G(\theta^{\prime}))$ with $j\in\theta_{i}^{\prime}$ . For all $S\subseteq N$ with $i\in S$ , let $Q^{i}_{S}$ be the probability of $B^{R,i}=S\setminus\{i\}$ in all orders $R\in\mathcal{R}(N)$ . Since $R$ is sampled with distribution $\mathcal{D}(\omega)$ , then for all $S\subseteq N$ with $i,j\in N$ , we have

\frac{Q^{i}_{S}}{Q^{j}_{S}}=\frac{\omega(i)}{\omega(j)}.

Hence, $Q^{i}_{S}=\frac{\omega(i)}{\omega(j)}Q^{j}_{S}$ and we have

$\displaystyle\varphi_{i}^{\omega,P}$	$\displaystyle=\sum_{S\ni i}Q^{i}_{S}\left[v^{P}(S)-v^{P}(S\setminus\{i\})\right]$
	$\displaystyle=\sum_{S\ni i,S\notni j}Q^{i}_{S}\left[v^{P}(S)-v^{P}(S\setminus\{i\})\right]$
	$\displaystyle\quad+\frac{\omega(i)}{\omega(j)}\left\{\sum_{S\ni i,S\ni j}Q^{j}_{S}\left[v^{P}(S)-v^{P}(S\setminus\{i\})\right]+\sum_{S\notni i,S\ni j}Q^{j}_{S}\cdot 0\right\}$
	$\displaystyle\geq\frac{\omega(i)}{\omega(j)}\left\{\sum_{S\ni i,S\ni j}Q^{j}_{S}\left[v^{P}(S)-v^{P}(S\setminus\{i\})\right]+\sum_{S\notni i,S\ni j}Q^{j}_{S}\cdot 0\right\}$
	$\displaystyle\geq\frac{\omega(i)}{\omega(j)}\left\{\sum_{S\ni i,S\ni j}Q^{j}_{S}\left[v^{P}(S)-v^{P}(S\setminus\{j\})\right]\right.$
	$\displaystyle\quad+\left.\sum_{S\notni i,S\ni j}Q^{j}_{S}\cdot\left[v^{P}(S)-v^{P}(S\setminus\{j\})\right]\right\}$	(4)
	$\displaystyle=\frac{\omega(i)}{\omega(j)}\left\{\sum_{S\ni j}Q^{j}_{S}\left[v^{P}(S)-v^{P}(S\setminus\{j\})\right]\right\}$
	$\displaystyle=\frac{\omega(i)}{\omega(j)}\varphi_{j}^{\omega,P}\geq\gamma\varphi_{j}^{\omega,P}$

where the Inequality (4) is satisfied according to the same reason for Equality (2) and Inequality (3) in Theorem 3.3.

Therefore, the $\mathcal{M}$ is $\gamma$ -SF. ∎

Intuitively, the parameter of the structural fairness is determined by $\min_{j\in\theta^{\prime}_{i}}\omega(i)/\omega(j)$ . For example, if $\omega(i)=d_{i}+1$ , then the corresponding weighted permission Shapley value is $1/2$ -SF.

4. The Only Solution to Query Network

A classic problem that can be modelled as a diffusion cooperative game is the query incentive network Kleinberg and Raghavan (2005), where a requester tries to find an answer to a specific problem by diffusing the request in the network. A solution 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 positions of the red balloons to obtain rewards. The solution proposed by the winning team is that they promised half of the reward for the first person who found it and one-fourth of the reward to the person who invited the finder and so on. The requester (initial players) will get the remaining. An example is shown in Figure 2.

Figure 2. An example of the solution given by winning team in DARPA challenge. Players 1 and 2 are the initial team members. Players 6 and 8 are those who find the balloon.

We can model it as a diffusion cooperative game with an additive characteristic function where only one agent (the answer holder) can contribute the utility. Without loss of generality, we assume there is only one initial player as the requester and only one player can provide the answer and the answer will bring one unit value (for the game in the example shown in Figure 2, we can seperate it as two games and add the two solutions up). More precisely, in the corresponding diffusion cooperative game to the query network, we set $\mathcal{I}=\{1\}$ and for any $S\subseteq N$ , $v(S)=1$ if and only if the answer holder $j\in S$ . In general, a solution to the query network is a reward distribution $x(i)$ for all players $i$ along the path from the requester to answer provider. We require that the reward distribution $x(i)$ satisfies the following properties.

Definition \thetheorem.

A reward distribution $x(i)$ for all players $i$ along the path from the requester 1 to answer provider $j$ in the query network is

•

anonymous if $x(i)$ only depends on $d_{i}$ and $d_{j}$ (the distances from player 1 to $i$ and $j$ , which indicates $i$ ’s position);
•

strongly individually rational (SIR) if $x(i)>0$ for all $i$ from 1 to $j$ ;
•

efficient if $\sum_{i}x(i)=1$ .

For example, the solution given by the DARPA winning team can be described as $x(i)=1/2^{d_{j}+1-d_{i}}$ with $i>1$ and $x(1)=1/2^{d_{j}}$ for all $i$ on the path from 1 to $j$ . We show that all the solution concepts can be mapped to a set of weighted permission Shapley values. In other words, the set of weighted permission Shapley value is the only satifiable solution to the query network.

{theorem}

A solution to a query network is anonymous, strongly individually rational and efficient if and only if it is a weighted permission Shapley value with $\omega(i)=f(d_{i},d_{j})$ , where $j$ is the answer provider.

Proof.

“ $\Rightarrow$ ”: suppose $x(i)$ is an anonymous, SIR and efficient solution to the query network. Construct a weighted permission Shapley value with $\omega(i)=x(i)$ for all $i$ on the path from agent 1 to $j$ and $\omega(i)=1$ for other players. Then,

\varphi^{\omega,P}_{i}=\sum_{k\in T_{i}}\frac{\omega(i)}{\sum_{l=0}^{d_{k}}\omega(l)}v(\{k\})=\frac{x(i)}{\sum_{l}x(l)}=x(i)

for all $i$ on the path from agent 1 to $j$ and otherwise $\varphi^{\omega,P}_{i}=0$ .

“ $\Leftarrow$ ”: consider a weighted permission Shapley value with $\omega(i)=f(d_{i},d_{j})$ . $\varphi^{\omega,P}_{i}=0$ if $i$ is not an ancestor of $j$ . For all $i$ on the path from 1 to $j$ , we have

\varphi^{\omega,P}_{i}=\frac{f(d_{i},d_{j})}{\sum_{k\in\text{ path from agent 1 to }j}f(d_{k},d_{j})}=\frac{f(d_{i},d_{j})}{\sum_{k=0}^{d_{j}}f(k,d_{j})}>0

which only depends on $d_{i}$ and $d_{j}$ . Finally, the efficiency holds since $v(N)=1$ . ∎

Again, take the solution of DARPA winning team as an example. Consider the weighted permission Shapley value with $\omega(i)=\max\{1,2^{d_{i}-1}\}$ , and we have

\varphi_{i}^{\omega,P}=\frac{2^{d_{i}-1}}{1+\sum_{k=1}^{d_{j}}2^{k-1}}=\frac{2^{d_{i}-1}}{2^{d_{j}}}=1/2^{d_{j}+1-d_{i}}

for all $i$ on the path from agent 1 to $j$ with $i>1$ , $\varphi_{1}^{\omega,P}=1/2^{d_{j}}$ and $\varphi_{i}^{\omega,P}=0$ otherwise, which is equivalent to the solution of DARPA winning team. Moreover, in this example, $\omega(i)$ only depends on $d_{i}$ , so that we know the solution of DARPA winning team is diffusion incentive compatible according to Theorem 3.4.

5. From Forest to DAG

In this section, we extend our result in the setting of forest to a general DAG model. An instance of a cooperative game in a DAG is shown in Example 5 below.

Example \thetheorem

Consider the case illustrated in Figure 3, where $\mathcal{I}=\{1,2\}$ . Agent $1$ asks her friends $3$ and $5$ , and $2$ asks $4$ and $5$ . Then $3$ , $4$ and $5$ further ask their friends and so on. Suppose the player $5$ will join in if $2$ invites her or $1$ and $3$ both invite her and the player $7$ will join in if $4$ invites her or $5$ and $6$ both invite her. Suppose the characteristic function $v$ is defined as for every $S\subseteq N$ ,

v(S)=\begin{cases}2&\text{if }7\in S;\\ 1&\text{if }\{1,2\}\cap S\neq\emptyset,7\notin S;\\ 0&\text{otherwise.}\end{cases}

Figure 3. An example of a cooperative game in DAG. The green nodes are initial players.

5.1. Permission Structure with Mixed Approach

Note that there is no existing approach of permission structure that can handle the case in Example 5. Gilles et al. Gilles et al. (1992, 1999) considered the cases where each player has to get permissions either from all or at least one of her superiors. Here we consider a more general case where each player can get permission from a partial subset of her superiors. Hence, we propose the permission structure with mixed approach.

A permission structure with mixed approach $\varrho$ on $N$ is a pair $(P,\Psi)$ where $P$ is a mapping $N\rightarrow 2^{N}$ . The mapping $P$ is asymmetric, i.e., for any pair $i$ , $j\in N$ , $j\in P(i)$ implies that $i\notin P(j)$ and $j$ is called a superior of $i$ . Define $P^{-1}(i)=\{j\in N\mid i\in P(j)\}$ as the set of $i$ ’s successors. Notice that $P(i)=\emptyset$ if $i\in\mathcal{I}$ . The set $\Psi=\{\psi_{i}\mid i\in N\}$ consists of players’ satisfiable expressions. For a coalition $S\subseteq N$ , the expression set $L_{S}$ is recursively defined:

(1)

$\xi_{i}\in L_{S}$ for any $i\in S$ ;
(2)

$a\vee b\in L_{S}$ for any $a$ , $b\in L_{S}$ ;
(3)

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

Given an expression $\psi\in L_{S}$ and a coalition $T\subseteq N$ , the evaluation $\psi(T)$ is the boolean result of $\psi$ when $\xi_{i}=1$ if $i\in T$ and $\xi_{i}=0$ otherwise for all $i\in S$ . Then for $i\in N$ , her satisfiable expression $\psi_{i}\in L_{P(i)}$ , indicates how her superiors hold the authority of permission: only when $\psi_{i}(T)$ is true, $i$ can get the permission to create value in $T$ . Specially, if $i\in\mathcal{I}$ , $\psi_{i}$ is always true since $i$ does not need any others’ permission. For instance, in Example 5, $\psi_{5}=\xi_{2}\vee(\xi_{1}\wedge\xi_{3})$ and $\psi_{7}=\xi_{4}\vee(\xi_{5}\wedge\xi_{6})$ . With the generalized permission structure, an autonomous coalition now can be defined as follows.

Definition \thetheorem.

A coalition $S\subseteq N$ is autonomous in the permission structure $\varrho=(P,\Psi)$ if for all $i\in S$ , $\psi_{i}(S)=1$ .

Denote the set of all autonomous coalitions in $\varrho$ by $A_{\varrho}$ . We can observe several properties of $A_{\varrho}$ as follows.

Lemma \thetheorem

Let $\varrho$ be a permission structure on $N$ , then (i) $\emptyset\in A_{\varrho}$ , (ii) $N\in A_{\varrho}$ and (iii) for all $S,T\in A_{\varrho}$ , $S\cup T\in A_{\varrho}$ .

Proof.

(i) Since there is no $i\in\emptyset$ , then $\emptyset\in A_{\varrho}$ . (ii) for all $\psi\in L_{S}$ , $S\subseteq N$ , $\psi(N)=1$ since all variables are true. Thus, $N\in A_{\varrho}$ . (iii) for all $i\in S\cup T$ , if $i\in S$ , $\psi_{i}(S)=1$ implies $\psi_{i}(S\cup T)=1$ since more variables get true; if $i\in T$ , similarly we have $\psi_{i}(S\cup T)=1$ . Thus, $S\cup T\in A_{\varrho}$ . ∎

Then we can give the definition of the largest autonomous part of a coalition.

Definition \thetheorem.

Let $\varrho$ be a permission structure on $N$ . Then the largest autonomous part of a coalition $S\subseteq N$ is defined by

\alpha(S)=\bigcup\{T\mid T\subseteq S\text{ and }T\in A_{\varrho}\}.

Intuitively, $\alpha(S)$ is the largest autonomous sub-coalition of $S$ , which suggests that for any player $i\in S\backslash\alpha(S)$ , she cannot create value in coalition $S$ .

Similar to Section 3.3, we can map a characteristic function $v$ to a projection $v^{\varrho}$ on $\varrho$ , where $v^{\varrho}(S)=v(\alpha(S))$ , for every coalition $S\subseteq N$ .

5.2. Weighted Shapley Value on Permission Structure

Finally, we introduce weighted Shapley value with mixed permission structure as a class of mechanisms for diffusion cooperative game on DAGs.

Definition \thetheorem.

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

\varphi^{\omega,\varrho}_{i}(v)=\varphi^{\omega}_{i}(v^{\varrho}).

As an example, if we apply the weighted permission Shapley value with mixed approach on the diffusion cooperative game in Example 5 and letting $\omega=1^{|N|}$ , then the reward distributed to each player is

\begin{cases}\varphi^{\omega,\varrho}_{1}=11/15,\qquad\varphi^{\omega,\varrho}_{2}=2/3,\\ \varphi^{\omega,\varrho}_{3}=\varphi^{\omega,\varrho}_{5}=\varphi^{\omega,\varrho}_{6}=\varphi^{\omega,\varrho}_{7}=1/15,\\ \varphi^{\omega,\varrho}_{4}=1/3.\\ \end{cases}

Similar to the mechanisms in a forest, we can conclude that weighted Shapley value with mixed approach is a desirable mechanism that satisfies efficiency and diffusion incentive compatibility if the weight function is selected properly.

Definition \thetheorem.

A weight function $\omega_{i}$ is proper if it only depends on $d_{i}$ as $\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 monotone non-decreasing.

{theorem}

For the monotone diffusion cooperative game in a DAG, if the reward distribution mechanism $\mathcal{M}$ is the weighted permission Shapley value with mixed approach with a proper weight function $\omega_{i}=f(d_{i})$ , then $\mathcal{M}$ is efficient and DIC.

Proof.

The efficiency can be easily derived since for all $\theta^{\prime}\in\Theta$ , $v^{\varrho}(J_{\mathcal{I}}(G(\theta^{\prime})))=v(J_{\mathcal{I}}(G(\theta^{\prime})))$ .

For the property of DIC, if we consider each player $i$ and edge $e=(i,j)\in E$ , there are two cases that may happen if $i$ does not invite $j$ given any possible report profile of others $\theta_{-i}^{\prime}\in\Theta_{-i}$ .

(i) if $j$ cannot join the coalition, i.e., $j\notin J_{\mathcal{I}}(G(\theta^{\prime}))$ , then the proof is similar to that of Theorem 3.4 that shows player $i$ will not get more reward without inviting $j$ .

(ii) if $j$ still can join the coalition, i.e., $j\in J_{\mathcal{I}}(G(\theta^{\prime}))$ , Let $v^{\varrho}$ be the projection game when $i$ invites $j$ and $v^{\varrho^{\prime}}$ be the projection game when $i$ does not invite $j$ . Suppose $R$ is an order in $\mathcal{R}(N)$ . Then we have

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

The above (in)equalities hold because (1) if $i$ is at the position before $j$ , the marginal contribution of $i$ is unchanged; (2) if $i$ is at the position after $j$ , she cannot bring $j$ ’s contribution when she does not invite $j$ . Note that $d_{k}$ will not change for any player $k$ with $d_{k}<d_{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, which can be computed from weights $\omega$ . Hence,

\varphi_{i}^{\omega,\varrho}=\sum_{R\in\mathcal{R}(N)}\omega_{R}C_{i}(v^{\varrho},R)\geq\sum_{R\in\mathcal{R}(N)}\omega_{R}C_{i}(v^{\varrho^{\prime}},R)=\varphi_{i}^{\omega,\varrho^{\prime}}

where $\varphi_{i}^{\omega,\varrho}$ is player $i$ ’s reward when she invites $j$ and $\varphi_{i}^{\omega,\varrho^{\prime}}$ is player $i$ ’s reward when she does not invite $j$ . (2) if $d_{j}^{\prime}>d_{j}$ , then $f(d_{j})\leq f(d_{j}^{\prime})$ since $f$ is monotone non-decreasing. Let $R_{ij}\in\mathcal{R}(N)$ be some order where $i$ comes before $j$ and $R_{ji}$ is the corresponding order where $i$ and $j$ ’s positions are exchanged in $R_{ij}$ . We have $\frac{\omega_{R_{ji}}}{\omega_{R_{ij}}}\geq\frac{\omega^{\prime}_{R_{ji}}}{\omega^{\prime}_{R_{ij}}}$ (since $R_{ij}$ is more likely sampled than $R_{ji}$ with a larger $\omega(j)$ ). Hence, we have

	$\displaystyle\varphi_{i}^{\omega,\varrho}$	$\displaystyle=\sum_{R_{ij}\in\mathcal{R}(N)}\left[\omega_{R_{ij}}C_{i}(v^{\varrho},R_{ij})+\omega_{R_{ji}}C_{i}(v^{\varrho},R_{ji})\right]$
		$\displaystyle\geq\sum_{R_{ij}\in\mathcal{R}(N)}\left[\omega^{\prime}_{R_{ij}}C_{i}(v^{\varrho^{\prime}},R_{ij})+\omega^{\prime}_{R_{ji}}C_{i}(v^{\varrho^{\prime}},R_{ji})\right]$
		$\displaystyle=\varphi_{i}^{\omega,\varrho^{\prime}}.$

The inequality in the second line holds since $\omega_{R_{ij}}+\omega_{R_{ji}}=\omega^{\prime}_{R_{ij}}+\omega^{\prime}_{R_{ji}}$ , $C_{i}(v^{\varrho},R_{ij})\geq C_{i}(v^{\varrho^{\prime}},R_{ji})$ and $C_{i}(v^{\varrho},R_{ij})=C_{i}(v^{\varrho^{\prime}},R_{ij})$ (i.e., the larger term will obtain a larger factor). Therefore, in all cases $i$ will not invite fewer agents. As a result, $\mathcal{M}$ is DIC. ∎

Finally, it is worth to point out that the weighted permission Shapley value that represents the solution of DARPA winning team also has a monotone non-decreasing weight function $\omega$ . Hence, it can be seen as a diffusion incentive compatible extension in DAGS of DARPA winning team’s solution.

5.3. Applying on General Graphs

We discuss the possibility to apply our method on general graphs. One may observe that in some real scenarios, the DAG we modelled is not necessarily the underlying social network. The underlying network could be any undirect graph. This paper focuses on the DAG because in practice, a DAG could be the result of players’ invitations associated with timestamp. Another reason to use DAG is that it is intuitive and handy to define permissions, which clearly specifies who permits/invites who.

It is worthwhile to point out that actually, our results can be extended to general undirected graphs. The only difficulty is defining the permission structure but there are many possible ways. One way we can provide here is to define the permission set of an agent $i$ to be all her neighbors via whom $i$ can reach one of the sources with a simple path (this also works even if there are cycles), i.e., $P(i)=\{j\mid(i,j)\in E\text{ and there exists a simple path }i\rightarrow j\rightarrow\dots\rightarrow s\text{ such that }s\in\mathcal{I}\}$ . Then, all results in this section can still hold.

6. 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. We expect that our work will have 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.

References

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

	$\displaystyle\varphi^{P^{\prime}}_{i}($	$\displaystyle v)=\frac{1}{\|N\|!}\sum_{R\in\mathcal{R}(N)}C_{i}(v^{P^{\prime}},R)$
		$\displaystyle=\frac{\|X\|!}{\|N\|!}\sum_{R\in\mathcal{R}(N\setminus X)}\left[\binom{\|N\|}{\|X\|}C_{i}(v^{P},R)+\sum_{Y\subseteq X}C_{Y}(v^{P^{\prime}},R,i)\right]$
		$\displaystyle\geq\frac{\|X\|!}{\|N\|!}\sum_{R\in\mathcal{R}(N\setminus X)}\binom{\|N\|}{\|X\|}C_{i}(v^{P},R)$
		$\displaystyle=\frac{1}{(\|N\|-\|X\|)!}\sum_{R\in\mathcal{R}(N\setminus X)}C_{i}(v^{P},R)=\varphi_{i}^{P}(v)$