南京大学：《计算理论之美》课程教学资源（课件讲稿）Social Choice Theory

Social Choice Theory Yuyi Wang ETH Zurich 0口11日1三1=至)9C

Social Choice Theory Yuyi Wang ETH Zurich

Social choice theory o Consider a group of />2 individuals must choose an alternative from a set X. We will first consider that set X is binary X={x,y} These two alternatives could represent the set of candidates competing for office,the policies to be implemented,etc. o Preferences: Every individual i's preference over x and y can be defined as a number: x;={1,0,-1} indicating that he prefers x to y,is indifferent between them, or he prefers alternative y to x,respectively. 4口，+8卡4三三，三为Q0

Social choice theory Consider a group of I  2 individuals must choose an alternative from a set X. We will Örst consider that set X is binary X = fx, yg These two alternatives could represent the set of candidates competing for o¢ ce, the policies to be implemented, etc. Preferences: Every individual iís preference over x and y can be deÖned as a number: αi indicating that he prefers or he prefers alternative y = f1, 0, ￾1g x to y, is indi§erent between them, to x, respectively

Social choice theory o We now seek to aggregate individual preferences with the use of a social welfare functional (or social welfare aggregator). o Social welfare functional: A social welfare functional(swf)is a rule F(1,2,x1）∈{1.0，-1} which,for every profile of individual preferences (c1,2,,d1）∈{1,0，-l',assigns a social preference F(a1,2,,1）∈{1,0，-1} Example: For individual preferences (@1.42,3)=(1,0,1),the swf F(1,0,1)=1,thus prefering alternative x over y. 4口11G4三1=1至)9C

Social choice theory We now seek to aggregate individual preferences with the use of a social welfare functional (or social welfare aggregator). Social welfare functional: A social welfare functional (swf) is a rule F (α1, α2, ..., αI) 2 f1, 0, ￾1g which, for every proÖle of individual preferences (α1, α2, ..., αI) 2 f1, 0, ￾1g I , assigns a social preference F (α1, α2, ..., αI) 2 f1, 0, ￾1g. Example: For individual preferences (α1, α2, α3) = (1, 0, 1), the swf F (1, 0, 1) = 1, thus prefering alternative x over y

Social choice theory Properties of swf: A swf is Paretian if it respects unanimity of strict preference: That is,if it strictly prefers alternative x when all individuals strictly prefer x.i.e..F(1.1.....1)=1, but strictly prefers alternative y when all individuals strictly prefer y,i.e.,F(-1,-1,,-1)=-1, o Note: This property is satisfied by many swf. Weighted voting and Dictatorship are two examples(let's show that). 4口，+6年4三卡4三，三习9C

Social choice theory Properties of swf: A swf is Paretian if it respects unanimity of strict preference; That is, if it strictly prefers alternative x when all individuals strictly prefer x, i.e., F (1, 1, ..., 1) = 1, but strictly prefers alternative y when all individuals strictly prefer y, i.e., F (￾1, ￾1, ..., ￾1) = ￾1, Note: This property is satisÖed by many swf. Weighted voting and Dictatorship are two examples (letís show that)

Social choice theory o Weighted voting swf: .We first add individual preferences,assigning a weight B;>0 to every individual,where(β1，β2，，f,)≠0，as follows ∑iBk;∈R. .We then apply the sign operator,which yields 1 when iBii>0,0 when iBiaj=0.and -1 when iBji0and F(-1,-1-=-1s5nceB=-A,<0

Social choice theory Weighted voting swf: We Örst add individual preferences, assigning a weight βi  0 to every individual, where (β1 , β2 , ..., βI ) 6= 0, as follows ∑i βi αi 2 R. We then apply the sign operator, which yields 1 when ∑i βi αi > 0, 0 when ∑i βi αi = 0, and ￾1 when ∑i βi αi 0; and F (￾1, ￾1, ..., ￾1) = ￾1 since ∑ i βi αi = ￾ ∑ i βi < 0

Social choice theory o Weighted voting swf: Needless to say,simple majority is a special case of weighted majority,whereby the weights satisfy B;=1 for every individual i. The vote of every individual receives the same weight. o Intuitively,if the number of individuals who prefer alternative x to y is larger than the number of individuals prefering y to x. then F(c1,2,,）=1. .This swf is Paretian,given that F(1.1.....1)=1.sincejai=N>0;and F(-1,-1,-1)=-1 since,a;=-N<0. 4口，+年4三卡4三卡三习9C

Social choice theory Weighted voting swf: Needless to say, simple majority is a special case of weighted majority, whereby the weights satisfy βi = 1 for every individual i. The vote of every individual receives the same weight. Intuitively, if the number of individuals who prefer alternative x to y is larger than the number of individuals prefering y to x, then F (α1, α2, ..., αI) = 1. This swf is Paretian, given that F (1, 1, ..., 1) = 1, since ∑ i βi αi = N > 0; and F (￾1, ￾1, ..., ￾1) = ￾1 since ∑ i βi αi = ￾N < 0

Social choice theory Dictatorial swf: The property of Paretian in swf is so lax that even Dictatorial swf satisfy it. o Let's first define a dictatorial swf: We say that a swf is dictatorial if there exists an agent h, called the dictator,such that,for any profile of individual preferences (a1,a2....), h=1 implies F(@1.a2....)=1,and h=-1 implies F(a1,a2.....)=-1, That is,the strict preference of the dictator prevails as the social preference. We can understand the dictatorial swf as a extreme case of weighted voting... where >0 for the dictator and B;=0 for all other individuals in the society ih. 4口11G1三1=1至)9C

Social choice theory Dictatorial swf: The property of Paretian in swf is so lax that even Dictatorial swf satisfy it. Letís Örst deÖne a dictatorial swf: We say that a swf is dictatorial if there exists an agent h, called the dictator, such that, for any proÖle of individual preferences (α1, α2, ..., αI), αh = 1 implies F (α1, α2, ..., αI) = 1, and αh = ￾1 implies F (α1, α2, ..., αI) = ￾1, That is, the strict preference of the dictator prevails as the social preference. We can understand the dictatorial swf as a extreme case of weighted voting... where βh > 0 for the dictator and βi = 0 for all other individuals in the society i 6= h

Social choice theory Dictatorial swf: Since weighted voting swf is Paretian,then the dictatorial swf (as a special case of weighted voting)must also be Paretian. Extra confirmation: F(1.1.....1)=1,since=n>0:and F(-1,-1,,-1)=-1 since,i=-ph<0 4口，+6年4三卡4三，三习9C

Social choice theory Dictatorial swf: Since weighted voting swf is Paretian, then the dictatorial swf (as a special case of weighted voting) must also be Paretian. Extra conÖrmation: F (1, 1, ..., 1) = 1, since ∑ i βi αi = βh > 0; and F (￾1, ￾1, ..., ￾1) = ￾1 since ∑ i βi αi = ￾βh < 0

Social choice theory o More properties of swf: Symmetry among agents (or anonymity): The swf F(a1,@2....)is symmetric among agents (or anonymous)if the names of the agents do not matter. That is,if a permutation of preferences across agents does not alter the social preference.Precisely,let π：{1,2.}→{1,2.1} be an onto function(i.e.,a function that,for every indvidual i. there is a j such that ()=i).Then,for every profile of individual preferences (1.2...),we have F(a1,2,a1）=F(al.2x0) o Example:majority voting satisfies anonymity

Social choice theory More properties of swf: Symmetry among agents (or anonymity): The swf F (α1, α2, ..., αI) is symmetric among agents (or anonymous) if the names of the agents do not matter. That is, if a permutation of preferences across agents does not alter the social preference. Precisely, let π : f1, 2, ..., I g ! f1, 2, ..., I g be an onto function (i.e., a function that, for every indvidual i, there is a j such that π(j) = i). Then, for every proÖle of individual preferences (α1, α2, ..., αI), we have F (α1, α2, ..., αI) = F  απ(1) , απ(2) , ..., απ(I)  Example: majority voting satisÖes anonymity

Social choice theory Anonymity holds in simple majority (%4,a)-(1-11) m(1)-3.red arrow 2a=111 Social preference coincides despite (2)=1,green arrow changing individual (3)=2,purple arrow ∑a=(-+11-1 identities Weighted voting does not neeessarily satisfy anonymity Using the same (a,,)and m)function as above ∑6a=月1+6(1)+月1=月+月-月 Social preference does not necessarily coincide ∑月4=月1+月(1)+月1=月+月-月 4口，+6年4三卡4三，三习9C

Social choice theory