Vi betraktar problemet med en rättvis fördelning av odelbara kollektiva nyttigheter. Vi modellerar kollektiva nyttigheter som element med genomförbarhetsbegränsningar på vilka undergrupper av element som kan väljas, och antar att agenter har additiva verktyg över olika element. Vår modell generaliserar befintliga ramar såsom rättvist offentligt beslutsfattande och deltagande budgetering. Vi studerar en gruppvis rättvisa begrepp kallas kärnan, som generaliserar välstuderade begrepp om proportionalitet och Pareto effektivitet, och kräver att varje delmängd av agenter måste få ett resultat som är rättvist i förhållande till sin storlek. I motsats till vad som gäller för delbara kollektiva nyttigheter (där deltilldelning är tillåten) är kärnan inte garanterad att existera vid tilldelning av odelbara kollektiva nyttigheter. Våra primära bidrag är begreppet additiv approximation till kärnan (med en liten multiplikativ förlust), och polynom tid algoritmer som uppnår en liten additiv approximation, där additiv faktorn är i förhållande till den största nyttan av en agent för ett element. Om genomförbarhetsbegränsningarna definierar en matris, visar vi en additiv approximation av 2. Ett liknande tillvägagångssätt ger en konstant tillsats som är bunden när genomförbarhetsbegränsningarna definierar en matchning. För genomförbarhetsbegränsningar som definierar en godtycklig förpackning polytop med milda restriktioner, visar vi en additiv garanti som är logaritmisk i bredden på polytopen. Våra algoritmer är baserade på konvexa programmet för att maximera Nash social välfärd, men skiljer sig avsevärt från tidigare arbete i hur det används. Så vitt vi vet är vårt arbete det första som approximerar kärnan i odelbara miljöer.
För heltal tilldelning med förpackning begränsningar, vi utökar våra tekniker för att ge approximationer till begreppet kärna med gåvor i den fullständiga versionen REF.
Fair Allocation of Indivisible Public Goods
{'venue': "EC '18", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}