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

3.2 大学住房分配程序

Parikh 和 Pauly（2012）从社交软件的角度研究了 Gale-Shapley 算法的一种变体，该算法用于斯坦福大学住房抽签，为学生分配房间。该算法的情况比婚姻场景更复杂，因为学生不会对所有房屋给出完整的排序，而只会对其中 8 栋房屋给出排序；此外，他们可能会选择分组参与抽签。在住房情境中，学生有动机诚实地提交他们的真实偏好：抽签对他们来说是不可操纵的。然而，理论上，他们仍然可以制定策略来选择他们提交偏好的 8 栋房屋子集。

在这种情况下，知识问题很有趣。尽管该算法可以在斯坦福大学的网页上找到，大多数学生和管理人员并不完全理解其运作方式。因此，斯坦福住房抽签法不能被视为学生的常识。一个有趣的现象似乎出现了：即使承认不理解该算法，大多数学生也会说他们认为它是公平的 (Parikh & Pauly 2012)。

4. 通信逻辑

通信协议在分布式计算中非常重要：分布式系统计算是指一组通过通信网络连接的计算机。从哲学角度来看，通信协议也很有趣，尤其是在讨论隐私价值的背景下（参见隐私与计算和道德责任条目）。形式化方法有助于回答诸如“更高的安全性是否必然导致隐私性降低？”之类的哲学问题。

4.1 通信与分布式计算

在以下示例中，灵感不仅源于社会问题到形式化解决方案，也源于成功的社会实践到形式化程序。许多分布式计算算法与日常生活中用于通信的社会协议相关。一个例子是使用“发言权杖”来规范一群同伴之间的讨论和决策，规则是发言权杖会被传递，只有持有权杖的人才能发言（Nerburn 1999）。

基于这种社交程序的计算机通信协议是令牌环协议。分布式计算中的令牌环是一种网络，其中每台计算机都连接到恰好两台其他计算机，并且每台计算机在网络中都是可访问的。单个“令牌”在环形网络中循环。通信只能由令牌的当前所有者发起。

有时令牌会因计算机或网络故障而丢失。在这种情况下，必须重新生成令牌，并保证只有一台计算机拥有该令牌。在令牌环中重新生成令牌的问题称为领导者选举问题。以下是该问题的算法：

假设通信按顺时针方向进行，每台计算机都能区分其顺时针邻居和逆时针邻居。假设所有计算机都有不同的标识符（正整数），并且每台计算机都知道自己的标识符。

每台计算机在环上发送自己的标识符。当计算机 c 收到一个标识符时，c 会将其与自己的标识符进行比较。如果该标识符大于自己的标识符，则 c 将其传递下去。如果该标识符小于自己的标识符，则 c 丢弃该标识符。如果该标识符等于自己的标识符，则 c 宣布自己为领导者。

不难看出，这保证了标识符 imax 最高的计算机成为领导者（参见 Lynch 1996）。无需假设环中计算机的数量，也无需假设任何计算机知道环的大小或其他计算机的标识符。协议的下一阶段可以是领导者发送注册为非领导者并停止的请求。

更深层次的抽象是从分布式计算机或进程到交互智能体或多智能体系统。这些智能体可以是计算机、机器人、人类、人类团队，或这些的某种组合。通常假设智能体具有一定程度的自主性，即智能体对整个系统具有有限的局部视角。并且整个系统没有指定的控制者（参见 Wooldridge 2002 [2009]）。

4.2 共同知识与社会程序

许多社会程序旨在创造共同知识（Lewis 1969；van Ditmarsch 等人 2009；以及关于共同知识的条目）。当你从银行账户中提取一大笔钱并由收银员以现金支付给你时发生的老式仪式就是一个例子。

如何以及能否实现共同知识取决于可用的通信设施。公开宣布或公开可观察的仪式（上文提到的收银员仪式）可以创造共同知识。但是，正如 Halpern 和 Moses (1984) 所证明的那样，在分布式环境中进行消息交换是无法实现的，因为无法保证消息的传递。Halpern 和 Moses 以两位将军计划协同攻击一座城市为例。两位将军分别驻扎在城市两侧的两座山丘上，各自率领着自己的军队。他们深知，只有两支军队同时进攻，才能攻占这座城市。然而，分隔两座山丘的山谷已被敌方控制，任何从一个军事基地派往另一个军事基地的信使都面临着被俘的巨大风险。将军们已经同意联合进攻，但仍需确定时间。于是，将军们开始发送信息，例如“我们上午9点进攻”。但他们无法确定信使能否成功传递信息。即使信使成功到达，也无法保证确认信息一定会送达。诸如此类。

即使在实践中，常识有时难以达成，但它却是规范社会的必要假设。罗马的立法者很久以前就发现，如果公民在其管辖范围内可以因不懂法律而申辩无罪，那么任何罪犯都永远不会被定罪。因此，他们发明了“法律无知，任何人都不能以无知为借口”（Ignorantia legis neminem excusat）之类的原则。遵守法治的社会必须以这样的方式组织，即原则上公民能够了解法律。法律必须得到妥善公布和传播，例如，刊登在每个公民都能查阅的政府公报上。

迈克尔·苏英·崔（Michael Suk-Young Chwe）在其著作《理性仪式》（2001）中指出，群体规模对于建立常识至关重要。一个在大型群体中广为人知的品牌价值不菲。崔分析了美式橄榄球超级碗期间播放的广告的例子。他将通过此类广告使某事物成为常识的巨大成本与显而易见的好处进行了比较。广告的部分好处在于它创造了常识。例如，在决定购买某个品牌的智能手机时，一个重要的考虑因素是知道其他人也会购买同款。

当然，在许多社交场合，你可能希望防止常识的产生，例如，如果你想对某些人保守秘密。还有一些更有趣的案例，每个人都知道一些事实，例如某个国家拥有核武器，但通过公开宣布这一事实成为常识会导致政治问题。关于许多此类维护隐私和知情权至关重要的社会场合，请参阅van Eijck 和 Verbrugge (2009)。最近一项有趣的进展是基于动态认知逻辑的认知规划研究，它使我们能够综合通信协议，从而在群体内创建特定高阶知识层次的精确配置（Bolander 和 Andersen 2011；Löwe、Pacuit 和 Witzel 2011）。

5. 战略推理与合作

博弈论这一广阔领域在本百科全书的其他引理中得到了广泛的解释（参见博弈论条目等）。自冯·诺依曼和摩根斯特恩 1944 年出版的开创性著作以来，这一研究领域一直非常活跃。同样，社会选择理论，尤其是投票理论（参见社会选择理论和投票方法条目），早在“社交软件”一词​​出现之前就已经是蓬勃发展的研究领域。

研究形式化方法和算法视角如何帮助解决社会问题大有裨益。例如，在著名的囚徒困境案例中（参见囚徒困境条目），尝试设计策略，通过惩罚其他主体，使其作弊收益减少，这很有意思。请注意，这种“社会软件工程”发生在元层面，高于囚徒选择策略的层面（van Eijck 2015）。

博弈论中一个与社会软件相关的近期趋势是，摆脱纳什均衡等解决方案概念，转而关注理性思考的过程：“游戏理论”（参见 van Benthem、Pacuit 和 Roy，2011，以及用于分析博弈的条目逻辑）。这类研究既描绘了指导参与者战略推理的规范原则，以及解释博弈中预测行为与观察行为之间差异的心理现象（Camerer 2003；Ghosh 和 Verbrugge 2018；Pacuit 2015；Meijering 等人 2012、2014；Top 等人 2018）。

在第 4.2 节中，我们简要讨论了知识和信念研究在分析社会程序中的作用。在这方面，认知博弈论领域关注的是主体对其他主体策略的信念，以及这些主体对其他主体策略的信念，等等，直至理想情况下，即一群主体拥有共同的认知，即他们都是理性的（参见“博弈论的认知基础”条目；Perea 2012；Brandenburger 2014）。

事实证明，尤其是在投票理论中，设计一种逻辑来明确地模拟主体在投票时所运用的知识非常有用。尤其有趣的是，当智能体通过歪曲自身偏好进行策略性投票以操纵结果时，对群体中发生的情况进行建模（van Eijck 2015；van Ditmarsch 等人 2012）。

近年来，在多智能体系统研究领域，社会程序的形式化方法也被用于帮助设计实际的软件，例如用于团队合作解决问题、联盟形成、知识融合、拍卖以及软件智能体之间的谈判（Bulling 等人 2015；Chalkiadakis 等人 2011；Dunin-Kęplicz 和 Verbrugge 2010；Pauly 2002；Shoham 和 Leyton-Brown 2009；Vazirani 等人 2007）。这些文献大多是规范性的。

相比之下，另一个有趣的研究领域，进化博弈论（参见进化博弈论条目），研究利他主义、社会规范、道德行为和合作等特征实际上是如何进化的。该领域融合了规范性研究和描述性研究（Axelrod 1984；Bowles and Gintis 2011；Sigmund 2010）。作为该领域一项特殊的社会软件贡献，Gärdenfors（2012）描述了几种合作类型所需的认知和沟通能力，从简单的群体行为，到互惠利他行为（“你帮我挠背，我帮你挠背”），直至成熟的团队合作。

6. 结论

总而言之，强调算法和信息的社会程序和智能交互的正式视角已经产生了各种重要的见解，也引发了有趣的哲学讨论。未来的主要挑战似乎是统一这个目前相对分散的领域，因为许多贡献者似乎并未意识到其他子领域的相关工作。