社会程序的形式化方法（一）

具有算法特征的社会程序通常可以通过重新设计来改进。这适用于投票和其他和平决策程序、婚介、拍卖、财产的公平分配以及许多分配正义程序。算法方面可以用形式化方法进行分析。“社会软件”一词​​由 Rohit Parikh (2002) 提出，指的是新兴的跨学科领域，该领域关注设计和分析规范社会过程的算法。这种分析和（重新）设计运用了逻辑、博弈论和理论计算机科学的方法。[1] 社会程序形式化方法的研究目标是建模社会情境、发展正确性理论以及（重新）设计社会程序，理想情况下能够引领新的社会行为。

逻辑学、博弈论和计算机科学并非唯一对社会机制有所涉猎的学科。投票理论、拍卖理论、社会选择理论、社会认识论、机制设计理论和算法博弈论也都研究此类机制。人工智能和分布式计算研究的是更抽象层面的多智能体交互，因此所有这些学科都对社会互动的形式化分析有所涉猎。

1. 作为算法的社交程序

2. 公平性

2.1 公平分配

2.2 在两位以上参与者之间切蛋糕

2.3 所罗门的判决

3. 稳定婚姻问题

3.1 盖尔-夏普利算法

3.2 大学宿舍分配程序

4. 沟通的逻辑

4.1 通信与分布式计算

4.2 常识与社会程序

5. 战略推理与合作

6. 结论

参考文献

参考文献

公平

稳定婚姻问题

沟通的逻辑

战略推理与合作

学术工具

其他网络资源

相关文章

1. 作为算法的社会程序

社会软件本身并非一个定义明确的研究领域，而是计算机科学、逻辑学和博弈论中某些研究类型的总括。然而，社会软件视角下的社会程序和智能交互，强调算法和信息，已经产生了许多重要的见解。本文将讨论一些案例，并提供哲学相关讨论的参考。

数学中算法的典型例子（参见可计算性和复杂性条目）是欧几里得求两个正整数 A 和 B 的最大公约数 (GCD)。两个数的最大公约数是能无余数整除两个数的最大数。

如果 A 大于 B，则用 A-B 替换 A；否则，如果 B 大于 A，则用 B-A 替换 B。如此反复，直到 A 等于 B。

最终的 A=B 等于初始值 A 和 B 的最大公约数。例如，假设算法初始值为 A=20，B=12。第一步，A 被替换为 20-12=8，因此 8 成为新的 A。第二步，B 被替换为 12-8=4，因此 4 成为新的 B。第三步，A 被替换为 8-4=4，因此 4 成为新的 A，A 和 B 两个数变得相等。该算法得出 4，即 20 和 12 的最大公约数。

欧几里得的公式是形式化的，我们可以用形式化的方法对其进行分析。欧几里得算法的正确性源于以下观点：如果有两个数 A 和 B，且 A 大于 B，将 A 替换为 A-B，则这两个数对的公约数集保持不变。

算法有多种形式和特点，例如顺序算法和并行算法。有关计算机科学中算法的有趣介绍，请参阅 Harel & Feldman (2004) 和 Miller & Boxer (2012)。与这些算法类似，社会程序可以用逻辑和理论计算机科学的形式化工具进行分析。[2]

似乎最适合采用形式化方法分析的是那些人们希望保证在特定起始条件下，程序能够保留或创建特定期望属性的社会程序。例如，公平分配（第 2 节）、匹配（第 3 节）和通信（第 4 节）的社会程序。最后，形式化视角在需要参与者进行策略推理的情境中非常有用（第五节）。一个共同点是，在所有这些情境中，代理的知识以及对其他代理心理状态的缺乏了解都发挥着重要作用。与本文中的例子相对照，Van Benthem (2018) 对社会视角在计算机科学本身中的当前作用进行了引人入胜的概述，强调了社会能动性和信息。

2. 公平性

形式化方法本身并不能解决哲学问题，正如 Padma (2007) 的以下故事所说明的那样。

两位农民，Ram 和 Shyam，正在吃印度薄饼。Ram 吃了 3 片扁平的圆形面包，Shyam 吃了 5 片。一位看起来又饿又累的旅行者骑马向他们走来。拉姆和希亚姆决定和他分享他们的恰巴提。三个人把8张恰巴提（像煎饼一样）叠起来，然后切成三等份。他们平分了这些恰巴提，一直吃到一无所有。旅行者是一位贵族，他非常感激，给了这两位农夫8枚金币作为他那份食物的报酬。

旅行者走后，拉姆和希亚姆琢磨着该如何分配这8枚金币。拉姆说，一共有8枚金币，而只有两个人，所以每人应该均分4枚。“但这不公平，”希亚姆说，“因为我本来就有5张恰巴提。”拉姆理解他的意思，但他不太想把其中5枚金币给希亚姆。于是他建议他们去见毛拉维，毛拉维非常明智。希亚姆同意了。

拉姆和希亚姆把事情的经过都告诉了毛拉维。经过长时间的思考，他说最公平的分配方式是给夏亚姆7枚硬币，给拉姆1枚。两人都感到惊讶。但当他们请毛拉解释他的理由时，他们确信这是对8枚硬币的公平分配。

以下是参与者可以给出的解释，以解释每种分配方式的公平性：

拉姆：“如果旅行者没来，我们会均分薄饼。所以，现在我们也均分8枚硬币才公平。”

夏亚姆：“如果旅行者没来，你会以薄饼的市价从我这里买一张薄饼。现在旅行者如此慷慨，市价突然涨到一张薄饼1金币。所以你的薄饼值3金币，我的值5金币。”

毛拉：“旅行者已经吃了八张薄饼的三分之一。拉姆一开始只吃了三张薄饼，因此，他吃了拉姆的三分之一个印度薄饼，又吃了希亚姆的七分之三个印度薄饼。所以，只有拉姆得到一枚硬币，希亚姆得到七枚硬币才公平。

其寓意在于，在这种情况下以及在许多情况下，公平的概念可能并不存在显而易见的正确性。形式分析总是从直觉出发，并有助于将直觉转化为更精确的定义。然后，人们可以检查给定的程序是否符合定义；然而，如果符合，并不表明该定义是正确的。

2.1 公平分配

社会程序与世界一样古老。分配与选择（也称为“我分，你选”）是两人公平分配某种可取或不可取的异质商品的程序。一个人将商品分成她认为相等的份额，另一个人进行选择。如果两个参与者对商品的某些部分有不同的价值判断，则可能两个参与者都认为自己获得了超过50%的商品。设X是表示待分配商品的集合。X的估值函数V是一个从P(X)到[0,1]的函数，其性质为V(∅)=0， V(X)=1，且对于所有子集 A、B，A⊆B⊆X 蕴涵 V(A)≤V(B)（符号解释见基本集合论补充）。假设 Vm 和 Vy 分别是你我各自对 X 内容估值的函数。如果 Vm 和 Vy 不同，则意味着你我对于 X 中某些内容的估值不同。由此可见，正如 Steinhaus 在 1948 年所观察到的，存在一种分配方式，使得双方的所得均超过其应得的份额；“这一事实推翻了普遍认为估值差异导致公平分配困难的观点”（Steinhaus 1948）。

估值是否为对方所知至关重要。此类知识可被分拆者利用。首先考虑我不知道你的估值，反之亦然的情况。如果我分拆，我能做的最好的选择是选择集合 A,B⊆X，其中 A∩B=∅，A∪B=X，且 Vm(A)=Vm(B)。如果你选择，你将使用 Vy 来选择 {Vy(A),Vy(B)} 中的最大值。由此可知，分拆可以保证公平分配，但仅此而已，而选择则有望达成更有利的交易。因此，如果在双方都只知道自己估值的情况下，你可以在分拆和选择之间做出选择，那么将分拆交给对方对你有利。

然而，如果估值是常识（参见常识条目），情况则相反，因为在这种情况下，扮演分拆者的角色更为有利。作为切蛋糕者，你可以尝试对 intp 集合 A 和 B 进行划分，根据对方的评价，A 的价值略高于 B，而根据你自己的评价，B 的价值远高于 A。

该示例表明，知识与无知问题对于分析公平分配协议至关重要。认识论逻辑（参见“认识论逻辑”条目）可以揭示社会互动中知识与无知的许多微妙方面，尤其是在公平分配问题中；有关一个有趣的切蛋糕实验，展示了知识与无知的重要性，请参阅 Kyropoulou 等人 2019 年的研究。然而，在传统的公平分配研究中，知识的作用并未被考虑在内，正如 Robertson & Webb (1998) 对“切蛋糕算法”的全面研究所证实的那样。

2.2 两位以上参与者切蛋糕

在社会选择文献中（Brams 2005；Brams & Taylor 1996），通常用切蛋糕来比喻单一异质物品的分配。例如，在继承土地时分割一块土地。蛋糕上有不同的配料，不可能全部切成相同成分的块：上面可能有蜜饯樱桃，有人喜欢，有人讨厌，等等。如果n位参与者中的每一位都认为自己根据自己对蛋糕各部分的估价，至少获得了1/n的蛋糕，那么蛋糕分配就是公平的。一个程序可以是公平的，但不必排除任何可能引发不满情绪的可能性。如果每个人都觉得没有其他人分到了更大的蛋糕，那么蛋糕分配就被称为无嫉妒分配。无嫉妒分配的一个明确标志是，没有人愿意与其他人交换蛋糕。事实证明，设计既公平又无嫉妒的切蛋糕程序非常困难。 “我切，你选”的程序是公平的，而且它不会产生嫉妒，因为剩下的蛋糕只有一块，所以不可能产生嫉妒。关于无嫉妒的哲学讨论，请参阅“经济学[规范]和经济正义”条目。

R. Parikh (2002) 分析了所谓的 Banach-Knaster 切蛋糕算法，该算法适用于至少三人公平分配蛋糕的情况，其流程如下：

我切了一块给自己的。其他人都考虑了一下。如果没有人反对，我就得到我的那一块。如果有人反对，她有权切下一块，并将其与蛋糕的其他部分一起放回原处。然后她询问是否可以得到减少的那一块。如果没有人反对，她就得到它；否则，其他人会拿刀继续切，把蛋糕再切一点。依此类推，直到有人拿到切好的那块。然后进入下一轮，n-1 名玩家。当剩下两名玩家时，他们使用分割选择算法。

Parikh 的讨论展示了如何运用理论计算机科学的方法来论证该程序的公平性。该程序的关键要素是一个循环操作：

继续切块，直到没有人对大小提出异议。

假设 r 代表根据 Banach-Knaster 算法切掉一块蛋糕并将其与蛋糕主体部分一起放回原位的动作，假设 F(m,k) 表示蛋糕主体部分足够大，可以容纳 k 个人。那么 F(m,n) 从一开始就成立：整个蛋糕足够大，可以容纳整个群体。此外，Parikh (1983, 2002) 运用他的博弈逻辑证明了 F(m,k) 在作用 r 下不变：如果 F(m,k) 在 r 之前为真，那么在 r 发生之后仍然为真。显然，如果能够证明 F(m,k) 在算法中持续成立，且 k 遍历 n,…,1，则证明该划分是公平的。[3]

2.3 所罗门的审判

在著名的《所罗门审判》中，所罗门王在两个自称是孩子母亲的女人之间发生了争执，他使用了“划分与选择”的变体。完整的故事记载在《列王纪上》3:16-28。住在同一屋檐下的两个女人都有一个婴儿儿子。其中一个女人声称另一个女人在睡觉时不小心闷死了自己的儿子，从而偷走了她的孩子。另一个女人否认了这一指控，并推翻了指控。所罗门王听完她们的故事后，召来一把剑，宣布只有一个公平的解决办法：把活着的孩子砍成两半，把一半分给两个女人。听到这话，真正的母亲哭喊着说，如果孩子能被救活，她愿意放弃孩子，而假母亲则同意了判决。这一行为让所罗门知道谁才是真正的母亲，她的孩子被归还给了她。

这个过程是不可重复的。正如圣经故事所说：

以色列众人听见王所作的判决，就敬畏王，因为他们看出王有神的智慧，能施行公义。

显然，在第二次类似的争执中，两个女人都会惊呼：“把孩子给她，但要让他活着！”

所罗门对这种情况的处理可以转化为一个可重复的社交程序，如下所示。所罗门没有叫人拿刀，而是向两个女人解释了以下步骤。首先，他会问第一个女人是否愿意放弃孩子。如果答案是“是”，争执就解决了，不再追问。否则，他会问另一个女人是否愿意放弃孩子。同样，如果答案是“是”，争议就解决了。如果他们都拒绝，那么孩子就归他了，然后他会允许其中一名女子以如下价格买回孩子。他们会在一张纸上写下金额，不写姓名。如果两人的出价分别是A和B，那么孩子的价格就定为

A+B

2

，命运将决定哪位女子将以该价格得到孩子，而另一位女子则需要支付少量罚款。如果两位女子都是理性的，其中一人在被要求时会主动放弃孩子（参见Moore 1992和Pauly 2005；关于理性的哲学讨论，参见“实践理性与博弈论”和“伦理学”条目）。Moore (1992) 和 Pauly (2005) 都讨论了在所罗门王案例中，对常识和无知进行推理的重要性。例如，所罗门王不知道谁是真正的母亲，但两位女性从一开始就普遍知道谁是真正的母亲，因此真正的母亲会比另一位出价高得多。这使得整个过程安全无虞。同样，认知逻辑，尤其是常识，有助于阐明一个棘手的社会程序。有关公平分配问题的更传统的哲学介绍，包括对公平性、可操纵性和无嫉妒性的更详尽的解释，请参阅“经济学[规范]和经济正义”条目。

下一节将展示社交软件的视角也可以阐明社会匹配问题。这些问题涵盖从婚姻到住院医生到医院的分配、大学录取程序以及学生的住房分配等各个方面。

3. 稳定婚姻问题

假设给定男女两组，他们都想与异性结婚，每个男人都以严格的顺序列出了他对女性的偏好，对每个女人也同样如此。稳定的婚姻匹配是男女之间的一对一映射，具有以下特性：如果一个男人比自己的妻子更喜欢另一个女人，那么这个女人不会比自己的丈夫更喜欢他；如果一个女人比自己的丈夫更喜欢另一个男人，那么这个男人也不会比自己的妻子更喜欢她。

3.1 盖尔-夏普利算法

计算机科学家盖尔和夏普利证明了稳定匹配总是存在的，并提出了一种寻找这种匹配的算法，即所谓的盖尔-夏普利算法（Gale & Shapley 1962）：

最初，所有男女都是自由的（未订婚）。

接下来，在多轮循环中，每个自由的男士向他最喜欢的、尚未求婚的女士求婚，并将她从他的名单中剔除。如果女士是自由的，她会接受，然后他们订婚。如果女士不是自由的，她会将求婚者与她现在的未婚夫进行比较。如果她更喜欢她，她会抛弃重新获得自由的未婚夫，然后求婚者会和他选中的女士订婚。

如此循环，直到所有男士和女士都订婚。

例如，假设有三个男士 a、b、c 和三个女士 d、e、f，他们的偏好列表如下（偏好最高的女士排在第一位）：a:edf，b:fed，c:dfe，d:abc，e:cda，g:acb。因此，a:edf 表示 a 更喜欢 e 而不是 d，而 d 更喜欢 f。假设偏好具有传递性，因此 a 也更喜欢 e 而不是 f。

这种情况下的稳定匹配示例表示为三对 (a,e)、(b,f)、(c,d)。请注意，女性 d 最终会选择她名单上排在最后一位的男性。但这场比赛仍然是稳定的，因为尽管 c 愿意将她的丈夫换成其他两位男性中的任何一位，但这两位候选人都不会同意，因为他们恰好都娶了自己名单上排在首位的女性。

为了检验 Gale-Shapley 算法是否总能产生稳定的匹配，我们可以按如下方式进行。显然，无人订婚的情况是稳定的。

对于“订婚”映射 E 来说，在女性集合 W 和男性集合 M 上保持稳定意味着什么？我们用 m>wm′ 来表示“w 更喜欢 m 而不是 m′”（因此，m 越大越好）。

（1）

对于所有 (m,w)∈E：如果存在 w′ 且 w′>mw，则不存在 m′ 且 (m′,w′)∈E 且 m>w′m′；

（2）

对于所有 (m,w)∈E：如果存在 m′ 且 m′>wm，则不存在 w′ 且 (m′,w′)∈E 且 w>m′w′。男人自由意味着什么？

(3)

自由男人的集合应该等于所有男人的集合减去已订婚男人的集合。

接下来，检查算法中某一步骤会发生什么。该步骤的前提是至少剩下一位自由男人m。这位自由男人m向他名单上排名最高的女性w求婚，而他尚未向该女性求婚。

有两种情况。如果w是自由的，w接受了求婚，他们订婚了。新的已订婚伴侣集合是否稳定？我们只需检查新的伴侣(w,m)。

假设存在一个自由的w′，且w′>mw。这不可能，因为w在m的名单首位。

假设存在一个m′，且m′>wm。那么，如果m′已订婚，假设w′是自由的，这必然意味着w>m′w′。否则，m′会向w求婚，而不是向w′求婚。

新的自由人名单等于旧名单减去 m。这是正确的，因为 m 刚刚订婚。

现在考虑另一种情况：假设 w 已经订婚。有两种子情况。如果 w 更喜欢她现在的未婚夫，则什么也不会发生。最终的订婚名单仍然稳定。自由人名单保持不变，因为 m 求婚后被拒绝。

如果 w 更喜欢 m 而不是她自己的未婚夫 m′，她会进行交换：(m,w) 替换订婚名单中的 (m′,w)。同样，很容易看出最终的订婚名单是稳定的。自由人名单中的 m 被 m′ 替换。这也是正确的。

需要注意的是，Gale-Shapley 匹配算法对求婚方非常有利。求婚方有机会按照优先顺序向任何候选人求婚。但在程序开始时，接收方必须对任何提议说“是”！在算法中交换男女角色的结果也将计算出一个稳定的匹配，但这个匹配对女性更有利。

Gale-Shapley 程序的运行时间与男女人数的平方成正比（例如，参见 Cechlérová 等人，2005）。Pini 等人（2011）展示了参与者如何通过歪曲他们​​的真实偏好来轻松操纵程序的结果。幸运的是，Pini 等人还提出了一种难以操纵的替代程序，因为想出一个对个人有利的偏好歪曲表述是一项计算复杂的任务。

Gale-Shapley 算法有许多重要的应用，甚至在婚姻中介领域之外也是如此；Gale 和 Shapley 本人也讨论了大学录取程序（1962）。下一小节将介绍另一个应用。