Robust Winners and Winner Determination Policies under ...

Robust Winners and Winner Determination Policies under ...

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

Recently Viewed Presentations

  • OPTIC Strategy

    OPTIC Strategy

    Why Use OPTIC?-A text can be anything (speech, non-fiction piece, poem, advertisement, fiction piece, visual).-Many students panic when they have to analyze a visual (i.e. your WOD on 3D Printing).
  • Welcome Back Scientists! AS YOU PREPARE TO TAKE

    Welcome Back Scientists! AS YOU PREPARE TO TAKE

    Students will understand the effects of the relative positions of the earth, moon and sun. a. Demonstrate the phases of the moon by showing the alignment of the earth, moon, and sun. b. Explain the alignment of the earth, moon,...
  • The Dawn of New Possibilities - Diocese of Oxford

    The Dawn of New Possibilities - Diocese of Oxford

    School Chaplaincy in the Diocese of Oxford. ... Incumbent, Team, PCC, Deanery, other churches? Who in the school understands and is sympathetic with a vision of increasing church/Christian outreach to schools? VICE/VERSA parish to schools.
  • ICD-10 Ready or Not here it comes! Coding

    ICD-10 Ready or Not here it comes! Coding

    Show providers examples of the type of terminology needed to show. stage, status, exacerbation, relapse and other qualifiers for conditions that can vary widely in their acuity and severity. ... Hierarchy Coding Category (HCC) ICD-10 Code Build.
  • 1Copyright  2015, Oracle and/or its affiliates. All rights

    1Copyright 2015, Oracle and/or its affiliates. All rights

    Accrual preference for interest component in status change . Reversal of interest income during status change with options . Liquidation order will be used to liquidated the components due on this order . Different types of Static and User defined...
  • My Last Duchess - missarchergcse.weebly.com

    My Last Duchess - missarchergcse.weebly.com

    The poem is a dramatic monologue.This means the poem is written in the voice of a character, a male narrator - an imaginary Italian Duke.. When? Browning wrote the poem in 1842. However, it seems likely that his idea for...
  • Adapting Falls Prevention Education for the Local Aboriginal

    Adapting Falls Prevention Education for the Local Aboriginal

    The chosen method maximised the benefit of eudaimonic wellbeing for the participants, who expressed attitudes and intentions to make a behavioural change related to falls prevention. The results of the personal action plan show only conveyed intentions to change. A...
  • Ict Development Fund (Ict -df) Legislation

    Ict Development Fund (Ict -df) Legislation

    In line with the NDP, USAASA through USAF projects provides broadband infrastructure and ICT connectivity in the underserved. SA Connect. Provides guidance on building an access or core network, coordinates building programmes for efficiency, and promote universal access through efficient...