×

Algorithmically efficient syntactic characterization of possibility domains. (English) Zbl 1452.91133

Summary: In the field of judgment aggregation, a domain, that is a subset of a Cartesian power of \(\{0,1\}\), is considered to reflect abstract rationality restrictions on vectors of two-valued judgments on a number of issues. We are interested in the ways we can aggregate the positions of a set of individuals, whose positions over each issue form vectors of the domain, by means of unanimous (idempotent) functions, whose output is again an element of the domain. Such functions are called non-dictatorial, when their output is not simply the positions of a single individual. Here, we consider domains admitting various kinds of non-dictatorial aggregators, which reflect various properties of majority aggregation: (locally) non-dictatorial, generalized dictatorships, anonymous, monotone, StrongDem and systematic. We show that interesting and, in some sense, democratic voting schemes are always provided by domains that can be described by propositional formulas of specific syntactic types we define. Furthermore, we show that we can efficiently recognize such formulas and that, given a domain, we can both efficiently check if it is described by such a formula and, in case it is, construct it. Our results fall in the realm of classical results concerning the syntactic characterization of domains with specific closure properties, like domains closed under logical AND which are the models of Horn formulas. The techniques we use to obtain our results draw from judgment aggregation as well as propositional logic and universal algebra.

MSC:

91B14 Social choice
91B06 Decision theory
91B86 Mathematical economics and fuzziness
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] Elmar B¨ohler, Nadia Creignou, Steffen Reith, and Heribert Vollmer. Playing with Boolean blocks, part I: Post’s lattice with applications to complexity theory. InSIGACT News. Citeseer, 2003.
[2] Elmar B¨ohler, Nadia Creignou, Steffen Reith, and Heribert Vollmer. Playing with Boolean blocks, part II: Constraint satisfaction problems. InACM SIGACT-Newsletter. Citeseer, 2004.
[3] Andrei A Bulatov. Conservative constraint satisfaction re-revisited.Journal of Computer and System Sciences, 82(2):347-356, 2016. · Zbl 1346.68108
[4] Fabrizio Cariani, Marc Pauly, and Josh Snyder. Decision framing in judgment aggregation.Synthese, 163(1):1- 24, 2008. · Zbl 1140.91334
[5] Nadia Creignou and J-J H´ebrard. On generating all solutions of generalized satisfiability problems.RAIROTheoretical Informatics and Applications, 31(6):499-511, 1997. · Zbl 0901.68075
[6] Rina Dechter and Judea Pearl. Structure identification in relational data.Artificial Intelligence, 58(1-3):237- 270, 1992. · Zbl 0782.68095
[7] Alvaro del Val. On 2-sat and renamable Horn. InProceedings of the National Conference on Artificial Intelligence, pages 279-284. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2000.
[8] Josep D´ıaz, Lefteris M. Kirousis, Sofia Kokonezi, and John Livieratos. Algorithmically efficient syntactic characterization of possibility domains. In46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece., pages 50:1-50:13, 2019. URL:https://doi. org/10.4230/LIPIcs.ICALP.2019.50,doi:10.4230/LIPIcs.ICALP.2019.50. · Zbl 07561543
[9] Franz Dietrich. A generalised model of judgment aggregation.Social Choice and Welfare, 28(4):529-565, 2007. · Zbl 1180.91105
[10] Franz Dietrich and Christian List. Arrow’s theorem in judgment aggregation.Social Choice and Welfare, 29(1):19-33, 2007. · Zbl 1138.91019
[11] Elad Dokow and Ron Holzman. Aggregation of binary evaluations for truth-functional agendas.Social Choice and Welfare, 32(2):221-241, 2009. · Zbl 1170.91011
[12] Elad Dokow and Ron Holzman. Aggregation of binary evaluations.Journal of Economic Theory, 145(2):495- 511, 2010. · Zbl 1238.91059
[13] Ramez Elmasri and Sham Navathe.Fundamentals of database systems. Pearson London, 2016. · Zbl 1058.68046
[14] Herbert B. Enderton.A mathematical introduction to logic. Elsevier, 2001. · Zbl 0992.03001
[15] Ulle Endriss and Ronald de Haan. Complexity of the winner determination problem in judgment aggregation: Kemeny, slater, tideman, young. InProceedings of the 2015 International Conference on Autonomous Agents
[16] Ulle Endriss, Umberto Grandi, Ronald De Haan, and J´erˆome Lang. Succinctness of languages for judgment aggregation. InFifteenth International Conference on the Principles of Knowledge Representation and Reasoning, 2016.
[17] Umberto Grandi and Ulle Endriss. Binary aggregation with integrity constraints. InIJCAI ProceedingsInternational Joint Conference on Artificial Intelligence, volume 22, page 204, 2011. · Zbl 1284.91138
[18] Umberto Grandi and Ulle Endriss. Lifting integrity constraints in binary aggregation.Artificial Intelligence, 199:45-66, 2013. · Zbl 1284.91138
[19] Peter Jeavons and David Cohen. An algebraic characterization of tractable constraints. InInternational Computing and Combinatorics Conference, pages 633-642. Springer, 1995.
[20] Peter Jeavons, David Cohen, and Marc Gyssens. How to determine the expressive power of constraints. Constraints, 4(2):113-131, 1999. · Zbl 0951.68190
[21] Lefteris Kirousis, Phokion G Kolaitis, and John Livieratos. On the computational complexity of non-dictatorial aggregation. InProceedings 17th International Conference on Relational and Algebraic Methods in Computer Science. Springer, 2018. For an extended version, seehttps://arxiv.org/abs/1711.01574v2. · Zbl 1518.68143
[22] Lefteris Kirousis, Phokion G Kolaitis, and John Livieratos. Aggregation of votes with multiple positions on each issue.ACM Transactions on Economics and Computation (TEAC), 7(1):1, 2019. · Zbl 1486.91035
[23] G´abor Kun and Mario Szegedy. A new line of attack on the dichotomy conjecture.European Journal of Combinatorics, 52:338-367, 2016. · Zbl 1327.05183
[24] J´erˆome Lang, Marija Slavkovik, and Srdjan Vesic. Agenda separability in judgment aggregation. InThirtieth AAAI Conference on Artificial Intelligence, 2016.
[25] Harry R Lewis. Renaming a set of clauses as a Horn set.Journal of the ACM (JACM), 25(1):134-135, 1978. ALGORITHMICALLY EFFICIENT SYNTACTIC CHARACT. OF POSSIBILITY DOMAINS135 · Zbl 0365.68082
[26] Christian List. The theory of judgment aggregation: An introductory review.Synthese, 187(1):179-207, 2012. · Zbl 1275.91049
[27] Klaus Nehring and Clemens Puppe. Abstract arrowian aggregation.Journal of Economic Theory, 145(2):467- 494, 2010. · Zbl 1238.91062
[28] Gabriella Pigozzi. Belief merging and the discursive dilemma: an argument-based account to paradoxes of judgment aggregation.Synthese, 152(2):285-298, 2006. · Zbl 1112.03305
[29] Emil Leon Post.The two-valued iterative systems of mathematical logic. Number 5 in Annals of Mathematics Studies. Princeton University Press, 1941. · Zbl 0063.06326
[30] Willard V Quine. On cores and prime implicants of truth functions.The American Mathematical Monthly, 66(9):755-760, 1959. · Zbl 0201.32203
[31] Thomas J. Schaefer. The complexity of satisfiability problems. InProc. of the 10th Annual ACM Symp. on Theory of Computing, pages 216-226, 1978. · Zbl 1282.68143
[32] Larry J Stockmeyer. The polynomial-time hierarchy.Theoretical Computer Science, 3(1):1-22, 1976. · Zbl 0353.02024
[33] Mario Szegedy and Yixin Xu. Impossibility theorems and the universal algebraic toolkit.CoRR, abs/1506.01315, 2015. URL:http://arxiv.org/abs/1506.01315.
[34] ´Agnes Szendrei.Clones in universal algebra, volume 99. Presses de l’Universit´e de Montr´eal, 1986. · Zbl 0603.08004
[35] Robert Endre Tarjan. Depth-first search and linear graph algorithms.SIAM J. Comput., 1(2):146-160, 1972. · Zbl 0251.05107
[36] Robert Wilson. On the theory of aggregation.Journal of Economic Theory, 10(1):89-99, 1975. · Zbl 0311.90008
[37] Susumu Yamasaki and Shuji Doshita. The satisfiabilty problem for a class consisting of Horn sentences and some non-Horn sentences in proportional logic.Information and Control, 59(1-3):1-12, 1983. · Zbl 0564.03010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.