Vi studerar problemet med att rättvist fördela en uppsättning odelbara varor till en uppsättning människor ur ett algoritmiskt perspektiv. Rättvis uppdelning har varit ett centralt ämne i den ekonomiska litteraturen och flera rättvisebegrepp har föreslagits. Kriteriet som vi fokuserar på är avundsfrihet. I vår modell är en monoton allmännyttig funktion associerad med varje spelare som anger värdet av varje delmängd av varorna för spelaren. En tilldelning är avundsfri om varje spelare föredrar sin egen andel än någon annan spelares andel. När varorna är delbara finns alltid avundsfria tilldelningar. I närvaro av odelbarheter visar vi att det finns tilldelningar där avunden begränsas av den maximala marginalnyttan och presenterar en enkel algoritm för beräkning av sådana tilldelningar. Vi tittar sedan på optimeringsproblemet med att hitta en tilldelning med minsta möjliga avundsjuka. I det allmänna fallet är problemet inte löst eller ungefärligt i polynom tid om inte P = NP. Vi betraktar naturliga specialfall (t.ex. additiva verktyg) som har ett nära samband med problem med arbetsschemaläggningen. Tillnärmningsalgoritmer samt otillåtliga resultat erhålls. Slutligen undersöker vi problemet med att utforma sanningsenliga mekanismer för att producera tilldelningar med begränsad avund.
Lipton m.fl. REF undersökte avundsfria mekanismer i samband med odelbara poster med fokus på beräknings komplexiteten i att hitta tilldelningar med minsta avund.
On approximately fair allocations of indivisible goods
{'venue': "EC '04", 'journal': None, 'mag_field_of_study': ['Computer Science']}