We propose a non-asymptotic approach to analyze kidney exchange that builds on the random graph model of kidney exchange introduced in Ashlagi, Garmarnik, Rees and Roth's "The need for (long) chains in kidney exchange" (2012). We analyze a two phase procedure where random walks are used to allocate chains, followed by allocation via matching in cycles. Random walks preserve the probabilistic structure of residual graphs, greatly facilitating analysis without sending the number of nodes to infinity. We derive useful analytical bounds that illustrate the performance of our procedure and more general kidney allocation procedures. Our results complement previous asymptotic results for large (limit) graphs on the benefits of using chains in kidney exchange and empirical results based on data from fielded kidney exchanges.

We consider a robust model proposed by Scarf, 1958, for stochastic optimization when only the marginal probabilities of (binary) random variables are given, and the correlation between the random variables is unknown. In the robust model, the objective is to minimize expected cost against worst possible joint distribution with those marginals. We introduce the concept of correlation gap to compare this model to the stochastic optimization model that ignores correlations and minimizes expected cost under independent Bernoulli distribution. We identify a class of functions, using concepts of summable cost sharing schemes from game theory, for which the correlation gap is well-bounded and the robust model can be approximated closely by the independent distribution model. As a result, we derive efficient approximation factors for many popular cost functions, like submodular functions, facility location, and Steiner tree. As a byproduct, our analysis also yields some new results in the areas of social welfare maximization and existence of Walrasian equilibria, which may be of independent interest.