臺灣博碩士論文加值系統

本論文探討「雙方配對」之多對一「大學入學問題」的模式。多對一的典型模式是一方為組織或機構，另一方為個人的配對模式；如學校可錄取若干的學生，醫院可聘用若干的實習醫生，與公司可僱用若干的勞工等。多對一模式是配對理論多種模式中唯一應用於實際問題，且國內外至今皆有實際大規模作業在施行中，例如：(1) 國內有大學入學考試的聯合分發與高中職五專的聯合分發作業，與(2) 在美國有醫學院學生申請為醫院駐院醫生之全國性的聯合分發稱為NRMP。我們可以發現，中外二個實際的例子使多對一配對理論有其應用的價值，同時多對一配對理論也因此成為聯合分發模式的數學理論架構，可以說這是一個理論與實務配合完善的良好實例。
但因為國內外的環境背景與傳統文化的差異，在聯合分發的問題上各自有其發展的特殊性與變異性，因此也使其所遇到的問題與關注的焦點有所不同。在我國考試分發入學的計分方式是事先決定且公開的，所以同分同名次是無法避免的，在美國並無與我國相同的聯考的制度，其NRMP作業中醫院方面甄選學生採用面試決定優先順序，所以不會發生同分同名次的情況；此外，我國教育單位為了保護弱勢之特殊學生的就學機會，促使各校系增設外加錄取名額，作為保護特殊生的優惠措施，在NRMP計劃中對於學生則無保護的優惠措施。
本論文針對國內考試分發入學多對一的模式，做兩個問題的研究，(1)各學系含有「限制名額」且在同分時採用增額錄取的聯合分發。我們對於此問題，首先對在預定錄取名額與限制錄取名額做適當的詮釋，再謹慎的建構一個「限制名額」分發模式，因為若模式選擇不當則可能會造成穩定榜不存在的窘境。(2)各學系增設外加錄取名額以保護弱勢之特殊生聯合分發。我們對於此問題，將成績優異的特殊生視為一般生以原成績分發，可不受保護名額限制，適當分至一般部，對於需以加分才能錄取的特殊生分至外加部，建構一個「保護名額」分發模式，可同時保障一般生與特殊生的權益。
對此二問題，我們分別建立一個合理且具有穩定性的數學模式，進一步發展分發演算法以提供分發程式的撰寫，最後分別做理論性的探討與證明，相信此二問題因此的到完善的解決。

In this dissertation, we will concentrate two-sided matching, many-to-one matching problem. Many-to-one matching is perhaps the most typical case, where one side is institutions and the other side is individuals. For example, colleges admit many students, hospitals employ many interns, and firms hire many workers, all at the same time. Many-to-one matching model is applied to actual problems, for example, (1) Entrance Examination Matching Program (EEMP) in Taiwan. (2) National Intern Matching Program (NIMP) in the United States. (Today NIMP is called the National Resident Matching Program; NRMP). The two examples prove the profound importance applied value of Many-to-one matching model. In addition, Many-to-one matching model structures the mathematic model of practical programs. This is a good case; actual problems and theories well cooperate in the many-to-one matching model.
Due to the facts, the environmental and cultural differences between Taiwan and foreign countries, each matching program model implementation creates its own uniqueness and variations. In Taiwan, studies and problems of the EEMP program are as follows: (A) Departments have discriminating quotas and weak preferences for students that are inevitable in EEMP program, because the program procedure to place students for each department is pre-determined and open to the public. (B) Departments want to protect the educational right of under-privileged students. In the NRMP program, departments have not weak preferences for students, and departments don’t want to protect students.
This thesis mainly focuses on the many-to-one matching in the EEMP program as follows:
(1)Departments have weak preferences and discriminating quotas together with extendable quotas for students. We carefully choose and explain the model, because misleading result from improper model will fail to meet the requirements and limitations.
(2)Departments protect the educational right of under-privileged (UP) students. We construct a “mathematic model of protecting UP students” taking fixed quotas. In the model, the less-qualified UP students can be assigned to the extra parts of departments. Further, the well-qualified UP students, like the well-qualified ordinary students, can be assigned to the ordinary parts of departments.
Dealing with the two problems above, we attempt to construct a reasonable and stable mathematic model, the development of algorithm, and the exploration of theories. Finally, we hope that a fair, rational, and stable EEMP model can be continuously sustained.

第1章：緒論…………………………………………………………… 1
1.1 問題背景與研究動機 …………………………………………… 1
1.2 文獻探討 ………………………………………………………… 3
1.3 多對一的穩定配對………………………………………………… 5
1.4 研究方法與目的 ………………………………………………… 8
1.5 研究範圍與限制 ………………………………………………… 8
1.6 論文架構 ………………………………………………………… 9
第2章：限制名額分發模式…………………………………………… 11
2.1 前言 ……………………………………………………………… 11
2.2 模式 ……………………………………………………………… 14
2.3 方法 ……………………………………………………………… 18
2.3.1 分發方式 …………………………………………………… 18
2.3.2 放榜 ………………………………………………………… 22
2.3.1 驗榜 ………………………………………………………… 23
2.4 基本理論 ………………………………………………………… 23
2.5 應用 ……………………………………………………………… 32
第3章：保護名額分發模式－採外加有名額限制…………………… 34
3.1 前言 ……………………………………………………………… 34
3.2 模式 ……………………………………………………………… 35
3.3 方法 ……………………………………………………………… 37
3.3.1 分發方式 …………………………………………………… 38
3.3.2 放榜 ………………………………………………………… 42
3.3.1 驗榜 ………………………………………………………… 42
3.4 基本理論 ………………………………………………………… 43
3.5 穩定性之充要條件 ……………………………………………… 46
3.6 應用 ……………………………………………………………… 49
第4章：結論…………………………………………………………… 52
4.1 主要研究結果 …………………………………………………… 52
4.2 後續研究 ………………………………………………………… 53
4.3 結語 ……………………………………………………………… 53
參考文獻……………………………………………………………… 55

《中文部分》
[1]中華民國大學入學考試中心(1992)：〈我國大學入學制度改革建議書：大學多元入學方案〉。
[2]李子壩(1983)：〈新制大學聯考分發問題的分析〉，《數學傳播》，第七卷第三期，頁36-49。
[3]李子壩(1987)：〈大學聯招同分增額錄取模式研究〉，行政院國家科學委員會專題研究計劃成果報告，NCS 77－0208－M008－10。
[4]姚瞻海(1992)：〈穩定狀態下室友問題延伸之問題〉，政治大學統計研究所碩士論文。
[5]教育部大學入學考試委員會(1982)：〈大學入學考試之改進(草案)〉，專案研究小組研究報告。
[6]黃炳煌(1991)：〈我國大學入學制度之研究〉，中華民國大學入學考試中心。
《英文部分》
[7]Abeledo, H. and Blum, Y.,(1996). " Stable matchings and linear programming." Linear Algebra and Its Applications, Vol. 245, pp.324-333.
[8]Abeledo, H. and Rothblum, U.,(1995). " Paths to marriage stability." Discrete Applied Mathematics, Vol. 63, pp.1-12.
[9]Aldershof, B. and Carducci, O.M.,(1996). " Stable matchings with couples." Discrete Applied Mathematics, Vol. 68, pp.203-207.
[10]Alkan, A.,(1986). " Nonexistence of stable threesome matching." Mathematical Social Sciences, Vol. 16, pp.207-209.
[11]Baiou, M. and Balinski, M.,(2000). " Many-to-many matching: stable polyandrous polygamy (or polygamous polyandry)." Discrete Applied Mathematics, Vol. 101, pp.1-12.
[12]Chung, Kim-Sau.,(2000). " On the Existence of Stable Roommate Matching." Games and Economic Behavior, Vol. 33, pp.206-230.
[13]Eeckhout, J.,(2000). " On the uniqueness of stable marriage Matching." Economics Letters, Vol. 69, pp.1-8.
[14]Gale, D. and Shapley, L.,(1962). " College admissions and the stability of marriage." American Mathematical Monthly, Vol. 69,pp.9-15.
[15]Gusfield, D.,(1989). " Three fast algorithms for four problems in stable marriage." SIAM Journal on Computing, Vol. 16, pp.111-128.
[16]Gusfield, D. and Irving, R.W.,(1989). " The stable marriage problem: structure and algorithms." MIT Press, Cambridge.
[17]Lee, F.T.,(1977). " A nonnumerical assignment problem." Policy Analysis and Information Systems, Vol. 1, No. 1, pp.209-223.
[18]Manlove, D. F.,(2002). " The structure of stable marriage with indifference." Discrete Applied Mathematics, Vol. 122, pp.167-181.
[19]Martinez, R., Masso, J., Neme, A., and Oviedo, J.,(2000). " Single Agents and the Set of many-to-One Stable Matchings." Journal of Economic Theory, Vol. 91, pp.91-105.
[20]Roth, A.,(1984). " The evolution of the labor market for medical interns and residents: A case study in game theory." Journal of Political Economy, Vol. 92, pp.991-1016
[21]Roth, A.,(1991). " A natural experiment in the organization of entry-level labor markets: regional markets for new physicians and surgeons in the United Kingdom." The American Economic Review, pp.415-440.
[22]Roth, A., Rothblum, U. and Vande Vate, J.H., (1993). " Stable matchings, optimal assignments, and linear programming." Mathematics of Operational Research, Vol. 18, pp.803-828.
[23]Roth, A. and Sotomayor, M.,(1990). " Two Sided Matching: A Study in Game-Theoretic Modeling and Analysis." New York, NY: Cambridge University Press.
[24]Roth, A. and Vande Vate, J.H.,(1990). " Random paths to stability in two-sided matching." Econometrica, Vol. 58, pp.1475-1480.
[25]Rothblum, U.,(1992). " Characterization of stable matchings as extreme points of a polytope." Mathematical Programming, Vol. 54, pp.57-67.
[26]Sotomayor, M.,(1996). " A non-constructive elementary proof of the existence of stable marriages." Games and Economic Behavior, Vol. 13, pp.135-137.
[27]Sotomayor, M.,(1999). " Three remarks on the many-to-many stable matching problem." Mathematical Social Sciences, Vol. 38, pp.55-70.
[28]Tan, J.M.,(1991). " A necessary and sufficient condition for the existence of a complete stable matching." Journal of Algorithms, Vol. 12, pp.154-178.
《報章雜誌》
[29]民國85年大學入學招生簡章。
[30]江達聰(2002)：〈外加實為內含公平在哪〉，《中國時報》，七月二十九日第十五版。
[31]申震雄、楊蕙菁(1999)：〈成績優於一般生，災區考生推甄落榜〉，《聯合報》，五月二日第八版。
[32]陳英資(2002)：〈基北區高中職五專報分發烏龍 特殊生名額原應外加誤為內含占掉一般生名額 各校勢必重新分發教育部指示誤影響考生權益〉，《聯合報》，七月二十五日第一版。
[33]詹惟鈞(2002)，〈特殊考生加、分具特殊意義〉，《中國時報》，七月二十九日第十五版。
《網路資料》
[34]大學入學考試中心，http//www.ceec.edu.tw。
[35]Roth, A.,(1996). Report on the design and testing of an applicant proposing matching algorithm, and comparison with the existing NRMP algorithm [design review of the National Resident Matching Program home page]. Available at: http//www.economics.harvard. edu/~alroth/phase1.html.