  The Condorcet criterion (CC) is a classical and well-accepted criterion for
voting. Unfortunately, it is incompatible with many other desiderata including
participation (Par), half-way monotonicity (HM), Maskin monotonicity (MM), and
strategy-proofness (SP). Such incompatibilities are often known as
impossibility theorems, and are proved by worst-case analysis. Previous work
has investigated the likelihood for these impossibilities to occur under
certain models, which are often criticized of being unrealistic.
  We strengthen previous work by proving the first set of semi-random
impossibilities for voting rules to satisfy CC and the more general, group
versions of the four desiderata: for any sufficiently large number of voters
$n$, any size of the group $1\le B\le \sqrt n$, any voting rule $r$, and under
a large class of {\em semi-random} models that include Impartial Culture, the
likelihood for $r$ to satisfy CC and Par, CC and HM, CC and MM, or CC and SP is
$1-\Omega(\frac{B}{\sqrt n})$. This matches existing lower bounds for CC and
Par ($B=1$) and CC and SP ($B\le \sqrt n$), showing that many commonly-studied
voting rules are already asymptotically optimal in such cases.
