We examine the complexity of constraint satisfaction problems that consist of a set of AllDiff constraints. Such CSPs naturally model a wide range of real-world and combinatorial problems, like scheduling, frequency allocations and graph coloring problems. As this problem is known to be NP-complete, we investigate under which further assumptions it becomes tractable. We observe that a crucial property seems to be the convexity of the variable domains and constraints. Our main contribution is an extensive study of the complexity of Multiple AllDiff CSPs for a set of natural parameters, like maximum domain size and maximum size of the constraint scopes. We show that, depending on the parameter, convexity can make the problem tractable while it is provably intractable in general.

Such problems are that each relation R can be defined by a Boolean combination frequently intractable, but there are several important of equations over the signature,, andc, which are set CSPs that are known to be polynomial-time function symbols for intersection, union, and complementation, tractable. We introduce a large class of set CSPs respectively. Details of the formal definition and many that can be solved in quadratic time. Our class, examples of set constraint languages can be found in Section which we call EI, contains all previously known 3. The choice of N is just for notational convenience; tractable set CSPs, but also some new ones that as we will see, we could have selected any infinite set for are of crucial importance for example in description our purposes. In the following, a set constraint satisfaction logics. The class of EI set constraints has an problem (set CSP) is a problem of the form CSP(Γ) for a elegant universal-algebraic characterization, which set constraint language Γ. It has been shown by Marriott and we use to show that every set constraint language Odersky [Marriott and Odersky, 1996] that all set CSPs are that properly contains all EI set constraints already contained in NP; they also showed that the largest set constraint has a finite sublanguage with an NPhard constraint language, which consists of all relations that can be satisfaction problem.

We develop a novel circuit-level stochastic local search (SLS) method D-CRSat for Boolean satisfiability by integrating a structure-based heuristic into the recent CRSat algorithm. D-CRSat significantly improves on CRSat on real-world application benchmarks on which other current CNF and circuit-level SLS methods tend to perform weakly. We also give an intricate proof of probabilistically approximate completeness for D-CRSat, highlighting key features of the method.

The Partner Units Problem is a specific type of configuration problem with important applications in the area of surveillance and security. In this work we show that a special case of the problem, that is of great interest to our partners in industry, can directly be tackled via a structural problem decompostion method. Combining these theoretical insights with general purpose AI techniques such as constraint satisfaction and SAT solving proves to be particularly effective in practice.

This paper examines an extended double auction model where market clearing is restricted by temporal constraints. It is found that the allocation problem in this model can be effectively transformed into a weighted bipartite matching in graph theory. By using the augmentation technique, we propose a Vickrey-Clarke-Groves (VCG) mechanism in this model and demonstrate the advantages of the payment compared with the classical VCG payment (the Clarke pivot payment). We also show that the algorithms for both allocation and payment calculation run in polynomial time. It is expected that the method and results provided in this paper can be applied to the design and analysis of dynamic double auctions and futures markets.

In multi-issue automated negotiation against unknown opponents, a key part of effective negotiation is the choice of concession strategy. In this paper, we develop a principled concession strategy, based on Gaussian processes predicting the opponent's future behaviour. We then use this to set the agent's concession rate dynamically during a single negotiation session. We analyse the performance of our strategy and show that it outperforms the state-of-the-art negotiating agents from the 2010 Automated Negotiating Agents Competition, in both a tournament setting and in self-play, across a variety of negotiation domains.

Note that this extra to make decisions about which plans are used to information is included as a preference rather than a goal, achieve their goals. Usually the choice of which as it is acceptable to satisfy the goal without satisfying the plan to use to achieve a particular goal is left up preference. For example, if the user prefers to fly on Dodgy to the system to determine. In this paper we show Airlines, but no such flights are available, then specifying this how preferences, which can be set by the user of the as a preference means that the user can still have a holiday; system, can be incorporated into the BDI execution specifying this as a goal would mean that the user refuses to process and used to guide the choices made.

We present the notion of Social Instruments as mechanisms that facilitate the emergence of conventions from repeated interactions between members of a society. Specifically, we focus on two social instruments: rewiring and observation. Our main goal is to provide agents with tools that allow them to leverage their social network of interactions when effectively addressing coordination and learning problems, paying special attention to dissolving meta-stable subconventions. Initial experiments throw some light on how Self-Reinforcing Substructures (SRS) in the network prevent full convergence, resulting in reduced convergence rates. The use of an effective composed social instrument (observation + rewiring) allow agents to eliminate the subconventions that otherwise remained meta-stable.

In this paper we conceptualize abstract argumentation in terms of successful and unsuccessful attacks, such that arguments are accepted when there are no successful attacks on them. We characterize the relation between attack semantics and Dung's approach, and we define an SCC recursive algorithm for attack semantics using attack labelings.

Typical solutions for agents assessing trust relies on the circulation of information on the individual level, i.e. reputational images, subjective experi- ences, statistical analysis, etc. This work presents an alternative approach, inspired to the cognitive heuristics enabling humans to reason at a categorial level. The approach is envisaged as a crucial ability for agents in order to: (1) estimate trustworthiness of unknown trustees based on an ascribed mem- bership to categories; (2) learn a series of emer- gent relations between trustees observable proper- ties and their effective abilities to fulfill tasks in sit- uated conditions. On such a basis, categorization is provided to recognize signs (Manifesta) through which hidden capabilities (Kripta) can be inferred. Learning is provided to refine reasoning attitudes needed to ascribe tasks to categories. A series of ar- chitectures combining categorization abilities, indi- vidual experiences and context awareness are eval- uated and compared in simulated experiments.