Reviews: Pairwise Choice Markov Chains

This paper considers the problem of developing flexible choice models that are not constrained to satisfy traditional, restrictive choice axioms (such as Luce's axiom of independence of irrelevant attributes, IIA), but that can be tractably inferred from data. A (discrete) choice model over n items specifies probabilities of the form p(i,S) Prob( i chosen from S) for each subset of items S \subseteq [n] and each item i \in S. One of the most widely used models of discrete choice is the multinomial logit (MNL) choice model, which can be inferred efficiently from data but which is constrained to satisfy IIA and other restrictive assumptions. The paper proposes a new Markov chain based model of discrete choice that is parametrized by a (n x n) pairwise selection probability matrix. The model avoids several of the earlier restrictive assumptions, but is shown to satisfy an interesting property termed contractibility, which in turn also implies a reasonable property of uniform expansion. Parameter estimation in the model is done by maximum likelihood (the log-likelihood function is non-concave in general, but the experiments suggest that good parameters are learned).