Coalitional Manipulations and Immunity of the Shapley Value

In recent years, cooperative game theory and its solution methods have expanded beyond traditional realms like cost-sharing (Shubik, 1962; Littlechild and Owen, 1973; Tijs and Driessen, 1986; Gopalakrishnan et al., 2021) and property rights remuneration (Hart and Moore, 1990; Tauman and Watanabe, 2007). Their application in statistics for identifying important variables (Lipovetsky and Conklin; Shorrocks, 2012), in machine learning for interpreting prediction models (Lundberg and Lee, 2017; Lundberg et al., 2020), and in marketing for attributing online advertisers' impact on customer conversion (Dalessandro et al.; Berman; Singal et al., forthcoming) demonstrate that today, allocation rules for cooperative games are routinely computed and implemented (Grömping, 2015; Google; GitHub). The most prominent allocation rule for these applications is the Shapley value, which rewards (punishes) a player for a higher (lower) marginal contributions. In fact, this strong monotonicity property is characteristic of the Shapley value (Young, 1985), which is commonly cited as a compelling reason for the widespread adoption of the Shapley value (Shorrocks, 2012; Huettner and Sunder, 2012; Lundberg and Lee, 2017). While strong monotonicity ensures that individuals have an incentive to work towards a common goal, less is known about the incentives of groups of players. In this paper, we study coalitional manipulations, i.e., modifications of a game with the intention to increase the total payoff accruing to the members of a coalition even as the coalition does not create any additional surplus. We introduce axioms ensuring that allocation rules are immune to such manipulations.