Distortion of AI Alignment: Does Preference Optimization Optimize for Preferences?
Authors: Paul Gölz
Nika Haghtalab
Kunhe Yang
Venue: NeurIPS 2025 poster ()
Keywords: social choice
distortion
RLHF
PPO
DPO
Nash Learning from Human Feedback
Primary area: theory

Abstract: After pre-training, large language models are aligned with human preferences based on pairwise comparisons. State-of-the-art alignment methods (such as PPO-based RLHF and DPO) are built on the assumption of aligning with a single preference model, despite being deployed in settings where users have diverse preferences. As a result, it is not even clear that these alignment methods produce models that satisfy users \emph{on average} --- a minimal requirement for pluralistic alignment. Drawing on social choice theory and modeling users' comparisons through individual Bradley-Terry (BT) models, we introduce an alignment method's \emph{distortion}: the worst-case ratio between the optimal achievable average utility, and the average utility of the learned policy. The notion of distortion helps draw sharp distinctions between alignment methods: \emph{Nash Learning from Human Feedback} achieves the minimax optimal distortion of $(\frac{1}{2} + o(1)) \cdot \beta$ (for the BT temperature $\beta$), robustly across utility distributions, distributions of comparison pairs, and permissible KL divergences from the reference policy. RLHF and DPO, by contrast, suffer $\geq (1 - o(1)) \cdot \beta$ distortion already without a KL constraint, and $e^{\Omega(\beta)}$ or even unbounded distortion in the full setting, depending on how comparison pairs are sampled.

Distortion of AI Alignment: Does Preference
Optimization Optimize for Preferences?
Paul Gölz
Nika Haghtalab
Kunhe Yang UC Berkeley kunheyang@berkeleeyyy edu
Cornell University paulgoelz@cornell.co
UC Berkeley
nika@berkeley.cm
Abstract
After pre-training. large language models are aligned with human preferences based pairwise comparisons. State-of-the-an alignment methods (such PPO-based RLHF and DPO) are built on the assumption of aligning with a single preference model, despite being deployed in settings where users have diverse preferences. As a result, is not even clear that these alignment methods produce models that satisfy average
minimal requirement for pluralistic alignment. Drawing social choice theory and modeling users' comparisons through individual Bradley- Terry (BT) models, introduce alignment method's ' distortion: the worst-case ratio between the optimal achievable average utility, and the average utility of the learned policy. The notion of distortion helps draw sharp distinctions between alignment methods: Nash Learning from Human Feedback achieves the minimax optimal distortion (1)+ (for the BT temperature 33), robustly across utility distributions, distributions of comparison pairs, and permissible KL divergences from the reference policy. RLHF and DPO, by contrast, suffer 2 (1-o(1)) B distortion already without a KL constraint, and en() or even unbounded distortion in the full setting, depending on how comparison pairs are sampled.
Introduction
has become the dominant paradigm for aligning large language models (LLMs) with human values and preferences. In typical alignment pipeline, human feedback provided as ordinal comparisons between pairs of candidate model outputs. This feedback is used to fine-tune pre-trained model, steering it toward the preferences expressed in these comparisons. A major limitation of RLHF and of many proposed alternatives (including DPO [43], 4PO [5 KTO [24), SimPO [3], XPO [00 is that they do not take into account that users will disagree on which model outputs are most useful or least harmful. growing body of evidence from both the general public and the research community 41 20
Reinforcement Learning from Human Feedback (RLHF) 38 +
18 59
suggests that this blind spot of current alignment methods can lead to unfair outcomes. For example, Chakraborty et al. 133 argue that RLHF may align with majority group's 's preferences and ignore the preferences of a minority.
In this work, study more basic question: do current alignment methods reliably lead to a high average utility across the users? Even such a minimal requirement might not be automatically met since alignment methods such as RLHF were originally designed with single, perhaps representative, user in mind whose noisy ordinal preferences are assumed to be consistent with an underlying utility model. As result, RLHF fits single reward model to the observed ordinal comparisons of population of users with different utility functions, effectively constructing a utility function for a "mythical" representative user. Could be that optimizing model for this mythical user leads to poor outcomes on average for real users? More fundamentally, do ordinal preferences even contain enough information to ensure high average utility across a heterogeneous user population?
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Preterance Data
Moxtmuu Bielhood
Lange Predinined Model (t-er)
Boncord Mudel
Fettin toa "mythiaa uaer
Users
dutoriin Angllille)
Finetaned model (e)
Figure I: The typical RLHF pipeline. The preference optimization process begins by collecting comparison data from users with potentially diverse utilities. A single Bradley-Terry model is then fit to this data via Maximum Likelihood Estimation (MLE), producing single reward model that represents "mythical user" whose utility best explain the observed heterogeneous preferences. This reward model is used to fine-tune pretrained policy. We define distortion as the ratio between the average utility of an optimal policy and that of the output policy, capturing how well the mythical user's utility aligns with the true average utility.
Distortion of alignment. To address these questions, we introduce the distortion of an alignment method[ which define as the ratio between the optimal average utility of policy (if the training process had access to users' true utilities) and the average utility achieved by the fine-tuned policy. A larger distortion implies lower average quality relative the optimal policy. This notion adapted from social choice theory [e.g.. 41 10 4]. where distortion quantifies the loss in average utility caused by using a voting rule that relies solely on ordinal preferences rather than full cardinal utilities.
Our setting departs from this classical formulation of distortion in two ways. First, we assume that users make pairwise comparisons probabilisttially. following Bradley-Terry model based on the user's idiosyncratic utilities. This assumption of probabilistic comparisons enables much less pessimistic distortion bounds than in the classic, deterministic-choice setting while capturing heterogeneous preferences. Second, our model and distortion bounds reflect that, in alignment, the models' generation policy is constrained stay close the pre-trained reference policy. These departures generate insights for both the social choice and the alignment communities.
1.1 Our Results
Our results address both the social choice setting with individual Bradlcy-Terry comparisons (Sec- tion and the alignment setting (Section 4p, which additionally constrains the policy to remain close in Kullback-Leible (KL) divergence to a reference policy. The social choice setting is a special case of the alignment setting, in which the proximity constraint is not binding. Besides RLHF, which coincides with the Borda voting rule in the social choice setting, we study the proposed alternative Nash Learning from Human Feedback (NLHF) (36), which coincides with the Maximal Lotteries [25) voting rule. Direct Preference Optimization (DPO)
4 is equivalent to RLHF in our analysis and
hence has the same distortion (see Appendix F.3 We define these alignment methods and voting
rules in Section 2 In Section we discuss how our results extend to KL-regularized (rather than constrained) alignment methods and generalized models sampling comparison pairs.
In this overview of results, summarized in Table I we present our bounds for the case where the number of sampled pairwise comparisons goes to infinity. In later sections, we accompany these statements with polynomially fast, finite-sample convergence bounds.
Our results establish that some distortion is unavoidable: in the social choice setting (i.e., without KL constraints), each user only provides single comparison, we show through non-identifiability argumen F that, for each value B > 0 of the Bradley-Terry temperature, every alignment method (or, equivalently, any voting rule) will suffer distortion of ( + o(1)), on some instances. This lower bound reflects a fundamental information bottleneck: even under Bradley-Terry generative
'While prior work has called for the study of distortion in alignment (2 or used alignment as motivation for studying the distortion of voting rules 229 (2). work define and analyze distortion of alignment methods. We discuss these related efforts in Appendix |
best knowledge the first to systematically
While the non-idene non-ideniifiablity of mixtures of ranking models is well established [57 56] (55), our result shows that the non non-identifiability be catastrophic, leading unavoidable loss in average utility.

---

Table 1: Overview of distortion bounds by alignment method and setting.
Alignment Method
Social Choice Setting
AI Alignment Setting
O Thm
RLHF 59
2 (1-o(1)) 3 Thm (Borda)
2 e ((8)) Thmm Unbounded in , Thm
NLHF 33
[ + o[]) 8 Corf
(Max. Lotteries)
= [} + o1)) B Thm
all (one comparison per user! Condorcet loser property)
+ (1))
2 ( + o()) 8
comparison pairs sampled from a distribution over pairs.
assumptions, ordinal feedback is not rich enough to perfectly optimize for the average utility of a heterogeneous user population. If cach user provides d 2 2 (possibly correlated) comparisons, the same lower bound applics to all voting rules that satisfy a probabilistic relaxation of the Condorcer loser criterion, a social-choice axiom widely satisfied by desirable voting rules, including Borda and Maximal Lotteries. As a result, this lower bound extends to RLHF and NLHF.
In the social choice setting, we show that both Borda and Maximal Lotteries have a distortion that is bounded in 3. Borda's 's distortion lies between (1 11-olp o and O(3)), whereas Maximal Lotteries' distortion is { o(1) (1))), matching even the lower-order terms of the lower bound. These results are of independent interest to the social choice community since they show that the introduction of randomized pairwise comparisons circumvents the necessary growth of distortion in the number of alternatives m. Recently, Goyal and Sarmasarkar [29] showed that the same Bradley-Terry assumption can reduce the distortion of specific voting rules in the metric distortion setting, where utilities are distances in a metric space. Our results show that the Bradley-Terry assumption has an even larger impact on general-utility distortion, where constant distortion is classically impossible, than in metric distortion. We derive the distortion bounds through a simple yet broadly applicable linearization lemma that sandwiches win-rates between linear functions, which be generalized to other random utility models as well. These distortion bounds also carry implications for AI leaderboards such Chatbot Arena (16), where heterogeneous user preferences across diverse tasks are aggregated via MLE under a single Bradley-Terry
effectively equivalent to using Borda scores. We elaborate on these implications in Section 3.3
In the alignment setting, we show that NLHF maintains Maximal Lotteries' optimal ( + o()) distortion with remarkable robustness: regardless of the population's utilities, how comparison pairs are sampled, the number of comparisons per user, the reference policy, and the bound on the permissible KL divergence, NLHF obtains ((1/3) fraction of the highest average utility achievable within the KL-divergence bound. Though we present this result for KL-constrained NLHF, we show in Section that this directly implies similar distortion guarantee for regularized NLHF, In contrast, RLHF's distortion can grow e(()) in the alignment setting and is even unbounded in / if the two outcomes to be compared are sampled in a correlated way rather than i.idd
We discuss additional related work in Appendix A
2 Preliminaries
Let A = {I..... m} be a finite set of alternatives. The population of users is described by probability distribution D over utility vectors (u(1)...., u(m)), whose entries 0 S u(x) S 1 indicate a user's 's utility for alternative x: The objective is to find an alternative z such that its average utility (vgUtil(z:) = En [=) across the user population (also known as the utilitarian social welfare) is as high as possible. We extend this notation to probability distributions π over alternatives by setting AvgUtil(z) == Ez (vggUti((())])
Both voting rules and alignment methods observe comparisons from n users. We model each i 1,... n fresh user with independently drawn utility vector u, D. For exposition, assume that each user provides an equal number d 2 1 of pairwise comparisons. For each i, and for = 1....,d. d, we independently draw alternatives x/. vl from fixed distribution μ over
*Our assumption that utilities be in J0, 1] is weaker than any of the three assumptions unit-sum, unit unit-range. approval (23 made in classic distortion avoid trivial infinite lower bounds.
3

---

alternatives. in which the minimum probability mass Mmin == minzed plx) is positive User i then compares each pair {x) y²} (for I,...,d) d) through a Bradley-Terry model based on i's utilities: prefers xi over sf (written "x >- v²"") with probability o aB (u,(x²) (x(y))) ))) where o(t) = 1/()=e is the logistic sigmoid function and [ is temperature parameter, and prefers y/ over x? ("yl b; xrl") otherwise Whereas this specifies the marginal probability of each pairwise comparison, we make assumption about the correlation between i's choices. For example, i might derive the pairwise comparisons from a Plackett-Luue ranking, ensuring that the user's comparisons always consistent ( We set p(z > y) for the expected win rate Eu (a (u(z) u(v)))].
Social Choice Setting, A voting rule f observes the sampled pairwise comparisons {z) >; v se(] and maps them to probability distribution over alternatives. For some m, D, 8. d. μ. and the correlation between comparisons, the average utility of ʃ for n samples is AvgUtil, (f) == E [AvgUttil (f(12) > ui }r,))] where the expectation is taken over the pairwise comparisons. The distortion of I' on D is the competitive ratio between AvgUtil, (J) and the optimal average utility max,EA AvgUtil(x) in the limit of n + oo samples, and the distortion of f the worst-case distortion over all D:
dist D) == lim sup
maXzEA AvgUtil(a)) { AugUtil, (f)
dist (f) = supp dist(J, D)-
For alternatives x, y. let #(I > y) = {(i.5) x!. = =x, = y/ denote the number of pairwise comparisons in which beat y. The (normalized) Borda score 45 of alternative x is
Σvea #(x2v)
BC(x) Eye #( #(v+x):
ie., the fraction of pairwise comparisons involving in which it wins. The Borda voting rule chooses the winner uniformly among all alternatives with maximum Borda score. The Maximal Lotteries vot- ing rule first computes the margin matrix M E Rm*m, where Mz.y siders symmetric two-player zero-sum game in which player I selects alternative 1 player selects alternative 22, and the payoffs are May,a for player and Mæg = - -Ma for player 2. The max- imal lotteries rule returns a distribution E argmaxx (AAA) minn)) (ee_w11,22000 (22. i.e., mixed strategy in Nash equilibrium. When several such æ exist, our results hold for any choice.
#()==) It then con-
Alignment Setting, The alignment setting generalizes the social choice setting in two ways: first, user utilities uz(y æ) may depend on a state æ; second, the goal in determining policy w is not purely to maximize the reward AvgUtil(T x), but a trade-off between this reward and the goal of remaining close reference policy -er(- x) E (AA in terms of the KL divergence ( Tre)). For theoretical tractability, we focus our analysis on a single state æ, which we from here on omit from the notation. Conceptually, this treatment of alignment on a state-by-state basis corresponds to an assumption that our policy class is expressive enough so that it can take the optimal distribution of actions at each state and abstracts from the generalization problem of estimating the population's 's preference between pair of alternatives at the given state æ based on preferences in similar states x'.
Having set aside the dependency between states, we focus on how the regularization with respect to reference policy impacts the ability to optimize the average utility of three alignment methods: RLHF, DPO, and NLHF. In addition to the pairwise comparisons, these methods take in a reference policy Jee E ((A) and KL bound 2 0, and map these inputs to policy π in the KL-ball B, = { E ((A) (xL(TT] Tee) r} around the reference policy, RLHF, DPO, and NLHF are typically implemented with a KL regularization rather than our KL-constrained formulation, which we adopt to enable a comparison on equal terms. In Section 5 we show that these perspectives are equivalent, and that distortion upper bounds carry over to regularized alignment methods.
'In Section 5 we discuss how most of our results extend more general distributions over comparison pairs. which can, for example. capture w-siee comparisons.
'Should we sample the same alternative x = xi = y twice for a pair, the user is not asked for a pairwise comparison. We record this as "r >; x",, in slight abuse of notation.
'In particular, if we sample the same unordered pair twice for a user, the answers can perfectly correlated.
"This assumption is common in the literature; see, for example, Rafailov et al. [43)ss application of first-order optimality conditions of PPO loss minimization.

---

The RLHF method first estimates rewards for each alternative, using maximum likelihood estimation assuming that comparisons were generated by a single Bradley-Terry model:
argmaX,ER* Eisignasisd log (o(r(z)) - r(())))
Next, RLHF uses PPO 4 to compute the policy TRLHF = arginax; Eg [r()]] with maximum expected reward within the KL-ball. In our setup, DPO is equivalent to RLHF (see Appendix F3 and thus has the same distortion.
The alignment method NLHF was inspired in part by a desire to better align with the preferences of a heterogeneous group [36]. NLHF naturally adapts the definitio of maxi- mal lotteries by constraining both players' mixed strategies to the KL-ball, i.e., TNLHF =
argmax,, n; (ma)) (B((m)) mill,,
(Tta) Ez [Mz
To generalize the definition of distortion to aligmment methods, we set the maximum average utility of any policy in the KI.-ball as the benchmark. For fixed m, 3, d, j and correlation between pairwise comparisons, the distortion of alignment method f is
dist = supD, ThatiT limsup
max EE max AvgUtil, (S (f(-Tatts7)
(Tar) AvgUhil(m)
3 Social Choice (or AI Alignment without KL Constraint)
We begin the demonstration of our distortion framework in the social choice setting. From the perspective of alignment, this setting is the limit where the KL constraint (equivalently, KL regu- larization) to the reference policy vanishes. Hence, distortion measures whether the "direction" in which an aligmment method pushes the pre-trained policy is aligned with average utility at all.
Moreover, the social choice setting allows us to illustrate how the Bradley-Terry assumption over- comes the pessimism of classic deterministic-choic distortion. In the classic setting, high distortion ((ym) even for randomized voting rules and under iillitynormalizzttio assumptions [10 23 is
unavoidable because a voting rule observes no signal about preference intensity, i.e., whether a user prefers over b strongly is merely breaking a tie between equally valued alternatives. Random Bradley-Terry comparisons would clearly side-step this problem if we could observe many samples of each pairwise comparison for single utility vector: by consistency, the Bradley-Terry MLE would recover the utilities (up to an additive shift), allowing us to select the utility-maiiiizin alternative and achieve a perfect distortion of 1.
is not obvious, by contrast, that random pairwise comparisons will be similarly useful in our heterogeneous setting, where each observation is drawn from mixture of users' Bradley-Terry models. Because users are not labeled and may provide as little as a single pairwise comparison, there is no hope to cluster users and estimate rewards per cluster. Instead, source of inspiration is an observation by Caragiannis and Procaccia 12] in a much simpler model, in which each user votes for single alternative with probability equal to their utility (which is normalized to sum to 1). Since the probability of the event "i votes for x" equals uz(z). the total number of votes of alternative x (i.e., DiEN votes for is unbiased estimator of its total utility. For many samples, this estimator concentrates around its mean and allows to select the optimal alternative. The argument would extend if some observed events from a user had probability that is affine in the user's 's utilities. Alas, we are not so lucky: the sigmoid function in the probability of the event "i ranks over y is nonlinear, and we show in Theorem 3 that this nonlinearity makes distortion of at least
1.0
1 unavoidable.
uppar bound
09
05.60
Though our observations' probabilities are not affine in the utilities, we can bound these probabilities by affine functions, which ultimately powers our distortion upper bounds. As shown in Fig. 2
oif (u(x) o(yl)
bound
0.5
1.0
we sandwich the probability a (u(x) u(y))) that user with utilitics u prefers x over y between the affine lower bound B u Eg u(
Figure 2: Bounds on probability of pre- ferring over y, 8 = 5.
and affine
"Assuming that each A wins at least one pairwise comparison against each * æ. this optimization has maximizer, which is unique up to additive shifts, by strict convexity.
5

---

upper bound B- (Lg u(x) L u(y) + 2.2 for constants L, Lg defined below. By linearity, this bound
extends to a bound of the expected win-rate p(r > y) E. En [o(3 (u(x) "(y))) by affine expressions in AvgUtil(a:) = ENED [u(x)) and AvgUtil(y) = ENND [u(y]]. We defer the lemma's formal proof to Appendix C
Lemma 1 (Linearization of Expected Win-Rates). Let == d0()) 1/4 and lg = -(8)-
D
I-e-6
For any pair of alternatives y, E A, we have
23
I+e-3-
B (lg AvgUtil(()) L. AvgUtil(y)) S p v) 53.. (L. AvgUtil(z)) - lg AvgUtil(y)).
3.1 Upper Bound on Borda Distortion
Siththaranjan et al. [46 observed that RLHF and the Borda voting rule are closely linked in that the Bradley-Terry MLE rewards are ordered by their alternatives' Borda score. Hence, as the KL constraint relaxes, RLHF moves all of the policy's probability mass on the Borda winner. Because Borda has infinite distortion in classic setting [41], we would hope that distortion more reasonable under our assumptions. Fortunately, Borda indeed has at most O distortion, which we prove through two applications of our lincarization lemma:
Theorem 2 (Borda Distortion Upper Bound). For any instance with any number of alternatives m. distribution over alternatives, and temperature 3, Borda has at most distortion ( ( In the finite-sample regime, have that
Lte P
T-e
AvgUtil,, (Borda) 2 (3 1-e ite-s) maxx AvgUtil(z*)- -o -
log(mn,9) L,
m. log(mn))
+
Proof sketch (full proof in Appendix E. For exposition, sketch this proof for 0C, assuming that each alternative's s Borda count has converged to its expectation BC* = Σyea p(z) > y).
Let å = argmaxze. (x) be the Borda winner in the limit, and xt = argmax AvgUtil(x) be the utility maximizer. Applying Lemma I to the win-rates p( > y) and p(x* y) for all y E A, we have that
(.)) S EVEAM()) (L AvgUtil(s) Eg AvgUtil(y))
= 3 (L AvgUtil(E) lo AvgUtil(A)):
(I)
BC*(x*) 2 EyEAR(U) B (Eg AvgUtil(**)) - L AvgUtil(y))
3 (lg AvgUtil(z") L AvgUtil(u)).
Since BC*(#) BC BC*("*) obtain from the above two inequalities that
L AvgUtil(3) + (L (a) (vgUtil(44) 2 ts AvgUtil(z").
A standard averaging argument shows that (BC, (=)) 1/2, which implies that (.) must be at least 1/2. Combining this with Eq. (1. obtain that AvgUtil(z) < # AvgUtil(f). Substituting this into Equation
(2) (noting that (a), we have that
1 AvgUtil($) L AvgUtil + (L-fa) L AvgUtil(#) Eo
Eg
2 L AvgUtil( ④) (L - (g) AvgUtil(μ)) 2 lg AvgUtil(z*),
which yields the distortion guarantee
AvgUtil(e*)) AvgUtil(2)
< (2)2 = -6 (1tte=2)
3.2 Lower Bounds (and Upper Bound for Maximal Lotteries)
The upper bound for Borda nested two applications of the linearization lemma. As result, it twice incurred a distortion factor of F [a(3) which measures the sigmoid function's deviation from linearity in the relevant range. Below, we show that any voting rule must incur this factor at least once, at least for the case of the voting rule has access to infinitely many pairwise comparison samples, which shows that the nonlinearity of the Bradley-Terry model can cause loss of the information necessary to find the utility maximizer.
(0)))
comparisons per user. This distortion occurs even though

---

The proof (in Appendix E.3)
constructs a user population D in which a small minority has utility I for some special alternative a and 0 for all other alternatives, whereas the majority has a small utility e for all alternatives except for a, for which they have utility 0. The sizes of these blocs are balanced such that all expected win-rates are 1/2. Due to the diminishing returns in the sigmoid function, the resulting average utility for is L EF times higher than that of the other alternatives. But since the pairwise comparisons observed by a voting rule are just independent Bernoulli draws with bias 1/2. all versions of the instance with permuted alternatives are indistinguishable. Since no voting rule can identify alternative a better than random guessing, they must incur L. distortion.
Ey
If there are d 2 2 observations per user, the above argument does not apply to all voting rules because an elaborate voting rule might use the correlations within a user's comparisons to identify a. We can, however, extend the lower bound to d 2 2 for all voting rules that put at most 1/m probability mass on a Condorcet loser, i.e., an alternative x such that #(y > x) > #(x > y) for all y & x. This property generalizes the Condorcet loser criterion and is satisfied by wide range of voting rules deemed desirable, including Borda and Maximal Lotteries. The proof uses essentially the same instance above, slightly tipping the expected win-rates against to make it Condorcet loser. Since the social choice setting is a special case of alignment, the lower bound extends to alignment. Theorem 3 ( (Voting Rule-Independen Distortion Lower Bound). Fix any B >> 0. If each user provides d=1 comparison, no voting rule can guarantee distortion better than 2 I- user reports 2 2 pairwise comparisons, any voting rule that puts at most 1/m probability mass on Condorcet loser must have at least the above distortion.
L+e for large m. If each
The Maximal Lotteries voting rule exactly matches the above lower bound of 3
T-e We omit the in the next section. proof here, as follows direct corollary of NLHF's upper bound (Theorem 7
1+e-8 9
Corollary (of Theorem 7p. The Maximal Lotteries voting rule has a distortion of 2/ 1
1-e-#-
The Borda rule, in contrast, does not match this optimal distortion bound, as shown by the following bound that we prove and state in full detail in Appendix B.2
Theorem 5 (Borda Distortion Lower Bound, Informally). For any B > and m 2 the distortion
guaranteed by Borda (and, hence, RLHF) is greater than and bounded away from 2 I--e 3- In particular, as 3 + co, this distortion guarantee is at least (1 (1-00) (1-o(1)) B.
Ite-0
3.3 Discussion
Implications for Social Choice Theory. Though we have presented these bounds in terms of their implications for alignment, they are of independent interest to social choice theory. In the classical social choice setting- - where each voter's 's ranking is produced deterministically, without any randomness such that introduced by a Bradley- (with nonnegative utilities) exhibits serious limitations. In particular, it leads to unreasonably high distortion and some unnatural prescriptions. For example, any deterministic voting rule has distortion ((m²). ), where optimal distortion is achieved by Plurality [12 (a rule widely disregarded by social choice theorists) whereas Borda and all Condorcet consistent rules have infinite distortion [4I). These limitations may explain in part why recent research activity [e.g.. 28
model the distortion framework
29) has focused on the in which many natural voting rules have constant distortion. But
metric distortion setting this comes at the cost of expressiveness: the metric setting assumes utilities are (negated) distances satisfying the triangle inequality. For example, the metric distortion setting implies that, if i has high utility for æ and y. and has high utility for x, then must also have high utility for which need not be the case in our setting. We see our assumption of a user-specific random choice model as another way to make distortion a more practical criterion for choosing between voting rules.
Implications for AI Leaderboards. Our results also have implications beyond being a special case of alignment. A notable example is LLM leaderboards such as Chatbot Arena [16]. where users submit prompts, are shown the responses of two anonymized models, and select their preferred response. The leaderboard aggregates these pairwise comparisons by fitting a Bradley-Terry model via MLE, and ranking the models according to their estimated rewards. As in the alignment setting, this approach assumes single latent notion of LLM quality, ignoring the fact that LLMs are used by diverse users for a wide range of tasks, each with their own goals, preferences, and prompt styles. This setting fits neatly into our social-choice model, where D captures random user's utility for the responses of different models to a random prompt (drawn from an arbitrary joint distribution over users and prompts), and AvgUtil quantified the average utility a model delivers for a random user and task, which captures the model's 's usability. We defer more detailed discussion to Appendix B
7

---

4 AI Alignment with KL Constraint
We now tackle the general alignment setting, in which the output policy a must be chosen within a preseribed KI. divergence of the reference policy Tie-- This setting is more challenging than the social choice setting because even an alignment method that would choose high-utility alternatives in the absence of constraints might make poor use of finite KL budget.
4.1 Lower Bound for RLHF
Before presenting the optimal distortion upper bound for NLHF, we illustrate the pitialls of the alignment setting with lower bound on RLHF This bound shows that a KL. constraint can cause RLHF to have exponential distortion in 8, exceeding its quadratic upper bound in the social choice setting (Theorem 2.
Theorem 6 (RLHF Distortion Lower Bound), For m 2 3, there is a sequence of alignment problems on which the distortion of RLHF scales as e0) in B.
Proof sketch (full proof in Appendix F.2 For ease of exposition, consider an instance with three alternatives a, b, where ((() is about e times larger than p(aa) =(b) 9 Let the population consist of tiny minority (a (e)²) fraction) with utilities u(a) = 0, u(b) = 1, u(c) = O. and large majority with utilities u(a) = g. ((b)= = 0, u(c) = 1. Both a and are likely to be beaten by c, but by carefully choosing the size of the minority, we can make p(b > c) > p(a > c), i.e., we can make his advantage of being preferred by the minority outweigh a's advantage of being slightly less dispreferred by the majority. Since ja(e) is so much larger than (())) the vast majority of pairwise comparisons involving a or b are against c. As a result, the MLE reward for 6 will be higher than for a, even though AvgUtil(a) = ( is exponentially larger than AvgUtil(b) = O (In the social choice setting, this would not be problem because e has even higher average utility and higher reward.)
The lower bound arises for reference policy that puts a tiny probability mass c, and 1- probability mass each on a and b, together with a KL. constraint of r = log 2. Now DxL(TT || mer) = =(b)
x(a) (a)) log [I-=)/2 + T Tb) log (I-e)/2 + (c) log xie), Since is very small, <(c) cannot be increased by enough to make meaningful difference on the achievable utility; but the KI. budget essentially allows to spread the probability mass of æ freely between a and b. Since b has a higher MLE reward, RLHF puts almost all of T's mass on b, which yields exponentially less utility than the uility-maximizing policy in the KL ball, which puts almost all mass on a.
This bound formalizes a key limitation of the reward- baseed approach inherent to RLHF. The MLE phase of RLHF attempts to fit rewards to the observed comparisons, whose frequencies are determined by J.. Due to preference heterogeneity, not all three pairwise win-rates can be simultaneously fit by a reward vector, so the MLE sacrifices accuracy on the rarely observed pair (a, b) for higher accuracy of comparisons involving c. By placing so little mass on c, our choice of Tee forces RI.FF to choose between the misrepresented alternatives and b, causing it to make high-distortion choice.
Our lower bound exploits that the distribution μ governing the frequencies of comparison pairs differs greatly from the reference policy Teef We leave open to characterize RLHF's distortion under the assumption that = Tet, for which we only know the lower bound Theorem 5
4.2 Distortion of NLHF
While we saw above that a mismatch between input distribution μ and reference policy nee can lead RLHF towards highly suboptimal policies. NLHF has no such problem. Below, we show that, across all settings of our model, NLHF'ss distortion exactly matches the lower bound from Theorem 3
Despite the generality of this result, the proof is no harder than our upper bound for Borda in the social choice setting and involves only a single application of the lincarization lemma. It also highlights key advantage over RLHF's reward-basee approach: Since the NLHF policy is computed Nash-equilibrium strategy in a game where the opponent might select any policy in the KL ball, the NLHF automatically "hedges" to perform well in expectation against all such policies, including the benchmark "r. Since the social choice setting is special case of alignment, this theorem immediately implies the distortion upper bound for Maximal Lotteries (Corollary 4. and both NLHF and Maximal Lotteries are minimax optimal by the lower bound in Theorem 3
To avoid such unbalanced μ., one could equivalently copy alternative many times and let μ be uniform.
8

---

Theorem 7 (NLHF Distortion Upper Bound). For any instance DD and any m, data distribution μ., temperature 3 of the Bradley- -eery model, and any reference policy we and KL budget T, we have
dis((NLHF) < 1tc I-c-B. B. In the finite-sampl regime, we have
AvgUtil, 2 (3
14c 1-e-d)
log(mn)) maX,* (B, AvgUtil(**)) -0 1--inn I, d-
+
(og(m (ram) n. n-Bu min
Proof sketch (full proof in Appendix F. For exposition, we assume that the NLHF method knows the expected win-rates p(r > v). and defer the proof of finite-sample guarantees, Hence, the NLHF policy by definition satisfies
TNHHF E argmax
min Eay Bo [p(x) > x2) - p(x2 > xi)].
x, E.EB-(ma) R (Tee)
Since this describes a Nash-equilibrium strategy for symmetric two-player zero-sum game, and any such game has value 0, it must hold that
min B (TFet)
E B [p(21 > x2) p(a2 > zi)]
Plugging in p(z) > x2) - pl12 > x1) 2 p(11 > 31) - 1, we obtain
B. T oo (p(m) > 22) 1/2] O.
Using the utility-maximiziin policy n² = BB. AvgUtil(** for Tτ. we obtain that R (p(a) > 22) - 0.
At this point, we upper bound the win-rate with the linearization lemma (Lemma D. and obtain
0 S Ex WTNNHE - [3 (L AvgUtil(211) - Es (vgUtil((22)] = B. (L. AvgUtil(#TNUL - f, AvgUtil(z")).
This implies that AvgUtil(*")
S 1/2 = -
0(3), thus completing the proof.
AugUHil(
The simplicity of the proof above also speaks to its generality. For instance, the only property of KL divergence we used was that the feasible region B, (Fter) is a closed convex set (to ensure the existence of Nash equilibrium). Consequently, the distortion bound of Nash learning extends to other ways of constraining proximity to the reference policy, such as by x² divergence [30].
5 Extensions of the Model
KL Constraints vs. Regularization. In our model, we defined alignment methods as taking in an explicit KL bound T as an input parameter, which convenient for comparing the policy against fair benchmark. In practice, however, alignment methods such as RLHF, DPO, and NLHF are regularized rather than constrained in terms of their KL-divergence. For example, the PPO phase of RLHF finds policy maximizing the regularized objective Ex~x [r(z]] ADRL Tee)), and the payoff matrix in the game solved by NL.FF is Tx R [May - >D m || (e))) + >DRL (T2 || (eer), where is regularization parameter given the alignment method instead of r.
We prove in Appendix F.4 that the regularized and constrained versions of RLHF and NLHF are equivalent. That is, each policy returned by the X-regularized version of a method is optimal for the r-constrained version for - = DxI.(m Feee) (and any policy returned by the r-constrained version is optimal for the X-regularized version and some À 2 0).
Through this equivalence, any distortion upper bound in our setting applies to the KL-regularized versions of the alignment method: if π results from the X-regularized alignment method, π is optimal for the -= DxI(" ( -oosscoonrr version by equivalence, bound shows that π can compete with any policy with no larger KL. divergence from T this observation to Theorem 7 we obtain the following guarantee for regularized NLHF:
which point the distortion upper
10 Applying
Corollary 8. If X-regularized NLHF (for any X > 0) returns policy ĀNLHF, this policy's 's average uiility at least 3 1-
1+e-= fruction of the optimal average utility of any policy n with DRI(m (Tr (mn)) S
D || Rnd) (minus f fimite-amppl errors, see Theorem] 7
Why not define distortion by flexibly selecting the benchmark based on the output policy's 's KL divergence? For this definition, an alignment method that always returns the reference policy would spuriously achieve distortion 1: because its KL divergence is O, we would benchmark it only against the reference policy, ie.. itself.

---

Sampling of Comparison Pairs, In our model, we assume that each voter provides d pairwise comparisons, where both members x/ uu of each comparison pair are sampled i.i.d. from μ.. More generally, we can model { v/} ~ V where is distribution over unordered alternative pairs, or even distribution over pairs of alternatives from which {=;; v/ :-.... v the alignment methods well defined, we assume that each comparison pair has positive probability of being sampled.) The latter of these models can, for example, express k-wise (rather than pairwise) comparisons, if d - (2) are all pairs inside randomly chosen set of r alternatives. Almost all of our results continue to hold in these general models: the lower bound for all alignment methods that satisfy the Condorcet loser criterion in the social choice setting (Theorem 3) the exponential lower bound for RLHF (Theorem 6). and the upper bound for NLHF/Maximal Lotteries (Theorem
sampled. (To keep
Given that our proofs continue to work out, the only "disadvantage" of these stronger models for sampling comparison pairs is that, without distribution μ., the Borda voting rule is no longer defined (and we see no obvious way to generalize the Borda-MIE equivalence [46 42 ). It seems that RLHF does not only become harder to analyze under these comparison models, but actually performs worse: we show in Appendix G that RLHF can have a distortion that is not bounded in | in these extended models, leading an even clearer separation with NLHE.
Theorem 9 (Unbounded Distortion of RLHF Under Correlated Sampling). For any B > 0, there exists a sequence of alignment instances and distributions E A ((2)) over comparison pairs such that RLHF's s distortion is unbounded.
6 Diseussion and Practical Takeaways
In this paper. we introduced the notion of distortion for Al alignment. We showed that one such alignment method, NLHF, obtains the optimal distortion guarantee of ( o(1) 3. Putting this bound into perspective, if we assume that user will rate a minimally preferred alternative over a maximally preferred alternative with 1% probability, this suggests a value of B log 99% 4.60 and distortion guarantee of about 2.34, which is a quite reasonable worst-case guarantee.
1%
For the incumbent method, RLHF, our analysis gave more negative results. Its distortion was worse than NLHF's in the unconstrained setting, exponentially worse in the constrained setting, and unbounded if the comparison pairs not drawn i.i.d.. Given the ubiquity of RLHF, it is pressing open question to fully characterize its distortion (especially when μ coincides with Tee) or find assumptions that guarantee lower distortion. A major technical challenge that bounding this distortion requires reasoning not only about the relative ordering of rewards but also their magnitudes.
Beyond these theoretical contributions, our results yields several practical insights:
Limitations of reward models as evaluation metries. Our findings indicate that reward- -odel scores are unreliable proxies for human satisfaction, not only because of insufficient data diversity or scale, but also due to fundamental Due to this limitation, it may be valuable to complement teward-mode! evaluations with direct measurements of cardinal preferences, such as graded feedback or satisfaction scores.
coormatiio--hhoretii limits of
conversion.
Sensitivity to post-training data distribution. The performance of reward-based pipelines such as RLHF is sensitive to the sampling distribution of pairwise comparisons, while the reward-free method NLHF shows greater robustness and theoretical tractability. As practitioners increasingly share or reuse post-traiming datasets across models and platforms, mitigating sensitivity becomes crucial.
Potential failure modes. Although our lower-bound constructions are stylized for analytic clarity, they highlight patterns that may emerge in practice for instance, systematic bias arises when comparisons frequently involve actions suppressed by the reference policy. Our theoretical frame- work provides principled way to study such effects and to identify the structural features of data distributions that most influence worst-case misalignment.
Finally, the distortion framework opens up many more questions: How large is the distortion of alignment methods besides RLHF, DPO, and NLHF? Can we extend the model to capture the generalization of preferences across states? Can distortion be reduced with little additional information? And can we go beyond average utility to capture finer- grained notions? After all, high average utility is necessary, but not sufficient, for successful alignment to heterogeneous population.
The finite-sampl bounds even improve in the latter model since each pair appears only once.
10

---

Acknowledgments and Disclosure of Funding
We thank Mark Bedaywi, Jim Dai, Sonja Kraiczy, Soroosh Shafiee, and Eric Zhao for helpful conversations. This work was supported in part by the National Science Foundation under grant CCF-2145898, by the Office Naval Research under grant N00014-24-1-2155, an Alfred P. Sloan fellowship. and Schmidt Sciences A12050 fellowship. Part of this work was performed while P.G. was at the Simons Institute for the Theory of Computing as a FODSI research fellow, for which he acknowledges the NSF's support through grant DMS-2023505.
References
[1] Al Incident Database. URL URL URLLiccpss/hhcccccddataaaass aii/
[2] Mayer Alvo and LH Philip. Statistical methods for ranking data, volume 1341. Springer, 2014.
[3] Elliot Anshelevich, Onkar Bhardwaj. Edith Elkind, John Postl, and Piotr Skowron. Approx- imating optimal social choice under metric preferences. Artificial Intelligence, 264:27-51, 2018.
[4] Elliot Anshelevich, Aris social choice problems: The first years and beyond. In Zhi- Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event Montreal, Canada, 19-27 August 2021, pages 4294 4301. ijeai.org, 2021. doi: 10. 24963/1JCA1.22215558
Nisarg Shah, and Alexandros A. Voudouris. Distortion
[5] Mohammad Gheshlaghi Azar, Zhaohan Daniel Guo, Bilal Piot, Remi Munos, Mark Rowland, Michal Valko, and Daniele Calandriello. A general theoretical paradigm to understand learning from human preferences. In International Conference on Artificial Intelligence and Statistics, pages 4447 4455. PMLR, 2024.
[6] Hossein Azari Soufiani, David C Parkes, and Lirong Xia. A statistical framework for social choice. Advances in Neural Information Processing Systems, 27, 2014:
[7] Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, al. Training helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint 3XXi:2204.005800 2022.
[8] Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, et al. Constitutional ai: Harmlessness from ai feedback. arXiv preprint arXiv:2212.08077 2022.
[9] Gerdus Benade, Swaprava Nath, Ariel D. Procaccia, and Nisarg Shah. Preference elicitation for participatory budgeting. Management Science, 67(5):2813-2821 2021. doi: 10/gmmm33.
[10] Craig Boutilier, Ioannis Caragiannis, Simi Haber, Tyler Lu, Ariel D. Procaccia, and Or Sheffet. Optimal social choice functions: A utilitarian view. In Proceedings of the 13th ACM Conference on Electronic Commerce, pages 197-214, Valencia Spain, June 2012. ACM. ISBN 1-5-0-- 1415-2. doi: 10. (0.1145/2229012.222900
[11] Daniele Calandriello, Zhaohan Daniel Guo, Remi Munos, Mark Rowland, Yunhao Tang, Bernardo Avila Pires, Pierre Harvey Richemond, Charline Le Lan, Michal Valko, Tianqi Liu, al. Human alignment of large language models through online preference optimisation. In Proceedings of the 41st International Conference on Machine Learning, pages 5409-5435, 2024.
[12] Ioannis Caragiannis and Ariel D. Procaccia. Voting almost maximizes social welfare despite lim- ited communication. Artificial Intelligence, 17509-10):1655-1671,, June 2011. ISSN 00043702. doi: 10/fknjz2.
[13] Souradip Chakraborty, Jiahao Qiu, Hui Yuan, Alec Koppel, Furong Huang, Dinesh Manocha, Amrit Singh Bedi, and Mengdi Wang. Maxmin-RLHF: Alignment with diverse human prefer- ences. arXiv preprint arXiv:2402.08925, 2024.
[14] Moses Charikar, Prasanna Ramakrishnan, Kangning Wang, and Hongxun Wu. Breaking the Metric Voting Distortion Barrier. Journal of the ACM, 133) December 2024. ISSN 0004-5411, 1557-735X. doi: 10. 10.1145/3689625.

---

[15] Daiwei Chen, Yi Chen, Aniket Rege, and Ramya Korlakai Vinayak. Pal: Pluralistic alignment framework for learning from heterogeneous preferences. arXiv preprint arXiv:2406.0888 08469, 2024.
[16] Wei-Lin Chiang, Liammin Zheng, Ying Sheng, Anastasios Nikolas Angelopoulos. Tianle Li, Dacheng Li, Banghua Zhu, Hao Zhang, Michael Jordan, Joseph E. Gonzalez, et al. Chatbot arena: An open platform for evaluating Iims by human preference. In Forty-first International Conference on Machine Learning, 2024.
[17] Keertana Chidambaram, Karthik Vinay Seetharaman, and Vasilis Syrgkanis. Direct preference optimization with unobserved preference heterogeneity. arXiv preprint arXiv:2405. 2024.
[18] Paul Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in neural information processing systems, 30, 2017.
[19] Vincent Conitzer and Tuomas Sandholm. Common voting rules as maximum likelihood estima- tors. In Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence. pages 145-152, 2005.
[20] Vincent Conitzer, Rachel Freedman, Jobst Heitzig, Wesley H Holliday, Bob M Jacobs, Nathan Lambert, Milan Mossé, Eric Pacuit, Stuart Russell, Hailey Schoelkopf, et al. Position: social choice should guide ai alignment in dealing with diverse human feedback. In Proceedings of the s1 International Conference on Machine Learning, pages 9346-9360, 2024.
[21] Jessica Dai and Eve Fleisig. Mapping social choice theory to RLHF. In ICLR 2024 Workshop on Reliable and Responsible Foundation Models, 2024.
[22] Soroush Ebadian, Daniel Halpern, and Evi Micha. Metric distortion with elicited pairwise comparisons. In Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI), pages 2791-2798, 2024.
[23] Soroush Ebadian, Anson Kahng, Dominik Peters, and Nisarg Shah. Optimized Distortion and Proportional Fairness in Voting. ACM Transactions on Economics and Computation, 12(1): 1-39, March 2024. ISSN 2167-8375, 2167-8383. doi: 10. 10.1145/3640760.
[24] Kawin Ethayarajh, Winnie Xu, Niklas Muennighoff, Dan Jurafsky, and Douwe Kiela. KTO: Model alignment as prospect theoretic optimization. arXiv preprint arXiv:2402.01300 2024.
[25] Peter C. Fishburn. Probabilistic social choice based on simple voting comparisons. The Review of Economic Studies, 5 51()):683-69) 692, 1984.
[26] Bailey Flanigan, Ariel D Procaccia, and Sven Wang. Distortion Under Public-Spiritee Voting. In Proceedings of the 24th ACM Conference on Economics and Computation. EC '23, page 700, New York, NY, USA. July 2023, Association for Computing Machinery. ISBN 979-8-4007- 0104-7. doi: 10. 145/3580507.359722
[27] Luise Ge, Daniel Halpern, Evi Micha, Ariel D Procaccia, Itai Shapira, Yevgeniy Vorob- eychik, and Junlin Wu. Axioms for Al alignment from human feedback. arXiv preprint 14775 2024.
[28] Vasilis Gkatzelis, Daniel Halpern, and Nisarg Shah. Resolving the optimal metric distortion conjecture. In 2020 IEEE 61 Annual Symposium on Foundations of Computer Science (FOCS), pages 1427-1438. IEEE, 2020. doi: 10. N0.1009/FOSS46700220000000
[29] Mohak Goyal and Sahasrajit Sarmasarkar. Metric distortion under probabilistic voting. arXiv preprint arXiv:2405. /4223v4, 2025.
[30] Audrey Huang. Wenhao Zhan, Tengyang Xie, Jason D Lee, Wen Sun, Akshay Krishnamurthy, and Dylan J Foster. Correcting the mythos of KL-regularization: Direct aligmment without overoptimization via chi-squared preference optimization. arXiv preprint arXiv:2407.13399 2024.
[31] Fatih Erdem Kizilkaya and David Kempe. Plurality Veto: A Simple Voting Rule Achieving Optimal Metric Distortion. In Proceedings of the Thirty- First International Joint Conference on Artificial Intelligence, pages 349-355, Vienna, Austria, July 2022. International Joint Conferences on Artificial Intelligence Organization. ISBN 978- 978-1-956792--0-3. doi: 10.24963/ 2022i..0
12

---

[32] Zhihan Liu, Miao Lu, Shenao Zhang, Boyi Liu, Hongyi Guo, Yingxiang Yang. Jose Blanchet, and Zhaoran Wang. Provably mitigating overoptimization in RLHF: Your SFT loss is implicitly an adversarial regularizer. In The Tiirth- Annual Conference on Neural Information Processing Systems, 2024.
[33] Roberto-Raate Rafael Maura- Rivero, Mare Lanctot, Francesco Visin, and Kate Larson. Jackpot! alignment maximal lottery. arXiv preprint arXiv:2501.19900 2025.
[34] Yu Meng, Mengzhou Xia, and Danqi Chen. SimPO: Simple preference optimization with reference-free reward. Advances in Neural Information Processing Systems, 37:124198-12222 2024.
[35] Abhilash Mishra. Ai alignment and social choice: Fundamental limitations and policy implica- tions. arXiv preprini arXiv:2310. 2600:2680.6 2023.
[36] Remi Munos, Michal Valko, Daniele Calandriello, Mohammad Gheshlaghi Azar, Mark Rowland, Zhaohan Daniel Guo, Yunhao Tang, Matthieu Geist, Thomas Mesnard, Côme Fiegel, al. Nash learning from human feedback. In International Conference on Machine Learning, pages 36743-36768. PMLR, 2024.
[37] Ritesh Noothigattu, Dominik Peters, and Ariel D Procaccia. Axioms for learning from pairwise comparisons, Advances in Neural Information Processing Systems, 33:17745- 2020.
[38] Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35:27730-27144, 2022.
[39] Chanwoo Park, Mingyang Liu, Dingwen Kong, Kaiqing Zhang, and Asuman Ozdaglar. RLHF from heterogeneous feedback via personalization and preference aggregation. arXiv preprint arXiv:2405.00254 2024.
[40] Sriyash Poddar, Yanming Wan, Hamish Ivison, Abhishek Gupta, and Natasha Jaques. Personal- izing reinforcement learning from human feedback with variational preference learning. The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[41] Ariel D. Procaccia and Jeffrey S. Rosenschein. The distortion of cardinal preferences in voting. In International Workshop on Cooperative Information Agents, pages 317-331. Springer, 2006.
[42] Ariel D Procaccia, Benjamin Schiffer, and Shirley Zhang. Clone-robust ai alignment. arXiv preprint 2rXiv:2501100254. 2025.
[43] Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. Advances in Neural Information Processing Systems, 36:53728-53741, 2023.
[44] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.063:: 06377777777..... 2017.
[45] Ali Shirali, Arash Nast-Esfahany, Abdullah Alomar, Parsa Mirtaheri, Rediet Abebe, and Ariel Procaccia. Direct alignment with heterogeneous preferences. arXiv preprint urXiv:2502.16320. 2025.
[46] Anand Siththaranjan, Cassidy Laidlaw, and Dylan Hadfield- Distributional prefer- ence learning: Understanding and accounting for hidden context in RLHF arXiv preprint arXiv:231..08338, 2023.
[47] Taylor Sorensen, Jared Moore, Jillian Fisher, Mitchell Gordon, Niloofar Mireshghallah, Christo- pher Michael Rytting, Andre Ye, Liwei Jiang, Ximing Lu, Nouha Dziri, et al. Position: a roadmap pluralistic alignment. In Proceedings of the 41st International Conference on Machine Learning, pages 46280-46302, 2024.
[48] Gokul Swamy, Christoph Dann, Rahul Kidambi, Zhiwei Steven Wu, and Alekh Agarwal. A minimaximalist approach reinforcement learning from human feedback. arXiv preprint arXiv:2401.0m 04056, 2024.
[49] Gokcan Tatli, Yi Chen, and Ramya Korlakai Vinayak. Learning populations of preferences via pairwise comparison queries. In International Conference on Artificial Intelligence and Statistics, pages 1720-1728. PMLR, 2024.
13

---

[50] Yuanhao Wang, Qinghua Liu, and Chi Jin. Is RLHF more difficult than standard RL? theoretical perspective. Advances in Neural Information Processing Systems, 36.76006-76032. 2023.
[51] Zhi Wang, Geelon So, and Ramya Korlakai Vinayak. Metric learning from limited pairwise preference comparisons. In Uncertainty in Artificial Intelligence, pages 3571-3602. PMLR, 2024.
[52] Yue Wu, Zhiqing Sun, Huizhuo Yuan, Kaixuan Ji, Yiming Yang, and Quanquan Gu. Self-play preference optimization for language model alignment. arXiv preprint arXlv:2405.00675, 2024.
[53] Lirong Xia. Bayesian estimators as voting rules. In Uncertainty in artificial intelligence, 2018.
[54] Lirong Xia. Learning and decision-making from rank data. Morgan & Claypool Publishers, 2019.
[55] Xiaomin Zhang, Xucheng Zhang, Po-Ling Loh, and Yingyu Liang. On the identifiability of mixtures of ranking models. arXiv preprint arXiv:2201.13132, 2022.
[56] Zhibing Zhao and Lirong Xia. Learning mixtures plackett-luce models from structured partial orders. Advances in Neural Information Processing Systems, 32, 2019.
[57] Zhibing Zhao, Peter Piech, and Lirong Xia. Learning mixtures of plackett-luce models. In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 2906-2914, New York, New York, USA, 20-22 Jun 2016. PMLR.
[58] Huiying Zhong, Zhun Deng, Weijie Su, Zhiwei Steven Wu, and Linjun Zhang. Provable multi- party reinforcement learning with diverse human feedback. arXiv preprint arXiv:2403.0500 05006, 2024.
[59] Daniel M Ziegler, Nisan Stiennon, Jeffrey Wu, Tom B Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geoffrey Irving. Fine-tuning language models from human preferences. arXiv preprint arXin:1909.085990 2019.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and the introduction clearly state the claims and contributions of this paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
15

---

We state our assumptions in each theorem, and provide proof for each theoretical result in either the main body or the appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
16

---

Answer: [NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
ooniioicoooyl) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/
CoodeSubeeiieeeeeeeeee ssi asionnolle onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
17

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http::////earrpp..cccppaaaaaaaaa
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: We proposed theoretical analysis framework rather than model or technol- ogy, so there is no direct societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
18

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
19

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
20

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
21

---

A Related work
Reward-based and reward-free alignment methods. The RLHF pipeline typically includes first training reward model via maximum likelihood estimation (MLE), then applying RL algorithms such as Proximal Policy Optimization (PPO) 44 to optimize policy that maximizes the reward [59, 77. Rafailov al. 43 proposes an alternative approach, Direct Preference Optimization (DPO), which bypasses explicit reward model training by directly optimizing an equivalent objective derived from the closed form of KL-constrained reward-maximizing policy. While the original formulation is based on single Bradley-Tece Terry model, we show in Appendix [.44 that the equivalence extends to settings with heterogeneous preferences. Building on the DPO framework. several recent methods including xPO (0]. RPO [32 and SimPO (34] have been proposed to improve the robustness and effectiveness.
Azar et al. 5 introduce 1PРO, another reward-free method that optimizes the expectation of a V-- transformation of the win-rates estimated from the offline comparison data. When V is the identity function, the resulting method - SalPO-reducee reduces to directly optimizing the normalized Borda count. Since RLHF is implicitly optimizing the normalized Borda count 46 42), this connection implies that IPO, DPO, and RLHF are all equivalent in the umregularizec/unconsrrannne setting.
Another reward-free free method is Nash Learning from Human Feedback (NLHF) [36] and its vari- ants [48] 52, [T]. which finds the Nash equilibrium of a game defined over the win-rate margins (i.... p( > y) ply z)) via online learning self-pli style algorithms. Maura- et al. 33 point out that NLHF can be viewed as a natural generalization of the Maximal Lotteries rule in social choice. Wang et al. [50] consider finding the Nash equilibrium of the win-rate matrix and reduce the problem to multiagent reward-based RL. They provide an impossibility result, showing the optimal policy is indeterminate when the underlying ranking model (e.g., Bradley-Terry with certain temperature) is unknown. In contrast, our results show that even when the ranking model is known, the optimal policy can remain nonidentifiable due to preference heterogeneity.
AI Alignment under heterogeneous user preferences. A growing body of recent works studies algorithms for Al alignment under heterogeneous user preferences. Siththaranjan et al. [46] points out that RLHF implicitly optimizes the normalized Borda count, which can lead to poor outcomes in the social choice setting. To address this, they propose Distributional Preference Learning (DPL), method that estimates distribution of score values for each alternative. Another line of work deals with heterogeneity by clustering user preferences and Icarning several reward models at once, then aggregate the learned reward models using various techniques such max-min optimization, which optimizes the worst-case reward among all clusters [17 13 or through aggregation rules motivated by axiomatic properties in social choice theory [58, 39 Poddar et al. [40] proposes variational inference approach that infers user-specific latent variables from preference data which enables steerable personalized language models. Chen et al. [15] proposes a framework based on the ideal point model, which learns a latent space of user preferences that can few-shot generalize to unseen users.
Statistical and Axiomatic Perspectives on Preference Aggregation. Maximum likelihood estima- tors (MLE), which serves as the core of the widely-used RLHF pipeline, can be viewed as voting rules: given set of rankings, they output a score for each alternative, thereby producing a single aggregated ranking. This connection was first observed by Conitzer and Sandholm 11), who show that any scoring-basee voting rule is maximum likelihood estimator under specific noise model. A rich literature in social choice theory has studied the axiomatic properties of such MLE-based voting
rules under various randomized ranking models (6 53 37 27 42 Notably, Ge et al. (27] analyzes
the axiomatic properties of MLE-based AI aligmment methods under the Bradley-Terry model for linear utility functions.
On the learning side, several works study the problem of learning mixture models from ranking data, see textbooks [ [4] for a comprehensive overview. Recently. Wang et al. [51], Tatli et al.
49 focus on learning metric spaces from pairwise preferences. Our work is notably related to the results on the non-identifiabiiiy of learning mixture of Bradley-Terry models from pairwise or k--isse preferences [57] 56 (55. We build on these results to quantify the loss of utility due to non-identifiability by proving a voting-rule independent distortion lower bound.
22

---

Distortion of randomized voting and RLHF.
The framework of implicit utilitarian voting, i.c., of
comparing voting rules in terms of their distortion was introduced by Procaccia and Rosenschein [4] which has since sparked a large body of work lork--bo both in the original utility setting [12 10 23
26 g
23 and in the metric setting 4 14 31] Several recent works have highlighted the importance
of using distortion as a metric to evaluate the quality of Al alignment methods. Dai and Fleisig [2]
draw a conceptual connection between social choice and RLHF, and propose to apply the notion of distortion to RLHF. Goyal and Sarmasarkar [29] uses alignment as motivation for studying the metric distortion of probabilistic voting rules under Bradley-Terry and other random utility models, where the voters and candidates We not only study the non-metric distortion (which is more expressive), but also go beyond the social choice setting to consider the alignment setting in which output policies are constrained to remain close to a given reference policy. More broadly, our work also contributes to the growing line of research on the intersection of social choice theory and RLHF, advocated in recent position papers
assumed to lie in common metric space satisfying triangle inequality.
20 35
B Distortion in AI Leaderboards
The AI leaderboard setting fits natural into our social-choice model, where D captures a random user's utility for the responses of different models to random prompt (drawn from an arbitrary joint distribution over users and prompts), and AvgUtil quantified the average utility a model delivers for a random user and task, which we call the model's 's usability.
Since Chatbot Arena and RLHF based on the same MLE, our distortion bounds on RHLF in the social choice setting imply that the usability of the top-ranked language model (i.e., the Borda winner) may be (1 o(1)) 33 times worse than the usability of some other ranked model (Theorem 5 (but at most by a ( factor, see Theorem 2. Our results in an extended setting in which comparison pairs are drawn in a correlated way (Section 5) show that Chatbot Arena's ranking highly sensitive to the distribution of LLM pairs. For certain correlated distributions, the gap in usability could be unbounded (Theorem D. which is concerning since Chatbot Arena adaptively oversamples new and highly ranked models.
These findings suggest that current leaderboard rankings may not fully reflect true model quality. Could alternative aggregation rules, such as Maximal Lotteries or the Copeland voting rule, provide more accurate assessments of model usability and be more robust to the choice of sampling distribu- tion? Does adaptive sampling introduce systematic biases that exacerbate the distortion of current pipelines? Addressing these questions is important direction for future work ensure the fidelity of Sraderboard-basee evaluations.
C Linearization Lemma for Expected Win-Rates
Lemma 1 (Linearization of Expected Win-Rates). Let L == d'(0) = 1/4 and la == -(8)-
3
23 L+e-#- For any pair of alternatives y, E A, we have
--
B. . (fg AvgUtil(r)) - L. AvgUtil(y)) S p( > y) 5 (L. AvgUtil(a) - l. AvgUtil(y)).
Proof of Lemmal 7 We prove this lemma by linearizing the sigmoid function ((2) = I+f = in the domain of 1-, 3). When [0, ]. the sigmoid function is concave and increasing, thus we have (=) < o o'(0) + (0) = + Lz, where L 1/ is the derivative o'()). When = E [-3,0] Oj.
the sigmoid function is convex, thus we have azx) - (1 + (0) --(-9) = 2 + L4 2, where
lg (9) 1 is the slope of the line connecting (-8, ( and (0, (0))
Plugging the above bounds into a (B (u(x) u(y))) ) we have that
8. (0.(w(z)) (u(x) - u(v)))
S B (u(x) u(v)) (L lu()) + 44 (u(x))u(()<())
I B (L ulz) - 11 u(v)).
23

---

Finally, taking an expectation over u ~ D, we have that
p( v) 2 S 3 L.
E [u(x)] - 1p wnD [u(v)l) = (L AvgUtil(z) - Lg AvgUtil(y)), u>D
This completes the proof of the upper bound. The lower bound follows from applying the same argument pyy > 2) and using the fact that p(r y) p(y > z).
D Finite-Sample Convergence Bounds
In this section, standard concentration techniques derive finite-sample convergence bounds for the normalized Borda score and the empirical win rate. The lemmas presented in this section will serve building block for proving finite-sample guarantees for the alignment methods studied in Sections a
D.1 Estimation Error of Win-Rates
Lemma 10. For any instance D with any number of alternatives m, any distribution p over alter-
natives with Pmin miD u(x),, and n i..dd. users sampled from D where each user labels d
comparison followinn the Bradley- Terry model with temperature 3, we have that with probability
at least 1 - 5 where 8 2 m² exp
(-
ndp
the empirical win rates pn pn( 8) == #( #(yzz)
#1 M)
satisfies that:
(n > v) p(u > v) s0
log(m//8 n min d "miin np
log(m/6)
Vx, E A,
Proof of Lemma 10 We first bound the estimation error of (n > y) for a fixed pair x. E (2) Here assume A y without loss of generality, because the estimation error for the x y case 0.
Since each voter i E [n]] is asked to label d pairwise comparisons, if each of them are asked to label pair {x, y multiple times, their answer will be consistent. Therefore, we can equivalently rewrite the process of sampling (2 y) as follows:
1. Draw ki,....k, kn Binomial(d, q) to represent the number of times the i-th voter is asked to label (x,z), where q = (p(r)p(y) is the probability that each comparison pair is {xx y}:
lid. 2. Draw Pi,...,Pr ~ Bernoulli(p) to represent the preference of the i-th voter on pair {as y). where p = p(a > y) is the probability that a fresh voter prefers x over y. In particular, we have p. 1 K2 because the sampling of voters and comparison pairs are independent;
3. Each voter E [n]] contributes K; to # [x > y) and K; (1 p.) to #(v > x).
As result, the empirical win rate pn > y) can be rewritten as:
# > y) Pn(x > y) # y) # x))
kipi
im k;
n
The eтror term is then given by:
kipi
Dn siml
1 hi ki - p) Σi Rv
Pa(x > y) p(x > v)
Now we use Bernstein's 's inequality to bound the numerator. We start by bounding the variance of
random variable Z, := k; (p: p). Note that E [2,] E [Kt]]
[p- pl because k; and pt p
are independent. Therefore, we have
Var (2,)) = EE |z?] IE k
(p. p) < IE [ = Var (ke) + (E [k:])² dg - 9) + dlg.
24

---

According to Bernstein's 's inequality, we have that with probability at least - 8,
Σ
Z
(ps p) V22nddg(1 9) log(1//)))) +3d1og(2/0)
Now we bound the denominator. Note that I [k-] = dg and Var (kx) = dg(1 - g). From the Chernoff bound, we have that with probability at least 1
nda
72 [g
ndq
(4)
2
Combining the bounds Equation and Equation 4 we have that when 8
with
probability least 1 26, for fixed pair 2, E A, we have
(x > 3) - p( > v)1 2m( 9) + d² log(2/8) + 3dlog(2/6)
ndq/2
(1 - q dq) log log(1/8)
log(1/0)
ndg
ng
where we use the fact that 1-g+d9
dlg and q 2p(x))(() 2 Pimin to obtain:
dg
0o (1
1o/(1/6) log(1/6) min f1, d, pain mp
Finally, by union bound over all (7) pairs, we have that with probability at least where
8 2 m² exp ndpuai the following holds simultancously for all x, E A:
( log(m/6) + log(m/6) Pala - y) p(æ > 8)1 00 mnn d pp n4
The proof is complete.
D.2 Estimation Error of Normalized Borda Score
Lemma 11. For any instance D with any number of alternatives m, any distribution over alter-
natives with Pmin min p(x), and n i.id users sampled from 'D where each user labels comparison pairs, the normalized Borda score BC,(z)) of any alternative A satisfies that with
probability at least - 8 where 8 > 2m exp(
uddaain
(V
Vx E A, BBC, (z) BC) s
log(m/0)
m log(m/0)
(5)
n- min d p
TPmmn
where (x) is the limiting normalized Borda score of candidate x, defined as
BC* = Σ m(v) p(x x y) = 2 [uxx) + Σ p(y) p(x > v).
(6)
VEA
Mafa
Proof. We first bound the estimation error (.) (x) for fixed alternative A. For notational simplicity, we use T,, (z) to denote the number of comparison pairs involving I, and (z) denote the number of comparison pairs where is the winner, i.c..
(x) (x > x)) + Σ #(x v) #( x)), Wa(x) #(x x x) + Σ #(x> v).
25

---

The normalized Borda score of r is then given by BC,, (α) W.(m) T.(())
It is then easy to see that
E (x)] nd
2u(x)2+ + Σ 22(x))(())
2ndp(xx);
((())n())((>>> 1)) ndu(x)
((ltt) + "Euo)o(r v)
E W (x)) nd
(xx))
Σ
The limiting Borda score (x) is then given by the ratio of the above two expectations, i.e.,
E [W (x)
(C)
2u(2) + Σ
"())p(x 8).
[x)
We can thus decompose the estimation error [BC, (x) BC (x)l as follows:
(x.
E [W.. (1:)
[BC,, (x) BC BCT(2)) (x)l
(x)
[T)]
(x)(x)
E [w)(
([W,(())
(x)x) (x)]
(T)
E TT (x:)
BC (c)
(w. - E [W
(T. - E (x)]
(n(x)
(x)
Now we bound the two terms (w, E [=.())]] and (x) E [Tn())] separately, and apply the union bound at the end.
write bound the deviation |# (z > v) - E (1 > y) using the same argument as in the proof of Lemma 10 Specifically, we write #(x > y) as
(I) Bounding [W, - E [W,())] For each y *
of i..d. random variables kap; where k; Binomial(d, 9x.y) and P; ~ Bernoulli > y)), where (x.y = (p(x) the probability that each comparison pair is {x, v). Therefore, have
Var (kspe) Var (ks)) Var (pz) Var (ks) E [pt] + Var (p:)
2dq
2z.u + dqn.u)
we can further bound the variance as since qu + dq S min(1,d min(1,dm2...
2d9x.
2dqx.x
2(d9z.p)
8(du(=))(y))
min 1, du dp
min(1, 1n, dp
Thus, by Bernstein's 's inequality, with probability least 1 8',
#(* v) - E (z > 2II| 4dp(z))(z))
n log(2/8") min(1, d p + 3dlog(2/8').
the other hand, for the comparison of x with itself, we have that #(x x) Binomial(nd, u(x)²). Therefore, with probability at least 1 - 8',
#(x > x)) E [ > 2>) / (2ddu(x) (x) log(2/8") + 3dlo/()
n mlo((200')
< <ddu(x)²
3d
min m
26

---

Applying union bound over all the m alternatives y E A, we have that with probability at least 1 m8..
(x) (e [[W(()]]] Σ
#(x 2) (1 w)]
n logg(/88) + 3d min d M
Adu(z))(o))
n nlog(2/8")
4du(z))
+ 3md
min(1, d m
(II). Bounding (T) [T, (z)] :
We can write (x) as sum of i..d. random variables:
Ta =
E 11 1 + 1/-=
Since each comparison pair x ve is sampled independently from μ x J4, we have that T, ~ Binomial(2nd, (zx))) Therefore, with probability least 1 - -
TT(x)) -E [T)())) - 2 ndd(()) 1og(2/8") + 12g(2/8)).
In addition, with probability at least exp( ndd(l)), we also have
E [T,] ndu(x))
Ta 2 2
(II.. Combining the two bounds: Finally, combining the above bounds [w,(x)) E (+)
and (T) - (x) l. together with the bound on the denominator (x), we have that with
probability least 1 2m8' exp(- ndu(a))
BC)) (x) [Wn(z) E (w)1
(x)x) - E (+)]
(x
(x
log(1/88)
du(x))
+ md log(1/8') + Vndu(r) log(2/8")
ndd(()
min(1,d d p
log(1 (1/8))
m log(1/8")
V min d d p
71/mnn
Finally, setting 8' =
2mp and taking a union bound over all the alternatives r E A, we have that
when 8 2 2m exp(- nddgiin) with probability at least 8, the above bound holds simultaneously for all x E A. This completes the proof.
E
Supplemental Materials for Section 3
E.1 Upper Bound for Borda
Theorem 2 (Borda Distortion Upper Bound). For any instance with any number of alternatives m,
distribution over alternatives, and temperature 3, Borda has most distortion ( O In the finite-sample regime, we have that
T-c
AvgUtil,, (Borrd),
- max, AvgUtil(**) -0 T
log(mn,3)
log(m)88)) 14 Minn
memin T.
Proof of Theorem From Lemma II
we have that with probability at least 1 1-66 6. all x E A satisfy that (x), BC (x)) S (n,)()), where
( = 0 (v
log (og(m/)) n- min m (1, d m
m log(m/0)
nfmmin
27

---

Following the proof sketch in Section 3.1 we use 2 = argmax, BC, to denote the Borda winner, and argmax AvgUtil r) denote the true welfare maximizer.
Since BC, (+) 2 BC, (x=), we have
(+) - (C*(x") 2 - (
For the limiting Borda score (z), the argument in Section 3.1 shows that
BC (2) BC (x*) S B (L AvgUtil(a) Eg AvgUtil(x**) (L -lp) AvgUtil(u))
La
S |3 AvgUtil(a) bg AvgUtil(z*))
(8)
Therefore, Combining Equations and (8) we have
L Eg
63
AvgUtil(x") 26 E
22)n, 53 3.
AvgUtil(
Eg AvgUtil(**)) AvgUtil()) 2
(T.
313
Combining this with the failure probability 5 of the above argument, the expected social welfare AvgUtil,, (Borda) satisfies that
((4)
AvgUtil(z*) 20 En.(())
(Bodda), 2 (1-6)-
B12
8g T
AvgUtil(<*) - o (Enald)
EB
[2g] 2
>
+ 8.
3
I
T
Finally, we set the failure probability to
6 θ
P. V min d p
(which satisfics the condition in Lemma
for large n1), we have
Cg T.
AvgUtil((*)) - -0 32
log(mn3) min (1, dp min)
m log (mgg))))))) B pmin
AvgUtil,, (Borda) >
which completes the proof.
E.2 Lower Bound for Borda
1.5
1.25
NLHF/Maximum Lotteries
RL RLHF/Borda lower bound
0.5
Figure 3: Comparison of the distortion achieved by NLHF/MMximum Lotteries and the lower bound on RLHF/Borda in Theorem 5 both as a fraction 3. The figure illustrates that NLHF has a worse distortion for every value of /3 (for worst-case distributions μ); in particular, the distortion of RLHF for large 3 is at least 3 - o(3), whereas the distortion of NLHF is 3/2 + o(3).
28

---

Theorem 12 (Lower Bound for Borda; Formal Version of Theorem 5
For any 3 > 0 and m 2 3, the 1- Borda voting rule (and, hence, RHLF) cannot guarantee distortion better than maxo< I-e--
(1 1 a(82)-1/2). This bound is strictly higher than the voting-rule independent lower bound 1tee 9 T----B for all 3 and at least (1 - o(]) 3 as 3 + cc.
(33)11/2
Proof of Theorem 12 Without loss of generality, may assume that 3. If m 3, we can repeatedly "split" some alternative x in two new alternatives y. y (where each user has the utility for y. 1/ as for the original alternative z, and (v() + =uy') is equal to the original mass of in (1). In this operation, the social welfares and Borda scores of y: y/ in the new instance are equal to the social welfare and Borda score of in the original instance, and the social welfares and Borda scores of all other alternatives do not change.
For any 0 0< < 1, < é' <1-6 c, and 0 < <y < 1, consider the following distribution D of utilities over alternatives (a, b, c):
(1 7.1,) with probability PA o(Be)-1/2 (()(
u(c)) = (1,0,e)
with probability pB == PA a(9)
11/2
(0,0,c+c))
with probability 1 PA PB-
One verifies that 0 PA. PB and PA + PB 1, so this describes valid probability distribution for all e, E', y and each type of utilities has positive probability of being drawn. Assuming that e' = 0, must be true that p(b > c) 1/2 p(c b) because
PA (3(1 - 0)) + (1 - PA) (8(00 c)) = Pa (o(3) - o(- ) + (-33))
=1-o(3e) =1-o(08)
= =P . (o(3) (Be) - + - (3E)
= 1/2 +1 - 1/2.
e > 0, it must be the case that p(c > b) > 1/2 by monotonicity, A similar chain of algebra shows
that p(a > 6) = 1/2 = p(b > a):
PA (- + pB (B3 L-PA-PB
+PB (o(3) +1/2 1/2. PA (o(-3)) 1/2
=1/2-a(B-)
-Px-(((8))-1/3)
For any 7 and positive c', note that, as the number of samples goes to infinity, the Borda score of the alternatives concentrate around their expected values:
1
BC(() -
2 =m(a) + - ((b) + p(a + m)
1
BC(b) - z u(a)) + (u(() + r(b x c) p(c)
BC(c) > p(c x a) p(a) + p(er x b) m(b) 2 _((c).
Recall that p(c > b) > 1/2> p(b > c). Regardless of what p(a > c) = p(c > a) may be, for any distribution μ with small enough plaa), plc) (and hence large jub)),, the expected Borda score of e will be strictly larger than that of a and b. By concentration, for large enough n, the Borda voting rule will almost surely select e as the winner, and the Borda's distortion for that f will be at least
max=e AvgUtil(z) AvgUtil(a) AvgUtil(c)
PA (1
PB
AvgUtil(c)
PB + (1 - PA PB) (c+e))
We can now derive lower bounds on the distortion of Borda by defining sequences of parameters e' y (and implicitly, sequence corresponding distributions μl), and considering the limit of Eq. (9). In each such sequence, we treat 7 as a fixed parameter, but let e' == e² and letting go to As + 0, it holds that PA - (because its numerator a(3c) 1/2 + 1/2 - 1/2 = 0), that PB + 0 (since it is constant multiple of PA), and hence both the numerator and denominator of
29

---

Eq. 9 converge to O. We apply I' l'Hôpitll's rule to determine the limit. Treating PA and PB. as well as the numerator num and denominator den of the equation as functions in e, we observe that
(0) 4. (0(3) 1/2)
3 (0(07) 1/2)
Pn
4. (0(3)- - 1/2)2
(1 - ((8)) 1/2
num (0) 4 (o(3) - 1/2)
o(3) - 1/2
den' den'(0) = 1+ 1 (0) 0+ PA( PB(()) (1+ 0) +0 (-P(((() Pa)(0)) 1.
Hence, the limit of Eq. (9) is
num' (0)
8
- $1+e* e 1/2 11-e- e-B
(1-9+ o(37) 1/2
1 1
den't (0) 110
( 1/2 (10)
which means that each 0 < 7 < 1 yields a distortion lower bound for Borda that is larger by factor
d(3))-1/2 than our algorithn-nndependent lower bound/the upper bound achieved by of 1 - + 172
NLHF. Since this factor is strictly concave in y and is equal to 1 for - 0 and + 1, any value of
Y will lead a strictly higher bound.
The value of y that maximizes the bound in Eq. 10 is >- = arctanh (V1- 0 -- /2 8
which
we used to plot Appendix E.2 Since the resulting expression algebraically unwieldy, we consider the weaker bound for 1+g(8+1) which yields
8 +
log(3 B + 1)
1+1/18-1) - 11/2
= = -1--00 =1-o
2
1 --
B
(B) 1/2
++1 us 9-+00
B
E.3
Algorithm-Inndependent Lower Bounds
Theorem 3 (Voting Rule-Independent Distortion Lower Bound). Fix any B > 0. Ifffeach user provides
d=1 comparison, no voting rule can guarantee distortion better than & 1+e-2 user reports 2 2 pairwise comparisons, any voting rule that puts at most 1/m probability mass on Condorcet loser must have least the above distortion.
T-e-R for large m. If each
Proof of Theorem 3 To prove this distortion lower bound, we identify a family of social choice problems for which the distortion of any such social choice function converges towards the claimed bound. We will parameterize these instances by the parameters m 2 2, 0 < e I 1/2, and I & < The instance has alternatives labeled a, bi...,, bm- b......,mm.... The distribution D is such that agent i ~ 'D has utilities
(Be) (1,0......0 0) with probability (u=(a), (b(b)) ..... (b EE,
(8)+
with probability
033)1122
(()+
Since the by alternatives have the same utility for any agent, any agent asked to compare two of them will prefer either one with probability 1/2. When 1, randomly drawn rater will prefer alternative a over some alternative by with probability
- 1/2
((3) 1/2
( o (3) o(3) + a (3e)
((-3e)
- (())
-(1 /B3c)\/2
( + ((E
x(8)/2 ( 1/2.
a(8) + (Bt)
30

---

It is easy to see that the probability of a random agent preferring over bj is monotone decreasing in o(Be)-1/2 and the social welfare of any by is fc (())+ Ç. The social welfare of is clearly ((8))a((e))1
a(8)-1/2
Fix a voting rule f. If each agent only provides single pairwise comparison, the voting rule simply observes n independent Bernoulli samples with bias 1/2. For any number of samples n. denote by Ps the probability that alternative x will win, where the randomness is taken over the realization of these samples and the randomness in f. By the pigeon-hole principle, some alternative z must be chosen with probability at most 1/m for infinitely many n. Without loss of generality, we can assume that this alternative is a (otherwise, simply permute the roles of the alternatives, which does not change the distribution over observed samples), and we restrict our focus to just the n where pa S 1/m. Now, the expected social welfare achieved by f is at most
- (vgUtil(a) + AvgUtil(b,) 1/m ( + + (o(B) - 1/2) a(8) (Bc)- -1
This shows that the distortion is at least AvgUtil(a)
a (Bc) - 1/2
(=(a(0)-1/2) a(8c)-1/2
2 1/m (B((B) 1/2) ge. (o( 1/2)
(11)
AvgUtil(f)
For sequence of social choice problems in which m + 00, 6 -> 0, and & = 1, this term converges towards
(o (0+ (o(B) 1/2) lim l (-00ppp11773 ) (0(())
4 -1
B 1
2 11---
where the first equality follows from I'Hôpital's rule and the Taylor approximation a(1) 1/2 1/4 + ((1)), and the second inequality follows from the identity (1) 1/2 = Ite-? - 1/2
2-1-e-1 ((1+e-1)
I-e= This shows the claimed bound on the distortion of any voting rule. Itc-r-
If each agent may provide several pairwise comparisons, the above argument does not work for all voting rules. The reason is that the correlations inside agent's ss comparisons might lead to nonzero covariances that might allow an (arguably unnatural) voting rule to distinguish the special alternative a. If the voting rule satisfies some natural social-choice properties, however, the lower bound above goes through by just slightly changing & away from 1.
Suppose, first, that the voting rule satisfies the probabilistic Condorcet loser criterion, i.c., it will never put more than 1/m probability mass on a Condorcet loser if one exists. If g > 1, a random agent prefers over by with less than 1/2 probability. As result, as the number of samples grows large, the probability that a is a Condorcet loser with probability converging to 1. Hence, f cannot put more than 1 m probability mass a, and the distortion lower bound in Eq. 111 holds. If g approaches 1 from above as m + oo and > 0, the distortion bounds converge to the same limit.
In the lower bound above, the probabilistic Condorcet loser criterion can easily be replaced by other axioms. If, for example, the voting rule is guaranteed to put at least 1 - 1/m probability mass on Condorcet winner (if one exists), the proof goes through if increase only 62 's utility by factor
& L I.
F
Supplemental Materials for Section 4
F. Upper Bound for NLHF
Theorem 7 (NLHF Distortion Upper Bound), For any instance 'D and any m. data distribution p. temperature 3 of the Mondlyy-Terry model, and any reference policy The and KL budget T, we have In the saite-sample regime, we have
dist(NLHF) < g 1+e-8
7 T-c-0.
AvgUtil,, (NLHF) 2 (3
1-e-a) 14e b) max, (F.J) -
log(mn))
+
(og(m))) n-
r-min (1, d=p2 Pain
min
Proof of Theorem 7
We prove this theorem by leveraging the convergence of empirical win-rates in We first condition the following successful event, which, according to Lemma I0
Lemma 10
31

---

holds with probability at least - 8 over n. samples of preference data,
Ve, y A, (p > y) - p(x > 8)y SO (v
log(m/8) min d minin
log(m/6)
= en,(
my
As argued in the proof sketch, the NLHF policy by definition satisfies
argmax min TIEB, m. (Krm)
Berwe [Pn > x2) - (m > zı)],
where Po (x) > x2) - (22
> œ1) describes eaashhquilibrium strategy for symmetric two-player (B(ee))). it must hold that
zero-sum game, and thus have value O. Therefore,
5 E
21 MI 3amm [pn(21 > x2) Pm x1)]=
E
[2pm(x1 > x2)
21
Since [Pm (2 > v) - p(æ > f)1 S ( we have [2p(21 > r2) 1] + 25 n
E
According to the linearization lemma (Lemma]) D.. we have
E
[23(L. AvgUtil(z;) lg AvgUtil(za)) + 2
THUUE
< 23(L AvgUtil(TTLHHE) la AvgUtil(**) En,a(0)
B
Therefore, under the successful event, we can lower bound the welfare of the NLHF policy by
AvgUtil((TNHrF) AugUtil(***) 4En,(0)
B
Taking the failure event into account, the expected welfare of the NL.FF method least
AvgUtil,, (NLHF) 2 (1 - (4 AvgUtil(**) - 4Ena(0)
3
2 AvgUtil(7*)) - -0 ( L
Eg
Lg
+ 8
3
T
Finally, choosing 8 =
/.l ) we have
Lg AvgUtil(**))
log(mn) min (1, d 2
log(mn)
2
n 1-ppp
This completes the proof.
F.2 Lower Bound for PPO-based RLHF and DPO
Theorem 6 (RLHF Distortion Lower Bound), For m 2 3, there is sequence of alignment problems on which the distortion of RLHF scales as (B) in 8.
Proof of Theorem Suppose that the instance has m alternatives A = {a, b, c1.... Cm Cm-2) }. where m-2 2 4e Let the data collection distribution be uniform over all candidates, i.e., lr = Uniform (A). We consider the following distribution D over utility vectors, such that the utility vector of random agent i ~ D satisfies
(u:(a), u;(),, ui(ci), .... (c(Cmm=2) (0, 10,1,0 ...0......) 0)
(type with probability 8,
0, 1,..,.....11 (type III with probability 1 1-8, 8,
where 8
O P). In other words, type users have strong preference for candidate b but only constitute fraction of the population, while type II users have strong preference for and weak preference for a > b and make up for a 1 8 fraction of the population.
10
10+e2
For the reference policy and the KL budget, we set (a) (br 1-c and )er((c m-2 for 2
all i [m --2 2]. We leave the choice of & to be determined later. The KL budget is set to be 1.
32

---

Analysis of the MLE reward. Now we show that when - oo, the MLE reward satisfies r(b) r(a) > 0. According
46 it suffices to show that limn- (b) BC, (a) >
which, by Lemma 11 is implied by BC (b) BC (a) > O.
We have
2 (p(b - 4) - p(a > ci) (o(b x a) - -p(a x b))
BC (b) - BC (a)
Σ 1=1
m
For each C₁ we have
p(b ca) p(a > 63) 5- (0 - + (1 - (1 (o(-3) - (o( -3)).
In the above equation, the first term accounts for type-I users and is lower bounded by & when 3 2 2. The second term accounts for type-Il II users, and we leverage the fact that (xx) is concave when x 2 0 to bound it as
e² = 8. (o o(3 11) 2
e 8 o'(3
(1 (o(-3))
e 8, 10
10
10
where the last step uses (z) (zx) (1- (x)) s 1 (zz) S e for all x. Plugging both bounds into the limit BC* (6) - BC (a) and substituting = To+e3
2 m- 2
20 gives
lim B PL-00
BC Ba)) 2
2
8 (5
e
-
1
1
m
m
m
Therefore, when n sufficiently large, we have BC( > BC(a) with high probability, which implies that b is has higher MLE reward than a.
As for the MLE reward of type-c candidates, since BC* (c:) (C²(c)) for all i, [m 2]. have jax (emm2) 2] (r(c)) r(c,)) + 0 when n + cc. In the limit, we can treat all type-c candidates as having the same reward.
Analysis of the KL-constrained policies. Since all type-c candidates have the same estimated reward and the same probability under the reference policy, both x and RRLHF will assign the same probability to all type-c candidates. This can be seen by the equivalence between regularized and constrained RLHF as shown in Appendix [F.4 As result, we can view all type-c candidates as a single candidate e which have mass under the reference policy.
We now show that for any 1) > 0, there exists an E > 0 such that any policy и E A(aa,, b)) inside the KL ball B, (TT)) cannot put more than 17 mass on c. We have
(a)
T(b)
+ T()) log x(c)
1 2 (TT || )e))) = x(a) log (1 - e)/2 + +(b) log
(1-
Fixing x(c), the KI. divergence is minimized when (aa) = x(b) = 1- [(c) KL divergence, we get
Substituting this into the
2
2 (1 - (1-x(c)) llog 1- 1-((c) E
T(c) E
+ (c)) log
Since / log! 2 -1/e for all
> 0, and log
--c 1 > 0. we have
2 T(c) log
Therefore, any policy in the KL ball must satisfy T(C) log 1 S 11+ 2/ee < 2, which implies that T(C) log(//5_ We can choose to be any constant smaller than e 2// to ensure that ((c) I 17.
We then show that when 7 is sufficiently small, TRLHF puts almost all probability mass b, whereas rt puts almost all probability mass on a. This will ultimately lead to a distortion of
AvgUtil(=*)) ((AvgUtil(a)) 0(1/3) AvgUtil(fRLHF)
e O(AvgUtil(b) O(e-8) = 2(0)
33

---

For TRLHF, we assume that the estimated reward is shifted such that r(c) = 0 (as a result, r(a) < r(b) 0). Since n' (0. 1. 0) also satisfies the KL constraint, we have ((TRLHF) 2
r(a²). Together with the fact that TRLHF (c) S 7/, we have
((x') r(b) S r (TRLHF) r(a) (RLH) (a) (R))TTLLFF())
S TRLHF (a) (r)) + TR)HF(A) 17) r(().
Therefore, have TRLHF(() (a) S " [(()) [a]] Setting be sufficiently small, we can guarantee that
[r(]]
S 11 1+
(12)
[D)
[(b)-r(a]
and thus (a) + (C) < AvgUttl((TRLHF) = @ (AvgUUti(()).
[r(6)]
S P.P. As result, we have
[r(b] [r(]]]
For n², a similar argument shows that when
1 122
AvgUtil
(13)
AvgUtil( AvgUtil(B)
We have n (T(b) + n (c) S Se As a result, we have AvgUtil(**) @(AvgUtil(a)))
Finally, we set e to be smaller than e mi) such that Equations 12 and 13 are both satisfied.
This ensures AggUtil(zt)/AvgUUi((TTRHHHH
((() and completes the proof.
F.3 Equivalence of DPO and RLHF under Heterogeneous Preferences
In this section, we formalize the observation that DPO and RLHF are equivalent under heterogeneous preferences. This is consistent with the result by Shirali et al. with the Borda count. We start by recalling the DPO objective
45 which shows that DPO also aligns
π (xx()
π T(/))
(TPO(TT; Teet)
Σ
log
Blog
3 log
[ee((r)))
Teer(y?)
ISiSn,ISisd
Now we perform a change of variables to transform into the following form: T(x)
(x) = <<)(()) exp(f(x)/3) where f(x) = .log )
Vo E A.
Substituting this into the DPO objective, we get:
CDeo(IT: neet)
Σ
log (o(((x;)) f(y 1)).
Isis
which is exactly the MLE objective for reward learning in RLHF, repeated here for convenience:
LMLE(T)
Σ SiignISiid
log (a(r(x))) r(x()))
Therefore, there is one-to-one correspondence between the MLE reward
argmin,er" (MLE(r) 13 and the DPO policy TDPO argmin, LDPO (T; Tyer) as:
TDP) = <er((>) (x)pr"(xx/BB)
On the other hand, the RLHF policy with regularization parameter À (see Appendix R4 for the equivalence between regularized and constrained versions of RLHF) is also given by
TRLHF (z) = π exp(r" (z)/A). ex)(r"())/A)
Therefore, the DPO policy TPP and the RLHF policy TRLHF are equivalent when the parameter / in the DPO objective equal the optimal policy "' Weef exp(AvgUtil(<r)/X\ (for potentially different X' that make the KL constraint tight) as o AvgUtil, which has also been pointed out by Shirali et al. [45]
the RLHF objective. Notably, both policies are different from
Note that the parameter does not need to be the same the true temperature of the Bradley -erry model our setting.
13 Note that we have minus sign in the MLE objective, which is equivalent to maximizing the sum of log-like liielihoods.
34

---

F.4 Equivalence of Regularized and Constrained Alignment Methods
In this section, we formally establish the equivalence between regularized and constrained formu- lations of both RLHF and NLHE. Although this equivalence is standard and likely known to many, we include the details here for completeness. We begin by proving the equivalence between the two versions of NLHF (which involves max-min optimization over the policy space); the corresponding result for RLHF then follows by analogous arguments.
Proposition 13 (Equivalence between Constrained and Regularized NLHE). Let n, be the output of the r-constrained NLHF method defined in Section 2 i...
argmax T,EB, (Tig) 12 B. (Rra) 11
min
[M1
(14)
and let x be the output of the >-regularized NLHF method [36]. ie..
x = argmax min Ti EMMMM (2E MI To
[M
(xI( || The)) + X Dxu Tnd). (15)
Then, for each X E [0, oo] with solution for Eq. 15 we have that 7 also an optimal solution to the r-constrained optimization problem in Eq. (4 each 2 0 with solution πt for Eq. 14). there exists À E 00 2o] such that कy is also an optimal
where T (x ( Tag). Conversely, for
solution to the X-regularized optimization problem in Eq. 15
Proof of Proposition 13 We start by observing that in both games Eq. (1) and Eq. 15 the utilities are anti-symmetric functions, and the strategy spaces for both players are identical, convex and compact. Therefore, the value of the both games is O, and both games have symmetric Nash cquilibria.
Now, we prove the two directions of the claim separately.
Regularized = Constrained. Given À E [0, oc] and ΩΛ be the solution to Eq. (5).. Consider the constrained optimization problem in Eq. (14) with DxL. (#x Teeer. ) We show that 22 #, is best response to क # in the constrained game with radius DRI x Tret), i.e.
カ
argmin
E [Ma
(16)
If Eq. (6) holds, then by the fact that the utility is anti-symmetric, we have that # is also best response to π2 = iT in the same constrained game. Putting both together, we have that (#x, 7x) a Nash equilibrium for the constrained game with radius (#x Tret), thus establishing the first direction.
Now we prove Equation 16). To see this, note that Vnz (- we have that DKL || Tre)) S T
DKL(ft (fx mett). Therefore, from the fact that n is Nash equilibrium for the regularized game we have that for any π2 E A(M) and specifically
Eq.
15
B, (Trer), we have that
E 2a
[Men
+ X- (TL lI गe))) 2
=A [M + DKL ( (ett)
E
E
[Mayzzl
E
[M
2 X (Del (#x ll meet) DKI(mT (rer)) 2 0.
21 21 A
This proves Eq. (16) and completes the proof of the first direction.
Constrained + Regularized. We prove the reverse direction using duality theory.
We first show how to construct the regularization parameter X. For simplicity, write π. M. as a shorthand for Ery [Mz Then minimizing player in the constrained game Eq. 14 with Ti n, can be written as
min n, M12 s.t. DKL(Te]lTae) S T, m
0,1 1.
(Constrained Minimization)
The Lagrangian of this problem is
L( f).)) = =T. + ( -) --i m2 + m1 m2:
35

---

where X, 1 2 0 are the Lagrange multipliers for the KL divergence constraint, the non non-negatvvity constraint, and the normalization constraint, respectively. Since the utility कं Mrr convex, the normalization constraint is affine, and the inequality constraints are convex, and the reference policy Tee strictly feasible with DKL(T (Tierrr (et) = 0 r [+ the Slater's condition is satisfied, which guarantees that the KKT conditions are necessary and sufficient for optimality -iiiyyythrrr there exists
parameters X", 17", 17" 2 O such that as an optimal solution to Eq. (Constrained Minimization). T2 = R satisfies the following KKT conditions:
x, + +x Vx, DKL 1T + +12 1 0, V (,,, 1 n²) MJ
(17)
where
77 (1 T2 1) =0 and (T(T2) = 0, [m].
(18)
due to complementary slackness.
We will show that this x is the regularization parameter we are looking for. Namely, for the regularized game in Eq. (15) with À = X*, we have that (Tr Ty) is a Nash equilibrium.
Again, let us first fix 1 nr and consider the regularized optimization problem for the minimizing player:
min n. Mr2 - X DKL (T2 (aet) s.t.
T2 2 0, n22 02 = 1. (Regularized Minimization)
Since n.. M2 2 is convex in m2, Slater's condition satisfied for the above problem and implies that the KKT conditions are sufficient for optimality. It is also not hard to see that L( X", -T",, ,y") coincides with the Lagrangian of (Regularized Minimization). We can therefore conclude from Eqs. 17 and (18) that for the minimizing player in the regularized game, T2 Tr is a best response strategy to π TT.
Since the regularized game is anti-symmetric, the same argument shows that for the maximizing player in the regularized game, πi ,, is also a best response strategy to TT2 Ty. Together, we have that (Tr, 7r is a Nash equilibrium for the regularized game in Eq. 15) with À = >" The proof complete.
Combining Proposition with Theorem 7 we obtain the following guarantee for the KL-regularized version of NLHF:
Corollary 8. If X-rreuulariedd NLHF (for any X A 0) returns a policy #NLHE, this policy's average 3.1-e fraction of the optimal average utility of any policy т with DKL(T || Teet) S DxL( ll Trr)) (minus fnite- errors, see Theorem
utility at least a 3'I4e
For the RLHF case, the proof is analogous, except that we no longer have nested minimization- maximization, so the proof is slightly simpler. We omit the details of proof, but state the result below.
Proposition 14 (Equivalence between Constrained and Regularized RLHF). Let be the MLE reward learned from the comparison data, and let ग. be the output of the T-constrained RLHF method defined in Section 2 i.e.
argmnax E [r(x)],
(19)
TEB, (Trd)
and let गT be the output of the X-regularized RLHF method, i.e.
A argmax E [r(x)] - X DKI(TT Rnf).
(20)
REA(M) a-5
Then, for each X E [0, oo] with solution at for Eq. 20 we have that At is also an optimal solution to the r-constrained optimization problem in Eq. (19 where ( Tra)- Conversely, for each T 2 0 with solution т. for Eq. 19). there exists À E 10, 20] such that म. is also an optimal solution to the X-regularized optimization problem in Eq. 20)
"If r 0. the only feasible policy is mit, and the claim clearly holds for X = co. We also assume that Tier (a) > 0 for all a E M. Otherwise if (a) = 0 for some E M. then both the regularized and constrained versions forbid any policy put nonzero probability a, which leads effectively smaller candidate set.
36

---

G Other Sampling Models
To prove Theorem 9 alternatives in Fig.
we first prove the following lemma. We illustrate the constructed sequence of
0.51
0.52
0.55
0.53
0.5.
0.52
0.52
0.51
0.51
0.51
0.51
0.51
0.51
33
24
36
By
3g
010
B11
812
B24
0.33
0.44
4²
0.333
0.49
0.00
0.29
0.51
0.00
0.20
0.39
0.00
0.17
0.33
0.00
0.15
0.29
0,4
0.33
0.31
Sw(ad
0.27
0.2
9.10
0.28
0.19
0.38
0.35
0.14
0.0
Figure 4: Utilities for first 14 alternatives in the sequences constructed in Lemma 15| for B 5. Bottom bar chart shows decreasing welfare. Numbers between alternative labels 0r+11 + dg give the expected win-rate p(ac4 az).
Lemma 15. For any 3 O, there is infinite sequence a1; ...... of alternatives. and distribution D of utility functions over these alternatives such that
AvgUtil(a1) 1/3.
for all 2 2, < AvgUtil(a:) AvgUtil(ar-1) 3/3 log (1 tanh (3/4 AvgUtil(ar-1))) AvgUtil(a--1), and
for all 1 1 p(at x a--1) > 1/2.
Proof. Our population D will be uniform distribution three utility vectors, u', u² and u². We define the sequence of alternatives and prove the claim by induction over 2 1.
For t= 1, set u² (a1) = =²(aa) = (a)) 1/3, which clearly satisfies the first claim.
and suppose that we have defined the utilities for alternatives 01..... az-1 and established the claims for all t' < t. We define utilities for a, and extend the claims to t. Let u denote the utility vector among w², u² u² with the highest utility for a;-1, and denote the other two utility vectors by B C. For convenience, set A a (at-1) 3 and A' log ((
Now, let
A (ax) == u (ar-1) 0,
u ( (a.
"(aa) u (a.1))))/))
will be useful to derive an alternative expression for A':
(ea/2 1)3
A12 (c 2 + 1)3
A' log
log
2 (e +3)
2cA/2 /2 (e + +3)
2/2 ( +3)
A
log 1/2 + 1)3 + (c 1)3
log
2
(64/2 1)3
2
(6A/2 + 1)3
A
A/2 - 1
3
log 11
log (1 tanh( A (/443/)))))
2
c2/2
1/2_ 3 in the logarithm is greater than 1, we know that A' < A/2.
Since the value 1 +
37

---

Since AvgUtil((a-1) > 0 by the induction hypothesis, it must hold that A > 0, and, by expanding, that
(A/2+11) log 3 + (e-12 - -1)3
log 3 +1
A' = log
(21)
2 2 +3)
c² 3
c +3
Since log 30 +1
log
+3 0, it holds that A > 0 and that AvgUtil(a:)) > 0. 8++3
We first must show that we have not set u ((a) and (ar) greater than 1. Since, by the induction hypothesis, ((4((ay=)) + u² (a)-1) + u (ac-1)) = AvgUtii((a--)) I AvgUtil((a-2)) 1 ... v
AvgUtil(a1) = 1/3. it must hold that u (a=-1) + u (a + _ (a-1) S 1, which by the choice of u implies that n0 (a.-1), 1), r (a-1) are most 1/2. Since A < <//2 u (a.-1) -3/2 - 8/2. u (ar) = R (a:-1) + 3 3 - 1/2 + 1/2 = 1, this holds for uB, and analogously for u
Next, we show the claimed reduction in social welfare using our alternative expression for A'
= 1 3 (a<(a)))++ + u (a((aa))) + u (a-1)) A - A-2A. 22
AvgUtil(a:) (ax) + u (at)) - u (as))
2 AvgUtil(a+-1) 3
= AvgUtil((;-.)
log (1+ tanhh(/44))))
3
By our choice of U and averaging, it holds that u (ac-1) AvgUtil(ar-1) and hence that A > 3- (a; Since the bound on AvgUtil(a:) above is monotone nonincreasing in A, we obtain our claim that
AvgUtil(a.) < AvgUtil((a-1) 2
log (1 (1+ (1+tam) tanh (3/4 A )
3
Finally, it remains to show that p(a; x at-1) 1/2. Since
plac > a=-1) ((-A) + 2 1 (a( +2 - 1/2)
2
(1/2 o (A)) + 2 (o 1/2)
suffices to show that 2 (a(A)) 1/2) o(A) 1/2. Observing that (x) - 1/2 1 I+e-r and applying Eq. 21). we bound
1 A4
e
2 (o () >2 ( ((+111 -1)
36
364+1
1
4c044
e +1
3e
36A+1
1-E
= 2 1+e-3 = -A) 21
which establishes our claim.
Theorem 9 (Unbounded Distortion of RLHF Under Correlated Sampling). For any 3 > 0, there exists a sequence of aligument instances and distributions v E A (( over comparison pairs such that RLHF's distortion is unbounded.
Proof. We construct our sequence of instances by taking increasingly long prefixes of the sequence in Lemma 15 i.e., by considering the alternatives :1....;00 am for increasing m. Rescaling by some constants, we can define the MLE rewards in RLHF as
# > v) nd
log (o(r(x) r(v))) + #(U x) n d
T argmax TERm
Σ
log (a(r())-r(z)) r(z)))
(E.)
Following Siththaranjan et al. each alternative x,
46 we apply the first-order optimality conditions to obtain that, for
#( v) nd
#(x > v)
# ((((z) rry)).
32 d
38

---

By the strong law of large numbers, as the number n of samples goes to infinity (regardless of d), the sample fraction #(*>v) converges almost surely to its expected value ((x, v}) p(æ y). Hence, as n + oc, the rewards (a random variable depending on the random pairwise comparisons) will satisfy that
Σ ((l.,u))-or(())) r(v)) 25 Σ E((a, ut) p(a > y). Ma
(22)
Consider a distribution / over pairs of alternatives that assigns each pair of adjacent alternatives {ar, 0r+ } probability of L-f of being drawn for comparison, and all other pairs probability of
m-1 2 (m=-1) where >> is small value, dependent on the current m, be determined in the
following.
Applying Eq. 22 to x = Om, we obtain that 1-c (r((m(((m)) - (0) + (+)) converges almost I-c
surely to m-1 p(am am-1) + O(c). Since Lemma 15 guarantees that p(am 0m-1) 1/2, for small enough e, it will hold almost surely that a (r((m)) r(am-1)) 1/2, i.e., that r(am) > r(am-1).
Next, apply Eq. 22 to am-1, to obtain that 1 ( - r(am)) + ((((mm-1) r(am-)))) + (e) converges almost surely to m-1 (p(am-1 > am) + p(am-1 > am am- + (c))
Having established above that, for small enough e, we can make o (r((mm-1) - r ((m))
1
pm > am-1) we see that o (r((m-1) r(mm-2) must become arbitrarily close to p(am-1 > am-2) > 1/2.
(r((am) r(mm-1)) arbitrarily close to p(am-1 am)
Continuing this argument for x = 9, am-3:.... 01. we obtain that, for small enough e, the rewards will be ordered as r(a1) < r(a2) <... < r(am) almost surely. Set e (for this specific m) so that this is the case. We set the KI. constraint large enough that all policies are possible; say, by choosing the reference policy to be uniform and setting T log m [B Then, the reward-maximizing policy clearly puts all probability mass on the alternative Om with maximal reward, obtaining distortion of AugUsil(a1)
1/3
AvgUtiil (a..)
Avg
We have now defined sequence of instances, whose distortion grows as AvgUtil((...] as m + op.
1/3
To show that distortion is not bounded in 8, it remains to show that AvgUtil am) + 0. The lemma already tells that AvgUtil(a:) (for 1,2,...) is monotonically decreasing sequence. Since the social welfare is nonnegative, the sequence is bounded from below and thus convergent, which also implies that the sequence of differences AvgUtil((a-1)) (vgUtil(a:) must converge to 0. Since the bound 2 log(1 1 + tanh(3/ Boub(B//Avguuu (AvgUtil(aa--))" is sandwiched between these differences and O, it must also converge to O. Since it is continuous in AvgUtil(a,-1) and positive for all positive values of AvgUtil(a,-)) this implies that AvgUti((a.1)) must converge to This shows that AvgUtil(am.) + 0 for large m, and that the distortion grows unboundedly large as increases, which concludes our proof.
33
This means that this lower bound fits into the social choice subsetting, Note that the theorem does not apply Borda count (which is not defined for general distribution but RLHF considered as voting rule.
39


Reviews:
[{"review_id": "etuKeq1hKz", "reviewer": "Reviewer_DYaW", "summary": "This paper introduces \"distortion\" as a novel framework to theoretically analyze the performance of AI alignment methods when faced with diverse and conflicting human preferences. Distortion quantifies the worst-case gap between the optimal average utility achievable and the utility attained by a given alignment method, which learns from probabilistic pairwise comparisons modeled by the Bradley-Terry model. The research provides a comparative analysis of major alignment techniques, demonstrating that NLHF is robust and achieves the minimax optimal distortion guarantee of $(1/2+o(1))\\beta$. In contrast, methods like RLHF and DPO are shown to suffer from significantly worse distortion, which can become exponential or even unbounded in the general alignment setting that includes a KL-divergence constraint from a reference policy. Ultimately, the work establishes that a certain level of distortion is unavoidable, revealing a fundamental information bottleneck when relying solely on ordinal feedback from a heterogeneous population.", "questions": "See Weakness.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\nThe paper's findings are significant because they draw a sharp theoretical distinction between different alignment approaches. The result that RLHF/DPO can have exponential or even unbounded distortion under certain conditions, while NLHF remains optimally robust, is a powerful and potentially impactful conclusion. This provides strong theoretical justification for exploring alternatives to the current RLHF paradigm.\n\n\n\n### Weakness\n- RLHF results rely on a significant mismatch between the distribution of comparison pairs $\\mu$ and the reference policy $\\pi_{\\rm ref}$, the authors should justify this assumption on real-world problems.\n- The paper is entirely theoretical. While this is not inherently a weakness for a theory paper, the lack of any experiments means the practical implications of the distortion bounds are left to speculation. Empirical studies could help determine if the identified failure modes for RLHF occur in practice or if the constants in the distortion bounds (e.g., $\\beta$) lead to meaningful differences on real-world problems.", "was_revised": true, "final_justification": "I maintain my original score as weakly accept.", "rebuttal": "Thank you for your feedback and appreciation of our theoretical results. We address your comments below.\n\n\n> (**RLHF lower bounds**) RLHF results rely on a significant mismatch between the distribution of comparison pairs and the reference policy; the authors should justify this assumption on real-world problems.\n\nWe have 3 lower bounds on RLHF and not all rely on the mismatch between $\\pi_{ref}$ and $\\mu$. Below, we provide the intuition behind each construction and their practical relevance.\n\n- (1) Thm. 5 presents an instance where RLHF distortion is lower bounded by $(1-o(1))\\beta$  even in the unconstrained setting where proximity constraint to $\\pi_{ref}$ is not binding. For example, $\\pi_{ref}$ and $\\mu$ could both be chosen to be uniform in this case. This establishes a constant factor separation between the distortion of RLHF and NLHF.\n\n- (2) Thm. 6 shows that under KL constraints, RLHF distortion can grow as $e^{\\Omega(\\beta)}$. The constructed instance does indeed rely on a large mismatch between $\\pi_{ref}$ and $\\mu$. Of course, a worst-case instance exaggerates problematic properties of the instance to a severity that is unlikely to be encountered by chance, but we believe that the less severe versions of the same pattern may well arise in practice.\n\nOur constructed instance exploits that the comparison distribution $\\mu$ often produces a particular type of response, which has very low probability mass in the reference policy. In practice, this type may for example correspond to some form of instruction-following but harmful responses, which is not yet suppressed when the comparison data is sampled, but is suppressed by the reference policy ($\\pi_{ref}$) due to guardrails and supervised fine-tuning. More broadly, a mismatch between $\\mu$ and $\\pi_{ref}$ arises whenever alignment relies on off-policy preference data: for example, Stiennon et al. (NeurIPS’20, “Learning to summarize with human feedback”) sampled candidate summaries for comparison “from several sources including the current policy, initial policy, original reference summaries and various baselines”; other models are trained using pre-existing comparison data, such as the OpenAssistant [Köpf et al. NeurIPS’23] dataset in which candidate responses are written by crowdworkers, which also implies that the data distribution and reference policy may be quite different.\n\n- (3) Thm. 9 gives an unbounded distortion with correlated sampling models, where there is no single distribution $\\mu$, and the challenge is about correlations rather than different levels of overall representation of alternatives in $\\mu$ and $\\pi_{ref}$. Specifically, the instance constructs a sequence of actions and assumes that adjacent action pairs are more frequently compared than non-adjacent pairs. Milder forms of these correlations could for example occur if actions are sampled over time during the policy’s training (where the policy's distribution shifts from actions early in the sequence to actions late in the sequence over the course of training). This result highlights RLHF’ lack of robustness to non-i.i.d. sampling distributions, which again may be present in externally procured comparison datasets.\n\n> (**Experiments & Practical implications**) The paper is entirely theoretical… Empirical studies could help determine if the identified failure modes for RLHF occur in practice or if the constants in the distortion bounds (e.g., beta) lead to meaningful differences on real-world problems.\n\nWhile we agree that empirical evaluations are an intriguing next step of our work, we want to echo reviewer `mjbj` who writes that “asking for extensive empirical results would be outside the scope of the paper (the theoretical results are already compelling as they stand, and the experiments themselves would be expensive enough to deserve their own paper anyways)”. Besides the computational cost of experiments, the limitations of pairwise comparisons we show also mean that most post-training dataset, which typically consist of such comparisons, are insufficient for such an evaluation. For future work, we are intrigued by recent datasets [e.g., Kirk et al., NeurIPS’24] that include expressions of cardinal information and the rater’s identity. Using such data to evaluate models based on user utilities will require overcoming challenges about users’ inconsistent reporting of cardinal values and the low amount of preference data per user in the datasets.\n\nWhile our work does not include such experiments, our main contribution is to introduce and analyze distortion as a theoretical metric for worst-case robustness. Our work also carries lessons for the practitioner as described below, which can motivate insightful empirical studies:\n- **Limitations of reward models as evaluation metrics.** Our analysis shows that a model’s performance according to the reward model is a highly flawed measure of agreement with human preferences, and should not be conflated with average user satisfaction. Our results show that this mismatch does not reduce with increasing the amount or diversity of comparison data, but is a persistent bias due to information-theoretic barriers. Since (ordinal) comparison data is inherently limited in its informativeness about user satisfaction, empirical evaluations of user satisfaction should be based on users’ expression of (cardinal) preference intensity.\n- **Sensitivity to choice of post-training dataset**: Our results demonstrate that the reward-based pipeline of RLHF is sensitive to the sampling distribution over pairwise comparisons, whereas the reward-free method NLHF is more robust and analytically tractable. There is recent interest in using post-training data sets across models and platforms (e.g., Zhang, et al.. *“Cultivating Pluralism In Algorithmic Monoculture: The Community Alignment Dataset”*). Our results indicate that practitioners who use RLHF should be wary of lack of knowledge and control over how their data set was curated. As the community moves towards general purpose and public post-training data sets, there is even more argument in favor of using methods that are robust to the distribution of comparison data such as NLHF.\n- **Failure modes that may occur in practice**: As is common for any worst-case analysis, our lower-bound instances are stylized and chosen to be easy to analyze. But from a practical lens, we believe that these instances exaggerate patterns that may well occur in real-world examples (for example, that frequent pairwise comparisons between alternatives suppressed by the reference policy can cause RLHF to misalign on unsuppressed actions). Our theory allows the exploration of such patterns in a systematic way, based on which patterns have the biggest worst-case effect."}, {"review_id": "xaDFXC7TS7", "reviewer": "Reviewer_mjbj", "summary": "Consider RLHF as a way of aggregating preferences across a population. Then a basic question which this paper considers is whether current alignment methods such as DPO and RHF reliably lead to high average utility across users. In short, the conclusion is no: stochastic ordinal preferences don't contain enough information to ensure high average utility across a heterogeneous user population.\n\nMore specifically, the distortion in the case where there's no KL regularization is at least linear in $\\beta$ — that is, the temperature term in the Bradley-Terry model, which quantifies how deterministic user preferences are. When KL regularization is added—so that we're now considering standard ROHF or DPO—the distortion becomes exponential in $\\beta$.\n\nIn short, the paper presents a strong case that standard alignment methods will fail to respect the preferences of the average user, let alone minority users.", "questions": "The confusions I have largely concern what the practical implications of the work are (I found the theorems themselves clear).\n\n1. Suppose you had two users A and B, and use DPO to train a reward model R_mix over a 60/40 mixture of the two user’s preferences. Is it possible to classify R_mix from R_A or R_B (trained on each user’s preferences alone) using the lower bounds on the distortion (Theorems 5, 6)? That is, drawing samples from the original population (mixture for R_mix, A for R_A, etc), computing the sample mean distortion, and classifying based on those distortions. If so, this could potentially serve as a post-hoc measure of how heterogeneous the preferences are.\n2. The discussion in Section 5 seems to suggest that simply replacing KL divergence with some other regularization from the reference policy is insufficient to reduce the distortion. But what if multiple reference policies were used (e.g. different base models, or different checkpoints of the same model), and the regularization consisted only of the minimum KL from each reference policy? So long as no reference policy puts a tiny amount of probability mass on c (line 289) wouldn’t this improve the lower bound in Theorem 6?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nOverall I find the theoretical argument compelling: the assumptions stay true to the Bradley Terry model and properly incorporate KL regularization, and \\emph{lower} bounds on the difference of \\emph{average} utility are more compelling than results which only consider the worst case. \n\nWeaknesses:\n\nYet even after reading the paper carefully, I am left wondering what the actual implication for alignment is? I suspect that this is largely a gap in writing that could be addressed during the discussion period. For instance section 5 seems to suggest that the issue is primarily the presence of KL regularization to a single reference policy. Having a short section which very clearly states for alignment practitioners what the theory suggests should be different would greatly improve the readability of the paper. I think that in this case, asking for extensive empirical results would be outside the scope of the paper (the theoretical results are already compelling as they stand, and the experiments themselves would be expensive enough to deserve their own paper anyways), but \\textbf{the paper should at least make the question clear, enabling empirical follow-up research}.\n\nQuality:\n\nThe overall quality of the paper is high. The writing is clear, the notation is consistent with other papers on RLHF alignment, and Figure 1 adds a lot of intuitive understanding.\n\nClarity:\n\nI predict reviewers will be pretty divided on the clarity of the paper, depending on their background. Personally, I think it’s very well written given the subject matter. However, readers from a strong empirical background will likely struggle to identify the thesis, since it’s not presented in a typical \"Figure 1\" style with bolded performance results that beat a baseline. That’s why I propose including a clear section at the end (and foreshadowed at the beginning) that concludes with a precise prediction for an experiment in a follow-up paper.\n\nSignificance:\n\nI think the paper, even in its current form—lacking any crisp predictions—still manages to have moderate significance. It clearly argues that the burden of evidence should be on showing that RLHF or DPO are fair, given that we have every theoretical reason to believe they are not. The significance would be greatly improved by including a single crisp prediction that could be explored empirically, in which case I would raise my score.\n\nOriginality:\n\nTo the best of my knowledge, the bounds presented here are new.", "was_revised": true, "final_justification": "Authors articulated what the concrete empirical predictions are. Conditional on them adding that to the paper, I am raising my score to 5 tentatively (we'll see how the rest of the discussion period with other authors goes as well).", "rebuttal": "Thank you for your feedback and appreciation of our theoretical results. We address your comments below.\n\n> Practical implications and directions for empirical study\n\nThis is an insightful suggestion. We will add a section on the insights our work carries for the practitioners and pointers for future work. The implications we have in mind are the following: \n- **Limitations of reward models as evaluation metrics.** Our analysis shows that a model’s performance according to the reward model is a highly flawed measure of agreement with human preferences, and should not be conflated with average user satisfaction. Our results show that this mismatch does not reduce with increasing the amount or diversity of comparison data, but is a persistent bias due to information-theoretic barriers. Since (ordinal) comparison data is inherently limited in its informativeness about user satisfaction, empirical evaluations of user satisfaction should be based on users’ expression of (cardinal) preference intensity.\n- **Sensitivity to choice of post-training dataset**: Our results demonstrate that the reward-based pipeline of RLHF is sensitive to the sampling distribution over pairwise comparisons, whereas the reward-free method NLHF is more robust and analytically tractable. There is recent interest in using post-training data sets across models and platforms (e.g., Zhang, et al.. *“Cultivating Pluralism In Algorithmic Monoculture: The Community Alignment Dataset”*). Our results indicate that practitioners who use RLHF should be wary of lack of knowledge and control over how their data set was curated. As the community moves towards general purpose and public post-training data sets, there is even more argument in favor of using methods that are robust to the distribution of comparison data such as NLHF.\n- **Failure modes that may occur in practice**: As is common for any worst-case analysis, our lower-bound instances are stylized and chosen to be easy to analyze. But from a practical lens, we believe that these instances exaggerate patterns that may well occur in real-world examples (for example, that frequent pairwise comparisons between alternatives suppressed by the reference policy can cause RLHF to misalign on unsuppressed actions). Our theory allows the exploration of such patterns in a systematic way, based on which patterns have the biggest worst-case effect. These should be fruitful for future empirical research.\n\n\n> (Question 1) Suppose you had two users A and B, and use DPO to train a reward model R_mix over a 60/40 mixture of the two user’s preferences. Is it possible to classify R_mix from R_A or R_B (trained on each user’s preferences alone) using the lower bounds on the distortion (Theorems 5, 6)? That is, drawing samples from the original population (mixture for R_mix, A for R_A, etc), computing the sample mean distortion, and classifying based on those distortions. If so, this could potentially serve as a post-hoc measure of how heterogeneous the preferences are.\n\nWe’re not entirely certain if we fully understand the details of this question, but our interpretation is as follows: if we had enough samples from users A, B, and the mixture respectively to train reward models for each, could one compute the distortion of the mixture population and use it as a post-hoc measure of heterogeneity? The answer to this question is positive. However, note that training a reward model for, say, user A, requires a large number of pairwise comparisons, and several independent comparisons for the same pair of actions, to be collected from user A (and the same for user B). This would be possible if we could elicit comparisons from many copies of user A, but deviates from the crowdsourcing setting motivating our work, in which  users need not be partitioned into homogeneous types, and the small number of comparisons provided by each user might not even make it easy to cluster users if they do indeed come from few types. In regimes where it is possible to construct reward models (say, because an algorithm can cluster users into few homogeneous types), distortion could serve not only as a diagnostic for heterogeneity but also as a guide for improving alignment. In particular, optimizing for the mixture of each subgroup’s reward models could potentially yield a model that is better aligned to an average user (than fitting a single reward model over the mixture of preference data).\n\n> (Question 2) what if multiple reference policies were used (e.g. different base models, or different checkpoints of the same model), and the regularization consisted only of the minimum KL from each reference policy? So long as no reference policy puts a tiny amount of probability mass on c (line 289) wouldn’t this improve the lower bound in Theorem 6?\n\nWe agree that it is interesting to study whether the pessimistic lower bounds for RLHF can be mitigated by using multiple reference policies, which pushes in a similar line to our open question about $\\mu = \\pi_{ref}$ in lines 302–304. Note that there are subtle tradeoffs for studying this case: on the one extreme, if all policies place similarly small mass on the critical candidate $c$, then the KL regularization to several reference policies still prevents the output policy from allocating meaningful mass on $c$, and our lower bound construction persists. On the other extreme, if there are many, sufficiently different reference policies, taking the minimum KL may effectively remove the regularization. While this does benefit from our better upper bounds of section 3 in the setting without a KL constraint, it also undermines the purposes of using KL regularization in practice.\n\nFinally, our construction amplifies a phenomenon that might likely appear in practice, if certain types of response (e.g., instruction-following but harmful) are not yet suppressed when the preference data is sampled, but are suppressed by all reference policies. In such a scenario, constraining relative to all reference policies would not circumvent the problem. Conversely, even if all reference policies place high mass on all alternatives with high mass in $\\mu$, we do not know if this is enough to ensure a low distortion for RLHF, or if other failure modes exist. Investigating this is an intriguing direction for future research."}, {"review_id": "tpnwc9Sb8g", "reviewer": "Reviewer_i2wL", "summary": "The paper initiates a study of distortion in the alignment setting. Their model assumes a finite alternative set $A$ of size $m$ and, $n$ user each with a utility vector $u_i \\in [0,1]^m$ drawn from a common prior distribution $\\mathcal{D}$. Pairwise comparison queries are generated by sampling two alternatives i.i.d. from a distribution $\\mu$ over $A$. And then all the users provide $d$ noisy comparison according to the Bradley-Terry model with a shared temperature $\\beta$. \n\nThe authors then distinguish two regimes: one with no KL‐divergence limit on the learned policy, and the other with. They call them social choice v.s. alignment settings.\n\nBoth RLHF and NLHF are analyzed in each regime. Their core technical tool is a linearization lemma that bounds the deviation of the win‐rate of $x \\succ y$ from a a half by affine functions of $x,y$'s social welafare. The principal conclusion is that NLHF admits strictly tighter upper bounds on distortion than RLHF under both unconstrained and KL‐constrained setups.", "questions": "Your contribution is novel and timely. However, I still have several major concerns. I am happy to revise my evaluation once they are addressed:\n\n1. Dependence on m.n.  \n\n  In Theorems 2 and 7, if one allows $m \\propto n^2$ and $\\mu$ to be uniform $\\mu(x)=1/m$, the second term in the finite-sample distortion bound appears to grow without bound as $n \\to \\infty$. Could you discuss how \\(m\\) and \\(n\\) must scale relative to one another to ensure the bound remains meaningful? I am a little bit uneasy about the correctness of your statements. \n\n2. Behavior of distortion at extreme $\\beta$  \n\n  Intuitively, one might expect a U-shaped dependence on $\\beta$  : As $\\beta \\to 0$, comparisons become nearly random, losing information; as $\\beta \\to \\infty$, even a tiny utility gap yields deterministic comparison outcomes (e.g. originally $u_i(x)=0.3; u_i(y)=0.2999$, but a very high $\\beta$ would make it almost always the case that $x \\succ_i y$), also not reflecting the original preference intensity. \n  Yet your distortion bounds only worsen for large $\\beta$ , with no analogous degradation at small $\\beta$. Could you clarify why the bound does not reflect information loss in the first regime?\n\n3. Reference policy in the KL-ball \n\n   In Theorem 6, instead of exhibiting a single adversarial reference policy for the lower bound, is it possible to bound the distortion between an arbitrary reference policy and all policies within its KL-ball? Also, in Theorem 6 you refer to “a sequence of alignments”; could you clarify the intended meaning and why you chose this phrasing?\n\n\n4. Role of the post–Theorem 5 discussion\n\n  The paragraph following Theorem 5 appears to critique the distortion framework even this paper is centred about distortion. I didn't fully get why you made this discussion. It was nice that you have already adopted a new, alignment-oriented distortion measure, and drew a line between the traditional setting (as introduced around line 128) to your new alignment setting. Were you just trying to stress that the social choice setting is really not important for the alignment practitioners? \n\nAdditionally, I was also a bit disappointed by the paragraph starting from line 128: first, it's very good that you have mentioned the context-dependent aspect of alignment, but then you directly make an assumption instead of discussing the alternatives (even though you have mentioned this as future work in later section). Second, i wished to see more comparisons/motivations for your model v.s. a tranditional social choice model, for example, you make many more distributional assumptions and allow each user to provide only $d=1$ or $2$ comparisons, which differs fundamentally from the full-ranking assumption in traditional social choice.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. This paper intiates a series of important questions regarding distortion, and it is outstanding in the sense that it takes social choice literature as inspiration but also goes beyond it--- it takes KL constraints into account. \n2. The results are extensive. I particularly like the discussion section as it partially addresses some of the concerns i was having.\n\nWeaknesses:\n1. The clarity can be improved:\n\nline 96, maybe stress that : the objective is to find an alternative $x \\in A$, because with the original alignment techniques, a policy is able to generate new alternatives. I was unsure which case you are addressing until i read many more lines.\n\nline 115, it took me a while to figure out/guess what you meant by saying the \"expectation is taken over the pairwise comparisons\".\n\nline 117, 156, the social welfare of a rule not only depends on the rule itself, but also on the pairwise comparisons distribution as well as the users distribution, but both notations really did not reflect this. I understand that the notations would not look so nice, then you could introduce a shorthand. \n\nline 253, maybe change the wording \"the distortion guarantee is at least...\"\n\n2. Please see my questions.", "was_revised": true, "final_justification": "The reviewers have addressed all of my concerns. I believe some of the writings may still need to be improved, as well as the justification of the model. But it should be accepted.", "rebuttal": "Thank you for your comments and suggestions. We address the questions below.\n\n> **(Dependence on m,n)** In Theorems 2 and 7, if one allows $m\\propto n^2$ and $\\mu$ to be uniform, the second term in the finite-sample distortion bound appears to grow without bound as $n\\to\\infty$. Could you discuss how m and n must scale relative to one another to ensure the bound remains meaningful?\n\nRecall that $m$ denotes the number of candidate responses, and $n$ is the number of crowdsourced labelers sampled from the user population. Our analysis focuses on the regime where  $m$ is fixed and finite (e.g., a finite number of potential responses, or bounded latent complexity of the set of responses), while $n$ represents the sample complexity, in other words the total number of labelers sampled from distribution and can be made arbitrarily large by sampling more labelers from the user distribution. As is standard in determining the sample complexity in statistical learning, our bounds are optimized for the regime in which the number of comparisons is large compared to the latent complexity of the space. As a result of this focus, following your assumption that $\\mu$ is uniform over $m$ candidates, the finite distortion bound Thm 2 starts having bite when $n\\gg m^3\\log m$, and the bound in Thm 7 when $n\\gg m^2\\log m$.\n\n> **(Extreme beta)** Intuitively, one might expect a U-shaped dependence on $\\beta$ ... as $\\beta\\to0$, comparisons become nearly random, losing information …  Could you clarify why the bound does not reflect information loss in the first regime?\n\nYour intuition about the U-shaped curve is correct. For small but nonzero $\\beta$, the distortion in the *infinite* sample regime ($n\\to\\infty$) remains finite and close to $1$, but it is indeed true that the welfare approximation for a given *finite* number of samples would grow. This can be seen in the error terms of Thm 2 and 7: if $\\beta \\to 0$ as the other quantities remain fixed, the concentration error term would grow and and make the lower bounds on social welfare (for Borda or NLHF) vacuous. This reflects your intuition that each comparison becomes more random and thus contains less information, so achieving finite distortion requires a lot more samples (large $n$) to counteract this randomness. We will add a discussion after the corresponding theorems to clarify this.\n\n> **(KL ball)** In Theorem 6, instead of exhibiting a single adversarial reference policy for the lower bound, is it possible to bound the distortion between an arbitrary reference policy and all policies within its KL-ball? \n\nThe question can be potentially interpreted in two ways:\n- (1) Can we avoid the exponential distortion in Thm 6 by requiring $\\pi_{ref}$ to have bounded distortion compared to the optimal policy in the KL ball (so that the choice of $\\pi_{ref}$ is not fully adversarial)? The answer is no: in our constructed instance, c has welfare on order 1 but can’t be meaningfully used in KL ball; a has welfare $\\Theta(1/\\beta)$ and b has welfare $\\Theta(e^{-\\beta})$. Therefore, both $\\pi_{ref}$ and $\\pi^*$ has $\\Theta(1/\\beta)$ welfare, which implies that $\\pi_{ref}$ already has constant distortion relative to all policies in its KL ball.\n- (2) Can we upper bound the distortion as a function of the KL divergence between $\\mu$ and $\\pi_{ref}$? This would be an intriguing strengthening of the open question about the $\\mu=\\pi_{ref}$. However, the same construction shows that such a bound cannot be polynomial: we have $KL(\\pi_{ref} \\\\| \\mu)=\\Theta(\\beta)$ but distortion $=e^{\\Omega(\\beta)}$.\n\nDespite the above observations, we agree that it is important to understand the distortion of RLHF beyond the specific failure mode constructed in Thm 6. This is an interesting open question for future research.\n\n> In Theorem 6 you refer to “a sequence of alignments”; could you clarify the intended meaning and why you chose this phrasing?\n\nBy “sequence of alignment problems” we refer to a sequence of instances with increasing values of beta and m, where the distortion of this sequence goes to infinity. This is standard usage, and we will reword it to make it clearer.\n\n> The paragraph following Theorem 5 appears to critique the distortion framework… It was nice that you have already adopted a new, alignment-oriented distortion measure, and drew a line between the traditional setting (as introduced around line 128) to your new alignment setting. Were you just trying to stress that the social choice setting is really not important for the alignment practitioners?\n\nThank you for pointing out this ambiguity in the writing. We believe your confusion is due to the fact that we have both:\na “social choice setting” (l. 112), a special case of our alignment model (l. 128) in which the alignment method can output any distribution over actions, the same output as (randomized) social choice [e.g., 1]\nthe setting of “classic deterministic-choice distortion” (l. 162), the setting considered in papers on voting in social choice theory. This setting has the same output as above, but additionally assumes that users deterministically choose the higher-utility action, rather than choosing through a Bradley–Terry model.\nOur discussion starting in l. 254 refers to the latter “classical setting”. Our intent is not to downplay social choice theory’s perspective (or the social choice subsetting), but to highlight that adopting the BT model provides a “beyond-worst-case” lens [2] that is more meaningful not only for alignment applications, but also for the study of voting. For example, a “significant barrier” [3] to the classic deterministic-choice distortion approach is that all known voting rules with low deterministic distortion are highly artificial, whereas the minimax-optimal voting rule for BT distortion is a natural choice in alignment (NLHF) and the voting special case (Maximal Lotteries). We will revise the discussion to resolve this confusion.\n\n[1] Gibbard, Allan. “Manipulation of Schemes That Mix Voting with Chance.” Econometrica 45, no. 3 (1977): 665--681.\n[2] Roughgarden, Tim. Beyond the worst-case analysis of algorithms. Cambridge University Press; 2021 Jan 14. \n[3] Ebadian, Soroush, Anson Kahng, Dominik Peters, and Nisarg Shah. “Optimized Distortion and Proportional Fairness in Voting.” ACM Transactions on Economics and Computation 12, no. 1 (2024): 1–39. \n\n> **the context-dependent aspect of alignment**\n\nNote that all our lower bounds extend to a model that is aware of states, since our setting can be thought of as the special case in which preferences are constant across states. Our NLHF upper bound can also be used to show that this lower bound can be met, in the limit of infinitely many samples, even in a state-dependent model (assuming that preferences are Lipschitz in the state). At a high level, this can be shown with an alignment method that determines the policy at each state $x$ in the support of the state distribution by applying NLHF to only comparison pairs in a small neighborhood of states around $x$. This shows that our state-independent model gives the right infinite-sample behavior for a world with states; some of the authors are currently thinking about how to be more sample efficient in such a setting.\n\n> **more comparisons/motivations for your model v.s. a traditional social choice model**, for example, you make many more distributional assumptions and allow each user to provide only d=1 or 2 comparisons, which differs fundamentally from the full-ranking assumption in traditional social choice.\n\n- **BT vs deterministic comparisons**: We discussed the virtues of modeling choices as Bradley–Terry rather than the classic modeling assumption of deterministic choices, and this is indeed what our discussion after Thm. 5 is meant to convey. We would also like to point out that we do not see deterministic choices as a more realistic model of human behavior than Bradley–Terry, and that our linearization approach should extend to similar random-utility models for pairwise decisions.\n\n- **Pairwise vs full ranking**: Though we focus on the setting in which each voter provides few comparisons for clarity of exposition (a fitting model of current alignment practice), almost all of our results remain intact when voters provide full rankings. Since these rankings are randomized, users’ rankings would be distributed according to a Plackett–Luce model (l. 110), so that each pairwise comparison is still Bradley–Terry distributed. This model fits into the extended model we discuss in l. 354 (by having a constant distribution over $\\binom{m}{2}$ pairs), and we discuss in lines 361–363 how the results generalize. In this special case, the Borda rule also continues to be defined, with the same upper and lower bounds (and slightly better finite-sample guarantees for the upper bound).\n\n- **Distributional assumption**: We assume a distribution of user utility functions, and each labeler is an independent sample drawn from this distribution. This formulation allows each user/labeler to have a distinct utility function, rather than restricting the population to a small number of types. This generalizes the traditional social choice setting with is a finite number of voters, as we can take this distribution to be uniform over these voters (there is a minor difference between sampling with or without replacement from the population, which should vanish when the number of samples is large)."}, {"review_id": "N958lOdAQL", "reviewer": "Reviewer_qFQ9", "summary": "This paper investigates the distortion, which is the ratio of the maximum expected utility and the expected utility achieved, of several preference alignment algorithms. The results include the lower bounds and upper bounds of algorithms without/with KL-constraints to a reference policy. Specifically, the paper proves that NLHF achieves the best distortion, while RLHF and DPO suffer a larger distortion.", "questions": "Intuitively, what is the reason that NLHF outperforms RLHF? Is it because NLHF optimizes on matrix $M$, which contains more information than the estimated utility vector used by RLHF?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n- The writing of the paper is clear and easy to follow.\n- The results sound novel to me. This paper shows that the final performance of NLHF (expected utility) might be an exponential multiple of that of RLHF. The reason is that RLHF cannot handle users with heterogeneous feedback since it encodes all preference data into a single utility vector. This further justifies the motivations of work focusing on RLHF with heterogeneous feedback, such as [1] and [2].\n\n## Weaknesses\n\n- This paper does not have any experiments to corroborate the results.\n- All results of RLHF are limited to the single-preference RLHF, where the algorithm ignores the source of each preference data. In other words, the RLHF considered in this paper does not consider heterogeneous preferences.\n\n[1] Zhong, Huiying, et al. \"Provable multi-party reinforcement learning with diverse human feedback.\" arXiv preprint arXiv:2403.05006 (2024).\n\n[2] Park, Chanwoo, et al. \"Principled rlhf from heterogeneous feedback via personalization and preference aggregation.\" arXiv e-prints (2024): arXiv-2405.", "was_revised": true, "final_justification": "The authors' response address my questions, and I will keep the rating.", "rebuttal": "Thank you for your feedback and appreciation of our results. We address your comments below.\n\n> **(Single-preference RLHF)** All results of RLHF are limited to the single-preference RLHF, where the algorithm ignores the source of each preference data. In other words, the RLHF considered in this paper does not consider heterogeneous preferences.\n\nTo avoid ambiguity for other readers, let us start by emphasizing that our model does capture preference heterogeneity (in fact, even richer forms of heterogeneity than Park et al. (2024) because we do not place assumptions on users’ utilities), and that the reviewer wishes that we had studied additional alignment methods such as proposed RLHF variants tailored for heterogeneous preferences.\n\nWe believe that it is extremely natural for our paper to initiate the study of alignment distortion by investigating RLHF/DPO [Christiano et al., Ziegler et al., Rafailov et al.], the incumbent methods for AI alignment in practice, as well as the minimax optimal alignment method NLHF. Studying the distortion of other alignment methods, including the proposed RLHF variants by Park et al., is an interesting direction for future research. Given that these algorithms are based on assumptions about user preferences (clusterability or a low-dimensional common representation), we would expect the algorithms to obtain very high distortion in our model, in which these assumptions need not hold. These algorithms also require a large number $d$ of comparison data per user to have any chance at clustering or representation learning. By comparison, it is impressive that NLHF can obtain an excellent distortion (optimal under the assumptions given in Thm. 3) already with a single comparison per user.\n\n> **Experiments & Practical implications**\n\nWhile we agree that empirical evaluations are an intriguing next step of our work, we want to echo reviewer `mjbj` who writes that “asking for extensive empirical results would be outside the scope of the paper (the theoretical results are already compelling as they stand, and the experiments themselves would be expensive enough to deserve their own paper anyways)”. Besides the computational cost of experiments, the limitations of pairwise comparisons we show also mean that most post-training datasets, which consist of such comparisons, are insufficient for such an evaluation. For future work, we are intrigued by recent datasets [e.g., Kirk et al., NeurIPS’24] that include expressions of cardinal information and the rater’s identity, but using such data to evaluate models based on user utilities will require overcoming challenges about users’ inconsistent reporting of cardinal values and the low amount of preference data per user in the datasets.\n\nWhile our work does not include such experiments, our main contribution is to introduce and analyze distortion as a theoretical metric for worst-case robustness. Our work also carries lessons for the practitioner as described below:\n- **Limitations of reward models as evaluation metrics.** Our analysis shows that a model’s performance according to the reward model is a highly flawed measure of agreement with human preferences, and should not be conflated with average user satisfaction. Our results show that this mismatch does not reduce with increasing the amount or diversity of comparison data, but is a persistent bias due to information-theoretic barriers. Since (ordinal) comparison data is inherently limited in its informativeness about user satisfaction, empirical evaluations of user satisfaction should be based on users’ expression of (cardinal) preference intensity.\n- **Sensitivity to choice of post-training dataset**: Our results demonstrate that the reward-based pipeline of RLHF is sensitive to the sampling distribution over pairwise comparisons, whereas the reward-free method NLHF is more robust and analytically tractable. There is recent interest in using post-training data sets across models and platforms (e.g., Zhang, et al. *“Cultivating Pluralism In Algorithmic Monoculture: The Community Alignment Dataset”*). Our results indicate that practitioners who use RLHF should be wary of lack of knowledge and control over how their data set was curated. As the community moves towards general purpose and public post-training data sets, there is even more argument in favor of using methods that are robust to the distribution of comparison data such as NLHF.\n- **Failure modes that may occur in practice**: As is common for any worst-case analysis, our lower-bound instances are stylized and chosen to be easy to analyze. But from a practical lens, we believe that these instances exaggerate patterns that may well occur in real-world examples (for example, that frequent pairwise comparisons between alternatives suppressed by the reference policy can cause RLHF to misalign on unsuppressed actions). Our theory allows the exploration of such patterns in a systematic way, based on which patterns have the biggest worst-case effect.\n\n\n> **Intuitively, what is the reason that NLHF outperforms RLHF?** Is it because NLHF optimizes on matrix, which contains more information than the estimated utility vector used by RLHF?\n\nWe agree with your intuition that RLHF is limited by the fact that its utility vector discards much of the relevant information, and that, conversely, NLHF profits from a richer representation of preferences, which preserves information about disagreements/heterogeneity. In addition, NLHF’s strength comes from its algorithmic approach — its computation of the policy by solving  a 2-player game “hedges” (l. 310) against any other alternative being much better, which makes the distribution particularly robust."}]

Author rebuttal:

Meta-review: This paper introduces distortion as a rigorous theoretical framework to evaluate alignment methods under heterogeneous human preferences, drawing from social choice theory. The authors provide tight upper and lower bounds showing that standard approaches such as RLHF and DPO can incur large, even unbounded distortion, while Nash Learning from Human Feedback achieves minimax-optimal robustness. Reviewers recognized the novelty and importance of this contribution, praising its strong theoretical results, clarity of analysis, and implications for pluralistic alignment. Concerns centered on the lack of empirical validation, the clarity of presentation in some sections, and the need for more explicit guidance for practitioners. The authors addressed these points effectively in rebuttal, clarifying technical details, explaining the relevance of their lower-bound constructions, and adding a section on practical implications and empirical directions. Several reviewers raised their scores after discussion, acknowledging that while the work is purely theoretical, its contributions are substantial and timely for the alignment community.
Decision: Accept (poster)