| paper | d4-conf-atal-2008-0053 |
| 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 by a proper realizable PAC learner with all the stated bit-complexity bounds. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3.1
statement extracted from the paper’s text layer
For \(m\) candidates, let each society \(\mu\) be a rational distribution with support size at most \(\tau\) over complete rankings, encoded with at most \(L\) bits. Given \(m,\epsilon,\delta\) and i.i.d. labeled examples \((\mu^i,y_i)\) from an unknown distribution \(D\) over such societies, promised that all labels are winners under one unknown scoring vector \(\alpha^\star\), can an algorithm output a polynomial-size rational scoring vector \(\hat{\alpha}\) such that \(\Pr_{\mu\sim D}[f_{\hat{\alpha}}(\mu)\ne f_{\alpha^\star}(\mu)]\le\epsilon\) with probability at least \(1-\delta\), using sample size and running time polynomial in \(m,\tau,L,1/\epsilon,\log(1/\delta)\)? Define each candidate’s score by \(\sum_t\mu_t\alpha_{\operatorname{rank}_t(c)}\); resolve score ties by lexicographically comparing the mass ranking each candidate in first, second, and subsequent places, then use a fixed candidate order.
A learner observes labeled rational population distributions over ranking types and chooses a scoring vector \(\alpha\). Its objective is low prediction error on future societies drawn from \(D\); each prediction uses the mass-weighted scoring totals and the stated tie-break.
The mirror covers Theorem 3.1’s realizable PAC learnability result and its consistent-scoring-rule learner, with Lemma 3.6 supporting the dimension analysis. It leaves the paper’s approximation results in Section 4 outside the mirror.
The strongest honest mirror is the paper’s learning result, not a bribery or control result. Theorem 3.1, proved in this paper, says that for every \(n\) and \(m\), the class \(S^n_m\) of scoring rules on \(n\)-voter, \(m\)-candidate profiles is efficiently PAC-learnable: from i.i.d. labeled profiles whose labels come from a scoring rule in the class, a learner can output a scoring rule with error at most \(\epsilon\) under the unknown profile distribution, with probability at least \(1-\delta\). The paper proves this with a polynomial-time linear program for fitting the examples and the dimension bound in Lemma 3.6. I would use this as my single anchor. The manipulation hardness entries in Table 1 are cited from elsewhere, and Theorem 4.3 is an approximation impossibility result, not a computational-hardness theorem.
Here is the continuous problem I would hand to a prover: Continuous-Society PAC Learning of Scoring Rules. Fix \(m\) candidates, and let each type \(t\) be a complete ranking of them. A society is a distribution \(\mu\) over rankings, given by at most \(\tau\) positive rational masses, each encoded with at most \(L\) bits. For a scoring vector \(\alpha\), the score of candidate \(c\) is \(s_\mu(c)=\sum_t \mu_t\alpha_{\operatorname{rank}_t(c)}\). Break score ties by comparing, in order, the mass ranking \(c\) first, second, and so on, then by a fixed candidate order.
The learner receives \(m,\epsilon,\delta\) and labeled examples \((\mu^i,y_i)\), drawn i.i.d. from an unknown distribution \(D\) over such societies. The realizability promise is that every label is the winner under one unknown scoring rule \(\alpha^\star\). The question is whether a learner can output a polynomial-size rational scoring vector \(\hat\alpha\) such that
\[
\Pr_{\mu\sim D}\!\left[f_{\hat\alpha}(\mu)\ne f_{\alpha^\star}(\mu)\right]\le\epsilon
\]
with probability at least \(1-\delta\), using sample size and running time polynomial in \(m,\tau,L,1/\epsilon\), and \(\log(1/\delta)\). The action is the choice of scoring vector; the objective is low prediction error on future societies. The LP constraints compare the labeled winner’s weighted score with each competitor’s, accounting for the tie rule. The same dimension argument appears to extend because each comparison is linear in the \(m\) scoring parameters. I would therefore expect this mirror to be tractable, in the programme’s Class A sense. That is an expected extension, not a result proved by Theorem 3.1.
A plausible regime is a designer learning a decision rule from recurring civic or market populations: each queried population may contain millions of people, while its members fall into relatively few shared ranking types. Mass then means population share, rather than a count tied to a fixed electorate size. The paper’s scoring rules already depend on aggregate ranking frequencies, so replacing a voter tuple with its distribution is a natural extension of the object being learned. The input society itself is continuous in the relevant sense: its masses are fractions, and the model imposes no fixed voter-count granularity. The PAC distribution \(D\) describes which societies are queried; it is separate from the population distribution \(\mu\) within each society.
This mirror covers Theorem 3.1’s learnability result only. It does not extend the paper’s claims about manipulation, or claim that every black-box voting rule is learnable by scoring rules. The weakest point is that the paper’s black box labels finite profiles, while this mirror requires the designer’s rule to accept fractional societies. An author might regard that as a natural extension of their input representation rather than a new learning problem. The case survives because the query is still a society whose winner must be learned, and the extension removes the fixed-\(n\) granularity while preserving the scoring rule and the learning objective. A natural next question is whether an agnostic version can learn the best scoring approximation to an arbitrary target over a chosen distribution of continuous societies; the paper’s uniform-distribution result does not supply a canonical distribution over the simplex.
The strongest case against this anchor is that the proposed mirror appears to change the encoding more than the underlying learning problem. For any rational society \(\mu\), choose a common denominator \(q\) and form a finite profile with \(q\mu_t\) voters of each type \(t\). Its candidate scores are \(q\,\mathrm{sc}_\mu(c)\), so the winner is unchanged; the mass-based tie-break is also just the count-based tie-break scaled by \(q\). The paper’s learner already fits scoring vectors using linear inequalities over aggregate rank counts. On that view, continuous-society learning is the same realizable learning problem on normalized tally vectors.
That objection does not defeat the better mirror. The paper’s running time is polynomial in the explicit voter count \(n\), whereas a continuous society is given by binary rational masses and should be handled in time polynomial in their bit length. Expanding \(\mu\) into \(q\) voters could take exponentially many voters. But the paper’s LP can use the rational mass coefficients directly, and its dimension argument still applies over the full rational simplex. So the mirror has a clear computational formulation, even if the expected proof is close to the original one.
The other likely objections fail too: large elections with repeated rankings are a sensible high-multiplicity regime; the scoring rule depends only on ranking types, not voter identities; and normalized scores and mass tie-breaks remain meaningful in the continuum. The proposed PAC distribution over societies is an outer sampling distribution, while each query is itself a continuous society, so it does not replace population continuization with outcome or noise continuization.
I cannot honestly make the negative case hold. The concern that the result may be a short extension rather than a rich new complexity landscape is real, but it is not a sound reason to reject a well-posed mirror under the programme’s criteria. Theorem 3.1 survives: its continuous-society PAC version is a natural, tractable mirror, and the case against it is weak.
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.