I've heard of a similar puzzle (where you don't know the bounds of the items in the bag you're drawing out of, but they're evenly distributed) called "37 bangs", though I can't find a link describing it. You discard the first (total/e) items, take the max, and keep the next item you draw greater than that max.
but just drawing more because "it's early" makes no sense - the game is totally non temporal, the cost of continuing drawing doesn't go up over time
I wouldn't say it's non-temporal, because as you draw, you gain information about the distribution, right?
Your first draw might be 800, but you don't know until you've drawn a lot more whether they're all 800 or higher, or all 800 or lower, or maybe split between all 800s and 200s.
You don't know whether that 800 is actually good or not until you've seen the actual distribution, and the only way to estimate the distribution is to sample. So "I just started drawing, I shouldn't stand yet" makes sense to me -- it means, "I don't know yet what game I'm playing; I need to play a bit to figure out the rules."
"I wouldn't say it's non-temporal, because as you draw, you gain information about the distribution, right?"
Yeah yeah, this is the crux of the whole game. You have to make a running estimate of the true distribution, and *also* a confidence measure of that estimate (more completely - you should estimate a probability of every possible distribution).
Then to make a decision, you evaluate the EV under each distribution assumption and weight it by the probability of that distribution being the true one. It's a whole lot like Bayesian Poker actually.
Anyway, just like in Poker, uncertainty is not a reason to cop out on a decision. Even when you weight over the various possible distributions with very high uncertainty, you may get a clear answer that standing is higher EV than drawing.
The classic secretary problem didn't penalize you for passing candidates. I guess Brian must have been responding to Ian, and not the post.
A DM friend of mine would roll hit points like that (with the -1 penalty per re-roll), but since the probability distribution is well-known the "solution" is more or less obvious. Didn't stop people from gambling from time to time, though.
Yeah Secretary Problem is interesting and similar, but the cost of redraw is a huge difference.
Also, reading the Wikipedia page -
"Experimental studies
Psychologists and experimental economists have studied the decision behavior of actual people in secretary problems [1]. In large part, this work has shown that people tend to stop searching too soon. This may be explained, at least in part, by the cost of evaluating candidates. Extrapolating to real world settings, this might suggest that people do not search enough whenever they are faced with problems where the decision alternatives are encountered sequentially. For example, when trying to decide at which gas station to stop for gas, people might not search enough before stopping. If true, then they would tend to pay more for gas than they might had they searched longer. The same may be true when people search online for airline tickets, say. Experimental research on problems such as the secretary problem is sometimes referred to as behavioral operations research."
this points out the huge flaw of failing to count the cost of redraw. I think this paragraph is the opposite of true. In fact, I believe most people search far too long for things like airline tickets and gas stations, and would almost always be best off just taking the first thing they see. The savings from finding something better is almost always dwarfed by the cost of the search (though again a correct decision would take into account the cost of the search vs. the likelihood and magnitude of improvement).
I just skimmed the problem statement and noticed it sounded familiar. I should have read it more carefully.
June 23, 2009 at 12:11 AM
Anonymous said...
I immediately thought of the secretary problem back when I read this comment on an old entry:
Which of the following will hurt you more?
A) Continue to endure the torture of uninvited noise for x months/year?
B) Endure the hassle of looking for another place and move again?
Personally, I would go for B, and then B, and B, and B, as many times as needed for me to be happy.
Obviously the -1 changes the problem in significant ways. One of the most interesting aspects of the solution to the secretary problem is that the distribution of values doesn't affect the solution, but this isn't true of your version of the problem. But it's still interesting that the secretary problem pretty much explicitly encodes "it's too early" into the algorithm.
Actually, correction: the canonical sectary problem solution is designed to give the maximum chance that you choose the maximum item, not to e.g. maximize expectation of the final choice. The expectation would presumably require a solution that isn't distribution-independent.
And since you only get one life, you might prefer to minimize the shittiness of the final choice rather than optimize even for expectation--i.e. you want to minimize variance or something. This probably forces you more towards "stop as soon as you hit something 'good enough'".
"And since you only get one life, you might prefer to minimize the shittiness of the final choice rather than optimize even for expectation--i.e. you want to minimize variance or something. This probably forces you more towards "stop as soon as you hit something 'good enough'"."
Yeah, the secretary solution gives you a 37% chance of getting the best one, but in the other 63% of the time you get an arbitrary bad one. Obviously that has little relation to real world decision making.
I've written about this before - the weighting of value in life is highly nonlinear and is mostly biased towards avoiding very bad outcomes rather than maximizing EV.
eg. in the context of gambling if someone offers you a 51% coin flip, your maximum EV move is to bet everything you own on it, but obviously that's a very poor real world decision, because real value is logarithmic or something.
eg. in apartment searching - avoiding something awful is far more important than getting something maximally awesome.
June 23, 2009 at 10:59 AM
This apartment searching is really annoying me. I can't handle having "many balls in the air" ; when I put something on my todo list,
I like to work at it until it's gone. God I fucking hate shit on my todo list (the fucking health care keeps reinserting itself on my
todo list and it's pissing me off; they got me again today with some billing fuckup, but I digress...).
Anyway, it's reminding me of a concept I often think about. I'll call it "the redrawer's dilemma" but there must be a better/standard name for
this.
The hypothetical game goes something like this :
You are given a bag with 100 numbers in it. You know the numbers are in [0,1000] but don't know how many of each number there are in the
bag. You start by drawing a random number from the bag.
At each turn of play, you can either keep your current number (in which case that is your final score), or you can put your current number
back in the bag and draw again, but drawing again costs you -1 that will be subtracted from your final score.
How do you play this game optimally?
There are two things that are interesting to me about this game in real life. One is that humans almost always play it incredibly badly,
and the second is that when you finally decide to stop redrawing you're almost always unhappy about it (unless you got super lucky and
draw a 900+ number).
The two classic human player errors in this game are the "I just started drawing, I shouldn't stand yet" and the "I can't stop now, I already
passed on something better than this". The "I just started drawing, I shouldn't stand yet" guy draws something like an 800 on one of his
early draws. He thinks dang that's really good, but maybe this bag just has lots of high numbers in it, I just started drawing, I should
put some time into it. Now of course that reasoning is based in correct logic - if you have reason to believe that your chance of drawing
higher is good enough to merit the cost of continued looking, then yes, do so, but just drawing more because "it's early" makes no sense -
the game is totally non temporal, the cost of continuing drawing doesn't go up over time. This often leads into the
"I can't stop now, I already passed on something better than this" guy, who's mainly motivated by pride and shame - he doesn't want to admit to himself that
he made a big mistake passing early when he got a high number, so he has to keep drawing until he gets something better. He might draw an 800,
then a whole mess of single digit numbers and he's thinking "oh fuck I blew it" and then he draws a 400. At that point he should stand and
quit redrawing, but he can't, so he draws again.
The thing is, even if he played correctly and just took the 400 after passing on the 800, he would be really unhappy about. And if the
early termination guy played correctly and just got an early 800 and didn't draw, he would be unhappy too, because he'd always be wondering
if he could've done better.
The other game theory / logical fallacy that plagues me in these kind of things is "I'm already spending X I may as well spend X". First I
was looking for places around $1500, then I bumped it to $1700, then $1900. Now I'm looking at places for $2500 cuz fuck it they're nicer
and I was looking at places for $2000 so it's only $500 more.
In other news, hotpads is actually a pretty cool apartment search site. It seems they are just scraping
craigslist and maybe some other classifieds sites, so it's not like they have anything new, but the map interface and search features and
such are solid. One thing is really annoying me about it though - the wheel zooming in the map is totally broken, I keep trying to wheel
zoom and it sends the map off the never never land. Urg!
In more random news, I've really enjoyed the "Wallander" series on PBS ; the crime stories are pretty dumb/ridiculous, but I like the muddled contemplative
pace of it, and the washed out monochrome color palette.
"06-22-09 - Redraw Dilemma"
9 Comments -
I've heard of a similar puzzle (where you don't know the bounds of the items in the bag you're drawing out of, but they're evenly distributed) called "37 bangs", though I can't find a link describing it. You discard the first (total/e) items, take the max, and keep the next item you draw greater than that max.
June 22, 2009 at 7:11 PM
but just drawing more because "it's early" makes no sense - the game is totally non temporal, the cost of continuing drawing doesn't go up over time
I wouldn't say it's non-temporal, because as you draw, you gain information about the distribution, right?
Your first draw might be 800, but you don't know until you've drawn a lot more whether they're all 800 or higher, or all 800 or lower, or maybe split between all 800s and 200s.
You don't know whether that 800 is actually good or not until you've seen the actual distribution, and the only way to estimate the distribution is to sample. So "I just started drawing, I shouldn't stand yet" makes sense to me -- it means, "I don't know yet what game I'm playing; I need to play a bit to figure out the rules."
June 22, 2009 at 7:24 PM
"I wouldn't say it's non-temporal, because as you draw, you gain information about the distribution, right?"
Yeah yeah, this is the crux of the whole game. You have to make a running estimate of the true distribution, and *also* a confidence measure of that estimate (more completely - you should estimate a probability of every possible distribution).
Then to make a decision, you evaluate the EV under each distribution assumption and weight it by the probability of that distribution being the true one. It's a whole lot like Bayesian Poker actually.
Anyway, just like in Poker, uncertainty is not a reason to cop out on a decision. Even when you weight over the various possible distributions with very high uncertainty, you may get a clear answer that standing is higher EV than drawing.
June 22, 2009 at 7:31 PM
This a classic probability problem. It is often posed in terms of a marriage problem. See http://en.wikipedia.org/wiki/Secretary_problem
June 22, 2009 at 9:50 PM
The classic secretary problem didn't penalize you for passing candidates. I guess Brian must have been responding to Ian, and not the post.
A DM friend of mine would roll hit points like that (with the -1 penalty per re-roll), but since the probability distribution is well-known the "solution" is more or less obvious. Didn't stop people from gambling from time to time, though.
June 22, 2009 at 10:32 PM
Yeah Secretary Problem is interesting and similar, but the cost of redraw is a huge difference.
Also, reading the Wikipedia page -
"Experimental studies
Psychologists and experimental economists have studied the decision behavior of actual people in secretary problems [1]. In large part, this work has shown that people tend to stop searching too soon. This may be explained, at least in part, by the cost of evaluating candidates. Extrapolating to real world settings, this might suggest that people do not search enough whenever they are faced with problems where the decision alternatives are encountered sequentially. For example, when trying to decide at which gas station to stop for gas, people might not search enough before stopping. If true, then they would tend to pay more for gas than they might had they searched longer. The same may be true when people search online for airline tickets, say. Experimental research on problems such as the secretary problem is sometimes referred to as behavioral operations research."
this points out the huge flaw of failing to count the cost of redraw. I think this paragraph is the opposite of true. In fact, I believe most people search far too long for things like airline tickets and gas stations, and would almost always be best off just taking the first thing they see. The savings from finding something better is almost always dwarfed by the cost of the search (though again a correct decision would take into account the cost of the search vs. the likelihood and magnitude of improvement).
June 22, 2009 at 10:55 PM
I just skimmed the problem statement and noticed it sounded familiar. I should have read it more carefully.
June 23, 2009 at 12:11 AM
I immediately thought of the secretary problem back when I read this comment on an old entry:
Which of the following will hurt you more?
A) Continue to endure the torture of uninvited noise for x months/year?
B) Endure the hassle of looking for another place and move again?
Personally, I would go for B, and then B, and B, and B, as many times as needed for me to be happy.
Obviously the -1 changes the problem in significant ways. One of the most interesting aspects of the solution to the secretary problem is that the distribution of values doesn't affect the solution, but this isn't true of your version of the problem. But it's still interesting that the secretary problem pretty much explicitly encodes "it's too early" into the algorithm.
Actually, correction: the canonical sectary problem solution is designed to give the maximum chance that you choose the maximum item, not to e.g. maximize expectation of the final choice. The expectation would presumably require a solution that isn't distribution-independent.
And since you only get one life, you might prefer to minimize the shittiness of the final choice rather than optimize even for expectation--i.e. you want to minimize variance or something. This probably forces you more towards "stop as soon as you hit something 'good enough'".
June 23, 2009 at 10:45 AM
"And since you only get one life, you might prefer to minimize the shittiness of the final choice rather than optimize even for expectation--i.e. you want to minimize variance or something. This probably forces you more towards "stop as soon as you hit something 'good enough'"."
Yeah, the secretary solution gives you a 37% chance of getting the best one, but in the other 63% of the time you get an arbitrary bad one. Obviously that has little relation to real world decision making.
I've written about this before - the weighting of value in life is highly nonlinear and is mostly biased towards avoiding very bad outcomes rather than maximizing EV.
eg. in the context of gambling if someone offers you a 51% coin flip, your maximum EV move is to bet everything you own on it, but obviously that's a very poor real world decision, because real value is logarithmic or something.
eg. in apartment searching - avoiding something awful is far more important than getting something maximally awesome.
June 23, 2009 at 10:59 AM