TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 26.10.2012

isti-logo

Page Content

to Navigation

A Multivariate Complexity Analysis of Lobbying in Multiple Referenda

Dipl.-Inf. Robert Bredereck (TU Berlin)

We extend work by Christian et al. [Review of Economic Design 2007] on lobbying in multiple referenda by first providing a more fine-grained analysis of the computational complexity of the NP-complete Lobbying problem. Herein, given a binary matrix, the columns represent issues to vote on and  the rows correspond to voters making a binary vote on each issue. An issue is approved if a majority of votes has a 1 in the corresponding column. The goal is to get all issues approved by modifying a minimum number of rows to all-1-rows. In our multivariate complexity analysis, we present a more holistic view on the nature of the computational complexity of Lobbying, providing both (parameterized) tractability and intractability results, depending on various problem parameterizations to be adopted. In this talk, I will present two new theoretical results (obtained since the publication of our work in AAAI-12) and discuss some preliminary experimental results. The first theoretical result is LogSNP-completeness of the Lobbying problem when every issue needs at most one additional 1 to be approved. The second result is polynomial-time solvability when the lobby is allowed to flip at most two 0s to 1 per vote. In elections, an alternative is said to be a Condorcet winner if it is preferred to any other alternative by a majority of voters. While this is a very attractive solution concept, many elections do not have a Condorcet winner. In this paper, we propose a set-valued relaxation of this concept, which we call a Condorcet winning set: such sets consist of alternatives that collectively dominate any other alternative. We also consider a more general version of this concept, where instead of domination by a majority of voters we require domination by a given fraction theta of voters; we refer to this concept as theta-winning set. We explore social choice-theoretic and algorithmic aspects of these solution concepts, both theoretically and empirically.

Date
Speaker
Location
Language
26.10.2012 14:15
Robert Bredereck
TEL 512
english/german

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe