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.     

On the family of linear extensions of a partial order

Given a partial order P defined on a finite set X, a binary relation ?_P may be defined on X by setting x ?_Py for elements x and y in X just when more linear extensions L of P on X have xLy than yLx. A linear extension L of P on X is a linear order on X with P ? L. There exist partial orders P such that ?_P includes cycles. Thus, in a voting situation in which voters are unanimous in their preferences on the pairs in P and express all possible linearly ordered preferences on X which are consistent with P, with no two voters having the same preference order, strict simple majorities as given by ?_P can cycle.     

Equilibrium and effectiveness of two-parameter scoring rules

We study a cardinal model of voting with three alternatives where voters’ von Neumann Morgenstern utilities are private information. We consider voting protocols given by two-parameter scoring rules, as introduced by Myerson (2002). For these voting rules, we show that all symmetric Bayes Nash equilibria are sincere, and have a very specific form. These equilibria are unique for a wide range of model parameters, and we can therefore compare the equilibrium performance of different rules. Computational results regarding the effectiveness of different scoring rules (where effectiveness is captured by a modification of the effectiveness measure proposed in Weber, 1978) suggest that those which most effectively represent voters’ preferences allow for the expression of preference intensity, in contrast to more commonly used rules such as the plurality rule, and the Borda Count. While approval voting allows for the expression of preference intensity, it does not maximize effectiveness as it fails to unambiguously convey voters’ ordinal preference rankings.     

On minimum sum representations for weighted voting games

A proposal in a weighted voting game is accepted if the sum of the (non-negative) weights of the ??yea?? voters is at least as large as a given quota. Several authors have considered representations of weighted voting games with minimum sum, where the weights and the quota are restricted to be integers. In Freixas and Molinero (Ann. Oper. Res. 166:243?C260, 2009) the authors have classified all weighted voting games without a unique minimum sum representation for up to 8 voters. Here we exhaustively classify all weighted voting games consisting of 9?voters which do not admit a unique minimum sum integer weight representation.     

Complexity of computing median linear orders and variants

Given a finite set X and a collection Π of linear orders defined on X, computing a median linear order (Condorcet-Kemenyʼs problem) consists in determining a linear order minimizing the remoteness from Π. This remoteness is based on the symmetric distance, and measures the number of disagreements between O and Π. In the context of voting theory, X can be considered as a set of candidates and the linear orders of Π as the preferences of voters, while a linear order minimizing the remoteness from Π can be adopted as the collective ranking of the candidates with respect to the votersʼ opinions. This paper studies the complexity of this problem and of several variants of it: computing a median order, computing a winner according to this method, checking that a given candidate is a winner and so on. We try to locate these problems inside the polynomial hierarchy.     

A note on hierarchies in weighted voting games and partitions

Weighted voting games (WVGs) model situations where voters, possibly controlling different numbers of votes, vote yes or no on a proposition. A proposition passes if and only if the number of yes votes meets or exceeds a quota \(q\). Each winning coalition is a partition of an integer greater than or equal to \(q\), with parts taken from the set of all weights for that game. Results about WVGs are here interpreted as results about partitions.     

How many miles to βX? II — Approximations to βX versus cofinal types of sets of metrics

Kada, Tomoyasu and Yoshinobu proved that the Stone-?ech compactification of a locally compact separable metrizable space is approximated by the collection of d-many Smirnov compactifications, where d is the dominating number. By refining the proof of this result, we will show that the collection of compatible metrics on a locally compact separable metrizable space has the same cofinal type, in the sense of Tukey relation, as the set of functions from ω to ω with respect to eventually dominating order.     

Voting cycles,plurality rule and strategic manipulation

In this note, we investigate the connection between the existence of cycles and the opportunities of strategic manipulation under a specific social decision function, the plurality rule. Contrary to previous research in this field, voting cycles are considered as a possible cause rather than a consequence of strategic voting. The results we obtain allow us to evaluate the vulnerability of the plurality rule to strategic voting, and to study how the distribution of voters over preference orderings affects the risk of manipulation.Partial support has been obtained from the Swedish Council for Research in the Humanities and Social Sciences.     

Transitive permutation groups and equipotent voting rules

Let F a two-alternative voting rule and G_F the subgroup of permutations of the voters under which F is invariant. Group theoretic properties of G_F provide information about the voting rule F. In particular, sets of imprimitivity of G_F describe the ‘committee decomposition’ structure of F and permutation group transitivity of G_F (equipotency) is shown to be closely connected with equal distribution of power among the voters. If equipotency replaces anonymity in the hypotheses of May's theorem, voting rules other than simple majority are possible. By combining equipotency with two additional social choice conditions a new characterization of simple majority rule is obtained. Equipotency is proposed as an important alternative to the more restrictive anonymity as a fairness criterion in social choice.     

Voting with preferences over margins of victory

This paper analyzes a two-alternative voting model with the distinctive feature that voters have preferences over margins of victory. We study voting contests with a finite as well as an infinite number of voters, and with and without mandatory voting. The main result of the paper is the existence and characterization of a unique equilibrium outcome in all those situations. At equilibrium, voters who prefer a larger support for one of the alternatives vote for such alternative, providing a formal argument for the conditional sincerity voting condition in [Alesina, Alberto, Rosenthal, Howard, 1995. Partisan Politics, Divided Government, and the Economy. Cambridge University Press, Cambridge] and the benefit of voting function in [Llavador, Humberto, 2006. Electoral platforms, implemented policies and abstention. Social Choice and Welfare 27 (1), 55–81]. Finally, we offer new insights on explaining why some citizens may vote strategically for an alternative different from the one declared as the most preferred.     

An experimental study of voting rules and polls in three-candidate elections

We report the results of elections conducted in a laboratory setting, modelled on a threecandidate example due to Borda. By paying subjects conditionally on election outcomes, we create electorates with (publicly) known preferences. We compare the results of experiments with and without non-binding pre-election polls under plurality rule, approval voting, and Borda rule. We also refer to a theory of voting “equilibria,” which makes sharp predictions concerning individual voter behavior and election outcomes. We find that Condorcet losers occasionally win regardless of the voting rule or presence of polls. Duverger's law (which asserts the predominance of two candidates) appears to hold under plurality rule, but close three-way races often arise under approval voting and Borda rule. Voters appear to poll and vote strategically. In elections, voters usually cast votes that are consistent with some strategic equilibrium. By the end of an election series, most votes are consistent with a single equilibrium, although that equilibrium varies by experimental group and voting rule.     

An Efficient Algorithm to Identify DNA Motifs

We consider the problem of identifying motifs that abstracts the task of finding short conserved sites in genomic DNA. The planted (l, d)-motif problem, PMP, is the mathematical abstraction of this problem, which consists of finding a substring of length l that occurs in each s _i in a set of input sequences S = {s ₁, s ₂, . . . ,s _t } with at most d substitutions. Our propose algorithm combines the voting algorithm and pattern matching algorithm to find exact motifs. The combined algorithm is achieved by running the voting algorithm on t′ sequences, t′ < t. After that we use the pattern matching on the output of the voting algorithm and the reminder sequences, t ? t′. Two values of t′ are calculated. The first value of t′ makes the running time of our proposed algorithm less than the running time of voting algorithm. The second value of t′ makes the running time of our proposed algorithm is minimal. We show that our proposed algorithm is faster than the voting algorithm by testing both algorithms on simulated data from (9, d ≤ 2) to (19, d ≤ 7). Finally, we test the performance of the combined algorithm on realistic biological data.     

A core of voting games with improved foresight

This paper considers voting situations in which the vote takes place iteratively. If a coalition replaces the status quo a with a contestant b, then b becomes the new status quo, and the vote goes on until a candidate is reached that no winning coalition is willing to replace. It is well known that the core, that is, the set of undominated alternatives, may be empty. To alleviate this problem, Rubinstein [Rubinstein, A., 1980. Stability of decision systems under majority rule. Journal of Economic Theory 23, 150–159] assumes that voters look forward one vote before deciding to replace an alternative by a new one. They will not do so if the new status quo is going to be replaced by a third that is less interesting than the first. The stability set, that is, the set of undominated alternatives under this behavior, is always non-empty when preferences are strict. However, this is not necessarily the case when voters’ indifference is allowed. Le Breton and Salles [Le Breton, M., Salles, M., 1990. The stability set of voting games: Classification and generecity results. International Journal of Game Theory 19, 111–127], Li [Li, S., 1993. Stability of voting games. Social Choice and Welfare 10, 51–56] and Martin [Martin, M., 1998. Quota games and stability set of order d. Economic Letters 59, 145–151] extend the sophistication of the voters by having them look d votes forward along the iterative process. For d sufficiently large, the resulting set of undominated alternatives is always non-empty even if indifference is allowed. We show that it may be unduly large. Next, by assuming that other voters along a chain of votes are also rational, that is, they also look forward to make sure that the votes taking place later on will not lead to a worst issue for them, we are able to reduce the size of this set while insuring its non-emptiness. Finally, we show that a vote with sufficient foresight satisfies a no-regret property, contrarily to the classical core and the stability set.     

Approximation of convex bodies by polytopes

LetC be a convex body ofE ^d and consider the symmetric difference metric. The distance ofC to its best approximating polytope having at mostn vertices is 0 (1/n ^2/(d?1)) asn→∞. It is shown that this estimate cannot be improved for anyC of differentiability class two. These results complement analogous theorems for the Hausdorff metric. It is also shown that for both metrics the approximation properties of «most» convex bodies are rather irregular and that ford=2 «most» convex bodies have unique best approximating polygons with respect to both metrics.     

A note on balancedness and nonemptiness of the core in voting games

Consider a society with a finite number,n, of individuals who have to choose an alternative from a setA in them-dimensional Euclidean space IR ^m . Assuming that the preference relation overA of every individual is convex and continuous, Greenberg (1979) showed some that if the set of winning coalitions (i.e. those that have the veto power) consists of all coalitions with more thanmn/m + 1 individuals the core of the induced game is nonempty. Greenberg and Weber (1984) have strengthened this result by showing that the induced game is in fact balanced. On the other hand Le Breton (1987), Schofield (1984a) and Strnad (1985) have generalized Greenberg's theorem to arbitrary voting games. The purpose of this note is to show that however the induced game is not generally balanced.     

Approaches to collective decision making with fuzzy preference relations

Recent experimental studies show that the predictive accuracy of many of the solution concepts derived from the collective decision making theory leaves much to be desired. In a previous paper the author attempted to explain some of the inaccuracies in terms of the fuzzy indifference regions of the individuals participating in the voting game. This paper gives straightforward generalizations of the solutions concepts in terms of the fuzzy social or individual preference relations. It turns out that some of these new solution concepts cotain their nonfuzzy counterparts as subsets. Others, in turn, are subsets of their nonfuzzy counterparts. We also discuss a method of aggregating individual nonfuzzy preferences so as to get a fuzzy social preference relation and, furthermore, a nonfuzzy social choice set.     

Self-similar fractals: An algorithmic point of view

This paper studies the self-similar fractals with overlaps from an algorithmic point of view.A decidable problem is a question such that there is an algorithm to answer"yes"or"no"to the question for every possible input.For a classical class of self-similar sets{E b.d}b,d where E b.d=Sn i=1(E b,d/d+b i)with b=(b1,...,b n)∈Qn and d∈N∩[n,∞),we prove that the following problems on the class are decidable:To test if the Hausdorff dimension of a given self-similar set is equal to its similarity dimension,and to test if a given self-similar set satisfies the open set condition(or the strong separation condition).In fact,based on graph algorithm,there are polynomial time algorithms for the above decidable problem.     

Logrolling and budget allocation games

In this paper we approach the concept of logrolling by examining a voting system where choices are made among sets of competing projects as a game in characteristic function form. We translate the question: “Will there be prices for votes on different projects which clear the market?” into a different, but equivalent question: “Is the formal game we have described amarket game?” We show that in general the answer is no, unless all voters have virtually the same preferences.     

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].     

Triple-consistent social choice and the majority rule

We define generalized (preference) domains \(\mathcal{D}\) as subsets of the hypercube {?1,1} ^D , where each of the D coordinates relates to a yes-no issue. Given a finite set of n individuals, a profile assigns each individual to an element of \(\mathcal{D}\) . We prove that, for any domain \(\mathcal{D}\) , the outcome of issue-wise majority voting φ _m belongs to \(\mathcal{D}\) at any profile where φ _m is well-defined if and only if this is true when φ _m is applied to any profile involving only 3 elements of \(\mathcal{D}\) . We call this property triple-consistency. We characterize the class of anonymous issue-wise voting rules that are triple-consistent, and give several interpretations of the result, each being related to a specific collective choice problem.