社會網路環境下機制設計理論及關鍵技術研究

《社會網路環境下機制設計理論及關鍵技術研究》是依託南京大學，由王崇駿擔任項目負責人的面上項目。

基本介紹

• 中文名：社會網路環境下機制設計理論及關鍵技術研究
• 項目類別：面上項目
• 項目負責人：王崇駿
• 依託單位：南京大學

項目摘要

影響最大化問題是社會網路分析領域一個廣為研究的重要問題。現有的社會網路傳播模型及影響最大化算法的研究取得了可觀的進展，但是大多存在一個信息完全可觀察的假定，從而限制了其對現實環境的建模能力。近年來一些相關工作考慮上述不確定性及節點之間的策略互動，將影響最大化問題建模成一個機制設計問題，成為解決這一問題的有效途徑。但是這些工作大多流於機制設計的簡單套用，實際上社會網路的套用環境是包含海量個體、有限個體理性、分布性和動態性的複雜環境，這給機制設計的傳統理論框架帶來了新的挑戰。本項目立足於線上社會網路的具體套用領域，通過考慮用戶的私有信息，把影響最大化問題建模成一個機制設計問題，並且以問題驅動的形式深入地研究社會網路環境中的機制設計問題。這不僅可以為解決社會網路中的影響最大化問題提供一種新思路，還可以開拓機制設計的套用領域，完善其理論框架，促進其在計算機科學領域的發展。

結題摘要

影響最大化問題是社會網路分析領域一個重要的研究問題。現有的社會網路傳播模型及影響最大化算法的研究存在信息完全可觀察的假定，限制了其對現實環境的建模能力。社會網路的套用環境是包含海量個體、有限個體理性、分布性和動態性的複雜環境。本項目立足於線上社會網路的具體套用領域，通過考慮用戶的私有信息，把影響最大化問題建模成一個機制設計問題，並且以問題驅動的形式深入地研究社會網路環境中的機制設計問題。這主要涉及到如下三個基本的問題：一是，如何有效建模面向社會網路影響最大化的信息傳播問題；二是，如何將社會網路中的信息傳播問題建模為機制設計問題；三是，針對難計算的機制設計問題，如何近似求解。主要取得了如下進展： 1) 提出了一系列新的信息傳播模型，包括：成本約束條件下的信息傳播，異構線上社交網路中信息傳播問題，信息傳播過程中實體情緒的變化，信息傳播問題中的異常檢測問題，多元信息融合的信息傳播問題。同時考慮社會網路的社團結構對每一類信息傳播問題的影響，並在多個社會網路實驗平台上進行了驗證。 2) 將信息傳播問題建模為開放環境下的機制設計問題，並對開放環境下的模型修正展開了研究；同時研究了社交網路中的路徑拍賣問題，提出了一種基於核選擇的路徑拍賣機制，大大降低了核約束的數量，並且通過理論證明其具有很好的激勵性質，且可在多項式時間內計算出分配結果和agent的支付結果，相比VCG大大減少了所需的總支付。 3) 提出了計算可行的常數因子的近似機制，基於算法機制設計的框架，在網路節點agent的代價機率分布已知的假設下，將基於邏輯的社會法則最佳化的問題框架，加權Steiner tree等問題進一步擴展到策略場景下，並證明這些機制都是激勵相容的，滿足個體理性和多項式可計算的。