1 July 2019, Computational Social Choice Seminar, Lefteris Kirousis

Abstract

Let V be a set of possible evaluations on an issue, with cardinality two or possibly greater. An abstract domain (or just domain) is an arbitrary subset D of a Cartesian power V^m. The elements of a domain are considered to represent the rational, or permissible, evaluation vectors on m issues, in some abstract sense of rationality. Given an integer k>1, a k-ary aggregator for D is a function F defined for all elements of D^k and taking values in D. We assume that aggregators are defined independently on each issue and that they are supportive. An aggregator F is called non-dictatorial if it differs from all projection functions on any d in 1..k. A domain D is called a possibility domain if it admits a non-dictatorial aggregator of some arity k. I will first give necessary and sufficient conditions for D to be a possibility domain in terms of existence of binary or ternary aggregators. Using this characterization as a stepping stone, I will give efficient (polynomial time in the size of the domain) algorithms that decide whether an input domain is a possibility one. Finally in the case the cardinality of V is exactly two (Boolean case), I will define a class of Conjunctive Normal Form formulas of Propositional Logic that describe the domains that are possibility ones. I will also prove that such formulas are recognizable in linear time in the size of the input formula.

For more information on the Computational Social Choice Seminar, please consult https://staff.science.uva.nl/u.endriss/seminar/.