This paper addresses the problem of ensuring that autonomous learning agents align with multiple moral values. Specifically, we present the theoretical principles and algorithmic tools necessary for creating an environment where we ensure that the agent learns a behaviour aligned with multiple moral values while striving to achieve its individual objective. To address this value alignment problem, we adopt the Multi-Objective Reinforcement Learning framework and propose a novel algorithm that combines techniques from Multi-Objective Reinforcement Learning and Linear Programming. In addition, we illustrate our value alignment process with an example involving an autonomous vehicle. Here, we demonstrate that the agent learns to behave in alignment with the ethical values of safety, achievement, and comfort, with achievement representing the agent’s individual objective. Such ethical behaviour differs depending on the ordering between values. We also use a synthetic multi-objective environment to evaluate the computational costs of guaranteeing ethical learning as the number of values increases.

This paper introduces the Approximate Ethical Embedding Process, an algorithm for automating the design of ethical environments for learning agents. Our algorithm helps build environments wherein multiple agents learn policies that align with an ethical (moral) value while simultaneously pursuing their individual objectives. Therefore, we contribute to endowing environment designers with algorithmic tools for building ethical environments. We demonstrate the ethical design process for two different settings of an environment where agents have to adhere to beneficence to promote the collective survival of the population. Our experiments show that our approximate embedding process successfully generates environments that incentivise the learning of value-aligned policies.

Abstract This paper tackles the open problem of value alignment in multi-agent systems. In particular, we propose an approach to build an ethical environment that guarantees that agents in the system learn a joint ethically-aligned behaviour while pursuing their respective individual objectives. Our contributions are founded in the framework of Multi-Objective Multi-Agent Reinforcement Learning. Firstly, we characterise a family of Multi-Objective Markov Games (MOMGs), the so-called ethical MOMGs, for which we can formally guarantee the learning of ethical behaviours. Secondly, based on our characterisation we specify the process for building single-objective ethical environments that simplify the learning in the multi-agent system. We illustrate our process with an ethical variation of the Gathering Game, where agents manage to compensate social inequalities by learning to behave in alignment with the moral value of beneficence.

Multi-objective reinforcement learning (MORL) is an excellent framework for multi-objective sequential decision-making. MORL employs a utility function to aggregate multiple objectives into one that expresses a user's preferences. However, MORL still misses two crucial theoretical analyses of the properties of utility functions: (1) a characterisation of the utility functions for which an associated optimal policy exists, and (2) a characterisation of the types of preferences that can be expressed as utility functions. As a result, we formally characterise the families of preferences and utility functions that MORL should focus on: those for which an optimal policy is guaranteed to exist. We expect our theoretical results to promote the development of novel MORL algorithms that exploit our theoretical findings.

We adopt an emerging and prominent vision of human-centred Artificial Intelligence that requires building trustworthy intelligent systems. Such systems should be capable of dealing with the challenges of an interconnected, globalised world by handling plurality and by abiding by human values. Within this vision, pluralistic value alignment is a core problem for AI– that is, the challenge of creating AI systems that align with a set of diverse individual value systems. So far, most literature on value alignment has considered alignment to a single value system. To address this research gap, we propose a novel method for estimating and aggregating multiple individual value systems. We rely on recent results in the social choice literature and formalise the value system aggregation problem as an optimisation problem. We then cast this problem as an ℓp-regression problem. Doing so provides a principled and general theoretical framework to model and solve the aggregation problem. Our aggregation method allows us to consider a range of ethical principles, from utilitarian (maximum utility) to egalitarian (maximum fairness). We illustrate the aggregation of value systems by considering real-world data from two case studies: the Participatory Value Evaluation process and the European Values Study. Our experimental evaluation shows how different consensus value systems can be obtained depending on the ethical principle of choice, leading to practical insights for a decision-maker on how to perform value system aggregation.

Abstract The School-Work Alternation (SWA) programme was developed (under a European Commission call) to bridge the gaps and establish a well-tuned partnership between education and the job market. This work details the development of the AI4Citizen pilot, an AI software suite designed to support the SWA programme. The AI4Citizen pilot, developed within the H2020 AI4EU project, offers AI tools to automate and enhance the current SWA process. At the same time, the AI4Citizen pilot offers novel tools to support the complex problem of allocating student teams to internship programs, promoting collaborative learning and teamwork skills acquisition. Notably, the AI4Citizen pilot corresponds to a pipeline of AI tools, integrating existing and novel technologies. Our exhaustive empirical analysis confirms that the AI4Citizen pilot can alleviate the difficulties of current processes in the SWA, and therefore it is ready for real-world deployment.

Decision makers are commonly challenged with comparing, and ultimately ranking, elements with regards to the degree to which they satisfy multiple criteria and in terms of their own preferences. This calls for a new decision making framework, which we formally present here. Within such a framework, we present multi-criteria lex-cel: a new method for ranking single elements. Furthermore, we formally establish that our contributions generalise recent results in the social choice literature. We also illustrate our contributions through a case study that poses an ethical decision-making problem.

In this paper we propose a new model to represent human debates and methods to obtain collective conclusions from them. This model overcomes two drawbacks of existing approaches. First, our model does not assume that participants agree on the structure of the debate. It does this by allowing participants to express their opinion about all aspects of the debate. Second, our model does not assume that participants’ opinions are rational, an assumption that significantly limits current approaches. Instead, we define a weaker notion of rationality that characterises coherent opinions, and we consider different scenarios based on the coherence of individual opinions and the level of consensus. We provide a formal analysis of different opinion aggregation functions that compute a collective decision based on the individual opinions and the debate structure. In particular, we demonstrate that aggregated opinions can be coherent even if there is a lack of consensus and individual opinions are not coherent. We conclude with an empirical evaluation demonstrating that collective opinions can be computed efficiently for real-sized debates.

AI research is being challenged with ensuring that autonomous agents learn to behave ethically, namely in alignment with moral values. A common approach, founded on the exploitation of Reinforcement Learning techniques, is to design environments that incentivise agents to behave ethically. However, to the best of our knowledge, current approaches do not theoretically guarantee that an agent will learn to behave ethically. Here, we make headway along this direction by proposing a novel way of designing environments wherein it is formally guaranteed that an agent learns to behave ethically while pursuing its individual objectives. Our theoretical results develop within the formal framework of Multi-Objective Reinforcement Learning to ease the handling of an agent's individual and ethical objectives. As a further contribution, we leverage on our theoretical results to introduce an algorithm that automates the design of ethical environments.

Software model checking has recently started to be applied in the verification of programmable logic controller (PLC) programs. It works efficiently when the number of input variables is limited, their interaction is small and, thus, the number of states the program can reach is not large. As observed in the large code base of the CERN industrial PLC applications, this is usually not the case: it thus leads to the well-known state-space explosion problem, making it impossible to perform model checking. One of the main reasons that causes state-space explosion is the inclusion of numeric variables due to the wide range of values they can take. In this paper, we propose an approach to discretize PLC input numeric variables (modelled as non-deterministic). This discretization is complemented with a set of transformations on the control-flow automaton that models the PLC program so that no extra behaviours are added. This approach is then quantitatively evaluated with a set of empirical tests using the PLC model checking framework PLCverif and three different state-of-the-art model checkers (CBMC, nuXmv, and Theta), showing beneficial results for BDD-based model checkers.

Abstract Decision makers can often be confronted with the need to select a subset of objects from a set of candidate objects by just counting on preferences regarding the objects’ features. Here we formalise this problem as the dominant set selection problem. Solving this problem amounts to finding the preferences over all possible sets of objects. We accomplish so by: (i) grounding the preferences over features to preferences over the objects themselves; and (ii) lifting these preferences to preferences over all possible sets of objects. This is achieved by combining lex-cel –a method from the literature—with our novel anti-lex-cel method, which we formally (and thoroughly) study. Furthermore, we provide a binary integer program encoding to solve the problem. Finally, we illustrate our overall approach by applying it to the selection of value-aligned norm systems.

Peer-to-peer ridesharing enables people to arrange one-time rides with their own private cars, without the involvement of professional drivers. It is a prominent collective intelligence application producing significant benefits both for individuals (reduced costs) and for the entire community (reduced pollution and traffic). Despite these very promising potential advantages, the percentage of users who currently adopt ridesharing solutions is very low, well below the adoption rate required to achieve said benefits. One of the reasons of this insufficient engagement by the public is the lack of effective incentive policies by regulatory authorities, who are not able to estimate the costs and the benefits of a given ridesharing adoption policy. Here we address these issues by (i) developing a novel algorithm that makes large-scale, real-time peer-to-peer ridesharing technologically feasible; and (ii) exhaustively quantifying the impact of different ridesharing scenarios in terms of environmental benefits (i.e., reduction of CO2 emissions, noise pollution, and traffic congestion) and quality of service for the users. Our analysis on a real-world dataset shows that major societal benefits are expected from deploying peer-to-peer ridesharing depending on the trade-off between environmental benefits and quality of service. Results on a real-world dataset show that our approach can produce reductions up to a 70.78% in CO2 emissions and up to 80.08% in traffic congestion.

Norms constitute regulative mechanisms extensively enacted in groups, organisations, and societies. However, 'choosing the right norms to establish' constitutes an open problem that requires the consideration of a number of constraints (such as norm relations) and preference criteria (e.g over involved moral values). This paper advances the state of the art in the Normative Multiagent Systems literature by formally defining this problem and by proposing its encoding as a linear program so that it can be automatically solved.

In education, student teams are composed aiming at completing academic tasks and co-learning. Key factors influencing team performance are individual competencies, personality and gender. In this paper, we present a computational model to compose proficient and congenial teams based on students' personalities, gender, and competencies to perform tasks of different nature. Our model, called synergistic team composition, extends Wilde's post-Jungian method, which solely employs individuals' personalities and gender. In addition to formally present the synergistic team composition problem, we develop an approximate algorithm to solve it. That is, an algorithm that partitions student groups into teams that are diverse in competencies, personality and gender. Finally, we discuss our positive empirical results on student performance.

Within the area of multi-agent systems, normative systems are a widely used framework for the coordination of interdependent activities. A crucial problem associated with normative systems is that of synthesising norms that will effectively accomplish a coordination task and that the agents will comply with. Many works in the literature focus on the on-line synthesis of a single, evolutionarily stable norm (convention) whose compliance forms a rational choice for the agents and that effectively coordinates them in one particular coordination situation that needs to be identified and modelled as a game in advance. In this work, we introduce a framework for the automatic off-line synthesis of evolutionarily stable normative systems that coordinate the agents in multiple interdependent coordination situations that cannot be easily identified in advance nor resolved separately. Our framework roots in evolutionary game theory. It considers multi-agent systems in which the potential conflict situations can be automatically enumerated by employing MAS simulations along with basic domain information. Our framework simulates an evolutionary process whereby successful norms prosper and spread within the agent population, while unsuccessful norms are discarded. The outputs of such a natural selection process are sets of codependent norms that, together, effectively coordinate the agents in multiple interdependent situations and are evolutionarily stable. We empirically show the effectiveness of our approach through empirical evaluation in a simulated traffic domain.

Summary The coalition structure generation problem is well known in the area of multi‐agent systems. Its goal is to establish coalitions between agents while maximizing the global welfare. Among the existing different algorithms designed to solve the coalition structure generation problem, DP and IDP are the ones with smaller temporal complexity. After analyzing the operation of the dynamic programming and improved dynamic programming algorithms, we have identified which are the most frequent operations and propose an optimized method. In addition, we study and implement a method for dividing the work into different threads. To describe incremental improvements of the algorithm design, we first compare performance of an improved single central processing unit core version where we obtain speedups ranging from 7 × to 11 × . Then, we describe the best resource use in a multi‐thread optimized version where we obtain an additional 7.5 × speedup running in a 12‐core machine.

Coalition formation typically involves the coming together of multiple, heterogeneous, agents to achieve both their individual and collective goals. In this article, we focus on a special case of coalition formation known as Graph-Constrained Coalition Formation (GCCF) whereby a network connecting the agents constrains the formation of coalitions. We focus on this type of problem given that in many real-world applications, agents may be connected by a communication network or only trust certain peers in their social network. We propose a novel representation of this problem based on the concept of edge contraction, which allows us to model the search space induced by the GCCF problem as a rooted tree. Then, we propose an anytime solution algorithm (Coalition Formation for Sparse Synergies (CFSS)), which is particularly efficient when applied to a general class of characteristic functions called m + a functions. Moreover, we show how CFSS can be efficiently parallelised to solve GCCF using a nonredundant partition of the search space. We benchmark CFSS on both synthetic and realistic scenarios, using a real-world dataset consisting of the energy consumption of a large number of households in the UK. Our results show that, in the best case, the serial version of CFSS is four orders of magnitude faster than the state of the art, while the parallel version is 9.44 times faster than the serial version on a 12-core machine. Moreover, CFSS is the first approach to provide anytime approximate solutions with quality guarantees for very large systems of agents (i.e., with more than 2,700 agents).

Most normative systems make use of explicit representations of norms (namely, obligations, prohibitions, and permissions) and associated mechanisms to support the self-regulation of open societies of self-interested and autonomous agents. A key problem in research on normative systems is that of how to synthesise effective and efficient norms. Manually designing norms is time consuming and error prone. An alternative is to automatically synthesise norms. However, norm synthesis is a computationally complex problem. We present a novel online norm synthesis mechanism, designed to synthesise compact normative systems. It yields normative systems composed of concise (simple) norms that effectively coordinate a multiagent system (MAS) without lapsing into overregulation. Our mechanism is based on a central authority that monitors a MAS, searching for undesired states. After detecting undesirable states, the central authority then synthesises norms aimed to avoid them in the future. We demonstrate the effectiveness of our approach through experimental results.

This special issue focuses on optimization in multi-agent systems (OptMASs), a sub-field of MASs research that poses novel research challenges. OptMASs is concerned with solving MAS problems using optimization techniques that cannot ignore the active participation of the actors in the system. Therefore, OptMASs must cope with the distributed nature of MASs, where agents reside on different computational units that may be prone to failures and have different computation/communication capabilities. Furthermore, it must consider that agents may be acting on behalf of different stakeholders, each with its own aims and objectives. Taking into account such assumptions leads to very hard optimization problems that are substantially different from problems traditionally dealt with in other areas. The objective of this special issue is to provide a detailed sample of recent advances in algorithms, theories and applications in the field of OptMASs. The seven papers included in this special issue are intended to outline the current state of the art in the field.

In this article we tackle the problem of maximizing cooperation among self-interested agents in a resource exchange environment. Our main concern is the design of mechanisms for maximizing cooperation among self-interested agents in a way that their profits increase by exchanging or trading with resources. Although dynamic coalition formation and partner switching (rewiring) have been shown to promote the emergence and maintenance of cooperation for self-interested agents, no prior work in the literature has investigated whether merging both mechanisms exhibits positive synergies that lead to increase cooperation even further. Therefore, we introduce and analyze a novel dynamic coalition formation mechanism, that uses partner switching, to help self-interested agents to increase their profits in a resource exchange environment. Our experiments show the effectiveness of our mechanism at increasing the agents’ profits, as well as the emergence of trading as the preferred behavior over different types of complex networks.

Adaptive organisation-centred multi-agent systems can dynamically modify their organisational components to better accomplish their goals. Our research line proposes an abstract distributed architecture (2-LAMA) to endow an organisation with adaptation capabilities. This article focuses on regulation-adaptation based on a machine learning approach, in which adaptation is learned by applying a tailored case-based reasoning method. We evaluate the robustness of the system when it is populated by non compliant agents. The evaluation is performed in a peer-to-peer sharing network scenario. Results show that our proposal significantly improves system performance and can cope with regulation violators without incorporating any specific regulation-compliance enforcement mechanisms.

Supply Chain Formation (SCF) is the process of determining the participants in a supply chain, who will exchange what with whom, and the terms of the exchanges. Decentralized SCF appears as a highly intricate task because agents only possess local information and have limited knowledge about the capabilities of other agents. The decentralized SCF problem has been recently cast as an optimization problem that can be efficiently approximated using max-sum loopy belief propagation. Along this direction, in this paper we propose a novel encoding of the problem into a binary factor graph (containing only binary variables) as well as an alternative algorithm. We empirically show that our approach allows to significantly increase scalability, hence allowing to form supply chains in market scenarios with a large number of participants and high competition.

Just as conventional institutions are organisational structures for coordinating the activities of multiple interacting individuals, electronic institutions provide a computational analogue for coordinating the activities of multiple interacting software agents. In this paper, we argue that open multi-agent systems can be effectively designed and implemented as electronic institutions, for which we provide a comprehensive computational model. More specifically, the paper provides an operational semantics for electronic institutions, specifying the essential data structures, the state representation and the key operations necessary to implement them. We specify the agent workflow structure that is the core component of such electronic institutions and particular instantiations of knowledge representation languages that support the institutional model. In so doing, we provide the first formal account of the electronic institution concept in a rigorous and unambiguous way.

Mixed multi-unit combinatorial auctions (MMUCAs) offer a high potential to be employed for the automated assembly of supply chains of agents. However, in order for mixed auctions to be effectively applied to supply chain formation, we must ensure computational tractability and reduce bidders' uncertainty. With this aim, we introduce Sequential Mixed Auctions (SMAs), a novel auction model conceived to help bidders collaboratively discover supply chain structures. Thus, an SMA allows bidders progressively build a supply chain structure through successive auction rounds. Moreover, the incremental nature of an SMA provides its participants with valuable information at the end of each auction round to guide their bidding. Finally, we empirically show that SMAs significantly reduce the computational effort required by MMUCA at the expense of a slight decrease in the auctioneer's revenue.

Sensor networks (SNs) have arisen as one of the most promising technologies for the next decades. The recent emergence of small and inexpensive sensors based upon microelectromechanical systems ease the development and proliferation of this kind of networks in a wide range of actual-world applications. Multiagent systems (MAS) have been identified as one of the most suitable technologies to contribute to the deployment of SNs that exhibit flexibility, robustness and autonomy. The purpose of this survey is 2-fold. On the one hand, we review the most relevant contributions of agent technologies to this emerging application domain. On the other hand, we identify the challenges that researchers must address to establish MAS as the key enabling technology for SNs.

Sensor networks (SN) are rapidly becoming the tool of choice for monitoring. Their versatility makes them useful in numerous and diverse application domains. However, most SN deployments assume that the area and events to monitor/control are well known/understood at design time. Thus, sensors' configurations can be defined prior to their deployment. Nevertheless, when the purpose of an SN is to monitor the events of an uncharted environment, where the distribution and nature of events is uncertain, it is rather intricate to configure its sensors at design time. Instead, sensors should be able to self-configure at run time. In this paper, we propose a low-cost (in terms of energy and computation) collective approach that allows the sensors in an SN to collaboratively search for their most appropriate configurations only using their local knowledge. We empirically show that our approach can help sensors efficiently monitor environments where various dynamic events exist.

In this paper we formulate a novel Divide-and-Coordinate (DaC) algorithm, the so-called Egalitarian Utilities Divide-and-Coordinate (EU-DaC) algorithm. The Divide-and-Coordinate (DaC) framework [3] is a family of bounded DCOP algorithms that solve DCOPs by exploiting the concept of agreement. The intuition behind EU-DaC is that agents get closer to an agreement, on the optimal solution, when they communicate the local max-marginals utilities for their assignments instead of only their preferred assignments. We provide empirical evidence supporting this hypothesis as well as illustrating the competitiveness of EU-DaC.

We study worst-case bounds on the quality of any fixed point assignment of the max-product algorithm for Markov Random Fields (MRF). We start proving a bound independent of the MRF structure and parameters. Afterwards, we show how this bound can be improved for MRFs with particular structures such as bipartite graphs or grids. Our results provide interesting insight into the behavior of max-product. For example, we prove that max-product provides very good results (at least 90% of the optimal) on MRFs with large variable-disjoint cycles (MRFs in which all cycles are variable-disjoint, namely that they do not share any edge and in which each cycle contains at least 20 variables).

In this paper, we introduce a novel auction-based decision support system to help a firm readily assemble supply chains. At this aim, we tackle the problem of deciding whether to outsource some production processes or not-the so-called make-or-buy decision problem. The solution to the make-or-buy decision problem is an optimal supply chain whose operations are either performed in-house or outsourced. We propose to employ a novel extension of combinatorial reverse auctions, the so-called Multiunit Combinatorial Reverse Auction with Transformability Relationships Among Goods, which allows the following: 1) a buyer/auctioneer to express transformability relationships among goods (some goods can be transformed into others at some transformation cost) and 2) bidders to express their preferences over bundles of goods.

Vickrey-Clarke-Groves (VCG) mechanisms are often used to allocate tasks to selfish and rational agents. VCG mechanisms are incentive compatible, direct mechanisms that are efficient (i.e., maximise social utility) and individually rational (i.e., agents prefer to join rather than opt out). However, an important assumption of these mechanisms is that the agents will "always" successfully complete their allocated tasks. Clearly, this assumption is unrealistic in many real-world applications, where agents can, and often do, fail in their endeavours. Moreover, whether an agent is deemed to have failed may be perceived differently by different agents. Such subjective perceptions about an agent's probability of succeeding at a given task are often captured and reasoned about using the notion of "trust". Given this background, in this paper we investigate the design of novel mechanisms that take into account the trust between agents when allocating tasks. Specifically, we develop a new class of mechanisms, called "trust-based mechanisms", that can take into account multiple subjective measures of the probability of an agent succeeding at a given task and produce allocations that maximise social utility, whilst ensuring that no agent obtains a negative utility. We then show that such mechanisms pose a challenging new combinatorial optimisation problem (that is NP-complete), devise a novel representation for solving the problem, and develop an effective integer programming solution (that can solve instances with about 2x10^5 possible allocations in 40 seconds).

We propose a computational model that facilitates agents in a MAS to collaboratively evolve their norms to reach the best norm conventions. Our approach borrows from the social contagion phenomenon to exploit the notion of positive infection: agents with good behaviors become infectious to spread their norms in the agent society. By combining infection and innovation, our computational model helps a MAS establish better norm conventions even when a sub-optimal one has fully settled in the population.

Software agent marketplaces require the development of new architectures, which are capable of coping with unreliable computational and network infrastructures, limited trust among independently developed agents and the possibility of systemic failures.In analogy with human societies, agent marketplaces will benefit from the introduction of appropriate electronic exception handling institutions, whose role will be to help guarantee efficiency and fairness in the face of these challenges.This paper presents a research methodology for designing and evaluating such electronic institutions.It also describes how the methodology has been applied in order to design and evaluate an exception handling architecture for robust software agent marketplaces based on the contract net protocol.

We introduce an infrastructure for easing construction of agent-based systems. We argue that such infrastructure constitutes a convenient solution for releasing agent developers from cumbersome interaction issues inherent to any agent-based system, and therefore for helping them concentrate on the domain-dependent agents' logics issues. Our proposal relies upon two fundamental elements: conversation protocols, coordination patterns that impose a set of rules on communicative acts uttered by agents participating in a conversation (what can be said, to whom, and when), and interagents, autonomous software agents that mediate the interaction between each agent and the agent society wherein this is situated. Interagents employ conversation protocols for mediating conversations among agents. Thus management of conversation protocols is presented as raison d'être of interagents. We also introduce JIM, our java-based implementation of a general-purpose interagent. On one hand, we show how it handles conversation protocols in practice, and on the other hand, how it has been endowed with the capability of dealing with agent interaction at different levels by means of the SHIP protocol. Finally, we illustrate the use of interagents by explaining several roles that they play in Fishmarket, an agent-mediated electronic auction market. ©2000 John Wiley & Sons, Inc.