Multi-level social welfare modelling in MAS: Application to assignment and matching problems

Multi-level social welfare modelling in MAS: Application to assignment and matching problems

Antoine Nongaillard Sébastien Picault 

Univ. Lille, CNRS, Centrale Lille, UMR 9189 – CRIStAL (équipe SMAC) Centre de Recherche en Informatique Signal et Automatique de Lille, France

Bioepar, INRA, Oniris, Nantes

Corresponding Author Email: 
prenom.nom@univ-lille.fr
Page: 
709-734
|
DOI: 
https://doi.org/10.3166/RIA.31.709-734
Received: 
|
Accepted: 
|
Published: 
31 December 2017
| Citation
Abstract: 

Multiagent Systems (MAS) allow for empirical comparisons between social welfare metrics, but with a preservation of the privacity of invidual preferences, leading to solving protocols for assignment or matching problems. The recent multi-level MAS offer an explicit representation of intermediate viewpoints between the individual and the collective levels. We propose a multi-level welfare model to define relevant welfare metrics for each agent group. Not only matching and assignment problems are handled through the same formalism, but subtle variations can also be addressed. Finally, we outline the general principles for distributed solvers within this modeling.

Keywords: 

social choice theory, multi-level modeling, assignment and matching problems

1. Introduction
2. Positionnement et contribution
3. Modèle proposé
4. Applications
5. Lien formel avec les problèmes d’affectation et d’appariement
6. Méthode de résolution
7. Discussion
8. Conclusion, perspectives
  References

Airiau S., Endriss U. (2013). Multiagent resource allocation with sharable items. J. Autonomous Agents and Multi-Agent Systems (JAAMAS), vol. 28, no 6, p. 956–985.

Arrow K. J. (1963). Social choice and individual values. New York, Wiley. (2nd ed.)

Brito I., Meseguer P. (2005). Distributed stable matching problems. Principles and Practice of Constraint Programming, vol. 3709, p. 152–166.

Chevaleyre Y., Dunne P., Endriss U., Lang J., Lemaître M., Maudet N. et al. (2006). Issues in multiagent resource allocation. Informatica, vol. 30, p. 3–31.

Drogoul A., Amouroux E., Caillou P., Gaudou B., Grignard A., Marilleau N. et al. (2013).

GAMA: multi-level and complex environment for agent-based models and simulations. In AAMAS, p. 1361–1362.

Drogoul A., Dubreuil C. (1991). Eco-problem-solving model: Results of the N-Puzzle. In Decentralized AI III, p. 283–295. Elsevier.

Everaere P., Morge M., Picard G. (2012). Casanova : un comportement d’agent respectant la privacité pour des mariages stables et équitables. RIA, vol. 26, no 5, p. 471–494.

Ferber J., Michel F., Báez J. (2005). AGRE: Integrating environments with organizations. In E4MAS, vol. 3374, p. 48–56. Springer.

Fischer K., Schillo M., Siekmann J. (2003). Holonic multiagent systems: A foundation for the organisation of multiagent systems. In HoloMAS.

Gale D., Shapley L. (1962). College admissions and the stability of marriage. American Mathematical Monthly, vol. 69, p. 9–14.

Kellerer H., Pferschy U., Pisinger D. (2004). Knapsack problems. Springer.

Knuth D. (1971). Mariages stables. Montréal, Canada, Presses de l’Université de Montréal.

Kuhn H. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, vol. 2, p. 83–97.

Macarthur K., Stranders R., Ramchurn S., Jennings N. (2011). A distributed anytime algorithm for dynamic task allocation in multi-agent systems. In 25th AAAI conf. on artificial intelligence.

Mathieu P., Picault S., Secq Y. (2015). Design patterns for environments in multi-agent simulations. In PRIMA, vol. 9387, p. 678–686. Springer.

Maudet A., Touya G., Duchêne C., Picault S. (2014). Representation of interactions in a multi-level multi-agent model for cartography constraint solving. In PAAMS, vol. 8473, p. 183–194. Springer.

Minar N., Burkhart R., Langton C., Askenazi M. (1996). The SWARM simulation system: a toolkit for building multi-agent simulations. Working Paper no 96-06-042. Santa Fe Institute.

Morvan G., Veremme A., Dupont D. (2011). IRM4MLS: the influence reaction model for multi-level simulation. In MABS XI, vol. 6532, p. 16–27. Springer.

Netzer A., Meisels A., Zivan R. (2015). Distributed envy minimization for resource allocation. JAAMAS, vol. 30, no 2, p. 364–402.

Nongaillard A., Mathieu P. (2011). Reallocation problems in agent societies: A local mechanism to maximize social welfare. JASSS, vol. 14, no 3.

Picault S., Mathieu P. (2011). An interaction-oriented model for multi-scale simulation. In IJCAI, p. 332–337.

Rodríguez S. (2005). From analysis to design of holonic multi-agent systems: a framework, methodological guidelines and applications. Thèse de doctorat, Université de Franche- Comté.

Sen A. (1970). Collective Choice and Social Welfare. Holden-Day.

Servat D. (2000). Modélisation de dynamiques de flux par agents. application aux processus de ruissellement, infiltration, et érosion. Thèse de doctorat, Université Paris VI.

Siebert J., Ciarletta L., Chevrier V. (2010). Agents & artefacts for multiple models coordination: Objective and decentralized coordination of simulators. In ACM symposium on applied computing, p. 2024–2028.

Simonin O., Ferber J. (2000). Modeling self satisfaction and altruism to handle action selection and reactive cooperation. In SAB, p. 314–323.

Sohier C., Denis B., Lesage J.-J. (1998). Eco-problem solving for the adaptive control of production systems: the CASPER project. In INCOM.

Weerdt M., Zhang Y., Klos T. (2011). Multiagent task allocation in social networks. JAAMAS, vol. 25, no 1, p. 46–86.