Axioms for AI Alignment from Human Feedback
Authors: Luise Ge
Daniel Halpern
Evi Micha
Ariel D. Procaccia
Itai Shapira
Yevgeniy Vorobeychik
Junlin Wu
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Social choice
reinforcement learning from human feedback
AI alignment
Primary area: algorithmic_game_theory

Abstract: In the context of reinforcement learning from human feedback (RLHF), the reward function is generally derived from maximum likelihood estimation of a random utility model based on pairwise comparisons made by humans. The problem of learning a reward function is one of preference aggregation that, we argue, largely falls within the scope of social choice theory. From this perspective, we can evaluate different aggregation methods via established axioms, examining whether these methods meet or fail well-known standards. We demonstrate that both the Bradley-Terry-Luce Model and its broad generalizations fail to meet basic axioms. In response, we develop novel rules for learning reward functions with strong axiomatic guarantees. A key innovation from the standpoint of social choice is that our problem has a *linear* structure, which greatly restricts the space of feasible rules and leads to a new paradigm that we call *linear social choice*.

Axioms for AI Alignment from Human Feedback
Luise Ge Washington University St. Louis e.lusseuustlledu
Daniel Halpern Harvard University
Evi Micha Harvard University
dhalpernng harvard. edu
emi emi chicsesss..... harvard.edu
Ariel D. Procaccia
Itai Shapira
Harvard University arielprodg.harvee harvard.
Harvard University
itaishapiraßg harvard.edu
Yevgeniy Vorobeychik Washington University St. Louis
Junlin Wu
Washington University in St. Louis junlin, su@vustl.edi
yvorobeychikewistl..em
Abstract
In the context of reinforcement learning from human feedback (RLHF). the reward function is generally derived from maximum likelihood estimation of random utility model based on pairwise comparisons made by humans. The problem of learning a reward function one of preference aggregation that, we argue, largely falls within the scope of social choice theory. From this perspective, we can eval- uate different aggregation methods via established axioms, examining whether these methods meet or fail well-known standards. We demonstrate that both the Bradley-Terry- Model and its broad generalizations fail to meet basic axioms. In response, we develop novel rules for learning reward functions with strong ax- iomatic guarantees. key innovation from the standpoint of social choice is that problem has linear structure, which greatly restricts the space of feasible rules and leads to a new paradigm that we call linear social choice.
Introduction
The alignment of AI models with human values is widely recognized as crucial task. A promi- nent method for this task, reinforcement learning with human feedback (RLHF), has been used in different applications, such as robotics [4, 17] and recommendations [28, 1]. Recently, RLHF has attracted significant attention as tool fine-tuning large language models (LLMs) [22, 32, 26). A typical implementation of RLHF involves learning reward model using pre-trained LLM, which then utilized fine-tune an existing L.M. During the learning step, human feedback is provided in the form of ordinal comparisons, and reward function is learned from these. The most com- mon learning method assumes an underlying random utility model such as the Bradley-Terry-Lun (BTL) model [5, 22, 8] and computes reward function that corresponds to maximum likelihood estimator for the observed comparisons.
Is this the "right" way of aggregating individual preferences towards socially desirable reward function? To answer this question, we draw on social choice theory, a field that studies collective decision making through mathematical lens [6]. The maximum likelihood estimation approach in line with a well-established body of work that assumes that different human participants have preferences stemming from noisy estimation of common ground truth, and the goal is to learn this ground truth as accurately as possible [29]. But this is not the case when it comes to questions of AI
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

alignment, where individuals can have legitimate differences of opinion rooted in different values or priorities.
We argue that when preferences are truly heterogeneous, the axiomatic approach- which rose to prominence in social choice with the work of Arrow [2] [2]-may be more suitable. This approach analyzes the desirability of aggregation methods by their satisfaction of certain axioms that capture notions of consensus, fairness, and economic efficiency. Specifically, iomatic properties of aggregation methods that take ordinal preferences as input and output a reward function. We address the following two research questions: What axioms are satisfied by aggrega- tion methods used by existing RLHF algorithms? And are there alternative aggregation methods that offer stronger axiomatic guarantees?
are interested in the ax-
1.1 Our Approach
In social choice theory, axioms are typically defined for rules that map rankings over candidates to single winner (social choice functions) or a ranking of the candidates (social welfare functions). By contrast, we are interested in rules that assign a reward to each candidate. This gap is easy bridge, though: we simply consider a ranking of the candidates by in descending reward order.
A much more significant gap is that in classical social choice, all relevant candidates appear in the input preferences, whereas in our setting (where candidates correspond, e.g., to prompts and their responses), we are only given preferences their feature, and we need to generalize from this information. In practice, this entails using cestritedd-commonlyy parametric- class of reward models which map candidate features to real-valued rewards, and which we fit to existing data.
relatively small set of candidates identified by
Specifically, we assume that linear reward function defined by parameter vector determines the reward of each candidate by computing the inner product the parameter vector and the feature vector of the candidate; these modeling choices are consistent with prior and concurrent work [31, 30, 15] and aim to capture the practice of RLHE Each human participant (henceforth referred to a voter) is associated with a parameter vector, which is unknown to us and is used to specify ordinal preferences over the candidates. Our task is to design linear rank aggregation rules, which aggregate rankings induced by these individual linear functions into collective ranking that is also induced by a linear function; this is a new paradigm in social choice, for which we coin the term linear social choice.
To evaluate linear rank aggregation rules, we adapt fundamental axioms from social choice the- ory [6]. The first is Pareto optimality (PO), which requires that if candidate is ranked above candidate in every input ranking, then the resulting ranking should rank a above This is seen as a basic requirement and is satisfied by every standard voting method in the classical setting.
The second axiom is pairwise majority consistency (PMC): If there exists a reward function that generates a ranking where, for each pair of candidates. a majority of voters agree with the ranking, then the resulting ranking should match that ranking. This axiom is an extension of Condorcet consistency to rankings, and is satisfied by some, but not all, standard voting methods in the classical setting.
1.2 Our Results
We start by examining, in Section 3.1, a family of loss-based nules that finds ranking induced by a parameter vector that optimizes a measure of loss; this measure increases for every disagreement with voter on a pair of alternatives, where the larger the difference in rewards, the larger the penalty. Crucially, by plugging in binary cross-entropy loss we can recover the BTL model. Our first main result that whenever the loss function is weakly convex and nondecreasing, or strictly convex- conditions satisfied by binary cross-entropy loss, as well as, e.g., exponential and hinge loss the
We can represent the reward model as embedding layer ((x) which is then aggregated linearly to compute the final reward. If we fix the embedding function and treat its output the feature representation of the outcomes, such as prompt-response pairs, the resulting reward model linear in o(x); see, e.g. [31]. 'I practice, typical RLHF datasets consist of pairwise comparisons, not complete rankings. Assuming rankings as input makes exposition cleaner, and is fundamental limitation, we discuss in Section 5.

---

corresponding rule fails both PMC and PO. This result suggests that the prevailing practice of RLHF flawed from an axiomatic viewpoint.
In Section 3.2, we take a first step towards addressing this shortcoming. We modify the loss-based formulation to focus majority preferences rather than individual preferences. This modification defines a family of rules that are PMC, but we show that all of them fail PO by establishing an even stronger impossibility result: In stark contrast the classical setting, any linear rank aggregation rule that depends only on majority preferences must fail PO.
In order achieve both PO and PMC, design (in Section 4) linear rank aggregation rule that call Leximax Copeland subject to PO. Not only does it satisfy our two main axioms, also satisfies two additional ones, majority consistency and winner monotonicity.
To summarize, while widely applied rules fail to meet basic axioms, there are alternative meth- ods that are desirable from this viewpoint. Our approach, therefore, provides discriminative lens through which to evaluate RLHF methods and Al alignment methods more broadly.
1.3 Related Work
During the eight months in which we have actively worked on this project (from September 2023 until May 2024) and especially in the first few months of 2024 slew of independent, concur- rent papers seeking to build bridges between social choice and RLHF have become publicly avail- able [10, 12, 19, 30, 23, 7, 15, 27, 25]; this surge of interest points, in our view, to the importance of the agenda.
Three of those papers are position papers that conceptually support our work in that they discuss the possibility of applying an axiomatic approach to RLHF [10, 12, 19], although they do not provide any technical results. By contrast, existing technical papers on RLHF do not take an axiomatic approach. Of the concurrent technical papers, the one that is most closely related to ours is that of Siththaranjan et al. [25]. They show, among other results, that the ranking induced by the reward function that the MLE estimator of the Bradley-Tere Terry-Luce Model returns follows the famous Borda count rule when unrestricted reward functions allowed. In the classical setting, Borda count has strong axiomatic guarantees, including PO (but not PMC). However, it cannot be realized as a linear rank aggregation rule, and it is arguably impractical for RLHE.
Our work builds on an earlier study by Noothigattu et al. [21], which explores the axiomatic prop- erties of reward functions defined MLE estimators of underlying random utility models. The key difference is that their approach allows for general reward functions, not just linear ones, and they do not consider features at all. Unlike our findings, they show that the BTL model satisfies Pareto Optimality under these conditions. Additionally, they find that pairwise majority consistency is violated even without assuming linearity. However, their results strongly depend on varying the number of comparisons across different pairs candidates. By contrast, our findings demonstrate that pairwise majority consistency is violated even when the number of comparisons is equal across all pairs of candidates.
The Linear Social Choice Model
Let C' be set of m distinct prompt/repoonses, referred to as candidates, and let = (1,.... n be a set of n human participants, known as voters. We denote by Rd the d-dimensional real space in which both candidate feature vectors and chosen parameter vectors lie.
Each candidate e C' is associated with a distinct feature vector x. E Rd. A parameter vector 0 E Rd induces a linear reward function ra C + R defined by taking the dot product with feature vectors (c) = (8, xx). We will primarily be interested in how these parameterized functions rank the candidates by reward. Let Ra>b (0 ra(a)) 2 (b)) be the region where the reward of is least as large as that of b. Note that aa>b and Rb>aa split Rdd into two half spaces, separated by the hyperplane orthogonal to X, Xs. Parameter vectors O on the hyperplane have ro(a) = ra(b), while rankings in the interior of either half-space strictly rank one over the other.
For a ranking o over the candidates, we say that @ induces a, denoted 0 > a, if a >o b implies re(a) 2 rb).). Let R {0 0D o} be the set of vectors 0 that induce it. Note that this can be written as the intersection of corresponding half spaces R No.bas.. Rav- Further, the
3

---

collection of {R*} essentially form a partition of R covering the space and intersecting only at their boundaries.
We call a 0 non-degenerate if is fully on one side of each of the separating hyperplanes, i.e., ra(a) # ro(b) for all a, b E C. Non-degenerate parameter vectors lie in the interior of some R and thus induce exactly one ranking. We call a feasible if Rº has a nonempty interior, i.c., is induced by some nondegenerate 0.²
Each voter E V submits a ranking over the candidate or. We assume that the feature space is rich enough that voter preferences can be captured via non-degenerate parameter vectors. In other words, we assume that each o, is feasible. We refer to the vector of voter rankings π = (eev as profile. Further, for two candidates a, b, we write Ra>b((T) = Hi V >a, bj for the number of voters that prefer a to b, and ( = M (T)/n )/n for the proportion of such voters. When the profile is clear from context, may shorten these Nay-b and Warb,, b, respectively.
We define a parameter aggregation rule as a function that takes as input a profile a and outputs a parameter vector 0", Our goal is to design parameter aggregation rules such that rg- satisfies desir- able properties with respect to the voter preferences. However, as the properties we care about will only be with respect to how Tg. ranks the candidates, it will be more convenient to work with what we call linear rank aggregation rules that take as input a profile π and output a feasible ranking a. There is a natural way to interpret parameter aggregation rule linear rank aggregation rule, namely, output any feasible ranking induced by 0" The exact properties of the parameter aggrega- tion rule could in principle be sensitive the tie-hreaking of non-degenerate outputs, however, all of our results will be robust to such tie-breaking." 4
We pay special attention to a prominent family of rules from social choice theory referred to as C'1 rules [14], whose outputs depend only on majority relationships, i.c., they only need to know for each pair of candidates (a, b) whether the majority prefers or b.
In our study, we examine several axioms borrowed from social choice theory to evaluate the reason- ableness (fairesss) of our aggregation mechanisms. These axioms include:
Definition 2.1 (Pareto Optimality). A linear rank aggregation rule f satisfies Pareto optimality if. whenever every voter prefers candidate a over candidate on n. i.e. Wa>-((T) = 1, then candidate a is ranked higher than candidate b in the output ranking, i.e., a f(x) b.
Definition 2.2 (Pairwise Majority Consistency (PMC)). A ranking a is called a PMC ranking for a b if and only if majority of voters rank ba; b, ie., Warb 1/2. A linear rank aggregation rule satisfies PMC if. when a PMC ranking a exists for the input profile π and a is feasible, then f(T) = a.
profile for all a, b E C, >>
Note that a PMC ranking for each π need not exist, but when one does, it is unique. The words "o feasible" allude to the possibility that no non-degenerate parameter vector 0 induces the unique PMC ranking. Indeed, we have such an example; see Appendix B for details.
Our research question, then, is whether these axioms can be simultancously satisfied by linear rank aggregation rules, Our approach seeks to provide a concrete illustration of how theoretical insights from social choice can inform practical algorithm design in RLHF.
'The number of feasible rankings is in general upper bounded by m 0(4) due to how many regions (T) hyperplanes can partition the space into [13]. Further. under mild conditions the feature vector locations, the exact number of feasible rankings is known [11, 16].
'One may wonder if there are any computational barriers to converting between parameter and linear rank aggregation rules. However, this is not the case. In particular, for every set of pairwise comparisons R {az > bi, a2 > bz, 03 > o.....), J. we can efficiently (i) check if there is feasible ranking a consistent with R. and (ii) if such a exists, find a nondegenerate 9 inducing such a a. This can be done by finding a satisfying the following system of linear inequalities, or determining that no such can satisfy them (which can be done using a linear program): ra(a) 2 rb(b) 1, Va > b E R. Any 0 satisfying the system would be nondegenerate and induce consistent with R. Furthermore, if feasible ranking is consistent with R, then taking any nondegenerate 0 inducing and scaling up its values would satisfy all inequalities. This means that given a ranking a <i > C2 > ... > Cm. we can check whether or not it is feasible, and so, find a 0 inducing it by running this with R = {cr > C2,..., Cm > }. Additionally, given possibly degenerate 6, we can find feasible ranking which 0 induces by running this with R = {a > b ro(a)) (b)).

---

3 Loss-Based Rules
3.1 Standard Loss Formulation
We begin our study of linear social choice by considering a quite broad yet natural class of rules that capture how RLHF is currently being done. Their core idea is the following: when considering parameter vector 0, for each voter that ranks a pair of candidates a >; b, we should incur some loss for giving b a higher reward than a. To formalize this, let é: IR R be loss function, which we assume is nonnegative. We can then choose a parameter vector minimizing
[(0: T. = Σ Narb(T)) E(ra(b) - ro((a))
a#bEC
Note that the BTL model fits within this framework using f(x) In(1 + +=),, i.c., binary cross- entropy loss.² One caveat to this approach, however, is that optimal @ need not be well-defined: is possible that no minimum is attained. Fortunately, since we only care about rankings induced by optimal parameter vectors,
conveniently remedy this by saying the output is any ranking that is induced by parameter vectors that are arbitrarily close to optimal. More formally, we say that linear rank aggregation rule f minimizes if for all [(T),
inf
L(0; n, E) inf [(0; e)
0:EER"
Even if no minimum is attained, there is always choice of feasible ranking such that Equation (1) satisfied.
With this definition in hand, we proceed to our first main result, which spells rather had news for this class of rules: Any loss-based aggregation rule using nondecreasing and convex loss function (of which BTL is one, and hinge loss is another) will fail our two core axioms, PMC and PO. This paints a negative picture for current RLHF methods with respect to their social choice guarantees. Note that we will exclude the discussion of loss functions with a global minimum at zero, like ReLU, because the loss minimizer will be zero, making all rankings vacuous consequently. And we have focused on convex loss functions due to their practical optimization ease.
Theorem 3.1. If a linear rank aggregation rule f optimizes a loss function that satisfies inf, E(x) < E(O) and is either nondecreasing and weakly convex, or strictly convex (and possibly nonmonotone), then I fails PMC and PO.
Proof. Fix a loss function l satisfying the theorem conditions. Note that since e is convex, we may also assume it continuous [24, Corollary 10.1.1]. Furthermore, since inf, {(x) < E(O), we know that there exists * 0 such that {(x) < (()). The case where x > 0 is relatively simple (as such loss functions lead to unnatural behavior), and we handle it at the end of the proof. For now, assume that there exists < 0 such that {(x) < {(O). Note that this also implies that for all y 2 0, é is lower bounded by the affine linear function connecting (z, {(x)) and (0, ((D),, and thus, lim {(x) 20.
We begin with a small instance just three candidates Crore {a. b, c} to gain some traction on how f behaves. We will later extend this instance with additional candidates to demonstrate profile where PO and PMC fail. The candidates will have feature vectors x, == (2, 1), x2 == (1, 1), and x == (0,0). 0). respectively. Furthermore, a p-fraction of voters (for to be chosen later) will rank a > b > c, while the remaining (1 pf-fraction will have inverted preferences, ranking e a.
Let
C (0)
Σ (ex))(ro(y)-raa -
*Typically, BTL is presented choosing 0 maximizing the likelihood of seeing the pairwise com- parisons we observed, assuming that Pr(a b]
e' (500) That is, we choose maximizing
cralu) Parb By taking the log and swapping the sign, we see that this is equivalent to mini-
Nazs (="9t))+e-001))
mizing Eogs log 100 (00))_
'It so happens that these rankings are feasible, but for now we will not worry about this as loss function- based rules still make sense regardless of whether the inputs are feasible. For the final example, we will ensure that the rankings are feasible.
5

---

with weyy E (1-111111 pt be the loss function on this instance (scaling Rzzy down to wayy leads to an equivalent formulation). Let g(z) = p ( -))((2)) Note that we can rewrite foom
( (0) g(ro (a) - ro ro( (b) g(ro(a) -aap((aa)rr))))))) ro(c)) + ((ro
Note that (c) = 0 for all 0, so we can simplify this
_ (0) g(ro(a) - ra(b)) ((ro(a))) g(ro())).
We will consider unconstrained version of this problem where free to choose rewards Tas Tb e R arbitrarily, and later show by which vectors these optimal values can be induced. That is, we will first find ray Tb R minimizing
Cunconstr (Ta:Tb) == g(ra - rb) + g(ra) + g(ro)-
Let - (fore(0) inf Leore (8') and PPTunconsty {(ra) Lunconstrr (ra- rb) inf,;, .r.g Canconstr (r', } be the set of minimizers for these two loss functions. In Appendix A, we establish the following results about these optimal sets.
Lemma 3.2. There exists rational p E (1/2,1] and values A1 < A2 with A2 such that OPTunconstr is nonempty and for all (Ta,Th) & OPTunconstr To >> Ag and Tb S A1.
Lemma 3.3. Suppose Lemma 3.2 holds for values p, A1 and A2, then, for this same choice of p. OPT is nonempty and there exist Ag and A4 with Ag > 0 such for all (01,02) E OPT 0 > A3 and 02 < As.
We will now explicitly construct a family of instances with candidate feature vectors parameterized by value E R such that for sufficiently small > 0, the output of f fails the two axioms. Fix p, A3 and A₁ from Lemma 3.3, and choose 8 with
such that 8A, As < 0 (8 < As/A1
works if A4 > 0, and otherwise, any 0 < 8 < 1 will do).
Each instance will have six candidates, which we will think of two groups of three, C Coorr U Coopies The first group Choore = {a. b, c} will be the same as the three-candidate instance from above, while the second group Croopees {a' b/, d'} will be new. The candidates a, b, will still be located at Xa == (2, 1), X == (1, 1). and x. == (0, 0), respectively. The candidates a', b', c' will be located near their undecorated counterparts X.! == X. + (-E,0), X X + (-e, 0) and X := X + (-8,6-5).
Next, we describe the voter preferences. A p-fraction of voters will have the ranking > a' > b > > c' > c, and the remaining (1-p) --)-fraccion of voters will have ranking > c >> b' > b> a' > a. As long O < E < 1 (which will be the case for our final chosen E), these are both feasible rankings. The former is induced by the nondegenerate feature vector (1, 1) and the latter by (-1,0).
For each E E R, let
(= = Σ wergllro(y) re(2))
JYVEC
with Mayy
{0, p.p, be the loss function optimizing using candidate locations parameterized by E.
We will show that for sufficiently small > O. inf ne' (0) infe L (0). This means that must output ranking with e > d. Observe that this is a PO violation because all voters agree that d' > Furthermore, this is PMC violation because a majority of voters have the ranking a >> a' > b' - c' > c, yet this is not the output.
Let (P)(s) be the set of vectors optimizing L The rest of the proof will follow from the following two lemmas, whose proofs are in Appendix A.
Lemma 3.4. OPT(0) C R'Ts
Lemma 3.5. Suppose OPT(0) C Re're then, for sufficiently small > O, inf inf o. (e > inf, L (0).
7 This induces rewards 3,3 s,2,, e, (1-8) 8) e and 0 for a, a', b, D' c', and c, respectively.
'This induces rewards c,0, 0,0, E, -1, -2 + and -2. for d' c, b d', and a, respectively.

---

Finally, we handle the case that exists x' > 0 such that {(x) < {(0). Note that by convexity, this implies that for all y O. E(y) > { > {(2), so infyso Ely) inf, {(y). Now, consider an instance with two candidates (a, bj located at ranking a > b (feasible via the parameter vector (1, 0)). It possible to achieve a loss of f(r)) e.g.,
= (1,0) and X; (0, 1), and a single voter
by outputting the parameter vector (0,z), On the other hand, any 0 inducing the ranking a > b will
be lower bounded by {0)) > {(x) from above. Hence, f must output > a, which is both a PO and PMC violation.
3.2
Majority-Bann -Based Loss Formulation
Despite the negative results for loss-function- based rules, we may hope for a remedy using slightly different information. Specifically, we consider similar loss-based function that rather than getting penalized for disagreeing with each voter only gets penalized if it disagrees with majority of voters. That is, we choose 8 minimizing
Lmai (0; 1)
I[Wa= > 1/2) ((re()) - re(a))) afDEC
Σ
Defining a parameter aggregation function based on this loss suffers from the same caveat as before, that in some cases no optimal 9 exists. Nevertheless, we can apply an analogous fix for a ranking variant. We say that linear rank aggregation rule minimizes E in the majority formulation if for all = f(T))
inf m (0; π E) = inf maá (0; E).
0:0E
We first show (in Appendix A.5) that this does indeed help achieve PMC with essentially all loss functions.
Theorem 3.6. Fix a nondecreasing loss function e with E(O) inf l(x). If linear rank aggrega- tion rule f minimizes in the majority formulation, then I satisfies PMC.
Note that if the E(0)= > i {(x) condition is not satisfied, i.e., E(0) inf (xx). then all linear rank aggregation rules / minimize in the majority formulation, so satisfying this is a vacuous condition. Indeed, the parameter vector 0 of all Os achieves optimal loss of E(O) for each pair and is consistent with every ranking a. Therefore, the condition E(0) > inf {(x) is as innocuous as possible to rule out these edge cases.
However, despite this good news for PMC, we show that this does not help in achieving PO. In fact, negative result extends to every C1 linear rank aggregation rule. Note that if f minimizing in the majority formulation breaks ties consistently (i.e., if multiple feasible rankings are optimal, then it consistently chooses the same one), then it is CI. We then have the following result, whose proof is relegated to Appendix A.6.
Theorem 3.7. All C1 linear rank aggregation rules PO.
This result is quite unfortunate, because if there were a rule that is both C1 and PO, we would automatically achieve PMC: Whenever there is feasible PMC ranking, a C'1 rule cannot distinguish between this profile and profile where all voters submit this ranking, hence, under the PO criterion, it must output it. Furthermore, whenever there is PMC ranking, outputting it is necessarily PO, as for every pair, a majority of voters agree with the PMC ranking. Interestingly, in the proof, we construct profile which has PMC ranking, yet is not feasible, and matter how C'1 linear rank aggregation rule breaks ties, there is an underlying profile in which this output violates PO.
4 Social Shoice-Based Rule
In light of the above negative results, in this section, we ask whether there are linear rank aggre- gation rules that concurrentyy satisfy our two axioms, PO and PMC. We answer this question affirmatively by presenting a new method based on a prominent rule from voting theory.
The Copeland rule assigns Copeland score to each alternative equal to the number of other alter- natives it beats in a pairwise competition, i.e., the score for a is Hb Wayb > 1/2)/. It then ranks the candidates in descending order according to their Copeland scores (breaking ties arbitrarily). It
7

---

is known that Copeland satisfies PO, PMC, and additional axiomatic properties, However, in linear social choice, since not every ranking feasible, we cannot always output the Copeland ranking.
We, therefore, define a new linear rank aggregation rule, which we call leximax Copeland. This rule chooses feasible ranking as follows. It ranks first the candidate with the highest Copeland score that can be feasibly ranked first under some parameter vector t. Subject to this first position, it ranks second the candidate with the highest Copeland score which can be feasibly ranked second, and continues this process for subsequent positions.
Copeland's 's rule is C1 rule because it only requires the majority relationships between the can- didates. Analogously, leximax Copeland is also a C11 linear rank aggregation rule. Therefore, by Theorem 3.7, it does not satisfy the PO criterion. To address this issue, we define variant called leximax Copeland subject to PO (I.CPO), which incorporates the PO criterion. Under ICPO, for every pair of alternatives where one dominates the other, the rule restricts rankings to place the dominating alternative above the dominated one.
The rule remains well-defined since the set of feasible rankings when enforcing the PO criterion is non-empty, as whenever a dominates b, all the rankings in the input profile rank above Note that if the Copeland ranking is feasible, then this rule outputs that ranking, since unrestricted Copeland satisfies PO.
In addition to PO and PMC, we wish to show that LCPO satisfies two additional properties, which we define presently.
Definition 4.1 (majority consistency). A linear rank aggregation rule satisfies majority consistency if when candidate is ranked first by a majority of voters in the input profile, is ranked first in the output ranking.
Majority consistency ensures that the collective decision reflects the preference of the majority when there is clear favorite. This principle aligns with PMC, but specifically focuses on the majority's s favorite alternative. However, as we discussed above, a PMC ranking does not necessarily exist, and even when it exists, it is not necessarily feasible. By contrast, when a majority winner exists, this candidate is necessarily ranked first by a majority of voters in the input profile, who themselves (by assumption) submit feasible rankings. Therefore, we need not handle the case where it is impossible to rank the majority winner first
Definition 4.2 (winner monotonicity). A linear rank aggregation rule satisfies winner monotonicity if. when a candidate is ranked first in the output ranking, elevating in any voter's preference does not cause a to lose their top position in the updated aggregate ranking.
Winner monotonicity ensures that improving a leading candidate's position among individual voters will not result in that candidate's 's demotion.
We now state and prove the main result of this section.
Theorem 4.3. LCPO satisfies PO, PMC, majority consistency and winner monotonicity.
Proof. LCPO trivially satisfies PO since it always outputs ranking that respects the PO criterion. Moreover, since Copeland satisfies PMC, and whenever Copeland's ranking is in the domain, lexi- max Copeland subject to PO returns this ranking, it clearly satisfies PMC.
Note that if an alternative a is ranked first by at least half of the voters, then a has the highest Copeland score, meaning that leximax Copeland subject to PO will rank this candidate first if this is possible. We see that this is indeed possible, by noticing that there is at least one feasible ranking in the input profile where is ranked first, and any such input ranking is feasible (by assumption) and satisfies the PO requirement. Therefore, majority consistency is satisfied.
It remains to show that LCPO satisfies winner monotonicity. Suppose that on input profile n, the rule outputs a ranking a where candidate a ranked first. Now, consider a profile x' which is similar to π with the only exception being ranking in which is placed in higher position. Let S be the set of agents that ranked above a in Copeland's ranking under π and let S' be the set of agents that ranked above a in Copeland's 's ranking under n'. Note that S' C S, since when moving from to to', only the Copeland score of a can increase, and therefore is not possible for candidate b to beat under n but not under
8

---

Now, suppose that R and R' are the set of rankings that satisfy the PO criterion with respect to π and H', respectively. We show that R' C R. First, note that since is ranked first under æ,, no alternative dominates in x, as otherwise the PO criterion would be violated. Therefore, we get that no other alternative dominates a in r' as well. Moreover, note that if dominates e in æ, then this remains true in n' as well. On the other hand, it is possible that a dominates an alternative b in x' but not in т. From all of the above, we conclude that R' C R.
Since a is ranked first in o, we get that for every candidate b E S, there is no ranking in R in which b ranked first, since otherwise, LCPO would output such a ranking. This also means that for every candidate b in S", there is no ranking in R' in which b is ranked first, since R' S R and S' S S. Moreover, note that every ranking in R in which a ranked first also R' since it satisfies all the PO restrictions of n'. Therefore, under x², LCPO outputs ranking in which is ranked first. n
Leximax Copeland subject to PO can be implemented in polynomial time by solving O(IC1²) rela- tively small linear programs. Specifically, given an input profile, we sequentially choose the candi- date that is ranked in position r + follows. We denote by or the partial ranking, where the first r positions have been fixed. For each candidate c that has not been ranked yet. we want to check if there is parameter vector that adheres to the partial ranking or, respects the Pareto optimality criterion and ranks e at position r + 1. Since all these constraints can be expressed as pairwise comparisons, we
linear program such as the one described in Footnote 4 to check if such a feasible ranking exists. Among the candidates meeting this criterion, we select the one with the highest Copeland score for position
5 Discussion
We conclude with a discussion of several extensions and limitations of our approach and results.
First of all, we wish to emphasize that our results are theoretical. While they highlight some short- comings of the current practice of RLHF, our goal was not to "outperform" existing RLHF methods. Rather, we see our model as giving a framework for understanding and comparing rules and meth- ods ids-it is (useful, we believe) lens through which researchers and engineers can examine their AI alignment methods.
Second, as written, our model has voters give their complete rankings, while in practice, this would be infeasible. In the real world, we are likely to elicit only relatively few pairwise comparisons per person. For our negative results, this assumption only makes them stronger: the BTL model fails both PO and PMC even with access to complete voter rankings. By contrast, for the positive results, specifically implementing leximax Copeland subject to PO, this ostensibly seems like serious limitation. However, the complete rankings are not necessary for computing this rule, rather, all we need to know are PO dominance relationships and majority directions. We can therefore apply the rule whenever we can approximate this information, for example, through sampling. An alternative approach is to infer a complete ranking of each voter by fitting parameter vector based on their pairwise responses; this process of learning a complete ranking and then running voting rules has been used before in variety of settings [20, 18).
Third, our work initiates the study of the axiomatic method our linear social choice model. How- ever, we leave open many questions about which axioms are compatible and finding rules that achieve them. It should be clear by now that the primary challenge in linear social choice is that not every ranking over the candidates can be output. This means that essentially all known aggregation rules cannot directly be used without at least some modification. A natural direction to tackle is to try to find methods of converting known voting rules into linear aggregation ones while maintaining some of their axiomatic properties. To this end, we conclude with some preliminary results, and somewhat surprising findings within this space.
Some rules which optimize over rankings can be naturally transformed. For example, consider the Kemeny rule, which returns the ranking with the smallest pairwise disagreement over all votes. This can easily be transformed to the linear setting by simply outputting the optimal feasible ranking- In fact, in Appendix C.2, we show that this rule carries over the property of separability,' social choice axiom that is violated by Copeland (in the classical setting) and leximax Copeland subject to
Formally, ranking separability to distinguish it from the single- winner version.

---

PO (in our setting). We show this in Appendix C.I. However, quite strikingly, although separability remains, this transformation makes Kemeny longer PO (Appendix C.2).
Finally, note that the "leximax" portion of leximax Copeland can be seen as a general purpose tool for mapping traditional rules to linear aggregation rules. In Appendix C.3, explore leximax plurality (run leximax on the ranking of candidates by plurality scores), and show that it satisfies majority consistency, winner monotonicity, and separability. Additionally, the "subject PO" can be seen as another "tool" for enforcing the Pareto optimality criterion when rule does not indepen- dently satisfy it. However, enforcing PO can again cause somewhat surprising results. For example, in Appendix C.2, we show that linear Kemeny subject to PO, while now trivially satisfying PO, again violates separability. These observations indicate the challenges inherent linear social choice, and we hope these open questions inspire fruitful follow-up research.
Acknowledgments
This research was partially supported by the National Science Foundation under grants IIS-2147187, IIS 1IS-222888,, CCF-2007080. 1IS-1905558, and IIS-2214141; and by the Office of Naval Research under grants N00014-20- 1-2448 and N00014-24-1-2704.
10

---

References
[1] Nir Ailon and Mehryar Mohri. Prefcrence-based learning to rank. Machine Learning, 80: 189-211, 2010.
[2] Kenneth Arrow. Social Choice and Individual Values. Wiley, 1951.
[3] Claude Berge. Topological Spaces. Oliver and Boyd, 1963.
[4] Erdem BIyık, Nicolas Huynh, Mykel Kochenderfer, and Dorsa Sadigh. Active preference- based Gaussian process regression for reward learning. arXiv preprint arXiv:2005.02575. 2020.
[5] Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324 345, 1952.
[6] Felix Brandt, Vincent Conitzer, Ulle Endríss, Jerôme Lang, and Ariel D. Procaccia, editors. Handbook of Computational Social Choice. Cambridge University Press, 2016.
[7] Souradip Chakraborty, Jiahao Qiu, Hui Yuan, Alee Koppel, Furong Huang, Dinesh Manocha, Amrit Singh Bedi, and Mengdi Wang. MaxMin-RLHF: Towards equitable alignment of large language models with diverse human preferences. arXiv preprint
2024.
[8] Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in Neural Information Pro- cessing Systems, 30, 2017.
[9] F.H. Clarke. Optimization and Nonsmooth Analysis. Wiley New York, 1983.
[10] Vincent Conitzer, Rachel Freedman, Jobst Heitzig, Wesley H Holliday, Bob M Jacobs, Nathan Lambert, Milan Mossé, Eric Pacuit, Stuart Russell, Hailey Schoelkopf, Emanuel Tewolde, and William S. Zwicker. Social choice for AI alignment: Dealing with diverse human feedback. arXiv preprint arXiv:2404. 10271, 2024.
[11] Thomas M Cover. The number of linearly inducible orderings of points in d-space. SIAM Journal on Applied Mathematics, 15(2):434-439, 1967.
[12] Jessica Dai and Eve Fleisig. Mapping social choice theory RLHF arXiv preprint arXiv:2404.1 13038 2024.
[13] H. Edelsbrunner. Algorithms in Combinatorial Geometry, volume 10 EATCS Monographs on Theoretical Computer Science. Springer, 1987.
[14] Peter C Fishburn. Condorcet social choice functions. SIAM Journal on applied Mathematics, 33(3):469-489, 1977.
[15] Luise Ge, Brendan Juba, and Yevgeniy Vorobeychik. Learning Linear Utility Functions From Pairwise Comparison Queries. arXiv preprint arXiv:2405.0266 02000.0222.2222 2024.
[16] Henry W Gould. A note the number of linearly inducible orderings of points in d-space. SIAM Journal on Applied Mathematics, 26(3):528 280000, 1974.
[17] Andras Kupesik, David Hsu, and Wee Sun Lee. Learning dynamic robot-to-humant object handover from human feedback. Robotics Research: Volume 1, pages 161-176, 2018.
[18] Min Kyung Lee, Daniel Kusbit, Anson Kahng, Ji Tae Kim, Xinran Yuan, Allissa Chan, Daniel See, Ritesh Noothigattu, Siheon Lee, Alexandros Psomas, et al. Webuildai: Participatory framework for algorithmic governance. In Proceedings 22nd ACM Conference on Computer- Supported Cooperative Work and Social Computing, pages 1-35, 2019.
[19] Abhilash Mishra. Al alignment and social choice: Fundamental limitations and policy impli- cations. arXiv preprint arXiv:2310, 16048, 2023.

---

[20] Ritesh Noothigattu, Snehalkumar Gaikwad, Edmond Awad, Sohan Dsouza, Iyad Rahwan, Pradeep Ravikumar, and Ariel Procaccia. A voting-based system for ethical decision mak- ing. In Proceedings of the 32th AAAI Conference Artificial Intelligence, pages 1587-1594, 2018.
[21] Ritesh Noothigattu, Dominik Peters, and Ariel D Procaccia. Axioms for learning from pairwise comparisons. Advances in Neural Information Processing Systems, 33:17745- 2020.
[22] Long Ouyang. Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray. John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35:27730-27744 2022.
[23] Chanwoo Park, Mingyang Liu, Kaiqing Zhang. and Asuman Ozdaglar. Principled RLHF from heterogeneous feedback via personalization and preference aggregation. arXiv preprint arXiv:2405.0025:: 2024.
[24] Tyrrell Rockafellar. Convex Analysis. Princeton University Press, 1970.
[25] Anand Siththaranjan, Cassidy Laidlaw, and Dylan Hadficld-Menell. Distributional prefer- ence learning: Understanding and accounting for hidden context in RLHE. arXiv preprint arXiv:23/2.08358, 2023.
[26] Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul Christiano. Learning to summarize with human feedback. Advances in Neural Information Processing Systems, 33:3008-3021, 2020.
[27] 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.040555 2024.
[28] Paolo Viappiani and Craig Boutilier. Optimal Bayesian recommendation sets and myopically optimal choice query sets. Advances in Neural Information Processing Systems, 23, 2010.
[29] H Peyton Young. Condorcet's 's theory of voting. The American Political Science Review, 82(4): 1231-1244, 1988.
[30] Huiying Zhong, Zhun Deng, Weijie J Su, Zhiwei Steven Wu, and Linjun Zhang. Prov- able multi-party reinforcement learning with diverse human feedback. arXiv preprint urXiv:2403.05006 2024.
[31] Banghua Zhu, Michael Jordan, and Jiantao Jiao. Principled reinforcement learning with hu- man feedback from pairwise k-wise comparisons. In Proceedings of the 40th International Conference on Machine Learning, pages 43037-43067, 2023.
[32] Daniel M Ziegler, Nisan Stienmon, Jeffrey Wu, Tom B Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geoffrey Irving. Fine-tuning language models from human preferences. arXiv preprint arXiv: 0999998999 2019.
12

---

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

---

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

---

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

---

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

---

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

---

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

---

A Deferred Proofs
A.1 Proof of Lemma 3.2
Proof. We begin with some observations on First, we have that since & is nonnegative, must also be nonnegative. This along with the fact that lom {(x) cc, we have that both limg- g(z) Do and limg- oo ((r) = oc. Together, these imply that Lunconstr attains a minimum. Indeed, Cunconatr (0, (0,0) 3g(0), and there is some bound B such that for all x > B and
BB,
g(z) 3g( We can therefore restrict the optimization problem to Ta, Tb E [-B, B) without changing the solutions. Since Lunconstr continuous and [-B, B compact, minimum is attained.
Next, note that y convex because compositions of convex functions with monotonic functions and convex combinations of convex functions are convex [24]. From this, we claim that if there is an optimal solution (ray rb). then (ra; (aa: is also optimal solution. Indeed, fix such (ra: Tb),
Cunconstr (ra: Na ra/2) = g(ra - -ra/)) + g(ra) + g(ra/2)
g(ra) + 2g(ra/2)
= g(Ta) + 2g(1/2(ra - rb) + 1/2ro)
g(ra) + 2(11/2g(ra rb) 1/2g(r=))
Lunconstr (ra;
where the inequality comes from convexity. This implies that (ra, ra/2) is also optimal. By above, we have that if (rb, ra) is optimal, it must be the case that minimizes
h(ra) == 2g(ra/2) + g(aa).
Observe that is again convex by monotonic composition and convex combinations.
Next, will make use of the following facts about convex functions. Although they need not be differentiable, right- and left-hand derivatives always exist. For a function & these are defined as
k(x + h) k(x))
(x)) lim
h-+
h
k( + h) k(x)
A (x) =
lim
h-
h
Further, l is convex, we have that [24]:
(i) k4 and K'_ are nondecreasing,
(ii) k (x) < (x)) for every a,,
(iii) x minimizes k if and only if (x(x)) 0 k0)),
(iv) K4 and K__ are right and left continuous, respectively.
They also follow standard linearity and chain rule properties, which allow for simpler computation. For example:
if k(x) az(x) + 68(x), then K4 (x) aa', + (z).
if kxx:: = a()a), then (x(x) (z) 70' (7x: if 2 0. and K (x) = ya'_ (yar) if y < 0,
(all of these hold for left-hand derivatives by swapping the positions of and -) [9].
Next, we claim that we can find a valid p (rational with 1/2 < p < 1) and w > such that g', (w) > O, while h4, (w) O. To that end, expanding the first derivative, we have
= = - (1- ())))
As long as l' (-z) + (x) > this is strictly more than 0 for p satisfying
(x)
p 8 (- x) + (x)
19

---

For h,
(x)x)) = (1/2
(z).
= --p(_((-/22+(((--)) + (11-)) (x)].
As long as P-_ (-x/2) f- (-))) 0, then this is strictly less than 0 for
(0022)+4000 + (-==
p
(3)
Now, choose w > 0 such that e (-w/2) > procedure. We know E (0) > 0 (as otherwise ((0) < {(x) for all x < O, contradicting assump- tion on f). We will split into cases depending on whether l is nondecreasing or strictly-convex (at least one must be true by the theorem assumptions).
>- (-w) 2 0. This is possible by using the following
First, suppose is non-decreasing. This implies that ('(x)) 2 for x. We know that there is point < 0 such that E'_ (x) (0) (as otherwise & would eventually become negative). Let (x). Take w such that
- sup(2 (z) d}.
Note that (-w) d because 8__ is left continuous (from (iv) above). Since -w < 0, -w. This implies that 8-_ (- -2) > d, as otherwise -u would not be the supremum of such points. In addition, we have that d 2 0 because
nondecreasing.
Next, suppose is strictly convex. then L"_ is strictly increasing, Further, since it is left continuous and (0) > O, there is a y >> 0 such that for all x E [-,,0) L' (x) 0. Therefore, choosing w ? will do: P-_ (->) 2 0 by choice of y, and -7/2 2 > -7, so E- (-7/2) > (-7) since e__ is strictly increasing.
For this choice of w, we first claim that the preconditions of denominators being positive hold for (2) and (3). Indeed, let us write 21, 22, 2g, 24 for 6 (-2w), E (-w), (w) l. (2w). We know that
2 22
23 24
by properties of convexity, and since l (_(-w) ( 8 (-w) > O, have that 0 21 < 22. The denominators are of the form 21 +2 and 21 + 22 + 24, which are now both necessarily positive. In addition, we also claim that a rational p with 1/2 < p satisfying both inequalities (2) and (3) will exist. Note that inequality (2) can now be represented as #1 and we have that .
24
< 1
21 + 24
because 0 21 24. Additionally, inequality (3) can be represented
23 + 24
21 22
23 +
24
which is at least 1/2 because 23 + 24 >
21 + 22. Finally, we have
21
21
<
22 23
22 24
21
which implies that
23 24
21 + 32 23 24
21 + Z4
Hence, there exists some rational p in this interval, which is necessarily between 1/2 and 1, as needed.
To summarize, have found valid p and value > 0 such that (L) < 0 while g' (w) > O. Because h4 is right continuous (from (iv) above), there is some 7 > such that h1, (w + + < 0 as well. We will now show for (ray PTTnconstrr Ta > w + and rb S w. Indeed, note that To must minimize h, h²_ (ra) 2 0 (from (iii above), which implies w + c. For Tb. suppose
20

---

for contradiction rb > w as well. Note that g4 > 0 means is increasing to the right of w. Let min(ra. (Ta, (b) 0. Consider (r's %6) (ra rb d). We then have
Cunconstr (F' r/)) = g(r', - r//) + +((r)) + g((r))
g - rb) + ((())) + g((()
< g( rb) + g(ra) + g(r))
Cuncomatr (Ta.
where the equality holds because r/ - rb and the inequality because is increasing to the right of w. Therefore, we reach a contradiction, because then (Ta:Th) would be optimal. Thus, we have found values satisfying the lemma statement with A and A2 7
A.2 Proof of Lemma 3.3
Proof. Fix p inducing nonempty OPTunconttr satisfying Lemma 3.2 with values A and Ag- We first claim that for any (Ta, (regardless of optimality), it is possible to find a such that re (a) Ta and (b) = Tb. Indeed, note that
2
01
re (r((a)
1
022)
rb(bb)
2 1 1 is invertible with inverse
Since M- =
M- = (11 -1)
2 )
for any Ta: we can simply set
0 = M- Fa
Thus, OPTeom is nonempty, and is simply the image of OPTuncnstr under M-1 Now, fix By assumption, we have ra > Ag and r A1-
(ra, ro) E OPTuncontrr and let M-1
1 Na rb A2 A1, while 0₂ 2rb ra 2A1 A2. Thus, setting
rb
This implies that 0,
Ag = A2 A1 and A4 = -2A1 A2 satisfy the desired properties.
A.3 Proof of Lemma 3.4
Proof. We first claim that OPT( OTrore, This will follow from showing
(0) 4 C (0) + 3-())
Indeed, in L the copied candidates are in exactly the same location as their counterparts. Hence, each term in Ceore appears times, one for each combination of original and copy. In addition to these, there are the 6 terms for each ordered pair of (a, a'), (6, b'), and (c, Note that, each since they are the same location. Therefore,
(a(x) = re (x') for each x E {a, b, e} regardless the l portion is always E(O), and the corresponding Ware'' and Wa'>a terms add up to for each pair. Hence, the total sum these terms 3 E(O). Since L is equivalent to ceore up to positive scaling and translation, they have the same optima.
Finally, fix a 0 E OPT(0). Since 0 E OProrre by Lemma 3.3, 02 > A3 and 02 As. Thus,
To (c(c') = (-01 502) < < 8A4) 0 ra(c)
by choice of 8. Hence, 0 E Re'sc
A.4 Proof of Lemma 3.5
Proof. We first show that when optimizing each _ it sufficient to consider only 0 coming from bounded region. Indeed, observe that L (0) ())(()
((0) for all Since lim {(x) 00,
21

---

We will have 9 candidates; 8 will be labeled of and c, for i = 1,2,3,4, 4, and one labeled c*. They will have feature vectors in RR. Each oi will be located at xx+ = t where e; is the i'th 10,0,0, 0, 11). Finally, e* will be located at (e(()) = ()) 1-p
can find some B > O such that for all x > B, {(x)
For pair of candidates
+ E Ceoom in the two terms concerning these candidates, we have
Wx wa-y ((ro))) rr(=)) (y>=((ro(x)) ro(u)) 2 (1 - p) (e(ro(v)) - + (ro
2 p)e((ro(0)) - ro(x))))
Applying this to {a,b) by and {b,c}.
L (0) (1 p) (e((ra(a)) ro(6) (((ro())) ro(c)))
= (1- ((((()) + E(10] + 02))
This implies that we may restrict our attention to 0 in the region
Rbounded 10 |0:1 S B, 102l S 2B3.
Indeed, for 0 & Rbounneed either [01| > B or 01 + 021 B. In either case, we have (=) > (1 (B)) (0).
Note that (0) is continuous not only in 9 but also in E. Additionally, Rhounded is closed and bounded, and hence, compact. Therefore, by Berge's s Maximum Theorem, (P)(s) nonempty and upper semi-continuuus in e [3]. As per the definition of upper semi-continuous, since OPT(0) S
Re'=c, an open set, for sufficiently small > O, OPT(s) S Re'*,, Finally, note that R te phounded is compact, minimum is attained, and this minimum must therefore be strictly larger than the values attained by members of (P()).
A.5 Proof of Theorem 3.6
Proof. Without loss of generality, we may assume that inf, {(x) = 0, as otherwise we could trans- late l without affecting the optimization problem. Fix a profile with fcasible PMC ranking and let grMC be a non-degenerate parameter vector that induces a.
First, we show that infg Lmai (0; E) = O. Indeed, note that c.- 0PMC E RRT for all c > 0. Further, note that for any a, b with (a>+((T) > 1/2, Tarus (b) Tepaae (a) < Therefore, by making c large, the nonzero terms in L will have an input to É negative and becoming arbitrarily large in magnitude. Since is nondecreasing, these approach the infemum of O.
Next, for any o' # a, infg L (0; n, E) 2 >(()). Indeed, there must be some pair of candidates o, b with a + a b and b > a. For any 0 E R (b) 2 ro(a,, so ((ro(b) ra(a)) 2 E(O), and this lower bounds the loss function.
A.6 Proof of Theorem 3.7
Proof. We construct an explicit instance and pairwise majority relationships such that no matter what feasible ranking a rule picks, there is an underlying profile where that output was a PO viola- tion.
standard basis vector, i.e., of is at (0, 1,0,0) and ej (1/5,) 1/5, 1/5, 1/5).
There will be 5 voters. Their pairwise majority graph will be follows. Candidate e* will pairwise beat all others. In addition, each et will pairwise beat each cj Among the oi candidates, there will be cycle ot > ct > cg of at and between the remaining two pairs of > c and oj ot- The of candidates will be the exact reverse of this, i.e., a cycle o > Cg > C2 G 4 along with og > ci and c7 > C2 A pictorial representation can be found in Figure 1.
CI rule must pick 0 solely based on the pairwise majority graph. We will show that regardless of what 0 it outputs, this will lead to PO violation.
22

---

ci
2
2
C
C3
C3
Figure 1: Graph showing pairwise majority relationship between candidates. Regular edges show relationships among of candidates and among ç candidates. Thick edges indicate that ct pairwise beats all candidates, and each ot pairwise beats each oj candidate.
To that end, the first fact we will show that no can rank e* first. Indeed, for any 0, re(c") = E, A I E, [0:] < max; [0)]. On the other hand, for i maximizing [6,], at least one of cf will achieve this reward, strictly larger than ro(c"). Hence, regardless of the output A some candidate must be ranked above ct. We will show that this leads to a PO violation.
To construct profiles consistent with the pairwise majority graph, voters will always have rankings of the following form:
c
4)
for some the rest in some order, followed by all candidates the reverse order. This is always achievable with the voter vector that puts values 3e, 2e, 1e in entires i, j. k; and f, respectively, for some small & >
4]. In other words, they will rank single candidate above e and
Fix an output 0 with induced ranking a. There must be at least one candidate * c* ranked above c*. We now split into cases depending on which candidate this is. For each choice, we will construct profile consistent with the pairwise majority graph where the candidate above c* is Pareto dominated by c². We will describe each voter's ranking only by an ordering over the + candidates, assuming they otherwise take the form described in (4). Note that c* is always ranked second, so if candidate never ranked first, they are Pareto dominated by e*. The profiles for each candidate et can be found in the following table. One can check that all pairwise relationships are satisfied, and the corresponding of is never ranked first.
Table I: Profiles with 5 voters and consistent with the pairwise majority graph where where the corresponding candidate is PO-dominated by c² The notation 1 (2, 1, 4) implies one voter has the ranking in the form of (4) with (i.j, k, 3,44.
1: (2, 1,3,4) 4)
2: 3,44)
2,4,4
2: (1,2,3,4)
1: (3,
1, 2)4)
2: (3,2,4,1)
2: (2,3,44,11
2: (2, (2,4,113)
1: (3, 2, 4,1)
(4,1,
(4,1,2233
1: 13,4,1,2)
2: 1.2.3
Finally, if candidate is ranked above ct, then any of the following profiles work, all candidates are Pareto dominated by e" with rankings shown in (4).
B PMC Infeasibility Example
Consider the case with d 3 and seven candidates: one special candidate located at (1/4, 1/4, 1/4), and six others o² located at standard basis vectors + We have three voters with parameter vectors (1, e), (2e, 1),), and (28,e, 1), where & < 1/5 is a small positive number. These voters have the following induced rankings:
23

---

Rank
U1
V2
03
1
02
2
a
a
3
C2
C
4
3
22
5
C3
C3
C2
C2
1
C1
C2
C3
We argue the ranking a' > cj > cj > C3 > 03 function can position a" the top of this ranking.
> S > ci a PMC ranking but no linear reward
For any reward vector (01, 02 03)
R$, the reward for a" is
a = (0 + +2 03)
Given the placement of of the standard basis vectors, each c₁ achieves reward equivalent to one of the absolute values of the components of 0, thus surpassing rg since
max 10:].
C Additional Axiomatic Properties of Social Choice-Basee Rules
We begin by stating another prominent axiom from social choice theory.
Definition C.1 (Separability). ranking aggregation rule satisfies ranking separability (or separa- bility for short) if. when two profiles yield identical output rankings, when combined into a single profile, this should also produce the same output ranking.
Ranking separability preserves consistency in aggregation outputs and ensures stable decisions across similar preference distributions.
C.1 Copeland Violates Separability
Theorem C.2. Both Copeland (in traditional social choice) and LCPO (in linear social choice) fail separability.
Proof. Consider the following two profiles on candidates with five and three voters each:
Rank
?1
Ub2
V/
V's
Rank
U6
V7
1
0
b
b
1
2
g
a
2
d
a
3
d
C
3
b
4
e
e
d
4
f
d
5
f
d
f
5
c
6
b
6
7
6
f
6
7
e
f
In the first profile, the Copeland scores are 5, 3,4,3,3, 3,3, for candidates a, b, c, d, e, f.g. respec- tively. Similarly, the second profile, they are 3, 3, 1, 1, So under any consistent tie-breaking rule, both of these profiles would output the ranking a > b > > d x > f >
However, if combine these two profiles, then the thus, b will be ranked above a, violating separability.
of is 5 while the of is 6, and
To see that this also holds for LCPO, note that when every ranking is feasible, LCPO coincides with Copeland. We can simply have 7 candidates R7 all located at unit vectors, and voters with inputs from the above profiles.

---

C.2
Linear Kemeny Rule
Next, we consider different rule from social choice theory, the Kemeny rule, which can trans- formed to the linear setting while maintaining the separability can be achieved along with PMC. Given imput profile я, the Kemeny rule returns ranking o that minimizes the total number of pairwise disagreements with voters rankings, i.e.
arg min m
Σ
Σ
1(b>a a)
KEV (a.b)aaze,b
where 9 contains all possible permutations of the candidates. This expression can be equiva- lently written as
Σ ma>b(()) [bb > a).
arg min oES
aFbEC
Here, we define the linear Kemeny rule, which outputs a parameter vector 0* that induces a ranking that minimizes the total number of pairwise disagreements with voters' rankings, i.e.,
l E arg min
E Marb(() (ro(b) > ra(a))
BERN
aFDEC
Note that this rule conforms to the standard loss formulation, where the loss function is binary: it is if two rankings agree with respect to the relative ranking of pair of candidates and otherwise. Since binary loss is not convex, it does not fit in the impossibility result of Theorem 3.1.
Note that Kemeny is generally NP-hard to compute; however, even for linear Kemeny, there is at least an exponential time aglorithm by brute-force computing the score of every ranking, and determining whether not it is feasible.
Theorem C.3. Linear Kemeny satisfies PMC and separability.
Proof. PMC holds because the linear Kemeny score minimizes disagreements even among non- transitive rankings, making the PMC ranking the optimal choice whenever is feasible. Separability evident the Kemeny dataset. If the same ranking minimizes the score both datasets independently. it will also minimize the score in their combination.
of ranking two datasets is simply the sum of the scores in each
Theorem C.4. Linear Kemeny does not satisfy PO or majority consistency.
Proof. Consider the scenario with 20 candidates whose feature vectors represented in the table below:
Candidate
Feature Vector
(2000000,0,00 0, 0,
2
(0, 2,000000,,,
3
200000, 0,0,0,0,0
(0, 100000, 0,
5
(0, 2,0000,0,000.00
(0,0, 0, 20000, 0,000000000,000000
7
(0. O. 10000,0.000
(0, O, O, 20000,
9
0, O,
(0,0, O, 1000, 1000,
11
0,0,0,00,
13
1,0,0,
00,0,0,0,0,2000, 200,
15
00.0.0.0.0,20.0)
0,0,0,0,0,,101100
17
(0.0.0.0.0.0,200
18
(0,0, 0,
19
(1,0,00 0.
20
(2, 0, 0,
25

---

Each vector is constructed such that candidates are prioritized based on the magnitude of their first non-zero entry, leading a natural ordering within grouped subsets: {1,2] {3, 4,5) >
[6. 7.8) > (9. 10, 1 > {12, 13, 14) > (15, 16, 17) > (18, 19, 20}. We will have six voters, with rankings induced by the parameter vectors described below.
Voter
Parameter Vector
U1
(2, 1, 7, 5, 4,3) [3 2,
U/
6,7,6,544
V3
4,3,2,1,7,66
04
15,43,2,10 1,7,,,77,66
V5 (6, 5, 4, 1,7
16
(7,6,
17,6,5,4
3,
Each voter ranks candidates within the group in increasing order except for single reversed group. For instance, 21 ranks candidates as 5 > 4 > 3 and so forth. Under this setup, no param- eter vector 0 can create ranking that satisfies all voters' preferences due to the cyclic nature and individual group preferences.
We can check that linear Kemeny rule outputs ranking in which candidate 2 is ranked above 1. From this analysis, we also conclude that the rules does not satisfy majority consistency either. C
A possibly easy fix the problem that linear Kemeny does not satisfy PO would be to enforce the PO criterion, as we did for the LCPO, i.e., to restrict to parameter vectors that respect PO. However, show that if we do that, then linear Kemeny subject to PO does not satisfy separability anymore.
Theorem C.5. Linear Kemeny subject PO violates separability and majority consistency.
Proof. First, consider set of candidates and profile similar to the one that is given in the proof of Theorem C.4. When we restrict to reward functions that 1 above 2, then we can check that Linear Kemeny subject to PO outputs generality, assume that outputs the ranking of i1.
of the rankings that are in the input profile. Without loss of
Second, consider the same set of candidates and three voters, with rankings induced by the following parameter vectors:
Voter
Parameter Vector
7,,,,7,6,5,443
02
(2, 7,1,7,6,5,4.8
2/
6,7,6,5,,433
In this case, Linear Kemeny subject to PO outputs the ranking of v/ which is the same with this of voter U1.
When the two profiles are combined, then we do not anymore restrict on rankings in which is above 2, since 1 does not Pareto dominates 2 anymore. Then, we can check that linear Kemeny subject to PO outputs a different ranking than before in which is ranked above 1. From this example, we see that linear Kemenery subject PO still violates majority consistency.
C.3 Leximax Plurality
Plurality is probably the most ubiquitous voting rule in the world. Its ranking variant ranks the can- didates in decreasing order with respect to their plurality scores. The plurality score of candidate equal to the number her appearances the first position. This rule is known to satisfy several axioms but in linear social choice cannot be directly applied, not all rankings feasibly.
Similarly to leximax Copeland, we define Leximax Plurality as follows. ranks first the candidate with the highest plurality score that can be ranked first under some parameter vector. Subject to this first position, it ranks second the candidate with the highest plurality score that can feasibly be ranked second, and on, until all the positions are filled.
26

---

Theorem C.6. Leximax Plurality satisfies majority consistency, winner monotonicity and separa- bility.
Proof. Note that leximax Plurality always returns a ranking in which the candidate with the highest plurality score is ranked first, since there exists at least one feasible ranking in which this candidate is ranked first. From this observation, we immediately see that leximax Plurality satisfies majority consistency.
Now, suppose that on input profile the rule outputs ranking such that candidate is ranked first. This means that a has the highest plurality score. Now, consider profile N' which is similar to with the only exception being ranking in which a is ranked in higher position. It is clear that continues to have the highest plurality score and therefore leximax Plurality will output a ranking in which a is ranked first. Therefore, winner monotonicity is satisfied..
remains prove that the rule satisfies separability. Suppose that under two different profiles m and T2, the rule outputs a, and under the aggregated profile it outputs o'. We will show that o'. One main observation that if candidate a has higher plurality score than candidate b under both and T2, then a has a higher plurality score than under as well. We will show the desired property by induction on the positions of the ranking o. Start from the first position in which say candidate a is ranked first. From above, we know that a has the highest plurality score under both गं and T2. which remains
in IT, and therefore to position - 1, and o' are similar and denote with a' the candidate that is ranked at position of a. We denote by S1, S2 and S3 the set of candidates that are not ranked among the first positions in and have higher plurality score than a' under T1, T2, and π3 respectively. Since, a' is ranked at the (-th postion in a, we get that, subject to the fixed first position, no candidate in S U S2 can be ranked at the (-th position. The theorem follows by noticing that S3 S S, U S2, which follows from the main observation above.
ranked first in a'. Now, assume that up
27


Reviews:
[{"review_id": "U8hFoSGTDr", "reviewer": "Reviewer_TLca", "summary": "The paper proposes an axiomatic approach to study preference aggregation for AI alignment. Inspired by works in social choice theory, the authors investigate a paradigm that they call linear social choice where preferences are representable by a linear model. In this context, they notably prove that if the linear rank aggregation rule minimizes some natural loss function (like the one induced by the Bradley-Terry model), then it cannot satisfy Pareto optimality. To circumvent this issue, the authors propose a variation of Copeland rule that outputs a ranking representable by a linear model.", "questions": "1) Could the authors comment on how only trying to recover part of the full ranking would impact their results?\n\n2) Could you the authors comment on their proposed rule could be implemented in practice?", "limitations": "The current discussion is adequate.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The paper investigates an important research question with a theoretically-founded approach.\n\nThe obtained results seem to be novel as far as I know. The failure of PO by minimizing a loss points to a strong limitation of the current approaches using human feedback.\n\nThe paper is well and clearly written. I notably appreciate the footnotes, comments, and connections with other works that the authors make.", "weaknesses": "I feel that the linear social choice paradigm may be too restrictive. I believe that the authors focus on linear models, because this is indeed a natural machine learning model. However, I don't think it is necessary to assume that the rankings of voters (i.e., humans in AI alignment) have to be linearly representable. In my opinion, the paper would be stronger if the results were presented without this latter assumption.\n\nThere are some gaps between the setting in machine learning (e.g., RLHF) and social choice theory. As the authors mention, in the latter, one usually observes pairwise comparisons instead of rankings. In addition, I think in the latter, one may not be interested to recover the full ranking, but only part of it, e.g., in RLHF, as the agent is trained, the reward approximator only needs to be good in the region of state-action pairs visited by a good policy. Could the authors comment on how this would impact their results?\n\nThe proposed social choice-based rule seems to me to be a bit artificial and only created to enforce Pareto optimality. It is not clear if such rule could easily be implemented in RLHF for instance and obtained via learning. For instance, in RLHF, this rule would require to consider all trajectories, which is impractical for any complex problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Could the authors comment on how only trying to recover part of the full ranking would impact their results?\n\nWe believe our work addresses this concern. The prompt/response datasets are derived from sampling an LLM, ensuring the corresponding feature vectors are already in a reasonable region of feature space simply by virtue of being in the dataset. Our axioms are designed to guarantee good performance specifically on these vectors.\n\nWe could have instead chosen even stronger notions requiring the conditions to hold across the entire feature space. For instance, PO could be defined such that for *any* two feature vectors $\\mathbf{x}, \\mathbf{x}' \\in \\mathbb{R}^d$, if all voters prefer $\\mathbf{x}$ to $\\mathbf{x}'$, then $\\theta^*$ should as well. This is (i) impossible to achieve with trivial counterexamples, and (ii) unnecessarily stringent for precisely the reasons you mentioned.\n\nThis idea extends to RLHF beyond LLMs, as long as the dataset defines a reasonable region for the reward approximator to perform well in.\n \n> The proposed social choice-based rule seems to me to be a bit artificial and only created to enforce Pareto optimality. It is not clear if such rule could easily be implemented in RLHF for instance and obtained via learning. For instance, in RLHF, this rule would require to consider all trajectories, which is impractical for any complex problem. [...] Could you the authors comment on their proposed rule could be implemented in practice?\n\nWe believe that the problem you're alluding to may not be an issue. In our desired use case, all \"trajctories\" are sequences of tokens which can in principle be embedded into a fixed-dimension feature space. In existing implementations, we are given a dataset of pairwise comparisons over token sequences which are interpreted as feature vectors. In common variants of RLHF, a reward function is learned to maximize the Bradley-Terry (BT) likelihood over a dataset of such comparisons. LCPO is just an alternative to this step, where instead of maximizing likelihood we solve a small number of linear programs. Just as in the case of BT, LCPO can be used on a dataset which contains only a small subset of possible pairwise comparisons. Once the reward function is obtained using LCPO, it can be used for reinforcement learning in precisely the same way as the standard RLHF pipeline.\n\n> I feel that the linear social choice paradigm may be too restrictive. I believe that the authors focus on linear models, because this is indeed a natural machine learning model. However, I don't think it is necessary to assume that the rankings of voters (i.e., humans in AI alignment) have to be linearly representable. In my opinion, the paper would be stronger if the results were presented without this latter assumption.\n\nWhile the linearity assumption is admittedly a limitation, we note that linear reward models are more general than they may first appear, as the \"feature vectors\" can be output embeddings of a pretrained LLM (and we just learn a linear layer of a reward model from pairwise comparisons). Consequently, even a linear model can in principle encode highly non-linear characteristics of the raw input (e.g., text).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2LAA2FteOp", "reviewer": "Reviewer_xjPu", "summary": "The paper presents a axiomatic social choice framework for the problem of doing RLHF on group preferences. It shows that classical RLHF (and indeed a wider class of similar methods) violates the Pareto Optimality and Pairwise Majority Consistency axioms, and shows (via explicit construction) that there are mechanisms that satisfy both axioms along with two other axioms. (To simplify the model, the space of preferences is assumed to be implementable via linear classification.)", "questions": "- Do you think the PO and PMC axioms (possibly along with majority consistency, winner monotonicity etc.) are in any sense the \"gold standards\"? Could there be other similarly reasonable axioms that are contradictory with PO/PMC? I'm asking this because I have the intuition (which could be wrong) that an Arrow-like impossibility result would also haunt the linear social choice setting; elaboration in the limitations section.", "limitations": "I highly appreciate the detailed discussion of limitations and future directions in the Discussion section of the paper, and I agree with most of the points there. I have the following two additional remarks, which are meant not as critiques but as suggestions for exploration.\n\n1. **(Non)existence of a gold standard in linear social choice**\n    - Let's look at Theorem 3.1 first. If the RLHF method decide to overturn a perfect consensus on one pair with a tiny margin, in order to much more significantly reduce loss on a divisive pair (which is possible due to strict convexity), this actually seems desirable, despite violating PO.\n        - One could counter that whether the margin is small or large does not matter when what we care about the outcome is only the ordering. However, the exact margins (<> the exact reward values) do matter a lot in practice, where they indirectly (in RLHF) or directly (in DPO) determines what probabilities to assign to each response (as opposed to merely a ranking relation between the responses).\n    - In general, I suspect there is some arrow-like impossibility result in this space, where all the desirable properties just cannot be met at the same time. It's unclear which among the conflicting properties (somewhere among them are PO and PMC, and somewhere else is \"prioritize preference violations with larger margins\", with many others) are the most important.\n    - This intuition seems to be confirmed by the LCPO construction, which introduces rather arbitrary requirements (namely hard-coding the PO rule into the LCPO algorithm) in order to satisfy PO. \n2. **Human evaluations and human subject experiments**\n    - I suspect that human evaluation (e.g. letting human subjects judge the fairness of preference aggregation outcomes) could be an equally, if not more, important criteria for preference aggregation mechanisms than formal axioms are, given that (1) it's unclear which formal principles are more important than others and (2) these principles could be in conflict with each other (as in Arrow's theorem).\n    - This could be used to evaluate both aggregation mechanisms (does the outcomes align with human judgment?) and axioms (is human judgment in line with this axiom in general? If not, why, and who is right?). \n    - Here, the line between computer science and cognitive science seems to be dissolving.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "**High importance and novelty**\n- LLMs, and also AI systems in general, are expected to have large societal impact now and in the future. In light of this expectation, how to make sure model policies fairly represent the welfare of all stakeholders is important. This question, to my knowledge, has not received sufficient analysis except in this work and some of its concurrent works.\n\n**Flawless construction of the theoretical framework**\n- The theoretical setup seems flawless, covering exactly all the fundamental components of the problem, and in a very elegant manner.", "weaknesses": "I have some suggestions for improvement/future work, but I don't feel like they count as \"weaknesses\" *per se*, since those are very high standards which I don't feel like a normal conference paper would be held up to. I am instead putting those suggestions in the limitations section.\n\nAlso, please note that I did not check the proofs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your discussion of limitations. You raise excellent points on the challenges here (and some relate to discussions we have had amongst ourselves!). With regard to your direct questions:\n\n> Do you think the PO and PMC axioms (possibly along with majority consistency, winner monotonicity etc.) are in any sense the \"gold standards\"? \n\nWe view both PO and PMC as relatively minimal requirements, more so than majority consistency and winner monotonicity. For example, PO (at least in traditional social choice) is a basic property that is satisfied by essentially all natural rules. Nevertheless, we agree that many other axioms can be considered, and it is indeed not self-evident that enforcing PO outweighs the tradeoff of not respecting large margins. We do not view our axioms and results as the final word. Rather, we hope the paper offers a starting point for having such conversations.\n\n> Could there be other similarly reasonable axioms that are contradictory with PO/PMC? \n\nThis seems quite plausible. We were quite surprised by the fact that PO and C1 are incompatible given how easy they are to achieve in traditional social choice. It does suggest that there may be other strong impossibilities yet to be discovered.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "e6TmcYbzhU", "reviewer": "Reviewer_6JKc", "summary": "Recent months have seen a flood of concurrent papers studying the relationship between RLHF, preference aggregation, and social choice theory. This paper joins these lines of work and studies how to aggregate diverse human preferences (in the context of RLHF) that are modeled as a random utility model (e..g., BTL). The authors adopt a social choice perspective and show that the BTL model (and similar ones) fail to satisfy basic axioms known from social choice theory. The paper then also proposes a leximax Copeland (subject to PO) rule that satisfies desirable properties such as pareto optimality and majority consistency.", "questions": "- What about non-linear reward function classes?", "limitations": "The authors address the limitations of the work adequately in Section 5.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is very well-written. \n- The studied problem is relevant and timely. \n- The authors do a good job explaining concepts from social choice theory so that the paper is also easy to read for researchers who don't have a background in computational social choice.   \n- While unsurprising, the main theoretical result that linear aggregation (using a linearly parameterized reward function) is insufficient to achieve basic axioms of \"fair\" and reasonable preference aggregation is useful and interesting.", "weaknesses": "- The assumption that for each voter the complete ranking is available is obviously unrealistic, which limits the applicability of the proposed leximax Copeland rule.  \n- I believe that this paper's practical relevance is quite limited. It is unclear how leximax Copeland could be implemented in practice. The sampling strategy over voters and candidates (prompt/responses) is far from obvious and not discussed in the paper. Any additional comments about how such a sampling strategy would look like would be appreciated. \n- In contrast to the various related works on RLHF + social choice, which provide algorithms/solutions to augment the traditional RLHF framework, this work does not provide a tractable approach to address the problem of aggregating preferences in a reasonable way.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The sampling strategy over voters and candidates (prompt/responses) is far from obvious and not discussed in the paper. Any additional comments about how such a sampling strategy would look like would be appreciated.\n\nWe believe you are referring to this passage in the discussion: \"However, the complete rankings are not necessary for computing this rule, rather, all we need to know are PO dominance relationships and majority directions. We can therefore apply the rule whenever we can determine this information at least approximately through, e.g., sampling.\"\n\nWe had the following model in mind: Each participant is shown a certain number of randomly selected pairs of candidates. We should be able to estimate all pairwise margins within a small error as long as each pair is compared at least $\\Omega(\\log m)$ times in expectation.\n\nThe only information needed to compute LCPO is for each pair of candidates in the dataset (i) which a majority of voters prefer and (ii) whether all voters have this preference. Determining these exactly is impossible with only approximate pairwise margins. However, running LCPO on the estimated margins would get an \"approximate\" LCPO winner, in the sense that the output ranking would be the winner on a profile differing on only a small fraction of voters.\n\n> What about non-linear reward function classes?\n\nThis is a great question. We first note  that linear reward models are more general than they may first appear, as the \"feature vectors\" can be output embeddings of a pretrained LLM (and we just learn a linear layer of a reward model from pairwise comparisons). Consequently, even a linear model can in principle encode highly non-linear characteristics of the raw input (e.g., text). \n\nNonetheless, expanding beyond linear reward functions is an important direction for future work. A significant challenge is that once we consdier nonconvex model classes (e.g., even small multi-layer perceptrons), they seems difficult to analyze theoretically, as we now run into an issue of local optima and computational intractability of computing globally optimal solutions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "O4OkoZO9rl", "reviewer": "Reviewer_Gde6", "summary": "Authors argue that for RLHF, the preferences are pairwise and we need to train a model that respects the preferences in aggregate which is in scope of social choice theory. Then they evaluate different aggregation methods on if they respect well established axioms. They showed that the popular TB model does not respect some axioms and came up with novel rules for reward learning.", "questions": "- could you cite the places where you obtained the axioms of social choice theory?\n- since you did not include where these axioms are from, are you missing any investigations of other axioms? If so, why did you choose the ones you investigated and why leaved the others out?", "limitations": "written in the discussion section", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- principled approach to model preferences from population, rooted in social choice theory\n- relevant topic for this conference\n- initated the filed to approach RLHF reward modeling to follow axiomatic guidance through social choice theory", "weaknesses": "- only theoretical contributions, we do not know how the theory translates to in practice, even in toy settings", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Could you cite the places where you obtained the axioms of social choice theory?\n\nWe consider canonical axioms from the social choice literature. See, for instance, \"The Handbook of Computational Soical Choice,\" Chapter 2. We are happy to add further references in a revision.\n\n> Since you did not include where these axioms are from, are you missing any investigations of other axioms? If so, why did you choose the ones you investigated and why leaved the others out?\n\nIndeed, there are a great number of axioms in the social choice literature one could consider. Our choice of PMC and PO was due to these serving as very natural starting points for this kind of investigation. In particular, Pareto optimality is viewed as one of the most fundamental properties expected of social choice rules, and is satisfied by practically all reasonable social choice rules, whereas PMC related to Condorcet consistency, one of the most extensively studied axioms. We also considered several others (see some discussion of these in Appendix B). In any case, we believe that an extensive study of other social choice axioms is an important subject for follow-up work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: After a good set of reviews, discussion, and rebuttal that involved all reviewers and the author we have arrived a recommendation of accepting this paper for NeurIPS. The paper is well written, within scope for the conference, and provides a solid theoretical contribution in the direction of LLM alignment.
Decision: Accept (spotlight)