| paper | d4-conf-ijcai-2015-0588 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: NP-complete, even for \(\tau=1\) and \(\Gamma=\top\), with either strictly positive or strictly negative formula weights. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3.1
statement extracted from the paper’s text layer
Given a finite variable set \(V\), a feasible-outcome constraint \(\Gamma\), complete goalbases \(G_1,\ldots,G_\tau\) with positive rational masses \(\mu_1,\ldots,\mu_\tau\) summing to \(1\), and a rational threshold \(\gamma\), is there an interpretation \(\sigma\models\Gamma\) such that \(\sum_{t=1}^{\tau}\mu_tG_t(\sigma)\ge\gamma\)?
A society is a distribution over complete utility types: each type \(t\) has mass \(\mu_t\) and goalbase \(G_t\). The decision variable is a common feasible interpretation \(\sigma\), and its per-capita utilitarian value is \(\sum_t\mu_tG_t(\sigma)\).
The type-weighted objective can be collapsed into one goalbase, so the population representation adds little computational structure and hardness already holds with one type.
fatal: False
The mirror covers the utilitarian decision results in Theorem 3.1; the normalized egalitarian decision results in Theorem 3.5 also have a support-based type-mass analogue. It does not establish continuous versions of the tractability frontiers in Sections 5 and 6.
The strongest mirror is utilitarian optimization over a population divided into cohorts with shared goalbases. Think of a large organization choosing one feasible policy, represented by a Boolean interpretation: each cohort has a complete weighted-goalbase utility description, and its mass is the fraction of the organization in that cohort. The cohorts must share the same utility function in every respect the model uses; they are not merely broad demographic labels. A plausible regime is a large membership choosing from a standard set of preference templates, with \(N\) people and \(\tau\) templates where \(N\gg\tau\).
Lead: High-Multiplicity Weighted-Goalbase Social Welfare. An instance consists of variables \(V\), a feasible-outcome constraint \(\Gamma\), goalbases \(G_1,\ldots,G_\tau\), positive rational masses \(\mu_1,\ldots,\mu_\tau\) summing to \(1\), and a rational threshold \(\gamma\). Each \(G_t\) is the complete utility description of type \(t\). Ask whether there is an interpretation \(\sigma\models\Gamma\) such that
\[
\sum_{t=1}^{\tau}\mu_tG_t(\sigma)\ge\gamma.
\]
A solution to the optimization version is a feasible interpretation maximizing this per-capita utilitarian welfare. A fixed-interpretation variant asks whether a supplied feasible \(\sigma\) is optimal.
The anchor is Theorem 3.1, proved in this paper: SW-VAL-CHECK is NP-complete and SW-INT-CHECK is co-NP-complete; the hardness holds on both positive and negative single-agent scenarios without constraints. In the mirror, SW-VAL-CHECK asks whether the maximum mass-weighted utility reaches \(\gamma\), and SW-INT-CHECK asks whether a supplied interpretation maximizes it. The single-agent hardness carries over with \(\tau=1\); repeating that type across a large population leaves the objective’s maximizer unchanged. Thus the likely answer is Class B: hardness transfers. The hard part lies in the Boolean outcome and utility structure, not in the number of named people.
This is a direct fit to the paper’s problem: it already optimizes a common interpretation against agents’ cardinal utilities. For a finite profile with \(n_t\) agents of type \(t\), set \(\mu_t=n_t/n\). The continuous objective is the paper’s utilitarian sum divided by \(n\), so the optimizer is unchanged and thresholds scale by \(1/n\). Conversely, a rational distribution can be expanded to counts using a common denominator, though a binary-encoded denominator can make that expansion exponentially large. The mirror’s algorithmic question is therefore whether one can work from the compressed type masses, with running time in \(|V|\), \(\tau\), formula size, and bit length—not the expanded population.
A second, credible mirror is Rawlsian fairness.
High-Multiplicity Normalized Egalitarian Optimization. Use the same instance, require at least two positive-mass types, and require every type’s goalbase to be normalized over \(\Gamma\): its minimum feasible value is \(0\) and its maximum is \(1\). Define
\[
E_\mu(\sigma)=\min_{t:\mu_t>0}G_t(\sigma).
\]
Ask whether some feasible \(\sigma\) has \(E_\mu(\sigma)\ge\gamma\); an optimization solution maximizes \(E_\mu\). Equivalently, the population is partitioned into positive-mass cohorts, and the score is the least utility received by any member. That is the normalized egalitarian objective from the paper.
Its anchor is Theorem 3.5, also proved here: on normalized, non-trivial scenarios, EG-VAL-CHECK is NP-complete and EG-INT-CHECK is co-NP-complete. The continuous value-check asks whether the maximum of \(E_\mu\) reaches \(\gamma\); the optimality-check asks whether a supplied interpretation maximizes it. A finite normalized instance maps to its empirical distribution: the minimum across agents is exactly the minimum across positive-mass types. Replicating every member of every cohort preserves that distribution and the fairness objective. So this mirror also predicts Class B: hardness transfers.
The utilitarian anchor is the lead: its objective genuinely uses cohort mass, and its hardness already holds with one type. The egalitarian mirror is worth including because it preserves the paper’s distinct fairness result, not as an extra claim about tractability. Neither mirror changes the outcome space into fractional decisions; the continuous object is the population, while feasible interpretations remain the paper’s combinatorial outcomes.
The weakest point is the egalitarian mirror’s treatment of mass. Once a type has positive mass, its size does not affect the minimum: a tiny cohort can determine the welfare just as much as a large one. That is faithful to “least happy agent,” but makes this anchor less informative about the quantitative role of a continuous population. The utilitarian mirror does not share that weakness, and the exact discrete-to-mass dictionary makes both questions recognizable as the paper’s optimization problems.
The strongest objection is that the utilitarian mirror makes the population disappear at the level of the optimization problem. For each type goalbase \(G_t\), multiply its formula weights by \(\mu_t\) and combine the resulting formulas into one goalbase \(G_\mu\). Then, for every feasible interpretation \(\sigma\),
\[
G_\mu(\sigma)=\sum_t \mu_t G_t(\sigma).
\]
The proposed High-Multiplicity Weighted-Goalbase Social Welfare problem is therefore exactly individual utility maximization over a single weighted goalbase—the setting the paper already studies. Its masses are legitimate coefficients, but the distribution over types carries no information the objective needs once those coefficients have been combined. That makes Theorem 3.1 a poor case for a *new population computation*: its hardness already holds with one agent, and the proposed version reduces to the paper’s individual-decision problem.
A large group choosing a common policy, or voters sharing a finite set of preference templates, is a plausible story for repeated types. It does not remove that objection: under the proposed utilitarian objective, changing the population while keeping \(G_\mu\) fixed cannot change the optimization problem. A more population-sensitive allocation model could track how mass of each type receives different integral bundles, with supplies scaled to population size. But that changes the feasible interpretation and introduces type-level allocation variables; Theorem 3.1 does not itself establish a result about that model. It may be worth studying, but it is a weaker mirror of this anchor.
The egalitarian mirror has a more direct continuum problem. In Theorem 3.5’s max-min objective, a type matters as soon as it has positive mass, however small. A cohort of mass \(10^{-12}\) can determine the value just as much as one with mass \(1/2\). As that cohort’s mass tends to zero, the finite-support objective can still change discontinuously when the mass reaches zero. In an atomless population, “least satisfied agent” therefore needs a convention: a pointwise minimum can be set by a measure-zero exception, while an essential infimum ignores it. The latter still counts every positive-mass type, however rare.
One could replace the minimum with a bottom-quantile or trimmed-welfare criterion to make prevalence matter. But that changes the fairness objective, so Theorem 3.5 no longer anchors the question. The faithful version keeps the theorem’s support-based fairness and inherits its discontinuity; the mass-sensitive repair asks a different question.
These are real reasons to doubt the value of the proposed mirrors, especially the egalitarian one. But I cannot honestly make them defeat every anchor. The utilitarian model is still a coherent high-multiplicity formulation: repeated complete utility types with rational masses define a sensible society, and the paper’s single-agent result applies to it. Flattening the objective shows that this mirror adds little new computational structure; it does not show that the continuous-population question is ill-posed or unrecognizable to the authors. The universal negative case is therefore weak at its central point.
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.