| paper | d4-conf-ijcai-2020-0421 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: polynomial-time solvable · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given \(m\) binary issues and a distribution \(\mu\) over \(\tau\) complete conditional approval ballot types, with rational masses summing to \(1\), suppose each supported type has maximum dependency in-degree at most \(1\) and the undirected union of their dependency graphs has treewidth at most \(2\). Find an assignment \(s\in\{0,1\}^m\) minimizing \(\sum_t \mu_t\delta_t(s)\), where \(\delta_t(s)\) is the number of issues on which type \(t\) is dissatisfied.
Types are complete conditional approval ballots, including each ballot's dependency graph and approvals; each type carries rational mass \(\mu_t\). The decision variable is the common Boolean assignment \(s\), and the objective is the per-capita dissatisfaction \(\sum_t\mu_t\delta_t(s)\).
The mirror covers the exact treewidth-two result in Theorem 3 and the bounded-in-degree approximation questions in Theorems 1 and 2; it leaves larger global treewidth and other voting rules aside.
The best mirror is Conditional Minisum over a continuous population of conditional approval ballot types. A type \(t\) is a complete ballot: its dependency graph and all the conditional approvals the voter gives. A society is a finite support of \(\tau\) such types with binary rational masses \(\mu_t\), summing to \(1\). The decision remains the paper’s common Boolean outcome \(s\in\{0,1\}^m\); its cost is the per-capita dissatisfaction
\[
D_\mu(s)=\sum_t\mu_t\delta_t(s).
\]
The question is to find an outcome minimizing \(D_\mu(s)\), or, for an approximation version, to return an outcome within the requested factor of optimum.
A plausible regime is a large municipal referendum on a portfolio of linked projects. Many residents cast one of a relatively small number of recurring conditional approval ballots—for instance, ballots associated with recurring stakeholder groups—so the population is large while \(\tau\) is modest. Each voter’s type includes their full ballot, as the programme requires. The common decision stays binary; only the population is continuous. This is a direct high-multiplicity version of the authors’ problem, and I would expect them to recognize it as such.
My lead anchor is Theorem 3, proved in this paper: if every voter’s dependency graph has maximum in-degree at most \(1\), and the undirected global dependency graph has treewidth at most \(2\), then CMS is optimally solvable in polynomial time. The matching mirror, CMS\(_\infty\)-TW2, has the same conditions on the supported types’ graphs and their union; it asks for an exactly optimal Boolean assignment minimizing \(D_\mu(s)\). I expect this to be tractable in \(\mathrm{poly}(m,\tau,L)\), where \(L\) is the mass encoding length. Each type’s dissatisfaction contribution for an issue depends only on that issue and at most one predecessor. Summing contributions by mass gives unary and pairwise costs on the global graph, so treewidth-two dynamic programming optimizes the continuous objective directly. This provides an exact algorithm for the distributional input without expanding a mass into individual voters.
A broader, weaker anchor is Theorem 1, proved in this paper: with maximum in-degree at most \(1\) for every voter, an \(\alpha\)-approximation for MIN 2-SAT yields a \(2\alpha\)-approximation for CMS; in particular, the authors obtain a polynomial-time \(2.2074\)-approximation. Its mirror, CMS\(_\infty\)-Indeg1-Approx, allows an arbitrary global dependency graph and asks for an outcome \(s\) with \(D_\mu(s)\le 2.2074\min_{s'}D_\mu(s')\). I expect a constant-factor algorithm, hence a likely Class A result. The paper’s reduction suggests the route: build clauses from each type’s local dissatisfaction patterns, weighted by \(\mu_t\). But Theorem 1 does not establish the same guarantee for binary-rational weights; obtaining an appropriate weighted MIN 2-SAT approximation is part of this continuous question, not something I would claim the paper has already solved.
The scope here is Conditional Minisum. It covers the paper’s exact low-treewidth result and its bounded-in-degree approximation question; it does not try to continuize the outcome space, replace CMS with another rule, or settle the paper’s open questions about larger treewidth. The paper discusses CMS hardness and attributes it to Barrot and Lang (2016), but the supplied paper has no numbered hardness theorem to use as an anchor. Its cited hardness is useful context, not a result I would mislabel as one of this paper’s numbered anchors. A natural follow-up is whether hardness persists for arbitrary global graphs when the continuous society has small support \(\tau\).
The weakest point is the regime assumption: residents must fall into a modest number of genuinely identical complete ballots, and the strongest exact result also needs a treewidth-two dependency graph. Those are meaningful restrictions, not guarantees about every referendum. Still, the mirror preserves the underlying decision problem and gives the authors a concrete continuous-population question, with a credible exact algorithm in the structural case they already study.
The strongest case against a mirror is that CMS is already additive over voters. Once voters with the same complete conditional ballot are grouped, the continuous objective is just a weighted Boolean optimization problem. The outcome space remains finite, and the continuous input changes the weights, not what a voter’s dissatisfaction means. That may make the mirror feel more like a compact encoding of CMS than a new model of collective choice.
But that concern does not defeat either anchor. For Theorem 3, each ballot contributes unary and pairwise costs, and replacing voter counts with rational masses leaves the treewidth-two dynamic program intact. The stronger version of the proposed mirror therefore has a direct exact algorithm in \(\mathrm{poly}(m,\tau,L)\). For Theorem 1, its reduction produces a weighted MIN 2-SAT instance: clauses from a type can carry that type’s mass. The unweighted approximation guarantee does not by itself prove the weighted result, but that is a concrete algorithmic question, not a fundamental obstacle.
The proposed municipal scenario is also credible: many residents could share a small set of complete conditional ballots over linked projects. Their identities do not matter to CMS, and each ballot type can include all preferences and dependencies the problem uses. Neither the finite outcome space nor the fact that rational masses can be scaled to voter counts is a valid objection under the programme’s criteria.
So my negative case is weak. The mirror may yield limited conceptual novelty because it looks like weighted CMS with compressed input, but that is precisely the high-multiplicity question the programme is meant to study. I cannot honestly defeat the treewidth-two anchor; on the evidence here, the paper should be green.
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.