On the complexity of constrained Nash equilibria in graphical games

A widely accepted rational behavior for non-cooperative players is based on the notion of Nash equilibrium. Although the existence of a Nash equilibrium is guaranteed in the mixed framework (i.e., when players select their actions in a randomized manner) in many real-world applications the existence of “any” equilibrium is not enough. Rather, it is often desirable to single out equilibria satisfying some additional requirements (in order, for instance, to guarantee a minimum payoff to certain players), which we call constrained Nash equilibria.In this paper, a formal framework for specifying these kinds of requirement is introduced and investigated in the context of graphical games, where a player p may directly be interested in some of the other players only, called the neighbors of p. This setting is very useful for modeling large population games, where typically each player does not directly depend on all the players, and representing her utility function extensively is either inconvenient or infeasible.Based on this framework, the complexity of deciding the existence and of computing constrained equilibria is then investigated, in the light of evidencing how the intrinsic difficulty of these tasks is affected by the requirements prescribed at the equilibrium and by the structure of players’ interactions. The analysis is carried out for the setting of mixed strategies as well as for the setting of pure strategies, i.e., when players are forced to deterministically choose the action to perform. In particular, for this latter case, restrictions on players’ interactions and on constraints are identified, that make the computation of Nash equilibria an easy problem, for which polynomial and highly-parallelizable algorithms are presented.     

The structure and complexity of Nash equilibria for a selfish routing game

In this work, we study the combinatorial structure and the computational complexity of Nash equilibria for a certain game that models selfish routing over a network consisting of m$m$ parallel links. We assume a collection of n$n$ users, each employing a mixed strategy, which is a probability distribution over links, to control the routing of her own traffic. In a Nash equilibrium, each user selfishly routes her traffic on those links that minimize her expected latency cost, given the network congestion caused by the other users. The social cost of a Nash equilibrium is the expectation, over all random choices of the users, of the maximum, over all links, latency through a link.     

The complexity of economic equilibria for house allocation markets

We prove NP-completeness of deciding the existence of an economic equilibrium in so-called house allocation markets. House allocation markets are markets with indivisible goods in which every agent holds exactly one copy of some good.     

On the complexity of market equilibria with maximum social welfare

We consider the computational complexity of the market equilibrium problem by exploring the structural properties of the Leontief exchange economy. We prove that, for economies guaranteed to have a market equilibrium, finding one with maximum social welfare or maximum individual welfare is NP-hard. In addition, we prove that counting the number of equilibrium prices is #P-hard.     

A novel approximate method of computing extended Nash equilibria

In this paper, we propose a new method of computing an approximate Nash equilibrium with additional features. Existing algorithms often fail to produce an exact solution for games involving more than 3 players. Similarly, existing algorithms do not permit additional constraints on the problem. The principle idea of this paper involves proposing a methodology for computing approximate solutions through evolutionary computation. To do so, we first provide formal definitions of these problems and their approximate versions. Following which, we present the details of our solution. One of the most important advantages of the proposed solution is flexibility, which provides solutions to problems related to Nash equilibrium extensions. The proposed idea is tested on several types of games that vary with difficulty and size. All test sets are generated based on the well-known Gamut program. Additional comparisons with classical algorithms are also performed. Results indicate that Differential Evolution is capable of obtaining satisfactory solutions to large random and covariant games. The results also demonstrate that there is a high probability that even large games, in which a set of strategies with a non-zero probability of being chosen are very small, have a solution. The computation time depends mainly on the problem size, and the original Nash equilibrium problem is unaffected by additional modifications.     

Extending the notion of rationality of selfish agents: Second Order Nash equilibria

Motivated by the increasing interest of the Computer Science community in the study and understanding of non-cooperative systems, we present a novel model for formalizing the rational behavior of agents with a more farsighted view of the consequences of their actions. This approach yields a framework creating new equilibria, which we call Second Order equilibria, starting from a ground set of traditional ones. By applying our approach to pure Nash equilibria, we define the set of Second Order pure Nash equilibria and present their applications to the Prisoner’s Dilemma game, to an instance of Braess’s Paradox in the Wardrop model and to the KP model with identical machines.     

Comparative dynamics in an overlapping-generations model: the effects of quasi-rational discrete choice on finding and maintaining Nash equilibrium

Many models of Nash Equilibrium are complex enough that it becomes difficult to ascertain if and under what conditions the economic players can find and maintain this equilibrium. Using an analytical overlapping- generations model of goods, labor, and banking markets and quasi-rational discrete choice decision making, we find through agent-based simulations that Nash Equilibrium in goods market prices is stable when firms are sufficiently sensitive to changes in profits. In addition to verifying the analytical Nash outcome, the simulations verify that their economic agents, decision rules, and other protocols correspond to and maintain consistency with the analytical theory and identify important bounds of the analytical model.      

纯策略纳什均衡的博弈强化学习

将博弈理论与多智能体强化学习结合形成博弈强化学习逐渐受到关注,但是也存在算法的计算复杂度高和无法保证纯策略纳什均衡的问题。Meta equilibrium Q-learning算法通过反应函数将原始博弈转换为元博弈,而元博弈推导出的元均衡是纯策略纳什均衡。该算法在保证纯策略纳什均衡的前提下能够使得每个智能体的回报不低于某特定阈值。同时,基于分形的均衡程度评估模型能够通过计算任意状态的分形维数来判断其稳态,并评估任意状态与均衡状态之间的距离,该模型可以检验元均衡的科学性与合理性,上述算法和模型的相关结论在福利博弈和夺控战中都得到具体验证。     

基于排斥技术的QPSO算法在纳什均衡中的应用

基于量子行为的粒子群优化算法(QPSO)是一种随机的全局优化搜索新方法。文章系统地介绍了PSO算法、QPSO算法和“repulsion”技术。在对QPSO算法和基于“repulsion”技术的PSO算法分析的基础上,提出了基于“repulsion”技术的QPSO算法。将该算法用于求解混合纳什均衡。实验表明,新算法在解的收敛性和稳定性等方面优于QPSO算法。     

On the complexity of finding a local maximum of functions on discrete planar subsets

We study how many values of an unknown integer-valued function f one needs to know in order to find a local maximum of f. We consider functions defined on finite subsets of discrete plane. We prove upper bounds for functions defined on rectangles and present lower bounds for functions defined on arbitrary domains in terms of the size of the domain and the size of its border.     

On the structure and complexity of worst-case equilibria

In the resource allocation game introduced by Koutsoupias and Papadimitriou, n$n$ jobs of different weights are assigned to m$m$ identical machines by selfish agents. For this game, it has been conjectured by several authors that the fully mixed Nash equilibrium (FMNE) is the worst possible w.r.t. the expected maximum load over all machines. Assuming the validity of this conjecture, computing a worst-case Nash equilibrium for a given instance was trivial, and approximating the Price of Anarchy for this instance would be possible by approximating the expected social cost of the FMNE by applying a known FPRAS.     

Empirical approximation of Nash equilibria in finite Markov games with discounted payoffs

This paper deals with finite nonzero-sum Markov games under a discounted optimality criterion and infinite horizon. The state process evolves according to a stochastic difference equation and depends on players' actions as well as a random disturbance whose distribution is unknown to the players. The actions, the states, and the values of the disturbance are observed by the players, then they use the empirical distribution of the disturbances to estimate the true distribution and make choices based on the available information. In this context, we propose an almost surely convergent procedure—possibly after passing to a subsequence—to approximate Nash equilibria of the Markov game with the true distribution of the random disturbance.     

On the intrinsic complexity of point finding in real singular hypersurfaces

In previous work we designed an efficient procedure that finds an algebraic sample point for each connected component of a smooth real complete intersection variety. This procedure exploits geometric properties of generic polar varieties and its complexity is intrinsic with respect to the problem. In the present paper we introduce a natural construction that allows to tackle the case of a non-smooth real hypersurface by means of a reduction to a smooth complete intersection.     

On the query complexity of finding a local maximum point

We calculate the minimal number of queries sufficient to find a local maximum point of a function on a discrete interval, for a model with M parallel queries, M?1. Matching upper and lower bounds are obtained. The bounds are formulated in terms of certain Fibonacci type sequences of numbers.     

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

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

The communication complexity of the Hamming distance problem

We investigate the randomized and quantum communication complexity of the Hamming Distance problem, which is to determine if the Hamming distance between two n-bit strings is no less than a threshold d. We prove a quantum lower bound of Ω(d) qubits in the general interactive model with shared prior entanglement. We also construct a classical protocol of O(dlogd) bits in the restricted Simultaneous Message Passing model with public random coins, improving previous protocols of O(d²) bits [A.C.-C. Yao, On the power of quantum fingerprinting, in: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 77-81], and O(dlogn) bits [D. Gavinsky, J. Kempe, R. de Wolf, Quantum communication cannot simulate a public coin, quant-ph/0411051, 2004].     

Analyzing the dynamics of stigmergetic interactions through pheromone games

The concept of stigmergy provides a simple framework for interaction and coordination in multi-agent systems. However, determining the global system behavior that will arise from local stigmergetic interactions is a complex problem. In this paper we propose to use Game Theory to analyze stigmergetic interactions. We show that a system where agents coordinate by sharing local pheromone information can be approximated by a limiting pheromone game in which different pheromone vectors represent player strategies. This game view allows us to use established methods and solution concepts from game theory to describe the properties of stigmergy based systems. Our goal is to provide a new framework to aid in the understanding and design of pheromone interactions. We demonstrate how we can use this system to determine the long term system behavior of a simple pheromone model, by analyzing the convergence properties of the pheromone update rule in the approximating game. We also apply this model to cases where multiple colonies of agents concurrently optimize different objectives. In this case a limiting colony game can be linked to colony level interactions to characterize the global system behavior.