wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Bachelor's Dilemma
        
(Message started by: tim on Aug 1^st, 2002, 5:07pm)

Title: Bachelor's Dilemma
Post by tim on Aug 1^st, 2002, 5:07pm

Bachelor's Dilemma (http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#bachelorsDilemma)

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//

Title: Re: Bachelor's Dilemma
Post by AlexH on Aug 2^nd, 2002, 5:14am

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.

Title: Re: Bachelor's Dilemma
Post by AlexH on Aug 2^nd, 2002, 5:15am

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)

Title: Re: Bachelor's Dilemma
Post by tim on Aug 2^nd, 2002, 3:47pm

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.

Title: Re: Bachelor's Dilemma
Post by Jonathan the Red on Aug 2^nd, 2002, 3:54pm

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.

Title: Re: Bachelor's Dilemma
Post by Eric Yeh on Aug 2^nd, 2002, 4:14pm

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

Title: Re: Bachelor's Dilemma
Post by AlexH on Aug 2^nd, 2002, 4:28pm

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?

Title: Re: Bachelor's Dilemma
Post by tim on Aug 2^nd, 2002, 5:00pm

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.

Title: Re: Bachelor's Dilemma
Post by AlexH on Aug 2^nd, 2002, 7:02pm

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.

Title: Re: Bachelor's Dilemma
Post by tim on Aug 2^nd, 2002, 7:31pm

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?

Title: Re: Bachelor's Dilemma
Post by AlexH on Aug 2^nd, 2002, 7:54pm

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.

Title: Re: Bachelor's Dilemma
Post by Eric Yeh on Aug 2^nd, 2002, 7:54pm

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

Title: Re: Bachelor's Dilemma
Post by tim on Aug 2^nd, 2002, 8:45pm

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.

Title: Re: Bachelor's Dilemma
Post by Eric Yeh on Aug 2^nd, 2002, 9:01pm

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

Title: Re: Bachelor's Dilemma
Post by OMG on Aug 5^th, 2002, 5:45pm

;D
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.

Title: Re: Bachelor's Dilemma
Post by mike1102 on May 27^th, 2003, 1:21pm

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.

Title: Re: Bachelor's Dilemma
Post by Eric Yeh on May 27^th, 2003, 1:50pm

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

Title: Re: Bachelor's Dilemma
Post by SWF on Jun 4^th, 2003, 8:43pm

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!

Title: Re: Bachelor's Dilemma
Post by Eric Yeh on Jun 5^th, 2003, 7:19am

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

Title: Re: Bachelor's Dilemma
Post by SWF on Jun 5^th, 2003, 10:39pm

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

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.

Title: Re: Bachelor's Dilemma
Post by Thordain on Jul 23^rd, 2003, 1:00pm

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_hard;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.

Title: Re: Bachelor's Dilemma
Post by SWF on Jul 24^th, 2003, 11:09pm

Thordain, the problem asked here was to maximize the probability of getting the best, not to maximize the expected rating of the woman selected.

Title: Re: Bachelor's Dilemma
Post by Rejeev on Nov 9^th, 2004, 2:25am

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.

Title: Re: Bachelor's Dilemma
Post by towr on Nov 9^th, 2004, 3:01am

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.

Title: Re: Bachelor's Dilemma
Post by spanchap on Mar 23^rd, 2007, 2:15pm

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

[hide]http://www.mathpages.com/home/kmath018.htm[/hide]

Title: Re: Bachelor's Dilemma
Post by amstrad on Mar 26^th, 2007, 12:13pm

also known as the Sultan's Dowry Problem:

http://mathworld.wolfram.com/SultansDowryProblem.html

Title: Re: Bachelor's Dilemma
Post by titan on Oct 15^th, 2013, 1:39am

"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) "

1) Why shud Willy date some number k of the N, then marry the first one after number k that is better than all the previous women? Why shud this strategy be used? Why have this strategy been thought of?
2) This:p(best of the first k+1 was in the first k dates) is basically no. of ways in which best date is in 1-k/that in k+1 = kC1/(k+1)C1 = k/k+1

Title: Re: Bachelor's Dilemma
Post by rmsgrey on Oct 15^th, 2013, 7:16am

on 10/15/13 at 01:39:30, titan wrote:

1) Why shud Willy date some number k of the N, then marry the first one after number k that is better than all the previous women? Why shud this strategy be used? Why have this strategy been thought of?

Willy has two pieces of information about each person he dates:

1) How they rank compared to the other people he's dated previously - in particular, whether or not they're the best he's dated.
2) Where they are in the list of the N people he could ever date - in particular, how many people he's dated previously.

Since the goal is to marry the best of the N people, the strategy obviously has to be of the form:

A) Reject anyone who isn't the "best so far" - they can't be the best of the N.
B) Reject anyone at specified points in the order - the only other basis for deciding to reject someone.
C) Accept the first person you don't reject.

Fairly obviously, the chances of the best so far being the best overall increase as he goes on more dates, so if Willy's prepared to risk a false positive with the k'th person dated, then he should also be prepared to risk it with the (k+1)'th, so the optimal strategy looks like "reject the first k and pick the next person who's better than all of them"

Title: Re: Bachelor's Dilemma
Post by titan on Oct 15^th, 2013, 7:49am

I think I'm getting it now. So here I go:-

He can date only some ladies. So, let it be k.
Now, he marries a girl based on the information he gathers by dating these k ladies.
Now, we don't know who he will marry out of the N-k. So, we add up all the possibilities. i.e. if he found k+1 is best or k+2 or k+3 and so on.
Now, when lets say he marries k+7 th girl, he secretly wants that best of all the k+6 girls shud have come up in the list he dated. So, we are multiplying these probabilities too with all the cases that either k+1 is best or k+2 or k+3 and so on!!
Am I right? :D

And since k can be anything from 1 to N-1, so, we have pretty much taken care of all cases.
And what if he dates just 1 lady and she is the best of N? We havn't taken into account for the case when he marries 1st date, I think, bcoz he only gets info by comparing! rightttt? :D

Title: Re: Bachelor's Dilemma
Post by rmsgrey on Oct 16^th, 2013, 5:19am

on 10/15/13 at 07:49:08, titan wrote:

And since k can be anything from 1 to N-1, so, we have pretty much taken care of all cases.
And what if he dates just 1 lady and she is the best of N? We havn't taken into account for the case when he marries 1st date, I think, bcoz he only gets info by comparing! rightttt? :D

When k=0 or k=N-1, then Willy only has a 1/N chance of marrying the best. When k=1 (assuming N>2), he has a better than 1/N chance - he has a 1/N chance that his first date is with the 2nd best, in which case he ends up with the best, but he also has a 1/N chance of it being with the 3rd best, in which case he then has a 1/2 chance of dating the best before the second best, so, just considering those two cases, he has a 1/N(1+1/2) chance of marrying the best - already better than the flat 1/N for settling for first or last...

So, yeah, he could settle for the first, but he only finds out about the distribution of women once he starts comparing them - after the first date, he has no idea whether it was good, bad, or about average, in comparison with the rest of the local dating pool...

Title: Re: Bachelor's Dilemma
Post by titan on Oct 16^th, 2013, 5:29am

A small doubt I have.

Quote:

Now, when lets say he marries k+7 th girl, he secretly wants that best of all the k+6 girls shud have come up in the list he dated.

He wud actually be wanting that best of all the N-1 wud have come in the list of girls he dated.
So, shudn't we be doing k/(N-1) n not k/(k+6).
Or is there any significance of numbering?