0
$\begingroup$

Suppose the following situation: we have to buy $n$ goods $g_1,\,\dots,\,g_n$ starting at day 1 and we can't buy more than one good per day.
On day $d$ the prices are $p_1^d,\,\dots,\,p_n^d;\quad p_i^d\lt p_i^{d+1}$, i.e. the prices for the goods keep rising.

Question:
what is the optimal buying strategy if the only available about the goods we have is the price for the current day and the next?
Under which conditions is always buying the good, whose price will increase the most, the optimal strategy?

The actual motivation for the question comes from combinatorial optimization, where one can't foresee all effects of exchanging elements that are subjected to topological constraints e.g. in graph theory.

$\endgroup$

1 Answer 1

3
$\begingroup$

With the information given, for any strategy you might pick, there exists an instance of the game that makes this strategy awful. For example, suppose $n=2$. Let $i$ be the index of the good you buy at day $1$, and suppose that $p_i^3=p_i^2+\epsilon$ and that for all $j\neq i$, $p_j^3=p_j^2+N$ for small $\epsilon$ and very large $N$.

If you want the notion of "optimal strategy" to make sense, you need to give more information. For example, you could ask that the daily price increments follow a given probability law on $\mathbb R_+$.

Assuming you have done so, let $X^d$ be the price increment vector between days $d$ and $d+1$, seen as a random variable in $(\mathbb R_+)^n$. If the $(X^d)_{1\leq i\leq d}$ are independant, then your strategy is optimal. Without independence, this is not always true.

$\endgroup$
1
  • $\begingroup$ That information is sufficient for my purposes; I had observed that the strategy was better than the greedy heuristic for a certain combinatorial problem on geometric graphs in the euclidean plane; specifically turnining a Minimum Spanning Tree into a Hamilton path via a sequence of edge-exchanges $\endgroup$ Commented Aug 4, 2023 at 15:16

You must log in to answer this question.

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