We consider the problem of ranking N objects starting from a set of noisy pairwise comparisons provided by a crowd of equal workers. We assume that objects are endowed with intrinsic qualities and that the probability with which an object is preferred to another depends only on the difference between the qualities of the two competitors. We propose a class of non-adaptive ranking algorithms that rely on a least-squares optimization criterion for the estimation of qualities. Such algorithms are shown to be asymptotically optimal (i.e., they require O(Nϵ2logNδ) comparisons to be (ϵ,δ) -PAC). Numerical results show that our schemes are very efficient also in many non-asymptotic scenarios exhibiting a performance similar to the maximum-likelihood algorithm. Moreover, we show how they can be extended to adaptive schemes and test them on real-world datasets.

Ranking a set of objects: a graph based least-square approach / Christoforou, Evgenia; Nordio, Alessandro; Tarable, Aberto; Leonardi, Emilio. - In: IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING. - ISSN 2327-4697. - ELETTRONICO. - 8:1(2021), pp. 803-813. [10.1109/TNSE.2021.3053423]

Ranking a set of objects: a graph based least-square approach

Evgenia Christoforou;Emilio Leonardi
2021

Abstract

We consider the problem of ranking N objects starting from a set of noisy pairwise comparisons provided by a crowd of equal workers. We assume that objects are endowed with intrinsic qualities and that the probability with which an object is preferred to another depends only on the difference between the qualities of the two competitors. We propose a class of non-adaptive ranking algorithms that rely on a least-squares optimization criterion for the estimation of qualities. Such algorithms are shown to be asymptotically optimal (i.e., they require O(Nϵ2logNδ) comparisons to be (ϵ,δ) -PAC). Numerical results show that our schemes are very efficient also in many non-asymptotic scenarios exhibiting a performance similar to the maximum-likelihood algorithm. Moreover, we show how they can be extended to adaptive schemes and test them on real-world datasets.
File in questo prodotto:
File Dimensione Formato  
TNSE3.pdf

non disponibili

Descrizione: Editorial postprint
Tipologia: 2a Post-print versione editoriale / Version of Record
Licenza: Non Pubblico - Accesso privato/ristretto
Dimensione 903.47 kB
Formato Adobe PDF
903.47 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
LS_Ranking_final.pdf

accesso aperto

Descrizione: Informal open version
Tipologia: 2. Post-print / Author's Accepted Manuscript
Licenza: PUBBLICO - Tutti i diritti riservati
Dimensione 6.26 MB
Formato Adobe PDF
6.26 MB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11583/2862351