This paper deals with a strategic issue in the stable marriage model with complete preference lists (i.e., a preference list of an agent is a permutation of all the members of the opposite sex). Given complete preference lists of n men over n women, and a marriage µ, we consider the problem for finding preference lists of n women over n men such that the men-proposing deferred acceptance algorithm (Gale-Shapley algorithm) adopted to the lists produces µ. We show a simple necessary and sufficient condition for the existence of a set of preference lists of women over men. Our condition directly gives an O(n2) time algorithm for finding a set of preference lists, if it exists.

The stable marriage problem is one of the basic problems proposed in 1962. In this paper, we consider a distributed stable marriage problem. This problem is applicable to cooperative works of autonomous robots in distributed environments. We show a Gale-Shapley based protocol to obtain stable matching and introduce autonomous mechanism for exchanging partners, called divorce process, in distributed environments. We report some interesting results of matching games by computer simulation.