Pairwise Choice Markov Chains
As datasets capturing human choices grow in richness and scale-particularly in online domains-there is an increasing need for choice models that escape traditional choice-theoretic axioms such as regularity, stochastic transitivity, and Luce's choice axiom. In this work we introduce the Pairwise Choice Markov Chain (PCMC) model of discrete choice, an inferentially tractable model that does not assume any of the above axioms while still satisfying the foundational axiom of uniform expansion, a considerably weaker assumption than Luce's choice axiom. We show that the PCMC model significantly outperforms both the Multinomial Logit (MNL) model and a mixed MNL (MMNL) model in prediction tasks on both synthetic and empirical datasets known to exhibit violations of Luce's axiom. Our analysis also synthesizes several recent observations connecting the Multinomial Logit model and Markov chains; the PCMC model retains the Multinomial Logit model as a special case.
stochastic transitivity does not imply the choice axiom; Thurstone's model exhibits strict stochastic transitivity.
Many choice theorists and empiricists, including Luce, have noted that the choice axiom and stochastic transitivity are strong assumptions that do not hold for empirical choice data [9,12,13,26,28]. A range of discrete choice models striving to escape the confines of the choice axiom have emerged over the years. The most popular of these models have been Elimination by Aspects [29], mixed MNL (MMNL) [6], and nested MNL [22]. Inference is practically difficult for all three of these models [15,23]. Additionally, Elimination by Aspects and the MMNL model also both exhibit the rigid property of regularity, defined below.
A broad, important class of models in the study of discrete choice is the class of random utility models (RUMs) [4,20]. A RUM affiliates with each i ∈ U a random variable X i and defines for each subset S ⊆ U the probability Pr(i chosen from S) = Pr(X i ≥ X j , ∀j ∈ S). An independent RUM has independent X i . RUMs assume neither choice axiom nor stochastic transitivity. Thurstone's Case V model and the BTL model are both independent RUMs; the Elimination by Aspects and MMNL models are both RUMs. A major result by McFadden and Train establishes that for any RUM there exists a MMNL model that can approximate the choice probabilities of that RUM to within an arbitrary error [23], a strong result about the generality of MMNL models. The nested MNL model, meanwhile, is not a RUM.
Although RUMs need not exhibit stochastic transitivity, they still exhibit the weaker property of regularity: for any choice sets A, B where A ⊆ B, p xA ≥ p xB . Regularity may at first seem intuitively pleasing, but it prevents models from expressing framing effects [12] and other empirical observations from modern behavior economics [28]. This rigidity motivates us to contribute a new model of discrete choice that escapes historically common assumptions while still furnishing enough structure to be inferentially tractable.
The present work. In this work we introduce a conceptually simple and inferentially tractable model of discrete choice that we call the PCMC model. The parameters of the PCMC model are the off-diagonal entries of a rate matrix Q indexed by U . The PCMC model affiliates each subset S of the alternatives with a continuous time Markov chain (CTMC) on S with transition rate matrix Q S , whose off-diagonal entries are entries of Q indexed by pairs of items in S. The model defines p iS , the selection probability of alternative i ∈ S, as the probability mass of alternative i ∈ S of the stationary distribution of the CTMC on S.
The transition rates of these CTMCs can be interpreted as measures of preferences between pairs of alternatives. Special cases of the model use pairwise choice probabilities as transition rates, and as a result the PCMC model extends arbitrary models of pairwise choice to models of setwise choice. Indeed, we show that when the matrix Q is parameterized with the pairwise selection probabilities of a BTL pairwise choice model, the PCMC model reduces to an MNL model. Recent parameterizations of non-transitive pairwise probabilities such as the Blade-Chest model [8] can be usefully employed to reduce the number of free parameters of the PCMC model. Our PCMC model can be thought of as building upon the observation underlying the recently introduced Iterative Luce Spectral Ranking (I-LSR) procedure for efficiently finding the maximum likelihood estimate for parameters of MNL models [21]. The analysis of I-LSR is precisely analyzing a PCMC model in the special case where the matrix Q has been parameterized by BTL. In that case the stationary distribution of the chain is found to satisfy the stationary conditions of the MNL likelihood function, establishing a strong connection between MNL models and Markov chains. The PCMC model generalizes that connection.
Other recent connections between the MNL model and Markov chains include the work on RankCentrality [24], which employs a discrete time Markov chain for inference in the place of I-LSR's continuous time chain, in the special case where all data are pairwise comparisons.
Separate recent work has contributed a different discrete time Markov chain model of "choice substitution" capable of approximating any RUM [3], a related problem but one with a strong focus on ordered preferences. Lastly, recent work by Kumar et al. explores conditions under which a probability distribution over discrete items can be expressed as the stationary distribution of a discrete time Markov chain with "score" functions similar to the "quality" parameters in an MNL model [17].
The PCMC model is not a RUM, and in general does not exhibit stochastic transitivity, regularity, or the choice axiom. We find that the PCMC model does, however, obey the lesser known but fundamental axiom of uniform expansion, a weakened version of Luce's choice axiom proposed by Yellott that implies the choice axiom for independent RUMs [30]. In this work we define a convenient structural property termed contractibility, for which uniform expansion is a special case, and we show that the PCMC model exhibits contractibility. Of the models mentioned above, only Elimination by Aspects exhibits uniform expansion without being an independent RUM. Elimination by Aspects obeys regularity, which the PCMC model does not; as such, the PCMC model is uniquely positioned in the literature of axiomatic discrete choice, minimally satisfying uniform expansion without the other aforementioned axioms.
After presenting the model and its properties, we investigate choice predictions from our model on two empirical choice datasets as well as diverse synthetic datasets. The empirical choice datasets concern transportation choices made on commuting and shopping trips in San Francisco. Inference on synthetic data shows that PCMC is competitive with MNL when Luce's choice axiom holds, while PCMC outperforms MNL when the axiom does not hold. More significantly, for both of the empirical datasets we find that a learned PCMC model predicts empirical choices significantly better than a learned MNL model. A Pairwise Choice Markov Chain (PCMC) model defines the selection probability p iS , the probability of choosing i from S ⊆ U , as the probability mass on alternative i ∈ S of the stationary distribution of a continuous time Markov chain (CTMC) on the set of alternatives S. The model's parameters are the off-diagonal entries q ij of rate matrix Q indexed by pairs of elements in U . See Figure 1 for a diagram. We impose the constraint q ij + q ji ≥ 1 for all pairs (i, j), which ensures irreducibility of the chain for all S.
Given a query set S ⊆ U , we construct Q S by restricting the rows and columns of Q to elements in S and setting q ii = − j∈S\i q ij for each i ∈ S. Let π S = {π S (i)} i∈S be the stationary distribution of the corresponding CTMC on S, and let π S (A) = x∈A π S (x). We define the choice probability p iS := π S (i), and now show that the PCMC model is well defined. Proposition 1. The choice probabilities p iS are well defined for all i ∈ S, all S ⊆ U of a finite U .
Proof. We need only to show that there is a single closed communicating class. Because S is finite, there must be at least one closed communicating class. Suppose the chain had more than one closed communicating class and that i ∈ S and j ∈ S were in different closed communicating classes. But q ij +q ji ≥ 1, so at least one of q ij and q ji is strictly positive and the chain can switch communicating classes through the transition with strictly positive rate, a contradiction. While the support of π S is the single closed communicating class, S may have transient states corresponding to alternatives with selection probability 0. Note that irreducibility argument needs only that q ij + q ji be positive, not necessarily at least 1 as imposed in the model definition. One could simply constrain q ij + q ji ≥ for some positive . However, multiplying all entriesof Q by some c > 0 does not affect the stationary distribution of the corresponding CTMC, so multiplication by 1/ gives a Q with the same selection probabilities.
In the subsections that follow, we develop key properties of the model. We begin by showing how assigning Q according a Bradley-Terry-Luce (BTL) pairwise model results in the PCMC model being equivalent to BTL's canonical extension, the Multinomial Logit (MNL) set-wise model. We then construct a Q for which the PCMC model is neither regular nor a RUM.
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). Previous models that avoid the above restrictive assumptions either do not satisfy even the uniform expansion property or are computationally difficult to learn, and so the proposed model offers unique properties in comparison to previous models. The proposed model also generalizes a recent Markov chain based formulation of the MNL model, which is subsumed as a special case.  The proposed model is applied to two real data sets on transportation choices in the Bay Area, and in both cases, shows better predictive ability than the classical MNL model.  
This is a strong paper, and additionally, is beautifully written and presented. It is one of the rare papers where I have very few comments or suggestions to make (just one question below). Truly beautiful work, and a pleasure to read!  Ques: What is the running time of the proposed parameter estimation algorithm on the two data sets, and how does this compare with the running time for learning the MNL model? It would be nice to give details on this in the author rebuttal if possible, and to include them in the final version if accepted. In future work or a longer version, it would also be nice to include such comparisons with other models such as nested MNL etc.  ---- After author response -----  I have read the author response and it addresses my question.