第10章网络科学与策略机制 匹配市场_55480802

《第10章网络科学与策略机制 匹配市场_55480802》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、10匹配市场MatchingMarkets1主要内容二部图与完美匹配估值与最优分配价格与市场清仓性质构造一组清仓价格与单品拍卖的关系2一个测试3从上面的n*n矩阵中，选出n个不同行不同列的元素，使其和最大96314637296417963825461837267641213845216632974回顾二部图的概念和一个性质4考虑两边相等的二部图匹配：图中的一组边，其中所涉及节点没有重复完美匹配：所有的节点都被覆盖的匹配受限组：图中一边的节点子集S，大于其邻居节点子集N(S)匹配定理：存在完美匹配，当且仅当不存在受限组

2、（如何确定是否存在受限组）判断一个二部图中是否存在完美匹配5匹配定理：存在完美匹配，当且仅当不存在受限组。（教材第10章深度学习材料部分提供了一个构造性证明）匹配市场的场景6某一类商品（例如房子），一群卖方和一群同样数量的买方商品的质量不同，大家的认识也有差别买方对商品各有一个底价，各自追求利益最大化市场按照供需关系自动调整价格，成交价格不会超过买方的底价我们关心最终能否大家都满意卖方：市场清仓；买方：得到差价最大的商品匹配市场基本模型：二部图7受限组－“供不应求”－“物以稀为贵”偏好卖家图价格调整后的偏好卖家图猜想

3、：市场总可以通过调整价格，得到具有完美匹配的偏好卖家图？称（3,1,0）为“市场清仓价格”8类拍卖过程促成市场清仓在这个过程中，偏好卖家图不断被调整，最终结束在一个含有完美匹配的图上最后的结果：市场清仓－所有物品都卖出去了，ax,bz,cy买家不仅每人都得到了最大差价的物品，并且他们获得的价值总和达到最大（12+6+5=23），用经济学的术语，达到了“社会最优”我们不由得会想起开始的测试问题9给定一个N＊N矩阵（A），从中选择N个不同行不同列元素，aij（即i，j分别在｛1，2，…，N｝中遍历），使得和最大。似

4、乎是可以通过“调整价格”实现的！前面的测试例10价格＋1后偏好卖家图没变，卖方再加价！9631463729641000096314637296412000买方受限组：｛2，4｝对应卖方｛1｝1看那个大些的例子11初始价格为0，形成偏好卖家图，看其中是否存在一个买家受限组7963825461837267641213845216632974000000与受限买家关联的卖家调整价格12形成新的偏好卖家图（看到边的调整），再看是否存在买家受限组7963825461837267641213845216632974110101与

5、受限买家关联的卖家调整价格13形成新的偏好卖家图（看到边的调整），再看是否存在买家受限组7963825461837267641213845216632974211202与受限买家关联的卖家调整价格14形成新的偏好卖家图（看到边的调整），此时已经没有受限组存在完美匹配7963825461837267641213845216632974311203匹配市场中的计算：启示15我们看到市场经济中的一些基本概念：理性的人、价格、供需关系、物以稀为贵、均衡、社会最优，…通过一个简单的模型：匹配市场（偏好卖家图、根据受限组进行价

6、格调整，…）得到了生动的表达。而一旦这么做了，也隐含着一个计算问题的高效解决（市场机制扮演了一个高效的问题求解器的角色！）社会计算、跨学科计算思维的一个具体示例市场清仓价格的形成：算法16给定买方估值，卖方从初始价格（0,0,…,0）开始，按照轮次进行下述操作：构造偏好卖家图识别是否存在买方受限组（S），若没有，则偏好卖家图中存在完美匹配，结束。将受限组对应的卖方集合N(S)中的价格都＋1（也就是根据需求调整价格，“物以稀为贵”）若因此使所有卖方价格都>0，则统一约减最低价至0。开始下一轮。（注：统一约减不影响偏好卖

7、家图关系）这个过程为什么一定能结束？17定义市场的势能：所有参与者潜在回报之和卖方：当前价格，a1,a2,…,ak；买方(i)：“估值减去对应价格”的最大值，max(vij-aj)势能初值（a=0）：我们如果能说明在上述算法过程中，（1）势能每一轮单调减，（2）但总不会小于0；则就说明了过程一定结束。“结束”＝“无受限集”。这个过程为什么一定结束？18设买卖双方各有K人，观察势能在每一轮的变化，可见只有价格a的变化会引起势能的变化。在操作过程中有两处会引起a的变化（1）必定发生：因受限集S造成的N(S)中元素价格＋1

8、（2）不一定发生：统一约减a至最小价格为0可见卖方势能之和，由于（1）增加N(S)，由于（2）减少K但总保持是≥0买方势能之和，由于（1）减少S>N(S)，由于（2）增加K结果也总是≥0（因为v≥0，且算法过程保证了总存在一个a=0）于是市场势能在每轮都单调递减，且下界为0。清仓价格的不唯一性19但都是“社会最优”（12＋6＋5＝23）上述有没