Page personnelle de Sylvain Bouveret

In this talk, we deal with the problem of fairly dividing a set of goods amongst a group of agents, when those agents have preferences that are ordinal relations over alternative bundles of goods (rather than utility functions) and when our knowledge of those preferences is incomplete. The incompleteness of the preferences stems from the fact that each agent reports their preferences by means of an expression of bounded size in a compact preference representation language. Specifically, we assume that each agent only provides a ranking of individual goods (rather than of bundles). In this context, we consider the algorithmic problem of deciding whether there exists an allocation that is possibly (or necessarily) envy-free, given the incomplete preference information available, if in addition some mild economic efficiency criteria need to be satisfied. We provide simple characterisations, giving rise to simple algorithms, for some instances of the problem, and computational complexity results, establishing the intractability of the problem, for others.

Représenter et raisonner sur des préférences dans des domaines combinatoires est un problème fondamental d'une part en intelligence artificielle, et d'autre part dans l'aide à la décision. Dans ce didacticiel, nous introduirons la notion de relation de préférence (ordinale, cardinale, ou autre), puis nous aborderons le problème de la représentation compacte de préférences sur des domaines combinatoires. Nous présenterons ensuite trois familles de langages de représentation compacte : les langages s'appuyant sur la logique propositionnelle, les CP-nets et les langages fondés sur l'indépendance additive généralisée. Enfin, nous présenterons une application de ces langages pour les problèmes d'allocation de ressources (enchères combinatoires, problèmes de partage équitable).

While there are several languages for representing combinatorial preferences over sets of alternatives, none of these are well-suited to the representation of ordinal preferences over sets of goods (which are typically required to be monotonic). We propose such a language, taking inspiration from previous work on graphical languages for preference representation, specifically CP-nets, and introduce conditional importance networks (CI-nets). A CI-net includes statements of the form "if I have a set A of goods, and I do not have any of the goods from some other set B, then I prefer the set of goods C over the set of goods D." We investigate expressivity and complexity issues for CI-nets. Then we show that CI-nets are well-suited to the description of fair division problems.

Complex business processes, that may involve numerous actors, require tools that allow for representing, communicating, modeling and reasoning about these processes. In this talk we will shortly introduce one of the prominent business process languages, BPMN, developed by the Object Management Group, which is a graphical language for business process modeling, based on the notion of workflow. Then we will present an attempt to translate this language to the logic of situation calculus. This translation gives a formal backbone to the BPMN language, and makes simple reasoning possible on processes BPMN modeled processes. This work is very preliminary.

Many real-world problems can be modelled as resource allocation problems implying indivisible goods to distribute among a set of agents. Many of these problems, implying human agents expressing some preferences on the set of objects to allocate, have also in common the notion of social fairness, that is, the fact that the collective decision must reflect the individual preferences. This notion of individual preference representation is also crucial in resource allocation problems: since many of these problems require the expression of non-additive preferences, one may introduce a compact language for expressing preferences, to avoid falling in the combinatorial trap. In this talk we will focus first on the modelling of fair resource allocation problems, borrowing the notion of fairness from microeconomics. We will then introduce a compact representation language based on propositional logic for representing these resource allocation problems, and analyze the impact of compact representation on the complexity of finding a fair allocation, for the notions of fairness introduced in the first part.

On s'intéresse à la prise de décision collective et coopérative dans un groupe d'agents ayant des préférences individuelles s'exprimant par des utilités numériques. Dans ce modèle, les préférences des agents sont agrégées en une préférence commune à l'aide d'une fonction d'utilité collective, traduisant ainsi de manière formelle le critère «éthique» choisi par la collectivité. La plupart des travaux issus du choix social supposent que les agents sont égaux a priori vis-à-vis de la prise de décision, mais ce n'est pas toujours le cas pour des problèmes réels. Nous nous intéressons à la construction et à l'étude de fonctions d'utilité collective prenant en compte ces droits inégaux.

We study the problem of computing a leximin-optimal solution of a constraint network. This problem is highly motivated by fairness and efficiency requirements in many real-world applications implying human agents. We compare several generic algorithms which solve this problem in a constraint programming framework. The first one is entirely original, and the other ones are partially based on existing works adapted to fit with this problem.

We study the problem of computing a leximin-optimal solution of a constraint network. This problem is highly motivated by fairness and efficiency requirements in many real-world applications implying human agents. We compare several generic algorithms which solve this problem in a constraint programming framework. The second one is entirely original, and the other ones are partially based on existing works adapted to fit with this problem. These algorithms are tested on combinatorial auctions instances.

L'objectif de cette présentation est d'introduire quatre algorithmes de programmation par contraintes pour la recherche d'instanciations leximin-optimales dans un réseau de contraintes. Nous commencerons par introduire quelques notions de base de programmation par contraintes, avant de justifier notre intérêt pour les instanciations leximin-optimales par des problèmes de décision collective. Enfin, nous introduirons les algorithmes de calcul de solutions leximin-optimales : le premier d'entre eux est fondé sur une méta-constrainte de cardinalité, le deuxième sur une contrainte de tri, le troisième sur une contrainte d'ordre leximin, et enfin le dernier algorithme, issu de la littérature sur les problèmes de satisfaction de contraintes flexibles, est fondé sur le calcul de sous-ensembles critiques de cardinalité minimale.

We propose two constraint programming algorithms for solving the following problem: fairly and efficiently allocate a finite set of objects to a set of agents, each one having their own utilities, under admissibility constraints. Our algorithms compute an allocation maximizing the leximin order on the utility profiles of the agents. Our main contribution is the use of a cardinality meta-constraint on the one hand, and an adaptation of an existing algorithm for enforcing a multiset ordering constraint on the other hand. Moreover, we describe the application domain that motivated this work: sharing of satellite resources. We extract from this real-world application a simple and precise fair allocation problem that allows for testing and evaluating our algorithms, using a benchmark generator. The implementations of both algorithms have been tested using the constraints programming tool CHOCO, and a translation of the first algorithm to integer linear programming has been tested using CPLEX.

L'objectif de cette présentation est d'introduire quatre algorithmes de programmation par contraintes pour la recherche d'instanciations leximin-optimales dans un réseau de contraintes. Nous commencerons par introduire quelques notions de base de programmation par contraintes, avant de justifier notre intérêt pour les instanciations leximin-optimales par des problèmes de décision collective. Enfin, nous introduirons les algorithmes de calcul de solutions leximin-optimales : le premier d'entre eux est fondé sur une méta-constrainte de cardinalité, le deuxième sur une contrainte de tri, le troisième sur une contrainte d'ordre leximin, et enfin le dernier algorithme, issu de la littérature sur les problèmes de satisfaction de contraintes flexibles, est fondé sur le calcul de sous-ensembles critiques de cardinalité minimale.

Dans le cadre de la programmation par contraintes, nous proposons un algorithme résolvant le problème suivant : allouer d'une manière équitable et efficace un ensemble fini d'objets à des agents ayant chacun leurs utilités propres, sous des contraintes d'admissibilité. L'algorithme calcule une allocation maximisant l'ordre leximin sur les profils d'utilités des agents. Nous décrivons de plus le domaine d'application qui a motivé ces travaux : le partage de ressources satellitaires. Nous en extrayons un problème simple et précis d'allocation équitable, qui nous sert de base, grâce à un générateur de jeux de tests, pour l'évaluation de l'algorithme proposé. Deux implantations de l'algorithme sont comparées, l'une en programmation par contrainte «pure», avec Choco, l'autre en programmation linéaire mixte avec Cplex.

Le problème de l'allocation d'une ressource entre plusieurs agents, ou problème de partage, possède de nombreuses applications concrètes et se retrouve sous des formes très diverses dans le monde réel. Plusieurs paramètres entrent en jeu dans ces problèmes de partage : nature de la ressource, expression des préférences des agents, critère(s) de qualité du partage, procédure d'allocation,... La diversité de ces critères conduit à des problèmes très différents. Les problèmes de partage faisant intervenir des agents humains ou des communautés d'agents humains ont cependant une caractéristique commune : celle de la modélisation du bien-être social, qui représente la stisfaction de la communauté vis-à-vis d'un partage. L'équité y joue un rôle prédominant. Le problème de partage est classiquement abordé dans deux communautés différentes. Alors que les économistes s'intéressent plutôt à la modélisation du bien-être social, aux propriétés des partages et aux procédures d'allocation, les centres d'intérêt de la communauté de l'IA se portent plutôt sur des considérations computationnelles (algorithmique et complexité) ou liées aux langages de représentation. Lors de cet exposé nous introduirons une définition générique du problème de partage, et nous nous intéresserons à ses différentes formes, et aux différentes propriétés du bien-être social. Nous nous pencherons ensuite sur un problème particulier, celui dans lequel la ressource est un ensemble d'objets. Cet exposé sera illustré par un ensemble de problèmes issus du monde réel.

De nombreuses activités industrielles ou de recherche ont un coût tel qu'il est souvent avantageux pour les agents concernés de cofinancer la construction ou l'acquisition d'une ressource commmune nécessaire à l'activité. Cette ressource devra ensuite être exploitée en commun, donc partagée. Les règles de partage devront prendre en compte des préférences antagonistes : chaque agent veut maximiser sa propre satisfaction, tandis que collectivement, on recherche des décisions équitables et exploitant au mieux la ressource. Nous proposons dans cet article un modèle formel du problème de partage de biens indivisibles, sans possibilité de compensations monétaires, et avec des contraintes d'admissibilité quelconques. Ce modèle est appliqué à un cas concret, celui du partage de ressources satellitaires.

Le problème de l'allocation d'une ressource entre plusieurs agents, ou problème de partage, possède de nombreuses applications concrètes et se retrouve sous des formes très diverses dans le monde réel. Le but de cet exposé est d'introduire la notion générique de problème de partage et d'essayer de mettre en évidence une classification des différentes formes de ce problème. Nous nous intéresserons ensuite à l'expression et à la prise en compte des préférences des agents. Ces thèmes seront mis en lumière par la présentation de quelques exemples de problèmes de partage concrets, issus par exemple du domaine spatial, des réseaux informatiques, ou encore de la gestion du trafic aérien. Ce premier séminaire pourra éventuellement être suivi par d'autres, abordant des problématiques plus spécifiques, telles que les formalisations des problèmes de partage, l'algorithmique du calcul de bons partages, la complexité théorique de ce calcul...

We study fair division of indivisible goods among agents from the point of view of compact representation and computational complexity. We identify the complexity of several problems, including that of deciding whether there exists an efficient and envy-free allocation when preferences are represented in a succinct way. We also draw connections to nonmonotonic reasoning.