A Unified Framework for Max-Min and Min-Max Fairness With Applications
By Bozidar Radunovic, J. L. Boudec. 2007
372 citations recorded by the source corpus.
Max-min fairness is widely used in various areas of networking. In every case where it is used, there is a proof of existence and one or several algorithms for computing it; in most, but not all cases, they are based on the notion of bottlenecks. In spite of this wide applicability, there are still examples, arising in the context of wireless or peer-to-peer networks, where the existing theories do not seem to apply directly. In this paper, we give a unifying treatment of max-min fairness, which encompasses all existing results in a simplifying framework, and extend its applicability to new examples. First, we observe that the existence of max-min fairness is actually a geometric property of the set of feasible allocations. There exist sets on which max-min fairness does not exist, and we describe a large class of sets on which a max-min fair allocation does exist. This class contains, but is not limited to the compact, convex sets of RN. Second, we give a general purpose centralized algorithm, called max-min programming, for computing the max-min fair allocation in all cases where it exists (whether the set of feasible allocations is in our class or not). Its complexity is of the order of N linear programming steps in RN, in the case where the feasible set is defined by linear constraints. We show that, if the set of feasible allocations has the free disposal property, then max-min programming reduces to a simpler algorithm, called water filling, whose complexity is much lower. Free disposal corresponds to the cases where a bottleneck argument can be made, and water filling is the general form of all previously known centralized algorithms for such cases. All our results apply mutatis mutandis to min-max fairness. Our results apply to weighted, unweighted and util-max-min and min-max fairness. Distributed algorithms for the computation of max-min fair allocations are outside the scope of this paper.
Subfields: Computer Networks and Communications, Electrical and Electronic Engineering
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computer Networks and Communications
- Ion Stoica
- Tian Li
- Mosharaf Chowdhury
- Sylvia Ratnasamy
- Virginia Smith
- Maziar Sanjabi
- Ertan Onur
- Arvind Krishnamurthy
In Electrical and Electronic Engineering
- Virginia Smith
- Tian Li
- Ertan Onur
- Ignas G. Niemegeers
- R. Venkatesha Prasad
- Sylvia Ratnasamy
- Dimitris J. Bertsimas
- Maziar Sanjabi
Citations in the corpus
- Fair Resource Allocation in Federated Learning (2019, background): “• Synthetic: We follow a similar set up as that in Shamir et al. (2014) and impose additional heterogeneity.”
- FairCloud: sharing the network in cloud computing (2012, background): “2 Previous work [22] has shown that the maximal lexicographical allocation is equivalent to max-min for multi-path routing, a problem to which network proportionality can be reduced to.”
- The Price of Fairness (2011, background): “…applications in communication networks (Bertsekas and Gallager (1987), Kelly et al. (1997), Luo et al. (2004), Luss (1999), Ogryczak et al. (2005), Radunovic and Boudec (2002), Radunovic and Boudec (2004)), the Air Traffic Flow Management problem (Bertsimas and Gupta (2010), Bertsimas…”
- Fairness in Wireless Networks:Issues, Measures and Challenges (2014, background): “Min-max fairness is contrary to max-min fairness, which is discussed in [20].”