| paper | d4-conf-sagt-2025-0021 |
| 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→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete, already for \(C=1\) and equal dyadic type masses. · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 6.1
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t>0\) summing to \(1\), integer capacities \(c_t\), strict rankings of partner types, and a rational bound \(B\), decide whether a stable half-matching exists with average rank-weighted cost at most \(B\). A realization assigns mass to finite individual portfolios of full partners and half-match incidences; portfolio masses sum to \(\mu_t\), capacities hold for each individual, and compatible incidences are paired into mass-preserving edges and half-match cycles. Stability uses the paper’s blocking condition interpreted over partner types.
An atomless society partitioned into cohorts of types \(t\), with mass \(\mu_t\), integer per-person capacity \(c_t\), and a ranking over partner types. Each individual receives an integral-capacity portfolio; the mass assigned to each portfolio may be fractional. Pairings preserve mass, half-match incidences form cycles, and cost is the mass-weighted sum of partner ranks, counting full matches with weight \(1\) and half-matches with weight \(1/2\).
The mirror covers only Theorem 6.1’s minimum-egalitarian-cost branch. It leaves the rank-1 and rank-r optimization variants, GSP computation, near-feasible results, structural characterizations, and experiments aside.
The strongest honest mirror is the optimization result Theorem 6.1, specifically its minimum-egalitarian-cost variant.
As printed, Theorem 6.1 says that for a Stable Fixtures instance \(I\) with regret \(r\), each of the following is NP-hard: finding a stable half-matching (equivalently, a GSP) with maximum total value assigned to rank-1 partners; finding one with minimum total value assigned at rank \(r\); and finding one with minimum egalitarian cost, the rank-weighted sum of assignments, counting a half-match with weight \(1/2\) and a full match with weight \(1\). Here \(r\) is the instance’s regret. The theorem is stated in this paper, but the hardness is inherited from cited work on the capacity-1 Stable Roommates special case, including prior hardness for stable half-matchings; the paper says the result follows trivially. It is therefore a useful anchor, but not a new hardness reduction for general capacities.
Continuous Minimum-Egalitarian Stable Half-Matching is the lead question. Consider a large peer-to-peer network whose nodes have a finite set \(T\) of service profiles. Type \(t\) has rational population share \(\mu_t>0\), with \(\sum_t\mu_t=1\), integer connection capacity \(c_t\), and a ranking of partner types. Members of a type are interchangeable for matching purposes and indifferent among peers of their own type; rankings between types are strict. This is a credible high-multiplicity regime: millions of nodes may have only dozens of profiles, while capacity remains per node and total capacity scales with the population.
An instance consists of \(T\), the binary-rational masses \(\mu_t\), capacities \(c_t\), type rankings, and a rational cost bound \(B\). Realize the population as an atomless space \(X=\bigsqcup_{t\in T}X_t\), with mass \(\mu_t\) in \(X_t\). A solution is a matching of these individuals allowing edge weights \(0,\frac12,1\): each individual has total assigned weight at most their capacity, half-weight edges form cycles, and the matching is stable in the paper’s sense—every pair is either fully matched or has at least one endpoint filled to capacity by partners ranked at least as highly as the other endpoint’s type. The question is whether there is such a stable half-matching with average egalitarian cost at most \(B\), where
\[ \mathrm{EC}(w)=\int_X\sum_y w(x,y)\,\mathrm{rank}_{t(x)}(t(y))\,d\lambda(x). \]
A finite description can group individuals by their partner-type portfolios, assign rational mass to each portfolio, pair full-match incidences symmetrically, and decompose half-match incidences into cycles. Thus each person still has an integral-capacity portfolio; it is the mass of people assigned to each portfolio that is divisible. The optimization asks for minimum average cost, exactly the objective in the third branch of Theorem 6.1.
I expect Class C hardness when the type support varies, because choosing stable portfolios can retain substantial combinatorics even after population mass becomes divisible. I would expect a tractable special case for fixed \(\tau\) and bounded capacities, where the portfolio space is finite and small. The paper’s NP-hardness does not prove hardness here: its capacity-1 instances use named-agent preference structure, and replacing those agents with atomless cohorts permits mass to split among portfolios. Whether the hard structure survives is the question.
The authors could plausibly recognize this as their problem: it retains Stable Fixtures’ capacities, blocking condition, stable half-matchings, and egalitarian objective. The paper itself points to peer-to-peer network design as an application. The co-modification is that interchangeable peers are ranked by type, so members of one type form an indifference class; that is a natural population model, though it extends the paper’s strict rankings over named agents.
The mirror covers only the egalitarian-cost branch of Theorem 6.1. The rank-1 and rank-\(r\) variants suggest companion questions, but I would not count them as additional anchors here. The GSP computation result, near-feasible capacity-modification results, solvability characterizations, and random-instance experiments are outside this mirror.
The main open questions are whether the type-portfolio formulation has polynomial-size rational certificates; how complexity depends on \(\tau\), capacities, and input bit length; and whether large finite cloned populations approximate the mass optimum in both directions. The weakest point is that cohort indifference changes the paper’s strict individual rankings, and the existing hardness may disappear entirely under this symmetry. That is a serious limitation on claiming hardness transfer, but it does not erase the value of the mirror: it isolates exactly whether egalitarian stable-matching optimization remains hard when a large society is described by a distribution over types.
The strongest objection is that Theorem 6.1’s hardness belongs to a model whose types are hard to compress. An agent’s strict ranking is over named individuals, and stability checks deviations by particular pairs. If “same type” means identical preferences in the paper’s sense, people in one type would need the same ordered list of named partners; with complete rankings, the omitted self alone makes that impossible for distinct agents. The capacity-one hardness inherited from Stable Roommates therefore does not itself establish a high-multiplicity regime.
The proponent’s stronger model repairs this by ranking partner types, making peers within a type indifferent, and distributing mass over integral partner portfolios. But that changes the preference and cost data: the paper’s rank of a named partner is not determined by the partner’s type. In a finite population, strict tie-breaking within a type can change both rank costs and which pairs block. The proposed type-rank objective is sensible, but it is a chosen extension rather than a limit forced by the paper’s model.
That is a real mismatch, but it does not defeat the mirror. The programme allows co-modifications that make fractional type averages meaningful, and a many-to-many market with type-level preferences is a plausible Stable Fixtures variant. Portfolio masses and type-level pairing constraints could retain integral capacity for each person while making population mass continuous. The resulting minimum-cost stable half-matching question is computational and distinct from an existing analytic treatment. Whether it is tractable or hard would be an answer, not a reason to reject the question.
So I cannot honestly make the universal negative case the prompt asks for. The mismatch weakens the claim that this is a direct continuization of Theorem 6.1, but the type-level version remains a credible mirror; the strongest anchor survives.
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.