Election control considers the problem of an adversary who attempts to tamper with a voting process, in order to either ensure that their favored candidate wins (constructive control) or another candidate loses (destructive control). As online social networks have become significant sources of information for potential voters, a new tool in an attacker’s arsenal is to effect control by harnessing social influence, for example, by spreading fake news and other forms of misinformation through online social media.
We consider the computational problem of election control via social influence, studying the conditions under which finding good adversarial strategies is computationally feasible. We consider two objectives for the adversary in both the constructive and destructive control settings: probability and margin of victory (POV and MOV, respectively). We present several strong negative results, showing, for example, that the problem of maximizing POV is inapproximable for any constant factor. On the other hand, we present approxima- tion algorithms which provide somewhat weaker approximation guarantees, such as bicriteria approximations for the POV objective and constant-factor approximations for MOV. Finally, we present mixed integer programming formulations for these problems. Ex- perimental results show that our approximation algorithms often find near-optimal control strategies, indicating that election control through social influence is a salient threat to election integrity.
more »
« less
Manipulating Elections by Selecting Issues
Constructive election control considers the problem of an adversary who seeks to sway the outcome of an electoral process in order to ensure that their favored candidate wins. We consider the computational problem of constructive election control via issue selection. In this problem, a party decides which political issues to focus on to ensure victory for the favored candidate. We also consider a variation in which the goal is to maximize the number of voters supporting the favored candidate. We present strong negative results, showing, for example, that the latter problem is inapproximable for any constant factor. On the positive side, we show that when issues are binary, the problem becomes tractable in several cases, and admits a 2-approximation in the two-candidate case. Finally, we develop integer programming and heuristic methods for these problems.
more »
« less
- NSF-PAR ID:
- 10130998
- Date Published:
- Journal Name:
- International Conference on Autonomous Agents and Multiagent Systems
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The culture within engineering colleges and departments has been historically quiet when considering social justice issues. Often the faculty in those departments are less concerned with social issues and are primarily focused on their disciplines and the concrete ways that they can make impacts academically and professionally in their respective arena’s. However, with the social climate of the United States shifting ever more towards a politically charged climate, and current events, particularly the protests against police brutality in recent years, faculty and students are constantly inundated with news of injustices happening in our society. The murder of George Floyd on May 25th 2020 sent shockwaves across the United States and the world. The video captured of his death shared across the globe brought everyone’s attention to the glaringly ugly problem of police brutality, paired with the COVID-19 pandemic, and US election year, the conditions were just right for a social activist movement to grow to a size that no one could ignore. Emmanuel Acho spoke out, motivated by injustices seen in the George Floyd murder, initially with podcasts and then by writing his book “Uncomfortable Converstations with a Black Man” [1]. In his book he touched on various social justice issues such as: racial terminology (i.e., Black or African American), implicit biases, white privilege, cultural appropriation, stereotypes (e.g., the “angry black man”), racial slurs (particularly the n-word), systemic racism, the myth of reverse racism, the criminal justice system, the struggles faced by black families, interracial families, allyship, and anti-racism. Students and faculty at Anonymous University felt compelled to set aside the time to meet and discuss this book in depth through the video conferencing client Zoom. In these meetings diverse facilitators were tasked with bringing the topics discussed by Acho in his book into conversation and pushing attendees of these meetings to consider those topics critically and personally. In an effort to avoid tasking attendees with reading homework to be able to participate in these discussions, the discussed chapter of the audiobook version of Acho’s book was played at the beginning of each meeting. Each audiobook chapter lasted between fifteen and twenty minutes, after which forty to forty-five minutes were left in the hour-long meetings to discuss the content of the chapter in question. Efforts by students and faculty were made to examine how some of the teachings of the book could be implemented into their lives and at Anonymous University. For broader topics, they would relate the content back to their personal lives (e.g., raising their children to be anti-racist and their experiences with racism in American and international cultures). Each meeting was recorded for posterity in the event that those conversations would be used in a paper such as this. Each meeting had at least one facilitator whose main role was to provide discussion prompts based on the chapter and ensure that the meeting environment was safe and inclusive. Naturally, some chapters address topics that are highly personal to some participants, so it was vital that all participants felt comfortable and supported to share their thoughts and experiences. The facilitator would intervene if the conversation veered in an aggressive direction. For example, if a participant starts an argument with another participant in a non-constructive manner, e.g., arguing over the definition of ethnicity, then the facilitator will interrupt, clear the air to bring the group back to a common ground, and then continue the discussion. Otherwise, participants were allowed to steer the direction of the conversation as new avenues of discussion popped up. These meetings were recorded with the goal of returning to these conversations and analyzing the conversations between attendees. Grounded theory will be used to first assess the most prominent themes of discussion between attendees for each meeting [2]. Attendees will be contacted to expressly ask their permission to have their words and thoughts used in this work, and upon agreement that data will begin to be processed. Select attendees will be asked to participate in focus group discussions, which will also be recorded via Zoom. These discussions will focus around the themes pulled from general discussion and will aim to dive deeper into the impact that this experience has had on them as either students or faculty members. A set of questions will be developed as prompts, but conversation is expected to evolve organically as these focus groups interact. These sessions will be scheduled for an hour, and a set of four focus groups with four participants are expected to participate for a total of sixteen total focus group participants. We hope to uncover how this experience changed the lives of the participants and present a model of how conversations such as this can promote diversity, equity, inclusion, and access activities amongst faculty and students outside of formal programs and strategic plans that are implemented at university, college, or departmental levels.more » « less
-
Integrity of elections is vital to democratic systems, but it is frequently threatened by malicious actors. The study of algorithmic complexity of the problem of manipulating election outcomes by changing its structural features is known as election control. One means of election control that has been proposed is to select a subset of issues that determine voter preferences over candidates. We study a variation of this model in which voters have judgments about relative importance of issues, and a malicious actor can manipulate these judgments. We show that computing effective manipulations in this model is NP-hard even with two candidates or binary issues. However, we demonstrate that the problem is tractable with a constant number of voters or issues. Additionally, while it remains intractable when voters can vote stochastically, we exhibit an important special case in which stochastic voting enables tractable manipulation.more » « less
-
Integrity of elections is vital to democratic systems, but it is frequently threatened by malicious actors.The study of algorithmic complexity of the problem of manipulating election outcomes by changing its structural features is known as election control Rothe [2016].One means of election control that has been proposed, pertinent to the spatial voting model, is to select a subset of issues that determine voter preferences over candidates.We study a variation of this model in which voters have judgments about relative importance of issues, and a malicious actor can manipulate these judgments.We show that computing effective manipulations in this model is NP-hard even with two candidates or binary issues.However, we demonstrate that the problem becomes tractable with a constant number of voters or issues.Additionally, while it remains intractable when voters can vote stochastically, we exhibit an important special case in which stochastic voting behavior enables tractable manipulation.more » « less
-
Following the seminal work of Bartholdi et al. [2], there has been a slew of research on the complexity of constructive and destructive control for specific election systems (a.k.a. voting rules), which was driven by the field’s desire to find a natural election system that is “resistant” to as many control attacks (types) as possible. While this race was happening, many proofs were devised for a variety of election systems, and yet unbeknownst to many, several control attacks were in fact exactly the same (when viewed as decision problems, which is the common framework). Hemaspaandra et al. [14] were the first to make this observation, demonstrating that there was a general lack of understanding of the standard control attacks. My work continues this line of research in three ways: (1) determining the relationships of electoral control types both in the “general” setting and in concrete settings, (2) finding axiomatic- sufficient conditions to determine if a particular equality between control types (a.k.a. collapse) occurs, and (3) linking results in the more abstract decision model to the more explicit search model.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
