PRIMA 2017: Principles and Practice of Multi-Agent Systems

Agents disagree in many situations and in many ways on their beliefs, preferences and goals. Abstract argumentation frameworks are a formal model to handle disagreement, which is represented as a conflict relation between a set of arguments. To solve the conflict and identify justified arguments, a single argumentation semantics is applied at a global level, under the assumption that the involved conflicts are essentially homogeneous. In the talk I will argue that disagreements are in general heterogeneous and thus should be treated in different ways according both to their nature and to the specific agents features. Accordingly, a general model of abstract argumentation will be discussed, able to handle heterogeneous disagreements by means of multiple argumentation semantics at a local level.

This paper provides a formalization of the other-condemning anger emotion which is a social type of anger triggered by the behaviour of other agents. Other-condemning anger responds to frustration of committed goals by others, and motivates goal-congruent behavior towards the blameworthy agents. Understanding this type of anger is crucial for modelling human behavior in social settings as well as designing socially aware artificial systems. We utilize existing psychological theories on other-condemning anger and propose a logical framework to formally specify this emotion. The logical framework is based on dynamic multi-agent logic with graded cognitive attitudes.

We study the use of a bipolar decision structure called BLF (bipolar leveled framework) in the context of collective decision making where the vote consists in giving factual information about a candidate which the group should accept or reject. A BLF defines the set of possible decision principles that may be used in order to evaluate the admissibility of a given candidate. A decision principle is a rule that relates some observations about the candidate to a given goal that the selection of this candidate may achieve or miss. The decision principles are ordered accordingly to the importance of the goal they support. Oppositions to decision principles are also described in the BLF under the form of observations that contradict the realization of the decision principles. We show how the use of a common BLF may reduce the impact of manipulation strategies in the context of group decision making.

We propose a framework for integrating belief revision with action narratives whose observations about properties of the world might be inaccurate. We define the notion of an acceptable revision of a narrative as a sequence of revision-candidate formulas which is used in revising the observations and creates a consistent narrative. We propose a more preferred relation among revisions and prove that this relation is transitive and irreflexive. We also define a notion of most preferred models of a narrative when likelihood of action occurrences are available and discuss an alternative characterization that takes into consideration preferences over revisions. We show that the more preferred relation among models is also transitive and irreflexive. We conclude the paper with a discussion on the related work.

We present a logic for reasoning about the interplay between belief, evidence and trust in a multi-agent setting. We call this logic DL-BET which stands for “Dynamic Logic of Belief, Evidence and Trust”. According to DL-BET, if the amount of evidence in support a given fact $$\varphi $$ and the ratio of evidence in support of $$\varphi $$ to the total amount of evidence in support of either $$\varphi $$ or its negation are sufficient then, as a consequence, one should be willing to believe $$\varphi $$. We provide a sound and complete axiomatization for the logic and illustrate its expressive power with the aid of a concrete example.

We give combinatorial, computational and simulation results for well-known distributed protocols for gossiping on completely connected networks. The protocols consist of: making any call ($$\mathsf {ANY}$$), only calling agents whose secret you do not know (“learn new secrets” $$\mathsf {LNS}$$), and never repeating calls (“call once” $$\mathsf {CO}$$). First, we show that these protocols all differ in what distributions of secrets are reachable by their execution. Next, we formulate $$\mathsf {ANY}$$ and $$\mathsf {LNS}$$ as Markov chains. We present an algorithm that generates the states of these Markov chains and computes the exact value of the expected duration of the protocols. Finally, we study the asymptotic behaviour of $$\mathsf {LNS}$$ via simulations, and compare this to the known result for $$\mathsf {ANY}$$.

In this paper, we introduce a discrete model for overlapping coalition formation called the multi-resource threshold task game (MR-TTG), which generalises the model introduced in [6]. Furthermore, we define the coalition structure generation (CSG) Problem for MR-TTGs. Towards the efficient solution of CSG problems for MR-TTGs, we provide two reductions to the well-known knapsack problems: the bounded multidimensional knapsack problem and the multiple-choice multidimensional knapsack problem. We then propose two branch and bound algorithms to compare between these reductions. Empirical evaluation shows that the latter reduction is more efficient in solving difficult instances of the problem.

Computationally Feasible Automated Mechanism Design (CFAMD) combines manual mechanism design and optimization.In CFAMD, we focus on a parameterized family of strategy-proof mechanisms, and then optimize within the family by adjusting the parameters. This transforms mechanism design (functional optimization) into value optimization, as we only need to optimize over the parameters.Under CFAMD, given a mechanism (characterized by a list of parameters), we need to be able to efficiently evaluate the mechanism’s performance. Otherwise, parameter optimization is computationally impractical when the number of parameters is large.We propose a new technique for speeding up CFAMD for worst-case objectives. Our technique builds up a set of worst-case type profiles, with which we can efficiently approximate a mechanism’s worst-case performance. The new technique allows us to apply CFAMD to cases where mechanism performance evaluation is computationally expensive.We demonstrate the effectiveness of our approach by applying it to the design of competitive VCG redistribution mechanism for public project problem. This is a well studied mechanism design problem. Several competitive mechanisms have already been proposed. With our new technique, we are able to achieve better competitive ratios than previous results.

Coalition Structure Generation (CSG), a main research issue in the domain of coalition games, involves partitioning agents into exhaustive and disjoint coalitions to optimize the social welfare. The advent of compact representation schemes, such as Partition Decision Trees (PDTs), promotes the efficiency of solving CSG problems.This paper studies the CSG problem for partition function games (PFGs) which are coalitional games with externalities. In PFGs, each value of a coalition depends on how the other agents are partitioned. We apply PDTs to represent PFGs and present two methods to solve CSG problems: a depth-first branch-and-bound algorithm and MaxSAT encoding.

We consider the problem of locating facilities on a discrete acyclic graph, where agents’ locations are publicly known and the agents are requested to report their demands, i.e., which facilities they want to access. In this paper, we study the effect of manipulations by agents that utilize vacant vertices. Such manipulations are called rename or false-name manipulations in game theory and mechanism design literature. For locating one facility on a path, we carefully compare our model with traditional ones and clarify their differences by pointing out that some existing results in the traditional model do not carry over to our model. For locating two facilities, we analyze the existing and new mechanisms from a perspective of approximation ratio and provide non-trivial lower bounds. Finally, we introduce a new mechanism design model where richer information is available to the mechanism designer and show that under the new model false-name-proofness does not always imply population monotonicity.

The handwritten/printed text discrimination problem is a decision problem usually solved after a binarization of grey level or color images. The decision is usually made at the connected component level of a filtered image. These image components are labeled as printed or handwritten. Each component is represented as a point in a n dimensional space based on the use of n different features. In this paper we present the transformation of a (state of the art) traditional system dealing with the handwritten/printed text discrimination problem to an agent-based system. In this system we associate two different agents with the two different points of view (i.e. linearity and regularity) considered in the baseline system for discriminating a text, based on four (two for each agent) different features. We are also using argumentation for modeling the decision making mechanisms of the agents. We then present experimental results that compare the two systems by using images of the IAM handwriting database. These results empirically prove the significant improvement we can have by using the agent-based system.

Medical image segmentation is a difficult task, essentially due to the inherent complexity of human body structures and the acquisition methods of this kind of images. Manual segmentation of medical images requires advance radiological expertize and is also very time-consuming. Several methods have been developed to automatize medical image segmentation, including multi-agent approaches. In this paper, we propose a new multi-agent approach based on a set of autonomous and interactive agents that integrates an enhanced region growing algorithm. It does not require any prior knowledge. This approach was implemented and experiments were performed on brain MRI simulated images and the obtained results are promising.

We consider multi-robot scenarios where robots ask for operator interventions when facing difficulties. As the number of robots increases, the operator quickly becomes a bottleneck for the system. Queue theory can be effectively used to optimize the scheduling of the robots’ requests. Here we focus on a specific queuing model in which the robots decide whether to join the queue or balk based on a threshold value. Those thresholds are a trade-off between the reward earned by joining the queue and cost of waiting in the queue. Though such queuing models reduce the system’s waiting time, the cost of balking usually is not considered. Our aim is thus to find appropriate balking strategies for a robotic application to reduce the waiting time considering the expected balking costs. We propose using a Q-learning approach to compute balking thresholds and experimentally demonstrate the improvement of team performance compared to previous queuing models.

In this paper, we propose a generic specification framework for argumentation dialogue protocols in an open multi-agent system. The specification framework is based on reusable elements – dialogue templates – which are realized as an open-source implementation. We provide operational semantics and show formally how templates can be used to determine the possible dialogues. Furthermore, for open multi-agent systems we need to be able to specify peer-to-peer dialogues, where the agents themselves are in a position to know whether their dialogue actions are legal according to the protocol without relying on central entities, institutes or middleware. We prove that all protocols that can be specified in our framework are peer-to-peer suitable.

Agents may use different ontologies for representing knowledge and take advantage of alignments between ontologies in order to communicate. Such alignments may be provided by dedicated algorithms, but their accuracy is far from satisfying. We already explored operators allowing agents to repair such alignments while using them for communicating. The question remained of the capability of agents to craft alignments from scratch in the same way. Here we explore the use of expanding repair operators for that purpose. When starting from empty alignments, agents fails to create them as they have nothing to repair. Hence, we introduce the capability for agents to risk adding new correspondences when no existing one is useful. We compare and discuss the results provided by this modality and show that, due to this generative capability, agents reach better results than without it in terms of the accuracy of their alignments. When starting with empty alignments, alignments reach the same quality level as when starting with random alignments, thus providing a reliable way for agents to build alignment from scratch through communication.

Frequency opponent modeling is one of the most widely used opponent modeling techniques in automated negotiation, due to its simplicity and its good performance. In fact, it outperforms even more complex mechanisms like Bayesian models. Nevertheless, the classical frequency model does not come without its own assumptions, some of which may not always hold in many realistic settings. This paper advances the state of the art in opponent modeling in automated negotiation by introducing a novel frequency opponent modeling mechanism, which soothes some of the assumptions introduced by classical frequency approaches. The experiments show that our proposed approach outperforms the classic frequency model in terms of evaluation of the outcome space, estimation of the Pareto frontier, and accuracy of both issue value evaluation estimation and issue weight estimation.

Optimizing within the affine maximizer auctions (AMA) is an effective approach for revenue maximizing mechanism design. The AMA mechanisms are strategy-proof and individually rational (if the agents’ valuations for the outcomes are nonnegative). Every AMA mechanism is characterized by a list of parameters. By focusing on the AMA mechanisms, we turn mechanism design into a value optimization problem, where we only need to adjust the parameters. We propose a linear programming based heuristic for optimizing within the AMA family. We apply our technique to revenue maximizing mechanism design for zero-day exploit markets. We show that due to the nature of the zero-day exploit markets, if there are only two agents (one offender and one defender), then our technique generally produces a near optimal mechanism: the mechanism’s expected revenue is close to the optimal revenue achieved by the optimal strategy-proof and individually rational mechanism (not necessarily an AMA mechanism).

This work concerns the challenge of computational accountability in a multiagent setting where agents interact inside organizations. We illustrate the requirements to realize accountability with the help of a scenario. Then, we provide a characterization of computational accountability in terms of a few general principles. We introduce and explain the ADOPT accountability protocol and show how it satisfies these principles with the help of model checking.

Artificial institutions usually consider that the regulation of the behaviour of the agents is expressed by norms that refer to an institutional reality, that is an institutional interpretation of the environment in which the agents are situated. To be applied on real systems, however, artificial institutions need to advance from the theory to the practice. Such step requires to conceive the institutional platform components that are in charge of building the institutional reality used in the normative regulation of the system. Such components must be connectable to the heterogeneous elements composing the environment and must also be able to accommodate the different normative platforms that regulate the system. This paper proposes the architecture of an institutional platform having these features. It is shown also how the proposed institutional platform can be linked to environmental and normative ones.

In this paper, we study normative multi-agent systems from a supervisory control theory perspective. Concretely, we show how to model three well-known types of norm enforcement mechanisms by adopting well-studied supervisory control theory techniques for discrete event systems. Doing so provides a semantics for normative multi-agent systems rooted in formal languages and the ability to automatically synthesize SCT-based norm enforcement mechanisms for special, but still fairly expressive, type of systems and properties.

Social influence is the process in which an agent is under pressure to form her opinion on an issue based on the opinions expresses by her peers. An obvious reaction to social influence is to change ones opinions to conform to the pressure. The study of formal models of social influence has been drawing attention in the literature. A comparatively under-explored aspect of social influence is its role as an instrument of social network change. Agents with an eclectic milieu of peers might find themselves under conflicting social pressures. In this case to conform to social influence by changing one’s beliefs is no longer an option and the agent may seek to distance herself from some of her peers to relieve the pressure. We build a formal model of social influence that allows us to study social influence as a source of conflict and an instrument of network change. Within our framework different models of social influence can be defined but also compared to each other.

Opinion polls are used in a variety of settings to assess the opinions of a population, but they mostly conceal the reasoning behind these opinions. Argumentation, as understood in AI, can be used to evaluate opinions in dialectical exchanges, transparently articulating the reasoning behind the opinions. We give a method integrating argumentation within opinion polling to empower voters to add new statements that render their opinions in the polls individually rational while at the same time justifying them. We then show how these poll results can be amalgamated to give a collectively rational set of voters in an argumentation framework. Our method relies upon Quantitative Argumentation Debate for Voting (QuAD-V) frameworks, which extend QuAD frameworks (a form of bipolar argumentation frameworks in which arguments have an intrinsic strength) with votes expressing individuals’ opinions on arguments.

Bipolar Argumentation Frameworks (BAFs) encompass both attacks and supports among arguments. We study different semantic interpretations of support in BAFs, particularly necessary and deductive support, as well as argument coalitions and a recent proposal by Gabbay. We analyse the relationship of these different notions of support in BAFs with the semantics of a well established structured argumentation formalism, Assumption-Based Argumentation (ABA), which predates BAFs. We propose natural mappings from BAFs into a restricted class of (non-flat) ABA frameworks, which we call bipolar, and prove that the admissible and preferred semantics of these ABA frameworks correspond to the admissible and preferred semantics of the various approaches to BAFs. Motivated by the definition of stable semantics for BAFs, we introduce a novel set-stable semantics for ABA frameworks, and prove that it corresponds to the stable semantics of the various approaches to BAFs. Finally, as a by-product of modelling various approaches to BAFs in bipolar ABA, we identify precise semantic relationships amongst all approaches we consider.

We define a generic notion of abstract games of argumentation strategy for (attack-only and bipolar) argumentation frameworks, which are zero-sum games whereby two players put forward sets of arguments and get a reward for their combined choices. The value of these games, in the classical game-theoretic sense, can be used to define measures of (quantitative) game-theoretic strength of arguments, which are different depending on whether either or both players have an “agenda” (i.e. an argument they want to be accepted). We show that this general scheme captures as a special instance a previous proposal in the literature (single agenda, attack-only frameworks), and seamlessly supports the definition of a spectrum of novel measures of game-theoretic strength where both players have an agenda and/or bipolar frameworks are considered. We then discuss the applicability of these instances of game-theoretic strength in different contexts and analyse their basic properties.

We present ABAplus, a system that implements reasoning with the argumentation formalism ABA$$^+$$. ABA$$^+$$ is a structured argumentation formalism that extends Assumption-Based Argumentation (ABA) with preferences and accounts for preferences via attack reversal. ABA$$^+$$ also admits as instance Preference-based Argumentation which accounts for preferences by reversing attacks in abstract argumentation (AA). ABAplus readily implements attack reversal in both AA and ABA-style structured argumentation. ABAplus affords computation, visualisation and comparison of extensions under five argumentation semantics. It is available both as a stand-alone system and as a web application.

Ontologies represent principled, formalised descriptions of agents’ conceptualisations of a domain. For a community of agents, these descriptions may significantly differ. We propose an aggregative view of the integration of ontologies based on Judgement Aggregation (JA). Agents may vote on statements of the ontologies, and we aim at constructing a collective, integrated ontology, that reflects the individual conceptualisations as much as possible. As several results in JA show, many attractive and widely used aggregation procedures are prone to return inconsistent collective ontologies. We propose to solve the possible inconsistencies in the collective ontology by applying suitable weakenings of axioms that cause inconsistencies.

Inspired from the ideas such as “algorithm portfolio”, “mixture of experts”, and “genetic algorithm”, this paper presents two novel negotiation strategies, which combine multiple negotiation experts to decide what to bid and what to accept during the negotiation. In the first approach namely incremental portfolio, a bid is constructed by asking each negotiation agent’s opinion in the portfolio and picking one of the suggestions stochastically considering the expertise levels of the agents. In the second approach namely crossover strategy, each expert agent makes a bid suggestion and a majority voting is used on each issue value to decide the bid content. The proposed approaches have been evaluated empirically and our experimental results showed that the crossover strategy outperformed the top five finalists of the ANAC 2016 Negotiation Competition in terms of the obtained average individual utility.

As we engage in a debate with other parties, it is usual that several subjects might come under discussion. In this work, we propose an extension of classic abstract argumentation frameworks which includes a set of interrelated topics decorating arguments. These topics represent what the arguments are addressing and provide a supporting structure for the analysis of multi-topic argumentation. A notion of “proximity” of an argument to the focus of the debate is introduced, leading to a notion of distance between the topics of the arguments, which is used for proximity-based semantic elaborations.

Urban transportation systems have received a special interest in the last few years due to the necessity to reduce congestion, air pollution and acoustic contamination in today’s cities. Bike sharing systems have been proposed as an interesting solution to deal with these problems. Nevertheless, shared vehicle schemes also arise problems that must be addressed such as the vehicle distribution along time and across space in the city. Differently to classic approaches, we propose the architecture for a muti-agent system that tries to improve the efficiency of bike sharing systems by introducing user-driven balancing in the loop. The rationale is that of persuading users to slightly deviate from their origins/destinations by providing appropriate arguments and incentives, while optimizing the overall balance of the system. In this paper we present two of the proposed system’s modules. The first will allow us to predict bike demand in different stations. The second will score stations and alternative routes. This modules will be used to predict the most appropriate offers for users and try to persuade them.

The quality of service and efficiency of labour utilization in emergency service fleets, such as police, fire departments, and emergency medical services (EMS), depends, among other things, on the efficiency of work break scheduling. The workload of such fleets usually cannot be forecasted with certainty and its urgency requires an immediate response. However, prolonged focused work periods decrease efficiency with related decline of attention and performance. Therefore, break schedule should be regularly updated as the work shift progresses to allow frequent and sufficiently long time for rest. In this paper, we propose a distributed and dynamic work break scheduling algorithm for crews in emergency service vehicle fleets. Based on the historical intervention data, the algorithm rearranges vehicles’ crews’ work breaks in a manner considering individual crews’ preferences. Moreover, it dynamically reallocates stand-by vehicles for best coverage of a region of interest. We analyze the proposed algorithm and show its performance and efficiency on the EMS use-case.

This paper describes an agent-based, incentive-driven, and privacy-preserving information sharing framework. Main contribution of the paper is to give the data provider agent an active role in the information sharing process and to change the currently asymmetric position between the provider and the requester of data and information (DI) to the favor of the DI provider. Instead of a binary yes/no answer to the requester’s data request and the incentive offer, the provider may negotiate about excluding from the requested DI bundle certain pieces of DI with high privacy value, and/or ask for a different type of incentive. We show the presented approach on a use case. However, the proposed architecture is domain independent.

Crowdsourcing is becoming increasingly popular in various tasks. Although the cost incurred by workers in crowdsourcing is lower than that by experts, the possibility of errors in the former generally exceeds that of the latter. One of the important approaches to quality control of crowdsourcing is based on mechanism design, which has been used to design a game’s rules/protocols so that agents have incentives to truthfully declare their preferences, and designers can select socially advantageous outcomes. Thus far, mechanism design has been conducted by professional economists or computer scientists. However, it is difficult to recruit professional mechanism designers, and developed mechanisms tend to be difficult for people to understand. Crowdsourcing requesters have to determine how to assign tasks to workers and how to reward them. Therefore, a requester can be considered to be an “amateur mechanism designer”. This paper introduces the “wisdom of the crowd” approach to mechanism design, i.e., using crowdsourcing to explore the large design space of incentive mechanisms. We conducted experiments to show that crowd mechanism designers can develop sufficiently diverse candidates for incentive mechanisms and they can choose appropriate mechanisms given a set of candidate mechanisms. We also studied how the designers’ theoretical, economic, and social tendencies, as well as their views on the world, justifiably affect the mechanisms they propose.

In this paper, we investigate the question of how to characterize “fault tolerance” in cooperative agents. It is generally admitted that cooperating agents can achieve tasks that they could not achieve without cooperation. Nevertheless, cooperating agents can have “Achilles’ heels”, a cooperative encounter can eventually fail to achieve its tasks because of the collapse of a single agent. The contribution of this paper is the study of how cooperating agents are affected by dependability issues. Specifically, our objectives are twofold: to formally define the concepts of dependability in cooperative encounters, and to analyze the computational complexity of devising dependable cooperative encounters.

Groups of agents in multi-agent systems may have to cooperate to solve tasks efficiently, and coordinating such groups is an important problem in the field of artificial intelligence. In this paper, we consider the problem of forming disjoint coalitions and assigning them to independent tasks simultaneously, and present an anytime algorithm that efficiently solves the simultaneous coalition structure generation and task assignment problem. This NP-complete combinatorial optimization problem has many real-world applications, including forming cross-functional teams aimed at solving tasks. To evaluate the algorithm’s performance, we extend established methods for synthetic problem set generation, and benchmark the algorithm using randomized data sets of varying distribution and complexity. Our results show that the presented algorithm efficiently finds optimal solutions, and generates high quality solutions when interrupted prior to finishing an exhaustive search. Additionally, we apply the algorithm to solve the problem of assigning agents to regions in a commercial computer-based strategy game, and empirically show that our algorithm can significantly improve the coordination and computational efficiency of agents in a real-time multi-agent system.

This paper addresses how to identify attack relations on the basis of lay arguers’ acceptability-judgments for natural language arguments. We characterize argument-based reasoning by three Bayesian network models (coherent, decisive, and positional). Each model yields a different attack relation-estimate. Subsequently, we analyze to which extent estimates are consistent with, and so could potentially predict, lay arguers’ acceptability-judgments. Evaluation of a model’s predictive ability relies on anonymous data collected online (N = 73). After applying leave-one-out cross-validation, in the best case models achieve an average area under the receiver operating curve (AUC) of .879 and an accuracy of .786. Though the number of arguments is small (N = 5), this shows that argument-based Bayesian inference can in principle estimate attack relations.

In multi-agent systems, a multilateral closed negotiation, where the opponent’s strategy and utility are closed, is an important class of automated negotiations. However, most existing negotiation protocols haven’t addressed the private information revealed by agents. During negotiations, such private information as agents preferences must be revealed fairly because each agent loses utility in them. In this paper, we propose a negotiation protocol that addresses the fairness of revealing each agent’s private information. First, we propose a new measure of revealing each agent’s private information, which is based on the accuracy of estimating opponents’ utility functions. Next, the negotiation protocol adjusts the number of offers by each agent based on a new measure. This adjustment encourages agents who reveal less private information than other agents to reveal more offers. In the experiments, we compared and investigated the fairness of revealing private information by tournaments among state-of-the-art agents in ANAC2016 using our proposed negotiation protocol. The experimental results demonstrate that our proposed negotiation protocol with the adjustment improves the fairness of the revealed private information and a trade-off between the revealed private information and individual utility exists.