Loading article…
分散アルゴリズムメカニズム設計(DAMD) は、アルゴリズムメカニズム設計の拡張です。
DAMD は、アルゴリズムが中央機関ではなく分散方式で計算される点で、アルゴリズム メカニズム設計とは異なります。これにより、ネットワーク内のすべてのエージェントによって負荷が共有されるため、計算時間が大幅に短縮されます。
DAMD における大きな障害の 1 つは、エージェントが特定のシナリオに関連する真のコストや好みを明らかにするようにすることです。多くの場合、これらのエージェントは、自分の効用を向上させるために嘘をつく傾向があります。合理的なプレーヤーがメッセージ パスとメカニズムの計算を制御する従順なネットワークとメカニズムのインフラストラクチャを想定できなくなったため、DAMD には新たな課題が山積しています。
ゲーム理論モデル
ゲーム理論と分散コンピューティングはどちらも、多くのエージェントを持つシステムを扱い、エージェントは異なる目標を追求する可能性があります。しかし、両者の焦点は異なります。たとえば、分散コンピューティングの関心事の 1 つは、障害のあるエージェントや同時にアクションを実行するエージェントを許容するアルゴリズムの正しさを証明することです。一方、ゲーム理論では、システムの均衡につながる戦略を考案することに焦点が当てられています。 [1]
ナッシュ均衡
ナッシュ均衡はゲーム理論で最も一般的に使用される均衡の概念です。しかし、ナッシュ均衡は誤った行動や予期しない行動には対処しません。ナッシュ均衡に到達したプロトコルは、合理的なエージェントに対して正しく実行されることが保証されており、プロトコルから逸脱することでその効用を向上させることができるエージェントは存在しません。[2]
ソリューションの好み
AMDのような信頼できるセンターは存在しません。したがって、メカニズムはエージェント自身によって実装される必要があります。ソリューションの好みの仮定では、各エージェントが結果がまったくない場合よりも、どのような結果でも好む必要があります。したがって、エージェントには結果に同意しなかったり、アルゴリズムを失敗させたりする動機がありません。言い換えると、Afek らが述べたように、「アルゴリズムが失敗してもエージェントは利益を得ることができません」。[3]結果として、エージェントは好みを持っていますが、アルゴリズムを失敗させる動機はありません。
誠実さ
エージェントが自分や他のエージェントの価値について嘘をついても何も得られない場合、メカニズムは誠実であるとみなされます。良い例としては、ネットワーク内の計算サーバーを選択するリーダー選出アルゴリズムが挙げられます。このアルゴリズムでは、エージェントが互いに計算能力の合計を送信し、その後最も強力なエージェントがタスクを完了するリーダーとして選ばれます。このアルゴリズムでは、エージェントが実際の計算能力について嘘をつく可能性があります。CPU を集中的に使用するジョブを課せられる危険があり、ローカルジョブを完了する能力が低下する可能性があるためです。これは、各エージェントの既存のデータと入力に関する事前の知識がなくても、各エージェントが要求に誠実に応答するようにする誠実メカニズムの助けを借りて克服できます。[4]
ゲーム理論におけるよく知られた真実のメカニズムは、ヴィックリーオークションです。
典型的な分散コンピューティングの問題
リーダー選出（完全接続ネットワーク、同期の場合）
リーダー選出は分散コンピューティングの基本的な問題であり、この問題を解決するプロトコルは数多くあります。システム エージェントは合理的であると想定されているため、リーダーがいないよりもいる方が望ましいです。エージェントは、誰がリーダーになるかに関して異なる好みを持つこともあります (エージェントは自分がリーダーになることを望む場合があります)。標準プロトコルは、システム エージェントの最低または最高の ID に基づいてリーダーを選択します。ただし、エージェントは自分の効用を向上させるために ID について嘘をつくインセンティブがあるため、このようなプロトコルはアルゴリズム メカニズム設計の設定では役に立ちません。
合理的なエージェントが存在する場合のリーダー選出プロトコルは、Ittai らによって導入されています。
- ラウンド 1 では、各エージェント i が自分の ID を全員に送信します。
- ラウンド 2 では、エージェント i は、受け取った ID のセット (自分自身の ID を含む) を他のエージェント j に送信します。エージェント i が受け取ったセットがすべて同一でない場合、または i がいずれかのエージェントから ID を受信しなかった場合、i は出力を Null に設定し、リーダー選出は失敗します。それ以外の場合、ID セットの基数を n とします。
- エージェントiは{0, ..., n−1}の中から乱数N iを選択し、それを他のすべてのエージェントに送信します。
- 各エージェントiはΣを計算する。1 の場合
N i (mod n) を実行し、セット内で N 番目に高い ID を持つエージェントをリーダーにします。(エージェント j が ia に乱数を送信しない場合、i はその出力を Null に設定します。)
このプロトコルは、均衡に到達しながらリーダーを正しく選出し、エージェントが入力について嘘をつくことで利益を得ることができないため、真実である。[5]
参照
参考文献
- ^ Halpern, Joseph Y. (2008). 「コンピュータサイエンスとゲーム理論：簡単な調査」。新パルグレイブ経済学辞典。doi : 10.1057 /978-1-349-95121-5_2133-1。
- ^ マーティン、オズボーン、ルビンスタイン、アリエル (1994)。ゲーム理論のコース。MIT 出版。
- ^ Afek, Yehuda ; Ginzberg, Yehonatan ; Feibish, Shir Landau; Sulamy, Moshe (2014). 「合理的エージェントのための分散コンピューティング ビルディング ブロック」。2014 ACM シンポジウム「分散コンピューティングの原理」の議事録。pp. 406–415。doi :10.1145/ 2611462.2611481。ISBN 9781450329446.S2CID 2048291 。
- ^ Shneidman, Jeffrey; Parkes, David (2004)。「有理ノードを持つネットワークにおける仕様の忠実性」。第 23 回 ACM シンポジウム「分散コンピューティングの原理」の議事録。p . 88。doi : 10.1145 /1011767.1011781。ISBN 1581138024. S2CID 5518144。
- ^ Abraham, Ittai; Dolev, Danny (2013). 「リーダー選挙のための分散プロトコル：ゲーム理論的観点」DISC : 61–75。
外部リンク
- [1] 分散アルゴリズムメカニズム設計：最近の成果と今後の方向性
- [2] 分散アルゴリズムメカニズム設計とネットワークセキュリティ
- [3] ヴィックレイオークションを用いた利己的モバイルアドホックネットワークにおけるサービス割り当て