Nucleolus of a Permutation Game → Rational Linear Programming Complexity open
Unsolved
Why this question matters
Moderate: the nucleolus is an established fairness rule in cooperative exchange; a positive result would extend efficient computation beyond the known cyclic permutation-game subclass and apply to unbounded-cycle kidney exchange models.
Benedek et al. (EJOR 2026, Open Problem 1) explicitly ask for the complexity of computing the nucleolus for permutation games and partitioned permutation games. Solymosi et al. (2005) solve only cyclic permutation games; that hypothesis is absent here.
The reduction to construct
Input is an n-by-n matrix of nonnegative binary rational utilities with zero diagonal. For coalition S, v(S) is the maximum total utility of a permutation of S, where fixed points represent zero-value dummy assignments. The output is the unique rational efficient and individually rational payoff vector that lexicographically minimizes the nonincreasing list of coalition excesses v(S)−x(S). There is no NO-SOLUTION case.
Input is an explicitly listed rational linear program with polynomially encoded coefficients. Valid outputs are all optimal rational solutions, or NO-SOLUTION when infeasible or unbounded. For this reduction every constructed instance must have an optimum.
Find deterministic polynomial-time F and G so every optimal LP output decodes to the exact nucleolus of the source permutation game, with polynomial bit bounds on the LP and payoff vector.
High: the lexicographic sequence ranges over exponentially many coalitions. An assignment oracle computes each coalition value, but a compact separation or extended formulation for every lexicographic stage is missing.
What a complete answer must include
Provide deterministic polynomial-time F and G with bit-size bounds. Prove correctness for every legal input and every valid target output, including NO-SOLUTION where defined; independently check recovered answers on representative instances. A generic SAT or ILP encoding alone does not meet the novelty goal.
References
- Computing Balanced Solutions for Large International Kidney Exchange Schemes When Cycle Length Is Unbounded ↗
- Computing the Nucleolus of Cyclic Permutation Games ↗
Literature checked 2026-09-26. Web searches 2026-09-26: "nucleolus permutation games complexity 2026", "computing nucleolus cyclic permutation games", and board aliases. Read EJOR 2026 introduction and conclusion and checked the earlier cyclic-subclass theorem. The EJOR PDF was intermittently inaccessible to line search after initial retrieval; the open-problem text was also indexed by search. Gate 5 route: use assignment dual variables to separate coalitions at each excess level, then compress the lexicographic LP sequence into one polynomial formulation. The missing separation theorem is substantial and untested; Gate 6 not assessed.