Jämlik fördelning av föremål

Jämlik artikelfördelning , även kallad max-min föremålsallokering, är ett rättvis fördelningsproblem , där skälighetskriteriet följer den egalitära regeln . Målet är att maximera minimivärdet för en agent. Det vill säga bland alla möjliga tilldelningar är målet att hitta en tilldelning där det minsta värdet av en agent är så stort som möjligt. Om det finns två eller flera tilldelningar med samma minsta värde, är målet att bland dessa tilldelningar välja den där det näst minsta värdet är så stort som möjligt, och så vidare (enligt leximinordningen ) . Därför kallas en jämlik artikelfördelning ibland för en leximinpostfördelning .

Det speciella fallet där värdet av varje objekt j till varje agent är antingen 0 eller någon konstant v _j kallas jultomteproblemet : jultomten har en fast uppsättning gåvor och vill fördela dem mellan barn så att minst- ett lyckligt barn är så lyckligt som möjligt.

Några relaterade problem är:

Flervägsnummerpartitionering med max-min-målet motsvarar ett specialfall där alla agenter har samma värderingar. Ett ännu mer speciellt fall är partitionsproblemet , som motsvarar fallet med två agenter. Även detta specialfall är NP-svårt i allmänhet.
Schemaläggning av icke-relaterade maskiner är ett dubbelt problem, där målet är att minimera det maximala värdet.
Maximin aktiepostallokering är ett annat problem, där målet inte är att uppnå en optimal lösning, utan snarare att hitta en lösning där varje agent får ett värde över en viss tröskel.

Normalisering

Det finns två varianter av den egalitära regeln:

absolut egalitär (eller absolut leximin ), där maximeringen använder de nominella värdena för agenterna;
relativ jämlikhet (eller relativ leximin ) där maximeringen använder sina normaliserade värden - buntvärde dividerat med värdet av alla objekt.

De två reglerna är likvärdiga när agenternas värderingar redan är normaliserade, det vill säga alla agenter tilldelar samma värde till uppsättningen av alla poster. De kan dock skilja sig åt med icke-normaliserade värderingar. Till exempel, om det finns fyra objekt, Alice värderar dem till 1,1,1,1 och George värderar dem till 3,3,3,3, då skulle absolut-leximin-regeln ge tre objekt till Alice och ett objekt till George eftersom nyttoprofilen i detta fall är (3,3), vilket är optimalt. Däremot skulle relativ-leximin-regeln ge två poster till varje agent, eftersom den normaliserade nyttoprofilen i detta fall, när det totala värdet av båda agenterna är normaliserat till 1, är (0,5,0,5), vilket är optimalt.

Exakta algoritmer

Även om det allmänna problemet är NP-hårt, kan små instanser lösas exakt med hjälp av tvångsprogrammeringstekniker . Bouveret och Lemaître presenterar fem olika algoritmer för att hitta leximin -optimala lösningar på diskreta problem med tillfredsställelse av begränsningar. De presenterar max-min artikelfördelning som ett specialfall.

Approximationsalgoritmer

Nedan är n antalet agenter och m är antalet poster.

För det speciella fallet med jultomteproblemet:

Bansal och Sviridenko gav ett $O(\log {\log {n}}/\log {\log {\log {n}}})$ -approximationsalgoritm, baserad på avrundning av ett linjärt program .
Feige bevisade att en approximationsalgoritm för polynom-tidskonstantfaktor existerar, men beviset använde Lovász lokala lemma och var icke-konstruktivt.
Asadpour, Feige och Saberi gav en faktisk konstantfaktorapproximationsalgoritm, med hjälp av hypergrafmatchning . De kunde inte bevisa att det konvergerar i ett begränsat antal steg.
Annamalai, Kalaitzis och Svensson gav en polynom-tid 13-approximationsalgoritm.

För det allmänna fallet, för agenter med additiv värdering :

Bezakova och Dani presenterade två algoritmer. Den första ger en $(m-n+1)$ -faktor approximation till det optimala egalitära värdet. Den andra finner en allokering som är egalitär upp till en vara, det vill säga varje agent får sitt värde i den optimala egalitära allokeringen minus högst en enskild post. Deras algoritm är baserad på en tidigare algoritm av Lenstra, Shmoys och Tardos, som i huvudsak hittar en allokering som är egalitär upp till en syssla . Båda algoritmerna är baserade på en liknande idé. De hittar en grundläggande genomförbar lösning av det linjära programmet för att hitta en bråkdel, jämlik allokering, och rundar den så att varje agent förlorar högst en vara, eller får högst en syssla.
Asadpour och Saberi gav en $O({\sqrt {n}}\cdot \log ^{3}n)$ -approximationsalgoritm. Deras algoritm använder en iterativ metod för att avrunda en bråkmatchning på ett träd . De ger också bättre gränser när det är tillåtet att utesluta en liten bråkdel av människor från problemet.

Chakrabarty, Chuzoy och Khanna gav en $O(m^{\varepsilon })}$ $) {\displaystyle O(m^{1 /\varepsilon })}$ -approximationsalgoritm med en körtid på , för alla $\varepsilon \in \Omega \left({\frac {\log \log m}{\log m}} \right)$ . För det speciella fallet där varje objekt inte har någon nytta för högst två agenter, gav de en 2-faktors approximationsalgoritm och bevisade att det är svårt att approximera till någon bättre faktor.
Golovin $OPT/k$ en algoritm med vilken, för varje heltal $k$ , en $(1-1/k)$ bråkdel av agenterna får användbarhet åtminstone . Detta resultat erhålls från avrundning av en lämplig linjär programmeringsrelaxering av problemet, och är det bästa möjliga resultatet för detta linjära program. Han gav också en $O({\sqrt {n}})$ -approximationsalgoritm för specialfallet med två klasser av varor.
Dall'Aglio och Mosca gav en exakt gren-och-bunden algoritm för två agenter, baserad på en anpassning av den justerade vinnarproceduren .

För agenter med submodulära verktygsfunktioner :

Golovin gav en $(m-n+1)$ -approximationsalgoritm, och några inapproximationsresultat för allmänna hjälpfunktioner.
Goemans, Harvey, Iwata och Mirrkoni ger ett $O({\sqrt {m}}\cdot n^{1/4} \cdot \log n\cdot \log ^{3/2}m)$ -approximationsalgoritm
Nguyen, Roos och Rothe presenterar några starkare hårdhetsresultat.

Vanligtvis jämlika tilldelningar

Den vanliga jämlikhetsregeln kräver att varje agent tilldelar ett numeriskt värde till varje objekt. Ofta har agenterna bara ordinarie verktyg . Det finns två generaliseringar av den egalitära regeln till ordinalinställningar.

1. Antag att agenter har en ordinarie rangordning över uppsättningen av buntar . Med tanke på varje diskret tilldelning, för varje agent i , definiera r ( i ) som rangen för agent i:s bunt, så att r(i)=1 om jag fick hans bästa bunt, r(i)=2 om jag fick hans andra- bästa bunt, etc. Detta r är en vektor med storlek n (antalet agenter). En ordinärt-egalitär allokering är en som minimerar det största inslaget i r. Proceduren för minskad efterfrågan hittar en ordinärt jämställd tilldelning för valfritt antal agenter med valfri beställning av buntar.

2. Antag att agenter har en ordinarie rangordning över uppsättningen av objekt . Givet varje diskret eller bråktilldelning, för varje agent i och positivt heltal k , definiera t ( i , k ) som den totala fraktion som agent i får från sina k översta indifferensklasser. Detta t är en vektor med storlek som högst n * m , där n är antalet agenter och m är antalet objekt. En ordinärt-egalitär allokering är en som maximerar vektorn t i leximinordningen. Simultaneous Eating-algoritmen med samma äthastigheter är den unika regeln som returnerar en ordinärt-egalitär allokering.

Jämförelse med andra rättvisekriterier

Proportionalitet

Närhelst det finns en proportionell allokering är den relativa leximinallokeringen proportionell. Detta beror på att i en proportionell allokering är det minsta relativa värdet av en agent minst 1/ n , så detsamma måste gälla när vi maximerar det minsta relativa värdet. Men tilldelningen av absoluta leximin kanske inte är proportionell, som visas i exemplet ovan.

Avundsfrihet

1. När alla agenter har identiska värderingar med marginalnyttor som inte är noll, är all relativ leximinallokering PO och EFX .

En förbättring av leximin som kallas leximin++ garanterar EFX (men inte PO) med generella identiska värderingar.

2. För två agenter med additiv värdering är eventuell relativ-leximinallokering EF1. Dock:

Den absoluta leximinallokeringen kanske inte är EF1 även för två agenter med additiv värdering. Anta till exempel att det finns fyra varor och två agenter som värderar dem till {0,1,1,1} och {3,3,3,3}. Den unika tilldelningen av absolut leximin ger {1,1,1} till den första agenten och {3} till den andra agenten, men sedan avundas den andra agenten.
Den relativa leximinallokeringen kanske inte är EF1 för tre eller flera agenter. Anta till exempel att det finns fyra varor och tre agenter som värderar dem till {30,0,0,0} {20,5,5,0} och {0,12,12,6}. Observera att värderingarna är normaliserade (det totala värdet är 30). I en leximinallokering måste den första varan allokeras till agent 1. Sedan måste den andra och tredje varan allokeras till agent 2, och varan blir kvar för agent 3. Men då avundas agent 3 agent 2 även efter att ha tagit bort en vara.

3. När alla agenter har värderingar som är matroida rangfunktioner (dvs submodulära med binära marginaler), är uppsättningen av absolut-leximinallokeringar ekvivalent med uppsättningen av max-produktallokeringar; alla sådana tilldelningar är max-summa och EF1.

4. I samband med odelbar allokering av sysslor (artiklar med negativa verktyg), med 3 eller 4 agenter med additiv värdering, är varje leximinoptimal allokering PROP1 och PO; med n agenter med generellt identiska värderingar är varje leximinoptimal allokering EFX.

Maximin andel

När alla agenter har identiska värderingar ger den egalitära tilldelningen per definition varje agent åtminstone hans/hennes maximala andel.

Men när agenter har olika värderingar är problemen olika. Tilldelningen av maximal andel är ett tillfredsställelseproblem: målet är att garantera att varje agent får ett värde över tröskeln för identisk värdering. Däremot är den egalitära allokeringen ett optimeringsproblem: målet är att ge varje agent så högt värde som möjligt. I vissa fall kan de resulterande tilldelningarna vara mycket olika. Anta till exempel att det finns fyra varor och tre agenter som värderar dem till {3,0,0,0}, {3-2 ε,ε,ε ,0} och {1-2 ε ,1,1,2 ε } (där ε är en liten positiv konstant). Observera att värderingarna är normaliserade (det totala värdet är 3), så absolut-leximin och relativ-leximin är likvärdiga.

Leximintilldelningen ger nyttoprofilen (3, 2ε, 2ε ): den första posten måste gå till agent 1 - annars är den minsta nyttan 0. Sedan måste den andra och tredje posten gå till agent 2 - annars den näst minsta nyttan är e eller mindre; så agent 3 får bara det sista föremålet.
Agenternas maximi-andelsvärden är 0, ε , 1. Därför måste en maximin-share-allokering ge agent 3 en av de tre första posterna; några möjliga nyttoprofiler i detta fall är (0, 2ε , 1) eller (3, ε , 1+ 2ε ).

Exemplet kan utökas till 1-av- k MMS för valfri k >3. Det finns k +1 varor och tre agenter som värderar dem till { k , 0, ..., 0}, { k -( k -1) ε , ε, ..., ε , 0} och {1- kε , 1, 1, ..., k } . Leximinverktygsprofilen måste vara ( k , kε, kε ) medan 1-av- k MMS för agent 3 är 1.

Verklig applikation

Leximinregeln har använts för att rättvist fördela oanvända klassrum i offentliga skolor till charterskolor.