首届国际理论计算机联合大会（International Joint Conference on Theoretical Computer Science，IJTCS）于2020年8月17日-21日在线上举行，主题为“理论计算机科学领域的最新进展与焦点问题”，由北京大学与中国工业与应用数学学会（CSIAM）、中国计算机学会（CCF）、国际计算机学会中国委员会（ACM China Council）联合主办，北京大学前沿计算研究中心承办。  

　　8月17日，上海财经大学的陆品燕教授带来了题为《最优机制设计：简洁性与鲁棒性》的主题报告，从分别从“简洁性”与“鲁棒性”两个角度对最优机制设计这一问题进行了讨论。报告由北京大学前沿计算研究中心讲席教授邓小铁主持。

　　陆老师首先介绍了什么是最优拍卖机制设计问题。问题背景为单个卖家想向多个买家卖物品。每个买家对每个物品的估值 v_i 服从一个已知的分布，分布之间独立。卖家目标为在这样的贝叶斯设定下最大化自己期望的总收入。

　　首先考虑最简单的单物品拍卖问题。以下是几种常见的拍卖机制：

       1）Simple Pricing Scheme: 卖家预先给物品设定价格 p。若 p 小于等于买家的估值，买家就会购买，否则不买。如何最大化收入就变成了一个简单的关于 p 的优化问题。

　　2）Sequential Posted-Pricing: 首先将买家们按某个规则排序，然后卖家依次向买家 i 出示价格 p_i。倘若在 i 号买家时第一次出现 v_i ≥ p_i，则发生交易。这一机制相较上一机制更为复杂，使用了价格歧视的手段，因此也不难构造出例子使得这一机制的期望收入高于上一机制。

　　3）Second Price Auction: 严格来说，前两种机制仅仅是定价方案，没有体现出拍卖的特点，而由 Vickery 提出的二价拍卖是极其经典的拍卖方式。每个买家一开始就将自己的报价封好交给卖家， 然后卖家将物品卖给出价最高的人，卖出价格为第二高的报价。该方案的最大优点是 truthful，即每个买家的最优策略就是诚实上报自己的估值，而且该方案也是公平的，没有价格歧视。然而，该方案中卖家的期望收入相对并不高。

　　4）Revenue Optimal Auction: 由 Myerson 提出了这一问题设定下的最优拍卖机制。该方案需要对每个买家计算一个虚拟报价，然后将物品卖给虚拟报价最高的人。具体公式请见下图。该机制下可能出现反直觉的情况，即物品并没有被卖给最高报价的人，因为有价格歧视。

　　5）Second Price Auction with Reserve Price：上述的 Revenue Optimal Auction 在假设所有买家的估值分布相同时，可以简化为 Second Price Auction with Reserve Price，即在原有的二价拍卖上设定了最低卖出价格。该机制在买家估值分布不同时，也经常被使用，因为其尽管不能保证最大化收入，但是没有价格歧视，保证了公平性。

　　现在我们可以开始讨论简单机制与最优机制的关系。一般来说，机制越简单越好，因为简单的机制往往具有公平（没有价格歧视），隐私泄露的风险更低等优点。然而，简单机制的收入相对于复杂机制可能更低。那么，如何量化这一 tradeoff 呢？陆老师及其合作者发表在 SODA 2019 与 STOC 2019 的相关论文中研究了这一问题。

　　四种拍卖机制如上图所示，其中 Anonymous Pricing 即 Simple Pricing Scheme，Myerson Auction 即 Revenue Optimal Auction，右上到左下的箭头体现了使用拍卖的优势，左上到右下的箭头体现了使用价格歧视的优势。具体来说：

       Second Price Auction with Reserve Price 相对于 Anonymous Pricing 的收入最高为 π²/6≈1.64倍，这个界是紧的。

       Sequential Posted-Pricing 相对于 Anonymous Pricing 的收入最高为2.62倍，这个界也是紧的。

       Myerson Auction 相对于 Anonymous Pricing 的收入最高同样为2.62倍，这个界同样是紧的。

       Myerson Auction 相对于 Second Price Auction with Reserve Price 的收入最高在 [2.15, 2.62] 倍之间。

      接下来，陆老师简单介绍了多物品拍卖下会出现的问题。首先，假设目前有 k 个一样的物品，每个卖家只需要买一个物品。那么，此时 Myerson Auction 是最优的。这一问题设定下同样能对比上述四种拍卖方案的收入，分析拍卖与价格歧视带来的收益，具体请参见下图。

　　如果有多个不同的物品，则即使只有一个买家，该问题也会变得极为复杂困难。例如，卖家可以选择每个物品分开卖，多个物品打包一块卖，甚至第二件物品半价等复杂的机制，因此，此设定下的最优机制是一个尚未被解决的难题。以上是报告第一部分有关机制“简洁性”的讨论。

　　报告的第二部分讨论了机制的“鲁棒性”。由于现实情境中估值分布很难能准确得到，因此我们希望机制对于估值分布的误差能较为鲁棒。

　　这里具体讨论的问题是分布间的相关性。注意到之前假设所有估值分布是独立的，若估值分布不独立，可能原先的拍卖机制效果会差很多。这里问题假设卖家仍然知道每个买家估值的边缘分布，希望最大化实际联合分布最差的情况下的收入。

　　该问题看似较为复杂，然而最终的答案却很简单。最优的机制就是将每个物品分开卖，一个一个定价。陆老师及其合作者研究了买家有预算的一般情况，技术上利用了线性规划对偶，最终结论仍然是将每个物品分开买是最优的。

　　最后，陆老师及其研究者还研究了单物品、多买家的情况下，对于分布相关性也要求鲁棒的机制设计问题。结论为 Sequential Posted-Pricing 是接近最优的。当然，该设定下仍有很多问题尚未解决。