Page personnelle de Sylvain Bouveret

Fairly and efficiently dividing a set of indivisible objects between a set of agents is a complex problem with a lot of practical applications. These applications range from allocating courses to students to scheduling observation requests on a constellation of Earth observing satellites. In this talk, after a short general introduction on fair division, we will present a very simple yet remarkable allocation protocol: picking sequences. Being conceptually quite simple, this protocol can be easily understood and implemented in various practical contexts. Yet, in spite of its simplicity, this protocol has nevertheless very appealing theoretical properties. During the presentation, we will particularly focus on the problem of finding the fairest picking sequences for a given configuration. We will also touch upon the topic of manipulating picking sequences.

De nombreuses situations que nous rencontrons au quotidien exigent que l'on prenne des décisions en commun entre plusieurs personnes : élections, partage de ressources, recrutement de candidats, sont quelques exemples des problèmes de décision collective que nous pouvons rencontrer. L'objectif de cet exposé sera de vous faire découvrir le domaine du choix social, à travers les différents types de problèmes qui le constituent. Dans la seconde partie de l'exposé, nous nous pencherons un peu plus particulièrement sur le vote, où nous nous intéresserons à des problématiques particulières telles que par exemple l'analyse des propriétés des modes de scrutin, ou encore le charcutage électoral. Amenez un ordinateur (ou alors un téléphone intelligent) : il est possible que je vous fasse voter sur une interface en ligne.

The problem of electing a set of representatives that stand for a given society is at the heart of any reasonable democracy. This problem has been discussed for ages, and social choice theorists have proposed dozens of voting methods, that all have their own merits and properties (but all suffer from the same paradoxes). There exist many voting rules. Yet, mainly the most simple ones like plurality or first-past-the-post are commonly used for crucial political elections (except in a few countries). Suppose that we change the voting rule for such high-stake political elections. What impact would it have on the voters’ behaviour and on the result of the election itself? This has been the main topic of two different experiments that have been carried out in France in 2017. The first one was run during the French presidential election and involved more than 40,000 voters that were asked to test alternative voting rules to elect the French president. The second one was run after the legislative election and aimed at using computer simulations to evaluate the impact of a reform of this election. In his talk, Sylvain Bouveret will use these two experiments to illustrate what happens when computational social choice theorists go out of the labs in the wild world of political elections.

The problem of electing a set of representatives that stand for a given society is at the heart of any reasonable democracy. This problem has been discussed for ages, and social choice theorists have proposed dozens of voting methods, that all have their own merits and properties (but all suffer from the same paradoxes). There exist many voting rules. Yet, mainly the most simple ones like plurality or first-past-the-post are commonly used for crucial political elections (except in a few countries). Suppose that we change the voting rule for such high-stake political elections. What impact would it have on the voters’ behaviour and on the result of the election itself? This has been the main topic of two different experiments that have been carried out in France in 2017. The first one was run during the French presidential election and involved more than 40,000 voters that were asked to test alternative voting rules to elect the French president. The second one was run after the legislative election and aimed at using computer simulations to evaluate the impact of a reform of this election. In his talk, Sylvain Bouveret will use these two experiments to illustrate what happens when computational social choice theorists go out of the labs in the wild world of political elections.

Fairly and efficiently dividing a set of indivisible objects between a set of agents is a complex problem with a lot of practical applications. These applications range from allocating courses to students to scheduling observation requests on a constellation of Earth observing satellites. In this talk, after a short general introduction on fair division, we will present a very simple yet remarkable allocation protocol: picking sequences. In spite of its simplicity, making it an appealing protocol for practical use, it has nevertheless very interesting theoretical properties. During the presentation, we will particularly focus on the problem of computing an optimal picking sequence and on aspects related to the agents strategic behaviour.

We consider fair allocation of indivisible items under an additional constraint: there is an undirected graph describing the relationship between the items, and each agent's share must form a connected subgraph of this graph. This framework captures, e.g., fair allocation of land plots, where the graph describes the accessibility relation among the plots. We focus on agents that have additive utilities for the items, and consider several common fair division solution concepts, such as proportionality, envy-freeness and maximin share guarantee. While finding good allocations according to these solution concepts is computationally hard in general, we design efficient algorithms for special cases where the underlying graph has simple structure, and/or the number of agents --- or, less restrictively, the number of agent types --- is small. In particular, despite non-existence results in the general case, we prove that for acyclic graphs a maximin share allocation always exists and can be found efficiently.

Fairly and efficiently dividing a set of indivisible objects between a set of agents is a complex problem with a lot of practical applications. These applications range from allocating courses to students to scheduling observation requests on a constellation of Earth observing satellites. In this talk, after a short general introduction on fair division, we will present a very simple yet remarkable allocation protocol: picking sequences. In spite of its simplicity, making it an appealing protocol for practical use, it has nevertheless very interesting theoretical properties. During the presentation, we will particularly focus on the problem of computing an optimal picking sequence and on aspects related to the agents strategic behaviour.

Le domaine du choix social s’intéresse à la formalisation des règles permettant, au sein d’une micro-société, de prendre en compte les opinions et préférences des divers individus en présence afin d’aboutir à une décision collective reflétant une forme de consensus. Bien que les philosophes se soient penchés dès l’antiquité sur ces domaines, on associe souvent la naissance de la théorie du choix social aux réflexions de Nicolas de Condorcet et Jean-Charles de Borda à la fin du XVIIIème siècle. Depuis, la théorie du choix social a principalement été l’apanage des économistes, des philosophes, des psychologues ou des mathématiciens, jusqu’à très récemment, où ce domaine a rencontré l’informatique, entraînant l’émergence du choix social computationnel. Ce rapprochement n’a rien d’étonnant : la recherche de consensus dans une collectivité étant une activité humaine par essence, il était donc naturel que l’informatique, et plus précisément l’intelligence artificielle, s’y intéresse et s’en empare. Dans cet exposé, nous tâcherons de dresser un panorama de ce domaine relativement nouveau et fructueux. Nous en évoquerons les principaux thèmes − théorie du vote, partage équitable de ressources, formation de coalition, agrégation de jugement − et nous donnerons quelques exemples de problèmes qui intéressent particulièrement la communauté des chercheurs en intelligence artificielle.

Le problème d'avoir à partager de manière efficace et équitable un ensemble d'objets indivisibles entre des agents est un problème complexe et ayant de nombreuses applications concrètes, allant de l'allocation de cours à des étudiants à l'allocation de tâches sur des machines. Dans cet exposé, après une introduction générale sur le problème de partage équitable de ressources, nous nous focaliserons sur le problème de partage sous hypothèse de préférences additives. Nous introduirons cinq critères formant une échelle linéaire permettant d'évaluer le degré d'équité d'un partage. Nous verrons que malgré leur simplicité, ces critères ont des propriétés extrêmement intéressantes et posent des problèmes de calcul (encore ouverts) épineux.

Le problème d'avoir à partager de manière efficace et équitable un ensemble d'objets indivisibles entre des agents est un problème complexe et ayant de nombreuses applications concrètes, allant de l'allocation de cours à des étudiants à l'allocation de tâches sur des machines. Dans cet exposé, après une introduction générale sur le problème de partage équitable de ressources, nous nous pencherons sur un protocole très simple d'allocation d'objets indivisibles : les séquences de choix. Ce protocole est remarquable car il est très simple à instancier sur des problèmes concrets, et possède néanmoins des propriétés très intéressantes. Nous nous intéresserons plus particulièrement au problème de calcul d'une séquence optimale, et à des considération liées au comportement stratégique des agents.

L'information géographique participative et citoyenne (VGI) est une nouvelle tendance observée dans les systèmes d'information géographique. Cette approche diffère radicalement du processus de production habituel des jeux de données géographiques en ceci que les données sont produites de manière collaborative par un ensemble d'utilisateurs contribuant individuellement à la base de données. L'un des projets phares de cette approche est OpenStreetMap, dont l'objectif affiché est de constituer une base de données cartographique collaborative libre (ouverte) du monde, et qui compte presque deux millions de contributeurs à l'heure actuelle. L'objectif de la présentation est d'introduire le principe de l'information géographique participative et citoyenne en l'analysant sous le prisme du projet OpenStreetMap. Nous présenterons l'historique et la philosophie d'OpenStreetMap et le modèle de données sous-jacent. Nous expliquerons de plus comment contribuer au projet et comment en exploiter les données. Enfin, nous nous appuierons sur cette présentation du projet OpenStreetMap pour tâcher de démêler les liens entre l'information participative et les jeux de données géographiques conventionnels et tâcher de comprendre en quoi cette nouvelle approche bouleverse l'écosystème traditionnel des données géographiques.

We investigate five different fairness criteria in a simple model of fair resource allocation of indivisible goods based on additive preferences. We show how these criteria are connected to each other, forming an ordered scale that can be used to characterize how conflicting the agents' preferences are: the less conflicting the preferences are, the more demanding criterion this instance will be able to satisfy, and the more satisfactory the allocation will be. We analyze the computational properties of the five criteria, give some experimental results about them, and further investigate a slightly richer model with k-additive preferences.

We define a family of rules for dividing $m$ indivisible goods among agents, parameterized by a scoring vector and a social welfare aggregation function. We assume that agents' preferences over sets of goods are additive, but that the input is ordinal: each agent simply ranks single goods. Similarly to positional scoring voting rules in voting, a scoring vector $s = (s_1, \ldots , s_m)$ consists of $m$ nonincreasing nonnegative weights, where $s_i$ is the score of a good assigned to an agent who ranks it in position $i$. The global score of an allocation for an agent is the sum of the scores of the goods assigned to her. The social welfare of an allocation is the aggregation of the scores of all agents, for some aggregation function $\star$ such as, typically, $+$ or $\min$. The rule associated with $s$ and $\star$ maps a profile of individual rankings over goods to (one of) the allocation(s) maximizing social welfare. After defining this family of rules and discussing some of their properties, we focus on the computation and approximation of winning allocations.

In this talk I will present a preliminary work about fair division of indivisible goods. A standard approach in fair division problems is to consider a given fairness property (such as envy-freeness), and to look for an allocation that satisfies this property. In this work we investigate five such fairness properties (some of them being original or not very well-known) in a simple model of fair resource allocation of indivisible goods with additive preferences. We show how these properties are connected to each other, forming an ordered scale that can be used to characterize how conflicting the agents' preferences are: the less these preferences are conflicting, the more exigent property this instance will be able to satisfy, and the easier and more satisfactory the allocation will be. We also introduce some theoretical computational properties, and we further investigate a slightly richer model with k-additive preferences.

Le but de cet exposé est de faire une présentation technique générale du projet OpenStreetMap, projet dont l'objectif est de mettre à disposition du public une base de données géographique mondiale collaborative. Nous présenteronts tout d'abord rapidement quelques éléments historiques et quelques-uns des objectifs techniques et éthiques (liberté des données) du projet OSM. Puis nous aborderons des sujets plus techniques, en commençant par le modèle de données, et l'ontologie primaire actuelle d'OpenStreetMap. Puis nous parlerons des outils faisant partie de l'écosystème OpenStreetMap, en commençant pas les outils d'édition, permettant aux utilisateurs de contribuer à la base, et en finissant par les outils permettant d'exploiter ces données (générateurs de tuiles, convertisseurs, APIs...). Nous terminerons cette présentation par un cas d'étude concret dédié à l'analyse de la qualité des données dans OpenStreetMap.

We consider the following sequential allocation process. A benevolent central authority has to allocate a set of indivisible goods to a set of agents whose preferences it is totally ignorant of. We consider the process of allocating objects one after the other by designating an agent and asking her to pick one of the objects among those that remain. The problem consists in choosing the "best" sequence of agents, according to some optimality criterion. We assume that agents have additive preferences over objects. The choice of an optimality criterion depends on three parameters: how utilities of objects are related to their ranking in an agent's preference relation; how the preferences of different agents are correlated; and how social welfare is defined from the agents' utilities. We address the computation of a sequence maximizing expected social welfare under several assumptions. We also address strategical issues.

The specification of a decision making problem includes the agents preferences on the available alternatives. The choice of a model of preferences (e.g., utility functions or binary relations) does not say how preferences should be represented (or specified). This tutorial we will give a survey of graphical languages for compact preference representation. We will first survey languages for ordinal preferences, with a special focus on CP-nets; then we will survey languages for numerical preferences. The last part of the tutorial will be devoted to applications of these languages to various AI fields, namely constrained optimization, planning, recommender systems, configuration, voting, and resource allocation. This tutorial is directed to AI researchers who work on related areas and want/need to know more about preference representation: researchers in knowledge representation, constraints, autonomous agents, multiagent systems (especially game-theoretic agents and computational social choice), planning, user modelling. There is very little prerequisite knowledge; the tutorial will be accessible to almost all AI researchers.

We study the problem of fairly allocating a set of indivisible goods to a set of agents having additive preferences. More precisely, we consider the problem in which each object can be in two possible states: good or bad. We further assume that the actual object state is not known at the allocation time, but that the decision-maker knows the probability for each object to be in each state. We propose a formal model of this problem, based on the notions of ex-ante and ex-post fairness, and we propose some algorithms aiming at computing optimal allocations in the sense of ex-post egalitarianism, the efficiency of these algorithms being tested on random instances.

The aim of this lecture is to give an overview of multiagent resource allocation, with a special focus on compact preference representation, collective decision criteria, and associated computational issues (complexity and algorithms). Some material included in this presentation is inspired from various tutorials by Ulle Endriss and Nicolas Maudet.

We study 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.

We study 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.

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.