Maximize the expected number of "losers" - Is it NP-hard?
Look at the graph that is formed by the comparisons. Each element corresponds to a vertex. If an element is a vertex of degree $d$, then the probability that it will be the lowest in at least one of these comparisons is the probability that it is not larger than all of its neighbors. This probability is $d/(d+1)$.

Now, expectation is linear. This means that the expected number of losers is $$ \sum_{v \in G} \frac{d_v}{d_v+1}.$$ To illustrate, with your example there is one vertex of degree 2 and two of degree 1, so the expected number of losers is $\frac{2}{3} + \frac{1}{2} + \frac{1}{2} = \frac{5}{3}.\ $ 

It is easy to prove that this quantity is maximized when the degrees of the vertices are all as close to equal as possible, so the vertex degrees all are either $d$ or $d+1$ for some $d$.