Dear all,

The next Computational Social Choice Seminar at the ILLC will take place on Monday at 15:00. It will be delivered by Lefteris Kirousis (Athens), who is going to be visiting for the day. He will speak about possibility results in judgment aggregation. I'm including the abstract below.

As always, for more information on the COMSOC Seminar please consult http://www.illc.uva.nl/~ulle/seminar/.

All the best, Ulle

-------------------------------------------------------------------------

Speaker: Lefteris Kirousis (Athens) Title: Abstract Possibility Domains: Algorithms and Characterizations Date: Monday 1 July 2019 Time: 15:00 Location: ILLC Room F1.15, Science Park 107, Amsterdam

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.