The strategic criticality index provides a boundary sensitive measure of agent importance with axiomatic uniqueness and a fully polynomial randomized approximation scheme for weighted voting games
摘要
The Strategic Criticality Index (SCI) was recently proposed as a heuristic that quantifies an agent’s importance in converting maximal losing coalitions into winning ones. In this work, we transform the SCI into a fully developed analytical concept. We first give a universal definition that applies to all monotone simple games, using a natural measure of coalition deficiency. We then provide an axiomatic characterization that uniquely determines the SCI within the class of boundary-linear indices satisfying dummy, symmetry, and total balance properties. On the computational side, we prove that computing the exact SCI is #P-hard for simple games accessed via an oracle. For the practically important class of weighted voting games with polynomially bounded weights, we design a conditional fully polynomial randomized approximation scheme (FPRAS) for the promised subclass of weighted voting games with polynomially bounded weights that satisfy a non-degeneracy condition on the boundary structure. Finally, we contrast the SCI with the Banzhaf and Shapley indices, demonstrating through theoretical comparisons and small-scale examples that the SCI captures strategic boundary proximity that classic power indices miss. The result is a well-founded and, for a broad class of games, efficiently computable metric for boundary-aware decision making in multi-agent AI systems.