[2E3-OS-13b] AIと制約プログラミング(2/3)

[2E3-OS-13b-04] An Efficient Algorithm for the Shapley Value of Cooperative Games on Poset Antimatroids

〇Daisuke Hatano¹ (1. RIKEN AIP)

Keywords:Cooperative game, Shapley value, Antimatroid

A solution concept (value division) of cooperative games is Shapley value, which is computed by dividing a reward of a game proportional to marginal contributions of players. Recently, the Shapley value is used in a wide variety of applications beyond cooperative games, such as the centrality of graphs and the explanability in machine learning. In some applications, a game needs to deal with a discrete structure like a precedence structure among the players. To represent the above structure, we introduce a discrete structure called antimatroid, which is a kind of set system and have a precedence structure as an application. We propose an efficient algorithm for computing the Shapley value of cooperative games on antimatroids under some reasonable assumptions that the game has a poset antimatroid, a special case of the antimatroid, and an additive characteristic function.<gdiv></gdiv>