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, Vincent Poor
TL;DR
The paper addresses the curse of boundary nodes in wireless packet-forwarding networks. It uses cooperative-transmission coalitions and studies their fairness; the proposed protocol is reported to improve network connectivity by about 50% over pure repeated-game schemes.
Problem
The paper addresses the curse of boundary nodes in wireless packet-forwarding networks.
Source: §I · pp. 2–3Method
The approach uses cooperative-transmission coalitions and studies their stability and fairness, including min-max, average, and market fairness.
Source: §I · p. 3, §V · p. 22Results
About 50% improved network connectivity is reported compared with the pure repeated game approach.
Source: §V · p. 23Takeaways & Limitations
The coalition approach is intended to let boundary nodes transmit their packets effectively.
Source: §V · p. 22
Abstract
from arXiv · showhide
In wireless packet-forwarding networks with selfish nodes, application 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 {\em 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. Here, the concept of core is used to study the stability of the coalitions in such games. Then three types of fairness are investigated, namely, min-max fairness using nucleolus, average fairness using the Shapley function, and a newly proposed market fairness. Based on the specific problem addressed in this paper, market fairness is a new fairness concept involving fairness between multiple backbone nodes and multiple boundary nodes. Finally, a protocol is designed using both repeated games and coalition games. Simulation results show how boundary nodes and backbone nodes form coalitions according to different fairness criteria. The proposed protocol can improve the network connectivity by about 50%, compared with pure repeated game schemes.
I. INTRODUCTION
Repeated-game incentives can fail for boundary nodes because backbone nodes do not depend on them. The paper proposes cooperative-transmission coalitions, studies their stability and fairness, and reports improved network connectivity.
I. INTRODUCTION
- Boundary nodes lack repeated-game leverage because backbone nodes do not depend on them and therefore need not fear retaliation for refusing to forward their packets.Forwarding also consumes a node’s limited battery energy, which may make forwarding others’ packets contrary to its interest.Source: §I · pp. 2–3
- The proposed coalitions let boundary nodes relay backbone transmissions in exchange for rewards for packet-forwarding.Cooperative transmission lets boundary nodes provide transmission benefits to backbone nodes treated as sources.Source: §I · p. 3
- Coalition stability and payoff division are studied using the core, nucleolus, and Shapley function.The paper distinguishes min-max fairness using the nucleolus, average fairness using the Shapley function, and newly proposed market fairness.Source: §I · p. 3
- Market fairness is introduced for fairness between multiple backbone nodes and multiple boundary nodes.The protocol combines repeated games and coalition games.Source: §I · pp. 3–4
- About 50% higher network connectivity is reported for the proposed protocol than for the pure repeated game approach.The simulations examine coalition formation under different fairness criteria.Source: §I · p. 4
II. REPEATED GAMES AND THE CURSE OF BOUNDARY NODES
This section reviews repeated games for nodes with mutual packet-forwarding dependencies and then focuses on the distinct problem of boundary nodes. It describes how repeated play can sustain cooperation and states the relevant Folk-theorem condition.
II. REPEATED GAMES AND THE CURSE OF BOUNDARY NODES
- A wireless packet-forwarding network is modeled as a directed graph whose nodes can have mutual packet-forwarding dependencies.The graph represents nodes and directed links, and routes to destinations involve potential forwarding nodes.Source: §II · p. 4
A. Repeated Games for Mutually Dependent Nodes
- Repeated games allow strategies to depend on past moves, making retaliation possible when a node defects from packet-forwarding.For sufficiently patient nodes, future punishment can offset the short-term benefit of withholding forwarding.Source: A. Repeated Games for Mutually… · pp. 4–5
- The Folk theorem states that an infinitely repeated game can attain any feasible payoff giving each node at least its Nash-equilibrium payoff, provided β is sufficiently close to 1.The theorem supplies a condition under which repeated play can sustain outcomes that improve on the Nash-equilibrium payoffs.Source: A. Repeated Games for Mutually… · p. 5
- The section assumes prior work has addressed selfish packet-forwarding with mutual dependency, then turns to the problems encountered by boundary nodes.Source: A. Repeated Games for Mutually… · p. 6
B. Curse of Boundary Nodes
The curse of boundary nodes arises when forwarding incentives based on mutual dependency do not extend to nodes at the network edge. Cooperative transmission offers those nodes a way to form coalitions with backbone nodes.
B. Curse of Boundary Nodes
- When a node’s forwarding dependency is not mutual, a backbone node may have no incentive to forward a boundary node’s packets and cannot be punished through future dependence.The section contrasts this with mutually dependent backbone nodes, who face possible retaliation for refusing to forward.Source: B. Curse of Boundary Nodes · p. 6
- A boundary node can form a coalition with a backbone node by helping its transmission, using cooperative transmission to address the incentive problem.The example describes a boundary node helping a backbone node’s transmission, with reduced transmitted power as a possible benefit.Source: B. Curse of Boundary Nodes · p. 6
III. COALITION GAMES WITH COOPERATIVE TRANSMISSION
The section lays out a coalition-game approach built around cooperative transmission. It covers the transmission technique, coalition formulation, fairness definitions, and a protocol combining repeated and coalition games.
III. COALITION GAMES WITH COOPERATIVE TRANSMISSION
- The section first introduces a cooperative-transmission technique that allows nodes to participate in coalitions, then formulates a coalition game using that technique.Source: §III · p. 6
- It proposes three fairness definitions for dividing coalition benefits.Source: §III · p. 6
- It constructs a packet-forwarding protocol that uses both repeated games and coalition games.Source: §III · p. 6
A. Cooperative Transmission System Model
The system model compares direct transmission with two-stage amplify-and-forward cooperation, in which relays help deliver a source node’s information. For a target link quality, cooperation requires less source power than direct transmission, creating a potential mutual benefit for backbone sources and boundary relays.
A. Cooperative Transmission System Model
- In the two-stage amplify-and-forward protocol, the source broadcasts first and the remaining nodes relay amplified signals to the destination in the second stage.The source and relays use orthogonal channels, such as TDMA, FDMA, or orthogonal CDMA.Source: A. Cooperative Transmission System Model · p. 7
- The destination combines the direct-stage signal and relay-stage signals using maximal ratio combining to obtain the output SNR.The model assumes equal noise power across the noises considered.Source: A. Cooperative Transmission System Model · pp. 7–8
- Cooperative transmission requires less source power than direct transmission to achieve the desired link quality.The reduced source power can provide incentives for backbone nodes to use boundary nodes as relays.Source: A. Cooperative Transmission System Model · p. 8
B. Coalition Game Formation for Boundary Nodes
The game models boundary nodes as relays that help backbone nodes reduce transmission power, while backbone nodes forward boundary-node packets in return. Its core conditions characterize when this coalition is stable and how the nodes’ utilities reflect their cooperation.
B. Coalition Game Formation for Boundary Nodes
- Boundary nodes can use cooperative transmission to relay backbone-node information, while backbone nodes return the benefit by forwarding their packets.The model first considers one backbone source and nearby boundary relays; the transmitted power saved by the source is the coalition benefit.Source: B. Coalition Game Formation for… · pp. 8–10
- A coalition is stable when no other coalition can upset its agreement, and the core is the set of stable payoff allocations.An imputation is both group rational and individually rational: it allocates the coalition’s value and gives each node at least its stand-alone benefit.Source: B. Coalition Game Formation for… · p. 9
- Without cooperation, a boundary node’s utility is −∞ because it cannot successfully deliver packets, even at maximal transmit power.With a grand coalition, the source and relay nodes instead share utilities from cooperative transmission.Source: B. Coalition Game Formation for… · pp. 9–10
- The core is nonempty when α_i ≥ 0 and the source’s coalition utility is at least its stand-alone utility; then the grand coalition can be stable.Each α_i is the ratio of packets the backbone node forwards for boundary node i to packets that node relays for the backbone node.Source: B. Coalition Game Formation for… · p. 10
- Core stability determines whether an allocation is stable, but not how utilities should be divided, motivating min-max, average, and market fairness criteria.Different α_i values give relay nodes different utilities.Source: B. Coalition Game Formation for… · p. 10
C. Min-Max Fairness of a Game Coalition using Nucleolus
This section uses the nucleolus to allocate coalition utility under min-max fairness. It derives the maximal α_i for that allocation, assuming relays can transmit at maximum power and the backbone node accepts an arbitrarily small power gain from joining.
C. Min-Max Fairness of a Game Coalition using Nucleolus
- The maximal α_i yielding the nucleolus gives the game’s min-max-fair allocation.The nucleolus minimizes the maximum dissatisfaction and, when the core is nonempty, lies in the core.Source: C. Min-Max Fairness of a Game… · p. 11
- The derivation considers the grand coalition because other coalitions have excess −∞, and it equalizes the nodes’ utilities at the min-max value.The method assumes the backbone node can accept an arbitrarily small power gain to join.Source: C. Min-Max Fairness of a Game… · p. 12
- The maximizing allocation has each relay transmit at the largest possible power, Pmax.The derivation uses that source power increases monotonically with relay transmit power and relay utility increases monotonically with α_i.Source: C. Min-Max Fairness of a Game… · p. 12
D. Average Fairness of Game Coalition using the Shapley Function
This section assigns average fairness using the Shapley function, interpreted as each node’s expected marginal contribution when it joins a coalition in random order. With the backbone node fixed in the coalition, it derives α_i values for boundary nodes under this fairness criterion.
D. Average Fairness of Game Coalition using the Shapley Function
- The Shapley function assigns each node its expected marginal contribution when it joins a coalition whose members arrive in random order.The paper fixes the backbone node in the coalition and randomizes the order in which boundary nodes join.Source: D. Average Fairness of Game Coalition… · p. 13
- The maximal α_i satisfying average fairness is determined using the Shapley allocation together with a nonempty-core condition.The method assumes the backbone node can accept an arbitrarily small power gain to join the coalition.Source: D. Average Fairness of Game Coalition… · pp. 13–14
- Unlike min-max fairness, Shapley-based average fairness gives different nodes different α_i values according to their channel conditions and ability to reduce backbone power.The Shapley value is characterized by axioms including symmetry, dummy-player treatment, and additivity.Source: D. Average Fairness of Game Coalition… · pp. 12, 14
E. Market Fairness of Game Coalition with Multiple Backbone Nodes
With multiple backbone nodes, the coalition game’s core is empty, so the paper introduces market fairness to model competition among backbone nodes and boundary nodes. It defines market fairness as an equilibrium of a two-level game in which nodes select coalition membership and forwarding policies.
E. Market Fairness of Game Coalition with Multiple Backbone Nodes
- With more than one backbone node, the coalition game’s core is surely empty.The paper attributes this to boundary nodes’ ability to choose among backbone-node coalitions.Source: E. Market Fairness of Game Coalition… · p. 15
- Backbone nodes compete for boundary-node coalitions by adjusting forwarding policies, while boundary nodes choose the coalition offering the largest payoff.The competition can lead backbone nodes to reduce their policies to attract boundary nodes and reduce transmitted power.Source: E. Market Fairness of Game Coalition… · pp. 15–16
- Market fairness is defined as the equilibrium of the two-level games governing backbone policies and boundary-node coalition choices.The approach addresses fairness involving multiple backbone nodes and multiple boundary nodes.Source: E. Market Fairness of Game Coalition… · pp. 15–16
- In the two-backbone, one-boundary example, the boundary node joins backbone node 1 when its policy is lower, and otherwise joins backbone node 2.Backbone node 1 has no incentive to raise its policy above the competing offer once it wins the boundary node.Source: E. Market Fairness of Game Coalition… · pp. 16–17
- The market-fairness formulation requires boundary-node and backbone-node rationality and maximizes backbone-node utility by lowering forwarding policies.The stated constraints require boundary nodes to select coalitions and backbone nodes to join only when their power can be reduced.Source: E. Market Fairness of Game Coalition… · p. 17
F. Joint Repeated-Game and Coalition-Game Packet-Forwarding Protocol
The protocol combines repeated-game forwarding incentives for backbone nodes with coalition formation that lets boundary nodes help through cooperative transmission. The approach offers incentives for backbone forwarding but requires boundary nodes to cooperate in an energy-inefficient way, and its direct implementation assumes contracts can be fulfilled faster than channel conditions change.
F. Joint Repeated-Game and Coalition-Game Packet-Forwarding Protocol
- The protocol combines repeated games and coalition games so boundary nodes can earn packet-forwarding rewards by using cooperative transmission to help backbone nodes.Backbone nodes forward packets under the threat of future punishment, while coalition competition prevents boundary nodes from being forced to accept minimal payoffs.Source: F. Joint Repeated-Game and… · pp. 17–18
- The protocol proceeds through route discovery, backbone packet-forwarding enforcement, boundary-node neighbor discovery, coalition formation, cooperative relay transmission, and forwarding of boundary nodes’ packets.Source: F. Joint Repeated-Game and… · p. 18
- Boundary nodes must help backbone nodes in an energy-inefficient way, although the paper presents this as preferable to a situation where their packets cannot be transmitted.The energy cost arises because boundary nodes are farther from the backbone nodes’ destination.Source: F. Joint Repeated-Game and… · pp. 18–19
- The contract-based implementation can proceed without major modification when contract fulfillment is faster than channel change; rapid changes call for stochastic payoff estimates.Source: F. Joint Repeated-Game and… · p. 19
IV. SIMULATION RESULTS
The simulations report that coalition games improve network connectivity by about 50% and illustrate how relay distance, channel quality, coalition size, and competition relate to coalition choices. The reported connectivity boundary is that a node too far from every other node may still fail to connect.
Min-max fairness
- The simulations identify less-crowded coalitions and nearer backbone nodes as preferences, with channel quality affecting the distance preference in the N = 1 case.When the source-destination channel is good, the closer backbone node is preferred; otherwise, the farther one can provide larger αi.Source: §IV · p. 20
Average fairness
- Under Shapley-function average fairness, a boundary node with a better channel and greater contribution to backbone relaying receives greater rewards.When boundary node 2 moves farther away, its α2 increases while α1 decreases, as the backbone node relies more on node 2 for relaying.Source: §IV · p. 20
Market fairness
- Market-fairness simulations show that boundary nodes prefer the closest backbone node, but competition and coalition combinations affect their choices and rewards.Rational boundary nodes select the largest αm offer; the paper reports that market fairness can counteract backbone-node greediness.Source: §IV · p. 21
Network topology
- Nodes in the network middle are less likely to be boundary nodes and have larger α, while the five-destination case makes them less likely to be boundary nodes than the one-destination case.Source: §IV · p. 22
Connectivity
- About 50%: coalition games improve network connectivity, defined as the probability that a randomly located node can connect to other nodes.Without coalition formation, selfish nodes leave boundary nodes unable to transmit their packets.Source: §IV · p. 22
- A node too far from any other node may remain unable to connect, despite the reported connectivity improvement from coalition games.Source: §IV · p. 22
V. CONCLUSIONS
The paper proposes coalition games using cooperative transmission to give selfish boundary nodes incentives to transmit their packets, and studies three fairness concepts. Its simulations show coalition formation under different fairness criteria and an example of about 50% greater connectivity than pure repeated-game schemes.
V. CONCLUSIONS
- The paper uses cooperative transmission and coalition games to provide incentives for selfish boundary nodes to transmit packets and to study stable, fair coalitions.Source: §V · p. 22
- The paper studies min-max, average, and market fairness, with market fairness using competition to counteract backbone-node greediness.Source: §V · p. 22
- Simulations illustrate coalition formation under different fairness criteria and report about 50% greater network connectivity than the pure repeated-game approach.Source: §V · pp. 22–23