A skyline framework for exploring the utility-fairness trade-off in top-k queries

Top-k queries are widely adopted in information retrieval and decision-support systems, yet their results can perpetuate or amplify existing social biases against protected de mographic groups. Most prior work resolves the tension by optimizing either an utility score or a group distribution share, leaving practitioners unable to see the full spectrum of trade-offs. This thesis develops and analyses the UF-Skyline framework, which computes the com plete Pareto frontier of utility–fairness trade-offs for top-k queries over grouped data. Given a dataset partitioned into demographic groups, the framework returns every non dominated k-sets whose utility cannot be raised without worsening fairness, and vice versa, giving decision-makers full visibility of the available options rather than a single, pre-committed choice. The baseline algorithm, UF-Sky-Lists, traverses candidates through a monotone-swap mechanism over group-sorted lists and runs in O(nlogn) time. From this baseline the framework is generalized along several axes so that it applies to realistic data: groups defined by the Cartesian product of several protected attributes; Hamilton rounding for fractional group quotas; a multiple-swap search that restores completeness once the sin gle global swap no longer suffices; a family of five interchangeable distance functions: Manhattan (L1), Squared Euclidean (L2 2), Chebyshev (L∞), Chi-Squared (χ2), and Co sine Similarities (cosine); and exposure, a position-aware measure whose fairness-optimal set is built greedily. Two measures and five distances compose into ten interchangeable fairness functions over a single code path. The combinations are evaluated on toy, synthetic, and real-world datasets using nDCG@k, count and exposure based L1 deviation, hypervolume, and coverage. No single distance always dominates, overall L1 is the best choice for proportional fairness and cosine for exposure fairness on five of the six datasets at moderate k. When very small minority groups must be protected, χ2 takes over. The distances separate most sharply at inter mediate query sizes, and the knee of the frontier offers a single, defensible trade-off when one ranking must ultimately be chosen.

Le query top-k sono ampiamente adottate nei sistemi di information retrieval e di sup porto alle decisioni, ma i loro risultati possono perpetuare o amplificare pregiudizi so ciali esistenti nei confronti di gruppi demografici protetti. La maggior parte dei lavori precedenti risolve questa tensione ottimizzando o un punteggio di utilità o una quota di distribuzione tra i gruppi, impedendo a chi deve decidere di vedere l’intero spettro dei compromessi. Questa tesi sviluppa e analizza il framework UF-Skyline, che calcola il fronte di Pareto completo dei compromessi utilità–fairness per query top-k su dati raggruppati. Dato un dataset partizionato in gruppi demografici, il framework restituisce ogni k-set non dom inato, la cui utilità non può essere aumentata senza peggiorare la fairness e viceversa, offrendo a chi decide piena visibilità sulle opzioni disponibili anziché un’unica scelta pre definita. L’algoritmo di base, UF-Sky-Lists, esplora i candidati attraverso un meccanismo di scambio monotono su liste ordinate per gruppo e ha complessità O(nlogn). A partire da questa base, il framework è generalizzato lungo più direzioni in modo da applicarsi a dati realistici: gruppi definiti dal prodotto cartesiano di più attributi protetti; arrotondamento di Hamilton per quote di gruppo frazionarie; una ricerca a scambi multipli (multiple-swap) che ripristina la completezza quando il singolo scambio globale non è più sufficiente; una famiglia di cinque funzioni di distanza intercambiabili: Manhattan (L1), Euclidea al quadrato (L2 2), Chebyshev (L∞), Chi-quadro (χ2) e Coseno (cosine); ed exposure, una misura sensibile alla posizione il cui insieme ottimo per la fairness è costruito in modo greedy. Due misure e cinque distanze si compongono in dieci funzioni di fairness intercambiabili su un unico percorso di codice. Le combinazioni sono valutate su dataset toy, sintetici e reali tramite nDCG@k, deviazione L1 basata sui conteggi e sull’esposizione, hypervolume e coverage. Nessuna distanza domina sempre: nel complesso L1 è la scelta migliore per la fairness proporzionale e il cosine per la fairness di esposizione su cinque dei sei dataset per valori di k moderati. Quando occorre tutelare gruppi minoritari molto piccoli, subentra il χ2. Le distanze si differenziano in modo più netto per dimensioni di query intermedie, e il punto di ginocchio (knee) del fronte offre un compromesso unico e difendibile quando occorre infine scegliere un singolo ranking.