Computational social choice meets databases

Benny Kimelfeld, Phokion G. Kolaitis, Julia Stoyanovich

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    We develop a novel framework that aims to create bridges between the computational social choice and the database management communities. This framework enriches the tasks currently supported in computational social choice with relational database context, thus making it possible to formulate sophisticated queries about voting rules, candidates, voters, issues, and positions. At the conceptual level, we give rigorous semantics to queries in this framework by introducing the notions of necessary answers and possible answers to queries. At the technical level, we embark on an investigation of the computational complexity of the necessary answers. In particular, we establish a number of results about the complexity of the necessary answers of conjunctive queries involving the plurality rule that contrast sharply with earlier results about the complexity of the necessary winners under the plurality rule.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI 2018
    EditorsJerome Lang
    PublisherInternational Joint Conferences on Artificial Intelligence
    Pages317-323
    Number of pages7
    ISBN (Electronic)9780999241127
    DOIs
    StatePublished - 2018
    Event27th International Joint Conference on Artificial Intelligence, IJCAI 2018 - Stockholm, Sweden
    Duration: Jul 13 2018Jul 19 2018

    Publication series

    NameIJCAI International Joint Conference on Artificial Intelligence
    Volume2018-July
    ISSN (Print)1045-0823

    Other

    Other27th International Joint Conference on Artificial Intelligence, IJCAI 2018
    Country/TerritorySweden
    CityStockholm
    Period7/13/187/19/18

    ASJC Scopus subject areas

    • Artificial Intelligence

    Fingerprint

    Dive into the research topics of 'Computational social choice meets databases'. Together they form a unique fingerprint.

    Cite this