THE REGISTRATION GAME

Craig Haile

Our college instituted the requirement in 1998 that any incoming student (freshman or transfer) would be required to take an interdisciplinary “capstone” course as the culminating experience of their general education program. The idea intrigued me and so I developed a course in game theory. This course touches aspects from political science, economics, history, and social science. As we shall see, it is also relevant to the familiar process of course registration.

I was pleased and a little bit surprised when 25 people preregistered for the course the first time it was offered in Winter 2000. I wanted it to run so I could get some of the “bugs” worked out, but expected a much smaller group as only a handful of transfer students were both eligible and required to take the course. As registration day ended I inquired to see how many students I would have in my class. Imagine how surprised and dismayed I was when I realized only 3 people had actually registered for the course! To determine what happened, I began to look at the preregistration process itself. The college had just instituted a new system in which students could preregister for a full load of classes (up to 18 hours) plus two “alternate” courses. The rationale behind this was that in the past any student who wished to make a change in schedule on registration day (due to a class being full, etc.) was required to get their advisor’s signature, which was a headache for all involved. Under the new system as long as the student registered for one of their choices or an alternate, they needed no signature. The problem was that under our present computer system there was no way for the preregistration numbers given to the faculty to make a distinction between “regular” and “alternate” courses. Add this to the fact that many students, wishing to have as much flexibility as possible, would sign up for 24 total hours when they only planned on taking 12 or 15, and you can see that the preregistration numbers were very misleading.

Let’s consider modeling this situation as a 2 × 2 matrix game. The “players” are the college and the students. They each have two choices of strategy. (We will assume all students will employ the same strategy.) The college can let preregistration numbers include both regular and alternate courses and offer classes based on the combined numbers. This is assuming that the students will truly need and use those alternate courses. We will call this strategy C for cooperative, since the students would prefer the college employ this strategy. The college could also decide to only include regular classes in the preregistration numbers and offer a smaller range and depth of classes based on these figures. This strategy would come from believing the students are padding their preregistration numbers with courses they don’t intend to take (for instance, signing up for 18 regular hours and 6 alternates when they only plan on taking 12 hours). We will call this strategy N for non–cooperative. The students could indeed decide to pad their registration numbers (N) to give themselves the maximum possible flexibility in choosing their courses, or they could only put down the courses that they actually planned on taking (C). The following 2 × 2 matrix shows the possible outcomes.

Students

N  C
College N  (N,N) (N,C)
C  (C,N)  (C,C)

Now let us consider how each player in the game views these outcomes.

(N,C). This is the least desirable situation for the students, as they have no flexibility and few classes to choose from. Also, it may not be desirable for the college since they may not offer enough courses to meet demand and could have to turn students away or add classes at the last minute.

(N,N). This is a better situation for the college in that they guessed what the students were doing and did not offer too many courses, but probably offered enough since the students had signed up for more regular hours than they really intended to take. It is not perfect for the college in that there is still some guesswork in what classes to offer since they do not know which are really wanted and which are not. It is also better for the students than (N,C) since they have more flexibility in what courses they may register for (if they are available).

(C,C). This is the best situation for the college in that they are assured of offering enough courses to meet demand and will likely not have an excess of courses since the students were honest in their preregistration. It is a good situation for the students since there should be enough courses available to get their preferences, but there is little room for flexibility.

(C,N). This situation is most desirable for students, since there should be a plethora of courses to choose from and great flexibility in what they may register for. The college does not like this situation since they had to plan for adjuncts or increased loads to meet a demand that in reality did not exist.

\underline{Example}. Suppose 40 students have preregistered for a class, either as a regular or alternate.

For the outcome (N,C) this would most likely mean that all 40 students would have signed up for this as a regular class and really want to take it. However, the college would assume that at least some of these 40 students signed up for more regular hours than they really intend to take, and therefore do not actually plan to register for the course. They would therefore only offer one section of the course and would have to turn 10 people away on registration day. These 10 would then have to chase down their advisors and scramble to find a less desirable course, if they can.

For the outcome (N,N) the college would again offer only one section of the course, but now it is likely that some of the 40 students signed up for the course as an alternate or as a regular course they didn’t really intend to take. There is still a chance that some students might have trouble finding a class, but much less likely than in the previous situation.

For (C,C) the college would again offer two sections, and they would get an enrollment of about 20 each. Everyone on both sides would likely be pleased by this outcome, although the students would have preferred the greater flexibility in their classes.

For (C,N) the college would offer two sections in order to accommodate all 40 possible students. They would also offer more sections in every other class under this strategy, thus a student who would really rather take another course would have that opportunity. Thus, it is likely that one section would have been sufficient to meet the demand.

Having considered all this we now attempt to rank the outcomes from each player’s perspective. Since there are four possible outcomes, we will rank each player’s preference on a scale of 1 to 4, 1 being the lowest and 4 being the highest. The outcomes can then be denoted by an ordered pair with the first element the ranking of the college and the second element the student ranking. This leads to the 2 × 2 matrix with outcomes as

Students

N  C
College N  (3,2)  (2,1)
C  (1,4)  (4,3)

In analyzing this game there arise some natural questions. Is it clear what strategy each player should employ? Given an outcome, would either or both players want to change their strategy? Is there an expected outcome to the game? To answer these questions we make a few definitions.

\underline{Definition 1}. A strategy for a given player is said to be dominant for that player if it yields a better outcome (compared to the players other choice of strategy) no matter what strategy the opposing player employs.

\underline{Definition 2}. An outcome is said to be a Nash equilibrium if neither player would gain by unilaterally changing their strategy.

\underline{Definition 3}. An outcome is expected if it would result from both players employing rational strategies.

Here “rational strategies” are used to mean either a dominant strategy or, if a dominant strategy does not exist, the strategy that would result from the expectation that the opposing player would employ their dominant strategy.

These definitions lead us to the following propositions.

\underline{Proposition 1}. The college has no dominant strategy.

\underline{Proof}. If the students choose C, the college would be better off choosing strategy C (4 to 2 over N). However, if the students choose N, the college would be better off choosing N (3 to 1 over C).

\underline{Proposition 2}. The students’ dominant strategy is N.

\underline{Proof}. If the college chooses N, the students would have outcome 2 with C and 3 with N. If the college chooses C, the students would have outcome 3 with C and 4 with N. Therefore, in either case N is better.

\underline{Proposition 3}. The outcome (3,2) is a Nash equilibrium.

\underline{Proof}. At the (3,2) position, we note that a unilateral change by the college would change their outcome from 3 to 1, and a change by the students would send them from 2 to 1. Obviously, neither of these changes would be preferable.

\underline{Remark 1}. There is no other Nash equilibrium. First, a unilateral change from (2,1) by either player would be preferable to that player. Secondly, the students would want to change from the (4,3) position, and lastly the college would want to change from the (1,4) position.

\underline{Proposition 4}. The outcome (3,2) is the expected outcome.

\underline{Proof}. Given that the students dominant strategy is N, the college would be compelled to employ the strategy N in order to maximize their outcome. This leads to (3,2).

\underline{Remark 2}. Although it is tempting from this example to equate the Nash equilibrium outcome with the expected outcome, this is not always the case. For an example, consider the game of “chicken” discussed in [1].

Looking at what happened in our preregistration last semester, it is pretty clear that we have been in the (1,4) position. Many advisors were encouraging their students to sign up for as many courses as allowed, both to give them maximum flexibility and to keep them from coming back needing a new signature. The college was taking all the courses (regular and alternate) and including them in the preregistration numbers. The result in many cases was that many classes that offered multiple sections should have only offered one and other courses (including my course) were questionable as to whether they should run at all. Now, from a strategic standpoint, what should happen next? Certainly the students are not changing their strategy since it is dominant. However, the college would be expected to change its strategy to N, which would lead to the (3,2) outcome. This is exactly what is happening in the preregistration for the fall semester. The college is including only regular courses (no alternates) in the preregistration numbers and many departments are wary of offering too many sections considering what happened previously.

Looking ahead, there is no reason to expect that either side will change their strategies since (3,2) is a Nash equilibrium. A reasonable person might object and say that the outcome (4,3) is more beneficial to both sides and hence, both players would change strategy to move to that outcome. However, it is unlikely that this would occur since it would require a mutual (not unilateral) change in strategies, and thus there would have to be significant communication, cooperation, and trust between both players. Moreover, if we did move to this position it would be very unstable, since the students would be tempted to change strategy and thus move to the (1,4) outcome. Likewise the college would be aware of this temptation and might consider changing their strategy pre–emptively to protect themselves from the (1,4) outcome. Thus, the expected outcome is not the mutually beneficial outcome. That somewhat paradoxical result is not uncommon in game theory, and it is part of what makes the subject interesting and appealing to novices.

\underline{Reference}

1. A. D. Taylor, Mathematics and Politics: Strategy, Voting, Power, and Proof, Springer–Verlag Inc., New York, 1995.

Craig Haile Department of Mathematics College of the Ozarks Point Lookout, MO 65726 email: haile@cofo.edu