プログラム均衡

プログラム均衡は、プレイヤーがコンピュータプログラムを提出してゲームを代行させ、プログラム同士が互いのソースコードを読み取ることができるシナリオにおけるゲーム理論上の解概念である。この用語は、 2004 年にMoshe Tennenholtzによって導入された。 ^{[ 1 ]}同じ設定は、以前にR. Preston McAfee ^{[ 2 ]}、JV Howard ^{[ 3 ]}、Ariel Rubinstein ^[⁴^]によって研究されていた。

設定と定義

プログラム均衡に関する文献では、以下の設定が考慮されています。標準形ゲームを基本ゲームとして考えます。簡略化のため、2人プレイのゲームを考えます。 $S_{1}$ そして $S_{2}$ 利用可能な戦略のセットと $u_1$ そして $u2$ はプレイヤーの効用関数である。次に、各プレイヤーが $i$ コンピュータプログラムを選択する $p_{i}$ プレイヤーの報酬（効用）は次のように決定されます。各プレイヤーのプログラム $p_{i}$ 他のプログラムと一緒に実行されます $p_{-i}$ 入力と出力としての戦略 $s_i$ プレイヤー向け $i$ 便宜上、プログラムは自身のソースコードにアクセスできると想定されることもよくあります。^{[注1 ]}最後に、プレイヤーのユーティリティは次のように与えられます。 $u_{i}(s_{1},s_{2})$ のために $i=1,2$ すなわち、基本ゲームの効用関数を選択された戦略に適用することによって。

さらに、プログラムの一つが $p_{i}$ 停止しない。これに対処する一つの方法は、停止しないプログラムを防ぐために、両方のプレイヤーが使用できるプログラムのセットを制限することである。^{[ 1 ]}^{[ 5 ]}

プログラム均衡とは、一対のプログラムのことである。 $(p_{1},p_{2})$ これは、プログラムゲームのナッシュ均衡を構成する。言い換えれば、 $(p_{1},p_{2})$ どちらのプレイヤーもプログラム均衡でない場合 $i$ 代替プログラムに逸脱する可能性がある $p_{i}'$ そのため、その効用は $(p_{i}',p_{-i})$ より $(p_{1},p_{2})$ 。

プログラムの代わりに、対戦相手が提出した論理式のエンコードに応じてプレイするアクションを指定する論理式など、他の種類のオブジェクトをプレイヤーに提出させる著者もいる。^{[ 6 ]}^{[ 7 ]}

囚人のジレンマにおける協調的プログラム均衡を達成するための様々なメカニズム

囚人のジレンマにおいて、協力的なプログラム均衡を達成する方法については、様々な著者が提案している。

構文比較に基づく協力

複数の著者が囚人のジレンマに対して以下のプログラムを独自に提案している。^{[ 1 ]}^{[ 3 ]}^{[ 2 ]}

アルゴリズムCliqueBot(opponent_program): 対するプログラムが this_program と等しい場合は Cooperate を返し、そうでない場合は Defect を返す

両方のプレイヤーがこのプログラムを提出した場合、両方のプログラムの実行においてif節は真となります。結果として、両方のプログラムは協力します。さらに、（CliqueBot,CliqueBot）は均衡状態です。どちらかのプレイヤーが他のプログラムに逸脱した場合、 $p_{i}$ CliqueBotと異なる場合、相手は裏切るだろう。したがって、 $p_{i}$ 最悪の場合、相互裏切りという結果に終わる可能性があり、それは相互協力という結果よりも悪い。

このアプローチは脆弱であると批判されてきた。^{[ 5 ]}プレイヤーが提出するソースコードの正確性について調整に失敗した場合（例えば、一方のプレイヤーが余分なスペース文字を追加した場合）、両方のプログラムが不正行為を行う。以下の技術の開発は、この脆弱性の問題が一因となっている。

証明に基づく協力

別のアプローチは、各プレイヤーのプログラムが相手のプログラムについて、あるいは2つのプログラムがどのように関連しているかについて何かを証明しようとすることに基づいています。^{[ 6 ]}^{[ 8 ]}^{[ 9 ]}^{[ 10 ]}そのようなプログラムの1つは次のとおりです。

アルゴリズムFairBot(opponent_program): 反対プログラム(this_program)が協力的であるという証明があれば協力 的 を返す、そうでなければ 欠陥を返す

Löbの定理を用いると、両方のプレイヤーがこのプログラムを提出した場合、互いに協力し合うことが示される。^{[ 8 ]}^{[ 9 ]}^{[ 10 ]}さらに、一方のプレイヤーが上記のプログラムに反するプログラムを提出した場合、（証明システムの一貫性が使用されると仮定すると）if条件は偽となり、上記のプログラムは反することになる。したがって、（FairBot,FairBot）もプログラム均衡である。

ε接地シミュレーションとの連携

別の提案プログラムは次のとおりです。^{[ 5 ]}^{[ 11 ]}^{[ 12 ]}

アルゴリズム $\epsilon$ GroundedFairBot(対戦相手プログラム): 確率 $\epsilon$ : 協力を 返すreturn 対戦相手プログラム(this_program)

ここ $\epsilon$ は小さな正の数です。

両方のプレイヤーがこのプログラムを提出した場合、ほぼ確実に終了し、協力します。終了までの期待ステップ数は等比級数で与えられます。さらに、両方のプレイヤーがこのプログラムを提出した場合、どちらも利益を得られるような逸脱はできません。 $\epsilon$ は十分に小さいので、確率で裏切る $\Delta$ 相手を裏切る可能性が高い $(1-\epsilon )\Delta$ 。

フォーク定理

本稿では、プログラム均衡において達成可能な利得を特徴づける定理を示す。

この定理では、次の用語を使用します。一対の利得 $(v_{1},v_{2})$ （混合戦略の）ペアが存在する場合、それは実行可能であると呼ばれる。 $(s_{1},s_{2})$ そのため $u_i(s_1,s_2)=v_i$ 両プレイヤーにとって $i$ つまり、ある戦略プロファイルで達成される場合、ペイオフのペアは実行可能であると呼ばれます。ペイオフ $v_{i}$ が、そのプレイヤーのミニマックス利得よりも優れている場合、それは個別に合理的であると呼ばれます。つまり、 $v_{i}\geq \min _{\sigma _{-i}}\max _{s_{i}}u_{i}(\sigma _{-i},s_{i})$ ここで最小値は、プレイヤーのすべての混合戦略についてである。 $-i$ [^注^{2 ]}

定理（プログラム均衡に関するフォーク定理）：^{[ 4 ]}^{[ 1 ]} Gを基本ゲームとする。 $(v_{1},v_{2})$ を実数値の利得のペアとする。このとき、以下の2つの主張は同等である。

報酬 $(v_{1},v_{2})$ 実現可能であり、個々に合理的である。
プログラムの均衡が存在する $(p_{1},p_{2})$ 利益をもたらす $(v_{1},v_{2})$ 。

この結果は、均衡利得に関する同じ条件を用いる繰り返しゲームに関するいわゆるフォーク定理（ゲーム理論）にちなんで、フォーク定理と呼ばれている。 $(v_{1},v_{2})$ 。

注記

↑プログラムゲーム内のプログラムが自身のソースコードにアクセスできる必要はありません。対角化補題により、クイニングを使用してプログラムが自身のソースコードを参照できるようにすることができます。^{[ 2 ]}^{[ 3 ]}^{[ 4 ]}
↑同様に、（フォン・ノイマンのミニマックス定理により） $v_{i}\geq \max _{\sigma _{i}}\min _{s_{-i}}u_{i}(\sigma _{i},s_{-i})$ 最大値は、すべての混合戦略についてです。 $\displaystyle \sigma _{i}}$ プレイヤー向け $i$ 。

参考文献

1 2 3 4 Tennenholtz, M. (2004年11月). 「プログラム均衡」. Games and Economic Behavior . 49 (2). Elsevier : 363– 373. doi : 10.1016/j.geb.2004.02.002 . ISSN 0899-8256 .
1 2 3 McAfee, RP (1984 年 5 月).経済的意思決定における効果的な計算可能性(PDF) (技術報告書). ウェスタンオンタリオ大学.
1 2 3 Howard, JV (1988 年 5 月). 「囚人のジレンマにおける協力」. Theory and Decision . 24 (3). Kluwer Academic Publishers : 203– 213. doi : 10.1007/BF00148954 . S2CID 121119727 .
1 2 3ルビンシュタイン、A. (1998). 「第 10.4 章」。『限定合理性のモデリング』。MIT Press。ISBN 978-0262681001。
1 2 3 Oesterheld, C. (2019 年 2 月). 「ロバストプログラム均衡」 . Theory and Decision . 86. Springer : 143–159 . doi : 10.1007 /s11238-018-9679-3 . S2CID 255103752 .
1 2 van der Hoek, W.; Witteveen, C.; Wooldridge, M. (2013). "Program equilibrium—a program reasoning approach". International Journal of Game Theory . 42 (3). Springer : 639–671 . CiteSeerX 10.1.1.228.6517 . doi : 10.1007/s00182-011-0314-6 . S2CID 253720520 .
↑ Peters, Michael; Szentes, Balázs (2012年1月)。「定義可能かつ契約可能な契約」(PDF)。Econometrica 。80 ( 1 )。The Econometric Society : 363–411。doi : 10.3982 /ECTA8375。
1 2 Barasz, M.; Christiano, P.; Fallenstein, B.; Herreshoff, M.; LaVictoire, P.; Yudkowsky, E. (2014). "囚人のジレンマにおける堅牢な協力: 証明可能性論理によるプログラム均衡". arXiv : 1401.5577 [ cs.GT ].
1 2 Critch, A. (2019). "Löbの定理のパラメトリックでリソース制限付きの一般化とオープンソースゲーム理論のための堅牢な協力基準". Journal of Symbolic Logic . 84 (4). Cambridge University Press : 1368– 1381. doi : 10.1017/jsl.2017.42 . S2CID 133348715 .
1 2 Critch, A.; Dennis, M.; Russell, S. (2022). "協力的および非協力的な制度設計: オープンソースゲーム理論における驚きと問題点". arXiv : 2208.07006 [ cs.GT ].
↑ DiGiovanni, A.; Clifton, J. (2023). "条件付き情報開示を伴うコミットメントゲーム". AAAI 人工知能会議議事録. arXiv : 2204.03484 .
↑ Cooper, E.; Oesterheld, C.; Conitzer, V. (2025). "シミュレーションベースのプログラム均衡の特性評価".人工知能に関するAAAI会議議事録. arXiv : 2412.14570 .

[5] プログラムゲーム内のプログラムが自身のソースコードにアクセスできる必要はありません。対角化補題により、クイニングを使用してプログラムが自身のソースコードを参照できるようにすることができます。^{[ 2 ]}^{[ 3 ]}^{[ 4 ]}

[14] 同様に、（フォン・ノイマンのミニマックス定理により） $v_{i}\geq \max _{\sigma _{i}}\min _{s_{-i}}u_{i}(\sigma _{i},s_{-i})$ 最大値は、すべての混合戦略についてです。 $\displaystyle \sigma _{i}}$ プレイヤー向け $i$ 。

[Tennenholtz2004-1] 1 2 3 4 Tennenholtz, M. (2004年11月). 「プログラム均衡」. Games and Economic Behavior . 49 (2). Elsevier : 363– 373. doi : 10.1016/j.geb.2004.02.002 . ISSN 0899-8256 .

[McAfee1984-2] 1 2 3 McAfee, RP (1984 年 5 月).経済的意思決定における効果的な計算可能性(PDF) (技術報告書). ウェスタンオンタリオ大学.

[Howard1988-3] 1 2 3 Howard, JV (1988 年 5 月). 「囚人のジレンマにおける協力」. Theory and Decision . 24 (3). Kluwer Academic Publishers : 203– 213. doi : 10.1007/BF00148954 . S2CID 121119727 .

[Rubinstein1998-4] 1 2 3ルビンシュタイン、A. (1998). 「第 10.4 章」。『限定合理性のモデリング』。MIT Press。ISBN 978-0262681001。

[Oesterheld2019-6] 1 2 3 Oesterheld, C. (2019 年 2 月). 「ロバストプログラム均衡」 . Theory and Decision . 86. Springer : 143–159 . doi : 10.1007 /s11238-018-9679-3 . S2CID 255103752 .

[Hoek2013-7] 1 2 van der Hoek, W.; Witteveen, C.; Wooldridge, M. (2013). "Program equilibrium—a program reasoning approach". International Journal of Game Theory . 42 (3). Springer : 639–671 . CiteSeerX 10.1.1.228.6517 . doi : 10.1007/s00182-011-0314-6 . S2CID 253720520 .

[PetersSzentes2012-8] Peters, Michael; Szentes, Balázs (2012年1月)。「定義可能かつ契約可能な契約」(PDF)。Econometrica 。80 ( 1 )。The Econometric Society : 363–411。doi : 10.3982 /ECTA8375。

[Barasz2014-9] 1 2 Barasz, M.; Christiano, P.; Fallenstein, B.; Herreshoff, M.; LaVictoire, P.; Yudkowsky, E. (2014). "囚人のジレンマにおける堅牢な協力: 証明可能性論理によるプログラム均衡". arXiv : 1401.5577 [ cs.GT ].

[Critch2019-10] 1 2 Critch, A. (2019). "Löbの定理のパラメトリックでリソース制限付きの一般化とオープンソースゲーム理論のための堅牢な協力基準". Journal of Symbolic Logic . 84 (4). Cambridge University Press : 1368– 1381. doi : 10.1017/jsl.2017.42 . S2CID 133348715 .

[Critch2022-11] 1 2 Critch, A.; Dennis, M.; Russell, S. (2022). "協力的および非協力的な制度設計: オープンソースゲーム理論における驚きと問題点". arXiv : 2208.07006 [ cs.GT ].

[DiGiovanni2023-12] DiGiovanni, A.; Clifton, J. (2023). "条件付き情報開示を伴うコミットメントゲーム". AAAI 人工知能会議議事録. arXiv : 2204.03484 .

[Cooper2025-13] Cooper, E.; Oesterheld, C.; Conitzer, V. (2025). "シミュレーションベースのプログラム均衡の特性評価".人工知能に関するAAAI会議議事録. arXiv : 2412.14570 .

[ 1 ]

[ 2 ]

[ 3 ]

[

[注1 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

注

プログラム均衡

設定と定義

囚人のジレンマにおける協調的プログラム均衡を達成するための様々なメカニズム

構文比較に基づく協力

証明に基づく協力

ε接地シミュレーションとの連携

フォーク定理

関連項目

注記

参考文献

関連するトピック

ゲーム理論上の

解概念

Moshe Tennenholtzによって導入された。

R. Preston McAfee