社會投票問題的參數化建模與算法研究

《社會投票問題的參數化建模與算法研究》是依託長沙理工大學，由鄭瑩擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：社會投票問題的參數化建模與算法研究
• 項目類別：青年科學基金項目
• 項目負責人：鄭瑩
• 依託單位：長沙理工大學

項目摘要

投票是一種簡單可行且深入人心的社會選擇方式，然而投票能否真正反映投票人的意願，當選者是否真的眾望所歸，引發了很多爭議，對投票系統的複雜性研究也成為近些年的熱點。投票系統中很多問題都已經證明了是NP難解的，但人們對投票系統複雜性的認識還處在一個初級階段，而且目前很多投票系統研究結果在複雜度或精確度方面存在著種種缺陷。本項目主要從投票問題的建模和複雜性分析、投票問題的參數算法設計、投票系統的策略攻擊分析以及投票系統的擴展套用等方面進行研究。首先從投票系統中具體問題出發，分析這些問題的參數複雜性，並根據問題的結構特性結合參數計算技術提出高效可行的求解方法。然後分析具體投票系統的策略攻擊模式以及複雜性，從而證明這些破壞行為的不可行。並最終實現對投票系統的核心化過程和參數算法實現，更好地對投票系統的合理性進行統計分析，從而推動可計算的社會選擇領域的發展。

結題摘要

人們在做出一個共同的決定時最好的辦法就是投票。然而，即便我們有好的投票規則，仍然無法保證能得到期盼的結果。其中一個原因就是會有人為了改變投票結果而對整個投票過程進行策略攻擊。人們不禁會問：是否存在一種投票規則，即在這個投票規則下即便有人進行策略攻擊也不能改變最終結果？這個問題促生了一個新的研究領域的出現——可計算的社會選擇。 本課題主要研究了可計算的社會選擇領域中的四個問題：投票問題的建模和複雜性分析、投票問題的參數算法設計、投票系統的策略攻擊分析以及投票系統的擴展套用。研究了投票問題基於d-贊成規則，最大最小規則，孔多塞規則，Copeland規則等不同的投票規則下的計算複雜性，並根據問題的結構特性結合參數計算技術提出了可行的求解方法。重點研究了投票問題在三種策略攻擊模式下的計算複雜性，已經證明了基於最大最小規則，Copeland規則和孔多塞規則的投票問題在賄賂攻擊下是NP難解的，基於Borda規則的投票問題在操縱攻擊下是NP難解的，以及基於孔多塞規則，Copeland規則和最大最小規則的投票問題在控制攻擊下是NP難解的，說明這些策略攻擊行為是不可行的。項目資助發表SCI、EI和核心論文5篇，待發表2篇。培養碩士生3名（包括留學生），其中1名已經取得碩士學位，1名取得博士學位，1名在讀。