二分图博弈

简介

考虑这样一类游戏

1.博弈者人数为两人，双方轮流进行决策。
2.博弈状态（对应点）可分为两类（状态空间可分为两个集合），对应二分图两边（X集和Y集）。任意合法的决策（对应边）使状态从一类跳转到另一类。（正是由于这个性质使得问题可以用二分图描述）
3.不可以转移至已访问的状态。（不可重复访问点）
4.无法转移者判负。

我们称这样的博弈为二分图博弈

结论：

如果起点是最大匹配非必须点，先手必败

否则先手必胜