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 :)

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.

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

1. focuses on the subset of stable matchings, 
2. characterize it by "M-simple matching," and
3. 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 :)

How did GS algorithm come out?

Roth, A. (2008), Deferred acceptance algorithms: history, theory, practice, and open questions, International Journal of Game Theory, 36: 537-569.

In this survey article on the Gale-Shapley's deferred acceptance algorithm, Al Roth mentions (in footnote 3) an amazing story about how GS discovered the algorithm (which of course established the theory of two-sided matchings):

At his birthday celebration in Stony Brook on 12 July 2007, David Gale related the story of his collaboration with Shapley to produce GS by saying that he (Gale) had proposed the model and definition of stability, and had sent to a number of colleagues the conjecture that a stable matching always existed. By return mail, Shapley proposed the deferred acceptance algorithm and the corresponding proof. 

Matching and Market

I found insightful comments on the relationship between matching theory and market economy (more specifically, general equilibrium) in the following paper:
Vincent Crawford (1991), "Comparative Statics in Matching Markets" Journal of Economic Theory, 54: 389-400.

Perhaps the most important advantage of the matching approach is its robustness to heterogeneity. A traditional competitive equilibrium cannot exist in general unless the goods traded in each market are homogeneous, because all goods in the same market must sell at the same price. A traditional model of a labor market with the degree of heterogeneity normally encountered therefore has the structure of a multi-market general equilibrium model. But because the markets in such a model are very thin, the usual arguments in support of price-taking are strained. The theory of matching markets replaces this collection of thin markets with a single market game, in which the terms of partnerships are determined endogenously, along with the matching, via negotiations between prospective partners. Gale and Shapley's notion of stability(*), suitable generalized, formalizes the idea of competition, and thereby makes it possible to evaluate the robustness of traditional competitive analysis to heterogeneity. (Stable outcomes in matching markets can in fact be viewed as traditional competitive equilibria when prices are allowed to reflect the differences between matches; see, for example, Shapley and Shubik, 1972(**))

The author, Vince Crawford, who is known as a leading researcher in game theory has written a few influential papers on matching theory. Especially, the following two are of great importance since they initiated the area of (many-to-one) matching with monetary transfers.

"Job Matching with Heterogeneous Firms and Workers"

with Elsie Marie Knoer, Econometrica, Vol. 49(2): 437-450, 1981.

"Job Matching, Coalition Formation, and Gross Substitutes"

with Alexander S. Kelso, Jr., Econometrica, Vol. 50(6): 1483-1504, 1982.

* Gale and Shapley (1962) "College Admissions and the Stability of Marriage" American Mathematics Monthly, 69: 9-15.

** Shapley and Shubik (1972) "The Assignment Game. 1. The Core" International Journal of Game Theory, 1: 111-130.

Kandori (RES 1992)

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

Kandori (1992) "Social Norms and Community Enforcement" RES, 59

The paper considers self-enforcing mechanisms in the situation where agents change their partners over time. Technically, the model in the paper is an extension of the theory of repeated games to the case of matching games. As main results, the following two are shown.

1) Community can sustain cooperation even when each agent knows nothing more than his personal experience.
2) Community can realize any mutually beneficial outcomes when each agent carries a label which is revised in a systematic way. That is, Folk Theorem holds.

As a motivation of the research, he mentions the benefit of specialization. After introducing theoretical achievements in personal enforcement mechanisms, i.e. Folk Theorem in the repeated game literature, he says as follows.

However, many important transactions are infrequent in nature. As economic historians argue, the division of labor and specialization are important driving forces of economic progress. Potential gains are larger in diverse transactions with different specialists than with fixed partners. Therefore, the control of incentives in such an infrequent trade is of vital importance to understand the organization of economic transactions.

He refers to two papers which initiated this line of research.

The attempt to generalize the Folk Theorem of repeated games to the case of matching games was initiated by Milgrom, North and Weingast (1990) and Okuno-Fujiwara and Postlewaite (1989). The former analyzed concrete examples of information transmission mechanisms and the latter introduced the notion of local information processing. Both of them, however, mainly deal with the infinite population case to avoid potentially complicated problems of incentives on off-equilibrium paths. Our paper shows that such problems can be resolved in a simple way if the stage game satisfies weak condition. Equilibria constructed in our paper work for any population size and any matching rule, and are robust to changes in information structures.

What a strong result he derived!! Although he does not stress the results given in Section 3 "Folk Theorem under Public Observability", I think Proposition 2 is very interesting. It is easy to understand that Folk Theorem holds if all the other players get into punishment phase after some player deviates, which is stated as Proposition 1. However, if we restrict our attention to such a situation where only the deviator is to be punished and innocent pairs are to play the originally prescribed actions, to show Folk Theorem is not straight forward. To be more precise, to check the incentives for innocent players in off-equilibrium path where community is highly populated with "guilty" agents is involved.
Introducing some "forgiveness" in the social norm, the author elegantly shows this problem can be avoided which leads to Proposition 2.

Interesting Papers in References

Harrington (1989) "Cooperation in Social Settings" mimeo
Section 7 of the above paper was revised and available as the following.
Harrington (1995) "Cooperation in a One-Shot Prisoners' Dilemma" GEB, 8
Milgrom, North and Weingast (1990) "The Role of Institutions in the Revival of Trade: The Law Merchant, Private Judges, and the Champagne Fairs" Economic Inquiry, 25
Okuno-Fujiwara and Polstlewaite (1995) "Social Norms in Random Matching Game" GEB, 9
Rubinstein and Wolinsky (1990) "Decentralized Trading, Strategic Behavior and the Walrasian Outcome" RES, 57

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.

Regional Caps on JRMP

I attended a lunch seminar on microeconomics at University of Tokyo today (May 27th); Fuhito Kojima, one of the most productive game theorists in my ages, talked about his recent matching paper with Yuichiro Kamada (a rising star at Harvard):
"Improving Efficiency in Matching Markets with Regional Caps: The Case of the Japan Residency Matching Program" (joint with Yuichiro Kamada)

Their work is strongly motivated by the actual centralized matching system used in the Japan residency matching program (JRMP). JRMP, as it follows NRMP in the U.S., employs the Gale-Shapley algorithm to assign doctors to hospitals. However, due to the vacancy problem at (mainly) rural hospitals, JRMP recently introduced "regional caps" to each prefecture in order to control the numbers of doctors in popular area.

The current paper theoretically investigates the effects of imposing such an exogenous caps to the GS algorithm. Based on the new stability concept they define, which incorporates regional cap constraints in a natural way and coincides with the usual stability if there were no caps, they show the followings:

1. The current Japanese mechanism, i.e., exogenous regional caps + GS, is not a stable matching mechanism.
2. There exists a new algorithm (natural extension of the GS) that always a stable and constrained efficient matching.
3. This new mechanism is group strategy-proof for doctors, that is, any group of doctors does not have an incentive to manipulate their preferences.

Here is a technical remark. To define new algorithm, we have to decide two things (which are absent from the usual GS algorithm), (1) target caps and (2) an order of hospitals. As I remember correctly, the resulting outcome is independent of the choice of (1) (whenever target caps satisfy weak feasibility conditions), but the speaker didn't mention whether the outcome is also invariant to (2) or not. I may better ask him later...

I found the paper really interesting: motivation is clear, results look nice, contains important policy implication, can be applied to different matching problems, and so on. It might be desirable if they could provide some policy recommendation with respect to the choice of regional caps. Although actual caps are typically determined by politics or something other than economic theory I suppose, some benchmark analysis should be helpful. Anyways, I like this paper very much :) (We may perhaps find its title on the front page of some top journal in the near future!)