Conception bayésienne de mécanismes et quantification de l'équité appliquées à la construction d'horaires personnalisés

Le problème de la construction des quarts est un problème classique de recherche opérationnelle. Le progrès dans leurs modélisations mathématiques et l'amélioration des puissances de calculs informatiques ont permis d'intégrer des facteurs de plus en plus complexes. L'objectif de cette thèse est d'inclure les préférences des employés à la construction d'horaires. Toutefois, au-delà des difficultés algorithmiques, cet objectif pose de nombreuses problématiques, à la fois nouvelles, générales et fondamentales. Les employés auront-ils intérêt à révéler leurs préférences de manière honnête ? Peut-on s'assurer de ne pas désavantager les employés honnêtes ? Peut-on garantir l'équité entre les employés ? Comment modéliser mathématiquement cette équité de manière convaincante ? Comment utiliser le concept d'équité pour optimiser la construction de quarts avec préférences des employés ? Nombre de ces questions élémentaires sont en lien avec la théorie des jeux. Mais les théories existantes sont insuffisantes pour adresser la complexité du contexte de la construction de quarts personnalisés. Ceci nous amènera à introduire une nouvelle perspective sur la théorie des jeux, puissante et adaptée aux calculs informatiques, qui se fonde sur un nouvel objet mathématique appelé fonction de retour. Au lieu de se focaliser sur les stratégies, la fonction de retour propose de se concentrer sur les conséquences des actions des individus sur l'issue qui leur est consacrée. Alors que ces fonctions de retour se prêtent mieux aux calculs, de façon cruciale, elles possèdent pourtant toute l'information nécessaire à l'étude des jeux. C'est pourquoi nous utiliserons alors ce nouvel objet mathématique pour une optimisation heuristique de mécanismes favorisant l'honnêteté dans un contexte simplifié de partage équitable de gâteau. Par ailleurs, nous introduirons de nouvelles définitions de l'équité fondées sur des concepts de distributions, d'échanges et de réseaux sociaux. Ces concepts viennent naturellement compléter la théorie des fonctions d'utilité de von Neumann and Morgenstern (1944), qui ne permet pas de déterminer de manière unique et sensée une quantification de la satisfaction des employés. Enfin, en dernier lieu, nous appliquerons les concepts de cette thèse à des instances de construction de quarts avec préférences des employés. Ceci fera intervenir la théorie du multicritère, ainsi qu'un lourd programme d'optimisation en nombres entiers. Toutefois, faute de temps et à cause de la complexité des calculs numériques, nous ne chercherons pas à favoriser l'honnêteté dans cette application.

Abstract

Shift scheduling is a classical problem of operations research. As mathematical modelings progress and computational capabilities improve, more complex issues are addressed. The main goal of this PhD thesis is to include employees' preferences. Yet, beside algorithmic considerations, our goal raises various new, general and fundamental questions. Will employees have incentives to reveal their preferences truthfully? Can we make sure that truthful employees are not disadvantaged? Can we guarantee the fairness of the shift allocation? How can fairness be formalized mathematically? How can we use a formal definition of fairness to optimize shift scheduling with employees' preferences? Many of these questions are related to game theory. However, game theory yields unsufficient tools to address the complexity of a shift scheduling scheme. This will lead us to introduce a new perspective on game theory, which we will argue to be both insightful and more computable. This perspective is based on a new object called the return function. Instead of concentrating on strategies, this return function drives focus on the way individuals' actions affect their outcomes. While return functions appear to be more tractable, importantly, they still contain all relevant information for the study of games. Hence, we will use this object to design a heuristical method to optimize over incentive-compatible mechanisms in a simplified fair cake-cutting problem. Furthermore, we will introduce new measures of fairness that are based on ideas of distributions, trades and social networks. These measures will rely on a natural completion of the utility theory by von Neumann and Morgenstern (1944), which does not yield a unique and sensible way of quantifying one's satisfaction. Finally, we apply concepts to difficult instances of shift scheduling with employees' preferences. This application will require a bit of multicriteria theory, as well as a large-scale integer optimization program. Unfortunately though, because of a lack of time and the hardness of algorithmic computations, we shall not aim at favoring fairness in this application.