0
$\begingroup$

I was assigned to write a computer program that simulates a CPU, but it is more like a game:
A queue of processes is initialized: $P_1,P_2...P_n$, ordered in some random permutation: $P_{\sigma (1)},P_{\sigma (2)},...,P_{\sigma (n)}$, where every process $P_i$ has a priority, $p_i\in\left \{1,2,...n \right \}$.
The lower the value $p_i$ is, the more urgent $P_i$ is (in other words, if $p_i=1$, then $P_i$ has the highest priority in the queue).
In addition, every process $P_i$ in the queue, has its relative priority, $r_i\in\left \{1,2,...n \right \}$, which, informally, represents "how urgent the process is relative to previous processes in the queue".
To be clear, let me give an example:
Let's say $n=6$: then the queue might look like this:
$$\begin{bmatrix} P_i: & P_5 & P_6 & P_1 & P_2 & P_4 & P_3\\ p_i & 4 & 5 & 2 & 1 & 3 & 6\\ r_i & 1 & 2 & 1 & 1 & 3 & 6 \end{bmatrix}$$ as you probably already noticed, $r_i$ represents "What is $P_i$'s priority, related to all processes that precedes it in the queue". that's why, for example, although $p_1=2$, $r_1=1$, because related to $P_5$ and $P_6$, $P_1$ has the highest priority.
My goal is, of course, to choose the process with the highest priority.
There are two tricky parts though:
First of all, the CPU (my program) does not "know" $p_i$ (meaning, I don't get $p_i$ as input).
My program starts a loop, where on the $i$'th loop iteration, the CPU gets $r_i$ as input, and has to decide on the spot, only based on $n$ and $r_i$, whether if it rejects $P_i$ or accepts it. when the CPU chooses to accept some $P_i$, the game is over, and the real priority $p_i$ is revealed (if I reject the first $n-1$ $P_i$s, I'm obligated to accept $P_n$).
The second tricky part is, I don't get to regret. whenever I reject $P_i$, it's gone, and $r_{i+1}$ is presented. I can't go back and choose $P_i$ later in the game.
Some portion of my grade will evaluated based on how well my program makes its decisions: the program will get executed $m$ times, and the grade will be calculated by: $\text{decision_making}=100\times\frac{n-\text{avg}}{n-1}+20$
where $\text{avg=average of real priority over m program executions}$.

So I read some articles online, explaining how to deal with a variation of this problem, called The secretary problem, where they say that in order to get the best results, one should reject the first $\frac{n}{e}$ processes ($e$ - the base of the natural logarithm), and then accepts the first one that has $r_i=1$ (if no such process exist, I 'get stuck' with the $P_n$), I also saw a proof, showing that this tactic will give $37$~ percent success rate. So I tried it, and indeed got some pretty good results. I was able to achieve an average of $4$~ for $n=40$, giving $\text{decision_making}=109.743$, which is more than enough really. I was just wondering, out of curiosity; since this version is a bit different than the original "Secretary problem", does anyone have an idea that can improve this?
For example, how about the following tactics:
Let $i$ be the loop iteration, I'll reject the first $k=\frac{n}{e}$ processes in the queue, and for $i>k$, the closer $i$ gets to $n$ the less strict my policy will be; meaning, I'll start settle for $r_i=2,3,4...$ as $i$ grows towards $n$.
Could that be a better tactics?
Of course, I can write that code down and check, but I'd rather hear some opinions before introducing my code to new bugs.

$\endgroup$
1
$\begingroup$

This is not a variation of the Secretary problem - it is the Secretary problem.

The secretary problem is only concerned with relative ranking i.e. is the current candidate the best so far. The absolute value of the ranking is not known a priori - hence the difficulty.

Specifically, your problem is the Cardinal Payoff variant with the modification that the distribution from which the values are drawn is different - you have unique integers from 1 to $n$. This additional information should allow you to do slightly better than for the Uniform distribution case. To guide you on this - you need to consider the German Tank Problem - specifically that in the first $c$ cases the expected maximum is $\frac{c(n+1)}{c+1}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.