Adjacencies on random ordering polytopes and flow polytopes
From MaRDI portal
Publication:6134082
Abstract: The Multiple Choice Polytope (MCP) is the prediction range of a random utility model due to Block and Marschak (1960). Fishburn (1998) offers a nice survey of the findings on random utility models at the time. A complete characterization of the MCP is a remarkable achievement of Falmagne (1978). Apart for a recognition of the facets by Suck (2002), the geometric structure of the MCP was apparently not much investigated. Recently, Chang, Narita and Saito (2022) refer to the adjacency of vertices while Turansick (2022) uses a condition which we show to be equivalent to the non-adjacency of two vertices. We characterize the adjacency of vertices and the adjacency of facets. To derive a more enlightening proof of Falmagne Theorem and of Suck result, Fiorini (2004) assimilates the MCP with the flow polytope of some acyclic network. Our results on adjacencies also hold for the flow polytope of any acyclic network. In particular, they 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 other models, see for instance Fishburn and Falmagne, 1989, and Marley and Regenwetter, 2017).
Recommendations
- Extended formulations for order polytopes through network flows
- Random utility representation of binary choice probabilities: Critical graphs yielding critical necessary conditions
- Combinatoric and geometric aspects of some probabilistic choice models -- a review
- Primary facets of order polytopes
- Adjacency of vertices of the complete pre-order polytope
Cites work
- scientific article; zbMATH DE number 3156726 (Why is no real title available?)
- scientific article; zbMATH DE number 3174052 (Why is no real title available?)
- scientific article; zbMATH DE number 4162686 (Why is no real title available?)
- scientific article; zbMATH DE number 1498519 (Why is no real title available?)
- A course in combinatorics.
- A general concept of majority rule
- A representation theorem for finite random scale systems
- A short proof of a theorem of Falmagne.
- Adjacency on combinatorial polyhedra
- An updated survey on the linear ordering problem for weighted or unweighted tournaments
- Analysis of multinomial models under inequality constraints: applications to measurement theory
- Bayesian inference and model comparison for random choice structures
- Binary choice probabilities and rankings
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Combinatorial optimization. Theory and algorithms.
- Extended formulations for order polytopes through network flows
- Facets of the \((s,t)-p\)-path polytope
- Falmagne and the Rationalizability of Stochastic Choices in Terms of Random Orderings
- Hamiltonicity and combinatorial polyhedra
- Identification in the random utility model
- Independent random utility representations
- Induced binary probabilities and the linear ordering polytope: A status report
- Intransitive indifference with unequal indifference intervals
- Maximum-Minimum Sätze über Graphen
- New handbook of mathematical psychology. Volume 2. Modeling and measurement
- Regular choice systems: a general technique to represent them by random variables
- Semiorders and a Theory of Utility Discrimination
- The diameters of network-flow polytopes satisfy the Hirsch conjecture
- The linear ordering problem. Exact and heuristic methods in combinatorial optimization.
- The stochastic choice problem: A game-theoretic approach
- Weak order polytopes.
Cited in
(2)
This page was built for publication: Adjacencies on random ordering polytopes and flow polytopes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6134082)
