This book constitutes the refereed proceedings of the 23rd International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2020, held in Nagoya, Japan, in November 2020. The 19 full papers presented and 13 short papers were carefully reviewed and selected from 50 submissions. Due to COVID-19, the conference was held online. The conference covers a wide range of ranging from foundations of agent theory and engineering aspects of agent systems, to emerging interdisciplinary areas of agent-based research.

Allocating resources, goods, agents (e.g., humans), expertise, production, and assets is one of the most influential and enduring cornerstone challenges at the intersection of artificial intelligence, operations research, politics, and economics. At its core—as highlighted by a number of seminal works [181, 164, 125, 32, 128, 159, 109, 209, 129, 131]—is a timeless question: How can we best allocate indivisible entities—such as objects, items, commodities, jobs, or personnel—so that the outcome is as valuable as possible, be it in terms of expected utility, fairness, or overall societal welfare? This thesis confronts this inquiry from multiple algorithmic viewpoints, focusing on the value-maximizing combinatorial assignment problem: the optimization challenge of partitioning a set of indivisibles among alternatives to maximize a given notion of value. To exemplify, consider a scenario where an international aid organization is responsible for distributing medical resources, such as ventilators and vaccines, and allocating medical personnel, including doctors and nurses, to hospitals during a global health crisis. These resources and personnel—inherently indivisible and non-fragmentable—necessitate an allocation process designed to optimize utility and fairness. Rather than using manual interventions and ad-hoc methods, which often lack precision and scalability, a rigorously developed and demonstrably performant approach can often be more desirable. With this type of challenge in mind, our thesis begins through the lens of computational complexity theory, commencing with an initial insight: In general, under prevailing complexity-theoretic assumptions (P ≠ NP), it is impossible to develop an efficient method guaranteeing a value-maximizing allocation that is better than “arbitrarily bad”, even under severely constraining limitations and simplifications. This inapproximability result not only underscores the problem’s complexity but also sets the stage for our ensuing work, wherein we develop novel algorithms and concise representations for utilitarian, egalitarian, and Nash welfare maximization problems, aimed at maximizing average, equitable, and balanced utility, respectively. For example, we introduce the synergy hypergraph—a hypergraph-based characterization of utilitarian combinatorial assignment—which allows us to prove several new state-of-the-art complexity results to help us better understand how hard the problem is. We then provide efficient approximation algorithms and (non-trivial) exponential-time algorithms for many hard cases. In addition, we explore complexity bounds for generalizations with interdependent effects between allocations, known as externalities in economics. Natural applications in team formation, resource allocation, and combinatorial auctions are also discussed; and a novel “bootstrapped” dynamic-programming method is introduced. We then transition from theory to practice as we shift our focus to the utilitarian variant of the problem—an incarnation of the problem particularly applicable to many real-world scenarios. For this variation, we achieve substantial empirical algorithmic improvements over existing methods, including industry-grade solvers. This work culminates in the development of a new hybrid algorithm that combines dynamic programming with branch-and-bound techniques that is demonstrably faster than all competing methods in finding both optimal and near-optimal allocations across a wide range of experiments. For example, it solves one of our most challenging problem sets in just 0.25% of the time required by the previous best methods, representing an improvement of approximately 2.6 orders of magnitude in processing speed. Additionally, we successfully integrate and commercialize our algorithm into Europa Universalis IV—one of the world’s most popular strategy games, with a player base exceeding millions. In this dynamic and challenging setting, our algorithm efficiently manages complex strategic agent interactions, highlighting its potential to improve computational efficiency and decision-making in real-time, multi-agent scenarios. This also represents one of the first instances where a combinatorial assignment algorithm has been applied in a commercial context. We then introduce and evaluate several highly efficient heuristic algorithms. These algorithms—while lacking provable quality guarantees—employ general-purpose heuristic and random-sampling techniques to significantly outperform existing methods in both speed and quality in large-input scenarios. For instance, in one of our most challenging problem sets, involving a thousand indivisibles, our best algorithm generates outcomes that are 99.5% of the expected optimal in just seconds. This performance is particularly noteworthy when compared to state-of-the-art industry-grade solvers, which struggle to produce any outcomes under similar conditions. Further advancing our work, we employ novel machine learning techniques to generate new heuristics that outperform the best hand-crafted ones. This approach not only showcases the potential of machine learning in combinatorial optimization but also sets a new standard for combinatorial assignment heuristics to be used in real-world scenarios demanding rapid, high-quality decisions, such as in logistics, real-time tactics, and finance. In summary, this thesis bridges many gaps between the theoretical and practical aspects of combinatorial assignment problems such as those found in coalition formation, combinatorial auctions, welfare-maximizing resource allocation, and assignment problems. It deepens the understanding of the computational complexities involved and provides effective and improved solutions for longstanding real-world challenges across various sectors—providing new algorithms applicable in fields ranging from artificial intelligence to logistics, finance, and digital entertainment, while simultaneously paving the way for future work in computational problem-solving and optimization.

Human-centric AI aims at designing and developing systems that operate along with humans in a cognitively-compatible and synergetic way. Such systems are required to exhibit human-like cognitive abilities and intelligence, either at the general level of the human population or at some specialized level of expertise in a specific field. In either case, human-centric AI systems exist as (expert) companions or peers of their human users that would operate alongside them to support and enhance their capabilities.

Due to numerous biomedical information sensing devices, such as Computed Tomography (CT), Magnetic Resonance (MR) Imaging, Ultrasound, Single Photon Emission Computed Tomography (SPECT), and Positron Emission Tomography (PET), to Magnetic Particle Imaging, EE/MEG, Optical Microscopy and Tomography, Photoacoustic Tomography, Electron Tomography, and Atomic Force Microscopy, etc. a large amount of biomedical information was gathered these years. However, identifying how to develop new advanced imaging methods and computational models for efficient data processing, analysis and modelling from the collected data is important for clinical applications and to understand the underlying biological processes. Deep learning approaches have been rapidly developed in recent years, both in terms of methodologies and practical applications. Deep learning techniques provide computational models of multiple processing layers to learn and represent data with multiple levels of abstraction. Deep Learning allows to implicitly capture intricate structures of large-scale data and ideally suited to some of the hardware architectures that are currently available.

This paper focuses on the high-level specification and generation of 3D models for operational environments using the idea of active queries as a basis for specifying and generating multi-agent plans for acquiring such models. Assuming an underlying multi-agent system, an operator can specify a request for a particular type of model from a specific region by specifying an active query. This declarative query is then interpreted and executed by collecting already existing data/information in agent systems or, in the active case, by automatically generating high-level mission plans for agents to retrieve and generate parts of the model that do not already exist. The purpose of an active query is to hide the complexity of multi-agent mission plan generation, data transformations, and distributed collection of data/information in underlying multi-agent systems. A description of an active query system, its integration with an existing multi-agent system and validation of the active query system in field robotics experimentation using Unmanned Aerial Vehicles and simulations are provided.