An optimization-based approach to ranking aggregation with weak order outputs

Abstract

Rank aggregation problems combine conflicting rankings of items into a single consensus ranking. In many applications, forcing all items into a strict order is too restrictive, since some items may be tied and placed in the same ordered group. This paper presents an optimization framework for rank aggregation problems in which the final ranking is a weak order, or bucket order. The framework uses binary variables to indicate whether one item is ranked before another or tied with it, and allows additional requirements to be added through linear constraints. We consider settings with an exact number of buckets, given bucket sizes, a ranking of the top items with the remaining items grouped in a final bucket, and fairness requirements for predefined groups in the upper part of the ranking. As a case study, we apply the framework to the Optimal Bucket Order Problem (OBOP), which we formulate for the first time as a mixed-integer linear programming problem. Experiments on benchmark instances derived from PrefLib and MovieLens evaluate the proposed formulation and its constrained versions. They also show that the new OBOP formulation allows us to confirm the optimality of most best-known heuristic solutions and improves some of them.

33 pages, 7 figures