Díaz, Josep ;
Kirousis, Lefteris ;
Kokonezi, Sofia ;
Livieratos, John
Algorithmically Efficient Syntactic Characterization of Possibility Domains
Abstract
We call domain any arbitrary subset of a Cartesian power of the set {0,1} when we think of it as reflecting abstract rationality restrictions on vectors of twovalued judgments on a number of issues. In Computational Social Choice Theory, and in particular in the theory of judgment aggregation, a domain is called a possibility domain if it admits a nondictatorial aggregator, i.e. if for some k there exists a unanimous (idempotent) function F:D^k  > D which is not a projection function. We prove that a domain is a possibility domain if and only if there is a propositional formula of a certain syntactic form, sometimes called an integrity constraint, whose set of satisfying truth assignments, or models, comprise the domain. We call possibility integrity constraints the formulas of the specific syntactic type we define. Given a possibility domain D, we show how to construct a possibility integrity constraint for D efficiently, i.e, in polynomial time in the size of the domain. We also show how to distinguish formulas that are possibility integrity constraints in linear time in the size of the input formula. Finally, we prove the analogous results for local possibility domains, i.e. domains that admit an aggregator which is not a projection function, even when restricted to any given issue. Our result falls in the realm of classical results that give syntactic characterizations of logical relations that have certain closure properties, like e.g. the result that logical relations componentwise closed under logical AND are precisely the models of Horn formulas. However, our techniques draw from results in judgment aggregation theory as well from results about propositional formulas and logical relations.
BibTeX  Entry
@InProceedings{daz_et_al:LIPIcs:2019:10626,
author = {Josep D{\'i}az and Lefteris Kirousis and Sofia Kokonezi and John Livieratos},
title = {{Algorithmically Efficient Syntactic Characterization of Possibility Domains}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {50:150:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10626},
URN = {urn:nbn:de:0030drops106269},
doi = {10.4230/LIPIcs.ICALP.2019.50},
annote = {Keywords: collective decision making, computational social choice, judgment aggregation, logical relations, algorithm complexity}
}
04.07.2019
Keywords: 

collective decision making, computational social choice, judgment aggregation, logical relations, algorithm complexity 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

04.07.2019 