Efficient Voting via Top-k Elicitation Scheme: A Probabilistic Approach

Slide Note

This work presents a probabilistic approach for efficient voting through the top-k elicitation scheme, focusing on communication-efficient group decision-making. The goal is to select the best outcome while minimizing the extraction of excessive information from committee members. The study explores methods for aggregating preferences, efficient preference elicitation, and different voting rules including score-based and positional scoring rules. The top-k elicitation scheme aims to determine the necessary information length to pick a winner based on a prescribed voting rule.

merryn Follow

Uploaded on Aug 10, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript

Efficient Voting via the Top-k Elicitation Scheme: A Probabilistic Approach Joel Oren, University of Toronto Joint work with Yuval Filmus, Institute of Advanced Study 1

Motivation Common theme: communication-efficient group decision- making. How to pick the single best item/candidate, without extracting too much information from the customers/committee members. Hiring committees: members can t rank all of the candidates. Too many candidates. Committee members may only be familiar with just subsets of candidates in their own fields. 2

The Basic Setting Candidates (alternatives/products): ? = {?1,?2, ,??} Agents with preferences over the possible outcomes. ?7 ?19 ?5 ?3 ?1 ?2 1. A canonical task: select the best outcome. 2. What is the information need for doing so. 1. Social choice: methods for aggregating preferences. 2. Efficient preference elicitation. 3

Basic Definitions ? = {?1, ,??} candidates, ?(?) set of all orderings over ?. Voter set ? = {1, ,?} with preferences ? = (??)?=1 Voting rule: ?:? ?? ?. Score-based voting rules: assign each candidate a score, pick the one with maximal score (most voting rules). ? ? ??. ? ? = ??????? ???? ? ? 1,1 2,1 1,1 2,1 1,1 2,1 3, 3, ?,? 1,? 2 3, ?,?2,?3, ?,? 1,? 2 ?,?2,?3, ?,? 1,? 2 ?,?2,?3, Borda Harmonic Geometric ?1 ?2 ?3 ?5 ?3 ?2 ?7 ?19 Positional scoring rules (PSR): score vector ? ??, ? th ranked candidate receives a score of ??. Question: do we really need to know all of ? to pick ? ? ? 4

Top-? Voting The General Elicitation Scheme Given a prescribed voting rule ? , ask each voter to report only his the length-? prefix of her preferences. Voter ? reports only ??,?= ?? The top-? elicitation scheme: an algorithm that 1. Elicits ??= ?1,?, ,??,?. 2. Computes a function ? that picks a winner `based on ?? and the voting rule ?( ). 11 , ,?? 1? . Question: how large does ? need to be so that ? ? = ? ??? 5

Previous Work Theoretically: many common voting rules require a lot of information from the voters, in the worst case [Conitzer & Sandholm 02,05, Xia & Conitzer 08]. Top-? voting: Complexity of finding possible/necessary winners [Baumeister et al. 12]. Empirically: in practice, top-? voting performs well [Kalech et al. 11]. Bridging the gap: assume a distributional model of preferences. Lu & Boutilier 11: studied the performance of partial preference elicitation for regret-minimization a objective, under distributional assumptions. Recently: A lower-bound on ?, for selecting the Borda winner in an impartial culture [O, Filmus, Boutilier 13]. 6

A Distributional Approach to Top-? Voting Input: Scoring rule: ??:? ? ?? ?+. Focus: positional scoring rules. Top-? algorithm ?? Each preference ??: drawn i.i.d. from distribution ? over ?(?). Output: ?? ??:given top-? votes, selects a winning candidate. ??(??). ??(??) ?? ?? ?? ?????? ??(?,?) ?1 ?2 ?5 ?3 ?7 ?19 ? ???? = ??????? ???(?,?), w.h.p. Q: for which ?, Ak 7

Three Distributional Models (and high-level Results) Three distributional models (increasing order of hardness): 1. Biased Distributions: distributions that favor one particular candidate over all else. (positionally-biased, pairwise-biased). Overall results: As ? , ? 1 is sufficient for many scoring rules. See paper for details. 2. Impartial Culture: ? is the uniform distribution over ?(?). Main results: a) PSRs: an almost tight threshold theorem. b) Additional scoring rule: Copeland. 3. Adversarial: ? is set by an adversary, but is fully known to us. Main results: a) Harmonic PSR: A worst-case distribution requiring ? = (?). b) Geometric PSR: for any D,? = ?(log?) sufficient; this is tight. 8

Top-? for PSRs: under an Impartial Culture Goal: Given a score vector ? ??, s.t. ?? ??+1, determine a LB and an UB in the limit ? . Possible algorithms the upper bound: 1. OPT alg.: compute the winning prob. of candidates not clear how to rigorously analyze such an algorithm. 2. Na ve: ? ?, ? ?, if ??? ?, ??? 0, otherwise. 3. FairCutOff: like Na ve, but if ??? > ?, ??? ?? ?+1, ,?[??]. ?? = ???(?), ??? ?? = ?? = ?? ?+1, ,?[??] 11 ?? 22 ?? 1? ?? 1? + 1 ?? 1? ?? ??,? ?? ?1 ?2 ?? 0 0 9

Empirical Results for the three algorithms ? = 2000,? = 20, 10? sample populations. FairCutoff overlaps with Opt FairCutoff overlaps with Opt Borda Harmonic ? = (1,1 2,1 1 ?) ? = (? 1,? 2, ) 3, , 10

A Threshold Theorem for PSRs The top-? scores according to FairCutoff: for ? [?], ??,?? ? ? ???? = ?? ??+1, ,? ??,? > ? We consider a measure depending on the amount of noise in each of the two parts of the score vector, in terms of ???,??: ??= ???? ??[???? ], ??= ???? ?[?]?? ? ???(?) Set ??= ??/?? the ?-partition variability ratio. Theorem: in the limit ? LB: if ??= ?(log?), no top-? can determine the right winner w.p. 1 ??(1). UB: if ??= ? log4/3? , then FairCutoff determines the right winner w.p. 1 ??1 . 11

Applications Theorem: in the limit ? LB: if ??= ?(log?), no top-? can determine the right winner w.p. 1 ??(1). UB: if ??= ? log4/3? , then FairCutoff determines the right winner w.p. 1 ??1 . 2, ??= ?? ,??= ?2 Borda: assuming that ? ??= ? = ?(log?). Gives a LB of (?) (improvement over the previous bound of ? ? ? log ?). Harmonic: UB k = ? log4/3? is sufficient, LB ? = (log?). Geometric: (? = (?,?2,?3, )) UB ? = ?(loglog?) -- sufficient, LB ? = (loglog?). 12

Proof Sketch Order Statistics of Correlated RVs Upper bound: ??= ? ???4/3? FairCutoff guesses the right winner w.h.p. 11 ?? 12 ?? ?2 1? ?? ?? ?1 ?? ?+1, ,?[??] ?? For each candidate, partition voter scores based on top- ?/bottom-(? ?) partition: ?1,?? ?1: ?2,?? ?2: ??,?? ??: ??1?1 + ??2?1 + ??1?2 + ??2?2 + ??1?? + ??2?? + ??(1)?? + ??2?? ??(1)?1 + ??2?1 ??(1)?2 + ??2?2 + + + ???(?1) ???(?2) ???(??) 13

Proof Sketch (continued) Each candidate s score is the sum: sc c = ??1? + ??2(?). Score according to top-?:???? = sc1c + E[sc2c ]. First and second order statistics: ????= ???????{???? },?2???= ??????? ?max{???? }. First step: estimate the distribution of ??????? ????2???. Complication: the ???( ) scores are correlated diagonalize covariance matrix via a linear transformation, without affecting the distribution of the difference. Approximate via CLT + order statistics analysis of Gaussian RVs. Difference grows as variance of ??(1)(?) grows (??). Second step: switch from ??2(?) to ? ??(2)?loses the added noise has a bounded effect (use ??) above gap won t be closed, w.h.p. 14

Top-? elicitation under Coplelands rule The scoring rule: for every two distinct candidates ?,? ?, set(?,? ) = 1[ 1] if ? beats [loses to] ? in a pairwise election. If there s a tie, set ?? ?,? = 0. A candidate s score is: ?? ? = ? ???(?,? ). Theorem: for ? ?/ log?, no top-? algorithm predicts the correct winner w.p. 1 ??(1) (? ). 15

The Adversarial Model The preference distribution ? is set by an adversary the full specifications are given to the decision maker. How bad can the bounds be for that case? Borda: already got a lower bound of ? = (?). Harmonic: we have a polylog UB for the impartial culture. Theorem: For a fixed ?, there is a distribution ??, such that any top-? algorithm requires k = ? , under the harmonic scoring rule. Geometric: a (loglog?) UB under an impartial culture. Theorem: if the decay factor ? (0,1) is fixed, then ? = ?(log?) is sufficient under the geometric scoring rule, under any distribution, and this is tight. 16

Conclusions & Future Directions A rigorous, probabilistic analysis of the top-? elicitation scheme. Under impartial culture: a principled method of analysis with applications: LB UB Scoring rule (?) [prev. (?/log?)] Borda ?(???4/3?) (log?) Harmonic (loglog?) ?(loglog?) Geometric Copeland (?/ log?) (future: ? ?) Result for Copeland: extension to weighted majority graph based rules? Can we extend our results to other rules? More involved distributions: mixture models. Top-k for proportional representation. 18