Multi-objective design method based on evolution game and its application for suspension

Through research and bionics of biology survival mode, game players with competition, cooperation and self-adaptation capacity are introduced in the multi-objective design. The dynamic behavior and bounded rationality in game processes for players are considered according to Chinese saying “In success, commit oneself to the welfare of the society; in distress, maintain one’s own integrity”. An evolution rule, Poor-Competition-Rich-Cooperation (short for PCRC), is proposed. Then, the corresponding payoff functions of competition and cooperation behavior are established and a multi-objective design method based on evolution game is proposed. The calculation steps are as follows: 1) Taking the design objectives as different game players, and calculating factors of the design variables to objective and fuzzy clustering. The design variables are divided into multiple strategy subsets owned by each game player. 2) According to the evolution rule, each player determines its behavior and payoff function in this game round. 3) In their own strategy subsets, each game player takes their payoff as mono-objective for optimization. It gives the best strategy upon other players. And so the best strategies of all players conform the group strategy in this round. The final equilibrium solution is obtained through multi-round game based on convergence criterion. The validity and reliability of this method are shown by the results of an example of a tri-objective optimization design of passive suspension parameters.     

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.     

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.     

具有学习机制及情绪特征的连续进化博弈仿真

当前博弈理论的研究主要集中在合作竞争及稳定性的分析上,有关心理因素对博弈过程的影响的研究尚不多见。将情绪特征引入连续进化博弈过程,可更为真实地仿真群体博弈过程。针对不同决策风格的个体,建立个体学习机制及根据情绪特征的策略变异机制。仿真结果表明,学习能力有助于个体之间的博弈平均合作率及群体收益总量的提高;情绪对个体收益产生一定的波动性影响,但对群体平均收益的波动性影响不大。     

基于演化博弈的P2P网络资源共享机制的研究

根据P2P网络的自组织、动态性、可扩展性等特点,针对当前P2P网络资源共享的微观、静态等研究方法的局限性,运用演化博弈理论方法,建立了一个P2P网络节点资源共享机制的演化博弈模型,分析了网络节点资源共享的动态演变过程。研究结果表明,该系统的演化方向与双方博弈的支付矩阵相关,同时与系统初始状态相关。并得出,共享产生的超额利润、共享的初始成本、节点服务能力的差异及其贴现因子是影响网络资源共享演变的关键因素。     

Game-theoretic analysis of an ancient Chinese horse race problem

This paper analyzes a legendary Chinese horse race problem involving the King of Qi and General Tianji which took place more than 2000 years ago. In this problem each player owns three horses of different speed classes and must choose the sequence of horses to compete against each other. Depending on the payoffs received by the players as a result of the horse races, we analyze two groups of constant-sum games. In each group, we consider three separate cases where the outcomes of the races are (i) deterministic, (ii) probabilistic within the same class, and (iii) probabilistic across classes. In the first group, the player who wins the majority of races receives a one-unit payoff. For this group we show analytically that the three different games with non-singular payoff matrices have the same solution where each player has a unique optimal mixed strategy with equal probabilities. For the second group of games where the payoff to a player is the total number of races his horses have won, we use linear programming with non-numeric data to show that the solution of the three games are mixed strategies given as a convex combination of two extreme points. We invoke results from information theory to prove that to maximize the opponent's “entropy” the players should use the equal probability mixed strategy that was found for the one-unit games.     

Interactive strategy sets in multiple payoff games

In game theory, it is usually assumed that each player has only one payoff function and the strategy set of the game is composed of the topological product of individual players’ strategy sets. In real business and system design or control problems, however, players’ strategy sets may be interactive and each player may have more than one payoff function. This paper, investigates the more general situation of multiple payoff and multiple person games in a normal form. In this paper, each player has several payoff functions which are dominated by certain convex cones, and the feasible strategy set of each player may be interactive with those of the other players. This new model is applied to a classical example without requiring variational and quasi-variational inequalities, or point-to-set mappings.     

Evolution of iterated prisoner's dilemma game strategies in structured demes under random pairing in game playing

We discuss the evolution of strategies in a spatial iterated prisoner's dilemma (IPD) game in which each player is located in a cell of a two-dimensional grid-world. Following the concept of structured demes, two neighborhood structures are used. One is for the interaction among players through the IPD game. A player in each cell plays against its neighbors defined by this neighborhood structure. The other is for mating strategies by genetic operations. A new strategy for a player is generated by genetic operations from a pair of parent strings, which are selected from its neighboring cells defined by the second neighborhood structure. After examining the effect of the two neighborhood structures on the evolution of cooperative behavior with standard pairing in game-playing, we introduce a random pairing scheme in which each player plays against a different randomly chosen neighbor at every round (i.e., every iteration) of the game. Through computer simulations, we demonstrate that small neighborhood structures facilitate the evolution of cooperative behavior under random pairing in game-playing.     

On the effect of quantum noise in a quantum prisoner’s dilemma cellular automaton

The disrupting effect of quantum noise on the dynamics of a spatial quantum formulation of the iterated prisoner’s dilemma game with variable entangling is studied in this work. The game is played in the cellular automata manner, i.e., with local and synchronous interaction. It is concluded in this article that quantum noise induces in fair games the need for higher entanglement in order to make possible the emergence of the strategy pair (Q, Q), which produces the same payoff of mutual cooperation. In unfair quantum versus classic player games, quantum noise delays the prevalence of the quantum player.     

The interpretation of discontinuous state feedback control laws as nonanticipative control strategies in differential games

In differential games, one player chooses a feedback strategy to maximize a payoff. The other player counters by applying a minimizing open loop control. Classical notions of feedback strategies, based on state feedback control laws for which the corresponding closed loop dynamics uniquely define a state trajectory, are too restrictive for many problems, owing to the absence of minimizing classical feedback strategies or because consideration of classical feedback strategies fails to define, in a useful way, the value of the game. A number of feedback strategy concepts have been proposed to overcome this difficulty. That of Elliot and Kalton, according to which a feedback strategy is a nonanticipative mapping between control functions for the two players, has been widely taken up because it provides a value of the game which connects, via the Hamilton-Jacobi-Isaacs equation, with other fields of systems science. Heuristic analysis of specific games problems often points to discontinuous optimal feedback strategies. These cannot be regarded as classical feedback control strategies because the associated state trajectories are not in general unique. We give general conditions under which they can be interpreted as generalized feedback strategies in the sense of Elliot and Kalton.     

Evolution of cooperative behavior among heterogeneous agents with different strategy representations in an iterated prisoner’s dilemma game

The iterated prisoner’s dilemma (IPD) game has frequently been used to examine the evolution of cooperative behavior among agents. When the effect of representation schemes of IPD game strategies was examined, the same representation scheme was usually assigned to all agents. That is, in the literature, a population of homogeneous agents was usually used in computational experiments. In this article, we focus on a slightly different situation where every agent does not necessarily use the same representation scheme. That is, a population can be a mixture of heterogeneous agents with different representation schemes. In computational experiments, we used binary strings of different lengths (i.e., three-bit and five-bit strings) to represent IPD game strategies. We examined the evolution of cooperative behavior among heterogeneous agents in comparison with the case of homogeneous ones for the standard IPD game with typical payoff values of 0, 1, 3, and 5. Experimental results showed that the evolution of cooperative behavior was slowed down by the use of heterogeneous agents. It was also demonstrated that a faster evolution of cooperative behavior is achieved among majority agents than among minority ones in a heterogeneous population.     

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     

Learning through reinforcement for N-person repeated constrained games

The design and analysis of an adaptive strategy for N-person averaged constrained stochastic repeated game are addressed. Each player is modeled by a stochastic variable-structure learning automaton. Some constraints are imposed on some functions of the probabilities governing the selection of the player's actions. After each stage, the payoff to each player as well as the constraints are random variables. No information concerning the parameters of the game is a priori available. The "diagonal concavity" conditions are assumed to be fulfilled to guarantee the existence and uniqueness of the Nash equilibrium. The suggested adaptive strategy which uses only the current realizations (outcomes and constraints) of the game is based on the Bush-Mosteller reinforcement scheme in connection with a normalization procedure. The Lagrange multipliers approach with a regularization is used. The asymptotic properties of this algorithm are analyzed. Simulation results illustrate the feasibility and the performance of this adaptive strategy.     

Promoting cooperation by setting a ceiling payoff for defectors under three-strategy public good games

The puzzle of altruistic behaviours among multi-agent systems poses a dilemma, which has been an overlapping topic that covers many subjects. The public goods game can be regarded as a paradigm for modelling and exploring it. In the traditional definition of public goods game, the equally divided benefit among all participants leads to the dominance of defection. Much effort has been made to explain the evolution of cooperation, including the model in which the payoff ceilings for defectors are introduced. Further, we study a three-strategy evolutionary public goods game by providing the role of being loners. The payoff ceilings will take effect when the number of cooperators exceeds some threshold. Analysis results by following the replicator dynamics indicate that lower values of the payoff ceilings can better promote levels of public cooperation. Importantly, a remarkable cyclic route has been found: when receiving relative lower benefits, loners act as catalysts, helping the population to escape from mutual defection to cooperation. And, the stable equilibrium points from cooperation to isolation can be realised by improving the fixed payoffs of loners. Finally, broader ceilings also for cooperators provide us more hints about how to suppress the spreading of defectors under certain conditions.     

Qubit flip game on a Heisenberg spin chain

We study a quantum version of a penny flip game played using control parameters of the Hamiltonian in the Heisenberg model. Moreover, we extend this game by introducing auxiliary spins which can be used to alter the behaviour of the system. We show that a player aware of the complex structure of the system used to implement the game can use this knowledge to gain higher mean payoff.     

时间尺度与选择倾向性协同作用下的演化博弈模型

针对合作行为的涌现与维持问题，基于演化博弈理论和网络理论，提出了一种促进合作的演化博弈模型。该模型同时将时间尺度、选择倾向性引入到演化博弈中。在初始化阶段，根据持有策略的时间尺度将个体分为两种类型：一种个体在每个时间步都进行策略更新；另一种个体在每一轮博弈后，以某种概率来决定是否进行策略更新。在策略更新阶段，模型用个体对周围邻居的贡献来表征他的声誉，并假设参与博弈的个体倾向于学习具有较好声誉邻居的策略。仿真实验结果表明，所提出的时间尺度与选择倾向性协同作用下的演化博弈模型中，合作行为能够在群体中维持；惰性个体的存在不利于合作的涌现，但是个体的非理性行为反而能够促进合作。     

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

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

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.     

一种新的(m+1,n)理性秘密分享机制

重复理性秘密分享机制仅适用于交互轮数无限的情形,但是无限轮的理性秘密分享机制的效率不高。为此,在(m,n) Shamir秘密分享机制的基础上,结合有限重复博弈,为每个参与者赋予一个参加协议的时限,由此提出一种新的(m+1,n)有限轮理性秘密分享机制。分析结果表明,当时限和参与者的效用函数满足一定条件时,可以得到一个常数轮的理性秘密分享机制,使所有理性参与者可以恢复秘密。     

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.