A Family of Convex Models to Achieve Fairness through Dispersion Control
Authors
Abhay Singh Bhadoriya
Deepjyoti Deka
Kaarthik Sundar
Abstract
Controlling the dispersion of a subset of decision variables in an optimization problem is crucial for enforcing fairness or load-balancing across a wide range of applications. Building on the well-known equivalence of finite-dimensional norms, the note develops a family of parameterized convex models that regulate the dispersion of a vector of decision-variable values through its coefficient of variation. Each model contains a single parameter that takes a value in the interval $[0,1]$. When the parameter is set to zero, the model imposes only a trivial constraint on the optimization problem; when set to one, it enforces equality of all the decision variables. As the parameter varies, the coefficient of variation is provably bounded above by a monotonic function of that parameter. The note also presents theoretical results that relate the space of feasible solutions to all the models. Finally it compares the models' solution quality on a variant of the assignment problem that regulates the dispersion in the assignment costs.
