Game theory in signal processing and communications [From the Guest Editors]

Game theory is a branch of mathematics aimed at the modeling and understanding of resource conflict problems. Essentially, the theory splits into two branches: noncooperative and cooperative game theory. The distinction between the two is whether or not the players in the game can make joint decisions regarding the choice of strategy. Noncooperative game theory is closely connected to minimax optimization and typically results in the study of various equilibria, most notably the Nash equilibrium. Cooperative game theory examines how strictly rational (selfish) actors can benefit from voluntary cooperation by reaching bargaining agreements. Another distinction is between static and dynamic game theory, where the latter can be viewed as a combination of game theory and optimal control. In general, the theory provides a structured approach to many important problems arising in signal processing and communications, notably resource allocation and robust transceiver optimization. Recent applications also occur in other emerging fields, such as cognitive radio, spectrum sharing, and in multihop-sensor and adhoc networks.     

MIMO-CDMA系统中一种基于博弈方式的分布式功率控制

针对MIMO-CDMA系统中的无线数据业务,本文研究了分布式非合作功率控制博弈。对MIMO-CDMA系统中的无线数据业务建立了收益函数,该收益函数对功率效率和频谱效率都进行了考虑,并能够反映系统中无线数据用户对服务质量(QoS)的满意程度。以收益函数为基础,建立了两种非合作功率控制博弈模型,并对模型纳什均衡的存在性和唯一性进行了推导。另外,还研究了两种代价函数机制。最后,给出了一种获得纳什均衡的算法,数值仿真结果表明该算法具有良好的性能,有效地控制了各用户的发射功率。     

Multiradio Channel Allocation in Multihop Wireless Networks

Channel allocation was extensively investigated in the framework of cellular networks, but it was rarely studied in the wireless ad hoc networks, especially in the multihop networks. In this paper, we study the competitive multiradio multichannel allocation problem in multihop wireless networks in detail. We first analyze that the static noncooperative game and Nash equilibrium (NE) channel allocation scheme are not suitable for the multihop wireless networks. Thus, we model the channel allocation problem as a hybrid game involving both cooperative game and noncooperative game. Within a communication session, it is cooperative; and among sessions, it is noncooperative. We propose the min-max coalition-proof Nash equilibrium (MMCPNE) channel allocation scheme in the game, which aims to maximize the achieved data rates of communication sessions. We analyze the existence of MMCPNE and prove the necessary conditions for MMCPNE. Furthermore, we propose several algorithms that enable the selfish players to converge to MMCPNE. Simulation results show that MMCPNE outperforms NE and coalition-proof Nash equilibrium (CPNE) schemes in terms of the achieved data rates of multihop sessions and the throughput of whole networks due to cooperation gain.     

基于非合作博弈论的多小区OFDMA系统动态资源分配算法研究

该文采用非合作博弈论的方法研究了多小区OFDMA系统中的动态资源分配问题,首先将各基站的发射功率平均分配给各子载波,然后由所有小区在每个子载波上独立地进行资源分配博弈,给出了用户调度与功率分配联合博弈框架。为了进一步简化,将用户调度和资源分配分开完成,通过将信道增益引入到定价函数中,提出了一种新的定价机制,建立了用户确定时的非合作功率分配博弈模型,分析了其纳什均衡的存在性和唯一性,并设计了具体的博弈算法。仿真结果表明,所提算法在保证吞吐量性能的同时,进一步提升了系统的公平性。     

Noncooperative Multimode Precoding with Limited Feedback in MIMO Interference Channels

This letter proposes an iterative multimode precoding scheme with limited feedback for nonreciprocal MIMO interference channels. Based on analysis of game theory, we model the iterative multimode precoding as a noncooperative game with a finite set of strategies. Numerical results are presented to verify the sum rate performance of the proposed scheme.     

Asynchronous Iterative Water-Filling for Gaussian Frequency-Selective Interference Channels

This paper considers the maximization of information rates for the Gaussian frequency-selective interference channel, subject to power and spectral mask constraints on each link. To derive decentralized solutions that do not require any cooperation among the users, the optimization problem is formulated as a static noncooperative game of complete information. To achieve the so-called Nash equilibria of the game, we propose a new distributed algorithm called asynchronous iterative water-filling algorithm. In this algorithm, the users update their power spectral density (PSD) in a completely distributed and asynchronous way: some users may update their power allocation more frequently than others and they may even use outdated measurements of the received interference. The proposed algorithm represents a unified framework that encompasses and generalizes all known iterative water-filling algorithms, e.g., sequential and simultaneous versions. The main result of the paper consists of a unified set of conditions that guarantee the global converge of the proposed algorithm to the (unique) Nash equilibrium of the game.     

Radio resource management games in wireless networks: an approach to bandwidth allocation and admission control for polling service in IEEE 802.16 [Radio Resource Management and Protocol Engineering for IEEE 802.16]

Game theory is a mathematical tool developed to understand competitive situations in which rational decision makers interact to achieve their objectives. Game theory techniques have recently been applied to various engineering design problems in which the action of one component impacts (and perhaps conflicts with) that of any other component. In particular, game theory techniques have been successfully used for protocol design and optimization (e.g., radio resource management, power control) in wireless networks. In this article we present an overview of different game theory formulations. Then a survey on the game-theory-based resource management and admission control schemes in different wireless networks is presented, and several open research issues are outlined. To this end, we propose an adaptive bandwidth allocation and admission control scheme for polling service in an IEEE 802.16-based wireless metropolitan area network. A noncooperative game is formulated, and the solution of this game is determined by the Nash equilibrium for the amount of bandwidth offered to a new connection. The admission control policy ensures QoS for all connections in the system     

Optimality and Complexity of Pure Nash Equilibria in the Coverage Game

In this paper, we investigate the coverage problem in wireless sensor networks using a game theory method.We assume that nodes are randomly scattered in a sensor field and the goal is to partition these nodes into K sets. At any given time, nodes belonging to only one of these sets actively sense the field. A key challenge is to achieve this partition in a distributed manner with purely local information and yet provide near optimal coverage. We appropriately formulate this coverage problem as a coverage game and prove that the optimal solution is a pure Nash equilibrium. Then, we design synchronous and asynchronous algorithms, which converge to pure Nash equilibria. Moreover, we analyze the optimality and complexity of pure Nash equilibria in the coverage game. We prove that, the ratio between the optimal coverage and the worst case Nash equilibrium coverage, is upper bounded by 2 ? 1 m+1 (m is the maximum number of nodes, which cover any point, in the Nash equilibrium solution s*). We prove that finding pure Nash equilibria in the general coverage game is PLS-complete, i.e. ?as hard as that of finding a local optimum in any local search problem with efficient computable neighbors?. Finally, via extensive simulations, we show that, the Nash equilibria coverage performance is very close to the optimal coverage and the convergence speed is sublinear. Even under the noisy environment, our algorithms can still converge to the pure Nash equilibria.     

Dynamic theoretic proactive caching placement game for energy saving in H‐CRAN

Edge caching is an effective feature of the next 5G network to guarantee the availability of the service content and a reduced time response for the user. However, the placement of the cache content remains an issue to fully take advantage of edge caching. In this paper, we address the proactive caching problem in Heterogeneous Cloud Radio Access Network (H‐CRAN) from a game theoretic point of view. The problem is formulated as a bargaining game where the remote radio heads (RRHs) dynamically negotiate and decide which content to cache in which RRH under energy saving and cache capacity constraints. The Pareto optimal equilibrium is proved for the cooperative game by the iterative Nash bargaining algorithm. We compare between cooperative and noncooperative proactive caching games and demonstrate how the selfishness of different players can affect the overall system performance. We also showed that our cooperative proactive caching game improves the energy consumption of 40% as compared with noncooperative game and of 68% to no‐game strategy. Moreover, the number of satisfied requests at the RRHs with the proposed cooperative proactive caching scheme is significantly increased.     

Joint random access and power control game in ad hoc networks with noncooperative users

We consider a distributed joint random access and power control scheme for interference management in wireless ad hoc networks. To derive decentralized solutions that do not require any cooperation among the users, we formulate this problem as noncooperative joint random access and power control game, in which each user minimizes its average transmission cost with a given rate constraint. Using supermodular game theory, the existence and uniqueness of Nash equilibrium are established. Furthermore, we present an asynchronous distributed algorithm to compute the solution of the game based on myopic best response updates, which converges to Nash equilibrium globally. Finally, a link admission algorithm is carried out to guarantee the reliability of the active users. Performance evaluations via simulations show that the game-theoretical based cross-layer design achieves high performance in terms of energy consumption and network stability.     

Noncooperative waveform adaptation games in multiuser wireless communications

This article provided a survey of waveform adaptation algorithms for multiuser wireless communications based on noncooperative game theory. Emphasis has been given to the problem of spreading code optimization in CDMA systems, a research topic that has attracted the interest of many researchers for years, and some space has also been devoted to other applications of waveform adaptation algorithms, such as beamforming in multiantenna multiuser communications and waveform selection in cognitive radio networks. For these three research tracks we have reviewed the principal results pertaining to the issue of noncooperative waveform adaptation, and some open research problems have been discussed. We believe that, given the rapid pace at which wireless communications have been developing, waveform adaptation will play a key role in the future to enhance the performance of increasingly highly loaded wireless data networks.     

The MIMO Iterative Waterfilling Algorithm

This paper considers the noncooperative maximization of mutual information in the vector Gaussian interference channel in a fully distributed fashion via game theory. This problem has been widely studied in a number of works during the past decade for frequency-selective channels, and recently for the more general multiple-input multiple-output (MIMO) case, for which the state-of-the art results are valid only for nonsingular square channel matrices. Surprisingly, these results do not hold true when the channel matrices are rectangular and/or rank deficient matrices. The goal of this paper is to provide a complete characterization of the MIMO game for arbitrary channel matrices, in terms of conditions guaranteeing both the uniqueness of the Nash equilibrium and the convergence of asynchronous distributed iterative waterfilling algorithms. Our analysis hinges on new technical intermediate results, such as a new expression for the MIMO waterfilling projection valid (also) for singular matrices, a mean-value theorem for complex matrix-valued functions, and a general contraction theorem for the multiuser MIMO watefilling mapping valid for arbitrary channel matrices. The quite surprising result is that uniqueness/convergence conditions in the case of tall (possibly singular) channel matrices are more restrictive than those required in the case of (full rank) fat channel matrices. We also propose a modified game and algorithm with milder conditions for the uniqueness of the equilibrium and convergence, and virtually the same performance (in terms of Nash equilibria) of the original game.     

Efficient power control via pricing in wireless data networks

A major challenge in the operation of wireless communications systems is the efficient use of radio resources. One important component of radio resource management is power control, which has been studied extensively in the context of voice communications. With the increasing demand for wireless data services, it is necessary to establish power control algorithms for information sources other than voice. We present a power control solution for wireless data in the analytical setting of a game theoretic framework. In this context, the quality of service (QoS) a wireless terminal receives is referred to as the utility and distributed power control is a noncooperative power control game where users maximize their utility. The outcome of the game results in a Nash (1951) equilibrium that is inefficient. We introduce pricing of transmit powers in order to obtain Pareto improvement of the noncooperative power control game, i.e., to obtain improvements in user utilities relative to the case with no pricing. Specifically, we consider a pricing function that is a linear function of the transmit power. The simplicity of the pricing function allows a distributed implementation where the price can be broadcast by the base station to all the terminals. We see that pricing is especially helpful in a heavily loaded system     

CR系统中基于微分博弈的功率控制算法

该文针对认知无线电系统动态性的特点,将微分博弈理论应用在认知无线电系统的功率控制中,建立了功率控制的非合作微分博弈模型,提出了一种基于微分博弈的分布式非合作功率控制算法。该算法在满足认知用户平均功率门限和QoS需求的基础上,实现了分布式动态功率控制,获得了反馈纳什均衡解析解。仿真结果表明,该算法可有效控制各认知用户的发射功率,增加系统吞吐量,提高系统性能。     

Nash equilibria of packet forwarding strategies in wireless ad hoc networks

In self-organizing ad hoc networks, all the networking functions rely on the contribution of the participants. As a basic example, nodes have to forward packets for each other in order to enable multihop communication. In recent years, incentive mechanisms have been proposed to give nodes incentive to cooperate, especially in packet forwarding. However, the need for these mechanisms was not formally justified. In this paper, we address the problem of whether cooperation can exist without incentive mechanisms. We propose a model,based on game theory and graph theory to investigate equilibrium conditions of packet forwarding strategies. We prove theorems about the equilibrium conditions for both cooperative and noncooperative strategies. We perform simulations to estimate the probability that the conditions for a cooperative equilibrium hold in randomly generated network scenarios.. As the problem is involved, we deliberately restrict ourselves to a static configuration. We conclude that in static ad hoc networks where the relationships between the nodes are likely to be stab le-cooperation needs to be encouraged.     

CDMA Uplink Power Control as a Noncooperative Game

We present a game-theoretic treatment of distributed power control in CDMA wireless systems. We make use of the conceptual framework of noncooperative game theory to obtain a distributed and market-based control mechanism. Thus, we address not only the power control problem, but also pricing and allocation of a single resource among several users. A cost function is introduced as the difference between the pricing and utility functions, and the existence of a unique Nash equilibrium is established. In addition, two update algorithms, namely, parallel update and random update, are shown to be globally stable under specific conditions. Convergence properties and robustness of each algorithm are also studied through extensive simulations.     

A game theoretic approach for power optimization during behavioral synthesis

In this paper, we describe a new methodology based on game theory for minimizing the average power of a circuit during scheduling and binding in behavioral synthesis. The problems are formulated as auction-based noncooperative finite games for which solutions are proposed based on the Nash equilibrium. In the scheduling algorithm, a first-price sealed-bid auction approach is used while, for the binding algorithm, each functional unit in the datapath is modeled as a player bidding for executing an operation with the estimated power consumption as the bid. Further, the techniques of functional unit sharing, path balancing, and register assignment are incorporated within the binding algorithm for power reduction. The combined scheduling and binding algorithm is formulated as a single noncooperative auction game with the functional units in the datapath modeled as players bidding for executing the operation in a particular control cycle. The proposed algorithms yield power reduction without any increase in area overhead and only a slight increase in the latency for some of the benchmark circuits. Experimental results indicate that the proposed game theoretic solution for binding yields an improvement of 13.9% over the linear programming (LP) method, while the scheduling and the combined scheduling and binding algorithms yield average improvements of 6.3% and 11.8%, respectively, over the integer-linear programming (ILP) approach.     

Inefficient Noncooperation in Networking Games of Common-Pool Resources

We study in this paper a noncooperative approach for sharing resources of a common pool among users, wherein each user strives to maximize its own utility. The optimality notion is then a Nash equilibrium. First, we present a general framework of systems wherein a Nash equilibrium is Pareto inefficient, which are similar to the `tragedy of the commons? in economics. As examples that fit in the above framework, we consider noncooperative flow-control problems in communication networks where each user decides its throughput to optimize its own utility. As such a utility, we first consider the power which is defined as the throughput divided by the expected end-to-end packet delay, and then consider another utility of additive costs. For both utilities, we establish the non-efficiency of the Nash equilibria.     

PSO-optimized Pareto and Nash equilibrium gaming-based power allocation technique for multistatic radar network

At present, multiple input multiple output radars offer accurate target detection and better target parameter estimation with higher resolution in high-speed wireless communication systems. This study focuses primarily on power allocation to improve the performance of radars owing to the sparsity of targets in the spatial velocity domain. First, the radars are clustered using the kernel fuzzy C-means algorithm. Next, cooperative and noncooperative clusters are extracted based on the distance measured using the kernel fuzzy C-means algorithm. The power is allocated to cooperative clusters using the Pareto optimality particle swarm optimization algorithm. In addition, the Nash equilibrium particle swarm optimization algorithm is used for allocating power in the noncooperative clusters. The process of allocating power to cooperative and noncooperative clusters reduces the overall transmission power of the radars. In the experimental section, the proposed method obtained the power consumption of 0.014 to 0.0119 at K = 2, M = 3 and K = 2, M = 3, which is better compared to the existing methodologies—generalized Nash game and cooperative and noncooperative game theory.     

基于博弈理论的Internet QoS评估的研究

Internet QoS(服务质量)评估是多学科领域的研究问题,本文从博弈理论的视角,基于多项罗吉特(MNL)模型提出了综合考虑服务质量指标和价格因素的Internet QoS评估机制。采用MNL建模用户的选择行为,同时将各个业务类表示为相对独立的竞争实体,每个业务类最大化自己的效用。通过基于非协作博弈理论的分析,论证了各个业务类的QoS指标和价格之间存在均衡,并通过数值分析进行了验证。