Fairness in non-convex systems
Corinne Touati, Hisao Kameda, Atsushi Inoie · 2005
Abstract — In general, the set of users utilities is bounded because of the limitation of resources. There may exist many Pareto optimal points in the set of users utilities. For selecting a Pareto optimum point, a family of fair-ness criteria, that contains the max-min fairness and a parameterized family of fairness (by Mo and Walrand), has been proposed and examined in some concrete networking contexts that result in specific convex utility sets. We newly examine general compact (closed and bounded) utility sets which include the specific utility sets as special cases. We first prove that each of the family of fairness criteria gives a unique fair (Pareto optimum) point if the utility set is convex. We find, however, counter-examples where each of the family of fairness criteria gives multiple fair points if the utility set is not convex. We propose an extention of the family of fairness criteria such that each of them gives only a unique fair point regardless of whether the utility set is convex or not, to which we give proofs. By using a specific load balancing model, we illustrate the counter-examples and how each criterion of our extended fair family gives a unique fair point. Index Terms — Fairness, convex and non-convex systems, Pareto optimality, max-min fairness, proportional fairness, mathematical programming / optimization, load balancing, distributed computer systems. I.