穩定配對之研究

Abstract

穩定性配對問題由Gale和Shapley 於1962年提出，其原來目的是要找出一個穩定配對 方法，用以解決男女之間的擇偶以及大學入學招生問題。 本論文主旨在於探討穩定性配對之相關問題，所研究的問題包括： □探討穩定性配對問題之動態化，發展穩定性配對問題之不變性（invariance）理論 。 □建立穩定性配對問題之近乎可操縱性（semi-manipulability ）理論，探討作幣對 於配對結果之公平性的影響，進而提出一有效的計算機方法，用以決定作弊集團的存 在與否。 □解析穩定性配對問題單一計算機方法之效率，分別針對其最差和最佳效率，探討喜 好順序表在何種條件下會造成最差和最佳效率的發生，以及發生的機率大小。 此外，並定義一些特殊的喜好順序表，探討具有這些特殊喜好順序表之穩定性配對問 題的基本特性。 □提出一個簡化的互惠式貿易模式（reciprocal trading model），依照此一模式作 為訂定配對問題之喜好順序表的根據，並探討此一特殊配問題之相關特性。

The stable matching problem was introduced by Gale and Shapley in 1962. That is the problem of matching two sets of agents in such a manner that no two unmatched agents prefer each other to their partners. This dissertation is a study of stable matching problem. We examine the problem from four different points of view: 1. We develop the theory of invariance for the stable matching proble. A set of sufficient conditions on the alteration of preference pattern for any given stable matching instance is presented, under which the male optimal stable matching for the resulting instance is identical to the male optimal stable matching for the original. 2. We present the theory of semi-manipulability for the stable matching problem. Specifically, for any given stable matching instance, we consider that if a coalition of men has a way to get the true preference data of all men and women, how they could band together to improve almost all of the members in them without making any effect on any members of men even for those outside that coalition. Based on the derived results, we propose an efficient algorithm for determining whether or not there exists such a coalition of men and identifying one if there exists. 3. We show the necessary and sufficient conditions for both the worst-case choice and the best-case choice, which, respectively, lead to the worst-case and best-case executions of any sequential stable matching algorithm that returns the male optimal stable matching as its answer. Further,we present the probabilities of occurrences for the worst-case execution and the best-case execution. Also, we present some specific preference patterns and then give the elementary properties for stable matching instances with those specific preference patterns. 4. We raise a specific stable matching problem with preferences derived from a reciprocal trading model. We also present some underlying structural properties of that problem and then derive an upper bound for the probability that any given arbitrary instance of that problem has no complete stable matching. In addition, we give a review of previous work in the stable matching problem.