Transcript Approximability of Manipulating Elections

The Complexity of Elections:
A New Domain for Heuristic
Computation
Piotr Faliszewski
AGH University of Science and
Technology, Kraków, Poland
[email protected]
Why Are Elections Important?
– Politics
• Electing leaders
• Deciding policies, laws
•…
– Business settings
• Stock holders make decisions
in companies
• University Senates, hiring
decisions
• Competitions (e.g., racing,
Eurovision)
– Multiagent systems
• Meta-search engines
• Planning
•…
Elections aggregate
the opinions of the
voters
Computational issues
in elections
GibbardSatterthwaite
Theorem
Cheating in
elections
Winner determination
Running the
election
Possible
winner
Manipulation
Campaign
management
control
bribery
Complexity Barrier Approach
Model: Represent each cheating strategy as
a computational decision problem.
Complexity barrier approach: If
manipulating elections is hard, then we can
ignore the fact that it is in principle possible.
Complexity Barrier: Results
• Effects of complexity barrier research
– Dozens of computational problems identified
– Multiple standard election systems analyze
– Quite thorough understanding of worst case complexity
of elections
• Complications…
– We would like some of the problems to be efficiently
computable
• Determining winners
• Organizing a campaign
– Worst-case analysis seems problematic…
Room for heuristic computation!
Agenda
• Why study elections?
• Formal model
– What are elections?
– How to model votes?
– What voting rules to use?
• Case study: Plurality bribery
– Simplest case
– Deterministic solution
• Case study: Campaign management
– Campaign management as bribery
– Why is it good to study?
• What has been done? Where to take data from?
• Conclusions and comments
How to Study Elections?
• We need to answer several questions:
– What are elections?
A mathematical object, a pair E = (C,V).
C – set of candidates, V – set of voters
– How can we model voters’ preferences?
A single top guy? A ranking of candidates?
Numerical values, “utility” a voter derives
from having a particular candidate elected?
– What election rules are we interested in?
An election rule is a function that given an
election returns the set of winners.
Election Model: Example
• Election E = (C,V)
C={
,
,
,
,
}
V={
>
>
>
>
,
>
>
>
>
,
>
>
>
>
,
>
>
>
>
,
>
>
>
>
C – candidate set
V – voter set
• Who is the winner?
–
–
–
–
–
–
–
–
–
–
–
Plurality
Veto
Borda
k-approval
Approval
Copeland
Llull
Dodgson
Kemeny
Young
…
families of
scoring
protocols
}
Election Model: Example
• Election E = (C,V)
C – candidate set
V – voter set
• Who is the winner?
– Borda count
score(
) = 13
score(
) = 12
score(
)=9
score(
)=8
score(
)=8
C={
α=(4
V={
,
,
,
, 2
,
>
>
>
>
,
>
>
>
>
,
>
>
>
>
,
>
>
>
>
,
>
>
>
>
,
3
1
,
}
,
0 )
}
Election Model: Example
• Election E = (C,V)
C={
,
,
,
,
}
V={
>
>
>
>
,
>
>
>
>
,
>
>
>
>
,
>
>
>
>
,
>
>
>
>
C – candidate set
V – voter set
• Who is the winner?
– Copeland
}
Agenda
• Why study elections?
• Formal model
– What are elections?
– How to model votes?
– What voting rules to use?
• Case study: Plurality bribery
– Simplest case
– Deterministic solution
• Case study: Campaign management
– Campaign management as bribery
– Why is it good to study?
• Conclusions and comments
Computational issues
in elections
Cheating in
elections
Winner determination
Running the
election
Possible
winner
Manipulation
Campaign
management
control
bribery
Bribery
Notation: Ɛ – an election system
Name: Ɛ-bribery.
Given: An election E = (C,V), a
candidate p in C, and an
integer k.
Question: Can we make p a
winner via modifying
votes of at most k
voters?
Many flavors of the
bribery problem.
- Ɛ-bribery
- Ɛ-$bribery
- Ɛ-weighted-bribery
- Ɛ-weighted-$bribery
Bribery in Plurality
• Setting
– We are given:
• An election E = (C,V)
• A preferred candidate p
• A budget k
– Question:
• Can we make p a winner
by bribing voters of cost
at most k?
• Observation:
– It is sufficient to only look
at each voter’s most
preferred candidate
unpriced
unweighted
weighted
priced
Bribery in Plurality
• Example:
– What is the cheapest way
to make Alice a winner?
7
6
• Setting
– We are given:
• An election E = (C,V)
• A preferred candidate p
• A budget k
– Question:
• Can we make p a winner
by bribing voters of cost
at most k?
5
4
3
2
1
0
Mary
Bill
John
Alice
Bribery in Plurality
• Example:
– What is the cheapest way
to make Alice a winner?
7
6
• Setting
– We are given:
• An election E = (C,V)
• A preferred candidate p
• A budget k
– Question:
• Can we make p a winner
by bribing voters of cost
at most k?
5
4
3
2
1
0
Mary
Bill
John
Alice
Bribery in Plurality
• Example:
– What is the cheapest way
to make Alice a winner?
7
6
• Setting
– We are given:
• An election E = (C,V)
• A preferred candidate p
• A budget k
– Question:
• Can we make p a winner
by bribing voters of cost
at most k?
5
4
3
2
1
0
Mary
Bill
John
Alice
Bribery in Plurality
• Example:
– What is the cheapest way
to make Alice a winner?
7
6
• Setting
– We are given:
• An election E = (C,V)
• A preferred candidate p
• A budget k
– Question:
• Can we make p a winner
by bribing voters of cost
at most k?
5
4
3
2
1
0
Mary
Bill
John
Alice
Bribery in Plurality
• Setting
– We are given:
• An election E = (C,V)
• A preferred candidate p
• A budget k
– Question:
• Can we make p a winner
by bribing voters of cost
at most k?
unpriced
unweighted
weighted
priced
Computational Complexity
• NP
– Class of problems whose
solutions are of polynomial
size, and are verifiable in
polynomial time
• Some problems in NP
• Reduction between problems
– A, B – two problems
– A reduces to B if there is a
polynomial-time computable
function f such that
x in A  f(x) in B
– SAT – is a given Boolean
formula satisfiable?
– Given a sequence of
integers (s1, … , sn), is
there a subsequence that
sums up to a given value
K?
– Does a graph have a clique of
size n?
• NP-com: An NP problem is
NP-complete if all NP
problems reduce to it
f
A
B
f
plurality-weighted-$bribery  NP-com
Proof: Reduction from the subset-sum problem
Subset-Sum
Input: s1, s2, … , sn
1
5
6
10
plurality-weighted-$bribery
k = 17
=34
12
12
10
6
Question: Is there a subsequence
that sums up to exactly half.
5
1
plurality-weighted-$bribery  NP-com
Proof: Reduction from the subset-sum problem
Subset-Sum
Input: s1, s2, … , sn
1
5
6
10
plurality-weighted-$bribery
k = 17
=34
12
1
12
Question: Is there a subsequence
that sums up to exactly half.
5
6
10
Bribery in Plurality
• Setting
– We are given:
• An election E = (C,V)
• A preferred candidate p
• A budget k
– Question:
• Can we make p a winner
by bribing voters of cost
at most k?
unpriced
unweighted
weighted
priced
Weighted Bribery in Plurality
• plurality-weighted-bribery
– Now voters have weights
• What algorithms can we
use?
– Heuristics:
• Heaviest voter first
• Winner’s heaviest voter
first
12
10
8
6
4
2
0
Mary
Bill
John
Bribery in Plurality
• Setting
– We are given:
• An election E = (C,V)
• A preferred candidate p
• A budget k
– Question:
• Can we make p a winner
by bribing voters of cost
at most k?
unpriced
unweighted
weighted
priced
Agenda
• Why study elections?
• Formal model
– What are elections?
– How to model votes?
– What voting rules to use?
• Case study: Plurality bribery
– Simplest case
– Deterministic solution
• Case study: Campaign management
– Campaign management as bribery
– Why is it good to study?
• What has been done? Where to take data from?
• Conclusions and comments
Computational issues
in elections
Cheating in
elections
Winner determination
Running the
election
Possible
winner
Manipulation
Campaign
management
control
bribery
Bribery vs Campaign Management
• Bribery
• Campaign
management
– Invest money to
change votes
– Invest money to
change voters’ minds
– Some votes are
cheaper than others
– Some voters are
easier to convince
– Want to spend as
little as possible
– The campaign should
be as cheap as
possible
Bribery Models
• Standard bribery
– Payment ==> full control over a vote
• Nonuniform bribery
– Payment depends on the amount of change
Problem: How to represent the prices?
Swap Bribery
• Price function
>
π for each voter.
>
>
π( ,
)=5
Swap Bribery
• Price function
>
π for each voter.
>
>
π( , )π(= 2 ,
)=5
Swap Bribery
• Price function
>
π for each voter.
>
>
• Swap bribery problem
– Given: E = (C,V), price function for each voter
– Question: What is the cheapest sequence of swaps
that makes our guy a winner?
π( , ) = 2
Questions About Swap Bribery
• Price of reaching a given vote?
> > >
> > >
• Swap bribery and other voting problems?
Voting problem
<m
• Complexity of swap bribery?
Swap bribery
Relations Between Voting Problems
Results on Swap Bribery
• Swap Bribery is easy
for:
– Plurality
– Veto
• Swap bribery is NP-hard
for:
–
–
–
–
–
–
–
–
Borda
Copeland
Bucklin
Maximin
Ranked pairs
Plurality with runoff
STV
…
• Swap bribery can
model winner
problems:
– Kemeny
– Dodgson
Why Study Swap Bribery?
Swap bribery is
hard for almost all
voting systems
Swap bribery is a
generalization of
most important
problems
Agenda
• Why study elections?
• Formal model
– What are elections?
– How to model votes?
– What voting rules to use?
• Case study: Plurality bribery
– Simplest case
– Deterministic solution
• Case study: Campaign management
– Campaign management as bribery
– Why is it good to study?
• What has been done? Where to take data from?
• Conclusions and comments
Dealing with Complexity
• Approximation algorithms
– Some success for manipulation
– Limited types of swap bribery
• Parameterized complexity attacks
– Mostly smart brute-force algorithms
• Heuristic attacks
–
–
–
–
So far, only on manipulation instances
Limited type of algorithms (ad-hoc approaches)
Manipulation  solved (Toby Walsh)
others  untouched
Where to Take Data From?
Generate data
Impartial culture
(votes chosen
Independently at
random)
Real Elections
- difficult to obtain
- additional sampling
Polya-Eggenberger
Urn Model
An urn with all m!
votes. Pick a vote at
random, return it + a
additional copies of
the vote
And many others: E.g., uniform single-peaked votes…
Agenda
• Why study elections?
• Formal model
– What are elections?
– How to model votes?
– What voting rules to use?
• Case study: Plurality bribery
– Simplest case
– Deterministic solution
• Case study: Campaign management
– Campaign management as bribery
– Why is it good to study?
• Conclusions and comments
Conclusions and Comments
• Conclusions
– Elections are a rich source of computational issues
– Abundance of worst-case complexity results for many
settings
– Very few experimental results
– Very few heuristic solutions
– Swap bribery can be a natural problem to attack with
heuristic methods  most general problem studied.
Conclusions and Comments
• Where to get more information about the field?
– Book chapter:
A Richer Understanding of the Complexity of
Election Systems
(Faliszewski, Hemaspaandra, Hemaspaandra, Rothe)
– Upcoming AI Magazine paper:
AI’s War on Manipulation: Are We Winning?
(Faliszewski, Procaccia)
– Upcoming CACM paper:
Using Complexity to Protect Elections
(Faliszewski, Hemaspaandra, Hemaspaandra)
• Google search
– By problem: complexity + voting + {manipulation,
bribery, swap bribery, possible winner, control}
– By people: Conitzer, Procaccia, Walsh, Hemaspaandra,
Elkind, Slinko, Faliszewski
Conclusions and Comments
• Where is this kind of work published?
– Conferences
•
•
•
•
•
•
AAAI (AAAI Conference on Artificial Intelligence)
AAMAS (Autonomous Agents and Multiagent Systems)
EC (ACM Conference on Electronic Commerce)
WINE (Workshop on Internet and Network Economics)
SAGT (Symposium on Algorithmic Game Theory)
ADT (Algorithmic Decision Theory)
– Journals
•
•
•
•
•
Artificial Intelligence
Journal of AI Research
Social Choice and Welfare
Autonomous Agents and Multiagent Systems
Mathematical Social Sciences
Thank you!
I am sorry, but we have voted, and we are
all in favor.