网络科学与策略机制 匹配市场PPT学习教案

1、会计学1网络科学与策略机制网络科学与策略机制 匹配市场匹配市场2第1页/共22页32 9 6 38 1 4 65 3 7 29 6 4 17 9 6 3 8 28 5 4 6 1 85 3 7 2 6 76 4 1 2 1 38 4 5 2 1 6 6 3 2 9 7 4第2页/共22页4第3页/共22页5第4页/共22页6n最大的商品第5页/共22页7偏好卖家图偏好卖家图价格调整后的偏好卖家图价格调整后的偏好卖家图猜想：市场总可以通过调整价格，得到具有完美匹配的偏好卖家图猜想：市场总可以通过调整价格，得到具有完美匹配的偏好卖家图？称（3,1,0）为“市场清仓价格”第6页/共22页8在这个过程

2、中，偏好卖家图不断被调整，最终结束在一个含有完美匹配的图上最后的结果：最后的结果：1.市场清仓所有物品都卖出去了，市场清仓所有物品都卖出去了，ax, bz, cy2.买家不仅每人都得到了最大差价的物品，并且买家不仅每人都得到了最大差价的物品，并且他们获得的价值总和达到最大（他们获得的价值总和达到最大（12+6+5=23），用经济学的术语，达到了，用经济学的术语，达到了“社会最优社会最优”第7页/共22页9nnnnnnaaaaaaaaa.212222111211给定一个NN矩阵（A），从中选择N个不同行不同列元素，aij（即i，j 分别在1，2，N中遍历），使得和最大。似乎是可以通过似乎是可以通

3、过“调整价格调整价格”实现的！实现的！第8页/共22页102 9 6 38 1 4 65 3 7 29 6 4 100002 9 6 38 1 4 65 3 7 29 6 4 12000买方受限组：买方受限组：2 2，4 4对应卖方对应卖方1 11第9页/共22页117 9 6 3 8 28 5 4 6 1 85 3 7 2 6 76 4 1 2 1 38 4 5 2 1 6 6 3 2 9 7 4000000第10页/共22页127 9 6 3 8 28 5 4 6 1 85 3 7 2 6 76 4 1 2 1 38 4 5 2 1 6 6 3 2 9 7 4110101第11页/共22页

4、137 9 6 3 8 28 5 4 6 1 85 3 7 2 6 76 4 1 2 1 38 4 5 2 1 6 6 3 2 9 7 4211202第12页/共22页147 9 6 3 8 28 5 4 6 1 85 3 7 2 6 76 4 1 2 1 38 4 5 2 1 6 6 3 2 9 7 4311203第13页/共22页15市场经济中的一些基本概念： 理性的人、价格、供需关系、物以稀为贵、均衡、社会最优，通过一个简单的模型： 匹配市场（偏好卖家图、根据受限组进行价格调整，）得到了生动的表达。而一旦这么做了，也隐含着一个计算问题的高效解决（市场机制扮演了一个高效的问题求解器的角色！

5、）社会计算、跨学科计算思维的一个具体示例第14页/共22页16n若因此使所有卖方价格都 0，则统一约减最低价至0。n开始下一轮。（注：统一约减不影响偏好卖家图关系）第15页/共22页17P0=maxj=1.k(vij-aj)i=1.k+ajj=1.k=maxj=1.k(vij)i=1.k 0我们如果能说明在上述算法过程中，（1）势能每一轮单调减，（2）但总不会小于0；则就说明了过程一定结束。“结束”“无受限集”。第16页/共22页18P=maxj=1.k(vij-aj)i=1.k+ajj=1.k第17页/共22页19第18页/共22页20P0=maxj=1.k(vij-aj)i=1.k+ajj=1.k=m