Supervision : Olivier SPANJAARD

Co-supervision : WENG Paul/VIAPPIANI Paolo

Oracle-based Algorithms for Optimizing Sophisticated Decision Criteria in Sequential, Robust and Fair Decision Problems

This thesis falls within the area of algorithmic decision theory, which is at the crossroads between decision theory, operational research and artificial intelligence. In this thesis, we study several decision models to solve problems in different domains: sequential decision problems under risk, robust optimization problems, and fair multi-agent optimization problems. To solve these problems efficiently, we use master-slave algorithms which solve the problem through an incremental process. These procedures, referred to as oracle methods in the thesis, make it possible to solve problems of large size. A particular attention is given to the skew-symmetric bilinear utility model, the weighted expected utility model and their counterparts in multicriteria decision making. These models are interesting at several respects. They extend the standard models (e.g., the expected utility model) and allow to represent a broader class of preferences while retaining their good theoretical and algorithmic properties. The thesis focuses both on theoretic (e.g., complexity results) and operational (e.g., design of practically efficient solution methods) aspects of the problems raised by the use of these criteria in the domains aforementioned. 

2015-2023 Publications

• 2023
  • H. Gilbert, M. Ouaguenouni, M. Öztürk, O. Spanjaard : “Robust Ordinal Regression for Subsets Comparisons with Interactions”, (2023)
• 2022
  • H. Gilbert, M. Ouaguenouni, M. Öztürk, O. Spanjaard : “Cautious Learning of Multiattribute Preferences”, 13^th Multidisciplinary Workshop on Advances in Preference Handling, Vienna, Austria (2022)
  • A. Ravier, H. Gilbert, M. Öztürk, O. Spanjaard : “Ordinal dominance with binary interactions for subset choice: axiomatic analysis and complexity issues”, M-pref 2022: 13^th Multidisciplinary Workshop on Advances in Preference Handling, Vienna, Austria (2022)
  • H. Gilbert, M. Öztürk, A. Ravier, O. Spanjaard : “Dominance ordinale avec interactions binaires : une étude axiomatique et algorithmique”, 23^e congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Villeurbanne - Lyon, France (2022)
  • H. Gilbert, T. Portoleau, O. Spanjaard : “Beyond pairwise comparisons in social choice: A setwise Kemeny aggregation problem”, Theoretical Computer Science, vol. 904, pp. 27-47, (Elsevier) (2022)
• 2020
  • H. Gilbert, T. Portoleau, O. Spanjaard : “Beyond Pairwise Comparisons in Social Choice: A Setwise Kemeny Aggregation Problem”, Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34 (02), Proceedings of the AAAI Conference on Artificial Intelligence, New York, United States, pp. 1982-1989 (2020)
  • B. Escoffier, H. Gilbert, A. Pass‑Lanneau : “Iterative Delegations in Liquid Democracy with Restricted Preferences”, AAAI Technical Track: Game Theory and Economic Paradigms, vol. 34 (2), New-York, NY, United States, pp. 1926-1933 (2020)
• 2019
  • B. Escoffier, H. Gilbert, A. Pass‑Lanneau : “The Convergence of Iterative Delegations in Liquid Democracy in a Social Network”, Lecture Notes in Computer Science, vol. 11801, Athènes, Greece, pp. 284-297 (2019)
  • H. Gilbert, O. Spanjaard : “Optimisation de l’indice de Gini généralisé dans le problème des mariages stables : complexité et approximation”, 20^e congrès annuel de la Société française de recherche opérationnelle et d’aide à la décision, Le Havre, France (2019)
  • H. Gilbert, O. Spanjaard : “Optimizing a Generalized Gini Index in Stable Marriage Problems: NP-Hardness, Approximation and a Polynomial Time Special Case”, Algorithmica, (Springer Verlag) (2019)
• 2018
  • H. Gilbert, O. Spanjaard : “Une vision théorie des jeux de l’optimisation multi-agents équitable avec solutions randomisées”, 19^e congrès annuel de la Société française de recherche opérationnelle et d’aide à la décision, Lorient, France (2018)
• 2017
  • H. Gilbert : “Oracle-based Algorithms for Optimizing Sophisticated Decision Criteria in Sequential, Robust and Fair Decision Problems”, thesis, defence 12/11/2017, supervision Spanjaard, Olivier, co-supervision : Weng, Paul/VIAPPIANI Paolo (2017)
  • H. Gilbert : “Fair Proportional Representation Problems with Mixture Operators”, 5^th International Conference on Algorithmic Decision Theory (ADT 2017), Luxembourg, Luxembourg (2017)
  • H. Gilbert, O. Spanjaard : “A Game-Theoretic View of Randomized Fair Multi-Agent Optimization”, The 3^rd IJCAI Algorithmic Game Theory Workshop, 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 26^th International Joint Conference on Artificial Intelligence (IJCAI'17), Melbourne, Australia (2017)
  • H. Gilbert, O. Spanjaard : “Complexity of Solving Decision Trees with Skew-Symmetric Bilinear Utility”, Proceedings of UAI 2017, Sydney, Australia (2017)
  • H. Gilbert, O. Spanjaard : “A double oracle approach to minmax regret optimization problems with interval data”, European Journal of Operational Research, (Elsevier) (2017)
• 2016
  • E. Nicart, B. Zanuttini, H. Gilbert, B. Grilhères, F. Praca : “Building document treatment chains using reinforcement learning and intuitive feedback”, Proc. 11^es Journées Francophones sur la Planification, la Décision et l'Apprentissage pour la conduite de systèmes (JFPDA~2016), Grenoble, France (2016)
  • H. Gilbert, B. Zanuttini, P. Viappiani, P. Weng, E. Nicart : “Model-Free Reinforcement Learning with Skew-Symmetric Bilinear Utilities”, Proc. 32^nd Conference on Uncertainty in Artificial Intelligence (UAI~2016), New York City, United States (2016)
  • H. Gilbert, O. Spanjaard : “Une nouvelle borne pour les problèmes d’optimisation combinatoire robuste avec des coûts sous forme d’intervalles”, 17^e congrès annuel de la Société française de recherche opérationnelle et d’aide à la décision (ROADEF), Compiègne, France (2016)
  • E. Nicart, B. Zanuttini, H. Gilbert, B. Grilhères, F. Praca : “Building Document Treatment Chains Using Reinforcement Learning and Intuitive Feedback”, Tools with Artificial Intelligence (ICTAI), 2016 IEEE 28^th International Conference on, San Jose, United States, pp. 635-639, (IEEE Computer Society) (2016)
• 2015
  • H. Gilbert, O. Spanjaard, P. Viappiani, P. Weng : “Reducing the Number of Queries in Interactive Value Iteration”, 4^th International Conference on Algorithmic Decision Theory (ADT 2015), vol. 9346, Lecture Notes in Computer Science, Lexington, KY, United States, pp. 139-152, (Springer) (2015)
  • H. Gilbert, O. Spanjaard, P. Viappiani, P. Weng : “Solving MDPs with Skew Symmetric Bilinear Utility Functions”, 24^th International Joint Conference on Artificial Intelligence (IJCAI-15), Buenos Aires, Argentina, pp. 1989-1995 (2015)
  • H. Gilbert, O. Spanjaard, P. Viappiani, P. Weng : “Processus décisionnels de Markov avec un tournoi valué sur les politiques”, 16^e congrès annuel de la Société française de recherche opérationnelle et d’aide à la décision (ROADEF), Marseille, France (2015)