Maximize the expected number of “losers” - Is it NP-hard?

Question

I am trying to find a reduction for a problem that seems NP-hard:

Let me start from a toy example. Consider 3 elements, $a$, $b$, and $c$. You want to choose two pairs out of the three pairs and compare the two elements of each pair. There is a true underlying ordering of the elements, which we don't know. Our objective is to pick the comparisons that will maximize, in expectation, the number of elements that will "lose" at least one comparison.

For example, lets assume that we choose $(a,b)$ and $(b,c)$. There are four possibilities:

(1) $a>b$ and $c>b$ with probability $\frac{2}{6}$ ($2$ out of the $3!$ possible permutations respect $a>b$ and $c>b$)

(2) $a>b$ and $c<b$ with probability $\frac{1}{6}$

(3) $a<b$ and $c>b$ with probability $\frac{1}{6}$

(4) $a<b$ and $c<b$ with probability $\frac{2}{6}$

In the case of (1), only $b$ loses at least one comparison, in (2), $b$ and $c$ lose at least one comparison, and so on. The expected number of elements losing at least one comparison is:

$\frac{2}{6} * 1 + \frac{1}{6} * 2 + \frac{1}{6} * 2 + \frac{2}{6} * 2 = 1\frac{2}{3}$

Note that the outcome of each comparison is based on the true ordering, which we don't know..

In this toy example, any two pairs give the same expected number of "losers". In its general form, the problem states that we have $n$ elements, and we can ask for $b$ comparisons (the problem becomes interesting when $b>\frac{n}{2}$). Making it even more general, we can have the outcome of previous comparisons as input and try to maximize the "losers" out of those elements that still haven't lost any comparison. I am interested in the second, more general, case but I feel that even without the previous comparisons' outcome, the problem is still NP-hard.

The most helpful result I have found until now, is that counting linear extensions of a partially ordered set is #P-complete [1].

I would greatly appreciate any ideas about a reduction, or any obvious reduction that I can not see.

Thank you!

[1] Brightwell, Graham R.; Winkler, Peter (1991), "Counting linear extensions", Order 8 (3): 225–242, paper

Answer 1

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$.