Skip to main content
main-content

Über dieses Buch

This book constitutes the revised post-conference proceedings of the 18th European Conference on Multi-Agent Systems, EUMAS 2021. The conference was held online in June, 2021. 16 full papers are presented in this volume, each of which carefully reviewed and selected from a total of 51 submissions. The papers report on both early and mature research and cover a wide range of topics in the field of multi-agent systems.

Inhaltsverzeichnis

Frontmatter

Ascending-Price Mechanism for General Multi-sided Markets

Abstract
We present an ascending-price mechanism for a multi-sided market with a variety of participants, such as manufacturers, logistics agents, insurance providers, and assemblers. Each deal in the market may consist of a combination of agents from separate categories, and different such combinations are simultaneously allowed. This flexibility lets multiple intersecting markets be resolved as a single global market. Our mechanism is obviously-truthful, strongly budget-balanced, individually rational, and attains almost the optimal gain-from-trade when the market is sufficiently large. We evaluate the performance of the suggested mechanism with experiments on real stock market data and synthetically produced data.
Dvir Gilor, Rica Gonen, Erel Segal-Halevi

Governing Black-Box Agents in Competitive Multi-Agent Systems

Abstract
Competitive Multi-Agent Systems (MAS) are inherently hard to control due to agent autonomy and strategic behavior, which is particularly problematic when there are system-level objectives to be achieved or specific environmental states to be avoided.
Existing solutions for this task mostly assume specific knowledge about agent preferences, utilities and strategies, neglecting the fact that actions are not always directly linked to genuine agent preferences, but can also reflect anticipated competitor behavior, be a concession to a superior adversary or simply be intended to mislead other agents. This assumption both reduces applicability to real-world systems and opens room for manipulation.
We therefore propose a new governance approach for competitive MAS which relies exclusively on publicly observable actions and transitions, and uses the acquired knowledge to purposefully restrict action spaces, thereby achieving the system’s objectives while preserving a high level of autonomy for the agents.
Michael Pernpeintner, Christian Bartelt, Heiner Stuckenschmidt

Path and Action Planning in Non-uniform Environments for Multi-agent Pickup and Delivery Tasks

Abstract
Although the multi-agent pickup and delivery (MAPD) problem, wherein multiple agents iteratively carry materials from some storage areas to the respective destinations without colliding, has received considerable attention, conventional MAPD algorithms use simplified, uniform models without considering constraints, by assuming specially designed environments. Thus, such conventional algorithms are not applicable to some realistic applications wherein agents have to move in a more complicated and restricted environment; for example, in a rescue or a construction site, their paths and orientations are strictly restricted owing to the path width, and the sizes of agents and materials they carry. Therefore, we first formulate an N-MAPD problem, which is an extension of the MAPD problem for a non-uniform environment. We then propose an N-MAPD algorithm, the path and action planning with orientation (PAPO), to effectively generate collision-free paths meeting the environmental constraints. The PAPO is an algorithm that considers not only the direction of movement but also the orientation of agents as well as the cost and timing of rotations in our N-MAPD formulation by considering the agent and material sizes, node sizes, and path widths. We experimentally evaluated the performance of the PAPO using our simulated environments and demonstrated that it could efficiently generate not optimal but acceptable paths for non-uniform environments.
Tomoki Yamauchi, Yuki Miyashita, Toshiharu Sugawara

Revealed Preference Argumentation and Applications in Consumer Behaviour Analyses

Abstract
Consumer preference studies in economics rest heavily on the behavioural interpretation of preference especially in the form of Revealed Preference Theory (RPT). Viewing purchasing decisions as a species of human reasoning, in this paper we are interested in generalising behaviourism to preference-based argumentation where existing frameworks are universally governed by the opposing mentalistic interpretation of preference. Concretely we re-construct and unify two main approaches to RPT then develop a so-called Revealed Preference Argumentation (RPA) framework which identifies preference as observed reasoning behaviour of an agent. We show that RPA subsumes RPT, by showing that key RPT-based consumer analyses can be translated to and solved as RPA computational tasks. It is argued that RPA may pave the way for future applications of argumentation to behavioural economics.
Nguyen Duy Hung, Van-Nam Huynh

Coordinating Multi-party Vehicle Routing with Location Congestion via Iterative Best Response

Abstract
This work is motivated by a real-world problem of coordinating B2B pickup-delivery operations to shopping malls involving multiple non-collaborative Logistics Service Providers (LSPs) in a congested city where space is scarce. This problem can be categorized as a Vehicle Routing Problem with Pickup and Delivery, Time Windows and Location Congestion with multiple LSPs (or ML-VRPLC in short), and we propose a scalable, decentralized, coordinated planning approach via iterative best response. We formulate the problem as a strategic game where each LSP is a self-interested agent but is willing to participate in a coordinated planning as long as there are sufficient incentives. Through an iterative best response procedure, agents adjust their schedules until no further improvement can be obtained to the resulting joint schedule. We seek to find the best joint schedule which maximizes the minimum gain achieved by any one LSP, as LSPs are interested in how much benefit they can gain rather than achieving a system optimality. We compare our approach to a centralized planning approach and our experiment results show that our approach is more scalable and is able to achieve on average 10% more gain within an operationally realistic time limit.
Waldy Joe, Hoong Chuin Lau

Explaining Ridesharing: Selection of Explanations for Increasing User Satisfaction

Abstract
Transportation services play a crucial part in the development of modern smart cities. In particular, on-demand ridesharing services, which group together passengers with similar itineraries, are already operating in several metropolitan areas. These services can be of significant social and environmental benefit, by reducing travel costs, road congestion and \(CO_2\) emissions.
Unfortunately, despite their advantages, not many people opt to use these ridesharing services. We believe that increasing the user satisfaction from the service will cause more people to utilize it, which, in turn, will improve the quality of the service, such as the waiting time, cost, travel time, and service availability. One possible way for increasing user satisfaction is by providing appropriate explanations comparing the alternative modes of transportation, such as a private taxi ride and public transportation. For example, a passenger may be more satisfied from a shared-ride if she is told that a private taxi ride would have cost her 50% more. Therefore, the problem is to develop an agent that provides explanations that will increase the user satisfaction.
We model our environment as a signaling game and show that a rational agent, which follows the perfect Bayesian equilibrium, must reveal all of the information regarding the possible alternatives to the passenger. In addition, we develop a machine learning based agent that, when given a shared-ride along with its possible alternatives, selects the explanations that are most likely to increase user satisfaction. Using feedback from humans we show that our machine learning based agent outperforms the rational agent and an agent that randomly chooses explanations, in terms of user satisfaction.
David Zar, Noam Hazon, Amos Azaria

Large-Scale, Dynamic and Distributed Coalition Formation with Spatial and Temporal Constraints

Abstract
The Coalition Formation with Spatial and Temporal constraints Problem (CFSTP) is a multi-agent task allocation problem in which few agents have to perform many tasks, each with its deadline and workload. To maximize the number of completed tasks, the agents need to cooperate by forming, disbanding and reforming coalitions. The original mathematical programming formulation of the CFSTP is difficult to implement, since it is lengthy and based on the problematic Big-M method. In this paper, we propose a compact and easy-to-implement formulation. Moreover, we design D-CTS, a distributed version of the state-of-the-art CFSTP algorithm. Using public London Fire Brigade records, we create a dataset with 347588 tasks and a test framework that simulates the mobilization of firefighters in dynamic environments. In problems with up to 150 agents and 3000 tasks, compared to DSA-SDP, a state-of-the-art distributed algorithm, D-CTS completes \(3.79\% \pm [42.22\%, 1.96\%]\) more tasks, and is one order of magnitude more efficient in terms of communication overhead and time complexity. D-CTS sets the first large-scale, dynamic and distributed CFSTP benchmark.
Luca Capezzuto, Danesh Tarapore, Sarvapali D. Ramchurn

Convention Emergence with Congested Resources

Abstract
Norms and conventions enable coordination in populations of agents by establishing patterns of behaviour, which can emerge as agents interact with their environment and each other. Previous research on norm emergence typically considers pairwise interactions, where agents’ rewards are endogenously determined. In many real-life domains, however, individuals do not interact with one other directly, but with their environment, and the resources associated with actions are often congested. Thus, agents’ rewards are exogenously determined as a function of others’ actions and the environment. In this paper, we propose a framework to represent this setting by: (i) introducing congested actions; and (ii) adding a central authority, that is able to manipulate agents’ rewards. Agents are heterogeneous in terms of their reward functions, and learn over time, enabling norms to emerge. We illustrate the framework using transport modality choice as a simple scenario, and investigate the effect of representative manipulations on the emergent norms.
Priel Levy, Nathan Griffiths

Aiming for Half Gets You to the Top: Winning PowerTAC 2020

Abstract
The PowerTAC competition provides a multi-agent simulation platform for electricity markets, in which intelligent agents acting as electricity brokers compete with each other aiming to maximize their profits. Typically, the gains of agents increase as the number of their customers rises, but in parallel, costs also increase as a result of higher transmission fees that need to be paid by the electricity broker. Thus, agents that aim to take over a disproportionately high share of the market, often end up with losses due to being obliged to pay huge transmission capacity fees. In this paper, we present a novel trading strategy that, based on this observation, aims to balance gains against costs; and was utilized by the champion of the PowerTAC-2020 tournament, TUC-TAC. The approach also incorporates a wholesale market strategy that employs Monte Carlo Tree Search to determine TUC-TAC’s best course of action when participating in the market’s double auctions. The strategy is improved by making effective use of a forecasting module that seeks to predict upcoming peaks in demand, since in such intervals incurred costs significantly increase. A post-tournament analysis is also included in this paper, to help draw important lessons regarding the strengths and weaknesses of the various strategies used in the PowerTAC-2020 competition.
Stavros Orfanoudakis, Stefanos Kontos, Charilaos Akasiadis, Georgios Chalkiadakis

Parameterized Analysis of Assignment Under Multiple Preferences

Abstract
The Assignment problem is a fundamental and well-studied problem in the intersection of Social Choice, Computational Economics and Discrete Allocation. In the Assignment problem, a group of agents expresses preferences over a set of items, and the task is to find a pareto optimal allocation of items to agents. We introduce a generalized version of this problem, where each agent is equipped with multiple incomplete preference lists: each list (called a layer) is a ranking of items in a possibly different way according to a different criterion. We introduce the concept of global optimality, which extends the notion of pareto optimality to the multi-layered setting, and we focus on the problem of deciding whether a globally optimal assignment exists. We study this problem from the perspective of Parameterized Complexity: we consider several natural parameters such as the number of layers, the number of agents, the number of items, and the maximum length of a preference list. We present a comprehensive picture of the parameterized complexity of the problem with respect to these parameters.
Barak Steindl, Meirav Zehavi

Solid Semantics for Abstract Argumentation Frameworks and the Preservation of Solid Semantic Properties

Abstract
In this paper, we propose solid admissibility that is a strengthened version of Dung’s admissibility to obtain the most acceptable set of arguments. Besides, other solid extensions based on solid admissibility are defined. Such extensions not only include all defenders of its elements but also exclude all arguments indirectly attacked and indirectly defended by some argument(s). Furthermore, we characterize solid extensions with propositional formulas. Using these formulas, we aggregate solid extensions by using approaches from judgment aggregation. Especially, although no quota rule preserves Dung’s admissibility for any argumentation framework, we show that there exist quota rules that preserve solid admissibility for any argumentation framework.
Xiaolong Liu, Weiwei Chen

Verification of Multi-layered Assignment Problems

Abstract
The class of assignment problems is a fundamental and well-studied class in the intersection of Social Choice, Computational Economics and Discrete Allocation. In a general assignment problem, a group of agents expresses preferences over a set of items, and the task is to allocate items to agents in an “optimal” way. A verification variant of this problem includes an allocation as part of the input, and the question becomes whether this allocation is “optimal”. In this paper, we generalize the verification variant to the setting where each agent is equipped with multiple incomplete preference lists: Each list (called a layer) is a ranking of items in a possibly different way according to a different criterion.
In particular, we introduce three multi-layer verification problems, each corresponds to an optimality notion that weakens the notion of global optimality (that is, pareto optimality in multiple layers) in a different way. Informally, the first notion requires that, for each group of agents whose size is exactly some input parameter k, the agents in the group will not be able to trade their assigned items among themselves and benefit in at least \(\alpha \) layers; the second notion is similar, but it concerns all groups of size at most k rather than exactly k; the third notion strengthens these notions by requiring that groups of k agents will not be part of possibly larger groups that benefit in at least \(\alpha \) layers. We study the three problems from the perspective of parameterized complexity under several natural parameterizations such as the number of layers, the number of agents, the number of items, the number of allocated items, the maximum length of a preference list, and more. We present an almost comprehensive picture of the parameterized complexity of the problems with respect to these parameters.
Barak Steindl, Meirav Zehavi

Logic and Model Checking by Imprecise Probabilistic Interpreted Systems

Abstract
Stochastic multi-agent systems raise the necessity to extend probabilistic model checking to the epistemic domain. Results in this direction have been achieved by epistemic extensions of Probabilistic Computation Tree Logic and related Probabilistic Interpreted Systems. The latter, however, suffer of an important limitation: they require the probabilities governing the system’s behaviour to be fully specified. A promising way to overcome this limitation is represented by imprecise probabilities. In this paper we introduce imprecise probabilistic interpreted systems and present a related logical language and model-checking procedures based on recent advances in the study of imprecise Markov processes.
Alberto Termine, Alessandro Antonucci, Giuseppe Primiero, Alessandro Facchini

On the Complexity of Predicting Election Outcomes and Estimating Their Robustness

Abstract
When dealing with election data it is reasonable to assume that the votes are incomplete or noisy. The reasons are manifold and range from cost-intensive elicitation to manipulation. We study the problems of evaluating elections with incomplete data and determining the robustness of elections with noisy data from a computational point of view. To capture a wide variety of motivations, we consider three different models for the distribution of preferences: the uniform distribution over the completions of incomplete preferences inspired by the possible winner problem, the dispersion around complete preferences, also called Mallows noise model, and a model in which the distribution over the votes of each voter is explicitly given. We consider both approval vector preferences and linear order preferences and show that the complexity of the problems can vary greatly depending on the voting rule, the distribution model, and the parameterization. We investigate the problems both in terms of counting complexity as well as decision complexity and discuss the effects of the winner model and tie-breaking on the results.
Dorothea Baumeister, Tobias Hogrebe

Point Based Solution Method for Communicative IPOMDPs

Abstract
Communicative interactive POMDPs (CIPOMDPs) provide a principled framework for optimal interaction and communication in multi-agent settings by endowing agents with nested models (theories of mind) of others and with the ability to communicate with them. In CIPOMDPs, agents use Bayes update to process their observations and messages without the usual assumption of cooperative discourse. We propose a variant of the point-based value iteration method, called IPBVI-Comm, to compute the approximate optimal policy of a CIPOMDP agent. We then use the IPBVI-Comm to study the optimal communicative behavior of agents in cooperative and competitive scenarios. Unsurprisingly, it is optimal for agents to attempt to mislead if their preferences are not aligned. But it turns out the higher depth of reasoning allows an agent to detect insincere communication and to guard against it. Specifically, in some scenarios, the agent is able to distinguish a truthful friend from a deceptive foe based on the message received.
Sarit Adhikari, Piotr Gmytrasiewicz

A Decentralized Token-Based Negotiation Approach for Multi-Agent Path Finding

Abstract
This paper introduces a negotiation approach to solve the Multi-Agent Path Finding problem. The approach aims to achieve a good trade-off between the privacy of the agents and the effectiveness of solutions. Accordingly, a token-based bilateral negotiation protocol and a compatible negotiation strategy are presented. The proposed approach is evaluated in a variety of scenarios by comparing it with state-of-the-art centralized approaches such as Conflict Based Search and its variant. The experimental results showed that the proposed approach can find conflict-free path solutions with a higher success rate, especially when the search space is large and high-density compared to centralized approaches while the gap between path cost differences is reasonably low. The proposed approach enables agents to have their autonomy; thus, it is convenient for MAPF problems involving self-interested agents.
Cihan Eran, M. Onur Keskin, Furkan Cantürk, Reyhan Aydoğan

Backmatter

Weitere Informationen

Premium Partner