<p>An example:<br>
Student type $t_1$ has 10 points to bid based on her GPA. Her favourite courses are A,B,C,D,E.<br>
Student type $t_2$ has 0 points to bid based on his GPA. His favourite courses are F,G,H,I,J.<br>
Student type $t_3$ has 1 point to bid based on her GPA. She ranks the courses alphabetically, A being best, Z being worst. (Or if there are only fifteen courses then O, as that is the 15th letter.) </p>

<p>Assume sixty $t_1$ type, sixty $t_2$ type and one $t_3$ type students. If all types were to subscribe to their favourite kind of courses, then A,B,C,D,E would have sixtyone applicants and hence they would be oversubsribed. F,G,H,I,J would have sixty applicants and would be full. $t_3$ may lose the bidding war in a reasonable equilibrium of round 2: If all type $t_1$ students bid 2 points on each course they will all get their favourite picks while $t_3$ type, who can only bid 1 point will lose out on all picks. Now she can only pick K,L,M,N,O, as F,G,H,I,J are already full. She would have been better off if she had picked F,G,H,I,J in round one, as there she would have one the bidding for at least one of the courses. Thus the 'truth-telling' strategy is not an equilibrium and hence the mechanism is not incentive compatible.</p>

CC BY-SA 3.0
2016-12-03T11:33:33.587Z
2016-12-03T11:33:33.587Z
Giskard
<p>I was thrilled at seeing an interesting bidding system in an academic institutions. This bidding is for registration of courses.
Each student is allocated some points based on her grade point(GPA). So, a student with higher GPA gets more points. 
Each course has a maximum strength of 60 students and a set of say 15 courses is offered.
A student bids higher for the courses that she wants and feels will be oversubscribed.</p>

<p>According to the literature in this subject, I know that this is not an incentive compatible mechanism as the students' bids are considered equivalent to their preferences but a student may bid more for a subject with less utility but which is has higher number of subscribers. 
Also, I feel that this is a kind of first price auction. Whatever bid I propose, it is consumed if I cross the minimum bid at which the subscription closes. </p>

<p>Courses are different and students have different preferences. Each student would bid for any number of courses that she prefers and expects to go oversubscribed. Students' preferences over courses are on academic basis i.e. courses that are popular or taken by some famous faculty. So, student's objective is to get her favorite course.</p>

<p><strong>EDIT :</strong> In first round, the students give a list of 5 courses they wish to enroll in. 
In second round, bidding happens for the oversubscribed courses. So, if I entered course A in round 1 and it got oversubscribed, then in round 2 I will have to bid for it. 
After round 2, if I get the courses that I wanted then it's fine else I will have to choose some other course (for which seats are not completely filled) so that I have 5 courses. </p>

<p>I am not being able to understand in intuitive terms how a student can behave wrong and hide her true preferences while bidding in such a mechanism. 
Please help point out some intuitive examples which violate the incentive compatibility. Thanks in advance. </p>

CC BY-SA 3.0
2016-11-27T08:03:42.153Z
Some aspects of the problem are still a bit unclear. Are the courses on offer homogeneous? Or do different students have different preferences for them? Does each student bid on only one course, or as many as she wants? What's a student's objective here? To get in on as many courses as she can, or to get in on her most favorite course, or to get in on courses that she can expect to maximize her GPA, etc.?
Herr K.
CC BY-SA 3.0
2016-11-27T08:38:42.267Z
Courses are different and students have different preferences. Each student would bid for any number of courses that she prefers and expects to go oversubscribed. Students' preferences over courses are on academic basis i.e. courses that are popular or taken by some famous faculty. So, student's objective is to get her favorite course.
Sub-Optimal
CC BY-SA 3.0
2016-11-27T13:22:04.263Z
Is there a minimum (higher than zero) and/or a maximum (lower than 15) number of courses that a student _should_ eventually be _subscribed_ in, according to the institution's regulations?
Alecos Papadopoulos
CC BY-SA 3.0
2016-11-27T13:28:53.670Z
Yes. A fixed set of 5 courses.
Sub-Optimal
CC BY-SA 3.0
2016-11-27T15:01:59.167Z
If you mean "exactly 5" then there is the following design issue: assume I am a student and I bid only for five courses. It so happens that I enter only in four of them given the bidding. But I _must_ be enrolled in five. How does the institution resolve this?
Alecos Papadopoulos
CC BY-SA 3.0
2016-11-27T15:50:54.617Z
Not all courses will oversubscribed. In this case, the student will have to choose one of the courses which are not oversubscribed. Actually the rules are many. Should I mention all rules in the question itself ?
Sub-Optimal
CC BY-SA 3.0
2016-11-29T00:32:43.370Z
I would say yes because otherwise I don't see how we could provide relevant answers
Alecos Papadopoulos
CC BY-SA 3.0
2016-11-29T09:55:38.007Z
Sorry for that. I have updated the question itself to include the details.
Sub-Optimal
CC BY-SA 3.0
2016-12-02T07:05:15.870Z
If a class becomes oversubscribed in round 1, how can people bid on it in round 2?
Kitsune Cavalry
CC BY-SA 3.0
2016-12-02T11:27:45.283Z
I added that in the first round students just give a list of their preferred courses. So, for example I list courses A,B,C,D,E and all students give their preferences. So, after first round for example more than 60 people listed course A. Then course A becomes oversubscribed and now in second round all students will have to bid for it.
Sub-Optimal
<game-theory><mechanism-design><bayesian-game>
Checking incentive compatibility of a mechanism
Sub-Optimal
# Checking incentive compatibility of a mechanism

(Asked by: username_0 on 2016-07-04)

I was thrilled at seeing an interesting bidding system in an academic institutions. This bidding is for registration of courses.
Each student is allocated some points based on her grade point(GPA). So, a student with higher GPA gets more points.
Each course has a maximum strength of 60 students and a set of say 15 courses is offered.
A student bids higher for the courses that she wants and feels will be oversubscribed.

According to the literature in this subject, I know that this is not an incentive compatible mechanism as the students' bids are considered equivalent to their preferences but a student may bid more for a subject with less utility but which is has higher number of subscribers.
Also, I feel that this is a kind of first price auction. Whatever bid I propose, it is consumed if I cross the minimum bid at which the subscription closes.

Courses are different and students have different preferences. Each student would bid for any number of courses that she prefers and expects to go oversubscribed. Students' preferences over courses are on academic basis i.e. courses that are popular or taken by some famous faculty. So, student's objective is to get her favorite course.

**EDIT :** In first round, the students give a list of 5 courses they wish to enroll in.
In second round, bidding happens for the oversubscribed courses. So, if I entered course A in round 1 and it got oversubscribed, then in round 2 I will have to bid for it.
After round 2, if I get the courses that I wanted then it's fine else I will have to choose some other course (for which seats are not completely filled) so that I have 5 courses.

I am not being able to understand in intuitive terms how a student can behave wrong and hide her true preferences while bidding in such a mechanism.
Please help point out some intuitive examples which violate the incentive compatibility. Thanks in advance.

**Tags:** game-theory, mechanism-design, bayesian-game
> **Comments:**
> **username_1**: Some aspects of the problem are still a bit unclear. Are the courses on offer homogeneous? Or do different students have different preferences for them? Does each student bid on only one course, or as many as she wants? What's a student's objective here? To get in on as many courses as she can, or to get in on her most favorite course, or to get in on courses that she can expect to maximize her GPA, etc.?  
> **username_0**: Courses are different and students have different preferences. Each student would bid for any number of courses that she prefers and expects to go oversubscribed. Students' preferences over courses are on academic basis i.e. courses that are popular or taken by some famous faculty. So, student's objective is to get her favorite course.  
> **username_2**: Is there a minimum (higher than zero) and/or a maximum (lower than 15) number of courses that a student _should_ eventually be _subscribed_ in, according to the institution's regulations?  
> **username_0**: Yes. A fixed set of 5 courses.  
> **username_2**: If you mean "exactly 5" then there is the following design issue: assume I am a student and I bid only for five courses. It so happens that I enter only in four of them given the bidding. But I _must_ be enrolled in five. How does the institution resolve this?  
> **username_0**: Not all courses will oversubscribed. In this case, the student will have to choose one of the courses which are not oversubscribed. Actually the rules are many. Should I mention all rules in the question itself ?  
> **username_2**: I would say yes because otherwise I don't see how we could provide relevant answers  
> **username_0**: Sorry for that. I have updated the question itself to include the details.  
> **username_3**: If a class becomes oversubscribed in round 1, how can people bid on it in round 2?  
> **username_0**: I added that in the first round students just give a list of their preferred courses. So, for example I list courses A,B,C,D,E and all students give their preferences. So, after first round for example more than 60 people listed course A. Then course A becomes oversubscribed and now in second round all students will have to bid for it.  

---

## 1 answers

### Answer by username_4 on 2016-12-03. Score: 1 | Accepted answer

An example:  
Student type $t\_1$ has 10 points to bid based on her GPA. Her favourite courses are A,B,C,D,E.  
Student type $t\_2$ has 0 points to bid based on his GPA. His favourite courses are F,G,H,I,J.  
Student type $t\_3$ has 1 point to bid based on her GPA. She ranks the courses alphabetically, A being best, Z being worst. (Or if there are only fifteen courses then O, as that is the 15th letter.)

Assume sixty $t\_1$ type, sixty $t\_2$ type and one $t\_3$ type students. If all types were to subscribe to their favourite kind of courses, then A,B,C,D,E would have sixtyone applicants and hence they would be oversubsribed. F,G,H,I,J would have sixty applicants and would be full. $t\_3$ may lose the bidding war in a reasonable equilibrium of round 2: If all type $t\_1$ students bid 2 points on each course they will all get their favourite picks while $t\_3$ type, who can only bid 1 point will lose out on all picks. Now she can only pick K,L,M,N,O, as F,G,H,I,J are already full. She would have been better off if she had picked F,G,H,I,J in round one, as there she would have one the bidding for at least one of the courses. Thus the 'truth-telling' strategy is not an equilibrium and hence the mechanism is not incentive compatible.


---

