| paper | d4-conf-aaai-2017-0416 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
parameterized→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete and \(\mathrm{W}[1]\)-hard parameterized by \(k\); no FPT algorithm unless \(\mathrm{FPT}=\mathrm{W}[1]\). · discrete side: parameterized · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given \(\tau\) types with rational masses \(\mu_t>0\) summing to \(1\), and a rival relation \(E\) on types, choose invited masses \(x_t\in[0,\mu_t]\) to maximize \(\sum_t x_t\), subject to \(x_t=0\) or \(x_u=0\) for every \(\{t,u\}\in E\). Equivalently, given a rational threshold \(q\), decide whether an individually rational invitation of mass at least \(q\) exists.
A continuous society has types \(T\), rational masses \(\mu_t\), no friends, universal approval of attendance mass, and a symmetric, loop-free rival relation \(E\). Inviting any positive mass of a type requires inviting zero mass of each rival type; the objective is to maximize invited mass.
The paper’s parameter \(k\) counts invited individuals, while the mirror’s threshold \(q=k/\tau\) effectively counts selected types; this preserves the graph hardness mechanism without transferring the theorem’s parameterized statement exactly.
fatal: False
The mirror covers the enemy-only individual-rationality case and the conflict-graph hardness mechanism of Theorem 4. It leaves aside friend constraints, stable invitations, bounded-enemy cases, and the paper’s other parameterized results.
My lead mirror is a maximum-mass version of the paper’s enemy-only, individually rational invitation problem. It uses the same willingness rule—an invited agent must have no enemy attending—and asks how much of a large society can attend.
The anchor is Theorem 4, proved in this paper. It says that \(k\)-IR-Invitation is W[1]-complete when the maximum number of enemies per agent is not bounded by any function of \(k\). The paper proves hardness by reducing from \(k\)-Independent-Set: each graph vertex becomes an agent with no friends, its graph neighbors become its enemies, and its approval set is \(\{k\}\). Membership follows from Theorem 2. The reduction’s combinatorics are the conflict graph among agents.
Here is the continuous question I would hand to a prover: Maximum Rival-Free Invitation Mass. The instance is a set \(T\) of \(\tau\) types, rational masses \(\mu_t>0\) summing to \(1\), a symmetric, loop-free rival relation \(E\) on types, and a threshold \(q\in[0,1]\). Every agent approves every total attendance mass in \([0,1]\), has no friends, and regards every member of each rival type as an enemy. Choose invited masses \(x_t\in[0,\mu_t]\). The question is whether there is an invitation with \(\sum_{t\in T}x_t\ge q\) such that, for every rival pair \(\{t,u\}\in E\), at least one of \(x_t,x_u\) is zero. A witness is the vector \(x\); equivalently, one can ask for a vector maximizing \(\sum_t x_t\).
This models, for example, a very large event with attendees drawn from organizational blocs. Members of a bloc share its rival blocs and attendance preferences, while the number of people is much larger than the number of blocs: \(N\gg\tau\). A bloc can be a positive-mass type even though it contains many people. The enemy-only restriction is deliberate: it is exactly the restriction used in Theorem 4’s reduction.
The fractional action does not erase the graph problem here. Any feasible vector has an independent set as its positive-mass support, and every such type can be invited in full. So a maximum always has \(x_t\in\{0,\mu_t\}\). With uniform masses \(\mu_t=1/\tau\) and \(q=k/\tau\), the question is equivalent to whether the type conflict graph has an independent set of size at least \(k\), hence of size exactly \(k\) after taking a subset. This restricted continuous problem is W[1]-complete parameterized by \(k\), by the same independent-set reduction as Theorem 4. For arbitrary rational masses it is weighted Independent Set, and is NP-hard as \(\tau\) grows. I expect hardness transfers (Class B): the hard choices live in the type conflict graph, not in the total number of people. The mirror also suggests questions about algorithms for restricted rival graphs, and about how adding friend requirements or stability changes the weighted type-level problem.
The scope is just Theorem 4’s enemy-only IR case. I would not use it to claim a continuous treatment of the paper’s stable-invitation results: in an atomless population a single deviator adds zero mass, so the stability condition needs its own careful definition and analysis.
The weakest point is the change from the paper’s exact-size question, with approvals such as \(S_i=\{k\}\), to a maximum-mass threshold question where every size is approved. Fractional selection makes an exact-mass version a poor mirror: part of one type could meet the target without corresponding to a \(k\)-agent solution. The maximum objective avoids that artifact and matches the paper’s stated goal of inviting as many agents as possible. Still, a referee could reasonably say this mirrors the invitation predicate and its hardness mechanism, rather than the exact \(k\)-IR problem in every detail.
Theorem 4 is the proponent’s strongest anchor: it is a named parameterized-complexity result about a computational problem. The most defensible case against its mirror is that the high-multiplicity version loses the feature that makes continuization valuable.
Take the proposed rival blocs. If type \(t\) and type \(u\) are rivals, every attendee of either type has an enemy among the attendees of the other type. Individual rationality therefore requires \(x_t x_u=0\). Feasible positive-mass supports are independent sets of the type-conflict graph. With universal approval and a maximum-mass objective, any feasible solution can fill every type in its support, so an optimum has \(x_t\in\{0,\mu_t\}\). A threshold \(q\) is feasible exactly when some independent set has total weight at least \(q\). The masses supply vertex weights; they do not create fractional choices that improve the graph selection problem. Replacing the conflict rule with a constraint that tolerates partial enemy mass could create such choices, but it changes SIP’s willingness condition.
There is also a parameter mismatch. Theorem 4’s \(k\) counts invited individuals. In a high-multiplicity instance, \(N\) identical copies of each vertex would make the corresponding invitation size scale with \(N\); keeping \(k\) fixed as the population grows makes the target mass vanish. The proponent’s \(k\) instead counts selected types. That is a sensible parameter for a new weighted independent-set question, but it is not the paper’s parameterized result carried over to a continuous population.
The type requirement makes this limitation hard to avoid. A type must include the agent’s full enemy profile. If people within a bloc have different individual enemy sets, separating those profiles increases the support until multiplicity disappears. Keeping a small number of types means their interactions are uniform, and a rival type excludes an entire type from any individually rational invitation. Fractional enemy exposure or probabilistic willingness could avoid that all-or-nothing choice, but those are new preference rules.
That is the best negative case: this mirror retains a plausible high-multiplicity setting, yet its continuous layer reduces to capacities on a discrete conflict graph, and its parameterized claim shifts from people to types. The case is still weak. Large rival blocs are plausible, the question remains recognizably about SIP, and a hard weighted graph problem can be a worthwhile Class B mirror. I cannot honestly conclude that this anchor fails the programme’s gate; I can only argue that its continuous contribution is limited.
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.