羽毛球假球事件

体育精神是一回事，比赛机制的确也有问题
SO a bad mechanism could lead to a bad result.
所以NBA 季后赛（playoffs）是强队打弱队。

---

🏀 为什么 NBA 季后赛强队打弱队？

1. 根本原因：奖励强队（Rewarding performance）

NBA 常规赛（82 场）结束后，战绩越好，排名越高。
季后赛规则是：

$$\text{第1名对第8名},\text{第2名对第7名},\text{第3名对第6名},\text{第4名对第5名}.$$

这样做的“为什么”很简单：

常规赛表现好的球队应该得到奖励
因为他们整个赛季表现稳定、努力、强。

这是一种 激励机制（incentive mechanism）：
你越努力，季后赛首轮越轻松。

---

2. 这样做的好处

（1）让常规赛更有价值

如果排名不重要，球队可能会摆烂、轮休、乱打。
现在每场常规赛都重要，因为高排位意味着更容易赢季后赛。

现实类比：
就像考试排名靠前的学生在选课或选宿舍时有优先权。

---

（2）保持季后赛的公平（Fairness）

强队与弱队交叉对位，让整体对阵更合理。
否则如果随机对阵，可能出现两支冠军热门球队在首轮互相淘汰，整体不公平。

---

（3）增加观赏性与商业价值

强队一般明星更多、关注度更大，
让他们更可能进入后几轮，能保证收视率与票房。

这和世界杯也类似：
强队不会在小组赛就互相打得你死我活。

---

3. 这是一种典型的“机制设计（Mechanism Design）”

用经济学语言解释更有趣：

NBA 的排位系统就是一个机制（mechanism），
它想实现的社会目标是：

$$\text{让表现最好的球队更有机会走得更远}.$$

为了实现这个目标，NBA设计了：

• 明确的规则（ranking rule）

• 激励方式（reward for high performance）

• 对阵安排（strong vs weak）

这和拍卖机制、资源分配机制的设计思路类似。

---

4. 如果强队不打弱队，会发生什么？

如果季后赛完全随机对阵：

• 常规赛就变得不重要

• 球队会更频繁摆烂

• 球迷会觉得“不公平”

• 商业价值会下降

• 首轮可能就“冠军热门互相淘汰”

---

What Mechanism Design Is Trying to Accomplish (Explained with MathJax)

1. The Situation

Mary wants to sell a vase to either Ann or Bob.
Each person has a private valuation:

• Ann’s valuation:
  $$v_A$$

• Bob’s valuation:
  $$v_B$$

These valuations are private information — Mary does not know them.

---

2. Mary’s Objective: A Social Choice Function

Mary wants the vase to go to the person who values it the most.
Formally, her desired social choice function is:

$$f(v_A,v_B)=\{\begin{array}{ll}A,& \text{if }{v}_A\ge v_B,\\ B,& \text{if }{v}_B>v_A.\end{array}$$

So she wants to choose the agent with the highest valuation.

---

3. The Challenge: Valuations Are Unknown

Because Mary cannot observe $$v_A$$ and $$v_B$$,
she cannot directly compute:

$$f(v_A,v_B).$$

She needs Ann and Bob to reveal their valuations.

But they may lie if lying helps them get the vase cheaper.

---

4. The Goal of Mechanism Design

Mechanism design asks:

Can we design a protocol that makes Ann and Bob reveal their valuations truthfully so the vase is allocated efficiently?

A mechanism consists of:

• A message space (what Ann and Bob can report)
  $$M_A,M_B$$

• An allocation rule
  $$x(m_A,m_B)$$

• A payment rule
  $$p_A(m_A,m_B),;p_B(m_A,m_B)$$

The mechanism should implement the social choice function:

$$(x,p)\text{ implements }f\text{if truthful reporting is optimal and }x(v_A,v_B)=f(v_A,v_B).$$

This is the core idea.

---

5. What the Slide Means (In Plain English)

• Mary wants efficiency: sell to whoever values it more.

• But she lacks the necessary information.

• So she defines the desired rule (“allocate to highest valuation”).

• Then she designs a mechanism so that, for any possible valuations, truthful behaviour leads to the desired outcome.

This is exactly what auctions such as the Vickrey second-price auction are designed to achieve.

---

What is Mechaism Design trying to accomplish

---

📘 机制设计到底想解决什么问题？

1. 固定一组可能的结果

设一组可能的结果集合为：

$$O=o_1,o_2,\dots ,o_m.$$

例如：
给一个物品，可以选择把它分配给 Ann、Bob、或者不卖，这些都属于可能结果。

---

2. 给定玩家的偏好（preference profile）

每个玩家 ( i ) 都有自己的偏好顺序：

$${⪰}_i$$

整组偏好称为偏好型谱（preference profile）：

$$({⪰}_1,\dots ,{⪰}_n).$$

在这些偏好下，有些结果比其他结果更“好”，即更符合社会目标。

例如：
把物品给价值最高的人，就是更好的结果。

设“理想结果集合”为：

$$O^{\ast }\subseteq O.$$

---

3. 问题在于：玩家的偏好是私人信息

设计者不知道：

$${⪰}_1,\dots ,{⪰}_n.$$

玩家可能撒谎，因为真实偏好可能不符合他们的利益。

---

4. 机制设计想解决的核心问题

设计一个游戏规则（机制），让玩家按照自己利益最大化的方式行动时，游戏的结果刚好落在我们想要的 (O^*) 中。

形式上：

• 机制定义一个 game form（博弈形式）

• 玩家按某个固定的解概念（solution concept，例如纳什均衡）来行动

• 态得到的均衡结果等于我们希望的社会理想结果

数学地写：

对于所有可能的偏好型谱
$$({⪰}_1,\dots ,{⪰}_n),$$
机制在所选解概念下产生的结果属于
$$O^{\ast }.$$

---

🔍 简单总结一句话

机制设计的目标是：
在不知道玩家真实偏好的情况下，设计一个游戏，让玩家“自发地”按照机制想要的方式行动，从而实现我们期望的社会结果。

---

P6 Strategic Behavior and the Importance of Truthfulness

C. L. Dodgson （👉 /ˈdɒdʒ.sən/ in phonetic symbols (British English)） is actually the real name of Lewis Carroll, the famous author of Alice’s Adventures in Wonderland.

Full name: Charles Lutwidge Dodgson (1832 – 1898)

He was:

🧮 A mathematician and logician at Christ Church, Oxford

✍️ A writer and photographer

🧠 One of the early thinkers in voting theory and social choice theory

In fact, beyond his children’s stories, Dodgson wrote several mathematical papers on how to make fair group decisions — what we now call collective decision-making or voting systems.

Mechanism Design and MAS

---

🧠 为什么机制设计适合多智能体系统？

1. 多智能体系统中的基本假设

在 MAS 中，我们通常假设每个智能体：

• 自利（self-interested）：
  智能体会选择让自己收益最大的行动。

• 自主（autonomous）：
  智能体并不会完全按照设计者写好的“规则”执行，而是根据自身目标做决策。

• 信息不透明（information asymmetry）：
  每个智能体的偏好、成本、收益都是私有信息。

这和经济学中的人类决策高度相似。

---

🔧 2. 为什么不能简单“写程序让它们合作”？

因为如果智能体是理性自利的，它们会选择 最大化自身收益 的行为，而不是你希望的行为。

例如：

• 你希望它报告真实价值
  但它可能撒谎。

• 你希望它合作
  但它可能背叛。

• 你希望它遵守协议
  但它可能破坏协议获取更多好处。

这意味着：

传统的算法控制方法（assume agents obey the code）在自利代理中完全失效。

---

🎯 3. 机制设计在 MAS 中的作用

机制设计的目标用一句话概括就是：

在不信任智能体、不掌握它们真实偏好的条件下，通过设计规则，让智能体“即使出于自利，也会做出对系统有利的决策”。

用数学语言：
设计一个机制 ( M )，使得真实偏好是智能体的最优策略。

$$\text{Truthful reporting is a dominant strategy.}$$

或者使得系统运行的均衡结果达到预期：

$$\text{Equilibrium}(M)\in O^{\ast }$$

即便代理自利。

---

🚦 4. MAS 情境举例（更贴近 AI）

（2）多机器人资源共享（Robotic Resource Sharing）

每个自动驾驶汽车都想尽快使用充电桩。
如果没有合适的，它们可能会抢占、不让位、甚至撒谎。
例如并不紧急，然而撒谎说没电了，亟需充电。
或者明明一会儿就充好了，但是预约一整晚的充电。。。

---

📌 一句话总结

在多智能体系统中使用机制设计，是因为每个智能体是自利的、自主的，有私有信息，而且不会按照你写好的程序 obediently 行动。

机制设计的任务，就是在这种情况下，通过设计激励与规则，让自利行为自动导向系统整体目标。

---

📝 总结一句话

Dodgson 的意思是：

不要让制度变成“谁更会玩策略谁就赢”。
要让制度反映“真实偏好”本身。

机制设计恰恰就是在解决这个问题：
构造机制，使得即便玩家是自利的、策略性的，说真话也最划算。

1️⃣ “不用担心”的真正含义是什么？

你之前的问题可以形式化成：

会不会存在某个 非真实 机制，比所有 激励相容（truthful） 机制表现更好，所以我们只研究真实机制是“吃亏”的？

机制设计的标准答案：

不用担心。
因为根据 揭示原理（Revelation Principle）：

任何通过某个（可能要求撒谎的）机制在均衡上能实现的社会选择函数，都可以通过一个直接揭示机制（direct revelation mechanism）、而且是真实汇报为均衡策略的方式来实现。

也就是说：
在“可实现什么结果”这一点上，允许撒谎的机制并不比真实机制更强。

---

📌 Strategic Behavior and the Importance of Truthfulness

Borda 规则是一种投票（preference aggregation）方法，用来根据选民的排序偏好选出一个赢家。

核心思想：

排序越靠前，得分越高；排序越靠后，得分越低。
最终总得分最高的选项获胜。

---

🧮 Borda 计分方式（标准版）

假设有 ( m ) 个候选项。

• 排名第 1 的得 ( m-1 ) 分

• 排名第 2 的得 ( m-2 ) 分

• 排名第 3 的得 ( m-3 ) 分

• …

• 排名最后的得 (0) 分

数学描述：

如果选民 (i) 的排序为：

$$a_1\succ a_2\succ \cdots \succ a_m,$$

则候选人 (a_k) 的得分为：

$$\text{BordaScore}(a_k)=m-k.$$

所有选民的得分相加，总分最高者获胜：

$$\text{Winner}=\arg \underset{a}{\max }\sum _i{\text{BordaScore}}_i(a).$$

---

---

📌 Borda 规则为什么会鼓励玩家撒谎？

这张幻灯片展示了：
在 Borda 计分规则 下，玩家 3 通过谎报偏好可以让结果变得更符合自己的利益。

---

1. 左边是三位玩家的真实偏好

玩家 1：
$$a\succ b\succ c\succ d$$

玩家 2：
$$a\succ b\succ d\succ c$$

玩家 3：
$$d\succ c\succ b\succ a$$

按照 Borda 规则（名次越靠前得分越高），
计算总分后赢家是：

$$a\text{(总分 6 分)}$$

---

2. 右边：玩家 3 改变了自己的排序（谎报）

玩家 3 把自己的排序改成：

$$b\succ c\succ d\succ a$$

重新计分后赢家变成：

$$b\text{(总分 7 分)}$$

---

3. 为什么这表示“撒谎更好”？

如果玩家 3 的真实偏好是：

$$d\succ c\succ b\succ a$$

那他明显更喜欢 b 胜出 而不是 a 胜出。

因此：

玩家 3 通过谎报偏好得到了更喜欢的结果。

即：Borda 规则不是“激励相容”的，会鼓励玩家进行策略性投票。

---

📌 结论（slide 原话的意思）

如果玩家 3 的真实偏好是左图那样，
那他确实更应该撒谎，因为谎报会带来更好的结果。

---

下面用**特朗普（Trump）和希拉里（Hillary Clinton）**的例子，来解释这张关于 社会选择函数（Social Choice Function） 和 战略博弈形式（Strategic Game Forms） 的幻灯片内容。
会非常直观。

---

🇺🇸 用“特朗普 vs 希拉里选举”解释幻灯片

假设一个国家要在 特朗普（T） 和 希拉里（H） 中选择一位总统。
选民作为“agent”，每个人都有一个 偏好排序。

---

---

P8

---

🇺🇸 Florida 2000（简化版）发生了什么？

这个例子展示：
在多数制（Plurality Voting）下，一个本不应该赢的人可能会因为“分裂票”（vote splitting）而获胜。

这是为什么投票机制不是一个“简单问题”。

---

🗳️ 三个候选人

• Bush（共和党）

• Gore（民主党）

• Nader（绿党）

---

📊 各类选民的偏好（排序）

比例	排序（从喜欢到不喜欢）
49%	Bush > Gore > Nader
20%	Gore > Nader > Bush
20%	Gore > Bush > Nader
11%	Nader > Gore > Bush

解读：

• 首先有 49% 是坚定共和党：喜欢 Bush，讨厌 Nader。

• 有 40%（20% + 20%） 真心喜欢 Gore。

• 有 11% 真心投 Nader，但 第二选择是 Gore。

---

🔍 关键点：多数人最喜欢 Gore，但 Gore 却输了！

统计 “谁比谁更受欢迎”：

Gore vs Bush

• 喜欢 Gore 的人：20% + 20% + 11% = 51%

• 喜欢 Bush 的人：49%

Gore 实际上是多数人心中的第一或第二选择。

Gore vs Nader

• Gore 胜过 Nader：49% + 20% + 20% = 89%

Gore 明显是 Condorcet Winner（康多塞赢家）：
即 在一对一对比中，Gore 战胜所有候选人。

---

⚠️ 但实际投票使用的是“单选多数制（Plurality Voting）”

每个人只能选 第一名。

于是实际票数：

• Bush：49%

• Gore：20% + 20% = 40%

• Nader：11%

结果：

Bush 赢了（49%）

即便 51% 的人更喜欢 Gore 超过 Bush。

---

🎯 问题的本质：Nader 的存在“分裂”了亲 Gore 阵营

如果投 Nader 的 11% 里有一小部分人作策略性投票（把票投给 Gore），结果会反转。

这就是 战略行为 会出现的原因：

理性的 Nader 支持者应该知道自己喜欢的 Nader 注定赢不了，
因此投给第二偏好 Gore（战略投票）可以避免最讨厌的 Bush 当选。

这个例子说明：

• 投票机制可能让较受欢迎的候选人输掉选举

• 选民可能需要“撒谎”才能让结果更符合自己偏好

• 选举不激励真实偏好汇报

这正是机制设计关注的问题。

---

📌 总结一句话

在 2000 年佛罗里达州选举中，
虽然多数选民最喜欢 Gore，
但由于“票源分裂”“战略投票”和多数制的缺陷，
结果却是 Bush 获胜。

这是一个投票机制容易被操控、无法真实反映民意的经典案例，用来说明：

设计一个好机制真的不是小问题（not a trivial problem）。

---

P9

---

🧠 投票理论（Voting Theory）为什么和 AI 相关？

幻灯片想表达的是：

投票理论不仅仅用于政治选举，它在 AI 中有大量自然的应用场景。
因为很多 AI 问题都需要“把多个意见、多个评分、多个智能体的决策汇总成一个输出”，
这本质就是“投票”。

以下逐点解释：

---

1️⃣ 搜索引擎（Search Engines）

搜索引擎需要确定：

• 哪些网页更重要？

• 多个搜索引擎的结果如何合并？

这其实是把每个网页的“被引用次数”当作选票。

例子：

• Google 的 PageRank 把每个超链接视为对网页的一票。

• 元搜索引擎（meta-search engines）要合并 Google、Bing、Yahoo 的排名 → 这是 rank aggregation → 标准投票问题。

---

2️⃣ 推荐系统（Recommender Systems）

推荐系统要根据其他用户的评分决定：

• 推荐哪个电影

• 推荐哪个商品

不同用户给出不同评分、排序 → 本质就是：

“把多个用户的偏好合并成一个系统推荐”。

例子：

• Netflix：把成千上万用户对电影的打分视为“投票”，合并成推荐结果。

• 淘宝/京东：把用户对商品的点击、聊天、浏览行为合并成商品排序。

---

3️⃣ 多智能体系统（Multiagent Systems）

多个自主软件智能体（agents）必须 协调决策。

例如：

• 多机器人投票选出最佳路线

• 多无人机投票决定哪一个目标优先

• 多个 AI agent 合作解决任务，需要“共同决策”

这就是：

“几个智能体各有计划，怎么通过投票得到联合行动？”

典型例子：

• 多智能体路径规划（每个 agent 投票选下一个行动）

• 机器人团队选择 leader

• 多智能体 RL 中 policy ensemble → “哪个 Q 函数说得算？”

---

4️⃣ AI 竞赛（AI Competitions）

AI 比赛需要评估：

• 哪个交易 agent 最好？

• 哪个 SAT solver 最强？

• 哪个 RoboCup 团队最厉害？

每个测试集、每场比赛、每个 judge 都给一部分信息。
最终需要“投票”决定冠军。

例子：

• Kaggle 竞赛的 leaderboard 合并多个 test case 的结果

• RoboCup 裁判系统：多个评分指标需要合并成最终得分

---

总结

AI 中“把多个模型、多个评分、多个 agent 的意见合并成一个决策”就是投票问题。
因此投票理论对 AI 极其重要，且需要新的投票模型来适应 AI 的复杂性。

---

P10

🧠 Voting Theory and AI (2) — “反向”关系

这页幻灯片要表达：

不仅 AI 会使用投票理论，
投票理论本身也可以从 AI 技术中获益。

换句话说：
AI ↔ Voting Theory 是双向促进的关系。

---

1️⃣ Algorithms and Complexity（算法与复杂性）

AI 和计算复杂性理论可以帮助：

• 为复杂的投票机制设计更快的算法

• 分析某些投票规则是否 NP-hard、是否难以计算

• 判断选举操控（manipulation）是否在计算上可行/困难

例子：
计算 STV 赢家是 NP-hard → 这会减少操控的可能性。

---

2️⃣ Knowledge Representation（知识表示）

很多投票场景有巨大候选空间（例如推荐商品 10 万个）。
AI 的知识表示研究可以帮助：

用更紧凑方式表示选民偏好，减少存储和计算成本。

例子：
使用 CP-nets、逻辑表达式、多属性偏好模型来表示偏好。

---

3️⃣ Logic and Automated Reasoning（逻辑与自动推理）

AI 中的逻辑推理工具可以：

• 形式化表达投票规则

• 自动验证投票规则是否满足某些公理（公平性、无操控性）

• 甚至自动发现新定理

例子：
自动证明工具（如 SMT solver）被用来验证投票机制满足 strategy-proof 性。

---

📌 总结一句话

AI 不仅使用投票模型，
AI 技术也反过来推动投票理论：
更好的算法、更强的偏好表示、更自动化的理论证明工具。

P13

P15

---

1️⃣ “单选多数制只看第 1 名，把大量偏好信息忽略了”

Plurality rule：每个选民只能投给 第一名。

问题：

• 40%（两个 20%）喜欢 Gore

• 11% 喜欢 Nader，但第二选择仍是 Gore

换句话说：

51% 的选民都更喜欢 Gore 胜过 Bush。

但因为 plurality rule 只看“第一名”，
40% 的 Gore 支持 + 11% 的 Nader 支持无法合并。

🔍 所以 Gore 的强大二选偏好信息被完全忽略了。

---

2️⃣ “意识形态相近的候选人会分裂票源”

Gore 和 Nader 的政治立场接近：都偏左。

结果：

• 20% 给 Gore

• 20% 给 Gore

• 11% 给 Nader

本来这 51% 都是 反 Bush 阵营。
但 plurality rule 把这 51% 分成：

• 40% 投 Gore

• 11% 投 Nader

于是接近的候选人 Gore/Nader 分裂票源，
让对立的 Bush（49%）反而赢了。

这对应 slide 第二点：

Dispersion of votes across ideologically similar candidates.

用人话讲就是：

同阵营的候选人会把票互相吃掉，导致敌人获胜。

---

3️⃣ “选民被迫不投自己最喜欢的人，要进行战略投票”

看看 Nader 的 11%：

他们真实排序是：

$$\text{Nader}>\text{Gore}>\text{Bush}$$

但他们知道：

• Nader 不可能赢

• 投 Nader 会帮助 Bush 赢

• 而 Bush 是他们最讨厌的

所以 理性策略投票是投给 Gore：

“投给我最喜欢的 Nader = 浪费票 → 反而让 Bush 赢。”

这对应 slide 第三点：

Encourages voters not to vote for their true favourite.

佛罗里达 2000 恰恰说明这一点：

如果 Nader 支持者策略性地投给 Gore，Gore 很可能赢得佛州，也就赢得整个美国大选。

---

⭐ 总结（用一句话）

佛罗里达 2000 清晰地说明：

Plurality Rule 会把二选偏好忽略、分裂同阵营票源，并且迫使选民进行策略投票。
结果是：
一个多数选民不喜欢的候选人（Bush）反而因为投票机制缺陷而获胜。

---

P16

---

📌 Plurality with Run-Off（多数制 + 第二轮决选）是什么？

流程：

1. 第一轮：每个选民只投一票（普通 plurality rule）。

2. 只保留前两名。

3. 第二轮：让选民在这两个候选人之间再次投票。
   多数获胜。

法国总统选举就是这样做的。

---

📌 这个制度如何解决单选多数制的一些问题？

（1）避免票源分裂（vote splitting）

佛州 2000 的问题是：

• Gore（中左）

• Nader（左）

把左派票源分裂成：

• Gore：40%

• Nader：11%

导致 Bush（右 49%）“捡漏”。

在 plurality with run-off 下：

第一轮：

• Bush：49%

• Gore：40%

• Nader：11%

❗ 前两名是 Bush 和 Gore

第二轮：

所有 Nader 支持者最终会投给 Gore：

“Nader > Gore > Bush”

所以第二轮票数：

• Bush：49%

• Gore：51%（40% + 11%）

➡ Gore 赢！

这避免了“本应获胜的 Gore 因票源分裂而输掉选举”的情况。

---

📌（2）让“第二偏好”更有影响力

在佛州例子里：

11% 的人真实偏好是：

$$Nader>Gore>Bush$$

在第二轮，他们的偏好就能直接影响结果（投 Gore）。

这就是 slide 说的：

realistic “second best” candidate gets another chance.

Gore 虽然不是这 11% 的 top choice，但至少是 second best。

---

📌（3）第二轮能收集更多偏好信息

Plurality（单轮）只知道“第一名是谁”。
而 run-off 机制能通过第二轮抓住“谁对多数人更可接受”。

佛州第二轮就是一个“信息补充”。

---

📌 那为什么仍然被批评（例如 2002 法国 Le Pen 事件）？

法国 2002：

• 右翼极端候选人 Jean-Marie Le Pen 侥幸进入第二轮

• 因为左派票源在第一轮严重分裂（多个左派候选人）

• 导致本应进入第二轮的 moderate 左派候选人被淘汰

这说明：

第一轮仍然存在票源分裂问题，一旦结果进入第二轮就无法修复。

也就是说：

• run-off 可以修复“第二轮中的偏好”，

• 但不能修复“第一轮中错误淘汰了一个很有竞争力的候选人”的情况。

佛州虽然第二轮能救 Gore，但 在 run-off 制度中如果 Gore 和 Nader 的票再分得更散，Gore 也可能进不了前两名。

---

⭐ 用一句话总结

Plurality with Run-Off 能解决部分票源分裂问题，并让“第二偏好”发挥作用，但第一轮仍可能淘汰真正受欢迎的候选人。
就像法国 2002 那样。

---

P19

📣 Condorcet 的英文发音

/kɒnˈdɔːrseɪ/
或更常见的学术发音：# 📌 Condorcet 是谁？

法国启蒙时代的数学家与政治思想家

1️⃣ 法国大革命前的政治关切

孔多塞是启蒙时代的政治思想家，他面对的问题是：

“如果我们想让公民通过投票决定国家大事，
那么投票结果真的能代表多数人的真实意愿吗？”

当时议会和委员会要频繁表决，
但人们发现结果经常不合理、不一致、不公平。

孔多塞希望找到：

• 公平

• 一致

• 理性

• 不会被策略操控

的投票制度。

所以他把投票当成一个数学问题来研究。

P21

Yes — according to Condorcet’s own philosophy and mathematical reasoning,
the Condorcet winner is the best candidate（在他的定义下最合理的赢家）。

---

✅ Why did Condorcet think the Condorcet winner is the best?

Condorcet 的逻辑非常简单：

如果一个候选人能够在“一对一”的比较中击败所有其他候选人，
那么这个人应该是最受多数人支持的。

这是因为：

• 一对一对比不会受到“第三候选人”干扰

• 多数胜多数 → 最直接反映选民的真实偏好

• 比“只看第一选择”的制度更稳健

• 比 Borda rule 更少策略性

他认为：

成对比较（pairwise majority）是最基本、最公平的多数原则。

所以，如果一个候选人能在所有 pairwise 比较中获胜，那么：

他在所有候选人中最能代表“多数人的意愿”。

---

🏆 Condorcet winner = 最能打败所有人

你可以把 Condorcet winner 视为：

“循环赛冠军”
——无论对手是谁，他都赢多数票。

这是一种非常强的胜利概念。

---

📌 关键点：Condorcet 认为这是“最稳定的”赢家

他给出理由：

1. 不会因为加入/移除某个候选人而改变胜者
   （满足 Independence of Irrelevant Alternatives 的一种强形式）

2. 对 pairwise 多数胜利的尊重，是民主最基本的原则

3. 如果 Condorcet winner 存在，它比 plurality/Borda/STV winner 更有民主正当性
   因为多数偏好是一切民主制度的核心。

---

⚠ 但是：Condorcet 也知道 Condorcet winner 并不一定存在

这就是著名的 Condorcet paradox（Condorcet 悖论）：

$$A>B,B>C,C>A$$

群体偏好可能不具有传递性。

所以他提出：

• 如果 Condorcet winner 存在 → 应该选它（最好）

• 如果不存在 → 需要其他 tie-breaking 方法

但只要它存在，他认为：

Condorcet winner 是最“民主合理”的选举结果。

---

⭐ 一句话总结

Yes.

Condorcet 认为 Condorcet winner 是在所有逻辑上最能代表多数意愿、因此最好的赢家。

是的，这个例子非常经典，它清楚地说明了投票制度的根本局限性：

即使每个人的偏好都非常理性、传递、完整，
群体的总体偏好却可能变得“不理性”和“自相矛盾”。

这就是 Condorcet Paradox（孔多塞悖论）。

下面用你的例子逐步解释。

---

🟩 例子回顾：三个人、三候选人

Ann：
$$A>B>C$$

Bob：
$$B>C>A$$

Cesar：
$$C>A>B$$

每个人的偏好都是“理性”的（严格、传递）。

---

🟥 但多数投票比较的结果是循环的（不理性）

我们做 pairwise majority votes：

1️⃣ A vs B

• Ann：A > B

• Bob：B > A

• Cesar：A > B

多数：A 胜 B

---

2️⃣ B vs C

• Ann：B > C

• Bob：B > C

• Cesar：C > B

多数：B 胜 C

---

3️⃣ C vs A

• Ann：A > C

• Bob：C > A

• Cesar：C > A

多数：C 胜 A

---

🔥 结果是一个循环：

$$A\succ B,B\succ C,C\succ A$$

这违反了最基本的传递性（transitivity），因此很“不理性”。

---

⭐ 这个例子揭示的投票制度局限性（核心结论）

P23 Copeland Rule

🟢 Copeland Rule 是什么？

核心一句话：

对每位候选人，计算他在 pairwise 一对一比较中赢了几次、输了几次，然后：
选“赢−输”最大的候选人。

数学上：

若候选人 x 的分数为：

Copeland(x)=#wins(x)−#losses(x)

平局（tie）一般算 0 或 0.5（视具体版本）。

🟧 Copeland rule 的优点

• 只要 Condorcet winner 存在，一定会被选出
  因为它会有最多的 pairwise 胜利数（全部胜）

• 容易计算

P24

---

🟢 1. 什么是 “tournament”？

在投票理论中，如果我们把所有候选人两两比较一次，就得到一个图：

• 节点：候选人

• 有向边：pairwise 多数胜者

  • 如果多数选民认为 (A) 比 (B) 好，就画一条 (A \to B)

这样，你就得到了一张有向图。

⚠ 特点：

• 任意两个不同节点之间 一定有一条边（A > B 或 B > A）
• 而且 方向唯一（没有平局）

这正是图论里的 tournament graph（锦标赛图）。

就像足球循环赛：
每两支队伍一定打一次，每场都分胜负。

---

🟡 2. “Tournament solution” 是什么？

既然 pairwise majority 形成了一张锦标赛图，
那么我们可以把“找赢家”这个问题理解为：

在一张锦标赛图里，选一个最合理的“冠军”。

任何从 tournament graph 中选出 subset / winner 的方法，
就叫 tournament solution。

例如：

• Copeland rule：数每个节点胜了几场、输了几场，选赢−输最大者。
• Top cycle（Smith set）：找所有能到达其他候选人的强连通集合。
• Uncovered set
• Slater rule
• Banks winner
  等等。

它们统称为：

tournament solutions（锦标赛解）
因为它们都把社会偏好看成一场“循环赛”，然后决定冠军。

---

P25 Kemeny Rule

下面给你一个清晰、直观、立即能懂的解释：
Kemeny rule 到底是什么？为什么这么定义？怎么理解步骤(1)？

---

🟢 1. Kemeny rule 的核心直觉（一句话）

找一条“最接近所有选民偏好”的社会排序（ranking），
然后选出该排序里排在最前的候选人。

“最接近”=
与所有选民在候选人对比上产生的总“冲突”最少。

数学上，它是求一个 最小总 Kendall tau distance 的排序。

---

---

🔵 3. 步骤解释（用你提供的定义）

原文说：

For every possible ranking ®, count the number of triples ((i, x, y))
such that ® disagrees with voter (i) on the ranking of (x) and (y).

翻译成直白中文：

步骤 1：枚举所有可能的“社会排名” ®

例如：
(A>B>C),
(A>C>B),
(B>A>C),
…（所有排列）

步骤 2：对于每个社会排名 ®，计算“与它不一致的 pairwise 对比”次数

如果某个选民 (i) 说 (x>y)，
但社会排名 ® 说 (y>x)，
那么就算 1 次“冲突”（disagreement）。

把所有这样的冲突加起来，就是 ® 的 total disagreement score。

步骤 3：找出 disagreement 总数最少的那些排名 → 最接近所有选民的排序

这些就是 Kemeny rankings。

步骤 4：选该排名中排第一的候选人 → Kemeny winner

---

🔴 4. 用一个简单例子立刻理解

假设 3 个选民，3 个候选人 (A, B, C)：

• 选民 1： (A>B>C)

• 选民 2： (A>C>B)

• 选民 3： (B>A>C)

我们查看某个候选社会排名，例如：

排序 1：

$$A>B>C$$

与每个选民进行 pairwise 比较：

• 对比 A vs B：

  • 选民 1: A>B（同意）

  • 选民 2: A>B（同意）

  • 选民 3: B>A（冲突 1 次）

• 对比 B vs C：

  • 选民 1: B>C（同意）

  • 选民 2: C>B（冲突）

  • 选民 3: B>C（同意）

总冲突：2 次。

同样计算其他排序：

• (A>C>B)

• (B>A>C)

• (B>C>A)

• (C>A>B)

• (C>B>A)

最后找到总冲突最少的那个。

比如如果 (A>B>C) 产生 2 次冲突，而其他排序产生 3 次或更多冲突，
那 Kemeny rule 就选：

A（因为它在最优排序中排第一）

---

🟣 5. 简单总结

Kemeny rule 就是：

• 看所有候选人对比

• 找出一个社会排序，使得“不同意的人最少”

• 排在这个排序最前面的候选人获胜

它是一种严肃的“集体一致性”度量，
在理论上非常合理，被许多人认为是最佳的排名方法。

---

P30 Summary

下面用非常清晰、简短、课堂友好的方式解释这三个 voting procedure 的性质：

---

🟢 1. Monotonicity（单调性）

❗ 含义（简单定义）

如果一个候选人因为选民的投票被排得更高（更受支持），
那这个候选人不应该因此变得更不可能获胜。

也就是说：

你越支持某人，他不应该因此输掉选举。

❌ 违反例子：No-show paradox（不投票更好）

某些投票制度里会发生怪事：

某个选民如果来投票支持某候选人，
反而会导致该候选人输掉选举。

但如果他“不来投票”，该候选人会赢。

这违反了单调性，因为：

• 支持候选人 → 候选人更糟
• 不投票 → 候选人获胜

这完全不合理。

---

🟡 2. Strategic issues（策略性投票问题）

❗ 含义

一个好的投票制度期望选民如实投票（truthful）。

但很多制度会让选民：

为了让更喜欢的候选人赢，而不得不谎报自己的真实偏好。

例如：

• 在 plurality 多数制中，选择“不会赢的候选人” = 浪费票
  于是选民常常策略性地投给第二喜欢、但更可能获胜的人。

这导致：

选票反映的不是真实偏好，而是策略计算。

几乎所有常见制度都不免疫（Gibbard–Satterthwaite theorem）。

---

🔵 3. Condorcet principle（孔多塞原则）

❗ 含义

如果存在一个候选人能够：

在所有 pairwise（两两对比）多数投票中击败所有对手，

那么：

这个候选人应该赢得整个选举。

这个人叫 Condorcet winner。

🧠 直觉

如果选民分组两两对比，结果显示：

• A 打败 B
• A 打败 C
• A 打败 D
• …

那 A 是真正意义上“最受多数人支持”的候选人。

因此如果 A 没赢选举，制度就“不合理”。

遗憾的是：

• 有些制度不保证选出 Condorcet winner（例如 plurality, Borda rule）
• Condorcet winner 有时根本不存在（Condorcet paradox）

---

⭐ 一句话总结三个性质

性质	想保证的合理性	现实问题
Monotonicity	更多支持不能让候选人变更差	某些制度会发生 no-show paradox
Strategic-proofness	希望选民说真话	很多制度会让选民必须“策略性投票”
Condorcet principle	如果一个候选人单挑打赢所有人，他就该赢	很多制度不选 Condorcet winner；有时不存在 Condorcet winner

---

如果你愿意，我还可以：

• 给你每个性质的数学定义（MathJax）
• 展示每种制度是否满足这些性质的表格
• 解释为什么 Gibbard–Satterthwaite 定理导致“策略问题不可避免”

P34 The Axiomatic Method

下面给你最清晰、最简短的解释，让你马上能在课堂上讲出：
Voting theory 中 “axiomatic, characterisation theorems, impossibility theorems”是什么意思？

---

🟢 Axiomatic approach（公理化方法）是什么？

投票理论里，我们会先提出一些“理想性质”（axioms），例如：

• 单调性（monotonicity）
• 不可操控（strategy-proofness）
• Condorcet 原则
• 匿名性、剩余独立性等

这些性质表达了：

我们希望一个投票制度满足哪些直觉上的“公平”“合理”。

然后，我们研究：

哪些投票规则满足这些性质？
有没有可能同时满足所有性质？

这就是 axiomatic approach。

---

🟡 1. Characterisation Theorems（刻画定理）

简单理解

给出一组性质（axioms），然后证明：
只有某一种（或一类）投票制度满足它们。

形式：

“如果一个投票规则满足 A, B, C 三个性质，
那么它一定就是 xxx 规则。”

举例

May’s theorem（梅氏定理）：

在两个候选人的选举中，
如果一个规则满足：

• 匿名性（treat voters equally）
• 中立性（treat candidates equally）
• 单调性

那么唯一满足这些的就是 多数投票规则（majority rule）。

也就是说：

这些性质正好刻画了 majority rule。

---

🔵 2. Impossibility Theorems（不可能性定理）

简单理解

给出一组看似合理的性质，然后证明：
根本不存在任何投票方法能同时满足它们。

形式：

“不存在任何投票制度能同时满足 A, B, C, D。”

举例

最著名的是 Arrow Impossibility Theorem（阿罗不可能定理）：

换句话说：

不存在完美的投票制度。

再比如 Gibbard–Satterthwaite theorem：

任何合理的投票制度在某些情况下都能被策略性投票操纵。
不存在完全 strategy-proof 的制度。

---

⭐ 一句话总结整张幻灯片

Axiomatic approach：先提出投票制度应该满足的“理想性质”（公理）。

Characterisation theorems：告诉你“只有某个规则满足这些理想性质”。

Impossibility theorems：告诉你“没有任何规则能满足这组看似合理的性质”。

---

P37

🟢 什么是 Anonymous（匿名性）？

定义：

如果两个选民交换他们的选票，结果不变，那么这个投票规则是匿名的。

换句话说：

• 投票规则不关心“谁说的”

• 只关心“说了什么偏好”

• 所有选民地位完全相同（对称）

---

⭐ 为什么我们喜欢 Anonymous？（直觉理由）

1️⃣ 公平（Fairness）

如果规则依赖某些人的身份才能决定胜负，例如：

• “富人投票比穷人重要”

• “VIP 用户的票权更高”

• “某几个特定人的投票被优先考虑”

那么这个制度就不公平。

匿名性保证：

你的票和别人的票一样重要。

---

---

3️⃣ 尊重民主基本原则（Equal voice）

在民主制度里，核心理念是：

one person, one vote

匿名性是这个理念的形式化表达。

如果移除匿名性，那实际上是说：

有些人的意见比别人更重要。

这违背了民主精神。

P38

🟢 什么是 Neutrality（中立性）？

定义：

如果把所有候选人的名字换一换（A→B，B→C，C→A），投票结果也跟着对应地换一换，那么投票规则是中立的。

即：

• 投票规则不偏爱某个候选人

• 所有候选人地位对称

• 决策只取决于选民的偏好，而不是候选人的标签

---

⭐ 为什么我们喜欢 Neutrality？（核心直觉）

1️⃣ 确保制度不偏袒任何候选人

如果一个投票制度不“中立”，它可能默认偏爱：

• 某个特定人（例如候选人 A）

• 或者某个特定类别（例如把现任者总是优先）

这就像比赛规则偏向某个队一样，有违公平。

中立性保证：

在规则层面，所有候选人一律平等。

---

2️⃣ 避免“名字决定胜负”这种荒谬现象

想象一个不中立的规则：

• 只因为候选人叫 A，就自动加额外分数

• 或者“排在选票第一列的候选人永远更容易赢”

P39 Positive Responsiveness

🟢 什么是 Positive Responsiveness（正向响应性）？

定义（换成直白中文）：

如果在原来的投票结果中，x 是赢家（可能并列），然后有一个选民把 x 在她的选票里往上提（提高排名），那么 x 应该成为唯一赢家。

也就是说：

• 你把某个“赢的人”放得更高

• 结果不应该变得对他更差

• 甚至要变得更“确认他赢”

---

⭐ 为什么喜欢这个性质？

1️⃣ 保证投票制度“不会惩罚你支持某个人”

想象一个不满足正向响应的制度：

• x 原本是赢家

• 投票人更喜欢 x → 把 x 排更高

• 结果 x 却 变成不赢，甚至输掉

这非常荒谬，也会让人不敢诚实投票。

Positive Responsiveness 保证：

“更支持你的人增加了，你的胜利更稳固。”

这是非常自然的公平性要求。

---

2️⃣ 避免“支持你反而害你”这种怪事

这个性质是一个“强版的单调性（monotonicity）”：

• 单调性（monotonicity）：
  如果你升高赢家的位置，赢家不应该跌出胜利者集合。

• 正向响应性（positive responsiveness）：
  如果你升高赢家的位置，他应该成为“唯一赢家”。

也就是说：

比单调性更强、更干净的公正性要求。

---

3️⃣ 让选民在心理上更“安全地表达真实偏好”

如果一个制度不满足正向响应性，选民会担心：

• “我如果把 A放到更靠前，会不会让 A 输？”

• “我是不是反而要故意把喜欢的人排低一点？”

这会导致：

• 战略投票（strategic voting）

• 不真实的选票

P43 🟢 Reinforcement（可合并性）是什么？

定义翻译成直白中文：

如果把选民分成两个小群体，这两个小群体各自投票都会选出同一个赢家 x，那么把所有选民合在一起投票时，也应该选 x。

也就是说：

• 小组 A 的赢家：x

• 小组 B 的赢家：x

• 那么 A∪B 的赢家也应该是 x

合并不会改变结果。

---

⭐ 为什么喜欢这个性质？

1️⃣ 保证“民主一致性”

如果两个独立群体都说：

“我们都认为 x 最好。”

那合在一起不应该突然变成：

“咦，我们合体后觉得 y 更好。”

这会让制度显得不一致、不可预测。

Reinforcement 保证：

集体偏好在规模扩大时不会奇怪地反转。

---

2️⃣ 避免完全荒谬的“规模效应”

想象一个不满足 reinforcement 的制度：

• 小区 A 选出市长候选人：Alice

• 小区 B 选出市长候选人：Alice

• 全城大选结果 → 居然不是 Alice，而是 Bob

这会让人困惑甚至愤怒，因为：

所有子群体都选了 Alice，但整体却排斥 Alice。

P44 Continuity

![[CleanShot 2025-11-18 at 22.24.50.png]]
![[CleanShot 2025-11-18 at 22.24.59.png]]

P47

![[CleanShot 2025-11-18 at 22.26.36.png]]

![[CleanShot 2025-11-18 at 22.27.42.png]]
![[CleanShot 2025-11-18 at 22.27.57.png]]

![[CleanShot 2025-11-18 at 22.29.49.png]]
![[CleanShot 2025-11-18 at 22.30.01.png]]

🟣 一句话总结

IIA 要求：无关候选人的出现、消失、排序变化，都不应影响 x 与 y 的结果。

它是选举制度的一种重要“合理性要求”，但几乎所有现实使用的投票规则都违反它（包括多数制、Borda、runoff 等）。

P49

🟢 独裁投票规则（Dictatorship）

定义非常简单：

存在某个选民 d，不管其他所有人怎么投票，最终唯一的赢家永远是 d 排在第一位的候选人。

这个选民就是“独裁者”。

---

🟦 直观解释

相当于整个投票系统是：

• “看看 d 喜欢谁。”

• 然后直接宣布：“赢家就是 d 的第一选择。”

其他人的选票完全不重要。
系统只读一个人的选票。

为什么我们讨厌独裁规则（dictatorship）？

---

🟥 核心原因（一句话）

独裁规则只看一个人的偏好，忽视所有其他人的意见，因此严重不公平。

---

🟦 更细的四个理由（每条都很短）

1. 极端不公平

只听一个人投票，其余所有人的偏好全部无效。
这与“民主”“群体决策”“集体智慧”完全相反。

现实类比：
100人一起决定去哪吃饭，但永远只听小明一个人的。
显然不公平。

---

2. 完全不反映集体偏好

目标是“社会选择”（social choice），
但独裁制度实际上是“个人选择”（individual choice）。

群体意愿 → 被彻底丢弃
社会福利 → 不被考虑

---

3. 太容易被操纵

只要你控制了独裁者（贿赂 or 威胁 or影响他），
你就控制了整个选举。

P50

Arrow 定理告诉我们：

完美的投票制度不存在，只能在“不完美中选可接受的”。
![[CleanShot 2025-11-18 at 22.34.31.png]]

P52 manipulation

🟩 strategy-proof = 免疫“策略性投票”的制度

也就是 no one can benefit from strategic manipulation。

换句话说：

不管选民怎么想、怎么算，他们都无法通过撒谎（strategic behaviour）让结果更符合自己的利益。

因此：
真话永远是最优策略 → 所以叫 strategy-proof（不会被策略“攻击”的意思）。

---

🟧 为什么叫 strategy-proof？

解释名字的组成：

• strategy（策略） = 选民为了影响结果而撒谎、伪造偏好

• proof（防护、安全） = 这种制度对策略性撒谎“免疫”

就像说 “waterproof”＝防水，
那 strategy-proof＝“防策略（操纵）”。

P53

🟦 一句话总结版

不管别人怎么投，选民永远不能通过撒谎让选举结果更好。
所以说真话永远是最优策略。

P54

下面把 Gibbard–Satterthwaite 定理用人类语言讲清楚，并说明它为什么是机制设计 / 多智能体系统 / 投票理论里最重要的定理之一。

Gibbard–Satterthwaite

👉 GI-bərd SA-ter-thwait

---

🟩 先翻译定义：surjective（满射）是什么？

一个投票制度 FFF 是 surjective（满射） 的意思很简单：

每个候选人都有机会在某些投票配置下赢一次。

就是说制度不是“偏心”的，不会永远让某些候选人不可能当选。

例如：

• Borda rule → surjective

• Plurality → surjective

• “永远选 A” → 不是 surjective（因为别人永远赢不了）

这只是一个“制度不偏袒某人”的自然条件。

---

🟩 用人话说 Gibbard–Satterthwaite 定理

定理内容：

任何（1）总是选出唯一赢家（resolute）、（2）每个候选人都有机会获胜（surjective）、（3）不允许选民通过撒谎获利（strategy-proof）的投票制度，在候选人 ≥3 的情况下，必定是独裁（dictatorial）。

换成人类语言：

🟦 **如果一个投票制度没有漏洞（不能通过撒谎操纵），

又允许所有候选人都有机会赢，
又每次都选唯一赢家，
那么这个制度只能是独裁。**

也就是说：

想要一个公平、不被操纵、不偏袒、还能处理至少 3 个候选人的投票制度？不存在。
不然只能变成“听一个人的”。

这就是它震撼的地方。

这说明：

🟩 1. 无法同时得到：公平 + 无操纵 + 多选项

这为整个投票制度设计泼了一盆冷水。
任何现实制度（多数制、Borda、Condorcet…）都不可能 strategy-proof。
所以现实中 always 会发生战略投票。

---

🟩 2. 为什么机制设计需要 VCG（拍卖）等机制？

因为在更一般的偏好空间（utilities）下，可以用支付（payment）来激励说真话，例如：

• VCG 拍卖

• 二价拍卖（Vickrey）

拍卖可以 strategy-proof，但它不是“投票”，因为允许付钱。

这就是机制设计的突破。

---

🟩 3. 对多智能体系统（MAS）意义巨大

在 MAS 中，每个 agent 自利、会撒谎，所以：

不能依赖“投票”本身达到 strategy-proof。

Gibbard–Satterthwaite 告诉你：

• 不能希望 MAS 里用“投票”实现真实汇报

• 必须使用更强的机制（如拍卖、协调协议、VCG、支付、随机机制等）

🟢 Social Choice Theory 的“革命性”，相较于之前的政治与经济理论，有哪些突破？

社会选择理论（Social Choice Theory）真正的革命性在于：
它把政治、选举、民主、集体决策这些“软问题”数学化了。
在它出现之前，政治学和民主设计更多是“哲学式讨论”和“制度经验总结”，缺乏精确工具。

下面分点讲它的革命：

---

🔵 1. 从哲学讨论 → 数学定理

在社会选择理论之前：

• 古希腊以来人们讨论“什么是最好的政府形式”

• 卢梭谈“公意”（general will, the general will）

• 孟德斯鸠谈三权分立

• 孟德尔森谈投票制度

• 边沁谈效用最大化

但这些都是概念性、哲学性、定性的。

Arrow 的出现是革命性的，因为他把“一个群体如何做出合理决定”变成了数学问题，有公理、有定理、有不可避免的限制。

特别是 Arrow 1951 的结果：

没有任何投票规则能同时满足几条特别合理的公平性要求。

这等同于说：
完美公平的民主制度是不可能的（数学意义上）。
这是对政治哲学的巨大震撼。

---

🔵 2. 第一次严肃地证明了“民主制度必然有缺陷”

以前大家只是模糊觉得：

• 投票可能有悖论

• 多数可能不稳定

• 选举可能被操纵

但 Arrow 和 Gibbard–Satterthwaite 直接给出数学定理：

✔ Arrow 不可能性定理

没有一个非独裁、满足弱帕累托、满足 IIA 的投票制度。
→ 你想要的一堆“公平特性”，数学上不可能同时实现。

✔ Gibbard–Satterthwaite 定理

任何合理投票方法都可以被策略性投票操纵
除非它是独裁。

换句话：

民主制度无论怎么设计，都躲不开阴暗的一面。

这在当时是极具颠覆性的。

---

🔵 3. 让“投票制度设计”变成一个科学领域

以前：

• 投票制度是通过经验和传统决定的（英国传统、美国传统）

• 没有人知道哪个制度更好

• 没人能证明某个制度不可能满足某些标准

社会选择理论把这些变成系统性研究：

• 定义公平性公理（匿名性、中立、单调性等）

• 分类投票制度

• 比较制度的性质

• 研究操纵、循环、议程操控

• 研究社会福利函数、偏好聚合

投票制度从“玄学”变成了一门数学科学。

---

🔵 4. 引入“偏好聚合”思想：从个人偏好 → 集体偏好

社会选择理论的核心问题：

给定个体偏好，如何构造群体偏好？

这是一个跨时代的抽象，它不仅适用于选举，还适用于：

• 资源分配（福祉经济学）

• 多智能体系统（AI）

• 群体决策

• 公司治理

• 机器投票

• 大模型的 alignment（偏好对齐）

它把“投票”从政治学拓展到数学、计算机科学、经济学。

---

🔵 5. 剧烈影响现代经济学：福利经济学第二定理体系化

Arrow–Sen 体系让经济学有了：

• 社会福利函数（Social Welfare Function）

• 社会福利序（Social Welfare Orderings）

• 公平理论

• 效率与公平之间的数学关系

• 公理化的福利经济学

特别是与 Amartya Sen 的合作，使得：

经济学从“效用最大化”走向“社会公平、自由、公正”的可数学描述体系。

---

🔵 6. 将投票、政治与计算复杂度联系起来 —— 现代计算社会选择

现代 AI 和 CS（Computer Science）很多方向都建立在社会选择理论的基础上：

例如：

• 选举操纵的 NP-hard 性

• 多智能体系统（Multi-agent systems）

• 机制设计

• 资源分配算法

• LLM 的 preference alignment（偏好对齐）

特别是：

LLM alignment 本质上就是一个社会选择问题：如何把许多人的偏好合成为一个“模型偏好”。

社会选择理论提供了数学工具。

---

🟣 总结：Social Choice Theory 的革命性

用一句话：

它把民主、投票、集体选择从哲学变成数学；
把制度设计从“经验主义”变成“有定理约束的科学”。

P56

域限制（Domain Restrictions）是什么意思？为什么有用？

我们前面看到很多“不可能定理”（Arrow、Gibbard–Satterthwaite），它们都告诉我们：

只要 选项 ≥ 3，只要 所有偏好都允许出现，就不存在“完美”的投票规则。

那有没有办法绕过这些“不可能”呢？

这页 slide 的意思是：

---

✅ 1. 不可能定理默认了一个非常强的假设：Universal Domain（全域假设）

意思是：

任何偏好顺序都可能出现。
每个选民可以给候选人排出任意的线性顺序。

例如：

• A > B > C

• C > A > B

• B > C > A

• ……全部都允许

这是一个极强的设定，它让理论分析非常干净，但也让“不可能定理”容易出现。

---

✅ 2. 如果我们限制偏好的“形状”，就能避免不可能定理

slide 的第二条：

如果我们限制 domain（选民偏好/可能出现的投票 profile），就能让更多规则满足更多性质。

这叫 域限制（domain restriction）。

下面用**五个候选人 + 一个现实政治的左右谱例子（包含 Trump）**清晰展示为什么 single-peaked（单峰偏好） 在现实中“非常自然”。

---

🌈 1. 先设定一条典型的政治光谱（left–right spectrum）

例如美国政治：

Far-Left   Left   Centre   Right   Far-Right

我们选 5 个“替代项”（alternatives）：

光谱位置	候选人（示例）
Far-Left	A = Sanders
Left	B = Biden
Centre	C = Romney
Right	D = Bush
Far-Right	E = Trump

它们从左到右构成一条 线性顺序（single-peaked 的必要条件）：

$$A\prec B\prec C\prec D\prec E$$

---

🌟 2. 为什么选民偏好自然呈现“单峰”？

因为大多数人在政治坐标轴上也有自己的“peak”（最喜欢的位置）。

例如一个 偏右的选民，她最喜欢 D（Bush）。

她对于距离“自己理想点”越远的候选人越不喜欢。

---

📌 3. 举五个选民的偏好（全部都是单峰的）

选民 1（非常左）喜好顺序：

峰值是 A
离 A 越远越不喜欢：

$$A\succ B\succ C\succ D\succ E$$

这是典型单峰。

---

选民 2（偏左）峰值是 B：

$$B\succ A\succ C\succ D\succ E$$

• B 最喜欢

• 离 B 最近的 A、C 次之

• 右边 D、E 最不喜欢

仍然是单峰。

---

选民 3（中间派）峰值是 C：

$$C\succ B\succ D\succ A\succ E$$

注意：

• B 与 D 都比 A 和 E 靠近 C

• 即使 B 和 D 不在同一侧，顺序仍然呈“山峰形”

仍然是单峰。

---

选民 4（偏右）峰值是 D：

$$D\succ C\succ E\succ B\succ A$$

仍然是单峰。

---

选民 5（非常右，Trump 支持者）峰值是 E：

$$E\succ D\succ C\succ B\succ A$$

仍然是单峰。

---

🏔️ 4. 为什么这些偏好是“自然”的？

因为：

• 人在政治光谱上有“理想点”

• 越偏离自己的理想位置，越不喜欢

• 因此偏好会形成一个“峰”

• 这就是 single-peaked

特朗普支持者（峰在 E）自然会讨厌 A/B 这些左派。

---

🌟 5. 举一个不是 single-peaked 的偏好（非常不自然）

例如：

$$C\succ A\succ E\succ D\succ B$$

在光谱中 A 和 E 在 C 的两侧，选民却喜欢：

• A（左边）

• 又喜欢 E（右边）

• 又讨厌 D（明明在 E 和 C 之间）

• 又把 B 排到最后（明明在 C 和 A 之间）

像是“左右乱跳”，
非常不符合人类的政治行为模式。

这类偏好是 single-peaked 不允许的。

---

🎯 总结：为什么 single-peaked 是“自然的”？

• 人在政治谱上通常有 单一理想点

• 偏好随“距离”增加而下降

• 因此偏好呈 山峰形：单峰

• 现实政治（如美国选民分布）天然满足这一结构

• 这类限制可以让很多“不可能定理”消失（例如中位选民定理）

---

P58

---

🟢 用“人话”解释 Black’s Theorem

定理内容：

如果有奇数个选民，并且大家的偏好是 single-peaked（单峰） 的，那么
① 一定存在 Condorcet winner（多数制冠军）
② 这个赢家就是 中位选民最喜欢的候选人（median voter winner）

换成人话：

---

🎯 1. 只要政治光谱是“单峰”的，就不会出现可怕的泰国式选举循环 → 一定能选出多数喜欢的候选人

例如：

• A 赢 B

• B 赢 C

• C 又赢 A（循环）

这种“大家互相赢来赢去，没有绝对赢家”的投票异常现象 不会发生。

因为路线是单峰的，人们就是“越接近自己的政治位置越喜欢”，不会突然左一下右一下。

---

🎯 2. 赢的人通常站在政治光谱的中间位置（median voter rule）

“中位选民”就是：

• 全体选民从左到右排队

• 排在正中间的人

Black’s theorem 说：

最终赢的人，就是那个最接近中位选民政治立场的人。

换句话说：

选举的最终结果往往由“中间派选民”决定，而不是极左或极右。

P61

🟢 这段话到底在说什么？

你看到的内容其实是社会选择理论里面的一个“好消息”：

在“单峰偏好”（single-peaked preferences）这个特殊情况下，
Gibbard–Satterthwaite 和 Arrow 两个不可能性定理都失效了！

什么意思？我们逐条解释：

---

🔵 (1) 在单峰偏好 + 奇数个选民下， median voter rule 是 strategy-proof 的

为什么这是好消息？

因为一般情况下（偏好没有任何结构）：

• 任何投票规则都可以被操纵（Gibbard–Satterthwaite 1973）
  除非它是独裁规则。

但是如果偏好是单峰的（比如政党、左右政治光谱、税率、年龄等线性议题），
而且选民人数是奇数：

median voter rule（中位选民规则）无法被策略性投票操纵。

也就是说：

• 没人通过撒谎改善自己的结果

• 每个人说真话最优

• 这是民主制度里极少数能 strategy-proof 的情况

你可以理解为：

单峰偏好给制度一个“特殊结构”，让操纵不再可能。

---

🔵 (2) 在单峰偏好 + 奇数 voters 下，median voter rule 满足 Arrow 的弱帕累托 + IIA

这是另一个大反转。

一般情况下，Arrow 1951 不可能性定理说：

没有任何投票制度同时满足：
Weak Pareto + IIA + 非独裁

但是在“单峰偏好”这个特殊情况下：

median voter rule（选择 Condorcet winner = 中位点）居然全部满足：

• 弱帕累托（everyone prefers A over B → A wins）

• IIA（无关替代物独立性）

• 并且不是独裁

• 还能 strategy-proof

这就像奇迹一样。

换句话说：

Arrow 不可能性定理，在单峰偏好上失效了。
所以制度设计突然变得“可能”。

P62 总结

1. May 定理：多数票制是合理的

如果只有 A 和 B 两个选项，那么：

• 每个人都被平等对待（anonymous）

• 每个候选人也被平等对待（neutral）

• 如果有人把 A 提得更高，A 就应该更可能赢（positive responsiveness）

满足这些性质的投票方式只有一个：

谁得票多，谁获胜（plurality rule）。

所以，在“两选项”场景，多数决是唯一“既公平又自然”的制度。

---

2. Young 定理：评分制投票 = 加权评分规则

Young 定理告诉我们：

如果你希望一个投票制度具有“强化”性质（reinforcement），
那么它一定属于评分规则（positional scoring rules）。

强化性质意思是：

• 小组 A 的赢家是 X

• 小组 B 的赢家也是 X

• 把两组票合并 → winner 还是 X

符合这个性质的就是 Borda、Plurality、Veto 等各种加权分数规则。

---

3. Arrow 定理：你想太多，民主做不到

Arrow 提出两个看似合理的要求：

1. 弱帕累托：大家都更喜欢 A → A 必须赢

2. IIA：A 和 B 的比较不能受 C 的存在与否影响

结果，却爆出震撼世界的结论：

任何满足这些性质的投票制度，必须是 独裁。

这就是著名的“不可能性定理”，告诉我们：

没有完美的民主制度。

---

4. Gibbard–Satterthwaite：只要候选人 ≥ 3，策略操纵几乎不可避免

G-S 定理说：

• 只要候选人 3 个或以上

• 你想找**不被操纵（strategy-proof）**的投票制度

那么你最终会得到：

一个独裁制度。

也就是说：

所有民主投票制度都可以被“撒谎投票”操控。

这就是为什么选举里总有“战略投票”（不投最喜欢的，投最不讨厌且可能获胜的）。

---

5. Black 定理：单峰偏好让民主“突然变好”

如果选民的偏好分布是“单峰的”（如左–中–右），那么：

• 一定存在 Condorcet winner

• median voter rule（中位选民）能选出它

• 制度不会被操纵

• 也避免了 Arrow 和 G-S 的不可能性

换句话说：

如果意见是在一条线上排的（比如政治光谱），民主就“正常工作”了。

这是对民主制度的一个巨大鼓舞。

---

🟢 总结：这 5 大定理告诉我们什么？

社会选择理论的革命性在于：
它第一次让我们用数学形式化地分析“民主是否可能”。

• May：告诉我们什么是“合理”的多数决

• Young：告诉我们评分制为什么自然

• Arrow：告诉我们完美制度不存在

• Gibbard：告诉我们不可能避免策略投票

• Black：告诉我们在某些结构下民主变得“可能”

一句话：

社会选择理论用数学证明了民主制度的极限、缺陷和可能的修复方式。

论文介绍

---

🧩 论文核心概述

本论文提出了一种“选举式（electoral）”方法，以改进大型语言模型（LLM）驱动的多智能体系统中的集体决策机制（Collective Decision-Making, CDM）。作者指出，现有的多智能体协作系统普遍缺乏决策方式的多样性，大多数仅采用“多数投票（Plurality Voting）”或“独裁式（Dictatorial）”决策，而忽视了社会选择理论（Social Choice Theory）中的其他方法。

---

📚 研究动机

• 当前LLM多智能体系统中，决策模式过于单一，主要依赖一个主导智能体（dictator）或简单多数投票。

  • 🗳️ 2. 多数投票（Plurality Voting）

    多数投票就是最常见的“得票最多的赢”。
    每个智能体（或人）只能选自己最喜欢的一个选项，谁得的“第一名票”最多，谁就是最终的决定。

    论文还提到两种变体：

    • Majority Voting（绝对多数）：必须超过半数票才算赢。

    • Consensus（共识）：要所有人都同意才算通过。

  • 🧮 1. 功利主义决策（Utilitarian）

    功利主义的做法是：

  “先算一算每个选择能给大家带来多大的好处，然后选那个让全体的‘幸福总和’最大化的选项。”

	就像一个团队要决定去哪吃饭，大家给每家餐厅打分（比如寿司=9分，火锅=8分，披萨=6分），最后选**总分最高的**那个地方。
	
	但论文提到一个重要区别：

  功利主义的“分数”并不是每个智能体自己想的，而是**外部规定或计算出来的**。  
  也就是说，这种方法**不是自主的（non-self-governing）**，而是别人提前告诉系统“这个选项值几分”。

• 这种单一决策方式在鲁棒性、公平性、稳定性方面存在缺陷，容易受到偏见或噪声的影响。

• 作者借鉴社会选择理论，旨在探索多种投票制（如Borda计数、Condorcet、Minimax、Instant Runoff等）在LLM集体决策中的适用性与效果。

---

⚙️ 方法与系统设计

作者提出了一个新的选举式CDM模块，称为 GEDI（General Electoral Decision-making Interface），它允许不同投票规则在LLM-agent之间进行比较与组合。
系统测试涵盖以下方法：

• 独裁制（Dictatorial）

• 多轮多数制（Plurality, Bucklin, IRV）

• 序列排名制（Borda Count, Ranked Pairs, Minimax）

• 效用最大化制（Utilitarian）

实验平台包括多个大型语言模型（GPT-3.5, GPT-4, Llama-3, Qwen, GLM, Mistral等）。

这张图（Figure 2）其实是这篇论文的核心概念图，它对比了四种多智能体系统（Multi-Agent System, MAS）中的集体决策方式（Collective Decision-Making, CDM）。
我来用通俗语言帮你拆开讲清楚👇

---

🧩 图的总体意思

这张图展示了 4 种不同的“AI 群体如何做决定”的方式：

1. 功利主义 (Utilitarian)

2. 独裁式 (Dictatorial)

3. 多数投票制 (Plurality)

4. 论文提出的 GEDI（Preferential Voting / 偏好排序投票）

每种方式的区别在于：

“谁说了算” + “怎么整合各个智能体的意见”。

蓝色箭头代表智能体之间的交流互动（Interaction），
绿色箭头代表他们将自己的意见传给决策模块（Preference Communication）。

---

⚙️ 一种一种来看：

① Utilitarian（功利主义）

🧠 想法：每个智能体计算某个方案能带来多少“效用（utility）”或“奖励（reward）”，然后选那个“总分最高”的方案。
📊 比如：三个AI在决定去哪吃饭，每个地方的“满意度分数”加起来最高的那个就赢。
⚠️ 问题：这些分数往往是外部设定的，不是智能体自己投票决定的，所以不是真正的自我决策系统。

---

② Dictatorial（独裁式）

👑 想法：所有AI都可以讨论，但只有一个AI（领导/裁判）拥有最终决定权。
🗣️ 比如：几个AI讨论方案，最后那个“王冠”的AI拍板定案。
⚠️ 问题：这种方式效率高但风险大、容易偏见，如果那个主导AI出错，整个系统都崩。

---

③ Plurality（多数投票制）

🗳️ 想法：每个AI投一个“最喜欢”的选项，得票最多的方案获胜。
💡 就像“简单民主制”，比如三票选A，两票选B → A赢。
⚠️ 问题：这种方法只考虑“第一偏好”，忽略了智能体对其他选项的看法，信息利用率低。

---

④ Preferential Voting（论文提出的 GEDI 模块）

🌟 这就是论文的创新点。

🧠 GEDI（General Electoral Decision-making Interface） 是一个“通用投票接口模块”，可以让多智能体用更“人类社会化”的方式做决策。

它的特点是：

• 每个智能体不是只选一个，而是对所有选项排序（1st, 2nd, 3rd …），形成一个偏好顺序（preferential ranking）。

• GEDI 把这些“排序票”汇总，通过不同的投票规则（比如 Borda 计数法、Ranked Pairs、Minimax 等）来算出集体偏好结果。

• 最终输出的不是一个单一决定，而是一个完整的偏好列表，展示群体对所有选项的整体态度。

📊 举个简单例子：
三个AI要选最合适的策略（A/B/C）。
每个AI给出排序：

• AI1：A > B > C

• AI2：B > A > C

• AI3：B > C > A
  GEDI会把这些排序结合，计算出一个整体偏好序列（比如B > A > C），代表群体的“共识倾向”。

🧩 优点：

• 不是一个AI说了算，而是大家都有话语权；

• 不只考虑“最喜欢的”，而是综合考虑全部偏好；

• 比简单投票更公平、更稳定、更“社会化”；

• 能减少单点失败（如果某个AI出错，整体决策仍然稳健）。

---

✅ 一句话总结：

前三种方法像是“谁声音最大谁赢”，而 GEDI 更像是“大家排个名，再通过不同的投票算法综合出群体意向”。

---

---

🧪 实验结果

实验在三个多选问答基准（MMLU, MMLU-Pro, ARC-Challenge）上进行，主要发现如下：

1. 多数投票优于单一智能体决策，平均提升准确率约2–6%。

2. 不同投票方法效果差异明显：Minimax和Ranked Pairs在多模型中表现最稳健。

3. 投票智能体数量达到3个以上时，集体决策效果明显优于独裁模式。

---

---

🪄 主要贡献

1. 首次系统性地将社会选择理论引入LLM多智能体集体决策。

2. 构建了GEDI系统，实现多种投票机制的自动化评估。

3. 通过实证研究展示了多样化CDM方法对模型集体智能的促进作用。

---

🔮 结论与未来工作

作者认为，引入多样化的投票方法有助于增强LLM多智能体系统的集体智能与公平性。未来研究方向包括：

• 根据任务特性自动选择最优CDM方法；

• 将社会选择理论进一步应用于模型对齐（alignment）与偏见评估。

---

---

🧩 总体意思

作者总结了他们的研究成果：
他们发现，现在很多基于大语言模型（LLM）的多智能体系统在**集体决策（CDM）**方面非常单一，大多数系统都用同一种决策方法（比如“多数投票”或“独裁式”），几乎没有多样性。

所以，他们提出并测试了一套新的框架——GEDI 投票系统，希望让AI群体的决策方式更“民主”、更丰富、更贴近人类社会的投票逻辑。

---

📊 主要结论（用简单话说）

1. 🔍 他们回顾了 52 个多智能体系统，发现：

   • 大部分都只用一种简单的决策方式；

   • 这样做虽然方便，但在复杂任务中容易出错、缺乏灵活性。

2. ⚙️ 他们从社会学里的“社会选择理论（Social Choice Theory）”借鉴方法，设计了GEDI模块。

   • 就像把“人类投票制度”搬进AI群体。

   • 让AI们也可以进行不同形式的投票、排名、协商。

3. 🧠 他们的实验结果表明：

   • 采用多种投票机制能显著提高AI群体决策的质量和鲁棒性；

   • 不同任务可能适合不同的决策方法。

   • 这种“多样化的决策方式”能帮助我们更好地理解AI群体的“集体行为”。

---

🔮 未来展望（作者接下来想做的事）

1. 🎯 任务匹配：未来想研究不同任务应该配哪种CDM方法，比如：

   • 有的任务需要快速决策 → 多数投票；

   • 有的任务需要公平性 → Borda排序；

   • 有的任务需要高鲁棒性 → Minimax 等。

2. 🔄 模型对齐与聚合（Alignment & Aggregation）：
   因为社会选择理论本质上研究“如何把很多人（或AI）的偏好合并成一个群体决策”，
   所以作者认为这也可以用来改进：

   • 模型对齐（alignment）：让不同AI模型的价值观趋于一致；

   • 模型聚合（aggregation）：让多个模型合作时能得出更平衡的集体判断。

3. 🌍 跨学科研究：他们希望这项研究能连接 NLP（自然语言处理）与社会科学、政治学等领域，
   用“人类社会的决策智慧”来改进“AI群体的合作方式”。

---

✅ 一句话总结

作者发现AI群体的决策太单一，于是借鉴人类社会的投票系统（GEDI）来让AI们“更会开会、更会投票”，从而提升群体智能。未来，他们想继续研究不同场景下最合适的投票方式，并把这种思想应用到AI对齐和群体智能研究中。