匹配市场清算价格求解

Table of Contents:

匹配市场
算法设计
- 一一对应算法（失败）
- 受限集+匈牙利算法
实验结果
实验心得

匹配市场#

匹配市场讨论一群卖方和一群同样数量买方的一一匹配问题，旨在找到社会最优的匹配方式。买家对每个卖家有自己的估值，形成 $n\times n$ 估值矩阵。通过调整卖家的价格至市场清仓价，买方可以得到与估值差价最大的商品，不存在冲突。

这里的“社会最优”指的是所有人对买到的商品的估值总和最大。清仓价格是不唯一的，算法设计部分中的失败案例中会提到案例。

算法设计#

一一对应算法（失败）#

书上介绍的匹配市场算法需要先找到受限买家集合 $S$ ，即 $S$ 中的买家偏好的商品集合 $S'$ 满足 $|S'|<|S|$ 。

开始实现了一个版本，试图找到价格更新后能够一一对应的结果，即试图让每个商品只有一个人偏好。代码如下：

import numpy as np

def read_file(file):
    with open(file, "r+", encoding="utf-8") as f:
        m = [line[:-1].split() for line in f.readlines()]
    m = [i for i in m if len(i) is not 0]   # 去除空行
    n = int(len(m[0]))
    buyer = np.array(m).reshape((n, n)).astype(int)
    return buyer, n


buyer, n = read_file('test14.txt')
price = np.zeros(n)
I = np.ones((n))

while True:
    profit = buyer - price
    prefer = (profit == np.max(profit, axis=1).reshape(n, 1))  # 买家偏好
    seller = np.sum(prefer, axis=0)  # 每个物品的偏好人数
    if (seller == I).all():
        break
    if not np.sum(seller > 1):
        break
    price += (seller > 1).astype(int)

但这种算法在课上的3*3的例子是有效的，能够得到与 $[5,2,0]$ 的解，其估值之和和 $[3,1,0]$ 的一样，都是社会最优解。

但遇到比如买家a和b的估值一致时，他们的偏好永远一致，不可能出现算法终止点，因此这个方法行不通，还是要回归受限集的算法。

受限集+匈牙利算法#

算法设计如下：

估值矩阵减去价格得到买家-卖家的效益矩阵profit，对每个买家，找到效益最大的卖家将两者连线。
对步骤1得到的二部图找最大匹配
- 如果匹配数=n，则找到了清仓价格和一一对应的匹配方式，算法结束。
- 如果匹配数<n，则找到卖家受限集，将它们价格+1，返回步骤1。

具体实现主要有三个部分：

主体循环结构
二部图最大匹配
受限集价格更新

主体部分#

得到prefer这个表示二部图关系的01矩阵，用于最大匹配算法计算匹配成功与否。

while True:
    profit = buyer - price
    prefer = (profit == np.max(profit, axis=1).reshape(n, 1))  # 买家偏好（连边）
    p = -np.ones(n)
    cnt, p = hungary(n)
    if cnt == n:
        print('清仓价格：', price)
        print('每个买家的商品选择：', p)
        total = 0
        for i in range(n):
            total += buyer[i][int(p[i])]
        print('社会最优：', total)
        break
    else:
        add_price(n, p)

二部图最大匹配：匈牙利算法#

给定二部图判断最大匹配数量，这里使用的是匈牙利算法的递归实现。

算法思路是依次为每个卖家匹配买家，如果匹配到的是已有配对的，则递归回溯已配对路径，看是否调整匹配以新增一对。

def match(i, n):
    global prefer
    global vis
    global p
    for j in range(n):
        if prefer[j][i] and vis[j] == 0:  # 买家尚未匹配
            vis[j] = 1
            if p[j] == -1 or match(int(p[j]), n):
                p[j] = i
                return True
    return False

def hungary(n):
    cnt = 0
    global vis
    global p
    for i in range(n):
        vis = np.zeros(n)
        if match(i, n):
            cnt += 1
    return cnt, p   # p[i]表示第i个买家对应的商品号

受限集价格更新#

给定一个已匹配的卖家，心仪它的买家中有未匹配上的，则该卖家是受限集的一员，需要涨价。

def add_price(n, p):
    global prefer
    for i in range(n):
        if i in p:  # 如果商品已经有匹配
            for j in range(n):  # 但是有喜欢它的人仍然没有匹配
                if prefer[j][i] == 1 and p[j] == -1:
                    price[i] += 1
                    break

实验结果#

test14.txt

清仓价格： [ 5.  5.  5.  0.  3.  0.  5.  5. 10. 10. 15.  3. 15. 10.]
每个买家的商品选择： [ 7. 10.  0.  3.  2. 13.  4.  6.  8.  5.  1. 12.  9. 11.]
社会最优： 500

·test24.txt

清仓价格： [ 0.  6. 31.  5.  1. 33. 22.  5.  7.  5.  5. 10. 23. 38.  8.  7.  5. 12.
  6. 12.  8. 22.  0.  0.]
每个买家的商品选择： [ 8.  9.  4. 15. 23. 20.  1. 14. 18. 17. 12. 21.  5. 13.  7.  3.  2.  0. 16.  6. 22. 10. 19. 11.]
社会最优： 911

test26.txt

清仓价格： [11.  6.  9. 10. 19.  1. 11.  6.  6.  6.  0.  3.  0.  6.  0.  0.  6. 11.
  0.  8.  8.  8.  3.  0.  3.  0.]
每个买家的商品选择： [21. 20.  8. 11. 24. 10.  3.  0.  1. 17.  4.  2. 13. 25. 22. 19. 23. 18. 16.  9.  6.  5.  7. 15. 14. 12.]
社会最优： 936

test31.txt

清仓价格： [ 0. 16.  2. 20. 50.  0. 43. 32. 31. 10.  6.  6.  6. 20.  7.  0.  6.  0.
 10. 53.  0.  6.  0.  0. 25.  1. 10.  1.  2.  2. 22.]
每个买家的商品选择： [28.  6.  4. 24.  9. 26. 23. 14. 19. 21.  0. 15.  8.  3.  7. 11. 27.  5. 10. 12. 17. 25. 20. 22.  2. 16.  1. 13. 30. 18. 29.]
社会最优： 1387

实验心得#

其实python里from scipy.optimize import linear_sum_assignment可以三行写完代码。感觉纯调包不太好就实现了一遍匈牙利算法，没想到把矩阵的ij写反这么一个小bug却de了好久，有点哭笑不得。
有一个问题没有想到答案，假设已知匹配结果，可以倒过来推出一组合理的清仓价格吗？
没有找到能直观解释全部清仓价格和商品选择的方法，不过找清仓价格的过程还是符合经济学概念的。比如受限集的思想本质上是「物以稀为贵」，根据供需关系市场进行了价格调整，从而价格上涨的商品需求就可能变少，更有利于分散分配。