博弈论术语表

English	中文	说明
player	玩家	也可译为参与者；本笔记统一使用“玩家”。
pure strategy	纯策略	不使用随机化的单一策略。
mixed strategy	混合策略	在纯策略集合上的概率分布。
strategy profile	策略组合	各玩家策略组成的整体；有时英文写作 profile。
payoff	收益	玩家从某个结果或策略组合中得到的效用值。
expected payoff	期望收益	在随机化或自然节点下按概率加权的收益。
best response	最优反应	在其他玩家策略给定时能最大化自身收益的策略。
Nash Equilibrium	纳什均衡	没有玩家能通过单方面偏离提高自身收益的策略组合。
strategic game	策略式博弈	也称 normal-form game；本笔记按原文语境译为“策略式博弈”。
unilateral deviation	单方面偏离	只有一个玩家改变策略，其他玩家策略保持不变。
finite	有限	集合或博弈对象包含有限个元素。
support	支撑集	混合策略中被赋予正概率的纯策略集合。
Nash’s Theorem	纳什定理	每个有限 $n$ 人策略式博弈都存在混合纳什均衡。
fixed point	不动点	满足 $f(x^\ast) = x^\ast$ 的点。
compact	紧	拓扑/分析中的紧性概念。
convex	凸	任意两点连线仍在集合内。
continuous function	连续函数	在 Brouwer 不动点定理中使用的连续映射。
Pareto efficient	帕累托有效	不存在能让所有人不变差且至少一人变好的另一个策略组合。
Pareto optimal	帕累托最优	与 Pareto efficient 同义。
social welfare	社会福利	本笔记中指所有玩家收益之和。
symmetric game	对称博弈	两个玩家拥有相同策略集合，且收益在交换玩家后对应相同。
evolutionarily stable strategy	进化稳定策略	常缩写为 ESS。
zero-sum game	零和博弈	一个玩家的收益等于另一个玩家损失的 2 人博弈。
payoff matrix	收益矩阵	用矩阵表示纯策略组合下玩家收益。
minmaximizer	minmaximizer	玩家 1 最大化自身可保证的最坏情形收益；保留英文术语以避免和 maxminimizer 混淆。
maxminimizer	maxminimizer	玩家 2 最小化玩家 1 可达到的最好情形收益；保留英文术语以避免和 minmaximizer 混淆。
minimax value	minimax 值	零和博弈中唯一的值 $v^\ast$。
minimax profile	minimax 策略组合	达到 minimax 值的策略组合。
optimization problem	优化问题	通过目标函数和约束条件刻画的问题。
linear programming	线性规划	也称 linear optimization，线性优化。
linear optimization	线性优化	与 linear programming 同义。
linear objective function	线性目标函数	由变量的一次项线性组合加常数构成。
optimization criterion	优化准则	最大化或最小化。
linear constraint	线性约束	线性不等式或等式约束。
feasible	可行	存在满足所有约束的解。
infeasible	不可行	不存在满足所有约束的解。
unbounded	无界	目标值可以无限增大或减小。
optimal feasible solution	最优可行解	常缩写为 OFS。
Fourier-Motzkin Elimination	Fourier-Motzkin 消元法	用于消去线性不等式系统中的变量。
Gaussian Elimination	高斯消元法	求解线性方程组的经典消元方法。
redundant	冗余	去掉后不改变问题可行域或结论的变量/约束。
Simplex Algorithm	单纯形算法	求解线性规划的经典算法。
local optimum	局部最优	在邻域内没有更优解。
global optimum	全局最优	在整个可行域内最优。
primal form	原始形式	LP 的一种标准化形式。
slack variable	松弛变量	把不等式约束转换为等式约束时加入的非负变量。
basis	基	dictionary 中位于等式左侧、用于表示基本解的一组变量。
dictionary	字典	单纯形法中以基变量表示非基变量的 LP 表示形式。
basic feasible solution	基本可行解	常缩写为 BFS，对应几何上的顶点。
pivoting	枢轴变换	单纯形法中从一个基移动到相邻基的操作。
neighboring BFS	相邻 BFS	通过一次 pivoting 可达的基本可行解。
primal LP	原始 LP	与 dual LP 相对的原问题。
dual LP	对偶 LP	由原始 LP 构造出的对偶问题。
LP duality	LP 对偶性	线性规划原问题与对偶问题之间的关系。
weak duality	弱对偶性	原问题可行解目标值不超过对偶问题可行解目标值。
strong duality	强对偶性	在适当条件下原问题和对偶问题最优值相等。
adversary	对抗者	用于说明对偶问题的直观角色。
complementary slackness	互补松弛	最优原始解和对偶解满足的一组等式/零条件。
dominance	支配	策略之间的偏序关系。
dominant strategy	占优策略	至少不差于所有其他策略的策略。
strictly dominant strategy	严格占优策略	严格优于所有其他策略的策略。
dominated strategy	被支配策略	存在另一个策略支配它。
strictly dominated strategy	被严格支配策略	存在另一个策略严格支配它。
weakly dominated strategy	被弱支配策略	存在另一个策略至少不差，并在某些情况下更好。
pure counter profile	纯反策略组合	除玩家 $i$ 外其他玩家的纯策略组合。
common knowledge	共同知识	所有玩家知道，且知道彼此知道，并无限递归下去的知识。
rationality	理性	玩家按自身收益最大化行动的假设。
residual game	剩余博弈	删除某些策略后得到的博弈。
iterated strategy elimination	迭代策略消除	反复删除被支配策略的过程。
system of constraints	约束系统	由等式、不等式和变量条件组成的系统。
rational NE	有理数 NE	概率和收益参数可用有理数表示的纳什均衡。
polynomial sized	多项式大小	数字表示长度随输入规模多项式增长。
extensive form game	扩展式博弈	用博弈树表示玩家按时间顺序行动的博弈。
game tree	博弈树	扩展式博弈中的树结构。
alphabet	字母表	形式化树定义中的动作符号集合。
node	节点	博弈树中的状态。
child	子节点	由当前节点采取一个动作后到达的节点。
action	动作	某节点处可选的移动。
leaf node	叶节点	没有子节点的终止节点。
terminal node	终止节点	与 leaf node 同义。
path	路径	博弈树中的节点序列。
play	对局	从根开始的完整路径。
chance node	机会节点	由随机性或自然决定动作的节点。
nature node	自然节点	与 chance node 同义。
information set	信息集	玩家无法区分的一组节点。
perfect information	完美信息	每个信息集都只含一个节点。
imperfect information	不完美信息	存在大小大于 1 的非平凡信息集。
perfect recall	完美记忆	玩家不会忘记自己的过去动作和经历过的信息集。
behavior strategy	行为策略	在每个信息集上独立地对动作随机化的策略。
subgame	子博弈	信息集自包含的博弈树子树。
subgame perfect equilibrium	子博弈完美均衡	在每个子博弈中都构成 NE 的策略组合。
subgame perfect Nash equilibrium	子博弈完美纳什均衡	与 subgame perfect equilibrium 同义，常缩写为 SPNE。
non-credible threat	不可信威胁	实际执行时并不理性的威胁。
trembling-hand perfect equilibrium	颤抖手完美均衡	对 NE/SGPE 的进一步精炼。
Kuhn’s Theorem	Kuhn 定理	有限完美信息扩展式博弈存在纯策略 SPNE。
depth	深度	节点字符串长度或树中最大节点深度。
bottom up algorithm	自底向上算法	从叶子/低层子问题向根节点计算。
determined	被决定的	零和博弈中 maxmin 值和 minmax 值相等。
winning strategy	必胜策略	保证某玩家获胜的纯策略。
win-lose-draw game	胜负和博弈	收益可能为胜、负、和三类。
alpha-beta pruning	alpha-beta 剪枝	minimax 搜索中的剪枝技术。
maximizer	最大化玩家	试图最大化评分/收益的玩家。
supremum	上确界	最小上界，记作 $\sup$。
infimum	下确界	最大下界，记作 $\inf$。
determinacy	决定性	博弈是否被决定的性质。
game graph	博弈图	用顶点和边表示可重复状态的博弈结构。
vertex	顶点	博弈图中的位置或配置。
edge	边	博弈图中从一个顶点到另一个顶点的可行动作。
start vertex	起始顶点	图上博弈开始的位置。
game on graph	图上的博弈	由博弈图、起始顶点和收益函数定义的博弈。
dead end	死端	没有外出边的顶点。
history oblivious payoff	历史无关收益	收益只依赖当前终止顶点或无限对局中无限次出现的顶点集合。
finitistic payoff	有限式收益	所有无限对局具有相同收益的历史无关收益。
memoryless strategy	无记忆策略	只依赖当前顶点、不依赖到达该顶点历史的策略。
memorylessly determined	无记忆决定	双方都有达到博弈值的无记忆策略。
value-achieving strategy	达值策略	达到博弈值的策略。
P-time algorithm	多项式时间算法	运行时间为输入规模多项式的算法。
Markov Decision Process	马尔可夫决策过程	常缩写为 MDP。
successor	后继	从当前顶点通过一条边可到达的顶点。
mean payoff	平均收益	长期平均意义下的收益目标。
discounted total payoff	折扣总收益	使用折扣因子累加未来收益的目标。
discount factor	折扣因子	控制未来收益权重的参数，通常 $0 < \beta < 1$。
target vertex	目标顶点	到达概率目标中的指定顶点。
memoryless optimal strategy	无记忆最优策略	最优且只依赖当前顶点的策略。
Bellman optimality equations	Bellman 最优性方程	描述最优值函数的递归方程。
value iteration	值迭代	通过反复应用 Bellman 算子逼近最优值。
stochastic game	随机博弈	状态转移带概率性的动态博弈。
simple stochastic game	简单随机博弈	常缩写为 SSG。
one-step reward	单步奖励	当前动作组合产生的即时奖励。
strategy improvement algorithm	策略改进算法	通过改进当前策略来寻找最优策略的算法。
parity game	奇偶博弈	一类可归约到 SSG 的无限图博弈。
mean payoff game	平均收益博弈	以长期平均收益为目标的图博弈。
selfish network routing	自私网络路由	个体按自身成本选择路径的网络路由博弈。
congestion game	拥塞博弈	玩家选择资源集合，资源成本取决于使用人数。
resource	资源	拥塞博弈中被玩家选择和共同使用的对象。
cost function	成本函数	资源使用成本关于拥塞人数的函数。
congestion	拥塞	使用同一资源的玩家数量。
total cost	总成本	玩家所选资源成本之和。
best response dynamics	最优反应动态	玩家反复切换到更优反应的动态过程。
improvement step	改进步	单个玩家单方面切换到更好策略的一步。
potential function	势函数	用于刻画改进动态单调变化的函数。
exact potential	精确势	单个玩家收益/成本变化与势函数变化精确相同的势函数。
flow network	流网络	带源点、汇点和边延迟/容量结构的网络。
Braess’s paradox	Braess 悖论	增加道路反而可能让均衡表现变差的现象。
price of anarchy	无政府代价	常缩写为 PoA，衡量自私行为导致的效率损失。
pure price of anarchy	纯无政府代价	只比较纯 NE 的 PoA 版本。
truthful mechanism	真实机制	激励参与者如实报告估值的机制。
VCG auction	VCG 拍卖	一类真实机制。
atomic congestion game	原子拥塞博弈	玩家数量有限、每个玩家不可分的拥塞博弈。
non-atomic network flow game	非原子网络流博弈	单个玩家影响可忽略的网络流博弈。
auction	拍卖	按规则分配物品并决定支付价格的机制。
single-item auction	单物品拍卖	只拍卖一个物品的拍卖。
sealed-bid auction	密封报价拍卖	投标者同时提交不可见报价的拍卖。
bidder	投标者	拍卖中的玩家。
valuation	估值	投标者对物品的私人价值。
price	价格	获胜者需要支付的金额。
true valuation	真实估值	投标者对物品的真实价值。
Vickrey auction	Vickrey 拍卖	二价密封报价拍卖。
second-price auction	二价拍卖	最高报价者获胜但支付第二高报价。
first-price auction	一价拍卖	最高报价者获胜并支付自己的报价。
complete information game	完全信息博弈	每个玩家知道所有相关收益/类型信息的博弈。
incomplete information game	不完全信息博弈	玩家不知道其他玩家某些私人信息的博弈。
Bayesian game	贝叶斯博弈	用类型和共同先验建模不完全信息的博弈。
type	类型	玩家持有的私人信息。
signal	信号	与 type 类似，用于表示私人信息。
common prior	共同先验	所有玩家都知道的类型联合概率分布。
conditional probability	条件概率	在给定自身类型后对其他玩家类型的概率判断。
Bayesian Nash equilibrium	贝叶斯纳什均衡	常缩写为 BNE。
truth revealing	真实揭示	报价/报告等于真实估值或真实类型。
revenue equivalence principle	收入等价原理	若干拍卖机制在对称 BNE 中期望收入相同的机制设计结果。
exchange economy	交换经济	代理人拥有初始禀赋并交换可分商品的经济模型。
divisible good	可分商品	可以连续分割的商品、服务或资源。
initial endowment	初始禀赋	代理人初始拥有的商品束。
bundle	商品束	多种商品数量组成的向量。
continuity	连续性	效用函数的合理性条件之一。
quasi-concavity	拟凹性	偏好集合凸的一类效用性质。
non-satiation	非饱和性	更多商品不会让代理人更差，通常更好。
optimal demand	最优需求	给定价格下可负担且效用最大的商品束集合。
market equilibrium	市场均衡	给定价格下需求最优且市场出清的配置。
price equilibrium	价格均衡	与 market equilibrium 同义。
market clears	市场出清	需求不超过供给，且有过剩供给的商品价格为零。
barter economy	物物交换经济	不使用货币的交换经济。
First Fundamental Theorem of Welfare Economics	福利经济学第一基本定理	市场均衡配置是帕累托最优的定理。
social choice function	社会选择函数	将个体偏好组合映射到一个社会结果。
outcome	结果	社会选择或机制中的候选结果。
candidate	候选项	社会选择中的可选结果。
preference ordering	偏好排序	对候选结果的完全排序。
strategically manipulated	策略性操纵	参与者通过虚报偏好改变结果并获益。
incentive compatible	激励相容	真实报告不会被任何参与者策略性操纵。
strategy-proof	策略免疫	与 incentive compatible 同义。
dictatorship	独裁制	结果总是选出某个固定玩家最偏好的候选项。
Gibbard-Satterthwaite theorem	Gibbard-Satterthwaite 定理	非独裁且覆盖所有结果的社会选择函数不可避免可操纵。
Arrow’s Impossibility Theorem	Arrow 不可能定理	偏好聚合中不存在满足所有理想条件的好规则。
Vickrey-Clarke-Groves mechanism	Vickrey-Clarke-Groves 机制	常缩写为 VCG 机制。
payment	支付	机制中参与者需要缴纳的金额。
purported utility	声称效用	基于声明估值计算出的效用。
matching market	匹配市场	研究双方或多方对象如何匹配的市场模型。
unit-demand auction	单需求拍卖	每个买家最多需要一个物品的拍卖。
Myerson’s revenue-optimal auction	Myerson 收入最优拍卖	最大化卖方期望收入的经典拍卖理论结果。
Stable Marriage Problem	稳定婚姻问题	匹配市场中的经典稳定匹配问题。