Diffusion Incentives in Cooperative Games

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.