In many real-world optimization tasks, the goal is to select a small set of items to satisfy a specific objective. For instance, in Information Propagation, one might seek a few "seed" users to maximize message spread. In Recommendation Systems, the aim is to suggest a small set of items that a user will find useful. However, these standard formulations often overlook two critical dimensions: fairness (satisfying multiple demographic groups or stakeholders simultaneously) and robustness (ensuring the solution remains effective even if some elements are removed or fail).
This paper, presented at AAAI 2021, introduces the Minimum Robust Multi-Submodular Cover for Fairness (MINRF) problem. MINRF asks for the smallest set $S$ such that for every group $i$, a target threshold $T_i$ is met even if any $r$ items are removed from $S$.
Theoretical Hardness and Verification
The authors prove that MINRF is computationally challenging. Specifically, it is inapproximable within a factor of $(1-\epsilon)\ln m$, where $m$ is the number of groups. Furthermore, verifying whether a set is robust against the removal of $r$ elements is inherently difficult, as a brute-force check involves evaluating $\binom{|S|}{r}$ subsets, which grows exponentially with $r$.
Proposed Algorithms
To address these challenges, the paper proposes three bicriteria approximation algorithms:
- RANDGR (Random Greedy): Designed for the non-robust case ($r=0$). It optimizes efficiency by randomly selecting a subset of unsatisfied constraints at each step, significantly reducing the number of computational queries compared to a standard greedy approach.
- ALG1: A specialized algorithm optimized for robustness against the removal of a single element ($r=1$).
- ALGR: A general algorithm for any $r$. It iteratively "hardens" a solution by identifying specific vulnerabilities—removals that cause the set to fail—and adding elements to patch those gaps.
Experimental Evaluation
The algorithms were evaluated on two real-world datasets: the Facebook (SNAP) dataset for Information Propagation (IP) and the MovieLens 20M dataset for Movie Recommendation (MR).
As shown in the experimental results, the proposed algorithms consistently outperform baseline heuristics. In terms of solution quality, the algorithms find much smaller sets $|S|$ than the "SEP" baseline (which represents a disjoint-set approach to robustness). In terms of efficiency, RANDGR and THRESGR (a threshold-based greedy variant) require significantly fewer queries than the standard GREEDY approach, particularly in the Movie Recommendation task.
The Robustness Bottleneck
While the algorithms are effective for small $r$, the computational cost increases drastically as the robustness requirement grows. This "verification bottleneck" is a key limitation of robust optimization.
The query count for most algorithms grows exponentially as $r$ increases from 2 to 6, reflecting the combinatorial explosion of possible failure subsets. This highlights the trade-off between achieving high levels of adversarial robustness and maintaining computational tractability.
Conclusion
The MINRF framework provides a robust and fair approach to multi-objective submodular optimization. By leveraging randomization and iterative hardening, the proposed algorithms achieve near-optimal solution sizes while maintaining practical efficiency for moderate robustness requirements. Future work may explore "average-case" robustness, where elements fail stochastically rather than adversarially, potentially offering further efficiency gains.
Summary updated