Talk by Prof. William S Zwicker (Union College): Aggregating Binary Relations: Computational Complexity & Orthogonal Decomposition

The mathematical study of voting dates back at least to the time of Condorcet and de Borda during the French Revolution. Over the intervening centuries, a diverse collection of voting rules have been proposed, using a variety of different ballot forms (inputs) to make collective decisions (outputs) of distinct kinds: which single candidate won, how should all candidates be ranked, which parliament should be seated, etc. These differences among input and output forms might seem to complicate the job of comparing one rule to another. However, if we encode inputs and outputs as types of binary relations (equivalence relations, weak orders, digraphs with no cycles, . . .) we can see a large subclass of aggregation rules (going beyond voting rules) as restrictions of one highly general aggregation mechanism. Under this view, differences among rules arise solely from four different types of information used or suppressed in the restriction prior to aggregation. In particular, two of these information types require NP-hard aggregation algorithms, while rules that aggregate only information from the other two types can be aggregated via polynomial-time algorithms. These four information types correspond to a decomposition of the linear space spanned by all binary relations into four orthogonal and complementary subspaces.

William S Zwicker is the William D Williams Professor of Mathematics at Union College, in New York. His original training was in logic and set theory, and more recent scholarship has been in the mathematical social sciences: social choice theory, cooperative game theory, and fair division.