| paper | Learning to Design Fair and Private Voting Rules (Extended Abstract) |
| authors | Farhad Mohsin, Ao Liu, Pin-Yu Chen, Francesca Rossi, Lirong Xia |
| venue | IJCAI 2023 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
The opponent wins on the decisive eligibility test: Theorem 1 is a named fairness theorem, not a theorem about the complexity of a computational problem. The proposed \(\mathrm{WorstGroupFairness}_\infty\) is a direct, author-recognisable high-multiplicity reformulation and likely has a tractable LP, but it cannot supply the missing computational anchor. The privacy issue in Theorem 3 is secondary because bit \(a\) already fails.
fails bit a — no named computational result to mirror
The mirror covers Theorem 1's worst-case fairness analysis over the profile simplex; it leaves Theorem 2's exact \(u\)-fair values, Theorem 3's local-DP bound, and the untheoremized learning and rule-design procedures without qualifying computational anchors.
There is a natural continuous-population mirror here, but the paper fails ChoCo’s strict anchor requirement.
The paper’s named results are Theorem 1, proved here, showing that every positional-scoring or Condorcet rule can have worst-case group fairness \(0\); Theorem 2, proved here, giving exact fairness values for the \(u\)-fair rules; and Theorem 3, proved here, giving a probabilistic fairness–privacy–utility bound. None asserts that a problem is in \(P\), NP-hard, FPT, \(W[1]\)-hard, or otherwise gives a computational-complexity classification. The machine-learning and constrained-optimization frameworks are also not accompanied by a named runtime or hardness theorem. Thus there is no qualifying computational anchor in the supplied paper.
The strongest would-be mirror is nevertheless quite credible. Consider a large institution with two protected cohorts, each containing many voters drawn from a small catalogue of recurring complete rankings. A type is \((g,R)\), where \(g\in\{1,2\}\) is the protected group and \(R\in\mathcal L(A)\) is a complete ranking. The society is a rational mass vector \(\mu^g_R\), with \(\rho_g=\sum_R\mu^g_R\) and \(\rho_1+\rho_2=1\). The regime is \(N\gg\tau\), where \(N\) is the number of agents and \(\tau\) is the number of ranking types with positive mass. The type description includes everything used by the paper: group membership, ranking, and the common rank-based utility vector \(\mathbf u\).
My lead would-be problem is \(\textsc{WorstGroupFairness}_{\infty}\), mirroring Theorem 1.
Given candidates \(A\), a rational positional scoring vector \(\mathbf s\), a rational utility vector \(\mathbf u\), rational group masses \(\rho_1,\rho_2\), and a rational threshold \(q\), determine whether there is a society \(\mu\) whose winner under the scoring rule has group fairness at most \(q\). For a candidate \(a\), define \(W_g(a,\mu)=\rho_g^{-1}\sum_R\mu^g_Ru_{\operatorname{pos}_R(a)}\) and \(W(a,\mu)=\sum_g\rho_gW_g(a,\mu)\). With \(z=\max(\rho_1,\rho_2)/\min(\rho_1,\rho_2)\), the fairness of the winner \(a_\mu\) is \(F(\mu)=1-\frac{1}{1+z}\frac{|W_1(a_\mu,\mu)-W_2(a_\mu,\mu)|}{W(a_\mu,\mu)}\), with the paper’s convention \(F=1\) when the denominator is zero. The question is whether \(\min_\mu F(\mu)\le q\), and a solution is a rational witness \(\mu\) together with its winning candidate.
This is recognisably the paper’s question: it preserves the same winner, group-average utilities, imbalance measure, and worst-case fairness objective. It only replaces the finite profile by its type-frequency vector. Every rational \(\mu\) with denominator \(N\) expands to a finite profile of \(N\) cloned voters, and every finite profile maps back to such a \(\mu\).
For an explicitly represented type table, I would expect this problem to be Class A for positional scoring rules. Fixing the possible winner \(a\) gives linear score inequalities; splitting the absolute value into two cases gives a linear-fractional optimization problem, solvable in polynomial time in \(m\), \(\tau\), and the encoding length. The same style should work for fixed Condorcet rules using pairwise linear inequalities. That would be a new ChoCo result, however, not a result established by Theorem 1.
The authors should recognise this mirror because their own experiments already describe each group by a common preference distribution, including Plackett–Luce distributions. The proposed regime simply treats the realised type frequencies as the society rather than repeatedly sampling named voters. It also stays within population continuity: the candidates and voting outcome remain discrete; only the population becomes a distribution.
I would not lead with Theorem 3. Local differential privacy is problematic in a genuinely atomless model: changing one individual changes \(\mu\) by zero mass, so individual privacy becomes vacuous, while aggregate randomized-response frequencies become increasingly accurate as \(N\) grows. A faithful privacy mirror must retain a microscopic scale \(1/N\), or replace individual privacy by positive-mass cohort privacy. Either is defensible, but each adds a modelling convention absent from the paper.
The weakest point is that \(\textsc{WorstGroupFairness}_{\infty}\) may look like a computational formalisation of the paper’s definitions rather than a substantial new complexity problem. Its likely tractability comes from enumerating candidates and solving a small linear-fractional program, not from deep continuous-optimization structure. More importantly, under the programme’s literal rules, Theorem 1 cannot serve as the required anchor because it is a fairness theorem, not a named complexity result. So the honest conclusion is: the paper has a strong and author-recognisable continuous-population mirror for its fairness analysis, but no eligible computational result on which to base a formal positive ChoCo verdict.
The decisive objection is that this paper has no eligible computational anchor. Theorem 1, Theorem 2, and Theorem 3 are statements about fairness values and probabilistic trade-offs, not complexity results for an input-output problem. There is no numbered theorem asserting polynomial-time solvability, hardness, approximation, parameterized complexity, or even an algorithmic decision problem. A newly invented computational wrapper cannot repair that absence: it may be a worthwhile paper inspired by this one, but it is not a continuization of a computational result in the sense ChoCo is studying.
The proposed \(\textsc{WorstGroupFairness}_{\infty}\) does not overcome this. The paper’s fairness quantity is already anonymous within each group and depends on a profile only through type frequencies and aggregate utilities. For every finite profile, the vectors \(\mu_R^g\) are simply normalized vote counts; conversely, every rational such vector expands into a cloned finite profile. Thus the proposed continuous society is a legitimate representation, but Theorem 1’s maximization over profiles has merely been rewritten as an optimization over the profile simplex. It introduces no population intervention, transfer, robustness budget, or other computational object present in the paper.
One could try to improve the mirror by asking for the minimum mass of voters whose rankings must be changed to make a rule’s winner sufficiently unfair. That would be a reasonable new research problem, but it is not Theorem 1: the paper evaluates a fixed rule in the worst case, whereas the proposed problem adds a cost model, admissible transformations, and a target notion of “making” an outcome unfair. Those modelling choices are not recoverable from the theorem. The same construction could be applied to almost any anonymous voting rule, so it does not provide a paper-specific computational mirror.
Theorem 2 has the same problem. A continuous \(u\)-fair rule is easy to state and author-recognisable: replace group averages by integrals over \(\mu\), then select the candidate minimizing imbalance. But this is only the natural measure-theoretic notation for a rule whose sufficient statistics are already the group-average utilities. It does not turn the theorem into a population-computation result. Asking for the fair winner from a supplied distribution, or optimizing a scoring vector subject to the paper’s fairness constraint, would again be a newly specified rule-evaluation or rule-design problem, not a continuization of the stated result. The machine-learning framework does not help: it is an empirical training procedure, with no named computational theorem to transport and no canonical continuous input representation.
Theorem 3 supplies the strongest substantive obstruction. Local differential privacy is explicitly about changing one named agent’s vote while holding the other named votes fixed. An exact population measure forgets that distinction. In an atomless society, changing one individual leaves \(\mu\) unchanged, so individual privacy becomes vacuous; retaining randomized-response noise at the \(1/N\) scale requires retaining a finite microscopic population and therefore abandoning the genuinely continuous object. Defining privacy for a positive-mass cohort would avoid vacuity, but it would be a different privacy notion—group or cohort privacy—not the paper’s local differential privacy. Adding named agents or a stochastic microstate to recover the original notion defeats the proposed continuization rather than validating it.
The honest concession is that \((g,R)\)-type societies are semantically sensible for the paper’s fairness definitions. Large groups of voters sharing rankings are a plausible high-multiplicity regime. But that concession does not produce a ChoCo anchor: the paper’s central claims are axiomatic, statistical, and design-oriented, while the only genuinely individual-level computational issue, privacy, loses its meaning under population continuization. The best case against inclusion is therefore strong: this paper may motivate continuous fairness analysis, but it supplies no computational result whose continuous mirror ChoCo can study, and its privacy result contains an identity dependence that the continuous population model cannot preserve.
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.