2
$\begingroup$

An item is to be obtained at the minimum possible expected price. It can be obtained by paying a fixed price $F$, or by buying some gambles $G_i=(P_i,q_i)$ from a collection of offers $O=\{G_i|i\in\{0..n\}\}$, where $P_i$ denotes the price and $q_i$ denotes the failure probability of not obtaining the item from this gamble. Each gamble can only be taken some finite number of times.

It is straightforward to exclude gambles that aren't worth it at all by checking that $P_i+q_i*F<F$. So without loss of generality, assume all $n$ remaining gambles in $O$ are worth to exhaust before paying the fixed price.

The question is: What is the optimal order to exhaust them in that minimizes the expected total price $T$?

$$\min_j T_j=P_{j_1}+q_{j_1}*(P_{j_2}+q_{j_2}*(...+q_{j_n}*F)...)$$

(that is assuming each gamble can be bought at most once, but w.l.o.g. this generalizes to any finite number by duplicating offers)

I feel like there should be a straightforward way of doing this as each gamble is fully characterized by just two numbers, but I'm struggling to find some rigorous, clean way of doing so.

Checking all $n!$ possible permutations obviously gets infeasible very quickly, even for small $n$.

Slightly better is building up the sequence bottom-up (i.e. going backward from the end) by constructing them over all subsets and keeping track of the optimal order for any subset. But that still involves something in the order of $2^n$, and it feels even simpler.

My intuition tells me the viability of an individual gamble doesn't actually depend on the global ordering that much, it's just the way of measuring the full expected value that makes it appear like it does so. That it should be possible to construct some total ordering of viability using some priority function, invariant under the insertion or deletion of other offers from the gamble.

Suppose, for example, the expected price if an individual offer in consideration could be infinitely repeated:

$$V_i=P_i+q_i*V_i \Rightarrow V_i=\frac{P_i}{(1-q_i)}$$

My intuition tells me if I just order them by this, it should yield the globally optimal permutation, but I don't know how to prove it.

Is my intuition correct? Could you either show me a counter example where it fails, or show how it's possible to formally prove its correctness?

If it's wrong, is precluding the gambles with $P_i+q_i*F>F$ even safe, or is that wrong too? And is there an easier way to find the optimal permutation that doesn't involve going over all of $O$'s subsets?

Thank you in advance!

EDIT: We may assume $P_i >0$ if it simplifies the analysis.

$\endgroup$
6
  • 1
    $\begingroup$ In the expression for $V_i$ you need to divide instead of multiply with (1-$q_1$). One thing we can see is that in the expected value, F is always multiplied by the same value regardless of the order, so F does not matter for the order. $\endgroup$ Commented Jun 11, 2024 at 13:19
  • $\begingroup$ Silly oversight, you're absolutely right, edited. Keen observation about $F$! $\endgroup$ Commented Jun 11, 2024 at 14:38
  • $\begingroup$ That's actually a really useful clue. We can think of this problem as a composition of linear functions, all of which have slope $\in[0,1)$ and (though not expressly stated) positive y-intercept. The above formula is actually their intersection with $y=x$. For larger inputs, the output will be smaller (injecting that offer in the chain reduces subsequent cost), and for lower inputs, the output will be larger. Since we would only ever add gambles that reduce the cost, any gamble that doesn't reduce cost on $F$ can never be worth it, so the exclusion is confirmed safe. $\endgroup$ Commented Jun 11, 2024 at 14:53
  • $\begingroup$ It's actually telling us a little bit more, namely the earliest point in the sequence (aka latest in the composition) at which a gamble may only be interjected. Since in the order of composition (reverse order of the sequence), the price gets successively lower, once it's below the $V_i$ threshold for that gamble there is no point in adding it at all anymore. This corroborates my suspicion that ordering by increasing $V_i$ yields the optimal sequence, however a proof is still elusive. $\endgroup$ Commented Jun 11, 2024 at 15:11
  • 1
    $\begingroup$ My first thought was to order it by expected value of the cost of doing bet plus buy directly if fail. But that depends on F so can’t be right. In a small example with 3 gambles, you can compute the cost of all 6 strategies. Then when playing around with the gamble stats, it indeed showed that if gambles have equivalent V that leads to order being indifferent for those two gambles. $\endgroup$ Commented Jun 11, 2024 at 15:20

1 Answer 1

Reset to default
1
$\begingroup$

I think I can show that for any given order you will reduce cost if for neighboring gambles you put the one with lower $V_i$ first:

If you write out the expected value of the cost you will see that switching 2 neighboring gambles will only change the terms with the 2 gambles and leave all the other terms the same, so we only need to focus on the 2 terms we are switching:

Before the switch they look like: $xP_{j_n} + xq_{j_n}P_{j_{n+1}}$

After the switch this becomes: $xP_{j_n+1} + xq_{j_n+1}P_{j_{n}}$

,with x the product of all $q_i$ that came before $P_{j_n}$.

By rewriting it, you can now quickly show that: $$xP_{j_n} + xq_{j_n}P_{j_{n+1}}>xP_{j_n+1} + xq_{j_n+1}P_{j_{n}} \Rightarrow \frac{P_{j_n}}{1-q_{j_n}}>\frac{P_{j_{n+1}}}{1-q_{j_{n+1}}}$$

Which is what we were looking for to show that ordering the gambles by $V_i$ gives the lowest expected cost.

$\endgroup$
3
  • $\begingroup$ I think this is almost complete, with two small aspects formally still missing: 1. We need to show the implication in the opposite direction. From objective to heuristic is irrelevant, crucial is that the heuristic implies the objective. 2. To show that this pairwise exchange argument works at any position, not just the last, the terms need to be reformulated to have both an X for the prefix of the objective, as above, and an Y for the suffix (like F). So if the heuristic order transfers to $X*(P_{j_i}+q_{j_i}*(P_{j_{i+1}}+q_{j_{i+1}}*Y))$ for any nonnegative X,Y, we are done. $\endgroup$ Commented Jun 13, 2024 at 7:04
  • 1
    $\begingroup$ Yes, for point 1, we still need to show that if no pairs can be exchanged to improve, then we have a minimum. For point 2, I think we are ok, because what I have shown does hold for any neighboring pair, not just the last. That is because of the remark that the terms after don’t change by switching 2 previous pairs. $\endgroup$ Commented Jun 13, 2024 at 7:11
  • $\begingroup$ Oh, right - what we have is just local optimality: No pairwise exchanges of neighbors yield an improvement on the sequence by ordered $V_i$. That by itself is not yet sufficient to prove global optimality, that there cannot be a cheaper sequence only reachable by a more drastic re-ordering. Perhaps we could use that the implication goes both ways, combined with this? Any permutation is generated by adjacent swaps... but that doesn't prove for any decreasing permutation exists a monotone decreasing sequence of swaps. :\ $\endgroup$ Commented Jun 13, 2024 at 10:03

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.