We start by proving statement (ii). We now prove statement (iii). The last constraint is trivially satisfied. This can be easily shown by induction. 's constraint remains equal when Let's pick such a branching Moreover, observe that every edge in B is tight.

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 .

A typical solution isdirect democracywhich decides based on amajority vote, the so called "wisdom of the crowd."

Neural Information Processing Systems http://nips.cc/

Frequently,we are also interested in the scores associated with the objects to deduce the intensity of the resulting preference.

The Dirichlet measure has probability density function w.r.t. Here we first note the original result from Biggs and Guedj (2022b) that is adapted in Equation (3); since this is obtained by applying an upper bound to the inverse small-kl and an additional step, it is strictly looser than the result we give in Equation (3). Biggs and Guedj (2022b) also uses a dimension doubling trick to allow negative weights (as they consider only the binary case), which we remove here to replace the factor log(2d) by log d. B.1 Definition of the margin We here note that the definition of the margin given in Gao and Zhou (2013) and Biggs and Guedj (2022b) is slightly different from our own, leading to a scaling of the margin definition by a factor of one-half. B.2 Proof of Theorem 6 and Equation (3) For completeness we provide here short proofs of Equation (3) and Theorem 6.