Omröstningen är kärnan i många viktiga beslut, inte minst valet av regeringstjänstemän. Genom att rösta, eller socialt val, studerar teorin aggregering av agentpreferenser till ett enda kollektivt beslut via en social valregel. Vanligtvis lämnar varje agent in en rankning över kandidaterna, och en social valregel kartlägger varje instans av dessa preferenser till ett eller flera alternativ. Men hur väljer vi den sociala valregeln? Traditionellt har dessa regler utvärderats baserat på enkla axiomatiska kriterier-t.ex., majoriteten vinnare kriterium-men tyvärr även små uppsättningar av axiom kan vara omöjligt att uppfylla samtidigt. En nyare strategi går längre än axiom för att ha en nyttosyn på det sociala valet. I denna modell, även om agenter uttrycker sina preferenser via en ordinal ranking, antas de ha latenta kardinal preferenser framför alternativen. I den metriska distorsionsmodellen [1] utgår vi från att agenterna och alternativen ligger i ett godtyckligt, okänt metriska utrymme, och att en agents kostnad för ett alternativ är lika med avståndet mellan de två. Med endast detta enkla antagande har det visat sig att vissa sociala valregler, som Copeland, kan åstadkomma en konstant faktorsförvrängning, dvs. det värsta förhållandet mellan de sociala kostnaderna för den valda kandidaten och den optimala kandidaten som valts allvetande [1]. Inom ramen för den metriska snedvridningen kan vi också fråga oss hur kvantitativt "rättvis" en social valregel är. I detta syfte anser vi att rättvisa förhållandet [2], som är en samtidig bunden, över alla k, på förhållandet mellan k största agentkostnader för den valda kandidaten kontra den optimala kandidaten i det okända metriska. Detta begrepp om rättvisa, baserat på ungefärlig majorisering, generaliserar både total kostnadsminimering (när k är lika med det totala antalet agenter), och max-min rättvisa (när k = 1) [2]. Rättviseförhållandet innebär också en approximativ garanti för en bred klass av konvexa objektiva funktioner [2]. I vårt arbete visar vi att dessa begrepp – snedvridningen och rättviseförhållandet – i själva verket är nära förbundna med varandra. Rättviseförhållandet är ett starkare begrepp än snedvridning, så det är alltid minst lika stort. Vi visar dock att rättviseförhållandet endast kan överstiga snedvridningen med högst en additiv faktor på 2 (och att detta gap är snävt). I huvudsak använder vi triangeln ojämlikhet för att hävda att om de värsta-off k agenter är långt från den valda kandidaten (jämfört med den optimala kandidaten), kan de återstående agenterna inte vara för nära heller. Vi betraktar den "diamant" som bildas av: avståndet från den valda kandidaten till den sämsta-off k agenter (mäta rättvisa); från de sämsta-off agenter till den optimala kandidaten; från den optimala kandidaten till en annan, godtycklig agent; och från den agenten till den utvalda kandidaten (mäta förvrängning). Vid jämförelse av rättvisa och snedvridning, den additiva faktorn 2 uppstår från de två sidorna av diamanten ansluten till den optimala kandidaten. Detta resultat ger omedelbart gränser för rättvisa förhållandet mellan flera sociala valregler, såsom STV, för vilka endast gränser för snedvridning tidigare var kända. Även om skillnaden mellan snedvridnings- och rättviseförhållandet fortfarande kan vara relevant när snedvridningen är liten, kan det hävdas att detta nära förhållande bidrar till att ytterligare bekräfta snedvridningen som ett användbart mått på kvaliteten på reglerna för socialt val. Slutligen anser vi att det är en relativt mindre välstuderad fråga i den metriska snedvridningsmodellen: den om flervinnande sociala valregler. Att välja flera alternativ kan vara värdefullt för tillämpningar från att välja kommittéer till att välja var man ska bygga brandstationer. Vi fokuserar särskilt på inställningen där agenters preferenser är additiv-den totala kostnaden för en agent är bara summan av hennes kostnader över den valda uppsättningen av alternativ. I detta sammanhang fastslår vi att alla bestämmelser om en enda vinnare kan tillämpas rekursivt för att erhålla en multivinnarregel med samma koppling till snedvridning. Rättviseförhållandet generaliseras inte direkt från en enda vinnare till flervinnare, utan genom att utvidga vårt huvudresultat (att rättviseförhållandet på sin höjd är snedvridningen plus 2) till flervinnares regler visar vi att en konstant snedvridning och rättvisa förhållande kan uppnås, till exempel genom den återkommande Copeland-regeln.
Dessutom kan rättviseförhållandet och snedvridningen endast skilja sig åt med högst 2 additivt REF.
Relating Metric Distortion and Fairness of Social Choice Rules
{'venue': "NetEcon '18", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}