The computing industry is currently facing a major architectural shift. Extra computing power is not coming anymore from higher processor frequencies, but from a growing number of computing cores and processors. For AI, and constraint solving in particular, this raises the question of how to scale current solving techniques to massively parallel architectures. While prior work focusses mostly on small scale parallel constraint solving, we conduct the first study on scalability of constraint solving on 100 processors and beyond in this paper. We propose techniques that are simple to apply and show empirically that they scale surprisingly well. These techniques establish a performance baseline for parallel constraint solving technologies against which more sophisticated parallel algorithms need to  compete  in the future.

We study under what conditions bound consistency (BC) and arc consistency  (AC),  two forms of propagation used in constraint solvers, are equivalent to each other. We show that they prune exactly the same values when the propagated constraint is connected row convex / closed under median and its complement is row convex. This  characterization is exact for binary constraints. Since row convexity depends on the order of the values in the domains, we give polynomial algorithms for computing orders under which BC and AC are equivalent, if any.

We show that some common and important global constraints like ALLDIFFERENT and GCC can be decomposed into simple arithmetic constraints on which we achieve bound or range consistency, and in some cases even greater pruning. These decompositions can be easily added to new solvers. They also provide other constraints with access to the state of the propagator by sharing variables. Such sharing can be used to improve propagation between constraints. We report experiments with our decomposition in a pseudo-Boolean solver.

We show that tools from circuit complexity can be used to study decompositions of global constraints. In particular, we study decompositions of global constraints into conjunctive normal form with the property that unit propagation on the decomposition enforces the same level of consistency as a specialized propagation algorithm. We prove that a constraint propagator has a a polynomial size decomposition if and only if it can be computed by a polynomial size monotone Boolean circuit. Lower bounds on the size of monotone Boolean circuits thus translate to lower bounds on the size of decompositions of global constraints. For instance, we prove that there is no polynomial sized decomposition of the domain consistency propagator for the alldiff constraint.

It is useful to impose organizational structure over multiagent coalitions.  Hierarchies, for instance, allow for compartmentalization of tasks: if organized correctly, tasks in disjoint subtrees of the hierarchy may be performed in parallel.  Given a notion of the way in which a group of agents need to interact, the Dynamic Distributed Multiagent Hierarchy Generation (DynDisMHG) problem is to determine the best hierarchy that might expedite the process of coordination. This paper introduces a distributed algorithm, called Mobed, for both constructing and maintaining organizational agent hierarchies, enabling exploitation of parallelism in distributed problem solving.  The algorithm is proved correct and it is shown that individual additions of agents to the hierarchy will run in an amortized linear number of rounds.  The hierarchies resulting after perturbations to the agent coalition have constant-bounded edit distance, making Mobed very well suited to highly dynamic problems.

Experiments show that these approaches achieve high effectiveness Negotiation scenarios involving nonlinear utility (measured as high optimality rates and low failure rates functions are specially challenging, because traditional for the negotiations) in the evaluation scenario they describe negotiation mechanisms cannot be applied. (Section 2). However, as we will show empirically in Section Even mechanisms designed and proven useful for 5.2, these approaches perform worse as the circumstances of nonlinear utility spaces may fail if the utility space the scenario turn harder (that is, when the utility functions is highly nonlinear. For example, although both are highly nonlinear, like in B2B interactions or distributed contract sampling and constraint sampling have automated control systems). Under these circumstances, the been successfully used in auction based negotiations failure rate increases drastically, raising the need for an alternative with constraint-based utility spaces, they tend approach.

Voting theory can provide useful insights for multiagent preference aggregation. However, the standard setting assumes voters with preferences that are total orders, as well as a ballot language that coincides with the preference language. In typical AI scenarios, these assumptions do not hold: certain alternatives may be incomparable for some agents, and others may have their preferences encoded in a format that is different from how the preference aggregation mechanism wants them. We study the consequences of dropping these assumptions. In particular, we investigate the consequences for the important notion of strategy-proofness. While strategy-proofness cannot be guaranteed in the classical setting, we are able to show that there are situations in our more general framework where this is possible. We also consider computational aspects of the problem.

We introduce planning games, a study of interactions of self-motivated agents in automated planning settings. Planning games extend STRIPS-like models of single-agent planning to systems of multiple self-interested agents, providing a rich class of structured games that capture subtle forms of local interactions. We consider two basic models of planning games and adapt game-theoretic solution concepts to these models.  In both models, agents may need to cooperate in order to achieve their goals, but are assumed to do so only in order to increase their net benefit. For each model we study the computational problem of finding a stable solution and provide efficient algorithms for systems exhibiting acyclic interaction structure.

While there are several languages for representing combinatorial preferences over sets of alternatives, none of these are well-suited to the representation of ordinal preferences over sets of goods (which are typically required to be monotonic). We propose such a language, taking inspiration from previous work on graphical languages for preference representation, specifically CP-nets, and introduce conditional importance networks (CI-nets).  A CI-net includes statements of the form "if I have a set A of goods, and I do not have any of the goods from some other set B, then I prefer the set of goods C over the set of goods D." We investigate expressivity and complexity issues for CI-nets. Then we show that CI-nets are well-suited to the description of fair division problems.

We study constraint satisfaction problems on the so-called planted random ensemble. We show that for a certain class of problems, e.g. We study the structural phase transitions, and the easy/hard/easy pattern in the average computational complexity. We also discuss the finite temperature phase diagram, finding a close connection with the liquid/glass/solid phenomenology. Constraint satisfaction problems (CSPs) stand at the root of the theory of computational complexity [1] and arise in computer science, physics, engineering and many other fields of science.