Core Criticality in Structured Voting Games with Extremal Bounds for the Strategic Criticality Index

The Strategic Criticality Index (SCI) is a boundary-sensitive measure of agent importance in monotone simple games that weights maximal losing coalitions by their deficiency. Exact SCI computation is #P-hard in general, and the existing FPRAS requires a non-degeneracy condition. This paper studies the SCI under two structural constraints common in safety-critical cooperative AI: strong cores and t-intersecting winning families. We prove that the SCI of veto players is exact, extend this to a strong-core decomposition into a residual weighted-voting game, and give a high-intersection bound on complement sizes. We introduce witness-based mass certificates and polynomial-time certificates for t-intersection. Algorithmically, we provide a bounded-weight dynamic-programming algorithm for exact SCI computation and a core-aware Monte Carlo approximation algorithm with explicit sample complexity. Conditioning on the residual game is shown to strictly reduce sampling variance for non-core agents. These results connect extremal set theory, fault-tolerant design, and boundary-sensitive cooperative game theory.