Home

Handbook of Computational Social Choice

Edited by Felix Brandt, Vincent Conitzer, Ulle Endriss,

Jérôme Lang, and Ariel Procaccia

Outline deadline: January 1st 2013

Draft deadline: May 1st 2013

Full chapter deadline: July 25th 2014

Reviews due: September 30th 2014

Final chapters due: November 30th 2014

General guidelines

• A book chapter should be seen as an accessible introduction to the respective area as well as a reference that provides an overview of the state of the art and pointers to related work.
• We encourage the authors to use examples and illustrations whenever possible.
• The most central concepts of an area should be defined formally.
• Depending on the topic, a chapter may contain some formal proofs or no proofs at all. Some chapters may benefit from including the proof of central results for didactical reasons. In general, however, the inclusion of proofs is most helpful when they are slightly different from the ones already appearing in the literature, either in being more accessible or providing a somewhat different viewpoint.
• We assume the reader to be able to read pseudocode and follow simple hardness proofs. An excessive number of hardness proofs in a single chapter should be avoided. If possible, more emphasis should be given to positive results, i.e., efficient algorithms.
• We will give informal explanations of P, NP, coNP, #P, reductions, fixed-parameter tractability, linear programming, integer linear programming, etc. and provide links to textbooks with further information in an appendix.
• Chapters should have *no* abstracts.

Terminology, notation, and LaTeX

The terms "agent" and "voter", "alternative" and "candidate", and "social choice function (SCF)" and "voting rule" can be used interchangeably. SCFs (or voting rules) are by default assumed to be irresolute, i.e., they return a non-empty set of alternatives (or candidates). A resolute SCF (or voting rule) always returns a singleton. You are encouraged to adhere to the following notation for the sake of consistency.

• Set of voters (or agents): $N={1,\dots,n}$
• Set of alternatives (or candidates): $A$, $|A|=m$
• Preference relation of voter $i$: $\succsim_i$ with strict part $\succ_i$ and indifference part $\sim_i$
• Set of all preference relations (transitive and complete) over a given set of alternatives A: $\mathcal{R}(A)$
• Set of all linear orders (transitive, complete, and antisymmetric) over a given set of alternatives A: $\mathcal{L}(A)$
• Preference profile: R=(\succsim_1,\dots,\succsim_n) (this allows us to use \succsim for a social preference relation such as for SWFs, Kemeny's rule, or the majority relation)
• Majority graph: (A,\succ), weak majority graph: (A,\succsim)

Chapters should be at most 25 pages (excluding references).

Please use the LaTeX template called “cambridge6Atight” available from this CUP website:

http://authornet.cambridge.org/information/productionguide/laTex_files/

Please use \usepackage[round]{natbib} with \bibliographystyle{abbrvnat} and cite papers using \citet and \citep.

Example chapter header:

\alphafootnotes

\author[V\, Conitzer and T\, Walsh]

{Vincent Conitzer\footnotemark and Toby Walsh\footnotemark}

\chapterauthor{Vincent Conitzer\footnotemark\

and Toby Walsh\footnotemark}

\chapter{Barriers to Manipulation}

\footnotetext[1]{Department of Computer Science, Duke University, USA}

\footnotetext[2]{NICTA and Department of Computer Science and

Engineering, University of New South Wales, Australia}

\arabicfootnotes

\contributor{Vincent Conitzer

\affiliation{Department of Computer Science, Duke University, USA}}

\contributor{Toby Walsh

\affiliation{NICTA and Department of Computer Science and

Engineering, University of New South Wales, Australia}}

How to cite other chapters:

Other chapters of this handbook should be cited by referring to the (hard-coded) chapter number followed by a reference. Example:

As seen in Chapter~1 \citep{ZwickerChapter}, May's Theorem shows that a number of rather weak and intuitively acceptable principles completely characterize majority rule.

Bibtex entries for all book chapters can be found below.

@InCollection{IntroChapter,

author = {Felix Brandt and Vincent Conitzer and Ulle Endriss

and J{\'e}r{\^o}me Lang and Ariel D.~Procaccia},

title = {Introduction to Computational Social Choice},

booktitle = {Handbook of Computational Social Choice},

publisher = {Cambridge University Press},

year = {2015},

editor = {F. Brandt and V. Conitzer and U. Endriss and J. Lang

and A. D. Procaccia},

chapter = {1}

}

@InCollection{ZwickerChapter,

author = {William S.~Zwicker},

title = {Introduction to the Theory of Voting},

booktitle = {Handbook of Computational Social Choice},

publisher = {Cambridge University Press},

year = {2015},

editor = {F. Brandt and V. Conitzer and U. Endriss and J. Lang

and A. D. Procaccia},

chapter = {2}

}

@InCollection{BrandtEtAlChapter,

author = {Felix Brandt and Markus Brill and Paul Harrenstein},

title = {Tournament Solutions},

booktitle = {Handbook of Computational Social Choice},

publisher = {Cambridge University Press},

year = {2015},

editor = {F. Brandt and V. Conitzer and U. Endriss and J. Lang

and A. D. Procaccia},

chapter = {3}

}

@InCollection{FischerEtAlChapter,

author = {Felix Fischer and Olivier Hudry and Rolf Niedermeier},

title = {Weighted Tournament Solutions},

booktitle = {Handbook of Computational Social Choice},

publisher = {Cambridge University Press},

year = {2015},

editor = {F. Brandt and V. Conitzer and U. Endriss and J. Lang

and A. D. Procaccia},

chapter = {4}

}

@InCollection{CaragiannisEtAlChapter,

author = {Ioannis Caragiannis and Edith Hemaspaandra and Lane

A.~Hemaspaandra},

title = {Dodgson's Rule and {Y}oung's Rule},

booktitle = {Handbook of Computational Social Choice},

publisher = {Cambridge University Press},

year = {2015},

editor = {F. Brandt and V. Conitzer and U. Endriss and J. Lang

and A. D. Procaccia},

chapter = {5}

}

@InCollection{ConitzerWalshChapter,

author = {Vincent Conitzer and Toby Walsh},

title = {Barriers to Manipulation in Voting},

booktitle = {Handbook of Computational Social Choice},

publisher = {Cambridge University Press},

year = {2015},

editor = {F. Brandt and V. Conitzer and U. Endriss and J. Lang

and A. D. Procaccia},

chapter = {6}

}

@InCollection{FaliszewskiRotheChapter,

author = {Piotr Faliszewski and J{\"o}rg Rothe},

title = {Control and Bribery in Voting},

booktitle = {Handbook of Computational Social Choice},

publisher = {Cambridge University Press},

year = {2015},

editor = {F. Brandt and V. Conitzer and U. Endriss and J. Lang

and A. D. Procaccia},

chapter = {7}

}

@InCollection{ElkindSlinkoChapter,

author = {Edith Elkind and Arkadii Slinko},

title = {Rationalizations of Voting Rules},

booktitle = {Handbook of Computational Social Choice},

publisher = {Cambridge University Press},

year = {2015},

editor = {F. Brandt and V. Conitzer and U. Endriss and J. Lang

and A. D. Procaccia},

chapter = {8}

}

@InCollection{LangXiaChapter,

author = {J{\'e}r{\^o}me Lang and Lirong Xia},

title = {Voting in Combinatorial Domains},

booktitle = {Handbook of Computational Social Choice},

publisher = {Cambridge University Press},

year = {2015},

editor = {F. Brandt and V. Conitzer and U. Endriss and J. Lang

and A. D. Procaccia},

chapter = {9}

}

@InCollection{BoutilierRosenscheinChapter,

author = {Craig Boutilier and Jeffrey Rosenschein},

title = {Incomplete Information and Communication in Voting},

booktitle = {Handbook of Computational Social Choice},

publisher = {Cambridge University Press},

year = {2015},

editor = {F. Brandt and V. Conitzer and U. Endriss and J. Lang

and A. D. Procaccia},

chapter = {10}

}

@InCollection{ThomsonChapter,

author = {William Thomson},

title = {Introduction to the Theory of Fair Allocation},

booktitle = {Handbook of Computational Social Choice},

publisher = {Cambridge University Press},

year = {2015},

editor = {F. Brandt and V. Conitzer and U. Endriss and J. Lang

and A. D. Procaccia},

chapter = {11}

}

@InCollection{BouveretEtAlChapter,

author = {Sylvain Bouveret and Yann Chevaleyre and Nicolas Maudet},

title = {Fair Allocation of Indivisible Goods},

booktitle = {Handbook of Computational Social Choice},

publisher = {Cambridge University Press},

year = {2015},

editor = {F. Brandt and V. Conitzer and U. Endriss and J. Lang

and A. D. Procaccia},

chapter = {12}

}

@InCollection{ProcacciaChapter,

author = {Ariel D.~Procaccia},

title = {Cake Cutting Algorithms},

booktitle = {Handbook of Computational Social Choice},

publisher = {Cambridge University Press},

year = {2015},

editor = {F. Brandt and V. Conitzer and U. Endriss and J. Lang

and A. D. Procaccia},

chapter = {13}

}

@InCollection{KlausEtAlChapter,

author = {Bettina Klaus and David Manlove and Francesca Rossi},

title = {Matching under Preferences},

booktitle = {Handbook of Computational Social Choice},

publisher = {Cambridge University Press},

year = {2015},

editor = {F. Brandt and V. Conitzer and U. Endriss and J. Lang

and A. D. Procaccia},

chapter = {14}

}

@InCollection{AzizSavaniChapter,

author = {Haris Aziz and Rahul Savani},

title = {Hedonic Games},

booktitle = {Handbook of Computational Social Choice},

publisher = {Cambridge University Press},

year = {2015},

editor = {F. Brandt and V. Conitzer and U. Endriss and J. Lang

and A. D. Procaccia},

chapter = {15}

}

@InCollection{ChalkiadakisWooldridgeChapter,

author = {Georgios Chalkiadakis and Michael Wooldridge},

title = {Weighted Voting Games},

booktitle = {Handbook of Computational Social Choice},

publisher = {Cambridge University Press},

year = {2015},

editor = {F. Brandt and V. Conitzer and U. Endriss and J. Lang

and A. D. Procaccia},

chapter = {16}

}

@InCollection{EndrissChapter,

author = {Ulle Endriss},

title = {Judgment Aggregation},

booktitle = {Handbook of Computational Social Choice},

publisher = {Cambridge University Press},

year = {2015},

editor = {F. Brandt and V. Conitzer and U. Endriss and J. Lang

and A. D. Procaccia},

chapter = {17}

}

@InCollection{TennenholtzZoharChapter,

author = {Moshe Tennenholtz and Aviv Zohar},

title = {The Axiomatic Approach and the {I}nternet},

booktitle = {Handbook of Computational Social Choice},

publisher = {Cambridge University Press},

year = {2015},

editor = {F. Brandt and V. Conitzer and U. Endriss and J. Lang

and A. D. Procaccia},

chapter = {18}

}

@InCollection{VassilevskaWilliamsChapter,

author = {Virginia Vassilevska-Williams},

title = {Knockout Tournaments},

booktitle = {Handbook of Computational Social Choice},

publisher = {Cambridge University Press},

year = {2015},

editor = {F. Brandt and V. Conitzer and U. Endriss and J. Lang

and A. D. Procaccia},

chapter = {19}

}