博弈论(二)完全信息静态博弈

简介: 博弈论(二)完全信息静态博弈

 完全信息静态博弈(static games of complete information)。其中假设参与人是理性的(Rationality),也就是参与人的目的是使得自己收益最大化,参与人是完美的计算者。并且参与人知道其它参与人是理性的。

Prisoners’ Dilemma

  上述例子就是完全信息静态博弈的例子。同时行动(simultaneous move)指的是每个参与人在选择他的策略时不知道其他参与人的选择。完全信息(complete information)指的是每个参与人的策略和收益函数都是所有参与人的共同知识(common konwledge)。


Normal-form (or strategic-form) representation


  一个博弈G GG的标准式(或策略式)包括:

image.png

2-player game

  如只有两个player,且每个player的策略有限,则可以用双变量矩阵来表示这个博弈:

  行和列表示策略可选策略,矩阵中的单元格表示策略组合

Prisoners’ Dilemma

  在囚徒困境这个例子中参与人集合可表示为:{ P r i s o n e r 1 , P r i s o n e r 2 } ,策略集合S 1 = S 2 = { M u m , C o n f e s s } 收益函数可表示为:

  那么其双变量矩阵可表示为:

Iterated elimination of strictly dominated strategies

Nash equilibrium

  纳什均衡是一个策略组合。其中,每个参与人选择的策略都是针对其他参与人选择策略的最优反应。

  更一般地考虑2-player game with strategiesS 1 = { s 11 , s 12 , s 13 } S 2 = { s 21 , s 22 },如果u 1 ( s 11 , s 21 ) ≥ u 1 ( s 12 , s 21 ) ,且u 1 ( s 11 , s 21 ) ≥ u 1 ( s 13 , s 21 )。那么player1的策略s 11 是他对player2策略s 21 的最优反应。

  在一个两个参与人的博弈中,当且仅当两个参与人所选策略都为对方所选策略的最优反应时,那么这个策略是一个纳什均衡。

  在一个纳什均衡的策略组合上,每个参与人给定对方策略选择时最大化自己的收益了,不会有任何动机偏离当前的策略选择。

  再看一个纳什均衡解的问题:

Best Response Function


  最优反应(Best Response Function)定义:在标准式博弈(normal-form game) { S 1 , S 2 , ⋯   , S n , u 1 , u 2 , ⋯   , u n } 中,如果其它玩家1 , 2 , ⋯   , i − 1 , i + 1 , ⋯   , n 选择策略s 1 , ⋯   , s i − 1 , s i + 1 , ⋯   , s n ,对于参与人i 来说,如果策略s i s_{i}si带给他的收益不小于他在任何其它策略带给他的收益,那么这个策略s i 就是对于其他参与人所选策略的最优反应:

image.png

或者定义为一个最大化问题:

image.png


依据最优反应定义纳什均衡

Applications of Nash equilibrium

最优反应求解纯策略纳什均衡

严格剔除劣策略纳什均衡

Mixed strategy Nash equilibrium

  混合策略是指定一个实际行动,它是从纯策略集中以某些指定的概率被随机选择出来的。伴随着策略选择的随机化是参与人收益的随机化。因此需要引入期望收益(expected payoff)

相关文章
|
存储 缓存 文件存储
如何保证分布式文件系统的数据一致性
分布式文件系统需要向上层应用提供透明的客户端缓存,从而缓解网络延时现象,更好地支持客户端性能水平扩展,同时也降低对文件服务器的访问压力。当考虑客户端缓存的时候,由于在客户端上引入了多个本地数据副本(Replica),就相应地需要提供客户端对数据访问的全局数据一致性。
32698 79
如何保证分布式文件系统的数据一致性
|
前端开发 容器
HTML5+CSS3前端入门教程---从0开始通过一个商城实例手把手教你学习PC端和移动端页面开发第8章FlexBox布局(上)
HTML5+CSS3前端入门教程---从0开始通过一个商城实例手把手教你学习PC端和移动端页面开发第8章FlexBox布局
17751 20
|
设计模式 存储 监控
设计模式(C++版)
看懂UML类图和时序图30分钟学会UML类图设计原则单一职责原则定义:单一职责原则,所谓职责是指类变化的原因。如果一个类有多于一个的动机被改变,那么这个类就具有多于一个的职责。而单一职责原则就是指一个类或者模块应该有且只有一个改变的原因。bad case:IPhone类承担了协议管理(Dial、HangUp)、数据传送(Chat)。good case:里式替换原则定义:里氏代换原则(Liskov 
36682 19
设计模式(C++版)
|
存储 编译器 C语言
抽丝剥茧C语言(初阶 下)(下)
抽丝剥茧C语言(初阶 下)
|
机器学习/深度学习 人工智能 自然语言处理
带你简单了解Chatgpt背后的秘密:大语言模型所需要条件(数据算法算力)以及其当前阶段的缺点局限性
带你简单了解Chatgpt背后的秘密:大语言模型所需要条件(数据算法算力)以及其当前阶段的缺点局限性
24758 14
|
机器学习/深度学习 弹性计算 监控
重生之---我测阿里云U1实例(通用算力型)
阿里云产品全线降价的一力作,2023年4月阿里云推出新款通用算力型ECS云服务器Universal实例,该款服务器的真实表现如何?让我先测为敬!
36660 15
重生之---我测阿里云U1实例(通用算力型)
|
SQL 存储 弹性计算
Redis性能高30%,阿里云倚天ECS性能摸底和迁移实践
Redis在倚天ECS环境下与同规格的基于 x86 的 ECS 实例相比,Redis 部署在基于 Yitian 710 的 ECS 上可获得高达 30% 的吞吐量优势。成本方面基于倚天710的G8y实例售价比G7实例低23%,总性价比提高50%;按照相同算法,相对G8a,性价比为1.4倍左右。
|
存储 算法 Java
【分布式技术专题】「分布式技术架构」手把手教你如何开发一个属于自己的限流器RateLimiter功能服务
随着互联网的快速发展,越来越多的应用程序需要处理大量的请求。如果没有限制,这些请求可能会导致应用程序崩溃或变得不可用。因此,限流器是一种非常重要的技术,可以帮助应用程序控制请求的数量和速率,以保持稳定和可靠的运行。
29838 52

热门文章

最新文章

下一篇
开通oss服务