The complexity of probabilistic lobbying

Daniel Binkele-Raible; Gábor Erdélyi; Henning Fernau; Judy Goldsmith; Nicholas Mattei; Jörg Rothe

doi:10.1016/j.disopt.2013.10.003

The complexity of probabilistic lobbying

Daniel Binkele-Raible
, Gábor Erdélyi
, Henning Fernau
, Judy Goldsmith
, Nicholas Mattei
, Jörg Rothe

Producción científica: Article › revisión exhaustiva

29 Citas (Scopus)

Resumen

We propose models for lobbying in a probabilistic environment, in which an actor (called "The Lobby") seeks to influence voters' preferences of voting for or against multiple issues when the voters' preferences are represented in terms of probabilities. In particular, we provide two evaluation criteria and two bribery methods to formally describe these models, and we consider the resulting forms of lobbying with and without issue weighting. We provide a formal analysis for these problems of lobbying, and determine their classical and parameterized complexity depending on the given bribery/evaluation criteria and on various natural parameterizations. Specifically, we show that some of these problems can be solved in polynomial time, some are NP-complete but fixed-parameter tractable, and some are W[2]-complete. Finally, we provide approximability and inapproximability results for these problems and several variants.

Idioma original	English
Páginas (desde-hasta)	1-21
Número de páginas	21
Publicación	Discrete Optimization
Volumen	11
N.º	1
DOI	https://doi.org/10.1016/j.disopt.2013.10.003
Estado	Published - feb 2014

Nota bibliográfica

Funding Information:
The second and sixth authors were supported in part by DFG grants RO 1202/11-1 , RO 1202/12-1 (within the European Science Foundation’s EUROCORES program LogICCC), and RO 1202/15-1 , and the Alexander von Humboldt Foundation’s TransCoop program. The fourth and fifth authors were supported in part by NSF grants CCF-1049360 and ITR-0325063 . The second author was supported in part by National Research Foundation (Singapore) under grant NRF-RF 2009-08 and DFG grant ER 738/1-1 .

Financiación

The second and sixth authors were supported in part by DFG grants RO 1202/11-1 , RO 1202/12-1 (within the European Science Foundation\u2019s EUROCORES program LogICCC), and RO 1202/15-1 , and the Alexander von Humboldt Foundation\u2019s TransCoop program. The fourth and fifth authors were supported in part by NSF grants CCF-1049360 and ITR-0325063 . The second author was supported in part by National Research Foundation (Singapore) under grant NRF-RF 2009-08 and DFG grant ER 738/1-1 .

Financiadores	Número del financiador
Alexander von Humboldt-Stiftung
Deutsche Forschungsgemeinschaft	RO 1202/12-1, RO 1202/11-1
EUROPEAN SCIENCE FOUNDATION	RO 1202/15-1
U.S. Department of Energy Chinese Academy of Sciences Guangzhou Municipal Science and Technology Project Oak Ridge National Laboratory Extreme Science and Engineering Discovery Environment National Science Foundation National Energy Research Scientific Computing Center National Natural Science Foundation of China	CCF-1049360, 0325063, ITR-0325063
National Research Foundation Singapore	ER 738/1-1, NRF-RF 2009-08

ASJC Scopus subject areas

Theoretical Computer Science
Computational Theory and Mathematics
Applied Mathematics

Acceder al documento

10.1016/j.disopt.2013.10.003

Otros archivos y enlaces

Citar esto

@article{510abd3dc341489b92585c834e3183be,

title = "The complexity of probabilistic lobbying",

abstract = "We propose models for lobbying in a probabilistic environment, in which an actor (called {"}The Lobby{"}) seeks to influence voters' preferences of voting for or against multiple issues when the voters' preferences are represented in terms of probabilities. In particular, we provide two evaluation criteria and two bribery methods to formally describe these models, and we consider the resulting forms of lobbying with and without issue weighting. We provide a formal analysis for these problems of lobbying, and determine their classical and parameterized complexity depending on the given bribery/evaluation criteria and on various natural parameterizations. Specifically, we show that some of these problems can be solved in polynomial time, some are NP-complete but fixed-parameter tractable, and some are W[2]-complete. Finally, we provide approximability and inapproximability results for these problems and several variants.",

keywords = "Approximability, Computational complexity, Computational social choice, Parameterized complexity",

author = "Daniel Binkele-Raible and G{\'a}bor Erd{\'e}lyi and Henning Fernau and Judy Goldsmith and Nicholas Mattei and J{\"o}rg Rothe",

note = "Funding Information: The second and sixth authors were supported in part by DFG grants RO 1202/11-1 , RO 1202/12-1 (within the European Science Foundation{\textquoteright}s EUROCORES program LogICCC), and RO 1202/15-1 , and the Alexander von Humboldt Foundation{\textquoteright}s TransCoop program. The fourth and fifth authors were supported in part by NSF grants CCF-1049360 and ITR-0325063 . The second author was supported in part by National Research Foundation (Singapore) under grant NRF-RF 2009-08 and DFG grant ER 738/1-1 . ",

year = "2014",

month = feb,

doi = "10.1016/j.disopt.2013.10.003",

language = "English",

volume = "11",

pages = "1--21",

number = "1",

}

TY - JOUR

T1 - The complexity of probabilistic lobbying

AU - Binkele-Raible, Daniel

AU - Erdélyi, Gábor

AU - Fernau, Henning

AU - Goldsmith, Judy

AU - Mattei, Nicholas

AU - Rothe, Jörg

N1 - Funding Information: The second and sixth authors were supported in part by DFG grants RO 1202/11-1 , RO 1202/12-1 (within the European Science Foundation’s EUROCORES program LogICCC), and RO 1202/15-1 , and the Alexander von Humboldt Foundation’s TransCoop program. The fourth and fifth authors were supported in part by NSF grants CCF-1049360 and ITR-0325063 . The second author was supported in part by National Research Foundation (Singapore) under grant NRF-RF 2009-08 and DFG grant ER 738/1-1 .

PY - 2014/2

Y1 - 2014/2

N2 - We propose models for lobbying in a probabilistic environment, in which an actor (called "The Lobby") seeks to influence voters' preferences of voting for or against multiple issues when the voters' preferences are represented in terms of probabilities. In particular, we provide two evaluation criteria and two bribery methods to formally describe these models, and we consider the resulting forms of lobbying with and without issue weighting. We provide a formal analysis for these problems of lobbying, and determine their classical and parameterized complexity depending on the given bribery/evaluation criteria and on various natural parameterizations. Specifically, we show that some of these problems can be solved in polynomial time, some are NP-complete but fixed-parameter tractable, and some are W[2]-complete. Finally, we provide approximability and inapproximability results for these problems and several variants.

AB - We propose models for lobbying in a probabilistic environment, in which an actor (called "The Lobby") seeks to influence voters' preferences of voting for or against multiple issues when the voters' preferences are represented in terms of probabilities. In particular, we provide two evaluation criteria and two bribery methods to formally describe these models, and we consider the resulting forms of lobbying with and without issue weighting. We provide a formal analysis for these problems of lobbying, and determine their classical and parameterized complexity depending on the given bribery/evaluation criteria and on various natural parameterizations. Specifically, we show that some of these problems can be solved in polynomial time, some are NP-complete but fixed-parameter tractable, and some are W[2]-complete. Finally, we provide approximability and inapproximability results for these problems and several variants.

KW - Approximability

KW - Computational complexity

KW - Computational social choice

KW - Parameterized complexity

UR - https://www.scopus.com/pages/publications/84890786344

UR - https://www.scopus.com/pages/publications/84890786344#tab=citedBy

U2 - 10.1016/j.disopt.2013.10.003

DO - 10.1016/j.disopt.2013.10.003

M3 - Article

AN - SCOPUS:84890786344

SN - 1572-5286

VL - 11

SP - 1

EP - 21

JO - Discrete Optimization

JF - Discrete Optimization

IS - 1

ER -

The complexity of probabilistic lobbying

Resumen

Nota bibliográfica

Financiación

ASJC Scopus subject areas

Acceder al documento

Otros archivos y enlaces

Huella

Citar esto