Author name cluster

David E. Narváez

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

2 author rows

EUMAS Conference 2024 Conference Paper

Search Versus Search for Collapsing Electoral Control Types

Benjamin Carleton
Michael C. Chavrimootoo
Lane A. Hemachandra
David E. Narváez
Conor Taliancich
Henry B. Welles

Abstract A 2024 paper of Carleton et al. [ 11 ] building on Hemaspaandra et al. [ 25 ] surprisingly shows, for 36 pairs of cases involving plurality, veto, and approval voting, that seemingly different, long-studied partition-based control attack types “collapse”: they are the same set (and so have the same decision complexity). The rather novel open question the 2024 paper concludes with is whether, for the 36 collapsing decision-problem pairs, their search -complexities are linked. In this paper, we completely resolve that question. We build a framework for linking the search complexities and solutions of members of collapsing pairs, and we both link and pinpoint the search complexities of all 36 collapsing cases (in part via linking the search complexities within the 7 “universal” collapsing pairs). This is important because for election problems the search versions are by far the more important versions: they tell one how to perform the desired attack.

Details

JAIR Journal 2024 Journal Article

Separating and Collapsing Electoral Control Types

Benjamin Carleton
Michael C. Chavrimootoo
Lane A. Hemaspaandra
David E. Narváez
Conor Taliancich
Henry B. Welles

Electoral control refers to attacking elections by adding, deleting, or partitioning voters or candidates. Hemaspaandra, Hemaspaandra, and Menton recently discovered, for seven pairs ( T, T ′) of seemingly distinct standard electoral control types, that T and T ′ are in practice identical: For each input I and each election system E, I is a “yes” instance of both T and T ′ under E, or of neither. Surprisingly, this had previously gone undetected even as the field was score-carding how many standard control types various 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 perhaps other pairs of control types are identical, and so work still is being needlessly duplicated. We completely determine, for all standard control types, which pairs are, for elections whose votes are linear orderings of the candidates, always identical. In particular, we prove that no identical control pairs exist beyond the known seven. We also for three central election systems completely determine which control pairs are identical (“collapse”) with respect to those particular election systems, and we also explore containment and incomparability relationships between control pairs. For approval voting, which has a different “type” for its votes, Hemaspaandra, Hemaspaandra, and Menton’s seven collapses still hold (since we observe that their argument applies to all election systems). However, we find 14 additional collapses that hold for approval voting but do not hold for some election systems whose votes are linear orderings of the candidates. We find one new collapse for veto elections and none for plurality. We prove that each of the three election systems mentioned have no collapses other than those inherited from Hemaspaandra, Hemaspaandra, and Menton or added in the present paper. We establish many new containment relationships between separating control pairs, and for each separating pair of standard control types classify its separation in terms of either 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.

PDF Details DOI

AAMAS Conference 2023 Conference Paper

Search versus Search for Collapsing Electoral Control Types

Benjamin Carleton
Michael C. Chavrimootoo
Lane A. Hemaspaandra
David E. Narváez
Conor Taliancich
Henry B. Welles

Hemaspaandra et al. [6] and Carleton et al. [3, 4] found that many pairs of electoral (decision) problems about the same election system coincide as sets (i. e. , they are collapsing pairs), which had previously 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 reductions 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.

PDF

AAMAS Conference 2023 Conference Paper

Separating and Collapsing Electoral Control Types

Benjamin Carleton
Michael C. Chavrimootoo
Lane A. Hemaspaandra
David E. Narváez
Conor Taliancich
Henry B. Welles

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 systems 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 control 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.

PDF

AAAI Conference 2021 Short Paper

Toward Determining NFA Equivalence via QBFs (Student Abstract)

Hannah Miller
David E. Narváez

Equivalence of deterministic finite automata (DFAs) has been researched for several decades, but equivalence of nondeterministic finite automata (NFAs) is not as studied. Equivalence of two NFAs is a PSPACE-complete problem. NFA equivalence is a challenging theoretical problem with practical applications such as lexical analysis. Quantified boolean formulas (QBFs) naturally encode PSPACE-complete problems, and we share our preliminary work towards determining NFA equivalence via QBFs.

PDF Details

AAAI Conference 2020 Short Paper

A QSAT Benchmark Based on Vertex-Folkman Problems (Student Abstract)

David E. Narváez

The purpose of this paper is to draw attention to a particular family of quantiﬁed Boolean formulas (QBFs) stemming from encodings of some vertex Folkman problems in extremal graph theory. We argue that this family of formulas is interesting for QSAT research because it is both conceptually simple and parametrized in a way that allows for a ﬁnegrained diversity in the level of difﬁculty of its instances. Additionally, when coupled with symmetry breaking, the formulas in this family exhibit backbones (unique satisfying assignments) at the top-level existential variables. This benchmark is thus suitable for addressing questions regarding the connection between the existence of backbones and the hardness of QBFs.

PDF Details

AAAI Conference 2019 Conference Paper

Very Hard Electoral Control Problems

Zack Fitzsimmons
Edith Hemaspaandra
Alexander Hoover
David E. Narváez

It is important to understand how the outcome of an election can be modified by an agent with control over the structure of the election. Electoral control has been studied for many election systems, but for all these systems the winner problem is in P, and so control is in NP. There are election systems, such as Kemeny, that have many desirable properties, but whose winner problems are not in NP. Thus for such systems control is not in NP, and in fact we show that it is typically complete for Σp 2 (i. e. , NPNP, the second level of the polynomial hierarchy). This is a very high level of complexity. Approaches that perform quite well for solving NP problems do not necessarily work for Σp 2-complete problems. However, answer set programming is suited to express problems in Σp 2, and we present an encoding for Kemeny control.

PDF Details