栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

【博弈论】基础知识

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【博弈论】基础知识

【博弈论】基础知识 1 策略式博弈

策略式博弈 又称 静态博弈,它是 一次 博弈。策略式博弈 G G G 形式化表示为:
G = { N , { A i } i = 1 N , { u i } i = 1 N } G=left{N,left{A_{i}right}_{i=1}^{N},left{u_{i}right}_{i=1}^{N}right} G={N,{Ai​}i=1N​,{ui​}i=1N​}
其中:

  • N N N:玩家集,所有玩家的有限集合;
  • A i A_{i} Ai​:玩家 i i i 的策略集:表示玩家 i i i 可选择的策略的集合;
  • u i u_i ui​:玩家 i i i 的收益函数: A 1 × A 2 × … A N → R A_{1} times A_{2} times ldots A_{N} rightarrow R A1​×A2​×…AN​→R 表示在一组策略下的收益。

完全信息静态博弈 具有以下特点:

  • 非合作博弈
  • 同时行动(simultaneous move):所有玩家同时做出策略选择。在选择策略时不知道其他玩家的策略选择
  • 完全信息(complete information):每个玩家的的策略和收益函数都是所有玩家的共同知识(common knowledge)

非完全信息静态博弈(也称 静态贝叶斯博弈)具有以下特点:

  • 非合作博弈
  • 同时行动(simultaneous move):所有玩家同时做出策略选择。在选择策略时不知道其他玩家的策略选择
  • 非完全信息(incomplete information):至少有一个玩家不能准确地知道其他某个玩家的收益函数。

以 囚徒困境 为例:

完全信息静态博弈:

两名犯罪嫌疑人被抓捕,被关到不同的牢房,但警方无充足证据,两名嫌疑人被告知:

  1. 若双方都不坦白,则均被判一个月;
  2. 若双方都坦白,则均被判六个月;
  3. 若一方坦白而另一方不坦白,则坦白一方释放,不坦白一方被判九个月。

可以使用双变量矩阵来表示二者的收益:

非完全信息静态博弈:

两名犯罪嫌疑人被抓捕,被关到不同的牢房,但警方无充足证据,两名嫌疑人被告知:

  1. 若双方都不坦白,则均被判一个月;
  2. 若双方都坦白,则均被判六个月;
  3. 若一方坦白而另一方不坦白,则坦白一方释放,不坦白一方被判九个月。

除此之外,还有额外需要注意的:

  1. Prisoner 1 总是理性的,即自私的
  2. Prisoner 2 可能是理性的,也可能是利他的,取决于他的心情
  3. 当 Prisoner 2 是利他时,那么他更偏好不坦白,他认为坦白等于“额外入狱四个月”
  4. Prisoner 1 不能准确地判断 Prisoner 2 是利己的还是利他的,但他能推断 Prisoner 2 理性的概率为 0.8,利他的概率为 0.2。

2 扩展式博弈

扩展式博弈,也称 动态博弈,它与策略博弈相对应。在扩展式博弈中,玩家是轮流进行决策的,通常可用 博弈树 将其刻画。

博弈树由 结点 (node)和 边 (edge)组成,对应博弈玩家、策略和收益。

  1. 非叶子结点:代表 博弈玩家,表示这个时候哪个博弈玩家做出决策。每个非叶子结点有且仅有一个博弈玩家。
  2. 叶子结点:代表每个玩家在此时的 收益。收益只存在于叶子结点。
  3. 边:表示 策略

扩展式博弈 G G G 形式化表示为:
G = { N , H , P , { u i } } G=left{N, H, P,left{u_{i}right}right} G={N,H,P,{ui​}}
其中:

  • N N N 为玩家集合;
  • H H H 为“策略的序列”构成的集合,可以是有限集或者无限集。 H H H 中的元素称为 历史 (history)。性质包括:
    • ∅ ∈ H emptyset in H ∅∈H,表示博弈树的根结点。
    • 如果策略序列 a 1 a 2 … a k ∈ H a^{1} a^{2} ldots a^{k} in H a1a2…ak∈H 并且 s < k s
    • 如果无穷策略序列 ( a k ) k = 1 ∞ left(a^{k}right)_{k=1}^{infty} (ak)k=1∞​ 满足对于任意的 k k k, a 1 a 2 … a k ∈ H a^{1} a^{2} ldots a^{k} in H a1a2…ak∈H,那么 ( a k ) k = 1 ∞ ∈ H left(a^{k}right)_{k=1}^{infty} in H (ak)k=1∞​∈H
    • 每一条历史序列都对应博弈树的一个结点,对应历史序列末端到达的结点
    • 在完全信息扩展式博弈中,历史集大小=结点个数
    • 最终历史集(Terminal history set): Z Z Z = {All Terminal history},在这些结点上是 收益
  • P P P 为博弈玩家函数(Player Function):
    • P : H Z → N P: H backslash Z rightarrow N P:HZ→N 给每一个非终结历史分配玩家集 N N N 中的一个元素
    • P ( h ) P(h) P(h) 表示在历史 h h h 后,轮到哪个玩家做决策
  • u i u_i ui​ 为收益函数,表示第 i i i 个玩家的收益
3 纳什均衡

继续上面 完全信息静态博弈 的囚徒困境的例子。我们先站在犯人1的角度思考:

  • 如果2坦白了,我选择坦白,则收益为-6;如果我不选择坦白,则收益为-9。因此我会选择坦白;
  • 如果2不坦白,我选择坦白,则收益为0;如果我不选择坦白,则收益为-9,因此我会选择坦白。

同时,犯人2也会这么想。因此二者都会坦白。

最优反应:当对手策略选定的时候,玩家会调整自己的策略,使得自己的收益在几种策略选择中是最大的。

纳什均衡:任何一位玩家在此策略组合下单方面改变自己的策略(其他玩家策略不变)都不会提高自身的收益。

也就是每个玩家的策略都是 最佳反应 的时候,就会形成一个稳定的局面,即达到 纳什均衡。

纳什均衡的形式化定义如下:

纳什均衡是博弈结果 a ∗ = ( a 1 ∗ , a 2 ∗ , … , a N ∗ ) a^{*}=left(a_{1}^{*}, a_{2}^{*}, ldots, a_{N}^{*}right) a∗=(a1∗​,a2∗​,…,aN∗​),即对每个玩家 i i i 都有:
u i ( a i ∗ , a − i ∗ ) ≥ u i ( a i , a − i ∗ ) u_{i}left(a_{i}^{*}, a_{-i}^{*}right) geq u_{i}left(a_{i}, a_{-i}^{*}right) ui​(ai∗​,a−i∗​)≥ui​(ai​,a−i∗​)
因此,我们可以 通过寻找同时满足所有人的最佳反应的博弈结果,来求解纳什均衡。

Reference

https://zhuanlan.zhihu.com/p/148407108

https://zhiqianghe.blog.csdn.net/article/details/107330041

https://www.docin.com/p-2590113104.html

https://zhuanlan.zhihu.com/p/199047997

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/986382.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号