# Optimality proof for greedy algorithm

Let $\mathcal{A} = \{a_1, \ldots, a_N\}$ be a set of actions that can be performed on a system $S$. Each action $a_i$, if performed, produces a gain $g_{a_i}(S)$. Moreover, the actions in $\mathcal{A}$ are NOT independent, i.e., the gain of $a_i$ may be lower if $a_j$ was asked earlier. The objective is to find the set of $B$ actions with the highest produced gain.

The algorithm for which I want to prove the optimality is as follows.

The first action $a_1^*$ that is selected is the one maximizing the gain $g_{a_i}(S)$:

$$a_1^* = \arg \max_{a_i \in \mathcal{A}} g_{a_i}(S)$$

The gain of the second action will depend on the action that was performed earlier, i.e.: $$a_2^* = \arg \max_{a_i \in \mathcal{A}\setminus a_1^*} g_{a_i}(S | a_1^*)$$ In general, given a budget $B$ of actions that can be performed, at the $i$-th step I will choose the action: $$a_i^* = \arg \max_{a_j \in \mathcal{A} \setminus A^*} g_{a_j}(S | A^*)$$ where $A^*$ is the set of previously chosen questions.

Is there a formal way of proving that this algorithm is optimal, i.e., that it does not exist any other sequence of $B$ actions that achieve a higher gain?

Thanks.

-
Why do you expect the greedy algorithm to be optimal? Do you have any other (hidden) assumptions? [Otherwise take $\mathcal A = \{a, b, c\}$, $\mathcal B = 2$ (I assume this to be the number of actions before stopping, is this correct?), $g_a(S) = 3$, $g_b(S) = g_c(S) = 2$, $g_x(S|a) = 0$ for $x = a$ or $b$ and $g_x(S|y) = 2$ otherwise]. –  j.p. Jul 8 '13 at 12:31
I expect it to be optimal since experimentally it obtains the same result as A*, that is known to be optimal. Notice that two actions cannot be performed twice, and that the gain achieved by performing a sequence of actions cannot be higher than a threshold T. –  Eleanore Jul 8 '13 at 13:02
I just saw that I phrased my counterexample wrongly [I thought the gains of all steps add up]. If you don't have any other assumptions about the gains [to me it is not clear if in your model the order of actions matter, but this does not change much anyway], you could construct a example where greedy is not optimal, by assigning a "high value" x to some action $a$ and lower values to all other actions in the first step, and then by assigning values greater x to all pairs of actions (u, v) with $u\ne a$ and the value x to pairs of actions starting with a. –  j.p. Jul 8 '13 at 15:21