實驗經濟學一：行為賽局論 Experimental Economics I: Behavioral Game Theory 第十四講：市場設計：臺灣國中會考 Lecture 14: Market Design at Taiwan 授課教師：國立臺灣大學 經濟學系 王道一教授（Joseph Tao-yi Wang ） 本課程指定教材: Colin E. Camerer, Behavioral Game Theory: Experiments in Strategic Interaction. New York: Russell Sage Foundation; New Jersey: Princeton UP, 2003. 【本著作除另有註明外，採取創用CC「姓名標示－非商業性－相同方式分享」臺灣3.0版授權釋出】

志願難填 教團：學生陷賽局困境 (2014/6/9國語日報)國教行動聯盟昨天痛批，升學制度儼然變成賭博式賽局，學生想進理想學校，竟得猜測別人的志願怎麼填，陷入「賽局理論」困境。 國教行動聯盟理事長王立昇表示，志願序納入超額比序計分，填錯會被扣分，加上第一次免試分發後，基北區約有六千個學生可能放棄錄取考特招，所以預測別人填哪些志願、會不會放棄一免，成了填寫志願的重要因素。 王立昇指出，「賽局理論」是研究遊戲中個體預測對方和己方行為，所產生的影響，並分析最佳策略。現在的十二年國教，已經讓學生面臨一樣的困擾。 12/5/2018

填志願諜對諜　國教盟驚爆：學生想輕生 國中會考成績上周四公布後，家長學生茫然不知如何選填志願。 國教行動聯盟今上午公開呼籲教育部，今年取消志願序計分，或採3-7個志願為群組，差一個群組扣1分，以免學生陷入選填志願的博弈賽局中，填志願淪為諜對諜。 Conclusion 結論

填志願諜對諜　國教盟驚爆：學生想輕生 (2014/6/7蘋果日報) 國教行動聯盟理事長王立昇表示，…教育部應公布更多資訊並延長志願表繳交時間，讓學生有更充足資訊能錄取最理想的學校。他進一步表示，學生為了上好學校，同學間已互相猜忌，打探彼此第一志願是什麼做為自己選填志願的參考，陷入博弈賽局中，解決方法只有取消志願序計分，或擴大為群組計分，降低傷害。 Conclusion 結論

制度變數多 教團憂入學如賽局 (2014/6/8) (中央社記者許秩維) 國教行動聯盟今天說，國教入學制度變數多，恐陷賽局理論，孩子得預測他人如何填志願，聯盟籲取消志願序計分。 國教行動聯盟舉行記者會，憂心國教入學制度陷入賽局理論的困境，讓學生和家長寢食難安。 國教行動聯盟理事長王立昇表示，目前國教入學制度面臨幾個問題，如志願序計分，由於不知別人如何填志願，要進入自己理想的學校就可能有很多變數，導致陷入賽局理論的困境，學生家長難以填志願。 Conclusion 結論 12/5/2018

Taiwan High School Choice History School Choice in Taiwan Old System: Gale-Shapley Deferred Acceptance New System in 2014 Exam-exempt School Choice based on: # of ABC from Joint Exam (會考) Self-reported School Choice Rankings Other factors (that all get the same score) Chinese composition: Grade 1-6 A++, A+, A, A-, etc. 12/5/2018

Taiwan School Choice: A Simplified Model How can we analyze this? Simplify to obtain a tractable model/example Implement in the lab What are key elements of the situation? What are the key results to reproduce? Next: Run lab experiments to Test the model Try alternative institutions Teach parents/policy makers 12/5/2018

Taiwan School Choice: A Simplified Model Three schools: A, B, C Three students: 1 & 2 are type a, 3 is type c Student Payoffs: School Payoffs: Actions: Self-report School Choice Rankings Assign everyone to their first choice Ties broken by student type (grade), then random Remaining students assigned to remaining schools

Taiwan School Choice: A Simplified Model This is manipulable (=not strategy-proof) Truthful Reporting of Ranking is not BR! Suppose all students truthfully report ABC Outcome: Student 1, 2 go to schools A, B (randomly) and student 3 goes to school C Schools ABC get students of type aac But: Student 3 could gain by misreporting!

Taiwan School Choice: A Simplified Model What is the Nash Equilibrium of the game? Student 3 reports BAC Student 1 & 2 report ABC with prob. p, report BAC with prob. (1 – p) Outcome: p2 : School ABC get students of type aca When both Student 1 & 2 report ABC… 1 – p2: School ABC get students of type aac 12/5/2018

Why is this a Nash Equilibrium? 3 reports BAC; 1,2 report ABC/ BAC with (p,1 – p) For Student 1 (and 2) to mix, need: 12/5/2018

Taiwan School Choice: A Simplified Model Why is this a Nash Equilibrium? Student 1 & 2 report ABC with prob. For Student 3, we need Since increasing 12/5/2018

Conclusion (for the Example) 結論 Nash Equilibrium of this 3-student game: Student 3 untruthfully reports BAC Student 1 & 2 mix between truthful & untruthful reports ABC/ BCA, (p, 1 – p) Outcome: p2 : School ABC get students of type aca When both Student 1 & 2 report ABC… 1 – p2: School ABC get students of type aac Conclusion 結論

Is Cardinal Utility Required? Possible Extensions: Is Cardinal Utility Required? Ordinal preferences is fine if exists p so that What if students have different preferences? Different Risk Attitudes? What if there are more students/schools? What if schools can also act strategically? What is a Good Alternative Mechanism? Conclusion 結論 12/5/2018

A Simple Theory of Matching (R-S, Ch.2) Gale & Shapley (1962); Roth & Sotomayor (1990) Finite Set of Students S and Schools C 1-1 Matching, Strict (Ordinal) Preferences: : Student s prefers School c to : School c prefers Student s to : is acceptable to j A matching is Conclusion 結論

A Simple Theory of Matching (R-S, Ch.2) Matching blocked by individual if Matching blocked by pair s, c if and Matching is stable if it is blocked by neither Core = Set of all stable matchings A stable matching is Pareto efficient Theorem (Gale-Shapley, R-S Theorem 2.8) Exists a stable matching in any 1-1 matching market Conclusion 結論 12/5/2018

Deferred Acceptance Algorithm Step 1: Students apply to their first choices Schools tentatively hold most preferred student and reject all others Step t (2 and above): Students rejected in Step t – 1 apply to next highest choice Schools tentatively hold most preferred student (new or held) and reject all others Stop when no more new applications Happens in finite time! Conclusion 結論 12/5/2018

DA Algorithm: Taiwan School Choice Model 3 schools: A, B, C ; 3 students: a, b, c Student Payoffs: School Payoffs: Step 1: All students apply to school A School A holds student a and rejects b, c Step 2: Students b, c apply to school B School B holds student b and rejects c Step 3: Students c applies to school C School C holds student c and terminates DA! 12/5/2018

Deferred Acceptance Algorithm Proof of Theorem (Gale-Shapley) DA gives matching where no student/school applies to/holds unacceptable schools/students Matching not blocked by any individual! If ,s was rejected by c before in DA But in DA, c rejects only if it sees better choice! Hence, Matching not blocked by any pair! Resulting Matching of DA is stable. QED Conclusion 結論

DA Algorithm: Taiwan School Choice Model What does stable mean in the field?! Roth (1984): stable ones successfully used continue to be used (unstable ones abandoned) Few complaints in Taiwan?! A student-proposing DA algorithm yields: Student-optimal stable matching (superior to all other stable matching) Proof of Theorem? See R-S Theorem 2.12 12/5/2018

DA Algorithm: Marriage Matching Male-optimal stable matching (superior to all other stable matching) Female-pessimal (inferior to all other stable matching) In contrast, A female-proposing DA leads to Female-optimal/male-pessimal stable matching Why is proposing power less important school choice? Student/School Preferences More Aligned? 12/5/2018

Rural Hospital Theorem (R-S Theorem 2.22) The same set of students/schools are left unmatched in all stable matching This means: A loser is a loser in any stable matching (魯蛇到哪裡都是魯蛇) Cannot expect any stable-matching mechanism to solve rural hospital problem (偏遠地區醫療) Proof? Let $\mu^S$ be the student-optimal stable matching and $\mu$ be an arbitrary stable matching. Since $\mu^S$ is student-optimal, all the students that are matched in $\mu$ are matched in S . Since S is college-pessimal, all the colleges that are matched in $\mu^S$ are matched in $\mu$. But the number of matched students and colleges are the same in any matching. This means that the same set of students and colleges are matched in $\mu^S$ and $\mu$. 12/5/2018

Proof of Rural Hospital Theorem Student-optimal stable matching Alternative stable matching is student-optimal: Students matched in also matched in is school-pessimal: Schools matched in also matched # of matches are the same in any match Same set of students/schools matched in Let $\mu^S$ be the student-optimal stable matching and $\mu$ be an arbitrary stable matching. Since $\mu^S$ is student-optimal, all the students that are matched in $\mu$ are matched in $\mu^S$. Since S is college-pessimal, all the colleges that are matched in $\mu^S$ are matched in $\mu$. But the number of matched students and colleges are the same in any matching. This means that the same set of students and colleges are matched in $\mu^S$ and $\mu$. 12/5/2018

Truthful Reporting and Strategy-Proofness Main problem of the new system in Taiwan: People want to misrepresent their preferences! Mechanism: Rule that yields a matching from (reported) preferences A mechanism is strategy-proof if reporting true preferences is a dominant strategy for everyone The new system in Taiwan is not strategy-proof Is DA strategy-proof? Let $\mu^S$ be the student-optimal stable matching and $\mu$ be an arbitrary stable matching. Since $\mu^S$ is student-optimal, all the students that are matched in $\mu$ are matched in S . Since S is college-pessimal, all the colleges that are matched in $\mu^S$ are matched in $\mu$. But the number of matched students and colleges are the same in any matching. This means that the same set of students and colleges are matched in $\mu^S$ and $\mu$. 12/5/2018

Truthful Reporting and Strategy-Proofness In fact, no stable mechanism is strategy-proof! (R-S Theorem 4.4) But, by Dubins and Freedman 1981, Roth 1982: Theorem (R-S Theorem 4.7): The student-proposing DA is strategy-proof for students. Why DA (old system in Taiwan) is good: Stable Students prefer it to all other stable matching Strategy-proof for students 12/5/2018

Strategy-proof  Manipulable 1-1  Many-to-one Extensions: Strategy-proof  Manipulable Degree of strategy-proofness (instead of Y/N) 1-1  Many-to-one Schools can accept up to students (quota) Existence of stable many-to-one matching market X-proposing DA  X-optimal stable matching Rural Hospital Theorem (fill same # of students) Student-proposing DA strategy-proof for students No stable mechanism strategy-proof for schools Problem for Married Couples?! Let $\mu^S$ be the student-optimal stable matching and $\mu$ be an arbitrary stable matching. Since $\mu^S$ is student-optimal, all the students that are matched in $\mu$ are matched in S . Since S is college-pessimal, all the colleges that are matched in $\mu^S$ are matched in $\mu$. But the number of matched students and colleges are the same in any matching. This means that the same set of students and colleges are matched in $\mu^S$ and $\mu$. 12/5/2018

版權聲明版權聲明 頁碼 作品 版權標示 來源/作者 1-26 2 3-4 國立臺灣大學 經濟學系 王道一 教授 國教行動聯盟昨天痛批，升學制度儼然…現在的十二年國教，已經讓學生面臨一樣的困擾。 劉偉瑩，國語日報，〈志願難教 教團：學生陷賽局困境〉，2014/6/9，引用自臺北市教育e週報 http://enews.tp.edu.tw/paper_show.aspx?EDM=EPS20140610144609J3Q 瀏覽日期：2016/2/20，依據著作權法第46、52、65條合理使用 3-4 國中會考成績上周四公布後…以免學生陷入選填志願的博弈賽局中…解決方法只有取消志願序計分，或擴大為群組計分，降低傷害。 陳威廷，蘋果日報，〈填志願諜對諜 國教盟驚爆：學生想輕生〉，2014/06/08 http://www.appledaily.com.tw/realtimenews/article/new/20140608/412340/

版權聲明版權聲明 頁碼 作品 版權標示 來源/作者 5 8-9 11 12 國教行動聯盟今天說，國教入學制度變數多，恐陷賽局理論….要進入自己理想的學校就可能有很多變數，導致陷入賽局理論的困境，學生家長難以填志願。 許秩維，中央社，〈制度變數多 教團憂入學如賽局〉，引用自中時電子報，2014/06/8 http://www.chinatimes.com/realtimenews/20140608002093-260405 瀏覽日期：2016/2/20 依據著作權法第46、52、65條合理使用 8-9 國立臺灣大學 經濟學系 王道一 教授 如需引用，請參考盧士彧，〈臺灣高中入學分析〉，臺灣大學社會科學院經濟學系碩士論文，pp.25-27. 11 12

版權聲明版權聲明 頁碼 作品 版權標示 來源/作者 14 15 16 17 國立臺灣大學 經濟學系 王道一 教授 如需引用，請參考盧士彧，〈臺灣高中入學分析〉，臺灣大學 社會科學院經濟學系碩士論文，pp.25-27. 依據著作權法第46、52、65條合理使用 15 A.E. Roth and Marilda Sotomayer, Two-Sided Matching, Cambridge UP, 1992, pp.17-20. 16 Theorem (Gale-Shapley, R-S Theorem 2.8) -Exists a stable matching in any 1-1 matching market A.E. Roth and Marilda Sotomayer, Two-Sided Matching, Cambridge UP, 1992, pp.27. 17 Step 1: Students apply to their first choices… new applications. Happens in finite time! A.E. Roth and Marilda Sotomayer, Two-Sided Matching, Cambridge UP, 1992, pp.28-30.

版權聲明版權聲明 頁碼 作品 版權標示 來源/作者 18 19 20 25 國立臺灣大學 經濟學系 王道一 教授 如需引用，請參考盧士彧，〈臺灣高中入學分析〉，臺灣大學社會科學院經濟學系碩士論文，pp.25-27. 依據著作權法第46、52、65條合理使用 19 Proof of Theorem (Gale-Shapley) DA gives matching...Resulting Matching of DA is stable. QED A.E. Roth and Marilda Sotomayer, Two-Sided Matching, Cambridge UP, 1992, pp.30-32. 20 stable ones successfully used continue to be used (unstable ones abandoned) A.E. Roth, “The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory,” Journal of Political Economy, Vol.92, No.6, (1984), pp. 995-996 and 998-999. 25 Theorem (R-S Theorem 4.7): The student-proposing DA is strategy-proof for students. A.E. Roth and Marilda Sotomayer, Two-Sided Matching, Cambridge UP, 1992, pp.90.