ダウンロード数: 35
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
j.tcs.2021.03.037.pdf | 752.62 kB | Adobe PDF | 見る/開く |
タイトル: | Algorithms for gerrymandering over graphs |
著者: | Ito, Takehiro Kamiyama, Naoyuki Kobayashi, Yusuke https://orcid.org/0000-0001-9478-7307 (unconfirmed) Okamoto, Yoshio |
著者名の別形: | 小林, 佑輔 |
キーワード: | Gerrymandering Computational social choice Graph algorithms |
発行日: | May-2021 |
出版者: | Elsevier BV |
誌名: | Theoretical Computer Science |
巻: | 868 |
開始ページ: | 30 |
終了ページ: | 45 |
抄録: | We initiate the systematic algorithmic study for gerrymandering over graphs that was recently introduced by Cohen-Zemach, Lewenberg and Rosenschein. Namely, we study a strategic procedure for a political districting designer to draw electoral district boundaries so that a particular target candidate can win in an election. We focus on the existence of such a strategy under the plurality voting rule, and give interesting contrasts which classify easy and hard instances with respect to polynomial-time solvability. For example, we prove that the problem for trees is strongly NP-complete (thus unlikely to have a pseudo-polynomial-time algorithm), but has a pseudo-polynomial-time algorithm when the number of candidates is constant. Another example is to prove that the problem for complete graphs is NP-complete when the number of electoral districts is two, while is solvable in polynomial time when it is more than two. |
著作権等: | © 2021. This manuscript version is made available under the Creative Commons Attribution-NonCommercial-NoDerivs 4.0 license. The full-text file will be made open to the public on 08 May 2023 in accordance with publisher's 'Terms and Conditions for Self-Archiving'. This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 |
URI: | http://hdl.handle.net/2433/268289 |
DOI(出版社版): | 10.1016/j.tcs.2021.03.037 |
出現コレクション: | 学術雑誌掲載論文等 |
このアイテムは次のライセンスが設定されています: クリエイティブ・コモンズ・ライセンス