Replication Robust Payoff Allocation in Submodular Cooperative Games
  Submodular functions have been a powerful mathematical model for a wide range
of real-world applications. Recently, submodular functions are becoming
increasingly important in machine learning (ML) for modelling notions such as
information and redundancy among entities such as data and features. Among
these applications, a key question is payoff allocation, i.e., how to evaluate
the importance of each entity towards the collective objective? To this end,
classic solution concepts from cooperative game theory offer principled
approaches to payoff allocation. However, despite the extensive body of
game-theoretic literature, payoff allocation in submodular games are relatively
under-researched. In particular, an important notion that arises in the
emerging submodular applications is redundancy, which may occur from various
sources such as abundant data or malicious manipulations where a player
replicates its resource and act under multiple identities. Though many
game-theoretic solution concepts can be directly used in submodular games,
naively applying them for payoff allocation in these settings may incur
robustness issues against replication. In this paper, we systematically study
the replication manipulation in submodular games and investigate replication
robustness, a metric that quantitatively measures the robustness of solution
concepts against replication. Using this metric, we present conditions which
theoretically characterise the robustness of semivalues, a wide family of
solution concepts including the Shapley and Banzhaf value. Moreover, we
empirically validate our theoretical results on an emerging submodular ML
application, i.e., the ML data market.
