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
This content will become publicly available on May 1, 2024
Separating and Collapsing Electoral Control Types
Electoral control refers to attacking elections by adding, deleting,
or partitioning voters or candidates [3]. Hemaspaandra et al. [16]
discovered, for seven pairs (T , T ′ ) of seemingly distinct standard
electoral control types, that T and T ′ are identical: For each input
𝐼 and each election system E, 𝐼 is a “yes” instance of both T and T ′
under E, or of neither. Surprisingly, this had gone undetected even
as the field was score-carding how many standard control types
election systems were resistant to; various “different” cells on such
score cards were, unknowingly, duplicate effort on the same issue.
This naturally raises the worry that other pairs of control types are
also identical, and so work still is being needlessly duplicated.
We determine, for all standard control types, which pairs are, for
elections whose votes are linear orderings of the candidates, always
identical. We show that no identical control pairs exist beyond the
known seven. For three central election systems, we determine
which control pairs are identical (“collapse”) with respect to those
particular systems, and we explore containment/incomparability
relationships between control pairs. For approval voting, which has
a different “type” for its votes, Hemaspaandra et al.’s [16] seven
collapses still hold. But we find 14 additional collapses that hold
for approval voting but not for some election systems whose votes
are linear orderings. We find one additional collapse for veto and
none for plurality. We prove that each of the three election sys-
tems mentioned have no collapses other than those inherited from
Hemaspaandra et al. [16] or added here. But we show many new
containment relationships that hold between some separating con-
trol pairs, and for each separating pair of standard control types
classify its separation in terms of containment (always, and strict
on some inputs) or incomparability.
Our work, for the general case and these three important election
systems, clarifies the landscape of the 44 standard control types,
for each pair collapsing or separating them, and also providing
finer-grained information on the separations.
more »
« less
- Award ID(s):
- 2006496
- NSF-PAR ID:
- 10422854
- Date Published:
- Journal Name:
- Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems
- Volume:
- 22
- ISSN:
- 2523-5699
- Page Range / eLocation ID:
- 1743 - 1751
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Hemaspaandra et al. [6] and Carleton et al. [3, 4] found that many pairs of electoral (decision) problems about the same election sys- tem coincide as sets (i.e., they are collapsing pairs), which had pre- viously gone undetected in the literature. While both members of a collapsing pair certainly have the same decision complexity, there is no guarantee that the associated search problems also have the same complexity. For practical purposes, search problems are more relevant than decision problems. Our work focuses on exploring the relationships between the search versions of collapsing pairs. We do so by giving a framework that relates the complexity of search problems via efficient reduc- tions that transform a solution from one problem to a solution of the other problem on the same input. We not only establish that the known decision collapses carry over to the search model, but also refine our results by determining for the concrete systems plurality, veto, and approval whether collapsing search-problem pairs are polynomial-time computable or NP-hard.more » « less
-
This dataset incorporates Mexico City related essential data files associated with Beth Tellman's dissertation: Mapping and Modeling Illicit and Clandestine Drivers of Land Use Change: Urban Expansion in Mexico City and Deforestation in Central America. It contains spatio-temporal datasets covering three domains; i) urban expansion from 1992-2015, ii) district and section electoral records for 6 elections from 2000-2015, iii) land titling (regularization) data for informal settlements from 1997-2012 on private and ejido land. The urban expansion data includes 30m resolution urban land cover for 1992 and 2013 (methods published in Goldblatt et al 2018), and a shapefile of digitized urban informal expansion in conservation land from 2000-2015 using the Worldview-2 satellite. The electoral records include shapefiles with the geospatial boundaries of electoral districts and sections for each election, and .csv files of the number of votes per party for mayoral, delegate, and legislature candidates. The private land titling data includes the approximate (in coordinates) location and date of titles given by the city government (DGRT) extracted from public records (Diario Oficial) from 1997-2012. The titling data on ejido land includes a shapefile of georeferenced polygons taken from photos in the CORETT office or ejido land that has been expropriated by the government, and including an accompany .csv from the National Agrarian Registry detailing the date and reason for expropriation from 1987-2007. Further details are provided in the dissertation and subsequent article publication (Tellman et al 2021). The Mexico City portion of these data were generated via a National Science Foundation sponsored project (No. 1657773, DDRI: Mapping and Modeling Clandestine Drivers of Urban Expansion in Mexico City). The project P.I. is Beth Tellman with collaborators at ASU (B.L Turner II and Hallie Eakin). Other collaborators include the National Autonomous University of Mexico (UNAM), at the Institute of Geography via Dr. Armando Peralta Higuera, who provided support for two students, Juan Alberto Guerra Moreno and Kimberly Mendez Gomez for validating the Landsat urbanization algorithm. Fidel Serrano-Candela, at the UNAM Laboratory of the National Laboratory for Sustainability Sciences (LANCIS) also provided support for urbanization algorithm development and validation, and Rodrigo Garcia Herrera, who provided support for hosting data at LANCIS (at: http://patung.lancis.ecologia.unam.mx/tellman/). Additional collaborators include Enrique Castelán, who provided support for the informal urbanization data from SEDEMA (Ministry of the Environmental for Mexico City). Electoral, land titling, and land zoning data were digitized with support from Juana Martinez, Natalia Hernandez, Alexia Macario Sanchez, Enrique Ruiz Durazo, in collaboration with Felipe de Alba, at CESOP (Center of Social Studies and Public Opinion, at the Mexican Legislative Assembly). The data include geospatial time series data regarding changes in urban land cover, digitized electoral results, land titling, land zoning, and public housing. Additional funding for this work was provided by NSF under Grant No. 1414052, CNH: The Dynamics of Multiscalar Adaptation in Megacities (PI H. Eakin), and the NSF-CONACYT GROW fellowship NSF No. 026257-001 and CONACYT number 291303 (PI Bojórquez). References: Tellman, B., Eakin, H., Janssen, M.A., Alba, F. De, Ii, B.L.T., 2021. The Role of Institutional Entrepreneurs and Informal Land Transactions in Mexico City’s Urban Expansion. World Dev. 140, 1–44. https://doi.org/10.1016/j.worlddev.2020.105374 Goldblatt, R., Stuhlmacher, M.F., Tellman, B., Clinton, N., Hanson, G., Georgescu, M., Wang, C., Serrano-Candela, F., Khandelwal, A.K., Cheng, W.-H., Balling, R.C., 2018. Using Landsat and nighttime lights for supervised pixel-based image classification of urban land cover. Remote Sens. Environ. 205, 253–275. https://doi.org/10.1016/j.rse.2017.11.026more » « less
-
We solve a long-standing challenge to the integrity of votes cast without the supervision of a voting booth: ``{\it improper influence},'' which typically refers to any combination of vote buying and voter coercion. Our approach allows each voter, or their trusted agents (which we call ``{\it hedgehogs}''), to {\it ``nullify''} (effectively cancel) their vote in a way that is unstoppable, irrevocable, and forever unattributable to the voter. In particular, our approach enhances security of online, remote, public-sector elections, for which there is a growing need and the threat of improper influence is most acute. We introduce the new approach, give detailed cryptographic protocols, show how it can be applied to several voting settings, and describe our implementation. The protocols compose a full voting system, which we call {\it {\votexx}}, including registration, voting, nullification, and tallying---using an anonymous communication system for registration, vote casting, and other communication in the system. We demonstrate how the technique can be applied to known systems, including where ballots can be mailed to voters and voters use codes on the ballot to cast their votes online. In comparison with previous proposals, our system makes fewer assumptions and protects against a strong adversary who learns all of the voter's keys. In {\votexx}, each voter has two public-private key pairs. Without revealing their private keys, each voter registers their public keys with the election authority. Each voter may share their keys with one or more hedgehogs. During nullification, the voter, or one or more of their hedgehogs, can interact through the anonymous communication system to nullify a vote by proving knowledge of one of the voter's private keys via a zero-knowledge proof without revealing the private key. We describe a fully decentralizable implementation of {\votexx}, including its public bulletin board, which could be implemented on a blockchain.more » « less
-
more » « less
We propose a modified spatial‐voting rule to explain why congressional candidates adopt more extreme ideological positions than their constituents' preferences. Our model accepts the standard spatial‐voting model with one critical exception: voters in the same party as a candidate tolerate extremism without imposing an electoral penalty. This, in turn, creates “leeway” for candidates to adopt extreme positions as they increasingly depend on voters from their own party. Electoral simulations demonstrate that a key election‐level implication of this model is that it explains candidate polarization without relying on institutional factors like primary elections. Finally, we show that asymmetry in perceptual bias is one possible mechanism and that real‐world patterns of ideological representation are consistent with our simulation results.
