看完《黑暗骑士》后，我对囚徒困境的概念非常着迷。必须有一种算法可以在特定情况下最大化自己的收益。
对于那些发现这个外国的人：http ://en.wikipedia.org/wiki/Prisoner%27s_dilemma
非常非常有趣的东西。
编辑：问题是，如果有的话，囚徒困境最有效的算法是什么？
rofly
问问题
6362 次
13 回答
12
由于只有一种选择，并且在没有任何可变输入的情况下，您的算法要么是：
cooperate = true;
...或者...
cooperate = false
为迭代囚徒困境寻找策略更有趣，这是很多人都做过的事情。例如http://www.iterated-prisoners-dilemma.info/
即使那样，它也不是“可解决的”，因为其他玩家是不可预测的。
于 2008-09-24T12:26:36.000 回答
7
维基百科页面似乎给出了所有答案......对于一次性囚徒困境，每个囚犯（不是两个囚犯）的最佳解决方案是背叛。
对于迭代囚徒困境，最好在第一次尝试时保持沉默，然后在最后一次执行其他囚徒所做的任何事情。
于 2008-09-24T12:22:19.537 回答
3
困境的全部意义在于最佳解决方案（两名囚犯都保持安静）是危险的，因为部分问题不在你的掌控之中。所以，选择次优的解决方案似乎可以最大化你的收益，但它仍然是次优的
当部分问题是未知的时，我看不出算法如何提供解决方案。
于 2008-09-24T12:17:48.783 回答
3
我推荐阅读Axelrod 的《合作的演变》。这是针对迭代囚徒困境的竞争策略的计算机实验。上次听说的时候，针锋相对的策略先出来了。它可能已经改变了。
于 2008-09-24T12:27:34.233 回答
3
对于一次性版本的游戏，最好的策略总是背叛，因为没有报复的机会。
迭代版本变得更有趣，因为玩家可以回应对手之前的选择。
如果我们事先确切知道会有多少轮，那么合乎逻辑的“最佳”策略仍然是总是背叛。这是因为在最后一回合背叛总是有意义的，因为没有报复的机会。当然，我们理性的对手会知道这一点，而且总是在最后一回合背叛。这让我们在倒数第二回合叛逃是明智的，因为无论如何在最后一回合都没有合作的机会。按照这个逻辑得出它的自然结论，我们应该每时每刻都背叛。
当总轮数未知时，事情变得更加有趣。一个好的游戏策略应该尝试预测对手会做什么。我研究了使用进化算法和简单的机器学习与对手建模来为我的硕士学位生成游戏策略。如果你真的有兴趣，可以阅读我的论文。
正如 Yuval 推荐的那样，最好的起点可能是Axelrod 的开创性著作。如果你真的对这些东西很感兴趣，有一个20 周年的后续活动，其中包括其他研究人员最近关于 IPD（迭代囚徒困境）的许多工作。
另外，我彻底推荐了威廉庞斯通的囚徒困境，这是约翰冯诺依曼的部分传记和博弈论的部分介绍。
于 2008-09-24T18:26:51.360 回答
1
好吧，据我了解，模式识别也是其中的重要组成部分。找出其他囚犯的习惯——他保持安静的频率以及他何时发情。您还必须将其与您自己的选择进行交叉引用，以确定您做了什么让他以某种方式做出反应。
我认为它比维基解释的要复杂一些。这不仅仅是囚犯在最后一次做的事情，而且在那之前的所有事情上都一直延伸到无穷大。
于 2008-09-24T12:24:13.557 回答
0
于 2008-09-24T12:21:55.060 回答
0
没有，因为你不能断然预测第二个囚犯的行为。
有各种各样的“解决方案”可以对第二个囚犯的行为做出基本但非常严格的假设，但他们对不受约束的问题几乎没有什么可说的（这就是使它成为如此令人信服的困境的原因）。
我的两分钱，鉴于您不能依赖第二个囚犯的行为，归根结底是：您是乐观主义者，还是愤世嫉俗者？两个囚犯是要粘在一起（盗贼中的荣誉），还是他们会一有机会就互相指责以挽救自己的喉咙……？
于 2008-09-24T12:23:50.140 回答
0
此外，在迭代的囚徒博弈中，最优策略将根据游戏中的其他策略而有所不同。
在系列赛中对抗一个总是背叛总是背叛的球员是最好的策略。在与可能会合作的玩家对抗时，采取报复但偶尔原谅的策略可能是最好的。
我应该补充一点，这仅适用于长度未知的游戏。任何已知长度的游戏都与单轮游戏相同。
于 2008-09-24T12:24:18.080 回答
0
尝试为囚徒困境找到最佳解决方案就像尝试为 Ro-Sham-Bo（石头剪刀布）找到一个最佳解决方案。您能做的最好的事情就是模拟您的对手并尝试利用模式。
在博弈论和计算机科学的早期，约翰·冯·诺依曼和兰德公司花费了大量的头骨汗水试图提出一个解决囚徒困境的最佳算法，但没有成功，iirc 最终在数学上证明没有最优解。
于 2008-09-24T12:26:20.697 回答
0
囚徒困境的全部意义在于，你的最佳策略是背叛另一个囚徒。O(1)
于 2008-09-24T13:00:34.483 回答
0
从数学上讲，其他帖子回答了这个问题，但实际上，可能还有其他选择。无论这些选择多么荒谬，它们都会带来额外的结果可能性，并且可能会增加个人收益的机会。例如，在蝙蝠侠的情况下，它会破坏情节，但他本可以杀死小丑——从而破坏小丑对结果的任何额外影响。通过让小丑活着，蝙蝠侠不知不觉地让小丑获得了他唯一需要的“胜利”。
于 2008-09-24T18:32:27.867 回答
0
当您退后一步并考虑整个锦标赛时，游戏会变得更加有趣。例如，几年前，一个来自英国的团队赢得了 PD 锦标赛，该团队提交了多个参赛作品。其中一个是“主人”，另一个是“奴隶”。他们都将从播放特定的动作序列开始，这将使主人和奴隶能够相互识别。一旦识别出主节点将背叛，从节点将在其余的迭代中合作。因此，主人赢得了比赛，但牺牲了奴隶。
该策略具有经济意义，因为第一名有金钱奖励，但进入成本很低。
更一般地说，在为 TD 锦标赛编写程序时，您需要着眼于大局：
- 奖品如何颁发？
- 你能和其他参赛者合谋吗？
- what are the costs of entry? penalties?
Otherwise, yes, the dominant strategy is to defect in the one-shot PD. Axelrod, as others mentioned, showed that tit-for-tat was robust in a series of tournaments, but in these tournaments nobody thought about conspiring with other contestants.
于 2008-09-25T19:54:10.643 回答