Compiling a collection of votes (a profile) consists in compressing the information it contains in a minimal way, while still allowing to compute the winner after more votes are received. These additional votes can be understood temporally (when votes come in an asynchronous way) or spatially (when votes are gathered locally in polling stations, and their results published locally before being aggregated on a global level). Given a voting rule, two profiles are equivalent for this rule if for whichever profile we add to each of them, the winner in the two expanded profiles will be the same. An equivalence relation between profiles corresponds to a set of information structures (called compilation structures) encoding equivalence classes. It is well-known that some information structures, such as pairwise majority matrices are the compilation structure for some voting rules, while some others (such as the majority graph) are not. We fully characterise the equivalence relations (or equivalently the information structures) that correspond to some voting rules, and we review a number of interesting information structures and give known voting rules that correspond to them.

Argumentation theory provides a formal framework to represent and analyse debates where participants propose arguments that attack or support others and assign scores expressing their opinions. Quantitative Bipolar Argumentation Frameworks model such debates by assigning initial weights to arguments and using semantics to compute final scores that reflect attackers’ and supporters’ influence. One of the major challenge is setting appropriate initial weights when debaters’ opinions are uncertain. In this paper, we introduce a formal approach to uncertainty propagation in Quantitative Bipolar argumentation frameworks by representing initial weights as belief mass functions over a discretized unit interval. We introduce two new propagation models: (i) an exact model that computes final mass functions by combining focal elements of initial weights with parent arguments via bipolar gradual semantics; (ii) a practical approximation that projects the exact mass onto a user-specified partition and reconstructs masses using the Moebius inverse. We prove mathematical properties of the projection and show that the baseline, while computationally efficient, can be overconfident by failing to preserve expectations. Our approximation reduces the exponential complexity of the exact model while satisfying Epistemic Cautiousness, yielding acceptability intervals that contain true theoretical expectations and balancing tractability with theoretical soundness.

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.

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.

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.

This paper deals with policy learning for a team of heterogeneous robotic agents when the whole team shares a single reward. We address the problem of providing an accurate estimation of the contribution of each agent in tasks where coordination between agents requires joint policy updates of two (or more) agents. This is typically the case when two agents must simultaneously modify their behaviors to perform a joint action that leads to a performance gain for the whole team. We propose a cooperative co-evolutionary algorithm extended with a multi-armed bandit algorithm that dynamically adjusts the number of agents that should update their policies simultaneously, aiming both for performance and learning speed. We use a realistic robotic multi-rover task where agents must physically distribute themselves on points of interest of different natures to complete the task. Results show that the algorithm is able to select the best group size for policy updates that reflects the task's coordination requirements. Surprisingly, we also reveal that coupling between agents' actions in a realistic setup can also emerge from interactions at the phenotypical level, hinting at subtle interactions during learning between the control parameter space and the behavioral space.

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.

In this paper, we explore the min-max inference mechanism of any rule-based system of n if-then possibilistic rules. We establish an additive formula for the output possibility distribution obtained by the inference. From this result, we deduce the corresponding possibility and necessity measures. Moreover, we give necessary and sufficient conditions for the normalization of the output possibility distribution. As application of our results, we tackle the case of a cascade of two if-then possibilistic rules sets and establish an input-output relation between the two min-max equation systems. Finally, we associate to the cascade construction an explicit min-max neural network.

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.

Mediation is a process for resolving conflicts among several entities. In argumentation debates, conflicting agents that may be organized as teams exchange arguments to persuade each other. In this paper, we consider an automated mediator, which assigns the speaking slots to agents so as to optimize some objectives and ensure the fairness of the debate. We propose a general setting where the argumentation strategies of the agents are probabilistically known and may evolve over time. We show that the problem can be solved as a semi-Markov decision problem with hidden modes.

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.

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.

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.

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.

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 pro- posed 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 proper- ties. That allows to underline the differences of behavior between the existing semantics.

Argumentation is based on the exchange and the evaluation of interacting arguments. Unlike Dung's theory where arguments are either accepted or rejected, ranking-based semantics rank-order arguments from the most to the least acceptable ones. We propose in this work six new ranking-based semantics. We argue that, contrarily to existing ranking semantics in the literature, that focus on evaluating attacks and defenses only, it is reasonable to give a prominent role to non-attacked arguments, as it is the case in standard Dung's semantics. Our six semantics are based on the propagation of the weight of each argument to its neighbors, where the weight of non-attacked arguments is greater than the attacked ones.

In this work we address the issue of uncertainty in abstract argumentation. We propose a way to compute the relative relevance of arguments by merging the classical argumentation framework proposed in [5] into a game theoretic coalitional setting, where the worth of a collection of arguments can be seen as the combination of the information concerning the defeat relation and the preferences over arguments of a “user”. Via a property-driven approach, we show that the Shapley value [17] for coalitional games defined over an argumentation framework, can be applied to resume all the information about the worth of sets of arguments into an attribution of relevance for the single arguments. We also prove that, for a large family of (coalitional) argumentation frameworks, the Shapley value can be easily computed.

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.

This paper studies multiagent systems where each agent has access to local observations of a dynamic environment and needs to build from this partial information an hypothesis on the state of the system. Each agent ensures that its hypothesis is consistent with its observations, and communicates with other agents to refine this hypothesis by confronting them to their own views. However, these communications are restricted by temporal and topological constraints, and can only be bilateral. We first study in this paper an abstract model of this problem, identifying conditions under which satisfying states can (or will) be reached. We rely in particular on a compositional consistency relation. We then detail a case study involving agents able to reason abductively (with Theorist), and study how demanding are the conditions required in this context. Different bilateral protocols are finally introduced and formally studied, to account for both compositional and noncompositional settings.

We consider multi-agent settings where a set of agents want to take a collective decision, based on their preferences over the possible candidate options. While agents have their initial inclination, they may interact and influence each other, and therefore modify their preferences, until hopefully they reach a stable state and declare their final inclination. At that point, a voting rule is used to aggregate the agents’ preferences and generate the collective decision. Recent work has modeled 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. We propose a way to model influence when agents express their preferences as CP-nets. We define two procedures for aggregating preferences in this scenario, by interleaving voting and influence convergence, and study their resistance to bribery.

Agents contributing to (online) debate systems often have different areas of expertise. This must be considered if we want to define a decision making process based on the output of such a system. Distinguishing agents on the basis of their areas of expertise also opens an interesting perspective: when a debate is deemed “controversial”, calling an additional expert may be a natural way to make the decision easier. We introduce possible definitions that capture these notions and we provide a preliminary analysis with the objective to help a designer find the “right” expert.

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.

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.

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.

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.

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.

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.

A multiagent system may be thought of as an artificial society of autonomous software agents and we can apply concepts borrowed from welfare economics and social choice theory to assess the social welfare of such an agent society. In this paper, we study an abstract negotiation framework where agents can agree on multilateral deals to exchange bundles of indivisible resources. We then analyse how these deals affect social welfare for different instances of the basic framework and different interpretations of the concept of social welfare itself. In particular, we show how certain classes of deals are both sufficient and necessary to guarantee that a socially optimal allocation of resources will be reached eventually.