pipette
ESEspañol

Computing the Nucleon of Matching Games

Haris Aziz, Gergely Cs\'aji

Preprint

In the authors' words

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: -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 -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.

Main resultLimitation the authors admit

Appeared: Thursday, October 22. arXiv. Preprint, not yet peer-reviewed.