  In this paper, we study contention resolution schemes for matchings. Given a
fractional matching $x$ and a random set $R(x)$ where each edge $e$ appears
independently with probability $x_e$, we want to select a matching $M \subseteq
R(x)$ such that $\Pr[e \in M \mid e \in R(x)] \geq c$, for $c$ as large as
possible. We call such a selection method a $c$-balanced contention resolution
scheme.
  Our main results are (i) an asymptotically (in the limit as $\|x\|_\infty$
goes to 0) optimal $\simeq 0.544$-balanced contention resolution scheme for
general matchings, and (ii) a $0.509$-balanced contention resolution scheme for
bipartite matchings. To the best of our knowledge, this result establishes for
the first time, in any natural relaxation of a combinatorial optimization
problem, a separation between (i) offline and random order online contention
resolution schemes, and (ii) monotone and non-monotone contention resolution
schemes. We also present an application of our scheme to a combinatorial
allocation problem, and discuss some open questions related to van der
Waerden's conjecture for the permanent of doubly stochastic matrices.
