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 Answer 1

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$
1
  • $\begingroup$ Thanks for the quick reply. $\endgroup$ Nov 2, 2013 at 21:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .