2010-05-28

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

4 comments:

yuichiro said...

Hi, I'm very happy to hear that the paper interested you.
Thanks for your comments.

I actually think that a spciefication of the target caps does matter. For example, suppose that there are one region r with cap 1, in which two hospitals h_1 and h_2 reside. There are two doctors d_1 and d_2. For d_i (resp. h_i), h_i (resp. d_i) is the only acceptable choice.
If the targets are (1,0) then I guess the resulting match is (h_1,d_1), indeopendent of the order of hgospitals. If they are (0,1) then the resulting match would be (h_2,d_2).

For the order of hospitals, I think it does matter again. For example, add one more hospital h_3 in r in the above example, and let the target be (0,0,1). No doctor thinks that h_3 is acceptable. Everything else is unchanged from the previous example. Then, I guess if the order is h_1->h_2 then the resulting match is (h_1,d_1), but if it is h_2->h_1, the match would be (h_2,d_2).
It's true that we should be clearer about this dependence on indices.

Thanks again, and let us know whenever you come up with any other related things!

yyasuda said...

Hi, Yuichiro. I'm also very happy that you kindly left the first comments in this blog!

The two simple (counter-)examples you constructed surely answer my informal question. Thank you so much :)

Now, I am thinking about monotonicity w.r.t. (1) and (2). Can you say something like the following?

Conjecture: For each hospital, (1') increasing its target cap, or (2') raising its order (assigning earlier order) NEVER makes it strictly worse off.

If this kind of monotonicity holds (it seems to hold, isn't it?), the government may well balance fairness/equity of hospitals within each region through the operation (1') or (2') without sacrificing stability/efficiency as a whole.

I think some professional sports league does practice something similar to (2') in the centralized job-offering process, "draft": making weaker team's order earlier.
(The last comment was also mentioned by Prof. Matsui during the seminar.)

yuichiro said...

Thanks for the comments.
Yes I think your conjecture is right; Fuhito and I were actually talking about it informally but didn't include it in the talk because we haven't yet proven it formally by the time of the talk.

But I certainly agree that it's worth mentioning in the paper. As you suggested, the monotonicity of that kind would imply that there may be room for the government to do something.

yyasuda said...

Thanks again for your quick reply :) I hope my comments would help you guys. Look forward to seeing the manuscript!