| paper | d4-conf-aaai-2010-0310 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→other discrete result → its continuous mirror
Answer: \(b(m,\tau,L)=\lfloor\log_2 N_{m,\tau,L}\rfloor\), where \(N_{m,\tau,L}\) is given by the explicit finite coefficient formula in Section 3. Uniformly computable compiler and decoder maps attain this exact length. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2 (Borda)
Fix \(m,\tau,L\). Each region has total mass \(1/2\) over at most \(\tau\) ranking types, with each type mass a binary rational of reduced numerator and denominator bit length at most \(L\). What is the minimum worst-case number \(b\) of bits for a compiler \(\sigma\) such that \(\sigma(\mu)=\sigma(\mu')\) implies that, for every allowed complementary distribution \(\nu\), the Borda winners of \(\mu+\nu\) and \(\mu'+\nu\) agree under the paper’s fixed tie-breaking order? Give a compiler and decoder attaining the minimum, or tight bounds on \(b\), with the maps computable from the rational input.
Ranking types carry rational population mass, with each of two regions contributing total mass \(1/2\). The compiler maps one region’s mass vector to a bit string; given that string and the other region’s distribution, a decoder returns the Borda winner. The objective is to minimize the worst-case summary length.
Bounded-precision rational masses can be cleared to integer vote counts, so the mirror may be a parameterized reformulation of finite-profile compilation; this limits novelty but does not invalidate the continuous question.
fatal: False
The mirror covers a bounded-support, bounded-precision, equal-size two-region version of Borda’s \(C_{m,k,u}\) compilation result. It leaves the other two compilation variants, unrestricted electorate sizes, and the paper’s other voting rules untouched.
The best positive mirror is Borda Mass Compilation. It takes the paper’s compilation question seriously: a summary must preserve enough information about one part of the population to determine the winner after any allowed complementary population is added.
The anchor is Theorem 2 (Borda). It states that \(C_{m,k,?}(\mathrm{Borda})=\Theta(m\log(km))\), \(C_{m,?,u}(\mathrm{Borda})=\Theta(m\log(um))\), and \(C_{m,k,u}(\mathrm{Borda})=\Theta(m\log(\min(km,um)))\). These are bounds on the minimum worst-case number of summary bits, not running-time classifications such as P or NP-hardness. The paper says the first bound was proved by Chevaleyre et al. (2009), with a fixable mistake in their lower-bound proof; the other cases are part of this paper’s study.
Here is a continuous-population version of the third case. Fix \(m\), a support bound \(\tau\), and a precision bound \(L\). Let \(\mathcal R_m\) be the rankings of the candidates, and let \(\mathcal D_{m,\tau,L}(1/2)\) be the distributions over at most \(\tau\) rankings that have total mass \(1/2\), with each mass a binary rational whose reduced numerator and denominator have at most \(L\) bits. A type is a complete ranking; its mass is the fraction of its region’s population holding that ranking.
The problem is to find the smallest \(b\) for which there is a compiler \(\sigma:\mathcal D_{m,\tau,L}(1/2)\to\{0,1\}^{\le b}\) with this property: whenever \(\sigma(\mu)=\sigma(\mu')\), then for every complementary distribution \(\nu\in\mathcal D_{m,\tau,L}(1/2)\), the Borda winners of \(\mu+\nu\) and \(\mu'+\nu\) are identical, using the paper’s fixed tie-breaking order. The decoder receives the summary and \(\nu\), and returns that winner. A solution is a compiler and decoder achieving the minimum worst-case summary length, or a tight bound on that minimum, with the maps computable from the rational input.
A plausible regime is a large electorate split across regions or reporting centres. Many people share each of a relatively small number of rankings, and one region must send a summary before the other region’s ballot distribution is available. The summary concerns population shares, not named voters. That is a natural high-multiplicity setting: the population can be enormous while \(\tau\) remains small.
This is a credible mirror because Borda’s score is linear in the mass of each ranking. The compiler can summarize aggregate Borda scores, just as the paper’s proof sketch does for vote counts, and the exact rational input makes finite summary lengths meaningful. I expect a finite-statistic compression result, with its tight bound depending on \(m,\tau,L\). That would mirror the underlying compilation problem without claiming that Theorem 2 already proves the continuous bound. Further questions include the tight dependence on support and precision, and whether approximate winner-preserving summaries become smaller when the final margin is bounded away from zero.
The soft spot is that Theorem 2 measures information required, not conventional algorithmic complexity, and the paper gives no named NP-hardness or P result to carry across. Also, an exact summary over unrestricted real masses would require unbounded precision; the precision bound is essential. I still think the mirror is worth asking: rational mass with explicit bit length is the programme’s stated input model, and the continuous question is whether the paper’s summary bounds persist when voters are represented by fractional type masses.
The strongest objection is that Theorem 2 measures how many bits a summary must contain, rather than the running time of an algorithm. Its Borda compiler stores score totals, and its bounds come from counting possible integer score vectors. That makes this a less direct fit for a programme centered on algorithms and computational complexity.
There is a real exactness problem if masses have unbounded precision. With three candidates \(A,B,C\), let \(\mu_x\) put mass \(x/2\) on \(A\succ B\succ C\) and \((1-x)/2\) on \(B\succ A\succ C\). Against a complementary distribution \(\nu_y\) of the same form, Borda elects \(A\) when \(x+y>1\) and \(B\) when \(x+y<1\). For any \(x<x'\), choosing \(y=1-(x+x')/2\) makes the winners differ. Thus every distinct \(x\) needs a distinct summary: there is no finite uniform bit bound for exact compilation over arbitrarily precise masses.
That objection does not defeat the proposed mirror, though. The proponent bounds the input precision by \(L\), as the programme’s input model permits. Then the domain is finite for fixed \(m,\tau,L\), and the question is well posed. Indeed, rational masses can be scaled to integer vote counts using a common denominator, making this a high-multiplicity version of the original setting. The new dependence on support and precision could still yield a worthwhile result; the paper’s worst-case bounds do not settle it.
The regional Borda scenario is also convincing: two large regions, each with repeated ranking types, must summarize their vote shares before learning the other region’s distribution. The summary concerns mass rather than voter identity, and the adversarial-complement requirement matches the paper’s question. Since compilation complexity is itself a legitimate computational-social-choice measure, I cannot honestly make a strong case that no worthwhile mirror exists. The negative case rests on precision sensitivity and the possibility that the result is mainly an arithmetic reformulation; the programme’s explicit treatment of \(L\) and high multiplicity makes that insufficient to dismiss the mirror.
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.