Page personnelle de Sylvain Bouveret

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.

@InProceedings{BEL-ECAI10,
  author    = {Sylvain Bouveret and Ulle Endriss and Jérôme Lang},
  title     = {Fair Division under Ordinal Preferences: Computing Envy-Free Allocations of Indivisible Goods},
  booktitle = {Proceedings of the 19th European Conference on Artificial Intelligence (ECAI'10)},
  year      = 2010,
  address   = {Lisbon, Portugal},
  month     = {August},
  publisher = {IOS Press},
  note      = {(to appear)},
  abstract  = {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. 
},
  url       = {http://recherche.noiraudes.net/resources/papers/ECAI10.pdf}
}

We study the problem of allocating a set of indivisible goods to a set of agents having additive preferences. We introduce two new important complexity results concerning efficiency and fairness in resource allocation problems: we prove that the problem of deciding whether a given allocation is Pareto-optimal is coNP-complete, and that the problem of deciding whether there is a Pareto-efficient and envy-free allocation is $\Sigma$₂^p-complete.

@InProceedings{KBKZ-ADT09,
  author    = {Bart de Keijzer and Sylvain Bouveret and Tomas Klos and Yingqian Zhang},
  title     = {On the complexity of efficiency and envy-freeness in fair division of indivisible goods with additive preferences},
  booktitle = {Proceedings of the 1st International Conference on Algorithmic Decision Theory (ADT'09)},
  year      = 2009,
  series    = {Lecture Notes in Artificial Intelligence},
  address   = {Venice, Italy},
  month     = {October},
  publisher = {Springer Verlag},
  abstract  = {We study the problem of allocating a set of indivisible goods to a set of agents having additive preferences. We introduce two new important complexity results concerning efficiency and fairness in resource allocation problems: we prove that the problem of deciding whether a given allocation is Pareto-optimal is \textsf{coNP}-complete, and that the problem of deciding whether there is a Pareto-efficient and envy-free allocation is $\Sigma_2^p$-complete.},
  url       = {http://recherche.noiraudes.net/resources/papers/ADT09.pdf}
}

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.

@InProceedings{BEL-IJCAI09,
  author    = {Sylvain Bouveret and Ulle Endriss and Jérôme Lang},
  title     = {Conditional Importance Networks: A Graphical Language for Representing Ordinal, Monotonic Preferences over Sets of Goods},
  booktitle = {Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI'09)},
  pages     = {67-72},
  year      = 2009,
  address   = {Pasadena, California},
  month     = {July},
  abstract  = {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.},
  url       = {http://ijcai.org/papers09/Papers/IJCAI09-022.pdf}
}

In many real-world multiobjective optimization problems one needs to find solutions or alternatives that provide a fair compromise between different conflicting objective functions--which could be criteria in a multicriteria context, or agent utilities in a multiagent context--while being efficient (i.e. informally, ensuring the greatest possible overall agents' satisfaction). This is typically the case in problems implying human agents, where fairness and efficiency requirements must be met. Preference handling, resource allocation problems are another examples of the need for balanced compromises between several conflicting objectives. A way to characterize good solutions in such problems is to use the leximin preorder to compare the vectors of objective values, and to select the solutions which maximize this preorder. In this article, we describe five algorithms for finding leximin-optimal solutions using constraint programming. Three of these algorithms are original. Other ones are adapted, in constraint programming settings, from existing works. The algorithms are compared experimentally on three benchmark problems.

@article{BL-AIJ09,
  author    = {Sylvain Bouveret and Michel Lemaître},
  title     = {Computing leximin-optimal solutions in constraint networks},
  journal   = {Artificial Intelligence},
  volume    = {173},
  number    = {2},
  pages     = {343-364},
  year      = {2009},
  issn      = {0004-3702},
  doi       = {DOI: 10.1016/j.artint.2008.10.010},
  url       = {http://www.sciencedirect.com/science/article/B6TYF-4TW6HTM-1/2/cfd8c4ad862142dda70b86e3dc15d4d5},
  abstract  = {In many real-world multiobjective optimization problems one needs to find solutions or alternatives that provide a fair compromise between different conflicting objective functions--which could be criteria in a multicriteria context, or agent utilities in a multiagent context--while being efficient (i.e. informally, ensuring the greatest possible overall agents' satisfaction). This is typically the case in problems implying human agents, where fairness and efficiency requirements must be met. Preference handling, resource allocation problems are another examples of the need for balanced compromises between several conflicting objectives. A way to characterize good solutions in such problems is to use the leximin preorder to compare the vectors of objective values, and to select the solutions which maximize this preorder. In this article, we describe five algorithms for finding leximin-optimal solutions using constraint programming. Three of these algorithms are original. Other ones are adapted, in constraint programming settings, from existing works. The algorithms are compared experimentally on three benchmark problems.}
}

We consider the problem of allocating fairly a set of indivisible goods among agents from the point of view of compact representation and computational complexity. We start by assuming that agents have dichotomous preferences expressed by propositional formulae. We express efficiency and envy-freeness in a logical setting, which reveals unexpected connections to nonmonotonic reasoning. Then we identify the complexity of determining whether there exists an efficient and envy-free allocation, for several notions of efficiency, when preferences are represented in a succinct way (as well as restrictions of this problem). We first study the problem under the assumption that preferences are dichotomous, and then in the general case.

@article{BL-JAIR08,
  author    = {Sylvain Bouveret and Jérôme Lang},
  title     = {Efficiency and Envy-freeness in Fair Division of Indivisible Goods: Logical Representation and Complexity},
  journal   = {Journal of Artificial Intelligence Research (JAIR)},
  volume    = {32},
  year      = {2008},
  pages     = {525-564},
  url       = {http://www.jair.org/media/2467/live-2467-3902-jair.pdf},
  abstract  = {We consider the problem of allocating fairly a set of indivisible goods among agents from the point of view of compact representation and computational complexity. We start by assuming that agents have dichotomous preferences expressed by propositional formulae. We express efficiency and envy-freeness in a logical setting, which reveals unexpected connections to nonmonotonic reasoning. Then we identify the complexity of determining whether there exists an efficient and envy-free allocation, for several notions of efficiency, when preferences are represented in a succinct way (as well as restrictions of this problem). We first study the problem under the assumption that preferences are dichotomous, and then in the general case.}
}

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.

@inproceedings{BL-IJCAI07,
  author    = {Sylvain Bouveret and
               Michel Lemaître},
  title     = {New Constraint Programming Approaches for the Computation
               of Leximin-Optimal Solutions in Constraint Networks},
  editor    = {Manuela M. Veloso},
  booktitle = {Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI'07)},
  year      = {2007},
  month     = {January},
  address   = {Hyderabad, India},
  pages     = {62-67},
  url       = {http://www.ijcai.org/papers07/Papers/IJCAI07-008.pdf},
  abstract  = {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.}
}

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.

@InProceedings{BL-MFI07,
 type      = {confnat},
 author    = {Sylvain Bouveret and Michel Lemaître},
 title     = {Fonctions d'utilité collective avec droits exogènes inégaux},
 booktitle = {Actes des cinquièmes journées francophones Modèles Formels de l'Interaction (MFI'07)},
 year      = {2007},
 editor    = {Vangelis Paschos and Bernard Roy},
 month     = {mai},
 address   = {Paris, France},
 publisher = {Université Paris IX Dauphine},
 url       = {http://recherche.noiraudes.net/resources/papers/MFI07.pdf}
 note      = {(in french)},
 abstract  = {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.},
}

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.

@InProceedings{BL-JFPC06,
 type      = {confnat},
 author    = {Sylvain Bouveret and Michel Lemaître},
 title     = {Un algorithme de programmation par contraintes pour la recherche d'allocations leximin-optimales},
 booktitle = {Actes des deuxièmes Journées Francophones de Programmation par Contraintes (JFPC'06)},
 year      = {2006},
 address   = {Nîmes, France},
 editor    = {AFPC},
 month     = {juin},
 url       = {http://recherche.noiraudes.net/resources/papers/JFPC06.pdf}
 note      = {(in french)},
 abstract  = {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.},
}

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.

@InProceedings{BL-COMSOC06,
  type      = {workshop},
  author    = {Sylvain Bouveret and Michel Lemaître},
  title     = {Finding leximin-optimal solutions using constraint programming: new algorithms and their application to combinatorial auctions},
  booktitle = {Proceedings of the 1st International Workshop on Computational Social Choice (COMSOC'06)},
  year      = 2006,
  editor    = {Ulle Endriss and Jérôme Lang},
  month     = {December},
  address   = {ILLC, University of Amsterdam},
  month     = {December},
  url       = {http://staff.science.uva.nl/~ulle/COMSOC-2006/papers/30-bouveret.pdf},
  abstract  = {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.},
}

@InProceedings{BL-ECAIWS06,
 type      = {workshop},
 author    = {Sylvain Bouveret and Michel Lemaître},
 title     = {Comparison of two constraint programming algorithms for computing leximin-optimal allocations},
 booktitle = {Proceedings the workshop on Modelling and Solving Problems with Constraints, ECAI'06},
 editor    = {Steven Prestwich and Brahim Hnich},
 year      = {2006},
 address   = {Riva del Garda, Italy},
 month     = {August},
 url       = {http://recherche.noiraudes.net/resources/papers/ECAI06.pdf}
 abstract  = {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.},
}

@inproceedings{BFLL-MFI05,
  type      = {confnat},
  author    = {Sylvain Bouveret and Hélène Fargier and Jérôme Lang and Michel Lemaître},
  title     = {Un modèle général et des résultats de complexité pour le partage de biens indivisibles},
  booktitle = {Actes des troisièmes journées francophones Modèles Formels de l'Interaction (MFI'05)},
  year      = 2005,
  editor    = {Andreas Herzig and Yves Lespérance and Abdel-Illah Mouaddib},
  month     = {mai},
  publisher = {Cépaduès Éditions},
  url       = {http://recherche.noiraudes.net/resources/papers/MFI05.pdf}
  abstract  = {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.}
}

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.

@inproceedings{BL-IJCAI05,
  author    = {Sylvain Bouveret and
               Jérôme Lang},
  title     = {Efficiency and envy-freeness in fair division of indivisible
               goods: logical representation and complexity},
  pages     = {935-940},
  editor    = {Leslie Pack Kaelbling and
               Alessandro Saffiotti},
  booktitle = {Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI'05)},
  address   = {Edinburgh, Scotland},
  month     = {July},
  publisher = {Professional Book Center},
  year      = {2005},
  url       = {http://www.ijcai.org/papers/0656.pdf},
  abstract = {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.}
}

Many industrial or research activities are so expensive that it is often benefitable for the involved agents to cofund the construction or the purchase of a common required resource. This resource will then be exploited in common, therefore in a shared way. The rules for resource sharing should take account of the possibly antagonistic preferences: each agent wants to maximize its own satisfaction, whereas, from the collective point of view, decisions which both are equitable and exploit the resources in an optimal way are looked for. We give in this article a formal model for indivisible goods resource sharing without monetary compensations and with arbitrary admissibility constraints. We also give some complexity results about this model. The model is applied to a real-world case, namely satellite resource sharing.

@inproceedings{BLFL-AAMAS05,
  author    = {Sylvain Bouveret and
               Michel Lemaître and
               Hélène Fargier and
               Jérôme Lang},
  title     = {Allocation of indivisible goods: a general model and some
               complexity results},
  editor    = {Frank Dignum and
               Virginia Dignum and
               Sven Koenig and
               Sarit Kraus and
               Munindar P. Singh and
               Michael Wooldridge},
  booktitle = {4rd International Joint Conference on Autonomous Agents
               and Multiagent Systems (AAMAS'05)},
  address   = {Utrecht, The Netherlands},
  month     = {July},
  publisher = {ACM},
  year      = {2005},
  pages     = {1309-1310},
  url       = {http://doi.acm.org/10.1145/1082473.1082747},
  note      = {(short paper)},
  abstract  = {Many industrial or research activities are so expensive that it is often benefitable for the involved agents to cofund the construction or the purchase of a common required resource. This resource will then be exploited in common, therefore in a shared way. The rules for resource sharing should take account of the possibly antagonistic preferences: each agent wants to maximize its own satisfaction, whereas, from the collective point of view, decisions which both are equitable and exploit the resources in an optimal way are looked for. We give in this article a formal model for indivisible goods resource sharing without monetary compensations and with arbitrary admissibility constraints. We also give some complexity results about this model. The model is applied to a real-world case, namely satellite resource sharing.}
}