{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,19]],"date-time":"2025-08-19T09:57:44Z","timestamp":1755597464385,"version":"3.40.5"},"reference-count":0,"publisher":"IOS Press","isbn-type":[{"type":"electronic","value":"9781643685489"}],"license":[{"start":{"date-parts":[[2024,10,16]],"date-time":"2024-10-16T00:00:00Z","timestamp":1729036800000},"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":[[2024,10,16]]},"abstract":"<jats:p>Weighted voting games are a well-known and useful class of succinctly representable simple games that have many real-world applications, e.g., to model collective decision-making in legislative bodies or shareholder voting. Among the structural control types being analyzing, one is control by adding players to weighted voting games, so as to either change or to maintain a player\u2019s power in the sense of the (probabilistic) Penrose\u2013Banzhaf power index or the Shapley\u2013Shubik power index. For the problems related to this control, the best known lower bound is PP-hardness, where PP is \u201cprobabilistic polynomial time,\u201d and the best known upper bound is the class NP, i.e., the class NP with a PP oracle. We optimally raise this lower bound by showing NPPP-hardness of all these problems for the Penrose\u2013Banzhaf and the Shapley\u2013Shubik indices, thus establishing completeness for them in that class. Our proof technique may turn out to be useful for solving other open problems related to weighted voting games with such a complexity gap as well.<\/jats:p>","DOI":"10.3233\/faia240906","type":"book-chapter","created":{"date-parts":[[2024,10,17]],"date-time":"2024-10-17T13:40:20Z","timestamp":1729172420000},"source":"Crossref","is-referenced-by-count":1,"title":["Control by Adding Players to Change or Maintain the Shapley\u2013Shubik or the Penrose\u2013Banzhaf Power Index in Weighted Voting Games Is Complete for NPPP"],"prefix":"10.3233","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6652-6433","authenticated-orcid":false,"given":"Joanna","family":"Kaczmarek","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik, MNF, 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":"Institut f\u00fcr Informatik, MNF, Heinrich-Heine-Universit\u00e4t D\u00fcsseldorf, D\u00fcsseldorf, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"7437","container-title":["Frontiers in Artificial Intelligence and Applications","ECAI 2024"],"original-title":[],"link":[{"URL":"https:\/\/ebooks.iospress.nl\/pdf\/doi\/10.3233\/FAIA240906","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,17]],"date-time":"2024-10-17T13:40:20Z","timestamp":1729172420000},"score":1,"resource":{"primary":{"URL":"https:\/\/ebooks.iospress.nl\/doi\/10.3233\/FAIA240906"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,16]]},"ISBN":["9781643685489"],"references-count":0,"URL":"https:\/\/doi.org\/10.3233\/faia240906","relation":{},"ISSN":["0922-6389","1879-8314"],"issn-type":[{"type":"print","value":"0922-6389"},{"type":"electronic","value":"1879-8314"}],"subject":[],"published":{"date-parts":[[2024,10,16]]}}}