algorithm - 囚人のジレンマアルゴリズム

Question

ダークナイトを見た後、私は囚人のジレンマの概念に夢中になりました。状況に応じて自分自身の利益を最大化するアルゴリズムが存在する必要があります。

この外国人を見つける人のために: http://en.wikipedia.org/wiki/Prisoner%27s_dilemma

非常に興味深い内容です。

編集: 問題は、囚人のジレンマのために存在する最も効率的なアルゴリズムが存在する場合、それは何ですか?

score 12 · Accepted Answer

選択できるのは 1 つだけであり、変更可能な入力がない場合、アルゴリズムは次のいずれかになります。

cooperate = true;

...また...

cooperate = false

反復囚人のジレンマに対する戦略を見つけることは、より興味深いことです。これは、多くの人が行ってきたことです。たとえばhttp://www.iterated-prisoners-dilemma.info/

それでも、他のプレイヤーは予測できないため、「解決可能」ではありません。

score 7 · Accepted Answer

ウィキペディアのページはすべての答えを与えているようです... 1 回限りの囚人のジレンマについては、各囚人 (両方の囚人ではない) にとって最適な解決策は裏切ることです。

繰り返される囚人のジレンマについては、最初は黙っていて、その後は他の囚人が最後に行ったことをすべて行うのが最善です。

score 3 · Accepted Answer

ゲームの 1 回限りのバージョンの場合、報復の可能性がないため、最善の戦略は常に脱走することです。

プレイヤーは対戦相手の以前の選択に応答できるため、反復バージョンではより興味深いものになります。

ラウンド数が正確に事前にわかっている場合、論理的な「最善の」戦略は、常に裏切ることです。これは、報復の可能性がないため、最後のターンで裏切ることが常に理にかなっているからです。もちろん、私たちの合理的な対戦相手はこれを知っており、最後のターンで常に裏切ります。いずれにせよ、最終ターンで協力する機会がないため、これにより、最後から 2 番目のターンで離脱することが賢明になります。この論理に従って自然な結論に達すると、あらゆるターンで裏切る必要があります。

ラウンドの総数が不明な場合、事態はより興味深いものになります。ゲームの優れた戦略とは、対戦相手が何をするかを予測することです。私は、進化的アルゴリズムと単純な機械学習を対戦相手のモデリングとともに使用して研究し、修士課程のゲームの戦略を生成しました。本当に興味があるなら、私の論文を読んでください。

Yuval が推奨するように、おそらく開始するのに最適な場所はAxelrod の独創的な本です。あなたが本当にこのことに興味を持っているなら、他の研究者によるIPD（反復囚人のジレンマ）に関する多くの最近の研究を含む20周年記念のフォローアップがありました.

また、ジョン・フォン・ノイマンの伝記であり、ゲーム理論の紹介でもある、ウィリアム・パウンドストーンの『囚人のジレンマ』を徹底的にお勧めします。

score 3 · Accepted Answer

ジレンマの全体的なポイントは、問題の一部はあなたの手の及ばないため、最適な解決策 (両方の囚人が黙っている) が危険であるということです。したがって、次善のソリューションを選択すると、利益が最大化されるように見えますが、それでも最適ではありません。

問題の一部が未知である場合、アルゴリズムがどのように解決策を提供できるかわかりません。

score 3 · Accepted Answer

Axelrod の The Evolution of Cooperationを読むことをお勧めします。これは、反復された囚人のジレンマに対する競合する戦略のコンピューター実験です。最後に聞いたときは、しっぺ返し戦略が最初に出てきました。変更された可能性があります。

score 1 · Accepted Answer

私の理解では、パターン認識もその大きな部分を占めています。他の受刑者の癖を見つける - どのくらいの頻度で静かにしているのか、いつ酔っ払っているのか。また、それを自分の選択と相互参照して、彼を特定の方法で反応させるために何をしたかを判断する必要があります.

ウィキで説明されているよりも少し複雑だと思います。それは、囚人が最後に行ったことだけでなく、その前に無限に広がるすべてのことです.

score 0 · Accepted Answer

囚人のジレンマの要点は、あなたの最適な戦略は他の囚人を裏切ることであるということです。O（1）

score 0 · Accepted Answer

一歩下がってトーナメント全体を考えると、ゲームはさらに面白くなります。たとえば、数年前の PD トーナメントでは、複数のエントリーを提出した英国のチームが優勝しました。そのうちの1人は「マスター」で、もう1人は「スレーブ」でした。それらはすべて、マスターとスレーブがお互いを認識できるようにする特定の一連のアクションを実行することから始まります。認識されると、マスターは裏切り、スレーブは残りの反復で協力します。したがって、マスターはトーナメントに勝ちましたが、奴隷を犠牲にしました。

この戦略は、1 位には賞金がありましたが、参加費が低かったため、経済的に理にかなっています。

より一般的には、TD トーナメント用のプログラムを作成するときは、全体像を見る必要があります。

賞品はどのように授与されますか？
他の競技者と共謀できますか?
エントリー費用は？罰則？

そうでなければ、支配的な戦略は、ワンショット PD で失敗することです。他の人が言及したように、アクセルロッドは、一連のトーナメントでしっぺ返しが強いことを示しましたが、これらのトーナメントでは、誰も他の競技者と共謀することを考えませんでした.

score 0 · Accepted Answer

囚人のジレンマの最適な解決策を見つけようとすることは、ローシャムボー (じゃんけん) の最適な解決策を見つけようとするようなものです。最善の方法は、対戦相手をモデル化し、パターンを利用しようとすることです。

ゲーム理論とコンピュータサイエンスの黎明期、ジョンフォンノイマンとランド社は、囚人のジレンマを解決するための最適なアルゴリズムを考え出すために多大な汗をかきましたが、成功しませんでした。最適解。

score 0 · Accepted Answer

数学的には他の投稿が質問に答えていますが、実際には追加のオプションがあるかもしれません。これらのオプションがどれほどばかげているとしても、追加の結果の可能性をもたらし、個人的な利益の可能性を高める可能性があります. たとえば、バットマンの場合、それは陰謀を台無しにするでしょうが、彼はジョーカーを殺した可能性があります-したがって、ジョーカーが結果に与える追加の効果を台無しにします. ジョーカーを生かしておくことで、バットマンは無意識のうちにジョーカーに必要な唯一の「勝利」を与えてしまいます。

score 0 · Accepted Answer

そうそう。これにより、ソフトウェア開発における囚人のジレンマに関するこの古い記事を思い出しました。

アルゴリズム PD コンテストについては、こちらをご覧ください

これもいいものでした

score 0 · Accepted Answer

2 番目の囚人の行動を断固として予測することはできないため、ありません。

2 番目の囚人の行動について、根底にあるが非常に制限的な仮定を行うあらゆる種類の「解決策」がありますが、制約のない問題についてはほとんど語っていません (それが、非常に説得力のあるジレンマになっている理由です)。

2 番目の囚人の行動に頼ることができないことを考えると、私の 2 セントは、次のようになるということです。あなたは楽観主義者ですか、それとも皮肉屋ですか? 二人の囚人はくっつくのか（泥棒の名誉）、それとも自分の喉を救うために最初の機会にお互いを殴り合うのか...？

score 0 · Accepted Answer

さらに、繰り返される囚人のゲームでは、最適な戦略はプレイ中の他の戦略によって異なります。

常に裏切るプレイヤーに対するシリーズでは、常に裏切ることが最善の戦略です。協力する可能性のあるプレーヤーと対戦する場合は、報復するが時々許す戦略が最善の可能性があります。

これは、長さが不明なゲームにのみ適用されることを付け加えておきます。既知の長さのゲームは、シングルラウンドゲームと同じです。

algorithm - 囚人のジレンマアルゴリズム

13 に答える 13

Related

Reference