TY - GEN

T1 - Algorithms for gerrymandering over graphs

AU - Ito, Takehiro

AU - Kamiyama, Naoyuki

AU - Kobayashi, Yusuke

AU - Okamot, Yoshio

N1 - Funding Information:
We thank M. TAKAHASHI, S. SETSU, and K. SATO for technical assistance, K. YAMAMOTO, T. HONDA, and H. MORI for providing E. coli strains and their genomic DNAs, Y. TERAWAKI for encouragement, and M. OHARA and Y. HAYASHI for language assistance. This work was performed as a part of the genome sequencing project of the EHEC 0157:H7 Sakai strain which was supported by The Japan Society for the Promotion of Science, "Research for the Future" Program, 97LOOI0l and JSPS-RFTF 00L01411.
Publisher Copyright:
© 2019 International Foundation for Autonomous Agents and Multiagent Systems. All rights reserved.

PY - 2019

Y1 - 2019

N2 - We initiate the systematic algorithmic study for gerrymandering over graphs that was recently introduced by Cohen-Zemach, Lewen-berg 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.

AB - We initiate the systematic algorithmic study for gerrymandering over graphs that was recently introduced by Cohen-Zemach, Lewen-berg 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.

UR - http://www.scopus.com/inward/record.url?scp=85076885438&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85076885438&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85076885438

T3 - Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS

SP - 1413

EP - 1421

BT - 18th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2019

PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)

T2 - 18th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2019

Y2 - 13 May 2019 through 17 May 2019

ER -