The worst-case complexity of general decentralized POMDPs, which are equivalent to partially observable stochastic games (POSGs) is very high, both for the cooperative and competitive cases. Some reductions in complexity have been achieved by exploiting independence relations in some models. We show that these results are somewhat limited: when these independence assumptions are relaxed in very small ways, complexity returns to that of the general case.

In this paper, we describe our autonomous bidding agent, RoxyBot, who emerged victorious in the travel division of the 2006 Trading Agent Competition in a photo finish. At a high level, the design of many successful trading agents can be summarized as follows: (i) price prediction: build a model of market prices; and (ii) optimization: solve for an approximately optimal set of bids, given this model. To predict, RoxyBot builds a stochastic model of market prices by simulating simultaneous ascending auctions. To optimize, RoxyBot relies on the sample average approximation method, a stochastic optimization technique.

In the naming game, individuals or agents exchange pairwise local information in order to communicate about objects in their common environment. The goal of the game is to reach a consensus about naming these objects. Originally used to investigate language formation and self-organizing vocabularies, we extend the classical naming game with a globally shared memory accessible by all agents. This shared memory can be interpreted as an external source of knowledge like a book or an Internet site. The extended naming game models an environment similar to one that can be found in the context of social bookmarking and collaborative tagging sites where users tag sites using appropriate labels, but also mimics an important aspect in the field of human-based image labeling. Although the extended naming game is non-deterministic in its word selection, we show that consensus towards a common vocabulary is reached. More importantly, we show the qualitative and quantitative influence of the external source of information, i.e. the shared memory, on the consensus dynamics between the agents.

Given a set of known numbers, there are many measures of the degree of inhomogeneity within the set such as the standard deviation, the relative mean difference, and the Gini coefficient. This paper discusses conceptual issues (such as qualitative versus quantitative diversity, and the group as a population versus as a sample), desired properties (such as symmetry and invariance properties), and technical considerations (such as working with differences versus deviations, or absolute versus squared values) in choosing an index suitable for describing the degree of inhomogeneity or diversity in a group of people or computer agents. In particular, it is argued that the relative mean difference and the Gini coefficient are not well-suited as indexes of cultural diversity. This paper then addresses two apparently neglected inverse problems: Given a pre-specified degree of inhomogeneity, what set of unknown numbers has the desired degree of inhomogeneity? And, in particular, what set has the maximal possible degree of inhomogeneity? The solution requires that the set of permissible numbers be bounded with minimum and maximum values. A key benefit of such inverse procedures is that agent-based groups with pre-selected degrees of cultural diversity can be formed to test hypotheses using the full range of possible diversities and thereby avoid statistical problems due to restriction of range effects.

We construct a computer model that allows us to simulate the effect of counterinsurgency operations on a population of agents. We build a society of agents who are interconnected in an established social network. Each agent in this network engages in political discourse with other agents over the legitimacy of the existing government. Agents may decide to support an insurgency, join an insurgency, side with the existing government, or remain neutral over which group to support. Using this model we explore the relative importance of social network structure, influence effectiveness, and combat operation effectiveness in minimizing insurgent strength.

We provide an algorithm to compute near-optimal strategies for the Cultaptation social learning game. We show that the strategies produced by our algorithm are near-optimal, both in their expected utility and their expected reproductive success. We show how our algorithm can be used to provide insight into evolutionary conditions under which learning is best done by copying others, versus the conditions under which learning is best done by trial-and-error.

The development of tools to provide insight into the behavioral response of a civilian population will greatly benefit the modeling and simulation community and have potential applications across multiple user communities in the U.S. Department of Defense. We present an overview of a modular agent-based modeling framework, grounded in the human behavioral and social theory, which is intended to represent a populations’ stance on issues as a function of their changing beliefs, values and interests. We utilize and integrate theories of narrative identity [1] and planned behavior [2] with macrosociological theories of heterogeneity and influence [3][4] to model civilian behavior in a conflict ecosystem. Communication between agents takes place across a social network developed using real data about the population under consideration, and essential services are implemented as objects within the model allowing for experimentation with different courses of action for development of civil service capacity. We describe the theoretical underpinnings of the model, the current state of implementation, potential use cases, and the path forward for future work.

This paper presents an agent based framework for modeling of the formation and dynamics of pirate networks. The framework consists of (1) development of network formation mechanism and (2) formulation of pirate attack dynamics. Accordingly, the paper attempts to define the characteristics of Pirate Networks and to formulate the rules that govern the operation and evolution of Pirate Networks. We discuss the clan based social system that facilitate pirate formation as well as the pirate network inter-action with the hosting clan system. Using published material, empirical data and surveys the paper attempts to establish credible formation mechanism and operational characterization of pirate attacks. The proposed framework accounts for clan dynamics and the interplay of social, ecological and physical spaces. Finally we conclude with a discussion on exploratory modeling for the refinement of the proposed framework and for empirically grounding proposed simulations.

The models of statistical physics used to study collective phenomena in some interdisciplinary contexts, such as social dynamics and opinion spreading, do not consider the effects of the memory on individual decision processes. On the contrary, in the Naming Game, a recently proposed model of Language formation, each agent chooses a particular state, or opinion, by means of a memory-based negotiation process, during which a variable number of states is collected and kept in memory. In this perspective, the statistical features of the number of states collected by the agents becomes a relevant quantity to understand the dynamics of the model, and the influence of topological properties on memory-based models. By means of a master equation approach, we analyze the internal agent dynamics of Naming Game in populations embedded on networks, finding that it strongly depends on very general topological properties of the system (e.g. average and fluctuations of the degree). However, the influence of topological properties on the microscopic individual dynamics is a general phenomenon that should characterize all those social interactions that can be modeled by memory-based negotiation processes.

Standard game theory assumes that the structure of the game is common knowledge among players. We relax this assumption by considering extensive games where agents may be unaware of the complete structure of the game. In particular, they may not be aware of moves that they and other agents can make. We show how such games can be represented; the key idea is to describe the game from the point of view of every agent at every node of the game tree. We provide a generalization of Nash equilibrium and show that every game with awareness has a generalized Nash equilibrium. Finally, we extend these results to games with awareness of unawareness, where a player i may be aware that a player j can make moves that i is not aware of, and to subjective games, where payers may have no common knowledge regarding the actual game and their beliefs are incompatible with a common prior.