【明報文章】2017-12-11
早前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始料不及的。
註：如果有多於一個選項排在最高（由於平排是容許的），便需要在其中挑出一項，但這可以是任意的；例如在文章中，一般我對用「他」或「她」沒有特別喜好，所以我在輸入拼音後，便按電腦自動排序而定。
■稿例
1.論壇版為公開園地，歡迎投稿。讀者來函請電郵至forum@mingpao.com，傳真﹕2898 3783。
2.本報編輯基於篇幅所限，保留文章刪節權，惟以力求保持文章主要論點及立場為原則﹔如不欲文章被刪節，請註明。
3.來稿請附上作者真實姓名及聯絡方法（可用筆名發表），請勿一稿兩投﹔若不適用，恕不另行通知，除附回郵資者外，本報將不予退稿。
4.投稿者注意：當文章被刊登後，本報即擁有該文章的本地獨家中文出版權，本報權利並包括轉載被刊登的投稿文章於本地及海外媒體（包括電子媒體，如互聯網站等）。此外，本報有權將該文章的複印許可使用權授予有關的複印授權公司及組織。本報上述權利絕不影響投稿者的版權及其權利利益。
作者是香港大學經濟及工商管理學院副教授
[程騰歡]
在經濟學裏，人是被假定為理性的。「理性」的意思是個人對不同選項有明確的排序（包括平排），而排得最高的選項便是他的選擇（註；非經濟學家，甚至是一些行為經濟學家，對「人是理性」的假設有不同意見，但這不是本文討論範圍）。理性的假設為個人選擇理論提供堅固的基礎，個人選擇理論已十分成熟。
在同一基礎上，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始料不及的。
註：如果有多於一個選項排在最高（由於平排是容許的），便需要在其中挑出一項，但這可以是任意的；例如在文章中，一般我對用「他」或「她」沒有特別喜好，所以我在輸入拼音後，便按電腦自動排序而定。
■稿例
1.論壇版為公開園地，歡迎投稿。讀者來函請電郵至forum@mingpao.com，傳真﹕2898 3783。
2.本報編輯基於篇幅所限，保留文章刪節權，惟以力求保持文章主要論點及立場為原則﹔如不欲文章被刪節，請註明。
3.來稿請附上作者真實姓名及聯絡方法（可用筆名發表），請勿一稿兩投﹔若不適用，恕不另行通知，除附回郵資者外，本報將不予退稿。
4.投稿者注意：當文章被刊登後，本報即擁有該文章的本地獨家中文出版權，本報權利並包括轉載被刊登的投稿文章於本地及海外媒體（包括電子媒體，如互聯網站等）。此外，本報有權將該文章的複印許可使用權授予有關的複印授權公司及組織。本報上述權利絕不影響投稿者的版權及其權利利益。
作者是香港大學經濟及工商管理學院副教授
[程騰歡]
沒有留言:
發佈留言