博弈论 小偷

海亮01/04博弈论杂题 T1 AT_agc017_d 题意 有一棵 \(N\) 个节点的树，节点标号为 \(1,2,⋯,N\)，边用 \((x_i,y_i)\)表示。 Alice 和 Bob 在这棵树上玩一个游戏，Alice先手，两人轮流操作： 选择一条树上存在的边，把它断开使树变成两个连通块。然 ......

首先，我们需要了解 \(Nim\) 游戏是什么东西。 \(Nim\) 游戏指：两个人，有 \(n\) 堆数，每堆有 \(a_i\) 个，每次可以且仅可以取一堆中的若干个数，求问先手有没有必胜策略（当然两个人都足够聪明）。 首先，先研究显然的必胜策略。比如，我们要得到 \(0\) 这个数，那么当你取完 ......

简单博弈论 必胜态和必败态 假设游戏状态为有向无环图(即游戏状态可以被枚举完同时不会落入重复状态中) 必胜: 存在一个后继为必败态(两个状态均是先手状态，即当前局面下谁先走下一步) 必败: 不存在一个后继为必败态, 所有后继必胜 例: 纠正条件是每次可以往上或往左移动一格 分析: 定义当前每步必胜态 ......

Nim 游戏 甲，乙两个人玩 nim 取石子游戏。 nim 游戏的规则是这样的：地上有 \(n\) 堆石子（每堆石子数量小于 \(10^4\)），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这 \(n\) 堆 ......

Link 一道很有意思的min-max博弈 用树上dp来解决，那么显然的，当前节点是谁取的会影响答案，\(dp2_{i,j}\)表示取当前阶段，被Alice/Bob取走的结果， 并且这个题是取子树上任意的节点，那么还需要保存子树上的信息，故使用\(dp_{i,j}\)记录下子树中的Alice/Bob ......

博弈论是好文明喵！ 博弈论入门提单喵 阶梯博弈 讲解 例题 POJ1704 评价：证明简单，特征比较明显，基本是铜/银牌题 斐波那契博弈 讲解 例题 HDU2516 评价：证明困难，但特征十分明显，直接打表找规律 Nim游戏的有趣题目 D-HihoCoder - 1172 题意：有一行n个硬币，有的 ......

第一章 导论 个体理性与社会最优 第一节 社会的基本问题 资源配置问题 等边际原理 社会：个体之间具有互动行为和相互依赖的群体 羊群效应 社会最基本的问题：协调问题、合作问题 正式和非正式的制度 第二节 个体理性行为 博弈论假设： （1） 博弈的每一个参与人是工具理性的； （2） “每一个参与人是工 ......

演化博弈理论的英文名是Evolutionary Game Theory。演化博弈理论一般会探讨博弈论在生物学中的应用，尤其是纳什均衡的一种很重要的生物学角度的解释：纳什均衡是无数次动态博弈的稳定状态，也可以说成：物竞天择，适者生存。虽然演化思想最初来自于生物学领域，但演化博弈论和演化经济学都把“创新 ......

从经济学角度上讲，对于理性的人，犯罪成本高于犯罪收益，自然就不会去犯罪。所以简单回答就是，违法成本变高会减少犯罪。使违法成本变高有很多方法，最直接最常见的就是严打，即加大对犯罪的处罚力度。小偷-守卫博弈有助于我们对这些方面的思考，该博弈在双方采用纯策略的情况下不存在纳什均衡，但在双方采用混合策略的情 ......

古诺模型（Cournot model）是博弈论中最具有代表性的模型之一，也是是纳什均衡最早的版本。它是法国经济学家古诺(Augustin Cournot)在1938年出版的《财富理论的数学原理研究》一书中最先提出的。而古诺的定义比纳什的定义早了一百多年，足以体现博弈论这样一个学科是深深扎根于经济学的 ......

Cutting Game POJ - 2311 给定一个有 \(n\times m\) 方格的纸片,两个人玩剪纸片游戏,每次可以沿着横向或者纵向笔直地剪一刀,谁先剪出 \(1\times 1\) 的小纸片谁就赢了.给出 \(n,m\) ,判断第一个剪的人能否获胜. (\(n,m \geq 2\) ) ......

信号博弈是经济学和决策理论中的一个重要概念，它旨在解释如何在存在信息不对称的情况下，通过信号传递和反应函数的相互作用，实现均衡。信息不对称是指参与博弈的各方所拥有的信息不同，这可能导致不公平的结果。信号传递是指通过某种行为或信号，传递信息给其他参与方，以改善信息的对称性，反应函数是指根据接收到的信号 ......

博弈论是深刻理解经济行为和社会问题的基础。现在人们说的博弈论，一般指非合作博弈论。它的特征是：人们行为相互作用时，当事人不能达成一个有约束力的协议。或者说，行为人之间的合约对于签约人没有实质性约束力。如现实中的非合作博弈问题的例子是，石油卡特尔欧佩克的产量协议，对于其成员国就没有约束力。你心里想什么 ......

期中寄，人已疯 \(\mathbf{LP}\)： \(A\) 是 \(m\times n\) 的矩阵，\(c\) 是 \(n\) 维向量，\(b\) 是 \(m\) 维向量，以下优化问题被称为 \(\mathbf{LP}\) 问题： \(x\) 是 \(n\times 1\) 维向量，在满足限制 \ ......

二分图·博弈 顾名思义 : 二分图 + 博弈 二分图 首先先知道一些基本方法： 求出二分图最大匹配所必须的点或边，就是求去掉这个点（边）过后最大匹配还是不是原来的最大匹配。 复杂度更优的方法是先跑一遍 Dinic 求出最大流的任意解与这种解下每条边的残量。分别从原点、汇点开始 tarjan 残量不为 ......

【笔记】博弈论 0 基本概念 & 性质 0.1 博弈论 1 SG 函数 ps. 通过 SG 函数来理解三个基本模型，也是不错的选择。 1.2 定义 \(\text{SG}(x)=\text{mex}\{\text{SG}(y_i)\}\)（其中 \(y_i\) 为 \(x\) 的后继状态） 1.3 ......

二分图博弈 什么是二分图博弈： 两个人博弈，每一次自己结束一定会轮到对方，并且自己某个状态选择后对方可以选择的状态是一个区间。 结论： 二分图博弈，作为起点的一方要是选择状态 \(P\)，若状态 \(P\) 一定在最大匹配上，则先手必胜，反之，先手必败。 这里的胜败表示的是“不能继续转移的人”失败。 ......

2023-11-01：用go语言，沿街有一排连续的房屋。每间房屋内都藏有一定的现金， 现在有一位小偷计划从这些房屋中窃取现金， 由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋， 小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额， 给你一个整数数组 nums 表 ......

传送门 description \(T\) 次询问，每次给定 \(n,m,p\)，总共 \(n+m\) 局游戏，每局 A 有 \(p\) 的概率获胜。一局游戏获胜 A 的得分加 1，否则减 1，但是如果 A 在得分为 0 的情况下输了一局，得分不变。求 A 赢 \(n\) 局，输 \(m\) 局后游 ......

博弈论专题 Nim游戏 内容： 有 n 堆石子，每堆石子的石子数给出，甲乙两人回合制取石子，每次可以取任意一堆石子的任意多个（可以直接取完，但不能不取），每个人都按照最优策略来取（抽象），问先手必胜或先手必败？ 结论： 设有 n 堆石子，每堆的个数分别为 a1 , a2 , a3 , …… , an ......

NOIP2023模拟3联测24-博弈树 目录NOIP2023模拟3联测24-博弈树题目大意思路code 题目大意 \(Alice\) 和 \(Bob\) 又开始玩游戏了： 给定一颗 \(n\) 个节点的树，\(Alice\) 和 \(Bob\) 随机选择一个节点作为起点放上棋子，由 Alice 先手 ......

前面讨论的博弈都属于“一次性”：每个人做出一个决策后就结束了。但现实中，人们可能会重复参与同一个博弈。两个囚徒有可能在局子里再次相会，老师和学生会在若干年的时间里为考试而反复博弈，寡头厂商之间每天都在勾心斗角……，就产生了重复博弈的理论研究。重复博弈理论的最大贡献是对人们之间的合作行为提供了理性解释 ......

一开始解决这道题的时候很费解，想了一些办法发现都是无从下手，最后看到一位大佬写的有关博弈论的博客，突然顿悟。以下是题目内容 std的国庆节结束了，由于疫情，校长决定让同学们分批进校。 ​ 至于每批学生来多少人由小蒲和小池负责，两个人轮番负责，需要所有人都可以进校，小蒲学长不想被别人嘲笑自己笨，小池要 ......

1 试给出下述博弈的纳什均衡 解：由划线解得知有一个纯纳什均衡（D,R ）。再看看它是否有纳什均衡，设B的混合策略为\((\gamma,1-\gamma)\)，则有 均衡条件： \[\begin{aligned} & V_A(U)=1 \cdot \gamma+2(1-\gamma)=2-\gamm ......

1 (分钱)两人之间分\(10\)。使用下述方法:每个人说出一个至多为10的数字(非负整数)。如果两人说出的数字之和不超过10，那么每个人得到她所说出的钱数(多出的钱被销毁)，如果两人提出的数字之和超过10并且数目不同，那么说出较小数的人得到自己所说的钱数，而另一个人则得到剩余的钱。如果两数之和超过 ......

我们已经知道，GAN使用的损失函数为特殊的二进制交叉熵函数(BCE Loss)，公式常写作 \[\mathop{min} \limits_G \mathop{max} \limits_D V(D,G)=\mathbb{E}_{x \sim Pdata(x)}[logD(x)]+\mathbb{E}_ ......

逆向选择是指由于信息的差异性或非对称性而导致的市场失灵现象，具体是指在市多交易双方中，参与交易的一方持有某些与交易相关的信息而另一方却不能直接或者间线完全知晓，而且不知情的一方对他方的信息由于验证信息成本的昂贵使得验证在经济上环现实或是不合算，在这种情况下，拥有信息优势的一方有可能隐藏自已的私人信息 ......

在动态博弈中，行动有先后次序；在不完全信息条件下，博弈的每一参与人知道其他参与人的有哪几种类型以及各种类型出现的概率，即知道“自然”参与人的不同类型与相应选择之间的关系，但是，参与人并不知道其他的参与人具体属于哪一种类型。由于行动有先后顺序，后行动者可以通过观察先行动者的行为，获得有关先行动者的信息 ......

前述各种静态博弈实例均有一个共同点，即每个参与者完全知晓自己和对手的支付相关信息。但实际问题中，经常出现某个（或所有）参与者对于其他参与者（甚至自身）支付或策略的信息了解并不充分的情况。一般地，在不完全信息博弈中，并非所有人均知晓同样的信息。博弈参与者除了均知晓的公共信息外，还具有各自的私有信息，后 ......

巴什博弈Bash 1堆n个石子，每次最少取一个，最多取m个 例如 m = 4 判断此刻先手状态（1为胜，0为败） n = 0， 0 n = 1， 1 n = 2， 1 n = 3， 1 n = 4， 1 n = 5， 0 n = 6， 1 n = 7， 1 n = 8， 1 n = 9， 1 n = ......