In Which Empirical Risk Minimization Is Cast as a Voting Rule, Kemeny–Young Rankings Are Computed Through NP-hard Struggle, and the Bradley–Terry Model Is Invoked to Justify the Aggregation of Human Preference Ballots.
adversarial
AI safety
game theory
machine learning
mind
NLP
social choice
Figure 1
In what sense is training on the data we generate as a society similar to letting us vote on the behaviour of our models? It can be very similar, in many senses. Roberto-Rafael Maura-Riverso calls the field of AI research in this vicinity pluralistic AI:
When people disagree about what’s right, what should AI do? This is pluralistic AI alignment’s core challenge. Voting systems seem natural, but Arrow’s impossibility theorem crushed that hope: no perfect voting method exists.
Each training example \((x_i, y_i)\) acts as a ballot from an agent in the corpus. Gradient descent aggregates these ballots into a model. This is social choice in a somewhat trivial sense.
Each example contributes one term. Full-batch GD averages all gradient contributions; SGD samples a minibatch at each step. As such, it’s a strange estimator of the mean, effectively representing the trivial social-choice rule of utilitarian aggregation. Set voter \(i\)’s utility over decisions to \(u_i = -\ell(\theta; x_i, y_i)\); we’re done.
There’s nothing special about this under an ordinary loss function (e.g., L2), but we could design the loss function itself and think about it as solving for some interesting utilities. cf Differential Voting (An, Nakshbandi, and Du 2026), which constructs differentiable surrogates for non-trivial collective utilities under utilitarian aggregation; see also An and Du (2026).
1.1 ERM as maximum-likelihood voting
Forget utilities for one second. We have an alternative— we can treat voters as noisy oracles about a hidden ground truth \(f^*\) — as opposed to agents with private cardinal preferences, as is common in modern preference aggregation theory. Each ballot \(y_i\) is a noisy observation, and a voting rule is the maximum-likelihood estimator of the ground truth under some noise model.
This turns out to be how Condorcet analysed the majority rule back in 1785— each juror has a probability \(p > 1/2\) of being right. The majority vote extracts truth. This was revived formally in Young (1988) and developed in Conitzer and Sandholm (2005), which catalogues which classical voting rules are MLE under which noise models. The “noisy oracles about a hidden ground truth” idea connects us to the Bayesian-elicitation literature, and to the truth-from-strategic-agents problem.
Under this lens, “what voting rule does ERM implement?” is a well-posed statistical question.
L2 ↔︎ Gaussian-noise MLE ↔︎ sample mean. Assume voter \(i\)’s report is a noisy observation of the ground truth,
the empirical conditional distribution. Cross-entropy ERM is categorical MLE.
The bounded per-example gradient of CE drops out as a property of the categorical likelihood: \(\partial_{\mathrm{logit}} \log p_\theta(y \mid x)\) is bounded for any softmax, regardless of how skewed the empirical conditional is. No single sample can dominate the MLE the way an outlier can dominate Gaussian L2 — \(\Delta_K\) is compact, and the log-score is bounded by its geometry.
The general pattern. The framing extends past supervised learning:
Most of these seem relatively uninteresting to me, although the last one seems to have potential. The Kemeny–Young rule takes voters’ submitted rankings and outputs the consensus ranking \(\sigma^*\) that minimizes total pairwise disagreement with them — the sum of Kendall-tau distances \(\sum_i d_\text{KT}(\sigma_i, \sigma^*)\), where \(d_\text{KT}\) counts pairs of alternatives the two rankings order differently. Under the Mallows model — where voters’ rankings are noisy observations of a hidden true ranking, with each pairwise disagreement penalized by a concentration parameter \(\phi\), \(p(\sigma \mid \sigma^*) \propto \exp(-\phi\, d_\text{KT}(\sigma, \sigma^*))\) — Kemeny–Young is exactly the MLE (Young 1988). It’s the canonical Condorcet-consistent rule, and it’s NP-hard to compute in general.
2 Distortion and implicit utilitarian voting
A tradition that refuses to commit to either utility shapes or noise models. Implicit utilitarian voting(Boutilier et al. 2015; Procaccia, Shah, and Zick 2016; Caragiannis et al. 2017) assumes voters do have latent cardinal utilities but submit only ordinal ballots, and characterizes rules by how much welfare they lose against the utilitarian optimum in the worst case.
2.1 Setup
\(n\) voters, \(m\) alternatives. Voter \(i\) has a latent utility \(u_i : \{1, \dots, m\} \to \mathbb{R}_{\geq 0}\), normalized (commonly \(\sum_a u_i(a) = 1\) — unit-sum utilities). They submit only an ordinal ballot \(\sigma_i\) consistent with \(u_i\), i.e., the ranking induced by sorting \(u_i\) in decreasing order. A rule \(f\) maps the ballot profile \(\boldsymbol{\sigma} = (\sigma_1, \dots, \sigma_n)\) to an alternative \(f(\boldsymbol{\sigma})\), without ever seeing the utilities.
The social welfare of alternative \(a\) under utilities \(\boldsymbol{u}\) is
Distortion \(= 1\) means the rule recovers the utilitarian optimum from ordinal data alone; distortion \(= \infty\) means an adversarial profile can drive the rule’s welfare arbitrarily far from the optimum.
2.2 What’s known
Under unit-sum utilities, classical results in \(m\) (the number of alternatives):
Plurality is bad — distortion grows polynomially in \(m\).
For deterministic ordinal rules there’s a fundamental \(\Omega(\sqrt{m})\) lower bound: ordinal information alone is not enough to be welfare-competitive.
Randomised rules — where \(f\) outputs a distribution over winners and welfare is taken in expectation — can break the \(\sqrt{m}\) barrier.
Different normalisation choices (unit-range, additive, etc.) yield different bounds. The programme designs rules to minimize this worst-case quantity; see Boutilier et al. (2015) and follow-ups, and the RoboVote system.
2.3 For ERM-as-voting
CE-ERM produces a distribution rather than a single winner, so our natural framing uses the randomised version: voters have latent utilities over the \(K\) class labels, submit only their argmax label as a ballot, and CE-ERM produces the empirical histogram \(\hat p_\text{emp}\) which we sample from. The distortion is then
with the sup over utility profiles whose argmax-ballots reproduce the observed labels.
3 Social-choice-like dynamics in RLHF
Aggregating explicit human preference judgements (pairwise comparisons from annotators) to train a reward model is a kind of collective choice. RLHF is a “Borda count” vote (!) (Siththaranjan, Laidlaw, and Hadfield-Menell 2023), which performs poorly as a voting mechanism with respect to Condorcet.
Cf. “Nash learning from human feedback” (NashLHF), the “best” (democratically speaking) feedback system (Munos et al. 2024).
More info at Lanctot et al. (2025), Maura-Rivero, Lanctot, et al. (2025), Maura-Rivero, Nagpal, et al. (2025).
Maura-Rivero introduced me to Maximal Lotteries, the only (Brandl and Brandt 2020) stochastic lottery with certain nice properties that are desirable in an AI context (read the paper for details — I have forgotten but wow it seemed neat at the time).
The pitch for that:
Stochastic voting systems (maximal lotteries) sidestep these limitations. The question now: how do we make LLMs behave like this ideal system?
This body of work interprets preference annotation as “votes”. This opens the question of which aggregation rule (Borda-ish? Condorcet-ish? Maximal lottery?) we should use.
4 Differentiable social choice
A research programme that parametrizes voting rules, auctions, allocation mechanisms and incentive schemes as differentiable functions and fits those from data, subject to explicit structural constraints, rather than deriving them as closed-form objects from axiomatic desiderata.
By contrast, (An and Du 2026) proposes that we can find neural networks that have the desired properties. Axioms become a specification language for loss functions and architectures, and an audit vocabulary for interpreting learned systems. Anonymity implies permutation-equivariant architecture; feasibility/budget implies a differentiable solver layer; incentive compatibility becomes a regret penalty; Condorcet consistency becomes a smooth surrogate loss.
Classical mechanism design goes axioms → closed-form mechanism → guarantees and impossibilities — clean, universal, worst-case, with intrinsic limits set by Arrow, Gibbard–Satterthwaite, Myerson, and friends.
By contrast, differentiable social choice follows data + objectives → parameterised mechanism class → optimisation and learning → audit, verification, governance — empirically tuned mechanisms whose normative properties we test rather than prove.
The axioms don’t disappear; they relocate into architectural inductive biases, loss terms, and post-training audits. Classical impossibility results resurface as trade-offs in the loss-and-architecture design space.
4.1 Six domains
An and Du (2026) organize the area around six topics:
Differentiable economics — auction and contract design as deep nets (RegretNet, RochetNet); incentive compatibility relaxed into approximate regret bounds.
Neural social choice and voting rules — learn aggregation rules from data; mimic known rules, or synthesise new ones by optimising against axioms.
Participatory budgeting and complex allocation — proportional resource-allocation rules (e.g. Method of Equal Shares) with feasibility enforced as a solver layer.
Liquid democracy and decentralised aggregation — delegation graphs as differentiable trust networks; bridges to federated learning.
AI alignment as social choice — RLHF, DPO and friends as implicit aggregation mechanisms.
Inverse mechanism learning — observe strategic behaviour, infer the implicit rule that induced it; “differentiable forensics”.
4.2 Mimicry vs synthesis
A central tension in the neural voting-rule subfield: do we mimic a known rule by training a network to reproduce its outputs, or synthesise a new rule by optimising directly against axioms?
Mimicry is computationally useful — Kemeny–Young is NP-hard, and a fast forward pass that approximates it well is genuinely valuable. But the mimicry–reasoning gap(Hornischer and Terzopoulou 2025) is real: high accuracy on a typical preference distribution does not imply the learned rule satisfies the axioms that define the target. Outcomes can match while reasoning differs, and the gap shows up sharply under distribution shift or on adversarial profiles.
The synthesis route — optimising directly against axiom-derived loss terms — can produce novel rules occupying new regions of the axiom-tradeoff landscape, sometimes outperforming any named classical rule on the chosen axiom set. Loss-as-rule: pick the axiom mix, pay the resulting optimisation costs, ship a learned aggregation.
4.3 Distribution-specific social choice and bespoke democracy
Worst-case axiom analysis is conservative. Real preference profiles have structure — single-peakedness, Mallows noise, empirical correlations — and rules trained on a target electorate can have far lower violation rates than universal rules. This points to a “bespoke democracy” — rules tuned to a specific society — and raises new legitimacy questions about who chooses the training distribution, how robust the rule is to demographic change, and who gets to weight the axioms in the loss.
Munos, Valko, Calandriello, et al. 2024. “Nash Learning from Human Feedback.” In Proceedings of the 41st International Conference on Machine Learning. ICML’24.
1 Social-choice-like dynamics in ERM
Each training example \((x_i, y_i)\) acts as a ballot from an agent in the corpus. Gradient descent aggregates these ballots into a model. This is social choice in a somewhat trivial sense.
Empirical risk minimization is
\[\theta^* = \arg\min_\theta \frac{1}{N} \sum_i \ell(\theta; x_i, y_i).\]
Each example contributes one term. Full-batch GD averages all gradient contributions; SGD samples a minibatch at each step. As such, it’s a strange estimator of the mean, effectively representing the trivial social-choice rule of utilitarian aggregation. Set voter \(i\)’s utility over decisions to \(u_i = -\ell(\theta; x_i, y_i)\); we’re done.
There’s nothing special about this under an ordinary loss function (e.g., L2), but we could design the loss function itself and think about it as solving for some interesting utilities. cf Differential Voting (An, Nakshbandi, and Du 2026), which constructs differentiable surrogates for non-trivial collective utilities under utilitarian aggregation; see also An and Du (2026).
1.1 ERM as maximum-likelihood voting
Forget utilities for one second. We have an alternative— we can treat voters as noisy oracles about a hidden ground truth \(f^*\) — as opposed to agents with private cardinal preferences, as is common in modern preference aggregation theory. Each ballot \(y_i\) is a noisy observation, and a voting rule is the maximum-likelihood estimator of the ground truth under some noise model.
This turns out to be how Condorcet analysed the majority rule back in 1785— each juror has a probability \(p > 1/2\) of being right. The majority vote extracts truth. This was revived formally in Young (1988) and developed in Conitzer and Sandholm (2005), which catalogues which classical voting rules are MLE under which noise models. The “noisy oracles about a hidden ground truth” idea connects us to the Bayesian-elicitation literature, and to the truth-from-strategic-agents problem.
Under this lens, “what voting rule does ERM implement?” is a well-posed statistical question.
L2 ↔︎ Gaussian-noise MLE ↔︎ sample mean. Assume voter \(i\)’s report is a noisy observation of the ground truth,
\[y_i = f^*(x_i) + \epsilon_i, \qquad \epsilon_i \sim \mathcal{N}(0, \sigma^2).\]
The MLE of \(f^*\) at \(x\) is
\[\hat f^*(x) = \arg\max_z \prod_{i \in S_x} \mathcal{N}(y_i; z, \sigma^2) = \tfrac{1}{|S_x|} \sum_{i \in S_x} y_i,\]
the sample mean. So L2 ERM is MLE under additive Gaussian noise.
CE ↔︎ categorical-MLE ↔︎ empirical conditional. We assume voter \(i\)’s label is sampled from the true conditional,
\[y_i \sim \mathrm{Categorical}\bigl(p^*(\cdot \mid x_i)\bigr).\]
The MLE of \(p^*\) at \(x\) (with \(p\) free on \(\Delta_K\)) is
\[\hat p^*(\cdot \mid x) = \arg\max_{p \in \Delta_K} \prod_{i \in S_x} p(y_i) = \tfrac{1}{|S_x|} \sum_{i \in S_x} \delta_{\cdot, y_i} = \hat p_\text{emp}(\cdot \mid x),\]
the empirical conditional distribution. Cross-entropy ERM is categorical MLE.
The bounded per-example gradient of CE drops out as a property of the categorical likelihood: \(\partial_{\mathrm{logit}} \log p_\theta(y \mid x)\) is bounded for any softmax, regardless of how skewed the empirical conditional is. No single sample can dominate the MLE the way an outlier can dominate Gaussian L2 — \(\Delta_K\) is compact, and the log-score is bounded by its geometry.
The general pattern. The framing extends past supervised learning:
Most of these seem relatively uninteresting to me, although the last one seems to have potential. The Kemeny–Young rule takes voters’ submitted rankings and outputs the consensus ranking \(\sigma^*\) that minimizes total pairwise disagreement with them — the sum of Kendall-tau distances \(\sum_i d_\text{KT}(\sigma_i, \sigma^*)\), where \(d_\text{KT}\) counts pairs of alternatives the two rankings order differently. Under the Mallows model — where voters’ rankings are noisy observations of a hidden true ranking, with each pairwise disagreement penalized by a concentration parameter \(\phi\), \(p(\sigma \mid \sigma^*) \propto \exp(-\phi\, d_\text{KT}(\sigma, \sigma^*))\) — Kemeny–Young is exactly the MLE (Young 1988). It’s the canonical Condorcet-consistent rule, and it’s NP-hard to compute in general.