Hodge decomposition and the Shapley value of a cooperative game

• 成果类型: Article
• 署名作者: Stern, Ari; Tettenhorst, Alexander
• 署名单位: Washington University (WUSTL)
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2018.09.006
• 发表日期: 2019
• 页码: 186-198
• 关键词: Shapley value; Cooperative game theory; Hodge decomposition; Graph Laplacian

摘要

We show that a cooperative game may be decomposed into a sum of component games, one for each player, using the combinatorial Hodge decomposition on a graph. This decomposition is shown to satisfy certain efficiency, null-player, symmetry, and linearity properties. Consequently, we obtain a new characterization of the classical Shapley value as the value of the grand coalition in each player's component game. We also relate this decomposition to a least-squares problem involving inessential games (in a similar spirit to previous work on least-squares and minimum-norm solution concepts) and to the graph Laplacian. Finally, we generalize this approach to games with weights and/or constraints on coalition formation. (C) 2018 Elsevier Inc. All rights reserved.