网络结构与效应原理：第10章 匹配市场.ppt

******匹配市场

（买卖双方直接见面的市场）（第10章）一个测试从上面的n*n矩阵中，选出n个不同行不同列的元素，使其和最大96314637296417963825461837267641213845216632974？？？匹配市场的场景某一类商品（例如房子），一群卖方和一群同样数量的买方商品的质量不同，大家的认识也有差别买方对商品各有一个底价，都追求利益最大化市场按照供需关系自动调整价格，试图达成买卖双方的某种匹配我们关心最终能否大家都满意卖方：市场清仓，商品在底价之上都卖出去了买方：得到差价最大的商品匹配市场基本模型：二部图受限组－供不应求－物以稀为贵，加价！偏好卖家图价格调整后的偏好卖家图市场是高效的：总是可以通过调整价格，得到具有完美匹配的偏好卖家图匹配市场操作的一般过程（1）azcybx000卖方买方12，4，28，7，67，5，2估值价格匹配市场操作的一般过程（2）azcybx100卖方买方12，4，28，7，67，5，2估值价格匹配市场操作的一般过程（3）azcybx200卖方买方12，4，28，7，67，5，2估值价格匹配市场操作的一般过程（4）azcybx310卖方买方12，4，28，7，67，5，2估值价格特别地，实现了最大估值之和（23），即“社会最优”我们不由得会想起开始的测试问题给定一个N＊N矩阵（A），从中选择N个不同行不同列元素，aij（即i，j分别在｛1，2，…，N｝中遍历），使得和最大。似乎是可以通过“调整价格”实现的！前面的测试例价格＋1后偏好卖家图没变，稀缺商品再加价！9631463729641000096314637296412000买方受限组：｛2，4｝对应卖方｛1｝1看那个大些的例子初始价格为0，形成偏好卖家图，看其中是否存在一个买家受限组7963825461837267641213845216632974000000与受限买家关联的卖家调整价格形成新的偏好卖家图（看到边的调整），再看是否存在买家受限组7963825461837267641213845216632974110101与受限买家关联的卖家调整价格形成新的偏好卖家图（看到边的调整），再看是否存在买家受限组7963825461837267641213845216632974211202与受限买家关联的卖家调整价格形成新的偏好卖家图（看到边的调整），此时已经没有受限组?存在完美匹配7963825461837267641213845216632974311203匹配市场中的计算：启示我们看到市场经济中的一些基本概念：理性的人、价格、供需关系、物以稀为贵、均衡、社会最优，…通过一个简单的模型：匹配市场（偏好卖家图、根据受限组进行价格调整，…）得到了生动的表达。而一旦这么做了，也隐含着一个计算问题的高效解决（市场机制扮演了一个高效的问题求解器的角色！）社会计算、跨学科计算思维的一个具体示例市场清仓价格的形成：算法给定买方估值，卖方从初始价格（0,0,…,0）开始，按照轮次进行下述操作：构造偏好卖家图识别是否存在买