A brief Introductory Tutorial on Computational Social Choice



Download 2.64 Mb.
Date09.08.2018
Size2.64 Mb.

A Brief Introductory Tutorial on Computational Social Choice

  • Vincent Conitzer

Outline

  • 1. Introduction to voting theory
  • 2. Hard-to-compute rules
  • 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
  • Slater: create an overall ranking of the candidates that is inconsistent with as few pairwise elections as possible
    • NP-hard!
  • 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: ΣeE 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

Preprocessing trick for Slater

  • Set S of similar alternatives: against any alternative x outside of the set, all alternatives in S have the same result against x
  • a
  • b
  • d
  • c
  • There exists a Slater ranking where all alternatives in S are adjacent
  • A nontrivial set of similar alternatives can be found in polynomial time (if one exists)

Preprocessing trick for Slater…

  • a
  • b
  • d
  • c
  • b
  • d
  • a
  • c
  • b>d
  • solve set of similar alternatives recursively
  • solve remainder (now with weighted nodes)
  • a > b > d > c

A few recent references for computing Kemeny / Slater rankings

  • Betzler et al. COMSOC 2010
  • Betzler et al. How similarity helps to efficiently compute Kemeny rankings. AAMAS’09
  • Conitzer. Computing Slater rankings using similarities among candidates. AAAI’06
  • Conitzer et al. Improved bounds for computing Kemeny rankings. AAAI’06
  • Davenport and Kalagnanam. A computational study of the Kemeny rule for preference aggregation. AAAI’04
  • Meila et al. Consensus ranking under the exponential model. UAI’07

Dodgson

  • Recall Dodgson’s rule: candidate wins that requires fewest swaps of adjacent candidates in votes to become Condorcet winner
  • NP-hard to compute an alternative’s Dodgson score [Bartholdi, Tovey, Trick 1989]
    • Exact complexity of winner determination: complete for Θ_2^p [Hemaspaandra, Hemaspaandra, Rothe 1997]
  • Several papers on approximating Dodgson scores [Caragiannis et al. 2009, Caragiannis et al. 2010]
  • Interesting point: if we use an approximation, it’s a different rule! What are its properties? Maybe we can even get better properties?
  • Th. 14:55 Approximation of Voting Rules

Computational hardness as a barrier to manipulation

Manipulability

  • Sometimes, a voter is better off revealing her preferences insincerely, aka. manipulating
  • E.g., plurality
    • Suppose a voter prefers a > b > c
    • Also suppose she knows that the other votes are
      • 2 times b > c > a
      • 2 times c > a > b
    • Voting truthfully will lead to a tie between b and c
    • She would be better off voting e.g. b > a > c, guaranteeing b wins
  • All our rules are (sometimes) manipulable
  • Th. 14:05 Strategic Voting

Inevitability of manipulability

  • Ideally, our mechanisms are strategy-proof, but may be too much to ask for
  • Gibbard-Satterthwaite theorem:
  • Suppose there are at least 3 alternatives
  • There exists no rule that is simultaneously:
    • onto (for every alternative, there are some votes that would make that alternative win),
    • nondictatorial, and
    • strategy-proof
  • Typically don’t want a rule that is dictatorial or not onto
  • With restricted preferences (e.g., single-peaked preferences), we may still be able to get strategy-proofness
  • Also if payments are possible and preferences are quasilinear
  • W. 17:00 Mechanism Design with Payments
  • Th. 16:00 Mechanism Design in Social Choice

Single-peaked preferences

  • Suppose candidates are ordered on a line
  • a1
  • a2
  • a3
  • a4
  • a5
  • Every voter prefers candidates that are closer to her most preferred candidate
  • Let every voter report only her most preferred candidate (“peak”)
  • v1
  • v2
  • v3
  • v4
  • v5
  • Choose the median voter’s peak as the winner
    • This will also be the Condorcet winner
  • Nonmanipulable!
  • Impossibility results do not necessarily hold when the space of preferences is restricted
  • W. 10:10 Possible Winners and Single-Peaked Electorates

Computational hardness as a barrier to manipulation

  • A (successful) manipulation is a way of misreporting one’s preferences that leads to a better result for oneself
  • Gibbard-Satterthwaite only tells us that for some instances, successful manipulations exist
  • It does not say that these manipulations are always easy to find
  • Do voting rules exist for which manipulations are computationally hard to find?
  • Tu. 11:35 Computing Strategic Manipulations

A formal computational problem

  • The simplest version of the manipulation problem:
  • CONSTRUCTIVE-MANIPULATION:
    • We are given a voting rule r, the (unweighted) votes of the other voters, and an alternative p.
    • We are asked if we can cast our (single) vote to make p win.
  • E.g., for the Borda rule:
    • Voter 1 votes A > B > C
    • Voter 2 votes B > A > C
    • Voter 3 votes C > A > B
  • Borda scores are now: A: 4, B: 3, C: 2
  • Can we make B win?
  • Answer: YES. Vote B > C > A (Borda scores: A: 4, B: 5, C: 3)

Early research

  • Theorem. CONSTRUCTIVE-MANIPULATION is NP-complete for the second-order Copeland rule. [Bartholdi, Tovey, Trick 1989]
    • Second order Copeland = alternative’s score is sum of Copeland scores of alternatives it defeats
  • Theorem. CONSTRUCTIVE-MANIPULATION is NP-complete for the STV rule. [Bartholdi, Orlin 1991]
  • Most other rules are easy to manipulate (in P)

Ranked pairs rule [Tideman 1987]

  • Order pairwise elections by decreasing strength of victory
  • Successively “lock in” results of pairwise elections unless it causes a cycle
  • a
  • b
  • d
  • c
  • 6
  • 8
  • 10
  • 2
  • 4
  • 12
  • Final ranking: c>a>b>d
  • Theorem. CONSTRUCTIVE-MANIPULATION is NP-complete for the ranked pairs rule [Xia et al. IJCAI 2009]

“Tweaking” voting rules

  • It would be nice to be able to tweak rules:
    • Change the rule slightly so that
      • Hardness of manipulation is increased (significantly)
      • Many of the original rule’s properties still hold
  • It would also be nice to have a single, universal tweak for all (or many) rules
  • One such tweak: add a preround [Conitzer & Sandholm IJCAI 03]

Adding a preround [Conitzer & Sandholm IJCAI-03]

  • A preround proceeds as follows:
    • Pair the alternatives
    • Each alternative faces its opponent in a pairwise election
    • The winners proceed to the original rule
  • Makes many rules hard to manipulate

Preround example (with Borda)

    • Voter 1: A>B>C>D>E>F
    • Voter 2: D>E>F>A>B>C
    • Voter 3: F>D>B>E>C>A
    • A gets 2 points
    • F gets 3 points
    • D gets 4 points and wins!
    • Voter 1: A>D>F
    • Voter 2: D>F>A
    • Voter 3: F>D>A
    • A vs B: A ranked higher by 1,2
    • C vs F: F ranked higher by 2,3
    • D vs E: D ranked higher by all
    • Match A with B
    • Match C with F
    • Match D with E
    • STEP 1:
    • A. Collect votes and
    • B. Match alternatives
    • (no order required)
    • STEP 2:
    • Determine winners of preround
    • STEP 3:
    • Infer votes on remaining alternatives
    • STEP 4:
    • Execute original rule
    • (Borda)

Matching first, or vote collection first?

  • Match, then collect
  • “A vs C,
  • B vs D.”
  • “D > C > B > A”
  • “A vs C,
  • B vs D.”
  • “A vs C,
  • B vs D.”
  • “A > C > D > B”
  • Collect, then match (randomly)

Could also interleave…

  • Elicitor alternates between:
    • (Randomly) announcing part of the matching
    • Eliciting part of each voter’s vote
  • “A vs F”
  • “C > D”
  • “B vs E”
  • “A > E”

How hard is manipulation when a preround is added?

  • Manipulation hardness differs depending on the order/interleaving of preround matching and vote collection:
  • Theorem. NP-hard if preround matching is done first
  • Theorem. #P-hard if vote collection is done first
  • Theorem. PSPACE-hard if the two are interleaved (for a complicated interleaving protocol)
  • In each case, the tweak introduces the hardness for any rule satisfying certain sufficient conditions
    • All of Plurality, Borda, Maximin, STV satisfy the conditions in all cases, so they are hard to manipulate with the preround

What if there are few alternatives? [Conitzer et al. JACM 2007]

  • The previous results rely on the number of alternatives (m) being unbounded
  • There is a recursive algorithm for manipulating STV with O(1.62m) calls (and usually much fewer)
  • E.g., 20 alternatives: 1.6220 = 15500
  • Sometimes the alternative space is much larger
    • Voting over allocations of goods/tasks
    • California governor elections
  • But what if it is not?
    • A typical election for a representative will only have a few

STV manipulation algorithm [Conitzer et al. JACM 2007]

  • Idea: simulate election under various actions for the manipulator
  • rescue d
  • don’t rescue d
  • d eliminated
  • c eliminated
  • no choice for manipulator
  • b eliminated
  • no choice for manipulator
  • d eliminated
  • rescue a
  • don’t rescue a
  • rescue a
  • don’t rescue a
  • no choice for manipulator
  • b eliminated
  • a eliminated
  • rescue c
  • don’t rescue c

Analysis of algorithm

  • 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
  • Can we make our preferred alternative p win?
  • E.g., another Borda example:
  • Voter 1 (weight 4): A>B>C, voter 2 (weight 7): B>A>C
  • Manipulators: one with weight 4, one with weight 9
  • Can we make C win?
  • Yes! Solution: weight 4 voter votes C>B>A, weight 9 voter votes C>A>B
    • Borda scores: A: 24, B: 22, C: 26

A simple example of hardness

  • We want: given the other voters’ votes…
  • … it is NP-hard to find votes for the manipulators to achieve their objective
  • Simple example: veto rule, constructive manipulation, 3 alternatives
  • Suppose, from the given votes, p has received 2K-1 more vetoes than a, and 2K-1 more than b
  • The manipulators’ combined weight is 4K
    • every manipulator has a weight that is a multiple of 2
  • The only way for p to win is if the manipulators veto a with 2K weight, and b with 2K weight
  • But this is doing PARTITION => NP-hard!

What does it mean for a rule to be easy to manipulate?

  • Given the other voters’ votes…
  • …there is a polynomial-time algorithm to find votes for the manipulators to achieve their objective
  • If the rule is computationally easy to run, then it is easy to check whether a given vector of votes for the manipulators is successful
  • Lemma: Suppose the rule satisfies (for some number of alternatives):
    • If there is a successful manipulation…
    • … then there is a successful manipulation where all manipulators vote identically.
  • Then the rule is easy to manipulate (for that number of alternatives)
    • Simply check all possible orderings of the alternatives (constant)

Example: Maximin with 3 alternatives is easy to manipulate constructively

  • Recall: alternative’s Maximin score = worst score in any pairwise election
  • 3 alternatives: p, a, b. Manipulators want p to win
  • Suppose there exists a vote vector for the manipulators that makes p win
  • WLOG can assume that all manipulators rank p first
    • So, they either vote p > a > b or p > b > a
  • Case I: a’s worst pairwise is against b, b’s worst against a
    • One of them would have a maximin score of at least half the vote weight, and win (or be tied for first) => cannot happen
  • Case II: one of a and b’s worst pairwise is against p
    • Say it is a; then can have all the manipulators vote p > a > b
      • Will not affect p or a’s score, can only decrease b’s score

Results for constructive manipulation

Destructive manipulation

  • Exactly the same, except:
  • Instead of a preferred alternative
  • We now have a hated alternative
  • Our goal is to make sure that the hated alternative does not win (whoever else wins)

Results for destructive manipulation

Hardness is only worst-case…

  • Results such as NP-hardness suggest that the runtime of any successful manipulation algorithm is going to grow dramatically on some instances
  • But there may be algorithms that solve most instances fast
  • Can we make most manipulable instances hard to solve?

Bad news…

  • Increasingly many results suggest that many instances are in fact easy to manipulate
  • Heuristic algorithms and/or experimental (simulation) evaluation [Conitzer & Sandholm AAAI-06, Procaccia & Rosenschein JAIR-07, Conitzer et al. JACM-07, Walsh IJCAI-09 / ECAI-10, Davies et al. COMSOC-10]
  • 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
  • c1R(C, v, kv, w1, kw)
  • for every c2 in C, c2 ≠ c1
    • choose w2 in which every manipulator ranks c2 first and c1 last
    • cR(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.
  • Proof.
    • The algorithm is sound (never returns a wrong (w, c) pair).
    • 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
  • An CP-net consists of
    • A set of variables x1,...,xp, taking values on D1,...,Dp
    • A directed graph G over x1,...,xp
    • Conditional preference tables (CPTs) indicating the conditional preferences over xi, given the values of its parents in G

CP-net: an example

  • Variables: x,y,z.
  • DAG, CPTs:
  • This CP-net encodes the following partial order:

Sequential voting rules [Lang IJCAI-07/Lang and Xia MSS-09]

  • Inputs:
    • A set of issues x1,...,xp, taking values on A=D1×... ×Dp
    • A linear order O over the issues. W.l.o.g. O=x1>...>xp
    • p local voting rules r1,...,rp
    • A profile P=(V1,...,Vn) of O-legal linear orders
      • O-legal means that preferences for each issue depend only on values of issues earlier in O
  • Basic idea: use r1 to decide x1’s value, then r2 to decide x2’s value (conditioning on x1’s value), etc.
  • Let SeqO(r1,...,rp) denote the sequential voting rule

Sequential rule: an example

  • Issues: main dish, wine
  • Order: main dish > wine
  • Local rules are majority rules
  • V1: > , : > , : >
  • V2: > , : > , : >
  • V3: > , : > , : >
  • Step 1:
  • Step 2: given , is the winner for wine
  • Winner: ( , )
  • Xia et al. [AAAI’08, AAMAS’10] study rules that do not require CP-nets to be acyclic

Strategic sequential voting

  • Binary issues (two possible values each)
  • Voters vote simultaneously on issues, one issue after another
  • For each issue, the majority rule is used to determine the value of that issue
  • Game-theoretic analysis?

Strategic voting in multi-issue domains

  • In the first stage, the voters vote simultaneously to determine S; then, in the second stage, the voters vote simultaneously to determine T
  • If S is built, then in the second step so the winner is
  • If S is not built, then in the 2nd step so the winner is
  • In the first step, the voters are effectively comparing and , so the votes are , and the final winner is
  • S
  • T
  • [Xia et al. 2010; see also Farquharson 69, McKelvey & Niemi JET 78, Moulin Econometrica 79, Gretlein IJGT 83, Dutta & Sen SCW 93]

Multiple-election paradoxes for strategic voting [Xia et al. 2010]

  • Theorem (informally). For any p≥2 and any n≥2p2 + 1, there exists a profile such that the strategic winner is
    • ranked almost at the bottom (exponentially low positions) in every vote
    • Pareto dominated by almost every other alternative
    • an almost Condorcet loser
    • multiple-election paradoxes [Brams, Kilgour & Zwicker SCW 98], [Scarsini SCW 98], [Lacy & Niou JTP 00], [Saari & Sieberg 01 APSR], [Lang & Xia MSS 09]

Preference elicitation / communication complexity

Preference elicitation (elections)

  • >
  • center/auctioneer/organizer/…
  • ?”
  • “yes”
  • >
  • ?”
  • “no”
  • “most preferred?”
  • >
  • ?”
  • “yes”
  • wins

Elicitation algorithms

  • Suppose agents always answer truthfully
  • Design elicitation algorithm to minimize queries for given rule
  • What is a good elicitation algorithm for STV?
  • What about Bucklin?
  • An elicitation algorithm for the Bucklin voting rule based on binary search [Conitzer & Sandholm EC’05]
  • Alternatives: A B C D E F G H
  • Top 4?
  • {A B C D}
  • {A B F G}
  • {A C E H}
  • Top 2?
  • {A D}
  • {B F}
  • {C H}
  • Top 3?
  • {A C D}
  • {B F G}
  • {C E H}
  • Total communication is nm + nm/2 + nm/4 + … ≤ 2nm bits
  • (n number of voters, m number of candidates)

Other topics in computational voting theory

  • Preference elicitation
    • How do we compute the winner with minimal communication?
    • Given partial information about the votes, which alternatives can still win?
  • Settings with exponentially many alternatives
  • W. 10:10 Possible Winners and Single-Peaked Electorates

A few other topics in computational social choice

  • Allocating resources to agents
    • “Fair” allocations
  • Judgment aggregation
  • Matching
  • Cooperative game theory
    • Weighted voting games, power indices
  • Tu. 15:25 Multiagent Resource Allocation, Fairness, Judgment Aggregation
  • W. 11:35 Cake Cutting Algorithms
  • Th. 10:10 Matchings and Social Choice
  • 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.



Share with your friends:


The database is protected by copyright ©sckool.org 2019
send message

    Main page