Previous | [1] | [2] | [3] | [4] | [5] |

The Reciprocal Stable Matching Problem

and Its Properties

**Ruey-Tyng Kuo and Shian-Shyong Tseng ^{+}**

National Chiao Tung University

Hsinchu, Taiwan 30050, Republic of China

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.