JISE

[1] [2] [3] [4] [5]

Journal of Information Science and Engineering, Vol. 5 No. 3, pp. 275-285

The Reciprocal Stable Matching Problem and Its Properties

Ruey-Tyng Kuo and Shian-Shyong Tseng⁺
Institute of Computer Science and Information Engineering
National Chiao Tung University
Hsinchu, Taiwan 30050, Republic of China
⁺Institute of Computer and Information Science
National Chiao Tung University
Hsinchu, Taiwan 30050, Republic of China

In this paper we introduce the reciprocal stable matching problem. Some underlying structural properties of this problem are given. An upper bound for the probability that any given arbitrary instance of this problem has no complete stable matching is derived. For instance, if there are thirty-two agents involved, then that probability is less than 1.5×10^-8.

Keywords: stable matching problem, reciprocal trading, preferences, stable roommates problem, discrete mathematics

Retrieve PDF document (JISE_198903_05.pdf)