OPEN ACCESS
In this paper, we introduce an agent-based model for coalition formation which is suitable for our usecase. We propose two clearinghouses mechanisms that return sound matchings. The first aims at maximizing the global welfare of the individuals. The second ensures that all individuals are assigned as much as possible to a preferred activity. Our experiments show that the outcome of our algorithms are better than those obtained with the classical searc/optimization techniques. Moreover, their distribution speeds up their runtime.
multi-agent system, distributed problem solving, negotiation, agent behavior, coalition formation
Aziz H., Brandt F., Seedig H. G. (2013). Computing desirable partitions in additively separable hedonic games. Artificial Intelligence Journal, vol. 195, p. 316–334.
Ballester C. (2004). NP-completeness in hedonic games. Games and Economic Behavior, vol. 49, no 1, p. 1–30.
Boutilier C., Caragiannis I., Haber S., Lu T., Procaccia A. D., Sheffet O. (2015). Optimal social choice functions: A utilitarian view. Artificial Intelligence Journal, vol. 227, p. 190–213.
Brito I., Meseguer P. (2005). Distributed stable matching problems. In International conference on principles and practice of constraint programming, p. 152–166.
Darmann A., Döcker J., Dorn B., Lang J., Schneckenburger S. (2017). On simplified group activity selection. In Proceedings of 5th international conference on algorithmic decision theory, p. 255–269. Luxembourg, Luxembourg, Springer International Publishing.
Darmann A., Elkind E., Kurz S., Lang J., Schauer J., Woeginger G. (2012). Group activity selection problem. In Proceedings of the 8th international conference on internet and network economics, p. 156–169. Liverpool, UK, Springer Berlin Heidelberg.
Dreze J., Greenberg J. (1980). Hedonic coalitions: Optimality and stability. Econometrica, vol. 48, p. 987–1003.
Everaere P., Morge M., Picard G. (2012). Casanova : un comportement d’agent respectant la privacité pour des mariages stables et équitables. Revue des Sciences et Technologies de
Gale D., Shapley L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, vol. 69, p. 9–14.
Hewitt C., Bishop P., Steiger R. (1973). A universal modular ACTOR formalism for artificial intelligence. In Proc. of the 3rd international joint conference on artificial intelligence, p. 235–245. San Francisco, CA, USA, Morgan Kaufmann Publishers Inc.
Igarashi A., Peters D., Elkind E. (2017). Group activity selection on social networks. In Proc. of 31th AAAI conference on artificial intelligence, p. 565–571. San Francisco, California USA.
Manlove D. F. (2014). Algorithmics of matching under preferences. World Scientific.
Morge M., Nongaillard A. (2017). Affectation distribuée d’individus à des activités avec des préférences additivement séparables. In Journées Francophones sur les Systèmes Multi-
Moulin H. (2002). Fair division and collective welfare. The MIT Press.
Nongaillard A., Picault S. (2017). Modélisation multi-niveaux du bien-être social dans un SMA : application aux problèmes d’affectation et d’appariement. Revue des Sciences et Affectation d’individus à des activités 657 p. 709–734.
Russell S., Norvig P. (2003). Artificial intelligence: A modern approach. In, p. 94–136. Pearson
Education. (2nd edition)
Sahni S. (1974). Computationally related problems. SIAM Journal on Computing, vol. 3, no 4, p. 262–279.
Schelling T. C. (1980). The strategy of conflict. Harvard university press.
Sen A. K. (1970). Collective choice and social welfare. North-Holland.
Zaccaro S. J., Lowe C. A. (1988). Cohesiveness and performance on an additive task: Evidence for multidimensionality. The Journal of Social Psychology, vol. 128, no 4, p. 547–558.