A parametric worst-case approach to fairness in cooperative games with transferable utility

• Published in: Theoretical computer science 2023-01, Vol.940, p.189-205
• Main Authors: Istrate, Gabriel, Bonchiş, Cosmin
• Format: Article
• Language: English
• Subjects: Approximation algorithms; Coalitional games; Entropy; Worst-case fairness
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2022.10.039

We study worst-case fairness in resource allocation and cooperative games with transferable utility, the stable division most dissimilar to a normative standard of fairness. Motivated by welfare economics, similarity is quantified using information-theoretic divergences. Worst-case fairness aims to parallel the spirit of the price of anarchy from noncooperative game theory, quantifying how much unfairness is compatible with coalitional rationality. Computing worst-case fairness is tractable in weighted voting games and classes of coalitional skill games, but NP-hard in highway allocation, induced-subgraph games and some task-count coalitional skill games. In these cases we show approximation algorithms that yield constant approximations. We also upper bound the performance of a Reverse Greedy algorithm on general convex games in terms of two game-specific constants. •We study worst-case fairness in resource allocation and cooperative games with transferable utility.•We consider the imputation in the core with the largest divergence with a fixed imputation, a ”standard of fairness”.•We study the problem for several classes of cooperative games with transferable utility.•In cases when worst-case fairness is intractable we give algorithms that produce an approximately worst-case fair imputation.