Algorithms for Finding Repeated Game Equilibria

This paper describes computational techniques for finding all equilibria in infinitely repeated games with discounting and perfect monitoring. It illustrates these techniques with a three player Cournot game. This is the first infinitely repeated three player game ever solved. The paper also presents the solution for the set of equilibria in a two country tariff war. In both games the set of equilibria is large even when the players are not patient.     

Consensus in Noncooperative Dynamic Games: A Multiretailer Inventory Application

We focus on Nash equilibria and Pareto optimal Nash equilibria for a finite horizon noncooperative dynamic game with a special structure of the stage cost. We study the existence of these solutions by proving that the game is a potential game. For the single-stage version of the game, we characterize the aforementioned solutions and derive a consensus protocol that makes the players converge to the unique Pareto optimal Nash equilibrium. Such an equilibrium guarantees the interests of the players and is also social optimal in the set of Nash equilibria. For the multistage version of the game, we present an algorithm that converges to Nash equilibria, unfortunately, not necessarily Pareto optimal. The algorithm returns a sequence of joint decisions, each one obtained from the previous one by an unilateral improvement on the part of a single player. We also specialize the game to a multiretailer inventory system.     

Equilibria problems on games: Complexity versus succinctness

We study the computational complexity of problems involving equilibria in strategic games and in perfect information extensive games when the number of players is large. We consider, among others, the problems of deciding the existence of a pure Nash equilibrium in strategic games or deciding the existence of a pure Nash or a subgame perfect Nash equilibrium with a given payoff in finite perfect information extensive games. We address the fundamental question of how can we represent a game with a large number of players? We propose three ways of representing a game with different degrees of succinctness for the components of the game. For perfect information extensive games we show that when the number of moves of each player is large and the input game is represented succinctly these problems are PSPACE-complete. In contraposition, when the game is described explicitly by means of its associated tree all these problems are decidable in polynomial time. For strategic games we show that the complexity of deciding the existence of a pure Nash equilibrium depends on the succinctness of the game representation and then on the size of the action sets. In particular we show that it is NP-complete, when the number of players is large and the number of actions for each player is constant, and that the problem is -complete when the number of players is a constant and the size of the action sets is exponential in the size of the game representation. Again when the game is described explicitly the problem is decidable in polynomial time.     

Graphical Congestion Games

We consider congestion games with linear latency functions in which each player is aware only of a subset of all the other players. This is modeled by means of a social knowledge graph G in which nodes represent players and there is an edge from i to j if i knows j. Under the assumption that the payoff of each player is affected only by the strategies of the adjacent ones, we first give a complete characterization of the games possessing pure Nash equilibria. Namely, if the social graph G is undirected, the game is an exact potential game and thus isomorphic to a classical congestion game. As a consequence, it always converges and possesses Nash equilibria. On the other hand, if G is directed an equilibrium is not guaranteed to exist, but the game is always convergent and an equilibrium can be found in polynomial time if G is acyclic, even if finding the best equilibrium remains an intractable problem.     

Existence of a feedback equilibrium for two-stage Stackelberg games

In this paper we consider a two-stage feedback game in which two players solve a Stackelberg problem at each stage and each player knows the state of the game at every level of play. In this kind of game, the leader does not have the ability to announce his strategy at all levels of play prior to the start of the game. Without assuming that at each stage the Stackelberg problem has a unique solution, we define a concept of “feedback Stackelberg solution” and give sufficient conditions to get existence of such a solution     

Strong coalitional equilibrium in a transportation game

This paper introduces an extension of the vehicle routing problem by involving several decision makers in competition. Each customer is characterized by demand and distance to the warehouse. The problem is described in form of a cooperative transportation game (CTG). We consider customers as players in the game. Their strategies are the routes for a vehicle they should rent in a coalition to deliver goods subject to their demand with minimal transportation costs, under the assumption that transportation costs are allocated between the players according to the Nash arbitration scheme. For each profile in coalitional strategies, we define a coalitional structure of players and the costs of each player. A strong equilibrium is found for the cooperative transportation game. In addition, we develop a procedure to calculate the strong equilibrium. This procedure is illustrated by a numerical example.     

Game-theoretic Evolutionary Algorithm Based on Behavioral Expectation and its Performance Analysis

Game theory has been widely recognized as an important tool in many fields, which provides general mathematical techniques for analyzing situations in which two or more individuals make decisions that will influence one another’s welfare. This paper presents a game-theoretic evolutionary algorithm based on behavioral expectation, which is a type of optimization approach based on game theory. A formulation to estimate the payoffs expectation is given, which is a mechanism of trying to master the player’s information so as to facilitate the player becoming the rational decision maker. GameEA has one population (players set), and generates new offspring only by the imitation operator and the belief learning operator. The imitation operator is used to learn strategies and actions from other players to improve its competitiveness and applies it into the future game, namely that one player updates its chromosome by strategically copying some segments of gene sequences from the competitor. Belief learning refers to models in which a player adjusts its own strategies, behavior or chromosome by analyzing current history information with respect to an improvement of solution quality. The experimental results on various classes of problems using real-valued representation show that GameEA outperforms not only the standard genetic algorithm (GA) but also other GAs having additional mechanisms of accuracy enhancement. Finally, we compare the convergence of GameEA with different numbers of players to determine whether this parameter has a significant effect on convergence. The statistical results show that at the 0.05 significance level, the number of players has a crucial impact on GameEA's performance. The results suggest that 50 or 100 players will provide good results with unimodal functions, while 200 players will provide good results for multimodal functions.     

Competing for consumer's attention

We consider an infinite-horizon differential game played by two direct marketers. Each player controls the number of emails sent to potential customers at each moment in time. There is a cost associated to the messages sent, as well as a potential reward. The latter is assumed to depend on the state variable defined as the level of the representative consumer's attention. Two features are included in the model, namely, marginal decreasing returns and bounded rationality. By the latter, we mean that the representative consumer has a limited capacity for processing the information received. The evolution of this capacity depends on its level, as well as on the emails sent by both players. This provides environmental flavour where, usually, one player's pollution emissions (here emails) also affect the payoff of the other player by damaging the common environment (here, the stock of consumer attention).We characterize competitive equilibria for different scenarios based on each player's type, i.e., whether the player is a spammer or not. We define a spammer as a myopic player, i.e., a player who cares only about short-term payoff and ignores the impact of her action on the state dynamics. In all scenarios, the game turns out to be of the linear-quadratic variety. Feedback Nash equilibria for the different scenarios are characterized and the equilibrium strategies and outcomes are compared.Finally, we analyze the game in normal form, where each player has the option of choosing between being a spammer or not, and we characterize Nash equilibria.     

Multistage network games with perfect information

We consider multistage network games with perfect information. At each time instant, a current network structure connecting the players is specified. It is assumed that each edge has some utility value (player’s benefit from being linked to another player), and players can change the network structure at each stage. We propose a method for finding optimal behavior for players in games of this type.     

Constrained Games: The Impact of the Attitude to Adversary's Constraints

We consider properties of constrained games, where the strategy set available to a player depends on the choice of strategies made by other players. We show that the utilities of each player associated with that player's own performance and constraints are not sufficient to model a constrained game and to define equilibria; for the latter, one also needs to model how a player values the fact that other players meet their constraints. We study three different approaches to other players' constraints, and show that they exhibit completely different equilibrium behaviors. Further, we study a general class of stochastic games with partial information, and focus on the case where the players are indifferent to whether the constraints of other players hold.     

篮球视频中球员的分割与跟踪算法

分割与跟踪一直是视频图像处理的一个热门问题。针对篮球视频中激烈运动的球员队属和跟踪问题,实现了一个实时的球员分割与跟踪算法。首先,不同于一般的分割方法,采用基于两个级别（像素级和帧级）实时分割和背景更新的背景减除方法,实现了对球员的分割;接着,通过将球员与模板进行马式距离比较来辨识球员队属;然后,使用基于核的目标跟踪方法,实现了在激烈比赛中对球员的准确跟踪。实验结果表明,提出的算法能够很好地辨别各个球员的队属问题并在不完全遮挡的情况下跟踪多个球员,而且在球员形态变化较大时也能稳定地跟踪。     

Quantum games and quaternionic strategies

It is well-known that the phenomenon of entanglement plays a fundamental role in quantum game theory. Occasionally, games constructed via maximally entangled initial states (MEIS) will have new Nash equilibria yielding to the players higher payoffs than the ones they receive in the classical version of the game. When examining these new games for Nash equilibrium payoffs, a fundamental question arises; does a suitable choice of an MEIS improve the lot of the players? In this paper, we show that the answer to this question is yes for at least the case of a variant of the well-known two player, two strategy game of Chicken. To that end, we generalize Landsburg’s quaternionic representation of the payoff function of two player, two strategy maximally entangled states to games where the initial state is chosen arbitrarily from a circle of maximally entangled initial states and for the corresponding quantized games show the existence of superior Nash equilibrium payoffs when an MEIS is appropriately chosen.     

When Can Limited Randomness Be Used in Repeated Games?

The central result of classical game theory states that every finite normal form game has a Nash equilibrium, provided that players are allowed to use randomized (mixed) strategies. However, in practice, humans are known to be bad at generating random-like sequences, and true random bits may be unavailable. Even if the players have access to enough random bits for a single instance of the game their randomness might be insufficient if the game is played many times. In this work, we ask whether randomness is necessary for equilibria to exist in finitely repeated games. We show that for a large class of games containing arbitrary two-player zero-sum games, approximate Nash equilibria of the n-stage repeated version of the game exist if and only if both players have Ω(n) random bits. In contrast, we show that there exists a class of games for which no equilibrium exists in pure strategies, yet the n-stage repeated version of the game has an exact Nash equilibrium in which each player uses only a constant number of random bits. When the players are assumed to be computationally bounded, if cryptographic pseudorandom generators (or, equivalently, one-way functions) exist, then the players can base their strategies on “random-like” sequences derived from only a small number of truly random bits. We show that, in contrast, in repeated two-player zero-sum games, if pseudorandom generators do not exist, then Ω(n) random bits remain necessary for equilibria to exist.     

A fuzzy approach to strategic games

A game is a decision-making situation with many players, each having objectives that conflict with each other. The players involved in the game usually make their decisions under conditions of risk or uncertainty. In the paper, a fuzzy approach is proposed to solve the strategic game problem in which the pure strategy set for each player is already defined. Based on the concepts of fuzzy set theory, the approach uses a multicriteria decision-making method to obtain the optimal strategy in the game, a method which shows more advantages than the classical game methods. Moreover, with this approach, some useful conclusions are reached concerning the famous “prisoner's dilemma” problem in game theory     

Altruistic behavior in a nonantagonistic positional differential game

We consider a two-person nonantagonistic positional differential game (NPDG) whose dynamics is described by an ordinary nonlinear vector differential equation. Constraints on values of players’ controls are geometric. Final time of the game is fixed. Payoff functionals of both players are terminal. The formalization of positional strategies in an NPDG is based on the formalization and results of the general theory of antagonistic positional differential games (APDGs) (see monographs by N.N. Krasovskii and A.I. Subbotin [3, 4]). Additionally, in the present paper we assume that each player, together with the usual, normal (nor), type of behavior aimed at maximizing his own functional, can use other behavior types introduced in [2, 5]. In particular, these may be altruistic (alt), aggressive (agg), and paradoxical (par) types. It is assumed that in the course of the game players can switch their behavior from one type to another. Using the possibility of such switches in a repeated bimatrix 2 × 2 game in [5, 6] allowed to obtain new solutions of this game. In the present paper, extension of this approach to NPDGs leads to a new formulation of the problem. In particular, of interest is the question of how players’ outcomes at Nash solutions are transformed. An urgent problem is minimizing the time of “abnormal” behavior while achieving a good result. The paper proposes a formalization of an NPDG with behavior types (NPDGwBT). It is assumed that in an NPDGwBT each player, simultaneously with choosing a positional strategy, chooses also his own indicator function defined on the whole game horizon and taking values in the set {normal, altruistic, aggressive, paradoxical}. The indicator function of a player shows the dynamics of changes in the behavior type demonstrated by the player. Thus, in this NPDGwBT each player controls the choice of a pair {positional strategy, indicator function}. We define the notion of a BT-solution of such a game. It is expected that using behavior types in the NPDGwBT which differ from the normal one (so-called abnormal types) in some cases may lead to more favorable outcomes for the players than in the NPDG. We consider two examples of an NPDGwBT with simple dynamics in the plane in each of which one player keeps to altruistic behavior type over some time period. It is shown that in the first example payoffs of both players increase on a BT-solution as compared to the game with the normal behavior type, and in the second example, the sum of players’ payoffs is increased.     

A Quantum Treatment of Public Goods Economics

Quantum generalizations of conventional games broaden the range of available strategies, which can help improve outcomes for the participants. With many players, such quantum games can involve entanglement among many states which is difficult to implement, especially if the states must be communicated over some distance. This paper describes a quantum approach to the economically significant n-player public goods game that requires only two-particle entanglement and is thus much easier to implement than more general quantum mechanisms. In spite of the large temptation to free ride on the efforts of others in the original game, two-particle entanglement is sufficient to give near optimal expected payoff when players use a simple mixed strategy for which no player can benefit by making different choices. This mechanism can also address some heterogeneous preferences among the players. PACS: 03.67-a; 02.50Le; 89.65.Gh     

Ad Hoc网络中基于重复博弈的攻击预测模型

大多数入侵检测系统预测攻击行为能力较弱,不能实时主动地响应攻击。针对该问题,提出一种基于重复博弈的攻击预测模型。通过建立入侵者和入侵检测系统之间的阶段博弈模型,给出阶段博弈的纳什均衡,并求出重复博弈情况下的子博弈精炼纳什均衡。使用QRE模型预测攻击者和防御者在博弈阶段1~t中选择各种策略的概率,利用Gambit分析得出预测结果。基于GloMoSim的仿真结果表明,相比纳什均衡模型,QRE均衡模型的预测效果更好。     

What's in a name? Ages and names predict the valence of social interactions in a massive online game

Multi-player online battle arena games (MOBAs) are large virtual environments requiring complex problem-solving and social interaction. We asked whether these games generate psychologically interesting data about the players themselves. Specifically, we asked whether user names, which are chosen by players outside of the game itself, predicted in-game behaviour. To examine this, we analysed a large anonymized dataset from a popular MOBA (‘League of Legends’) – by some measures the most popular game in the world.We find that user names contain two pieces of information that correlate with in-game social behaviour. Both player age (estimated from numerical sequences within name) and the presence of highly anti-social words are correlated with the valences of player/player interactions within the game.Our findings suggest that players' real-world characteristics influence behaviour and interpersonal interactions within online games. Anonymized statistics derived from such games may therefore be a valuable tool for studying psychological traits across global populations.     

Mixed scheduling with heterogeneous delay constraints in cyber-physical systems

The physical space and the cyber space are deeply coupled in Cyber-Physical Systems (CPS). The traffic flows are constrained by heterogeneous delay constraints. In order to provide real-time and predictable communication, the paper combines the distributed scheduling algorithm with game theory. A non-cooperative game is proposed to form the scheduling set in the contention-based multiple-access scenario. In the game, each player only has its delay knowledge and makes decision without the information of other competing players. The payoff function is designed to encourage players to give the transmission chance to the player with urgent packets. Simulation results demonstrate that the game-theoretic scheduling approach can improve the real-time performance compared with the existing scheduling algorithms under different scenarios.     

Price of Stability in Survivable Network Design

We study the survivable version of the game theoretic network formation model known as the Connection Game, originally introduced in Anshelevich et al. (Proc. 35th ACM Symposium on Theory of Computing, 2003). In this model, players attempt to connect to a common source node in a network by purchasing edges, and sharing their costs with other players. We introduce the survivable version of this game, where each player desires 2 edge-disjoint connections between her pair of nodes instead of just a single connecting path, and analyze the quality of exact and approximate Nash equilibria. This version is significantly different from the original Connection Game and have more complications than the existing literature on arbitrary cost-sharing games since we consider the formation of networks that involve many cycles.