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