Book chapters

Journals

International conferences

International workshops

National conferences

[ABLM-AAAI18]Aziz, Haris, Bouveret, Sylvain, Caragiannis, Ioannis, Giagkousi, Ira and Lang, Jérôme (2018). Knowledge, Fairness, and Social Constraints. In Proceedings of the 32nd AAAI conference on Artificial Intelligence (AAAI'18), New Orleans, Louisiana, USA. AAAI Press. (to appear).

[Abstract]
[BibTeX]
[PDF]

In the context of fair allocation of indivisible items, fairness concepts often compare the satisfaction of an agent to the satisfaction she would have from items that are not allocated to her: in particular, envy-freeness requires that no agent prefers the share of someone else to her own share. We argue that these notions could also be defined relative to the knowledge that an agent has on how the items that she does not receive are distributed among other agents. We define a family of epistemic notions of envy-freeness, parameterized by a social graph, where an agent observes the share of her neighbours but not of her non-neighbours. We also define an intermediate notion between envy-freeness and proportionality, also parameterized by a social graph. These weaker notions of envy-freeness are useful when seeking a fair allocation, since envy-freeness is often too strong. We position these notions with respect to known ones, thus revealing new rich hierarchies of fairness concepts. Finally, we present a very general framework that covers all the existing and many new fairness concepts.

@InProceedings{ABLM-AAAI18, author = {Haris Aziz and Sylvain Bouveret and Ioannis Caragiannis and Ira Giagkousi and Jérôme Lang}, title = {Knowledge, Fairness, and Social Constraints}, booktitle = {Proceedings of the 32nd AAAI conference on Artificial Intelligence (AAAI'18)}, year = 2018, publisher = {AAAI Press}, address = {New Orleans, Louisiana, USA}, url = {http://recherche.noiraudes.net/resources/papers/AAAI18.pdf}, abstract = {In the context of fair allocation of indivisible items, fairness concepts often compare the satisfaction of an agent to the satisfaction she would have from items that are not allocated to her: in particular, envy-freeness requires that no agent prefers the share of someone else to her own share. We argue that these notions could also be defined relative to the knowledge that an agent has on how the items that she does not receive are distributed among other agents. We define a family of epistemic notions of envy-freeness, parameterized by a social graph, where an agent observes the share of her neighbours but not of her non-neighbours. We also define an intermediate notion between envy-freeness and proportionality, also parameterized by a social graph. These weaker notions of envy-freeness are useful when seeking a fair allocation, since envy-freeness is often too strong. We position these notions with respect to known ones, thus revealing new rich hierarchies of fairness concepts. Finally, we present a very general framework that covers all the existing and many new fairness concepts.}, note = {(to appear)} }

[ZHGB-W2GIS]Ziébelin, Danielle, Hobus, Kim, Genoud, Philippe and Bouveret, Sylvain (2017). Heterogeneous Data Integration Using Web of Data Technologies. In Proceedings of the 15th International Symposium on Web and Wireless Geographical Information Systems (W2GIS 2017), Shanghai, China.

[Abstract]
[BibTeX]
[URL]

The Coordinated Online Information Network (COIN) is a spatial data infrastructure (SDI) which provides an online network of resources to share, use and integrate information of geographic locations in North Canada. COIN incorporates semantic web technology that integrates, publishes and visualizes time series water data allowing users to access a multitude of datasets in order to compare the data and draw conclusions. COIN utilizes a number of standards from OGC (Open Geospatial Consortium) and W3C (Resource Description Framework, RDF, Web Ontology Language OWL, SPARQL query language for RDF) and GeoSPARQL for geospatial query). COIN benefits from generic ontologies transforming data into semantics, enriching data sets and making the data available and interoperable via WFS and WMS standards. These principles facilitate publication and exchange of data across the web, increasing transparency and interpretability. Through modernized data submission and retrieval we hope to break down the silos of data, allowing users to visualize time series water quality and hydrometric data from multiple sources to increase knowledge in relationship to impacts on Yukon water.

@inproceedings{ZHGB-W2GIS type = {workshop}, author = {Danielle Zi{\'{e}}belin and Kim Hobus and Philippe Genoud and Sylvain Bouveret}, title = {Heterogeneous Data Integration Using Web of Data Technologies}, booktitle = {Proceedings of the 15th International Symposium on Web and Wireless Geographical Information Systems ({W2GIS} 2017)}, url = {https://link.springer.com/chapter/10.1007/978-3-319-55998-8_3}, series = {Lecture Notes in Computer Science}, volume = {10181}, pages = {35--47}, year = {2017}, month = may, address = {Shanghai, China}, abstract = {The Coordinated Online Information Network (COIN) is a spatial data infrastructure (SDI) which provides an online network of resources to share, use and integrate information of geographic locations in North Canada. COIN incorporates semantic web technology that integrates, publishes and visualizes time series water data allowing users to access a multitude of datasets in order to compare the data and draw conclusions. COIN utilizes a number of standards from OGC (Open Geospatial Consortium) and W3C (Resource Description Framework, RDF, Web Ontology Language OWL, SPARQL query language for RDF) and GeoSPARQL for geospatial query). COIN benefits from generic ontologies transforming data into semantics, enriching data sets and making the data available and interoperable via WFS and WMS standards. These principles facilitate publication and exchange of data across the web, increasing transparency and interpretability. Through modernized data submission and retrieval we hope to break down the silos of data, allowing users to visualize time series water quality and hydrometric data from multiple sources to increase knowledge in relationship to impacts on Yukon water.} }

[SBG-MOMM17]Sales Fonteles, André, Bouveret, Sylvain and Gensel, Jérôme (2017). A programming framework for Spatial Crowdsourcing. In Proceedings of the 15th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2017, Salzbourg, Austria.

[Abstract]
[BibTeX]

Spatial crowdsourcing platforms (SCP) are systems that allow someone, or something, to publish spatial tasks in order to find suitable workforce to perform it. These tasks require people, often using mobile devices, to be at a given location in order to accomplish them. SCPs have been source of much interest for both academy and industry. For this reason, Doan argued in 2011 that the race was now on "toward building general crowdsourcing platforms that can be used to develop such systems quickly". Since then, not much has been done in this matter. More important, there is a gap between what is done in the industry and is proposed in the literature. We propose GENIUS-C, a framework to support the development of SCPs. This framework is based on a generic architecture previously proposed by Fonteles et al., 2016 and designed to bridge the gap between academy and industry. Among other things, GENIUS-C is meant to reduce time-to-market, development cost and effort and increase overall quality of SCPs. A case study SCP has been created using GENIUS-C in order to demonstrate its benefits and how it can be used in the developments of new SCPs.

@inproceedings{SBG-MOMM17, type = {workshop}, author = {Sales Fonteles, André and Sylvain Bouveret and Jérôme Gensel}, title = {A programming framework for Spatial Crowdsourcing}, booktitle = {Proceedings of the 15th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2017}, address = {Salzbourg, Austria}, month = {December}, year = 2017, abstract = {Spatial crowdsourcing platforms (SCP) are systems that allow someone, or something, to publish spatial tasks in order to find suitable workforce to perform it. These tasks require people, often using mobile devices, to be at a given location in order to accomplish them. SCPs have been source of much interest for both academy and industry. For this reason, Doan argued in 2011 that the race was now on "toward building general crowdsourcing platforms that can be used to develop such systems quickly". Since then, not much has been done in this matter. More important, there is a gap between what is done in the industry and is proposed in the literature. We propose GENIUS-C, a framework to support the development of SCPs. This framework is based on a generic architecture previously proposed by Fonteles et al., 2016 and designed to bridge the gap between academy and industry. Among other things, GENIUS-C is meant to reduce time-to-market, development cost and effort and increase overall quality of SCPs. A case study SCP has been created using GENIUS-C in order to demonstrate its benefits and how it can be used in the developments of new SCPs.} }

[BCDL-IJCAI17]Bouveret, Sylvain, Chevaleyre, Yann, Durand, François and Lang, Jérôme (2017). Voting by Sequential Elimination with few Voters. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI-17), Melbourne, Australia.

[Abstract]
[BibTeX]
[PDF]

We define a new class of low-communication voting rules, tailored for contexts with few voters and possibly many candidates. These rules are defined by a predefined sequence of voters: at each stage, the designated voter eliminates a candidate, and the last remaining candidate wins. We study deterministic and randomized versions of these rules. We first investigate their axiomatic properties. Then we focus on a subfamily of rules defined by "non-interleaved" sequences, for which we seek a sequence that best approximates the Borda rule under Impartial Culture. Finally, we apply our rules to randomly generated data.

@InProceedings{BCDL-IJCAI17, author = {Sylvain Bouveret and Yann Chevaleyre and François Durand and Jérôme Lang}, title = {Voting by Sequential Elimination with few Voters}, booktitle = {Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI-17)}, year = 2017, month = aug, url = {http://recherche.noiraudes.net/resources/papers/IJCAI17-sequences.pdf}, address = {Melbourne, Australia}, abstract = {We define a new class of low-communication voting rules, tailored for contexts with few voters and possibly many candidates. These rules are defined by a predefined sequence of voters: at each stage, the designated voter eliminates a candidate, and the last remaining candidate wins. We study deterministic and randomized versions of these rules. We first investigate their axiomatic properties. Then we focus on a subfamily of rules defined by "non-interleaved" sequences, for which we seek a sequence that best approximates the Borda rule under Impartial Culture. Finally, we apply our rules to randomly generated data.} }

[BCEIP-IJCAI17]Bouveret, Sylvain, Cechlárová, Katarína, Elkind, Edith, Igarashi, Ayumi and Peters, Dominik (2017). Fair Division of a Graph. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI-17), Melbourne, Australia.

[Abstract]
[BibTeX]
[PDF]

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.

@InProceedings{BCEIP-IJCAI17, author = {Sylvain Bouveret and Katarína Cechlárová and Edith Elkind and Ayumi Igarashi and Dominik Peters}, title = {Fair Division of a Graph}, booktitle = {Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI-17)}, year = 2017, month = aug, url = {http://recherche.noiraudes.net/resources/papers/IJCAI17-cakecutting.pdf}, address = {Melbourne, Australia}, abstract = {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.} }

[ABLM-AAAI17]Aziz, Haris, Bouveret, Sylvain, Lang, Jérôme and Mackenzie, Simon (2017). Complexity of Manipulating Sequential Allocation. In Proceedings of the 31st AAAI conference on Artificial Intelligence (AAAI'17), San Francisco, California, USA. AAAI Press.

[Abstract]
[BibTeX]
[PDF]

Sequential allocation is a simple allocation mechanism in which agents are given pre-specified turns in which they take one item among those that are still available. It has long been known that sequential allocation is not strategyproof. This raises the question of the complexity of computing a preference report that yields a higher utility than the truthful preference. We show that the problem is NP-complete for one manipulating agent with additive utilities and several non-manipulating agents. In doing so, we correct a wrong claim made in a previous paper. We then give two additional results. First, we present a polynomial-time algorithm for optimal manipulation when the manipulator has additive binary utilities. Second, we consider a stronger notion of manipulation whereby the untruthful outcome yields more utility than the truthful outcome for all utilities consistent with the ordinal preferences; for this notion, we show that a manipulation, if any, can be computed in polynomial time.

@InProceedings{ABLM-AAAI17, author = {Haris Aziz and Sylvain Bouveret and Jérôme Lang and Simon Mackenzie}, title = {Complexity of Manipulating Sequential Allocation}, booktitle = {Proceedings of the 31st AAAI conference on Artificial Intelligence (AAAI'17)}, year = 2017, publisher = {AAAI Press}, address = {San Francisco, California, USA}, url = {http://recherche.noiraudes.net/resources/papers/AAAI17.pdf}, abstract = {Sequential allocation is a simple allocation mechanism in which agents are given pre-specified turns in which they take one item among those that are still available. It has long been known that sequential allocation is not strategyproof. This raises the question of the complexity of computing a preference report that yields a higher utility than the truthful preference. We show that the problem is NP-complete for one manipulating agent with additive utilities and several non-manipulating agents. In doing so, we correct a wrong claim made in a previous paper. We then give two additional results. First, we present a polynomial-time algorithm for optimal manipulation when the manipulator has additive binary utilities. Second, we consider a stronger notion of manipulation whereby the untruthful outcome yields more utility than the truthful outcome for all utilities consistent with the ordinal preferences; for this notion, we show that a manipulation, if any, can be computed in polynomial time.} }

[B-CHAPTER-TRENDS17]Bouveret, Sylvain (2017). Social Choice on the Web. In Endriss, Ulle, editors, Trends in Computational Social Choice, : 387--402. Chapter 20.AI Access.

[Abstract]
[BibTeX]
[PDF]

In this chapter, we speak about the development and use of a web application dedicated to social choice, Whale. The chapter is intended to be a compilation of lessons learned from the users of this web application, rather than an extensive presentation of it. We see through specific use cases what concrete problems have been encountered during the development of this web application.

@InCollection{B-CHAPTER-TRENDS17, author = {Sylvain Bouveret}, title = {Social Choice on the Web}, editor = {Ulle Endriss}, booktitle = {Trends in Computational Social Choice}, chapter = {20}, pages = {387--402}, publisher = {AI Access}, url = {http://research.illc.uva.nl/COST-IC1205/BookDocs/Chapters/TrendsCOMSOC-20.pdf}, year = {2017}, abstract = {In this chapter, we speak about the development and use of a web application dedicated to social choice, Whale. The chapter is intended to be a compilation of lessons learned from the users of this web application, rather than an extensive presentation of it. We see through specific use cases what concrete problems have been encountered during the development of this web application.} }

[KBB-COMSOC16]Karanikolas, Nikos, Blanch, Renaud and Bouveret, Sylvain (2016). Edge-Compressed Majority Graph: Where Social Choice Meets Information Visualization. In Proceedings of the Sixth International Workshop on Computational Social Choice (COMSOC'16), Toulouse, France.

[Abstract]
[BibTeX]
[PDF]

Collective decisions are everywhere: choosing central or local governments, selecting a candidate to hire for an open position, choosing a restaurant to share a dinner with some friends are examples of collective decision making situations. Social Choice provides a lot of methods which can help people making a decision in such situations. However, the diversity of these voting procedures and the mathematical background necessary to understand them can be seen as obstacles to the use of these methods in everyday situations by laypersons. We claim that information visualization techniques can help a lot the democratization of social choice, by providing people with some easily interpretable information and, in the end, helping them making informed collective decisions. In this paper, we present the Edge-Compressed Majority Graph, a technique dedicated to the visualization of the majority graph of a preference profile. Using an insight-based evaluation method, we show that this technique gives better results in conveying information about the preferences than other classical visualization techniques.

@InProceedings{KBB-COMSOC16, type = {workshop}, author = {Nikos Karanikolas and Renaud Blanch and Sylvain Bouveret}, title = {Edge-Compressed Majority Graph: Where Social Choice Meets Information Visualization}, booktitle = {Proceedings of the Sixth International Workshop on Computational Social Choice (COMSOC'16)}, year = 2016, month = {June}, address = {Toulouse, France}, abstract = {Collective decisions are everywhere: choosing central or local governments, selecting a candidate to hire for an open position, choosing a restaurant to share a dinner with some friends are examples of collective decision making situations. Social Choice provides a lot of methods which can help people making a decision in such situations. However, the diversity of these voting procedures and the mathematical background necessary to understand them can be seen as obstacles to the use of these methods in everyday situations by laypersons. We claim that information visualization techniques can help a lot the democratization of social choice, by providing people with some easily interpretable information and, in the end, helping them making informed collective decisions. In this paper, we present the Edge-Compressed Majority Graph, a technique dedicated to the visualization of the majority graph of a preference profile. Using an insight-based evaluation method, we show that this technique gives better results in conveying information about the preferences than other classical visualization techniques.}, url = {https://www.irit.fr/COMSOC-2016/proceedings/KaranikolasEtAlCOMSOC2016.pdf} }

[BL-COMSOC16]Bouveret, Sylvain and Lemaître, Michel (2016). Efficiency and Sequenceability in Fair Division of Indivisible Goods with Additive Preferences. In Proceedings of the Sixth International Workshop on Computational Social Choice (COMSOC'16), Toulouse, France.

[Abstract]
[BibTeX]
[PDF]

In fair division of indivisible goods, using sequences of sincere choices (or picking sequences) is a natural way to allocate the objects. The idea is the following: at each stage, a designated agent picks one object among those that remain. This paper, restricted to the case where the agents have numerical additive preferences over objects, revisits to some extent the seminal paper by Brams and King (2005) which was specific to ordinal and linear order preferences over items. We point out similarities and differences with this latter context. In particular, we show that any Pareto-optimal allocation (under additive preferences) is sequenceable, but that the converse is not true anymore. This asymmetry leads naturally to the definition of a ``scale of efficiency'' having three steps: Pareto-optimality, sequenceability without Pareto-optimality, and non-sequenceability. Finally, we investigate the links between these efficiency properties and the ``scale of fairness'' we have described in an earlier work (Bouveret and Lemaître, 2015): we first show that an allocation can be envy-free and non-sequenceable, but that every competitive equilibrium with equal incomes is sequenceable. Then we experimentally explore the links between the scales of efficiency and fairness.

@InProceedings{BL-COMSOC16, type = {workshop}, author = {Sylvain Bouveret and Michel Lemaître}, title = {Efficiency and Sequenceability in Fair Division of Indivisible Goods with Additive Preferences}, booktitle = {Proceedings of the Sixth International Workshop on Computational Social Choice (COMSOC'16)}, year = 2016, month = {June}, address = {Toulouse, France}, abstract = {In fair division of indivisible goods, using sequences of sincere choices (or picking sequences) is a natural way to allocate the objects. The idea is the following: at each stage, a designated agent picks one object among those that remain. This paper, restricted to the case where the agents have numerical additive preferences over objects, revisits to some extent the seminal paper by Brams and King (2005) which was specific to ordinal and linear order preferences over items. We point out similarities and differences with this latter context. In particular, we show that any Pareto-optimal allocation (under additive preferences) is sequenceable, but that the converse is not true anymore. This asymmetry leads naturally to the definition of a ``scale of efficiency'' having three steps: Pareto-optimality, sequenceability without Pareto-optimality, and non-sequenceability. Finally, we investigate the links between these efficiency properties and the ``scale of fairness'' we have described in an earlier work (Bouveret and Lemaître, 2015): we first show that an allocation can be envy-free and non-sequenceable, but that every competitive equilibrium with equal incomes is sequenceable. Then we experimentally explore the links between the scales of efficiency and fairness.}, url = {https://www.irit.fr/COMSOC-2016/proceedings/BouveretLemaitreCOMSOC2016.pdf} }

[BBLNNR-JAAMAS16]Baumeister, Dorothea, Bouveret, Sylvain, Lang, Jérôme, Nguyen, Nhan-Tam, Nguyen, Trung Thanh, Rothe, Jörg and Saffidine, Abdallah (2016). Positional Scoring-Based Allocation of Indivisible Goods. In Autonomous Agents and Multi-Agent Systems, : 1--28.Springer US

[Abstract]
[BibTeX]
[PDF]

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 reports her preferences simply by ranking single goods. Similarly to positional scoring rules in voting, a scoring vector $s\; =\; (s$_{1}, … , 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 $\u2605$ such as, typically, $+$ or $min$. The rule associated with $s$ and $\u2605$ maps a profile to (one of) the allocation(s) maximizing social welfare. After defining this family of rules, and focusing on some key examples, we investigate some of the social-choice-theoretic properties of this family of rules, such as various kinds of monotonicity, and separability. Finally, we focus on the computation of winning allocations, and on their approximation: we show that for commonly used scoring vectors and aggregation functions this problem is NP-hard and we exhibit some tractable particular cases.

@article{BBLNNR-JAAMAS16, year = 2016, issn= {1573-7454}, doi = {10.1007/s10458-016-9340-x}, journal = {Autonomous Agents and Multi-Agent Systems}, title = {Positional Scoring-Based Allocation of Indivisible Goods}, url = {http://recherche.noiraudes.net/resources/papers/JAAMAS16.pdf}, publisher = {Springer US}, keywords = {Computational social choice; resource allocation; fair division; indivisible goods; preferences}, author = {Dorothea Baumeister and Sylvain Bouveret and Jérôme Lang and Nhan-Tam Nguyen and {Trung Thanh} Nguyen and Jörg Rothe and Abdallah Saffidine}, pages = {1--28}, abstract = {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 reports her preferences simply by ranking single goods. Similarly to positional scoring 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 to (one of) the allocation(s) maximizing social welfare. After defining this family of rules, and focusing on some key examples, we investigate some of the social-choice-theoretic properties of this family of rules, such as various kinds of monotonicity, and separability. Finally, we focus on the computation of winning allocations, and on their approximation: we show that for commonly used scoring vectors and aggregation functions this problem is NP-hard and we exhibit some tractable particular cases.} }

[BCM-CHAPTER-COMSOC16]Bouveret, Sylvain, Chevaleyre, Yann and Maudet, Nicolas (2016). Fair Allocation of Indivisible Goods. In Brandt, Felix, Conitzer, Vincent, Endriss, Ulle, Lang, Jérôme and Procaccia, Ariel D., editors, Handbook of Computational Social Choice, Chapter 12.Cambridge University Press.

[Abstract]
[BibTeX]
[URL]

This chapter deals with fair division of indivisible goods. The first part of the chapter is dedicated to preference representation for resource allocation problems. Then we introduce fairness and efficiency criteria and focus on the computational aspects of fair division, namely, complexity and algorithmic issues of the centralized computation of fair allocations. The final part of the chapter is dedicated to distributed protocols for fair division.

@InCollection{BCM-CHAPTER-COMSOC16, author = {Sylvain Bouveret and Yann Chevaleyre and Nicolas Maudet}, title = {Fair Allocation of Indivisible Goods}, booktitle = {Handbook of Computational Social Choice}, publisher = {Cambridge University Press}, url = {http://recherche.noiraudes.net/en/handbook.php}, year = 2016, editor = {Felix Brandt and Vincent Conitzer and Ulle Endriss and Jérôme Lang and Ariel D. Procaccia}, chapter = 12, abstract = {This chapter deals with fair division of indivisible goods. The first part of the chapter is dedicated to preference representation for resource allocation problems. Then we introduce fairness and efficiency criteria and focus on the computational aspects of fair division, namely, complexity and algorithmic issues of the centralized computation of fair allocations. The final part of the chapter is dedicated to distributed protocols for fair division.} }

[SBG-INFORSID15]Sales Fonteles, André, Bouveret, Sylvain and Gensel, Jérôme (2015). Recommandation opportuniste de trajectoires pour l'accomplissement de tâches dans les systèmes crowdsourcing. In Actes du XXXIIIème Congrès INFORSID, Biarritz, France.

[Abstract]
[BibTeX]

Les systèmes de marché Crowdsourcing (CMS) sont des plateformes qui permettent à quelqu'un de publier des tâches afin qu'elles soient accomplies par d'autres. Récemment, un type de CMS est apparu dans lequel des tâches spatio-temporelles doivent être accomplies par des personnes dans une fenêtre de temps et un lieu précis. Dans cet article, nous présentons le Problème de Recommandation de Trajectoires Utiles (PRTU), qui permet à une personne qui veut se déplacer d'accomplir des tâches spatio-temporelles pour lesquelles elle montre une grande affinité et/ou aptitude, sans compromettre son arrivée dans les temps à destination. Nous démontrons que le PRTU est NP-complet (dans sa version décisionnelle) et lui proposons un algorithme exact. En outre, nous proposons une architecture de référence pour aider dans l'emploi de la recommandation de ces trajectoires dans un CMS réel. Enfin, nos expérimentations montrent que l'algorithme proposé est une solution faisable pour les instances de PRTU ayant quelques centaines de tâches ou moins.

@inproceedings{SBG-INFORSID15, type = {confnat}, author = {Sales Fonteles, André and Sylvain Bouveret and Jérôme Gensel}, title = {Recommandation opportuniste de trajectoires pour l'accomplissement de tâches dans les systèmes crowdsourcing}, booktitle = {Actes du XXXIIIème Congrès INFORSID}, address = {Biarritz, France}, month = {May}, pages = {201--215}, year = {2015}, abstract = {Les systèmes de marché Crowdsourcing (CMS) sont des plateformes qui permettent à quelqu'un de publier des tâches afin qu'elles soient accomplies par d'autres. Récemment, un type de CMS est apparu dans lequel des tâches spatio-temporelles doivent être accomplies par des personnes dans une fenêtre de temps et un lieu précis. Dans cet article, nous présentons le Problème de Recommandation de Trajectoires Utiles (PRTU), qui permet à une personne qui veut se déplacer d'accomplir des tâches spatio-temporelles pour lesquelles elle montre une grande affinité et/ou aptitude, sans compromettre son arrivée dans les temps à destination. Nous démontrons que le PRTU est NP-complet (dans sa version décisionnelle) et lui proposons un algorithme exact. En outre, nous proposons une architecture de référence pour aider dans l'emploi de la recommandation de ces trajectoires dans un CMS réel. Enfin, nos expérimentations montrent que l'algorithme proposé est une solution faisable pour les instances de PRTU ayant quelques centaines de tâches ou moins.} }

[SBG-W2GIS15]Sales Fonteles, André, Bouveret, Sylvain and Gensel, Jérôme (2015). Opportunistic Trajectory Recommendation for Task Accomplishment in Crowdsourcing Systems. In Gensel, Jérôme and Tomko, Martin, editors, Proceedings of the 14th International Symposium on Web and Wireless Geographical Information Systems (W2GIS 2015), Grenoble, France.

[Abstract]
[BibTeX]

Crowdsourcing market systems (CMS) are platforms that enable one to publish tasks that others are intended to accomplished. Usually, these are systems where users, called workers, perform tasks using desktop computers. Recently, some CMS have appeared with spatiotemporal tasks that requires a worker to be at a given location within a given time window to be accomplished. In this paper, we introduce the trajectory recommendation problem (or TRP) where a CMS tries to find and recommend a trajectory for a mobile worker that allows him to accomplish tasks he has some affinity with without compromising his arrival in time at destination. We show that TRP is NP-hard and then propose an exact algorithm for solving it. Our experimentation proved that using our algorithm for recommending trajectories is a feasible solution when up to a few hundred tasks must be analyzed to find an optimal solution.

@inproceedings{SBG-W2GIS15, type = {workshop}, author = {Sales Fonteles, André and Sylvain Bouveret and Jérôme Gensel}, title = {Opportunistic Trajectory Recommendation for Task Accomplishment in Crowdsourcing Systems}, booktitle = {Proceedings of the 14th International Symposium on Web and Wireless Geographical Information Systems ({W2GIS} 2015)}, address = {Grenoble, France}, month = {May}, editor = {Jérôme Gensel and Martin Tomko}, series = {Lecture Notes in Computer Science}, pages = {178--190}, year = {2015}, abstract = {Crowdsourcing market systems (CMS) are platforms that enable one to publish tasks that others are intended to accomplished. Usually, these are systems where users, called workers, perform tasks using desktop computers. Recently, some CMS have appeared with spatiotemporal tasks that requires a worker to be at a given location within a given time window to be accomplished. In this paper, we introduce the trajectory recommendation problem (or TRP) where a CMS tries to find and recommend a trajectory for a mobile worker that allows him to accomplish tasks he has some affinity with without compromising his arrival in time at destination. We show that TRP is NP-hard and then propose an exact algorithm for solving it. Our experimentation proved that using our algorithm for recommending trajectories is a feasible solution when up to a few hundred tasks must be analyzed to find an optimal solution.} }

[SBG-MOMM15]Sales Fonteles, André, Bouveret, Sylvain and Gensel, Jérôme (2015). Heuristics for Task Recommendation in Spatiotemporal Crowdsourcing Systems. In Chen, Liming Luke, Steinbauer, Matthias, Khalil, Ismail and Anderst-Kotsis, Gabriele, editors, Proceedings of the 13th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2015, Brussels, Belgium.

[Abstract]
[BibTeX]

Crowdsourcing systems (CS) are platforms that enable a system or a user to publish tasks in order to be accomplished by others. Typically, a CS is a system where users, called workers, perform tasks using desktop computers. Recently, some CS have appeared with spatiotemporal tasks. Such tasks require a worker to be in a given location within a specific time-window to be accomplished. We propose and study here the usage of five heuristics for solving the NP-hard trajectory recommendation problem (TRP). In a TRP, the system recommends a trajectory to a worker that allows him to accomplish spatiotemporal tasks he has skill and/or affinity with, without exceeding his available time. Our experiments show that some of our heuristics are efficient alternatives for a heavy optimal approach providing trajectories with an average utility of about 60% of the optimal ones.

@inproceedings{SBG-MOMM15, type = {workshop}, author = {Sales Fonteles, André and Sylvain Bouveret and Jérôme Gensel}, editor = {Liming Luke Chen and Matthias Steinbauer and Ismail Khalil and Gabriele Anderst{-}Kotsis}, title = {Heuristics for Task Recommendation in Spatiotemporal Crowdsourcing Systems}, booktitle = {Proceedings of the 13th International Conference on Advances in Mobile Computing and Multimedia, MoMM 2015}, address = {Brussels, Belgium}, month = {December}, pages = {1--5}, year = 2015, abstract = {Crowdsourcing systems (CS) are platforms that enable a system or a user to publish tasks in order to be accomplished by others. Typically, a CS is a system where users, called workers, perform tasks using desktop computers. Recently, some CS have appeared with spatiotemporal tasks. Such tasks require a worker to be in a given location within a specific time-window to be accomplished. We propose and study here the usage of five heuristics for solving the NP-hard trajectory recommendation problem (TRP). In a TRP, the system recommends a trajectory to a worker that allows him to accomplish spatiotemporal tasks he has skill and/or affinity with, without exceeding his available time. Our experiments show that some of our heuristics are efficient alternatives for a heavy optimal approach providing trajectories with an average utility of about 60\% of the optimal ones.} }

[BL-JAAMAS15]Bouveret, Sylvain and Lemaître, Michel (2015). Characterizing conflicts in fair division of indivisible goods using a scale of criteria. In Autonomous Agents and Multi-Agent Systems, 30(2): 259--290.Springer US

[Abstract]
[BibTeX]
[PDF]

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: for a given instance of a resource allocation problem, the less conflicting the agents' preferences are, the more demanding criterion this instance is able to satisfy, and the more satisfactory the allocation can 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.

@article{BL-JAAMAS15, year = {2015}, issn = {1573-7454}, journal = {Autonomous Agents and Multi-Agent Systems}, doi = {10.1007/s10458-015-9287-3}, title = {Characterizing conflicts in fair division of indivisible goods using a scale of criteria}, url = {http://recherche.noiraudes.net/resources/papers/JAAMAS15.pdf}, publisher = {Springer US}, keywords = {Computational social choice; Resource allocation; Fair division; Indivisible goods; Preferences}, author = {Bouveret, Sylvain and Lemaître, Michel}, volume = {30}, number = {2}, pages = {259--290}, abstract = {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: for a given instance of a resource allocation problem, the less conflicting the agents' preferences are, the more demanding criterion this instance is able to satisfy, and the more satisfactory the allocation can 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.} }

[SBG-MOBIGIS14]Sales Fonteles, André, Bouveret, Sylvain and Gensel, Jérôme (2014). Towards matching improvement between spatio-temporal tasks and workers in mobile crowdsourcing market systems. In Proceedings of the Third ACM SIGSPATIAL International Workshop on Mobile Geographic Information Systems (MobiGIS 2014), Dallas / Forth Worth, Texas, USA.

[Abstract]
[BibTeX]

Crowdsourcing market systems (CMS) are platforms that enable one to publish tasks that others are intended to accomplished. Usually, these are systems where users, called workers, perform tasks using desktop computers. Recently, mobile CMSs have appeared with tasks that exploit the mobility and the location of workers. For example, if a third party system requires a picture of a given place, it may publish a task asking for some worker to go there, take this picture and upload it. One problem of CMSs is that the more tasks they have, the harder it is for workers to find and choose one they are interested in. Besides, workers who accomplish tasks may have no particular experience and consequently provide bad results for tasks. In order to improve the matching between workers and spatio-temporal tasks in mobile CMSs, we propose a conceptual framework that consists of two mechanisms. One considers the requirements of a task for selecting suitable workers, while the other recommends tasks for a worker according to his preferences and skills. As a result, workers spend less time searching tasks, more working on it, providing results with higher quality.

@InProceedings{SBG-MOBIGIS14, type = {workshop}, author = {Sales Fonteles, André and Sylvain Bouveret and Jérôme Gensel}, title = {Towards matching improvement between spatio-temporal tasks and workers in mobile crowdsourcing market systems}, booktitle = {Proceedings of the Third {ACM} {SIGSPATIAL} International Workshop on Mobile Geographic Information Systems (MobiGIS 2014)}, year = 2014, month = {November}, address = {Dallas / Forth Worth, Texas, USA}, abstract = {Crowdsourcing market systems (CMS) are platforms that enable one to publish tasks that others are intended to accomplished. Usually, these are systems where users, called workers, perform tasks using desktop computers. Recently, mobile CMSs have appeared with tasks that exploit the mobility and the location of workers. For example, if a third party system requires a picture of a given place, it may publish a task asking for some worker to go there, take this picture and upload it. One problem of CMSs is that the more tasks they have, the harder it is for workers to find and choose one they are interested in. Besides, workers who accomplish tasks may have no particular experience and consequently provide bad results for tasks. In order to improve the matching between workers and spatio-temporal tasks in mobile CMSs, we propose a conceptual framework that consists of two mechanisms. One considers the requirements of a task for selecting suitable workers, while the other recommends tasks for a worker according to his preferences and skills. As a result, workers spend less time searching tasks, more working on it, providing results with higher quality.} }

[SGB-SAGEO14]Sales Fonteles, André, Gensel, Jérôme and Bouveret, Sylvain (2014). Améliorer l'appariement entre tâches et exécutants dans les Systèmes de Marché Participatifs Mobiles. In Actes de la 11ème conférence francophone en géomatique et analyse spatiale (SAGEO'2014), Grenoble, France.

[Abstract]
[BibTeX]

Les Systèmes de Marché Participatifs ou Crowdsourcing Market Systems (CMS) sont des plateformes qui permettent à des utilisateurs, appelés commanditaires, de soumettre des tâches de tout ordre qui pourront être effectuées par d'autres utilisateurs, appelés exécutants, gratuitement ou moyennant une récompense. Récemment sont apparus les CMS mobiles dont la particularité est que les tâches exploitent la mobilité et la localisation des exécutants. Un problème des CMS est que plus les tâches sont nombreuses, plus il est difficile pour les exécutants potentiels de trouver la tâche qu'ils souhaitent réaliser. En outre, les exécutants n'ont souvent pas de compétence particulière et peuvent donc réaliser des tâches de façon non satisfaisante pour les commanditaires. Nous proposons un cadre conceptuel, composé de deux mécanismes, pour améliorer l'adéquation entre les exécutants mobiles et les tâches géo-localisées dans les CMS mobiles. L'un tient compte des exigences formulées par le commanditaire pour chaque tâche afin d'améliorer la sélection des exécutants les plus compétents ; l'autre recommande des tâches à un exécutant en prenant en compte ses préférences, ainsi que son contexte spatio-temporel. Le cadre conceptuel proposé permet aux exécutants de passer moins de temps à chercher des tâches qui leur conviennent, et de se consacrer davantage à leur réalisation, améliorant globalement l'efficacité des CMS mobiles.

@InProceedings{SGB-SAGEO14, type = {confnat}, author = {Sales Fonteles, André and Jérôme Gensel and Sylvain Bouveret}, title = {Améliorer l'appariement entre tâches et exécutants dans les Systèmes de Marché Participatifs Mobiles}, booktitle = {Actes de la 11ème conférence francophone en géomatique et analyse spatiale (SAGEO'2014)}, year = 2014, month = {November}, address = {Grenoble, France}, abstract = {Les Systèmes de Marché Participatifs ou Crowdsourcing Market Systems (CMS) sont des plateformes qui permettent à des utilisateurs, appelés commanditaires, de soumettre des tâches de tout ordre qui pourront être effectuées par d'autres utilisateurs, appelés exécutants, gratuitement ou moyennant une récompense. Récemment sont apparus les CMS mobiles dont la particularité est que les tâches exploitent la mobilité et la localisation des exécutants. Un problème des CMS est que plus les tâches sont nombreuses, plus il est difficile pour les exécutants potentiels de trouver la tâche qu'ils souhaitent réaliser. En outre, les exécutants n'ont souvent pas de compétence particulière et peuvent donc réaliser des tâches de façon non satisfaisante pour les commanditaires. Nous proposons un cadre conceptuel, composé de deux mécanismes, pour améliorer l'adéquation entre les exécutants mobiles et les tâches géo-localisées dans les CMS mobiles. L'un tient compte des exigences formulées par le commanditaire pour chaque tâche afin d'améliorer la sélection des exécutants les plus compétents ; l'autre recommande des tâches à un exécutant en prenant en compte ses préférences, ainsi que son contexte spatio-temporel. Le cadre conceptuel proposé permet aux exécutants de passer moins de temps à chercher des tâches qui leur conviennent, et de se consacrer davantage à leur réalisation, améliorant globalement l'efficacité des CMS mobiles.} }

[BL-COMSOC14]Bouveret, Sylvain and Lang, Jérôme (2014). Manipulating picking sequences. In Proceedings of the Fifth International Workshop on Computational Social Choice (COMSOC'14), Pittsburgh, Pennsylvania.

[Abstract]
[BibTeX]
[PDF]
[Long version (PDF)]

Picking sequences are a natural way of allocating indivisible items to agents in a decentralized manner: at each stage, a designated agent chooses an item among those that remain available. We address the computational issues of the manipulation of picking sequences by an agent or a coalition of agents. We show that a single agent can compute an optimal manipulation in polynomial time. Then we consider several notions of coalitional manipulation; for one of these notions, we show that computing an optimal manipulation is easy. We temper these results by giving a nontrivial upper bound on the impact of manipulation on the loss of social welfare.

@InProceedings{BL-COMSOC14, type = {workshop}, author = {Sylvain Bouveret and Jérôme Lang}, title = {Manipulating picking sequences}, booktitle = {Proceedings of the Fifth International Workshop on Computational Social Choice (COMSOC'14)}, year = 2014, month = {June}, address = {Pittsburgh, Pennsylvania}, abstract = {Picking sequences are a natural way of allocating indivisible items to agents in a decentralized manner: at each stage, a designated agent chooses an item among those that remain available. We address the computational issues of the manipulation of picking sequences by an agent or a coalition of agents. We show that a single agent can compute an optimal manipulation in polynomial time. Then we consider several notions of coalitional manipulation; for one of these notions, we show that computing an optimal manipulation is easy. We temper these results by giving a nontrivial upper bound on the impact of manipulation on the loss of social welfare.}, url = {http://recherche.noiraudes.net/resources/papers/COMSOC14.pdf}, urlfull = {http://recherche.noiraudes.net/resources/papers/ECAI14-full.pdf} }

[BL-ECAI14]Bouveret, Sylvain and Lang, Jérôme (2014). Manipulating picking sequences. In Proceedings of the 21st European Conference on Artificial Intelligence (ECAI'14), Prague, Czech Republic. IOS Press.

[Abstract]
[BibTeX]
[PDF]
[Long version (PDF)]

Picking sequences are a natural way of allocating indivisible items to agents in a decentralized manner: at each stage, a designated agent chooses an item among those that remain available. We address the computational issues of the manipulation of picking sequences by an agent or a coalition of agents. We show that a single agent can compute an optimal manipulation in polynomial time. Then we consider several notions of coalitional manipulation; for one of these notions, we show that computing an optimal manipulation is easy. We temper these results by giving a nontrivial upper bound on the impact of manipulation on the loss of social welfare.

@InProceedings{BL-ECAI14, author = {Sylvain Bouveret and Jérôme Lang}, title = {Manipulating picking sequences}, booktitle = {Proceedings of the 21st European Conference on Artificial Intelligence (ECAI'14)}, year = 2014, month = {August}, address = {Prague, Czech Republic}, publisher = {{IOS} Press}, abstract = {Picking sequences are a natural way of allocating indivisible items to agents in a decentralized manner: at each stage, a designated agent chooses an item among those that remain available. We address the computational issues of the manipulation of picking sequences by an agent or a coalition of agents. We show that a single agent can compute an optimal manipulation in polynomial time. Then we consider several notions of coalitional manipulation; for one of these notions, we show that computing an optimal manipulation is easy. We temper these results by giving a nontrivial upper bound on the impact of manipulation on the loss of social welfare.}, url = {http://recherche.noiraudes.net/resources/papers/ECAI14.pdf}, urlfull = {http://recherche.noiraudes.net/resources/papers/ECAI14-full.pdf} }

[BL-AAMAS14]Bouveret, Sylvain and Lemaître, Michel (2014). Characterizing Conflicts in Fair Division of Indivisible Goods Using a Scale of Criteria. In Proceedings of the 13th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS'14), Paris, France. ACM. Runner up for best paper award.

[Abstract]
[BibTeX]
[PDF]
[Long version (PDF)]

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.

@InProceedings{BL-AAMAS14, author = {Sylvain Bouveret and Michel Lemaître}, title = {Characterizing Conflicts in Fair Division of Indivisible Goods Using a Scale of Criteria}, booktitle = {Proceedings of the 13th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS'14)}, year = 2014, address = {Paris, France}, month = {May}, publisher = {ACM}, abstract = {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.}, url = {http://recherche.noiraudes.net/resources/papers/AAMAS14.pdf}, urlfull = {http://recherche.noiraudes.net/resources/papers/AAMAS14-full.pdf}, note = {Runner up for best paper award} }

[BBLNNR-COMSOC14]Baumeister, Dorothea, Bouveret, Sylvain, Lang, Jérôme, Nguyen, Nhan-Tam, Nguyen, Trung Thanh, Rothe, Jörg and Saffidine, Abdallah (2014). Scoring Rules for the Allocation of Indivisible Goods. In Proceedings of the Fifth International Workshop on Computational Social Choice (COMSOC'14), Pittsburgh, Pennsylvania.

[Abstract]
[BibTeX]
[PDF]

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 rules in voting, a scoring vector $s\; =\; (s$_{1}, … , 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 $\u2605$ such as, typically, $+$ or $min$. The rule associated with $s$ and $\u2605$ maps a profile to (one of) the allocation(s) maximizing social welfare. After defining this family of rules, and focusing on some key examples, we investigate some of the social-choice-theoretic properties of this family of rules, such as various kinds of monotonicity, separability, envy-freeness, and Pareto efficiency.

@InProceedings{BBLNNR-COMSOC14, type = {workshop}, author = {Dorothea Baumeister and Sylvain Bouveret and Jérôme Lang and Nhan-Tam Nguyen and {Trung Thanh} Nguyen and Jörg Rothe and Abdallah Saffidine}, title = {Scoring Rules for the Allocation of Indivisible Goods}, booktitle = {Proceedings of the Fifth International Workshop on Computational Social Choice (COMSOC'14)}, year = 2014, month = {June}, address = {Pittsburgh, Pennsylvania}, abstract = {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 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 to (one of) the allocation(s) maximizing social welfare. After defining this family of rules, and focusing on some key examples, we investigate some of the social-choice-theoretic properties of this family of rules, such as various kinds of monotonicity, separability, envy-freeness, and Pareto efficiency.}, url = {http://recherche.noiraudes.net/resources/papers/COMSOC14-2.pdf} }

[BBLNNR-ECAI14]Baumeister, Dorothea, Bouveret, Sylvain, Lang, Jérôme, Nguyen, Nhan-Tam, Nguyen, Trung Thanh and Rothe, Jörg (2014). Scoring Rules for the Allocation of Indivisible Goods. In Proceedings of the 21st European Conference on Artificial Intelligence (ECAI'14), Prague, Czech Republic. IOS Press.

[Abstract]
[BibTeX]
[PDF]

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 rules in voting, a scoring vector $s\; =\; (s$_{1}, … , 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 $\u2605$ such as, typically, $+$ or $min$. The rule associated with $s$ and $\u2605$ maps a profile to (one of) the allocation(s) maximizing social welfare. After defining this family of rules, and focusing on some key examples, we investigate some of the social-choice-theoretic properties of this family of rules, such as various kinds of monotonicity, separability, envy-freeness, and Pareto efficiency.

@InProceedings{BBLNNR-ECAI14, author = {Dorothea Baumeister and Sylvain Bouveret and Jérôme Lang and Nhan-Tam Nguyen and {Trung Thanh} Nguyen and Jörg Rothe}, title = {Scoring Rules for the Allocation of Indivisible Goods}, booktitle = {Proceedings of the 21st European Conference on Artificial Intelligence (ECAI'14)}, year = 2014, month = {August}, address = {Prague, Czech Republic}, publisher = {{IOS} Press}, abstract = {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 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 to (one of) the allocation(s) maximizing social welfare. After defining this family of rules, and focusing on some key examples, we investigate some of the social-choice-theoretic properties of this family of rules, such as various kinds of monotonicity, separability, envy-freeness, and Pareto efficiency.}, url = {http://recherche.noiraudes.net/resources/papers/ECAI14-2.pdf} }

[BLL-CHAPTER-IA14]Bouveret, Sylvain, Lang, Jérôme and Lemaître, Michel (2014). Systèmes Multiagents : Décision Collective. In Marquis, Pierre, Papini, Odile and Prade, Henri, editors, Panorama de l'Intelligence Artificielle, volume 1, Représentation des Connaissances et Formalisation des Raisonnements. Chapter 15.Cépaduès.

[Abstract]
[BibTeX]

Ce chapitre présente deux principaux modèles de la décision collective (multi-agents) : le modèle de base qualitatif (ordinal) et le modèle qualitatif utilitariste (numérique). Trois problèmes emblématiques de la décision collective sont ensuite exposés : le vote ; le partage de biens ou de ressources ; et enfin les enchères.

@InCollection{BLL-CHAPTER-IA14, author = {Sylvain Bouveret and Jérôme Lang and Michel Lemaître}, title = {Systèmes Multiagents : Décision Collective}, booktitle = {Panorama de l'Intelligence Artificielle}, publisher = {Cépaduès}, year = 2014, editor = {Pierre Marquis and Odile Papini and Henri Prade}, volume = {1, Représentation des Connaissances et Formalisation des Raisonnements}, chapter = 15, abstract = {Ce chapitre présente deux principaux modèles de la décision collective (multi-agents) : le modèle de base qualitatif (ordinal) et le modèle qualitatif utilitariste (numérique). Trois problèmes emblématiques de la décision collective sont ensuite exposés : le vote ; le partage de biens ou de ressources ; et enfin les enchères.} }

[BL-MFI13]Bouveret, Sylvain and Lemaître, Michel (2013). Mon partage sera-t-il conflictuel ? Une échelle de propriétés pour la caractérisation d'instances de partage de biens indivisibles. In Actes des huitièmes journées francophones Modèles Formels de l'Interaction (MFI'13), Lille, France.

[Abstract]
[BibTeX]
[PDF]

À partir d'un modèle simple de problème de partage de biens indivisibles avec préférences additives, nous montrons comment une série de cinq propriétés pouvant définir l'équité d'un partage sont connectées entre elles, formant une échelle d'exigences croissantes. Cette échelle permet de caractériser la conflictualité d'une instance de problème de partage : le degré de non-conflit se reflète dans la plus exigeante des propriétés que peut satisfaire un partage de cette instance. Des résultats de complexité théorique concernant ces propriétés sont établis. Le modèle est élargi vers des préférences $k$-additives.

@InProceedings{BL-MFI13, type = {confnat}, author = {Sylvain Bouveret and Michel Lemaître}, title = {Mon partage sera-t-il conflictuel ? Une échelle de propriétés pour la caractérisation d'instances de partage de biens indivisibles}, booktitle = {Actes des huitièmes journées francophones Modèles Formels de l'Interaction (MFI'13)}, year = 2013, address = {Lille, France}, month = {juillet}, abstract = {À partir d'un modèle simple de problème de partage de biens indivisibles avec préférences additives, nous montrons comment une série de cinq propriétés pouvant définir l'équité d'un partage sont connectées entre elles, formant une échelle d'exigences croissantes. Cette échelle permet de caractériser la conflictualité d'une instance de problème de partage : le degré de non-conflit se reflète dans la plus exigeante des propriétés que peut satisfaire un partage de cette instance. Des résultats de complexité théorique concernant ces propriétés sont établis. Le modèle est élargi vers des préférences $k$-additives.}, url = {http://recherche.noiraudes.net/resources/papers/MFI13.pdf}, }

[BBLNRS-EUMAS13]Baumeister, Dorothea, Bouveret, Sylvain, Lang, Jérôme, Nguyen, Trung Thanh, Rothe, Jörg and Saffidine, Abdallah (2013). Positional Scoring Rules for the Allocation of Indivisible Goods. In Proceedings of the 11th European Workshop on Multi-Agent Systems (EUMAS'13), Toulouse, France.

[Abstract]
[BibTeX]
[PDF]

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}, … , 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 $\u2605$ such as, typically, $+$ or $min$. The rule associated with $s$ and $\u2605$ 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.

@InProceedings{BBLNRS-EUMAS13, type = {workshop}, author = {Dorothea Baumeister and Sylvain Bouveret and Jérôme Lang and {Trung Thanh} Nguyen and Jörg Rothe and Abdallah Saffidine}, title = {Positional Scoring Rules for the Allocation of Indivisible Goods}, booktitle = {Proceedings of the 11th European Workshop on Multi-Agent Systems (EUMAS'13)}, year = 2013, address = {Toulouse, France}, month = {December}, abstract = {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. }, url = {http://recherche.noiraudes.net/resources/papers/EUMAS13.pdf}, }

[LBL-ECAI12]Lumet, Charles, Bouveret, Sylvain and 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.

[Abstract]
[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, address = {Montpellier, France}, month = {August}, publisher = {{IOS} Press}, 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} }

[LBL-MFI11]Lumet, Charles, Bouveret, Sylvain and 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.

[Abstract]
[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, address = {Rouen, France}, 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 and 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.

[Abstract]
[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, address = {Barcelona, Spain}, 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 and 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.

[Abstract]
[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, address = {Hannover, Germany}, 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/HOTSWUP11.pdf} }

[BL-IJCAI11]Bouveret, Sylvain and 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.

[Abstract]
[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, address = {Barcelona, Spain}, 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}, }

[BEL-COMSOC10]Bouveret, Sylvain, Endriss, Ulle and 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.

[Abstract]
[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, address = {Düsseldorf, Germany}, 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 and 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.

[Abstract]
[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, address = {Lisbon, Portugal}, 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} }

[KBKZ-ADT09]Keijzer, Bart, Bouveret, Sylvain, Klos, Tomas and 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.

[Abstract]
[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 $_{2}^{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} }

[BEL-IJCAI09]Bouveret, Sylvain, Endriss, Ulle and 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, USA.

[Abstract]
[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, address = {Pasadena, California, USA}, 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://www.ijcai.org/Proceedings/09/Papers/022.pdf} }

[BL-AIJ09]Bouveret, Sylvain and Lemaître, Michel (2009). Computing leximin-optimal solutions in constraint networks. In Artificial Intelligence, 173(2): 343-364.

[Abstract]
[BibTeX]
[URL]

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.} }

[BL-JAIR08]Bouveret, Sylvain and 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.

[Abstract]
[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.} }

[BL-IJCAI07]Bouveret, Sylvain and Lemaître, Michel (2007). New Constraint Programming Approaches for the Computation of Leximin-Optimal Solutions in Constraint Networks. In Veloso, Manuela M., editors, Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI'07), Hyderabad, India.

[Abstract]
[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}, address = {Hyderabad, India}, pages = {62-67}, url = {http://www.ijcai.org/Proceedings/07/Papers/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 and Lemaître, Michel (2007). Fonctions d'utilité collective avec droits exogènes inégaux. In Paschos, Vangelis and Roy, Bernard, editors, Actes des cinquièmes journées francophones Modèles Formels de l'Interaction (MFI'07), Paris, France. Université Paris IX Dauphine.

[Abstract]
[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}, 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.}, }

[BL-JFPC06]Bouveret, Sylvain and Lemaître, Michel (2006). Un algorithme de programmation par contraintes pour la recherche d'allocations leximin-optimales. In AFPC, editors, Actes des deuxièmes Journées Francophones de Programmation par Contraintes (JFPC'06), Nîmes, France.

[Abstract]
[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}, 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.}, }

[BL-COMSOC06]Bouveret, Sylvain and Lemaître, Michel (2006). Finding leximin-optimal solutions using constraint programming: new algorithms and their application to combinatorial auctions. In Endriss, Ulle and Lang, Jérôme, editors, Proceedings of the 1st International Workshop on Computational Social Choice (COMSOC'06), ILLC, University of Amsterdam.

[Abstract]
[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 and Lemaître, Michel (2006). Comparison of two constraint programming algorithms for computing leximin-optimal allocations. In Prestwich, Steven and Hnich, Brahim, editors, Proceedings the workshop on Modelling and Solving Problems with Constraints, ECAI'06, Riva del Garda, Italy.

[Abstract]
[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.}, }

[BFLL-MFI05]Bouveret, Sylvain, Fargier, Hélène, Lang, Jérôme and 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 and Mouaddib, Abdel-Illah, editors, Actes des troisièmes journées francophones Modèles Formels de l'Interaction (MFI'05), Caen, France. Cépaduès Éditions.

[BL-IJCAI05]Bouveret, Sylvain and Lang, Jérôme (2005). Efficiency and envy-freeness in fair division of indivisible goods: logical representation and complexity. In Kaelbling, Leslie Pack and Saffiotti, Alessandro, editors, Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI'05), Edinburgh, Scotland. Professional Book Center.

[Abstract]
[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)}, address = {Edinburgh, Scotland}, month = {July}, publisher = {Professional Book Center}, year = {2005}, url = {http://www.ijcai.org/Proceedings/05/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 and 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. and Wooldridge, Michael, editors, 4rd International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS'05), Utrecht, The Netherlands. ACM. (short paper).

[Abstract]
[BibTeX]
[URL]

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.} }

Last modified: Thu Jun 5 08:58:39 CEST 2014

Click here if you want to do not want your information to be collected.