Diferenças

Aqui você vê as diferenças entre duas revisões dessa página.

--- geopro:pedro:games [2008/02/26 17:11] – 150.163.67.167
+++ geopro:pedro:games [2012/02/16 20:00] (atual) – pedro
@@ Linha 1: / Linha 1: @@
-====== Evolutionary Games ======
+====== Games ======
+==== Braess's paradox ====
+Braess's paradox, credited to the mathematician Dietrich Braess, states that **adding extra capacity to a network when the moving entities selfishly choose their route, can in some cases reduce overall performance**. This is because the Nash equilibrium of such a system is not necessarily optimal.
+The paradox is stated as follows: "For each point of a road network, let there be given the number of cars starting from it, and the destination of the cars. Under these conditions one wishes to estimate the distribution of traffic flow. Whether one street is preferable to another depends not only on the quality of the road, but also on the density of the flow. If every driver takes the path that looks most favorable to him, the resultant running times need not be minimal. Furthermore, it is indicated by an example that an extension of the road network may cause a redistribution of the traffic that results in longer individual running times."
+====Schelling point====
+In game theory, a Schelling point (also called focal point) is a solution that people will tend to use in the absence of communication, because it seems natural, special or relevant to them. Schelling describes "focal point[s] for each person’s expectation of what the other expects him to expect to be expected to do." Consider a simple example: **two people unable to communicate with each other are each shown a panel of four squares and asked to select one; if and only if they both select the same one, they will each receive a prize. Three of the squares are blue and one is red**. Assuming they each know nothing about the other player, but that they each do want to win the prize, then they will, reasonably, both choose the red square. Of course, the red square is not in a sense a better square; they could win by both choosing any square. And it is the "right" square to select only if a player can be sure that the other player has selected it; but by hypothesis neither can. It is the most salient, the most notable square, though, and lacking any other one most people will choose it, and this will in fact (often) work.
 ====Game Theory: Dominance, Nash Equilibrium, Symmetry====
-|B. L. Slantchev, 2007|
+|B. L. Slantchev, 2007| {{http://www.leg.ufpr.br/~pedro/slantchev-game-theory.pdf|pdf}}|
 That is, we must be able to assume not only that all players are rational, but also
@@ Linha 13: / Linha 21: @@
 Five Interpretations of Mixed Strategies:
-  - **Deliberate Randomization:** One (naive) view is that playing a mixed strategy means that the player deliberately introduces randomness into his behavior. That is, a player who uses a mixed strategy commits to a randomization device which yields the various pure strategies with the probabilities specified by the mixed strategy. This interpretation makes sense for games where players try to outguess each other (e.g. strictly competitive games, poker, and tax audits). However, it has two problems.
+  - **Deliberate Randomization:** One (naive) view is that playing a mixed strategy means that the player deliberately introduces randomness into his behavior. That is, **a player who uses a mixed strategy commits to a randomization device which yields the various pure strategies with the probabilities specified by the mixed strategy**. This interpretation makes sense for games where players try to outguess each other (e.g. strictly competitive games, poker, and tax audits). However, it has two problems.
     * the notion of mixed strategy equilibrium does not capture the players’ motivation to introduce randomness into their behavior. This is usually done in order to influence the behavior of other players. We shall rectify some of this once we start working with extensive form games, in which players move can sequentially.
     * perhaps more troubling, in equilibrium a player is indifferent between his mixed strategy and any other mixture of the  strategies in the support of his equilibrium mixed strategies. His equilibrium mixed strategy is only one of many strategies that yield the same expected payoff given the other players’ equilibrium behavior.
-  - **Equilibrium as a Steady State:** players act repeatedly and ignore any strategic link that may exist between successive interactions. In this sense, a mixed strategy represents information that players have about past interactions. For example, if 80% of past play by player 1 involved choosing strategy A and 20% involved choosing strategy B, then these frequencies form the beliefs each player
+  - **Equilibrium as a Steady State:** players act repeatedly and ignore any strategic link that may exist between successive interactions. In this sense, **a mixed strategy represents information that players have about past interactions**. For example, if 80% of past play by player 1 involved choosing strategy A and 20% involved choosing strategy B, then these frequencies form the beliefs each player can form about the future behavior of other players when they are in the role of player 1. Thus, the corresponding belief will be that player 1 plays A with probability .8 and B with probability .2. In equilibrium, the frequencies will remain constant over time.
-can form about the future behavior of other players when they are in the role of player 1. Thus, the corresponding belief will be that player 1 plays A with probability .8 and B with probability .2. In equilibrium, the frequencies will remain constant over time.
+  - **Pure Strategies in an Extended Game:** Before a player selects an action, he may receive a private signal on which he can base his action. Most importantly, the player may not consciously link the signal with his action (e.g. a player may be in a particular mood which made him choose one strategy over another). This sort of thing will appear random to the other players if they (a) perceive the factors affecting the choice as irrelevant, or (b) find it too difficult or costly to determine the relationship. The problem with this interpretation is that it is hard to accept the notion that players deliberately make choices depending on factors that do not affect the payoffs. However, since in a mixed strategy equilibrium a player is indifferent among his pure strategies in the support of the mixed strategy, it may make sense to pick one because of mood.
-  - **Pure Strategies in an Extended Game:** Before a player selects an action, he may receive a private signal on which he can base his action. Most importantly, the player may not consciously link the signal with his action (e.g. a player may be in a particular mood which made him choose one strategy over another). This sort of thing will appear random to the other players if they (a) perceive the factors affecting the choice as irrelevant, or (b) find it too difficult or costly to determine the relationship.
+  - **Pure Strategies in a Perturbed Game:** Harsanyi introduced another interpretation of mixed  strategies, according to which a game is a frequently occurring situation, in which players’ preferences are subject to small random perturbations. Like in the previous section, random factors are introduced, but here they affect the payoffs. Each player observes his own preferences but not that of other players. The mixed strategy equilibrium is a summary of the frequencies with which the players choose their actions over time. Establishing this result requires knowledge of Bayesian Games, which we shall obtain later in the course. Harsanyi’s result is so elegant because even if no player makes any effort to use his pure strategies with the required probabilities, the random variations in the payoff functions induce each player to choose the pure strategies with the right frequencies. The equilibrium behavior of other players is such that a player who chooses the uniquely optimal pure strategy for each realization of his payoff function chooses his actions with the frequencies required by his equilibrium mixed strategy.
-The problem with this interpretation is that it is hard to accept the notion that players deliberately make choices depending on factors that do not affect the payoffs. However, since in a mixed strategy equilibrium a player is indifferent among his pure strategies in the support of the mixed strategy, it may make sense to pick one because of mood.
+  - **Beliefs:** Other authors prefer to interpret mixed strategies as beliefs. That is, **the mixed strategy profile is a profile of beliefs, in which each player’s mixed strategy is the common belief of all other players about this player’s strategies**. Here, each player chooses a single strategy, not a mixed one. An equilibrium is a steady state of beliefs, not actions. This interpretation is the one we used when we defined MSNE in terms of best responses. The problem here is that each player chooses an action that is a best response to equilibrium beliefs. The set of these best responses includes every strategy in the support of the equilibrium mixed strategy (a problem similar to the one in the first interpretation).
-  - **Pure Strategies in a Perturbed Game:**
-Harsanyi introduced another interpretation of mixed strategies, according to which a game is a frequently occurring situation, in which players’ preferences are subject to small random perturbations. Like in the previous section, random factors are introduced, but here they affect the payoffs. Each player observes his own preferences but not that of other players. The mixed strategy equilibrium is a summary of the frequencies with which the players choose their actions over time. Establishing this result requires knowledge of Bayesian Games, which we shall obtain later in the course. Harsanyi’s result is so elegant because even if no player makes any effort to
-use his pure strategies with the required probabilities, the random variations in the payoff functions induce each player to choose the pure strategies with the right frequencies. The equilibrium behavior of other players is such that a player who chooses the uniquely optimal pure strategy for each realization of his payoff function chooses his actions with the frequencies required by his equilibrium mixed strategy.
+====The Economics of Fair Play====
-  - **Beliefs:** Other authors prefer to interpret mixed strategies as beliefs. That is, the mixed strategy profile is a profile of beliefs, in which each player’s mixed strategy is the common belief of
+|K. Sigmund and E. Fehr and M. A. Nowak, 2002| Scientific American|
-all other players about this player’s strategies. Here, each player chooses a single strategy, not a mixed one. An equilibrium is a steady state of beliefs, not actions. This interpretation
-is the one we used when we defined MSNE in terms of best responses. The problem here is
+one round ultimatum game. game of the "sharing" pool with and without punishment. homo economicus and homo emoticus
-that each player chooses an action that is a best response to equilibrium beliefs. The set of
-these best responses includes every strategy in the support of the equilibrium mixed strategy
+If, for instance, the proposer is chosen not by a flip of a coin but
-(a problem similar to the one in the first interpretation).
+by better performance on a quiz, then offers are routinely a bit lower and get
+accepted more easily — the inequality is felt to be justified.
+our emotional apparatus has been shaped by millions of years of living in small groups, where
+it is hard to keep secrets. Our emotions are thus not finely tuned to interactions
+occurring under strict anonymity. We expect that our friends, colleagues and
+neighbors will notice our decisions. If others know that I am content
+with a small share, they are likely to make me low offers.
+Because one-shot interactions were rare during human evolution, these emotions
+do not discriminate between one-shot and repeated interactions.
+====The Power of Memes====
+|S. Blackmore, 2000|
+ver URGENTE: colocar na apresentacao para o referata:
+"an evolution of ideas, or memes"
@@ Linha 198: / Linha 223: @@
 |Nowak and Sigmund, 1992| Nature|
+====The Work of John Nash in Game Theory====
+|H. W. Kuhn, J. C. Harsanyi, R. Selten, J. W. Weibull, E. van Damme, J. F. Nash, P. Hammerstein, 1994| [[http://www.leg.ufpr.br/~pedro/nash-lecture.pdf|pdf]]|
+A Nash equilibrium is defined as a strategy combination with the property
+that every player’s strategy is a best reply to the other players’ strategies.
+**This of course is true also for Nash equilibria in mixed strategies. But in the
+latter case, besides his mixed equilibrium strategy, each player will also have
+infinitely many alternative strategies that are his best replies to the other players’
+strategies. This will make such equilibria potentially unstable.**
+In view of this fact, I felt it was desirable to show that “almost all”
+Nash equilibria can be interpreted as strict equilibria in pure strategies of a
+suitably chosen game with randomly fluctuating payoff functions.
+====Non-Cooperative Games====
+|J Nash, 1950| [[http://www.leg.ufpr.br/~pedro/papers/nash-thesis.pdf|pdf]]|
+It is assumed that each participant acts independently, without collaboration or communication
+with any of the others.
+If we transform the payoff functions linearly: p_i' = a_i p_i + b_i, where a_i > 0, the game
+will be essentially the same. Note that equilibrium points are preserved under such
+transformations.
+Nash proposed two interpretations for the concept of equilibrium. The first one concerns
+extremely rational players, which cannot communicate, have common knowledge and play the
+game only once.
+We shall now take up the "mass-action" interpretation of equilibrium points. In this interpretation
+solutions have no great significance. It is unnecessary to assume that the participants have full
+knowledge of the game, or the ability and inclination to go through any complex reasoning process.
+But the participants are supposed to accumulate empirical information on the relative advantages
+of the various pure strategies at their disposal.
+To be more detailed, we assume that there is a population (in the sense of statistics) of
+participants for each position of the game.
+====Games with Finite Resources====
+{{  http://leg.est.ufpr.br/~pedro/figures/finite-resources.jpg}}
+Games with finite resources are two-person zero-sum multistage games defined by Gale (1957) to have the following structure.
+Player I's resource set is A = {1, 2, ..., N}.
+Player II's resource set is B = {1, 2, ..., N}.
+Associated with these resources is an NxN payoff matrix M = (M(i, j)). The game is played in N stages and each player is allowed to use each resource once and only once during these N stages.