  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 effects. Motivated by the challenge of predicting complex choices,
we study the query complexity of these functions in a variety of settings. We
consider settings 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 efficiently as a basic maximum or minimum choice function across many query
contexts, suggesting that choice-set effects need not entail any fundamental
algorithmic barriers to inference. We also introduce a class of choice
functions we call distance-comparison-based functions, and briefly discuss the
analysis of such functions. The framework we outline provides intriguing
connections between human choice behavior and a range of questions in the
theory of sorting.
