In their groundbreaking paper, Bartholdi, Tovey and Trick [1989] argued that many well-known voting rules, such as Plurality, Borda, Copeland and Maximin are easy to manipulate. An important assumption made in that paper is that the manipulator’s goal is to ensure that his preferred candidate is among the candidates with the maximum score, or, equivalently, that ties are broken in favor of the manipulator’s preferred candidate. In this paper, we examine the role of this assumption in the easiness results of [Bartholdi et al., 1989]. We observe that the algorithm presented in [Bartholdi et al., 1989] extends to all rules that break ties according to a fixed ordering over the candidates. We then show that all scoring rules are easy to manipulate if the winner is selected from all tied candidates uniformly at random. This result extends to Maximin under an additional assumption on the manipulator’s utility function that is inspired by the original model of [Bartholdi et al., 1989]. In contrast, we show that manipulation becomes hard when arbitrary polynomial-time tie-breaking rules are allowed, both for the rules considered in [Bartholdi et al., 1989], and for a large class of scoring rules.

Semi-supervised learning algorithms commonly incorporate the available background knowledge such that an expression of the derived model's quality is improved. Depending on the specific context quality can take several forms and can be related to the generalization performance or to a simple clustering coherence measure. Recently, a novel perspective of semi-supervised learning has been put forward, that associates semi-supervised clustering with the efficiency of spectral methods. More precisely, it has been demonstrated that the appropriate use of partial supervision can bias the data Laplacian matrix such that the necessary eigenvector computations are provably accelerated. This result allows data mining practitioners to use background knowledge not only for improving the quality of clustering results, but also for accelerating the required computations. In this paper we initially provide a high level overview of the relevant efficiency maximizing semi-supervised methods such that their theoretical intuitions are comprehensively outlined. Consecutively, we demonstrate how these methods can be extended to handle multiple clusters and also discuss possible issues that may arise in the continuous semi-supervised solution. Finally, we illustrate the proposed extensions empirically in the context of text clustering.

The personalization aspect of recommender systems makes them well suited to applications in The goal of rating-based recommender systems is electronic commerce and entertainment, while the fact that to make personalized predictions and recommendations they do not rely on text-based descriptions of items makes for individual users by leveraging the preferences them well suited to content like movies and music. of a community of users with respect to a In this paper, we focus on a key problem in rating-based collection of items like songs or movies. Recommender collaborative filtering: the possibility of a basic incompatibility systems are often based on intricate statistical between the properties of recommender system data sets models that are estimated from data sets containing and the assumptions required for valid estimation and evaluation a very high proportion of missing ratings. of statistical models in the presence of missing data. This work describes evidence of a basic incompatibility We describe properties of recommender system data sets and between the properties of recommender relate them to the statistical theory of model estimation in system data sets and the assumptions required for the presence of nonrandom missing data. We describe an valid estimation and evaluation of statistical models extended modelling framework and a modified set of evaluation in the presence of missing data. We discuss the protocols for dealing with nonrandom missing data.

Case-based problem-solving systems reason by retrieving relevant prior cases and adapting their solutions to fit new circumstances. The ability of case-based reasoning (CBR) to reason from ungeneralized episodes can benefit knowledge acquisition, but acquiring the needed case adaptation knowledge has proven challenging. This paper presents a method for alleviating this problem with just-in-time gathering of case adaptation knowledge, based on introspective reasoning and mining of Web knowledge sources. The approach combines knowledge planning with introspective reasoning to guide recovery from case adaptation failures and reinforcement learning to guide selection of knowledge sources. The failure recovery and knowledge source selection methods have been tested in three highly different domains with encouraging results. The paper closes with a discussion of limitations and future steps.

In some domains, the most appropriate matchings may not strictly preserve ancestry. For instance, while reparenting Tree-matching problems arise in many computational even a single node in a phylogenetic tree of bacteria would domains. The literature provides several destroy its validity, the ancestry relationships in the Document methods for creating correspondences between labeled Object Model tree of a Web page are much less prescriptive: trees; however, by definition, tree-matching moving a search bar from header to footer results in a algorithms rigidly preserve ancestry. That is, once different--but largely equivalent--page. This pattern follows two nodes have been placed in correspondence, for many other tree structures encountered in design and data their descendants must be matched as well. We introduce management, in which hierarchy plays an important--but not flexible tree matching, which relaxes this definitive--role [Chawathe and Garcia-Molina, 1997].

The Semantic Web aims to offer an interoperable environment that will allow users to safely delegate complex actions to intelligent agents. Much work has been done for agents' interoperability; especially in the areas of ontology-based metadata and rule-based reasoning. Nevertheless, the SW proof layer has been neglected so far, although it is vital for agents and humans to understand how a result came about, in order to increase the trust in the interchanged information. This paper focuses on the implementation of third party SW reasoning and proofing services wrapped as agents in a multi-agent framework. This way, agents can exchange and justify their arguments without the need to conform to a common rule paradigm. Via external reasoning and proofing services, the receiving agent can grasp the semantics of the received rule set and check the validity of the inferred results.

The use of ontologies for accessing data is one of the most exciting new applications of description logic in databases and other information systems. A realistic way of realising sufficiently scalable ontology- based data access in practice is by reduction to querying relational databases. In this paper, we describe the ‘combined approach,’ which incorporates the information given by the ontology into the data and employs query rewriting to eliminate spurious answers. We illustrate this approach for ontologies given in the DL-Lite family of description logics and briefly discuss the results obtained for the EL family.

Many complex robot motor skills can be represented using elementary movements, and there exist efficient techniques for learning parametrized motor plans using demonstrations and self-improvement. However with current techniques, in many cases, the robot currently needs to learn a new elementary movement even if a parametrized motor plan exists that covers a related situation. A method is needed that modulates the elementary movement through the meta-parameters of its representation. In this paper, we describe how to learn such mappings from circumstances to meta-parameters using reinforcement learning. In particular we use a kernelized version of the reward-weighted regression. We show two robot applications of the presented setup in robotic domains; the generalization of throwing movements in darts, and of hitting movements in table tennis. We demonstrate that both tasks can be learned successfully using simulated and real robots.

Recommender systems are becoming tools of choice to select the online information relevant to a given user. Collaborative filtering is the most popular approach to building recommender systems and has been successfully employed in many applications. With the advent of online social networks, the social network based approach to recommendation has emerged. This approach assumes a social network among users and makes recommendations for a user based on the ratings of the users who have direct or indirect social relations with the given user. As one of their major benefits, social network based approaches have been shown to reduce the problems with cold start users. In this paper, we explore a model-based approach for recommendation in social networks, employing matrix factorization techniques. Advancing previous work, we incorporate the mechanism of trust propagation into the model in a principled way. Trust propagation has been shown to be a crucial phenomenon in the social sciences, in social network analysis and in trust-based recommendation. We have conducted experiments on two real life data sets. Our experiments demonstrate that modeling trust propagation leads to a substantial increase in recommendation accuracy, in particular for cold start users.

A plan with rich control structures like branches and loops can usually serve as a general solution that solves multiple planning instances in a domain. However, the correctness of such generalized plans is non-trivial to define and verify, especially when it comes to whether or not a plan works for all of the infinitely many instances of the problem. In this paper, we give a precise definition of a generalized plan representation called an FSA plan, with its semantics defined in the situation calculus. Based on this, we identify a class of infinite planning problems, which we call one-dimensional (1d), and prove a correctness result that 1d problems can be verified by finite means. We show that this theoretical result leads to an algorithm that does this verification practically, and a planner based on this verification algorithm efficiently generates provably correct plans for 1d problems.