{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T15:45:54Z","timestamp":1750347954737,"version":"3.40.5"},"reference-count":0,"publisher":"IOS Press","isbn-type":[{"type":"print","value":"9781643684369"},{"type":"electronic","value":"9781643684376"}],"license":[{"start":{"date-parts":[[2023,9,28]],"date-time":"2023-09-28T00:00:00Z","timestamp":1695859200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,9,28]]},"abstract":"<jats:p>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 connected coalitions are taken into consideration for calculating the players\u2019 power indices. We focus on the probabilistic Penrose\u2013Banzhaf index\u00a0[5] and the Shapley\u2013Shubik index\u00a0[18] and study the computational complexity of manipulating these games by an external agent who can add edges to or delete edges from the graph. For the problems modeling such scenarios, we raise some of the lower bounds obtained by Kaczmarek and Rothe\u00a0[9] from NP- or DP-hardness to PP-hardness, where PP is probabilistic polynomial time. We also solve one of their open problems by showing that it is a coNP-hard problem to maintain the Shapley\u2013Shubik index of a given player in a graph-restricted weighted voting game when edges are deleted.<\/jats:p>","DOI":"10.3233\/faia230395","type":"book-chapter","created":{"date-parts":[[2023,9,29]],"date-time":"2023-09-29T09:11:25Z","timestamp":1695978685000},"source":"Crossref","is-referenced-by-count":1,"title":["Complexity of Control by Adding or Deleting Edges in Graph-Restricted Weighted Voting Games"],"prefix":"10.3233","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6652-6433","authenticated-orcid":false,"given":"Joanna","family":"Kaczmarek","sequence":"first","affiliation":[{"name":"Heinrich-Heine-Universit\u00e4t D\u00fcsseldorf, D\u00fcsseldorf, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0589-3616","authenticated-orcid":false,"given":"J\u00f6rg","family":"Rothe","sequence":"additional","affiliation":[{"name":"Heinrich-Heine-Universit\u00e4t D\u00fcsseldorf, D\u00fcsseldorf, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7916-0979","authenticated-orcid":false,"given":"Nimrod","family":"Talmon","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Beer-Sheva, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"7437","container-title":["Frontiers in Artificial Intelligence and Applications","ECAI 2023"],"original-title":[],"link":[{"URL":"https:\/\/ebooks.iospress.nl\/pdf\/doi\/10.3233\/FAIA230395","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,29]],"date-time":"2023-09-29T09:11:36Z","timestamp":1695978696000},"score":1,"resource":{"primary":{"URL":"https:\/\/ebooks.iospress.nl\/doi\/10.3233\/FAIA230395"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,28]]},"ISBN":["9781643684369","9781643684376"],"references-count":0,"URL":"https:\/\/doi.org\/10.3233\/faia230395","relation":{},"ISSN":["0922-6389","1879-8314"],"issn-type":[{"type":"print","value":"0922-6389"},{"type":"electronic","value":"1879-8314"}],"subject":[],"published":{"date-parts":[[2023,9,28]]}}}