TY - JOUR

T1 - Extended formulations for order polytopes through network flows

AU - Davis-Stober, Clintin P.

AU - Doignon, Jean Paul

AU - Fiorini, Samuel

AU - Glineur, François

AU - Regenwetter, Michel

N1 - Publisher Copyright:
© 2018 Elsevier Inc.

PY - 2018/12

Y1 - 2018/12

N2 - 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.

AB - 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.

KW - Distribution free random utility

KW - Extended formulations

KW - Network flows

KW - Order polytopes

KW - Probabilistic choice

UR - http://www.scopus.com/inward/record.url?scp=85053810620&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85053810620&partnerID=8YFLogxK

U2 - 10.1016/j.jmp.2018.08.003

DO - 10.1016/j.jmp.2018.08.003

M3 - Article

C2 - 30906069

AN - SCOPUS:85053810620

SN - 0022-2496

VL - 87

SP - 1

EP - 10

JO - Journal of Mathematical Psychology

JF - Journal of Mathematical Psychology

ER -