早前AlphaGo擊敗所有人類挑戰者，令人嘩然，人工智能頓時成為熱門話題。我覺得人工智能並非一般熱潮，便開始學習認識人工智能。原來人工智能和對策論（game theory）結合已有一段時間。對策論我有點認識，可從對策論方面入手，向讀者介紹一個人工智能和對策論結合的成果———「程式機制設計」（algorithmic mechanism design）。
在經濟學裏，人是被假定為理性的。「理性」的意思是個人對不同選項有明確的排序（包括平排），而排得最高的選項便是他的選擇（註；非經濟學家，甚至是一些行為經濟學家，對「人是理性」的假設有不同意見，但這不是本文討論範圍）。理性的假設為個人選擇理論提供堅固的基礎，個人選擇理論已十分成熟。
在同一基礎上，Kenneth Arrow（1972年諾貝爾經濟學獎得主之一）開創社會選擇（social choice）理論。他認為社會選擇應該符合4個「基本」條件：（1）社會跟個人一樣，對不同選項有明確的排序；社會的選擇是（2）「最優的」（根據「Pareto準則」）、（3）非獨裁的，和（4 ）不受「不相干的」選項影響。這些條件看似理所當然，卻被Arrow證明是互相牴觸。這就是著名的「Arrow's不可能性定理」（impossibility theorem）。
令人「講真話」的機制
「Arrow's不可能性定理」並非無懈可擊。首先，他的第二個條件比第一個重要，因為社會得到最優的選擇才是最終目的；至於社會是否對所有選項有明確的排序，可以不用堅持。另外，什麼是「相干不相干」其實未有定論，所以他的第四個條件也不用堅持。第二和第三個條件非常合理，沒有牴觸，可以保存。社會選擇理論可在此基礎上重新發展。
另一方面，Allan Gibbard和Mark Satterthwaite指出社會選擇理論的理性基礎不足。他們指出個人對不同選項的排序是「在心中」的（private information），旁人「看不到」（unobservable）。他們認為人們可藉此作假、誤報排序，從中得益。因此他們提倡建立機制、提供誘因，讓人們「講真話」（truth telling）。從此，機制設計（mechanism design）成為選擇理論的重點。
Gibbard和Satterthwaite嘗試尋找令人「講真話」的機制，卻發現只有一些極端機制可行。撇除這些極端機制後，他們證明所有其他機制均不能讓人「講真話」，這就是以他們命名的「Gibbard-Satterthwaite不可能性定理」。社會選擇理論再次走進死胡同，社會選擇理論家卻沒有氣餒，從拍賣理論中找到出路。
賣家選用拍賣或招標時，往往是因為他們不清楚買家對該物件的真正價值，而買家的競投價或入標價通常低於他們對該物件的真正價值。William Vickrey（1996年諾貝爾經濟學獎得主之一）重塑「次價招標方案」（second-price sealed-bid auction），亦名為「Vickrey招標方案」。他證明「次價招標方案」令到投標者以真正價值入標，是一個不折不扣的「講真話」機制。
Vickrey能夠突破「Gibbard-Satterthwaite不可能性定理」，主要是因為勝出的投標者需要支付一個價錢；如果這個價錢設計得宜，如「Vickrey招標方案」，便能提供誘因，讓投標者「講真話」。Edward H. Clarke和Theodore Groves提出更巧妙的設計，名為「Vickrey-Clarke-Groves（VCG）原理」，成功擴展「Vickrey招標方案」，成為「VCG招標方案」，後來更完善為「VCG機制」。
電腦機制設計反過來用於經濟
在經濟學上「VCG機制」應用廣泛，可應用於單元拍賣（「Vickrey招標方案」是一種「VCG機制」）、多元拍賣（「VCG招標方案」是一種多元招標方案，可以用來幫助Google出售廣告位）、採購、雙邊貿易和公共項目。近年網絡興起，「VCG機制」亦可應用在通訊網絡中購買路徑。
以上最後的一個例子是將「VCG機制」應用於電腦科學。近年機制設計漸漸受到電腦科學家重視，有些電腦科學家把它發展成為「程式機制設計」，可反過來用於經濟上。例子是在互聯網上建立新的電腦化交易平台，由「超理性」的軟件操作，比傳統交易平台更成熟和複雜。這些應用統稱為「電子市場設計」（electronic market design）。
Arrow是偉大的經濟學家，開創社會選擇理論，目的是將個人排序集匯成社會排序。經過社會選擇理論家的不懈研究，最後突破「不可能性定理」，建立「VCG機制」。機制設計後來被電腦科學家發展成為程式機制設計，應用更為廣泛，甚至取代傳統交易平台，對我們的日常生活影響深遠，相信這是Arrow始料不及的。
註：如果有多於一個選項排在最高（由於平排是容許的），便需要在其中挑出一項，但這可以是任意的；例如在文章中，一般我對用「他」或「她」沒有特別喜好，所以我在輸入拼音後，便按電腦自動排序而定。
（刊於明報2017年12月11日https://news.mingpao.com/pns/dailynews/web_tc/article/20171211/s00012/1512929010357）
