The Complexity of Campaigning

Cory Siler; Luke Harold Miles; Judy Goldsmith

doi:10.1007/978-3-319-67504-6_11

The Complexity of Campaigning

Cory Siler, Luke Harold Miles, Judy Goldsmith

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

Abstract

In “The Logic of Campaigning”, Dean and Parikh consider a candidate making campaign statements to appeal to the voters. They model these statements as Boolean formulas over variables that represent stances on the issues, and study optimal candidate strategies under three proposed models of voter preferences based on the assignments that satisfy these formulas. We prove that voter utility evaluation is computationally hard under these preference models (in one case, P -hard), along with certain problems related to candidate strategic reasoning. Our results raise questions about the desirable characteristics of a voter preference model and to what extent a polynomial-time-evaluable function can capture them.

Original language	English
Title of host publication	Algorithmic Decision Theory - 5th International Conference, ADT 2017, Proceedings
Editors	Jorg Rothe
Pages	153-165
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-319-67504-6_11
State	Published - 2017
Event	5th International Conference on Algorithmic Decision Theory, ADT 2017 - Luxembourg, Luxembourg Duration: Oct 25 2017 → Oct 27 2017

Publication series

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

Conference

Conference	5th International Conference on Algorithmic Decision Theory, ADT 2017
Country/Territory	Luxembourg
City	Luxembourg
Period	10/25/17 → 10/27/17

Bibliographical note

Publisher Copyright:
© 2017, Springer International Publishing AG.

Funding

Acknowledgments. The authors thank three anonymous reviewers for their helpful feedback and thank Alec Gilbert for catching errors in a late draft. All remaining errors are the responsibility of the authors. This material is based upon work partially supported by the National Science Foundation under Grants No. IIS-1646887 and No. IIS-1649152. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.

Funders	Funder number
National Science Foundation (NSF)	IIS-1646887

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-67504-6_11

Cite this

Siler, C., Miles, L. H., & Goldsmith, J. (2017). The Complexity of Campaigning. In J. Rothe (Ed.), Algorithmic Decision Theory - 5th International Conference, ADT 2017, Proceedings (pp. 153-165). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10576 LNAI). https://doi.org/10.1007/978-3-319-67504-6_11

@inproceedings{244e5165f4514c2ab6e58e2d8f65acff,

title = "The Complexity of Campaigning",

abstract = "In “The Logic of Campaigning”, Dean and Parikh consider a candidate making campaign statements to appeal to the voters. They model these statements as Boolean formulas over variables that represent stances on the issues, and study optimal candidate strategies under three proposed models of voter preferences based on the assignments that satisfy these formulas. We prove that voter utility evaluation is computationally hard under these preference models (in one case, P -hard), along with certain problems related to candidate strategic reasoning. Our results raise questions about the desirable characteristics of a voter preference model and to what extent a polynomial-time-evaluable function can capture them.",

author = "Cory Siler and Miles, {Luke Harold} and Judy Goldsmith",

note = "Publisher Copyright: {\textcopyright} 2017, Springer International Publishing AG.; 5th International Conference on Algorithmic Decision Theory, ADT 2017 ; Conference date: 25-10-2017 Through 27-10-2017",

year = "2017",

doi = "10.1007/978-3-319-67504-6_11",

language = "English",

isbn = "9783319675039",

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

pages = "153--165",

editor = "Jorg Rothe",

booktitle = "Algorithmic Decision Theory - 5th International Conference, ADT 2017, Proceedings",

}

Siler, C, Miles, LH & Goldsmith, J 2017, The Complexity of Campaigning. in J Rothe (ed.), Algorithmic Decision Theory - 5th International Conference, ADT 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10576 LNAI, pp. 153-165, 5th International Conference on Algorithmic Decision Theory, ADT 2017, Luxembourg, Luxembourg, 10/25/17. https://doi.org/10.1007/978-3-319-67504-6_11

The Complexity of Campaigning. / Siler, Cory; Miles, Luke Harold; Goldsmith, Judy.
Algorithmic Decision Theory - 5th International Conference, ADT 2017, Proceedings. ed. / Jorg Rothe. 2017. p. 153-165 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10576 LNAI).

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

TY - GEN

T1 - The Complexity of Campaigning

AU - Siler, Cory

AU - Miles, Luke Harold

AU - Goldsmith, Judy

PY - 2017

Y1 - 2017

N2 - In “The Logic of Campaigning”, Dean and Parikh consider a candidate making campaign statements to appeal to the voters. They model these statements as Boolean formulas over variables that represent stances on the issues, and study optimal candidate strategies under three proposed models of voter preferences based on the assignments that satisfy these formulas. We prove that voter utility evaluation is computationally hard under these preference models (in one case, P -hard), along with certain problems related to candidate strategic reasoning. Our results raise questions about the desirable characteristics of a voter preference model and to what extent a polynomial-time-evaluable function can capture them.

AB - In “The Logic of Campaigning”, Dean and Parikh consider a candidate making campaign statements to appeal to the voters. They model these statements as Boolean formulas over variables that represent stances on the issues, and study optimal candidate strategies under three proposed models of voter preferences based on the assignments that satisfy these formulas. We prove that voter utility evaluation is computationally hard under these preference models (in one case, P -hard), along with certain problems related to candidate strategic reasoning. Our results raise questions about the desirable characteristics of a voter preference model and to what extent a polynomial-time-evaluable function can capture them.

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

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

U2 - 10.1007/978-3-319-67504-6_11

DO - 10.1007/978-3-319-67504-6_11

M3 - Conference contribution

AN - SCOPUS:85032477627

SN - 9783319675039

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

SP - 153

EP - 165

BT - Algorithmic Decision Theory - 5th International Conference, ADT 2017, Proceedings

A2 - Rothe, Jorg

T2 - 5th International Conference on Algorithmic Decision Theory, ADT 2017

Y2 - 25 October 2017 through 27 October 2017

ER -

The Complexity of Campaigning

Abstract

Publication series

Conference

Bibliographical note

Funding

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this