# Random Draft Allocation: Nash Equilibrium? [closed]

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

(s1,s2,s3);(s1,s3,s2);(s2,s1,s3);(s3,s1,s2);(s3,s2,s1);(s2,s3,s1)

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.

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