博弈规则的设计
博弈策略求解是博弈问题中的一个重要内容，另外一个重要的内容是博弈规则的设计：
也就是说，假设博弈的参与者都是足够理性的，如何设计一个博弈规则能确保公正性或者达到设计者的最大利益。主要的难点是：规则复杂，计算量大。
主要应用于：
- 拍卖竞价：互联网广告投放、车牌竞价
- 供需匹配：污染权、学校录取
- 公正选举：选举制度、表决制度、议席分配
G-S算法(Gale-Shapley)
在规则设计里面有不同的算法，比方说有GS算法：
- 在生活中，人们通常会碰到与资源匹配相关的决策问题(如求职就业、报考录取等)，这些需要双向选择的情况被称为是双边匹配问题。在双边匹配问题中，需要双方互相满足对方的需求才会达成匹配。
- 匹配的稳定是指没有任何人能从偏离稳定状态中获益。如果将匹配问题看做是一种合作博弈的话，稳定状态解就是纳什均衡解。
- 1962年，美国数学家大卫·盖尔和博弈论学家沙普利提出了针对双边稳定匹配问题的解决算法，并将其应用于稳定婚姻问题的求解。
- 稳定婚姻问题(stable marriage problem)是指在给定成员偏好的条件下，分两组成员寻找稳定匹配。由于这种匹配并不是简单地价高者得，所以匹配解法应考虑双方意愿。
- 稳定婚姻问题的稳定解是指不存在未达成匹配的两个人都更倾向于选择对方胜过自己当前的匹配对象。
稳定婚姻问题
- 假设有相同数量的单身男性和单身女性，其构成男性集合$M=\{m_{1},m_{2}, \cdots , m_{n}\}$和女性集合$W=\{w_{1},w_{2},\cdots,w_{n}\}$。
- 单身男性向最喜欢的女性表白
- 所有收到表白的女性从向其表白男性中选择最喜欢的男性，暂时匹配
- 未匹配的男性继续向没有拒绝过他的女性表白。收到表白的女性如果没有完成匹配，则从这一批表白者中选择最喜欢男性。即使收到表白的女性已经完成匹配，但是如果她认为有她更喜欢的男性，则可以拒绝之前的匹配者，重新匹配。
- 如此循环迭代，直到所有人都成功匹配为止
- 这一过程中，男生使用贪心策略告白，而女生具有选择权，一旦出现不稳定的匹配者，即替换当前匹配者。
最大交易圈算法(Top-Trading Cycle algorithm)
- 匹配问题中，还有一类交换不可分的的标的物的匹配问题，被称为单边匹配问题，如远古时期以物易物、或者宿舍的床位分配。
1974年，沙普利和斯夫提出了针对单边匹配问题的稳定匹配算法：最大交易圈算法(TTC)，算法过程如下：
- 首先每个交易者连接一条指向他最喜欢的标的物的边，并从每一个标的物连接到其占有者或者是具有最高优先权的交易者。
- 此时形成一张有向图，且比存在交易圈，对于交易圈中的交易者，将每人指向节点所代表的标的物赋予其，同时交易者放弃原先占有的标的物，占有者和匹配成功的标的物离开匹配市场
- 接着从剩余的交易者和标的物之间重复进行交易圈匹配，直到无法形成交易圈，算法停止。
室友匹配问题
参考
- 非完全信息博弈中的虚拟遗憾最小化(CFR)算法(附实现代码)
- 吴飞，《人工智能导论：模型与方法》，高等教育出版社出版(拟2020年2月出版)
- 人工智能：模型与算法
- 关于德州扑克AI中Counterfactual Regret Minimization的介绍
我的微信公众号名称：深度学习与先进智能决策
微信公众号ID：MultiAgent1024
公众号介绍：主要研究分享深度学习、机器博弈、强化学习等相关内容！期待您的关注，欢迎一起学习交流进步！
