【IJTCS 2020】陆品燕教授谈最优机制设计:简洁性与鲁棒性

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

 

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

  

 

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

 

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

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

 

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

 

  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 的收入最高为 π2/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 是接近最优的。当然,该设定下仍有很多问题尚未解决。