Almost Envy Freeness and Welfare Efficiency in Fair Division with Goods or Bads
share
We consider two models of fair division with indivisible items: one for goods and one for bads. For both models, we study four generalized envy freeness proxies (EF1 and EFX for goods, and 1EF and XEF for bads) and three common welfare (utilitarian, egalitarian and Nash) efficiency notions. We revealed a close relation between these properties that allow us to use for bads a few existing algorithms for goods. However, most existing algorithms for goods do not work for bads. We thus propose several new algorithms for the model with bads. Our new algorithms exhibit many nice properties. For example, with goods and additive valuations, Nash efficiency and EF1 can be achieved simultaneously. With bads, the problem was unresolved. In response, we propose a new negative Nash welfare and an algorithm for it that is further 1EF. We also give simple cases when these envy freeness proxies and welfare efficiency are attainable.
READ FULL TEXT