Transcript The Tradeoff between Fairness and Efficiency of Voting Rules

Efficiency in IC, IAC and
GIAC models
Pavel Dolezel, IES FSV UK, Praha 4.5.2009
Voting system
N is the set of all parties (voters). The probability of acceptance is p∈(0,1).
There are m∈ℕ different voting rules. The proposal is admitted only if all
inequalities in ① hold.
j  1,...,m
①
x=(x1,…,xn)∈Θ, where Θ is the set of all the vertices of n-dimensional unit cube
and (∀1≤i≤n, 1≤j≤s: wij≥0, 0≤qj≤1) and
j  1,...,m
②
We will call the ordered couple (q,w) given above a committee and denote the set
of all vectors (w1,…,wn) for n voters:
n
Pavel Dolezel, IES FSV UK, Prague
Pavel Dolezel,
IES FSV UK, Praha 4.5.2009
2
Voting system
In the case of IC model, all attainable values for the efficiency are given by the
set:
In the case of IAC and GIAC models, all attainable values for the efficiency are
given by the set:

n  p k 1  p
n k

j : j  0,,2n ; k  0,, n
Pavel Dolezel, IES FSV UK, Prague
Pavel Dolezel,
IES FSV UK, Praha 4.5.2009
3
IC model
Guildbauld (1952)
binary issue votes („yes“ or „no“)
independent voters
probability of acceptance p=1/2
efficiency:
Pavel Dolezel, IES FSV UK, Prague
Pavel Dolezel,
IES FSV UK, Praha 4.5.2009
4
IAC model
Gehrlein and Fishburn (1976)
binary issue votes („yes“ or „no“)
independent voters
probability of acceptance p
(0,1), p ~ U(0,1)
efficiency:
Pavel Dolezel, IES FSV UK, Prague
Pavel Dolezel,
IES FSV UK, Praha 4.5.2009
5
GIAC model
Gehrlein and Fishburn (1976)
binary issue votes („yes“ or „no“)
independent voters
probability of acceptance p
(0,1), p ~ F(0,1)( )
efficiency:
Pavel Dolezel, IES FSV UK, Prague
Pavel Dolezel,
IES FSV UK, Praha 4.5.2009
6
How to compute efficiency?
•
Computing efficiency of voting system is an NP-complete problem !!!
•
Suppose n is the number of voters, i.e. it is a positive integer number.
The following algorithms can be used to compute or estimate the
efficiency:
EXACT COMPUTATION
•
Basic Recursive Algorithm (BRA)
-precise, n<20
•
Branch and Bound Recursive Algorithm (BBRA)
-precise, n<25
•
Basic Heuristic Algorithm (BHA)
-estimate, n<1000
•
Modified Heuristic Algorithm (MHA)
-estimate, any n
ESTIMATION
Pavel Dolezel, IES FSV UK, Prague
Pavel Dolezel,
IES FSV UK, Praha 4.5.2009
7
Basic Recursive Algorithm (BRA)
•
recursive algorithm simply come through all possible coalitions and counts the
winning ones
•
can be used for at most 20 voters (then it starts to be extremely time
demanding)
quota=0.7
0
1:
0
2:
3:
1
0
1
1
0
0.5
0
10
1
1
0
0.3
1
0.2
weights
Pavel Dolezel, IES FSV UK, Prague
Pavel Dolezel,
IES FSV UK, Praha 4.5.2009
8
Branch and Bound Recursive
Algorithm (BBRA)
•
recursive algorithm come through all possible coalitions and counts the winning
ones, but stops computing whenever it is already over the quota or when the
quota can not be reached
1:
quota=0.7
0
1
0
2:
3:
0
0.5
1
1
0.3
0.2
weights
Pavel Dolezel, IES FSV UK, Prague
Pavel Dolezel,
IES FSV UK, Praha 4.5.2009
9
Basic Heuristic Algorithm (BHA)
•
algorithm simulates the process of coalition formation by choosing a
random number with binomial probability distributon representing the
size of the coalition
•
can be used for significantly higher number of voters, however it is
still limited by the ability to compute binomial coefficient for high
numbers
size: 1
2
2
3
Pavel Dolezel, IES FSV UK, Prague
Pavel Dolezel,
IES FSV UK, Praha 4.5.2009
5
10
Modified Heuristic Algorithm
(MHA)
•
modified BHA
•
can be used for any number of voters because it is not limited by the
ability to compute binomial coefficient for high numbers
•
computing binomial coefficients is substituted by Fisher-Snedecor
distribution function:
Pavel Dolezel, IES FSV UK, Prague
Pavel Dolezel,
IES FSV UK, Praha 4.5.2009
11
How good is the
estimation?
Hoeffding’s inequality:
Xi=0 if the i-th simulated coalition from the set of all possible
coalitions is loosing and Xi=1 if it is winning
S=X1+…+Xn, ai=0 for any i and bi=1 for any i, t=0.01, n=50000
Pavel Dolezel, IES FSV UK, Prague
Pavel Dolezel,
IES FSV UK, Praha 4.5.2009
12
How good is the
estimation?
Probability of efficiency estimate falling
outside the interval is in case of 50 000
iterations lower than 0,0001
(e)-0,01
real efficiency (e)
(e)+0,01
Pavel Dolezel, IES FSV UK, Prague
Pavel Dolezel,
IES FSV UK, Praha 4.5.2009
13
Problem: Assume m=1 and p=1/2. How to allocate the weights to maximize the
efficiency?
Observation: For any comitee
q, w  (w1,...,wn )
the maximum of
ε
is attained
in one of the points from the set:
⑥
The cardinality of this set is:
Hypothesis: The previous observation holds for any fixed p in (0,1).
Pavel Dolezel, IES FSV UK, Prague
Pavel Dolezel,
IES FSV UK, Praha 4.5.2009
14
Definition: The set function defined by:
1)
2)
we call the quota function (where P(A) stands for the power set of A).
Observation:
If
0  k  2n ,
q>0 and
then:
Observation:
Pavel Dolezel, IES FSV UK, Prague
Pavel Dolezel,
IES FSV UK, Praha 4.5.2009
15
Observation: The efficiency as a function of probability of acceptance does
not attain niether its maximum nor minimum.
Definition: The set of n+1-tuples given as {(k0, k1, . . . , kn) , ki is the
number of winning coalitions of the size i, i=1, . . . , n, 0≤λ≤1}
we will call the set of all attainable coalition sizes for n voters on
the maxmin set and denote it Ц*n(maxmin).
Observation: The set Ц*n(maxmin) equals to the set:
where
Pavel Dolezel, IES FSV UK, Prague
Pavel Dolezel,
IES FSV UK, Praha 4.5.2009
16
For k-voters, we divide the interval (0,1) in the following way:
Denote dij = i/(k−j) for 0  i  (k − j), iN, j = 0,..., k−1 and sort
all the dij in ascending order. Whenever there are more such members of
the sorted sequence, with the same value, delete from the sequence
all of them except just one. The elements of the final sequence we denote
0 = d1 < d2 < ... < dk’ = 1, where k’ k and call them milestones. The
interval (0,1) is then divided as
(0,1) = (d1,d2)  [d2,d3) ... [dk’−1,dk’).
We denote this division: D1 = (d1,d2) ,..., Dk’−1 = [dk’−1,dk’).
Pavel Dolezel, IES FSV UK, Prague
Pavel Dolezel,
IES FSV UK, Praha 4.5.2009
17
Observation: Suppose 0<k<101, k  N is the number of voters. Let’s denote:


 min   , w : w   
mk  max   , w  : w   k
 k
k
Then the following implication holds:
m
k
1

 mk2   k1   k2  1  Di  2  Dj  i  j 
 m
 

i
 i j0  
k 
 

i 0  i 
t
t
j
  2m  k
m k
minima of efficiency function
Proof: Is based on computer simulations:
milestones
Pavel Dolezel, IES FSV UK, Prague
Pavel Dolezel,
IES FSV UK, Praha 4.5.2009
18
Observation: Let (wk) be a sequence
 of strictly positive weights. Let p is a
probability of acceptance and (Uk) is the sequence of uniformly distributed
on [0,1] independent random variables. Let
N
XN 
 w I U
k 1
k
Suppose
w
k 1
k

 p
N
w
k
k 1

k
2
    wk     k : 0  wk  W 
, then
k 1
X
N
a. s.
 p.
N 
If p is random, independent of Uk for all k and f is the density function of
p, then we get for any quota q:


q
lim P X N  q   f u du
N 
0
Pavel Dolezel, IES FSV UK, Prague
Pavel Dolezel,
IES FSV UK, Praha 4.5.2009
19
Council of EU
Application of AIC model:
Qualified majority:
1) at least 255 out of 345 points
2) at least 14 out of 27 states
3) at least 62% of EU population
weight
population
(in millions)
Germany
29
82.3
Italy
29
59.7
France
29
64.5
United Kingdom
29
61
Spain
27
45.2
Poland
27
38.1
Romania
14
22.3
The Netherlands
13
16.4
Belgium
12
10.6
Czech Republic
12
10.4
Greece
12
11.2
Hungary
12
10
Portugal
12
10.6
Austria
10
8.3
Sweden
10
9.2
Bulgaria
10
7.7
Denmark
7
5.5
Ireland
7
4.4
Lithuania
7
3.4
Slovakia
7
5.4
Finland
7
5.3
Cyprus
4
0.8
Estonia
4
1.4
Latvia
4
2.3
Luxembourg
4
0.5
Slovenia
4
2
Malta
3
0.4
State
Pavel Dolezel, IES FSV UK, Prague
Pavel Dolezel,
IES FSV UK, Praha 4.5.2009
20
Council of EU
The artifical weights rule decreases the efficiency dramatically, see the graph
below:
Pavel Dolezel, IES FSV UK, Prague
Pavel Dolezel,
IES FSV UK, Praha 4.5.2009
21
Council of EU
The GIAC model can be applied in order to incorporate some filtering of proposals.
I have tried three filters although I do not expect their cardinal relevance. Their
relevance is purely theoretical and reflects the current discussion between Dan
Felshental and Moshe Machover on one side and Swedish diplomat Axel Moberg on
the other side, who argue, that there is a strong tradition of consensus in the
EU. Filters are given as densities of probability of acceptance.
50.6%
Filter 1
59.6%
86.7%
Filter 2
Filter 3
Efficiencies are estimated through Monte Carlo simulation with 200 elections.
Pavel Dolezel, IES FSV UK, Prague
Pavel Dolezel,
IES FSV UK, Praha 4.5.2009
22
European Parliament
There are 732 deputies in the EU Parliament from 27 EU member states.
The distribution of deputies among states is in the table:
Country
Germany
France
Italy
Belgium
Netherlands
Luxembourg
Great Britain
Denmark
Ireland
Weight Members
Country
13.5%
99 Greece
9.8%
72 Spain
9.8%
72 Portugal
3.0%
22 Sweden
3.4%
25 Austria
0.8%
6 Finland
9.8%
72 Poland
1.8%
13 Czech Republic
1.6%
12 Hungary
Weight Members
Country
3.0%
22 Slovakia
6.8%
50 Slovenia
3.0%
22 Latvia
2.5%
18 Lithuania
2.3%
17 Cyprus
1.8%
13 Estonia
6.8%
50 Malta
2.7%
20 Romania
2.7%
20 Bulgaria
Weight Members
1.8%
13
1.0%
7
1.1%
8
1.6%
12
0.8%
6
0.8%
6
0.7%
5
4.5%
33
2.3%
17
The a priori efficiency of EU Parliament simple majority voting system (with
probability of acceptance 0.5) equals 0.49798815.
Pavel Dolezel, IES FSV UK, Prague
Pavel Dolezel,
IES FSV UK, Praha 4.5.2009
23
Conclusions
1) We have developed several algorithms to compute efficiency of multi-rule
voting system. Two are precise and two are heuristic based on Monte Carlo
simulations (the most sophisticated uses Snedecor-Fisher distribution).
2) We have provided basic analysis of error in the estimation of efficiency
and also made some theoretical observations, such as minimum and maximum
analysis of the efficiency as a function of quota and weights.
3) We showed three concepts of measuring the efficiency in voting system
IC, AIC and GAIC and applied it to several examples.
4) We applied the Monte Carlo simulations based heuristic algorithm to
analyze the efficiency in the Council of EU and in the European Parliament.
We showed, the European Parliament voting rule is very efficient, while the
Council of EU qualified majority is quite inefficient mainly due to the
artificial weights rule.
Pavel Dolezel, IES FSV UK, Prague
Pavel Dolezel,
IES FSV UK, Praha 4.5.2009
24
Conclusions
5) We have proposed an artificial concept of filtering of proposals, which
takes place in advance of the elections themselves. The filter can be used
to numerically estimate the real efficiencies in certain voting body (Council
of EU, European Parliament, national Parliament, etc.) and to theoretically
explain the difference between the results of IC or AIC models and the
real observations. It can also be an answer to Axel Moberg without making
the individual preferences endogenous in voting rules analysis.
Thank you.
Pavel Dolezel, IES FSV UK, Prague
Pavel Dolezel,
IES FSV UK, Praha 4.5.2009
25