The complexity of probabilistic lobbying

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

doi:10.1007/978-3-642-04428-1_8

The complexity of probabilistic lobbying

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

19 Scopus citations

Abstract

We propose various models for lobbying in a probabilistic environment, in which an actor (called "The Lobby") seeks to influence the 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 three 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 in a stochastic environment, and determine their classical and parameterized complexity depending on the given bribery/evaluation criteria. 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 (in)approximability results.

Original language	English
Title of host publication	Algorithmic Decision Theory - First International Conference, ADT 2009, Proceedings
Pages	86-97
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-04428-1_8
State	Published - 2009
Event	1st International Conference on Algorithmic Decision Theory, ADT 2009 - Venice, Italy Duration: Oct 20 2009 → Oct 23 2009

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5783 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	1st International Conference on Algorithmic Decision Theory, ADT 2009
Country/Territory	Italy
City	Venice
Period	10/20/09 → 10/23/09

Bibliographical 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’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 .

Funding

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 .

Funders	Funder number
National Science Foundation (NSF)	CCF-1049360, ITR-0325063
Directorate for Computer and Information Science and Engineering	0325063
Alexander von Humboldt-Stiftung
EUROPEAN SCIENCE FOUNDATION	RO 1202/15-1
National Research Foundation Singapore	ER 738/1-1, NRF-RF 2009-08
Deutsche Forschungsgemeinschaft	RO 1202/12-1, RO 1202/11-1

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-04428-1_8

Cite this

Erdélyi, G., Fernau, H., Goldsmith, J., Mattei, N., Raible, D., & Rothe, J. (2009). The complexity of probabilistic lobbying. In Algorithmic Decision Theory - First International Conference, ADT 2009, Proceedings (pp. 86-97). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5783 LNAI). https://doi.org/10.1007/978-3-642-04428-1_8

@inproceedings{a3ec77f8066e4ccd862d22c6ebae6d57,

title = "The complexity of probabilistic lobbying",

abstract = "We propose various models for lobbying in a probabilistic environment, in which an actor (called {"}The Lobby{"}) seeks to influence the 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 three 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 in a stochastic environment, and determine their classical and parameterized complexity depending on the given bribery/evaluation criteria. 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 (in)approximability results.",

author = "G{\'a}bor Erd{\'e}lyi and Henning Fernau and Judy Goldsmith and Nicholas Mattei and Daniel Raible 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 . ; 1st International Conference on Algorithmic Decision Theory, ADT 2009 ; Conference date: 20-10-2009 Through 23-10-2009",

year = "2009",

doi = "10.1007/978-3-642-04428-1_8",

language = "English",

isbn = "3642044271",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "86--97",

booktitle = "Algorithmic Decision Theory - First International Conference, ADT 2009, Proceedings",

}

Erdélyi, G, Fernau, H, Goldsmith, J, Mattei, N, Raible, D & Rothe, J 2009, The complexity of probabilistic lobbying. in Algorithmic Decision Theory - First International Conference, ADT 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5783 LNAI, pp. 86-97, 1st International Conference on Algorithmic Decision Theory, ADT 2009, Venice, Italy, 10/20/09. https://doi.org/10.1007/978-3-642-04428-1_8

The complexity of probabilistic lobbying. / Erdélyi, Gábor; Fernau, Henning; Goldsmith, Judy et al.
Algorithmic Decision Theory - First International Conference, ADT 2009, Proceedings. 2009. p. 86-97 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5783 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - The complexity of probabilistic lobbying

AU - Erdélyi, Gábor

AU - Fernau, Henning

AU - Goldsmith, Judy

AU - Mattei, Nicholas

AU - Raible, Daniel

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 - 2009

Y1 - 2009

N2 - We propose various models for lobbying in a probabilistic environment, in which an actor (called "The Lobby") seeks to influence the 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 three 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 in a stochastic environment, and determine their classical and parameterized complexity depending on the given bribery/evaluation criteria. 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 (in)approximability results.

AB - We propose various models for lobbying in a probabilistic environment, in which an actor (called "The Lobby") seeks to influence the 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 three 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 in a stochastic environment, and determine their classical and parameterized complexity depending on the given bribery/evaluation criteria. 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 (in)approximability results.

UR - http://www.scopus.com/inward/record.url?scp=71549147221&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=71549147221&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-04428-1_8

DO - 10.1007/978-3-642-04428-1_8

M3 - Conference contribution

AN - SCOPUS:71549147221

SN - 3642044271

SN - 9783642044274

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 86

EP - 97

BT - Algorithmic Decision Theory - First International Conference, ADT 2009, Proceedings

T2 - 1st International Conference on Algorithmic Decision Theory, ADT 2009

Y2 - 20 October 2009 through 23 October 2009

ER -

Erdélyi G, Fernau H, Goldsmith J, Mattei N, Raible D, Rothe J. The complexity of probabilistic lobbying. In Algorithmic Decision Theory - First International Conference, ADT 2009, Proceedings. 2009. p. 86-97. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-04428-1_8

The complexity of probabilistic lobbying

Abstract

Publication series

Conference

Bibliographical note

Funding

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this