Balancing Notions of Equity: Trade-offs Between Fair Portfolio Sizes and Achievable Guarantees

Understand

Motivated by fairness concerns, we study the `portfolio problem': given an optimization problem with set $D$ of feasible solutions, a class $\mathbf{C}$ of fairness objective functions on $D$, and an approximation factor $\alpha \ge 1$, a set $X \subseteq D$ of feasible solutions is an $\alpha$-approximate portfolio if for each objective $f \in \mathbf{C}$, there is an $\alpha$-approximation for $f$ in $X$.

• Choosing the classes of top-$k$ norms, ordered norms, and symmetric monotonic norms as our equity objectives, we study the trade-off between the size $|X|$ of the portfolio and its approximation factor $\alpha$ for various combinatorial problems.
• For the problem of scheduling identical jobs on unidentical machines, we characterize this trade-off for ordered norms and give an exponential improvement in size for symmetric monotonic norms over the general upper bound.
• We generalize this result as the OrderAndCount framework that obtains an exponential improvement in portfolio sizes for covering polyhedra with a constant number of constraints.