最優(yōu)算法機(jī)制設(shè)計(jì)若干問(wèn)題的研究

我們從計(jì)算經(jīng)濟(jì)學(xué)和算法設(shè)計(jì)等兩方面對(duì)該項(xiàng)目進(jìn)行了研究： 1) 我們給出了隨機(jī)的誠(chéng)實(shí)機(jī)制的等價(jià)條件。它刻畫(huà)出了隨機(jī)的誠(chéng)實(shí)機(jī)制的內(nèi)在的組合特性。該結(jié)果能夠指導(dǎo)我們?cè)O(shè)計(jì)誠(chéng)實(shí)的機(jī)制。 2) 在此基礎(chǔ)上，我們給出了一個(gè)框架可以將一系列優(yōu)化問(wèn)題的近似算法在不改變近似度的前提下，轉(zhuǎn)換成誠(chéng)實(shí)機(jī)制，這將有助于我們?cè)O(shè)計(jì)收益最優(yōu)化的誠(chéng)實(shí)機(jī)制。 3) 我們從理論上證明了如果一個(gè)競(jìng)拍者以多個(gè)身份進(jìn)行拍賣(mài)的話(huà)，則廣義二價(jià)拍賣(mài)機(jī)制將不一定會(huì)收斂到一個(gè)穩(wěn)定的狀態(tài)，甚至不存在一個(gè)誠(chéng)實(shí)的而且社會(huì)效益最大化的機(jī)制。而在目前的現(xiàn)實(shí)的廣告位置拍賣(mài)中，這種現(xiàn)象卻屢見(jiàn)不鮮。因此，該研究成果告訴我們?cè)谠O(shè)計(jì)拍賣(mài)機(jī)制的時(shí)候，應(yīng)當(dāng)嚴(yán)格禁止一個(gè)拍賣(mài)者以多個(gè)身份進(jìn)行拍賣(mài)。 4) 我們提出了弱支配策略刪除均衡的概念，并且證明在通用二價(jià)拍賣(mài)中，在只有兩個(gè)參與者以及兩個(gè)廣告位的情況下，無(wú)論其刪除過(guò)程怎樣，其最終結(jié)果幾乎滿(mǎn)足社會(huì)效益最大化。 5) 我們對(duì)網(wǎng)絡(luò)論壇中的帖子的文本內(nèi)容設(shè)計(jì)了分析工具，并進(jìn)行情感分析。該分析能夠?qū)墒羞M(jìn)行較為準(zhǔn)確的分析和預(yù)測(cè)。我們利用數(shù)據(jù)挖掘技術(shù)對(duì)網(wǎng)絡(luò)論壇對(duì)股市進(jìn)行分析的研究思路和技術(shù)可以幫助我們來(lái)挖掘廣告競(jìng)拍者的競(jìng)拍行為。 6) 我們研究了世界上最大的B2C市場(chǎng)—eBay下的買(mǎi)家的策略行為，并給出了對(duì)稱(chēng)貝葉斯-納什均衡。我們比較了在此均衡基礎(chǔ)上的拍賣(mài)商的收益和帶有兩份拷貝的二價(jià)拍賣(mài)模型下的拍賣(mài)商的收益。我們證明了在絕大多數(shù)情況下前者的收益要小于后者的收益。 7) 我們研究了基于約束規(guī)劃方法的調(diào)度問(wèn)題中不確定信息的建模和求解算法，分析了調(diào)度問(wèn)題中的不確定控制行為，運(yùn)用定量約束滿(mǎn)足問(wèn)題模型對(duì)實(shí)時(shí)調(diào)度問(wèn)題中的不確定控制行為進(jìn)行基于定量化策略的建模，在約束求解前進(jìn)行基于約束一致性驗(yàn)證的可調(diào)度性分析，并將其融合到已有的約束求解框架，以提高調(diào)度算法和系統(tǒng)的可靠性與可信度。此外，我們還分別研究了行車(chē)路線(xiàn)為樹(shù)和圖的情況下的車(chē)輛調(diào)度問(wèn)題。我們證明了該優(yōu)化問(wèn)題的難解性，并給出了相應(yīng)的近似算法。 8) 我們研究了二進(jìn)制串在“與”、“或”、“非”等操作下的判定問(wèn)題、計(jì)數(shù)問(wèn)題和優(yōu)化問(wèn)題。評(píng)審專(zhuān)家紛紛表示該問(wèn)題描述簡(jiǎn)單，結(jié)論非常有趣。

隨著Internet技術(shù)的迅猛發(fā)展，越來(lái)越多的計(jì)算逐漸轉(zhuǎn)移到并依賴(lài)于Internet這個(gè)巨大的計(jì)算平臺(tái)。為了更好地理解Internet，理論計(jì)算機(jī)科學(xué)除了運(yùn)用傳統(tǒng)的邏輯、組合等數(shù)學(xué)工具外，也開(kāi)始引入微觀經(jīng)濟(jì)學(xué)以及博弈論的相關(guān)知識(shí)。本項(xiàng)目正是著眼于由理論計(jì)算機(jī)領(lǐng)域中的算法和博弈論中的機(jī)制設(shè)計(jì)相結(jié)合所產(chǎn)生的新的研究領(lǐng)域- - 算法機(jī)制設(shè)計(jì)中的優(yōu)化問(wèn)題。. 本項(xiàng)目將著手刻畫(huà)收益最優(yōu)的算法機(jī)制的內(nèi)在組合特性，以及滿(mǎn)足不同均衡解的誠(chéng)實(shí)的算法機(jī)制的等價(jià)條件；并將研究結(jié)果應(yīng)用到廣告位置拍賣(mài)模型中，設(shè)計(jì)出公平、合理、實(shí)際的收益最優(yōu)的拍賣(mài)機(jī)制。. 本項(xiàng)目屬于計(jì)算機(jī)理論科學(xué)和經(jīng)濟(jì)學(xué)中博弈論的交叉學(xué)科，是當(dāng)前國(guó)際理論計(jì)算機(jī)科學(xué)界的一個(gè)研究熱點(diǎn)。本項(xiàng)目扎根于算法設(shè)計(jì)，研究?jī)?nèi)容為算法機(jī)制設(shè)計(jì)理論，研究背景為網(wǎng)絡(luò)廣告位置拍賣(mài)。其研究結(jié)果既可以增進(jìn)兩個(gè)學(xué)科的融合，又可以推動(dòng)網(wǎng)絡(luò)經(jīng)濟(jì)的發(fā)展。

非線(xiàn)性最優(yōu)控制簡(jiǎn)介

解決最優(yōu)控制問(wèn)題最大的難點(diǎn)在于HJB方程的求解，只有當(dāng)系統(tǒng)模型是低階線(xiàn)性模型時(shí)，才有可能給出具有顯式表達(dá)式的最優(yōu)控制解。在實(shí)際系統(tǒng)里，乃至自然界中，幾乎絕大多數(shù)系統(tǒng)都是非線(xiàn)性的系統(tǒng)，想得到具有顯式表達(dá)式的控制量幾乎不可能，這就需要借助計(jì)算機(jī)，以及選擇合適的最優(yōu)的數(shù)值解法，以得到最優(yōu)解。一般的，最優(yōu)控制問(wèn)題的求解方法為數(shù)值算法。極大值原理和動(dòng)態(tài)規(guī)劃從理論方面研究了最優(yōu)控制所應(yīng)遵循的方程和條件，而最優(yōu)控制的數(shù)值算法則是從計(jì)算方面來(lái)確定最優(yōu)控制量的具體方法和步驟。

評(píng)價(jià)最優(yōu)控制數(shù)值算法優(yōu)劣的三個(gè)主要方面是算法的收斂性、計(jì)算復(fù)雜性以及數(shù)值穩(wěn)定性。算法的收斂性是保證計(jì)算過(guò)程能達(dá)到正確結(jié)果的前提。算法的計(jì)算復(fù)雜性也尤其重要，這對(duì)實(shí)時(shí)控制具有特別重要的意義。一個(gè)好的算法應(yīng)使計(jì)算量和存儲(chǔ)量盡可能小，以便能由盡可能簡(jiǎn)單的計(jì)算機(jī)來(lái)實(shí)現(xiàn)計(jì)算。好的算法還應(yīng)具有較好的數(shù)值穩(wěn)定性，即計(jì)算的結(jié)果對(duì)初始數(shù)據(jù)和運(yùn)算過(guò)程的誤差不能過(guò)于敏感，同時(shí)具有處理病態(tài)問(wèn)題的能力。典型的最優(yōu)控制數(shù)值算法包括:求解由極大值原理導(dǎo)出的微分或差分方程的兩點(diǎn)邊值問(wèn)題的各種算法，對(duì)動(dòng)態(tài)規(guī)劃中的貝爾曼方程進(jìn)行數(shù)值求解_的算法，求解線(xiàn)性二次型最優(yōu)控制問(wèn)題的黎卡提方程的各種算法，處理控制或狀態(tài)受約束問(wèn)題的懲罰函數(shù)法，在控制策略的函數(shù)空間中利用搜索尋優(yōu)或梯度尋優(yōu)技術(shù)和牛頓一拉夫森方法等直接求解非線(xiàn)性系統(tǒng)最優(yōu)控制問(wèn)題的算法等。其中，針對(duì)非線(xiàn)性系統(tǒng)的開(kāi)環(huán)最優(yōu)控制問(wèn)題和線(xiàn)性二次型最優(yōu)控制問(wèn)題展開(kāi)的數(shù)值算法研究尤多。

非線(xiàn)性最優(yōu)控制最優(yōu)問(wèn)題間接求解法

在間接法中，我們依靠最小值原理和其它一些必要條件得到一個(gè)兩點(diǎn)邊值問(wèn)題，然后通過(guò)數(shù)值求解該問(wèn)題得到相應(yīng)的最優(yōu)軌跡。在幾種基于打靶法求解兩點(diǎn)邊值問(wèn)題的方法中，多重打靶法是最引人矚目的。而其它的一些間接數(shù)值求解法，比如伴隨方程的向前一向后積分法、函數(shù)空間梯度法等，在過(guò)去的幾年中應(yīng)用并不十分廣泛。間接法的主要優(yōu)點(diǎn)是解的精度高，同時(shí)方法保證了求解滿(mǎn)足最優(yōu)條件。然而間接法常常會(huì)遇到比較嚴(yán)重的解的收斂性問(wèn)題。如果在求解中，沒(méi)有關(guān)于系統(tǒng)初始值的一個(gè)好的選取，或是沒(méi)有關(guān)于約束和非約束下系統(tǒng)運(yùn)動(dòng)軌跡的先驗(yàn)知識(shí)，收斂過(guò)程可能需要花費(fèi)很長(zhǎng)的計(jì)算時(shí)間，甚至可能根本無(wú)法找到最優(yōu)解。

非線(xiàn)性最優(yōu)控制最優(yōu)問(wèn)題直接求解法

在直接法中，連續(xù)性的最優(yōu)控制問(wèn)題通過(guò)參數(shù)化的過(guò)程被轉(zhuǎn)化為了一個(gè)有限維的優(yōu)化問(wèn)題。轉(zhuǎn)化后的問(wèn)題可以通過(guò)一些已有的比較成熟的約束優(yōu)化算法進(jìn)行數(shù)值求解。相對(duì)于間接法而言，直接法無(wú)需考慮最優(yōu)化條件，而是直接求解問(wèn)題本身。直接法不易受到收斂問(wèn)題的影響，但估計(jì)的精度不如間接法。最優(yōu)的必要條件不是直接滿(mǎn)足的，而且伴隨量的估計(jì)精度有時(shí)也會(huì)很差?，F(xiàn)在比較常用的幾種直接求解方法包括最優(yōu)參數(shù)控制法，有限差分方法，配點(diǎn)法，微分包含方法和偽譜方法。在最優(yōu)參數(shù)控制法中，控制量被單獨(dú)參數(shù)化，同時(shí)數(shù)值積分方法被用來(lái)求解微分方程;在有限差分方法中，原微分方程和邊界條件被近似為有限差分方程組:在配點(diǎn)法中，狀態(tài)量和控制量同時(shí)被參數(shù)化，在各個(gè)節(jié)點(diǎn)處，局部分段多項(xiàng)式被用來(lái)近似微分方程;微分包含方法只是將狀態(tài)量參數(shù)化，并使用由速端曲線(xiàn)定義的狀態(tài)變化率;在偽譜方法中，通過(guò)全局多項(xiàng)式將狀態(tài)量和控制量同時(shí)參數(shù)化，積分方程和微分方程通過(guò)求積法被近似。配點(diǎn)法和偽譜方法的一個(gè)重要的特點(diǎn)就是伴隨量的相合估計(jì)。

將委托代理理論和拍賣(mài)理論進(jìn)行有機(jī)結(jié)合，構(gòu)建雙重委托代理模型，從理論、模型和實(shí)證三個(gè)層面，深入考察招投標(biāo)中串謀發(fā)生的內(nèi)在機(jī)理及其對(duì)招投標(biāo)結(jié)果的影響。在此基礎(chǔ)上，考慮到現(xiàn)有招投標(biāo)機(jī)制的缺陷，對(duì)招投標(biāo)中的最優(yōu)激勵(lì)機(jī)制設(shè)計(jì)進(jìn)行探討。主要特色與創(chuàng)新在于：（1）著重于從多項(xiàng)目、多期重復(fù)動(dòng)態(tài)兩個(gè)維度來(lái)研究串謀，而且在研究中將串謀人數(shù)和賄賂進(jìn)行內(nèi)生；（2）將橫向串謀與縱向串謀放在統(tǒng)一分析框架下進(jìn)行研究，現(xiàn)有研究將兩種串謀孤立開(kāi)來(lái)進(jìn)行研究，而實(shí)際上兩種串謀是緊密聯(lián)系且常常會(huì)同時(shí)發(fā)生；（3）現(xiàn)有研究只是籠統(tǒng)地認(rèn)為增加透明度可以減少串謀的發(fā)生，但是沒(méi)有對(duì)合理透明度水平進(jìn)行系統(tǒng)研究。我們需要對(duì)招投標(biāo)不同階段應(yīng)該采取什么樣的合理透明度水平（包括披露什么信息，在哪個(gè)階段披露以及對(duì)誰(shuí)披露信息）進(jìn)行系統(tǒng)深入研究；（4）運(yùn)用實(shí)驗(yàn)經(jīng)濟(jì)學(xué)的方法對(duì)理論研究中的關(guān)鍵性結(jié)論進(jìn)行實(shí)證分析，并對(duì)最優(yōu)的招投標(biāo)激勵(lì)機(jī)制進(jìn)行績(jī)效評(píng)估。