(8.2)--PPT-博弈规则设计机器学习模型与算法.ppt

博弈规则设计问题与认知目标问题：假设某个寝室有4位同学和4个床位，每个同学都有自己的偏好和需求，如有的喜欢上铺，有的喜欢下铺，如何合理地进行进行床位分配，尽可能地满足4位同学地需求。认知目标：掌握双边匹配算法掌握单边匹配算法博弈规则设计：博弈规则设计：双边匹配算法双边匹配算法在生活中，人们常常会碰到与资源匹配相关的决策问题(如求职就业、报考录取等)，这些需要双向选择的情况被称为是双双边边匹匹配配问问题题。在双边匹配问题中，需要双方互相满足对方的需求才会达成匹配。稳定婚姻问题稳定婚姻问题（stable marriage problem）1962年年，美美国国数数学学家家大大卫卫盖盖尔尔和和博博弈弈论论学学家家沙沙普普利利提提出出了了针针对对双双边边稳稳定定匹匹配配问问题题的的解解决决算算法法（也也被被称称为为Gale-Shapely算算法法或或G-S算算法法），并并将将其其应应用用于于稳稳定定婚婚姻姻问问题题的的求求解解Gale 1962，算法过程如下：，算法过程如下：1)单身男性向最喜欢的女性表白单身男性向最喜欢的女性表白2)所有收到表白的女性从向其表白男性中选择最喜欢的男性，暂时匹配所有收到表白的女性从向其表白男性中选择最喜欢的男性，暂时匹配3)未未匹匹配配的的男男性性继继续续向向没没有有拒拒绝绝过过他他的的女女性性表表白白。收收到到表表白白的的女女性性如如果果没没有有完完成成匹匹配配，则则从从这这一一批批表表白白者者中中选选择择最最喜喜欢欢男男性性。即即使使收收到到表表白白的的女女性性已已经经完完成成匹匹配，但是如果她认为有她更喜欢的男性，则可以拒绝之前的匹配者，重新匹配配，但是如果她认为有她更喜欢的男性，则可以拒绝之前的匹配者，重新匹配4)如此循环迭代，直到所有人都成功匹配为止如此循环迭代，直到所有人都成功匹配为止博弈规则设计：博弈规则设计：双边匹配算法双边匹配算法博弈规则设计：博弈规则设计：单边匹配算法单边匹配算法在匹配问题中，除了需要双向选择的双边匹配问题，还有一种类似于以物易物方式的交换匹配问题，被称为单单边边匹匹配配问问题题，例如室友的匹配或者是座位的分配。这些问题中分配的对象都是不可分的标的物，他们只能属于一个所有者，且可以属于任何一个所有者。博弈规则设计：博弈规则设计：单边匹配算法单边匹配算法对于单边匹配问题，1974年，沙普利和斯卡夫提出了针对单边匹配问题的稳定匹配算法“最大交易圈算法（Top-trading cycle，TTC）”Shapley 1974，算法过程如下：1)首先记录每个标的物的初始占有者，或者对物品进行随机分配。2)每个交易者连接一条指向他最喜欢的标的物的边，并从每一个标的物连接到其占有者或是具有高优先权的交易者。3)此时形成一张有向图，且必存在环，这种环被称为“交易圈”，对于交易圈中的交易者，将每人指向节点所代表的标的物赋予交易者，同时交易者放弃原先占有的标的物，占有者和匹配成功的标的物离开匹配市场。4)接着从剩余的交易者和标的物之间重复进行交易圈匹配，直到无法形成交易圈，算法停止。博弈规则设计：博弈规则设计：单边匹配算法单边匹配算法稳定室友匹配问题就是一个典型的单边匹配问题。假设某寝室有A、B、C、D四位同学和1、2、3、4四个床位，当前给A、B、C、D四位同学随机分配4、3、2、1四个床位。表表8.12 床位偏好顺序床位偏好顺序博弈规则设计：博弈规则设计：单边匹配算法单边匹配算法在在图图8.6可可以以看看出出:，A和和D之之间间构构成成一一个个交交易易圈圈，可可达达成成交交易易，所所以以A得得到到床床位位1，D得到床位得到床位4，之后将，之后将 A和和D以及以及1和和4从匹配图中移除。从匹配图中移除。从从图图8.7可可以以看看出出，B和和C都都希希望望得得到到床床位位2，无无法法再再构构成成交交易易圈圈，但但是是由由于于C是床位的本身拥有者，所以是床位的本身拥有者，所以C仍然得到床位仍然得到床位2，B只能选择床位只能选择床位3。最后交易结果最后交易结果A1，B 3，C 2，D 4图图8.6 第一轮单边匹配第一轮单边匹配图图8.7 第二轮单边匹配第二轮单边匹配课后题医生医生偏好偏好11 2 3 4 5 6 725 4 3 2 1 7 636 1 2 4 3 7 542 3 1 4 5 6 753 4 5 2 1 7 666 2 4 3 5 1 774 2 3 1 5 7 6假设某医院有七名医生负责一周的夜班值守，每人值一天夜班，但是不同医生希望值夜班的偏好有所不同（见表）。值班日偏好顺序值班日偏好顺序请给出一个尽量照顾每位医生偏好的值班表。