Abstract

Introduction
11
Matching is a pervasive phenomenon that arises in many economic and social settings. 1  In a two-sided matching market, agents that belong to one of two dis- joint sets, say colleges and students, have to be matched to each other. Agents— both colleges and students—have preferences over the other side of the market and over the prospect of being unmatched.  The matching problem then reduces to assigning students to colleges by means of a matching mechanism.  Stability, strategy-proofness, and (Pareto) efficiency of such mechanisms are highly valued properties. 2 The perhaps most famous matching mechanism relies on the deferred-accept- ance algorithm introduced by Gale and Shapley (1962). This algorithm was writ- ten as a means to show that a stable matching always exists in a two-sided match- ing market, transforming a matching where all agents are unmatched into a stable matching.  Besides guaranteeing stability, the Gale-Shapley mechanism has other appealing properties: truth is a dominant strategy for one side of the market (Du- bins and Freedman, 1981, Roth, 1982a) and it is efficient when welfare of both sides of the market is considered (Roth, 1982a). Many studies of strategic behavior under a matching mechanism rely on the implausible assumption of complete information.  Knowing the true preferences of every agent in the market is more than we may reasonably expect from agents in most matching markets.  Roth (1989) made the first attempt to deal with the incom- plete information case. Even though truth obviously remains a dominant strategy for one side of the market when the Gale-Shapley mechanism is employed, the equilibrium characterization for the complete information case is not robust to in- complete information. Ehlers and Massó (2007) study the Bayes-Nash equilibria of mechanisms that produce stable matchings and find a necessary and sufficient condition for truth-telling to be an equilibrium.  Roth and Rothblum (1999) and Ehlers (2003, 2004) are less ambitious and do not aim at characterizing equilibria, but give advice to individuals on how to act in matching markets when there is uncertainty about the others’ strategies. Still, many questions regarding strategic incentives under incomplete infor- mation remain to be answered on theoretical grounds.  How the amount of in-
2
formation held by individuals on the elements of the game actually influences individuals' decisions and affects the performance of matching mechanisms, are questions to be explored.  Barberà and Dutta (1995) consider truth-telling as a form of "protective" behavior, claiming that risk averse agents may revert to faith- fully revealing their true preferences when they are poorly informed.  Moreover, in mechanisms for which truth is not a dominant strategy, computing the optimal strategies requires a lot of information on others' preferences.  In this paper we present an experimental study of these and other related claims, providing a direc- tion into which the role of information on individual decisions may be ascertained. Following a previous work by Pais and Pintér (Pais and Pintér, 2007) where the role of information on decision making and the properties of several matching mechanisms in the school choice model were examined in the experimental lab, in this paper we pose similar questions in a more general matching model, the so called college admissions model. 3  In these problems, individuals of one side of the market—let us call them teachers—have strict preferences over the agents of the other side (schools). In contrast to the school choice model, in the college ad- mission problem schools are assumed to be strategic agents with strict preference ordering over teachers and a maximum capacity, i.e., the number of vacancies that should be filled by teachers.  Hence, in this model both sides of the market act strategically. Therefore both teachers and schools may be interested in hiding their true preferences. We assess the influence of information in the Gale-Shapley mechanism and in another well-known matching mechanism, the Top Trading Cycles mechanism (TTC). 4 Although the TTC mechanism was initially designed for situations where indivisible objects have to be assigned to individuals, it can be fi t to the college admission problem by taking into consideration the schools’ preferences as well. We provide an empirical test of the matching mechanisms with boundedly rational individuals and address a series of practical questions. First, we compare the two above mentioned mechanisms under three informational scenarios, ranging from complete ignorance about the other participants' preferences to complete infor- mation on all elements of the game. In particular, we are interested in comparing the incentives agents face under different mechanisms, as well as in comparing efficiency levels and stability of the outcomes, for different information levels. Second, within each mechanism, we evaluate the influence of the amount of in- formation held by individuals on private decisions. We are concerned in testing whether truth-telling emerges as a salient form of behavior among teachers when information is low. This would imply that, in markets where we expect agents to know little about others, strategy-proofness of the mechanism should not drive the choice of the matching mechanism. On the other hand, if we are able to determine that information significantly affects individuals' behavior, we can immediately conclude that some of the existing theoretical results, which use the assumption of complete information, are insufficient to deal with markets where agents know little about others.  Otherwise, if the effect of information is not relevant, theory (with complete information) may be considered apt to deal with the incomplete information case. Our results support the first conjecture:  information is important, there is a large difference in individuals' behavior between scenarios where they hold almost no information on the elements of the game and those where informa- tion held is substantial.  In fact, in a very low informational environment, acting straightforwardly is a salient form of behavior not only among teachers, but also among schools. This result for the schools contradicts the theoretical results (for complete information).  In what stability is concerned, information has again an important but contrary effect on the two mechanisms: while in the Gale-Shapley mechanism the amount of information has a negative effect on the frequency of stable outcomes, in the TTC mechanism this effect is positive. The same negative relation can be observed between information and efficiency in the TTC mecha- nism, while in Gale-Shapley mechanism efficiency is not sensitive to the amount of information participants hold.  Despite the simplicity of the experimental de- sign, the comparison of the mechanisms may have important policy implications. The results in this paper suggest that the Gale-Shapley mechanism proves to be more successful than the TTC mechanism regarding both stability and efficiency. 5 When examining strategy-proofness, the only significant difference in the propor- tion of truthful play we find is in the partial-information treatment in favor of the TTC mechanism. There exist several experimental studies of matching problems, some of which aim at testing the above mentioned mechanisms.  Harrison and McCabe (1996) explore the Gale-Shapley mechanism and show that profitable manipulation of agents’ preferences and reaching an efficient outcome become more difficult as markets get larger. Chen and Sönmez (2002a) compare a random serial dictator- ship mechanism used to allocate dormitory rooms in American universities with a variant of the TTC in an incomplete information environment.  They conclude that the TTC produces significantly more efficient allocations.  In a compan- ion paper, Chen and Sönmez (2002b) evaluate the performance of these mech- anisms under complete information, reaching the same qualitative results.  Chen
44
and Sönmez (2006) consider the school choice problem and analyze the TTC, the Gale-Shapley, and the Boston mechanisms under (partially) incomplete infor- mation, concluding that, in what efficiency is concerned, Gale-Shapley improves upon the TTC, which outperforms the Boston mechanism.  The difference be- tween the above studies and this paper derives not only from the use of the college admissions model, but also from our main objective: to test the role of information in evaluating matching mechanisms. 6 We proceed as follows.  Section 2 presents the description and the theoreti- cal properties of the matching mechanisms under study.  Section 3 describes our experimental design.  Section 4 summarizes the main experimental results and section 5 concludes.
Theoretical results
2
Two-sided matching models have been developed to analyze situations in which elements from the two (disjoint) sides of the market should be paired, where each element has a preference ordering on the opposite side and both sides can act strategically.  In the assignment problem that we implemented in the experi- mental lab a number of teachers is to fill a number of vacancies across different schools.  Each teacher is assumed to have a strict preference ordering over all schools and each school is assumed to have a strict preference ordering over all teachers, as well as a maximum number of teachers to employ (capacity).  The fact that both teachers and schools can act strategically and reveal orderings that are different from the true preferences is what distinguishes this problem from the school choice model.7 The outcome of the problem is a matching, an assignment of teachers to teach- ing positions (schools), such that each teacher is assigned one vacancy and each vacancy is filled by one teacher only.  A matching is Pareto efficient if there is no matching that assigns at least one participant a strictly better partner and every other participant a weakly better mate. A matching is stable if every agent prefers his partner to being alone and, moreover, no pair of agents (each on one side of the market) who are not matched to each other would rather prefer to be so matched. A matching mechanism consists of a strategy space for each participant—the set of all possible preference orderings over the other side of the market—and a function that selects a matching for each strategy profile. A matching mechanism
S
is efficient if it always chooses Pareto efficient matchings.  It is strategy-proof if no participant can profitably manipulate her preferences, independently of the other agents' strategies, and it is stable if it always selects stable matchings. In what follows we briefly describe the two matching mechanisms whose em- pirical properties we studied in the experimental lab. The presentation is tailored to our example with teachers and schools. 8 Mechanism 1. Gale-Shapley 1. Each teacher reports her preferences over the schools and each school re- ports her preferences over the teachers. 2. Given the submitted preferences of the teachers and schools’ priority orders, positions are allocated after undergoing the following steps: (a) Each teacher proposes to her first ranked school.  Each school keeps the applicants with higher priority order on hold until positions are filled, while rejecting the lowest priority teachers in excess of its ca- pacity. (b)  In general at round k: Every teacher who got rejected in the previous step proposes to the next school on her list of preferences. Each school considers the teach- ers on hold from the previous steps together with the new applicants. The lowest priority teachers in excess of the school’s capacity are re- jected, while remaining applicants are kept on hold. (c) This process is repeated until no applications are rejected. Each par- ticipant is then assigned the position at the school that keeps her on hold. The Gale-Shapley mechanism is strategy-proof for the proposing side; in our case truth is a dominant strategy for teachers.  However, schools may gain by manipulating their messages and not reporting their preferences truthfully. There- fore, we expect a different kind of behavior from teachers and schools: teachers should faithfully reveal their true preferences over schools independently of the information they hold, while among schools we expect to find some preference manipulation.  The Gale-Shapley mechanism is stable and it is also Pareto effi- cient when the welfare of both sides of the market is taken into account. Although the other—TTC—mechanism was initially designed for situations where indivisible objects had to be assigned to individuals, it can be fit to the college admissions problems by taking into consideration the schools’ preferences as well (see the description of the mechanism below). Mechanism 2. Top Trading Cycles (TTC) 1. Each school reports her preferences over the teachers and each teacher reports her preferences over the schools. 2.  An ordering (a queue) of teachers is randomly chosen. 3. For any submitted profile of teachers’ preferences, schools’ preferences, and ordering of teachers, the outcome is obtained after undergoing the following steps: (a)  A tentative assignment is made in the following way.  Given the submit- ted preferences of schools, each schools gets assigned its top-ranked teachers up to capacity.  In case a teacher is preferred by several schools, she gets assigned to the school she prefers (according to her submitted preference ordering), and the other schools keep this posi- tion vacant. (b) The first teacher in the random ordering proposes to her top ranked school. If either nobody or she was tentatively assigned to this school, the assignment is finalized and both the teacher and this teaching po- sition are removed from the system. The procedure continues with the second teacher in the ordering. Otherwise, the first teacher in the or- dering who was tentatively assigned to the desired position is inserted in the top of the ordering. (c) When the ordering is modified, this procedure is repeated, so that the teacher who just became first in the ordering sends an application to her highest-ranked school.  If either nobody was assigned tentatively or she has priority at this school, the assignment is finalized and the procedure continues with the next teacher in line; otherwise, the first teacher in the ordering with priority at the proposed school is inserted in the top of the ordering, in front of the requester. (d) If a cycle forms, it consists of a sequence of proposals of the kind: A proposes to the school where B was tentatively assigned, B applies to C’s priority school, and C proposes to A’s priority school.  In such cases, all teachers in the cycle are assigned to the schools they pro- posed to and teachers and their respective assignments are removed from the system.
(e) The procedure stops when all teachers are assigned to a position.
The TTC mechanism in this setting is strategy-proof for agents on the propos- ing side, i.e., for teachers, but schools may gain with untruthful behavior.  The mechanism is Pareto efficient for reported preferences, but it is not stable. 9  We thus expect to observe different behavior from teachers and schools regarding faithfulness—just as in the Gale-Shapley mechanism. If theory is to be confirmed, the Gale-Shapley mechanism should outperform the TTC in terms of stability, while regarding truthful preference revelation and efficiency the two mechanisms should perform similarly in the experimental lab.
Experimental design
3
Economic experiments with different informational settings have been designed to analyze the empirical behavior of the above described two matching mechanisms. We use a 2x3 design, i.e., we construct three treatments (for both mechanisms) differing in the amount of information held by participants on the elements of the game. This allows us to compare individual decisions in six treatments. Our analysis concentrates on the role of information in truthful preference revelation, in efficiency, and in stability.  The environment is designed to capture the key aspects and difficulties of each mechanism, under a controlled environment, with relatively small groups of participants. At the beginning of each session participants were randomly and anonymously assigned a role:  teacher (J, K, L, M, or N) or school (A, B, or C). These roles were maintained during the session.  Participants were told that they had been sorted in anonymous groups of eight (five teachers and three schools).  In each group there were five vacancies across three schools differing in capacity and desirability, and each position was to be assigned to one teacher only. Preferences over the agents of the other side of the market were induced by the monetary payoff participants obtained depending on their position in the resulting matching at the end of the experiment. The payoff tables were designed to create a strategic conflict situation. The payoffs obtained by teachers and schools were symmetric as every teacher got 15€ for her top choice, 9€ for the second choice, and 3€ for the last choice; while each school got 15€ for her top choice, 12€ for the second choice, 9€ for the third choice, 6€ for the fourth choice, and 3€ for the last (fifth) choice.
8
Different teachers and schools did not need to agree on which school or teacher was her top, her second, etc., last choice, respectively.  The payoffs of different outcomes were sufficiently dispersed so as to have a monetarily salient difference between getting one's best and one's worst choice. In what follows we compare individual reports to the induced preference orderings and treat the latter as the true preference ordering. Under each mechanism, each group of participants played the game three times, receiving three different amounts of information in an increasing way. In order to avoid participants from playing from memory when the mechanism was changed, we shuffled the labeling of schools and modified school characteristics accordingly.  It follows that each participant kept the same role throughout the whole experiment, even though her payoff matrix seemingly changed. 10 In each experimental session the following three different informational treat- ments were implemented in case of both mechanisms: ● Zero information : Each participant knows her own induced preferences (i.e., the row of the payoff matrix that corresponds to her role), but not the other participants' preferences.  She is only told that different participants might have different payoff tables.  In this treatment teachers and schools have no information about the other side's induced preferences, but they are told the capacity of each school. ● Partial information : Besides the own induced preferences and the capac- ity of each school, teachers and schools have some information about the preference orderings of the other side of the market. Each teacher is given the list of favorite teacher(s) of each school (up to capacity) and each school is told the top choice of each teacher. ● Full information : Each participant has complete information on the pref- erences of all participants and the capacity of schools. In the case of the TTC mechanism, as the schools' priority orderings are re- flected in the tentative assignment, under the partial-information treatment partic- ipants are told—besides their own induced preferences—the tentative assignment of all participants given the induced preferences. Under the full-information treat- ment they know both the induced preferences of all participants and the tentative assignment.  In these two treatments participants are reminded that this initial
9
assignment may change as schools and/or teachers might manipulate their prefer- ences. Three sessions were conducted with undergraduate students from the Uni- versitat Autònoma de Barcelona, recruited using classroom announcements and posters throughout the campus, where the experimental sessions (on paper/by hand) took place.  Overall 72 subjects divided into 9 groups participated in the experiment. Each subject was allowed to participate in one session only. Sub- jects were informed that they would participate in a decision making task. At the beginning of each session, they were randomly seated at the tables and printed instructions were given to them. Before starting a mechanism, the corresponding instructions were read aloud. In each session and for each informational setting participants were asked to submit a preference ordering, from their top choice to the last. In each session six treatments were implemented. In this way we have observed six decisions from each participant, each under a different mechanism and/or different informational setting. The order of implementation of the mecha- nisms and informational settings—to avoid learning about others' preferences—is listed in table 1.
Subjects did not get any feedback about previous decisions or outcomes at any moment of the experiment. At the end of each session, one of the six treat- ments was chosen randomly for payment, matching was determined for the chosen treatment, and earnings were paid. Sessions lasted for about 90 minutes and the average net payment—including a 3€ show-up fee—was around 16€ .11
10
Experimental results
4
Our main aim is to examine the importance of the level of information that par- ticipants hold in the two matching mechanisms. The experimental setting we use allows us to analyze simultaneously the role of information in private decisions and whether it affects the empirical properties of the mechanisms. The first ques- tion is whether individuals report their preferences truthfully. We study whether the amount of information given to the participants influences truthful preference revelation. And, on the other hand, whether under the same informational setting, truthful preference revelation changes with the implemented mechanism.  The question is the same regarding stability and efficiency. Again, we compare sta- bility and efficiency levels under each mechanism across information settings and across different mechanisms for the same information level.
Truthful preference revelation
4.1
Table 2 shows the proportion of teachers and schools who played truthfully. Re- member that according to theoretical results truth is a dominant strategy for teach- ers in both mechanisms, but it is not for schools. Therefore, we expect a significant number of schools manipulating their messages in both mechanisms.
Our data shows that the proportion of truthful preference revelation of teachers– for whom both mechanisms are strategy-proof—varies between 84% and 58%, depending on both the informational setting and the implemented mechanism. Considering the results of similar experiments¹², we note that these proportions are relatively high in general, which may also be due to the fact that potentially profitable manipulations for teachers are very limited in a three school setup. 13
11
Still, given that even under both strategy-proof mechanisms we observe misrep- resentation of preferences, it remains important to examine who manipulates the preferences and in which manner. We identify three possible ways of preference manipulation for teachers. We noticed that a substantial proportion of the teach- ers has ranked the school where she has priority higher in the submitted ranking than it would be according to the induced preferences, this is what we call the "Priority School Bias" (PSB). The second identified way of manipulating the true preferences is to underrank the most competitive school (i.e., the school with only one vacancy). This behavior we call—following Chen and Sönmez—the "Small School Bias" (SSB). The third manipulation method (PSB&SSB) is the simul- taneous use of both previously described ways. 14 By comparing the payoffs that teachers earn, we confirm that untruthful behavior is costly, as on average a teacher who manipulated her preferences lost 1.98€ in the Gale-Shapley mechanism and 2.43€ in the TTC mechanism. This is not surprising given that both mechanisms are strategy-proof for teachers. Among schools preference manipulation is much more frequent but this is not surprising given the predictions of theory (for this side of the market it is not dominant to reveal truthfully their induced preferences).  Note that it may also be due to the fact that schools have to rank 5 candidates whereas teachers rank only 3 schools (as explained above). We can observe that the proportion of pref- erence manipulation among schools varies between 78% and 44%, depending on the mechanism and the amount of information these participants hold. In general, we can see that as players get more information about the elements of the game, the proportion of schools that reveal the preferences truthfully decreases, in both mechanisms. In the case of the schools we can also observe that schools tend to rank higher those teachers who rank them higher in their (induced) preferences. This may mean that schools recognize the teachers' incentives for truthful play and therefore with this kind of preference manipulations they pretend to "ensure" themselves an acceptable—although not the top—candidate. We can distinguish two versions of this general way of manipulating preferences: there are schools that only manipulate the candidates that are out of its capacity in the induced pref- erence list (i.e., changing the order of the last four or three candidates, depending on the number of vacancies the school has); while there are schools that manipu- late over the whole list. Comparing the earnings, we can conclude that, in general, this strategic behavior results successful, as schools that decide to manipulate their preferences earn slightly more than if they did not do so. This difference is 0.47€ for the Gale-Shapley mechanism, and 0.13€ for the TTC mechanism.  Although these average gains are small, and individually there may be schools that loose,
12
this result shows that schools manage to benefit from preference manipulation. Our main findings related to truthful behavior and based on the statistical anal- ysis of the data are summarized in results 1a and 1b. Result 1a: The amount of information has a significant negative effect on teachers’ truthfulness under both mechanisms.  The more information teachers receive, the lower the proportion of truthful reports. Statistical evidence. Under both mechanisms, the null hypothesis of equal pro- portions of truthful preference revelation across the three informational settings can be rejected at 5% significance level. 15 The results of the pairwise comparisons (with the corresponding significance level based on Cochran's test) are in Table 3. 16 For both mechanisms, the zero-information setting resulted in a significantly
higher proportion of truth-telling than in any other treatment where teachers got additional information about other participants' preferences.  Interestingly, there is no significant difference regarding truthful preference revelation between the partial and the full information settings under any of the mechanisms. ■ As for the other side of the market, theory predicts that preference manipula- tion may represent a profitable strategy for schools. Result 1b: The amount of information has a significant negative effect on schools' truthfulness under both mechanisms. The more information schools re- ceive, the lower the proportion of truthful reports. Statistical evidence. Under both mechanisms, the null hypothesis of equal pro- portions of truthful preference revelation across the three informational settings can be rejected at 5% significance level. 17 The results of the pairwise compar- isons can be found in table 3. For both mechanisms the zero-information setting results in a significantly higher proportion of truth-telling than the full information one and in the case of the TTC mechanism the difference is significant between the zero and the partial information settings as well. This difference comes from the high proportion of truth-telling in this mechanism under the zero-information setting.  There is no significant difference regarding truthful preference revelation between the partial and full information settings, in any of the mechanisms. Regarding differences in truthfulness across mechanisms, truthful preference revelation is slightly higher in the TTC mechanism under every treatment, even though Cochran's test confirms a significant difference only in the partial-information treatment.
Stability and efficiency
4.2
The other two important properties of a matching mechanism are stability and efficiency. Recall that the Gale-Shapley mechanism generates outcomes that are stable with respect to the submitted preferences, while the TTC mechanism does not fulfil this property.  The average stability of a treatment is calculated as the proportion of stable matchings with true preferences among all the matchings re- alized.  The set of stable (core) matchings for both mechanisms is listed in table 4.
The proportion of stable outcomes varied between 0% and 66.7% across mech- anisms and informational settings in the experiment. Result 2: Depending on the information setting, there exists a significant dif- ference in stability between the Gale-Shapley and the TTC mechanisms.  Both mechanisms are sensitive to the amount of information that participants hold, but the effect of information on stability is the opposite in the two mechanisms. Statistical evidence.  Our results show that (on average) stability in the Gale-Shapley mechanism (52%) is higher than in the TTC mechanism (33%). However, de- pending on the information setting this difference can be insignificant.  When comparing the proportion of stable outcomes across the mechanisms (under the same information treatment), we find that the difference is highly significant in the zero- and full-information treatments, while it is not significant in the partial- information treatment. The proportion of stable matchings in each treatment that support the result are to be found in table 5. Apparently the amount of informa-
tion has an important effect on the stability of the mechanisms. For both mech- anisms the null hypothesis of equal proportions of stable outcomes across the three information treatments is rejected at the usual significance levels. 18  In the Gale-Shapley mechanism stability is significantly higher in the zero-information treatment than in any other treatment with additional information, but there is no significant difference in stability between the partial- and full-information set- tings. In case of the TTC mechanisms the difference in stability is highly sig- nificant between any two information treatments.  While in the Gale-Shapley mechanism with the increase of the amount of information—and of preference manipulation—the ratio of the stable matchings decreases, in the TTC mechanism we observe the opposite: as more information is available and preference manip- ulation gets more frequent, the likelihood of getting a stable outcome increases. ■ The results of the pairwise comparisons are in table 6.

15
Following Harrison and McCabe (1996) we define efficiency as the minimum payoff distance to the core using the cardinal information contained in the payoff tables. 19 First, we compute the absolute value of the difference between the core payoff and the realized payoff for each group and for each core outcome.  With this we have for each group the distance to each of the three stable outcomes our games have. Then, we choose the minimum over these three distances, and this is the measure we will use to evaluate efficiency. We are concerned about the possible differences in efficiency across differ- ent information settings and also between the two mechanisms.  If we find that efficiency depends on the amount of information participants hold, this directly implies that under some informational treatment(s) stability is significantly higher than in some other(s). Now let us focus on the effect of information on efficiency. Result 3: In the Gale-Shapley mechanism there is no significant difference in efficiency across the three informational settings. In the case of the TTC mecha- nism there is a significant difference in efficiency:  in the zero-information setting efficiency is significantly lower. Statistical evidence.  Under the Gale-Shapley mechanism the hypothesis of equal efficiency (equal distance to the core) across the three informational settings can not be rejected at the usual significance levels, whereas under the TTC mecha- nism the same hypothesis can be rejected. 20  The average distance from the core in the zero-information setting is significantly higher than either in the partial- infomation or the full-information setting. We do not find any significant differ- ence regarding efficiency between the partial and full information settings.  The results of pairwise comparisons (with the corresponding significance levels) can be found in table 8.21 ■ Result 4: If participants have no information about the preferences of other participants, the Gale-Shapley mechanism performs significantly better than the TTC mechanism in terms of efficiency.  In case participants have additional in- formation, there is no significant difference in efficiency between the two mecha- nisms. Statistical evidence.  In the zero-information treatment the Wilcoxon signed ranks test confirms that the average minimum distance from the core is significantly
16

***Difference significant at 1%.
higher under the TTC mechanism than under the Gale-Shapley mechanism, at any significance level no lower than 1.4%. 22 This implies a significantly higher efficiency level under the Gale-Shapley mechanism. The same test in the partial- information setting can not detect a significant difference in efficiency (the test statistics is -0.677) between the two mechanisms. In the full-information setting the difference in efficiency between the two mechanisms is significant only at a significance level higher than 8.8%. ■
Concluding remarks
5
In this paper, we examine the so called college admissions model that is closely related to the school choice problem.  We analyze two well-known matching mechanisms—the Gale-Shapley and the TTC mechanisms—under three differ- ent informational settings. Our experimental design allows us—besides providing an empirical test of matching mechanisms with boundedly rational individuals– to analyze two main questions. Firstly, we compare the two mechanisms in terms of strategy proofness and efficiency in three informational settings. Secondly, we evaluate the effect of the amount of information held by individuals on decision making. Our results show that in each mechanism having more information about oth- ers' preferences results in a lower proportion of truth-telling for teachers. That is, in case teachers have partial or full information about the elements of the game, a significantly higher number of participants manipulate their preferences than when they only know their own preferences.  This result is consistent with the results presented in Pais and Pintér (2007) for the school choice model, but differs in intensity, as when schools may also behave strategically the preference manip- ulation rate is higher—specially under the TTC mechanism—than when schools are mere objects to be distributed among teachers.  Although these differences in teachers' preference manipulation across the two matching models are only signif- icant in the TTC mechanism under the zero- and full information treatments 23 , our results suggest that teachers anticipate the strategic behavior of schools and adjust their decisions to it.  The behavior of schools shows a similar pattern regarding truth-telling—more information means less truthfulness—, however preference manipulation for schools is predicted by theory. Regarding efficiency—measured as a distance to the core—information is rel- evant only in the TTC mechanism, where we detect a significantly lower efficiency level in the zero information setting. In the case of the Gale-Shapley mechanism all three treatments yield the same (relatively high) efficiency as well as stabil- ity levels. When comparing the two mechanisms in terms of efficiency, we find that the Gale-Shapley mechanism performs better than the TTC mechanism, as in the zero-information setting—when preference manipulation is low—it clearly outperforms the TTC mechanism. Examining our results regarding stability we observe that in the TTC mechanism stability increases with the amount of infor- mation. Comparing these results with Pais and Pintér (2007), we suspect that it is due to the activity of the schools, as in the school choice model stability was very low for any informational environment. We conclude that the comparison of the mechanisms suggests the superiority of the Gale-Shapley mechanism in the college admissions model.  Although re- garding truthful preference revelation—depending on the implemented informa- tional setting—it may give similar results to the TTC mechanism, in the achieved efficiency level and stability the Gale-Shapley mechanism performs clearly better than the Gale-Shapley mechanism. We also find that the amount of information plays an important role in partic- ipants' decision making. In general, if participants—both teachers and schools— only know their own preferences they are more likely to play truthfully than in case of having additional information.
18
[1] Abdulkadiroglu, Atila and Sönmez, Tayfun (1999): "House Allocation with Existing Tenants", Journal of Economic Theory 88(2), pp.233-260 [2] Abdulkadiroglu, Atila and Sönmez, Tayfun (2003): "School Choice: A Mechanism Design Approach", American Economic Review 93(3), pp.729- 747 [3] Abdulkadiroglu, A., Pathak, P., Roth. A., and Sönmez, T. (2005): "The Boston Public School Match", American Economic Review, Papers and Pro- ceedings 95(2), pp.368-371 [4] Abdulkadiroglu, A., Pathak, P., Roth, A. and Sönmez, T. (2006): "Changing the Boston School Choice Mechanism", NBER Working Papers no. 11965 [5] Barberà, S. and Dutta, B. (1995): "Protective Behavior in Matching Mod- els", Games and Economic Behavior 8., pp.281-296 [6] Chen, Y. and Sönmez, T. (2002a): "Improving Efficiency of On-Campus Housing:  an  Experimental  Study",  American  Economic  Review  92(5), pp.1669-1686 [7] Chen, Y. and Sönmez, T. (2002b): "An Experimental Study of House Allo- cation Mechanisms", Economics Letters 83(1), pp.137-140 [8] Chen, Y. and Sönmez, T. (2006): "School Choice: An Experimental Study", Journal of Economic Theory 127., pp. 202-231 [9]  Conover, W.J. (1980):  Practical Nonparametric Statistics , New York:  John Wiley & Sons [10] Dubins, L. and Freedman, D. (1981): "Machiavelli and the Gale-Shapley Algorithm", American Mathematical Monthly 88., pp.485-494 [11] Ehlers, L. (2003): ''In Search of Advice for Physicians in Entry-Level Med- ical Markets" Cahiers de Recherche, 13-2003, Centre Interuniversitaire de Recherche en Économie Quantitative, CIREQ [12] Ehlers, L. (2004): ''In Search of Advice for Participants in Matching Mar- kets Which Use the Deferred-Acceptance Algorithm", Games and Economic Behavior 48., pp.249-270 [13] Ehlers, L. and Massó, J. (2007): "Incomplete Information and Singleton Cores in Matching Markets" Journal of Economic Theory 136(1), pp.587- 600 [14] Ergin, H. and Sönmez, T. (2006): "Games of School Choice under the Boston Mechanism", Journal of Public Economics 90., pp.215-237 [15] Gale, D. and Shapley, L. (1962): "College Admissions and the Stability of Marriage", American Mathematical Monthly 69., pp.9-15 [16] Harrison, G. and McCabe, K. (1996): "Stability and Preference Distortion in Resource Matching: an Experimental Study of the Marriage Problem", In V. Smith (ed.) Research in Experimental Economics 6., pp.53-129, JAI Press [17] Haruvy, E., Roth, A., and Ünver, U. (2006): "The Dynamics of Law Clerk Matching: An Experimental and Computational Investigation of Proposals for Reform of the Market", Journal of Economic Dynamics and Control 30., pp.457-486 [18] Kagel, J. and Roth, A. (2000): "The Dynamics of Reorganization in Match- ing Markets: a Laboratory Experiment Motivated by a Natural Experiment", Quarterly Journal of Economics 115(1)., pp.201-235 [19] McKinney, C., Niederle, M., and Roth, A. (2005): ''The Collapse of a Med- ical Labour Clearinghouse (and Why Such Failures Are Rare)" American Economic Review 95., pp.878-889 [20] Nalbantian, H. and Schotter, A. (1995): "Matching and Efficiency in the Baseball Free-Agent System: an Experimental Examination",  Journal of Labour Economics 13., pp.1-31 [21] Olson, M. and Porter, D. (1994): "An Experimental Examination Into De- sign of Decentralized Methods to Solve the Assignment Problem With and Without Money", Economic Theory 4., pp.11-40. [22] Pais, J. and Pintér, A. (2007): "School Choice and Information: An Exper- imental Study on Matching Mechanisms", Games and Economic Behavior, forthcoming [23] Roth, A. (1982a): "The Economics of Matching: Stability and Incentives", Mathematics of Operations Research 7., pp.617-628 [24] Roth, A. (1982b): ''Incentive Compatibility in a Market With Indivisibili- ties", Economics Letters 9., pp.127-132 [25] Roth, A. (1984): "The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory", Journal of Political Econ- omy 92., pp. 991-1016. [26]  Roth, A. (1989): "Two-Sided Matching With Incomplete Information about Others' Preferences", Games and Economic Behavior 1., pp.191-209 [27] Roth, A. and Rothblum, U. (1999): "Truncation Strategies in Matching Mar- kets - In Search of Advice for Participants", Econometrica 67., pp.21-43 [28]  Roth, A. and Sotomayor, M. (1990): Two Sided Matching: a Study in Game Theoretic Modeling and Analysis , Econometric Society Monograph Series. New York: Cambridge University Press [29]  Shapley, L. and Scarf, H. (1974): "On Cores and Indivisibility", Journal of Mathematical Economics 1., pp.23-28 [30]  Ünver, U. (2001): "On the Survival of Some Two-Sided Matching Mech- anisms: An Experimental and Computational Investigation of the Stability Hypothesis” Mimeo, Koç University [31]  Ünver, U. (2005): "On the Survival of Some Two-Sided Matching Mecha- nisms", International Journal of Game Theory 33., pp.239-254 A
You are participant ID ……, in the role of teacher J . Capacity:  There are two positions opening at school B and C, and one at school A. Recall: Your payoff amount depends on the school position you hold at the end of the experiment.  Your possible payoff amounts are outlined in the following table:
This means, that if at the end of the experiment you hold a position: ●  at school A, you will be paid 15 €; ●  at school B, you will be paid 3 €; ●  at school C, you will be paid 9 €. Recall! Other participants might have different payoff tables. Recall!  The preference ordering submitted on the Decision Sheet does not necessarily need to coincide with the one generated by the payoff matrix. Recall! There are two positions opening at school B and C, and one at school A. Priority ordering of schools: Schools when offering teaching positions con- sider the quality of each applicant and the experience they have; and on this basis they make a priority ordering of all candidates. In this first informational environ- ment of the experiment you do not know anything about this ordering. Please submit your ranking of schools (A through C) from your first choice to your last choice. Please rank ALL three schools!
This is the end of the first game under the first mechanism. After the experimenter collects your Decision Sheet, you will be given the second Decision Sheet under the same mechanism, but for a new game (with different information structure). B
You are participant ID ……, in the role of school A. Capacity:  There are two positions opening at school B and C, and one at school A. Recall:  Your payoff amount depends on the school position you hold at the end of the experiment.  Your possible payoff amounts are outlined in the following table:
This means, that if at the end of the experiment you are matched with teacher: ●  J, you will be paid 3 €; ●  K, you will be paid 9 €; ●  L, you will be paid 6 €; ●  M, you will be paid 12 €; ● N, you will be paid 15 €. Recall! Different participants might have different payoff tables. Recall!  The preference ordering submitted on the Decision Sheet does not necessarily need to coincide with the one generated by the payoff matrix. Recall! There are two positions opening at school B and C, and one at school A. Priority ordering of teachers: Teachers when applying to schools, make a priority ordering of all schools.  In this first informational environment of the experiment you do not know anything about this ordering. Please submit your ranking of teachers (J through N) from your first choice to your last choice. Please rank ALL five teachers!
This is the end of the first game under the first mechanism. After the experimenter collects your Decision Sheet, you will be given the second Decision Sheet under the same mechanism, but for a new game (with different information structure). C You are participant ID ……, in the role of teacher J. Capacity:  There are two positions opening at school B and C, and one at school A. Recall:  Your payoff amount depends on the school position you hold at the end of the experiment.  Your possible payoff amounts are outlined in the following table:
This means, that if at the end of the experiment you hold a position: ●  at school A, you will be paid 15 €; ●  at school B, you will be paid 3 €; ●  at school C, you will be paid 9 €. Recall!  Different participants might have different payoff tables.  That is, payoff by school might be different for different participants. Recall!  The preference ordering submitted on the Decision Sheet does not necessarily need to coincide with the one generated by the payoff matrix. Recall! There are two positions opening at school B and C, and one at school A. Priority ordering of schools: Schools when offering teaching positions con- sider the quality of each applicant and the experience they have; and on this basis they make a priority ordering of all candidates. In this informational environment from the priority ordering of the schools you know only the best candidate(s) of each school. These are the following: ●  at school A teacher N has priority; ●  at school B teachers K and M have priority; ●  at school C teachers J (you) and L have priority. Please submit your ranking of the schools (A through C) from your first choice to your last choice. Please rank ALL three schools!
This is the end of the second game under the first mechanism. After the experimenter collects your Decision Sheet, you will be given the second Decision Sheet under the same mechanism, but for a new game (with different information structure). You are participant ID ……, in the role of school A. Capacity:  There are two positions opening at school B and C, and one at school A. Recall:  Your payoff amount depends on the school position you hold at the end of the experiment.  Your possible payoff amounts are outlined in the following table:
This means, that if at the end of the experiment you are matched with teacher: ●  J, you will be paid 3 €; ●  K, you will be paid 9 €; ●  L, you will be paid 6 €; etc. Recall! Different participants might have different payoff tables. Recall!  The preference ordering submitted on the Decision Sheet does not necessarily need to coincide with the one generated by the payoff matrix. Recall! There are two positions opening at school B and C, and one at school A. Priority ordering of teachers: Teachers when applying to schools, make a priority ordering of all schools. In this informational environment of the game you know in which school would each teacher get the highest payoff (according to the payoff table, but not the submitted ordering). Please submit your ranking of teachers (J through N) from your first choice to your last choice. Please rank ALL five teachers!
This is the end of the second game under the first mechanism. After the experimenter collects your Decision Sheet, you will be given the last Decision Sheet under the same mechanism, but for a new game (with different information structure). E You are participant ID ……, in the role of teacher J. Capacity:  There are two positions opening at school B and C, and one at school A. Recall:  Your payoff amount depends on the school position you hold at the end of the experiment.  Your possible payoff amounts are outlined in the following table:
C 9
15 3 3 9 This means, that for example, if at the end of the experiment: ●  you hold a position at school A, teachers K and L hold a position at school B, and teachers M and N hold a position at school C, the payoffs would be the following: ●  you would be paid 15€; teacher K would get 9€; teacher L would get 15€; teacher M would get 3€; and teacher N would get 9€. ¡Recall!  The preference ordering submitted on the Decision Sheet does not necessarily need to coincide with the one generated by the payoff matrix. Priority ordering of schools: Schools when offering teaching positions con- sider the quality of each applicant and the experience they have; and on this basis they make a priority ordering of all candidates. In this informational environment the complete priority ordering of the schools is known by each teacher, and is shown in the following table:
Please submit your ranking of the schools (A through C) from your first choice to your last choice. Please rank ALL three schools!
This is the end of the games under the first mechanism. After we collect your Decision Sheet, you will be given the Instructions and the first Decision Sheet for a new mechanism. You are participant ID ……, in the role of school A. Capacity: There are two positions opening at school B and C, and one at school A. Recall:  Your payoff amount depends on the school position you hold at the end of the experiment.  Your possible payoff amounts are outlined in the following table:
This means, that if at the end of the experiment: ● You are matched with teacher J, school B with teachers K and L, and school C with teachers M and N, the payoffs would be the following: ●  You would get 3€; school B: 15€ (12€ +3€); and school C 15€ (9€ +6€). ¡Recall!  The preference ordering submitted on the Decision Sheet does not necessarily need to coincide with the one generated by the payoff matrix. Priority ordering of teachers: Teachers when applying to schools, make a priority ordering of all schools. In this informational environment of the game all participants know the complete payoff matrix of teachers, which is the following:
Please submit your ranking of teachers (J through N) from your first choice to your last choice. Please rank ALL five teachers!
This is the end of the first mechanism. After we collect your Decision Sheet, you will be given the Instructions and the first Decision Sheet for a new mechanism.