博弈论算法讲义

「算法笔记」博弈论⼊门⼀、公平组合游戏 ICG1. 公平组合游戏的定义若⼀个游戏满⾜：1. 游戏有两个⼈参与，⼆者轮流做出决策。

2. 在游戏进程的任意时刻，可以执⾏的合法⾏动与轮到哪名玩家⽆关。

3. 不能⾏动的玩家判负。

则称该游戏为⼀个公平组合游戏。

2. ⼀些说明我们把游戏过程中⾯临的状态称为局⾯，整局游戏第⼀个⾏动的为先⼿，第⼆个⾏动的为后⼿。

我们讨论的博弈问题⼀般只考虑理想情况，即两⼈均⽆失误，都采取最优策略⾏动时游戏的结果。

定义必胜态为先⼿必胜的状态，必败态为先⼿必败的状态。

注意，在⼀般确定操作状态的组合游戏中，只会存在这两种状态，如果先⼿和后⼿都⾜够聪明，不会出现介于必胜态和必败态之间的状态。

⼀个重要的性质：⼀个状态是必败态当且仅当它的所有后继都是必胜态。

⼀个状态是必胜态当且仅当它⾄少有⼀个后继是必败态。

特别地，没有后继状态的状态是必败态（因为⽆法操作则负）。

⼆、Nim 博弈\(\text{Nim}\) 游戏是⼀个公平组合游戏。

⼤概是这样的：现在有 \(n\) 堆⽯⼦，第 \(i\) 堆有 \(a_i\) 个。

两⼈轮流操作，每⼈每次可以从任选⼀堆中取⾛任意多个⽯⼦，但是不能不取。

取⾛最后⼀个⽯⼦的⼈获胜（即⽆法再取的⼈就输了）。

结论：\(\text{Nim}\) 博弈先⼿必胜，当且仅当 \(a_1\oplus a_2\oplus \cdots \oplus a_n\neq 0\)。

证明：为了证明这个结论，我们需要证明：1. 所有⽯⼦都被取⾛是⼀个必败局⾯。

2. 对于任意⼀个局⾯，若 \(a_1\oplus a_2\oplus \cdots \oplus a_n\neq 0\)，⼀定能得到⼀个 \(a_1\oplus a_2\oplus \cdots \oplusa_n=0\) 的局⾯。

3. 对于任意⼀个局⾯，若 \(a_1\oplus a_2\oplus \cdots \oplus a_n=0\)，⼀定不能得到⼀个 \(a_1\oplus a_2\oplus \cdots \oplusa_n=0\) 的局⾯。

博弈论算法一、博弈的战略式表述及纳什均衡的定义在博弈论里，一个博弈可以用两种不同的方式来表述：一种是战略式表述（strategic form representation ），另一种是扩展式表述（或译为“展开式表述”）（extensive form representation ）。

从分析的角度看，战略式表述更适合于静态博弈，而扩展式表述更适合于讨论动态博弈。

1.1博弈的战略式表述战略式表述又称为标准式表述（normal form representation ）。

在这种表述中，所参与人同时选择各自的战略，所有参与人选择的战略一起决定每个参与人的支付。

战略式表述给出：1.博弈的参与人集合：(),1,2,,i n ∈ΓΓ=。

2.每个参与人的战略空间：,1,2,,i S i n =。

3.每个参与人的支付函数：12(,,,),1,2,,i n u s s s i n =。

我们用()11,,;,,n n G S S u u =代表战略式表述博弈。

例如在两个寡头产量博弈里，企业是参与人，产量是战略空间，利润是支付;战略式表述博弈为：{}121122120, 0; (,), (,)G q q q q q q ππ=≥≥ (1.1)这里i q 、i π别表示第i 个企业的产量和利润。

1.2纳什均衡的定义有n 个参与人的战略式表述博弈()11,,;,,n n G S S u u =，战略组合{}1,,,,i n s s s s ****=是一个纳什均衡。

如果对于每一个i 、i s *是给定其他参与人选择{}111,,,,,i i i n s s s s s *****--+=的情况下第个参与人的最优战略，即(,)(,),,i i i i i i i i u s s u s s s S i***--≥∀∈∀ (1.2)或者用另一种表述方式，i s *是下述最大化问题的解:111argmax (,...,,,,...,),1,2,..., ;i i i i i n i i s u s s s s s i n s S *****-+∈=∈(1.3)我们用这个定义来检查一个特定的战略组合是否是一个纳什均衡。

算法博弈论算法博弈论（algorithmic game theory）是2018年公布的计算机科学技术名词。

是计算机科学与博弈论的交叉研究领域。

从博弈的角度、以经济学和计算理论的方法分别研究计算机科学和经济学中的计算模型。

长期以来来，经济学研究人员专注各种经济活动和各种相应的经济关系及其运行，以及身为一名理性人在经济活动中的行为；而计算机科学研究人员则专注于研究信息与计算以及计算机系统中如何实现与应用，二者互不干涉。

这一情况在上个世纪90年代得到了改变，互联网的兴起，让原来只关注自身领域的计算机研究人员和经济学研究人员走到了一起：对于计算机科学研究人员，他们开始考虑互联网上的非合作博弈（non-cooperative）特性以及相应的激励(incentive)问题；同样的，经济学研究人员也开始涉足新兴的互联网，研究其跟经济相关的问题。

就这样计算机科学（computer science）与博弈论（game theory）走到了一起，形成了一门新的学科：算法博弈论（algorithmic game theory).和传统的博弈论和计算机科学相比，算法博弈论主要关注点在互联网网络，非传统拍卖等，主要不同体现在这些方面：应用领域：算法博弈论主要研究包括Internet网络和非传统拍卖，比如社交网络里的个体行为，baidu,google等用拍卖的方式出售它的关键字广告位，或者4G频段的拍卖。

工程量化方法：从具体优化问题的角度对应用建模，寻求最优解、判断不可解问题以及研究可解优化的上下限问题。

比如，在对问题用博弈论的框架进行建模过程中，可能会得到很多个稳定的状态（纳什均衡）。

那么在在这些稳定状态中，我们会关注系统最好情况的系统状况，最坏情况下系统的状况，以及统计意义上平均的系统状况。

以经典的囚徒困境为例，很显然在均衡状态下总共的收益是-4，而当两人都选择沉默时，每个人的收益-2。

很显然在均衡状态下并不最优的（inefficient），那我们该如何去量化这种inefficiency呢，这是算法博弈化研究内容之一。

2.2最小化最大原则最小最大原则（minimax principle）是证明随机算法运行时间下界的一个通用技巧，只能用于对所有输入和随机选择，都可以在有限时间内中止的算法最小最大原则使用博弈论中的概念，我们首先对博弈论进行介绍。

博弈论博弈论（game theory）是研究多个理性个体间博弈过程和结果的理论，一个简单的博弈通常可以由一个收益/支付矩阵（payoff matrix）!表示，考虑两人间有先后次序的石头剪子布博弈:支付矩阵上的元!!"∈!表示行决策者Roberta选择策略#，列决策者Charles 选择策略$时，Charles付给Roberta 的钱数/收益/数目…剪刀布石头剪刀01-1布-101石头1-1RobertaCharlesØ这是一个双人零和博弈（two-person zero-sum game），即两个人的净收益总和为0Ø进一步假设这是一个零信息博弈，即没有博弈者知道对手的策略。

自然地，行博弈者想最大化支付值，列博弈者想最小化博弈值Ø如果R 选择策略i，他得到的支付值是min"!!"，此时R 的最优策略是(#=max $min"!!"，这是R 支付给C 值的下界Ø如果C选择策略j，他得到的支付值是m,-!!!"，此时C 的最优策略是(%=m#.m,-!!"，这是C 支付给R 值的上界剪刀布石头剪刀01-1布-101石头1-10RobertaCharles一般有，max*min+),+≤m<=-m>?,),+，当@.=@/=V时，称它为博弈的一个解值，对应的策略称为博弈的解、鞍点、最优策略。

对于有界的博弈，令B,D分别表示R 和C 的最优策略，有@=)01。

注意，博弈可能不只有一个最优策略，也就是说解不只一个。

混合策略前面的讨论是针对于单一策略，当可能的策略为一个概率分布时，我们称其为混合策略，此时行决策者在分布p =(H %,…,H 2)上进行决策，H ,表示选择策略<的概率，列决策者在分布K =(K %,…,K 3)上进行决策，K +表示选择策略L 的概率。

博弈论启发式算法和纳什均衡-概述说明以及解释1.引言1.1 概述博弈论是一门研究决策和策略的数学理论，它以个体或组织在面对冲突和竞争时的互动行为为研究对象。

在现实生活中，博弈论可以应用于各种领域，如经济学、政治学、社会科学等。

启发式算法是一种基于经验和规则的问题解决方法，它通过不断试错和搜索最优解的过程，逐步逼近问题的解。

启发式算法可应用于各种优化问题、组合问题以及决策问题等。

本文旨在探讨博弈论、启发式算法和纳什均衡之间的关系。

博弈论的基本概念将会被介绍，包括博弈的类型、参与者的策略选择、收益与支付等因素。

启发式算法的原理和应用将会被解释，以展示它们在解决博弈论问题中的潜力。

本文的结论将会重点探讨纳什均衡的概念和特点。

纳什均衡是指在博弈中，每个参与者根据其他参与者的策略选择下的最佳响应策略。

此外，还将探讨博弈论、启发式算法和纳什均衡之间的联系，以揭示它们在实际问题中的应用潜力和相互作用关系。

通过本文的阅读，读者将对博弈论、启发式算法和纳什均衡有更深入的理解，并能够将它们应用于实际问题的解决中。

本文的目的是为读者提供一种全面的视角，以便能够更好地理解和应用这些概念和方法。

1.2 文章结构文章结构：本文主要分为引言、正文和结论三个部分。

在引言部分，将对博弈论、启发式算法和纳什均衡进行简要概述，并介绍文章的目的。

正文部分将着重阐述博弈论的基本概念以及启发式算法的原理和应用。

最后，在结论部分将探讨纳什均衡的概念和特点，并深入讨论博弈论、启发式算法和纳什均衡之间的关系。

本文旨在通过对博弈论、启发式算法和纳什均衡的研究，探索博弈论在实际问题中的应用，并探讨启发式算法与纳什均衡的关联性，从而提供对博弈论和启发式算法的理解和应用以及对纳什均衡的深入认识。

1.3 目的本部分将重点介绍本文的目的。

通过阅读本文，读者将能够深入了解博弈论、启发式算法和纳什均衡之间的关系。

我们将首先简要介绍博弈论的基本概念，包括博弈的定义和元素，以及博弈论在经济学、政治学和计算机科学等领域的应用。

第八章 博弈论前面章节对经济人最优决策的讨论，是在简单环境下进行的，没有考虑经济人之间决策相互影响的问题。

本章讨论这个问题，建立复杂环境下的决策理论。

开展这种研究的的理论叫做博弈论，也称为对策论(Game Theory)。

最近十几年来，博弈论在经济学中得到了广泛应用，在揭示经济行为相互制约性质方面取得了重大进展。

大局部经济行为都可视作博弈的特殊情况，比方把经济系统看成是一种博弈，把竞争均衡看成是该博弈的古诺-纳什均衡。

博弈论的思想精髓与方法，已成为经济分析根底的必要组成局部。

第一节 博弈事例博弈是一种日常现象，例如棋手下棋，双方都要根据对方的行动来决定自己的行动，双方的目的都是要战胜对方，互不相容，互相影响，互相制约。

一般来讲，博弈现象的特征表现为两个或两个以上具有利害冲突的当事人处于一种不相容的状态中，一方的行动取决于对方的行动，每个当事人的收益都取决于所有当事人的行动。

当所有当事人都拿定主意作出决策时，博弈的局势就暂时确定下来。

博弈论就是研究这种不相容现象的一种理论，并把当事人叫做局中人(player)。

博弈论推广了标准的一人决策理论。

在每个局中人的收益都依赖于其他局中人的选择的情况下，追求收益最大化的局中人应该如何采取行动？显然，为了确定出可行的策略，每个局中人都必须考虑其他局中人面临的问题。

下面来举例说明。

例1．便士匹配(Matching Pennies)(二人零和博弈)设博弈中有两个局中人甲和乙，每个局中人都有一块硬币，并且各自独立安排硬币是否正面朝上。

局中人的收益情况是这样的：如果两个局中人同时出示硬币正面或反面，那么甲赢得１元，乙输掉１元；如果一个局中人出示硬币正面，另一个局中人出示硬币反面，那么甲输掉１元，乙赢得１元。

对于这个博弈，每个局中人可选择的策略都有两种：正面朝上和反面朝上，即甲和乙的策略集合都是{正面，反面}。

当甲和乙都作出选择时，博弈的局势就确定了。

显然，该博弈的局势集合是{(正面,正面)，(正面,反面)，(反面,正面)，(反面,反面)}，即各种可能的局势的全体，也称为局势表，即表1。