| paper | Learning to Design Fair and Private Voting Rules |
| authors | Farhad Mohsin, Ao Liu, Pin-Yu Chen, Francesca Rossi, Lirong Xia |
| venue | JAIR 2022 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The proposed distributional fairness problem is coherent and preserves the paper’s winner, utility, and imbalance semantics. However, Theorem 3 is analytic rather than computational, so the paper supplies no qualifying named computational anchor for a green mirror.
fails bit a — no named computational result to mirror
Theorem 3 is an analytic fairness bound, not a numbered computational result, so the LP formulation does not mirror computational work contained in the paper.
fatal: True
The proposed mirror covers the two-group positional-scoring fairness analysis around Theorem 3, with Theorem 2 as calibration; it leaves the ML rule-design procedures, privacy mechanism, empirical trade-offs, and other analytic theorems aside.
The strongest honest positive case is a single Class-A mirror of the paper’s worst-case fairness analysis, anchored on Theorem 3. There is an important limitation: the paper contains no named theorem asserting NP-hardness, membership in P, parameterized hardness, or a comparable computational classification. Thus this cannot honestly be presented as a hardness-dissolution result. It is a computational continuization of a named finite-population theorem.
Take \(m\) alternatives and let \(L\) be the \(m!\) complete rankings. A type is \((g,R)\), where \(g\in\{1,2\}\) is the protected group and \(R\in L\) is the ranking. The group label belongs in the type because the paper’s fairness measure uses it. In the intended regime, each group contains a very large number of voters but only a small number of recurring ranking types: for fixed \(m\), perhaps \(n\gg 2m!\). A plausible setting is a national or large organizational election with a fixed candidate set and two protected cohorts whose members repeatedly exhibit the same ballots. The point is not that every election has this form, but that this is a sensible high-multiplicity regime for the paper’s exact mathematical problem.
Let group \(1\) have mass \(\lambda\ge \tfrac12\) and group \(2\) mass \(1-\lambda\), with distributions \(\mu_1,\mu_2\) over \(L\). The aggregate society is \(\mu=\lambda\mu_1+(1-\lambda)\mu_2\). For score vector \(s\), the winner is the positional-scoring winner of \(\mu\). For utility vector \(u\), define \(U_g(a)=\sum_{R\in L}\mu_g(R)u_{\operatorname{rank}_R(a)}\), and \(U(a)=\lambda U_1(a)+(1-\lambda)U_2(a)\). The imbalance is \(\operatorname{Imb}(u,a)=|U_1(a)-U_2(a)|/U(a)\) when \(U(a)>0\), and \(0\) otherwise.
The continuous problem is:
\(\textsc{Continuous Worst-Case Fairness Evaluation}\): given \(m\), rational \(\lambda\), score vector \(s\), utility vector \(u\), and a threshold \(\eta\), decide whether there exist distributions \(\mu_1,\mu_2\) such that the scoring-rule winner \(a\) has \(\operatorname{Imb}(u,a)\ge\eta\). Equivalently, compute the supremum \(\Phi_\infty\) of this imbalance over all continuous societies and return \(F_\infty=1-(1-\lambda)\Phi_\infty\). This is exactly the paper’s \(F(r,u,n,z)\) with counts replaced by masses, since \(z=\lambda/(1-\lambda)\).
My lead anchor is Theorem 3, “Fairness for Positional Scoring Rules,” proved in this paper. It states that, for any utility vector \(u\), population size \(n\), group-size ratio \(z\), and positional scoring rule with score vector \(\langle s_1,\ldots,s_m\rangle\), the paper’s fairness value satisfies the following upper bound. Writing \(s_{[k:m]}\) and \(u_{[k:m]}\) for the averages of the entries from positions \(k\) through \(m\), the bound is \(1-\frac{u_1-u_m}{zu_1+u_m}\) outside the relevant score-ratio intervals, and within an interval \(z\in[\frac{s_1-s_m}{s_1-s_{[k+1:m]}},\frac{s_1-s_m}{s_1-s_{[k:m]}}]\), for \(k=m-1,\ldots,2\), it is the minimum of \(1-\frac{u_1-u_m}{zu_1+u_m}\) and \(1-\frac{u_1-u_{[k:m]}}{zu_{[k:m]}+u_1}\). The theorem is proved here, and the authors explicitly note that these are upper bounds and need not always be tight for finite \(n\).
This theorem is especially suitable for continuization because its proof already identifies the relevant phenomenon: as \(n\to\infty\), fractional mixtures of rankings can realize average score vectors that finite electorates cannot realize exactly. The continuous mirror makes those fractions the input object rather than an asymptotic proof device. It preserves the same winner rule, utility function, group imbalance, and worst-case quantifier.
I would expect \(\textsc{Continuous Worst-Case Fairness Evaluation}\) to be Class A. After fixing the possible winner \(a\) and the sign of \(U_1(a)-U_2(a)\), the problem is a linear-fractional optimization over the masses \(\mu_g(R)\). A Charnes–Cooper transformation turns it into an LP. The LP has exponentially many ranking variables, but its pricing problem is a weighted assignment problem: a ranking \(R\) receives a linear weight determined by the score and utility assigned to each alternative at each position. That pricing problem is polynomial-time solvable. Thus column generation or separation-based LP machinery should give an algorithm polynomial in \(m\) and the input bit length, despite the \(m!\) implicit types.
The paper’s Theorem 2 provides a useful calibration of this mirror, although I would not count it as a separate anchor: for rank utility \(u_{\mathrm{rank}}=\langle m-1,\ldots,0\rangle\), it proves \(F(r_{\mathrm{Plu}},u_{\mathrm{rank}},n,z)=0\) and \(F(r_{\mathrm{Bor}},u_{\mathrm{rank}},n,z)=1-\frac1z\). The continuous problem should recover exactly these values after replacing \(z\) by \(\lambda/(1-\lambda)\). Further questions include when Theorem 3’s upper bound becomes exact in the continuum, how the finite value converges to \(F_\infty\), and whether the same LP machinery handles the paper’s multi-group fairness definitions.
The weakest point is decisive: this paper does not itself study a computational problem in the complexity-theoretic sense. The proposed mirror asks us to computationalize a worst-case fairness quantity that the paper treats analytically and experimentally. An opposing reader can therefore say that the continuum is already latent in the proof of Theorem 3, or that this is a new optimization problem rather than the paper’s stated problem. The answer is that the paper never gives a continuous society as an instance, never formulates the mass-distribution optimization, and never studies its separation problem. So the mirror is defensible, but modest: it is a credible tractable population mirror of Theorem 3, not a hardness-based continuization case.
The negative case is stronger than a criticism of the proposed LP: the anchor fails the programme’s eligibility test. Theorem 3 is not a computational result. It gives an analytic worst-case upper bound for a scalar fairness measure; it does not define a decision, optimization, approximation, or complexity problem. The paper contains no theorem establishing membership in \( \mathrm{P} \), hardness, parameterized complexity, or an algorithmic guarantee for the relevant voting problem. The ML procedures are constructions, not complexity results, and Theorem 7 is a concentration bound. Thus \( \textsc{Continuous Worst-Case Fairness Evaluation} \) would be a new problem inspired by Theorem 3, not a continuization of a named computational contribution.
Even granting that relaxed standard, the proposed mirror has very little genuine continuous-computational content. For each group \(g\), define
\[ X^g_{ij}=\Pr[\text{alternative }a_i\text{ is ranked at position }j]. \]
Every \(X^g\) is doubly stochastic, and every doubly stochastic matrix is a convex combination of ranking matrices. Hence distributions over the \(m!\) rankings can be replaced exactly by \(m\times m\) assignment marginals. The group’s scoring vector and utility vector are simply
\[ S^g_i=\sum_j s_jX^g_{ij}, \qquad U^g_i=\sum_j u_jX^g_{ij}. \]
The winner constraints and the imbalance of a fixed candidate depend only on these quantities. After fixing the candidate and the sign of \(U^1_i-U^2_i\), the fractional objective can indeed be linearized, but the resulting problem is already a polynomial-size LP over two Birkhoff polytopes. There is no \(m!\)-variable pricing problem whose tractability reveals anything about continuous populations. This is precisely the normalized version of the paper’s own positional score matrix in Definition 6.
The paper has already performed the only limiting step that matters here. Claim 1 in the proof of Theorem 3 observes that, as \(n\) grows, fractional mixtures can approximate arbitrary feasible average score vectors. Replacing finite profiles by \( \mu_g \) therefore removes only the lattice effects that the proof itself treats as asymptotically irrelevant. Computing the exact optimum of the resulting convexified problem might tighten Theorem 3’s non-tight bounds, but that would be a refinement of an analytic theorem, not a new computational landscape produced by continuization.
The strongest repairs do not help much. Giving a continuous society as input makes winner and fairness evaluation a direct calculation from the score matrix. Optimizing over all societies gives the Birkhoff LP above; adding more protected groups merely adds more copies. Heterogeneous utility vectors would create a new type model rather than mirror this paper’s common rank-based utility assumption. Local differential privacy is no better: its guarantee concerns changing one individual vote, whereas an atomless population gives an individual measure zero, so preserving the paper’s privacy question requires a new cohort-level adjacency notion. Treating Plackett–Luce or uniform sampling as the continuous object instead makes distributions a noise or data-generating model, not the society itself.
A high-multiplicity election with repeated ballots and protected cohorts is perfectly sensible; that is not the objection. The objection is that this particular paper supplies no qualifying computational result, while its strongest possible mirror collapses immediately to the finite-dimensional summary representation already used in the paper. If the programme allowed new optimization problems motivated by axiomatic results, an exact continuum tightness or convergence study could be a modest project. Under the stated computational-anchor standard, however, there is no worthwhile ChoCo mirror 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.