Random ordering models and flow polytopes

Random ordering models (Block and Marschak, 1960) explain various data sets from a common assumption: the answers of the subject(s) are guided by a latent probability distribution on the set of all orderings of the alternatives (here, ordering means linear ordering). For instance, there are such models for binary choice, multiple choice and best/worst choice. Characterizing a probabilistic model means describing its set of predictions (see for instance Doignon, Heller and Stefanutti, 2018). In many cases, the predicted points of a random ordering model form a convex polytope. The vertices of the polytope are known (they bijectively correspond to the orderings). The characterization problem is then turned into the search of a description of the polytope by a system of equalities and inequalities. Obtaining an efficient characterization of the binary choice model is deemed infeasible (if P ≠ NP, see Fiorini, 2006; note that the binary choice polytope is known in operations research as the linear ordering polytope). To the contrary, a remarkable achievement of Falmagne (1978) provides an explicit characterization of the multiple choice model. Falmagne generalizes inequalities formulated by Block and Marschak (1960), and he then shows by recurrence on the number of alternatives that the resulting inequalities together with obvious equalities determine the multiple choice polytope (MCP). To derive an enlightening proof of Falmagne's Theorem, Fiorini (2004) assimilates the MCP with the flow polytope of some acyclic network. We further exploit Fiorini technique, and extend its applicability. Apart from a recognition of the facets by Suck (2002), the geometric structure of the MCP was apparently not much investigated. We describe the adjacency of vertices and the adjacency of facets (Doignon and Saito, 2023). Our description of the edges of the MCP helps understand recent findings in economics papers such as Chang, Narita and Saito (2022) and Turansick (2022). As a matter of fact, Doignon and Saito describe the two adjacencies in the more general setting of flow polytopes of acyclic networks (the MCP is just a particular case). So, the results apply not only to the MCP, but also to three polytopes which Davis-Stober, Doignon, Fiorini, Glineur and Regenwetter (2018) introduced as extended formulations of the weak order polytope, interval order polytope and semiorder polytope (the prediction ranges of random models with other types of orderings, see for instance Marley and Regenwetter, 2017): in each of the three cases, they rely on a specific, acyclic network. We also show how Fiorini technique helps in the analysis of further random ordering models, in particular we improve the results of Barberá and Pattanaik (1986) on the multiple choice model with latent weak orders (this is on-going joint work with Kota Saito). However, there is no reason that any random ordering model could be characterized in terms of the flows on an acyclic network. For instance, the best/worst choice model apparently requires other techniques. This is another story, still to be written (for a prologue, see the other presentation by the speaker at this meeting). Symposium DETERMINISTIC AND PROBABILISTIC MODELS OF CHOICE Daniel Cavagnaro Jean-Paul Doignon Marc Jekel Tim Pleskac Mike Regenwetter Reinhard Suck