Minimal winning coalitions in weighted-majority voting games

Riker's size principle for n-person zero-sum games predicts that winning coalitions that form will be minimal in that any player's defection will negate the coalition's winning status. Brams and Fishburn (1995) applied Riker's principle to weighted-majority voting games in which players have voting weights w ₁≥w ₂≥...≥w _n,and a coalition is winning if its members' weights sum to more than half the total weight. We showed that players' bargaining power tends to decrease as their weights decrease when minimal winning coalitions obtain, but that the opposite trend occurs when the minimal winning coalitions that form are “weight-minimal”, referred to as least winning coalitions. In such coalitions, large size may be more harmful than helpful. The present paper extends and refines our earlier analysis by providing mathematical foundations for minimal and least winning coalitions, developing new data to examine relationships between voting weight and voting power, and applying more sophisticated measures of power to these data. We identify all sets of minimal and least winning coalitions that arise from different voting weights for n≤6 and characterize all coalitions that are minimal winning and least winning for every n. While our new analysis supports our earlier findings, it also indicates there to be less negative correlation between voting weight and voting power when least winning coalitions form. In this context, players' powers are fairly insensitive to their voting weights, so being large or small is not particularly important for inclusion in a least winning coalition.     

A computational analysis of the tournament equilibrium set

A recurring theme in the mathematical social sciences is how to select the “most desirable” elements given a binary dominance relation on a set of alternatives. Schwartz’s tournament equilibrium set (TEQ) ranks among the most intriguing, but also among the most enigmatic, tournament solutions proposed so far. Due to its unwieldy recursive definition, little is known about TEQ. In particular, its monotonicity remains an open problem to date. Yet, if TEQ were to satisfy monotonicity, it would be a very attractive solution concept refining both the Banks set and Dutta’s minimal covering set. We show that the problem of deciding whether a given alternative is contained in TEQ is NP-hard, and thus does not admit a polynomial-time algorithm unless P equals NP. Furthermore, we propose a heuristic that significantly outperforms the naive algorithm for computing TEQ.     

The Banks Set in Infinite Spaces

I provide a definition of the Banks set, or set of sophisticated voting outcomes, over an infinite policy space and when individual preferences are weak. I also show that the Banks set is a subset of one definition of the uncovered set, but not another. The interpretation of the Banks set in this setting differs from Banks’s original interpretation in the implicit role of the agenda setter. In addition, a characterization of the Banks set is provided for a three-player game of distributive politics. In this special setting, the Banks set and all definitions of the uncovered set have full measure over the space of alternatives.     

Criticality in games with multiple levels of approval

In this article, criticality within a voting game is rigorously defined and examined. Criticality forms the basis of the traditional voting power measures frequently employed to analyse voting games; therefore understanding criticality is a pre-requisite to understanding any such analysis. The concept of criticality is extended to encompass games in which players are allowed to express multiple levels of approval. This seemingly innocuous extension raises some important questions, forcing us to re-evaluate exactly what it means to be critical. These issues have been largely side-stepped by the main body of research as they focus almost exclusively on ‘yes/no’ voting games, the so called single level approval voting games. The generalisation to multilevel approval voting games is much more than just a theoretical extension, as any single level approval game in which a player can abstain is in effect a multilevel approval voting game.     

Does uncertainty lead to sincerity? Simple and complex voting mechanisms

We ask whether the absence of information about other voters’ preferences allows optimal voting to be interpreted as sincere.We start by classifying voting mechanisms as simple and complex according to the number of message types voters can use to elect alternatives. We show that while in simple voting mechanisms the elimination of information about other voters’ preferences allows optimal voting to be interpreted as sincere, this is no longer always true for complex ones. In complex voting mechanisms, voters’ optimal strategy may vary with the size of the electorate. Therefore, in order to interpret optimal voting as sincere for complex voting mechanisms, we describe the optimal voting strategy when voters not only have no information but also have no pivotal power, i.e., as the size of the electorate tends to infinity.     

The inverse Banzhaf problem

Let ${\mathcal{F}}Let F{\mathcal{F}} be a family of subsets of the ground set [n] = {1, 2, . . . , n}. For each i ? [n]{i \in [n]} we let p(F,i){p(\mathcal{F},i)} be the number of pairs of subsets that differ in the element i and exactly one of them is in F{\mathcal{F}}. We interpret p(F,i){p(\mathcal{F},i)} as the influence of that element. The normalized Banzhaf vector of F{\mathcal{F}}, denoted B(F){B(\mathcal{F})}, is the vector (B(F,1),...,B(F,n)){(B(\mathcal{F},1),\dots,B(\mathcal{F},n))}, where B(F,i)=\fracp(F,i)p(F){B(\mathcal{F},i)=\frac{p(\mathcal{F},i)}{p(\mathcal{F})}} and p(F){p(\mathcal{F})} is the sum of all p(F,i){p(\mathcal{F},i)}. The Banzhaf vector has been studied in the context of measuring voting power in voting games as well as in Boolean circuit theory. In this paper we investigate which non-negative vectors of sum 1 can be closely approximated by Banzhaf vectors of simple voting games. In particular, we show that if a vector has most of its weight concentrated in k < n coordinates, then it must be essentially the Banzhaf vector of some simple voting game with n − k dummy voters.     

On the equilibrium of voting games with abstention and several levels of approval

We study the core of “(j, k) simple games”, where voters choose one level of approval from among j possible levels, partitioning the society into j coalitions, and each possible partition facing k levels of approval in the output (Freixas and Zwicker in Soc Choice Welf 21:399–431, 2003). We consider the case of (j, 2) simple games, including voting games in which each voter may cast a “yes” or “no” vote, or abstain (j = 3). A necessary and sufficient condition for the non-emptiness of the core of such games is provided, with an important application to weighted symmetric (j, 2) simple games. These results generalize the literature, and provide a characterization of constitutions under which a society would allow a given number of candidates to compete for leadership without running the risk of political instability. We apply these results to well-known voting systems and social choice institutions including the relative majority rule, the two-thirds relative majority rule, the United States Senate, and the United Nations Security Council.     

Characterizations of two power indices for voting games with r alternatives

In the first three sections of this paper we present a set of axioms which provide a characterization of an extension of the Banzhaf index to voting games with r alternatives, such as the United Nations Security Council where a nation can vote “yes”, “no”, or “abstain”. The fourth section presents a set of axioms which characterizes a power index based on winning sets instead of pivot sets. Received: 4 April 2000/Accepted: 30 April 2001     

The original Borda count and partial voting

In a Borda count, bc, M. de Borda suggested the last preference cast should receive 1 point, the voter’s penultimate ranking should get 2 points, and so on. Today, however, points are often awarded to (first, second,..., last) preferences cast as per (n, n?1, ..., 1) or more frequently, (n ?1, n?2,..., 0). If partial voting is allowed, and if a first preference is to be given n or n ? 1 points regardless of how many preferences the voter casts, he/she will be incentivised to rank only one option/candidate. If everyone acts in this way, the bc metamorphoses into a plurality vote... which de Borda criticized at length. If all the voters submit full ballots, the outcome—social choice or ranking—will be the same under any of the above three counting procedures. In the event of one or more persons submitting a partial vote, however, outcomes may vary considerably. This preliminary paper suggests research should consider partial voting. The author examines the consequences of the various rules so far advocated and then purports that M. de Borda, in using his formula, was perhaps more astute than the science has hitherto recognised.     

Sophisticated voting and equilibrium refinements under plurality rule

In this paper we show in the context of voting games with plurality rule that the “perfect” equilibrium concept does not appear restrictive enough, since, independently of preferences, it can exclude at most the election of only one candidate. Furthermore, some examples show that there are “perfect” equilibria that are not “proper”. However, also some “proper” outcome is eliminated by sophisticated voting, while Mertens' stable set fully satisfies such criterium, for generic plurality games. Moreover, we highlight a weakness of the simple sophisticated voting principle. Finally, we find that, for some games, sophisticated voting (and strategic stability) does not elect the Condorcet winner, neither it respects Duverger's law, even with a large number of voters. Received: 16 March 1999/Accepted: 25 September 1999     

Equilibrium in abstract political economies: with an application to a public good economy with voting

Consider an abstract political economy which has a collective choice rule together with strategic interactions among players. We prove that there exists an equilibrium in such an economy by synthesizing an equilibrium existence theorem in generalized games by Shafer and Sonnenschein (1975) and a voting core existence theorem in simple games by Schofield (1984, 1989). The theorem can be applied to a public good economy where public good provisions are determined by a class of voting rule.Thanks are due to David Austen-Smith, Jeffrey Banks, Marcus Berliant, Steve Ching, Ryo-Ichi Nagahisa, Mary Beth Savio, Norman Schofield, and Tomoichi Shinotsuka. Detailed comments from an anonymous referee of the journal are gratefully acknowledged. Errors are, of course, my own.     

Behavioral evidence for framing effects in the resolution of the doctrinal paradox

The aggregation of individual sets of judgments over interconnected propositions can yield inconsistent collective sets of judgments, even when the individual sets of judgments are themselves consistent. A doctrinal paradox occurs when majority voting on a compound proposition (such as a conjunction or disjunction) yields a different result than majority voting on each of the elements of the proposition. For example, when most individuals accept proposition X; most individuals accept proposition Y ; but only a minority of individuals accept the compound proposition ‘X and Y’. Conducting two elemental votes would lead to accept X and Y , but conducting one compound vote would lead to reject X and Y . In such a situation, do people manifest a stable preference as to which voting procedure should be applied? This research reports the results of two behavioral experiments using a within-participant design, which show that procedural preferences can be upturned by framing either positively or negatively the set of judgments to be aggregated. This shift in procedural preference leads to large swings in the final collective judgment endorsed by participants.     

How the size of a coalition affects its chances to influence an election

Since voting rules are prototypes for many aggregation procedures, they also illuminate problems faced by economics and decision sciences. In this paper we are trying to answer the question: How large should a coalition be to have a chance to influence an election? We answer this question for all scoring rules and multistage elimination rules, under the Impartial Anonymous Culture assumption. We show that, when the number of participating agents n tends to infinity, the ratio of voting situations that can be influenced by a coalition of k voters to all voting situations is no greater than $D_{m} \frac{k}{n}Since voting rules are prototypes for many aggregation procedures, they also illuminate problems faced by economics and decision sciences. In this paper we are trying to answer the question: How large should a coalition be to have a chance to influence an election? We answer this question for all scoring rules and multistage elimination rules, under the Impartial Anonymous Culture assumption. We show that, when the number of participating agents n tends to infinity, the ratio of voting situations that can be influenced by a coalition of k voters to all voting situations is no greater than , where D _m is a constant which depends only on the number m of alternatives but not on k and n. Recent results on individual manipulability in three alternative elections show that this estimate is exact for k=1 and m=3.

Arkadii SlinkoEmail:

     

Gambling Prevention Program Among Children

Gambling becomes a more frequent activity among children as they have an easy access to the world of the games. In the same time children are at a higher risk for developing problem and/or pathological gambling having erroneous information about how games of chance and games of skill work. The purpose of the study was to compare the influence of specific primary prevention with rational emotive education (REE) on the subjects’ knowledge about games. The experimental design randomly assigned children (N = 81, age 12–13, 37 male and 44 female) into three groups: 1. control, 2. specific information about games using the interactive software “Amazing Chateau”, and 3. REE. All children completed a questionnaire with 38 items at the beginning of the study and after 10 weekly interventional meetings. Each item had three answering options, children choosing only one correct answer. Findings indicated that the use of the software significantly improved subjects’ knowledge about gambling and corrected their information about how games work. The results of the study confirmed that using specific primary prevention tools for changing erroneous conceptions about games is more efficient than using only REE. The implications of these results for the prevention of gambling problems especially in schools are discussed.     

A smallest tournament for which the Banks set and the Copeland set are disjoint

Given a tournament T, a Banks winner of T is the first vertex of any maximal (with respect to inclusion) transitive subtournament of T; a Copeland winner of T is a vertex with a maximum out-degree. In this paper, we show that 13 is the minimum number of vertices that a tournament must have so that none of its Copeland winners is a Banks winner: for any tournament with less than 13 vertices, there is always at least one vertex which is a Copeland winner and a Banks winner simultaneously. Received: 2 May 1997 / Accepted: 30 September 1997     

Choosing from a large tournament

A tournament can be viewed as a majority preference relation without ties on a set of alternatives. In this way, voting rules based on majority comparisons are equivalent to methods of choosing from a tournament. We consider the size of several of these tournament solutions in tournaments with a large but finite number of alternatives. Our main result is that with probability approaching one, the top cycle set, the uncovered set, and the Banks set are equal to the entire set of alternatives in a randomly chosen large tournament. That is to say, each of these tournament solutions almost never rules out any of the alternatives under consideration. We also discuss some implications and limitations of this result.     

Classification theorem for smooth social choice on a manifold

A classification theorem for voting rules on a smooth choice space W of dimension w is presented. It is shown that, for any non-collegial voting rule, σ, there exist integers v ^*(σ), w ^*(σ) (with v ^*(σ)<w ^*(σ)) such that

1. structurally stable σ-voting cycles may always be constructed when w ? v ^*(σ) + 1
2. a structurally stable σ-core (or voting equilibrium) may be constructed when w ? v ^*(σ) ? 1

Finally, it is shown that for an anonymous q-rule, a structurally stable core exists in dimension \(\frac{{n - 2}}{{n - q}}\) , where n is the cardinality of the society.     

Scoring rule voting games and dominance solvability

This article studies the dominance solvability (by iterated deletion of weakly dominated strategies) of general scoring rule voting games when there are three alternatives. The scoring rules we study include Plurality rule, Approval voting, Borda rule, and Relative Utilitarianism. We provide sufficient conditions for dominance solvability of general scoring rule voting games. The sufficient conditions that we provide for dominance solvability are in terms of one statistic of the game: sufficient agreement on the best alternative or on the worst alternative. We also show that the solutions coincide with the set of Condorcet Winners whenever the sufficient conditions for dominance solvability are satisfied. Approval Voting performs the best in terms of our criteria.     

Reconciling marginalism with egalitarianism: consistency, monotonicity, and implementation of egalitarian Shapley values

One of the main issues in economic allocation problems is the trade-off between marginalism and egalitarianism. In the context of cooperative games this trade-off can be framed as one of choosing to allocate according to the Shapley value or the equal division solution. In this paper we provide three different characterizations of egalitarian Shapley values being convex combinations of the Shapley value and the equal division solution. First, from the perspective of a variable player set, we show that all these solutions satisfy the same reduced game consistency. Second, on a fixed player set, we characterize this class of solutions using monotonicity properties. Finally, towards a strategic foundation, we provide a non-cooperative implementation for these solutions which only differ in the probability of breakdown at a certain stage of the game. These characterizations discover fundamental differences as well as intriguing connections between marginalism and egalitarianism.