zbMATH — the first resource for mathematics

Extended formulations for order polytopes through network flows. (English) Zbl 1411.91181
Summary: Mathematical psychology has a long tradition of modeling probabilistic choice via distribution-free random utility models and associated random preference models. For such models, the predicted choice probabilities often form a bounded and convex polyhedral set, or polytope. Polyhedral combinatorics have thus played a key role in studying the mathematical structure of these models. However, standard methods for characterizing the polytopes of such models are subject to a combinatorial explosion in complexity as the number of choice alternatives increases. Specifically, this is the case for random preference models based on linear, weak, semi- and interval orders. For these, a complete, linear description of the polytope is currently known only for, at most, 5-8 choice alternatives. We leverage the method of extended formulations to break through those boundaries. For each of the four types of preferences, we build an appropriate network, and show that the associated network flow polytope provides an extended formulation of the polytope of the choice model. This extended formulation has a simple linear description that is more parsimonious than descriptions obtained by standard methods for large numbers of choice alternatives. The result is a computationally less demanding way of testing the probabilistic choice model on data. We sketch how the latter interfaces with recent developments in contemporary statistics.

91B06 Decision theory
91B08 Individual preferences
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Full Text: DOI arXiv
[1] Armstrong, W., The determinateness of the utility function, Economics Journal, 49, 453-467, (1939)
[2] Bertsekas, D., Network optimization: Continuous and discrete models, (1998), Athena Scientific Belmont: Athena Scientific Belmont Belmont, Massachusetts · Zbl 0997.90505
[3] Bogart, K.; West, D., A short proof that “proper = unit”, Discrete Mathematics, 201, 21-23, (1999) · Zbl 0932.05065
[4] Boyd, S.; Pulleyblank, W., Facet generating techniques, (Research trends in combinatorial optimization, (2009), Springer: Springer Berlin, Germany), 33-55 · Zbl 1359.90113
[5] Brown, S. D.; Heathcote, A., The simplest complete model of choice response time: Linear ballistic accumulation, Cognitive Psychology, 57, 153-178, (2008)
[6] Christof, T.; Reinelt, G., Combinatorial optimization and small polytopes, TOP, 4, 1-64, (1996) · Zbl 0858.90107
[7] Conforti, M.; Cornuéjols, G.; Zambelli, G., Extended formulations in combinatorial optimization, 4OR. A Quarterly Journal of Operations Research, 8, 1-48, (2010) · Zbl 1219.90193
[8] Cormen, T.; Leiserson, C.; Rivest, R.; Stein, C., Introduction to algorithms, (2003), The M.I.T. Press: The M.I.T. Press Cambridge, Massachusetts
[9] Davis-Stober, C. P., Analysis of multinomial models under inequality constraints: Applications to measurement theory, Journal of Mathematical Psychology, 53, 1-13, (2009) · Zbl 1176.91140
[10] Davis-Stober, C. P.; Brown, N., A shift in strategy or “error”? Strategy classification over multiple stochastic specifications, Judgment and Decision Making, 6, 800-813, (2011)
[11] Davis-Stober, C. P.; Brown, N.; Cavagnaro, D. R., Individual differences in the algebraic structure of preferences, Journal of Mathematical Psychology, 66, 70-82, (2015) · Zbl 1354.91037
[12] Doignon, J.; Fiorini, S., Facets of the weak order polytope derived from the induced partition projection, SIAM Journal of Discrete Mathematics, 15, 112-121, (2002) · Zbl 1009.52024
[13] Doignon, J.-P.; Fiorini, S.; Joret, G., Facets of the linear ordering polytope: a unification for the fence family through weighted graphs, Journal of Mathematical Psychology, 50, 251-262, (2006) · Zbl 1096.05050
[14] Doignon, J.-P.; Fiorini, S.; Joret, G., Weighted graphs defining facets: a connection between stable set and linear ordering polytopes, Discrete Optimization, 6, 1-9, (2009) · Zbl 1221.05189
[15] Doignon, J.-P.; Rexhep, S., Primary facets of order polytopes, Journal of Mathematical Psychology, 75, 231-245, (2016) · Zbl 1396.91110
[16] Ducamp, A.; Falmagne, J. C., Composite measurement, Journal of Mathematical Psychology, 6, 359-390, (1969) · Zbl 0184.45501
[17] Erdfelder, E.; Auer, T.-S.; Hilbig, B. E.; Aßfalg, A.; Moshagen, M.; Nadarevic, L., Multinomial processing tree models: A review of the literature, Zeitschrift FÜr, 217, 108-124, (2009)
[18] Falmagne, J.-C., A representation theorem for finite random scale systems, Journal of Mathematical Psychology, 18, 52-72, (1978) · Zbl 0408.62093
[19] Fiorini, S., Polyhedral combinatorics of order polytopes, (2001), Université Libre de Bruxelles, Département de Mathématiques: Université Libre de Bruxelles, Département de Mathématiques Brussels, Belgium, (Ph.D. thesis)
[20] Fiorini, S., A short proof of a theorem of Falmagne, Journal of Mathematical Psychology, 48, 80-82, (2004) · Zbl 1053.60009
[21] Fiorini, S., \(\{0, 1 / 2 \}\)-cuts and the linear ordering problem: Surfaces that define facets, SIAM Journal of Discrete Mathematics, 20, 893-912, (2006) · Zbl 1126.05081
[22] Fiorini, S., How to recycle your facets, Discrete Optimization, 3, 136-153, (2006) · Zbl 1146.90478
[23] Fiorini, S.; Fishburn, P. C., Weak order polytopes, Discrete Mathematics, 275, 111-127, (2004) · Zbl 1077.91016
[24] Fiorini, S.; Massar, S.; Pokutta, S.; Tiwary, H.; Wolf, R.d., Exponential lower bounds for polytopes in combinatorial optimization, Journal of the Association for Computing Machinery, 62, 17.1-17.23, (2015)
[25] Fiorini, S.; Pashkovich, K., Uncapacitated flow-based extended formulations, Mathematical Progamming, 153, 117-131, (2015) · Zbl 1356.90122
[26] Fishburn, P., Intransitive indifference with unequal indifference intervals, Journal of Mathematical Psychology, 7, 144-149, (1970) · Zbl 0191.31501
[27] Fishburn, P. C., Interval orders and interval graphs, (1985), Wiley: Wiley New York, New York · Zbl 0568.05047
[28] Garey, M.; Johnson, D., Computers and intractability. A guide to the theory of NP-completeness, (1979), Freeman: Freeman New York, New York · Zbl 0411.68039
[29] Kaibel, V., Extended formulations in combinatorial optimization, Optima, 85, 2-7, (2011)
[30] Kaibel, V.; Weltge, S., A short proof that the extension complexity of the correlation polytope grows exponentially, Discrete & Computational Geometry, 53, 397-401, (2014) · Zbl 1315.52021
[31] Karabatsos, G., Bayesian nonparametric model selection and model testing, Journal of Mathematical Psychology, 50, 123-148, (2006) · Zbl 1099.62005
[32] Kass, R. E.; Raftery, A. E., Bayes factors, Journal of the American Statistical Association, 90, 773-795, (1995) · Zbl 0846.62028
[33] Klugkist, I.; Hoijtink, H., The Bayes factor for inequality and about equality constrained models, Computational Statistics & Data Analysis, 51, 6367-6379, (2007) · Zbl 1445.62049
[34] Korte, B.; Vygen, J., Combinatorial optimization, (2008), Springer: Springer Berlin, Germany · Zbl 1149.90126
[35] Luce, R. D., Semiorders and a theory of utility discrimination, Econometrica, 26, 178-191, (1956) · Zbl 0071.14006
[36] Luce, R. D., Utility of gains and losses: Measurement-theoretical and experimental approaches, (2000), Mahwah, New Jersey: Lawrence Erlbaum Association, Psychology Press · Zbl 0997.91500
[37] Maksimenko, A. N., A Boolean quadratic polytope is the face of a linear-order polytope, Sibirskie Èlektronnye Matematicheskie Izvestiya, 14, 640-646, (2017), (in Russian)
[38] Martí, R.; Reinelt, G., (The linear ordering problem: Exact and heuristic methods in combinatorial optimization. Applied Mathematical Sciences: vol. 175, (2011), Berlin, Germany: Springer) · Zbl 1213.90005
[39] Mirkin, B. G., Description of some relations on the set of real-line intervals, Journal of Mathematical Psychology, 9, 243-252, (1972) · Zbl 0236.06002
[40] Müller, R.; Schulz, A., The interval order polytope of a digraph, (Balas, E.; Clausen, J., Integer programming and combinatorial optimization. Lecture Notes in Computer Science: vol. 920, (1995)), 50-64, Proceedings of the 4th International IPCO Conference
[41] Myung, J. I.; Karabatsos, G.; Iverson, G. J., A Bayesian approach to testing decision making axioms, Journal of Mathematical Psychology, 49, 205-225, (2005) · Zbl 1104.91016
[42] Nesterov, Y.; Nemirovskii, A., (Interior-point polynomial algorithms in convex programming. SIAM Studies in Applied Mathematics: vol. 13, (1994), Philadelphia, Pennsylvania: Society for Industrial and Applied Mathematics) · Zbl 0824.90112
[43] Oswald, M.; Reinelt, G.; Seitz, H., Applying mod-\(k\)-cuts for solving linear ordering problems, TOP, 17, 158-170, (2009) · Zbl 1170.90469
[44] Pirlot, M.; Vincke, P., Semiorders: Properties, representations, applications, (1997), Kluwer: Kluwer Dordrecht, The Netherlands · Zbl 0897.06002
[45] Ratcliff, R.; Rouder, J. N., Modeling response times for two-choice decisions, Psychological Science, 9, 347-356, (1998)
[46] Ratcliff, R.; Smith, P. L., A comparison of sequential sampling models for two-choice reaction time, Psychological Review, 111, 333-367, (2004)
[47] Regenwetter, M.; Dana, J.; Davis-Stober, C. P., Testing transitivity of preferences on two-alternative forced choice data, Frontiers in Quantitative Psychology and Measurement, 1, (2010)
[48] Regenwetter, M.; Dana, J.; Davis-Stober, C. P., Transitivity of preferences, Psychological Review, 118, 42-56, (2011)
[49] Regenwetter, M.; Dana, J.; Davis-Stober, C. P.; Guo, Y., Parsimonious testing of transitive or intransitive preferences: Reply to Birnbaum (2011), Psychological Review, 118, 684-688, (2011)
[50] Regenwetter, M.; Davis-Stober, C., Ternary paired comparisons induced by semi- or interval order preferences, (Dzhafarov, E.; Perry, L., Descriptive and normative approaches to human behavior. Advanced Series on Mathematical Psychology: vol. 3, (2011), World Scientific: World Scientific Singapore), 225-248 · Zbl 1320.91049
[51] Regenwetter, M.; Davis-Stober, C., Behavioral variability of choices versus structural inconsistency of preferences, Psychological Review, 119, 408-416, (2012)
[52] Regenwetter, M.; Marley, A. A.J., Random relations, random utilities, and random functions, Journal of Mathematical Psychology, 45, 864-912, (2001) · Zbl 1004.91071
[53] Roberts, F. S., Measurement theory, (1979), Addison-Wesley: Addison-Wesley London, United Kingdom
[54] Scott, D.; Suppes, P., Foundational aspects of theories of measurement, Journal of Symbolic Logic, 23, 113-128, (1958) · Zbl 0084.24603
[55] Silvapulle, M.; Sen, P., (Constrained statistical inference. Wiley Series in Probability and Statistics, (2005), Wiley-Interscience [John Wiley & Sons]: Wiley-Interscience [John Wiley & Sons] Hoboken, New Jersey)
[56] Sloane, N. (2016). The On-Line Encyclopedia of Integer Sequences. Published electronically at https://oeis.org/. · Zbl 1044.11108
[57] Suck, R. (1995). Random utility representations based on semiorders, interval orders, and partial orders. Unpublished manuscript.
[58] Trueblood, J. S.; Brown, S. D.; Heathcote, A., The multiattribute linear ballistic accumulator model of context effects in multialternative choice, Psychological Review, 121, 179, (2014)
[59] Tversky, A., Intransitivity of preferences, Psychological Review, 76, 31-48, (1969)
[60] Wiener, N., Studies in synthetic logic, Proceeding of the Cambridge Philosophical Society, 18, 14-28, (1915) · JFM 45.1216.08
[61] Wolsey, L. A., Using extended formulations in practice, Optima, 85, 7-9, (2011)
[62] Ziegler, G., Lectures on polytopes, (1998), Springer-Verlag: Springer-Verlag Berlin, Germany
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.