Solving multiagent planning problems modeled as DEC-POMDPs is an important challenge.  These models are often solved by using dynamic programming, but the high resource usage of current approaches results in limited scalability.  To improve the efficiency of dynamic programming algorithms, we propose a new backup algorithm that is based on a reachability analysis of the state space.  This method, which we call incremental policy generation, can be used to produce an optimal solution for any possible initial state or further scalability can be achieved by making use of a known start state. When incorporated into the optimal dynamic programming algorithm, our experiments show that planning horizon can be increased due to a marked reduction in resource consumption. This approach also fits nicely with approximate dynamic programming algorithms.  To demonstrate this, we incorporate it into the state-of-the-art PBIP algorithm and show significant performance gains.  The results suggest  that the performance of other dynamic programming algorithms for DEC-POMDPs could be similarly improved by integrating the incremental policy generation approach.

We describe in this article a multiagent urban traffic simulation, as we believe individual-based modeling is necessary to encompass the complex influence the actions of an individual vehicle can have on the overall flow of vehicles. We first describe how we build a graph description of the network from purely geometric data, ESRI shapefiles. We then explain how we include traffic related data to this graph. We go on after that with the model of the vehicle agents: origin and destination, driving behavior, multiple lanes, crossroads, and interactions with the other vehicles in day-to-day, ?ordinary? traffic. We conclude with the presentation of the resulting simulation of this model on the Rouen agglomeration.

In this paper, we investigate knowledge reasoning within a simple framework called knowledge structure. We use variable forgetting as a basic operation for one agent to reason about its own or other agents\' knowledge. In our framework, two notions namely agents\' observable variables and the weakest sufficient condition play important roles in knowledge reasoning. Given a background knowledge base and a set of observable variables for each agent, we show that the notion of an agent knowing a formula can be defined as a weakest sufficient condition of the formula under background knowledge base. Moreover, we show how to capture the notion of common knowledge by using a generalized notion of weakest sufficient condition. Also, we show that public announcement operator can be conveniently dealt with via our notion of knowledge structure. Further, we explore the computational complexity of the problem whether an epistemic formula is realized in a knowledge structure. In the general case, this problem is PSPACE-hard; however, for some interesting subcases, it can be reduced to co-NP. Finally, we discuss possible applications of our framework in some interesting domains such as the automated analysis of the well-known muddy children puzzle and the verification of the revised Needham-Schroeder protocol. We believe that there are many scenarios where the natural presentation of the available information about knowledge is under the form of a knowledge structure. What makes it valuable compared with the corresponding multi-agent S5 Kripke structure is that it can be much more succinct.

A key question in cooperative game theory is that of coalitional stability, usually captured by the notion of the \emph{core}--the set of outcomes such that no subgroup of players has an incentive to deviate. However, some coalitional games have empty cores, and any outcome in such a game is unstable. In this paper, we investigate the possibility of stabilizing a coalitional game by using external payments. We consider a scenario where an external party, which is interested in having the players work together, offers a supplemental payment to the grand coalition (or, more generally, a particular coalition structure). This payment is conditional on players not deviating from their coalition(s). The sum of this payment plus the actual gains of the coalition(s) may then be divided among the agents so as to promote stability. We define the \emph{cost of stability (CoS)} as the minimal external payment that stabilizes the game. We provide general bounds on the cost of stability in several classes of games, and explore its algorithmic properties. To develop a better intuition for the concepts we introduce, we provide a detailed algorithmic study of the cost of stability in weighted voting games, a simple but expressive class of games which can model decision-making in political bodies, and cooperation in multiagent settings. Finally, we extend our model and results to games with coalition structures.

We study the complexity of influencing elections through bribery: How computationally complex is it for an external actor to determine whether by paying certain voters to change their preferences a specified candidate can be made the elections winner? We study this problem for election systems as varied as scoring protocols and Dodgson voting, and in a variety of settings regarding homogeneous-vs.-nonhomogeneous electorate bribability, bounded-size-vs.-arbitrary-sized candidate sets, weighted-vs.-unweighted voters, and succinct-vs.-nonsuccinct input specification. We obtain both polynomial-time bribery algorithms and proofs of the intractability of bribery, and indeed our results show that the complexity of bribery is extremely sensitive to the setting. For example, we find settings in which bribery is NP-complete but manipulation (by voters) is in P, and we find settings in which bribing weighted voters is NP-complete but bribing voters with individual bribe thresholds is in P. For the broad class of elections (including plurality, Borda, k-approval, and veto) known as scoring protocols, we prove a dichotomy result for bribery of weighted voters: We find a simple-to-evaluate condition that classifies every case as either NP-complete or in P.

This thesis aims to provide a foundation for designing computer agents able to work better with people and with other agents in heterogeneous groups. When agents work together on a collaborative activity, in addition to performing their share of the activity, they may be able to help one another and thus improve the collective utility. The thesis specifically focuses on investigating the question of how, when and what kinds of helpful behavior should emerge when agents collaborate, taking into account the costs of a helpful action. It considers collaborative activities that take place in settings in which there is uncertainty about agents' capabilities and about the state of the world. To ensure that helpful behavior improves the overall benefit of the collaboration, the thesis incorporates decision-theoretic mechanisms for managing helpful behavior into existing formalizations of collaborative activity. It provides an investigation of the way people perceive the usefulness of helpful actions when proposed by a computer agent. It proposes incentives for facilitating collaboration among self-interested agents. In addition to these theoretical and empirical contributions, my findings are applied to several real-life application domains with different characteristics.

Multi-agent pathfinding is a challenging problem with many important real-life applications. Despite its completeness and solution solution optimality guarantees, a global search such as centralised A* has little practical value due to its exponential state space. Scalability to larger problems has been achieved with decentralized approaches, which decompose an initial problem into a series of searches. Even though their CPU and memory requirements are significantly lower, existing decentralized methods are incomplete and provide no criteria to distinguish between problems that can successfully be solved and problems where such algorithms fail. Further, no guarantees are given with respect to the running time, the memory requirements, and the quality of the computed solutions. Addressing such limitations is the central motivation for our recent and current work on identifying a tractable class of problems and developing an algorithm that is complete on this class of problems, with guarantees of low-polynomial running time, memory requirements and solution length.

In large, distributed sensor web systems, allocating resources to complex user tasks presents significant challenges. Sensor web users and their desired tasks have differing importance in the sensor web, so designing a multi-agent framework to yield allocations that are both fair and efficient (high utility) is a challenging research problem. With complex, hierarchically-decomposable tasks, individual subtasks could potentially be assigned to a number of agents (e.g., when there is overlap in sensor or data processing capability among constituent sensor networks). Efficient allocation of subtasks within the proposed multi-agent framework presents additional challenges. Both of these research problems are further compounded by the dynamic nature of the sensor web, in which both desired tasks and resource availability change significantly with time and environmental conditions. This paper presents an overview of these research challenges and a solution approach employing broker agents in a novel variation of the contract net protocol (CNP) for fair and efficient allocation of complex tasks.

Deadline pressures, unexpected events, and combinatorial numbers of possible courses of action often lead a person to decide which activity she will begin next without considering a full enumeration of possible schedules, and thus, without a full awareness of the implications that her choice will have on the rest of her day's schedule. Furthermore, people suffering from cognitive impairments may lack the abilities to perform such reasoning in the first place. The goal of my thesis is to develop foundational technologies for computational agents that augment the abilities of people who face the above challenges to reason about the implications of scheduling. In particular, I develop, integrate, and evaluate new techniques for solving multi-agent Hybrid Scheduling Problems, which support coordinated activity selection and scheduling for human users.

This paper describes a novel approach based on a combination of techniques in AI, parallel computing, and network science to address an important problem in social sciences and public health: planning and responding in the event of epidemics. Spread of infectious disease is an important societal problem -- human behavior, social networks, and the civil infrastructures all play a crucial role in initiating and controlling such epidemic processes.  We specifically consider the economic and social effects of realistic interventions  proposed and adopted by public health officials and behavioral changes  of  private citizens in the event of a ``flu-like'' epidemic. Our results provide new insights for developing robust public policies that can prove useful for epidemic planning.