7.5.2 社会选择中的经典结论
7.5.2.1 阿罗不可能定理
要设计出一个优秀的投票机制是一件困难的事情。阿罗不可能定 理（Arrow's Impossibility Theorem）[1] 是由美国经济学家肯尼斯·阿 罗（Kenneth Arrow）于 1951 年提出的一项重要理论。这个定理涉及 社会选择理论，旨在探讨在特定条件下，如何将个体的偏好转化为集 体决策。阿罗不可能定理的核心观点是，不存在一种完美的社会选择 机制，能够满足所有合理的要求。换句话说，没有一种决策规则能够 在所有情况下将个体的偏好进行完美的汇聚，并得出符合所有公平性 标准的集体决策。虽然没有一种完美的决策规则可以满足所有的要求，但通过深入理解阿罗不可能定理，我们可以更好地设计决策机制，使 其更加公平、合理和高效。
7.5.2.2 Gibbard-Satterthwaite 定理
Gibbard-Satterthwaite 定理[2] [3] 也是社会选择理论中的一个重 要结果，该定理探讨了在特定条件下，不存在一种理想的社会选择机 制，能够避免潜在的操纵或欺骗。该定理的核心结论是，任何在三个 或更多候选选项上进行社会选择的机制，若要满足非独裁性（Non- dictatorship）和独立性（Independence of Irrelevant Alternatives），那么 都会存在潜在的操纵或欺骗的可能性。这个定理揭示了社会选择的困 难，即无论采用何种机制，都无法完全消除操纵或欺骗的可能性。对 于多个候选选项的社会选择过程，个体可能会有动机通过改变自己的 选择来影响最终的集体决策结果，这可能导致不公平或非最优的结果。
7.5.2.3 扭曲
投票者的偏好通常被认为是通过效用函数来表示的，效用函数为不同的选项分配数值，以表明一个人对某种可能结果相比另一种结果
更喜欢的强度。虽然这种基本的效用结构很少有争议，但社会选择理 论中的主要挑战是从参与者那里获取的偏好信息有限；尤其是，他们 通常被要求提供对不同结果的顺序偏好排名。这主要是由于认知原因，因为这样的比较排名更容易提供，而不是一个数字效用结构。由于偏 好的有限表达性，不可避免地导致信息的丢失。考虑社会福利最大化，即所选结果的个人效用总和，我们如何才能做出正确的选择呢？如下 面的例子所示，有些情况下我们无法做到这一点。考虑一个简单的情 景，有两个结果 a 和 b。参投票者的顺序偏好是一半喜欢 a 而不喜欢 b，剩下的一半喜欢 b 而不喜欢a。在这种情况下，仅基于这些顺序偏 好，就无法区分这两种结果，因此可以选择它们中的任何一种作为赢 家。因此，假设我们选择了结果 a 作为赢家。然而实际上一半投票者 对 ab 都不太在意的人，效用约为 1/2，而其余的投票者喜欢 b，若选 b 效用为 1，若选 a 则效用为 0。因此，参与者对获胜者 a 的总效用只 有大约𝑛/4左右，他们对 b 的效用是3𝑛/4，其中𝑛是参与者的数量。 这表明，a 显然不是最优选择，并且实际上只获得了一个与最优选择 相差 3 倍的社会福利近似。
虽然上述例子清楚地表明选择使社会福利最大化的结果并不总是可能的，但它并不能最终回答关于选择的最佳结果有多远的问题。在最坏情况分析和近似算法原则的推动下，自 2006 年以来，Procaccia和 Rosenschein[4] 提出了“扭曲”（distortion）的概念，以衡量在社会选择中总体基本目标的最坏情况恶化。我们将从一般化的社会选择理论出发，过渡到空间中的社会选择。
首先来看一般化的社会选择理论，考虑之前提及过的多数投票规则，Caragiannis 和 Procaccia 表明[5] ，该规则具有𝑂(𝑚2)的扭曲，其中𝑚为候选者的数量，这个界限后来被证明在所有确定性投票规则中是最好的[6] 。而另一种熟知的投票规则 Borda Count，该投票规则被证明为扭曲是无界的[4] 。随机化已被证明是一种强大的可用于改进
扭曲边界的方法，随机规则输出概率分布而非单一结果，是基于社会福利的期望的。Boutilier 等人[7] 对随机规则的扭曲进行了研究，他们设计了一种特殊的扭曲投票规则可达到𝑂(√𝑚 ∙ 𝑙𝑜𝑔∗𝑚)。此外，他们还提出了一个更简单的规则，可实现了𝑂(√𝑚 ∙ 𝑙𝑜𝑔𝑚)：以 50%的概率随机选择一个候选者，并以 50%的概率根据调和评分(1, 1/2, . . . , 1/𝑚)来进行选择。
当来到社会选择进入到空间中后，使用度量空间来表示候选选项的偏好关系。度量空间是一个数学结构，用来描述候选选项之间的相对距离和偏好强度。每个候选选项在度量空间中表示为一个点，而偏好关系则由这些点之间的距离来体现。
度量社会选择的关键是要定义合适的度量准则，以衡量不同候选选项的优劣。这些度量准则可以包括距离度量、超平面分割等。通过对度量空间中的点进行度量计算，可以得出集体决策的结果，以及评估社会选择机制的性能和公平性。注意到，度量空间需满足三角不等式。同样地考虑确定性规则，度量空间中社会选择的任何确定性投票规则的扭曲至少为 3。Anshelevich 等人[8] 证明了 Copeland rule 有着 5 的扭曲。而 Ranked Pairs rule 被 Anshelevich 等人[8] 证明具有 3 的扭曲，从而匹配上了之前所提到的下界。Skowron 和 Elkind[10] 说明了 STV 方法的扭曲在𝑂(√𝑙𝑜𝑔𝑚)与𝑂(𝑙𝑜𝑔𝑚)之间。若在度量空间中考虑随机机制，如 Random Dictatorship（随机独裁机制），该规则被 Anshelevich 和 Postl[11] 证明具有3 − 2/𝑛的扭曲。随后，Kempe[12] 设计了一种具有3 − 2/𝑚扭曲的规则，当𝑛大但𝑚较小时，表现将好于随机独裁机制。虽然大部分工作一般输入完整的排名，但是也有一些工作考虑不完整的顺序信息[13] -[14] 。该方向也出现了一些有趣的机制，如 2-Agree 机制：随机询问投票者最喜欢的候选者，直到两名投票者的意见一致，在某些情况下，该机制会比之前所有的机制的表现更优。
在上述大多数情况中，假设是当代理被要求提交他们的顺序偏好
排名时，他们会诚实地如实表达。然而，在很多情况下，代理人可能会有动机错误地报告他们的偏好，以获得更有利的结果（例如选择更受欢迎的选项或分配更有利的资源）。在这种情况下，我们希望设计出不会激励这种行为的规则，这种属性通常被称为"Strategy-proof"
（诚实性），它是社会选择理论中的一个重要概念，指的是一个社会 选择机制在选民对自己的偏好进行报告时，无论其选择如何，都不能 通过不诚实的策略来改变个体的最终结果。简而言之，一个诚实性的 社会选择机制意味着选民不需要考虑欺骗性的投票策略，而只需要按 照自己的真实偏好进行投票。选民可以坦诚地报告他们的偏好，而不 必担心这会对最终结果产生不利影响。这种特性使得诚实性成为一个 重要的社会选择准则，因为它鼓励选民坦诚地表达自己的意愿，从而 确保最终结果更加公正和准确。一个社会选择机制如果满足诚实性，那么选民不会从提供虚假或欺骗性的信息中获得任何好处。换句话说，选民不会因为改变他们的投票策略而改变最终的集体决策结果。这样 的机制可以减少个体的不确定性和战略性行为，促进更真实的投票结 果。然而，实现诚实性并不总是容易的，尤其是在具有复杂偏好和多 个候选选项的情况下。一些经典的社会选择机制，如多数规则和 Borda Count，在某些情况下可能不满足诚实性，因为选民可能会采取策略 性的投票来影响最终结果。针对真实机制的研究，目前也有着一些工 作[15] -[17] 。