We show that without using any domain knowledge, we can predict the final performance of a team of voting agents, at any step towards solving a complex problem.

The vision of populating the world with autonomous systems that reduce human labor and improve safety is gradually becoming a reality. Autonomous systems have changed the way space exploration is conducted and are beginning to transform everyday life with a range of household products. In many areas, however, there are considerable barriers to the deployment of fully autonomous systems. We refer to systems that require some degree of human intervention in order to complete a task as semi-autonomous systems. We examine the broad rationale for semi-autonomy and define basic properties of such systems. Accounting for the human in the loop presents a considerable challenge for current planning techniques. We examine various design choices in the development of semi-autonomous systems and their implications on planning and execution. Finally, we discuss fruitful research directions for advancing the science of semi-autonomy.

Living organisms adapt to challenges through evolution. This has proven to be a key difficulty in developing therapies, since the organisms evolve resistance.I propose the wild idea of steering evolution strategically — using computational game theory for (typically incomplete-information) multistage games and opponent exploitation techniques. A sequential contingency plan for steering evolution is constructed computationally for the setting at hand. In the biological context, the opponent (e.g., a disease) has a systematic handicap because it evolves myopically. This can be exploited by computing trapping strategies that cause the opponent to evolve into states where it can be handled effectively. Potential application classes include therapeutics at the population, individual, and molecular levels (drug design), as well as cell repurposing and synthetic biology.

Sequential decision problems that involve multiple objectives are prevalent. Consider for example a driver of a semi-autonomous car who may want to optimize competing objectives such as travel time and the effort associated with manual driving. We introduce a rich model called Lexicographic MDP (LMDP) and a corresponding planning algorithm called LVI that generalize previous work by allowing for conditional lexicographic preferences with slack. We analyze the convergence characteristics of LVI and establish its game theoretic properties. The performance of LVI in practice is tested within a realistic benchmark problem in the domain of semi-autonomous driving. Finally, we demonstrate how GPU-based optimization can improve the scalability of LVI and other value iteration algorithms for MDPs.

Team formation is a core problem in AI. Remarkably, little prior work has addressed the problem of mechanism design for team formation, accounting for the need to elicit agents' preferences over potential teammates. Coalition formation in the related hedonic games has received much attention, but only from the perspective of coalition stability, with little emphasis on the mechanism design objectives of true preference elicitation, social welfare, and equity. We present the first formal mechanism design framework for team formation, building on recent combinatorial matching market design literature. We exhibit four mechanisms for this problem, two novel, two simple extensions of known mechanisms from other domains. Two of these (one new, one known) have desirable theoretical properties. However, we use extensive experiments to show our second novel mechanism, despite having no theoretical guarantees, empirically achieves good incentive compatibility, welfare, and fairness.

In cooperative game theory, it is typically assumed that the value of each coalition is known. We depart from this, assuming that v(S) is only a noisy estimate of the true value V (S), which is not yet known. In this context, we investigate which solution concepts maximize the probability of ex-post stability (after the true values are revealed). We show how various conditions on the noise characterize the least core and the nucleolus as optimal. Modifying some aspects of these conditions to (arguably) make them more realistic, we obtain characterizations of new solution concepts as being optimal, including the partial nucleolus, the multiplicative least core, and the multiplicative nucleolus.

We study strong equilibria in symmetric capacitated cost-sharing games. In these games, a graph with designated source s and sink t is given, and each edge is associated with some cost. Each agent chooses strategically an s-t path, knowing that the cost of each edge is shared equally between all agents using it. Two variants of cost-sharing games have been previously studied: (i) games where coalitions can form, and (ii) games where edges are associated with capacities; both variants are inspired by real-life scenarios. In this work we combine these variants and analyze strong equilibria (profiles where no coalition can deviate) in capacitated games. This combination gives rise to new phenomena that do not occur in the previous variants. Our contribution is two-fold. First, we provide a topological characterization of networks that always admit a strong equilibrium. Second, we establish tight bounds on the efficiency loss that may be incurred due to strategic behavior, as quantified by the strong price of anarchy (and stability) measures. Interestingly, our results are qualitatively different than those obtained in the analysis of each variant alone, and the combination of coalitions and capacities entails the introduction of more refined topology classes than previously studied.

We examine the quality of social choice mechanisms using a utilitarian view, in which all of the agents have costs for each of the possible alternatives. While these underlying costs determine what the optimal alternative is, they may be unknown to the social choice mechanism; instead the mechanism must decide on a good alternative based only on the ordinal preferences of the agents which are induced by the underlying costs. Due to its limited information, such a social choice mechanism cannot simply select the alternative that minimizes the total social cost (or minimizes some other objective function). Thus, we seek to bound the distortion: the worst-case ratio between the social cost of the alternative selected and the optimal alternative. Distortion measures how good a mechanism is at approximating the alternative with minimum social cost, while using only ordinal preference information. The underlying costs can be arbitrary, implicit, and unknown; our only assumption is that the agent costs form a metric space, which is a natural assumption in many settings. We quantify the distortion of many well-known social choice mechanisms. We show that for both total social cost and median agent cost, many positional scoring rules have large distortion, while on the other hand Copeland and similar mechanisms perform optimally or near-optimally, always obtaining a distortion of at most 5. We also give lower bounds on the distortion that could be obtained by any deterministic social choice mechanism, and extend our results on median agent cost to more general objective functions.

We consider the Social Ridesharing (SR) problem, where a set of commuters, connected through a social network, arrange one-time rides at short notice. In particular, we focus on the associated optimisation problem of forming cars to minimise the travel cost of the overall system modelling such problem as a graph constrained coalition formation (GCCF) problem, where the set of feasible coalitions is restricted by a graph (i.e., the social network). Moreover, we significantly extend the state of the art algorithm for GCCF, i.e., the CFSS algorithm, to solve our GCCF model of the SR problem. Our empirical evaluation uses a real dataset for both spatial (GeoLife) and social data (Twitter), to validate the applicability of our approach in a realistic application scenario. Empirical results show that our approach computes optimal solutions for systems of medium scale (up to 100 agents) providing significant cost reductions (up to -36.22%). Moreover, we can provide approximate solutions for very large systems (i.e., up to 2000 agents) and good quality guarantees (i.e., with an approximation ratio of 1.41 in the worst case) within minutes (i.e., 100 seconds).

Electric vehicles will play a crucial role in balancing the future electrical grid, which is complicated by many intermittent renewable energy sources. We developed an algorithm that determines for a fleet of electric vehicles, which EV at what price and location to commit to the operating reserve market to either absorb excess capacity or provide electricity during shortages (vehicle-2-grid). The algorithm takes the value of immobility into account by using carsharing fees as a reference point. A virtual power plant autonomously replaces cars that are committed to the operating reserves and are then rented out, with other idle cars to pool the risks of uncertainty. We validate our model with data from a free float carsharing fleet of 500 electric vehicles. An analysis of expected future developments (2015, 2018, and 2022) in operating reserve demand and battery costs yields that the gross profits for a carsharing operator increase between 7-12% with a negligible decrease in car availability (<0.01%).