| paper | d4-conf-ijcai-2016-0043 |
| 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: Randomized polynomial-time additive estimation, with \(O(m^4\varepsilon^{-2}(1+\log(1/\delta)))\) samples. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 5.1
statement extracted from the paper’s text layer
Given \(m\) candidates, \(z\) equal-mass districts, fixed tie-breaking, and a polynomial-time sampler \(M\) that outputs rational mass vectors \(\mu\) over types \((d,\pi)\) with total mass \(1/z\) in each district, estimate \(\mathbb{E}_{\mu\sim M}[\mathrm{MR}_\infty(\mu)]\) within additive error \(\varepsilon\) with probability at least \(1-\delta\). For plurality, \(\mathrm{MR}_\infty(\mu)\le m^2\), so Hoeffding sampling uses at most \(\left\lceil (m^2-1)^2\ln(2/\delta)/(2\varepsilon^2)\right\rceil\) samples; each sample’s ratio is computable from its supported types.
A society is a rational mass distribution over district-ranking types \((d,\pi)\), with mass \(1/z\) in every district; uncertainty is a sampler over such societies. The decision task is to output an additive \((\varepsilon,\delta)\)-approximation to expected plurality misrepresentation, with runtime polynomial in \(m,z,\tau,L,1/\varepsilon,\log(1/\delta)\).
The mirror covers Theorem 5.1’s expected-misrepresentation approximation task when each sample is a continuous district composition. It leaves the worst-case bounds in Section 4, the Copeland analysis, and the simulation results outside the mirror.
The strongest mirror is the paper’s expected-misrepresentation problem, with uncertainty placed over population compositions rather than over individual ballots.
Consider a large, equal-population district election with \(z\) districts and a modest number \(m\) of candidates. A type is \((d,\pi)\): a district \(d\) and a complete ranking \(\pi\) of the candidates. The district belongs in the type because it determines which local election the voter affects. A society is a rational mass vector \(\mu\) over these types, with total mass \(1/z\) in each district and total mass \(1\). In a regime with millions of residents and relatively few distinct rankings per district, the support size \(\tau\) can be far smaller than the number of people.
This retains the paper’s two-stage institution. For a scoring rule \(f\), let \(S_{d,\mu}(c)\) be candidate \(c\)’s score within district \(d\), normalized by that district’s mass, and let \(S_\mu(c)\) be the candidate’s score over the whole society. The district winner is \(\arg\max_c S_{d,\mu}(c)\); the overall winner \(w(\mu)\) is the candidate winning the most districts, with fixed tie-breaking at both stages. Define
\[
\mathrm{MR}_\infty(\mu)
=\frac{\max_{c\in C} S_\mu(c)}{S_\mu(w(\mu))}.
\]
For plurality, this ratio is at most \(m^2\): the overall winner takes at least a \(1/m\) fraction of the districts, and in each district they win they have at least a \(1/m\) share of first-place votes. Their national share is therefore at least \(1/m^2\).
The anchor is Theorem 5.1, proved in this paper. It says that, given a generative model \(M\) that samples finite election outcomes, a known bound \(H\) on the misrepresentation ratio, and polynomial-time winner determination, Expected-MR returns an estimate \(\hat r\) of \(r=\mathbb{E}_M[\mathrm{MR}]\) satisfying \(\Pr[|\hat r-r|\le\varepsilon]\ge1-\delta\). The paper’s algorithm uses
\[
s=\left\lceil\frac{(H-1)^2\ln(2/\delta)}{2\varepsilon^2}\right\rceil
\]
independent samples; its guarantee follows from Hoeffding’s inequality. This is an additive randomized approximation result, not a hardness result. The paper gives no comparable named hardness anchor for this case.
Continuous Expected-MR Approximation is the corresponding prover-ready problem. An instance consists of \(C\), \(z\), plurality with fixed tie-breaking, and a polynomial-time sampler \(M\) that outputs rational mass vectors \(\mu\) over \((d,\pi)\), with each district’s mass fixed at \(1/z\). Each sampled vector has polynomial bit length. Given \(\varepsilon>0\) and \(\delta>0\), output \(\hat r\) such that
\[
\Pr\!\left[\left|\hat r-\mathbb{E}_{\mu\sim M}
[\mathrm{MR}_\infty(\mu)]\right|\le\varepsilon\right]\ge1-\delta.
\]
A solution is the randomized estimate. Here \(H=m^2\) suffices, so the sample count is at most
\[
\left\lceil\frac{(m^2-1)^2\ln(2/\delta)}{2\varepsilon^2}\right\rceil.
\]
Each sample’s ratio can be computed from its supported types, in time polynomial in \(m,z,\tau\), and the input bit length. Thus this mirror should be tractable by the paper’s sampling argument. The practical scenario is uncertainty over plausible district compositions—for example, draws from a model of district-level population shares—rather than independent ballot noise for a fixed finite list of people. Its randomness is over societies \(\mu\); the society in each draw is itself the continuous object.
This is a narrow mirror of Theorem 5.1 and its expected-MR task. It does not claim to continuize the paper’s worst-case bounds, nor does it turn the paper into a hardness result. It is plausible as the continuous analogue because the statistic, district rule, and question—how much expected misrepresentation arises under a generative model—are preserved. The paper already makes expected MR under generated elections a computational question; the continuous version replaces each generated profile with a generated distribution over voter types.
The soft spot is that Theorem 5.1 samples finite profiles, while this mirror samples mass vectors. If the authors intend only independent individual ballot noise, then the limiting mass vector may be deterministic, or the expected value may behave differently near ties. The mirror is strongest when the model represents persistent uncertainty about district composition, not merely sampling noise that vanishes as the electorate grows. In exchange, it keeps the paper’s central institutional question intact and puts it in a genuine high-multiplicity regime.
The only credible case against this mirror is that it may have little research yield. Theorem 5.1’s Hoeffding argument carries over almost unchanged: sample a rational mass vector, compute its misrepresentation ratio from the supported types, and average. The proposed version adds no new bottleneck or optimization machinery, and its value depends on having a credible model for uncertainty over district compositions.
That objection is too weak to defeat the anchor under the programme’s standard. A low-yield or quickly solved question can still be a worthwhile mirror. Nor is the mass-vector model merely outcome noise: uncertainty over district compositions makes the society itself the random continuous object. A type \((d,\pi)\) is a complete description for this problem, and large districts with many residents sharing a finite set of rankings are a sensible high-multiplicity regime. The misrepresentation ratio remains defined and nontrivial there; for plurality, the proposed bound \(m^2\) prevents degeneration. There is no identity dependence to obstruct aggregation.
A more convincing version could place a posterior over district-level population shares, perhaps informed by surveys, and ask for expected or robust misrepresentation under that uncertainty. That makes the uncertainty model more concrete while retaining the continuous society. The paper’s sampler-based theorem does not itself study such population distributions, so it is not a continuous-population collision.
I therefore cannot make a strong case that this anchor fails. The negative argument supports a caution about novelty and application, but the paper provides a named computational result, and the continuous-population version remains well-posed and plausible. The anchor survives.
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.