人工智能博弈

人工智能博弈

1.博弈相关概念（纳什均衡）

基本术语

• 策略：参与者可以采取的行动方案，是一整套在采取行动之前就准备好的完整方案
  • 混合策略：参与者通过一定概率分布来选择若干个不同的策略
  • 纯策略：参与者每次行动都选择某确定的策略
• 博弈论的研究范式：建模者对玩家规定可采取的策略集和取得的收益，观察当参与者选择若干策略以最大化其收益时会产生什么结果。

博弈论的分类

• 玩家合作博弈与非合作博弈
  • 合作博弈：部分玩家可组成联盟以获取更大的收益
  • 非合作博弈：参与者在决策中都彼此独立，不合作
• 静态博弈与动态博弈
  • 静态博弈：所有参与者同时决策（参与者互不知道对方的决策）
  • 动态博弈：根据规则先后行动，后行动者知道先行动者策略
• 完全信息博弈与不完全信息博弈
  • 完全信息：所有玩家均了解其他玩家的策略集、收益等信息
  • 非完全信息：补集

纳什均衡

• 指的是一组策略，其中每个玩家在其他玩家的策略固定的情况下，无法通过改变自己的策略来获得更好的结果。在纳什均衡下，每个玩家的选择是对其他玩家的选择产生的影响做出的最佳响应。
  • 囚徒困境两人同时相互举报就是这一问题的Nash均衡

• 纳什均衡并不一定代表最优解，而是在给定其他玩家的策略时，每个玩家都选择了使自己最优化的策略。
  • 囚徒困境的最优解为两人同时沉默，均衡解为两人同时相互举报

• Nash定理：若参与者有限，每位参与者的策略有限，收益函数为实函数，则博弈必定存在混合意义下的Nash均衡

策梅洛定理
对于任意一个有限步的双人完全信息零和博弈，一定存在先手必胜策略或后手必胜策略或双方保平策略。

最优反应策略
在给定其他玩家的策略组合（可选的策略）的情况下，此玩家所能选择的使其收益达到最大的策略。
最优反应策略通常基于对其他玩家可能采取的策略的假设</，而不是确切地知道其他玩家实际采取了哪种策略。在博弈中，玩家通常面临不确定性，并且很难准确了解其他玩家的内部思维和决策。

• 若每个玩家相对其他玩家的策略而言都是最佳反应策略，则所有玩家的策略构成一个Nash均衡。
• 在有限对手、有限策略的情况下，Nash均衡一定存在。
  • 计算资源有限，需要找到近似Nash均衡。

遗憾匹配
在得到玩家i的所有可选策略的遗憾值后，可以根据遗憾值的大小来选择后续第T+1轮博弈的策略。
遗憾值为负数的策略不能提升下一时刻的收益。

虚拟遗憾最小算法
一种根据以往博弈过程中所得遗憾程度来选择未来行为的方法。
1.初始化遗憾值和累加策略表为0
2.采用随机选择的方法来决定策略
3.利用当前策略与对手进行博弈
4.计算每个玩家采取每次行为后的遗憾值
5.根据博弈结果计算每个行动的累加遗憾值大小来更新策略
6.重复3)到5)步若干次，不断的优化策略
7.根据重复博弈最终的策略，完成最终的动作选择