参考书目：Shoham, Y., & Leyton-Brown, K. (2008). Multiagent systems: Algorithmic, game-theoretic, and logical foundations. Cambridge University Press.

博弈主体的自利假设与效用函数

效用函数的有效性建立在偏好理论之上。

为了方便，这里引入偏好关系的定义。假设 $O$ 是outcomes的有限集，对于 $O$ 中的任意outcomes对 $o_1, o_2$， 约定 $o_1 \succeq o_2$ 表示agent在面对 $o_1, o_2$ 时对 $o_1$具有弱偏好，换句话说，对于agent来说，单独考虑这两个outcomes，$o_1$不会比$o_2$更坏。强偏好和等偏好关系都可以用弱偏好来定义，因此为了符号简洁，我们只用弱偏好来讨论。

偏好选择需要考虑不确定性，因此将偏好建模为“对某某outcome选择的概率”更合适，也更具有决策价值。为了在不确定性上建模偏好，引入彩票（lottery）的定义，lottery是一个定义在所有outcomes的集合$O$上的概率分布函数，我们将偏好关系的描述对象扩展至outcomes和outcomes上的lotteries，即我们认为lotteries是一种广义上的outcomes。

在上述定义的基础上，可以开始讨论效用理论的若干公理，这些对于偏好关系的公理假设是合理的，并且有利于后续进一步的讨论：

公理1. (完备性) $\forall o_1, o_2, o_1 \succ o_2 \text{ or } o_2 \succ o_1 \text{ or } o_1 \sim o_2$

公理2. (传递性) $\text{if } o_1\succeq o_2 \text{ and } o_2 \succeq o_3 \text{, then } o_1 \succeq o_3$

公理3.(可替代性)若 $o_1 \sim o_2$，则对于任意包含一个或多个结果 $o_3,\ldots,o_k$ 的序列，以及满足 \(p+\sum_{i=3}^{k}p_i=1\) 的概率集合 $p,p_3,\ldots,p_k$，都有 \([p:o_1,p_3:o_3,\ldots,p_k:o_k]\sim[p:o_2,p_3:o_3,\ldots,p_k:o_k].\)

公理4.(可分解性) 若对于所有 $o_i\in O$，均有 \(P_{\ell_1}(o_i)=P_{\ell_2}(o_i),\) 则 \(\ell_1\sim\ell_2.\)

公理5. (单调性)若$o_1\succ o_2$，则在分配$o_1$和$o_2$权重时（总权为1），将$o_1$分配更多权重总是更优的

公理6.(连续性)对于$o_1\succ o_2\succ o_3$，then $\exist p\in [0,1] ,s.t. \text{ }o_2\sim[p:o_1,1-p:o_3]$

冯·纽曼-摩根斯坦效用定理（Von Neumann–Morgenstern utility theorem，简称 VNM效用定理）
If a preference relation $\succeq$ satisfies the axioms completeness, transitivity, substitutability, decomposability, monotonicity, and continuity, then there exists a function(utility function) \(u:\mathcal{L}\mapsto [0,1]\) with the properties that\

1. \(u(o_1)\ge u(o_2) \iff o_1 \succeq o_2,\) and
   2. \(u([p_1:o_1,\ldots,p_k:o_k]) = \sum_{i=1}^{k} p_i u(o_i).\)

值得指出的是，定理中的值域$[0,1]$只是一个representation，效用函数的值域不一定是$[0,1]$，实际上，效用函数的任意正仿射变换后（$u^\prime(o)=au(o)+b, a>0 \text{ and } a,b \text{ are constants}$）都会得到对于同一个agent意义相同的（即同样满足定理中的两条性质的）效用函数。

定理指出，在一系列对偏好关系的合理假设下，agent会存在一个想要maximize的效用函数。这样即使在不确定的环境中，agent仍可以只追求效用函数的最大化，agent只需知道actions的outcomes以及对应的概率。然而在multi-agent的环境中，其他agent的行为会影响到自己的收益，就需要引入博弈论了。

标准形式的博弈

标准形式，或者叫策略式，假设世界的状态只取决于参与者的行为组合。实际上，考虑环境的随机性的情况下，即所谓的贝叶斯式博弈，可以证明能够化约成标准式博弈（只不过相比原来的博弈规模会更大）。很多其他形式的博弈都有其标准化约式。因此，标准式毫无辩驳地是博弈论中最基础的一种。

定义(标准式博弈).
一个有限n人标准式博弈是一个三元组$(N,A,u)$，其中:

• $N$是一个n个参与者的有限集，用$i$索引
• $A=A_1\times \dots \times A_n$，其中$A_i$是参与者$i$的有限行动集，$A$的任一元素向量被称为一个行为组合
• $u=(u_1,\dots,u_n)$，其中$u_i:A\mapsto \mathbb{R}$是参与者$i$的实效用函数(或代价函数)

注意这里效用函数被定义为actions上的映射，这似乎与之前定义为outcomes上的映射冲突，但实际上，标准形式的博弈隐含下列假设：$O=A$。

n人标准式博弈可以用一个n维矩阵来表示。囚徒博弈、纯协作博弈、零和博弈（常数和博弈）、性别之争等常作为双人博弈的一些典型案例。

下面讨论标准式博弈的策略(strategies)。我们将单个策略称为纯策略，并将所有参与者的任意纯策略组合称为纯策略组合。参与者也可以根据某个概率分布随机选择可能的行为，这被称为混合策略，下面是标准式博弈的混合策略的定义：

定义(混合策略).
设$(N,A,u)$是一个标准式博弈，对于任何集合$X$，设$\Pi(X)$是$X$上所有概率分布的集合，那么参与者$i$的混合策略集合为$S_i=\Pi(A_i)$

用$s_i(a_i)$表示在混合策略$s_i$下采取行动$a_i$的概率。注意，这里的$a_i$表示的是行为组合中的第i个，也就是参与者$i$此时的行为。

定义(支撑集).
混合策略$s_i$的支撑集是混合策略中所有概率不为0的纯策略的集合

下面通过期望给出某个混合策略组合对于参与者的效用函数的定义。

定义(混合策略的期望效用).
给定一个标准式博弈$(N,A,u)$，混合策略$s=(s_1,\dots,s_n)$对于参与者$i$的期望效用函数$u_i$ 定义为 \(u_i(s)=\sum_{a\in A}u_i(a)\prod_{j=1}^n s_j(a_j)\)

分析博弈：从优化到均衡

如何分析博弈，或者说如何求得最佳策略，博弈论学者通过确定某些被称为解概念的特定outcomes子集来解决这个问题，这些子集在某种意义上是具有研究价值或令人感兴趣的。

下面会介绍两种最基础的解概念：帕累托最优和纳什均衡

帕累托最优

首先，我们需要研究一下什么样的最优解对一个博弈是有意义的。从一个外部观察者的视角，是否有某些outcomes可以说是比其他更优的。

考虑到我们可以对参与者的效用函数做正仿射变换而不影响其本质，就像两个互不流通（或没有确定的汇率）的货币很难比较价值一样，像总效用值这样的优化目标是不合理的。但我们能很明确的确定10单位的货币A和3单位的货币B一定比9单位的A和3单位的B更有价值。

于是就有了帕累托占优的概念。

定义(帕累托占优).
策略组合$s$帕累托占优于策略组合$s^\prime$的条件是对于所有的$i\in N,u_i(s)\geq u_i(s^\prime)$并且存在对于某个$j\in N$有$u_j(s)>u_j(s^\prime)$

帕累托占优给出的是策略组合的一个局部的排序规则，正因此，我们无法像之前我们想要的那样得到一个唯一的最优解，帕累托“最优”实际上是一组互相无法比较的局部极优解。

定义(帕累托最优).
一个策略组合是帕累托最优，或严格帕累托有效，意味着不存在其他的策略组合帕累托占优于它

我们可以很轻易地得出有关帕累托最优的几个结论。首先，每个博弈都必有至少一个帕累托最优，并且都必有至少一个所有参与者采取纯策略的帕累托最优（可以用凸包的性质来证明）。其次，一些博弈会存在多个帕累托最优，例如，在零和博弈中，所有的策略组合都是严格帕累托有效的。

最佳响应和纳什均衡

接下来独立的参与者的视角来研究。如果一个参与者知道其他参与者会如何行动，那么ta的策略问题会变得简单，实际上，这样就可以化约成一个单主体的效应函数最大化问题。为了方便，我们定义$s_{-i}=(s_1,\dots,s_{i-1},s_{i+1},\dots,s_n)$为不包含参与者$s$的策略组合。这样在给定$s_{-i}$后就可以按单主体的效应函数最大化来决定参与者$s$的最佳响应了。

定义(最佳响应).
参与者$i$对$s_{-i}$的最佳响应是一个混合策略$s_i^{\ast}\in S_i,s.t. u_i(s_I^{\ast},s_{-i})\geq u_i(s_i,s_{-i}),\forall s_i\in S_i$

最佳响应不一定是唯一的，实际上除了在一些唯一的最佳响应是纯策略的极端情形下，最佳响应的数量总是无限的。当一个最佳响应的支撑集中存在不止一个元素时，agent一定对于它们是不区分的，否则，agent一定会通过将其中至少一个action的概率降到0来提高收益。

可以用最佳响应的想法来引出新的解概念：纳什均衡。

定义(纳什均衡).
一个策略组合$s=(s_1,\dots,s_n)$是一个纳什均衡的条件是对于所有的参与者$i$,$s_i$是对于$s_{-i}$的最佳响应。

直观上来看，纳什均衡是一个稳定的策略组合：没有参与者想去改变ta的策略如果ta知道其他参与者此时的策略。

可以将纳什均衡分成两类：强纳什均衡和弱纳什均衡。强和弱取决于每个参与者的策略是否对其他参与者的策略构成唯一的最佳响应。直观上来看，强纳什均衡比弱纳什均衡要更稳定，因为后者至少有一个参与者对其他参与者的策略存在一个非均衡策略的最佳响应。混合策略纳什均衡不必然是弱的，纯策略纳什均衡也可能是强可能是弱，取决于具体的博弈。

定义了纳什均衡之后，我们当然会关心一件事：纳什均衡是否总是存在？纳什定理给了我们一记强心剂：每个博弈至少拥有一个纳什均衡。

在讨论纳什定理及其证明之前，先从一些初步的概念开始入手。

定义(凸性). 一个集合$C\in \mathbb{R}$