BENABBOU Nawal
Supervision : Patrice PERNY
Procédures de décision par élicitation incrémentale de préférences en optimisation multicritère, multi-agents et dans l'incertain
This thesis work falls within the area of algorithmic decision theory which is at the junction of decision theory, operations research and artificial intelligence. Our aim is to produce algorithms allowing the fast resolution of decision problems in complex environments (multiple criteria, multi-agents, uncertainty). This work focuses on decision-theoretic elicitation and uses preferences to efficiently determine the best solutions among a set of alternatives explicitly or implicitly defined (combinatorial optimization). For combinatorial optimization problems, we propose and study a new approach consisting in interleaving incremental preference elicitation and preference-based search. The idea is to use the exploration to identify informative preference queries while exploiting answers to better focus the search on the preferred solutions. This approach leads us to propose incremental elicitation procedures for multi-objective state-space search problems, multicriteria shortest path problems, multicriteria minimum spanning tree problems, multi-agents knapsack problems and sequential decision problems under uncertainty. We provide theoretical guarantees on the correctness of the proposed algorithms and we present numerical tests showing their practical efficiency.
Defence : 05/05/2017
Jury members :
M. Jérôme LANG, Directeur de Recherche (CNRS - l'Université Paris-Dauphine) [Rapporteur]
M. Marc PIRLOT, Professeur(Faculté Polytechnique de Mons) [Rapporteur]
M. Patrice PERNY, Professeur (l'Université Pierre et Marie Curie)
Mme Clarisse DHAENENS, Professeur (Université Lille 1)
M. Nicolas MAUDET, Professeur (Université Pierre et Marie Curie)
M. Vincent MOUSSEAU, Professeur à l'École Centrale de Paris
M. Daniel VANDERPOOTEN, Professeur à l'Université Paris-Dauphine
Two past PhD students (2022 - 2024) at Sorbonne University
- 2024
- GROSS-HUMBERT Nathanaël : Étude des notions de diversité et d'envie dans le cadre de problèmes d'affectation avec groupes d'agents.
- 2022
- LEROY Cassandre : Élicitation incrémentale combinée à la recherche heuristique pour l'optimisation combinatoire multi-objectifs.
2014-2024 Publications
-
2024
- A. Khannoussi, A.‑L. Olteanu, P. MEYER, N. Benabbou : “A regret-based query selection strategy for the incremental elicitation of the criteria weights in an SRMP model”, Operational Research, vol. 24 (2), pp. 12, (Springer) (2024)
-
2023
- N. Gross‑Humbert, N. Benabbou, A. Beynier, N. Maudet : “On the Notion of Envy Among Groups of Agents in House Allocation Problems”, 26th European Conference on Artificial Intelligence, vol. 372, Frontiers in Artificial Intelligence and Applications, Krakow, Poland, pp. 924-931, (IOS Press) (2023)
-
2022
- N. Gross‑‑Humbert, N. Benabbou, A. Beynier, N. Maudet : “Sequential and Swap Mechanisms for Public Housing Allocation with Quotas and Neighbourhood-based Utilities”, ACM Transactions on Economics and Computation, vol. 10 (4), (Association for Computing Machinery (ACM)) (2022)
-
2021
- N. Benabbou, C. Leroy, Th. Lust, P. Perny : “Interactive Optimization of Submodular Functions under Matroid Constraints”, ADT 2021 - 7th International Conference on Algorithmic Decision Theory, vol. 13023, Lecture Notes in Computer Science book series, Toulouse, France, pp. 307-322, (Springer-Verlag), (ISBN: 978-3-030-87755-2) (2021)
- N. Benabbou, M. Chakraborty, A. Igarashi, Y. Zick : “Finding Fair and Efficient Allocations for Matroid Rank Valuations”, ACM Transactions on Economics and Computation, (Association for Computing Machinery (ACM)) (2021)
- N. Gross‑Humbert, N. Benabbou, A. Beynier, N. Maudet : “Sequential and Swap Mechanisms for Public Housing Allocation with Quotas and Neighbourhood-Based Utilities (Extended Abstract)”, Proceedings of the 20th International Conference on Autonomous Agentsand Multiagent Systems (AAMAS 2021), London / Online, United Kingdom (2021)
- N. Benabbou, H. Martin, P. Perny : “Min Cost Improvement and Max Gain Stability in Multicriteria Sorting Methods on Combinatorial Domains”, Journal of Multi-Criteria Decision Analysis, (Wiley) (2021)
- N. Benabbou, C. Leroy, Th. Lust, P. Perny : “Élicitation IncrĂ©mentale combinĂ©e Ă la Recherche Locale et Recherche Gloutonne pour l’Optimisation de MatroĂŻdes PondĂ©rĂ©s”, 22e congrès annuel de la sociĂ©tĂ© française de recherche opĂ©rationnelle et d'aide Ă la dĂ©cision, Mulhouse (en ligne), France (2021)
- N. Benabbou, C. Leroy, Th. Lust, P. Perny : “Combining Preference Elicitation with Local Search and Greedy Search for Matroid Optimization”, Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI'21), Virtual, France (2021)
-
2020
- A. Khannoussi, N. Benabbou, A. Olteanu, P. MEYER : “Incremental elicitation of the criteria weights of SRMP using a regret-based query selection strategy”, DA2PL 2020: From Multiple Criteria Decision Aid to Preference Learning, Trento (virtual), Italy (2020)
- N. Benabbou, M. Chakraborty, A. Igarashi, Y. Zick : “Finding Fair and Efficient Allocations When Valuations Don’t Add Up”, The 13th Symposium on Algorithmic Game Theory (SAGT 2020), vol. 12283, Lecture Notes in Computer Science, Augsburg (Virtual Conference), Germany, pp. 32-46, (Springer) (2020)
- N. Benabbou, M. Chakraborty, X.‑V. Ho, J. Sliwinski, Y. Zick : “The Price of Quota-based Diversity in Assignment Problems”, ACM Transactions on Economics and Computation, vol. 8 (3), pp. 14, (Association for Computing Machinery (ACM)) (2020)
- N. Benabbou, C. Leroy, Th. Lust : “Regret-Based Elicitation for Solving Multi-Objective Knapsack Problems with Rank-Dependent Aggregators”, The 24th European Conference on Artificial Intelligence (ECAI'20), Saint Jacques de Compostelle, Spain (2020)
- N. Benabbou, M. Chakraborty, E. Elkind, Y. Zick : “Fairness Towards Groups of Agents in the Allocation of Indivisible Items”, The Fair Allocation in Multiagent Systems, MontrĂ©al, Canada (2020)
- N. Benabbou, C. Leroy, Th. Lust : “Élicitation IncrĂ©mentale combinĂ©e Ă la Recherche Heuristique pour l’Optimisation Combinatoire Multi-objectifs”, 21e congrès annuel de la sociĂ©tĂ© française de recherche opĂ©rationnelle et d'aide Ă la dĂ©cision, Montpellier, France (2020)
- N. Benabbou, M. Chakraborty, E. Elkind, Y. Zick : “Partage Équitable de Ressources Ă des Groupes d’Agents”, ROADEF 2020 - 21e congrès annuel de la sociĂ©tĂ© Française de Recherche OpĂ©rationnelle et d’Aide Ă la DĂ©cision, Montpellier, France (2020)
- N. Benabbou, C. Leroy, Th. Lust : “An Interactive Regret-Based Genetic Algorithm for Solving Multi-Objective Combinatorial Optimization Problems”, Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI'20), New York, United States (2020)
-
2019
- N. Benabbou, Th. Lust : “An Interactive Polyhedral Approach for Multi-Objective Combinatorial Optimization with Incomplete Preference Information”, SUM 2019 - The 13th international conference on Scalable Uncertainty Management, Compiègne, France (2019)
- N. Benabbou, C. Leroy, Th. Lust, P. Perny : “Combining Local Search and Elicitation for Multi-Objective Combinatorial Optimization”, ADT 2019 - 6th International Conference on Algorithmic Decision Theory, Durham, NC, United States (2019)
- N. Benabbou, M. Chakraborty, Y. Zick : “Fairness and Diversity in Public Resource Allocation Problems”, Bulletin of the Technical Committee on Data Engineering, (IEEE Computer Society) (2019)
- N. Benabbou, M. Chakraborty, E. Elkind, Y. Zick : “Fairness Towards Groups of Agents in the Allocation of Indivisible Items”, The 28th International Joint Conference on Artificial Intelligence (IJCAI'19), MACAO, China (2019)
- N. Benabbou, Th. Lust : “A General Interactive Approach for Solving Multi-Objective Combinatorial Optimization Problems with Imprecise Preferences”, The International Symposium on Combinatorial Search (SoCS'19), Napa, United States (2019)
- N. Benabbou, M. Chakraborty, X.‑V. Ho, J. Sliwinski, Y. Zick : “Un Problème d’Affectation avec des Contraintes de DiversitĂ© : ComplexitĂ© et Prix de la DiversitĂ©”, 18 ème confĂ©rence ROADEF sociĂ©tĂ© Française de Recherche OpĂ©rationnelle et d’Aide Ă la DĂ©cision, Le Havre, France (2019)
-
2018
- N. Benabbou, M. Chakraborty, X.‑V. Ho, J. Sliwinski, Y. Zick : “Diversity Constraints in Public Housing Allocation”, 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2018), Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2018), Stockholm, Sweden (2018)
- N. Benabbou, M. Chakraborty, X.‑V. Ho, J. Sliwinski, Y. Zick : “The Assignment Problem with Diversity Constraints with an application to Ethnic Integration in Public Housing”, International Workshop on Computational Social Choice (COMSOC'18), ComSoc 2018 Proceedings, Troy, NY, United States (2018)
- N. Benabbou, P. Perny : “Interactive resolution of multiobjective combinatorial optimization problems by incremental elicitation of criteria weights”, EURO journal on decision processes, (Springer) (2018)
-
2017
- N. Benabbou : “ProcĂ©dures de dĂ©cision par Ă©licitation incrĂ©mentale de prĂ©fĂ©rences en optimisation multicritère, multi-agents et dans l’incertain”, thesis, phd defence 05/05/2017, supervision Perny, Patrice (2017)
- N. Benabbou, P. Perny : “Adaptive Elicitation of Preferences under Uncertainty in Sequential Decision Making Problems”, Proceedings of IJCAI'17, Melbourne, Australia (2017)
- H. Gilbert, N. Benabbou, P. Perny, O. Spanjaard, P. Viappiani : “Incremental Decision Making Under Risk with the Weighted Expected Utility Model”, Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI'17), Melbourne, Australia (2017)
- N. Benabbou, P. Perny, P. Viappiani : “Incremental elicitation of choquet capacities for multicriteria choice, ranking and sorting problems”, Artificial Intelligence, vol. 246, pp. 152-180, (Elsevier) (2017)
-
2016
- N. Benabbou, P. Perny, P. Viappiani : “A regret-based preference elicitation approach for sorting with multicriteria reference profiles”, From Multicriteria Decision Making to Preference Learning (DA2PL'16), Paderborn, Germany (2016)
- N. Benabbou, P. Perny : “Solving Multi-agent Knapsack Problems Using Incremental Approval Voting”, European Conference on Artificial Intelligence, La Haye, Netherlands (2016)
- N. Benabbou, P. Perny : “Incremental Approval Voting for Multi-agent Knapsack Problems”, International Workshop on Computational Social Choice (COMSOC'16), Toulouse, France (2016)
- N. Benabbou, P. Perny, P. Viappiani : “Tri multicritère intĂ©ractif basĂ© sur le concept de regret : approches avec seuils de prĂ©fĂ©rences ou profils de rĂ©fĂ©rence”, 17e congrès annuel de la sociĂ©tĂ© Française de Recherche OpĂ©rationnelle et d’Aide Ă la DĂ©cision (ROADEF 2016), Compiègne, France (2016)
- N. Benabbou, S. Di Sabatino Di Diodoro, P. Perny, P. Viappiani : “Incremental Preference Elicitation in Multi-Attribute Domains for Choice and Ranking with the Borda Count”, The tenth International Conference on Scalable Uncertainty Management, vol. 9858, Lecture Notes in Computer Science, Nice, France, pp. 81-95, (Springer) (2016)
-
2015
- N. Benabbou, P. Perny : “On Possibly Optimal Tradeoffs in Multicriteria Spanning Tree Problems”, Proceedings of the 4th International Conference on Algorithmic Decision Theory (ADT'15), vol. 9346, Lecture Notes in Computer Science, Lexington, KY, United States, pp. 322-337, (Springer International Publishing) (2015)
- N. Benabbou, P. Perny : “Combining Preference Elicitation and Search in Multiobjective State-Space Graphs”, Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI'15), Buenos Aires, Argentina, pp. 297-303 (2015)
- N. Benabbou, Ch. Gonzales, P. Perny, P. Viappiani : “Minimax Regret Approaches for Preference Elicitation with Rank-Dependent Aggregators”, EURO Journal on Decision Processes, vol. 3 (1-2), pp. 29-64 (2015)
- N. Benabbou, P. Perny : “OptimalitĂ© potentielle et Ă©licitation de poids dans les problèmes d’arbres couvrants multi-objectifs”, 16e confĂ©rence ROADEF SociĂ©tĂ© Française de Recherche OpĂ©rationnelle et Aide Ă la DĂ©cision, Marseille, France (2015)
- N. Benabbou, P. Perny : “Incremental Weight Elicitation for Multiobjective State Space Search”, Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI'15), Austin, Texas, United States, pp. 1093-1099 (2015)
- N. Benabbou : “Possible Optimality and Preference Elicitation for Decision Making”, The 4th International Conference on Algorithmic Decision Theory, vol. 9346, Lecture Notes in Computer Science, Lexington, United States, pp. 561-566 (2015)
-
2014
- N. Benabbou, P. Perny, P. Viappiani : “Incremental Elicitation of Choquet Capacities for Multicriteria Decision Making”, Proceedings of the 21st European Conference on Artificial Intelligence (ECAI'14), vol. 263, Frontiers in Artificial Intelligence and Applications, Prague, Czechia, pp. 87-92 (2014)
- N. Benabbou, P. Perny, P. Viappiani : “Apprentissage des paramètres d’une intĂ©grale de Choquet par regret minimax”, ROADEF - 15e congrès annuel de la SociĂ©tĂ© française de recherche opĂ©rationnelle et d'aide Ă la dĂ©cision, Bordeaux, France (2014)