Authors:
Eric Piette, Maxime Morge, Gauthier Picard

Venue:
Modèles Formels de l'Interaction (MFI), 2013

Topics:
Multi-agent systems, stable matching, fairness, negotiation

Links: PDF

We are interested in the well-known stable marriage problem. Recent methods promote fairness, such as Swing. However, this method may not terminate for some instances. In this paper, we propose Swing++, which detects the dilemmas causing non-termination and resolves them. Our implementation is distributed and, like Swing, promotes fairness.

This work extends previous approaches to the Stable Marriage Problem (SMP), focusing on fairness and distributed resolution. While classical algorithms such as Gale–Shapley guarantee stability, they introduce asymmetries between agents.

Swing introduced alternating roles between agents to improve fairness, but suffers from potential non-termination due to cyclic behaviours. Swing++ addresses this limitation by explicitly detecting and resolving these cycles within a multi-agent framework.

M. Morge, E. Piette, and G. Picard (2013). Swing++ : méthode multi-agents pour la résolution du problème des mariages stables. In Modèles Formels de l'Interaction (MFI).

@inproceedings{morge2013swingpp,
  author = {Morge, Maxime and Piette, Eric and Picard, Gauthier},
  title = {Swing++ : méthode multi-agents pour la résolution du problème des mariages stables},
  booktitle = {Modèles Formels de l'Interaction (MFI)},
  year = {2013}
}