偏好順序均為完整排列時之熱門配對集合研究

Abstract

熱門配對問題與分配資源的現實問題高度相關， 由於其特別關注如何在資源有限的狀況下，同時考慮到配對對象的喜好， 近年來被廣泛的研究。熱門配對問題的定義如下：給定 n 個申請人， m 個工作項目，並給定每個申請人對工作項目的喜好排序， 希望找到一個配對，使得其他任何配對，都不會獲得更多申請人的青睞。 這樣的配對稱之為熱門配對。 但熱門配對未必存在，因此我們定義熱門配對集合如下： 對任何一個在熱門配對集合之外的配對，都能在熱門配對集合中 找到一個對手配對，使得喜歡集合中配對的人數不會少於喜歡集合外配對的人數。 本論文的研究均以如下特定情況為前提：m=n，且每個申請人的喜好排序都相同。 排序不容許申請人將不同的工作項目排於同一喜好順位。 我們定義了標準集合 Rn，並證明當 n 為偶數時， Rn 將會是一個熱門配對集合。 當 n 為奇數時，我們證明：倘若給定的配對 T，其所包含逆配對的數量不少於 (n-1)/2 個時， 標準集合 Rn 中必定會存在著 T 的對手配對。 作為日後研究的基礎，本篇論文亦對標準集合定義了數個輔助函數， 並導出他們的簡單式。此外，一些不同觀點的嘗試與觀察亦收錄在本論文中。

Popular matching problems have been explored in recent years, as they are highly related to realistic problems that allocate limited resources and taking requesters' preference in concern. An instance of a popular matching problem consists of n applicants, m posts, and n preference lists which rank the posts for each applicant. A Popular matching M is the one that no other matching is preferred by more applicants when comparing with M. Since popular matching might not exist, we define the popular set S, which gathers a set of matching, such that for any given matching T, there exists a rival matching S in S that S is preferred by at least as many applicants as T. Our inspection focuses on a specialized case that m=n, and all preference lists are the same, each of which ranks all posts and contains no tie. We also compose the {em regular set} Rn, and prove when n is even, Rn is a popular set. For odd n, we show that if a given matching T contains no less than (n-1)/2 negative matches, there is a rival matching against T in the regular set. For further study on the case that n is odd, we also derive auxiliary functions for the regular set, and raise some observations from several different points of view.