計算社會選擇是一個跨學科的領域研究界面的社會選擇理論和計算機科學，促進兩個方向的交換思想。一方面，它涉及的應用技術開發的電腦嗎科學、復雜性分析和算法設計等研究社會選擇機制，比如投票過程或公平劃分算法。另一方面，計算社會選擇從社會選擇理論概念導入計算。為實例，研究偏好聚合機制也非常相關的多重代理系統。在這個簡短的紙我們一般介紹計算社會選擇，提出了一種分類通過這門學科來解決的問題，加上一些說明性的的例子和一個(不完全)參考書目。
1、 簡介：計算社會選擇是什么?
社會選擇理論是關注設計與分析方法集體決策。近幾年，計算機科學和人工智能(人工智能)已經采取越來越多的社會選擇感興趣。有兩個主要原因，導致兩種不同的研究。第一個是關于進口人工智能的概念和方法解決問題最初源于社會的選擇。的起點這一研究的是在社會選擇的大部分工作理論集中在關于存在建立抽象的結果(或其他)程序滿足特定需求，但計算問題很少被認為是。例如，它可能是不可能的設計一個選民投票協議使它不可能作弊，很可能的情況是，作弊成功的結果是一個難以計算的問題，因此被視為一個可接受的風險。這就是人工智能(和運籌學，更普遍計算機科學)。除了復雜性理論分析投票協議、其他工作的典型例子計算社會選擇包括社會的正式規范和驗證程序(如公平分割算法)用數學邏輯，和技術的應用開發的人工智能和邏輯組合的緊湊表示偏好域(如談判不可分割的資源和支持委員會)。
研究在計算社會選擇的第二行相反。這是關心進口
從社會的概念和過程選擇理論為解決問題，出現在計算機科學和人工智能的應用程序域。例如，這是管理社會的自治軟件代理，要求談判和投票程序。另一個例子從社會選擇的應用技術開發頁面嗎互聯網搜索引擎排名系統。
這些都是例子為更廣泛的跨學科研究的趨勢涉及所有的決策理論、博弈理論、社會選擇和福利經濟學一方面，計算機科學、人工智能、可替換主體系統，運籌學和計算邏輯。特別是，互利的影響研究博弈理論和計算機科學已得到廣泛認可并已導致顯著的進步等領域組合拍賣機制設計，系統的談判，并在電子商務應用程序。
本文的目的是進一步突出一些領域的成功跨學科研究，關注社會選擇理論的相互作用計算機科學，提出這個新分類法的問題解決計算社會選擇的紀律。有兩種截然不同的線的我們可以通過計算來解決社會選擇的主題進行分類:
(1) 社會選擇的性質問題處理；和
(2) 正式或計算技術研究的類型。
這兩個維度在某種程度上是獨立的。我們第一次給一個(nonexhaustive)主題列表下下降(一個):
偏好聚合----聚合偏好意味著映射集合P = hP1,。偏好關系，句(或資料)的個人代理到一個集體偏好關
系P(這意味著繞過箭頭不可能定理[6]通過放松其適用性條件之一)。有時我們只關心決定社會優先選擇，或社會優先選擇，而不是一個完整的子集集
體偏好關系：社會選擇函數映射一個集體概要文件P 到一個替代，而社會選擇對應的地圖一個集體概要P 為一個非空的子集的選擇。這第一個特定的主題是低于以下的也主要是處理某種偏好聚合，但每個在一個特定的上下文。
投票理論——投票是達到共同的最流行的方式之一決策。社會選擇理論的研究人員廣泛的研究不同家庭的投票規則的屬性，但通常被忽視計算問題。整個全景的投票規則提出了在文獻[15]。我們這里只提到了幾個例子。一個位置得分規則計算得分為每個候選人(數量)從每個個體偏好和選擇的候選人最大的成績。簡單多數原則，例如，給的分數1最喜歡的每個選民和候選人0到其他所有人。的Borda規則分配分數從m(候選人)的數量下降到1候選人根據每個選民的偏好配置文件。另一個重要的概念是，孔多塞的贏家，即候選人優先其他候選人由嚴格的大多數選民。眾所周知，有配置文件不存在孔多塞的贏家。顯然，當存在一個孔多塞冠軍那是獨一無二的。一個Condorcet-consistent規則是一個投票選舉規則孔多塞只要有一個贏家。
資源分配和公正的部門——不可分割的資源分配貨物分配項目旨在從一個有限集R的一組的成員代理的N，對所有可能的包的商品的偏好。在集中分配任務是由一個中央的問題權威的代理人事先給他們的
偏好。在分布式配置問題代理談判，他們的交流利益，交易或貿易貨物在幾輪，可能在一個多邊的方式。資源分配問題的概述在[20]。我們可以區分兩種類型的標準在評估質量的資源分配，即效率與公平。最基本的效率標準是帕累托效率：一個分配是這樣，沒有選擇分配，會更好一些代理沒有任何其他的更糟糕。為一個例子公平條件envy-freeness：分配是envy-free敵我識別沒有代理寧愿獲得他人持有的包一個。
聯盟的形成，在許多場合，代理商不但是競爭而不是合作，例如更有效地完成給定的任務。例如假設代理x獎勵10時執行一個給定的單獨的任務，而代理y 得到20。現在如果他們組成一個團隊，獲得50(例如認為兩個音樂家，單獨或在玩二重唱)。聯盟的形成通常研究兩個問題：如何聯盟將形成對于一個給定的問題，那么應該如何盈余被劃分在聯盟的成員(后解決他們優化問題)。核心穩定性的概念：一個代理應該沒有離開聯盟的動機。研究了這些問題領域的合作博弈理論[72]，和不同的解決方案的概念介紹了。例如，最強的，稱為核心，要求沒有其他聯盟可能會使其成員更好。
判斷聚合和信仰融合領域的判斷聚合的目的在于研究一群人應該如何聚合他們的成員的個人判斷一些相互關聯的命題到相應的集體判斷這些命題。這種
聚合問題發生在許多不同的集體決策機構(特別是委員會和專家小組)。1信念合并是一個密切相關的問題，關注調查聚合方式數量的個人信仰基地為集體(之間的聯系這兩個問題都討論了由埃克特和Pigozzi[78])。
排名系統——所謂的“排名系統”設置的一個變體經典社會選擇理論的代理和一系列的選擇一致的。最知名的家庭這樣的系統頁面排名系統的搜索引擎(和更普遍的是，聲譽系統)[92]。
關于我們提出的第二個維度分類計算的主題社會選擇，即分類根據技術問題社會選擇問題的解決而不是自然本身，這是現在(同樣不完整)的問題列表:— 計算困難聚合規則;
— 社會選擇組合域;
— 計算方面的驗證策略和操縱;
— 分布式資源分配和談判;
— 在社會選擇通信需求;
— 基于邏輯分析的社會過程。
剩下的紙是組織根據第二個維度。為每一個上面的產品我們給一些典型問題考慮的描述文獻，加上一些指針書目。
2、 計算困難的聚合規則
許多聚合和投票規則實際上使用的那些可計算的線性或二次時間在候選人的數量(和幾乎總是線性的
