JISE Vol.5 No.3 #5

[1]

[2]

[3]

[4]

[5]

Journal of Inforamtion Science and Engineering, Vol.5 No.3, pp.275-285 (July 1989)
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

Received December 20, 1988; revised October 17, 1989.
Communicated by Chin-Chen Chang.
^*This research was supported by the National Science Council under grant number NSC77-0408-E009-06.