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.

Modeling the role of competition and cooperation in the evolution of katydid acoustic synchrony

The precise timing of individual signals in response to those of signaling neighbors is seen in many animal species. Synchrony is the most striking of the resultant timing patterns. One of the best examples of acoustic synchrony is in katydid choruses where males produce chirps with a high degree of temporal overlap. Cooperative hypotheses that speculate on the evolutionary origins of acousti synchrony include the preservation of the species-specific call pattern, reduced predation risks, and increased call intensity. An alternative suggestion is that synchrony evolved as an epiphenomenon of competition between males in response to a female preference for chirps that lead other chirps. Previous models investigating the evolutionary origins of synchrony focused only on intrasexual competitive interactions. We investigated both competitive and cooperative hypotheses for the evolution of synchrony in the katydid Mecopoda ``Chirper'' using physiologically and ecologically realistic simulation models incorporating the natural variation in call features, ecology, female preferences, and spacing patterns, specifically aggregation. We found that although a female preference for leading chirps enables synchronous males to have some selective advantage, it is the female preference for the increased intensity of aggregations of synchronous males that enables synchrony to evolve as an evolutionarily stable strategy.

Evolution of cooperation by reciprocation within structured demes

The iterative two-person Prisoners’ Dilemma game has been generalised to theN-person case. The evolution of cooperation is explored by matching the Tit For Tat (TFT) strategy (Axelrod and Hamilton 1981) against the selfish strategy. Extension of TFT toN-person situations yields a graded set of strategies from the softest TFT, which continues cooperation even if only one of the opponents reciprocates it, to the hardest, which would do so only when all the remaining opponents cooperate. The hardest TFT can go to fixation against the selfish strategy provided it crosses a threshold frequencypc. All the other TFT are invadable by the selfish (D) or the pure defector strategy, while none can invadeD. Yet, provided a thresholdpc is crossed, they can coexist stably withD. AsN, the size of the group increases, the threshold pc also increases, indicating that the evolution of cooperation is more difficult for larger groups. Under certain conditions, only the soft TFT can coexist stably against the selfish strategyD, while the harder ones cannot. An interesting possibility of a complete takeover of the selfish population by successive invasions by harder and harder TFT strategies is also presented.

Cooperation of Notch and Ras/MAPK signaling pathways in human breast carcinogenesis

Background: Recent studies have implicated aberrant Notch signaling in breast cancers. Yet, relatively little is known about the pattern of expression of various components of the Notch pathway, or its mechanism of action. To better understand the role of the Notch pathway in breast cancer, we have undertaken a detailed expression analysis of various Notch receptors, their ligands, and downstream targets at different stages of breast cancer progression. Results: We report here that there is a general increase in the expression levels of Notch 1, 2, 4, Jagged1, Jagged2, and Delta-like 4 proteins in breast cancers, with simultaneous upregulation of multiple Notch receptors and ligands in a given cancer tissue. While Notch3 and Delta-like1 were undetectable in normal tissues, moderate to high expression was detected in several cancers. We detected the presence of active, cleaved Notch1, along with downstream targets of the Notch pathway, Hes1/Hes5, in similar to 75% of breast cancers, clearly indicating that in a large proportion of breast cancers Notch signaling is aberrantly activated. Furthermore, we detected cleaved Notch1 and Hes1/5 in early precursors of breast cancers - hyperplasia and ductal carcinoma in situ suggesting that aberrant Notch activation may be an early event in breast cancer progression. Mechanistically, while constitutively active Notch1 alone failed to transform immortalized breast cells, it synergized with the Ras/MAPK pathway to mediate transformation. This cooperation is reflected in vivo, as a subset of cleaved Notch positive tumors additionally expressed phopsho-Erk1/2 in the nuclei. Such cases exhibited high node positivity, suggesting that Notch-Ras cooperation may lead to poor prognosis. Conclusions: High level expression of Notch receptors and ligands, and its increased activation in several breast cancers and early precursors, places Notch signaling as a key player in breast cancer pathogenesis. Its cooperation with the Ras/MAPK pathway in transformation offers combined inhibition of the two pathways as a new modality for breast cancer treatment.

A Shapley value analysis to coordinate the formation of procurement

In this paper we address the problem of forming procurement networks for items with value adding stages that are linearly arranged. Formation of such procurement networks involves a bottom-up assembly of complex production, assembly, and exchange relationships through supplier selection and contracting decisions. Recent research in supply chain management has emphasized that such decisions need to take into account the fact that suppliers and buyers are intelligent and rational agents who act strategically. In this paper, we view the problem of Procurement Network Formation (PNF) for multiple units of a single item as a cooperative game where agents cooperate to form a surplus maximizing procurement network and then share the surplus in a fair manner. We study the implications of using the Shapley value as a solution concept for forming such procurement networks. We also present a protocol, based on the extensive form game realization of the Shapley value, for forming these networks.

A combinatorial procurement auction for QoS-aware web services

Business processes and application functionality are becoming available as internal web services inside enterprise boundaries as well as becoming available as commercial web services from enterprise solution vendors and web services marketplaces. Typically there are multiple web service providers offering services capable of fulfilling a particular functionality, although with different Quality of Service (QoS). Dynamic creation of business processes requires composing an appropriate set of web services that best suit the current need. This paper presents a novel combinatorial auction approach to QoS aware dynamic web services composition. Such an approach would enable not only stand-alone web services but also composite web services to be a part of a business process. The combinatorial auction leads to an integer programming formulation for the web services composition problem. An important feature of the model is the incorporation of service level agreements. We describe a software tool QWESC for QoS-aware web services composition based on the proposed approach.

Correlation, Coding, and Cooperation in Wireless Sensor Networks

We consider a single-hop data-gathering sensor network, consisting of a set of sensor nodes that transmit data periodically to a base-station. We are interested in maximizing the lifetime of this network. With our definition of network lifetime and the assumption that the radio transmission energy consumption forms the most significant portion of the total energy consumption at a sensor node, we attempt to enhance the network lifetime by reducing the transmission energy budget of sensor nodes by exploiting three system-level opportunities. We pose the problem of maximizing lifetime as a max-min optimization problem subject to the constraint of successful data collection and limited energy supply at each node. This turns out to be an extremely difficult optimization to solve. To reduce the complexity of this problem, we allow the sensor nodes and the base-station to interactively communicate with each other and employ instantaneous decoding at the base-station. The chief contribution of the paper is to show that the computational complexity of our problem is determined by the complex interplay of various system-level opportunities and challenges.

Optimal auctions for multi-unit procurement with volume discount bids

Our attention, is focused on designing an optimal procurement mechanism which a buyer can use for procuring multiple units of a homogeneous item based on bids submitted by autonomous, rational, and intelligent suppliers. We design elegant optimal procurement mechanisms for two different situations. In the first situation, each supplier specifies the maximum quantity that can be supplied together with a per unit price. For this situation, we design an optimal mechanism S-OPT (Optimal with Simple bids). In the more generalized case, each supplier specifies discounts based on the volume of supply. In this case, we design an optimal mechanism VD-OPT (Optimal with Volume Discount, bids). The VD-OPT mechanism uses the S-OPT mechanism as a building block. The proposed mechanisms minimize the cost to the buyer, satisfying at the same time, (a) Bayesian, incentive compatibility and (b) interim individual rationality.

The core and shapley value analysis for cooperative formation of procurement networks

Formation of high value procurement networks involves a bottom-up assembly of complex production, assembly, and exchange relationships through supplier selection and contracting decisions, where suppliers are intelligent and rational agents who act strategically. In this paper we address the problem of forming procurement networks for items with value adding stages that are linearly arranged We model the problem of Procurement Network Formation (PNF) for multiple units of a single item as a cooperative game where agents cooperate to form a surplus maximizing procurement network and then share the surplus in a stable and fair manner We first investigate the stability of such networks by examining the conditions under which the core of the game is non-empty. We then present a protocol, based on the extensive form game realization of the core, for forming such networks so that the resulting network is stable. We also mention a key result when the Shapley value is applied as a solution concept.

An analytical approach to the study of cooperation in wireless ad hoc networks

In wireless ad hoc networks, nodes communicate with far off destinations using intermediate nodes as relays. Since wireless nodes are energy constrained, it may not be in the best interest of a node to always accept relay requests. On the other hand, if all nodes decide not to expend energy in relaying, then network throughput will drop dramatically. Both these extreme scenarios (complete cooperation and complete noncooperation) are inimical to the interests of a user. In this paper, we address the issue of user cooperation in ad hoc networks. We assume that nodes are rational, i.e., their actions are strictly determined by self interest, and that each node is associated with a minimum lifetime constraint. Given these lifetime constraints and the assumption of rational behavior, we are able to determine the optimal share of service that each node should receive. We define this to be the rational Pareto optimal operating point. We then propose a distributed and scalable acceptance algorithm called Generous TIT-FOR-TAT (GTFT). The acceptance algorithm is used by the nodes to decide whether to accept or reject a relay request. We show that GTFT results in a Nash equilibrium and prove that the system converges to the rational and optimal operating point.

Implications of the half-duplex constraint on relay-aided cooperation using rateless codes

The half-duplex constraint, which mandates that a cooperative relay cannot transmit and receive simultaneously, considerably simplifies the demands made on the hardware and signal processing capabilities of a relay. However, the very inability of a relay to transmit and receive simultaneously leads to a potential under-utilization of time and bandwidth resources available to the system. We analyze the impact of the half-duplex constraint on the throughput of a cooperative relay system that uses rateless codes to harness spatial diversity and efficiently transmit information from a source to a destination. We derive closed-form expressions for the throughput of the system, and show that as the number of relays increases, the throughput approaches that of a system that uses more sophisticated full-duplex nodes. Thus, half-duplex nodes are well suited for cooperation using rateless codes despite the simplicity of both the cooperation protocol and the relays.

Autonomous and non-autonomous traits mediate social cooperation in Dictyostelium discoideum

In the trishanku (triA(-)) mutant of the social amoeba Dictyostelium discoideum, aggregates are smaller than usual and the spore mass is located mid-way up the stalk, not at the apex. We have monitored aggregate territory size, spore allocation and fruiting body morphology in chimaeric groups of (quasi-wild-type) Ax2 and triA(-) cells. Developmental canalisation breaks down in chimaeras and leads to an increase in phenotypic variation. A minority of triA(-) cells causes largely Ax2 aggregation streams to break up; the effect is not due to the counting factor. Most chimaeric fruiting bodies resemble those of Ax2 or triA(-). Others are double-deckers with a single stalk and two spore masses, one each at the terminus and midway along the stalk. The relative number of spores belonging to the two genotypes depends both on the mixing ratio and on the fruiting body morphology. In double-deckers formed from 1:1 chimaeras, the upper spore mass has more Ax2 spores, and the lower spore mass more triA(-) spores, than expected. Thus, the traits under study depend partly on the cells' own genotype and partly on the phenotypes, and so genotypes, of other cells: they are both autonomous and non-autonomous. These findings strengthen the parallels between multicellular development and behaviour in social groups. Besides that, they reinforce the point that a trait can be associated with a genotype only in a specified context.

Asymmetric Cooperation Among Relays with Linear Precoding

Fixed and mobile relays are used, among other applications, in the downlink of cellular communications systems. Cooperation between relays can greatly increase their benefits in terms of extended coverage, increased reliability, and improved spectral efficiency. In this paper, we introduce the fundamental notion of asymmetric cooperation. For this, we consider a two-phase transmission protocol where, in the first phase, the base station (BS) sends several available messages to the relays over wireless links. But, depending on the channel state and the duration of the BS transmission, not all relays decode all messages. In a second phase, the relays, which may now have asymmetric message knowledge, use cooperative linear precoding for the transmission to the mobile stations. We show that for many channel configurations, asymmetric cooperation, although (slighlty) sub-optimum for the second phase, is optimum from a total-throughput point of view, as it requires less time and energy in the first phase. We give analytical formulations for the optimum operating parameters and the achievable throughput, and show that under typical circumstances, 20-30% throughput enhancement can be achieved over conventional systems.

Energy-Efficient Decentralized Routing with Localized Cooperation Suitable for Fast Fading

Wireless networks transmit information from a source to a destination via multiple hops in order to save energy and, thus, increase the lifetime of battery-operated nodes. The energy savings can be especially significant in cooperative transmission schemes, where several nodes cooperate during one hop to forward the information to the next node along a route to the destination. Finding the best multi-hop transmission policy in such a network which determines nodes that are involved in each hop, is a very important problem, but also a very difficult one especially when the physical wireless channel behavior is to be accounted for and exploited. We model the above optimization problem for randomly fading channels as a decentralized control problem – the channel observations available at each node define the information structure, while the control policy is defined by the power and phase of the signal transmitted by each node.In particular, we consider the problem of computing an energy-optimal cooperative transmission scheme in a wireless network for two different channel fading models: (i) slow fading channels, where the channel gains of the links remain the same for a large number of transmissions, and (ii) fast fading channels,where the channel gains of the links change quickly from one transmission to another. For slow fading, we consider a factored class of policies (corresponding to local cooperation between nodes), and show that the computation of an optimal policy in this class is equivalent to a shortest path computation on an induced graph, whose edge costs can be computed in a decentralized manner using only locally available channel state information(CSI). For fast fading, both CSI acquisition and data transmission consume energy. Hence, we need to jointly optimize over both these; we cast this optimization problem as a large stochastic optimization problem. We then jointly optimize over a set of CSI functions of the local channel states, and a corresponding factored class of control policies corresponding to local cooperation between nodes with a local outage constraint. The resulting optimal scheme in this class can again be computed efficiently in a decentralized manner. We demonstrate significant energy savings for both slow and fast fading channels through numerical simulations of randomly distributed networks.