Keynote Speech: Computational Social Choice and
Incomplete Information – Abstract
Phokion G. Kolaitis1
1
    University of California Santa Cruz and IBM Research, Santa Cruz, CA 95064, USA


                                         Abstract
                                         Computational social choice is an interdisciplinary field that studies collective decision-making from an
                                         algorithmic perspective. Determining the winners under various voting rules is a mainstream area of
                                         research in computational social choice. Such rules assume that the voters provide complete information
                                         about their preferences, an assumption that is often unrealistic because typically only partial preference
                                         information is available. This state of affairs has motivated the study of the notions of the necessary
                                         winners and the possible winners with respect to a variety of voting rules.
                                             In the first part of the talk, we will present an overview of results about the complexity of winner de-
                                         termination under incomplete information. In the second part of the talk, we will discuss the framework
                                         of election databases, a new framework that aims to create bridges between the computational social
                                         choice and the data management communities. An election database contains incomplete information
                                         about the preferences of voters (in the form of partial orders), alongside with standard database relations
                                         that provide contextual information. The availability of relational context enables the formulation of
                                         sophisticated queries about voting rules, candidates, winners, issues, and positions on issues. We will
                                         introduce the semantics of queries on election databases and explore their computational complexity.

                                         Keywords
                                         voting rules, complexity of winner determination under incomplete information, queries on election
                                         databases




SEBD 2021: The 29th Italian Symposium on Advanced Database Systems, September 5-9, 2021, Pizzo Calabro (VV),
Italy
" kolaitis@ucsc.edu (P. G. Kolaitis)
                                       © 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
    CEUR
    Workshop
    Proceedings
                  http://ceur-ws.org
                  ISSN 1613-0073       CEUR Workshop Proceedings (CEUR-WS.org)