图灵奖得主姚期智最新论文出炉！中秋人家看月亮，AI人看论文

AI科技大本营

发布于 2018-04-28 10:11:41

9610

发布于 2018-04-28 10:11:41

文章被收录于专栏：AI科技大本营的专栏AI科技大本营的专栏

参与 | 周翔、reason_W

今年2月，世界著名计算机科学家姚期智放弃外国国籍成为中国公民，正式转为中国科学院院士，加入中国科学院信息技术科学部。

为什么这一消息引发了如此高的关注度？首先得从姚期智院士的个人履历讲起：

1946年12月生于上海；
1967年获得中国台湾大学物理学士学位；
1972年至1975年，先后获得美国哈佛大学物理博士学位和伊利诺依大学计算机科学博士学位；
1975年至2004年先后在美国麻省理工学院、斯坦福大学、加利福尼亚大学伯克利分校、普林斯顿大学等著名学府担任教授；
1998年被选为美国科学院院士；
2000年被选为美国科学与艺术学院院士，并成为当年的“图灵奖”得主；
2004年，57岁的姚期智辞去了普林斯顿大学终身教职，卖掉了在美国的房子，回归中国大陆，加入清华大学。
2005年，大名鼎鼎的“姚班”在清华大学成立，著名的“楼教主”——楼天城，CVPR2017最佳论文作者——刘壮，此外，旷视科技三位联合创始人印奇、唐文斌、杨沐都是“姚班”的本科同学。

如果你了解姚期智院士在密码学基础，计算复杂性及量子计算方面的杰出贡献，那么你也会知道“图灵奖”是实至名归。

这几年，姚期智院士进入了一个新的领域——计算经济学，研究的是一种博弈拍卖理论。而且和很多人不一样，姚期智院士喜欢“单打独斗”。

近日，AI科技大本营就在arXiv上发现了姚期智院士的最新论文——“On RevenueMonotonicity in Combinatorial Auctions”。该论文对拍卖中买家对商品的估值与拍卖收益的相关性进行了研究。

清华大学的唐平中老师表示，通常意义上认为，卖家通过打广告，有助于提升买家对商品的认知和估值，从而提升销售的收入。Hart and Nisan在EC-13的论文中提出，存在某类场景，使得当买家的估值提升后，卖家的收益下降。也就是，所谓的revenue monotonicity性质并不成立。姚期智院士在最新的论文中证明，approximate revenue monotonicity成立，即买家估值提升后，卖家的的收益不会低于之前收益的常数倍。该结果对任意拍卖场景均成立。

AI科技大本营对姚院士最新论文的部分内容进行了翻译，不过其中类似下图的“Proof. Obvious”的地方就要靠读者自行脑补了。

摘要

随着近期多物品拍卖的近似最优机制设计研究取得的实质性进展，一些有趣的结构性问题也得以被提出和研究。特别是，卖方是否总是可以从竞买人出价高于其他市场的市场上获得更多的收益。在本文中，我们证明了一般集合中这样的收益单调性结果。更准确地说，考虑的情形是贝叶斯集中，由估值函数

和

独立物品类型分布的集合

指定的，

个物品和

个竞买人的收益最大化组合拍卖。令

表示任意激励兼容机制在集合

下可实现的最大收益。直觉上，如果分布

随机支配集合

，则可以预期

。但令人惊讶的是，Hart和Reny的研究表明，即使对于

是加法这样的简单情况，结果也并不总是如此。这里就出现一个本质的问题：这些偏差是否包含在边界内？单调性直觉在多大程度上仍然有效？我们给出了分次可加（Fractionally subadditive 或XOS）这一类估值函数

的近似单调性定理，表明如果分布

随机支配估值函数

下的集合

（其中

是普通常数），则有

。之前，只知道

情况下的近似单调性：Babaioff et al. 为加法估值函数的情况做了证明，Rubinstein和Weinberg为所有次可加估值函数做了证明。

简介

随着近期多物品拍卖的近似最优机制设计研究取得的实质性进展，一些有趣的结构性问题也得以被提出和研究。特别是，卖方是否总是可以从竞买人出价高于其他市场的市场上获得更多的收益。在本文中，我们利用相关机制设计文献中最近的进展，证明了一般集合中这样的收益单调性结果。

在最简单的Myerson单物品拍卖情形中，

表示独立估值分布

的最优收益。当

随机支配集合

（即，对每个竞买人

，

随机支配

）时，

。直觉上，如果每个竞买人都准备为该拍品支付更多的价钱，卖方应该能够获得更多的收入。这样的结果看起来很合理，Rubinstein和Weinberg 的研究也表明，作为Myerson的表征的结果，单物品拍卖也确实是这样的结果。

但当拍卖中有

个物品时，收益单调性问题就变得微妙起来。Hart 和Reny [10]的研究表明，即使只有一个竞买人

和两个物品

，收益单调性也并不适用。他们给出了分布

随机支配时

，

的例子。因此，当存在

个物品时，目标只能是approximate revenue monotonicity，例如，对一些绝对正常数

，有

。

对于存在

个竞买人和任意数量的物品的情况，已经证明了如下单调性结果：如果分布

随机支配集合

，那么当估值函数为加法时，

（Babaioff 等），并且对于任何次可加估值的组合拍卖（Rubinstein 和Weinberg），有

。这些结果作为它们分布收益单调的情况下各自近似最优机制的直接推论获得的。最近，姚、蔡、Devanur和Weinberg对加法估值函数的研究以及在蔡和赵（还有Feldman、Gravin 和 Lucier 在福利最大化方面的研究）对XOS估值函数的研究都发现，对于任何n，m，都存在近似最优的机制。然而，这些机制在分布中并不是明显收入单调的; 因此，对于

，没有一般的单调性结果。

我们的主要成果是解决了XOS估值函数类上的这个问题。对于任意m，和XOS估值函数

的组合拍卖，我们证明对于c =

，如果分布

随机支配

，在估值函数为时

，有

。为了证明我们的主要成果，我们还证明了两个辅助定理，这些成果本身也是有用的。首先，对于任何单参数环境中的拍卖,，我们证明如果分布随机支配，则最优收益满足

。这意味着收益单调性不仅仅适用于Myerson单物品最优拍卖，也适用于分配向量被限制为任意允许的模式集合的一般的一维拍卖问题。其次，作为上述单参数单调性的结果，我们推测在单需求多项目拍卖中

。

这项工作的贡献：

1）我们已经对收益单调性问题给出了非常一般性的答案，适用于所有XOS次可加估值函数，而在此之前学界甚至对加法估值也不甚了解。

2）我们在证明技术方面的关键创新是概念性的，不需要复杂的计算或分析。证明XOS单调性的主要困难在于[3]中给出的近似最优机制不是单调的。为了克服这个障碍，我们首先将我们的拍卖嵌入一个更放松的环境（即数字商品）。在这个更大的空间中，我们可以通过两个嵌入式分布之间的连接路径（在新空间中）来建立收益单调性。

3）在更哲学的层面上，我们同意（Hart和Nisan 所表达的）这样的观点，即设计机制的目标不仅是产生一种有效的算法，而且还能揭示某种数学结构，使得诸如收益单调性这些有趣的问题得到解答。我们目前的工作是这种方法的成果的另一个验证。

主要结果

我们给出了独立集中三个标准拍卖模式的结果，其中所有