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.     

Comments on "A computational evolutionary approach to evolving game strategies and cooperation"

Azuaje offers an approach to the co-evolution of competing virtual creatures and a model for the evolution of game strategies and their emerging behaviors (F. Azuaje, see ibid., vol. 33, p.498-502, 2003). This model can be greatly simplified and optimal solutions can be obtained more quickly and easily by using an analytical approach. We emphasize the importance of performing a model analysis before choosing an evolutionary or analytical approach to a problem. Furthermore, Azuaje's model is derived from the Prisoner's Dilemma, a classical model in game theory; some results have already been discussed in the literature. We discuss his model from the perspective of game theorists.     

Equilibria, stability and reachability of Leslie systems withnonnegative inputs

Leslie systems, a particular class of positive systems used in population dynamics and control, are defined and analyzed. A simple property relating sign and stability of their equilibria, and some geometric characteristics of their reachability set (in cases of bounded and unbounded inputs) are proved. All the properties do not hold, in general, in other classes of positive systems. It is shown that Leslie systems have strictly positive equilibria if and only if they are asymptotically stable. Their reachability set in the case of unbounded inputs is the positive cone generated by the reachability vectors, while in the case of bounded inputs, it is a polyhedron whose vertices can be easily computed. All of these properties follow from the nonpositiveness of the coefficients of the characteristic polynomial of the system     

The game chromatic number and the game colouring number of cactuses

We consider the colouring game and the marking game. A graph G is a cactus if any two cycles of G have at most one common vertex. We prove that χg(C)=colg(C)=5 for family of cactuses C.     

On the Complexity of Pareto-Optimal Nash and Strong Equilibria

We consider the computational complexity of coalitional solution concepts in scenarios related to load balancing such as anonymous and congestion games. In congestion games, Pareto-optimal Nash and strong equilibria, which are resilient to coalitional deviations, have recently been shown to yield significantly smaller inefficiency. Unfortunately, we show that several problems regarding existence, recognition, and computation of these concepts are hard, even in seemingly special classes of games. In anonymous games with constant number of strategies, we can efficiently recognize a state as Pareto-optimal Nash or strong equilibrium, but deciding existence for a game remains hard. In the case of player-specific singleton congestion games, we show that recognition and computation of both concepts can be done efficiently. In addition, in these games there are always short sequences of coalitional improvement moves to Pareto-optimal Nash and strong equilibria that can be computed efficiently.     

Noise and the magic square game

A pseudo-telepathy game is a game for two or more players for which there is no classical winning strategy, but there is a winning strategy based on sharing quantum entanglement by the players. Since it is generally very hard to perfectly implement a quantum winning strategy for a pseudo-telepathy game, quantum players are almost certain to make errors even though they use a winning strategy. After introducing a model for pseudo-telepathy games, we investigate the impact of erroneously performed unitary transformations and also of noisy measurement devices on the quantum winning strategy for the magic square game. The question of how strong both types of noise can be so that quantum players would still be better than classical ones is also dealt with.     

A game approach to production,storage, and marketing problems

Dynamic control of production, storage, and marketing processes is regarded as a cooperative game or as a two-criteria optimal control problem. The problem is solved under the assumption that producer controls production and consumer, buying process. Necessary conditions for the producer and buyer to have a positive profit are formulated.Translated from Avtomatika i Telemekhanika, No. 2, 2005, pp. 115–123.Original Russian Text Copyright © 2005 by Paraev.     

Matching free trees, maximal cliques, and monotone game dynamics

Motivated by our recent work on rooted tree matching, in this paper we provide a solution to the problem of matching two free (i.e., unrooted) trees by constructing an association graph whose maximal cliques are in one-to-one correspondence with maximal common subtrees. We then solve the problem using simple payoff-monotonic dynamics from evolutionary game theory. We illustrate the power of the approach by matching articulated and deformed shapes described by shape-axis trees. Experiments on hundreds of larger, uniformly random trees are also presented. The results are impressive: despite the inherent inability of these simple dynamics to escape from local optima, they always returned a globally optimal solution.     

The game chromatic number and the game colouring number of classes of oriented cactuses

We prove that the game chromatic and the game colouring number of the class of orientations of cactuses with girth of 2 or 3 is 4. We improve this bound for the class of orientations of certain forest-like cactuses to the value of 3. These results generalise theorems on the game colouring number of undirected forests (Faigle et al., 1993 [3]) resp. orientations of forests (Andres, 2009 [1]). For certain undirected cactuses with girth 4 we also obtain the tight bound 4, thus improving a result of Sidorowicz (2007) [8].     

A Big Picture on Recent Vulnerabilities: Active AX,Web server compromises and insecure documents

You may not know it, but some of your employees are installing vulnerable software — and you are silently accepting it, you may even encourage them to do so…     

Semistability, Finite-Time Stability, Differential Inclusions, and Discontinuous Dynamical Systems Having a Continuum of Equilibria

This paper focuses on semistability and finite-time semistability for discontinuous dynamical systems having a continuum of equilibria. Semistability is the property whereby the solutions of a dynamical system converge to Lyapunov stable equilibrium points determined by the system initial conditions. In this paper, we extend the theory of semistability to discontinuous autonomous dynamical systems. In particular, Lyapunov-based tests for semistability and finite-time semistability for autonomous differential inclusions are established.     

Just a game after all: Violent video game exposure and time spent playing effects on hostile feelings,depression, and visuospatial cognition

Research in the domain of video game violence continues to be contentious and debated. Scholars have examined both positive and negative effects of violent games, although results thus far have been inconclusive and systematic internal validity problems have been identified with past research. The current study adds to this growing literature by examining the effects of video game violence exposure and time spent playing on depression, hostility, and visuospatial cognition. This study improves upon previous research by matching game conditions carefully on confounding variables identified as problems by other scholars. In a laboratory setting, 100 participants were randomly assigned into one of six conditions based on two independent variables (time spent playing and type of video game). Results indicated that neither randomized video game play nor time spent playing a video game had any effect on depression, hostility, or, visuospatial cognition. Effect size estimates were below levels for practical significance. These results suggest that both positive and negative influences of violence in video games may be limited in scope.     

Quantum game simulator, using the circuit model of quantum computation

We present a general two-player quantum game simulator that can simulate any two-player quantum game described by a 2×2 payoff matrix (two strategy games).The user can determine the payoff matrices for both players, their strategies and the amount of entanglement between their initial strategies. The outputs of the simulator are the expected payoffs of each player as a function of the other player's strategy parameters and the amount of entanglement. The simulator also produces contour plots that divide the strategy spaces of the game in regions in which players can get larger payoffs if they choose to use a quantum strategy against any classical one. We also apply the simulator to two well-known quantum games, the Battle of Sexes and the Chicken game.

Program summary

Program title: Quantum Game Simulator (QGS)Catalogue identifier: AEED_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEED_v1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 3416No. of bytes in distributed program, including test data, etc.: 583 553Distribution format: tar.gzProgramming language: Matlab R2008a (C)Computer: Any computer that can sufficiently run Matlab R2008aOperating system: Any system that can sufficiently run Matlab R2008aClassification: 4.15Nature of problem: Simulation of two player quantum games described by a payoff matrix.Solution method: The program calculates the matrices that comprise the Eisert setup for quantum games based on the quantum circuit model. There are 5 parameters that can be altered. We define 3 of them as constant. We play the quantum game for all possible values for the other 2 parameters and store the results in a matrix.Unusual features: The software provides an easy way of simulating any two-player quantum games.Running time: Approximately 0.4 sec (Region Feature) and 0.3 sec (Payoff Feature) on a Intel Core 2 Duo GHz with 2 GB of memory under Windows XP.     

Nash Equilibria and the Price of Anarchy for Flows over Time

We study Nash equilibria in the context of flows over time. Many results on static routing games have been obtained over the last ten years. In flows over time (also called dynamic flows), flow travels through a network over time and, as a consequence, flow values on edges are time-dependent. This more realistic setting has not been tackled from the viewpoint of algorithmic game theory yet; but there is a rich literature on game theoretic aspects of flows over time in the traffic community.     

Payoff-monotonic game dynamics and the maximum clique problem

Evolutionary game-theoretic models and, in particular, the so-called replicator equations have recently proven to be remarkably effective at approximately solving the maximum clique and related problems. The approach is centered around a classic result from graph theory that formulates the maximum clique problem as a standard (continuous) quadratic program and exploits the dynamical properties of these models, which, under a certain symmetry assumption, possess a Lyapunov function. In this letter, we generalize previous work along these lines in several respects. We introduce a wide family of game-dynamic equations known as payoff-monotonic dynamics, of which replicator dynamics are a special instance, and show that they enjoy precisely the same dynamical properties as standard replicator equations. These properties make any member of this family a potential heuristic for solving standard quadratic programs and, in particular, the maximum clique problem. Extensive simulations, performed on random as well as DIMACS benchmark graphs, show that this class contains dynamics that are considerably faster than and at least as accurate as replicator equations. One problem associated with these models, however, relates to their inability to escape from poor local solutions. To overcome this drawback, we focus on a particular subclass of payoff-monotonic dynamics used to model the evolution of behavior via imitation processes and study the stability of their equilibria when a regularization parameter is allowed to take on negative values. A detailed analysis of these properties suggests a whole class of annealed imitation heuristics for the maximum clique problem, which are based on the idea of varying the parameter during the imitation optimization process in a principled way, so as to avoid unwanted inefficient solutions. Experiments show that the proposed annealing procedure does help to avoid poor local optima by initially driving the dynamics toward promising regions in state space. Furthermore, the models outperform state-of-the-art neural network algorithms for maximum clique, such as mean field annealing, and compare well with powerful continuous-based heuristics.     

An electricity market game between consumers, retailers and network operators

We consider a simple game-theoretical model in which an electricity retailer and a network owner offer incentives to consumers to shift load from a peak period to an off-peak period. Using a simple example, we compare the market outcomes from collusion with those from the equilibrium of a non-cooperative game and examine the behaviour in this game when it is repeated in a situation in which agents have imperfect information.     

Fiducial intervals for the waiting time in batch and time-sharing systems

In this paper error-estimates for fiducial intervals for the waiting time are analyzed, the intensity and the mean CPU-time being submitted to variations; this is done for a batch-system withn CPU's. Moreover we consider fiducial intervals for the conditional exspectationW(x)=E(waiting time‖CPU-time=x) in the case of the Round-Robin algorithm. Especially we focus on the dependence of the fiducial intervals forW(x) upon the distribution of the CPU-time (Erlang- versus exponential distribution). The results are derived as equations or inequalities including the possibility of numerical computation.     

Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width

In a previous paper (J. Comput. System Sci. 64 (2002) 519), the authors introduced the notion of hypertree decomposition and the corresponding concept of hypertree width and showed that the conjunctive queries whose hypergraphs have bounded hypertree width can be evaluated in polynomial time. Bounded hypertree width generalizes the notions of acyclicity and bounded treewidth and corresponds to larger classes of tractable queries. In the present paper, we provide natural characterizations of hypergraphs and queries having bounded hypertree width in terms of game-theory and logic. First we define the Robber and Marshals game, and prove that a hypergraph H has hypertree width at most k if and only if k marshals have a winning strategy on H, allowing them to trap a robber who moves along the hyperedges. This game is akin the well-known Robber and Cops game (which characterizes bounded treewidth), except that marshals are more powerful than cops: They can control entire hyperedges instead of just vertices. Kolaitis and Vardi (J. Comput. System Sci. 61 (2000) 302) recently gave an elegant characterization of the conjunctive queries having treewidth <k in terms of the k-variable fragment of a certain logic L (=existential-conjunctive fragment of positive FO). We use the Robber and Marshals game to derive a surprisingly simple and equally elegant characterization of the class HW[k] of queries of hypertree width at most k in terms of guarded logic. In particular, we show that HW[k]=GF_k(L), where GF_k(L) denotes the k-guarded fragment of L. In this fragment, conjunctions of k atoms rather than just single atoms are allowed to act as guards. Note that, for the particular case k=1, our results provide new characterizations of the class of acyclic queries. We extend the notion of bounded hypertree width to nonrecursive stratified Datalog and show that the k-guarded fragment GF_k(FO) of first-order logic has the same expressive power as nonrecursive stratified Datalog of hypertree width at most k.     

Fuzzy AHP for determining the key features and cognitive differences of mobile game development among designer and game player

Previous studies have assessed the elements of a game design from game players’ viewpoints. Scant research has been conducted from the perspectives of both game players and game developers. This study explored the cognitive difference among game players and game developers in the importance of online game designs by employing the fuzzy analytic hierarchy process (FAHP) to analyze the importance of puzzle game designs. The online game design hierarchical framework comprising 3 systems, 9 components, and 29 factors was established. The research findings are summarized as follows: 1) System quality is the most crucial design component. 2) Game development should primarily focus on technology followed by aesthetics. 3) A gap exists in the perception of game players and game developers on the design component “service quality.” Finally, researchers can adopt the multiple criteria decision-making model used in this current study to rank the importance of design contents for cultural and creative industries.     

Enhancing the control of force in putting by video game training.

Even if golf video games provide no proprioceptive afferences on actual putting movement, they may give sufficient substitutive visual cues to enhance force control in this skill. It was hypothesized that this usefulness requires, however, two conditions: the video game must provide reliable demonstrations of actual putts, and the user must want to use the game to make progress in actual putting. Accordingly, a video game was selected on the basis of its fidelity to the real-world game. It allowed two different methods of adjusting the virtual player's putting force in order to hole a putt: an analogue method that consisted of focusing on the virtual player's movement and a symbolic method that consisted of focusing on the movement of a gauge on a scale representing the virtual player's putting force. The participants had to use one of these methods with either the intention of making progress in actual putting or in a second condition to simply enjoy the game. Results showed a positive transfer of video playing to actual putting skill for the learning group and also, to a lesser degree, for the enjoyment group; but only when they used the symbolic method. Results are discussed in the context of how vision may convey force cues in sports video games.