In multi-agent reinforcement learning (MARL) and game theory, agents repeatedly interact and revise their strategies as new data arrives, producing a sequence of strategy profiles. This paper studies sequences of strategies satisfying a pairwise constraint inspired by policy updating in reinforcement learning, where an agent who is best responding in one period does not switch its strategy in the next period. This constraint merely requires that optimizing agents do not switch strategies, but does not constrain the non-optimizing agents in any way, and thus allows for exploration. Sequences with this property are called satisficing paths, and arise naturally in many MARL algorithms. A fundamental question about strategic dynamics is such: for a given game and initial strategy profile, is it always possible to construct a satisficing path that terminates at an equilibrium? The resolution of this question has implications about the capabilities or limitations of a class of MARL algorithms. We answer this question in the affirmative for normal-form games. Our analysis reveals a counterintuitive insight that suboptimal, and perhaps even reward deteriorating, strategic updates are key to driving play to equilibrium along a satisficing path.

Despite the success of generative adversarial networks (GANs) in generating visually appealing images, they are notoriously challenging to train. In order to stabilize the learning dynamics in minimax games, we propose a novel recursive reasoning algorithm: Level $k$ Gradient Play (Lv.$k$ GP) algorithm. Our algorithm does not require sophisticated heuristics or second-order information, as do existing algorithms based on predictive updates. We show that as k increases, Lv.$k$ GP converges asymptotically towards an accurate estimation of players' future strategy.Moreover, we justify that Lv.$\infty$ GP naturally generalizes a line of provably convergent game dynamics which rely on predictive updates. Furthermore, we provide its local convergence property in nonconvex-nonconcave zero-sum games and global convergence in bilinear and quadratic games. By combining Lv.$k$ GP with Adam optimizer, our algorithm shows a clear advantage in terms of performance and computational overhead compared to other methods. Using a single Nvidia RTX3090 GPU and 30 times fewer parameters than BigGAN on CIFAR-10, we achieve an FID of 10.17 for unconditional image generation within 30 hours, allowing GAN training on common computational resources to reach state-of-the-art performance.

This paper investigates asynchronous algorithms for distributedly seeking generalized Nash equilibria with delayed information in multiagent networks. In the game model, a shared affine constraint couples all players' local decisions. Each player is assumed to only access its private objective function, private feasible set, and a local block matrix of the affine constraint. We first give an algorithm for the case when each agent is able to fully access all other players' decisions. By using auxiliary variables related to communication links and the edge Laplacian matrix, each player can carry on its iteration asynchronously with only private data and possibly delayed information from its neighbors. Then, we consider the case when agents cannot know all other players' decisions, called a partial-decision information case. We introduce a local estimation of the overall agents' decisions and incorporate consensus dynamics on these local estimations. The two algorithms do not need any centralized clock coordination, fully exploit the local computation resource, and remove the idle time due to waiting for the "slowest" agent. Both algorithms are developed by preconditioned forward-backward operator splitting, and their convergence is shown by relating them to asynchronous fixed-point iterations, under proper assumptions and fixed and nondiminishing step-size choices. Numerical studies verify the algorithms' convergence and efficiency.

We consider the problem of efficient content delivery over networks in which individual nodes are equipped with content caching capabilities. We present a flexible methodology for the design of cooperative, decentralized caching strategies that can adapt to real-time changes in regional content popularity. This design methodology makes use of a recently proposed reduced consensus optimization scheme, in which a number of networked agents cooperate in locating the optimum of the sum of their individual, privately known objective functions. The outcome of the design is a set of dynamic update rules that stipulate how much and which portions of each content piece an individual network node ought to cache. In implementing these update rules, the nodes achieve a collectively optimal caching configuration through nearest-neighbor interactions and measurements of local content request rates only. Moreover, individual nodes need not be aware of the overall network topology or how many other nodes are on the network. The desired caching behavior is encoded in the design of individual nodes' costs and can incorporate a variety of network performance criteria. Using the proposed methodology, we develop a set of content-caching update rules designed to minimize the energy consumption of the network as a whole by dynamically trading off transport and caching energy costs in response to changes in content demand.

We consider the problem of designing content-caching strategies for the energy-efficient delivery of content such as video, over an internet-style network. We propose a method for the design of decentralized caching strategies that can adapt to real-time changes in regional content popularity. This design method is based on a recently proposed reduced consensus-optimization scheme wherein a number of agents networked over a general mesh topology cooperate in locating the optimum of the sum of their individual, privately known objective functions. The agents (i.e. network nodes with caching capabilities) achieve the collectively optimal caching configuration via nearest-neighbor interactions and measurements of local content request rates only. The caching behavior of individual nodes, which dynamically trades transport and caching energy costs in response to fluctuations in content demand, is designed to optimize the performance of the network as a whole.

This paper studies a constrained optical signal-to-noise ratio (OSNR) optimization problem in optical networks from the perspective of system performance. A system optimization problem is formulated with the objective of achieving an OSNR target for each channel while satisfying the total power constraint. In order to establish existence of a unique optimal solution, the conditions are derived, which can be used as a basis for an admission control scheme. The original problem is then converted to a relaxed system problem by using a barrier function and solved by a distributed iterative algorithm. Next, the system optimization framework developed is compared to the game theoretic one in [1]. The effects of parameters in both formulations are investigated to study efficiency of Nash equilibria in the OSNR game and pricing mechanisms affecting overall system performance. The theoretical analysis is supported by numerical simulations and experiments conducted on an optical fiber link.

This paper considers a generalized framework to study OSNR optimization-based end-to-end link level power control problems in optical networks. We combine favorable features of game-theoretical approach and central cost approach to allow different service groups within the network. We develop solutions concepts for both cases of empty and nonempty feasible sets. In addition, we derive and prove the convergence of a distributed iterative algorithm for different classes of users. In the end, we use numerical examples to illustrate the novel framework.

This paper considers a generalized framework to study OSNR optimization-based end-to-end link level power control problems in optical networks. We combine favorable features of game-theoretical approach and central cost approach to allow different service groups within the network. We develop a novel solution concept for the case of nonempty feasible set. In addition, we derive and prove the convergence of a distributed iterative algorithm for different classes of users. In the end, we use numerical examples to illustrate the novel framework.

In this paper, we introduce a class of linear non- cooperative games with linearly coupled constraints. It bears striking connections with classical linear systems theory and finds itself pervasively used in network engineering applications. In the second part of the paper, we will illustrate this type of games by an application from OSNR-based power control in optical networks, where we can view the slack variables as fictitious players. This powerful interpretation allows us to bridge over the theory and the issue of implementation in engineering.

This paper develops a Nash game towards optimizing optical signal-to-noise ratio (OSNR) in the presence of link capacity constraint. In optical wavelength-division multiplexing (WDM) networks, all wavelength-multiplexed channels in a link share the optical fiber. In order to limit nonlinear effects, the total power launched into a fiber has to be below a nonlinearity threshold. This can be regarded as the optical link capacity constraint. We formulate an extended OSNR Nash game that incorporates this underlying system constraint. The status of an optical link is considered directly in the cost function. Sufficient conditions for existence and uniqueness of the Nash equilibrium (NE) solution are given. Two iterative algorithms for channel power control are proposed to compute the NE solution: a parallel update algorithm (PUA) and a relaxed PUA (r-PUA). Their convergence is studied under different conditions, both theoretically and numerically.

We develop the first state-space model of a semiconductor optical amplifier that contains nonlinear gain compression and electronic parasitics. The new model adds an equivalent circuit to account for parasitics encountered during electronic SOA control, and polynomial nonlinear gain compression to account for spectral hole burning and carrier heating. Using the model we design a controller that regulates SOA output power by first relating the SOA’s source voltage to its gain, and then driving an optical control channel that keeps the input power constant.

We study the optical signal-to-noise ratio (OSNR) optimization problem in optical wavelength-division multiplexed (WDM) networks. This work extends our previous results in [1] on games with coupled constraints in optical links to generic WDM networks. We first develop a model for the network and an OSNR model for each link by investigating the interaction between the network and physical layers. The nonlinear threshold is considered as the link capacity constraint and we study the case in which channel powers are adjustable at the switching nodes. We formulate an OSNR Nash game with coupled utilities and constraints. Each player (channel) in the game maximizes its own utility function which is related to minimizing the individual OSNR degradation. We exploit this OSNR Nash game in two typical network topologies: multi-link topology and quasi-ring topology. The hierarchical decomposition approach leads to a lower-level game for channels with no coupled constraints and a higher-level optimization problem for the network.

Non-cooperative game theory is a powerful modeling tool for resource allocation problems in modern communication networks. However, practical concerns of capacity constraints and allocation efficiency have been a challenge for network engineers. In this paper, we base our results in the context of link-level power control of optical networks and propose a special form of games with an additional player to overcome these difficulties.We introduce a novel framework with a fictitious player (GFP) to extend the current OSNR Nash game framework with capacity constraints. We characterize a more analytically tractable solution in comparison to other approaches and propose a first-order iterative algorithm to find the equilibrium.

This paper considers the problem of optical signal-to-noise ratio (OSNR) optimization with link capacity constraints within a Nash game framework. In optical wavelength-division multiplexed (WDM) networks, all wavelength-multiplexed channels share the optical fiber. Even when individually channel parameters are adjusted, the total launched power has to be limited below the nonlinearity threshold. This can be regarded as the optical link capacity constraint. In the previous work of Pan & Pavel (2005), the authors have proposed an extended OSNR Nash game. Channel utility has been related to OSNR and the status of the optical link has been considered directly in channel cost function. The difficulty is that the unique Nash equilibrium (NE) solution of this OSNR Nash game is highly nonlinear and thus analytically intractable. The main contribution of this paper is to develop an iterative, distributed gradient algorithm towards finding the NE solution. The algorithm uses only local measurements and the current load of the network (or link). The authors proved that the iterative gradient algorithm converges globally to this NE solution under sufficient conditions.

This paper develops a Nash game formulation for optical signal-to-noise ratio (OSNR) in distributed optical links. The starting point is a recent network OSNR model developed for optically amplified links whereby channel powers are adjusted independently only at transmitter sites. A more general case is considered here where channel powers are also adjustable at intermediary dynamic sites, specific to optical networks. For this inherent distributed configuration a nested Nash game is formulated towards minimizing channel OSNR degradation along the link. Existence and uniqueness of the Nash equilibrium solution is shown and a recursive procedure for constructing it is given. Based on this, an iterative algorithm that is distributed with respect to both channels and -spans is proposed.

This paper develops a hierarchical iterative OSNR algorithm based on a game theory framework. A Nash game is formulated between channels with channel utility related to maximizing channel optical signal-to-noise ratio (OSNR). The OSNR game has coupled utilities and coupled constraints, such that total power is kept below the nonlinearity threshold. Solving directly this game requires coordination among all channels and is impractical in networks. A duality approach is used instead, based on the recent theoretical results in [16]. This method offers a natural way to hierarchically decompose the coupled Nash game into a lower-level Nash game with no coupled constraints, and a higher-level link optimization problem for pricing parameters. The lower-level Nash game is analytically tractable, and its solution can be iteratively found via an algorithm decentralized with respect to channels. The price is adjusted at the network higher-level so that channels are induced to cooperate towards satisfying the coupled total power constraint.

This paper addresses the problem of optical signal-to-noise ratio (OSNR) optimization in optical networks. An analytical OSNR network model is developed for a general multilink configuration, that includes the contribution of amplified spontaneous emission and crosstalk accumulation. The network OSNR optimization problem is formulated such that all channels maintain a desired individual OSNR level, while input optical power is minimized. Conditions for existence and uniqueness of the optimal solution are given. An iterative, distributed algorithm for channel power control is proposed, which is shown to converge geometrically to the optimal solution. The algorithm is valid for general network configurations, and uses only local measurements or decentralized feedback. Convergence is proved for both synchronous and asynchronous operation, which is particularly important for adaptation in a dynamic environment

This paper addresses the problem of optical signal-to-noise ratio (OSNR) optimization in optical networks. An analytical OSNR network model is developed for a general multi-link configuration, that includes the contribution of amplified spontaneous emission and crosstalk accumulation. An network OSNR optimization problem is formulated such that all channels maintain a desired individual OSNR level, while input optical power is minimized. An iterative, distributed algorithm for channel power control is proposed, which is shown to converge geometrically to the optimal solution. Convergence is proved for both synchronous and asynchronous operation.