Solutions:

1. Let's consider the world from the point of view of some immortal X. We will prove the following statement:

Regardless of how many other immortals N there are, if their total power is Tot then X's chances of winning are P(X)/(P(X) + Tot) regardless of the order of duels.

The statement is clearly true if there is just one other immortal (i.e. N =1). We will prove that if it is true for all immortals up to N = k, then it is true for all up to N = k+1. In general, before the last fight, X has faced some set J of immortals either directly or indirectly (i.e., among those J, some have killed others). At that point X has some power JPower which is the sum of P(X) plus the original power of those J other immortals. The remaining set have power [Tot + P(X) – Jpower]. Therefore X's probability of winning is (JPower/(JPower + Tot + P(X) - JPower) = JPower/(Tot + P(X)). Given this statement, order doesn't matter. Aggression doesn't contribute to overall safety.

2. The probabilities are such that the initiator and the first non-initiator have the same probability 0.36(0.5 * 0.8 * 0.9), the second non-initiator has probability 0.18 of surviving and the last non-initiator has probability 0.10.

3. The initiator should start from the least powerful and go to the most powerful. If he does that, his first chance of winning will be

(1/2) against non-initiator having power 1,
(1/2) against non-initiator having power 2,
(1/2) against non-initiator having power 4,
with a resulting probability for surviving all the duels of 1/8.

If the initiator instead starts with the non-initiator having power 4, his chances of winning that duel alone are only 1/16. The odds are less bad but in the same discouraging spirit if the initiator starts with the middle non-initiator.

4. It is better for the initiators to start fighting one another than for each initiator to start fighting a non-initiator. In the former case the probabilities are 0.36 and 0.36 for the two initiators, and (0.18)[(1/5) * (9/10)] and 0.10 for the first and second non-initiator, respectively. If each initiator starts to fight a non-initiator, the probabilities are 0.25 for each of the four immortals.

5. If you have a choice between weaker initiators and stronger ones, then choose weaker ones. If all initiators have the same initial power and work just as fast as one another, then it is better for them to face one another first.

Ivan Rezanka helped greatly with all aspects of this puzzle.