高效获取集体分歧

# 有效引发集体分歧的机制  
**来源**: https://arxiv.org/html/2605.19521  

**Mohamed Ouaguenouni¹**, **Felipe Garrido-Lucero¹**, **Umberto Grandi¹**, **César Hidalgo²,³,⁴**, **Magdalena Tydrichova⁵**  
¹ IRIT，图卢兹第一大学，法国图卢兹  
² 集体学习中心，IAST，图卢兹经济学院，法国图卢兹  
³ 集体学习中心，CIAS，布达佩斯考文纽斯大学，匈牙利布达佩斯  
⁴ AMBS，曼彻斯特大学，英国曼彻斯特  
⁵ Centrale Supélec，巴黎萨克雷大学，法国  

###### 摘要  
我们分析了选民群体在备选项集合上分歧的结构。传统调查通常要求参与者进行成对比较（简单直观）或对备选项进行完整排序（揭示全部偏好）。基于成对比较无法区分结构性分歧与随机噪声这一观察，我们提出一个分层框架，用于识别计算文献中多种分歧度量所需的最小聚合偏好信息。具体而言，我们引入**多数矩阵**，这是成对比较的推广，记录每个子集 \(S\) 中每个 \(a \in S\) 在 \(S\) 中排名第一的概率。我们将分歧度量的**阶**定义为其表达所需的最小子集大小，证明许多现有概念（如排名方差和分歧性）位于第 3 阶，表明成对比较（第 2 阶）是不够的。此外，我们从理论和实验两个方面展示了超越第 3 阶的价值。为使这些结果可行，我们设计了两种估计多数矩阵的引发协议，探索所需参与者数量与每个参与者认知负荷之间的权衡。

## 1 引言  
社会选择理论旨在建模并改进社会做出集体决策的方式。大量文献通过提出偏好聚合规则来解决这个问题，这些规则旨在根据代理人声明的偏好从选项集中选出最优备选项，并通过公理化刻画和设计高效的计算引发协议（Arrow 等，2010；Brandt 等，2016b；Fürnkranz 和 Hüllermeier，2011）。然而，共识只是故事的一半：社会在达成一致之前，通常需要面对并解决分歧（Waldron，1999）。这在协商平台 Pol.is 上得到了充分体现，该平台在展示共识性提议的同时，也突出显示票数差距最小的提议。尽管兴趣日益增长，但（计算）社会选择文献中对分歧的关注相对较少。直观上，当一个群体支持某个选项而另一个群体反对时，该选项就是有分歧的。然而，尚未建立起规范的定义：现有方法依赖于极化度量（Esteban 和 Ray，1994）、选项排名在用户间的方差（Gaitonde 等，2020；Musco 等，2018），或利用相对排名识别群体派系（Navarrete 等，2024）。  
除了聚合规则的选择，集体决策中同样重要的方面是偏好的引发方式。大量工作专注于设计高效的引发协议，旨在减少认知和沟通负担，同时保留足够信息以进行准确决策（Conitzer 和 Sandholm，2005；Procaccia，2009）。一种特别简单且广泛使用的引发原语是**成对比较**（Thurstone，1927），即要求代理人在两个备选项之间做出选择。然而，仅依赖成对比较可能无法揭示集体偏好的重要特征，尤其是与分歧和极化相关的特征，如下例所示：  
**成对比较不足以捕捉集体分歧。**  
考虑两个对三个备选项 \(a, b, c\) 进行排序的人群。在人群 1 中，所有六种可能的排序出现频率相同。在人群 2 中，选民被分为两个对立群体：一半将 \(a\) 排第一、\(c\) 排最后，另一半则相反。从成对比较的角度看，这两群人完全相同：对于任何一对备选项，每个选项排在对方案之前的概率相等。然而，潜在的分歧结构却大相径庭。在人群 1 中，每个备选项的位置均匀分布在三个排名上；而在人群 2 中，选项 \(a\) 和 \(c\) 要么排第一要么排最后，形成分裂。  
**贡献。**  
基于上述观察，我们引入一种新的偏好表示，对每个备选项子集编码该子集中每个成员作为其最高排名选项的可能性。利用这种表示，我们研究了计算文献中若干著名分歧度量所需的最小信息，并设计了适合不同场景的引发协议。我们的主要贡献如下：

- • 我们引入了**多数矩阵**，对于每个备选项子集 \(S\) 和每个 \(a \in S\)，记录 \(a\) 在 \(S\) 中排名第一的概率。行按 \(S\) 的大小递增排列，定义了不同的**阶**，成对比较对应于第 2 阶。
- • 我们证明了计算**一致指数**（Faliszewski 等，2023）、**排名方差**（Kendall 和 Smith，1939）和**分歧性度量**（Navarrete 等，2024）分别需要第 2、第 3 和第 3 阶的信息，表明某些分歧度量本质上需要比成对比较更多的信息。
- • 我们证明，对于任意阶 \(k\)，都存在实例在第 \(k\) 阶上信息相同但在第 \(k+1\) 阶上不同，表明阶的层次结构是严格的。此外，对于每个阶 \(k\)，我们构造了一个恰好位于该阶的分歧度量。
- • 我们证明，在单峰偏好或 Plackett–Luce 模型下，层次结构坍缩到第 2 阶。
- • 我们提出了两种引发协议，并分析了它们在每个选民认知负荷与人群规模之间产生的权衡。

**相关工作。**  
相关文献涵盖三个互补方向：社会选择中分歧的度量、超越成对比较的增强型引发，以及成本效益高的引发协议设计。首先，社会选择中的一些工作研究了如何定义与共识正交的度量。现有方法通常捕捉选民偏好的多样性（Ammann 和 Puppe，2025；Faliszewski 等，2026；Hashemi 和 Endriss，2014；Karpov，2017）或极化（Can 等，2015；Faliszewski 等，2023）。这些概念通常定义在完整偏好轮廓层面，并且往往依赖于完整排序。与我们的视角更接近的是定义在备选项层面的度量，例如 Navarrete 等人的分歧性度量（Colley 等，2023a；Navarrete 等，2024），以及 Delemazure 等人对冲突对的公理化分析（Delemazure 等，2024）。  
其次，一些工作考虑了比成对比较更丰富的查询模型，用于偏好引发，并且与我们的框架密切相关。特别是，子集查询——呈现一组备选项并返回最佳者——已在学习和排序设置中得到研究（Saha 和 Gopalan，2019）。相关模型包括 top-\(k\) 查询，每次交互提取更多信息（Ayadi 等，2022；Chen 等，2018），以及最近关于引发所查询子集完整排序的工作（Halpern 等，2024）。  
第三，一条互补的工作路线研究认知约束下的引发协议，这与我们设计可行的替代完整排序引发方法的目标相关。在投票中，Terzopoulou（2023）最近引入了选民报告偏好的“能量”概念，捕捉每个选民能排名的备选项数量限制，并研究了由此对多数投票和 Borda 规则造成的社会福利损失。更广泛地说，行为决策理论强调了认知负荷和任务复杂性对回答质量的影响（Griffin 等，2005），从而推动了在信息丰富性与实际可用性之间取得平衡的混合或自适应引发格式的设计（Brams 和 Sanver，2009；Dery，2024）。

## 2 模型  
本节致力于引入代理人对备选项偏好的概率模型，定义**多数矩阵**，并将三个分歧度量定义为我们的用例。  
设 \(\mathcal{A} = \{a, b, \ldots\}\) 为 \(m \ge 3\) 个备选项的有限集合，\(\Pi_m\) 为所有 \(m!\) 种 \(\mathcal{A}\) 的严格排序的集合，\(\mathcal{S} := \{S \subseteq \mathcal{A}: 2 \le |S| \le m\}\)（按大小排序，然后按字典序）。对于陈述 \(\tau\)，\(\mathbb{1}\{\tau\}\) 表示 \(\tau\) 的指示函数。**偏好轮廓**（或选民群体）是 \(\Pi_m\) 上的一个概率分布 \(\pi\)，而**选民**对应于从 \(\pi\) 中采样的一个排序 \(\succ \in \Pi_m\)。我们采用概率观点，因为许多应用（如在线平台）通常涉及大量参与者。  
我们现在介绍本文的主要概念之一——**多数矩阵**，它将作为分析分歧和设计引发协议的基础。

###### 定义 2.1。  
设 \(\pi\) 是偏好轮廓。我们定义**多数矩阵** \(\mathcal{P}_\pi \in [0,1]^{\mathcal{S} \times \mathcal{A}}\)，其中对于每个 \(S \in \mathcal{S}\) 和 \(a \in \mathcal{A}\)，条目 \((S, a)\) 由下式给出：  
\[
p_S^\pi(a) := \mathbb{P}_\pi(a \text{ 在备选项集 } S \text{ 中排名第一}) \cdot \mathbb{1}\{a \in S\}.
\]  
为简便起见，我们将 \(p_{\{x,y,w,z\}}^\pi\) 写作 \(p_{xywz}^\pi\)。对于 \(k \in \{2, \ldots, m\}\)，我们将**第 \(k\) 阶的数据（或信息）** 称为仅包含大小为 \(k\) 的集合对应行的子矩阵。我们说一个实值统计量 \(\Phi\) 的**阶**为 \(k\)，如果对于任何偏好轮廓 \(\pi\) 和备选项 \(a\)，\(\Phi(\pi, a)\) 可以用最多第 \(k\) 阶的数据表示，但不能用最多第 \(k-1\) 阶的数据表示。我们在本文中假设 \(p_S^\pi(a) > 0\) 对于每个轮廓 \(\pi\)、每个 \(S \in \mathcal{S}\) 和 \(a \in S\) 都成立：违反这一点的备选项在每个选民的排序中都处于被支配地位，因此永远不会成为分歧点。为简便起见，在下面的例 2.3 中我们做一次例外。当 \(a \notin S\) 时，我们写作 \(p_S^\pi(a) = \cdot\)。

###### 定义 2.2。  
设 \(\pi\) 是偏好轮廓，\(\succ \in \Pi_m\) 是一个排序，且 \(a \in \mathcal{A}\)。我们分别定义 \(a\) 的**排名**和 **Borda 分数**为：  
\[
r_a(\succ) := 1 + |\{b \in \mathcal{A} \setminus \{a\}: b \succ a\}| \quad \text{和} \quad \operatorname{Bor}_\pi(a) := \sum_{b \in \mathcal{A} \setminus \{a\}} p_{ab}^\pi(a) = m - \mathbb{E}_\pi[r_a].
\]  
此外，给定 \(x, y \in \mathcal{A}\)，我们定义 \(a\) 在偏好 \(x\) 优于 \(y\) 的子群体中的 Borda 分数为：  
\[
\operatorname{Bor}_\pi\bigl(a; \mathcal{N}_\pi^{x \succ y}\bigr) := \sum_{b \in \mathcal{A} \setminus \{a\}} \mathbb{P}_\pi(a \succ b \mid x \succ y).
\]  
成对比较（更精确地说，是所有选民对其的聚合）对应于第 2 阶的数据。特别地，Borda 分数是一个第 2 阶的度量。成对比较在文献中被广泛用于计算许多投票规则（Brandt 等，2016a；Fischer 等，2016；Navarrete 等，2024）。在另一个极端，第 \(m\) 阶的数据对应于多数票分数，即每个备选项在选民中排名第一的比例。一般来说，多数矩阵中不同阶的数据是互不相关的，也就是说，无法从另一个恢复出这一个。我们接下来通过例 2.3 说明多数矩阵的概念并给出一些初步见解。

###### 例 2.3。  
设 \(\mathcal{A} = \{a, b, c\}\)，考虑两个偏好轮廓：  
¹ 注意这两个轮廓位于 Szufa 等人（2025）可视化罗盘的相反两端。  
**公正文化轮廓** \(\pi_{\mathrm{IC}}\)，² 在我们的术语中，偏好轮廓通常被称为社会选择文献中的“文化”或“分布”。本例中我们考虑公正文化，但其他分布对应的轮廓参见图 2。其中所有备选项被均匀排序；以及**对抗轮廓** \(\pi_{\mathrm{AN}}\)，其中 \(b\) 和 \(c\) 被均匀排序，但 \(a\) 要么排第一要么排最后，概率各为 \(1/2\)。形式上，\(r_a\) 满足：  
\[
\mathbb{P}_{\pi_{\mathrm{IC}}}[r_a = i] = \frac{1}{3}, \text{ 对于 } i \in \{1,2,3\} \quad \text{和} \quad \mathbb{P}_{\pi_{\mathrm{AN}}}[r_a = i] = \frac{1}{2} \cdot \mathbb{1}\{i=1\} + \frac{1}{2} \cdot \mathbb{1}\{i=3\}.
\]  
表 1 展示了上述两个轮廓的多数矩阵。

**表 1：** \(\mathcal{A} = \{a, b, c\}\) 上 \(\pi_{\mathrm{IC}}\) 和 \(\pi_{\mathrm{AN}}\) 的多数矩阵  

| 集合 | \(\pi_{\mathrm{IC}}\) 的概率 | \(\pi_{\mathrm{AN}}\) 的概率 |
|------|---------------------------|---------------------------|
|      | \(a\) | \(b\) | \(c\) | \(a\) | \(b\) | \(c\) |
| \(\{a,b\}\) | 1/2 | - | - | 1/2 | - | - |
| \(\{a,c\}\) | 1/2 | - | - | 1/2 | - | - |
| \(\{b,c\}\) | - | 1/2 | 1/2 | - | 1/2 | 1/2 |
| \(\{a,b,c\}\) | 1/3 | 1/3 | 1/3 | 1/2 | 1/4 | 1/4 |

注意到两个矩阵在第 2 阶的所有条目上一致，但在第 3 阶上不同。任何仅基于