Primary facets of order polytopes
From MaRDI portal
Publication:730181
DOI10.1016/J.JMP.2016.07.004zbMATH Open1396.91110arXiv1511.00314OpenAlexW2962871821MaRDI QIDQ730181FDOQ730181
Authors: Jean-Paul Doignon, Selim Rexhep 
Publication date: 23 December 2016
Published in: Journal of Mathematical Psychology (Search for Journal in Brave)
Abstract: Mixture models on order relations play a central role in recent investigations of transitivity in binary choice data. In such a model, the vectors of choice probabilities are the convex combinations of the characteristic vectors of all order relations of a chosen type. The five prominent types of order relations are linear orders, weak orders, semiorders, interval orders and partial orders. For each of them, the problem of finding a complete, workable characterization of the vectors of probabilities is crucial---but it is reputably inaccessible. Under a geometric reformulation, the problem asks for a linear description of a convex polytope whose vertices are known. As for any convex polytope, a shortest linear description comprises one linear inequality per facet. Getting all of the facet-defining inequalities of any of the five order polytopes seems presently out of reach. Here we search for the facet-defining inequalities which we call primary because their coefficients take only the values -1, 0 or 1. We provide a classification of all primary, facet-defining inequalities of three of the five order polytopes. Moreover, we elaborate on the intricacy of the primary facet-defining inequalities of the linear order and the weak order polytopes.
Full work available at URL: https://arxiv.org/abs/1511.00314
Recommendations
Individual preferences (91B08) Partial orders, general (06A06) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)
Cites Work
- Combinatorial optimization and small polytopes
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The linear ordering problem. Exact and heuristic methods in combinatorial optimization.
- On the partial order polytope of a digraph
- Facets of the linear ordering polytope
- Title not available (Why is that?)
- NP-hardness results for the aggregation of linear orders into median orders
- Shelling polyhedral 3-balls and 4-polytopes
- Betweenness, orders and interval graphs
- Weak order polytopes.
- Ternary paired comparisons induced by semi- or interval order preferences
- On the computation of median linear orders, of median complete preorders and of median weak orders
- A combinatorial study of partial order polytopes
- Integer Programming
- Title not available (Why is that?)
- Several unresolved conceptual problems of mathematical psychology
- Random utility representation of binary choice probabilities: A new class of necessary conditions
- The strongest facets of the acyclic subgraph polytope are unknown
- Random utility representation of binary choice probabilities: Critical graphs yielding critical necessary conditions
- There Are Many Models of Transitive Preference: A Tutorial Review and Current Perspective
- Random relations, random utilities, and random functions
- Complexity results for extensions of median orders to different types of remoteness
- How to recycle your facets
- Facets of the weak order polytope derived from the induced partition projection
- Consensus theories. An oriented survey
- The interval order polytope of a digraph
- 0, 1/2‐Cuts and the Linear Ordering Problem: Surfaces That Define Facets
Cited In (11)
- Multinomial models with linear inequality constraints: overview and improvements of computational methods for Bayesian inference
- Extended formulations for order polytopes through network flows
- Levelness of Order Polytopes
- Facets of linear signed order polytopes.
- A lexicographic semiorder polytope and probabilistic representations of choice
- Weak order polytopes.
- A correct response model in knowledge structure theory
- Order-chain polytopes
- Derivations of large classes of facet defining inequalities of the weak order polytope using ranking structures
- Triangulations, order polytopes, and generalized snake posets
- Adjacencies on random ordering polytopes and flow polytopes
Uses Software
This page was built for publication: Primary facets of order polytopes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q730181)
