Vi studerar sociala valregler inom ramen för den utilitaristiska snedvridningen, med ytterligare ett metriska antagande om agenternas kostnader i förhållande till alternativen. I detta tillvägagångssätt ges dessa kostnader genom ett underliggande mått på uppsättningen av alla agenter plus alternativ. Reglerna för socialt val har endast tillgång till agenters normala preferenser, men inte till de latenta huvudkostnader som föranleder dem. Snedvridning definieras sedan som förhållandet mellan den sociala kostnaden (vanligtvis summan av agentkostnaderna) för det alternativ som valts av den nuvarande mekanismen och det optimala alternativet som väljs av en allvetande algoritm. Den värsta snedvridningen av en social valregel är därför ett mått på hur nära den alltid kommer det optimala alternativet utan någon kunskap om de underliggande kostnaderna. Enligt denna modell har man antagit att Ranked Pars, den välkända viktade turneringsregeln, uppnår en förvrängning på högst 3 (Anshelevich et al. Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning. Vi motbevisar denna gissning genom att konstruera en sekvens av fall som visar att den värsta fall förvrängning av Rankade par är minst 5. Vår nedre gräns på den värsta förvrängningen av Ranked Pairs matchar en tidigare känd övre gräns för Copeland-regeln, vilket bevisar att i värsta fall är den enklare Copeland-regeln minst lika bra som Ranked Pairs. Och så länge vi är begränsade till (viktade eller oviktade) turneringsregler, visar vi att randomisering inte kan bidra till att uppnå en förväntad värsta fall snedvridning på mindre än 3. Med hjälp av begreppet ungefärlig majorisering inom ramen för snedvridningen, visar vi att Copeland och Randomized Dictatorship uppnår låg konstant faktor rättvisa-ratios (5 respektive 3), vilket är en betydande generalisering av liknande resultat för summan av kostnader och enskilda största kostnadsmål. Förutom allt det ovanstående skisserar vi flera intressanta riktningar för ytterligare forskning i detta utrymme.
Rättvisa egenskaper sociala val regler generaliserar snedvridning i den meningen att för alla k, den anser summan av de k största kostnaderna REF.
Metric Distortion of Social Choice Rules: Lower Bounds and Fairness Properties
{'venue': "EC '17", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}