【博弈论】信竞博弈论入门笔记 |
您所在的位置：网站首页 › 纳什均衡在博弈函数中的名称 › 【博弈论】信竞博弈论入门笔记 |
【博弈论】信竞博弈论入门笔记
|
目录
背景一些资料平等组合游戏
约定Min-MaxNIMSG函数anti-NIM 完全信息静态博弈
约定纳什均衡（未完成求解方法）
纯策略纳什均衡混合策略纳什均衡
背景
本人长期徘徊于弥补多项式短板/写字符串爽题/码毒瘤数据结构/看数学书这四件奇怪的事情上，因此水平很菜。 以前接触过一点简单的博弈论，但那实在是太简单了，就是对抗搜索（Min-Max）。 近期训练，做到了一道SAMParent-Tree上倍增之后博弈的题目，SAM都码完了，一看那个博弈，越看越慌，发现自己根本不会：何止不会，一分都拿不到。 于是开始恶补博弈论，发现很妙，但是挺好理解的。 本文因为作者被作业抓走了，暂时没有完成纳什均衡的内容。 update：发现那道促使我学习博弈论的题目是道假题，具体可以看我在anti-NIM里的内容 tip: 文章中的大量（哔——），是我为净化网络环境所作的努力（雾 一些资料oi-wiki 基本可以博弈论入门了 SG函数入门及例题 这篇文章良心 anti-NIM问题入门 很短，anti-NIM建议把SG搞懂之后作为一个应用加深了解，但是他是（哔——）（哔——），证明有点问题。 纳什均衡的一个例子 初步演示纳什均衡在OI中的用法 纳什均衡/划线法 这篇文章我弄出来，只是为了说明划线法（哔——）得不得了 纳什均衡/靠谱计算方法 个人认为是比较靠谱的纳什均衡计算方法（疯狂diss划线法） 纳什均衡/混合策略 （FBI Warning）这玩意儿太神仙了，个人计划如果有时间找一本博弈论的书来学习这一块内容，但讲道理OI里面大概是不会出现这种东西的（搞个纳什均衡出来就不错了）。 纳什均衡/生动例子（雾 这可是我太爷爷的太爷爷关注的up主[doge]手动滑稽 相信大家看出来了，我不想写纳什均衡，于是资料收集了很多。 平等组合游戏 一些定义、约定及基本规律平等组合游戏（不严谨） 两个人参与，且一胜一负每个人面对所有局面的可能选择都是一样的游戏总能结束，即，可以把所有状态抽象成点，选择抽象成边，游戏会变成 D A G DAG DAG一般而言不能操作者输（不能操作者赢就是anti-NIM问题）N-position&P-position 对于一个状态，如果当前获得这个状态的人能获胜，则称之为N-position（Now）对于一个状态，如果前一个状态转移过来的人能获胜，则称之为P-position（Pre）如果一个状态是N-position，则他一定可以转移到一个P-position 如果一个状态是P-position，则他的所有转移都一定指向N-position Min-Max搜索 作用及简介就是搜索平等组合游戏最暴力的方法，你能用这个方法得出几乎所有这类问题的指数级暴力算法 很基础，所以也没什么好讲的。 大致流程先抽象状态，然后写暴力从题目给定的初始状态出发，用基本事实以及边界条件判断每个状态是N还是P。 因此，记忆化搜索是常用的。 可以结合这样一个问题来理解这个过程： Alice和Bob在做游戏，这个游戏是在一个 n × n n\times n n×n棋盘上进行的，棋盘中每个格子都有一定的金币，Alice和Bob轮流操控一枚初始时在棋盘左上角的棋子，每人每次移动一格，并收集目标格子里的金币（重复经过可重复收集），每轮Alice移动一次之后Bob移动一次，共移动 m m m轮。因为Alice是mhw，所以所有金币全部归她，而Bob会一无所有。自然地，Alice希望最大化收集到的金币数，而Bob则希望最小化这个数值。给出棋盘大小，每个格子里的金币数，进行的轮数，求最终Alice可以获得多少金币。（原创题，但是也许比较经典，会在什么地方有类似的题目） NIM问题 简介这几乎是博弈论里面最经典的问题了。后文的SG函数以及anti-NIM问题的理解基本都要以其作为基础。 描述现在你有 n n n堆石子，第 i i i堆石子有 a i a_i ai个。两个人轮流进行游戏，每次可以从任意一堆中拿走任意数量的石子，但不能不拿，不能行动的人就输了。问是先手必胜还是后手。 结论先手能获胜，当且仅当 a 1 a_1 a1 ^ a 2 a_2 a2 ^ a 3 a_3 a3 ^ … ^ a n ≠ 0 a_n\neq0 an=0 换言之，就是一个状态异或和不为0就是N-position，一个状态异或和为0就是P-position 证明最终获胜者的最后一步操作，在异或和上的体现，就是从非0变成了0。 接下来，只要证明有这样一种方法，使得非0的异或和减去一个数字之后异或和就能变成0。 设当前异或和为 k k k且 h i g h b i t ( k ) = d highbit(k)=d highbit(k)=d（ h i g h b i t ( k ) = d highbit(k)=d highbit(k)=d表示 k k k在二进制下最高位为第 d d d位），则必有 a i a_i ai第 d d d位是1。我们将这个 a i a_i ai变为 a i ′ = a i a_i^{\prime}=a_i ai′=ai ^ k k k 考虑到 k k k与 a i a_i ai在第 d d d位上都为1，因此 a i ′ a_i^{\prime} ai′在第 d d d位上为0，因此 a i ′ < a i a_i^{\prime}a1,a2,...,an}这个初始状态下的 S G ( A ) SG(A) SG(A)为 s g ( a i ) sg(a_i) sg(ai)的异或和。 定理 一个状态 A A A是N-position（先手获胜），当且仅当 S G ( A ) ≠ 0 SG(A)\neq0 SG(A)=0 证明我们发现这个东西真的与NIM问题很像。 考虑 D A G DAG DAG上没有出边的点，其 s g sg sg一定为0，而一个人输了，就是他拿到的状态里所有的点都没有出边。因此此时这个状态 S G = 0 SG=0 SG=0，是P-position。考虑一个点 a a a，如果 s g ( a ) = k sg(a)=k sg(a)=k，则他能转移到的状态b中，一定有 s g ( b ) = 0 , s g ( b ) = 1 , . . . s g ( b ) = k − 1 sg(b)=0,sg(b)=1,...sg(b)=k-1 sg(b)=0,sg(b)=1,...sg(b)=k−1的，这一点与NIM问题很像，因为NIM中，我们也可以把一堆 k k k个的石子变成 0 , 1 , 2 , . . . , k − 1 0,1,2,...,k-1 0,1,2,...,k−1个中的任意一个。那么，当我们遇到一个 S G ( A ) ≠ 0 SG(A)\neq0 SG(A)=0的状态的时候，我们可以把 s g sg sg的值的大小看作这一堆的石子数，借用上面NIM问题的方法，把状态 a i ∣ h i g h b i t ( s g ( a ) ) = h i g h b i t ( S G ( A ) ) a_i|highbit(sg(a))=highbit(SG(A)) ai∣highbit(sg(a))=highbit(SG(A))，变为状态 a i ′ a_i' ai′使得 s g ( a i ′ ) = s g ( a i ) sg(a_i')=sg(a_i) sg(ai′)=sg(ai) ^ S G ( A ) SG(A) SG(A)即可。同样的，一个 S G ( A ) = 0 SG(A)=0 SG(A)=0的状态，进行一步改变， S G ( A ′ ) SG(A^{\prime}) SG(A′)是一定会不等于0的。 anti-NIM注意anti-NIM问题的结论只有在取石子游戏或者具有某种特殊性质的 S G SG SG函数中才成立。那道促使我学习博弈论的题目就是因为其误用了anti-NIM的结论，将其错误地推广至一般情况。 取石子游戏 描述其他条件都和一般的NIM游戏一样，只是判定胜利的条件变成了不能走的人是赢家。 定理对于一个状态 A = { a 1 , a 2 , . . . , a n } A=\{a_1,a_2,...,a_n\} A={a1,a2,...,an}： 若 max s g ( a i ) ≤ 1 \max sg(a_i)\leq 1 maxsg(ai)≤1，则其为N-position当且仅当 S G ( A ) = 0 SG(A)=0 SG(A)=0若 max s g ( a i ) > 1 \max sg(a_i)>1 maxsg(ai)>1，则其为N-position当且仅当 S G ( A ) ≠ 0 SG(A)\neq0 SG(A)=0其中 a i a_i ai表示第 i i i堆石子的个数；在这个问题里， s g ( a i ) = a i sg(a_i)=a_i sg(ai)=ai 证明 max s g ( a i ) > 1 \max sg(a_i)>1 maxsg(ai)>1 (Case1) 若 S G ( A ) ≠ 0 SG(A)\neq0 SG(A)=0 (Case1.1) 当有多个 s g ( a i ) > 1 sg(a_i)>1 sg(ai)>1时 (Case1.1.1) 与 S G SG SG函数里的证明差不多，我们总能将 A A A变为 A ′ A' A′使得 S G ( A ′ ) = 0 SG(A')=0 SG(A′)=0当只有一个 s g ( a i ) > 1 sg(a_i)>1 sg(ai)>1时 (Case1.1.2) 我们发现修改后会造成 max s g ( a i ) ≤ 1 \max sg(a_i)\leq1 maxsg(ai)≤1，我们应当使得 S G ( A ′ ) SG(A') SG(A′)不为0。假设我们沿用原来的方法，求得 a i a_i ai应变为 a i ′ a_i' ai′，则我们实际应将之变为 a i ′ ′ a_i'' ai′′使得 s g ( a i ′ ′ ) = s g ( a i ′ ) sg(a_i'')=sg(a_i') sg(ai′′)=sg(ai′) ^ 1 1 1。此时易知 s g ( a i ′ ′ ) ∈ { 0 , 1 } sg(a_i'')\in\{0,1\} sg(ai′′)∈{0,1}，因此我们就成功转移到了一个P-position，并且 a i → a i ′ ′ a_i\rightarrow a_i'' ai→ai′′是合法的转移 若 S G ( A ) = 0 SG(A)=0 SG(A)=0(Case1.2) 此时一定有超过1个 s g ( a i ) > 1 sg(a_i)>1 sg(ai)>1，因此 S G SG SG函数那里的讨论依然适用。 (Case1.2.1) max s g ( a i ) ≤ 1 \max sg(a_i)\leq1 maxsg(ai)≤1(Case2) 若 S G ( A ) = 0 SG(A)=0 SG(A)=0(Case2.1) 若存在 s g ( a i ) = 1 sg(a_i)=1 sg(ai)=1，将之变为0即可 (Case2.1.1)若不存在 s g ( a i ) = 1 sg(a_i)=1 sg(ai)=1，即所有 s g ( a i ) sg(a_i) sg(ai)都是0，我们发现这就是结束状态。 (Case2.1.2) 若 S G ( A ) ≠ 0 SG(A)\neq0 SG(A)=0，即 S G ( A ) = 1 SG(A)=1 SG(A)=1(Case2.2) 要么在0和1之间改动，使得 max s g ( a i ) ≤ 1 \max sg(a_i)\leq1 maxsg(ai)≤1且 S G ( A ′ ) = 0 SG(A')=0 SG(A′)=0 (Case2.2.1)要么将一个数 a i a_i ai改动至 a i ′ a_i' ai′使得 s g ( a i ′ ) > 1 sg(a_i')>1 sg(ai′)>1，此时 max s g ( a i ) > 1 \max sg(a_i)>1 maxsg(ai)>1且 S G ( A ′ ) ≠ 0 SG(A')\neq0 SG(A′)=0 (Case2.2.2)此处做详细证明，是为了后文说明方便。 推广 一个错误推广/*一点唠叨 *\ 既然，普通的NIM问题可以推广到一般的SG函数，那么，anti-NIM直觉上也是可以的。 而且你稍微想一下，会觉得如果把 s g sg sg值看作石子个数，那么根据上文的证明，这就是成立的。 但是，事实真的与我们的直觉一致吗？ 这可是反直觉的博弈论诶。 我曾经也以为这个直觉是对的，直到我详细写出了证明。 \*唠叨结束 */ 我们定义一个anti-SG问题一般形式为：初始时，在一张 D A G DAG DAG上放置了 n n n个点，双方轮流行动，最终不能行动的一方获胜，给定 D A G DAG DAG与初始条件，求是先手必胜还是后手必胜。错误地推广来的结论：anti-SG问题中，先手必胜的条件与取石子游戏相同。 错误性证明 在anti-NIM的分类讨论里面，我们逐条分析，发现除了(Case2.1.2)，其他都是对的。 （在证明中我特意把所有的石子个数都写成了 s g ( a i ) sg(a_i) sg(ai)，就是为了现在不用再写一遍）(Case2.1.2)的条件是：所有 s g ( a i ) sg(a_i) sg(ai)都为0。在取石子游戏中，我们发现这就是终止状态了，但是在一般的 D A G DAG DAG中，并不是这样的。有可能非终止节点的 s g sg sg也为0。此时，我们发现只要你进行转移， S G ( A ′ ) SG(A') SG(A′)就一定不为0。 如果转移后的 s g ( a i ′ ) = 1 sg(a_i')=1 sg(ai′)=1，则根据要证明的结论，我们转移至一个P-position，还是可以的。如果转移后的 s g ( a i ′ ) > 1 sg(a_i')>1 sg(ai′)>1，则根据要证明的结论，我们转移至一个N-position，这就不行了。 事情就出在这里，你不能保证一定可以转移到一个 s g ( a i ′ ) = 1 sg(a_i')=1 sg(ai′)=1的节点。由于我们这是一个数学归纳的过程，这一步的结论出错，其他所有结论就都错了，几乎无法挽救。 一个反例这里给出一个反例，以说明我没有在说瞎话。 考虑有向图： 1 → 2 2 → 3 3 → 4 2 → 4 1\rightarrow2\qquad2\rightarrow3\qquad3\rightarrow4\qquad2\rightarrow4 1→22→33→42→4 即： 就是那道促使我学习博弈论的题目： 题面给出一个由小写英文字母构成的字符串 S S S,再取 n n n个字符串,它们都是 S S S的子串,之后开始游戏,两人轮流操作: 每次选一个串,在其后添加一个英文字母,保证添加后该串仍为 S S S的子串。谁不能操作谁输,或者谁不能操作谁胜（这是两种询问）。 题解（误 我们发现，这就是在SAM上作一般的SG游戏以及anti-SG游戏。那么，第一种询问就可以随便完成，第二种询问就是假的，不可作。 推广的补救方法我们发现，证明告诉我们，错误的原因时 s g ( a i ′ ) sg(a_i') sg(ai′)不一定可以为1。那么，如果我们在条件当中加入一条： 保证所有 s g = 0 sg=0 sg=0节点，要么是终止节点，要么一定可以转移到 s g = 1 sg=1 sg=1的节点就可以了。 推广的另一补救方法我们发现，可以修改问题本身，令获胜条件就是所有 s g ( a i ) sg(a_i) sg(ai)全部都是0。 我翻资料的时候发现在网络上对于这个问题有一个名字：SJ。 完全信息静态博弈 定义 就是若干方博弈，所有人能做出的选择，每种选择带来的收益等一切信息所有人都知道 纳什均衡 概述其实有四种纳什均衡：严格占优纳什均衡、重复剔除的占优策略均衡、纯策略纳什均衡、混合策略纳什均衡。 这四种是包含关系：严格占优纳什均衡s1,s2,...,si,...,sn}为纳什均衡当且仅当： 对于每一个人 i i i，都不存在 S ′ = { s 1 , s 2 , . . . , s i ′ , . . . , s n } S'={\{s_1,s_2,...,s_i',...,s_n\}} S′={s1,s2,...,si′,...,sn}使得 u S ′ , i > u S , i u_{S',i}>u_{S,i} uS′,i>uS,i换而言之，就是每个人在其他人决策不变的情况下，都取到了可能的最佳结果。 举个栗子 现在有JSOI王国（简称J）正在和SAO（简称S）王国战略对峙，双方都初步掌握了卡常技巧，但是世界上其他人全都不会卡常，因此他们就取得了巨大优势，所有人都打不过它们，他们因此不受任何人的管束，可以随意瞎搞，人们称他们为：两大（哔——）。他们发展了一段时间卡常技巧之后，感觉这个东西太毒瘤了，一旦互相出题出的全是卡常题，事情将会一发不可收拾。他们一致决定相互协商，禁止卡常技术的继续研究发展。但是考虑到如果自己老老实实地停止发展，但是对方悄密密地继续，自己就会打不过对方。而且，如果自己不遵守，对方也无计可施。因此，他们就决定劝说对方禁止，反正自己不禁止。于是，他们继续发展卡常技术。此时双方就达成了一种纳什均衡状态。也就是说，双方都有两种选择：发展/不发展。但是不管对方是什么选择，自己永远是选择发展可以获得更大的利益，因此双方在追求利益最大化的过程中都会作出这种选择。这段话绝对没有对国际现象有任何影射一个更加正常的例子，可以看这里 计算方法 划线法我先讲一下，我认为这个方法就是（哔——）（哔——）。 所以，我不想写。看这里 但是，不得不说，这个方法还是有可取之处的。他揭示了纳什均衡的本质，让人能够看出来纳什均衡究竟在什么时候会出现。这实际上为其它的解法奠定了基础。而且他让你能手算小模型的纳什均衡。 求函数交点参考博客：纳什均衡/靠谱计算方法 高阶版本-混合策略纳什均衡啊啊啊，这个坑太大了，我不填。 update: 我填，我填 混合策略 混合策略大致解释：每个决策概率进行，决定决策实际是决定每个决策的进行概率。此时的纳什均衡就是对于每个人，其他所有人的决策固定，此时自己的决定的期望收益最大。比较数学化的表述：对于一个人他有纯策略策略： S = { s 1 , s 2 , . . . , s n } S=\{s_1,s_2,...,s_n\} S={s1,s2,...,sn} 我们再记一个概率向量 X = ( x 1 , x 2 , . . . , x n ) X=(x_1,x_2,...,x_n) X=(x1,x2,...,xn)表示其概率选择。 即，这个人选择 s 1 s_1 s1策略的概率是 x 1 x_1 x1，选择 s 2 s_2 s2策略的概率是 x 2 x_2 x2，…，选择 s n s_n sn策略的概率是 x n x_n xn 那么，我们就称 X X X是这个人的一个混合策略。这种情况下的纳什均衡在理解上是与纯策略相同的，只不过其中的策略是纯策略的扩展。 混合策略的意义很多事情是没有纳什均衡的（比如石头剪刀布） 但是，如果你把每种决策的概率考虑进去来构成策略，他就有纳什均衡了。 事实上，这会更加贴近现实生活。 单纯形法 |
【本文地址】
今日新闻 |
推荐新闻 |