Introduction and Overview

SOE - YCS0002
Instructors: Matthew O. Jackson, Kevin Leyton-Brown, Yoav Shoham
URL: https://www.coursera.org/learn/game-theory-1/home/week/1

1-1 Game Theory Intro - TCP Backoff

【经典场景】Backoff Game：退避游戏

TCP Backoff 是计算机网络中TCP协议的退避机制(Backoff Mechanism)

TCP Backoff Game

设情况为双人游戏 （Player A和Player B），玩家可以选择使用正确实现（Correct）或有缺陷的实现（Defective）的通信协议：

  • 双方使用正确实现协议： 双方延迟 1 ms；
  • 一方使用正确，一方使用缺陷实现协议：正确实现者延迟 4 ms， 缺陷实现者延迟 0 ms；
  • 双方使用缺陷实现协议：双方延迟 3 ms。

可根据要求定义支付矩阵（Payoff Matrix），描述可能的策略组合对应的结果：

Player B (Correct) Player B (Defective)
Player A (Correct) -1，-1 -4，0
Player A (Defective) 0，-4 -3，-3

可视这个博弈为纳什均衡博弈（Nash Equilibrium），在这个博弈中有两个纳什均衡，既（Correct, Correct）和（Defective, Defective）。若双方都做出正确的实现，将获得最佳结果。若其中一方选择有缺陷实现则另一方也将收到机理选择缺陷的实现避免更大的损失。在这种撞他爱夏，没有玩家有动机单方面改变自己的策略。

1-2 Self-Interested Agents and Utility Theory

自利代理人 (Self-interested Agents)：在决策过程中主要考虑自身利益最大化的个体或实体。

效用 (utility)：一个量化的指标，用来衡量个体偏好和满意度的一个概念。

自利代理人 效用
行为主体，追求最大化个人利益 决策过程中的量化指标，衡量个体从特定结果中获得的满足程度
在博弈中根据效用函数选择策略 影响策略选择，是策略选择的依据
动态变化，根据博弈进展调整策略 静态评估，但可能随策略选择而变化
强调个体利益 可以是个体的，也可以是集体的，影响集体决策
策略的制定者 策略选择的结果，指导策略选择
策略选择影响效用 效用评估影响策略调整

这个表格展示了自利代理人与效用之间的联系。自利代理人通过追求效用最大化来制定策略，而效用则是这些策略选择的量化结果。两者在博弈论中相互作用，共同影响博弈的进程和结果。

1-3 Defining Games

博弈论的关键组成部分通常包括以下几个方面：

  1. 玩家（Players）：参与博弈的个体或实体，可以是个人、公司、国家等。

  2. 策略（Strategies）：玩家在博弈中可能采取的行动或决策。策略可以是纯策略（单一选择）或混合策略（概率分布下的多种选择）。

  3. 支付（Payoffs）：每个玩家根据博弈结果可以获得的收益或效用。支付可以是货币价值、地位、资源等。

  4. 信息（Information）：玩家在博弈中所拥有的关于游戏规则、其他玩家策略以及游戏状态的知识。

  5. 规则（Rules）：定义博弈如何进行的一系列约束条件，包括玩家的行动顺序、信息传递方式等。

  6. 结果（Outcomes）：博弈的最终状态，是所有玩家策略组合的结果。

  7. 均衡（Equilibrium）：在均衡状态下，所有玩家都没有动机单方面改变策略。纳什均衡是博弈论中最著名的均衡概念。

  8. 博弈类型（Game Type）：描述博弈的基本特征，如零和博弈、非零和博弈、合作博弈、非合作博弈等。

  9. 动态（Dynamics）：博弈可能涉及的时间序列，包括动态博弈中的策略演变和适应过程。

  10. 解决方案（Solution Concepts）：解释博弈结果的理论框架，如纳什均衡、子博弈完美均衡、进化稳定策略等。

这些组成部分共同构成了博弈论的基础，使得我们能够分析和理解在不同情境下个体如何做出决策以及这些决策如何相互作用。

博弈的标准表达式通常指的是博弈论中用来描述博弈结构的数学模型。对于不同类型的博弈，标准表达式可能有所不同，但通常包括以下几个关键元素：

  1. 玩家集合（Players）：用集合表示参与博弈的个体或实体，如P = {1, 2, ..., n}。

  2. 策略集合（Strategy Sets）：对于每个玩家，定义一个策略集合，如SiS_i 表示玩家i的策略集合。

  3. 支付函数（Payoff Functions）：描述每个玩家在特定策略组合下的收益，通常用 ui(s)u_i(s) 表示玩家i在策略组合s下的效用，其中s是所有玩家策略的向量。

  4. 博弈类型（Game Type）：根据博弈的性质，如零和博弈、非零和博弈、完全信息博弈、不完全信息博弈等，来确定博弈的具体形式。

  5. 博弈描述（Game Description）：描述博弈的具体情况，如博弈是同时行动还是顺序行动，玩家是否有共同知识等。

  6. 均衡概念（Equilibrium Concepts）：描述博弈中可能达到的均衡状态，如纳什均衡、子博弈完美均衡、贝叶斯均衡等。

对于不同类型的博弈，标准表达式可能包括：

  • 同时行动博弈（Simultaneous Games）：通常用支付矩阵来表示，其中每一行代表一个玩家的策略，每一列代表另一个玩家的策略，矩阵中的每个单元格代表相应策略组合下的支付。

  • 顺序行动博弈（Sequential Games）：通常用扩展形式（Extensive Form）表示，包括决策树（Decision Tree）和博弈树（Game Tree），其中节点代表玩家的决策点，边代表策略选择，叶子节点代表游戏的终端状态和支付。

  • 不完全信息博弈（Incomplete Information Games）：用贝叶斯博弈（Bayesian Games）表示，其中包括类型（Types）和信念（Beliefs）等元素。

  • 演化博弈（Evolutionary Games）：用演化稳定策略（Evolutionarily Stable Strategies, ESS）和复制者动态（Replicator Dynamics）等概念来描述。

这些标准表达式为博弈论提供了一种通用的语言，使得研究人员能够清晰地描述和分析各种复杂的博弈情况。

简单的博弈论问题可以使用矩阵表达式，但是复杂的问题会因为维度过高、动态性、非线性和非凸性、不确定型和随机性、多目标和多约束、系统间相互作用、计算资源限制、模型的准确性和简化等因素影响而无法用矩阵表达。

1-4 Examples of Games

囚徒困境

博弈论中最著名的概念之一，它描述了两个理性个体在缺乏沟通和合作机制的情况下，即使合作对双方都有利，也可能导致双方都选择不合作的策略。如下表矩阵所示，其结果的有优劣程度按照 c>a>d>bc>a>d>b 来排序。

C D
C (a, a) (b, c)
D (c, b) (d, d)

纯竞争博弈

在博弈中，双方具有完全对立的利益。对于双方任意动作组合，其效用之和永远为一个常数。对于双方任意动作组合，其效用之和永远为一个常数 a∈A,u1(a)+u2(a)=ca \in A, u_1(a)+u_2(a)=c，当常数 cc 为 0 时，构成了零和博弈。 在零和博弈中，参与者的策略选择直接影响对手的收益，因此，每个玩家都试图最大化自己的收益，同时最小化对手的收益。

合作博弈

参与者之间可以通过合作来达成某种共同利益的博弈。在合作博弈中，玩家可以通过形成联盟（Coalitions）来共同决策，以实现比单独行动时更好的结果。这种博弈的核心在于玩家之间的互动和策略协调。他的特点包括：

  1. 联盟形成：玩家可以自由地组成联盟，联盟可以是任意大小的子集，包括单个玩家或所有玩家的集合。
  2. 合作收益：联盟内部的玩家可以共享收益，这些收益通常来自于合作带来的额外效益。
  3. 分配规则：合作博弈涉及到如何公平地分配联盟内部的总收益。这可能涉及到各种分配规则，如按贡献分配、按需分配等。
  4. 稳定性：在合作博弈中，一个重要的概念是稳定性。一个分配方案是稳定的，如果联盟中的任何子集都无法通过重新分配收益来获得更多的利益。
  5. 解决方案：合作博弈试图找到一种解决方案，该方案能够满足一定的合理性条件，如个体理性、集体理性和公平性等。著名的解决方案包括沙普利值（Shapley Value）、核心（Core）、稳定集（Stable Set）等。

合作博弈与非合作博弈（如囚徒困境）形成对比，后者关注的是玩家在没有约束力的协议下的行为。在非合作博弈中，玩家的策略选择是独立且自私的，而在合作博弈中，玩家可以通过合作来实现共同的目标。

1-5 Nash Equilibrium Intro & 1-6 Strategic Reasoning

描述非合作博弈中的一种稳定状态，每个参与者都选择了对自己最优的策略，且在其他参与者策略不变的情况下，没有任何一个参与者能够通过单方面改变策略来提高自己的收益。其特点如下：

  1. 个体最优性：在纳什均衡下，每个参与者的策略是其在给定其他参与者策略的情况下的最优反应。
  2. 稳定性：一旦达到纳什均衡，没有任何参与者有动机单方面改变策略，因为这样做不会提高其收益。
  3. 预测性：纳什均衡提供了一种预测博弈结果的方法，即在均衡状态下，参与者的行为是可预测的。

1-7 Best Response and Nash Equilibrium

最优响应 (Best Respond, BR)：在给定其他玩家策略的情况下，一个玩家如何做出对自己最有利的策略选择。

ai∗∈BR(a−i)  iff  ∀ai∈Ai, ui(ai∗,a−i)≥ui(ai,a−i)a_i^* \in BR(a_{-i}) \; \text{iff}\; \forall a_i \in A_i, \, u_i(a_i^*,a_{-i})\geq u_i(a_i,a_{-i})

BR(a−i)BR(a_{-i}) 表示已知其他决策信息后第 ii 个决策者做出的最优响应，最优响应不一定只有一个。并且最优相应集合中的所有元素 ai∗a_i^* 都满足下列要求，当且仅当选择 ai∗a_i^* 的效用大于等于选择其他所有响应的效用。

纳什均衡：

a=<a1,...,an>is a ("pure strategy") Nash equilibrium iff  ∀i, ai∈BR(a−i)a=<a_1,...,a_n> \text{is a ("pure strategy") Nash equilibrium iff} \; \forall i,\, a_i \in BR(a_{-i})

最优响应的概念与纳什均衡紧密相关。在纳什均衡中，每个玩家的策略都是对其他玩家策略的最优响应。如果所有玩家都选择了自己的最优响应策略，那么这个策略组合就是一个纳什均衡。

纳什均衡并不一定意味着社会最优或帕累托最优，如：囚徒困境。纳什均衡是一个描述个体理性行为导致的结果，但它并不一定是社会最优解。

1-9 Dominant Strategies

严格支配 (Strictly Dominates):

sistrictly dominatessi’  if  ∀s−i∈S−i, ui(si,s−i)>ui(si′,s−i)s_i \quad \text{\textcolor{darkred}{strictly dominates}} \quad s_i’ \; \text{if} \; \forall s_{-i} \in S_{-i}, \, u_i(s_i,s_{-i})>u_i(s_i',s_{-i})

非常弱支配 (very Weakly Dominates):

sivery weakly dominatessi’  if  ∀s−i∈S−i, ui(si,s−i)≥ui(si′,s−i)s_i \quad \text{\textcolor{darkred}{very weakly dominates}} \quad s_i’ \; \text{if} \; \forall s_{-i} \in S_{-i}, \, u_i(s_i,s_{-i})\geq u_i(s_i',s_{-i})

如果一个决策压制其他所有决策，那么称之为占优策略。如果该决策严格压制每一个其他决策，那么称之为严格占优策略，并且该策略唯一。由占优策略组成的策略组合一定是纳什均衡点，全部由严格占优策略组成的策略组合一定是唯一的纳什均衡点。

1-10 Pareto Optimality

一种资源分配状态，其中任何一方的福利增加都不能不损害至少另一方的福利。帕累托最优并不意味着资源分配是公平的，它只关注效率，而不涉及公平性。在某些情况下，帕累托最优可能导致资源分配非常不平等，因为只要不损害任何人，就可以通过重新分配资源来增加某些人的福利。因此，帕累托最优是一个纯粹的效率概念\textcolor{darkred}{纯粹的效率概念}，而不涉及分配的公平性。

一个决策组合o∗o^*，如果没有其他任何一个决策组合帕累托压制o∗o^* ,那么称该决策组合是帕累托最优。对于零和博弈问题来说，所有决策组合都是帕累托最优。

  • 一场游戏中可能有多个帕累托最优决策组合。
  • 一场游戏中最少含有一个帕累托最优决策组合。