Social Welfare and Voting Systems
Social Welfare, Arrow +
Gibbard-
Satterthwaite,
VCG+CPP
1
TexPoint fonts used in EMF.
Read the TexPoint manual before you delete this box.:
A
A
A
A
A
A
A
A
Collectively choose among outcomes
◦
Elections,
◦
Choice of Restaurant
◦
Rating of movies
◦
Who is assigned what job
◦
Goods allocation
◦
Should we build a bridge?
Participants have
preferences
over outcomes
A social choice function
aggregates those
preferences and
picks an outcome
If there are
two
options and an odd number of
voters
Each having a clear preference between the
options
Natural choice:
majority voting
Sincere/Truthful
Monotone
Merging two sets where the majorities are
the same preserves majority
Order of queries has no significance
If we start pairing the alternatives:
Order may matter
Assumption:
n
voters give their complete ranking on set
A
of alternatives
L
– the set of
linear orders
on
A
(permutations).
Each voter i provides
Á
i
2
L
◦
Input to the aggregator/voting rule is
(
Á
1
,
Á
2
,… ,
Á
n
)
Goals
A function
f: L
n
A
is called a
social choice function
◦
Aggregates voters preferences and selects a
winner
A function
W: L
n
L
is called a
social welfare function
◦
Aggergates voters preference into a
common order
a
1
a
2
a
m
A
a
10
, a
1
, … , a
8
S
c
o
r
i
n
g
r
u
l
e
s
:
d
e
f
i
n
e
d
b
y
a
v
e
c
t
o
r
(
a
1
,
a
2
,
…
,
a
m
)
Being ranked
i
th in a vote gives the candidate
a
i
points
•
P
l
u
r
a
l
i
t
y
:
d
e
f
i
n
e
d
b
y
(
1
,
0
,
0
,
…
,
0
)
–
W
i
n
n
e
r
i
s
c
a
n
d
i
d
a
t
e
t
h
a
t
i
s
r
a
n
k
e
d
f
i
r
s
t
m
o
s
t
o
f
t
e
n
•
V
e
t
o
:
i
s
d
e
f
i
n
e
d
b
y
(
1
,
1
,
…
,
1
,
0
)
–
W
i
n
n
e
r
i
s
c
a
n
d
i
d
a
t
e
t
h
a
t
i
s
r
a
n
k
e
d
l
a
s
t
t
h
e
l
e
a
s
t
o
f
t
e
n
•
B
o
r
d
a
:
d
e
f
i
n
e
d
b
y
(
m
-
1
,
m
-
2
,
…
,
0
)
P
l
u
r
a
l
i
t
y
w
i
t
h
(
2
-
c
a
n
d
i
d
a
t
e
)
r
u
n
o
f
f
:
t
o
p
t
w
o
c
a
n
d
i
d
a
t
e
s
i
n
t
e
r
m
s
o
f
p
l
u
r
a
l
i
t
y
s
c
o
r
e
p
r
o
c
e
e
d
t
o
r
u
n
o
f
f
.
S
i
n
g
l
e
T
r
a
n
s
f
e
r
a
b
l
e
V
o
t
e
(
S
T
V
,
a
k
a
.
I
n
s
t
a
n
t
R
u
n
o
f
f
)
:
c
a
n
d
i
d
a
t
e
w
i
t
h
l
o
w
e
s
t
p
l
u
r
a
l
i
t
y
s
c
o
r
e
d
r
o
p
s
o
u
t
;
f
o
r
v
o
t
e
r
s
w
h
o
v
o
t
e
d
f
o
r
t
h
a
t
c
a
n
d
i
d
a
t
e
:
t
h
e
v
o
t
e
i
s
t
r
a
n
s
f
e
r
r
e
d
t
o
t
h
e
n
e
x
t
(
l
i
v
e
)
c
a
n
d
i
d
a
t
e
Repeat until only one candidate remains
J
e
a
n
-
C
h
a
r
l
e
s
d
e
B
o
r
d
a
1
7
7
0
There is something wrong with Borda!
[1785]
1743-1794
M
a
r
i
e
J
e
a
n
A
n
t
o
i
n
e
N
i
c
o
l
a
s
d
e
C
a
r
i
t
a
t
,
m
a
r
q
u
i
s
d
e
C
o
n
d
o
r
c
e
t
•
A
c
a
n
d
i
d
a
t
e
i
s
t
h
e
C
o
n
d
o
r
c
e
t
w
i
n
n
e
r
i
f
i
t
w
i
n
s
a
l
l
o
f
i
t
s
p
a
i
r
w
i
s
e
e
l
e
c
t
i
o
n
s
•
Does not always exist…
C
o
n
d
o
r
c
e
t
p
a
r
a
d
o
x
:
t
h
e
r
e
c
a
n
b
e
c
y
c
l
e
s
–
Three voters and candidates:
a > b > c
,
b > c > a
,
c > a > b
–
a
defeats
b
,
b
defeats
c
,
c
defeats
a
Many rules do not satisfy the criterion
•
F
o
r
i
n
s
t
a
n
c
e
:
p
l
u
r
a
l
i
t
y
:
–
b > a > c > d
–
c > a > b > d
–
d > a > b > c
•
a
is the Condorcet winner, but not the plurality winner
•
Candidates
a
and
b:
•
Comparing how often
a
is ranked above
b
, to how
often
b
is ranked above
a
Also
Borda
:
a > b > c > d > e
a > b > c > d > e
c > b > d > e > a
•
K
e
m
e
n
y
:
–
Consider all pairwise comparisons.
–
Graph representation: edge from winner to loser
–
Create an overall ranking of the candidates that has as few
disagreements as possible with the pairwise comparisons.
•
Delete as few edges as possible so as to make the directed comparison graph
acyclic
•
A
p
p
r
o
v
a
l
[
n
o
t
a
r
a
n
k
i
n
g
-
b
a
s
e
d
r
u
l
e
]
:
e
v
e
r
y
v
o
t
e
r
l
a
b
e
l
s
e
a
c
h
c
a
n
d
i
d
a
t
e
a
s
a
p
p
r
o
v
e
d
o
r
d
i
s
a
p
p
r
o
v
e
d
.
C
a
n
d
i
d
a
t
e
w
i
t
h
t
h
e
m
o
s
t
a
p
p
r
o
v
a
l
s
w
i
n
s
How do we choose one rule from all of these rules?
•
What is the “perfect” rule?
•
We list some natural
criteria
•
Honor societies
•
General Secretary of the UN
Skip to the 20
th
Centrury
Kenneth Arrow, an economist. In his
PhD thesis, 1950, he:
◦
Listed desirable properties of
voting scheme
◦
Showed that no rule can satisfy all
of them.
Properties
Unanimity
Independence of irrelevant
alternatives
Not Dictatorial
Kenneth Arrow
1921-
•
Independence of irrelevant alternatives: 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 property
–
Should they?
a
b
a
b
a
b
a
b
a
b
a
b
¼
E
v
e
r
y
S
o
c
i
a
l
W
e
l
f
a
r
e
F
u
n
c
t
i
o
n
W
o
v
e
r
a
s
e
t
A
o
f
a
t
l
e
a
s
t
3
c
a
n
d
i
d
a
t
e
s
:
If it satisfies
–
Independence of irrelevant alternatives
–
Pareto efficiency:
If for all
i
a
Á
i
b
then
a
Á
b
where
W(
Á
1
,
Á
2
,… ,
Á
n
) =
Á
T
h
e
n
i
t
i
s
d
i
c
t
a
t
o
r
i
a
l
:
f
o
r
a
l
l
s
u
c
h
W
t
h
e
r
e
e
x
i
s
t
s
a
n
i
n
d
e
x
i
s
u
c
h
t
h
a
t
f
o
r
a
l
l
Á
1
,
Á
2
,
…
,
Á
n
2
L
,
W
(
Á
1
,
Á
2
,
…
,
Á
n
)
=
Á
i
Claim
: Let W be as above, and let
Á
1
,
Á
2
,…,
Á
n
and
Á
’
1
,
Á
’
2
,…,
Á
’
n
be two profiles
s.t.
◦
Á
=W(
Á
1
,
Á
2
,…,
Á
n
)
and
Á
’=W(
Á
’
1
,
Á
’
2
,…,
Á
’
n
)
◦
and where for all
i
a
Á
i
b
c
Á
’
i
d
Then
a
Á
b
c
Á
’
d
Proof
: suppose
a
Á
b
and
c
b
Create a single preference
i
from
Á
i
and
Á’
i
:
where
c
is just below
a
and
d
just above
b.
Let
Á
=W(
Á
1
,
Á
2
,…,
Á
n
)
We must have:
(i)
a
Á
b
(ii)
c
Á
a
and
(iii)
b
Á
d
And therefore
c
Á
d
and
c
Á
’
d
Change must happen
at some
profile
i*
•
Where
voter
i*
changed his
opinion
Claim
: For arbitrary
a,b
2
A
consider profiles
a
Á
b
b
Á
a
C
l
a
i
m
:
t
h
i
s
i
*
i
s
t
h
e
d
i
c
t
a
t
o
r
!
H
y
b
r
i
d
a
r
g
u
m
e
n
t
V
o
t
e
r
s
1
2
n
P
r
o
f
i
l
e
s
0
1
2
…
n
Claim
: for any
Á
1
,
Á
2
,…,
Á
n
and
Á
=W(
Á
1
,
Á
2
,…,
Á
n
)
and
c,d
2
A
. If
c
Á
i*
d
then
c
Á
d
.
Proof: take
e
c,
d
and
for
i<i*
move
e
to the bottom of
Á
i
for
i>i*
move
e
to the top of
Á
i
for
i*
put
e
between
c
and
d
For resulting preferences:
◦
Preferences of
e
and
c
like
a
and
b
in
profile
i*.
◦
Preferences of
e
and
d
like
a
and
b
in profile
i*-1.
c
Á
e
e
Á
d
Therefore
c
Á
d
A function f: L
n
A is called a
social choice function
◦
Aggregates voters preferences and selects a
winner
A function W: L
n
L is called a
social welfare
function
◦
Aggergates voters preference into a
common order
We’ve seen:
◦
Arrows Theorem
: Limitations on Social Welfare
functions
Next:
◦
Gibbard-Satterthwaite Theorem
: Limitations on
Incentive Compatible Social Choice functions
16
A
social choice function
f
can be
manipulated
by
voter i if for some
Á
1
,
Á
2
,…,
Á
n
and
Á
’
i
and we
have
a
=f(
Á
1
,…
Á
i
,…,
Á
n
)
and
a’
=f(
Á
1
,…,
Á
’
i
,…,
Á
n
)
but
a
Á
i
a’
voter
i
prefers
a’
over
a
and can get it by changing
her vote from her true preference
Á
i
to
Á
’
i
f
is called
incentive compatible
if it cannot be
manipulated
•
Suppose there are at least 3 alternatives
•
T
h
e
r
e
e
x
i
s
t
s
n
o
s
o
c
i
a
l
c
h
o
i
c
e
f
u
n
c
t
i
o
n
f
t
h
a
t
i
s
s
i
m
u
l
t
a
n
e
o
u
s
l
y
:
–
Onto
•
for every candidate, there are some preferences so that the
candidate alternative is chosen
–
Nondictatorial
–
Incentive compatible
Given non-manipulable, onto, non dictator social choice
function f,
Construct a Social Welfare function
W
f
(total order)
based on f.
W
f
(
Á
1
,…,
Á
n
)
=
Á
where
a
Á
b
iff
f(
Á
1
{a,b},…,
Á
n
{a,b})
=b
Keep everything in order but
move
a and b
to top
That is “well formed”
◦
Antisymmetry
◦
Transitivity
◦
Unanimity
◦
IIA
◦
Non-dictatorship
Contradiction to Arrow
20
C
l
a
i
m
:
f
o
r
a
l
l
Á
1
,
…
,
Á
n
a
n
d
a
n
y
S
½
A
w
e
h
a
v
e
f
(
Á
1
S
,
…
,
Á
n
S
,
)
2
S
Take
a
2
S
. There is some
Á
’
1
,
Á
’
2
,…,
Á
’
n
where
f(
Á
’
1
,
Á
’
2
,…,
Á
’
n
)=a.
Sequentially change
Á
’
i
to
Á
S
i
•
At no point does
f
output
b
2
S
.
•
Due to the non-manipulation
Keep everything in order but move
elements of S
to top
Antisymmetry: implied by claim for
S={a,b}
Transitivity: Suppose we obtained contradicting
cycle
a
Á
b
Á
c
Á
a
take
S={a,b,c} and suppose
a = f(
Á
1
S
,…,
Á
n
S
)
Sequentially change
Á
S
i
to
Á
i
{a,b}Non manipulability implies that
f(
Á
1
{a,b},…,
Á
n
{a,b})
=a
and
b
Á
a
.
Unanimity: if for all
i
b
Á
i
a
then
(
Á
i
{a,b})
{a} =
Á
i
{a,b} and
f(
Á
1
{a,b},…,
Á
n
{a,b})
=a
Independence of irrelevant alternatives
:
◦
Again, non-manulpulation,
◦
if there are two profiles
Á
1
,
Á
2
,…,
Á
n
and
Á
’
1
,
Á
’
2
,…,
Á
’
n
where for all
i
b
Á
i
a
iff
b
Á
’
i
a,
then
f(
Á
1
{a,b},…,
Á
n
{a,b}) =
f(
Á
’
1
{a,b},…,
Á
’
n
{a,b})
by sequentially flipping from
Á
i
{a,b} to
Á
’
i
{a,b}
Non dictator:
preserved
24
Set of alternatives A
◦
Who wins the auction
◦
Which path is chosen
◦
Who is matched to whom
Each participant: a type function t
i
:A
R
◦
Note: real value, not only
order
Participant = agent/bidder/player/etc
.
We want to implement a social choice function
◦
(a function of the agent types)
◦
Need to know agents’ types
◦
Why should they reveal them?
Idea: Compute alternative (a in A) and
payment vector p
Utility to agent i of alternative a with
payment p
i
is t
i
(a)-p
i
Q
u
a
s
i
l
i
n
e
a
r
p
r
e
f
e
r
e
n
c
e
s
A social planner wants to choose an alternative
according to players’ types:
f
: T
1
× ... × T
n
→
A
Problem: the planner does not know the types.
Single item for sale
Each player has scalar value
z
i
– value of getting
item
If he wins item and has to pay
p
: utility
z
i
-p
If someone else wins item: utility
0
Second price auction
: Winner is the one with the
highest declared value
z
i
. P
ays the second
highest bid
p*=max
j
i
z
j
Theorem (Vickrey): for any every
z
1
, z
2
,…,z
n
and every
z
i
’.
Let
u
i
be i’s utility if he bids
z
i
and
u’
i
if he bids
z
i
’.
Then
u
i
¸
u’
i.
.
A
direct revelation mechanism
is a
social choice
function
f: T
1
T
2
…
T
n
A
and
payment
functions
p
i
: T
1
T
2
…
T
n
R
Participant i pays
p
i
(t
1
, t
2
, … t
n
)
A mechanism
(f,p
1
, p
2
,… p
n
)
is
incentive compatible in dominant strategies
if for every
t=(t
1
, t
2
, …,t
n
)
,
i
and
t
i
’
2
T
i
: if
a = f(t
i
,t
-i
)
and
a’ = f(t’
i
,t
-i
)
then
t
i
(a)-p
i
(t
i
,t
-i
)
¸
t
i
(a’)
-p
i
(t’
i
,t
-i
)
t=(t
1
, t
2
,… t
n
)
t
-
i
=(t
1
, t
2
,… t
i-1
,t
i+1
,… t
n
)
A mechanism
(f,p
1
, p
2
,… p
n
) is called
Vickrey-
Clarke-Grove (VCG)
if
f(t
1
, t
2
, … t
n
)
maximizes
i
t
i
(a)
over
A
◦
Maximizes welfare
There are functions
h
1
, h
2
,… h
n
where
h
i
: T
1
T
2
…
T
i-1
T
i+1
…
T
n
R
we have that:
p
i
(t
1
, t
2
, … t
n
) =
h
i
(t
-i
)
-
j i
t
j
(f(t
1
, t
2
,… t
n
))
t=(t
1
, t
2
,… t
n
)
t
-
i
=(t
1
, t
2
,… t
i-1
,t
i+1
,… t
n
)
D
o
e
s
n
o
t
d
e
p
e
n
d
o
n
t
i
Recall:
f
assigns the item to one participant and
t
i
(j) = 0
if
j
i
and
t
i
(i)=z
i
f(t
1
, t
2
, … t
n
) = i s.t. z
i
=max
j
(z
1
, z
2
,… z
n
)
h
i
(t
-i
) = max
j
(z
1
, z
2
, … z
i-1
, z
i+1
,…, z
n
)
p
i
(t) = h
i
(v
-i
) -
j i
t
j
(f(t
1
, t
2
,… t
n
))
If
i
is the winner
p
i
(t) = h
i
(t
-i
) = max
j
i
z
j
and for
j
i
p
j
(t)= z
i
– z
i
= 0
A={i wins|I 2
I}
Theorem
: Every VCG Mechanism
(f,p
1
, p
2
,… p
n
)
is
incentive compatible
Proof
:
Fix
i,
t
-i
,
t
i
and
t’
i
. Let
a=f(t
i
,t
-i
)
and
a’=f(t’
i
,t
-i
).
Have to show
t
i
(a)-p
i
(t
i
,t
-i
)
¸
t
i
(a’)
-p
i
(t’
i
,t
-i
)
Utility of
i
when declaring
t
i
:
t
i
(a) +
j i
t
j
(a) - h
i
(t
-i
)
Utility of
i
when declaring
t’
i
:
t
i
(a’)+
j i
t
j
(a’)- h
i
(t
-i
)
Since
a
maximizes
social welfare
t
i
(a) +
j i
t
j
(a)
¸
t
i
(a’) +
j i
t
j
(a’)
What is the “right”:
h
?
Individually rational
: participants always get non
negative utility
t
i
(f(t
1
, t
2
,… t
n
)) - p
i
(t
1
, t
2
,… t
n
)
¸
0
No positive transfers
: no participant is ever paid
money
p
i
(t
1
, t
2
,… t
n
)
¸
0
Clark Pivot rule:
Choosing
h
i
(
t
-i
) = max
b
2
A
j i
t
j
(b)
Payment of
i
when
a=f(t
1
, t
2
,…, t
n
):
p
i
(t
1
, t
2
,… t
n
) =
max
b
2
A
j i
t
j
(b)
-
j i
t
j
(a)
i
pays an amount corresponding to the total “
damage
” he
causes other players:
difference in social welfare caused
by his participation
m
a
x
i
m
i
z
e
s
i
t
i
(
a
)
o
v
e
r
A
Theorem
: Every VCG Mechanism with Clarke pivot
payments makes no
positive Payments.
If
t
i
(a)
¸
0
then it is
Individually rational
Proof
:
Let
a=f(t
1
, t
2
,… t
n
)
maximize
social welfare
Let
b
2
A
maximize
j
i
t
j
(b)
Utility of
i
:
t
i
(a) +
j
i
t
j
(a) -
j
i
t
j
(b)
¸
j
t
j
(a) -
j
t
j
(b)
¸
0
Payment of
i
:
j
i
t
j
(b) -
j
i
t
j
(a)
¸
0
from choice
of
b
Second Price auction:
h
i
(
t
-i
) = max
j
(w
1
, w
2
,…, w
i-1
, w
i+1
,…, w
n
)
= max
b
2
A
j i
t
j
(b)
Multiunit auction
: if
k
identical items are to be sold
to
k
individuals.
A={S wins |S ½
I, |S|=k}
and
v
i
(S) = 0
if
i
2
S
and
v
i
(i)=w
i
if
i
2
S
Allocate units to top
k
bidders. They pay the
k+1
st
price
Claim
: this is
max
S’
½
I\{i} |S’| =k
j i
v
j
(S’)-
j i
v
j
(S)
Want to build a bridge:
◦
Cost is
C
(if built) (One more player – the “state”)
◦
Value to each individual
v
i
◦
Want to built iff
i
v
j
¸
C
Player with
v
j
¸
0 pays
only if pivotal
j i
v
j
< C
but
j
v
j
¸
C
in which case pays
p
j
= C-
j i
v
j
In general:
i
p
j
< C
Payments do not cover project cost’s
Subsidy necessary!
A={build, not build}Equality only when
i
v
j
= C
Set
A
of alternatives: all
s-t
paths
A Directed graph
G=(V,E)
where each edge
e
is
“owned” by a different player and has cost
c
e
.
Want to construct a
path
from source
s
to
destination
t
.
How do we solicit the real cost
c
e
?
◦
Set of alternatives: all paths from
s
to
t
◦
Player
e
has cost:
0
if
e
not
on chosen path and
–c
e
if on
◦
Maximizing social welfare
: finding shortest
s-t
path
:
min
paths
e
2
path
c
e
A VCG mechanism pays 0 to those not on path
p
:
pay
each
e
0
2
p
:
e
2
p’
c
e
-
e
2
p\{e0
}
c
e
where
p’
is shortest path
without
e
o
If
e
0
would not have woken up in the morning, what would other
edges earn? If he does wake up, what would other edges earn?
•
R
e
q
u
i
r
e
s
p
a
y
m
e
n
t
s
&
q
u
a
s
i
l
i
n
e
a
r
u
t
i
l
i
t
y
f
u
n
c
t
i
o
n
s
•
In general money needs to flow away from the system
–
Strong budget balance
= payments sum to
0
–
Impossible in general
[Green & Laffont 77]
•
Vulnerable to
collusions
•
Maximizes sum of players’ valuations (social welfare)
–
(not counting payments, but does include “COST” of alternative)
But: sometimes
[usually, often??]
the mechanism is not
interested in maximizing social welfare:
–
E
.
g
.
t
h
e
c
e
n
t
e
r
m
a
y
w
a
n
t
t
o
m
a
x
i
m
i
z
e
r
e
v
e
n
u
e
–
M
i
n
i
m
i
z
e
t
i
m
e
–
M
a
x
i
m
i
z
e
f
a
i
r
n
e
s
s
–
E
t
c
.
,
E
t
c
.
40
There is a distribution
D
i
on the
types
T
i
of
Player i
It is known to everyone
The
actual type of agent i
,
t
i
2
D
i
T
i
is the
private
information
i
knows
A profile of strategis
s
i
is a
Bayes Nash
Equilibrium if for
i
all
t
i
and all
t’
i
E
d
-i
[u
i
(t
i
, s
i
(t
i
), s
-i
(t
-i
) )]
¸
E
d
-i
[u
i
(t’
i
, s
-i
(t
-i
)) ]
First price auction for a single item with two
players.
Private values (types)
t
1
and
t
2
in
T
1
=T
2
=[0,1]
Does not make sense to bid true value – utility
0
.
There are distributions
D
1
and
D
2
Looking for
s
1
(t
1
)
and
s
2
(t
2
)
that are
best replies
to each other
Suppose both
D
1
and
D
2
are uniform.
Claim
: The strategies
s
1
(t
1
)
= t
i
/2
are in
Bayes Nash
Equilibrium
t
1
Cannot win
Win half the time
43
44
Expected Revenue:
◦
For
first price
auction:
max(T
1
/2, T
2
/2)
where
T
1
and
T
2
uniform in
[0,1]
◦
For
second price
auction
min(T
1
, T
2
)
◦
Which is better?
◦
Both are 1/3.
◦
Coincidence?
Theorem [Revenue Equivalence]
: under
very general
conditions
, every
two
Bayesian Nash
implementations of
the
same
social choice function
if for
some player
and
some type
they have the same
expected payment then
◦
All types
have the same expected payment to
the
player
◦
If all player have the same expected payment: the
expected revenues are the same
Explore the concept of social welfare in decision-making, including Arrow's Impossibility Theorem, Gibbard-Satterthwaite Theorem, VCG mechanism, and competitive prices for positions. Learn about collective decision-making for elections, restaurant choices, and more, using various voting methods like majority voting, Borda count, and Condorcet winner. Uncover challenges like Condorcet paradox and the need for fair and effective voting systems.
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
Social Welfare, Arrow + Gibbard- Satterthwaite, VCG+CPP 1
Collectively choose among outcomes Elections, Choice of Restaurant Rating of movies Who is assigned what job Goods allocation Should we build a bridge? Participants have preferences over outcomes A social choice function aggregates those preferences and picks an outcome
If there are two options and an odd number of voters Each having a clear preference between the options Natural choice: majority voting Sincere/Truthful Monotone Merging two sets where the majorities are the same preserves majority Order of queries has no significance
If we start pairing the alternatives: Order may matter Assumption: n voters give their complete ranking on set A of alternatives a10, a1, , a8 am L the set of linear orders on A (permutations). Each voter i provides i2 L Input to the aggregator/voting rule is ( 1, 2, , n ) Goals A function f: Ln A is called a social choice function Aggregates voters preferences and selects a winner A function W: Ln L is called a social welfare function Aggergates voters preference into a common order a2 a1 A
Scoring rules: defined by a vector (a1, a2, , am) Being ranked ith in a vote gives the candidate ai points Plurality: defined by (1, 0, 0, , 0) Winner is candidate that is ranked first most often Veto: is defined by (1, 1, , 1, 0) Winner is candidate that is ranked last the least often Borda: defined by (m-1, m-2, , 0) Jean-Charles de Borda 1770 Plurality with (2-candidate) runoff: top two candidates in terms of plurality score proceed to runoff. Single Transferable Vote (STV, aka. Instant Runoff): candidate with lowest plurality score drops out; for voters who voted for that candidate: the vote is transferred to the next (live) candidate Repeat until only one candidate remains
Marie Jean Antoine Nicolas de Caritat, marquis de Condorcet 1743-1794 There is something wrong with Borda! [1785]
A candidate is the Condorcet winner if it wins all of its pairwise elections Does not always exist Condorcet paradox: there can be cycles Three voters and candidates: a > b > c, b > c > a, c > a > b a defeats b, b defeats c, c defeats a Many rules do not satisfy the criterion For instance: plurality: b > a > c > d c > a > b > d d > a > b > c a is the Condorcet winner, but not the plurality winner Candidates a and b: Comparing how often a is ranked above b, to how often b is ranked above a Also Borda: a > b > c > d > e a > b > c > d > e c > b > d > e > a
Kemeny: Consider all pairwise comparisons. Graph representation: edge from winner to loser Create an overall ranking of the candidates that has as few disagreements as possible with the pairwise comparisons. Delete as few edges as possible so as to make the directed comparison graph acyclic Honor societies General Secretary of the UN Approval [not a ranking-based rule]: every voter labels each candidate as approved or disapproved. Candidate with the most approvals wins How do we choose one rule from all of these rules? What is the perfect rule? We list some natural criteria
Skip to the 20th Centrury Kenneth Arrow, an economist. In his PhD thesis, 1950, he: Listed desirable properties of voting scheme Showed that no rule can satisfy all of them. Properties Unanimity Independence of irrelevant alternatives Not Dictatorial Kenneth Arrow 1921-
Independence of irrelevant alternatives: 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 property Should they? b a a a b a b b a a b b
Every Social Welfare FunctionW over a set A of at least 3 candidates: If it satisfies Independence of irrelevant alternatives Pareto efficiency: If for all ia i b then a b where W( 1, 2, , n ) = Then it is dictatorial : for all such W there exists an index i such that for all 1, 2, , n 2 L, W( W( 1 1, , 2 2, , , , n n ) = ) = i i
Claim: Let W be as above, and let 1, 2, , n and 1, 2, , n be two profiles s.t. =W( 1, 2, , n) and =W( 1, 2, , n) and where for all i a i b c i d Then a b c d Proof: suppose a b and c b Create a single preference i from i and i: where c is just below a and d just above b. Let =W( 1, 2, , n) We must have: (i) a b (ii) c a and (iii) b d And therefore c d and c d Why?? Why?? next slide next slide
Justification: a i b c i d suppose c b If c=b and d=a, rename alternatives then i= I If c=b and and ? ? Create a single preference i from i and i: where d is just above b. Let =W( 1, 2, , n) We must have: (i) a b (=c) (ii) and (iii) b (=c) d And therefore c d and c d
Claim: For arbitrary a,b 2 A consider profiles Voters 1 2 Hybrid argument a b a b a b a b b a b a Change must happen at some profile i* Where voter i* changed his opinion b a b a b a b a a b b a n Claim: this i* is the dictator! 0 1 2 n a b b a Profiles
Claim: for any 1,2,,n and =W(1,2,,n) and c,d 2 A. If c i* d then c d. Proof: take e c, d and for i<i* move e to the bottom of i for i>i* move e to the top of i for i* put e between c and d For resulting preferences: Preferences of e and c like a and b in profile i*. Preferences of e and d like a and b in profile i*-1. c e e d Thereforec d
A function f: Ln A is called a social choice function Aggregates voters preferences and selects a winner A function W: Ln L is called a social welfare function Aggergates voters preference into a common order We ve seen: Arrows Theorem: Limitations on Social Welfare functions Next: Gibbard-Satterthwaite Theorem: Limitations on Incentive Compatible Social Choice functions 16
A social choice function f can be manipulated by voter i if for some 1, 2, , n and i and we have a=f( 1, i, , n) and a =f( 1, , i, , n) but a i a voter i prefers a over a and can get it by changing her vote from her true preference i to i f is called incentive compatible if it cannot be manipulated
Suppose there are at least 3 alternatives There exists no social choice functionf that is simultaneously: Onto for every candidate, there are some preferences so that the candidate alternative is chosen Nondictatorial Incentive compatible
Given non-manipulable, onto, non dictator social choice function f, Construct a Social Welfare function Wf (total order) based on f. Wf( 1, , n)= where a b iff f( 1{a,b}, , n{a,b})=b Keep everything in order but move a and b to top
That is well formed Antisymmetry Transitivity Unanimity IIA Non-dictatorship Contradiction to Arrow Wf 20
Claim: for all 1,,n and any S A we have f( 1S, , nS,)2 S Keep everything in order but move elements of S to top Take a 2 S. There is some 1, 2, , n where f( 1, 2, , n)=a. Sequentially change i to Si At no point does f output b 2 S. Due to the non-manipulation
Antisymmetry: implied by claim for S={a,b} Transitivity: Suppose we obtained contradicting cycle a b c a take S={a,b,c} and suppose a = f( 1S, , nS) Sequentially change Si to i{a,b} Non manipulability implies that f( 1{a,b}, , n{a,b}) =a and b a. Unanimity: if for all i b ia then ( i{a,b}){a} = i{a,b} andf( 1{a,b}, , n{a,b}) =a
Independence of irrelevant alternatives: Again, non-manulpulation, if there are two profiles 1, 2, , n and 1, 2, , n where for all i b ia iff b ia, then f( 1{a,b}, , n{a,b}) =f( 1{a,b}, , n{a,b}) by sequentially flipping from i{a,b} to i{a,b} Non dictator: preserved
Set of alternatives A Who wins the auction Which path is chosen Who is matched to whom Each participant: a type function ti:A R Note: real value, not only order Participant = agent/bidder/player/etc.
We want to implement a social choice function (a function of the agent types) Need to know agents types Why should they reveal them? Idea: Compute alternative (a in A) and payment vector p Utility to agent i of alternative a with payment pi is ti(a)-pi Quasi linear preferences
A social planner wants to choose an alternative according to players types: f : T1 ... Tn A Problem: the planner does not know the types.
Single item for sale Each player has scalar value zi value of getting item If he wins item and has to pay p: utility zi-p If someone else wins item: utility 0 Second price auction: Winner is the one with the highest declared value zi. Pays the second highest bid p*=maxj i zj Theorem (Vickrey): for any every z1, z2, ,zn and every zi . Let uibe i s utility if he bids zi and u i if he bids zi . Then ui u i..
A direct revelation mechanism is a social choice function f: T1 T2 Tn A and payment functions pi: T1 T2 Tn R Participant i pays pi(t1, t2, tn) t=(t1, t2, tn) t-i=(t1, t2, ti-1 ,ti+1, tn) A mechanism (f,p1, p2, pn) is incentive compatible in dominant strategies if for every t=(t1, t2, ,tn), i and ti 2 Ti: if a = f(ti,t-i) and a = f(t i,t-i) then ti(a)-pi(ti,t-i) ti(a ) -pi(t i,t-i)
A mechanism (f,p1, p2, pn ) is called Vickrey- Clarke-Grove (VCG) if f(t1, t2, tn) maximizes i ti(a) over A Maximizes welfare There are functions h1, h2, hn where hi: T1 T2 Ti-1 Ti+1 Tn R we have that: pi(t1, t2, tn) = hi(t-i) - j i tj(f(t1, t2, tn)) Does not depend on ti t=(t1, t2, tn) t-i=(t1, t2, ti-1 ,ti+1, tn)
Recall: f assigns the item to one participant and ti(j) = 0 if j i and ti(i)=zi f(t1, t2, tn) = i s.t. zi =maxj(z1, z2, zn) hi(t-i) = maxj(z1, z2, zi-1, zi+1, , zn) A={i wins|I 2 I} pi(t) = hi(v-i) - j i tj(f(t1, t2, tn)) If i is the winner pi(t) = hi(t-i) = maxj i zj and for j i pj(t)= zi zi = 0
Theorem: Every VCG Mechanism (f,p1, p2, pn) is incentive compatible Proof: Fix i, t-i, ti and t i. Let a=f(ti,t-i) and a =f(t i,t-i). Have to show ti(a)-pi(ti,t-i) ti(a ) -pi(t i,t-i) Utility of i when declaring ti: ti(a) + j i tj(a) - hi(t-i) Utility of i when declaring t i: ti(a )+ j i tj(a )- hi(t-i) Since a maximizessocial welfare ti(a) + j i tj(a) ti(a ) + j i tj(a )
What is the right: h? Individually rational: participants always get non negative utility ti(f(t1, t2, tn)) - pi(t1, t2, tn) 0 No positive transfers: no participant is ever paid money pi(t1, t2, tn) 0 Clark Pivot rule: Choosing hi(t-i) = maxb 2 A j i tj(b) Payment of i when a=f(t1, t2, , tn): pi(t1, t2, tn) = maxb 2 A j i tj(b) - j i tj(a) i pays an amount corresponding to the total damage he causes other players: difference in social welfare caused by his participation
Theorem: Every VCG Mechanism with Clarke pivot payments makes no positive Payments. If ti(a) 0 then it is Individually rational maximizes i i t ti i(a (a) ) over A A Proof: Let a=f(t1, t2, tn) maximizesocial welfare Let b 2 A maximize j i tj(b) Utility of i: ti(a) + j i tj(a) - j i tj(b) j tj(a) - j tj(b) 0 Payment of i: j i tj(b) - j i tj(a) 0 from choice of b
Second Price auction: hi(t-i) = maxj(w1, w2, , wi-1, wi+1, , wn) = maxb 2 A j i tj(b) Multiunit auction: if k identical items are to be sold to k individuals. A={S wins |S I, |S|=k} and vi(S) = 0 if i2S and vi(i)=wi if i 2 S Allocate units to top k bidders. They pay the k+1st price Claim: this is maxS I\{i} |S | =k j i vj(S )- j i vj(S)
Multiunit auction: if k identical items are to be sold to k individuals. A={S wins |S I, |S|=k} and vi(S) = 0 if i S and vi(i)=wi if i 2 S VCG with Clarke Pivot Payments: Allocate units to top k bidders. Each pays bid k+1. GSP: The k items are not identical (ad slots) vi(S) = 0 if i S and vi(j)=wij if i is given item j Agents bid one value i th top bidder gets slot i at price of bid i+1 Common in web advertising Claim: this is not incentive compatible
Want to build a bridge: Cost is C (if built) (One more player the state ) Value to each individual vi Want to built iff i vj C Player with vj 0 pays only if pivotal j i vj < C but j vj C in which case pays pj = C- j i vj In general: i pj < C A={build, not build} Equality only when i vj = C Payments do not cover project cost s Subsidy necessary!
A Directed graph G=(V,E) where each edge e is owned by a different player and has cost ce. Want to construct a path from source s to destination t. How do we solicit the real cost ce? Set of alternatives: all paths from s to t Player e has cost: 0 if e not on chosen path and ce if on Maximizing social welfare: finding shortest s-t path: minpaths e 2 2 path ce A VCG mechanism pays 0 to those not on path p: pay each e02 p: e 2p ce - e 2 p\{e0} ce where p is shortest path without eo Set A of alternatives: all s-t paths If e0 would not have woken up in the morning, what would other edges earn? If he does wake up, what would other edges earn?
Requires payments & quasilinear utility functions In general money needs to flow away from the system Strong budget balance = payments sum to 0 Impossible in general [Green & Laffont 77] Vulnerable to collusions Maximizes sum of players valuations (social welfare) (not counting payments, but does include COST of alternative) But: sometimes [usually, often??] the mechanism is not interested in maximizing social welfare: E.g. the center may want to maximizerevenue Minimize time Maximize fairness Etc., Etc.
There is a distribution Di on the types Ti of Player i It is known to everyone The actual type of agent i, ti2DiTi is the private information i knows A profile of strategis si is a Bayes Nash Equilibrium if for i all ti and all t i Ed-i[ui(ti, si(ti), s-i(t-i) )] Ed-i[ui(t i, s-i(t-i)) ]
First price auction for a single item with two players. Private values (types) t1 and t2 in T1=T2=[0,1] Does not make sense to bid true value utility 0. There are distributions D1 and D2 Looking for s1(t1) and s2(t2) that are best replies to each other Suppose both D1 and D2are uniform. Claim: The strategies s1(t1) = ti/2 are in Bayes Nash Equilibrium t1 Win half the time Cannot win
Auction for selling single item. Bidder i's value vi (or ti) drawn independently from distribution Fi, Zx Fi(x) = fi(x)dx: z= 0 Assume Fi strictly increasing and continuous on [0;hi]. i: [0;hi] 7 ! < ai(v) - probability of allocation item to bidder i when bidder i bids i(v), probability over choice of vj, j 6 = i. 43
Claim1: If (1;2;:::;n) is a Bayes-Nash equilibrium, (agent i bids i(vi) when vi is her value), then, for all i: 1. The probability of allocation ai(vi) is monotone increasing in vi. 2. The expected utility ui(vi) is a convex function of vi, Zvi ui(vi) = ai(z)dz: 0 3. The expected payment Zvi Zvi za0 pi(vi) = viai(vi) ai(z)dz = i(z)dz: 0 0 Claim2: If ( 1; 2;:::; n) are such that either (1) and (2) hold or (1) and (3) hold then ( 1; 2;:::; n) are a Bayes-Nash equilibria. 44
Expected Revenue: For first price auction: max(T1/2, T2/2) where T1 and T2 uniform in [0,1] For second price auction min(T1, T2) Which is better? Both are 1/3. Coincidence? Theorem [Revenue Equivalence]: under very general conditions, every twoBayesian Nash implementations of the same social choice function if for some player and some type they have the same expected payment then All types have the same expected payment to the player If all player have the same expected payment: the expected revenues are the same
