Search

This study addresses a mobility network pricing problem in a competitive environment. We consider a multimodal transportation network where the links are operated by multiple profit-maximizing, mobility service providers (MSPs). We take the perspective of a network regulator that aims to increase ridership in a target mobility network by providing non-additive, path-based subsidies to travelers. We model paths’ attractiveness using generalized cost functions that combine path travel time and path cost, and we use linear elastic travel demand functions to capture the proportion of demand served by a path. MSPs are non-cooperative and adjust link fares according to the subsidy policy implemented by the regulator. The goal of the network regulator is to solve a budget-constrained mobility network pricing problem under MSP competition. This game-theoretical framework is modeled as a single-leader multi-follower game (SLMFG) wherein the leader player represents the network regulator and multiple follower players represent the MSPs. We conduct a theoretical analysis of this SLMFG by identifying necessary and sufficient conditions for the existence of solutions to the parameterized generalized Nash equilibrium problem (GNEP) that is played amongst MSPs. We show that this GNEP is jointly convex and we use this property to develop an exact numerical approach to solve the SLMFG based on customized branch-and-bound algorithms. Numerical results reveal the impact of MSP competition in this mobility network pricing problem and shed novel insights into the design of optimal path-based subsidy policies. © 2024 The Authors

The generalized Nash equilibrium problem (GNEP) is a kind of game to find strategies for a group of players such that each player’s objective function is optimized. Solutions for GNEPs are called generalized Nash equilibria (GNEs). In this paper, we propose a numerical method for finding GNEs of GNEPs of polynomials based on the polyhedral homotopy continuation and the Moment-SOS hierarchy of semidefinite relaxations. We show that our method can find all GNEs if they exist, or detect the nonexistence of GNEs, under some genericity assumptions. Some numerical experiments are made to demonstrate the efficiency of our method.

We consider the interplay between latency constrained applications and function-level resource management in a serverless edge computing environment. We develop a game theoretic model of the interaction between rate adaptive applications and a load balancing operator under a function-oriented pay-as-you-go pricing model. We show that under perfect information, the strategic interaction between the applications can be formulated as a generalized Nash equilibrium problem, and use variational inequality theory to prove that the game admits an equilibrium. For the case of imperfect information, we propose an online learning algorithm for applications to maximize their utility through rate adaptation and resource reservation. We show that the proposed algorithm can converge to equilibria and achieves zero regret asymptotically, and our simulation results show that the algorithm achieves good system performance at equilibrium, ensures fast convergence, and enables applications to meet their latency constraints., QC 20230523

Nowadays many companies have available large amounts of raw, unstructured data. Among Big Data enabling technologies, a central place is held by the MapReduce framework and, in particular, by its open source implementation, Apache Hadoop. For cost effectiveness considerations, a common approach entails sharing server clusters among multiple users. The underlying infrastructure should provide every user with a fair share of computational resources, ensuring that service level agreements (SLAs) are met and avoiding wastes. In this paper we consider mathematical models for the optimal allocation of computational resources in a Hadoop 2.x cluster with the aim to develop new capacity allocation techniques that guarantee better performance in shared data centers. Our goal is to get a substantial reduction of power consumption while respecting the deadlines stated in the SLAs and avoiding penalties associated with job rejections. The core of this approach is a distributed algorithm for runtime capacity allocation, based on Game Theory models and techniques, that mimics the MapReduce dynamics by means of interacting players, namely the central Resource Manager and Class Managers.

Mobile Network Operators (MNOs) are nowadays forced to continuously invest in their network infrastructure to keep up with the increasing bandwidth demand and traffic load coming from mobile users. In this context, MNOs have to face the strategic problem of whether to invest on their own or deploy shared networks. We address here the problem of Radio Access Network (RAN) and spectrum sharing in 4G mobile networks. Namely, we consider the case in which multiple MNOs are planning to deploy small cell Base Stations to improve their current network infrastructure; the deployment investment may be shared with other MNOs, thus giving rise to shared RANs. The RAN and spectrum sharing problem is formalized as a Generalized Nash Equilibrium Problem, where the strategy of each MNO in the game is twofold: selecting a coalition (whom to cooperate) and the fraction of the coalition cost to pay, with the goal of maximizing the individual return on investment. The proposed approach is leveraged to characterize the stable coalitions and their respective cost division policies for various network and economic conditions.

Mobile Network Operators (MNOs) are nowadays forced to continuously invest in their network infrastructure to keep up with the increasing bandwidth demand and traffic load coming from mobile users. In this context, MNOs have to face the strategic problem of whether to invest on their own or deploy shared networks. We address here the problem of Radio Access Network (RAN) and spectrum sharing in 4G mobile networks. Namely, we consider the case in which multiple MNOs are planning to deploy small cell Base Stations to improve their current network infrastructure; the deployment investment may be shared with other MNOs, thus giving rise to shared RANs. The RAN and spectrum sharing problem is formalized as a Generalized Nash Equilibrium Problem, where the strategy of each MNO in the game is twofold: selecting a coalition (whom to cooperate) and the fraction of the coalition cost to pay, with the goal of maximizing the individual return on investment. The proposed approach is leveraged to characterize the stable coalitions and their respective cost division policies for various network and economic conditions.

The envisioned smart grid aims at improving the interaction between the supply-and the demand-side of the electricity network, creating unprecedented possibilities for optimizing the energy usage at different levels of the grid. In this paper, we propose a distributed demand-side management (DSM) method intended for smart grid users with load prediction capabilities, who possibly employ dispatchable energy generation and storage devices. These users participate in the day-ahead market and are interested in deriving the bidding, production, and storage strategies that jointly minimize their expected monetary expense. The resulting day-ahead grid optimization is formulated as a generalized Nash equilibrium problem (GNEP), which includes global constraints that couple the users' strategies. Building on the theory of variational inequalities, we study the main properties of the GNEP and devise a distributed, iterative algorithm converging to the variational solutions of the GNEP. Additionally, users can exploit the reduced uncertainty about their energy consumption and renewable generation at the time of dispatch. We thus present a complementary DSM procedure that allows them to perform some unilateral adjustments on their generation and storage strategies so as to reduce the impact of their real-time deviations with respect to the amount of energy negotiated in the day-ahead. Finally, numerical results in realistic scenarios are reported to corroborate the proposed DSM technique.

Cloud computing is an emerging technology that allows to access computing resources on a pay-per-use basis. The main challenges in this area are the efficient performance management and the energy costs minimization. In this paper we model the service provisioning problem of Cloud Platform-as-a-Service systems as a Generalized Nash Equilibrium Problem and show that a potential function for the game exists. Moreover, we prove that the social optimum problem is convex and we derive some properties of social optima from the corresponding Karush-Kuhn-Tucker system. Next, we propose a distributed solution algorithm based on the best response dynamics and we prove its convergence to generalized Nash equilibria. Finally, we numerically evaluate equilibria in terms of their efficiency with respect to the social optimum of the Cloud by varying our algorithm initial solution. Numerical results show that our algorithm is scalable and very efficient and thus can be adopted for the run-time management of very large scale systems.

The envisioned smart grid aims at improving the interaction between the supply-and the demand-side of the electricity network, creating unprecedented possibilities for optimizing the energy usage at different levels of the grid. In this paper, we propose a distributed demand-side management (DSM) method intended for smart grid users with load prediction capabilities, who possibly employ dispatchable energy generation and storage devices. These users participate in the day-ahead market and are interested in deriving the bidding, production, and storage strategies that jointly minimize their expected monetary expense. The resulting day-ahead grid optimization is formulated as a generalized Nash equilibrium problem (GNEP), which includes global constraints that couple the users' strategies. Building on the theory of variational inequalities, we study the main properties of the GNEP and devise a distributed, iterative algorithm converging to the variational solutions of the GNEP. Additionally, users can exploit the reduced uncertainty about their energy consumption and renewable generation at the time of dispatch. We thus present a complementary DSM procedure that allows them to perform some unilateral adjustments on their generation and storage strategies so as to reduce the impact of their real-time deviations with respect to the amount of energy negotiated in the day-ahead. Finally, numerical results in realistic scenarios are reported to corroborate the proposed DSM technique.

Cloud computing is an emerging technology that allows to access computing resources on a pay-per-use basis. The main challenges in this area are the efficient performance management and the energy costs minimization. In this paper we model the service provisioning problem of Cloud Platform-as-a-Service systems as a Generalized Nash Equilibrium Problem and show that a potential function for the game exists. Moreover, we prove that the social optimum problem is convex and we derive some properties of social optima from the corresponding Karush-Kuhn-Tucker system. Next, we propose a distributed solution algorithm based on the best response dynamics and we prove its convergence to generalized Nash equilibria. Finally, we numerically evaluate equilibria in terms of their efficiency with respect to the social optimum of the Cloud by varying our algorithm initial solution. Numerical results show that our algorithm is scalable and very efficient and thus can be adopted for the run-time management of very large scale systems.

The envisioned smart grid aims at improving the interaction between the supply-and the demand-side of the electricity network, creating unprecedented possibilities for optimizing the energy usage at different levels of the grid. In this paper, we propose a distributed demand-side management (DSM) method intended for smart grid users with load prediction capabilities, who possibly employ dispatchable energy generation and storage devices. These users participate in the day-ahead market and are interested in deriving the bidding, production, and storage strategies that jointly minimize their expected monetary expense. The resulting day-ahead grid optimization is formulated as a generalized Nash equilibrium problem (GNEP), which includes global constraints that couple the users' strategies. Building on the theory of variational inequalities, we study the main properties of the GNEP and devise a distributed, iterative algorithm converging to the variational solutions of the GNEP. Additionally, users can exploit the reduced uncertainty about their energy consumption and renewable generation at the time of dispatch. We thus present a complementary DSM procedure that allows them to perform some unilateral adjustments on their generation and storage strategies so as to reduce the impact of their real-time deviations with respect to the amount of energy negotiated in the day-ahead. Finally, numerical results in realistic scenarios are reported to corroborate the proposed DSM technique., Peer Reviewed, Postprint (published version)

This paper deals with the generalized Nash equilibrium problem (GNEP), i.e. a noncooperative game in which the strategy set of each player, as well as his payoff function, depends on the strategies of all players. We consider an equivalent optimization reformulation of GNEP using a regularized Nikaido-Isoda function so that solutions of GNEP coincide with global minima of the optimization problem. We then propose a derivative-free descent type method with inexact line search to solve the equivalent optimization problem and we prove that our algorithm is globally convergent. The convergence analysis is not based on conditions guaranteeing that every stationary point of the optimization problem is a solution of GNEP. Finally, we present the performance of our algorithm on some examples.

This paper deals with the generalized Nash equilibrium problem (GNEP), i.e. a noncooperative game in which the strategy set of each player, as well as his payoff function, depends on the strategies of all players. We consider an equivalent optimization reformulation of GNEP using a regularized Nikaido-Isoda function so that solutions of GNEP coincide with global minima of the optimization problem. We then propose a derivative-free descent type method with inexact line search to solve the equivalent optimization problem and we prove that our algorithm is globally convergent. The convergence analysis is not based on conditions guaranteeing that every stationary point of the optimization problem is a solution of GNEP. Finally, we present the performance of our algorithm on some examples.

We present a new covering theorem for a nonlinear mapping on a convex cone, under the assumptions weaker than the classical Robinson’s regularity condition. When the latter is violated, one cannot expect to cover the entire neighborhood of zero in the image space. Nevertheless, our covering theorem gives rise to natural conditions guaranteeing stability of a solution of a cone-constrained equation subject to wide classes of perturbations, and allowing for nonisolated solutions, and for systems with the same number of equations and variables. These features make these results applicable to various classes of variational problems, like nonlinear complementarity problems. We also consider the related stability issues for generalized Nash equilibrium problems. © 2017, Springer Science+Business Media B.V.