Autonomous Mechanism for Partner Exchanging in Distributed Stable Marriage Problems

Hideki KINJO  Morikazu NAKAMURA  Kenji ONAGA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E80-A   No.6   pp.1040-1048
Publication Date: 1997/06/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section of Papers Selected from 1996 International Technical Conference on Circuits/Systems, Computers and Communications(ITC-CSCC'96))
Category: 
Keyword: 
distributed algorithm,  stable marriage problem,  matching game,  Gale-Shapley algorithm,  

Full Text: PDF(698.8KB)>>
Buy this Article




Summary: 
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.