Paper deep dive

Distortion of AI Alignment: Does Preference Optimization Optimize for Preferences?

Paul Gölz, Nika Haghtalab, Kunhe Yang

Year: 2025Venue: arXiv preprintArea: Alignment TrainingType: TheoreticalEmbeddings: 328

Intelligence

Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 96%

Last extracted: 3/12/2026, 6:16:58 PM

Summary

The paper introduces the concept of 'distortion' in AI alignment to measure the gap between the average utility of a learned policy and the optimal achievable average utility. It demonstrates that current methods like RLHF and DPO, which rely on a single 'mythical' reward model, suffer from significant distortion when users have heterogeneous preferences. In contrast, Nash Learning from Human Feedback (NLHF) is shown to achieve minimax optimal distortion, providing a more robust approach for pluralistic alignment.

Entities (5)

DPO · alignment-method · 100%NLHF · alignment-method · 100%RLHF · alignment-method · 100%Bradley-Terry Model · statistical-model · 95%Distortion · metric · 95%

Relation Signals (3)

NLHF → achievesdistortion → (1/2 + o(1)) * β

confidence 95% · Nash Learning from Human Feedback achieves the minimax optimal distortion of (1/2 + o(1)) * β

DPO → equivalentto → RLHF

confidence 95% · Direct Preference Optimization (DPO) (Rafailov et al., 2023) is equivalent to RLHF in our analysis

RLHF → exhibitsdistortion → e^Ω(β)

confidence 90% · RLHF and DPO, by contrast, suffer ≥(1-o(1))⋅β distortion already without a KL constraint, and e^Ω(β) or even unbounded distortion in the full setting

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

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 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 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 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.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

327,773 characters extracted from source content.

Expand or collapse full text

Distortion of AI Alignment: Does Preference Optimization Optimize for Preferences? Paul Gölz Cornell University paulgoelz@cornell.edu Nika Haghtalab UC Berkeley nika@berkeley.edu Kunhe Yang UC Berkeley kunheyang@berkeley.edu 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 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 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 of (12+o⁢(1))⋅β⋅121( 12\!+\!o(1))·β( divide start_ARG 1 end_ARG start_ARG 2 end_ARG + o ( 1 ) ) ⋅ β (for the BT temperature β), robustly across utility distributions, distributions of comparison pairs, and permissible KL divergences from the reference policy. RLHF and DPO, by contrast, suffer ≥(1−o⁢(1))⋅βabsent⋅11≥(1\!-\!o(1))·β≥ ( 1 - o ( 1 ) ) ⋅ β distortion already without a KL constraint, and eΩ⁢(β)superscriptΩe (β)eroman_Ω ( β ) or even unbounded distortion in the full setting, depending on how comparison pairs are sampled. 1 Introduction Reinforcement Learning from Human Feedback (RLHF) (Ouyang et al., 2022; Rafailov et al., 2023; Christiano et al., 2017; Ziegler et al., 2019) has become the dominant paradigm for aligning large language models (LLMs) with human values and preferences. In a typical alignment pipeline, human feedback is provided as ordinal comparisons between pairs of candidate model outputs. This feedback is used to fine-tune a pre-trained model, steering it toward the preferences expressed in these comparisons. A major limitation of RLHF and of many proposed alternatives (including DPO (Rafailov et al., 2023), Φ ΦPO (Azar et al., 2024), KTO (Ethayarajh et al., 2024), SimPO (Meng et al., 2024), χPO (Huang et al., 2024)) is that they do not take into account that users will disagree on which model outputs are most useful or least harmful. A growing body of evidence — from both the general public and the research community (AII, ; Sorensen et al., 2024; Conitzer et al., 2024; Bai et al., 2022b) — suggests that this blind spot of current alignment methods can lead to unfair outcomes. For example, Chakraborty et al. (2024) argue that RLHF may align with a majority group’s preferences and ignore the preferences of a minority. In this work, we study a 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 a single, perhaps representative, user in mind whose noisy ordinal preferences are assumed to be consistent with an underlying utility model. As a result, RLHF fits a single reward model to the observed ordinal comparisons of a population of users with different utility functions, effectively constructing a utility function for a “mythical” representative user. Could it be that optimizing a 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? Figure 1: The typical RLHF pipeline. The preference optimization process begins by collecting comparison data from users with heterogeneous utilities. A single Bradley-Terry model is then fit to this data via Maximum Likelihood Estimation (MLE), producing a single reward model that represents a “mythical user” whose utility best explains the observed comparisons. This reward model is used to fine-tune the pretrained policy. We define distortion as the ratio between the average utility of an optimal policy and that of the output policy, which measures how well a policy aligned with 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,111While prior work has called for the study of distortion in alignment (Dai and Fleisig, 2024), or used alignment as a motivation for studying the distortion of voting rules (Goyal and Sarmasarkar, 2025; Ebadian et al., 2024a), our work is to our best knowledge the first to systematically define and analyze the distortion of alignment methods. We discuss these related efforts in Appendix A. which we define as the ratio between the optimal average utility of a 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 to the optimal policy. This notion is adapted from social choice theory (e.g., Procaccia and Rosenschein, 2006; Boutilier et al., 2012; Anshelevich et al., 2021), 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 probabilistically, following a 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 to stay close to 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 Bradley–Terry comparisons (Section 3) and the alignment setting (Section 4), which additionally constrains the policy to remain close in Kullback-Leibler (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) (Munos et al., 2024), which coincides with the Maximal Lotteries (Fishburn, 1984) voting rule. Direct Preference Optimization (DPO) (Rafailov et al., 2023) is equivalent to RLHF in our analysis and hence has the same distortion. We define these alignment methods and voting rules in Section 2. In Section 5, we discuss how our results extend to KL-regularized (rather than constrained) alignment methods and to generalized models of sampling comparison pairs. In this overview of results, summarized in Table 1, 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), if each user only provides a single comparison, we show through a non-identifiability argument222While the non-identifiability of mixtures of ranking models is well established (Zhao et al., 2016; Zhao and Xia, 2019; Zhang et al., 2022), our result quantifies the resulting loss in average utility. that, for each value β>00β>0β > 0 of the Bradley–Terry temperature, every alignment method (or, equivalently, any voting rule) will suffer a distortion of (12+o⁢(1))⁢β121( 12+o(1))β( divide start_ARG 1 end_ARG start_ARG 2 end_ARG + o ( 1 ) ) β on some instances. This lower bound reflects a fundamental information bottleneck: even under Bradley–Terry generative assumptions, ordinal feedback is not rich enough to perfectly optimize for the average utility of a heterogeneous user population. If each user provides d≥22d≥ 2d ≥ 2 (possibly correlated) comparisons, the same lower bound applies to all voting rules that satisfy a probabilistic relaxation of the Condorcet 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 β. Borda’s distortion lies between (1−o⁢(1))⁢β11(1-o(1))β( 1 - o ( 1 ) ) β and O⁢(β2)superscript2O(β^2)O ( β2 ), whereas Maximal Lotteries’ distortion is (12+o⁢(1))⁢β121( 12+o(1))β( divide start_ARG 1 end_ARG start_ARG 2 end_ARG + o ( 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 (2025) 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 in the general-utility distortion setting, where constant distortion is classically impossible, than in metric distortion. For the AI community, these distortion bounds also carry implications for AI leaderboards such as Chatbot Arena Chiang et al. (2024), where heterogeneous user preferences across diverse tasks are aggregated via MLE under a single Bradley–Terry model — 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 (12+o⁢(1))⁢β121( 12+o(1))β( divide start_ARG 1 end_ARG start_ARG 2 end_ARG + o ( 1 ) ) β 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 a Ω⁢(1/β)Ω1 (1/β)Ω ( 1 / β ) 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 5 that this directly implies a similar distortion guarantee for regularized NLHF. In contrast, RLHF’s distortion can grow as eΩ⁢(β)superscriptΩe (β)eroman_Ω ( β ) 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.i.d. Table 1: Overview of distortion bounds by alignment method and setting. Alignment Method Social Choice Setting AI Alignment Setting RLHF (Ziegler et al., 2019) ≤O⁢(β2)absentsuperscript2≤ O(β^2)≤ O ( β2 ) Thm 2 (Borda) ≥(1−o⁢(1))⁢βabsent11≥(1-o(1))\,β≥ ( 1 - o ( 1 ) ) β Thm 5 ≥eΩ⁢(β)absentsuperscriptΩ≥ e (β)≥ eroman_Ω ( β ) Thm 6 / Unbounded in β* Thm 9 NLHF (Munos et al., 2024) =(12+o⁢(1))⁢βabsent121= ( 12+o(1) )\,β= ( divide start_ARG 1 end_ARG start_ARG 2 end_ARG + o ( 1 ) ) β Cor 4 (Max. Lotteries) =(12+o⁢(1))⁢βabsent121= ( 12+o(1) )\,β= ( divide start_ARG 1 end_ARG start_ARG 2 end_ARG + o ( 1 ) ) β Thm 7 all (one comparison per user/ Condorcet loser property) ≥(12+o⁢(1))⁢βabsent121≥ ( 12+o(1) )\,β≥ ( divide start_ARG 1 end_ARG start_ARG 2 end_ARG + o ( 1 ) ) β Thm 3 ≥(12+o⁢(1))⁢βabsent121≥ ( 12+o(1) )\,β≥ ( divide start_ARG 1 end_ARG start_ARG 2 end_ARG + o ( 1 ) ) β Thm 3 *comparison pairs sampled from a distribution over pairs. We discuss additional related work in Appendix A. 2 Preliminaries Let A=1,…,m1…A=\1,…,m\A = 1 , … , m be a finite set of alternatives. The population of users is described by a probability distribution DD over utility vectors u=(u⁢(1),…,u⁢(m))1…u=(u(1),…,u(m))u = ( u ( 1 ) , … , u ( m ) ), whose entries 0≤u⁢(x)≤1010≤ u(x)≤ 10 ≤ u ( x ) ≤ 1 indicate a user’s utility for alternative x.333Our assumption that utilities be in [0,1]01[0,1][ 0 , 1 ] is weaker than any of the three assumptions — unit-sum, unit-range, or approval (Ebadian et al., 2024b) — made in classic distortion to avoid trivial infinite lower bounds. The objective is to find an alternative x such that its average utility ⁢(x)≔u∼⁢[u⁢(x)]≔subscriptsimilar-todelimited-[] AvgUtil(x) _u [u(x)]sansserif_AvgUtil ( x ) ≔ blackboard_Eu ∼ D [ u ( x ) ] 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 ⁢(π)≔x∼π⁢[⁢(x)]≔subscriptsimilar-todelimited-[] AvgUtil(π) _x π[ AvgUtil(x)]sansserif_AvgUtil ( π ) ≔ blackboard_Ex ∼ π [ sansserif_AvgUtil ( x ) ]. Both voting rules and alignment methods observe comparisons from n users. We model each i=1,…,n1…i=1,…,ni = 1 , … , n as a fresh user with independently drawn utility vector ui∼similar-tosubscriptu_i _i ∼ D. For exposition, we assume that each user i provides an equal number d≥11d≥ 1d ≥ 1 of pairwise comparisons. For each i, and for j=1,…,d1…j=1,…,dj = 1 , … , d, we independently draw alternatives xij,yijsuperscriptsubscriptsuperscriptsubscriptx_i^j,y_i^jxitalic_iitalic_j , yitalic_iitalic_j from a fixed distribution μ over alternatives, in which the minimum probability mass μmin≔minx∈A⁡μ⁢(x)≔subscriptsubscript _ _x∈ Aμ(x)μroman_min ≔ minitalic_x ∈ A μ ( x ) is positive.444In Section 5, we discuss how most of our results extend more general distributions over comparison pairs, which can, for example. capture k-wise comparisons. User i then compares each pair xij,yijsuperscriptsubscriptsuperscriptsubscript\x_i^j,y_i^j\ xitalic_iitalic_j , yitalic_iitalic_j (for j=1,…,d1…j=1,…,dj = 1 , … , d) through a Bradley-Terry model based on i’s utilities: i prefers xijsuperscriptsubscriptx_i^jxitalic_iitalic_j over yijsuperscriptsubscripty_i^jyitalic_iitalic_j (written “xij≻iyijsubscriptsucceedssuperscriptsubscriptsuperscriptsubscriptx_i^j _iy_i^jxitalic_iitalic_j ≻i yitalic_iitalic_j”) with probability σ⁢(β⋅(ui⁢(xij)−ui⁢(yij)))⋅subscriptsuperscriptsubscriptsubscriptsuperscriptsubscriptσ (β·(u_i(x_i^j)-u_i(y_i^j)) )σ ( β ⋅ ( uitalic_i ( xitalic_iitalic_j ) - uitalic_i ( yitalic_iitalic_j ) ) ), where σ⁢(t)≔1/(1+e−t)≔11superscriptσ(t) 1/(1+e^-t)σ ( t ) ≔ 1 / ( 1 + e- t ) is the logistic sigmoid function and β>00β>0β > 0 is a temperature parameter, and prefers yijsuperscriptsubscripty_i^jyitalic_iitalic_j over xijsuperscriptsubscriptx_i^jxitalic_iitalic_j (“yij≻ixijsubscriptsucceedssuperscriptsubscriptsuperscriptsubscripty_i^j _ix_i^jyitalic_iitalic_j ≻i xitalic_iitalic_j”) otherwise.555Should we sample the same alternative x=xij=yijsuperscriptsubscriptsuperscriptsubscriptx=x_i^j=y_i^jx = xitalic_iitalic_j = yitalic_iitalic_j twice for a pair, the user is not asked for a pairwise comparison. We record this as “x≻ixsubscriptsucceedsx _ix ≻i x”, in a slight abuse of notation. Whereas this specifies the marginal probability of each pairwise comparison, we make no assumption about the correlation between i’s choices. For example, i might derive the pairwise comparisons from a Plackett-Luce ranking, ensuring that the user’s comparisons are always consistent.666In particular, if we sample the same unordered pair twice for a user, the answers can be perfectly correlated. We set p⁢(x≻y)succeedsp(x y)p ( x ≻ y ) for the expected win rate u∼⁢[σ⁢(β⋅(u⁢(x)−u⁢(y)))]subscriptsimilar-todelimited-[]⋅E_u [σ (β·(u(x)-u(y)) )% ]blackboard_Eu ∼ D [ σ ( β ⋅ ( u ( x ) - u ( y ) ) ) ]. Social Choice Setting. A voting rule f observes the sampled pairwise comparisons xij≻iyiji∈[n],j∈[d]subscriptsubscriptsucceedssuperscriptsubscriptsuperscriptsubscriptformulae-sequencedelimited-[]delimited-[]\x_i^j _iy_i^j\_i∈[n],j∈[d] xitalic_iitalic_j ≻i yitalic_iitalic_j i ∈ [ n ] , j ∈ [ d ] and maps them to a probability distribution over alternatives. For some m, DD, β, d, μ, and the correlation between comparisons, the average utility of f for n samples is n⁢(f)≔⁢[⁢(f⁢(xij≻iyiji,j))]≔subscriptdelimited-[]subscriptsubscriptsucceedssuperscriptsubscriptsuperscriptsubscript AvgUtil_n(f) [ AvgUtil (f(\x_% i^j _iy_i^j\_i,j) ) ]sansserif_AvgUtiln ( f ) ≔ blackboard_E [ sansserif_AvgUtil ( f ( xitalic_iitalic_j ≻i yitalic_iitalic_j i , j ) ) ], where the expectation is taken over the pairwise comparisons. The distortion of f on DD is the competitive ratio between n⁢(f)subscript AvgUtil_n(f)sansserif_AvgUtiln ( f ) and the optimal average utility maxx∈A⁡⁢(x)subscript _x∈ A AvgUtil(x)maxitalic_x ∈ A sansserif_AvgUtil ( x ) in the limit of n→∞→n→∞n → ∞ samples, and the distortion of f the worst-case distortion over all DD: ⁢(f,)≔lim supn→∞maxx∈A⁡⁢(x)n⁢(f),⁢(f)=sup⁢(f,).formulae-sequence≔subscriptlimit-supremum→subscriptsubscriptsubscriptsupremumdist(f,D) _n→∞ _x∈ A% AvgUtil(x) AvgUtil_n(f), (f)= _% Ddist(f,D).dist ( f , D ) ≔ lim supn → ∞ divide start_ARG maxitalic_x ∈ A sansserif_AvgUtil ( x ) end_ARG start_ARG sansserif_AvgUtiln ( f ) end_ARG , dist ( f ) = supcaligraphic_D dist ( f , D ) . For alternatives x,yx,yx , y, let #⁢(x≻y)≔(i,j)∣xij=x,yij=y≔#succeedsconditional-setformulae-sequencesuperscriptsubscriptsuperscriptsubscript\#(x y) \(i,j) x_i^j=x,y_i^j=y\# ( x ≻ y ) ≔ ( i , j ) ∣ xitalic_iitalic_j = x , yitalic_iitalic_j = y denote the number of pairwise comparisons in which x beat y. The (normalized) Borda score (Shirali et al., 2025) of alternative x is ⁢(x)≔∑y∈A#⁢(x≻y)∑y∈A#⁢(x≻y)+∑y≠x#⁢(y≻x),≔subscript#succeedssubscript#succeedssubscript#succeeds BC(x) _y∈ A\#(x y) _y∈ A\#(x y% )+ _y≠ x\#(y x),sansserif_BC ( x ) ≔ divide start_ARG ∑y ∈ A # ( x ≻ y ) end_ARG start_ARG ∑y ∈ A # ( x ≻ y ) + ∑y ≠ x # ( y ≻ x ) end_ARG , i.e., the fraction of pairwise comparisons involving x in which it wins. The Borda voting rule chooses the winner uniformly among all alternatives with maximum Borda score. The Maximal Lotteries voting rule first computes the margin matrix M∈ℝm×msuperscriptℝM ^m× mM ∈ blackboard_Rm × m, where Mx,y=#⁢(x≻y)−#⁢(y≻x)#⁢(x≻y)+#⁢(y≻x)subscript#succeeds#succeeds#succeeds#succeedsM_x,y= \#(x y)-\#(y x)\#(x y)+\#(y x)Mitalic_x , y = divide start_ARG # ( x ≻ y ) - # ( y ≻ x ) end_ARG start_ARG # ( x ≻ y ) + # ( y ≻ x ) end_ARG. It then considers a symmetric two-player zero-sum game in which player 1 selects alternative x1subscript1x_1x1, player 2 selects alternative x2subscript2x_2x2, and the payoffs are Mx1,x2subscriptsubscript1subscript2M_x_1,x_2Mitalic_x start_POSTSUBSCRIPT 1 , x2 end_POSTSUBSCRIPT for player 1 and Mx2,x1=−Mx1,x2subscriptsubscript2subscript1subscriptsubscript1subscript2M_x_2,x_1=-M_x_1,x_2Mitalic_x start_POSTSUBSCRIPT 2 , x1 end_POSTSUBSCRIPT = - Mitalic_x start_POSTSUBSCRIPT 1 , x2 end_POSTSUBSCRIPT for player 2. The maximal lotteries rule returns a distribution π∈argmaxπ1∈Δ⁢(A)minπ2∈Δ⁢(A)⁡x1∼π1,x2∼π2⁢[Mx1,x2]subscriptargmaxsubscript1Δsubscriptsubscript2Δsubscriptformulae-sequencesimilar-tosubscript1subscript1similar-tosubscript2subscript2delimited-[]subscriptsubscript1subscript2π∈ *argmax_ _1∈ (A) _ _2∈ (A)% E_x_1 _1,x_2 _2[M_x_1,x_2]π ∈ argmaxitalic_π start_POSTSUBSCRIPT 1 ∈ Δ ( A ) end_POSTSUBSCRIPT minitalic_π start_POSTSUBSCRIPT 2 ∈ Δ ( A ) end_POSTSUBSCRIPT blackboard_Ex start_POSTSUBSCRIPT 1 ∼ π1 , x2 ∼ π2 end_POSTSUBSCRIPT [ Mitalic_x start_POSTSUBSCRIPT 1 , x2 end_POSTSUBSCRIPT ], i.e., a mixed strategy in Nash equilibrium. (When several such π exist, our results hold for any choice.) Alignment Setting. The alignment setting generalizes the social choice setting in two ways: first, user utilities ui⁢(y∣)subscriptconditionalu_i(y x)uitalic_i ( y ∣ italic_x ) may depend on a state xitalic_x; second, the goal in determining a policy π is not purely to maximize the reward ⁢(π∣)conditional AvgUtil(π x)sansserif_AvgUtil ( π ∣ italic_x ), but a trade-off between this reward and the goal of remaining close to a reference policy πref(⋅∣)∈Δ(A) _ref(· x)∈ (A)πref ( ⋅ ∣ italic_x ) ∈ Δ ( A ) in terms of the KL divergence DKL(⋅∥πref)D_KL(·\,\|\, _ref)DKL ( ⋅ ∥ πref ). For theoretical tractability, we focus our analysis on a single state xitalic_x, 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 state777This assumption is common in the literature; see, for example, Rafailov et al. (2023)’s application of first-order optimality conditions of PPO loss minimization. and abstracts from the generalization problem of estimating the population’s preference between a pair of alternatives at the given state xitalic_x based on preferences in similar states ′superscript′ x italic_x′. Having set aside the dependency between states, we focus on how the regularization with respect to a 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 πref∈Δ⁢(A)subscriptrefΔ _ref∈ (A)πref ∈ Δ ( A ) and a KL bound τ≥00τ≥ 0τ ≥ 0, and map these inputs to a policy π in the KL-ball Bτ⁢(πref)≔π∈Δ⁢(A)∣DKL⁢(π∥πref)≤τ≔subscriptsubscriptrefconditional-setΔsubscriptKLconditionalsubscriptrefB_τ( _ref) \π∈ (A) D_KL(π\,\|% \, _ref)≤τ\Bitalic_τ ( πref ) ≔ π ∈ Δ ( A ) ∣ DKL ( π ∥ πref ) ≤ τ 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. The RLHF method first estimates rewards for each alternative, using maximum likelihood estimation assuming that comparisons were generated by a single Bradley–Terry model: r≔argmaxr∈ℝm⁢∑1≤i≤n,1≤j≤dlog⁡(σ⁢(r⁢(xij)−r⁢(yij))).≔subscriptargmaxsuperscriptℝsubscriptformulae-sequence11superscriptsubscriptsuperscriptsubscript r *argmax_r ^m _1≤ i% ≤ n,1≤ j≤ d (σ(r(x_i^j)-r(y_i^j)) ).r ≔ argmaxitalic_r ∈ blackboard_Rm ∑1 ≤ i ≤ n , 1 ≤ j ≤ d log ( σ ( r ( xitalic_iitalic_j ) - r ( yitalic_iitalic_j ) ) ) . Next, RLHF uses PPO (Schulman et al., 2017) to compute the policy with maximum expected reward within the KL-ball: π≔argmaxπ∈Bτ⁢(πref)x∼π⁢[r⁢(x)].≔subscriptsubscriptargmaxsubscriptsubscriptrefsubscriptsimilar-todelimited-[] _ RLHF *argmax_π∈ B_τ( _ % ref)E_x π[r(x)].πsansserif_RLHF ≔ argmaxitalic_π ∈ B start_POSTSUBSCRIPT τ ( πref ) end_POSTSUBSCRIPT blackboard_Ex ∼ π [ r ( x ) ] . In our setup, DPO is equivalent to RLHF (see Section E.3) 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 (Munos et al., 2024). NLHF naturally adapts the definition of maximal lotteries by constraining both players’ mixed strategies to the KL-ball, i.e., π≔argmaxπ1∈Bτ⁢(πref)minπ2∈Bτ⁢(πref)⁢x1∼π1,x2∼π2[Mx1,x2].≔subscriptsubscriptargmaxsubscript1subscriptsubscriptrefsubscriptsubscript2subscriptsubscriptrefsubscriptformulae-sequencesimilar-tosubscript1subscript1similar-tosubscript2subscript2subscriptsubscript1subscript2 _ NLHF *argmax_ _1∈ B_τ( _% ref) _ _2∈ B_τ( _ref) *% E_x_1 _1,x_2 _2 [M_x_1,x_2 ].πsansserif_NLHF ≔ argmaxitalic_π start_POSTSUBSCRIPT 1 ∈ Bitalic_τ ( πref ) end_POSTSUBSCRIPT minitalic_π start_POSTSUBSCRIPT 2 ∈ Bitalic_τ ( πref ) end_POSTSUBSCRIPT blackboard_Ex start_POSTSUBSCRIPT 1 ∼ π1 , x2 ∼ π2 end_POSTSUBSCRIPT [ Mitalic_x start_POSTSUBSCRIPT 1 , x2 end_POSTSUBSCRIPT ] . To generalize the definition of distortion to alignment methods, we set the maximum average utility of any policy in the KL-ball as the benchmark. For fixed m,,β,d,μm,D,β,d, , D , β , d , μ and correlation between pairwise comparisons, the distortion of alignment method f is ⁢(f)=sup,πref,τlim supn→∞maxπ∈Bτ⁢(πref)⁡⁢(π)n⁢(f⁢(⋅,πref,τ)).subscriptsupremumsubscriptrefsubscriptlimit-supremum→subscriptsubscriptsubscriptrefsubscript⋅subscriptrefdist(f)= _D, _ref,τ _n→∞% _π∈ B_τ( _ref) AvgUtil(π) % AvgUtil_n(f(·, _ref,τ)).dist ( f ) = supcaligraphic_D , π start_POSTSUBSCRIPT ref , τ end_POSTSUBSCRIPT lim supn → ∞ divide start_ARG maxitalic_π ∈ B start_POSTSUBSCRIPT τ ( πref ) end_POSTSUBSCRIPT sansserif_AvgUtil ( π ) end_ARG start_ARG sansserif_AvgUtiln ( f ( ⋅ , πref , τ ) ) end_ARG . 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 regularization) to the reference policy vanishes. Hence, distortion measures whether the “direction” in which an alignment 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 overcomes the pessimism of classic deterministic-choice distortion. In the classic setting, high distortion — Ω⁢(m)Ω ( m)Ω ( square-root start_ARG m end_ARG ) even for randomized voting rules and under utility-normalization assumptions (Boutilier et al., 2012; Ebadian et al., 2024b) — is unavoidable because a voting rule observes no signal about preference intensity, i.e., whether a user prefers a over b strongly or 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 a single utility vector: by consistency, the Bradley-Terry MLE would recover the utilities (up to an additive shift), allowing us to select the utility-maximizing alternative and achieve a perfect distortion of 1. It is not obvious, by contrast, that random pairwise comparisons will be similarly useful in our heterogeneous setting, where each observation is drawn from a 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, a source of inspiration is an observation by Caragiannis and Procaccia (2011) in a much simpler model, in which each user votes for a single alternative with probability equal to their utility (which is normalized to sum to 1111). Since the probability of the event “i votes for x” equals ui⁢(x)subscriptu_i(x)uitalic_i ( x ), the total number of votes of alternative x (i.e., ∑i∈Ni votes for xsubscriptsubscript1i votes for x _i∈ N 1_$i$ votes for $x$∑i ∈ N blackboard_1i votes for x) is an unbiased estimator of its total utility. Figure 2: Bounds on probability of preferring x over y, β=55β=5β = 5. 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 a probability that is affine in the user’s utilities. Alas, we are not so lucky: the sigmoid function in the probability of the event “i ranks x over y” is nonlinear, and we show in Theorem 3 that this nonlinearity makes a distortion of at least β2⁢1+e−β1−e−β>121superscript1superscript1 β2\, 1+e^-β1-e^-β>1divide start_ARG β end_ARG start_ARG 2 end_ARG divide start_ARG 1 + e- β end_ARG start_ARG 1 - e- β end_ARG > 1 unavoidable. 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, we sandwich the probability σ⁢(β⋅(u⁢(x)−u⁢(y)))⋅σ(β·(u(x)-u(y)))σ ( β ⋅ ( u ( x ) - u ( y ) ) ) that a user with utilities u prefers x over y between the affine lower bound β⋅(L⁢u⁢(x)−ℓβ⁢u⁢(y))+12⋅subscriptℓ12β·(L\,u(x)- _β\,u(y))+ 12β ⋅ ( L u ( x ) - ℓitalic_β u ( y ) ) + divide start_ARG 1 end_ARG start_ARG 2 end_ARG and affine upper bound β⋅(ℓβ⁢u⁢(x)−L⁢u⁢(y))+12⋅subscriptℓ12β·( _β\,u(x)-L\,u(y))+ 12β ⋅ ( ℓitalic_β u ( x ) - L u ( y ) ) + divide start_ARG 1 end_ARG start_ARG 2 end_ARG, for constants L,ℓβsubscriptℓL, _βL , ℓitalic_β defined below. By linearity, this bound extends to a bound of the expected win-rate p⁢(x≻y)=u∼[σ⁢(β⋅(u⁢(x)−u⁢(y)))]succeedssubscriptsimilar-to⋅p(x y)= *E_u [σ(β% ·(u(x)-u(y))) ]p ( x ≻ y ) = blackboard_Eu ∼ D [ σ ( β ⋅ ( u ( x ) - u ( y ) ) ) ] by affine expressions in ⁢(x)=u∼[u⁢(x)]subscriptsimilar-to AvgUtil(x)= *E_u [u(x) ]sansserif_AvgUtil ( x ) = blackboard_Eu ∼ D [ u ( x ) ] and ⁢(y)=u∼[u⁢(y)]subscriptsimilar-to AvgUtil(y)= *E_u [u(y) ]sansserif_AvgUtil ( y ) = blackboard_Eu ∼ D [ u ( y ) ]. We defer the lemma’s formal proof to Appendix B. Lemma 1 (Linearization of Expected Win-Rates). Let L≔σ′⁢(0)=1/4≔superscript′014L σ (0)=1/4L ≔ σ′ ( 0 ) = 1 / 4 and ℓβ≔σ⁢(β)−12β=12⁢β⋅1−e−β1+e−β≔subscriptℓ12⋅121superscript1superscript _β σ(β)- 12β= 12β% · 1-e^-β1+e^-βℓitalic_β ≔ divide start_ARG σ ( β ) - divide start_ARG 1 end_ARG start_ARG 2 end_ARG end_ARG start_ARG β end_ARG = divide start_ARG 1 end_ARG start_ARG 2 β end_ARG ⋅ divide start_ARG 1 - e- β end_ARG start_ARG 1 + e- β end_ARG. For any pair of alternatives x,y∈Ax,y∈ Ax , y ∈ A, we have β⋅(ℓβ⋅⁢(x)−L⋅⁢(y))≤p⁢(x≻y)−12≤β⋅(L⋅⁢(x)−ℓβ⋅⁢(y)).⋅subscriptℓ⋅succeeds12⋅subscriptℓ β· ( _β· AvgUtil(x)-L% · AvgUtil(y) )≤ p(x y)- 12≤β· % (L· AvgUtil(x)- _β· AvgUtil(y) ).β ⋅ ( ℓitalic_β ⋅ sansserif_AvgUtil ( x ) - L ⋅ sansserif_AvgUtil ( y ) ) ≤ p ( x ≻ y ) - divide start_ARG 1 end_ARG start_ARG 2 end_ARG ≤ β ⋅ ( L ⋅ sansserif_AvgUtil ( x ) - ℓitalic_β ⋅ sansserif_AvgUtil ( y ) ) . 3.1 Upper Bound on Borda Distortion Siththaranjan et al. (2023) 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 the classic setting (Procaccia and Rosenschein, 2006), we would hope that distortion is more reasonable under our assumptions. Fortunately, Borda indeed has at most O⁢(β2)superscript2O(β^2)O ( β2 ) distortion, which we prove through two applications of our linearization lemma: Theorem 2 (Borda Distortion Upper Bound). For any instance DD with any number of alternatives m, distribution μ over alternatives, and temperature β, Borda has at most distortion (β2⋅1+e−β1−e−β)2=O⁢(β2).superscript⋅21superscript1superscript2superscript2 ( β2· 1+e^-β1-e^-β )^2=O(% β^2).( divide start_ARG β end_ARG start_ARG 2 end_ARG ⋅ divide start_ARG 1 + e- β end_ARG start_ARG 1 - e- β end_ARG )2 = O ( β2 ) . In the finite-sample regime, we have that n⁢()≥(2β⋅1−e−β1+e−β)2⋅maxx⋆∈A⁡⁢(x⋆)−O⁢(1β2⁢log⁡(m⁢n⁢β)n⋅min⁡1,d⁢μmin2+m⁢log⁡(m⁢n⁢β)n⋅β2⁢μmin2).subscript⋅superscript⋅21superscript1superscript2subscriptsuperscript⋆superscript⋆1superscript2⋅1superscriptsubscript2⋅superscript2superscriptsubscript2 AvgUtil_n( Borda)≥ ( 2% β· 1-e^-β1+e^-β )^2· _x % ∈ A AvgUtil(x )-O ( 1β^2 (% mnβ)n· \1,d _ ^2\+ m (mnβ)n·β^% 2 _ ^2 ).sansserif_AvgUtiln ( sansserif_Borda ) ≥ ( divide start_ARG 2 end_ARG start_ARG β end_ARG ⋅ divide start_ARG 1 - e- β end_ARG start_ARG 1 + e- β end_ARG )2 ⋅ maxitalic_x⋆ ∈ A sansserif_AvgUtil ( x⋆ ) - O ( divide start_ARG 1 end_ARG start_ARG β2 end_ARG square-root start_ARG divide start_ARG log ( m n β ) end_ARG start_ARG n ⋅ min 1 , d μroman_min2 end_ARG end_ARG + divide start_ARG m log ( m n β ) end_ARG start_ARG n ⋅ β2 μroman_min2 end_ARG ) . Proof sketch (full proof in Section D.1). For exposition, we sketch this proof for n→∞→n→∞n → ∞, assuming that each alternative’s Borda count has converged to its expectation ⋆⁢(x)≔∑y∈Aμ⁢(y)⋅p⁢(x≻y)≔superscript⋆subscript⋅succeeds BC (x) _y∈ Aμ(y)· p(x y)sansserif_BC⋆ ( x ) ≔ ∑y ∈ A μ ( y ) ⋅ p ( x ≻ y ). Let x^=argmaxx∈A⋆⁢(x)^subscriptargmaxsuperscript⋆ x= *argmax_x∈ A BC (x)over start_ARG x end_ARG = argmaxitalic_x ∈ A sansserif_BC⋆ ( x ) be the Borda winner in the limit, and x⋆=argmaxx∈A⁢(x)superscript⋆subscriptargmaxx = *argmax_x∈ A AvgUtil(x)x⋆ = argmaxitalic_x ∈ A sansserif_AvgUtil ( x ) be the utility maximizer. Applying Lemma 1 to the win-rates p⁢(x^≻y)succeeds^p( x y)p ( over start_ARG x end_ARG ≻ y ) and p⁢(x⋆≻y)succeedssuperscript⋆p(x y)p ( x⋆ ≻ y ) for all y∈Ay∈ Ay ∈ A, we have that ⋆⁢(x^)−12≤superscript⋆^12absent BC ( x)- 12≤sansserif_BC⋆ ( over start_ARG x end_ARG ) - divide start_ARG 1 end_ARG start_ARG 2 end_ARG ≤ ∑y∈Aμ⁢(y)⋅β⁢(L⋅⁢(x^)−ℓβ⋅⁢(y))subscript⋅^⋅subscriptℓ _y∈ Aμ(y)·β (L· % AvgUtil( x)- _β· AvgUtil(y) )∑y ∈ A μ ( y ) ⋅ β ( L ⋅ sansserif_AvgUtil ( over start_ARG x end_ARG ) - ℓitalic_β ⋅ sansserif_AvgUtil ( y ) ) = == β⁢(L⋅⁢(x^)−ℓβ⋅⁢(μ));⋅^⋅subscriptℓ β (L· AvgUtil( x)- _β·% AvgUtil(μ) );β ( L ⋅ sansserif_AvgUtil ( over start_ARG x end_ARG ) - ℓitalic_β ⋅ sansserif_AvgUtil ( μ ) ) ; (1) ⋆⁢(x⋆)−12≥superscript⋆superscript⋆12absent BC (x )- 12≥sansserif_BC⋆ ( x⋆ ) - divide start_ARG 1 end_ARG start_ARG 2 end_ARG ≥ ∑y∈Aμ⁢(y)⋅β⁢(ℓβ⋅⁢(x⋆)−L⋅⁢(y))subscript⋅subscriptℓsuperscript⋆⋅ _y∈ Aμ(y)·β ( _β·% AvgUtil(x )-L· AvgUtil(y) )∑y ∈ A μ ( y ) ⋅ β ( ℓitalic_β ⋅ sansserif_AvgUtil ( x⋆ ) - L ⋅ sansserif_AvgUtil ( y ) ) = == β⁢(ℓβ⋅⁢(x⋆)−L⋅⁢(μ)).⋅subscriptℓsuperscript⋆⋅ β ( _β· AvgUtil(x )-L·% AvgUtil(μ) ).β ( ℓitalic_β ⋅ sansserif_AvgUtil ( x⋆ ) - L ⋅ sansserif_AvgUtil ( μ ) ) . Since ⋆⁢(x^)≥⋆⁢(x⋆)superscript⋆^superscript⋆superscript⋆ BC ( x)≥ BC (x )sansserif_BC⋆ ( over start_ARG x end_ARG ) ≥ sansserif_BC⋆ ( x⋆ ), we obtain from the above two inequalities that L⋅⁢(x^)+(L−ℓβ)⋅⁢(μ)≥ℓβ⋅⁢(x⋆).⋅^⋅subscriptℓ⋅subscriptℓsuperscript⋆ L· AvgUtil( x)+(L- _β)· % AvgUtil(μ)≥ _β· AvgUtil(x ).L ⋅ sansserif_AvgUtil ( over start_ARG x end_ARG ) + ( L - ℓitalic_β ) ⋅ sansserif_AvgUtil ( μ ) ≥ ℓitalic_β ⋅ sansserif_AvgUtil ( x⋆ ) . (2) A standard averaging argument shows that x∼μ⁢[⋆⁢(x)]≥1/2subscriptsimilar-todelimited-[]superscript⋆12E_x μ[ BC (x)]≥ 1/2blackboard_Ex ∼ μ [ sansserif_BC⋆ ( x ) ] ≥ 1 / 2, which implies that ⋆⁢(x^)superscript⋆ BC ( x)sansserif_BC⋆ ( over start_ARG x end_ARG ) must be at least 1/2121/21 / 2. Combining this with Eq. 1, we obtain that ⁢(μ)≤Lℓβ⋅⁢(x^)⋅subscriptℓ AvgUtil(μ)≤ L _β· AvgUtil( x)sansserif_AvgUtil ( μ ) ≤ divide start_ARG L end_ARG start_ARG ℓitalic_β end_ARG ⋅ sansserif_AvgUtil ( over start_ARG x end_ARG ). Substituting this into Equation 2 (noting that L≥ℓβsubscriptℓL≥ _βL ≥ ℓitalic_β), we have that L2ℓβ⁢(x^)=superscript2subscriptℓ^absent L^2 _β AvgUtil( x)=divide start_ARG L2 end_ARG start_ARG ℓitalic_β end_ARG sansserif_AvgUtil ( over start_ARG x end_ARG ) = L⋅⁢(x^)+(L−ℓβ)⁢Lℓβ⋅⁢(x^)⋅^⋅subscriptℓsubscriptℓ L· AvgUtil( x)+ (L- _β)\,L _% β· AvgUtil( x)L ⋅ sansserif_AvgUtil ( over start_ARG x end_ARG ) + divide start_ARG ( L - ℓitalic_β ) L end_ARG start_ARG ℓitalic_β end_ARG ⋅ sansserif_AvgUtil ( over start_ARG x end_ARG ) ≥ ≥ L⋅⁢(x^)+(L−ℓβ)⋅⁢(μ)≥ℓβ⋅⁢(x⋆),⋅^⋅subscriptℓ⋅subscriptℓsuperscript⋆ L· AvgUtil( x)+(L- _β)· % AvgUtil(μ)≥ _β· AvgUtil(x ),L ⋅ sansserif_AvgUtil ( over start_ARG x end_ARG ) + ( L - ℓitalic_β ) ⋅ sansserif_AvgUtil ( μ ) ≥ ℓitalic_β ⋅ sansserif_AvgUtil ( x⋆ ) , which yields the distortion guarantee ⁢(x⋆)⁢(x^)≤(Lℓβ)2=(β2⁢1+e−β1−e−β)2superscript⋆^superscriptsubscriptℓ2superscript21superscript1superscript2 AvgUtil(x ) AvgUtil( x)≤ ( % L _β )^2= ( β2 1+e^-β1-e^-% β )^2divide start_ARG sansserif_AvgUtil ( x⋆ ) end_ARG start_ARG sansserif_AvgUtil ( over start_ARG x end_ARG ) end_ARG ≤ ( divide start_ARG L end_ARG start_ARG ℓitalic_β end_ARG )2 = ( divide start_ARG β end_ARG start_ARG 2 end_ARG divide start_ARG 1 + e- β end_ARG start_ARG 1 - e- β end_ARG )2. ∎ 3.2 Lower Bounds (and Upper Bound for Maximal Lotteries) The upper bound for Borda nested two applications of the linearization lemma. As a result, it twice incurred a distortion factor of Lℓβ=σ′⁢(0)(σ⁢(β)−σ⁢(0))/βsubscriptℓsuperscript′00 L _β= σ (0)(σ(β)-σ(0))/βdivide start_ARG L end_ARG start_ARG ℓitalic_β end_ARG = divide start_ARG σ′ ( 0 ) end_ARG start_ARG ( σ ( β ) - σ ( 0 ) ) / β end_ARG, 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 d=11d=1d = 1 comparisons per user. This distortion occurs even though the voting rule has access to infinitely many pairwise comparison samples, which shows that the nonlinearity of the Bradley-Terry model can cause a loss of the information necessary to find the utility maximizer. The proof (in Section D.3) constructs a user population DD in which a small minority has utility 1 for some special alternative a and 0 for all other alternatives, whereas the majority has a small utility ϵitalic-ϵεϵ 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/2121/21 / 2. Due to the diminishing returns in the sigmoid function, the resulting average utility for a is Lℓβsubscriptℓ L _βdivide start_ARG L end_ARG start_ARG ℓitalic_β end_ARG 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/2121/21 / 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ℓβsubscriptℓ L _βdivide start_ARG L end_ARG start_ARG ℓitalic_β end_ARG distortion. If there are d≥22d≥ 2d ≥ 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≥22d≥ 2d ≥ 2 for all voting rules that put at most 1/m11/m1 / m probability mass on a Condorcet loser, i.e., an alternative x such that #⁢(y≻x)>#⁢(x≻y)#succeeds#succeeds\#(y x)>\#(x y)# ( y ≻ x ) > # ( x ≻ y ) for all y≠xy≠ xy ≠ x. This property generalizes the Condorcet loser criterion and is satisfied by a wide range of voting rules deemed desirable, including Borda and Maximal Lotteries. The proof uses essentially the same instance as above, slightly tipping the expected win-rates against a to make it a Condorcet loser. Since the social choice setting is a special case of alignment, the lower bound extends to alignment. Theorem 3 (Voting Rule-Independent Distortion Lower Bound). Fix any β>00β>0β > 0. If each user provides d=11d=1d = 1 comparison, no voting rule can guarantee distortion better than β2⋅1+e−β1−e−β⋅21superscript1superscript β2· 1+e^-β1-e^-βdivide start_ARG β end_ARG start_ARG 2 end_ARG ⋅ divide start_ARG 1 + e- β end_ARG start_ARG 1 - e- β end_ARG for large m. If each user reports d≥22d≥ 2d ≥ 2 pairwise comparisons, any voting rule that puts at most 1/m11/m1 / m probability mass on a Condorcet loser must have at least the above distortion. The Maximal Lotteries voting rule exactly matches the above lower bound of β2⋅1+e−β1−e−β⋅21superscript1superscript β2· 1+e^-β1-e^-βdivide start_ARG β end_ARG start_ARG 2 end_ARG ⋅ divide start_ARG 1 + e- β end_ARG start_ARG 1 - e- β end_ARG. We omit the proof here, as it follows as a direct corollary of NLHF’s upper bound (Theorem 7) in the next section. Corollary 4 (of Theorem 7). The Maximal Lotteries voting rule has a distortion of β2⋅1+e−β1−e−β⋅21superscript1superscript β2· 1+e^-β1-e^-βdivide start_ARG β end_ARG start_ARG 2 end_ARG ⋅ divide start_ARG 1 + e- β end_ARG start_ARG 1 - e- β end_ARG. 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 Section D.2. Theorem 5 (Borda Distortion Lower Bound, Informally). For any β>00β>0β > 0 and m≥33m≥ 3m ≥ 3, the distortion guaranteed by Borda (and, hence, RLHF) is greater than and bounded away from β2⁢1+e−β1−e−β21superscript1superscript β2 1+e^-β1-e^-βdivide start_ARG β end_ARG start_ARG 2 end_ARG divide start_ARG 1 + e- β end_ARG start_ARG 1 - e- β end_ARG. In particular, as β→∞→β→∞β → ∞, this distortion guarantee is at least (1−o⁢(1))⋅β⋅11(1-o(1))·β( 1 - o ( 1 ) ) ⋅ β. 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 our view, a major drawback of the distortion framework (with nonnegative utilities) is that it leads to unreasonably high distortion, and some unnatural prescriptions. For example, any deterministic voting rule has distortion Ω⁢(m2)Ωsuperscript2 (m^2)Ω ( m2 ), where optimal distortion is achieved by Plurality (Caragiannis and Procaccia, 2011) (a rule widely disregarded by social choice theorists) wheras Borda and all Condorcet consistent rules have infinite distortion (Procaccia and Rosenschein, 2006). These limitations may explain in part why recent research activity (e.g., Gkatzelis et al., 2020; Charikar et al., 2024; Goyal and Sarmasarkar, 2025) has focused on the metric distortion setting (Anshelevich et al., 2018, 2021), in which many natural voting rules have constant distortion. But 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 x and y, and j has high utility for x, then j must also have high utility for y, 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. For the AI community, our social-choice distortion results also have implications beyond being a special case of alignment. A notable example is Chatbot Arena’s evaluation of language models (Chiang et al., 2024), 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 reward. As in the alignment setting, this approach assumes a 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 DD captures a 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 AvgUtilsansserif_AvgUtil quantified the average utility a model delivers for a random user and task, which we call the model’s usability in this section. Since Chatbot Arena and RLHF are 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))⋅β⋅11(1-o(1))·β( 1 - o ( 1 ) ) ⋅ β times worse than the usability of some other ranked model (Theorem 5) (but at most by a O⁢(β2)superscript2O(β^2)O ( β2 ) factor, see Theorem 2). Our later results in an extended setting in which comparison pairs are drawn in a correlated way (Section 5) show that Chatbot Arena’s ranking is highly sensitive to the distribution of LLM pairs. For certain correlated distributions, the gap in usability could be unbounded (Theorem 9), 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 distribution? Does adaptive sampling introduce systematic biases that exacerbate the distortion of current pipelines? Addressing these questions is an important direction for future work to ensure the fidelity of leaderboard-based evaluations. 4 AI Alignment with KL Constraint We now tackle the general alignment setting, in which the output policy π must be chosen within a prescribed KL divergence of the reference policy πrefsubscriptref _refπref. 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 a finite KL budget. 4.1 Lower Bound for RLHF Before presenting the optimal distortion upper bound for NLHF, we illustrate the pitfalls of the alignment setting with a lower bound on RLHF. This bound shows that a KL constraint can cause RLHF to have exponential distortion in β, exceeding its quadratic upper bound in the social choice setting (Theorem 2). Theorem 6 (RLHF Distortion Lower Bound). For m≥33m≥ 3m ≥ 3, there is a sequence of alignment problems on which the distortion of RLHF scales as eΩ⁢(β)superscriptΩe (β)eroman_Ω ( β ) in β. Proof sketch (full proof in Section E.2). For ease of exposition, consider an instance with three alternatives a,b,ca,b,ca , b , c where μ⁢(c)μ(c)μ ( c ) is about eβsuperscripte^βeitalic_β times larger than μ⁢(a)=μ⁢(b)μ(a)=μ(b)μ ( a ) = μ ( b ).999To avoid such unbalanced μ, one could equivalently copy alternative c many times and let μ be uniform. Let the population consist of a tiny minority (a Θ⁢(eβ)Θsuperscript (e^β)Θ ( eitalic_β ) fraction) with utilities u⁢(a)=0,u⁢(b)=1,u⁢(c)=0formulae-sequence0formulae-sequence10u(a)=0,u(b)=1,u(c)=0u ( a ) = 0 , u ( b ) = 1 , u ( c ) = 0, and a large majority with utilities u⁢(a)=1β,u⁢(b)=0,u⁢(c)=1formulae-sequence1formulae-sequence01u(a)= 1β,u(b)=0,u(c)=1u ( a ) = divide start_ARG 1 end_ARG start_ARG β end_ARG , u ( b ) = 0 , u ( c ) = 1. Both a and b 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)succeedssucceedsp(b c)>p(a c)p ( b ≻ c ) > p ( a ≻ c ), i.e., we can make b’s advantage of being preferred by the minority outweigh a’s advantage of being slightly less dispreferred by the majority. Since μ⁢(c)μ(c)μ ( c ) is so much larger than μ⁢(a),μ⁢(b)μ(a),μ(b)μ ( a ) , μ ( b ), the vast majority of pairwise comparisons involving a or b are against c. As a result, the MLE reward for b will be higher than for a, even though ⁢(a)=Θ⁢(1β)Θ1 AvgUtil(a)= ( 1β)sansserif_AvgUtil ( a ) = Θ ( divide start_ARG 1 end_ARG start_ARG β end_ARG ) is exponentially larger than ⁢(b)=Θ⁢(eβ)Θsuperscript AvgUtil(b)= (e^β)sansserif_AvgUtil ( b ) = Θ ( eitalic_β ). (In the social choice setting, this would not be a problem because c has even higher average utility and higher reward.) The lower bound arises for a reference policy that puts a tiny probability mass ε ε on c, and 1−ε212 1- 2divide start_ARG 1 - ε end_ARG start_ARG 2 end_ARG probability mass each on a and b, together with a KL constraint of τ=log⁡22τ= 2τ = log 2. Now DKL⁢(π∥πref)=π⁢(a)⁢log⁡π⁢(a)(1−ε)/2+π⁢(b)⁢log⁡π⁢(b)(1−ε)/2+π⁢(c)⁢log⁡π⁢(c)εsubscriptKLconditionalsubscriptref1212D_KL(π\,\|\, _ref)=π(a) π(a)(1-% )/2+π(b) π(b)(1- )/2+π(c) π% (c) DKL ( π ∥ πref ) = π ( a ) log divide start_ARG π ( a ) end_ARG start_ARG ( 1 - ε ) / 2 end_ARG + π ( b ) log divide start_ARG π ( b ) end_ARG start_ARG ( 1 - ε ) / 2 end_ARG + π ( c ) log divide start_ARG π ( c ) end_ARG start_ARG ε end_ARG. Since ε ε is very small, π⁢(c)π(c)π ( c ) cannot be increased by enough to make a meaningful difference on the achievable utility; but the KL 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 π’s mass on b, which yields exponentially less utility than the utility-maximizing policy in the KL ball, which puts almost all mass on a. ∎ This bound formalizes a key limitation of the reward-based approach inherent to RLHF. The MLE phase of RLHF attempts to fit rewards to the observed comparisons, whose frequencies are determined by μ. 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\a,b\ a , b for higher accuracy of comparisons involving c. By placing so little mass on c, our choice of πrefsubscriptref _refπref forces RLHF to choose between the misrepresented alternatives a and b, causing it to make a high-distortion choice. Our lower bound exploits that the distribution μ governing the frequencies of comparison pairs differs greatly from the reference policy πrefsubscriptref _refπref. We leave open to characterize RLHF’s distortion under the assumption that μ=πrefsubscriptrefμ= _refμ = πref, 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 πrefsubscriptref _refπref can lead RLHF towards highly suboptimal policies, NLHF has no such problem. Below, we show that, across all settings of our model, NLHF’s 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 linearization lemma. It also highlights a key advantage over RLHF’s reward-based approach: Since the NLHF policy is computed as a 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 utility-maximizing benchmark π⋆superscript⋆π π⋆. Since the social choice setting is a 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. Theorem 7 (NLHF Distortion Upper Bound). For any instance DD and any m, data distribution μ, temperature β of the Bradley-Terry model, and any reference policy πrefsubscriptref _refπref and KL budget τ, we have ⁢()≤β2⋅1+e−β1−e−β.⋅21superscript1superscriptdist( NLHF)≤ β2· 1+e^-β1-e^-% β.dist ( sansserif_NLHF ) ≤ divide start_ARG β end_ARG start_ARG 2 end_ARG ⋅ divide start_ARG 1 + e- β end_ARG start_ARG 1 - e- β end_ARG . In the finite-sample regime, we have n⁢()≥(2β⋅1−e−β1+e−β)⋅maxπ⋆∈Bτ⁢(πref)⁡⁢(π⋆)−O⁢(1β⁢log⁡(m⁢n)n⋅min⁡1,d⋅μmin2+log⁡(m⁢n)n⋅β⁢μmin2).subscript⋅21superscript1superscriptsubscriptsuperscript⋆subscriptsubscriptrefsuperscript⋆1⋅1⋅superscriptsubscript2⋅superscriptsubscript2 AvgUtil_n( NLHF)≥ ( 2% β· 1-e^-β1+e^-β )· _π ∈ B% _τ( _ref) AvgUtil(π )-O ( 1β% (mn)n· \1,\,d· _ ^2\+ (mn)% n·β _ ^2 ).sansserif_AvgUtiln ( sansserif_NLHF ) ≥ ( divide start_ARG 2 end_ARG start_ARG β end_ARG ⋅ divide start_ARG 1 - e- β end_ARG start_ARG 1 + e- β end_ARG ) ⋅ maxitalic_π⋆ ∈ B start_POSTSUBSCRIPT τ ( πref ) end_POSTSUBSCRIPT sansserif_AvgUtil ( π⋆ ) - O ( divide start_ARG 1 end_ARG start_ARG β end_ARG square-root start_ARG divide start_ARG log ( m n ) end_ARG start_ARG n ⋅ min 1 , d ⋅ μroman_min2 end_ARG end_ARG + divide start_ARG log ( m n ) end_ARG start_ARG n ⋅ β μroman_min2 end_ARG ) . Proof sketch (full proof in Section E.1). For exposition, we assume that the NLHF method knows the expected win-rates p⁢(x≻y)succeedsp(x y)p ( x ≻ y ), and defer the proof of finite-sample guarantees. Hence, the NLHF policy by definition satisfies π∈argmaxπ1∈Bτ⁢(πref)minπ2∈Bτ⁢(πref)⁡x1∼π1,x2∼π2⁢[p⁢(x1≻x2)−p⁢(x2≻x1)].subscriptsubscriptargmaxsubscript1subscriptsubscriptrefsubscriptsubscript2subscriptsubscriptrefsubscriptformulae-sequencesimilar-tosubscript1subscript1similar-tosubscript2subscript2delimited-[]succeedssubscript1subscript2succeedssubscript2subscript1 _ NLHF∈ *argmax_ _1∈ B_τ( _% ref) _ _2∈ B_τ( _ref)E_x_1 _1% ,x_2 _2[p(x_1 x_2)-p(x_2 x_1)].πsansserif_NLHF ∈ argmaxitalic_π start_POSTSUBSCRIPT 1 ∈ Bitalic_τ ( πref ) end_POSTSUBSCRIPT minitalic_π start_POSTSUBSCRIPT 2 ∈ Bitalic_τ ( πref ) end_POSTSUBSCRIPT blackboard_Ex start_POSTSUBSCRIPT 1 ∼ π1 , x2 ∼ π2 end_POSTSUBSCRIPT [ p ( x1 ≻ x2 ) - p ( x2 ≻ x1 ) ] . Since this describes a Nash-equilibrium strategy for a symmetric two-player zero-sum game, and any such game has value 0, it must hold that minπ2∈Bτ⁢(πref)⁡x1∼π,x2∼π2⁢[p⁢(x1≻x2)−p⁢(x2≻x1)]=0.subscriptsubscript2subscriptsubscriptrefsubscriptformulae-sequencesimilar-tosubscript1subscriptsimilar-tosubscript2subscript2delimited-[]succeedssubscript1subscript2succeedssubscript2subscript10 _ _2∈ B_τ( _ref)E_x_1 _ % NLHF,x_2 _2[p(x_1 x_2)-p(x_2 x_1)]=0.minitalic_π start_POSTSUBSCRIPT 2 ∈ Bitalic_τ ( πref ) end_POSTSUBSCRIPT blackboard_Ex start_POSTSUBSCRIPT 1 ∼ πsansserif_NLHF , x2 ∼ π2 end_POSTSUBSCRIPT [ p ( x1 ≻ x2 ) - p ( x2 ≻ x1 ) ] = 0 . Plugging in p⁢(x1≻x2)−p⁢(x2≻x1)=2⁢p⁢(x1≻y1)−1succeedssubscript1subscript2succeedssubscript2subscript12succeedssubscript1subscript11p(x_1 x_2)-p(x_2 x_1)=2\,p(x_1 y_1)-1p ( x1 ≻ x2 ) - p ( x2 ≻ x1 ) = 2 p ( x1 ≻ y1 ) - 1, we obtain minπ2∈Bτ⁢(πref)⁢x1∼π,x2∼π2[p⁢(x1≻x2)−12]=0.subscriptsubscript2subscriptsubscriptrefsubscriptformulae-sequencesimilar-tosubscript1subscriptsimilar-tosubscript2subscript2succeedssubscript1subscript2120 _ _2∈ B_τ( _ref) *E_x_1% _ NLHF,x_2 _2 [p(x_1 x_2)- 12% ]=0.minitalic_π start_POSTSUBSCRIPT 2 ∈ Bitalic_τ ( πref ) end_POSTSUBSCRIPT blackboard_Ex start_POSTSUBSCRIPT 1 ∼ πsansserif_NLHF , x2 ∼ π2 end_POSTSUBSCRIPT [ p ( x1 ≻ x2 ) - divide start_ARG 1 end_ARG start_ARG 2 end_ARG ] = 0 . Using the utility-maximizing policy π⋆≔argmaxπ∈Bτ⁢(πref)⁢(π)≔superscript⋆subscriptargmaxsubscriptsubscriptrefπ *argmax_π∈ B_τ( _ref)% AvgUtil(π)π⋆ ≔ argmaxitalic_π ∈ B start_POSTSUBSCRIPT τ ( πref ) end_POSTSUBSCRIPT sansserif_AvgUtil ( π ) for π2subscript2 _2π2, we obtain that x1∼π,x2∼π⋆⁢[p⁢(x1≻x2)−12]≥0subscriptformulae-sequencesimilar-tosubscript1subscriptsimilar-tosubscript2superscript⋆delimited-[]succeedssubscript1subscript2120E_x_1 _ NLHF,x_2 π [p(x_1 x_% 2)- 12]≥ 0blackboard_Ex start_POSTSUBSCRIPT 1 ∼ πsansserif_NLHF , x2 ∼ π⋆ end_POSTSUBSCRIPT [ p ( x1 ≻ x2 ) - divide start_ARG 1 end_ARG start_ARG 2 end_ARG ] ≥ 0. At this point, we upper bound the win-rate with the linearization lemma (Lemma 1), and obtain 0≤0absent 0≤0 ≤ x1∼π,x2∼π⋆⁢[β⋅(L⋅⁢(x1)−ℓβ⋅⁢(x2))]subscriptformulae-sequencesimilar-tosubscript1subscriptsimilar-tosubscript2superscript⋆delimited-[]⋅subscript1⋅subscriptℓsubscript2 _x_1 _ NLHF,x_2 π % [β· (L· AvgUtil(x_1)- _β· % AvgUtil(x_2) ) ]blackboard_Ex start_POSTSUBSCRIPT 1 ∼ πsansserif_NLHF , x2 ∼ π⋆ end_POSTSUBSCRIPT [ β ⋅ ( L ⋅ sansserif_AvgUtil ( x1 ) - ℓitalic_β ⋅ sansserif_AvgUtil ( x2 ) ) ] = == β⋅(L⋅⁢(π)−ℓβ⋅⁢(π⋆)).⋅subscript⋅subscriptℓsuperscript⋆ β· (L· AvgUtil( _ NLHF)- _% β· AvgUtil(π ) ).β ⋅ ( L ⋅ sansserif_AvgUtil ( πsansserif_NLHF ) - ℓitalic_β ⋅ sansserif_AvgUtil ( π⋆ ) ) . This implies that ⁢(π⋆)⁢(π)≤Lℓβ=β2⋅1+e−β1−e−β=O⁢(β)superscript⋆subscriptsubscriptℓ⋅21superscript1superscript AvgUtil(π ) AvgUtil( _ NLHF)% ≤ L _β= β2· 1+e^-β1-e^-β% =O(β)divide start_ARG sansserif_AvgUtil ( π⋆ ) end_ARG start_ARG sansserif_AvgUtil ( πsansserif_NLHF ) end_ARG ≤ divide start_ARG L end_ARG start_ARG ℓitalic_β end_ARG = divide start_ARG β end_ARG start_ARG 2 end_ARG ⋅ divide start_ARG 1 + e- β end_ARG start_ARG 1 - e- β end_ARG = O ( β ), thus completing the proof. ∎ 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τ⁢(πref)subscriptsubscriptrefB_τ( _ref)Bitalic_τ ( πref ) is a closed convex set (to ensure the existence of a Nash equilibrium). Consequently, the distortion bound of Nash learning extends to other ways of constraining proximity to the reference policy, such as by χ2superscript2χ^2χ2 divergence (Huang et al., 2024). 5 Extensions of the Model KL Constraints vs. Regularization. In our model, we defined alignment methods as taking in an explicit KL bound τ as an input parameter, which is convenient for comparing the policy against a 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 a policy π maximizing the regularized objective x∼π⁢[r⁢(x)]−λ⁢DKL⁢(π∥πref)subscriptsimilar-todelimited-[]subscriptKLconditionalsubscriptrefE_x π[r(x)]-λ D_KL(π\,\|\, _ref)blackboard_Ex ∼ π [ r ( x ) ] - λ DKL ( π ∥ πref ), and the payoff matrix in the game solved by NLHF is x1∼π1,x2∼π2⁢[Mx1,x2]−λ⁢DKL⁢(π1∥πref)+λ⁢DKL⁢(π2∥πref)subscriptformulae-sequencesimilar-tosubscript1subscript1similar-tosubscript2subscript2delimited-[]subscriptsubscript1subscript2subscriptKLconditionalsubscript1subscriptrefsubscriptKLconditionalsubscript2subscriptrefE_x_1 _1,x_2 _2[M_x_1,x_2]-λ D_% KL( _1\,\|\, _ref)+λ D_KL( _2\,\|\,% _ref)blackboard_Ex start_POSTSUBSCRIPT 1 ∼ π1 , x2 ∼ π2 end_POSTSUBSCRIPT [ Mitalic_x start_POSTSUBSCRIPT 1 , x2 end_POSTSUBSCRIPT ] - λ DKL ( π1 ∥ πref ) + λ DKL ( π2 ∥ πref ), where λ≥00λ≥ 0λ ≥ 0 is a regularization parameter given to the alignment method instead of τ. We prove in Section E.4 that the regularized and constrained versions of RLHF and NLHF are equivalent. That is, each policy π returned by the λ-regularized version of a method is optimal for the τ-constrained version for τ=DKL⁢(π∥πref)subscriptKLconditionalsubscriptrefτ=D_KL(π\,\|\, _ref)τ = DKL ( π ∥ πref ) (and any policy returned by the τ-constrained version is optimal for the λ-regularized version and some λ≥00λ≥ 0λ ≥ 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 λ-regularized alignment method, π is optimal for the τ=DKL⁢(π∥πref)subscriptKLconditionalsubscriptrefτ\!=\!D_KL(π\,\|\, _ref)τ = DKL ( π ∥ πref )-constrained version by equivalence, at which point the distortion upper bound shows that π can compete with any policy with no larger KL divergence from πrefsubscriptref _refπref.101010Why not define distortion by flexibly selecting the benchmark based on the output policy’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 0, we would benchmark it only against the reference policy, i.e., itself. Applying this observation to Theorem 7, we obtain the following guarantee for regularized NLHF: Corollary 8. If λ-regularized NLHF (for any λ≥00λ≥ 0λ ≥ 0) returns a policy π~subscript~ π_ NLHFover~ start_ARG π end_ARGsansserif_NLHF, this policy’s average utility is at least a 2β⋅1−e−β1+e−β⋅21superscript1superscript 2β· 1-e^-β1+e^-βdivide start_ARG 2 end_ARG start_ARG β end_ARG ⋅ divide start_ARG 1 - e- β end_ARG start_ARG 1 + e- β end_ARG fraction of the optimal average utility of any policy π with DKL⁢(π∥πref)≤DKL⁢(π~∥πref)subscriptKLconditionalsubscriptrefsubscriptKLconditionalsubscript~subscriptrefD_KL(π\,\|\, _ref)≤ D_KL( π_% NLHF\,\|\, _ref)DKL ( π ∥ πref ) ≤ DKL ( over~ start_ARG π end_ARGsansserif_NLHF ∥ πref ) (minus finite-sample errors, see Theorem 7). Sampling of Comparison Pairs. In our model, we assume that each voter provides d pairwise comparisons, where both members xij,yijsuperscriptsubscriptsuperscriptsubscriptx_i^j,y_i^jxitalic_iitalic_j , yitalic_iitalic_j of each comparison pair are sampled i.i.d. from μ. More generally, we can model xij,yij∼νsimilar-tosuperscriptsubscriptsuperscriptsubscript\x_i^j,y_i^j\ ν xitalic_iitalic_j , yitalic_iitalic_j ∼ ν where ν is a distribution over unordered alternative pairs, or even a distribution over d pairs of alternatives from which xi1,yi1,…,xid,yidsuperscriptsubscript1superscriptsubscript1…superscriptsubscriptsuperscriptsubscript\x_i^1,y_i^1,…,x_i^d,y_i^d\ xitalic_i1 , yitalic_i1 , … , xitalic_iitalic_d , yitalic_iitalic_d are sampled. (To keep 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=(r2)binomial2d= r2d = ( FRACOP start_ARG r end_ARG start_ARG 2 end_ARG ) are all pairs inside a 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 7)111111The finite-sample bounds even improve in the latter model since each pair appears only once.. Given that our proofs continue to work out, the only “disadvantage” of these stronger models for sampling comparison pairs is that, without a distribution μ, the Borda voting rule is no longer defined (and we see no obvious way to generalize the Borda–MLE equivalence (Siththaranjan et al., 2023; Procaccia et al., 2025)). It seems that RLHF does not only become harder to analyze under these comparison-pair models, but actually performs worse: we show in Appendix F that RLHF can have a distortion that is not bounded in β in these extended models, leading to an even clearer separation with NLHF. Theorem 9 (Unbounded Distortion of RLHF Under Correlated Sampling). For any β>00β>0β > 0, there exists a sequence of alignment instances and distributions ν∈Δ⁢((A2))Δbinomial2ν∈ ( A2 )ν ∈ Δ ( ( FRACOP start_ARG A end_ARG start_ARG 2 end_ARG ) ) over comparison pairs such that RLHF’s distortion is unbounded. 6 Discussion In this paper, we introduced the notion of distortion for AI alignment. We showed that one such alignment method, NLHF, obtains the optimal distortion guarantee of (12+o⁢(1))⁢β121( 12+o(1))\,β( divide start_ARG 1 end_ARG start_ARG 2 end_ARG + o ( 1 ) ) β. Putting this bound into perspective, if we assume that a user will rate a minimally preferred alternative over a maximally preferred alternative with 1%percent11\%1 % probability, this suggests a value of β=log⁡99%1%≈4.60percent99percent14.60β= 99\%1\%≈ 4.60β = log divide start_ARG 99 % end_ARG start_ARG 1 % end_ARG ≈ 4.60 and a distortion guarantee of about 2.342.342.342.34, which is a quite reasonable worst-case guarantee. 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 are not drawn i.i.d.. Given the ubiquity of RLHF, characterizing its distortion is a pressing open question, especially when the distribution μ for drawing comparison pairs coincides with the reference policy, or finding similar assumptions that guarantee a lower distortion. A major technical difficulty in this is that bounding this distortion requires reasoning not only about the relative ordering of rewards but also their magnitudes. 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 take into account the generalization of preferences across states? Can the lower bound on distortion be overcome with a little additional information? Finally: can we extend our model to go beyond average utility and measure fairness?121212The concept of distortion of proportional fairness by Ebadian et al. (2024b) points in one possible direction. After all, high average utility is necessary, but not sufficient, for successful alignment to a heterogeneous population. Acknowledgments 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 of Naval Research under grant N00014-24-1-2159, an Alfred P. Sloan fellowship, and a Schmidt Sciences AI2050 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] AI Incident Database. URL https://incidentdatabase.ai/. Alvo and Philip [2014] Mayer Alvo and LH Philip. Statistical methods for ranking data, volume 1341. Springer, 2014. Anshelevich et al. [2018] Elliot Anshelevich, Onkar Bhardwaj, Edith Elkind, John Postl, and Piotr Skowron. Approximating optimal social choice under metric preferences. Artificial Intelligence, 264:27–51, 2018. Anshelevich et al. [2021] Elliot Anshelevich, Aris Filos-Ratsikas, Nisarg Shah, and Alexandros A. Voudouris. Distortion in social choice problems: The first 15 years and beyond. In Zhi-Hua Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, pages 4294–4301, 2021. Azar et al. [2024] 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. Azari Soufiani et al. [2014] Hossein Azari Soufiani, David C Parkes, and Lirong Xia. A statistical decision-theoretic framework for social choice. Advances in Neural Information Processing Systems, 27, 2014. Bai et al. [2022a] Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al. Training a helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint arXiv:2204.05862, 2022a. Bai et al. [2022b] 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.08073, 2022b. Benade et al. [2021] Gerdus Benade, Swaprava Nath, Ariel D. Procaccia, and Nisarg Shah. Preference elicitation for participatory budgeting. Management Science, 67(5):2813–2827, 2021. Boutilier et al. [2012] 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. ACM, 2012. Calandriello et al. [2024] Daniele Calandriello, Zhaohan Daniel Guo, Remi Munos, Mark Rowland, Yunhao Tang, Bernardo Avila Pires, Pierre Harvey Richemond, Charline Le Lan, Michal Valko, Tianqi Liu, et 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. Caragiannis and Procaccia [2011] Ioannis Caragiannis and Ariel D. Procaccia. Voting almost maximizes social welfare despite limited communication. Artificial Intelligence, 175(9-10):1655–1671, 2011. Chakraborty et al. [2024] Souradip Chakraborty, Jiahao Qiu, Hui Yuan, Alec Koppel, Furong Huang, Dinesh Manocha, Amrit Singh Bedi, and Mengdi Wang. Maxmin-RLHF: Alignment with diverse human preferences. arXiv preprint arXiv:2402.08925, 2024. Charikar et al. [2024] Moses Charikar, Prasanna Ramakrishnan, Kangning Wang, and Hongxun Wu. Breaking the Metric Voting Distortion Barrier. Journal of the ACM, 71(6):1–33, 2024. Chen et al. [2024] Daiwei Chen, Yi Chen, Aniket Rege, and Ramya Korlakai Vinayak. Pal: Pluralistic alignment framework for learning from heterogeneous preferences. arXiv preprint arXiv:2406.08469, 2024. Chiang et al. [2024] Wei-Lin Chiang, Lianmin 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 llms by human preference. In Forty-first International Conference on Machine Learning, 2024. Chidambaram et al. [2024] Keertana Chidambaram, Karthik Vinay Seetharaman, and Vasilis Syrgkanis. Direct preference optimization with unobserved preference heterogeneity. arXiv preprint arXiv:2405.15065, 2024. Christiano et al. [2017] Paul F 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. Conitzer and Sandholm [2005] Vincent Conitzer and Tuomas Sandholm. Common voting rules as maximum likelihood estimators. In Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence, pages 145–152, 2005. Conitzer et al. [2024] 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 41st International Conference on Machine Learning, pages 9346–9360, 2024. Dai and Fleisig [2024] Jessica Dai and Eve Fleisig. Mapping social choice theory to RLHF. In ICLR 2024 Workshop on Reliable and Responsible Foundation Models, 2024. Ebadian et al. [2024a] 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, 2024a. Ebadian et al. [2024b] 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, 2024b. Ethayarajh et al. [2024] Kawin Ethayarajh, Winnie Xu, Niklas Muennighoff, Dan Jurafsky, and Douwe Kiela. KTO: Model alignment as prospect theoretic optimization. arXiv preprint arXiv:2402.01306, 2024. Fishburn [1984] Peter C. Fishburn. Probabilistic social choice based on simple voting comparisons. The Review of Economic Studies, 51(4):683–692, 1984. Flanigan et al. [2023] Bailey Flanigan, Ariel D Procaccia, and Sven Wang. Distortion Under Public-Spirited Voting. In Proceedings of the 24th ACM Conference on Economics and Computation, EC ’23, page 700. Association for Computing Machinery, 2023. Ge et al. [2024] Luise Ge, Daniel Halpern, Evi Micha, Ariel D Procaccia, Itai Shapira, Yevgeniy Vorobeychik, and Junlin Wu. Axioms for AI alignment from human feedback. arXiv preprint arXiv:2405.14758, 2024. Gkatzelis et al. [2020] Vasilis Gkatzelis, Daniel Halpern, and Nisarg Shah. Resolving the optimal metric distortion conjecture. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1427–1438. IEEE, 2020. Goyal and Sarmasarkar [2025] Mohak Goyal and Sahasrajit Sarmasarkar. Metric distortion under probabilistic voting. arXiv preprint arXiv:2405.14223v4, 2025. Huang et al. [2024] Audrey Huang, Wenhao Zhan, Tengyang Xie, Jason D Lee, Wen Sun, Akshay Krishnamurthy, and Dylan J Foster. Correcting the mythos of KL-regularization: Direct alignment without overoptimization via chi-squared preference optimization. arXiv preprint arXiv:2407.13399, 2024. Kizilkaya and Kempe [2022] 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. International Joint Conferences on Artificial Intelligence Organization, 2022. Liu et al. [2024] 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 Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. Maura-Rivero et al. [2025] Roberto-Rafael Maura-Rivero, Marc Lanctot, Francesco Visin, and Kate Larson. Jackpot! alignment as a maximal lottery. arXiv preprint arXiv:2501.19266, 2025. Meng et al. [2024] Yu Meng, Mengzhou Xia, and Danqi Chen. SimPO: Simple preference optimization with a reference-free reward. Advances in Neural Information Processing Systems, 37:124198–124235, 2024. Mishra [2023] Abhilash Mishra. Ai alignment and social choice: Fundamental limitations and policy implications. arXiv preprint arXiv:2310.16048, 2023. Munos et al. [2024] Remi Munos, Michal Valko, Daniele Calandriello, Mohammad Gheshlaghi Azar, Mark Rowland, Zhaohan Daniel Guo, Yunhao Tang, Matthieu Geist, Thomas Mesnard, Côme Fiegel, et al. Nash learning from human feedback. In International Conference on Machine Learning, pages 36743–36768. PMLR, 2024. Noothigattu et al. [2020] Ritesh Noothigattu, Dominik Peters, and Ariel D Procaccia. Axioms for learning from pairwise comparisons. Advances in Neural Information Processing Systems, 33:17745–17754, 2020. Ouyang et al. [2022] 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–27744, 2022. Park et al. [2024] 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. Poddar et al. [2024] Sriyash Poddar, Yanming Wan, Hamish Ivison, Abhishek Gupta, and Natasha Jaques. Personalizing reinforcement learning from human feedback with variational preference learning. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. Procaccia and Rosenschein [2006] 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. Procaccia et al. [2025] Ariel D Procaccia, Benjamin Schiffer, and Shirley Zhang. Clone-robust ai alignment. arXiv preprint arXiv:2501.09254, 2025. Rafailov et al. [2023] 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. Schulman et al. [2017] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017. Shirali et al. [2025] Ali Shirali, Arash Nasr-Esfahany, Abdullah Alomar, Parsa Mirtaheri, Rediet Abebe, and Ariel Procaccia. Direct alignment with heterogeneous preferences. arXiv preprint arXiv:2502.16320, 2025. Siththaranjan et al. [2023] Anand Siththaranjan, Cassidy Laidlaw, and Dylan Hadfield-Menell. Distributional preference learning: Understanding and accounting for hidden context in RLHF. arXiv preprint arXiv:2312.08358, 2023. Sorensen et al. [2024] Taylor Sorensen, Jared Moore, Jillian Fisher, Mitchell Gordon, Niloofar Mireshghallah, Christopher Michael Rytting, Andre Ye, Liwei Jiang, Ximing Lu, Nouha Dziri, et al. Position: a roadmap to pluralistic alignment. In Proceedings of the 41st International Conference on Machine Learning, pages 46280–46302, 2024. Swamy et al. [2024] Gokul Swamy, Christoph Dann, Rahul Kidambi, Zhiwei Steven Wu, and Alekh Agarwal. A minimaximalist approach to reinforcement learning from human feedback. arXiv preprint arXiv:2401.04056, 2024. Tatli et al. [2024] 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. Wang et al. [2023] Yuanhao Wang, Qinghua Liu, and Chi Jin. Is RLHF more difficult than standard RL? a theoretical perspective. Advances in Neural Information Processing Systems, 36:76006–76032, 2023. Wang et al. [2024] 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. Wu et al. [2024] Yue Wu, Zhiqing Sun, Huizhuo Yuan, Kaixuan Ji, Yiming Yang, and Quanquan Gu. Self-play preference optimization for language model alignment. arXiv preprint arXiv:2405.00675, 2024. Xia [2018] Lirong Xia. Bayesian estimators as voting rules. In Uncertainty in artificial intelligence, 2018. Xia [2019] Lirong Xia. Learning and decision-making from rank data. Morgan & Claypool Publishers, 2019. Zhang et al. [2022] Xiaomin Zhang, Xucheng Zhang, Po-Ling Loh, and Yingyu Liang. On the identifiability of mixtures of ranking models. arXiv preprint arXiv:2201.13132, 2022. Zhao and Xia [2019] Zhibing Zhao and Lirong Xia. Learning mixtures of plackett-luce models from structured partial orders. Advances in Neural Information Processing Systems, 32, 2019. Zhao et al. [2016] 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, 2016. PMLR. Zhong et al. [2024] Huiying Zhong, Zhun Deng, Weijie J Su, Zhiwei Steven Wu, and Linjun Zhang. Provable multi-party reinforcement learning with diverse human feedback. arXiv preprint arXiv:2403.05006, 2024. Ziegler et al. [2019] 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 arXiv:1909.08593, 2019. Appendix A Additional Related Work Reward-based and reward-free alignment methods. The RLHF pipeline typically includes first training a reward model via maximum likelihood estimation (MLE), then applying RL algorithms such as Proximal Policy Optimization (PPO) [Schulman et al., 2017] to optimize a policy that maximizes the reward [Ziegler et al., 2019, Bai et al., 2022a]. Rafailov et al. [2023] 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 a single Bradley–Terry model, we show in Section E.4 that the equivalence extends to settings with heterogeneous preferences. Building on the DPO framework, several recent methods including χPO [Huang et al., 2024], RPO [Liu et al., 2024] and SimPO [Meng et al., 2024] have been proposed to improve the robustness and effectiveness. Azar et al. [2024] introduce Ψ ΨPO, another reward-free method that optimizes the expectation of a Ψ Ψ-transformation of the win-rates estimated from the offline comparison data. When Ψ Ψ is the identity function, the resulting method — IPO — reduces to directly optimizing the normalized Borda count. Since RLHF is implicitly optimizing the normalized Borda count [Siththaranjan et al., 2023, Procaccia et al., 2025], this connection implies that IPO, DPO, and RLHF are all equivalent in the unregularized/unconstrained setting. Another reward-free method is Nash Learning from Human Feedback (NLHF) [Munos et al., 2024] and its variants [Swamy et al., 2024, Wu et al., 2024, Calandriello et al., 2024], which finds the Nash equilibrium of a game defined over the win-rate margins (i.e., p⁢(x≻y)−p⁢(y≻x)succeedssucceedsp(x y)-p(y x)p ( x ≻ y ) - p ( y ≻ x )) via online learning or self-play style algorithms. Maura-Rivero et al. [2025] point out that NLHF can be viewed as a natural generalization of the Maximal Lotteries rule in social choice. Wang et al. [2023] 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 AI alignment under heterogeneous user preferences. Siththaranjan et al. [2023] 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), a method that estimates a distribution of score values for each alternative. Another line of work deals with heterogeneity by clustering user preferences and learning several reward models at once, then aggregate the learned reward models using various techniques such as max-min optimization, which optimizes the worst-case reward among all clusters [Chidambaram et al., 2024, Chakraborty et al., 2024], or through aggregation rules motivated by axiomatic properties in social choice theory [Zhong et al., 2024, Park et al., 2024]. Poddar et al. [2024] proposes a variational inference approach that infers user-specific latent variables from preference data which enables steerable personalized language models. Chen et al. [2024] 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 estimators (MLE), which serves as the core of the widely-used RLHF pipeline, can be viewed as voting rules: given a 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 [2005], who show that any scoring-based voting rule is a maximum likelihood estimator under a 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 [Azari Soufiani et al., 2014, Xia, 2018, Noothigattu et al., 2020, Ge et al., 2024, Procaccia et al., 2025]. Notably, Ge et al. [2024] analyzes the axiomatic properties of MLE-based AI alignment 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 [Alvo and Philip, 2014, Xia, 2019] for a comprehensive overview. Recently, Wang et al. [2024], Tatli et al. [2024] focus on learning metric spaces from pairwise preferences. Our work is notably related to the results on the non-identifiability of learning mixture of Bradley-Terry models from pairwise or k-wise preferences [Zhao et al., 2016, Zhao and Xia, 2019, Zhang et al., 2022]. We build on these results to quantify the loss of utility due to non-identifiability by proving a voting-rule independent distortion lower bound. Distortion of randomized voting and RLHF. The framework of implicit utilitarian voting, i.e., of comparing voting rules in terms of their distortion was introduced by Procaccia and Rosenschein [2006], which has since sparked a large body of work — both in the original utility setting [Caragiannis and Procaccia, 2011, Boutilier et al., 2012, Ebadian et al., 2024b, Flanigan et al., 2023, Benade et al., 2021] and in the metric setting [Anshelevich et al., 2018, 2021, Gkatzelis et al., 2020, Charikar et al., 2024, Kizilkaya and Kempe, 2022]. Several recent works have highlighted the importance of using distortion as a metric to evaluate the quality of AI alignment methods. Dai and Fleisig [2024] draw a conceptual connection between social choice and RLHF, and propose to apply the notion of distortion to RLHF. Goyal and Sarmasarkar [2025] 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 are assumed to lie in a common metric space satisfying triangle inequality. 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, as advocated in recent position papers [Conitzer et al., 2024, Mishra, 2023]. Appendix B Linearization Lemma for Expected Win-Rates See 1 Proof of Lemma 1. We prove this lemma by linearizing the sigmoid function σ⁢(z)=11+e−z11superscriptσ(z)= 11+e^-zσ ( z ) = divide start_ARG 1 end_ARG start_ARG 1 + e- z end_ARG in the domain of z∈[−β,β]z∈[-β,β]z ∈ [ - β , β ]. When z∈[0,β]0z∈[0,β]z ∈ [ 0 , β ], the sigmoid function is concave and increasing, thus we have σ⁢(z)≤σ′⁢(0)⋅z+σ⁢(0)=12+L⁢z⋅superscript′0012σ(z)≤σ (0)· z+σ(0)= 12+Lzσ ( z ) ≤ σ′ ( 0 ) ⋅ z + σ ( 0 ) = divide start_ARG 1 end_ARG start_ARG 2 end_ARG + L z, where L=1414L= 14L = divide start_ARG 1 end_ARG start_ARG 4 end_ARG is the derivative σ′⁢(0)superscript′0σ (0)σ′ ( 0 ). When z∈[−β,0]0z∈[-β,0]z ∈ [ - β , 0 ], the sigmoid function is convex, thus we have σ⁢(z)≤(1+zβ)⁢σ⁢(0)−zβ⁢σ⁢(−β)=12+lβ⋅z1012⋅subscriptσ(z)≤ (1+ zβ )σ(0)- zβσ(-% β)= 12+l_β· zσ ( z ) ≤ ( 1 + divide start_ARG z end_ARG start_ARG β end_ARG ) σ ( 0 ) - divide start_ARG z end_ARG start_ARG β end_ARG σ ( - β ) = divide start_ARG 1 end_ARG start_ARG 2 end_ARG + litalic_β ⋅ z, where lβ=σ⁢(β)−12βsubscript12l_β= σ(β)- 12βlitalic_β = divide start_ARG σ ( β ) - divide start_ARG 1 end_ARG start_ARG 2 end_ARG end_ARG start_ARG β end_ARG is the slope of the line connecting (−β,σ⁢(−β))(-β,σ(-β))( - β , σ ( - β ) ) and (0,σ⁢(0))00(0,σ(0))( 0 , σ ( 0 ) ). Plugging the above bounds into σ⁢(β⋅(u⁢(x)−u⁢(y)))⋅σ (β·(u(x)-u(y)) )σ ( β ⋅ ( u ( x ) - u ( y ) ) ), we have that σ⁢(β⋅(u⁢(x)−u⁢(y)))−12≤⋅12absent σ (β·(u(x)-u(y)) )- 12≤σ ( β ⋅ ( u ( x ) - u ( y ) ) ) - divide start_ARG 1 end_ARG start_ARG 2 end_ARG ≤ β⋅(u⁢(x)−u⁢(y))⋅(L⋅u⁢(x)−u⁢(y)≥0+lβ⋅u⁢(x)−u⁢(y)<0)⋅subscript10⋅subscriptsubscript10 β·(u(x)-u(y))· (L· 1_u(x)-u(y)≥ 0% +l_β· 1_u(x)-u(y)<0 )β ⋅ ( u ( x ) - u ( y ) ) ⋅ ( L ⋅ blackboard_1u ( x ) - u ( y ) ≥ 0 + litalic_β ⋅ blackboard_1u ( x ) - u ( y ) < 0 ) ≤ ≤ β⋅(L⋅u⁢(x)−lβ⋅u⁢(y)).⋅subscript β· (L· u(x)-l_β· u(y) ).β ⋅ ( L ⋅ u ( x ) - litalic_β ⋅ u ( y ) ) . Finally, taking an expectation over u∼similar-tou ∼ D, we have that p⁢(x≻y)−12≤β⁢(L⋅u∼[u⁢(x)]−lβ⋅u∼[u⁢(y)])=β⁢(L⋅⁢(x)−lβ⋅⁢(y)).succeeds12⋅subscriptsimilar-to⋅subscriptsubscriptsimilar-to⋅subscript p(x y)- 12≤β (L· *% E_u [u(x) ]-l_β· *% E_u [u(y) ] )=β (L·% AvgUtil(x)-l_β· AvgUtil(y) ).p ( x ≻ y ) - divide start_ARG 1 end_ARG start_ARG 2 end_ARG ≤ β ( L ⋅ blackboard_Eu ∼ D [ u ( x ) ] - litalic_β ⋅ blackboard_Eu ∼ D [ u ( y ) ] ) = β ( L ⋅ sansserif_AvgUtil ( x ) - litalic_β ⋅ sansserif_AvgUtil ( y ) ) . This completes the proof of the upper bound. The lower bound follows from applying the same argument to p⁢(y≻x)succeedsp(y x)p ( y ≻ x ) and using the fact that p⁢(x≻y)=1−p⁢(y≻x)succeeds1succeedsp(x y)=1-p(y x)p ( x ≻ y ) = 1 - p ( y ≻ x ). ∎ Appendix C Finite-Sample Convergence Bounds In this section, we use standard concentration techniques to derive finite-sample convergence bounds for the normalized Borda score and the empirical win rate. The lemmas presented in this section will serve as a building block for proving finite-sample guarantees for the alignment methods studied in Sections 3 and 4. C.1 Estimation Error of Win-Rates Lemma 10. For any instance DD with any number of alternatives m, any distribution μ over alternatives with μmin=minx∈A⁡μ⁢(x)subscriptsubscript _ = _x∈ Aμ(x)μroman_min = minitalic_x ∈ A μ ( x ), and n i.i.d. users sampled from DD where each user labels d comparison pairs following the Bradley-Terry model with temperature β, we have that with probability at least 1−δ11- 1 - δ where δ≥m2⁢exp⁡(−n⁢d⁢μmin28)superscript2superscriptsubscript28δ≥ m^2 (- nd _ ^28 )δ ≥ m2 exp ( - divide start_ARG n d μroman_min2 end_ARG start_ARG 8 end_ARG ), the empirical win rates pn⁢(x≻y):=#⁢(x≻y)#⁢(x≻y)+#⁢(y≻x)assignsubscriptsucceeds#succeeds#succeeds#succeedsp_n(x y):= \#(x y)\#(x y)+\#(y x)pitalic_n ( x ≻ y ) := divide start_ARG # ( x ≻ y ) end_ARG start_ARG # ( x ≻ y ) + # ( y ≻ x ) end_ARG satisfies that: ∀x,y∈A,|pn⁢(x≻y)−p⁢(x≻y)|≤O⁢(log⁡(m/δ)n⋅min⁡1,d⋅μmin2+log⁡(m/δ)n⁢μmin2).formulae-sequencefor-allsubscriptsucceedssucceeds⋅1⋅superscriptsubscript2superscriptsubscript2 ∀ x,y∈ A, |p_n(x y)-p(x y) |% ≤ O ( (m/δ)n· \1,\,d· _ ^2\% + (m/δ)n _ ^2 ).∀ x , y ∈ A , | pitalic_n ( x ≻ y ) - p ( x ≻ y ) | ≤ O ( square-root start_ARG divide start_ARG log ( m / δ ) end_ARG start_ARG n ⋅ min 1 , d ⋅ μroman_min2 end_ARG end_ARG + divide start_ARG log ( m / δ ) end_ARG start_ARG n μroman_min2 end_ARG ) . Proof of Lemma 10. We first bound the estimation error of pn⁢(x≻y)subscriptsucceedsp_n(x y)pitalic_n ( x ≻ y ) for a fixed pair x,y∈(A2)binomial2x,y∈ A2x , y ∈ ( FRACOP start_ARG A end_ARG start_ARG 2 end_ARG ). Here we assume x≠yx≠ yx ≠ y without loss of generality, because the estimation error for the x=yx=yx = y case is 00. Since each voter i∈[n]delimited-[]i∈[n]i ∈ [ n ] is asked to label d pairwise comparisons, if each of them are asked to label a pair x,y\x,y\ x , y multiple times, their answer will be consistent. Therefore, we can equivalently rewrite the process of sampling pn⁢(x≻y)subscriptsucceedsp_n(x y)pitalic_n ( x ≻ y ) as follows: 1. Draw k1,…,kn∼i.i.d.⁢(d,q)superscriptsimilar-toi.i.d.subscript1…subscriptk_1,…,k_n .i.d. % Binomial(d,q)k1 , … , kitalic_n start_RELOP SUPERSCRIPTOP start_ARG ∼ end_ARG start_ARG i.i.d. end_ARG end_RELOP sansserif_Binomial ( d , q ) to represent the number of times the i-th voter is asked to label x,y\x,y\ x , y , where q:=2⁢μ⁢(x)⁢μ⁢(y)assign2q:=2μ(x)μ(y)q := 2 μ ( x ) μ ( y ) is the probability that each comparison pair is x,y\x,y\ x , y ; 2. Draw p1,…,pn∼i.i.d.⁢(p)superscriptsimilar-toi.i.d.subscript1…subscriptp_1,…,p_n .i.d. % Bernoulli(p)p1 , … , pitalic_n start_RELOP SUPERSCRIPTOP start_ARG ∼ end_ARG start_ARG i.i.d. end_ARG end_RELOP sansserif_Bernoulli ( p ) to represent the preference of the i-th voter on pair x,y\x,y\ x , y , where p:=p⁢(x≻y)assignsucceedsp:=p(x y)p := p ( x ≻ y ) is the probability that a fresh voter prefers x over y. In particular, we have pi⟂kiperpendicular-tosubscriptsubscriptp_i k_ipitalic_i ⟂ kitalic_i because the sampling of voters and comparison pairs are independent; 3. Each voter i∈[n]delimited-[]i∈[n]i ∈ [ n ] contributes ki⋅pi⋅subscriptsubscriptk_i· p_ikitalic_i ⋅ pitalic_i to #⁢(x≻y)#succeeds\#(x y)# ( x ≻ y ) and ki⋅(1−pi)⋅subscript1subscriptk_i·(1-p_i)kitalic_i ⋅ ( 1 - pitalic_i ) to #⁢(y≻x)#succeeds\#(y x)# ( y ≻ x ). As a result, the empirical win rate pn⁢(x≻y)subscriptsucceedsp_n(x y)pitalic_n ( x ≻ y ) can be rewritten as: pn⁢(x≻y)=#⁢(x≻y)#⁢(x≻y)+#⁢(y≻x)=∑i=1nki⁢pi∑i=1nki.subscriptsucceeds#succeeds#succeeds#succeedssuperscriptsubscript1subscriptsubscriptsuperscriptsubscript1subscript p_n(x y)= \#(x y)\#(x y)+\#(y x)=% _i=1^nk_ip_i _i=1^nk_i.pitalic_n ( x ≻ y ) = divide start_ARG # ( x ≻ y ) end_ARG start_ARG # ( x ≻ y ) + # ( y ≻ x ) end_ARG = divide start_ARG ∑i = 1n kitalic_i pitalic_i end_ARG start_ARG ∑i = 1n kitalic_i end_ARG . The error term is then given by: pn⁢(x≻y)−p⁢(x≻y)=∑i=1nki⁢pi∑i=1nki−p=∑i=1nki⁢(pi−p)∑i=1nki.subscriptsucceedssucceedssuperscriptsubscript1subscriptsubscriptsuperscriptsubscript1subscriptsuperscriptsubscript1subscriptsubscriptsuperscriptsubscript1subscript p_n(x y)-p(x y)= _i=1^nk_ip_iΣ% _i=1^nk_i-p= _i=1^nk_i(p_i-p) _i=1^nk_i.pitalic_n ( x ≻ y ) - p ( x ≻ y ) = divide start_ARG ∑i = 1n kitalic_i pitalic_i end_ARG start_ARG ∑i = 1n kitalic_i end_ARG - p = divide start_ARG ∑i = 1n kitalic_i ( pitalic_i - p ) end_ARG start_ARG ∑i = 1n kitalic_i end_ARG . Now we use Bernstein’s inequality to bound the numerator. We start by bounding the variance of random variable Zi:=ki⁢(pi−p)assignsubscriptsubscriptsubscriptZ_i:=k_i(p_i-p)Zitalic_i := kitalic_i ( pitalic_i - p ). Note that [Zi]=[ki]⋅[pi−p]=0subscript⋅subscriptsubscript0 *E [Z_i ]= *E [k% _i ]· *E [p_i-p ]=0blackboard_E [ Zitalic_i ] = blackboard_E [ kitalic_i ] ⋅ blackboard_E [ pitalic_i - p ] = 0 because kisubscriptk_ikitalic_i and pi−psubscriptp_i-ppitalic_i - p are independent. Therefore, we have Var⁢(Zi)=[Zi2]=[ki2]⋅[(pi−p)2]≤[ki2]=Var⁢(ki)+([ki])2=d⁢q⁢(1−q)+d2⁢q2.Varsubscriptsuperscriptsubscript2⋅superscriptsubscript2superscriptsubscript2superscriptsubscript2Varsubscriptsuperscriptsubscript21superscript2superscript2 (Z_i )= *E [Z_% i^2 ]= *E [k_i^2 ]·% *E [(p_i-p)^2 ]≤ * % E [k_i^2 ]=Var (k_i )+( *% E [k_i ])^2=dq(1-q)+d^2q^2.Var ( Zitalic_i ) = blackboard_E [ Zitalic_i2 ] = blackboard_E [ kitalic_i2 ] ⋅ blackboard_E [ ( pitalic_i - p )2 ] ≤ blackboard_E [ kitalic_i2 ] = Var ( kitalic_i ) + ( blackboard_E [ kitalic_i ] )2 = d q ( 1 - q ) + d2 q2 . According to Bernstein’s inequality, we have that with probability at least 1−δ11- 1 - δ, |∑i=1nZi|=|∑i=1nki⁢(pi−p)|≤2⁢n⁢(d⁢q⁢(1−q)+d2⁢q2)⁢log⁡(2/δ)+3⁢d⁢log⁡(2/δ).superscriptsubscript1subscriptsuperscriptsubscript1subscriptsubscript21superscript2superscript2232 | _i=1^nZ_i |= | _i=1^nk_i(p_i-% p) |≤ 2n(dq(1-q)+d^2q^2) (2/δ)+3d (2/δ).| ∑i = 1n Zitalic_i | = | ∑i = 1n kitalic_i ( pitalic_i - p ) | ≤ square-root start_ARG 2 n ( d q ( 1 - q ) + d2 q2 ) log ( 2 / δ ) end_ARG + 3 d log ( 2 / δ ) . (3) Now we bound the denominator. Note that [ki]=d⁢qsubscript *E [k_i ]=dqblackboard_E [ kitalic_i ] = d q and Var⁢(ki)=d⁢q⁢(1−q)Varsubscript1Var (k_i )=dq(1-q)Var ( kitalic_i ) = d q ( 1 - q ). From the Chernoff bound, we have that with probability at least 1−e−n⁢d⁢q81superscript81-e^- ndq81 - e- divide start_ARG n d q end_ARG start_ARG 8 end_ARG, ∑i=1nki≥n⁢[ki]2=n⁢d⁢q2.superscriptsubscript1subscriptsubscript22 _i=1^nk_i≥ n *E [k_% i ]2= ndq2.∑i = 1n kitalic_i ≥ divide start_ARG n blackboard_E [ kitalic_i ] end_ARG start_ARG 2 end_ARG = divide start_ARG n d q end_ARG start_ARG 2 end_ARG . (4) Combining the bounds in Equation 3 and Equation 4, we have that when δ≥e−n⁢d⁢q8superscript8δ≥ e^- ndq8δ ≥ e- divide start_ARG n d q end_ARG start_ARG 8 end_ARG, with probability at least 1−2⁢δ121-2 1 - 2 δ, for a fixed pair x,y∈Ax,y∈ Ax , y ∈ A, we have |pn⁢(x≻y)−p⁢(x≻y)|≤subscriptsucceedssucceedsabsent |p_n(x y)-p(x y) |≤| pitalic_n ( x ≻ y ) - p ( x ≻ y ) | ≤ 2⁢n⁢(d⁢q⁢(1−q)+d2⁢q2)⁢log⁡(2/δ)+3⁢d⁢log⁡(2/δ)n⁢d⁢q/221superscript2superscript22322 2n(dq(1-q)+d^2q^2) (2/δ)+3d (2/δ% )ndq/2divide start_ARG square-root start_ARG 2 n ( d q ( 1 - q ) + d2 q2 ) log ( 2 / δ ) end_ARG + 3 d log ( 2 / δ ) end_ARG start_ARG n d q / 2 end_ARG ≤ ≤ O⁢((1−q+d⁢q)⁢log⁡(1/δ)n⁢d⁢q+log⁡(1/δ)n⁢q)111 O ( (1-q+dq) (1/δ)ndq+ (1/% δ)nq )O ( square-root start_ARG divide start_ARG ( 1 - q + d q ) log ( 1 / δ ) end_ARG start_ARG n d q end_ARG end_ARG + divide start_ARG log ( 1 / δ ) end_ARG start_ARG n q end_ARG ) where we use the fact that 1−q+d⁢qd⁢q≤2min⁡1,d⁢q121 1-q+dqdq≤ 2 \1,dq\divide start_ARG 1 - q + d q end_ARG start_ARG d q end_ARG ≤ divide start_ARG 2 end_ARG start_ARG min 1 , d q end_ARG and q=2⁢μ⁢(x)⁢μ⁢(y)≥μmin22superscriptsubscript2q=2μ(x)μ(y)≥ _ ^2q = 2 μ ( x ) μ ( y ) ≥ μroman_min2 to obtain: ≤ ≤ O⁢(log⁡(1/δ)n⁢min⁡1,d⋅μmin2+log⁡(1/δ)n⁢μmin2).11⋅superscriptsubscript21superscriptsubscript2 O ( (1/δ)n \1,d· _ ^2% \+ (1/δ)n _ ^2 ).O ( square-root start_ARG divide start_ARG log ( 1 / δ ) end_ARG start_ARG n min 1 , d ⋅ μroman_min2 end_ARG end_ARG + divide start_ARG log ( 1 / δ ) end_ARG start_ARG n μroman_min2 end_ARG ) . Finally, by union bound over all (m2)binomial2 m2( FRACOP start_ARG m end_ARG start_ARG 2 end_ARG ) pairs, we have that with probability at least 1−δ11- 1 - δ where δ≥m2⁢exp⁡(−n⁢d⁢μmin28)superscript2superscriptsubscript28δ≥ m^2 (- nd _ ^28 )δ ≥ m2 exp ( - divide start_ARG n d μroman_min2 end_ARG start_ARG 8 end_ARG ), the following holds simultaneously for all x,y∈Ax,y∈ Ax , y ∈ A: |pn⁢(x≻y)−p⁢(x≻y)|≤O⁢(log⁡(m/δ)n⋅min⁡1,d⋅μmin2+log⁡(m/δ)n⁢μmin2).subscriptsucceedssucceeds⋅1⋅superscriptsubscript2superscriptsubscript2 |p_n(x y)-p(x y) |≤ O ( % (m/δ)n· \1,\,d· _ ^2\+ (m/δ)% n _ ^2 ).| pitalic_n ( x ≻ y ) - p ( x ≻ y ) | ≤ O ( square-root start_ARG divide start_ARG log ( m / δ ) end_ARG start_ARG n ⋅ min 1 , d ⋅ μroman_min2 end_ARG end_ARG + divide start_ARG log ( m / δ ) end_ARG start_ARG n μroman_min2 end_ARG ) . The proof is complete. ∎ C.2 Estimation Error of Normalized Borda Score Lemma 11. For any instance DD with any number of alternatives m, any distribution μ over alternatives with μmin=minx∈A⁡μ⁢(x)subscriptsubscript _ = _x∈ Aμ(x)μroman_min = minitalic_x ∈ A μ ( x ), and n i.i.d. users sampled from DD where each user labels d comparison pairs, the normalized Borda score n⁢(x)subscript BC_n(x)sansserif_BCn ( x ) of any alternative x∈Ax∈ Ax ∈ A satisfies that with probability at least 1−δ11- 1 - δ where δ≥2⁢m⁢exp⁡(−n⁢d⁢μmin8)2subscript8δ≥ 2m (- nd _ 8)δ ≥ 2 m exp ( - divide start_ARG n d μroman_min end_ARG start_ARG 8 end_ARG ), ∀x∈A,|n⁢(x)−⋆⁢(x)|≤O⁢(log⁡(m/δ)n⋅min⁡1,d⋅μmin2+m⁢log⁡(m/δ)n⁢μmin),formulae-sequencefor-allsubscriptsuperscript⋆⋅1⋅superscriptsubscript2subscript ∀ x∈ A, | BC_n(x)- BC (% x) |≤ O ( (m/δ)n· \1,d· _ % ^2\+ m (m/δ)n _ ),∀ x ∈ A , | sansserif_BCn ( x ) - sansserif_BC⋆ ( x ) | ≤ O ( square-root start_ARG divide start_ARG log ( m / δ ) end_ARG start_ARG n ⋅ min 1 , d ⋅ μroman_min2 end_ARG end_ARG + divide start_ARG m log ( m / δ ) end_ARG start_ARG n μroman_min end_ARG ) , (5) where ⋆⁢(x)superscript⋆ BC (x)sansserif_BC⋆ ( x ) is the limiting normalized Borda score of candidate x, defined as ⋆⁢(x):=∑y∈Aμ⁢(y)⋅p⁢(x≻y)=12⁢μ⁢(x)+∑y≠xμ⁢(y)⋅p⁢(x≻y).assignsuperscript⋆subscript⋅succeeds12subscript⋅succeeds BC (x):= _y∈ Aμ(y)· p(x y)=% 12μ(x)+ _y≠ xμ(y)· p(x y).sansserif_BC⋆ ( x ) := ∑y ∈ A μ ( y ) ⋅ p ( x ≻ y ) = divide start_ARG 1 end_ARG start_ARG 2 end_ARG μ ( x ) + ∑y ≠ x μ ( y ) ⋅ p ( x ≻ y ) . (6) Proof. We first bound the estimation error |n⁢(x)−⋆⁢(x)|subscriptsuperscript⋆| BC_n(x)- BC (x)|| sansserif_BCn ( x ) - sansserif_BC⋆ ( x ) | for a fixed alternative x∈Ax∈ Ax ∈ A. For notational simplicity, we use Tn⁢(x)subscriptT_n(x)Titalic_n ( x ) to denote the number of comparison pairs involving x, and Wn⁢(x)subscriptW_n(x)Witalic_n ( x ) to denote the number of comparison pairs where x is the winner, i.e., Tn⁢(x)=2⁢#⁢(x≻x)+∑y≠x#⁢(x≻y)+#⁢(y≻x),Wn⁢(x)=#⁢(x≻x)+∑y≠x#⁢(x≻y).formulae-sequencesubscript2#succeedssubscript#succeeds#succeedssubscript#succeedssubscript#succeeds T_n(x)=2\#(x x)+ _y≠ x\#(x y)+\#(y x),% W_n(x)=\#(x x)+ _y≠ x\#(x y).Titalic_n ( x ) = 2 # ( x ≻ x ) + ∑y ≠ x # ( x ≻ y ) + # ( y ≻ x ) , Witalic_n ( x ) = # ( x ≻ x ) + ∑y ≠ x # ( x ≻ y ) . The normalized Borda score of x is then given by n⁢(x)=Wn⁢(x)Tn⁢(x)subscriptsubscriptsubscript BC_n(x)= W_n(x)T_n(x)sansserif_BCn ( x ) = divide start_ARG Witalic_n ( x ) end_ARG start_ARG Titalic_n ( x ) end_ARG. It is then easy to see that [Tn⁢(x)]=subscriptabsent *E [T_n(x) ]=blackboard_E [ Titalic_n ( x ) ] = n⁢d⁢(2⁢μ⁢(x)2+∑y≠x2⁢μ⁢(x)⁢μ⁢(y))=2⁢n⁢d⁢μ⁢(x);2superscript2subscript22 nd (2μ(x)^2+ _y≠ x2μ(x)μ(y) )=2ndμ(x);n d ( 2 μ ( x )2 + ∑y ≠ x 2 μ ( x ) μ ( y ) ) = 2 n d μ ( x ) ; [Wn⁢(x)]=subscriptabsent *E [W_n(x) ]=blackboard_E [ Witalic_n ( x ) ] = n⁢d⁢(μ⁢(x)2+∑y≠xμ⁢(x)⁢μ⁢(y)⁢p⁢(x≻y))=n⁢d⁢μ⁢(x)⁢(12⁢μ⁢(x)+∑y≠xμ⁢(y)⁢p⁢(x≻y)).superscript2subscriptsucceeds12subscriptsucceeds nd (μ(x)^2+ _y≠ xμ(x)μ(y)p(x y) )=% ndμ(x) ( 12μ(x)+ _y≠ xμ(y)p(x y) ).n d ( μ ( x )2 + ∑y ≠ x μ ( x ) μ ( y ) p ( x ≻ y ) ) = n d μ ( x ) ( divide start_ARG 1 end_ARG start_ARG 2 end_ARG μ ( x ) + ∑y ≠ x μ ( y ) p ( x ≻ y ) ) . The limiting Borda score ⋆⁢(x)superscript⋆ BC (x)sansserif_BC⋆ ( x ) is then given by the ratio of the above two expectations, i.e., ⋆⁢(x)=superscript⋆absent BC (x)=sansserif_BC⋆ ( x ) = [Wn⁢(x)][Tn⁢(x)]=12⁢μ⁢(x)+∑y≠xμ⁢(y)⁢p⁢(x≻y).subscriptsubscript12subscriptsucceeds *E [W_n(x) ]% *E [T_n(x) ]= 12μ(x)+ _y≠ x% μ(y)p(x y).divide start_ARG blackboard_E [ Witalic_n ( x ) ] end_ARG start_ARG blackboard_E [ Titalic_n ( x ) ] end_ARG = divide start_ARG 1 end_ARG start_ARG 2 end_ARG μ ( x ) + ∑y ≠ x μ ( y ) p ( x ≻ y ) . We can thus decompose the estimation error |n⁢(x)−⋆⁢(x)|subscriptsuperscript⋆| BC_n(x)- BC (x)|| sansserif_BCn ( x ) - sansserif_BC⋆ ( x ) | as follows: |n⁢(x)−⋆⁢(x)|=subscriptsuperscript⋆absent | BC_n(x)- BC (x)|=| sansserif_BCn ( x ) - sansserif_BC⋆ ( x ) | = |Wn⁢(x)Tn⁢(x)−[Wn⁢(x)][Tn⁢(x)]|subscriptsubscriptsubscriptsubscript | W_n(x)T_n(x)- *E% [W_n(x) ] *E [T_n(x) ] || divide start_ARG Witalic_n ( x ) end_ARG start_ARG Titalic_n ( x ) end_ARG - divide start_ARG blackboard_E [ Witalic_n ( x ) ] end_ARG start_ARG blackboard_E [ Titalic_n ( x ) ] end_ARG | ≤ ≤ |Wn⁢(x)−[Wn⁢(x)]|Tn⁢(x)+[Wn⁢(x)][Tn⁢(x)]⏟⋆⁢(x)≤1⋅|Tn⁢(x)−[Tn⁢(x)]|Tn⁢(x)subscriptsubscriptsubscript⋅subscript⏟subscriptsubscriptsuperscript⋆1subscriptsubscriptsubscript |W_n(x)- *E [W_n(x) ]|% T_n(x)+ *E [W_n(x) ]% *E [T_n(x) ]_ BC (x)≤ 1% · |T_n(x)- *E [T_n(x) ]% |T_n(x)divide start_ARG | Witalic_n ( x ) - blackboard_E [ Witalic_n ( x ) ] | end_ARG start_ARG Titalic_n ( x ) end_ARG + under⏟ start_ARG divide start_ARG blackboard_E [ Witalic_n ( x ) ] end_ARG start_ARG blackboard_E [ Titalic_n ( x ) ] end_ARG end_ARGsansserif_BC⋆ ( x ) ≤ 1 ⋅ divide start_ARG | Titalic_n ( x ) - blackboard_E [ Titalic_n ( x ) ] | end_ARG start_ARG Titalic_n ( x ) end_ARG ≤ ≤ |Wn⁢(x)−[Wn⁢(x)]|Tn⁢(x)+|Tn⁢(x)−[Tn⁢(x)]|Tn⁢(x).subscriptsubscriptsubscriptsubscriptsubscriptsubscript |W_n(x)- *E [W_n(x) ]|% T_n(x)+ |T_n(x)- *E [T_n(x) % ] |T_n(x).divide start_ARG | Witalic_n ( x ) - blackboard_E [ Witalic_n ( x ) ] | end_ARG start_ARG Titalic_n ( x ) end_ARG + divide start_ARG | Titalic_n ( x ) - blackboard_E [ Titalic_n ( x ) ] | end_ARG start_ARG Titalic_n ( x ) end_ARG . Now we bound the two terms |Wn⁢(x)−[Wn⁢(x)]|subscriptsubscript|W_n(x)- *E [W_n(x) ]|| Witalic_n ( x ) - blackboard_E [ Witalic_n ( x ) ] | and |Tn⁢(x)−[Tn⁢(x)]|subscriptsubscript|T_n(x)- *E [T_n(x) ]|| Titalic_n ( x ) - blackboard_E [ Titalic_n ( x ) ] | separately, and apply the union bound at the end. (I). Bounding |Wn⁢(x)−[Wn⁢(x)]|subscriptsubscript|W_n(x)- *E [W_n(x) ]|| Witalic_n ( x ) - blackboard_E [ Witalic_n ( x ) ] |: For each y≠xy≠ xy ≠ x, we can write bound the deviation |#⁢(x≻y)−[#⁢(x≻y)]|#succeeds#succeeds|\#(x y)- *E [\#(x y) ]|| # ( x ≻ y ) - blackboard_E [ # ( x ≻ y ) ] | using the same argument as in the proof of Lemma 10. Specifically, we can write #⁢(x≻y)#succeeds\#(x y)# ( x ≻ y ) as a sum of i.i.d. random variables ki⁢pisubscriptsubscriptk_ip_ikitalic_i pitalic_i where ki∼⁢(d,qx,y)similar-tosubscriptsubscriptk_i Binomial(d,q_x,y)kitalic_i ∼ sansserif_Binomial ( d , qitalic_x , y ) and pi∼⁢(p⁢(x≻y))similar-tosubscriptsucceedsp_i Bernoulli(p(x y))pitalic_i ∼ sansserif_Bernoulli ( p ( x ≻ y ) ), where qx,y=2⁢μ⁢(x)⁢μ⁢(y)subscript2q_x,y=2μ(x)μ(y)qitalic_x , y = 2 μ ( x ) μ ( y ) is the probability that each comparison pair is x,y\x,y\ x , y . Therefore, we have Var⁢(ki⁢pi)=Varsubscriptsubscriptabsent (k_ip_i )=Var ( kitalic_i pitalic_i ) = Var(ki)⋅Var(pi)+Var(ki)[pi2]+Var(pi)[ki]2 (k_i )·Var (p_i )% +Var (k_i ) *E [p_i^2 % ]+Var (p_i ) *E [k_i ]^2Var ( kitalic_i ) ⋅ Var ( pitalic_i ) + Var ( kitalic_i ) blackboard_E [ pitalic_i2 ] + Var ( pitalic_i ) blackboard_E [ kitalic_i ]2 ≤ ≤ 2⁢d⁢qx,y⁢(1−qx,y+d⁢qx,y)2subscript1subscriptsubscript 2dq_x,y(1-q_x,y+dq_x,y)2 d qitalic_x , y ( 1 - qitalic_x , y + d qitalic_x , y ) since 1−qx,y+d⁢qx,y≤2⁢d⁢qx,ymin⁡1,d⁢qx,y≤2⁢d⁢qx,ymin⁡1,d⁢μmin21subscriptsubscript2subscript1subscript2subscript1superscriptsubscript21-q_x,y+dq_x,y≤ 2dq_x,y \1,dq_x,y\≤ 2dq_x,y% \1,d _ ^2\1 - qitalic_x , y + d qitalic_x , y ≤ divide start_ARG 2 d qitalic_x , y end_ARG start_ARG min 1 , d qitalic_x , y end_ARG ≤ divide start_ARG 2 d qitalic_x , y end_ARG start_ARG min 1 , d μroman_min2 end_ARG, we can further bound the variance as ≤ ≤ 2⁢(d⁢qx,y)2min⁡1,d⁢μmin2=8⁢(d⁢μ⁢(x)⁢μ⁢(y))2min⁡1,d⁢μmin2.2superscriptsubscript21superscriptsubscript28superscript21superscriptsubscript2 2(dq_x,y)^2 \1,d _ ^2\= 8(dμ(x)% μ(y))^2 \1,d _ ^2\.divide start_ARG 2 ( d qitalic_x , y )2 end_ARG start_ARG min 1 , d μroman_min2 end_ARG = divide start_ARG 8 ( d μ ( x ) μ ( y ) )2 end_ARG start_ARG min 1 , d μroman_min2 end_ARG . Thus, by Bernstein’s inequality, with probability at least 1−δ′1superscript′1-δ 1 - δ′, |#⁢(x≻y)−[#⁢(x≻y)]|≤#succeeds#succeedsabsent |\#(x y)- *E [\#(x y)% ] |≤| # ( x ≻ y ) - blackboard_E [ # ( x ≻ y ) ] | ≤ 4⁢d⁢μ⁢(x)⁢μ⁢(y)⁢n⁢log⁡(2/δ′)min⁡1,d⋅μmin2+3⁢d⁢log⁡(2/δ′).42superscript′1⋅superscriptsubscript232superscript′ 4dμ(x)μ(y) n (2/δ ) \1,d% · _ ^2\+3d (2/δ ).4 d μ ( x ) μ ( y ) square-root start_ARG divide start_ARG n log ( 2 / δ′ ) end_ARG start_ARG min 1 , d ⋅ μroman_min2 end_ARG end_ARG + 3 d log ( 2 / δ′ ) . On the other hand, for the comparison of x with itself, we have that #⁢(x≻x)∼⁢(n⁢d,μ⁢(x)2)similar-to#succeedssuperscript2\#(x x) Binomial(nd,μ(x)^2)# ( x ≻ x ) ∼ sansserif_Binomial ( n d , μ ( x )2 ). Therefore, with probability at least 1−δ′1superscript′1-δ 1 - δ′, |#⁢(x≻x)−[#⁢(x≻x)]|≤#succeeds#succeedsabsent |\#(x x)- *E [\#(x x)% ] |≤| # ( x ≻ x ) - blackboard_E [ # ( x ≻ x ) ] | ≤ 2⁢n⁢d⁢μ⁢(x)2⁢log⁡(2/δ′)+3⁢d⁢log⁡(2/δ′)2superscript22superscript′32superscript′ 2ndμ(x)^2 (2/δ )+3d (2/δ^% )square-root start_ARG 2 n d μ ( x )2 log ( 2 / δ′ ) end_ARG + 3 d log ( 2 / δ′ ) ≤ ≤ 4⁢d⁢μ⁢(x)2⁢n⁢log⁡(2/δ′)min⁡1,d⋅μmin2+3⁢d⁢log⁡(2/δ′).4superscript22superscript′1⋅superscriptsubscript232superscript′ 4dμ(x)^2 n (2/δ ) \1,d·% _ ^2\+3d (2/δ ).4 d μ ( x )2 square-root start_ARG divide start_ARG n log ( 2 / δ′ ) end_ARG start_ARG min 1 , d ⋅ μroman_min2 end_ARG end_ARG + 3 d log ( 2 / δ′ ) . Applying a union bound over all the m alternatives y∈Ay∈ Ay ∈ A, we have that with probability at least 1−m⁢δ′1superscript′1-mδ 1 - m δ′, |Wn⁢(x)−[Wn⁢(x)]|≤subscriptsubscriptabsent |W_n(x)- *E [W_n(x) ]|≤| Witalic_n ( x ) - blackboard_E [ Witalic_n ( x ) ] | ≤ ∑y≠x|#⁢(x≻y)−[#⁢(x≻y)]|subscript#succeeds#succeeds _y≠ x |\#(x y)- *E [% \#(x y) ] |∑y ≠ x | # ( x ≻ y ) - blackboard_E [ # ( x ≻ y ) ] | ≤ ≤ ∑y≠x(4⁢d⁢μ⁢(x)⁢μ⁢(y)⁢n⁢log⁡(2/δ′)min⁡1,d⋅μmin2+3⁢d⁢log⁡(2/δ′))subscript42superscript′1⋅superscriptsubscript232superscript′ _y≠ x (4dμ(x)μ(y) n (2/δ^% ) \1,d· _ ^2\+3d (2/δ ) )∑y ≠ x ( 4 d μ ( x ) μ ( y ) square-root start_ARG divide start_ARG n log ( 2 / δ′ ) end_ARG start_ARG min 1 , d ⋅ μroman_min2 end_ARG end_ARG + 3 d log ( 2 / δ′ ) ) ≤ ≤ 4⁢d⁢μ⁢(x)⁢n⁢log⁡(2/δ′)min⁡1,d⋅μmin2+3⁢m⁢d⁢log⁡(2/δ′).42superscript′1⋅superscriptsubscript232superscript′ 4dμ(x) n (2/δ ) \1,d· _% ^2\+3md (2/δ ).4 d μ ( x ) square-root start_ARG divide start_ARG n log ( 2 / δ′ ) end_ARG start_ARG min 1 , d ⋅ μroman_min2 end_ARG end_ARG + 3 m d log ( 2 / δ′ ) . (I). Bounding |Tn⁢(x)−[Tn⁢(x)]|subscriptsubscript|T_n(x)- *E [T_n(x) ]|| Titalic_n ( x ) - blackboard_E [ Titalic_n ( x ) ] |: We can write Tn⁢(x)subscriptT_n(x)Titalic_n ( x ) as a sum of i.i.d. random variables: Tn=∑i=1n∑j=1d(xij=x+yij=x)subscriptsuperscriptsubscript1superscriptsubscript1subscript1superscriptsubscriptsubscript1superscriptsubscript T_n= _i=1^n _j=1^d( 1_x_i^j=x+% 1_y_i^j=x)Titalic_n = ∑i = 1n ∑j = 1d ( blackboard_1x start_POSTSUBSCRIPT iitalic_j = x end_POSTSUBSCRIPT + blackboard_1y start_POSTSUBSCRIPT iitalic_j = x end_POSTSUBSCRIPT ) Since each comparison pair xij,yijsuperscriptsubscriptsuperscriptsubscriptx_i^j,y_i^jxitalic_iitalic_j , yitalic_iitalic_j is sampled independently from μ×μ×μ × μ, we have that Tn∼⁢(2⁢n⁢d,μ⁢(x))similar-tosubscript2T_n Binomial(2nd,μ(x))Titalic_n ∼ sansserif_Binomial ( 2 n d , μ ( x ) ). Therefore, with probability at least 1−δ′1superscript′1-δ 1 - δ′, |Tn⁢(x)−[Tn⁢(x)]|≤2⁢n⁢d⁢μ⁢(x)⁢log⁡(2/δ′)+3⁢log⁡(2/δ′).subscriptsubscript22superscript′32superscript′ |T_n(x)- *E [T_n(x) ]% |≤ 2 ndμ(x) (2/δ )+3 (2/δ ).| Titalic_n ( x ) - blackboard_E [ Titalic_n ( x ) ] | ≤ 2 square-root start_ARG n d μ ( x ) log ( 2 / δ′ ) end_ARG + 3 log ( 2 / δ′ ) . In addition, with probability at least 1−exp⁡(−n⁢d⁢μ⁢(x)4)141- (- ndμ(x)4)1 - exp ( - divide start_ARG n d μ ( x ) end_ARG start_ARG 4 end_ARG ), we also have Tn≥[Tn]2=n⁢d⁢μ⁢(x).subscriptsubscript2 T_n≥ *E [T_n ]2=% ndμ(x).Titalic_n ≥ divide start_ARG blackboard_E [ Titalic_n ] end_ARG start_ARG 2 end_ARG = n d μ ( x ) . (I). Combining the two bounds: Finally, combining the above bounds on |Wn⁢(x)−[Wn⁢(x)]|subscriptsubscript|W_n(x)- *E [W_n(x) ]|| Witalic_n ( x ) - blackboard_E [ Witalic_n ( x ) ] | and |Tn⁢(x)−[Tn⁢(x)]|subscriptsubscript|T_n(x)- *E [T_n(x) ]|| Titalic_n ( x ) - blackboard_E [ Titalic_n ( x ) ] |, together with the bound on the denominator Tn⁢(x)subscriptT_n(x)Titalic_n ( x ), we have that with probability at least 1−2⁢m⁢δ′−exp⁡(−n⁢d⁢μ⁢(x)4)12superscript′41-2mδ - (- ndμ(x)4)1 - 2 m δ′ - exp ( - divide start_ARG n d μ ( x ) end_ARG start_ARG 4 end_ARG ), |n⁢(x)−⋆⁢(x)|≤subscriptsuperscript⋆absent | BC_n(x)- BC (x)|≤| sansserif_BCn ( x ) - sansserif_BC⋆ ( x ) | ≤ |Wn⁢(x)−[Wn⁢(x)]|Tn⁢(x)+|Tn⁢(x)−[Tn⁢(x)]|Tn⁢(x)subscriptsubscriptsubscriptsubscriptsubscriptsubscript |W_n(x)- *E [W_n(x) ]|% T_n(x)+ |T_n(x)- *E [T_n(x) % ] |T_n(x)divide start_ARG | Witalic_n ( x ) - blackboard_E [ Witalic_n ( x ) ] | end_ARG start_ARG Titalic_n ( x ) end_ARG + divide start_ARG | Titalic_n ( x ) - blackboard_E [ Titalic_n ( x ) ] | end_ARG start_ARG Titalic_n ( x ) end_ARG ≲less-than-or-similar-to ≲ 1n⁢d⁢μ⁢(x)⁢(d⁢μ⁢(x)⁢n⁢log⁡(1/δ′)min⁡1,d⋅μmin2+m⁢d⁢log⁡(1/δ′)+n⁢d⁢μ⁢(x)⁢log⁡(2/δ′))11superscript′1⋅superscriptsubscript21superscript′2superscript′ 1ndμ(x) (dμ(x) n (1/δ % ) \1,d· _ ^2\+md (1/δ )+ ndμ(x)% (2/δ ) )divide start_ARG 1 end_ARG start_ARG n d μ ( x ) end_ARG ( d μ ( x ) square-root start_ARG divide start_ARG n log ( 1 / δ′ ) end_ARG start_ARG min 1 , d ⋅ μroman_min2 end_ARG end_ARG + m d log ( 1 / δ′ ) + square-root start_ARG n d μ ( x ) log ( 2 / δ′ ) end_ARG ) ≲less-than-or-similar-to ≲ log⁡(1/δ′)n⋅min⁡1,d⋅μmin2+m⁢log⁡(1/δ′)n⁢μmin.1superscript′⋅1⋅superscriptsubscript21superscript′subscript (1/δ )n· \1,d· _% ^2\+ m (1/δ )n _ .square-root start_ARG divide start_ARG log ( 1 / δ′ ) end_ARG start_ARG n ⋅ min 1 , d ⋅ μroman_min2 end_ARG end_ARG + divide start_ARG m log ( 1 / δ′ ) end_ARG start_ARG n μroman_min end_ARG . Finally, setting δ′=δ4⁢m2superscript′4superscript2δ = δ4m^2δ′ = divide start_ARG δ end_ARG start_ARG 4 m2 end_ARG and taking a union bound over all the m alternatives x∈Ax∈ Ax ∈ A, we have that when δ≥2⁢m⁢exp⁡(−n⁢d⁢μmin8)2subscript8δ≥ 2m (- nd _ 8)δ ≥ 2 m exp ( - divide start_ARG n d μroman_min end_ARG start_ARG 8 end_ARG ), with probability at least 1−δ11- 1 - δ, the above bound holds simultaneously for all x∈Ax∈ Ax ∈ A. This completes the proof. ∎ Appendix D Supplemental Materials for Section 3 D.1 Upper Bound for Borda See 2 Proof of Theorem 2. From Lemma 11, we have that with probability at least 1−δ11- 1 - δ, all x∈Ax∈ Ax ∈ A satisfy that |n⁢(x)−⋆⁢(x)|≤εn,d⁢(δ)subscriptsuperscript⋆subscript | BC_n(x)- BC (x) |≤ _n,d(δ)| sansserif_BCn ( x ) - sansserif_BC⋆ ( x ) | ≤ εitalic_n , d ( δ ), where εn,d⁢(δ)=O⁢(log⁡(m/δ)n⋅min⁡1,d⋅μmin2+m⁢log⁡(m/δ)n⁢μmin).subscript⋅1⋅superscriptsubscript2subscript _n,d(δ)=O ( (m/δ)n% · \1,d· _ ^2\+ m (m/δ)n _ % ).εitalic_n , d ( δ ) = O ( square-root start_ARG divide start_ARG log ( m / δ ) end_ARG start_ARG n ⋅ min 1 , d ⋅ μroman_min2 end_ARG end_ARG + divide start_ARG m log ( m / δ ) end_ARG start_ARG n μroman_min end_ARG ) . Following the proof sketch in Section 3.1, we use x^=argmaxx∈An⁢(x)^subscriptargmaxsubscript x= *argmax_x∈ A BC_n(x)over start_ARG x end_ARG = argmaxitalic_x ∈ A sansserif_BCn ( x ) to denote the Borda winner, and x⋆=argmaxx∈A⁢(x)superscript⋆subscriptargmaxx = *argmax_x∈ A AvgUtil(x)x⋆ = argmaxitalic_x ∈ A sansserif_AvgUtil ( x ) to denote the true utility maximizer. Since n⁢(x^)≥n⁢(x⋆)subscript^subscriptsuperscript⋆ BC_n( x)≥ BC_n(x )sansserif_BCn ( over start_ARG x end_ARG ) ≥ sansserif_BCn ( x⋆ ), we have ⋆⁢(x^)−⋆⁢(x⋆)≥−2⁢εn,d⁢(δ).superscript⋆^superscript⋆superscript⋆2subscript BC ( x)- BC (x )≥-2% _n,d(δ).sansserif_BC⋆ ( over start_ARG x end_ARG ) - sansserif_BC⋆ ( x⋆ ) ≥ - 2 εitalic_n , d ( δ ) . (7) For the limiting Borda score ⋆⁢(x)superscript⋆ BC (x)sansserif_BC⋆ ( x ), the argument in Section 3.1 shows that ⋆⁢(x^)−⋆⁢(x⋆)≤superscript⋆^superscript⋆superscript⋆absent BC ( x)- BC (x )≤sansserif_BC⋆ ( over start_ARG x end_ARG ) - sansserif_BC⋆ ( x⋆ ) ≤ β⋅(L⋅⁢(x^)−ℓβ⋅⁢(x⋆)+(L−ℓβ)⋅⁢(μ))⋅^⋅subscriptℓsuperscript⋆⋅subscriptℓ β· (L· AvgUtil( x)- _β·% AvgUtil(x )+(L- _β)· AvgUtil(μ) )β ⋅ ( L ⋅ sansserif_AvgUtil ( over start_ARG x end_ARG ) - ℓitalic_β ⋅ sansserif_AvgUtil ( x⋆ ) + ( L - ℓitalic_β ) ⋅ sansserif_AvgUtil ( μ ) ) ≤ ≤ β⋅(L2ℓβ⋅⁢(x^)−ℓβ⋅⁢(x⋆))⋅superscript2subscriptℓ^⋅subscriptℓsuperscript⋆ β· ( L^2 _β· AvgUtil(% x)- _β· AvgUtil(x ) )β ⋅ ( divide start_ARG L2 end_ARG start_ARG ℓitalic_β end_ARG ⋅ sansserif_AvgUtil ( over start_ARG x end_ARG ) - ℓitalic_β ⋅ sansserif_AvgUtil ( x⋆ ) ) (8) Therefore, Combining Equations 7 and 8, we have −2⁢εn,d⁢(δ)≤β⋅(L2ℓβ⋅⁢(x^)−ℓβ⋅⁢(x⋆))⇒⁢(x^)≥(ℓβL)2⁢(x⋆)−2⁢ℓβ⋅εn,d⁢(δ)β⁢L2.2subscript⋅superscript2subscriptℓ^⋅subscriptℓsuperscript⋆⇒^superscriptsubscriptℓ2superscript⋆⋅2subscriptℓsubscriptsuperscript2 -2 _n,d(δ)≤β· ( L^2 _% β· AvgUtil( x)- _β· AvgUtil(x^% ) )\ \ AvgUtil( x)≥ ( _% βL )^2 AvgUtil(x )- 2 _β·% _n,d(δ)β L^2.- 2 εitalic_n , d ( δ ) ≤ β ⋅ ( divide start_ARG L2 end_ARG start_ARG ℓitalic_β end_ARG ⋅ sansserif_AvgUtil ( over start_ARG x end_ARG ) - ℓitalic_β ⋅ sansserif_AvgUtil ( x⋆ ) ) ⇒ sansserif_AvgUtil ( over start_ARG x end_ARG ) ≥ ( divide start_ARG ℓitalic_β end_ARG start_ARG L end_ARG )2 sansserif_AvgUtil ( x⋆ ) - divide start_ARG 2 ℓitalic_β ⋅ εitalic_n , d ( δ ) end_ARG start_ARG β L2 end_ARG . Combining this with the failure probability δ of the above argument, the average utility n⁢()subscript AvgUtil_n( Borda)sansserif_AvgUtiln ( sansserif_Borda ) satisfies that n⁢()≥subscriptabsent AvgUtil_n( Borda)≥sansserif_AvgUtiln ( sansserif_Borda ) ≥ (1−δ)⋅((ℓβL)2⁢(x⋆)−2⁢ℓβ⋅εn,d⁢(δ)β⁢L2)⋅1superscriptsubscriptℓ2superscript⋆⋅2subscriptℓsubscriptsuperscript2 (1-δ )· ( ( _βL% )^2 AvgUtil(x )- 2 _β· _n,% d(δ)β L^2 )( 1 - δ ) ⋅ ( ( divide start_ARG ℓitalic_β end_ARG start_ARG L end_ARG )2 sansserif_AvgUtil ( x⋆ ) - divide start_ARG 2 ℓitalic_β ⋅ εitalic_n , d ( δ ) end_ARG start_ARG β L2 end_ARG ) ≥ ≥ (ℓβL)2⁢(x⋆)−O⁢(εn,d⁢(δ)β⋅(ℓβL)+δ⋅(ℓβL)2).superscriptsubscriptℓ2superscript⋆⋅subscriptsubscriptℓ⋅superscriptsubscriptℓ2 ( _βL )^2 AvgUtil(x % )-O ( _n,d(δ)β· ( _β% L )+δ· ( _βL )^2 ).( divide start_ARG ℓitalic_β end_ARG start_ARG L end_ARG )2 sansserif_AvgUtil ( x⋆ ) - O ( divide start_ARG εitalic_n , d ( δ ) end_ARG start_ARG β end_ARG ⋅ ( divide start_ARG ℓitalic_β end_ARG start_ARG L end_ARG ) + δ ⋅ ( divide start_ARG ℓitalic_β end_ARG start_ARG L end_ARG )2 ) . Finally, we set the failure probability to be δ=Θ⁢(Lβ⋅ℓβ⋅1n⋅min⁡1,d⋅μmin2)Θ⋅subscriptℓ1⋅1⋅superscriptsubscript2 δ= ( Lβ· _β· % 1n· \1,d· _ ^2\ )δ = Θ ( divide start_ARG L end_ARG start_ARG β ⋅ ℓitalic_β end_ARG ⋅ square-root start_ARG divide start_ARG 1 end_ARG start_ARG n ⋅ min 1 , d ⋅ μroman_min2 end_ARG end_ARG ) (which satisfies the condition in Lemma 11 for large n), we have n⁢()≥subscriptabsent AvgUtil_n( Borda)≥sansserif_AvgUtiln ( sansserif_Borda ) ≥ (ℓβL)2⁢(x⋆)−O⁢(1β2⁢log⁡(m⁢n⁢β)n⋅min⁡1,d⁢μmin2+m⁢log⁡(m⁢n⁢β)n⋅β2⁢μmin2),superscriptsubscriptℓ2superscript⋆1superscript2⋅1superscriptsubscript2⋅superscript2superscriptsubscript2 ( _βL )^2 AvgUtil(x % )-O ( 1β^2 (mnβ)n· \1,d _% ^2\+ m (mnβ)n·β^2 _ ^2 ),( divide start_ARG ℓitalic_β end_ARG start_ARG L end_ARG )2 sansserif_AvgUtil ( x⋆ ) - O ( divide start_ARG 1 end_ARG start_ARG β2 end_ARG square-root start_ARG divide start_ARG log ( m n β ) end_ARG start_ARG n ⋅ min 1 , d μroman_min2 end_ARG end_ARG + divide start_ARG m log ( m n β ) end_ARG start_ARG n ⋅ β2 μroman_min2 end_ARG ) , which completes the proof. ∎ D.2 Lower Bound for Borda Figure 3: Comparison of the distortion achieved by NLHF/Maximum Lotteries and the lower bound on RLHF/Borda in Theorem 5, both as a fraction of β. The figure illustrates that NLHF has a worse distortion for every value of β>00β>0β > 0 (for worst-case distributions μ); in particular, the distortion of RLHF for large β is at least β−o⁢(β)β-o(β)β - o ( β ), whereas the distortion of NLHF is β/2+o⁢(β)2β/2+o(β)β / 2 + o ( β ). Theorem 12 (Lower Bound for Borda; Formal Version of Theorem 5). For any β>00β>0β > 0 and m≥33m≥ 3m ≥ 3, the Borda voting rule (and, hence, RHLF) cannot guarantee a distortion better than max0<γ<1⁡β2⁢1+e−β1−e−β⋅(1−γ+σ⁢(β⁢γ)−1/2σ⁢(β)−1/2)⋅subscript0121superscript1superscript11212 _0<γ<1 β2 1+e^-β1-e^-β· (1% -γ+ σ(βγ)-1/2σ(β)-1/2 )max0 < γ < 1 divide start_ARG β end_ARG start_ARG 2 end_ARG divide start_ARG 1 + e- β end_ARG start_ARG 1 - e- β end_ARG ⋅ ( 1 - γ + divide start_ARG σ ( β γ ) - 1 / 2 end_ARG start_ARG σ ( β ) - 1 / 2 end_ARG ). This bound is strictly higher than the voting-rule independent lower bound β2⁢1+e−β1−e−β21superscript1superscript β2 1+e^-β1-e^-βdivide start_ARG β end_ARG start_ARG 2 end_ARG divide start_ARG 1 + e- β end_ARG start_ARG 1 - e- β end_ARG for all β and is at least (1−o⁢(1))⁢β11(1-o(1))\,β( 1 - o ( 1 ) ) β as β→∞→β→∞β → ∞. Proof of Theorem 12. Without loss of generality, we may assume that m=33m=3m = 3. If m>33m>3m > 3, we can repeatedly “split” some alternative x in two new alternatives y,y′,y y , y′ (where each user has the utility for y,y′,y y , y′ as for the original alternative x, and μ⁢(y)+μ⁢(y′)superscript′μ(y)+μ(y )μ ( y ) + μ ( y′ ) is equal to the original mass of x in μ). In this operation, the average utilities and Borda scores of y,y′,y y , y′ in the new instance are equal to the average utility and Borda score of x in the original instance, and the average utilities and Borda scores of all other alternatives do not change. For any 0<ϵ<10italic-ϵ10<ε<10 < ϵ < 1, 0≤ϵ′<1−ϵ0superscriptitalic-ϵ′1italic-ϵ0≤ε <1- 0 ≤ ϵ′ < 1 - ϵ, and 0<γ<1010<γ<10 < γ < 1, consider the following distribution DD of utilities over alternatives (a,b,c)(a,b,c)( a , b , c ): (u⁢(a),u⁢(b),u⁢(c))=(1−γ,1,0)with probability pA≔σ⁢(β⁢ϵ)−1/2σ⁢(β)+σ⁢(β⁢ϵ)−1(1,0,ϵ)with probability pB≔pA⋅σ⁢(β⁢γ)−1/2σ⁢(β)−1/2(0,0,ϵ+ϵ′)with probability 1−pA−pB.cases110with probability pA≔σ⁢(β⁢ϵ)−1/2σ⁢(β)+σ⁢(β⁢ϵ)−110italic-ϵwith probability pB≔pA⋅σ⁢(β⁢γ)−1/2σ⁢(β)−1/200italic-ϵsuperscriptitalic-ϵ′with probability 1−pA−pB.(u(a),u(b),u(c))= cases(1-γ,1,0)&with probability $p_A% σ(βε)-1/2σ(β)+σ(βε)-% 1$\\ (1,0,ε)&with probability $p_B p_A· σ(% βγ)-1/2σ(β)-1/2$\\ (0,0,ε+ε )&with probability $1-p_A-p_B$. cases( u ( a ) , u ( b ) , u ( c ) ) = start_ROW start_CELL ( 1 - γ , 1 , 0 ) end_CELL start_CELL with probability pitalic_A ≔ divide start_ARG σ ( β ϵ ) - 1 / 2 end_ARG start_ARG σ ( β ) + σ ( β ϵ ) - 1 end_ARG end_CELL end_ROW start_ROW start_CELL ( 1 , 0 , ϵ ) end_CELL start_CELL with probability pitalic_B ≔ pitalic_A ⋅ divide start_ARG σ ( β γ ) - 1 / 2 end_ARG start_ARG σ ( β ) - 1 / 2 end_ARG end_CELL end_ROW start_ROW start_CELL ( 0 , 0 , ϵ + ϵ′ ) end_CELL start_CELL with probability 1 - pitalic_A - pitalic_B . end_CELL end_ROW One verifies that 0<pA,pB0subscriptsubscript0<p_A,p_B0 < pitalic_A , pitalic_B and pA+pB<1subscriptsubscript1p_A+p_B<1pitalic_A + pitalic_B < 1, so this describes a valid probability distribution for all ϵ,ϵ′,γitalic-ϵsuperscriptitalic-ϵ′ε,ε ,γϵ , ϵ′ , γ and each type of utilities has positive probability of being drawn. Assuming that ϵ′=0superscriptitalic-ϵ′0ε =0ϵ′ = 0, it must be true that p⁢(b≻c)=1/2=p⁢(c≻b)succeeds12succeedsp(b c)=1/2=p(c b)p ( b ≻ c ) = 1 / 2 = p ( c ≻ b ) because pA⋅σ⁢(β⁢(1−0))+(1−pA)⋅σ⁢(β⁢(0−ϵ))⋅subscript10⋅1subscript0italic-ϵ p_A·σ(β(1-0))+(1-p_A)·σ(β(0-% ε))pitalic_A ⋅ σ ( β ( 1 - 0 ) ) + ( 1 - pitalic_A ) ⋅ σ ( β ( 0 - ϵ ) ) =pA⋅(σ⁢(β)−σ⁢(−β⁢ϵ)⏟=1−σ⁢(β⁢ϵ))+σ⁢(−β⁢ϵ)⏟=1−σ⁢(β⁢ϵ)absent⋅subscriptsubscript⏟italic-ϵabsent1italic-ϵsubscript⏟italic-ϵabsent1italic-ϵ =p_A· (σ(β)- σ(-βε% )_=1-σ(βε) )+ σ(-βε)_=1-% σ(βε)= pitalic_A ⋅ ( σ ( β ) - under⏟ start_ARG σ ( - β ϵ ) end_ARG= 1 - σ ( β ϵ ) ) + under⏟ start_ARG σ ( - β ϵ ) end_ARG= 1 - σ ( β ϵ ) =pA⋅(σ⁢(β)+σ⁢(β⁢ϵ)−1)+1−σ⁢(β⁢ϵ)absent⋅subscriptitalic-ϵ11italic-ϵ =p_A· (σ(β)+σ(βε)-1 )+1-% σ(βε)= pitalic_A ⋅ ( σ ( β ) + σ ( β ϵ ) - 1 ) + 1 - σ ( β ϵ ) =σ⁢(β⁢ϵ)−1/2+1−σ⁢(β⁢ϵ)=1/2.absentitalic-ϵ121italic-ϵ12 =σ(βε)-1/2+1-σ(βε)=1/2.= σ ( β ϵ ) - 1 / 2 + 1 - σ ( β ϵ ) = 1 / 2 . If ϵ′>0superscriptitalic-ϵ′0ε >0ϵ′ > 0, it must be the case that p⁢(c≻b)>1/2succeeds12p(c b)>1/2p ( c ≻ b ) > 1 / 2 by monotonicity. A similar chain of algebra shows that p⁢(a≻b)=1/2=p⁢(b≻a)succeeds12succeedsp(a b)=1/2=p(b a)p ( a ≻ b ) = 1 / 2 = p ( b ≻ a ): pA⋅σ⁢(−β⁢γ)+pB⋅σ⁢(β)+1−pA−pB2=pA⋅(σ⁢(−β⁢γ)−1/2)⏟=1/2−σ⁢(β⁢γ)+pB⋅(σ⁢(β)−1/2)⏟=pA⋅(σ⁢(β⁢γ)−1/2)+1/2=1/2.⋅subscript⋅subscript1subscriptsubscript2⋅subscriptsubscript⏟12absent12subscript⏟⋅subscript12absent⋅subscript121212p_A·σ(-βγ)+p_B·σ(β)+ 1-p_A-p_B2% =p_A· (σ(-βγ)-1/2 )_=1/2-σ(% βγ)+ p_B· (σ(β)-1/2 )_=p_A% ·(σ(βγ)-1/2)+1/2=1/2.pitalic_A ⋅ σ ( - β γ ) + pitalic_B ⋅ σ ( β ) + divide start_ARG 1 - pitalic_A - pitalic_B end_ARG start_ARG 2 end_ARG = pitalic_A ⋅ under⏟ start_ARG ( σ ( - β γ ) - 1 / 2 ) end_ARG= 1 / 2 - σ ( β γ ) + under⏟ start_ARG pitalic_B ⋅ ( σ ( β ) - 1 / 2 ) end_ARG= p start_POSTSUBSCRIPT A ⋅ ( σ ( β γ ) - 1 / 2 ) end_POSTSUBSCRIPT + 1 / 2 = 1 / 2 . For any ϵ,γitalic-ϵε,γϵ , γ and positive ϵ′italic-ϵ′ε ϵ′, note that, as the number of samples goes to infinity, the Borda score of the alternatives concentrate around their expected values: ⁢(a) BC(a)sansserif_BC ( a ) →12⁢μ⁢(a)+12⁢μ⁢(b)+p⁢(a≻c)⁢μ⁢(c)→absent1212succeeds → 12μ(a)+ 12μ(b)+p(a c)\,μ(c)→ divide start_ARG 1 end_ARG start_ARG 2 end_ARG μ ( a ) + divide start_ARG 1 end_ARG start_ARG 2 end_ARG μ ( b ) + p ( a ≻ c ) μ ( c ) ⁢(b) BC(b)sansserif_BC ( b ) →12⁢μ⁢(a)+12⁢μ⁢(b)+p⁢(b≻c)⁢μ⁢(c)→absent1212succeeds → 12μ(a)+ 12μ(b)+p(b c)\,μ(c)→ divide start_ARG 1 end_ARG start_ARG 2 end_ARG μ ( a ) + divide start_ARG 1 end_ARG start_ARG 2 end_ARG μ ( b ) + p ( b ≻ c ) μ ( c ) ⁢(c) BC(c)sansserif_BC ( c ) →p⁢(c≻a)⁢μ⁢(a)+p⁢(c≻b)⁢μ⁢(b)+12⁢μ⁢(c).→absentsucceedssucceeds12 → p(c a)\,μ(a)+p(c b)\,μ(b)+ 12μ(c).→ p ( c ≻ a ) μ ( a ) + p ( c ≻ b ) μ ( b ) + divide start_ARG 1 end_ARG start_ARG 2 end_ARG μ ( c ) . Recall that p⁢(c≻b)>1/2>p⁢(b≻c)succeeds12succeedsp(c b)>1/2>p(b c)p ( c ≻ b ) > 1 / 2 > p ( b ≻ c ). Regardless of what p⁢(a≻c)=1−p⁢(c≻a)succeeds1succeedsp(a c)=1-p(c a)p ( a ≻ c ) = 1 - p ( c ≻ a ) may be, for any distribution μ with small enough μ⁢(a),μ⁢(c)μ(a),μ(c)μ ( a ) , μ ( c ) (and hence large μ⁢(b)μ(b)μ ( b )), the expected Borda score of c will be strictly larger than that of a and b. By concentration, for large enough n, the Borda voting rule will almost surely select c as the winner, and the Borda’s distortion for that μ will be at least maxx∈A⁡⁢(x)⁢(c)≥⁢(a)⁢(c)=pA⁢(1−γ)+pBpB⁢ϵ+(1−pA−pB)⁢(ϵ+ϵ′).subscriptsubscript1subscriptsubscriptitalic-ϵ1subscriptsubscriptitalic-ϵsuperscriptitalic-ϵ′ _x∈ A AvgUtil(x) AvgUtil(c)≥ % AvgUtil(a) AvgUtil(c)= p_A\,(1-γ)+p_Bp_B\,% ε+(1-p_A-p_B)\,(ε+ε ).divide start_ARG maxitalic_x ∈ A sansserif_AvgUtil ( x ) end_ARG start_ARG sansserif_AvgUtil ( c ) end_ARG ≥ divide start_ARG sansserif_AvgUtil ( a ) end_ARG start_ARG sansserif_AvgUtil ( c ) end_ARG = divide start_ARG pitalic_A ( 1 - γ ) + pitalic_B end_ARG start_ARG pitalic_B ϵ + ( 1 - pitalic_A - pitalic_B ) ( ϵ + ϵ′ ) end_ARG . (9) We can now derive lower bounds on the distortion of Borda by defining sequences of parameters ϵ,ϵ′,γitalic-ϵsuperscriptitalic-ϵ′ε,ε ,γϵ , ϵ′ , γ (and implicitly, a sequence of corresponding distributions μ), and considering the limit of Eq. 9. In each such sequence, we treat γ as a fixed parameter, but let ϵ′≔ϵ2≔superscriptitalic-ϵ′italic-ϵ2ε ε^2ϵ′ ≔ ϵ2 and letting ϵitalic-ϵεϵ go to 0. As ϵ→0→italic-ϵ0ε→ 0ϵ → 0, it holds that pA→0→subscript0p_A→ 0pitalic_A → 0 (because its numerator σ⁢(β⁢ϵ)−1/2→1/2−1/2=0→italic-ϵ1212120σ(βε)-1/2→ 1/2-1/2=0σ ( β ϵ ) - 1 / 2 → 1 / 2 - 1 / 2 = 0), that pB→0→subscript0p_B→ 0pitalic_B → 0 (since it is a constant multiple of pAsubscriptp_Apitalic_A), and hence both the numerator and denominator of Eq. 9 converge to 0. We apply l’Hôpital’s rule to determine the limit. Treating pAsubscriptp_Apitalic_A and pBsubscriptp_Bpitalic_B, as well as the numerator numnum and denominator denden of the equation as functions in ϵitalic-ϵεϵ, we observe that pA′⁢(0)superscriptsubscript′0 p_A (0)pitalic_A′ ( 0 ) =β4⋅(σ⁢(β)−1/2)absent⋅412 = β4·(σ(β)-1/2)= divide start_ARG β end_ARG start_ARG 4 ⋅ ( σ ( β ) - 1 / 2 ) end_ARG pB′⁢(0)superscriptsubscript′0 p_B (0)pitalic_B′ ( 0 ) =β⋅(σ⁢(β⁢γ)−1/2)4⋅(σ⁢(β)−1/2)2absent⋅12⋅4superscript122 = β·(σ(βγ)-1/2)4·(σ(β)-% 1/2)^2= divide start_ARG β ⋅ ( σ ( β γ ) - 1 / 2 ) end_ARG start_ARG 4 ⋅ ( σ ( β ) - 1 / 2 )2 end_ARG ′⁢(0)superscript′0 (0)num′ ( 0 ) =β4⋅(σ⁢(β)−1/2)⋅(1−γ+σ⁢(β⁢γ)−1/2σ⁢(β)−1/2)absent⋅41211212 = β4·(σ(β)-1/2)· (1-γ+ % σ(βγ)-1/2σ(β)-1/2 )= divide start_ARG β end_ARG start_ARG 4 ⋅ ( σ ( β ) - 1 / 2 ) end_ARG ⋅ ( 1 - γ + divide start_ARG σ ( β γ ) - 1 / 2 end_ARG start_ARG σ ( β ) - 1 / 2 end_ARG ) ′⁢(0)superscript′0 (0)den′ ( 0 ) =pB⁢(0)⏟=0⋅1+pB′⁢(0)⋅0+(1−pA⁢(0)−pB⁢(0))⏟=1⋅(1+2⋅0)+0⋅(−pA′⁢(0)−pB′⁢(0))=1.absent⋅subscript⏟subscript0absent01⋅superscriptsubscript′00⋅subscript⏟1subscript0subscript0absent11⋅20⋅0superscriptsubscript′0superscriptsubscript′01 = p_B(0)_=0· 1+p_B (0)· 0+% (1-p_A(0)-p_B(0))_=1·(1+2· 0)+0·(-p_A % (0)-p_B (0))=1.= under⏟ start_ARG pitalic_B ( 0 ) end_ARG= 0 ⋅ 1 + pitalic_B′ ( 0 ) ⋅ 0 + under⏟ start_ARG ( 1 - pitalic_A ( 0 ) - pitalic_B ( 0 ) ) end_ARG= 1 ⋅ ( 1 + 2 ⋅ 0 ) + 0 ⋅ ( - pitalic_A′ ( 0 ) - pitalic_B′ ( 0 ) ) = 1 . Hence, the limit of Eq. 9 is ′⁢(0)′⁢(0)=β4⁢(σ⁢(β)−1/2)⋅(1−γ+σ⁢(β⁢γ)−1/2σ⁢(β)−1/2)=β2⁢1+e−β1−e−β⋅(1−γ+σ⁢(β⁢γ)−1/2σ⁢(β)−1/2),superscript′0superscript′0⋅41211212⋅21superscript1superscript11212 num (0)den (0)= β4(% σ(β)-1/2)· (1-γ+ σ(βγ)-1/2σ(% β)-1/2 )= β2 1+e^-β1-e^-β· (% 1-γ+ σ(βγ)-1/2σ(β)-1/2 ),divide start_ARG num′ ( 0 ) end_ARG start_ARG den′ ( 0 ) end_ARG = divide start_ARG β end_ARG start_ARG 4 ( σ ( β ) - 1 / 2 ) end_ARG ⋅ ( 1 - γ + divide start_ARG σ ( β γ ) - 1 / 2 end_ARG start_ARG σ ( β ) - 1 / 2 end_ARG ) = divide start_ARG β end_ARG start_ARG 2 end_ARG divide start_ARG 1 + e- β end_ARG start_ARG 1 - e- β end_ARG ⋅ ( 1 - γ + divide start_ARG σ ( β γ ) - 1 / 2 end_ARG start_ARG σ ( β ) - 1 / 2 end_ARG ) , (10) which means that each 0<γ<1010<γ<10 < γ < 1 yields a distortion lower bound for Borda that is larger by a factor of 1−γ+σ⁢(β⁢γ)−1/2σ⁢(β)−1/2112121-γ+ σ(βγ)-1/2σ(β)-1/21 - γ + divide start_ARG σ ( β γ ) - 1 / 2 end_ARG start_ARG σ ( β ) - 1 / 2 end_ARG than our algorithm-independent lower bound/the upper bound achieved by NLHF. Since this factor is strictly concave in γ and is equal to 1111 for γ→0→0γ→ 0γ → 0 and γ→1→1γ→ 1γ → 1, any value of γ will lead to a strictly higher bound. The value of γ that maximizes the bound in Eq. 10 is γ∗≔2β⁢arctanh⁡(1−4⁢σ⁢(β)−1/2β)≔superscript2arctanh1412γ^* 2βarctanh ( 1-4 % σ(β)-1/2β )γ∗ ≔ divide start_ARG 2 end_ARG start_ARG β end_ARG arctanh ( square-root start_ARG 1 - 4 divide start_ARG σ ( β ) - 1 / 2 end_ARG start_ARG β end_ARG end_ARG ), which we used to plot Fig. 3. Since the resulting expression is algebraically unwieldy, we consider the weaker bound for γ=log⁡(β+1)β1γ= (β+1)βγ = divide start_ARG log ( β + 1 ) end_ARG start_ARG β end_ARG, which yields β2⁢1+e−β1−e−β⏟→1⁢ as ⁢β⁣→∞⋅(1−log⁡(β+1)β+11+1/(β+1)−1/2σ⁢(β)−1/2)⏟→2⁢ as ⁢β⁣→∞=(1−o⁢(1))⁢β.∎⋅2subscript⏟1superscript1superscript→absent1 as →absentsubscript⏟1111111212→absent2 as →absent11 β2 1+e^-β1-e^-β_→ 1~% as~β→∞· (1- (β+1)β+% 11+1/(β+1)-1/2σ(β)-1/2 )_→ 2~% as~β→∞=(1-o(1))\,β. start_ARG β end_ARG start_ARG 2 end_ARG under⏟ start_ARG divide start_ARG 1 + e- β end_ARG start_ARG 1 - e- β end_ARG end_ARG→ 1 as β → ∞ ⋅ under⏟ start_ARG ( 1 - divide start_ARG log ( β + 1 ) end_ARG start_ARG β end_ARG + divide start_ARG divide start_ARG 1 end_ARG start_ARG 1 + 1 / ( β + 1 ) end_ARG - 1 / 2 end_ARG start_ARG σ ( β ) - 1 / 2 end_ARG ) end_ARG→ 2 as β → ∞ = ( 1 - o ( 1 ) ) β . ∎ D.3 Algorithm-Independent Lower Bounds See 3 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≥22m≥ 2m ≥ 2, 0<ϵ≤1/20italic-ϵ120<ε≤ 1/20 < ϵ ≤ 1 / 2, and 1≤ξ<2121≤ξ<21 ≤ ξ < 2. The instance has m alternatives labeled a,b1,…,bm−1subscript1…subscript1a,b_1,…,b_m-1a , b1 , … , bitalic_m - 1. The distribution DD is such that an agent i∼similar-toi ∼ D has utilities (ui⁢(a),ui⁢(b1),…,ui⁢(bm−1))=(1,0,…,0)with probability σ⁢(β⁢ϵ)−1/2σ⁢(β)+σ⁢(β⁢ϵ)−1(0,ξ⁢ϵ,…,ξ⁢ϵ)with probability σ⁢(β)−1/2σ⁢(β)+σ⁢(β⁢ϵ)−1.subscriptsubscriptsubscript1…subscriptsubscript1cases10…0with probability σ⁢(β⁢ϵ)−1/2σ⁢(β)+σ⁢(β⁢ϵ)−10italic-ϵ…italic-ϵwith probability σ⁢(β)−1/2σ⁢(β)+σ⁢(β⁢ϵ)−1.(u_i(a),u_i(b_1),…,u_i(b_m-1))= cases(1,0,…,0)&% with probability $ σ(βε)-1/2σ(β)+σ(β% ε)-1$\\ (0,ξε,…,ξε)&with probability $ σ(β)-% 1/2σ(β)+σ(βε)-1$. cases( uitalic_i ( a ) , uitalic_i ( b1 ) , … , uitalic_i ( bitalic_m - 1 ) ) = start_ROW start_CELL ( 1 , 0 , … , 0 ) end_CELL start_CELL with probability divide start_ARG σ ( β ϵ ) - 1 / 2 end_ARG start_ARG σ ( β ) + σ ( β ϵ ) - 1 end_ARG end_CELL end_ROW start_ROW start_CELL ( 0 , ξ ϵ , … , ξ ϵ ) end_CELL start_CELL with probability divide start_ARG σ ( β ) - 1 / 2 end_ARG start_ARG σ ( β ) + σ ( β ϵ ) - 1 end_ARG . end_CELL end_ROW Since the bjsubscriptb_jbitalic_j alternatives have the same utility for any agent, any agent asked to compare two of them will prefer either one with probability 1/2121/21 / 2. When ξ=11ξ=1ξ = 1, a randomly drawn rater will prefer alternative a over some alternative bjsubscriptb_jbitalic_j with probability σ⁢(β⁢ϵ)−1/2σ⁢(β)+σ⁢(β⁢ϵ)−1⋅σ⁢(β)+σ⁢(β)−1/2σ⁢(β)+σ⁢(β⁢ϵ)−1⋅σ⁢(−β⁢ϵ)⋅italic-ϵ12italic-ϵ1⋅12italic-ϵ1italic-ϵ σ(βε)-1/2σ(β)+σ(β% ε)-1·σ(β)+ σ(β)-1/2σ(β)+σ(% βε)-1·σ(-βε)divide start_ARG σ ( β ϵ ) - 1 / 2 end_ARG start_ARG σ ( β ) + σ ( β ϵ ) - 1 end_ARG ⋅ σ ( β ) + divide start_ARG σ ( β ) - 1 / 2 end_ARG start_ARG σ ( β ) + σ ( β ϵ ) - 1 end_ARG ⋅ σ ( - β ϵ ) = == σ⁢(β⁢ϵ)⁢σ⁢(β)−σ⁢(β)/2+σ⁢(β)⁢(1−σ⁢(β⁢ϵ))−(1−σ⁢(β⁢ϵ))/2σ⁢(β)+σ⁢(β⁢ϵ)−1italic-ϵ21italic-ϵ1italic-ϵ2italic-ϵ1 σ(βε)σ(β)-σ(β)/2+σ(% β)(1-σ(βε))-(1-σ(βε))/2σ(β)+% σ(βε)-1divide start_ARG σ ( β ϵ ) σ ( β ) - σ ( β ) / 2 + σ ( β ) ( 1 - σ ( β ϵ ) ) - ( 1 - σ ( β ϵ ) ) / 2 end_ARG start_ARG σ ( β ) + σ ( β ϵ ) - 1 end_ARG = == σ⁢(β)/2+σ⁢(β⁢ϵ)/2−1/2σ⁢(β)+σ⁢(β⁢ϵ)−1=1/2.2italic-ϵ212italic-ϵ112 σ(β)/2+σ(βε)/2-1/2σ(β)+% σ(βε)-1=1/2.divide start_ARG σ ( β ) / 2 + σ ( β ϵ ) / 2 - 1 / 2 end_ARG start_ARG σ ( β ) + σ ( β ϵ ) - 1 end_ARG = 1 / 2 . It is easy to see that the probability of a random agent preferring a over bjsubscriptb_jbitalic_j is monotone decreasing in ξ. The social welfare of a is clearly σ⁢(β⁢ϵ)−1/2σ⁢(β)+σ⁢(β⁢ϵ)−1italic-ϵ12italic-ϵ1 σ(βε)-1/2σ(β)+σ(βε)-1divide start_ARG σ ( β ϵ ) - 1 / 2 end_ARG start_ARG σ ( β ) + σ ( β ϵ ) - 1 end_ARG and the social welfare of any bjsubscriptb_jbitalic_j is ξ⁢ϵ⁢σ⁢(β)−1/2σ⁢(β)+σ⁢(β⁢ϵ)−1italic-ϵ12italic-ϵ1ξε σ(β)-1/2σ(β)+σ(βε)-1ξ ϵ divide start_ARG σ ( β ) - 1 / 2 end_ARG start_ARG σ ( β ) + σ ( β ϵ ) - 1 end_ARG. Fix a voting rule f. If each agent only provides a single pairwise comparison, the voting rule simply observes n independent Bernoulli samples with bias 1/2121/21 / 2. For any number of samples n, denote by pxsubscriptp_xpitalic_x 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 x must be chosen with probability at most 1/m11/m1 / 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≤1/msubscript1p_a≤ 1/mpitalic_a ≤ 1 / m. Now, the expected social welfare achieved by f is at most 1m⁢(a)+⁢(b1)=1/m⋅(σ⁢(β⁢ϵ)−1/2)+ξ⁢ϵ⋅(σ⁢(β)−1/2)σ⁢(β)+σ⁢(β⁢ϵ)−1.1subscript1⋅1italic-ϵ12⋅italic-ϵ12italic-ϵ1 1m AvgUtil(a)+ AvgUtil(b_1)= 1/m·(σ(% βε)-1/2)+ξε·(σ(β)-1/2)σ(β)+σ(% βε)-1.divide start_ARG 1 end_ARG start_ARG m end_ARG sansserif_AvgUtil ( a ) + sansserif_AvgUtil ( b1 ) = divide start_ARG 1 / m ⋅ ( σ ( β ϵ ) - 1 / 2 ) + ξ ϵ ⋅ ( σ ( β ) - 1 / 2 ) end_ARG start_ARG σ ( β ) + σ ( β ϵ ) - 1 end_ARG . This shows that the distortion is at least ⁢(a)⁢(f)≥σ⁢(β⁢ϵ)−1/21/m⋅(σ⁢(β⁢ϵ)−1/2)+ξ⁢ϵ⋅(σ⁢(β)−1/2)=(1m+ξ⁢ϵ⁢(σ⁢(β)−1/2)σ⁢(β⁢ϵ)−1/2)−1.italic-ϵ12⋅1italic-ϵ12⋅italic-ϵ12superscript1italic-ϵ12italic-ϵ121 AvgUtil(a) AvgUtil(f)≥ σ(βε)% -1/21/m·(σ(βε)-1/2)+ξε·(σ(β)-1/2)% = ( 1m+ ξε(σ(β)-1/2)σ(β% ε)-1/2 )^-1.divide start_ARG sansserif_AvgUtil ( a ) end_ARG start_ARG sansserif_AvgUtil ( f ) end_ARG ≥ divide start_ARG σ ( β ϵ ) - 1 / 2 end_ARG start_ARG 1 / m ⋅ ( σ ( β ϵ ) - 1 / 2 ) + ξ ϵ ⋅ ( σ ( β ) - 1 / 2 ) end_ARG = ( divide start_ARG 1 end_ARG start_ARG m end_ARG + divide start_ARG ξ ϵ ( σ ( β ) - 1 / 2 ) end_ARG start_ARG σ ( β ϵ ) - 1 / 2 end_ARG )- 1 . (11) For a sequence of social choice problems in which m→∞→m→∞m → ∞, ϵ→0→italic-ϵ0ε→ 0ϵ → 0, and ξ=11ξ=1ξ = 1, this term converges towards (0+(σ⁢(β)−1/2)⋅limϵσ⁢(β⁢ϵ)−1/2ϵ→0)−1=((σ⁢(β)−1/2)⋅4β)−1=β2⁢1+e−β1−e−β,superscript0⋅12subscriptitalic-ϵitalic-ϵ12→italic-ϵ01superscript⋅124121superscript1superscript (0+(σ(β)-1/2)· _ε→ 0 εσ(% βε)-1/2 )^-1= ((σ(β)-1/2)· 4β% )^-1= β2\, 1+e^-β1-e^-β,( 0 + ( σ ( β ) - 1 / 2 ) ⋅ lim start_FLOATSUBSCRIPT ϵ → 0 end_FLOATSUBSCRIPT divide start_ARG ϵ end_ARG start_ARG σ ( β ϵ ) - 1 / 2 end_ARG )- 1 = ( ( σ ( β ) - 1 / 2 ) ⋅ divide start_ARG 4 end_ARG start_ARG β end_ARG )- 1 = divide start_ARG β end_ARG start_ARG 2 end_ARG divide start_ARG 1 + e- β end_ARG start_ARG 1 - e- β end_ARG , where the first equality follows from l’Hôpital’s rule and the Taylor approximation σ⁢(t)=1/2+t/4+O⁢(t3)124superscript3σ(t)=1/2+t/4+O(t^3)σ ( t ) = 1 / 2 + t / 4 + O ( t3 ), and the second inequality follows from the identity σ⁢(t)−1/2=11+e−t−1/2=2−1−e−t2⁢(1+e−t)=12⋅1−e−t1+e−t1211superscript1221superscript21superscript⋅121superscript1superscriptσ(t)-1/2= 11+e^-t-1/2= 2-1-e^-t2\,(1+e^-t)= 1% 2· 1-e^-t1+e^-tσ ( t ) - 1 / 2 = divide start_ARG 1 end_ARG start_ARG 1 + e- t end_ARG - 1 / 2 = divide start_ARG 2 - 1 - e- t end_ARG start_ARG 2 ( 1 + e- t ) end_ARG = divide start_ARG 1 end_ARG start_ARG 2 end_ARG ⋅ divide start_ARG 1 - e- t end_ARG start_ARG 1 + e- t end_ARG. This shows the claimed bound on the distortion of any voting rule. 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 an agent’s 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.e., it will never put more than 1/m11/m1 / m probability mass on a Condorcet loser if one exists. If ξ>11ξ>1ξ > 1, a random agent prefers a over bjsubscriptb_jbitalic_j with less than 1/2121/21 / 2 probability. As a 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/m11/m1 / m probability mass on a, and the distortion lower bound in Eq. 11 holds. If ξ approaches 1111 from above as m→∞→m→∞m → ∞ and ϵ→0→italic-ϵ0ε→ 0ϵ → 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/m111-1/m1 - 1 / m probability mass on a Condorcet winner (if one exists), the proof goes through if we increase only b2subscript2b_2b2’s utility by a factor ξ↘1↘1ξ 1ξ ↘ 1. Appendix E Supplemental Materials for Section 4 E.1 Upper Bound for NLHF See 7 Proof of Theorem 7. We prove this theorem by leveraging the convergence of empirical win-rates in Lemma 10. We first condition on the following successful event, which, according to Lemma 10, holds with probability at least 1−δ11- 1 - δ over n samples of preference data, ∀x,y∈A,|pn⁢(x≻y)−p⁢(x≻y)|≤O⁢(log⁡(m/δ)n⋅min⁡1,d⋅μmin2+log⁡(m/δ)n⁢μmin2):=εn,d⁢(δ).formulae-sequencefor-allsubscriptsucceedssucceeds⋅1⋅superscriptsubscript2superscriptsubscript2assignsubscript ∀ x,y∈ A, |p_n(x y)-p(x y) |% ≤ O ( (m/δ)n· \1,\,d· _ ^2\% + (m/δ)n _ ^2 ):= _n,d(δ).∀ x , y ∈ A , | pitalic_n ( x ≻ y ) - p ( x ≻ y ) | ≤ O ( square-root start_ARG divide start_ARG log ( m / δ ) end_ARG start_ARG n ⋅ min 1 , d ⋅ μroman_min2 end_ARG end_ARG + divide start_ARG log ( m / δ ) end_ARG start_ARG n μroman_min2 end_ARG ) := εitalic_n , d ( δ ) . As argued in the proof sketch, the NLHF policy by definition satisfies π∈argmaxπ1∈Bτ⁢(πref)minπ2∈Bτ⁢(πref)⁡x1∼π1,x2∼π2⁢[pn⁢(x1≻x2)−pn⁢(x2≻x1)],subscriptsubscriptargmaxsubscript1subscriptsubscriptrefsubscriptsubscript2subscriptsubscriptrefsubscriptformulae-sequencesimilar-tosubscript1subscript1similar-tosubscript2subscript2delimited-[]subscriptsucceedssubscript1subscript2subscriptsucceedssubscript2subscript1 _ NLHF∈ *argmax_ _1∈ B_τ( _% ref) _ _2∈ B_τ( _ref)E_x_1 _1% ,x_2 _2[p_n(x_1 x_2)-p_n(x_2 x_1)],πsansserif_NLHF ∈ argmaxitalic_π start_POSTSUBSCRIPT 1 ∈ Bitalic_τ ( πref ) end_POSTSUBSCRIPT minitalic_π start_POSTSUBSCRIPT 2 ∈ Bitalic_τ ( πref ) end_POSTSUBSCRIPT blackboard_Ex start_POSTSUBSCRIPT 1 ∼ π1 , x2 ∼ π2 end_POSTSUBSCRIPT [ pitalic_n ( x1 ≻ x2 ) - pitalic_n ( x2 ≻ x1 ) ] , where pn⁢(x1≻x2)−pn⁢(x2≻x1)subscriptsucceedssubscript1subscript2subscriptsucceedssubscript2subscript1p_n(x_1 x_2)-p_n(x_2 x_1)pitalic_n ( x1 ≻ x2 ) - pitalic_n ( x2 ≻ x1 ) describes a Nash-equilibrium strategy for a symmetric two-player zero-sum game, and thus have value 00. Therefore, for π⋆∈Bτ⁢(πref)superscript⋆subscriptsubscriptrefπ ∈ B_τ( _ref)π⋆ ∈ Bitalic_τ ( πref ), it must hold that 0≤0absent 0≤0 ≤ x1∼π,x2∼π⋆[pn⁢(x1≻x2)−pn⁢(x2≻x1)]=x1∼π,x2∼π⋆[2⁢pn⁢(x1≻x2)−1]subscriptformulae-sequencesimilar-tosubscript1subscriptsimilar-tosubscript2superscript⋆subscriptsucceedssubscript1subscript2subscriptsucceedssubscript2subscript1subscriptformulae-sequencesimilar-tosubscript1subscriptsimilar-tosubscript2superscript⋆2subscriptsucceedssubscript1subscript21 *E_x_1 _ NLHF,x_2% π [p_n(x_1 x_2)-p_n(x_2 x_1) ]=% *E_x_1 _ NLHF,x_2 π % [2p_n(x_1 x_2)-1 ]blackboard_Ex start_POSTSUBSCRIPT 1 ∼ πsansserif_NLHF , x2 ∼ π⋆ end_POSTSUBSCRIPT [ pitalic_n ( x1 ≻ x2 ) - pitalic_n ( x2 ≻ x1 ) ] = blackboard_Ex start_POSTSUBSCRIPT 1 ∼ πsansserif_NLHF , x2 ∼ π⋆ end_POSTSUBSCRIPT [ 2 pitalic_n ( x1 ≻ x2 ) - 1 ] Since |pn⁢(x≻y)−p⁢(x≻y)|≤εn,d⁢(δ)subscriptsucceedssucceedssubscript |p_n(x y)-p(x y) |≤ _n,d(δ)| pitalic_n ( x ≻ y ) - p ( x ≻ y ) | ≤ εitalic_n , d ( δ ), we have ≤ ≤ x1∼π,x2∼π⋆[2⁢p⁢(x1≻x2)−1]+2⁢εn,d⁢(δ)subscriptformulae-sequencesimilar-tosubscript1subscriptsimilar-tosubscript2superscript⋆2succeedssubscript1subscript212subscript *E_x_1 _ NLHF,x_2% π [2p(x_1 x_2)-1 ]+2 _n,d(δ)blackboard_Ex start_POSTSUBSCRIPT 1 ∼ πsansserif_NLHF , x2 ∼ π⋆ end_POSTSUBSCRIPT [ 2 p ( x1 ≻ x2 ) - 1 ] + 2 εitalic_n , d ( δ ) According to the linearization lemma (Lemma 1), we have ≤ ≤ x1∼π,x2∼π⋆[2⁢β⁢(L⋅⁢(x1)−ℓβ⋅⁢(x2))]+2⁢εn,d⁢(δ)subscriptformulae-sequencesimilar-tosubscript1subscriptsimilar-tosubscript2superscript⋆2⋅subscript1⋅subscriptℓsubscript22subscript *E_x_1 _ NLHF,x_2% π [2β(L· AvgUtil(x_1)- _β·% AvgUtil(x_2)) ]+2 _n,d(δ)blackboard_Ex start_POSTSUBSCRIPT 1 ∼ πsansserif_NLHF , x2 ∼ π⋆ end_POSTSUBSCRIPT [ 2 β ( L ⋅ sansserif_AvgUtil ( x1 ) - ℓitalic_β ⋅ sansserif_AvgUtil ( x2 ) ) ] + 2 εitalic_n , d ( δ ) ≤ ≤ 2⁢β⁢(L⋅⁢(π)−ℓβ⋅⁢(π⋆)+εn,d⁢(δ)β).2⋅subscript⋅subscriptℓsuperscript⋆subscript 2β(L· AvgUtil( _ NLHF)- _β% · AvgUtil(π )+ _n,d(δ)β).2 β ( L ⋅ sansserif_AvgUtil ( πsansserif_NLHF ) - ℓitalic_β ⋅ sansserif_AvgUtil ( π⋆ ) + divide start_ARG εitalic_n , d ( δ ) end_ARG start_ARG β end_ARG ) . Therefore, under the successful event, we can lower bound the average utility of the NLHF policy by ⁢(π)≥ℓβL⁢(π⋆)−4⁢εn,d⁢(δ)β.subscriptsubscriptℓsuperscript⋆4subscript AvgUtil( _ NLHF)≥ _βL% AvgUtil(π )- 4 _n,d(δ)β.sansserif_AvgUtil ( πsansserif_NLHF ) ≥ divide start_ARG ℓitalic_β end_ARG start_ARG L end_ARG sansserif_AvgUtil ( π⋆ ) - divide start_ARG 4 εitalic_n , d ( δ ) end_ARG start_ARG β end_ARG . Taking the failure event into account, the expected average utility of the NLHF method is at least n⁢()≥subscriptabsent AvgUtil_n( NLHF)≥sansserif_AvgUtiln ( sansserif_NLHF ) ≥ (1−δ)⁢(ℓβL⁢(π⋆)−4⁢εn,d⁢(δ)β)1subscriptℓsuperscript⋆4subscript (1-δ) ( _βL AvgUtil(π % )- 4 _n,d(δ)β )( 1 - δ ) ( divide start_ARG ℓitalic_β end_ARG start_ARG L end_ARG sansserif_AvgUtil ( π⋆ ) - divide start_ARG 4 εitalic_n , d ( δ ) end_ARG start_ARG β end_ARG ) ≥ ≥ ℓβL⋅⁢(π⋆)−O⁢(εn,d⁢(δ)β+δ⋅ℓβL)⋅subscriptℓsuperscript⋆subscript⋅subscriptℓ _βL· AvgUtil(π )-O (% _n,d(δ)β+δ· _βL )divide start_ARG ℓitalic_β end_ARG start_ARG L end_ARG ⋅ sansserif_AvgUtil ( π⋆ ) - O ( divide start_ARG εitalic_n , d ( δ ) end_ARG start_ARG β end_ARG + δ ⋅ divide start_ARG ℓitalic_β end_ARG start_ARG L end_ARG ) Finally, choosing δ=Θ⁢(1n)Θ1δ= ( 1 n )δ = Θ ( divide start_ARG 1 end_ARG start_ARG square-root start_ARG n end_ARG end_ARG ), we have ≥ ≥ ℓβL⋅⁢(π⋆)−O⁢(1β⁢log⁡(m⁢n)n⋅min⁡1,d⋅μmin2+log⁡(m⁢n)n⋅β⁢μmin2).⋅subscriptℓsuperscript⋆1⋅1⋅superscriptsubscript2⋅superscriptsubscript2 _βL· AvgUtil(π )-O (% 1β (mn)n· \1,\,d· _ ^2\+% (mn)n·β _ ^2 ).divide start_ARG ℓitalic_β end_ARG start_ARG L end_ARG ⋅ sansserif_AvgUtil ( π⋆ ) - O ( divide start_ARG 1 end_ARG start_ARG β end_ARG square-root start_ARG divide start_ARG log ( m n ) end_ARG start_ARG n ⋅ min 1 , d ⋅ μroman_min2 end_ARG end_ARG + divide start_ARG log ( m n ) end_ARG start_ARG n ⋅ β μroman_min2 end_ARG ) . This completes the proof. ∎ E.2 Lower Bound for PPO-based RLHF and DPO See 6 Proof of Theorem 6. Suppose that the instance has m alternatives A=a,b,c1,…,cm−2subscript1…subscript2A=\a,b,c_1,…,c_m-2\A = a , b , c1 , … , citalic_m - 2 , where m−2≥4⁢eβ24superscriptm-2≥ 4e^βm - 2 ≥ 4 eitalic_β. Let the data collection distribution be uniform over all candidates, i.e., μ=⁢(A)μ= Uniform(A)μ = sansserif_Uniform ( A ). We consider the following distribution DD over utility vectors, such that the utility vector of a random agent i∼similar-toi ∼ D satisfies (ui⁢(a),ui⁢(b),ui⁢(c1),…,ui⁢(cm−2))=(0,1,0,…,0)(type I) with probability ⁢δ,(1β,0,1,…,1)(type I) with probability ⁢1−δ,subscriptsubscriptsubscriptsubscript1…subscriptsubscript2cases010…0(type I) with probability 101…1(type I) with probability 1 (u_i(a),u_i(b),u_i(c_1),…,u_i(c_m-2))= % cases (0,1,0,…,0 )&(type I) with probability δ,\\ ( 1β,0,1,…,1 )&(type I) with probability 1% -δ, cases( uitalic_i ( a ) , uitalic_i ( b ) , uitalic_i ( c1 ) , … , uitalic_i ( citalic_m - 2 ) ) = start_ROW start_CELL ( 0 , 1 , 0 , … , 0 ) end_CELL start_CELL (type I) with probability δ , end_CELL end_ROW start_ROW start_CELL ( divide start_ARG 1 end_ARG start_ARG β end_ARG , 0 , 1 , … , 1 ) end_CELL start_CELL (type I) with probability 1 - δ , end_CELL end_ROW where δ=1010+eβ=Θ⁢(e−β)1010superscriptΘsuperscriptδ= 1010+e^β= (e^-β)δ = divide start_ARG 10 end_ARG start_ARG 10 + eitalic_β end_ARG = Θ ( e- β ). In other words, type I users have a strong preference for candidate b but only constitute a δ fraction of the population, while type I users have a strong preference for c and weak preference for a≻bsucceedsa ba ≻ b and make up for a 1−δ11- 1 - δ fraction of the population. For the reference policy and the KL budget, we set πref⁢(a)=πref⁢(b)=1−ε2subscriptrefsubscriptref12 _ref(a)= _ref(b)= 1- 2πref ( a ) = πref ( b ) = divide start_ARG 1 - ε end_ARG start_ARG 2 end_ARG and πref⁢(ci)=εm−2subscriptrefsubscript2 _ref(c_i)= m-2πref ( citalic_i ) = divide start_ARG ε end_ARG start_ARG m - 2 end_ARG for all i∈[m−2]delimited-[]2i∈[m-2]i ∈ [ m - 2 ]. We leave the choice of ε ε to be determined later. The KL budget τ is set to be τ=11τ=1τ = 1. Analysis of the MLE reward. Now we show that when n→∞→n→∞n → ∞, the MLE reward satisfies r⁢(b)−r⁢(a)>00r(b)-r(a)>0r ( b ) - r ( a ) > 0. According to [Siththaranjan et al., 2023, Procaccia et al., 2025], it suffices to show that limn→∞n⁢(b)−n⁢(a)>0subscript→subscriptsubscript0 _n→∞ BC_n(b)- BC_n(a)>0limitalic_n → ∞ sansserif_BCn ( b ) - sansserif_BCn ( a ) > 0, which, by Lemma 11, is implied by ⋆⁢(b)−⋆⁢(a)>0superscript⋆superscript⋆0 BC (b)- BC (a)>0sansserif_BC⋆ ( b ) - sansserif_BC⋆ ( a ) > 0. We have ⋆⁢(b)−⋆⁢(a)=superscript⋆superscript⋆absent BC (b)- BC (a)=sansserif_BC⋆ ( b ) - sansserif_BC⋆ ( a ) = 1m⁢∑i=1m−2(p⁢(b≻ci)−p⁢(a≻ci))+1m⁢(p⁢(b≻a)−p⁢(a≻b))1superscriptsubscript12succeedssubscriptsucceedssubscript1succeedssucceeds 1m _i=1^m-2 (p(b c_i)-p(a c_i)% )+ 1m (p(b a)-p(a b) )divide start_ARG 1 end_ARG start_ARG m end_ARG ∑i = 1m - 2 ( p ( b ≻ citalic_i ) - p ( a ≻ citalic_i ) ) + divide start_ARG 1 end_ARG start_ARG m end_ARG ( p ( b ≻ a ) - p ( a ≻ b ) ) For each cisubscriptc_icitalic_i, we have p⁢(b≻ci)−p⁢(a≻ci)=δ⋅(σ⁢(β)−σ⁢(0))+(1−δ)⋅(σ⁢(−β)−σ⁢(1−β)).succeedssubscriptsucceedssubscript⋅0⋅11 p(b c_i)-p(a c_i)=δ· (σ(β)-% σ(0) )+(1-δ)· (σ(-β)-σ(1-β) ).p ( b ≻ citalic_i ) - p ( a ≻ citalic_i ) = δ ⋅ ( σ ( β ) - σ ( 0 ) ) + ( 1 - δ ) ⋅ ( σ ( - β ) - σ ( 1 - β ) ) . In the above equation, the first term accounts for type-I users and is lower bounded by δ33 δ3divide start_ARG δ end_ARG start_ARG 3 end_ARG when β≥22β≥ 2β ≥ 2. The second term accounts for type-I users, and we leverage the fact that σ⁢(x)σ(x)σ ( x ) is concave when x≥00x≥ 0x ≥ 0 to bound it as (1−δ)⋅(σ⁢(−β)−σ⁢(1−β))=−eβ10⁢δ⋅(σ⁢(β)−σ⁢(β−1))≥−eβ10⁢δ⋅σ′⁢(β−1)≥−e10⁢δ,⋅11⋅superscript101⋅superscript10superscript′110 (1-δ)· (σ(-β)-σ(1-β) )=- % e^β10δ· (σ(β)-σ(β-1) )≥- % e^β10δ·σ (β-1)≥- e10δ,( 1 - δ ) ⋅ ( σ ( - β ) - σ ( 1 - β ) ) = - divide start_ARG eitalic_β end_ARG start_ARG 10 end_ARG δ ⋅ ( σ ( β ) - σ ( β - 1 ) ) ≥ - divide start_ARG eitalic_β end_ARG start_ARG 10 end_ARG δ ⋅ σ′ ( β - 1 ) ≥ - divide start_ARG e end_ARG start_ARG 10 end_ARG δ , where the last step uses σ′⁢(x)=σ⁢(x)⋅(1−σ⁢(x))≤1−σ⁢(x)≤e−xsuperscript′⋅11superscriptσ (x)=σ(x)·(1-σ(x))≤ 1-σ(x)≤ e^-xσ′ ( x ) = σ ( x ) ⋅ ( 1 - σ ( x ) ) ≤ 1 - σ ( x ) ≤ e- x for all x. Plugging both bounds into the limit ⋆⁢(b)−⋆⁢(a)superscript⋆superscript⋆ BC (b)- BC (a)sansserif_BC⋆ ( b ) - sansserif_BC⋆ ( a ) and substituting δ=1010+eβ≥20m−21010superscript202δ= 1010+e^β≥ 20m-2δ = divide start_ARG 10 end_ARG start_ARG 10 + eitalic_β end_ARG ≥ divide start_ARG 20 end_ARG start_ARG m - 2 end_ARG gives limn→∞⁢(b)−⁢(a)=⋆⁢(b)−⋆⁢(a)≥m−2m⋅δ⋅(13−e10)−1m≥1m.subscript→superscript⋆superscript⋆⋅2131011 _n→∞ BC(b)- BC(a)= BC % (b)- BC (a)≥ m-2m·δ· ( 13-% e10 )- 1m≥ 1m.limitalic_n → ∞ sansserif_BC ( b ) - sansserif_BC ( a ) = sansserif_BC⋆ ( b ) - sansserif_BC⋆ ( a ) ≥ divide start_ARG m - 2 end_ARG start_ARG m end_ARG ⋅ δ ⋅ ( divide start_ARG 1 end_ARG start_ARG 3 end_ARG - divide start_ARG e end_ARG start_ARG 10 end_ARG ) - divide start_ARG 1 end_ARG start_ARG m end_ARG ≥ divide start_ARG 1 end_ARG start_ARG m end_ARG . Therefore, when n is sufficiently large, we have ⁢(b)>⁢(a) BC(b)> BC(a)sansserif_BC ( b ) > sansserif_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 ⋆⁢(ci)=⋆⁢(cj)superscript⋆subscriptsuperscript⋆subscript BC (c_i)= BC (c_j)sansserif_BC⋆ ( citalic_i ) = sansserif_BC⋆ ( citalic_j ) for all i,j∈[m−2]delimited-[]2i,j∈[m-2]i , j ∈ [ m - 2 ], we have maxi,j∈[m−2]⁡|r⁢(ci)−r⁢(cj)|→0→subscriptdelimited-[]2subscriptsubscript0 _i,j∈[m-2]|r(c_i)-r(c_j)|→ 0maxitalic_i , j ∈ [ m - 2 ] | r ( citalic_i ) - r ( citalic_j ) | → 0 when n→∞→n→∞n → ∞. 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 π⋆superscript⋆π π⋆ and π^subscript π_ RLHFover start_ARG π end_ARGsansserif_RLHF 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 Section E.4. As a result, we can view all type-c candidates as a single candidate c which have mass ε ε under the reference policy. We now show that for any η>00η>0η > 0, there exists an ε>00 >0ε > 0 such that any policy π∈Δ⁢(a,b,c)Δπ∈ (\a,b,c\)π ∈ Δ ( a , b , c ) inside the KL ball Bτ⁢(πref)subscriptsubscriptrefB_τ( _ref)Bitalic_τ ( πref ) cannot put more than η mass on c. We have 1≥DKL⁢(π∥πref)=1subscriptKLconditionalsubscriptrefabsent 1≥ D_KL(π\,\|\, _ref)=1 ≥ DKL ( π ∥ πref ) = π⁢(a)⋅log⁡π⁢(a)(1−ε)/2+π⁢(b)⋅log⁡π⁢(b)(1−ε)/2+π⁢(c)⋅log⁡π⁢(c)ε⋅12⋅12⋅ π(a)· π(a)(1- )/2+π(b)· % π(b)(1- )/2+π(c)· π(c) π ( a ) ⋅ log divide start_ARG π ( a ) end_ARG start_ARG ( 1 - ε ) / 2 end_ARG + π ( b ) ⋅ log divide start_ARG π ( b ) end_ARG start_ARG ( 1 - ε ) / 2 end_ARG + π ( c ) ⋅ log divide start_ARG π ( c ) end_ARG start_ARG ε end_ARG Fixing π⁢(c)π(c)π ( c ), the KL divergence is minimized when π⁢(a)=π⁢(b)=1−π⁢(c)212π(a)=π(b)= 1-π(c)2π ( a ) = π ( b ) = divide start_ARG 1 - π ( c ) end_ARG start_ARG 2 end_ARG. Substituting this into the KL divergence, we get ≥ ≥ (1−π⁢(c))⋅log⁡1−π⁢(c)1−ε+π⁢(c)⋅log⁡π⁢(c)ε⋅111⋅ (1-π(c))· 1-π(c)1- +π(c)· % π(c) ( 1 - π ( c ) ) ⋅ log divide start_ARG 1 - π ( c ) end_ARG start_ARG 1 - ε end_ARG + π ( c ) ⋅ log divide start_ARG π ( c ) end_ARG start_ARG ε end_ARG Since t⁢log⁡t≥−1/e1t t≥-1/et log t ≥ - 1 / e for all t>00t>0t > 0, and log⁡11−ε>0110 11- >0log divide start_ARG 1 end_ARG start_ARG 1 - ε end_ARG > 0, we have ≥ ≥ −2e+π⁢(c)⁢log⁡1ε.21 - 2e+π(c) 1 .- divide start_ARG 2 end_ARG start_ARG e end_ARG + π ( c ) log divide start_ARG 1 end_ARG start_ARG ε end_ARG . Therefore, any policy in the KL ball must satisfy π⁢(c)⁢log⁡1ε≤1+2/e≤21122π(c) 1 ≤ 1+2/e≤ 2π ( c ) log divide start_ARG 1 end_ARG start_ARG ε end_ARG ≤ 1 + 2 / e ≤ 2, which implies that π⁢(c)≤2log⁡(1/ε)21π(c)≤ 2 (1/ )π ( c ) ≤ divide start_ARG 2 end_ARG start_ARG log ( 1 / ε ) end_ARG. We can choose ε ε to be any constant smaller than e−2/ηsuperscript2e^-2/ηe- 2 / η to ensure that π⁢(c)≤ηπ(c)≤ηπ ( c ) ≤ η. We then show that when η is sufficiently small, πsubscript _ RLHFπsansserif_RLHF puts almost all probability mass on b, whereas π⋆superscript⋆π π⋆ puts almost all probability mass on a. This will ultimately lead to a distortion of ⁢(π⋆)⁢(π^)=Θ⁢(⁢(a))Θ⁢(⁢(b))=Θ⁢(1/β)Θ⁢(e−β)=eΩ⁢(β).superscript⋆subscript^Θ1ΘsuperscriptsuperscriptΩ AvgUtil(π ) AvgUtil( π_ RLHF% )= ( AvgUtil(a)) ( AvgUtil(b))= % (1/β) (e^-β)=e (β).divide start_ARG sansserif_AvgUtil ( π⋆ ) end_ARG start_ARG sansserif_AvgUtil ( over start_ARG π end_ARGsansserif_RLHF ) end_ARG = divide start_ARG Θ ( sansserif_AvgUtil ( a ) ) end_ARG start_ARG Θ ( sansserif_AvgUtil ( b ) ) end_ARG = divide start_ARG Θ ( 1 / β ) end_ARG start_ARG Θ ( e- β ) end_ARG = eroman_Ω ( β ) . • For πsubscript _ RLHFπsansserif_RLHF, we assume that the estimated reward is shifted such that r⁢(c)=00r(c)=0r ( c ) = 0 (as a result, r⁢(a)<r⁢(b)<00r(a)<r(b)<0r ( a ) < r ( b ) < 0). Since π′=(0,1,0)superscript′010π =(0,1,0)π′ = ( 0 , 1 , 0 ) also satisfies the KL constraint, we have r⁢(π)≥r⁢(π′)subscriptsuperscript′r( _ RLHF)≥ r(π )r ( πsansserif_RLHF ) ≥ r ( π′ ). Together with the fact that π⁢(c)≤ηsubscript _ RLHF(c)≤ηπsansserif_RLHF ( c ) ≤ η, we have r⁢(π′)=r⁢(b)≤superscript′absent r(π )=r(b)≤r ( π′ ) = r ( b ) ≤ r⁢(π)=r⁢(a)⁢π⁢(a)+r⁢(b)⁢π⁢(b)subscriptsubscriptsubscript r( _ RLHF)=r(a) _ RLHF(a)+r(b) _% RLHF(b)r ( πsansserif_RLHF ) = r ( a ) πsansserif_RLHF ( a ) + r ( b ) πsansserif_RLHF ( b ) ≤ ≤ π⁢(a)⋅r⁢(a)+(1−π⁢(a)−η)⋅r⁢(b).⋅subscript⋅1subscript _ RLHF(a)· r(a)+(1- _ RLHF(a)-η)% · r(b).πsansserif_RLHF ( a ) ⋅ r ( a ) + ( 1 - πsansserif_RLHF ( a ) - η ) ⋅ r ( b ) . Therefore, we have π⁢(a)≤η⋅|r⁢(b)||r⁢(b)−r⁢(a)|subscript⋅ _ RLHF(a)≤η· |r(b)||r(b)-r(a)|πsansserif_RLHF ( a ) ≤ η ⋅ divide start_ARG | r ( b ) | end_ARG start_ARG | r ( b ) - r ( a ) | end_ARG. Setting ε ε to be sufficiently small, we can guarantee that η≤η1:=e−β1+|r⁢(b)||r⁢(b)−r⁢(a)|,subscript1assignsuperscript1 η≤ _1:= e^-β1+ |r(b)||r(b)-r(a)|,η ≤ η1 := divide start_ARG e- β end_ARG start_ARG 1 + divide start_ARG | r ( b ) | end_ARG start_ARG | r ( b ) - r ( a ) | end_ARG end_ARG , (12) and thus π⁢(a)+π⁢(c)≤η⁢(1+|r⁢(b)||r⁢(b)−r⁢(a)|)≤e−βsubscriptsubscript1superscript _ RLHF(a)+ _ RLHF(c)≤η (1+ |r(b)||r(% b)-r(a)| )≤ e^-βπsansserif_RLHF ( a ) + πsansserif_RLHF ( c ) ≤ η ( 1 + divide start_ARG | r ( b ) | end_ARG start_ARG | r ( b ) - r ( a ) | end_ARG ) ≤ e- β. As a result, we have ⁢(π)=Θ⁢(⁢(b))subscriptΘ AvgUtil( _ RLHF)= ( AvgUtil(b))sansserif_AvgUtil ( πsansserif_RLHF ) = Θ ( sansserif_AvgUtil ( b ) ). • For π⋆superscript⋆π π⋆, a similar argument shows that when η≤η2:=e−β1+⁢(a)⁢(a)−⁢(b),subscript2assignsuperscript1 η≤ _2:= e^-β1+ AvgUtil(a)% AvgUtil(a)- AvgUtil(b),η ≤ η2 := divide start_ARG e- β end_ARG start_ARG 1 + divide start_ARG sansserif_AvgUtil ( a ) end_ARG start_ARG sansserif_AvgUtil ( a ) - sansserif_AvgUtil ( b ) end_ARG end_ARG , (13) We have π⋆⁢(b)+π⋆⁢(c)≤e−βsuperscript⋆superscript⋆superscriptπ (b)+π (c)≤ e^-βπ⋆ ( b ) + π⋆ ( c ) ≤ e- β. As a result, we have ⁢(π⋆)=Θ⁢(⁢(a))superscript⋆Θ AvgUtil(π )= ( AvgUtil(a))sansserif_AvgUtil ( π⋆ ) = Θ ( sansserif_AvgUtil ( a ) ). Finally, we set ε ε to be smaller than e−2/min⁡η1,η2superscript2subscript1subscript2e^-2/ \ _1, _2\e- 2 / min η1 , η2 such that Equations 12 and 13 are both satisfied. This ensures ⁢(π⋆)/⁢(π)=eΩ⁢(β)superscript⋆subscriptsuperscriptΩ AvgUtil(π )/ AvgUtil( _ RLHF)=e (% β)sansserif_AvgUtil ( π⋆ ) / sansserif_AvgUtil ( πsansserif_RLHF ) = eroman_Ω ( β ) and completes the proof. ∎ E.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. [2025], which shows that DPO also aligns with the Borda count. We start by recalling the DPO objective [Rafailov et al., 2023].131313Note that the parameter β does not need to be the same as the true temperature of the Bradley-Terry model in our setting. ℒDPO⁢(π;πref)=−∑1≤i≤n,1≤j≤dlog⁡σ⁢(β⁢log⁡π⁢(xij)πref⁢(xij)−β⁢log⁡π⁢(yij)πref⁢(yij)).subscriptℒDPOsubscriptrefsubscriptformulae-sequence11superscriptsubscriptsubscriptrefsuperscriptsubscriptsuperscriptsubscriptsubscriptrefsuperscriptsubscript _DPO(π; _ref)=- _1≤ i≤ n% ,1≤ j≤ d σ (β π(x_i^j) _ref% (x_i^j)-β π(y_i^j) _ref(y_i^j) ).LDPO ( π ; πref ) = - ∑1 ≤ i ≤ n , 1 ≤ j ≤ d log σ ( β log divide start_ARG π ( xitalic_iitalic_j ) end_ARG start_ARG πref ( xitalic_iitalic_j ) end_ARG - β log divide start_ARG π ( yitalic_iitalic_j ) end_ARG start_ARG πref ( yitalic_iitalic_j ) end_ARG ) . Now we perform a change of variables to transform π into the following form: π⁢(x)=πref⁢(x)⋅exp⁡(r^⁢(x)/β)wherer^⁢(x):=β⁢log⁡π⁢(x)πref⁢(x),∀x∈A.formulae-sequence⋅subscriptref^whereformulae-sequenceassign^subscriptreffor-all π(x)= _ref(x)· ( r(x)/β) % where r(x):=β π(x) _ref(x),\ ∀ x% ∈ A.π ( x ) = πref ( x ) ⋅ exp ( over start_ARG r end_ARG ( x ) / β ) where over start_ARG r end_ARG ( x ) := β log divide start_ARG π ( x ) end_ARG start_ARG πref ( x ) end_ARG , ∀ x ∈ A . Substituting this into the DPO objective, we get: ℒDPO⁢(π;πref)=−∑1≤i≤n,1≤j≤dlog⁡(σ⁢(r^⁢(xij)−r^⁢(yij))),subscriptℒDPOsubscriptrefsubscriptformulae-sequence11^superscriptsubscript^superscriptsubscript _DPO(π; _ref)=- _1≤ i≤ n% ,1≤ j≤ d (σ( r(x_i^j)- r(y_i^j)) ),LDPO ( π ; πref ) = - ∑1 ≤ i ≤ n , 1 ≤ j ≤ d log ( σ ( over start_ARG r end_ARG ( xitalic_iitalic_j ) - over start_ARG r end_ARG ( yitalic_iitalic_j ) ) ) , which is exactly the MLE objective for reward learning in RLHF, repeated here for convenience: ℒMLE⁢(r):=−∑1≤i≤n,1≤j≤dlog⁡(σ⁢(r⁢(xij)−r⁢(yij))).assignsubscriptℒMLEsubscriptformulae-sequence11superscriptsubscriptsuperscriptsubscript _MLE(r):=- _1≤ i≤ n,1≤ j≤ d% (σ(r(x_i^j)-r(y_i^j)) ).LMLE ( r ) := - ∑1 ≤ i ≤ n , 1 ≤ j ≤ d log ( σ ( r ( xitalic_iitalic_j ) - r ( yitalic_iitalic_j ) ) ) . Therefore, there is a one-to-one correspondence between the MLE reward r⋆=argminr∈ℝmℒMLE⁢(r)superscript⋆subscriptargminsuperscriptℝsubscriptℒMLEr = *argmin_r ^mL_MLE(r)r⋆ = argminitalic_r ∈ blackboard_Rm LMLE ( r )141414Note that we have a minus sign in the MLE objective, which is equivalent to maximizing the sum of log-likelihoods., and the DPO policy π=argminπℒDPO⁢(π;πref)subscriptsubscriptargminsubscriptℒDPOsubscriptref _ DPO= *argmin_πL_DPO(π;% _ref)πsansserif_DPO = argminitalic_π LDPO ( π ; πref ) as: π⁢(x)=πref⁢(x)⋅exp⁡(r⋆⁢(x)/β).subscript⋅subscriptrefsuperscript⋆ _ DPO(x)= _ref(x)· (r (x)/% β).πsansserif_DPO ( x ) = πref ( x ) ⋅ exp ( r⋆ ( x ) / β ) . On the other hand, the RLHF policy with regularization parameter λ (see Section E.4 for the equivalence between regularized and constrained versions of RLHF) is also given by π⁢(x)=πref⁢(x)⋅exp⁡(r⋆⁢(x)/λ).subscript⋅subscriptrefsuperscript⋆ _ RLHF(x)= _ref(x)· (r (x)/% λ).πsansserif_RLHF ( x ) = πref ( x ) ⋅ exp ( r⋆ ( x ) / λ ) . Therefore, the DPO policy πsubscript _ DPOπsansserif_DPO and the RLHF policy πsubscript _ RLHFπsansserif_RLHF are equivalent when the parameter β in the DPO objective is equal to λ in the RLHF objective. Notably, both policies are different from the optimal policy π⋆∝πref⋅exp⁡(⁢(x)/λ′)proportional-tosuperscript⋆⋅subscriptrefsuperscript′π _ref· ( AvgUtil(x)/λ^% )π⋆ ∝ πref ⋅ exp ( sansserif_AvgUtil ( x ) / λ′ ) (for a potentially different λ′λ λ′ that make the KL constraint tight) as r⋆≠superscript⋆r ≠ AvgUtilr⋆ ≠ sansserif_AvgUtil, which has also been pointed out by Shirali et al. [2025]. E.4 Equivalence of Regularized and Constrained Alignment Methods In this section, we formally establish the equivalence between regularized and constrained formulations of both RLHF and NLHF. 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 NLHF.). Let πτsubscript _τπitalic_τ be the output of the τ-constrained NLHF method defined in Section 2, i.e., πτ=argmaxπ1∈Bτ⁢(πref)minπ2∈Bτ⁢(πref)⁢x1∼π1,x2∼π2[Mx1,x2],subscriptsubscriptargmaxsubscript1subscriptsubscriptrefsubscriptsubscript2subscriptsubscriptrefsubscriptformulae-sequencesimilar-tosubscript1subscript1similar-tosubscript2subscript2subscriptsubscript1subscript2 _τ= *argmax_ _1∈ B_τ( _ % ref) _ _2∈ B_τ( _ref) *E% _x_1 _1,x_2 _2 [M_x_1,x_2 ],πitalic_τ = argmaxitalic_π start_POSTSUBSCRIPT 1 ∈ Bitalic_τ ( πref ) end_POSTSUBSCRIPT minitalic_π start_POSTSUBSCRIPT 2 ∈ Bitalic_τ ( πref ) end_POSTSUBSCRIPT blackboard_Ex start_POSTSUBSCRIPT 1 ∼ π1 , x2 ∼ π2 end_POSTSUBSCRIPT [ Mitalic_x start_POSTSUBSCRIPT 1 , x2 end_POSTSUBSCRIPT ] , (14) and let π~λsubscript~ π_λover~ start_ARG π end_ARGλ be the output of the λ-regularized NLHF method [Munos et al., 2024], i.e., π~λ=argmaxπ1∈Δ⁢(M)minπ2∈Δ⁢(M)⁢x1∼π1,x2∼π2[Mx1,x2]−λ⋅DKL⁢(π1∥πref)+λ⋅DKL⁢(π2∥πref).subscript~subscriptargmaxsubscript1Δsubscriptsubscript2Δsubscriptformulae-sequencesimilar-tosubscript1subscript1similar-tosubscript2subscript2subscriptsubscript1subscript2⋅subscriptKLconditionalsubscript1subscriptref⋅subscriptKLconditionalsubscript2subscriptref π_λ= *argmax_ _1∈ (M)% _ _2∈ (M) *E_x_1 _1,x_2% _2 [M_x_1,x_2 ]-λ· D_KL( _1\,% \|\, _ref)+λ· D_KL( _2\,\|\, _ref).over~ start_ARG π end_ARGλ = argmaxitalic_π start_POSTSUBSCRIPT 1 ∈ Δ ( M ) end_POSTSUBSCRIPT minitalic_π start_POSTSUBSCRIPT 2 ∈ Δ ( M ) end_POSTSUBSCRIPT blackboard_Ex start_POSTSUBSCRIPT 1 ∼ π1 , x2 ∼ π2 end_POSTSUBSCRIPT [ Mitalic_x start_POSTSUBSCRIPT 1 , x2 end_POSTSUBSCRIPT ] - λ ⋅ DKL ( π1 ∥ πref ) + λ ⋅ DKL ( π2 ∥ πref ) . (15) Then, for each λ∈[0,∞]0λ∈[0,∞]λ ∈ [ 0 , ∞ ] with solution π~λsubscript~ π_λover~ start_ARG π end_ARGλ for Eq. 15, we have that π~λsubscript~ π_λover~ start_ARG π end_ARGλ is also an optimal solution to the τ-constrained optimization problem in Eq. 14, where τ=DKL⁢(π~λ∥πref)subscriptKLconditionalsubscript~subscriptrefτ=D_KL( π_λ\,\|\, _ref)τ = DKL ( over~ start_ARG π end_ARGλ ∥ πref ). Conversely, for each τ≥00τ≥ 0τ ≥ 0 with solution πτsubscript _τπitalic_τ for Eq. 14, there exists λ∈[0,∞]0λ∈[0,∞]λ ∈ [ 0 , ∞ ] such that πτsubscript _τπitalic_τ is also an optimal solution to the λ-regularized optimization problem in Eq. 15. Proof of Proposition 13. We start by observing that in both games Eq. 14 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 0, and both games have symmetric Nash equilibria. Now, we prove the two directions of the claim separately. Regularized ⇒ ⇒ Constrained. Given λ∈[0,∞]0λ∈[0,∞]λ ∈ [ 0 , ∞ ] and π~λsubscript~ π_λover~ start_ARG π end_ARGλ be the solution to Eq. 15. Consider the constrained optimization problem in Eq. 14 with τ=DKL⁢(π~λ∥πref)subscriptKLconditionalsubscript~subscriptrefτ=D_KL( π_λ\,\|\, _ref)τ = DKL ( over~ start_ARG π end_ARGλ ∥ πref ). We show that π2=π~λsubscript2subscript~ _2= π_λπ2 = over~ start_ARG π end_ARGλ is a best response to π1=π~λsubscript1subscript~ _1= π_λπ1 = over~ start_ARG π end_ARGλ in the constrained game with radius τ=DKL⁢(π~λ∥πref)subscriptKLconditionalsubscript~subscriptrefτ=D_KL( π_λ\,\|\, _ref)τ = DKL ( over~ start_ARG π end_ARGλ ∥ πref ), i.e., π~λ=argminπ2∈Bτ⁢(πref)x1∼π~λ,x2∼π2[Mx1,x2]subscript~subscriptargminsubscript2subscriptsubscriptrefsubscriptformulae-sequencesimilar-tosubscript1subscript~similar-tosubscript2subscript2subscriptsubscript1subscript2 π_λ= *argmin_ _2∈ B_τ% ( _ref) *E_x_1 π_λ,% x_2 _2 [M_x_1,x_2 ]over~ start_ARG π end_ARGλ = argminitalic_π start_POSTSUBSCRIPT 2 ∈ Bitalic_τ ( πref ) end_POSTSUBSCRIPT blackboard_Ex start_POSTSUBSCRIPT 1 ∼ over~ start_ARG π end_ARGλ , x2 ∼ π2 end_POSTSUBSCRIPT [ Mitalic_x start_POSTSUBSCRIPT 1 , x2 end_POSTSUBSCRIPT ] (16) If Eq. 16 holds, then by the fact that the utility is anti-symmetric, we have that π1=π~λsubscript1subscript~ _1= π_λπ1 = over~ start_ARG π end_ARGλ is also a best response to π2=π~λsubscript2subscript~ _2= π_λπ2 = over~ start_ARG π end_ARGλ in the same constrained game. Putting both together, we have that (π~λ,π~λ)subscript~subscript~( π_λ, π_λ)( over~ start_ARG π end_ARGλ , over~ start_ARG π end_ARGλ ) is a Nash equilibrium for the constrained game with radius τ=DKL⁢(π~λ∥πref)subscriptKLconditionalsubscript~subscriptrefτ=D_KL( π_λ\,\|\, _ref)τ = DKL ( over~ start_ARG π end_ARGλ ∥ πref ), thus establishing the first direction. Now we prove Equation 16. To see this, note that ∀π2∈Bτ⁢(πref)for-allsubscript2subscriptsubscriptref∀ _2∈ B_τ( _ref)∀ π2 ∈ Bitalic_τ ( πref ), we have that DKL⁢(π2∥πref)≤τ=DKL⁢(π~λ∥πref)subscriptKLconditionalsubscript2subscriptrefsubscriptKLconditionalsubscript~subscriptrefD_KL( _2\,\|\, _ref)≤τ=D_KL( π% _λ\,\|\, _ref)DKL ( π2 ∥ πref ) ≤ τ = DKL ( over~ start_ARG π end_ARGλ ∥ πref ). Therefore, from the fact that π~λsubscript~ π_λover~ start_ARG π end_ARGλ is a Nash equilibrium for the regularized game Eq. 15, we have that for any π2∈Δ⁢(M)subscript2Δ _2∈ (M)π2 ∈ Δ ( M ) and specifically π2∈Bτ⁢(πref)subscript2subscriptsubscriptref _2∈ B_τ( _ref)π2 ∈ Bitalic_τ ( πref ), we have that x1∼π~λ,x2∼π2[Mx1,x2]+λ⋅DKL⁢(π2∥πref)≥x1∼π~λ,x2∼π~λ[Mx1,x2]+λ⋅DKL⁢(π~λ∥πref)subscriptformulae-sequencesimilar-tosubscript1subscript~similar-tosubscript2subscript2subscriptsubscript1subscript2⋅subscriptKLconditionalsubscript2subscriptrefsubscriptformulae-sequencesimilar-tosubscript1subscript~similar-tosubscript2subscript~subscriptsubscript1subscript2⋅subscriptKLconditionalsubscript~subscriptref *E_x_1 π_λ,x_2% _2 [M_x_1,x_2 ]+λ· D_KL( _2\,% \|\, _ref)≥ *E_x_1 π_% λ,x_2 π_λ [M_x_1,x_2 ]+λ% · D_KL( π_λ\,\|\, _ref)blackboard_Ex start_POSTSUBSCRIPT 1 ∼ over~ start_ARG π end_ARGλ , x2 ∼ π2 end_POSTSUBSCRIPT [ Mitalic_x start_POSTSUBSCRIPT 1 , x2 end_POSTSUBSCRIPT ] + λ ⋅ DKL ( π2 ∥ πref ) ≥ blackboard_Ex start_POSTSUBSCRIPT 1 ∼ over~ start_ARG π end_ARGλ , x2 ∼ over~ start_ARG π end_ARGλ end_POSTSUBSCRIPT [ Mitalic_x start_POSTSUBSCRIPT 1 , x2 end_POSTSUBSCRIPT ] + λ ⋅ DKL ( over~ start_ARG π end_ARGλ ∥ πref ) ⇒ \ ⇒ x1∼π~λ,x2∼π2[Mx1,x2]−x1∼π~λ,x2∼π~λ[Mx1,x2]≥λ⋅(DKL⁢(π~λ∥πref)−DKL⁢(π2∥πref))≥0.subscriptformulae-sequencesimilar-tosubscript1subscript~similar-tosubscript2subscript2subscriptsubscript1subscript2subscriptformulae-sequencesimilar-tosubscript1subscript~similar-tosubscript2subscript~subscriptsubscript1subscript2⋅subscriptKLconditionalsubscript~subscriptrefsubscriptKLconditionalsubscript2subscriptref0 *E_x_1 π_λ,x_2% _2 [M_x_1,x_2 ]- *E_x_1 % π_λ,x_2 π_λ [M_x_1,x_2% ]≥λ· (D_KL( π_λ\,\|\, _% ref)-D_KL( _2\,\|\, _ref) )≥ 0.blackboard_Ex start_POSTSUBSCRIPT 1 ∼ over~ start_ARG π end_ARGλ , x2 ∼ π2 end_POSTSUBSCRIPT [ Mitalic_x start_POSTSUBSCRIPT 1 , x2 end_POSTSUBSCRIPT ] - blackboard_Ex start_POSTSUBSCRIPT 1 ∼ over~ start_ARG π end_ARGλ , x2 ∼ over~ start_ARG π end_ARGλ end_POSTSUBSCRIPT [ Mitalic_x start_POSTSUBSCRIPT 1 , x2 end_POSTSUBSCRIPT ] ≥ λ ⋅ ( DKL ( over~ start_ARG π end_ARGλ ∥ πref ) - DKL ( π2 ∥ πref ) ) ≥ 0 . 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 λ. For simplicity, we write π1⁢M⁢π2superscriptsubscript1subscript2 _1 TM _2π1sansserif_T M π2 as a shorthand for x1∼π1,x2∼π2[Mx1,x2]subscriptformulae-sequencesimilar-tosubscript1subscript1similar-tosubscript2subscript2subscriptsubscript1subscript2 *E_x_1 _1,x_2 _2 [M_x_1,x% _2 ]blackboard_Ex start_POSTSUBSCRIPT 1 ∼ π1 , x2 ∼ π2 end_POSTSUBSCRIPT [ Mitalic_x start_POSTSUBSCRIPT 1 , x2 end_POSTSUBSCRIPT ]. Then minimizing player in the constrained game Eq. 14 with π1=πτsubscript1subscript _1= _τπ1 = πitalic_τ can be written as minπ2∈ℝm⁡πτ⁢M⁢π2s.t.D⁢(π2∥πref)≤τ,π2≥,⁢π2=1.formulae-sequencesubscriptsubscript2superscriptℝsuperscriptsubscriptsubscript2s.t.subscriptconditionalsubscript2subscriptrefformulae-sequencesubscript20superscript1subscript21 _ _2 ^m _τ TM _2% .t. D_ KL( _2\| _ref)≤τ, _% 2 0,1 T _2=1.minitalic_π start_POSTSUBSCRIPT 2 ∈ blackboard_Rm end_POSTSUBSCRIPT πitalic_τsansserif_T M π2 s.t. Dsansserif_KL ( π2 ∥ πref ) ≤ τ , π2 ≥ 0 , 1sansserif_T π2 = 1 . (Constrained Minimization) The Lagrangian of this problem is ℒ⁢(π2,λ,μ→,η)=πτ⁢M⁢π2+λ⁢(D⁢(π2∥πref)−τ)−μ→⁢π2+η⁢π2,ℒsubscript2→superscriptsubscriptsubscript2subscriptconditionalsubscript2subscriptrefsuperscript→subscript2superscript1subscript2 ( _2,λ, μ,η)= _τ T% M _2+λ (D_ KL( _2\| _ref)-τ )% - μ T _2+ 1 T _2,L ( π2 , λ , over→ start_ARG μ end_ARG , η ) = πitalic_τsansserif_T M π2 + λ ( Dsansserif_KL ( π2 ∥ πref ) - τ ) - over→ start_ARG μ end_ARGsansserif_T π2 + η 1sansserif_T π2 , where λ,μ→,η≥0→0λ, μ,η≥ 0λ , over→ start_ARG μ end_ARG , η ≥ 0 are the Lagrange multipliers for the KL divergence constraint, the non-negativity constraint, and the normalization constraint, respectively. Since the utility π1⁢M⁢π2superscriptsubscript1subscript2 _1 TM _2π1sansserif_T M π2 is convex, the normalization constraint is affine, and the inequality constraints are convex, and the reference policy πrefsubscriptref _refπref is strictly feasible with D⁢(πref∥πref)=0<τsubscriptconditionalsubscriptrefsubscriptref0D_ KL( _ref\| _ref)=0< _KL ( πref ∥ πref ) = 0 < τ,151515 If τ=00τ=0τ = 0, the only feasible policy is πrefsubscriptref _refπref, and the claim clearly holds for λ=∞λ=∞λ = ∞. We also assume that πref⁢(a)>0subscriptref0 _ref(a)>0πref ( a ) > 0 for all a∈Ma∈ Ma ∈ M. Otherwise if πref⁢(a)=0subscriptref0 _ref(a)=0πref ( a ) = 0 for some a∈Ma∈ Ma ∈ M, then both the regularized and constrained versions forbid any policy to put nonzero probability on a, which leads to an effectively smaller candidate set. the Slater’s condition is satisfied, which guarantees that the KKT conditions are necessary and sufficient for optimality — there exists parameters λ⋆,μ→⋆,η⋆≥0superscript⋆superscript→⋆superscript⋆0λ , μ ,η ≥ 0λ⋆ , over→ start_ARG μ end_ARG⋆ , η⋆ ≥ 0 such that as an optimal solution to Eq. Constrained Minimization, π2=πλsubscript2subscript _2= _λπ2 = πitalic_λ satisfies the following KKT conditions: ∇π2ℒ⁢(π2,λ⋆,μ→⋆,η⋆)=M⁢πτ+λ⋆⋅∇π2D⁢(π2∥πref)−μ→⋆+η⋆⋅=0,subscript∇subscript2ℒsubscript2superscript⋆superscript→⋆superscript⋆superscriptsubscript⋅superscript⋆subscript∇subscript2subscriptconditionalsubscript2subscriptrefsuperscript→⋆⋅superscript⋆10 _ _2L( _2,λ , μ^% ,η )=M T _τ+λ · _ _% 2D_ KL( _2\| _ref)- μ +η % ·1=0,∇π start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT L ( π2 , λ⋆ , over→ start_ARG μ end_ARG⋆ , η⋆ ) = Msansserif_T πitalic_τ + λ⋆ ⋅ ∇π start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT Dsansserif_KL ( π2 ∥ πref ) - over→ start_ARG μ end_ARG⋆ + η⋆ ⋅ 1 = 0 , (17) where η⋆⁢(⁢π2−1)=0andμi⋆⁢(π2)i=0,∀i∈[m],formulae-sequencesuperscript⋆superscript1subscript210andformulae-sequencesuperscriptsubscript⋆subscriptsubscript20for-alldelimited-[] η (1 T _2-1)=0 % _i ( _2)_i=0,∀ i∈[m],η⋆ ( 1sansserif_T π2 - 1 ) = 0 and μitalic_i⋆ ( π2 )i = 0 , ∀ i ∈ [ m ] , (18) due to complementary slackness. We will show that this λ⋆superscript⋆λ λ⋆ is the regularization parameter we are looking for. Namely, for the regularized game in Eq. 15 with λ=λ⋆superscript⋆λ=λ λ = λ⋆, we have that (πτ,πτ)subscriptsubscript( _τ, _τ)( πitalic_τ , πitalic_τ ) is a Nash equilibrium. Again, let us first fix π1=πτsubscript1subscript _1= _τπ1 = πitalic_τ and consider the regularized optimization problem for the minimizing player: minπ2⁡πτ⁢M⁢π2−λ⋆⋅D⁢(π2∥πref)s.t.π2≥,⁢π2=1.formulae-sequencesubscriptsubscript2superscriptsubscriptsubscript2⋅superscript⋆subscriptconditionalsubscript2subscriptrefs.t.subscript20superscript1subscript21 _ _2 _τ TM _2-λ % · D_ KL( _2\| _ref) .t. _2% 0,1 T _2=1.minitalic_π start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT πitalic_τsansserif_T M π2 - λ⋆ ⋅ Dsansserif_KL ( π2 ∥ πref ) s.t. π2 ≥ 0 , 1sansserif_T π2 = 1 . (Regularized Minimization) Since πτ⁢M⁢π2superscriptsubscriptsubscript2 _τ TM _2πitalic_τsansserif_T M π2 is convex in π2subscript2 _2π2, Slater’s condition is satisfied for the above problem and implies that the KKT conditions are sufficient for optimality. It is also not hard to see that ℒ⁢(π2,λ⋆,μ→⋆,η⋆)ℒsubscript2superscript⋆superscript→⋆superscript⋆L( _2,λ , μ ,η )L ( π2 , λ⋆ , over→ start_ARG μ end_ARG⋆ , η⋆ ) 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, π2=πτsubscript2subscript _2= _τπ2 = πitalic_τ is a best response strategy to π1=πτsubscript1subscript _1= _τπ1 = πitalic_τ. Since the regularized game is anti-symmetric, the same argument shows that for the maximizing player in the regularized game, π1=πτsubscript1subscript _1= _τπ1 = πitalic_τ is also a best response strategy to π2=πτsubscript2subscript _2= _τπ2 = πitalic_τ. Together, we have that (πτ,πτ)subscriptsubscript( _τ, _τ)( πitalic_τ , πitalic_τ ) is a Nash equilibrium for the regularized game in Eq. 15 with λ=λ⋆superscript⋆λ=λ λ = λ⋆. The proof is complete. ∎ Combining Proposition 13 with Theorem 7, we obtain the following guarantee for the KL-regularized version of NLHF: See 8 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 r be the MLE reward learned from the comparison data, and let πτsubscript _τπitalic_τ be the output of the τ-constrained RLHF method defined in Section 2, i.e., πτ=argmaxπ∈Bτ⁢(πref)x∼π[r⁢(x)],subscriptsubscriptargmaxsubscriptsubscriptrefsubscriptsimilar-to _τ= *argmax_π∈ B_τ( _ref% ) *E_x π [r(x) ],πitalic_τ = argmaxitalic_π ∈ B start_POSTSUBSCRIPT τ ( πref ) end_POSTSUBSCRIPT blackboard_Ex ∼ π [ r ( x ) ] , (19) and let π~λsubscript~ π_λover~ start_ARG π end_ARGλ be the output of the λ-regularized RLHF method, i.e., π~λ=argmaxπ∈Δ⁢(M)x∼π[r⁢(x)]−λ⋅DKL⁢(π∥πref).subscript~subscriptargmaxΔsubscriptsimilar-to⋅subscriptKLconditionalsubscriptref π_λ= *argmax_π∈ (M)% *E_x π [r(x) ]-λ· D_% KL(π\,\|\, _ref).over~ start_ARG π end_ARGλ = argmaxitalic_π ∈ Δ ( M ) blackboard_Ex ∼ π [ r ( x ) ] - λ ⋅ DKL ( π ∥ πref ) . (20) Then, for each λ∈[0,∞]0λ∈[0,∞]λ ∈ [ 0 , ∞ ] with solution π~λsubscript~ π_λover~ start_ARG π end_ARGλ for Eq. 20, we have that π~λsubscript~ π_λover~ start_ARG π end_ARGλ is also an optimal solution to the τ-constrained optimization problem in Eq. 19, where τ=DKL⁢(π~λ∥πref)subscriptKLconditionalsubscript~subscriptrefτ=D_KL( π_λ\,\|\, _ref)τ = DKL ( over~ start_ARG π end_ARGλ ∥ πref ). Conversely, for each τ≥00τ≥ 0τ ≥ 0 with solution πτsubscript _τπitalic_τ for Eq. 19, there exists λ∈[0,∞]0λ∈[0,∞]λ ∈ [ 0 , ∞ ] such that πτsubscript _τπitalic_τ is also an optimal solution to the λ-regularized optimization problem in Eq. 20. Appendix F Other Sampling Models To prove Theorem 9, we first prove the following lemma. We illustrate the constructed sequence of alternatives in Fig. 4. Figure 4: Utilities for first 14 alternatives in the sequences constructed in Lemma 15, for β=55β=5β = 5. Bottom bar chart shows decreasing utility. Numbers between alternative labels at+1→at→subscript1subscripta_t+1→ a_taitalic_t + 1 → aitalic_t give the expected win-rate p⁢(at+1≻at)succeedssubscript1subscriptp(a_t+1 a_t)p ( aitalic_t + 1 ≻ aitalic_t ). Lemma 15. For any β>00β>0β > 0, there is an infinite sequence a1,a2,…subscript1subscript2italic-…a_1,a_2,…a1 , a2 , … of alternatives, and a distribution DD of utility functions over these alternatives such that • ⁢(a1)=1/3subscript113 AvgUtil(a_1)=1/3sansserif_AvgUtil ( a1 ) = 1 / 3, • for all t≥22t≥ 2t ≥ 2, 0<(at)≤(at−1)−23⁢βlog(1+tanh(β/4⋅(at−1))3)<(at−1)0< AvgUtil(a_t)≤ AvgUtil(a_t-1)- 23\,β\,% (1+ (β/4· AvgUtil(a_t-1) )^3 % )< AvgUtil(a_t-1)0 < sansserif_AvgUtil ( aitalic_t ) ≤ sansserif_AvgUtil ( aitalic_t - 1 ) - divide start_ARG 2 end_ARG start_ARG 3 β end_ARG log ( 1 + tanh ( β / 4 ⋅ sansserif_AvgUtil ( aitalic_t - 1 ) )3 ) < sansserif_AvgUtil ( aitalic_t - 1 ), and • for all t≥22t≥ 2t ≥ 2, p⁢(at≻at−1)>1/2succeedssubscriptsubscript112p(a_t a_t-1)>1/2p ( aitalic_t ≻ aitalic_t - 1 ) > 1 / 2. Proof. Our population DD will be a uniform distribution over three utility vectors, u1superscript1u^1u1, u2superscript2u^2u2, and u3superscript3u^3u3. We define the sequence of alternatives and prove the claim by induction over t≥11t≥ 1t ≥ 1. For t=11t=1t = 1, set u1⁢(a1)=u2⁢(a1)=u3⁢(a1)≔1/3superscript1subscript1superscript2subscript1superscript3subscript1≔13u^1(a_1)=u^2(a_1)=u^3(a_1) 1/3u1 ( a1 ) = u2 ( a1 ) = u3 ( a1 ) ≔ 1 / 3, which clearly satisfies the first claim. Now, let t≥22t≥ 2t ≥ 2, and suppose that we have defined the utilities for alternatives a1,…,at−1subscript1…subscript1a_1,…,a_t-1a1 , … , aitalic_t - 1 and established the claims for all t′<tsuperscript′t <t′ < t. We define utilities for atsubscripta_taitalic_t and extend the claims to t. Let uAsuperscriptu^Auitalic_A denote the utility vector among u1,u2,u3superscript1superscript2superscript3u^1,u^2,u^3u1 , u2 , u3 with the highest utility for at−1subscript1a_t-1aitalic_t - 1, and denote the other two utility vectors by uB,uCsuperscriptsuperscriptu^B,u^Cuitalic_B , uitalic_C. For convenience, set Δ≔uA⁢(at−1)⋅β≔Δ⋅superscriptsubscript1 u^A(a_t-1)·βΔ ≔ uitalic_A ( aitalic_t - 1 ) ⋅ β and Δ′≔log⁡((eΔ/2+1)32⁢(eΔ+3))≔superscriptΔ′superscriptΔ2132superscriptΔ3 ( (e /2+1)^32\,(e +% 3) )Δ′ ≔ log ( divide start_ARG ( eroman_Δ / 2 + 1 )3 end_ARG start_ARG 2 ( eroman_Δ + 3 ) end_ARG ). uA⁢(at)≔uA⁢(at−1)−Δ/β=0,uB⁢(at)≔uB⁢(at−1)+Δ′/β,uC⁢(at)≔uC⁢(at−1)+Δ′/β.formulae-sequence≔superscriptsubscriptsuperscriptsubscript1Δ0formulae-sequence≔superscriptsubscriptsuperscriptsubscript1superscriptΔ′≔superscriptsubscriptsuperscriptsubscript1superscriptΔ′u^A(a_t) u^A(a_t-1)- /β=0, u^B(a_t)% u^B(a_t-1)+ /β, u^C(a_t)% u^C(a_t-1)+ /β.uitalic_A ( aitalic_t ) ≔ uitalic_A ( aitalic_t - 1 ) - Δ / β = 0 , uitalic_B ( aitalic_t ) ≔ uitalic_B ( aitalic_t - 1 ) + Δ′ / β , uitalic_C ( aitalic_t ) ≔ uitalic_C ( aitalic_t - 1 ) + Δ′ / β . It will be useful to derive an alternative expression for Δ′: Δ′ =log⁡((eΔ/2+1)32⁢(eΔ+3))=log⁡(eΔ/2⁢(eΔ/2+1)32⁢eΔ/2⁢(eΔ+3))absentsuperscriptsuperscriptΔ2132superscriptΔ3superscriptΔ2superscriptsuperscriptΔ2132superscriptΔ2superscriptΔ3 = ( (e /2+1)^32\,(e +3) )=% (e /2\, (e /2+1)^32\,e /2\,(e^% +3) )= log ( divide start_ARG ( eroman_Δ / 2 + 1 )3 end_ARG start_ARG 2 ( eroman_Δ + 3 ) end_ARG ) = log ( eroman_Δ / 2 divide start_ARG ( eroman_Δ / 2 + 1 )3 end_ARG start_ARG 2 eroman_Δ / 2 ( eroman_Δ + 3 ) end_ARG ) =Δ2−log⁡2⁢eΔ/2⁢(eΔ+3)(eΔ/2+1)3=Δ2−log⁡(eΔ/2+1)3+(eΔ/2−1)3(eΔ/2+1)3absentΔ22superscriptΔ2superscriptΔ3superscriptsuperscriptΔ213Δ2superscriptsuperscriptΔ213superscriptsuperscriptΔ213superscriptsuperscriptΔ213 = 2- 2\,e /2\,(e +3)(e^% /2+1)^3= 2- (e /2+1)^3+(e /2% -1)^3(e /2+1)^3= divide start_ARG Δ end_ARG start_ARG 2 end_ARG - log divide start_ARG 2 eroman_Δ / 2 ( eroman_Δ + 3 ) end_ARG start_ARG ( eroman_Δ / 2 + 1 )3 end_ARG = divide start_ARG Δ end_ARG start_ARG 2 end_ARG - log divide start_ARG ( eroman_Δ / 2 + 1 )3 + ( eroman_Δ / 2 - 1 )3 end_ARG start_ARG ( eroman_Δ / 2 + 1 )3 end_ARG =Δ2−log(1+(eΔ/2−1eΔ/2+1)3)=Δ2−log(1+tanh(Δ/4)3). = 2- (1+ ( e /2-1e^% /2+1 )^3 )= 2- (1+ ( /4)^3% ).= divide start_ARG Δ end_ARG start_ARG 2 end_ARG - log ( 1 + ( divide start_ARG eroman_Δ / 2 - 1 end_ARG start_ARG eroman_Δ / 2 + 1 end_ARG )3 ) = divide start_ARG Δ end_ARG start_ARG 2 end_ARG - log ( 1 + tanh ( Δ / 4 )3 ) . Since the value 1+(eΔ/2−1eΔ/2+1)31superscriptsuperscriptΔ21superscriptΔ2131+( e /2-1e /2+1)^31 + ( divide start_ARG eroman_Δ / 2 - 1 end_ARG start_ARG eroman_Δ / 2 + 1 end_ARG )3 in the logarithm is greater than 1, we know that Δ′<Δ/2superscriptΔ′Δ2 < /2Δ′ < Δ / 2. Since ⁢(at−1)>0subscript10 AvgUtil(a_t-1)>0sansserif_AvgUtil ( aitalic_t - 1 ) > 0 by the induction hypothesis, it must hold that Δ>0Δ0 >0Δ > 0, and, by expanding, that Δ′=log⁡(eΔ/2+1)32⁢(eΔ+3)=log⁡3⁢eΔ+1+12⋅(eΔ/2−1)3eΔ+3>log⁡3⁢eΔ+1eΔ+3.superscriptΔ′superscriptΔ2132superscriptΔ33superscriptΔ1⋅12superscriptsuperscriptΔ213superscriptΔ33superscriptΔ1superscriptΔ3 = (e /2+1)^32\,(e +3)= 3% \,e +1+ 12·(e /2-1)^3e +3> % 3\,e +1e +3.Δ′ = log divide start_ARG ( eroman_Δ / 2 + 1 )3 end_ARG start_ARG 2 ( eroman_Δ + 3 ) end_ARG = log divide start_ARG 3 eroman_Δ + 1 + divide start_ARG 1 end_ARG start_ARG 2 end_ARG ⋅ ( eroman_Δ / 2 - 1 )3 end_ARG start_ARG eroman_Δ + 3 end_ARG > log divide start_ARG 3 eroman_Δ + 1 end_ARG start_ARG eroman_Δ + 3 end_ARG . (21) Since log⁡3⁢eΔ+1eΔ+3>log⁡eΔ+3eΔ+3=03superscriptΔ1superscriptΔ3superscriptΔ3superscriptΔ30 3\,e +1e +3> e +3e +3=0log divide start_ARG 3 eroman_Δ + 1 end_ARG start_ARG eroman_Δ + 3 end_ARG > log divide start_ARG eroman_Δ + 3 end_ARG start_ARG eroman_Δ + 3 end_ARG = 0, it holds that Δ′>0superscriptΔ′0 >0Δ′ > 0 and that ⁢(at)>0subscript0 AvgUtil(a_t)>0sansserif_AvgUtil ( aitalic_t ) > 0. We first must show that we have not set uB⁢(at)superscriptsubscriptu^B(a_t)uitalic_B ( aitalic_t ) and uC⁢(at)superscriptsubscriptu^C(a_t)uitalic_C ( aitalic_t ) greater than 1. Since, by the induction hypothesis, 13⁢(uA⁢(at−1)+uB⁢(at−1)+uC⁢(at−1))=⁢(at−1)≤⁢(at−2)≤⋯≤⁢(a1)=1/313superscriptsubscript1superscriptsubscript1superscriptsubscript1subscript1subscript2⋯subscript113 13(u^A(a_t-1)+u^B(a_t-1)+u^C(a_t-1))= AvgUtil(a_% t-1)≤ AvgUtil(a_t-2)≤·s≤ AvgUtil(a_1)=1/3divide start_ARG 1 end_ARG start_ARG 3 end_ARG ( uitalic_A ( aitalic_t - 1 ) + uitalic_B ( aitalic_t - 1 ) + uitalic_C ( aitalic_t - 1 ) ) = sansserif_AvgUtil ( aitalic_t - 1 ) ≤ sansserif_AvgUtil ( aitalic_t - 2 ) ≤ ⋯ ≤ sansserif_AvgUtil ( a1 ) = 1 / 3, it must hold that uA⁢(at−1)+uB⁢(at−1)+uC⁢(at−1)≤1superscriptsubscript1superscriptsubscript1superscriptsubscript11u^A(a_t-1)+u^B(a_t-1)+u^C(a_t-1)≤ 1uitalic_A ( aitalic_t - 1 ) + uitalic_B ( aitalic_t - 1 ) + uitalic_C ( aitalic_t - 1 ) ≤ 1, which by the choice of uAsuperscriptu^Auitalic_A implies that uB⁢(at−1),uC⁢(at−1)superscriptsubscript1superscriptsubscript1u^B(a_t-1),u^C(a_t-1)uitalic_B ( aitalic_t - 1 ) , uitalic_C ( aitalic_t - 1 ) are at most 1/2121/21 / 2. Since Δ′<Δ/2=uA⁢(at−1)⋅β/2≤β/2superscriptΔ′Δ2⋅superscriptsubscript122 < /2=u^A(a_t-1)·β/2≤β/2Δ′ < Δ / 2 = uitalic_A ( aitalic_t - 1 ) ⋅ β / 2 ≤ β / 2, uB⁢(at)=uB⁢(at−1)+Δ′/β≤1/2+1/2=1superscriptsubscriptsuperscriptsubscript1superscriptΔ′12121u^B(a_t)=u^B(a_t-1)+ /β≤ 1/2+1/2=1uitalic_B ( aitalic_t ) = uitalic_B ( aitalic_t - 1 ) + Δ′ / β ≤ 1 / 2 + 1 / 2 = 1, this holds for uBsuperscriptu^Buitalic_B, and analogously for uCsuperscriptu^Cuitalic_C. Next, we show the claimed reduction in average utility using our alternative expression for Δ′. ⁢(at)subscript AvgUtil(a_t)sansserif_AvgUtil ( aitalic_t ) =13⋅(uA⁢(at)+uB⁢(at)+uC⁢(at))=13⋅(uA⁢(at−1)+uB⁢(at−1)+uC⁢(at−1)−Δ−2⁢Δ′β)absent⋅13superscriptsubscriptsuperscriptsubscriptsuperscriptsubscript⋅13superscriptsubscript1superscriptsubscript1superscriptsubscript1Δ2superscriptΔ′ = 13· (u^A(a_t)+u^B(a_t)+u^C(a_t)% )= 13· (u^A(a_t-1)+u^B(a_t-1)+u^C(a_t-1)-% -2\, β )= divide start_ARG 1 end_ARG start_ARG 3 end_ARG ⋅ ( uitalic_A ( aitalic_t ) + uitalic_B ( aitalic_t ) + uitalic_C ( aitalic_t ) ) = divide start_ARG 1 end_ARG start_ARG 3 end_ARG ⋅ ( uitalic_A ( aitalic_t - 1 ) + uitalic_B ( aitalic_t - 1 ) + uitalic_C ( aitalic_t - 1 ) - divide start_ARG Δ - 2 Δ′ end_ARG start_ARG β end_ARG ) =(at−1)−Δ−2⁢Δ′3⁢β=(at−1)−23⁢βlog(1+tanh(Δ/4)3). = AvgUtil(a_t-1)- -2\, 3\,% β= AvgUtil(a_t-1)- 23\,β\, (1+ ( % /4)^3 ).= sansserif_AvgUtil ( aitalic_t - 1 ) - divide start_ARG Δ - 2 Δ′ end_ARG start_ARG 3 β end_ARG = sansserif_AvgUtil ( aitalic_t - 1 ) - divide start_ARG 2 end_ARG start_ARG 3 β end_ARG log ( 1 + tanh ( Δ / 4 )3 ) . By our choice of uAsuperscriptu^Auitalic_A and averaging, it holds that uA⁢(at−1)≥⁢(at−1)superscriptsubscript1subscript1u^A(a_t-1)≥ AvgUtil(a_t-1)uitalic_A ( aitalic_t - 1 ) ≥ sansserif_AvgUtil ( aitalic_t - 1 ) and hence that Δ≥β⋅⁢(at−1)Δ⋅subscript1 ≥β· AvgUtil(a_t-1)Δ ≥ β ⋅ sansserif_AvgUtil ( aitalic_t - 1 ). Since the bound on ⁢(at)subscript AvgUtil(a_t)sansserif_AvgUtil ( aitalic_t ) above is monotone nonincreasing in Δ Δ, we obtain our claim that (at)≤(at−1)−23⁢βlog(1+tanh(β/4⋅(at−1))3). AvgUtil(a_t)≤ AvgUtil(a_t-1)- 23\,β\, % (1+ (β/4· AvgUtil(a_t-1) )^3 ).sansserif_AvgUtil ( aitalic_t ) ≤ sansserif_AvgUtil ( aitalic_t - 1 ) - divide start_ARG 2 end_ARG start_ARG 3 β end_ARG log ( 1 + tanh ( β / 4 ⋅ sansserif_AvgUtil ( aitalic_t - 1 ) )3 ) . Finally, it remains to show that p⁢(at≻at−1)>1/2succeedssubscriptsubscript112p(a_t a_t-1)>1/2p ( aitalic_t ≻ aitalic_t - 1 ) > 1 / 2. Since p⁢(at≻at−1)succeedssubscriptsubscript1 p(a_t a_t-1)p ( aitalic_t ≻ aitalic_t - 1 ) =σ⁢(−Δ)+2⁢σ⁢(Δ′)3=12+(σ⁢(−Δ)−1/2)+2⁢(σ⁢(Δ′)−1/2)3absentΔ2superscriptΔ′312Δ122superscriptΔ′123 = σ(- )+2\,σ( )3= 12% + (σ(- )-1/2)+2\,(σ( )-1/2)3= divide start_ARG σ ( - Δ ) + 2 σ ( Δ′ ) end_ARG start_ARG 3 end_ARG = divide start_ARG 1 end_ARG start_ARG 2 end_ARG + divide start_ARG ( σ ( - Δ ) - 1 / 2 ) + 2 ( σ ( Δ′ ) - 1 / 2 ) end_ARG start_ARG 3 end_ARG =12+(1/2−σ⁢(Δ))+2⁢(σ⁢(Δ′)−1/2)3,absent1212Δ2superscriptΔ′123 = 12+ (1/2-σ( ))+2\,(σ( % )-1/2)3,= divide start_ARG 1 end_ARG start_ARG 2 end_ARG + divide start_ARG ( 1 / 2 - σ ( Δ ) ) + 2 ( σ ( Δ′ ) - 1 / 2 ) end_ARG start_ARG 3 end_ARG , it suffices to show that 2⁢(σ⁢(Δ′)−1/2)>σ⁢(Δ)−1/22superscriptΔ′12Δ122\,(σ( )-1/2)>σ( )-1/22 ( σ ( Δ′ ) - 1 / 2 ) > σ ( Δ ) - 1 / 2. Observing that σ⁢(x)−1/2=12⋅1−e−x1+e−x12⋅121superscript1superscriptσ(x)-1/2= 12· 1-e^-x1+e^-xσ ( x ) - 1 / 2 = divide start_ARG 1 end_ARG start_ARG 2 end_ARG ⋅ divide start_ARG 1 - e- x end_ARG start_ARG 1 + e- x end_ARG and applying Eq. 21, we bound 2⁢(σ⁢(Δ′)−12)2superscriptΔ′12 2\, (σ( )- 12 )2 ( σ ( Δ′ ) - divide start_ARG 1 end_ARG start_ARG 2 end_ARG ) >2⁢(σ⁢(log⁡(3Δ+1eΔ+3))−12)=1−eΔ+33⁢eΔ+11+eΔ+33⁢eΔ+1=2⁢eΔ−23⁢eΔ+14⁢eΔ+43⁢eΔ+1=24⋅eΔ−1eΔ+1absent2superscript3Δ1superscriptΔ3121superscriptΔ33superscriptΔ11superscriptΔ33superscriptΔ12superscriptΔ23superscriptΔ14superscriptΔ43superscriptΔ1⋅24superscriptΔ1superscriptΔ1 >2\, (σ ( ( 3 +1e +3)% )- 12 )= 1- e +33\,e +11+% e +33\,e +1= 2\,e -23\,e^% +1 4\,e +43\,e +1= 24· e^% -1e +1> 2 ( σ ( log ( divide start_ARG 3Δ + 1 end_ARG start_ARG eroman_Δ + 3 end_ARG ) ) - divide start_ARG 1 end_ARG start_ARG 2 end_ARG ) = divide start_ARG 1 - divide start_ARG eroman_Δ + 3 end_ARG start_ARG 3 eroman_Δ + 1 end_ARG end_ARG start_ARG 1 + divide start_ARG eroman_Δ + 3 end_ARG start_ARG 3 eroman_Δ + 1 end_ARG end_ARG = divide start_ARG divide start_ARG 2 eroman_Δ - 2 end_ARG start_ARG 3 eroman_Δ + 1 end_ARG end_ARG start_ARG divide start_ARG 4 eroman_Δ + 4 end_ARG start_ARG 3 eroman_Δ + 1 end_ARG end_ARG = divide start_ARG 2 end_ARG start_ARG 4 end_ARG ⋅ divide start_ARG eroman_Δ - 1 end_ARG start_ARG eroman_Δ + 1 end_ARG =12⋅1−e−Δ1+e−Δ=σ⁢(Δ)−12,absent⋅121superscriptΔ1superscriptΔ12 = 12· 1-e^- 1+e^- =σ(% )- 12,= divide start_ARG 1 end_ARG start_ARG 2 end_ARG ⋅ divide start_ARG 1 - e- Δ end_ARG start_ARG 1 + e- Δ end_ARG = σ ( Δ ) - divide start_ARG 1 end_ARG start_ARG 2 end_ARG , which establishes our claim. ∎ See 9 Proof. We construct our sequence of instances by taking increasingly long prefixes of the sequence in Lemma 15, i.e., by considering the alternatives a1,…,amsubscript1…subscripta_1,…,a_ma1 , … , aitalic_m for increasing m. Rescaling by some constants, we can define the MLE rewards in RLHF as r=argmaxr∈ℝm⁢∑x,y∈(A2)#⁢(x≻y)n⁢d⁢log⁡(σ⁢(r⁢(x)−r⁢(y)))+#⁢(y≻x)n⁢d⁢log⁡(σ⁢(r⁢(y)−r⁢(x))).subscriptargmaxsuperscriptℝsubscriptbinomial2#succeeds#succeedsr= *argmax_r ^m _\x,y\∈ A2% \#(x y)n\,d (σ(r(x)-r(y)) )+ \#(y x% )n\,d (σ(r(y)-r(x)) ).r = argmaxitalic_r ∈ blackboard_Rm ∑ x , y ∈ ( FRACOP start_ARG A end_ARG start_ARG 2 end_ARG ) divide start_ARG # ( x ≻ y ) end_ARG start_ARG n d end_ARG log ( σ ( r ( x ) - r ( y ) ) ) + divide start_ARG # ( y ≻ x ) end_ARG start_ARG n d end_ARG log ( σ ( r ( y ) - r ( x ) ) ) . Following Siththaranjan et al. [2023], we apply the first-order optimality conditions to obtain that, for each alternative x, ∑y≠x#⁢(x≻y)n⁢d=∑y≠x#⁢(x≻y)+#⁢(y≻x)n⁢d⋅σ⁢(r⁢(x)−r⁢(y)).subscript#succeedssubscript⋅#succeeds#succeeds _y≠ x \#(x y)n\,d= _y≠ x \#(x y)+\#(y% x)n\,d·σ(r(x)-r(y)).∑y ≠ x divide start_ARG # ( x ≻ y ) end_ARG start_ARG n d end_ARG = ∑y ≠ x divide start_ARG # ( x ≻ y ) + # ( y ≻ x ) end_ARG start_ARG n d end_ARG ⋅ σ ( r ( x ) - r ( y ) ) . By the strong law of large numbers, as the number n of samples goes to infinity (regardless of d), the sample fraction #⁢(x≻y)n⁢d#succeeds \#(x y)n\,ddivide start_ARG # ( x ≻ y ) end_ARG start_ARG n d end_ARG converges almost surely to its expected value ν⁢(x,y)⋅p⁢(x≻y)⋅succeedsν(\x,y\)· p(x y)ν ( x , y ) ⋅ p ( x ≻ y ). Hence, as n→∞→n→∞n → ∞, the rewards (a random variable depending on the random pairwise comparisons) will satisfy that ∑y≠xν⁢(x,y)⋅σ⁢(r⁢(x)−r⁢(y))⟶a.s.∑y≠xν⁢(x,y)⋅p⁢(x≻y).superscript⟶a.s.subscript⋅subscript⋅succeeds _y≠ xν(\x,y\)·σ(r(x)-r(y)) % .s. _y≠ xν(\x,y\)· p(x y).∑y ≠ x ν ( x , y ) ⋅ σ ( r ( x ) - r ( y ) ) start_RELOP SUPERSCRIPTOP start_ARG ⟶ end_ARG start_ARG a.s. end_ARG end_RELOP ∑y ≠ x ν ( x , y ) ⋅ p ( x ≻ y ) . (22) Consider a distribution ν over pairs of alternatives that assigns each pair of adjacent alternatives at,at+1subscriptsubscript1\a_t,a_t+1\ aitalic_t , aitalic_t + 1 a probability of 1−ϵm−11italic-ϵ1 1-εm-1divide start_ARG 1 - ϵ end_ARG start_ARG m - 1 end_ARG of being drawn for comparison, and all other pairs a probability of ϵ(m2)−(m−1)italic-ϵbinomial21 ε m2-(m-1)divide start_ARG ϵ end_ARG start_ARG ( FRACOP start_ARG m end_ARG start_ARG 2 end_ARG ) - ( m - 1 ) end_ARG, where ϵ>0italic-ϵ0ε>0ϵ > 0 is a small value, dependent on the current m, to be determined in the following. Applying Eq. 22 to x=amsubscriptx=a_mx = aitalic_m, we obtain that 1−ϵm−1⁢σ⁢(r⁢(am)−r⁢(am−1))+O⁢(ϵ)1italic-ϵ1subscriptsubscript1italic-ϵ 1-εm-1σ(r(a_m)-r(a_m-1))+O(ε)divide start_ARG 1 - ϵ end_ARG start_ARG m - 1 end_ARG σ ( r ( aitalic_m ) - r ( aitalic_m - 1 ) ) + O ( ϵ ) converges almost surely to 1−ϵm−1⋅p⁢(am≻am−1)+O⁢(ϵ)⋅1italic-ϵ1succeedssubscriptsubscript1italic-ϵ 1-εm-1· p(a_m a_m-1)+O(ε)divide start_ARG 1 - ϵ end_ARG start_ARG m - 1 end_ARG ⋅ p ( aitalic_m ≻ aitalic_m - 1 ) + O ( ϵ ). Since Lemma 15 guarantees that p⁢(am≻am−1)>1/2succeedssubscriptsubscript112p(a_m a_m-1)>1/2p ( aitalic_m ≻ aitalic_m - 1 ) > 1 / 2, for small enough ϵitalic-ϵεϵ, it will hold almost surely that σ⁢(r⁢(am)−r⁢(am−1))>1/2subscriptsubscript112σ(r(a_m)-r(a_m-1))>1/2σ ( r ( aitalic_m ) - r ( aitalic_m - 1 ) ) > 1 / 2, i.e., that r⁢(am)>r⁢(am−1)subscriptsubscript1r(a_m)>r(a_m-1)r ( aitalic_m ) > r ( aitalic_m - 1 ). Next, we apply Eq. 22 to x=am−1subscript1x=a_m-1x = aitalic_m - 1, to obtain that 1−ϵm−1⁢(σ⁢(r⁢(am−1)−r⁢(am))+σ⁢(r⁢(am−1)−r⁢(am−2)))+O⁢(ϵ)1italic-ϵ1subscript1subscriptsubscript1subscript2italic-ϵ 1-εm-1(σ(r(a_m-1)-r(a_m))+σ(r(a_m-1)-r(a_m-2% )))+O(ε)divide start_ARG 1 - ϵ end_ARG start_ARG m - 1 end_ARG ( σ ( r ( aitalic_m - 1 ) - r ( aitalic_m ) ) + σ ( r ( aitalic_m - 1 ) - r ( aitalic_m - 2 ) ) ) + O ( ϵ ) converges almost surely to 1−ϵm−1⋅(p⁢(am−1≻am)+p⁢(am−1≻am−2))+O⁢(ϵ)⋅1italic-ϵ1succeedssubscript1subscriptsucceedssubscript1subscript2italic-ϵ 1-εm-1·(p(a_m-1 a_m)+p(a_m-1 a_m-2))+O(ε)divide start_ARG 1 - ϵ end_ARG start_ARG m - 1 end_ARG ⋅ ( p ( aitalic_m - 1 ≻ aitalic_m ) + p ( aitalic_m - 1 ≻ aitalic_m - 2 ) ) + O ( ϵ ). Having established above that, for small enough ϵitalic-ϵεϵ, we can make σ⁢(r⁢(am−1)−r⁢(am))=1−σ⁢(r⁢(am)−r⁢(am−1))subscript1subscript1subscriptsubscript1σ(r(a_m-1)-r(a_m))=1-σ(r(a_m)-r(a_m-1))σ ( r ( aitalic_m - 1 ) - r ( aitalic_m ) ) = 1 - σ ( r ( aitalic_m ) - r ( aitalic_m - 1 ) ) arbitrarily close to p⁢(am−1≻am)=1−p⁢(am≻am−1)succeedssubscript1subscript1succeedssubscriptsubscript1p(a_m-1 a_m)=1-p(a_m a_m-1)p ( aitalic_m - 1 ≻ aitalic_m ) = 1 - p ( aitalic_m ≻ aitalic_m - 1 ), we see that σ⁢(r⁢(am−1)−r⁢(am−2))subscript1subscript2σ(r(a_m-1)-r(a_m-2))σ ( r ( aitalic_m - 1 ) - r ( aitalic_m - 2 ) ) must become arbitrarily close to p⁢(am−1≻am−2)>1/2succeedssubscript1subscript212p(a_m-1 a_m-2)>1/2p ( aitalic_m - 1 ≻ aitalic_m - 2 ) > 1 / 2. Continuing this argument for x=am−2,am−3,…,a1subscript2subscript3…subscript1x=a_m-2,a_m-3,…,a_1x = aitalic_m - 2 , aitalic_m - 3 , … , a1, we obtain that, for small enough ϵitalic-ϵεϵ, the rewards will be ordered as r⁢(a1)<r⁢(a2)<⋯<r⁢(am)subscript1subscript2⋯subscriptr(a_1)<r(a_2)<·s<r(a_m)r ( a1 ) < r ( a2 ) < ⋯ < r ( aitalic_m ) almost surely. Set ϵitalic-ϵεϵ (for this specific m) so that this is the case. We set the KL constraint large enough that all policies are possible; say, by choosing the reference policy to be uniform and setting τ=log⁡mτ= mτ = log m.161616This means that this lower bound fits into the social choice subsetting. Note that the theorem does not apply to Borda count (which is not defined for a general distribution ν), but to RLHF considered as a voting rule. Then, the reward-maximizing policy clearly puts all probability mass on the alternative amsubscripta_maitalic_m with maximal reward, obtaining a distortion of ⁢(a1)⁢(am)=1/3⁢(am)subscript1subscript13subscript AvgUtil(a_1) AvgUtil(a_m)= 1/3 % AvgUtil(a_m)divide start_ARG sansserif_AvgUtil ( a1 ) end_ARG start_ARG sansserif_AvgUtil ( aitalic_m ) end_ARG = divide start_ARG 1 / 3 end_ARG start_ARG sansserif_AvgUtil ( aitalic_m ) end_ARG. We have now defined a sequence of instances, whose distortion grows as 1/3⁢(am)13subscript 1/3 AvgUtil(a_m)divide start_ARG 1 / 3 end_ARG start_ARG sansserif_AvgUtil ( aitalic_m ) end_ARG as m→∞→m→∞m → ∞. To show that distortion is not bounded in β, it remains to show that ⁢(am)→0→subscript0 AvgUtil(a_m)→ 0sansserif_AvgUtil ( aitalic_m ) → 0. The lemma already tells us that ⁢(at)subscript AvgUtil(a_t)sansserif_AvgUtil ( aitalic_t ) (for t=1,2,…12…t=1,2,…t = 1 , 2 , …) is a monotonically decreasing sequence. Since the average utility is nonnegative, the sequence is bounded from below and thus convergent, which also implies that the sequence of differences ⁢(at−1)−⁢(at)subscript1subscript AvgUtil(a_t-1)- AvgUtil(a_t)sansserif_AvgUtil ( aitalic_t - 1 ) - sansserif_AvgUtil ( aitalic_t ) must converge to 0. Since the bound 23⁢βlog(1+tanh(β/4(at−1))3) 23β (1+ (β/4 AvgUtil(a_t-1))^3)divide start_ARG 2 end_ARG start_ARG 3 β end_ARG log ( 1 + tanh ( β / 4 sansserif_AvgUtil ( aitalic_t - 1 ) )3 ) is sandwiched between these differences and 0, it must also converge to 0. Since it is continuous in ⁢(at−1)subscript1 AvgUtil(a_t-1)sansserif_AvgUtil ( aitalic_t - 1 ) and positive for all positive values of ⁢(at−1)subscript1 AvgUtil(a_t-1)sansserif_AvgUtil ( aitalic_t - 1 ), this implies that ⁢(at−1)subscript1 AvgUtil(a_t-1)sansserif_AvgUtil ( aitalic_t - 1 ) must converge to 0. This shows that ⁢(am)→0→subscript0 AvgUtil(a_m)→ 0sansserif_AvgUtil ( aitalic_m ) → 0 for large m, and that the distortion grows unboundedly large as m increases, which concludes our proof. ∎

Instant research discovery