Author name cluster

Lane Hemaspaandra

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.

6 papers

1 author row

AAAI Conference 2018 Conference Paper

Computational Social Choice and Computational Complexity: BFFs?

Lane Hemaspaandra

We discuss the connection between computational social choice (comsoc) and computational complexity. We stress the work so far on, and urge continued focus on, two lessrecognized aspects of this connection. Firstly, this is very much a two-way street: Everyone knows complexity classi- ﬁcation is used in comsoc, but we also highlight beneﬁts to complexity that have arisen from its use in comsoc. Secondly, more subtle, less-known complexity tools often can be very productively used in comsoc.

PDF Details

AAAI Conference 2017 Conference Paper

The Opacity of Backbones

Lane Hemaspaandra
David Narvez

A backbone of a boolean formula F is a collection S of its variables for which there is a unique partial assignment aS such that F[aS] is satisﬁable (Monasson et al. 1999; Willams, Gomes, and Selman 2003). This paper studies the nontransparency of backbones. We show that, under the widely believed assumption that integer factoring is hard, there exist sets of boolean formulas that have obvious, nontrivial backbones yet ﬁnding the values, aS, of those backbones is intractable. We also show that, under the same assumption, there exist sets of boolean formulas that obviously have large backbones yet producing such a backbone S is intractable. Further, we show that if integer factoring is not merely worst-case hard but is frequently hard, as is widely believed, then the frequency of hardness in our two results is not too much less than that frequency.

PDF Details

AAAI Conference 2014 Conference Paper

A Control Dichotomy for Pure Scoring Rules

Edith Hemaspaandra
Lane Hemaspaandra
Henning Schnoor

Scoring systems are an extremely important class of election systems. A length-m (so-called) scoring vector applies only to m-candidate elections. To handle general elections, one must use a family of vectors, one per length. The most elegant approach to making sure such families are “family-like” is the recently introduced notion of (polynomial-time uniform) pure scoring rules (Betzler and Dorn 2010), where each scoring vector is obtained from its precursor by adding one new coefficient. We obtain the first dichotomy theorem for pure scoring rules for a control problem. In particular, for constructive control by adding voters (CCAV), we show that CCAV is solvable in polynomial time for k-approval with k ≤ 3, k-veto with k ≤ 2, every pure scoring rule in which only the two top-rated candidates gain nonzero scores, and a particular rule that is a “hybrid” of 1-approval and 1-veto. For all other pure scoring rules, CCAV is NP-complete. We also investigate the descriptive richness of different models for defining pure scoring rules, proving how more rule-generation time gives more rules, proving that rationals give more rules than do the natural numbers, and proving that some restrictions previously thought to be “w. l. o. g. ” in fact do lose generality.

PDF Details

AAAI Conference 2010 Conference Paper

Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates

Felix Brandt
Markus Brill
Edith Hemaspaandra
Lane Hemaspaandra

For many election systems, bribery (and related) attacks have been shown NP-hard using constructions on combinatorially rich structures such as partitions and covers. It is important to learn how robust these hardness protection results are, in order to find whether they can be relied on in practice. This paper shows that for voters who follow the most central political-science model of electorates—single-peaked preferences—those protections vanish. By using singlepeaked preferences to simplify combinatorial covering challenges, we show that NP-hard bribery problems—including those for Kemeny and Llull elections—fall to polynomial time. By using single-peaked preferences to simplify combinatorial partition challenges, we show that NP-hard partitionof-voters problems fall to polynomial time. We furthermore show that for single-peaked electorates, the winner problems for Dodgson and Kemeny elections, though Θp 2-complete in the general case, fall to polynomial time. And we completely classify the complexity of weighted coalition manipulation for scoring protocols in single-peaked electorates.

PDF Details

TCS Journal 2009 Journal Article

The complexity of power-index comparison

Piotr Faliszewski
Lane Hemaspaandra

We study the complexity of the following problem: Given two weighted voting games G ′ and G ″ that each contain a player p, in which of these games is p ’s power index value higher? We study this problem with respect to both the Shapley–Shubik power index and the Banzhaf power index. Our main result is that for both of these power indices the problem is complete for probabilistic polynomial time (i. e. , is PP -complete). We apply our results to partially resolve some recently proposed problems regarding the complexity of weighted voting games. We also study the complexity of the raw Shapley–Shubik power index. Deng and Papadimitriou showed that the raw Shapley–Shubik power index is #P -metric-complete. We strengthen this by showing that the raw Shapley–Shubik power index is many–one complete for #P. And our strengthening cannot possibly be further improved to parsimonious completeness, since we observe that, in contrast with the raw Banzhaf power index, the raw Shapley–Shubik power index is not #P -parsimonious-complete.

Details DOI

AAAI Conference 2007 Conference Paper

Llull and Copeland Voting Broadly Resist Bribery and Control

Piotr Faliszewski
Lane Hemaspaandra

Control of elections refers to attempts by an agent to, via such actions as addition/deletion/partition of candidates or voters, ensure that a given candidate wins (Bartholdi, Tovey, & Trick 1992). An election system in which such an agent’s computational task is NP-hard is said to be resistant to the given type of control. Aside from election systems with an NP-hard winner problem, the only systems known to be resistant to all the standard control types are highly artiﬁcial election systems created by hybridization (Hemaspaandra, Hemaspaandra, & Rothe 2007b). In this paper, we prove that an election system developed by the 13th century mystic Ramon Llull and the well-studied Copeland election system are both resistant to all the standard types of (constructive) electoral control other than one variant of addition of candidates. This is the most comprehensive resistance to control yet achieved by any natural election system whose winner problem is in P. In addition, we show that Llull and Copeland voting are very broadly resistant to bribery attacks, and we integrate the potential irrationality of voter preferences into many of our results.

PDF Details