<p>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)$.</p>

<p>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}.\ $ </p>

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

CC BY-SA 3.0
2013-12-07T20:44:27.810Z
Thank you so much!  
Indeed, in the simple case the probability of a node winning 
all of the $d$ comparisons, it is involved in, 
is $\frac{1}{d+1}$. So the problem is trivial. Thank you for showing it to me.  
When you start with a known partial order, some of the $n!$ permutations
are not possible. The straightforward way would be to count the linear extensions 
of the partial order to find the probability of a node winning all of the $d$ comparisons. Nevertheless, counting the linear extensions is #P-complete.
Do you have any ideas about the hardness of the problem  in this case?
bill
CC BY-SA 3.0
2013-12-07T21:00:55.077Z
My guess is that it's NP-hard, but I don't know how to show it.
Peter Shor 
CC BY-SA 3.0
2013-12-07T21:10:38.967Z
Have you seen any problem similar to this one, where a reduction from it could be possible? Thanks again!
bill
CC BY-SA 3.0
2013-12-07T14:21:40.017Z
2013-12-07T14:21:40.017Z
Peter Shor 
<p>I am trying to find a reduction for a problem that seems NP-hard:</p>

<p>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. </p>

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

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

<p>(2) $a&gt;b$ and $c&lt;b$ with probability $\frac{1}{6}$</p>

<p>(3) $a&lt;b$ and $c&gt;b$ with probability $\frac{1}{6}$</p>

<p>(4) $a&lt;b$ and $c&lt;b$ with probability $\frac{2}{6}$</p>

<p>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:</p>

<p>$\frac{2}{6} * 1 + \frac{1}{6} * 2 + \frac{1}{6} * 2 + \frac{2}{6} * 2 = 1\frac{2}{3}$</p>

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

<p>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&gt;\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.</p>

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

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

<p>Thank you!</p>

<p>[1] Brightwell, Graham R.; Winkler, Peter (1991), "Counting linear extensions", Order 8 (3): 225–242, <a href="http://dx.doi.org/10.1007/BF00383444" rel="nofollow">paper</a></p>

CC BY-SA 3.0
2013-12-07T13:53:34.143Z
First, this can't possibly be NP-hard. There's only a polynomial number of inputs — $n \choose 2$ — for each $n$, and sparse problems can't be NP-hard. If you start with a known partial order, and have $k$ more comparisons, maximizing the number of distinct losers might be NP-hard.
Peter Shor 
<cc.complexity-theory><graph-theory><np-hardness><reductions><directed-acyclic-graph>
Maximize the expected number of "losers" - Is it NP-hard?
bill
# Maximize the expected number of "losers" - Is it NP-hard?

(Asked by: username_0 on 2013-12-07)

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

(3) $ab$ with probability $\frac{1}{6}$

(4) $a

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](http://dx.doi.org/10.1007/BF00383444)

**Tags:** cc.complexity-theory, graph-theory, np-hardness, reductions, directed-acyclic-graph

> **Comments:**
> **username_1**: First, this can't possibly be NP-hard. There's only a polynomial number of inputs — $n \choose 2$ — for each $n$, and sparse problems can't be NP-hard. If you start with a known partial order, and have $k$ more comparisons, maximizing the number of distinct losers might be NP-hard.  

---

## 1 answers

### Answer by username_1 on 2013-12-07. Score: 6 | Accepted answer

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

> **Comments:**
> **username_0**: Thank you so much!   Indeed, in the simple case the probability of a node winning  all of the $d$ comparisons, it is involved in,  is $\frac{1}{d+1}$. So the problem is trivial. Thank you for showing it to me.   When you start with a known partial order, some of the $n!$ permutations are not possible. The straightforward way would be to count the linear extensions  of the partial order to find the probability of a node winning all of the $d$ comparisons. Nevertheless, counting the linear extensions is #P-complete. Do you have any ideas about the hardness of the problem  in this case?  
> **username_1**: My guess is that it's NP-hard, but I don't know how to show it.  
> **username_0**: Have you seen any problem similar to this one, where a reduction from it could be possible? Thanks again!  

---

