Maximizing Coverage While Ensuring Fairness: A Tale of Conflicting Objectives

Abolfazl Asudeh, Tanya Y. Berger-Wolf, Bhaskar DasGupta, Anastasios SidiropoulosAlgorithmica 2023 · OpenReview

Abstract

Ensuring fairness in computational problems has emerged as a key topic during recent years, buoyed by considerations for equitable resource distributions and social justice. It is possible to incorporate fairness in computational problems from several perspectives, such as using optimization, game-theoretic or machine learning frameworks. In this paper we address the problem of incorporation of fairness from a combinatorial optimization perspective. We formulate a combinatorial optimization framework, suitable for analysis by researchers in approximation algorithms and related areas, that incorporates fairness in maximum coverage problems as an interplay between two conflicting objectives. Fairness is imposed in coverage by using coloring constraints that minimizes the discrepancies between number of elements of different colors covered by selected sets; this is in contrast to the usual discrepancy minimization problems studied extensively in the literature where (usually two) colors are not given a priori but need to be selected to minimize the maximum color discrepancy of each individual set. Our main results are a set of randomized and deterministic approximation algorithms that attempts to simultaneously approximate both fairness and coverage in this framework.

Introduction

The classic Maximum Coverage Problem (MCP) is a cornerstone of operations research, used for critical infrastructure decisions like placing cell towers or school locations. The goal is straightforward: given a collection of sets, select $k$ of them to cover as many unique elements as possible. However, standard MCP is "demographically blind." By optimizing solely for total reach, it can inadvertently neglect minority groups—a phenomenon known as "redlining."

This paper formalizes the Fair Maximum Coverage (FMC) problem, a framework that balances resource reach with the requirement of equitable distribution across different demographic groups. The authors introduce fairness by assigning "colors" (attributes) to elements. A solution is considered fair if the proportion of covered elements of each color matches a pre-specified target. The core challenge lies in the fact that coverage and fairness are often conflicting objectives: the most equitable solution may cover significantly fewer individuals than the most efficient one.

Problem Formulation and Complexity

The authors approach FMC through the lens of combinatorial optimization. A striking finding of the research is the Feasibility Trap: even determining if a perfectly fair solution exists is NP-complete. This necessitates the development of approximation algorithms—methods guaranteed to find solutions within a mathematically defined distance of the optimal result.

Figure 1: A graph-theoretic illustration of the Fair Maximum Coverage problem, where nodes and edges represent sets and elements with distinct color attributes.

In graph-based versions of the problem (NODE-FMC), elements are represented as edges of different colors, and the goal is to select a subset of vertices to cover these edges while maintaining color balance. As illustrated in Figure 1, the interplay between node sets and edge colors creates a complex landscape where selecting a vertex to increase total coverage might simultaneously skew the fairness ratio, highlighting the inherent trade-offs in the framework.

Methodology

To navigate the NP-hard nature of FMC, the authors employ several sophisticated techniques:

  1. Strengthened LP Relaxations: The problem is modeled using Linear Programming (LP), with added "covering inequalities" to tighten the gap between fractional mathematical models and real-world discrete set selections.
  2. Randomized Rounding: Using Srinivasan’s sampling, the authors convert fractional LP solutions into whole sets. This ensures selected sets are "negatively correlated," allowing the use of statistical tools like Azuma’s Inequality to prove that algorithms stay close to fairness targets with high probability.
  3. Iterated Rounding: For deterministic results, an iterative approach solves the LP, fixes the most certain variables based on the "Rank Lemma," and resolves the remaining problem.
  4. Geometric Shifting: For spatial versions of the problem (e.g., elements as points in space), a random shifting technique decomposes the space into manageable grids.

Key Results and Insights

The authors provide a suite of algorithms depending on specific constraints:

  • Randomized Algorithms: Achieve the standard $1 - 1/e$ ($\approx 63\%$) approximation ratio for coverage, while keeping color discrepancies within a factor of the element frequency ($f$).
  • Deterministic NODE-FMC: For graph-based coverage, they achieve a $1/2$ approximation for coverage with a fairness bound proportional to the number of colors.
  • Segregated FMC: In cases where each set contains only one demographic color, they achieve near-optimal $1 - 1/e$ coverage with a tight fairness bound of 2.

A fundamental insight is the "Frequency" Penalty: the number of sets an element belongs to ($f$) acts as a bottleneck. In highly overlapping systems, fairness is mathematically harder to maintain. The paper quantifies the "price of fairness," demonstrating that a fair solution might cover significantly fewer elements (e.g., 6 edges) compared to an unfair optimal (e.g., 11 edges).

Conclusion

This work provides a rigorous foundation for incorporating social justice into resource allocation. While the current algorithms provide strong guarantees, future work could explore Semidefinite Programming (SDP) to further close the fairness gap. Additionally, extending the framework to submodular functions—where the utility of additional coverage decreases—remains a major open challenge for reflecting real-world utility more accurately.

Summary updated

Abstract

Ensuring fairness in computational problems has emerged as a key topic during recent years, buoyed by considerations for equitable resource distributions and social justice. It is possible to incorporate fairness in computational problems from several perspectives, such as using optimization, game-theoretic or machine learning frameworks. In this paper we address the problem of incorporation of fairness from a combinatorial optimization perspective. We formulate a combinatorial optimization framework, suitable for analysis by researchers in approximation algorithms and related areas, that incorporates fairness in maximum coverage problems as an interplay between two conflicting objectives. Fairness is imposed in coverage by using coloring constraints that minimizes the discrepancies between number of elements of different colors covered by selected sets; this is in contrast to the usual discrepancy minimization problems studied extensively in the literature where (usually two) colors are not given a priori but need to be selected to minimize the maximum color discrepancy of each individual set. Our main results are a set of randomized and deterministic approximation algorithms that attempts to simultaneously approximate both fairness and coverage in this framework.
BibTeX
@inproceedings{asudeh2023maximizing,
  author = {Abolfazl Asudeh and Tanya Y. Berger-Wolf and Bhaskar DasGupta and Anastasios Sidiropoulos},
  title = {{Maximizing Coverage While Ensuring Fairness: A Tale of Conflicting Objectives}},
  booktitle = {Algorithmica},
  year = {2023},
  url = {https://openreview.net/forum?id=emgMsIFqQyw},
}
Figure