RUMs from Head-to-Head Contests

Matteo Almanza, Flavio Chierichetti, Ravi Kumar, Alessandro Panconesi, Andrew TomkinsICML 2022 · OpenReview

Introduction

In discrete choice theory, Random Utility Models (RUMs) are the gold standard for modeling how people choose between items. The underlying premise is intuitive: every item possesses a "utility" or inherent value, but that value is subject to random noise at the moment of decision. A user simply chooses the item that presents the highest realized utility.

While RUMs are theoretically powerful and effectively capture "rational" human behavior, they are notoriously difficult to deploy in machine learning contexts. Optimization typically involves non-concave likelihoods, leading to local optima and severe stability issues. Consequently, most existing approaches either restrict the model (e.g., by assuming independent noise) or pivot to incomparable models like the "Blade-Chest" model.

This paper tackles the challenge of finding the best-fitting RUM specifically for head-to-head contests (pairwise choices). These contests are represented by a tournament matrix where each entry denotes the probability of one item defeating another. To solve this, the authors introduce the first polynomial-time algorithm (RIPPLE) and a highly practical heuristic (RUMRUNNER) for learning general RUMs from pairwise competition data.

Methodology: Distributions Over Permutations

The authors approach the problem by treating a RUM as a distribution over permutations. For $n$ items, there are $n!$ possible rankings. A RUM assigns a probability to each ranking, and the probability of item $j$ beating item $i$ is the sum of the probabilities of all rankings where $j$ is ranked higher than $i$.

To navigate this massive space, the paper introduces three core contributions:

  1. RIPPLE (Randomized Interior Point Permutation LEarner): This theoretical breakthrough formulates the problem as a massive Linear Program (LP) with an exponential number of variables (one for each permutation). The authors solve the dual of this LP using the Ellipsoid method. The critical innovation is demonstrating that the required separation oracle can be approximated by solving an instance of the Minimum Feedback Arc Set (FAS) problem.
  2. RUMRUNNER: Because the Ellipsoid method is computationally heavy in practice, the authors developed RUMRUNNER. This heuristic uses a separating-hyperplane approach, iteratively adding permutations to the model's support to minimize error efficiently.
  3. Succinct Representation: The authors prove that any RUM can be approximated to within an error $\epsilon$ using only $O(\epsilon^{-2})$ permutations. This guarantees that a complex distribution over $n!$ rankings can be compressed into a small, manageable set of weighted permutations.

Datasets and Empirical Performance

The authors evaluated their algorithms on several real-world datasets to test their expressivity and accuracy:

  • Election Datasets (A5, A9, A17, A48, A81): Ballots from various elections transformed into pairwise matches.
  • Super Street Fighter IV (SF): Matchup data between characters in the popular fighting game.
  • Jester: A dataset of joke ratings, converted into pairwise preferences.
Dataset statistics and error metrics

As shown in the table above, RUMs are incredibly flexible. The experiments demonstrated that they could perfectly encode the election datasets (achieving exactly zero average error) and achieve near-perfect fits on the others. For instance, on the SF dataset, the maximum average error was negligible ($\approx 0.001$).

Key Insights and Results

Beyond raw performance, the paper highlights several important theoretical and practical insights:

  • The FAS Connection: Linking RUM optimization to the Feedback Arc Set problem creates a clever bridge between choice theory and combinatorial optimization. It allows researchers to use established approximation algorithms for FAS to navigate the otherwise intractable exponential space of permutations.
  • Interpretability: Unlike "black-box" neural models, a learned RUM is simply a weighted set of rankings. Practitioners can inspect the top-weighted permutations to understand the primary "types" of user preferences within a population.
  • Average vs. Uniform Error: A major theoretical finding is that while minimizing average error across all pairs is solvable in polynomial time, minimizing the maximum (uniform) error for any single pair is NP-hard to even approximate.
Average error convergence across datasets

The convergence plots illustrate the efficiency of the proposed methods. RUMRUNNER proved to be a stable, hyperparameter-free alternative to gradient descent-based methods, which frequently get stuck in local optima. In cross-validation tasks, it performed comparably to state-of-the-art models like Blade-Chest (BC) and Majority Vote (MV), while offering superior interpretability and the inherent ability to predict outcomes for slates larger than size two.

Limitations and Future Work

The primary limitation of this work is its focus on pairwise choices. While RUMs naturally generalize to larger "slates" (e.g., choosing 1 out of 5 items), the specific learning algorithms presented here are tuned for head-to-head data.

The authors suggest two main avenues for future research:

  1. Extending these efficient learning methods to handle winning probabilities in slates of size three or larger.
  2. Investigating the complexity of finding the smallest possible set of permutations (support size $k$) that exactly represents a given tournament matrix.

Summary updated

BibTeX
@inproceedings{almanza2022rums,
  author = {Matteo Almanza and Flavio Chierichetti and Ravi Kumar and Alessandro Panconesi and Andrew Tomkins},
  title = {{RUMs from Head-to-Head Contests}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=AawwTSeIN4D},
}
Figure