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

Popular Sets of Matching for Instances with Uniform Permutations of Preferences

陳婕妤(Chieh-Yu Chen)

指導教授 ： 趙坤茂

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2015年)

https://doi.org/10.6342/NTU.2015.01570

摘要

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

並列關鍵字

matchings ； popular matchings ； one-sided preference lists ； bipartite graphs ； permutation

參考文獻

[9] Thomas J Schaefer. The complexity of satisfiability problems. In Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, pages 216–226. ACM, 1978.

[10] Yen-Wei Wu, Wei-Yin Lin, Hung-Lung Wang, and Kun-Mao Chao. The generalized popular condensation problem. In Algorithms and Computation, pages 606–617. Springer, 2014.

[1] Peter Gärdenfors. Match making: assignments based on bilateral preferences. Behavioral Science, 20(3):166–173, 1975.

[4] Atila Abdulkadiroğlu and Tayfun Sönmez. Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica, pages 689–701, 1998.

[5] Alvin E Roth and Andrew Postlewaite. Weak versus strong domination in a market with indivisible goods. Journal of Mathematical Economics, 4(2):131–137, 1977.