プログラマーのPaul Khuongによる2012年のブログ記事によれば、数学とコンピュータサイエンスの概念である不动点理論は、学生組合の集合的意思決定を理解するための予想外の視点を提供します。核心は、x = f(x)という形式の方程式の解、すなわち不动点を見つけることにあります。順序を保つ単調関数に対して、定義域が完全格子を形成するとき、Tarskiの不动点定理により、最小不动点と最大不动点の両方が存在することが保証されます。プログラミングの文脈では、この理論はコンパイラにおけるデッドバリュー除去などの問題に現れます。Khuongは、コードで使われていない変数を特定する際、多くの人が直感的にすべての値が生きている(使用されている)と仮定し、それから使われていない値を計算するものを削除していくと指摘します。しかし、このアプローチは実際に望まれている最小不动点-すなわち除去可能な計算の最大の集合-ではなく、最大不动点に収束します。正しいアプローチはこの直感を逆にします:戻り値とメモリ書き込みだけが生きていると仮定し、それから生きている値を計算する値を繰り返し加えていき、これ以上追加できなくなるまで続けます。これにより最小不动点-つまり除去すべき値の最適な集合-が得られます。Khuongはこの洞察を、ケベックの学生組合における実際のシナリオに拡張します。授業料抗議の期間中、大学およびCEGEPの学生組合は、参加人数の最低条件を含むストライキの義務付けについて投票することがよくあります。例えば、一定数の他の学生または組合もストライキに参加することを条件とするものです。これらの義務付けは単調なシステムを作り出します:ストライキの条件を満たす組合の集合があるとき、その超集合(より大きい集合)も条件を満たします。この数学的性質により、部分集合による包含関係で組合のべき集合が完全格子を形成するとき、Tarskiの定理が適用されます。重要な質問は、どの不动点がストライキ投票プロセスの実際の結果を表すかということです。Khuongは、同時にストライキを行える組合の最大の集合-つまり部分集合の順序における最大不动点-を見つけることが目標だと主張します。しかし、この問題を解く直感的なアルゴリズムはしばしば、ストライキを行っていない組合から始め、現在のストライキしている集合の条件を満たす組合を繰り返し加えていきます。このアプローチは最小不动点を求め、結果としてストライキの可能性があるにもかかわらずどの組合もストライキしないデッドロック状況を引き起こすことがあります。例として、Khuongはそれぞれ5,000人のメンバーを持つ2つの組合と、参加者が10,000人必要なストライキ義務付けについて説明します。ゼロからストライキしている組合を始めると、いずれの組合も条件を満たさず、ストライキに参加せず、その結果膠着状態になります。正しいアプローチは、義務付けを持つすべての組合がストライキしていると仮定して始め、現在の集合で条件を満たさない組合を取り除いていき、その結果両方の組合がストライキする最大不动点に収束します。Khuongはこれを「抽象的な数学が実際の状況を解釈するのに役立つかなり見事な例」と表現していますが、これが主に理論的なままである可能性もあると認めています。それでも、この例はより広範なパターンを示しています:不动点計算において、直感的な保守的アプローチはしばしば最適でない解に収束し、最小不动点と最大不动点の選択は問題の要件に基づいて意識的に行うべきであり、無意識のバイアスによるものではありません。ブログ記事の結論では、保守的な初期値は収束を速め、常に正しい中間結果をもたらすかもしれませんが、最適でない解決で妥協することは、代替の不动点を見落とす結果ではなく、明確な選択であるべきだと指摘しています。
HN Digest / · HN #49916550
学生ストライキの義務付けに適用される不动点理論
2012年のブログ記事は、コンピュータサイエンスの不动点数学がケベックの学生組合のストライキ義務付けにどのように適用されるかを説明し、ストライキを行う組合を決定する直感的なアプローチがなぜしばしば失敗するのか、そして最大不动点を探すことが正しい解決策であることを示しています。

出典ページのスクリーンショット(pvk.ca)