博弈论 小偷

博弈论（GameTheory）是一种研究人类决策行为的数学方法，用于研究多个参与者之间的交互和策略选择。机制设计（MechanismDesign）则是博弈论的应用，用于构建合理的市场机制或决策规则，旨在引导参与者按照规则进行交互，在最优化的情况下获得稳定的收益。这里将探讨博弈论与机制设计的基本概念及 ......

Shapley值法是Shapley L.S于1953年提出，为解决多个局中人在合作过程中因利益分配而产生矛盾的问题，属于合作博弈领域。应用 Shapley 值的一大优势是按照成员对联盟的边际贡献率将利益进行分配，即成员$i$所分得的利益等于该成员为他所参与联盟创造的边际利益的平均值。下文从Shapl ......

Gambit 软件可以用于分析和解决各种类型的博弈论问题，从而帮助研究人员深入理解决策制定者之间的相互影响和策略选择。使用 Gambit 软件，研究人员可以建立博弈模型，定义不同决策制定者的策略集合和支付函数，然后通过计算来分析各种可能的博弈结果。例如，Gambit 软件可以用于计算纳什均衡，即在博 ......

完全信息动态博弈中信息是完全的，即双方都掌握参与者对他参与人的策略空间和策略组合下的支付函数有完全的了解，但行动是有先后顺序的，后动者可以观察到前者的行动，了解前者行动的所有信息，而且一般都会持续一个较长时期。 ###一、扩展式博弈（博弈树） ![](https://img2023.cnblogs. ......

这个博弈论是不含 SG 函数的 . 其实可能更像一个杂题选讲 . Nim 游戏：$n$ 堆石子，Alice 和 Bob 轮流选一堆石子取若干个，谁取不了谁输 . 结论：先手必败当且仅当所有石子的异或和为 0 . 关键结论：把 ICG 看成 DAG，如果一个状态只能转移到必胜，那么它必败 . 如果一个 ......

完全信息动态博弈是一种研究行为科学者、决策者和经济学家最关心的博弈理论形式之一。它试图研究他们在某种状况下，如何让一组参与者在他们之间分得最大的利益。完全信息动态博弈是一种行为科学模型，可以通过模拟和抽象实际的情况来研究系统中的行为。因此，它是一种重要的研究工具，可以用来模拟和研究不同情境下的博弈局 ......

博弈论好神奇！！！（虽然不会） [ARC131C] Zero XOR 题目链接 博弈论真是太好了！！！ 先观察题目，看完之后思考，思考完之后直接猜一个结论，反正是跟先后手有关，那就根据规则，猜出来一个神奇的结论： 当n为奇数时，先手必胜 手模几组样例之后，发现很对，那为什么这么对呢？接下来是重头戏。 ......

**博弈论基础** 这里主要讨论两人博弈的博弈，不讨论前沿的多人博弈。 点击查看目录 [TOC] ## 前置知识： * 注意，无特殊说明，所有博弈论的题目均已双方会选择最优方案的前提下进行。 （所以据说我们 $K8He$ 老师想要出一个概率出错的博弈论（ * 平等组合游戏 $ICG$：两人轮流操作， ......

> 博弈论中玩家的选择均为对自己最有利の理论最优解. > >文中提到的必胜状态和必败状态来自要求的游戏起始状态, 但不由其推得. 这句话可能有些抽象，我也不太会表达(重度社恐),所以举个例子: $nim$游戏,3堆石子,分别为1,2,3. 最暴力的解法,我们枚举所有可能的状态, 然后把他们构成一个有 ......

# 博弈论 %%[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} ......

摸牌博弈 ```cpp // 摸牌博弈 // 一维排列的卡牌，其上有不同的数字，两个对手A和B依次从中摸牌 // 卡牌及顺序均对两人可见 // 每次只能从最左或最右摸牌 // 最终摸到的卡牌数字之和最大者获胜 // 两个人都绝顶聪明(两人都会选择对自己有利对对手不利的牌) #include #inc ......

# mm算法随笔 ## 学习笔记（回溯算法） 1. 回溯 递归1.递归的下面就是回溯的过程 2. 回溯法是一个 纯暴力的 搜索、有的时候暴力求解都没有办法，用回溯可以解决。 3. 回溯法解决的问题： * 组合问题 如：1234 两两组合 * 切割问题 如：一个字符串有多少个切割方式 ，或者切割出来是 ......

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

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

在研究过 Nim 游戏及各种变种之后，Orez 又发现了一种全新的取石子游戏，这个游戏是这样的： 有 n 堆石子，将这 n 堆石子摆成一排。 游戏由两个人进行，两人轮流操作，每次操作者都可以从最左或最右的一堆中取出若干颗石子，可以将那一堆全部取掉，但不能不取，不能操作的人就输了。 Orez 问：对于 ......

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

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

应用: 问 2人依次走, 但是不能走到历史状态 看题意是否满足 二分图建图 性质 结论: 如果起始点, 必然在 最大匹配上, 那么先手必赢 不一定在最大匹配上, 那么先手必败 实现: 利用网络流, 先让 和 开始点的边权为0,跑一次 在恢复边权跑一次, 看ans 变大没有 ......

# Zero-sum game 属于非合作博弈，具体来说，是治所有博弈方的利益之和为0或一个常数，namely，有一方收入，必然有某方损失，因而，在零和博弈中，博弈各方不会合作。与之相对，非零和博弈为在不同策略组合下各博弈方的利益之和事不确定的变量，因此又称之为变和博弈，因此，如果存在战略使得各方的 ......

#### 二分图博弈 二分图博弈模型的描述为：在一张二分图上，给定一个起始点S，有两个玩家轮流操作，每轮玩家可以走到一个相邻的且之前没有走到过的点，不能移动的人输掉。 二分图博弈的结论为：如果起始点S一定属于二分图的最大匹配，则先手必胜，否则先手必败。 证明： 1.若S一定属于最大匹配，则先手只需要 ......