0
$\begingroup$

A bag contains $n$ items with different values. The total value is $1$. I am allowed to pick one item, and pick the item with the maximal value. Obviously, in the worst case I will get a value of $1 \over n$.

Now, suppose the bag is shaken so that some items break, and their value decreases. Specifically, there are $n$ known constants, $p_1,...,p_n \in (0,1]$, such that the value of item $i$ is now $p_i v_i$ (where $v_i$ is the original value). What is now the value I can get in the worst case (as a function of the $p_i$'s)?

Formally, I look for a lower bound on the solution of the following maximization problem:

$$ \max_{i=1..n} p_i v_i $$ $$ s.t. \sum_{i=1..n} v_i = 1$$

The lower bound is a function of the parameters $p_1,...,p_n$.

EXAMPLE: Suppose $n=2$, $p_1=1$, $p_2=0.5$. My value is the maximum between $v_1$ and $0.5 v_2 = 0.5(1-v_1)$. The worst case is when $v_1 = {1 \over 3}$. In this case the two expressions are equal, and my value is ${1 \over 3}$.

SOME BOUNDS:

  • If only a single item has a value (i.e. $v_i=1$ for some $i$), then in the worst case my value will be $p_i$. So in general, the lower bound is at most $\min_{i} {p_i}$.
  • If all items have the same value (i.e. $v_i={1 \over n}$ for all $i$), then in the worst case my value will be $\max_{i} {p_i \over n}$. So in general, the lower bound is at most ${\max_{i} p_i} \over {n}$

These two bounds are not tight: in the example I gave above, these bounds are both $1 \over 2$, while the actual lower bound is $1 \over 3$. Can you find a tight lower bound?

$\endgroup$
1
$\begingroup$

The worst case distribution of $v_i$ is when the values of the items equalise as you noticed, which is when each $v_i$ is inversely proportional to $p_i$, i.e. when $$v_i = \dfrac{\frac1{p_i}}{\sum \frac1{p_i}} $$

Clearly for this distribution $p_i v_i = \dfrac{1}{\sum \frac1{p_i}}$ for all $i$ and you have the desired lower bound.

In the specific example you mention, this gives $\dfrac{1}{\sum \frac1{p_i}} = \frac{1}{1+2} = \frac13$.

$\endgroup$
  • $\begingroup$ Thanks for the quick reply. $\endgroup$ – Erel Segal-Halevi Nov 2 '13 at 21:04

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.