Jämlik tårtskärning
Jämlik tårtskärning är en sorts rättvis tårtskärning där rättvisekriteriet är den jämlika regeln . Kakan representerar en kontinuerlig resurs (som mark eller tid), som måste fördelas mellan personer med olika värderingar över delar av resursen . Målet med jämlik kakskärning är att maximera det minsta värdet av en agent; med förbehåll för detta, maximera det näst minsta värdet; och så vidare. Det kallas också för leximinkakskärning , eftersom optimeringen görs med hjälp av leximinordningen på verktygens vektorer.
Konceptet med jämlik kakskärning beskrevs först av Dubins och Spanier , som kallade det "optimal partition".
Existens
Leximin-optimala tilldelningar finns närhelst uppsättningen av tilldelningar är ett kompakt utrymme . Detta är alltid fallet vid allokering av diskreta objekt, och lätt att bevisa vid allokering av ett ändligt antal kontinuerliga homogena resurser. Dubins och Spanier bevisade att, med en kontinuerlig heterogen resurs (" kaka "), är uppsättningen av tilldelningar kompakt. Därför finns det alltid leximinoptimala tårtandelningar. Av denna anledning kallas regeln för tilldelning av leximinkaka ibland Dubins-Spanier-regeln .
Varianter
När agenternas värderingar inte är normaliserade (dvs. olika agenter kan tilldela ett annat värde till hela kakan), finns det en skillnad mellan den absoluta nyttoprofilen för en allokering (där element i bara är nyttan av agent i ), och dess relativa nyttoprofil (där element i är nyttan av agent i dividerat med det totala värdet för agent i ). Den absoluta leximinregeln väljer en allokering där den absoluta nyttoprofilen är leximinmaximal, och den relativa leximinregeln väljer en allokering där den relativa nyttoprofilen är leximinmaximal.
Egenskaper
Båda varianterna av leximinregeln är Pareto-optimala och populationsmonotona . Men de skiljer sig åt i andra egenskaper:
- Den absoluta-leximinregeln är resursmonoton men inte proportionell ;
- Relativ-leximinregeln är proportionell men inte resursmonotonisk.
Förhållande till avundsfrihet
Båda varianterna av leximinregeln kan ge tilldelningar som inte är avundsfria . Anta till exempel att det finns 5 agenter, kakan är bitvis-homogen med 3 regioner, och agenternas värderingar är (saknade värden är nollor):
| Ombud | Vänster | Mitten | Höger |
|---|---|---|---|
| A | 6 | 9 | |
| B | 5 | 10 | |
| C | 15 | ||
| D | 15 | ||
| E | 15 |
Alla agenter värderar hela kakan till 15, så absolut-leximin och relativ-leximin är likvärdiga. Största möjliga minimivärde är 5, så en leximinallokering måste ge alla agenter minst 5. Det betyder att Högern måste delas lika mellan agenterna C, D, E, och Mitten måste ges helt till agent B. Men då A avundas B.
Dubins och Spanier bevisade att, när alla värdemått är strikt positiva, är varje relativ-leximinallokering fri från avund.
Weller visade en avundsfri och effektiv tårttilldelning som inte är relativ-leximin. Kakan är [0,1], det finns tre medel, och deras värdemått är triangulära fördelningar centrerade på 1/4, 1/2 respektive 3/4. Tilldelningen ([0,3/8],[3/8,5/8],[5/8,1]) har en verktygsprofil (3/8,7/16,7/16). Det är avundslöst och utilitaristiskt optimalt, därav Pareto-effektivt. Det finns dock en annan allokering ([0,5/16],[5/16,11/16],[11/16,1]) med en leximin-bättre verktygsprofil.
Beräkning
Dall'aglio presenterar en algoritm för att beräkna en leximinoptimal resursallokering.
Se även
- Rättvis tårtskärning - en tilldelning som ger varje agent lika nytta. Ofta sammanfaller den jämlika fördelningen med den rättvisa fördelningen, eftersom om verktygen är olika kan den mindre nyttan förbättras genom att flytta lite kaka från agenten med större nytta.
- Egalitär likvärdighet - ett liknande koncept i samband med homogen resursallokering.