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