Pure subgame-perfect equilibria in free transition games

We consider a class of stochastic games, where each state is identified with a player. At any moment during play, one of the players is called active. The active player can terminate the game, or he can announce any player, who then becomes the active player. There is a non-negative payoff for each player upon termination of the game, which depends only on the player who decided to terminate. We give a combinatorial proof of the existence of subgame-perfect equilibria in pure strategies for the games in our class.     

Uncomputability and undecidability in economic theory

Economic theory, game theory and mathematical statistics have all increasingly become algorithmic sciences. Computable Economics, Algorithmic Game Theory[Noam Nisan, Tim Roiughgarden, Éva Tardos, Vijay V. Vazirani (Eds.), Algorithmic Game Theory, Cambridge University Press, Cambridge, 2007] and Algorithmic Statistics[Péter Gács, John T. Tromp, Paul M.B. Vitányi, Algorithmic statistics, IEEE Transactions on Information Theory 47 (6) (2001) 2443-2463] are frontier research subjects. All of them, each in its own way, are underpinned by (classical) recursion theory - and its applied branches, say computational complexity theory or algorithmic information theory - and, occasionally, proof theory. These research paradigms have posed new mathematical and metamathematical questions and, inadvertently, undermined the traditional mathematical foundations of economic theory. A concise, but partial, pathway into these new frontiers is the subject matter of this paper. Interpreting the core of mathematical economic theory to be defined by General Equilibrium Theory and Game Theory, a general - but concise - analysis of the computable and decidable content of the implications of these two areas are discussed. Issues at the frontiers of macroeconomics, now dominated by Recursive Macroeconomic Theory (The qualification ‘recursive’ here has nothing to do with ‘recursion theory’. Instead, this is a reference to the mathematical formalizations of the rational economic agent’s intertemporal optimization problems, in terms of Markov Decision Processes, (Kalman) Filtering and Dynamic Programming, where a kind of ‘recursion’ is invoked in the solution methods. The metaphor of the rational economic agent as a ‘signal processor’ underpins the recursive macroeconomic paradigm.), are also tackled, albeit ultra briefly. The point of view adopted is that of classical recursion theory and varieties of constructive mathematics.     

Nash equilibria in all-optical networks

We consider the problem of routing a number of communication requests in WDM (wavelength division multiplexing) all-optical networks from the standpoint of game theory. If we view each routing request (pair of source-target nodes) as a player, then a strategy consists of a path from the source to the target and a frequency (color). To reflect the restriction that two requests must not use the same frequency on the same edge, conflicting strategies are assigned a prohibitively high cost.Under this formulation, we consider several natural cost functions, each one reflecting a different aspect of restriction in the available bandwidth. For each cost function we examine the problem of the existence of pure Nash equilibria, the complexity of recognizing and computing them and finally, the problem in which we are given a Nash equilibrium and we are asked to find a better one in the sense that the total bandwidth used is less. As it turns out some of these problems are tractable and others are NP-hard.     

Game-perfect graphs

A graph coloring game introduced by Bodlaender (Int J Found Comput Sci 2:133–147, 1991) as coloring construction game is the following. Two players, Alice and Bob, alternately color vertices of a given graph G with a color from a given color set C, so that adjacent vertices receive distinct colors. Alice has the first move. The game ends if no move is possible any more. Alice wins if every vertex of G is colored at the end, otherwise Bob wins. We consider two variants of Bodlaender’s graph coloring game: one (A) in which Alice has the right to have the first move and to miss a turn, the other (B) in which Bob has these rights. These games define the A-game chromatic number resp. the B-game chromatic number of a graph. For such a variant g, a graph G is g-perfect if, for every induced subgraph H of G, the clique number of H equals the g-game chromatic number of H. We determine those graphs for which the game chromatic numbers are 2 and prove that the triangle-free B-perfect graphs are exactly the forests of stars, and the triangle-free A-perfect graphs are exactly the graphs each component of which is a complete bipartite graph or a complete bipartite graph minus one edge or a singleton. From these results we may easily derive the set of triangle-free game-perfect graphs with respect to Bodlaender’s original game. We also determine the B-perfect graphs with clique number 3. As a general result we prove that complements of bipartite graphs are A-perfect.      

Transmit power and bits/channel use adaption in competitive cognitive radio networks

In this paper, we propose an optimization framework to determine the distribution of power and bits/channel use to secondary users in a competitive cognitive radio networks. The objectives of the optimization framework are to minimize total transmission power, maximize total bits/channel use and also to maintain quality of service. An upper bound on probability of bit error and lower bound on bits/channel use requirement of secondary users are considered as quality of service. The optimization problem is also constrained by total power budget across channels for a user. Simulating the framework in a centralized manner shows that more transmit power is required to allocate in a channel with higher noise power. However, allocation of bits/channel use is directly proportional to signal to interference plus noise power ratio. The proposed framework is more capable of supporting high bits/channel use requirement than existing resource allocation framework. We also develop the game theoretic user based distributed approach of the proposed framework. We see that user based distributed solution also follows centralized solution.     

RAT selection for IoT devices in HetNets: Reinforcement learning with hybrid SMDP algorithm

Due to the increasing deployment of heterogeneous networks (HetNets), the selection of which radio access technologies (RATs) for Internet of Things (IoT) devices such as user equipments (UEs) has recently received extensive attention in mobility management research. Most of existing RAT selection methods only optimize the selection strategies from the UE side or network side, which results in heavy network congestion, poor user experience and system utility degradation. In this paper the UE side and the network side are considered comprehensively, based on the game theory (GT) model we propose a reinforcement learning with assisted network information algorithm to overcome the crucial points. The assisted information is formulated as a semi-Markov decision process (SMDP) provided for UEs to make accurate decisions, and we adopt the iteration approach to reach the optimal policy. Moreover, we investigate the impacts of different parameters on the system utility and handover performance. Numerical results validate that our proposed algorithm can mitigate unnecessary handovers and improve system throughputs.     

Evolutionary game on a stochastic growth network

In some real complex systems the structures are difficult to map or changing over time. To explore the evolution of strategies on these complex systems, it is not realistic enough to specify their structures or topological properties in advance. In this paper, we address the evolutionary game on a stochastic growth network adopting the prisoner’s dilemma game. We introduce a growing rate q$q$ to control the ratio of network growth to strategy evolution. A large q$q$ denotes that the network grows faster than strategy evolution. Simulation results show that a fast growing rate is helpful to promote the average payoffs of both cooperators and defectors. Moreover, this parameter also significantly influences the cooperation frequency on the resulting networks. The coexisting mechanisms in this paper may provide a beneficial insight for understanding the emergence of complex topological structures and game behaviors in numerous real systems.     

Ellipsoid projection method in matrix games

A problem of calculating a solution of a zero-sum matrix game is considered in the paper The problem of search of a solution is reduced to a constrained convex minimization problem for which an ellipsoid projection algorithm is used. The algorithm generates an ?-optimal solution of the game in a polynomial time     

Can international environmental cooperation be bought: Comment

Fuentes-Albero and Rubio (2010) analytically examine the effects of the countries’ heterogeneity on the international environmental cooperation. They consider two types of countries having different abatement costs in one case and different environmental damages in another case. Furthermore it is analyzed whether a self-financed transfer system can diminish these heterogeneity effects. The paper shows for both scenarios of asymmetry and no transfers that the maximum level of cooperation consists of three countries of the same type. For the case of heterogeneity in environmental damages, Fuentes-Albero and Rubio conclude that an agreement between one type 1 and one type 2 country is also self-enforcing given that the differences in the damages are not very large. In this comment, the derivation of the last mentioned result is shown to be incorrect by proving that this coalition is not self-enforcing.