Miguel Couceiro (Universite de Lorraine, France), Impossibility theorems over median algebras and beyond

Tue, 9 Nov 2021, 1 pm MST

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.