Aggregating Quantitative Relative Judgments: From Social Choice to Ranking Prediction

Thank you for your recognition and thoughtful comments.

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

On your question

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

Thank you for your recognition and thoughtful comments.

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

On the first question

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

On the second question

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

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

We will reorganize the introduction to provide additional clarity about the motivation.

On the third question

Thank you for the constructive comments.

Thank you for your thoughtful comments.

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

On the first question

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

Conceptually, $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".

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

On the second question

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

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

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

On the third question

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

References

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

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

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

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

Thank you for your recognition and thoughtful comments.

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

On the first point in Weaknesses

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

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

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

We will clarify this.

On the second point in Weaknesses

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

On the third point in Weaknesses

QRJA addresses issues in the motivating examples by considering the relative performance of contestants rather than their absolute performance in each contest. More specifically:

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

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

References

$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
the 45th annual ACM Symposium on Theory of Computing (STOC).

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