New algorithms for approximate Nash equilibria in bimatrix games

We consider the problem of computing additively approximate Nash equilibria in non-cooperative two-player games. We provide a new polynomial time algorithm that achieves an approximation guarantee of 0.36392. We first provide a simpler algorithm, that achieves a 0.38197-approximation, which is exactly the same factor as the algorithm of Daskalakis, Mehta and Papadimitriou. This algorithm is then tuned, improving the approximation error to 0.36392. Our method is relatively fast and simple, as it requires solving only one linear program and it is based on using the solution of an auxiliary zero-sum game as a starting point. Finally we also exhibit a simple reduction that allows us to compute approximate equilibria for multi-player games by using algorithms for two-player games.     

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.     

Decentralized tracking-type games for multi-agent systems with coupled ARX models: Asymptotic Nash equilibria

A class of decentralized tracking-type games is considered for large population multi-agent systems (MAS). The agents are described by stochastic discrete-time auto-regressive models with exogenous inputs (ARX models), and coupled together through their individual dynamics and performance indexes by terms of the unknown population state average (PSA). The performance index of each agent to minimize is a stochastic long term averaged group-tracking-type functional, in which there is a nonlinear term of the unknown PSA. The control law is decentralized and implemented via the Nash certainty equivalence principle. By probability limit theory, under mild conditions it is shown that: (a) the estimate of the PSA is strongly consistent; (b) the closed-loop system is stable almost surely, and the stability is independent of the number N of agents; (c) the decentralized control law is an asymptotic Nash equilibrium almost surely or in probability according to the property of the nonlinear coupling function in the performance indexes.     

Existence and uniqueness of open-loop Nash equilibria in linear-quadratic discrete time games

We present existence and uniqueness results for an equilibrium in an M-person Nash game with quadratic performance criteria and a linear difference equation as constraint, describing the system dynamics under an open-loop information pattern. The approach used is the construction of a value function which leads to existence assertions in terms of solvability of certain symmetric and nonsymmetric Riccati difference equations.     

Nash equilibria: Complexity,symmetries, and approximation

We survey recent joint work with Christos Papadimitriou and Paul Goldberg on the computational complexity of Nash equilibria. We show that finding a Nash equilibrium in normal form games is computationally intractable, but in an unusual way. It does belong to the class NP; but Nash’s theorem, showing that a Nash equilibrium always exists, makes the possibility that it is also NP-complete rather unlikely. We show instead that the problem is as hard computationally as finding Brouwer fixed points, in a precise technical sense, giving rise to a new complexity class called PPAD. The existence of the Nash equilibrium was established via Brouwer’s fixed-point theorem; hence, we provide a computational converse to Nash’s theorem.To alleviate the negative implications of this result for the predictive power of the Nash equilibrium, it seems natural to study the complexity of approximate equilibria: an efficient approximation scheme would imply that players could in principle come arbitrarily close to a Nash equilibrium given enough time. We review recent work on computing approximate equilibria and conclude by studying how symmetries may affect the structure and approximation of Nash equilibria. Nash showed that every symmetric game has a symmetric equilibrium. We complement this theorem with a rich set of structural results for a broader, and more interesting class of games with symmetries, called anonymous games.     

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.     

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.     

A note on proofs of existence of Nash equilibria in finite strategic games,of two players

Known general proofs of Nash’s Theorem (about the existence of Nash Equilibria (NEa) in finite strategic games) rely on the use of a fixed point theorem (e.g. Brouwer’s or Kakutani’s). While it seems that there is no general way of proving the existence of Nash equilibria without the use of a fixed point theorem, there do however exist some (not so common in the CS literature) proofs that seem to indicate alternative proof paths, for games of two players. This note discusses two such proofs.     

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.     

Nash equilibria for combined flow control and routing in networks:asymptotic behavior for a large number of users

We consider a noncooperative game framework for combined routing and flow control in a network of parallel links, where the number of users (players) is arbitrarily large. The utility function of each user is related to the power criterion, and is taken as the ratio of some positive power of the total throughput of that user to the average delay seen by the user. The utility function is nonconcave in the flow rates of the user, for which we introduce a scaling to make it well defined as the number of users, N, becomes arbitrarily large. In spite of the lack of concavity, we obtain explicit expressions for the flow rates of the users and their associated routing decisions, which are in O(1/N) Nash equilibrium. This O(1/N) equilibrium solution, which is symmetric across different users and could be multiple in some cases, exhibits a delay-equalizing feature among the links which carry positive flow. The paper also provides the complete optimal solution to the single-user case, and includes several numerical examples to illustrate different features of the solutions in the single- as well as N-user cases, as N becomes arbitrarily large     

Modeling, control, and stability analysis for time-delay TLP systems using the fuzzy Lyapunov method

In this study, we present a Takagi–Sugeno (T–S) fuzzy model for the modeling and stability analysis of oceanic structures. We design a nonlinear fuzzy controller based on a parallel distributed compensation (PDC) scheme and reformulate the controller design problem as a linear matrix inequalities (LMI) problem as derived from the fuzzy Lyapunov theory. The robustness design technique is adopted so as to overcome the modeling errors for nonlinear time-delay systems subject to external oceanic waves. The vibration of the oceanic structure, i.e., the mechanical motion caused by the force of the waves, is discussed analytically based on fuzzy logic theory and a mathematical framework. The end result is decay in the amplitude of the surge motion affecting the time-delay tension leg platform (TLP) system. The feedback gain of the fuzzy controller needed to stabilize the TLP system can be found using the Matlab LMI toolbox. This proposed method of fuzzy control is applicable to practical TLP systems. The simulation results show that not only can the proposed method stabilize the systems but that the controller design is also simplified. The effects of the amplitude damping of the surge motion on the structural response are obvious and work as expected due to the control force.     

Stability analysis and control synthesis for switched systems: a switched Lyapunov function approach

This paper addresses the problem of stability analysis and control synthesis of switched systems in the discrete-time domain. The approach followed in this paper looks at the existence of a switched quadratic Lyapunov function to check asymptotic stability of the switched system under consideration. Two different linear matrix inequality-based conditions allow to check the existence of such a Lyapunov function. The first one is classical while the second is new and uses a slack variable, which makes it useful for design problems. These two conditions are proved to be equivalent for stability analysis. Investigating the static output feedback control problem, we show that the second condition is, in this case, less conservative. The reduction of the conservatism is illustrated by a numerical evaluation.     

Exploring the potential of computer and video games for health and physical education: A literature review

This study aims at critically reviewing recently published scientific literature on the use of computer and video games in Health Education (HE) and Physical Education (PE) with a view: (a) to identifying the potential contribution of the incorporation of electronic games as educational tools into HE and PE programs, (b) to present a synthesis of the available empirical evidence on the educational effectiveness of electronic games in HE and PE, and (c) to define future research perspectives concerning the educational use of electronic games in HE and PE. After systematically searching online bibliographic databases, 34 relevant articles were located and included in the study. Following the categorization scheme proposed by [Dempsey, J., Rasmussen, K., & Lucassen, B. (1996). The instructional gaming literature: Implications and 99 sources. University of South Alabama, College of Education, Technical Report No. 96-1], those articles were grouped into the following four categories: (a) research, (b) development, (c) discussion and (d) theory. The overviewed articles suggest that electronic games present many potential benefits as educational tools for HE and PE, and that those games may improve young people’s knowledge, skills, attitudes and behaviours in relation to health and physical exercise. Furthermore, the newly emerged physically interactive electronic games can potentially enhance young people’s physical fitness, motor skills and motivation for physical exercise. The empirical evidence to support the educational effectiveness of electronic games in HE and PE is still rather limited, but the findings present a positive picture overall. The outcomes of the literature review are discussed in terms of their implications for future research, and can provide useful guidance to educators, practitioners and researchers in the areas of HE and PE, and to electronic game designers.     

Forests,frames, and games: Algorithms for matroid sums and applications

This paper presents improved algorithms for matroid-partitioning problems, such as finding a maximum cardinality set of edges of a graph that can be partitioned intok forests, and finding as many disjoint spanning trees as possible. The notion of a clump in a matroid sum is introduced, and efficient algorithms for clumps are presented. Applications of these algorithms are given to problems arising in the study of the structural rigidity of graphs, the Shannon switching game, and others.     

Forests, frames, and games: Algorithms for matroid sums and applications

This paper presents improved algorithms for matroid-partitioning problems, such as finding a maximum cardinality set of edges of a graph that can be partitioned intok forests, and finding as many disjoint spanning trees as possible. The notion of a clump in a matroid sum is introduced, and efficient algorithms for clumps are presented. Applications of these algorithms are given to problems arising in the study of the structural rigidity of graphs, the Shannon switching game, and others.This is a revised and expanded version of a paper appearing in theProceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988. This research was supported in part by National Science Foundation Grants MCS-8302648 and DCR-851191.     

Method of Lyapunov functions for analysis of absorption and explosion in Markov chains

The main goal of this paper is to derive some sufficient conditions for testing the absorption, explosion, and nonexplosion of time-inhomogeneous Markov chains with a countable state space. The method of Lyapunov functions is used for this purpose. Several theorems concerned with such sufficient conditions are proved for a general class of Markov chains. Then they are applied to some problems in time-inhomogeneous birth-death processes and branching processes.     

Systematic planning for digital preservation: evaluating potential strategies and building preservation plans

A number of approaches have been proposed for the problem of digital preservation, and the number of tools offering solutions is steadily increasing. However, the decision making procedures are still largely ad-hoc actions. Especially, the process of selecting the most suitable preservation action tool as one of the key issues in preservation planning has not been sufficiently standardised in practice. The Open Archival Information Systems (OAIS) model and corresponding criteria catalogues for trustworthy repositories specify requirements that such a process should fulfill, but do not provide concrete guidance. This article describes a systematic approach for evaluating potential alternatives for preservation actions and building thoroughly defined, accountable preservation plans for keeping digital content alive over time. In this approach, preservation planners empirically evaluate potential action components in a controlled environment and select the most suitable one with respect to the particular requirements of a given setting. The method follows a variation of utility analysis to support multi-criteria decision making procedures in digital preservation planning. The selection procedure leads to well-documented, well-argued and transparent decisions that can be reproduced and revisited at a later point of time. We describe the context and foundation of the approach, discuss the definition of a preservation plan and describe the components that we consider necessary to constitute a solid and complete preservation plan. We then describe a repeatable workflow for accountable decision making in preservation planning. We analyse and discuss experiences in applying this workflow in case studies. We further set the approach in relation to the OAIS model and show how it supports criteria for trustworthy repositories. Finally, we present a planning tool supporting the workflow and point out directions for future research.     

Adaptable pointer swizzling strategies in object bases: design,realization, and quantitative analysis

In this article, different techniques for pointer swizzling are classified and evaluated for optimizing the access to main-memory resident persistent objects. To speed up the access along inter-object references, the persistent pointers in the form of unique object identifiers (OIDs) are transformed (swizzled) into main-memory pointers (addresses). Pointer swizzling techniques can be divided into two classes: (1) those that allow replacement of swizzled objects from the buffer before the end of an application program, and (2) those that rule out the displacement of swizzled objects. The first class (i.e., techniques that take precautions for the replacement of swizzled objects) has not yet been thoroughly investigated. Four different pointer swizzling techniques allowing object replacement are investigated and compared with the performance of an object manager employing no pointer swizzling. The extensive qualitative and quantitative evaluation—only part of which could be presented in this article—demonstrate that there is noone superior pointer swizzling strategy forall application profiles. Therefore, an adaptable object base run-time system is devised that employs the full range of pointer swizzling strategies, depending on the application profile characteristics that are determined by, for example, monitoring in combination with sampling, user specifications, and/or program analysis.     

GEECAT and GEEGOR: computer programs for the analysis of correlated categorical response data

GEECAT and GEEGOR are two user-friendly SAS macros for the analysis of clustered, correlated categorical response data. Both programs implement methodology which extend the generalized estimating equation (GEE) approach of Liang and Zeger (Biometrika 73 (1986) 13-22). GEECAT and GEEGOR both use a first set of estimating equations to model the marginal response. With GEECAT, either correlated nominal or ordered categorical response data can be analyzed. The program GEEGOR employs a second set of estimating equations to model the association of ordered categorical responses within a cluster using the global odds ratio as a measure of association. The programs run on both mainframe computers and microcomputers. Examples are provided to illustrate the features of both programs.     

Lyapunov function-based control laws for revolute robot arms:tracking control, robustness, and adaptive control

A new class of joint level control laws for all-revolute robot arms is introduced. The analysis is similar to an energy-like Lyapunov function approach, except that the closed-loop potential function is shaped in accordance with the underlying joint space topology. This approach gives way to a much simpler analysis and leads to a new class of control designs which guarantee both global asymptotic stability and local exponential stability. When Coulomb and viscous friction and parameter uncertainty are present as model perturbations, a sliding mode-like modification of the control law results in a robustness-enhancing outer loop. Adaptive control is formulated within the same framework. A linear-in-the-parameters formulation is adopted and globally asymptotically stable adaptive control laws are derived by simply replacing unknown model parameters by their estimates