  We study the problem of actively learning a non-parametric choice model based
on consumers' decisions. We present a negative result showing that such choice
models may not be identifiable. To overcome the identifiability problem, we
introduce a directed acyclic graph (DAG) representation of the choice model.
This representation provably encodes all the information about the choice model
which can be inferred from the available data, in the sense that it permits
computing all choice probabilities.
  We establish that given exact choice probabilities for a collection of item
sets, one can reconstruct the DAG. However, attempting to extend this
methodology to estimate the DAG from noisy choice frequency data obtained
during an active learning process leads to inaccuracies. To address this
challenge, we present an inclusion-exclusion approach that effectively manages
error propagation across DAG levels, leading to a more accurate estimate of the
DAG. Utilizing this technique, our algorithm estimates the DAG representation
of an underlying non-parametric choice model. The algorithm operates
efficiently (in polynomial time) when the set of frequent rankings is drawn
uniformly at random. It learns the distribution over the most popular items
among frequent preference types by actively and repeatedly offering assortments
of items and observing the chosen item. We demonstrate that our algorithm more
effectively recovers a set of frequent preferences on both synthetic and
publicly available datasets on consumers' preferences, compared to
corresponding non-active learning estimation algorithms. These findings
underscore the value of our algorithm and the broader applicability of
active-learning approaches in modeling consumer behavior.
