Effektiv ungefär rättvis tilldelning av föremål

När man fördelar objekt mellan personer med olika preferenser är två huvudmål Pareto-effektivitet och rättvisa. Eftersom objekten är odelbara kan det hända att det inte finns någon rättvis fördelning. Till exempel, när det finns ett enda hus och två personer, kommer varje tilldelning av huset att vara orättvist mot en person. Därför har flera vanliga approximationer studerats, såsom maximin-share fairness (MMS) , avundsfrihet upp till ett objekt (EF1), proportionalitet upp till ett objekt (PROP1) och equitability upp till ett objekt (EQ1). Problemet med effektiv approximativt rättvis postallokering är att hitta en allokering som är både Pareto-effektiv (PE) och som uppfyller en av dessa rättvisa föreställningar. Problemet presenterades första gången 2016 och har väckt stor uppmärksamhet sedan dess.

Miljö

Det finns en ändlig uppsättning objekt, betecknad med M . Det finns n agenter. Varje agent i har en värdefunktion Vi _, som tilldelar ett värde till varje delmängd av objekt. Målet är att dela upp M i n delmängder, Xi _, ..., Xn _att , och ge varje delmängd _Xi till agent i , så allokeringen är både Pareto-effektiv och ungefärlig rättvis. Det finns olika föreställningar om ungefärlig rättvisa.

Effektiv ungefär avundsfri tilldelning

En tilldelning kallas avundsfri (EF) om för varje agent tror att värdet på hans/hennes andel är minst lika högt som för någon annan agent. Det kallas avundsfritt upp till ett föremål (EF1) om, för varannan agent i och j, om högst ett föremål tas bort från paketet med j, så avundas i inte j. Formellt:

$\forall i,j:~~~\exists Y\subseteq X_{j}:~~~|Y|\leq 1, ~~~V_{i}(X_{i})\geq V_{i}(X_{j}\setminus Y)$

Vissa tidiga algoritmer kunde hitta en ungefär rättvis allokering som tillfredsställer en svag form av effektivitet, men inte PE.

Round -robin -proceduren returnerar en komplett EF1-allokering med additivverktyg . Avundsgraf - proceduren returnerar en fullständig EF1-allokering för godtyckliga monotona preferensrelationer. Båda kommer garanterat att returnera en tilldelning utan avundscykler. Tilldelningen är dock inte garanterad att vara Pareto-effektiv.
Approximate -CEEI-mekanismen returnerar en partiell EF1-allokering för godtyckliga preferensrelationer. Det är PE för de allokerade objekten, men inte PE för alla objekt (eftersom vissa objekt kan förbli oallokerade).

Detta väckte frågan om att hitta en allokering som är både PE och EF1.

Maximal Nash Welfare regel

Caragiannis, Kurokawa, Moulin, Procaccia, Shah och Wang var de första som bevisade att det fanns en PE+EF1-tilldelning. De bevisade att, när alla medel har positiva tillsatser , är varje allokering som maximerar produkten av verktyg (även känd som Nash-välfärden ) EF1. Eftersom det är uppenbart att den maximerande allokeringen är PE, följer förekomsten av PE+EF1-allokering.

Även om maxproduktallokeringen har önskvärda egenskaper, kan den inte beräknas i polynomtid: att hitta en maxproduktallokering är NP-hård och till och med APX-hård . Detta ledde till olika arbeten som försökte approximera den maximala produkten, med förbättrade approximationsfaktorer:

Cole och Gkatzelis presenterade en approximation på 2,89 faktorer.
Anari, Gharan, Saberi och Singh presenterade en e-faktorapproximation.
Cole, Devanur, Gkatelis, Jain, Mai, Vazirani och Yazdanbod presenterade en 2-faktors approximation.

Dessa uppskattningar garanterar dock inte EF1. Några nyare algoritmer garanterar både ungefärlig maxprodukt och rättvisa:

Barman, Krishanmurthy och Vaish presenterar en algoritm som garanterar PE, (1+epsilon)-EF1 och en approximation på 1,45 till maxprodukten, i pseudopolynomisk tid (se algoritm för ökande pris nedan).
Garg och McGlaughlin presenterar en algoritm som garanterar PE, PROP1 och en 2-approximation till maxprodukten, i starkt polynomisk tid.
Caragiannis, Gravin och Huang presenterar en algoritm som garanterar EFX, PROP1 och en 2,9-approximation till maxprodukten, genom att kassera vissa varor (de visar också att det finns en 2-ungefärlig allokering).

Max-produktlösningen är särskilt tilltalande när värderingarna är binära (värdet på varje artikel är antingen 0 eller 1):

Amanatidis, Birmpas, Filos-Ratsikas, Hollender och Voudouris bevisar att med binära värderingar är maxproduktslösningen inte bara EF1 utan även EFX (avundsfri upp till någon nytta). Detta gäller när värdet på varje objekt kan ha ett av två värden - inte nödvändigtvis 0 eller 1. Med allmänna additiva värderingar innebär max-product inte EFX utan en naturlig generalisering av det.
Halpern, Procaccia, Psomas och Shah bevisar att med binära värderingar kan maxproduktregeln med lexikografiskt tie-breaking beräknas i polynomtid, och den är också gruppstrategisäker .

Icke-additiva värderingar

Om agenternas hjälpmedel inte är additiv, är max-produktlösningen inte nödvändigtvis EF1; men om agenternas verktyg är åtminstone submodulära , uppfyller max-product-lösningen en svagare egenskap som kallas Marginal-Envy-Freeness except-1-item ( MEF1): det betyder att varje agent i värderar sin bunt minst lika mycket som marginell nytta av (bunten av j med det bästa föremålet borttaget från det). Formellt:

$\forall i,j:~~~\exists Y\subseteq X_{j }:~~~|Y|\leq 1,~~~V_{i}(X_{i})\geq V_{i}(X_{i}\cup (X_{j}\setminus Y))-V_ {i}(X_{i})$

Liknande approximationer har hittats för mer allmänna hjälpfunktioner:

Bei, Garg, Hoefer och Mehlhorn och Anari, Mai, Gharan och Vazirani studerar marknader med flera enheter av varje objektstyp, där värderingarna är åtskiljbara [ sic ? ] styckvis linjär konkav . Detta innebär att nyttan av ett paket med olika föremålstyper är summan av nyttigheter för varje enskild föremålstyp (detta är betydelsen av "separerbar"), men för varje föremålsslag har värderingen minskande marginella nyttigheter ( detta är betydelsen av "styckvis linjär konkav"). De ger en 2-approximation till maxprodukten.
Ortega studerar en marknad med flera enheter med binära värderingar. Han bevisar att den egalitära regeln är Lorenz-dominant (en egenskap som är starkare än leximinoptimalitet), unik i verktyg och gruppstrategisäker .
Garg, Hoefer och Mehlhorn studerar budgetadditiva värderingar - en underklass av submodulära verktyg. De ger en (2,404 + ε )-approximation till maxprodukten i tidspolynom i ingångsstorleken och 1/ ε.
Benabbou, Chakraborty, Igarashi och Zick studerar submodulära verktyg med binära marginella vinster (dvs varje objekt lägger till antingen 0 eller 1 till värdet av varje paket). De bevisar att med sådana värderingar är både maxprodukten och leximintilldelningen EF1 och maximerar den utilitaristiska välfärden (summan av nyttigheter).
Babaioff, Ezra och Feige studerar också submodulära verktyg med binära ("dikotoma") marginella vinster. De presenterar en deterministisk sanningsenlig mekanism som ger en Lorenz-dominant allokering, som alltså är EFX och max-produkt.

Blandade värderingar

Martin och Walsh visar att, med "blandad manna" (- additivvärderingar som kan vara både positiva och negativa), säkerställer maximering av produkten av verktyg (eller minimering av produkten av minus verktygen) inte EF1. De bevisar också att en EFX3-allokering kanske inte existerar även med identiska verktyg. Men med tertiära verktyg finns det alltid EFX- och PO-allokeringar, eller EFX3- och PO-allokeringar; och med identiska verktyg finns det alltid EFX- och PO-allokeringar. För dessa fall finns polynom-tidsalgoritmer.

Algorithm för ökande pris

Barman, Krishanmurthy och Vaish presenterade en pseudopolynomisk tidsalgoritm för att hitta PE+EF1-allokeringar för positiva additivvärderingar. De bevisade följande resultat.

Algoritmen hittar en PE+EF1-allokering i tiden O(poly( m , n , v _max )), där m är antalet objekt, n antalet agenter och v _max det största värdet av en artikel (alla värderingar) är heltal).
Samma algoritm ger en approximation på 1,45 till den maximala Nash-välfärden.
Algoritmen bevisar också att det finns en allokering som är både EF1 och paretooptimal .

Grundläggande koncept

Deras algoritm är baserad på idén om konkurrenskraftig jämvikt på en Fisher-marknad . Den använder följande begrepp.

Ungefärlig EF1-allokering : Givet en konstant e > 0, är en allokering e -EF1 om den uppfyller EF1-villkoret upp till en multiplikationskonstant på (1+ e ). Formellt:
- $\forall i,j:~~~\exists Y\subseteq X_{j}:~~~| Y|\leq 1,~~~(1+e)\cdot V_{i}(X_{i})\geq V_{i}(X_{j}\setminus Y)$
Pris-vektor : en vektor som tilldelar ett pris (ett reellt tal) till varje artikel.
Bang-for-buck-förhållande : för en agent i och ett objekt o är det förhållandet mellan agentens värdering av föremålet och föremålets pris: v _ij / p _j .
Maximal bang-for-buck (MBB) set : för en agent i är det uppsättningen objekt som maximerar hans bang-for-buck-förhållande (givet en pris-vektor p ).
MBB-allokering : en allokering där varje agent endast tar emot objekt från sin MBB-uppsättning. I en MBB-allokering maximerar varje agent sin nytta givet sin budget (men MBB-allokering är ett starkare villkor). Det första välfärdsteoremet antyder att en MBB-allokering är bråkdels Pareto-optimal .
Prisavundsfri (pEF) allokering : en allokering X där, för varannan agent i . j , priset på X _i (kallat "inkomsten" av i) är minst lika stort som priset X _j . Detta innebär att alla inkomster är identiska. Dessutom är en allokering som är både MBB och pEF fri från avundsjuka , eftersom varje agent maximerar sin nytta med tanke på sin inkomst, och alla andra agenter har samma inkomst.
Pris-avundsfri-utom-en (pEF1) allokering : en tilldelning där jag för varannan agent i . j , priset p( X _i ) är minst lika stort som priset på Xj utan dess dyraste artikel. Detta inte att inkomsterna är identiska. En allokering som är både MBB och pEF1 är emellertid också EF1.
e -pEF1-allokering , för någon konstant e > 0: en allokering där, för varannan agent i . j , produkten (1+ e )·p( X _i ) är minst lika stor som p( Xj ) utan dess dyraste artikel. Observera att e -pEF1-tillståndet är svagare när e är större. Speciellt är en pEF1-allokering e -pEF1 för varje e > 0, men motsatsen är inte sant. En allokering som är både MBB och e -pEF1 är också e -EF1 .
Minsta spenderare : Givet en allokering och en prisvektor är det agenten i så att p( X _i ) är minst (banden bryts baserat på någon förspecificerad ordning av agenterna). Observera att en allokering är e -pEF1 om e -pEF1-villkoret är uppfyllt för den minst spenderare (som agent i ).
MBB Hierarki för agent i (given alllokering X och prisvektor p ): en trädstruktur byggd på följande sätt.
- Sätt agent i vid roten (detta kallas nivå 0).
- Anslut till agent i alla objekt i hans MBB-uppsättning (med tanke på prisvektorn p ).
- Anslut till varje objekt av agenten som äger det i X , om det ännu inte finns i trädet (detta kallas nivå 1)
- Anslut till varje agent på nivå 1, alla objekt i hans MBB-uppsättning som ännu finns i trädet.
- Fortsätt att lägga till agenter och objekt omväxlande på liknande sätt: för varje agent, lägg till hans MBB-objekt; för varje artikel, lägg till dess ägande agent.
Överträdare (given alllokering X och prisvektor p ): en agent h som bryter mot pEF1-villkoret med hänsyn till den minst spenderande i . Så priset på X _h , även när den dyraste artikeln tas bort från den, är högre än p ( X _i ). På liknande sätt e -violator en agent som bryter mot e -pEF1-villkoret med hänsyn till den minst spenderande.
Sökvägsöverträdare (given allokering X och prisvektor p och MBB-hierarkin): en agent h som förekommer på MBB-hierarkin för den minst spenderade i , och delvis bryter mot pEF1-villkoret wrt i . Mer detaljerat: anta att det finns en bana, längs kanterna på MBB-hierarkin, från den minst spenderade i till objekt o , och sedan en kant från objekt o till agent h (detta betyder att X _h innehåller o ). Om p ( X _h \ { o }) > p ( X _i ), så är h en vägöverträdare. Observera att varje överträdare är en vägöverträdare, men motsatsen är inte sant. På liknande sätt, om p ( X _h \ { o } ) > (1+ e )· p ( X _i ), då är h en e -vägöverträdare .

Algoritm

Givet en parameter e , syftar algoritmen till att hitta en allokering som är både fPO och 3 e -pEF1. Det pågår i flera faser.

Fas 1: Konstruera en initial MBB-allokering+pris (X, p) .

Ett sätt att göra det är att ge varje objekt o till den agent i som värderar det högst (bryta band godtyckligt), och sätta priset på o till v _i,o . Detta garanterar att för varje agent är bang-for-buck för alla objekt i hans bunt exakt 1, och bang-for-buck för alla objekt i andra buntar är högst 1. Därför är allokeringen MBB, därav det är också fPO.
Om allokeringen är 3 e -pEF1, returnera den; fortsätt annars till fas 2.

Fas 2: Ta bort prisavundsjuka inom MBB-hierarkin :

Konstruera MBB-hierarkin för den minst spenderade, givet strömmen ( X , p ).
För L = 1,2,...:
- För varje agent h i nivå L i trädet:
  - Om h är en e -vägöverträdare längs vägen: i → ... → h' → o → h, överför sedan objekt o från agent h till agent h' (observera att allokeringen förblir MBB). Starta om fas 2.
När det inte finns fler e -path-violators:
- Om allokeringen är 3 e -pEF1, returnera den; fortsätt annars till fas 3.

Fas 3: Höj priserna . Öka priserna på alla objekt i MBB-hierarkin med samma multiplikationsfaktor tills en av följande tre saker händer:

Identiteten för den minst spenderande förändras. Detta kan hända om någon agent utanför hierarkin (vars varor inte ökar i pris) blir den minst spenderande. I det här fallet startar vi om i fas 2.
Ett nytt objekt läggs till i MBB-hierarkin. Detta kan hända eftersom, när priserna på objekt i hierarkin ökar med en faktor r , minskar BB-kvoten för objekt i hierarkin med r , medan BB-kvoten för objekt utanför hierarkin förblir densamma. Därför, när r är tillräckligt stor, kommer något externt objekt att bli MBB för någon hierarkiagent. Även i detta fall startar vi om i fas 2.
Den aktuella allokeringen X blir 3 e -pEF1. Detta kan hända eftersom, när priserna på objekt i hierarkin ökar, ökar inkomsten för de minst spenderande, medan inkomsten för agenter utanför hierarkin förblir konstant. Därför, när r är tillräckligt stor, är det möjligt att 3 e -pEF1-villkoret är uppfyllt med hänsyn till den minsta förbrukningen. I detta fall returnerar vi allokeringen X och det nya priset p .

Bevis på riktighet

Antag först att ovanstående algoritm exekveras på en instans där alla värden är potenser av (1+ e ), för vissa fasta e >0.

Den första utmaningen är att bevisa att algoritmen upphör. Det kan bevisas att, när alla värderingar är potenser av (1+ e ), slutar algoritmen i tiden O (poly(m, n, 1/ e , ln( V _max )), där V _max är det största värdet av ett objekt till en agent.
Den initiala allokeringen är en MBB-allokering, och alla operationer bibehåller detta tillstånd. Därför är den returnerade allokeringen MBB, så det är också fPO.
Enligt termineringsvillkoren, närhelst algoritmen avslutas, är den returnerade allokeringen 3 e -pEF1, så den är också 3 e -EF1.

Antag nu att vi har en instans med generella värderingar. Vi kör ovanstående algoritm på en avrundad instans , där varje värdering avrundas uppåt till närmaste potens av (1+ e ). Notera att för varje agent i och objekt o är det avrundade värdet Vi _' ( o ) avgränsat mellan Vi _o ( ) och (1+ e ) Vi _o ( ).

Enligt föregående stycke är den resulterande allokeringen fPO och 3 e -EF1 med avseende på den avrundade instansen.
För varje e tillräckligt liten (särskilt mindre än 1/6 m ³ V _max⁴ ), är en allokering som är fPO för den avrundade instansen PO för den ursprungliga instansen.
Genom att kombinera 3 e -EF1-garantin för den avrundade instansen, med gränsen för avrundning, får vi att den returnerade allokeringen uppfyller följande approximativa EF1-villkor:
- $\forall i,j:~~~\exists C\subseteq X_{ j}:~~~|C|\leq 1,~~~(1+e)\cdot (1+3e)\cdot V_{i}(X_{i})\geq V_{i}(X_{j }\setminus C)$
För tillräckligt litet e är produkten (1+ e )(1+3e ) högst (1+7e ) . Därför är en allokering som är 3 e -EF1 för den avrundade instansen 7 e -EF1 för den ursprungliga instansen.
Eftersom de ursprungliga värderingarna är heltal, när e är tillräckligt litet, är en 7 e -EF1-allokering också EF1.
Den resulterande allokeringen är alltså PO+EF1 för den ursprungliga instansen.

Generaliserad justerad vinnare

Aziz, Caragiannis, Igarashi och Walsh utökade villkoret för EF1 till blandade värderingar (objekt kan ha både positiva och negativa nytta). De presenterade en generalisering av det justerade vinnarförfarandet , för att hitta en PO+EF1-allokering för två agenter i tiden O( m ² ).

Effektiv approximativt proportionell allokering

En tilldelning av objekt är proportionell (PROP) om varje agent värderar sin andel minst 1/ n av värdet av alla objekt. Det kallas proportionell upp till en artikel (PROP1) om för varje agent i , om högst en artikel läggs till i paketet av i , då värderar i paketet minst 1/ n av totalen. Formellt, för alla i (där M är mängden av alla varor):

$\exists Y\subseteq M\setminus X_{i}:~~~|Y|\leq 1,~~~V_{ i}(X_{i}\kopp Y)\geq V_{i}(M)/n$ .

PROP1-villkoret infördes av Conitzer, Freeman och Shah i samband med rättvist offentligt beslutsfattande. De bevisade att det i detta fall alltid finns en PE+PROP1-allokering.

Eftersom varje EF1-allokering är PROP1, finns en PE+PROP1-allokering också i odelbar postallokering; frågan är om sådana tilldelningar kan hittas med snabbare algoritmer än de för PE+EF1.

Barman och Krishnamurthy presenterade en stark-polynom-tidsalgoritm som hittade en PE+PROP1-allokering för varor (objekt med positiv nytta).

Branzei och Sandomirskiy utökade villkoret för PROP1 till sysslor (objekt med negativ användbarhet). Formellt, för alla jag :

$\exists Y\subseteq X_{i}:~~~|Y|\leq 1,~~~V_{i}( X_{i}\setminus Y)\geq V_{i}(M)/n$ .

De presenterade en algoritm för att hitta en PE+PROP1-allokering av sysslor. Algoritmen är starkt-polynomisk-tid om antingen antalet objekt eller antalet agenter (eller båda) är fasta.

Aziz, Caragiannis, Igarashi och Walsh utökade villkoret för PROP1 till blandade värderingar (objekt kan ha både positiva och negativa egenskaper). I den här inställningen kallas en allokering PROP1 om, för varje agent i , om vi tar bort ett negativt objekt från i:s paket, eller lägger till ett positivt objekt till i:s paket, då i:s nytta är minst 1/ n av totalen. Deras Generalized Adjusted Winner-algoritm hittar en PE+EF1-allokering för två agenter; en sådan tilldelning är även PROP1.

Aziz, Moulin och Sandomirskiy presenterade en starkt polynomisk tidsalgoritm för att hitta en allokering som är bråkdel-PE (starkare än PE) och PROP1, med generella blandade värderingar, även om antalet agenter eller objekt inte är fixerat, och även om agenterna har olika rättigheter.

Effektiv ungefär rättvis fördelning

En allokering av objekt kallas equitable (EQ) om det subjektiva värdet av alla agenter är detsamma. Motivationen för att studera denna uppfattning kommer från experiment som visar att mänskliga försökspersoner föredrar rättvisa tilldelningar framför avundsfria. En allokering kallas equitable upp till en post (EQ1) om, för varannan agent i och j, om högst en post tas bort från bunten av j, då är det subjektiva värdet av i åtminstone det för j. Formellt, för all i , j :

$\exists Y\subseteq X_{j}:~~~|Y|\leq 1,~~~V_{i}(X_ {i})\geq V_{j}(X_{j}\setminus Y)$ .

En starkare föreställning är rättvis upp till vilken post som helst (EQx) : för varje två agenter i och j, om någon enskild artikel tas bort från paketet av j, så är det subjektiva värdet av i åtminstone det för j:

$\forall y\in X_{j}:~~~V_{i}(X_{i})\ geq V_{j}(X_{j}\setminus \{y\})$ .

EQx-tilldelningar studerades först av Gourves, Monnot och Tlilane, som använde en annan term: "nära svartsjukefri". De bevisade att en partiell EQx-allokering av alltid existerar, även med det ytterligare kravet att föreningen av alla allokerade varor är en grund för en given matroid . De använde en algoritm som liknar envy-graph-proceduren . Suksompong bevisade att en EQ1-tilldelning existerar även med det ytterligare kravet att alla tilldelningar måste vara sammanhängande delmängder av en linje.

Freeman, Sidkar, Vaish och Xia visade följande starkare resultat:

När alla värderingar är strikt positiva existerar alltid en PE+EQx-allokering, och det finns en pseudopolynomisk tidsalgoritm som hittar en PE+EQ1-allokering.
När vissa värderingar kan vara noll, kanske inte ens en PE+EQ1-allokering existerar, och att avgöra om en PE+EQ/EQ1/EQx existerar är starkt NP-svårt .
En PE+EQ1+EF1-allokering kanske inte finns. Att bestämma om det existerar är starkt NP-svårt , men polynom-tid lösbart med binära (0 eller 1) värderingar.

Algoritmer för ett litet antal agenter

Bredereck, Kaczmarcyk, Knop och Niedermeier studerar en miljö där det finns få agenter (liten n ) och få föremålstyper (liten m ), nyttan per föremålstyp är övre gräns (av V ), men det kan finnas många föremål av varje typ. För den här inställningen bevisar de följande metasats (sats 2): Givet ett effektivitetskriterium E och ett rättvisekriterium F, om $n+u_{\max }+m$ är fast , då är det möjligt att avgöra i polynomtid om det finns en allokering som är både E-effektiv och F-rättvis, så länge som E och F uppfyller följande egenskaper:

Rättvisa : Frågan om en F-rättvis allokering existerar kan modelleras av ett linjärt heltalsprogram med en fast dimension.
Effektivitet : Frågan om det finns en allokering som E-dominerar en annan given allokering kan modelleras av ett heltalsprogram vars dubbla träddjup , och absolutvärdet av den största koefficienten, är övre gränsade av någon funktion $f(n,u_{\max })$ .

Sedan bevisar de att flera vanliga kriterier för rättvisa och effektivitet uppfyller dessa egenskaper, inklusive:

Rättvisebegrepp : avundsfrihet, EF1, EFx, graf-EF (när agenterna bara avundas sina grannar på en fast graf), jämlikhet, maximin-share och genomsnittlig grupp-avundsfrihet (där varje grupp av agenter värdesätter sin andel som det aritmetiska medelvärdet av medlemmarnas nyttigheter).
Effektivitetsbegrepp : Pareto-effektivitet, graf Pareto-effektivitet (där Pareto-dominans endast beaktar utbyten mellan grannar på en fast graf) och grupp-Pareto-effektivitet. En allokering X som k-grupp-Pareto-effektiv (GPE _k ) om det inte finns någon annan allokering Y som är minst lika bra (med aritmetiskt medelvärde av verktyg) för alla grupper av storlek k , och strikt bättre för minst en grupp av storlek k . Observera att GPE ₁ motsvarar Pareto-effektivitet. GPE _n är ekvivalent med en utilitaristisk-maximal allokering, eftersom för den stora gruppen G av storlek n är det aritmetiska medelvärdet ekvivalent med summan av alla agenters nyttigheter. För alla k innebär GPE _{k+1 GPE}_k .

Körtiden för deras algoritm är polynom i indatastorleken (i bitar) gånger $d^{2.5d}$ , där d är antalet variabler i den resulterande ILP, vilket är $d=m(n+1)+m(n+1)\cdot ( 4\cdot (4n\cdot V+1)^{n})^{m(n+1)}$ .

De utvecklade senare mer praktiska algoritmer för några av dessa problem.

Se även

Fraktionell Pareto-effektivitet#Hitta rättvisa och fPO-tilldelningar

Se även

Effektiv avundsfri uppdelning - för delbara resurser. Det finns inget behov av uppskattningar eftersom exakt rättvisa är möjlig.
Avundsfri föremålstilldelning - utan krav på PE.
Hyresharmoni - med en ytterligare begränsning att varje agent måste få en enda vara.