From Marriages to Coalitions: A Soft CSP Approach
Stefano Bistarelli, Simon N. Foley, Barry O’Sullivan, Francesco Santini · Lecture notes in computer science · 2009
In this work we represent the Optimal Stable Marriage problem as a Soft Constraint Satisfaction Problem . In addition, we extend this problem from couples of individuals to coalitions of generic agents, in order to define new coalition-formation principles and stability conditions. In the coalition case, we suppose the preference value as a trust score, since trust can describe the belief of a node in the capabilities of another node, in its honesty and reliability. Semiring-based soft constraints represent a general and expressive framework that is able to deal with distinct concepts of optimality by only changing the related c-semiring structure, instead of using different ad-hoc algorithms. At last, we propose an implementation of the classical OSM problem using integer linear programming tools. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.