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

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.