{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T07:42:15Z","timestamp":1723016535057},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,7]]},"abstract":"<jats:p>The Chamberlin-Courant and Monroe rules are fundamental and well-studied rules in the literature of multi-winner elections. The problem of determining if there exists a committee of size k that has a Chamberlin-Courant (respectively, Monroe) dissatisfaction score of at most r is known to be NP-complete. We consider the following natural problems in this setting: a) given a committee S of size k as input, is it an optimal k-sized committee?, and b) given a candidate c and a committee size k, does there exist an optimal k-sized committee that contains c? In this work, we resolve the complexity of both problems for the Chamberlin-Courant and Monroe voting rules in the settings of rankings as well as approval ballots. We show that verifying if a given committee is optimal is coNP-complete whilst the latter problem is complete for Theta_2^P. Our contribution fills an essential gap in the literature for these important multi-winner rules.<\/jats:p>","DOI":"10.24963\/ijcai.2020\/13","type":"proceedings-article","created":{"date-parts":[[2020,7,8]],"date-time":"2020-07-08T12:12:10Z","timestamp":1594210330000},"page":"89-95","source":"Crossref","is-referenced-by-count":2,"title":["On the Complexity of Winner Verification and Candidate Winner for Multiwinner Voting Rules"],"prefix":"10.24963","author":[{"given":"Chinmay","family":"Sonar","sequence":"first","affiliation":[{"name":"University of California, Santa Barbara"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Palash","family":"Dey","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Kharagpur"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neeldhara","family":"Misra","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Gandhinagar"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"10584","event":{"number":"28","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"acronym":"IJCAI-PRICAI-2020","name":"Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}","start":{"date-parts":[[2020,7,11]]},"theme":"Artificial Intelligence","location":"Yokohama, Japan","end":{"date-parts":[[2020,7,17]]}},"container-title":["Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2020,7,9]],"date-time":"2020-07-09T02:12:53Z","timestamp":1594260773000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2020\/13"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2020,7]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2020\/13","relation":{},"subject":[],"published":{"date-parts":[[2020,7]]}}}