Refinement of defection strategies stabilizes cooperation

Cooperation among unrelated individuals is an enduring evolutionary riddle and a number of possible solutions have been suggested. Most of these suggestions attempt to refine cooperative strategies, while little attention is given to the fact that novel defection strategies can also evolve in the population. Especially in the presence of punishment to the defectors and public knowledge of strategies employed by the players, a defecting strategy that avoids getting punished by selectively cooperating only with the punishers can get a selective benefit over non-conditional defectors. Furthermore, if punishment ensures cooperation from such discriminating defectors, defectors who punish other defectors can evolve as well. We show that such discriminating and punishing defectors can evolve in the population by natural selection in a Prisoner’s Dilemma game scenario, even if discrimination is a costly act. These refined defection strategies destabilize unconditional defectors. They themselves are, however, unstable in the population. Discriminating defectors give selective benefit to the punishers in the presence of non-punishers by cooperating with them and defecting with others. However, since these players also defect with other discriminators they suffer fitness loss in the pure population. Among the punishers, punishing cooperators always benefit in contrast to the punishing defectors, as the latter not only defect with other punishing defectors but also punish them and get punished. As a consequence of both these scenarios, punishing cooperators get stabilized in the population. We thus show ironically that refined defection strategies stabilize cooperation. Furthermore, cooperation stabilized by such defectors can work under a wide range of initial conditions and is robust to mistakes.

Learning Optimal Discriminant Functions through a Cooperative Game of Automata

The problem of learning correct decision rules to minimize the probability of misclassification is a long-standing problem of supervised learning in pattern recognition. The problem of learning such optimal discriminant functions is considered for the class of problems where the statistical properties of the pattern classes are completely unknown. The problem is posed as a game with common payoff played by a team of mutually cooperating learning automata. This essentially results in a probabilistic search through the space of classifiers. The approach is inherently capable of learning discriminant functions that are nonlinear in their parameters also. A learning algorithm is presented for the team and convergence is established. It is proved that the team can obtain the optimal classifier to an arbitrary approximation. Simulation results with a few examples are presented where the team learns the optimal classifier.

A cooperative game of a pair of learning automata

A cooperative game played in a sequential manner by a pair of learning automata is investigated in this paper. The automata operate in an unknown random environment which gives a common pay-off to the automata. Necessary and sufficient conditions on the functions in the reinforcement scheme are given for absolute monotonicity which enables the expected pay-off to be monotonically increasing in any arbitrary environment. As each participating automaton operates with no information regarding the other partner, the results of the paper are relevant to decentralized control.

Location of Pathogenic Bacteria during Persistent Infections: Insights from an Analysis Using Game Theory

Bacterial persistent infections are responsible for a significant amount of the human morbidity and mortality. Unlike acute bacterial infections, it is very difficult to treat persistent bacterial infections (e.g. tuberculosis). Knowledge about the location of pathogenic bacteria during persistent infection will help to treat such conditions by designing novel drugs which can reach such locations. In this study, events of bacterial persistent infections were analyzed using game theory. A game was defined where the pathogen and the host are the two players with a conflict of interest. Criteria for the establishment of Nash equilibrium were calculated for this game. This theoretical model, which is very simple and heuristic, predicts that during persistent infections pathogenic bacteria stay in both intracellular and extracellular compartments of the host. The result of this study implies that a bacterium should be able to survive in both intracellular and extracellular compartments of the host in order to cause persistent infections. This explains why persistent infections are more often caused by intracellular pathogens like Mycobacterium and Salmonella. Moreover, this prediction is in consistence with the results of previous experimental studies.

A cooperative game theoretic approach to prototype selection

In this paper we consider the task of prototype selection whose primary goal is to reduce the storage and computational requirements of the Nearest Neighbor classifier while achieving better classification accuracies. We propose a solution to the prototype selection problem using techniques from cooperative game theory and show its efficacy experimentally.

Experimental implementation of a three qubit quantum game with corrupt source using nuclear magnetic resonance quantum information processor

In a three player quantum `Dilemma' game each player takes independent decisions to maximize his/her individual gain. The optimal strategy in the quantum version of this game has a higher payoff compared to its classical counterpart. However, this advantage is lost if the initial qubits provided to the players are from a noisy source. We have experimentally implemented the three player quantum version of the `Dilemma' game as described by Johnson, [N.F. Johnson, Phys. Rev. A 63 (2001) 020302(R)] using nuclear magnetic resonance quantum information processor and have experimentally verified that the payoff of the quantum game for various levels of corruption matches the theoretical payoff. (c) 2007 Elsevier Inc. All rights reserved.

Selective attention in a synchronising bushcricket: physiology

Synchronising bushcricket males achieve synchrony by delaying their chirps in response to calling neighbours. In multi-male choruses, males that delay chirps in response to all their neighbours would remain silent most of the time and be unable to attract mates. This problem could be overcome if the afferent auditory system exhibited selective attention, and thus a male interacted only with a subset of neighbours. We investigated whether individuals of the bushcricket genus Mecopoda restricted their attention to louder chirps neurophysiologically, behaviourally and through spacing. We found that louder leading chirps were preferentially represented in the omega neuron but the representation of softer following chirps was not completely abolished. Following chirps that were 20 dB louder than leading chirps were better represented than leading chirps. During acoustic interactions, males synchronised with leading chirps even when the following chirps were 20 dB louder. Males did not restrict their attention to louder chirps during interactions but were affected by all chirps above a particular threshold. In the field, we found that males on average had only one or two neighbours whose calls were above this threshold. Selective attention is thus achieved in this bushcricket through spacing rather than neurophysiological filtering of softer signals.

Selective attention in a synchronising bushcricket: physiology, behaviour and ecology

Synchronising bushcricket males achieve synchrony by delaying their chirps in response to calling neighbours. In multi-male choruses, males that delay chirps in response to all their neighbours would remain silent most of the time and be unable to attract mates. This problem could be overcome if the afferent auditory system exhibited selective attention, and thus a male interacted only with a subset of neighbours. We investigated whether individuals of the bushcricket genus Mecopoda restricted their attention to louder chirps neurophysiologically, behaviourally and through spacing. We found that louder leading chirps were preferentially represented in the omega neuron but the representation of softer following chirps was not completely abolished. Following chirps that were 20 dB louder than leading chirps were better represented than leading chirps. During acoustic interactions, males synchronised with leading chirps even when the following chirps were 20 dB louder. Males did not restrict their attention to louder chirps during interactions but were affected by all chirps above a particular threshold. In the field, we found that males on average had only one or two neighbours whose calls were above this threshold. Selective attention is thus achieved in this bushcricket through spacing rather than neurophysiological filtering of softer signals.

Selective attention in a synchronising bushcricket: physiology, behaviour and ecology

Synchronising bushcricket males achieve synchrony by delaying their chirps in response to calling neighbours. In multi-male choruses, males that delay chirps in response to all their neighbours would remain silent most of the time and be unable to attract mates. This problem could be overcome if the afferent auditory system exhibited selective attention, and thus a male interacted only with a subset of neighbours. We investigated whether individuals of the bushcricket genus Mecopoda restricted their attention to louder chirps neurophysiologically, behaviourally and through spacing. We found that louder leading chirps were preferentially represented in the omega neuron but the representation of softer following chirps was not completely abolished. Following chirps that were 20 dB louder than leading chirps were better represented than leading chirps. During acoustic interactions, males synchronised with leading chirps even when the following chirps were 20 dB louder. Males did not restrict their attention to louder chirps during interactions but were affected by all chirps above a particular threshold. In the field, we found that males on average had only one or two neighbours whose calls were above this threshold. Selective attention is thus achieved in this bushcricket through spacing rather than neurophysiological filtering of softer signals.

Two-agent cooperative search using game models with endurance-time constraints

In this article, the problem of two Unmanned Aerial Vehicles (UAVs) cooperatively searching an unknown region is addressed. The search region is discretized into hexagonal cells and each cell is assumed to possess an uncertainty value. The UAVs have to cooperatively search these cells taking limited endurance, sensor and communication range constraints into account. Due to limited endurance, the UAVs need to return to the base station for refuelling and also need to select a base station when multiple base stations are present. This article proposes a route planning algorithm that takes endurance time constraints into account and uses game theoretical strategies to reduce the uncertainty. The route planning algorithm selects only those cells that ensure the agent will return to any one of the available bases. A set of paths are formed using these cells which the game theoretical strategies use to select a path that yields maximum uncertainty reduction. We explore non-cooperative Nash, cooperative and security strategies from game theory to enhance the search effectiveness. Monte-Carlo simulations are carried out which show the superiority of the game theoretical strategies over greedy strategy for different look ahead step length paths. Within the game theoretical strategies, non-cooperative Nash and cooperative strategy perform similarly in an ideal case, but Nash strategy performs better than the cooperative strategy when the perceived information is different. We also propose a heuristic based on partitioning of the search space into sectors to reduce computational overhead without performance degradation.

Design of incentive compatible protocols for wireless networks: A game theoretic approach

In this thesis work, we design rigorous and efficient protocols/mechanisms for different types of wireless networks using a mechanism design [1] and game theoretic approach [2]. Our work can broadly be viewed in two parts. In the first part, we concentrate on ad hoc wireless networks [3] and [4]. In particular, we consider broadcast in these networks where each node is owned by independent and selfish users. Being selfish, these nodes do not forward the broadcast packets. All existing protocols for broadcast assume that nodes forward the transit packets. So, there is need for developing new broadcast protocols to overcome node selfishness. In our paper [5], we develop a strategy proof pricing mechanism which we call immediate predecessor node pricing mechanism (IPNPM) and an efficient new broadcast protocol based on IPNPM. We show the efficacy of our proposed broadcast protocol using simulation results.

A Shapley Value-Based Approach to Discover Influential Nodes in Social Networks

Our study concerns an important current problem, that of diffusion of information in social networks. This problem has received significant attention from the Internet research community in the recent times, driven by many potential applications such as viral marketing and sales promotions. In this paper, we focus on the target set selection problem, which involves discovering a small subset of influential players in a given social network, to perform a certain task of information diffusion. The target set selection problem manifests in two forms: 1) top-k nodes problem and 2) lambda-coverage problem. In the top-k nodes problem, we are required to find a set of k key nodes that would maximize the number of nodes being influenced in the network. The lambda-coverage problem is concerned with finding a set of k key nodes having minimal size that can influence a given percentage lambda of the nodes in the entire network. We propose a new way of solving these problems using the concept of Shapley value which is a well known solution concept in cooperative game theory. Our approach leads to algorithms which we call the ShaPley value-based Influential Nodes (SPINs) algorithms for solving the top-k nodes problem and the lambda-coverage problem. We compare the performance of the proposed SPIN algorithms with well known algorithms in the literature. Through extensive experimentation on four synthetically generated random graphs and six real-world data sets (Celegans, Jazz, NIPS coauthorship data set, Netscience data set, High-Energy Physics data set, and Political Books data set), we show that the proposed SPIN approach is more powerful and computationally efficient. Note to Practitioners-In recent times, social networks have received a high level of attention due to their proven ability in improving the performance of web search, recommendations in collaborative filtering systems, spreading a technology in the market using viral marketing techniques, etc. It is well known that the interpersonal relationships (or ties or links) between individuals cause change or improvement in the social system because the decisions made by individuals are influenced heavily by the behavior of their neighbors. An interesting and key problem in social networks is to discover the most influential nodes in the social network which can influence other nodes in the social network in a strong and deep way. This problem is called the target set selection problem and has two variants: 1) the top-k nodes problem, where we are required to identify a set of k influential nodes that maximize the number of nodes being influenced in the network and 2) the lambda-coverage problem which involves finding a set of influential nodes having minimum size that can influence a given percentage lambda of the nodes in the entire network. There are many existing algorithms in the literature for solving these problems. In this paper, we propose a new algorithm which is based on a novel interpretation of information diffusion in a social network as a cooperative game. Using this analogy, we develop an algorithm based on the Shapley value of the underlying cooperative game. The proposed algorithm outperforms the existing algorithms in terms of generality or computational complexity or both. Our results are validated through extensive experimentation on both synthetically generated and real-world data sets.

A non-cooperative game-theoretic approach to channel assignment in multi-channel multi-radio wireless networks

Channel assignment in multi-channel multi-radio wireless networks poses a significant challenge due to scarcity of number of channels available in the wireless spectrum. Further, additional care has to be taken to consider the interference characteristics of the nodes in the network especially when nodes are in different collision domains. This work views the problem of channel assignment in multi-channel multi-radio networks with multiple collision domains as a non-cooperative game where the objective of the players is to maximize their individual utility by minimizing its interference. Necessary and sufficient conditions are derived for the channel assignment to be a Nash Equilibrium (NE) and efficiency of the NE is analyzed by deriving the lower bound of the price of anarchy of this game. A new fairness measure in multiple collision domain context is proposed and necessary and sufficient conditions for NE outcomes to be fair are derived. The equilibrium conditions are then applied to solve the channel assignment problem by proposing three algorithms, based on perfect/imperfect information, which rely on explicit communication between the players for arriving at an NE. A no-regret learning algorithm known as Freund and Schapire Informed algorithm, which has an additional advantage of low overhead in terms of information exchange, is proposed and its convergence to the stabilizing outcomes is studied. New performance metrics are proposed and extensive simulations are done using Matlab to obtain a thorough understanding of the performance of these algorithms on various topologies with respect to these metrics. It was observed that the algorithms proposed were able to achieve good convergence to NE resulting in efficient channel assignment strategies.

A game theoretical multiple resource interaction approach to resource allocation in an air campaign

In this paper we propose a multiple resource interaction model in a game-theoretical framework to solve resource allocation problems in theater level military campaigns. An air raid campaign using SEAD aircraft and bombers against an enemy target defended by air defense units is considered as the basic platform. Conditions for the existence of saddle point in pure strategies is proved and explicit feedback strategies are obtained for a simplified model with linear attrition function limited by resource availability. An illustrative example demonstrates the key features.