| paper | d4-conf-ijcai-2015-0307 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Corollary 1
Given iid samples from an unknown two-candidate society \(\mu\) over ballot types, estimate the mass-transfer margin \(\rho_r(\mu)\), the infimum mass whose ballot types must change for the winner set under \(r\) to change, within additive error \(c\rho_r(\mu)+\epsilon\) with failure probability at most \(\delta\). Determine the minimum sample complexity for rules \(r\) that reduce to plurality on two candidates.
The types are the possible ballots over two candidates, and \(\mu\) assigns each type its population mass. An estimator observes iid type samples and outputs an estimate of \(\rho_r(\mu)\); the objective is to meet the stated error and failure bounds with as few samples as possible.
ChoCo's standard input is an explicit rational support list, while these bounds concern an estimator given iid samples from an unknown \(\mu\); the proponent states this restriction but does not connect it to the explicit-support optimization question.
fatal: False
The surviving mirrors cover the paper's sample-estimation results in Theorems 4 and 7 and its sample-complexity lower bounds in Theorem 2 and Corollary 1. They leave exact mass-transfer optimization from an explicit support list unaddressed.
The strongest mirror is Continuous Margin Estimation by Mass Transfer. A type is a complete ranking \(t\in L(C)\), and a society is a distribution \(\mu\) over rankings. To define its margin, choose transfers \(x_{t,t'}\ge 0\), with \(\sum_{t'\ne t}x_{t,t'}\le\mu_t\); these produce a new distribution \(\mu'\). The continuous margin \(\rho_r(\mu)\) is the infimum of \(\sum_{t\ne t'}x_{t,t'}\) over transfers for which the winner set under rule \(r\) changes. Thus the action is changing a fraction of voters’ rankings, and the objective is the fraction changed.
A plausible regime is a large public election with a relatively small candidate set and recurring ballot types: millions of voters, but far fewer distinct rankings. Voters of one type share the same ranking and the same unit cost of changing it; mass is their fraction of the electorate. This is especially natural in the paper’s polling and audit settings, where the pollster samples voters rather than inspecting every ballot. For the estimation questions below, the distribution is accessed through iid draws of rankings, as in the paper. An explicit support list with rational masses gives the underlying society; the estimator’s restricted access is part of the problem.
My lead is Continuous \(k\)-Approval Margin Estimation, anchored in Theorem 4, proved in this paper. The theorem states that for a finite \(k\)-approval election, a polynomial-time algorithm can estimate its margin of victory within additive error \(\epsilon n\), with probability at least \(1-\delta\), using \(12\epsilon^{-2}\ln(2k/\delta)\) sampled votes. The continuous problem is: given \(C\), \(k\), \(\epsilon,\delta\), and sample access to \(\mu\), estimate \(\rho_{k\text{-approval}}(\mu)\) to additive error \(\epsilon\) with probability at least \(1-\delta\). A solution is such an estimator, with its sample and running-time bounds.
This is a close analogue of the theorem’s underlying problem. In \(k\)-approval, the continuous margin is half the gap between the largest and second-largest approval masses: that much mass can be moved from ballots approving the leader but not the runner-up to ballots approving the runner-up but not the leader. The finite margin rounds this fractional quantity to whole voters, so the normalized values differ by at most \(1/n\). The theorem’s score-estimation argument therefore gives a direct route to the continuous estimator, with the same \(12\epsilon^{-2}\ln(2k/\delta)\) sample bound. I expect this oracle-estimation problem to be tractable. It also raises a separate question: when \(\mu\) is explicitly given by its support list, can its exact mass-transfer margin be computed in time polynomial in \(m,\tau,L\)?
Continuous Maximin Margin Estimation is a second mirror, anchored in Theorem 7, stated and proof-sketched in this paper. The theorem gives a polynomial-time \((1/3,\epsilon,\delta)\)-MOV algorithm for maximin using \(24\epsilon^{-2}\ln(2m/\delta)\) samples. Its continuous counterpart takes \(C\), sample access to \(\mu\), and \(\epsilon,\delta\), and returns \(\hat\rho\) with \(|\hat\rho-\rho_{\text{maximin}}(\mu)|\le \rho_{\text{maximin}}(\mu)/3+\epsilon\) with probability at least \(1-\delta\). Pairwise preference margins are expectations under \(\mu\), so the paper’s estimator has a natural distributional form. I expect this estimation question to be tractable at the stated sample scale. It leaves open the harder explicit-support question of whether the continuous mass-transfer margin itself admits an efficient exact algorithm. The paper reports that exact finite maximin margin computation is NP-hard, citing Xia (2012); that is useful context, but it is not a numbered hardness result proved in this paper.
The lower-bound side is anchored in Theorem 2 and Corollary 1, both proved in the paper (the corollary follows immediately from the theorem). Theorem 2 says that for two-candidate plurality, every \((c,\epsilon,\delta)\)-MOV estimator needs at least \(\frac{(1-c)^2}{36\epsilon^2}\ln\!\bigl(\frac{1}{8e\sqrt{\pi}\delta}\bigr)\) samples. Corollary 1 extends that bound to voting rules that reduce to plurality on two candidates, including scoring rules, approval, Bucklin, maximin, and Copeland\(_\alpha\). The continuous question is Continuous Plurality-Family Margin Estimation: given sample access to a two-candidate society (or one of those rules restricted to two candidates), estimate \(\rho_r(\mu)\) within \(c\rho_r(\mu)+\epsilon\) with failure probability at most \(\delta\). The paper’s two-distribution lower-bound argument is naturally read as a bound for distinguishing nearby distributions over rankings; I expect the continuous oracle problem to inherit the same \(\Omega((1-c)^2\epsilon^{-2}\ln(1/\delta))\) dependence. Together with Theorem 4 at \(k=1\), this predicts the right dependence on \(\epsilon\) and \(\delta\) for plurality. The further question is which rules and support structures attain matching constants or introduce additional dependence on \(m\) or \(\tau\).
The paper has no numbered exact-MoV hardness theorem of its own, so I have not promoted its cited Xia result into an anchor. These anchors instead cover the paper’s named contribution: sample-efficient margin estimation. The authors should recognize the mirror because their estimators already estimate normalized score and pairwise-margin quantities from random voters, and the finite electorate’s empirical type distribution is the direct bridge to \(\mu\).
The weak point is that the paper’s formal instance is a finite election, whereas the mirror makes fractional transfers legal. Ties make the distinction visible: an arbitrarily small transfer can change a continuous winner set, while a finite election must change at least one vote. For \(k\)-approval, the normalized discrepancy vanishes with \(n\); the paper does not establish the corresponding identity for every rule, or solve the exact explicit-support transfer problem. So this is a strong case for continuous mirrors of its estimation results, especially Theorem 4, rather than a claim that the paper already settles the continuous complexity of margin optimization.
The strongest case against is a mismatch in the input model. ChoCo’s central instance gives the society as an explicit support list with rational masses. The paper’s estimator instead gets samples and must infer a margin from an unseen electorate. If we keep ChoCo’s explicit input, there is no sampling uncertainty; if we keep the paper’s sample restriction, we have added an oracle model that the continuization does not require. That makes the proposed mirrors poor evidence for a new high-multiplicity complexity landscape.
For Theorem 4, though, the mirror is unusually strong. For \(k\)-approval, the continuous margin is half the gap between the largest and second-largest approval masses, assuming a unique winner. The normalized finite margin differs by at most \(O(1/n)\). With explicit support, the continuous margin follows directly from the approval totals; with sample access, the theorem’s estimator applies. But the formula’s simplicity cannot itself disqualify the mirror: ChoCo treats even a known or easy answer as worthwhile if the question is well posed. I cannot honestly defeat this anchor on its merits.
Theorem 7 has the same access-model problem, but a less immediate bridge. Its estimator samples pairwise preferences and estimates maximin scores; a continuous mass-transfer margin would ask how much mass must move to change the winner set. That is a meaningful target, and the score-based argument suggests a natural route to estimating it. The theorem does not establish the exact-support transfer problem, so treating its sampling algorithm as already solving that different problem would overstate the case against.
Theorem 2 and Corollary 1 make the input mismatch clearest. Their lower bound is about distinguishing nearby distributions from samples. With an explicit rational \(\mu\), that information-theoretic sampling obstacle is absent. But if sample access is accepted as part of the continuous problem, the lower-bound argument carries over naturally. So this anchor either falls outside ChoCo’s stated input model or survives under the proponent’s oracle model.
That is the honest limit of the negative case. It can argue that these are sample-oracle estimation questions, not the explicit-support continuous optimization questions at the center of ChoCo. It cannot establish that no worthwhile mirror exists in any scenario. The \(k\)-approval anchor in particular survives, and the maximin mirror is plausible. I would not support a categorical rejection on the evidence here.
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.