信息不完全博弈中的完美玩法

人工智能 研究 哲学 博弈论 不完整信息
2021-11-09 03:06:53

如标题所示,在信息不完整的游戏中是否存在完美游戏(或至少“完美优化”)?或者至少证明为什么不能?

天真地(并且看起来很明显),答案将是一个响亮的否定,因为代理可能会被迫在“彩票事件”之间进行选择。

但在实践中(使用竞争性视频游戏作为类比),我们会看到玩家会坚持使用元游戏,该元游戏装备精良,可以防御大多数可能发生的事件,因为信息不完整。当然,对此的回应可能是任何给定的元游戏都可能存在“硬反制”,但如果元游戏确实是“最优化”的情况,它可能也是这种情况大多数时候,这样的硬反击会让玩家处于不利的位置,因此“硬反击”本身并不是最优的。因此,我们可能会看到任何给定的第一次遭遇玩家仍然会坚持他们的“最佳元游戏”,而不是硬反击他们的最佳游戏。

更严格的类比是问:“在 Hofstadter 的超理性概念下,代理人将如何玩信息不完全博弈”,但我找不到任何关于试图将超理性概念引入信息不完全博弈的读物。

或者:是否存在“完美最优元游戏”之类的东西?

3个回答

这可能是一个不断发展的答案,因为从某种意义上说,这个问题是一个(有用的)兔子洞。如果我没有深入研究元游戏本身,我深表歉意,因为它有点超出我的范围,这是完美信息的非机会游戏,但我认为值得考虑相关不确定性的潜在问题对一般游戏。

有限理性*是一个有用的概念,因为它预先假定了计算难处理的条件。计算难处理性可以以多种形式引入游戏:

  • 复杂
  • 隐藏信息
  • 随机性(“量子”不确定性)

[有关我在随机性方面使用“量子”的更多详细信息,请参阅确定性游戏。]

博弈论的根本目的是为任何给定问题确定“最优”策略。我把最优放在引号中,因为最优是一个频谱,并且在计算难处理的条件下是主观的。

因此,我们无法知道AlphaGo是否发挥最佳,只能知道它在5 场比赛中有 4 场比李世石 发挥得更好。

这与井字游戏等强解游戏不同,在这种游戏中,我们可以完全确定选择是最优的,因为井字游戏的问题在计算上是易于处理的。

部分混淆可能是语义上的,因为这些概念是微妙而深刻的,并且需要语言,TS Eliot 可能会称之为“与文字和意义的无法忍受的搏斗”。(例如,我在上面使用了隐藏信息来避免区分不完整和不完整的信息。)

  • 完美游戏通常被定义为一种策略,无论对手的选择如何,都能为参与者带来最佳结果。

因此,极小极大至关重要,并为博弈论提供了基础。

即使在信息不完全的博弈中,无论是“确定性”(Battleship)还是涉及“量子不确定性”(Prisoner's Dilemma),都有最优策略。对于诸如Dilemma 和所有众多扩展minimax之类的同步游戏。在 Battleship 中,至少存在三种增加最优性的策略,尽管似乎没有一种策略可以产生 P > .5,但如果一个玩家采用更最优的策略,他们将在总和上获胜。甚至Rock, Paper, Scissors 似乎也有一个最佳策略,这让我大吃一惊,并提醒我需要更多地研究它。

  • 因此,按照定义,完美游戏当然是可以实现的,但并不一定意味着(客观地)最优选择,这有点令人困惑,因为“完美”意味着客观性,这种情况只有在可处理的问题中才有可能。

同样重要的是要注意,可能没有比对手更好的“获胜”策略,在这种情况下,完美或最佳的打法就是减轻损失。


*具体而言,就不完全信息博弈而言,我认为有理由将有限理性的概念扩展到包括无法观察或“知道”的信息。

通俗地说,这将包括“未知”(已知和未知)和“不可知”(量子不确定性和叠加)。

第二个答案试图专门解决与不完整信息相关的完美游戏。

回答这个问题的一个困难因素可能是完美游戏的概念被广泛应用于组合博弈论领域的已解决博弈,而不是严格的经济博弈论。

关于信息不完整的博弈:

  • 完美的游戏,定义为最好的选择,不考虑对手的选择,可能在信息不完整的游戏中实现

重要的是要注意完美的比赛可能不会导致胜利。在井字游戏中,结果是平局。在某些游戏中,对于处于劣势的玩家来说,这可能会导致“最好的”可能的损失。

  • 经典囚徒困境中的完美玩法是极小极大策略。

难题在于,在这个模型中,它不会导致最优结果,而只会导致最优结果,而不考虑其他代理的选择。

在经典的囚徒困境中,补充策略的风险更大,因为没有关于其他代理的信息(任何一种选择的概率始终为 50%)并且它不会限制下行空间。


通过将囚徒困境扩展到迭代和循环,可以证明超理性策略在数学上是可支持的变体。这部分是因为在迭代变体中,选择是代理之间的一种交流形式。然而,超理性策略可能不是制胜策略,因为超理性主体的动机可以说是利益最大化,而不是仅仅限制下行空间。在迭代的囚徒困境中,超理性的智能体可能不得不牺牲几次迭代(转过脸颊)以激励理性的智能体改变策略和合作,并确定另一个智能体是否是非理性的,在这种情况下超理性的代理人可能会转向最小化最大不利因素和最大化最小收益的理性策略。

在经典的迭代困境中,选择是代理之间唯一的通信形式,每个选择都成为另一个代理决策数据集的一部分。信息仍然不完整,但在每次迭代中不那么不完整。

不完全信息博弈的超理性策略通过统计分析变得可行。

这取决于游戏。在零和非合作游戏中是的,总是有 GTO 策略。

最简单的例子是 Rock, Paper, Scissors,其中每个随机播放 1/3 将是唯一的最佳策略。在这种情况下也是收支平衡,在某些游戏中,尽管 GTO 对任何不是 GTO 本身的策略都有积极的预期价值。

通常在线视频游戏的策略和元数据很大程度上基于对人口趋势的适应,这本身并不是完美的游戏,但它可以比与非最佳对手的完美游戏具有更好的预期价值。