Timezone: »

 
Poster
RUMs from Head-to-Head Contests
Matteo Almanza · Flavio Chierichetti · Ravi Kumar · Alessandro Panconesi · Andrew Tomkins

Thu Jul 21 03:00 PM -- 05:00 PM (PDT) @ Hall E #700
in Poster Session 3 »
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.
Keywords: OPT: Discrete and Combinatorial Optimization · OPT: Sampling and Optimization · T: Learning Theory

Author Information

Matteo Almanza (Sapienza University)
Flavio Chierichetti (Sapienza University)
Ravi Kumar (Google)
Alessandro Panconesi (Sapienza, University of Rome)
Andrew Tomkins (Google)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors