365体育网站

365体育网站Advertisement

Springer Nature is making SARS-CoV-2 and COVID-19 research free. View research | View latest news | Sign up for updates

The impact of dependence among voters’ preferences with partial indifference

Abstract

Standard weighted scoring rules do not directly accommodate the possibility that some voters might have dichotomous preferences in three-candidate elections. The direct solution to this issue would be to require voters to arbitrarily break their indifference ties on candidates and report strict rankings. This option was previously found to be a poor alternative when voters have completely independent preferences. The introduction of a small degree of dependence among voters’ preferences has typically been found to make a significant reduction of the impact of such negative outcomes in earlier studies. However, we find that the forced ranking option continues to be a poor choice when dependence is introduced among voters’ preferences. This conclusion is reinforced by the fact that other voting options like Approval Voting and Extended Scoring Rules have been found to produce much better results. These observations are made as a result of using a significant advancement in techniques that obtain probability representations for such outcomes.

This is a preview of subscription content, log in to check access.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Notes

  1. 1.

    365体育网站Online appendix: . Full input and output data of calculations: .

References

  1. 365体育网站Baldoni, V., Berline, N., De Loera, J., Köppe, M., Vergne, M.: Three Ehrhart Quasi-polynomials, Preprint at (2014)

  2. Berg, S., Bjurulf, B.: A note on the paradox of voting: anonymous preference profiles and May’s formula. Public Choice 40365体育网站, 307–316 (1983)

  3. Brams, S.J., Fishburn, P.C.: Approval Voting. Birkhäuser, Boston (1983)

  4. Clauss, P., Loechner, V.: Parametric analysis of polyhedral iteration spaces. J. VLSI Signal Process. Syst. Signal Image Video Technol. 19365体育网站(2), 179–194 (1998)

  5. Courtin, S., Martin, M., Moyouwou, I.: The q-majority efficiency of positional rules. Theory Decis. 79365体育网站, 31–49 (2015)

  6. Diss, M., Merlin, V., Valognes, F.: On the Condorcet efficiency of approval voting and extended scoring rules for three alternatives. In: Laslier, J.-F., Sanver, R.M. (eds.) Handbook on Approval Voting, pp. 255–283. Springer, Berlin (2010)

  7. Diss, M., Pérez-Asurmendi, P.: Consistent collective decisions under majorities based on difference of votes. Theory Decis. 80, 473–494 (2016)

  8. Ehrhart, E.: Sur les polyhèdres rationnels homothétiques à n dimensions. C. R. Acad. Sci. Paris 254, 616–618 (1962)

  9. Fishburn, P.C., Gehrlein, W.V.: The paradox of voting: effects of individual indifference and intransitivity. J. Public Econ. 14365体育网站, 83–94 (1980)

  10. Gehrlein, W.V.: Condorcet efficiency and constant scoring rules. Math. Soc. Sci. 2365体育网站, 123–130 (1982)

  11. 365体育网站Gehrlein, W.V.: The impact of forcing preference rankings when indifference exists. In: Van Deemen, A., Rusinowska, A. (eds.) Collective Decision Making: views from Social Choice and Game Theory, pp. 17–29. Springer, Berlin (2010)

  12. Gehrlein, W.V., Fishburn, P.C.: Condorcet’s paradox and anonymous preference profiles. Public Choice 26, 1–18 (1976)

  13. Gehrlein, W.V., Lepelley, D.: The Condorcet efficiency of approval voting and the probability of electing the Condorcet loser. J. Math. Econ. 29, 271–283 (1998)

  14. Gehrlein, W.V., Lepelley, D.: The Condorcet efficiency of Borda rule with anonymous voters. Math. Soc. Sci. 41365体育网站, 39–50 (2001)

  15. Gehrlein, W.V., Lepelley, D.: Voting Paradoxes and Group Coherence: the Condorcet Efficiency of Voting Rules. Springer, Berlin (2010)

  16. Gehrlein, W.V., Lepelley, D.: The value of research based on simple assumptions about voters’ preferences. In: Felsenthal, D.S., Machover, M. (eds.) Electoral Systems: paradoxes, Assumptions and Procedures. Springer, Berlin (2011)

  17. Gehrlein, W.V., Lepelley, D.: The Condorcet efficiency advantage that voter indifference gives to approval voting over some other voting rules. Group Decis. Negot. 24, 243–269 (2015)

  18. Gehrlein, W.V., Valognes, F.: Condorcet efficiency: a preference for indifference. Soc. Choice Welf 18, 193–205 (2001)

  19. Gehrlein, W.V., Lepelley, D., Plassmann, F.: Should voters be required to rank candidates in an election? Soc. Choice Welf 46365体育网站, 707–747 (2015a)

  20. Gehrlein, W.V., Lepelley, D., Plassmann, F.: Further support for ranking candidates in elections. Group Decis. Negot. 25, 941–966 (2015b)

  21. Guilbaud, G.T.: Les théories de l’intérêt général et le problème logique de l’agrégation. Econ. Appl. 5365体育网站, 501–584 (1952)

  22. Kamwa, E., Merlin, V.: Scoring rules over subsets of alternatives: consistency and paradoxes. J. Math. Econ. 16, 130–138 (2015)

  23. Lepelley, D., Louichi, A., Smaoui, H.: On Ehrhart polynomials and probability calculations in voting theory. Soc. Choice Welf. 30365体育网站, 363–383 (2008)

  24. Rehn, T., Schürmann, A.: C++ Tools for Exploiting Polyhedral Symmetries, in Mathematical SoftwareICMS 2010, Springer Lecture Notes in Computer Science, 6327 (2010): 295–298. Software Sympol.

  25. Schürmann, A.: Exploiting polyhedral symmetries in social choice. Soc. Choice Welf. 40, 1097–1110 (2013)

  26. Sen, A.K.: Preferences, votes and the transitivity of majority decisions. Rev. Econ. Stud. 31, 163–165 (1964)

  27. Verdoolaege, S.:“Barvinok: User guide.” Version 0.39, Electronically (2016).

  28. Verdoolaege, S., Bruynooghe, M.: Algorithms for weighted counting over parametric polytopes: a survey and a practical comparison. In: Proceedings of the 2008 International Conference on Information Theory and Statistical Learning (ITSL) (2008)

Download references

Acknowledgements

365体育网站Erik Friese and Achill Schürmann were partially supported by DFG-Grant SCHU 1503/6-1.

Author information

Correspondence to Achill Schürmann.

Appendices

Appendix: Counting lattice points in parametric polytopes

Mathematical framework

The total number of possible voting situations that result in some specified election outcome can be modeled as the number of integral solutions of a system of linear inequalities that are dependent on the total number \(n\) of all voters, and on the number \(k\) of them having strict preference rankings on the candidates. More precisely, we are dealing with a parametric polytope \(P\), i.e. a family of polytopes \(P_{n,k} \subset {\mathbb{Q}}^{d}\) of the form

$$P_{n,k} = \left\{ {x \in {\mathbb{Q}}^{d} :Fx \le G\left( {\begin{array}{*{20}c} n \\ k \\ \end{array} } \right) + c} \right\}$$

for certain \(d\)- and \(2\)-column matrices \(F\) and \(G\) and a suitable vector \(c\). The enumerator \({\mathcal{E}}_{P}\), defined by

$${\mathcal{E}}_{P} \left( {n,k} \right) = \# \left( {P_{n,k} \mathop \cap \nolimits {\mathbb{Z}}^{d} } \right),$$

counts the number of integral points contained in \(P\) depending on \(n\) and \(k\). That is, it counts the number of different voting situations with the specified election outcome, given \(n\) voters with \(k\) of them having strict preference rankings.

By a mathematical theory going back to the work of Ehrhart (1962) we can express \({\mathcal{E}}_{P} (n,k)\) by a closed formula. Its use in voting theory is for instance described in Lepelley et al. (2008). For the multi-parameter setting, it was proven by Clauss and Loechner (1998), that the parameter space (\({\mathbb{Z}}^{2}\) in our case) can be decomposed into finitely many polyhedra, called chambers, such that \({\mathcal{E}}_{P}\) for each chamber is a quasipolynomial, which is a polynomial with coefficients that are periodic. The important component for us is the leading term \({\text{LT}}_{P}\) of \({\mathcal{E}}_{P}\)365体育网站 which is known to be a polynomial on each chamber.

Let P and S denote parametric polytopes, with \(P\) contained in \(S\). Then, the expected relative frequency of voting situations being in \(P\), among voting situations in \(S\)365体育网站 is expressed by

$$Prob(n,k) = \frac{{{\mathcal{E}}_{P} (n,k)}}{{{\mathcal{E}}_{S} (n,k)}}$$

Since the formulas for \(Prob(n,k)\) are too cumbersome for practical purposes, we restrict our attention to the probability for \(n\) and \(k\) tending to infinity. More precisely, let \(\alpha = k/n\) be the probability that a random voter has a strict preference ranking on the candidates, and let \({\text{LT}}_{P}\) and \({\text{LT}}_{S}\) be the leading terms (which are homogeneous polynomials) of \({\mathcal{E}}_{P}\) and \({\mathcal{E}}_{S}\), respectively, on some fixed chamber. Then we have

$$Prob(n,\alpha n)\mathop \to \limits^{n \to \infty } \frac{{{\text{LT}}_{P} (1,\alpha )}}{{{\text{LT}}_{S} (1,\alpha )}},$$

given that \({\mathcal{E}}_{P}\) and \({\mathcal{E}}_{S}\) have the same total degree, and \(\alpha\) is such that \(\left( {\begin{array}{*{20}c} n \\ {\alpha n} \\ \end{array} } \right)\) lies in the fixed chamber mentioned before, for all sufficiently large values of \(n\). In the examples we are concerned with, these constraints are always satisfied, so in order to determine the limiting probability it suffices to calculate the polynomials \({\mathcal{E}}_{P}\) and \({\mathcal{E}}_{S}\). Note that each chamber gives a segment of α365体育网站-values for which a closed probability formula is obtained.

Practical computations

We use the software package barvinok to compute the quasipolynomials \({\mathcal{E}}_{P}\) and \({\mathcal{E}}_{S}\) on all chambers. Afterwards, we filter out the chambers, we are interested in (i.e. those containing \((n,\alpha n)^{t}\) for sufficiently large \(n\), where \(0 \le \alpha \le 1\)), and cut off the leading terms of the corresponding quasipolynomials to obtain the polynomials \({\text{LT}}_{P}\) and \({\text{LT}}_{S}\)365体育网站 on those chambers.

In the following we demonstrate an example calculation of the limiting probability \(P_{CW}^{\infty } (\alpha ,EIAC)\) that a CW exists, given that \(k = \alpha n\) of \(n\) voters have strict preferences on the candidates, where \(0 < \alpha < \frac{1}{4}\). Figure 9 shows the input file which encodes the parametric polytope \(P\) that describes all voting situations where Candidate A is the CW [see Verdoolaege (2016) concerning the syntax]. The first two equalities, as denoted by a 0 in the first column in Fig 9, specify that there are exactly \(k\) voters having strict rankings (distributed among \(n_{1} , \ldots ,n_{6}\)) and \(n - k\) voters with partial indifferences (distributed among \(n_{7} , \ldots ,n_{12}\)). The next two inequalities, as specified by a 1 in the first column, then describe those voting situations where A M B and A M C respectively. Finally, there are 12 inequalities specifying that all \(n_{i}\) are nonnegative.

Fig. 9
figure9

Parametric polytope P describing the voting situations where candidate A is a CW

Applying the program barvinok_enumerate_e to this file yields the complete list of all chambers and corresponding quasipolynomials describing the enumerator \({\mathcal{E}}_{P}\). They are too lengthy to print them here, but we can handle their leading terms. On the chamber \(\left\{ {(n,k)^{t} \in {\mathbb{Z}}^{2} :n \ge 4k + 2,k \ge 1} \right\}\) for example the leading term of the quasipolynomial \({\mathcal{E}}_{P}\)365体育网站 is given by

$$\begin{array}{*{20}c} {{\text{LT}}_{P} \left( {n,k} \right) = \frac{ - 1573}{58060800}k^{10} + \frac{1}{8960}nk^{9} - \frac{1}{4480}n^{2} k^{8} + \frac{83}{362880}n^{3} k^{7} - \frac{1}{8640}n^{4} k^{6} + \frac{1}{43200}n^{5} k^{5} } \\ \end{array}$$

Since each of the three candidates is a CW in the same number of voting situations, \(3 \cdot {\mathcal{E}}_{P}\) gives the total number of voting situations where a CW exists, so the leading term of the enumerator is \(3 \cdot {\text{LT}}_{P}\) for the corresponding chamber. A representation of the parametric polytope \(S\) corresponding to all possible voting situations for which k voters have strict preference rankings is obtained from Figure A.1 by removing the first and second inequalities. On the chamber \(\left\{ {(n,k)^{t} \in {\mathbb{Z}}^{2} :0 \le k \le n} \right\}\), which clearly contains the previous chamber, the enumerator \({\mathcal{E}}_{S}\)365体育网站 is given by the polynomial

$$\begin{array}{*{20}c} {{\mathcal{E}}_{S} (n,k) = \left( {\begin{array}{*{20}c} {k + 5} \\ 5 \\ \end{array} } \right) \cdot \left( {\begin{array}{*{20}c} {n - k + 5} \\ 5 \\ \end{array} } \right)} \\ \end{array} .$$

365体育网站Its leading term is

$$\begin{array}{*{20}c} {{\text{LT}}_{S} (n,k) = \frac{1}{14400}(n - k)^{5} k^{5} } \\ \end{array} .$$

Putting these results together, we obtain

$$\begin{aligned} P_{CW}^{\infty } (\alpha ,EIAC) &= \mathop { \lim }\limits_{n \to \infty } \frac{{3 \cdot {\mathcal{E}}_{P} (n,\alpha n)}}{{{\mathcal{E}}_{S} (n,\alpha n)}} = \frac{{3 \cdot {\text{LT}}_{P} (1,\alpha )}}{{{\text{LT}}_{S} (1,\alpha )}} \hfill \\ &= \frac{{ - 1573\alpha^{5} + 6480\alpha^{4} - 12960\alpha^{3} + 13280\alpha^{2} - 6720\alpha + 1344}}{{1344(1 - \alpha )^{5} }} \hfill \\ \end{aligned}$$

for all \(0 < \alpha < \frac{1}{4}\). The probability representations concerning the remaining segments of \(\alpha\) values are obtained in exactly the same way.

Exploiting symmetries

If a parametric polytope \(P_{n,k}\) has symmetries, i.e. if there exist permutations of the variables \(x_{1} , \ldots ,x_{d}\) under which it stays unchanged, one may hope for some computational gain by exploiting the structure coming with these symmetries. One such approach in the one parameter case was successfully applied to voting problems in Schürmann (2013). A generalization to the setting of more than one parameter is principally possible: If certain sums of \(m\)  variables, say \(n_{{i_{1} }} + \cdots + n_{{i_{m} }}\), occur in all relevant inequalties and equations together, we can substitute them by a single new variable, say \(N\). In order to obtain the same counting results with \(m - 1\) variables less, we have to adapt the way of counting though. For a fixed nonnegative integer  \(N\) we have to count \(\left( {\begin{array}{*{20}c} {N + m} \\ m \\ \end{array} } \right)\) voting situations (which is a polynomial in \(N\) of degree \(m\)), as it gives the number of possibilities to choose different nonnegative integers \(n_{{i_{1} }} , \ldots ,n_{{i_{m} }}\) with \(N = n_{{i_{1} }} + \ldots + n_{{i_{m} }}\). With several of such substitutions we get a product of polynomials in the new variables, which we have to use as weights in a new dimension reduced weighted counting problem.

We applied this approach to our voting examples using the barvinok package, which is currently—to the best of our knowledge—the only available software package capable of weighted counting computations with more than one parameter (and with weights being quasi-polynomials). There are three different methods implemented that we could use (see Verdoolaege and Bruynooghe 2008).

In the examples of this paper we computed all affine symmetries of the parametric polytopes, using the software Sympol (see Rehn and Schürmann 2010). In each case these symmetries turned out to come from permutations of coordinates, many of them allowing a reformulation into a weighted counting problem as described above. In some of the computations this has a substantial beneficial effect. In one of the cases (FCW) we were able to take advantage of a symmetry group of order 9216 giving a reduction of computation time to roughly 25 %. However, in another case (BR-CW) there was no symmetry we could take advantage of. Unfortunately, this was the computation taking by far the longest to finish (more than half a year on a machine with two Xeon X5650 Six Core 2.66 GHz processors).

We finally note that we think, in the future it should be possible to take more advantage of available symmetries. Recent theoretical advances as in Baldoni et al. (2014) seem to show that in particular the computation of leading terms should be easier, once a counting problem can be reduced to a lower dimensional weighted counting problem. However, at the moment we are still missing efficient software to take advantage of such reformulations in practical multi-parameter computations.

Rights and permissions

About this article

Cite this article

Friese, E., Gehrlein, W.V., Lepelley, D. et al. The impact of dependence among voters’ preferences with partial indifference. Qual Quant 51, 2793–2812 (2017). http://doi.org/10.1007/s11135-016-0446-7

Download citation

  • Published:

  • Issue Date:

Keywords

  • Partial indifference of voters
  • Weighted scoring rules
  • Condorcet efficiency
  • Impartial culture and impartial anonymous culture (IC and IAC)
  • Polyhedral computations
  • Ehrhart theory