Author |
Topic: Bachelor's Dilemma (Read 15402 times) |
|
tim
Junior Member
Posts: 81
|
 |
Bachelor's Dilemma
« on: Aug 1st, 2002, 5:07pm » |
 Quote  Modify
|
Bachelor's Dilemma
I don't think this problem has any optimal solution as stated. The best strategy will depend upon willy's prior knowledge of the distribution.
This is easiest to see in the case N=2. If willy knows the median, he should use that as a criterion for a 75% chance. If he knows nothing about the median, he has only a 50% chance. An approximation to the median will give some chance in the middle.
//Link added by moderator//
|
| « Last Edit: Aug 28th, 2003, 6:19pm by Icarus » |
 IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: Bachelor's Dilemma
« Reply #1 on: Aug 2nd, 2002, 5:14am » |
Quote Modify
|
Since nothing is said about any prior knowledge I think we're meant to assume he has none. Willy can simply make comparisons among the women he dates.
|
| « Last Edit: Aug 2nd, 2002, 5:15am by AlexH » |
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: Bachelor's Dilemma
« Reply #2 on: Aug 2nd, 2002, 5:15am » |
Quote Modify
|
Moved hint to this message so it would be against black background.
Hint:
Willy will want to pick some number k of women, and marry the first woman who is better than all of the first k women.
Hint 2:
Approximate the Harmonic series with
H(n) = 1+1/2+1/3+... +1/n = (approx) ln n + .577... + 1/(2n)
|
| « Last Edit: Aug 2nd, 2002, 7:05am by AlexH » |
IP Logged |
|
|
|
tim
Junior Member
Posts: 81
|
|
Re: Bachelor's Dilemma
« Reply #3 on: Aug 2nd, 2002, 3:47pm » |
Quote Modify
|
Reply to hint: No strategy of this form works. For any k>0, there is a non-zero chance that willy will marry no woman at all, violating the conditions of the problem. Note: N is described as fixed before he dates any of them.
My other concern is your assumption that willy knows absolutely nothing about the distribution of women. Your assumption implies that willy knows no more about the first woman after his date than before it, regardless of how good or bad the date was.
I did briefly consider this assumption, and worked out a solution, but I consider the premise to be the weakest of those I considered.
I am open to suggestions as to why you think it is a reasonable assumption, though.
There is an answer if you treat it as a trick question: willy should let N=1. That way, he is guaranteed to choose the best woman in the set. Again, I think this is a poor answer. Its only redeeming feature is that it technically meets the problem specification. Could I convince willy that it is optimal? That's up to willy, but anyone looking for a wife using the method described shouldn't be too hard to convince of anything.
|
|
IP Logged |
|
|
|
Jonathan the Red
Guest
|
The problem is to maximize the probability of picking the best woman, not maximize the expected utility. Alex's hint is valid; if no woman is found in the N-k women better than the first k, Willy should marry the Nth woman (or stay single), but this will be a failure case.
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender: 
Posts: 318
|
|
Re: Bachelor's Dilemma
« Reply #5 on: Aug 2nd, 2002, 4:14pm » |
Quote Modify
|
Tim,
Willy indeed knows a great deal more about the woman after he has dated her than before: He knows how she compares to all previous dates. You should model the problem as recieving a string of real numbers, and trying to determine at which point stopping would maximize your chance of getting the best woman.
Note that N is fixed as a given, not something that is decided by Willy.
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: Bachelor's Dilemma
« Reply #6 on: Aug 2nd, 2002, 4:28pm » |
Quote Modify
|
First: agreement with Jonathan. If Willy must marry despite failing to find the best woman, then obviously he has to take the Nth woman even if he knows she isn't the best. This solution still maximizes his chance at the best woman which was the question that was asked.
Second: What are you talking about tim? Are you intentionally being pedantic? You can choose to model the date as a sampling of a random variable which is used to condition your prior expectations, but why try to do this when nothing of the kind was mentioned in the problem. If you're desperate for precision then instead of having as I colloquially said "no prior knowledge", assume Willy's priors about each individual woman are so weak that they are almost completely overridden by the date experience, and we really don't need him to have any priors on the set of all women, since he doesn't need to form any judgements about that set. If someone else programs some bitsequence to be printed out by a compter I have extremely weak priors on what it might be, but that doesn't mean that once I see it I still don't know what it is.
It is much more logical to model this as Willy having a sense after the date that the woman has some value x as a wife, or, equivalently if we assume he doesn't know anything about the distribution over all women, that after a set of dates he can compare the women and make judgements between them. This comparison model provides a nice solution and fits the problem. Why look for difficulties that don't exist?
|
|
IP Logged |
|
|
|
tim
Junior Member
Posts: 81
|
|
Re: Bachelor's Dilemma
« Reply #7 on: Aug 2nd, 2002, 5:00pm » |
Quote Modify
|
Regarding choice of N: The problem explicitly states that willy "plans to date exactly N women at random". That certainly sounds like it is willy who chooses N.
Eric: I explicitly metioned the first woman. Willy knows nothing about her after his date according to Alex's assumption. Should we assume that willy is unobservant as well as clueless?
Also, you haven't given any reason why I should model the problem your way. Why shouldn't I model it as receiving a string of numbers from a uniform distrubtion on [0,1]? This is a reasonable match to the practice of rating "X out of ten". Is willy capable of evaluating a date or not?
Alex: Of course I'm being pedantic. The problem asks for the optimal solution. I won't settle for a conditional one based on highly dubious assumptions.
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: Bachelor's Dilemma
« Reply #8 on: Aug 2nd, 2002, 7:02pm » |
Quote Modify
|
Why would you make assumtions about willy having useful prior information about set of N women, assumptions which are certainly not supported by the text of the question and which should at least be discouraged by the line "none of whom he knows anything about". If you don't then an unknown distribution on [0,1] reduces to my model with the exception that, if willy ever dates a 1 he is done. Sure willy can judge women out of 10, but there is no reason to think his judging would be uniform random on the distribution of all women. If willy had some ability to judge a women against the set of all other women the problem obviously should have included that information, it didn't. You're assuming he can do this only to complain about the fact that how well he can do it isn't specified in the problem. The resolution of this problem should be clear, don't assume he can do it.
To say that willy knows absolutely nothing after his first date is simply wrong. He knows nothing about how his first date compares to other women, but so what? As soon as he's had his second date he can start making comparisons and that is all we need.
I'm not sure what assumptions you're referring to when you claim my assumptions are "highly dubious". Is it the assumption that willy can compare women after he has dated them or the assumption that he will judge these women by the dates and not based on some knowledge about women in general which is never mentioned in the problem.
I don't think you and I use the same definition of pedantic.
|
|
IP Logged |
|
|
|
tim
Junior Member
Posts: 81
|
|
Re: Bachelor's Dilemma
« Reply #9 on: Aug 2nd, 2002, 7:31pm » |
Quote Modify
|
Your assumption means that he needs to have a second date before he has any idea at all about how the first one went. You don't think that makes it a highly dubious assumption? (And that's all it is, an assumption not based on anything stated in the problem)
The problem didn't say willy was a moron. Maybe it should have?
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: Bachelor's Dilemma
« Reply #10 on: Aug 2nd, 2002, 7:54pm » |
Quote Modify
|
Of course he can have information about how it went. "I had a good time", "she was a cute but kind of pedantic", "Her adam's apple was sexy", "She r0x0rs 7eet lik JLo" . Willy can think any of these things within my model and thats fine. What he can't think is, "I know she is probably the best woman in the set". The information he lacks is how likely it is other women in his pool will be better or worse than this one.
Willy is a fictional construct used to present a problem, not an actual person. His method of choosing a wife is certainly not the act of a normal thinking person, but we accept it because its given by the problem. We didn't get any information about the odds that willy is shot by the jealous husband of some women he picked out of the phone book, but I don't think that spoils the problem.
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: Bachelor's Dilemma
« Reply #11 on: Aug 2nd, 2002, 7:54pm » |
Quote Modify
|
Reponse to Tim's thread 7:
I concede that there is a very mild ambiguity in the wording of the "N" choice, but clearly it can be interpreted as a number that is passed into the problem as well as one that can be chosen. Furthermore, any good reader of problems should immediately determine the correct intent of the author by the very fact that there would otherwise be a trivial soln.
Regarding the first woman: My apologies for misreading the thrust of your previous comment. However, my thought process remains the same, and it is clear to me that it is not only the intended meaning of the author but also a reasonable assumption to make on a first date. When you encountered the first person you met in your life, did you consider him either good or bad? I certainly classified my first acquaintance as neutral -- statistically it is your best guess of the mean of the population. Suppose I offered you a bfjdsbjure, a fruit from an island in the Pacific which you've never had before. It tastes very good to you. Do you now assume it's the best of it's kind of fruit?? If I have N-1 more waiting for you would you hang your hat on that one as the best one (supposing there were a way to quantify it)?
And while resisting from joining the foray into mathematical jargon, I do completely agree with Alex regarding the modelling of this aspect of the problem.
Tim, there's no need to so antagonistic -- I was merely trying to be helpful.
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
tim
Junior Member
Posts: 81
|
|
Re: Bachelor's Dilemma
« Reply #12 on: Aug 2nd, 2002, 8:45pm » |
Quote Modify
|
Interesting you should talk about personal experience. I married the woman I first dated, because I knew there was a very slim chance I would meet someone better. In hindsight, I'm pretty sure I was right.
Yes, willy is a fictional construct. One who should probably done away with so that the problem can be restated less ambiguously.
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: Bachelor's Dilemma
« Reply #13 on: Aug 2nd, 2002, 9:01pm » |
Quote Modify
|
Wow! Congratulations Tim, I've very impressed. I myself have always felt it is almost never the right thing to do to stay with your first love (my model of life is actually much closer to fictitious Willy's than to yours, it seems), so I am always quite impressed when people do so and make it work.  Perhaps you possess a much better power of observation and foresight than the rest of us, and that was what set our interpretations of the wording apart.
In any case, I'm glad we can at last put this issue to rest.
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
OMG
Guest
|
Whenever a bachelor and his date agree to get married, is when they should.
He should pick her only after she has "picked" him, otherwise she might be unavailable or worse. (psycho)
When he has been picked, and he returns the pick, the "algorithm is optimal" because they both think that they are getting the better of the agreement.
|
|
IP Logged |
|
|
|
mike1102
Guest
|
The way I see it......
1. Willie probably has dated somewhat before he decides he is lonely and wants a wife. Thus, he has some apriori grading scheme based upon experience. Let's say its 1 to 10, with 10 being highest and the average woman rates a 5.
2. Willy is going to date at most, N women - perhaps less than N. After deciding upon "the one", although the problem statement would allow Willy to continue dating, the future Mrs. Wutang would most likely frown upon that.
3. Before the first date, Willy must choose a threshold such that when a woman is at or above this threshold, she is "the one". Let that threshold be T where 1 <= T < 10.
4. Let's assume the N women are Normally distributed about a mean value of 5 - invoke the Central Limit Theorm and Choose N "sufficiently large" and a corresponding T < 10. Obviously, N & T are related as T --> 10, N --> very large. (the time spent dating becomes very large too.)
Algorithm: Selecting N implys selecting T. Propose to the first lady that meets or exceeds T. She won't be a perfect "10" (neither is Willy) but she is the best under the circumstances.
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: Bachelor's Dilemma
« Reply #16 on: May 27th, 2003, 1:50pm » |
Quote Modify
|
Mike,
I generally agree except that the problem can be more general without assumption 1, ie if Willy has no previous dating experience. There's also no reason to believe that the distribution has to be normal (tho I tend to agree in real life, it's not necessary for the problem). Finally -- with full concession that I haven't re-read the statement of the problem in almost a year at least  -- part of the problem is to find the function T(N).
Wow, you're the first person to respond to one of my watch threads in almost a year.
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Bachelor's Dilemma
« Reply #17 on: Jun 4th, 2003, 8:43pm » |
Quote Modify
|
Willy should date some number k of the N, then marry the first one after number k that is better than all the previous women. Need to find k in terms of N that maximizes the probability of ending up with the best one.
The probability of ending up with the best of the N women with this strategy is:
p(date k+1 is best)
+ p(date k+2 is best)*p(best of the first k+1 was in the first k dates)
+ p(date k+3 is best)*p(best of the first k+2 was in the first k dates)
+ p(date k+4 is best)*p(best of the first k+3 was in the first k dates)
+ ...
+ p(date N is best)*p(best of the first N-1 was in the first k dates)
Otherwise, Willy will either marry one of the women better than all the first k, but not the best of the lot, or the best was passed up in the first k and he rejects all N women (or settles on the last one).
Filling in the numbers for the above probabilities is straight forward, it gives:
1/N
+ 1/N * k/(k+1)
+ 1/N * k/(k+2)
+ 1/N * k/(k+3)
+ ...
+ 1/N * k/(N-1)
= k/N*( 1/k + 1/(k+1) + 1/(k+2) +1/(k+3) + ... + 1/(N-1) )
= k/N*( H(N-1) - H(k-1) )
where H(m) is the sum of the first m terms of the harmonic series:
H(m) = 1 + 1/2 + 1/3 +1/4 + ... + 1/m
There is probably some clever way to find the integer k that maximizes the probability, but a pretty good quick approximation can be found by using H(m)=ln(m)+g, where g is the Euler-Mascheroni constant. This approximation for H(m) is accurate to within about 1/(2*m). Plugging in the formula for probability and using calculus to maximize with respect to k gives the approximation that k = (N-1)/e + 1, where e=2.71828... What a romantic way for Willy to meet his wife!
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: Bachelor's Dilemma
« Reply #18 on: Jun 5th, 2003, 7:19am » |
Quote Modify
|
SWF,
Bravo on the general analysis! Can you show that last bit of calculus? It's been a while since I worked on this, but I seem to recall my answer being ever-so-slightly different, and somehow I'm not getting the calc to fall out as you've written.
Thanks,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Bachelor's Dilemma
« Reply #19 on: Jun 5th, 2003, 10:39pm » |
Quote Modify
|
P(k)=k/N*(ln(N-1) - ln(k-1)) (approximately)
dP/dk=0= ln(N-1) - ln(k-1) - k/(k-1)
N-1=(k-1)*exp(k/(k-1))
The result given yesterday was from being lazy and approximating exp(k/(k-1)) by e. By being more careful in the approximation, a little better was something like (I threw away the envelope it was on):
k= (N-1)/2/e + sqrt(((N-1)/e)2-2)/2
Never mind the calculus, I found a better way to maximize P(k). The exact expression is P(k)=k/N*(H(N-1)-H(k-1)). The smallest k with P(k+1)-P(k)<0 should give the maximum P(k), because when plotting P(k) vs. k it starts out increasing, reaches a max, and then decreases (or at least I assume it does).
P(k+1)-P(k) = H(N-1)/N - H(k+1)/N + k/N( H(k)-H(k+1) ) < 0
This reduces to trying to find the smallest k that satisfies
1 > H(N-1) - H(k) = 1/(k+1) + 1/(k+2) + 1/(k+3) + ... 1/(N-1)
Using the approximation for H(n) implies k is the smallest integer greater than (N-1)/e.
|
|
IP Logged |
|
|
|
Thordain
Newbie
Posts: 3
|
|
Re: Bachelor's Dilemma
« Reply #20 on: Jul 23rd, 2003, 1:00pm » |
Quote Modify
|
Ok, here is the solution I got.
In general: For N women, and a discarding the first k, the expected rating of the date is what?
If the most beautiful woman is in the first k, then willy ends up discarding all other women and is stuck with the last one, with an expected rating of (1 + N - 1)/2
. The chance of this happening is k/N. So the expected return in this case is
N/2 * k/N = k/2
If the most beautiful woman is NOT in the first k, then willy will get the first woman more beautiful than the best of the first k. If the most beautiful woman of the first k has a rating of p, then willy's woman will get an expected rating of (p + 1 + N)/2. The chance of this happening is (N-k)/N. So the expected return in this case is
(p+1+N)/2 * (N-k)/N
The calculation of p is a little trick and takes some combinatorial identities to reduce. But I eventually found that
p = N - (N - k)/(k + 1)
After some algebra to clean this up, we get.
E(k, N) = N - k/2 - (N-k)(N-k-1)/2N(k+1)
For the case of 100, in the sultan and his 100 wives problem
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_har d;action=display;num=1058954585
I plugged in values for N 100 and k ranging for 1 to 11, and found that it maxes out at k = 9, with
E(9, 100) = 91.405
So by discarding the first 9 women out of 100, willy can get an expected rating of 91.405.
|
|
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Bachelor's Dilemma
« Reply #21 on: Jul 24th, 2003, 11:09pm » |
Quote Modify
|
Thordain, the problem asked here was to maximize the probability of getting the best, not to maximize the expected rating of the woman selected.
|
|
IP Logged |
|
|
|
Rejeev
Newbie
Gender:
Posts: 31
|
|
Re: Bachelor's Dilemma
« Reply #22 on: Nov 9th, 2004, 2:25am » |
Quote Modify
|
After each dating he has to calculate a benchmark, and if the next dating is above that benchmark choose that girl. benchmark depends up on the average and standard deviation of previous dates and number of girls remaining (as fraction of total). benchmark at last girl should be 0 so that he will marry the last girl in the worst case. This will increase the expected utility than the probability of marrying the best. one simple function is:
benchmark = (avg + SD) * fraction of girls remaining
Regards,
Rejeev.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Bachelor's Dilemma
« Reply #23 on: Nov 9th, 2004, 3:01am » |
Quote Modify
|
You're using assumptions about the distribution. Sure, if it's a normal distribution you'll score better, but if it isn't you may fare much, much worse.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
spanchap
Newbie
Suresh
Gender:
Posts: 40
|
|
Re: Bachelor's Dilemma
« Reply #24 on: Mar 23rd, 2007, 2:15pm » |
Quote Modify
|
I came up with a solution that is very close to another more elegant solution to be found at the link below. I did not want to add to it to avoid any appearances of plagiarism
http://www.mathpages.com/home/kmath018.htm
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove