《最優算法機制設計若干問題的研究》是依託華東師範大學，由卜天明擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：最優算法機制設計若干問題的研究
- 項目類別：青年科學基金項目
- 項目負責人：卜天明
- 依託單位：華東師範大學
項目摘要,結題摘要,
項目摘要
隨著Internet技術的迅猛發展，越來越多的計算逐漸轉移到並依賴於Internet這個巨大的計算平台。為了更好地理解Internet，理論計算機科學除了運用傳統的邏輯、組合等數學工具外，也開始引入個體經濟學以及博弈論的相關知識。本項目正是著眼於由理論計算機領域中的算法和博弈論中的機制設計相結合所產生的新的研究領域- - 算法機制設計中的最佳化問題。. 本項目將著手刻畫收益最優的算法機制的內在組合特性，以及滿足不同均衡解的誠實的算法機制的等價條件；並將研究結果套用到廣告位置拍賣模型中，設計出公平、合理、實際的收益最優的拍賣機制。. 本項目屬於計算機理論科學和經濟學中博弈論的交叉學科，是當前國際理論計算機科學界的一個研究熱點。本項目紮根於算法設計，研究內容為算法機制設計理論，研究背景為網路廣告位置拍賣。其研究結果既可以增進兩個學科的融合，又可以推動網路經濟的發展。
結題摘要
我們從計算經濟學和算法設計等兩方面對該項目進行了研究：（1）我們給出了隨機的誠實機制的等價條件。它刻畫出了隨機的誠實機制的內在的組合特性。該結果能夠指導我們設計誠實的機制。（2）在此基礎上，我們給出了一個框架可以將一系列最佳化問題的近似算法在不改變近似度的前提下，轉換成誠實機制，這將有助於我們設計收益最最佳化的誠實機制。（3）我們從理論上證明了如果一個競拍者以多個身份進行拍賣的話，則廣義二價拍賣機制將不一定會收斂到一個穩定的狀態，甚至不存在一個誠實的而且社會效益最大化的機制。而在目前的現實的廣告位置拍賣中，這種現象卻屢見不鮮。因此，該研究成果告訴我們在設計拍賣機制的時候，應當嚴格禁止一個拍賣者以多個身份進行拍賣。 （4）我們提出了弱支配策略刪除均衡的概念，並且證明在通用二價拍賣中，在只有兩個參與者以及兩個廣告位的情況下，無論其刪除過程怎樣，其最終結果幾乎滿足社會效益最大化。（5）我們對網路論壇中的帖子的文本內容設計了分析工具，並進行情感分析。該分析能夠對股市進行較為準確的分析和預測。我們利用數據挖掘技術對網路論壇對股市進行分析的研究思路和技術可以幫助我們來挖掘廣告競拍者的競拍行為。（6）我們研究了世界上最大的B2C市場—eBay下的買家的策略行為，並給出了對稱貝葉斯-納什均衡。我們比較了在此均衡基礎上的拍賣商的收益和帶有兩份拷貝的二價拍賣模型下的拍賣商的收益。我們證明了在絕大多數情況下前者的收益要小於後者的收益。（7）我們研究了基於約束規劃方法的調度問題中不確定信息的建模和求解算法，分析了調度問題中的不確定控制行為，運用定量約束滿足問題模型對實時調度問題中的不確定控制行為進行基於定量化策略的建模，在約束求解前進行基於約束一致性驗證的可調度性分析，並將其融合到已有的約束求解框架，以提高調度算法和系統的可靠性與可信度。此外，我們還分別研究了行車路線為樹和圖的情況下的車輛調度問題。我們證明了該最佳化問題的難解性，並給出了相應的近似算法。 （8）我們研究了二進制串在“與”、“或”、“非”等操作下的判定問題、計數問題和最佳化問題。評審專家紛紛表示該問題描述簡單，結論非常有趣。
