Asymptotic probability of majority inversion under a general binomial voting model

We obtain limits on the probability of majority inversion when the number of voters tends to infinity, for a binomial voting model specific to each state with different population sizes, and for different voting quotas in the two stages of the voting procedure. The case of weighted votes at the second stage is also discussed. For an important special case where the limit cannot be determined, we provide an exact expression for the inversion probability, but only for unweighted votes.     

Accusation probabilities in Tardos codes: beyond the Gaussian approximation

We study the probability distribution of user accusations in the q-ary Tardos fingerprinting system under the Marking Assumption, in the restricted digit model. In particular, we look at the applicability of the so-called Gaussian approximation, which states that accusation probabilities tend to the normal distribution when the fingerprinting code is long. We introduce a novel parametrization of the attack strategy which enables a significant speedup of numerical evaluations. We set up a method, based on power series expansions, to systematically compute the probability of accusing innocent users. The ‘small parameter’ in the power series is 1/m, where m is the code length. We use our method to semi-analytically study the performance of the Tardos code against majority voting and interleaving attacks. The bias function ‘shape’ parameter k{{\kappa}} strongly influences the distance between the actual probabilities and the asymptotic Gaussian curve. The impact on the collusion-resilience of the code is shown. For some realistic parameter values, the false accusation probability is even lower than the Gaussian approximation predicts.     

整数计分投票方法下全排序概率问题研究

讨论了在与Borda投票规则相似的整数计分投票方法中,投票结果使备选方案集产生全排序(任意两个备选方案的总分值不同)的概率P的问题.给出了在一定假设条件下计算P值的相关公式;通过分析运行计算机程序得到的数据,讨论了P值关于整数计分投票问题的三个变量的单调性性质;最后根据P值函数的单调性性质,指出应如何设计和调整整数计分投票规则.     

Voting power in a system of compound majority rule

In 1973, the United States Supreme Court ruled that a water district's voting scheme that apportioned votes on the basis of the assessed valuation of acreage in the district was constitutional. Among the justifications for the constitutionality of this scheme was the concurrent requirement that legislation be approved by a majority of voters as well as by a majority of weighted votes. However, analysis of this voting scheme in game-theoretic terms indicates that this justification is only partial: when two sets of winning coalitions must form simultaneously in order to pass legislation, the voting power of each voter in the combined system equals the mean of the voting power afforded each voter in each simple system. The results can be generalized to three or more concurrent requirements.     

Likelihood of voting outcomes with generalized IAC probabilities

After determining all supporting profiles with any number of voters for any specified three-candidate pairwise majority vote outcome, a new, large class of “octahedral” probability distributions, motivated by and including IAC, is introduced to examine various three-candidate voting outcomes involving majority vote outcomes. Illustrating examples include computing each distribution’s likelihood of a majority vote cycle and the likelihood that the Borda Count and Condorcet winners agree. Surprisingly, computations often reduce to a simple exercise of finding the volumes of tetrahedrons.     

Necessary and sufficient conditions for the existence of a nonempty core of a majority game

In this note we consider the core of a game with side payments representing simple majority voting. We provide necessary and sufficient conditions for the game to have a nonempty core.     

Condorcet winner configurations of linear networks

We consider the problem of locating a fixed number of facilities along a line to serve n players. We model this problem as a cooperative game and assume that any locational configuration can be eventually disrupted through a strict majority of players voting for an alternative configuration. A solution of such a voting location problem is called a Condorcet winner configuration. In this article, we state three necessary and one sufficient condition for a configuration to be a Condorcet winner. Consequently, we propose a fast algorithm which enables us to verify whether a given configuration is a Condorcet winner, and can be efficiently used also for computing the (potentially empty) set of all Condorcet winner configurations.     

Simple majority voting isn't special

Simple majority voting is compared with several other representative voting systems with respect to the frequency with which various anomalies occur. Whether strong or weak preferences are used, for each anomaly type simple majority voting yields neither highest nor lowest frequencies.     

Incoherent majorities: The McGarvey problem in judgement aggregation

Judgement aggregation is a model of social choice where the space of social alternatives is the set of consistent truth-valuations (‘judgements’) on a family of logically interconnected propositions. It is well known that propositionwise majority voting can yield logically inconsistent judgements. We show that, for a variety of spaces, propositionwise majority voting can yield any possible judgement. By considering the geometry of sub-polytopes of the Hamming cube, we also estimate the number of voters required to achieve all possible judgements. These results generalize the classic results of McGarvey (1953) [13] and Stearns (1959) [22].     

Voting Power in the Governance of the International Monetary Fund

In general in an organisation whose system of governance involves weighted voting, a member's weight in terms of the number of votes and the formal power it represents differ. Power indices provide a means of analysing this difference. The paper uses new algorithms for computing power indices for large games. Three analyses are carried out: (1) the distribution of Banzhaf voting power among members in 1999; the results show that the United States has considerably more power over ordinary decisions than its weight of 17% but that the use of special supermajorities limits its power; (2) the effect of varying the majority requirement on the power of the IMF to act and the powers of members to prevent and initiate action (Coleman indices); the results show the effect of supermajorities severely limits the power to act and therefore renders the voting system ineffective in democratic terms, also the sovereignty of the United States within the IMF is effectively limited to just the power of veto; (3) the paper proposes the determination of the weights instrumentally by means of an iterative algorithm to give the required power distribution; this would be a useful procedure for determining appropriate changes in weights consequent on changes to individual countries' quotas; this is applied to the 1999 data. Policy recommendations are, first, that the IMF use only simple majority voting, and discontinue using special supermajorities, and, second, allocate voting weight instrumentally using power indices.     

Choice from a Three-Element Set: Some Lessons of the 2000 Presidential Campaign in the United States

We consider the behavior of four choice rules—plurality voting, approval voting, Borda count, and self-consistent choice—when applied to choose the best option from a three-element set. It is assumed that the two main options are preferred by a large majority of the voters, while the third option gets a very small number of votes and influences the election outcome only when the two main options receive a close number of votes. When used to rate the main options, Borda count and self-consistent choice contain terms that allow both for the strength of preferences of the voters and the rating of the main candidates by voters who vote for the third option. In this way, it becomes possible to determine more reliably the winner when plurality voting or approval voting produce close results.     

Optimal bounds for the no-show paradox via SAT solving

One of the most important desirable properties in social choice theory is Condorcet-consistency, which requires that a voting rule should return an alternative that is preferred to any other alternative by some majority of voters. Another desirable property is participation, which requires that no voter should be worse off by joining an electorate. A seminal result by Moulin (1988) has shown that Condorcet-consistency and participation are incompatible whenever there are at least 4 alternatives and 25 voters. We leverage SAT solving to obtain an elegant human-readable proof of Moulin’s result that requires only 12 voters. Moreover, the SAT solver is able to construct a Condorcet-consistent voting rule that satisfies participation as well as a number of other desirable properties for up to 11 voters, proving the optimality of the above bound. We also obtain tight results for set-valued and probabilistic voting rules, which complement and significantly improve existing theorems.     

Condorcet Winners for Public Goods

In this work, we consider a public facility allocation problem decided through a voting process under the majority rule. A location of the public facility is a majority rule winner if there is no other location in the network where more than half of the voters would have been closer to than the majority rule winner. We develop fast algorithms for interesting cases with nice combinatorial structures. We show that the computing problem and the decision problem in the general case, where the number of public facilities is more than one and is considered part of the input size, are all NP-hard. Finally, we discuss majority rule decision making for related models.     

On the Probability of Correct Selection by Distributed Voting in Stochastic Optimization

This note presents a lower bound on the probability of correct selection for a weighted plurality voting with a single sample performance in approximately solving stochastic optimization problems. It is shown that the lower bound increases exponentially with the number of distributed sampling agents under some condition.     

Voting power in the European Union enlargement

The Shapley–Shubik power index in a voting situation depends on the number of orderings in which each player is pivotal. The Banzhaf power index depends on the number of ways in which each voter can effect a swing. If there are n players in a voting situation, then the function which measures the worst case running time for computing these indices is in O(n2ⁿ). We present a combinatorial method based in generating functions to compute these power indices efficiently in weighted double or triple majority games and we study the time complexity of the algorithms. Moreover, we calculate these power indices for the countries in the Council of Ministers of the European Union under the new decision rules prescribed by the Treaty of Nice.     

Optimal location of candidates in ideological space

The strong point is the point which minimizes the probability that a candidate be defeated in a two-party election. The center of power is the weighted average of voters' positions in a spatial voting game, where the weights are given by Shapley's modified value. We show that, under very general conditions, the strong point and the center of power coincide.     

The Size of a Political Club

We investigate the size of a political club that admits new members according to a rule that if only a few members vote against admission the candidate joins, but the members who voted against admission leave. For the simplest ergodic case, we use a modified Bessel function to give the generating function for the invariant distribution of the club size. This also allows us to give asymptotics for the moments as the probability of voting for admission approaches 1 and to prove global and local central limit theorems. We also calculate the mean recurrent time and determine formulas for calculating first passage times. We then show that for an expanded set of cases the club size process approaches the Ornstein-Uhlenbeck process as the probability of voting for admission approaches 1. This means that the club size will approach a Gaussian distribution for a wide set of formal and informal admission rules. Finally, we show a comparison between theoretical results and simulation runs for two cases.     

Computable error bounds of multidimensional Euler inversion and their financial applications

Transform inversion is an efficient approximation procedure in operations research, yet the inversion results are sometimes unstable which calls for comprehensive error analysis. This article proposes a multidimensional Euler inversion (MEI) algorithm with computable error bounds. We design mild sufficient conditions that validate the inversion formula, and provide closed-form upper bounds of the inversion errors. Numerical experiments are conducted to compute the joint probability of default and barrier option prices under complicated stochastic models, and output the associated error bounds.     

基于模拟退火地震反演技术——以X油田某区为例

为了提高地震反演预测的分辨率和可信度,提出了线性反演与非线性反演二者相结合的反演方法——以稀疏脉冲反演结果为约束背景的基于模拟退火的反演方法,阐述了基于模拟退火法的反演机理,并以X油田某区为例,开展了基于模拟退火地球物理反演预测,从反演分辨率、可信度和误差三个方面进行分析和定量研究.结果表明,非线性的随机反演与线性反演相结合有效地提高了反演分辨率,纵向上能够精细到单砂体级,反演结果多个概率的实现最大程度上降低反演的多解性,并且,反演结果的精度较高,2m以上砂岩反演符合率均在90%以上.     

Evaluating correct classification probability for weighted voting classifiers with plurality voting

Weighted voting classifiers (WVCs) consist of N units that each provide individual classification decisions. The entire system output is based on tallying the weighted votes for each decision and choosing the winning one (plurality voting) or one which has the total weight of supporting votes greater than some specified threshold (threshold voting). Each individual unit may abstain from voting. The entire system may also abstain from voting if no decision is ultimately winning. Existing methods of evaluating the correct classification probability (CCP) of WVCs can be applied to limited special cases of these systems (threshold voting) and impose some restrictions on their parameters. In this paper a method is suggested which allows the CCP of WVCs with both plurality and threshold voting to be exactly evaluated without imposing constraints on unit weights. The method is based on using the modified universal generating function technique.