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?