Are convex combinations of 0-1 Pareto efficient vectors efficient?

Question

Let $Y$ be any subset of $\{0,1\}^n$ for $n\geq3$. A vector $\alpha\in$ $Y$ is Pareto efficient if there is no $\beta\in$ $Y$ such that $\beta_i$ $\geq$ $\alpha_i$ for each $i\in\{1,...,n\}$ and $\beta_j>\alpha_j$ for some $j\in\{1,...,n\}$. Let $PE$ be the set of all Pareto efficient vectors in $Y$.

Let $Z=conv(Y)$ where $conv(.)$ denotes convex hull. $x\in$ $Z$ is efficient if there is no $y\in$ $Z$ such that $y_i\geq$ $x_i$ for each $i\in\{1,...,n\}$ and $y_j>$ $x_j$ for some $j\in\{1,...,n\}$. Let $E$ be the set of all efficient vectors in $Z$.

Is it true that $E=conv(PE)$? This is obviously true when $|PE|=1$. So, kindly consider the case when that is not the case. Thanks!

It might be helpful to consider this as a maximization problem over 0-1 polytopes.

Answer 1

Here is a counter-example: let $A=(1,0,0,0,0,1)$, $B=(1,1,1,0,0,0)$, $C=(0,0,1,1,0,0)$ and $D=(0,0,0,1,1,1)$. Take $Y=\{A,B,C,D\}$. Then:

• $PE=\{A,B,C,D\}$, so that $conv(PE)=Z$.

• The vector $(.5,0,.5,.5,0,.5)$ is in $conv(PE)=Z$, but it is not in $E$ since $(.5,.5,.5,.5,.5,.5)$ is also in $Z$.

(The second or the fourth coordinate can be deleted in the example, to get an example with only five coordinates. I am not sure whether that is smallest possible).