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

arXiv: https://arxiv.org/abs/2311.03230 · HTML: https://mlsanity.com/paper/2311.03230/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Nov 2023.

## Built on by (most cited first, 4 of 4)

- [Navigating the Social Welfare Frontier: Portfolios for Multi-objective Reinforcement Learning](https://mlsanity.com/paper/2502.09724/) (2025)
- [Retriever Portfolios: A Principled Approach to Adaptive RAG](https://mlsanity.com/paper/2605.31176/) (2026)
- [Online Correlation Clustering: Simultaneously Optimizing All ℓp-norms](https://mlsanity.com/paper/2510.15076/) (2025)
- [Many Preferences, Few Policies: Towards Scalable Language Model Personalization](https://mlsanity.com/paper/2604.04144/) (2026)

## Abstract (arXiv)

Motivated by fairness concerns, we study the `portfolio problem': given an optimization problem with set D of feasible solutions, a class C of fairness objective functions on D, and an approximation factor α ≥ 1, a set X subseteq D of feasible solutions is an α-approximate portfolio if for each objective f ∈ C, there is an α-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 α 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. Our framework is based on a novel primal-dual counting technique that may be of independent interest. We also introduce a general IterativeOrdering framework for simultaneous approximations or portfolios of size 1 for symmetric monotonic norms, which generalizes and extends existing results for problems such as scheduling, k-clustering, set cover, and routing.