What majority decisions are possible

Suppose we are given a family of choice functions on pairs from a given finite set (with at least three elements) closed under permutations of the given set. The set is considered the set of alternatives (say candidates for an office). The question is, what are the choice functions c on pairs of this set of the following form: for some (finite) family of “voters”, each having a preference, i.e. a choice from each pair from the given family, is chosen by the preference of the majority of voters. We give full characterization.     

Maximal Condorcet Domains

A Condorcet domain is a subset of the set of linear orders on a finite set of candidates (alternatives to vote), such that if voters preferences are linear orders belonging to this subset, then the simple majority rule does not yield cycles. It is well-known that the set of linear orders is the Bruhat lattice. We prove that a maximal Condorcet domain is a distributive sublattice in the Bruhat lattice. An explicit lattice formula for the simple majority rule is given. We introduce the notion of a symmetric Condorcet domain and characterize symmetric Condorcet domains of maximal size.     

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.     

Condorcet domains of tiling type

A Condorcet domain (CD) is a collection of linear orders on a set of candidates satisfying the following property: for any choice of preferences of voters from this collection, a simple majority rule does not yield cycles. We propose a method of constructing “large” CDs by use of rhombus tiling diagrams and explain that this method unifies several constructions of CDs known earlier. Finally, we show that three conjectures on the maximal sizes of those CDs are, in fact, equivalent and provide a counterexample to them.     

Scoring rule and majority agreements for large electorates with arbitrary preferences

This paper examines elections among three candidates when the electorate is large and voters can have any of the 26 nontrivial asymmetric binary relations on the candidates as their preference relations. Comparisons are made between rule-λ rankings based on rank-order ballots and simple majorities based on the preference relations. The rule-λ ranking is the decreasing point total order obtained when 1, λ and 0 points are assigned to the candidates ranked first, second and third on each voter's ballot, with 0 ? λ ? 1.Limit probabilities as the number of voters gets large are computed for events such as ‘the first-ranked rule-λ candidate has a majority over the second-ranked rule-λ candidate’ and ‘the rule-λ winner is the Condorcet candidate, given that there is a Condorcet candidate’. The probabilities are expressed as functions of λ and the distribution of voters over types of preference relations. In general, they are maximized at λ = 1/2 (Borda) and minimized at λ = 0 (plurality) and at λ = 1 for any fixed distribution of voters over preference types. The effects of more indifference and increased intransitivity in voter's preference relations are analyzed when λ is fixed.     

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

Achieving fully proportional representation by clustering voters

Both the Chamberlin–Courant and Monroe rules are voting rules that solve the problem of fully proportional representation: given a set of candidates and a set of voters, they select committees of candidates whose members represent the voters so that the voters’ total dissatisfaction is minimized. These two rules suffer from a common disadvantage, namely being computationally intractable. As both the Chamberlin–Courant and Monroe rules, explicitly or implicitly, partition voters so that the voters in each part share the same representative, they can be seen as clustering algorithms. This suggests studying approximation algorithms for these voting rules by means of cluster analysis, which is the subject of this paper. Using ideas from cluster analysis we develop several approximation algorithms for the Chamberlin–Courant and Monroe rules and experimentally analyze their performance. We find that our algorithms are computationally efficient and, in many cases, are able to provide solutions which are very close to optimal.     

Estimating the size of the calling population in finite-source election queues by bilinear programming techniques

Finite source multi-server queuing systems represent a particular type of an exact model of voting places (precincts) servicing voters on the election day. The size of the calling population from which the arrivals (voters) come to vote in a precinct at each time segment of the election day is among key parameters of such systems. The problem of finding this parameter is formulated as the problem of maximizing the maximum function of a finite number of bilinear functions on polyhedra, and it can be solved with the use of bilinear programming techniques.     

The Banzhaf power index for political games

The Banzhaf index of a voting game is a measure of a priori power of the voters. The model on which the index is based treats the voters symmetrically, i.e. the ideology, outlook, etc., of the voters influencing their voting behavior is ignored. Here we present a nonsymmetric generalization of the Banzhaf index in which the ideology of the voters affecting their voting behavior is taken into account. A model of ideologies and issues is presented. The conditions under which our model gives the Shapley-Shubik index (another index of a priori power of the voters) are given. Finally several examples are presented and some qualitative results are given for straight majority and pure bargaining games.     

Fractal Polynomials and Maps in Approximation of Continuous Functions

The primary goal of this article is to establish some approximation properties of fractal functions. More specifically, we establish that a monotone continuous real-valued function can be uniformly approximated with a monotone fractal polynomial, which in addition agrees with the function on an arbitrarily given finite set of points. Furthermore, the simultaneous approximation and \mboxinterpolation which is norm-preserving property of fractal polynomials is established. In the final part of the article, we establish differentiability of a more general class of fractal functions. It is shown that these smooth fractal functions and their derivatives are good approximants for the original function and its \mboxderivatives.     

大型群体决策问题中的简单多数规则（3个评选对象场合）

一个群体决策问题取决于两个因素,一个是群体决策的规则,另一个是投票。当选定群体决策规则时,一个群体决策问题由投票完全决定,此时,群体决策问题与投票之间一一对应。简单多数规则是个简单且被广泛采用的群体决策规则,但它有缺陷,我们可举出些群体决策问题使用简单多数规则没法从投票得到最后群体决策的结果。这里我们将给出一个简单多数规则的有趣性质,即在3个评选对象场合,使用简单多数规则没法从投票得到最后群体决策结果的n个评选人的群体决策问题的个数与所有n个评选人的群体决策问题的个数之比当评选人个数n趋向无穷时趋于零,这说明3个评选对象的大型群体决策场合,简单多数规则的缺陷不严重。     

A universal envelope for Gaussian processes and their kernels

The central theme in our paper deals with mathematical issues involved in the answer to the following question: How can we generate stochastic processes from their correlation data? Since Gaussian processes are determined by moment information up to order two, we focus on the Gaussian case. Two functional analytic tools are used here, in more than one variant. They are: operator factorization; and direct integral decompositions in the form of Karhunen-Loève expansions. We define and study a new interplay between the theory of positive definition functions, and their reproducing kernels, on the one hand, and Gaussian stochastic processes, on the other. The three classes of processes we study are as follows: Processes associated with: (a) arbitrarily given sigma finite regular measures on a fixed Borel measure space; (b) with Hilbert spaces of sigma-functions; and (c) with systems of self-similar measures arising in the theory of iterated function systems. Starting with a non-degenerate positive definite function K on some fixed set S, we show that there is a choice of a universal sample space Ω, which can be realized as a “boundary” of (S,K). Its boundary-theoretic properties are analyzed, and we point out their relevance to the study of electrical networks on countable infinite graphs.     

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.     

A distributed social choice protocol for combinatorial domains

In this paper, we study the problem of collective decision-making over combinatorial domains, where the set of possible alternatives is a Cartesian product of (finite) domain values for each of a given set of variables, and these variables are not preferentially independent. Due to the large alternative space, most common rules for social choice cannot be directly applied to compute a winner. In this paper, we introduce a distributed protocol for collective decision-making in combinatorial domains, which enjoys the following desirable properties: (i) the final decision chosen is guaranteed to be a Smith member; (ii) it enables distributed decision-making and works under incomplete information settings, i.e., the agents are not required to reveal their preferences explicitly; (iii) it significantly reduces the amount of dominance testings (individual outcome comparisons) that each agent needs to conduct, as well as the number of pairwise comparisons; (iv) it is sufficiently general and does not restrict the choice of preference representation languages.     

A provably convergent heuristic for stochastic bicriteria integer programming

We propose a general-purpose algorithm APS (Adaptive Pareto-Sampling) for determining the set of Pareto-optimal solutions of bicriteria combinatorial optimization (CO) problems under uncertainty, where the objective functions are expectations of random variables depending on a decision from a finite feasible set. APS is iterative and population-based and combines random sampling with the solution of corresponding deterministic bicriteria CO problem instances. Special attention is given to the case where the corresponding deterministic bicriteria CO problem can be formulated as a bicriteria integer linear program (ILP). In this case, well-known solution techniques such as the algorithm by Chalmet et al. can be applied for solving the deterministic subproblem. If the execution of APS is terminated after a given number of iterations, only an approximate solution is obtained in general, such that APS must be considered a metaheuristic. Nevertheless, a strict mathematical result is shown that ensures, under rather mild conditions, convergence of the current solution set to the set of Pareto-optimal solutions. A modification replacing or supporting the bicriteria ILP solver by some metaheuristic for multicriteria CO problems is discussed. As an illustration, we outline the application of the method to stochastic bicriteria knapsack problems by specializing the general framework to this particular case and by providing computational examples.     

A reduction result for location problems with polyhedral barriers

In this paper we consider the problem of locating one new facility in the plane with respect to a given set of existing facilities where a set of polyhedral barriers restricts traveling. This non-convex optimization problem can be reduced to a finite set of convex subproblems if the objective function is a convex function of the travel distances between the new and the existing facilities (like e.g. the median and center objective functions). An exact algorithm and a heuristic solution procedure based on this reduction result are developed.     

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.     

Über Picardmengen ganzer Funktionen

Following Lehto we call a set E in the complex plane a Picard set for integral functions, if every non-rational integral function omits at most one finite value in the complement (with respect to the plane) of E. The existence of non-trivial Picard sets was proved by Lehto [3]. The aim of this paper is to give a new criterion for denumberable point sets E to be Picard sets for integral functions. In some way the criterion given by theorem 1 is an extension of the result on Picard sets for integral functions given by Toppila [5] and improves the criterion given by the author in [6].