A Lyapunov Function Approach to Dynamic Stable Matching in A Multi-agent System - Mohd Syakirin, Ramli; Shigeru, Yamamoto (ICGST LLC, 2015)
The Stable Marriage Problem (SMP) is a combinatorial optimization problem of finding the stable partnership in a given bipartite graph. In this paper, we investigate the potential of implementing the Lyapunov theory to attain stable matching in a multi-agent system (MAS). In the system, all agents are segregated into two groups, which can be regarded as the men’s and women’s sets, respectively. A suitable local Lyapunov function is defined for each agent based on a given preference list. A global optimization is formulated by summing the local Lyapunov function of each individual agent. Two control laws (centralized and decentralized) are derived and compared so that dynamic matching between agents is obtained. Current results indicate that the matching and agents formation are stable in the sense of Lyapunov despite the existence of a few blocking pairs.