Den maximala Nash välfärd (MNW) lösning-som väljer en tilldelning som maximerar produkten av verktyg-är känd för att ge utestående rättvisa garantier vid tilldelning delbara varor. Och även om den verkar förlora sin lyster när den tillämpas på odelbara varor, visar vi att MNW-lösningen faktiskt är slående rättvis även i denna miljö. I synnerhet bevisar vi att det väljer tilldelningar som är avundsfria upp till en bra-en övertygande uppfattning som är ganska svårfångad när det kombineras med ekonomisk effektivitet. Vi konstaterar också att MNW-lösningen ger en bra approximation till en annan populär (ännu möjligen ogenomförbar) rättvisefastighet, den maximala aktiegarantin, i teorin och ännu mer so-in praktiken. Samtidigt som det är svårt att beräkna MNW-lösningen, utvecklar vi en icke-trivial implementation och visar att den skalar sig väl på verkliga data. Dessa resultat etablerar MNW som en övertygande lösning för tilldelning av odelbara varor och ligger till grund för dess införande på en populär webbplats för rättvis fördelning. 12:2 Jag. Caragiannis et al. Vi är intresserade av problemet med en rättvis fördelning av odelbara varor, till exempel smycken eller konstverk. Men för att bättre förstå sammanhanget för vårt arbete, låt oss börja med ett enklare problem: rättvis fördelning av delbara varor. Specifikt, låt det finnas m homogena delbara varor, och n spelare med linjära värderingar över dessa varor; det vill säga, om spelaren jag får en x i på bråkdelen av bra, hennes värde Frågan, naturligtvis, är vilken bråkdel av varje vara att fördela till varje spelare; och det har ett elegant svar, ges mer än fyra decennier sedan av Varian [41]. Under hans konkurrenskraftiga jämvikt från lika inkomster (CEEI) lösning, alla spelare är utrustade med en lika budget, säger $ 1 vardera. Balansen är en fördelning i kombination med (virtuella) priser för varorna, så att varje spelare köper sin favorit paket av varor för de givna priserna, och market clears (alla varor säljs). Ett formellt sätt att hävda att denna lösning är rättvis är genom den övertygande föreställningen om avundsfrihet [23]: Varje spelare föredrar svagt sitt eget paket framför bunten av någon annan spelare. Denna egendom är uppenbarligen nöjd med CEEI, eftersom varje spelare har råd med bunten av alla andra spelare, men istället väljer att köpa sin egen bunt. Även om CEEI-lösningen kan verka tekniskt otymplig vid första anblicken, finns den alltid, och i själva verket har en mycket enkel struktur i den föregående inställningen: CEEI-tilldelningen (som är vad vi bryr oss om, eftersom priserna är virtuella) exakt sammanfaller med tilldelningar x som maximerar Nash social välfärd i v i (x i ) [5, Volym 2, kapitel 14]. Följaktligen kan en CEEI tilldelning beräknas i polynom tid via konvex program av Eisenberg och Gale [22]. Låt oss nu se över vårt ursprungliga problem - att fördela odelbara varor, under additiva värderingar: nyttan av en spelare för hennes bunt av varor är helt enkelt summan av hennes värden för de enskilda varor hon får. Detta är en ogästvänlig värld där centrala rättvisa föreställningar som avund frihet inte kan garanteras (tänk bara på en enda odelbar bra och två spelare). Det behöver inte sägas att det inte längre finns någon CEEI-tilldelning. Icke desto mindre verkar tanken på att maximera Nash sociala välfärd (dvs. produkten av verktyg) naturligt i sig själv [19, 37]. Informellt, det träffar en söt plats mellan Benthams utilitaristiska begreppet social välfärd-maximera summan av verktyg-och den jämlika begreppet av Rawlsmaximize den minsta nytta. Dessutom är denna lösning skalfri, i den meningen att skalning av en spelares värderingsfunktion inte skulle ändra resultatet [31]. Men, när den maximala Nash välfärd lösning är vriden från världen av delbara varor, verkar det förlora sin styrka. Eller gör det det? Vårt mål i denna artikel är att visa "orimlig effektivitet" [43]-eller orimlig rättvisa, om du vill-av den maximala Nash välfärd (MNW) lösning, även när varorna är odelbara. Vi vill övertyga läsaren om att. .. MNW lösning uppvisar en svårfångad kombination av rättvisa och effektivitet egenskaper, och kan enkelt beräknas i praktiken. Det ger den mest genomförbara metoden för datum-argumentabelt, den slutliga lösningen-för uppdelning av odelbara varor enligt additiva värderingar. Vår strävan efter rättvisare algoritmer är en del av det växande arbetet med praktiska tillämpningar av beräknings rättvis uppdelning [1, 16, 24, 27, 36]. Vi är särskilt glada över att göra en verklig påverkan genom Spliddit (www.spliddit.org), en icke-vinstdrivande fair-division webbplats [25]. Sedan starten i november 2014 har webbplatsen lockat mer än 90K-användare. Mottot för Spliddit är bevisligen rättvisa lösningar, vilket innebär att de lösningar som erhålls från var och en av webbplatsens fem applikationer uppfyller garanterade rättvisa egenskaper. Dessa egenskaper förklaras noggrant för användarna,
I Ref studerades avvägningen mellan rättvisa och välfärd genom rättvisepriset – förhållandet mellan den maximala välfärden för en godtycklig fördelning och den maximala välfärden för en rättvis fördelning.
The Unreasonable Fairness of Maximum Nash Welfare
{'venue': 'TEAC', 'journal': None, 'mag_field_of_study': ['Computer Science']}