<p>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.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

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

  • Duc Nghia Vu,
  • Janos Demetrovics,
  • Duc Thi Vu,
  • Quang Minh Le,
  • Hoang Son Nguyen,
  • Le Nam Vo

摘要

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.