Approximation algorithms for campaign management

Edith Elkind; Piotr Faliszewski

doi:10.1007/978-3-642-17572-5_40

Approximation algorithms for campaign management

Edith Elkind^*, Piotr Faliszewski

^*Corresponding author for this work

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

62 Scopus citations

Abstract

We study electoral campaign management scenarios in which an external party can buy votes, i.e., pay the voters to promote its preferred candidate in their preference rankings. The external party's goal is to make its preferred candidate a winner while paying as little as possible. We describe a 2-approximation algorithm for this problem for a large class of electoral systems known as scoring rules. Our result holds even for weighted voters, and has applications for campaign management in commercial settings. We also give approximation algorithms for our problem for two Condorcet-consistent rules, namely, the Copeland rule and maximin.

Original language	English (US)
Title of host publication	Internet and Network Economics - 6th International Workshop, WINE 2010, Proceedings
Pages	473-482
Number of pages	10
DOIs	https://doi.org/10.1007/978-3-642-17572-5_40
State	Published - 2010
Externally published	Yes
Event	6th International Workshop on Internet and Network Economics, WINE 2010 - Stanford, CA, United States Duration: Dec 13 2010 → Dec 17 2010

Publication series

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

Conference

Conference	6th International Workshop on Internet and Network Economics, WINE 2010
Country/Territory	United States
City	Stanford, CA
Period	12/13/10 → 12/17/10

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-17572-5_40

Cite this

Elkind, E., & Faliszewski, P. (2010). Approximation algorithms for campaign management. In Internet and Network Economics - 6th International Workshop, WINE 2010, Proceedings (pp. 473-482). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6484 LNCS). https://doi.org/10.1007/978-3-642-17572-5_40

@inproceedings{ba832c4d1b624af8a6e03390c746a726,

title = "Approximation algorithms for campaign management",

abstract = "We study electoral campaign management scenarios in which an external party can buy votes, i.e., pay the voters to promote its preferred candidate in their preference rankings. The external party's goal is to make its preferred candidate a winner while paying as little as possible. We describe a 2-approximation algorithm for this problem for a large class of electoral systems known as scoring rules. Our result holds even for weighted voters, and has applications for campaign management in commercial settings. We also give approximation algorithms for our problem for two Condorcet-consistent rules, namely, the Copeland rule and maximin.",

author = "Edith Elkind and Piotr Faliszewski",

year = "2010",

doi = "10.1007/978-3-642-17572-5_40",

language = "English (US)",

isbn = "3642175716",

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

pages = "473--482",

booktitle = "Internet and Network Economics - 6th International Workshop, WINE 2010, Proceedings",

note = "6th International Workshop on Internet and Network Economics, WINE 2010 ; Conference date: 13-12-2010 Through 17-12-2010",

}

Elkind, E & Faliszewski, P 2010, Approximation algorithms for campaign management. in Internet and Network Economics - 6th International Workshop, WINE 2010, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6484 LNCS, pp. 473-482, 6th International Workshop on Internet and Network Economics, WINE 2010, Stanford, CA, United States, 12/13/10. https://doi.org/10.1007/978-3-642-17572-5_40

Approximation algorithms for campaign management. / Elkind, Edith; Faliszewski, Piotr.
Internet and Network Economics - 6th International Workshop, WINE 2010, Proceedings. 2010. p. 473-482 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6484 LNCS).

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

TY - GEN

T1 - Approximation algorithms for campaign management

AU - Elkind, Edith

AU - Faliszewski, Piotr

PY - 2010

Y1 - 2010

N2 - We study electoral campaign management scenarios in which an external party can buy votes, i.e., pay the voters to promote its preferred candidate in their preference rankings. The external party's goal is to make its preferred candidate a winner while paying as little as possible. We describe a 2-approximation algorithm for this problem for a large class of electoral systems known as scoring rules. Our result holds even for weighted voters, and has applications for campaign management in commercial settings. We also give approximation algorithms for our problem for two Condorcet-consistent rules, namely, the Copeland rule and maximin.

AB - We study electoral campaign management scenarios in which an external party can buy votes, i.e., pay the voters to promote its preferred candidate in their preference rankings. The external party's goal is to make its preferred candidate a winner while paying as little as possible. We describe a 2-approximation algorithm for this problem for a large class of electoral systems known as scoring rules. Our result holds even for weighted voters, and has applications for campaign management in commercial settings. We also give approximation algorithms for our problem for two Condorcet-consistent rules, namely, the Copeland rule and maximin.

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

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

U2 - 10.1007/978-3-642-17572-5_40

DO - 10.1007/978-3-642-17572-5_40

M3 - Conference contribution

AN - SCOPUS:78650855129

SN - 3642175716

SN - 9783642175718

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

SP - 473

EP - 482

BT - Internet and Network Economics - 6th International Workshop, WINE 2010, Proceedings

T2 - 6th International Workshop on Internet and Network Economics, WINE 2010

Y2 - 13 December 2010 through 17 December 2010

ER -

Approximation algorithms for campaign management

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this