Search

We develop a model for contagion risks and optimal security investment in a directed network of interconnected agents with heterogeneous degrees, loss functions and security profiles. Our model generalizes much of contagion models in the literature; in particular the independent cascade model and the linear threshold model. We state various limit theorems on the final size of infected agents in the case of random networks with given vertex degrees for finite and infinite variance degree distributions. The results allow us to derive a resilience condition of the network to the infection of a large group of agents and quantify how contagion amplifies small shocks to the network. We show that when the degree distribution has infinite variance and, highly correlated in- and out-degrees, then even when agents have high thresholds, a sub-linear fraction of initially infected agents is enough to trigger the infection of a positive fraction. We also show how these results are sensitive to vertex and edge percolation (immunization). We then study the asymptotic Nash equilibrium and socially optimal security investment. In the asymptotic limit, agents' risk depends on all other agents' investment through an aggregate quantity, that we call network vulnerability. The limit theorems allow us to capture the impact of one class of agents' decision on the overall network vulnerability. Based on our results, the vulnerability is semi-analytic allowing for a tractable Nash equilibrium. We give sufficient conditions for investment in equilibrium to be monotone in the network vulnerability. When investment is monotone, we show that the (asymptotic) Nash equilibrium is unique. In the particular example of two types core-periphery agents, we exhibit a strong effect of the cost heterogeneity and in particular non-monotonous investment as a function of costs.

Driven by the increasing demand of real-time mobile application processing, Multi-access Edge Computing (MEC) has been envisioned as a promising paradigm for pushing computational resources to network edges. In this paper, we investigate an MEC network enabled by Unmanned Aerial Vehicles (UAV), and consider both the multi-user computation offloading and edge server deployment to minimize the system-wide computation cost under dynamic environment, where users generate tasks according to time-varying probabilities. We decompose the minimization problem by formulating two stochastic games for multi-user computation offloading and edge server deployment respectively, and prove that each formulated stochastic game has at least one Nash Equilibrium (NE). Two learning algorithms are proposed to reach the NEs with polynomial-time computational complexities. We further incorporate these two algorithms into a chess-like asynchronous updating algorithm to solve the system-wide computation cost minimization problem. Finally, performance evaluations based on real-world data are conducted and analyzed, corroborating that the proposed algorithms can achieve efficient computation offloading coupled with proper server deployment under dynamic environment for multiple users and MEC servers.

Multi-access edge computing (MEC) has been recently considered in challenging environments lacking available terrestrial infrastructures by extending the computing resources to the air for further enhancing the computation capability of the new aerial user equipment (AUE). Additionally, wireless power transfer (WPT) is a promising solution to prolong the battery lifetime of energy-constrained wireless devices like AUEs. In this paper, we investigate the integration of laser-beamed WPT in the high-altitude platform (HAP) aided MEC systems for the HAP-connected AUEs. By discretizing the three-dimensional coverage space of the HAP, we present a multi-tier tile grid-based spatial structure to provide aerial locations for laser charging. With this setup, we identify a new privacy vulnerability caused by the openness during the air-to-air transmission of WPT signaling messages in the presence of a terrestrial adversary. A privacy-aware laser-powered aerial MEC framework is developed that addresses this vulnerability and enhances the location privacy of AUEs for laser WPT. Specifically, the interaction between the HAP as a defender and the adversary in their tile grid allocation as charging locations to AUEs is formulated as a Colonel Blotto game, which models the competition of the players for limited resources over multiple battlefields for a finite time horizon. Moreover, we derive the mixed-strategy Nash equilibria of the tile grid allocation game for both symmetric and asymmetric tile grids between the defender and the adversary. Simulations results show that the proposed framework significantly outperforms the design baselines with a given privacy protection level in terms of system-wide expected total utilities.

Unmanned Aerial Vehicles (UAVs) have been utilized to serve on-ground users with various services, e.g., computing, communication and caching, due to their mobility and flexibility. The main focus of many recent studies on UAVs is to deploy a set of homogeneous UAVs with identical capabilities controlled by one UAV owner/company to provide services. However, little attention has been paid to the issue of how to enable different UAV owners to provide services with differentiated service capabilities in a shared area. To address this issue, we propose a multi-agent imitation learning enabled UAV deployment approach to maximize both profits of UAV owners and utilities of on-ground users. Specially, a Markov game is formulated among UAV owners and we prove that a Nash equilibrium exists based on the full knowledge of the system. For online scheduling with incomplete information, we design agent policies by imitating the behaviors of corresponding experts. A novel neural network model, integrating convolutional neural networks, generative adversarial networks and a gradient-based policy, can be trained and executed in a fully decentralized manner with a guaranteed -Nash equilibrium. Performance results show that our algorithm has significant superiority on average profits, utilities and execution time compared with other representative algorithms.

The price of anarchy is the most well-known measure for quantifying the inefficiency of equilibrium flows in traffic networks and routing games. In this work, we give unifying price of anarchy bounds for atomic and non-atomic parallel link routing games with polynomial cost functions under various cost objectives including the arithmetic mean, geometric mean and worst-case cost objective. We do this through the study of the generalized p-mean as cost objective, and obtain upper bounds on the price of anarchy in terms of this parameter p. Our bounds unify existing results from the literature, and, in particular, give alternative proofs for price of anarchy results in parallel link routing games with polynomial cost functions under the geometric mean objective obtained by Vinci et al. (ACM Trans Econ Comput 10(2):41, 2022). We recover those simply as a limiting case. To the best of our knowledge, these are the first price of anarchy bounds that capture multiple cost objectives simultaneously in a closed-form expression.

Learning automata (LA) with artificially absorbing barriers was a completely new horizon of research in the 1980s (Oommen, 1986). These new machines yielded properties that were previously unknown. More recently, absorbing barriers have been introduced in continuous estimator algorithms so that the proofs could follow a martingale property, as opposed to monotonicity (Zhang et al., 2014), (Zhang et al., 2015). However, the applications of LA with artificial barriers are almost nonexistent. In that regard, this article is pioneering in that it provides effective and accurate solutions to an extremely complex application domain, namely that of solving two-person zero-sum stochastic games that are provided with incomplete information. LA have been previously used (Sastry et al., 1994) to design algorithms capable of converging to the game's Nash equilibrium under limited information. Those algorithms have focused on the case where the saddle point of the game exists in a pure strategy. However, the majority of the LA algorithms used for games are absorbing in the probability simplex space, and thus, they converge to an exclusive choice of a single action. These LA are thus unable to converge to other mixed Nash equilibria when the game possesses no saddle point for a pure strategy. The pioneering contribution of this article is that we propose an LA solution that is able to converge to an optimal mixed Nash equilibrium even though there may be no saddle point when a pure strategy is invoked. The scheme, being of the linear reward-inaction ( $L_{R-I}$ ) paradigm, is in and of itself, absorbing. However, by incorporating artificial barriers, we prevent it from being ``stuck'' or getting absorbed in pure strategies. Unlike the linear reward-εpenalty ( $L_{R-ε P}$ ) scheme proposed by Lakshmivarahan and Narendra almost four decades ago, our new scheme achieves the same goal with much less parameter tuning and in a more elegant manner. This article includes the nontrial proofs of the theoretical results characterizing our scheme and also contains experimental verification that confirms our theoretical findings.

In this paper, a novel data offloading decision-making framework is proposed, where users have the option to partially offload their data to a complex Multi-access Edge Computing (MEC) environment, consisting of both ground and UAV-mounted MEC servers. The problem is treated under the perspective of risk-aware user behavior as captured via prospect-theoretic utility functions, while accounting for the inherent computing environment uncertainties. The UAV-mounted MEC servers act as a common pool of resources with potentially superior but uncertain payoff for the users, while the local computation and ground server alternatives constitute safe and guaranteed options, respectively. The optimal user task offloading to the available computing choices is formulated as a maximization problem of each user's satisfaction, and confronted as a non-cooperative game. The existence and uniqueness of a Pure Nash Equilibrium (PNE) are proven, and convergence to the PNE is shown. Detailed numerical results highlight the convergence of the system to the PNE in few only iterations, while the impact of user behavior heterogeneity is evaluated. The introduced framework's consideration of the user risk-aware characteristics and computing uncertainties, results to a sophisticated exploitation of the system resources, which in turn leads to superior users' experienced performance compared to alternative approaches.

We study an optimal targeting problem for super-modular games with binary actions and finitely many players. The considered problem consists in the selection of a subset of players of minimum size such that, when the actions of these players are forced to a controlled value while the others are left to repeatedly play a best response action, the system will converge to the greatest Nash equilibrium of the game. Our main contributions consist in showing that the problem is NP-complete and in proposing an efficient iterative algorithm with provable convergence properties for its solution. We discuss in detail the special case of network coordination games and its relation with the notion of cohesiveness. Finally, we show with simulations the strength of our approach with respect to naive heuristics based on classical network centrality measures.

This paper considers remote state estimation in cyber-physical systems (CPSs) with multiple sensors. Each plant is modeled by a discrete-time stochastic linear system with measurements of each sensor transmitted to the corresponding remote estimator over a shared communication network when their securities are interdependent due to network induced risks. A dynamic nonzero-sum game with asymmetric information is formulated in which each sensor subject to a resource budget constraint needs to decide whether to invest in security for sending data packets, taking the behaviors of other sensors into account. To overcome the difficulty in characterizing or computing the Nash equilibria (NE), the game with asymmetric information is transformed into another game with symmetric information such that the equilibrium of the original game can be obtained by solving the equilibrium of the new game. Under certain conditions, we devise a backward induction algorithm to obtain a subclass of NE of the original game, known as common information based Markov perfect equilibria (CIBMPE). Finally, a numerical example is provided to illustrate the results obtained.

Теоретико-игровые модели принятия решений являются вполне приемлемыми для социально-экономических задач. Это связано с тем, что в моделировании возникают конкуренция, неопределенность, риски, отсутствие информации о поведении соперника и т.д. Для таких сценариев происходит интеграция статистической и антагонистической игры, а также определяется наличие связи между квадратичным программированием и игрой в смешанных стратегиях.В данной работе представлен подход, который заключается в использовании теоретико-игровых методов при решении оптимизационной нелинейной задачи и принятии решения о вложении средств. Особенностью данного исследования является практический аспект, в котором наглядно показана возможность применения такого метода в реальной ситуации, что, зачастую, бывает достаточно сложно сделать в теоретико-игровом моделировании., Game-theoretic models of decision-making are well suited for socio-economic problems. This is because there is competition, uncertainty, risks, lack of information about the behaviour of the opponent, etc. in the simulation. For such scenarios, the integration of statistical and antagonistic games occurs, and the relationship between quadratic programming and mixed-strategy games is determined.This work presents an approach which consists in using game-theoretic methods when solving an optimization nonlinear problem and making an investment decision. A special point of this research is the practical aspect, which clearly demonstrates the possibility of applying such a method in a real situation, which is often quite difficult to do in game-theoretic modelling., Международный научно-исследовательский журнал, Выпуск 7 (133) 2023

We formally assume that players in a game consider Nash Equilibrium (NE) the behavioral norm. In finite games of perfect information this leads to a refinement of NE: Faithful Nash Equilibrium (FNE). FNE is outcome equivalent to NE of the trimmed game, obtained by restricting the original tree to its NE paths. Thus, it always exists but it need not be unique. Iterating the norm ensures uniqueness of outcome. FNE may violate backward induction when subgame perfection requires play according to the SPE following a deviation from it. We thus provide an alternative view of tenable threats in equilibrium analysis.

In a simple two-country Ricardian economy with public infrastructures, we consider a simultaneous and non-cooperate game between governments with respect to public infrastructure supply. Then it is shown that a country with larger (smaller) factor endowment exports a good whose production is more (less) dependent on public infrastructures, and both countries will gain from trade as long as factor endowment differs between countries. However, the following special features appear. (i) Any incompletely specialising country produces two goods at an inner point of the production possibility set. (ii) If factor endowment is the same between countries, the trading equilibrium is attained by the pattern of specialisation such that each country specialises in one good different from each other and both countries become better off. Which country specialises in which good is indeterminate. The result shows a typical case of symmetric breaking. JEL codes: F11, H41

In this second part of our work, we study the steady state of the population and the social utility for the three dynamics SSD, NBRD and NRPM; which were introduced in the first part. We provide sufficient conditions on the network based on a maximum payoff density parameter of each node under which there exists a unique Nash equilibrium. We then utilize positive correlation properties of the dynamics to reduce the flow graph in order to provide an upper bound on the steady state social utility. Finally we extend the idea behind the sufficient condition for the existence of a unique Nash equilibrium to partition the graph appropriately in order to provide a lower bound on the steady state social utility. We also illustrate interesting cases as well as our results using simulations.

We consider the distributed scheduling problem on parallel machines with the central objective of maximizing the number of on-time jobs. Jobs are self-interested utility-maximizers that can choose the machines they are processed on and are exclusively interested in reducing their own private objective function. Each machine processes the jobs according to a local policy. We discuss Nash equilibria in the resulting schedules and perform a thorough analysis of the resulting (absolute) prices of anarchy for various parallel machine environments, utilities of the agents, and local policies of the machines. We show that local policies that are based on simple sorting-based procedures like shortest processing time first (SPT) and earliest due date first (EDD) lead to big losses in welfare compared to the global optimum. However, when employing Moore-Hodgson’s algorithm as a local policy, we can prove a price of anarchy of ( 2 m − 1 ) / m for identical machines and a price of anarchy of 2 for related and unrelated parallel machines. Moreover, we show how these results can be used to prove approximation ratios for greedy scheduling algorithms. This paper is the first to prove approximation ratios for two greedy scheduling procedures, turning them from simple heuristics into actual approximation ratios with a provable approximation ratio.

A generalized game is a strategic situation in which agents’ behavior restricts their opponents’ available action choices, giving rise to interdependencies in terms of what strategy profiles remain mutually feasible. This paper proposes a novel example of a simple generalized game in which the well-known convexity, compactness, continuity, and concavity assumptions are satisfied, but no Nash equilibrium exists. This finding reinforces that certain additional conditions appearing in the literature (primarily, the lower hemicontinuity of feasibility correspondences) are indispensable for equilibrium existence and must be considered as supplemental desiderata beyond the usual regularity conditions. Implications for institutional design are discussed.

We study the optimal management of evolving hierarchies of revenue-generating agents. The initiator invests into expanding the hierarchy by adding another agent, who will bring revenues to the joint venture and who will invest herself into expanding the hierarchy further, and so on. The higher the investments (which are private information), the higher the probability of expanding the hierarchy. An allocation scheme specifies how revenues are distributed, as the hierarchy evolves. We obtain schemes that are socially optimal and initiator-optimal, respectively. Our results have potential applications for blockchain, cryptocurrencies, social mobilization, and multilevel marketing. This paper was accepted by Manel Baucells, behavioral economics and decision analysis.

In this article, we study the optimal control problem arising from the mean-field game formulation of the collective decision-making in honeybee swarms. A population of homogeneous players (the honeybees) has to reach consensus on one of two options. We consider three states: the first two represent the available options (or strategies), and the third one represents the uncommitted state. We formulate the continuous-time discrete-state mean-field game model. The contributions of this article are the following: 1) we propose an optimal control model where players have to control their transition rates to minimize a running cost and a terminal cost, in the presence of an adversarial disturbance; 2) we develop a formulation of the micro–macro model in the form of an initial-terminal value problem with switched dynamics; 3) we study the existence of stationary solutions and the mean-field Nash equilibrium for the resulting switched system; 4) we show that under certain assumptions on the parameters, the game may admit periodic solutions; and 5) we analyze the resulting microscopic dynamics in a structured environment where a finite number of players interact through a network topology.

Due to the nature of high mobility and dynamic network topology, Intrusion Detection Systems (IDSs) in Vehicular Ad-hoc Networks (VANETs) face lots of challenges, especially in balancing the accuracy and efficiency of detection. Current researches about the deployment of IDSs in VANETs mainly focus on a tradeoff between the effectiveness and efficiency, but few efforts have been done about the adaptability of the tradeoff in the changeable networks. Thus, we address two crucial problems: 1) how to perceive the environmental change in the perspective of an IDS? 2) how to make the IDS adaptive in different scenarios? In this paper, a Bayesian Game theory and Deep Q-learning Network-based IDS is proposed for VANETs, called GaDQN-IDS. The interactions between an IDS and attackers are formulated as a dynamic intrusion detection game, in which the IDS decides either to just adjust the tradeoff between the accuracy and efficiency or to be retrained completely when its detection capacity has declined. The Nash Equilibria (NE) of the game is derived to reveal how the optimal decision of the IDS depends on the detection performance and road conditions. Moreover, a Deep Q-learning Network (DQN)-Adjustment is proposed to realize the self-adaptation of the IDS in the dynamic game, while an Error Priority Learning (EPL) is further designed for IDS retraining in changing VANETs. Simulation results show that the GaDQN-IDS has better performance than other existing IDSs with higher detection rate as well as lower detection time and overhead.

Human-machine shared control has become an effective cutting-edge approach to enhance driving safety and assist in the transition from manual to autonomous driving. However, driving authority allocation when conflict occurs between a human driver and a machine still represents an intractable problem. In order to solve this problem, this paper proposes an adaptive steering torque coupling framework to achieve the human-machine shared control with conflict resolution. Additionally, a driver trajectory prediction method considering human-machine interaction is established based on the extended state observer and long short-term memory network. In addition, the human-machine shared steering system is modeled based on a non-cooperative dynamic game by the prediction model method for path-tracking, and the obtained solution is given according to the Nash equilibrium. Particularly, a dynamic load allocation approach is designed to resolve human-machine conflict and relax the driver. In order to verify the strategy formed based on the proposed framework, a driver-in-the-loop experiment is conducted. The experimental results reveal that the proposed strategy can effectively reduce the human-machine conflict torque and ensure a driver has absolute control authority. Furthermore, the proposed strategy can also transfer the driving workload between the driver and machine, provide driving experience, or improve driving comfort when there is no conflict.

Renewable resources are starting to constitute a growing portion of the total generation mix of the power system. A key difference between renewables and traditional generators is that many renewable resources are managed by individuals, especially in the distribution system. In this paper, we study the capacity investment and pricing problem, where multiple renewable producers compete in a decentralized market. It is known that most deterministic capacity games tend to result in very inefficient equilibria, even when there are a large number of similar players. In contrast, we show that due to the inherent randomness of renewable resources, the equilibria in our capacity game becomes efficient as the number of players grows and coincides with the centralized decision from the social planner's problem. This result provides a new perspective on how to look at the positive influence of randomness in a game framework as well as its contribution to resource planning, scheduling, and bidding. We validate our results by simulation studies using real world data., Appears in IEEE Transactions on Sustainable Computing

Switch-based adaptive dynamic programming (ADP) is an optimal control problem in which a cost must be minimized by switching among a family of dynamical modes. When the system dimension increases, the solution to switch-based ADP is made prohibitive by the exponentially increasing structure of the value function approximator and by the exponentially increasing modes. This technical correspondence proposes a distributed computational method for solving switch-based ADP. The method relies on partitioning the system into agents, each one dealing with a lower dimensional state and a few local modes. Each agent aims to minimize a local version of the global cost while avoiding that its local switching strategy has conflicts with the switching strategies of the neighboring agents. A heuristic algorithm based on the consensus dynamics and Nash equilibrium is proposed to avoid such conflicts. The effectiveness of the proposed method is verified via traffic and building test cases.

Edge computing, as an emerging and prospective computing paradigm, allows a service provider to serve its users by allocating them to nearby edge servers delivering services with low latency. From the service provider's perspective, a cost-effective service user allocation aims to allocate maximum service users to minimum edge servers. Such an allocation leverages multi-tenancy to reduce the resources hired by the service provider for serving the service users. However, the allocation of excessive service users to an edge server may result in severe interference and consequently impact their data rates. There is a trade-off between multi-tenancy and interference in the pursuit of a cost-effective service user allocation. In this paper, we formally model this service user allocation (SUA) problem. To solve the SUA problem effectively and efficiently, we propose a game-theoretic approach, namely MI-SUAGame, to formulate the SUA problem as a potential game. We analyze the game and prove its admission to a Nash equilibrium. Then, a novel decentralized algorithm is designed for finding a Nash equilibrium in the game as the solution to the SUA problem. The performance of MI-SUAGame is theoretically analyzed and experimentally evaluated against the state-of-the-art approach.

When a set of self-interested users shares multiple resources in a distributed system, we face the problem of allocating resources, called the load balancing problem. In particular, load balancing is defined as allocating the load to the servers of the distributed system such that jobs' response time is minimized, and the utilization of servers is improved. In this paper, the load balancing problem in a distributed system consists of a finite set of servers, and a finite set of users is studied. The load balancing problem considered here is a bi-objective problem with two highly probable conflicting objectives: (i) minimizing jobs' response time (ii) providing the fair utilization of servers. In order to satisfy these two objectives simultaneously, both the objectives are considered in an integrated manner. Next, the load balancing problem is formulated as a noncooperative game; and to solve the game (i.e., to find the Nash equilibrium), a distributed load balancing algorithm (DLBA) is proposed. An experimental study is carried out to ascertain the efficacy of the proposed DLBA. Further, we compare DBLA with three existing load balancing approaches to evaluate its comparative effectiveness. The experimental results validate the effectiveness of the DLBA over the existing approaches.

In this article, we study a variation of the active target-attacker-defender (ATAD) differential game involving multiple targets, an attacker, and a defender. Our model allows for 1) a capability of the defender to switch roles from rescuer (rendezvous with all the targets) to interceptor (intercepts the attacker) and vice versa and 2) the attacker to continuously pursue the closest target (which can change during the course of the game). We assume that the mode of the defender (rescue or interception) defines the mode of the game itself. Using the framework of Games of a Degree, we first analyze the game within each mode. More specifically, the objectives of the players are taken as a combination of weighted Euclidean distances and penalties on their control efforts. We model the interaction of the players within each mode as a linear quadratic differential game (LQDG) and obtain the open-loop Nash equilibrium strategies. We then use the receding horizon approach to enable switching between the modes to obtain switching strategies for the players. By partitioning the matrices associated with the Riccati differential equations we obtain geometric characterization of the trajectories of the players. Furthermore, under mild restrictions on the problem parameters and for a particular choice of the defender's switching function we show that interception mode is invariant. We illustrate our results with numerical simulations. Experimental results involving multiple autonomous differential drive mobile robots are presented.

In this article, the problem of distributed generalized Nash equilibrium (GNE) seeking in noncooperative games is investigated via multiagent networks, where each player aims to minimize his or her own cost function with a nonsmooth term. Each player's cost function and feasible action set in the noncooperative game are both determined by actions of others who may not be neighbors, as well as his/her own action. Particularly, feasible action sets are constrained by private convex inequalities and shared linear equations. Each player can only have access to his or her own cost function, private constraint, and a local block of shared constraints, and can only communicate with his or her neighbours via a digraph. To address this problem, a novel continuous-time distributed primal-dual algorithm involving Clarke's generalized gradient is proposed based on consensus algorithms and the primal-dual algorithm. Under mild assumptions on cost functions and graph, we prove that players' actions asymptotically converge to a GNE. Finally, a simulation is presented to demonstrate the effectiveness of our theoretical results.

Mobile edge computing is emerging to provide cloud-computing capabilities to mobile users, so that they can offload computation intensive tasks to close proximity for execution. However, most existing works imply that a transmission-finished task still occupies the channel until all users on the same channel finish the transmission, leading to severe channel resource waste. To solve this problem, we propose an efficient computation offloading mechanism which releases the channel resources of transmission-finished tasks for transmission-unfinished tasks, and aims to minimize the response time and energy consumption for each user. Specifically, we formulate the computation offloading problem as a game, analyze its structural properties and show how it possesses a Nash equilibrium and admits the finite improvement property, in the cases of elastic cloud and non-elastic cloud respectively. We then propose a Distributed Multi-channel Computation Offloading (DMCO) algorithm, which can converge to a Nash equilibrium, and find the upper bound of the convergence time. We further evaluate the performance of DMCO using the price of anarchy. Numerical results show that DMCO scales well with the number of users, and outperforms existing works, for example, benefits 13.3% more users and reduces cost by 23.7% than CO, one of the best existing works.

Edge computing (EC) is an emerging paradigm that extends cloud computing by pushing computing resources onto edge servers that are attached to base stations or access points at the edge of the cloud in close proximity with end-users. Due to edge servers' geographic distribution, the EC paradigm is challenged by many new security threats, including the notorious distributed Denial-of-Service (DDoS) attack. In the EC environment, edge servers usually have constrained processing capacities due to their limited sizes. Thus, they are particularly vulnerable to DDoS attacks. DDoS attacks in the EC environment render existing DDoS mitigation approaches obsolete with its new characteristics. In this paper, we make the first attempt to tackle the edge DDoS mitigation (EDM) problem. We model it as a constraint optimization problem and prove its NP-hardness. To solve this problem, we propose an optimal approach named EDMOpti and a novel game-theoretical approach named EDMGame for mitigating edge DDoS attacks. EDMGame formulates the EDM problem as a potential EDM Game that admits a Nash equilibrium and employs a decentralized algorithm to find the Nash equilibrium as the solution. Through theoretical analysis and experimental evaluation, we demonstrate that our approaches can solve the EDM problem effectively and efficiently.

Edge Computing, extending cloud computing, has emerged as a prospective computing paradigm. It allows a SaaS (Software-as-a-Service) vendor to allocate its users to nearby edge servers to minimize network latency and energy consumption on their devices. From the SaaS vendor's perspective, a cost-effective SaaS user allocation (SUA) aims to allocate maximum SaaS users on minimum edge servers. However, the allocation of excessive SaaS users to an edge server may result in severe interference and consequently impact SaaS users data rates. In this paper, we formally model this problem and prove that finding the optimal solution to this problem is NP-hard. Thus, we propose ISUAGame, a game-theoretic approach that formulates the interference-aware SUA (ISUA) problem as a potential game. We analyze the game and show that it admits a Nash equilibrium. Then, we design a novel decentralized algorithm for finding a Nash equilibrium in the game as a solution to the ISUA problem. The performance of this algorithm is theoretically analyzed and experimentally evaluated. The results show that the ISUA problem can be solved effectively and efficiently.

To support the increasing computation-intensive applications in the Internet of Things (IoT), edge computing is introduced to provide mobile devices computing resources for performing low-latency tasks. Therefore, how to design an effective and secure computing resource allocation mechanism is attracting increasing attention. A lot of works have been done to design an effective computational resource market for IoT, but the problems of vulnerability and inefficiency still exist. In this paper, we propose a two-level Stackelberg game-based computing resource trading mechanism for mobile IoT devices with a credit-based payment approach, which is implemented by smart contracts on blockchain. In our model, the Stackelberg game consists of two levels, i.e., leader-level and user-level. In the leader-level, the computing service provider (CSP) and its agent constitute a composite leader. The agent purchases computing resource from CSP on credit and acts as a broker among leader-level and user-level reselling these computing resources to users. In the user-level, every user experiences social externality, which means users are interdependent. The leader-level subgame makes credit payment easier by making loaning and trading become a joint credit payment. The user-level subgame makes the market more active and closer to reality by introducing social externality. Besides, smart contracts can prevent malicious behaviors such as delay payment. We also conduct equilibrium analysis and prove the existence and uniqueness of the Nash equilibrium in our Stackelberg game-based model. Finally, we conduct numerical experiments to evaluate the cost of smart contracts and the performance of each entity with the proposed pricing mechanism.

We propose a game attack-defense graph (GADG) approach that integrates the attack-defense graph and the game theory to model and analyze cyberattacks and defenses in the local metering system (LMS). Different from previous studies concentrating on static analyses of cybervulnerabilities, the GADG method considers correlations among these vulnerabilities. Besides, to avoid the uncertainty brought by unilateral analysis, we introduce the game theory for the interaction analysis between the attacker and the defender. The mixed-strategy Nash equilibrium that they finally reach can serve as the input for the inference of system states. We also propose two eliminating algorithms to reduce the complexity of solving mixed-strategy Nash equilibrium on large-scale LMS. In the case study, our GADG model has been conducted on a real LMS, and the results prove its efficiency. This research aims to assist the power company in optimizing the allocation of limited defensive resources, especially specific in attacking steps.

This paper studies a setting in which multiple suppliers compete for a buyer's procurement business. The buyer faces uncertain demand and there is a requirement to reserve capacity in advance of knowing the demand. Each supplier has costs that are two dimensional, with some costs incurred before demand is realized in order to reserve capacity and some costs incurred after demand is realized at the time of delivery. A distinctive feature of our model is that the marginal costs may not be constants, and this naturally leads us to a supply function competition framework in which each supplier offers a schedule of prices and quantities. We treat this problem as an example of a general class of capacity games and show that, when the optimal supply chain profit is submodular, in equilibrium the buyer makes a reservation choice that maximizes the overall supply chain profit, each supplier makes a profit equal to their marginal contribution to the supply chain, and the buyer takes the remaining profit. We further prove that this submodularity property holds under two commonly studied settings: (1) there are only two suppliers; and (2) in the case of more than two suppliers, the marginal two-dimension costs of each supplier are non-decreasing and constant, respectively., Comment: 35 pages

In this article, we investigate the distributed Nash equilibrium (NE) seeking problem for the multi-cluster game under switching communication topologies. Specifically, the communication topology switches between a group of jointly connected digraphs. First, a new distributed NE seeking algorithm for the multi-cluster games is designed by the consensus protocol and gradient play rule under the switching communication topologies. Furthermore, in order to make the algorithm still applicable when the agent only knows part of the decision information, the leader-following consensus protocol is used to generate the estimates for all agents action in the cluster under the assumption that the switching topology between clusters is directed and strongly connected. A more general NE seeking algorithm for the multi-cluster games is designed. For these two algorithms, the results of local convergence and non-local convergence are given, respectively. Two examples verify the validity of the theoretical results.

In this paper, we investigate the behavior of agents with bounded rationality, attacking a set of stochastic sensors measuring the state of a binary event. The coordination problem between the attackers is formulated as a multi-player non-zero-sum one-shot game. Each attacker aims to maximize the probability that a certain detector will produce an erroneous estimate of the true event, while they remain stealthy. To better predict the outcome of this game, we categorize the players based on the number of strategic thinking steps they will take. Each level-k attacker behaves based on subjective beliefs of the others' behaviors, which are quantified via a Poisson distribution over the lower levels. The expected best responses for the type of each attacker are derived. The limiting conditions as the cognitive levels increase, as well as when the attackers fully coordinate, are shown to converge to the Nash equilibrium.

Federated learning (FL) is a distributed machine learning framework that can effectively help multiple players to use data to train federated models while complying with their privacy, data security, and government regulations. Due to federated model training, an accurate model should be trained, and all federated players should actively participate. Therefore, it is crucial to design an incentive mechanism; however, there is a conflict between fairness and Pareto efficiency in the incentive mechanism. In this paper, we propose an incentive mechanism via the combination of the Shapley value and Pareto efficiency optimization, in which a third party is introduced to supervise the federated payoff allocation. If the payoff can reach Pareto optimality, the federated payoff is allocated by the Shapley value method; otherwise, the relevant federated players are punished. Numerical and simulation experiments show that the mechanism can achieve fair payoff allocation and Pareto optimality payoff allocation. The Nash equilibrium of this mechanism is formed when Pareto optimality payoff allocation is achieved.

Badminton tactics refer to the techniques and strategies employed by players to win a match. Analyzing these tactics can help players improve their performance and outsmart their opponents. To study the tactics of top players, we use a gaming tree to analyze matches between two of the most powerful badminton players in history: Lin and Lee. By employing the Nash Equilibrium, we can discover the most beneficial strategies for both players, which reflect their most powerful techniques. Additionally, with the help of this gaming tree, we can precisely predict how players will implement their tactics. Empirical experimental results demonstrate that our proposed method not only evaluates and identifies each player’s weaknesses and strengths but also has powerful capabilities to predict their tactics.

International audience; This paper considers different pricing models for a platform based rental system, such as Airbnb. A linear model is assumed for the demand response to price, and existence and uniqueness conditions for Nash equilibria are obtained. The Stackelberg equilibrium prices for the game are also obtained, and an iterative scheme is provided, which converges to the Nash equilibrium. Different cooperative pricing schemes are studied, and splitting of revenues based on the Shapley value is discussed. It is shown that a division of revenue based on the Shapley value gives a revenue to the platform proportional to its control of the market. The demand response function is modified to include user response to quality of service. It is shown that when the cost to provide quality of service is low, both renter and the platform will agree to maximize the quality of service. However, if this cost is high, they may not always be able to agree on what quality of service to provide.

We formulate a security game in a context of mixed armament acquisition, involving a finite set of Nations in strategic relationship, with utility functions which are nonlinear and non-differentiable on the boundary of their sets of definition. Since we want to study the long-term effect of the Nations' investment in nuclear weapons, we focus on the steady-state analysis of the game. This requires us to extend the classical results from Rosen on compact-convex games, to unbounded convex games, relying on the coercivity property of the Nations' utility functions. In addition, we prove the existence and uniqueness, under mild assumptions, of an interior point Nash Equilibrium solution of the game. Simulations are performed in case of a duopoly, highlighting the efficiency loss reduction and stabilizing effect of nuclear armaments by comparison with the conventional-only setting.

This paper conducts a rigorous game-theoretic analysis on multi-task deep learning, providing mathematical insights into the dynamics and interactions of tasks within these models. Multi-task deep learning has attracted significant attention in recent years due to its ability to leverage shared representations across multiple correlated tasks, leading to improved generalization and reduced training time. However, understanding and examining the interactions between tasks within a multi-task deep learning system poses a considerable challenge. In this paper, we present a game-theoretic investigation of multi-task deep learning, focusing on the existence and convergence of Nash equilibria. Game theory provides a suitable framework for modeling the interactions among various tasks in a multi-task deep learning system, as it captures the strategic behavior of learning agents sharing a common set of parameters. Our primary contributions include: casting the multi-task deep learning problem as a game where each task acts as a player aiming to minimize its task-specific loss function; introducing the notion of a Nash equilibrium for the multi-task deep learning game; demonstrating the existence of at least one Nash equilibrium under specific convexity and Lipschitz continuity assumptions for the loss functions; examining the convergence characteristics of the Nash equilibrium; and providing a comprehensive analysis of the implications and limitations of our theoretical findings. We also discuss potential extensions and directions for future research in the multi-task deep learning landscape.

The design of agents interacting with human beings is becoming a crucial problem in many real-life applications. Different methods have been proposed in the research areas of human–computer interaction (HCI) and multi-agent systems (MAS) to model teams of participants (agents and humans). It is then necessary to build models analyzing their decisions when interacting, while taking into account the specificities of these interactions. This paper, therefore, aimed to propose an explicit model of such interactions based on game theory, taking into account, not only environmental characteristics (e.g., criticality), but also human characteristics (e.g., workload and experience level) for the intervention (or not) of agents, to help the latter. Game theory is a well-known approach to studying such social interactions between different participants. Existing works on the construction of game matrices required different ad hoc descriptors, depending on the application studied. Moreover, they generally focused on the interactions between agents, without considering human beings in the analysis. We show that these descriptors can be classified into two categories, related to their effect on the interactions. The set of descriptors to use is thus based on an explicit combination of all interactions between agents and humans (a weighted sum of 2-player matrices). We propose a general model for the construction of game matrices based on any number of participants and descriptors. It is then possible to determine using Nash equilibria whether agents decide (or not) to intervene during the tasks concerned. The model is also evaluated through the determination of the gains obtained by the different participants. Finally, we illustrate and validate the proposed model using a typical scenario (involving two agents and two humans), while describing the corresponding equilibria.

We consider a queueing system which opens at a given point in time and serves a finite number of users according to the last-come first-served discipline with preemptive-resume (LCFS-PR). Each user must decide individually when to join the queue. We allow for general classes of user preferences and service time distributions and show existence and uniqueness of a symmetric Nash equilibrium. Furthermore, we show that no continuous asymmetric equilibrium exists, if the population consists of only two users, or if arrival strategies satisfy a mild regularity condition. For an illustrative example, we implement a numerical procedure for computing the symmetric equilibrium strategy based on our constructive existence proof for the symmetric equilibrium. We then compare its social efficiency to that obtained if users are instead served on a first-come first-served (FCFS) basis.

At the time of writing, the Riemann Hypothesis (RH) is one of the major unsolved problems in pure mathematics. In this note, a parameterized family of non-cooperative games is constructed with the property that, if RH holds true, then any game in this family admits a unique Nash equilibrium.

We present a detailed analysis of Nash equilibria in multi-objective normal-form games, which are normal-form games with vectorial payoffs. Our approach is based on modelling each player's utility using a utility function that maps a vector to a scalar utility. For mixed strategies, we can apply the utility function before calculating the expectation of the payoff vector as well as after, resulting in two distinct optimisation criteria. We show that when computing the utility from the expected payoff, a Nash equilibrium can be guaranteed when players have quasiconcave utility functions. In addition, we show that when players have quasiconvex utility functions, pure strategy Nash equilibria are equal under both optimisation criteria. We extend this to settings where some players optimise for one criterion, while others optimise for the second. We combine these results and formulate an algorithm that computes all pure strategy Nash equilibria given quasiconvex utility functions.

Logit dynamics is a form of randomized game dynamics where players have a bias towards strategic deviations that give a higher improvement in cost. It is used extensively in practice. In congestion (or potential) games, the dynamics converges to the so-called Gibbs distribution over the set of all strategy profiles, when interpreted as a Markov chain. In general, logit dynamics might converge slowly to the Gibbs distribution, but beyond that, not much is known about their algorithmic aspects, nor that of the Gibbs distribution. In this work, we are interested in the following two questions for congestion games: i) Is there an efficient algorithm for sampling from the Gibbs distribution? ii) If yes, do there also exist natural randomized dynamics that converges quickly to the Gibbs distribution? We first study these questions in extension parallel congestion games, a well-studied special case of symmetric network congestion games. As our main result, we show that there is a simple variation on the logit dynamics (in which we in addition are allowed to randomly interchange the strategies of two players) that converges quickly to the Gibbs distribution in such games. This answers both questions above affirmatively. We also address the first question for the class of so-called capacitated $k$-uniform congestion games. To prove our results, we rely on the recent breakthrough work of Anari, Liu, Oveis-Gharan and Vinzant (2019) concerning the approximate sampling of the base of a matroid according to strongly log-concave probability distribution., Accepted at the 22nd ACM Conference on Economics and Computation (EC 2021)

The increasing popularity of ride-hailing applications has given rise to a new channel in which ride-hailing platforms are bundled into aggregation platforms to earn additional orders by charging commissions and slotting fees. Such bundled channels, unlike traditional reseller electronic ones, may flutter prices, service levels, market demands, and then further affect their profits. These divergent attitudes raise an interesting and key question about whether and under what conditions bundled channels should be introduced to ride-hailing platforms. In this paper, we provide an analytical framework for ride-hailing and aggregation platforms in unbundled and bundled scenarios, respectively. We build a Stackelberg game model in which ride-hailing and aggregation platforms as leaders obtain prices by constructing Nash equilibria, while drivers as followers determine service levels given to two platforms. Drivers’ best responses in terms of service levels for two platforms, as well as platforms’ optimal pricing strategies and profits are achieved. To capture access conditions of the ride-hailing platform and the profit contention between two platforms, we further conduct sensitivity analysis on cost coefficients of service levels, price and cross-price substitutions, service level and cross-service level substitutions, revenue-sharing ratio, cost, as well as commission and slotting fee. Based on numerical examples and analysis of the results, some interesting managerial insights about bundling strategies are gained for ride-hailing platforms.

Efficient grant-free uplink transmission is critical in minimizing Age of Information (AoI) in multi-channel Internet of Things (IoT) networks. But less attention has been paid to this topic especially when dynamic channel access attacks (DCAAs) exist. To bridge this gap, this paper formulates the distributed channel access problem in AoI-oriented IoT networks, and then a reinforcement learning-based solution is put forward based on the theoretical results of the game theory. Firstly, a utility maximization problem is formulated for each sensor node based on its average AoI under DCAAs with probabilistic ACK feedback. Secondly, the problem is transformed into two ordinary potential game (OPG) models, which are both proved to have at least one Nash Equilibrium (NE); and a distributed learning algorithm is proposed to reach the NE. Finally, extensive simulations are conducted to evaluate the proposal’s performance. Simulation results verify the effectiveness of the proposed algorithm in various parameters settings.

We aim to address the Nash equilibrium (NE) seeking problem for multiple players over Markovian switching communication networks in this article, where a new type of distributed synchronous discrete-time algorithm is proposed and utilized. Specifically, each player in the present game model is assumed to employ a gradient-like projection algorithm to choose its action based upon the estimated ones for all the others. Under the mild condition that the union network of all communication network candidates is connected, we show that the players' actions could converge to an arbitrarily small neighborhood of the NE in the mean-square sense by adjusting the algorithm parameters. It is further found that the unique NE is mean-square stable when it is not restricted by any constraint set. In addition, we show that the proposed distributed discrete-time NE seeking algorithm can be utilized to deal with the energy trading problem in microgrids where each microgrid is modeled as a rational player using a purchase price as its action to buy energy from other microgrids with surplus supplies. The energy market allocates the excess energy according to the principle of proportional distribution. Some numerical simulations are finally presented to verify the validity of the present discrete-time NE seeking algorithm in solving the energy trading problem.

We study the production/inventory competition problem between two manufacturers each adopting the co-production system to process a raw material into two products in fixed proportions that are substitutable between the manufacturers. We first consider the one-period problem where the demands for the two manufacturers’ products are uncertain and independent. The unmet demand of one manufacturer's product can be met by the other manufacturer's leftover stock of the same product, if available, and is lost otherwise. The manufacturers compete for the substitute demands by choosing their own purchase/processing quantities. We show the existence of the unique Nash equilibrium processing quantity, and examine the impact of competition by comparing the total equilibrium quantity of the game with that of the centralized-decision case. We then study the multi-period production/inventory competition problem in which the manufacturers make decisions in each period according to the initial inventory levels of the products and the rivals’ decisions. We show the existence and uniqueness of the Nash equilibrium strategy and that the equilibrium strategy has the simple base-stock structure. We then consider the case where the manufacturers’ demands are correlated. In addition, studying the case where the manufacturers are capacitated, we show that the unique Nash equilibrium exists and has a modified base-stock structure. We further generalize the results to the infinite-period case and the case with more than two products. Finally, numerical studies are conducted to investigate the impacts of the model parameters on the equilibrium outcomes and get some managerial insights from the analytical findings.

In the multi-access edge computing (MEC) environment, app vendors’ data can be cached on edge servers to ensure low-latency data retrieval. Massive users can simultaneously access edge servers with high data rates through flexible allocations of transmit power. The ability to manage networking resources offers unique opportunities to app vendors but also raises unprecedented challenges. To ensure fast data retrieval for users in the MEC environment, edge data caching must take into account the allocations of data, users, and transmit power jointly. We make the first attempt to study the Data, User, and Power Allocation (DUPA $^3$ 3 ) problem, aiming to serve the most users and maximize their overall data rate. First, we formulate the DUPA $^3$ 3 problem and prove its $\mathcal {NP}$ NP -completeness. Then, we model the DUPA $^3$ 3 problem as a potential DUPA $^3$ 3 game admitting at least one Nash equilibrium and propose a two-phase game-theoretic decentralized algorithm named DUPA $^3$ 3 Game to achieve the Nash equilibrium as the solution to the DUPA $^3$ 3 problem. To evaluate DUPA $^3$ 3 Game, we analyze its theoretical performance and conduct extensive experiments to demonstrate its effectiveness and efficiency.