熱門配對問題與分配資源的現實問題高度相關, 由於其特別關注如何在資源有限的狀況下,同時考慮到配對對象的喜好, 近年來被廣泛的研究。熱門配對問題的定義如下:給定 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.