Problemet med att rangordna en uppsättning objekt är en grundläggande algoritmisk uppgift i dagens datadrivna värld, och har fått stor uppmärksamhet inom datavetenskap. Rankningsalgoritmer ligger i kärnan av applikationer som sökmotorer, nyhetsflöden och rekommendationssystem. Flera händelser på senare tid har dock pekat på att algoritmiska fördomar i rangordningar, som resulterar i minskad rättvisa eller mångfald i den typ av innehåll som presenteras, kan främja stereotyper och sprida orättvisor. Motiverade av sådana verkliga tillämpningar inleder vi i detta dokument en studie av det traditionella rankningsproblemet med ytterligare krav på rättvisa. Med tanke på en samling av objekt tillsammans med 1) värdet av att placera en post på en viss position, 2) insamling av eventuellt icke-skiljaktiga attribut (t.ex. kön, ålder, ras) för varje post och 3) en samling rättvisa begränsningar som övre gräns för antalet objekt med varje attribut som tillåts visas i de högsta positionerna i rangordningen, målet är att producera en ranking som maximerar värdet samtidigt som begränsningarna respekteras. Detta problem inkapslar olika välstuderade problem relaterade till bipartit och hypergraph matchning som specialfall och visar sig vara svårt att approximera även med enkla begränsningar. Våra viktigaste tekniska bidrag är exakta och approximationsalgoritmer tillsammans med kompletterande hårdhetsresultat som tillsammans är nära att lösa det begränsade rankningsmaximeringsproblemets approximabilitet. Vi identifierar en parameter - det maximala antalet egenskaper något objekt har - och visar att å ena sidan när  till = 1, det finns en snabb algoritm för att lösa problemet exakt, men å andra sidan när  till ≥ 3, problemet är svårt att approximera, och vi presenterar en nära-optimal O ( ska) - approximation algoritm för problemet under milda antaganden. Till skillnad från tidigare arbete på tillnärmningen av begränsade matchningsproblem, vår algoritm är polynom tid, även när antalet begränsningar är stort (polynomiskt många), dess approximation beror inte på antalet begränsningar, och det producerar lösningar med små begränsningar överträdelser. Tekniskt sett är våra huvudsakliga resultat beroende av nya insikter om standard linjär programmeringsavkoppling för det begränsade matchningsproblemet när den objektiva funktionen uppfyller vissa egenskaper som visas i gemensamma rankningsmått såsom diskonterad kumulativ vinst (DCG), Spearmans rho eller Bradley-Terry, tillsammans med den bofasta strukturen av rättvisa begränsningar. Sammantaget bidrar våra resultat till den växande uppsättningen algoritmer som kan motverka algoritmiska förutfattade meningar, och de strukturella insikter som erhålls kan användas i andra algoritmiska sammanhang relaterade till rankingproblem.
Celis m.fl. REF presenterar en teoretisk undersökning av beräkning av rättvis rankning med begränsningar av högsta och lägsta antal element som har ett attributvärde som kan förekomma vid varje rankning.
Ranking with Fairness Constraints
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}