Arrow Research search

Author name cluster

Nicolas Maudet

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.

62 papers
2 author rows

Possible papers

62

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

JAAMAS Journal 2026 Journal Article

Modular Representation of Agent Interaction Rules through Argumentation

  • Antonis Kakas
  • Nicolas Maudet
  • Pavlos Moraitis

Communication between agents needs to be flexible enough to encompass together a variety of different aspects such as, conformance to society protocols, private tactics of the individual agents, strategies that reflect different classes of agent types (or personal attitudes) and adaptability to the particular external circumstances at the time when the communication takes place. In this paper, we propose an argument-based framework for representing communication theories of agents that can take into account in a uniform way these different aspects. We show how this approach can be used to realize existing types of dialogue strategies and society protocols in a way that facilitates their modular development and extension to make them more flexible in handling different or special circumstances.

Details DOI

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

JAAMAS Journal 2026 Journal Article

Negotiating Dialogue Games

  • Nicolas Maudet

Abstract Recently in the field of agent communication, many authors have adopted the view of interaction as a joint activity regulated by means of dialogue games. It is argued in particular that this approach should increase the flexibility of dialogues by allowing a variety of game compositions. In this research note, we present a framework suited to this feature. A preliminary attempt to capture the negotiation phase (which allows agents to agree upon the dialogue game currently regulating their conversation) is discussed.

Details DOI

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 2022 Conference Paper

Multiagent Dynamics of Gradual Argumentation Semantics

  • Louise Dupuis de Tarlé
  • Elise Bonzon
  • Nicolas Maudet

In the abstract argumentation setting, gradual semantics have been proposed to assess the individual strength of arguments. A number of such semantics have been proposed recently, and their formal properties have been studied. While these semantics are sometimes motivated by their better adequacy to capture debates, their behaviour in such multiagent settings is largely unexplored. In this paper, we undertake a study of the multiagent dynamics of a standard gradual semantics. We propose a simple protocol, where agents exchange arguments in order to provide a collective evaluation of the value of a given argument (i. e an issue), and may learn new arguments from the other agents, as well as an extended version allowing votes. The debate proceeds following a better response dynamics. We study how the value of the issue and the agents opinion evolve, depending on various parameters of this setting.

PDF

AAMAS Conference 2021 Conference Paper

Rank Aggregation by Dissatisfaction Minimisation in the Unavailable Candidate Model

  • Arnaud Grivet Sébert
  • Nicolas Maudet
  • Patrice Perny
  • Paolo Viappiani

In this paper, we extend the unavailable candidate model [10] and present two new voting rules based on a finer notion of disagreement, called dissatisfaction, which depends on the ranks of the candidates, considered among all the candidates (ex ante dissatisfaction rule) or only among the available candidates (ex post dissatisfaction rule). We provide algorithmic results for the two rules and show that apparently very different voting rules such as scoring rules or Kemeny rule can be unified under the same aggregation concept: expectation of dissatisfaction under the availability distribution.

PDF

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

IJCAI Conference 2019 Conference Paper

Comparing Options with Argument Schemes Powered by Cancellation

  • Khaled Belahcene
  • Christophe Labreuche
  • Nicolas Maudet
  • Vincent Mousseau
  • Wassila Ouerdane

We introduce a way of reasoning about preferences represented as pairwise comparative statements, based on a very simple yet appealing principle: cancelling out common values across statements. We formalize and streamline this procedure with argument schemes. As a result, any conclusion drawn by means of this approach comes along with a justification. It turns out that the statements which can be inferred through this process form a proper preference relation. More precisely, it corresponds to a necessary preference relation under the assumption of additive utilities. We show the inference task can be performed in polynomial time in this setting, but that finding a minimal length explanation is NP-complete.

PDF 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

IJCAI Conference 2018 Conference Paper

Accountable Approval Sorting

  • Khaled Belahcene
  • Yann Chevaleyre
  • Christophe Labreuche
  • Nicolas Maudet
  • Vincent Mousseau
  • Wassila Ouerdane

We consider decision situations in which a set of points of view (voters, criteria) are to sort a set of candidates to ordered categories (Good/Bad). Candidates are judged good, when approved by a sufficient set of points of view; this corresponds to NonCompensatory Sorting. To be accountable, such approval sorting should provide guarantees about the decision process and decisions concerning specific candidates. We formalize accountability using a feasibility problem expressed as a boolean satisfiability formulation. We illustrate different forms of accountability when a committee decides with approval sorting and study the information that should be disclosed by the committee.

PDF Details

KR Conference 2018 Conference Paper

Combining Extension-based semantics and Ranking-based semantics for Abstract Argumentation

  • Elise Bonzon
  • Jérôme Delobelle
  • Sébastien Konieczny
  • Nicolas Maudet

Two kinds of semantics exist for abstract argumentation. Extension-based semantics evaluate the acceptability of sets of arguments, while ranking-based semantics evaluate the strength of each argument. They focus on different aspects of the information conveyed by argumentation systems. After discussing pros and cons of both approaches, we study how to combine them, in order to take benefits from both. We propose six new families of semantics for abstract argumentation combining extension-based and ranking-based semantics. More precisely we propose to refine the ranking-based semantics using information coming from extension-based semantics acceptability of arguments, and to modify the extensions chosen by extension-based semantics using preferential information coming from ranking-based semantics.

AAMAS Conference 2018 Conference Paper

Fairness in Multiagent Resource Allocation with Dynamic and Partial Observations

  • Aur�lie Beynier
  • Nicolas Maudet
  • Anastasia Damamme

We investigate fairness issues in distributed resource allocation of indivisible goods. More specifically, we study envy-freeness in a setting where the observations of agents only result from encounters with other agents. Agents thus have a partial and uncertain view of the entire allocation, that they maintain throughout the process, and which allows them to have different estimates of their envy. We provide a fully distributed protocol allowing to guarantee termination despite the limited knowledge of agents.

PDF

KR Conference 2018 Conference Paper

Gradual semantics accounting for similarity between arguments

  • Leila Amgoud
  • Elise Bonzon
  • Jérôme Delobelle
  • Dragan Doder
  • Sébastien Konieczny
  • Nicolas Maudet

Argumentation is a reasoning model based on the justification of claims by arguments. Often, arguments to be considered are not completely independent, two arguments can be related for different reasons, they may overlap, or given by two persons that make similar statements during a debate, but express them differently, etc. This paper studies for the first time the impact of similarity (i. e. , when pairs of arguments are related) in the context of gradual evaluation in abstract argumentation. We present principles that a semantics accounting for similarities should satisfy, and show how to extend gradual semantics for this purpose. We propose three original methods to do so, and study their properties. In particular, the new semantics are evaluated with respect to the new principles, and others from the literature.

AAMAS Conference 2018 Conference Paper

Local Envy-Freeness in House Allocation Problems

  • Aur�lie Beynier
  • Yann Chevaleyre
  • Laurent Gourv�s
  • Julien Lesca
  • Nicolas Maudet
  • Ana�lle Wilczynski

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

PDF

IJCAI Conference 2017 Conference Paper

A Model for Accountable Ordinal Sorting

  • Khaled Belahcene
  • Christophe Labreuche
  • Nicolas Maudet
  • Vincent Mousseau
  • Wassila Ouerdane

We address the problem of multicriteria ordinalsorting through the lens of accountability, i. e. theability of a human decision-maker to own a recommendationmade by the system. We put forward anumber of model features that would favor the capabilityto support the recommendation with a convincingexplanation. To account for that, we designa recommender system implementing and formalizingsuch features. This system outputs explanationsdefined under the form of specific argumentschemes tailored to represent the specific rules ofthe model. At the end, we discuss possible andpromising argumentative perspectives.

PDF Details

AIJ Journal 2017 Journal Article

Distributed fair allocation of indivisible goods

  • Yann Chevaleyre
  • Ulle Endriss
  • Nicolas Maudet

Distributed mechanisms for allocating indivisible goods are mechanisms lacking central control, in which agents can locally agree on deals to exchange some of the goods in their possession. We study convergence properties for such distributed mechanisms when used as fair division procedures. Specifically, we identify sets of assumptions under which any sequence of deals meeting certain conditions will converge to a proportionally fair allocation and to an envy-free allocation, respectively. We also introduce an extension of the basic framework where agents are vertices of a graph representing a social network that constrains which agents can interact with which other agents, and we prove a similar convergence result for envy-freeness in this context. Finally, when not all assumptions guaranteeing envy-freeness are satisfied, we may want to minimise the degree of envy exhibited by an outcome. To this end, we introduce a generic framework for measuring the degree of envy in a society and establish the computational complexity of checking whether a given scenario allows for a deal that is beneficial to every agent involved and that will reduce overall envy.

Details DOI

JAIR Journal 2017 Journal Article

Rationalisation of Profiles of Abstract Argumentation Frameworks: Characterisation and Complexity

  • Stéphane Airiau
  • Elise Bonzon
  • Ulle Endriss
  • Nicolas Maudet
  • Julien Rossit

Different agents may have different points of view. Following a popular approach in the artificial intelligence literature, this can be modeled by means of different abstract argumentation frameworks, each consisting of a set of arguments the agent is contemplating and a binary attack-relation between them. A question arising in this context is whether the diversity of views observed in such a profile of argumentation frameworks is consistent with the assumption that every individual argumentation framework is induced by a combination of, first, some basic factual attack-relation between the arguments and, second, the personal preferences of the agent concerned regarding the moral or social values the arguments under scrutiny relate to. We treat this question of rationalisability of a profile as an algorithmic problem and identify tractable and intractable cases. In doing so, we distinguish different constraints on admissible rationalisations, e.g., concerning the types of preferences used or the number of distinct values involved. We also distinguish two different semantics for rationalisability, which differ in the assumptions made on how agents treat attacks between arguments they do not report. This research agenda, bringing together ideas from abstract argumentation and social choice, is useful for understanding what types of profiles can reasonably be expected to occur in a multiagent system.

PDF Details DOI

IJCAI Conference 2017 Conference Paper

Rationalisation of Profiles of Abstract Argumentation Frameworks: Extended Abstract

  • Stephane Airiau
  • Elise Bonzon
  • Ulle Endriss
  • Nicolas Maudet
  • Julien Rossit

We review a recently introduced model in which each of a number of agents is endowed with an abstract argumentation framework reflecting her individual views regarding a given set of arguments. A question arising in this context is whether the diversity of views observed in such a situation is consistent with the assumption that every individual argumentation framework is induced by a combination of, first, some basic factual information and, second, the personal preferences of the agent concerned. We treat this question of rationalisability of a profile as an algorithmic problem and identify tractable and intractable cases. This is useful for understanding what types of profiles can reasonably be expected to occur in a multiagent system.

PDF Details

AAAI Conference 2016 Conference Paper

A Comparative Study of Ranking-Based Semantics for Abstract Argumentation

  • Elise Bonzon
  • Jérôme Delobelle
  • Sébastien Konieczny
  • Nicolas Maudet

Argumentation is a process of evaluating and comparing a set of arguments. A way to compare them consists in using a ranking-based semantics which rank-order arguments from the most to the least acceptable ones. Recently, a number of such semantics have been proposed independently, often associated with some desirable properties. However, there is no comparative study which takes a broader perspective. This is what we propose in this work. We provide a general comparison of all these semantics with respect to the proposed properties. That allows to underline the differences of behavior between the existing semantics.

PDF Details

AAMAS Conference 2016 Conference Paper

Rationalisation of Profiles of Abstract Argumentation Frameworks

  • Stephane Airiau
  • Elise Bonzon
  • Ulle Endriss
  • Nicolas Maudet
  • Julien Rossit

Different agents may have different points of view. This can be modelled using different abstract argumentation frameworks, each consisting of a set of arguments and a binary attack-relation between them. A question arising in this context is whether the diversity of views observed in such a profile of argumentation frameworks is consistent with the assumption that every individual argumentation framework is induced by a combination of, first, some basic factual attack-relation between the arguments and, second, the personal preferences of the agent concerned. We treat this question of rationalisability of a profile as an algorithmic problem and identify tractable and intractable cases. This is useful for understanding what types of profiles can reasonably be expected to come up in a multiagent system.

PDF

IJCAI Conference 2015 Conference Paper

Formal Analysis of Dialogues on Infinite Argumentation Frameworks

  • Francesco Belardinelli
  • Davide Grossi
  • Nicolas Maudet

The paper analyses multi-agent strategic dialogues on possibly infinite argumentation frameworks. We develop a formal model for representing such dialogues, and introduce FOA-ATL, a first-order extension of alternating-time logic, for expressing the interplay of strategic and argumentation-theoretic properties. This setting is investigated with respect to the model checking problem, by means of a suitable notion of bisimulation. This notion of bisimulation is also used to shed light on how static properties of argumentation frameworks influence their dynamic behaviour.

PDF Details

IJCAI Conference 2015 Conference Paper

Optimization of Probabilistic Argumentation with Markov Decision Models

  • Emmanuel Hadoux
  • Aur
  • eacute; lie Beynier
  • Nicolas Maudet
  • Paul Weng
  • Anthony Hunter

One prominent way to deal with conflicting viewpoints among agents is to conduct an argumentative debate: by exchanging arguments, agents can seek to persuade each other. In this paper we investigate the problem, for an agent, of optimizing a sequence of moves to be put forward in a debate, against an opponent assumed to behave stochastically, and equipped with an unknown initial belief state. Despite the prohibitive number of states induced by a naive mapping to Markov models, we show that exploiting several features of such interaction settings allows for optimal resolution in practice, in particular: (1) as debates take place in a public space (or common ground), they can readily be modelled as Mixed Observability Markov Decision Processes, (2) as argumentation problems are highly structured, one can design optimization techniques to prune the initial instance. We report on the experimental evaluation of these techniques.

PDF Details

ECAI Conference 2014 Conference Paper

On the Use of Target Sets for Move Selection in Multi-Agent Debates

  • Dionysios Kontarinis
  • Elise Bonzon
  • Nicolas Maudet
  • Pavlos Moraitis

In debates, agents are faced with the problem of deciding how to best contribute to the current state of the debate in order to satisfy their own goals. Target sets specify minimal changes on the current state of the debate that are required to achieve such goals, where changes are the addition and/or deletion of attacks among arguments. However, agents may not have the ability to implement all the actions prescribed by a target set, nor to rely on others to help them to do so. In this short paper we provide evidence that this notion is still a useful criterion for move selection.

Details

AAMAS Conference 2012 Conference Paper

Finding new consequences of an observation in a system of agents

  • Gauvain Bourgne
  • Katsumi Inoue
  • Nicolas Maudet

When a new observation is added to an existing logical theory, it is often necessary to compute new consequences of this observation together with the theory. This paper investigates whether this reasoning task can be performed incrementally in a distributed setting involving first-order theories. We propose a complete asynchronous algorithm for this non-trivial task, and illustrate it with a small example. As some produced consequences may not be new, we also propose a post-processing technique to remove them.

PDF

AAMAS Conference 2012 Conference Paper

Influence and aggregation of preferences over combinatorial domains

  • Nicolas Maudet
  • Maria Silvia Pini
  • Francesca Rossi
  • Kristen Brent Venable

In a multi-agent context where a set of agents declares their preferences over a common set of candidates, it is often the case that agents may influence each others. Recent work has modelled the influence phenomenon in the case of voting over a single issue. Here we generalize this model to account for preferences over combinatorially structured domains including several issues. When agents express their preferences as CP-nets, we show how to model influence functions and how to aggregate preferences by interleaving voting and influence convergence.

PDF

ECAI Conference 2012 Conference Paper

Justifying Dominating Options when Preferential Information is Incomplete

  • Christophe Labreuche
  • Nicolas Maudet
  • Wassila Ouerdane

Providing convincing explanations to accompany recommendations is a key issue in decision-aiding. In the context of decisions involving multiple criteria, the problem is made very difficult because the decision model itself may involve a complex process. In this paper, we investigate the following issue: when the preferential information provided by the user is incomplete, is there a principled way to define what is a "simple" explanation for a recommended choice? We argue first that explanations may necessitate different levels of detail. Next, we show that even when a detailed explanation is necessary, it is possible to distinguish explanations of different levels of complexity. Our results rely on an original connection we establish between the "mechanics" required to compute supporting coalitions of criteria and the simplicity of the explanation.

Details

TARK Conference 2011 Conference Paper

Compilation and communication protocols for voting rules with a dynamic set of candidates

  • Yann Chevaleyre
  • Jérôme Lang
  • Nicolas Maudet
  • Jérôme Monnot

We address the problem of designing communication protocols for voting rules when the set of candidates can evolve via the addition of new candidates. We show that the necessary amount of communication that must be transmitted between the voters and the central authority depends on the amount of space devoted to the storage of the votes over the initial set of candidates. This calls for a bicriteria evaluation of protocols. We consider a few usual voting rules, and three types of storage functions: full storage, where the full votes on the initial set of voters are stored; null storage, where nothing is stored; and anonymous storage, which lies in-between. For some of these pairs (voting rule, type of storage) we design protocols and show that they are asymptotically optimal by determining the communication complexity of the rule under the storage function considered.

Details

KER Journal 2011 Journal Article

Informal logic dialogue games in human–computer dialogue

  • Tangming Yuan
  • David Moore
  • Chris Reed
  • Andrew Ravenscroft
  • Nicolas Maudet

Abstract Informal logic (IL) is an area of philosophy rich in models of communication and discourse with a heavy focus on argument and ‘dialogue games’. Computational dialectics is a maturing strand of research that is focused on implementing these dialogue games. The aim of this paper is to review research on applying IL dialogue games into human–computer dialogue design. We argue that IL dialogue games tend to have a number of attractive properties for human computer dialogue and that their computational utilization in this area has been increasing recently. Despite the strength of the case for IL, a number of important barriers need to be overcome if the potential of IL is to be fulfilled. These barriers are examined and means of overcoming them discussed.

Details DOI

AAMAS Conference 2011 Conference Paper

On the Outcomes of Multiparty Persuasion

  • Elise Bonzon
  • Nicolas Maudet

In recent years, several bilateral protocols regulating the exchange of arguments between agents have been proposed. When dealing with persuasion, the objective is to arbitrate among conflicting viewpoints. Often, these debates are not entirely predetermined from the initial situation, which means that agents have a chance to influence the outcome in a way that fits their individual preferences. This paper introduces a simple and intuitive protocol for multiparty argumentation, in which several (more than two) agents are equipped with argumentation systems. We further assume that they focus on a (unique) argument (or issue) -thus making the debate two-sided- but do not coordinate. We study what outcomes can (or will) be reached if agents follow this protocol. We investigate in particular under which conditions the debate is pre-determined or not, and whether the outcome coincides with the result obtained by merging the argumentation systems.

PDF

ECAI Conference 2010 Conference Paper

ABA: Argumentation Based Agents

  • Antonis C. Kakas
  • Leila Amgoud
  • Gabriele Kern-Isberner
  • Nicolas Maudet
  • Pavlos Moraitis

Many works have identified the potential benefits of using argumentation to address a large variety of multiagent problems. In this paper we take this idea one step further and develop the concept of a fully integrated argumentation-based agent architecture that allows us to develop agents that are coherently designed on an underlying argumentation based foundation. Under this architecture, an agent is composed of a collection of modules each of which is equipped with a local argumentation theory. Similarly, the intra-agent control of the agent is governed by local argumentation theories that are sensitive to the current situation of the agent through dynamically enabled feasibility arguments.

Details

ECAI Conference 2010 Conference Paper

Abduction of distributed theories through local interactions

  • Gauvain Bourgne
  • Katsumi Inoue
  • Nicolas Maudet

What happens when distributed sources of information (agents) hold and acquire information locally, and have to communicate with neighbouring agents in order to refine their hypothesis regarding the actual global state of this environment? This question occurs when it is not be possible (e. g. for practical or privacy concerns) to collect observations and knowledge, and centrally compute the resulting theory. In this paper, we assume that agents are equipped with full clausal theories and individually face abductive tasks, in a globally consistent environment. We adopt a learner/critic approach. Previous work in this line mostly relied on some assumptions of compositionality (which allow to treat each piece of exchanged information separately). Because no shared background knowledge is assumed to start with, this does not hold here. We design a protocol guaranteeing convergence to a situation "sufficiently" satisfying as far as consistency of the system is concerned, and discuss its other properties.

Details

ECAI Conference 2010 Conference Paper

Dealing with the dynamics of proof-standard in argumentation-based decision aiding

  • Wassila Ouerdane
  • Nicolas Maudet
  • Alexis Tsoukiàs

Usually, in argumentation, the proof-standards that are used are fixed a priori by the procedure. However (multicriteria) decision-aiding is a context where it may be modified dynamically during the process, depending on the responses of the decision-maker. The expert indeed needs to adapt and refine its choice of an appropriate method of aggregating arguments pros and cons, so that it fits the preference model inferred from the interaction. In this short paper we introduce how this aspect can be handled in an argumentation-based decision-aiding framework. The first contribution of the paper is conceptual: the notion of a concept lattice based on simple properties and allowing to navigate among the different proof-standards is put forward. We then show how this can be integrated within the Carneades model.

Details

AAAI Conference 2010 Conference Paper

Possible Winners when New Candidates Are Added: The Case of Scoring Rules

  • Yann Chevaleyre
  • Jérôme Lang
  • Nicolas Maudet
  • Jérôme Monnot

In some voting situations, some new candidates may show up in the course of the process. In this case, we may want to determine which of the initial candidates are possible winners, given that a fixed number k of new candidates will be added. Focusing on scoring rules, we give complexity results for the above possible winner problem.

PDF Details

IJCAI Conference 2009 Conference Paper

  • Yann Chevaleyre
  • Jérôme Lang
  • Nicolas Maudet
  • Guillaume Ravilly-Abadie

In many practical contexts where a number of agents have to find a common decision, the votes do not come all together at the same time. In such situations, we may want to preprocess the information given by the subelectorate (consisting of the voters who have expressed their votes) so as to “compile” the known votes for the time when the latecomers have expressed their votes. We study the amount of space necessary for such a compilation, as a function of the voting rule, the number of candidates, and the number of votes already known. We relate our results to existing work, especially on communication complexity.

PDF Details

JAAMAS Journal 2009 Journal Article

Simple negotiation schemes for agents with simple preferences: sufficiency, necessity and maximality

  • Yann Chevaleyre
  • Ulle Endriss
  • Nicolas Maudet

Abstract We investigate the properties of an abstract negotiation framework where agents autonomously negotiate over allocations of indivisible resources. In this framework, reaching an allocation that is optimal may require very complex multilateral deals. Therefore, we are interested in identifying classes of valuation functions such that any negotiation conducted by means of deals involving only a single resource at a time is bound to converge to an optimal allocation whenever all agents model their preferences using these functions. In the case of negotiation with monetary side payments amongst self-interested but myopic agents, the class of modular valuation functions turns out to be such a class. That is, modularity is a sufficient condition for convergence in this framework. We also show that modularity is not a necessary condition. Indeed, there can be no condition on individual valuation functions that would be both necessary and sufficient in this sense. Evaluating conditions formulated with respect to the whole profile of valuation functions used by the agents in the system would be possible in theory, but turns out to be computationally intractable in practice. Our main result shows that the class of modular functions is maximal in the sense that no strictly larger class of valuation functions would still guarantee an optimal outcome of negotiation, even when we permit more general bilateral deals. We also establish similar results in the context of negotiation without side payments.

Details DOI

AAMAS Conference 2008 Conference Paper

Trajectories of Goods in Distributed Allocation

  • Yann Chevaleyre
  • Ulle Endriss
  • Nicolas Maudet

Distributed allocation mechanisms rely on the agents’ autonomous (and supposedly rational) behaviour: states evolve as a result of agents contracting deals and exchanging resources. It is no surprise that restrictions on potential deals also restrict the reachability of some desirable states, for instance states where goods are efficiently allocated. In particular topological restrictions make any attempt to guarantee asymptotic convergence to an optimal allocation impossible in most cases. In this paper, we concentrate on the dynamics of such systems; more precisely we study the trajectories of goods in such iterative reallocative processes. Our first contribution is to propose an upper bound on the length of the trajectories of goods, when agent utility functions are modular. The second innovative aspect of the paper is then to discuss how this affects, on average, the quality of the states that are reached. Finally, a preliminary study of the non-modular case is proposed, examining how synergetic effects between items can affect their trajectories.

PDF

IJCAI Conference 2007 Conference Paper

  • Yann Chevaleyre
  • Ulle Endriss
  • Sylvia Estivie
  • Nicolas Maudet

Mechanisms for dividing a set of goods amongst a number of autonomous agents need to balance efficiency and fairness requirements. A common interpretation of fairness is envy-freeness, while efficiency is usually understood as yielding maximal overall utility. We show how to set up a distributed negotiation framework that will allow a group of agents to reach an allocation of goods that is both efficient and envy-free.

PDF Details

AAMAS Conference 2007 Conference Paper

Hypotheses Refinement under Topological Communication Constraints

  • Gauvain Bourgne
  • Gael Hette
  • Nicolas Maudet
  • Suzanne Pinson

We investigate the properties of a multiagent system where each (distributed) agent locally perceives its environment. Upon perception of an unexpected event, each agent locally computes its favoured hypothesis and tries to propagate it to other agents, by exchanging hypotheses and supporting arguments (observations). However, we further assume that communication opportunities are severely constrained and change dynamically. In this paper, we mostly investigate the convergence of such systems towards global consistency. We first show that (for a wide class of protocols that we shall define), the communication constraints induced by the topology will not prevent the convergence of the system, at the condition that the system dynamics guarantees that no agent will ever be isolated forever, and that agents have unlimited time for computation and arguments exchange. As this assumption cannot be made in most situations though, we then set up an experimental framework aiming at comparing the relative efficiency and effectiveness of different interaction protocols for hypotheses exchange. We study a critical situation involving a number of agents aiming at escaping from a burning building. The results reported here provide some insights regarding the design of optimal protocol for hypotheses refinement in this context.

PDF

KER Journal 2005 Journal Article

Multiagent resource allocation

  • Yann Chevaleyre
  • Paul E. Dunne
  • Ulle Endriss
  • Jérôme Lang
  • Nicolas Maudet
  • Juan A. Rodríguez-Aguilar

Resource allocation in multiagent systems is a central research issue in the AgentLink community. The aim of the Technical Forum Group on Multiagent Resource Allocation (TFG-MARA) is to provide a venue for the exchange of ideas in this area and to foster collaboration between different research groups. In this article we report on the first meeting of TFG-MARA, which was held as part of the Second AgentLink III Technical Forum in Ljubljana.

Details DOI

JAAMAS Journal 2005 Journal Article

On the Communication Complexity of Multilateral Trading: Extended Report

  • Ulle Endriss
  • Nicolas Maudet

We study the complexity of a multilateral negotiation framework, where autonomous agents agree on a sequence of deals to exchange sets of discrete resources in order to both further their own goals and to achieve a distribution of resources that is socially optimal. When analysing such a framework, we can distinguish different aspects of complexity: How many deals are required to reach an optimal allocation of resources? How many communicative exchanges are required to agree on one such deal? How complex a communication language do we require? And finally, how complex is the reasoning task faced by each agent?

Details DOI

IJCAI Conference 2003 Conference Paper

Protocol Conformance for Logic-based Agents

  • Ulrich Endriss
  • Nicolas Maudet
  • Fariba Sadri
  • Francesca Toni

An agent communication protocol specifies the "rules of encounter" governing a dialogue between agents in a multiagent system. In non-cooperative interactions (such as negotiation dialogues) occur­ ring in open societies it is crucial that agents are equipped with proper means to check, and possi­ bly enforce, conformance to protocols. We identify different levels of conformance (weak, exhaustive, and robust conformance) and explore how a spe­ cific class of logic-based agents can exploit a new representation formalism for communication proto­ cols based on simple if-then rules in order to either check conformance a priori or enforce it at runtime.

PDF

NMR Workshop 2002 Conference Paper

Strategical considerations for argumentative agents (preliminary report)

  • Leila Amgoud
  • Nicolas Maudet

This paper aims at exploring some aspects of the strategical problem of move selection in the context of persuasive dialogues. The proposed heuristics are based on some human strategies issued from natural dialogues. A three-layered approach of strategy is defended, and a preliminary strategical deliberation process (illustrating the interplay of these different levels) is proposed.

Details
v2026.09.13