根据程序员Paul Khuong在2012年的一篇博客文章,fixed point theory —— 这一来源于数学和计算机科学的概念 —— 为理解学生工会的集体决策提供了意想不到的视角。核心思想在于求解形如x = f(x)的方程的解,这类解被称为fixed point。当处理monotone函数 —— 那些保持顺序的函数 —— 时,Tarski's fixed point theorem保证,当定义域形成complete lattice时,既存在least fixed point也存在greatest fixed point。在编程领域,这一理论体现在例如编译器中的dead value elimination问题上。Khuong指出,当被要求识别代码中无用的变量时,许多人直觉地从假设所有值都是活跃的(被使用)开始,然后剔除仅计算无用值的那些变量。然而,这种方法收敛于greatest fixed point,而实际所期望的是least fixed point —— 即可删除计算的最大集合。正确的做法则相反:从仅假设返回值和内存写入是活跃的开始,然后迭代添加那些计算出活跃值的变量,直到无法再添加为止。这样得到的就是least fixed point —— 即最优的可删除值集合。Khuong将这一见解延伸到了Québec学生工会的真实场景。在学费抗议期间,大学和CEGEP学生工会会就罢工授权进行投票,这些授权常包含关于最低参与人数的条件——例如,要求一定数量的其他学生或工会也承诺罢工后才能采取行动。这些授权形成了一个monotone系统:如果一组工会满足罢工条件,那么任何更大的集合(超集)也会满足这些条件。这一数学性质意味着Tarski's fixed point theorem适用,此时工会的power set按subset inclusion排序形成一个complete lattice。关键问题变为:哪个fixed point代表罢工投票过程的实际结果?Khuong认为目标是找出能够同时罢工的最大可能工会集合 —— 即在subset ordering下的greatest fixed point。然而,解决此问题的直觉算法通常从没有任何工会罢工开始,然后迭代添加其条件被当前罢工集合满足的工会。这种方法寻求的是least fixed point,可能导致尽管存在集体行动的潜力却出现僵局 —— 即没有任何工会罢工。作为举例,Khuong描述了两个各有5,000名成员的工会,其罢工授权要求至少有10,000名学生参与。从零个罢工工会开始,没有任何工会会加入罢工,因为条件未得到满足,由此导致僵局。正确的方法是首先假设所有持有授权的工会都在罢工,然后移除那些在当前集合中不满足条件的工会,最终收敛到greatest fixed point —— 此时两个工会都罢工。尽管Khuong将此称为‘抽象数学帮助我们解释现实情况的一个相当不错的例子’,但他承认这可能主要停留在理论层面。尽管如此,该例子凸显了一种更广泛的模式:在fixed point计算中,直觉的保守方法常常收敛于次优解,而在least fixed point和greatest fixed point之间的选择应当基于问题需求进行deliberate决策,而非源于无意识的偏见。该博客文章在结论中指出,尽管保守的初始值可能带来更快的收敛和始终正确的中间结果,但满足于次优解应当是一个显式选择,而非忽略其他fixed point的后果。
HN Digest / · HN #49916550
不动点理论在学生罢工授权中的应用
一篇2012年的博客文章解释了计算机科学中的fixed point mathematics如何应用于Québec学生工会的罢工授权,直观方法确定哪些工会应罢工往往失败,而寻找greatest fixed point则给出正确解决方案。

来源页面截图(pvk.ca)