Matching theory is among the most fundamental graph optimization problems. Several different variants of this problem have been introduced and studied. Maximum matching, capacitated matching, and perfect matchings are all well studied examples of problems in matching theory. Here we motivate and study a generalization of the maximum weighted matching problem, so-called k-scenario matching. In k-scenario matching we are given a graph \(G=(V,E)\) , in which each edge belongs to at least one of the k subsets \(E_1,...,E_k\) (scenarios), and each scenario is equipped with probability \(p_i\) for each \(1\le i \le k\) (hence \(\sum _{i=1}^k p_i = 1\) ). We are provided with budget, some integer B, and our goal is to find a subset \(\hat{E}\subseteq E\) of size at most B, that maximizes the expected value of the maximum cardinality matchings on all the possible k scenarios (i.e. \(\sum _{i=1}^k p_i |M_i|\) where \(M_i\) is a maximum matching on edges \(\hat{E}\cap E_i\) .) This problem is motivated by applications such as kidney exchange, where compatibility between donors and patients is uncertain. Tests must be performed to ascertain whether two vertices can be matched, but due to the time and cost involved, only a limited number of tests are possible. In this paper we show that this problem is NP-hard even in the simple case where we have two scenarios, and the input graph is both bipartite and sub-cubic. We also study the approximability of this problem in several cases from the positive direction. For the general case of this problem, we find a 2.314-approximation by a natural greedy algorithm. We then present two approximation algorithms for the case where there are two scenarios. When \(p_1=p_2=\frac{1}{2}\) , our first algorithm achieves a \(\frac{11}{9}\) -approximation. When \(p_1 \ne p_2\) , we show that this problem admits a \(\frac{5}{4}\) -approximation. For the general case of this problem, we find a 2.314-approximation by a natural greedy algorithm.