Computing Choice: Learning Distributions over Permutations
Devavrat Shah · Cambridge University Press eBooks · 2021
We discuss the question of learning distributions over permutations of a given set of choices, options or items based on partial observations. This is central to capturing the so-called “choice’’ in a variety of contexts. The question of learning distributions over permutations arises beyond capturing “choice’’ too, e.g., tracking a collection of objects using noisy cameras, or aggregating ranking of web-pages using outcomes of multiple search engines. Here we focus on learning distributions over permutations from marginal distributions of two types: first-order marginals and pair-wise comparisons. We emphasize the ability to identify the entire distribution over permutations as well as the “best ranking’’.