| paper | d4-conf-ijcai-2021-0126 |
| 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, even with fixed \(N=2\) for every fixed \(k\geq1\). · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t \geq 0\) summing to \(1\), a symmetric type-level friendship relation \(F\), a tagged representative of type \(a\), a loyalty depth \(k\), a reference population scale \(N\), and a rational normalized threshold \(q\), choose \(x_t \in [0,\mu_t]\). Let \(S=\{a\}\cup\{t:x_t>0\}\), and let \(v_b^N(x)=N\sum_{t:(b,t)\in F}x_t-\sum_{t:(b,t)\notin F}x_t\), with the tagged representative’s own mass omitted. Is there an \(x\) such that \(\min\{v_b^N(x): b\in S,\ d_{F[S]}(a,b)\leq k\}\geq q\)?
A distribution over complete friendship types, with a tagged representative and a selectable mass \(x_t\) of each type. For each selected support, evaluate the paper’s \(k\)-fold loyal utility as the minimum base utility among types within loyalty distance \(k\); use \(N\) as the reference scale for the FOHG friend payoff.
The \(n\)-scaled friend payoff and \(-1\) enemy payoff leave a modeling choice: under bounded per-capita normalization, enemy mass vanishes as \(N\) grows, so the paper does not single out one canonical limiting cardinal scale.
fatal: False
The mirror covers Theorem 2’s \(k\)-fold FOHG BestCoalition result and can also cover Theorem 3’s locally egalitarian variant. It leaves the core results and the ASHG and MFHG results aside.
The strongest anchor is Theorem 2, proved by the authors via a reduction from SetCover: for every \(k\geq 1\), deciding BestCoalition is NP-complete for the \(k\)-fold loyal variant of symmetric friend-oriented hedonic games (FOHGs). Its input is a game, a distinguished agent \(i^\star\), and a rational threshold \(q\); the question is whether some coalition \(C\ni i^\star\) gives \(i^\star\) loyal utility at least \(q\).
A natural high-multiplicity setting is a large membership organization that repeatedly forms working groups. Members have role or credential profiles, and two members with the same profile have the same friendship relation to every profile. The type is that complete profile; \(\mu_t\) is the fraction of the available membership of type \(t\). A plausible regime has hundreds of thousands of members but only dozens of recurring profiles. A tagged representative asks what mix of profile mass could form a sufficiently good coalition.
Here is the lead mirror, Continuous Loyal Best-Coalition\(_k\). An instance has a finite set \(T\) of \(\tau\) types; rational masses \(\mu_t\geq 0\) summing to \(1\); a symmetric type-level friendship relation \(F\); a tagged representative of type \(a\); a rational threshold \(q\); and the loyalty depth \(k\). For a candidate coalition, choose a mass vector \(x\) with \(0\leq x_t\leq\mu_t\). Its support is the set of types present in positive mass, together with the tagged representative’s type. Write \(v_b(x)\) for the base FOHG utility of type \(b\) against that coalition composition. To preserve the paper’s friend/enemy payoff convention at a reference population scale \(N\), one possible normalization is \(v_b(x)=\sum_{t:(b,t)\in F}x_t-\frac{1}{N}\sum_{t:(b,t)\notin F}x_t\); the tagged representative has zero mass. The instance asks whether there is an \(x\) for which every type at distance at most \(k\) from \(a\) in the friendship graph induced by the coalition’s support has \(v_b(x)\geq q\). Such an \(x\), with its support, is a solution.
This keeps the paper’s underlying question intact: find a coalition for a representative whose loyal utility clears a threshold. It replaces selecting individual members with selecting available type mass. Crucially, loyalty still depends on who is present: adding any positive mass of a type can bring that type’s utility into the minimum, even if the mass is tiny. The continuous problem therefore retains a genuine support-selection decision.
The second anchor is Theorem 3, also proved by the authors, with details deferred to the extended version: BestCoalition is NP-complete for the locally egalitarian variant of symmetric FOHGs. Its mirror, Continuous Limit Best-Coalition, uses the same instance and mass vector, but takes the minimum \(v_b(x)\) over the entire connected component of \(a\) in the friendship graph induced by the coalition support. It asks whether that minimum is at least \(q\). This is the direct mass analogue of the paper’s limit utility, where loyalty has propagated through the whole connected part of the coalition.
My working prediction for both continuous questions is Class C: potentially hard for continuum-specific reasons. For any fixed support, either query reduces to rational linear feasibility: compute the relevant loyalty-reachable types and require their utilities to meet \(q\). The remaining search is over which types to include. There are up to \(2^\tau\) supports, so these formulations are fixed-parameter tractable in \(\tau\) by support enumeration and LP; whether the dependence on \(\tau\) can be made polynomial is the central question. The positive-mass activation of loyalty gives a plausible source of hardness that survives fractional mass. But that is a conjectured route, not a result. A gap-preserving embedding of the discrete problem could instead put a continuous hardness result in Class B.
The scope here is only BestCoalition for \(k\)-fold loyalty and the locally egalitarian limit in symmetric FOHGs. It does not cover core existence or computation, nor the paper’s results for ASHGs or MFHGs.
The main weakness is that the paper’s NP-hardness does not itself establish hardness in the proposed regime. Its SetCover construction is a finite-agent construction; it may rely on many distinct profiles, whereas the intended mirror has \(\tau\ll N\). Also, allowing fractional mass can make a threshold attainable when no discrete coalition attains it. The FOHG payoff scale needs care too: after normalization, the enemy term carries a \(1/N\) factor. So the continuous questions are credible mirrors of the authors’ BestCoalition problem, but neither their hardness nor their tractability follows from Theorems 2 and 3.
Theorem 2 and Theorem 3 are genuine computational anchors, so I would not argue that the paper lacks a result to mirror. They reduce to the same underlying question: can a tagged agent join a coalition whose utility, after taking a minimum over loyal coalition members, reaches a threshold? Theorem 3 changes which members enter that minimum by using the whole connected component.
I would also grant the strongest plausible setting for the proposed mirror: a large organization with recurring roles, where friendship is uniform between roles. That gives repeated, complete agent types and a sensible high-multiplicity regime. The difficulty is that the paper’s FOHG payoffs make the continuum limit depend sharply on how utility is normalized. With \(N\) agents, an agent’s utility is \(N\) times their number of friends in the coalition, minus their number of enemies. If the coalition contains friend mass \(f\) and enemy mass \(e\), this is \(N^2 f-Ne\). Dividing by \(N^2\) to obtain a bounded per-capita utility gives \(f-e/N\): as \(N\) grows, enemy mass disappears. Yet enemy counts affect the paper’s loyal utilities and thresholds. Keeping a fixed \(\pm1\) payoff per type mass preserves enemy effects, but changes FOHG’s population-scaled friend payoff and its cardinal meaning. The tagged-agent and finite-\(N\) formulations can retain those details, but they do not supply a canonical population-limit model.
There is a second problem even after choosing a normalization. Loyalty depends on presence: adding an arbitrarily small positive mass of a type can make its utility enter the minimum, while zero mass excludes it. For both anchors, the fixed-support problem may be a linear feasibility problem, but the search over supports remains. The consequential decision is still whether a type is present at all; the amount of its mass can be arbitrarily small. In the locally egalitarian mirror this is especially direct: any positive mass that joins the tagged agent’s component can affect the minimum as much as a large mass. This is a crisp support-based model, but its central operation is discontinuous in mass, and the proposed relaxation does not remove the paper’s type-selection problem.
That is a reason to doubt that either anchor unlocks the continuous-optimization advantage motivating ChoCo; it is not proof that the questions are uninteresting. A finite-\(N\) mass relaxation could still be a worthwhile mixed discrete-continuous problem. I cannot honestly rule that out for every role-based scenario. The negative case is therefore limited: both mirrors face the same normalization and support-selection obstacle, but a reader who regards a natural hybrid model as sufficient may still find the proponent’s case convincing.
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.