Minimizing and balancing envy among agents using Ordered Weighted Average

EasyChair Preprint 2544

Abstract

In the problem of fair resource allocation, envy freeness is one of the most interesting fairness criterion as it ensures that no agent prefers the bundle of another agent. However, when considering indivisible goods, an envy-free allocation may not exist. In this paper, we investigate a new relaxation of envy freeness consisting in minimizing the Ordered Weighted Average (OWA) of the envy vector. The idea is to choose the allocation that is fair in the sense of the distribution of the envy among agents. The OWA aggregator is a well-known tool to express fairness in multiagent optimization. In this paper, we focus on fair OWA operators where the weights of the OWA are decreasing. When an envy-free allocation exists, minimizing OWA will return this allocation. However, when no envy-free allocation exists, one may wonder how fair min OWA allocations are.

After some definitions and description of the model, we show how to formulate the computation of such a min OWA allocation as a Mixed Integer Program. Then, we investigate the link between the min OWA allocation and other well-known fairness measures such as max min share and envy freeness up to one good or to any good.

Keyphrases: computational social choice, envy-freeness, fair division, indivisible goods, resource allocation

@booklet{EasyChair:2544,
  author    = {Parham Shams and Aurélie Beynier and Sylvain Bouveret and Nicolas Maudet},
  title     = {Minimizing and balancing envy among agents using Ordered Weighted Average},
  howpublished = {EasyChair Preprint 2544},
  year      = {EasyChair, 2020}}