PaperlayerView exact revision on arXiv

Source-linked AI summary

Real and Complex Monotone Communication Games

Gesualdo Scutari, Francisco Facchinei, Jong-Shi Pang, Daniel P. Palomar

arXiv:1212.6235v2cs.GTcs.IT

TL;DR

The paper addresses distributed solution of general real or complex player-convex NEPs without restrictive problem structure, including games with multiple equilibria. It develops VI-based asynchronous best-response methods and applies them to generalized SISO/MIMO cognitive-radio games, reporting improved performance over plain noncooperative schemes.

  • Problem

    Existing best-response methods are limited by restrictive structure, unique equilibria, and inadequate tools for complex player-convex NEPs.

  • Method

    The paper develops a VI-based framework and distributed asynchronous best-response algorithms for real and complex player-convex NEPs, including equilibrium-selection procedures.

  • Results

    The algorithms solve generalized SISO/MIMO cognitive-radio games and show superiority over plain noncooperative solutions with good performance relative to centralized solutions.

  • Takeaways & Limitations

    With limited signaling, the methods can select a high-quality equilibrium among multiple solutions rather than leaving the reached equilibrium unpredictable.

  • Takeaways & Limitations

    The P-property convergence condition cannot hold when a player’s cost function has a singular Hessian at even one point.

Abstract

from arXiv · show

Noncooperative game-theoretic tools have been increasingly used to study many important resource allocation problems in communications, networking, smart grids, and portfolio optimization. In this paper, we consider a general class of convex Nash Equilibrium Problems (NEPs), where each player aims to solve an arbitrary smooth convex optimization problem. Differently from most of current works, we do not assume any specific structure for the players' problems, and we allow the optimization variables of the players to be matrices in the complex domain. Our main contribution is the design of a novel class of distributed (asynchronous) best-response- algorithms suitable for solving the proposed NEPs, even in the presence of multiple solutions. The new methods, whose convergence analysis is based on Variational Inequality (VI) techniques, can select, among all the equilibria of a game, those that optimize a given performance criterion, at the cost of limited signaling among the players. This is a major departure from existing best-response algorithms, whose convergence conditions imply the uniqueness of the NE. Some of our results hinge on the use of VI problems directly in the complex domain; the study of these new kind of VIs also represents a noteworthy innovative contribution. We then apply the developed methods to solve some new generalizations of SISO and MIMO games in cognitive radios and femtocell systems, showing a considerable performance improvement over classical pure noncooperative schemes.

1 Introduction and Motivation

The paper targets distributed solution of broad real and complex player-convex NEPs, including games with multiple equilibria. It develops VI-based asynchronous best-response methods that can select equilibria using limited signaling.

  • Noncooperative games model decentralized resource allocation in communications, networking, and smart grids where centralized approaches are unsuitable.
  • Player-convex NEPs permit real vectors or complex matrices, with each player solving a convex, continuously differentiable optimization problem given rivals’ strategies.The paper treats this as a general setting without imposing application-specific structure.
  • Existing distributed best-response methods typically require special problem structure, unique or closed-form best responses, or convergence conditions implying a unique equilibrium.
  • The paper develops a VI-based unified theory and distributed asynchronous best-response algorithms for general player-convex NEPs.The framework provides a systematic way to analyze algorithms and extends to complex-domain problems.
  • For games with multiple equilibria, the proposed schemes can select solutions satisfying a prescribed performance criterion at the cost of limited player signaling.
  • The framework does not require best responses to be unique or available in closed form.

2 Motivating Examples: Noncooperative Games Over Gaussian ICs

The paper formulates generalized SISO and MIMO Gaussian interference-channel resource-allocation problems as real or complex NEPs. These examples expose limitations of existing waterfilling analyses and motivate the proposed general framework.

  • The motivating applications are cognitive-radio and related multiuser systems modeled by SISO or MIMO Gaussian interference channels.The interference-channel model also covers systems such as ad-hoc, peer-to-peer, multicell, and femtocell networks.
  • 2.1 The SISO case: In the SISO model, each secondary link chooses a power-allocation vector across parallel Gaussian subchannels to maximize its rate given other users’ allocations.
  • 2.1 The SISO case: SISO cognitive-radio feasible sets include total power budgets, spectral masks, and generalized interference constraints limiting radiated power toward primary users.
  • 2.1 The SISO case: Classical SISO results guarantee uniqueness and asynchronous IWFA convergence under ρ(Γ) < 1, but this condition can be too restrictive when multiple equilibria occur.
  • 2.2 The MIMO case: The MIMO model uses transmit covariance matrices and allows null, soft, and peak power-shaping constraints over prescribed spatial, temporal, or frequency directions.
  • 2.2 The MIMO case: Existing asynchronous MIMO IWFA results rely on specific waterfilling structure and do not apply to the generalized MIMO NEP.

3 Nash Equilibrium Problems

The paper connects convex NEPs to partitioned variational inequalities, enabling existence, uniqueness, and algorithmic analysis through properties of the associated mapping. Matrix conditions provide practical sufficient tests for these properties.

  • 3.1 Connection to variational inequalities: A real NEP consists of players choosing feasible strategies while minimizing objectives coupled through the other players’ decisions.
  • 3.1 Connection to variational inequalities: The VI reformulation converts best-response fixed-point analysis into a framework supporting distributed solution methods.
  • 3.1 Connection to variational inequalities: Under closed convex strategy sets and player-wise convex differentiable objectives, the NEP is equivalent to an associated partitioned VI.
  • 3.2 Existence and uniqueness of a NE: Bounded strategy sets ensure a nonempty compact solution set, while monotonicity gives a convex solution set and P or strict monotonicity gives at most one solution.
  • 3.2 Existence and uniqueness of a NE: Uniform P or strong monotonicity guarantees a unique NE.
  • 3.3 Problem classes: The framework introduces condensed matrices and extends VI analysis directly to complex domains, including feasible sets with empty interior.
  • 3.3 Problem classes: Copositivity, positive definiteness, and P-matrix conditions on condensed Jacobian-related matrices provide sufficient conditions for monotonicity and uniform-P properties.

4 Distributed Algorithms for NEPs

The paper develops distributed best-response algorithms for real player-convex and monotone NEPs, including games with multiple equilibria and equilibrium-selection objectives. The methods combine proximal regularization, asynchronous updates, and limited signaling while providing convergence guarantees under stated conditions.

  • Algorithmic framework: The framework provides distributed and asynchronous algorithms for P Υ NEPs and monotone NEPs, including games with multiple solutions.The algorithms differ in computational effort and player synchronization or signaling requirements.
  • P Υ NEPs: Algorithm 1 converges to the unique NE under updating schedules satisfying assumptions A1–A3.The convergence guarantee applies to all special cases generated by the algorithm and is robust to missing or outdated updates.
  • P Υ NEPs: Global convergence of Algorithm 1 requires the P property of ΥF, equivalently ρ(ΓF) < 1.The paper notes that this condition cannot hold when a player's cost function has a singular Hessian at even one point.
  • Monotone NEPs: Proximal regularization reduces solving a monotone NEP to solving a sequence of P Υ NEPs, with each regularized solution connected to the original game.A point x⋆ solves the original game if and only if it solves the regularized game Gτ,x⋆.
  • Monotone NEPs: The proximal algorithm generates a sequence converging to a solution of the monotone game, but exact computation may require a potentially infinite number of inner iterations.In practice, inaccurate subproblem solutions and a limited number of regularized games can often yield an accurate original-NEP solution.
  • Equilibrium selection: Equilibrium-selection algorithms target solutions satisfying an additional criterion and converge so that every limit point solves the selection problem under Theorem 21's assumptions.The approach incurs a moderate increase in best-response computation and interplayer signaling.

5 Variational Inequalities and Games in the Complex Domain

The paper develops a direct complex-domain framework for variational inequalities and convex-player games with complex matrix variables. It introduces derivative, monotonicity, and convexity tools that extend real-domain analysis and support complex NEP solution methods.

  • Motivation: Complex-domain analysis avoids awkward real reformulations for communication and signal-processing problems with complex matrix variables.The paper motivates direct treatment because real-domain reformulations can be difficult to handle and produce conditions that are hard to interpret in the original complex setup.
  • Derivative tools: Wirtinger calculus and R-differentiability provide the derivative framework for real- and complex-valued functions of complex variables and matrices.The development distinguishes formal derivatives with respect to a variable and its conjugate from real partial derivatives of real and imaginary components.
  • Complex variational inequalities: The complex VI problem generalizes the minimum principle by replacing the conjugate gradient with a complex-valued matrix mapping.This formulation is used to study monotonicity and P properties directly in the complex domain.
  • Monotonicity and P properties: A novel augmented Jacobian containing R-derivatives and conjugate R-derivatives yields complex-domain conditions for monotonicity, strict and strong monotonicity, and P properties.Augmented positive semidefiniteness or definiteness of the Jacobian, and corresponding conditions on ΥFC, provide the stated characterizations or sufficient conditions.
  • Convexity: For real-valued functions of complex variables, convexity is characterized through monotonicity of the conjugate gradient and an augmented Hessian.The paper also shows that ordinary positive-semidefiniteness can be too restrictive, motivating augmented positive semidefiniteness.
  • Complex NEPs: Under closed convex strategy sets and convex, continuously R-differentiable payoffs, a complex NEP is equivalent to a complex VI.This equivalence enables the real-domain solution developments to be extended to complex player-convex NEPs.

6 Noncooperative Games Over Interference Channels Revisited

The paper applies its real/complex NEP framework to SISO and MIMO interference-channel games, with convergence guarantees for unique and multiple equilibria. The resulting distributed algorithms support efficient best responses and equilibrium selection through limited cooperation.

  • Applications: SISO and MIMO interference-channel games are formulated within the proposed real/complex NEP framework and solved with distributed algorithms.The applications include novel waterfilling-like procedures for SISO systems and analogous results for MIMO games.
  • SISO case: Positive semidefiniteness of JGlow yields monotonicity, while P-matrix conditions on ΥG yield a unique SISO Nash equilibrium.The P-matrix conditions have a physical interpretation in terms of sufficiently small interference among secondary users.
  • SISO case: In the low-interference regime, Algorithm 1 converges asynchronously to the unique SISO equilibrium under assumptions A1–A3.Each user can compute its best response locally through a multi-level waterfilling-like expression based on measured overall interference.
  • SISO case: For monotone SISO games with multiple equilibria, PDAs and PTRA provide convergence-guaranteed distributed solution options, with PTRA enabling equilibrium selection through limited cooperation.These methods are presented as the first distributed power-control schemes in the cited signal-processing and communications literature to converge with multiple Nash equilibria.
  • Equilibrium selection: PTRA solves a sequence of perturbed PΥ NEPs, and Algorithm 5 converges so every limit point solves the equilibrium-selection problem minimizing the chosen merit criterion.The procedure uses ε(n) tending to zero, a suitable proximal parameter, and modified player objectives; it can target minimum overall interference among users.
  • MIMO case: For the complex MIMO game, positive semidefiniteness gives monotonicity, whereas P-matrix or positive-definiteness conditions make it a complex PΥ NEP with a unique equilibrium.Algorithm 1 converges asynchronously to that unique equilibrium under assumptions A1–A3, while Algorithm 4 converges to a solution of the selection problem.

7 Numerical Results

The numerical experiments compare distributed algorithms for SISO and MIMO cognitive-radio games by achievable sum-rate and convergence speed. Best-response methods perform well, including equilibrium selection with limited signaling and faster convergence than gradient-response schemes.

  • SISO results: More than 90% separates the worst and best Nash equilibria in SISO sum-rate, motivating equilibrium selection.
  • SISO results: Algorithm 5 outperforms Algorithm 2 by selecting equilibria through criterion (55), while losing little sum-rate relative to the DPA.The DPA requires significant signaling among users at each iteration.
  • SISO results: Algorithm 5 retains superior average sum-rate over Algorithm 2 across 5000 random channel realizations.The comparison uses average sum-rate versus SNR under the stated channel and power settings.
  • Convergence comparison: Best-response schemes reach comparable performance in a very few iterations, whereas gradient-response requires two orders of magnitude more iterations.This convergence pattern was observed across all simulated channel realizations.
  • MIMO results: In the MIMO experiment, sum-rate is compared across Jacobi best-response algorithms, a merit-function method, and a Gauss-Seidel stationary-solution algorithm.The setting uses three antennas per transceiver, five active secondary users, and nonlinear programming for strongly convex player problems.
  • MIMO results: The MIMO stationary-solution scheme requires exchanging matrix information among secondary users at each iteration.

8 Conclusions

The paper develops a VI-based framework for general real or complex player-convex NEPs, including games with multiple equilibria. Applications to SISO and MIMO cognitive-radio resource allocation show convergence and improved performance relative to plain noncooperative solutions, with performance comparable to centralized approaches.

  • The proposed VI method handles real or complex player-convex NEPs with arbitrary structure, nonunique or unavailable closed-form best responses, and multiple solutions.
  • The algorithms converge under mild conditions that do not imply equilibrium uniqueness and can target a best equilibrium under a prescribed criterion.Equilibrium selection requires some signaling among players.
  • Complex-domain VI problems and their properties are introduced and studied for the first time in the paper.
  • Applications to SISO and MIMO cognitive-radio resource-allocation NEPs show convergence where related literature schemes can fail.
  • Numerical results show superiority over plain noncooperative solutions and good performance relative to centralized solutions.

A.1 Solution analysis

This section defines monotonicity and P-type properties for VI mappings, then states how these properties constrain existence, convexity, and uniqueness of VI solutions. Stronger properties yield stronger solution guarantees.

  • Function classes: A mapping is monotone when its pairwise variational inequality is nonnegative, strictly monotone when the inequality is strict for distinct points, and strongly monotone when it has a positive quadratic lower bound.
  • Function classes: For partitioned mappings, P0, P, and uniformly P properties extend monotonicity concepts to blockwise comparisons.The uniformly P property uses a constant c_uP and a squared-norm lower bound.
  • Function classes: Monotonicity plays the role for VIs that convexity plays for optimization, while P properties are tailored to partitioned structures.
  • Solution analysis: A continuous VI on a closed convex set has a closed solution set, and boundedness of the feasible set ensures nonemptiness and compactness.
  • Solution analysis: A monotone VI has a possibly empty convex solution set, whereas strict monotonicity or the P property implies at most one solution.
  • Solution analysis: Strong monotonicity or the uniformly P property guarantees a unique VI solution.

B Proof of Proposition 5

The proof establishes a lower bound using a univariate mean-value argument and properties of a P-matrix. The final bound depends on matrix characteristics and the number of players.

  • Because of space limitations, only part (e) is proved explicitly; parts (a)–(d) are said to follow similar ideas.
  • The proof introduces a univariate continuously differentiable function along the segment joining two feasible points and applies the mean-value theorem.
  • A P-matrix property yields a positive constant c(Υ_F) used in the proof.
  • The lower bound is obtained as c(Υ_F) ≥ δ(Υ_F)/(I · (1 + ζ(Υ_F)/δ(Υ_F))^2(I−1)).

C Proof of Theorem 10

The proof establishes that the best-response mapping is a block-contraction under the theorem’s assumptions. This contraction satisfies the asynchronous convergence conditions for Algorithm 1.

  • Convergence implication: Because block-contraction guarantees the hypotheses of the asynchronous convergence theorem, Algorithm 1 satisfies the required asynchronous convergence conditions.This connects the contraction property directly to the convergence analysis of the distributed best-response method.
  • Norm argument: A suitable weighted block-maximum norm is defined using the nonsingular matrices Ci and a positive weight vector c.The proof then shows that ΓF has induced matrix norm below one for an appropriate choice of c.
  • Block-contraction result: Under the P-property assumption on ΥF, the best-response mapping B(x) is a block-contraction.There exists a positive weight vector c such that the induced contraction factor αc is below one.
  • Proof construction: The proof uses optimality inequalities for best responses at two points x and y, then combines them through an intermediate convex combination.The resulting inequality relates best-response differences to gradients evaluated along a line segment.
  • Proof construction: Introducing blockwise differences and norms converts the componentwise inequalities into a vector inequality involving ΓF.The block differences are measured by eBi = ∥Bi(x) − Bi(y)∥i and ei = ∥xi − yi∥i.

D Proof of Proposition 15

The proof characterizes equilibria of a monotone game through fixed points of a regularized, strongly monotone game. The regularization gives a unique equilibrium for each reference point.

  • Regularized game: The regularized game Gτ,y corresponds to a strongly monotone VI and therefore has a unique Nash equilibrium for every τ > 0 and y.That equilibrium is denoted Sτ(y) = SOL(Q, F + τ(I − y)).
  • Equilibrium characterization: Every Nash equilibrium x⋆ of the original monotone game is a fixed point of the regularized solution mapping Sτ.The VI conditions imply x⋆ = Sτ(x⋆), and x⋆ is the unique equilibrium of Gτ,x⋆.

E Proof of Theorem 21

The proof analyzes an iterative VI-based algorithm by showing that all limit points belong to the target solution set and that the distance measure δ(n) converges to zero. Three cases cover the possible index-set behaviors.

  • VI formulation: The NEP is equivalent to VI(Q, F), and each regularized VI solved by Algorithm 4 has a unique solution because F(n) is strongly monotone.The target solution set S is nonempty, bounded, and convex.
  • Convergence measure: The proof measures progress using the Euclidean projection PS onto S and reduces convergence to showing δ(n) tends to zero.A VI inequality at each iteration is combined with projection properties and monotonicity of F.
  • Case 1: When V(n+1) is eventually nonpositive, δ(n) becomes eventually non-increasing, and the proof obtains boundedness and vanishing successive differences.This permits the limit-point argument used to establish convergence to S.
  • Limit-point argument: The limit-point argument uses VI inequalities, continuity, and convexity of the performance function to show that accumulation points lie in the desired solution set.This establishes convergence of the relevant subsequences and, through the case analysis, the full sequence.
  • Case 2: When both index sets J and J̄ are infinite, the subsequence indexed by J̄ is shown to be bounded, and every convergent subsequence has δ(n) approaching zero.Continuity and the VI characterization imply that its limit points belong to S.
  • Case 3: When J is infinite and J̄ is finite, δ(n) is eventually non-increasing, so the argument reduces to the preceding limit-point reasoning.The proof concludes that δ(n) converges to zero in this remaining case.

F Proof of Lemma 23

The proof of Lemma 23 converts real-valued functions of complex matrices into real-coordinate functions. Standard real calculus is then used to derive Taylor and derivative relationships in the complex domain.

  • Taylor expansion: The first-order Taylor expansion for the complex-matrix function follows by applying standard real Taylor expansion to its real-coordinate representation.The remainder of the proof then follows the minimum-principle argument for real-valued functions of real variables.
  • Real-coordinate representation: A complex matrix space Cn×m is represented as the real space R2nm through an isomorphic transformation.The original complex variables and their real-coordinate representations are denoted separately.
  • Derivative connection: For a real-valued function of complex matrices, the corresponding real-coordinate function is differentiable whenever the original function is continuously R-differentiable.The Jacobians of the two representations are connected through the function’s Jacobian and conjugate Jacobian.
  • Taylor expansion: The proof verifies the complex derivative identities using vectorization, trace relations, and the fact that the function is real-valued.These identities complete the derivation of the stated Taylor relation.
  • Derivative and Hessian calculations: The appendix derives conjugate derivatives and the augmented Hessian for the log-determinant example using matrix differential and vectorization rules.The inverse differential, Kronecker-product vectorization, and commutation-matrix identities lead to the augmented Hessian expression.
  • Derivative and Hessian calculations: The resulting Jacobian calculations yield the augmented Hessian HZZ∗˜f(Z) used in the paper’s complex-domain analysis.The derivation relies on standard identification rules for complex matrix derivatives.
  • Proof organization: Proposition 28 is sufficient to prove because Proposition 27 is a special case.The proof introduces an intermediate result before establishing Proposition 28.

H.1 Mean-value theorem for functions of complex variables

The section establishes a mean-value theorem for real-valued functions of complex matrices by reducing the analysis to a scalar function along a line segment and applying complex matrix differentiation.

  • The theorem considers a continuously R-differentiable real-valued matrix function on a convex, closed subset of complex matrices.
  • For two points in the domain, the proof defines a scalar function along their line segment and applies the mean-value theorem at an intermediate point.
  • The derivative of the scalar function is computed using the chain rule for complex matrix derivatives.
  • The resulting expression is rewritten compactly using the augmented Jacobian matrix introduced earlier.

H.2 Proof of Proposition 28

The proof characterizes monotonicity and strong monotonicity through the augmented Jacobian on the feasible affine subspace, using line segments for sufficiency and relative-interior limits for necessity.

  • Sufficiency part: Sufficiency follows by applying the mean-value result to two feasible points and using convexity to keep the connecting segment inside the domain.
  • Sufficiency part: A uniform quadratic-form lower bound involving the augmented Jacobian implies strong monotonicity of FC on K.
  • Necessity part: For necessity, strong monotonicity first yields the corresponding Jacobian inequality at points in the relative interior of K.
  • Necessity part: The inequality extends to boundary points by approximating them with a sequence from ri(K) and using continuity of the Jacobian.
  • When K has nonempty interior, the result reduces to Proposition 27 because Aff(K) equals the full complex matrix space.

I Proof of Proposition 36

The proof establishes Proposition 36 by relating the augmented Jacobian to a block derivative matrix and bounding its off-diagonal terms through spectral-radius and comparison-matrix arguments.

  • The proof reduces augmented positive semidefiniteness of the Jacobian to positive semidefiniteness of the derivative matrix DQFC(Q).
  • Because DQ⋆FC(Q) equals zero, the augmented Jacobian becomes block diagonal, with blocks determined by derivatives of the players’ mappings.
  • The derivative matrix is represented through Kronecker products of the channel-dependent matrices Ψij(Q).
  • A condensed matrix captures the relevant diagonal and off-diagonal terms, and its off-diagonal terms are rewritten using spectral norms and square-root matrix factors.
  • The comparison matrix ΥmimoFC is used to transfer positive-semidefiniteness to the derivative and augmented Jacobian matrices.
  • The argument uses that the channel matrices Hii are full-column rank, ensuring the relevant Ψii(Q) matrices are positive definite.
  • The proof bounds the interaction terms using projection, spectral-radius, and matrix-order inequalities, obtaining the required relationship between the comparison-matrix entries.
Loading 1212.6235v2…