人工智能

人工智能

课程概述

参考教材

参考网站

前8周讲授完毕，并进行期中闭卷考试(40分)

全自动区分计算机和人类的图灵测试：Completely Automated Public Turing test to tell Computers and Humans Apart，简称CAPTCHA

搜索

状态空间搜索

状态空间的表示

图搜索：需要检测和消除解路径上的循环

树搜索：免除检测的开销

搜索树

状态空间的搜索方向

回溯技术：通过试错方式搜索状态空间所有解路径

宽度优先搜索：

深度优先搜索：

所以，将两者结合我们得到了迭代加深深度优先：有近似于BFS的时间复杂度和近似于DFS的空间复杂度，避免组合爆炸。

迭代加深深度优先与广度优先等价

启发式搜索

为什么需要启发：1.没有精确解；2.约简搜索的状态空间

爬山搜索：

但爬山搜索容易陷入局部最优，我们可以增加回溯机制

最佳优先搜索，类似于宽度优先搜索，但把队列换成了优先队列

错位牌数是什么？？ 距离又是什么？？？

$A*$算法

把$h(n)$定义为0，且边权为1，就是BFS。DFS?

$A^*$算法具有可采纳性和单调性

可采纳性(admissible):最优评估函数一个算法是可采纳的，当存在一个解路径时，算法总是终止在此最优解路径上。

可采纳启发式是指它从不会过高估计到达目标的代价。

$A^*$算法是可采纳的：

$A^$最优性：如果$h_1(n) < h_2(n) $, 则$A_2^$展开的节点数小于$A_1^*$ P92

$A^*$单调性：启发函数$h$是单调的

单调性：在首次访问的目标状态的路径，保证一定是最短路径。

$A^$有如下性质：如果$h(n)$是可采纳的，那么$A^$的树搜索版本是最优的；如果$h(n)$是一致的，那么图搜索的$A^*$算法是最优的。

博弈树搜索

极小极大过程

将启发值自底向上传播

但这样状态数仍然很多，本质上还是穷竭搜索，所以要剪枝：

$\alpha - \beta$ 过程

极小极大过程：

$\alpha -\beta$剪枝

Monte Caro 树搜索

参考资料

基本原理；随机抽样+假设检验+树搜索

解决：迭代产生游戏树，解决树空间太大的问题

性质：用概率的方式，产生合理的推理，但并不保证一定最优

预测值：

SELECTION步骤：利用树策略选择节点

蒙特卡洛树的选择策略：

Expansion:添加一个 “?”的叶子节点。这是每次迭代中唯一添加的节点。

SImulation:又称 playout 或者 rollout。执行操作，直到达到结束状态，或者 满足设定的阈值，就停止该操作。然后基于模拟的结果，建立新 添加节点的值。

Backpropagation:利用新添加节点的值，对之前的树进行更新。从新的节点开始， 算法反向遍历回到根节点。

推理

合取范式(CNF),析取范式(DNF)

谓词演算的五大推理规则:取式假言推理、拒式假言推理、与消除、与引入、全称例化

合一

合一：判断什么样的替换可以使两个谓词表达式匹配的算法。

合一表明了两个或多个表达式在什么条件下可以称为等价的。

替换：一个替换(Substitution)就是形如${t1/x1,t2/x2,…,tn/xn}$的有限集合，$x1,x2,…,xn$是互不相同的个体变元，$ti$不同于$xi$, $xi$也不循环出现在$tj$中。

斯柯伦标准化:去掉所有的存在量词：$(\forall X)(\exists Y) (mother(X,Y))$ 转换为$(\forall X) (mother(X,m(X))) $

组合：在合一过程中，如果先后产生$S$和$S'$的替换，那么将S中的某个元素应用$S'$,所产生的新的替换，称为组合

最一般的合一式(MGU,Most Generalize Unify): 如果$g$是表达式$E$的最一般合一式，那么对于任何的其他合一式$s$,都存在另一个合一式$s'$,使$Es = Egs'$. 其中$Es$和$Egs'$是应用到表达式$E$的合一式的组合。

合一算法

1. 递归地对表达式的初始成分合一。如果成功，这次合一返回的任何代入式被用到两个表达式的剩下部分，然后以这两个表达式为参数。
2. 当两个参数之一为一个符号(谓词名，函词名，变元，常元)， 或两个表达式的每一元素都已匹配了，算法终止。

UNIFY
case
	E1, E2或者是常元或者是空表: %递归终止
		If E1=E2 then return {};
		else return FAIL;
	E1是一个变元：
		If E1在E2中出现 then return FAIL;
		else return {E2/E1};
	E2是一个变元：
		If E2在E1中出现then return FAIL;
		else return {E1/E2};
	其他情况: %E1和E2都是表
		begin
			HE1:=E1的第一个元素;
			HE2:=E2的第二个元素;
			SUBS1:=unify*HE1,HE2;
			if(SUBS1=FAIL) then return FAIL;
			TE1:=apply(SUBS1,E1的后半部);
			TE2:=apply(SUBS1,E2的后半部);
			SUBS2:=unify(TE1,TE2);
			if(SUBS2=FAIL) then return FAIL;
			else return SUBS1与SUBS2的并集;
		end

归结

归结法的基本思想：

消解是一种应用于谓词演算中的定理证明技术，是人工智 能问题求解的一个组成部分。消解描述了如何用最少的合一次数在一个子句数据库中发现矛盾的方法。

消解否证包含以下步骤：

产生子句的一系列过程：最后转换成不含量词的合取范式

归结的策略：

知识表示

常见的知识表示方法：

一阶谓词知识表示

优点：精确、自然、严密，易于实现

缺点：表示和处理分离，组合爆炸导致效率低

产生式表示

一阶谓词中蕴含式表示的知识是精确的(真或假)，而产生式表示的知识可以是不精确的(可信度)，产生式的推理匹配过程也可以是部分匹配。

产生式系统：一组产生式，互相配合/协调，其中一个产生式产生的结论可以作为另一个产生式的事实使用，以求解问题。有三个组件：数据库、规则库、

规则库：

数据库(工作内存)：

控制系统：

产生式表示/系统的优点：

产生式表示适用范围

语义网络表示法

通过有向图，其顶点表示概念，边表示概念间的语义关系，来表达复杂的概念及其相互关系。

语义网络的推理

语义网络表示的优缺点：

框架表示

定义：是描述对象(一个事物、一个事件、一个概念)属性的一 种数据结构。在框架表示法中，框架被认为是知识表示的 最基本单元

表示形式：框架名、槽名(描述某一方面的属性)、侧面(描述属性的某 一方面)、值组成

框架网络系统：将多个相互关联的框架连接起来组织的知识表示和推理系统

框架表示的优缺点

不确定性推理

从不确定性的初始事实（证据），运用不确定性的知识，获得不确定性但却合理的结论，获得不确定性但却合理的结论。

反绎推理

$P \rightarrow Q$ 与$Q$, 可能推出P

是一种寻找最佳解释的推理，是不可靠的推理。也称为溯因推理。

基于谓词逻辑的推理

三个重要假设（传统）

但如果假设不成立

非单调推理

模态操作符的扩充

真值维护系统

目标：维持推理系统的逻辑完整性

原理：通过存储每条推理的理由，再重新推断根据新的信念所得出的结论的支持情况

实现方式：

  1. 时序回溯：从死状态或者末状态返回，系统的遍历所有可能路径。(低效!)
  2. 相关性指导回溯:直接回溯到出问题的点，并在那个状态 对解进行修正。
    • TMS实现机制
      • 关联机制：将每条结论和其理由联系在一起
      • 定位机制：当给定矛盾和其理由时，直接定位错误的假设。
      • 回收机制：收回错误的假设
      • 追溯机制：收回错误的假设的结论

基于理由的真值维护系统JTMS

构造理由网络，并将网络与推理过程分离

理由网络

基于最小模型的逻辑

模型:对所有变量赋值均满足谓词表达式集合S的解释

存在问题:实际的领域无需任意多的谓词

最小模型:对所有变量赋值满足谓词表达式S的模型中，最小的那个模型

集合覆盖

考虑反绎推理中解释的产生:一个反绎的解释为谓词的覆盖。

确信度理论

MB(H|E):给定证据E时，假设H的可信度量

MD(H|E):给定证据E时，假设H的不可信度量

不确定性知识的表示：在CF模型中，知识是用产生式规则表示的，其一般形式为: IF E THEN H (CF(H|E))

(不)可信度量和概率

$MB(H|E) = \begin{cases} 1 & P(H)=1 \ \frac{\max{P(H|E),P(H)}-P(H) }{1-P(H)} & \text{otherwise} \end{cases}$

$MD(H|E) = \begin{cases} 1 & P(H)=0 \ \frac{\min{P(H|E),P(H)}-P(H) }{-P(H)} & \text{otherwise} \end{cases}$

  1. 当$MB(H,E) >0$时,有$P(H|E) > P(H)$, $E$的出现增加了$H$的概率。
  2. 当$MD(H,E)>0$时,有$P(H|E)<P(H)$,$E$的出现降低了$H$的概率

确信度的性质

互斥性：同一证据不可能既增加对$H$的信任程度，又同时增加对$H$的不信任程序，故$MB$和$MD$是互斥的。即有如下互斥性：

值域： $0 \le MB(H|E) \le 1$, $0 \le MD(H|E) \le 1$, $-1 \le CF(H|E) \le 1$

典型值：

  1. 当$CF(H|E)=1$时，有$P(H|E)=1$, $E$所对应证据的出现使$H$为真。此时，$MB(H|E)=1, MD(H|E)=0$
  2. 当$CF(H|E)=-1$时，有$P(H|E)=0$, $E$所对应证据的出现使$H$为真。此时，$MB(H|E)=0, MD(H|E)=1$
  3. 当$CF(H|E)=0$时，有$MB(H|E)=0, MD(H|E)=0$, $E$所对应证据的出现不证实$H$,也不否认$H$.

CF(H | E) = MB(H | E) - MD(H | E)

实际应用中，P(H)和P(H|E)的值难以获得，因此CF(H|E)的值要 求由领域专家直接给出。

  1. 否定证据不确定性的计算： $CF(\neg E) = - CF(E)$

  2. 组合证据不确定性的计算：

    1. 合取：当规则前提(组合证据)是多个单一证据的组合，即$E = E_1 \land … \land E_n$时，若已知$CF(E_1),CF(E_2),…,CF(E_n)$ , 则$CF(E) = \min {CF(E_1,…,CF(E_n))}$
    2. 析取：当规则前提(组合证据)是多个单一证据的析取，即$E = E_1 \lor … \lor E_n$时，若已知$CF(E_1),CF(E_2),…,CF(E_n)$ , 则$CF(E) = \max {CF(E_1,…,CF(E_n))}$

不确定性的更新公式： $CF(H) = CF(H,E) \times \max{0,CF(E)}$

  1. 若$CF(E)<0$,则$CF(H)=0$,即该模型没考略$E$为假对$H$的影响
  2. 若$CF(E)=1$,则$CF(H) = CF(H,E)$, 即规则强度$CF(H,E)$实际上是在$E$为真时，$H$的确信度。

结论不确定性的合成

原理:多条知识支持同一个结论，且这些知识的前提相互独立， 结论的确信度不相同时，可利用不确定性的合成算法求出结论 的综合确信度。

设有知识: If E1 then H (CF(H|E1)), If E2 then H (CF(H|E2))

我们先计算每个CF(H): CF1(H) = CF(H|E1) * max{0,CF(E1)}, CF2(H) = CF(H|E2) * max{0,CF(E2)}, 然后用如下公式求E1与E2对H的综合确信度

$CF(H) = \begin{cases} CF1(H)+CF2(H)-CF1(H)*CF2(H) & \text{若} CF1(H) \ge 0 \text{且} CF2(H) \ge 0 \ CF1(H)+CF2(H)+CF1(H)*CF2(H) & \text{若} CF1(H) < 0 \text{且} CF2(H) < 0 \ \frac{CF1(H)+CF2(H)}{1- \min{|CF1(H)|, |CF2(H)|}} & \text{若} CF1(H)\text{与} CF2(H)异号 \end{cases}$

合并计算公式所含特性：

证据理论

原理:基于收集到的证据数量，将概率论中的单点赋值扩展为集合赋值， 处理由“不知道”所引起的不确定性。

形式定义:考虑命题集，赋给区间值[belief, plausibility]，每个命题的可信度(belief measure)必须在这个区间内。

  1. 从相关问题的主观概念得到其可信度的思想
  2. 基于相互独立的证据时，合并可信度的规则

信任函数

Bel: $ 2^{\Omega} \rightarrow [0,1]$, $Bel(A) = \sum\limits_{B \subseteq A} m(B)$, 其中 $A \subseteq \Omega$.

Bel为下限函数，Bel(A)表示对$A$的总信任度

似然函数：

Pl: $2^{\Omega} \rightarrow [0,1]$, $PI(A) = 1- Bel(\neg A)$, 其中$A \subseteq \Omega$, $\neg A = \Omega -A$

$PI$为上限函数，$Bel(\neg A)$表示对$\neg A$的总信任度， 即$A$为假的信任度，因此$PI(A)$ 表示对$A$为非假的信任度。

信任函数与似然函数

$PI(A) \ge Bel(A)$

称$Bel(A)$ 和 $PI(A)$为对A信任程度的下限和上限，记为：$A[Bel(A),PI(A)]$

$PI(A) - Bel(A)$:描述"不知道"的情况

Dempster证据合并规则

对于$\forall A \subseteq \Omega, \Omega$上的两个$m$函数$m_1$, $m_2$,其Dempster合成规则为: $m_1 \oplus m_2 (A) = \frac{1}{K} \sum\limits_{B \cap C =A} m_1(B) \times m_2(C)$. $K= \sum\limits_{B \cap C \not= \emptyset} m_1(B) \times m_2(C) = 1- \sum\limits_{B \cap C = \emptyset} m_1(B) \times m_2(C)$

贝叶斯网络

先验概率 vs 后验概率

演绎推理 vs 归纳推理

贝叶斯定理： 通过先验概率和类条件概率表达式，计算后验概率

贝叶斯信念网络

贝叶斯网络

贝叶斯网络中的独立性：

d-可分

网络结构确定：

$a$的顺序会影响网络的结构。

贝叶斯信念网络推理

马尔科夫逻辑网络

Markov链

考虑一个$N$(有限)状态${s_1,s_2,…,s_n}$的系统：在离散的时间序列中${t_1,t_2,…}$, 其在时间$t$的状态记为$X_t$.

系统在时间$t$处在状态$s_j(1 \le j \le n)$ 的概率取决于其在时间${1,2,..,t-1}$的状态： $P(X_t = s_k | X_1,X_2,…,X_{t-1})$

一阶马尔科夫链：$P(X_t = s_k | X_1,X_2,…,X_{t-1}) = P(X_t = s_k | X_{t-1})$

Markov网

有向图+概率分布：Bayesian Network

无向图+概率分布：Markov Network(Markov Random Field, MRF), $G=(V,E)$

顶点：随机变量$V$

边：变量间的依赖关系$E$

团(Clique):各边所在的最大全联通子图(必须全连接)

势函数：为非负函数，表示团的一个状态

联合分布函数

对数线性模型：

在马尔可夫网络中，我们可以使用类似的直觉，但因为其中没有有方向的边（箭头），所以其条件独立陈述相对简单——如果节点 A 和 B 之间没有路径能使得该路径上的所有节点都被观察到，那么 A 和 B 就是相互独立的。换种说法：如果在 A 和 B 之间至少有一条路径上的所有中间节点都未被观察到，那么 A 和 B 就不是相互独立的。

Markov逻辑网的独立性

一个无向图$G=(V,E)$,是马尔科夫网络的充分必要条件是：当且仅当其满足以上三条独立性质

构建马尔科夫网络

马尔科夫逻辑网

一个可能世界(A Possible World):为每个可能的闭谓词指定真值。

可满足:一个一阶公式是可满足的，当且仅当该公式至少在一个世界中为真。

一阶逻辑的推理:判断一个知识库中是否包含公式F，即F是否在 所有满足知识库的世界中为真。

Markov逻辑网(Markov Logic Networks, MLNs): Markov网+一阶逻辑，其本质是公式附加权值的一阶逻辑知识库

基本思想：将一阶逻辑的限制放松，即一个可能世界违反公式越多，其发生的概率越小，但未必为0。

公式权重：表示公式限制强度的大小。权值越大，满足该公式世界的发生概率与不满足该公式世界的发生概率之间的差越大。

Markov逻辑网的定义

马尔科夫逻辑网$L$:是$(F_i,w_i)$对的集合，其中$F_i$代表一阶逻辑规则，$w_i$是用一个实数表示权重；有限的常数集为$C= {c_1,c_2,…,c_n}$

马尔科夫逻辑网$M_{L,C}$:

MLN特例：一阶逻辑

$\Pr({ { R(A), \neg S(A) } }) = 1/(3e^w + 1)$, 其他均为$e^w/(3e^w+1)$

MLN推理

贝叶斯公式：$P(A,B) = P(A) P(B|A)$

边缘概率求取公式$P(A) = \sum_B P(A,B)$

BN中的和积(Sum-Product)

MN中的和积

变量消除算法

符号学习

概念学习(Concept Learning)

定义：给定样例集合，以及每个样例是否属于某个概念，自动地推断出该概念的一般定义。

实例集合$X$: 如PPT中用六个属性表示

目标概念$c$: 定义在实例集上的布尔函数：$c: X \rightarrow {0,1}$

训练样例：正例$(c(x)=1)$, 反例$(c(x)=0)$

假设集$H$:每个假设$h$表示$X$上定义的布尔函数$h: X \rightarrow {0,1}$

概念学习：寻找一个假设$h$, 使对于$X$中的所有$x$, $h(x)=c(x)$

实例空间和假设数

最一般的假设:

最特殊的假设：

实例空间：

假设空间：

归纳学习假设：任一假设如果在足够大的训练样例集合中能很好的逼近目标概念函数，它也能在未见实例中很好的逼近目标概念。

假设的一般到特殊序

$h1=<Sunny,?,?,Strong,?,?>$, $h2=<Sunny,?,?,?,?,?>$,

$h2$包含的实例数多于$h_1$

更泛化(more general greater than or equal to): 令$h_j$和$h_k$是定义在$X$上的布尔函数，若$h_j \ge_g h_k$ 当且仅当，$(\forall x \in X)[h_k(x)=1 \rightarrow h_j(x)=1]$

严格泛化： $h_j >_g h_k $

更特化： $h_j \ge_s h_k$

Find-S:寻找极大特殊假设

  1. 将$h$初始化为$H$中最特殊的假设
  2. 对每个正例$x$
    • 对$h$的每个属性约束$a_i$，如果$x$满足$a_i$ 那么不做任何处理，否则将$h$中$a_i$替换为$x$满足的另一个最一般的约束
  3. 输出假设$h$

变型空间

列表消除算法：List-Then-Eliminate

  1. 变型空间VersionSpace,包含$H$中所有假设的列表
  2. 对每个样例$<x,c(x)>$: 从变型空间中移除$h(x) \not=c(x)$的假设$h$
  3. 输出VersionSpace中的假设列表

缺点：要列出所有假设，在实际中往往不可能

极大泛化(maximally general): $H$中与训练样例集合$D$一致的极大一般成员的集合。 $G={g\in H | Consistent(g,D)\wedge (\neg \exists g' \in H [ (g' >_g g) \wedge Consitent(g',D)] ) }$

极大特化(maximally specific):$H$中与训练样例集合$D$一致的极大特殊成员的集合：$S \equiv { s\in H | Consistent(s,D) \wedge (\neg \exists s' \in H [(s >_s s') \wedge Consitent(s',D) ]) }$

变型空间表示定理

表示定理：令$X$为任意的实例集合，$H$为$X$上定义的布尔函数集合。令$c: X \rightarrow [0,1]$为$X$上定义的任一目标概念，并令$D$为任意训练样例的集合${<x,c(x)> }$. 对所有的$X,H,c,D$以及良好定义的$S$和$G$: $VS_{H,D} \equiv { h\in H | (\exists s \in S)(\exists g \in G) [g >_g h >_s s] }$

正例和反例的作用

候选消除算法：Candidate-Eliminate

归纳偏置

决策树学习

决策树学习：

算法：

归纳偏置

信息增益： $Entropy(S) = \sum\limits_{i=1}^c -p_i \log_2{p_1}$

神经网络

激活函数

A saturating activation function squeezes the input.

$f$ is non-saturating iff ($|\lim\limits_{z \rightarrow - \infty} f(z)| = + \infty$) $\lor (|\lim\limits_{z \rightarrow + \infty } f(z)| = + \infty) $

感知机的学习方法：

感知机学习缺点：感知机模型属于单层神经网络，它不能解决一类非线性可分的问题。典型的例子就是异或。

二层神经网络可以表达所有的布尔函数

Delta规则

Delta规则是基于错误(误差)平面的，错误(误差)平面是神经 网络所表示的函数在数据集上的累积误差。每一个神经网络 权值向量都对应误差平面中的一个点。

应用delta规则时，激励函数必须是连续的和可微分的。

$\Delta W_k = c(d_i - O_i) f'(net_i) * X_k$

Delta规则分析

多层神经网络

隐藏层神经元实际为特征检测算子 (feature detector)，在多层神经网络 的学习过程中，隐藏层神经元开始 逐步“发现”刻画训练数据的突出 特征。

反向传播算法(Back Propagation)

BP神经网络：

遗传算法

遗传算法GA:受生物进化启发的学习算法：

假设的表示：可以用01位串表示

适应函数(fitness)

染色体的选择：

遗传算子(GA operator): 对从当前群体中选择的染色体进行重组，以产生后代

交叉： 选择两个候选个体，分解每一个个体，然后交换分量形成两个新的候选个体

变异：选择一个候选个体，随机的选择一位，然后取反

遗传算法的优势：

未解决的问题：

模式定理

Short schemata with large fitness will increase their representation in the population during the evolution

模式H的阶，o(H):模式H中确定位置的个数

模式H的长度，d(H):模式H中第一个确定的位置到最后一个确定位置的距离

模式的进化

$m(s,t)$ 表示在第$t$代种群$p_t$中模式$s$的实例数量

模式理论：

轮盘赌选择：$\Pr(h) = \frac{f(h)}{\sum\limits_{i=1}^n f(h_i)} = \frac{f(h)}{n\bar{f}(t)}$

选择的假设是模式$s$的实例的概率：$\Pr(h \in s) = \sum\limits_{h \in s \cap p_t}\frac{f(h)}{n\bar{f}(t)} = \frac{\hat{u}(s,t)}{n \bar{f}(t)} m(s,t)$

如果选择$n$次，得到$s$的实例的期望值是$\mathbb{E}[m(s,t+1)] = \frac{\hat{u}(s,t)}{\bar{f}(t)} m(s,t)$

模式定理：$E[m(s,t+1)] \ge \frac{\hat{u}(s,t)}{\bar{f}(t)} m(s,t) (1 - p_c \frac{d(s)}{l-1}) (1-p_m)^{o(s)}$

强化学习

强化学习的本质：奖惩和试错(Trial and Error)

Markov Decision Process(MDP)

MDP模型-返回函数

MDP模型-动作选择：

监督学习 VS 强化学习

动态规划

给定一个完全已知的MDP模型

$V^{\pi} (s):$ 从s状态出发，采用$\pi$策略，所获得的期望返回值

$Q^{\pi} (s,a):$ 从$s$状态出发，采用$a$动作，继而采用$\pi$策略，所获得的期望返回值

最优值函数($V^(s)$ 和 $Q^(s,a)$): 采用最优策略$\pi^*$所获得的期望返回值

定理：策略$\pi$为最优策略当且仅当，在每一个状态s, $V^*(s) = \max_{\pi} V^{\pi} (s)$, $V^{\pi}(s) = \max_a Q^{\pi}(s,a)$

最优策略： $\pi^* =\arg \max \limits_{\pi} V^{\pi}(s), (\forall s) $

Bellman等式(有折扣无限窗口)：

动态规划-最优控制

Monte Carlo策略

策略评价：

策略优化：$V(s_t) \leftarrow V(s_t) + \alpha(R_t - V(s_t))$

最优控制：

时差学习(Temporal-Difference Learning)

蒙特卡洛的方法可以看做是最大步数的时差学习

单步时差方法：$V(s_t) = V(s_t) + \alpha[r_t + \gamma V(s_{t+1}） - V(s_t)]$

$R_t^{(2)} = r_t + \gamma V(s_{t+1})$

N步时差方法：$R_t^{(n)} = \sum\limits_{i=0}^{n-1} \gamma^i r_{t+i} + \gamma^n V(s_{t+n})$

N步回退方法：$R_t $

Bootstaps和Sampling

Bootstraps

采样

博弈

囚徒困境

布雷斯悖论：它是指在一个交通网络上增加一条路段反而使网络上的旅行时间增加；这一附加路段不但没有减少交通延滞，反而降低了整个交通网络的服务水准。这种出力不讨好且与人们直观感受相背的交通网络现象主要源于纳什均衡点并不一定使社会最优化。

社会福利(Social Welfare):最大化所有参与者的受益和

帕里托优(Pareto Efficiency)

纳什均衡(Nash Equilibrium)

优超(Dominant):不依赖其他参与者

帕里托优

一个方案$x$是帕里脱最优，当且仅当不存在另一个方案$x'$满足

帕里托最优：不考虑跨Agent效益比较的情况下满足一个全局最优

帕里托改善：在不减少一方利益的同时，通过改变现有的资源配置而提高另一方的利益

社会福利是帕利脱最优的一个子集：一个agent要想提高自己的利益，必然存在其他agent的利益受损

纳什均衡

Agent的策略依赖于其他agent

如果$S_A^* = <S_1^*,S_2^*,…,S_{|A|^*}>$ 为纳什均衡策略，当且仅当对agent $i$:$S_i^*$ 对于agent $i$ 是最优策略当其他agent选择以下策略时$<S_1^*,S_2^*,…,S_{i-1}^*,S_{i+1}^*,…,S_{|A|}^*>$

没有参与者可以独自行动而增加受益

问题:

不同准则下的最优策略

分布式决策下的博弈??

协商

投票

投票机制：

投票机制的六原则

不同的投票机制：

拍卖

拍卖机制：

谈判

谈判机制：