Advances in Complex Systems

Despite the fact that social networks are ubiquitous on the Internet, only few websites exploit the potential of combining user communities and online marketplaces. Not many platforms allow users to engage in a phenomenon called "group buying" — buyers joining groups, or coalitions, to bundle their purchasing power towards sellers. We argue that this may be due to a lack of face-to-face interaction on the Internet; often, users do not know which other users to trust, which makes them suspicious of engaging in online business, in particular if many unknown other parties are involved. This situation, however, can be alleviated by leveraging the social networks of users: based on who a user knows and is connected to, a trust metric — for example, the TrustWebRank metric developed by us — can be computed to assess who else may be considered trustworthy to that user. In this paper, we build a simple agent-based model of coalition formation among agents in the setting of group buying in an electronic marketplace. In this model, agents use their trust relationships in order to determine who to form coalitions with. We show that this leads agents to experience high utility and that agents are able to learn who is trustworthy and who is not, even when they have no initial knowledge about the trustworthiness of other agents. This work may provide the foundation for a real-world application of an online coalition formation platform for e-commerce built on a social networking platform such as Facebook.

In many e-commerce sites, recommender systems, which provide personalized recommendations from among a large number of items, have recently been introduced. Collaborative filtering is one of the most successful algorithms which provide recommendations using ratings of users on items. There are two approaches: user-based and item-based collaborative filtering. Additionally a unifying method for user-based and item-based collaborative filtering was proposed to improve the recommendation accuracy. The unifying approach uses a constant value as a weight parameter to unify both algorithms. However, because the optimal weight for unifying is actually different depending on the situation, the algorithm should estimate an appropriate weight dynamically, and should use it. In this research, we first investigate the relationship between recommendation accuracy and the weight parameter. The results show that the optimal weight is different depending on the situation. Second, we propose an approach for estimation of the appropriate weight value based on collected ratings. Then, we discuss the effectiveness of the proposed approach based on both multi-agent simulation and the MovieLens dataset. The results show that the proposed approach can estimate the weight value within an error rate of 0.5% for the optimal weight.

Axelrod's model describes the dissemination of a set of cultural traits in a society constituted by individual agents. In a social context, nevertheless, individual choices toward a specific attitude are also at the basis of the formation of communities, groups and parties. The membership in a group changes completely the behavior of single agents who start acting according to a social identity. Groups act and interact among them as single entities, but still conserve an internal dynamics. We show that, under certain conditions of social dynamics, the introduction of group dynamics in a cultural dissemination process avoids the flattening of the culture into a single entity and preserves the multiplicity of cultural attitudes. We also consider diffusion processes on this dynamical background, showing the conditions under which information as well as innovation can spread through the population in a scenario where the groups' choices determine the social structure.

Two distinct learning mechanisms are considered for a population of agents who engage in decentralized search for the common optimum. An agent may choose to learn via innovation (individual learning) or via imitation (social learning). The agents are endowed with heterogeneous skills in engaging in the two modes of learning. When the agents choose imitation, they also choose whom to learn from. This leads to the emergence of a social learning network among agents in the population. This paper focuses on the impact the endowed learning skills have on the individual's choice of learning mechanism as well as the micro and macro structure of the evolving network. Finally, it explores the impact the degree of environmental volatility has on the structure of such networks.

Social conventions are useful self-sustaining protocols for groups to coordinate behavior without a centralized entity enforcing coordination. The emergence of such conventions in different multi agent network topologies has been investigated by several researchers, although exploring only specific cases of the convention emergence process. In this work we will provide multi-dimensional analysis of several factors that we believe determines the process of convention emergence, such as: the size of agents memory, the population size and structure, the learning approach taken by agents, the amount of players in the interactions, or the convention search space dimension. Although we will perform an exhaustive study of different network structures, we are concerned that different topologies will affect the emergence in different ways. Therefore, the main research question in this work is comparing and studying effects of different topologies on the emergence of social conventions. While others have investigated memory for learning algorithms, the effects of memory on the reward have not been investigated thoroughly. We propose a reward metric that is derived directly from the history of the interacting agents. Another research question to be answered is what effect does the history based reward function and the learning approach have on convergence time in different topologies. Experimental results show that all the factors analyzed affect differently the convention emergence process, being such information very useful for policy-makers when designing self-regulated systems.

This paper examines the evolution of agent strategies in a commons dilemma using a tag interaction model. Using a tag-mediated interaction model, individual's can determine their interactions based on their tag similarity. The experimental results show the significance of agent strategies that contribute to the overall value of the commons. The paper also examines the significance of viscosity on the emergence of cooperation in the commons dilemma. Viscosity represents a specific form of openness that will be examined in the paper. An initial series of experiments demonstrates the role of tags in the n-player dilemma while subsequent experiments examine the impact of openness on the evolution of agent strategies. The paper shows the emergence of cooperation through tag-mediated interactions. Simulation results show the emergence of strategies that contribute heavily to the value of the shared commons. The role of viscosity on the population strategy set is examined and this is similar to some forms of openness in multi-agent environments.

This paper investigates the impact of reward shaping in multi-agent reinforcement learning as a way to incorporate domain knowledge about good strategies. In theory, potential-based reward shaping does not alter the Nash Equilibria of a stochastic game, only the exploration of the shaped agent. We demonstrate empirically the performance of reward shaping in two problem domains within the context of RoboCup KeepAway by designing three reward shaping schemes, encouraging specific behaviour such as keeping a minimum distance from other players on the same team and taking on specific roles. The results illustrate that reward shaping with multiple, simultaneous learning agents can reduce the time needed to learn a suitable policy and can alter the final group performance.

The design of reinforcement learning solutions to many problems artificially constrain the action set available to an agent, in order to limit the exploration/sample complexity. While exploring, if an agent can discover new actions that can break through the constraints of its basic/atomic action set, then the quality of the learned decision policy could improve. On the flipside, considering all possible non-atomic actions might explode the exploration complexity. We present a novel heuristic solution to this dilemma, and empirically evaluate it in grid navigation tasks. In particular, we show that both the solution quality and the sample complexity improve significantly when basic reinforcement learning is coupled with action discovery. Our approach relies on reducing the number of decision points, which is particularly suited for multiagent coordination learning, since agents tend to learn more easily with fewer coordination problems (CPs). To demonstrate this we extend action discovery to multi-agent reinforcement learning. We show that Joint Action Learners (JALs) indeed learn coordination policies of higher quality with lower sample complexity when coupled with action discovery, in a multi-agent box-pushing task.