×

An approval-voting polytope for linear orders. (English) Zbl 0892.90044

Summary: A probabilistic model of approval voting on \(n\) alternatives generates a collection of probability distributions on the family of all subsets of the set of alternatives. Focusing on the size-independent model proposed by Falmagne and Regenwetter, we recast the problem of characterizing these distributions as the search for a minimal system of linear equations and inequalities for a specific convex polytope. This approval-voting polytope, with \(n!\) vertices in a space of dimension \(2^n\), is proved to be of dimension \(2^n-n-1\). Several families of facet-defining linear inequalities are exhibited, each of which has a probabilistic interpretation. Some proofs rely on special sequences of rankings of the alternatives. Although the equations and facet-defining inequalities found so far yield a complete minimal description when \(n\leq 4\) (as indicated by the PORTA software), the problem remains open for larger values of \(n\).

MSC:

91B12 Voting theory

Software:

PORTA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brams, S. J.; Fishburn, P. C., Approval Voting (1983), Birkhäuser: Birkhäuser Boston · Zbl 0537.90001
[2] T. Christof, 1996, PORTA—A polyhedron representation transformation algorithm; T. Christof, 1996, PORTA—A polyhedron representation transformation algorithm
[3] Dieudonné, J., Foundations of Modern Analysis (1960), Academic Press: Academic Press New York · Zbl 0100.04201
[4] Doignon, J.-P.; Falmagne, J.-C., A polynomial time algorithm for unidimensional unfolding representations, Journal of Algorithms, 16, 218-233 (1994) · Zbl 0797.68081
[5] Dowling, C., On the irredundant construction of knowledge spaces, Journal of Mathematical Psychology, 37, 49-62 (1993) · Zbl 0772.92018
[6] Falmagne, J.-C.; Regenwetter, M., A random utility model for approval voting, Journal of Mathematical Psychology, 40, 152-159 (1996) · Zbl 0866.90041
[7] Fishburn, P. C., Induced binary probabilities and the linear ordering polytope: A status report, Mathematical Social Sciences, 23, 67-80 (1992) · Zbl 0751.90004
[8] Grünbaum, B., Convex Polytopes (1967), Wiley: Wiley New York · Zbl 0163.16603
[9] Harary, F., Graph Theory (1969), Addison-Wesley: Addison-Wesley Reading · Zbl 0797.05064
[10] Koppen, M., Random utility representations of binary choice probabilities: Critical graphs yielding critical necessary conditions, Journal of Mathematical Psychology, 39, 21-39 (1995) · Zbl 0897.92045
[11] Marley, A. A.J., A historical and contemporary perspective on random scale representations of choice probabilities and reaction times in the context of Cohen and Falmagne’s (1990,Journal of Mathematical Psychology34, Journal of Mathematical Psychology, 34, 81-87 (1990) · Zbl 0689.92019
[12] Merrill, S. I., Making Multicandidate Elections More Democratic (1988), Princeton Univ. Press: Princeton Univ. Press New Jersey
[13] Nurmi, H., Comparing Voting Systems (1987), Kluwer
[14] M. Regenwetter, 1995, Random utility representations and probabilistic models of subset choice and ranking data, Mathematical Behavioral Sciences, University of California, Irvine; M. Regenwetter, 1995, Random utility representations and probabilistic models of subset choice and ranking data, Mathematical Behavioral Sciences, University of California, Irvine
[15] Regenwetter, M., Random utility representations of finite m-ary relations, Journal of Mathematical Psychology, 40, 219-234 (1996) · Zbl 0862.60017
[16] Regenwetter, M.; Grofman, B., Choosing subsets: A size-independent probabilistic model and the quest for a social welfare ordering, Social Choice and Welfare (1995) · Zbl 1066.91542
[17] M. Regenwetter, B. Grofman, Approval voting, Borda winners and Condorcet winners: Evidence from seven elections, Management Science; M. Regenwetter, B. Grofman, Approval voting, Borda winners and Condorcet winners: Evidence from seven elections, Management Science · Zbl 0989.90093
[18] M. Regenwetter, A. Marley, H. Joe, 1996, Random utility threshold models of subset choice; M. Regenwetter, A. Marley, H. Joe, 1996, Random utility threshold models of subset choice
[19] Sen, A. K., A possibility theorem on majority decisions, Econometrica, 34, 491-499 (1966) · Zbl 0149.17003
[20] Suck, R., Geometric and combinatorial properties of the polytope of binary choice probabilities, Mathematical Social Sciences, 23, 81-102 (1992) · Zbl 0751.90006
[21] R. Suck, 1996, Random utility representations based on semiorders, interval orders and partial orders; R. Suck, 1996, Random utility representations based on semiorders, interval orders and partial orders
[22] Weber, R. J., Approval voting, Journal of Economic Perspectives, 9, 39-49 (1995)
[23] Ziegler, G. M., Lectures on Polytopes (1995), Springer-Verlag: Springer-Verlag Berlin · Zbl 0823.52002
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.