% Sample paper for COMSOC-2010
\documentclass{comsoc2010}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Specify your title and author names here:
\title{Paper Submissions to COMSOC-2010}
\author{Vincent Conitzer and J\"org Rothe\\
\footnotesize{Earlier versions by Ulle Endriss, Paul Goldberg, and J\'er\^ome Lang}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Page numbers are useful for submission, but need to be removed during 
% preparation of the camear-ready version. Remove the following line to 
% get rid of page numbers:
\pagestyle{plain}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Include a short abstract here (100-300 words):
\begin{abstract}
This short paper explains the formatting instructions for submissions
to the Third International Workshop on Computational Social Choice.
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Formatting Instructions}

Authors are invited to submit full papers not exceeding 12 pages, 
including references (roughly 5000 words). Each paper should include 
a title, the names and contact details of all authors, and an abstract 
of 100--300 words.

Please format your paper according to the following guidelines.
The most important requirements are (1)~that the submission should be 
formatted for A4 paper (that is, the page size as shown under 
\emph{Document Properties} in the Acrobat Reader, for instance, should 
be $8.27\times 11.69\,\mbox{in}$); and (2)~that the text should fit into 
an area of $5.5\times 8.5\,\mbox{in}$ ($14\times 21.6\,\mbox{cm}$). 
This excludes page numbers (which we suggest you include for the 
submission, but which must be removed for the camera-ready version in 
case of acceptance). Please use a 10pt typeface, with suitable deviations
for section headings, footnotes, etc. In general, please aim at having 
your paper look as close to this sample as possible. The easiest way of 
achieving this is to use the Latex document preparation system with the 
style file \texttt{comsoc2010.cls} provided at the workshop  website 
(take the file \texttt{sample.tex} as a starting point).

Papers not conforming to these guidelines will be accepted for review
(provided they are not excessively long), but in case of acceptance we
must insist that the guidelines be followed during preparation of the 
camera-ready version.  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{What is Computational Social Choice?}

Computational social choice \cite{ChevaleyreEtAlSOFSEM2007} is an 
interdisciplinary field of study at the interface of social choice theory 
and computer science, promoting an exchange of ideas in both directions. 
On the one hand, it is concerned with the application of techniques 
developed in computer science, such as complexity analysis or algorithm 
design, to the study of social choice mechanisms, such as voting procedures 
or fair division algorithms. On the other hand, computational social choice 
is concerned with importing concepts from social choice theory into computing. 
For instance, social welfare orderings originally developed to analyse the 
quality of resource allocations in human society are equally well applicable 
to problems in multiagent systems or network design.

Social choice theory is concerned with the design and analysis of methods for 
collective decision making. Examples include in particular voting protocols, 
but also procedures for fairly dividing a number of goods between several agents. 
Much classical work in the field has concentrated on establishing abstract 
results regarding the existence (or otherwise) of procedures meeting certain 
requirements, but such work has not usually taken computational issues into 
account. For instance, classical results in voting theory show that, under 
some weak and very natural conditions, it is impossible to design a voting 
protocol that voters cannot manipulate by reporting insincere preferences when 
casting their ballots. A voting system that induces such insincere voting 
behaviour cannot be expected to reliably return the socially most preferable 
candidate as a winner. In recent years, computer scientists have started to 
analyse this kind of problem from a computational point of 
view~\cite{fal-hem-hem-rot:b:richer}. The basic 
idea is that, should it be the case that manipulating successfully is a 
computationally intractable problem, then manipulability may be less of a worry.
Other applications of preference aggregation and collective decision
making include multiagent resource allocation, auctions, and prediction
markets, where strategic behaviour is again analysed both game-theoretically
and from a computational perspective~\cite{con:j:making-decisions}.

Another example for the application of tools typically used in computer science 
to problems stemming from economics and social choice is the use of logic for 
the formal specification and verification, or more generally analysis, of 
social procedures. In the same way as computer scientists have long been using 
logic to formally specify the behaviour of computer systems, so as to allow for 
the automatic verification of certain desirable properties of such systems, 
suitable logics may be used to specify social procedures such as voting 
protocols or fair division algorithms. This line of research is also known 
as ``social software''.

Known methods for collective decision making and classical results from 
social choice theory may not always be applicable when the number of 
alternatives from which to choose is large. This may, for instance, be 
the case when these alternatives have a combinatorial structure, as in 
negotiation over indivisible goods (where the number of bundles an agent 
may obtain is exponential in the number of goods) or committee elections 
(where the number of possible committees is exponential in the number 
of seats to be filled). For such combinatorial problems, the mere 
representation of the preferences of individuals over different 
alternatives becomes a non-trivial problem. A third example for work 
in computational social choice is then the application of techniques 
developed in artificial intelligence and logic for the compact 
representation of preferences to this kind of problem. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% References

\begin{thebibliography}{1}

\bibitem{ChevaleyreEtAlSOFSEM2007}
Y.~Chevaleyre, U.~Endriss, J.~Lang, and N.~Maudet. 
A Short Introduction to Computational Social Choice. 
In \emph{Proc.\ 33rd Conference on Current Trends in 
Theory and Practice of Computer Science (SOFSEM-2007)}, 
LNCS 4362, Springer-Verlag, 2007.

\bibitem{con:j:making-decisions}
V.~Conitzer.
\newblock Making decisions based on the preferences of multiple agents.
\newblock {\em Communications of the ACM}, 53(3):84--94, 2010.

\bibitem{fal-hem-hem-rot:b:richer}
P.~Faliszewski, E.~Hemaspaandra, L.~Hemaspaandra, and J.~Rothe.
\newblock A richer understanding of the complexity of election systems.
\newblock In S.~Ravi and S.~Shukla, editors, {\em Fundamental Problems in
  Computing: {Essays} in Honor of {Professor} {Daniel} {J.} {Rosenkrantz}},
  chapter~14, pages 375--406. Springer, 2009.

\end{thebibliography}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% At the very end of the paper, please include your contact details:

\begin{contact}
Vincent Conitzer\\
Department of Computer Science\\
Levine Science Research Center, Box 90129\\
Duke University\\
Durham, NC 27708, USA\\
\email{conitzer@cs.duke.edu}
\end{contact}

\begin{contact}
J\"org Rothe\\
Institut f\"ur Informatik\\
Heinrich-Heine-Universit\"at D\"usseldorf\\
Universit\"atsstr.~1\\
40225 D\"usseldorf, Germany\\
\email{rothe@cs.uni-duesseldorf.de}
\end{contact}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%