Vi anser att en miljö där en enda delbar bra ("cake") måste delas mellan n spelare, var och en med en möjligen olika värdering funktion över bitar av kakan. För denna inställning, vi tar itu med problemet med att hitta divisioner som maximerar den sociala välfärden, med fokus på divisioner där varje spelare behöver för att få en sammanhängande bit av kakan. Vi visar att det för både utilitaristiska och jämlika sociala välfärdsfunktioner är NPhard att hitta den optimala uppdelningen. För den utilitaristiska välfärden ger vi en konstant faktor approximationsalgoritm, och bevisar att ingen FPTAS är möjlig om inte P=NP. För jämlik välfärd, visar vi att det är NP-hård att approximera den optimala till någon faktor mindre än 2. För det fall där antalet spelare är litet tillhandahåller vi en FPT (fast parameterfallbar) FPTAS för både utilitaristiska och jämlika välfärdsmål.
Aumann m.fl. REF undersökte problemet med att hitta en sammanhängande tilldelning som maximerar välfärden för både delbara och odelbara poster.
Computing Socially-Efficient Cake Divisions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}