| paper | d4-conf-aaai-2014-0127 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Both rules are polynomial-time computable in \(m,\tau,L\). Every winner satisfies \(D_\mu(b)\le 2\mathrm{OPT}_\mu\), strictly when \(\mathrm{OPT}_\mu>0\). Every AVR winner also satisfies the sharp bound \(D_\mu(b)\le \frac{2(m-1)}m\mathrm{OPT}_\mu\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 9
statement extracted from the paper’s text layer
Given an integrity constraint \(IC\) and a finite support \(S\subseteq\operatorname{Mod}(IC)\) with positive binary-rational masses \(\mu_t\) summing to \(1\), compute an AVR or MVR winner \(b\in S\) and establish that \(D_\mu(b)\le 2\min_{x\in\operatorname{Mod}(IC)}D_\mu(x)\), strictly when the minimum is positive, where \(D_\mu(x)=\sum_{t\in S}\mu_t H(x,t)\). For fixed \(m\), establish the stronger AVR bound \(D_\mu(b)\le \frac{2(m-1)}{m}\min_{x\in\operatorname{Mod}(IC)}D_\mu(x)\).
Ballot types \(t\) carry population mass \(\mu_t\); the output is a supported ballot \(b\). The objective is expected Hamming disagreement \(D_\mu(b)\), compared with the minimum over feasible ballots.
Every rational-mass instance expands to a finite profile with exactly the same distances and winners, so the guarantee adds no new approximation behavior; this limits the novelty of the mirror, though the proponent acknowledges its histogram-like character.
fatal: False
Covers Theorem 9’s AVR and MVR guarantees and Theorem 11’s fixed-\(m\) AVR guarantee; it leaves the RVR bounds, rule comparisons, and reinforcement results aside.
The strongest mirror is a distribution over complete ballots on a fixed slate of binary issues. Imagine a large referendum or organizational poll in which many people answer the same set of questions, and many submit the same ballot. A type is a ballot \(t\in\{0,1\}^m\) satisfying the shared integrity constraint; its mass \(\mu_t\) is the fraction of the population with that ballot. The regime is one where the number of people \(N\) is much larger than the number \(\tau\) of distinct ballots with positive mass. That is plausible for a fixed agenda: with \(m\) issues there are at most \(2^m\) ballot types, however large \(N\) becomes. Since the rules in the paper use only ballots and their frequencies, two people with the same ballot are indistinguishable for this problem. The output remains an integral ballot selected from the population; it is the population that becomes continuous.
My lead anchor is Theorem 9, proved in this paper. It states that, for every integrity constraint \(IC\), both the average-voter rule (AVR) and the majority-voter rule (MVR) are strict \(2\)-approximations of the distance-based rule \(\mathrm{DBR}_{IC}\). Here “strict” means the distance guarantee is strict whenever the distance of the best \(\mathrm{DBR}_{IC}\) outcome is nonzero. The paper’s named results are approximation theorems rather than numbered hardness or exact complexity classifications, so this is its strongest broad anchor.
The corresponding continuous problem, Continuous Representative-Voter \(2\)-Approximation (CRV-2), is: given \(m\), an integrity constraint \(IC\), a finite support \(S\subseteq\operatorname{Mod}(IC)\), and positive binary-rational masses \(\mu_t\) summing to \(1\), return a ballot \(b\in S\) whose expected Hamming distance from the population is at most twice the best feasible distance. Write
\[
D_\mu(b)=\sum_{t\in S}\mu_t H(b,t),
\qquad
\mathrm{OPT}_\mu(IC)=\min_{x\in\operatorname{Mod}(IC)}D_\mu(x).
\]
The question is to return \(b\in S\) with \(D_\mu(b)\le 2\,\mathrm{OPT}_\mu(IC)\), strictly less when \(\mathrm{OPT}_\mu(IC)>0\).
The continuous AVR returns the supported ballots minimizing \(D_\mu\). For the continuous MVR, let \(p_j=\sum_{t:t_j=1}\mu_t\); define weak and strict majority ballots by setting coordinate \(j\) to \(1\) when \(p_j\ge \tfrac12\) and \(p_j>\tfrac12\), respectively. The MVR returns supported ballots closest to one of those two majority ballots. The mirror of Theorem 9 is that every winner of either rule satisfies the CRV-2 guarantee for every \(IC\). I expect this approximation-selection problem to be tractable: compute the \(p_j\), score each supported ballot, and select the minimizers. This takes \(O(m\tau)\) arithmetic operations and polynomial bit complexity in \(m,\tau,L\). The exact constrained optimum may still require searching a much larger feasible ballot space; the theorem gives a useful aggregation outcome without computing it.
A second, genuinely useful anchor is Theorem 11, also proved here. It states that when \(m\) is constant, the AVR is an \(\alpha\)-approximation of \(\mathrm{DBR}_{IC}\) for every integrity constraint, where \(\alpha=2(m-1)/m\). Its mirror is Fixed-Agenda Continuous AVR: with the same distribution input and fixed \(m\), return an AVR winner \(b\in S\) satisfying \(D_\mu(b)\le \frac{2(m-1)}{m}\mathrm{OPT}_\mu(IC)\). I expect this problem to be tractable for the same reason as CRV-2. The result is a sharper guarantee for a fixed issue agenda, not a claim that all continuous populations are easier to aggregate.
These mirrors are plausible because the paper itself defines the support of a profile, and its representative-voter rules depend on ballot frequencies rather than voter identities. A finite profile is an empirical distribution; the continuous input allows the same idea to be given directly as a compressed list of types and rational masses, without expanding a large electorate. The authors could recognize both questions as their problem: selecting a representative ballot that approximates minimum disagreement under integrity constraints. The paper’s results do not make the outcome space continuous, and this mirror does not need to. It continuizes the population.
The mirror covers Theorems 9 and 11 and their approximation guarantees, not the paper’s entire comparison of rules or its reinforcement axiom results. A further question is whether the exact continuous distance-based rule is hard for expressive integrity constraints. I would expect discrete hardness to transfer where the relevant finite problem is hard: an explicit finite profile maps to its empirical rational distribution. Other natural questions are whether structure in \(IC\) yields exact algorithms, or whether agenda-specific guarantees can be improved further.
The weakest point is that the continuous extension is mathematically close to a histogram restatement of the finite model: the paper already studies support and frequency-based rules, and its approximation arguments appear to extend directly to rational masses. So this is a credible high-multiplicity mirror, but not evidence by itself of a new complexity landscape. Its case rests on a natural compressed population model and a meaningful approximation question, not on a surprising separation between discrete and continuous complexity.
The strongest negative case is that both anchors are unusually close to the paper’s existing finite model. For any binary-rational distribution on ballot types, a common denominator \(q\) turns its masses into counts in a finite profile of \(q\) voters. The expected Hamming distances, majority outcomes, and representative ballots then agree exactly with those in that profile. The paper already defines profile support and proves its guarantees for every finite profile. So the proposed mirrors introduce no new ballot or aggregation structure; they ask whether the same rules can use a compressed histogram of the electorate.
That is a real limit on the novelty claim, but it does not defeat either anchor. The paper does not give the guarantees in the \((m,\tau,L)\) input model, and its voter-by-voter runtime bounds do not answer the compressed-input question. More importantly, the programme explicitly treats high multiplicity as a reason to study a continuous population, not as a collision. The histogram observation is therefore not enough to rule out a worthwhile mirror.
I cannot make a sound case that Theorem 9 fails as an anchor. Its continuous version is well posed: types are complete ballots, the output is a supported ballot, and weighted Hamming distance gives a meaningful per-capita objective. The AVR and MVR can be computed from the support and rational masses, and the approximation guarantee has a sensible mass-based form. Theorem 11 also survives: it sharpens the AVR guarantee when the agenda size is fixed. That is a valid, if narrower, mirror.
Other possible objections fail too. There is no identity-sensitive objective, and the limit does not erase the representatives: a supported ballot has positive mass. Calling the results “only approximation bounds” does not disqualify them under this programme, which explicitly includes approximation questions. Nor is there an existing continuous-population treatment in the paper; its statements are about finite voter profiles, even if their proofs extend naturally to weighted masses.
So the negative case is weak. The mirrors may offer little new mathematical structure, and the paper already points toward the right compressed representation. But the remaining question—how these guarantees and algorithms behave when the electorate is supplied as \(\tau\) weighted types rather than \(n\) listed voters—is exactly a high-multiplicity computational question. I cannot honestly argue that no scenario makes it worthwhile.
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.