巴尔默的二分搜索面试游戏中的纳什均衡

主要观点:John Graham-Cumming 发布关于 Steve Ballmer 错误二进制搜索面试题的内容,引发对二进制搜索是否为解决该谜题正确方法的讨论,通过多个版本的游戏示例计算纳什均衡及预期值等。
关键信息:

  • Ballmer 提出的游戏规则及调整后的数字,讨论二进制搜索在其中的应用及改变预期值的情况。
  • 分别介绍 3 数、4 数、5 数版本游戏的纯策略、支付矩阵、计算各策略的预期值等,得出不同版本的纳什均衡及混合策略。
  • 提及有人用计算机工具如scipy.optimize.linprog改进计算,以及其他人对均衡值范围的研究。
    重要细节:
  • 3 数版本中 Alice 有 3 种纯策略,Bob 有 5 种纯策略,通过计算找到纳什均衡时 Alice 和 Bob 的混合策略及预期值为$22。
  • 4 数版本中 Alice 有 4 种纯策略,Bob 有 7 种纯策略,纳什均衡时 Alice 随机选数,Bob 随机选23后按特定规则猜。
  • 5 数版本中 Alice 有 5 种纯策略,Bob 有 7 种纯策略,存在至少一个纳什均衡,Alice 按特定比例选数,Bob 按特定混合策略猜,预期值为$37.77。
  • 后续有人用计算机工具改进计算及对均衡值范围的研究成果。
阅读 15
0 条评论