拍卖算法

拍卖算法是一种解决目标分配问题的算法。额这个算法我看了网上好多博客的讲解，都不是很理解，最后直接debug了一个代码，总算弄清楚了。果然源码面前，了无秘密。

问题描述

• 情景描述：在一个拍卖场中，存在N个投标人，M件商品，需要将M件商品分配给投标人们。
• 单分配问题：每个投标人对所有商品都有意愿争取，但是每人最多只能中标一件商品。（更复杂的暂且不谈）
• 完全分配问题：是单分配问题，并且\(N=M\)。
• 目标：拍卖行该如何分配商品给投标人，才能使得投标人综合获益最大？

一个最经典的完全分配问题如下（表格中数据表示对应商品在对应投标人心中的价值）：

商品价值	商品1	商品2	商品3	商品4	商品5	商品6
投标人1	11	18	11	18	33	4
投标人2	4	34	33	32	26	23
投标人3	3	0	27	24	14	9
投标人4	25	15	25	23	7	26
投标人5	30	18	34	20	17	29
投标人6	5	35	34	4	17	28

## 问题分析与数学建模

• N：投标人数量，此处\(N=6\)；
• M：商品数量，此处\(M=6\)；
• \(I=\{ i_1,...,i_N\}\)：投标人集合；
• \(J=\{j_1,...,j_M \}\)：商品集合；
• A(n)：第n个投标人感兴趣的集合，此处\(A(n)=J\)；
• \(S=\{\{i_{s1},j_{s1}\},\{i_{s2},j_{s2}\},...,\{i_{sT},j_{sT}\} \}\)：分配情况集合，大小为T；
• \(W=\{w_{ij} \| i \in I, j \in J \}\)：表示投标人i得到商品j可以得到的获益；
• \(P=\{p_j \mid j \in J \}\)：表示商品j当前的报价；
• \(F=\{f_{ij} \mid i\in I, j\in J \}\)：投标人i是否拍得商品j的集合，是则\(f_{ij}=1\)，否则\(f_{ij}=0\)。

某种分配方案下，投标人的总收益为： \[ \sum_{k=s1}^{sT}g_{i_kj_k} = \sum_{k=s1}^{sT} (w_{i_k j_k}) \] 因为每个投标人最多只能拍得一件商品，因此有(在此例中是一一对应应该等于1)： \[ \sum_{j=1}^M f_{ij} \le 1, \forall i \in I \] 每件商品都被拍卖，则有(分配集合与商品集合是一一对应的) \[ T=M \]

所以最终优化的模型应该为 \[ max \sum_{k=s1}^{sT}g_{i_kj_k} \\ st. \sum_{j=1}^M f_{ij} \le 1, \forall i \in I \\ T=M \]

拍卖算法流程实现

• 首先初始化参数：所有商品的初始报价\(P=\{p_j \mid j \in J \}\)均为0，松弛互补参数\(\epsilon =0.01\)，待报价投标人集合\(B=I\);
• 遍历B中每一个投标人i；
  • 该投标人对每件商品的收益集合为\(\pi_i = \{ w_{ij} -p_j \}_{j\in J}\)，计算该投标人的最大收益\({\pi}_{max}\)和次大收益\({\pi}_{max2}\)：
  • 更新该投标人i的最大收益商品的报价为\(p_j \mathrel{+}= \pi_{max} - \pi_{max2} + \epsilon\)；
  • 如果该投标人i的最大收益商品之前的报价不为0，则将之前对该商品报价的投标人放入B中；
  • 将该投标人i从B中拿出；
• 直到B中不再有没有拍得商品的投标人，算法截止；

上述算法需要满足\(N \le M\)

问题总结

• 首先，投标人根据不同商品目前的的竞标价格，可以知道自身竞标哪个商品可以获得最大收益，因此此处建立投标人的最大获益方程： \[ \pi_i = max_{k \in A(i)}\{ a_{ik} - p_k \} \]

• 次大获益方程为： \[ \pi_{i1} = max_{k\in A(i),k \ne j}\{a_{ik} - p_k\} \]

• 拍卖算法有初始化的参数很重要，一个是初始价格（起拍价），一个是松弛互补参数\(\epsilon\)；

  • 对于完全分配问题，当取\(\epsilon < 1/N\)时，该算法可以得到最优分配解。
    • 如果一个商品已经分配了，它会一直保持分配状态，只是由于竞标价的迭代可能会不断的分给不同的投标人；
    • 如果一个商品未分配，那它会一直保持为最初时的价格，而完全分配问题中，未分配的商品总会对应着一个未中标的投标人，所以随着其他商品竞标价的提升，未中标的投标人总会青睐尚未分配的商品的；

参考文献

• [1] https://blog.csdn.net/weixin_47546390/article/details/108470396