Strategy-Proof Voting: Approximations and Possibilities
Approximately Strategy-Proof
Voting
Eleanor Birrell
Rafael Pass
Cornell University
u
Charlie
(A) = 1
u
Charlie
(B) = .9
u
Charlie
(C) = .2
The Model
…
A
B
C
σ
Charlie
(A) >
σ
Charlie
(B)
σ
Charlie
(B) >
σ
Charlie
(C)
Goal:
Voters honestly report their
preference
σ
f
Goal:
f
is
strategy-proof
u
i
(j)
Є
[
0,1
]
Circumventing Gibbard-Satterthwaite
•
Hard to manipulate?
–
BTT89, FKN09, IKM10
•
Randomized Approximations?
–
CS06, Gibb77, Proc10
•
Restricted preferences?
–
Moul80
•
Relaxed Problem?
ε
- Strategy Proof:
By lying, no
voter can improve their utility
very much
δ - Approximations:
f’
returns an
outcome that is
close
to
f(
σ
)
A
B
f
C
u
Charlie
(A) = 1
u
Charlie
(B) = .9
u
Charlie
(C) = .2
Strategy Proof:
By lying (mis-reporting their preference
σ
i
), no
voter can improve their utility
u
i
.
ε
-Strategy Proof:
By lying (mis-reporting their preference
σ
i
), no
voter can improve their utility
u
i
by more than
ε
.
ɛ-
Strategy-Proof Voting
Strategy Proof:
ε
-Strategy Proof:
δ - Approximations
Defining “Close”
Defining Approximation
•
f’
is a δ-approx. of
f
if the
outcome of
f’
is always
close
to that of
f .
•
Distance depends on
both input and output:
f’(x) = f(y)
s.t.
Δ(x,y) <
δ
σ
Alice
σ
Bob
σ
Charlie
σ
Zelda
…
σ
'
Bob
σ
‘
Zelda
Is
ε
-Strategy Proof Voting Possible?
ε
-Strategy Proof Voting:
A Construction
Deterministic Rule (
f
):
Approximation (
f’
):
ε
-Strategy Proof Voting:
A Construction
A
B
C
{A, B, C}{A, C, B}{C, A, B}{C, B, A}Distance: d
f
(
f
(
σ
), j)
Proportional Probability: Pr [
f’
(
σ
) = j ]
How Good is This?
• Every voting rule has a .05-strategy-proof 650-approx.
• And a . 01-strategy-proof 3,250-approx.
• And a .005-strategy-proof 6,500-approx.
• And a .001-strategy-proof 32,500-approx.
• And a .0005-strategy-proof 65,000-approx.
This is Asymptotically Optimal
h(
σ
):=
i=1
i=n
…
…
…
j=1
j=k
j=1
j=k
Return g(
σ
)
Select player
i
:
Select rank
j
:
Prob:
k
ε
(k-1)
k
ε
(k-k)
k
ε
(k-1)
k
ε
(k-k)
Punish Deviating
Reduction:
ε
-SP to 0-SP
p
p
1 - np
Summary
Thank you!
•
A new technique for circumventing Gibbard-Satterthwaite
•
Extensions
•
Small elections?
•
Uncertainty in inputs?
Explore the concept of approximately strategy-proof voting through models and constructions, aiming to prevent manipulation while ensuring fair outcomes. Discuss the challenges and potential methods to circumvent manipulations based on Gibbard-Satterthwaite theorems. Delve into defining approximations and the possibility of achieving strategy-proof voting.
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
Approximately Strategy-Proof Voting Eleanor Birrell Rafael Pass Cornell University
The Model uCharlie (A) = 1 uCharlie (B) = .9 uCharlie (C) = .2 Charlie (B) > Charlie (C) Alice = {A,B,C} Bob = {C, A, B} Charlie = {A,C,B} Zelda = {C,B,A} Charlie (A) > Charlie (B) ui(j) [0,1] f Goal: f is strategy-proof Goal: f is strategy-proof Goal: f is strategy-proof Goal: Voters honestly report their preference A B C Bad News: Only if f is dictatorial or binary. [Gibb73, Gibb77, Satt75] [Gibb73, Gibb77, Satt75] Bad News: Only if f is trivial.
Circumventing Gibbard-Satterthwaite Hard to manipulate? BTT89, FKN09, IKM10 Randomized Approximations? CS06, Gibb77, Proc10 Restricted preferences? Moul80 Relaxed Problem? - Strategy Proof: By lying, no voter can improve their utility very much - Approximations: f returns an outcome that is close to f( )
-Strategy-Proof Voting uCharlie (A) = 1 uCharlie (B) = .9 uCharlie (C) = .2 Alice Bob Charlie Zelda f Strategy Proof: By lying (mis-reporting their preference i), no voter can improve their utility ui . Strategy Proof: -Strategy Proof: By lying (mis-reporting their preference i), no voter can improve their utility ui by more than . -Strategy Proof: A B C
- Approximations Defining Approximation Defining Close f is a -approx. of f if the outcome of f is always close to that of f . Alice Bob Charlie Zelda 'Bob Zelda Distance depends on both input and output: f (x) = f(y) s.t. (x,y) < 6 5 4 4 2 2 0 A B C
Is -Strategy Proof Voting Possible? = o (1/n) = (1/n) = n No Yes Theorem 1: Theorem 2:
-Strategy Proof Voting: A Construction Deterministic Rule ( f ): Approximation ( f ): d = 1 d = 1 d = 2 d = 2 d = 3 d = 3 d = 4 d = 4 d = 5 d = 5
-Strategy Proof Voting: A Construction A {A, B, C} Proportional Probability: Pr [ f ( ) = j ] ? Note: Only works 1 {C, A, B} for 0.8 f B {A, C, B} 0.6 0.4 /3 0.2 C 0 {C, B, A} 1 0 2 3 Distance: df( f( ), j) A C B 1
How Good is This? Every voting rule has a .05-strategy-proof 650-approx. And a . 01-strategy-proof 3,250-approx. And a .005-strategy-proof 6,500-approx. And a .001-strategy-proof 32,500-approx. And a .0005-strategy-proof 65,000-approx. Candidate Votes Obama 69,498,215 McCain 59,948,240 Nader 738,720 Baldwin 199,437 McKinney 161,680 Candidate Carpenter Fishpaw Cole Sweeney Carlson Votes 6,582 5,865 4,500 1,988 1,837
This is Asymptotically Optimal 0-strategy proof prob. dist. over trivial rules. [Gibb77] -strategy proof prob. dist. over trivial rules ( = o(1/n)). = o(1/n) no good -strategy proof approx of Plurality. h( ):= trival no good approx. Reduction: -SP to 0-SP Punish Deviating Return g( ) i=1 i=n Select player i: p p j=1 j=k Select rank j: j=1 j=k 1 - n k (k-j) j 1 - np k (k-1) k (k-k) k (k-1) k (k-k) Prob: 0-strategy proof trivial trivial
Summary = o (1/n) = (1/n) No Yes = n A new technique for circumventing Gibbard-Satterthwaite Extensions Small elections? Uncertainty in inputs? Thank you!
