Aggregating Quantitative Relative Judgments: From Social Choice to Ranking Prediction
Authors: Yixuan Even Xu
Hanrui Zhang
Yu Cheng
Vincent Conitzer
Venue: NeurIPS 2024 poster (2024)
Keywords: Algorithmic Game Theory
Ranking and Preference Learning
Primary area: algorithmic_game_theory
TL;DR: We propose new rules for aggregating quantitative relative judgments, study their computational complexity, and evaluate their empirical performance.

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.

Aggregating Quantitative Relative Judgments: From Social Choice to Ranking Prediction
Yixuan Even Xu Carnegie Mellon University yixuanxecs. cmu.
Hanrui Zhang Chinese University of Hong Kong hanrui@cse cuhk. edu hk
Yu Cheng Brown University yu_ muu_chen@@brow..ce
Vincent Conitzer
Carnegie Mellon University coni cmu
cdu edu
Abstract
Quantitative Relative Judgment Aggregation (QRJA) is a new research topic in (computational) social choice. the QRJA model, agents provide judgments the relative quality of different candidates, and the goal is aggregate these judgments across all agents. In this work, our main conceptual contribution is to explore the interplay between QRJA in 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, race can be viewed the contestants' relative abilities. This allows us to aggregate results from multiple races evaluate the contestants' true qualities. At technical level, we introduce new aggregation rules for QRJA and study their structural and computational prop- erties. We evaluate the proposed methods data from various real races and show that QRJA- methods offer effective and interpretable ranking predictions.
"judgment" on
Introduction
In voting theory, each voter ranks set of candidates, and a voting rule maps the vector of rankings to either winning candidate aggregate ranking of all the candidates. There has been signif- icant interaction between computer scientists interested voting theory and the learning-to toarning-tt-rank community. The learning-to- to-rakkk community is interested in problems such ranking webpages in response to a search query, or ranking recommendations to a user (see, e.g., Liu 2009)). Another problem of interest is aggregate multiple rankings into 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 model where there is latent "true" ranking of the candidates, of which all the votes are just noisy observations. Conse- quently, it is natural to try to estimate the true ranking based on the received rankings, and such an estimation procedure corresponds
voting rule. (See, e.g., Young [1995); Conitzer and Sandholm [2005]; Meila et al. [2007]; Conitzer et al, [2009]; Caragiannis et al. 2003 Soufiani et al. 2014]] Xial 2016), and Elkind and Slinko 2015] for an overview.
Voting rules are just one type of mechanism in the broader field 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 (0155 for overview), judges assess whether certain propositions true false, and the goal is to aggregate these judgments into logically consistent statements. The observation
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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, 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 al. 2018); another example could be that an agent judges that "using unit of gasoline is as bad as creating units of landfill trash" (in a societal tradeoff context) [Comitzer al. 2016). Quantitative judgment aggregation has been considered in the area of automated moral decision beecision-making. where an Al 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 observe that relative "judgments" can be produced by process other than a subjective agent reporting them, which is the standard assumption in social choice. To illustrate, consider a race in which contestant finishes 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-rant 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 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 social choice context are less important in 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- metieilcoiice solution concepts to the problem of ranking prediction, which creates bridge between research typically done in the social choice and the learning-to to-rank communities. (2) We pose and study the problem of quantitative relative judgment aggregation (QRJA) in Section B which generalizes models from previous work [Conitzer et al. 2016). (3) Theoretically, we focus on lp QRJA, an important subclass of QRJA problems. We (almost) settle the computational complexity of lp QRJA in Section 4 proving that é, QRJA is solvable in almost-linear time when
p 1, and is NP-hard when p < T. (4) Empirically, we focus on & and Eg QRJA. We conduct extensive experiments on 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.
2 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 "casy" races (or only the "hard" races), simply taking the median or mean of historical performance will return biased estimates, as illustrated in Figure
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:00
Figure 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 '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:00
Figure 2: The same results in Figure 1 but with some data missing. If we only look the data Alice and Charlie, it difficult to judge who is the faster runner. If anything, Charlie appears to be slightly faster. However, if we know Bob's s results in these races, then transitivity suggests that Alice runs faster than Charlie.
Example 3. When the variance of the races' difficulty much higher than the variance in the contestants" performance, taking the median will essentially focus on the result of single race (with median difficulty) and may throw away useful information as shown Figure
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:10:00
4:32:00
4:09:00
Figure 3: In this example, the races' diffieulty has high variance, and everyone's median time is in Boston. Based on this, we would predict Charlie to be faster than Bob. However, if we consider the other races, overall it seems that Bob runs faster than Charlie.
QRJA addresses the above issues by considering relative performance instead of absolute performance. More specifically, each race provides a judgment the form "A runs faster than by minutes" for every pair of contestants (A, B) that participated in this race.
3 Problem Formulation
In this section, we formally define the Quantitative Relative Judgment Aggregation (QRJA) problem. We start with the definition of its input.
Definition (Quantitative Relative Judgment). For a set of n candidates N = f1.... n guantitative relative judgment a tuple J (a, y), denoting a judgment that candidate N better than candidate b E N by IK units.
The input of QRJA set of quantitative relative judgments to be aggregated. We model the aggregation result as vector x E R", where 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 |._ Ib to be small. We use a loss function f(|2, - DB - y/) to measure the inconsistency between the aggregation result and the input judgments. The aggregation result should minimize the weighted total loss. Formally, define QRJA follows.
Definition 2 (Quantitative Relative Judgment Aggregation (QRJA)). Consider candidates' N (1...., n and m quantitative relative judgments J .,,....,,mm,, with weights w (wi,.... Wm) where J; = (as, bi, ).). The quantitative relative judgment aggregation problem with loss function f: R20 + R200 asks for a vector x 18" that minimizes Σ -i= w. f(
Tb. yrl).
2019 studied special case of QRJA where f(t) = f. 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 convex optimization problem. Consequently, one can use standard convex optimization methods like gradient descent or the ellipsoid method to solve QRJA in polynomial time.
Previous work [Conitzer al.
2015
2016
Zhang et al.
However, general-purpose convex optimization methods are often very slow when the numbers of candidates n and judgments are large. For this reason, we focus é, QRJA, an important subclass of QRJA problems with loss function f(( = IP. Our theoretical analysis (almost) settles the computational complexity of &p QRJA for all p 0. We show that lp QRJA is solvable in

---

almost-linear time when p 2 1, and is NP-hard when < 1. Our experiments focus on comparing f and Eg QRJA with various baselines in social choice and machine learning. We conduct extensive experiments wide range of real-world data sets.
4 Theoretical Aspects of lp QRJA
In this section, we study the theoretical aspects of bp QRJA, providing clean and (almost) tight characterization of the computational complexity of Ep QRJA for different values of Recall that is the number of candidates and m is the number of judgments. Note that n S 2m.
In Section 4.1
be solved in almost-linear time O ++)))) In Section 4.2 we show that when p < 1, Ep QRJA is NP-hard and there is no FPTAS unless P
prove that for all p 2 1, cp QRJA
NP. Additionally, Appendix we show that if S p S 2 and m > n, we can reduce m to (())
while incurring small error.
4.1 P QRJA in Almost-Lineat Time When p 2
We first show that when p 2 1, Ep QRJA can be solved in O(m!+o(l) time, i.e., in time almost linear in the size of the input. Note that to solve lp QRJA with p in polynomial time, one can formulate the problem an & regression problem and apply general-purpose techniques for lp regression, e.g., [Bubeck et al. 2018 Adil el al. 2024). However, these methods would result in a running time that 52(m + n²)) where w > 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 al. (002)).
Theorem 1. Let p 2 1 be an absolute constant. Consider Ep QRJA in Definition 2 with loss function f(t) = t. Assume all input numbers are polynomially bounded in m. We can solve lp QRJA in time (m()))() with exp(- log" m) additive error for any constant
Proof of Theorem 1
We first prove the theorem for p > 1. We will prove the = 1 case in Appendix B.1 Let Sipptt = (n, m, (w;) (y+))* 1). We assume m sufficiently large, and that is a sufficiently large constant such that Vu E Simput. either = 0 or 1/m < |u| < m².
Consider an e, QRJA instance (N, J, w) where J (J 1..., Jm) and Js (as, bi, Wi). construct a matrix A E Rmxxn and a vector z E R as follows:
if Oj
AIj
if = b otherwise
2, w/wiyt.
(1)
Given A and z, the l, QRJA problem can be formulated as
min
we Wa/wao
Fb; wal P
min xER"
|| =1|p,
We will show how to find x in time O(m-+o(11) such that
|A zllp I min Axx zllp exp( log"* m).
We first write the optimization as
min xeR
Ax - z11,
min
|||||
(2)
xER" ,EE "== Ax-2
The Lagrangian dual of 2 is
min max ||s||, + TT (Ax -2)))
FER"
Fully Polynomial- -ime Approximation Scheme.
"The Ö(-) notation hides logarithmic factors in its argument.

---

Note that Ax z is enforced; otherwise the inner maximization problem is unbounded. Let 1. (So q > 1.) By strong duality,
Il-ll, be the dual norm of II-1| i...
(1ss|p) + +f (s (Ax -z))
max FER" x SER"
min
f + min SERm
[|Ss|lp + +FTs)
max f Ax XEX"
max FER"
max
z.
(3)
TER" f=0,1if1l,
The last step follows from the fact that the value of (mingeRm ||s||p p ffs) is I and otherwise, and that maXxeR" f Ax is unbounded if A ff 0.
We will show that the dual program 3 can be solved near-optimally in almost-linear time (Lemma and given near-optimal dual solution E Rm, good primal solution TR" can be computed in linear time (Lemma Theorem follows directly from Lemmas] and
Lemma 1. We can find a feasible solution f E RT of 3 in time (mm++o(1) with additive error exp(- log m).
Proof of Lemma Consider the following problem, which moves the constraint of ( into the objective:
FER A t=0 f z-- |f
(4) is closely related to lp norm mincost flow. Recent breakthrough in mincost flow [Chen al. 2022 showed that feasible solution f of within error exp(- 13c m) can be computed in O +o(1) time.
Suppose [ft l,, 2 exp( - log" m). which we prove later. Notice that f is solution within error
exp(- exp(-log"* 13c m) of
log
f Fz..
max TER",ATER
||
Choosing f = ft/ ||ft] satisfies Lemma
To lower bound [F l1. let f be the optimal solution of (3.. When f z 2 3, because the optimal
value of 44 is least f z and ff near-optimal for we have ft z 2 f"
and thus |f] 2 exp(- log" 7e m).
lft 2 1/3. When f" T < 3, we will show ff z 2 exp(
log 6c m),
To show ft 2 exp(-log" m), only need to show that the optimal value of 44 is at least sxp(-log m). We can assume w.l.o.g. that ft > exp(-log" m). otherwise there primal solution x almost consistent with all judgments, which is easy to approximate. Note that when scaling down f", || scales faster than f- z. Let f' = kf" with ie = exp(-log' m). We have r z 1 k(f z) k2 > exp(- log m), where the last step assumes that m is sufficiently large, in particular log" max q-1-9 1).
Lemma 2. Given a solution of 3 that satisfies Lemma we can compute a vector x E R in
time (mm) such that
Ax z||p < min A| - xl1p exp(- m).
Proof of Lemma 2
We assume w.l.o.g. that [|f]11
Let U = z and consider
(f')) where ((f') TT 2|
(5)
F'ER" A T =0=0
g
5

---

Because is solution of (3) within error exp(- m). and max ffl,, ||f]|,
[illy is achieved
q
when || fl1 1, we know that is a solution of ( within error exp( log s0 m).
5 guarantees that (f)() is very close to potential flow. That is, we can find in (m) time vector x E R", such that AA - (f & exp( log" m). For this
The first-order optimality condition
Ax z S (f) zI, + +AA V - |Ax (
1- m Ax (f)()
ビッ+ exp( - log 20 m)
s min x
||xx - z11p exp( log m).
The last inequality uses that = f z is a lower bound on the optimal value because is a feasible dual solution.
4.2 NP-Hardness of e, QRJA When p
In this section, we show that 4p QRJA is NP-hard when < 1 by reducing from Max-Cut. Note that in this case, the loss function f(t) (P is longer convex.
Definition 3 (Max-Cut). For an undirected graph G = (V. E), Max- Cut asks for partition of into two sets S and T that the number of edges between S and T is maximized.
Reduction from Max-Cut Ep QRJA. Given a Max-Cut instance on an undirected graph let [V], m EE 202 I-p 1, and w1 nu2 +
We will construct an tp QRJA instance with n + 2 candidates V U fo(") and O(n + m) quantitative relative judgments. Specifically, we add the following judgments:
(o(t), (()) 1) with weight w1
(ofs), u, 0) with weight w2 for each E V.
(o(0) u, 0) with weight wy for each u E 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 solution with loss at most nuw + 2(m kz) + k22, which implies the following hardness result.
Theorem 2. For any < 1, there exists constant e > 0 such that it is NP-hard to approximate Ep QRJA within a multplicaative factor of (1)
Theorem 2 limpliss that there no (multiplicative) FPTAS for é, QJA when p < 1 unless P NP. This is because if (1 +) solution can be computed in poly(m, 1/E) time, then choosing gives poly-time algorithm for Max-Cut.
Experiments
We conduct experiments on real-world datasets to compare the performance & and &g QRJA with existing methods. We focus on & and & QRJA because the almost- time algorithm for general values of p 2 relies on very complicated galactic algorithms for ép norm mincost flow [Chen et al. 2022]. Although general-pune purpose convex optimization methods can also be used to solve Ep QRJA, they are not efficient enough for some the large-scale datasets we use. All experiments are done on server with 56 CPU cores and 504G RAM. The experiments in Section 5 and Appendices A and take around weeks in total to run on this server. No GPU used. All source code available at jwwggjjttggteeeeeeeeeeee aggregation.
https:// //i thub.

---

5.1 Experiments Setup
Datasets. We consider types of contests where events are reasonably frequent (so 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 and the copyright information of the datasets in Appendix B
three more datasets in Appendix [
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 2023 Each contest is typically round-robin tournament among 10 to 14 contestants. A contestant's numerical score 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 races (https: www formulal........ 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 '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:////// /wwww//wwww..... 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 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 btttps://codeforee com) 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. contestant's 's numerical score is that contestant's 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 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 error F 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 ε and & QRJA in Python. We use Gurobi Gurobi Optimization, LLC [023 and NetworkX Hagberg et al. [2008 to implement & QRJA and the least-square regression implementation in SciPy PJnes et al. 2014] to implement & QRJA. To transform the contest standings into a QRJA instance, we construct quantitative relative judgment J J= (a, b, y) for each contest and each pair of contestants (a, b) with y being the score difference between a and in that contest. We set all weights to ensure fair comparison with benchmarks.
Benchmarks. We evaluate & and &g QRJA against several benchmark algorithms. Specifically, we consider the natural dineenmennio aggregation methods Mean and Median, social choice methods Borda and Kemeny- Seunnny-Youg,,, and common method for prediction, matrix factorization. We describe how we apply these methods to our setting below.
We choose the time frame of our datasets be longer than the active period of most contestants 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.I The relative performance of the tested algorithms these two metrics similar.
7

---

0.70
68.4%
Accuracy
66.6%
1:15
1.1163
Quantitaiie
0.65
62.5%
52.9%
1.03
0.60
0.9848
0,9689
0.55
0.95
LIORJA L2ORJA Median
Mean
Borda
KM
MF
LIORYA
L2ORJA
Median
Mean
MF
(a) Ordinal accuracy Chess
(b) Quantitative loss Chess
10
64.3%
66.0%
64.6%
8.0461
0.55
55.1%
1.4436
LIORIA LZORJA Median
Mean
Borda
K
MF
LIORJA
L2QRJA
Median
Mean
Mr
(c) Ordinal accuracy Fl
(d) Quantitative loss
FI
0.80
79.3%
78.8%
78.8%
79.4%
0.76
0.78
74.5%
0.56
0.5632
72.2%
0.54
0.5304
0.5280
0.5254
0.52
LIORIA LZORJA Median
Mean
Borda
MF
L1QRIA
L2ORJA
Median
Mean
MF
(e) Ordinal accuracy Marathon
(f) Quantitative loss Marathon
0.66
6%.3%
65.0%
1.15
1.1022
0.62
0.65
0.63
0.64
62.1%
64.3%
64.3%
64.0%
1.00
1,05
0.9332
0,9328
0.61
LIGRJA L2ORJA Median
L1ORJA
L2ORJA
Mean
(g) Ordinal accuracy on Codeforces
(h) Quantitative loss on Codeforces
Figure 4: Ordinal accuracy and quantitative loss of the algorithms on all four datasets. Error bars are not shown here as the algorithms are deterministic. The results show that both versions of QRJA perform consistently well across the tested datasets.
median of that contestant's scores training contests. We then make predictions based on differences between these mean 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. (0066).
Mean and Median. For every contestant in the training take the
The Borda rule. The Borda rule is voting rule that takes rankings input and produces ranking as output. We use normalized version the Borda rule. The i-th ranked contestant in contest receives 2(i-1)
n;-1 points, where nj is the number of contestants in the contest. The aggregated ranking result obtained by sorting the contestants by their total number of points.
The Kemeny-Youur 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 ranking output. Specifically, it outputs ranking that minimizes the number of disagreements on pairs of contestants with the input rankings. Finding the optimal Kemeny- Young ranking is known be NP-hard Bartholdi el al. [1989] In experiments, 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 run Kemeny-Young.
Matrix Factorization (MF). Matrix factorization takes input matrix with missing entries and outputs prediction the whole matrix. Every row is contestant and every column is race. The score of contestant in 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 this context. But we do not include them in benchmarks because they do not exactly fit our setting motivation. For example, the seminal Elo rating system Elo 1978) as well as many other methods Maher [1982]: Karlis and Nizoufras (2008):
Guo et al. 2012
Hunter and others 2004) can all predict the results of pairwise matches in, c.g..

---

chess and football. However, they are not originally designed for predicting the results of contests with more than two contestants.
5.2 Experiment Results
The complete experimental results of all algorithms on the four datasets are shown in Fig- Note that Borda and Honneny-Young do not make quantitative predictions, so they are included in Figs.
and 4h
The performance of QRJA. As shown in Fig. both versions of QRJA perform consistently well across the tested datasets. They are always among the best algorithms 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-Younr Borda and Kemeny-
do not make quan- titative 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 Fl, 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 QRJA. The advantage of QRJA over MF is the interpretability of its model. The variables in QRIA have clear meanings they can be interpreted 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 & QRJA is more robust large variance in contestants' performance than MF.
Summary of experimental results. summary, both MF and QRJA are never significantly worse than the perf-oern algorithm 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 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 have is ranking data, rather than numerical data such finishing times. Moreover, random utility models generally do not model common factors, such as 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 have in mind. Matrix completion Rennie and Srebro 22055 Candès and Recht [2009) is a popular approach in collaborative filtering. where the goal is to recover missing entries given a partially-observer 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 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 al. (2009)) )) One high-level difference is that preference learning tends to use existing methodologies in machine learning learn rankings. In contrast, our methods (as well as those in previous work Conitzer et al. 2015 2016)) are social-choice-ther theoreeiill 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 el al. (2006), have been developed to maintain rankings of players various forms of games. Unlike QRJA, these methods focus more the online aspects of the problem, i.c.,

---

how to properly update scores after each game. While under specific statistical assumptions, these methods can in principle predict the outcome of future game, they are not designed for making ordinal or quantitative predictions in their nature.
7 Conclusion
In this paper, we conduct thorough investigation of QRJA (Quantitative Relative Judgment Ag- gregation). We pose and study QRJA and focus on an important subclass of problems, lp QRJA. Our theoretical analysis shows that ep QRJA can be solved almost-linear time when p 2 1, and is NP-hard when < 1. Empirically, we conduct experiments on real-world datasets to show that DRJA-based methods are effective for predicting contest results. As mentioned before, the almost- linear time algorithm for general values of f 1, 2 relies very complicated galactic algorithms. An interesting avenue for future work would be to develop fast (e.g.. nearly-linear time) algorithms for Ep QRJA with of 1, that are more practical, and evaluate their empirical performance.
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.
Broader Impacts.
Acknowledgments and Disclosure of Funding
Zhang and Conitzer are supported by NSF IIS-181400 1814056, the Center for Emerging Risk Research, and the Cooperative AI Foundation. Cheng supported in part by NSF Award CCF-2307106.
10

---

References
Decksha Adil, Rasmus Kyng, Richard Peng, and Sushant Sachdeva. Fast algorithms for by regressssion. J. ACM, August 2024.
John Bartholdi, Craig A Tovey, and Michael A Trick. Voting schemes for which it can be difficult to tell who won the election. Social Choice and welfare, 6:157-165, 1989.
Aaron Bernstein, Danupon Nanongkai, and Christian Wulff-Nilsen. Negative-weight single-source shortest paths in near-linear time. In 2022 IEEE 63rd Annual Symposium Foundations of Computer Science (FOCS), pages 600-611. IEEE, 2022.
Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, and Yuanzhi Li. An homotopy method for &p regression provably beyond ceff-concordance and in input-sparsity time. In Proceedings of the 45th annual ACM Symposium on Theory of Computing (STOC), pages 1130-1137. ACM, 2018.
Emmanuel J. Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 96))717-772, 2009.
Ioannis Caragiannis, Ariel D Procaccia, and Nisarg Shah. When do noisy votes reveal the truth? In Proceedings of the fourteenth ACM conference on Electronic commerce, pages 143-160. ACM, 2013.
Li Chen, Rasmus Kyng, Yang P Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 612-623. IEEE, 2022.
Michael B. Cohen and Richard Peng. l row sampling by lewis weights. In Proceedings of the 47th annual ACM Symposium on Theory of Computing (STOC), pages 183-192. ACM, 2015.
Vincent Conitzer and Tuomas Sandholm. Common voting rules as maximum likelihood estimators. In Proceedings of the 21 Annual Conference on Uncertainty in Artificial Intelligence (UAI), pages 145-152, Edinburgh, UK, 2005.
Vincent Conitzer, Andrew Davenport, and Jayant Kalagnanam. Improved bounds for computing kemeny rankings. In AAAI, volume 6, pages 620-626, 2006.
Vincent Conitzer, Matthew Rognlie, and Lirong Xia. Preference functions that score rankings and maximum likelihood estimation. In Proceedings of the Twenty-Firs International Joint Conference on Artificial Intelligence (ICCAI), pages 109-115, 115, Pasadena, CA, USA, 2009.
Vincent Conitzer, Markus Brill, and Rupert Freeman. Crowdsoureing societal tradeoffs. In Proceed- ings of the Fourteenth International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 1213-1217, Istanbul, Turkey, 2015.
Vincent Conitzer, Rupert Freeman, Markus Brill, and Yuqian Li. Rules for choosing societal tradeoffs. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, pages 467, Phoenix, AZ, USA, 2016.
Edith Elkind and Arkadii Slinko. Rationalizations of voting rules, In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, editors, Handbook of Computational Social Choice, chapter 8. Cambridge University Press, 2015.
Arpad Elo. The rating of chessplayers, past and present. Arco Pub., 1978.
Ulle Endriss. Judgment aggregation. F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, editors, Handbook of Computational Social Choice, chapter 17. Cambridge University Press, 2015.
Jean Mundahl Engels and Paula Diehr. Imputation of missing longitudinal data: a comparison of methods. Journal of clinical epidemiology,
976, 2003.
Mohsen Ahmadi Fahandar, Eyke Hüllermeier, and Inés Couso. Statistical inference for incomplete ranking data: the case of renk-depen coarsening. Proceedings of the 34th International Conference Machine Learning- Volume 70, pages 1078-1087 JMLR. org, 2017.

---

Shengbo Guo, Scott Sanner, Thore Graepel, and Wray Buntine. Score-based bayesian skill learning. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 106-121. Springer, 2012.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023.
Aric Hagberg, Pieter Swart, and Daniel Chult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Lab.(LANL), Los Alamos, NM (United States), 2008.
Ralf Herbrich, Tom Minka, and Thore Graepel. Trueskill A bayesian skill rating system. In Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems, pages 569-576, 2006.
David R Hunter et al. Mm algorithms for generalized bradley-terry models. The annals of statistics, 32(1):384 2004.
Eric Jones, Travis Oliphant, and Pearu Peterson. Scipy: open source scientific tools for python, 2014.
Dimitris Karlis and Ioannis Ntzoufras. Bayesian modelling of football outcomes: using the skellam's distribution for the goal difference. IMA Journal of Management Mathematics, 20(2):133-144 2008.
John Kemeny. Mathematics without numbers. Daedalus, 88:575-515 591, 1959.
Yehuda Koren, Robert Bell, and Chris Volinsky, Matrix factorization techniques for recommender systems, Computer, 42(8):30-37,
D. Lewis. Finite dimensional subspaces of lp- Studia Mathematica, 63(2):207-213 1978.
Yin Liu. Learning to rank for information retrieval. Foundations and Trends Information Retrieval, 333)225--21,,000 2009.
Michael J Maher. Modelling association football scores. Statistica Neerlandica, 36(3):109-118, 1982.
Marina Mcila. Kapil Phadnis, Arthur Patterson, and Jeff Bilmes. Consensus ranking under the exponential model. Proceedings of the 23rd Anmual Conference on Uncertainty Artificial Intelligence (UAI), pages 284-294, Vancouver, BC, Canada, 2007.
Ritesh Noothigattu, Snehalkumar Gaikwad, Edmond Awad, Sohan Dsouza, Tyad Rahwan, Pradeep Ravikumar, and Ariel Procaccia. A voting-based system for ethical decision making. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018
Tapio Pahikkala, Exgeni Tsivtsivadze, Antti Airola, Jouni Järvinen, and Jorma Boberg. An efficient algorithm for learning to rank from preference graphs. Machine Learning, 75(1):129-16) 2009.
Jason D. M. Rennie and Nathan Srebro. Fast maximum margin matrix factorization for collaborative prediction. In Proceedings of the 22nd International Conference on Machine Learning, pages 713-719, 2005.
Fiona M Shrive, Heather Stuart, Hude Quan, and William A Ghali. Dealing with missing data in multi-question depression scale: comparison of imputation methods. BMC medical research methodology, 6(1):57, 2006.
Hossein Azari Soufiani, David C Parkes, and Lirong Xia. A statistical decision-theoretie framework for social choice. In Advances in Neural Information Processing Systems, pages 3185-3193, 2014.
Lirong Xia. Quantitative extensions of the condorcet jury theorem with strategic agents. In AAAI, pages 644 644-650, 2016.
H. Peyton Young and Arthur Levenglick. consistent extension of Condorcet's election principle. SIAM Journal of Applied Mathematics, 35(2):285-300, 1978.
12

---

H. Peyton Young. Condorcet's 's theory of voting. American Political Science Review, 82:1231-1244, 1988.
H. Peyton Young. Optimal voting rules. Journal of Economic Perspectives, 9())511-44 1995.
Hanrui Zhang, Yu Cheng, and Vincent Conitzer. A better algorithm for socictal tradeoffs. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 2229-22366 2019.
Zhibing Zhao, Tristan Villamil, and Lirong Xia. Leamning mixtures of random utility models. In Seirty-Second AAAI Conference on Artificial Intelligence, 2018
13

---

A Subsampling Judgments
A.1 Subsampling Judgments When
[1,
In this section, we show that for E [1, 2]. we can reduce the number of judgments while incurring a small approximation enror by subsampling the input judgments.
Algorithm 1 Subsampling Judgments
Input: bp QRJA instance (N, J, w). subsample count M E N, and subsampling weights RR".
Output: bp QRIA instance (N, J', ,w').
for each E (1, m). 1: Let qi < ΣØ
2: for E (1,2,..., M) do
(1,2..... m) with probability tu- 4: Let J c Jæ and wi M.
3: Sample
5: end for
6: return (N,J',"').
Algorithm takes as input an lp QRJA instance, parameter M, and vector s E Rm samples M judgments from the input instance (with replacements) with probability proportional to and outputs new ep QRJA instance with the sampled judgments. The weight of any judgment the output instance is divided by its expected number of occurrences in the output instance, so that the expected total weight of any judgment preserved after subsampling.
then
Theorem 3. Fix absolute constants E [1,2] and s > O. Given any E, QRJA instance [N, w), we can compute subsampling weights E Rmm in time O(m + n=+o(())) where w is the matrix multiplication exponent. For these weights and M Ó(), Algorithm 1 with high probability outputs an Ep QRJA instance (N,J', w') whose optimal solution is an (1 + -approximate solution of the original instance.
To obtain the theoretical guarantee of Algorithm 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 many real-world datasets (see Appendix A.2)).
Proof of Theorem 3: For an tp QRJA instance (N,J, J. w), define matrix A E [=m((+1))
if d; if j
Auj
if = n otherwise.
The Lewis weights for this Ep QRJA instance is defined as the unique vector s E IR" such that for each i (1.2....,m) m),
a, AATS -TaT =8
2/v
where S = diag(s) and a; 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 E [1,2], the Lewis weights can be computed in ((nnz(A) n2 w = O(m + n=()())) time.
For R", we have
m
Wa Ta.
Lb.
l.l..
Thus the 4p QRJA loss is always equal to || A I for some E Ra+1 The theorem then follows
from the E, Matrix Concentration Bounds in Cohen and Peng 20155
14

---

A.2 Subsampling Experiments
We also conduct experiments to test the performance of our subsampling algorithm (Algorithm) . which speeds up the (approximate) computation of QRJA large datasets. In the experiments, specify the subsample rate o, let M = [om] and be an all-ones vector in Algorithm |
Experiment setup. We run & and lz QRJA with instances subsampled by Algorithm ! on the datasets. For each a = {0.1, 0.2, ........ 1.0].
we run & and & QRJA times and report their average performance on both metries with error bars. Due to the space constraints, only show the results on Chess in Fig. in this section. The results on other datasets are deferred to Appendix
0.68
00.66
1.3
0.64
0.62
1.1
0.60
0.2
0.4
0.5
0.8
1.0
0.2
0.4
0.6
0.8
1.0
Subsample Rate (o)
Subsample Rate (60
(a) and & QRJA's ordinal accuracy on Chess
(b) and E2 QRJA's quantitative loss on Chess
Figure 5: The performance of & and & QRJA Chess after subsampling judgments using Al- gorithm with equal weights for all judgments. The subsample rate a means M [am in Algorithm] T Error bars indicate the standard deviation. The results show that Algorithm Can reduce the number of judgments to factor of 0.4 with a minor performance loss on Chess.
Experiment results. As is shown in Fig. with equal weights for all judgments, Algorithm 1 can reduce the number of judgments without significantly hurting the performance of l and & QRJA as long as the sampling rate is not too small (2 0.4 for Chess). This shows that Algorithm is practical algorithm for subsampling judgments QRJA. We also note that as the experiments show, lg QRJA is more robust to subsampling than & QRJA.
B Missing Proofs in Section
B.1 Proof of Theorem 1
Theorem 1. Let p 2 1 be an absolute constant. Consider Ep QRJA in Definition with loss function f(1) = (P. Assume all input numbers are polynomially bounded in m. We can solve Ep QRJA in time O(m)+o(1)) with exp(- log" m) additive error for any constant
Proof of Theorem (when p 1): We proved Theorem for p in Section 4.1 It remains to consider p 1.
When 1, the overall loss function of QRJA is sum of absolute values of some linear terms. We can therefore formulate & QRJA as the following linear program (LPP,, as observed [Zhang et al. 2019
minimize subject to
I m
i=1 (2, + 2,
2 2 Fo. Eb,
Vi E [m]
2. 2 Y/ + Tb. Ta.
Vi E m
27 0, 2, 2
Vi E [m]
4;
E IR
Vi E
[n]
For this I.P. Zhang et al. 2019 gave faster algorithm than using general-purpose L.P solvers.
Lemma 3 Zhang et al. 2019.. There is reduction from & QRJA to Minimum Cost Flow with O(n) vertices and (()) edges in (T (n, m, W)) time, where Tsssp(n, m, W) is the time required solve Singl-Souree Shortest Path with negative weights on graph with vertices, edges, and maximum absolute distance W.
Using this reduction (Lemmal together with the SSSP algorithm in Bernstein et al, 2022 and the minimum cost flow algorithm in Chen et al. 22022). we have algorithm for & QRJA that runs in time O Omm++(11) ++0(1)).
15

---

B.2 Proof of Theorem 2
Theorem 2. For any p there exists constant c such that NP-hard approximate lp ORJA within multiplicative factor of (1 ,
Recall the reduction from Max-Cut to Ep QRJA: Given an instance of Max-Cut with an undirected graph G = E), let n. IV = |نا and let w2 = I-p
2n + L, W1 nw2 + 1. We construct
an instance of ep QRJA with n + 2 candidates V {u(+), oltt) and O(n + m) quantitative relative judgments. Specifically, we construct the followings judgments:
(o(t), (()), with weight w1
(o(*), u, 0) with weight w2 for each E V.
(o()) u, 0) with weight w2 for each u E V.
(u, 1), (u, 1) with weight 1 for each (u, v) E E.
To show validity of the reduction above, we will first establish integrality of any optimal solution. Lemma 4. Any optimal solution of the ey QRJA instance described in the above reduction integral. Moreover, all variables must be either O or 1 up to a global constant shift.
We need inequality for the proof of Lemma 4
Lemma 5. For any d E (0, 2 p (0, 1).
1 (1 11-11 d)p S pdP.
Proof of Lemma
Fix p E (0, 1). Let f(d) = pdd 1 + (1 dyp. We have
(' = p(pdp-1 - (1-d)p-1)
Note that f' is decreasing for d E (0, 1). In other words, f is single peaked on (0, 4 and continuous at O. Now only have to check that f (0) 2 which is trivial, and f (3) 0. For the latter, let
((p) (p 1)0.5" 1.
g()) 2 for p E [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
Proof of Lemma 4 Let Ta be the potential of candidate a in lp QRIA. W.l.o.g. assume that in any solution, Fy(o) 0. We first show that if 2,(9) & 1, then moving it to strictly improves the solution. d. By moving Fete) to 1, decrease the loss the judgment (o(1), ((()) 1) by widP. For other judgments (v((), u) incident on (((), the loss increase by no more than wyd?, since
Suppose (ryc
(I + d) Eul?" (x, Zu dp.
Overall, the cost decreases by at least
wh d mw2d" d 0.
Now we show moving any fractional x, to the closest value in {0, 1} strictly improves the solution. There are cases:
Tu E (0, 1). W.L.o.g. Eu E (1, 2] and we try to move it to by a displacement of d = r.. The total loss on (u(*), u, 0) and (u(0, 0) decreases by w2 (dd + (1 d) 1), while the total cost on judgments of form (u, v, 1) and (v, u, 1) can increase by no more than ra(d + (2 - d)" 2P).
With Lemma 5 we see that
W2 + (1 - d) 1) 2 w2(d -pPP)
2nd
2 (d) + +2+ + d)p -
So, there is positive improvement from rounding T...
16

---

$ [0, 1]. W.l.ogg Za < 0 and we try to move it to 0 by a displacement of = - -u. The total loss on (e(*), u, 0) and (v(9) 0) decreases by w2(dd + + d)² 1), while the total cost on edges of form (u, v, 1) and (v, u, 1) can increase by no more than n(d d) 2*). And
W2 (d + (1 d) 1) 2 w2d
> 2nd
2 n(d + (2 d)p 2²).
We conclude that in any optimal solution, T.((s) = 0, (1) = 1, and for any V. E {0,
Next, we present lemma that shows the connection between solutions in the Max-Cut instance and those in the constructed Ep QRJA instance.
Lemma 6. A Max-Cut instance has solution of size at least k iff its corresponding lp QRJA instance has a solution of loss at most rew2 + 2(m - k) k2P. Moreover, with such a solution to the lp QRJA instance, one construct Max-Cut solution of the claimed size.
Proof of Lemma 6; Given a Max-Cut solution (S) of size at least k setting the potentials of the vertices in and to be and 1 respectively gives an lp QRJA solution with loss at most nu2 + 2(m k) A2"..
Given ép QRJA solution of loss at most nwr + 2(m - ke) + k22 we first round the solution the form stated in Lemma This improves the solution. The two vertex sets U = {u V a<u)) = 0} and V (v E V x<)) = 1} then form a Max-Cut solution of size least k.
We are now ready to prove Theorem
Proof of Theorem 2 According Lemma any approximation with additive error less
than 2 2" of the constructed ép QRJA instance can be rounded to produce an optimal solution to
Max- Max-Cut. Since Max-Cur ut is NP-Hard and the constructed lp QRJA instance's optimal solution has
loss (n² + m), the theorem follows.
C Additional Experiments
C.1
L2 Variant of Quantitative Loss
1.3-
1.2965
Quantitative
100
84.8865
82.2005
80
1.2
1.1
1.0
0,9424
0.9512
13.1296
1.0858
1.0453
LIORIA
L2ORJA
LIQRJA
(a) L2 Quantitative loss on Chess
(b) L2 Quantitative loss on
1.10
0.3483
1.05
1.0363
0.32
0.90
0.95
0.9973
0.30
0.2937
0.2891
0.2859
0.85
0.7630
0.7576
0,7580
0.28
L1ORJA
Madian
Madian
Mean
MF
(c) 1.2 Quantitative loss on Marathon
(d) L. Quantitative loss on Codeforces
Figure 6: L.2 quantitative loss of the algorithms all four datasets used in Section 5 Error bars are not shown here as the algorithms are deterministic. Similar to Fig. 4 the results show that both versions of QRJA perform consistently well across the tested datasets.
We include in this subsection experiment results using average squared enror as the quantitative metric. call this metric 1.2 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 1.2 quantitative quantitative loss of the trivial prediction that always predicts 0 for all pairs
as the average squared error of the predictions, and normalize it by the 1.2
17

---

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 (I.I) quantitative loss in Section [
Additionally, & QRJA performs slightly better than & QRJA this metric. This is expected because this metric is more aligned with the &g QRJA's loss function.
C.2 Performance Experiments on More Datasets
We include in this subsection the performance experiments 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 pottps://vre crross-tablee (aables.com)) from 2000 to 2023. Each contest 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 FI-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 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 this modified dataset because all other datasets we use in the experiments are sparse datasets (i.e., contestants participate in small fraction of the contests average), so want to what happens dense ones. There are 327 contests and 17 contestants in total.
We evaluate & and & QRJA using the same metrics against the same set of benchmarks in Section 5 We highlight a few extra observations below.
on these three datasets. The results are shown Fig. 7
Extra observations on Tabses. In terms of ordinal accuracy, Median performs the best among the tested algorithms on 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. and 7 This shows that although Median is occasionally good in performance, fails in other cases.
Extra observations on F1-Full. On F1-Full, both MF and & QRJA and perform considerably worse than & QRJA. This is not seen in other datasets. We believe this is because our score calculation results a large variance in contestants' scores F1-Full, which makes it harder for these methods to make good predictions. This also shows that & QRJA is more robust to datasets with large variances in contestants' performance than these methods. We also notice that Borda and Homeny-YYung perform well on F1-Full, which is consistent with their good performance on FI.
Extra observations 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 dense dataset like Codeforces-Core, most algorithms make good predictions. Moreover, MF does not have a clear ad advantage over other algorithms in our problem even if the dataset is dense.
C.3 Subsampling Experiments on More Datasets
We also conduct the subsampling experiments Appendix A.2 on all other 5 datasets. The results shown in Fig. g
Experiment results. The message here is the same as that in Appendix A.2 In particular, Algorithm I can reduce the number of judgments with only minor loss in performance as long as the subsample rate a not too small. Note that some of the figures, like Fig. Sc the errors seem to be large visually. This is because of the small scale of the y-axis (only 0.6% for Fig, 8ch. The actual errors
18

---

0.80
76.3%
75.4%
77.3%
Accuracy
1.1
1.0521
Quantitative
0.75
0,9055
0,70
70.5%
0.9
0.8994
0.8
LIORJA L2ORJA
Median
Mean
Borda
K
MF
LIORYA
L2ORJA
Median
Mean
MF
Ordinal accuracy Cross- Tables
(b) Quantitative loss Cross-Tables
1.25
0.62
51.3%
1.20
0.60
1.15
1.1173
1-1092
1.1195
0.56
57.0%
1.10
1.00
1.05
1.0411
LIORIA L2ORJA Median
Mean
Borda
Ke
Mf
LIORJA
L2ORJA
Median
Mean
MF
Ordinal accuracy Fl Full
(d) Quantitative loss
F1 Full
0.73
0.72
72.3%
72.2%
72.0%
22.0%
0.840
0,8430
0.835
69.8%
0.830
0.8260
0.8272
0.8280
0.825
LIORIA LZQRJA Median
Mean
Borda
MF
LIQRIA
LZORIA
Median
Mean
MF
(e) Ordinal accuracy on Codeforces-Core
(l) Quantitative loss Codeforces-Core
algorithms on Tables, FI-Full, and Codeforces- Core.. Error bars not shown the algorithms deterministic. The results show that & QRJA still performs consistently well across the tested datasets. However, l QRJA performs considerably worse than & QRJA on F1-Full. This is not seen in other datasets.
Figure 7: The performance
small. Moreover, we observe that the performance of le QRJA is slightly more robust subsampling than that of E QRJA. This is consistent with the results in Appendix A.2
C.4 Experiments about Matrix Factorization
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 their implementation details.
Recall that in Section D
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 1. We describe the implementation details below.
Low-Rank MF. Recall that in the context of our experiments, we can view each contestant as row and each contest as a column. The score of contestant in contest is the entry in the corresponding row and column. A E Raxm as the product of two low-rank matrices UV where U E R r V E m for some small r. Note that in our experiments, the algorithm required to predict new column of A with known entries. Therefore, cannot directly apply this method since the corresponding row of V will remain unchanged after initialization. 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 fixed number of epochs on a deterministic initialization to keep the results deterministic. We test 2, 5 in this subsection.
classical model of MF Koren et al. 2009 is factorizing
solve this problem,
Additive ME. We also consider an additive variant of MF. For x E R y RR". this method be viewed contestant i's skill level, and yj can be
predicts Arj 2; yj- Here, interpreted as the (inversed) difficulty of contest j. 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; + yj holds for the known entries. We also use the standard sum the squared loss function and use gradient descent for fixed number of epochs a deterministic initialization to keep it deterministic.
Performance experiments. We first evaluate these variants of MF using the same metrics as in Section on all datascts. The results are shown in Fig, 9 We can that RI MF and Additive MF
19

---

0.66
1.4
0.65
L2
0.64
0.63
L2
0.62
1.0
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
0.8
1.0
Subsample Rate (o)
Subsample Rate (c)
(a) QRJA's ordinal accuracy on
QRJA's quantitative loss on F1
0.796
0.960
0.:795
8 0.7764
0.950
0.793
0.945
8 0.7792
0.791
0.940
0.790
0.935
0.2
0.4
0.5
0.8
1.0
0.2
0.4
0.5
0.8
1.0
Subsample Rate (o)
Subsample Rate (0)
(c) QRIA's ordinal accuracy on Marathon
(d) QRJA's quantitative loss on Marathon
0.545
Accuracy
0.652
0.654
0.540
0.650
0.535
0.648
0.530
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.5
0.8
1.0
Subsample Rate (o)
Subsample Rate (x)
(c) QRJA's ordinal accuracy on Codeforces
(f) QRJA's quantitative loss on Codeforces
0.76
Accurayy
0.74
8
1.3
1.2
0.72
1.1
0.70
10
0.9
0.6
0.8
Subsample Rate
Subsample Rate (x)
(g) QRJA's ordinal accuracy on Cross-Tables
(h) QRJA's quantitative loss on Cross-Tables
0.62
1.16
00.61
1.14
0.660
0.59
1.10
1.08
0.57
1.06
0.56
0.6
1.0
0.4
Subsample Rate
Subsample (0)
(i) QRJA's ordinal accuracy on F1-Full
(j) QRJA's 's quantitative loss on FI-Full
0. 7274
0.87
5 0.722
0. 720
718
0.85
716
0.83
0.5
Subsample
Subsample (s)
(k) QRJ''s ordinal accuracy Codeforces Core
()) QRJA's quantitative loss Codeforces-Con
Figure 8: The performance of & and l2 QRJA after subsampling judgments using Algorithm ] with equal weights for all judgments. The subsample rate means M [am] in Algorithm Error bars indicate the standard deviation. The results show that Algorithm I can reduce the number of judgments to factor less than 1.0 with 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.
20

---

66.6%
Ordinal Accuracy
67.3%
1.4199
Quantitative
0.65
1.3
1,2705
0.60
1.2
0.55
53.0%
51.0%
1.1
1.0
0.9689
0.9364
0.9
R1 MF
R2 MF
RS MF
Add NF
R1 MF
R2 MF
RS MF
Add MF
(a) MF's ordinal accuracy Chess
(b) MF's quantitative loss Chess
0.70
50
48.7361
0.60
40
0.55
0.45
0.40
44.9%
46.8%
20
10
1.4436
17,6003
3,2104
MF
(c) MF's ordinal accuracy on F1
(d) MF's quantitative loss on F1
0.85
0.80
79.4%
2,1033
0.75
0.70
1.1
0.65
55.2%
1.0
0.9328
0.9359
MF
MF
RS MF
Add
(e) MF's ordinal accuracy on Marathon
(f) MF's quantitative loss on Marathon
0.86
65 888
65.7%
3.5
3.0
2.9451
2,8708
2.5
0.64
2.0
0.63
1.5
0.62
0.60
0.61
60.9%
0.5
0.0
1.0
0.5254
0.5247
RI MF
R2 MF
R5 MF
Add MF
RI MF
R2 MF
RS MF
Add MF
(g) MF's ordinal accuracy Codeforces
(h) MF's guantitative loss Codeforces
0.76
75.1%
0.74
71.9%
0.96
0.88
0.8734
0.84
0.68
68.2%
0.82
0.80
0.8157
1.81
MF
R2 MF
MF
Add
R2
MF
(i) MF's ordinal accuracy on Cross-Tables
(j) MF's quantitative loss on Cross- Tables
57.2%
1.40
1.35
1.3490
0.56
1.30
0.54
1.25
1.2329
1.2321
0.50
49.5%
50.5%
1.20
1.15
1.10
1.1142
0.48
1.05
MF
MF
MF
Add
MF
(k) MF's ordinal accuracy on F1-Full
(I) MF's quantitative loss on F1-Full
0.73
72.4%
0.8604
72.0%
0.86
0.71
0.85
0.84
0.8430
0.8340
0.70
69.9%
0.83
0.8301
R1 MF
R2 MF
R5 MF
Add MF
R1 MF
R2 MF
RS MF
Add MF
(m) MF's ordinal accuracy Codeforces-Core
MF's quantitative loss Codeforces-Core
Figure 9: The performance of different variants of Matrix Factorization. The results show that R1 MF and Additive MF generally have similar performance, In contrast, R2 and R5 MF perform worse than the former.
21

---

Accuracy
0.65
R1
13
R1
0.60
11
R2
0.55
R5
1.0
25
50
75
100
125
150
175
200
150
175
200
Number of epoches
Number epoches
(a) MF's ordinal accuracy on Chess
(b) MF's quantitative loss on Chess
0.65
00.60
40-
0.55
0.50
20
0.45
10-
0.40
0
200
400
600
800
1000
200
400
600
800
1000
Number of epoches
Number of epoches
(c) MF's ordinal accuracy F1
(d) MF's quantitative loss on F1
0.80
0.755
1.3-
0.770
0.65
1.2
0.60
1.1
0.55
1.0
0.50
Number opoches
Number opoches
(c) MF's ordinal accuracy on Marathon
(f) MP's quantitative loss on Marathon
0.66
Accuraky
-0.55
0.64
Locs
w
0.63
0.62
0.61
0
20
40
60
80
100
20
40
60
80
100
Number of epoches
Number of epoches
(g) MF's ordinal accuracy on Codeforces
(h) MF's quantitative loss on Codeforces
0.74
0.722
0.95
0.70
0 0.90
0.68
0.66
0.64
100
200
300
400
500
100
200
300
400
500
Number of opoches
Number of opoches
(i) MF's ordinal accuracy Cross-Tables
(j) MF's quantitative loss Cross-Tables
0.575
0..330
0.525
g 1.20
0.475
1.30
1.15
1.05
1000
Number epoches
Number epoches
(k) MF's ordinal accuracy on F1-Full
(I) MF's quantitative loss on F1-Full
0.72
Accureyy
0.70
0.97
0.90
0.68
0.88
0.66
0.86
20
40
60
80
100
20
60
80
100
Number of epoches
Number of epoches
(m) MF's ordinal accuracy on Codeforces-Core
(n) MF's quantitative loss on Codeforces-Core
Figure 10: The performance of Matrix Factorization with different numbers of training epochs on all datasets. The results generally show that RI MF outperforms R2 and R5 MF. Moreover, on some datasets, R2 and R5 MF's performance worsens as the number of training epochs increases. In contrast, RI MF's performance improves as the number of training epochs increases.
22

---

Entrywise L1 Loss
0.5738
0.4
Entrywise L2 Loss
0.3936
0.3-
0.3196
0.2
0,2318
0.2163
0,2580
0.1
0,0782
0.0989
0.0
(a) Entrywise LI
on Chess
(b) Entrywise loss on Chess
0.8
0,6802
0.5
0,4837
0.4
0.3
0.1877
0.2
0.1126
0.1159
0.0335
0,0333
0.0
0.0
Median
Mean
MF
R2 MF
R5 MF
Median
Mean
R1 MF
R2 MF
R5 MF
(c) Entrywisc LI loss on F1
(d) Entrywise L2 loss
Fl
0.8
0.6738
0.30
0.25
0.4
0.3958
0.2
0,1342
0,1243
0.1430
0.0269
0.0260
0.0264
0.10
Median
Mean
R2 MF
RS MF
Median
Mean
A1 MF
MF
MF
(c) Entrywise L.1 loss on Marathon
(f) Entrywise 1.2 loss on Marathon
0,4389
0,4848
0.40
0.4
0.35
0.3
0.30
0.3003
0.3061
6.1
0.25
0.0
0.0013
0,0012
0.0016
(g) Entrywise on Codeforces
(h) Entrywise loss Codeforces
0.6421
0.55
0.5262
0.50
0.60
0.45
0.55
0.5304
0.40
0.3754
0.50
0.4807
0,4767
0.6976
0.3153
0,2869
0.3182
Median
Mean
R1 MF
R2 MF
R5 MF
Median
Mean
R1 MF
R2 MF
R5 MF
Entrywise L1 loss Cross Tables
(j) Entrywise L2 loss Cross Cross-Tables
1,0251
0.8544
0.9462
0.9
0.8
0.6903
0.8242
0.8179
6.7
0.6
0.6187
0.5267
0.6364
0,7097
0.6
Median
Mean
R2 MI
R5 MF
Median
Meen
R1 MF
MF
(k) Entrywise L1 loss on F1-Full
(l) Entrywise L2 loss on F1-Full
0.445
0.4446
0.4457
0.240
0.235
0,2368
0,440
0.4372
0,4400
0.225
0.2284
0,2243
0.2207
0.2174
0.430
Median
(m) Entrywise L1 loss on Codeforces-Core
(n) Entrywise 1.2 loss on Codeforces-Core
Figure 11: Entrywise LI and L2 loss of Matrix Factorization, Mean, and Median. The results show that on most datasets, R1 MF outperforms R2 and R5 MF. The exceptions are F1-Full and Codeforces-Come Moreover, Matrix Factorization does not have clear ad advantage over Mean and Median on any dataset terms of entrywise metrics.
23

---

generally have similar performance. In contrast, R2 and R5 MF perform worse than the former. We therefore choose to present RI MF in Section
Low-Rank MF's performance over training. The observation that R2 and R5 MF perform worse than R1 MF is surprising to To confirm this observation, plot the performance of these variants of MF with different numbers of training epochs on all datasets. The results are shown in Fig. Io] We can see that RI MF generally outperforms R2 and R5 MF in terms of both ordinal accuracy and quantitative loss when trained for long enough. Moreover, RI 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, FI, 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 entrywise metrics. As the metrics in Section 5 are defined in pairwise fashion and might not be well-suited for MF, we also evaluate the performance of MF in terms of entrywise LI 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. TT 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 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 Codeforces-Core. These two datasets are different from the other ones in that F1-Full's '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, RI MF and Additive MF, which are similar performance, generally perform better than R2 and R5 MF. Therefore, we choose to include only the results of R1 MF in Section
D Axiomatic Characterization of QRJA
We characterize Ep QRJA by giving a set of axioms for the family of transformation functions ʃ of pairwise loss that consider. We show that those transformation functions considered in Ep QRJA are essentially the minimum set of functions satisfying these axioms.
Recall that for each judgment about and b where is better b by y units, the absolute error of the prediction vector x on this pair Ix. - rh y). Using this as the loss function, we obtain the & 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 l, QRJA for any positive rational number p E +.. Note that restricting p to be rational is without loss of generality, since the output of Ep QRJA is continuous in p.
We consider transforming the absolute error by transformation function f to obtain the actual pairwise loss, which is f([2a- T6 yl). For l QRJA, the transformation function is f(t) t", To characterize QRJA as family of rules (for different E Q+). we give axioms for the corresponding family of transformation functions, i.e., 1r for p E Q+. Let F be a family of transformation functions.
Below are the axioms we consider:
Identity. There is an identity transformation fo E F, such that fo(t) f for any t 0. Invertibility. For each E F, there is f2 E F such that fa composed with f2 is identity, i.e., for any 2 0,
(f((())) =t. Closedness under multiplication. For any f1, E F, there exists Sa E F such that for any t
ft(t (t( = fa(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
24

---

transformation fo where fo(t) = t in F², (This corresponds to & QRJA.) Then by the third axiom, for any k E 24. S also in F², where (t) = 1. And by the second axiom, for any E B4. fo also in Fr, where (1) (2/k, This is because fo (Jb(L))
Finally, for any Q+ ( ") is in F*, where (t) = t².
where r - p/g for p,q E E., by the third axiom, fö = (fu
Note that the above argument establishes that FF contains all transformation functions corresponding to QRJA, i.e.
ftr r Q+)
Below we show the other direction, i.e. ft" r E Q+} satisfy the axioms, and as result,
FC (t' | Q+}-
For f1(1)= = (2) where r1, Q+. we have
fi(t) f2(t) = tritts,
where 71 + 12 E Q++ and
fi(f((t) = =( = = where 71 E Q+. This implies F S {1" | Q+). Thus F = {1" r Q+3 as desired.
E
Copyright Information for Datasets Used
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.
Chess. Copyright: @ 2023 Tata Steel Chess Tournament. Data collected is sub-
ject to the website's Terms of Conditions, available at https::/ratastteel.. com/
terms- -ntdiaa-aacconniiiiion
F1. Copyright: ② 2003-2024 Formula One World Championship Limited. Data collected subject to the website's s Terms of Use, available httpss//accoumm..ormmlll.l.oo
en/terms-of-use
Marathon. Copyright: 2000-2024, All Rights Reserved by MarathonCuuide.com
LLC. Data collected is subject to the website's Policy, available at hhtps://www cfm
Codeforces. Copyright: @ 2010-2024 Mike Mirzayanov, Data collected is subject the website's Terms and Conditions, available at https:://coe::: crces. com/terms
Cross-Tables Copyright: @ 2005-2024 Seth Lipkin and Keith Smith. Data collected is
subject to the website's 's Policy, available at witttts: :/www../www... cross- trooss-tables. ctt..ccomppite com/privacy html
25

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The 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 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.
is fine to include aspirational goals as motivation as long 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:
We briefly discuss the limitations our work in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those 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 authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might 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 address problems of privacy and faimess.
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 '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: [Yes]
26

---

The theoretical results are stated with the full set of assumptions and their proofs are provided either in Section or in Appendices A and B
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 the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
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 the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken 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 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 is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how 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 way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
27

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code and data provided in the supplemental materials, including automated test script to reproduce the experimental results stated the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cc
aublic//uuddes/Coeeeubbiis wtt.eeeeuuumiisioooooooooooo for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is 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 NeurlPS code and data submission guidelines (https
/ wwtps/cccpblccggiuiieeeee
Stteee//CooSSSemsssS.Si.a www.ssssiicggsoooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. 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 as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is 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: [Yes]
Justification: The experiment settings in Section 5 and Appendices A and 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 the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [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 emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
28

---

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.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог 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 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: [Yes]
Justification: It is stated in Section that "All experiments are done on a server with 56 CPU and 504G RAM. The experiments in Section [5 and Appendices A and take around weeks in total to run on this server. No GPU is used."
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httpp//////eeeigg..ccco/p/ttt///
Answer: [Yes]
Justification:
We have reviewed the Code of Ethics and believe that our paper conforms to it.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We briefly discuss the boarder impacts of our work in Section 7
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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not release data or models that have high risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses 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: [Yes]
Justification: Any existing code package used in the paper is properly cited Section S] 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
30

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com/ com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if 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 explain the purpose of the file and the functions defined in it.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/codeemmodll as part 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 used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
31

---

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


Reviews:
[{"review_id": "6IDN5XlUgQ", "reviewer": "Reviewer_iMha", "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 \n$$\\sum_i w_i f(|x_{a_i}-x_{b_i}-y_i|)$$\nfrom collection of quantitative relative judgement $J_i = (a_i,b_i,y_i)$ where $f$ is some increasing function. \n\nThe 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.", "questions": "Can you address the first point in weakness of Theorem 1?\n- why dual program\n- Limitation of using $p$-norm regression\n- Reduction to Chen et al. 2022", "limitations": "The paper addresses the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "+) The combination of social choice and ranking prediction is pretty neat.\n+) The dichotomy results on the degree of the monomial is intuitive and interesting.", "weaknesses": "1. The technical writing is not very friendly or informative.\n- 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?\n- 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. \n\n2.  I feel the empirical results should be compared to more relevant literature. \n  - 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. \n  - Another related area may be item response theory, where contestants have expertise and events have difficulty.\n\n3.  The presentation should be more cogent\n- It is not clear to me how the model conceptually addresses issues in those motivating examples (Examples 1 to 3).   \n- 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$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your recognition and thoughtful comments.\n\nWe are glad that you find the topic of our work neat and our theoretical dichotomy results intuitive and interesting. Below, we respond to the questions raised in your review.\n\n**On the first point in Weaknesses**\n\n$\\\\ell\\_p$ QRJA is indeed a special case of sparse $p$-norm regression, but it has additional structure: for $\\\\ell\\_p$ QRJA, the matrix $A$ in $\\\\min \\\\|Ax-z\\\\|\\_p$ has exactly two nonzero entries per row and they sum to $0$. This is crucial because it allows the dual of $\\\\ell\\_p$ QRJA to correspond to a flow problem.\n\nWithout this additional structure, applying the state-of-the-art algorithm for sparse $p$-norm regression \\[1\\] would result in an $\\\\Omega(m \\+ n^{\\\\omega})$ runtime for $\\\\ell\\_p$ QRJA, where $\\\\omega \\\\geq 2$ is the matrix multiplication exponent. This is significantly slower than almost linear time.\n\nWith this additional structure, we can solve $\\\\ell\\_p$ QRJA in almost-linear time using Theorem 10.13 of \\[2\\]: In Equation (4), one can view each entry $f\\_e$ in $\\\\mathbf{f}$ as the directed flow on an edge $e$, and the optimization constraints as flow conservation constraints. For edge $e$, its contribution to the total cost is $|f\\_e|^q \\- z\\_e f\\_e$, and the total cost is edge-separable and convex. This allows us to use Theorem 10.13 of \\[2\\]. \n\nWe will clarify this.\n\n**On the second point in Weaknesses**\n\nWe agree that many other approaches deserve mention in this context, including Elo and other methods. In our work, we had to select a subset of these methods to compare with QRJA. We chose Mean and Median due to their straightforwardness, Borda and Kemeny-Young from the social choice literature, and Matrix Factorization from the machine learning literature.\n\n**On the third point in Weaknesses**\n\nQRJA addresses issues in the motivating examples by considering the relative performance of contestants rather than their absolute performance in each contest. More specifically:\n* Example 1: Even if a contestant only participates in “easy” races, QRJA can better avoid over-rating their strength by using the relative performance data of other contestants in those races.\n* Example 2: If past data shows that Alice consistently beats Bob, and Bob consistently beats Charlie, the QRJA model will predict that Alice runs faster than Charlie, as it tends to be consistent with previous relative judgments.\n* Example 3: Although the Boston race indicates that Charlie is slightly faster than Bob, the other two races suggest that Bob is faster than Charlie by a large margin. To minimize inconsistencies across all judgments, QRJA will predict that Bob is faster than Charlie.\n\nWe focus on $\\\\ell\\_1$ and $\\\\ell\\_2$ QRJA because the almost-linear time algorithm for general values of $p \\\\geq 1$ relies on galactic algorithms for $\\\\ell\\_p$ norm mincost flow \\[2\\]. While standard gradient descent works for general values of $p$, its running time is too slow on large datasets like Codeforces and Cross-Tables. We acknowledged this in the conclusion: “An interesting avenue for future work would be to develop fast (e.g., nearly-linear time) algorithms for $\\\\ell\\_p$ QRJA with $p \\\\neq 1, 2$ that are more practical, and evaluate their empirical performance.” We will further clarify this.\n\n**References**\n\n\\[1\\] Bubeck, S.; Cohen, M. B.; Lee, Y. T.; and Li, Y. 2018\\. An homotopy method for $\\\\ell\\_p$ regression provably beyond self-concordance and in input-sparsity time. In Proc. of  \nthe 45th annual ACM Symposium on Theory of Computing (STOC).\n\n\\[2\\] Chen, L.; Kyng, R.; Liu, Y. P.; Peng, R.; Gutenberg, M. P.; and Sachdeva, S. 2022\\. Maximum flow and minimum-cost flow in almost-linear time. In Proc. of the IEEE 63rd Symposium on Foundations of Computer Science (FOCS).", "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": "5EzxYMQ5RV", "reviewer": "Reviewer_Fgap", "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.", "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. \n2. Please answer my question related to the motivation of the race in the weakness section. \n3. Please specify what simple algorithm you apply for $l_2$ norm in the experiment.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "+ QJRA problem is indeed interesting and important. \n+ The theoretical results are sound and non-trivial.\n+ Clear example demonstrate why simple methods do not work.", "weaknesses": "-The relationship between previous work. I don't quite see how this paper conceptually distinguishes itself from [Conitzer et al, 2016]. \nThe 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. \n- 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?\n- The proofs and the sketches are hard to follow with too many skips and magic numbers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful comments.\n\nWe are glad that you find our problem interesting and important, and our theoretical results sound and non-trivial. Below, we respond to the questions raised in your review.\n\n**On the first question**\n\nConitzer et al., 2015 \\[1\\] is a short visionary paper that proposes the abstract problem of setting numerical standards of societal tradeoffs such as “using 1 unit of gasoline is as bad as creating 3 units of landfill trash”. Conitzer et al., 2016 \\[2\\] axiomatically characterize a specific aggregation rule for the societal tradeoffs problem, which is mathematically equivalent to QRJA with loss function $f(x) \\= x$. Zhang et al., 2019 \\[3\\] study the computation complexity of the specific aggregation rule characterized in \\[2\\].\n\nConceptually, \\[1\\], \\[2\\] and \\[3\\] are all confined to computational social choice, since the societal tradeoffs problem was originally motivated by setting numerical tradeoff standards. In our work, the “relative judgments” to be aggregated can be those subjective judgments as in \\[1\\], \\[2\\] and \\[3\\], but they can also be produced by an objective process, like a race, rather than human judges. This gives us the opportunity to explore the interplay between social choice theory and the learning-to-rank community. In this sense, we \"apply social-choice-motivated solution concepts to the problem of ranking prediction\".\n\nOn the technical level, only \\[3\\] studies computational problems related to our work. However, the techniques used by \\[3\\] and our work are fundamentally different. \\[3\\] takes a linear programming-based approach, while we need to use convex optimization techniques. We present a non-trivial reduction to the convex minimum cost flow problem and utilize recent advancements for this problem \\[4\\] to solve $\\\\ell\\_p$ QRJA when $p \\\\geq 1$. To complement our results, we show that when $p \\< 1$, $\\\\ell\\_p$ QRJA is NP-hard by reducing from Max-Cut. None of these techniques are present in \\[3\\].\n\n**On the second question**\n\nWe observe that the “relative judgments” can also be produced by an objective process, like races. In this sense, races are instances of judgments, rather than the representation of judgments.\n\nThis specific instance of judgments is worth a separate (empirical) study because of its conceptual value of bridging the social choice and the learning-to-rank communities. That being said, our QRJA model and theoretical results are not confined to races. These contributions are also valuable within the social choice community.\n\nOne direct real-world application is assigning contest ratings to a set of contestants, as illustrated in Section 2 of our paper. Besides that, our work can also be applied to the use cases of prior works on societal tradeoffs \\[1-3\\] like setting numerical tradeoff standards.\n\n**On the third question**\n\n$\\\\ell\\_2$ QRJA is reducible to $\\\\ell\\_2$-regression, which is often referred to as the linear least-square regression problem. In our experiments, we use the Python package `scipy.sparse.linalg.lsqr` to solve it (see Line 120 of the uploaded `code/qrja.py` in supplementary materials). We will clarify this.\n\n**References**\n\n\\[1\\] Conitzer, V.; Brill, M.; and Freeman, R. 2015\\. Crowdsourcing societal tradeoffs. In Proc. of the 14th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS).\n\n\\[2\\] Conitzer, V.; Freeman, R.; Brill, M.; and Li, Y. 2016\\. Rules for choosing societal tradeoffs. In Proc. of the 30th AAAI Conference on Artificial Intelligence (AAAI).\n\n\\[3\\] Zhang, H.; Cheng, Y.; and Conitzer, V. 2019\\. A better algorithm for societal tradeoffs. In Proc. of the 33rd AAAI Conference on Artificial Intelligence (AAAI).\n\n\\[4\\] Chen, L.; Kyng, R.; Liu, Y. P.; Peng, R.; Gutenberg, M. P.; and Sachdeva, S. 2022\\. Maximum flow and minimum-cost flow in almost-linear time. In Proc. of the IEEE 63rd Symposium on Foundations of Computer Science (FOCS).", "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": "306gbUPhBy", "reviewer": "Reviewer_zJAB", "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.", "questions": "Summarizing some of the points above into questions:\n- Can you further clarify the explainability benefits of your approach vs MF, perhaps drawing on the provide \"Examples\" section\n- 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)\n- 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": "The current draft is reasonable in its claims: the theoretical analyses and experiments provided are commensurate to the claimed contributions.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper has a number of strengths. Below, they are briefly listed. I'll also note that while the overall length of the \"Weaknesses\" section in this review is longer than \"Strengths\", overall the potential contribution here is very strong.\n\n- Theoretical analysis of computational complexity for a new problem (variant of previous problem) + experiments to back this up.\n- The paper includes several novel aspects (updating task and framing within an existing literature on social choice, the actual results)\n- Code is shared, documented, and useful in providing additional clarity about experiments.\n- Relatively clear paper overall. The actual presentation of model, code (supplementary materials) + experiments are all extremely clear. The explanation and presentation of Theorems 1 and 2 were reasonably clear (familiar with some of the cited social choice work, but had to refer to the provided previous work to understand the motivation for different loss functions f -- this could be a bit clearer).\n\nIn terms of significance, this work has the potential to be broadly relevant to many areas where social choice theory is relevant (i.e., many domains, as the current draft points out) and also will be of interest to readers who are familiar with this specific literature, the computational complexity results of similar methods, the implementation, etc.", "weaknesses": "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'.\n\nFrom 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.\n\nSection 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\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your recognition and thoughtful comments.\n\nWe are glad that you find our contribution novel and strong, and our presentation extremely clear. We are particularly delighted to see you noted and recognized our documented code for the experiments. Below, we respond to the questions raised in your review.\n\n**On the first question**\n\nQRJA and Matrix Factorization (MF) are both optimization-based methods for contest ranking prediction. QRJA can have explainability benefits over MF because its variables have clear intuitive meanings: they can be interpreted as the strength of each contestant. In contrast, the variables in MF are latent features of contests and contestants, which can be harder to interpret. We will expand the discussion of this in our paper.\n\n**On the second question**\n\nThe general formulation of QRJA is motivated by the common need of aggregating quantitative relative “judgments”. These judgments are often subjective opinions from human judges, e.g.,“using 1 unit of gasoline is as bad as creating 3 units of landfill trash”. Our modeling and theoretical study of QRJA is motivated by the need of aggregating such judgments.\n\nMoreover, we observe that these relative “judgments” can also be produced by an objective process, like a contest, rather than human judges. This gives us the opportunity to explore the interplay between social choice theory and the learning-to-rank community. Therefore, we apply the QRJA rules to the problem of contest ranking prediction for further study.\n\nWe will reorganize the introduction to provide additional clarity about the motivation.\n\n**On the third question**\n\nThank you for the constructive comments.", "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": "grqDEbGpdk", "reviewer": "Reviewer_Z9Qp", "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.\n\n==============================\n\nThis 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.\n\nThe 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.", "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": "The authors have done a good job of filling out the checklist and have addressed the limitations of the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Novelty\n\nThe paper appears to extend an existing framework. The results expressed in the paper and the evaluation of their framework are novel while the methodology used is standard.\n\n\nQuality\n\nThe paper presents several theoretical results which appear quite plausible. I am not well equipped to thoroughly check the proof of Theorem 1 but it appears to me to be quite reasonable.\n\nThe experimental results compare the developed framework across multiple datasets with several other methodologies that can be used to solve the same problem. Some of the other methodologies are more well-suited to the task than others but overall this comparison is substantial and provides a useful overview of the performance of l_p QRJA.\n\n\nClarity\n\nThe paper is well written in general. The introduction and motivating examples provide excellent intuition as to the problem domain. The framework and theory are fairly clearly described; I do feel as though the significance of the results could be highlighted more strongly but overall the paper is quite understandable.\n\n\nSignificance\n\nThe main result of the paper is theory showing the complexity of their l_p QRJA framework under varying conditions, backed by simulations verifying the performance of the framework. The paper is a meaningful improvement to existing work which appears roughly as impactful as most papers in top-tier conferences. There is certainly room for future work to develop based on this or for this work to be adapted into an algorithm for deployed use.", "weaknesses": "See previously written and lightly edited section above.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your recognition and thoughtful comments.\n\nWe are grateful that you updated your review reflecting the changes in our paper. Compared with the AAAI 2024 version, we significantly improved our work. Notably, we strengthened our theoretical results \\- our algorithm was improved from polynomial time to almost linear time. In addition, we reorganized the paper structure, re-ran some experiments, and addressed other reviewer comments.\n\n**On your question**\n\nWe have re-run the experiments. This is because one of the AAAI 2024 reviewers suggested that we should “consider the average of the square of the error of the predictions”, i.e., an $\\\\ell\\_2$ version of the quantitative loss we used. Therefore, in the subsequent revision of our work, we re-ran the experiments to incorporate this metric. See Appendix C.1 for the details.", "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:
We thank all reviewers for taking the time to read our paper and provide thoughtful comments.

We are delighted to learn that the reviewers find our topic “interesting and important” (Fgap), and the “combination of social choice and ranking prediction” “neat” (iMha). In addition, we are glad that reviewers judged our theoretical results to be “sound and non-trivial” (Fgap), our empirical evaluation “substantial” (Z9Qp), and our potential contribution “very strong” (zJAB).

Below we provide detailed responses to each reviewer’s questions.

Meta-review: 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).
Decision: Accept (poster)