  The following game is played on a weighted graph: Alice selects a matching
$M$ and Bob selects a number $k$. Alice's payoff is the ratio of the weight of
the $k$ heaviest edges of $M$ to the maximum weight of a matching of size at
most $k$. If $M$ guarantees a payoff of at least $\alpha$ then it is called
$\alpha$-robust. In 2002, Hassin and Rubinstein gave an algorithm that returns
a $1/\sqrt{2}$-robust matching, which is best possible.
  We show that Alice can improve her payoff to $1/\ln(4)$ by playing a
randomized strategy. This result extends to a very general class of
independence systems that includes matroid intersection, b-matchings, and
strong 2-exchange systems. It also implies an improved approximation factor for
a stochastic optimization variant known as the maximum priority matching
problem and translates to an asymptotic robustness guarantee for deterministic
matchings, in which Bob can only select numbers larger than a given constant.
Moreover, we give a new LP-based proof of Hassin and Rubinstein's bound.

Discrete Mathematics;Combinatorics