دستکاری هزینه تقاضا در تطبیق بازارها

In some well-known hospital–intern type of matching markets, hospitals impose mandatory application fees on internship applicants to consider their applications. Motivated by this real-life phenomenon, we study the application fee overreporting incentives of hospitals in centralized matching markets by assuming that interns have finite budgets to spend on such fees. Our main theorem shows that no stable mechanism is immune to application fee manipulations. Interestingly, under any stable rule, hospitals might not only obtain better matchings but also increase their application fee revenues through overreporting their application fees. In the restricted domains in which either side has homogeneous preferences or each hospital has only one available position, every stable mechanism turns out to be immune to application fee overreportings.

In some well-known hospital–intern type of matching markets, hospitals impose mandatory application fees on internship applicants to consider their applications. The Veterinary Internship and Residency Matching Program (VIRMP),1 and The Dietetic Internship Matching Program2 (hereafter, DIMP) are two examples of such centralized markets in the United States. Hospitals are matched with veterinarians and dietetic interns through these programs, respectively. Motivated by this real-life phenomenon, this paper examines the application fee manipulation incentives of hospitals in centralized matching markets. In a matching problem, there are two finite and disjoint sets of hospitals and interns. Each intern has a preference relation over the set of hospitals and being unemployed, and each hospital has a preference relation over the set of groups of interns along with a capacity limiting the maximum number of interns it can employ. A matching is an assignment of interns to hospitals such that no hospital employs more interns than its capacity, and no intern is assigned more than one hospital. A matching is individually rational if no intern prefers being unemployed to his assignment, and no hospital prefers keeping a seat vacant to one of its assigned interns. An unmatched hospital–intern pair blocks a matching if the intern prefers the hospital to his assignment, and the hospital prefers the intern to any one in its assignment or keeping a seat vacant (if it has). A matching is stable if it is individually rational and is not blocked by a hospital–intern pair. Besides the theoretical appeal of stability, it has been central to the practical market design. In many widely-known matching markets, the previously used unstable mechanisms have been replaced with stable ones.3 For instance, Roth (1984) shows that the National Resident Matching Program (NRMP) has been using a stable mechanism since 1950 to match medical doctors and hospitals in the United States. Fortunately, Gale and Shapley (1962) show that the existence of a stable solution is not specific to NRMP, but it is true for any two-sided matching market and introduce an algorithm for finding one. This positive existence result, however, has not solved all the problems of matching market design, especially regarding the strategic ones. It is well known that no stable mechanism is immune to the preference manipulations (Roth, 1982). As well as preference misreporting, Sönmez, 1997 and Sönmez, 1999 prove that there exists no stable mechanism which is non-manipulable via capacities and pre-arrangements, respectively. In some real-life matching markets, hospitals charge an application fee to consider internship applications. As we pointed out before, VIRMP and DIMP are two well known examples. Moreover, it is known that application fees vary a lot across the hospitals in real life. If we believe that the monetary equivalent of the marginal cost of assessing an application to hospitals should not differ across them as much as prevailing application fees do, then an interesting economic question turns out to be how can we explain the application fee differences in real-life matching markets? Naturally, one can immediately argue that hospitals might announce application fees which are higher than their respective constant marginal costs of assessing an application in order to increase their revenues. While it can be a natural reasoning, in the current paper, we take a different view and approach it from the manipulation point of view in centralized matching markets where hospitals do only care about their assignments. How can a hospital manipulate matching mechanisms by overreporting its true application fee, which is assumed to be equal to the constant marginal cost of assessing an application to the hospital throughout the paper, to obtain better interns? We know that, in real-life matching markets, the presence of application fees brings a certain budget constraint on interns: an intern cannot finalize his application to a hospital unless he pays the application fee of it, and, in this case, he ultimately loses the chance of being matched with the hospital. Therefore, application fees play a role in outcomes through constraints they impose on interns whenever they have finite budgets to spend on such fees. This, in turn, might enable hospitals to manipulate matching mechanisms through overreporting their fees in the hope of obtaining better interns. In order to study the application fee manipulation incentives of hospitals, we employ the conventional matching market model with additional application fee and budget profiles of hospitals and interns, respectively. For the ease of analysis, it is assumed that both hospitals and interns have non-monetary preferences, in other words, they have preferences only over the opposite side of the market. However, we also informally show that our main result continues to hold under the quasi-linear payoff setting where money is the numeraire. Since we are interested in the application fee manipulation incentives, we fix the preference and capacity profiles of hospitals, and let them announce their application fees. Given a stable mechanism, each announced application fee profile induces a preference-reporting game in which every intern simultaneously submits a “feasible” preference relation, that is, a preference relation such that the total application fees of the acceptable hospitals4 according to it is less than or equal to his budget. Then, the given stable mechanism assigns a matching based on the submitted feasible preference profile of interns, and the fixed preference and capacity profiles of hospitals. In this game setting, we focus on pure Nash equilibria and say that a mechanism is manipulable via application fees if, at a problem instance, there exist a hospital and a false application fee (a higher fee than the “true” one) such that the hospital strictly prefers every pure Nash equilibrium outcome under the false application fee profile to all of those under the “true” one.5 Regarding the “true” application fee of a hospital, it is equal to the marginal cost of assessing an application to the hospital, which is assumed to be constant throughout the paper. Note that we only investigate the application fee overreporting incentives, since, in our setting, it is easy to see that hospitals can match with their preferred interns via underreporting their application fees, however, whether it is true by overreporting is a subtle question. We first show that, for any stable mechanism and announced application fee profile, there always exists a pure Nash equilibrium of the preference-reporting game. Then, our main theorem reveals that there exists no stable mechanism which is non-manipulable via application fees. Interestingly, under any stable rule, hospitals might not only obtain better assignments but also increase their application fee revenues in any equilibrium by overreporting their application fees. Lastly, we focus on some special restricted domains and show that if either side has homogeneous preferences or each hospital has only one available position, then every stable mechanism turns out to be immune to application fee overreportings. We should emphasize that the introduced game setting totally mimics the aforementioned budget constraint interns encounter in matching markets with application fees. Namely, interns cannot complete their applications to hospitals if they do not pay their application fees, and, in this case, they lose the chance of being matched with these hospitals. Given this real-world practice, since stable mechanisms do not assign interns to their unacceptable alternatives, under any feasible preference profile, they are not matched with hospitals of which the application fees are higher than their budgets. Our paper is important not only for theoretical purposes, but also for practical issues. Application fees are commonly observed in various real-life matching problems. Given the prevalence of such fees, our main theorem demonstrates that the relevant economic agents might have strong incentives to manipulate them, as, by doing so, they not only obtain better matchings but also increase their total application fee revenues. While this theoretical result does not necessarily show that hospitals do indeed overreport their application fees in real-life, it demonstrates a potential for such manipulation and justifies the observed application fee differences from another point of view. Another important point is the practical differences between application fee manipulations and the other well-known types of manipulations in the literature: preference, capacity and pre-arrangement. They are different in some important ways. First, as we will formally investigate in the discussion section, there are problem instances at which every stable mechanism is manipulable via application fees, yet, non-manipulable via capacities and pre-arrangements. While this is not true for preference manipulations, application fee channel might still be more advantageous due to the additional higher revenue aspect.

This paper extends the line of research on manipulations in matching markets by investigating the application fee overreporting incentives. We introduce a preference-reporting game which mimics real-world matching markets with application fees and show that no stable mechanism is immune to application fee manipulations. Interestingly, we observe that, under any stable rule, a hospital might not only obtain a better assignment but also increase its application fee revenue in any equilibrium outcome through overreporting its true application fee. In contrast to this negative result, no stable mechanism turns out to be manipulable at a problem if either side has homogeneous preferences or each hospital has only one position.