Aggregating Quantitative Relative Judgments: From Social Choice to Ranking Prediction

Authors: yixuan even xu
hanrui  zhang
yu  cheng
vincent  conitzer
Venue: NeurIPS_cc_2024_Conference
Published: 2024-04-30 15:00:40

Abstract: Quantitative Relative Judgment Aggregation (QRJA) is a new research topic in (computational) social choice. In the QRJA model, agents provide judgments on the relative quality of different candidates, and the goal is to aggregate these judgments across all agents. In this work, our main conceptual contribution is to explore the interplay between QRJA in a social choice context and its application to ranking prediction. We observe that in QRJA, judges do not have to be people with subjective opinions; for example, a race can be viewed as a ``judgment'' on the contestants' relative abilities. This allows us to aggregate results from multiple races to evaluate the contestants' true qualities. At a technical level, we introduce new aggregation rules for QRJA and study their structural and computational properties. We evaluate the proposed methods on data from various real races and show that QRJA-based methods offer effective and interpretable ranking predictions.

Main paper: 
 introduction: 
 In voting theory, each voter ranks a set of candidates, and a voting rule maps the vector of rankings to either a winning candidate or an aggregate ranking of all the candidates. There has been significant interaction between computer scientists interested in voting theory and the learning-to-rank community. The learning-to-rank community is interested in problems such as ranking webpages in response to a search query, or ranking recommendations to a user (see, e.g., Liu [2009] ). Another problem of interest is to aggregate multiple rankings into a single one, for example combining the ranking results from different algorithms ("voters") into a single meta-ranking. While the interests of the communities may differ, e.g., the learning-to-rank community is less concerned about strategic aspects of voting, a natural intersection point for these two communities is a model where there is a latent "true" ranking of the candidates, of which all the votes are just noisy observations. Consequently, it is natural to try to estimate the true ranking based on the received rankings, and such an estimation procedure corresponds to a voting rule. (See, e.g., Young [1995] ; Conitzer and Sandholm [2005] ; Meila et al. [2007] ; Conitzer et al. [2009] ; Caragiannis et al. [2013] ; Soufiani et al. [2014] ; Xia [2016] , and Elkind and Slinko [2015] for an overview.)Voting rules are just one type of mechanism in the broader field of social choice, which studies the broader problem of making decisions based on the opinions and preferences of multiple agents. Such opinions are not necessarily represented as rankings. For example, in judgment aggregation (see Endriss [2015] for an overview), judges assess whether certain propositions are true or false, and the goal is to aggregate these judgments into logically consistent statements. The observation that other types of input are aggregated in social choice prompts the natural question of whether analogous problems exist in statistics and machine learning (as is the case with ranking aggregation).In this paper, we focus on a relatively new model in social choice, the quantitative judgment aggregation problem [Conitzer et al., 2015 [Conitzer et al., , 2016]] . In this problem, the goal is to aggregate relative quantitative judgments: for example, one agent may value the life of a 20-year-old at 2 times the life of a 50-year-old (say in the context of self-driving cars making decisions) [Noothigattu et al., 2018] ; another example could be that an agent judges that "using 1 unit of gasoline is as bad as creating 3 units of landfill trash" (in a societal tradeoff context) [Conitzer et al., 2016] . Quantitative judgment aggregation has been considered in the area of automated moral decision-making, where an AI system may choose a course of action based on data about human judgments in similar scenarios.An important conceptual difference between this work and previous studies on quantitative judgment aggregation is that we observe that relative "judgments" can be produced by a process other than a subjective agent reporting them, which is the standard assumption in social choice. To illustrate, consider a race in which contestant A finishes at 20:00 and contestant B at 30:00. In this race, the "judgment" is that A is 10:00 faster than B. This key observation allows us to bring the social choice community and the learning-to-rank community closer together, by applying existing social choice formulations of quantitative judgment aggregation to the problem of ranking prediction.Under this new perspective, the formulation of quantitative judgment aggregation can be applied a set of new scenarios, like ranking contestants using "judgments" from past races, or ranking products based on "judgments" from their sales data. We are interested in aggregating such "judgments" from past data, and using them to predict future rankings. Given the different motivations, some important aspects in a social choice context are less important in our setting. For example, social choice is often concerned with agents strategically misreporting, but this is less relevant in our setting because the "judgments" considered in our setting are not strategic.Our Contributions. We summarize our main contributions below: (1) Conceptually, we apply social-choice-motivated solution concepts to the problem of ranking prediction, which creates a bridge between research typically done in the social choice and the learning-to-rank communities. (2) We pose and study the problem of quantitative relative judgment aggregation (QRJA) in Section 3, which generalizes models from previous work [Conitzer et al., 2015 [Conitzer et al., , 2016]] . (3) Theoretically, we focus on ℓ p QRJA, an important subclass of QRJA problems. We (almost) settle the computational complexity of ℓ p QRJA in Section 4, proving that ℓ p QRJA is solvable in almost-linear time when p ≥ 1, and is NP-hard when p < 1. (4) Empirically, we focus on ℓ 1 and ℓ 2 QRJA. We conduct extensive experiments on a wide range of real-world datasets in Section 5 to compare the performance of QRJA with several other commonly used methods, showing the effectiveness of QRJA in practice.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: The main contributions are summarized at the end of the introduction.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 be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
motivating examples: 
 To better motivate our study and help readers understand the problem, we first consider simple mean/median approaches for aggregating quantitative judgments and illustrate their limitations through three examples.Example 1. When each race has some common "difficulty" factor (e.g. how hilly a marathon route is), if a contestant only participates in the "easy" races (or only the "hard" races), simply taking the median or mean of historical performance will return biased estimates, as illustrated in Figure 1 .Contestant ⧹ Race Boston New York Chicago Alice 4:00:00 4:10:00 3:50:00 Bob 4:11:00 4:18:00 4:01:00 Charlie 4:09:00Figure 1 : Bob finishes earlier than Charlie in the Chicago race, which suggests that Bob runs marathons faster than Charlie. However, if we simply calculate the mean or median of all available data, Charlie's mean/median finishing time will be faster than Bob's. This is because, Charlie participated only in the Chicago race, where conditions were more favorable.Example 2. Suppose past data shows that Alice has beaten Bob in some race, and Bob has beaten Charlie in another race. If we have never seen Alice and Charlie competing in the same race, we may want to predict that Alice runs faster than Charlie (see Figure 2 ). However, when comparing Alice and Charlie, simple measures like median and mean effectively ignore the data on Bob, even though Bob's data can provide useful information for this comparison.Contestant ⧹ Race Boston New York Chicago Alice 4:10:00 Bob 4:11:00 4:18:00 4:01:00 Charlie 4:09:00Figure 2 : The same results as in Figure 1 , but with some data missing. If we only look at the data on Alice and Charlie, it is difficult to judge who is the faster runner. If anything, Charlie appears to be slightly faster. However, if we know Bob's results in these races, then transitivity suggests that Alice runs faster than Charlie.Example 3. When the variance of the races' difficulty is much higher than the variance in the contestants' performance, taking the median will essentially focus on the result of a single race (with median difficulty) and may throw away useful information as shown in Figure 3 . QRJA addresses the above issues by considering relative performance instead of absolute performance. More specifically, each race provides a judgment of the form "A runs faster than B by Y minutes" for every pair of contestants (A, B) that participated in this race.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: We briefly discuss the limitations of our work in Section 7.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a 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 authors should reflect on 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 a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
problem formulation: 
 In this section, we formally define the Quantitative Relative Judgment Aggregation (QRJA) problem.We start with the definition of its input. Definition 1 (Quantitative Relative Judgment). For a set of n candidates N = {1, . . . , n}, a quantitative relative judgment is a tuple J = (a, b, y), denoting a judgment that candidate a ∈ N is better than candidate b ∈ N by y ∈ R units.The input of QRJA is a set of quantitative relative judgments to be aggregated. We model the aggregation result as a vector x ∈ R n , where x i is the single-dimensional evaluation of candidate i.The aggregation result should be consistent with the input judgments as much as possible, i.e., for a quantitative relative judgment (a, b, y), we want |x a -x b -y| to be small. We use a loss function f (|x a -x b -y|) to measure the inconsistency between the aggregation result and the input judgments.The aggregation result should minimize the weighted total loss. Formally, we define QRJA as follows.Definition 2 (Quantitative Relative Judgment Aggregation (QRJA)). Consider n candidates N = {1, . . . , n} and m quantitative relative judgments J = (J 1 , . . . , J m ) with weights w = (w 1 , . . . , w m ) where J i = (a i , b i , y i ). The quantitative relative judgment aggregation problem with loss function f : R ≥0 → R ≥0 asks for a vector x ∈ R n that minimizesm i=1 w i f (|x ai -x bi -y i |).Previous work [Conitzer et al., 2015 [Conitzer et al., , 2016;; Zhang et al., 2019] studied a special case of QRJA where f (t) = t. In this work, we broaden the scope and study QRJA with more general loss functions. We first note that when the loss function f is convex, QRJA can be formulated as a convex optimization problem. Consequently, one can use standard convex optimization methods like gradient descent or the ellipsoid method to solve QRJA in polynomial time.However, general-purpose convex optimization methods are often very slow when the numbers of candidates n and judgments m are large. For this reason, we focus on ℓ p QRJA, an important subclass of QRJA problems with loss function f (t) = t p . Our theoretical analysis (almost) settles the computational complexity of ℓ p QRJA for all p > 0. We show that ℓ p QRJA is solvable in almost-linear time when p ≥ 1, and is NP-hard when p < 1. Our experiments focus on comparing ℓ 1 and ℓ 2 QRJA with various baselines in social choice and machine learning. We conduct extensive experiments on a wide range of real-world data sets.4 Theoretical Aspects of ℓ p QRJAIn this section, we study the theoretical aspects of ℓ p QRJA, providing a clean and (almost) tight characterization of the computational complexity of ℓ p QRJA for different values of p. Recall that n is the number of candidates and m is the number of judgments. Note that n ≤ 2m.In Section 4.1, we prove that for all p ≥ 1, ℓ p QRJA can be solved in almost-linear time O(m 1+o(1) ).In Section 4.2, we show that when p < 1, ℓ p QRJA is NP-hard and there is no FPTAS 1 unless P = NP. Additionally, in Appendix A, we show that if 1 ≤ p ≤ 2 and m ≫ n, we can reduce m to O(n) while incurring a small error. 24.1 ℓ p QRJA in Almost-Linear Time When p ≥ 1We first show that when p ≥ 1, ℓ p QRJA can be solved in O(m 1+o(1) ) time, i.e., in time almost linear in the size of the input. Note that to solve ℓ p QRJA with p ≥ 1 in polynomial time, one can formulate the problem as an ℓ p regression problem and apply general-purpose techniques for ℓ p regression, e.g., [Bubeck et al., 2018; Adil et al., 2024] . However, these methods would result in a running time that is Ω(m + n ω ), where ω ≥ 2 is the matrix multiplication exponent. This is significantly slower than almost-linear time. Our approach leverages the additional structure of the QRJA problem, and utilizes the recent advancements in faster algorithms for (directed) maximum flow [Chen et al., 2022] . Theorem 1. Let p ≥ 1 be an absolute constant. Consider ℓ p QRJA in Definition 2 with loss function f (t) = t p . Assume all input numbers are polynomially bounded in m. We can solve ℓ p QRJA in time O(m 1+o(1) ) with exp(-log c m) additive error for any constant c > 0.Proof of Theorem 1: We first prove the theorem for p > 1. We will prove the p = 1 case in Appendix B.1. Let S input = (n, m, (w i ) m i=1 , (y i ) m i=1 ). We assume m is sufficiently large, and that c is a sufficiently large constant such that ∀v ∈ S input , either v = 0 or 1/m c < |v| < m c . Consider an ℓ p QRJA instance (N, J, w) where J = (J 1 , . . . , J m ) and J i = (a i , b i , y i ), we construct a matrix A ∈ R m×n and a vector z ∈ R m as follows:EQUATIONGiven A and z, the ℓ p QRJA problem can be formulated asmin x∈R n m i=1 w i |x ai -x bi -y i | p = min x∈R n ∥Ax -z∥ p p ,We will show how to findx in time O(m 1+o(1) ) such that ∥Ax -z∥ p ≤ min x * ∥Ax * -z∥ p + exp(-log 2c m).We first write the optimization asEQUATIONThe Lagrangian dual of (2) ismin x∈R n ,s∈R m max f ∈R m ∥s∥ p + f ⊤ (s -(Ax -z)) .1 Fully Polynomial-Time Approximation Scheme. 2 The O(•) notation hides logarithmic factors in its argument.Note that s = Axz is enforced; otherwise the inner maximization problem is unbounded. Let ∥•∥ q be the dual norm of ∥•∥ p , i.e., 1 p + 1 q = 1. (So q > 1.) By strong duality,EQUATIONThe last step follows from the fact that the value of (mins∈R m ∥s∥ p + f ⊤ s) is 0 if ∥f ∥ q ≤ 1 and -∞ otherwise, and that max x∈R n f ⊤ Ax is unbounded if A ⊤ f ̸ = 0.We will show that the dual program (3) can be solved near-optimally in almost-linear time (Lemma 1), and given a near-optimal dual solution f ∈ R m , a good primal solution x ∈ R n can be computed in linear time (Lemma 2). Theorem 1 follows directly from Lemmas 1 and 2.Lemma 1. We can find a feasible solution f ∈ R m of (3) in time O(m 1+o(1) ) with additive error exp(-log 6c m).Proof of Lemma 1: Consider the following problem, which moves the norm constraint of (3) into the objective:EQUATION(4) is closely related to ℓ p norm mincost flow. Recent breakthrough in mincost flow [Chen et al., 2022] showed that a feasible solution f † of (4) within error exp(-log 13c m) can be computed in O(m 1+o(1) ) time.Suppose f † q ≥ exp(-log 7c m), which we prove later. Notice that f † is a solution within error exp(-log 13c m) ofmax f ∈R m ,A ⊤ f =0,∥f ∥ q =∥f † ∥ q f ⊤ z. Choosing f = f † / f † q satisfies Lemma 1.To lower bound f † q , let f * be the optimal solution of (3). When f * ⊤ z ≥ 3, because the optimal value of (4) is at least f * ⊤ z -1 and f † is near-optimal for (4), we have f † ⊤ z ≥ f * ⊤ z -2 and thus f † q ≥ 1/3. When f * ⊤ z < 3, we will show f † ⊤ z ≥ exp(-log 6c m), so f † q ≥ exp(-log 7c m).To show f † ⊤ z ≥ exp(-log 6c m), we only need to show that the optimal value of (4) is at least exp(-log 5c m). We can assume w.l.o.g. that f * ⊤ z > exp(-log 3c m), otherwise there is a primal solution x almost consistent with all judgments, which is easy to approximate. Note that when scaling down f * , ∥f * ∥ q q scales faster than f * ⊤ z. Let f ′ = kf * with k = exp(-log 4c m). We havef ′ ⊤ z -∥f ′ ∥ q q = k(f * ⊤ z) -k q > exp(-log 5c m), where the last step assumes that m is sufficiently large, in particular log c m > max{ 2 q-1 , q + 1}. Lemma 2. Given a solution f of (3) that satisfies Lemma 1, we can compute a vector x ∈ R n in time O(m) such that ∥Ax -z∥ p ≤ minx * ∥Ax * -z∥ p + exp(-log 2c m).Proof of Lemma 2: We assume w.l.o.g. that ∥f ∥ q = 1.EQUATION)Because f is a solution of (3) within error exp(-log 6c m), and max ∥f ∥ q v ∥f ∥ q -v q ∥f ∥ q q is achieved when ∥f ∥ q = 1, we know that f is a solution of (5) within error exp(-log 5c m).The first-order optimality condition of (5) guarantees that ∇Φ(f ) is very close to a potential flow. That is, we can find in O(m) time a vector x ∈ R n , such that ∥Ax -∇Φ(f )∥ ∞ ≤ exp(-log 3c m). For this x,∥Ax -z∥ p ≤ ∥∇Φ(f ) -z∥ p + ∥Ax -∇Φ(f )∥ p = v + ∥Ax -∇Φ(f )∥ p ≤ v + m ∥Ax -∇Φ(f )∥ ∞ ≤ v + exp(-log 2c m) ≤ min x * ∈R n ∥Ax * -z∥ p + exp(-log 2c m).The last inequality uses that v = f ⊤ z is a lower bound on the optimal value because f is a feasible dual solution.4.2 NP-Hardness of ℓ p QRJA When p < 1In this section, we show that ℓ p QRJA is NP-hard when p < 1 by reducing from Max-Cut. Note that in this case, the loss function f (t) = t p is no longer convex. Definition 3 (Max-Cut). For an undirected graph G = (V, E), Max-Cut asks for a partition of V into two sets S and T that the number of edges between S and T is maximized.Reduction from Max-Cut to ℓ p QRJA. Given a Max-Cut instance on an undirected graph G = (V, E), let n = |V |, m = |E|, w 2 = 2n 1-p + 1, and w 1 = nw 2 + 1.We will construct an ℓ p QRJA instance with n + 2 candidates V ∪ {v (s) , v (t) } and O(n + m) quantitative relative judgments. Specifically, we add the following judgments:• (v (t) , v (s) , 1) with weight w 1 .• (v (s) , u, 0) with weight w 2 for each u ∈ V .• (v (t) , u, 0) with weight w 2 for each u ∈ V .• (u, v, 1), (v, u, 1) with weight 1 for each (u, v) ∈ E.In Appendix B.2, we will prove that the Max-Cut instance has a cut of size at least k if and only if the constructed ℓ p QRJA instance has a solution with loss at most nw 2 + 2(m -k) + k2 p , which implies the following hardness result. Theorem 2. For any p < 1, there exists a constant c > 0 such that it is NP-hard to approximate ℓ p QRJA within a multiplicative factor of 1 + c n 2 .Theorem 2 implies that there is no (multiplicative) FPTAS for ℓ p QJA when p < 1 unless P = NP. This is because if a (1 + ε) solution can be computed in poly(m, 1/ε) time, then choosing ε = c n 2gives a poly-time algorithm for Max-Cut.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes] Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification: The code and data are provided in the supplemental materials, including an automated test script to reproduce the experimental results stated in the paper.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experiments: 
 We conduct experiments on real-world datasets to compare the performance of ℓ 1 and ℓ 2 QRJA with existing methods. We focus on ℓ 1 and ℓ 2 QRJA because the almost-linear time algorithm for general values of p ≥ 1 relies on very complicated galactic algorithms for ℓ p norm mincost flow [Chen et al., 2022] . Although general-purpose convex optimization methods can also be used to solve ℓ p QRJA, they are not efficient enough for some of the large-scale datasets we use. All experiments are done on a server with 56 CPU cores and 504G RAM. The experiments in Section 5 and Appendices A and C take around 2 weeks in total to run on this server. No GPU is used. All source code is available at https://github.com/YixuanEvenXu/quantitative-judgment-aggregation.Datasets. We consider types of contests where events are reasonably frequent (so it makes sense to predict future events based on past ones), and contest results contain numerical scores in addition to rankings. Specifically, we use the four datasets listed below. We include additional experiments on three more datasets in Appendix C, and the copyright information of the datasets in Appendix E.• Chess. This dataset contains the results of the Tata Steel Chess Tournament (https: //tatasteelchess.com/, also historically known as the Hoogovens Tournament or the Corus Chess Tournament) from 1983 to 20233 . Each contest is typically a round-robin tournament among 10 to 14 contestants. A contestant's numerical score is the contestant's number of wins in the tournament. There are 80 contests and 408 contestants in this dataset.• F1. This dataset contains the results of Formula 1 races (https://www.formula1.com/) from 1950 to 2023. In each contest, we take all contestants who complete the whole race. There are around 7 such contestants in each contest. A contestant's numerical score is the negative of his/her finishing time (in seconds). There are 878 contests and 261 contestants in this dataset.• Marathon. This dataset contains the results of the Boston and New York Marathons from 2000 to 2023. We use the data from https://www.marathonguide.com/, which publishes results of all major marathon events. Each contest usually involves more than 20000 contestants. We take the 100 top-ranked contestants in each contest as our dataset. A contestant's numerical score is the negative of that contestant's finishing time (in seconds). There are 44 contests and 2984 contestants.• Codeforces. This dataset contains the results of Codeforces (https://codeforces.com), a website hosting frequent online programming contests, from 2010 to 2023 (Codeforces Round 875). We consider only Division 1 contests, where only more skilled contestants can participate. Each contest involves around 700 contestants. We take the 100 top-ranked contestants in each contest as our dataset. A contestant's numerical score is that contestant's points in that contest.There are 327 contests and 5338 contestants in total in this dataset.Evaluation Metrics. For all the datasets we use, contests are naturally ordered chronologically.We use the results of the first i -1 contests to predict the results of the i-th contest. We apply the following two metrics to evaluate the prediction performance of different algorithms.• Ordinal Accuracy. This metric measures the percentage of correct relative ordinal predictions.For each contest, we predict the ordinal results of all pairs of contestants that (i) have both appeared before and (ii) have different numerical scores in the current contest. We compute the percentage of correct predictions.• Quantitative Loss. This metric measures the average absolute error4 of relative quantitative predictions. For each contest, we predict the difference in numerical scores of all pairs of contestants that have both appeared before. We then compute the quantitative loss as the average absolute error of the predictions. We normalize this number by the quantitative loss of the trivial prediction that always predicts 0 for all pairs.Implementation. We have implemented both ℓ 1 and ℓ 2 QRJA in Python. We use Gurobi Gurobi Optimization, LLC [2023] and NetworkX Hagberg et al. [2008] to implement ℓ 1 QRJA and the least-square regression implementation in SciPy [Jones et al., 2014] to implement ℓ 2 QRJA. To transform the contest standings into a QRJA instance, we construct a quantitative relative judgment J = (a, b, y) for each contest and each pair of contestants (a, b) with y being the score difference between a and b in that contest. We set all weights to 1 to ensure fair comparison with benchmarks.Benchmarks. We evaluate ℓ 1 and ℓ 2 QRJA against several benchmark algorithms. Specifically, we consider the natural one-dimensional aggregation methods Mean and Median, social choice methods Borda and Kemeny-Young, and a common method for prediction, matrix factorization. We describe how we apply these methods to our setting below. • Mean and Median. For every contestant in the training set, we take the mean or median of that contestant's scores in training contests. We then make predictions based on differences between these mean or median scores. In one-dimensional environments like ours, means and medians are considered to be among the best imputation methods for various tasks (see, e.g., Engels and Diehr, 2003, Shrive et al., 2006 ). • The Borda rule. The Borda rule is a voting rule that takes rankings as input and produces a ranking as output. We use a normalized version of the Borda rule. The i-th ranked contestant in contest j receives 1 -2(i-1) nj -1 points, where n j is the number of contestants in the contest. The aggregated ranking result is obtained by sorting the contestants by their total number of points.• The Kemeny-Young rule. [Kemeny, 1959; Young and Levenglick, 1978; Young, 1988] . The Kemeny-Young rule is a voting rule that takes multiple (partial) rankings of the contestants as input and produces a ranking as output. Specifically, it outputs a ranking that minimizes the number of disagreements on pairs of contestants with the input rankings. Finding the optimal Kemeny-Young ranking is known to be NP-hard Bartholdi et al. [1989] . In our experiments, we use Gurobi to solve the mixed-integer program formulation of the Kemeny-Young rule given in Conitzer et al. [2006] . As this method is still computationally expensive and can only scale to hundreds of contestants, for each contest we predict, we only keep the contestants within that specific contest and discard all other contestants to run Kemeny-Young. • Matrix Factorization (MF). Matrix factorization takes as input a matrix with missing entries and outputs a prediction of the whole matrix. Every row is a contestant and every column is a race. The score of a contestant in a race is the entry in the corresponding row and column. We implement several variants of MF and report results for one variant (Koren et al. [2009] ), as other variants have comparable or worse performance. For implementation details and other variants, see Appendix C.4.Many other, related approaches deserve mention in this context. But we do not include them in the benchmarks because they do not exactly fit our setting or motivation. For example, the seminal Elo rating system Elo [1978] as well as many other methods Maher [1982] ; Karlis and Ntzoufras [2008] ; Guo et al. [2012] ; Hunter and others [2004] can all predict the results of pairwise matches in, e.g., chess and football. However, they are not originally designed for predicting the results of contests with more than two contestants.The complete experimental results of all algorithms on the four datasets are shown in Fig. 4 . Note that Borda and Kemeny-Young do not make quantitative predictions, so they are not included in Figs. 4b, 4d , 4f and 4h.The performance of QRJA. As shown in Fig. 4 , both versions of QRJA perform consistently well across the tested datasets. They are always among the best algorithms in terms of both ordinal accuracy and quantitative loss.The performance of Mean and Median. In terms of ordinal accuracy, Mean and Median do well on Marathon, but are not among the best algorithms on other datasets, especially on F1 (for both) and Codeforces (for Median). Moreover, for quantitative loss, they are never among the best algorithms.The performance of Borda and Kemeny-Young. Borda and Kemeny-Young do not make quantitative predictions, so we only compare them with other algorithms in terms of ordinal accuracy.As shown in Fig. 4 , Borda and Kemeny-Young perform very well on F1, but are not among the best algorithms on other datasets. By only using rankings as input, Borda and Kemeny-Young are more robust on datasets where contestants' performance varies a lot. However, they fail to utilize the quantitative information on other datasets.The performance of Matrix Factorization (MF). MF works well across the tested datasets in terms of both metrics. In all of our four datasets, it has performance comparable to QRJA. The advantage of QRJA over MF is the interpretability of its model. The variables in QRJA have clear meanings -they can be interpreted as the strength of each contestant -in contrast to the latent factors and features in MF, which are harder to interpret. Additionally, we observe in Appendix C.2 that ℓ 1 QRJA is more robust to large variance in contestants' performance than MF.Summary of experimental results. In summary, both MF and QRJA are never significantly worse than the best-performing algorithm on any of the tested datasets, unlike the other benchmark methods.QRJA additionally offers an interpretable model. This shows that QRJA is an effective method for making predictions on contest results. 
related work: 
 Random utility models. Random utility models (Fahandar et al. [2017] ; Zhao et al. [2018] ) explicitly reason about the contestants being numerically different from each other, e.g., one contestant is generally 1.1 times as fast as another. However, they are still designed for settings in which the only input data we have is ranking data, rather than numerical data such as finishing times. Moreover, random utility models generally do not model common factors, such as a given race being tough and therefore resulting in higher finishing times for everyone.Matrix completion. Richer models considered in recommendation systems appear too general for the scenarios we have in mind. Matrix completion Rennie and Srebro [2005] ; Candès and Recht [2009] is a popular approach in collaborative filtering, where the goal is to recover missing entries given a partially-observed low-rank matrix. While using higher ranks may lead to better predictions, we want to model contestants in a single-dimensional way, which is necessary for interpretability purposes (the single parameter being interpreted as the "quality" of the contestant).Preference learning. In preference learning, we train on a subset of items that have preferences toward labels and predict the preferences for all items (see, e.g., Pahikkala et al. [2009] ). One high-level difference is that preference learning tends to use existing methodologies in machine learning to learn rankings. In contrast, our methods (as well as those in previous work Conitzer et al. [2015 Conitzer et al. [ , 2016]] ) are social-choice-theoretically well motivated. In addition, our methods are designed for quantitative predictions, while the main objective of preference learning is to learn ordinal predictions.Elo and TrueSkill. Empirical methods, such as the Elo rating system Elo [1978] and Microsoft's TrueSkill Herbrich et al. [2006] , have been developed to maintain rankings of players in various forms of games. Unlike QRJA, these methods focus more on the online aspects of the problem, i.e., how to properly update scores after each game. While under specific statistical assumptions, these methods can in principle predict the outcome of a future game, they are not designed for making ordinal or quantitative predictions in their nature.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: The experiment settings in Section 5 and Appendices A and C aim to provide necessary details to understand the results. The full details are provided with the code.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a 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. 
conclusion: 
 In this paper, we conduct a thorough investigation of QRJA (Quantitative Relative Judgment Aggregation). We pose and study QRJA and focus on an important subclass of problems, ℓ p QRJA.Our theoretical analysis shows that ℓ p QRJA can be solved in almost-linear time when p ≥ 1, and is NP-hard when p < 1. Empirically, we conduct experiments on real-world datasets to show that QRJA-based methods are effective for predicting contest results. As mentioned before, the almostlinear time algorithm for general values of p ̸ = 1, 2 relies on very complicated galactic algorithms.An interesting avenue for future work would be to develop fast (e.g., nearly-linear time) algorithms for ℓ p QRJA with p ̸ = 1, 2 that are more practical, and evaluate their empirical performance.Broader Impacts. We expect our work to have a mostly positive social impact by providing an effective and interpretable method for aggregating quantitative relative judgments that can be used in applications such as predicting contest results. While for specific applications, certain desiderata may be not met by QRJA, we allow users (e.g., contest organizers) to set different weights for different judgments, which can be used to reflect the importance of different contests.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] Justification: We state in the caption of the figures that "error bars are not shown here as the algorithms are deterministic", which is appropriate information about statistical significance.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, confidence intervals, or statistical significance tests, at least for the experiments that support the 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, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. 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 or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper does not release data or models that have a high risk for misuse.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: 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?Answer: [Yes] Justification: Any existing code package used in the paper is properly cited in Section 5. The datasets used in the paper are publicly available and their copyright information are explicitly mentioned in Appendix E.Guidelines:• The answer NA means that the paper does not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 13. New Assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [Yes] Justification: The uploaded code is accompanied by a README file that documents the overall usage of it, and for each individual source file, comments are provided to explain the purpose of the file and the functions defined in it.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS 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. 
 
 Appendix: A.1 Subsampling Judgments When p ∈ [1, 2]In this section, we show that for p ∈ [1, 2], we can reduce the number of judgments while incurring a small approximation error by subsampling the input judgments.Algorithm 1 Subsampling Judgments Input: ℓ p QRJA instance (N, J, w), subsample count M ∈ N, and subsampling weights s ∈ R m . Output:ℓ p QRJA instance (N, J ′ , w ′ ). 1: Let q i ← si m j=1 sj for each i ∈ {1, 2, . . . , m}. 2: for i ∈ {1, 2, . . . , M } do 3: Sample x ∈ {1, 2, . . . , m} with probability q x . 4: Let J ′ i ← J x and w ′ i ← wx M •qx . 5: end for 6: return (N, J ′ , w ′ ).Algorithm 1 takes as input an ℓ p QRJA instance, a parameter M , and a vector s ∈ R m . It then samples M judgments from the input instance (with replacements) with probability proportional to s, and outputs a new ℓ p QRJA instance with the sampled judgments. The weight of any judgment in the output instance is divided by its expected number of occurrences in the output instance, so that the expected total weight of any judgment is preserved after subsampling.Theorem 3. Fix absolute constants p ∈ [1, 2] and ε > 0. Given any ℓ p QRJA instance (N, J, w), we can compute subsampling weights s ∈ R m in time O(m + n ω+o(1) ), where ω is the matrix multiplication exponent. For these weights s and M = O(n), Algorithm 1 with high probability outputs an ℓ p QRJA instance (N, J ′ , w ′ ) whose optimal solution is an (1 + ε)-approximate solution of the original instance.To obtain the theoretical guarantee of Algorithm 1, we use the Lewis weights mentioned in (Cohen and Peng [2015]) as vector s. Empirically, we also find that simply setting s as an all-ones vector works well in many real-world datasets (see Appendix A.2).Proof of Theorem 3: For an ℓ p QRJA instance (N, J, w), define matrix A ∈ R m×(n+1)A i,j =        p √ w i if j = a i -p √ w i if j = b i -p √ w i y i if j = n + 1 0 otherwise.The Lewis weights for this ℓ p QRJA instance is defined as the unique vector s ∈ R m such that for each i ∈ {1, 2, . . . , m},a i A ⊤ S 1-2 p A -1 a ⊤ i = s 2/p i ,where S = diag(s) and a i is the i-th row of A.The existence and uniqueness of such weights are first shown in Lewis [1978] . In Cohen and Peng [2015] , the authors show that for p ∈ [1, 2], the Lewis weights can be computed in O(nnz(A) + n ω+o(1) ) = O(m + n ω+o(1) ) time.For x ∈ R n , we haveA x 1 p p = m i=1 w i |x ai -x bi -y i | p .Thus the ℓ p QRJA loss is always equal to ∥Ax∥ p p for some x ∈ R n+1 . The theorem then follows from the ℓ p Matrix Concentration Bounds in Cohen and Peng [2015] .We also conduct experiments to test the performance of our subsampling algorithm (Algorithm 1), which speeds up the (approximate) computation of QRJA on large datasets. In the experiments, we specify the subsample rate α, let M = ⌊αm⌋ and s be an all-ones vector in Algorithm 1.Experiment setup. We run ℓ 1 and ℓ 2 QRJA with instances subsampled by Algorithm 1 on the datasets. For each α = {0.1, 0.2, . . . , 1.0}, we run ℓ 1 and ℓ 2 QRJA 10 times and report their average performance on both metrics with error bars. Due to the space constraints, we only show the results on Chess in Fig. 5 Experiment results. As is shown in Fig. 5 , with equal weights for all judgments, Algorithm 1 can reduce the number of judgments without significantly hurting the performance of ℓ 1 and ℓ 2 QRJA as long as the sampling rate α is not too small (≥ 0.4 for Chess). This shows that Algorithm 1 is a practical algorithm for subsampling judgments in QRJA. We also note that as the experiments show, ℓ 2 QRJA is more robust to subsampling than ℓ 1 QRJA. Proof of Theorem 1 (when p = 1): We proved Theorem 1 for p > 1 in Section 4.1. It remains to consider p = 1.When p = 1, the overall loss function of QRJA is a sum of absolute values of some linear terms. We can therefore formulate ℓ 1 QRJA as the following linear program (LP), as observed in [Zhang et al., 2019] : minimizem i=1 w i z + i + z - i subject to z + i ≥ x ai -x bi -y i ∀i ∈ [m] z - i ≥ y i + x bi -x ai ∀i ∈ [m] z + i ≥ 0, z - i ≥ 0 ∀i ∈ [m] x i ∈ R ∀i ∈ [n]For this LP, Zhang et al. [2019] gave a faster algorithm than using general-purpose LP solvers. Theorem 2. For any p < 1, there exists a constant c > 0 such that it is NP-hard to approximate ℓ p QRJA within a multiplicative factor of 1 + c n 2 . Recall the reduction from Max-Cut to ℓ p QRJA: Given an instance of Max-Cut with an undirected graph G = (V, E), let n = |V |, m = |E| and let w 2 = 2n 1-p + 1, w 1 = nw 2 + 1. We construct an instance of ℓ p QRJA with n + 2 candidates V ∪ {v (s) , v (t) } and O(n + m) quantitative relative judgments. Specifically, we construct the followings judgments:• (v (t) , v (s) , 1) with weight w 1 .• (v (s) , u, 0) with weight w 2 for each u ∈ V .• (v (t) , u, 0) with weight w 2 for each u ∈ V .• (u, v, 1), (v, u, 1) with weight 1 for each (u, v) ∈ E.To show validity of the reduction above, we will first establish integrality of any optimal solution. Lemma 4. Any optimal solution of the ℓ p QRJA instance described in the above reduction is integral. Moreover, all variables must be either 0 or 1 up to a global constant shift.We need an inequality for the proof of Lemma 4. Lemma 5. For any d ∈ (0,1 2 ], p ∈ (0, 1), 1 -(1 -d) p ≤ pd p . Proof of Lemma 5: Fix p ∈ (0, 1). Let f (d) = pd p -1 + (1 -d) p . We have f ′ (d) = p(pd p-1 -(1 -d) p-1 ).Note that f ′ is decreasing for d ∈ (0, 1). In other words, f is single peaked on (0, 1 2 ] and continuous at 0. Now we only have to check that f (0) ≥ 0, which is trivial, and f 1 2 ≥ 0. For the latter, let g(p) = (p + 1)0.5 p -1.g(p) ≥ 0 for p ∈ [0, 1] since g(p) is concave on [0, 1] and g(0) = g(1) = 0. The lemma then follows.We then proceed to prove Lemma 4.Proof of Lemma 4: Let x a be the potential of candidate a in ℓ p QRJA. W.l.o.g. assume that in any solution, x v (s) = 0. We first show that if x v (t) ̸ = 1, then moving it to 1 strictly improves the solution. Suppose |x v (t) -1| = d. By moving x v (t) to 1, we decrease the loss on the judgment (v (t) , v (s) , 1) by w 1 d p . For other judgments (v (t) , u) incident on v (t) , the loss increase by no more thanw 2 d p , since |(x v (t) ± d) -x u | p ≤ |x v (t) -x u | p + d p .Overall, the cost decreases by at leastw 1 d p -nw 2 d p = d p > 0.Now we show moving any fractional x u to the closest value in {0, 1} strictly improves the solution. There are two cases:• x u ∈ (0, 1). W.l.o.g. x u ∈ (1, 12 ] and we try to move it to 0 by a displacement of d = x u . The total loss on (v (s) , u, 0) and (v (t) , u, 0) decreases by w 2 (d p + (1 -d) p -1), while the total cost on judgments of form (u, v, 1) and (v, u, 1) can increase by no more than n(d p + (2 + d) p -2 p ). With Lemma 5, we see thatw 2 (d p + (1 -d) p -1) ≥ w 2 (d p -pd p ) > 2nd p ≥ n(d p + (2 + d) p -2 p ).So, there is a positive improvement from rounding x u .• x u / ∈ [0, 1]. W.l.o.g. x u < 0 and we try to move it to 0 by a displacement of d = -x u . The total loss on (v (s) , u, 0) and (v (t) , u, 0) decreases by w 2 (d p + (1 + d) p -1), while the total cost on edges of form (u, v, 1) and (v, u, 1) can increase by no more than n(d p + (2 + d) p -2 p ). Andw 2 (d p + (1 + d) p -1) ≥ w 2 d p > 2nd p ≥ n(d p + (2 + d) p -2 p ).We conclude that in any optimal solution, x v (s) = 0, x v (t) = 1, and for any u ∈ V , x u ∈ {0, 1}.Next, we present a lemma that shows the connection between solutions in the Max-Cut instance and those in the constructed ℓ p QRJA instance.Lemma 6. A Max-Cut instance has a solution of size at least k iff its corresponding ℓ p QRJA instance has a solution of loss at most nw 2 + 2(m -k) + k2 p . Moreover, with such a solution to the ℓ p QRJA instance, one can construct a Max-Cut solution of the claimed size.Proof of Lemma 6: Given a Max-Cut solution (S, T ) of size at least k, setting the potentials of the vertices in S and T to be 0 and 1 respectively gives an ℓ p QRJA solution with loss at mostnw 2 + 2(m -k) + k2 p .Given a ℓ p QRJA solution of loss at most nw 1 + 2(m -k) + k2 p , we first round the solution to the form stated in Lemma 4. This improves the solution. The two vertex setsU = {u ∈ V | x(u) = 0} and V = {v ∈ V | x(v) = 1}then form a Max-Cut solution of size at least k.We are now ready to prove Theorem 2.Proof of Theorem 2: According to Lemma 6, any approximation with an additive error less than 2 -2 p of the constructed ℓ p QRJA instance can be rounded to produce an optimal solution to Max-Cut. Since Max-Cut is NP-Hard and the constructed ℓ p QRJA instance's optimal solution has loss Θ(n 2 + m), the theorem follows. We include in this subsection experiment results using average squared error as the quantitative metric. We call this metric L2 quantitative loss. Specifically, for each contest, we predict the difference in numerical scores of all pairs of contestants that have both appeared before. We then compute the L2 quantitative loss as the average squared error of the predictions, and normalize it by the L2 quantitative loss of the trivial prediction that always predicts 0 for all pairs.The results are shown in Fig. 6 . We observe that both versions of QRJA still perform consistently well compared to other algorithms across the tested datasets. This is consistent with the results using the (L1) quantitative loss in Section 5.Additionally, ℓ 2 QRJA performs slightly better than ℓ 1 QRJA on this metric. This is expected because this metric is more aligned with the ℓ 2 QRJA's loss function.We include in this subsection the performance experiments on three more datasets. The new datasets are listed below.• Cross-Tables. This dataset contains the results of cross-tables (a crossword-style word game) tournaments (https://www.cross-tables.com/) from 2000 to 2023. Each contest is a round-robin tournament involving around 8 contestants. A contestant's numerical score is his/her number of wins in the tournament. There are 1215 contests and 1912 contestants in this dataset.• F1-Full. This dataset is an alternative version of F1. In F1-Full, we choose to additionally include contestants who do not complete the whole race. Now the contestants are ranked first by the number of laps they finish, and then their finishing time. A contestant's numerical score is the negative of the contestant's finishing time (in seconds). If the contestant does not finish all laps, we add a large penalty (1000 seconds) for each lap the contestant fails to finish. There are 878 contests and 606 contestants in this dataset.• Codeforces-Core. This dataset is a modified version of Codeforces. We only keep contestants who have participated in at least half of the contests in this dataset. We test on this modified dataset because all other datasets we use in the experiments are sparse datasets (i.e., contestants participate in a small fraction of the contests on average), so we want to see what happens on dense ones. There are 327 contests and 17 contestants in total.We evaluate ℓ 1 and ℓ 2 QRJA using the same metrics against the same set of benchmarks as in Section 5 on these three datasets. The results are shown in Fig. 7 . We highlight a few extra observations below.Extra observations on Cross-Tables. In terms of ordinal accuracy, Median performs the best among the tested algorithms on Cross-Tables. However, in terms of quantitative loss, Median is the worst algorithm among the tested ones. Moreover, it mostly performs suboptimally on other datasets as shown in Figs. 4 and 7 . This shows that although Median is occasionally good in performance, it fails in other cases.Extra observations on F1-Full. On F1-Full, both MF and ℓ 2 QRJA and perform considerably worse than ℓ 1 QRJA. This is not seen in other datasets. We believe this is because our score calculation results in a large variance in contestants' scores on F1-Full, which makes it harder for these methods to make good predictions. This also shows that ℓ 1 QRJA is more robust to datasets with large variances in contestants' performance than these methods. We also notice that Borda and Kemeny-Young perform well on F1-Full, which is consistent with their good performance on F1.Extra observations on Codeforces-Core. In terms of ordinal accuracy, all tested algorithms except Borda perform well. In terms of quantitative loss, MF and Median are worse than the other ones. This shows that on a dense dataset like Codeforces-Core, most algorithms can make good predictions. Moreover, MF does not have a clear advantage over other algorithms in our problem even if the dataset is dense.We also conduct the subsampling experiments in Appendix A.2 on all other 5 datasets. The results are shown in Fig. 8 .Experiment results. The message here is the same as that in Appendix A.2. In particular, Algorithm 1 can reduce the number of judgments with only a minor loss in performance as long as the subsample rate α is not too small. Note that in some of the figures, like Fig. 8c , the errors seem to be large visually. This is because of the small scale of the y-axis (only 0.6% for Fig. 8c ). The actual errors are The results show that ℓ 1 QRJA still performs consistently well across the tested datasets. However, ℓ 2 QRJA performs considerably worse than ℓ 1 QRJA on F1-Full. This is not seen in other datasets.small. Moreover, we observe that the performance of ℓ 2 QRJA is slightly more robust to subsampling than that of ℓ 1 QRJA. This is consistent with the results in Appendix A.2.Recall that in Section 5, we only show results of one version of Matrix Factorization (MF). We include in this subsection the experiments involving different variants of Matrix Factorization as well as their implementation details.Implementation details. We have implemented two variants of MF: Low-Rank MF and Additive MF. The MF algorithm used in Section 5 is Low-Rank MF with rank r = 1. We describe the implementation details below.• Low-Rank MF. Recall that in the context of our experiments, we can view each contestant as a row and each contest as a column. The score of a contestant in a contest is the entry in the corresponding row and column. A classical model of MF Koren et al. [2009] is factorizing A ∈ R n×m as the product of two low-rank matrices UV ⊤ , where U ∈ R n×r , V ∈ R m×r for some small r. Note that in our experiments, the algorithm is required to predict a new column of A with no known entries. Therefore, we cannot directly apply this method since the corresponding row of V will remain unchanged after initialization. To solve this problem, we instead predict every column with known entries in A and then take the average of the predictions as the prediction for the new column. We use the standard loss function that sums up the squared errors of all observed entries. We implement this method with SciPy [Jones et al., 2014] and use gradient descent for a fixed number of epochs on a deterministic initialization to keep the results deterministic. We test r = 1, 2, 5 in this subsection.• Additive MF. We also consider an additive variant of MF. For x ∈ R n , y ∈ R m , this method predicts A i,j = x i + y j . Here, x i can be viewed as contestant i's skill level, and y j can be interpreted as the (inversed) difficulty of contest j. We then use the vector x to make predictions.Note that this version of MF resembles QRJA in that for each of these two methods, the loss function is 0 if A i,j = x i + y j holds for the known entries. We also use the standard sum of the squared loss function and use gradient descent for a fixed number of epochs on a deterministic initialization to keep it deterministic.Performance experiments. We first evaluate these variants of MF using the same metrics as in Section 5 on all datasets. The results are shown in Fig. 9 . We can see that R1 MF and Additive MF The results show that Algorithm 1 can reduce the number of judgments to a factor less than 1.0 with a minor loss in performance in the used datasets. Note that errors in some figures appear large because of the small scale of the y-axis. The actual errors are small. generally have similar performance. In contrast, R2 and R5 MF perform worse than the former. We therefore choose to present R1 MF in Section 5.Low-Rank MF's performance over training. The observation that R2 and R5 MF perform worse than R1 MF is surprising to us. To confirm this observation, we plot the performance of these variants of MF with different numbers of training epochs on all datasets. The results are shown in Fig. 10 . We can see that R1 MF generally outperforms R2 and R5 MF in terms of both ordinal accuracy and quantitative loss when trained for long enough. Moreover, R1 MF's performance on both metrics generally improves as the number of training epochs increases (the only exception is quantitative loss on F1-Full). In contrast, R2 and R5 MF's performance in terms of both metrics worsens as the number of training epochs increases on Chess, F1, and Codeforces. These observed phenomena suggest that R2 and R5 MF tend to overfit the data. The problem for R1 MF is less severe.Experiment results on entrywise metrics. As the metrics in Section 5 are defined in a pairwise fashion and might not be well-suited for MF, we also evaluate the performance of MF in terms of entrywise L1 and L2 loss (i.e., the average absolute and squared error of the predictions on each contestant's actual score in each contest). We also normalize each of these losses by the corresponding loss of the trivial all-zero prediction. The results are shown in Fig. 11 . Note that QRJA and Additive MF are not included, because their predictions can be shifted by an arbitrary constant, and thus entrywise losses do not apply to them. We can see that in terms of entrywise L1 and L2 loss, R1 MF outperforms R2 and R5 MF on most datasets. The exceptions are F1-Full and Codeforces-Core. These two datasets are different from the other ones in that F1-Full's scores are calculated with two numbers (the number of laps finished and the finishing time) and Codeforces-Core is a dense dataset constructed from Codeforces. Therefore, on these datasets, MF with higher ranks might be more suitable than R1 MF, while on the other datasets, they tend to overfit the training data. Moreover, we note that on entrywise metrics, MF generally performs worse than Mean and Median.Summary of experiment results. In summary, experiments in this subsection show that on our datasets, R1 MF and Additive MF, which are similar in performance, generally perform better than R2 and R5 MF. Therefore, we choose to include only the results of R1 MF in Section 5.We characterize ℓ p QRJA by giving a set of axioms for the family of transformation functions f of pairwise loss that we consider. We show that those transformation functions considered in ℓ p QRJA are essentially the minimum set of functions satisfying these axioms.Recall that for each judgment about a and b where a is better b by y units, the absolute error of the prediction vector x on this pair is |x a -x b -y|. Using this as the loss function, we obtain the ℓ 1 QRJA rule, which has been characterized using axioms in the context of social choice theory Conitzer et al. [2016] . Below we extend this characterization to ℓ p QRJA for any positive rational number p ∈ Q + . Note that restricting p to be rational is without loss of generality, since the output of ℓ p QRJA is continuous in p.We consider transforming the absolute error by a transformation function f to obtain the actual pairwise loss, which is f (|x a -x b -y|). For ℓ p QRJA, the transformation function is f (t) = t p . To characterize QRJA as a family of rules (for different p ∈ Q + ), we give axioms for the corresponding family of transformation functions, i.e., t p for p ∈ Q + . Let F be a family of transformation functions.Below are the axioms we consider:• Identity. There is an identity transformation f 0 ∈ F, such that f 0 (t) = t for any t ≥ 0.• Invertibility. For each f 1 ∈ F, there is an f 2 ∈ F such that f 1 composed with f 2 is identity, i.e., for any t ≥ 0, f 1 (f 2 (t)) = t.• Closedness under multiplication. For any f 1 , f 2 ∈ F, there exists f 3 ∈ F such that for any t ≥ 0,f 1 (t) • f 2 (t) = f 3 (t).We show below that the family of transformation functions corresponding to the ℓ p QRJA rules is the minimum family of functions F * satisfying the above axioms. By the first axiom, the identity transformation f 0 where f 0 (t) = t is in F * . (This corresponds to ℓ 1 QRJA.) Then by the third axiom, for any k ∈ Z + , f k 0 is also in F * , where f k 0 (t) = t k . And by the second axiom, for any k ∈ Z + , f 1/k 0 is also in F * , where f1/k 0 (t) = t 1/k . This is because f 1/k 0 (f k 0 (t)) = t.Finally, for any r ∈ Q + where r = p/q for p, q ∈ Z + , by the third axiom, f r 0 = (f 1/q 0 ) p is in F * , where f r 0 (t) = t r . Note that the above argument establishes that F * contains all transformation functions corresponding to QRJA, i.e.,{t r | r ∈ Q + } ⊆ F * .Below we show the other direction, i.e., {t r | r ∈ Q + } satisfy the 3 axioms, and as a result,F * ⊆ {t r | r ∈ Q + }.For f 1 (t) = t r1 , f 2 (t) = t r2 where r 1 , r 2 ∈ Q + , we havef 1 (t) • f 2 (t) = t r1+r2 ,where r 1 + r 2 ∈ Q + , andf 1 (f 2 (t)) = (t r2 ) r1 = t r1•r2 ,wherer 1 • r 2 ∈ Q + . This implies F * ⊆ {t r | r ∈ Q + }. Thus F * = {t r | r ∈ Q + } as desired.The datasets used in this paper are collected from publicly available websites either manually or through an API. We provide the following information about these datasets. NeurIPS Paper Checklist38th Conference on Neural Information Processing Systems (NeurIPS 2024).We choose the time frame of our datasets to be longer than the active period of most contestants to emphasize that contestants come and go, but their past performance could help the prediction.We also include the experiment results using average squared error as the quantitative metric in Appendix C.1. The relative performance of the tested algorithms on these two metrics are similar. 


Decision: The paper generalizes the quantitative relative judgments aggregation problem (QRJA) proposed by Conitzer et al. (2015, 2016), bridging voting theory and learning-to-rank problems. There is a latent “true” ranking of the candidates to be learned based on a set of judgments (a, b, y) indicating that candidate a is better than candidate b by y units. The paper introduces new aggregation rules for QRJA for high-order loss functions and tests their algorithms on real-world data.

The review team agreed that the problem is interesting and important and the paper presents a sound theoretical analysis and clear experiments. The reviewers pointed out several aspects that could be improved, including the presentation of the technical details, positioning of the paper within the literature (highlighting better the conceptual contributions), and discussing and comparing against related empirical works (see e.g., the suggestions and comments by Reviewer iMha, zJAB). 

Overall, the review team, including myself, view positively the contributions of the paper. I believe most of the concerns can be sufficiently addressed in a revision (given the information provided by the authors in their rebuttal).

Reviews: review: paper_summary: paper_summary: The paper generalizes relative quantitative judgments by Conitzer et al., which aims to aggregate judgments on the relative quality of different candidates from various sources and applies it to a learning-to-rank setting.  The authors introduce new aggregation rules QRJA that tries to assign vector $x_1,\dots x_n$ that minimizes error 
$$\sum_i w_i f(|x_{a_i}-x_{b_i}-y_i|)$$
from collection of quantitative relative judgement $J_i = (a_i,b_i,y_i)$ where $f$ is some increasing function. 

The paper mostly focuses on $f(t)$ being a monomial $t^p$.  They provide a near-linear time algorithm to solve the above optimization problem if $p\ge 1$ and NP-hardness results when $p<1$.  Empirically, the paper validates the effectiveness of QRJA-based methods through some simple baselines, (mean, median, Borda rule, matrix factorization, and KY rule) on on real-world datasets, including chess, Formula 1, marathons, and programming contests.
strength_weakness: strength_weakness: 1. The technical writing is not very friendly or informative.
- It seems the optimization problem can be reduced to a sparse $p$-norm regression problem.  Is there an off-shelf method to solve it?  Why is it necessary to consider the dual program?
- The proof of Lemma 1 is not clear to me.  Which results in Chen et al. 2022 are you used to solve Equation (4) (e.g., Theorem 10.14)?  Moreover, the author should provide an explicit statement of the reduction. 

2.  I feel the empirical results should be compared to more relevant literature. 
  - Given the long history of rank aggregation or ranking system, I feel the evaluation in the paper is insufficient.  A rating system is an algorithm that adjusts a players rating upwards after each win, or downwards after each loss.  Some notable rating systems used in practice include Harkness, Elo, Glicko, Sonas, TrueSkill, URS, and more.   As ordinal accuracy in the paper is also derived from pairwise comparisons, it seems reasonable to apply Elo and other methods. 
  - Another related area may be item response theory, where contestants have expertise and events have difficulty.

3.  The presentation should be more cogent
- It is not clear to me how the model conceptually addresses issues in those motivating examples (Examples 1 to 3).   
- The empirical results only test QRJA under $p = 1,2$, and provide little discussion on the choice of $p$.  Note that standard gradient descent should solve the optimization problem for all $p\ge 1$.
questions: questions: Can you address the first point in weakness of Theorem 1?
- why dual program
- Limitation of using $p$-norm regression
- Reduction to Chen et al. 2022
limitations: limitations: The paper addresses the limitations.
paper_summary: paper_summary: The paper studies Quantitative Relative Judgment Aggregation, in which they want to learn a quantitative score for a group of alternatives that align with a series of pairwise quantitative differences between alternatives as much as possible. They extend the result in [Conitzer et al, 2016] from linear loss function to high-order loss function and show the NP-hardness to find an optimal score when the order $p < 1$. They also test their algorithms on real-world racing data and shows its supremacy towards previous methods.
strength_weakness: strength_weakness: -The relationship between previous work. I don't quite see how this paper conceptually distinguishes itself from [Conitzer et al, 2016]. 
The two papers study similar problems under similar settings. In this case, I would rather grant the conceptual contribution of "social-choice-motivated solution concepts to the problem of ranking prediction" to their paper. Your paper indeed has its own conceptual contribution compared to the previous work, but the current claim is not precise enough. 
- The motivation of the race. I feel that the whole introduction emphasizes that the paper focuses on race scenarios, yet multiple questions are unanswered: For example, why race is a reasonable representation of judgments? What are the differences between traditional scenarios that are worth a separate study? What are the real-world applications?
- The proofs and the sketches are hard to follow with too many skips and magic numbers.
questions: questions: 1. Please distinguish your paper from previous work, especially how your work is different from [Conitzer et al, 2016] and [Conitzer et al, 2015] conceptually and technically. 
2. Please answer my question related to the motivation of the race in the weakness section. 
3. Please specify what simple algorithm you apply for $l_2$ norm in the experiment.
limitations: limitations: Yes.
paper_summary: paper_summary: This work defines and studies the "Quantitative Relative Judgment Aggregation" problem, which involves asking a set of judge agents to predict the performance of a set of "competitor agents" in some kind of content (e.g., a race). This task is related to recsys style collaborative filtering, ranking systems in games, and other models of preference-over-items, but the work argues this particular task is distinct and should be theoretically analyzed as a distinct setting. The paper provides several theorems about the computational complexity of QRJA and experiments using real competition data with a backtesting-style evaluation.
strength_weakness: strength_weakness: One minor point regarding the interpretation of experimental results: the specific claim that QRJA is inherently more interpretable than MF was made a bit briefly and might benefit from additional remarks. My initial interpretation of the experimental results was: it seems like the new method introduced in the paper is about as good as MF, and has potential explainability benefits because we can walk through / "print out" the aggregation steps that took place and explain how a QRJA-using system came to the conclusion that Alice is faster than Bob. However, it seems possible that in the realm of MF one can apply various results from explainability in recommender systems (including post-hoc methods, e.g. . Concretely, I think just a brief expansion of this point would be helpful, and especially the extent to which there's a core modelling limitation with latent factors approach vs. a practical problem of 'need large embedding space to make MF good for these datasets'.

From the perspective of someone working on social choice-related theory or experimental work, I think this paper will be a strong contribution. However, one potential high-level weakness with this paper for a general audience is that readers may have some trouble understanding the general motivation for this problem, because of the mixed examples (trying to use "judgments" which are actually sensor readings from e.g. a relatively objective "race" to estimate a physical parameter of something like a car vs. trying to aggregate human judgements). While I think after spending some time with the paper, I get what the current draft is going for (something along the lines of, "social choice theory is useful in the context of these subjective aggregation problems in which some people will be weighted more or less, and is ALSO useful in estimating real "physical" models), I think this may not be totally clear.

Section 2 is helpful in this regard, but I think it could be useful to just generally clarify if the first-order goal here is to use this method to model "true rankings".
questions: questions: Summarizing some of the points above into questions:
- Can you further clarify the explainability benefits of your approach vs MF, perhaps drawing on the provide "Examples" section
- Is it possible to provide additional clarity about the primary motivation for the work (estimating "true" / "physical" values vs. contributing to work on aggregating subjective values)
- Minor: tying the choice of loss functions back to the provided examples and motivation could make the results more exciting for a broad audience / general ML audience.
limitations: limitations: The current draft is reasonable in its claims: the theoretical analyses and experiments provided are commensurate to the claimed contributions.
paper_summary: paper_summary: NOTE: I have reviewed a previous version of this paper submitted to AAAI 2024. The review here is an updated version of that review reflecting the changes in the paper.

==============================

This paper explores the problem of comparing numerical judgements against each other in order to arrive at a scoring of candidates. e.g. Comparing the scores of competitors against one another, possibly when some scores are missing. The model of Quantitative Relative Judgement Aggregation accepts a set of tuples (a, b, y) which indicate that a is better than b by y units. The goal of the framework is a score for each candidate such that the difference between scores of each candidate is similar to the reported difference between candidates.

The paper narrows their framework to l_p QRJA which uses a more restricted loss function in order to ease the use of known complexity results. They show various complexity results as p changes, notably that l_p QRJA can be solved in near-linear time with bounded error for p >= 1 and that the problem is NP-hard when p <1. Experiments on several datasets show that using p = 1 and p = 2 does lead to a higher accuracy and lower loss than a number of other comparable metrics.
strength_weakness: strength_weakness: See previously written and lightly edited section above.
questions: questions: Have you re-run the experiments since the previous submission that I reviewed? I ask because the numbers in Figure 4 are quite similar but do not match exactly the previous version. I cannot figure out why 2 weeks of server time would have been spent re-running the same (?) experiments previously reported.
limitations: limitations: The authors have done a good job of filling out the checklist and have addressed the limitations of the paper.

Comments: comment: Thank you for your reply. We will incorporate this discussion in the revised version of the paper. We will also add more examples to show the broader applicability of ranking objective judgments, while continuing to use the racing scenario as a running example.
I appreciate your detailed discussion. I am more familiar with social choice than learning to rank, and your explanation answers my questions well. I will be more positive about this paper if you can add this discussion to the edited version of this paper. Also, I feel that while ranking objective judgments makes sense, racing data itself is not persuasive enough. I think you can discuss more applications in the motivation and make racing a running example (as you already do in the paper).
Thanks for these responses. I maintain my original positive recommendation.
Thank you for the response!
Another difference between the communities is the degree to which aggregate rankings need to be justified, be transparent, follow a clear and simple pre-specified rule, satisfy certain axioms, etc. These aspects tend to be especially important in the social choice community; in the learning-to-rank community, it varies, but at least in some cases they do not matter too much.  For example, in many content recommendation settings, what matters primarily is that the results are "good" by some metric, such as that they contain what the user is searching for early in the results. We think the bridging role played by our current paper can also be helpful in intermediate settings, such as aggregating the results of races or contests, where we don't need to worry about the races somehow being strategic agents, but for fair evaluation we still want the results to be based on some clear interpretable rule.
Thank you for your reply.
 
Generally speaking, in social choice, people typically consider subjective opinions and judges as inputs, e.g., voting. Conversely, in the learning-to-rank community, the inputs are usually more objective, e.g., ranking web pages in response to a search query. The difference in subjectiveness has led to the difference in the focus of these two communities. For example, the learning-to-rank community is less concerned about strategic aspects of voting. By considering a social-choice-motivated problem with objective inputs typically seen in the learning-to-rank community, we explore the interplay between them.
Thank you for your response. I have one additional question related to your response on question 1. 

In the second paragraph, you state that "(relative judgments to be aggregated) can also be produced by an objective process, like a race, rather than human judges" and then "This gives us the opportunity to explore the interplay between social choice theory and the learning-to-rank community". Could you deliberate it bit more on how the first statement logically leads to the second? Is it because that the subjective human judges does not fit into learning-to-ranking problems? Or are there other reasons?
Thanks for these responses. This helped to clarify my minor questions about the paper, and I stand by my original positive recommendation.