首页    期刊浏览 2024年12月01日 星期日
登录注册

文章基本信息

  • 标题:Computational Social Choice (Tutorial)
  • 本地全文:下载
  • 作者:Felix Brandt
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2015
  • 卷号:30
  • 页码:19-19
  • DOI:10.4230/LIPIcs.STACS.2015.19
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:Over the past few years there has been a lively exchange of ideas between computer science, in particular theoretical computer science and artificial intelligence, on the one hand and economics, in particular game theory and social choice, on the other. This exchange goes in both directions and has produced active research areas such as algorithmic game theory and computational social choice. Social choice theory concerns the formal analysis and design of methods for aggregating possibly conflicting preferences such as in voting, assignment, or matching problems. Much of the work in classic social choice theory has focused on results concerning the formal possibility and impossibility of aggregation functions that combine desirable properties. This tutorial provided an overview of central results in social choice theory with a special focus on axiomatic characterizations as well as computational aspects. While some aggregation functions can be easily computed, others have been shown to be computationally intractable (e.g., NP-hard or #P-hard). Topics that were covered in this tutorial included (i) rational choice theory, (ii) Arrow's impossibility theorem, (iii) tournament solutions (such as the top cycle, the uncovered set, the Banks set, or the tournament equilibrium set), and (iv) randomized social choice functions. The overarching theme were escape routes from negative results such as Arrow's impossibility theorem.
  • 关键词:social choice theory; economics; algorithms; theory
国家哲学社会科学文献中心版权所有