Adjacencies on random ordering polytopes and flow polytopes
From MaRDI portal
Publication:6134082
DOI10.1016/J.JMP.2023.102768zbMATH Open1520.91110arXiv2207.06925OpenAlexW4362454806MaRDI QIDQ6134082FDOQ6134082
Publication date: 25 July 2023
Published in: Journal of Mathematical Psychology (Search for Journal in Brave)
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).
Full work available at URL: https://arxiv.org/abs/2207.06925
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
- Title not available (Why is that?)
- A course in combinatorics.
- The stochastic choice problem: A game-theoretic approach
- A representation theorem for finite random scale systems
- A short proof of a theorem of Falmagne.
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Semiorders and a Theory of Utility Discrimination
- Title not available (Why is that?)
- Falmagne and the Rationalizability of Stochastic Choices in Terms of Random Orderings
- Title not available (Why is that?)
- Combinatorial optimization. Theory and algorithms.
- Hamiltonicity and combinatorial polyhedra
- Binary choice probabilities and rankings
- Adjacency on combinatorial polyhedra
- Intransitive indifference with unequal indifference intervals
- Maximum-Minimum Sätze über Graphen
- The linear ordering problem. Exact and heuristic methods in combinatorial optimization.
- Induced binary probabilities and the linear ordering polytope: A status report
- Facets of the \((s,t)-p\)-path polytope
- Title not available (Why is that?)
- Bayesian inference and model comparison for random choice structures
- Analysis of multinomial models under inequality constraints: applications to measurement theory
- Weak order polytopes.
- An updated survey on the linear ordering problem for weighted or unweighted tournaments
- Independent random utility representations
- Regular choice systems: a general technique to represent them by random variables
- New Handbook of Mathematical Psychology
- Identification in the random utility model
- Extended formulations for order polytopes through network flows
- The diameters of network-flow polytopes satisfy the Hirsch conjecture
- A general concept of majority rule
Cited In (1)
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)
