Generalized arc consistency (GAC) is one of the most fundamental properties for reducing the search space when solving constraint satisfaction problems (CSPs). Consistencies stronger than GAC have also been shown useful, but the challenge is to develop efficient and simple filtering algorithms. Several CSP transformations are proposed recently so that the GAC algorithms can be applied on the transformedCSP to enforce stronger consistencies. Among them, the factor encoding (FE) is shown to be promising with respect to recent higher-order consistency algorithms. Nonetheless, one potential drawback of the FE is the fact that it enlarges the table relations as it increases constraint arity. We propose a variation of the FE that aims at reducing redundant columns in the constraints of the FE while still preserving full pairwise consistency. Experiments show that the new approach is competitive over a variety of random and structured benchmarks.

We study equilibrium dynamics in candidacy games, in which candidates may strategically decide to enter the election or withdraw their candidacy, following their own preferences over possible outcomes. Focusing on games under Plurality, we extend the standard model to allow for situations where voters may refuse to return their votes to those candidates who had previously left the election, should they decide to run again. We show that if at the time when a candidate withdraws his candidacy, with some positive probability each voter takes this candidate out of his future consideration, the process converges with probability 1. This is in sharp contrast with the original model where the very existence of a Nash equilibrium is not guaranteed. We then consider the two extreme cases of this setting, where voters may block a withdrawn candidate with probabilities 0 or 1. In these scenarios, we study the complexity of reaching equilibria from a given initial point, converging to an equilibrium with a predermined winner or to an equilibrium with a given set of running candidates. Except for one easy case, we show that these problems are NP-complete, even when the initial point is fixed to a natural---truthful---state where all potential candidates stand for election.

We present a method to calculate cost-optimal policies for co-safe linear temporal logic task specifications over a Markov decision process model of a stochastic system. Our key contribution is to address scenarios in which the task may not be achievable with probability one. We formalise a task progression metric and, using multi-objective probabilistic model checking, generate policies that are formally guaranteed to, in decreasing order of priority: maximise the probability of finishing the task; maximise progress towards completion, if this is not possible; and minimise the expected time or cost required. We illustrate and evaluate our approach in a robot task planning scenario, where the task is to visit a set of rooms that may be inaccessible during execution.

Hedonic games provide a natural model of coalition formation among self-interested agents. The associated problem of finding stable outcomes in such games has been extensively studied. In this paper, we identify simple conditions on expressivity of hedonic games that are sufficient for the problem of checking whether a given game admits a stable outcome to be computationally hard. Somewhat surprisingly, these conditions are very mild and intuitive. Our results apply to a wide range of stability concepts (core stability, individual stability, Nash stability, etc.) and to many known formalisms for hedonic games (additively separable games, games with W-preferences, fractional hedonic games, etc.), and unify and extend known results for these formalisms. They also have broader applicability: for several classes of hedonic games whose computational complexity has not been explored in prior work, we show that our framework immediately implies a number of hardness results for them.

We study truthful mechanisms in the context of cake cutting when agents not only value their own pieces of cake but also care for the pieces assigned to other agents. In particular, agents derive benefits or costs from the pieces of cake assigned to other agents. This phenomenon is often referred to as positive or negative externalities. We propose and study the following model: given an allocation, externalities of agents are modeled as percentages of the reported values that other agents have for their pieces. We show that even in this restricted class of externalities, under some natural assumptions, no truthful cake cutting mechanisms exist when externalities are either positive or negative. However, when the percentages agents get from each other are small, we show that there exists a truthful cake cutting mechanism with other desired properties.

In Massively Open Online Courses (MOOCs) TA resources are limited; most MOOCs use peer assessments to grade assignments. Students have to divide up their time between working on their own homework and grading others. If there is no risk of being caught and penalized, students have no reason to spend any time grading others Course staff want to incentivize students to balance their time between course work and peer grading. They may do so by auditing students, ensuring that they perform grading correctly. One would not want students to invest too much time on peer grading, as this would result in poor course performance. We present the first model of strategic auditing in peer grading, modeling the student's choice of effort in response to a grader's audit levels as a Stackelberg game with multiple followers. We demonstrate that computing the equilibrium for this game is computationally hard. We then provide a PTAS in order to compute an approximate solution to the problem of allocating audit levels. However, we show that this allocation does not necessarily maximize social welfare; in fact, there exist settings where course auditor utility is arbitrarily far from optimal under an approximately optimal allocation. To circumvent this issue, we present a natural condition that guarantees that approximately optimal TA allocations guarantee approximately optimal welfare for the course auditors.

Plan recognition, the problem of inferring the goals or plans of an observed agent, is a key element of situation awareness in human-machine and machine-machine interactions for many applications. Some plan recognition algorithms require knowledge about the potential behaviours of the observed agent in the form of a plan library, together with a decision model about how the observed agent uses the plan library to make decisions. It is however difficult to elicit and specify the decision model a priori . In this paper, we present a recursive neural network model that learns such a decision model automatically. We discuss promising experimental results of the approach with comparisons to selected state-of-the-art plan recognition algorithms on three benchmark domains.

Many robotic tasks require solutions that maximize multiple performance objectives. For example, in path-planning, these objectives often include finding short paths that avoid risk and maximize the information obtained by the robot. Although there exist many algorithms for multiobjective optimization, few of these algorithms apply directly to robotic path-planning and fewer still are capable of finding the set of Pareto optimal solutions. We present the MORRF*(Multi-Objective Rapidly exploring Random Forest*) algorithm, which blends concepts from two different types of algorithms from the literature: Optimal rapidly exploring random tree (RRT*) for efficient path finding and a decomposition-based approach to multi-objective optimization. The random forest uses two types of tree structures: a set of reference trees and a set of subproblem trees. We present a theoretical analysis that demonstrates that the algorithm asymptotically produces the set of Pareto optimal solutions, and use simulations to demonstrate the effectiveness and efficiency of MORRF* in approximating the Pareto set.

Compositionality is a fundamental notion in computation whereby complex abstractions can be constructed from simpler ones, but this property has so far escaped the paradigm of end-user programming from examples or natural language. Existing approaches restrict end users to only give holistic end-to-end specifications, which limits the expressivity and scalability of these approaches to relatively simple programs in very restricted domains. In this paper we propose a new approach to end-user program synthesis in which input can be given in a compositional manner through a combination of natural language and examples. We present a domain-agnostic program synthesis algorithm and demonstrate its application to an expressive string manipulation language. We evaluate on a range of complex examples from help forums that are beyond the scope of previous systems.

Hierarchical Task Network (HTN) planning with Task Insertion (TIHTN planning) is a formalism that hybridizes classical planning with HTN planning by allowing the insertion of operators from outside the method hierarchy. This additional capability has some practical benefits, such as allowing more flexibility for design choices of HTN models: the task hierarchy may be specified only partially, since "missing required tasks" may be inserted during planning rather than prior planning by means of the (predefined) HTN methods. While task insertion in a hierarchical planning setting has already been applied in practice, its theoretical properties have not been studied in detail, yet — only EXPSPACE membership is known so far. We lower that bound proving NEXPTIME-completeness and further prove tight complexity bounds along two axes: whether variables are allowed in method and action schemas, and whether methods must be totally ordered. We also introduce a new planning technique called acyclic progression, which we use to define provably efficient TIHTN planning algorithms.