A note on competitive diffusion through social networks

We introduce a game-theoretic model of diffusion of technologies, advertisements, or influence through a social network. The novelty in our model is that the players are interested parties outside the network. We study the relation between the diameter of the network and the existence of pure Nash equilibria in the game. In particular, we show that if the diameter is at most two then an equilibrium exists and can be found in polynomial time, whereas if the diameter is greater than two then an equilibrium is not guaranteed to exist.     

Matrix games with missing,interval, and ambiguous lottery payoffs of pure strategy profiles and compound strategy profiles

In a matrix game, the interactions among players are based on the assumption that each player has accurate information about the payoffs of their interactions and the other players are rationally self‐interested. As a result, the players should definitely take Nash equilibrium strategies. However, in real‐life, when choosing their optimal strategies, sometimes the players have to face missing, imprecise (i.e., interval), ambiguous lottery payoffs of pure strategy profiles and even compound strategy profile, which means that it is hard to determine a Nash equilibrium. To address this issue, in this paper we introduce a new solution concept, called ambiguous Nash equilibrium, which extends the concept of Nash equilibrium to the one that can handle these types of ambiguous payoff. Moreover, we will reveal some properties of matrix games of this kind. In particular, we show that a Nash equilibrium is a special case of ambiguous Nash equilibrium if the players have accurate information of each player's payoff sets. Finally, we give an example to illustrate how our approach deals with real‐life game theory problems.     

A Pure Nash Equilibrium-Based Game Theoretical Method for Data Replication across Multiple Servers

This paper proposes a non-cooperative game based technique to replicate data objects across a distributed system of multiple servers in order to reduce user perceived Web access delays. In the proposed technique computational agents represent servers and compete with each other to optimize the performance of their servers. The optimality of a non-cooperative game is typically described by Nash equilibrium, which is based on spontaneous and non-deterministic strategies. However, Nash equilibrium may or may not guarantee system-wide performance. Furthermore, there can be multiple Nash equilibria, making it difficult to decide which one is the best. In contrast, the proposed technique uses the notion of pure Nash equilibrium, which if achieved, guarantees stable optimal performance. In the proposed technique, agents use deterministic strategies that work in conjunction with their self-interested nature but ensure system-wide performance enhancement. In general, the existence of a pure Nash equilibrium is hard to achieve, but we prove the existence of such equilibrium in the proposed technique. The proposed technique is also experimentally compared against some well-known conventional replica allocation methods, such as branch and bound, greedy, and genetic algorithms.     

Discovering theorems in game theory: Two-person games with unique pure Nash equilibrium payoffs

In this paper we provide a logical framework for two-person finite games in strategic form, and use it to design a computer program for discovering some classes of games that have unique pure Nash equilibrium payoffs. The classes of games that we consider are those that can be expressed by a conjunction of two binary clauses, and our program re-discovered Kats and Thisse?s class of weakly unilaterally competitive two-person games, and came up with several other classes of games that have unique pure Nash equilibrium payoffs. It also came up with new classes of strict games that have unique pure Nash equilibria, where a game is strict if for both player different profiles have different payoffs.     

How hard is it to find extreme Nash equilibria in network congestion games?

We study the complexity of finding extreme pure Nash equilibria in symmetric (unweighted) network congestion games. In our context best and worst equilibria are those with minimum respectively maximum makespan. On series–parallel graphs a worst Nash equilibrium can be found by a Greedy approach while finding a best equilibrium is NP-hard. For a fixed number of users we give a pseudo-polynomial algorithm to find the best equilibrium in series–parallel networks. For general network topologies also finding a worst equilibrium is NP-hard.     

Repeated Budgeted Second Price Ad Auction

Our main goal is to abstract existing repeated sponsored search ad auction mechanisms which incorporate budgets, and study their equilibrium and dynamics. Our abstraction has multiple agents bidding repeatedly for multiple identical items (such as impressions in an ad auction). The agents are budget limited and have a value per item. We abstract this repeated interaction as a one-shot game, which we call budget auction, where agents submit a bid and a budget, and then items are sold by a sequential second price auction. Once an agent exhausts its budget it does not participate in the proceeding auctions. Our main result shows that if agents bid conservatively (never bid above their value) then there always exists a pure Nash equilibrium. We also study simple dynamics of repeated budget auctions, showing their convergence to a Nash equilibrium for two agents and for multiple agents with identical budgets.     

On Robustness of Forward-looking in Sponsored Search Auction

We analyze the robustness of pure Nash Equilibria of sponsored search auctions, based on the forward-looking response function. To consider the robustness of such refined solution concept, we first study the convergence property of several adjustment schemes. Especially, we prove that under the randomized scheme, the auction always converges to a unique fixed point with probability one, whose revenue is equal to the celebrated VCG mechanism. Additionally, we study the robustness of such forward-looking strategic heuristic against aggressive selfish strategic heuristic called vindictive bidding. We investigate three types of such bidding strategies and substantiate that the pure Nash equilibrium still exists under two types even if there is an arbitrary portion of vindictive bidders.     

Pareto Effectiveness of Equilibria in Active Systems with the Distributed Control

Active systems with the distributed control (one active element and a few control centers) are considered. Questions for the existence of the Nash equilibrium of the game of centers in pure strategies are studied. It is shown that at any distribution of the incomes from the work of an active system among a few centers and the existence of at least one Pareto-ineffective Nash equilibrium, any Pareto-effective outcome can be implemented as a Nash equilibrium. It is proved that in the system consisting of two centers there always exists a Pareto-effective Nash equilibrium in pure strategies.     

带Poisson跳的线性二次随机微分博弈及其在鲁棒控制中的应用

研究了一类带Poisson跳扩散过程的线性二次随机微分博弈,包括非零和博弈的Nash均衡策略与零和博弈的鞍点均衡策略问题．利用微分博弈的最大值原理,得到Nash均衡策略的存在条件等价于两个交叉耦合的矩阵Riccati方程存在解,鞍点均衡策略的存在条件等价于一个矩阵Riccati方程存在解的结论,并给出了均衡策略的显式表达及最优性能泛函值．最后,将所得结果应用于现代鲁棒控制中的随机H₂/H_∞控制与随机H_∞控制问题,得到了鲁棒控制策略的存在条件及显式表达,并验证所得结果在金融市场投资组合优化问题中的应用．     

Multi-agent discrete-time graphical games and reinforcement learning solutions

This paper introduces a new class of multi-agent discrete-time dynamic games, known in the literature as dynamic graphical games. For that reason a local performance index is defined for each agent that depends only on the local information available to each agent. Nash equilibrium policies and best-response policies are given in terms of the solutions to the discrete-time coupled Hamilton–Jacobi equations. Since in these games the interactions between the agents are prescribed by a communication graph structure we have to introduce a new notion of Nash equilibrium. It is proved that this notion holds if all agents are in Nash equilibrium and the graph is strongly connected. A novel reinforcement learning value iteration algorithm is given to solve the dynamic graphical games in an online manner along with its proof of convergence. The policies of the agents form a Nash equilibrium when all the agents in the neighborhood update their policies, and a best response outcome when the agents in the neighborhood are kept constant. The paper brings together discrete Hamiltonian mechanics, distributed multi-agent control, optimal control theory, and game theory to formulate and solve these multi-agent dynamic graphical games. A simulation example shows the effectiveness of the proposed approach in a leader-synchronization case along with optimality guarantees.     

Simulation Analysis for Network Formulation

In their model of network formation, Berninghaus et al. (Exp Econ 9:237–251, 2006; J Evol Econ 17:317–347, 2007) showed that a periphery-sponsored star network is a strict Nash equilibrium. To examine the validity of their result, they also performed a laboratory experiment with human subjects, and they found that a periphery-sponsored star network can be formed, but when broken down, a different star network forms. In this paper, after considering some factors explaining this phenomenon, we develop a simulation system involving these factors with artificial autonomous agents. Through simulations using this system, we try to explain the behavior of human subjects in the network formation experiment, i.e., the fact that a strict Nash equilibrium periphery-sponsored star network is broken down and a different periphery-sponsored star network is formed.     

When Can Limited Randomness Be Used in Repeated Games?

The central result of classical game theory states that every finite normal form game has a Nash equilibrium, provided that players are allowed to use randomized (mixed) strategies. However, in practice, humans are known to be bad at generating random-like sequences, and true random bits may be unavailable. Even if the players have access to enough random bits for a single instance of the game their randomness might be insufficient if the game is played many times. In this work, we ask whether randomness is necessary for equilibria to exist in finitely repeated games. We show that for a large class of games containing arbitrary two-player zero-sum games, approximate Nash equilibria of the n-stage repeated version of the game exist if and only if both players have Ω(n) random bits. In contrast, we show that there exists a class of games for which no equilibrium exists in pure strategies, yet the n-stage repeated version of the game has an exact Nash equilibrium in which each player uses only a constant number of random bits. When the players are assumed to be computationally bounded, if cryptographic pseudorandom generators (or, equivalently, one-way functions) exist, then the players can base their strategies on “random-like” sequences derived from only a small number of truly random bits. We show that, in contrast, in repeated two-player zero-sum games, if pseudorandom generators do not exist, then Ω(n) random bits remain necessary for equilibria to exist.     

Ad Hoc网络中基于重复博弈的攻击预测模型

大多数入侵检测系统预测攻击行为能力较弱,不能实时主动地响应攻击。针对该问题,提出一种基于重复博弈的攻击预测模型。通过建立入侵者和入侵检测系统之间的阶段博弈模型,给出阶段博弈的纳什均衡,并求出重复博弈情况下的子博弈精炼纳什均衡。使用QRE模型预测攻击者和防御者在博弈阶段1~t中选择各种策略的概率,利用Gambit分析得出预测结果。基于GloMoSim的仿真结果表明,相比纳什均衡模型,QRE均衡模型的预测效果更好。     

Quantum prisoners’ dilemma under enhanced interrogation

In the quantum version of prisoners’ dilemma, each prisoner is equipped with a single qubit that the interrogator can entangle. We enlarge the available Hilbert space by introducing a third qubit that the interrogator can entangle with the other two. We discuss an enhanced interrogation technique based on tripartite entanglement and analyze Nash equilibria. We show that for tripartite entanglement approaching a W-state, we calculate the Nash equilibria numerically and show that they coincide with the Pareto-optimal choice where both prisoners cooperate. Upon continuous variation between a W-state and a pure bipartite entangled state, the game is shown to have a surprisingly rich structure. The role of bipartite and tripartite entanglement is explored to explain that structure. As an application, we consider an evolutionary game based on our quantum game with a network of agents on a square lattice with periodic boundary conditions and show that the strategy corresponding to Nash equilibrium completely dominates without placing any restrictions on the initial set of strategies.     

Distributed projection subgradient algorithm for two-network zero-sum game with random sleep scheme

In this paper, a zero-sum game Nash equilibrium computation problem with a common constraint set is investigated under two time-varying multi-agent subnetworks, where the two subnetworks have opposite payoff function. A novel distributed projection subgradient algorithm with random sleep scheme is developed to reduce the calculation amount of agents in the process of computing Nash equilibrium. In our algorithm, each agent is determined by an independent identically distributed Bernoulli decision to compute the subgradient and perform the projection operation or to keep the previous consensus estimate, it effectively reduces the amount of computation and calculation time. Moreover, the traditional assumption of stepsize adopted in the existing methods is removed, and the stepsizes in our algorithm are randomized diminishing. Besides, we prove that all agents converge to Nash equilibrium with probability 1 by our algorithm. Finally, a simulation example verifies the validity of our algorithm.     

An incentive-based distributed mechanism for scheduling divisible loads in tree networks

The underlying assumption of Divisible Load Scheduling (DLS) theory is that the processors composing the network are obedient, i.e., they do not “cheat” the scheduling algorithm. This assumption is unrealistic if the processors are owned by autonomous, self-interested organizations that have no a priori motivation for cooperation and they will manipulate the algorithm if it is beneficial to do so. In this paper, we address this issue by designing a distributed mechanism for scheduling divisible loads in tree networks, called DLS-T, which provides incentives to processors for reporting their true processing capacity and executing their assigned load at full processing capacity. We prove that the DLS-T mechanism computes the optimal allocation in an ex post Nash equilibrium. Finally, we simulate and study the mechanism under various network structures and processor parameters.     

Dynamics and stability of potential hyper-networked evolutionary games

This paper considers the modeling and convergence of hyper-networked evolutionary games (HNEGs). In an HNEG the network graph is a hypergraph, which allows the fundamental network game to be a multi-player one. Using semi-tensor product of matrices and the fundamental evolutionary equation, the dynamics of an HNEG is obtained and we extend the results about the networked evolutionary games to show whether an HNEG is potential and how to calculate the potential. Then we propose a new strategy updating rule, called the cascading myopic best response adjustment rule (MBRAR), and prove that under the cascading MBRAR the strategies of an HNEG will converge to a pure Nash equilibrium. An example is presented and discussed in detail to demonstrate the theoretical and numerical results.     

RFID-enabled item-level product information revelation

We consider a homogeneous product market and the incentive for oligopolists to share item-level product information with their customers. Enabled by Radio Frequency Identification technology, each firm has the option to record and reveal item-level information of a proportion of its products. We consider a two-stage game where each firm first decides its production plan and then determines its level of information revelation. With a constant clearance discount rate, we derive pure strategy equilibria that are subgame perfect and demonstrate that complete information sharing is the unique Nash equilibrium for the game when the common demand is volatile and that no information revelation is the unique Nash equilibrium when demand is not volatile. Furthermore, we show that the Nash equilibrium is the same with a decreasing clearance discount rate and that neither complete information revelation nor zero information revelation is consistent with an equilibrium with an increasing discount rate. Results are similar in a duopoly non-homogeneous product market scenario.     

Evolutionary asymmetric games for modeling systems of partially cooperative agents

Based on the tenet of Darwinism, we propose a general mechanism that guides agents (which can be partially cooperative) in selecting appropriate strategies in situations of complex interactions, in which agents do not have complete information about other agents. In the mechanism, each participating agent generates many instances of itself to help it find an appropriate strategy. The generated instances adopt alternative strategies from the agent's strategy set. While all instances generated by different agents meet randomly to complete a task, every instance adapts its strategy according to the difference between the average utilities of its current strategy and all its strategies. We give a complete analysis of the mechanism for the case with two agents when each agent has two strategies, and show that by the tenet of Darwinism, agents can find their appropriate strategies through evolution and adaptation: 1) if dominant strategies exist, then the proposed mechanism is guaranteed to find them; 2) if there are two or more strict Nash equilibrium strategies, the proposed mechanism is guaranteed to find them by using different initial strategy distributions; and 3) if there is no dominant strategy and no strict Nash equilibrium, then agents will oscillate periodically. Nevertheless, the mechanism allows agent designers to derive the appropriate strategies from the oscillation by integration. For cases with two agents when each agent has two or more strategies, it is shown that agents can reach a steady state where social welfare is optimum.     

广义Nash平衡点和切换控制在对策论中的应用

通过把平衡点和决策者的动机耦合的方法,提出了广义纳什平衡点这一新概念.决策者的动机通常有两类：一是最大化自己的利益,另一则是最大化对手的利益.如果每一个决策者的动机都是第一类,一个理性的群体就会形成,整个系统最终会达到第一类平衡点（也就是经典的纳什平衡点）.如果每一个决策者的动机都是第二类,一个有智慧的群体就会形成,整个系统最终会达到第二类平衡点.同时,切换控制被用来帮助决策者确定他们的动机.