Paper Info
Title
Discrete Choice, Permutations, and Reconstruction.
Abstract
In this paper we study the well-known family of Random Utility Models, developed over 50 years ago to codify rational user behavior in choosing one item from a finite set of options. In this setting each user draws i.i.d. from some distribution a utility function mapping each item in the universe to a real-valued utility. The user is then offered a subset of the items, and selects the one of maximum utility. A Max-Dist oracle for this choice model takes any subset of items and returns the probability (over the distribution of utility functions) that each will be selected. A discrete choice algorithm, given access to a Max-Dist oracle, must return a function that approximates the oracle. We show three primary results. First, we show that any algorithm exactly reproducing the oracle must make exponentially many queries. Second, we show an equivalent representation of the distribution over utility functions, based on permutations, and show that if this distribution has support size k, then it is possible to approximate the oracle using O(nk) queries. Finally, we consider settings in which the subset of items is always small. We give an algorithm that makes less than n(1−ε/2)K queries, each to sets of size at most (1−ε/2)K, in order to approximate the Max-Dist oracle on every set of size |T| ≤ K with statistical error at most ε. In contrast, we show that any algorithm that queries for subsets of size [Equation] must make maximal statistical error on some large sets.
Year
DOI
Venue
2018
10.5555/3174304.3175308
SODA '18: Symposium on Discrete Algorithms New Orleans Louisiana January, 2018
Field
DocType
ISBN
Discrete mathematics,Generating function,Combinatorics,Finite set,Computer science,Permutation,Oracle,Discrete choice,Function mapping,Exponential growth
Conference
978-1-61197-503-1
Citations 
PageRank 
References 
0
0.34
4
Authors
3
Name
Order
Citations
PageRank
Flavio Chierichetti162639.42
Ravi Kumar2139321642.48
Andrew Tomkins393881401.23