2010-08-31

Aumann's View on Science and Game Theory

I was impressed by Robert Aumann, when I met him at the game theory conference in Brazil (link). And, after coming back to Japan, I got impressed again to see what he has written on the preface of the volume of his "Collected Papers." His view on science and game theory is very close to mine (perhaps, I have been unconsciously affected by his view or similar idea spread among theorists).

[A]ll the papers in the collection concern game theory, its applications and its tools. Beyond the subject matter, they also share a common methodological theme: they deal with relationships. Science is often characterized as a quest for truth, where truth is something absolute, which exists outside of the observer. But I view science more as a quest for understanding, where the understanding is that of the observer, the scientist. Such understanding is best gained by studying relations - relations between different ideas, relations between different phenomena, relations between ideas and phenomena.
(...)
Indeed, the idea of relationship is fundamental to game theory. Disciplines like economics or political science use disparate models to analyze monopoly, oligopoly, perfect competition, public goods, elections, coalition formation, and so on. In contrast, game theory uses the same tools in all these applications. (...) Perhaps the most exciting advance in game theory in recent years has been the connection with evolution: The realization that when properly interpreted, the fundamental notion of Nash equilibrium, which a priori reflects the behavior of consciously maximizing agents, is the same as an equilibrium of populations that reproduce blindly without regard to maximizing anything.
Aumann's message forward to Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis by Roth and Sotomayor (1990), which he describes as a book chronicles one of the outstanding success stories of the theory of games,  is also insightful. I again share his view on evaluating the good "matching" of theory and practice.

The theoretical part of the story begins in 1962, with the publication of the famous Gale-Shapley paper, "College Admissions and the Stability of Marriage." Since then, a large theoretical literature has grown from this paper, which is thoroughly covered in this book. But the most dramatic development came in 1984, when Roth published his discovery that the Gale-Shapley algorithm had in fact been in practical use already since 1951 for the assignment of interns to hospitals in the United States; it had evolved by a tirial-and-error process that spanned more than half a century.

2010-08-26

Lecture 2 (Dutta): Dynamic Programming 1

Original article (link) posted: 22/09/2005

Topics in the class

1) Conditional Probability and Feller Property
(a) The definitions of a transition function: q and the conditional expectation operator: T.
(b) The properties of Tg (g is a measurable function); measurable, non-negative (if g non-negative), and bounded (if g bounded).
(c) Feller Property.

2) Dynamic Programming Set Up
(d) The def. of a reward function and a feasibility correspondence.
(e) Example; Neo-classical growth model, Portfolio choice, Capital accumulation, Search, and, Price with inertia (menu cost).
(f) The def. of history and policy (action).
(g) Setting up optimization problem and value function.

3) Bellman (Optimality) Equation
(h) Necessity: If the value function V is measurable, then TV=V.
(i) Sufficiency: If the bounded and measurable function U solves U=TU, then U is larger than or equal to V. Additionally if there is a selection from the optimality equation, then U=V. Note) a selection from TU=U is a stationary Markovian policy which solves TU=U.

Comments

Basic concepts in Measure theory such as sigma-algebra and measurability are postulated. I should check what Feller Property exactly means. (I'm not sure if it's just a definition or with necessary and sufficient conditions.)

2010-08-22

Historical drama on the creation of game theory

I just came back to Tokyo after attending the SAET conference (link) in Singapore and the world congress of the Econometric Society (link) in China (Shanghai). It was a great experience to visit the two Asian countries that I have never been before. I really enjoyed the conferences, meeting lots of people such as my friends, co-authors, teachers, and big names.

Now it's time to go back to my work! Many thanks to everyone I met there. Hope all of you would have a productive academic year starting from September :)

The short article below is what I had prepared before I left Japan:

A new book on the early history of game theory came out recently. It focuses on the two founding fathers, Von Neumann and Morgenstern.

"Von Neumann, Morgenstern, and the Creation of Game Theory: From Chess to Social Science, 1900–1960" by Robert Leonard, Cambridge University Press (link)

As a reviewer's comment, Harold W. Kuhn, a professor emeritus of mathematics at Princeton university describes the book as follows:
The publication of The Theory of Games and Economic Behavior by John von Neumann and Oskar Morgenstern in 1944 was hailed by one reviewer as 'one of the major scientific achievements of the first half of the twentieth century.' Another reviewer signaled that 'the techniques applied by the authors in tackling economic problems are of sufficient generality to be valid in political science, sociology, or even military strategy.' In this exemplary study in the history of economics, Robert Leonard has given us a masterful account of the gestation of this work, starting with the importance of chess in European intellectual life at the beginning of the twentieth century and ending with the military applications of game theory at the RAND Corporation during the middle of the century.
The predecessor of the work is the author's 1995 article in the Journal of Economic Literature, which won the Best Article Award of the History of Economics Society.

Robert Leonard (1995) "Von Neumann, Morgenstern, and the Creation of Game Theory From Chess to Social Science, 1900–1960" (link)

2010-08-11

Bayesian Games

Original article (link) posted: 22/09/2005

The following is the memo about Bayesian Games. All the sentences are quoted from Myerson (1991) "Game Theory" (Chapter 2.8 and 2.9).

Background
A game with incomplete information is a game in which, at the first point in time when the players can begin to plan their moves in the game, some players already have private information about the game that other players do not know.
The initial private information that a player has at this point in time is called the type of the player.
Harsanyi (1967-68) argued that a generalization of the strategic form, called the Bayesian form, is needed to represent games with incomplete information.

Consistent model
Most of the Bayesian games that have been studied in applied game theory have beliefs that are consistent with a common prior. One reason for this tendency to use consistent models is that consistency simplifies the definition of the model. Furthermore, inconsistency often seems like a strikingly unnatural feature of a model. In a consistent model, differences in beliefs among players can be explained by differences in information, whereas inconsistent beliefs involve differences of opinion that cannot be derived from any differences in observations and must be simply assumed a priori.

Agreeing to disagree
In a sports match, suppose it is common knowledge among the coaches of two teams that each believes that his own team has a 2/3 probability of winning its next game against the other team, then the coaches' beliefs cannot be consistent with a common prior. In a consistent model, it can happen that each coach believes that his team has a 2/3 probability of winning, but this difference of beliefs cannot be common knowledge among the coaches. (see Aumann, 1976)

Bayesian Games are general enough?
To describe a situation in which many individuals have substantial uncertainty about one another's information and beliefs, we may have to develop a very complicated Bayesian-game model with large type sets and assume that this model is common knowledge among the players. This result begs the question; is it possible to construct a situation for which there are no sets of types large enough to contain all the private information that players are supposed to have, so that no Bayesian game could represent this situation?
Mertens and Zamir (1985) showed under some technical assumptions, that no such counterexample to the generality of the Bayesian game model can be constructed, because a universal belief space can be constructed that is always big enough to serve as the set of types for each player.
Although constructing an accurate model for any given situation may be extremely difficult, we can at least be confident that no one will ever be able to prove that some specific conflict situation cannot be described by any sufficient complicated Bayesian game.

References

Aumann (1976) "Agreeing to Disagree" Annals of Statistics, 4
Harsanyi (1967-68) "Games with Incomplete Information Played by 'Bayesian' Players" Management Science, 14
Mertens and Zamir (1985) "Formulation of Bayesian Analysis for Games with Incomplete Information" IJGT, 14

2010-08-07

Quantum game theory

My friends working at University of Tokyo recently published an article about quantum game theory on Journal of Physics.
Yohei Sekiguchi, Kiri Sakahara, and Takashi Sato (2010), "Uniqueness of Nash equilibria in a quantum Cournot duopoly game," Journal of Physics A: Mathematical and Theoretical, Volume 43, Number 14
Here is a link to the article. Congratulations!

Unfortunately, I don't know anything about quantum game theory. According to wikipedia (link), it is explained as follows:
Quantum game theory is an extension of classical game theory to the quantum domain. It differs from classical game theory in three primary ways:
  1. Superposed initial states,
  2. Quantum entanglement of initial states,
  3. Superposition of strategies to be used on the initial states.
Anyways, it is surprising that game theorists publish their papers on physics journals. Hum, quantum game theory might be worth trying to study...


During the conference in Brazil (link), I had a chance to attend one of the presentations by physicists, whose topic is not about quantum game theory though:

"Distinguishing the Opponents: Mutual Cooperation is Never Destroyed"
by Lucas Lages Wardil (Universidade Federal de Minas Gerais)
The paper investigates the evolution in network structures. Unlike previous works, he considers that each agent can take a contingent action, i.e., strategy, rather than a unconditional action which has been commonly assumed in the literature. That is, depending on whom to play with, each agent will take different actions; with a certain updating process each agent changes her (contingent) action against a specific opponent. In this framework with extended agents' types, he shows that cooperation (in prisoner's dilemma) becomes easy to sustain under certain networks and imitation dynamics.

In evolutionary biology, where this kind of research is widely investigated, it is unrealistic to regard contingent actions as a agents' type, because a type is considered to be genetic. In Economics, we usually examine contingent action plans in rational frameworks but it is uncommon in bounded rational frameworks such as evolutionary game. The reason (I guess) is that it is difficult to argue why and how an agent with such a complicated action plan follows a irrational/heuristic adjustment process to update her behaviors.

Anyways, I found this paper by a physicist very interesting. In some sense, his research connects biology and economics (although further justification/interpretation seems to be necessary to apply his models in these fields). There might be many things that we economists can learn from physicists.

2010-08-02

Reny's new exsistence theorem

In the plenary session on the third day of BWGT conference (link), Professor Philip Reny talked about his new research on monotone pure strategy equilibria:
Title: On the Existence of Monotone Pure Strategy Equilibria in Bayesian Games (link to pdf)
Abstract: We generalize Athey's (2001) and McAdams' (2003) results on the existence of monotone pure strategy equilibria in Bayesian games. We allow action spaces to be compact locally-complete metrizable semilattices and type spaces to be partially ordered probability spaces. Our proof is based upon contractibility rather than convexity of best reply sets. Several examples illustrate the scope of the result, including new applications to multi-unit auctions with risk-averse bidders.
According to Prof. Reny, while the topic of the paper is related to many fields such as mathematical economics, mechanism design, and auctions, there are two seminal papers that strongly motivated his research. Athey (2001) first establishes the sufficient conditions to guarantee the existence of monotone pure strategy equilibria in Bayesian games with one-dimensional and totally ordered type and action spaces. The key condition is a Spence-Mirlees single-crossing property. McAdams (2003) extends Athey's analysis to multi-dimensional and partially ordered spaces.

Prof. Reny succeeded to derive weaker conditions than McAdams in Bayesian games with multi-dimensional strategy spaces, and also extend to the infinite type and action spaces. The key insight is to use a fixed point theorem derived by Eilenberg and Montgomery (1946) instead of Kakutani's (used by Athey) or Glicksberg's (used by McAdams) ones. The latter two theorems require best reply sets to be convex while the former requires only contractibility, which turns out to be (almost) automatically satisfied in Bayesian games.
His main result says the following:
Theorem: (Under some conditions) If, whenever the other players employ monotone pure strategies, each player's set  of monotone pure-strategy best replies is nonempty and join-closed, then a monotone pure strategy equilibrium exists.
Note that a subset of strategies is join-closed if the pointwise supremum of any pair of strategies in the set is also in the set.

The idea of join-closedness (in the different context, though) recently showed up when I discussed my jointwork on the structure of stable matchings with co-authors. It may have some connection...

References
Susan Athey (2001), "Single Crossing Properties and the Existence of Pure Strategy Equilibria in Games of Incomplete Information,"  Econometrica, Vol. 69: 861-889.
Samuel Eilenberg and Deane Montgomery (1946), "Fixed Point Theorems for Multi-Valued Transformations," American Journal of Mathematics, Vol. 68: 214-222.
David McAdams (2003), "Isotone Equilibrium in Games of Incomplete Information," Econometrica, Vol. 71:1191-1214.