Fictitious Play

Fictitious Play ( often written as: fictitious play, mutatis mutandis: moves in spirit), also known as Brown -Robinson learning process, is an analysis of game theory. Specifically Fictitious play is a convergent method for the determination of value and optimal strategy. This procedure was in 1951 by G.W. Brown ( 1951) as an algorithm has been introduced to find the optimal value in zero-sum games.

Fictitious play is part of the subregion of the evolutionary game theory. The basic idea of these theories are based on the assumption that players are looking for optimized solutions are not (fully ) act rationally.

History

Brown described in 1951 in his review, Fictitious Play, the player with the pass as a strategy the fictional game play in her head, this update in each round and adapt to the strategy that was chosen by their opponents in advance. Hence the naming of this strategy is, the strategies do not take place exclusively in the head, but all can be played.

In the modern game theory the idea is met with Browns no longer the priority given by this theory held earlier. The new representations differ with respect to the original publication, in the course of updating the new Beliefs before each game round. Brown assumes that the beliefs of each player alternately, in terms of the empirical distribution function of the opponent, adapted and updated. In contrast, modern game theorists believe that the beliefs are updated simultaneously by the players.

After 1951 Beliefs were only updated simultaneously, which, inter alia, due to the symmetrical treatment of decisions.

Furthermore, it was Fictitous Play then used to approximate the optimal strategy to calculate. This is also very outdated and only found at the present time, the algorithm of Nash equilibrium practical application. Thus, the optimal strategies are not approximated, but determined by the following algorithm:

Today Fictitious play is because of the enormous complexity, almost exclusively been applied in computer science. There are very complex, game-theoretic problems with two people, such as Chess or backgammon, analyzed by Fictitious Play.

Evolutionary game theory

Fictitious play is based called the assumptions of evolutionary, also evolutionary game theory. Their approach differs from the "traditional" game theory is that it turns away from the rationality arguments of the players. Instead, it is assumed that each player is assigned to exactly one possible strategy that is not optimized due to an irrational assumption, the payoff of the players. In addition, the player in such games is not aware that he is in a game. This strategy is not limited to the clear rules of a game, but represents an evolutionary development in which the player is a " species " symbolize.

In the model of evolutionary game theory, the players always meet each other in pairs. The probability to encounter a specific strategy types, depends on the proportion of this strategy on the totality of all possible strategies. In this model we no longer speak of a set of strategies, but from a "population".

Practical application in economics will find the theories of evolutionary game theory, especially in fields of tax and electoral systems, standards of conduct and ownership structures.

Learning Strategies

Fictitious play is included in this part of the field of game theory. These strategies are applied only to repetitive games, as their best responses are based on decisions that have been taken in the past. At these decisions in the past, Beliefs be adapted, which is also called Belief Learning.

Reinforcement Learning is a reinforcement of the Learning Strategies, as is assumed here that players play strategies more frequently, who introduced them in the past profits.

Model Fictitious Play

Fictitious play is designed to agents in a position to put to approximate optimal solutions in a very short time. In each round, each player plays the best response, which is geared to the past, opponent's moves and the highest winning percentage generated. For Fictitious Play, each player assumes that the other players follow a stationary strategy. A stationary strategy is characterized by individual decisions that are taken independently from the decision time.

In the first round of Fictitious Play any strategy should be chosen, because you can not access any historical strategies of the other players.

From the second round, players take the average of the historical strategies of the counterparty as a basis for its action forecast in the next game. This is due to the assumption that the counterparty will also play in the upcoming game after its historic strategy frequency. Using this analysis of past strategies, the player plays the best strategy against them.

Fictitious play is only successful if the opponent actually follow a stationary strategy. Follow the Opponents, however, a strategy based on a different basis ( for example, when the opponent is based only on the last played strategy ), fictious play is not a successful strategy.

Assumptions of the model

It is assumed that a repetitive game with two fixed people, which their decisions simultaneously. The Beliefs of players are formed on the basis of games played in the past strategies of the opponent's. Both players play stationary strategies.

Mathematical definitions

It is considered the symmetrical formation of the Beliefs of a game with two players in the following.

Is the pure strategy space of the two players with

, Is a historical game.

Be the number occurs in the. So and

Now the starting conditions for to be determined. For his

With these conditions, now the averages are calculated as

Again, since this corresponds to

Brown's definition from 1951

A best response of a player on the strategy of the opponent with.

Is given and is called a pair of functions

, Fictitious Play, when applicable in each period,

Are that and and recursively and determined.

This means that a player is only optimal behaves when his opponent actually plays or - otherwise not!

Convergence properties of Fictitious Play

In the long run Fictitious Play only under special assumptions to a Nash equilibrium. In Fictitious Play Nash equilibria are absorbing, which means if a Nash equilibrium is played in any round of the game by all the players, it follows that for each subsequent game also the Nash equilibrium is played. Furthermore, it can be shown that there is a correlation between Nash equilibrium and the probabilities forms when Fictitious play converges to a distribution.

Since Fictitous Play does not always converge to distributions, other update dynamics are applied to beliefs for the next round form, such as Replicator Dynamics. This method is more complicated than Fictitious Play, it can be assumed with certainty that the results converge.

Fictitious play converges with security in the following cases:

Although Fictitious Play also does not apply as a general solution concept ( Shapley 1964 ), but it converges in principle against half of approximate equilibria ( Conitzer 2009; Goldberg, Savani, Sorensen, Ventre, 2011).

If all players choose their strategies according to Fictitious Play, the strategy is weakened by the resulting Nash equilibria. A typical result of this is the limit -cycle behavior, which increases with increasing number of games. In some specific cases, the product of empirical Verteilungt against the Nash equilibrium converges, although played in cycles, like matching pennies.

Practical Application

Be the most popular place Fictitious play nowadays only in poker. Pioneer in the application of Fictitious Play in poker ( in this case we are only talking about the poker game Texas Hold'em ) was Duziak 2006. Through Fictitious Play the complexity of the game states is greatly simplified.

There are at Poker 10 ^ 18 possible game states, which are reduced with Fictitious Play in 10 ^ 7. This abstraction may have different algorithms based. In this case is mainly due to the poker called " bucketing " (English, buckets ) as possible, since in this case the size of the algorithm is reduced, without having to abstract the underlying cause. This happens because hands (poker) a similar value are grouped into different " buckets ". If you now have abstracted the game, it is now essential if one wants to optimize Fictitious play its strategy to develop a well-defined game tree. This tree quickly assumes gigantic dimensions, so that one sorted out lower odds, and cuts off those paths of the tree. Thus, the game tree is getting smaller and the pseudo- optimal strategy can be calculated during the game. The pseudo- optimality is concluded therefore, as the game states are greatly simplified, resulting in lower chances of winning.

Criticism of Fictitious Play

In practice it is fictious play, just hardly found except in poker, because it is not suitable for games with several people and plays no optimal strategies. Even simple games with more than two people can due to the high number of terms no longer be calculated, so this in the foreseeable future is only possible for computers.

For more complex games, there is a more efficient algorithm, called Joint Strategy Fictitious Play. This simplifies the complexity of Fictitious Play, since it considers the historical decisions and thus the upcoming strategies of the opponents is approximated. The simplification is that your strategy is chosen randomly and is not adapted to all players. Thus, the computational cost is much lower, the expense of optimality. In the case of the 2-person game, the strategy of Joint Strategy Fictitious Play corresponds to the original Fictitious Play. However, Joint Strategy Fictitious Play is practicable with a number of persons > 2, in contrast to Fictitious Play in games. In addition to the high computational cost of Ficitious play, the observation effort of the previous strategies is another aspect that makes this strategy hardly possible in practice.