Decision Making Theory, Maximin

Question

1 of the items in a batch of 11 is damaged. The items can be sent for checking in groups of any number; however the group containing the damaged item will be disposed of. Checking fee for each group is $\$$1000 regardless of the number of items it contains. Once found undamaged, an item can be sold for $\$$1000. What plan should you use to send in items for checking to maximise returns under the Maximin criterion?

PS: Plan means, for example, 5-4-1-1 (the last one won't certainly be sent for checking because it'll be obvious if it's defective or not); 4-4-3; 2-2-2-2-2-1; etc.

I know the correct answer but how do we get to it? It is impossible to list out all possible combinations...

Answer 1

EDIT

After reading @Bram28's answer, I realized my mistake, I included one extra checking fee that was unnecessary, leading to extra costs... Kudos to him for finding the right answer. In this edit, I will correct my original answer through comments

like this

to show an alternative approach for reaching the result.

---

Say you have $n$ items in a batch. Consider $k$ integers $a=(a_1,\ldots,a_k)\in\mathbb N^k$. For $a$ to be a proper plan, it must satisfy

• $\sum_{i=1}^ka_i=n$
• $\forall i$, $a_i\ge 1$

The maximin criterion is about maximizing the minimum gain. Given a plan $a$, the return is the total number of items sold, minus the number of inspections paid. If the damaged item was in the $i$-th group, the return is $(n-a_i)-i$ (times \$1000).

If $i=k$ however, we do not need to pay the $k$-th fee because we know the defective item must be in that group. This yields a return of $(n-a_k)-(k-1)$ instead.

Finding the minimum gain of plan $a$ coincides with finding the index $i$, $1\le i\le k$, such that $a_i+i$ is maximum. In other words we want to find $$ \min_{a\text{ a plan}} \max_{i} (a_i+i) = \min_{k} \min_{a\in\mathbb N^k} \max_{1\le i\le k} (a_i+i) $$

The formula above is erroneous because of the forgotten case $i=k$. The general idea is still valid though.

The question we're going to have a look at now is, given a fixed number of groups $k$, what's the plan $a\in\mathbb N^k$ with the best maximin criterion. Knowing that, we can then have a look at how things change for various values of $k$. We define the companion series of $k$ positive integers $b^a$, with $b^a_i=a_i+i$.

and $b^a_k=a_k+k-1$.

One property of $b^a$ is that the sum of its terms is independent from the initial plan $a$. $$ \sum_{i=1}^k b^a_i=\sum_{i=1}^k (a_i+i)=\left(\sum_{i=1}^ka_i\right)+\left(\sum_{i=1}^ki\right)=n+\frac{k(k+1)}2 $$

$ \sum_{i=1}^kb^a_i = n-1+\frac{k(k+1)}2$

Now, there's that principle that if you try to split a number $N$ of items into $k$ groups, one of the group will contain at least $N/k$ elements. With $N=n+k(k+1)/2$ that means however you choose your plan, at least one group in that plan will have at least $n/k+(k+1)/2$ items in it.

Bonus comment, here we want to split the expected loss rather than actual items, so that wherever the defective items actually ends up, the loss incurred will be the same.

Since we're dealing with integers, that means that whatever plan $a$ you choose, you will have $$ \max_{1\le i\le k} a_i+i \ge \left\lceil \frac nk+\frac{k+1}2 \right\rceil $$

$ \max_i b_i\ge \left\lceil \frac{n-1}k+\frac{k+1}2 \right\rceil $

Now, does there always exist a plan $a$ that reaches that lower bound? The answer is a definite yes, just choose $a_i=\text{bound} -i$.

and $a_k=\text{bound} -(k-1)$.

In general, you will probably end up with more than $n$ items, but just remove some from wherever you want and you're good to go.

Now if you just check out what are the different values of the lower bound for $n=11$ and $1\le k\le 11$, you'll quickly figure out what plans will achieve your maximin criterion. Here's a table of values.

\begin{array}{c|c|c} k & \left\lceil \frac{11}k+\frac{k+1}2 \right\rceil & \left\lceil \frac{10}k+\frac{k+1}2 \right\rceil \\ \hline 1 & 12 & 11\\ 2 & 7 & 7\\ 3 & 6 & 6\\ 4 & 6 & 5\\ 5 & 6 & 5\\ 6 & 6 & 6\\ 7 & 6 & 6\\ 8 & 6 & 6\\ 9 & 7 & 7\\ 10 & 7 & 7\\ 11 & 7 & 7 \end{array}

I added an additional column above. So there should be plans with 4 or 5 groups that reach a minimum max-loss of \$5000, or in other words a maximin return of \$6000. Assuming a loss pattern of $(5,5,5,5)$ for $k=4$, we obtain a plan of $(4,3,2,2)$. For $k=5$, the loss pattern is $(5,5,5,5,5)$ and that corresponds to a plan of $(4,3,2,1,1)$.

And here we reach the tragedy that my development doesn't coincide with the answer given by your teacher, but let's proceed regardless. From my table, we can just pick $k=3$, and that correspond to the "average maximum loss" of $6$. The "ideal" plan is then $(5,4,3)$, but this sums to 12. So instead we can just take the "real" plan $(4,4,3)$, or $(5,3,3)$ or $(5,4,2)$. These respectively correspond to a loss of $(5,6,6)$, or $(6,5,6)$, or $(6,6,5)$, depending in which group the defective item was. Notice that you cannot redistribute the number of elements in the groups so as to lower the maximum loss, and that maximum loss is indeed \$6000 in every cases. In other words, a minimum return of \$5000.

I don't see any obvious flaw in my reasoning, but hat may be dues to tiredness. If your teacher gave you an example of plan with a minimum return of \$6000, could you share it? I'd like to have a look to decide whether I'm wrong or not...

I was obviously wrong...

---

---

Edit 2: further discussion -- on the influence of $n$

Let the function $f_n$ be \begin{align*} f_n: [1,n] &\to \mathbb R\\ k &\mapsto \frac{n-1}k +\frac{k+1}2 \end{align*} In the analysis above, I brute forced the issue of finding the minimum of $f_n$ for integer values of $k$, because I was too lazy to do it properly at the time. Looking at $f_n$ as a function defined over the interval of real numbers $[1,n]$, we can compute its derivatives. $$ \frac{\partial f_n}{\partial k}=-\frac{n-1}{k^2}+\frac 12 $$ $f_n$ admits a minimum at the real number $k_\text{min}$ that satisfies $k_\text{min}^2=2(n-1)$. Now what happens if we restrict $f_n$ to integer values of $k$? Notice that $$ \frac{\partial^2f_n}{\partial k^2}=\frac{2(n-1)}{k^3}>0 $$ which means that $f_n$ is convex. The convexity of $f_n$ guarantees that the minimum of $f_n$ restricted to integers is reached at either $\lceil k_\text{min} \rceil$ or $\lfloor k_\text{min} \rfloor$ (or both).

---

Assuming there exists an integer $m$ such that $n-1=\frac{m(m+1)}2$, we deduce that the real $k_\text{min}$ for which $f_n$ is minimum is somewhere in between $m$ and $m+1$. So the minimum over integer values is at $m$ or $m+1$. It just so happens that in this particular case, we have $f_n(m)=f_n(m+1)=m+1$, so both values yield a minimum.

If we pick $k=m$ we end up with the plan $(m,m-1,m-2,\ldots,4,3,2,2)$, whereas for $k=m+1$ we get $(m,m-1,m-2,\ldots,4,3,2,1,1)$. So as @Bram28 observed, if $n$ has the form $n=\frac{m(m+1)}2+1$ the plan $(m,m-1,m-2,\ldots,3,2,1,1)$ with $m+1$ groups is always (among) the best plans.

In fact, because $f_n$ is strictly convex, it is one of the only two optimal plans. Specifically, it is the optimal plan with the greatest number of groups.

---

Now let's have a look at other values of $n$. There are always integers $m,r$ such that

• $n-1=\frac{m(m+1)}2+r$
• $0 \le r < m+1=\frac{(m+1)(m+2)}2-\frac{m(m+1)}2$

So $k^2_\text{min}=m(m+1)+2r$. Knowing that $0\le 2r\le 2m$ we get $$ m^2 < m(m+1) \le k^2_\text{min} \le m(m+1)+2m < (m+2)^2 $$ This time we're left with three integers values: $m,m+1,m+2$. \begin{align*} f_n(m) &= m+1 +\frac rm \\ f_n(m+1) &= m+1 +\frac r{m+1} \\ f_n(m+2) &= \frac{m(m+1)+2r}{2(m+2)}+\frac{m+3}2 = \frac{2m^2+6m+6+2r}{2(m+2)} = \frac{(m+1)(m+2)+r+1}{m+2}\\ &= m+1 +\frac{r+1}{m+2} \end{align*} In this context, the $m+1$ part can be disregarded and we reduce to basically compare the values of $r/m$, $r/(m+1)$ and $(r+1)/(m+2)$. Among those three, $r/(m+1)$ is always minimum for all values $r$, $0\le r<m+1$.

This means that there is a best plan with $m+1$ groups, it will achieve the minmax loss of $$ \lceil f_n(m+1)\rceil = \begin{cases} m+1 &\text{if $r=0$}\\ m+2 &\text{otherwise} \end{cases} $$ If I didn't misread @Bram28's comment (English isn't my first language, so apologies if I did), then I'd disagree with his observation (?). We only add $1$ to the minmax loss of $n=\frac{m(m+1)}2+1$, one single time (and not every time), until we reach the next integer of the form $n=\frac{(m+1)(m+2)}2+1$.

This seems coherent, because if the plan $(m+1,m,\ldots,3,2,1,1)$ is optimal for $n=\frac{(m+1)(m+2)}2+1$, it's easy to find plans for $n\le\frac{(m+1)(m+2)}2+1$ whose max loss will be no greater than the max loss of $(m+1,m,\ldots,3,2,1,1)$. It indeed suffices to subtract some elements from the groups. So when $n$ is stuck in between $$\frac{m(m+1)}2+1< n\le\frac{(m+1)(m+2)}2+1$$ if we pick a plan "in between" $(m,m-1,\ldots,2,1,1,0)$ and $(m+1,m,\ldots,3,2,1,1)$, we will obtain a max loss between $m+1$ and $m+2$. Because $(m,m-1,\ldots,2,1,1,0)$ is optimal for $n=\frac{m(m+1)}2+1$ with the greatest number of (non-trivial) groups, it's impossible to get a minmax loss of $m+1$ if $n>\frac{m(m+1)}2+1$. Any such plan would require more than $m+1$ groups, from which we would deduce the existence of a plan for $\frac{m(m+1)}2+1$ with strictly more (non-trivial) groups than $(m,m-1,\ldots,2,1,1,0)$, which is a contradiction.

---

Tl;dr: Find the integer $m$ such that $$ \frac{m(m+1)}2 < n-1\le\frac{(m+1)(m+2)}2 $$ Subtract elements from the plan $(m+1,m,m-1,\ldots,3,2,1,1)$ until it sums to $n$. The resulting plan reaches the minmax loss for $n$, that minmax loss is precisely $m+2$.

Answer 2

I was able to determine that the best plan is:

$4-3-2-2$

or

$4-3-2-1-1$

with indeed a worst-case return of $6000

Below I'll explain the basic strategy I used to obtain this answer. I was able to avoid completely brute forcing this, but I still ended up having to look at quite a few different plans (or 'plan-schemes', really), so I still want to think more about this problem and see if there is some general pattern that I can prove (probably using induction) is the best. But anyway, here's how I did it:

OK, first of all, let's approach this problem generally, i.e. not specifically for $11$ items, but let's say we want the best plan for $n$ total items. And let's say that $maxmin(n)$ is the maximum return you can get with $n$ items.

(And to keep the math simple, let's compute the return simply as number of items sold - number of fees paid, so I can avoid having to multiply everything by 1000)

Now, a key insight is that you can now set this up as a kind of problem involving recursive functions. For example, for any $n$: a plan of the form

$1-....$

and where the defective item is not that very first item, has a worst-case return of $maxmin(n-1)$, which not only shows the kind of recursion I am referring to, but this also shows that for any $n$: $maxmin(n) \ge maxmin(n-1)$

Now, obviously with $1$ item the best 'plan' is $1$ (and since that is the last batch, you don't send it in at all, meaning that you sell $0$ items and pay $0$ fees for a total return of $0$). So: $maxmin(1)=0$

It's also fairly easy to find that $maxmin(2)=0$, as the only plans are $2$ (meaning again nothing gets checked and nothing gets sold .. let's call this the 'all-zero-plan') and $1-1$ (which we already saw leads to a return of $maxmin(1)=0$)

And for $n=3$: $3$ is again the 'all-zero plan', and any plan starting with $1-$ gives a return of $maxmin(2)=0$, so the only interesting plan is $2-1$, but if the defective item is in the first batch you still get $0$ return. So, $maxmin(3)=0$

For $n=4$, the only plans other than the all-zero-plan and plans starting with $1-...$ are $3-1$, $2-2$, and $2-1-1$. Now, the $3-1$ plan gets a worst-case of $0$ if the defective item is in the first batch. Now, instead of analyzing $2-2$ and $2-1-1$ separately, it makes more sense to analyze this using the general 'plan-scheme'

$2-plan2$

meaning that the first batch is $2$, and if we want to do anything after that, we'll do whatever the best plan is for $2$ items.

We can further analyze this 'plan-scheme' as follows

$\color{red}{2}-\color{blue}{plan2}$

$\color{blue}{2}-\color{red}{plan2}$

where the red indicates that the defective item is in that part of the plan (and the blue is that it's not there ... not sure why I give it a color at all, but hey, it looks pretty)

In the first case, the return is $-1+2=1$

In the second case, the return is $-1+2+maxmin(2)=1+0=1$

So, we see that $maxmin(4)=1$: the first time we can actually get a positive return.

We can follow a similar analysis for $n=5$. That is, any plan starting with $1-$ gives us $maxmin(4)=1$, the all-zero-plan $5$ gives us $0$, leaving us with $3$ other plan-schemes:

$2-plan3$

$3-plan2$

$4-plan1$

To further reduce your search, you can show that you do not have to consider any plan-scheme $k-plan(n-k)$ with $k>n-k$ (i.e where the first batch is the majority of all the items), because the plan-scheme $(n-k)-plan(k)$ will always be just as good or better (e.g plan-scheme $3-plan2$ will be same or worse than plan-scheme $2-plan3$). Here's why:

Assume $k > k-n$ and consider plan-scheme $k-plan(n-k)$. Again, we have two cases to consider:

$\color{red}{k}-\color{blue}{plan(n-k)}$

$\color{blue}{k}-\color{red}{plan(n-k)}$

First case gives return of $-1+n-k$

Second case gives return of $-1+k+maxmin(n-k)$

Since $k>n-k$, that means return in second case is greater or equal to return in first case, meaning that the worst-case return of this plan-scheme is $-1+n-k$

Compare this with plan-scheme $(n-k)-plan(k)$:

$\color{red}{n-k}-\color{blue}{plan(k)}$

$\color{blue}{n-k}-\color{red}{plan(k)}$

First case gives return of $-1+k$, which is greater or equal to $-1+n-k$

Second case gives return of $-1+n-k+maxmin(n-k)$, which is also greater or equal to $-1+n-k$

So, whichever is the worst-case as far as the second plan-scheme goes, the second plan-scheme has a greater or equal return than the first plan-scheme.

So, for $n=5$ we really only have to consider:

$2-plan3$ .. which leads to a return of $1$:

$\color{red}{2}-\color{blue}{plan3}$ : return = $-1+3=2$

$\color{blue}{2}-\color{red}{plan3}$ : return = $-1+2+maxmin(3)=1+0=1$

OK, I hope you gpot the general idea, and so now it is a matter of working up through the numbers, but with this analysis it really isn't too bad. In particular, for $n=7$ you get that the best plan is $3-plan4$, i.e. $3-2-2$ or $3-2-1-1$, and that accordingly, $maxmin(7)=3$. After some more steps you get eventually to the $4-3-2-2$ or $4-3-2-1-1$ plan for $n=11$ with $maxmin(11)=6$, i.e. a maxmin return of $6000

Here, by the way, are the best plans (actually, some have multiple best plans, so I just the shortest plan) and maxmin values I found:

\begin{array}{c|c} n & plan(n) & maxmin(n)\\ \hline 1 & 1 & 0\\ 2 & 2 & 0\\ 3 & 3 & 0\\ 4 & 2-2 & 1\\ 5 & 2-3 \ or 3-2 & 1\\ 6 & 2-plan(4) \ or 3-3 & 2\\ 7 & 3-plan(4) & 3\\ 8 & 2-plan(6) \ or \ 3-plan(5) \ or \ 4-plan(4) & 3\\ 9 & 2-plan(7) \ or \ 3-plan(6) \ or \ 4-plan(5) & 4\\ 10 & 3-plan(7) \ or \ 4-plan(6) & 5\\ 11 & 4-plan(7) & 6\\ \end{array}

By the way, for higher numbers, I also made the observation that when $n=2k$, then the plan-scheme $(k)-plan(k)$ has a worst-case return of $k-1$ (you can do the analysis .. it's not hard to see). This is matched by $n=4$, $n=6$, and $n=8$, but for $n=10$ we get a return better than $5-1$, and so from this point on there is no need to consider any such 'inferior' plan-schemes.

Finally, I bet for $n=16$ the best plan is $5-4-3-2-2$, for $n=22$ it's $6-5-4-3-2-2$, etc. ... but like I said, I need to study this more to prove it, and of course to prove the in between cases as well.