IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2207.06925.html
   My bibliography  Save this paper

Adjacencies on random ordering polytopes and flow polytopes

Author

Listed:
  • Jean-Paul Doignon
  • Kota Saito

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

Suggested Citation

  • Jean-Paul Doignon & Kota Saito, 2022. "Adjacencies on random ordering polytopes and flow polytopes," Papers 2207.06925, arXiv.org.
    • Handle: RePEc:arx:papers:2207.06925
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2207.06925
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Haoge Chang & Yusuke Narita & Kota Saito, 2022. "Approximating Choice Data by Discrete Choice Models," Papers 2205.01882, arXiv.org, revised Dec 2023.
    2. Regenwetter, Michel & Marley, A. A. J. & Grofman, Bernard, 2002. "A general concept of majority rule," Mathematical Social Sciences, Elsevier, vol. 43(3), pages 405-428, July.
    3. Turansick, Christopher, 2022. "Identification in the random utility model," Journal of Economic Theory, Elsevier, vol. 203(C).
    4. Fishburn, Peter C., 1992. "Induced binary probabilities and the linear ordering polytope: a status report," Mathematical Social Sciences, Elsevier, vol. 23(1), pages 67-80, February.
    5. Suck, Reinhard, 2002. "Independent random utility representations," Mathematical Social Sciences, Elsevier, vol. 43(3), pages 371-389, July.
    6. Morgan McClellon, 2015. "Unique Random Utility Representations," Working Paper 262661, Harvard University OpenScholar.
    7. Barbera, Salvador & Pattanaik, Prasanta K, 1986. "Falmagne and the Rationalizability of Stochastic Choices in Terms of Random Orderings," Econometrica, Econometric Society, vol. 54(3), pages 707-715, May.
    8. Clintin P. Davis-Stober & Jean-Paul Doignon & Samuel Fiorini & François Glineur & Michel Regenwetter, 2018. "Extended formulations for order polytopes through network flows," LIDAM Reprints CORE 2987, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    9. Irène Charon & Olivier Hudry, 2010. "An updated survey on the linear ordering problem for weighted or unweighted tournaments," Annals of Operations Research, Springer, vol. 175(1), pages 107-158, March.
    10. Fishburn, Peter C. & Falmagne, Jean-Claude, 1989. "Binary choice probabilities and rankings," Economics Letters, Elsevier, vol. 31(2), pages 113-117, December.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Christopher Turansick, 2023. "An Alternative Approach for Nonparametric Analysis of Random Utility Models," Papers 2303.14249, arXiv.org, revised May 2024.
    2. Haruki Kono & Kota Saito & Alec Sandroni, 2023. "Axiomatization of Random Utility Model with Unobservable Alternatives," Papers 2302.03913, arXiv.org, revised Aug 2023.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Sprumont, Yves, 0. "Randomized collective choices based on a fractional tournament," Theoretical Economics, Econometric Society.
    2. Suleymanov, Elchin, 2024. "Branching-independent random utility model," Journal of Economic Theory, Elsevier, vol. 220(C).
    3. Sam Cosaert & Thomas Demuynck, 2018. "Nonparametric Welfare and Demand Analysis with Unobserved Individual Heterogeneity," The Review of Economics and Statistics, MIT Press, vol. 100(2), pages 349-361, May.
    4. McClellon, Morgan, 2016. "Confidence models of incomplete preferences," Mathematical Social Sciences, Elsevier, vol. 83(C), pages 30-34.
    5. Turansick, Christopher, 2022. "Identification in the random utility model," Journal of Economic Theory, Elsevier, vol. 203(C).
    6. Faruk Gul & Wolfgang Pesendorfer, 2006. "Random Expected Utility," Econometrica, Econometric Society, vol. 74(1), pages 121-146, January.
    7. Regenwetter, Michel & Marley, A. A. J. & Grofman, Bernard, 2002. "A general concept of majority rule," Mathematical Social Sciences, Elsevier, vol. 43(3), pages 405-428, July.
    8. Daniele Caliari & Henrik Petri, 2024. "Irrational Random Utility Models," Papers 2403.10208, arXiv.org.
    9. Yaron Azrieli & John Rehbeck, 2022. "Marginal stochastic choice," Papers 2208.08492, arXiv.org.
    10. repec:cup:judgdm:v:8:y:2013:i:1:p:55-73 is not listed on IDEAS
    11. Itai Sher & Jeremy T. Fox & Kyoo il Kim & Patrick Bajari, 2011. "Partial Identification of Heterogeneity in Preference Orderings Over Discrete Choices," NBER Working Papers 17346, National Bureau of Economic Research, Inc.
    12. Daniel McFadden, 2005. "Revealed stochastic preference: a synthesis," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 26(2), pages 245-264, August.
    13. Yun-shil Cha & Michelle Choi & Ying Guo & Michel Regenwetter & Chris Zwilling, 2013. "Reply: Birnbaum's (2012) statistical tests of independence have unknown Type-I error rates and do not replicate within participant," Judgment and Decision Making, Society for Judgment and Decision Making, vol. 8(1), pages 55-73, January.
    14. Yuichi Kitamura & Jörg Stoye, 2013. "Nonparametric analysis of random utility models: testing," CeMMAP working papers 36/13, Institute for Fiscal Studies.
    15. Regenwetter, Michel & Grofman, Bernard & Marley, A. A. J., 2002. "On the model dependence of majority preference relations reconstructed from ballot or survey data," Mathematical Social Sciences, Elsevier, vol. 43(3), pages 451-466, July.
    16. De Donder, Philippe & Le Breton, Michel & Truchon, Michel, 2000. "Choosing from a weighted tournament1," Mathematical Social Sciences, Elsevier, vol. 40(1), pages 85-109, July.
    17. Simone Cerreia-Vioglio & David Dillenberger & Pietro Ortoleva & Gil Riella, 2019. "Deliberately Stochastic," American Economic Review, American Economic Association, vol. 109(7), pages 2425-2445, July.
      • Simone Cerreia-Vioglio & David Dillenberger & Pietro Ortoleva & Gil Riella, 2012. "Deliberately Stochastic," PIER Working Paper Archive 17-013, Penn Institute for Economic Research, Department of Economics, University of Pennsylvania, revised 25 May 2017.
    18. Thierry Denœux & Marie-Hélène Masson, 2012. "Evidential reasoning in large partially ordered sets," Annals of Operations Research, Springer, vol. 195(1), pages 135-161, May.
    19. Philip A. Haile & Ali Hortaçsu & Grigory Kosenok, 2008. "On the Empirical Content of Quantal Response Equilibrium," American Economic Review, American Economic Association, vol. 98(1), pages 180-200, March.
    20. Bandyopadhyay, Taradas & Bandyopadhyay, Bandyopadhyay & Pattanaik, Prasanta K., 2002. "Demand Aggregation and the Weak Axiom of Stochastic Revealed Preference," Journal of Economic Theory, Elsevier, vol. 107(2), pages 483-489, December.
    21. Yuichi Kitamura & Jörg Stoye, 2018. "Nonparametric Analysis of Random Utility Models," Econometrica, Econometric Society, vol. 86(6), pages 1883-1909, November.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:arx:papers:2207.06925. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.