Afficher :
Articles de journaux
Conférences internationales
Workshops internationaux
Conférences nationales

2012

[LBL-ECAI12]Lumet, Charles, Bouveret, Sylvain et Lemaître, Michel (2012). Fair division of indivisible goods under risk. In Proceedings of the 20th European Conference on Artificial Intelligence (ECAI'12), Montpellier, France. IOS Press.
[Résumé] [BibTeX] [PDF]
We consider the problem of fairly allocating a set of $m$ indivisible objects to $n$ agents having additive preferences over them. In this paper we propose an extension of this classical problem, where each object can possibly be in bad condition (e.g broken), in which case its actual value is zero. We assume that the central authority in charge of allocating the objects does not know beforehand the objects conditions, but only has probabilistic information. The aim of this work is to propose a formal model of this problem, to adapt some classical fairness criteria to this extended setting, and to introduce several approaches to compute optimal allocations for small instances as well as suboptimal good allocations for real-world inspired allocation problems of realistic size.
@InProceedings{LBL-ECAI12,
author    = {Charles Lumet and Sylvain Bouveret and Michel Lemaître},
title     = {Fair division of indivisible goods under risk},
booktitle = {Proceedings of the 20th European Conference on Artificial Intelligence (ECAI'12)},
year      = 2012,
month     = {August},
publisher = {IOS Press},
note      = {(to appear)},
abstract  = {We consider the problem of fairly allocating a set of $m$ indivisible objects to $n$ agents having additive preferences over them. In this paper we propose an extension of this classical problem, where each object can possibly be in bad condition (\textit{e.g} broken), in which case its actual value is zero. We assume that the central authority in charge of allocating the objects does not know beforehand the objects conditions, but only has probabilistic information. The aim of this work is to propose a formal model of this problem, to adapt some classical fairness criteria to this extended setting, and to introduce several approaches to compute optimal allocations for small instances as well as suboptimal good allocations for real-world inspired allocation problems of realistic size.},
url       = {http://recherche.noiraudes.net/resources/papers/ECAI12.pdf}
}

2011

[LBL-MFI11]Lumet, Charles, Bouveret, Sylvain et Lemaître, Michel (2011). Partage équitable de biens indivisibles sous risque. In Actes des septièmes journées francophones Modèles Formels de l'Interaction (MFI'11), Rouen, France.
[Résumé] [BibTeX] [PDF]
Cet article concerne le problème de partage équitable d'objets indivisibles entre des agents ayant des préférences additives sur ces objets. Nous nous intéressons au cas où chaque objet peut être dans deux états possibles : normal ou dégradé. Nous supposons de plus que l'état réel des objets n'est pas connu au moment du partage, mais que le décideur connaît la probabilité pour chaque objet d'être normal ou dégradé. Nous proposons un modèle formel de ce problème s'appuyant sur les notions d'équité ex-ante et ex-post, et nous proposons des algorithmes de calcul de partages optimaux au sens de l'égalitarisme ex-post que nous évaluons sur des jeux d'instances aléatoires.
@InProceedings{LBL-MFI11,
type      = {confnat},
author    = {Charles Lumet and Sylvain Bouveret and Michel Lemaître},
title     = {Partage équitable de biens indivisibles sous risque},
booktitle = {Actes des septièmes journées francophones Modèles Formels de l'Interaction (MFI'11)},
year      = 2011,
month     = {juin},
abstract  = {Cet article concerne le problème de partage équitable d'objets indivisibles entre des agents ayant des préférences additives sur ces objets. Nous nous intéressons au cas où chaque objet peut être dans deux états possibles : normal ou dégradé. Nous supposons de plus que l'état réel des objets n'est pas connu au moment du partage, mais que le décideur connaît la probabilité pour chaque objet d'être normal ou dégradé. Nous proposons un modèle formel de ce problème s'appuyant sur les notions d'équité \textit{ex-ante} et \textit{ex-post}, et nous proposons des algorithmes de calcul de partages optimaux au sens de l'égalitarisme \textit{ex-post} que nous évaluons sur des jeux d'instances aléatoires.},
url       = {http://recherche.noiraudes.net/resources/papers/MFI11.pdf},
}
[LBL-WSCAI11]Lumet, Charles, Bouveret, Sylvain et Lemaître, Michel (2011). Fair division of indivisible goods under risk. In Proceedings of the IJCAI-2011 Workshop on Social Choice and Artificial Intelligence, Barcelona, Spain.
[Résumé] [BibTeX] [PDF]
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.
@InProceedings{LBL-WSCAI11,
type      = {workshop},
author    = {Charles Lumet and Sylvain Bouveret and Michel Lemaître},
title     = {Fair division of indivisible goods under risk},
booktitle = {Proceedings of the IJCAI-2011 Workshop on Social Choice and Artificial Intelligence},
year      = 2011,
month     = {July},
abstract  = {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 \textit{ex-ante} and \textit{ex-post} fairness, and we propose some algorithms aiming at computing optimal allocations in the sense of \textit{ex-post} egalitarianism, the efficiency of these algorithms being tested on random instances.},
url       = {http://recherche.noiraudes.net/resources/papers/WSCAI11.pdf},
editors   = {Edith Elkind and Ulle Endriss and Jérôme Lang}
}
[BBDD-HOTSWUP11]Bouveret, Sylvain, Brunel, Julien, Chemouil, David et Dagnat, Fabien (2011). Towards a categorical framework to ensure correct software evolutions. In Proceedings of the Third Workshop on Hot Topics in Software Upgrades (HotSWUp'11), Hannover, Germany.
[Résumé] [BibTeX] [PDF]
Distributed software, such as satellite software are now developed and managed by several actors. In this context supporting the maintenance and therefore the evolution of such applications is complex and need a formal framework. In this article, we propose a first step towards such a formal framework to ensure the correctness of software evolutions. Using category theory, we can model software and represent patches. This modeling allows to identify the proof obligations that the provider of a patch has to discharge in order to ensure that its patch preserves the correctness of the software.
@InProceedings{BBDD-HOTSWUP11,
type      = {workshop},
author    = {Sylvain Bouveret and Julien Brunel and David Chemouil and Fabien Dagnat},
title     = {Towards a categorical framework to ensure correct software evolutions},
booktitle = {Proceedings of the Third Workshop on Hot Topics in Software Upgrades (HotSWUp'11)},
year      = 2011,
month     = {April},
abstract  = {Distributed software, such as satellite software are now developed and managed by several actors. In this context supporting the maintenance and therefore the evolution of such applications is complex and need a formal framework. In this article, we propose a  first step towards such a formal framework to ensure the correctness of software evolutions. Using category theory, we can model software and represent patches. This modeling allows to identify the proof obligations that the provider of a patch has to discharge in order to ensure that its patch preserves the correctness of the software.},
url       = {http://recherche.noiraudes.net/resources/papers/HOTSWUP10.pdf}
}
[BL-IJCAI11]Bouveret, Sylvain et Lang, Jérôme (2011). A general elicitation-free protocol for allocating indivisible goods. In Proceedings of the 22st International Joint Conference on Artificial Intelligence (IJCAI'11), Barcelona, Spain.
[Résumé] [BibTeX] [PDF]
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.
@InProceedings{BL-IJCAI11,
author    = {Sylvain Bouveret and Jérôme Lang},
title     = {A general elicitation-free protocol for allocating indivisible goods},
booktitle = {Proceedings of the 22st International Joint Conference on Artificial Intelligence (IJCAI'11)},
year      = 2011,
month     = {July},
abstract  = {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.},
url       = {http://recherche.noiraudes.net/resources/papers/IJCAI11.pdf},
}

2010

[BEL-COMSOC10]Bouveret, Sylvain, Endriss, Ulle et Lang, Jérôme (2010). Fair Division under Ordinal Preferences: Computing Envy-Free Allocations of Indivisible Goods. In Proceedings of the 3rd International Workshop on Computational Social Choice (COMSOC'10), Düsseldorf, Germany.
[Résumé] [BibTeX] [PDF]
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-COMSOC10,
type      = {workshop},
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 3rd International Workshop on Computational Social Choice (COMSOC'10)},
year      = 2010,
month     = {September},
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/COMSOC10.pdf}
}
[BEL-ECAI10]Bouveret, Sylvain, Endriss, Ulle et Lang, Jérôme (2010). Fair Division under Ordinal Preferences: Computing Envy-Free Allocations of Indivisible Goods. In Proceedings of the 19th European Conference on Artificial Intelligence (ECAI'10), Lisbon, Portugal. IOS Press.
[Résumé] [BibTeX] [PDF]
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,
month     = {August},
publisher = {IOS Press},
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}
}

2009

[KBKZ-ADT09]Keijzer, Bart, Bouveret, Sylvain, Klos, Tomas et Zhang, Yingqian (2009). On the complexity of efficiency and envy-freeness in fair division of indivisible goods with additive preferences. In Proceedings of the 1st International Conference on Algorithmic Decision Theory (ADT'09), Venice, Italy. Springer Verlag.
[Résumé] [BibTeX] [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$2p-complete.
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},
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.},
}
[BEL-IJCAI09]Bouveret, Sylvain, Endriss, Ulle et Lang, Jérôme (2009). Conditional Importance Networks: A Graphical Language for Representing Ordinal, Monotonic Preferences over Sets of Goods. In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI'09), Pasadena, California.
[Résumé] [BibTeX] [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,
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}
}
[BL-AIJ09]Bouveret, Sylvain et Lemaître, Michel (2009). Computing leximin-optimal solutions in constraint networks. In Artificial Intelligence, 173(2): 343-364.
[Résumé] [BibTeX] [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},
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.}
}

2008

[BL-JAIR08]Bouveret, Sylvain et Lang, Jérôme (2008). Efficiency and Envy-freeness in Fair Division of Indivisible Goods: Logical Representation and Complexity. In Journal of Artificial Intelligence Research (JAIR), 32: 525-564.
[Résumé] [BibTeX] [PDF]
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.}
}

2007

[BL-IJCAI07]Bouveret, Sylvain et Lemaître, Michel (2007). New Constraint Programming Approaches for the Computation of Leximin-Optimal Solutions in Constraint Networks. In Veloso, Manuela M., éditeurs, Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI'07), Hyderabad, India.
[Résumé] [BibTeX] [PDF]
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},
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.}
}
[BL-MFI07]Bouveret, Sylvain et Lemaître, Michel (2007). Fonctions d'utilité collective avec droits exogènes inégaux. In Paschos, Vangelis et Roy, Bernard, éditeurs, Actes des cinquièmes journées francophones Modèles Formels de l'Interaction (MFI'07), Paris, France. Université Paris IX Dauphine.
[Résumé] [BibTeX] [PDF]
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},
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.},
}

2006

[BL-JFPC06]Bouveret, Sylvain et Lemaître, Michel (2006). Un algorithme de programmation par contraintes pour la recherche d'allocations leximin-optimales. In AFPC, éditeurs, Actes des deuxièmes Journées Francophones de Programmation par Contraintes (JFPC'06), Nîmes, France.
[Résumé] [BibTeX] [PDF]
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},
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.},
}
[BL-COMSOC06]Bouveret, Sylvain et Lemaître, Michel (2006). Finding leximin-optimal solutions using constraint programming: new algorithms and their application to combinatorial auctions. In Endriss, Ulle et Lang, Jérôme, éditeurs, Proceedings of the 1st International Workshop on Computational Social Choice (COMSOC'06), ILLC, University of Amsterdam.
[Résumé] [BibTeX] [PDF]
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},
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.},
}
[BL-ECAIWS06]Bouveret, Sylvain et Lemaître, Michel (2006). Comparison of two constraint programming algorithms for computing leximin-optimal allocations. In Prestwich, Steven et Hnich, Brahim, éditeurs, Proceedings the workshop on Modelling and Solving Problems with Constraints, ECAI'06, Riva del Garda, Italy.
[Résumé] [BibTeX] [PDF]
@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.},
}

2005

[BFLL-MFI05]Bouveret, Sylvain, Fargier, Hélène, Lang, Jérôme et Lemaître, Michel (2005). Un modèle général et des résultats de complexité pour le partage de biens indivisibles. In Herzig, Andreas, Lespérance, Yves et Mouaddib, Abdel-Illah, éditeurs, Actes des troisièmes journées francophones Modèles Formels de l'Interaction (MFI'05), Caen, France. Cépaduès Éditions.
[Résumé] [BibTeX] [PDF]
@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},
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.}
}
[BL-IJCAI05]Bouveret, Sylvain et Lang, Jérôme (2005). Efficiency and envy-freeness in fair division of indivisible goods: logical representation and complexity. In Kaelbling, Leslie Pack et Saffiotti, Alessandro, éditeurs, Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI'05), Edinburgh, Scotland. Professional Book Center.
[Résumé] [BibTeX] [PDF]
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)},
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.}
}
[BLFL-AAMAS05]Bouveret, Sylvain, Lemaître, Michel, Fargier, Hélène et Lang, Jérôme (2005). Allocation of indivisible goods: a general model and some complexity results. In Dignum, Frank, Dignum, Virginia, Koenig, Sven, Kraus, Sarit, Singh, Munindar P. et Wooldridge, Michael, éditeurs, 4rd International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS'05), Utrecht, The Netherlands. ACM.
[Résumé] [BibTeX] [PDF]
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)},