Extended Formulations for Order Polytopes through Network Flows.

Area of Science:

• Mathematical Psychology
• Computational Social Science
• Operations Research

Background:

• Probabilistic choice modeling relies on random utility and preference models.
• These models predict choice probabilities forming polytopes, studied using polyhedral combinatorics.
• Standard polytope descriptions face combinatorial explosion with increasing alternatives.

Purpose of the Study:

• To develop computationally efficient methods for analyzing random preference models.
• To overcome the limitations of standard polyhedral descriptions for complex choice scenarios.
• To provide a more parsimonious representation for probabilistic choice models.

Main Methods:

• Leveraging extended formulations via network flow polytopes.
• Constructing specific networks for linear, weak, semi-, and interval orders.
• Developing a simple linear description for the extended formulation.

Main Results:

• The network flow polytope serves as an extended formulation for choice model polytopes.
• This extended formulation offers a more parsimonious linear description.
• The new method significantly reduces computational demands for model testing.

Conclusions:

• Extended formulations provide a breakthrough for analyzing complex probabilistic choice models.
• This approach enhances the computational tractability of random preference models.
• The findings facilitate integration with contemporary statistical methods.