d4-conf-ijcai-2020-0508

Theorem 2, item 1 is a rule-quality guarantee, and the other named results are also distortion statements; the simulations give no stated computational guarantee. The polarized continuous-population question is coherent, but it is not anchored in a named computational result, so bit (a) fails.

The objection that survived

Theorem 2, item 1 establishes a distortion bound, which the criteria explicitly exclude from computational results; asking for its supremum over societies is a global quality question, not a computational result of the paper.

What the mirror covers

The proposed mirror covers only Theorem 2, item 1's polarized \(k\)-Copeland guarantee; it does not cover the other rules, Theorem 1, or the simulations and weighted experiments.

Open questions for a prover

The case FOR (proponent)

There is a qualification: this paper has no named theorem classifying a problem as NP-hard, in P, FPT, or similar. The “hardness” in its Theorem 1 means infinite distortion, not computational hardness. So it has no anchor that meets the strict complexity-class requirement. The strongest named result for a positive mirror is Theorem 2, item 1, proved in this paper: for societies centered around two poles, the satisfaction-based distortion of \(k\)-Copeland is exactly \(1\). In other words, every committee returned by \(k\)-Copeland is utility-optimal in that domain.

A plausible high-multiplicity regime is a large civic organization choosing a representative board on a fixed agenda. Each member and candidate supports one of two coherent platforms; members share a stable fallback ordering when platform-aligned candidates tie. The population may be very large while the number of complete voter types is at most two. Candidates and the odd committee size \(k\) remain discrete.

Here is the mirror. Fix \(m\) candidates, \(p\) issues, odd \(k\), and two poles \(a,b\in\{0,1\}^p\), with every candidate assigned one of those two issue vectors. A voter type is a full type \(t=(x,\succ)\): \(x\in\{a,b\}\) records issue preferences, and \(\succ\) is a complete ranking consistent with the paper’s similarity rule and tie-breaking. The society is a finite-support distribution \(\mu\) over those types, with binary-rational masses summing to \(1\). Define \(U_\mu(W)=\sum_t\mu_t\sum_{j=1}^p\mathbf 1[W[j]=x_j]\), where \(W[j]\) is the committee’s majority decision on issue \(j\).

Call the problem Polarized Continuous \(k\)-Copeland Distortion: given the candidate and issue setup, compute the supremum, over such societies \(\mu\), of \(\max_{W\in k\text{-Copeland}(\mu)} U_\mu(\operatorname{OPT}(\mu))/U_\mu(W)\), using the paper’s \(0/0=1\) convention and including all tied rule outcomes. A solution is the exact supremum, with a proof; if it is not attained, a sequence approaching it suffices. Theorem 2, item 1 predicts the answer \(1\) for every setup in this family. The expected direction is tractable by structural insight: on polarized profiles, committees can produce only the two pole decision vectors, and weighted pairwise comparisons define \(k\)-Copeland over the finite candidate set.

This is a direct population mirror of the paper’s model: voters are distributed over their full relevant types, committee decisions and voter utility are unchanged, and only the population sum becomes an integral. For a rational \(\mu\), clearing denominators gives a finite election with \(n_t/n=\mu_t\); total utility is multiplied by \(n\), so the distortion ratio is unchanged. The paper’s model is finite, so this mirror is a high-multiplicity formulation of its question rather than a restatement of a model that already treats the population as continuous. The authors should recognize the issue as theirs: it asks whether their exact committee-quality guarantee survives when voter counts are represented as masses.

The mirror covers only the \(k\)-Copeland result in Theorem 2. It does not extend to the simulation section or claim results for the other rules. It also generates natural follow-ups: how the exact distortion changes with support size \(\tau\), and whether the bounds for SNTV, CC, Monroe, and the other rules have continuous counterparts as the smallest positive mass approaches zero.

The weak point is substantial: this anchor is a distortion theorem, not a complexity result about a hard computational problem, and the continuous question is likely to retain the discrete answer exactly. The case for a mirror is therefore that this is a sensible, precise high-multiplicity problem with a clean structural result—not that continuization is likely to dissolve a hardness barrier in this paper.

The case AGAINST (opponent, writing after the proponent)

The sole anchor is Theorem 2(1): \(k\)-Copeland has satisfaction-based distortion \(1\) on two-pole societies. That is a rule-quality guarantee, not a result about the complexity of computing a committee or carrying out an intervention. The paper’s other named results are also distortion statements; its simulations compare rule quality. Under ChoCo’s stated target—computational complexity and algorithms for problems on continuous societies—there is no computational result here to mirror.

The strongest version of the proposed mirror is a credible one: represent members by masses over complete types \((x,\succ)\), with finite candidates and an odd committee size, and ask whether the guarantee holds. I would not attack the civic-organization scenario or claim that mass is meaningless. But asking for the supremum distortion over all such societies supplies no society as input; it restates a global rule-quality claim. If instead the input is a particular \(\mu\), computing its \(k\)-Copeland winners and their utility is a different task. Extending the distortion analysis to support size \(\tau\) could be worthwhile research, but it adds a question the paper did not ask rather than continuizing one of its computational results.

For binary-rational masses, multiplying by a common denominator recovers a finite profile exactly. That makes the high-multiplicity formulation clean, but does not provide this anchor with a computational bottleneck for continuization to address.

So the negative case is strongest on fit with ChoCo’s computational brief, not on the modelling. The two-pole population is a sensible continuous object, and I cannot honestly rule out a worthwhile follow-up on its quality guarantees. I can argue that this paper offers no direct complexity mirror; I cannot make the universal claim that no continuous mirror is worthwhile in any scenario.

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.