1 Search Results for "Livieratos, John"


Document
Track A: Algorithms, Complexity and Games
Algorithmically Efficient Syntactic Characterization of Possibility Domains

Authors: Josep Díaz, Lefteris Kirousis, Sofia Kokonezi, and John Livieratos

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)


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 two-valued 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 non-dictatorial 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 component-wise 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.

Cite as

Josep Díaz, Lefteris Kirousis, Sofia Kokonezi, and John Livieratos. Algorithmically Efficient Syntactic Characterization of Possibility Domains. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 50:1-50:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{diaz_et_al:LIPIcs.ICALP.2019.50,
  author =	{D{\'\i}az, Josep and Kirousis, Lefteris and Kokonezi, Sofia and Livieratos, John},
  title =	{{Algorithmically Efficient Syntactic Characterization of Possibility Domains}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{50:1--50:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.50},
  URN =		{urn:nbn:de:0030-drops-106269},
  doi =		{10.4230/LIPIcs.ICALP.2019.50},
  annote =	{Keywords: collective decision making, computational social choice, judgment aggregation, logical relations, algorithm complexity}
}
  • Refine by Author
  • 1 Díaz, Josep
  • 1 Kirousis, Lefteris
  • 1 Kokonezi, Sofia
  • 1 Livieratos, John

  • Refine by Classification
  • 1 Theory of computation → Theory and algorithms for application domains

  • Refine by Keyword
  • 1 algorithm complexity
  • 1 collective decision making
  • 1 computational social choice
  • 1 judgment aggregation
  • 1 logical relations

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail