Induced Representations in Cooperative Games with Homogeneous Groups of Players
This work provides a theoretical framework for efficiently computing Shapley values in cooperative games with homogeneous groups, benefiting game theory and multi-agent systems where symmetry reduces complexity.
The paper addresses the computational infeasibility of the Shapley value for games with many players by exploiting symmetry in homogeneous group games, proving that such games are supported only by irreducible representations with bounded interaction depth, enabling polynomial-time computation. The approach recovers the Shapley value uniquely for m=2 and is applied to the UN Security Council and complementary goods markets.
Oftentimes, the Shapley value becomes infeasible for games with many players. However, establishing symmetry allows for polynomial-time computation. To examine this reduction, we identify the spectrum of homogeneous group games by using an induced representation from a Young subgroup. We then prove that such games are supported solely by irreducible representations, via the Littlewood-Richardson rule, where the depth of interactions is strictly bounded by the size of the minority group. Therefore, the algebraic structure of the game filters out the complexities of the general kernel $W$. We then show that this filtration constrains any symmetric linear value to a specific subspace. This recovers the Shapley value uniquely for $m=2$ under standard axioms. Finally, we explore applications to the UN Security Council and complementary goods markets to illustrate the practical power of this approach.