發布時間：2021-04-23所屬分類：科技論文瀏覽：1次
摘 要： [譯者按]在復雜的環境中，要充分了解交易的潛在特征，從而設計出最好的機制來有效地從交易中獲得收益是很具有挑戰性的。近年來，人工智能已經成為一個重要的工具，它可以幫助市場設計者揭示重要的市場基本面，并更好地預測可能導致市場摩擦的波動。本文提供
[譯者按]在復雜的環境中，要充分了解交易的潛在特征，從而設計出最好的機制來有效地從交易中獲得收益是很具有挑戰性的。近年來，人工智能已經成為一個重要的工具，它可以幫助市場設計者揭示重要的市場基本面，并更好地預測可能導致市場摩擦的波動。本文提供了一些人工智能如何幫助市場設計者改善市場運作的例子，并概述了人工智能將如何繼續形塑和影響市場設計的方向。
[關鍵詞]人工智能機器學習激勵拍賣市場設計
一、導言
幾千年來，市場在為個人和企業提供從貿易中獲益的機會方面發揮了關鍵作用。市場往往需要結構和各種機制支持才能有效運作。例如，當價格發現(pricediscovery)成為一種必需，拍賣就成為了一種常用的從貿易中獲得收益的機制。這一領域的研究現在通常被稱為市場設計(marketdesign)——最早由威廉•維克瑞(WilliamVickrey)于1961年在《反投機、拍賣和競爭密封投標》(Counterspeculation,Auctions,andCompetitiveSealedTenders)一文中提出——這表明，為了取得有效的結果，更廣泛地設計拍賣和市場機構是至關重要的。任何市場設計師者都需要了解預期完成的交易的一些基本細節，以便設計最有效果且最有效率的市場結構來支持這些交易。例如，將醫生與住院醫生相匹配的國家，住院醫生匹配項目最初設計的時候，幾乎所有的醫生都是男性，而他們的妻子往往跟隨他們到所駐醫院。到了20世紀90年代，這一項目就需要重新設計，以滿足雙方都是醫生的夫婦的需要，因為男女醫生不能被分配到不同的城市。即使是像農民死亡后出售農場這樣稀松平常的事情，也需要掌握關于結構和決策的知識，究竟是將農場作為整體出售;還是房子作為周末度假別墅單獨出售，同時將土地出售給鄰近的農民;還是將森林單獨出售給野生動物保護基金。
在復雜的環境中，理解交易的基本特征可能是不容易的，更不用說充分了解它們，以便設計出最好的機制，有效地從貿易中獲得收益，這是很有挑戰性的。例如，最近互聯網廣告交易平臺快速發展，許多廣告代理被使用實時拍賣的廣告商獲得。但是，出版商應該如何設計這些拍賣，以充分利用他們的廣告空間，以及他們如何最大限度地提高他們的回報?羅杰•邁爾森(RogerB.Myerson)的早期理論拍賣設計研究，以及邁克爾•奧斯特洛夫斯基(MichaelOstrovsky)和邁克爾•施瓦茨(MichaelSchwartz)近年對互聯網廣告定價的研究都已經表明，只要在市場設計時對起拍價設定稍作優化，就可以對在線廣告平臺的盈利產生戲劇性的影響。
但是，市場設計者如何能獲知設定最優或至少更好的起拍價所必需的交易特征呢?或者更廣泛地說，市場設計者如何才能更好地了解其市場環境?針對這些挑戰，人工智能和機器學習正日益成為市場設計的重要工具。零售商和交易平臺，如eBay、淘寶、亞馬遜、優步和許多其他企業，都在進行海量數據挖掘，以建立更優化的市場模式，幫助他們為客戶創造更好的體驗，并提高他們的市場效率。通過更好的預測工具，這些公司可以預測，并更好地管理復雜和動態的市場環境。人工智能和機器學習算法改進了預測效度，有助于市場和零售商更好地預測消費者需求和生產商供應，并幫助產品和服務能夠進入到更細分的市場。
回到在線廣告的市場，像谷歌這樣的雙邊市場(two-sidedmarket)，它將廣告商與消費者相匹配，不僅使用人工智能來設置起拍價，還將消費者細分，進行廣告定位，而且他們還開發了基于人工智能的工具來幫助廣告商進行廣告競價。在2017年4月，谷歌推出了“智能競價”，這是一項基于人工智能和機器學習的產品，幫助廣告商根據廣告轉化率自動出價，以便他們能夠更好地確定他們的最優出價。谷歌解釋說，這些算法使用了大量的數據，并不斷地完善用戶轉化模型，以便使廣告商的投入都能用在刀刃上，給他們帶來最高的轉化率。
二、機器學習與激勵拍賣
在20世紀上半葉，美國最重要的基礎設施項目都在運輸和能源領域。然而，到21世紀初，需要大量運輸的不僅僅是人員和貨物，還有信息。移動設備、無線網絡、視頻點播、物聯網、云服務以及更多新技術新事物的出現，已經創造了對通信網絡進行重大投資的需求。隨著5G技術的發展，更多的技術將紛至沓來。
然而，無線通信依賴于基礎設施和其他資源。無線通信速率取決于信道容量，而信道容量又取決于所使用的通信技術和專用于無線電頻譜帶寬的數量。為了鼓勵帶寬的增長和新用途的快速發展，奧巴馬政府于2010年發布了《國家寬帶計劃》(NationalBroadbandPlan)。該計劃目標將大量帶寬從舊的、生產力較低的用途中解放出來，投入到現代數據高速公路系統中。
2016—2017年，美國聯邦通信委員會(FCC)設計并召開拍賣來完成上述計劃的部分工作。那次拍賣的頻率使用許可總金額高達200億美元。為了優化頻率資源，給新許可證騰出空間，FCC先以100億美元的價格向廣播電視運營商購買了轉播權，又支付了近30億美元將其他廣播公司轉移到新頻道。最終，共提供約84MHz頻率資源，其中70MHz作為授權頻率，另外14MHz作無牌用途。本節將詳細描述這一過程，以及人工智能和機器學習在改進這一市場的基本算法方面所起的作用。
總體而言，重新分配頻率資源，無論是規劃還是實施都不容易，也沒有直截了當的方法。這一計劃的規劃過程就遭遇到前所未有的計算困難，實施階段則需要各部門的高度協調。特別是重新分配的一部分頻率資源是用于超高頻廣播電視的頻譜帶，需要預先設定要清理多少個原有頻道;暫停哪些電臺電視臺(為新的用途騰出頻率空間);哪些頻道會繼續留給原有電臺電視臺使用;何時進行頻道切換，以避免信號干擾。這一極為復雜的市場設計問題涉及多了個計算難題，其中最主要的就是非確定性多項式時間(NP)。這一過程中最關鍵的算法之一——“可行性檢查器”(feasibilitychecker)，已經借助機器學習的方法被開發出來。
那么，為什么要重新分配頻率資源呢?電視轉播技術在20世紀末發生了巨大的變化。早期都是通過模擬技術傳播;其后幾十年里，有線電視和衛星服務不斷擴展，到2010年，90%以上的美國人都獲得了這些替代服務。標清電視信號被高清信號和4K信號所取代。數字電視和調諧器的出現降低了頻道資源分配的重要性，因此消費者/觀眾使用的頻道不需要與廣播電視公司所使用的頻道相匹配。數字編碼能夠更有效地利用波段，它使多路復用成為可能，因此曾經只能加載單一標清信號的頻道現在可以加載多個高清頻道，邊際譜(marginalspectrum)的價值有所下降。
相關知識推薦：人工智能的核心期刊都有哪些
然而，頻道資源的重新分配是一項困難重重的項目，并非普通市場機制可實現的。美國有數以千計的電視廣播塔，它們發射出信號能夠造成半徑為200英里的干擾范圍，所以這些頻率中的廣播內容需要清理干凈，以用于新用途。這一過程不僅需要美國不同地區間的協調，還需要協調與美國接壤的加拿大和墨西哥邊境地區。由于任一頻率只能在所有相關廣播公司停止運作之后才能使用，因此及時協調各方棄用頻率方可保證效率，也即要求同步操作。
需要解決的問題很多，其中之一是如何確定哪些電臺將在頻道資源重新分配后繼續保留。如果目標是效率，那么解決方案就是在拍賣后，使這些得以保留的頻道的價值最大化。設N是所有當前電臺電視臺的集合，SN，設為這些電臺電視臺的一個子集。設集合C為拍賣后可分配給電臺電視臺的頻道，代表不再能繼續廣播的電臺電視臺所獲得的零分配空集。頻道分配是映射A:N→C∪{}。可供分配的頻道都是有條件的，即排除了電臺電視臺之間的相互干擾，采用公式：A(n1)=c1A(n2)≠c2，(c1，c2)∈C2。每一個限制條件都可由一個四元組合來描述：(N1，c1n2，c2)。FCC面臨的問題中，這樣的限制條件超過百萬。如果能滿足所有抗干擾條件，那么頻道分配即是可行的，此時A代表可行的分配集合;設集合A為可行的分配。集合S為可繼續廣播的電臺電視臺，S∈F(C)，如果A∈A，則∈A(S)。
大多抗干擾條件采取了特殊形式，即地理位置臨近的兩個電臺電視臺無法共用同一頻道，這類電臺電視臺被稱為“鏈接臺”，它們之間的關系設為(n1，n2)∈L。對這樣一對“鏈接臺”，限制條件可設為A(N1)=A(N2)A(N1)=。這些就是同信道干擾條件。(N,L)則構成一個節點N與弧L組成的圖譜。如果同信道干擾是唯一限制條件，那么確定S∈F是否成立，就決定了能否將集合C中的頻道分配給集合N中的電臺電視臺，以便保證沒有兩個鏈接節點被分配到同一頻道上。
圖1顯示了美國和加拿大的同信道干擾圖。圖顯示，美國東部地區和太平洋沿岸干擾最為最密集。問題是能否正確地將顏色(通道)分配給圖中的每個節點(電臺電視臺)，保證兩個鏈接節點被分配到不同的顏色。圖著色是NP完全問題(NP-completeproblem)的一類，對于這種問題，沒有已知的算法能夠快速解決，并且通常假設最壞情況下的求解時間與問題大小呈指數增長關系。由于一般的站點分配問題包括圖著色問題，因此它也是NP完全問題，并且因為FCC的問題體量，其求解難度會變得極為棘手。
這樣一封信會讓許多電臺電視臺感到不悅，更加猶豫是否參拍。因此FCC決定使用另一種設計，即廣播公司只需要決定是同意出售其廣播權，還是拒絕FCC的出價保留其廣播權，繼續使用原頻率廣播。所有廣播公司都很滿意這一拍賣設計，即便還有其他的選項(例如變更保留廣播權，但變更頻率)，也不予以考慮。
在這一簡化了的拍賣中，每位參拍者i在拍賣輪次t時的出價為pi(t)，這一價格每一輪遞減。每一輪中，參拍者都可以選擇“退出”，拒絕當前出價，并保留自己的廣播權;或者選擇接受當前出價。t輪結束后，所有參拍臺被同時進行算法處理。在處理電視臺t時，考慮到有些臺已經選擇退出，因此必須有空余頻道供再分配，這時拍賣軟件會使用“可行性檢查器”校驗電視臺t能否繼續保留其廣播權。這就是上述提到的廣義圖著色問題。如果軟件運行超時，或計算結果為無法分配該電視臺，則這家電視臺即成為本輪拍賣贏家，成交價為pi(t–1)。否則，出價將降至pi(t)，它可以根據規則選擇退出或者繼續。因此，對于電臺電視臺而言，無論定價算法和軟件如何設定運行，在pi(t)
這種針對難解計算問題(hardcomputation)的時鐘拍賣理論是由保羅•米爾格羅姆和厄爾文•塞加爾(IrvingSegal)提出的，他們模擬出超低成本且高效的電視廣播權購買實例。
這種下降式拍賣設計的表現在很大程度上取決于“可行性檢查器”的質量。根據早期的模擬，我們粗略估計，每1%的可行性檢查失敗將增加約1.5%，即約1.5億美元的廣播權購買成本。因此，快速解決大部分問題成為拍賣設計團隊的當務之急。
作為一個理論命題，對于頻道打包1問題中的可行性檢查，任何已知的算法都會隨著問題的體量增大而增加。然而，如果我們知道可能的問題的分布，仍然可以大概率地找到快速算法。但是我們如何知道問題的分布，又如何找到這樣的算法呢?
FCC拍賣使用了由凱文•萊頓-布朗(KevinLeyton-Brown)教授領導的不列顛哥倫比亞大學拍賣經濟學研究團隊研發的可行性檢查器。研發過程包含許多步驟，但在這里我們聚焦其中機器學習的作用。拍賣經濟學的目標是能夠在一分鐘或更短的時間內解決99%的問題。
研發工作首先是模擬拍賣產生可行性問題，如在實際拍賣中可能遇到的問題。模擬產生了大約140萬個問題，可用于訓練和測試可行性檢查算法。分析的第一步是將問題描述為混合整數規劃(mixedintegerprograms)，并測試標準商業軟件CPLEX和Gurobi，以判斷實驗結果與實驗目標相距幾何。結論卻是，相去甚遠。每100秒時間段內，Gurobi只能解決大約10%的問題，而CPLEX只能解決大約25%。對于實時拍賣，這一結果是不盡人意的。
接下來，同樣的問題被描述為布爾可滿足性問題(Booleansatisfiabilityproblem，SAT)，并測試了近期參與SAT求解大賽的17個求解器。這次結果差強人意，但是100秒內仍沒有哪個求解器的解決能力能超過2/3。而實驗目標是在60秒內，解決99%的問題。
下一步是使用自動算法配置(automatedalgorithmconfiguration)，這是由弗蘭克•亨特(FrankHutter)、霍格•胡斯(HolgerH.Hoos)和凱文•萊頓-布朗2011年開發的程序，并由萊頓-布朗和他的學生在實驗中進行應用測試。首先使用解決可滿足性問題的高度參數化算法，訓練隨機森林算法模型(randomforestmodel)。為了做到這一點，我們首先進行模擬拍賣，假設參拍者作出理性行為，以產生大量具有代表性的數據。然后，使用大量不同參數組合，來確定每個參數向量的求解時間分布，最終解決問題。這一過程產生了一個帶有參數和測量指標的數據集。運行過程中最有趣的兩點是，中位運行時間和在一分鐘內解決問題的比例。然后，通過使用貝葉斯模型，我們加入了不確定性，實驗者“相信”結果呈正態分布，隨機森林算法所決定的平均值，和取決于參數向量與數據集最近點的距離的方差。接下來，參考先驗的均值和方差以及已知最佳參數向量的結果，系統識別能最大限度地提高預期結果改進的參數向量。最后，系統測試實際運行，識別參數并將其作為對數據集的觀察。系統迭代處理，識別出更多的參數進行測試、校驗，并將它們添加到數據中，以提高模型的精度，直到預算時間耗盡。——論文作者：保羅•米爾格羅姆史蒂文•泰迪里斯劉佳平
SCISSCIAHCI
