Procédure décentralisée d’affectation d’individus à des activités

Procédure décentralisée d’affectation d’individus à des activités

Maxime Morge Antoine Nongaillard  

Univ. Lille, CNRS, Centrale Lille, UMR 9189 - CRIStAL - Centre de Recherche en Informatique Signal et Automatique de Lille, F-59000 Lille, France

Corresponding Author Email: 
31 December 2018
| Citation

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

1. Introduction
2. Modélisation multi-agents du processus d’affectation
3. Affectation d’individus à des activités
4. Procédure centralisée d’appariement
5. Comportement d’agent
6. Évaluation empirique
7. Application pratique
8. Discussion
Annexe A. Programmation linéaire

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.