| paper | d4-conf-atal-2021-0227 |
| 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: \(\Sigma_2^p\)-complete, and hence \(\mathrm{NP}\)-hard · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5.9
statement extracted from the paper’s text layer
Given a finite agenda \(\Phi\), a target formula \(\phi^\star\), and a rational distribution \(\mu\) over complete, consistent judgment types \(t\), does there exist an order \(\pi\) of \(\Phi^+\) such that \(\phi^\star\) belongs to the sequential outcome? At each step, use logical entailment from earlier decisions when it determines the formula's value; otherwise select \(\phi\in\Phi^+\) when \(\mu(\phi)>1/2\), and select its complement when \(\mu(\phi)\le 1/2\), where \(\mu(\phi)=\sum_{t:\phi\in t}\mu_t\).
A society is a binary-rational distribution \(\mu\) over complete, consistent judgment types, represented by its positive-mass support of size \(\tau\). The decision is an agenda order \(\pi\); the outcome follows the paper's entailment rule and mass-based majority quota, and the question is whether the target formula is included.
After the mass-based majority judgment is computed, the masses disappear, leaving complexity driven mainly by agenda logic and offering little use for continuous-optimization tools; the proponent acknowledges this limitation.
fatal: False
The mirror covers quota-based agenda design for a single target formula and for a complete target judgment, anchored by Theorems 5.9 and 5.4. It leaves fixed-order winner determination, robustness, supported-judgment results, and other underlying rules unmirrored.
The strongest mirror is the paper’s majority-quota agenda-order design problem. It has a natural high-multiplicity setting: a large membership organization or public consultation decides a logically connected set of policy clauses. Members submit complete, internally consistent judgments; many may share the same judgment pattern. The agenda setter chooses which clauses become binding first, and earlier decisions can determine later ones by logical entailment. The order is the decision variable. There is no cost objective: the question is whether some order can produce a specified outcome.
Fix an agenda \(\Phi\) as in the paper, and let a type \(t\) be a complete, consistent judgment over \(\Phi\). The society is a rational distribution \(\mu\) over these types, given by its positive-mass support and binary rational masses; let \(\tau\) be the support size. For each formula \(\phi\), write \(\mu(\phi)=\sum_{t:\phi\in t}\mu_t\). For majority quota, the underlying rule selects \(\phi\in\Phi^+\) when \(\mu(\phi)>1/2\), and selects its complement when \(\mu(\phi)\le 1/2\). Thus ties go to \(\Phi^-\), matching the paper’s quota convention. The sequential rule processes an order \(\pi\) of \(\Phi^+\): it takes the logically entailed side if earlier decisions entail one, and otherwise takes the side selected by this mass-based majority rule.
My lead anchor is Theorem 5.9, proved in the paper. It states that, for every quota rule \(F_q\), the problem \(S_{F_q}\)-Winner-Design is \(\Sigma_2^p\)-complete when the desired set is a single formula \(J=\{\phi\}\). The paper proves hardness by reduction from Succinct Set Cover; it relies on Umans [23] for that source problem’s \(\Sigma_2^p\)-completeness.
The continuous question is Continuous Single-Formula Agenda Design: given \(\Phi\), a rational society \(\mu\) over complete consistent judgment types, and a target formula \(\phi^\star\), does there exist an order \(\pi\) of \(\Phi^+\) such that \(\phi^\star\) belongs to the resulting sequential judgment? A solution is a yes/no answer, with an order serving as a witness when the answer is yes. I expect this problem to remain \(\Sigma_2^p\)-complete for majority quota. The paper’s reduction uses two judges. Represent their judgments as two types of mass \(1/2\) each: every formula supported by one judge is exactly at the continuous majority tie, and the tie convention reproduces the finite rule. The reduction therefore survives with \(\tau\le2\). The upper-bound argument also carries over: the mass-based rule is computable from the support, and the paper’s sequential winner-design bound applies. The agenda’s logical structure supplies the hardness, so I expect this to be Class B: hardness transfers.
A second, independently useful anchor is Theorem 5.4, also proved in the paper. It states that for every quota rule \(F_q\), the \(S_{F_q}\)-Winner-Design problem is coNP-complete when the requested set \(J\) is a complete, consistent judgment. Its proof reduces SAT to agenda design. The corresponding continuous question is Continuous Complete-Outcome Agenda Design: given \(\Phi\), \(\mu\), and a complete, consistent target judgment \(J\), is there an order \(\pi\) for which the sequential outcome equals \(J\)? Since the output is itself complete, asking that it contain \(J\) is equivalent to asking for equality. A yes solution includes the realizing order.
For majority quota I again expect coNP-completeness: the theorem’s two-judge reduction maps to two types of mass \(1/2\), preserving the underlying quota judgment and hence the sequential outcomes for every order. The continuous upper bound follows from the paper’s coNP argument and efficient computation of majority over the support. This is another Class B result. It is a distinct target from Theorem 5.9: here the agenda setter must realize an entire coherent judgment, rather than secure one specified formula.
The authors should recognize both questions. The mirror keeps their problem’s defining ingredients—complete judgments, quota aggregation, logical entailment, and agenda-order manipulation—and changes the society input to proportions of judgment types. For majority quota, the bridge is exact: any rational \(\mu\) can be scaled to an even finite electorate with the same sequential outcomes, and finite profiles map back to rational distributions. The many-agent scenario is a large electorate or membership organization whose ballots cluster into a few complete judgment patterns; the paper’s reductions themselves need only two types.
These mirrors cover the paper’s quota-based agenda-design results, not every sequential rule or every winner-determination result in the paper. They also generate a useful parameter question: how much of the complexity survives with one type? With one type, every sequential decision agrees with that type, so the output is immediate; the paper’s reductions give hardness with at most two types. Further tractability questions could restrict the agenda’s logical structure, for example by bounding a structural measure of the formulas.
The weakest point is that these results offer no population-driven tractability gain. Their hardness already occurs with two types, and for majority quota the continuous input is exactly a normalized finite profile. That makes the mirror a faithful high-multiplicity formulation, but not a case where replacing the population by a continuum dissolves hardness. The large-organization scenario is also less typical of small expert committees; it depends on there being many members and a plausible concentration of their judgments into shared types.
The strongest case against prioritizing a continuous mirror is that the population carries little of the computational work in either result. Given a rational society \(\mu\), the quota rule computes a judgment \(F_{1/2}(\mu)\); the sequential procedure then works with that judgment, the agenda, and logical entailment. Once the majority judgment is known, the masses disappear. This paper offers no clear opening for the continuous optimization machinery that motivates ChoCo. Its mirrors look like compressed-input versions of agenda problems whose main structure is propositional logic.
That concern does not defeat Theorem 5.9. Its single-formula agenda-design problem has a sound continuous version. A large organization with many members sharing a small number of complete judgment types is plausible, and a society with two types of mass \(1/2\) reproduces the reduction’s two judges under the stated tie rule. Rational societies can also be scaled to finite profiles. The fact that hardness already holds with two types may limit prospects for a population-driven tractability gain, but that is a possible result of the mirror, not a reason the question is unworthwhile.
The same holds for Theorem 5.4. A large membership organization seeking a specified coherent collective judgment gives a plausible scenario for complete-outcome agenda design. Its two-type reduction also transfers to a society with masses \(1/2\) and \(1/2\), and the continuous majority rule preserves the sequential outcomes. The target is demanding, but realizing a full collective policy across connected propositions is recognizable as a real design objective.
The skeptical case is therefore about research yield: these mirrors may add little beyond an exact high-multiplicity encoding, and their complexity may remain driven by agenda logic. It cannot honestly establish that either mirror is invalid or already answered continuously. The paper contains named computational results; its rules are anonymous; large populations with repeated judgment types make sense; and no existing continuous computational treatment is supplied. Under ChoCo’s stated scope, even an exact correspondence or a result that hardness survives is a legitimate finding. I cannot make a strong case against these anchors without relying on objections the programme explicitly rules out.
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.