A broad range of on-line behaviors are mediated by interfaces in which people make choices among sets of options. A rich and growing line of work in the behavioral sciences indicate that human choices follow not only from the utility of alternatives, but also from the choice set in which alternatives are presented. In this work we study comparison-based choice functions, a simple but surprisingly rich class of functions capable of exhibiting so-called choice-set e ects. Motivated by the challenge of predicting complex choices, we study the query complexity of these functions in a variety of se ings. We consider se ings that allow for active queries or passive observation of a stream of queries, and give analyses both at the granularity of individuals or populations that might exhibit heterogeneous choice behavior. Our main result is that any comparison-based choice function in one dimension can be inferred as e ciently as a basic maximum or minimum choice function across many query contexts, suggesting that choice-set e ects need not entail any fundamental algorithmic barriers to inference. We also introduce a class of choice functions we call distance-comparisonbased functions, and brie y discuss the analysis of such functions. e framework we outline provides intriguing connections between human choice behavior and a range of questions in the theory of sorting. Additional Key Words and Phrases: Choice-set e ects, sorting with noisy comparisons, sorting in one round. Modern information systems across a broad range of domains wrestle with increasingly expansive and heterogeneous corpora of data describing human decisions -from online marketplaces such as Amazon and AirBnB recording diverse purchasing behavior to search engines and recommendation systems that process continuous clickstreams, where clicks re ect choices. Many of the decisions made in these on-line environments have a consistent structure: users are presented with a set of options -a list of recommended books, search results, ight options, or users to follow -and they select one or more items from the set. e ubiquity of this framework has led to an active line of research on the problem of learning ranking functions [1] . ere are many formulations in the literature, but the essential core is to assume that a user has a ranking over alternatives that is hidden from us, and by observing their choices we would like to infer this ranking. is question can be asked at the level of individuals or at the level of populations containing heterogeneous but related rankings. Choice-set e ects. A central assumption in the work on rankings is that individuals start from an underlying total order on the possible alternatives. Roughly speaking, consider an inventory Z = {z 1 , z 2 , . . . , z n } of possible choices, globally ordered so that a particular user prefers z i to z j for i < j. When the user is presented with a set of choices S ⊆ Z , they select the item in S that is ranked rst according to this global order. ere are many variations on this basic pa ern -there may be noise in the selection, or options may be unobserved -but the total ordering is a crucial part of the structure. A long line of work in behavioral science [9, 15, 22, 25, 28] , however, indicates that people's empirical choices tend to deviate in signi cant ways from this picture. A person's choice will in fact typically depend not just on the total ordering on the full set of alternatives Z , which is o en enormous and implicit, but also on the choice set S they are shown as part of the speci c decision at hand. Notable examples of such choice-set e ects include the compromise e ect, similarity aversion, and the decoy e ect (also known as asymmetric dominance), and have been observed in diverse contexts both o ine and online; recent work in machine learning has highlighted the prevalence of choice-set e ects [4, 19, 23, 33] and non-transitive comparisons [7, 8] , particularly in online search, online ads, and online games. A canonical example of a choice-set e ect is the so-called compromise e ect [24]: faced with the choice between a mediocre option for $10, a good option for $15, and an excellent option for $20, people will tend to choose the good option for $15; but faced instead with a choice between the same good option for $15, the excellent option for $20, and an outstanding option for $25, people will be more likely to choose the excellent option for $20. In other words, there is a tendency to favor the option that compromises between the two extremes in the set that is presented. More generally, suppose that a set of products exhibit a trade-o between two factors -for example, price vs. quality, power vs. reliability, or aesthetics vs. fuel e ciency. ere is a naturally de ned one-dimensional set of products that are on the Pareto frontier: they are the options for which no other product is more desirable in both factors. Consider four products A, B, C, and D that are arranged in this order along the one-dimensional frontier (A is the least powerful but most reliable, and D as the most powerful but least reliable). In a wide variety of se ings, B will be empirically chosen more o en when it is presented as one of the three choices S = {A, B, C} than when it is one of the three choices S = {B, C, D} -in other words, when it is the compromise option rather than an extreme option. By the same reasoning, C will be chosen more o en when it is presented as part of S than as part of S. One can ask whether this is simply a representational issue, but in fact it is much deeper. e point is that in any model based on a total ordering on the alternatives Z , a user would prefer either B or C, and this would hold in any choice set S that contains both of them. But B and C are options in both the sets S = {A, B, C} and S = {B, C, D}, and the aggregate distribution of choices in favor of B versus C changes across these two sets. is suggests that the relative ordering of B and C in fact is not well-de ned in isolation, but must be evaluated in the context of the choice set (S or S ). It ma ers what else is on o er. Comparison-based choice functions. In this paper, we consider a set of basic algorithmic questions that arise when we seek to infer models of user choice in the presence of comparisonbased choice-set e ects. We focus on a basic formulation in which these e ects arise, and show how our framework makes it possible to derive asymptotic bounds on query complexity and sample complexity in performing these types of inference. We set up the problem as follows. (1) Embedding of alternatives. e full collection of alternatives is a set U = {u 1 , . . . , u n }, and there is an embedding of U into a space of a ributes X via a function h : U → X . For most of our discussion we will take X to be the real line R 1 , so that h(u i ) is a real number; thus most of the time we can think of the embedded points {h(u 1 ), . . . , h(u n )} as representing a one-dimensional trade-o continuum as in the discussion above. We will assume that the embedding h is not known to us. Indeed, while we sometimes might know the crucial one-dimensional a ribute of an item, such
Kleinberg et al. REF consider a general class of comparison-based choice models, and study the complexity of learning their model from samples.
Comparison-based Choices
EC '17
Mathematics Computer Science