On the probability of a Condorcet winner among a large number of alternatives

Abstract

Consider 2k-1 voters, each of which has a preference ranking between n given alternatives. An alternative A is called a Condorcet winner, if it wins against every other alternative B in majority voting (meaning that for every other alternative B there are at least k voters who prefer A over B). The notion of Condorcet winners has been studied intensively for many decades, yet some basic questions remain open. In this paper, we consider a model where each voter chooses their ranking randomly according to some probability distribution among all rankings. One may then ask about the probability to have a Condorcet winner with these randomly chosen rankings (which, of course, depends on n and k, and the underlying probability distribution on the set of rankings). In the case of the uniform probability distribution over all rankings, which has received a lot of attention and is often referred to as the setting of an "impartial culture", we asymptotically determine the probability of having a Condorcet winner for a fixed number 2k-1 of voters and n alternatives with n . This question has been open for around fifty years. While some authors suggested that the impartial culture should exhibit the lowest possible probability of having a Condorcet winner, in fact the probability can be much smaller for other distributions. We determine, for all values of n and k, the smallest possible probability of having a Condorcet winner (and give an example of a probability distribution over all rankings which achieves this minimum possible probability).

Tasks

Reproductions