Geb. 20.14, R 103.1

05. Nov 2013

Prof. Arkadii Slinko, University of Auckland

15:45 - 17:15

Suppose that we have a family of linear orders on a finite set C. A subset of C which is ranked consecutively (though possibly in different order) in all linear orders is called a clone set. All clone sets for a given family of linear orders form a clone structure. In this paper we formalise and study properties of clone structures. In particular, we give an axiomatic characterisation of clone structures, relate them to PQ-trees, define the composition of those, classify irreducible ones, and show that it is sufficient to have only three linear orders to realise any clone structure. We also discuss clone structures implementable by single-peaked and single-crossing profiles.

In applications, a set of linear orders is normally interpreted as opinions of voters about candidates in C. Cloning candidates (products) is one of the most sophisticated tools of manipulation of elections (consumer surveys). Unfortunately most common voting rules are vulnerable to this method of manipulation. So clones do matter.

This is a joint work with Piotr Faliszewski (Krakow) and Edith Elkind (Oxford).