RUMs from Head-to-Head Contests

Matteo Almanza · Flavio Chierichetti · Ravi Kumar · Alessandro Panconesi · Andrew Tomkins

Hall E #700

Keywords: [ OPT: Sampling and Optimization ] [ T: Learning Theory ] [ OPT: Discrete and Combinatorial Optimization ]

[ Abstract ]
[ Poster [ Paper PDF
Thu 21 Jul 3 p.m. PDT — 5 p.m. PDT
Spotlight presentation: Optimization/Reinforcement Learning
Thu 21 Jul 7:30 a.m. PDT — 9 a.m. PDT

Abstract: Random utility models (RUMs) encode the likelihood that a particular item will be selected from a slate of competing items. RUMs are well-studied objects in both discrete choice theory and, more recently, in the machine learning community, as they encode a fairly broad notion of rational user behavior. In this paper, we focus on slates of size two representing head-to-head contests. Given a tournament matrix $M$ such that $M_{i,j}$ is the probability that item $j$ will be selected from $\{i, j\}$, we consider the problem of finding the RUM that most closely reproduces $M$. For this problem we obtain a polynomial-time algorithm returning a RUM that approximately minimizes the average error over the pairs.Our experiments show that RUMs can {\em perfectly} represent many of the tournament matrices that have been considered in the literature; in fact, the maximum average error induced by RUMs on the matrices we considered is negligible ($\approx 0.001$). We also show that RUMs are competitive, on prediction tasks, with previous approaches.

Chat is not available.