Improved Solution to Secretary Problem?

On May 26 2014 15:17 Daut wrote: and i just got real lazy. will likely come back to it at some point, but i have no work ethic to finish something i start because i havent done anything productive in 8 years

lold

you seem like a creative guy with good ideas, how can u not be productive. I mean how do you want to spend your next 50 years

On May 26 2014 15:39 dnagardi wrote: Show nested quote + On May 26 2014 15:17 Daut wrote: and i just got real lazy. will likely come back to it at some point, but i have no work ethic to finish something i start because i havent done anything productive in 8 years lold you seem like a creative guy with good ideas, how can u not be productive. I mean how do you want to spend your next 50 years

with a belly full of wine and a girls mouth around my cock?

The original algorithm maximizes P(r =1), where r is the rank of the chosen candidate. You are interested in maximizing E(r), the expected rank of the chosen candidate. Try to prove that your algorithm achieves a better value than the other one for the criterion E(r). Im sure someone has worked on such a variation before.

This link studies the generalized secretary problem. It seems that the optimal solution is similar to what you propose. I didn't read in detail.

http://vlab.ethz.ch/ROM/DBGT/Curves_files/BeardenMurphyDraft.pdf

This might be of interest too: http://www.spotlightmind.com/optimal-search

It was difficult to try your code because there's no spacing in the quotes. I put slightly cleaned up versions in gists:

Original:
https://gist.github.com/jchysk/2ea832c30f4a2d475079

Daut version:
https://gist.github.com/jchysk/7582c7618f9a35b9b5bd

I'm with Romm3l on implementing a search cost. Real world applications open up pretty dramatically when you incorporate a cost function to the mix. Then you can add in variable/static secretary salaries that scale with their overall ranks. I'm not very good with Python, but I could probably model this up in excel pretty easily. Either way, pretty interesting problem.

On May 27 2014 00:06 Bigbobm wrote: I'm with Romm3l on implementing a search cost. Real world applications open up pretty dramatically when you incorporate a cost function to the mix. Then you can add in variable/static secretary salaries that scale with their overall ranks. I'm not very good with Python, but I could probably model this up in excel pretty easily. Either way, pretty interesting problem.

suppose theres a search for a position. there are 3 things at play
-the more secretaries you search for, the more time and possibly cost goes by
-the longer you search, the longer a position is unfilled
-the days that you are searching you are not paying a new employee

i dont really know what kind of costs it takes to search for a new employee, nor do i know how much value a secretary adds versus her salary (or any position for that matter in a general sense). this seems kinda hard to model even though it likely is the single most important part of the whole real world equation lol

i think keeping it abstract at first is probably the best idea, mainly because the real world applications wont be at all similar. unknown N, ability to go back and call people already interviewed and no way a great candidate wouldnt be snap hired because she was one of the first applicants. its just a little silly to call it a secretary problem. it really should be applied to dating/marriage.

That was pretty cool. I might actually use this in real life. Can you go on further about the significance of e in the initial solution?

Hey I tried to generalize the problem so you do something other than 100 sec's but I'm finding the best match 35% of the time so I screwed up somewhere.
https://gist.github.com/RobertCorey/5fcdc0e6b07ba56fb91a
honestly thinking about ranges makes my brain hurt i'm the worst with off by 1 errors, when i played monopoly as a kid I could never remember if you were supposed to count the square you were on.

Btw in terms if code, you should create a function for all those while loops. Should also try and make those static checkpoints dynamic based on the number being ranked. That will likely take more work than necessary but it's still a good practice to have.

this is cool

Well, it's not an improved solution to secretary problem. Yours is a proposal to a different problem. For your problem:

If n is large you can approximate the distribution of population, say, by sampling first 1 million candidates. Stop at the first candidate who is better than 99.99% of approximated population. With large n, you should able to do this ~100% of the time.

^what you proposed there is a very different problem to op's or the orig secretary problem (which is more similar to op's than yours).. We're considering a situation where n is sufficiently small that there's a tradeoff between sampling enough candidates to get an idea of the distribution and what's considered good, and running the risk of losing the best candidates to the sampling process / not having enough candidates left to select from after. That's a fundamental idea behind the secretary problem, and that's the problem daut is trying to solve but with a modified payoff function (orig payoff function is 1 if best is selected, 0 otherwise). If you lose that tradeoff property from the problem you're looking at, you no longer have so many parallel situations that exist in the real world.

On May 27 2014 03:36 Daut wrote: Show nested quote + On May 27 2014 00:06 Bigbobm wrote: I'm with Romm3l on implementing a search cost. Real world applications open up pretty dramatically when you incorporate a cost function to the mix. Then you can add in variable/static secretary salaries that scale with their overall ranks. I'm not very good with Python, but I could probably model this up in excel pretty easily. Either way, pretty interesting problem. suppose theres a search for a position. there are 3 things at play -the more secretaries you search for, the more time and possibly cost goes by -the longer you search, the longer a position is unfilled -the days that you are searching you are not paying a new employee i dont really know what kind of costs it takes to search for a new employee, nor do i know how much value a secretary adds versus her salary (or any position for that matter in a general sense). this seems kinda hard to model even though it likely is the single most important part of the whole real world equation lol i think keeping it abstract at first is probably the best idea, mainly because the real world applications wont be at all similar. unknown N, ability to go back and call people already interviewed and no way a great candidate wouldnt be snap hired because she was one of the first applicants. its just a little silly to call it a secretary problem. it really should be applied to dating/marriage.

I think we don't need to make such a technical model for search cost.. just linear increasing with number searched will do the job and be close enough to the real world once you get the size of the increment right relative to payoffs.

Once you have search cost I think you don't need to consider a limit to N anymore as you said, since you already have pressure to hurry up and pick someone and not look forever.

Another thing to add to the mix that exists in the real world is a set of a priori beliefs about secretary ability that gets bayesian updated after each search, instead of going in with 0 assumed knowledge of the distribution before your first search

On June 03 2014 06:49 Romm3l wrote: ^what you proposed there is a very different problem to op's or the orig secretary problem (which is more similar to op's than yours).. We're considering a situation where n is sufficiently small that there's a tradeoff between sampling enough candidates to get an idea of the distribution and what's considered good, and running the risk of losing the best candidates to the sampling process / not having enough candidates left to select from after. That's a fundamental idea behind the secretary problem, and that's the problem daut is trying to solve but with a modified payoff function (orig payoff function is 1 if best is selected, 0 otherwise). If you lose that tradeoff property from the problem you're looking at, you no longer have so many parallel situations that exist in the real world.

My understanding of orig secretary problem does not assume sufficiently small n. In orig problem, both cost and benefit of searching are functions of n -that is, when you are concerned with determining the best candidate. Size of n doesn't matter.

Maybe small n was implied in op's problem.

Yeah, its a different problem, we can call it the "Daut's marriage problem", how to maximize the average scoring if they are ranked from 1 to 99. But then you have to prove that your algorithm is the best for that problem (we only know from a numerical method that its better than the original algoritm for the original problem).
I think the most practical result would be to get a set of must have rules like you have to leave your first X girlfriends you expect to date in your life but dont wait more than Y, becouse there are so many variables in the real world and sometimes not enough sample to use exactly the e number.
We can start studying the most basic marriage problem and then adding some complexity and try to solve it analytically.
So I'd do:
1. find the best solution to maximize average
2. add search cost (includes search, time being single, score decreasing becouse you get older)
3. random scores normalized (0 is the bottom of your choosing range, and 1 the top)
4. random scores distributed in a more realistic way (there are more bottom girls than top ones, so maybe you can use a top side of a normal?)
5. think this problem for poker?. If I play 2hr sessions, should I play now against this weak reg or wait for a weaker reg or fish?

Fuck my N number for girlfriend is low. How do I find my distribution ?
More seriously, I really like the problem set this way.

6. what if the girls are also playing the marriage problem and can dump you?

On June 03 2014 14:40 YourHarry wrote: Show nested quote + On June 03 2014 06:49 Romm3l wrote: ^what you proposed there is a very different problem to op's or the orig secretary problem (which is more similar to op's than yours).. We're considering a situation where n is sufficiently small that there's a tradeoff between sampling enough candidates to get an idea of the distribution and what's considered good, and running the risk of losing the best candidates to the sampling process / not having enough candidates left to select from after. That's a fundamental idea behind the secretary problem, and that's the problem daut is trying to solve but with a modified payoff function (orig payoff function is 1 if best is selected, 0 otherwise). If you lose that tradeoff property from the problem you're looking at, you no longer have so many parallel situations that exist in the real world. My understanding of orig secretary problem does not assume sufficiently small n. In orig problem, both cost and benefit of searching are functions of n -that is, when you are concerned with determining the best candidate. Size of n doesn't matter. Maybe small n was implied in op's problem.

heh that's true.. orig problem does give solution in terms of n. if n is so ridic big though that you can leisurely search 1mm candidates and have an excellent idea of the distribution and have plenty of candidates left over afterwards to select from then it doesnt really matter anymore where exactly we draw the line between search/select since it makes no material diff between searching the first 1mm or 1.5mm, so trying to get the answer of the orig problem stops being useful