3. Using computational hardness to prevent manipulation and other undesirable behavior in elections

4. Selected topics (time permitting)

Introduction to voting theory

Voting over alternatives

>

>

>

>

voting rule (mechanism) determines winner based on votes

Can vote over other things too

Where to go for dinner tonight, other joint plans, …

Voting (rank aggregation)

Set of m candidates (aka. alternatives, outcomes)

n voters; each voter ranks all the candidates

E.g., for set of candidates {a, b, c, d}, one possible vote is b > a > d > c

Submitted ranking is called a vote

A voting rule takes as input a vector of votes (submitted by the voters), and as output produces either:

the winning candidate, or

an aggregate ranking of all candidates

Can vote over just about anything

political representatives, award nominees, where to go for dinner tonight, joint plans, allocations of tasks/resources, …

Also can consider other applications: e.g., aggregating search engines’ rankings into a single ranking

Example voting rules

Scoring rules are defined by a vector (a1, a2, …, am); being ranked ith in a vote gives the candidate ai points

Plurality is defined by (1, 0, 0, …, 0) (winner is candidate that is ranked first most often)

Veto (or anti-plurality) is defined by (1, 1, …, 1, 0) (winner is candidate that is ranked last the least often)

Borda is defined by (m-1, m-2, …, 0)

Plurality with (2-candidate) runoff: top two candidates in terms of plurality score proceed to runoff; whichever is ranked higher than the other by more voters, wins

Single Transferable Vote (STV, aka. Instant Runoff): candidate with lowest plurality score drops out; if you voted for that candidate, your vote transfers to the next (live) candidate on your list; repeat until one candidate remains

Similar runoffs can be defined for rules other than plurality

Pairwise elections

>

>

>

>

>

>

>

two votes prefer Obama to McCain

>

two votes prefer Obama to Nader

>

two votes prefer Nader to McCain

>

>

Condorcet cycles

>

>

>

>

>

>

>

two votes prefer McCain to Obama

>

two votes prefer Obama to Nader

>

two votes prefer Nader to McCain

?

“weird” preferences

Voting rules based on pairwise elections

Copeland: candidate gets two points for each pairwise election it wins, one point for each pairwise election it ties

Maximin (aka. Simpson): candidate whose worst pairwise result is the best wins

Cup/pairwise elimination: pair candidates, losers of pairwise elections drop out, repeat

Ranked pairs (Tideman): look for largest pairwise defeat, lock in that pairwise comparison, then the next-largest one, etc., unless it creates a cycle

Even more voting rules…

Kemeny: create an overall ranking of the candidates that has as few disagreements as possible (where a disagreement is with a vote on a pair of candidates)

NP-hard!

Bucklin: start with k=1 and increase k gradually until some candidate is among the top k candidates in more than half the votes; that candidate wins

Approval (not a ranking-based rule): every voter labels each candidate as approved or disapproved, candidate with the most approvals wins

Condorcet criterion

A candidate is the Condorcet winner if it wins all of its pairwise elections

Does not always exist…

… but the Condorcet criterion says that if it does exist, it should win

Many rules do not satisfy this

E.g. for plurality:

b > a > c > d

c > a > b > d

d > a > b > c

a is the Condorcet winner, but it does not win under plurality

One more voting rule…

Dodgson: candidate wins that can be made Condorcet winner with fewest swaps of adjacent alternatives in votes

NP-hard!

Choosing a rule…

How do we choose a rule from all of these rules?

How do we know that there does not exist another, “perfect” rule?

Axiomatic approach

E.g., Kemeny is the unique rule satisfying Condorcet and consistency properties [Young & Levenglick 1978]

Maximum likelihood approach

View votes as perturbations of “correct” ranking, try to estimate correct ranking

Kemeny is the MLE under one natural model [Young 1995], but other noise models lead to other rules [Drissi & Truchon 2002, Conitzer & Sandholm 2005, Truchon 2008, Conitzer et al. 2009, Xia et al. 2010]

Distance rationalizability

Look for a closeby consensus profile (e.g., Condorcet consistent) and choose its winner

See Elkind, Faliszewski, Slinko COMSOC 2010 talk

Also Baigent 1987, Meskanen and Nurmi 2008, …

Th. 11:35 Social Choice

Majority criterion

If a candidate is ranked first by a majority (> ½) of the votes, that candidate should win

Relationship to Condorcet criterion?

Some rules do not even satisfy this

E.g. Borda:

a > b > c > d > e

a > b > c > d > e

c > b > d > e > a

a is the majority winner, but it does not win under Borda

Monotonicity criteria

Informally, monotonicity means that “ranking a candidate higher should help that candidate,” but there are multiple nonequivalent definitions

A weak monotonicity requirement: if

candidate w wins for the current votes,

we then improve the position of w in some of the votes and leave everything else the same,

then w should still win.

E.g., STV does not satisfy this:

7 votes b > c > a

7 votes a > b > c

6 votes c > a > b

c drops out first, its votes transfer to a, a wins

But if 2 votes b > c > a change to a > b > c, b drops out first, its 5 votes transfer to c, and c wins

Monotonicity criteria…

A strong monotonicity requirement: if

candidate w wins for the current votes,

we then change the votes in such a way that for each vote, if a candidate c was ranked below w originally, c is still ranked below w in the new vote

then w should still win.

Note the other candidates can jump around in the vote, as long as they don’t jump ahead of w

None of our rules satisfy this

Independence of irrelevant alternatives

Independence of irrelevant alternatives criterion: if

the rule ranks a above b for the current votes,

we then change the votes but do not change which is ahead between a and b in each vote

then a should still be ranked ahead of b.

None of our rules satisfy this

Arrow’s impossibility theorem [1951]

Suppose there are at least 3 candidates

Then there exists no rule that is simultaneously:

Pareto efficient (if all votes rank a above b, then the rule ranks a above b),

nondictatorial (there does not exist a voter such that the rule simply always copies that voter’s ranking), and

independent of irrelevant alternatives

Muller-Satterthwaite impossibility theorem [1977]

Suppose there are at least 3 candidates

Then there exists no rule that simultaneously:

satisfies unanimity (if all votes rank a first, then a should win),

is nondictatorial (there does not exist a voter such that the rule simply always selects that voter’s first candidate as the winner), and

is monotone (in the strong sense).

Gibbard-Satterthwaite impossibility theorem

Suppose there are at least 3 candidates

There exists no rule that is simultaneously:

onto (for every candidate, there are some votes that would make that candidate win),

nondictatorial (there does not exist a voter such that the rule simply always selects that voter’s first candidate as the winner), and

nonmanipulable

Hard-to-compute rules

Tu. 10:10 Winner Determination in Voting and Tournament Solutions

Kemeny & Slater

Closely related

Kemeny:

NP-hard [Bartholdi, Tovey, Trick 1989]

Even with only 4 voters [Dwork et al. 2001]

Exact complexity of Kemeny winner determination: complete for Θ_2^p [Hemaspaandra, Spakowski, Vogel 2005]

Slater:

NP-hard, even if there are no pairwise ties [Ailon et al. 2005, Alon 2006, Conitzer 2006, Charbit et al. 2007]

Pairwise election graphs

Pairwise election between a and b: compare how often a is ranked above b vs. how often b is ranked above a

Graph representation: edge from winner to loser (no edge if tie), weight = margin of victory

E.g., for votes a > b > c > d, c > a > d > b this gives

a

b

d

c

2

2

2

Kemeny on pairwise election graphs

Final ranking = acyclic tournament graph

Edge (a, b) means a ranked above b

Acyclic = no cycles, tournament = edge between every pair

Kemeny ranking seeks to minimize the total weight of the inverted edges

a

b

d

c

2

2

10

4

4

2

pairwise election graph

Kemeny ranking

a

b

d

c

2

2

(b > d > c > a)

Slater on pairwise election graphs

Final ranking = acyclic tournament graph

Slater ranking seeks to minimize the number of inverted edges

a

b

d

c

a

b

d

c

pairwise election graph

Slater ranking

(a > b > d > c)

An integer program for computing Kemeny/Slater rankings

y(a, b) is 1 if a is ranked below b, 0 otherwise

w(a, b) is the weight on edge (a, b) (if it exists)

in the case of Slater, weights are always 1

minimize: ΣeE we ye

subject to:

for all a, b V, y(a, b) + y(b, a) = 1

for all a, b, c V, y(a, b) + y(b, c) + y(c, a) ≥ 1

Let T(m) be the maximum number of recursive calls to the algorithm (nodes in the tree) for m alternatives

Let T’(m) be the maximum number of recursive calls to the algorithm (nodes in the tree) for m alternatives given that the manipulator’s vote is currently committed

T(m) ≤ 1 + T(m-1) + T’(m-1)

T’(m) ≤ 1 + T(m-1)

Combining the two: T(m) ≤ 2 + T(m-1) + T(m-2)

The solution is O(((1+√5)/2)m)

Note this is only worst-case; in practice manipulator probably won’t make a difference in most rounds

Walsh [ECAI 2010] shows an optimized version of this algorithm is highly effective in experiments (simulation)

Manipulation complexity with few alternatives

Ideally, would like hardness results for constant number of alternatives

But then manipulator can simply evaluate each possible vote

assuming the others’ votes are known & executing rule is in P

Even for coalitions of manipulators, there are only polynomially many effectively different vote profiles (if rule is anonymous)

However, if we place weights on votes, complexity may return…

Unweighted

voters

Weighted

voters

Individual

manipulation

Coalitional

manipulation

Can be

hard

easy

easy

easy

Constant #alternatives

Unbounded #alternatives

Can be

hard

Can be

hard

Can be

hard

Potentially

hard

Unweighted

voters

Weighted

voters

Constructive manipulation now becomes:

We are given the weighted votes of the others (with the weights)

And we are given the weights of members of our coalition

Algorithms that only have a small “window of error” of instances on which they fail [Zuckerman et al. AIJ-09, Xia et al. EC-10]

Results showing that whether the manipulators can make a difference depends primarily on their number

If n nonmanipulator votes drawn i.i.d.,with high probability, o(√n) manipulators cannot make a difference, ω(√n) can make any alternative win that the nonmanipulators are not systematically biased against [Procaccia & Rosenschein AAMAS-07, Xia & Conitzer EC-08a]

Border case of Θ(√n) has been investigated [Walsh IJCAI-09]

Quantitative versions of Gibbard-Satterthwaite showing that under certain conditions, for some voter, even a random manipulation on a random instance has significant probability of succeeding [Friedgut, Kalai, Nisan FOCS-08; Xia & Conitzer EC-08b; Dobzinski & Procaccia WINE-08, Isaksson et al. FOCS-10]

Weak monotonicity

An instance (R, C, v, kv, kw)

is weakly monotone if for every pair of alternatives c1, c2 in C, one of the following two conditions holds:

either: c2 does not win for any manipulator votes w,

or: if all manipulators rank c2 first and c1 last, then c1 does not win.

voting rule

alternative set

nonmanipulator votes

nonmanipulator weights

manipulator weights

A simple manipulation algorithm [Conitzer & Sandholm AAAI 06]

Find-Two-Winners(R, C, v, kv, kw)

choose arbitrary manipulator votes w1

c1 ← R(C, v, kv, w1, kw)

for every c2 in C, c2 ≠ c1

choose w2 in which every manipulator ranks c2 first and c1 last

c ← R(C, v, kv, w2, kw)

if c ≠ c1 return {(w1, c1), (w2, c)}

return {(w1, c1)}

Correctness of the algorithm

Theorem. Find-Two-Winners succeeds on every instance that

(a) is weakly monotone, and

(b) allows the manipulators to make either of exactly two alternatives win.

By (b), all that remains to show is that it will return a second pair, that is, that it will terminate early.

Suppose it reaches the round where c2 is the other alternative that can win.

If c = c1 then by weak monotonicity (a), c2 can never win (contradiction).

So the algorithm must terminate.

Experimental evaluation

For what % of manipulable instances do properties (a) and (b) hold?

Depends on distribution over instances…

Use Condorcet’s distribution for nonmanipulator votes

There exists a correct ranking t of the alternatives

Roughly: a voter ranks a pair of alternatives correctly with probability p, incorrectly with probability 1-p

Independently? This can cause cycles…

More precisely: a voter has a given ranking r with probability proportional to pa(r, t)(1-p)d(r, t) where a(r, t) = # pairs of alternatives on which r and t agree, and d(r, t) = # pairs on which they disagree

Manipulators all have weight 1

Nonmanipulable instances are thrown away

p=.6, one manipulator, 3 alternatives

p=.5, one manipulator, 3 alternatives

p=.6, 5 manipulators, 3 alternatives

p=.6, one manipulator, 5 alternatives

Control problems [Bartholdi et al. 1992]

Imagine that the chairperson of the election controls whether some alternatives participate

Suppose there are 5 alternatives, a, b, c, d, e

Chair controls whether c, d, e run (can choose any subset); chair wants b to win

Rule is plurality; voters’ preferences are:

a > b > c > d > e (11 votes)

b > a > c > d > e (10 votes)

c > e > b > a > d (2 votes)

d > b > a > c > e (2 votes)

c > a > b > d > e (2 votes)

e > a > b > c > d (2 votes)

Can the chair make b win?

NP-hard

many other types of control, e.g., introducing additional voters

see also various work by Faliszewksi, Hemaspaandra, Hemaspaandra, Rothe

Tu. 17:00 Bribery, Control, and Cloning in Elections

Combinatorial alternative spaces

Multi-issue domains

Suppose the set of alternatives can be uniquely characterized by multiple issues

Let I={x1,...,xp} be the set of p issues

Let Di be the set of values that the i-th issue can take, then A=D1×... ×Dp

Example:

I={Main dish, Wine}

A={} ×{ }

Example: joint plan [Brams, Kilgour & Zwicker SCW 98]

The citizens of LA county vote to directly determine a government plan

Plan composed of multiple sub-plans for several issues

E.g.,

CP-net [Boutilier et al. UAI-99/JAIR-04]

A compact representation for partial orders (preferences) on multi-issue domains

W. 15:15 Coalition Formation and Cooperative Game Theory

Getting involved in this community

Community mailing list

https://lists.duke.edu/sympa/subscribe/comsoc

A few useful overviews

Y. Chevaleyre, U. Endriss, J. Lang, and N. Maudet. A Short Introduction to Computational Social Choice. In Proc. 33rd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM-2007), LNCS 4362, Springer-Verlag, 2007.

V. Conitzer. Making decisions based on the preferences of multiple agents. Communications of the ACM, 53(3):84–94, 2010.

V. Conitzer. Comparing Multiagent Systems Research in Combinatorial Auctions and Voting. To appear in the Annals of Mathematics and Artificial Intelligence.

P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe. A richer understanding of the complexity of election systems. In S. Ravi and S. Shukla, editors, Fundamental Problems in Computing: Essays in Honor of Professor Daniel J. Rosenkrantz, chapter 14, pages 375–406. Springer, 2009.

P. Faliszewski and A. Procaccia. AI's War on Manipulation: Are We Winning? To appear in AI Magazine.

L. Xia. Computational Social Choice: Strategic and Combinatorial Aspects. AAAI’10 Doctoral Consortium.