Efficient Rank Aggregation from Pairwise Comparisons

Rank aggregation is a widely applicable task in various domains, including voting, gaming, and recommendation systems. It involves combining pairwise or listwise comparisons to generate a unified ranking.
This topic has a long history and is still relevant today: it dates back to democratic voting systems in Ancient Greece; it was modeled in psychology experiments in the last century, and it is the cornerstone of reinforcement learning with human feedback (RLHF) in large language model (LLM) fine-tuning to produce high quality output aligned with human values. In the era of big data, with an abundance of available data, there is a growing need for efficient and accurate analysis to uncover hidden knowledge.

Motivated by the inefficiencies during usage and acquisition of data from multiple sources with different levels of quality during rank aggregation, this work aims to address the challenges of efficiently and accurately dealing with heterogeneous data sources in multiple scenarios.

First of all we propose a novel model that originates from the Random Utility Model (RUM) to take account of the heterogeneity of data sources. Next, we devised an active ranking algorithm that works not only for the proposed model but also for a wider class of models that in the family of Strong Stochastic Transitivity (SST) models.

Noted by the inefficiency of the active ranking algorithm above for Weak Stochastic Transitivity (WST) models that are more prevalent in real-world scenarios, we further propose a new variant of the active ranking algorithm that is able to handle WST models. Following this work, we provide the heterogeneous variant of this algorithm that also efficiently aggregates from multiple data sources setting.

Active ranking techniques aim to minimize the number of samples needed to generate an aggregated ranking by strategically selecting data based on existing information and rankings.

If the objective of the algorithm is both to rank items and to collect rewards such as on online shopping platforms where the seller is interested in both collecting the revenue and figuring out the best seller, the ranking problem can be formulated as a dueling bandits problem. This work further covers this case by considering several generalized linear models that contains variable data source quality. We first fill the void of lack of Borda score bandits in the field by proposing a new variant of the dueling bandits algorithm that is able to handle Borda score. This work is further extended to the variance-aware Borda score dueling bandits that is able to handle the heterogeneous data sources setting. The proposed methods achieve nearly optimal regret for this class of problems.