香港中文大学：《Topics in Theoretical Computer Science》课程教学资源（PPT课件讲稿）Lecture 8 Mechanism design

CMS57opomtr cince Week 8:Social Choice and Mechanism Design Instructor:Shengyu Zhang

Instructor: Shengyu Zhang 1

Social welfare Motivating example 1. Each year we interview and recruit graduate students. A panel of 4-6 professors attend the interview and give individual rank of the 20-30 candidates. We need to aggregate these rankings to get a final ranking for the department. Question:How to aggregate rankings? 2

Social welfare ◼ Motivating example 1. ◼ Each year we interview and recruit graduate students. ◼ A panel of 4-6 professors attend the interview and give individual rank of the 20-30 candidates. ◼ We need to aggregate these rankings to get a final ranking for the department. ◼ Question: How to aggregate rankings? 2

Social choice Motivating example 2. A small number of candidates run for president. A large number of voters,each gives a ranking of the candidates Question:Who should win? 3

Social choice ◼ Motivating example 2. ◼ A small number of candidates run for president. ◼ A large number of voters, each gives a ranking of the candidates ◼ Question: Who should win? 3

Formal setting A:set of alternatives/candidates. I:set of n voters/professors. L:set of linear orders of A. A linear order is a full ranking of alternatives in A. Equivalently,a permutation of alternatives in A. aE.g.a4<a3 <a1<as a2 for A= {a1,a2,a3,a4,a5} Each voter i has a linear order <iL

Formal setting ◼ 𝐴: set of alternatives/candidates. ◼ 𝐼: set of 𝑛 voters/professors. ◼ 𝐿: set of linear orders of 𝐴. ❑ A linear order is a full ranking of alternatives in 𝐴. ❑ Equivalently, a permutation of alternatives in 𝐴. ❑ E.g. 𝑎4 ≺ 𝑎3 ≺ 𝑎1 ≺ 𝑎5 ≺ 𝑎2 for 𝐴 = {𝑎1,𝑎2, 𝑎3,𝑎4, 𝑎5} ◼ Each voter 𝑖 has a linear order ≺𝑖∈ 𝐿. 4

Formal setting A:set of alternatives/candidates. I:set of n voters/professors. L:set of linear orders of A. Each voter i has a linear order A. 5

Formal setting ◼ 𝐴: set of alternatives/candidates. ◼ 𝐼: set of 𝑛 voters/professors. ◼ 𝐿: set of linear orders of 𝐴. ◼ Each voter 𝑖 has a linear order ≺𝑖∈ 𝐿. ◼ Social welfare function: a function 𝐹: 𝐿 𝑛 → 𝐿. ◼ Social choice function: a function 𝑓: 𝐿 𝑛 → 𝐴. 5

Social welfare Let's consider social welfare functions first. What would be a good social welfare function F? 6

Social welfare ◼ Let’s consider social welfare functions first. ◼ What would be a good social welfare function 𝐹? 6

Desirable properties ■Unanimity:For every<∈L,F(<,.,<)=<. If everyone has the same preference list <then we should just use that

Desirable properties ◼ Unanimity: For every ≺∈ 𝐿, 𝐹 ≺, …, ≺ =≺. ❑ If everyone has the same preference list ≺, then we should just use that. 7

Desirable properties Independence of irrelevant alternatives:Va,b E A,H<1,…,<<i,,<n∈L,let<=F(<1,<n) and 'F(1,.,<).Then a<ib台a<b,i implies a<b台a<'b. The social preference between any a and b depends only on the voters'preferences between a and b. If each voter i changes his ranking from <to <as long as they each don't change the relative preference between a and b,then they won't change the final comparison between a and b. 8

Desirable properties ◼ Independence of irrelevant alternatives: ∀𝑎, 𝑏 ∈ 𝐴, ∀≺1 ,… , ≺𝑛, ≺1 ′ , … , ≺𝑛 ′ ∈ 𝐿, let ≺= 𝐹 ≺1 , … , ≺𝑛 and ≺ ′ = 𝐹 ≺1 ′ ,… , ≺𝑛 ′ . Then 𝑎 ≺𝑖 𝑏 ⇔ 𝑎 ≺𝑖 ′ 𝑏, ∀𝑖 implies 𝑎 ≺ 𝑏 ⇔ 𝑎 ≺ ′ 𝑏. ❑ The social preference between any 𝑎 and 𝑏 depends only on the voters’ preferences between 𝑎 and 𝑏. ❑ If each voter 𝑖 changes his ranking from ≺𝑖 to ≺𝑖 ′ , as long as they each don’t change the relative preference between 𝑎 and 𝑏, then they won’t change the final comparison between 𝑎 and 𝑏. 8

Impossibility 1 ■Arrow's theorem.IfA≥3，then only dictatorship satisfies both unanimity and independence of irrelevant alternatives. A dictatorship is a social welfare function F(<1,…,<n)=<i for some i∈[n]. It's not a voting any more. Arrow's theorem says that there is no good social welfare function. 9

Impossibility 1 ◼ Arrow’s theorem. If 𝐴 ≥ 3, then only dictatorship satisfies both unanimity and independence of irrelevant alternatives. ◼ A dictatorship is a social welfare function 𝐹 ≺1,… , ≺𝑛 =≺𝑖 for some 𝑖 ∈ [𝑛]. ❑ It’s not a voting any more. ◼ Arrow’s theorem says that there is no good social welfare function. 9

Social choice? Social choice needs to get only one winner. Easier task than social welfare. a Question:Is there a good social choice function? 10

Social choice? ◼ Social choice needs to get only one winner. ❑ Easier task than social welfare. ◼ Question: Is there a good social choice function? 10