圖靈獎得主姚期智最新論文出爐!中秋人家看月亮,AI人看論文

NO IMAGE

640?wx_fmt=jpeg&wxfrom=5&wx_lazy=1

參與 | 周翔、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”的地方就要靠讀者自行腦補了

0?wx_fmt=png

摘要

隨著近期多物品拍賣的近似最優機制設計研究取得的實質性進展,一些有趣的結構性問題也得以被提出和研究。特別是,賣方是否總是可以從競買人出價高於其他市場的市場上獲得更多的收益。在本文中,我們證明了一般集合中這樣的收益單調性結果。更準確地說,考慮的情形是貝葉斯集中,由估值函式0?wx_fmt=png0?wx_fmt=gif獨立物品型別分佈的集合0?wx_fmt=gif指定的,0?wx_fmt=gif個物品和0?wx_fmt=gif個競買人的收益最大化組合拍賣。令0?wx_fmt=gif

表示任意激勵相容機制在集合0?wx_fmt=gif下可實現的最大收益。直覺上,如果分佈0?wx_fmt=gif隨機支配集合0?wx_fmt=gif,則可以預期0?wx_fmt=gif。但令人驚訝的是,Hart和Reny的研究表明,即使對於0?wx_fmt=gif是加法這樣的簡單情況,結果也並不總是如此。這裡就出現一個本質的問題:這些偏差是否包含在邊界內?單調性直覺在多大程度上仍然有效?我們給出了分次可加(Fractionally subadditive 或XOS)這一類估值函式0?wx_fmt=gif的近似單調性定理,表明如果分佈0?wx_fmt=gif隨機支配估值函式0?wx_fmt=gif下的集合0?wx_fmt=gif(其中0?wx_fmt=gif是普通常數),則有0?wx_fmt=gif。之前,只知道0?wx_fmt=gif情況下的近似單調性:Babaioff et al. 為加法估值函式的情況做了證明,Rubinstein和Weinberg為所有次可加估值函式做了證明。



簡介

隨著近期多物品拍賣的近似最優機制設計研究取得的實質性進展,一些有趣的結構性問題也得以被提出和研究。特別是,賣方是否總是可以從競買人出價高於其他市場的市場上獲得更多的收益。在本文中,我們利用相關機制設計文獻中最近的進展,證明了一般集合中這樣的收益單調性結果。

 

在最簡單的Myerson單物品拍賣情形中,0?wx_fmt=gif表示獨立估值分佈0?wx_fmt=gif的最優收益。當0?wx_fmt=gif隨機支配集合0?wx_fmt=gif(即,對每個競買人0?wx_fmt=gif0?wx_fmt=gif隨機支配0?wx_fmt=gif)時,0?wx_fmt=gif。直覺上,如果每個競買人都準備為該拍品支付更多的價錢,賣方應該能夠獲得更多的收入。這樣的結果看起來很合理,Rubinstein和Weinberg 的研究也表明,作為Myerson的表徵的結果,單物品拍賣也確實是這樣的結果。

 

但當拍賣中有0?wx_fmt=gif個物品時,收益單調性問題就變得微妙起來。Hart 和Reny [10]的研究表明,即使只有一個競買人0?wx_fmt=gif和兩個物品0?wx_fmt=gif,收益單調性也並不適用。他們給出了分佈0?wx_fmt=gif隨機支配時0?wx_fmt=gif0?wx_fmt=gif的例子。因此,當存在0?wx_fmt=gif個物品時,目標只能是approximate revenue monotonicity,例如,對一些絕對正常數0?wx_fmt=gif,有0?wx_fmt=gif

 

對於存在0?wx_fmt=gif個競買人和任意數量的物品的情況,已經證明了如下單調性結果:如果分佈0?wx_fmt=gif隨機支配集合0?wx_fmt=gif,那麼當估值函式為加法時,0?wx_fmt=gif

(Babaioff 等),並且對於任何次可加估值的組合拍賣(Rubinstein 和Weinberg),有0?wx_fmt=gif。這些結果作為它們分佈收益單調的情況下各自近似最優機制的直接推論獲得的。最近,姚、蔡、Devanur和Weinberg對加法估值函式的研究以及在蔡和趙(還有Feldman、Gravin 和 Lucier 在福利最大化方面的研究)對XOS估值函式的研究都發現,對於任何n,m,都存在近似最優的機制。然而,這些機制在分佈中並不是明顯收入單調的; 因此,對於0?wx_fmt=gif,沒有一般的單調性結果。

 

我們的主要成果是解決了XOS估值函式類上的這個問題。對於任意m,和XOS估值函式0?wx_fmt=gif的組合拍賣,我們證明對於c =0?wx_fmt=gif,如果分佈0?wx_fmt=gif隨機支配0?wx_fmt=gif,在估值函式為時0?wx_fmt=gif,有0?wx_fmt=gif。為了證明我們的主要成果,我們還證明了兩個輔助定理,這些成果本身也是有用的。首先,對於任何單引數環境中的拍賣,,我們證明如果分佈隨機支配,則最優收益滿足0?wx_fmt=gif。這意味著收益單調性不僅僅適用於Myerson單物品最優拍賣,也適用於分配向量被限制為任意允許的模式集合的一般的一維拍賣問題。其次,作為上述單引數單調性的結果,我們推測在單需求多專案拍賣中0?wx_fmt=gif

 

這項工作的貢獻:

1)我們已經對收益單調性問題給出了非常一般性的答案,適用於所有XOS次可加估值函式,而在此之前學界甚至對加法估值也不甚瞭解。 

2)我們在證明技術方面的關鍵創新是概念性的,不需要複雜的計算或分析。證明XOS單調性的主要困難在於[3]中給出的近似最優機制不是單調的。為了克服這個障礙,我們首先將我們的拍賣嵌入一個更放鬆的環境(即數字商品)。在這個更大的空間中,我們可以通過兩個嵌入式分佈之間的連線路徑(在新空間中)來建立收益單調性。

 3)在更哲學的層面上,我們同意(Hart和Nisan 所表達的)這樣的觀點,即設計機制的目標不僅是產生一種有效的演算法,而且還能揭示某種數學結構,使得諸如收益單調性這些有趣的問題得到解答。我們目前的工作是這種方法的成果的另一個驗證。

主要結果

我們給出了獨立集中三個標準拍賣模式的結果,其中所有0?wx_fmt=gif物品型別都是從獨立分佈中抽取出來的。下面來回顧一些熟悉的術語。

 

對於任何兩個隨機變數0?wx_fmt=gif0?wx_fmt=gif,如果0?wx_fmt=gif0?wx_fmt=gif在分佈上相等,則記為0?wx_fmt=gif,即對於任意可測量集合0?wx_fmt=gif0?wx_fmt=gif。令0?wx_fmt=gif0?wx_fmt=gif分佈在0?wx_fmt=gif上。如果0?wx_fmt=gif0?wx_fmt=gif隨機支配,我們記為0?wx_fmt=gif。(例如,對於所有0?wx_fmt=gif0?wx_fmt=gif)。同樣地,如果0?wx_fmt=gif支配0?wx_fmt=gif,我們可以寫0?wx_fmt=gif。令0?wx_fmt=gif0?wx_fmt=gif0?wx_fmt=gif上的乘積分佈。如果對於每個0?wx_fmt=gif,都有0?wx_fmt=gif我們說0?wx_fmt=gif(或等價於0?wx_fmt=gif)。

 

0?wx_fmt=gif表示0?wx_fmt=gif個競買人DIC-IR機制,令0?wx_fmt=gif0?wx_fmt=gif上的輸入估值分佈。令0?wx_fmt=gif

0?wx_fmt=gif代表概率空間0?wx_fmt=gif中的隨機變數 。

 

隨機DIC-IR機制是一系列的0?wx_fmt=gif機制,其中0?wx_fmt=gif每個都是一個DIC-IR機制,並且0?wx_fmt=gif根據一些分佈H被隨機選擇。令0?wx_fmt=gif= (0?wx_fmt=gif),0?wx_fmt=gif= (0?wx_fmt=gif)。在輸入分佈0?wx_fmt=gif下由0?wx_fmt=gif產生的revenue定義為0?wx_fmt=gif。令0?wx_fmt=gif

0?wx_fmt=gif代表概率空間0?wx_fmt=gif中的隨機變數0?wx_fmt=gif,0?wx_fmt=gif

 

單引數環境(參見如Gonczarowski和Nisan [8])由一組可能的結果0?wx_fmt=gif指定。對於0?wx_fmt=gif上的估值分佈,0?wx_fmt=gif被定義為任何DIC-IR機制產生的最大收益,其中任意型別像0?wx_fmt=gif的分配0?wx_fmt=gif被限制在集合中。

 

定理1  [單引數環境]令0?wx_fmt=gif(其中為0?wx_fmt=gif分配函式和0?wx_fmt=gif為支付函式)代表其估值分佈0?wx_fmt=gif0?wx_fmt=gif上的0?wx_fmt=gif個玩家的DIC-IR機制。

 

0?wx_fmt=gif0?wx_fmt=gif表示對應於0?wx_fmt=gif0?wx_fmt=gif的隨機變數。那麼對於任何估值分佈0?wx_fmt=gif,存在隨機的DIC-IR機制0?wx_fmt=gif滿足:

(A)0?wx_fmt=gif0?wx_fmt=gif0?wx_fmt=gif,  其中0?wx_fmt=gif0?wx_fmt=gif

(B)0?wx_fmt=gif,和0?wx_fmt=gif

 

推論 對於任何單引數環境0?wx_fmt=gif,如果0?wx_fmt=gif,我們有0?wx_fmt=jpeg

 

定理1可用於證明單需求多專案拍賣的單調性定理。令0?wx_fmt=gif表示單需求模型中分佈F的任意確定性DIC-IR機制可實現的最佳收益,並且使用0?wx_fmt=gif代表允許隨機抽獎的激勵相容機制實現的最佳收益。眾所周知(Chawla,Malec和Sivan)允許抽獎有時可以產生更多的收益。

 

定理2  [單需求多專案拍賣]如果0?wx_fmt=gif,那麼0?wx_fmt=gif

定理2 在下一個定理的證明中是有用的,這是本文的主要結果。令0?wx_fmt=gif

作為估值函式,並且每個0?wx_fmt=gif對於所有0?wx_fmt=gif具有0?wx_fmt=gif(參見第5節定義)。已知如果0?wx_fmt=gif是分次可加的(XOS),則0?wx_fmt=gif,並且如果0?wx_fmt=gif是次可加函式,則更一般地,0?wx_fmt=gif。讓0?wx_fmt=gif0?wx_fmt=gif分佈在某種型別的空間上。我們說如果可以產生一個耦合隨機對0?wx_fmt=gif,對於所有的0?wx_fmt=gif,使得邊際分佈滿足0?wx_fmt=gif0?wx_fmt=gif0?wx_fmt=gif隨機支配0?wx_fmt=gif

 

在下一個定理中,0?wx_fmt=gif是指任意確定DIC-IR機制在估值函式v和分佈0?wx_fmt=gif下可實現的最大收益;0?wx_fmt=gif是指任意隨機BIC-BIR機制在估值函式0?wx_fmt=gif和分佈0?wx_fmt=gif下可實現的最大收益。

 

定理3  [次可加組合拍賣]讓0?wx_fmt=gif成為滿足單調性,亞加性和無外來性的估值。如果0?wx_fmt=gif,則對於0?wx_fmt=gif,我們有0?wx_fmt=gif

其中0?wx_fmt=gif

推論 如果0?wx_fmt=gif是XOS,則0?wx_fmt=gif並選擇0?wx_fmt=gif

給出0?wx_fmt=gif

使用Myerson的理論,當所有分佈,在上是連續的並且嚴格遞增時,定理1是很容易證明的。由於分佈的不連續性和平穩性,一般情況需要更加謹慎。 我們在這裡省略了證明。

 

你看懂了多少呢?歡迎在評論區留言。

 

論文地址:https://arxiv.org/abs/1709.03223

資源推薦

斯坦福大學Tensorflow深度學習課程表  

資源 | 多倫多大學“神經網路與機器學習導論”2017年課程表

爆款 | Medium上6900個讚的AI學習路線圖,讓你快速上手機器學習

Chatbot大牛推薦:AI、機器學習、深度學習必看9大入門視訊

Quora十大機器學習作者與Facebook十大機器學習、資料科學群組

128篇論文,21大領域,深度學習最值得看的資源全在這了(附一鍵下載)

葵花寶典之機器學習:全網最重要的AI資源都在這裡了(大牛,研究機構,視訊,部落格,書籍,Quora……)

重磅|資料科學入門必看:來自斯坦福、MIT、微軟、Twitter等名校名企的20門課程清單

資源 | 機器學習進階,給你推薦13款ML框架

0?wx_fmt=jpeg

 ☞ 點贊和分享是一種積極的學習態度