网络群体与市场课件第10章

一个测试,从上面的n*n矩阵中，选出n个不同行不同列的元素，使其和最大,9 6 3 1 4 6 3 7 2 9 6 4 1,7 9 6 3 8 2 5 4 6 1 8 3 7 2 6 7 6 4 1 2 1 3 8 4 5 2 1 6 6 3 2 9 7 4,回顾二部图的概念和一个性质,考虑两边相等的二部图 匹配：图中的一组边，其中所涉及节点没有重复 完美匹配：所有的节点都被覆盖的匹配 受限组：图中一边的节点子集S，大于其邻居节点子集N(S) 匹配定理：存在完美匹配，当且仅当不存在受限组 （如何确定是否存在受限组）,判断一个二部图中是否存在完美匹配,匹配定理：存在完美匹配，当且仅当不存在受限组。（教材第10章深度学习材料部分提供了一个构造性证明）,匹配市场的场景,某一类商品（例如房子），一群卖方和一群同样数量的买方 商品的质量不同，大家的认识也有差别 买方对商品各有一个底价，各自追求利益最大化 市场按照供需关系自动调整价格，成交价格不会超过买方的底价 我们关心最终能否大家都满意 卖方：市场清仓；买方：得到差价最大的商品,匹配市场基本模型：二部图,受限组“供不应求”“物以稀为贵”,偏好卖家图,价格调整后的偏好卖家图,猜想：市场总可以通过调整价格，得到具有完美匹配的偏好卖家图？,称（3,1,0）为“市场清仓价格”,类拍卖过程促成市场清仓,在这个过程中，偏好卖家图不断被调整，最终结束在一个含有完美匹配的图上,最后的结果： 市场清仓所有物品都卖出去了，ax, bz, cy 买家不仅每人都得到了最大差价的物品，并且他们获得的价值总和达到最大（12+6+5=23），用经济学的术语，达到了“社会最优”,我们不由得会想起开始的测试问题,给定一个NN矩阵（A），从中选择N个不同行不同列元素，aij（即i，j 分别在1，2，N中遍历），使得和最大。,似乎是可以通过“调整价格”实现的！,前面的测试例,价格1后偏好卖家图没变，卖方再加价！,9 6 3 1 4 6 3 7 2 9 6 4 1,0 0 0 0,9 6 3 1 4 6 3 7 2 9 6 4 1,2 0 0 0,买方受限组：2，4 对应卖方1,1,看那个大些的例子,初始价格为0，形成偏好卖家图，看其中是否存在一个买家受限组,7 9 6 3 8 2 5 4 6 1 8 3 7 2 6 7 6 4 1 2 1 3 8 4 5 2 1 6 6 3 2 9 7 4,0 0 0 0 0 0,与受限买家关联的卖家调整价格,形成新的偏好卖家图（看到边的调整），再看是否存在买家受限组,7 9 6 3 8 2 5 4 6 1 8 3 7 2 6 7 6 4 1 2 1 3 8 4 5 2 1 6 6 3 2 9 7 4,1 1 0 1 0 1,与受限买家关联的卖家调整价格,形成新的偏好卖家图（看到边的调整），再看是否存在买家受限组,7 9 6 3 8 2 5 4 6 1 8 3 7 2 6 7 6 4 1 2 1 3 8 4 5 2 1 6 6 3 2 9 7 4,2 1 1 2 0 2,与受限买家关联的卖家调整价格,形成新的偏好卖家图（看到边的调整），此时已经没有受限组存在完美匹配,7 9 6 3 8 2 5 4 6 1 8 3 7 2 6 7 6 4 1 2 1 3 8 4 5 2 1 6 6 3 2 9 7 4,3 1 1 2 0 3,匹配市场中的计算：启示,我们看到,市场经济中的一些基本概念： 理性的人、价格、供需关系、物以稀为贵、均衡、社会最优， 通过一个简单的模型： 匹配市场（偏好卖家图、根据受限组进行价格调整，） 得到了生动的表达。 而一旦这么做了，也隐含着一个计算问题的高效解决（市场机制扮演了一个高效的问题求解器的角色！）,社会计算、跨学科计算思维的一个具体示例,市场清仓价格的形成：算法,给定买方估值，卖方从初始价格（0,0,0）开始，按照轮次进行下述操作： 构造偏好卖家图 识别是否存在买方受限组（S），若没有，则偏好卖家图中存在完美匹配，结束。 将受限组对应的卖方集合N(S)中的价格都1 （也就是根据需求调整价格，“物以稀为贵”） 若因此使所有卖方价格都 0，则统一约减最低价至0。 开始下一轮。（注：统一约减不影响偏好卖家图关系）,这个过程为什么一定能结束？,定义市场的势能：所有参与者潜在回报之和 卖方：当前价格，a1, a2, , ak； 买方(i)：“估值减去对应价格”的最大值，max (vij-aj) 势能初值（a=0）：,我们如果能说明在上述算法过程中，（1）势能每一轮单调减，（2）但总不会小于0；则就说明了过程一定结束。“结束”“无受限集”。,这个过程为什么一定结束？（续）,设买卖双方各有K人，观察势能在每一轮的变化，可见只有价格 a 的变化会引起势能的变化。 在操作过程中有两处会引起 a 的变化 （1）必定发生：因受限集 S 造成的 N(S) 中元素价格1 （2）不一定发生：统一约减 a 至最小价格为0 可见 卖方势能之和，由于（1）增加N(S)，由于（2）减少K 但总保持是0 买方势能之和，由于（1）减少SN(S) ，由于（2）增加K 结果也总是0（因为v0，且算法过程保证了总存在一个a=0） 于是市场势能在每轮都单调递减，且下界为0。,清仓价格的不唯一性,但都是“社会最优”（126523）,上述有没有矛盾？,我们说，达到“市场清仓”就意味着“社会最优” 社会最优即社会福利最大化，社会福利定义为所有参与人回报之和（包括买卖双方），也等价于无冲突的买方估值之和 在论证中又说势能单调减 势能定义为所有参与人潜在回报之和,潜在回报不等于可达回报,小结,市场经济概念下，价格取决于供需关系，供需关系则依赖于买方对价值的认识，在供需关系（价格）调整的过程中，市场能够做到资源的优化配置 也就是说，我们可以将市场活动看成是一种自然行为（无形之手的作用），其过程就像是在做一种优化计算 上述认识可以通过严格的模型来表达（学习重点） 同时也需要意识到，模型是现实的抽象，但不等于现实本身，现实市场情形当然要复杂很多。好的模型能抓住主要因素，说明关键概念。,使用时，直接删除本页！,精品课件，你值得拥有！,精品课件，你值得拥有！,使用时，直接删除本页！,精品课件，你值得拥有！,精品课件，你值得拥有！,使用时，直接删除本页！,精品课件，你值得拥有！,精品课件，你值得拥有！,作业：练习10.5,设有三个卖家a，b和c，三个买