Demange (2012) generalized the classical single-crossing property to the intermediate property on median graphs and proved that the representative voter theorem still holds for this more general framework. We complement her result with proving that the linear orders of any profile which is intermediate on a median graph  form a Condorcet domain. We prove that for any median graph there exists a profile that is intermediate with respect to that graph and that one may need at least as many alternatives as vertices to construct such a profile.  We provide a polynomial-time algorithm to recognize whether or not a given profile is intermediate with respect to some median graph. Finally, we show that finding winners for the Chamberlin-Courant rule is polynomial-time solvable  for profiles that are single-crossing on a tree.

Fundamental to reasoning about actions and beliefs is the projection problem: to decide what is believed after a sequence of actions is performed. Progression is one widely applied technique to solve this problem. In this paper we propose a novel framework for computing progression in the epistemic situation calculus. In particular, we model an agent's preferential belief structure using conditional statements and provide a technique for updating these conditional statements as actions are performed and sensing information is received. Moreover, we show, by using the concepts of natural revision and only-believing, that the progression of a conditional knowledge base can be represented by only-believing the revised set of conditional statements. These results lay the foundations for feasible belief progression due to the unique-model property of only-believing.

The Atari 2600 games supported in the Arcade Learning Environment [Bellemare et al., 2013] all feature a known initial (RAM) state and actions that have deterministic effects. Classical planners, however, cannot be used off-the-shelf as there is no compact PDDL-model of the games, and action effects and goals are not known a priori. Indeed, there are no explicit goals, and the planner must select actions on line while interacting with a simulator that returns successor states and rewards. None of this precludes the use of blind lookahead algorithms for action selection like breadth-first search or Dijkstra’s yet such methods are not effective over large state spaces. We thus turn to a different class of planning methods introduced recently that have been shown to be effective for solving large planning problems but which do not require prior knowledge of state transitions, costs (rewards) or goals. The empirical results over 54 Atari games show that the simplest such algorithm performs at the level of UCT, the state-of-the-art planning method in this domain, and suggest the potential of width-based methods for planning with simulators when factored, compact action models are not available.

An author’s profile on Google Scholar consists of indexed articles and associated data, such as the number of citations and the H-index. The author is allowed to merge articles, which may affect the H-index. We analyze the parameterized complexity of maximizing the H-index using article merges. Herein, to model realistic manipulation scenarios, we define a compatability graph whose edges correspond to plausible merges. Moreover, we consider multiple possible measures for computing the citation count of a merged article. For the measure used by Google Scholar, we give an algorithm that maximizes the H-index in linear time if the compatibility graph has constant-size connected components. In contrast, if we allow to merge arbitrary articles, then already increasing the H-index by one is NP-hard. Experiments on Google Scholar profiles of AI researchers show that the H-index can be manipulated substantially only by merging articles with highly dissimilar titles, which would be easy to discover.

General Game Playing aims to create AI systems that can understand the rules of new games and learn to play them effectively without human intervention. The recent proposal for general game-playing robots extends this to AI systems that play games in the real world. Execution monitoring becomes a necessity when moving from a virtual to a physical environment, because in reality actions may not be executed properly and (human) opponents may make illegal game moves. We develop a formal framework for execution monitoring by which an action theory that provides an axiomatic description of a game is automatically embedded in a meta-game for a robotic player — called the arbiter — whose role is to monitor and correct failed actions. This allows for the seamless encoding of recovery behaviours within a meta-game, enabling a robot to recover from these unexpected events.

Tour recommendation and itinerary planning are challenging tasks for tourists, due to their need to select Points of Interest (POI) to visit in unfamiliar cities, and to select POIs that align with their interest preferences and trip constraints. We propose an algorithm called PersTour for recommending personalized tours using POI popularity and user interest preferences, which are automatically derived from real-life travel sequences based on geo-tagged photos. Our tour recommendation problem is modelled using a formulation of the Orienteering problem, and considers user trip constraints such as time limits and the need to start and end at specific POIs. In our work, we also reflect levels of user interest based on visit durations, and demonstrate how POI visit duration can be personalized using this time-based user interest. Using a Flickr dataset of four cities, our experiments show the effectiveness of PersTour against various baselines, in terms of tour popularity, interest, recall, precision and F1-score. In particular, our results show the merits of using time-based user interest and personalized POI visit durations, compared to the current practice of using frequency-based user interest and average visit durations.

The probabilistic serial (PS) rule is a prominent randomized rule for assigning indivisible goods to agents. Although it is well known for its good fairness and welfare properties, it is not strategyproof. In view of this, we address several fundamental questions regarding equilibria under PS. Firstly, we show that Nash deviations under the PS rule can cycle. Despite the possibilities of cycles, we prove that a pure Nash equilibrium is guaranteed to exist under the PS rule. We then show that verifying whether a given profile is a pure Nash equilibrium is coNP-complete, and computing a pure Nash equilibrium is NP-hard. For two agents, we present a linear-time algorithm to compute a pure Nash equilibrium which yields the same assignment as the truthful profile. Finally, we conduct experiments to evaluate the quality of the equilibria that exist under the PS rule, finding that the vast majority of pure Nash equilibria yield social welfare that is at least that of the truthful profile.

List of committee members on the program committees of the IJCAI 2015 conference.

We consider the computational complexity of computing welfare maximizing partitions for fractional hedonic games — a natural class of coalition formation games that can be succinctly represented by a graph. For such games, welfare maximizing partitions constitute desirable ways to cluster the vertices of the graph. We present both intractability results and approximation algorithms for computing welfare maximizing partitions.

When a belief state is represented as a probability function P, the resulting belief state of the contraction of a sentence (belief) from the original belief state P can be given by the probabilistic version of the Harper Identity. Specifically, the result of contracting P by a sentence h is taken to be the mixture of two states: the original state P, and the resultant state P* ~h of revising P by the negation of h. What proportion of P and P* ~h should be used in this mixture remains an open issue and is largely ignored in literature. In this paper, we first classify different belief states by their stability, and then exploit the quantitative nature of probabilities and combine it with the basic ideas of argumentation theory to determine  the mixture proportions. We, therefore, propose a novel approach to probabilistic belief contraction using argumentation.