Majority Decisions and Transitivity: Some Special Cases

Abstract

The problem considered is that of obtaining majority decisions which are transitive. We show that the corresponding optimization problems for the weighted l 1 norm and the weighted l 2 norm are identical. We then show that she general problem of minimizing the weighted l k norm can be equivalently formulated as a set covering problem. Finally, we identify the Tchebycheff problem ( l 2 norm) with a class, of bottleneck quadratic assignment problems and give an efficient algorithm for solving it.