In this work we consider the problem of fitting Random Utility Models (RUMs)
to user choices. Given the winner distributions of the subsets of size $k$ of a
universe, we obtain a polynomial-time algorithm that finds the RUM that best
approximates the given distribution on average. Our algorithm is based on a
linear program that we solve using the ellipsoid method. Given that its
corresponding separation oracle problem is NP-hard, we devise an approximate
separation oracle that can be viewed as a generalization of the weighted
feedback arc set problem to hypergraphs. Our theoretical result can also be
made practical: we obtain a heuristic that is effective and scales to
real-world datasets.

本文研究拟合随机效用模型（Random Utility Models，简称 RUMs）到用户选择问题，提出了一个基于线性规划和椭球法的多项式时间算法，并得出可行的近似分离规则解决方案，可以被视为超图的加权反馈弧集问题的一般化。

从 K-Slates 分布逼近 RUM

Approximating a RUM from Distributions on k-Slates

In this paper we study noisy sorting without re-sampling. In this problem
there is an unknown order $a_{\pi(1)} < ... < a_{\pi(n)}$ where $\pi$ is a
permutation on $n$ elements. The input is the status of $n \choose 2$ queries
of the form $q(a_i,x_j)$, where $q(a_i,a_j) = +$ with probability at least
$1/2+\ga$ if $\pi(i) > \pi(j)$ for all pairs $i \neq j$, where $\ga > 0$ is a
constant and $q(a_i,a_j) = -q(a_j,a_i)$ for all $i$ and $j$. It is assumed that
the errors are independent. Given the status of the queries the goal is to find
the maximum likelihood order. In other words, the goal is find a permutation
$\sigma$ that minimizes the number of pairs $\sigma(i) > \sigma(j)$ where
$q(\sigma(i),\sigma(j)) = -$. The problem so defined is the feedback arc set
problem on distributions of inputs, each of which is a tournament obtained as a
noisy perturbations of a linear order. Note that when $\ga < 1/2$ and $n$ is
large, it is impossible to recover the original order $\pi$.
It is known that the weighted feedback are set problem on tournaments is
NP-hard in general. Here we present an algorithm of running time
$n^{O(\gamma^{-4})}$ and sampling complexity $O_{\gamma}(n \log n)$ that with
high probability solves the noisy sorting without re-sampling problem. We also
show that if $a_{\sigma(1)},a_{\sigma(2)},...,a_{\sigma(n)}$ is an optimal
solution of the problem then it is ``close'' to the original order. More
formally, with high probability it holds that $\sum_i |\sigma(i) - \pi(i)| =
\Theta(n)$ and $\max_i |\sigma(i) - \pi(i)| = \Theta(\log n)$.
Our results are of interest in applications to ranking, such as ranking in
sports, or ranking of search items based on comparisons by experts.

研究了反馈弧集问题的算法，使用 n 个元素上的顺序形成的锦标赛作为输入，并考虑到噪声干扰，以最大似然的方式找到排名。