Author name cluster

Aurélie Beynier

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

16 papers

2 author rows

AAMAS Conference 2026 Conference Paper

Fairness in Cooperative Multi-objective Multi-agent Reinforcement Learning using Expected Utility

Fares Chouaki
Aurélie Beynier
Nicolas Maudet
Paolo Viappiani

Fairness as equity and compromise across multiple viewpoints is a necessary consideration in any decision that is evaluated from several possibly conflicting perspectives. It is also a property that artificial decision-making agents should uphold to be deployable to real-worldproblems. However, existingworkinsequentialdecisionmaking ensures fairness among agents or objectives but struggles with real-world problems that are both multi-agent and multiobjective. Furthermore, research integrating fairness into Multi- ObjectiveReinforcementLearning(MORL)isfocusedonoptimizing the Scalarized Expected Return (SER) criterion while mostly ignoring the Expected Scalarized Return (ESR) criterion. We argue that fairness in MORL should also be investigated under ESR since it is sometimes more suitable when solving problems where fairness matters. In this paper, we study objective-wise fairness in cooperative multi-agent multi-objective decision-making under ESR. We propose the first algorithm that learns efficient decentralized policies while enforcing fairness across objectives under ESR. We identify a key challenge in this setting related to policy conditioning on globally accumulated returns, which hinders decentralized learning and execution, and we present an approach to address it based on inter-agent communication. Experiments on discrete and continuous control tasks demonstrate that our method outperforms existing baselines.

PDF

AAMAS Conference 2026 Conference Paper

Multi-Objective Categorical Deep Q-Networks

Farès Chouaki
Aurélie Beynier
Nicolas Maudet
Paolo Viappiani

Motivated by recent advances in distributional reinforcement learning on the one hand and Multi-Objective Reinforcement Learning (MORL) on the other, we propose MO-CDQN, a value-based algorithmthat, givenapossiblynon-linearscalarizationfunction, learns the policy with maximal expected scalarized return. Leveraging the Kantorovich-Rubinstein duality, we prove the theoretical validity of our method for Lipschitz-continuous scalarization functions. We establish that the state-action return distributions learned by our algorithm converge to a fixed point whose expected scalarized return is optimal. Our approach is then extended to propose the first valuebased multi-policy algorithm for solving MORL problems under the expected scalarized return criterion. The proposed algorithms are tested on several environments from the MO-gymnasium benchmark. The results are promising and show that, on the one hand, our algorithm learns policies better than those obtained by existing approaches in the literature while requiring fewer interactions with the environment. On the other hand, given a set of scalarization functions, our multi-policy algorithm takes advantage of its offpolicy nature to successfully optimize several policies concurrently and efficiently provide a set of policies, each optimal for a given scalarization function.

PDF

ECAI Conference 2025 Conference Paper

Enhancing CBBA Convergence and Optimality Guarantees in Multiagent Task Allocation

Alexandre Kha
Aurélie Beynier
Christophe Labreuche
Mathieu Marchand

The Consensus-Based Bundle Algorithm (CBBA) is a leading approach for decentralized task allocation, offering conflict-free task assignments within a bounded number of iterations and a 50% optimality guarantee for utility functions with Diminishing Marginal Gains (DMG). However, we identify three limitations: (1) the Time-Discounted Reward utility function proposed with CBBA is not always DMG, (2) the optimality guarantee may not hold even with DMG functions, and (3) the algorithm can be inefficient as it incurs unnecessary idle iterations after convergence. To address these issues, we propose three key contributions. For limitation (1), we introduce the Repeated Path Times utility function, which is DMG in all cases and aligns with Min-Sum and Makespan objectives. Regarding point (2), we develop Global CBBA (GCBBA), a variant algorithm that leverages global consensus to restore the 50% optimality guarantee under DMG and ensures bounded convergence for any bundle-monotonic objective. Finally, to address limitation (3), we design a decentralized early convergence detection method to improve efficiency. Experimental results show that GCBBA significantly accelerates convergence on large-scale problems compared to the baseline CBBA.

Details

AAMAS Conference 2025 Conference Paper

Fairness in Cooperative Multi-agent Multi-objective Reinforcement Learning using the Expected Scalarized Return

Farès Chouaki
Aurélie Beynier
Nicolas Maudet
Paolo Viappiani

Fairness is essential for deploying artificial decision-making agents in the real world. Existing work in sequential decision-making ensures fairness among agents or objectives but struggles with real-world problems that are both multi-agent and multi-objective. Furthermore, research integrating fairness into Multi-Objective Reinforcement Learning (MORL) is focused on ensuring fairness over the objectives only on the average of several executions of a policy, which is achived by optimizing the policy’s scalarized expected return (SER). To achieve fairness over objectives during each execution the expected scalarized return (ESR) of a policy needs to be optimized instead. This paper presents an argument on the necessity of using ESR in the context of fair multi-objective decision-making and proposes the first mono-policy algorithm able to learn efficient decentralized policies while ensuring fairness across objectives under ESR.

PDF

ECAI Conference 2025 Conference Paper

Uncertainty in Quantitative Bipolar Argumentation Frameworks

Jordan Thieyre
Caren Al Anaissy
Aurélie Beynier
Sébastien Destercke
Nicolas Maudet
Srdjan Vesic

Online deliberation platforms allow people to exchange their opinions around a specified issue and to vote on these opinions in order to reach a collective decision. Argumentation allows to structure and analyse user input for these platforms. A debate can be represented by a quantitative bipolar argumentation framework where votes on each argument of the debate are aggregated into an initial weight. One of the main challenges these platforms face is sparse voting i. e. participants vote on a few number of arguments, leading to an imbalance of the number of votes between the arguments. In this paper, we propose a methodology that handles sparse voting in online debates, by introducing imprecise quantitative bipolar argumentation frameworks that incorporate uncertainty on the initial weights. Specifically, we leverage votes on arguments to initialize weight intervals that represent the uncertainty on the initial weights, using the imprecise Dirichlet model. We use four state-of-the-art bipolar gradual semantics to generate a final acceptability interval on each argument and we introduce several properties to study the effect of these semantics on the uncertainty on each argument’s final evaluation. Our methodology allows for a more robust representation of argument strength in the presence of limited data.

Details

ECAI Conference 2024 Conference Paper

Explaining the Lack of Locally Envy-Free Allocations

Aurélie Beynier
Jean-Guy Mailly
Nicolas Maudet
Anaëlle Wilczynski

In fair division, local envy-freeness is a desirable property which has been thoroughly studied in recent years. In this paper, we study explanations which can be given to explain that no allocation of items can satisfy this criterion, in the house allocation setting where agents receive a single item. While Minimal Unsatisfiable Subsets (MUSes) are key concepts to extract explanations, they cannot be used as such: (i) they highly depend on the initial encoding of the problem; (ii) they are flat structures which fall short of capturing the dynamics of explanations; (iii) they typically come in large number and exhibit great diversity. In this paper we provide two SAT encodings of the problem which allow us to extract MUS when instances are unsatisfiable. We build a dynamic graph structure which allows to follow step-by-step the explanation. Finally, we propose several criteria to select MUSes, some of them being based on the MUS structure, while others rely on this original graphical explanation structure. We give theoretical bounds on these metrics, showing that they can vary significantly for some instances. Experimental results on synthetic data complement these results and illustrate the impact of the encodings and the relevance of our metrics to select among the many MUSes.

Details

AAMAS Conference 2024 Conference Paper

Is Limited Information Enough? An Approximate Multi-agent Coverage Control in Non-Convex Discrete Environments

Tatsuya Iwase
Aurélie Beynier
Nicolas Bredeche
Nicolas Maudet
Jason R. Marden

Conventional distributed approaches to coverage control may suffer from lack of convergence and poor performance, due to the fact that agents have limited information, especially in non-convex discrete environments. To address this issue, we extend the approach of [12] which demonstrates how a limited degree of inter-agent communication can be exploited to overcome such pitfalls in onedimensional discrete environments. The focus of this paper is on extending such results to general dimensional settings. We show that the extension is convergent and keeps the approximation ratio of 2, meaning that any stable solution is guaranteed to have a performance within 50% of the optimal one. The experimental results exhibit that our algorithm outperforms several state-of-the-art algorithms, and also that the runtime is scalable.

PDF

ECAI Conference 2023 Conference Paper

On the Notion of Envy Among Groups of Agents in House Allocation Problems

Nathanaël Gross-Humbert
Nawal Benabbou
Aurélie Beynier
Nicolas Maudet

Envy-freeness is one of the prominent fairness notions in multiagent resource allocation but it has been mainly studied from an individual point of view. When the agents are partitioned into groups, fairness between groups is desirable. Several notions of group envy-freeness have been proposed over the last few years in the domain of fair division. In this paper we show that when groups may have different sizes and each agent gets at most one item, existing group envy-freeness notions fail to satisfy some desirable axioms. This motivates us to propose an original notion of degree of envy-freeness among groups, based on the counterfactual comparison of subgroups of the same size. While this notion is computationally demanding, we show that it can be efficiently approximated thanks to an adapted sampling method, showing that our approach is of practical relevance.

Details

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.

PDF Details DOI

AAMAS Conference 2021 Conference Paper

Sequential and Swap Mechanisms for Public Housing Allocation with Quotas and Neighbourhood-Based Utilities

Nathanaël Gross-Humbert
Nawal Benabbou
Aurélie Beynier
Nicolas Maudet

We consider the problem of allocating indivisible items to agents where both agents and items are partitioned into disjoint groups. Following previous works on public housing allocation, each item (or house) belongs to a block and each agent is assigned a type. The allocation problem consists in assigning at most one item to each agent in a good way while respecting diversity constraints. Based on Schelling’s seminal work, we introduce a generic individual utility function where the welfare of an agent not only relies on her preferences over the items but also takes into account the fraction of agents of her own type in her own block. In this context, we investigate the issue of stability, and study two existing allocation mechanisms: a sequential mechanism used in Singapore and a distributed procedure based on mutually improving swaps of items.

PDF

JAAMAS Journal 2021 Journal Article

Swap dynamics in single-peaked housing markets

Aurélie Beynier
Nicolas Maudet
Parham Shams

Abstract This paper focuses on the problem of fairly and efficiently allocating resources to agents. We consider a specific setting, usually referred to as a housing market, where each agent must receive exactly one resource (and initially owns one). In this framework, in the domain of linear preferences, the Top Trading Cycle (TTC) algorithm is the only procedure satisfying Pareto-optimality, individual rationality and strategy-proofness. Under the restriction of single-peaked preferences, Crawler enjoys the same properties. These two centralized procedures might however involve long trading cycles. In this paper we focus instead on procedures involving the shortest cycles: bilateral swap-deals. In such swap dynamics, the agents perform pairwise mutually improving deals until reaching a swap-stable allocation (no improving swap-deal is possible). We prove that in the single-peaked domain every swap-stable allocation is Pareto-optimal, showing the efficiency of the swap dynamics. In fact, this domain turns out to be maximal when it comes to guaranteeing this property. Besides, both the outcome of TTC and Crawler can always be reached by sequences of swaps. However, some Pareto-optimal allocations are not reachable through improving swap-deals. We further analyze the outcome of swap dynamics through social welfare notions, in our context the average or minimum rank of the resources obtained by agents in the final allocation. We start by providing a worst-case analysis of these procedures. Finally, we present an extensive experimental study in which different versions of swap dynamics are compared to other existing allocation procedures. We show that they exhibit good results on average in this domain, under different cultures for generating synthetic data.

Details DOI

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.

Details

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.

PDF

JAAMAS Journal 2019 Journal Article

Local envy-freeness in house allocation problems

Aurélie Beynier
Yann Chevaleyre
Anaëlle Wilczynski

Abstract We study the fair division problem consisting in allocating one item per agent so as to avoid (or minimize) envy, in a setting where only agents connected in a given network may experience envy. In a variant of the problem, agents themselves can be located on the network by the central authority. These problems turn out to be difficult even on very simple graph structures, but we identify several tractable cases. We further provide practical algorithms and experimental insights.

Details DOI

ECAI Conference 2010 Conference Paper

A Decision-Theoretic Approach to Cooperative Control and Adjustable Autonomy

Abdel-Illah Mouaddib
Shlomo Zilberstein
Aurélie Beynier
Laurent Jeanpierre

Cooperative control can help overcome the limitations of autonomous systems (AS) by introducing a supervision unit (SU) (human or another system) into the control loop and creating adjustable autonomy. We present a decision-theoretic approach to accomplish this using Mixed Markov Decision Processes (MI-MDPs). The solution is an optimal plan that tells the AS what actions to perform as well as when to request SU attention or transfer control to the SU. This provides a varying degree of autonomy, particularly suitable for robots exploring a domain with regions that are too complex or risky for autonomous operation, or intelligent vehicles operating in heavy traffic.

Details

JAAMAS Journal 2010 Journal Article

Solving efficiently Decentralized MDPs with temporal and resource constraints

Aurélie Beynier
Abdel-illah Mouaddib

Abstract Optimizing the operation of cooperative multi-agent systems that can deal with large and realistic problems has become an important focal area of research in the multi-agent community. In this paper, we first present a new model, the OC-DEC-MDP (Opportunity Cost Decentralized Markov Decision Process), that allows us to represent large multi-agent decision problems with temporal and precedence constraints. Then, we propose polynomial algorithms to efficiently solve problems formalized by OC-DEC-MDPs. The problems we deal with consist of a set of agents that have to execute a set of tasks in a cooperative way. The agents cannot communicate during task execution and they must respect resource and temporal constraints. Our approach is based on Decentralized Markov Decision Processes (DEC-MDPs) and uses the concept of opportunity cost borrowed from economics to obtain approximate control policies. Experimental results show that our approach produces good quality solutions for complex problems which are out of reach of existing approaches.

Details DOI