| paper | d4-conf-sagt-2021-0003 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: \(\mathrm{P}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1.1
statement extracted from the paper’s text layer
Given a bipartite type-compatibility graph \(H\), rational type masses \(\mu\), and a rational per-type allocation \(q\), form for each admissible integer \(d\) the finite simple \(3\)-matching game with \(d\mu_t\) agents of each type and an edge between every pair whose types are adjacent in \(H\). Let \(q^{(d)}\) be the per-type payoff vector in that game’s nucleolus. Decide whether \(\lim_{d\to\infty} q^{(d)}=q\), with \(d\) ranging over integers for which every \(d\mu_t\) is integral.
A dense bipartite matching market whose agents are grouped into role types with mass \(\mu_t\); each agent has capacity \(3\), and compatibility and deal value depend only on type. A coalition with type masses \(y_t\) has limiting value \(\nu_H(y)\), given by maximizing total deal mass \(z_e\) subject to \(z_e\ge0\) and \(\sum_{e\ni t}z_e\le3y_t\); the target is the limit of the finite games’ per-type nucleolus allocations.
Finite nucleoli may be shaped by coalitions whose size is negligible relative to \(d\), so the mass LP does not establish convergence or determine the limit; the proponent flags convergence as open but supplies no structure for it.
fatal: False
The mirror covers only Theorem 1.1’s unweighted, simple, bipartite \(b\equiv3\) nucleolus-recognition result in dense type-block markets; it leaves Theorem 1.2 and the paper’s other results aside.
The strongest anchor is Theorem 1.1, proved in this paper: deciding whether a given allocation is the nucleolus of an unweighted simple bipartite \(3\)-matching game is NP-hard, even when the graph has maximum degree \(7\). This is hardness for recognizing the game’s fairness solution, not for finding a matching.
A natural high-multiplicity setting is a large matching market with many agents in a modest number of role categories. An agent’s type records their side of the market, capacity, and eligible partner categories; agents of the same type have the same deal value and all other problem-relevant attributes. A deal earns one unit, and each agent can participate in at most three deals. Let \(H=(L\dot\cup R,E)\) be the bipartite compatibility graph on the types, and let \(\mu_t\) be the fraction of the population of type \(t\), with \(\sum_t\mu_t=1\).
For a coalition containing mass \(y_t\in[0,\mu_t]\) of each type, define its value by the continuous matching LP
\[
\nu_H(y)=
\max \sum_{e\in E}z_e
\quad\text{subject to}\quad
z_e\ge 0,\qquad
\sum_{e\ni t}z_e\le 3y_t\quad(t\in L\cup R).
\]
Here \(z_e\) is the mass of deals between the endpoint types. An allocation \(q_t\) pays each unit of type \(t\) the same amount, so a coalition of mass vector \(y\) receives \(\sum_t y_tq_t\). This is a plausible market model when compatibility depends on role rather than on named individuals. In the atomless population, the constraint that a particular pair can contract only once disappears; that is a co-modification of the matching model needed for a mass-based society.
I would pose Block-Limit \(3\)-Matching Nucleolus Recognition as the mirror of Theorem 1.1. Its input is \(H\), rational masses \(\mu\), and a candidate rational per-type allocation \(q\). For each integer \(d\) making every \(d\mu_t\) integral, form the finite simple game with \(d\mu_t\) agents of type \(t\), connecting every pair of agents whose types are adjacent in \(H\). Let \(q_t^{(d)}\) be the payoff per agent of type \(t\) in that game’s nucleolus; it is well-defined because permutations within each type preserve the game and the nucleolus is unique. The question is whether \(q^{(d)}\) converges, as \(d\) grows through those integers, to \(q\). A “yes” answer means \(q\) is the asymptotic per-capita nucleolus; a “no” answer means the sequence fails to converge to \(q\). The matching LP above gives the continuous society’s coalition values, while the limit supplies a precise nucleolus notion without imposing an arbitrary ordering on an uncountable set of coalition excesses.
This mirrors the paper’s nucleolus-recognition problem for unweighted bipartite \(b\)-matching games, in a regime where the population scale \(d\) is much larger than the number \(\tau\) of role types. A tractability result would naturally be stated in \(\tau\), \(|E|\), and the binary input length \(L\), rather than in \(d\). My initial expectation is Class A: coalition values are LP-defined over a \(\tau\)-dimensional mass space, which gives continuous optimization a plausible route to a compact characterization. That is only a conjecture; computing the full lexicographic refinement and proving convergence are central parts of the problem.
The mirror covers only the simple, unweighted, bipartite \(b\equiv3\) nucleolus-recognition result, restricted to exchangeable type blocks. It does not cover the paper’s other results. Its weakest point is substantial: replacing an arbitrary sparse graph by complete blocks destroys the maximum-degree-\(7\) structure in Theorem 1.1, and the paper’s hardness result therefore does not establish hardness for this limit problem. The next questions are whether the limit always exists, whether it agrees with a direct fractional-game nucleolus, and whether hardness survives in a high-multiplicity model that retains sparse interaction structure.
Theorem 1.1 is a real computational anchor, so “there is no named result to mirror” cannot carry the negative case. The stronger objection is that the paper’s hard instances depend on the exact sparse interaction graph: a coalition’s value is determined by which particular vertices and edges it contains. High multiplicity compresses those identities only when agents of a type have the same relevant relationships.
For the proposed role-type model, that condition makes compatibility between two types a complete block of edges. It is a plausible matching market, but it changes the graph regime behind the theorem: individual degrees grow with the number of copies, and the finite simple matching value approaches a fractional capacity LP. Theorem 1.1 gives no reason to expect its hardness to survive that change. A mirror that preserves sparse interactions has the opposite problem: it must retain neighborhood or component information, because type masses alone do not tell us which compatible agents occur together in a coalition. For arbitrary graphs, encoding that information can make the number of types grow with the graph.
There is also a gap between the displayed mass LP and the proposed nucleolus question. The nucleolus ranks excesses over all coalitions, including small coalitions whose mass vanishes in the limit. The LP specifies macroscopic coalition values; it does not establish that the finite-copy nucleoli converge or that their limit can be computed from those values. Defining the mirror through the sequence of finite games is coherent, but convergence and an efficient characterization are additional results to prove.
That makes the case against this anchor a case about distance from the paper’s hard problem: the clean mass model is a dense market variant, while a sparse-preserving model may lose the type compression that motivates continuization. It does not establish that no worthwhile mirror exists. Role-based matching markets are plausible, and the authors may recognize their nucleolus problem as part of the same family. So the honest negative case is limited: the paper does not itself support the proposed complexity story, but this anchor survives as a credible new continuous-population question.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.