License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2015.19
URN: urn:nbn:de:0030-drops-49593
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4959/
Go to the corresponding LIPIcs Volume Portal

Brandt, Felix

Computational Social Choice (Tutorial)

pdf-format:
59.pdf (0.4 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{brandt:LIPIcs:2015:4959,
  author =	{Felix Brandt},
  title =	{{Computational Social Choice (Tutorial)}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{19--19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Ernst W. Mayr and Nicolas Ollinger},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4959},
  URN =		{urn:nbn:de:0030-drops-49593},
  doi =		{10.4230/LIPIcs.STACS.2015.19},
  annote =	{Keywords: social choice theory, economics, algorithms, theory}
}

Keywords: social choice theory, economics, algorithms, theory
Collection: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Issue Date: 2015
Date of publication: 26.02.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI