رویکرد QBD برای تئوری بازی تکاملی

Game theory is extensively used in economics to predict the best strategies in an evolutionary process of buying/selling, bargaining or in stock market. Many game solvers in the literature use simulation or even experimental games (pay the players). In general simulation takes a huge time and experimental games are very expensive. In this paper, we model the 2 × 2 non-symmetric game and the 3 × 3 symmetric game as finite, state dependent quasi-birth-and-death processes. We propose solution procedures based on the block Gaussian elimination for the 2 × 2 game and the block Gauss–Seidel iteration method for the 3 × 3 game. Our solver is a powerful tool that gives a probability distribution on the set of strategies available in the game, which helps to identify the best strategies. Furthermore, our game solver is very effective in terms of time and cost. We provide some illustrative examples.

Game theory is concerned with decision situations wherein one party is in conflict with another. Competitive situations arise in almost every facet of human activity––in parlor games, sports, military strategy, and business. In all of these situations, the results achieved depend on both our own action and that of our competitor. There are many features common to both simple games and complicated conflicts in business and industry. For this reason, knowledge of the theory of games should be helpful to the decision maker who continually faces competitive situations in business, industry, and government. One way to describe a game is by listing the players (or individuals) participating in the game, and for each player, listing the alternative choices (called actions or strategies) available to that player. In the case of a two-player game, the actions of the first player form the rows, and the actions of the second player the columns, of a matrix. The entries in the matrix are two numbers representing the payoff to the first and second player, respectively. A very famous game is the Prisoner
s Dilemma game. In this game the two players are partners in a crime who have been captured by the police. Each suspect is placed in a separate cell, and offered the opportunity to confess to the crime. The game can be represented by the following matrix of payoffs Note that higher numbers are better (more payoff). If neither suspect confesses, they go free, and split the proceeds of their crime which we represent by 5 units of utility for each suspect. However, if one prisoner confesses and the other does not, the prisoner who confesses testifies against the other in exchange for going free and gets the entire 10 units of utility, while the prisoner who did not confess goes to prison and gets nothing. If both prisoners confess, then both are given a reduced term, but both are convicted, which we represent by giving each 1unit of payoff: better than having the other prisoner confess, but not so good as going free. This game has fascinated game theorists for a variety of reasons. It is a simple representation of a variety of important situations. Consider, for example, two wholesalers competing through their respective supermarket chains. Each fall they must decide on whether they will conduct a promotion campaign the following winter. The larger wholesaler attempts to formulate his decision problem in terms of a two-person game. From past records he knows that in general his chain handles 60% of what he at first considers a fixed segment of the business and his competitor 40%. If he conducts a promotion campaign and his competitor does not, he attracts business not only from his competitor, but also from the other independent stores, and the combined volume of these two major wholesalers is increased by 10 units, with his volume increased 30 units and the competitor
s volume decreased 20 units. A similar relationship holds if the competitor is the only one to conduct a campaign. If both wholesalers conduct campaigns they both lose 10 units from their income under routine operations. The wholesaler decides to formulate the problem as a non-zerosum game. He uses as utility units the volume of business, measured in thousands of dollars, less the cost of a promotion campaign if such is conducted. The result is the following table, where his firm is represented by player 1.This is a two-person, non-zero-sum game of the prisoner
s dilemma type. The ‘‘promotion’’ strategy of each player dominates the other strategy, and so the game has only one equilibrium strategy pair, and the outcome corresponding to this pair is the (50,30) payoff. Thus, if the game is played non-cooperatively, the seemingly expected result favors the advertising agencies. Note, however, that the outcome (60,40) is more beneficial to both parties than the outcome (50,30). This non-cooperative game does not yield optimal profits for the wholesalers. If they could mutually agree (cooperate) not to hold promotion campaigns in the winter, they could realize this advantageous payoff. Many authors have observed that traditional game theory imposes too severe restrictions on the information processing capacity of the players and on the degree of rationality, especially in playing games with a complicated strategic structure. As a consequence, attention has shifted to evolutionary games, by introducing learning processes. The evolutionary, population-dynamic view of games is useful because it does not require the assumption that all players are sophisticated and think the others are also rational, which is often unrealistic. Instead, the notion of rationality is replaced with the much weaker concept of reproductive success: strategies that are successful on average will be used more frequently. Evolutionary game theory has extensive applications in many fields, such as business and biology. Excellent discussions are contained in [1,2]. The last decade has seen a rapid literature on the subject. Foster and Young [3] added a new perspective by introduction a stochastic noise term in the evolutionary framework. Kandori et al. [4] characterized bounded rationality and learning by three points • Inertia: not all players react instantaneously to their environment. • Myopia: while players are learning, they are not taking into account the long run implication of their strategy choices. • Mutation: there is a small probability that players change their strategies at random. Amir and Berninghaus [5] extended the model of Kandori et al. to continuous time. They considered a 2 · 2 symmetric game where an outside player is playing against a finite population. The population players switch from one strategy to another with transition rates function of average payoffs. They model the evolutionary process as a homogeneous Markov process with finite state space and derive its limiting distribution. Modelling games as Markovian processes is very interesting because it adds more convenience and simplicity to their study. It handles the above features such as inertia (sojourn times and transition times from one state to another are exponentially distributed) and myopia (players forget). In the present paper, we use the same approach to analyze a 2 · 2 non-symmetric and a 3 · 3 symmetric games. The evolutionary process turns out to be in both cases a state dependent quasibirth- and-death (QBD) process with finite state space. Numerical approaches developed by Stewart [6] are used to derive the limiting distribution of the 2 · 2 and 3 · 3 games. Our solver is a powerful alternative to simulation and experimental games. To the best of our knowledge, this is the first time that QBD processes are used to model evolutionary games. Section 2 describes the evolutionary models of the 2 · 2 non-symmetric and the 3 · 3 symmetric games. Section 3 summarizes relevant definition and results from Stewart [6]. In Section 4 the block Gaussian elimination and the block Gauss–Seidel iteration methods are adapted to solve the 2 · 2 and the 3 · 3 games, respectively. Examples and numerical results are given in Section 5. Concluding remarks and directions for further research end the paper in Section 6.

In this paper, a finite, state dependent QBD process is suggested to model some evolutionary games. These models were solved using efficient numerical methods. In all cases, the results obtained were as expected. Further studies can be made on the choice of . On one hand, the numerical techniques may be sensitive to the value of . On the other hand, how would this value affect the dynamic behaviour of the game.