CONTEXTUAL RANKING AND MATCHING. OPTIMAL REGRET UNDER LST

We address the problem of online matchmaking with contextual information. In each round, a perfect matching between a varying set of players -- with different strengths -- is selected, and the outcomes of the comparisons of the chosen pairs are observed. We assume that matching players incurs dissatisfaction proportional to the "strength gap", thereby incentivising the pairing of players with closely matched strengths. Additionally, we assume that the strength of each player can be inferred from some available contextual information through the contextualised linear stochastic transitivity model \textbf{(LST)}. We propose an algorithm that performs matchmaking by selecting pairs of maximum informativeness among admissible pairs and prove that its regret is optimal up to logarithmic factors.