Sylvain Bouveret

AAMAS Conference 2026 Conference Paper

Computational Social Choice: Research & Development

• Dorothea Baumeister
• Ratip Emin Berker
• Niclas Boehmer
• Sylvain Bouveret
• Andreas Darmann
• Piotr Faliszewski
• Martin Lackner
• Jérôme Lang

Computational social choice (COMSOC) studies principled ways to aggregate conflicting individual preferences into collective decisions. In this paper, we call for an increased effort towards Computational Social Choice: Research & Development (COMSOC-R&D), a problem-driven research agenda that explicitly aims to design, implement, and test collective decision-making systems in the real world. We articulate the defining features of COMSOC-R&D, argue for its value, and discuss various roadblocks and possible solutions.

IJCAI Conference 2025 Conference Paper

Constrained Serial Dictatorships Can Be Fair

• Sylvain Bouveret
• Hugo Gilbert
• Jérôme Lang
• Guillaume Méroué

When allocating indivisible items to agents, it is known that the only strategyproof mechanisms that satisfy a set of rather mild conditions are constrained serial dictatorships: given a fixed order over agents, at each step the designated agent chooses a given number of items (depending on her position in the sequence). Agents who come earlier in the sequence have a larger choice of items; however, this advantage can be compensated by a higher number of items received by those who come later. How to balance priority in the sequence and number of items received is a nontrivial question. We use a previous model, parameterized by a mapping from ranks to scores, a social welfare functional, and a distribution over preference profiles. For several meaningful choices of parameters, we show that the optimal sequence can be computed exactly in polynomial time or approximated using sampling. Our results hold for several probabilistic models on preference profiles, with an emphasis on the Plackett-Luce model. We conclude with experimental results showing how the optimal sequence is impacted by various parameters.

AAMAS Conference 2023 Conference Paper

Representing and Reasoning about Auctions

• Munyque Mittelmann
• Laurent Perrussel
• Sylvain Bouveret

In this paper, we propose a framework for representing and reasoning about auction-based protocols. Such a framework is of interest for building digital marketplaces based on auctions and should fulfill two requirements: (i) it should enable bidders to express their preferences over combinations of items and (ii) it should allow the mechanism designer to describe the rules governing the market, namely the legality of bids, the allocative choice, and the payment rule. To do so, we define a logical language in the spirit of the Game Description Language, namely Auction Description Language with a set of functions FB (ADL[FB]). ADL[FB] is expressive enough to represent different kinds of protocols and enables reasoning about auction properties, including playability, termination, and budget-balance. We also study the complexity of model-checking ADL[FB].

JAIR Journal 2022 Journal Article

Fair in the Eyes of Others

• Parham Shams
• Aurélie Beynier
• Sylvain Bouveret
• Nicolas Maudet

Envy-freeness is a widely studied notion in resource allocation, capturing some aspects of fairness. The notion of envy being inherently subjective though, it might be the case that an agent envies another agent, but that from the other agents' point of view, she has no reason to do so. The difficulty here is to define the notion of objectivity, since no ground-truth can properly serve as a basis of this definition. A natural approach is to consider the judgement of the other agents as a proxy for objectivity. Building on previous work by Parijs (who introduced "unanimous envy") we propose the notion of approval envy: an agent ai experiences approval envy towards aj if she is envious of aj, and sufficiently many agents agree that this should be the case, from their own perspectives. Another thoroughly studied notion in resource allocation is proportionality. The same variant can be studied, opening natural questions regarding the links between these two notions. We exhibit several properties of these notions. Computing the minimal threshold guaranteeing approval envy and approval non-proportionality clearly inherits well-known intractable results from envy-freeness and proportionality, but (i) we identify some tractable cases such as house allocation; and (ii) we provide a general method based on a mixed integer programming encoding of the problem, which proves to be efficient in practice. This allows us in particular to show experimentally that existence of such allocations, with a rather small threshold, is very often observed.

JAAMAS Journal 2022 Journal Article

Representing and reasoning about auctions

• Munyque Mittelmann
• Sylvain Bouveret
• Laurent Perrussel

Abstract The goal of this paper is to propose a framework for representing and reasoning about the rules of auction-based protocols. Such a framework is of interest for building digital marketplaces based on this type of mechanism. Hence the framework should fulfill two requirements: (i) it should enable bidders to express their preferences over combinations of items and (ii) it should allow the mechanism designer to describe the rules governing the market, namely the legality of bids, the allocative choice, and the payment rule. To do so, we define a logical language in the spirit of the Game Description Language, namely Auction Description Language with a set of functions \(\mathcal {F}_{\mathcal {B}}\) ( ADL \([\mathcal {F}_{\mathcal {B}}]\) ). ADL \([\mathcal {F}_{\mathcal {B}}]\) is the first language for describing auctions in a logical framework. With our approach, each stage in a protocol is seen as an independent direct revelation mechanism. Our contribution is three-fold: first, we illustrate the general dimension by representing different kinds of protocols. Second, we show how this machine-processable language enables reasoning about auction properties, including playability, termination, and classical conditions from mechanism design (e. g. , budget-balance and individual rationality). Finally, we develop a model-checking algorithm for ADL \([\mathcal {F}_{\mathcal {B}}]\), with complexity in PTIME when the functions in \(\mathcal {F}_{\mathcal {B}}\) can be computed in polynomial time.

AAMAS Conference 2021 Conference Paper

A General Framework for the Logical Representation of Combinatorial Exchange Protocols

• Munyque Mittelmann
• Sylvain Bouveret
• Laurent Perrussel

The goal of this work is to propose a framework for representing and reasoning about the rules governing a combinatorial exchange. Such a framework is at first interest as long as we want to build up digital marketplaces based on auction, a widely used mechanism for automated transactions. Hence the framework should fulfill two requirements: (i) it should enable bidders to express their bids on combinations of goods and (ii) it should allow describing the rules governing some market, namely the legal bids, the allocation and payment rules. To do so, we define a logical language in the spirit of the Game Description Language: the Combinatorial Exchange Description Language is the first language for describing combinatorial exchange in a logical framework. The contribution is two-fold: first, we illustrate the general dimension by representing different kinds of protocols, and second, we show how to reason about auction properties in this machine-processable language.

ECAI Conference 2020 Conference Paper

Fair in the Eyes of Others

• Parham Shams
• Aurélie Beynier
• Sylvain Bouveret
• Nicolas Maudet

Envy-freeness is a widely studied notion in resource allocation, capturing some aspects of fairness. The notion of envy being inherently subjective though, it might be the case that an agent envies another agent, but that she objectively has no reason to do so. The difficulty here is to define the notion of objectivity, since no ground-truth can properly serve as a basis of this definition. A natural approach is to consider the judgement of the other agents as a proxy for objectivity. Building on previous work by Parijs (who introduced “unanimous envy”) we propose the notion of approval envy: an agent ai experiences approval envy towards aj if she is envious of aj, and sufficiently many agents agree that this should be the case, from their own perspectives. Some interesting properties of this notion are put forward. Computing the minimal threshold guaranteeing approval envy clearly inherits well-known intractable results from envy-freeness, but (i) we identify some tractable cases such as house allocation; and (ii) we provide a general method based on a mixed integer programming encoding of the problem, which proves to be efficient in practice. This allows us in particular to show experimentally that existence of such allocations, with a rather small threshold, is very often observed.

JAAMAS Journal 2019 Journal Article

Chore division on a graph

• Sylvain Bouveret
• Katarína Cechlárová
• Julien Lesca

Abstract The paper considers fair allocation of indivisible nondisposable items that generate disutility (chores). We assume that these items are placed in the vertices of a graph and each agent’s share has to form a connected subgraph of this graph. Although a similar model has been investigated before for goods, we show that the goods and chores settings are inherently different. In particular, it is impossible to derive the solution of the chores instance from the solution of its naturally associated fair division instance. We consider three common fair division solution concepts, namely proportionality, envy-freeness and equitability, and two individual disutility aggregation functions: additive and maximum based. We show that deciding the existence of a fair allocation is hard even if the underlying graph is a path or a star. We also present some efficiently solvable special cases for these graph topologies.

AAMAS Conference 2019 Conference Paper

Efficiency, Sequenceability and Deal-Optimality in Fair Division of Indivisible Goods

• Aurélie Beynier
• Sylvain Bouveret
• Michel Lemaître
• Nicolas Maudet
• Simon Rey
• Parham Shams

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 as follows: at each stage, a designated agent picks one object among those that remain. Another intuitive way to obtain an allocation is to give objects to agents in the first place, and to let agents exchange them as long as such “deals” are beneficial. This paper investigates these notions, when agents have additive preferences over objects, and unveils surprising connections between them, and with other efficiency and fairness notions. In particular, we show that an allocation is sequenceable if and only if it is optimal for a certain type of deals, namely cycle deals involving a single object. Furthermore, any Pareto-optimal allocation is sequenceable, but not the converse. Regarding fairness, we show that an allocation can be envy-free and non-sequenceable, but that every competitive equilibrium with equal incomes is sequenceable. To complete the picture, we show how some domain restrictions may affect the relations between these notions. Finally, we experimentally explore the links between the scales of efficiency and fairness.

AAAI Conference 2018 Conference Paper

Knowledge, Fairness, and Social Constraints

• Haris Aziz
• Sylvain Bouveret
• Ioannis Caragiannis
• Ira Giagkousi
• Jérôme Lang

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.

AAAI Conference 2017 Conference Paper

Complexity of Manipulating Sequential Allocation

• Haris Aziz
• Sylvain Bouveret
• JŽr™me Lang
• Simon Mackenzie

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

IJCAI Conference 2017 Conference Paper

Fair Division of a Graph

• Sylvain Bouveret
• Katarína Cechlárová
• Edith Elkind
• Ayumi Igarashi
• Dominik Peters

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

IJCAI Conference 2017 Conference Paper

Voting by sequential elimination with few voters

• Sylvain Bouveret
• Yann Chevaleyre
• François Durand
• Jérôme Lang

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 both deterministic (non-anonymous) variants, and randomized (and anonymous) versions of these rules. We focus on a subfamily of these rules defined by ``non-interleaved'' sequences. We first focus on the axiomatic properties of our rules. Then we focus on the identification of the non-interleaved sequence that gives the best approximation of the Borda score under the impartial culture. Finally, we apply our rules to randomly generated data. Our conclusion is that, in contexts where there are more candidates than voters, elimination-based rules allow for a very low communication complexity (and especially, avoid asking voters to rank alternatives), and yet can be good approximations of common voting rules, while enjoying a number of good properties.

JAAMAS Journal 2016 Journal Article

Positional scoring-based allocation of indivisible goods

• Dorothea Baumeister
• Sylvain Bouveret
• Abdallah Saffidine

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.

JAAMAS Journal 2015 Journal Article

Characterizing conflicts in fair division of indivisible goods using a scale of criteria

• Sylvain Bouveret
• Michel Lemaître

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.

ECAI Conference 2014 Conference Paper

Manipulating picking sequences

• Sylvain Bouveret
• Jérôme Lang

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.

ECAI Conference 2014 Conference Paper

Scoring Rules for the Allocation of Indivisible Goods

• Dorothea Baumeister
• Sylvain Bouveret
• Jérôme Lang
• Nhan-Tam Nguyen
• Trung Thanh Nguyen 0004
• Jörg Rothe

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 = (s1, .. ., sm) consists of m nonincreasing nonnegative weights, where siis 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 ★ such as, typically, + or min. The rule associated with s and ★ 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.

ECAI Conference 2012 Conference Paper

Fair Division of Indivisible Goods under Risk

• Charles Lumet
• Sylvain Bouveret
• Michel Lemaître

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 sub-optimal good allocations for real-world inspired allocation problems of realistic size.

IJCAI Conference 2011 Conference Paper

A General Elicitation-Free Protocol for Allocating Indivisible Goods

• Sylvain Bouveret
• J
• eacute; r
• ocirc; me Lang

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.

ECAI Conference 2010 Conference Paper

Fair Division under Ordinal Preferences: Computing Envy-Free Allocations of Indivisible Goods

• Sylvain Bouveret
• Ulle Endriss
• Jérôme Lang

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.

IJCAI Conference 2009 Conference Paper

• Sylvain Bouveret
• Ulle Endriss
• Jérôme Lang

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.

AIJ Journal 2009 Journal Article

Computing leximin-optimal solutions in constraint networks

• Sylvain Bouveret
• Michel Lemaître

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.

IJCAI Conference 2007 Conference Paper

• Sylvain Bouveret
• Michel Lema
• icirc; tre

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.

AAMAS Conference 2005 Conference Paper

Allocation Of Indivisible Goods: A General Model And Some Complexity Results

• Sylvain Bouveret
• H
• eacute; l
• egrave; ne Fargier
• J
• eacute; r
• ocirc; me Lang
• Michel Lema

IJCAI Conference 2005 Conference Paper

Efficiency and envy-freeness in fair division of indivisible goods: logical representation and complexity

• Sylvain Bouveret
• Jérôme

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.