Design of a Laboratory Assignment Institution without the Second Selection
under the Sameness Assumption: Fairness, Strategy-Proof and Stability
Yoshinori TOMIYAMA and Fumio HOSONO(Gunma University)"Laboratory assignment" is a process to assign students to laboratories for their graduation research.
It assumes the following conditions: every student should belong to one and only one laboratory, themaximum number of students for each laboratory is fixed and announced in advance, and the processof assignment depends only on the preferences of the students and teachers involved. Under thisassumption, we consider a laboratory assignment institution for each student to be able to belong tosome laboratory. An extended version of the matching institution which was proposed by Gale andShapley (1962) not only satisfies the conditions required but also has some theoretically desirable
properties. But this institution assumes, among others, that every student should, by preference,linearly order all the laboratories from which to choose only one for his/her graduation research,which, though theoretically valid, is not realistically plausible. To put it into practice, it should beexamined whether assignment can be successful when the number is relatively small of thecandidates a student should choose first from all the laboratories. Analysis by Monte Carlo simulation
reveals that this institution works well even in such situations, given a certain set of conditions on themaximum number of students for each laboratory and the number of the candidates the students
should submit first.
Key words and phrases: Laboratory Assignment, Sequential Selection Institution, Institution Design
without Second Selection, Social Matching Theory, Monte Carlo Simulation

1. INTRODUCTION"Laboratory assignment" is a process to assign students to laboratories for theirgraduation research. It assumes the following conditions: every student should belong to one
and only one laboratory, the maximum number of students for each laboratory is fixed andannounced in advance, and the process of assignment depends only on the preferences of thestudents and teachers involved. Under this assumption, we consider a laboratory assignment
institution for each student to be able to belong to some laboratory.
Among the institutions ever proposed for the same or a similar purpose is "Sequential
Selection Institution," which has actually been used in some faculties in Japanese universities.
The main part of this institution is as follows. Some of all the students are assigned tosomewhere laboratories at the first selection of laboratory assignment. Some of the otherstudents who are unmatched at the first are assigned to somewhere laboratories at the second.
Some of the other students who are unmatched at the second are assigned to somewherelaboratories at the third, and so on. This matching process is repeated until all students areassigned. This institution, however, has some problems: unfairness among students orm iyano.doc 2002.12.26 01:39

1/9

tom iyam alaboratories in assignment processes, existence of incentives to show untrue preferences, andinstability on assignment outcomes (Tomiyama and Hosono 1999).
Another institution is an extended version of the matching procedure that was proposed
by Gale and Shapley (1962), using the social matching theory as a branch of the game theory.
This institution not only satisfies the conditions required above but also avoids these problems(Roth 1982, 1984, 1985a, 1985b, 1985c, Roth and Sotomayer 1990, Tomiyama 1992). But
this institution assumes, among others, that every student should, by preference, linearly order
all the laboratories from which to choose only one for his/her graduation research, which,though theoretically valid, is not realistically plausible. To put it into practice, it should be
examined whether assignment can be successful when the number is relatively small of thecandidates a student should choose first from all the laboratories. According to Tomiyama andHosono (1999), an analysis by Monte Carlo simulation reveals that this institution works welleven in such situations, given a certain set of conditions on both the maximum number ofstudents for each laboratory and the number of the laboratories the students should submit
first.
The good result is obtained under several assumptions set up for the simulation. One of
the assumptions is that the preference orderings of laboratories over the set of students are
randomly generated from the uniform distribution in the computer program. Some faculties inJapanese universities, however, do not satisfy this random assumption. In their laboratory
assignment institutions, the preference orderings of laboratories are the same. The sameness isactualized by use of a list of the students' records. Under this sameness assumption, it is notclear whether the above simulation result is preserved. The purpose of this paper is toinvestigate this situation by Monte Carlo simulation under the same assumptions inTomiyama and Hosono (1999), except for the sameness assumption.

2. A MONTE CARLO SIMULATION: METHOD AND PARAMETERS
The matching procedure that was proposed by Gale and Shapley is outlined in thefollowing. It has the six parameters:
NOS

the number of students

NOL

the number of laboratories

MNS

the maximum number of students who can belong to each laboratory

RPO

the ranking of preference ordering which a student submits firstPOS

the preference ordering of a student over the set of laboratories

m iyano.doc 2002.12.26 01:39

2/9

tom iyam aPOL

the preference ordering of a laboratory over the set of students

Given a set of the first four parameters, NOS, NOL, MNS and RPO, this proceduremakes a matching outcome between students and laboratories by use of only theinformation about a certain set of POSs and POLs. On this matching outcome, each
student may be matched to some laboratory, or some of the students may be matchedand the others unmatched. (For more information about the procedure, see Gale andShapley (1962) or Tomiyama (1992).)
Whether each student can be matched to some laboratory depends on the valuesof the parameters. In order to suitably determine the values used in the simulation, wewill have to consider about their characteristics in a real laboratory assignment. At
any time of laboratory assignment, it is considered that the values of NOS and NOL
are exogenously determined and fixed. This means that their values are uncontrollable
to the designer. But they may be different at the first of the academic year. Since
POLs are arbitrary fixed because of the sameness assumption, they also areuncontrollable. POSs are also uncontrollable, but are freely and randomly revealed by
the students. On the other hand, the values of MNS and RPO are normally considered
to be controllable within certain constraints.
Judging from the above, we determined the range of parameters’ values andseveral assumptions used in the simulation as follows. Table 1 shows the range of thefirst four parameters. It is assumed through the simulation that all MNSs are the sameamong the laboratories and all RPOs are the same among the students. POSs arerandomly and independently generated from the uniform distribution in the computer
program. But a certain POL is fixed in it as the same among the laboratories. In theTable 1. Range of parameters: Initial, final and incremental values
Parameters

InitialFinal

Increm
ental

NOS

20

200

20NOL

1050

5MNS

the minimum integer

20（NOS=20,40,60）

more than NOS/NOL

25（NOS=80,100）

130（NOS=120,140）
35（NOS=160,180,200）m iyano.doc 2002.12.26 01:39

3/9

tom iyam asimulation, the average number of unmatched students for 10,000 sets of POSs iscalculated under the sameness assumption about POL, given every set of the values ofNOS, NOL, MNS and RPO in Table 1. We call this average the "u-number" below.

3. ANALYSIS OF SIMULATION RESULTS
3.1 MNS and RPO Making the u-Number Zero
Analysis of the u-number for a pair of NOS and NOL. As mentioned in the preceding
section, it is considered that a pair of NOS and NOL is fixed at any time of laboratory
assignment. So, first, we shall analyze the u-numbers for one pair and investigate theircharacteristics.
Table 2 shows the u-numbers for all the pairs of MNS and RPO in Table 1 when NOS is
120 and NOL is 35. All of the u-numbers in the table are rounded off to one decimal place.
This is same in the other cases. This table tells us that the two outcomes hold:
Outcome 1: For any MNS, the u-number decreases monotonically as RPO increases.
Outcome 2: For any RPO, the u-number decreases monotonically as MNS increases.
These outcomes are identical to our intuition on the relation between MNS and RPO.
Let us introduce here some terminology for later discussions to be convenient. Assume
that a pair of NOS and NOL is fixed. We will use the term the “zero-RPO” to refer to theTable 2. The u- numbers (NOS=120, NOL=35)
RPO
MNS

12

34

56

7894

16.8 6.8 3.1 1.5 0.8 0.4 0.2 0.1 0.1

57.7 1.4 0.3 0.1

63.2 0.3

07

1.2

080.4

910m iyano.doc 2002.12.26 01:39

0000000000000000000000000 〜000000000000.1

000000000000000000000〜3010 〜 35〜000004/90〜
00000

tom iyam aminimum RPO making the u-number zero for a MNS and the “zero-MNS” to the minimum
MNS making the u-number zero for a RPO. The term “zero-line” can be defines as the set ofpairs of MNS and RPO satisfying both the zero-MNS and the zero-RPO. In Table 2, forexample, the zero-RPO for MNS 4 is 10, the zero-MNS for RPO 1 is 10, and the zero-line isconsisted of all 0 s.
Outcome 1 implies that there is only one zero-RPO for a MNS, and Outcome 2 implies
that there is only one zero-MNS for a RPO. Therefore, it is implied that there is only onezero-line for a given pair of NOS and NOL. Furthermore, the two outcomes imply thefollowings.
Outcome 3: When MNS is minimal and RPO is 1, the u-number is maximal.
Outcome 4: When MNS is minimal, the zero-RPO is maximal.
Outcome 5: When RPO is 1, the zero-MNS is maximal.
Outcome 6: The zero-RPO decreases monotonically as MNS increases.
Outcome 7: The zero-MNS decreases monotonically as RPO increases.
Analysis of the u-number for all pairs of NOS and NOL.

Outcomes 1 and 2 satisfied

for a pair of NOS 120 and NOL 35 were satisfied for all pairs of NOS and NOL in Table 1.
All of the zero-lines under the sameness assumption are shown in Table 3.
According to Tomiyama and Hosono (1999), the outcomes also held under therandomness assumption. All of the zero-lines under this assumption are shown in Table 4. The
table will be used in the last section when the zero-lines under the two assumptions arecompared with. Before turning to there, we must draw attention to some implications of theanalyzed result to the design of a laboratory assignment institution without the secondselection.
3.2 Implications to the Design of an Institution without the Second Selection
A laboratory assignment institution making the u-number zero, that is an institution
without the second selection, can be designed by selecting a pair of MNS and RPO in Table 3
under a given pair of NOS and NOL. There are several pairs of MNS and RPO on the zeroline. Which pair should the designer select from them? In order to get some suggestion toanswer this question, we have to inquire into two things; one is about characteristics of thezero-line and the other is about requirements (or constraints) for MNS and/or RPO in a reallaboratory assignment. Let us consider them in order.
The zero-line has such a basic characteristic that the smaller MNS is, the larger RPO is.
As MNS is smaller, the numbers of the students assigned to laboratories are more equalizedm iyano.doc 2002.12.26 01:39

5/9

tom iyam a

On the side of laboratories,
smaller

MNS

largermore

Equalization

lessOn the side of students,
largerRPO

smaller

wider

Difference

narrowerheavier

Burdenlighter

Figure 1. The characteristics of the zero-line
among them. As RPO is larger, on the other hand, the difference among the students is wider
in the sense that their rankings for laboratories in a matching outcome disperse. In addition,
the burden on the side of students is heavier in the sense that they must linearly rank a numberof laboratories by their preferences. Figure 1 summaries these relationships. It seems that theequalization, differences and burden are useful as criteria in a real situation of laboratory
assignment for the designer to select a pair of MNS and RPO from several pairs on the zeroline.
In a real laboratory assignment, there may or not be some requirements for MNS and/orRPO. This takes part in whether the designer has to select MNS and RPO simultaneously as apair or sequentially in some order. We shall discuss it in detail. To begin with, assume that
there is no requirement for them. To make the u-number zero then, it is desirable to selectsome MNS and some RPO on the zero-line simultaneously. The reason is that any pair on thezero-line is the most efficient of all possible pairs in the sense that RPO is always minimal to
make the u-number zero for a given MNS, and vice versa. Next, assume that there is somerequirement for MNS and/or RPO. A typical example of such a requirement may be that someconstraint is given to the MNS from viewpoint of educational effects. In this case, someparticular MNS is determined first as the MNS adopted in the laboratory assignment
institution. In order to make the u-number zero under the institutional MNS, the designer has
to select the zero-RPO for it. Such zero-RPO can be easily calculated on the zero-line in Table
3. We should notice that this zero-RPO is not necessarily on the zero-line. In Table 2, forexample, if the institutional MNS is 8, then the zero-RPO for it is 2. This pair of MNS andRPO is not on the zero-line.

m iyano.doc 2002.12.26 01:39

6/9

tom iyam a4. DISCUSSION AND CONCLUSIONSIn the previous section, we discussed how to make a decision about the selection ofMNS and RPO when a pair of NOS and NOL was given and fixed. In this final section, weshall discuss some characteristics of the MNS and RPO selection regardless of NOS and NOL,
comparing the simulation results under the sameness assumption in Table 3 with them under
the randomness assumption in Table 4.
Analyzing the simulation results in Table 4, Tomiyama and Hosono (1999) made asummary of the characteristics under the randomness assumption (R) in the following.
(R1) There is a pair of zero-MNS and zero-RPO on the zero-line only when MNS is theminimum (i.e., k=0) and the minimum plus 1 (i.e., k=1).
(R2) When MNS is the minimum, the minimum, maximum and average of RPO are 4,
24 and 8.5 respectively. Since they show that RPO is large, the minimum MNS is
not appropriate to use in a real design of laboratory assignment institution.
(R3) When MNS is the minimum plus 1, the minimum, maximum and average of RPO
are 2, 5 and 3.7 respectively. Since they show that RPO is small, the minimum plus
1 of MNS is reasonable to do in it.
Analyzing the simulation results in Table 3 in a similar manner, we can summarize thecharacteristics of the MNS and RPO selection regardless of NOS and NOL under thesameness assumption (S) as follows.
(S1) There is a pair of zero-MNS and zero-RPO on the zero-line only when MNS is theminimum (i.e., k=0) and the minimum plus 1 (i.e., k=1).
(S2) When MNS is the minimum, the minimum, maximum and average of RPO are 5, 49and 15.6 respectively. Since they show that RPO is large, the minimum MNS is notappropriate to use in a real design of laboratory assignment institution.
(S3) When MNS is the minimum plus 1, the minimum, maximum and average of RPO
are 2, 8 and 5.2 respectively. Since they show that RPO is a little large, theminimum plus 1 of MNS may not be appropriate to do in it.
(S4) When MNS is the minimum plus 2, there is a pair of zero-MNS and zero-RPO on
the zero-line, except that NOS is 20 and NOL is 35 or 40. But these two cases are
not problematic because NOS is larger than NOL for almost every situation in real.
MNS being the minimum plus 2, the minimum, maximum and average of RPO are
1, 5 and 3.4 respectively. Since they show that RPO is small, the minimum plus 2 ofm iyano.doc 2002.12.26 01:39

7/9

tom iyam a

MNS is reasonable to do in it.
From the above discussions, we conclude that the matching procedure proposed byGale and Shapley is applicable enough regardless of NOS and NOL when MNS is theminimum plus 1 under the randomness assumption and when MNS is the minimum plus 2
under the sameness assumption.
It should be noticed that this conclusion holds under the condition that the preference
orderings of students over the set of laboratories are randomly generated from the uniform
distribution. In real situations of laboratory assignment, however, this condition is notnecessarily satisfied. For example, we may observe social phenomena that there are several
groups of students and all the members in every group have some identical preference
ordering. It is not clear whether the conclusion hold even under this situation. This is open tobe solved.

References
Gale, D. and Shapley, L. 1962. "College Admissions and the Stability of Marriage."
American Mathematical Monthly, 69, 9-15.
Roth, A.E. 1982. "The Economics of Matching: Stability and incentives." Mathematics ofOperations Research, 7, 617-628.
Roth, A.E. 1984. "Misrepresentation and Stability in the Marriage Problem." Journal ofEconomic Theory, 34, 383-387.
Roth, A.E. 1985a. "Common and Conflicting Interests in Two-Sided Matching Markets."
European Economic Review, 27, 75-96.
Roth, A.E. 1985b. "Conflict and Coincidence of Interest in Job matching: Some New
Results and Open Questions." Mathematics of Operations Research, 10, 379-389.
Roth, A.E. 1985c. "The College Admissions Problem is not Equivalent to the MarriageProblem." Journal of Economic Theory, 36, 277-288.
Roth, A.E. and Sotomayor, M. 1990. Two-Sided Matching: A Study in Game-TheoreticModeling and Analysis. Econometric Society Monographs, Cambridge: Cambridge
University Press.
Tomiyama, Y. 1992. "Shakaiteki Matchingu Riron to Daigaku Nyuushi Seido (SocialMatching Theory and College Admission Institutions)." Riron to Houhou(Sociological Theory and Methods), Vol.7, No.2, 61-83.
Tomiyama, Y. and Hosono, F. 1999. "Niji Senbatu wo Hituyou to shinai Kenkyuushitum iyano.doc 2002.12.26 01:39

8/9

tom iyam a

Haizoku Seido no Sekkei (Design of a Laboratory Assignment Institution without theSecond Selection)." Riron to Houhou (Sociological Theory and Methods), Vol.14, No.2,
73-88.

m iyano.doc 2002.12.26 01:39

9/9

tom iyam a