Author |
Topic: Checkbox on Exam (Read 914 times) |
|
Foolish
Newbie
Posts: 15
|
 |
Checkbox on Exam
« on: Nov 29th, 2004, 11:58am » |
 Quote  Modify
|
I haven't seen this puzzle, and am not sure if this is where it belongs, but someone will know and possibly yell at me if it is out of place, so i expect I will know before long...
The problem:
A professor gives an exam, and at the end of the exam there is a checkbox with the following rules:
1. If you leave this checkbox blank, your score will be unaffected.
2. If you check the box, and more than (or exactly) half the class checks the box, you will lose 10% of your score.
3. If you check the box, and less than half the class checks the box, you will add 10% to your score.
Assuming that it is the goal of everyone in the class to maximize their score, but knowing nothing else about them, which do you choose?
Is there some way to represent this problem statistically/probabalistically, or is it a purely psycolgical question? My friends father used to ask my friend and I these types of questions, and I don't think we ever resolved it...
|
| « Last Edit: Nov 30th, 2004, 1:41pm by Foolish » |
 IP Logged |
|
|
|
ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
|
Re: Checkbox on Exam
« Reply #1 on: Nov 29th, 2004, 8:37pm » |
Quote Modify
|
This is a similar situation to a Prisoner's Dilemma.
|
| « Last Edit: Nov 29th, 2004, 8:44pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Foolish
Newbie
Posts: 15
|
|
Re: Checkbox on Exam
« Reply #2 on: Nov 29th, 2004, 10:34pm » |
Quote Modify
|
on Nov 29th, 2004, 8:37pm, THUDandBLUNDER wrote:
Hmm... Cooperation versus competition, game theory...
A certain *me* is out of his league... Best be sticking with the "it's socialogical" solution ;)
|
|
IP Logged |
|
|
|
ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Checkbox on Exam
« Reply #3 on: Nov 30th, 2004, 2:02am » |
Quote Modify
|
Quote:| A certain *me* is out of his league... |
|
Here's a bit of simple analysis:
If all the other students toss a fair coin to decide to check or not, then one's expected gain from checking the box is negative. Hence we should not check the box and be content with zero expected gain. But if most students reason thus and don't check the box, it then becomes advantageous to check the box. But then if most students check the box, it becomes advantageous not to, etc.
|
| « Last Edit: Nov 30th, 2004, 10:23pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Checkbox on Exam
« Reply #4 on: Nov 30th, 2004, 11:17am » |
Quote Modify
|
on Nov 29th, 2004, 11:58am, Foolish wrote:| Assuming that it is the goal of everyone in the class to maximize their score, but knowing nothing else about them, which do you choose? |
|
The optimal (cooperative) strategy for all participating in this exam game is to toss a slightly biased coin such that the box is ticked with probability 1/2 - [epsilon], and left blank with probability 1/2 + [epsilon]. The value of [epsilon] depends on the size of the group being examined ([epsilon] vanishing when the groupsize grows to infinity). This will generate an expected increase in score close to 10% for almost 50% of the group. Hence, an expected increase in score slightly less than 5% for all participating in this strategy.
However, such a cooperative strategy will only originate when the participants in this 'game' communicate in some way. Such communication can originate - for instance - when this 'game' is played repetitively with the same group of players.
In the strict absence of any communication (as implied in the wording of the riddle) for the given game, rational players are likely to be caught up in a Nash equilibrium with non-optimal expected gains for all of them (e.g. with participants cheating when the coin tells them not to check the box).
|
| « Last Edit: Dec 1st, 2004, 2:25pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Foolish
Newbie
Posts: 15
|
|
Re: Checkbox on Exam
« Reply #5 on: Nov 30th, 2004, 1:42pm » |
Quote Modify
|
Edited to say that exactly half falls into the -10% category, and now I am off to google/mathworld to look up Nash Equilibriums ;)
|
|
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Checkbox on Exam
« Reply #6 on: Nov 30th, 2004, 6:27pm » |
Quote Modify
|
If your score without checking the box would have been s, and you choose to check the box with probability p, there are three possibilities:
1) With probability (1-p) your score is s
2) With probability p*r you check the box and your score is 0.9*s
3) With probability p*(1-r) you check the box and your score is 1.1*s
r is the probability that too many people in the rest of the class check boxes:
r= [sum] pn*(1-p)M-1-n*(M-1)!/n!/(M-1-n)!
The sum is on n from int((M+1)/2)-1 to M-1, where M is the number of students in the class.
Your expected score is (1-p)*s + p*r*0.9*s + p*(1-r)*1.1*s
Find the p which maximizes your expected score. For a class of 21 students, p=0.319.
This assumes everyone in the class uses the same strategy. With everyone in the same situation, shouldn't the best strategy be the same for everyone?
If you are certain that you missed every question on the exam, it can't hurt to check the box. Maybe you can bring down the class average enough that 0 becomes a passing grade.
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Checkbox on Exam
« Reply #7 on: Dec 1st, 2004, 1:20pm » |
Quote Modify
|
on Nov 30th, 2004, 6:27pm, SWF wrote:<..> you choose to check the box with probability p
<..>
Find the p which maximizes your expected score. For a class of 21 students, p=0.319.
This assumes everyone in the class uses the same strategy. With everyone in the same situation, shouldn't the best strategy be the same for everyone? <..> |
|
Yes, the best strategy is the same for all participants. However, as indicated in my post, the strategy defined in your post is NOT optimal assuming rational (selfish / non-cooperative) strategies from all players.
What your analysis misses is that the resulting 'optimal' strategy is not robust against selfish behavior:
what if all but one (N-1) participants adhere to the 'optimal' strategy of ticking the box with probability 1/2 - [epsilon] (as derived in your post, for the number of players N = 21 you find [epsilon] = 0.181), and one rogue participant follows the alternative strategy of always ticking the box?
Without doing the actual calculation for all N, I claim that for large enough N the rogue player will benefit (have a better expectation for the relative score boost) at the expense of the other N-1 players.
But... if it is advantageous for one player to deviate from the 'optimal' strategy, it will be tempting for all players to do so. So the 'optimal' strategy will NOT be followed by any of the players (again assuming rational behaviour!).
What results is a situation that game theorists refer to as a Nash equilibrium (for obvious reasons in this context one avoids the term 'optimum strategy'). In fully symmetrical games (all players in exactly the same situation) the Nash equilibrium refers to a strategy that has the property that when all players adhere to this strategy, it is not advantageous for a single player to deviate from this strategy (assuming the others stick to the Nash strategy). A generic result in game theory (as derived by John Nash) states that basically all games (that is all games that can be represented in some very generic form) have at least one Nash equilibrium. That also holds for the N-person game described in this thread.
|
| « Last Edit: Dec 1st, 2004, 1:32pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Checkbox on Exam
« Reply #8 on: Dec 1st, 2004, 3:09pm » |
Quote Modify
|
OK, to demonstrate the difference between what is the optimal cooperative strategy (that can originates when the players can communicate, create an atmosphere of mutual trust, and agree startegies), and what constitutes the Nash equilibrium (that originates when the players can not communicate and all behave purely rational), let's consider a group of size N=3 players.
Consider the generic one-person strategy to tick the box with probability p, and to leave it blank with probability q = 1-p.
If the two other players follow this strategy, the third player will have an expected gain of 10(2q2-1) percent of the score if he/she ticks the box, and an expected gain of 0 percent if he she does not tick the box. If he/she also follows the same probabilistic strategy of the two others, the expected gain for all three of them will be 10(1-q)(2q2-1) percent increase of their individual scores. For q = (2+[sqrt]10)/6 [approx] 0.8604 (p [approx] 0.1396) this expected gain reaches a maximum of 0.671%. This constitutes the optimum gain that is reached when all three players stick to the optimal cooperative strategy.
However, if the third player deviates from the optimal cooperative strategy followed by the two others, he/she can get a larger expected gain reaching 4.805% if he/she always ticks the box assuming the two others stick to the optimal cooperative strategy.
Of course, in reality the two others will NOT stick to the optimal cooperative strategy, but seek the Nash equilibrium that results when all players know the others are as selfish as he/her-self.
Consider the strategy with q = 1/[sqrt]2 (p [approx] 0.2929). This strategy constitutes a Nash equilibrium for this game: when the two other players follow this strategy, the third player can not do better (can not get a larger expected gain) by not following the same Nash equilibrium strategy. (This is the case because the expected "check-the-box gain" of 10(2q2-1) for the third player equals zero for q = 1/[sqrt]2, whilst the "leave-the-box-empty gain" is also zero.)
What results is a Nash equilibrium with an expected gain of exactly zero (on average zero boost of the score result) for all players. This clearly is less than the 0.671% gain they all could get by all following the optimal cooperative strategy.
|
| « Last Edit: Dec 1st, 2004, 3:29pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Checkbox on Exam
« Reply #9 on: Dec 2nd, 2004, 12:37am » |
Quote Modify
|
on Dec 1st, 2004, 3:09pm, JocK wrote:| Of course, in reality the two others will NOT stick to the optimal cooperative strategy, but seek the Nash equilibrium that results when all players know the others are as selfish as he/her-self. |
|
That's not reality.. People aren't rational, and they have a sense of fairness. If they're smart enough to figure out the problem, then most would know the only way to gain is to be fair towards each other. And beat up everyone who cheats 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Foolish
Newbie
Posts: 15
|
|
Re: Checkbox on Exam
« Reply #10 on: Dec 2nd, 2004, 12:55am » |
Quote Modify
|
When my friend and I were first posed this question, it took us only moments to figure out what we would do...ask around 
But in seeing as it is an exam, I would venture a guess and say that cooperation is a no-go.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Checkbox on Exam
« Reply #11 on: Dec 2nd, 2004, 1:45am » |
Quote Modify
|
Cooperation is possible without (explicit) communication, it's just a matter empathy, a good sense of how other people will act, and act accordingly. So the fact that it's an exam doesn't say much in that respect.
I'd probably just flip a coin or something, or decide not to check the box. (Even with a positive expectation, I might not want to risk it. And I wouldn't be the only one.)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Checkbox on Exam
« Reply #12 on: Dec 3rd, 2004, 1:56pm » |
Quote Modify
|
on Dec 2nd, 2004, 12:37am, towr wrote:
That's not reality.. People aren't rational, and they have a sense of fairness. If they're smart enough to figure out the problem, then most would know the only way to gain is to be fair towards each other. |
|
OK, let's test that:
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_eas y;action=display;num=1102110574.
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Checkbox on Exam
« Reply #13 on: Dec 5th, 2004, 7:44am » |
Quote Modify
|
There isn't anything at stake there, now is there.. it's just pretend
|
| « Last Edit: Dec 5th, 2004, 8:11am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Foolish
Newbie
Posts: 15
|
|
Re: Checkbox on Exam
« Reply #14 on: Dec 5th, 2004, 7:37pm » |
Quote Modify
|
I suppose that it is better than nothing...
When I was in AP Calc I proposed that my teacher use that on an exam, alas, he didn't. So I have no evidence.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print