Control by Adding or Deleting Edges in Graph-Restricted Weighted Voting Games
Journal of Artificial Intelligence Research · 25.02.2025 · 82
DOI: 10.1613/jair.1.16940 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Artificial Intelligence Research, online erschienen am 25.02.2025. Verfasst von Joanna Kaczmarek und 2 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref).
Abstract (Originalsprache)
Graph-restricted weighted voting games generalize weighted voting games, a well-studied class of succinct simple games, by embedding them into a communication structure: a graph whose vertices are the players some of which are connected by edges. In such games, only sufficiently connected coalitions are taken into consideration for calculating the players' power indices. Focusing on the probabilistic Penrose-Banzhaf index (which Dubey and Shapley proposed in 1979 as an alternative to the normalized Penrose-Banzhaf index) and the Shapley-Shubik index, we study control of these games by an agent who can add edges to or delete edges from the given graph. We determine upper and lower bounds on how much such control actions can change a distinguished player's power and we study the computational complexity of the related problems.
Zitieren
APA
Kaczmarek, J., Rothe, J., & Talmon, N. (2025). Control by Adding or Deleting Edges in Graph-Restricted Weighted Voting Games. Journal of Artificial Intelligence Research, 82. https://doi.org/10.1613/jair.1.16940
Vancouver
Kaczmarek J, Rothe J, Talmon N. Control by Adding or Deleting Edges in Graph-Restricted Weighted Voting Games. Journal of Artificial Intelligence Research. 2025;82. doi:10.1613/jair.1.16940
BibTeX
@article{Kaczmarek2025,
author = {Kaczmarek, Joanna and Rothe, Jörg and Talmon, Nimrod},
title = {Control by Adding or Deleting Edges in Graph-Restricted Weighted Voting Games},
journal = {Journal of Artificial Intelligence Research},
year = {2025},
volume = {82},
doi = {10.1613/jair.1.16940}
}
EUVIMED