标题： 在大量替代方案中出现康多塞获胜者的概率 显示英文标题

标题： On the probability of a Condorcet winner among a large number of alternatives

摘要： 考虑$2k-1$选民，每个选民在$n$个给定的备选方案之间有一个偏好排名。 另一种$A$被称为康多塞优胜者，如果它在多数投票中击败了其他所有另一种$B$（这意味着对于其他任何另一种$B$，至少有$k$名选民更喜欢$A$胜过$B$）。 康多塞优胜者的概念已经被研究了数十年，但一些基本问题仍然悬而未决。 在本文中，我们考虑一个模型，其中每个选民根据所有排名中的某种概率分布随机选择他们的排名。 然后人们可能会问，当随机选择排名时，出现康多塞赢家的概率是多少（这当然取决于$n$和$k$，以及排名集合上的基础概率分布）。 在所有排名上的均匀概率分布情况下，这种情况受到了很多关注，并常被称为“无偏文化”情形，我们渐近地确定了在固定数量的$2k-1$选民和$n$个候选者的情况下，出现康多塞赢家的概率，其中$n\to \infty$。 这个问题已经存在了大约五十年。 虽然一些作者认为无偏文化应该表现出最低可能的康多塞赢家概率，但实际上对于其他分布，这个概率可以小得多。 我们确定了对于所有$n$和$k$的值，出现康多塞赢家的最小可能概率（并给出一个实现这一最小可能概率的概率分布的例子）。 显示英文摘要

摘要： 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\to \infty$. 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).