I found a very interesting, entertaining, and informative movie.
You can learn Japan's history just in 9 minutes!
Please check this out!!
P.S.
I have changed the title of this blog. Those who are familiar with economics books may guess where it comes from.
2016-02-04
2015-11-10
SlideShare
I've uploaded lecture slides at SlideShare. They are written in English or Japanese. The below are the titles (+ links) of the slides that are written in English. It would be great if you could take a look!
2015-05-02
Kandori and Matsushima (1998)
Original article (link) posted: 12/12/2005
The following is a short version of An essay on Kandori and Matsushima (1998) "Private Observation, Communication and Collusion" (Econometrica, 66), the term paper of the class by Professor Dutta.
Summary
The present paper analyzes the role of communication and the possibility of cooperation in a long term relationship, when the actions of the players are imperfectly observed and each player receives only private signal.
The analysis of such a situation, a repeated game with (imperfect) private monitoring, is known to be a hard problem in game theory due to its fairly complex mathematical structure, particularly due to the lack of common information shared by players. Under private monitoring, the distribution of the private histories is no longer common knowledge after a deviation (off the equilibrium path), because only the deviator takes her deviation into account for up-dating her belief while other players cannot. This means the continuation play off the equilibrium path is not even an equilibrium of the original game. Therefore, the recursive structure found in the public monitoring case, i.e., the property that the continuation payoff after any history is chosen from the identical set of equilibrium payoffs, is destroyed under private monitoring (hence, we cannot apply dynamic programming techniques provided by Abreu, Pearce and Stacchetti (1990)).
Indeed, in sharp contrast to the well-explored case of repeated games under public information (with the celebrated Folk Theorems by Fudenberg, Levine and Maskin (1994)), little had been known about the private monitoring case until recently. This is unfortunate because this class of games admits a wide range of applications such as collusion under secret price-cutting, exchange of goods with uncertain quality, and observation errors.
In this paper, the authors introduce communication in the model with private monitoring to overcome the basic difficulty of this subject. Namely, they assume that at the end of each period players can communicate what they privately observed. The announced messages generate publicly observable history, and the players can play different equilibria depending on the history of communication. Facilitating communication as a coordination device, the authors construct equilibria in which players reveal their private information truthfully, and show that the folk theorem obtains under a set of mild assumptions.
Finally, it should be noticed that their results provide a theoretical support for the conventional wisdom that communication plays an important role in sustaining collusion.
Introducing Communication
To overcome the difficulties associated with private monitoring, the authors introduce communication which generates publicly observable history, and enables players to play different equilibria depending on the history of communication. Thanks to this communication, the recursive structure is recovered, and one can apply the results in previous literature, e.g., the characterization of equilibrium payoff sets provided by Abreu, Pearce and Stacchetti (1990) and Fudenberg and Levine (1994), or Folk Theorems given by Fudenberg, Levine and Maskin (1994).
Main Result
Folk theorem can obtain given Condition 1-3 listed below.
Condition 1
If player j has a perfectly undetectable deviation at the minimax point for player i, j has no incentive to take it.
Condition 2
If either player i or j (but not both) deviates with certain probabilities from a pure action profile wich generales an extremal point, the other players can statistically detect it.
Condition 3
The players other than i and j can statistically discriminate player i's (possibly mixed) deviations from player j's at any pure action profile wich generales an extremal point.
Remark 1
These conditions guarantee that every Pareto-efficient profile and each minimax strategy profile are enforceable, which is sufficient to establish the following Folk Theorem. Roughly speaking, Condition 2 and 3 correspond to the pair-wise identifiability condition and Condition 1 is replaced with the individually full-rank condition in Fudenberg, Levine and Maskin (1994). The former is sufficient for Nash-threat version of the Folk Theorem, while the latter, in addition to the former, is sufficient for minimax version of the Folk Theorem.
Folk Theorem
Suppose that there are more than two players (n>2) and the information structure satisfies Condition 1-3. Also suppose that the dimension of V is equal to the number of players. Then, any interior point in the set of feasible and individually rational payoffs can be achieved as a sequential equilibrium average payoff profile of the repeated game with communication, if the discount factor is close enough to 1.
Basic Idea
In their communication model, one must induce each player to reveal her signal truthfully. To do so, they consider the equilibria in which each player's future payoff is independent of what she communicates. If this is the case, she is just indifferent as to what she says, and truthful revelation becomes a (weak) best response.
As one might expect, this can be done if there are at least three players and the information structure can distinguish different players' deviations. A player's private information can be used to determine when and how to transfer payoffs among other players. (In two player case, this transfer is no longer available and hence the punishment of the other player necessarily invites welfare loss.)
Remark 2
Roughly speaking, efficiency under publicly observable signals can be achieved if players can be punished by "transfers". If the information structure allows us to tell which player is suspect, we can transfer the suspect player's future payoff to the other players. This can provide the right incentives without causing welfare loss, compared to the case where all players are punished simultaneously.
Remark 3
The authors also examine the possibility of providing strict incentives to tell the truth. It is shown that when private signals are correlated, there is a way to check if each player is telling the truth and we can construct the equilibria in which the players have strict incentives for truth telling.
Remark 4
If there are two players, or if the information structure fails to distinguish different players' deviations, the above idea cannot be utilized. However, even in such cases, the Folk Theorem can be obtained by infrequent communication. This is based on the idea of Abreu, Milgrom and Pearce (1991) that delaying the release of information helps to achieve efficiency.
Remark 5
To analyze the equilibria, they employ the method developed by Fudenberg and Levine (1994). Instead of directly solving the repeated game, this method first considers simple contract problems associated with the stage game. Then, the solutions to those contract problems are utilized to construct the set of equilibrium payoffs of the repeated game.
Conclusion
As I explained in Summary, the characterization of equilibria in repeated games with private monitoring have been an open question, because the games lack recursive structure and are hard to analyze. The present paper shows that communication is an important means to resolve possible confusion among players in the course of collusion during repeated play. Namely, as they introduce communication to generate publicly observable history, the authors recover the recursive structure and show a Folk Theorem.
However, it should be noticed that they did not show the necessity of communication for a Folk Theorem. In principle, there is a possibility that a Folk Theorem holds even without communication. Indeed, the analyses of private monitoring have been rapidly developed (not yet achieve the complete characterization of equilibrium, though) since Kandori and Matushima (1998). Therefore, I would like to mention the recent literature on repeated games with private monitoring, which concludes this essay (I relied on the excellent survey by Kandori (2002) for the remain part).
Recent Literature
Sekiguchi (1997) is the first paper to construct an equilibrium which is apart from the repetition of the stage game equilibrium under private monitoring. He shows that efficiency can be approximately achieved (without communication) in the prisoner's dilemma model, if the information is almost perfect.
Bhaskar and Obara (2002) extend Sekiguchi's construction to support any point Pareto dominating (d,d) (in the prisoner's dilemma), when monitoring is private but almost perfect. Sekiguchi-Bhaskar-Obara type of equilibrium is called "belief-based" equilibrium because they facilitate the coordinated punishment idea.
Piccione (2002) and Ely and Valimaki (2002) introduce a completely different, useful technique to support essentially the same area under almost perfect monitoring. In contrast to "belief-based" equilibrium by S-B-O, their equilibrium utilizes the uncoordinated punishment idea, and hence is named "belief-free" equilibrium.
Matsushima (2004) extends Ely and Valimaki's construction and show that their Folk Theorem continues to hold even if monitoring is far from perfect, as long as private signals are distributed independently.
Ely, Horner and Olszewski (2005) give the most general results in two-player repeated games with private monitoring. Using "belief-free" strategies, they provide a simple and sharp characterization of equilibrium payoffs. While such strategies support a large set of payoffs, they are not rich enough to generate a Folk Theorem in most games besides the prisoner's dilemma, even when information is almost perfect.
References
Abreu, Milgrom and Pearce (1991) "Information and timing in repeated partnerships" Econometrica, 59
Abreu, Pearce and Stacchetti (1990) "Toward a Theory of Discounted Repeated Games with Imperfect Monitoring" Econometrica, 58
Bhaskar and Obara (2002) "Belif-based Equilibria in the Repeated Prisoners' Dilemma with Private Monitoring" Journal of Economic Theory, 102
Ely, Horner and Olszewski (2005) "Belief-free Equilibria in Repeated Games" Econometrica, 73
Ely and Valimaki (2002) "A Robust Folk Theorem for the Prisoner's Dilemma" Journal of Economic Theory, 102
Fudenberg and Levine (1994) "Efficiency and Observability with Long-Run and Short-run Players" Journal of Economic Theory, 62
Fudenberg, Levine and Maskin (1994) "The folk theorem with imperfect public information" Econometrica, 62
Kandori (2002) "Introduction to Repeated Games with Private Monitoring" Journal of Economic Theory, 102
Matsushima (2004) "Repeated Games with Private Monitoring: Two Players" Econometrica, 72
Piccione (2002) "The Repeated Prisoner's Dilemma with Imperfect Private Monitoring" Journal of Economic Theory, 102
Sekiguchi (1997) "Efficiency in the Prisoner's Dilemma with Private Monitoring" Journal of Economic Theory, 76
The following is a short version of An essay on Kandori and Matsushima (1998) "Private Observation, Communication and Collusion" (Econometrica, 66), the term paper of the class by Professor Dutta.
Summary
The present paper analyzes the role of communication and the possibility of cooperation in a long term relationship, when the actions of the players are imperfectly observed and each player receives only private signal.
The analysis of such a situation, a repeated game with (imperfect) private monitoring, is known to be a hard problem in game theory due to its fairly complex mathematical structure, particularly due to the lack of common information shared by players. Under private monitoring, the distribution of the private histories is no longer common knowledge after a deviation (off the equilibrium path), because only the deviator takes her deviation into account for up-dating her belief while other players cannot. This means the continuation play off the equilibrium path is not even an equilibrium of the original game. Therefore, the recursive structure found in the public monitoring case, i.e., the property that the continuation payoff after any history is chosen from the identical set of equilibrium payoffs, is destroyed under private monitoring (hence, we cannot apply dynamic programming techniques provided by Abreu, Pearce and Stacchetti (1990)).
Indeed, in sharp contrast to the well-explored case of repeated games under public information (with the celebrated Folk Theorems by Fudenberg, Levine and Maskin (1994)), little had been known about the private monitoring case until recently. This is unfortunate because this class of games admits a wide range of applications such as collusion under secret price-cutting, exchange of goods with uncertain quality, and observation errors.
In this paper, the authors introduce communication in the model with private monitoring to overcome the basic difficulty of this subject. Namely, they assume that at the end of each period players can communicate what they privately observed. The announced messages generate publicly observable history, and the players can play different equilibria depending on the history of communication. Facilitating communication as a coordination device, the authors construct equilibria in which players reveal their private information truthfully, and show that the folk theorem obtains under a set of mild assumptions.
Finally, it should be noticed that their results provide a theoretical support for the conventional wisdom that communication plays an important role in sustaining collusion.
Introducing Communication
To overcome the difficulties associated with private monitoring, the authors introduce communication which generates publicly observable history, and enables players to play different equilibria depending on the history of communication. Thanks to this communication, the recursive structure is recovered, and one can apply the results in previous literature, e.g., the characterization of equilibrium payoff sets provided by Abreu, Pearce and Stacchetti (1990) and Fudenberg and Levine (1994), or Folk Theorems given by Fudenberg, Levine and Maskin (1994).
Main Result
Folk theorem can obtain given Condition 1-3 listed below.
Condition 1
If player j has a perfectly undetectable deviation at the minimax point for player i, j has no incentive to take it.
Condition 2
If either player i or j (but not both) deviates with certain probabilities from a pure action profile wich generales an extremal point, the other players can statistically detect it.
Condition 3
The players other than i and j can statistically discriminate player i's (possibly mixed) deviations from player j's at any pure action profile wich generales an extremal point.
Remark 1
These conditions guarantee that every Pareto-efficient profile and each minimax strategy profile are enforceable, which is sufficient to establish the following Folk Theorem. Roughly speaking, Condition 2 and 3 correspond to the pair-wise identifiability condition and Condition 1 is replaced with the individually full-rank condition in Fudenberg, Levine and Maskin (1994). The former is sufficient for Nash-threat version of the Folk Theorem, while the latter, in addition to the former, is sufficient for minimax version of the Folk Theorem.
Folk Theorem
Suppose that there are more than two players (n>2) and the information structure satisfies Condition 1-3. Also suppose that the dimension of V is equal to the number of players. Then, any interior point in the set of feasible and individually rational payoffs can be achieved as a sequential equilibrium average payoff profile of the repeated game with communication, if the discount factor is close enough to 1.
Basic Idea
In their communication model, one must induce each player to reveal her signal truthfully. To do so, they consider the equilibria in which each player's future payoff is independent of what she communicates. If this is the case, she is just indifferent as to what she says, and truthful revelation becomes a (weak) best response.
As one might expect, this can be done if there are at least three players and the information structure can distinguish different players' deviations. A player's private information can be used to determine when and how to transfer payoffs among other players. (In two player case, this transfer is no longer available and hence the punishment of the other player necessarily invites welfare loss.)
Remark 2
Roughly speaking, efficiency under publicly observable signals can be achieved if players can be punished by "transfers". If the information structure allows us to tell which player is suspect, we can transfer the suspect player's future payoff to the other players. This can provide the right incentives without causing welfare loss, compared to the case where all players are punished simultaneously.
Remark 3
The authors also examine the possibility of providing strict incentives to tell the truth. It is shown that when private signals are correlated, there is a way to check if each player is telling the truth and we can construct the equilibria in which the players have strict incentives for truth telling.
Remark 4
If there are two players, or if the information structure fails to distinguish different players' deviations, the above idea cannot be utilized. However, even in such cases, the Folk Theorem can be obtained by infrequent communication. This is based on the idea of Abreu, Milgrom and Pearce (1991) that delaying the release of information helps to achieve efficiency.
Remark 5
To analyze the equilibria, they employ the method developed by Fudenberg and Levine (1994). Instead of directly solving the repeated game, this method first considers simple contract problems associated with the stage game. Then, the solutions to those contract problems are utilized to construct the set of equilibrium payoffs of the repeated game.
Conclusion
As I explained in Summary, the characterization of equilibria in repeated games with private monitoring have been an open question, because the games lack recursive structure and are hard to analyze. The present paper shows that communication is an important means to resolve possible confusion among players in the course of collusion during repeated play. Namely, as they introduce communication to generate publicly observable history, the authors recover the recursive structure and show a Folk Theorem.
However, it should be noticed that they did not show the necessity of communication for a Folk Theorem. In principle, there is a possibility that a Folk Theorem holds even without communication. Indeed, the analyses of private monitoring have been rapidly developed (not yet achieve the complete characterization of equilibrium, though) since Kandori and Matushima (1998). Therefore, I would like to mention the recent literature on repeated games with private monitoring, which concludes this essay (I relied on the excellent survey by Kandori (2002) for the remain part).
Recent Literature
Sekiguchi (1997) is the first paper to construct an equilibrium which is apart from the repetition of the stage game equilibrium under private monitoring. He shows that efficiency can be approximately achieved (without communication) in the prisoner's dilemma model, if the information is almost perfect.
Bhaskar and Obara (2002) extend Sekiguchi's construction to support any point Pareto dominating (d,d) (in the prisoner's dilemma), when monitoring is private but almost perfect. Sekiguchi-Bhaskar-Obara type of equilibrium is called "belief-based" equilibrium because they facilitate the coordinated punishment idea.
Piccione (2002) and Ely and Valimaki (2002) introduce a completely different, useful technique to support essentially the same area under almost perfect monitoring. In contrast to "belief-based" equilibrium by S-B-O, their equilibrium utilizes the uncoordinated punishment idea, and hence is named "belief-free" equilibrium.
Matsushima (2004) extends Ely and Valimaki's construction and show that their Folk Theorem continues to hold even if monitoring is far from perfect, as long as private signals are distributed independently.
Ely, Horner and Olszewski (2005) give the most general results in two-player repeated games with private monitoring. Using "belief-free" strategies, they provide a simple and sharp characterization of equilibrium payoffs. While such strategies support a large set of payoffs, they are not rich enough to generate a Folk Theorem in most games besides the prisoner's dilemma, even when information is almost perfect.
References
Abreu, Milgrom and Pearce (1991) "Information and timing in repeated partnerships" Econometrica, 59
Abreu, Pearce and Stacchetti (1990) "Toward a Theory of Discounted Repeated Games with Imperfect Monitoring" Econometrica, 58
Bhaskar and Obara (2002) "Belif-based Equilibria in the Repeated Prisoners' Dilemma with Private Monitoring" Journal of Economic Theory, 102
Ely, Horner and Olszewski (2005) "Belief-free Equilibria in Repeated Games" Econometrica, 73
Ely and Valimaki (2002) "A Robust Folk Theorem for the Prisoner's Dilemma" Journal of Economic Theory, 102
Fudenberg and Levine (1994) "Efficiency and Observability with Long-Run and Short-run Players" Journal of Economic Theory, 62
Fudenberg, Levine and Maskin (1994) "The folk theorem with imperfect public information" Econometrica, 62
Kandori (2002) "Introduction to Repeated Games with Private Monitoring" Journal of Economic Theory, 102
Matsushima (2004) "Repeated Games with Private Monitoring: Two Players" Econometrica, 72
Piccione (2002) "The Repeated Prisoner's Dilemma with Imperfect Private Monitoring" Journal of Economic Theory, 102
Sekiguchi (1997) "Efficiency in the Prisoner's Dilemma with Private Monitoring" Journal of Economic Theory, 76
2015-02-03
New Papers
My new paper, "Exit Option Can Make Cooperation Easier" (joint with Takako Fujiwara-Greve) is uploaded at SSRN. The manuscript is very short (only 7 pages!). Please take a look if you are interested in how introducing exit option would affect cooperative incentives.
A completely different paper on matching, "Expanding "Choice" in School Choice" (joint with Atila Abdulkadiroğlu, Yeon-Koo Che) was finally published in the American Economic Journal: Microeconomics. (as a lead article!) Our earlier paper, "Resolving Conflicting Preferences in School Choice: The "Boston Mechanism" Reconsidered", appeared in the American Economic Review, was originally a part of this AEJ paper. Both are theoretical works but contains important policy implications on public school choice. It would be very nice if you could read (and hopefully cite) the articles :)
A completely different paper on matching, "Expanding "Choice" in School Choice" (joint with Atila Abdulkadiroğlu, Yeon-Koo Che) was finally published in the American Economic Journal: Microeconomics. (as a lead article!) Our earlier paper, "Resolving Conflicting Preferences in School Choice: The "Boston Mechanism" Reconsidered", appeared in the American Economic Review, was originally a part of this AEJ paper. Both are theoretical works but contains important policy implications on public school choice. It would be very nice if you could read (and hopefully cite) the articles :)
2014-08-17
Are Economists Japan's New Exports?
I created a list of Japanese economists who currently work at universities outside of Japan: Link.
Although the list is still incomplete (it may never be complete), the number of economists has already reached 100! This is far beyond my expectation!! And so, making the list has taken much longer time than I expected...
As you might know, getting an academic job at a good research university is very difficult, even if you have a Ph.D. from a top school. The list shows that Japanese economists, especially among the young generation (those graduated their colleges in the late 90's or later), are highly competitive. In recent years, it is not uncommon for Japanese junior economists to get international academic jobs posted in the JOE.
I wish my list help visualizing the great success of overseas Japanese economists, and stimulate domestic Japanese economists as well. By the way, a list of Japanese economists who work at domestic universities (with reasonably good research outputs) is now in preparation. Don't miss it!
Although the list is still incomplete (it may never be complete), the number of economists has already reached 100! This is far beyond my expectation!! And so, making the list has taken much longer time than I expected...
As you might know, getting an academic job at a good research university is very difficult, even if you have a Ph.D. from a top school. The list shows that Japanese economists, especially among the young generation (those graduated their colleges in the late 90's or later), are highly competitive. In recent years, it is not uncommon for Japanese junior economists to get international academic jobs posted in the JOE.
I wish my list help visualizing the great success of overseas Japanese economists, and stimulate domestic Japanese economists as well. By the way, a list of Japanese economists who work at domestic universities (with reasonably good research outputs) is now in preparation. Don't miss it!
2014-06-11
Samurai in Brazil
Another cool TV commercial was made by CUPNOODLE. The Samurai in the movie is Kotaro TOKUDA, the world champion of the freestyle football!
2014-06-09
Special CM featuring #10
A special TV commercial made by KIRIN BEER was broadcasted only on May 31, the last day of National Stadium (国立競技場). This CM features a Japanese football player Shinji Kagawa, the number 10 of our national team, whom I believe makes a big surprise in the FIFA world cup :) Go Shinji! Go Japan!!
2014-05-20
Athey et al. (2005)
Original article (link) posted: 07/11/2005
Athey, Atkeson and Kehoe (2005) "The Optimal Degree of Discretion in Monetary Policy" Econometrica
The paper examines a monetary policy game in which the monetary authority has private information about the state of the economy. In the literature, two seminal papers, Taylor (1983) and Canzoneri (1985), established no discretion should be left to the monetary authority if there is no such private information; the best outcomes can be achieved by rules that specify the action of the monetary authority as a function of observables. The introduction of private information creates a tension between discretion and time inconsistency. Tight constraints on discretion mitigate the time inconsistency problem in which the monetary authority is tempted to claim repeatedly that the current state of the economy justifies a monetary stimulus to output. However, tight constraints leave little room for the monetary authority to time-tune its policy to its private information. In short, loose constraints allow the monetary authority to do that fine tuning, but they also allow more room for the monetary authority to stimulate the economy with surprise inflation.
Making use of dynamic mechanism design techniques, they find that the optimal mechanism is quite simple; for a broad class of economics, the optimal mechanism is static (policies depend only on the current report by the monetary authority) and can be implemented by setting an inflation cap, an upper limit on the permitted inflation rate. It is also shown that the optimal degree of monetary policy discretion turns out to shrink as the severity of the time inconsistency problem increases relative to the importance of private information.
Comment
The results they derive seem to be very interesting. In particular, the “inflation cap” result is directly related to the optimal inflation targets and has strong importance with actual monetary policies. As they mention, their work provides one theoretical rationale for the type of constrained discretion advocated by Bernanke and Mishkin (1997). This paper might become a must-read paper for those who work in monetary policies.
References
Bernanke and Mishkin (1997) "Inflation Targeting: A New Framework for Monetary Policy?" J. of Econ, Perspectives, 11
Canzoneri (1985) "Monetary Policy Games and the Role of Private Information" AER, 75
Taylor (1983) "Rules, Discretion, and Reputation in a Model of Monetary Policy: Comments" JME, 12
Athey, Atkeson and Kehoe (2005) "The Optimal Degree of Discretion in Monetary Policy" Econometrica
The paper examines a monetary policy game in which the monetary authority has private information about the state of the economy. In the literature, two seminal papers, Taylor (1983) and Canzoneri (1985), established no discretion should be left to the monetary authority if there is no such private information; the best outcomes can be achieved by rules that specify the action of the monetary authority as a function of observables. The introduction of private information creates a tension between discretion and time inconsistency. Tight constraints on discretion mitigate the time inconsistency problem in which the monetary authority is tempted to claim repeatedly that the current state of the economy justifies a monetary stimulus to output. However, tight constraints leave little room for the monetary authority to time-tune its policy to its private information. In short, loose constraints allow the monetary authority to do that fine tuning, but they also allow more room for the monetary authority to stimulate the economy with surprise inflation.
Making use of dynamic mechanism design techniques, they find that the optimal mechanism is quite simple; for a broad class of economics, the optimal mechanism is static (policies depend only on the current report by the monetary authority) and can be implemented by setting an inflation cap, an upper limit on the permitted inflation rate. It is also shown that the optimal degree of monetary policy discretion turns out to shrink as the severity of the time inconsistency problem increases relative to the importance of private information.
Comment
The results they derive seem to be very interesting. In particular, the “inflation cap” result is directly related to the optimal inflation targets and has strong importance with actual monetary policies. As they mention, their work provides one theoretical rationale for the type of constrained discretion advocated by Bernanke and Mishkin (1997). This paper might become a must-read paper for those who work in monetary policies.
References
Bernanke and Mishkin (1997) "Inflation Targeting: A New Framework for Monetary Policy?" J. of Econ, Perspectives, 11
Canzoneri (1985) "Monetary Policy Games and the Role of Private Information" AER, 75
Taylor (1983) "Rules, Discretion, and Reputation in a Model of Monetary Policy: Comments" JME, 12
2014-05-05
Echenique (2003)
Echenique, F. (2003), The Equilibrium Set of a Two Player Game with Complementarities is a Sublattice, Economic Theory, 22: 903-905. Link
Summary I prove that the equilibrium set in a two-player game with complementarities, and totally ordered strategy spaces, is a sublattice of the joint strategy space.
It is widely known that in games with strategic complementarities (GSC), i.e., best reply correspondings are monotone increasing for all players, the set of pure-strategy Nash equilibria forms a non-empty complete lattice. This result implies the existence of smallest and largest Nash equilibria.
The current paper looks further into the structure of the equilibrium set of GSC, and shows that under certain restrictions the equilibrium set becomes not just a complete lattice but also a sublattice, as is written down in the Summary above.
The practical importance of this result, according to the author, is:
If the equilibrium set of a game is a sublattice, then we can find new equilibria from knowing that two profiles are equilibria, and by taking the componentwise join and meet of players’ strategies.
Note that we cannot obtain such strong property by a complete lattice structure alone. In this sense, a sublattice is indeed critical. The proof is extremely simple, which makes use of the observation that (a) when there are only 2 players and (b) their strategy spaces are completely ordered, (c) the other player's strategy must be completely ordered. The property (c) does not hold either (a) or (b) is not satisfied. Once (c) is verified, the rest of the proof is just to follow the definition of GSC.
My random thought: A sublattice property also arises in one-to-one two-sided matching markets (but neither in one-to-many nor many-to-many markets). I'm wondering if the idea of this paper can be somehow connected to the sublattice property of the set of stable matchings.
A final remark: A nicely written but a bit uninformative note.
2014-05-03
Sotomayor (1996)
Sotomayor, M. (1996), A non constructive elementary proof of the existence of stable marriages, Games and Economic Behavior, 13: 135–7. Link
Abstract Gale and Shapley showed in their well known paper of 1962 (Amer. Math. Monthly 69, 9–14) that stable matchings always exist for the marriage market. Their proof was constructed by means of an algorithm. Except for the existence of stable matchings, all the results for the marriage market which were proved by making use of the Gale and Shapley algorithm could also be proved without the algorithm. The purpose of this note is to fill out this case. We present here a nonconstructive proof of the existence of a stable matching for the marriage market, which is quite short and simple and applies directly to both cases of preferences: strict and nonstrict.
In this short note, the author establishes the existence of stable matchings for the marriage market, i.e., one-to-one matching market, without employing any algorithms. Her key idea is a new concept that she calls a simple matching, which is defined as follows:
A matching is simple if, in the case a blocking pair (m, w) exists, w is single.
Since the set of simple matchings is nonempty and finite, there must exist a specific matching that I call here (for notational convenience) an M-simple matching:
A simple matching is M-simple if it cannot be (weakly) Pareto dominated for men by any other simple matching.
Then, she shows that such M-simple matching is stable. The basic logic is that the existence of blocking pair necessarily induces Pareto improvement for men (since w is single), which contradicts to the Pareto efficiency of M-simple matching for men.
As the author claims, the proof is very shout and simple, yet quite novel I think. To explain her proof strategy in a different way, she
- focuses on the subset of stable matchings,
- characterize it by "M-simple matching," and
- shows that the set is non-empty.
It is immediate that M-simple matching is unique and coincides with M-optimal stable matching when all the preferences are strict. In this way, we can see that her idea is somewhat related to the existence of one-sided optimal stable matchings, a widely known result in the literature.
A minor remark: The definition of matching in the paper incorporates individual rationality, and consequently that of of stable matchings pays attention only on blocking pairs. This looks a bit non-standard while nothing is lost in her analysis.
A final remark: I like this paper very much :)
Subscribe to:
Posts (Atom)