One of the challenges of multiagent decision making is that the behavior needed to maximize utility can depend on what other agents choose to do: sometimes there is no "right" answer in the absence of knowledge of how opponents will act. The Nash equilibrium is a sensible choice of behavior because it represents a mutual best response. But, even when there is a unique equilibrium, other players are under no obligation to take part in it. This observation has been forcefully illustrated in the behavioral economics community where repeated experiments have shown individuals playing Nash equilibria and performing badly as a result. In this paper, we show how to apply a tool from behavioral economics called the Cognitive Hierarchy (CH) to the design of agents in general sum games. We attack the recently introduced ``Lemonade Game'' and show how the results of an open competition are well explained by CH. We believe this game, and perhaps many other similar games, boils down to predicting how deeply other agents in the game will be reasoning. An agent that does not reason enough risks being exploited by its opponents, while an agent that reasons too much may not be able to interact productively with its opponents. We demonstrate these ideas by presenting empirical results using agents from the competition and idealizations arising from a CH analysis.

In this paper we apply a Monte-Carlo Tree Search implementation that is boosted with domain knowledge to the game of poker. More specifically, we integrate an opponent model in the Monte-Carlo Tree Search algorithm to produce a strong poker playing program. Opponent models allow the search algorithm to focus on relevant parts of the game-tree. We use an opponent modelling approach that starts from a (learned) prior, i.e., general expectations about opponent behavior, and then learns a relational regression tree-function that adapts these priors to specific opponents. Our modelling approach can generate detailed game features or relations on-the-fly. Additionally, using a prior we can already make reasonable predictions even when limited experience is available for a particular player. We show that Monte-Carlo Tree Search with integrated opponent models performs well against state-of-the-art poker programs.

Distributed Partially Observable Markov Decision Processes (DEC-POMDPs) are a popular planning framework for multiagent teamwork to compute (near-)optimal plans. However, these methods assume a complete and correct world model, which is often violated in real-world domains. We provide a new algorithm for DEC-POMDPs that is more robust to model uncertainty, with a focus on domains with sparse agent interactions. Our STC algorithm relies on the following key ideas: (1) reduce planning-time computation by shifting some of the burden to execution-time reasoning, (2) exploit sparse interactions between agents, and (3) maintain an approximate model of agents’ beliefs. We empirically show that STC is often substantially faster to existing DEC-POMDP methods without sacrificing reward performance.

We study several classes of interactive assistants from the points of view of decision theory and computational complexity. We first introduce a special class of POMDPs called hidden-goal MDPs (HGMDPs), which formalize the problem of interactively assisting an agent whose goal is hidden and whose actions are observable. In spite of its restricted nature, we show that optimal action selection in finite horizon HGMDPs is PSPACE-complete even in domains with deterministic dynamics. We then introduce a more restricted model called helper action MDPs (HAMDPs), where the assistant’s action is accepted by the agent when it is helpful, and can be easily ignored by the agent otherwise. We show classes of HAMDPs that are complete for PSPACE and NP along with a polynomial time class. Furthermore, we show that for general HAMDPs a simple myopic policy achieves a regret, compared to an omniscient assistant, that is bounded by the entropy of the initial goal distribution. A variation of this policy is also shown to achieve worst-case regret that is logarithmic in the number of goals for any goal distribution.

This paper examines the problem of finding articles in Wikipedia to match noun synsets in WordNet. The motivation is that these articles enrich the synsets with much more information than is already present in WordNet. Two methods are used. The first is title matching, following redirects and disambiguation links. The second is information retrieval over the set of articles. The methods are evaluated over a random sample set of 200 noun synsets which were manually annotated. With 10 candidate articles retrieved for each noun synset, the methods achieve recall of 93%. The manually annotated data set and the automatically generated candidate article sets are available online for research purposes.

We have been exploring the use of Web-derived knowledge bases through the development of Wikitology — a hybrid knowledge base of structured and unstructured information extracted from Wikipedia augmented by RDF data from DBpedia and other Linked Open Data resources. In this paper, we describe approaches that aid in enriching Wikipedia and thus the resources that derive from Wikipedia such as the Wikitology knowledge base, DBpedia, Freebase and Powerset.

Present-day programs are brittle as computers are notoriously lacking in common sense. While significant progress has been made in building large common sense knowledge bases, they are intrinsically incomplete and inconsistent. This paper presents a novel approach to bridging the gaps between multiple knowledge bases, making it possible to answer queries based on knowledge collected from multiple sources without a common ontology. New assertions are found by computing graph similarity with principle component analysis to draw analogies across multiple knowledge bases. Experiments are designed to find new assertions for a Chinese commonsense knowledge base using the OMCS ConceptNet and similarly for WordNet. The assertions are voted by online users to verify that 75.77% / 77.59% for Chinese ConceptNet / WordNet respectively are good, despite the low overlap in coverage among the knowledge bases.

Increasingly, we need to computationally understand real-time streams of information in places such as news feeds, speech streams, and social networks. We present Streaming AnalogySpace, an efficient technique that discovers correlations in and makes predictions about sparse natural-language data that arrives in a real-time stream. AnalogySpace is a noise-resistant PCA-based inference technique designed for use with collaboratively collected common sense knowledge and semantic networks. Streaming AnalogySpace advances this work by computing it incrementally using CCIPCA, and keeping a dense cache of recently-used features to efficiently represent a sparse and open domain. We show that Streaming AnalogySpace converges to the results of standard AnalogySpace, and verify this by evaluating its accuracy empirically on common-sense predictions against standard AnalogySpace.

It has generally been assumed that the knowledge employed by an AI reasoning system needs to be in an unambiguous, formally interpretable form. From that perspective, general knowledge expressed in ordinary language (e.g., “dogs bark”) is unacceptably ambiguous and incomplete. However, we can achieve at least a partial transformation of such knowledge into formal, generically quantified sentences by taking account of properties of words and phrases such as the aspectual category, tense, Levin class, and presuppositions of verbs, or the classification of predicates (adjectival, nominal, verbal) as applicable to objects or kinds of objects.

Until recently, the AI and in particular the NLP community GA, immediately preceding the Twenty-Fourth AAAI Conference have relied on resources built manually by experts in on Artificial Intelligence -- AAAI 2010. It is a successor specific areas (in particular linguists, philosophers, cognitive to the workshops organized at AAAI 2008 entitled linguists). User contributed knowledge has opened up "Wikipedia and Artificial Intelligence: An Evolving Synergy" a new perspective, in that it captures the kind of knowledge (WikiAI 08) and at IJCAI 2009 entitled "User Contributed and organization that arises naturally out of the consensus Knowledge and Artificial Intelligence: An Evolving of the masses, and as such represents better our collective Synergy" (WikiAI 09). The outcome is a multifaceted and extremely This volume contains papers accepted for presentation at rich source of information, revealed through embedded annotations the workshop. We issued calls for regular papers, short latebreaking and structural information.