| paper | d4-conf-aaai-2004-0098 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: The decision problem is in \(\mathrm{P}\), and \(M\) can be computed exactly in polynomial time. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Corollary 1 (Consistency)
statement extracted from the paper’s text layer
Given Boolean variables \(V\), a finite support \(T\) of conditional preference theories \(\Gamma_t\) with rational masses \(\mu_t\) summing to \(1\), and acyclic \(G(\Gamma_t)\) for every type, compute \(M=\sum_{t:\,\Gamma_t\text{ is consistent}}\mu_t\), or decide whether \(M\ge q\) for a given rational threshold \(q\).
Each type is a complete conditional preference theory over common Boolean variables, and \(\mu_t\) is its population mass. Compute the total mass of consistent theories, or compare it with a threshold.
The typewise check adds no interaction or shared choice, so the population objective depends on an application-level audit policy; the proponent acknowledges the typewise nature but does not establish that this is a collective-choice task.
fatal: False
The mirror covers consistency checking under the acyclicity condition, using the paper's binary-domain checking bound; it leaves expressiveness, swapping-sequence entailment, optimal-outcome generation, and constrained optimization aside.
My strongest case is a population audit built around Corollary 1, “Consistency,” proved in this paper. It says that if \(G(\Gamma)\) is acyclic, then a conditional preference theory \(\Gamma\) is consistent exactly when it is locally consistent: for every complete assignment \(\alpha\) and variable \(X\), the transitive closure of the value comparisons validated by statements applicable at \(\alpha\) is irreflexive. The paper adds that, with binary variables, local consistency can be checked in time proportional to \(|\Gamma|^2|V|\). Together, these give a polynomial-time consistency check in that setting. The corollary gives a criterion rather than printing a complexity-class label; this is the paper’s clearest named tractability anchor. I know of no named hardness result in the paper itself.
Consider a large configuration-advice platform whose users state conditional preferences over the same Boolean attributes. Users who provide the same complete theory \(\Gamma\) are one type; \(\mu_t\) is that type’s fraction of users. A platform with millions of users may have only hundreds of distinct preference templates. That is a plausible high-multiplicity regime: the users of a type are indistinguishable for the audit, and the quantity of interest is a population share.
Call the mirror Continuous Consistent-Preference Mass. An instance consists of Boolean variables \(V\), a listed support of \(\tau\) types with positive rational masses \(\mu_t\) summing to \(1\), a theory \(\Gamma_t\) for each type, and a rational threshold \(q\). Assume each \(G(\Gamma_t)\) is acyclic. The question is whether
\[
\sum_{t:\,\Gamma_t\text{ is consistent}}\mu_t \ge q.
\]
A solution is the yes/no answer, with the exact consistent mass and its contributing types as a certificate. By Corollary 1 and the paper’s binary-domain checking bound, this is tractable: check each supported theory, then sum its rational mass. The expected classification is Class A.
The finite-population bridge is direct. If type \(t\) has \(n_t\) users among \(n\), set \(\mu_t=n_t/n\); the output is the fraction of users whose stated preferences admit a strict total-order model. The mirror covers consistency checking only. It does not extend the paper’s results on expressiveness, swapping-sequence entailment, or constrained optimization.
The weak point is that the theorem still does its computational work one type at a time; mass supplies a population-level audit, and the threshold makes the result useful for reporting, but population size does not change the consistency predicate. A referee could reasonably call this a high-multiplicity batch audit, with a thinner connection to the paper than a continuous intervention problem would have. Further questions include how the audit changes when \(G(\Gamma_t)\) may be cyclic, when variable domains are not binary, or when the type distribution is represented implicitly instead of by its support.
The proponent’s only anchor is Corollary 1, and it is real: combined with the binary-domain checking bound, it gives an efficient procedure for deciding whether one preference theory is consistent. I would not argue that the paper has no computational result to mirror, or that a continuous version must preserve the discrete answer.
The proposed question is well-defined too. Given types \((\Gamma_t,\mu_t)\), compute the mass \(\sum_t \mu_t\,\mathbf{1}[\Gamma_t\text{ is consistent}]\). Grouping people who submit the same theory is a legitimate high-multiplicity regime. But the population statistic is an extra audit wrapped around an individual-report check. Each \(\Gamma_t\) is a preference theory over assignments for one decision maker; Corollary 1 says nothing about choosing a shared assignment, comparing users’ preferences, or changing anyone’s report. The threshold \(q\) makes the audit easy to state, but does not supply that missing collective-choice problem. This could be useful for checking a preference platform, yet its value comes from the platform’s reporting policy, not from a population-level choice problem developed in the paper.
The stronger alternatives expose the same gap. One could ask for a shared configuration that is maximal for at least \(q\) mass of users, or aggregate users’ comparisons and ask whether the result is consistent. Those are more recognizably social-choice questions, especially if everyone has the same outcome space. But they require choosing a collective rule that the paper does not provide. Its results concern each theory’s consistency, maximal outcomes, and constrained optimization in isolation. They can help validate inputs or generate individual optima; they do not solve the population-level selection problem. Because the theories are ordinal and may be incomplete, there is also no canonical way to average them into a fractional preference theory. A majority rule over comparisons or a mass threshold over maximal outcomes is possible, but the substantive model comes from that new choice.
So the strongest negative case is about fit and payoff, not impossibility: the direct mirror is a weighted validity audit, while the more consequential mirrors need an independently chosen aggregation problem. That makes this paper a weak priority for the programme’s computational-social-choice agenda. I cannot honestly make the universal claim airtight, though. A shared-configuration platform with repeated preference templates is plausible, and an application that cares about population-level maximality could make the stronger question worthwhile. The case against those mirrors rests on their being new collective problems rather than continuizations of the paper’s results; it does not establish that no such problem could merit study.
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.