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.     

Analysis and design of selection committees: a game theoretic secretary problem

Firms often delegate important decisions to committees which are set up specifically for that purpose; for example selection committees. We analyze the equilibrium behavior of a game in which committee members (the players) interview candidates sequentially, either hiring or going on to the next one. The players have differing evaluations of candidates (e.g. one cares about typing skills; the other about IT skills), which become their utilities if the candidate is hired. We then consider the optimal design (rules of the game) of such a committee, from the point of view of the firm. That is, which rules hire candidates which maximize the firm’s utility. Our committee game has a first round in which the members sequentially, by order of player number, say ‘yea’ or ‘nea’ to the candidate. If there are sufficient ‘yeas’ then she is tentatively hired; otherwise she is rejected. In the former case, members who said nea can veto the candidate in the second round. Thus the candidate is either hired, rejected, or vetoed. In the last case, the member casting a veto has one less to use on later candidates. We analyze equilibria where a player may say ‘yea’ to a candidate he would prefer not to hire, in order to force the other player to use up a valuable veto. We show that for the uniform candidate distribution there is a unique equilibrium and better candidates for the firm are hired when there are more vetoes. However we exhibit a candidate distribution where increasing the numbers of vetoes results in hiring worse candidates.     

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.     

How hard is it to tell which is a Condorcet committee?

This paper establishes the computational complexity status for a problem of deciding on the quality of a committee. Starting with individual preferences over alternatives, we analyse when it can be determined efficiently if a given committee C$C$ satisfies a weak (resp. strong) Condorcet criterion–i.e., if C$C$ is at least as good as (resp. better than) every other committee in a pairwise majority comparison. Scoring functions used in classic voting rules are adapted for these comparisons. In particular, we draw the sharp separation line between computationally tractable and intractable instances with respect to different voting rules. Finally, we show that deciding if there exists a committee which satisfies the weak (resp. strong) Condorcet criterion is computationally hard.     

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.     

Extensions of the Young and Levenglick result about the inconsistency of Condorcet voting correspondences

The Young’s Consistency property means that when some candidates are chosen as winners by two disjoint electorates, those and only those candidates are chosen in the aggregated electorate. We define two new properties requiring that, when a candidate x is elected in a situation and a new electorate is added for which x is a very good candidate, x will remain elected. These properties, weaker than Young’s Consistency, lead to new impossibility results strengthening the Young and Levenglick result about the inconsistency of Condorcet Voting Correspondences. Also we adapt the Young and Levenglick result to the k-choice voting function context.     

The Borda rule and Pareto stability: a further comment

In their paper “The Borda rule and Pareto stability: a comment” published in 1979 by Econometrica, Farkas and Nitzan revealed the “intimate relationship” between the Borda rule and the Pareto criterion. The idea was the following: in a profile of total orders, when there is a candidate who obviously wins under unanimous agreement of the voters, that candidate should be in the choice set. In a profile where there is no obvious winner, the candidates that are the closest to unanimity should be chosen. According to this principle, they defined a choice rule called “closeness to unanimity” and they showed that it is equivalent to the Borda rule. In our paper, we give an equivalent result for a ranking rule. Then we try to obtain similar results when aggregating profiles of tournaments, weak orders, semiorders, fuzzy relations, … and we show that the definition of an obvious winner is no more obvious.     

Group preference aggregation rules: The results of a comparative analysis with <Emphasis Type="Italic">in situ</Emphasis> data

Committees are sometimes engaged in tasks concerned with establishing ranked priorities and rationing scarce resources. However there is no generally accepted approach to combining judgements from individual members of a committee to form a group consensus. There are issues concerned with the make-up of a committee, its size and history, and the procedures used to produce committee decisions. This article presents the results of an analysis of data from 28 separate committees engaged on an actual ranking task concerned with the selection of research proposals for public sector funding. This paper explores whether the ranked lists produced by the committees are influenced by the position of a particular proposal in the agenda, the financial value of the proposal, the scoring scale used by the committees, or an ‘out of line’ rating by a single committee member. The results suggest that the last two factors can have a significant effect on the ranked positions produced by the committees.     

Networks with condorcet solutions

A Condorcet point on a network is a point such that thare is no other point closer to a strict majority of users which are located at the vertices of the network. A complete characterization is given of those networks on which no Condorcet paradox occurs, in the sense that for each distribution of users there exists at least one Condorcet point. Moreover, those networks are characterized on which Condorcet points and Weber points always coincide. A polynomial algorithm is obtained which decides whether a given network has Condorcet points for all distributions of users on the network.     

Comparison of α-Condorcet points with median and center locations

The usual concept of solution in single voting location is the Condorcet point. A Condorcet solution is the location such that no other location is preferred by a strict majority of voters; i.e. a half of them. It is assumed that each user always prefers closer locations. Because a Condorcet point does not necessarily exist, the α-Condorcet point is defined in the same way but assuming that two locations are indifferent for a user if the distances to both differ at most in α. We give bounds for the value of the objective function in an α-Condorcet point in the median and center problems. These results, for a general graph and for a tree, extend previous bounds for the objective function in a Condorcet point. We also provide a set of instances where these bounds are asymptotically reached. This research has been partially supported by DGICYT through project PB95-1237-C03-02 and by Gobierno de Canarias through the projects CO-1/97 and PI1999/116.     

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.     

Representations of simple games by social choice functions

We investigate possible constructions of choice procedures (social choice functions) for committees (simple games). The notion of a capacity of a committee is derived from our construction. We determine the capacity of strong, symmetric and weak simple games. We also provide an upper bound on the capacity of a simple game without veto players.     

A ranked voting system using a DEA/AR exclusion model: A note

This paper addresses ranked voting systems to determine an ordering of candidates in terms of the aggregate vote by rank for each candidate. It is shown that specifying nothing arbitrary, we can obtain a total ordering of candidates by using a DEA/AR (Data Envelopment Analysis/Assurance Region) exclusion model. Explaining the evaluation criterion used to rank candidates, it is concluded that we may consider the system proposed at least as an alternative to determine an ordering of candidates.     

MARS: selecting basis functions and knots with an empirical Bayes method

An empirical Bayes method to select basis functions and knots in multivariate adaptive regression spline (MARS) is proposed, which takes both advantages of frequentist model selection approaches and Bayesian approaches. A penalized likelihood is maximized to estimate regression coefficients for selected basis functions, and an approximated marginal likelihood is maximized to select knots and variables involved in basis functions. Moreover, the Akaike Bayes information criterion (ABIC) is used to determine the number of basis functions. It is shown that the proposed method gives estimation of regression structure that is relatively parsimonious and more stable for some example data sets.     

Comparing the Likelihood Functions of Phylogenetic Trees

DNA sequence data provide a good source of information on the evolutionary history of organisms. Among the proposed methods, the maximum likelihood methods require an explicit probabilistic model of nucleotide substitution that makes the assumption clear. However, procedures for testing hypotheses on topologies have not been well developed. We propose a revised version of the maximum likelihood estimator of a tree and derive some of its properties. Then we present tests to compare given trees and to derive the most likely candidates for the true topology, applying to maximum likelihoods the notion of contrast, as defined in the framework of the analysis of variance, and the procedures used in multiple comparison. Finally, an example is presented.     

A multicriteria accreditation system for information technology skills and qualifications

Employees must acquire new competences and qualifications throughout their lives, in order to be able to deal with the multiple changes in the labour market. The specific knowledge and competences, acquired either formally or non-formally, must be recognized so that they can be transferred and utilized. The existing titles of studies and accreditation mechanisms do not generally cover this need. This paper aims to propose an integrated approach for the evaluation of information technology knowledge and skills, regardless of where and how they have been acquired, so as to apply a continuous education and training policy. The proposed multicriteria methodology for the evaluation of qualifications and skills concerns candidates wishing to be accredited in an information technology specialization or profession. The methodology refers to the evaluation of the professional experience, studies and vocational training of the candidates for accreditation. It contains the analysis and modelling of the qualitative criteria as well as the implementation of multicriteria aggregation–disaggregation techniques attributing value to each criterion. Then, the candidates are classified in categories of professionals using the Electre Tri method, accepting as input data the multicriteria assessments on each criterion. The proposed evaluation approach has been adapted to the Greek educational system and is applied to a specific example of candidate.     

Majority decisions when abstention is possible

Suppose that we are given a family of choice functions on pairs from a given finite set. The set is considered as a set of alternatives (say candidates for an office) and the functions as potential “voters.” The question is, what choice functions agree, on every pair, with the majority of some finite subfamily of the voters? For the problem as stated, a complete characterization was given in Shelah (2009) [7], but here we allow voters to abstain. Aside from the trivial case, the possible families of (partial) choice functions break into three cases in terms of the functions that can be generated by majority decision. In one of these, cycles along the lines of Condorcet’s paradox are avoided. In another, all partial choice functions can be represented.     

On the composition and decomposition of clutters

The decomposition theory for simple n-person games is discussed in the context of clutters on a finite set. The notion of committee is defined, and an algorithm is given to find committees of any clutter. It is shown that this decomposition leads to a decomposition scheme for solving bottleneck and shortest path problems over clutters. Finally it is shown that the property of satisfying the length-width inequality is preserved under composition.     

Model-based regression clustering for high-dimensional data: application to functional data

Finite mixture regression models are useful for modeling the relationship between response and predictors arising from different subpopulations. In this article, we study high-dimensional predictors and high-dimensional response and propose two procedures to cluster observations according to the link between predictors and the response. To reduce the dimension, we propose to use the Lasso estimator, which takes into account the sparsity and a maximum likelihood estimator penalized by the rank, to take into account the matrix structure. To choose the number of components and the sparsity level, we construct a collection of models, varying those two parameters and we select a model among this collection with a non-asymptotic criterion. We extend these procedures to functional data, where predictors and responses are functions. For this purpose, we use a wavelet-based approach. For each situation, we provide algorithms and apply and evaluate our methods both on simulated and real datasets, to understand how they work in practice.     

Inequality in population weights,majority threshold and the inversion probability in the case of three states

Two-tier voting systems are prone to majority inversions, when the outcome of an election is not backed by a majority of popular vote. We study the inversion probability in a model with two candidates, three states and uniformly distributed fractions of supporters for each candidate. We show that the inversion probability in a two-tier voting system with three states eventually decreases with a majority threshold in the states and increases with the inequality in the size distribution of the states.