Robust Winners and Winner Determination Policies under Candidate Uncertainty JOEL OREN, UNIVERSITY OF TORONTO JOINT WORK WITH CRAIG BOUTILIER , JRME L ANG AND HCTOR PAL ACIOS . 1 Motivation Winner Determination under Candidate Uncertainty A committee, with preferences over alternatives: Prospective projects. Goals. a? ?b a b c b c

?c Best alternative depends on available ones. 2 voters Costly determination of availabilities: Market research for determining the feasibility of a project: engineering estimates, surveys, focus groups, etc. 4 voters 3 voters c a b a Winner ac 2 Efficient Querying Policies for Winner Determination 4 voters 3 voters

Voters submit votes in advance. Query candidates sequentially, until enough is known in order to a determine the winner. a? ?b b b c c a c Example: a wins. 2 voters c a b

a Winner 3 3 voters 2 voters The Formal Model A set C of candidates. A vector, , of rankings (a preference profile). Set is partitioned: 1. a priori known availability. 2. the unknown set. Each candidate is available with probability . Voting rule: is the election winner. a b c b c a c a

b C Y U b c a (available) (unknown) 4 3 voters 2 voters Querying & Decision Making At iteration submit query q(x), . a b c Information set . b c

a Initial available set . c a b Upon querying candidate : If available: add to . If unavailable: remove from . restriction of pref. profile to the candidate set . Stop when is -sufficient no additional querying will change the robust winner. + a b ? C ? b

c a 0.5 0.7 0.4 5 Computing a Robust Winner Robust winner: Given , is a robust winner if . A related question in voting: [Destructive control by candidate addition] Candidate set , disjoint spoiler set , pref. profile over , candidate , voting rule . Question: is there a subset , s.t. ? Proposition: Candidate is a robust winner there is no destructive control against , where the spoiler set is . Y x Y ( ( ) )= ) )= 6 Computing a Robust Winner Proposition: Candidate is a robust winner there is no destructive control against , where the spoiler set is . Implication: Pluarlity, Bucklin, ranked pairs coNP-complete; Copeland, Maximin polytime tractable. Additional results: Checking if is a robust winner for top cycle, uncovered set, and Borda can be done in polynomial time.

Top-cycle & Uncovered set: prove useful criteria for the corresponding majority graph. 7 The Query Policy Goal: design a policy for finding correct winner. a Can be represented by a decision tree. b b Example for the vote profile (plurality): abcde, abcde, adbec, bcaed, bcead, cdeab, cbade, cdbea U a b c d + a c b b a

wins c wins c a wins b wins c a wins 8 Winner Determination Policies as Trees r-Sufficient tree: Information set at each leaf is -sufficient. Each leaf is correctly labelled with the winner. -- cost of querying candidate/node . \{,} a b a wins b c

b wins c expected cost of policy, over dist. of . c wins a wins a wins 9 Recursively Finding Optimal Decision Trees Cost of a tree: . For each node a training set: Possible true underlying sets A, that agree with . Example 1: Example 2: . Can solve using a dynamic-programming approach. Running time: -- computationally heavy. a b a

wins c wins b c a wins b wins c a wins 10 Myopically Constructing Decision Trees Well-known approach of maximizing information gain at every node until reached pure training sets leaves (C4.5). Mypoic step: query the candidate for the highest information gain (decrease in entropy of the training set). Running time: 11 Empirical Results 100 votes, availability probability . Dispersion parameter . distribution). ( uniform

Tested for Plurality, Borda, Copeland. Preference distributions drawn i.i.d. from Mallows -distribution: probabilities decrease exponentially with distance from a reference ranking. = Method 0.3 0.5 0.9 Plurality, Plurality, DP DP Plurality, Myopic Plurality, Myopic Borda, DP Borda, Borda, DP Myopic Borda, Myopic 4.1 4.1 4.1 4.1 3.7 3.7 3.7 3.7

3.4 3.4 3.5 3.5 2.7 2.7 2.7 2.7 2.7 2.7 2.8 2.8 1.7 1.7 1.7 1.7 Average cost (# of queries) 12 Empirical Results Cost decrease as increases [ less uncertainty about the available candidates set]. Myopic performed very close to the OPT DP alg. 0.3 0.5 0.9 Method Method

Plurality, DP 4.1 3.4 2.7 Plurality, DP 4.1 3.4 2.7 Plurality, Myopic 4.1 3.5 2.8 Cost increases with the dispersion parameter Plurality, Myopic 4.1 3.5 2.8 Borda, DP 3.7 2.7 1.7 noisier/more diverse preferences (not shown). Borda, 3.7 2.7 1.7 Borda, DP Myopic 3.7 2.7 1.7 -Approximation: stop the recursion when training set Borda, Myopic 3.7 2.7 1.7 is pure.

Average cost (# of queries) For plurality, , , . For , . Not shown: 13 Additional Results Query complexity: expected number of queries under a worst-case preference profile. Result: For Plurality, Borda, and Copeland, worst-case exp. query complexity is . Simplified policies: Assume for all . Then there is a simple iterative query policy that is asymptotically optimal as . 14 Conclusions & Future Directions A framework for querying candidates under a probabilistic availability model. Connections to control of elections. Two algorithms for generating decision trees: DP, Myopic. Future directions: 1. Ways of pruning the decision trees (depend on the voting rules). 2. Sample-based methods for reducing training set size. 3. Deeper theoretical study of the query complexity. 15