  Mathematical psychology has a long tradition of modeling probabilistic choice
via distribution-free random utility models and associated random preference
models. For such models, the predicted choice probabilities often form a
bounded and convex polyhedral set, or polytope. Polyhedral combinatorics have
thus played a key role in studying the mathematical structure of these models.
However, standard methods for characterizing the polytopes of such models are
subject to a combinatorial explosion in complexity as the number of choice
alternatives increases. Specifically, this is the case for random preference
models based on linear, weak, semi- and interval orders. For these, a complete,
linear description of the polytope is currently known only for, at most, 5--8
choice alternatives. We leverage the method of extended formulations to break
through those boundaries. For each of the four types of preferences, we build
an appropriate network, and show that the associated network flow polytope
provides an extended formulation of the polytope of the choice model. This
extended formulation has a simple linear description that is more parsimonious
than descriptions obtained by standard methods for large numbers of choice
alternatives. The result is a computationally less demanding way of testing the
probabilistic choice model on data. We sketch how the latter interfaces with
recent developments in contemporary statistics.
