Which items to buy if the best one will always be stolen?

Question

The Problem:

A store sells $N$ items. Each item $i$ is priced at $p_i \ge 0$ and you value the $i$th item at $x_i \ge p_i$. You can carry at most two items.

To complicate matters, when you leave the store you will be attacked by a bully who will steal the item you value most among the items you have bought. (If you buy no items the bully leaves you alone; if you buy one item he steals it and if you buy items $i$ and $j$, say, with $x_i \ge x_j$ he steals item $i$).

Which items do you buy?

I am wondering whether this problem has an explicit, "simple" solution. If not, is it possible to prove that there is no simple solution?

The only way of solving it I can come up with is brute force:

Example with $N=3$:

$$x_1 = 10, x_2 = 5, x_3 = 4$$ $$p_1 = 3, p_2 = 2, p_3 = 1.$$

• If you buy two items you can keep either item 2 or item 3 since item 1 would always be stolen.

1. If you want to keep item 2 you must also buy item 1 and so you get $5-(3+2)=0$
2. If you want to keep item 3 you must also buy either item 1 or item 2. In the first case you get $4-3-1=0$; in the second case you get $4-1-2=1.$

• If you buy only one item it will be stolen but you will have paid a positive price for it, so you get less than zero.
• If you buy no item you get zero.

So in this example the optimal thing to do is to buy items 2 and 3.

Answer 1

For each $i$ let $q_i=\min\{p_j|x_j>x_i\}.$ Then the problem is to maximize $x_i-p_i-q_i$.