Intelligent Agents Lab

Abstract

In open Multi-Agent Systems, where there is no centralised control and individuals have equal authority, ensuring cooperative and coordinated behaviour is challenging. Norms and conventions are a useful means of supporting cooperation in an emergent decentralised manner, however it takes time for effective norms and conventions to emerge. Identifying influential individuals enables the targeted seeding of desirable norms and conventions, which can reduce the establishment time and increase efficacy. Existing research is limited with respect to considering (i) how to identify influential agents, (ii) the extent to which network location imbues influence on an agent, and (iii) the extent to which different network structures affect influence. In this paper, we propose a general methodology for learning the network value of a node in terms of influence, and evaluate it using sampled real-world networks with a model of convention emergence that has realistic assumptions about the size of the convention space. We show that (i) the models resulting from our methodology are effective in predicting influential network locations, (ii) there are very few locations that can be classified as influential in typical networks, (iii) that four single metrics are robustly indicative of influence across a range of network structures, and (iv) our methodology learns which single metric or combined measure is the best predictor of influence in a given network.

Abstract

Understanding the dynamics of reciprocation is of great interest in sociology and computational social science. The recent growth of Massively Multi-player Online Games (MMOGs) has provided unprecedented access to large-scale data which enables us to study such complex human behavior in a more systematic manner. In this paper, we consider three different networks in the EverQuest2 game: chat, trade, and trust. The chat network has the highest level of reciprocation (33%) because there are essentially no barriers to it. The trade network has a lower rate of reciprocation (27%) because it has the obvious barrier of requiring more goods or money for exchange; morever, there is no clear benefit to returning a trade link except in terms of social connections. The trust network has the lowest reciprocation (14%) because this equates to sharing certain within-game assets such as weapons, and so there is a high barrier for such connections because they require faith in the players that are granted such high access. In general, we observe that reciprocation rate is inversely related to the barrier level in these networks. We also note that reciprocation has connections across the heterogeneous networks. Our experiments indicate that players make use of the medium-barrier reciprocations to strengthen a relationship. We hypothesize that lower-barrier interactions are an important component to predicting higherbarrier ones. We verify our hypothesis using predictive models for trust reciprocations using features from trade interactions. Using the number of trades (both before and after the intial trust link) boosts our ability to predict if the trust will be reciprocated up to 11% with respect to the AUC. More generally, we see strong correlations across the different networks and emphasize that network dynamics, such as reciprocation, cannot be studied in isolation on just a single type of connection.

Abstract

When users post photos on Facebook, they have the option of allowing their friends, followers, or anyone at all to subsequently reshare the photo. A portion of the billions of photos posted to Facebook generates cascades of reshares, enabling many additional users to see, like, comment, and reshare the photos. In this paper we present characteristics of such cascades in aggregate, finding that a small fraction of photos account for a significant proportion of reshare activity and generate cascades of non-trivial size and depth. We also show that the true influence chains in such cascades can be much deeper than what is visible through direct attribution. To illuminate how large cascades can form, we study the diffusion trees of two widely distributed photos: one posted on President Barack Obama’s page following his reelection victory, and another posted by an individual Facebook user hoping to garner enough likes for a cause.We show that the two cascades, despite achieving comparable total sizes, are markedly different in their time evolution, reshare depth distribution, predictability of subcascade sizes, and the demographics of users who propagate them. The findings suggest not only that cascades can achieve considerable size but that they can do so in distinct ways.

Abstract

The multi-robot manipulation task, where a team of robots cooperatively lift and move objects, is exceptionally difficult due to the synchronization between the robots. Although increasing the number of robots can expand the area that the robots can cover within a bounded period of time, a poor human-robot interface will ultimately compromise the performance of the team of robots. However, introducing a human operator to the team of robots, does not automatically improve performance due to the difficulty of teleoperating mobile robots with manipulators. The human operator’s concentration is divided not only among multiple robots but also between controlling each robot’s base and arm. This complexity substantially increases the potential neglect time, since the operator’s inability to effectively attend to each robot during a critical phase of the task leads to a significant degradation in task performance. In this dissertation, I propose to develop an agent-based user interface for multi-robot manipulation interface that identifies and manages any single robot that is not currently being controlled by the human operator, as well a learning from demonstration technique with the robots learning from the pre recorded macro representation of the specified task. Propagating the user’s macro commands from the actively-controlled robot to the neglected robot allows the neglected robot to leverage this control information and position itself effectively without direct human supervision. The objective of robot learning from demonstration is to have a robot learn from watching a demonstration of the task to be performed. A policy is calculated based on the task learned from demonstrations in which the user verifies that the robot has executed the macro correctly in a new situation.

Abstract

With the rapid expansion of the Internet and WWW, the problem of analyzing social media data has received an increasing amount of attention in the past decade. The boom in social media platforms offers many possibilities to study human collective behavior and interactions on an unprecedented scale. In the past, much work has been done on the problem of learning from networked data with homogeneous topologies, where instances are explicitly or implicitly interconnected by a single type of relationship. In contrast to traditional content-only classification methods, relational learning succeeds in improving classification performance by leveraging the correlation of the labels between linked instances. However, networked data extracted from social media, web pages, and bibliographic databases can contain entities of multiple classes and linked by various causal reasons, hence treating all links in a homogeneous way can limit the performance of relational classifiers. Learning the collective behavior and interactions in heterogeneous networks becomes much more complex. The contribution of this thesis include 1) classification frameworks for identifying human collective behavior in multi-relational social networks. 2) supervised learning models for relationship prediction in multi-relational collaborative networks. Our methods improve the performance of homogeneous relational models by differentiating heterogeneous relations and capturing the prominent interaction patterns underlying the network structure. The work has been evaluated in various real-world social networks as well as synthetically generated datasets. We believe that this study will be useful for analyzing human collective behavior and interactions specifically in the scenario when the heterogeneous relationships in the network arise from various causal reasons.

Abstract

Online social networking technologies enable individuals to simultaneously share information with any number of peers. Quantifying the causal effect of these mediums on the dissemination of information requires not only identification of who influences whom, but also of whether individuals would still propagate information in the absence of social signals about that information. We examine the role of social networks in online information diffusion with a large-scale eld experiment that randomizes exposure to signals about friends' information sharing among 253 million subjects in situ. Those who are exposed are significantly more likely to spread information, and do so sooner than those who are not exposed. We further examine the relative role of strong and weak ties in information propagation. We show that, although stronger ties are individually more influential, it is the more abundant weak ties who are responsible for the propagation of novel information. This suggests that weak ties may play a more dominant role in the dissemination of information online than currently believed.

Abstract

We consider learning in a Markov decision process where we are not explicitly given a reward function, but where instead we can observe an expert demonstrating the task that we want to learn to perform. This setting is useful in applications (such as the task of driving) where it may be difficult to write down an explicit reward function specifying exactly how different desiderata should be traded o. We think of the expert as trying to maximize a reward function that is expressible as a linear combination of known features, and give an algorithm for learning the task demonstrated by the expert. Our algorithm is based on using "inverse reinforcement learning" to try to recover the unknown reward function. We show that our algorithm terminates in a small number of iterations, and that even though we may never recover the expert's reward function, the policy output by the algorithm will attain performance close to that of the expert, where here performance is measured with respect to the expert's unknown reward function.

Abstract

We consider the problem of learning to follow a desired trajectory when given a small number of demonstrations from a sub-optimal expert. We present an algorithm that (i) extracts the—initially unknown—desired trajectory from the sub-optimal expert’s demonstrations and (ii) learns a local model suitable for control along the learned trajectory. We apply our algorithm to the problem of autonomous helicopter flight. In all cases, the autonomous helicopter’s performance exceeds that of our expert helicopter pilot’s demonstrations. Even stronger, our results significantly extend the state-of-the-art in autonomous helicopter aerobatics. In particular, our results include the first autonomous tic-tocs, loops and hurricane, vastly superior performance on previously performed aerobatic maneuvers (such as in-place flips and rolls), and a complete airshow, which requires autonomous transitions between these and various other maneuvers.

Abstract

Participatory sensing is a revolutionary new paradigm in which volunteers collect and share information from their local environment using mobile phones. The inherent open- ness of this platform makes it easy to contribute corrupted data. This paper proposes a novel reputation system that employs the Gompertz function for computing device rep- utation score as a re ection of the trustworthiness of the contributed data. We implement this system in the con- text of a participatory noise monitoring application and con- duct extensive real-world experiments using Apple iPhones. Experimental results demonstrate that our scheme achieves three-fold improvement in comparison with the state-of-the- art Beta reputation scheme.

Abstract

Agent-based models are a useful technique for rapidly prototyping complex social systems; they are widely used in a number of disciplines and can yield theoretical insights that are different from those produced by a variable based analysis. However, it remains difficult to compare the results of two models and to validate the performance of an agent-based simulation. In this paper, we present a case study on how to analyze the relationship between agent-based models using category theory. Category theory is a powerful mathematical methodology that was originally introduced to organize mathematical ideas according to their shared structure. It has been successfully employed in abstract mathematical domains, but has also enjoyed some success as a formalism for software engineering. Here we present a procedure for analyzing agent-based models using category theory and a case study in its usage at analyzing two different types of simulations.

Abstract

Reputation systems can be used to foster good behaviour and to encourage adherence to contracts in e-commerce. Several reputation systems have been deployed in practical applications or proposed in the literature. This paper describes a new system called the beta reputation system which is based on using beta probability density functions to combine feedback and derive reputation ratings. The advantage of the beta reputation system is flexibility and simplicity as well as its foundation on the theory of statistics.