PaperlayerView exact revision on arXiv

Source-linked AI summary

Computing the Nucleon of Matching Games

Haris Aziz, Gergely Csáji

arXiv:2610.29731v1cs.GT

TL;DR

The paper asks how to compute the nucleon exactly in matching games and in b-matching and partitioned matching extensions. It develops a combinatorial algorithm and hardness results, and shows that the capacity-two case reduces to Shortest Non-Zero Cycle.

  • Problem

    The paper addresses open questions about exact nucleon computation in matching games and its b-matching and partitioned matching extensions, including settings where the core may be empty.

    Source: §1 · p. 2

  • Method

    It replaces linear-programming feasibility steps in the matching-game stage framework with graph algorithms and relates capacity-two stages to Shortest Non-Zero Cycle.

    Source: §1 · p. 4

  • Results

    Computing a nucleon allocation is polynomial-time for ordinary matching games, NP-hard for unit-weight b-matching games with capacities at most three and partitioned games with at most three vertices per player, and polynomial-time Turing reducible to Shortest Non-Zero Cycle for b-matching capacities at most two.

    Source: §1 · pp. 3–4

  • Takeaways & Limitations

    The results give exact complexity boundaries for the studied models, including an implication for international kidney exchange with pairwise exchanges and up to three patient–donor pairs per country.

    Source: §1 · pp. 3–4

    The matching-game algorithm is polynomial in binary input length, with no strongly polynomial bound claimed; capacity-two complexity remains open absent a resolution of Shortest Non-Zero Cycle.

    Source: §1 · p. 4, §6 · p. 26

Abstract

from arXiv · show

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.

1. Introduction

Matching games model feasible pairwise partnerships and their value, while cooperative game theory addresses how that value should be divided. The paper resolves open questions about exact nucleon computation in matching games and two extensions, establishing a polynomial-time algorithm for ordinary matching games, hardness results for bounded extensions, and a conditional reduction for capacity two.

1. Introduction

  • Matching games model pairwise collaborations, with applications including kidney exchange, transportation, roommate formation, and multi-partner pairings.Partitioned matching games represent settings where one player owns several vertices, as in countries contributing multiple patient–donor pairs.Source: §1 · p. 2
  • The nucleon lexicographically maximizes coalitions’ payoff-to-value ratios, remaining defined when the core is empty and prioritizing relative shortfalls over additive ones.For matching games, its first-stage multiplicative core guarantee is at least 2/3, and the triangle example shows this bound is tight.Source: §1 · pp. 2–3
  • The survey’s open questions ask for a combinatorial algorithm in matching games and the complexity of nucleon computation in b-matching and partitioned matching games.Faigle et al. had already given a polynomial-time matching-game algorithm using compact linear systems.Source: §1 · p. 3
  • For nonnegative rational-weight matching games, a polynomial-time combinatorial algorithm uses maximum-weight matching, shortest paths, minimum-cost flow, and exact rational arithmetic.It returns a nucleon allocation and a compact description of all nucleon allocations; its running time is polynomial in binary input length, not claimed strongly polynomial.Source: §1 · pp. 3–4
  • Computing any nucleon allocation is NP-hard for unit-weight b-matching games with capacities at most three and unit-weight partitioned matching games with at most three vertices per player.The hardness proofs add a disjoint unit-weight edge; the partitioned-game result implies polynomial-time exact nucleon-based allocations for international kidney exchange would imply P = NP, even with pairwise exchanges and at most three patient–donor pairs per country.Source: §1 · pp. 3–4
  • For b-matching games with capacities at most two, exact nucleon computation is polynomial-time Turing reducible to Shortest Non-Zero Cycle, whose complexity remains open.The paper establishes no reverse reduction for the restricted stage queries or for full nucleon computation.Source: §1 · p. 4

2. Related work

Prior work establishes polynomial-time results for matching-game cores and the nucleolus, while capacitated and partitioned variants have distinct complexity boundaries. This paper’s combinatorial feasibility routine builds on the nucleon’s compact stage representation and adapts an oracle connection previously used for nucleolus separation.

2. Related work

  • For ordinary matching games, nonnegativity and edge inequalities imply coalition inequalities; prior work gives polynomial-time core algorithms and an O(n^4)-time nucleolus algorithm when the core is nonempty.The assignment game is the bipartite special case and has a nonempty core.Source: §2 · p. 5
  • For b-matching games, core membership and separation are polynomial-time solvable at capacity two, while core membership and nonemptiness become coNP-hard in stated unit-weight capacity-three settings.Partitioned matching-game core nonemptiness is polynomial-time decidable with at most two vertices per player and coNP-hard with up to three; the paper’s hardness proofs use these nonemptiness results.Source: §2 · p. 5
  • Faigle et al. introduced the nucleon and gave a polynomial-time matching-game algorithm using weighted matching to build stage constraints, with feasibility tested by linear programming.The paper retains this stage representation and supplies a combinatorial feasibility routine for singleton and pair bounds with an efficiency equality.Source: §2 · p. 5
  • A 2/3-approximate core guarantee is optimal in ordinary matching games, but a prescribed approximation factor does not optimize the full lexicographic ratio vector.A multiple-partners model allowing repeated use of an edge also has a 2/3 guarantee, under a convention different from this paper’s.Source: §2 · pp. 5–6
  • Polynomial-time algorithms for the additive nucleolus are known in several restricted matching settings, and the ellipsoid method handles general weighted matching games; a combinatorial algorithm for that additive objective remains open.For capacitated games, earlier additive hardness does not classify the multiplicative nucleon; this paper adapts the Shortest Non-Zero Cycle oracle connection to nucleon stages.Source: §2 · p. 6

3. Preliminaries

Matching games value coalitions by their best feasible partnerships, while the nucleon lexicographically maximizes coalitions’ payoff-to-value ratios. The section defines matching-game extensions and explains the nucleon’s guarantees and computation task.

3.1. Matching games and allocations

  • A coalition’s matching-game value is its maximum matching weight; b-matching permits several incident edges, while partitioned matching lets players own multiple vertices.Matching-game weights are nonnegative rationals; in partitioned games, width is the largest number of vertices owned by one player.Source: §3.1 · pp. 6–7

3.2. The nucleon

  • The nucleon lexicographically maximizes the nondecreasing list of proper coalitions’ payoff-to-value ratios, improving the smallest ratio first.Zero-valued coalitions need no ratio comparison, and the grand coalition is excluded because its ratio is always one.Source: §3.2 · pp. 7–8
  • For matching games, every nucleon allocation lies in the 2/3-approximate core, and its first-stage common guarantee is optimal.If the core is nonempty, nucleon allocations lie in the core; otherwise, the first stage maximizes the common fraction guaranteed to positive-valued proper coalitions.Source: §3.2 · p. 8
  • In the unit triangle, the unique nucleon gives each pair 2/3 of its value despite the empty core; adding a disjoint unit edge gives the triangle’s pairs and the edge ratio 4/5.The added edge’s two-player payoff totals 4/5.Source: §3.2 · p. 9, Figure 1 · p. 9
  • The computation task is to return an exact rational nucleon allocation, with a compact description of all allocations for matching games.The stated algorithm uses graph routines and exact arithmetic without the ellipsoid method or a general-purpose linear programming solver.Source: §3.2 · p. 9

4. A combinatorial algorithm for matching games

The paper replaces linear-programming feasibility checks in matching-game nucleon computation with a combinatorial procedure. It characterizes successive stages by pair and singleton bounds, solves those bounds with shortest paths and minimum-cost flow, and computes the full nucleon exactly in polynomial time.

4. A combinatorial algorithm for matching games

  • The algorithm represents each remaining stage with polynomially many pair and singleton constraints, replacing the prior linear-programming feasibility step with a combinatorial routine.This addresses the stated obstacle of handling exponentially many coalitions while retaining the efficiency equality.Source: §4 · pp. 9–10

4.5. The algorithm

  • The algorithm computes a nucleon allocation and compact description of the full nucleon in polynomial time using matching, shortest paths, minimum-cost flow, and exact rational arithmetic.Each test uses O(n^2) maximum-weight matching computations, one Bellman–Ford computation, and two minimum-cost flow computations.Source: §4 · p. 10, §4.5 · p. 19

4.1. Successive stages

  • The successive-stage scheme fixes coalition payoffs lexicographically, drops comparisons already decided, and terminates after at most n−1 stages with the nucleon.The final stage polytope P_K equals the set of nucleon allocations.Source: §4.1 · pp. 10–11

4.2. Compact stages for matching games

  • Each matching-game stage reduces to bounds on pair sums and singleton payoffs, alongside efficiency, with the terminal polytope describing the nucleon.For the weighted path with edge weights 5, 4, and 2, the three stage levels are 1, 6/5, and 4/3.Source: §4.2 · pp. 12, 14

4.3. Pair bounds with a prescribed total

  • A Bellman–Ford computation and two minimum-cost flow computations decide whether coordinate and pair-sum bounds admit a solution with prescribed total, and find one if so.The method finds the smallest and largest feasible totals, then interpolates to the prescribed total when it lies between them.Source: §4.3 · pp. 14–15

4.4. Exact arithmetic

  • A denominator bound makes binary search exact: feasibility tests locate each stage level, and continued fractions recover its rational value in polynomially many tests.The same search strategy finds minimum and maximum pair or singleton sums over the stage polytope.Source: §4.4 · p. 17

5. Hardness for b-matching and partitioned matching games

Exact nucleon computation is NP-hard for unit-weight b-matching games with capacities at most three and partitioned matching games of width at most three. The reductions use an isolated unit edge whose total payoff records whether the original game has a nonempty core.

5. Hardness for b-matching and partitioned matching games

  • Computing any exact nucleon allocation is NP-hard for unit-weight b-matching games with capacities at most three and partitioned matching games with at most three vertices per player.The hardness holds even when producing only one allocation.Source: §5 · p. 20

5.1. Direct sums calibrate component budgets

  • The direct-sum lemma assigns each component a uniquely determined first-stage payoff total based on its value and best multiplicative guarantee.The first-stage optimum is one exactly when every component core is nonempty.Source: §5.1 · pp. 20–21

5.2. The reductions

  • The reductions preserve unit weights and the capacity-three or width-three bound while adding only an isolated edge.A single call returning any nucleon allocation then decides an NP-hard core-emptiness problem.Source: §5.2 · p. 22

5.1. Direct sums calibrate component budgets

  • Adding a disjoint unit edge makes its two players’ combined payoff less than one exactly when the original game’s core is empty.The edge total therefore encodes core emptiness in every exact nucleon allocation.Source: §5.1 · p. 22, §5.2 · p. 23

5.2. The reductions

  • The hardness arises already at the multiplicative least-core stage, and the results concern exact computation rather than hardness of approximation.The encoded edge total persists in every allocation attaining the enlarged instance’s first-stage optimum.Source: §5.2 · p. 23

6. The capacity-two frontier

For capacity-two b-matching games, stage separation can be reduced to minimum-excess optimization and then to Shortest Non-Zero Cycle. This gives a polynomial-time Turing reduction, but the unconditional complexity remains open.

6. The capacity-two frontier

  • At later nucleon stages, only positive-valued proper coalitions whose payoffs are not fixed remain relevant.A coalition’s payoff is constant on the current polytope exactly when its incidence vector lies in the associated subspace.Source: §6 · pp. 23–24
  • For a candidate allocation and ratio, separation tests whether an unfixed positive-valued proper coalition violates the multiplicative payoff constraint, using LSA-MinExcess.For simple capacity-two b-matching games, LSA-MinExcess is polynomially equivalent to Shortest Non-Zero Cycle.Source: §6 · p. 24
  • Exact nucleon computation for b-matching games with nonnegative rational weights and capacities at most two is polynomial-time Turing reducible to Shortest Non-Zero Cycle.The theorem gives a conditional algorithm because the target problem’s complexity is open.Source: §6 · pp. 25–26
  • The reduction relies on an unrestricted minimum-excess oracle, and the paper establishes no reverse reduction for the restricted stage queries or full nucleon computation.Whether the restricted queries admit a simpler algorithm remains open.Source: §6 · pp. 25–26

7. Conclusions

The paper establishes a polynomial-time combinatorial algorithm for matching games and exact-computation hardness for two extensions. Capacity-two b-matching has a conditional reduction, while width-two partitioned matching remains open.

7. Conclusions

  • Matching games admit an exact polynomial-time combinatorial nucleon algorithm, while exact allocation is NP-hard for the stated unit-weight capacity-three and width-three extensions.These results resolve Open Problems 5 and 7 of Benedek et al. [2].Source: §7 · p. 26
  • The capacity-two b-matching case reduces in polynomial time to Shortest Non-Zero Cycle, but its unconditional complexity remains open.The paper also leaves open whether the restricted stage queries have a simpler algorithm.Source: §7 · p. 26
  • The complexity of nucleon computation for width-two partitioned matching games remains open, with no comparable oracle reduction established.The paper also asks whether the matching-game algorithm can be made strongly polynomial.Source: §7 · p. 26

Declaration of generative AI assistance

The authors acknowledge assistance from OpenAI’s GPT Sol 6.1 and Anthropic’s Fable 5.1 with proof details for the combinatorial algorithm.

Declaration of generative AI assistance

Loading 2610.29731v1…