Video在线视频

各位同学 大家好

欢迎来到网络 群体与市场的

在.线课堂

我是这门课的主讲老师——石兵

在这一讲我们将会介绍一种

典型的市场 叫做匹配市场

匹配市场是什么呢

它是买卖双方可以直接见面的市场

我们可以看这样一个典型的场景

有一类商品

一群卖方以及一群买方

这个商品的质量是不同的

因此大家的认识也有差别

所以买方对商品是有一个底价的

这个买方他会追求利益的最大化

也就是说买方的底价减去他的

支付价格就是他的收益

他希望最大化他的收益

市场可以按照供需关系

自动调整卖方的价格

它试图达成买卖双方的一种匹配

我们关心什么问题呢

最终卖方是不是可以把

所有的商品都卖掉

达到市场清仓的目的

买方是不是可以得到

差价最大的商品

也就是说他可以得到

底价减去支付价格（的结果）

最大的那个商品

我们可以看这样一个

简化的匹配市场的图

有这样三个买方x y z

有三个卖方a b c

买方对这个商品有一个底价

比如说买方x

他的底价就是12,4,2

表示什么意思呢

他觉得a这个商品值12元

b值4元 c值2元

同样的y和z也有他们的

这样一个估值

我们先来看

其实对于x y z

他们都希望得到哪个商品

很显然他们都希望得到a

这是由于这个时候

他们的收益可以达到最大

这个时候买方x的收益是12

y的收益是8 z的收益是7

但是很可惜 商品a只有一个

这个时候就存在这样一个

偏好卖家图

我们可以看到这是一个图

显然它是一个二部图

在这样的图里面我们可以看到

三个买方想购买同一个商品

也就是说供应小于需求

在这种情况下

卖方的价格就要提高

我们假设商品a的价格会加1

这个时候会发生什么情况呢

这时候x会发现他购买商品a

的回报是12－1=11

但是买b和c的回报分别是

4-0=4和2-0=2

所以他还是希望买a

这个时候y发现他买

a和b的回报都是7

所以他会考虑这两个

都是可以接受的

z发现他还是希望买a

这时候我们发现还是存在这样

一个受限组x y z偏好a

买方a商品的价格再次提高

这个时候会出现什么情况呢

我们看x还是喜欢a

因为这个时候它的回报是10

其它两个商品的回报

分别是4和2

z会发现买a和b的回报都是5

y会发现他买b的回报会比较高

可以达到7

但是买其它的回报分别都是6

这个时候还是会存在

这样一个受限的情况

也就是说x y z

他们三个人要来买a b

那价格就再次提高

这个时候a的价格加1

b的价格也会加1

我们看这个时候卖方a

b的价格分别变成3和1

这个时候会出现什么情况呢

我们可以看到 x会希望买a

因为这个时候它的回报还是最大的

它的回报达到12－3=9

而其它买b和c的回报

分别是4－1=3和2

y会希望买什么呢 买b和c

因为这个时候它的回报都是6

而对z来说他会希望买b和a

因为这个时候它的回报都是4

这个时候我们可以看到

在这样一个他们的

偏好卖家图 下

这样一个二部图下

我们可以找到一个完美的匹配

每个人都可以找到

自己期望获得的商品

然后最大化他的收益

x买a y买c z买b

这个时候它们对应得估值之和

是什么呢 x买a 他的估值是12

y买c估值是6

z买b 他的估值是5

而且我们还可以发现

这个12 6 5其实是这样一个

3×3的矩阵里面不同行不同列

的元素之和最大的一个情况

也就是说我们实现了最大估值之和

也就是 社会最优

其实刚才这样一个过程就是一个

市场清仓价格的算法

我们现在把这个算法再重头到尾

理一遍 首先我们给定买方的估值

卖方从初始价格

（0,0,...,0）开始

进行下面这样一个过程

首先我们构造偏好卖家图

（它是一个二部图）

在这个偏好卖家图里面

我们识别是不是存在买方受限组

买方受限组的意思就是

有多个买方想买少于这个

买方数量的商品

如果不存在买方受限组

我们就可以找到一个完美的匹配

大家都可以得到自己期望的商品

但是如果有买方受限组

这个时候就说明供需不平衡

那么受限组对应的卖方集合

的价格将会加1

也就是说根据需求来调整价格

这也就是我们通常所说的

物以稀为贵

另外我们考虑一下

如果说因为这个价格的调整

使得卖方价格都大于0

我们可以统一约减一下

那么现在的问题是

这样的一个过程会结束吗

也就是说是不是肯定会

找到这样一个状态

它会不会来回震荡呢

得不到这样一个完美匹配的

偏好卖家图

我们可以证明说这样一个过程

肯定会结束

这个证明的思路其实跟我们之前

介绍交通网里面证明这样一个

最终肯定会找到一个

纳什均衡的司机路线一样

我们找一个势能

这个势能随着每一轮都会减少

但是这个势能有一个最低值

所以当到某个程度

没法再减少的时候

就达到了这样一个均衡的状态

那么这里面这个势能怎么定义呢

我们定义这个势能就是

所有参与者的回报之和

所以卖方的势能就是他的价格

也就是a1 a2...ak;

买方的势能就是他的回报

也就是估值减去价格的最大值

刚开始的时候价格是0

因此势能的初值就是它（估值）

我们接下来就要证明在这样一个

不停的迭代下去的过程中

势能会在单调递减

但是它有一个下限的 不会小于0

如果我们可以证明到这一点

那这个过程肯定就会结束

结束的时候就说明

我们找不到受限集

也就是说这个偏好卖家图里面

我们可以找到一个完美的匹配

我们可以看一下

这个势能怎么会变化呢

势能的变化肯定是

由于价格a的变化引起的

也就是说当a变化的时候

这个势能才会变

在我们这样一个算法的过程中

只有两个地方可能会引起a的变化

第一个是在每一轮肯定会发生的

在这一轮我们会发现受限集

由于受限集我们会调整卖方的价格

所以价格加1

也就是说某些a的价格会加1

在这种情况下势能就会变化

还有一种情况是不一定会发生

也就是我们所说的统一约减

因此我们可以看到在这种情况下

由于加1这个操作肯定会增加势能

增加的量是对应的卖方集合的数量

等于N(S)

买方势能会减少S

而且我们知道由于是买方受限

也就是说想买的人多于

卖的人的数量

所以S>N(S)

这就说明这样的势能在单调递减

但我们也要看一下2

这种不一定会发生的情况

因为它是统一约减

所以要么就是卖方的势能减少K

然后与之对应的买方的势能

会增加K

所以这个对势能

不会产生影响

但是通过这样一个分析

我们可以发现 总的来说

在每一轮势能总是会单调递减的

但是势能肯定要大于等于0的

这就说明这个算法过程肯定会终止

在终止的时候我们就找到了一种

完美的匹配

也就是说市场达到了清仓的目的

其实刚才这样一个市场清仓价格

算法有一些在数学上的运用

比如说我们给定一个

N×N的矩阵(A)

我们采用这个算法可以找到

不同行不同列的元素 使得和最大

我们可以通过

调整价格的方法来实现

就是刚才这样一个

市场清仓价格算法

我们以这样一个例子为例

这个例子很简单

是一个4×4的矩阵

这个4×4的矩阵大家会觉得

不需要用这个算法

用肉眼都能看得出来

确实可以看的出来

但是我们可以体会一下

用这个算法怎么做

我们看同样的构造

有这样4个买家 4个卖家

4个卖家刚开始的价格是0

这个时候会存在受限组

我们会发现买家2和4

他们都希望买商品1

这个时候这个卖家价格加1

这个时候我们会形成一个

新的偏好卖家图

这个时候我们会发现

买家1喜欢卖家2

买家2喜欢卖家4

买家3喜欢卖家3

买家4喜欢卖家1

这个时候我们可以找到一个

完美的匹配 不再有受限组

而与之对应的是9 6 7 9

通过这个方法我们就可以找到

不同行不同列元素之和最大

我们其实还可以考虑

比较复杂的例子

比如说这样一个6×6的矩阵

或者说100×100的矩阵

这个时候我们凭肉眼就没法

直接看的出来

这个算法就有用武之地

这样一个例子大家可以

课后练习一下

在这一讲我们介绍了

匹配市场以及其中最重要的

市场清仓价格算法

我们要注意其实我们可以把

市场的活动看做是一种自然的行为

通过这种市场自发的调节供需

我们可以达到买方估值之和最大

其实这一过程就像我们在做一个

优化计算一样

这一讲就进行到这里 谢谢大家