Computational Issues in Long-term Fairness Among Groups of Agents

Abstract

Fairness within groups is important to a very broad range of problems, from policies for battery-operated soccer robots to distributed traffic control. While no single action may be fair to everyone, it is possible to achieve long-term optimal fairness for everyone through choice of repeated actions. I explore the issue of achieving such long-term fairness among multiple agents, and provide a unified view of the problem and solutions to it. The issue of constructing long-term fair policies among multiple agents has not been well studied in the literature. I concentrate on the “average reward” utility model, where one’s utility is defined as the average of the rewards one has received from past interactions. Also, I focus on a particular definition of fairness, called “leximin” fairness, but most of the results apply to other measures as well. After examination of fairness through an infinite series of repeated actions, I extend analysis in several directions. First, I consider how to achieve as fair a result as possible given a finite series of actions, where the length of the series is not precisely known beforehand but rather is chosen from an unknown or stochastic distribution of time horizons. My solution guarantees the beneficiaries the fairest possible long-term results, minus a bounded worst-case loss due to the game ending unexpectedly. I show that finding sequences of actions with optimal worst-case loss is NP-hard, and I propose a family of approximation algorithms. Second, I examine stateful domains, where one’s choices have side-effects that influence the effects of actions in the future. I introduce a multi-objective genetic algorithm for finding good tradeoff points between beneficiaries utilities and their worst-case losses. Third, I focus on decision-making processes which have been decentralized in the form of hierarchies. I propose an algorithm based on my stochastic time-horizon solution, and show empirically that an agent hierarchy running that algorithm is able to achieve optimal long-term utilities.