Multiagent coordination in cooperative multiagent systems (MASs) has been widely studied in both fixed-agent repeated interaction setting and the static social learning framework. However, two aspects of dynamics in real-world multiagent scenarios are currently missing in existing works. First, the network topologies can be dynamic where agents may change their connections through rewiring during the course of interactions. Second, the game matrix between each pair of agents may not be static and usually not known as a prior. Both the network dynamic and game uncertainty increase the coordination difficulty among agents. In this paper, we consider a multiagent dynamic social learning environment in which each agent can choose to rewire potential partners and interact with randomly chosen neighbors in each round. We propose an optimal rewiring strategy for agents to select most beneficial peers to interact with for the purpose of maximizing the accumulated payoff in repeated interactions. We empirically demonstrate the effectiveness and robustness of our approach through comparing with benchmark strategies. The performance of three representative learning strategies under our social learning framework with our optimal rewiring is investigated as well.
There are some existing works on using rewiring mechanism to support cooperation in social networks @cite_8 @cite_26 @cite_33 @cite_27 . @cite_8 propose a new mechanism based on three main pillars: indirect reciprocity, coalitions and rewiring, to improve cooperation among self-interested agents placed in a complex network. Rewiring, as a part of the proposed mechanism, alters the worst social links with the best coalition members the neighbors' reputation coalitions information. They confirm that the use of rewiring indeed improves cooperation when they play the donation game in their social scenario. Griffiths and Luck present and demonstrate a decentralised tag-based mechanism to support cooperation in the presence of cheaters without requiring reciprocity. The simple rewiring enables agents to change their neighbour connections, in particular by removing connections to the worst neighbours and replacing them with connections to neighbours with whom others have had positive experiences. Their results show that cooperation can be improved by enabling agents to change their neighbour connections. In contrast, in this paper, we consider the multiagent coordination problem in cooperative MASs and how rewiring can increase the benefits of individual agents during long-run interactions under the social learning framework.
@cite_27 @cite_26 @cite_33 @cite_8
2135136710 2203503346 2106114848 1996008403
In systems of autonomous self-interested agents, in which agents' neighbourhoods are defined by their connections to others, cooperation can arise through observation of the behaviour of neighbours to determine values of trust and reputation. While there are many techniques for encouraging cooperative behaviour within such systems, they often require a centralised authority or rely on reciprocity that is not always available. In response, this paper presents a decentralised mechanism to supporting cooperation without requiring reciprocity. The mechanism is based on tag-based cooperation, supplemented by assessing neighbourhood context and using simple rewiring to cope with cheaters. In particular, the paper makes two key contributions. First, it provides a technique for increasing resilience in the face of malicious behaviour by enabling individuals to rewire their connections to others and so modify their neighbourhoods. Second, it provides an empirical analysis of several strategies for rewiring, evaluating them through simulations. It is generally known that cooperation can be achieved in complex real-world interactions that are not limited to direct interactions only. In particular, cooperation can consider prior interactions with other players, i.e., indirect reciprocity. Moreover, coalition based mechanisms have shown to facilitate cooperation among self-interested agents. Also, research on games over dynamic topologies has found empirical evidence showing that partner switching leads to cooperative behavior. In this paper we present a new mechanism to improve cooperation among self-interested agents placed in a complex network. Our mechanism is based on three main pillars: indirect reciprocity, coalitions and rewiring. Thus agents play against each other an indirect reciprocity game where they can create coalitions to share information about agents' reputation or change their personal network (social contacts). Altogether, we explore the conditions to enhance cooperation in complex networks. Finally, in our experiments we determine how, by using our mechanism, cooperation is improved in our reputation-based game, and how topology highly influences cooperation in our scenario. A longstanding idea in the literature on human cooperation is that cooperation should be reinforced when conditional cooperators are more likely to interact. In the context of social networks, this idea implies that cooperation should fare better in highly clustered networks such as cliques than in networks with low clustering such as random networks. To test this hypothesis, we conducted a series of experiments on Amazon Mechanical Turk, in which 24 individuals played a local public goods game arranged on one of five network topologies that varied between disconnected cliques and a random regular graph. In contrast with previous work, we found that network topology had no significant effect on average contributions. This result implies either that individuals are not conditional cooperators, or else that cooperation does not benefit from positive reinforcement between connected neighbors. We then tested both of these possibilities in two subsequent series of experiments in which artificial "seed" players were introduced, making either full or zero contributions. First, we found that although players did generally behave like conditional cooperators, they were as likely to decrease their contributions in response to low contributing neighbors as they were to increase their contributions in response to high contributing neighbors. Second, we found that positive effects of cooperation did not spread beyond direct neighbors in the network. In total we report on 113 human subjects experiments, highlighting the speed, flexibility, and cost-effectiveness of web-based experiments over those conducted in physical labs. In cooperative multiagent systems an alternative that maximizes the social welfare-the sum of utilities-can only be selected if each agent reports its full utility function. This may be infeasible in environments where communication is restricted. Employing a voting rule to choose an alternative greatly reduces the communication burden, but leads to a possible gap between the social welfare of the optimal alternative and the social welfare of the one that is ultimately elected. Procaccia and Rosenschein (2006) [13] have introduced the concept of distortion to quantify this gap. In this paper, we present the notion of embeddings into voting rules: functions that receive an agent@?s utility function and return the agent@?s vote. We establish that very low distortion can be obtained using randomized embeddings, especially when the number of agents is large compared to the number of alternatives. We investigate our ideas in the context of three prominent voting rules with low communication costs: Plurality, Approval, and Veto. Our results arguably provide a compelling reason for employing voting in cooperative multiagent systems.