With the widespread adoption of internet-of-things (IoT) devices capable of supporting numerous intelligent applications, the demand for computational power has surged dramatically. Multi-access edge computing (MEC) technology is a promising solution to assist the often power-constrained IoT devices by providing additional computing resources for time-sensitive tasks. In this paper, we consider the problem of optimal task offloading in MEC systems with due consideration of the timeliness and scalability issues under two scenarios of equitable and priority access to the edge server (ES). In the first scenario, we consider a MEC system consisting of$N$devices assisted by one ES, where the devices can split task execution between a local processor and the ES, withequitable accessto the ES. In the second scenario, we consider a MEC system consisting of one primary user,$N$secondary users and one ES. The primary user haspriority accessto the ES while the secondary users haveequitable accessto the ES amongst themselves. In both scenarios, due to the power consumption associated with utilizing the local resource and task offloading, the devices must optimize their actions. Additionally, since the ES is a shared resource, other users' offloading activity serves to increase latency incurred by each user. We thus model both scenarios using alarge usernon-cooperative game framework. However, the presence of a large number of users makes it nearly impossible to compute the equilibrium offloading policies for each user, which would require a significant communication overhead to exchange information with each other. Thus, to alleviate such scalability issues, we invoke the paradigm of mean-field games (MFGs) to design completely distributed low complexity algorithms for the computation of approximate Nash equilibrium policies for each user based on only their local information. Further, by leveraging the novel age of information (AoI) metric, we study the trade-offs between increasing information freshness and reducing power consumption for each user. Using numerical evaluations, we show that our approach can recover the offloading trends displayed under centralized solutions, and provide additional insights into the results obtained.

Emerging 6G wireless systems suffer severe performance degradation in challenging environments like high-speed trains traversing dense urban corridors and Unmanned Aerial Vehicles (UAVs) links over mountainous terrain. These scenarios exhibit non-Gaussian, non-stationary channels with heavy-tailed fading and abrupt signal fluctuations. To address these challenges, this paper proposes a novel wireless channel model based on symmetric α-stable Lévy processes, thereby enabling continuous-time state-space characterization of both long-term and short-term fading. Building on this model, a generalized optimal control framework is developed via a fractional Hamilton-Jacobi-Bellman (HJB) equation that incorporates the Riesz fractional operator to capture non-local spatial effects and memory-dependent dynamics. The existence and uniqueness of viscosity solutions to the fractional HJB equation are rigorously established, thus ensuring the theoretical validity of the proposed control formulation. Numerical simulations conducted in a multi-cell, multi-user downlink setting demonstrate the effectiveness of the fractional HJB-based strategy in optimizing transmission power under heavy-tailed co-channel and multi-user interference.

In this work, we study $\gamma$-discounted infinite-horizon tabular Markov decision processes (MDPs) and introduce a framework called dynamic policy gradient (DynPG). The framework directly integrates dynamic programming with (any) policy gradient method, explicitly leveraging the Markovian property of the environment. DynPG dynamically adjusts the problem horizon during training, decomposing the original infinite-horizon MDP into a sequence of contextual bandit problems. By iteratively solving these contextual bandits, DynPG converges to the stationary optimal policy of the infinite-horizon MDP. To demonstrate the power of DynPG, we establish its non-asymptotic global convergence rate under the tabular softmax parametrization, focusing on the dependencies on salient but essential parameters of the MDP. By combining classical arguments from dynamic programming with more recent convergence arguments of policy gradient schemes, we prove that softmax DynPG scales polynomially in the effective horizon $(1-\gamma)^{-1}$. Our findings contrast recent exponential lower bound examples for vanilla policy gradient.

We study the sequential decision making problem of maximizing the expected total reward while satisfying a constraint on the expected total utility. We employ the natural policy gradient method to solve the discounted infinite-horizon optimal control problem for Constrained Markov Decision Processes (constrained MDPs). Specifically, we propose a new Natural Policy Gradient Primal-Dual (NPG-PD) method that updates the primal variable via natural policy gradient ascent and the dual variable via projected subgradient descent. Although the underlying maximization involves a nonconcave objective function and a nonconvex constraint set, under the softmax policy parametrization, we prove that our method achieves global convergence with sublinear rates regarding both the optimality gap and the constraint violation. Such convergence is independent of the size of the state-action space, i.e., it is~dimension-free. Furthermore, for log-linear and general smooth policy parametrizations, we establish sublinear convergence rates up to a function approximation error caused by restricted policy parametrization. We also provide convergence and finite-sample complexity guarantees for two sample-based NPG-PD algorithms. We use a set of computational experiments to showcase the effectiveness of our approach.

We consider an information update system on a gossip network, where a source node encodes information intontotal keys such that any subset of at leastk+ 1 keys can fully reconstruct the original information. This encoding process follows the principles of ak-out-of-nthreshold system. The encoded updates are then disseminated across the network through peer-to-peer communication. We have two different types of nodes in a network: subscriber nodes, which receive a unique key from the source node for every status update instantaneously, and nonsubscriber nodes, which receive a unique key for an update only if the node is selected by the source, and this selection is renewed for each update. For the message structure between nodes, we consider two different schemes: a memory scheme (in which the nodes keep the source’s current and previous encrypted messages) and a memoryless scheme (in which the nodes are allowed to only keep the source’s current message). We measure thetimelinessof information updates by using a recent performance metric called, the version age of information. We present explicit formulas for the time average AoI in a scalable homogeneous network as functions of the number of subscriber nodes under a memoryless scheme. Additionally, we provide strict lower and upper bounds for the time average AoI under a memory scheme.

We consider a communication system consisting of a server that tracks and publishes updates about a time-varying data source or event, and a gossip network of users interested in closely tracking the event. The timeliness of the information is measured through the version age of information. The users wish to have their expected version ages remain below a threshold, and have the option to either rely on gossip from their neighbors or subscribe to the server directly to follow updates about the event if the former option does not meet the timeliness requirements. The server wishes to maximize its profit by increasing the number of subscribers and reducing costs associated with the frequent sampling of the event. We model the problem setup as a Stackelberg game between the server and the users, where the server commits to a frequency of sampling the event, and the users make decisions on whether to subscribe or not. As an initial work, we focus on directed networks with unidirectional flow of information and obtain the optimal equilibrium strategies for all the players. We provide simulation results to confirm the theoretical findings and provide additional insights.

Most existing stochastic models on age of information (AoI) focus on a single shared server serving status update packets from N > 1 sources where each packet update stream is Poisson, i.e., single-hop scenario. In the current work, we study a two-hop edge computing system for which status updates from the information sources are still Poisson but they are not immediately available at the shared edge server, but instead they need to first receive service from a transmission server dedicated to each source. For exponentially distributed and heterogeneous service times for both the dedicated servers and the edge server, and bufferless preemptive resource management, we develop an analytical model using absorbing Markov chains (AMC) for obtaining the distribution of AoI for any source in the system. Moreover, for a given tagged source, the traffic arriving at the shared server from the N - 1 un-tagged sources, namely the interference traffic, is not Poisson any more, but is instead a Markov modulated Poisson process (MMPP) whose state space grows exponentially with N. Therefore, we propose to employ a model reduction technique that approximates the behavior of the MMPP interference traffic with two states only, making it possible to approximately obtain the AoI statistics even for a very large number of sources. Numerical examples are presented to validate the proposed exact and approximate models.

We consider online reinforcement learning in Mean-Field Games (MFGs). Unlike traditional approaches, we alleviate the need for a mean-field oracle by developing an algorithm that approximates the Mean-Field Equilibrium (MFE) using the single sample path of the generic agent. We call this Sandbox Learning, as it can be used as a warm-start for any agent learning in a multi-agent non-cooperative setting. We adopt a two time-scale approach in which an online fixed-point recursion for the mean-field operates on a slower time-scale, in tandem with a control policy update on a faster time-scale for the generic agent. Given that the underlying Markov Decision Process (MDP) of the agent is communicating, we provide finite sample convergence guarantees in terms of convergence of the mean-field and control policy to the mean-field equilibrium. The sample complexity of the Sandbox learning algorithm is $O(\epsilon^{-4})$ where $\epsilon$ is the MFE approximation error. This is similar to works which assume access to oracle. Finally, we empirically demonstrate the effectiveness of the sandbox learning algorithm in diverse scenarios, including those where the MDP does not necessarily have a single communicating class.

Multi-agent reinforcement learning (MARL) has primarily focused on solving a single task in isolation, while in practice the environment is often evolving, leaving many related tasks to be solved. In this paper, we investigate the benefits of meta-learning in solving multiple MARL tasks collectively. We establish the first line of theoretical results for meta-learning in a wide range of fundamental MARL settings, including learning Nash equilibria in two-player zero-sum Markov games and Markov potential games, as well as learning coarse correlated equilibria in general-sum Markov games. Under natural notions of task similarity, we show that meta-learning achieves provable sharper convergence to various game-theoretical solution concepts than learning each task separately. As an important intermediate step, we develop multiple MARL algorithms with initialization-dependent convergence guarantees. Such algorithms integrate optimistic policy mirror descents with stage-based value updates, and their refined convergence guarantees (nearly) recover the best known results even when a good initialization is unknown. To our best knowledge, such results are also new and might be of independent interest. We further provide numerical simulations to corroborate our theoretical findings.

Model-based reinforcement learning (RL), which finds an optimal policy after establishing an empirical model, has long been recognized as one of the cornerstones of RL. It is especially suitable for multi-agent RL (MARL), as it naturally decouples the learning and the planning phases, and avoids the non-stationarity problem when all agents are improving their policies simultaneously. Though intuitive and widely-used, the sample complexity of model-based MARL algorithms has not been fully investigated. In this paper, we aim to ad- dress the fundamental question about its sample complexity. We study arguably the most basic MARL setting: two-player discounted zero-sum Markov games, given only access to a generative model. We show that model-based MARL achieves a sample complexity of Oe(|S||A||B|(1 − γ)−3ε−2) for finding the Nash equilibrium (NE) value up to some ε error, and the ε-NE policies with a smooth planning oracle, where γ is the discount factor, and S,A,B denote the state space, and the action spaces for the two agents. We further show that such a sample bound is minimax-optimal (up to logarithmic factors) if the algorithm is reward-agnostic, where the algorithm queries state transition samples without reward knowledge, by establishing a matching lower bound. This is in contrast to the usual reward- aware setting, where the sample complexity lower bound is Ωe(|S|(|A| + |B|)(1 − γ)−3ε−2), and this model-based approach is near-optimal with only a gap on the |A|, |B| dependence. Our results not only illustrate the sample-efficiency of this basic model-based MARL approach, but also elaborate on the fundamental tradeoff between its power (easily handling the reward-agnostic case) and limitation (less adaptive and suboptimal in |A|, |B|), which particularly arises in the multi-agent context.

Distributed machine learning is envisioned as the bedrock of future intelligent networks, where agents exchange information with each other to train models collaboratively without uploading data to a central processor. Despite its broad applicability, a downside of distributed learning is the need for iterative information exchange between agents, which may lead to high communication overhead unaffordable in many practical systems with limited communication resources. To resolve this communication bottleneck, we need to devise communication-efficient distributed learning algorithms and protocols that can reduce the communication cost and simultaneously achieve satisfactory learning/optimization performance. Accomplishing this goal necessitates synergistic techniques from a diverse set of fields, including optimization, machine learning, wireless communications, game theory, and network/graph theory. This Special Issue is dedicated to communication-efficient distributed learning from multiple perspectives, including fundamental theories, algorithm design and analysis, and practical considerations.

Distributed learning is envisioned as the bedrock of next-generation intelligent networks, where intelligent agents, such as mobile devices, robots, and sensors, exchange information with each other or a parameter server to train machine learning models collaboratively without uploading raw data to a central entity for centralized processing. By utilizing the computation/communication capability of individual agents, the distributed learning paradigm can mitigate the burden at central processors and help preserve data privacy of users. Despite its promising applications, a downside of distributed learning is its need for iterative information exchange over wireless channels, which may lead to high communication overhead unaffordable in many practical systems with limited radio resources such as energy and bandwidth. To overcome this communication bottleneck, there is an urgent need for the development of communication-efficient distributed learning algorithms capable of reducing the communication cost and achieving satisfactory learning/optimization performance simultaneously. In this paper, we present a comprehensive survey of prevailing methodologies for communication-efficient distributed learning, including reduction of the number of communications, compression and quantization of the exchanged information, radio resource management for efficient learning, and game-theoretic mechanisms incentivizing user participation. We also point out potential directions for future research to further enhance the communication efficiency of distributed learning in various scenarios.

Serverless Function-as-a-Service (FaaS) offers improved programmability for customers, yet it is not server-"less" and comes at the cost of more complex infrastructure management (e.g., resource provisioning and scheduling) for cloud providers. To maintain service-level objectives (SLOs) and improve resource utilization efficiency, recent research has been focused on applying online learning algorithms such as reinforcement learning (RL) to manage resources. Despite the initial success of applying RL, we first show in this paper that the state-of-the-art single-agent RL algorithm (S-RL) suffers up to 4.8x higher p99 function latency degradation on multi-tenant serverless FaaS platforms compared to isolated environments and is unable to converge during training. We then design and implement a scalable and incremental multi-agent RL framework based on Proximal Policy Optimization (SIMPPO). Our experiments demonstrate that in multi-tenant environments, SIMPPO enables each RL agent to efficiently converge during training and provides online function latency performance comparable to that of S-RL trained in isolation with minor degradation (<9.2%). In addition, SIMPPO reduces the p99 function latency by 4.5x compared to S-RL in multi-tenant cases.

Multi-agent reinforcement learning (MARL) algorithms often suffer from an exponential sample complexity dependence on the number of agents, a phenomenon known as the curse of multiagents. We address this challenge by investigating sample-efficient model-free algorithms in decentralized MARL, and aim to improve existing algorithms along this line. For learning (coarse) correlated equilibria in general-sum Markov games, we propose stage-based V-learning algorithms that significantly simplify the algorithmic design and analysis of recent works, and circumvent a rather complicated no-weighted-regret bandit subroutine. For learning Nash equilibria in Markov potential games, we propose an independent policy gradient algorithm with a decentralized momentum-based variance reduction technique. All our algorithms are decentralized in that each agent can make decisions based on only its local information. Neither communication nor centralized coordination is required during learning, leading to a natural generalization to a large number of agents. Finally, we provide numerical simulations to corroborate our theoretical findings.

We consider information dissemination over a network of gossiping agents (nodes). In this model, a source keeps the most up-to-date information about a time-varying binary state of the world, and n receiver nodes want to follow the information at the source as accurately as possible. When the information at the source changes, the source first sends updates to a subset of m≤n nodes. After that, the nodes share their local information during the gossiping period to disseminate the information further. The nodes then estimate the information at the source using the majority rule at the end of the gossiping period. To analyze information dissemination, we introduce a new error metric to find the average percentage of nodes that can accurately obtain the most up-to-date information at the source. We characterize the equations necessary to obtain the steady-state distribution for the average error. Through numerical results, we first show that when the source’s transmission capacity m is limited, gossiping can be harmful as it causes incorrect information to disseminate. We then find the optimal gossip rates to minimize the average error for a fixed m.

This paper analyzes the fundamental limit of the strategic semantic communication problem in which a transmitter obtains a limited number of indirect observations of an intrinsic semantic information source and can then influence the receiver’s decoding by sending a limited number of messages over an imperfect channel. The transmitter and the receiver can have different distortion measures and can make rational decisions about their encoding and decoding strategies, respectively. The decoder can also have some side information (e.g., background knowledge and/or information obtained from previous communications) about the semantic source to assist its interpretation of the semantic information. We focus particularly on the case that the transmitter can commit to an encoding strategy and study the impact of the strategic decision making on the rate distortion of semantic communication. Three equilibrium solution concepts including the optimal Stackelberg equilibrium, robust Stackelberg equilibrium, as well as Nash equilibrium are studied and compared. The optimal encoding and decoding strategy profiles under various equilibrium solutions are derived. We prove that committing to an encoding strategy cannot always bring benefit to the encoder. We provide a feasible condition under which committing to an encoding strategy can always reduce the distortion of semantic communication. We consider an example with a dictionary-based semantic information source to verify our observation.

Reinforcement learning (RL) has gained increasing popularity for resource management in cloud services such as serverless computing. As self-interested users compete for shared resources in a cluster, the multi-tenancy nature of serverless platforms necessitates multi-agent reinforcement learning (MARL) solutions, which often suffer from severe scalability issues. In this paper, we propose a mean-field game (MFG) approach to cloud resource management that is scalable to a large number of users and applications and incorporates function approximation to deal with the large state-action spaces in real-world serverless platforms. Specifically, we present an online natural actor-critic algorithm for learning in MFGs compatible with various forms of function approximation. We theoretically establish its finite-time convergence to the regularized Nash equilibrium under linear function approximation and softmax parameterization. We further implement our algorithm using both linear and neural-network function approximations, and evaluate our solution on an open-source serverless platform, OpenWhisk, with real-world workloads from production traces. Experimental results demonstrate that our approach is scalable to a large number of users and significantly outperforms various baselines in terms of function latency and resource utilization efficiency.

This paper deals with distributed reinforcement learning problems with safety constraints. In particular, we consider that a team of agents cooperate in a shared environment, where each agent has its individual reward function and safety constraints that involve all agents' joint actions. As such, the agents aim to maximize the team-average long-term return, subject to all the safety constraints. More intriguingly, no central controller is assumed to coordinate the agents, and both the rewards and constraints are only known to each agent locally/privately. Instead, the agents are connected by a peer-to-peer communication network to share information with their neighbors. In this work, we first formulate this problem as a distributed constrained Markov decision process (D-CMDP) with networked agents. Then, we propose a decentralized policy gradient (PG) method, Safe Dec-PG, to perform policy optimization based on this D-CMDP model over a network. Convergence guarantees, together with numerical results, showcase the superiority of the proposed algorithm. To the best of our knowledge, this is the first decentralized PG algorithm that accounts for the coupled safety constraints with a quantifiable convergence rate in multi-agent reinforcement learning. Finally, we emphasize that our algorithm is also novel in solving a class of decentralized stochastic nonconvex-concave minimax optimization problems, where both the algorithm design and corresponding theoretical analysis are of independent interest.

We consider model-free reinforcement learning (RL) in non-stationary Markov decision processes. Both the reward functions and the state transition functions are allowed to vary arbitrarily over time as long as their cumulative variations do not exceed certain variation budgets. We propose Restarted Q-Learning with Upper Confidence Bounds (RestartQ-UCB), the first model-free algorithm for non-stationary RL, and show that it outperforms existing solutions in terms of dynamic regret. Specifically, RestartQ-UCB with Freedman-type bonus terms achieves a dynamic regret bound of $\widetilde{O}(S^{\frac{1}{3}} A^{\frac{1}{3}} \Delta^{\frac{1}{3}} H T^{\frac{2}{3}})$, where $S$ and $A$ are the numbers of states and actions, respectively, $\Delta>0$ is the variation budget, $H$ is the number of time steps per episode, and $T$ is the total number of time steps. We further show that our algorithm is \emph{nearly optimal} by establishing an information-theoretical lower bound of $\Omega(S^{\frac{1}{3}} A^{\frac{1}{3}} \Delta^{\frac{1}{3}} H^{\frac{2}{3}} T^{\frac{2}{3}})$, the first lower bound in non-stationary RL. Numerical experiments validate the advantages of RestartQ-UCB in terms of both cumulative rewards and computational efficiency. We further demonstrate the power of our results in the context of multi-agent RL, where non-stationarity is a key challenge.

We study multi-agent reinforcement learning (MARL) in infinite-horizon discounted zero-sum Markov games. We focus on the practical but challenging setting of decentralized MARL, where agents make decisions without coordination by a centralized controller, but only based on their own payoffs and local actions executed. The agents need not observe the opponent's actions or payoffs, possibly being even oblivious to the presence of the opponent, nor be aware of the zero-sum structure of the underlying game, a setting also referred to as radically uncoupled in the literature of learning in games. In this paper, we develop a radically uncoupled Q-learning dynamics that is both rational and convergent: the learning dynamics converges to the best response to the opponent's strategy when the opponent follows an asymptotically stationary strategy; when both agents adopt the learning dynamics, they converge to the Nash equilibrium of the game. The key challenge in this decentralized setting is the non-stationarity of the environment from an agent's perspective, since both her own payoffs and the system evolution depend on the actions of other agents, and each agent adapts her policies simultaneously and independently. To address this issue, we develop a two-timescale learning dynamics where each agent updates her local Q-function and value function estimates concurrently, with the latter happening at a slower timescale.

Direct policy search serves as one of the workhorses in modern reinforcement learning (RL), and its applications in continuous control tasks have recently attracted increasing attention. In this work, we investigate the convergence theory of policy gradient (PG) methods for learning the linear risk-sensitive and robust controller. In particular, we develop PG methods that can be implemented in a derivative-free fashion by sampling system trajectories, and establish both global convergence and sample complexity results in the solutions of two fundamental settings in risk-sensitive and robust control: the finite-horizon linear exponential quadratic Gaussian, and the finite-horizon linear-quadratic disturbance attenuation problems. As a by-product, our results also provide the first sample complexity for the global convergence of PG methods on solving zero-sum linear-quadratic dynamic games, a nonconvex-nonconcave minimax optimization problem that serves as a baseline setting in multi-agent reinforcement learning (MARL) with continuous spaces. One feature of our algorithms is that during the learning phase, a certain level of robustness/risk-sensitivity of the controller is preserved, which we termed as the implicit regularization property, and is an essential requirement in safety-critical control systems.

Multi-agent reinforcement learning (MARL) has long been a significant research topic in both machine learning and control systems. Recent development of (single-agent) deep reinforcement learning has created a resurgence of interest in developing new MARL algorithms, especially those founded on theoretical analysis. In this paper, we review recent advances on a sub-area of this topic: decentralized MARL with networked agents. In this scenario, multiple agents perform sequential decision-making in a common environment, and without the coordination of any central controller, while being allowed to exchange information with their neighbors over a communication network. Such a setting finds broad applications in the control and operation of robots, unmanned vehicles, mobile sensor networks, and the smart grid. This review covers several of our research endeavors in this direction, as well as progress made by other researchers along the line. We hope that this review promotes additional research efforts in this exciting yet challenging area.

Web services integrate various components in the Internet of Things (IoT). In a Web service-based data-collection system with multiple smart sensor nodes periodically sampling and estimating the same unknown physical parameter of interest, the smart sensor nodes first submit their estimates to the Web server, and then, the server picking the one with the minimum error seems to be a practical way to arrive at a minimum error estimate (MEE). More submissions provide the Web server with more candidates to consider, which can maximize the probability of the server guaranteeing the MEE, while also leading to more network traffic. Therefore, how to make the optimal tradeoff between network traffic and sensing accuracy arises as an interesting problem. This article proposes a network traffic-dependent probability threshold policy within an intended underlying optimization-theoretical framework to address this problem. The policy is such that the smart sensor nodes submit their estimates and corresponding estimation errors (ECEEs) to the Web server within a tolerable network traffic threshold while maximizing the probability of the server delivering the MEE. Theoretical analysis, simulation, and field experiments document and illustrate its performance.Note to Practitioners—This article addresses the interesting tradeoff between sensing accuracy and network traffic demand in the Web service-based data-collection system that operates in some remote areas with limited network traffic. It helps to improve the operation efficiency of the Internet-of-Things (IoT) systems that employ Web service technology to enable the Web server to deliver minimum error estimate with maximum probability while keeping the network traffic within a given range. Our simulation and experimental investigations show that the solution developed here outperforms existing solutions.

We study the economic interactions among sellers and buyers in online markets. In such markets, buyers have limited information about the product quality, but can observe the sellers' reputations which depend on their past transaction histories and ratings from past buyers. Sellers compete in the same market through pricing, while considering the impact of their heterogeneous reputations. We consider sellers with limited as well as unlimited capacities, which correspond to different practical market scenarios. In the unlimited seller capacity scenario, buyers prefer the seller with the highest reputation-price ratio. If the gap between the highest and second highest seller reputation levels is large enough, then the highest reputation seller dominates the market as a monopoly. If sellers' reputation levels are relatively close to each other, then those sellers with relatively high reputations will survive at the equilibrium, while the remaining relatively low reputation sellers will get zero market share. In the limited seller capacity scenario, we further consider two different cases. If each seller can only serve one buyer, then it is possible for sellers to set their monopoly prices at the equilibrium while all sellers gain positive market shares; if each seller can serve multiple buyers, then it is possible for sellers to set maximum prices at the equilibrium. Simulation results show that the dynamics of reputations and prices in the longer-term interactions will converge to stable states, and the initial buyer ratings of the sellers play the critical role in determining sellers' reputations and prices at the stable state.

This paper is concerned with the optimal control of rational expectations models in the general case of longer forward-looking time (d ≥ 2). The main contribution is the necessary and sufficient condition for the solvability of the finite-horizon problem. In particular, explicit characterizations of the optimal solution and the optimal cost are given in terms of difference equations. The key technique is to solve the forward and backward stochastic difference equations (FBSDEs) obtained by the stochastic maximum principle.

We study sequential decision-making problems in which each agent aims to maximize the expected total reward while satisfying a constraint on the expected total utility. We employ the natural policy gradient method to solve the discounted infinite-horizon Constrained Markov Decision Processes (CMDPs) problem. Specifically, we propose a new Natural Policy Gradient Primal-Dual (NPG-PD) method for CMDPs which updates the primal variable via natural policy gradient ascent and the dual variable via projected sub-gradient descent. Even though the underlying maximization involves a nonconcave objective function and a nonconvex constraint set under the softmax policy parametrization, we prove that our method achieves global convergence with sublinear rates regarding both the optimality gap and the constraint violation. Such a convergence is independent of the size of the state-action space, i.e., it is~dimension-free. Furthermore, for the general smooth policy class, we establish sublinear rates of convergence regarding both the optimality gap and the constraint violation, up to a function approximation error caused by restricted policy parametrization. Finally, we show that two sample-based NPG-PD algorithms inherit such non-asymptotic convergence properties and provide finite-sample complexity guarantees. To the best of our knowledge, our work is the first to establish non-asymptotic convergence guarantees of policy-based primal-dual methods for solving infinite-horizon discounted CMDPs. We also provide computational results to demonstrate merits of our approach.

In this paper, we revisit and improve the convergence of policy gradient (PG), natural PG (NPG) methods, and their variance-reduced variants, under general smooth policy parametrizations. More specifically, with the Fisher information matrix of the policy being positive definite: i) we show that a state-of-the-art variance-reduced PG method, which has only been shown to converge to stationary points, converges to the globally optimal value up to some inherent function approximation error due to policy parametrization; ii) we show that NPG enjoys a lower sample complexity; iii) we propose SRVR-NPG, which incorporates variance-reduction into the NPG update. Our improvements follow from an observation that the convergence of (variance-reduced) PG and NPG methods can improve each other: the stationary convergence analysis of PG can be applied on NPG as well, and the global convergence analysis of NPG can help to establish the global convergence of (variance-reduced) PG methods. Our analysis carefully integrates the advantages of these two lines of works. Thanks to this improvement, we have also made variance-reduction for NPG possible for the first time, with both global convergence and an efficient finite-sample complexity.

Monte-Carlo planning, as exemplified by Monte-Carlo Tree Search (MCTS), has demonstrated remarkable performance in applications with finite spaces. In this paper, we consider Monte-Carlo planning in an environment with continuous state-action spaces, a much less understood problem with important applications in control and robotics. We introduce POLY-HOOT, an algorithm that augments MCTS with a continuous armed bandit strategy named Hierarchical Optimistic Optimization (HOO) (Bubeck et al., 2011). Specifically, we enhance HOO by using an appropriate polynomial, rather than logarithmic, bonus term in the upper confidence bounds. Such a polynomial bonus is motivated by its empirical successes in AlphaGo Zero (Silver et al., 2017b), as well as its significant role in achieving theoretical guarantees of finite space MCTS (Shah et al., 2019). We investigate, for the first time, the regret of the enhanced HOO algorithm in non-stationary bandit problems. Using this result as a building block, we establish non-asymptotic convergence guarantees for POLY-HOOT: the value estimate converges to an arbitrarily small neighborhood of the optimal value function at a polynomial rate. We further provide experimental results that corroborate our theoretical findings.

Reinforcement learning (RL) algorithms can fail to generalize due to the gap between the simulation and the real world. One standard remedy is to use robust adversarial RL (RARL) that accounts for this gap during the policy training, by modeling the gap as an adversary against the training agent. In this work, we reexamine the effectiveness of RARL under a fundamental robust control setting: the linear quadratic (LQ) case. We first observe that the popular RARL scheme that greedily alternates agents’ updates can easily destabilize the system. Motivated by this, we propose several other policy-based RARL algorithms whose convergence behaviors are then studied both empirically and theoretically. We find: i) the conventional RARL framework (Pinto et al., 2017) can learn a destabilizing policy if the initial policy does not enjoy the robust stability property against the adversary; and ii) with robustly stabilizing initializations, our proposed double-loop RARL algorithm provably converges to the global optimal cost while maintaining robust stability on-the-fly. We also examine the stability and convergence issues of other variants of policy-based RARL algorithms, and then discuss several ways to learn robustly stabilizing initializations. From a robust control perspective, we aim to provide some new and critical angles about RARL, by identifying and addressing the stability issues in this fundamental LQ setting in continuous control. Our results make an initial attempt toward better theoretical understandings of policy-based RARL, the core approach in Pinto et al., 2017.

Model-based reinforcement learning (RL), which finds an optimal policy using an empirical model, has long been recognized as one of the cornerstones of RL. It is especially suitable for multi-agent RL (MARL), as it naturally decouples the learning and the planning phases, and avoids the non-stationarity problem when all agents are improving their policies simultaneously using samples. Though intuitive and widely-used, the sample complexity of model-based MARL algorithms has been investigated relatively much less often. In this paper, we aim to address the fundamental open question about the sample complexity of model-based MARL. We study arguably the most basic MARL setting: two-player discounted zero-sum Markov games, given only access to a generative model of state transition. We show that model-based MARL achieves a sample complexity of $\tilde \cO(|\cS||\cA||\cB|(1-\gamma)^{-3}\epsilon^{-2})$ for finding the Nash equilibrium (NE) \emph{value} up to some $\epsilon$ error, and the $\epsilon$-NE \emph{policies}, where $\gamma$ is the discount factor, and $\cS,\cA,\cB$ denote the state space, and the action spaces for the two agents. We also show that this method is near-minimax optimal with a tight dependence on $1-\gamma$ and $|\cS|$ by providing a lower bound of $\Omega(|\cS|(|\cA|+|\cB|)(1-\gamma)^{-3}\epsilon^{-2})$. Our results justify the efficiency of this simple model-based approach in the multi-agent RL setting.

In this work, we study the problem of multi-agent reinforcement learning (MARL) with model uncertainty, which is referred to as robust MARL. This is naturally motivated by some multi-agent applications where each agent may not have perfectly accurate knowledge of the model, e.g., all the reward functions of other agents. Little a priori work on MARL has accounted for such uncertainties, neither in problem formulation nor in algorithm design. In contrast, we model the problem as a robust Markov game, where the goal of all agents is to find policies such that no agent has the incentive to deviate, i.e., reach some equilibrium point, which is also robust to the possible uncertainty of the MARL model. We first introduce the solution concept of robust Nash equilibrium in our setting, and develop a Q-learning algorithm to find such equilibrium policies, with convergence guarantees under certain conditions. In order to handle possibly enormous state-action spaces in practice, we then derive the policy gradients for robust MARL, and develop an actor-critic algorithm with function approximation. Our experiments demonstrate that the proposed algorithm outperforms several baseline MARL methods that do not account for the model uncertainty, in several standard but uncertain cooperative and competitive MARL environments.

In this paper, a novel mathematical framework is introduced for modeling and analyzing the cyber-physical security of time-critical UAV applications. A general UAV security network interdiction game is formulated to model interactions between a UAV operator and an interdictor, each of which can be benign or malicious. In this game, the interdictor chooses the optimal location(s) from which to target the drone system by interdicting the potential paths of the UAVs. Meanwhile, the UAV operator responds by finding an optimal path selection policy that enables its UAVs to evade attacks and minimize their mission completion time. New notions from cumulative prospect theory (PT) are incorporated into the game to capture the operator's and the interdictor's subjective valuations of mission completion times and perceptions of the risk levels facing the UAVs. The equilibrium of the game, with and without PT, is then analytically characterized and studied, while providing detailed derivations of mission completion times (and their expected values), PT valuations of both players (along with proofs of their convergence), and equilibrium points under different studied security regimes. Novel algorithms are then proposed to reach the game's equilibria under both PT and classical game theory. Simulation results show the properties of the equilibrium for both the rational and PT cases, highlighting the effects of bounded rationality on the interdictor's and the operator's strategies as well as mission completion times, and the way it can be exploited by a fully rational opponent.

In this paper, we propose a game theoretical adversarial intervention detection mechanism for reliable smart road signs. A future trend in intelligent transportation systems is “smart road signs” that incorporate smart codes (e.g., visible at infrared) on their surface to provide more detailed information to smart vehicles. Such smart codes make road sign classification problem aligned with communication settings more than conventional classification. This enables us to integrate well-established results in communication theory, e.g., error-correction methods, into road sign classification problem. Recently, vision-based road sign classification algorithms have been shown to be vulnerable against (even) small scale adversarial interventions that are imperceptible for humans. On the other hand, smart codes constructed via error-correction methods can lead to robustness against small scale intelligent or random perturbations on them. In the recognition of smart road signs, however, humans are out of the loop since they cannot see or interpret them. Therefore, there is no equivalent concept of imperceptible perturbations in order to achieve a comparable performance with humans. Robustness against small scale perturbations would not be sufficient since the attacker can attack more aggressively without such a constraint. Under a game theoretical solution concept, we seek to ensure certain measure of guarantees against even the worst case (intelligent) attackers that can perturb the signal even at large scale. We provide a randomized detection strategy based on the distance between the decoder output and the received input, i.e., error rate. Finally, we examine the performance of the proposed scheme over various scenarios.

In this paper, we address the challenges facing the adoption of client puzzles as a means to protect the TCP connection establishment channel from state exhaustion DDoS attacks. We model the problem of selecting the puzzle difficulties as a Stackelberg game with the server as the leader and the clients as the followers and obtain the equilibrium solution for the puzzle difficulty. We then present an implementation of client puzzles inside the TCP stack of the Linux 4.13.0 kernel. We evaluate the performance of our implementation and the obtained solution against a range of attacks through reproducible experiments on the DETER testbed. Our results show that client puzzles are effective at boosting the tolerance of the TCP handshake channel to state exhaustion DDoS attacks by rate limiting malicious attackers while allocating resources for legitimate clients.

We study the global convergence of policy optimization for finding the Nash equilibria (NE) in zero-sum linear quadratic (LQ) games. To this end, we first investigate the landscape of LQ games, viewing it as a nonconvex-nonconcave saddle-point problem in the policy space. Specifically, we show that despite its nonconvexity and nonconcavity, zero-sum LQ games have the property that the stationary point of the objective function with respect to the linear feedback control policies constitutes the NE of the game. Building upon this, we develop three projected nested-gradient methods that are guaranteed to converge to the NE of the game. Moreover, we show that all these algorithms enjoy both globally sublinear and locally linear convergence rates. Simulation results are also provided to illustrate the satisfactory convergence properties of the algorithms. To the best of our knowledge, this work appears to be the first one to investigate the optimization landscape of LQ games, and provably show the convergence of policy optimization methods to the NE. Our work serves as an initial step toward understanding the theoretical aspects of policy-based reinforcement learning algorithms for zero-sum Markov games in general.

Making decisions in the presence of a strategic opponent requires one to take into account the opponent’s ability to actively mask its intended objective. To describe such strategic situations, we introduce the non-cooperative inverse reinforcement learning (N-CIRL) formalism. The N-CIRL formalism consists of two agents with completely misaligned objectives, where only one of the agents knows the true objective function. Formally, we model the N-CIRL formalism as a zero-sum Markov game with one-sided incomplete information. Through interacting with the more informed player, the less informed player attempts to both infer and optimize the true objective function. As a result of the one-sided incomplete information, the multi-stage game can be decomposed into a sequence of single- stage games expressed by a recursive formula. Solving this recursive formula yields the value of the N-CIRL game and the more informed player’s equilibrium strategy. Another recursive formula, constructed by forming an auxiliary game, termed the dual game, yields the less informed player’s strategy. Building upon these two recursive formulas, we develop a computationally tractable algorithm to approximately solve for the equilibrium strategies. Finally, we demonstrate the benefits of our N-CIRL formalism over the existing multi-agent IRL formalism via extensive numerical simulation in a novel cyber security setting.

We propose a new information-driven intersection control to enhance the quality of transportation by using communication between vehicles and roadside units. The state-of-the-art solutions for intersection control only have access to the sensor data that is collected by vehicles or roadside units. However, congestion at intersections can have different impact on different drivers, and yet such an impact cannot be measured by sensors. An effective intersection control can consider such driver-exclusive differences based on the information reported by the drivers, which can substantially enhance the quality of transportation. However, such information is driver-exclusive, i.e., not verifiable easily, and therefore prone to be misreported strategically. We propose strategy-proof intersection control addressing such issues via a payment-based incentive-compatible mechanism. Particularly, vehicles at close proximity of the intersection report their driver-exclusive utility functions that they want to maximize (not necessarily truthfully), while the roadside unit seeks to maximize the sum of those utilities, i.e., social welfare, by scheduling intersection usage and charging each vehicle an amount of time-tokens corresponding to their impact on other drivers. This approach, based on the Vickrey-Clarke-Groove mechanism, guarantees truthful utility reporting by the vehicles and, correspondingly, maximizes the social welfare. The proposed scheme is universal such that it can be implemented based on various utility functions or intersection control constraints. We also provide a practical implementation to analyze the performance via numerical simulations.

An upcoming frontier for distributed computing might literally save lives in future military operations. In civilian scenarios, significant efficiencies were gained from interconnecting devices into networked services and applications that automate much of everyday life from smart homes to intelligent transportation. The ecosystem of such applications and services is collectively called the Internet of Things (IoT). Can similar benefits be gained in a military context by developing an IoT for the battlefield? This paper describes unique challenges in such a context as well as potential risks, mitigation strategies, and benefits.

We consider the fully decentralized multi-agent reinforcement learning (MARL) problem, where the agents are connected via a time-varying and possibly sparse communication network. Specifically, we assume that the reward functions of the agents might correspond to different tasks, and are only known to the corresponding agent. Moreover, each agent makes individual decisions based on both the information observed locally and the messages received from its neighbors over the network. To maximize the globally averaged return over the network, we propose two fully decentralized actor-critic algorithms, which are applicable to large-scale MARL problems in an online fashion. Convergence guarantees are provided when the value functions are approximated within the class of linear functions. Our work appears to be the first theoretical study of fully decentralized MARL algorithms for networked agents that use function approximation.

For Internet-based services, users' quality of service (QoS) depends on not only the available resource (capacity) but also the number of users who use the resource simultaneously (e.g., congestion effect). When a new Internet-based service provider first enters the market, there can be uncertainties regarding both the capacity and congestion, and hence the uncertainty of QoS. In this paper, we consider a participation-dependent social learning over the QoS through users' online reviews, where the QoS changes with the number of review participants. We study how such a learning process affects the provider's dynamic pricing strategy. With a simple two-period model, we analyze the strategic interactions between the provider and the users, and characterize the provider's optimal two-period dynamic pricing policy. Our results show that when the capacity is small or the users' prior QoS belief is high, the provider will choose a higher introductory price in the first period (than the price in the second period). This is in sharp contrast with the common practice of setting a lower introductory price to attract users (when congestion is not an issue). Furthermore, the learning process is beneficial to the provider with a large capacity.

In this paper, we study the effects of subjective biases on strategic information transmission (SIT) within a Stackelberg game setting, where a human transmitter (leader) communicates an encoded source message to a human receiver (follower) so that the receiver decodes back a desired version of the original source signal. We model human decisions using Rieger-Wang's prospect theory, which is an extension of traditional prospect theory to continuous decision spaces. Having found a closed-form expression for the receiver's best response strategy under any general setting, we consider two settings: Gaussian SIT games and exponential SIT games. While the Gaussian SIT games result in strategies that are independent of subjective biases of both the transmitter and the receiver, we show that the equilibrium strategies in exponential SIT games depend on the subjective biases of both the transmitter and the receiver. Numerical results are presented to illustrate results in both Gaussian and exponential settings.

The use of unmanned aerial vehicles (UAVs) as delivery systems of online goods is rapidly becoming a global norm, as corroborated by Amazon's “Prime Air” and Google's “Project Wing” projects. However, the real-world deployment of such drone delivery systems faces many cyber-physical security challenges. In this paper, a novel mathematical framework for analyzing and enhancing the security of drone delivery systems is introduced. In this regard, a zero-sum network interdiction game is formulated between a vendor, operating a drone delivery system, and a malicious attacker. In this game, the vendor seeks to find the optimal path that its UAV should follow, to deliver a purchase from the vendor's warehouse to a customer location, to minimize the delivery time. Meanwhile, an attacker seeks to choose an optimal location to interdict the potential paths of the UAVs, so as to inflict cyber or physical damage to it, thus, maximizing its delivery time. First, the Nash equilibrium point of this game is characterized. Then, to capture the subjective behavior of both the vendor and attacker, new notions from prospect theory are incorporated into the game. These notions allow capturing the vendor's and attacker's (i) subjective perception of attack success probabilities, and (ii) their disparate subjective valuations of the achieved delivery times relative to a certain target delivery time. Simulation results have shown that the subjective decision making of the vendor and attacker leads to adopting risky path selection strategies which inflict delays to the delivery, thus, yielding unexpected delivery times which surpass the target delivery time set by the vendor.

Next-generation networks will be characterized by three key features:heterogeneity, in terms of technologies and services,dynamics, in terms of rapidly varying environments and uncertainty, andsize, in terms of the numbers of users, nodes, and services. The emergence of such large-scale and decentralized heterogeneous networks operating under dynamic and uncertain environments imposes new challenges in the design, analysis, and optimization of networks. The past decade has witnessed a confluence among the disciplines of networks, games, and economics, which has necessitated novel mathematical tools and designs that can truly remove the boundaries between these disciplines. In this context, advancing game-theoretic models and tailoring them towards the optimization and operation of future networked systems become pressing needs for our research community. The main goal of this IEEE JSAC Special Issue on “Game Theory for Networks” is to collect cutting-edge contributions that address and show the latest developments in game-theoretic models for emerging networking applications. The response of the community to the call has been overwhelming. We received a total of 120 submissions. We want to thank all the authors who submitted their works to this Special Issue. After a strict and selective review process, we accepted 40 papers and decided to publish two issues. Papers were selected based on their appropriateness for and relevance to the Special Issue as well as their technical merits. Unfortunately, a number of interesting papers did not make the cut because of the criteria set forth above and also due to the constraints on the total page count in a JSAC Special Issue. We hope that such interesting papers will find other venues for publication.

This is the second part of the IEEE JSAC Special Issue on “Game Theory for Networks.” The response of the community to the call has been overwhelming. We received a total of 120 submissions. We want to thank all the authors who submitted their works to this Special Issue. After a strict and selective review process, we accepted 40 papers and decided to publish two issues, each of 20 papers. The first one was published in February 2017. The papers of this second issue cover a wide selection of topics as follows.

This paper analyzes the information disclosure problems originated in economics through the lens of information theory. Such problems are radically different from the conventional communication paradigms in information theory since they involve different objectives for the encoder and the decoder, which are aware of this mismatch and act accordingly. This leads, in our setting, to a hierarchical communication game, where the transmitter announces an encoding strategy with full commitment, and its distortion measure depends on a private information sequence whose realization is available at the transmitter. The receiver decides on its decoding strategy that minimizes its own distortion based on the announced encoding map and the statistics. Three problem settings are considered, focusing on the quadratic distortion measures, and jointly Gaussian source and private information: compression, communication, and the simple equilibrium conditions without any compression or communication. The equilibrium strategies and associated costs are characterized. The analysis is then extended to the receiver side information setting and the major changes in structure of optimal strategies are identified. Finally, an extension of the results to the broader context of decentralized stochastic control is presented.

We consider the static optimal sensor selection problem, where we optimally select d sensors among s possible sensors with d <; s. Under the assumption that the s sensors are mutually orthogonal to each other, we cast the optimal sensor selection problem as a linear integer program (LIP) that corresponds to minimization of the trace of the linear least-squares estimation error covariance. We show that even though general LIPs are NP-hard, our problem can be solved in polynomial time as a linear program; hence, it is not necessary to go for suboptimal solutions. This is due to the associated integral convex polyhedron constraint set followed by its total unimodularity property. We provide simulation results to demonstrate polynomial-time solvability of the corresponding problem with the orthogonality condition as well as additional sensor selection constraints.

This paper analyzes the fundamental limits of strategic communication in network settings. Strategic communication differs from the conventional communication paradigms in information theory since it involves different objectives for the encoder and the decoder, which are aware of this mismatch and act accordingly. This leads to a Stackelberg game where both agents commit to their mappings ex-ante. Building on our prior work on the point-to-point setting, this paper studies the compression and communication problems with the receiver and/or the transmitter side information setting. The equilibrium strategies and the associated costs are characterized for the Gaussian variables and quadratic cost functions. Several questions on the benefit of side information in source and joint source-channel coding in such strategic settings are analyzed. Our analysis has uncovered an interesting result on optimality of uncoded communication in strategic source-channel coding in the presence of receiver side information.

In this paper, a novel context-aware approach for resource allocation in two-tier wireless small cell networks (SCNs) is proposed. In particular, the SCN's users are divided into two types: frequent users, who are regular users of certain small cells, and occasional users, who are one-time or infrequent users of a particular small cell. Given such context information, each small cell base station (SCBS) aims to maximize the overall performance provided to its frequent users, while ensuring that occasional users are also well serviced. We formulate the problem as a noncooperative game in which the SCBSs are the players. The strategy of each SCBS is to choose a proper power allocation so as to optimize a utility function that captures the tradeoff between the users' quality-of-service gains and the costs in terms of resource expenditures. We provide a sufficient condition for the existence and uniqueness of a pure strategy Nash equilibrium for the game, and we show that this condition is independent of the number of users in the network. Simulation results show that the proposed context-aware resource allocation game yields significant performance gains, in terms of the average utility per SCBS, compared to conventional techniques such as proportional fair allocation and sum-rate maximization.

We provide two novel adaptive-rate compressive sensing (CS) strategies for sparse, time-varying signals using side information. The first method uses extra cross-validation measurements, and the second one exploits extra low-resolution measurements. Unlike the majority of current CS techniques, we do not assume that we know an upper bound on the number of significant coefficients that comprises the images in the video sequence. Instead, we use the side information to predict the number of significant coefficients in the signal at the next time instant. We develop our techniques in the specific context of background subtraction using a spatially multiplexing CS camera such as the single-pixel camera. For each image in the video sequence, the proposed techniques specify a fixed number of CS measurements to acquire and adjust this quantity from image to image. We experimentally validate the proposed methods on real surveillance video sequences.

This paper considers the problem of optimal zero-delay jamming over an additive noise channel. Building on a sequence of recent results on conditions for linearity of optimal estimation, and of optimal mappings in source-channel coding, the saddle-point solution to the jamming problem is derived for general sources and channels, without recourse to Gaussianity assumptions. The linearity conditions are shown to play a pivotal role in jamming, in the sense that the optimal jamming strategy is to effectively force both the transmitter and the receiver to default to linear mappings, i.e., the jammer ensures, whenever possible, that the transmitter and the receiver cannot benefit from non-linear strategies. This result is shown to subsume the known result for Gaussian source and channel. The conditions and general settings where such unbeatable strategy can indeed be achieved by the jammer are analyzed. Moreover, a numerical procedure is provided to approximate the optimal jamming strategy in the remaining (source-channel) cases where the jammer cannot impose linearity on the transmitter and the receiver. Next, the analysis is extended to vector sources and channels. This extension involves a new aspect of optimization: the allocation of available transmit and jamming power over source and channel components. Similar to the scalar setting, the saddle-point solution is derived using the linearity conditions in vector spaces. The optimal power allocation strategies for the jammer and the transmitter have an intuitive interpretation as the jammer allocates power according to water-filling over the channel eigenvalues, while the transmitter performs water-pouring (reverse water-filling) over the source eigenvalues.

In this paper, we investigate the problem of placing small cell base stations (SCBSs) in adversarial heterogeneous wireless networks. We consider a continuum of wireless users facing potential eavesdropping and jamming attacks. For each such attack, we first propose a suitable utility function for the wireless users. Then, we propose a novel optimal placement algorithm for finding the optimal locations of the SCBSs given the underlying security considerations. In eavesdropping scenarios, we consider the prospective eavesdroppers to be spread over a given region. The SCBSs are then placed in such a way to minimize the eavesdroppers' effect without having any information about their exact locations. In jamming scenarios, we consider a cost constrained jammer to be present in the network. The SCBSs are then placed in order to minimize the effect of the jammer's signal on the quality of the user's transmission. We simulate the developed algorithm for both types of attacks and for various network configurations. Simulation results show that the proposed solution approach yields significant improvements in the spatial SINR of all users when compared with conventional placement techniques.

This work addresses a vision-based target tracking problem between a mobile observer and a target in the presence of a circular obstacle. The task of keeping the target in the observer's field-of-view is modeled as a pursuit-evasion game by assuming that the target is adversarial in nature. Due to the presence of obstacles, this is formulated as a game with state constraints. The objective of the observer is to maintain a line-of-sight with the target at all times. The objective of the target is to break the line-of-sight in finite amount of time. First, we establish that the value of the game exists in this setting. Then we reduce the dimension of the problem by formulating the game in relative coordinates, and present a discretization in time and space for the reduced game. Based on this discretization, we use a fully discrete semi-Lagrangian scheme to compute the Kružkov transform of the value function numerically, and show that the scheme converges for our problem. Finally, we compute the optimal control action of the players from the Kružkov transform of the value function, and demonstrate the performance of the numerical scheme by numerous simulations.

In this paper, we investigate the problem of secure communications between a number of secondary users (SUs) transmitting data to a common base station in the presence of primary users (PUs) and eavesdroppers in a cognitive radio network. The SUs aim at mitigating the effect of eavesdropping by changing their positions using only partial information about the locations of the eavesdroppers. Accordingly, for each SU, we propose an appropriate utility function and then maximize the social welfare of all SUs without interfering with the PUs' radio receivers and taking into account the interference thresholds set by the PUs on each channel. Given these constraints, we formulate the problem so as to optimize the social welfare of all SUs. Depending on the possible communication links and the available information, we propose three different algorithms to solve the proposed constrained optimization: first we solve the problem centrally at the BS, second we propose a decentralized game theoretic approach, and third we consider a Lagrangian-heuristic based algorithm. Simulation results show that the proposed decentralized algorithms can achieve high near-optimal performances.

In this paper, we investigate the problem of secure communication between secondary users (SUs) and their serving base station in the presence of multiple eavesdroppers and multiple primary users. We analyze the interactions between the SUs and eavesdroppers using the framework of noncooperative game theory. To solve the formulated game, we propose a novel secure channel selection algorithm that enables the SUs and eavesdroppers to take distributed decisions so as to reach a Nash equilibrium point. We study and analyze several properties of the equilibrium resulting from the proposed algorithm. Simulation results show that the proposed approach yields significant improvements of at least 32.7%, in terms of the average secrecy rate per SU, relative to a classical spectrum sharing scheme. Moreover, the results show that the proposed scheme enables the SUs to reach Nash equilibrium with up to 86.5% less computation than standard learning algorithms.

This paper studies a particular sensor network model which involves one single Gaussian source observed by many sensors, subject to additive independent Gaussian observation noise. Sensors communicate with the receiver over an additive Gaussian multiple access channel. The aim of the receiver is to reconstruct the underlying source with minimum mean squared error. The scenario of interest here is one where some of the sensors act as adversary (jammer): they strive to maximize distortion. We show that the ability of transmitter sensors to secretly agree on a random event, that is “coordination”, plays a key role in the analysis. Depending on the coordination capability of sensors and the receiver, we consider two problem settings. The first setting involves transmitters with “coordination” capabilities in the sense that all transmitters can use identical realization of randomized encoding for each transmission. In this case, the optimal strategy for the adversary sensors also requires coordination, where they all generate the same realization of independent and identically distributed Gaussian noise. In the second setting, the transmitter sensors are restricted to use fixed, deterministic encoders and this setting, which corresponds to a Stackelberg game, does not admit a saddle-point solution. We show that the the optimal strategy for all sensors is uncoded communications where encoding functions of adversaries and transmitters are in opposite directions. For both settings, digital compression and communication is strictly suboptimal.

Performance of a delay-tolerant network has strong dependence on the nodes participating in data transportation. Such networks often face several resource constraints especially related to energy. Energy is consumed not only in data transmission, but also in listening and in several signaling activities. On one hand these activities enhance the system's performance while on the other hand, they consume a significant amount of energy even when they do not involve actual node transmission. Accordingly, in order to use energy efficiently, one may have to limit not only the amount of transmissions, but also the amount of nodes that are active at each time. Therefore, we study two coupled problems: 1) the activation problem that determines when a mobile will turn on in order to receive packets; and 2) the problem of regulating the beaconing. We derive optimal energy management strategies by formulating the problem as an optimal control one, which we then explicitly solve. We also validate our findings through extensive simulations that are based on contact traces.

In emerging small cell wireless, each femtocell access point (FAP) can either service its home subscribers exclusively (i.e., closed access) or open its access to accommodate a number of macrocell users so as to reduce cross-tier interference. In this paper, we propose a game-theoretic framework that enables the FAPs to strategically decide on their uplink access policy. We formulate a noncooperative game in which the FAPs are the players that want to strategically decide on whether to use a closed or an open access policy in order to maximize the performance of their registered users. Each FAP aims at optimizing the tradeoff between reducing cross-tier interference, by admitting macrocell users, and the associated cost in terms of allocated resources. Using novel analytical techniques, we show that the game always admits a pure strategy Nash equilibrium, despite the discontinuities in the utility functions. Further, we propose a distributed algorithm that can be adopted by the FAPs to reach their equilibrium access policies. Simulation results show that the proposed algorithm provides an improvement of 85.4% relative to an optimized open access scheme in the average worst-case FAP utility.

Smart grid is a visionary user-centric system that will elevate the conventional power grid system to one which functions more cooperatively, responsively, and economically. Dynamic demand side management is one of the key issues that enable the implementation of smart grid. In this paper, we use the framework of dynamic games to model the distribution demand side management. The market price is characterized as the dynamic state using a sticky price model. A two-layer optimization framework is established. At the lower level, for each player (such as one household), different appliances are scheduled for energy consumption. At the upper level, the dynamic game is used to capture the interaction among different players in their demand responses through the market price. We analyze the N-person nonzero-sum stochastic differential game and characterize its feedback Nash equilibrium. A special case of homogeneous users is investigated in detail and we provide a closed-form solution for the optimal demand response. From the simulation results, we demonstrate the use of demand response strategy from the game-theoretic framework and study the behavior of market price and demand responses to different parameters.

The 17 papers in this special issue cover various traditional as well as emerging networking and communications problems in innovative and insightful ways.

This paper introduces a novel approach that enables a number of cognitive radio devices that are observing the availability pattern of a number of primary users (PUs), to cooperate and use Bayesian nonparametric techniques to estimate the distributions of the PUs' activity pattern. To address this problem, a coalitional game is formulated between the cognitive devices and an algorithm for cooperative coalition formation is proposed. It is shown that the proposed coalition formation algorithm allows the cognitive nodes that are experiencing a similar behavior from some PUs to self-organize into disjoint, independent coalitions. Inside each coalition, the cooperative cognitive nodes use Bayesian nonparametric techniques so as to improve the accuracy of the estimated PUs' activity distributions. Simulation results show that the proposed algorithm significantly improves the estimates of the PUs' activity patterns.

Traditional intrusion detection systems (IDSs) work in isolation and can be easily compromised by unknown threats. An intrusion detection network (IDN) is a collaborative IDS network intended to overcome this weakness by allowing IDS peers to share detection knowledge and experience, and hence improve the overall accuracy of intrusion assessment. In this work, we design an IDN system, called GUIDEX, using game-theoretic modeling and trust management for peers to collaborate truthfully and actively. We first describe the system architecture and its individual components, and then establish a game-theoretic framework for the resource management component of GUIDEX. We establish the existence and uniqueness of a Nash equilibrium under which peers can communicate in a reciprocal incentive compatible manner. Based on the duality of the problem, we develop an iterative algorithm that converges geometrically to the equilibrium. Our numerical experiments and discrete event simulation demonstrate the convergence to the Nash equilibrium and the security features of GUIDEX against free riders, dishonest insiders and DoS attacks.

In this paper, we introduce a distributed dynamic routing algorithm in multi-hop cognitive radio (CR) networks, in which secondary users (SUs) want to minimize their interference to the primary users (PUs) while keeping the delay along the route low. We employ a cognitive pilot channel (CPC) for SUs to be able to access the information about PUs, including PUs' locations and channel conditions. Medial axis with a relaxation factor is used as a reference path for the routing, along which we develop a hierarchical structure for multiple sources to reach their destinations. We introduce a temporal and spatial dynamic non-cooperative game to model the interactions among the SUs as well as their influences on the PUs, and obtain by backward induction a set of mixed (behavioral) Nash equilibrium strategies. We also employ a multi-stage fictitious play learning algorithm for distributed routing, which minimizes the overall interference from the SUs to the PUs, as well as the average packet delay along the route from the SU nodes to their destinations. Simulation results show that our proposed algorithm can avoid congestion in the CR network and minimize delay while keeping the interference level low.

Physical layer security has emerged as a promising technique that complements existing cryptographic approaches and enables the securing of wireless transmissions against eavesdropping. In this paper, the impact of optimizing physical layer security metrics on the architecture and interactions of the nodes in multi-hop wireless networks is studied. In particular, a game-theoretic framework is proposed using which a number of nodes interact and choose their optimal and secure communication paths in the uplink of a wireless multi-hop network, in the presence of eavesdroppers. To this end, a tree formation game is formulated in which the players are the wireless nodes that seek to form a network graph among themselves while optimizing their multi-hop secrecy rates or the path qualification probabilities, depending on their knowledge of the eavesdroppers' channels. To solve this game, a distributed tree formation algorithm is proposed and is shown to converge to a stable Nash network. Simulation results show that the proposed approach yields significant performance gains in terms of both the average bottleneck secrecy rate per node and the average path qualification probability per node, relative to classical best-channel algorithms and the single-hop star network. The results also assess the properties and characteristics of the resulting Nash networks.

In this paper, we propose a dynamic secure routing game framework to effectively combat jamming attacks in distributed cognitive radio networks. We first propose a stochastic multi-stage zero-sum game framework based on the directional exploration of ad hoc on-demand distance vector (AODV) algorithms. The zero-sum game captures the conflicting goals between malicious attackers and honest nodes and considers packet error probability and delay as performance metrics. The game-theoretic routing protocol guarantees a performance level given by the value of the game. Distributed Boltzmann-Gibbs learning is used for an on-line routing algorithm, in which the users do not have the knowledge of the attackers and the utility function. Instead, the users learn the payoffs based on their past observations. We use simulations to illustrate the proposed routing mechanism and compare the algorithm with fictitious-play learning. Unlike typical distributed routing algorithms such as AODV routing, the proposed secure routing algorithm supports a novel recovery of routing path failure against unknown attackers.

In this work, we study the problem of power allocation and adaptive modulation in teams of decision makers. We consider the special case of two teams with each team consisting of two mobile agents. Agents belonging to the same team communicate over wireless ad hoc networks, and they try to split their available power between the tasks of communication and jamming the nodes of the other team. The agents have constraints on their total energy and instantaneous power usage. The cost function adopted is the difference between the rates of erroneously transmitted bits of each team. We model the adaptive modulation problem as a zero-sum matrix game which in turn gives rise to a a continuous kernel game to handle power control. Based on the communications model, we present sufficient conditions on the physical parameters of the agents for the existence of a pure strategy saddle-point equilibrium (PSSPE).

Cooperation among wireless nodes has been recently proposed for improving the physical layer (PHY) security of wireless transmission in the presence of multiple eavesdroppers. While existing PHY security literature answered the question “what are the link-level secrecy rate gains from cooperation?”, this paper attempts to answer the question of “how to achieve those gains in a practical decentralized wireless network and in the presence of a cost for information exchange?”. For this purpose, we model the PHY security cooperation problem as a coalitional game with non-transferable utility and propose a distributed algorithm for coalition formation. Using the proposed algorithm, the wireless users can cooperate and self-organize into disjoint independent coalitions, while maximizing their secrecy rate taking into account the costs during information exchange. We analyze the resulting coalitional structures for both decode-and-forward and amplify-and-forward cooperation and study how the users can adapt the network topology to environmental changes such as mobility. Through simulations, we assess the performance of the proposed algorithm and show that, by coalition formation using decode-and-forward, the average secrecy rate per user is increased of up to 25.3 and 24.4% (for a network with 45 users) relative to the non-cooperative and amplify-and-forward cases, respectively.

The introduction of relay station (RS) nodes is a key feature in next generation wireless networks such as 3GPP's long term evolution advanced (LTE-Advanced), or the forthcoming IEEE 802.16j WiMAX standard. This paper presents, using game theory, a novel approach for the formation of the tree architecture that connects the RSs and their serving base station in the uplink of the next generation wireless multi-hop systems. Unlike existing literature which mainly focused on performance analysis, we propose a distributed algorithm for studying the structure and dynamics of the network. We formulate a network formation game among the RSs whereby each RS aims to maximize a cross-layer utility function that takes into account the benefit from cooperative transmission, in terms of reduced bit error rate, and the costs in terms of the delay due to multi-hop transmission. For forming the tree structure, a distributed myopic algorithm is devised. Using the proposed algorithm, each RS can individually select the path that connects it to the BS through other RSs while optimizing its utility. We show the convergence of the algorithm into a Nash tree network, and we study how the RSs can adapt the network's topology to environmental changes such as mobility or the deployment of new mobile stations. Simulation results show that the proposed algorithm presents significant gains in terms of average utility per mobile station which is at least 17.1% better relatively to the case with no RSs and reaches up to 40.3% improvement compared to a nearest neighbor algorithm (for a network with 10 RSs). The results also show that the average number of hops does not exceed 3 even for a network with up to 25 RSs.

Autonomous wireless agents such as unmanned aerial vehicles, mobile base stations, cognitive devices, or self-operating wireless nodes present a great potential for deployment in next-generation wireless networks. While current literature has been mainly focused on the use of agents within robotics or software engineering applications, this paper proposes a novel usage model for self-organizing agents suitable for wireless communication networks. In the proposed model, a number of agents are required to collect data from several arbitrarily located tasks. Each task represents a queue of packets that require collection and subsequent wireless transmission by the agents to a central receiver. The problem is modeled as a hedonic coalition formation game between the agents and the tasks that interact in order to form disjoint coalitions. Each formed coalition is modeled as a polling system consisting of a number of agents, designated as collectors, which move between the different tasks present in the coalition, collect and transmit the packets. Within each coalition, some agents might also take the role of a relay for improving the packet success rate of the transmission. The proposed hedonic coalition formation algorithm allows the tasks and the agents to take distributed decisions to join or leave a coalition, based on the achieved benefit in terms of effective throughput, and the cost in terms of polling system delay. As a result of these decisions, the agents and tasks structure themselves into independent disjoint coalitions which constitute a Nash-stable network partition. Moreover, the proposed coalition formation algorithm allows the agents and tasks to adapt the topology to environmental changes, such as the arrival of new tasks, the removal of existing tasks, or the mobility of the tasks. Simulation results show how the proposed algorithm allows the agents and tasks to self-organize into independent coalitions, while improving the performance, in terms of average player (agent or task) payoff, of at least 30.26 percent (for a network of five agents with up to 25 tasks) relatively to a scheme that allocates nearby tasks equally among agents.

In current peer-to-peer file sharing networks, a large number of peers with heterogeneous connections simultaneously seek to download resources, e.g., files or file fragments, from a common seed at the time these resources become available, which incurs high download delays on the different peers. Unlike existing literature which mainly focused on cooperative strategies for data exchange between different peers after all the peers have already acquired their resources, in this paper, we study the cooperation possibilities among a number of peers seeking to download, concurrently, a number of resources at the time the availability of the resources is initially announced at a common seed. We model the problem as a coalitional game in partition form and we propose an algorithm for coalition formation among the peers. The proposed algorithm enables the peers to take autonomous decisions to join or leave a coalition while minimizing their average download delay. We show that, by using the proposed algorithm, a Nash-stable partition composed of coalitions of peers is formed. Within every coalition, the peers distribute their download requests between the seed and the cooperating partners in a way to minimize the total average delay incurred on the coalition. Analytically, we study the 2-peer scenario and derive the optimal download request distribution policies. Simulation results show that, using the proposed coalition formation game, the peers can improve their average download delay per peer of up to 99.6% compared to the non-cooperative approach for the case with N = 15 peers.

In this paper, we introduce a distributed dynamic routing algorithm for secondary users (SUs) to minimize their interference with the primary users (PUs) in multi-hop cognitive radio (CR) networks. We use the medial axis with a relaxation factor as a reference path which is contingent on the states of the PUs. Along the axis, we construct a hierarchical structure for multiple sources to reach cognitive pilot channel (CPC) base stations. We use a temporal and spatial dynamic non-cooperative game to model the interactions among SUs as well as their influences from PUs in the multi-hop structure of the network. A multi-stage fictitious play learning is used for distributed routing in multi-hop CR networks. We obtain a set of mixed (behavioral) Nash equilibrium strategies of the dynamic game in closed form by backward induction. The proposed algorithm minimizes the overall interference and the average packet delay along the routing path from SU nodes to CPC base stations in an optimal and distributed manner.

This paper considers a Markovian dynamical game theoretic setting for distributed transmission control in a wireless sensor network. The available spectrum bandwidth is modeled as a Markov chain. A distributed algorithm named correlated Q-learning algorithm is proposed to obtain the correlated equilibrium policies of the system. This algorithm has the decentralized feature and is easily implementable in a real system. Numerical example is also provided to verify the performances of the proposed algorithms.

Collaborative intrusion detection networks are often used to gain better detection accuracy and cost efficiency as compared to a single host-based intrusion detection system (IDS). Through cooperation, it is possible for a local IDS to detect new attacks that may be known to other experienced acquaintances. In this paper, we present a sequential hypothesis testing method for feedback aggregation for each individual IDS in the network. Our simulation results corroborate our theoretical results and demonstrate the properties of cost efficiency and accuracy compared to other heuristic methods. The analytical result on the lower-bound of the average number of acquaintances for consultation is essential for the design and configuration of IDSs in a collaborative environment.

In cognitive radio network, spectrum sensing is a key component to detect spectrum holes (i.e., channels not used by any primary users). Collaborative spectrum sensing among the cognitive radio nodes is expected to improve fidelity of primary user detection. However, malicious nodes can significantly impair the collaborative spectrum sensing by sending the wrong reports to the fusion center. To overcome this problem, in this paper we propose non- regret learning algorithms to study the non-constructive secondary users caused either by evil-intention or altruistical incapability. Both perfect observation and partial monitoring are investigated, and two algorithms are proposed respectively. Some convergence properties are also shown. Moreover, we also analyze the case in which the nature is assumed to be a player. Illustration example and simulation results demonstrate the proposed schemes can automatically pick the malicious nodes in a distributed way.

The security issue in collaborative sensing in cognitive radio networks can be modeled as attackers and secondary users in a jamming and anti-jamming scenario. In this paper, we introduce a stochastic zero-sum game model to study the strategies. Primary users, secondary users and jammers are the three types of agents in the system. The primary users dictate the system states and their transitions while the secondary users and jammers behave non-cooperatively to achieve their goals independently under different system environment. Our Markovian game model captures not only the zero-sum interactions between secondary users and the jammers but also the dynamics of the system. Our results indicate that the secondary users can enhance their security level or increase their long-term payoff by either improving their sensing capabilities to confuse the jammer with the choice or choosing to communicate under states where the available channels are less prone to jamming. In the numerical experiments, we point out that the payoff of the secondary users increases with the number of available jamming-free channels and is eventually limited by the behavior of primary users.

Much research has been devoted to maximize the life time of mobile ad-hoc networks. Life time has often been defined as the time elapsed until the first node is out of battery power. In the context of static networks, this could lead to disconnectivity. In contrast, Delay Tolerant Networks (DTNs) leverage the mobility of relay nodes to compensate for lack of permanent connectivity, and thus enable communication even after some nodes deplete their stored energy. One can thus consider the lifetimes of nodes as some additional parameters that can be controlled to optimize the performance of a DTN. In this paper, we consider two ways in which the energy state of a mobile can be controlled. Both listening and transmission require energy, besides each of these has a different type of effect on the network performance. Therefore we consider a joint optimization problem consisting of: i) activation, which determines when a mobile will turn on in order to receive packets, and ii) transmission control, which regulates the beaconing. The optimal solutions are shown to be of the threshold type. The findings are validated through extensive simulations.

Cooperation between intrusion detection systems (IDSs) allow collective information and experience from a network of IDSs to be shared for improving the accuracy of detection. A critical component of a collaborative network is the mechanism of feedback aggregation in which each IDS makes an overall security evaluation based on peer opinions and assessments. In this paper, we propose a collaboration framework for intrusion detection networks (CIDNs) and use a Bayesian approach for feedback aggregation by minimizing the combined costs of missed detection and false alarm. The proposed model is highly scalable, robust, and cost effective. Experimental results demonstrate an improvement in the true positive detection rate and a reduction in the average cost of our mechanism compared to existing models.

In order to maintain a conflict-free environment among licensed primary users (PUs) and unlicensed secondary users (SUs) in cognitive radio networks, providing frequency and geographical information through control channels, such as the cognitive pilot channel (CPC), has been recently proposed. While existing literature focused on the type of information that these control channels need to carry, this paper investigates the problem of gathering this information cooperatively, among a network of secondary base stations (SBSs). In this regard, given a cognitive network where every SBS can only have accurate knowledge on a small number of different primary users (PUs) or channels, each SBS can cooperate with neighboring SBSs in order to improve its view of the spectrum, i.e., learn about new PUs that can subsequently be used by its served SUs. We model the problem as a hedonic coalition formation game among the SBSs and we propose an algorithm for forming the coalitions. Using the proposed algorithm, each SBS can take an individual decision to join or leave a coalition while maximizing its overall potential utility, which accounts for the tradeoff between the benefit from learning new channels through coalition members and the cost from receiving inaccurate information. Simulation results show that the proposed algorithm yields a performance advantage, in terms of the average payoff per SBS reaching up to 165% relative to the non-cooperative case for a large network with 27 SBSs.

In this paper, we propose a game theoretic approach to tackle the problem of the distributed formation of the hierarchical network architecture that connects the nodes in the uplink of a wireless multi-hop network. Unlike existing literature which focused on the performance assessment of hierarchical multi-hop networks given an existing topology, this paper investigates the problem of the formation of this topology among a number of nodes that seek to send data in the uplink to a central base station through multihop. We model the problem as a hierarchical network formation game and we divide the network into different hierarchy levels, whereby the nodes belonging to the same level engage in a noncooperative Nash game for selecting their next hop. As a solution to the game, we propose a novel equilibrium concept, the hierarchical Nash equilibrium, for a sequence of multi-stage Nash games, which can be found by backward induction analytically. For finding this equilibrium, we propose a distributed myopic dynamics algorithm, based on fictitious play, in which each node computes the mixed strategies that maximize its utility which represents the probability of successful transmission over the multi-hop communication path in the presence of interference. Simulation results show that the proposed algorithm presents significant gains in terms of average achieved expected utility per user up to 125.6% relative to a nearest neighbor algorithm.

In this paper, we propose an evolutionary game-theoretic framework for hybrid additive white Gaussian noise multiple access channels. We consider a communication system consisting of multiple users and multiple receivers, where each user chooses a rate and splits it over the receivers. Users have coupled constraints determined by the capacity regions. We show the existence of Nash equilibrium under general conditions and characterize the equilibria of the static game. Building upon the static game, we formulate a system of hybrid evolutionary game dynamics using G-function dynamics and Smith dynamics on rate control and channel selection, respectively. We show that the evolutionary hybrid multiple access game has an equilibrium and illustrate these dynamics with numerical examples.

We study two-player security games which can be viewed as sequences of nonzero-sum matrix games played by an attacker and a defender. At each stage of the game iterations, the players make imperfect observations of each other's previous actions. The underlying decision process can be viewed as a fictitious play (FP) game, but what differentiates this class from the standard one is that the communication channels that carry action information from one player to the other, or the sensor systems, are error prone. Two possible scenarios are addressed in the paper: (i) if the error probabilities associated with the sensor systems are known to the players, then our analysis provides guidelines for each player to reach a Nash equilibrium (NE), which is related to the NE of the underlying static game; (ii) if the error probabilities are not known to the players, then we study the effect of observation errors on the convergence to the NE and the final outcome of the game. We discuss both the classical FP and the stochastic FP, where for the latter the payoff function of each player includes an entropy term to randomize its own strategy, which can be interpreted as a way of concealing its true strategy.

In this paper, we propose a game theoretical approach to tackle the problem of the distributed formation of the uplink tree structure among the relay stations (RSs) and their serving base station (BS) in an IEEE 802.16j WiMAX network. Unlike existing literature, which focused on the performance assessment of the network in the presence of the RSs, we investigate the topology and dynamics of the tree structure in the uplink of an 802.16j network. We model the problem as a network formation game, where each RS aims to maximize its utility that accounts for the gains from cooperation in terms of bit error rate (BER) and the delay costs resulting from multi-hop transmission. The proposed utility model is based on the concept of the R-factor which is a parameter suitable for assessing the performance of VoIP services. For forming the tree structure, we propose a distributed myopic best response dynamics in which each RS can autonomously choose the path that connects it to the BS through other relays while optimizing its utility. Using the proposed dynamics, the RSs can self-organize into the tree structure, and adapt this topology to environmental changes such as mobility while converging to a Nash tree network. Simulation results show that the proposed algorithm presents significant gains in terms of average achieved MS utility reaching up to 42.57% compared to the star topology where all RSs are directly connected to the BS, and up to 44.78% compared to the case with no RSs.

Collaborative spectrum sensing among secondary users (SUs) in cognitive networks is shown to yield a significant performance improvement. However, there exists an inherent trade off between the gains in terms of probability of detection of the primary user (PU) and the costs in terms of false alarm probability. In this paper, we study the impact of this trade off on the topology and the dynamics of a network of SUs seeking to reduce the interference on the PU through collaborative sensing. Moreover, while existing literature mainly focused on centralized solutions for collaborative sensing, we propose distributed collaboration strategies through game theory. We model the problem as a non-transferable coalitional game, and propose a distributed algorithm for coalition formation through simple merge and split rules. Through the proposed algorithm, SUs can autonomously collaborate and self-organize into disjoint independent coalitions, while maximizing their detection probability taking into account the cooperation costs (in terms of false alarm). We study the stability of the resulting network structure, and show that a maximum number of SUs per formed coalition exists for the proposed utility model. Simulation results show that the proposed algorithm allows a reduction of up to 86.6% of the average missing probability per SU (probability of missing the detection of the PU) relative to the non-cooperative case, while maintaining a certain false alarm level. In addition, through simulations, we compare the performance of the proposed distributed solution with respect to an optimal centralized solution that minimizes the average missing probability per SU. Finally, the results also show how the proposed algorithm autonomously adapts the network topology to environmental changes such as mobility.

We study a dynamic random access game with a finite number of opportunities for transmission and with energy constraints. We provide sufficient conditions for feasible strategies and for existence of Nash-Pareto solutions and show that finding Nash-Pareto policies of the dynamic random access game is equivalent to partitioning the set of time slot opportunities with constraints into a set of terminals. We further derive upper bounds for pure Nash-Pareto policies, and extend the study to non-integer energy constraints and unknown termination time, where Time Division Multiplexing policies can be suboptimal. We show that the dynamic random access game has several strong equilibria (resilient to coalition of any size), and we compute them explicitly. We introduce the (strong) price of anarchy concept to measure the gap between the payoff under strong equilibria and the social optimum.

Cooperation between wireless network nodes is a promising technique for improving the physical layer security of wireless transmission, in terms of secrecy capacity, in the presence of multiple eavesdroppers. While existing physical layer security literature answered the question “what are the link-level secrecy capacity gains from cooperation?”, this paper attempts to answer the question of “how to achieve those gains in a practical decentralized wireless network and in the presence of a secrecy capacity cost for information exchange?”. For this purpose, we model the physical layer security cooperation problem as a coalitional game with non-transferable utility and propose a distributed algorithm for coalition formation. Through the proposed algorithm, the wireless users can autonomously cooperate and self-organize into disjoint independent coalitions, while maximizing their secrecy capacity taking into account the security costs during information exchange. We analyze the resulting coalitional structures, discuss their properties, and study how the users can self-adapt the network topology to environmental changes such as mobility. Simulation results show that the proposed algorithm allows the users to cooperate and self-organize while improving the average secrecy capacity per user up to 25.32% relative to the non-cooperative case.

We investigate a novel robust flow control framework for heterogeneous network access by devices with multi-homing capabilities. Towards this end, we develop an H-infinity-optimal control formulation for allocating rates to devices on multiple access networks with heterogeneous time-varying characteristics. H-infinity analysis and design allow for the coupling between different devices to be relaxed by treating the dynamics for each device as independent of the others. Thus, the distributed end-to-end rate control scheme proposed in this work relies on minimum information and achieves fair and robust rate allocation for the devices. An efficient utilization of the access networks is established through an equilibrium analysis in the static case. We perform measurement tests to collect traces of the available bandwidth on various WLANs and Ethernet. Through simulations, our approach is compared with AIMD and LQG schemes. In addition, the efficiency, fairness, and robustness of the H-infinity-optimal rate controller developed are demonstrated via simulations using the measured real world network characteristics. Its favorable characteristics and general nature indicate applicability of this framework to a variety of networked systems for flow control.

The performance of carrier sense multiple access (CSMA) wireless networks heavily depends on the level of spatial reuse, i.e., how many concurrent transmissions are allowed. Spatial reuse is primarily determined by physical carrier sense, and a key parameter for physical carrier sense is the carrier sense threshold. Our focus is on how to control the carrier sense threshold for improving network performance. We present a noncooperative game-theoretic framework, which leads to a fully distributed algorithm for tuning the carrier sense threshold. We introduce a utility function of each node, which is a nondecreasing concave function of the carrier sense threshold. A pricing function is further introduced to mitigate severe interference among nodes. The cost function is defined as the difference between the pricing and the utility functions. We prove that the noncooperative carrier sense game admits a unique Nash equilibrium (NE) under some technical conditions.We derive sufficient conditions that ensure the convergence of the synchronous and asynchronous update algorithms. Based on the analysis, we propose a fully distributed algorithm, entitled noncooperative carrier sense update algorithm (NCUA). Our simulation study indicates that NCUA outperforms standard CSMA with respect to the per-node throughput by 10-50%.

The 26 papers in this special issue focus on game theory in communication systems. The papers are grouped in four clusters according to their topics: (1) Physical layer models in wireless communications, (2) higher layer and cross-layer issues in wireless communications, (3) wire-line communication networks, and (4) specific topics including peer-to-peer networking, network coding, and network security.

A common feature of congestion control protocols is the presence of information packets used to signal congestion. We address here the question of how frequently such protocols need to generate information packets in order to optimize their performance. Through a number of congestion control models, we identify and quantify different types of effects of the frequency of generating information packets. We consider both TCP-type protocols, in which controlling the frequency of information packets is done through static or dynamic delayed ACK options, as well as ATM type flow control, where the optimal time spacing between the generation of network management packets is computed. We show how the spacing between information packets influences the throughput and the stability of the system.

In the communication network pricing literature, it is the linear pricing schemes that have been largely adopted as the means of controlling network usage or generating profits for network service providers. This paper extends the framework to nonlinear pricing and investigates optimal nonlinear pricing policy design for a monopolistic service provider. The problem is formulated as an incentive-design problem, and incentive (pricing) policies are obtained for a many-users regime, which enable the service provider to approach arbitrarily close to Pareto- optimal solutions. Under the assumption that the service provider knows the true user types, analytical and numerical results indicate a profit improvement exceeding 38% over linear pricing by the introduction of nonlinear pricing. We also consider the scenario where the service provider has incomplete information on user types. A comparative study of the results for complete information and incomplete information is carried out as well, with numerical results pointing to 25%-40% loss of profit by the service provider due to incompleteness of information on the user types.

We study the distributed averaging problem on arbitrary connected graphs, with the additional constraint that the value at each node is an integer. This discretized distributed averaging problem models averaging in a network with finite capacity channels (and in this form has applications to distributed detection in sensor networks) and load balancing in a processor network. We describe simple randomized distributed algorithms which achieve consensus to the extent that the discrete nature of the problem permits.

We address the problem of devising efficient decentralized allocation mechanisms for a divisible resource, which is critical to many technological domains such as traffic management on the Internet and bandwidth allocation to agents in ad hoc wireless networks. We introduce a class of efficient signal proportional allocation (ESPA) mechanisms that yields an allocation which maximizes social welfare with minimal signaling and computational requirements for the resource. Revenue limits for this class are obtained and a sequence of schemes that approach these limits arbitrarily closely are given. We also present a locally stable negotiation scheme applicable to the entire class and illustrate efficiency and revenue properties through simulation.

We present a game-theoretic treatment of distributed power control in CDMA wireless systems using outage probabilities. We first prove that the noncooperative power control game considered admits a unique Nash equilibrium (NE) for uniformly strictly convex pricing functions and under some technical assumptions on the SIR threshold levels. We then analyze global convergence of continuous-time as well as discrete-time synchronous and asynchronous iterative power update algorithms to the unique NE of the game. Furthermore, we show that a stochastic version of the discrete-time update scheme, which models the uncertainty due to quantization and estimation errors, converges almost surely to the unique NE point. We finally investigate and demonstrate the convergence and robustness properties of these update schemes through simulation studies.

This paper discusses modeling and simulation issues associated with the stochastic behavior of a special type of a computer worm called a random constant scanning (RCS) worm. Although these worms propagate by randomly scanning network addresses to find hosts that are susceptible to infection, traditional RCS worm models are fundamentally deterministic. A density-dependent Markov jump process model for RCS worms is presented and analyzed. Conditions are shown for when worm models can safely ignore some stochastic properties of RCS worm propagation. A computationally simple hybrid deterministic/stochastic model for the observed scanning behavior on a local network due to the global propagation of an RCS scanning worm is also presented and discussed.

Deterministic delay differential equation models, where the packet traffic is modeled as a fluid, are widely used to study congestion control algorithms in the Internet. In this paper, we point out some pitfalls in such fluid modeling of window flow control algorithms. Specifically, we argue that the modeling assumptions used to capture the variability in the RTT (due to queue length fluctuations) may play a critical role in our ability to design stable algorithms. We study two scenarios to illustrate the dramatic impact of RTT modeling. We first consider TCP-Reno with RED, and show that assuming that the RTT is a constant (when it is actually time-varying) leads to conservative parameter choices, i.e., the system continues to be stable even with variable RTT. On the other hand, for the recently proposed stabilized Vegas, we show the following result: while the network can be stabilized under the constant RTT assumption, there is no choice of parameters that would stabilize the system when the RTT variations are taken into account. Interestingly, such problems do not arise if the congestion-control mechanisms at the end-users are rate-based.

We study power control in multicell CDMA wireless networks as a team optimization problem where each mobile attains its individual fixed target SIR level by transmitting with minimum possible power level. We derive conditions under which the power control problem admits a unique feasible solution. Using a Lagrangian relaxation approach similar to F. Kelly et al. (1998) we obtain two decentralized dynamic power control algorithms: primal and dual power update, and establish their global stability utilizing both classical Lyapunov theory and the passivity framework [J.T. Wen and M. Arcak, February 2004]. We show that the robustness results of passivity studies [(X. Fan et al., July 2004), (X. Fan et al., 2004)] as well as most of the stability and robustness analyses of F. Kelly et al. (1998) in the literature are applicable to the power control problem considered. In addition, some of the basic principles of call admission control are investigated from the perspective of the model adopted in this paper. We illustrate the proposed power control schemes through simulations.

This paper initiates a study toward developing and applying randomized algorithms for stability of high-speed communication networks. The focus is on congestion and delay-based flow controllers for sources, which are "utility maximizers" for individual users. First, we introduce a nonlinear algorithm for such source flow controllers, which uses as feedback aggregate congestion and delay information from bottleneck nodes of the network, and depends on a number of parameters, among which are link capacities, user preference for utility, and pricing. We then linearize this nonlinear model around its unique equilibrium point and perform a robustness analysis for a special symmetric case with a single bottleneck node. The "symmetry" here captures the scenario when certain utility and pricing parameters are the same across all active users, for which we derive closed-form necessary and sufficient conditions for stability and robustness under parameter variations. In addition, the ranges of values for the utility and pricing parameters for which stability is guaranteed are computed exactly. These results also admit counterparts for the case when the pricing parameters vary across users, but the utility parameter values are still the same. In the general nonsymmetric case, when closed-form derivation is not possible, we construct specific randomized algorithms which provide a probabilistic estimate of the local stability of the network. In particular, we use Monte Carlo as well as quasi-Monte Carlo techniques for the linearized model. The results obtained provide a complete analysis of congestion control algorithms for internet style networks with a single bottleneck node as well as for networks with general random topologies.

In this paper, we develop, analyze and implement a congestion control scheme in a noncooperative game framework, where each user's cost function is composed of a pricing function proportional to the queueing delay experienced by the user, and a fairly general utility function which captures the user demand for bandwidth. Using a network model based on fluid approximations and through a realistic modeling of queues, we establish the existence of a unique equilibrium as well as its global asymptotic stability for a general network topology, where boundary effects are also taken into account. We also provide sufficient conditions for system stability when there is a bottleneck link shared by multiple users experiencing nonnegligible communication delays. In addition, we study an adaptive pricing scheme using hybrid systems concepts. Based on these theoretical foundations, we implement a window-based, end-to-end congestion control scheme, and simulate it in ns-2 network simulator on various network topologies with sizable propagation delays.

This paper introduces and analyzes a decentralized network congestion control algorithm which has dynamic adaptations at both user ends and link ends, a so-called general primal-dual algorithm. We obtain sufficient conditions for local stability of this algorithm in a general topology network with heterogeneous round-trip delays. Then, as an implementation of this algorithm in the Internet, we introduce an AQM (Active Queue Management) scheme called Exponential-RED (E-RED), which outperforms RED and is inherently stable when combined with TCP-Reno or its variants for high-speed networks.

A zero-sum mutual information game on MIMO Gaussian Rayleigh fading channels is considered in this paper. The players are an encoder-decoder pair as the maximizer, and a jammer as the minimizer, of the mutual information between the input and the output of the channel. There are total power constraints on both the jammer and the encoder. Also, the jammer has access to the encoder output. We find the unique saddle point of this game, and prove the somewhat surprising result that the knowledge of the channel input is useless to the jammer.

We consider a zero-sum mutual information game on multiple-input multiple-output (MIMO) Gaussian Rayleigh-fading channels. The players are an encoder-decoder pair as the maximizer, and a jammer as the minimizer, of the mutual information between the input and the output of the channel. There are total power constraints on both the jammer and the encoder. Also, the jammer has access to the encoder output. We find the unique saddle point of this game, and prove the somewhat surprising result that the knowledge of the channel input is useless to the jammer.

In this paper, we develop, analyze and implement a congestion control scheme obtained in a noncooperative game framework where each user's cost function is composed of a pricing function, proportional to the queueing delay experienced by the user, and a fairly general utility function which captures the user demand for bandwidth. Using a network model based on fluid approximations and through a realistic modeling of queues, we establish the existence of a unique equilibrium as well as its global asymptotic stability for a general network topology. We also provide sufficient conditions for system stability when there is a bottleneck link shared by multiple users experiencing nonnegligible communication delays. Based on these theoretical foundations, we implement a window-based, end-to-end congestion control scheme, and simulate it in ns-2 network simulator on various network topologies with sizable propagation delays.

We consider a network where each user is charged a fixed price per unit of bandwidth used, but where there is no congestion-dependent pricing. However, the transmission rate of each user is assumed to be a function of network congestion (like TCP), and the price per unit bandwidth. We are interested in answering the following question: how should the network choose the price to maximize its overall revenue? To obtain a tractable solution, we consider a single link accessed by many users where the capacity is increased in proportion to the number of users. We show the following result: as the number of users increases, the optimal price per unit bandwidth charged by the service provider may increase or decrease depending upon the bandwidth of the link. However, for all values of the link capacity, the service provider's revenue per unit bandwidth increases and the overall performance of each user (measured in terms of a function of its throughput, the network congestion and the cost incurred by the user for bandwidth usage) improves. Since the revenue per unit bandwidth increases, it provides an incentive for the service provider to increase the available bandwidth in proportion to the number of users.

We present a novel ABR congestion control algorithm which is adaptive to changing network conditions and robust to network delays. The algorithm is easy to implement, as it only requires a single design parameter, and no centralized knowledge about the status of the network. Further, max-min fairness and queue length stability under minimum cell rate (MCR) and peak cell rate (PCR) constraints are automatically achieved.

We study a class of noncooperative general topology networks shared by N users. Each user has a given flow which it has to ship from a source to a destination. We consider a class of polynomial link cost functions, adopted originally in the context of road traffic modeling, and show that these costs have appealing properties that lead to predictable and efficient network flows. In particular, we show that the Nash equilibrium is unique, and is moreover efficient, i.e., it coincides with the solution of a corresponding global optimization problem with a single user. These properties make the cost structure attractive for traffic regulation and link pricing in telecommunication networks. We finally discuss the computation of the equilibrium in the special case of the affine cost structure for a topology of parallel links.

The paper considers the design of explicit rate-based flow control for available bit rate (ABR) sources in an ATM network. The goal is to share the available capacity "fairly" among many sources while maintaining queue length at a bottleneck node at a desired level. This problem is formulated as a stochastic control problem, and in this framework rate-control mechanisms are developed, which stabilize the queue length even though different sources may have different round-trip delays to the bottleneck node. Various robustness properties of the solution are illustrated through simulation experiments.

Flow and congestion control allow the users of a telecommunication network to regulate the traffic that they send into the network in accordance with the quality of service that they require. Flow control may be performed by the network, as is the case in asynchronous transfer mode (ATM) networks (the available bit rate (ABR) transfer capacity), or by the users themselves, as is the case in the Internet [transmission control protocol/Internet protocol (TCP/IP)]. We study both situations using optimal control and dynamic game techniques. The first situation leads to the formulation of a dynamic team problem, while the second one leads to a dynamic noncooperative game, for which we establish the existence and uniqueness of a linear Nash equilibrium and obtain a characterization of the corresponding equilibrium policies along with the performance costs. We further show that when the users update their policies in a greedy manner, not knowing a priori the utilities of the other players, the sequence of policies thus generated converges to the Nash equilibrium. Finally, we study an extension of the model that accommodates multiple traffic types for each user, with the switching from one type of traffic to another being governed by a Markov jump process. Presentation of some numerical results complements this study.

We study the problem of identification for nonlinear systems in the presence of unknown driving noise, using both feedforward multilayer neural network and radial basis function network models. Our objective is to resolve the difficulty associated with the persistency of excitation condition inherent to the standard schemes in the neural identification literature. This difficulty is circumvented here by a novel formulation and by using a new class of identification algorithms recently obtained by Didinsky et al. We show how these algorithms can be exploited to successfully identify the nonlinearity in the system using neural-network models. By embedding the original problem in one with noise-perturbed state measurements, we present a class of identifiers (under L1 and L2 cost criteria) which secure a good approximant for the system nonlinearity provided that some global optimization technique is used. In this respect, many available learning algorithms in the current neural-network literature, e.g., the backpropagation scheme and the genetic algorithms-based scheme, with slight modifications, can ensure the identification of the system nonlinearity. Subsequently, we address the same problem under a third, worst case L(infinity) criterion for an RBF modeling. We present a neural-network version of an H(infinity)-based identification algorithm from Didinsky et al and show how, along with an appropriate choice of control input to enhance excitation, under both full-state-derivative information (FSDI) and noise-perturbed full-state-information (NPFSI), it leads to satisfaction of a relevant persistency of excitation condition, and thereby to robust identification of the nonlinearity. Results from several simulation studies have been included to demonstrate the effectiveness of these algorithms.

Decentralized detection problems are studied where the sensor distributions are not specified completely. The sensor distributions are assumed to belong to known uncertainty classes. It is shown for a broad class of such problems that a set of least favorable distributions exists for minimax robust testing between the hypotheses. It is hence established that the corresponding minimax robust tests are solutions to simple decentralized detection problems for which the sensor distributions are specified to be the least favorable distributions.>

A decentralized sequential detection problem is considered in which each one of a set of sensors receives a sequence of observations about the hypothesis. Each sensor sends a sequence of summary messages to the fusion center where a sequential test is carried out to determine the true hypothesis. A Bayesian framework for this problem is introduced, and for the case when the information structure in the system is quasi-classical, it is shown that the problem is tractable. A detailed analysis of this case is presented, along with some numerical results.>

The complete solution is obtained to the following problem. A Gaussian stochastic process ( theta /sub t/,t in (0,t/sub f/)) satisfying a certain stochastic differential equation is to be transmitted through a stochastic channel to a receiver under minimum mean-squared error distortion measure. The channel is to be used for exactly t/sub f/ seconds, and, in addition to white Gaussian noise with a given energy level, the channel is corrupted by another source whose output may be correlated with the input to the channel and which satisfied a given power constraint. There is an input power constraint to the channel, and noiseless feedback is allowed between the receiver (decoder) and the transmitter (encoder). The authors determine the linear causal encoder and decoder structures that function optimally under the worst admissible noise inputs to the channel. The least favorable probability distribution for this unknown noise is found to be Gaussian and is correlated with the transmitted signal. Also included is a comparative study of these results with earlier ones that addressed a similar problem without a causality restriction imposed on the transmitter.>

The problem is considered of transmitting a sequence of independent and identically distributed Gaussian random variables over a channel whose statistical description is incomplete. The channel is modeled as one that is conditionally Gaussian, with the unknown part being controlled by a so-called jammer who may have access to the input to the encoder and operates under a given power constraint. By adopting a game-theoretic approach, a complete set of solutions is obtained (encoder and decoder mappings, and least-favorable distributions for the channel noise) for this statistical decision problem, under two different sets of conditions, depending on whether the encoder mapping is deterministic or stochastic. In the latter case, existence of a mixed saddle-point solution can be verified when a side channel of a specific nature is available between the transmitter and the receiver. In the former case, however, only minimax and maximin solutions can be derived.

Discrete and continuous-time two-person decision problems with a hierarchical decision structure are studied, and the applicability and appropriateness of a function-space approach in the derivation of causal real-time implementable optimal Stackelberg (incentive) strategies under various information patterns are discussed. Results on existence and derivation of incentive strategies for dynamic games formulated in abstract inner-product spaces, in the absence of any causality restriction on the leader's policies, are presented; these results are extended and specialized in two major directions: (1) discrete-time dynamic games, and (2) derivation of causal, physically realizable optimum affine Stackelberg policies for both discrete and continuous-time problems.

The problem of transmitting a sequence of identically distributed independent Gaussian random variables through a Gaussian memoryless channel with a given input power constraint, in the presence of an intelligent jammer, is considered. The jammer taps the channel and feeds back a signal, at a given energy level, for the purpose of jamming the transmitting sequence. Under a square-difference distortion measure which is to be maximized by the jammer and to be minimized by the transmitter and the receiver, this correspondence obtains the complete set of optimal (saddle-point) policies. The solution is essentially unique, and it is structurally different in three different regions in the parameter space, which are determined by the signal-to-noise ratios and relative magnitudes of the noise variances. The best (maximin) policy of the jammer is either to choose a linear function of the measurement he receives through channel-tapping, or to choose, in addition (and additively), an independent Gaussian noise sequence, depending on the region where the parameters lie. The optimal (minimax) policy of the transmitter is to amplify the input sequence to the given power level by a linear transformation, and that of the receiver is to use a Bayes estimator.

This paper is concerned with modeling and control strategy interaction in a multimodel context. The role of the observability structure in multiple deeisionmaker (DM) problems is examined. A procedure is developed for generating multimodel solutions based on certain deterministic information patterns. This is achieved by first explicitly identifying the state space structure induced by the observation sets of the DM's, and then overlapping appropriately the input space structure of each DM. Such a representation is used to identify the class of admissible strategies which generate multimodel solutions. Conditions, which depend on the information pattern, are obtained under which these multimodel solutions admit partial noninteraction among the DM's.

The design and evaluation of real-time implementable coding schemes for Gaussian multisource-multichannel communication systems are considered. The problem is to transmit the output from ann-dimensional Gaussian source over a memorylessm-dimensional Gaussian channel with power constraint and a mean-squared error distortion measure. Shannon performance bounds are obtained for this system through the optimum performance theoretically attainable (OPTA) relationship between the source distortion level\betaand the channel input power level\alpha. The optimum encoder is determined within the class of linear memoryless transformations, in which case the optimum decoder transformation becomes a least-mean-square estimator. The optimum linear encoder-decoder pair either coincides with or is very close to the Shannon bound in a number of significant cases.

The problem of optimal coding in a communication system with a noiseless feedback link and with noisy side information at the decoder is treated. The message is taken as a Gaussian random variable and both the main and the side channels are assumed to be continuous white-Gaussian. A linear encoding-decoding scheme is developed which attains the well-known performance bounds for the special cases of i) noiseless side information and ii) no side information.