Active Ranking and Matchmaking, with Perfect Matchings

Hafedh El Ferchichi, Matthieu Lerasle, Vianney Perchet
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:13460-13480, 2024.

Abstract

We address the challenge of actively ranking a set of items/players with varying values/strengths. The comparison outcomes are random, with a greater noise the closer the values. A crucial requirement is that, at each iteration of the algorithm, all items must be compared once, i.e., an iteration is a perfect matching. Furthermore, we presume that comparing two players with closely matched strengths incurs no cost and, in contrast, a unit cost is associated with comparing players whose strength difference is more substantial. Our secondary objective is to determine an optimal matching between players based on this cost function: we propose and analyze an algorithm that draws on concepts from both AKS sorting networks and bandit theory. Our algorithm achieves both objectives with high probability, and the total cost is optimal (up to logarithmic terms).

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-ferchichi24a, title = {Active Ranking and Matchmaking, with Perfect Matchings}, author = {Ferchichi, Hafedh El and Lerasle, Matthieu and Perchet, Vianney}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {13460--13480}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/ferchichi24a/ferchichi24a.pdf}, url = {https://proceedings.mlr.press/v235/ferchichi24a.html}, abstract = {We address the challenge of actively ranking a set of items/players with varying values/strengths. The comparison outcomes are random, with a greater noise the closer the values. A crucial requirement is that, at each iteration of the algorithm, all items must be compared once, i.e., an iteration is a perfect matching. Furthermore, we presume that comparing two players with closely matched strengths incurs no cost and, in contrast, a unit cost is associated with comparing players whose strength difference is more substantial. Our secondary objective is to determine an optimal matching between players based on this cost function: we propose and analyze an algorithm that draws on concepts from both AKS sorting networks and bandit theory. Our algorithm achieves both objectives with high probability, and the total cost is optimal (up to logarithmic terms).} }
Endnote
%0 Conference Paper %T Active Ranking and Matchmaking, with Perfect Matchings %A Hafedh El Ferchichi %A Matthieu Lerasle %A Vianney Perchet %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-ferchichi24a %I PMLR %P 13460--13480 %U https://proceedings.mlr.press/v235/ferchichi24a.html %V 235 %X We address the challenge of actively ranking a set of items/players with varying values/strengths. The comparison outcomes are random, with a greater noise the closer the values. A crucial requirement is that, at each iteration of the algorithm, all items must be compared once, i.e., an iteration is a perfect matching. Furthermore, we presume that comparing two players with closely matched strengths incurs no cost and, in contrast, a unit cost is associated with comparing players whose strength difference is more substantial. Our secondary objective is to determine an optimal matching between players based on this cost function: we propose and analyze an algorithm that draws on concepts from both AKS sorting networks and bandit theory. Our algorithm achieves both objectives with high probability, and the total cost is optimal (up to logarithmic terms).
APA
Ferchichi, H.E., Lerasle, M. & Perchet, V.. (2024). Active Ranking and Matchmaking, with Perfect Matchings. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:13460-13480 Available from https://proceedings.mlr.press/v235/ferchichi24a.html.

Related Material