PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal Linear Precoding Strategies for Wideband Non-Cooperative Systems based on Game Theory-Part I: Nash Equilibria

Gesualdo Scutari, D. P. Palomar, S. Barbarossa

arXiv:0707.0568v1cs.ITcs.GT

TL;DR

The paper studies decentralized transceiver design for wideband links competing over shared resources, asking when Nash equilibria exist and are unique and how their performance compares with centralized optimization. It models links as strategic players and shows that equilibria exist as pure strategies, with low performance loss relative to Pareto-optimal solutions especially in symmetric systems.

  • Problem

    The paper asks under which conditions Nash equilibria exist and are unique, and what performance penalty decentralized optimization incurs.

  • Method

    The paper formulates each link as a game-theoretic player that chooses its transceiver pair to optimize under shared-resource constraints.

  • Results

    Nash equilibria always exist as pure strategies, while decentralized performance loss relative to the Pareto-optimal solution is low in symmetric systems and larger in highly asymmetric systems.

  • Takeaways & Limitations

    The decentralized strategy closely approaches Pareto-optimal performance in symmetric systems, but its loss is greater when systems are highly asymmetric.

  • Takeaways & Limitations

    The analysis assumes white noise, although the authors describe extension to colored noise as straightforward.

Abstract

from arXiv · show

In this two-parts paper we propose a decentralized strategy, based on a game-theoretic formulation, to find out the optimal precoding/multiplexing matrices for a multipoint-to-multipoint communication system composed of a set of wideband links sharing the same physical resources, i.e., time and bandwidth. We assume, as optimality criterion, the achievement of a Nash equilibrium and consider two alternative optimization problems: 1) the competitive maximization of mutual information on each link, given constraints on the transmit power and on the spectral mask imposed by the radio spectrum regulatory bodies; and 2) the competitive maximization of the transmission rate, using finite order constellations, under the same constraints as above, plus a constraint on the average error probability. In Part I of the paper, we start by showing that the solution set of both noncooperative games is always nonempty and contains only pure strategies. Then, we prove that the optimal precoding/multiplexing scheme for both games leads to a channel diagonalizing structure, so that both matrix-valued problems can be recast in a simpler unified vector power control game, with no performance penalty. Thus, we study this simpler game and derive sufficient conditions ensuring the uniqueness of the Nash equilibrium. Interestingly, although derived under stronger constraints, incorporating for example spectral mask constraints, our uniqueness conditions have broader validity than previously known conditions. Finally, we assess the goodness of the proposed decentralized strategy by comparing its performance with the performance of a Pareto-optimal centralized scheme. To reach the Nash equilibria of the game, in Part II, we propose alternative distributed algorithms, along with their convergence conditions.

1 Introduction and Motivation

The paper formulates decentralized precoding and multiplexing for noncooperative wideband links as matrix-valued games, using Nash equilibrium as the optimality criterion. Part I establishes equilibrium existence, diagonal optimality, uniqueness conditions, and performance assessment against centralized solutions.

  • System model: The system comprises Q noncooperative wideband links sharing time and bandwidth, with independent encoding and decoding and multiuser interference treated as colored additive noise.Each receiver knows its direct channel and interference covariance matrix, but not the interfering channels.
  • Optimization problems: The paper studies mutual-information maximization and finite-constellation transmission-rate maximization under transmit-power and spectral-mask constraints, with average error probability additionally constrained in the latter.Spectral masks impose radiation limits over licensed bands, while finite constellations motivate the second problem.
  • Game-theoretic formulation: Both optimization problems are cast as strategic noncooperative matrix-valued games in which each link selects its transceiver pair to maximize its own payoff.This transforms a coupled multi-objective design problem into mutually coupled competitive single-objective problems.
  • Part I contributions: The solution sets of both games are always nonempty and contain only pure strategies, while diagonal transmission through channel eigenmodes is optimal without performance penalty.The diagonal structure applies irrespective of channel state, power budget, spectral-mask constraints, and interference levels, reducing both problems to a unified vector power-control game.
  • Part I contributions: Part I provides sufficient conditions for unique Nash equilibrium, shows the condition holds beyond a critical interlink distance almost irrespective of channel frequency response, and compares decentralized performance with Pareto-optimal solutions.The paper also modifies the game so its equilibria coincide with Pareto-optimal solutions, at the cost of significantly increased signaling and coordination.

2 System Model and Problem Formulation

The paper models independently operated wideband links as a vector Gaussian interference channel and formulates decentralized transceiver design as noncooperative games under power, spectral-mask, and error-rate constraints. For mutual-information maximization, Nash equilibria can be achieved with pure strategies and Gaussian signaling.

  • 2.1 System model: Users operate independently without coordination or interference cancellation, so multiuser interference is treated as additive colored noise.The model assumes independent encoding and decoding across links.
  • 2.1 System model: Channels are fixed FIR filters, with cyclic prefixes and quasi-block synchronization enabling block-based transmission.The cyclic-prefix length satisfies L ≥ Lh, where Lh is the maximum channel order.
  • 2.1 System model: Cyclic-prefix insertion diagonalizes each resulting channel matrix through the normalized IFFT, yielding parallel frequency-bin channels.After guard-interval removal, Hrq is Toeplitz circulant and is diagonalized as Hrq = WDrqWH.
  • 2.1 System model: Each transmitter is constrained by maximum total power and per-frequency-bin spectral masks, while each link must satisfy a maximum tolerable uncoded symbol error rate.Spectral masks limit interference over specified frequency bands.
  • 2.2 Problem Formulation: Optimal Transceivers Design based on Game Theory: Transceiver pairs are designed within a game-theoretic framework using Nash equilibrium as the optimality criterion and considering two payoff-function classes.The formulation explicitly targets decentralized design of the transceiver pairs (Fq, Gq).
  • 2.2.1 Competitive maximization of mutual information: Under Gaussian signaling, users competitively maximize mutual information subject to maximum-power and spectral-mask constraints, with MMSE reception assumed without capacity loss.The receiver can be modeled as an MMSE stage followed by another stage because MMSE is capacity-lossless.
  • 2.2.1 Competitive maximization of mutual information: Every Nash equilibrium of the mutual-information game is achieved using pure strategies, because the payoff is strictly concave in each user’s precoding covariance.The mixed-strategy extension therefore does not require randomization at equilibrium.
  • 2.2.2 Competitive maximization of transmission rates: The transmission-rate formulation motivates moving beyond ideal Gaussian codebooks to finite-order constellations.The preceding optimality criterion requires ideal Gaussian codebooks.

3 Optimality of the Channel-Diagonalizing Structure

Theorem 1 establishes that diagonal transmission is optimal for both noncooperative games, including finite-constellation rate maximization under spectral-mask, power, and error-probability constraints. This result converts the matrix-valued problems into an equivalent vector power-control game without performance loss.

  • Optimal diagonal transmission: Theorem 1 proves that both matrix-valued games admit an optimal channel-diagonalizing transmission structure.Each user transmits diagonally through the channel eigenmodes, corresponding to frequency bins.
  • Optimal diagonal transmission: The diagonal structure remains optimal irrespective of channel realizations, power budgets, spectral masks, and multiuser interference.The result reduces each user’s unknowns from N^2 matrix entries to N power variables, with no performance loss.
  • Optimal diagonal transmission: The theorem extends diagonal-transmission optimality to G2, which maximizes finite-constellation transmission rate under spectral-mask, power, and average-error-probability constraints.Earlier approaches imposed diagonalization and gap approximation without proving their joint optimality; Theorem 1 proves it and includes the no-mask case as a special case.
  • Equivalent vector game: Because all channel matrices share the IFFT matrix W as a diagonalizing matrix, the matrix games can be replaced by an equivalent vector game without performance loss.The same common-diagonalizer property also appears for time-varying flat-fading channels with transmit-power and time-interval emission constraints, where the identity matrix diagonalizes all channels.
  • Dual time-domain interpretation: By duality, the optimal strategy in the corresponding time-selective setting is a form of TDMA across N time slots, with users optimizing power allocation across slots.This interpretation requires non-causal knowledge of channel variation, potentially obtained through channel prediction.

4 Existence and Uniqueness of NE

Theorem 2 establishes existence of a Nash equilibrium for arbitrary channels, spectral masks, and transmit powers, with uniqueness guaranteed by condition (C1). The paper also gives alternative interference-based conditions and shows that (C1) is less restrictive and exhibits threshold behavior tied to interlink distance.

  • Theorem 2: Theorem 2 guarantees a nonempty solution set for any channels, spectral mask constraints, and transmit powers; the NE is unique when ρ(H(k)) < 1 for every k.Here, H(k) is the matrix defined in (26), and ρ(H(k)) denotes its spectral radius.
  • Alternative sufficient conditions: Corollary 2 provides two sufficient alternatives, (C3) and (C4), using weighted interference bounds for every user or transmitter and every subcarrier.The conditions use any positive vector w and the matrix H(k) defined in (26).
  • Physical interpretation: Uniqueness is ensured when links are sufficiently far apart, with (C3) bounding interference received by each user and (C4) bounding interference generated by each transmitter.As multiuser interference becomes negligible, the rate-maximization problems decouple and each user’s problem has a unique solution.
  • Robustness of uniqueness: The uniqueness condition is robust to the worst normalized channel ratios because subcarriers with extreme ratios may be excluded from the active sets Dq.This includes subchannels where the direct channel gain |Hqq(k)|2 is vanishing.

5 Physical Interpretation of NE

The Nash equilibrium changes with interference: low interference yields a unique, full-bandwidth allocation that becomes flat at high SNR, whereas high interference permits multiple orthogonal equilibria. At intermediate levels, users’ power spectra partially overlap.

  • Low interference case: When interference is low and SNR is sufficiently large, condition (C1) holds, the NE is unique, and every user uses the whole bandwidth.The low-interference regime corresponds to sufficiently small inrq and sufficiently large snrq; this can occur when links are sufficiently far apart.
  • Low interference case: As SNR increases in the low-interference regime, each user’s optimal power allocation tends to become flat across the whole bandwidth.The resulting full-spectrum transmission is compared with a CDMA-like system because interference nulling would not justify bandwidth reduction.
  • High interference case: When inrq >> 1 for all distinct links, the game admits multiple Nash equilibria, including FDMA-like orthogonal equilibria with nonoverlapping user power spectra.Users self-organize into nonoverlapping bands to remove interference completely; when Q = N, there are Q! such equilibria corresponding to carrier permutations.
  • High interference case: As interference decreases, the NE becomes unique; if an orthogonal equilibrium remains, each user receives the best portion of the spectrum, while intermediate interference permits partial PSD superposition.The allocation rule generalizes the multiple-access frequency-selective channel condition, and numerical examples show users tending toward nonoverlapping bands under high interference.

6 How good is a Nash Equilibrium ?

This section evaluates Nash equilibria against Pareto-efficient centralized solutions, showing that ordinary equilibria are generally not Pareto-efficient but can be aligned with Pareto optima through modified utilities. Under low interference and high SNR, the modified game has unique equilibria representing any Pareto-optimal rate profile, while ordinary equilibria admit performance bounds but may remain Pareto dominated.

  • Motivation and comparison: Nash equilibria generally are not Pareto-efficient, so uniqueness alone does not guarantee proximity to the centralized optimum.The section compares equilibrium rates with the Pareto-optimal boundary of the achievable rate region.
  • Rate-region characterization: Under low interference (inrrq << 1) and high SNR (snrq >> 1), the achievable rate region R is convex.This condition enables Pareto trade-offs to be characterized through the rate region.
  • Pareto-aligned game: For any positive weight vector λ, the modified game has a nonempty equilibrium containing the globally optimal solution of the corresponding scalarized multi-objective problem.The associated Pareto point is where the hyperplane with normal vector λ is tangent to the rate-region boundary.
  • Pareto-aligned game: When Proposition 3 holds, the modified game admits a unique Nash equilibrium for every λ > 0, and every Pareto-optimal rate profile can be obtained with a proper λ.The modified utility incorporates positive-weight linear combinations of the other players’ utilities.
  • Coordination cost: Achieving Pareto efficiency requires significant signalling and coordination, conflicting with the goal of distributed, independent coding and decoding.The proposed gradient-projection approach requires each user to know other users’ channels and strategies at every iteration.
  • Bounds on ordinary equilibria: Every ordinary-game Nash equilibrium yields each user a rate above the worst-case benchmark, but such equilibria may still be Pareto dominated.The section next quantifies this loss numerically.

7 Numerical Results

Numerical results compare Nash-equilibrium rate regions with Pareto-optimal boundaries in symmetric and asymmetric two-user systems. They show limited loss in symmetric settings, up to 30% sum-rate loss under strong asymmetry, and improved decentralized performance with increasing channel order.

  • Example 1: Symmetric Case: In symmetric two-user systems, Nash equilibria approach the Pareto-optimal curve as interference decreases.When interference is sufficiently low, user interaction becomes negligible and performance is noise-limited; at closer interpair distances, interference dominates and the decentralized loss grows, but remains limited.
  • Example 1: Symmetric Case: The decentralized game-theoretic approach is viable for symmetric systems because it is simpler than the centralized optimal solution.This conclusion was observed across several independent symmetric channel realizations, including cases where links were relatively close.
  • Example 1: Symmetric Case: The modified game can reach solutions to the multiobjective problem as Nash equilibria, but its gradient projection algorithm is not distributed.The algorithm requires every user to know the channels and power allocations of all other links.
  • Example 2: Asymmetric Case: In asymmetric systems, increasing asymmetry makes Nash equilibria diverge more from corresponding Pareto-optimal points.For the illustrated setup, the sum-rate performance loss reaches 30% of the globally optimal solution, with the same qualitative behavior across channel realizations and user counts.
  • Example 3: Rate region versus channel order: Decentralized performance improves with increasing channel order because larger frequency fluctuations provide more degrees of freedom for spectral partitioning.The simulations use i.i.d. Gaussian channel taps with zero mean and variance 1/(L_h + 1).

8 Conclusions · A.1 Game G1

The paper establishes Nash equilibria for both mutual-information and finite-constellation rate games, with optimal diagonal transmission reducing them to a unified vector power-control game. It also gives uniqueness conditions, compares decentralized and Pareto-optimal centralized strategies, and proves the diagonal optimal structure for G1.

  • 8 Conclusions: Both noncooperative games always possess Nash equilibria in pure strategies, and their optimal precoding/multiplexing strategies yield diagonal transmission for all users.The games respectively maximize mutual information or finite-constellation transmission rate under spectral-mask, power, and average-error-probability constraints.
  • 8 Conclusions: The diagonal structure reduces both original matrix-valued games to a unified vector power-control game without performance penalty.This simplification enables analysis of equilibrium properties in the lower-dimensional formulation.
  • 8 Conclusions: Sufficient conditions for Nash-equilibrium uniqueness are derived and shown to have broader validity than previously known conditions for special cases.The conditions incorporate stronger constraints, including spectral-mask constraints, while applying more broadly than earlier results.
  • 8 Conclusions: The decentralized strategy incurs relatively low performance loss versus the Pareto-optimal centralized solution in symmetric systems, but larger losses in very asymmetric systems.The comparison evaluates the totally decentralized strategy against a Pareto-optimal centralized scheme.
  • 8 Conclusions: Modified user payoffs can create a game whose Nash equilibria are Pareto-optimal, but extra signaling breaks the original games’ noncooperative feature.The modification is proposed to approach Pareto-optimal performance more closely.
  • A.1 Game G1: For game G1, fixing the other players’ strategies, the mutual-information maximum under the stated constraints is achieved by F_q = WΣ_qW^H, with Σ_q = diag(p_q) and p_q solving (20).The proof uses the Nash-equilibrium definition and characterizes each player’s best response.
  • A.1 Game G1: For G1, channel diagonalization by the IFFT matrix W and Hadamard’s inequality imply that an optimal Q_q is diagonal, yielding the desired structure for F_q.Equality is reached only when Q_q is diagonal, so setting Q_q = Σ_q is optimal without loss of generality.
  • A.1 Game G1: Spectral-mask constraints preserve the diagonal optimal structure because the additional constraints depend only on diagonal elements.Thus the preceding diagonality argument remains applicable when spectral masks are present.

A.2 Game G2 · B Proof of Theorem 2 · B.1 Existence of a NE

The proof reduces the matrix-valued optimization in Game G2 to an equivalent simpler problem whose optimum has a diagonalizing structure. The resulting game G admits at least one Nash equilibrium because its feasible strategy sets are convex and compact and its payoffs are continuous and concave in each player’s strategy.

  • A.2 Game G2: Game G2 is recast as the simpler game G in (20).
  • A.2 Game G2: The proof shows that, given other users’ optimal strategies at a Nash equilibrium, user q’s optimal precoding matrix has the form in (19).
  • A.2 Game G2: The original problem (18) is equivalent to a simpler problem whose solution yields the optimal structure for the original matrix F_q.
  • A.2 Game G2: An optimal P_q exists such that E_q(P_q) is diagonal, equivalently making the corresponding transformed interference-related matrix diagonal.
  • A.2 Game G2: The diagonalizing structure leads to a diagonal power allocation form for the optimal strategy.
  • B.1 Existence of a NE: The existence proof invokes a game-theoretic theorem requiring each strategy set to be nonempty, compact, and convex and each payoff to be continuous and quasi-concave.
  • B.1 Existence of a NE: The game G in (20) always admits at least one Nash equilibrium.
  • B.1 Existence of a NE: This follows because each feasible strategy-profile set is convex and compact, while each player’s payoff is continuous and strictly concave in its own strategy.

B.2 Uniqueness of the NE

The section derives sufficient conditions ensuring that the Nash equilibrium is unique. The proof rules out two distinct equilibria by showing that a P-matrix condition forces their difference to vanish.

  • Uniqueness argument: The analysis first derives a necessary condition that two distinct admissible strategy profiles would have to satisfy to both be Nash equilibria.This condition follows from the KKT conditions and concavity of the users’ payoff functions.
  • Uniqueness argument: A sufficient positivity condition prevents the first term in the equilibrium comparison inequality from vanishing, ruling out two different Nash equilibria.The argument identifies carriers where the two solutions differ and shows that positivity on those carriers contradicts the condition required by distinct equilibria.
  • P-matrix criterion: If H is a P-matrix, the comparison inequality forces all components of the equilibrium difference to zero, contradicting distinctness and guaranteeing uniqueness.The proof uses the P-matrix characterization that such a matrix cannot reverse the sign of a nonzero vector.
  • Spectral-radius condition: Condition (C1) implies the P-matrix requirement through the equivalence between I − H being a K-matrix and ρ(H) < 1.The block-diagonal structure of H converts the spectral-radius condition into (C1).
  • Corollary conditions: Additional corollary conditions follow from spectral-radius monotonicity and sufficient matrix-norm bounds for the block matrices H(k).The norm-based conditions use a weighted block maximum norm with any positive vector w.

C Proof of Proposition 2 · D Proof of Proposition 3

The proofs establish that high-interference systems always admit an orthogonal Nash equilibrium and characterize the required subcarrier distribution under condition (31). They also prove convexity of the rate region under the stated high-interference and high-signal-to-noise assumptions.

  • C Proof of Proposition 2: An orthogonal NE always exists in the high-interference environment.The proof shows that users have no rate-increasing incentive to share subcarriers at such a point.
  • C Proof of Proposition 2: If an orthogonal NE exists and condition (31) holds, the available subcarriers must be distributed among users according to (32).The characterization follows from the KKT conditions and the resulting relations for users’ assigned subcarrier sets.
  • C Proof of Proposition 2: At any orthogonal NE, each user’s power distribution satisfies single-user waterfilling over its assigned subcarriers.The construction uses user-specific subcarrier sets I_q and waterfilling on those sets.
  • C Proof of Proposition 2: A power distribution satisfying (76) always exists when Q ≤ N.For Q = N, Q! partitions assign one carrier to each user, guaranteeing (76).
  • C Proof of Proposition 2: The strategy profile in (76) is a NE because no user has an incentive to change its power allocation.Although the profile is not necessarily a NE initially, the proof establishes the no-deviation condition for every user.
  • D Proof of Proposition 3: The rate region defined in (33) is convex under the stated approximation.The proof applies logarithmic variables, convexity of the relevant log function, and an upper bound on the expression in (84).
  • D Proof of Proposition 3: The interpolated power vector is feasible because the power constraint set P is convex.This follows from the geometric-arithmetic inequality and p ≤ αp̄ + βp̃ ∈ P, with α, β ≥ 0 and α + β = 1.

E Proof of Proposition 4

The proof establishes that every λ > 0 yields at least one Nash equilibrium of eG(λ) containing a Pareto-optimal point, while under Proposition 3 the correspondence becomes one-to-one and the equilibrium is unique. Under those conditions, the convex rate-region boundary is attained through the scalarized MOP and eG(λ).

  • Existence and Pareto optimality: For any λ > 0, the Nash equilibria of eG(λ) include a Pareto-optimal point of MOP (34), although the converse is generally false.The converse fails because the payoff functions are not quasiconcave in pq.
  • Existence and Pareto optimality: For any λ > 0, eG(λ) has at least one Nash equilibrium because a solution to the scalarized MOP (35) always exists.The scalarized problem has a compact domain and a continuous objective in the interior.
  • Uniqueness under Proposition 3: Under Proposition 3, the correspondence between Nash equilibria and Pareto-optimal points becomes one-to-one, with each Pareto-optimal point associated with a unique NE for a proper λ.Proposition 3 also makes the rate region convex, allowing all boundary points to be achieved by solving the scalarized MOP.
  • Uniqueness under Proposition 3: For any λ > 0, eG(λ) admits a unique NE under Proposition 3, because its payoff functions are strictly concave in each player’s strategy and satisfy the uniqueness condition.The proof verifies the sufficient uniqueness condition using (81) and (90).

F Proof of Proposition 5

The proof of Proposition 5 derives the relevant lower bound from the Nash-equilibrium definition and establishes the minimax inequality by interchanging supremum and infimum. It verifies the required conditions using the compact strategy set and the concave-convex structure of each payoff function.

  • At any Nash equilibrium p⋆, the proof starts from the definition of Nash equilibrium to establish the required bound.
  • The inequality follows by interchanging the order of the supremum and infimum in the relevant expression.
  • The product strategy set P1 × . . . × PQ is closed, bounded, and non-empty, satisfying the cited minimax conditions.
  • Each payoff Rq(pq, p−q) is strictly concave in pq for fixed p−q and convex in p−q for fixed pq.
  • Therefore, Rq(pq, p−q) is concave-convex on Pq × P−q, completing the structural condition needed in the proof.
Loading 0707.0568v1…