A linear ordering problem of sets

Periodical
Annals of Operations Research
Volume
288
Year
2020
Issue number
1
Page range
45-64
Relates to study/studies
PISA 2012

A linear ordering problem of sets

Abstract

Given a ranking of elements of a set and given a disjoint partition of the same set, the ranking does not generally imply a total order of the partition. In this paper, we introduce the Kendall-tau partition ranking, a linear order of the subsets of the partition which follows from the given ranking. We prove that, under certain assumptions, the Kendall-tau partition ranking is robust, in the sense that it remains the same when removing subsets of the partition. Then, we give several results (properties) concerning the adequacy of the ranking for ordering the partition and we prove that the integrality gap of the 0-1 problem associated to the Kendall-tau partition ranking tends to 8/7. Additionally, we provide a comparison of the new ranking with respect to the mean and median based scores from a theoretical and empirical point of view. Finally, a real application with data from the Programme for International Student Assessment is presented, where countries are ordered based on their school rankings.