結合有限對稱群觀點之熱門配對集合研究

Abstract

熱門配對問題是一個長年來備受關注的議題，其主要在考慮如何在有限的資源情況下加上人人平等的假設前提，將資源做有效率的分配。熱門配對問題定義如下: 給定m個申請人，n 個工作項目，以及每位申請人對工作項目之喜好順序，欲找到一個申請人與工作項目之間的配對，且保證沒有任何其他配對較此配對受到更多申請人的青睞，並稱此配對為“熱門配對”。然而，熱門配對並不總是存在，因此有許多替代的準則仍被持續討論當中, 例如: Pareto optimal, rank-maximal 等等。甚至，對於配對之“不熱門性” 亦有人提出想法。本篇論文採用熱門配對集合之定義並在以下特殊情況下做討論: m 與n 相等，每位申請人之喜好順序皆一致並且沒有一位申請人對兩個工作項目之喜好程度相同。我們另外將此問題與有限對稱群之觀念結合，提出兩者間的對應關係，並在標準集合的基礎下另外定義了廣義標準集合以及關鍵長度函數CL(n)，並證明對所有的整數n，指標為CL(n)之廣義標準集合為一熱門配對集合。最後，對於小於17 的整數，我們利用電腦精確的求出其關建長度。對於較大的整數，我們利用抽樣的方法估計之，並觀察期變化趨勢。

The popular matching problem is widely discussed in recent year. It’s mainly attributed to solve the problem about limited resources distribution in an efficient way. An instance of the popular matching problem consists of n applicants ,m posts and n preference lists which rank the posts for each applicants. The output is a matching M between applicants and posts. In addition, no other matching is preferred by more applicants when comparing with M. We call such matching M a popular matching. Since popular matching may not exist, several interesting alternative criteria have been proposed such as pareto optimal and rank-maximal. The “unopularities” of a matching were also discussed. We focus on one of the alternative criteria : popular matching set problem . A popular matching set S gathering a set of matchings assures that for any given matching M, there exist a rival matching in S. Besides, three assumptions are considered in this work : (1) m equals n. (2) all preference lists are the same. (3) Each preference list ranks all posts and contains no tie. We also combine finite symmetric group with this problem and propose a mapping between matchings and group. In addition, we also define the generalized regular set and critical length function CL(n). Finally, we prove that for all n, generalized regular set with index CL(n) is a popular matching set.