How Many Repeated Pairwise Comparisons Are Needed for Ranking under Heterogeneity?
This study investigates how many repeated pairwise comparisons are needed per user-task context to recover model rankings when user preferences vary widely across different users and tasks. It shows that while naive methods require many comparisons, improved algorithms can achieve ranking recovery with only logarithmic dependence on the inverse of the utility gap, proving this logarithmic dependence is optimal.