Maximin andel

Ej att förväxla med Max-min artikeltilldelning .

Maximin share (MMS) är ett kriterium för rättvis postallokering . Givet en uppsättning objekt med olika värden, 1-av-n maximin-andel det maximala värdet som kan uppnås genom att dela upp objekten i n delar och ta delen med det lägsta värdet.

En fördelning av poster mellan n agenter med olika värderingar kallas MMS-fair om varje agent får en bunt som är minst lika bra som hans/hennes 1-av- n maximin-share. MMS fairness uppfanns av Eric Budish som en uppmjukning av proportionalitetskriteriet - varje agent får en bunt som är minst lika bra som den lika stora fördelningen (1/ n av varje resurs). Proportionalitet kan garanteras när posterna är delbara, men inte när de är odelbara, även om alla agenter har identiska värderingar. Däremot kan MMS-rättvisa alltid garanteras för identiska agenter, så det är ett naturligt alternativ till proportionalitet även när agenterna är olika.

Motivation och exempel

Identiska föremål. Antag först att m identiska poster måste fördelas rättvist mellan n personer. Helst bör varje person få m / n artiklar, men detta kan vara omöjligt om m inte är delbart med n , eftersom objekten är odelbara. Ett naturligt näst bästa rättvisa kriterium är att avrunda m / n ner till närmaste heltal och ge varje person minst floor( m / n ) poster. Att ta emot föremål som är mindre än golv( m / n ) är "för orättvist" - det är en orättvisa som inte motiveras av föremålens odelbarhet.

Olika föremål. Antag nu att föremålen är olika och att varje föremål har olika värde. Anta till exempel att n =3 och m =5 och objektens värden är 1, 3, 5, 6, 9, vilket summerar till 24. Om objekten var delbara skulle vi ge varje person värdet 24/3 = 8 (eller, om de bara var delbara till heltalsvärden som i föregående stycke, åtminstone floor(24/3) = 8), men detta är inte möjligt. Det största värdet som kan garanteras för alla tre agenterna är 7, av partitionen {1,6},{3,5},{9}. Informellt är 7 det totala värdet dividerat med n "avrundat nedåt till närmaste post".

Uppsättningen {1,6} som uppnår detta maximivärde kallas "1-out-of-3 maximin-share" - det är den bästa delmängden av objekt som kan konstrueras genom att dela upp originaluppsättningen i 3 delar och ta minsta värdefull del. Därför, i det här exemplet, är en allokering MMS-rättvis om den ger varje agent ett värde på minst 7.

Olika värderingar. Anta nu att varje agent tilldelar ett annat värde till varje artikel, till exempel:

• Alice värderar dem till 1,3,5,6,9;
• George värderar dem till 1,7,2,6,8;
• Dina värderar dem till 1,1,1,4,17.

Nu har varje agent olika MMS:

• Alices MMS är fortfarande {1,6} enligt ovan;
• Georges MMS är {1,7} eller {2,6} eller {8}, av partitionen {1,7},{2,6},{8} (alla dessa paket är likvärdiga för honom);
• Dinas MMS är {1,1,1}, av partitionen {1,1,1},{4},{17}.

Här är en tilldelning MMS-rättvis om den ger Alice ett värde på minst 7, George ett värde på minst 8 och Dina ett värde på minst 3. Till exempel, ge George de två första objekten {1,7} , Alice de två nästa objekten {5,6}, och Dina det sista objektet {17}, är MMS-rättvis.

Tolkning . En agents 1-av- n MMS kan tolkas som den maximala nyttan som en agent kan hoppas få från en tilldelning om alla andra agenter har samma preferenser , när han alltid får den sämsta andelen. Det är den minimala nyttan som en agent kan känna sig berättigad till, baserat på följande argument: om alla andra agenter har samma preferenser som jag, finns det åtminstone en allokering som ger mig denna nytta och gör varannan agent (svagt ) bättre utan; därför finns det ingen anledning att ge mig mindre.

En alternativ tolkning är: den mest föredragna bunt agenten skulle kunna garantera som avdelare i sönderdelning och val mot fientliga motståndare: agenten föreslår sin bästa tilldelning och låter alla andra välja en aktie innan han tar den återstående.

MMS-rättvisa kan också beskrivas som ett resultat av följande förhandlingsprocess. En viss tilldelning föreslås. Varje agent kan invända mot det genom att föreslå en alternativ partition av objekten. Däremot måste han låta alla andra agenter välja sin andel innan han gör det. Därför skulle en agent motsätta sig en tilldelning endast om han kan föreslå en partition där alla paket är bättre än hans nuvarande paket. En allokering är MMS-rättvis om ingen agent motsätter sig den, dvs för varje agent, i varje partition finns det en bunt som är svagt sämre än hans nuvarande andel.

Formell definition

Låt C vara en mängd som representerar resursen som ska tilldelas. Låt V vara vilken reell funktion som helst på delmängder av C , som representerar deras "värde". 1 -av- n maximin-andelen av V från C definieras som:

$\operatorname { MMS} _{V}^{1{\text{-out-of-}}n}(C):=~~~\max _{(Z_{1},\ldots,Z_{n})\in \operatörsnamn {Partitioner} (C,n)}~~~\min _{j\in [n]}~~~V(Z_{j})$

Här är det maximala över alla partitioner av C i n disjunkta delmängder, och minimum är över alla n delmängder i partitionen. I exemplen ovan C en uppsättning heltal och V var summafunktionen, det vill säga V(Z) definierades som summan av heltal i Z . Till exempel visade vi att ${\displaystyle \operatörsnamn {MMS} _{V}^{1{\text {-out-of-}}3}(\{1,3,5,6,9\}):=7} ,$ där den maximerande partitionen är ({1,6},{3,5},{9 }). I ett typiskt Vn _rättvis allokeringsproblem finns det några n olika agenter med olika värdefunktioner V ₁ ,..., över samma resurs C . 1-av- n MMS-värdet för agent $\operatorname {MMS} _{i}^{1{\text{-out-of-}}n}(C):=\operatörsnamn {MMS} _{V_{i}}^{1{\text{-out- av-}}n}(C)$ betecknas med . En allokering är en vektor av n parvis disjunkta delmängder av C -- en delmängd per agent. En allokering Z ₁ ,..., Z _n kallas MMS-rättvis om för varje agent i,

$V_{i}(Z_{i})\geq \operatörsnamn {MMS} _{i}^{1{\text {-out-of-}}n}(C)$ .

Förekomsten av MMS-mässa tilldelningar

När alla n agenter har identiska värderingar existerar alltid en MMS-rättvis allokering per definition.

Ett lite mer generellt fall där en MMS-rättvis allokering existerar är när några n -1 agenter har identiska värderingar. En MMS-rättvis allokering kan sedan hittas genom att dividera och välja : de n -1 identiska agenterna delar upp objekten i n buntar som var och en är minst lika bra som deras MMS; den n :e agenten väljer en bunt med ett högsta värde; och de identiska medlen tar de återstående n -1-buntarna. I synnerhet, med två agenter, finns alltid en MMS-rättvis tilldelning.

Bouveret och Lemaître utförde omfattande randomiserade simuleringar för mer än 2 agenter, och fann att MMS-rättvisa tilldelningar existerar i varje försök. De bevisade att MMS-tilldelningar finns i följande fall:

• Binära värderingar - varje agent gillar antingen en vara (värderar den till 1) eller ogillar den (värderar den till 0).
• Identiska multiuppsättningar - agenter kan värdera objekten olika, men multiuppsättningarna av agenternas värden är desamma.
• Få föremål - m ≤ n +3.

Procaccia och Wang och Kurokawa konstruerade en instans med n= 3 agenter och m = 12 poster, där ingen tilldelning garanterar varje agent 1-av-3 MMS. I deras fall finns det 12 objekt, indexerade med $i\in [3]$ och $j\in [4]$ . Varje agent $k$ värderar varje objekt $(i,j)$ med:

$v_{k}(i,j)=1 000 000+1 000\cdot T_{ i,j}+E_{i,j}^{(k)}$

där $T,E^{(1)},E^{(2)},E^{(3)}$ är speciella 3- by-4 matriser med värden mindre än 100. De bevisar att varje agent kan dela upp objekten i 3 delmängder med 4 objekt vardera, så att summan av värden i varje delmängd är 4 055 000, vilket därför är MMS för alla agenter. De bevisar att varje MMS-tilldelning måste ge exakt 4 särskilda objekt till varje agent, men en sådan tilldelning existerar inte. Varje tilldelning ger alltså minst en agent ett värde på högst 4 054 999. De generaliserade denna instans och visade att för varje n ≥ 3 finns det en sådan instans med 3 n +4 objekt.

Däremot visar samma författare att det i ett slumpmässigt fall finns en MMS-allokering med hög sannolikhet . Beviset tar hänsyn till två fall:

• Det finns många poster: $m\geq \alpha \cdot n\ln {n}$ för någon konstant $\alpha$ som beror på sannolikhetsfördelningen. Sedan, genom ett tidigare resultat, existerar en avundsfri artikelallokering med hög sannolikhet; en sådan tilldelning är alltid MMS.
• Det finns få poster: $m<n^{8/7}$ [observera att det här fallet delvis överlappar det tidigare fallet]. För det här fallet presenterar de en algoritm som kallas matchat utkast . Den är baserad på att konstruera en tvådelad graf av agenter vs. objekt, och hitta en perfekt matchning i den . De bevisar att (1) sannolikheten att det matchade utkastet lyckas går till 1 eftersom n går till oändlighet. (2) Om det matchade utkastet lyckas, är värdet på varje agent minst hans MMS.

Amanatidis, Markakis, Nikzad och Saberi bevisar också att, i slumpmässigt genererade fall, finns MMS-rättvisa tilldelningar med hög sannolikhet .

Feige, Sapir och Tauber visar en snävare instans, där approximationsförhållandet är 39/40,

Uppskattningar

Budish introducerade en uppskattning av 1-av- n MMS-det 1-av-( $n+1$ ) MMS - varje agent får minst så mycket som han kunde få genom att dela upp i n +1 buntar och få den värsta. I allmänhet, för vilken d > n som helst , kan man betrakta 1-av-d MMS som en approximation till 1-av -n MMS, och leta efter en allokering där, för varje agent i :

$V_{i}(Z_{i})\geq \operatörsnamn {MMS} _{i}^{1{\text {-out-of-}}d}(C)$

Observera att värdet på 1-av-d MMS är en svagt minskande funktion av d . Detta kallas en ordinal approximation , eftersom det bara beror på rangordningen av buntarna och inte på deras exakta värden. Procaccia och Wang introducerade en annan typ av approximation - den multiplikativa approximationen till MMS: en allokering är r-fraktion MMS -fair, för någon bråkdel r i [0,1], om varje agents värde är minst en bråkdel r av värdet av hans/hennes MMS, det vill säga för varje agent jag :

$V_{i}(Z_{i})\geq r\cdot \operatörsnamn {MMS} _{i}^ {1{\text{-out-of-}}n}(C)$

Anta att man kan välja mellan två algoritmer: den första garanterar en multiplikativ approximation (t.ex. 3/4-bråk MMS), medan den andra garanterar en ordningsapproximation (t.ex. 1-av-(3 n /2) MMS ) . Vilken av de två garantierna är högre? Svaret beror på värdena.

• Den multiplikativa approximationen är högre, till exempel när det finns n identiska varor med värdet 1. Då är 1-of- $d$ MMS 0 för alla d > n , men 1-of- $n$ MMS är 1, så varje positiv multiplikativ approximation av det är bättre.
• Ordinal approximationen är högre, till exempel när det finns d identiska varor med värdet 1, för vissa d i { n +1,...,2 n -1}. Sedan 1-av-d MMS 1, och 1-of- $n$ MMS är också 1, så varje r- multiplikativ approximation av det med r <1 är sämre.

I allmänhet, för alla heltal k , 1-av- n MMS som minst k gånger 1-av- nk MMS: ta en optimal 1-av- nk MMS-partition och gruppera buntarna i n superbuntar, vardera varav innehåller k originalbuntar. Var och en av dessa superbuntar är värda minst k gånger den minsta originalbunten. Därför är en 1/ k -multiplikativ approximation minst lika stor som en 1-of- nk ordningsapproximation, men kan vara mindre än 1-of-( nk- 1) ordningsapproximation, som i exemplet ovan. I synnerhet är varje r -multiplikativ approximation för r ≥ 1/2 minst lika bra som 1-av-(2n ) ordningsapproximation, men kan vara sämre än 1-av-(2 n -1) ordningsapproximation.

MMS-mässa tilldelning av varor

Multiplikativa approximationer

Procaccia och Wang presenterade en algoritm som alltid hittar en r _n -fraktion MMS, där

$r_{n}:={\frac {2\cdot {\text{oddfloor}}(n)}{3\cdot {\text{oddfloor}}(n)-1}}={\begin{cases}{\frac {2n}{3n-1 }}&n~{\text{ udda}}\\{\frac {2n-2}{3n-4}}&n~{\text{ jämn}}\end{cases}}$

där oddfloor( n ) är det största udda heltal mindre eller lika med n . Speciellt r ₃ = r ₄ = 3/4, den minskar när n ökar, och den är alltid större än 2/3. Deras algoritm körs i tidspolynom i m när n är konstant, men dess körtid kan vara exponentiell i n .

Amanatidis, Markakis, Nikzad och Saberi presenterade flera förbättrade algoritmer:

• En enkel och snabb 1/2-fraktions MMS-algoritm;
• En 2/3-fraktions MMS-algoritm som körs i polynomtid i både m och n ;
• En 7/8-fraktions MMS-algoritm för 3 agenter;
• En MMS-rättvis algoritm för fallet med ternära värderingar - varje värde är 0 eller 1 eller 2.

Barman och Krishnamurthy presenterade:

• En enkel och snabb algoritm för 2/3-bråk MMS med additiva värderingar . Deras algoritm är baserad på att "beställa" instansen (dvs. reducera instansen till en där alla agenter är överens om rangordningen av varor), och sedan köra avundsgraf- proceduren med början på den mest värdefulla varan. De bevisar att resultatet är EFX och garanterar till varje agent ${\frac {2n}{3n-1}}$ av hans MMS, vilket är minst 2/3.
• En enkel algoritm för 1/10-fraktions MMS för det mer utmanande fallet med submodulära värderingar - baserad på round-robin objektallokering .

Ghodsi, Hajiaghayi, Seddighin, Seddighin och Yami presenterade:

• För additiva värderingar: ett bevis på existens för 3/4-fraktion MMS-rättvist.
• För n = 4 tillsatsmedel: en algoritm för 4/5-fraktions MMS-rättvisa.
• För submodulära värderingar : en polynom-tidsalgoritm för 1/3-bråk MMS-rättvishet och en övre gräns för 3/4-bråk.
• För XOS-värderingar : en polynom-tidsalgoritm för 1/8-bråk MMS-rättvist, ett existensbevis för 1/5-bråk och en övre gräns för 1/2-bråk.
• För subadditiva värderingar: ett existensbevis för log( m )/10-fraktion MMS-rättvisa, och en övre gräns på 1/2-fraktion.

Garg, McGlaughlin och Taki presenterade en enkel algoritm för 2/3-fraktions MMS-rättvisa vars analys också är enkel.

Garg och Taki presenterade:

• En enkel algoritm för 3/4-bråk MMS, som inte behöver känna till MMS-värdet, och därmed körs i starkt polynomisk tid.
• Ett bevis på existens av $({\frac {3}{4}}+{\frac {1}{12n}})$ -fraktion MMS.

Hittills är det inte känt vad som är det största r så att en r -fraktion MMS-allokering alltid existerar. Det kan vara vilket tal som helst mellan 3/4 och något mindre än 1.

Ordinal approximationer

Budish visade att Approximate Competitive Equilibrium from Equal Incomes alltid garanterar 1-av-( $n+1$ ) MMS. Denna allokering kan dock ha överskottsutbud och – ännu viktigare – överskottsefterfrågan: summan av paketen som tilldelats alla agenter kan vara något större än uppsättningen av alla artiklar. Ett sådant fel är rimligt i kurstilldelningen , eftersom ett litet överskott kan korrigeras genom att lägga till ett litet antal platser. Men det klassiska rättvisa uppdelningsproblemet förutsätter att föremål inte får läggas till.

Utan överskott av utbud och efterfrågan är följande approximationer kända:

• En 1-av-(2 n -2) MMS-allokering av varor och en 1-av-(2 n /3) MMS-allokering av sysslor, med avundsfri matchning .
• En 1-av-(3 n /2) MMS-allokering av varor, som kan beräknas i polytime när n <6.
• En 1-av-(3 n /2) MMS-allokering av varor i polynomtid, och ett L -out-of-([ L +1/2] n ) MMS-allokeringsexistensresultat.
• En 1-av-(3 n /4) MMS-tilldelning av sysslor.

Hittills är det inte känt vad som är det minsta d så att en 1-av- d MMS-allokering alltid finns. Det kan vara vilket tal som helst mellan n +1 och 3 n/ 2. Det minsta öppna fallet är n =4.

Ytterligare begränsningar

Maximering av produkten : Caragiannis, Kurokawa, Moulin, Procaccia, Shah och Wang visade att max-Nash-välfärdsallokeringen (tilldelningen som maximerar produkten av verktyg) alltid är ${\frac {2 }{1+{\sqrt {4n-3}}}}$ -fraktion MMS rättvist, och det är tight.

Sanning : Amanatidis, Birmpas och Markakis presenterade sanningsenliga mekanismer för ungefärliga tilldelningar av MMS-mässor (se även Strategisk rättvis uppdelning) :

• För n medel: en 1/O( m )-fraktion MMS.
• För 2 agenter: en 1/2-fraktion MMS och ett bevis på att ingen sanningsenlig mekanism kan uppnå mer än 1/2.

Kardinalitetsbegränsningar : Objekten är uppdelade i kategorier, och varje agent kan få högst k _h objekt från varje kategori h . Med andra ord måste buntarna vara oberoende uppsättningar av en partitionsmatroid .

• Barman och Biswas presenterar en algoritm som reducerar problemet till ett problem utan begränsningar men med submodulära värderingar, och använder sedan algoritmen för att uppnå 1/3-del av MMS-rättvist.
• Hummel och Hetland presenterar en förbättrad polynom-tidsalgoritm för 1/2-fraktions MMS-rättvisa. De anpassar standardteknikerna och minskningarna från den obegränsade inställningen till inställningen med begränsningar, och tillämpar sedan en variant av en påfyllningsprocedur.

Konfliktgraf : Hummel och Hetland studerar en annan inställning där det finns en konfliktgraf mellan objekt (till exempel: objekt representerar händelser och en agent kan inte delta i två samtidiga händelser). De visar att, om graden av konfliktgrafen är d och den är i (2, n ), så kan en 1/ d -fraktion MMS-allokering hittas i polynomtid, och en 1/3-bråk MMS-allokering finns alltid .

Anslutning : objekten är placerade på en graf, och varje del måste vara en ansluten subgraf.

• Bouveret, Cechlarova, Elkind, Igarashi och Peters bevisar att om grafen är acyklisk så existerar alltid en MMS-rättvis allokering och kan hittas effektivt. I allmänna grafer kanske en MMS-rättvis allokering inte existerar och kan vara NP-svår att hitta.
• Lonc och Truszczynski fokuserar på fallet där grafen är en cykel och presenterar en algoritm för ungefär MMS-rättvis allokering.

MMS-mässa fördelning av sysslor

Aziz, Rauchecker, Schryen och Walsh utökade MMS-begreppet till sysslor (objekt med negativa verktyg). Observera att för sysslor är de multiplikativa approximationsfaktorerna större än 1 (eftersom färre sysslor har högre användbarhet), och de ordinala approximationsfaktorerna är mindre än n . De presenterade:

• Ett bevis på att en MMS-tilldelning kanske inte finns för sysslor;
• En 2-fraktions MMS-algoritm för sysslor;
• Algoritmer för att hitta den optimala MMS-approximationen för en given instans, baserade på algoritmer för flervägsnummerpartitionering .

Barman och Krishnamurthy presenterade en algoritm som uppnår 4/3-fraktion MMS (exakt ${\displaystyle {\frac {4n-1}{3n}}})$ . Algoritmen kan ses som en generalisering av LPT-algoritmen för schemaläggning av identiska maskiner.

Huang och Lu bevisar att en 11/9-bråkdel MMS-rättvis allokering för sysslor alltid existerar, och en 5/4-bråkdel MMS-allokering kan hittas i polynomtid. Deras algoritm kan ses som en generalisering av Multifit-algoritmen för schemaläggning av identiska maskiner.

Kulkarni, Mehta och Taki studerar MMS-mässan tilldelning med blandade värderingar , dvs när det finns både varor och sysslor. De bevisar att:

• Ingen multiplikativ approximation är möjlig. De utökar exemplet med Procaccia och Wang genom att lägga till tre sysslor med ett värde på -4 054 999,75. 1-av-3 MMS för varje agent är 0,25 (varje MMS-paket innehåller fyra varor med en summa på 4 055 000 och en syssla). Varje tilldelning av godset ger dock minst ett ombud, ett värde på högst 4 054 999 från varan. Vi måste ge varje agent en syssla; därför har minst en agent ett negativt värde.
• De presenterar också förhållanden under vilka beräkning av en α-MMS och Pareto-optimal allokering, för bästa möjliga α i ett specifikt fall, kan göras i polynomtid.

Tekniker och algoritmer

Olika normaliseringar kan tillämpas på det ursprungliga problemet utan att ändra lösningen. Nedan O mängden av alla objekt.

Skalning

Om, för varje agent i, alla värderingar skalas med en faktor k _i (som kan vara olika för olika agenter), så skalas MMS för varje agent med samma faktor; därför är varje MMS-allokering i den ursprungliga instansen en MMS-allokering i den skalade instansen. Det är vanligt att skala värderingarna så att varje agents MMS är exakt 1. Efter denna skalning kan MMS-approximationsproblemen anges som:

• r-fraktion MMS : det totala värdet av O är åtminstone n ; vi måste ge var och en av n agenter en bunt värd minst r .
• 1-av-d MMS : det totala värdet av O är minst d ; vi måste ge var och en av n agenter ett paket värt minst 1.

Ovanstående skalning kräver att man beräknar MMS för varje agent, vilket är ett NP-hårt problem ( flervägsnummerpartitionering) . En alternativ skalning, som kan göras snabbare, är:

• r-fraktion MMS : det totala värdet av O är exakt n ; MMS är högst 1; vi måste ge var och en av n agenter en bunt värd minst r .
• 1-av-d MMS : det totala värdet av O är exakt d ; MMS är högst 1; vi måste ge var och en av n agenter ett paket värt minst 1.

Tilldela ett objekt

Om vi ​​tar bort ett objekt o från O . Sedan för varje agent är 1-av-( n -1) MMS med den återstående uppsättningen O \ o åtminstone hans 1-av- n MMS med hänsyn till den ursprungliga uppsättningen O . Detta beror på att n -1 delar förblir intakta i den ursprungliga MMS-partitionen. Anta nu att vi strävar efter att ge varje agent ett värde på r . Om något objekt o ₁ är värt minst r till minst en agent, så kan vi ge o ₁ till en sådan agent godtyckligt och fortsätta att allokera de återstående objekten till de återstående agenterna. Därför kan vi anta wlog att:

• r-fraktion MMS : värdet för varje objekt för alla agenter är mindre än r .
• 1-av-d MMS : värdet för varje objekt för alla agenter är mindre än 1.

Denna normalisering fungerar även med snabb skalning och med godtyckliga monotona värderingar (även icke-additiva).

Påsfyllning

Beteckna ett objekt, som värderas med högst s av alla agenter, som ett " s -litet objekt". Antag att alla objekt är s -små. Ta en tom påse och fyll den med föremål efter föremål, tills påsen är värd minst r till minst en agent. Ge sedan påsen till en sådan agent godtyckligt. Eftersom alla objekt är s -små, värderar de återstående agenterna påsen högst r + s ; om detta värde är tillräckligt litet, så är det återstående värdet tillräckligt stort så att vi kan fortsätta rekursivt. I synnerhet ger påsfyllning följande lösningar:

• 1/2-fraktion MMS : ta s = r = 1/2; Observera att genom den tidigare normaliseringen kan vi anta att alla objekt är 1/2-små. Inledningsvis finns det n agenter och det totala värdet är minst n för dem. Efter att en påse har allokerats värderar de återstående n -1 agenterna de återstående objekten till minst n - ( r + s ) = n -1, så vi kan fortsätta rekursivt.
• 1-av-(2n) MMS : ta s = r = 1; Observera att genom den tidigare normaliseringen kan vi anta att alla objekt är 1-små. Inledningsvis finns det n agenter och det totala värdet är minst 2 n för dem. Efter att en påse har allokerats värderar de återstående n -1 agenterna de återstående objekten till minst 2 n - ( r + s ) = 2n -2 = 2( n -1), så vi kan fortsätta rekursivt.

Dessa påsfyllningsalgoritmer fungerar även med den snabba skalningen, så de körs i polynomtid - de behöver inte veta det exakta MMS-värdet. Faktum är att båda algoritmerna kan anges utan att nämna MMS alls:

• Varje agent för vilken varje objekt är värt högst 1/(2 n ) av det totala värdet, får minst 1/(2 n ) av det totala värdet.

Modifierad påsfyllning : Villkoret att alla föremål är små kan lättas upp enligt följande. Ta några s < r . Beteckna ett objekt som inte är s -litet (dvs. värderat minst s av minst en agent) som ett " s -large objekt". Antag att högst n objekt är s -stora. Ta ett s -stort föremål o ₁ , lägg det i en påse och fyll det med s - små föremål tills en agent indikerar att det är värt för honom minst r . Det måste finnas minst en sådan agent, eftersom någon agent i värderar o ₁ vid några x > s . För denna agent finns det högst n -1 kvarvarande s -stora objekt. Genom den tidigare normaliseringen är dessa objekt fortfarande r -små, så deras totala värde för i är som mest r(n -1) , så värdet på återstående s -små objekt är åtminstone nr(n -1)- x = r ( n -1)+ rx ≥ rx.

Beställning

en instans ordnas om alla agenter har samma ordningsföljd på objekten, dvs objekten kan numreras o ₁ , ..., o _m så att för varje agent i , v _i ( o ₁ ) ≥ ... ≥ v _i ( o _m ). Intuitivt är ordnade instanser svårast, eftersom konflikten mellan agenter är störst. Faktum är att den negativa instansen av är ordnad - ordningen på objekten bestäms av matrisen ${\displaystyle T} ,$ som är densamma för alla agenter. Detta kan också bevisas formellt. Anta att vi har en algoritm som hittar, för varje ordnad instans, en r -fraktion MMS-allokering. Nu får vi en allmän artikelallokeringsinstans P . Vi löser det på följande sätt.

1. Konstruera en ordnad instans ord (P) på följande sätt: för varje agent i , definiera v _i ( o _j ) in ord( P ) som det j -:e högsta värdet i uppsättningen av värden för agent i i P. Detta kräver O( nm log( m )) tid.
2. Hitta en r -fraktion MMS-allokering ord( A) i ord( P ).
3. Konstruera en plocksekvens där agenten som fick o ₁ i ord (A) plockar först, agenten som fick o ₂ i ord (A) plockar tvåa osv.
4. Låt agenterna välja sina bästa föremål enligt plockningssekvensen. Låt A vara den resulterande allokeringen. I A får varje agent exakt samma antal artiklar som i ord( A ). Dessutom får varje agent som fick o _j i ord( A ), en av sina bästa j poster i A . Därför är hans värde för varje föremål han fick i A minst lika stort som hans värde för motsvarande föremål i ord( A ). Därför är värdet på varje agent i A minst lika högt som i ord( A ). Eftersom beställningen inte ändrar MMS-värdena är den nya allokeringen A fortfarande r -fraktion MMS.

Så när vi letar efter r -fraktion MMS-allokeringar kan vi anta wlog att:

• Ordinal rangordningen av objekten är densamma för alla agenter.

Tilldela två objekt

Antag att vi hittar två objekt o ₁ och o ₂ , att en agent i värderar minst r , medan de andra agenterna värderar högst 1. Då kan dessa två objekt allokeras till i . För de andra agenterna är 1-av-( n -1) MMS med avseende på den återstående uppsättningen åtminstone hans 1-av- n MMS med hänsyn till den ursprungliga uppsättningen O. Detta beror på att i den ursprungliga MMS-partitionen förblir minst n -2 delar intakta, medan de två delarna som inte är intakta kan kombineras till en enda del med ett värde på minst 1. Denna normalisering fungerar endast med additiva värderingar .

Anta dessutom att instansen är ordnad, och anta att vi tar bort från O de två objekten o _n , o _{n +1} (dvs de n -:e och ( n +1) -:e objekten med högst värde). Sedan för varje agent är 1-av-( n -1) MMS med den återstående uppsättningen åtminstone hans 1-av- n MMS med den ursprungliga uppsättningen O . Detta beror på att, enligt duvhålsprincipen, minst en MMS-del av varje agent måste innehålla två eller flera objekt från uppsättningen { o ₁ , ..., o _{n +1} }. Dessa objekt kan användas för att ersätta objekten som ges bort, vilket resulterar i n -1 delar med ett värde på minst 1. Detta betyder att, om objekten o _n , o _{n +1} har ett värde på minst MMS för vissa agent i , vi kan ge dem till i och fortsätta att allokera de återstående objekten till de återstående agenterna. Därför kan vi anta wlog att:

• r-fraktion MMS : det totala värdet av o _n , o _{n +1} för alla medel är mindre än r . I synnerhet är värdet på o _{n +1} och alla objekt efter det i beställningen mindre än r /2.
• 1-av-d MMS : det totala värdet av od , o _{d +1} för alla agenter är mindre än 1. I synnerhet är värdet på o _{d +1} och alla objekt efter det i beställningen mindre än 1/2.

Denna normalisering fungerar även med snabb skalning. Att kombinera det med modifierad påsfyllning leder till följande enkla algoritm för 2/3-fraktions MMS.

• Så länge som ett enskilt objekt är värt minst 2/3 för någon agent, allokera det.
• Beställ instansen.
• Så länge o _n , o _{n +1} är värda minst 2/3 för någon agent, allokera dem.
• Slutligen finns det högst n objekt med ett värde på minst 1/3; fördela dem med modifierad påsfyllning.

Garantin för denna algoritm kan anges även utan att nämna MMS:

• Varje agent, för vilken o ₁ är värd högst 2/(3 n ) av det totala värdet och o _n + o _n+1 är värda tillsammans högst 2/(3 n ) av det totala värdet, får minst 2/ (3 n ) av det totala värdet.

Algoritmiska problem

Flera grundläggande algoritmer relaterade till MMS är:

• Beräknar 1-av- n MMS för en given agent. Detta är ett NP-hårt optimeringsproblem, men det har flera approximationsalgoritmer; se Partitionering av flervägsnummer och schemaläggning av identiska maskiner .
• Att bestämma om en given allokering är MMS-rättvis är co-NP komplett för agenter med additiv värdering (det är i co-NP, eftersom det är möjligt att bevisa i polynomtid att en given allokering inte är MMS-rättvis, givet MMS-partitionen av en av agenterna, vilket visar att agentens MMS-värde är större än hans värde i den givna allokeringen).
• Besluta om en given instans tillåter någon MMS-tilldelning, givet MMS-värdena för alla agenter. Det är i NP eftersom det kan verifieras i polynomtid givet allokeringen; dess exakta körtidskomplexitet är okänd.
  • Därför är beslutet om huruvida en given instans tillåter någon MMS-allokering i ${\displaystyle NP^{NP}} ,$ dvs det kan lösas i icke-deterministisk-polynomisk tid genom att använda ett orakel till ett NP-problem (oraklet behövs för att beräkna MMS för en agent). Den exakta beräkningskomplexiteten för detta problem är dock fortfarande okänd: det kan vara nivå 2 eller 1 eller till och med 0 i polynomhierarkin .
• Beslutsproblemet med att kontrollera om det finns en minimax- andelsallokering är NP-svårt. Båda problemen kan approximeras av en PTAS , förutsatt att antalet agenter är fast. När agenternas värderingar är binära eller additiva och baserade på Borda-poäng , kan maximin-aktietilldelningar alltid hittas effektivt. När deras värderingar är icke-additiva, finns det fall där en r -fraktion MMS-allokering inte existerar för något positivt r . För en klass av symmetriska submodulära verktyg finns det emellertid en snäv 1/2-fraktions MMS-allokering, och den kan uppskattas till en faktor på 1/4.

Förhållande till andra skälighetskriterier

En tilldelning kallas avundsfri-utom-c-objekt (EF c ) för en agent i om det för varannan agent j finns en uppsättning av högst c objekt som, om den tas bort från j :s bunt, då i avundas inte resten. En EF0-tilldelning kallas helt enkelt avundsfri . EF1-tilldelningar kan hittas till exempel genom round-robin-objektallokering eller genom envy-graph-proceduren .

En allokering kallas proportionell-except-c-items (PROP* c ) för en agent i om det finns en uppsättning av högst c poster utanför i :s paket som, om den tas bort från uppsättningen av alla poster, då i värderar hans bunta minst 1/ n av resten. En PROP*0-allokering kallas helt enkelt proportionell .

EF0 antyder PROP*0, och EF1 antyder PROP*( n -1). Dessutom, för vilket heltal c 0 som helst, innebär EF c PROP*(( n -1) c ). Den motsatta implikationen gäller när n =2, men inte när n >2.

Följande maximi-andelsapproximationer antyds av PROP*( n -1), därför också av EF1:

• Multiplikativ approximation: 1/ n -fraktion MMS (1/ n är snäv);
• Ordinal approximation: 1-av-(2 n -1) MMS (2 n -1 är tät). På liknande sätt, för varje heltal c , innebär PROP* c 1-av-( c + n ) MMS.
• MMS när värdefunktionen är binär. Den motsatta innebörden gäller också.

Ovanstående implikationer illustreras nedan:

Avundslöst	→	Proportionell	→	Maximin-andel
↓		↓		↓
			→	1/ n -fraktion MMS
EF1	→	PROP*( n -1)	↔	MMS för binär värdering
↓		↓	→	1-av-(2 n -1) MMS
				↓
EF c	→	PROP*(( n -1) c )	→	1-av-(( n -1) c+n ) MMS

En tilldelning kallas avundsfri-utom-varje-föremål (EF x ) för en agent i om, för varannan agent j , för varje enskilt föremål som tagits bort från j :s paket, i inte avundas resten. EFx är strikt starkare än EF1. Det innebär följande MMS-uppskattningar:

• 2/3-fraktion MMS för 2 eller 3 agenter (det är tätt);
• 4/7-fraktion MMS för valfritt antal agenter (det är inte känt om det är snävt; den nuvarande övre gränsen är 8/13).

MMS för grupper

En tilldelning kallas pairwise-maximin-share-fair (PMMS-fair) om agenten i för varannan agent i och j får åtminstone sin 1-av-2 maximin-andel begränsad till de poster som tas emot av i och j . Det är inte känt om en PMMS-allokering alltid existerar, men en 0,618-approximation finns alltid.

En tilldelning kallas groupwise-maximin-share-fair (GMMS-fair) om, för varje undergrupp av agenter av storlek k , varje medlem i undergruppen får sin 1-av- k maximin-andel begränsad till objekten mottas av denna undergrupp.

Med additiva värderingar är de olika rättviseuppfattningarna relaterade enligt följande:

• Avundsfrihet innebär GMMS-rättvisa;
• GMMS-rättvishet innebär MMS-rättvist (genom att ta undergruppen av storlek n ) och PMMS-rättvisa (genom att ta undergrupper av storlek 2);
• PMMS-rättvishet innebär 2/3-MMS-rättvist för tre agenter och 4/7-MMS-rättvist i allmänhet;
• PMMS-rättvisa innebär EFX, vilket innebär EF1.
• EF1 innebär 1/2-PMMS och EFX innebär 2/3-PMMS. Därför kan en 1/2-PMMS-allokering hittas i polynomtid.
• MMS-rättvisa och PMMS-rättvisa innebär inte varandra.

GMMS-allokeringar finns garanterat när värderingarna av agenterna är antingen binära eller identiska. Med allmänna additiva värderingar finns 1/2-GMMS-allokeringar och kan hittas i polynomtid.

MMS för agenter med olika rättigheter

När agenter har olika rättigheter (även kallat: ojämlika andelar eller asymmetriska rättigheter ) bör MMS-rättvisa anpassas för att garantera en högre andel för agenter med högre rättigheter. Olika anpassningar har föreslagits. Nedan antar vi att rättigheterna ges av en vektor ${\displaystyle t=(t_{1},\ldots ,t_{n})} ,$ där $t_{i}$ representerar rätten för agent $i$ .

Viktad MMS rättvisa

Farhadi, Ghodsi, Hajiaghayi, Lahaie, Pennock, Seddighin och Seddigin introducerar Weighted Maximin Share (WMMS), definierad av:

$\operatorname {WMMS} _{i}^{t}(C):=~~ ~\max _{(Z_{1},\ldots ,Z_{n})\i \operatörsnamn {Partitioner} (C,n)}~~~\min _{j\in [n]}~~~{ \frac {t_{i}}{t_{j}}}V(Z_{j})=~~~t_{i}\cdot \max _{(Z_{1},\ldots ,Z_{n}) \in \operatorname {Partitioner} (C,n)}~~~\min _{j\in [n]}~~~{\frac {V(Z_{j})}{t_{j}}}$

Intuitivt uppnås det optimala WMMS genom en partition där värdet av del j är proportionell mot rätten för agent j . Anta till exempel att alla värdefunktioner är summorna och att berättigandevektorn är t =(1/6, 11/24, 9/24). Sedan $\operatörsnamn {WMMS} _{1}^{t}(\{1,3,5,6,9\} )=4$ av partitionen ({1,3},{5,6},{9}); det är optimalt eftersom värdet för varje del $i$ är lika med $24t_{i}$ . Med samma partition, $\operatorname {WMMS} _{2}^{t}=11$ och $\operatorname {WMMS} _{3}^{t }=9$ . När alla n rättigheter är lika, $\operatörsnamn {WMMS} _{i}^{t}\equiv \operatörsnamn {MMS} _{i}^{1 {\text{-out-of-}}n}$ .

En tilldelning av C kallas WMMS-fair för rättighetsvektor t om värdet för varje agent i är minst $\operatorname {WMMS} _{i}^{t}(C)$ . När alla n agenter har identiska värderingar existerar alltid en WMMS-rättvis allokering per definition. Men med olika värderingar är bästa möjliga multiplikativ approximation 1/ n . Den övre gränsen bevisas av följande exempel med 2 n -1 varor och n agenter, där ε>0 är en mycket liten konstant:

Ombud	Rättighet	Värde för objekt 1, ..., n -1	Värde för artikelnr	Värde för objekt n +1, ..., 2 n -1
1, ..., n -1	ε	ε	1-( n -1) e	0
n	1-( n -1) e	[1-( n -1) e ]/ n	[1-( n -1) e ]/ n	ε

Alla agenter har en optimal WMMS-partition: för de "små" agenterna (1, ..., n -1) är det partitionen ({1}, ..., { n -1}, { n }) och för den "stora" agenten ( n ) är den ({ n +1}, ..., {2 n -1}, {1,..., n }). Därför är $\operatorname {WMMS} _{i}^{t}=t_{i}$ för alla agenter i (för jämförelse, observera att ${\displaystyle \operatorname {MMS} _{i}^{1{\text{-out-of-}}n}=\epsilon =t_{i}} för de små agenterna,$ men $\operatörsnamn {MMS} _{i}^{1{\text{-out-of-}} n}=[1-(n-1)\epsilon ]/n=t_{i}/n$ för den stora agenten).

I varje multiplikativ approximation av WMMS måste alla agenter få ett positivt värde. Det betyder att de små agenterna tar minst n -1 av objekten 1,..., n , så högst en sådan post återstår för den stora agenten, och hans värde är ungefär 1/ n snarare än nästan 1.

En 1/ n -fraktion WMMS-rättvis allokering finns alltid och kan hittas genom round-robin objektallokering . I ett begränsat fall, där varje agent i värderar varje vara med högst $\operatorname {WMMS} _{i}^{t}$ , finns en 1/2-fraktion WMMS-rättvis allokering och kan hittas med en algoritm som liknar påsfyllning: värderingarna för varje agent i multipliceras med $t_{i}/\operatörsnamn {WMMS} _{i}^{t}$ ; och i varje iteration ges ett objekt till en missnöjd agent (en agent med ett värde mindre än $\operatorname {WMMS} _{i}^{t}/2$ ) som värderar det som mest. Denna algoritm allokerar till varje agent i minst $\operatorname {WMMS} _{i}^{t}/2$ och högst $\operatorname {WMMS} _{ i}^{t}$ . I praktiken existerar nästan alltid en WMMS-rättvis tilldelning.

Ordinal-MMS rättvisa

Babaioff, Nisan och Talgam-Cohen presenterar en naturlig förlängning av den ordinarie MMS-uppskattningen till agenter med olika rättigheter. För två heltal $l,d$ , sätt C och värdefunktionen V , definiera

$\operatörsnamn {MMS} _{V }^{l{\text{-out-of-}}d}(C):=~~~\max _{P\in \operatörsnamn {Partitioner} (C,d)}~~~\min _{ Z\in \operatörsnamn {Unions} (P,l)}~~~V(Z)$

Här är maximum över alla partitioner av C i $d$ disjunta delmängder, och minimum är över alla föreningar av $l$ delar. Till exempel, $\operatörsnamn {MMS} _{V}^{2{\text{-out- of-}}3}(\{1,3,5,6,9\})=15$ av partitionen ({1,6},{3,5},{9}). Nu definieras Ordinal Maximin Share (OMMS) av:

$\operatorname {OMMS} _{i}^{t}( C):=~~~\max _{l,d:~l/d\leq t_{i}}\operatörsnamn {MMS} _{i}^{l{\text{-out-of-}}d }(C)$

Till exempel, om berättigandet för agent i är vilket reellt tal som helst som är minst så stort som 2/3, då har han rätt till minst 2-av-3 MMS av C . Observera att även om det finns oändligt många par $l,d$ som uppfyller $l/d\leq t_{i}$ , är bara ändligt många av dem inte redundanta (inte underförstått av andra), så det är möjligt att beräkna OMMS i ändlig tid. En allokering Z ₁ ,..., Z _n kallas OMMS-fair för entitlement-vektor w om värdet för varje agent i är minst $\operatorname {OMMS} _{i} ^{t}(C)$ .

OMMS kan vara högre eller lägre än WMMS, beroende på värdena:

• Som ett exempel där WMMS är högre, anta att C = {40, 60} och t = (0,4, 0,6) . Sedan tydligt WMMS ₁ =40 och WMMS ₂ =60, så den enda WMMS-rättvisa allokeringen ger 40 till 1 och 60 till 2. Men OMMS ₁ =0, eftersom bråken som uppfyller $l /d\leq 0.4$ är ​​1/3, 2/5, 3/7, etc., och i alla fall, i alla partitioner av C i $d$ delmängder, finns det minst $l$ tomma delmängder. Dessutom är OMMS ₂ =40, eftersom bråken som uppfyller $l/d\leq 0,6$ är 1/2, 2/4, 3/5, 4/7, etc., och i alla fall , i någon partition av C i $d$ undermängder, innehåller $l$ minst värdefulla undermängder inte 60. Därför kan en OMMS-rättvis allokering ge 40 till 2 och 60 till 1 , eller ge ingenting till 1, som båda verkar orättvisa.
• Som ett exempel där OMMS är högre, anta att C = {40, 60} och t = (0,2, 0,2, 0,6) . Då WMMS _i =0 för all i , eftersom i vilken 3-partition av C som helst är minst en bunt tom. Så WMMS-rättvishetskriteriet är värdelöst. På liknande sätt, OMMS ₁ = OMMS ₂ = 0. Emellertid, OMMS ₃ =40 av paret $l/d=1/2$ och partitionen ({40},{60}), så OMMS-fairness kräver att ge minst en objekt till agent 3, vilket verkar rättvisare.

AnyPrice-Share rättvisa

Babaioff, Ezra och Feige introducerade ett tredje kriterium för rättvisa, som de kallar AnyPrice Share (APS) . De definierar det på två likvärdiga sätt; en av dem är helt klart en förstärkning av maximin-andelen. Istället för att dela upp objekten i osammanhängande buntar får agenten välja vilken samling buntar som helst som kan överlappa varandra. Men agenten måste då tilldela en vikt till varje bunt så att summan av vikter är minst 1, och varje objekt tillhör buntar vars totalvikt som mest är agentens rättighet. APS är värdet av det minst värdefulla paketet med positiv vikt. Formellt:

$\operatorname {APS} _{V}^{t}(C):=~ ~~\max _{P\in \operatorname {AllowedBundleSets} (C,t_{i})}~~~\min _{Z\in P}~~~V(Z)$

där det maximala är över alla uppsättningar av buntar så att, för viss tilldelning av vikter till buntarna, den totala vikten av alla buntar är minst 1, och den totala vikten för varje föremål är högst t _i . Det finns en polyomial-tidsalgoritm som garanterar varje agent minst 3/5 av hans APS.

APS är alltid minst lika hög som OMMS: givet en optimal l -out-of- d partition, med l/d ≤ t _i , kan man tilldela en vikt på 1/ d till föreningen av delar 1,.. ., l , föreningen av delar 2,..., l +1, och så vidare (på ett cykliskt sätt), så att varje del ingår i exakt l förbund. Därför tillhör varje föremål buntar vars totalvikt är högst l / d , vilket är högst t _i . Agenten är garanterad den minst värdefulla sådan bunt, som åtminstone är l -out-of- d MMS.

I vissa fall är APS strikt högre än OMMS. Här är två exempel:

• Ett enkelt exempel med olika rättigheter: låt C = {2,1,1,1,0} och t _i = 2/5 . OMMS är högst 1 (det räcker att kontrollera l/d i {1/3, 2/5}). Men APS är 2, med följande vikter: 0,4*{2}, 0,2*{1,1}, 0,2*{1,1}, 0,2*{1,1}. Observera att summan av vikter är 1. 2:an visas i en enda uppsättning med vikten 0,4, medan var och en av ettorna visas i två uppsättningar med vikten 0,2, 0,2.
• Ett mer komplext exempel med lika rättigheter: låt C = {5, 5, 5, 7, 7, 7, 11, 17, 23, 23, 23, 31, 31, 31, 65} och t i ₌ 1/3 . OMMS är lika med 1-av-3 MMS, och det är som mest 96; detta kan verifieras genom att kontrollera alla 3-partitioner. APS är 97, eftersom det är möjligt att konstruera 6 buntar med 5 artiklar vardera, med ett totalt värde av 97, så att varje objekt visas i exakt två buntar. Sedan kan man tilldela en vikt på 1/6 till varje bunt.
  • Detta exempel visar också att en APS-tilldelning kanske inte existerar ens för 3 agenter med identiska värderingar och lika rättigheter. Detta till skillnad från OMMS, som alltid finns med identiska värderingar och lika rättigheter, och WMMS, som alltid finns med identiska värderingar och godtyckliga rättigheter.

APS kan vara högre eller lägre än WMMS; exemplen är desamma som de som används för OMMS vs WMMS:

• WMMS är högre: C = {40, 60} och t = (0,4, 0,6) . Då WMMS ₁ =40 och WMMS ₂ =60. Men APS ₁ =0, eftersom varje föremål måste ha en vikt på högst 0,4, så den tomma bunten måste ha en vikt på minst 0,2. APS ₂ =40, eftersom varje föremål måste ha en vikt på högst 0,6, så {40} och det tomma paketet måste ha en totalvikt på minst 0,4.
• APS är högre: C = {40, 60} och t = (0,2, 0,2, 0,6) . Sedan WMMS _i =0 för all i . På liknande sätt är APS ₁ = APS ₂ = 0 enligt ovan. Men APS ₃ =40 t.ex. med vikterna 0,5*{40}, 0,5*{60}.

Se även

• Bintäckningsproblem och Binpackningsproblem - två väl studerade optimeringsproblem som kan ses som specialfall av odelbar godsallokering respektive odelbar sysslorallokering . Många tekniker som används för dessa problem är också användbara i fallet med tilldelning av maximin aktiepost.
• Egalitär postallokering - ofta kallad med det mycket liknande namnet "max-min item allocation", men dess definition och allokeringen den ger är mycket annorlunda än maximin share fairness.