Location: MF 12

Speaker: Sten Wessel (TU/e)

Title: Fairness in Graph-Theoretical Optimization Problems

Abstract:
There is arbitrariness in optimum solutions of graph-theoretic problems that can give rise to unfairness. We show how existing approaches that deal with this unfairness are connected to well-known graph-theoretic properties. In this work, we analyze in detail two fairness measures that are based on finding a probability distribution over the set of solutions. One measure guarantees uniform fairness, i.e. entities have equal chance of being part of the solution when one is sampled from this probability distribution. The other measure maximizes the minimum probability for every entity of being selected in a solution. In particular, we reveal that computing these individual fairness measures is in fact equivalent to computing the fractional covering number and the fractional partitioning number of a hypergraph. In addition, we show that for a general class of problems that we classify as independence systems, these two measures coincide. Finally, we analyze how not only fairness can be described for individuals, but also for how for groups of individuals we can achieve fairness by requiring representation of the group in a solution.