Recent work in portfolios of problem solvers has shown their ability to outperform single-algorithm approaches in some tasks (e.g. SAT or Automated Planning). However, not much work has been devoted to a better understanding of the relationship between the order of the component solvers and the performance of the resulting portfolio over time. We propose to sort the component solvers in a sequential portfolio, such that the resulting ordered portfolio maximizes the probability of providing the largest performance at any point in time. We empirically show that our greedy approach efficiently obtains near-optimal performance over time. Also, it generalizes much better than an optimal approach which has been observed to suffer from overfitting.

The intractability in cooperative, decentralized control models is mainly due to prohibitive memory requirements in both optimal policies and value functions. The complexity analysis has emerged as the standard method to estimating the memory needed for solving a given computational problem, but complexity results may be somewhat limited. This paper introduces a general methodology — structural analysis — for the design of optimality-preserving concise policies and value functions, which will eventually lead to the development of efficient theory and algorithms. For the first time, we show that memory requirements for policies and value functions may be asymmetric, resulting in cooperative, decentralized control models with exponential reductions in memory requirements.

The number of multi-robot systems deployed in field applications has risen dramatically over the years. Nevertheless, supervising and operating multiple robots at once is a difficult task for a single operator to execute. In this paper we propose a novel approach for utilizing advising automated agents when assisting an operator to better manage a team of multiple robots in complex environments. We introduce the Myopic Advice Optimization (MYAO) Problem and exemplify its implementation using an agent for the Search And Rescue (SAR) task. Our intelligent advising agent was evaluated through extensive field trials, with 44 non-expert human operators and 10 low-cost mobile robots, in simulation and physical deployment, and showed a significant improvement in both team performance and the operator’s satisfaction.

A major challenge in Content-Based Image Retrieval (CBIR) is to bridge the semantic gap between low-level image contents and high-level semantic concepts. Although researchers have investigated a variety of retrieval techniques using different types of features and distance functions, no single best retrieval solution can fully tackle this challenge. In a real-world CBIR task, it is often highly desired to combine multiple types of different feature representations and diverse distance measures in order to close the semantic gap. In this paper, we investigate a new framework of learning to rank for CBIR, which aims to seek the optimal combination of different retrieval schemes by learning from large-scale training data in CBIR. We first formulate the problem formally as a learning to rank task, which can be solved in general by applying the existing batch learning to rank algorithms from text information retrieval (IR). To further address the scalability towards large-scale online CBIR applications, we present a family of online learning to rank algorithms, which are significantly more efficient and scalable than classical batch algorithms for large-scale online CBIR. Finally, we conduct an extensive set of experiments, in which encouraging results show that our technique is effective, scalable and promising for large-scale CBIR.

Cepheus is the first computer program to essentially solve a game of imperfect information that is played competitively by humans. The game it plays is heads-up limit Texas hold'em poker, a game with over 10^14 information sets, and a challenge problem for artificial intelligence for over 10 years. Cepheus was trained using a new variant of Counterfactual Regret Minimization (CFR), called CFR+, using 4800 CPUs running for 68 days. In this paper we describe in detail the engineering details required to make this computation a reality. We also prove the theoretical soundness of CFR+ and its component algorithm, regret-matching+. We further give a hint towards understanding the success of CFR+ by proving a tracking regret bound for this new regret matching algorithm. We present results showing the role of the algorithmic components and the engineering choices to the success of CFR+.

Distributed constraint optimization (DCOP) is an important framework for coordinated multiagent decision making. We address a practically useful variant of DCOP, called resource-constrained DCOP (RC-DCOP), which takes into account agents' consumption of shared limited resources. We present a promising new class of algorithm for RC-DCOPs by translating the underlying coordination problem to probabilistic inference. Using inference techniques such as expectation-maximization and convex optimization machinery, we develop a novel convergent message-passing algorithm for RC-DCOPs. Experiments on standard benchmarks show that our approach provides better quality than previous best DCOP algorithms and has much lower failure rate. Comparisons against an efficient centralized solver show that our approach provides near-optimal solutions, and is significantly faster on larger instances.

We study resource allocation in a model due to Brams and King [2005] and further developed by Baumeister et al. [2014]. Resource allocation deals with the distribution of resources to agents. We assume resources to be indivisible, nonshareable, and of single-unit type. Agents have ordinal preferences over single resources. Using scoring vectors, every ordinal preference induces a utility function. These utility functions are used in conjunction with utilitarian social welfare to assess the quality of allocations of resources to agents. Then allocation correspondences determine the optimal allocations that maximize utilitarian social welfare. Since agents may have an incentive to misreport their true preferences, the question of strategy-proofness is important to resource allocation. We assume that a manipulator has a strictly monotonic and strictly separable linear order on the power set of the resources. We use extension principles (from social choice theory, such as the Kelly and the Gärdenfors extension) for preferences to study manipulation of allocation correspondences. We characterize strategy-proofness of the utilitarian allocation correspondence: It is Gärdenfors/Kelly-strategy-proof if and only if the number of different values in the scoring vector is at most two or the number of occurrences of the greatest value in the scoring vector is larger than half the number of goods.

Allocation games are coalitional games defined in the literature as a way to analyze fair division problems of indivisible goods. The prototypical solution concepts for them are the Shapley value and the Banzhaf value. Unfortunately, their computation is intractable, formally #P-hard. Motivated by this bad news, structural requirements are investigated which can be used to identify islands of tractability. The main result is that, over the class of allocation games, the Shapley value and the Banzhaf value can be computed in polynomial time when interactions among agents can be formalized as graphs of bounded treewidth. This is shown by means of technical tools that are of interest in their own and that can be used for analyzing different kinds of coalitional games. Tractability is also shown for games where each good can be assigned to at most two agents, independently of their interactions.

Standard results on and algorithms for repeated games assume that defections are instantly observable. In reality, it may take some time for the knowledge that a defection has occurred to propagate through the social network. How does this affect the structure of equilibria and algorithms for computing them? In this paper, we consider games with cooperation and defection. We prove that there exists a unique maximal set of forever-cooperating agents in equilibrium and give an efficient algorithm for computing it. We then evaluate this algorithm on random graphs and find experimentally that there appears to be a phase transition between cooperation everywhere and defection everywhere, based on the value of cooperation and the discount factor. Finally, we provide a condition for when the equilibrium found is credible, in the sense that agents are in fact motivated to punish deviating agents. We find that this condition always holds in our experiments, provided the graphs are sufficiently large.

We introduce one-way games, a framework motivated by applications in large-scale power restoration, humanitarian logistics, and integrated supply-chains. The distinguishable feature of the games is that the payoff of some player is determined only by her own strategy and does not depend on actions taken by other players. We show that the equilibrium outcome in one-way games without payments and the social cost of any ex-post efficient mechanism, can be far from the optimum. We also show that it is impossible to design a Bayes-Nash incentive-compatible mechanism for one-way games that is budget-balanced, individually rational, and efficient. Finally, we propose a privacy-preserving mechanism that is incentive-compatible and budget-balanced, satisfies ex-post individual rationality conditions, and produces an outcome which is more efficient than the equilibrium without payments.