Social computing 5 —— 博弈论
博弈论的基本概念
-
博弈（game）
博弈三要素：
-
参与人（player，玩家）
-
策略集（strategy，战略）
-
回报（payoff，收益、支付）
-
次序（order）
-
均衡（equilibrium）
每个参与人都有一个策略集；
策略组：每个参与人出一个策略构成策略组合
对应每个策略组，每个参与人都有一个回报
-
-
田忌赛马
-
参与人：齐威王、田忌
-
策略集
-
上中下
-
上下中
-
中下上
-
中上下
-
下上中
-
下中下
-
-
回报
-
对于策略组（1，1），田忌（-3）
-
对于策略组（5，1），田忌（+1）
-
……
-
-
-
博弈不总是讲输赢
商场走失问题：两友人同逛一个大商场，走散了。已知商场有南北两个门，也知道朋友会在某个门等候，你会去哪个门？
—— 只有协调，才能共赢
-
收益矩阵（表达博弈的一种直观方式）
-
博弈论的关切（不同于博弈参与人的关切）
在”理性人“等基本假设下，博弈（作为一个整体）的结果、走向、发展趋势、哪些策略组（合） 会被人们采用。
-
博弈推理的假定（assumption）
-
自己的回报是每个参与人关心的唯一因素
-
参与人都是 “理性人” ，即只要可能，总是要选择有更好回报的策略
-
每个参与人都对博弈结构完全了解
-
-
个体理性与集体理性
-
个体理性
个人理性是指个人分析问题，决定自己行为取向时所表现的理性。
-
集体非理性
集体理性是指集体在决定和从事集体行动所表现出来的理性，而集体非理性则相反。
-
无论是个人理性、集体理性还是集体非理性，他们强调的是在选择和策略过程中表现的一种思维思考活动。
-
-
一个博弈的解，是“稳定的策略组”，要求是其中任何参与人不可能通过单方面改变策略而获得更好的回报。
- ”稳定的“ → 在博弈推理假设下不可能再变化
不是所有的博弈都有解
这里解的概念，实际上就是博弈均衡的概念。
-
策略L 策略R 策略U 90,90 86,92 策略D 92,86 88,88 -
严格占优策略：对一个参与人来说，若存在一个策略，无论另一个参与人选择何种策略，该策略都是严格最佳的选择，则这个策略就被称为是前者的严格占优策略。
-
按照博弈推理假设，参与人将选择严格占优策略。
-
-
严格与不严格的区别
L R U 3，3 4，3 D 2，0 3，4 -
横向为参与人1，纵向为参与人2
-
U是参与人1的严格占优策略；R是参与人2的占优策略，但不是严格的
-
L是U的最佳应对，但不是最严格的；R是D的严格最佳应对
-
-
简单博弈的行为推理
-
如果两个人都有严格占优策略，可以预计他们均会采用严格占优策略。
-
如果只有一个人有严格占优策略，则这个人会采取严格占优策略，而另一方会采取此策略的最佳应对（一定会有）。
-
占优策略 → 占优策略 ； 占优策略 → 最佳应对
-
互为最佳应对策略组 → 纳什均衡
-
具有多个纳什均衡的博弈
-
-
如果两个人均没有严格占优策略呢？
如何讨论博弈的走向？
A B C A 4,4 0,2 0,2 B 0,0 1,1 0,2 C 0,0 0,2 1,1 -
三客户博弈的解，横向为公司1，纵向为公司2
-
策略组（A，A）中的两个策略为最佳应对
纳什均衡：互为最佳应对的策略组。
-
-
协调博弈
北门 南门 北门 1，1 0，0 南门 0，0 1，1 -
横向为你，纵向为你的拍档。
-
有两个纳什均衡（北门，北门）与（南门，南门）
-
如何预测协调博弈中参与人的行为？
引入外部条件
-
鹰鸽博弈的推理
-
两个均衡，不能推断出哪个均衡会出现
-
一般来说，纳什均衡的概念能够有助于缩小预测的范围，但它并不一定能够给出唯一的预测
-
-
如果不存在纳什均衡，怎么办？
零和博弈（zero sum game） → 猜测他人的策略，不让他人预测你的策略
-
-
混合策略的引入
-
引入随机性，考虑参与人将以一定的概率在不同策略间进行选择，一个概率对应一个“策略”（称为混合策略）。此时，选择策略就是选择策略，而博弈矩阵中给出的选项称为寸策略。
- 一般地，混合策略是一个概率分布，双策略情形等价为一个概率。
-
通常地，在有两个纯策略H和T的情形，我们说：
-
你的策略概率是，是指你以概率执行 H； 以概率执行T。
-
他的策略概率是，是指他以概率执行H；以概率执行T。
-
-
针对混合策略的博弈，三要素齐全了吗？
-
参与人 √
-
策略（概率） √
-
回报 ？
此时的策略是两种（纯）策略上选择的概率，每一组纯策略是对应有固有收益的。因而，从概率意义出发，此时的收益应该体现一种在两种纯策略上的“平均”（期望）。
-
-
但是，在研究一个混合策略博弈的时候，我们一般并不关心在每个策略下的具体回报情况，而是关心是否能够达到均衡？在什么混合策略组下达到均衡？哪两个概率是互为最佳应对？
最佳应对：改变策略后，不会得到更好的回报。
-
-
博弈均衡有两种：纯策略均衡、混合策略均衡；
任何博弈都存在均衡：
-
可能有一个，也可能有多个
-
可能是某一个，也可能两种都有
-
-
社会最优
-
均衡是博弈的解（走向、结果），参与人都实现个体最优，但不一定是社会最优。
-
帕累托最优（Pareto Optimality）
帕累托最优是指资源分配的一种理想状态。
假定固有的一群人和可分配的资源，从一种分配状态到另一种状态的变化中，再没有使任何人境况变坏的前提下，使得至少一个人变得更好。
帕累托最优的状态就是不可能再有更多的帕累托改进的余地；换句话说，帕累托改进是达到帕累托最优的路径和方法。帕累托最优是公平与效率的“理想王国”。
-
一组策略选择是社会福利最大化（或社会最优），若它使参与者的回报之和最大。
-
社会最优和纳什均衡有可能一致。
-
从社会应用的意义讲，均衡与社会最优一致的系统是理想系统。
-
-
相关概念
-
纳什均衡（Nash Equilibrium）
在一策略组合中，所有的参与者面临这样的情况：当其他人不改变策略时，他此时的策略师最好的。也就是说，此时如果他改变策略他的回报（payoff）将会降低。
在纳什均衡点上，每一个理性的参与者都不会有单独改变策略的冲动。
纳什的奠基性贡献：证明了具有有限参与者和有限纯策略集的博弈一定存在纳什均衡（包含混合策略均衡）。
-
零和博弈（Zero-sum Game）
零和博弈是一种非合作博弈，指的是参与博弈的各方，在严格竞争下，一方的收益必然意味着另一方的损失，博弈各方的收益和损失之和永远为“零”。双方不存在合作的可能。
零和博弈的结果是一方吃掉一方，一方的所得正是另一方的所失，整个社会的利益不会因此增加一分。
-
非零和博弈（Non-zero-sum Game）
非零和博弈是一种非合作下的博弈，博弈中各方的收益或损失的总和不是零值，它区别于零和博弈。在经济学研究中很有用。
在非零和博弈中，对局各方不是完全对立的，一个局中人所得并不一定意味着其他局中人要遭到同样数量的损失。也就是说，博弈参与者之间不存在“你之得即我之失”这样一种简单的关系。
参与者之间可能存在着某种共同的利益，博弈参与者可能实现“双赢”或者“多赢”。
-
囚徒困境（Prisoner’s dilemma）
两个嫌疑犯（A和B）作案后被警察抓住，隔离审讯。警方的政策是“坦白从宽，抗拒从严”，如果两个人都坦白则各判8年；如果一个人坦白，另外一个人不坦白，则坦白的放出去，不坦白的判刑十年；如果都不坦白，则因为证据不足各判1年。
囚徒困境最早由美国普林斯顿大学数学家阿尔伯特·塔克（Albnert Tucker）在1950年提出来，他当时编了一个故事向斯坦福大学的一群心理学家们解释什么是博弈论，这个故事后来成为博弈论中最著名的案例。
→ 此时，都坦白是二者的严格最优策略。
-
Social computing 5 —— 博弈论