高级人工智能 - 博弈ii

《高级人工智能 - 博弈ii》由会员分享，可在线阅读，更多相关《高级人工智能 - 博弈ii（56页珍藏版）》请在金锄头文库上搜索。

1、高级人工智能高级人工智能 沈华伟 中国科学院计算技术研究所 2016.11.8 课程课程回顾回顾 博弈 基本概念 纳什均衡 机制设计 两个经济学的应用 拍卖 讨价 课堂作业课堂作业回顾回顾 海盗分金币 问题描述：有5个海盗抢到了100个金币，经过激烈争 论，就如何分配达成以下协议： 抽签决定每个人提分配方案的顺序 抽到1号签的海盗首先提出自己的分配方案，然后所有人 表决（包括方案提出者），当且仅当半数或超过半数以上 的人同意的时候，才按照他提出的方案执行，否则他会被 扔进海里 1号海盗的方案如果未被通过，那么2号海盗提自己的方案， 规则和上述一样，直到某个方案通过 给出最终的分配方案 提示：

2、从后往前回滚 海盗分金币海盗分金币 从后向前回滚 如果前三个海盗都死了，只剩最后两个海盗，那么4号 海盗可以提出分配方案（100，0），他自己同意，满 足规则，所以会执行 4 (100，0) 海盗分金币海盗分金币 所有的海盗都知道这一点，因此第三个海盗会给 出如下策略 如果前两个海盗死了，第三个海盗为了使自己的方案通 过，并使自己获得最大的利益，那么他的分配方案即为 （99，0，1），3号和5号肯定会同意。因为5号这样至 少还能得到1个金币 3 结束 4 （100，0） （99，0，1） 同意 不同意 海盗分金币海盗分金币 同理，可以推出2号海盗的分配方案为（99，0， 1，0） 2 3 结束

3、 结束 4 （100，0） （99，0，1） （99，0，1，0） 同意 不同意 同意 不同意 海盗分金币海盗分金币 最终，1号海盗的方案（98，0，1，0，1） 1 结束 2 3 4 结束 结束 （98，0，1，0，1） （99，0，1，0） （99，0，1） （100，0） 同意 同意 同意 不同意 不同意 不同意 课程内容课程内容 maxmin策略和策略和minmax策略策略 匹配市场 中介市场 议价权 maxmin策略策略 maxmin策略 最大化自己最坏情况时的效用（收益） argmaxmin, 局中人的策略 除之外其他局中人的策略 局中人的效用函数 maxmin策略示例策略示例 性

4、别大战 妻子的策略：以概率选择韩剧，以概率1 选择体育 丈夫的策略：以概率选择韩剧，以概率1 选择体育 妻子的期望收益 妻子的期望收益关于丈夫的策略是单调的 最小值的可能取值点： = 0或 = 1 妻子的最坏期望收益 妻子的maxmin策略为 韩剧 体育 韩剧 1,2 0,0 体育 0,0 2,1 丈 夫妻子 丈夫: 妻子: , = 2 + 1 1 = 3 + 1 min, = min 1 ,2 argmaxmin, maxmin策略示例策略示例 性别大战 解得 =1 3 妻子的maxmin策略 1/3概率选择韩剧，2/3概率选择体育 同理，丈夫的maxmin策略 2/3概率选择韩剧，1/3概

5、率选择体育 argmaxmin, = argmaxmin 1 ,2 2 1 maxmin策略策略 为什么要用maxmin策略？ 最小化损失，控制风险 预防其它局中人的不理性给自己带来损失 minmax策略策略 minmax策略 最小化对手的最大收益（收益） argminmax, 局中人的策略 对手的策略 对手的效用函数 minmax策略示例策略示例 性别大战 妻子的策略：以概率选择韩剧，以概率1 选择体育 丈夫的策略：以概率选择韩剧，以概率1 选择体育 丈夫的期望收益（注意：妻子的minmax策略考虑到是丈夫的收益） 丈夫的期望收益关于其策略是单调的 最大值的可能取值点： = 0或 = 1 丈

6、夫的最好期望收益 妻子的minmax的策略为 韩剧 体育 韩剧 1,2 0,0 体育 0,0 2,1 丈 夫妻子 , = + 2 1 1 = 3 2 2 +2 max, = max 2 2, argminmax, 丈夫: 妻子: minmax策略示例策略示例 性别大战 解得 =2 3 妻子的minmax策略 2/3概率选择韩剧，1/3概率选择体育 同理，丈夫的minmax策略 1/3概率选择韩剧，2/3概率选择体育 argminmax 2 2, 2 2 maxmin策略和策略和minmax策略策略 性别大战小结 maxmin策略（以我为主） 妻子1/3概率选择韩剧，2/3概率选择体育 丈夫2/

7、3概率选择韩剧，1/3概率选择体育 minmax策略（抑制对手） 妻子2/3概率选择韩剧，1/3概率选择体育 丈夫1/3概率选择韩剧，2/3概率选择体育 混合纳什均衡策略（抑制对手） 妻子2/3概率选择韩剧，1/3概率选择体育 丈夫1/3概率选择韩剧，2/3概率选择体育 maxmin策略和策略和minmax策略策略 零和博弈情况下 minmax和maxmin是对偶的 minmax策略和maxmin策略等价于纳什均衡策略 Heads Tails Heads 1,-1 -1,1 Tails -1,1 1,-1 玩 家 一玩家二 零和博弈的例子 课程内容课程内容 maxmin策略和minmax策略

8、匹配市场匹配市场 中介市场 议价权 匹配问题匹配问题(matching) 生活中有很多匹配问题 分宿舍：学生和宿舍之间的匹配 结婚：男性和女性的匹配 大作业分组：搭档匹配 匹配蕴含着很多智能问题 价格的作用 匹配问题示例匹配问题示例 学生宿舍分配 每个学生列出自己可以接受 的宿房间 Vikram认为宿舍1,2,3均可接受 Wendy只接受房间1 学生对房间偏好采用一个二 部图表示 左侧节点是房间 右侧节点是学生 连边表示偏好关系 完全匹配完全匹配 完全匹配 对于两类节点集合大小一样 的二部图，选择数目和节点 个数一样的边，使得每类节 点中的任意一个节点在另一 类节点中都有唯一的对应者 如何判断

9、一个二部图是否 存在完全匹配呢？ 如果存在，找到这个完全匹 配即可 如果不存在，怎么办呢？ 匹配定理匹配定理 匹配定理 对于左右两部节点数相同的二部图，如果其不存在完全 匹配，那么该二部图一定包含一个受限集。 受限集 假设是二部图某部节点集的子集， 是的邻居节 点集合（注意：该集合的节点一定来自二部图的另一部 节点集合），如果 中的节点个数 小于中的 节点个数 ，即 ，则称为受限集 匹配定理匹配定理 完全匹配不存在的例子 受限集 受限集总是成对出现 Vikram,Wendy,Xin Room3,Room4,Room5 更一般的匹配问题更一般的匹配问题 前面的宿舍分配问题中， 每个人只列出可接受

10、的房 间，更一般的情形是每个 人对于房间给出一个估价 前面的例子可以看成一个 打分为0和1的特例 估价 最优匹配最优匹配 匹配的效用 成功匹配的估价之和，称为匹配的效用 最优匹配 效用：12+6+5=23 最优匹配 效用最大的匹配 最优匹配对于个体而言不 一定最优，甚至是最差的 Yoram和Zoe的最优选择是 Room1 Yoram的最差选择是Room3 最优匹配最优匹配 如何找到最优匹配呢？ 穷举搜索 时间复杂度： ! 有更高效的方法吗? 需要宿舍管理员这样的全局角色吗？ 价格 价格导向的匹配价格导向的匹配 价格导向的匹配问题的形式化表示 价格 (Price) 卖方 (Seller) 买方

11、(Buyer) 估价 (Evaluation) = , , , , , , , , , 价格导向的匹配价格导向的匹配 估价不低于价格时，买方可以接受 如果, ，则买方可以接受卖方的价格，如果 成交，买方获得的效用是 对于买方，如果使其效用最大的卖方是 ，那么在二 部图中添加一条由指向的边 对于同一个买方，如果有多个卖方使其效用最大，则 添加多条边 最终得到一个“买方偏好图” , 价格导向的匹配价格导向的匹配 示例 5 2 0 价格 (Price) 卖方 (Seller) 买方 (Buyer) 12, 4, 2 8, 7, 6 7, 5, 2 = 估价 (Evaluation) 买方偏好图 市场

12、结清价格市场结清价格 市场结清(Market-Clearing) 每个卖方和买方都成交了 给定买方报价的情况下，如 果卖方的某种价格使得对应 的买方偏好图中存在完全匹 配，则称卖方的这组价格为 市场结清价格 卖方 (Seller) 买方 (Buyer) 买方偏好图 5 2 0 市场结清价格市场结清价格 未实现市场结清的价格 2 1 0 价格 (Price) 卖方 (Seller) 买方 (Buyer) 12, 4, 2 8, 7, 6 7, 5, 2 = 估价 (Evaluation) 买方偏好图 市场结清价格的性质市场结清价格的性质 最优性 市场结清价格所对应的买方偏好图中得到的完全 匹配是

13、最优匹配 存在性 对于任意买方估价，市场结清价格一定存在 市场结清价格的存在性市场结清价格的存在性 寻找市场结清价格的过程 步骤1：初始时，所有卖方的价格为0 步骤2：构建买方偏好图，检查其是否存在完全匹配 如果存在，当前价格是市场结清价格 如果不存在，从图中找到一个受限集（一定是买方）及其邻居 ，让 中的每个卖家的价格增加1 回到步骤2（当所有价格都为正时，可以通过让所有价格减去最低价格， 使最低价格为0，此操作不影响结果） 收敛性 买卖双方的总收益有限 ，总收益下降，但不会小于0 市场结清价格市场结清价格 寻找市场结清价格的过程示例 第一轮 第三轮 第二轮 第四轮 受限集S=x,y,z，N(S)=a 受限集S=x,z，N(S)=a 受限集S=x,y,z，N(S)=a,b 市场结清价格的存在性市场结清价格的存在性 小结 完全匹配是否存在可以通过寻找受限集来判断 价格能够引导市场优化配置 市场结清价格总是存在 市场结清价格使得买卖双方总效用最优 课间休息课间休息 课程内容课程内容 maxmin策略和minmax策略 匹配市场 中介市场中介市场 议价权 中介中介市场市场 中介市场的形式化表示 卖方 (Seller) 买方 (Buyer) 中介 (Trader) 报价 0 0 0 1 1 1 报价 中介市场中介市场 中介市场博弈规则