博弈论

# 博弈论 %%[happyguy](https://home.cnblogs.com/u/happyguy/) ![img](https://img2023.cnblogs.com/blog/2948260/202308/2948260-20230814191514424-571403424.pn ......

- ### 容斥原理 - $|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$ - $|\displaystyle \cup_{i=1}^n A_i |=\sum_{i}|A_i|-\sum_{i,j} ......

静态博弈指的是博弈各方同时做出决策，或者说决策有先后顺序，但是在做决策时博弈者互相看不到其他博弈者的策略，一旦做出决策后就只能等待博弈的结果，其对博弈的发展也不能产生任何影响。静态博弈又称为“同时决策博弈”（Simultaneous Move Games）。静态博弈有很多例子，比如之前介绍的“囚徒困 ......

完全信息静态博弈是指参与者在做出决策之前拥有所有可能的信息，包括对手的策略和利益。因此，每位参与者可以准确地评估各种选择对自己和对手的影响。这种情况下，决策的结果是确定性的，不受随机因素影响。参与者通过理性分析和预测对手的行为，以最大化自身利益。完全信息静态博弈广泛应用于经济、政治和生活中的决策情境 ......

博弈论是现代数学的一个新分支，也是运筹学的一个重要学科。它主要研究公式化了的激励结构间的相互作用，是研究具有斗争或竞争性质现象的数学理论和方法。博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。博弈论已经成为经济学的标准分析工具之一，在金融学、证券学、生物学、经济学、国际关系、计算机 ......

给定一个有 N 个节点的有向无环图，图中某些节点上有棋子，两名玩家交替移动棋子。 玩家每一步可将任意一颗棋子沿一条有向边移动到另一个点，无法移动者输掉游戏。 对于给定的图和棋子初始位置，双方都会采取最优的行动，询问先手必胜还是先手必败。 输入格式 第一行，三个整数N,M,K，N 表示图中节点总数，M ......

现在，有一个 nn 级台阶的楼梯，每级台阶上都有若干个石子，其中第i 级台阶上有 ai 个石子(i≥1)。 两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。 已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。 问如果两人都采用最优策略，先手是否必胜。 ......

# 博弈论 ## 公平组合游戏 > 公平组合游戏（Impartial Game）的定义如下： $\bullet$ 游戏有两个人参与，二者轮流做出决策，双方均知道游戏的完整信息； $\bullet$ 任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与游戏者无关； $\bullet$ ......

# Nim 游戏 ## 基础模型 例题：[CSES 1730](https://vjudge.csgrandeur.cn/problem/CSES-1730) - 有 $n$ 堆石子，第 $i$ 堆石子有 $a_i$ 颗，每个人一次可以从一堆里那任意个石子（至少拿一个），不能操作的人输掉。 - $1 ......

#前言 浅浅复习~~（我想说，国家队论文yyds😍）~~之前学的一点博弈论的皮毛，然后又上某谷练习了一下~~（切了几个水题，感觉全靠直觉/_ \）~~，我觉得我可以进一步学习博弈论的知识了（双击助力蒟蒻助力Alice薄纱Bob🌹） #树上删边游戏 ##问题描述： 给出一个有 N个点的树，有一个点 ......

# SG 函数与 SG 定理 ## 公平组合游戏 公平组合游戏满足以下条件： - 两个玩家参与游戏，轮流操作。 - 游戏以某个玩家不能操作未结束，且不能操作的玩家失败，游戏不含平局。 - 游戏的操作与玩家无关，只与当前的状态有关。 - 游戏状态不会重复出现，若将状态设为点，将一次操作对状态的改变设为 ......

# Nim游戏 #### 给定 $n$ 堆石子，第 $i$ 堆石子有 $A_i$ 个石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿),最后无法进行操作的人视为失败。 若两人均为巨佬，采用最优策略，先手是否必胜。 这种游戏被称作**Nim博弈**。游戏过程 ......

# 博弈论们： - ## Nim 博弈： 先手，后手：第一个，第二个行动者。 必胜，必败：指先手必胜或必败。 定理：Nim 博弈先手必胜，当且仅当：$$\bigoplus_{i=1}^nA_i\ne 0$$ 证明：反证法假设 $A_i'=A_i$ 得出矛盾。（懒，咕了，有机会再说） - ## SG ......

## 引入 OI 中的博弈论主要研究的是**公平组合游戏**。 #### 什么是公平组合游戏（$\text{Impartial Game}$）？ 1. 游戏有**两个人**参与，双方轮流作出决策，双方均知道完整的游戏信息。 2. 任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与 ......

[toc] ## 概念 ### 1、平等组合游戏 + 两人游戏，两人轮流走步 + 有一个状态集，而且通常是有限的 + 有一个终止状态，到达终止状态后游戏结束 + 游戏可以在有限的步数内结束 + 规定好了哪些状态转移是合法的 + 所有规定对于两人是一样的 > 象棋围棋并不满足最后一个条件，因为双方可移 ......

#前言 被Alice狠狠薄纱，Alice啊！我的Alice😭。于是开启博弈论的学习之路(❁´◡`❁)~~（主要是发现前几天刚学了一点现在就忘得差不多了🥀，故决定记录一下）~~ #博弈论 [博弈论](https://oi-wiki.org/math/game-theory/intro/)，是经济学 ......

## 分类 #### 公平组合游戏 - 1.游戏有两个人参与，知道游戏的所有信息。 - 2.在游戏的任意时刻，游戏者可以做出的决策只与当前游戏的状态有关，与游戏者无关。 - 3.游戏中的同一个状态不可能多次抵达，游戏以玩家无法行动为结束，且游戏一定会在有限步后以非平局结束。 #### 非公平组合游戏 ......

# 博弈论基础 ## 一、四大博弈模型 ### 1、巴什博奕 **定义**：一堆n个物品，两个人轮流从中取出不多于m个，最后取光者胜，不能继续取的人输； **结论**：若n%(m+1)!=0，则先手必胜，反之先手必输 ### 2、尼姆博弈 **定义：**n堆物品，每堆物品的个数任意，两人轮流取，每次 ......

**一.公平组合游戏ICG：** 定义为: 1.有两名玩家交替行动 2.在游戏进行的任意时刻，可以执行的合法行动与轮到哪位玩家无关 3.不能行动的玩家判负 **二.mex运算** 定义为: $mex(S) = min\{x\} (x \in N, x \notin S)$ 即为不属于集合$S$的最小 ......

## $\text{CF388C}$ ### 题意简述： 桌子上有 $n$ 堆牌。每张牌上都有一个正整数。Ciel可以从任何非空牌堆的顶部取出一张牌，Jiro可以从任何非空牌堆的底部取出一张牌。Ciel先取，当所有的牌堆都变空时游戏结束。他们都想最大化他所拿牌的分数（即每张牌上正整数的和）。问他们所 ......

###纯博弈： 单纯的动机组合，离散的集合 ###混合博弈： 加入了概率论，以百分比的概率执行不同的的动机。，概率分布 零和博弈、合作博弈、协同博弈 ###扩展博弈和非完美信息 ###扩展博弈、贝叶斯博弈 ###纳什均衡 任何一位玩家在此策略组合下单方面改变自己的策略（其他玩家策略不变）都不会提高自 ......

# 简单博弈论 ## Nim游戏 Nim游戏满足以下三个条件: (1)两名玩家交替行动 (2)游戏过程中，可以执行的的行动和轮到哪位玩家没有关系 (3)不能行动的玩家判负 比如围棋就不是一种Nim游戏，因为围棋有黑白两子不满足(2)，围棋判断输赢规则较为复杂不符合(3)。下面的取石子游戏就是一个Ni ......

# 博弈论入门 * 必败情况为P，必胜情况为N，我们要得出N一定有方法能转换到P，P任意操作都会到N ## 1.巴什博弈 * 两个顶尖聪明的人在玩游戏，有一堆n个石子，每次每个人能取$[1,m]$个石子，不能拿的人输，请问先手与后手谁必败？ * 1~m个石子，先手必胜 * 反推m+1个石子只能到1~ ......

在许多地方曾经行过这样一个小游戏，摆出三堆硬币。分别包含3枚、5枚、7枚。两人轮流行动每次可以任选一堆，从中取走任意多枚硬币，可把一堆取完，但不能不取。取走最后一枚硬币者获得胜利。 这类游戏可以推广为更加一般的形式: > 给定 $n$ 堆物品，第 $i$ 堆物品有 $A_i$ 个。两名玩家轮流行动， ......

Alice 和 Bob 正在一个序列 ai​ 上玩游戏，Alice 先手，轮流玩。每一轮当前玩家可以取走序列中任意一个数，直到取完。 如果最后 Ailce 取走的数的和为偶数，则 Ailce 赢，否则 Bob 赢。保证每个人用最优策略玩。对于每组数据，输出赢家。 输入输出样例 输入 #1复制 4 3 ......

# 博弈论入门 ## 前言： 本篇按照 Qingyu 在省集讲的加入我这个萌新的萌新理解而成。 听了 Qingyu 的博弈论讲解，感觉我之前学过的博弈就是冰山一角。 由于有一些东西没听懂，就主要写写我听懂的部分，没懂得以后再说吧。 所以这篇只是一个入门，关于博弈的一些习题可能会咕咕咕。 ## 平等博 ......

### 闲话 这其实是个大作业来着……然而早上八点才开始写，中间还上了好几个小时的课（虽然全都没有听）（大嘘）。所幸最终还是从理论到代码从头写完了，DDL 刚过几分钟……认真完成作业对我来说实属不易，于是顺便贴到博客上来以供来者。下面是实验报告的内容。 ### 实验原理 #### 纯策略求解 直接枚 ......

博弈论在 OI 中主要研究组合博弈，可能也会与其它的知识点相结合。做博弈论题时，我们要利用已有的博弈结论，或是建出模型解决问题。 # 组合博弈 组合博弈一般分为两种： - 平等博弈：可允许的操作只和当前局面的状态而和操作的玩家无关。 - 不平等博弈：可允许的操作还和当前操作的玩家相关。 比如说围棋， ......

教练让我学三周数论，然而数论多少还是无聊了点，所以浅学一下博弈论划划水。 （只是简单学了一下，不会记特别多。） ###**巴什博弈：** 有两个聪明人玩游戏，有n个石子，两人轮流从这堆石子里取出一部分，每人一次可以取[1,m]个石子，最后不能拿的人输。两人都会选择最优策略的情况下，问：先手和后手谁赢 ......

基础概念 相关参考资料：易老师整理（放个大佬的链接） Nim Game 题目：有n堆石子，数量分别为$a_1,a_2,...,a_n$，两个玩家均足够聪明，轮流拿石子，每次仅可以从任意一堆中拿走任意数量的石子。 结论：当$a_1⊕a_2⊕...⊕a_n≠0$时，先手必胜；否则先手必败。 而且，令$a ......