So, it's been awhile since my last post.
What intrigued me to write in here again was my lecturer. My taxation seminar lecturer, Mr. Riko Riandoko, has a very interesting grading method. (He's an awesome guy.) Basically, Mr. Riko gave us task to each write an essay every week. However, the grading system was like this (with some adjustments to make the assumption simpler):
- Everyone submits the essays to one designated student.
- That student removes the writers' names from every essay, leaving only the title. The essays then are put online on a cloud drive.
- Everyone then read and ranks the essays from the best to the worst EXCEPT for her own essay. (Thus A ranked B, C, D's essays; B ranked A, C, and D's, and so forth.)
- To make it simple, the ranking used scoring system, with the best essay given highest score, 2nd best given the 2nd highest score, and so forth. So if there are 10 essays, one would give the best essay 9, the 2nd best 8, and so forth. One must give her own essay a 0 score, due to the above rule. The winner is the one with most total score.
This system makes me think of some questions.
a) Assuming full honesty (no coalition in which the members give the highest score to members of that coalition, and no one give her own essay score > 0) what is the probability of one winning?
b) Is such coalition possible?
-------------
The first ones is not so easy to calculate. First, the possible combination of scoring (or the probability space) from a student's perspective with regard to her own essay is (n-1)^(n-1), with n as the total students in the class. This configuration got large the more the students are. For instance, if there are 3 students, there are 2^2 or 4 possible scores from A's perspective (2, 3, 3, and 4):
2 if both B and C give A each 1 score;
3 if either B gives 1 and C gives 2, or the reverse;
4 if both B and C give A score of 2.
If there are 4 students, the possible configuration of scores becomes 27. If there are 5 students, 64. 6 students? 125.*)
This makes calculation of exact probability get increasingly difficult in scale. Remember that it is basically similar to the probability of getting k in n-run. Even for binary outcomes (coin flip, "success"/"failure"), the equation is ugly, moreover the calculation. The equation is:
And that is only for two kinds of outcome. But Mr. Riko's essay grading have (n-1) possible outcomes. I'd rather pass this one over.
However! one can calculate the average expected score of her own essay. Since these scores are independent and identically distributed random variables, we can calculate the expected score E(s) using mid range method. This estimation is robust, as the n of students got large enough the expected mean will follow the central limit theorem.
The highest possible score for A is (n-1)^2, that is if everyone else votes A's essay with highest score. The lowest possible score for A is (n-1), in which everyone else thinks A's essay is the worst. Using midrange, it is easy to see that the expected score for A is:
Interestingly, this is also the score where there is no winner! Recall that the expression n(n-1)/2 is formula for 1+2+3+...+(n-1). This score is what everyone gets when there is Condorcet voting paradox. Condorcet voting paradox happens when the situation is as follows:
A voted B > C > D
B voted C > D > A
C voted D > A > B
D voted A > B > C
So everyone basically gets voted highest exactly once, 2nd highest exactly once, and so forth until she also gets the lowest score exactly once. Therefore, for the example above, A gets 1, 2, and 3, with the total score of 6. But so do B, C, D! They all get 6. In which no one wins (or everyone wins, if you're that "glass half full" guy.) What a bummer.
-------------
Now, the second question. Is it possible to form a coalition with some friends so that at least one of the members wins, or at least guaranteed above average score? It is interesting to answer that in game theory perspective.
My theorem is that, yes, such coalition is possible. Such coalition has to adhere to some rules, however.
1) Members of coalition must vote cyclically among themselves. If a coalition exists between A, B, and C, A must vote B > C; B must vote C > A; and C must vote A > B.
2) There must exist at least someone who is outside the coalition, a.k.a. that forever alone guy who doesn't have friend.
My theorem: there exists coalition c with members of (k+1) so that E(c) > E(s). In other words, maximizing the possibility of getting the most score. Such coalition must have k that satisfies the equation:
The left side is derived from the total score from Condorcet voting amongst its members, plus the additional expected scores from non-members.
There exist finitely many solutions for this, except where k = 0 (no coalition) and k = n-1 (i.e. everyone is in the coalition, which is basically going back to the Condorcet voting paradox above). However I can't prove the generality of this theorem. In other words, I don't know if this always applies in general. My math is rusty.
If, however, this is the case, then the best strategy for a rational agent is indeed to form a coalition. A student will have better chance of winning if she makes a deal with her friends.
I don't know if anyone has put some thoughts to this type of game theory. If I recall correctly, most of social choice literature dealt with voters that are clearly distinct from the candidates. For example, election, in which Marquis de Condorcet, Kenneth Arrow, Allan Gibbard, and Amartya Sen extensively concerned themselves with. Or maybe Keynesian beauty contest-like situation.
In Mr. Riko's grading case, all voters are also all the candidates, except that they can't vote for themselves – creating the incentive to cooperate with opponents. Another difference from election is that a vote does not necessarily correspond to a score of 1, but ∈ of {1, 2, 3, ..., n-1}.
All in all, this got me spending much time in warkop, looking at its walls like a dumb ass.
-------------
Post script:
*) The all possible ordering, class-wide, is even nastier as the n of students gets increasingly large. It is the (n-1) permutation of (n-1) elements, to the power of n. In other words, it is.
(n-1)!^(n)
Even for 3 students, the possible class score ordering is large. Take a look:
0, 1, 2 0, 2, 1
1, 0, 2 1, 0, 2
1, 2, 0 1, 2, 0
0, 1, 2 0, 2, 1
2, 0, 1 2, 0, 1
1, 2, 0 1, 2, 0
0, 1, 2 0, 2, 1
1, 0, 2 1, 0, 2
2, 1, 0 2, 1, 0
0, 1, 2 0, 2, 1
2, 0, 1 2, 0, 1
2, 1, 0 2, 1, 0
For a class with 4 students? It's 6^4 possible ordering, or exactly 1296. I'd rather not imagine how big it is for a class with 39 students like mine.
What intrigued me to write in here again was my lecturer. My taxation seminar lecturer, Mr. Riko Riandoko, has a very interesting grading method. (He's an awesome guy.) Basically, Mr. Riko gave us task to each write an essay every week. However, the grading system was like this (with some adjustments to make the assumption simpler):
- Everyone submits the essays to one designated student.
- That student removes the writers' names from every essay, leaving only the title. The essays then are put online on a cloud drive.
- Everyone then read and ranks the essays from the best to the worst EXCEPT for her own essay. (Thus A ranked B, C, D's essays; B ranked A, C, and D's, and so forth.)
- To make it simple, the ranking used scoring system, with the best essay given highest score, 2nd best given the 2nd highest score, and so forth. So if there are 10 essays, one would give the best essay 9, the 2nd best 8, and so forth. One must give her own essay a 0 score, due to the above rule. The winner is the one with most total score.
This system makes me think of some questions.
a) Assuming full honesty (no coalition in which the members give the highest score to members of that coalition, and no one give her own essay score > 0) what is the probability of one winning?
b) Is such coalition possible?
-------------
The first ones is not so easy to calculate. First, the possible combination of scoring (or the probability space) from a student's perspective with regard to her own essay is (n-1)^(n-1), with n as the total students in the class. This configuration got large the more the students are. For instance, if there are 3 students, there are 2^2 or 4 possible scores from A's perspective (2, 3, 3, and 4):
2 if both B and C give A each 1 score;
3 if either B gives 1 and C gives 2, or the reverse;
4 if both B and C give A score of 2.
If there are 4 students, the possible configuration of scores becomes 27. If there are 5 students, 64. 6 students? 125.*)
This makes calculation of exact probability get increasingly difficult in scale. Remember that it is basically similar to the probability of getting k in n-run. Even for binary outcomes (coin flip, "success"/"failure"), the equation is ugly, moreover the calculation. The equation is:
And that is only for two kinds of outcome. But Mr. Riko's essay grading have (n-1) possible outcomes. I'd rather pass this one over.
However! one can calculate the average expected score of her own essay. Since these scores are independent and identically distributed random variables, we can calculate the expected score E(s) using mid range method. This estimation is robust, as the n of students got large enough the expected mean will follow the central limit theorem.
The highest possible score for A is (n-1)^2, that is if everyone else votes A's essay with highest score. The lowest possible score for A is (n-1), in which everyone else thinks A's essay is the worst. Using midrange, it is easy to see that the expected score for A is:
Interestingly, this is also the score where there is no winner! Recall that the expression n(n-1)/2 is formula for 1+2+3+...+(n-1). This score is what everyone gets when there is Condorcet voting paradox. Condorcet voting paradox happens when the situation is as follows:
A voted B > C > D
B voted C > D > A
C voted D > A > B
D voted A > B > C
So everyone basically gets voted highest exactly once, 2nd highest exactly once, and so forth until she also gets the lowest score exactly once. Therefore, for the example above, A gets 1, 2, and 3, with the total score of 6. But so do B, C, D! They all get 6. In which no one wins (or everyone wins, if you're that "glass half full" guy.) What a bummer.
-------------
Now, the second question. Is it possible to form a coalition with some friends so that at least one of the members wins, or at least guaranteed above average score? It is interesting to answer that in game theory perspective.
My theorem is that, yes, such coalition is possible. Such coalition has to adhere to some rules, however.
1) Members of coalition must vote cyclically among themselves. If a coalition exists between A, B, and C, A must vote B > C; B must vote C > A; and C must vote A > B.
2) There must exist at least someone who is outside the coalition, a.k.a. that forever alone guy who doesn't have friend.
My theorem: there exists coalition c with members of (k+1) so that E(c) > E(s). In other words, maximizing the possibility of getting the most score. Such coalition must have k that satisfies the equation:
The left side is derived from the total score from Condorcet voting amongst its members, plus the additional expected scores from non-members.
There exist finitely many solutions for this, except where k = 0 (no coalition) and k = n-1 (i.e. everyone is in the coalition, which is basically going back to the Condorcet voting paradox above). However I can't prove the generality of this theorem. In other words, I don't know if this always applies in general. My math is rusty.
If, however, this is the case, then the best strategy for a rational agent is indeed to form a coalition. A student will have better chance of winning if she makes a deal with her friends.
I don't know if anyone has put some thoughts to this type of game theory. If I recall correctly, most of social choice literature dealt with voters that are clearly distinct from the candidates. For example, election, in which Marquis de Condorcet, Kenneth Arrow, Allan Gibbard, and Amartya Sen extensively concerned themselves with. Or maybe Keynesian beauty contest-like situation.
In Mr. Riko's grading case, all voters are also all the candidates, except that they can't vote for themselves – creating the incentive to cooperate with opponents. Another difference from election is that a vote does not necessarily correspond to a score of 1, but ∈ of {1, 2, 3, ..., n-1}.
All in all, this got me spending much time in warkop, looking at its walls like a dumb ass.
-------------
Post script:
*) The all possible ordering, class-wide, is even nastier as the n of students gets increasingly large. It is the (n-1) permutation of (n-1) elements, to the power of n. In other words, it is.
(n-1)!^(n)
Even for 3 students, the possible class score ordering is large. Take a look:
0, 1, 2 0, 2, 1
1, 0, 2 1, 0, 2
1, 2, 0 1, 2, 0
0, 1, 2 0, 2, 1
2, 0, 1 2, 0, 1
1, 2, 0 1, 2, 0
0, 1, 2 0, 2, 1
1, 0, 2 1, 0, 2
2, 1, 0 2, 1, 0
0, 1, 2 0, 2, 1
2, 0, 1 2, 0, 1
2, 1, 0 2, 1, 0
For a class with 4 students? It's 6^4 possible ordering, or exactly 1296. I'd rather not imagine how big it is for a class with 39 students like mine.
So if there are 39 students in my class, I'm gonna read 38 essays every f--king week? And give score to each of them? You must be kiddin'~
ReplyDeleteAnw, it's interesting how you use "her" to refer to "someone" or other indefinite singular pronouns. In my case, I always use "his". Idk, taste.
Originally, yes. Read all, grade all. But then the rule changed, so that now we must only vote for the top 10. Still gotta read all, though. Modelling this rule however is difficult so I just stayed with the original~
Delete