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

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. [ABSTRACT FROM AUTHOR]