Novel autonomous search and rescue systems, although powerful, still require a human decision-maker involvement. In this project, we focus on the human aspect of one such novel autonomous SAR system. Relying on the knowledge gained in a field study, as well as through the literature, we introduced several extensions to the system that allowed us to achieve a more user-centered interface. In the evaluation session with a rescue service specialist, we received positive feedback and defined potential directions for future work.

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. 

Optimal simultaneous coalition structure generation and assignment is computationally hard. The state-of-the-art can only compute solutions to problems with severely limited input sizes, and no effective approximation algorithms that are guaranteed to yield high-quality solutions are expected to exist. Real-world optimization problems, however, are often characterized by large-scale inputs and the need for generating feasible solutions of high quality in limited time. In light of this, and to make it possible to generate better feasible solutions for difficult large-scale problems efficiently, we present and benchmark several different anytime algorithms that use general-purpose heuristics and Monte Carlo techniques to guide search. We evaluate our methods using synthetic problem sets of varying distribution and complexity. Our results show that the presented algorithms are superior to previous methods at quickly generating near-optimal solutions for small-scale problems, and greatly superior for efficiently finding high-quality solutions for large-scale problems. For example, for problems with a thousand agents and values generated with a uniform distribution, our best approach generates solutions 99.5% of the expected optimal within seconds. For these problems, the state-of-the-art solvers fail to find any feasible solutions at all.

An important research problem in artificial intelligence is how to organize multiple agents, and coordinate them, so that they can work together to solve problems. Coordinating agents in a multi-agent system can significantly affect the systems performance-the agents can, in many instances, be organized so that they can solve tasks more efficiently, and consequently benefit collectively and individually. Central to this endeavor is coalition formation-the process by which heterogeneous agents organize and form disjoint groups (coalitions). Coalition formation often involves finding a coalition structure (an exhaustive set of disjoint coalitions) that maximizes the systems potential performance (e.g., social welfare) through coalition structure generation. However, coalition structure generation typically has no notion of goals. In cooperative settings, where coordination of multiple coalitions is important, this may generate suboptimal teams for achieving and accomplishing the tasks and goals at hand. With this in mind, we consider simultaneously generating coalitions of agents and assigning the coalitions to independent alternatives (e.g., tasks/goals), and present an anytime algorithm for the simultaneous coalition structure generation and assignment problem. This combinatorial optimization problem hasmany real-world applications, including forming goal-oriented teams. To evaluate the presented algorithms performance, we present five methods for synthetic problem set generation, and benchmark the algorithm against the industry-grade solver CPLEXusing randomized data sets of varying distribution and complexity. To test its anytime-performance, we compare the quality of its interim solutions against those generated by a greedy algorithm and pure random search. Finally, we also apply the algorithm to solve the problem of assigning agents to regions in a major commercial strategy game, and show that it can be used in game-playing to coordinate smaller sets of agents in real-time.

A fundamental problem in artificial intelligence is how to organize and coordinate agents to improve their performance and skills. In this paper, we consider simultaneously generating coalitions of agents and assigning the coalitions to independent tasks, and present an anytime algorithm for the simultaneous coalition structure generation and assignment problem. This optimization problem has many real-world applications, including forming goal-oriented teams of agents. To evaluate the algorithm’s performance, we extend established methods for synthetic problem set generation, and benchmark the algorithm against CPLEX using randomized data sets of varying distribution and complexity. We also apply the algorithm to solve the problem of assigning agents to regions in a major commercial strategy game, and show that the algorithm can be utilized in game-playing to coordinate smaller sets of agents in real-time.

We present, analyze and benchmark two algorithms for simultaneous coalition structure generation and assignment: one based entirely on dynamic programming, and one anytime hybrid approach that uses branch-and-bound together with dynamic programming. To evaluate the algorithms’ performance, we benchmark them against both CPLEX (an industry-grade solver) and the state-of-the-art using difficult randomized data sets of varying distribution and complexity. Our results show that our hybrid algorithm greatly outperforms CPLEX, pure dynamic programming and the current state-of-the-art in all of our benchmarks. For example, when solving one of the most difficult problem sets, our hybrid approach finds optimum in roughly 0.1% of the time that the current best method needs, and it generates 98% efficient interim solutions in milliseconds in all of our anytime benchmarks; a considerable improvement over what previous methods can achieve.

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 presents preliminary work on using deep neural networksto guide general-purpose heuristic algorithms for performing utilitarian combinatorial assignment. In more detail, we use deep learning in an attempt to produce heuristics that can be used together with e.g., search algorithms to generatefeasible solutions of higher quality more quickly. Our results indicate that ourapproach could be a promising future method for constructing such heuristics.