Lexicographic Min-Max Fairness in Task Assignments

Assignment problems and their variants are ubiquitous across resource allocation applications. While they traditionally focus on minimizing costs or maximizing utility, fairness is also an important consideration, especially for task assignment in multi-agent systems. We propose algorithms for assigning tasks to agents that consider lexicographic min-max fairness, a stronger notion of fairness than min-max fairness, which minimizes the maximum cost to any single agent. We apply our proposed approaches to both one-to-one and one-to-many assignment problems. Due to the computational challenges of one-to-many task assignments, we develop tractable approaches to achieve approximate fairness. Finally, we use the proposed methods to evaluate the trade-offs between efficiency and fairness through numerical experiments.