Computing the nucleon allocation efficiently in matching games and variants
Computing the Nucleon of Matching Games
Computer Science and Game Theory
Summary
Certain kinds of games called matching games involve players forming partnerships to share rewards. The authors study a way of fairly dividing rewards called the nucleon, which balances how much value each group of players gets compared to what they could gain alone. They develop a practical algorithm to find nucleon allocations quickly for basic matching games but show that it is very hard (NP-hard) to do so for more complex versions. For a specific intermediate case, they connect the problem to finding special cycles in graphs, providing a new perspective.
What this means in practice
- •For game theory software developers: Implement algorithms for fair reward division in matching games using the new polynomial-time method for nucleon computation.
- •For combinatorial optimization engineers: Use nucleon computation complexity results to guide resource allocation design involving partnerships with capacity constraints.
Authors
Haris Aziz, Gergely Csáji
Abstract
The nucleon is the multiplicative counterpart of the nucleolus: it lexicographically maximizes the fraction of its stand-alone value that each coalition receives. We study exact nucleon computation in matching games and in two extensions: $b$-matching games, in which players may have several partners, and partitioned matching games, in which one player may own several vertices. We resolve three open problems from a recent survey. For ordinary matching games with nonnegative rational weights, we give a polynomial-time combinatorial algorithm using maximum-weight matching, shortest paths, and minimum-cost flow, ; it returns both a nucleon allocation and a compact description of the full nucleon. In contrast, computing any nucleon allocation is NP-hard for unit-weight $b$-matching games with capacities at most three and for unit-weight partitioned matching games of width at most three. Finally, for the unresolved capacity-two case, we show that exact nucleon computation is polynomial-time Turing reducible to SHORTEST NON-ZERO CYCLE.