PaperlayerView exact revision on arXiv

Source-linked AI summary

Coalitional Game Theory for Communication Networks: A Tutorial

Walid Saad, Zhu Han, Merouane Debbah, Are Hjørungnes, Tamer Basar

arXiv:0905.4057v1cs.ITcs.GT

TL;DR

Communication networks need analytical tools for cooperation amid challenges of modeling, efficiency, complexity, and fairness, while existing coalitional-game literature remains sparse. This tutorial unifies coalitional game theory for communications, classifies games into three categories, and surveys their analysis and applications. It presents coalitional games as an analytical tool for communication and wireless networks and as a tutorial filling a gap in the communications literature.

  • Problem

    Large-scale cooperation in communication networks faces modeling, efficiency, complexity, and fairness challenges, while research applying coalitional games remains limited because the literature is sparse.

  • Method

    The tutorial unifies coalitional game theory for engineering applications, classifies games into canonical, coalition formation, and coalitional graph games, and analyzes their methodologies and applications.

  • Results

    The article provides a comprehensive tutorial on applying coalitional game theory in communication and wireless networks.

  • Takeaways & Limitations

    The classification offers an application-oriented framework for understanding and analyzing coalitional games in communication networks.

Abstract

from arXiv · show

Game theoretical techniques have recently become prevalent in many engineering applications, notably in communications. With the emergence of cooperation as a new communication paradigm, and the need for self-organizing, decentralized, and autonomic networks, it has become imperative to seek suitable game theoretical tools that allow to analyze and study the behavior and interactions of the nodes in future communication networks. In this context, this tutorial introduces the concepts of cooperative game theory, namely coalitional games, and their potential applications in communication and wireless networks. For this purpose, we classify coalitional games into three categories: Canonical coalitional games, coalition formation games, and coalitional graph games. This new classification represents an application-oriented approach for understanding and analyzing coalitional games. For each class of coalitional games, we present the fundamental components, introduce the key properties, mathematical techniques, and solution concepts, and describe the methodologies for applying these games in several applications drawn from the state-of-the-art research in communications. In a nutshell, this article constitutes a unified treatment of coalitional game theory tailored to the demands of communications and network engineers.

I. INTRODUCTION AND MOTIVATION

The tutorial addresses the sparse literature and practical challenges surrounding cooperation in communication networks by organizing coalitional game theory for engineering use. It introduces an application-oriented classification and surveys the concepts, techniques, and applications associated with its classes.

  • Cooperation can improve performance from the physical layer to networking layers, but large-scale implementation raises modeling, efficiency, complexity, and fairness challenges.
  • Communication-network research has largely applied standard coalitional models to limited aspects of cooperation, reflecting sparse literature on coalitional games.
  • The tutorial provides a unified treatment of coalitional game theory oriented toward engineering applications and gathers state-of-the-art work from game theory and communications.
  • It groups coalitional games into three classes: canonical coalitional games, coalition formation games, and coalitional graph games.
  • The classification is application-oriented, while the tutorial develops each class’s components, properties, techniques, solution concepts, and communication applications.
  • Coalitional games model cooperating groups through coalition values, with characteristic-form values depending only on coalition members and transferable utility allowing arbitrary division among them.

III. CLASS I: CANONICAL COALITIONAL GAMES

Canonical coalitional games are characteristic-form games with superadditivity, so forming larger coalitions is not detrimental and analysis centers on the grand coalition. Their main concerns are stability and fair distribution of cooperative gains.

  • Main properties of canonical coalitional games: Canonical games are characteristic-form games, including transferable-utility and non-transferable-utility variants.
  • Main properties of canonical coalitional games: Because cooperation is never detrimental, canonical games favor formation of the grand coalition containing all players.
  • Main properties of canonical coalitional games: Superadditivity requires cooperation among disjoint coalitions to guarantee at least the value obtainable when they act separately.
  • Main properties of canonical coalitional games: Canonical-game analysis studies whether the grand coalition is stable and how its cooperative gains should be distributed fairly.
  • Main properties of canonical coalitional games: The tutorial presents established game-theoretic solution concepts and techniques for solving canonical coalitional games.

B. The Core as a Solution for Canonical Coalitional Games

The core is a solution concept for canonical coalitional games that identifies payoff allocations preventing coalitions from leaving the grand coalition. Its existence can be analyzed through linear programming and game properties such as balancedness and convexity, but it is not guaranteed in general.

  • Definition: Superadditivity gives players an incentive to form the grand coalition, whose stability is the core’s central concern.When a core allocation exists, the grand coalition is stable and optimal for the coalitional game.
  • Definition: The core consists of payoff allocations that give no coalition an incentive to deviate from the grand coalition.For NTU games, no coalition can provide all its members with strictly higher payoffs; TU games use coalition-value inequalities.
  • Definition: For TU games, core allocations are imputations that distribute v(N) while ensuring each player receives at least its standalone value.Group rationality requires the total payoff to equal v(N), and individual rationality requires xi ≥ v({i}).
  • Properties and Existence: The core is not guaranteed to exist; in many games it is empty, so the grand coalition cannot be stabilized by this solution concept.The tutorial therefore surveys alternative solution concepts and categories of games with guaranteed non-empty cores.
  • Properties and Existence: For TU games, determining core non-emptiness is an LP-feasibility problem whose constraint count grows exponentially with the number of players and is NP-complete in general.Graphical methods are intuitive but limited to TU games with up to 3 players.
  • Properties and Existence: The Bondareva-Shapley theorem states that a TU or NTU canonical game has a non-empty core if and only if it is balanced.Convex games provide another class in which structural properties support core analysis; convexity is equivalent to supermodularity.

C. The Shapley Value

The Shapley value is a unique payoff allocation characterized by four axioms and interpreted as expected marginal contribution under random joining order. It provides fairness properties, but may be computationally costly and is not generally guaranteed to lie in the core.

  • Definition and axioms: The Shapley value is the unique payoff mapping satisfying efficiency, symmetry, dummy, and additivity axioms.Efficiency distributes the grand coalition’s value; symmetry equalizes equivalent players; dummy players receive zero; additivity relates values across games.
  • Interpretation: Under a random joining order, each player receives its expected marginal contribution to the grand coalition.The marginal contribution is v(S ∪ {i}) − v(S), weighted by the probability that player i encounters coalition S.
  • Relation to the core: The Shapley value can combine fairness axioms with core stability when an application-specific result places it in the core, but this is not general.For convex games, the Shapley value lies in the core; in general, it is unrelated to the core.
  • Applications: The Shapley value is used for resource and data-rate allocation in communication networks and as the Shapley-Shubik power index in voting games.Its communication-network applications include allocating resources or data rates.
  • Computation and limitations: For games with many players, computing the Shapley value becomes significantly more complex, motivating analytical and sampling techniques.The tutorial mentions multilinear extensions and sampling methods as approaches for reducing computation time.

D. The Nucleolus

The nucleolus selects a unique allocation by lexicographically minimizing coalition dissatisfaction. It combines fairness and stability, although its computation can be complex and its NTU extension is not formalized.

  • Motivation: Excess measures a coalition’s dissatisfaction by comparing its value with the total payoff allocated to its members.The nucleolus seeks an allocation that minimizes these excesses across coalitions.
  • Definition: The nucleolus is the unique imputation that lexicographically minimizes excesses arranged in non-increasing order.The procedure minimizes the largest excess first, then successively minimizes the next largest excesses when needed.
  • Stability properties: If the core is non-empty, the nucleolus lies in the core and also belongs to the game’s kernel.It therefore satisfies the kernel’s equal-maximum-excess property for players in the same coalition.
  • Example: The Talmud’s recommended allocations for the three-wives problem coincide with the nucleolus of the modeled game.The correspondence illustrates the nucleolus’s role in allocating fair payoffs.
  • Assessment: The nucleolus combines fairness criteria with stability, but its computational complexity can be a major drawback in some games.The tutorial also restricts its discussion to TU canonical games because NTU extensions are not yet formalized.

E. Applications of Canonical Coalitional Games

Canonical-game applications model communication resources through coalition values and seek stable, fair allocations for the grand coalition. Gaussian MAC rate allocation shows that envy-free fairness can provide a unique core allocation.

  • Rate allocation in a multiple access channel: In Gaussian MAC rate allocation, a coalition’s characteristic value is its maximum sum-rate under the assumption that complementary users form a jamming coalition.Because the value is a transferable sum-rate, the game is in characteristic form and is a TU game.
  • Rate allocation in a multiple access channel: The Gaussian MAC game is superadditive, so the central problem is allocating the grand coalition’s capacity among users fairly and stably.The same jamming coalition underlies the superadditivity argument.
  • Rate allocation in a multiple access channel: Every imputation on the grand coalition’s capacity boundary lies in the core, establishing that the grand coalition can be stabilized.The core is therefore non-empty, although it contains many rate vectors.
  • Rate allocation in a multiple access channel: The Shapley value is unsuitable for this rate-allocation game because additivity fails and the resulting allocation does not lie in the core.It consequently cannot stabilize the grand coalition in this application.
  • Rate allocation in a multiple access channel: The proposed envy-free fairness criterion yields a unique allocation that lies in the core and is presented as suitable for rate allocation.It retains the first three Shapley axioms and replaces additivity with an envy-free allocation axiom.

2) Canonical games for receivers and transmitters cooperation:

Receiver cooperation games can yield stable core allocations under joint decoding or proportional fairness, while multiuser detection produces an NTU game stable and sum-rate maximizing at high SINR. Transmitter cooperation with jamming generally has an empty core and lacks superadditivity.

  • Receiver cooperation: With receiver cooperation and joint decoding, the game is TU, characteristic-form, and superadditive because receivers’ cooperation channels are noiseless.The resulting network can be viewed as a SIMO MAC channel.
  • Receiver cooperation: The joint-decoding receiver game has a non-empty core containing all imputations on the SIMO-MAC capacity region.The proof selects rate vectors on the SIMO-MAC region and shows that they lie in the core.
  • Receiver cooperation: The Nash bargaining solution, particularly proportional fair rate allocation, lies in the core and provides suitable fair and stable allocations.This addresses the difficulty of selecting one allocation from the large core.
  • Receiver cooperation: With linear multiuser detectors, individual SINRs cannot be shared, so the receiver-cooperation game becomes NTU with SINR vectors as coalition payoffs.At high SINR, the grand coalition is proven stable and sum-rate maximizing using limiting conditions on the SINR expression.
  • Transmitter cooperation: For transmitter cooperation with joint receiver decoding and complementary-user jamming, the game generally has an empty core and is not superadditive.The grand coalition remains the main candidate because it is proven to be the optimal partition from a total-utility perspective.
  • Transmitter cooperation: The transmitter game’s core existence may depend on power and channel gains, but no core-existence results are provided.This limits the available stability guarantees for that model.

3) Other applications for canonical games and future directions:

Canonical coalitional games address cooperation and fairness in communication networks, especially when cooperation is beneficial and the grand coalition is a meaningful candidate. Applications include packet forwarding, connectivity, cooperative transmission, and future cooperative networking problems.

  • Applications: The curse of the boundary nodes leaves peripheral users unable to send packets because backbone nodes do not need their help.A canonical game models cooperation between boundary nodes and a backbone node to address this problem.
  • Applications: Boundary-node cooperation uses relays for packet forwarding while reducing backbone-node power consumption.Boundary nodes act as relays, while the backbone node forwards their packets in return.
  • Applications: The packet-forwarding game has a non-empty core because boundary nodes receive no utility if they leave the grand coalition with the backbone node.This is classified as a T6 technique in the tutorial’s table.
  • Applications: Canonical games have also been used to improve ad hoc-network connectivity and to study the grand coalition across communication applications.The tutorial identifies canonical games as tools for cooperation, fairness, stability, and allocating cooperative gains.
  • Future directions: Canonical games extend beyond link-level analysis to network-level studies and can assess grand-coalition stability when cooperation yields gains.Suggested applications include cooperative transmission capacity, distributed source coding, and cooperative relaying in cognitive radio.
  • Coalition formation games: Coalition formation games differ by incorporating network structure, coalition-formation costs, environmental changes, and partitions that are generally not superadditive.They may be static, with externally imposed structure, or dynamic, with players forming structures through interaction.
  • Coalition formation games: Solving coalition formation games is more difficult and application-specific than solving canonical games with formal solution concepts.This difficulty is especially relevant when costs, environmental variation, or distributed formation are present.
  • Coalition formation games: Dynamic coalition formation studies which coalitions form, their properties, and how structures adapt to changes in players, strengths, or topology.The framework is intended to answer questions about coalition membership, size, and structural characteristics.

B. Impact of a Coalitional Structure on Solution Concepts of Canonical Coalitional Games

An externally imposed coalitional structure changes canonical solution concepts by replacing global efficiency with relative efficiency. The Shapley value retains a restriction property, whereas the core and nucleolus depend on all coalitions and are harder to compute.

  • Shapley value: The B-value modifies the Shapley value by replacing efficiency with relative efficiency while preserving the other Shapley axioms.The B-value is the Shapley value associated with the structured game (N, v, B).
  • Modified solution concepts: With a coalitional structure B, relative efficiency requires each imposed coalition B_k to distribute exactly v(B_k) among its members.This replaces the canonical focus on distributing the grand coalition’s value v(N) among all players.
  • Shapley value: The B-value has a restriction property, so it can be computed by solving each restricted game separately and combining the resulting allocations.The restricted games are (B_k, v|B_k) for every imposed coalition B_k.
  • Core and nucleolus: The core and nucleolus do not satisfy the restriction property because both depend on all coalitions, including those absent from B.Their computation is therefore more complex than computing the Shapley-based B-value.
  • Core and nucleolus: For games with v({i}) = 0 for every player, an equivalent-game reformulation can be used to find the core and nucleolus.The approach redefines the value function before computing these solutions.
  • Computational complexity: Solution computation becomes more complex for NTU, partition-form, or dynamic coalition formation games, especially under distributed implementation.Dynamic games require payoff allocation and coalition-structure formation to be evaluated jointly.
  • Dynamic coalition formation: Merge-and-split rules converge to a final partition, and when a Dc-stable partition exists, it is uniquely reached from any starting partition.Under utilitarian order it maximizes social welfare; under Pareto order it yields a Pareto-optimal payoff distribution.

D. Applications of Coalition Formation Games

Coalition formation applications model cooperation when network structure and formation costs make the grand coalition unattractive. The tutorial illustrates this through distributed virtual MIMO formation in TDMA networks, including adaptive topology and payoff allocation.

  • 1) Transmitter cooperation with cost in a TDMA system:: Virtual MIMO formation lets single-antenna transmitters cooperate as coalition-level MIMO users to improve capacity in an uplink TDMA system.Each coalition transmits during the slots previously assigned to its members, with one coalition scheduled per slot.
  • 1) Transmitter cooperation with cost in a TDMA system:: Information exchange costs power that increases with coalition size and internal distances, so cooperation is not always beneficial.For sufficiently distant users, exchange can consume the total power; adding users can also increase costs enough to reduce utility.
  • 1) Transmitter cooperation with cost in a TDMA system:: The power cost makes the game non-superadditive, so the grand coalition seldom forms except in extremely favorable two-user cases.The grand coalition forms only in cases such as two very close users.
  • 1) Transmitter cooperation with cost in a TDMA system:: A coalition’s value is its cost-adjusted sum-rate under a per-slot power constraint, with some power reserved for information exchange.If exchange power exceeds the per-slot budget, v(S) = 0; otherwise the remaining power supports coalition transmission as single-user MIMO.
  • 1) Transmitter cooperation with cost in a TDMA system:: Users start from a non-cooperative network and autonomously perform pairwise merges or splits when these improve total utility.Users discover nearby partners starting with the closest neighbor and use the utilitarian order for merge decisions.
  • 1) Transmitter cooperation with cost in a TDMA system:: Merge-and-split converges, and when an optimal Dc-stable partition exists, the distributed algorithm converges to it.Its existence depends on random user locations and is not guaranteed.
  • 1) Transmitter cooperation with cost in a TDMA system:: Periodic distributed merge-and-split operations adapt the network topology to mobility and transmitters joining or leaving.Coalitions detect nearby partners, exchange required information, and make local formation decisions without centralized coordination.
  • 1) Transmitter cooperation with cost in a TDMA system:: Fairness rules change the resulting topology: proportional fairness, the Shapley value, and the nucleolus allocate coalition value differently.The Shapley allocation accounts for joining order, while the nucleolus minimizes dissatisfaction within each forming coalition.

2) Coalition formation for spectrum sensing in cognitive radio networks:

Coalition formation in collaborative spectrum sensing balances improved detection with false-alarm costs and constraints. Dynamic, distributed merge-and-split produces adaptive disjoint coalitions and can substantially improve sensing while preserving a target false-alarm level.

  • 2) Coalition formation for spectrum sensing in cognitive radio networks:: Collaborative spectrum sensing combines coalition members’ sensing bits through a coalition head’s decision-fusion rule.The goal is to reduce each secondary user’s probability of missed detection.
  • 2) Coalition formation for spectrum sensing in cognitive radio networks:: Reducing missed detection increases false alarms, creating a tradeoff that shapes the coalition structure.The tradeoff reflects improved protection against interference to the primary user versus spectrum utilization.
  • 2) Coalition formation for spectrum sensing in cognitive radio networks:: The CSS utility decreases with coalition miss and false-alarm probabilities and imposes a maximum false-alarm constraint α.Because payoffs represent probabilities and cannot be transferred arbitrarily, the game is non-transferable utility.
  • 2) Coalition formation for spectrum sensing in cognitive radio networks:: The grand coalition seldom forms because false alarms increase with coalition size and member distances and may violate α.This makes smaller, disjoint coalitions a natural outcome of the sensing problem.
  • 2) Coalition formation for spectrum sensing in cognitive radio networks:: The three-phase algorithm performs local sensing, adaptive merge-and-split formation, and coalition-head reporting for PU detection.The NTU formation phase uses Pareto order and can operate in a distributed manner.
  • 2) Coalition formation for spectrum sensing in cognitive radio networks:: The formation phase converges to a Dc-stable partition with Pareto-optimal payoffs when that partition exists, then periodically adapts to environmental changes.Changes include SU mobility, PU mobility, and deployment of additional SUs.
  • 2) Coalition formation for spectrum sensing in cognitive radio networks:: The coalition-size upper bound depends only on α and the non-cooperative false-alarm value P_f, not user locations or network size.For α = P_f = 0.1, the network remains non-cooperative because any cooperation violates the false-alarm constraint.

3) Future applications of coalition formation games:

Coalition formation games are presented as a framework for distributed, self-organizing communication networks, especially when cooperation involves costs and changing conditions. Partition-form variants are identified as an important direction for future applications.

  • They provide a framework for self-configuring and self-organizing networks that adapt to topology, technology, service-demand, and application changes.The tutorial connects this adaptability with flexibility and functional scalability.
  • Applications span cooperative networks, wireless sensor networks, next-generation IP networks, ad hoc networks, data collection, transmission, and physical-layer security.The cited examples include unmanned aerial vehicles and cooperation among wireless transmitters.
  • Coalition formation games model cooperative wireless-node behavior when network costs are present.They are also suited to distributed algorithms in autonomic networks.
  • Partition-form coalition formation games can represent interference among coalitions more realistically than characteristic-form models.They account for actual interference affecting a coalition and are therefore identified as ripe for future communication-network applications.

V. CLASS III: COALITIONAL GRAPH GAMES

Coalitional graph games incorporate communication graphs into cooperative-game analysis, so connectivity can affect coalition utility, allocations, stability, and efficiency. The class also includes network-formation games that seek to construct stable graphs through distributed strategic interaction.

  • Coalitional graph games differ from canonical and coalition-formation games because the communication structure among players can affect utility and game outcomes.Their value may depend on internal or external network structure, and games may be TU or NTU.
  • Their objectives are to build directed or undirected network graphs with low-complexity distributed algorithms and analyze graph stability and efficiency.Some settings begin with a given graph and focus only on its stability and efficiency.
  • The Myerson value extends Shapley-value allocation to games whose coalition value is derived from a communication graph.Later work makes the value depend on graph structure rather than only on connected components, enriching the framework but increasing solution complexity.
  • Network formation games combine graph-game objectives with non-cooperative strategies in which players form or break links.They seek both graph formation and stability, using myopic or far-sighted approaches; myopic best-response dynamics can converge to a Nash network under certain utility conditions.
  • Nash-network approaches may produce empty or inefficient graphs, motivating pairwise and coalitional stability concepts based on group deviations.A central design tradeoff is achieving stability together with payoff or social-welfare efficiency.

C. Applications of Coalitional Graph Games

Coalitional graph games are applied to distributed uplink-tree formation in IEEE 802.16j networks, where relay stations autonomously select links toward the base station. The resulting adaptive Nash tree improves packet success rate relative to static or relay-free alternatives.

  • 1) Distributed uplink tree formation in IEEE 802.16j: IEEE 802.16j introduces relay stations to improve network capacity and coverage, but the standard does not specify a tree-formation algorithm.A distributed approach is needed because relay stations may be nomadic or mobile.
  • 1) Distributed uplink tree formation in IEEE 802.16j: The model treats relay stations as players forming a directed uplink tree toward the base station, with each relay transmitting received packets upstream.
  • 1) Distributed uplink tree formation in IEEE 802.16j: Relay-station utility increases with effective throughput and packet success rate while accounting for received packets and link-maintenance costs.Each relay has a maximum supported number of links, and additional links require greater rewards.
  • 1) Distributed uplink tree formation in IEEE 802.16j: A sequential myopic best-response algorithm lets relay stations form, replace, or break links, producing a Nash-network tree connecting relays to the base station.Each relay is prioritized before selecting the utility-maximizing strategy in the current network state.
  • 1) Distributed uplink tree formation in IEEE 802.16j: The resulting tree improves overall packet success rate compared with a static star topology or a network without relays.The algorithm also adapts by replacing links after external mobile-station deployment or relay and mobile-station mobility.

2) Other applications and future potential:

Coalitional graph games support routing and broader communication-network applications by analyzing both graph formation and existing-network properties. The tutorial organizes this literature into three game classes and identifies further opportunities across diverse networking problems.

  • 2) Other applications and future potential: Network formation games have been applied to routing, where nodes seek to minimize routing, link-maintenance, and disconnection costs.A myopic dynamic best-response algorithm repeatedly considers whether randomly selected node pairs should form or remove links.
  • 2) Other applications and future potential: A stochastic network-formation approach is reported to converge to a pairwise-stable and efficient tree network, which becomes a star under a stated cost-function condition.Efficiency is measured by Pareto optimality of utilities in the NTU game.
  • 2) Other applications and future potential: The reported algorithm has slow convergence for large networks and is mainly implemented for undirected graphs, although extension to directed graphs is discussed.
  • 2) Other applications and future potential: Coalitional graph games can analyze existing-network stability, traffic flows, and node-level network flows while accounting for graph stability.Directed-graph applications use generalized pairwise stability and non-cooperative game theory.
  • 2) Other applications and future potential: Potential applications extend beyond routing to trust management, cognitive radio, relay selection, intrusion detection, peer-to-peer transfer, multi-hop relaying, and sensor-network forwarding.
  • VI. CONCLUSIONS: The tutorial classifies coalitional games as canonical, coalition formation, or coalitional graph games and explains each class through properties, solution concepts, methodologies, and applications.It presents the treatment as filling a gap in communications literature with a tutorial tailored to communication networks.
Loading 0905.4057v1…