Topology-aware approach for the emergence of social norms in multiagent systems

Social norms facilitate agent coordination and conflict resolution without explicit communication. Norms generally involve restrictions on a set of actions or behaviors of agents to a particular strategy and can significantly reduce the cost of coordination. There has been recent progress in multiagent systems (MAS) research to develop a deep understanding of the social norm formation process. This includes developing mechanisms to create social norms in an effective and efficient manner. The hypothesis of this dissertation is that equipping agents in networked MAS with "network thinking" capabilities and using this contextual knowledge to form social norms in an effective and efficient manner improves the performance of the MAS. This dissertation investigates the social norm emergence problem in conventional norms (where there is no conflict between individual and collective interests) and essential norms (where agents need to explicitly cooperate to achieve socially-efficient behavior) from a game-theoretic perspective. First, a comprehensive investigation of the social norm formation problem is performed in various types of networked MAS with an emphasis on the effect of the topological structures on the process. Based on the insights gained from these network-theoretic investigations, novel topology-aware decentralized mechanisms are developed that facilitate the emergence of social norms suitable for various environments. It addresses the convention emergence problem in both small and large conventional norm spaces and equip agents to predict the topological structure to use the suitable convention mechanisms. It addresses the cooperation emergence problem in the essential norm space by harnessing agent commitments and altruism where appropriate. Extensive simulation based experimentation has been conducted on different network topologies by varying the topological features and agent interaction models. Comparisons with state-of-the-art norm formation techniques show that proposed mechanisms facilitate significant improvement in performance in a variety of networks.