Fair solutions for some multiagent optimization problems

Abstract We consider optimization problems in a multiagent setting where a solution is evaluated with a vector. Each coordinate of this vector represents an agent’s utility for the solution. Due to the possible conflicts, it is unlikely that one feasible solution is optimal for all agents. Then, a natural aim is to find solutions that maximize the satisfaction of the least satisfied agent, where the satisfaction of an agent is defined as his relative utility, i. e. , the ratio between his utility for the given solution and his maximum possible utility. This criterion captures a classical notion of fairness since it focuses on the agent with lowest relative utility. We study worst-case bounds on this ratio: for which ratio a feasible solution is guaranteed to exist, i. e. , to what extend can we find a solution that satisfies all agents? How can we build these solutions in polynomial time? For several optimization problems, we give polynomial-time deterministic algorithms which (almost always) achieve the best possible ratio.

Authors

• Bruno Escoffier
• Laurent Gourvès Université Paris-Dauphine, Université PSL, CNRS, LAMSADE, 75016, Paris, France
• Jérôme Monnot University of Paris-Dauphine

Keywords

• Multiagent optimization
• Combinatorial optimization
• Fairness