Source-linked AI summary
Coalition Games with Cooperative Transmission: A Cure for the Curse of Boundary Nodes in Selfish Packet-Forwarding Wireless Networks
Zhu Han, H. Vincent Poor
TL;DR
Selfish nodes may avoid forwarding because it costs battery energy, while boundary nodes cannot rely on reciprocal forwarding incentives. The paper uses cooperative-transmission coalitions to exchange relay help for packet forwarding, and reports about 50% better network connectivity than pure repeated-game approaches.
Problem
Forwarding others’ packets consumes battery energy, while boundary nodes lack reciprocal dependence that could induce backbone nodes to forward their traffic.
Source: §I · p. 1, B. Curse of Boundary Nodes · p. 3Method
The paper forms coalitions in which boundary nodes use cooperative transmission to help backbone nodes, then combines coalition and repeated games in a protocol.
Source: §I · p. 2, B. Curse of Boundary Nodes · p. 3Results
Network connectivity improves by about 50% compared with pure repeated-game approaches.
Source: §IV · p. 8, §V · p. 8Takeaways & Limitations
Abstract
from arXiv · showhide
In wireless packet-forwarding networks with selfish nodes, applications of a repeated game can induce the nodes to forward each others' packets, so that the network performance can be improved. However, the nodes on the boundary of such networks cannot benefit from this strategy, as the other nodes do not depend on them. This problem is sometimes known as the curse of the boundary nodes. To overcome this problem, an approach based on coalition games is proposed, in which the boundary nodes can use cooperative transmission to help the backbone nodes in the middle of the network. In return, the backbone nodes are willing to forward the boundary nodes' packets. The stability of the coalitions is studied using the concept of a core. Then two types of fairness, namely, the min-max fairness using nucleolus and the average fairness using the Shapley function are investigated. Finally, a protocol is designed using both repeated games and coalition games. Simulation results show how boundary nodes and backbone nodes form coalitions together according to different fairness criteria. The proposed protocol can improve the network connectivity by about 50%, compared with pure repeated game schemes.
I. INTRODUCTION
Selfish packet forwarding creates a cooperation problem because forwarding consumes battery energy even though refusal can impair network function. The paper addresses boundary nodes’ lack of reciprocal leverage with coalitions based on cooperative transmission.
I. INTRODUCTION
- Forwarding others’ packets consumes limited battery energy, while refusing to forward can impair network functionality and a node’s own performance.Source: §I · p. 1
- Prior packet-forwarding incentives broadly use virtual payments or personal and community enforcement to sustain cooperation.Examples include pricing and credit methods, and watchdog, pathrater, reputation, and repeated-game approaches.Source: §I · p. 1
- The proposed protocol improves network connectivity by about 50% compared with pure repeated-game approaches.Boundary nodes relay for backbone nodes, which in return forward boundary traffic.Source: §I · p. 2
- Cooperative transmission lets boundary nodes relay for backbone nodes, which can reward them by forwarding their packets.The paper studies coalition stability and payoff division using the core, nucleolus, and Shapley function, then combines coalition and repeated games in a protocol.Source: §I · p. 2
II. REPEATED GAMES AND CURSE OF BOUNDARY NODES
- The paper reviews repeated games and boundary-node dependence before turning to coalition games and cooperative transmission.Source: §I · p. 2
A. Repeated Games for Mutually Dependent Nodes
Repeated games let nodes condition cooperation on past behavior, supporting retaliation and reputation. The account assumes mutual-dependency packet forwarding has been addressed and focuses on boundary nodes.
A. Repeated Games for Mutually Dependent Nodes
- Repeated interactions allow strategies to depend on past moves, making reputation and retribution possible.Source: A. Repeated Games for Mutually… · p. 2
- In a T-period repeated game, each period’s moves are known to every node, and total payoff discounts later-period payoffs by β.β represents a node’s patience, or how much past behavior affects current payoff.Source: A. Repeated Games for Mutually… · p. 2
- Sufficiently patient nodes may prefer cooperation because future punishment can offset the short-term gain from refusing to forward packets.Source: A. Repeated Games for Mutually… · p. 2
- The Folk theorem states that, when β is sufficiently close to 1, an infinitely repeated game can sustain feasible average payoffs at least as high as each node’s Nash-equilibrium payoff.Source: A. Repeated Games for Mutually… · p. 2
- The paper assumes prior approaches have solved packet forwarding among mutually dependent nodes and focuses instead on boundary-node problems.The cited approaches include tit-for-tat, cartel maintenance, and self-learning repeated games.Source: A. Repeated Games for Mutually… · p. 2
B. Curse of Boundary Nodes
Boundary nodes lack the reciprocal dependence that makes retaliation effective, so backbone nodes may have no incentive to forward their packets. Cooperative transmission offers a way for boundary nodes to contribute and earn forwarding in return.
B. Curse of Boundary Nodes
- Without mutual dependence, middle nodes can refuse boundary traffic without facing future punishment, leaving boundary nodes especially exposed.The example contrasts mutually dependent node pairs with boundary-to-backbone routes that offer no reciprocal leverage.Source: B. Curse of Boundary Nodes · p. 3
- A boundary node can help a backbone node’s transmission, for example by reducing its transmit power, in exchange for help forwarding its own packets.Source: B. Curse of Boundary Nodes · p. 3
- The paper calls middle nodes like 1 and 2 backbone nodes and outer nodes like 0 and 3 boundary nodes.Source: B. Curse of Boundary Nodes · p. 3
III. COALITION GAMES WITH COOPERATIVE TRANSMISSION
The section develops a cooperative-transmission technique for coalition formation, studies coalition fairness, and constructs a packet-forwarding protocol combining repeated and coalition games.
III. COALITION GAMES WITH COOPERATIVE TRANSMISSION
- A cooperative-transmission technique enables nodes to participate in coalitions.Source: §III · p. 3
- The section formulates a coalition game and investigates fairness through two fairness definitions.Source: §III · p. 3
- The proposed packet-forwarding protocol uses both repeated games and coalition games.Source: §III · p. 3
A. Cooperative Transmission System Model
The model compares direct transmission with a two-stage cooperative scheme in which relay nodes amplify a source’s signal. The combined destination signals reduce the source power needed for the target link quality, creating a potential benefit for backbone sources and boundary relays.
A. Cooperative Transmission System Model
- The direct-transmission source power is bounded by Pmax, and the link must meet the target SNR γ.The model defines hs,d as the source-to-destination channel gain and σ2 as the noise level.Source: A. Cooperative Transmission System Model · p. 3
- In the cooperative scheme, the source transmits first and the remaining N nodes amplify and retransmit its signal in a second stage.The source and relays use orthogonal channels, such as TDMA, FDMA, or orthogonal CDMA.Source: A. Cooperative Transmission System Model · p. 3
- The destination combines the first-stage and N second-stage signals using maximal ratio combining.The source-to-destination and relay contributions determine the output SNR.Source: A. Cooperative Transmission System Model · p. 3
- Cooperative transmission requires less source power than direct transmission to achieve the desired link quality γ.The source and relays transmit in two stages, and the destination combines their received signals using maximal ratio combining.Source: A. Cooperative Transmission System Model · pp. 3–4
B. Coalition Game Formation for Boundary Nodes
The coalition game models boundary nodes as relays for a backbone source and represents packet-forwarding rewards through utility allocation. Its core identifies stable allocations, while the paper separately considers how to divide coalition benefits fairly.
B. Coalition Game Formation for Boundary Nodes
- A coalition is a cooperating subset of nodes, and its characteristic function v assigns a value to cooperation.The core concerns stable payoff allocations; it does not itself specify how the utility is divided.Source: B. Coalition Game Formation for… · p. 4
- A backbone node is modeled as the source and nearby boundary nodes as relays; without cooperation, the source utility is −Pd and relay utilities are −∞.With a grand coalition, relays help transmit the source’s information, and their utilities depend on the allocation parameters αi.Source: B. Coalition Game Formation for… · p. 4
- Each αi is the ratio of packets a backbone node agrees to forward for boundary node i to packets that node relays for it.The relay utility Ui = −Pi/αi uses negative power as utility; αi also represents average power per transmission for boundary nodes.Source: B. Coalition Game Formation for… · p. 4
- The grand coalition is stable when the core is nonempty, which Theorem 2 ties to αi ≥ 0 and the source’s utility meeting its standalone value.The proof states that adding relays monotonically reduces required source power, and condition (12) completes the stability condition.Source: B. Coalition Game Formation for… · p. 4
- The paper treats min-max and average fairness as separate ways to divide utility among relays.Different αi values give relay nodes different utilities.Source: B. Coalition Game Formation for… · p. 4
C. Min-Max Fairness of a Game Coalition using Nucleolus
The nucleolus is used to pursue min-max fairness by minimizing the maximum coalition dissatisfaction. In this model, the maximal αi is tied to source power when all relays transmit at Pmax, under the stated assumption about backbone participation.
C. Min-Max Fairness of a Game Coalition using Nucleolus
- For the fairness analysis, the paper minimizes the maximum dissatisfaction across coalitions, quantified by excess.It considers only the grand coalition’s excess because other coalitions have excess −∞.Source: C. Min-Max Fairness of a Game… · pp. 4–5
- The model omits the transmission power needed for a boundary node’s own packet to reach the backbone node.That power is excluded because it is irrelevant to the coalition.Source: C. Min-Max Fairness of a Game… · p. 4
- The nucleolus minimizes the maximum excess, making it the allocation used for the game’s min-max fairness criterion.The paper states that the nucleolus is unique and, when the core is nonempty, lies in the core and kernel.Source: C. Min-Max Fairness of a Game… · p. 5
- The maximal αi yielding the nucleolus is determined with source power P0(N) when all relays transmit at Pmax.The backbone node is assumed to accept an arbitrarily small power gain to join the coalition.Source: C. Min-Max Fairness of a Game… · p. 5
D. Average Fairness of Game Coalition using the Shapley Function
Average fairness uses the Shapley function to assign coalition value according to nodes’ expected marginal contributions under random joining order. The resulting α_i values differ by node location.
D. Average Fairness of Game Coalition using the Shapley Function
- The Shapley function is uniquely determined by efficiency, symmetry, dummy, and additivity axioms.It assigns a vector of real numbers to each characteristic function.Source: D. Average Fairness of Game Coalition… · p. 5
- Under random joining order, each node’s Shapley value is its expected marginal contribution to coalition worth.The backbone node is always in the coalition, while boundary nodes join randomly.Source: D. Average Fairness of Game Coalition… · p. 5
- The section formulates maximal α_i through average fairness and the condition that the coalition core is non-empty.The fairness condition is based on the Shapley function’s physical interpretation; the analysis assumes the backbone node accepts arbitrarily small power gain to join.Source: D. Average Fairness of Game Coalition… · pp. 5–6
- Average fairness gives different nodes different α_i values according to their locations, unlike min-max fairness.The section’s theorem seeks the maximal α_i satisfying average fairness and a non-empty core, assuming a backbone node accepts arbitrarily small power gain to join.Source: D. Average Fairness of Game Coalition… · pp. 5–6
E. Joint Repeated-Game and Coalition-Game Packet-Forwarding Protocol
The protocol combines repeated-game enforcement among backbone nodes with coalitions between backbone and boundary nodes. Cooperative transmission provides the exchange through which boundary nodes receive packet-forwarding rewards.
E. Joint Repeated-Game and Coalition-Game Packet-Forwarding Protocol
- The protocol has boundary nodes relay packets for backbone nodes, followed by backbone forwarding of boundary nodes’ packets.These are the final two steps after route discovery, enforcement, neighbor discovery, and coalition formation.Source: E. Joint Repeated-Game and… · p. 6
- Backbone nodes forward other nodes’ packets under the threat of future punishment in the repeated game.Route discovery first identifies which nodes depend on one another for transmission.Source: E. Joint Repeated-Game and… · p. 6
- Boundary nodes discover neighboring backbone nodes and form coalitions to earn forwarding of their own packets.Cooperative transmission lets boundary nodes pay credits first; competition among backbone nodes prevents them from being forced to accept minimal payoffs.Source: E. Joint Repeated-Game and… · p. 6
IV. SIMULATION RESULTS
Simulations examine min-max and average fairness across relay locations, then measure coalition games’ effect on connectivity. The coalition game improves network connectivity by about 50%.
IV. SIMULATION RESULTS
- Under min-max fairness, α_i approaches 1/N when relays are close to the source, while backbone-node P0 increases as boundary nodes move farther away.The simulations average α_i over 1,000 iterations; the comparison considers different source-destination channels and node counts.Source: §IV · pp. 6–7, Figure 4 · p. 7
- For multiple backbones under min-max fairness, boundary nodes prefer less crowded coalitions and nearer backbones; with N = 1, channel quality can favor a farther backbone.A good source-destination channel favors the closer backbone; otherwise, the farther one can provide larger α_i.Source: §IV · p. 7
- Under average fairness, the boundary node with the better channel receives greater rewards; as node 2 moves farther away, α_1 falls and α_2 rises.The reported comparison uses two boundary-node locations and shows the α_i curves crossing at node 1’s location.Source: §IV · p. 7, Figure 5 · p. 7
- About 50%: the coalition game improves network connectivity compared with no coalition game, with failures remaining when a node is too far from any other.Connectivity is defined as the probability that a randomly located node can connect to the other nodes.Source: §IV · pp. 7–8, Figure 7 · p. 8
V. CONCLUSIONS
The paper combines cooperative transmission and coalition games with repeated games to support packet forwarding by selfish boundary nodes. Simulations show coalition formation under two fairness criteria and about 50% higher connectivity than pure repeated-game schemes.
V. CONCLUSIONS
- The proposed protocol combines repeated games and coalition games, with stable and fair coalitions based on min-max and average fairness.The approach uses cooperative transmission to benefit selfish nodes and help boundary nodes transmit their packets effectively.Source: §V · p. 8
- Simulations show boundary and backbone nodes forming coalitions according to the fairness criterion.Source: §V · p. 8
- About 50%: network connectivity improves compared with the pure repeated-game approach.Source: §V · p. 8