Search

The impossibility theorems of Arrow and Gibbard-Satterthwaite have been thought to rule out economic democracy and welfare economics. This paper demonstrates an information processing system which accords with the premises of these authors, and, consequently, proves their conclusions of impossibility to be untrue except as mathematical tautologies.

We study multiwinner elections with approval-based preferences. An instance of a multiwinner election consists of a set of alternatives, a population of voters---each voter approves a subset of alternatives, and the desired committee size $k$; the goal is to select a committee (a~subset) of $k$ alternatives according to the preferences of the voters. We investigate a number of election rules and ask whether the committees that they return represent the voters proportionally. In contrast to the classic literature, we employ quantitative techniques that allow to measure the extent to which the considered rules are proportional. This allows us to arrange the rules in a clear hierarchy. For example, we find that Proportional Approval Voting (PAV) has better proportionality guarantees than its sequential counterpart, and that Phragm\'{e}n's Sequential Rule is worse than Sequential PAV. Yet, the loss of proportionality for the two sequential rules is moderate and in some contexts can be outweighed by their other appealing properties. Finally, we measure the tradeoff between proportionality and utilitarian efficiency for a broad subclass of committee election rules.

Under approval voting (AV), each voter just distinguishes the candidates he approves of from those appearing as unacceptable. The preference approval voting (PAV) is a hybrid version of the approval voting first introduced by Brams and Sanver (in: Brams, Gehrlein, Roberts (eds) The mathematics of preference, choice and order. Springer, Berlin, pp 215–237, 2009). Under PAV, each voter ranks all the candidates and then indicates the ones he approves. In this paper, we provide an analytical representation of the limiting probability that PAV elects the Condorcet winner (resp. the Condorcet loser) when she exists in three-candidate elections. We perform our analysis by assuming the assumption of the Extended Impartial Culture. The aim is to measure at which extend PAV performs better than AV both on the propensity of electing the Condorcet winner and on that of the non-election of the Condorcet loser. For this purpose, we also provide an analytical representation of the limiting probability that AV elects the Condorcet winner (resp. the Condorcet loser) when she exists in three-candidate elections. Our representation of the limiting probability that AV elects the Condorcet winner is more general than that provided by Diss et al. (in: Laslier and Sanver (eds) Handbook on approval voting. Springer, Berlin, pp 255–283, 2010) and it leads to the same figures as the representation provided by Gehrlein and Lepelley (Group Decis Negot 24:243–269, 2015).

Although two-round voting procedures are common, the theoretical voting literature rarely discusses any such rules beyond the traditional plurality runoff rule. Therefore, using four criteria in conjunction with two data-generating processes, we define and evaluate nine “runoff pair selection rules” that comprise two rounds of voting, two candidates in the second round, and a single final winner. The four criteria are: social utility from the expected runoff winner (UEW), social utility from the expected runoff loser (UEL), representativeness of the runoff pair (Rep), and resistance to strategy (RS). We examine three rules from each of three categories: plurality rules, utilitarian rules and Condorcet rules. We find that the utilitarian rules provide relatively high UEW and UEL, but low Rep and RS. Conversely, the plurality rules provide high Rep and RS, but low UEW and UEL. Finally, the Condorcet rules provide high UEW, high RS, and a combination of UEL and Rep that depends which Condorcet rule is used.

The Gibbard–Satterthwaite theorem states that for any non-dictatorial voting system there will exist an election where a voter, called a manipulator, can change the election outcome in their favour by voting strategically. When a given preference profile admits several manipulators, voting becomes a game played by these voters, who have to reason strategically about each other’s actions. To complicate the game even further, some voters, called countermanipulators, may try to counteract potential actions of manipulators. Previously, voting manipulation games have been studied mostly for the Plurality rule. We extend this to k -Approval voting rules. However, unlike previous studies, we assume that voters are boundedly rational and do not think beyond manipulating or countermanipulating. We classify all 2-by-2 games that can be encountered by these strategic voters, and investigate the complexity of arbitrary voting manipulation games, identifying conditions on strategy sets that guarantee the existence of a Nash equilibrium in pure strategies.

As a common task for choosing a group of representatives, the problem of approval voting has been studied in contexts varying from democratic elections, to sports, to products marketing, and to multi-criteria decision making. In these applications, the length of individual ballots is often enforced, but how many candidates should be approved in an individual ballot is still a puzzling question. The experimental framework we present here endeavors to understand the impact of ballot-length in the effectiveness of election outcomes. Our results suggest that: (1) given the number of voters and candidates, the effectiveness of election outcome is U-shaped in the variance of individual ballot-length; (2) the determination of the optimal ballot-length critically depends on the accuracy of ballots; (3) more voters bring more effective election outcomes. Our study of how ballot length affects the effectiveness of election outcome provides new insights into an understudied area, and it can serve as a starting point for future studies of the approval balloting-based elections in other retail contexts.

The organization of US presidential elections make them potentially vulnerable to so-called “voting paradoxes”, identified by social choice theorists but rarely documented empirically. The presence of a record high number of candidates in the 2016 Republican Party presidential primaries may have made this possibility particularly latent. Using polling data from the primaries we identify two possible cases: Early in the pre-primary (2015) a cyclical majority may have existed in Republican voters’ preferences between Bush, Cruz and Walker—thereby giving a rare example of the Condorcet Paradox. Furthermore, later polling data (March 2016) suggests that while Trump (who achieved less than 50% of the total Republican primary vote) was the Plurality Winner, he could have been beaten in pairwise contests by at least one other candidate—thereby exhibiting a case of the Borda Paradox. The cases confirm the empirical relevance of the theoretical voting paradoxes and the importance of voting procedures.

We study how voting rules shape voter coordination in large three-candidate elections. We consider three rules, varying according to the number of candidates that voters can support in their ballot: Plurality (one), Anti-Plurality (two) and Approval Voting (one or two). We show that the Condorcet winner—a normatively desirable candidate—can always be elected at equilibrium under Approval Voting. We then numerically study a dynamic process of political tâtonnement. Monte-Carlo simulations of the process deliver rich insights on election outcomes. The Condorcet winner is virtually always elected under Approval Voting, but not under the other rules. The dominance of Approval Voting is robust to alternative welfare criteria and to the introduction of expressive voters.

Arribillaga acknowledges financial support received from the Universidad Nacional de San Luis, through Grant 319502, and from the Consejo Nacional de Investigaciones Científicas y Técnicas (CONICET), through Grant PIP 112-200801-00655. Massó acknowledges financial support received from the Spanish Ministry of Economy and Competitiveness, through the Severo Ochoa Programme for Centres of Excellence in R&D (SEV-2015-0563) and Grant ECO2014-53051-P, and from the Generalitat de Catalunya, through Grant SGR2014-515. The paper was partly written while Massó was visiting the Department of Economics at Stanford University. He wishes to acknowledge the hospitality of its members as well as financial support received from the Spanish Ministerio de Educación, Cultura y Deporte, through Project PR2015-00408. Altres ajuts: UNSL/319502 Altres ajuts: CONICET/PIP112-200801-00655 We consider the class of voting by committees to be used by a society to collectively choose a subset from a given set of objects. We offer a simple criterion to compare two voting by committees without dummy agents according to their manipulability. This criterion is based on the set-inclusion relationships between the two corresponding pairs of sets of objects, those at which each agent is decisive and those at which each agent is vetoer. We show that the binary relation "to be as manipulable as" endows the set of equivalence classes of anonymous voting by committees (i.e., voting by quotas) with a complete upper semilattice structure, whose supremum is the equivalence class containing all voting by quotas with the property that the quota of each object is strictly larger than one and strictly lower than the number of agents. Finally, we extend the comparability criterion to the full class of all voting by committees.

We axiomatically study voting rules without making any assumption on the ballots that voters are allowed to cast. In this setting, we characterize the family of “endorsement rules,” which includes approval voting and the plurality rule, via the imposition of three normative conditions. The first condition is the well known social‐theoretic principle of consistency; the second one, unbiasedness, roughly requires social outcomes not to be biased toward particular candidates or voters; the last one, dubbed no single voter overrides, demands that the addition of a voter to an electorate cannot radically change the social outcome. Building on this result, we provide the first axiomatic characterization of approval voting without the approval balloting assumption. The informational basis of approval voting as well as its aggregative rationale are jointly derived from a set of conditions that can be defined on most of the ballot spaces studied in the literature.

Online tools like Doodle polls are frequently used for meeting coordination and other decentralized cooperative decision-making. Since Doodle polls are a form of approval voting, theoretical results from voting theory often underpin work in this area. Sincerity, where a voter never says yes to a less-preferred option without saying yes to all more preferable choices, is a common assumption in approval voting. However, that does not take into account cooperative behavior sometimes exhibited by users when others’ responses are known. We conduct a user study investigating the extent to which college-student participants in Doodle-style polls were sincere, reporting on responses from one institution.

International audience; This paper presents data from a survey leading up to the 2016 US presidential elections. Participants were asked their opinions about the candidates and were also asked to vote according to three alternative voting rules, in addition to plurality: approval voting, range voting, and instant runoff voting. The participants were split into two groups, one facing a set of four candidates (Clinton, Trump, Johnson, and Stein) and the other a set of nine candidates (the previous four plus Sanders, Cruz, McMullin, Bloomberg, and Castle). The paper studies three issues: (1) How do US voters use these alternative rules? (2) What kinds of candidates, in terms of individual preferences, are favored by which rule? (3) Which rules empirically satisfy the independence of eliminated alternatives? Our results provide evidence that, according to all standard criteria computed on individual preferences, be there utilitarian or of the Condorcet type, the same candidate (Sanders) wins. Evaluative voting rules such as approval voting and range voting might lead to this outcome, contrary to direct plurality and instant runoff voting (that elects Clinton) and to the official voting rule (that elected Trump).

This paper introduces excluding outlier voters (EOV) as a general mechanism for revealing true preferences in social choices, and for discouraging voters from strategic voting and manipula-tion. This mechanism is general in that it can be implemented with any voting system. The paper demonstrates its use with Borda count, range voting, modified range/Borda voting, approval voting, and positional voting, although it can also be used with other voting systems discussed in the literature and used in practice. The mechanism helps reveal true group preferences, even when the intention to employ it is not disclosed to the voters beforehand. More importantly, however, once the mechanism is known to the voters, it strongly discourages them from not reporting their true preferences. This disincentive is rooted in certain nonmonotonicity violations that the mechanism introduces to the voting system: a voter’s favorite candidate may lose his/her winning position as a result of being dishonestly overrated or his/her main rival being dishon-estly underrated. From this point of view, these monotonicity violations are “positive”, as they create a “punishment” mechanism for manipulating voters. On the other hand, the mechanism encourages outlier voters to dishonestly report preferences so that they become closer to the group average. As shown below, implementing EOV results in a unique Nash equilibrium in which the best interests of all nonoutlier voters is to “vote honestly”.

One of the common objections to the social choice methods based on linear rankings of the candidates, is that they require too much involvement of the voters. Each voter is required to provide full linear ranking of all candidates, which can be demanding process when there is larger number of candidates. Therefore, there is a demand for providing social choice methods that are based on some partial expression of voters preference. In this work we are preseting one such method, a generalisation of Approved voting, which also satisfy Compromise Axiom.

In the high-stakes race to develop more scalable blockchains, some platforms (Cosmos, EOS, TRON, etc.) have adopted committee-based consensus protocols, whereby the blockchain's record-keeping rights are entrusted to a committee of elected block producers. In theory, the smaller the committee, the faster the blockchain can reach consensus and the more it can scale. What's less clear, is whether this mechanism ensures that honest committees can be consistently elected, given voters typically have limited information. Using EOS' Delegated Proof of Stake (DPoS) protocol as a backdrop, we show that identifying the optimal voting strategy is complex and practically out of reach. We empirically characterize some simpler (suboptimal) voting strategies that token holders resort to in practice and show that these nonetheless converge to optimality, exponentially quickly. This yields efficiency gains over other PoS protocols that rely on randomized block producer selection. Our results suggest that (elected) committee-based consensus, as implemented in DPoS, can be robust and efficient, despite its complexity.

We fully describe the set of equilibrium winners in a model of strategic Approval voting. To this end, we introduce the concept of viable candidate: a candidate is viable if the number of voters who do not rank him last is larger than the number of voters who rank first any other candidate. If at most two candidates are viable, we prove that the unique equilibrium winner is the Condorcet Winner. For any election with more viable candidates, we show that for some utility profiles we can build an equilibrium in which all the viable candidates are tied for victory.

Agents vote to choose a fair mixture of public outcomes; each agent likes or dislikes each outcome. We discuss three outstanding voting rules. The Conditional Utilitarian rule, a variant of the random dictator, is Strategyproof and guarantees to any group of like-minded agents an influence proportional to its size. It is easier to compute and more efficient than the familiar Random Priority rule. Its worst case (resp. average) inefficiency is provably (resp. in numerical experiments) low if the number of agents is low. The efficient Egalitarian rule protects similarly individual agents but not coalitions. It is Excludable Strategyproof: I do not want to lie if I cannot consume outcomes I claim to dislike. The efficient Nash Max Product rule offers the strongest welfare guarantees to coalitions, who can force any outcome with a probability proportional to their size. But it fails even the excludable form of Strategyproofness., Comment: 37 pages

This paper proposes an alternative reading of the politics of the 2017 French presidential election, using an unstudied source of information on voters' preferences: experimental data on approval voting. We provide a new narrative of the election process and outcome. The principal approach for understanding the political context has for many decades been a distinction between left and right-wing political forces. We introduce a method for generating an endogenous political axis, and construct three indices so that we might understand how and why the conventional approach has become progressively irrelevant. We find no gender effect, but instead an age effect. Voters, especially those who belong to generations at the beginning or the end of their working life, use their vote in national elections to support radical change; and the younger the voters, the less they conform to a left-right axis. However, this desire for change does not represent a rejection of existing parties, as the official results would suggest. Rather, the approval results suggest an erosion in the voters' minds of barriers between distinct political camps, and between traditional and populist parties.

SSRN: 10.2139/ssrn.3683849; International audience; Many voters seem to appreciate the greater freedom of expression afforded by alternative voting rules; in evaluative voting, for example, longer grading scales and/or negative grades seem desirable in so far as, all other things being equal, they allow greater expressivity. The paper studies to what extent the behavior of voters, and the outcomes of elections, are sensitive to the grading scale employed in evaluative (or "range") voting. To this end, we use voting data from an experiment conducted in parallel with the 2017 French presidential election, which aimed to scrutinize the negative grade effect and the length effect in grading scales. First, this paper confirms that the introduction of a negative grade disfavors "polarizing" candidates, those whose political discourse provokes divisive debate, but more generally we establish that it disfavors major candidates and favors minor candidates. Second, under non-negative scales, polarizing candidates may be relatively disfavored by longer scales, especially compared with candidates who attract only infrequent media coverage and who are little known among voters. Third, longer scales assign different weights to the votes of otherwise equal voters, depending on their propensity to vote strategically. Overall, we observe that the benefits of the expressivity provided by longer scales or negative grades need to be balanced against the controversial advantage these give to minor candidates, and their tendency to undermine the principle that each vote should count equally in the outcome of the election.

By the Gibbard–Satterthwaite theorem, every reasonable voting rule for three or more alternatives is susceptible to manipulation: there exist elections where one or more voters can change the election outcome in their favour by unilaterally modifying their vote. When a given election admits several such voters, strategic voting becomes a game among potential manipulators: a manipulative vote that leads to a better outcome when other voters are truthful may lead to disastrous results when other voters choose to manipulate as well. We consider this situation from the perspective of a boundedly rational voter, using an appropriately adapted cognitive hierarchy framework to model voters’ limitations. We investigate the complexity of algorithmic questions that such a voter faces when deciding on whether to manipulate. We focus on k -approval voting rules, with k ≥ 1 . We provide polynomial-time algorithms for k = 1 , 2 and hardness results for k ≥ 4 (NP and co-NP), supporting the claim that strategic voting, albeit ubiquitous in collective decision making, is computationally hard if the manipulators try to reason about each other’s actions.

In approval-based multiwinner elections, we are given a set of voters, a set of candidates, and, for each voter, a set of candidates approved by the voter. The goal is to find a committee of size k that maximizes the total utility of the voters. In this paper, we study approximability of Thiele rules, which are known to be NP-hard to solve exactly. We provide a tight polynomial time approximation algorithm for a natural class of geometrically dominant weights that includes such voting rules as Proportional Approval Voting or p-Geometric. The algorithm is relatively simple: first we solve a linear program and then we round a solution by employing a framework called pipage rounding due to Ageev and Sviridenko (2004) and Calinescu et al. (2011). We provide a matching lower bound via a reduction from the Label Cover problem. Moreover, assuming a conjecture called Gap-ETH, we show that better approximation ratio cannot be obtained even in time f(k)*pow(n,o(k)).

The two main criticisms by approval voting (AV) supporters have been that majority judgment (MJ) is not “Condorcet” and that it admits the no-show paradox. That MJ is not Condorcet consistent is a good property shared with AV: the domination paradox shows that majority rule may well err in an election between two. Whereas the no-show paradox is in theory possible with MJ, it is as a practical matter impossible. Moreover, it is proven that MJ with three grades does not admit the no-show paradox. In contrast, AV suffers from serious drawbacks. With AV, voters cannot express their opinions adequately; experiments show that Approve is not the opposite of Disapprove and that AV does not admit the no-show paradox—it admits the very closely allied no-show syndrome. Two grades are simply too few! The debate must concern three or more grades.

v2: added a numerical study of rarity of bad cycles and equilibriums, and a case of chaotic Continuous Polling Dynamics. Many other improvements throughout the text.; We consider synchronized iterative voting in the Approval Voting system. We give examples with a Condorcet winner where voters apply simple, sincere, consistent strategies but where cycles appear that can prevent the election of the Condorcet winner, or that can even lead to the election of a "consensual loser", rejected in all circumstances by a majority of voters. We conduct numerical experiments to determine how rare such cycles are. It turns out that when voters apply Laslier's Leader Rule they are quite uncommon, and we prove that they cannot happen when voters' preferences are modeled by a one-dimensional culture. However a slight variation of the Leader Rule accounting for possible draws in voter's preferences witnesses much more bad cycle, especially in a one-dimensional culture.Then we introduce a continuous-space model in which we show that these cycles are stable under perturbation. Last, we consider models of voters behavior featuring a competition between strategic behavior and reluctance to vote for candidates that are ranked low in their preferences. We show that in some cases, this leads to chaotic behavior, with fractal attractors and positive entropy.

Risk-limiting audits (RLAs) for many social choice functions can be reduced to testing sets of null hypotheses of the form “the average of this list is not greater than 1/2” for a collection of finite lists of nonnegative numbers. Such social choice functions include majority, super-majority, plurality, multi-winner plurality, Instant Runoff Voting (IRV), Borda count, approval voting, and STAR-Voting, among others. The audit stops without a full hand count iff all the null hypotheses are rejected. The nulls can be tested in many ways. Ballot polling is particularly simple; two new ballot-polling risk-measuring functions for sampling without replacement are given. Ballot-level comparison audits transform each null into an equivalent assertion that the mean of re-scaled tabulation errors is not greater than 1/2. In turn, that null can then be tested using the same statistical methods used for ballot polling—applied to different finite lists of nonnegative numbers. The SHANGRLA approach thus reduces auditing different social choice functions and different audit methods to the same simple statistical problem. Moreover, SHANGRLA comparison audits are more efficient than previous comparison audits for two reasons: (i) for most social choice functions, the conditions tested are both necessary and sufficient for the reported outcome to be correct, while previous methods tested conditions that were sufficient but not necessary, and (ii) the tests avoid a conservative approximation. The SHANGRLA abstraction simplifies stratified audits, including audits that combine ballot polling with ballot-level comparisons, producing sharper audits than the “SUITE” approach. SHANGRLA works with the “phantoms to evil zombies” strategy to treat missing ballot cards and missing or redacted cast vote records. That also facilitates sampling from “ballot-style manifests,” which can dramatically improve efficiency when the audited contests do not appear on every ballot card. Open-source software implementing SHANGRLA ballot-level comparison audits is available. SHANGRLA was tested in a process pilot audit of an instant-runoff contest in San Francisco, CA, in November, 2019.

Pivato and Soh [Pivato, M., Soh, A., 2020. Weighted representative democracy. Journal of Mathematical Economics 88 (2020) 52--63] proposed a new system of democratic representation whereby any individual can choose any legislator as her representative and different legislators can represent different numbers of individuals, concomitantly determining their weights in the legislature. For such legislatures, we consider other voting rules, namely, the weighted approval voting rule' and weighted majority judgement rule. We show that if the size of the electorate is very large, then with very high probability, the decisions made by the legislature will be the same as the decisions that would have been reached by a direct democracy, as decided by the corresponding simple (unweighted) voting rules.

In this paper we address the problem of electing a committee among a set of m candidates on the basis of the preferences of a set of n voters. We consider the approval voting method in which each voter can approve as many candidates as he likes by expressing a preference profile (boolean m-vector). In order to elect a committee, a voting rule must be established to ‘transform’ the n voters’ profiles into a winning committee. The problem is widely studied in voting theory; for a variety of voting rules the problem was shown to be computationally difficult and approximation algorithms and heuristic techniques were proposed in the literature. In this paper we follow an Ordered Weighted Averaging approach and study the k-sum approval voting (optimization) problem in the general case 1 ≤ k

Referendums commonly offer a binary choice between supporting and rejecting proposed legislation. Binary designs benefit from simplicity and guarantee a majority result, but also provoke voting biases and interpretation challenges. Referendum designs offering multiple policy alternatives provide a different approach which could alleviate binary referendum challenges whilst maintaining the aggregative benefits. Offering more than two options, however, raises new challenges in designing the referendum process and obtaining majority results. This article uses survey data collected on a corrective referendum held in the Netherlands in 2018 to compare the challenges faced by binary and multi-option referendum designs respectively. The analysis demonstrates how the multi-option design empowers voters in expressing their preferences and delivers more detailed and constructive referendum results. Building on the survey data, the article subsequently discusses the challenges of extending choice and concludes that alternative voting methods can mitigate some of these challenges.