Communication Dans Un Congrès Année : 2024

Active Ranking and Matchmaking, with Perfect Matchings

Résumé

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).

Fichier principal
Vignette du fichier
ferchichi24a (7).pdf (562.75 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-04891449 , version 1 (16-01-2025)

Identifiants

  • HAL Id : hal-04891449 , version 1

Citer

Hafedh El Ferchichi, Matthieu Lerasle, Vianney Perchet. Active Ranking and Matchmaking, with Perfect Matchings. ICML 2024 - The Forty-First International Conference on Machine Learning, Jul 2024, Vienne, Austria. ⟨hal-04891449⟩
0 Consultations
0 Téléchargements

Partager

More