Fair division har dykt upp som ett mycket hett ämne i AI, och avund-frihet är utan tvekan det mest övertygande rättvisekonceptet. En tilldelning av odelbara objekt till agenter är avundsfri om ingen agent föredrar bunten av någon annan agent framför sin egen i termer av värde. Eftersom avundsfrihet sällan är ett genomförbart mål, finns det nyligen fokus på avslappning av definitionen. Ett tillvägagångssätt i denna riktning är att komplettera anslagen med betalningar (eller bidrag) till ombuden. Ett genomförbart mål är då att uppnå avundsfrihet när det gäller det totala värde en agent får av tilldelningen och subventionerna. Vi anser att det naturliga optimeringsproblemet med att beräkna tilldelningar som är avundslösa med hjälp av det minsta beloppet av subventioner. Eftersom problemet är NP-hård, fokuserar vi på utformningen av approximationsalgoritmer. På den positiva sidan presenterar vi en algoritm som för ett konstant antal agenter, ungefär motsvarar det minsta beloppet av subventioner inom alla nödvändiga noggrannhet, på bekostnad av en graciös ökning av körtiden. På den negativa sidan visar vi att för ett stort antal agenter är problemet med att minimera subventioner för avundsfrihet inte bara svårt att beräkna exakt (som ett folklore argument visar) utan också, vilket är ännu viktigare, svårt att uppskatta. * I den här artikeln följer vi en optimeringsstrategi. Vi definierar och studerar optimeringsproblemet SMEF (som står för Subsidiy Minimization for Envy-Frihet). Med tanke på ett tilldelningsproblem som består av poster och agenter med värdering av posterna, begär SMEF en tilldelning som är avundslös med hjälp av det minsta totala bidragsbeloppet. SMEF är NP-hård; detta följer av NP-hårdheten att avgöra om ett givet tilldelningsproblem har en avundsfri tilldelning eller inte. Därför använder vi oss av approximationsalgoritmer för SMEF. Eftersom multiplikativa approximativa garantier är hopplösa, är vårt mål att utforma algoritmer som löper i polynom-tid och beräkna en tilldelning som är avundslös med en mängd subventioner som inte överstiger det minsta möjliga beloppet av subventioner (benämns χ) med mycket. I synnerhet använder vi den totala värderingen av alla agenter för alla varor (benämns som summan v) som riktmärke och söker tilldelningar som är avundsfria med ett belopp på högst χ + ρ · summan v som subventioner. Målet för approximationsgarantin ρ för en algoritm är att vara så liten som möjligt. Vi inleder studien av SMEF och presenterar två resultat. På den positiva sidan utformar vi en algoritm som uppnår en godtycklig låg approximationsgaranti på  och > 0. När den tillämpas på tilldelning instanser med ett konstant antal agenter, använder algoritmen dynamisk programmering och körs i tid som är polynom i antalet objekt och 1/ på. På den negativa sidan visar vi att små och medelstora företag i allmänhet inte bara är svåra att lösa exakt, utan också svåra att uppskatta inom en liten konstant. Till skillnad från folklore reduktion 1 för att bevisa hårdhet av avund-frihet, våra bevis använder en ny approximation-bevarande minskning. Förutom att skilja det allmänna fallet från det med ständigt många agenter, vårt negativa resultat indikerar att uppnå goda approximativa garantier kommer att vara ett utmanande mål.
Dessutom övervägde REF optimeringsproblemet med att minimera subventionsbeloppet för att erhålla avundsfrihet för ett tilldelningsexempel.
Computing envy-freeable allocations with limited subsidies
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}