Extended formulations for order polytopes through network flows

Clintin P. Davis-Stober, Jean Paul Doignon, Samuel Fiorini, François Glineur, Michel Regenwetter

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)1-10
Number of pages10
JournalJournal of Mathematical Psychology
StatePublished - Dec 2018


  • Distribution free random utility
  • Extended formulations
  • Network flows
  • Order polytopes
  • Probabilistic choice

ASJC Scopus subject areas

  • General Psychology
  • Applied Mathematics


Dive into the research topics of 'Extended formulations for order polytopes through network flows'. Together they form a unique fingerprint.

Cite this