I would like to find the Nash equilibrium of the following allocation problem.

There are 3 courses and 3 students. Each student has to take 2 courses, and each course has a capacity of 2 seats. Students have the following values for each of the 3 courses with strict preferences. Let student be s where s1= student 1, and course be c where c1=course 1

Ranking c1, c2, c3 respectively in values,

s1: 12, 10, 6

s2: 6, 10, 8

s3: 7, 10, 5

Students are allocated to courses in the following manner.

  1. First, each student submits their course preferences (eg. c2>c1>c3).

  2. Then, a random order of the 3 students are generated. All combinations are equally likely.

  3. Suppose the order generated is s1,s2,s3. the first-ranked student gets to pick 1 course first, according to his submitted preferences. s2 picks 1 course next and followed by s3.

  4. After every student has picked a course, the generated order is reversed, so s3 now gets to pick his 2nd course first, followed by s2, and s1.

  5. Process ends after all course spaces are full.

  6. In the event it is a student's turn to pick a course but it is full, the student will be allocated his next preferred course.

Here's an example: Student 1 decides what preference to submit. If he assumes that the other 2 students will tell the truth, and he submits preference $c1>c2>c3$ according to his true values, then his expected utility is

$EU = \frac{1}{6}(12+6) +\frac{1}{6}(12+6)+\frac{1}{6}(12+6)+\frac{1}{6}(12+6)+\frac{1}{6}(12+6)+\frac{1}{6}(12+6)=18$

given that the student order generated are equally likely


However, if student 1 lies about his preferences, and submits $c2>c1>c3$ instead, his expected utility is

$EU = \frac{1}{6}(10+12) +\frac{1}{6}(10+6)+\frac{1}{6}(10+12)+\frac{1}{6}(10+12)+\frac{1}{6}(12+6)+\frac{1}{6}(12+6)=19\frac{2}{3}>18$, thus he has an incentive to lie.

This is student 1's best response given that s2 and s3 tell the truth. But if s2 and s3 decide to lie also, knowing that s1 would lie as well, how exactly can we find the Nash equilibrium? It seems very tedious to iterate all the possible scenarios and I hope there is an elegant way to find the Nash equilibrium.

  • $\begingroup$ So far this seems like a homework problem with little effort shown... $\endgroup$ – Giskard Nov 11 '17 at 9:35

Each student can report 6 preference orders. However, eliminating strictly dominated strategies (no need to calculate actual expected payoffs, you can use basic logic based on their real preference orders and the availability of places) reduces this to 2 orders per student. A second iteration of elimination reduces s2's strategy set to a single order. The third iteration reduces s1's and s3's strategy set to a single order as well. These reported preference orders constitute the Nash-equilibrium.

  • $\begingroup$ thanks for your response, can you please show how do you eliminate and reduce the 6 possible preference orders to just 2 per student? $\endgroup$ – advantage Nov 15 '17 at 13:53
  • $\begingroup$ @advantage By eliminating strictly dominated strategies. $\endgroup$ – Giskard Nov 15 '17 at 13:58
  • $\begingroup$ sorry Im new at this could you walk me through how you use their real preference orders to eliminate strictly dominated strategies $\endgroup$ – advantage Nov 17 '17 at 0:20
  • $\begingroup$ @advantage Sorry, that is not what this site is for. Read our policy on homework. $\endgroup$ – Giskard Nov 17 '17 at 7:47

Not the answer you're looking for? Browse other questions tagged or ask your own question.