群体博弈的思想最早来源于Nash的博士论文中关于混合策略的大量行动的解释^[1]. 近年来, 国内外学者对于群体博弈的研究越来越多, 1982年, Smith在专著^[2]中提到"在很多情况下, 博弈的参与者不仅仅只是与单一的参与者进行博弈, 而是与一个群体或其中的一部分进行博弈". Sandholm在2011年出版的专著^[3]给出了群体博弈的基本模型, 并系统的阐述了群体博弈及其演化动力学的研究及应用, 为群体博弈的研究提供重要的依据. 2017年, Yang和Yang将Sandholm的工作扩展到多目标群体博弈, 并分析了多目标群体博弈弱Pareto-Nash均衡的稳定性^[4]. 2016年, Yang等研究了多目标群体博弈加权Nash均衡的存在性和稳定性^[5]. 2019年, 杨光惠和杨辉通过引入一个理性函数, 建立了群体博弈的有限理性模型, 在此有限理性框架下研究了群体博弈Nash平衡的稳定性^[6].

逼近定理是许多计算问题的核心, 相关理论提供了深入的见解, 也是算法的基础. 1955年, Simon提出了有限理性理论, 其核心是满意原则, 就是使决策者感到满意的原则. 他认为问题本身是近似的, 其求解方法也是近似的, 只能寻求某种近似的, 但已经是足够好的, 可以使决策者满意和放心的方案或策略^[7]. 根据Simon的有限理性理论思想, 影响决策者的结果主要有三因素: 首先决策者的决策方案是近似的, 然后选择的目标函数也是近似的, 最后求解的计算方法是近似的^[8]. 俞建教授在文献[9] 中给出了有限理性思想下$n$人非合作博弈问题和最优化问题的逼近定理, 证明了可以用有限理性来逼近完全理性, 回应了Simon有限理性的质疑^[8], 这是很有理论意义的. 从实际应用的角度看, 反映了有限理性是以完全理性作为自己的终极目标的.

2011年, 文献[10] 给出了向量平衡问题(VEP) 的$\varepsilon$ -弱有效解的标量化结果. 在适当的条件下证明了VEPs的$\varepsilon$ -弱有效解集和$\varepsilon$ -有效解集的连通性. 2015年, 文献[11] 在适当的条件下, 还给出了同时扰动目标映射和可行域的参数广义向量平衡问题弱有效近似解映射的上半连续性和有效近似解映射的Hausdorff上半连续性. 2018年, 文献[12] 证明了平衡问题在有限理性思想下的一个逼近定理并利用集值分析的方法, 得到了单调平衡问题解在Baire范畴意义下的通有唯一性和通有收敛性, 说明了可以用有限理性来逼近完全理性. 文献[13] 通过引入群体博弈合作均衡的概念, 证明了群体博弈合作均衡的存在性和通有稳定性. 2019年, 文献[14] 基于有限理性理论, 证明了有限理性下变分不等式问题的逼近定理, 为有关变分不等式问题的算法提供了一个理论支持. 2020年, 文献[15] 证明了在一些一般假设下, 向量平衡问题的一个逼近定理. 根据Baire定理得到了严格拟单调向量平衡问题解的一个通有收敛性定理. 受以上工作的启发, 该文证明了有限理性思想下的群体博弈逼近定理, 在一定的假设条件下, 可以用有限理性来逼近完全理性. 同时, 利用集值分析的方法, 在Baire分类的意义下, 得到了目标函数扰动情况下群体博弈的解具有通有收敛性的结果.

我们首先介绍群体博弈模型.

设$P = \{1, 2, \cdots, N \}$是由$N$个群体组成的社会, $N\geq1$, 每个群体由数量充分大但有限的代理人组成, 群体$p$中个体总量份额为$m^p>0$, $\forall p \in P$, 群体$p$中每一个体的纯策略集为$S^p = \{{1, 2, \cdots, n^p}\}$, 相应的群体状态集为

其中$x_i^p \in {{{\Bbb R}} _ + }$表示群体$p$中选择策略$i\in S^{p}$的个体份额. 令$n = \sum\limits_{p\in P}n^{p}$, 表示所有群体中全部纯策略的总数.

表示整个社会$P$的社会状态集合, $x = (x^{1}, x^{2}, \cdots, x^{N})\in X$表示一种社会状态. $F:X\rightarrow {{\Bbb R}} ^{n}$表示整个社会的支付函数, $\forall x\in X$, $F(x) = (F^{1}(x), F^{2}(x), \cdots, F^{p}(x))$, 其中$\forall p \in P$, $F^{p}:X \rightarrow {{\Bbb R}} ^{n^{p}}$为群体$p$对应于$S^{p}$的支付向量, 即

其中$F_{i}^{p}(x):X \rightarrow {{\Bbb R}}$为群体$p$中代理人选择策略$i\in S^{p}$时的支付. 我们通常将一个群体博弈简记为$PG = (P, X, F)$.

特殊情形下, 当$N = 1$时表示单群体博弈模型, 即$m^p = 1$, 省略上面所有符号的上标$p$, 此时, 博弈的策略集为$S = \{1, 2, \cdots, n\}$, 状态空间为$X = \{x\in {{\Bbb R}} _{+}^{n}:\sum\limits_{i\in S}x_{i} = 1\}$, 它是${{\Bbb R}} ^n$中的单纯形.

定义2.1^[3]  设$PG = (P, X, F)$是一个群体博弈, 如果社会状态$\bar{x} = (\bar x^{1}, \bar x^{2}, \cdots, \bar x^{N})\in X$满足: 对任意的$p\in P, i\in S^{p}$有

则称$\bar x = ({\bar x^1}, {\bar x^2}, \cdots , {\bar x^N}) \in X$为群体博弈$PG$的Nash平衡.

引理2.1^[3]  如果$F:X \to {{{\Bbb R}} ^n}$连续, 则群体博弈$PG$在$X$上至少存在一个Nash均衡.

定义2.2^[16]  设$X, Y$是两个拓扑空间, 集值映射$F:X \to {P_0}(Y)$, 其中${P_0}(Y)$表示$Y$的所有子集的非空集合, $x \in X$, 则

(1) 如果对$Y$中的任意开集$G$, $F(x) \subset G$, 存在$x$的开邻域$O(x)$, 使得$\forall x' \in O(x)$, 有$F(x') \subset G$, 则称集值映射$F$在$x$是上半连续的.

(2) 如果对$Y$中的任意开集$G$, $F(x) \cap G \ne \emptyset$, 存在$x$的开邻域$O(x)$, 使得$\forall x' \in O(x)$, 有$F(x') \cap G \ne \emptyset$, 则称集值映射$F$在$x$是下半连续的.

(3) 如果集值映射$F$在$x$既是上半连续的又是下半连续的, 则称集值映射$F$在$x$是连续的. 如果集值映射$F$在每一点$x \in X$都是连续的, 则称集值映射$F$在$X$是连续的.

定义2.3^[16]   设$F:X \to {P_0}(Y)$是一个集值映射, $F$的图定义为

如果集值映射$F$的图$GraphF = \{ (x, y) \in X \times Y:y \in F(x)\}$是$X \times Y$中的闭集, 则称集值映射$F$是闭的.

引理2.2^[9]  设$X, Y$是两个拓扑空间, 集值映射$F:X \to {P_0}(Y)$是闭的, 而$Y$是紧的, 则$F$必是$X$上的一个usco映射, 即$\forall x \in X$, $F$在$x$是上半连续的, 且$F(x)$是非空紧集.

引理2.3^[9]  设$X$是一个Baire空间, $Y$是一个度量空间, $F:X \to {P_0}(Y)$是$X$上的一个usco映射, 则存在$X$中的一个第二纲的稠密剩余集$Q$, 使$\forall x \in Q$, 集值映射$F$在$x$是下半连续的从而是连续的.

注2.1   完备度量空间是Baire空间.

引理2.4^[9]   设${A_n}$是度量空间$X$中的一列非空有界子集, $A$是$X$中的一个非空有界子集, $G$是$X$中的一个开集, $G \cap A \ne \emptyset$. 如果$h({A_n}, A) \to 0(n \to \infty )$, 则存在正整数$N$, 使得对于任意的$n \ge N$, 有$G \cap {A_n} \ne \emptyset$, 其中$h$是$X$上的Hausdorff距离.

引理2.5^[9]  设${A_n}$是度量空间$X$中的一列非空有界子集, $h({A_n}, A) \to 0(n \to \infty )$, 其中$A$是$X$中的一个非空紧子集, $h$是$X$上的Hausdorff距离. ${x_n} \in {A_n}$, $n = 1, 2, \cdots$, 则存在$\{ {x_n}\}$的子序列${\rm{\{ }}{x_{n_k}}\}$, 使得${x_{n_k}} \to x \in A$.

在本节中, 首先引入群体博体$\varepsilon$ -近似Nash平衡解的概念.

定义3.1   设$P = \{ 1, 2, \cdots {N}\}$, 若社会状态$\bar x = ({\bar x^1}, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\bar x^2}, \cdots , {\bar x^N}) \in X$, $\forall p \in P$, 群体$p$中每一个体的纯策略集为$S^p = (1, 2, \cdots , n^p)$, 给定一个实数$\varepsilon > 0$满足

则称$\bar x = ({\bar x^1}, {\bar x^2}, \cdots , {\bar x^N}) \in X$为群体博弈$PG$的$\varepsilon$ -近似Nash平衡解.

接着, 我们给出群体博弈的逼近定理.

定理3.1   设$(X, d)$是度量空间, $P = \{ 1, 2, \cdots {N}\}$, $S^p = \{1, 2, \cdots , n^p\}$, $\forall p \in P$, 假设下列条件成立:

(ⅰ) $\forall n = 1, 2, \cdots$, 函数$F_j^{(n)p}:X \to{{\Bbb R}}$满足$n \to \infty$时

其中, $F_j^p:X \to {{\Bbb R}}$是连续的.

(ⅱ) $\forall n = 1, 2, \cdots$, ${A_n}$是$X$中的非空子集, 且$h({A_n}, A) \to 0{\kern 1pt} {\kern 1pt} {\kern 1pt} (n \to \infty )$, 其中$h$是$X$上的Hausdorff距离, $A$是$X$中的一个非空紧集.

(ⅲ) $\forall n = 1, 2, \cdots$, ${x_n} \in X$, 且$d({x_n}, {A_n}) \to 0$, 满足

其中, ${\varepsilon _n} > 0$, 且$n \to \infty$时${\varepsilon _n} \to 0$.

则

(1) 存在$\{ {x_n}\}$的一个收敛子列$\{ {x_{n_k}}\}$, 使得${x_{n_k}} \to \bar x \in A$;

(2) ${\bar x_{i}^p} > 0 \Rightarrow {F_i^p}(\bar x) = \mathop {\max }\limits_{j \in {S^p}} {F_j^p}(\bar x)$, $\forall i \in {S^p}$;

(3) 若群体博弈的Nash平衡解集是单点集, 必有${x_n} \to \bar x$.

证   (1) $n = 1, 2, 3, \cdots$, 因为$d({x_n}, {\kern 1pt} {\kern 1pt} {\kern 1pt} {A_n}) \to 0$, $\exists {x'_n} \in {A_n}$, 使$d({x_n}, {x'_n}) \to 0$, $h({A_n}, A) \to 0{\kern 1pt} {\kern 1pt} {\kern 1pt} (n \to \infty )$, 且$A$是紧集, 由引理2.5知, $\{ {x'_n}\}$必有子序列$\{ {x'_{n_k}}\}$, 使得${x'_{n_k}} \to \bar x \in A$, 故$\{ {x_n}\}$必有子序列$\{ {x_{n_k}}\}$, 使${x_{n_k}} \to \bar x \in A$.

(2) 由(1), 不妨设${x_n} \to \bar x$. 以下用反证法证明, 如果(2) 的结论不成立, 则存在$p_0\in P$, ${i_0} \in {S^{p_0}}$, 使得$x_{i_0}^{p_0}>0$但是

即存在${j_0} \in {S^{p_0}}$使

因为${F_j^p}$在$X$上是连续的, 则存在一个实数${\delta _0} > 0$, $\exists \bar x$的一个开邻域$O(\bar x)$, 使$\forall x' \in O(\bar x)$, 有

由$\mathop {\sup }\limits_{x \in X} \left| {F_i^{(n)p}(x) - {F_i^p}(x)} \right| \to 0$, 且${\varepsilon _n} \to 0$, 存在正整数${N_1}$, $\forall n \ge {N_1}$有

因${x_n} \to \bar x$, $n \to \infty$, 存在正整数${N_2}$, 不妨设${N_2} \ge {N_1}$, 使$n \ge {N_2}$, 有${x_n} \in O(\bar x)$, $\forall n \ge {N_2}$, 有

且

因为${x_n} \to x, x_{{i_0}}^{{p_0}} > 0$, 所以$x_{{i_0}(n)}^{{p_0}} > 0$, 与条件(ⅲ) 矛盾.

(3) 如果结论不成立, 则存在$\delta > 0$和$\left\{ {{x_n}} \right\}$的一个子序列$\left\{ {{x_{n_k}}} \right\}$, 使$d({x_{{n_k}}}, \bar x) \ge \delta$, 序列$\left\{ {{x_{n_k}}} \right\}$又必有收敛子序列, 不妨设${x_{n_k}} \to x'$, 即$d({x_{{n_k}}}, x') \to 0$, $x'$属于$A$且也是群体博弈的Nash平衡解, 又因为群体博弈的Nash平衡解是单点集, 故$x' = \bar x$, 则$d({x_{{n_k}}}, x') \ge \delta$矛盾. 定理3.1证毕.

注3.1  根据定理3.1, 群体博弈的支付函数是近似的(${F_i}^{(n)p}$近似$F_i^p$), 可行解集是近似的($A_n$近似$A$), 求解精度也是近似的(精度为$\varepsilon_n$), 但是可以得到一个逼近序列${x_{n_k}}$, 使得$x_{n_k} \rightarrow \bar x \in A$. 如果把群体博弈问题$F_i^{(n)p}$的$\varepsilon_n$近似解看作有限理性的" 满意解", 即群体博弈的解$\bar x$看作完全理性的"精确解". 定理3.1蕴含了可以用有限理性来逼近完全理性, 即完全理性可以用一系列有限理性的近似解来逼近, 一定程度上回应了Simon的有限理性理论.

如果定理3.1中, ${x_n} \in {A_n}$, $n = 1, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} 2, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} 3, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \cdots$, 结论仍然成立, 见下面的推论.

推论3.1   设$(X, d)$是度量空间, $P = \{ 1, 2, \cdots {N}\}$, $S^p = \{1, 2, \cdots , n^p\}$, $\forall p \in P$, 假设下列条件成立:

(ⅰ) $\forall n = 1, 2, \cdots$, 函数$F_j^{(n)p}:X \to {{\Bbb R}}$满足$n \to \infty$时

其中, $F_j^p:X \to {{\Bbb R}}$是连续的.

(ⅱ) $\forall n = 1, 2, \cdots$, ${A_n}$是$X$中的非空子集, 且$n \to \infty$时$h({A_n}, A) \to 0$, $A$是$X$中的非空紧集.

(ⅲ) 对每个$n = 1, 2, 3, \cdots$, ${x_n} \in {A_n}$, 满足

其中, ${\varepsilon _n} > 0$, 且$n \to \infty$时${\varepsilon _n} \to 0$. 则

(1) 存在$\{ {x_n}\}$的一个收敛子列$\{ {x_{n_k}}\}$, 使得${x_{n_k}} \to \bar x \in A$;

(2) ${\bar x_{i}^p} > 0 \Rightarrow {F_i^p}(\bar x) = \mathop {\max }\limits_{j \in {S^p}} {F_j^p}(\bar x)$, $\forall i \in {S^p}$;

(3) 若群体博弈的解集是单点集, 必有${x_n} \to \bar x$.

如果定理3.1中${A_n} = A$, $n = 1, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} 2, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} 3, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \cdots$, 结论仍然成立, 见下面的推论3.2.

推论3.2   设$(X, d)$是度量空间, $P = \{ 1, 2, \cdots {N}\}$, $S^p = \{1, 2, \cdots , n^p\}$, $\forall p \in P$, 假设下列条件成立

(ⅰ) $\forall n = 1, 2, \cdots$, 函数$F_j^{(n)p}:X \to {{\Bbb R}}$满足$n \to \infty$时

其中, $F_j^p:X \to {{\Bbb R}}$是连续的.

(ⅱ) $A$是$X$中的非空紧集.

(ⅲ) 对每个$n = 1, 2, 3, \cdots$, ${x_n} \in {A}$是$F^n$的$\varepsilon_n$近似解, 满足

其中, ${\varepsilon _n} > 0$, 且$n \to \infty$时${\varepsilon _n} \to 0$.则

(1) 存在$\{ {x_n}\}$的一个收敛子列$\{ {x_{n_k}}\}$, 使得${x_{n_k}} \to \bar x \in A$;

(2) ${\bar x_{i}^p} > 0 \Rightarrow {F_i^p}(\bar x) = \mathop {\max }\limits_{j \in {S^p}} {F_j^p}(\bar x)$, $\forall i \in {S^p}$;

(3) 若群体博弈的解集是单点集, 必有${x_n} \to \bar x$.

在本节中, 设$(X, d)$是一个紧度量空间, 定义函数空间${M}$如下:

$\forall F, G \in M$, 定义距离

则易证$({M}, \rho )$是一个完备度量空间.

$\forall F \in {M}$, 定义

则${T}(F) \ne \emptyset$, 由$F \to {T}(F)$就定义了一个集值映射${T}(F):{M} \to {P_0}(X)$.

引理4.1  ${T}(F)$是${M}$上的一个usco映射.

证   因$X$是紧集, 由引理2.2知, 只需证明集值映射${T}(F)$是闭的, 即要证明$\forall {F^n} \in {M}, {F^n} \to F$, $\forall {x_n} \in {T}({F^n})$, ${x_n} \to x$, 则$x \in {T}(F)$.

$\forall n = 1, 2, 3, \cdots$, 因${x_n} \in {T}({F^n})$, 有$x_{i(n)}^{p}>0 \Rightarrow F_{i}^{(n)p}({x_n}) = \mathop {\max }\limits_{j \in S^p} F_j^{(n)p}({x_n})$, $\forall i \in S^p$.

因${x_n} \to x$, 当$n$充分大时, 有$x_i^p > 0$, 又因为${F^n} \to F$, $F$在$x$上是连续的, 且${x_n} \to x$, 则有

得$F_i^{(n)p}({x_n}) \to {F_i^p}(x)$, 故$x \in {T}(F)$. 引理4.1证毕.

定理4.1  存在${M}$中的一个稠密剩余集${Q}$, 使$\forall F \in {Q}$, ${T}(F)$必是单点集.

证   首先, 因${M}$是完备度量空间, ${T}(F)$在${M}$上是usco映射, 由引理2.3知, 存在${M}$中的一个稠密剩余集${Q}$, 使$\forall F \in {Q}$, 集值映射${T}(F)$在$F$上是下半连续的.

$F \in {Q}$, 以下用反正法, 如果${T}(F)$不是单点集, 则存在${x_1}, {x_2} \in {T}(F)$, 而${x_1} \ne {x_2}$, 存在${x_1}$的开邻域$V$和${x_2}$的开邻域$W$, 使$V \cap W = \emptyset$. $\forall x \in X$, 定义函数$G:X \to [0, 1]$如下

易知$G$连续, $G({x_1}) = 0$, 而$\forall x \in X\backslash V$, 有$G(x) = 1$.

$\forall n = 1, 2, 3, \cdots$, $\forall x \in X$, 令$F_i^{(n)p}(x) = {F_i^p}(x) - \frac{1}{n}G(x)$, 则$F^{n} \in {M}$, 且${\rho _1}({F^n}, F) \to 0$. $\forall i \in S^p$, 记${F_i^p}({x_1}) = {F_i^p}({x_2}) = \mathop {\max }\limits_{j \in S^p} {F_j^p}(x) = a$. $\forall x \in X$, 因$F_i^{(n)p}(x) \le {F_i^p}(x) \le a$, 而${F_i^{(n)p}}({x_1}) = F_i^p({x_1}) = a$, 故$\forall n = 1, 2, 3 \cdots$, $i \in S^p, x \in X$, 有$F_i^{(n)p}(x) = \mathop {\max }\limits_{j \in S^p} F_j^{(n)p}(x) = a$.

因${x_2} \in W$, 即${T}(F) \cap W \ne \emptyset$, 集值映射${T}(F)$在$F$是连续的, 而$F_i^{(n)p} \to {F_i^p}$, 故存在一个足够大的正整数${n_0}$, 使得${T}({F^{{n_0}}}) \cap W \ne \emptyset$. 任取${x_{{n_0}}} \in {T}({F^{{n_0}}}) \cap W$, 则$F_i^{{(n_0)p}}({x_{{n_0}}}) = a$. 但是由${x_{{n_0}}} \in W \subset X\backslash V$, 得

矛盾, 故$\forall F \in {Q}$, ${T}(F)$必是单点集. 定理4.1证毕.

定理4.2   存在${M}$中的一个稠密剩余集${Q}$, 使$\forall F \in {Q}$, $\forall p \in P$, 必有${x_n} \to x$, 且$x \in X$, $x_i^p > 0 \Rightarrow {F_i^p}(x) = \mathop {\max }\limits_{j \in S^p} {F_j^p}(x)$.

证   由定理4.1, 存在${M}$中的一个稠密剩余集${Q}$, 使$\forall F \in {Q}$, ${T}(F)$是单点集. 再由定理3.1中的结论(3), 必有${x_n} \to x$. 证理4.2证毕.

注4.1  定理4.2表明了紧集$X$上目标函数受扰动下, 群体博弈问题的解集具有通有收敛性.

该文从有限理性理论出发, 针对群体博弈问题, 研究代表有限理性的近似解能否收敛到代表完全理性的精确解问题. 得到了群体博弈的逼近定理, 在一定的假设条件下, 证明了群体博弈Nash平衡解可以用有限理性来逼近完全理性, 即支付函数是近似的, 策略集是近似的, 求解精度也是近似的, 可以得到一个逼近精确解的子序列. 我们利用集值分析的方法, 在Baire分类的意义下, 得到了目标函数扰动情况下群体博弈的解具有通有收敛性的结果.