1
$\begingroup$

"Buy and Resell Problem" can be described in the following way:

There are $n$ cities. For each city, the price of products in this city is given (a positive number). Now a person will travel from city 1 to city $n$, one by one. When reaching a city, he can buy exactly one product with the price in this city, or sell exactly one product if he currectly has at least one product. He can also do nothing and then go on to the next city. The problem is how to plan a strategy so that he can earn maximal money. He has unlimited money initially.

For example, if $n=5$ and the prices are 3,2,5,1,4, then the maximal profit he can earn is $5-2+4-1=6$.

There is a correct greedy algorithm to this problem. When reaching city $i$, consider all $j$ in $1 ... i-1$, and find a $j$ with lowest price such that he doesn't buy a product in city $j$ (he could have sold a product in city $j$). If such $j$ does not exists or the price of city $j$ is higher than city $i$, he simply does nothing in city $i$. Otherwise he buys a product in city $j$ and sells it in city $i$. If he has sold a product in city $j$, it means he does nothing in city $j$ after finishing the $i$th city. The algorithm runs all $i$ in increasing order, and finally gives the best strategy.

The pseudo-code can be written as:

maintain a set s which is empty initially
maintain a boolean array named sell whose items are false initially
profit = 0
for i in 1 to n
  if s is not empty  
    select an item j in s with the loweset price  
    if price_j is lower than price_i  
      profit += price_i - price_j
      if sell_j == true
        sell_j = false
      else
        erase item j from set s
      endif
      sell_i = true
    endif
  endif
  insert i to set s
endfor
output profit

The solution is quite simple and can be easily implemented using a priority_queue, which takes $\Theta(n \log n)$ time in total, but how to prove its correctness?

$\endgroup$
  • $\begingroup$ cs.stackexchange.com/q/59964/755 $\endgroup$ – D.W. Sep 15 '18 at 15:50
  • $\begingroup$ I read the tutorial, which seems to be a quite general answer on greey algorithm proofs, and the example there is really easy. I think using the technique there to prove this problem may not be easy. $\endgroup$ – zbh2047 Sep 15 '18 at 16:14
  • $\begingroup$ It might, or it might not; the only way to know is to try. I would suggest that you give it a try, then update your question with your progress so far and where you got stuck. I suspect you are more likely to receive help that way. $\endgroup$ – D.W. Sep 15 '18 at 16:25
  • $\begingroup$ I don't get it. How many different products are on sale in every city? Just one? $\endgroup$ – gnasher729 Sep 16 '18 at 21:11
  • $\begingroup$ Yes, the product has different prices in different cities. $\endgroup$ – zbh2047 Sep 17 '18 at 7:19
2
$\begingroup$

Summary: It is proposed to label the simple and intriguing algorithm given in the question as Adaptive Greedy. Several characterizations of the best strategy are presented. Also included is a rigorous and nontrivial proof of the algorithm. Some interesting original exercises and topics are attached.


Reformulation in mathematical terms

Let $a..b$ stand for the integers from a to b inclusively.

Let us fix $n\ge 2$ and $p(i)>0$, the price of an item in city $i \in 1..n$ (All items are the same except their prices). Assume all prices are different. This assumption is not necessary in order to establish the arguments, the concepts and conclusions below. However, it does simplify them significantly. For example, the algorithm becomes deterministic, producing the same output given the same input.

A strategy $s$ is a function from $1..n$ to $\{1,0,-1\}$, where $1,0$ and $-1$ mean buying, passing and selling respectively.

Given a strategy $s$, let $h_s(i)=\sum_{j\in 1..i}s(j)$ be the number of items held right after city $i$ and also let $h_s(0)=0$. A strategy is an admissible strategy if $h_s(i)\ge0$ for all $i$; otherwise it is an inadmissible strategy. We will only consider admissible strategy unless stated otherwise.

The profit made by strategy $s$ is profit$(s)=\sum_{i\in 1..n} -s(i)p(i)$. If strategy $m$ makes the maximal profit, that is, profit$(m)=\max_s($profit$(s))$, then we say $m$ is a best strategy. Since there are finitely many strategies, there must exist at least one best strategy.


The adaptive greedy algorithm that returns the best strategy

Here is the pseudocode in Python style for the adaptive greedy algorithm. It is the same as the pseudocode in the question except that it uses the self-explanatory terms defined above and that it returns the best strategy instead of the maximal profit. We will prove that it returns the unique best strategy shortly.

Input:   
  price $p(i)$ for $i\in 1..n$.  
Procedure:
  Let s be the all-passing strategy, i.e., s(i)=0 for i in 1..n
  For each city from 1 to n:
    Try finding the previous city where s passes or sells with the \  
       lowest prices that is lower than the price at the current city.
    If found, let s sell in the current city and change its action \   
       at the city found from pass to buy or from sell to pass. 
Output:
    strategy s

The above algorithm, or its equivalent version given in the question, will be referred to as "this algorithm".


Is this algorithm a greedy algorithm and why is it better called adaptive greedy?

At each city, given all admissible pairs of choices of an action in the current city and a change of the action in a previous city, this algorithm selects the pair of choices that can increase the profit the most if it is possible to increase the profit. Otherwise, this algorithm does nothing. That locally optimal selection of admissible choices at each successive city is why we call this algorithm greedy.

Readers might wonder why I explain this algorithm can be classified as greedy, a fact that seems obvious and is assumed by the questioner. That classification is, in fact, not conclusive at all. In fact, the Wikipedia entry on greedy algorithm says the following.

Greedy choice property
We can make whatever choice seems best at the moment and then solve the subproblems that arise later. The choice made by a greedy algorithm may depend on choices made so far, but not on future choices or all the solutions to the subproblem. It iteratively makes one greedy choice after another, reducing each given problem into a smaller one. In other words, a greedy algorithm never reconsiders its choices.

Optimal substructure
"A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to the sub-problems."[2]

Note that this algorithm reconsiders all of its choices made so far when it makes every new choices. When this algorithm runs for cities 1, 2, 3, 4, 5 with prices 1, 2, 3, 4, 5 respectively, the unique optimal solution returned by it, buying in city 1 and 2 and selling in city 4 and 5, does not contain any optimal solution to any sub-problem it has considered except for two cities. It is clear this algorithm is not an ordinary greedy algorithm. Nor does it belong to dynamical programming in its usual sense. Readers can also check some answers to does every greedy algorithm have matroid structure.

Considering the definition and explanations in the Wikipedia, I propose to label this algorithm as an adaptive greedy algorithm, a greedy algorithm in the more general sense of "greedy". More precise definitions of adaptive greedy algorithm will be referenced here after they become available elsewhere.

Henceforth, this algorithm will also be referred as "this greedy algorithm" or "this adaptive greedy algorithm".


Why is it not easy to prove this greedy algorithm is correct?

All greedy algorithms other than this algorithm I have seen so far build larger optimal solutions by keeping the smaller optimal solutions intact and adding one more element. Their correctness are often proved by one of the following three strategies, which are not necessarily mutually exclusive.

  • "Staying Ahead". Show that after each step of $G$, its solution is at least as good as any other algorithm's.
    This proof technique applies to Dijkstra's algorithm that finds the shortest path between nodes in a graph and the algorithm that always selects next interval of earliest ending time to find the most compatible interval in activity selction problem (which is also a kind of interval scheduling).
  • "Unimprovable Solutions". Give any other solution, we can gradually improved it until it becomes unimprovable. Show all unimprovable solutions give the same result or there is only one unimprovable solution. Show that the solution found by greedy algorithm is unimprovable.
    This proof technique applies to the usual greedy algorithms for problems such as Interval Scheduling for Minimal Maximum Lateness and others [1] [2] [3] [4] [5].
  • "Always promising". If $G$ is a weighted matroid or greedoid, its standard greedy algorithm adds one more element to the current result subset in each stage, always promising there is a desired subset with maximal total weight that contains the result subset so far. When the algorithm ends, that promised desired subset will become none other than the result subset. The way to keep the promise is to use exchange of elements. This proof technique applies to most of problems tagged with "greedy algorithm" including Kruskal’s algorithm or Prim's algorithm for minimal spanning tree.

However, as observed before, the new decision made by this algorithm at each city may, more often than not, modify the decisions for previous cities. In fact, the decision made at the last city may modify the selected action of the first city that has stayed the same for all previous partial solutions. This modification makes it non-trivial to prove the correctness of this simple algorithm. I encourage interested readers to try proving it. Any proof that is easier than the proof below will be a nice surprise.

In fact, there is not a single proof of the correctness of this algorithm as far as I have searched. Many answers, articles or online programming contests may explain clearly the greediness (in its plain sense as in English) of this algorithm or provide vast numerical evidences, which are still, however, far from a rigorous proof of its correctness.

It turns out only the second proof strategy, "unimprovable solutions" can be applied to this adaptive greedy algorithm successfully, as shown in a later section of this answer. There is a new twist, though. The uniqueness of the unimprovable solution can only be established by induction with the help of applying this algorithm. I am stilling searching for ways to show that uniqueness directly without using this algorithm.


The characterization theorem on the best strategy

An increasing integer pair $(i,j)$ is said to be $s$-clearance-separated if $h_s(z)=0$ for some $z\in i..(j-1)$.

A strategy $s$ to be said to improvable at two selected cities if the following conditions hold.

  • (room to improve) $s$ buy or pass at a lower price in one city but buy or pass at a higher price in the other city. Assume the former city is city $i$ and the other city is city $j$.
  • (no obstruction to switch) $i>j$ or $i<j$ and $(i,j)$ is not $s$-clearance-separated.

A strategy $s$ is unimprovable if $h_n(s)=0$ and it is not improvable at any two cities.

(The characterization theorem) The following four propositions about a strategy $s$ are equivalent.

  1. (best strategy) $s$ is a best strategy.
  2. (unimprovable strategy) $s$ is unimprovable.
  3. (output of the greedy algorithm) $s$ is the unique strategy produced by this adaptive greedy algorithm.
  4. (anatomy of the best strategy) There are integers $0=i_0\lt i_1\lt i_2\lt\cdots \lt i_t=n$ such that $h_s(i)=0$ if $i=i_j$ for some $j$ and $h_s(i)\gt0$ otherwise. That is, $i_j$'s are all clearance cities where he ends up with no item in his inventory. Call cities $(i_{k-1}+1)..i_k$ of term $k$.
    • If $s$ buys in a city of some term and sells in a city of the same term or a previous term, the buying price is smaller than the selling price.
    • If $s$ buys in a city of some term and passes in a city of the same term or a previous term, the buying price is smaller than the passing price.
    • If $s$ passes in a city of some term and sells in a city of the same term or a previous term, the passing price is smaller than the selling price.
    • Each passing price happens in a city of a different term.
    • All passing prices form a decreasing sequence.

Proof of the theorem

"best strategy $\Rightarrow$ unimprovable strategy": Suppose strategy $s$ is not unimprovable.

If $h_s(n)>0$, then we can find city $b$, the last city where $s$ buys. Construct $s'$, the strategy that is the same as $s$ except $s'$ passes in city $b$. Since $h_{s'}(i)=h_s(i)$ if $i\lt b$ and $h_{s'}(i)=h_s(i)-1\ge h_s(n)-1\ge 0$, $s'$ is an admissible strategy. Since $\text{profit}(s')=\text{profit}(s)+p(b)$, $s'$ makes bigger profit than $s$.

If $h_s(n)=0$, then we can find two integers $i,j\in 1..n$ such that $p(i)<p(j)$ such that one of the following two cases happens.

  • $s(i)=s(j)=0$ or $s(i)<s(j)$. Furthermore, $i<j$.

    Let $s'$ be the strategy that is the same as $s$ except that $s'(i)=s(i)+1$ and $s'(j)=s(j)-1$. Since $h_{s'}(t)\ge h_s(t)$ for all $t$, $s'$ is an admissible strategy. We have, $$\text{profit}(s')-\text{profit}(s)=-p(i)+p(j)\gt0$$

  • $s(i)=s(j)=0$ or $s(i)>s(j)$. Furthermore, $i<j$ and $(i,j)$ is not $s$-clearance-separated.

    Recall that $h_s(t)\ge0$ for all $t$ and, since $(i,j)$ is not $s$-clearance-separated, $h_s(t)\ge1$ for all $t\in i..(j-1)$. Let $s'$ be the strategy that is the same as $s$ except that $s'(i)=s(i)-1$ and $s'(j)=s(j)+1$. Since $h_{s'}(t)= h_s(t)$ for all $t\not\in i..(j-1)$ and $h_{s'}(t)= h_s(t)-1$ for all $t\in i..(j-1)$, $h_{s'}(t)\ge0$ for all $t$. That is, $s'$ is an admissible strategy. We have, $$\text{profit}(s')-\text{profit}(s)=p(i)-p(j)\gt0$$

So in all cases, we have found an admissible strategy that makes more profit then $s$.

"unimprovable strategy $\Rightarrow$ output of the greedy algorithm": We will use mathematical induction on $n$.

The base case, $n=2$ is easy. In fact, we can extend the whole exposition to include the case when $n=1$, which becomes the obviously-true base case.

Suppose the implication is true for $n$ cities. Now consider the case of $n+1$ cities. Let $w$ be an unimprovable strategy on $1..(n+1)$ for some price function $q$. Since $w(n+1)=h_w(n+1)-h_w(n)=-h_w(n)\le 0$, there are two cases.

  • $w(n+1)=0$. That means, $h_w(n)=0$. Let $s$ be the restriction of $w$ to $1..n$. Then $s$ is an unimprovable strategy on $1..n$ for the same prices as $q$. Then $s$ is the uniqued strategy produced by the greedy algorithm running up to city $n$. If we continue to run the greedy algorithm at city $n+1$, it must choose to passes in that last city since $w$ is unimprovable. That is, the greedy algorithm will produce $w$.

  • $w(n+1)=-1$. That means, $n+1$ is a clearance city where $w$ sells. Treating 0 as an clearance city if necessary, let $c$ be the last clearance city before $n+1$. Let $k$ be the city among $(c+1)..n$ where $w$ passes or buys with the highest price. Let $s$ be the strategy on $1..n$ that is the same as $w$ except that $s(k)=w(k)-1$. Then we can verify that $s$ is an unimprovable strategy on $1..n$ for the same prices as $q$. Then $s$ is the unique strategy produced by the algorithm running up to city $n$. If we continue to run the algorithm at city $n+1$, we can verify that it will select to sell in that city as well as change the action in city $k$ from $s(k)$ to $w(k)$. That is, the greedy algorithm will produce $w$. (There are quite some details left out in this part of the proof. Interested readers may take a look at Exercise 0.)

So, we have shown the implication is also true for $n+1$.

"output of the greedy algorithm $\Rightarrow$ best strategy" Let $s$ be the unique strategy generated by the greedy algorithm. Let $b$ be a best strategy. Then $b$ must be an unimprovable strategy and, then, must also be the unique strategy generated by the greedy algorithm as we just proved.

"unimprovable strategy $\Leftrightarrow$ anatomy of the best strategy". The latter one is basically a careful refinement of the former one into cases.


Beyond this problem

There are multiple variations and possible generalizations. It should be a nice topic for an undergraduate student or a master student to look further into this phenomenon, since this adaptive greedy algorithm does not fit into the framework of matroid or greedoid.

Please leave a comment if anyone wants to collaborate on this topic. Please leave a comment if anyone encounters some literature that looks like applicable, especially in integer linear programming theory or generalized greedoid or submodular functions.


Some exercises and topics

The answers to all the exercises are known. However, topics are much harder, to which I do not claim to know an answer or verify the answer.

Exercise 0. Fill the missing details in the proof of "unimprovable strategy $\Rightarrow$ output of the greedy algorithm". As a hint, "anatomy of the best strategy" may help you get a better understanding of the cities in the last term. (Thanks to user zbh2047, the questioner, who points out a missing case in a previous more-complex formulation of "unimprovable strategy")

Exercise 1. Suppose the prices in different cities can be the same. Then there might be multiple best strategies. Show that the algorithm, after slight modification, is able to find all best strategies.

Exercise 2. By switching buying and selling, describe a greedy algorithm that starts from city $n$, moving backwards. Prove its correctness.

Exercise 3. Suppose he can only either buy an item or sell one item in each city. That is, he cannot do nothing in any city. Describe a greedy algorithm to find the strategy that makes the most profit or, if no profit can be made, make the least loss. Prove its correctness.

Exercise 4. Describe a greedy algorithm that, in each iteration, tries determining the available city of lowest price to buy an item and the corresponding available city with the highest price that is higher than that lowest price to sell an item, staying away from the inadmissible strategies. If it can find the corresponding city, mark both cities as unavailable; otherwise, mark the first city as unavailable. Prove its correctness.

Exercise 5. Can you find a greedy algorithm and prove its correctness in each of the following situations?
(Part a) Suppose he can short items. That is, the number of items hold by him can be as low as $-n$ but not any lower for some positive integer $n$.
(Part b) Suppose for some positive integer $k$, if the number of items held by him is no more than $k$ in the last city, then the total prices of those items will be added to his profit.
(Part c) Suppose he is required to buy in some specified cities and to sell in some other specified cities.

Exercise 6. Show that the best strategy can be verified in linear time of $n$. The characterization theorem on the best strategy tell us that the best strategy only depends on the relative size of the prices. Show that the minimal number of comparisons needed to determine the best strategy for 2, 3, 4, and n cities are 1, 3, 5 and $\Theta(n\log n)$ respectively.

Topic 1. Suppose he can only buy or pass initially until he holds $k$ items for some positive integer $k$. Then he can buy or sell one item or pass as before. (When) is there a greedy algorithm?

Topic 2. Suppose there is a selling cost $t(i)>0$ associated to sell in city $i$ for each $i\in 1..n$. (When) is there a greedy algorithm?

Topic 3. Let $c(n)$ be the minimal number of comparisons needed to sort any $n$ numbers and $z(n)$ be the minimal number of comparisons needed to find a best strategy for any prices in $n$ cities. We know $z(n) \le c(n)$. Is it true that $c(n)=z(n)$ for all $n$?

All above exercises and topics are created by this author except exercise 4 that comes from an answer at Quora

$\endgroup$
  • $\begingroup$ Initially I also thought that matroid can be used to solve it. However, the problem doesn't satisfy the augment property of matroid. $\endgroup$ – zbh2047 Sep 25 '18 at 13:42
  • $\begingroup$ I have understood your whole proof! Also, the exercises and topics are really interesting. By the way, I am a little curious about the random algorithm you mentioned before. Could you explain it, please? $\endgroup$ – zbh2047 Sep 25 '18 at 13:50
  • $\begingroup$ The random algorithm just repeatedly tries increasing the profit by changing the actions on two randomly chosen cities. Before I was convinced that my theorem is correct, I had used this random algorithm to check whether "optimal everywhere" implies the best strategy, which can be computed by dynamic programming. Now that I have the theorem, it can be shown easily that any run of the random algorithm will produce the best strategy eventually with a probability of 1. $\endgroup$ – Apass.Jack Sep 25 '18 at 19:43
  • $\begingroup$ I just updated my answer. @zbh2047. Please take a look. I will make another update that will use the last version of "optimal everywhere". $\endgroup$ – Apass.Jack Oct 1 '18 at 17:53
  • $\begingroup$ It should be completely correct now. Thanks a lot! $\endgroup$ – zbh2047 Oct 2 '18 at 2:41

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.