如何通过矩阵选出孔多塞选举的获胜者？

Question

我想了解如何在排名选择选举中选出孔多塞获胜者。

在wikipedia上有一个例子 - 在“基本程序”标题下的“成对计数和矩阵”子标题下，其中为选举中的候选人 A、B、C 和 D 构建了成对比较矩阵。矩阵看起来像：

从这个矩阵可以得出结论：A 是孔多塞获胜者。我可以看到结果是正确的，但不明白如何通过算法解决这个问题。

`

[[0, 2, 2, 2],

[1, 0, 1, 2],

[1, 2, 0, 2],

[1, 1, 1, 0]]

`

更复杂的例子可以在accuratedemocracy的表2-a中找到；考虑与候选人 A、B、C 和 D 进行不同的选举时；他们发现 C 是获胜者，但可以单击单元格 C 和 D 来验证它们在成对比较矩阵中获得相同数量的选票。为什么C获胜而不是D？

假设已经构造了两两比较矩阵。如何从这个矩阵中选出孔多塞获胜者？

举个例子，可以使用以下代码在Python中构造成对比较矩阵：

`

import numpy as np

unranked_choices = ["A", "B", "C", "D"]

def generate_preference_matrix(ranked_choices):
    num_candidates = len(ranked_choices)
    preference_matrix = np.zeros((num_candidates, num_candidates))

    for i, candidate_i in enumerate(unranked_choices):
        for j, candidate_j in enumerate(unranked_choices):
            if i != j:
                if ranked_choices.index(candidate_i) < ranked_choices.index(candidate_j):
                    preference_matrix[i, j] += 1  # Candidate_i is preferred over candidate_j
                # else:
                #     preference_matrix[i, j] = 0  # No preference or candidate_j is preferred over candidate_i

    return preference_matrix


# Test with example ranked choices
ranked_choices = ['B', 'C', 'A', 'D']  # Ranked choices in order of preference
preference_matrix = generate_preference_matrix(ranked_choices)
print(preference_matrix)

ranked_choices = ['A', 'D', 'B', 'C']  # Ranked choices in order of preference
preference_matrix = generate_preference_matrix(ranked_choices)
print(preference_matrix)

`

Answer 1

您需要将偏好矩阵相加才能计算排名。总分最高的候选人被宣布为获胜者。

import numpy as np
from itertools import combinations


def get_ranked_order(candidates, preferences):

    def get_preference_matrix(preference_order):
        nonlocal candidates
        preference_matrix = np.zeros((len(preference_order), len(preference_order)))
        for a, b in combinations(candidates, 2):
            if preference_order.index(a) < preference_order.index(b):
                preference_matrix[candidates.index(a), candidates.index(b)] += 1
            if preference_order.index(b) < preference_order.index(a):
                preference_matrix[candidates.index(b), candidates.index(a)] += 1
        return preference_matrix

    # Sum the preference matrices
    sum_matrix = np.zeros((len(candidates), len(candidates)))
    for p in preferences:
        sum_matrix = np.add(sum_matrix, get_preference_matrix(p))

    # Sort candidates by decreasing scores
    return sorted(zip(candidates, [sum(r) for r in sum_matrix]),
                  key=lambda t: t[1], reverse=True)

使用维基百科页面上示例的数据：

vote_candidates = ("A", "B", "C", "D")
voter_preferences = [("B", "C", "A", "D"), ("A", "D", "B", "C"), ("A", "C", "B", "D")]
rankings = get_ranked_order(vote_candidates, voter_preferences)

if rankings[0][1] > rankings[1][1]:
    print(f"Condorcet Winner is {rankings[0]}")
else:
    print(rankings)

结果：

Condorcet Winner is ('A', 7.0)