Metric Distortion of Social Welfare Functions

In de wereld van besluitvorming, van het aannemen van een nieuwe werknemer tot het kiezen van een film voor een groepsavond, vertrouwen we vaak op mensen om hun voorkeuren te rangschikken. We vragen: "Wie is je favoriet?" of "Wat is je eerste keuze?" en gebruiken die antwoorden om een collectieve beslissing te nemen. Decennialang hebben onderzoekers bestudeerd hoe goed deze rangschikkingen vertalen naar goede uitkomsten wanneer we niet precies weten hoeveel mensen elke optie waarderen. Ze ontdekten dat zelfs zonder de exacte intensiteit van iemands gevoelens te kennen, het louter weten van hun volgorde van voorkeur kan leiden tot verrassend eerwaardige resultaten. Echter, het grootste deel van dit werk richtte zich op het kiezen van één enkele winnaar, zoals een president of de beste kandidaat. Het echte leven is vaak complexer. We moeten regelmatig een volledige lijst maken, waarbij iedereen van eerste tot laatste wordt gerangschikt, zoals een wachtlijst voor universiteitsopnames of een feed met productaanbevelingen. In dergelijke scenario's doet de positie er toe. De eerste plaats kunnen zijn cruciaal, terwijl de tiende plaats bijna hetzelfde kan zijn als de laatste. De vraag wordt dan: als we alleen de volgorde kennen die mensen verkiezen, maar niet weten hoeveel ze geven om het verschil tussen de eerste en de tweede plek, hoe goed kunnen we dan een volledige lijst opstellen die iedereen tevreden stelt?

Een team van onderzoekers heeft zich nu aangepakt voor deze specifieke uitdaging, door te onderzoeken hoe men een volledige rangschikking kan opbouwen wanneer kiezers verschillende niveaus van belangstelling hebben voor verschillende posities. Ze stelden zich een scenario voor waarin elke persoon een verborgen schaal van waarden heeft, die bepaalt hoeveel ze geven om de bovenste plek versus de onderste plek. Sommige mensen geven misschien alleen om de allereerste aanbeveling, terwijl anderen bereid zijn om door verschillende opties te bladeren voordat ze iets geschikts vinden. De onderzoekers wilden weten of een stemsysteem een eerlijke, kwalitatief hoogwaardige rangschikking voor iedereen kan creëren, zelfs zonder deze verborgen schalen te zien. Ze kwamen tot de conclusie dat het antwoord volledig afhangt van welke informatie het systeem mag gebruiken. Als het systeem precies weet hoeveel elke persoon aan elke positie waarde hecht, kan het een rangschikking construeren met de best mogelijke kwaliteit, waarbij een optimale distortie van 3 wordt bereikt. Als het systeem de waarden niet kent, maar weet dat iedereen dezelfde verborgen schaal deelt, kan het nog steeds erg goed presteren, waarbij de kwaliteit van het resultaat afhangt van hoeveel die gedeelde schaal varieert.

De moeilijkste situatie doet zich voor wanneer het systeem niets weet over de gewichten, en elke persoon zijn eigen unieke, verborgen schaal heeft. In dat geval bewezen de onderzoekers dat, ongeacht hoe slim de stemregel ook is, de kwaliteit van de rangschikking onvermijdelijk zal lijden naarmate het aantal kandidaten groeit. Ze toonden aan dat de fout in de uitkomst lineair groeit met het aantal kandidaten dat gerangschikt wordt. Simpel gezegd: als u een kleine groep rangschikt, kan het systeem een redelijk goed werk leveren, maar als u een groot aantal kandidaten heeft, maakt het gebrek aan informatie over hoeveel mensen geven om specifieke posities het onmogelijk om een goed resultaat te garanderen. Dit onderzoek benadrukt een fundamentele limiet: zonder te weten hoe kiezers het belang van verschillende plaatsen wegen, is een perfecte rangschikking onbereikbaar voor grote groepen.

De onderzoekers testten hun ideeën door een stapsgewijze methode te bouwen om deze rangschikkingen te creëren. Stel u voor dat u een lijst plek voor plek vult, beginnend bij de top. Bij elke stap kiest het systeem de beste beschikbare kandidaat voor die specifieke positie op basis van de huidige voorkeuren. Ze ontdekten dat als het systeem de gewichten kent, deze eenvoudige stapsgewijze aanpak optimaal werkt en een optimale distortie van 3 bereikt. Ze gebruikten een specifieke, geavanceerde methode om de winnaar bij elke stap te kiezen, waardoor ze konden bewijzen dat de uiteindelijke lijst net zo goed zou zijn als de theoretisch best mogelijke lijst onder deze beperkingen. Dit was een belangrijke ontdekking, omdat het aantoonde dat het creëren van een volledige lijst geen kwaliteitsverlies vereist vergeleken met het kiezen van slechts één winnaar, mits het systeem over de juiste informatie beschikt.

Wanneer de gewichten verborgen zijn maar door iedereen worden gedeeld, vonden de onderzoekers dat dezelfde stapsgewijze methode nog steeds werkt, maar dat de kwaliteit van het resultaat verandert op basis van de vorm van de gedeelde schaal. Als iedereen elke positie ongeveer evenveel waardeert, presteert het systeem met een distortie van 1, wat betekent dat de uitkomst perfect is afgestemd op de optimale sociale welvaart. Als iedereen alleen om de bovenste plek geeft, presteert het systeem exact even goed als wanneer het één winnaar kiest. De prestaties glijden soepel tussen deze twee extremen. Dit betekent dat zelfs zonder de specifieke cijfers te kennen, als de groep uniform is in hoe zij over de lijst denken, het systeem nog steeds een zeer effectieve rangschikking kan produceren. De onderzoekers boden een precieze formule voor deze prestatie, waarmee ze precies laten zien hoe de variatie in de waarden van de groep de uiteindelijke uitkomst beïnvloedt.

Echter, het verhaal verandert volledig wanneer de gewichten verborgen zijn en verschillend zijn voor iedere persoon. De onderzoekers toonden aan dat in deze chaotische omgeving het systeem een aanzienlijk verlies in kwaliteit niet kan vermijden. Ze construeerden specifieke voorbeelden waarbij de best mogelijke rangschikking vele malen superieur was aan wat enige stemregel zonder de gewichten zou kunnen produceren. Ze bewezen dat de kloof tussen de best mogelijke uitkomst en de werkelijke uitkomst direct groeit met het aantal kandidaten. Voor een lijst van tien kandidaten is de fout klein; voor een lijst van honderd is de fout veel groter. Dit resultaat ontkracht de hoop dat een slim algoritme het probleem kan oplossen zonder meer informatie. Het stelt een harde grens: om een kwalitatief hoogwaardige rangschikking voor een grote groep te krijgen, moet u ofwel weten hoe mensen de posities wegen, ofwel accepteren dat het resultaat imperfect zal zijn.

De studie onderzocht ook twee verschillende manieren waarop mensen hun waarden kunnen normaliseren. In het ene scenario verdeelt iedereen een vaste hoeveelheid totale waarde over de gehele lijst, zoals het verdelen van een dollar over alle posities. In het andere scenario geeft iedereen de bovenste plek een vaste waarde van één, ongeacht hoe ze de rest waarderen. De onderzoekers vonden dat in beide van deze realistische scenario's, het probleem van verborgen, verschillende gewichten tot dezelfde lineaire toename in fout leidt. Ongeacht hoe de kiezers hun interne schalen structureren, als het systeem ze niet kan zien en ze verschillen van persoon tot persoon, zal de kwaliteit van de rangschikking afnemen naarmate de lijst langer wordt. Dit vormt een duidelijke waarschuwing voor ontwerpers van aanbevelingssystemen of selectiecommissies: als u te maken heeft met een diverse groep met verschillende prioriteiten, kunt u niet vertrouwen op eenvoudige rangschikkingsmethoden om een perfecte lijst te produceren zonder meer specifieke gegevens over hun voorkeuren te verzamelen.

Uiteindelijk verheldert dit werk de grenzen van wat we kunnen bereiken met beperkte informatie. Het laat zien dat de weg naar een goede collectieve beslissing zwaar afhangt van de structuur van de beschikbare informatie. Wanneer we de gewichten kennen, kunnen we de optimale distortie van 3 bereiken. Wanneer we weten dat de gewichten voor iedereen gelijk zijn, kunnen we een distortie van 1 bereiken als de gewichten uniform zijn, of een resultaat dat tussen 1 en de single-winner grens interpoleert, afhankelijk van de variatie. Maar wanneer de gewichten verborgen en verschillend zijn, stuiten we op een muur waarbij de omvang van de groep de kwaliteit van het resultaat bepaalt. De onderzoekers hebben niet alleen een nieuwe manier voorgesteld om te stemmen; ze hebben de grenzen in kaart gebracht van wat mogelijk is, en hebben precies aangetoond waar de regels van eerlijkheid en efficiëntie breken wanneer informatie ontbreekt. Hun bevindingen bieden een praktische gids voor iedereen die voorkeuren wil aggregeren tot een volledige rangschikking, en herinneren ons eraan dat de complexiteit van de taak groeit met de diversiteit van de betrokken mensen.