Core Criticality in Structured Voting Games with Extremal Bounds for the Strategic Criticality Index
AI · 03.11.2026 · 7 (11) · 457
DOI: 10.3390/ai7110457 ↗Kurz gefasst
Fachartikel in der Zeitschrift AI, online erschienen am 03.11.2026. Verfasst von Duc Nghia Vu und 1 weiteren Autor:innen. Die Arbeit nennt 20 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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.
Zitieren
APA
Vu, D. N., & Vu, D. T. (2026). Core Criticality in Structured Voting Games with Extremal Bounds for the Strategic Criticality Index. AI, 7(11), 457. https://doi.org/10.3390/ai7110457
Vancouver
Vu DN, Vu DT. Core Criticality in Structured Voting Games with Extremal Bounds for the Strategic Criticality Index. AI. 2026;7(11):457. doi:10.3390/ai7110457
BibTeX
@article{Vu2026,
author = {Vu, Duc Nghia and Vu, Duc Thi},
title = {Core Criticality in Structured Voting Games with Extremal Bounds for the Strategic Criticality Index},
journal = {AI},
year = {2026},
volume = {7},
number = {11},
pages = {457},
doi = {10.3390/ai7110457}
}
EUVIMED