Approximation Theory for Decomposition Integrals via Set and Collection Reduction

Decomposition integrals on finite spaces have a natural linear programming representation, but their evaluation may require exponentially many variables indexed by subsets of the underlying space. Restricting the admissible sets or collections produces computationally smaller lower approximations and raises the problem of quantifying the resulting loss. We develop an approximation theory for this reduction. For a retained collection and a removed set, the central quantity is the retained collection integral evaluated at the indicator of the removed set; its positive shortfall from the monotone measure value defines the reconstruction defect. We aggregate these local defects through a residual packing problem and obtain simultaneous deletion bounds. For a single removed set, the estimate is sharp and equals the worst-case error on the unit cube. We also determine the smallest uniform multiplicative approximation factor, derive a posteriori certificates from dual reduced profits, and characterize pointwise exactness. The results extend to comparisons of arbitrary collections and to decomposition systems, including deletion of whole member collections. For cardinality-based monotone measures, reconstruction values and approximation factors admit closed forms. These results provide rigorous certificates for sparse evaluation while preserving the underlying non-additive structure.