| paper | d4-journals-jair-2013-0026 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 15
statement extracted from the paper’s text layer
Fix a finite atom set \(U\), choose CO or ASO semantics, and let each type \(\theta\) be a complete module \(P_\theta=(G_\theta,S_\theta)\). Given finite-support rational distributions \(\mu,\nu\) over types, form \(P_\mu=(\bigcup_{\mu_\theta>0}G_\theta,\bigcup_{\mu_\theta>0}S_\theta)\) and \(P_\nu\) analogously. Decide whether \(\operatorname{Opt}(P_\mu\cup(\emptyset,S_R))=\operatorname{Opt}(P_\nu\cup(\emptyset,S_R))\) for every ranked selector \(S_R\), where \(\operatorname{Opt}\) is the set of preferred outcomes under the chosen semantics.
Types are complete optimization modules \(\theta=(G_\theta,S_\theta)\); a mass distribution contributes each positive-mass module once by union, and the decision predicate is equality of preferred sets after every selector-only context.
Because \(P_\mu\) depends only on \uoperatorname{supp}(\mu), the case does not establish that frequency-blind module pooling is a persuasive model of large cohorts; its organizational scenario supports repeated types but not why their shares are irrelevant.
fatal: False
The mirror covers Theorem 15’s strong sel-equivalence complexity result alone; it leaves the other characterizations and complexity results untouched.
The strongest positive case is a direct extension of the paper’s own multi-agent interpretation: compare two large cohorts of agents whose modules specify feasible outcomes and qualitative preferences, and ask whether one cohort can replace the other without changing the preferred outcomes under any future preference input.
My anchor is Theorem 15, proved in this paper. It states that, given optimization problems \(P\) and \(Q\), deciding strong sel-equivalence \(P\equiv^s Q\) is coNP-complete for classical optimization problems (CO) and \(\Pi_2^P\)-complete for answer-set optimization problems (ASO). Here sel-equivalence quantifies over extensions that add selectors while leaving the generators fixed. The theorem’s lower bounds reduce from known hardness of equivalence for the corresponding generators; the ASO hardness is attributed to prior work, while this paper establishes the stated classification for strong sel-equivalence.
Here is the continuous problem I would hand to a prover: Continuous Cohort Interchangeability. Fix a finite set of atoms \(U\) and choose either CO or ASO semantics. A type \(\theta\) is a complete optimization module \((G_\theta,S_\theta)\): its generator and ranked selector describe everything about an agent that this problem uses. A society is a finite-support rational distribution \(\mu\) over such types, with \(\sum_\theta\mu_\theta=1\). Its aggregate module is
\[
P_\mu=\left(\bigcup_{\mu_\theta>0}G_\theta,\ \bigcup_{\mu_\theta>0}S_\theta\right).
\]
Given two societies \(\mu\) and \(\nu\), decide whether
\[
\forall R=(\emptyset,S_R),\qquad
\operatorname{Opt}(P_\mu\cup R)=\operatorname{Opt}(P_\nu\cup R),
\]
where \(\operatorname{Opt}\) is the set of preferred outcomes under the chosen semantics. A YES answer means the cohorts are interchangeable under every future selector extension. A NO answer can be witnessed by a selector context and a difference in preferred outcomes.
This is a faithful population mirror of the anchor: point-mass societies \(\delta_P,\delta_Q\) give exactly Theorem 15’s problem. Conversely, each finite-support society aggregates to an ordinary pair of optimization modules. The continuous question therefore has the theorem’s classification: coNP-complete for CO and \(\Pi_2^P\)-complete for ASO. I expect Class B for this mirror. Finite cohorts encode as rational frequencies \(n_\theta/n\), and rational measures can be cleared to integer counts. The anchor’s hardness is already present in the modules’ descriptions, so allowing cohort masses does not remove it.
A plausible regime is a large organization with many sites or departments governed by a modest collection of repeated policy modules. The agents share a type when they have the same feasible-outcome constraints and the same preference rules; then \(n\) can be very large while the number of types \(\tau\) stays moderate. This also fits the paper’s stated question of whether one agent in an ensemble can be replaced by another without changing optimal alternatives in future contexts. The outcomes remain ordinary interpretations; the population over modules is the continuous object.
The weak point is substantial: under the paper’s qualitative union semantics, \(\mu_\theta\) matters only through whether it is positive. Ten percent and ninety percent of a type contribute the same module, and repeating a selector rule does not give it more weight. This makes the cohort model exact and easy to relate to the paper, but the masses do not create a new mass-sensitive computational question. A frequency-weighted preference aggregator could make them matter, but it would change the paper’s semantics and would not be justified by Theorem 15. So I would present this as a credible, narrow population mirror of the paper’s interchangeability result—not as evidence that continuization makes this particular hardness tractable or dissolves it. It covers Theorem 15 alone; questions such as how complexity varies with \(\tau\), or whether a genuinely mass-sensitive variant has useful algorithms, remain open follow-ups.
Theorem 15 is a genuine computational anchor: it classifies strong sel-equivalence, so the negative case cannot rest on the paper having no named complexity result. The proponent’s point-mass construction is formally correct too. If a type is a complete module \(P_\theta=(G_\theta,S_\theta)\) and a society is aggregated by taking the union of its modules, a point mass recovers the theorem’s input.
That same construction exposes the main problem. Both parts of a module are combined by union, so duplicate modules have no effect. For every selector context \(R\), the preferred outcomes of \(P_\mu\cup R\) depend only on \(\operatorname{supp}(\mu)\), not on the masses. Any two societies with the same support behave identically whether their shares are \(1\%\) and \(99\%\) or \(50\%\) and \(50\%\). A large organization with repeated policy modules is plausible, but under this formalism its population size and proportions do no work. The continuum reduces to a choice of which modules appear.
The best repair is to give the mass a role in the output. For each context \(R\), one could record the mass of agents whose individual module has a particular optimal set:
\[
D_\mu^R(A)=\sum_{\theta:\operatorname{Opt}(P_\theta\cup R)=A}\mu_\theta.
\]
This is well-defined, sensitive to mass, and agrees with strong sel-equivalence on point masses. It is also the strongest challenge to a blanket negative verdict.
But it changes the target. The paper combines modules first and asks for the optimal outcomes of the resulting shared problem. \(D_\mu^R\) applies the context separately to each type and compares a distribution of individual responses. That could be a useful population study, but it does not say whether one cohort can replace another in the paper’s shared optimization problem. Making mass matter within that shared problem would require a new aggregation rule for qualitative preferences—weighted ranks, a majority relation, or something else. The paper supplies no natural weighting, and different choices can change the social ordering.
So the direct cohort mirror is weak: it preserves the theorem while discarding the very population quantities that make continuization matter. The broader distributional version is a credible adjacent question, but whether the authors would recognize it as a mirror of Theorem 15 is the negative case’s honest weak point. I would reject the proposed union-based mirror; I would not present the universal claim that no worthwhile reconstruction exists as airtight.
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.