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.

Aggregated phenomena in social sciences and economi cs are highly dependent on the way individuals interact. To help understanding the interplay betwe en socio-economic activities and underlying social networks, this paper studies a sequential prisoner's dilemma with binary choice. It proposes an analytical and computational insight about the role of endogenous networks in emergence and sustainability of cooperation and exhibits an alternative to the choice and refusal mechanism that is often proposed to explain cooperation. The study fo cuses on heterogeneous equilibriums and emergence of cooperation from an all-defector state that are the two stylized facts that this model successfully reconstructs.

We consider directed graphs over a set of n agents, where an edge (i,j) is taken to mean that agent i supports or trusts agent j. Given such a graph and an integer k\leq n, we wish to select a subset of k agents that maximizes the sum of indegrees, i.e., a subset of k most popular or most trusted agents. At the same time we assume that each individual agent is only interested in being selected, and may misreport its outgoing edges to this end. This problem formulation captures realistic scenarios where agents choose among themselves, which can be found in the context of Internet search, social networks like Twitter, or reputation systems like Epinions. Our goal is to design mechanisms without payments that map each graph to a k-subset of agents to be selected and satisfy the following two constraints: strategyproofness, i.e., agents cannot benefit from misreporting their outgoing edges, and approximate optimality, i.e., the sum of indegrees of the selected subset of agents is always close to optimal. Our first main result is a surprising impossibility: for k \in {1,...,n-1}, no deterministic strategyproof mechanism can provide a finite approximation ratio. Our second main result is a randomized strategyproof mechanism with an approximation ratio that is bounded from above by four for any value of k, and approaches one as k grows.

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.

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.

Agents and market mechanisms are widely elaborated and applied to automate interaction and decision processes among others in robotics, for decentralized control in sensor networks and by algorithmic traders in financial markets. Currently there is a high demand of efficient mechanisms for the provisioning, usage and allocation of distributed services in the Cloud. Such mechanisms and processes are not manually manageable and require decisions taken in quasi real-time. Thus agent decisions should automatically adapt to changing conditions and converge to optimal values. This paper presents a bidding strategy, which is capable of automating the bid generation and utility maximization processes of consumers and providers by the interaction with markets as well as to converge to optimal values. The bidding strategy is applied to the consumer side against benchmark bidding strategies and its behavior and convergence are evaluated in two market mechanisms, a centralized and a decentralized one.

In this paper, we study distributed algorithms for cooperative agents that  allow them to exchange their assigned tasks in order to reduce their team  cost. We define a new type of contract, called K-swaps, that describes multiple task exchanges among multiple agents at a time, which generalizes the concept of single task exchanges. We design a distributed algorithm that constructs all possible K-swaps that reduce the team cost of a given task allocation and show that each agent typically only needs to communicate a small part of its local computation results to the other agents. We then demonstrate empirically that K-swaps can reduce the team costs of several existing task-allocation algorithms significantly even if K is small.

Artificial societies — distributed systems of autonomous agents — are becoming increasingly important in e-commerce. Agents base their decisions on trust and reputation in ways analogous to human societies. Many different definitions for trust and reputation have been proposed that incorporate many sources of information; however, system designs have tended to focus much of their attention on direct interactions. Furthermore, trust updating schemes for direct interactions have tended to uncouple updates for positive and negative feedback. Consequently, behaviour in which cycles of positive feedback followed by a single negative feedback results in untrustworthy agents remaining undetected. This con-man style of behaviour is formally described and desirable characteristics of con-resistant trust schemes proposed. A con-resistant scheme is proposed and compared with FIRE, Regret and Yu and Singh's model. Simulation experiments demonstrate the utility of the con-resistant scheme.

Coalition structure generation has received considerable attention in recent research. Several algorithms have been proposed to solve this problem in Characteristic Function Games (CFGs), where every coalition is assumed to perform equally well in any coalition structure containing it. In contrast, very little attention has been given to the more general Partition Function Games (PFGs), where a coalition's effectiveness may change from one coalition structure to another. In this paper, we deal with PFGs with positive and negative externalities. In this context, we identify the minimum search that is required in order to establish a bound on the quality of the best coalition structure found. We then develop an anytime algorithm that improves this bound with further search, and show that it outperforms the existing state-of-the-art algorithms by orders of magnitude.

Planning under uncertainty for multiple agents has flourished with the development of formal models such as multi-agent MDPs and decentralized MDPs. Despite their richness, applicability of these models remains limited due to their computational complexity. We present the class of event-detecting Multi-agent MDPs (eMMDPs), designed to detect multiple mobile targets by a team of sensor agents. We show that eMMDPs are NP-Hard and present a scalable 2-approximation algorithm for solving them using matroid theory and constraint optimization. Its complexity is linear in the state-space and number of agents, quadratic in the horizon, and exponential only in a small parameter that depends on the interaction among the agents. Despite the worst-case approximation ratio of 2, experimental results show that the algorithm produces nearoptimal policies for a range of test problems.