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 <;EL. Social welfare function:a function F:LL. Social choice function:a function f:L>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