1
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ Can the player buy/sell a fraction number of a droid? $\endgroup$ – xskxzr Dec 9 '19 at 7:24
  • $\begingroup$ @xskxzr The question does not specify that, but I have been assuming that only integer numbers of droids can be bought/sold. I'm also assuming that all prices are integers, I don't think that assumption changes things too much. $\endgroup$ – eatfood Dec 9 '19 at 9:13
  • $\begingroup$ I have read the link you posted and I agree with most of the suggestions put forward by Raphael and yourself. However, in this case, I don't think there is a particular concept in play here, its more of I haven't truly understood where the 'hardness' of this particular problem comes from, and hence can't find the reduction. Also, you mentioned that when asking questions one should try to generalize and avoid asking specific questions, but this particular exercise doesn't resemble anything I've seen before haha. $\endgroup$ – eatfood Dec 9 '19 at 9:25
3
$\begingroup$

You can find a simple reduction from Knapsack or from the Partition Problem (which itself reduces to Knapsack).

Let's do it from the Partition Problem:

Given $n$ integers $S = \{a_1, a_2\ldots, a_n\}$ with even total sum, does there exist a subset whose sum is exactly half the sum of all elements ?

So suppose you are given an instance of the Partition Problem. We construct an instance of the Droid Trader problem as follows:

  • There will be $n$ types of droids, one for each integer in $S$. There will be two planets $s$ and $t$, with a directed edge from $s$ to $t$.
  • On planet $s$, the player can buy a single droid of each type $i$ for a price of $a_i$, and can sell nothing.
  • On planet $t$, the player can sell droids of every type $i$ for a price of $2\cdot a_i$, and can buy nothing.
  • The player starts with $z$ equal to half the sum of all elements in $S$.

Then, it is easy to see that, the player can never end up with more money than $\sum S$. Moreover, he can achieve $\sum S$ if and only if he can buy $\frac{1}{2}\sum S$ worth of droids on the first planet, i.e. there exists a subset of $S$ with sum $\frac{1}{2}\sum S$.

So the original question on the Partition Problem instance is equivalent to asking if the player can end up with $\sum S$ money in the corresponding Droid Trader problem.

Because this is a polynomial time reduction, this proves the claim.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ That is genius! It never crossed my mind to double the selling price of the droids to force the player to spend his coins. I tried this approach but I couldn't find a way prevent the player from just holding on to all his coins. Thanks! $\endgroup$ – eatfood Dec 9 '19 at 12:17
  • $\begingroup$ Yes also I ran into this problem at first. You're welcome :) $\endgroup$ – Tassle Dec 9 '19 at 17:13
1
$\begingroup$

The problem is NP-complete even if the player can buy/sell a fraction number of a droid. We reduce Not-All-Equal 3SAT (NAE3SAT) to this problem.

Given an instance of NAE3SAT with $n$ variables $x_1,\ldots,x_n$ and $m$ clauses, we construct a graph like follows.

s ---> x_1^0 --> x_2^0 ... x_n^0 ---> t
  \          \/                   / 
   \         /\                  /
    -> x_1^1 --> x_2^1 ... x_n^1

That is, in every step, the player chooses to go to exactly one of the planets $x_i^0$ and $x_i^1$.

We construct two types of droids $d_j$ and $d_j'$ for each clause $j$. If clause $j$ is, for example, $x_1\vee \neg x_3\vee x_4$, then there is 1 droid of type $d_j$ in planet $x_1^0, x_3^1$ for sale and 1 droid of type $d_j'$ in planet $x_1^1, x_3^0$ for sale, and there is 1 demand for droids of type $d_j$ in planet $x_4^0$ and 1 demand for droids of type $d_j'$ in planet $x_4^1$. For each type, the price for the player to buy one droid is always 1, and the price for the player to sell one droid is always 2. The player has $M$ money initially where $M$ is a very large number.

Now we can see the fomula is a valid instance of NAE3SAT if and only if the player can hold $M+m$ money when she arrives at $t$.

By the way, this reduction shows that your problem, no matter whether the player can buy/sell a fraction number of a droid, is strongly NP-complete.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.