Impossibility theorems over median algebras and beyond

Abstract: In this presentation we consider aggregation procedures (consensus functions) over median algebras (ternary algebras that subsume several ordered structures such as distributive lattices as well as several combinatorial structures such as median graphs). Our starting point is a recent Arrow type impossibility result that states that any median preserving consensus function over linearly ordered sets is trivial in the sense that it only depends on a single argument. In view of this result, a natural problem is then to identify those median algebras that lead to such impossibility results. In particular, we will show that such impossibility results are inevitable when the codomain contains no cycle, i.e., it is a "tree", and we will provide a surprisingly simple condition that completely describes the latter as median algebras. To broaden the talk, we will also present some recent results that answer the parametrized version of this problem in which dependence is restricted to k arguments. We will conclude by observing that the underlying property to proving such results is that of congruence distributivity, which naturally raises the question whether these results extend to other varieties of algebras, e.g., congruence modular varieties.

computational complexitycategory theorylogic

Audience: researchers in the topic

PALS Panglobal Algebra and Logic Seminar

Series comments: The PALS seminar is a research and learning seminar organized by the algebra and logic research group of the Department of Mathematics at the University of Colorado at Boulder. The scope of the seminar includes all topics with links to algebra, logic, or their applications, like general algebra, logic, model theory, category theory, set theory, set-theoretic topology, or theoretical computer science. Please contact one of the organizers for the Zoom password, to join the mailing list or if you want to speak.