---
title: "Diffusion Incentives in Cooperative Games"
authors:
  - "Yao Zhang"
doi: "10.24963/ijcai.2022/845"
url: "https://ijcai.org/proceedings/2022/845"
pdf: "https://ijcai.org/proceedings/2022/0845.pdf"
venue: "Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence"
year: 2022
pages: "5885-5886"
track: "Doctoral Consortium"
keywords:
  - "Game Theory and Economic Paradigms (GTEP): General"
---

# Diffusion Incentives in Cooperative Games

Yao Zhang

*Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence*, pages 5885-5886. DOI: [10.24963/ijcai.2022/845](https://doi.org/10.24963/ijcai.2022/845)

## Abstract

We study a cooperative game setting where we want to gather more players through their social connections. Social connections can be modeled as a graph, and initially, only a subset of the players are in the game. We want to introduce diffusion incentives in such a cooperative game, i.e., incentivize the players to use their connections to invite more players to join the game. Our goal cannot be achieved by existing classical solutions, such as the Shapley value. Hence, to combat this problem, we have already proposed a solution called weighted permission Shapley value. Under this solution, for each player, inviting all of her neighbors is a dominant strategy in all monotone games. As one special application of the diffusion cooperative game, we also considered the diffusion incentives in query networks and the weighted permission Shapley value successfully characterizes the solution to the query network. Furthermore, we also characterize a Sybil-proof solution to the query network called the double geometric mechanism.

## Full text

## 1 Introduction

The cooperative game is a classical topic in game theory, which focuses on reward schemes for a fixed coalition of players [Young, 1985; Peleg and Sudh¨olter, 2007]. Here we focus on monotone games, i.e., more players will create more value, and all players will collaborate in the grand coalition [Driessen, 2013]. Since more involved players means more created values, we consider a new problem of gathering additional participants who are not already in the game.

To gather more participants, utilizing social connections and incentivizing players to invite their social neighbours is a new trend in the field of mechanism design [Zhao, 2021]. Previous literature mainly focused on non-cooperative games. For example, Li et al. [2017; 2022] proposed the very first diffusion mechanisms to attract buyers in auctions via social networks. We share a similar motivation in which players are connected and one cannot become aware of and participate in the collaboration without being invited by their participating neighbors. In particular, we aim to create a reward dis- Classical cooperative game solutions will not work in this new environment because there may be competition among inviters and invitees to share the reward. For example, Shapley value, one of the most well-known solutions, which computes the average marginal contributions of a player to join all possible sub-coalitions [Shapley, 1953], fails to give diffusion incentives in a simple counterexample. Consider two players, and assume that, initially, only one of them is in the game, and she can invite the other player to the game. However, the other player can provide the same contribution as the initial player. In this example, the Shapley value of the initial player after inviting the other player is only half of what it would be if the initial player kept herself alone in the game.

To combat this problem, a very first idea called layered Shapley value [Zhang et al., 2020] was introduced. We then have modelled the diffusion cooperative games and proposed a solution called the weighted permission Shapley value [Zhang and Zhao, 2022] 1 (inspired by the permission structure [Gilles et al., 1992] and the weighted Shapley value [Kalai and Samet, 1987]). The new model can also describe the classical model of query networks [Kleinberg and Raghavan, 2005], and the new solution can well explain the winning solution in the DARPA 2009 Red Balloon Challenge [Pickard et al., 2011], which is a classic application of the query network. We also invented and characterized the Double Geometric Mechanism, a Sybil-proof mechanism for the deployment of query networks [Zhang et al., 2021].

The completed research described above, as well as the target of the remaining work, will be briefly introduced in the following sections.

## 2 Contributions

## 2.1 Completed Research

We model the social connections of players as a network presented by a graph. Each edge indicates that one player can invite the other. There is a special player set called the initial set, who are in the game/coalition initially without invitation, and the invitations have to start from the initial players. The social connections, namely the set of neighbours, are private information of the players, and we treat them as the players' type. Then the invitation process can be mathematically considered as players' reporting their types once rather than an iterated process. According to the reported types, we can induce a directed graph that indicates how players invite each other. Since we actually consider a diffusion model, only the set of players who can be reached by at least one player from the initial set in the directed graph can contribute to the game and share the reward. In practice, this means that the others will not be informed about the game at all.

1 to appear at AAMAS 2022

The main goal is to establish a reward distribution mechanism that efficiently distributes the value created by all the involved players. The key property we emphasize here is diffusion incentive compatibility, which requires that inviting all neighbours is a dominant strategy for all players. A first idea for this purpose is to distribute the marginal contribution in each layer, which is layered Shapley value, but this cannot provide positive incentives to players for their invitation. We then utilize a permission structure to represent the priorities between an inviter and an invitee, and assign different weights to them to control the importance of their priorities. Finally, we have a solution called weighted permission Shapley value. We proved that if a player's weight only depends on her shortest distances to initial players and is monotone non-decreasing, then the solution satisfies diffusion incentive compatibility.

As an application of the diffusion cooperative game, the query incentive network, where a requester tries to find an answer to a specific problem by diffusing the request in the network, can also be solved by our solution. We have shown that the famous solution given by the winning team from MIT in the DARPA 2009 Red Balloon challenge 2 can be represented by a special case of our solution. More importantly, we have also found that the weighted permission Shapley value is the only solution to the query incentive network that is anonymous, strongly individually rational, and efficient.

Sybil-proofness is another important property in our setting, which ensures that players cannot cheat for more rewards by creating fake identities. We have already proposed a solution called double geometric mechanism that is diffusion incentive compatible and Sybil-proof for the special case of the query network. This mechanism cannot be represented by the weighted permission Shapley value since it is not efficient.

## 2.2 OngoingWork and Future Directions

Based on the current results, we are going to characterize all efficient and diffusion incentive compatible solutions for diffusion cooperative games. This will give us a more general solution and a full understanding to diffusion cooperative games. Stability, such as core, is another future direction in our new setting, which prevents sub-coalitions from leaving the game. With the constraint of social connections, we may consider the case where only connected players can leave together. Finally, we have only solved Sybil-proofness in query networks. Hence, we also want to achieve Sybil-proofness in all diffusion cooperative games.

2 In the challenge, each team needed to find positions of the red balloons to obtain rewards. The solution proposed by the winning team is to promise half of the reward for the first person who finds it, one-fourth of the reward for the person who invites the finder, and so on. The requester will get the remaining amount.

## References

1. [Driessen, 2013] Theo SH Driessen. Cooperative games, so- lutions and applications, volume 3. Springer Science & Business Media, 2013.
2. [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.
3. [Kalai and Samet, 1987] Ehud Kalai and Dov Samet. On weighted shapley values. International Journal of Game Theory, 16(3):205-222, 1987.
4. [Kleinberg and Raghavan, 2005] Jon Kleinberg and Prab- hakar Raghavan. Query incentive networks. In 46th An- nual IEEE Symposium on Foundations of Computer Sci- ence (FOCS'05), pages 132-141. IEEE, 2005.
5. [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.
6. [Li et al., 2022] Bin Li, Dong Hao, Hui Gao, and Dengji Zhao. Diffusion auction design. Artificial Intelligence, 303:103631, 2022.
7. [Peleg and Sudhölter, 2007] Bezalel Peleg and Peter Sudhölter. Introduction to the theory of cooperative games. Springer Science & Business Media, 2007.
8. [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.
9. [Shapley, 1953] Lloyd S Shapley. A value for n-person games. Contributions to the Theory of Games, 2(28):307- 317, 1953.
10. [Young, 1985] Hobart Peyton Young. Monotonic solutions of cooperative games. International Journal of Game The- ory, 14(2):65-72, 1985.
11. [Zhang and Zhao, 2022] Yao Zhang and Dengji Zhao. Incen- tives to invite others to form larger coalitions. In AAMAS, 2022.
12. [Zhang et al., 2020] Wen Zhang, Yao Zhang, and Dengji Zhao. Collaborative data acquisition. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, pages 1629-1637, 2020.
13. [Zhang et al., 2021] Yao Zhang, Xiuzhen Zhang, and Dengji Zhao. Sybil-proof answer querying mechanism. In Pro- ceedings of the 29th International Conference on Interna- tional Joint Conferences on Artificial Intelligence, pages 422-428, 2021.
14. [Zhao, 2021] Dengji Zhao. Mechanism design powered by social interactions. In Proceedings of the 20th Interna- tional Conference on Autonomous Agents and MultiAgent Systems, pages 63-67, 2021.