| paper | d4-conf-aaai-2004-0026 |
| 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}\text{-complete}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given types \(T\) with rational masses \(\mu_t>0\), \(\sum_{t\in T}\mu_t=1\), per-unit assigned payoffs \(p_t\), and issue tables \(v_i:\{0,1\}^{C_i}\to\{0,1\}\) with \(|C_i|\le 3\), decide whether there are participation fractions \(q_t\in[0,1]\) such that \(\sum_i\widetilde v_i(q)>\sum_t p_t\mu_tq_t\), where \(\widetilde v_i\) is the multilinear extension of \(v_i\).
A coalition selects mass \(x_t=\mu_tq_t\) from each complete type. Each issue's value is the expected original table value when one representative of each involved type is independently sampled from the society and counts as participating with probability \(q_t\); the coalition blocks when total expected issue value exceeds its assigned payoff.
The paper does not determine fractional issue values, and the multilinear rule adds random representative sampling that may not describe a coalition selecting its own members.
fatal: False
The mirror covers Theorem 3's blocking and core-membership question. It leaves Theorem 1's Shapley computation and Theorem 2's manipulation hardness unaddressed.
The strongest anchor is Theorem 3, proved in this paper by reduction from VERTEX-COVER. It says that CHECK-IF-BLOCKED is NP-complete even when every issue concerns at most three agents, each issue’s explicitly listed value is in \(\{0,1\}\), and every issue value function—and therefore their sum—is increasing and superadditive. The question is whether some coalition’s value exceeds the sum of its members’ assigned values. This is a good anchor because it concerns the paper’s underlying stability problem, not just a formulation of it.
My mirror is Multilinear Continuous Blocking. Let \(\Theta\) be a set of complete agent types, with positive rational masses \(\mu_t\) summing to \(1\). A type includes all the issue-relevant characteristics and the same assigned payoff for every agent of that type. A proposed blocking coalition selects mass \(x_t\in[0,\mu_t]\) of each type; write \(q_t=x_t/\mu_t\) for the fraction selected.
Each issue \(i\) concerns a set \(C_i\subseteq\Theta\) of at most three types and has a binary table \(v_i:\{0,1\}^{C_i}\to\{0,1\}\). Extend that table to fractions by its multilinear extension:
\[
\widetilde v_i(q)=
\sum_{z\in\{0,1\}^{C_i}}v_i(z)
\prod_{t:z_t=1}q_t
\prod_{t:z_t=0}(1-q_t).
\]
This has a concrete interpretation: issue \(i\) samples one representative from each relevant type, independently, and evaluates the original issue table on the representatives who joined the coalition. If type \(t\) has payoff \(p_t\) per unit of mass, the continuous question is whether there exists \(x\) such that
\[
\sum_i\widetilde v_i(x/\mu)>\sum_{t\in\Theta}p_t x_t.
\]
A solution is such a mass vector \(x\). The society is continuous because agents are grouped by type and a coalition may take any fraction of each type; the issue outcome itself remains the paper’s scalar value.
A plausible regime is a large pool of firms or contractors repeatedly drawn from the same capability and contract profiles. Each type might represent a supplier profile, issues might be small projects involving a coordinator and one of two specialist profiles, and a deviation asks whether a subset of the market can earn more together than its assigned payoff. With \(M\) near-identical agents per type, the population size is \(N=M|\Theta|\), while the support is only \(\tau=|\Theta|\). The profiles must be complete for the problem: agents sharing a type have the same issue roles and payoff.
The connection to Theorem 3 is exact at all-or-none type choices, where \(q_t\in\{0,1\}\): the continuous issue value is then precisely the paper’s table value. For its Vertex Cover construction, use one type for each vertex and a coordinator type. Each edge issue pays \(1\) exactly when the coordinator and at least one endpoint type participate. If its endpoint types are \(u,v\), its extension is \(q_0(q_u+q_v-q_uq_v)\). Set the total payoff of each full type cohort to the corresponding payoff in the paper’s reduction, equivalently \(p_t\mu_t=d(a_t)\). Replicating each type \(M\) times preserves that cohort total while making the population arbitrarily larger than the support.
This mirror is expected to be Class B: hardness transfers. The continuous objective minus coalition payoffs is affine in each \(q_t\) when the other coordinates are fixed. Its maximum over the box is therefore attained at a corner. So if any fractional coalition blocks, some all-or-none selection of types blocks as well. The continuous question has a binary witness, and the paper’s reduction makes deciding whether such a witness exists NP-complete; deciding core membership is consequently coNP-complete. The hardness lives in the incidence structure among types and issues, so making each type a large cohort does not erase it.
This case covers Theorem 3 only. It also suggests follow-up questions: what happens with other continuous extensions of the issue tables; whether the problem becomes tractable under restrictions such as bounded incidence-treewidth; and whether approximate blocking can be decided more efficiently.
The weakest point is that multilinear extension is a choice of semantics, not an interpolation forced by the paper. It models fractional participation through expected issue value, which suits projects staffed from a pool, but other settings may use thresholds or production proportional to mass and yield a different problem. The case survives that limitation as a specific, defensible mirror: it retains the paper’s exact issue tables and core question at whole-type coalitions, while giving fractional mass a clear operational meaning.
Theorem 3 is a real computational result, and the core problem has an obvious large-market story: many firms share a few capability profiles, and a coalition may have reason to break away. I cannot rule out that a continuous version would be worth studying. The strongest objection is narrower: the paper does not specify what an issue is worth when a coalition contains a *fraction* of a type, and that choice determines whether there is an interesting mirror of the theorem.
Take an edge issue in the paper’s Vertex Cover reduction. Its value is \(1\) exactly when the coordinator and at least one endpoint participate. If \(q_0,q_u,q_v\) are the fractions of those types in a coalition, the proposed multilinear extension assigns value \(q_0(q_u+q_v-q_uq_v)\). That is a coherent stochastic production rule: sample a representative of each type and evaluate the original table. But it is an extra assumption, not a consequence of the characteristic function. A support-based rule could give the full value whenever \(q_0>0\) and either endpoint fraction is positive; a capacity model could scale value with the participating mass. These alternatives agree with the paper’s table when each type is wholly in or out, yet can disagree about whether a coalition blocks. For example, with payoff density \(0.6\) for each type and \(q_0=q_u=\varepsilon,\ q_v=0\), the support rule gives value \(1\) against payoff \(1.2\varepsilon\), while the multilinear rule gives value \(\varepsilon^2\) against that same payoff.
The support rule has its own problem: in an atomless society, arbitrarily small positive masses can claim the full value of a project. That makes a negligible coalition a blocker. The multilinear rule avoids this collapse by making project value probabilistic, but then the result depends on a new random-assignment mechanism. It samples workers from the whole type population rather than describing what a coalition that has selected its members can accomplish. That may suit a particular market, but it is a substantive change to the game.
The stronger alternative would specify a production function for each issue over participating type masses, perhaps based on capacity, scale, or complementarity. Such a model could be sensible for large pools of firms or contractors, and its blocking problem could be computationally interesting. But the paper’s binary issue tables do not determine those functions. The resulting complexity question would be about the added production technology as well as the population continuum; the Vertex Cover reduction alone would not justify it.
So the negative case does not defeat every plausible mirror. The firm-pool scenario is credible, and a specified mass-based production model could be a worthwhile continuation. The case against is that the proponent’s strongest anchor does not select or validate its key fractional semantics: the mirror’s answer can turn on a modeling choice that the theorem leaves open.
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.