Performative Submodular Decision Making

Modern decision-making systems increasingly operate under feedback, where deployed decisions alter future data distributions. Many such systems involve combinatorial subset selection, for which submodularity provides a tractable diminishing-returns structure and efficient approximation methods. However, decision-dependent distributions challenge the structural and algorithmic guarantees underlying classical stochastic submodular optimization. We study this phenomenon through performative submodular decision making, where the selected set both determines the utility and induces its evaluation distribution. We show that the induced performative objective may lose monotonicity and submodularity even when the realization-wise utility preserves both properties, and repeated best response retraining may decrease deployed performance or cycle. To recover tractable structure, we decouple the deployed set from the candidate set being optimized. For any fixed deployment, the resulting frozen objective remains monotone and submodular, providing the basis for approximate performative stability as a self-consistent solution concept. Moreover, under distribution-sensitivity conditions, approximate stability yields a global approximation guarantee for the original performative objective, up to an additive penalty controlled by distributional feedback. Together, these results motivate a finite-sample feedback-safe retraining method that, with high probability, guarantees improvement of the true performative objective along accepted deployments and provides a terminal quality bound upon rejection. Experiments on decision-dependent weighted coverage illustrate structural violations, retraining instability, and the reliability- conservativeness tradeoff of certification.