Consider a Public School Choice problem with five students {s1, . . . , s5} and

Question

Consider a Public School Choice problem with five students {s1, . . . , s5} and four schools {c1, . . . , c4}. Only c2 has two slots, and every other school has only one slot. All schools have the same priority list: s1 s2 s3 s4 s5. Students’ preferences are given as follows:

• P(s1), P(s2) : c1 >c2 >c3 >c4,

• P(s3) : c1 >c3 >c2 >c4,

• P(s4) : c2 >c1 >c3 >c4,

• P(s5) : c3 >c1> c2> c4.

(a) If all agents report their preferences truthfully, what is the matching produced by the Boston mechanism?

(b) Is there an agent who has an incentive to misreport her preferences (assuming other agents’ truth-telling)?

(c) What is the matching produced by the student-proposing DA algorithm?

Explanation / Answer

A

·         s1,s2,s3 will request c1

·         so c1 will choose s1 and s2,s3 are rejected

·         s4 will request c2

·         so c2 will choose s4

·         s5 will request c3

·         c3 choose s5

·         S2 will chose c2,

·         S3 will chose c3

·         C2 will take s2

·         c3 is already full so will reject s3

·         S3 will go for c2

·         Since c2 is already full with so will reject s3

·         C4 will accept s3 as it is vacant

·         C1 –s1

·         C2 —s2,s4

·         C3 – s5

·         C4 – s3

B c3 can decline s5 to get s3

when s3 will apply for c3

yes

C

Deffered Algorithm

·         s1,s2,s3 will request c1

·         so c1 will choose s1 and s2,s3 are rejected

·         s4 will request c2

·         so c2 will choose s4

·         s5 will request c3

·         c3 choose s5

·         S2 will chose c2,

·         S3 will chose c3

·         C2 will take s2

·         c3 will take s3 as he preffer s3 over s5

·         S5 will go for c1

·         Since c1 is already full with high preferred so will reject s5

·         C2 prefer s4 over s2 so will reject s5

·         So matching are as follow

·         C1 –s1

·         C2 —s2,s4

·         C3 – s3

·         C4 – s5

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.