CONTEXTUAL RANKING AND MATCHING. OPTIMAL REGRET UNDER LST

Hafedh El Ferchichi, Vianney Perchet, Matthieu LERASLE
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:4609-4617, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-el-ferchichi26a, title = { CONTEXTUAL RANKING AND MATCHING. OPTIMAL REGRET UNDER LST }, author = {El Ferchichi, Hafedh and Perchet, Vianney and LERASLE, Matthieu}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {4609--4617}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/el-ferchichi26a/el-ferchichi26a.pdf}, url = {https://proceedings.mlr.press/v300/el-ferchichi26a.html}, abstract = { 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. } }
Endnote
%0 Conference Paper %T CONTEXTUAL RANKING AND MATCHING. OPTIMAL REGRET UNDER LST %A Hafedh El Ferchichi %A Vianney Perchet %A Matthieu LERASLE %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-el-ferchichi26a %I PMLR %P 4609--4617 %U https://proceedings.mlr.press/v300/el-ferchichi26a.html %V 300 %X 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.
APA
El Ferchichi, H., Perchet, V. & LERASLE, M.. (2026). CONTEXTUAL RANKING AND MATCHING. OPTIMAL REGRET UNDER LST . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:4609-4617 Available from https://proceedings.mlr.press/v300/el-ferchichi26a.html.

Related Material