Axiomatics in Bioconsensus

William H. E. Day
Port Maitland, Nova Scotia, Canada

Bioconsensus is a rapidly evolving field in which consensus rules, having been developed for use in social choice theory, are adapted for use in areas such as systematic biology and evolutionary or molecular biology. Given a set of objects of interest, a basic problem of bioconsensus is to identify an appropriate consensus rule that, when presented a -tuple of objects of , returns from a unique consensus object that in some sense best represents ; if is the set of all hierarchical classifications or all partitions of a set, then the problem concerns finding a consensus of classifications. Solving this problem requires evaluating consensus rules in terms of the basic properties (axioms) that they satisfy. Sometimes one can obtain an impossibility result by listing a set of reasonable axioms that any consensus rule on should satisfy, then proving that no such rule can exist. Such a contradiction encourages one to explore how to weaken the axioms while maintaining the contradiction, or how to alter the axioms so as to remove the contradiction. Such analyses may yield characterizations of consensus rules in terms of axioms with which users may assess the appropriateness of the rules for given applications. Although the axiomatic approach may seem to be abstract and purely technical, its practical and concrete aspects enable one to discover what is realizable and what is not.

This short course explores how axiomatics can be used to investigate consensus rules in classification, clustering, and systematic biology. I describe how axiomatics can establish the nonexistence of suitable consensus rules and the existence of unique rules or families of rules. The rules discussed include majority, plurality, and median rules; the objects on which they act include partitions of a set, hierarchical structures, unrooted trees, and sequences. The course is introductory and assumes only that participants have a certain familiarity with mathematical reasoning, a certain capacity for abstract thought, and a certain interest in how mathematics is used to model aspects of biological problems.

Related Reading

W. H. E. DAY AND F. R. MCMORRIS, Axiomatic Consensus Theory in Group Choice and Biomathematics. Society for Industrial and Applied Mathematics, Philadelphia, Pennsylvania, 2003.

M. A. STEEL, A. W. M. DRESS, AND S. BSOCKER, Simple but fundamental limitations on supertree and consensus tree methods, Systematic Biology, 49(2000), pp. 363-368.