Alexander Søltoft

Computing Approximately Proportional Allocations of Indivisible Goods: Beyond Additive and Monotone Valuations

Although approximate notions of envy-freeness—such as envy-freeness up to one good (EF1)—have been extensively studied for indivisible goods, the seemingly simpler fairness concept of proportionality up to one good (PROP1) has received far less attention. For additive valuations, every EF1 allocatio