This question is from chapter 8, exercise 35, of Algorithm Design by Kleinberg and Tardos.
A player in the game controls a spaceship and is trying to make money buying and selling droids on different planets. There are $n$ different types of droids and $k$ different planets. Each planet $p$ has the following properties: there are $s(j, p) \geq 0$ droids of type $j$ available for sale, at a fixed price of $x(j, p) \geq 0$ each, for $j = 1, 2, \dots , n$, and there is a demand for $d(j, p) \geq 0$ droids of type $j$, at a fixed price of $y(j, p) \geq 0$ each. (We will assume that a planet does not simultaneously have both a positive supply and a positive demand for a single type of droid; so for each $j$, at least one of $s(j, p)$ or $d(j, p)$ is equal to $0$.)
The player begins on planet $s$ with $z$ units of money and must end at planet $t$; there is a directed acyclic graph $G$ on the set of planets, such that $s$-$t$ paths in $G$ correspond to valid routes by the player. (G is chosen to be acyclic to prevent arbitrarily long games.) For a given $s$-$t$ path $P$ in $G$, the player can engage in transactions as follows. Whenever the player arrives at a planet $p$ on the path $P$, she can buy up to $s(j, p)$ droids of type $j$ for $x(j, p)$ units of money each (provided she has sufficient money on hand) and/or sell up to $d(j, p)$ droids of type $j$ for $y(j, p)$ units of money (so I'm assuming you can make multiple buy/sells at each planet). The player’s final score is the total amount of money she has on hand when she arrives at planet $t$.
I'm trying to prove this problem is harder than some NP-complete problem, but I am quite stuck. Since the planets are organized in a DAG, I think the 'hardness' of the problem comes from the fact that you can buy and sell many different types of droids at each planet. Also, this problem is a maximation problem, and I don't know many NP-complete maximization problems other than quadratic assignment.
My thought process is that the droids have to represent something, for example choosing vertices of a graph. Then the price of the droid reflects the 'value' in some way; for example in a vertex cover reduction, the droid representing vertex $i$ would have a sale price equal to the degree of vertex $i$ for example.
Something that worked well for me for the previous 30 exercises was to consider a very simple version of the problem. So in this case, I considered cases where the planets were just a line graph, or there are only two types of droids, or each planets sells exactly 1 type of droid and buys 1 type of droid (so you can force the player to buy/sell instead of just holding on to their cash). I try to simplify in this way and see if it starts to resemble other NP-hard problems, which is why I suspect that it should be a vertex-cover or 3-sat reduction.
Any hints would be appreciated such as what problem X should I choose to reduce to Droid Trader Problem, or how should I view this problem (e.g. 3-SAT can be viewed as choosing one out of $2^n$ choices and then checking that the choice satisfies some set of contraints)