Pareto-optimal Nash equilibrium: Sufficient conditions and existence in mixed strategies

This paper considers the Nash equilibrium strategy profiles that are Pareto optimal with respect to the rest Nash equilibrium strategy profiles. The sufficient conditions for the existence of such pure strategy profiles are established. These conditions employ the Germeier convolutions of the payoff functions. For the non-cooperative games with compact strategy sets and continuous payoff functions, the existence of the Pareto optimal Nash equilibria in mixed strategies is proved.     

Pure Nash equilibria in player-specific and weighted congestion games

Unlike standard congestion games, weighted congestion games and congestion games with player-specific delay functions do not necessarily possess pure Nash equilibria. It is known, however, that there exist pure equilibria for both of these variants in the case of singleton congestion games, i.e., if the players’ strategy spaces contain only sets of cardinality one. In this paper, we investigate how far such a property on the players’ strategy spaces guaranteeing the existence of pure equilibria can be extended. We show that both weighted and player-specific congestion games admit pure equilibria in the case of matroid congestion games, i.e., if the strategy space of each player consists of the bases of a matroid on the set of resources. We also show that the matroid property is the maximal property that guarantees pure equilibria without taking into account how the strategy spaces of different players are interweaved.     

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.     

Random Bimatrix Games Are Asymptotically Easy to Solve (A Simple Proof)

We focus on the problem of computing approximate Nash equilibria and well-supported approximate Nash equilibria in random bimatrix games, where each player’s payoffs are bounded and independent random variables, not necessarily identically distributed, but with almost common expectations. We show that the completely mixed uniform strategy profile, i.e., the combination of mixed strategies (one per player) where each player plays with equal probability each one of her available pure strategies, is with high probability a $\sqrt{\frac{\ln n}{n}}$ -Nash equilibrium and a $\sqrt{\frac{3\ln n}{n}}$ -well supported Nash equilibrium, where n is the number of pure strategies available to each player. This asserts that the completely mixed, uniform strategy profile is an almost Nash equilibrium for random bimatrix games, since it is, with high probability, an ?-well-supported Nash equilibrium where ? tends to zero as n tends to infinity.     

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.     

Analytical solution for a class of linear quadratic open-loop Nash game with multiple players

In this paper, the Nash equilibria for differential games with multiple players is studied. A method for solving the Riccati-type matrix differential equations for open-loop Nash strategy in linear quadratic game with multiple players is presented and analytical solution is given for a type of differential games in which the system matrix can be diagonalizable. As the special cases, the Nash equilibria for some type of differential games with particular structure is studied also, and some results in previous literatures are extended. Finally, a numerical example is given to illustrate the effectiveness of the solution procedure.     

Analytical solution for a class of linear quadratic open-loop Nash game with multiple players

In this paper, the Nash equilibria for differential games with multiple players is studied. A method for solving the Riccati-type matrix differential equations for open-loop Nash strategy in linear quadratic game with multiple players is presented and analytical solution is given for a type of differential games in which the system matrix can be diagonalizable. As the special cases, the Nash equilibria for some type of differential games with particular structure is studied also, and some results in previous literatures are extended. Finally, a numerical example is given to illustrate the effectiveness of the solution procedure.     

Stackelberg Strategies for Atomic Congestion Games

We investigate the effectiveness of Stackelberg strategies for atomic congestion games with unsplittable demands. In our setting, only a fraction of the players are selfish, while the rest are willing to follow a predetermined strategy. A Stackelberg strategy assigns the coordinated players to appropriately selected strategies trying to minimize the performance degradation due to the selfish players. We consider two orthogonal cases, namely congestion games with affine latency functions and arbitrary strategies, and congestion games on parallel links with arbitrary non-decreasing latency functions. We restrict our attention to pure Nash equilibria and derive strong upper and lower bounds on the pure Price of Anarchy (PoA) under different Stackelberg strategies.     

Existence of equilibria in quantum Bertrand–Edgeworth duopoly game

Both classical and quantum version of two models of price competition in duopoly market, the one is realistic and the other is idealized, are investigated. The pure strategy Nash equilibria of the realistic model exists under stricter condition than that of the idealized one in the classical form game. This is the problem known as Edgeworth paradox in economics. In the quantum form game, however, the former converges to the latter as the measure of entanglement goes to infinity.     

A comment on pure-strategy Nash equilibria in competitive diffusion games

In [N. Alon, M. Feldman, A.D. Procaccia, M. Tennenholtz, A note on competitive diffusion through social networks, Inform. Process. Lett. 110 (2010) 221–225], the authors introduced a game-theoretic model of diffusion process through a network. They showed a relation between the diameter of a given network and existence of pure Nash equilibria in the game. Theorem 1 of their paper says that a pure Nash equilibrium exists if the diameter is at most two. However, we have an example which does not admit a pure Nash equilibrium even if the diameter is two. Hence we correct the statement of Theorem 1 of their paper.     

On the Structure of Weakly Acyclic Games

The class of weakly acyclic games, which includes potential games and dominance-solvable games, captures many practical application domains. In a weakly acyclic game, from any starting state, there is a sequence of better-response moves that leads to a pure Nash equilibrium; informally, these are games in which natural distributed dynamics, such as better-response dynamics, cannot enter inescapable oscillations. We establish a novel link between such games and the existence of pure Nash equilibria in subgames. Specifically, we show that the existence of a unique pure Nash equilibrium in every subgame implies the weak acyclicity of a game. In contrast, the possible existence of multiple pure Nash equilibria in every subgame is insufficient for weak acyclicity in general; here, we also systematically identify the special cases (in terms of the number of players and strategies) for which this is sufficient to guarantee weak acyclicity.     

基于博弈思想的副本创建策略研究

在云计算等复杂网络环境下,提高海量数据存储的可靠性和访问效率,需引入副本存储及管理技术。基于此,提出基于博弈思想的副本创建策略,应用博弈原理建立复杂网络环境下的副本创建基本模型,证明纯策略纳什均衡解的存在性及求解方法,并通过仿真分析方法验证了该策略的有效性。     

Uniqueness and efficiency of Nash equilibrium in a family of randomly generated repeated games

This paper describes the results of an analysis of the Nash equilibrium in randomly generated repeated games. We study two families of games: symmetric bimatrix games G(A, B) with B = A^⊤ and nonsymmetric bimatrix games (the first includes the classical games of prisoner dilemma, battle of the sexes, and chickens). We use pure strategies, implemented by automata of size two, and different strategy domination criteria. We observe that, in this environment, the uniqueness and efficiency of equilibria outcomes is the typical result.     

Equilibria,fixed points,and complexity classes

Many models from a variety of areas involve the computation of an equilibrium or fixed point of some kind. Examples include Nash equilibria in games; market equilibria; computing optimal strategies and the values of competitive games (stochastic and other games); stable configurations of neural networks; analysing basic stochastic models for evolution like branching processes and for language like stochastic context-free grammars; and models that incorporate the basic primitives of probability and recursion like recursive Markov chains. It is not known whether these problems can be solved in polynomial time. There are certain common computational principles underlying different types of equilibria, which are captured by the complexity classes PLS, PPAD, and FIXP. Representative complete problems for these classes are, respectively, pure Nash equilibria in games where they are guaranteed to exist, (mixed) Nash equilibria in two-player normal form games, and (mixed) Nash equilibria in normal form games with three (or more) players. This paper reviews the underlying computational principles and the corresponding classes.     

Bounded Budget Connection (BBC) games or how to make friends and influence people,on a budget

Motivated by applications in social and peer-to-peer networks, we introduce the Bounded Budget Connection (BBC) game and study its pure Nash equilibria. We have a collection of n   players, each with a budget for purchasing links. Each link has a cost and a length. Each node has a preference weight for each node, and its objective is to purchase outgoing links within its budget to minimize its sum of preference-weighted distances to the nodes. We show that determining if a BBC game has pure Nash equilibria is NP-hard. We study (n,k)$(n,k)$-uniform BBC games, where all link costs, lengths, and preferences are equal and every budget equals k  . We show that pure Nash equilibria exist for all (n,k)$(n,k)$-uniform BBC games and all equilibria are essentially fair. We construct a family of equilibria spanning the spectrum from minimum to maximum social cost. We also analyze best-response walks and alternative node objectives.     

Establishing Nash equilibria of strategic games: a multistart Fuzzy Adaptive Simulated Annealing approach

This paper's proposal is to show some significant results obtained by the application of the optimization algorithm known as Fuzzy Adaptive Simulated Annealing (Fuzzy ASA) to the task of finding all Nash equilibria of normal form games. To that end, a special version of Fuzzy ASA, that utilizes space-filling curves to find good seeds, is applied to several well-known strategic games, showing its effectiveness in obtaining all Nash equilibria in all cases. The results are compared to previous work that also used computational intelligence techniques in order to solve the same problem but could not find all equilibria in all tests. Game theory is a very important subject, modeling interactions between generic agents, and Nash equilibrium represents a powerful concept portraying situations in which joint strategies are optimal in the sense that no player can benefit from changing her/his strategy while the other players do not change their strategies as well. So, new techniques are always welcome, mainly those that can find the whole set of solutions for a given strategic game.     

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.     

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.     

Generalized Graph k-Coloring Games

Theory of Computing Systems - We investigate pure Nash equilibria in generalized graphk-coloring games where we are given an edge-weighted undirected graph together with a set of k colors. Nodes...     

On Equilibria in Quantitative Games with Reachability/Safety Objectives

In this paper, we study turn-based multiplayer quantitative non zero-sum games played on finite graphs with reachability objectives. In this framework each player aims at reaching his own goal as soon as possible. We focus on existence results for two solution concepts: Nash equilibrium and secure equilibrium. We prove the existence of finite-memory Nash (resp. secure) equilibria in n-player (resp. 2-player) games. For the case of Nash equilibria, we extend our result in two directions. First, we show that finite-memory Nash equilibria still exist when the model is enriched by allowing n-tuples of positive costs on edges (one cost by player). Secondly, we prove the existence of Nash equilibria in quantitative games with both reachability and safety objectives.