PaperlayerView exact revision on arXiv

Source-linked AI summary

Competitive Design of Multiuser MIMO Systems based on Game Theory: A Unified View

Gesualdo Scutari, Daniel P. Palomar, Sergio Barbarossa

arXiv:0806.1565v1cs.ITcs.GTmath.OC

TL;DR

The paper addresses distributed mutual-information maximization in Gaussian interference channels, especially the difficult MIMO extension. It unifies prior waterfilling analyses through projection interpretations and derives sufficient conditions for equilibrium uniqueness and asynchronous algorithm convergence.

  • Problem

    Existing MIMO game studies were limited, and practical quantified conditions for equilibrium uniqueness and distributed-algorithm convergence were lacking.

  • Method

    The paper unifies SISO analyses and studies MIMO waterfilling by interpreting waterfilling operators as projections and using fixed-point and contraction theory.

  • Results

    The framework provides sufficient conditions guaranteeing Nash-equilibrium uniqueness and convergence of totally asynchronous waterfilling-based distributed algorithms.

  • Takeaways & Limitations

    The projector interpretation supplies a common mathematical framework for analyzing SISO and MIMO waterfilling games and their asynchronous algorithms.

Abstract

from arXiv · show

This paper considers the noncooperative maximization of mutual information in the Gaussian interference channel in a fully distributed fashion via game theory. This problem has been studied in a number of papers during the past decade for the case of frequency-selective channels. A variety of conditions guaranteeing the uniqueness of the Nash Equilibrium (NE) and convergence of many different distributed algorithms have been derived. In this paper we provide a unified view of the state-of-the-art results, showing that most of the techniques proposed in the literature to study the game, even though apparently different, can be unified using our recent interpretation of the waterfilling operator as a projection onto a proper polyhedral set. Based on this interpretation, we then provide a mathematical framework, useful to derive a unified set of sufficient conditions guaranteeing the uniqueness of the NE and the global convergence of waterfilling based asynchronous distributed algorithms. The proposed mathematical framework is also instrumental to study the extension of the game to the more general MIMO case, for which only few results are available in the current literature. The resulting algorithm is, similarly to the frequency-selective case, an iterative asynchronous MIMO waterfilling algorithm. The proof of convergence hinges again on the interpretation of the MIMO waterfilling as a matrix projection, which is the natural generalization of our results obtained for the waterfilling mapping in the frequency-selective case.

I. INTRODUCTION

The paper studies fully distributed, game-theoretic mutual-information maximization in interference channels and unifies prior waterfilling analyses. It extends this framework to MIMO channels, where changing transmit directions make existing SISO techniques insufficient.

  • Motivation: Interference channels model practical systems in which multiple uncoordinated links share a communication medium.Examples include digital subscriber lines, cellular radio, ad-hoc wireless networks, and cognitive radio systems.
  • Motivation: Treating multiuser interference as additive colored noise limits signaling and reduces design to selecting each transmitter’s optimal covariance matrix.The system assumes independent units without multiuser encoding, decoding, or interference cancellation.
  • Prior formulation: The paper formulates mutual-information maximization as a strategic noncooperative game in which each SISO link selects power allocations across frequency bins to maximize its own rate.This problem had been studied extensively for SISO frequency-selective channels before the paper’s unified treatment.
  • Unified framework: Earlier analyses used projection, variational-inequality, and piecewise-affine interpretations of waterfilling, which the paper shows fit within a unified projector-based view.The framework supports sufficient conditions for Nash-equilibrium uniqueness and convergence of totally asynchronous waterfilling algorithms.
  • MIMO extension: MIMO is a nontrivial extension because users’ optimal transmit directions change with other users’ strategies, unlike fixed directions in SISO frequency-selective channels.Existing SISO techniques therefore cannot be directly or trivially extended; the paper uses a matrix-projection interpretation of MIMO waterfilling.
  • System model: The model represents Q transmitter-receiver pairs with MIMO channels, covariance-matrix strategies, fixed channels, and perfect channel-state information at each link’s transmitter and receiver.Each receiver treats interference from other links as noise, and each transmitter is constrained by an average power budget.

B. Game Theoretical Formulation

The game assigns each link a covariance matrix as its strategy and its information rate as payoff under a power constraint. The paper connects Nash equilibria to waterfilling fixed points and develops a projector-based route to uniqueness and asynchronous convergence conditions.

  • Game definition: Each player chooses its transmit covariance matrix to maximize its own information rate given the other users’ covariance matrices.The admissible strategy is constrained by the user’s transmit-power budget.
  • Game definition: A Nash equilibrium is a strategy profile in which no user can increase its rate by unilaterally changing its own covariance matrix.The players are the communication links, and their payoffs are the corresponding information rates.
  • Best response: For fixed strategies of the other users, each player’s best response is the MIMO waterfilling solution, expressed through an eigendecomposition of an equivalent channel matrix.The water level is selected to satisfy the user’s total-power constraint.
  • Equilibrium characterization: The paper characterizes Nash equilibria as fixed points of the waterfilling mapping.This provides a compact representation of the equilibrium conditions.
  • Analytical challenge: MIMO analysis is difficult because optimal eigenvector matrices depend implicitly on other users’ strategies, unlike the user-independent directions in scalar frequency-selective games.Prior MIMO work established existence in broad settings or under nearly negligible interference but did not provide a practical quantified uniqueness condition with algorithmic convergence guarantees.
  • Analytical framework: Reinterpreting MIMO waterfilling as a projector yields a more tractable fixed-point mapping and sufficient conditions for unique equilibria and convergence of asynchronous distributed algorithms.The analysis also emphasizes that convergence of algorithms using a mapping can depend on the chosen norm.

III. NASH EQUILIBRIUM AS A FIXED POINT

The paper treats Nash equilibria as fixed points of waterfilling mappings and develops fixed-point and contraction tools for analyzing existence and uniqueness. It emphasizes that norm choice affects contraction and algorithmic convergence.

  • Any Nash equilibrium can be interpreted as a fixed point of the waterfilling mapping.
  • A continuous mapping on a nonempty, convex, compact set has at least one fixed point.
  • A contraction on a closed set has a unique fixed point.
  • The existence and uniqueness conditions are sufficient, rather than necessary.
  • Contraction is norm-dependent, so selecting a proper norm is central to characterizing convergence.

B. Convergence to a Fixed-point

The paper frames distributed fixed-point algorithms through component-update schemes, including simultaneous, sequential, and totally asynchronous updates. Block contractions provide unified convergence guarantees across these schemes.

  • Distributed fixed-point methods differ by whether components update simultaneously, sequentially, or totally asynchronously.Totally asynchronous updates may use outdated information and need not update components equally often.
  • A block-maximum norm measures the mapping relative to a partition of the state vector into components.
  • The framework assumes the domain is a Cartesian product of lower-dimensional component sets.This matches the joint admissible strategy set used for the game.
  • A block-contraction with modulus α<1 guarantees asymptotic convergence of the totally asynchronous algorithm to the unique fixed point.The guarantee holds for every initial condition and updating schedule in the stated domain.
  • Variational inequality theory offers a transformation-based route for studying convergence while preserving the fixed-point set.

IV. CONTRACTION PROPERTIES OF THE MULTIUSER WATERFILLING MAPPING

The paper applies its fixed-point framework to multiuser waterfilling by seeking contraction conditions in a suitable block-maximum norm. The MIMO analysis relies on viewing waterfilling as a matrix projection.

  • The paper derives contraction conditions for the multiuser waterfilling mapping in a proper block-maximum norm.
  • The MIMO result interprets the waterfilling operator as a matrix projection onto the convex feasible-strategy set.This projection-based result supports analysis of Nash-equilibrium uniqueness and asynchronous-algorithm convergence.

A. Frequency-Selective Gaussian Interference Channels

For frequency-selective Gaussian interference channels, the paper unifies projection, variational-inequality, and piecewise-affine analyses of waterfilling. Contraction conditions then yield uniqueness of the Nash equilibrium and convergence of distributed algorithms.

  • Frequency-selective channels become parallel scalar channels, reducing the game to users’ power allocations across carriers.Toeplitz-circulant channel matrices admit an eigendecomposition using the normalized IFFT matrix.
  • The optimal strategy at a Nash equilibrium satisfies a simultaneous multiuser waterfilling fixed-point equation.Each user’s waterfilling operator uses the other users’ strategies and a waterlevel satisfying the power constraint.
  • Approach #1: Multiuser waterfilling as a projector: The waterfilling operator can be written as a Euclidean projection, making Nash equilibria fixed points of a related mapping.This projection interpretation is the basis for contraction analysis.
  • Approach #1: Multiuser waterfilling as a projector: The waterfilling mapping is Lipschitz continuous under a weighted block norm, enabling sufficient conditions for equilibrium uniqueness and asynchronous convergence.
  • Approach #2: Multiuser waterfilling as solution of an Affine VI: The game can also be reformulated as an affine variational inequality, whose sufficient conditions establish uniqueness and synchronous sequential IWFA convergence.
  • Approach #2: Multiuser waterfilling as solution of an Affine VI: The affine-VI, fixed-point, and projection formulations are equivalent, so their convergence conditions coincide for an appropriate weight vector.
  • Approach #3: Multiuser waterfilling as a piecewise affine function: A piecewise-affine representation of waterfilling yields contraction conditions that also guarantee global convergence of totally asynchronous algorithms.
  • The generalized condition α<1 guarantees global convergence of synchronous sequential and simultaneous IWFAs to the unique Nash equilibrium.The framework extends these results to asynchronous IWFA and aligns the conditions with the broader contraction criterion.

B. MIMO Gaussian Interference Channels

The MIMO extension is nontrivial because each user's optimal transmit directions change with the other users' strategies. The paper focuses on square, nonsingular direct channel matrices, while the general case is outside its scope.

  • B. MIMO Gaussian Interference Channels: The analysis concentrates on MIMO systems with square, nonsingular direct channel matrices.The more general case is described as substantially more involved and beyond the paper's scope.

1) Multiuser waterfilling in Gaussian MIMO interference channels :

The paper reformulates MIMO waterfilling as a matrix projection onto a convex set, enabling an equivalent fixed-point characterization of Nash equilibria. This projection interpretation follows from convex optimality conditions and supports a nonexpansive operator property.

  • 1) Multiuser waterfilling in Gaussian MIMO interference channels :: The projection formulation is established by showing equivalence between the waterfilling conditions and the KKT conditions of a convex problem.The corresponding optimization problem has a unique solution because its objective is strictly concave or strictly convex on the positive semidefinite cone.
  • 1) Multiuser waterfilling in Gaussian MIMO interference channels :: The projection formulation is stated for nonsingular square channels, while a more general singular or rectangular-channel expression is referenced separately.The broader expression is attributed to prior work rather than developed here.
  • 1) Multiuser waterfilling in Gaussian MIMO interference channels :: MIMO waterfilling is equivalently represented as a matrix projection onto the convex feasible set Qq under the Frobenius norm.The projection solves the associated convex optimization problem with the user's transmit-power constraint.
  • 1) Multiuser waterfilling in Gaussian MIMO interference channels :: All Nash equilibria can be obtained as fixed points of the mapping defined by the matrix-projection representation.This replaces the original waterfilling expression with a more tractable fixed-point formulation.
  • 1) Multiuser waterfilling in Gaussian MIMO interference channels :: The MIMO waterfilling projector is nonexpansive with respect to the Frobenius norm.This property is used to derive contraction properties for the multiuser waterfilling mapping.

2) Contraction property of MIMO multiuser waterfilling:

The paper defines a weighted block-maximum norm and a nonnegative interference matrix to analyze the MIMO waterfilling mapping. Under a spectral condition, the mapping becomes a block-contraction, supporting asynchronous convergence results.

  • 2) Contraction property of MIMO multiuser waterfilling:: The analysis uses a weighted block-maximum norm built from Frobenius norms and a positive weight vector.The weights provide degrees of freedom for characterizing contraction and algorithmic convergence.
  • 2) Contraction property of MIMO multiuser waterfilling:: Theorem 5 establishes Lipschitz continuity of the MIMO waterfilling mapping on the joint feasible set Q.The mapping and its contraction modulus are expressed using the matrix S and the selected weighted norm.
  • 2) Contraction property of MIMO multiuser waterfilling:: If ∥S∥w∞,mat < 1, the waterfilling mapping is a block-contraction with modulus α = ∥S∥w∞,mat.The proof combines the projection's nonexpansiveness with channel nonsingularity and norm inequalities.
  • 2) Contraction property of MIMO multiuser waterfilling:: The contraction proof bounds differences between waterfilling outputs by a vector inequality involving the nonnegative interference matrix S.This yields the block-contraction condition in the weighted norm.

V. EXISTENCE AND UNIQUENESS OF THE NE

The game always has a Nash equilibrium, and the paper gives sufficient conditions for uniqueness based on contraction of the waterfilling mapping. These conditions quantify interference limits and extend earlier special-case results.

  • V. EXISTENCE AND UNIQUENESS OF THE NE: Theorem 6 states that game G always admits a Nash equilibrium for any channel matrices and user transmit powers.Existence follows from continuity of the waterfilling projector and compactness and convexity of the joint strategy set.
  • V. EXISTENCE AND UNIQUENESS OF THE NE: The Nash equilibrium is unique when the waterfilling mapping satisfies the theorem's contraction condition for some positive weight vector.The argument applies the block-contraction result to the fixed-point characterization of equilibria.
  • V. EXISTENCE AND UNIQUENESS OF THE NE: The sufficient uniqueness conditions quantify how much interference receivers and transmitters can tolerate.Conditions C2 and C3 bound interference levels from receiver and transmitter perspectives.
  • V. EXISTENCE AND UNIQUENESS OF THE NE: The conditions apply to arbitrary MIMO interference systems and recover many SISO frequency-selective and OFDM conditions as special cases.Their generality comes from not requiring a particular channel-matrix structure, subject to the stated channel assumptions.
  • V. EXISTENCE AND UNIQUENESS OF THE NE: Unlike an earlier result based on an unspecified interference threshold, these conditions explicitly quantify the interference strength sufficient for uniqueness.The paper presents this quantification as making the conditions practically checkable.

VI. MIMO ASYNCHRONOUS ITERATIVE WATERFILLING ALGORITHM

The asynchronous MIMO IWFA lets users update covariance strategies using possibly delayed interference information, under standard total-asynchrony assumptions. Under condition (C1), it converges globally to the unique Nash equilibrium for any feasible initialization and updating schedule.

  • Algorithm definition: Each updating user selects its optimal covariance matrix by waterfilling over the currently perceived interference-plus-noise covariance.The perceived interference from each other user may come from its most recent available iteration.
  • Asynchrony assumptions: Totally asynchronous operation requires causal information, eventual purging of sufficiently old values, and infinitely many updates by every user.These requirements are expressed as assumptions A1–A3.
  • Algorithm definition: The asynchronous IWFA is formally specified as Algorithm 1, initialized from any feasible covariance matrix and iterated until the iteration limit.The algorithm is based on the MIMO waterfilling mapping.
  • Convergence guarantee: Under condition (C1), asynchronous IWFA converges to the unique NE for any feasible initial conditions and updating schedule as Nit →∞.The result follows from Theorems 2 and 5 and applies to the algorithm described in Algorithm 1.
  • Convergence guarantee: Sequential and simultaneous MIMO IWFA are special cases of the asynchronous scheme and share the same convergence conditions when A1–A3 hold.The conditions do not depend on the user scheduling or delay parameters.
  • Distributed implementation: The MIMO asynchronous IWFA is distributed because each user only needs to measure overall interference-plus-noise covariance and waterfill over it.The framework generalizes the asynchronous IWFA for SISO frequency-selective parallel interference channels.

VII. NUMERICAL RESULTS

The numerical section evaluates MIMO gains and compares sequential with simultaneous IWFA convergence. More antennas improve sum-rate, while simultaneous IWFA converges faster than sequential IWFA in the studied network.

  • MIMO versus SISO: Increasing transmit and receive antenna counts improves sum-rate in the simulated two-user frequency-selective MIMO interference system.The curves average 500 independent channel realizations.
  • MIMO versus SISO: MIMO incremental gains are almost independent of interference level, with high-interference gains nearly coinciding with corresponding low-interference gains.Figure 1 varies interpair distance and antenna counts.
  • Sequential versus simultaneous IWFA: Sequential IWFA is slower than simultaneous IWFA, especially when the number of active links Q is large.Sequential updates force each user to wait for users scheduled earlier before changing its power allocation.
  • Sequential versus simultaneous IWFA: The sequential-versus-simultaneous convergence-speed pattern persists across changed channel realizations and antenna counts.Figure 2 plots rates for three of the eight links in the cellular-network example.

VIII. CONCLUSIONS

The paper unifies prior distributed mutual-information maximization results through a projection interpretation of waterfilling. It extends the framework to MIMO games and asynchronous algorithms.

  • Unified framework: Prior approaches to noncooperative mutual-information maximization can be unified by interpreting waterfilling as projection onto a proper polyhedral set.The paper applies this interpretation to results developed over the preceding seven years.
  • MIMO extension: The framework extends the analysis to MIMO games and supports asynchronous distributed waterfilling algorithms.The conclusion presents this as an extension of the frequency-selective setting.
Loading 0806.1565v1…